LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

FunctionLiveVarInfo.cpp

Go to the documentation of this file.
00001 //===-- FunctionLiveVarInfo.cpp - Live Variable Analysis for a Function ---===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This is the interface to function level live variable information that is
00011 // provided by live variable analysis.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "FunctionLiveVarInfo.h"
00016 #include "llvm/CodeGen/MachineInstr.h"
00017 #include "llvm/CodeGen/MachineFunction.h"
00018 #include "llvm/Target/TargetMachine.h"
00019 #include "llvm/Target/TargetInstrInfo.h"
00020 #include "llvm/Support/CFG.h"
00021 #include "llvm/ADT/PostOrderIterator.h"
00022 #include "llvm/ADT/SetOperations.h"
00023 #include "llvm/Support/CommandLine.h"
00024 #include "BBLiveVar.h"
00025 #include <iostream>
00026 
00027 namespace llvm {
00028 
00029 static RegisterAnalysis<FunctionLiveVarInfo>
00030 X("livevar", "Live Variable Analysis");
00031 
00032 LiveVarDebugLevel_t DEBUG_LV;
00033 
00034 static cl::opt<LiveVarDebugLevel_t, true>
00035 DEBUG_LV_opt("dlivevar", cl::Hidden, cl::location(DEBUG_LV),
00036              cl::desc("enable live-variable debugging information"),
00037              cl::values(
00038 clEnumValN(LV_DEBUG_None   , "n", "disable debug output"),
00039 clEnumValN(LV_DEBUG_Normal , "y", "enable debug output"),
00040 clEnumValN(LV_DEBUG_Instr,   "i", "print live-var sets before/after "
00041            "every machine instrn"),
00042 clEnumValN(LV_DEBUG_Verbose, "v", "print def, use sets for every instrn also"),
00043                         clEnumValEnd));
00044 
00045 
00046 
00047 //-----------------------------------------------------------------------------
00048 // Accessor Functions
00049 //-----------------------------------------------------------------------------
00050 
00051 // gets OutSet of a BB
00052 const ValueSet &FunctionLiveVarInfo::getOutSetOfBB(const BasicBlock *BB) const {
00053   return BBLiveVarInfo.find(BB)->second->getOutSet();
00054 }
00055       ValueSet &FunctionLiveVarInfo::getOutSetOfBB(const BasicBlock *BB)       {
00056   return BBLiveVarInfo[BB]->getOutSet();
00057 }
00058 
00059 // gets InSet of a BB
00060 const ValueSet &FunctionLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const {
00061   return BBLiveVarInfo.find(BB)->second->getInSet();
00062 }
00063 ValueSet &FunctionLiveVarInfo::getInSetOfBB(const BasicBlock *BB) {
00064   return BBLiveVarInfo[BB]->getInSet();
00065 }
00066 
00067 
00068 //-----------------------------------------------------------------------------
00069 // Performs live var analysis for a function
00070 //-----------------------------------------------------------------------------
00071 
00072 bool FunctionLiveVarInfo::runOnFunction(Function &F) {
00073   M = &F;
00074   if (DEBUG_LV) std::cerr << "Analysing live variables ...\n";
00075 
00076   // create and initialize all the BBLiveVars of the CFG
00077   constructBBs(M);
00078 
00079   unsigned int iter=0;
00080   while (doSingleBackwardPass(M, iter++))
00081     ; // Iterate until we are done.
00082   
00083   if (DEBUG_LV) std::cerr << "Live Variable Analysis complete!\n";
00084   return false;
00085 }
00086 
00087 
00088 //-----------------------------------------------------------------------------
00089 // constructs BBLiveVars and init Def and In sets
00090 //-----------------------------------------------------------------------------
00091 
00092 void FunctionLiveVarInfo::constructBBs(const Function *F) {
00093   unsigned POId = 0;                // Reverse Depth-first Order ID
00094   std::map<const BasicBlock*, unsigned> PONumbering;
00095 
00096   for (po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
00097       BBI != BBE; ++BBI)
00098     PONumbering[*BBI] = POId++;
00099 
00100   MachineFunction &MF = MachineFunction::get(F);
00101   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
00102     const BasicBlock &BB = *I->getBasicBlock();        // get the current BB 
00103     if (DEBUG_LV) std::cerr << " For BB " << RAV(BB) << ":\n";
00104 
00105     BBLiveVar *LVBB;
00106     std::map<const BasicBlock*, unsigned>::iterator POI = PONumbering.find(&BB);
00107     if (POI != PONumbering.end()) {
00108       // create a new BBLiveVar
00109       LVBB = new BBLiveVar(BB, *I, POId);
00110     } else {
00111       // The PO iterator does not discover unreachable blocks, but the random
00112       // iterator later may access these blocks.  We must make sure to
00113       // initialize unreachable blocks as well.  However, LV info is not correct
00114       // for those blocks (they are not analyzed)
00115       //
00116       LVBB = new BBLiveVar(BB, *I, ++POId);
00117     }
00118     BBLiveVarInfo[&BB] = LVBB;
00119     
00120     if (DEBUG_LV)
00121       LVBB->printAllSets();
00122   }
00123 }
00124 
00125 
00126 //-----------------------------------------------------------------------------
00127 // do one backward pass over the CFG (for iterative analysis)
00128 //-----------------------------------------------------------------------------
00129 
00130 bool FunctionLiveVarInfo::doSingleBackwardPass(const Function *M,
00131                                                unsigned iter) {
00132   if (DEBUG_LV) std::cerr << "\n After Backward Pass " << iter << "...\n";
00133 
00134   bool NeedAnotherIteration = false;
00135   for (po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
00136        BBI != BBE; ++BBI) {
00137     BBLiveVar *LVBB = BBLiveVarInfo[*BBI];
00138     assert(LVBB && "BasicBlock information not set for block!");
00139 
00140     if (DEBUG_LV) std::cerr << " For BB " << (*BBI)->getName() << ":\n";
00141 
00142     // InSets are initialized to "GenSet". Recompute only if OutSet changed.
00143     if(LVBB->isOutSetChanged()) 
00144       LVBB->applyTransferFunc();        // apply the Tran Func to calc InSet
00145     
00146     // OutSets are initialized to EMPTY.  Recompute on first iter or if InSet
00147     // changed.
00148     if (iter == 0 || LVBB->isInSetChanged())        // to calc Outsets of preds
00149       NeedAnotherIteration |= LVBB->applyFlowFunc(BBLiveVarInfo);
00150     
00151     if (DEBUG_LV) LVBB->printInOutSets();
00152   }
00153 
00154   // true if we need to reiterate over the CFG
00155   return NeedAnotherIteration;         
00156 }
00157 
00158 
00159 void FunctionLiveVarInfo::releaseMemory() {
00160   // First remove all BBLiveVars created in constructBBs().
00161   if (M) {
00162     for (Function::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
00163       delete BBLiveVarInfo[I];
00164     BBLiveVarInfo.clear();
00165   }
00166   M = 0;
00167 
00168   // Then delete all objects of type ValueSet created in calcLiveVarSetsForBB
00169   // and entered into MInst2LVSetBI and MInst2LVSetAI (these are caches
00170   // to return ValueSet's before/after a machine instruction quickly).
00171   // We do not need to free up ValueSets in MInst2LVSetAI because it holds
00172   // pointers to the same sets as in MInst2LVSetBI (for all instructions
00173   // except the last one in a BB) or in BBLiveVar (for the last instruction).
00174   //
00175   for (hash_map<const MachineInstr*, ValueSet*>::iterator
00176          MI = MInst2LVSetBI.begin(),
00177          ME = MInst2LVSetBI.end(); MI != ME; ++MI)
00178     delete MI->second;           // delete all ValueSets in  MInst2LVSetBI
00179 
00180   MInst2LVSetBI.clear();
00181   MInst2LVSetAI.clear();
00182 }
00183 
00184 
00185 
00186 
00187 //-----------------------------------------------------------------------------
00188 // Following functions will give the LiveVar info for any machine instr in
00189 // a function. It should be called after a call to analyze().
00190 //
00191 // These functions calculate live var info for all the machine instrs in a 
00192 // BB when LVInfo for one inst is requested. Hence, this function is useful 
00193 // when live var info is required for many (or all) instructions in a basic 
00194 // block. Also, the arguments to this function does not require specific 
00195 // iterators.
00196 //-----------------------------------------------------------------------------
00197 
00198 //-----------------------------------------------------------------------------
00199 // Gives live variable information before a machine instruction
00200 //-----------------------------------------------------------------------------
00201 
00202 const ValueSet &
00203 FunctionLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *MI,
00204                                               const BasicBlock *BB) {
00205   ValueSet* &LVSet = MInst2LVSetBI[MI]; // ref. to map entry
00206   if (LVSet == NULL && BB != NULL) {    // if not found and BB provided
00207     calcLiveVarSetsForBB(BB);           // calc LVSet for all instrs in BB
00208     assert(LVSet != NULL);
00209   }
00210   return *LVSet;
00211 }
00212 
00213 
00214 //-----------------------------------------------------------------------------
00215 // Gives live variable information after a machine instruction
00216 //-----------------------------------------------------------------------------
00217 
00218 const ValueSet & 
00219 FunctionLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *MI,
00220                                              const BasicBlock *BB) {
00221 
00222   ValueSet* &LVSet = MInst2LVSetAI[MI]; // ref. to map entry
00223   if (LVSet == NULL && BB != NULL) {    // if not found and BB provided 
00224     calcLiveVarSetsForBB(BB);           // calc LVSet for all instrs in BB
00225     assert(LVSet != NULL);
00226   }
00227   return *LVSet;
00228 }
00229 
00230 // This function applies a machine instr to a live var set (accepts OutSet) and
00231 // makes necessary changes to it (produces InSet). Note that two for loops are
00232 // used to first kill all defs and then to add all uses. This is because there
00233 // can be instructions like Val = Val + 1 since we allow multiple defs to a 
00234 // machine instruction operand.
00235 //
00236 static void applyTranferFuncForMInst(ValueSet &LVS, const MachineInstr *MInst) {
00237   for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
00238          OpE = MInst->end(); OpI != OpE; ++OpI) {
00239     if (OpI.isDef())                          // kill if this operand is a def
00240       LVS.erase(*OpI);                        // this definition kills any uses
00241   }
00242 
00243   // do for implicit operands as well
00244   for (unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
00245     if (MInst->getImplicitOp(i).isDef())
00246       LVS.erase(MInst->getImplicitRef(i));
00247   }
00248 
00249   for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
00250          OpE = MInst->end(); OpI != OpE; ++OpI) {
00251     if (!isa<BasicBlock>(*OpI))      // don't process labels
00252       // add only if this operand is a use
00253       if (OpI.isUse())
00254         LVS.insert(*OpI);            // An operand is a use - so add to use set
00255   }
00256 
00257   // do for implicit operands as well
00258   for (unsigned i = 0, e = MInst->getNumImplicitRefs(); i != e; ++i)
00259     if (MInst->getImplicitOp(i).isUse())
00260       LVS.insert(MInst->getImplicitRef(i));
00261 }
00262 
00263 //-----------------------------------------------------------------------------
00264 // This method calculates the live variable information for all the 
00265 // instructions in a basic block and enter the newly constructed live
00266 // variable sets into a the caches (MInst2LVSetAI, MInst2LVSetBI)
00267 //-----------------------------------------------------------------------------
00268 
00269 void FunctionLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
00270   BBLiveVar *BBLV = BBLiveVarInfo[BB];
00271   assert(BBLV && "BBLiveVar annotation doesn't exist?");
00272   const MachineBasicBlock &MIVec = BBLV->getMachineBasicBlock();
00273   const MachineFunction &MF = MachineFunction::get(M);
00274   const TargetMachine &TM = MF.getTarget();
00275 
00276   if (DEBUG_LV >= LV_DEBUG_Instr)
00277     std::cerr << "\n======For BB " << BB->getName()
00278               << ": Live var sets for instructions======\n";
00279   
00280   ValueSet *SetAI = &getOutSetOfBB(BB);         // init SetAI with OutSet
00281   ValueSet CurSet(*SetAI);                      // CurSet now contains OutSet
00282 
00283   // iterate over all the machine instructions in BB
00284   for (MachineBasicBlock::const_reverse_iterator MII = MIVec.rbegin(),
00285          MIE = MIVec.rend(); MII != MIE; ++MII) {  
00286     // MI is cur machine inst
00287     const MachineInstr *MI = &*MII;  
00288 
00289     MInst2LVSetAI[MI] = SetAI;                 // record in After Inst map
00290 
00291     applyTranferFuncForMInst(CurSet, MI);      // apply the transfer Func
00292     ValueSet *NewSet = new ValueSet(CurSet);   // create a new set with a copy
00293                                                // of the set after T/F
00294     MInst2LVSetBI[MI] = NewSet;                // record in Before Inst map
00295 
00296     // If the current machine instruction has delay slots, mark values
00297     // used by this instruction as live before and after each delay slot
00298     // instruction (After(MI) is the same as Before(MI+1) except for last MI).
00299     if (unsigned DS = TM.getInstrInfo()->getNumDelaySlots(MI->getOpcode())) {
00300       MachineBasicBlock::const_iterator fwdMII = MII.base(); // ptr to *next* MI
00301       for (unsigned i = 0; i < DS; ++i, ++fwdMII) {
00302         assert(fwdMII != MIVec.end() && "Missing instruction in delay slot?");
00303         const MachineInstr* DelaySlotMI = fwdMII;
00304         if (! TM.getInstrInfo()->isNop(DelaySlotMI->getOpcode())) {
00305           set_union(*MInst2LVSetBI[DelaySlotMI], *NewSet);
00306           if (i+1 == DS)
00307             set_union(*MInst2LVSetAI[DelaySlotMI], *NewSet);
00308         }
00309       }
00310     }
00311 
00312     if (DEBUG_LV >= LV_DEBUG_Instr) {
00313       std::cerr << "\nLive var sets before/after instruction " << *MI;
00314       std::cerr << "  Before: ";   printSet(*NewSet);  std::cerr << "\n";
00315       std::cerr << "  After : ";   printSet(*SetAI);   std::cerr << "\n";
00316     }
00317 
00318     // SetAI will be used in the next iteration
00319     SetAI = NewSet;                 
00320   }
00321 }
00322 
00323 } // End llvm namespace