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