lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp

   1 //===-- FunctionLiveVarInfo.cpp - Live Variable Analysis for a Function ---===//
   2 //
   3 // This is the interface to function level live variable information that is
   4 // provided by live variable analysis.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "llvm/CodeGen/FunctionLiveVarInfo.h"
   9 #include "llvm/CodeGen/MachineInstr.h"
  10 #include "llvm/CodeGen/MachineFunction.h"
  11 #include "llvm/Target/TargetMachine.h"
  12 #include "llvm/Target/TargetInstrInfo.h"
  13 #include "llvm/Support/CFG.h"
  14 #include "Support/PostOrderIterator.h"
  15 #include "Support/SetOperations.h"
  16 #include "Support/CommandLine.h"
  17 #include "BBLiveVar.h"
  18
  19 static RegisterAnalysis<FunctionLiveVarInfo>
  20 X("livevar", "Live Variable Analysis");
  21
  22 LiveVarDebugLevel_t DEBUG_LV;
  23
  24 static cl::opt<LiveVarDebugLevel_t, true>
  25 DEBUG_LV_opt("dlivevar", cl::Hidden, cl::location(DEBUG_LV),
  26              cl::desc("enable live-variable debugging information"),
  27              cl::values(
  28 clEnumValN(LV_DEBUG_None   , "n", "disable debug output"),
  29 clEnumValN(LV_DEBUG_Normal , "y", "enable debug output"),
  30 clEnumValN(LV_DEBUG_Instr,   "i", "print live-var sets before/after "
  31            "every machine instrn"),
  32 clEnumValN(LV_DEBUG_Verbose, "v", "print def, use sets for every instrn also"),
  33                         0));
  34
  35
  36
  37 //-----------------------------------------------------------------------------
  38 // Accessor Functions
  39 //-----------------------------------------------------------------------------
  40
  41 // gets OutSet of a BB
  42 const ValueSet &FunctionLiveVarInfo::getOutSetOfBB(const BasicBlock *BB) const {
  43   return BBLiveVar::GetFromBB(*BB)->getOutSet();
  44 }
  45       ValueSet &FunctionLiveVarInfo::getOutSetOfBB(const BasicBlock *BB)       {
  46   return BBLiveVar::GetFromBB(*BB)->getOutSet();
  47 }
  48
  49 // gets InSet of a BB
  50 const ValueSet &FunctionLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const {
  51   return BBLiveVar::GetFromBB(*BB)->getInSet();
  52 }
  53       ValueSet &FunctionLiveVarInfo::getInSetOfBB(const BasicBlock *BB)       {
  54   return BBLiveVar::GetFromBB(*BB)->getInSet();
  55 }
  56
  57
  58 //-----------------------------------------------------------------------------
  59 // Performs live var analysis for a function
  60 //-----------------------------------------------------------------------------
  61
  62 bool FunctionLiveVarInfo::runOnFunction(Function &F) {
  63   M = &F;
  64   if (DEBUG_LV) std::cerr << "Analysing live variables ...\n";
  65
  66   // create and initialize all the BBLiveVars of the CFG
  67   constructBBs(M);
  68
  69   unsigned int iter=0;
  70   while (doSingleBackwardPass(M, iter++))
  71     ; // Iterate until we are done.
  72
  73   if (DEBUG_LV) std::cerr << "Live Variable Analysis complete!\n";
  74   return false;
  75 }
  76
  77
  78 //-----------------------------------------------------------------------------
  79 // constructs BBLiveVars and init Def and In sets
  80 //-----------------------------------------------------------------------------
  81
  82 void FunctionLiveVarInfo::constructBBs(const Function *F) {
  83   unsigned POId = 0;                // Reverse Depth-first Order ID
  84   std::map<const BasicBlock*, unsigned> PONumbering;
  85
  86   for (po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
  87       BBI != BBE; ++BBI)
  88     PONumbering[*BBI] = POId++;
  89
  90   MachineFunction &MF = MachineFunction::get(F);
  91   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
  92     const BasicBlock &BB = *I->getBasicBlock();        // get the current BB
  93     if (DEBUG_LV) std::cerr << " For BB " << RAV(BB) << ":\n";
  94
  95     BBLiveVar *LVBB;
  96     std::map<const BasicBlock*, unsigned>::iterator POI = PONumbering.find(&BB);
  97     if (POI != PONumbering.end()) {
  98       // create a new BBLiveVar
  99       LVBB = BBLiveVar::CreateOnBB(BB, *I, POId);
 100     } else {
 101       // The PO iterator does not discover unreachable blocks, but the random
 102       // iterator later may access these blocks.  We must make sure to
 103       // initialize unreachable blocks as well.  However, LV info is not correct
 104       // for those blocks (they are not analyzed)
 105       //
 106       LVBB = BBLiveVar::CreateOnBB(BB, *I, ++POId);
 107     }
 108
 109     if (DEBUG_LV)
 110       LVBB->printAllSets();
 111   }
 112 }
 113
 114
 115 //-----------------------------------------------------------------------------
 116 // do one backward pass over the CFG (for iterative analysis)
 117 //-----------------------------------------------------------------------------
 118
 119 bool FunctionLiveVarInfo::doSingleBackwardPass(const Function *M,
 120                                                unsigned iter) {
 121   if (DEBUG_LV) std::cerr << "\n After Backward Pass " << iter << "...\n";
 122
 123   bool NeedAnotherIteration = false;
 124   for (po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
 125        BBI != BBE; ++BBI) {
 126     BBLiveVar *LVBB = BBLiveVar::GetFromBB(**BBI);
 127     assert(LVBB && "BasicBlock information not set for block!");
 128
 129     if (DEBUG_LV) std::cerr << " For BB " << (*BBI)->getName() << ":\n";
 130
 131     // InSets are initialized to "GenSet". Recompute only if OutSet changed.
 132     if(LVBB->isOutSetChanged())
 133       LVBB->applyTransferFunc();        // apply the Tran Func to calc InSet
 134
 135     // OutSets are initialized to EMPTY.  Recompute on first iter or if InSet
 136     // changed.
 137     if (iter == 0 || LVBB->isInSetChanged())        // to calc Outsets of preds
 138       NeedAnotherIteration |= LVBB->applyFlowFunc();
 139
 140     if (DEBUG_LV) LVBB->printInOutSets();
 141   }
 142
 143   // true if we need to reiterate over the CFG
 144   return NeedAnotherIteration;
 145 }
 146
 147
 148 void FunctionLiveVarInfo::releaseMemory() {
 149   // First remove all BBLiveVar annotations created in constructBBs().
 150   if (M)
 151     for (Function::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
 152       BBLiveVar::RemoveFromBB(*I);
 153   M = 0;
 154
 155   // Then delete all objects of type ValueSet created in calcLiveVarSetsForBB
 156   // and entered into MInst2LVSetBI and MInst2LVSetAI (these are caches
 157   // to return ValueSet's before/after a machine instruction quickly).
 158   // We do not need to free up ValueSets in MInst2LVSetAI because it holds
 159   // pointers to the same sets as in MInst2LVSetBI (for all instructions
 160   // except the last one in a BB) or in BBLiveVar (for the last instruction).
 161   //
 162   for (hash_map<const MachineInstr*, ValueSet*>::iterator
 163          MI = MInst2LVSetBI.begin(),
 164          ME = MInst2LVSetBI.end(); MI != ME; ++MI)
 165     delete MI->second;           // delete all ValueSets in  MInst2LVSetBI
 166
 167   MInst2LVSetBI.clear();
 168   MInst2LVSetAI.clear();
 169 }
 170
 171
 172
 173
 174 //-----------------------------------------------------------------------------
 175 // Following functions will give the LiveVar info for any machine instr in
 176 // a function. It should be called after a call to analyze().
 177 //
 178 // Thsese functions calucluates live var info for all the machine instrs in a
 179 // BB when LVInfo for one inst is requested. Hence, this function is useful
 180 // when live var info is required for many (or all) instructions in a basic
 181 // block. Also, the arguments to this function does not require specific
 182 // iterators.
 183 //-----------------------------------------------------------------------------
 184
 185 //-----------------------------------------------------------------------------
 186 // Gives live variable information before a machine instruction
 187 //-----------------------------------------------------------------------------
 188
 189 const ValueSet &
 190 FunctionLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *MI,
 191                                               const BasicBlock *BB) {
 192   ValueSet* &LVSet = MInst2LVSetBI[MI]; // ref. to map entry
 193   if (LVSet == NULL && BB != NULL) {    // if not found and BB provided
 194     calcLiveVarSetsForBB(BB);           // calc LVSet for all instrs in BB
 195     assert(LVSet != NULL);
 196   }
 197   return *LVSet;
 198 }
 199
 200
 201 //-----------------------------------------------------------------------------
 202 // Gives live variable information after a machine instruction
 203 //-----------------------------------------------------------------------------
 204
 205 const ValueSet &
 206 FunctionLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *MI,
 207                                              const BasicBlock *BB) {
 208
 209   ValueSet* &LVSet = MInst2LVSetAI[MI]; // ref. to map entry
 210   if (LVSet == NULL && BB != NULL) {    // if not found and BB provided
 211     calcLiveVarSetsForBB(BB);           // calc LVSet for all instrs in BB
 212     assert(LVSet != NULL);
 213   }
 214   return *LVSet;
 215 }
 216
 217 // This function applies a machine instr to a live var set (accepts OutSet) and
 218 // makes necessary changes to it (produces InSet). Note that two for loops are
 219 // used to first kill all defs and then to add all uses. This is because there
 220 // can be instructions like Val = Val + 1 since we allow multipe defs to a
 221 // machine instruction operand.
 222 //
 223 static void applyTranferFuncForMInst(ValueSet &LVS, const MachineInstr *MInst) {
 224   for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
 225          OpE = MInst->end(); OpI != OpE; ++OpI) {
 226     if (OpI.isDefOnly() || OpI.isDefAndUse()) // kill if this operand is a def
 227       LVS.erase(*OpI);                        // this definition kills any uses
 228   }
 229
 230   // do for implicit operands as well
 231   for (unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
 232     if (MInst->getImplicitOp(i).opIsDefOnly() ||
 233         MInst->getImplicitOp(i).opIsDefAndUse())
 234       LVS.erase(MInst->getImplicitRef(i));
 235   }
 236
 237   for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
 238          OpE = MInst->end(); OpI != OpE; ++OpI) {
 239     if (!isa<BasicBlock>(*OpI))      // don't process labels
 240       // add only if this operand is a use
 241       if (!OpI.isDefOnly() || OpI.isDefAndUse() )
 242         LVS.insert(*OpI);            // An operand is a use - so add to use set
 243   }
 244
 245   // do for implicit operands as well
 246   for (unsigned i = 0, e = MInst->getNumImplicitRefs(); i != e; ++i)
 247     if (MInst->getImplicitOp(i).opIsUse() ||
 248         MInst->getImplicitOp(i).opIsDefAndUse())
 249       LVS.insert(MInst->getImplicitRef(i));
 250 }
 251
 252 //-----------------------------------------------------------------------------
 253 // This method calculates the live variable information for all the
 254 // instructions in a basic block and enter the newly constructed live
 255 // variable sets into a the caches (MInst2LVSetAI, MInst2LVSetBI)
 256 //-----------------------------------------------------------------------------
 257
 258 void FunctionLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
 259   BBLiveVar *BBLV = BBLiveVar::GetFromBB(*BB);
 260   assert(BBLV && "BBLiveVar annotation doesn't exist?");
 261   const MachineBasicBlock &MIVec = BBLV->getMachineBasicBlock();
 262   const MachineFunction &MF = MachineFunction::get(M);
 263   const TargetMachine &TM = MF.getTarget();
 264
 265   if (DEBUG_LV >= LV_DEBUG_Instr)
 266     std::cerr << "\n======For BB " << BB->getName()
 267               << ": Live var sets for instructions======\n";
 268
 269   ValueSet *SetAI = &getOutSetOfBB(BB);         // init SetAI with OutSet
 270   ValueSet CurSet(*SetAI);                      // CurSet now contains OutSet
 271
 272   // iterate over all the machine instructions in BB
 273   for (MachineBasicBlock::const_reverse_iterator MII = MIVec.rbegin(),
 274          MIE = MIVec.rend(); MII != MIE; ++MII) {
 275     // MI is cur machine inst
 276     const MachineInstr *MI = *MII;
 277
 278     MInst2LVSetAI[MI] = SetAI;                 // record in After Inst map
 279
 280     applyTranferFuncForMInst(CurSet, MI);      // apply the transfer Func
 281     ValueSet *NewSet = new ValueSet(CurSet);   // create a new set with a copy
 282                                                // of the set after T/F
 283     MInst2LVSetBI[MI] = NewSet;                // record in Before Inst map
 284
 285     // If the current machine instruction has delay slots, mark values
 286     // used by this instruction as live before and after each delay slot
 287     // instruction (After(MI) is the same as Before(MI+1) except for last MI).
 288     if (unsigned DS = TM.getInstrInfo().getNumDelaySlots(MI->getOpCode())) {
 289       MachineBasicBlock::const_iterator fwdMII = MII.base(); // ptr to *next* MI
 290       for (unsigned i = 0; i < DS; ++i, ++fwdMII) {
 291         assert(fwdMII != MIVec.end() && "Missing instruction in delay slot?");
 292         MachineInstr* DelaySlotMI = *fwdMII;
 293         if (! TM.getInstrInfo().isNop(DelaySlotMI->getOpCode())) {
 294           set_union(*MInst2LVSetBI[DelaySlotMI], *NewSet);
 295           if (i+1 == DS)
 296             set_union(*MInst2LVSetAI[DelaySlotMI], *NewSet);
 297         }
 298       }
 299     }
 300
 301     if (DEBUG_LV >= LV_DEBUG_Instr) {
 302       std::cerr << "\nLive var sets before/after instruction " << *MI;
 303       std::cerr << "  Before: ";   printSet(*NewSet);  std::cerr << "\n";
 304       std::cerr << "  After : ";   printSet(*SetAI);   std::cerr << "\n";
 305     }
 306
 307     // SetAI will be used in the next iteration
 308     SetAI = NewSet;
 309   }
 310 }