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