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