lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp

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