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