lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp

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