LLVM API Documentation
00001 //===-- InstLoops.cpp -----------------------------------------------------===// 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 first-level instrumentation pass for the Reoptimizer. It 00011 // instrument the back-edges of loops by inserting a basic block 00012 // containing a call to llvm_first_trigger (the first-level trigger function), 00013 // and inserts an initialization call to the main() function. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/Analysis/Dominators.h" 00018 #include "llvm/Support/CFG.h" 00019 #include "llvm/Instructions.h" 00020 #include "llvm/Module.h" 00021 #include "llvm/Pass.h" 00022 #include "llvm/Type.h" 00023 #include "llvm/Support/Debug.h" 00024 #include "../ProfilingUtils.h" 00025 00026 namespace llvm { 00027 00028 //this is used to color vertices 00029 //during DFS 00030 00031 enum Color{ 00032 WHITE, 00033 GREY, 00034 BLACK 00035 }; 00036 00037 namespace { 00038 typedef std::map<BasicBlock *, BasicBlock *> BBMap; 00039 struct InstLoops : public FunctionPass { 00040 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00041 AU.addRequired<DominatorSet>(); 00042 } 00043 private: 00044 Function *inCountMth; 00045 DominatorSet *DS; 00046 void getBackEdgesVisit(BasicBlock *u, 00047 std::map<BasicBlock *, Color > &color, 00048 std::map<BasicBlock *, int > &d, 00049 int &time, BBMap &be); 00050 void removeRedundant(BBMap &be); 00051 void findAndInstrumentBackEdges(Function &F); 00052 public: 00053 bool doInitialization(Module &M); 00054 bool runOnFunction(Function &F); 00055 }; 00056 00057 RegisterOpt<InstLoops> X("instloops", "Instrument backedges for profiling"); 00058 } 00059 00060 //helper function to get back edges: it is called by 00061 //the "getBackEdges" function below 00062 void InstLoops::getBackEdgesVisit(BasicBlock *u, 00063 std::map<BasicBlock *, Color > &color, 00064 std::map<BasicBlock *, int > &d, 00065 int &time, BBMap &be) { 00066 color[u]=GREY; 00067 time++; 00068 d[u]=time; 00069 00070 for(succ_iterator vl = succ_begin(u), ve = succ_end(u); vl != ve; ++vl){ 00071 BasicBlock *BB = *vl; 00072 00073 if(color[BB]!=GREY && color[BB]!=BLACK){ 00074 getBackEdgesVisit(BB, color, d, time, be); 00075 } 00076 00077 //now checking for d and f vals 00078 else if(color[BB]==GREY){ 00079 //so v is ancestor of u if time of u > time of v 00080 if(d[u] >= d[BB]){ 00081 //u->BB is a backedge 00082 be[u] = BB; 00083 } 00084 } 00085 } 00086 color[u]=BLACK;//done with visiting the node and its neighbors 00087 } 00088 00089 //look at all BEs, and remove all BEs that are dominated by other BE's in the 00090 //set 00091 void InstLoops::removeRedundant(BBMap &be) { 00092 std::vector<BasicBlock *> toDelete; 00093 for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(), 00094 ME = be.end(); MI != ME; ++MI) 00095 for(BBMap::iterator MMI = be.begin(), MME = be.end(); MMI != MME; ++MMI) 00096 if(DS->properlyDominates(MI->first, MMI->first)) 00097 toDelete.push_back(MMI->first); 00098 // Remove all the back-edges we found from be. 00099 for(std::vector<BasicBlock *>::iterator VI = toDelete.begin(), 00100 VE = toDelete.end(); VI != VE; ++VI) 00101 be.erase(*VI); 00102 } 00103 00104 //getting the backedges in a graph 00105 //Its a variation of DFS to get the backedges in the graph 00106 //We get back edges by associating a time 00107 //and a color with each vertex. 00108 //The time of a vertex is the time when it was first visited 00109 //The color of a vertex is initially WHITE, 00110 //Changes to GREY when it is first visited, 00111 //and changes to BLACK when ALL its neighbors 00112 //have been visited 00113 //So we have a back edge when we meet a successor of 00114 //a node with smaller time, and GREY color 00115 void InstLoops::findAndInstrumentBackEdges(Function &F){ 00116 std::map<BasicBlock *, Color > color; 00117 std::map<BasicBlock *, int> d; 00118 BBMap be; 00119 int time=0; 00120 getBackEdgesVisit(F.begin(), color, d, time, be); 00121 00122 removeRedundant(be); 00123 00124 for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(), 00125 ME = be.end(); MI != ME; ++MI){ 00126 BasicBlock *u = MI->first; 00127 BasicBlock *BB = MI->second; 00128 // We have a back-edge from BB --> u. 00129 DEBUG (std::cerr << "Instrumenting back-edge from " << BB->getName () 00130 << "-->" << u->getName () << "\n"); 00131 // Split the back-edge, inserting a new basic block on it, and modify the 00132 // source BB's terminator accordingly. 00133 BasicBlock *newBB = new BasicBlock("backEdgeInst", u->getParent()); 00134 BranchInst *ti = cast<BranchInst>(u->getTerminator()); 00135 unsigned char index = ((ti->getSuccessor(0) == BB) ? 0 : 1); 00136 00137 assert(ti->getNumSuccessors() > index && "Not enough successors!"); 00138 ti->setSuccessor(index, newBB); 00139 00140 BasicBlock::InstListType < = newBB->getInstList(); 00141 lt.push_back(new CallInst(inCountMth)); 00142 new BranchInst(BB, newBB); 00143 00144 // Now, set the sources of Phi nodes corresponding to the back-edge 00145 // in BB to come from the instrumentation block instead. 00146 for(BasicBlock::iterator BB2Inst = BB->begin(), BBend = BB->end(); 00147 BB2Inst != BBend; ++BB2Inst) { 00148 if (PHINode *phiInst = dyn_cast<PHINode>(BB2Inst)) { 00149 int bbIndex = phiInst->getBasicBlockIndex(u); 00150 if (bbIndex>=0) 00151 phiInst->setIncomingBlock(bbIndex, newBB); 00152 } 00153 } 00154 } 00155 } 00156 00157 bool InstLoops::doInitialization (Module &M) { 00158 inCountMth = M.getOrInsertFunction("llvm_first_trigger", Type::VoidTy, 0); 00159 return true; // Module was modified. 00160 } 00161 00162 /// runOnFunction - Entry point for FunctionPass that inserts calls to 00163 /// trigger function. 00164 /// 00165 bool InstLoops::runOnFunction(Function &F){ 00166 if (F.isExternal ()) 00167 return false; 00168 00169 DS = &getAnalysis<DominatorSet> (); 00170 00171 // Add a call to reoptimizerInitialize() to beginning of function named main. 00172 if (F.getName() == "main") 00173 InsertProfilingInitCall (&F, "reoptimizerInitialize"); 00174 00175 findAndInstrumentBackEdges(F); 00176 return true; // Function was modified. 00177 } 00178 00179 FunctionPass *createLoopInstrumentationPass () { 00180 return new InstLoops(); 00181 } 00182 00183 } // End llvm namespace