lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp

   1 /* Title:   MethodLiveVarInfo.cpp
   2    Author:  Ruchira Sasanka
   3    Date:    Jun 30, 01
   4    Purpose:
   5
   6    This is the interface for live variable info of a method that is required
   7    by any other part of the compiler.
   8
   9 */
  10
  11
  12 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
  13 #include "llvm/CodeGen/MachineInstr.h"
  14 #include "llvm/BasicBlock.h"
  15 #include "Support/PostOrderIterator.h"
  16 #include <iostream>
  17
  18 AnalysisID MethodLiveVarInfo::ID(AnalysisID::create<MethodLiveVarInfo>());
  19
  20
  21 //-----------------------------------------------------------------------------
  22 // Performs live var analysis for a method
  23 //-----------------------------------------------------------------------------
  24
  25 bool MethodLiveVarInfo::runOnMethod(Method *M) {
  26   if (DEBUG_LV) std::cerr << "Analysing live variables ...\n";
  27
  28   // create and initialize all the BBLiveVars of the CFG
  29   constructBBs(M);
  30
  31   while (doSingleBackwardPass(M))
  32     ; // Iterate until we are done.
  33
  34   if (DEBUG_LV) std::cerr << "Live Variable Analysis complete!\n";
  35   return false;
  36 }
  37
  38
  39 //-----------------------------------------------------------------------------
  40 // constructs BBLiveVars and init Def and In sets
  41 //-----------------------------------------------------------------------------
  42
  43 void MethodLiveVarInfo::constructBBs(const Method *M) {
  44   unsigned int POId = 0;                // Reverse Depth-first Order ID
  45
  46   for(po_iterator<const Method*> BBI = po_begin(M), BBE = po_end(M);
  47       BBI != BBE; ++BBI, ++POId) {
  48     const BasicBlock *BB = *BBI;        // get the current BB
  49
  50     if (DEBUG_LV) { std::cerr << " For BB "; printValue(BB); cerr << ":\n"; }
  51
  52     // create a new BBLiveVar
  53     BBLiveVar *LVBB = new BBLiveVar(BB, POId);
  54     BB2BBLVMap[BB] = LVBB;              // insert the pair to Map
  55
  56     LVBB->calcDefUseSets();             // calculates the def and in set
  57
  58     if (DEBUG_LV)
  59       LVBB->printAllSets();
  60   }
  61
  62   // Since the PO iterator does not discover unreachable blocks,
  63   // go over the random iterator and init those blocks as well.
  64   // However, LV info is not correct for those blocks (they are not
  65   // analyzed)
  66   //
  67   for (Method::const_iterator BBRI = M->begin(), BBRE = M->end();
  68        BBRI != BBRE; ++BBRI, ++POId)
  69     if (!BB2BBLVMap[*BBRI])                  // Not yet processed?
  70       BB2BBLVMap[*BBRI] = new BBLiveVar(*BBRI, POId);
  71 }
  72
  73
  74 //-----------------------------------------------------------------------------
  75 // do one backward pass over the CFG (for iterative analysis)
  76 //-----------------------------------------------------------------------------
  77
  78 bool MethodLiveVarInfo::doSingleBackwardPass(const Method *M) {
  79   if (DEBUG_LV) std::cerr << "\n After Backward Pass ...\n";
  80
  81   bool NeedAnotherIteration = false;
  82   for (po_iterator<const Method*> BBI = po_begin(M); BBI != po_end(M) ; ++BBI) {
  83     BBLiveVar *LVBB = BB2BBLVMap[*BBI];
  84     assert(LVBB && "BasicBlock information not set for block!");
  85
  86     if (DEBUG_LV) std::cerr << " For BB " << (*BBI)->getName() << ":\n";
  87
  88     if(LVBB->isOutSetChanged())
  89       LVBB->applyTransferFunc();        // apply the Tran Func to calc InSet
  90
  91     if (LVBB->isInSetChanged())        // to calc Outsets of preds
  92       NeedAnotherIteration |= LVBB->applyFlowFunc(BB2BBLVMap);
  93
  94     if (DEBUG_LV) LVBB->printInOutSets();
  95   }
  96
  97   // true if we need to reiterate over the CFG
  98   return NeedAnotherIteration;
  99 }
 100
 101
 102 void MethodLiveVarInfo::releaseMemory() {
 103   // First delete all BBLiveVar objects created in constructBBs(). A new object
 104   // of type BBLiveVar is created for every BasicBlock in the method
 105   //
 106   for (BBToBBLiveVarMapType::iterator HMI = BB2BBLVMap.begin(),
 107          HME = BB2BBLVMap.end(); HMI != HME; ++HMI)
 108     delete HMI->second;                // delete all BBLiveVar in BB2BBLVMap
 109
 110   BB2BBLVMap.clear();
 111
 112   // Then delete all objects of type LiveVarSet created in calcLiveVarSetsForBB
 113   // and entered into  MInst2LVSetBI and  MInst2LVSetAI (these are caches
 114   // to return LiveVarSet's before/after a machine instruction quickly). It
 115   // is sufficient to free up all LiveVarSet using only one cache since
 116   // both caches refer to the same sets
 117   //
 118   for (MInstToLiveVarSetMapType::iterator MI = MInst2LVSetBI.begin(),
 119          ME = MInst2LVSetBI.end(); MI != ME; ++MI)
 120     delete MI->second;           // delete all LiveVarSets in  MInst2LVSetBI
 121
 122   MInst2LVSetBI.clear();
 123   MInst2LVSetAI.clear();
 124 }
 125
 126
 127
 128
 129 //-----------------------------------------------------------------------------
 130 // Following functions will give the LiveVar info for any machine instr in
 131 // a method. It should be called after a call to analyze().
 132 //
 133 // Thsese functions calucluates live var info for all the machine instrs in a
 134 // BB when LVInfo for one inst is requested. Hence, this function is useful
 135 // when live var info is required for many (or all) instructions in a basic
 136 // block. Also, the arguments to this method does not require specific
 137 // iterators.
 138 //-----------------------------------------------------------------------------
 139
 140 //-----------------------------------------------------------------------------
 141 // Gives live variable information before a machine instruction
 142 //-----------------------------------------------------------------------------
 143
 144 const LiveVarSet *
 145 MethodLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *MInst,
 146                                             const BasicBlock *BB) {
 147   if (const LiveVarSet *LVSet = MInst2LVSetBI[MInst]) {
 148     return LVSet;                      // if found, just return the set
 149   } else {
 150     calcLiveVarSetsForBB(BB);          // else, calc for all instrs in BB
 151     return MInst2LVSetBI[MInst];
 152   }
 153 }
 154
 155
 156 //-----------------------------------------------------------------------------
 157 // Gives live variable information after a machine instruction
 158 //-----------------------------------------------------------------------------
 159 const LiveVarSet *
 160 MethodLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *MI,
 161                                            const BasicBlock *BB) {
 162
 163   if (const LiveVarSet *LVSet = MInst2LVSetAI[MI]) {
 164     return LVSet;                       // if found, just return the set
 165   } else {
 166     calcLiveVarSetsForBB(BB);           // else, calc for all instrs in BB
 167     return MInst2LVSetAI[MI];
 168   }
 169 }
 170
 171
 172
 173 //-----------------------------------------------------------------------------
 174 // This method calculates the live variable information for all the
 175 // instructions in a basic block and enter the newly constructed live
 176 // variable sets into a the caches (MInst2LVSetAI, MInst2LVSetBI)
 177 //-----------------------------------------------------------------------------
 178
 179 void MethodLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
 180   const MachineCodeForBasicBlock &MIVec = BB->getMachineInstrVec();
 181
 182   LiveVarSet *CurSet = new LiveVarSet();
 183   const LiveVarSet *SetAI = getOutSetOfBB(BB); // init SetAI with OutSet
 184   CurSet->setUnion(SetAI);                     // CurSet now contains OutSet
 185
 186   // iterate over all the machine instructions in BB
 187   for (MachineCodeForBasicBlock::const_reverse_iterator MII = MIVec.rbegin(),
 188          MIE = MIVec.rend(); MII != MIE; ++MII) {
 189     // MI is cur machine inst
 190     const MachineInstr *MI = *MII;
 191
 192     MInst2LVSetAI[MI] = SetAI;                 // record in After Inst map
 193
 194     CurSet->applyTranferFuncForMInst(MI);      // apply the transfer Func
 195     LiveVarSet *NewSet = new LiveVarSet();     // create a new set and
 196     NewSet->setUnion(CurSet);                  // copy the set after T/F to it
 197
 198     MInst2LVSetBI[MI] = NewSet;                // record in Before Inst map
 199
 200     // SetAI will be used in the next iteration
 201     SetAI = NewSet;
 202   }
 203 }