lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp

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