LLVM API Documentation
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