LLVM API Documentation
00001 //===-- ProfilePaths.cpp - interface to insert instrumentation --*- C++ -*-===// 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 inserts instrumentation for counting execution of paths though a given 00011 // function Its implemented as a "Function" Pass, and called using opt 00012 // 00013 // This pass is implemented by using algorithms similar to 00014 // 1."Efficient Path Profiling": Ball, T. and Larus, J. R., 00015 // Proceedings of Micro-29, Dec 1996, Paris, France. 00016 // 2."Efficiently Counting Program events with support for on-line 00017 // "queries": Ball T., ACM Transactions on Programming Languages 00018 // and systems, Sep 1994. 00019 // 00020 // The algorithms work on a Graph constructed over the nodes made from Basic 00021 // Blocks: The transformations then take place on the constructed graph 00022 // (implementation in Graph.cpp and GraphAuxiliary.cpp) and finally, appropriate 00023 // instrumentation is placed over suitable edges. (code inserted through 00024 // EdgeCode.cpp). 00025 // 00026 // The algorithm inserts code such that every acyclic path in the CFG of a 00027 // function is identified through a unique number. the code insertion is optimal 00028 // in the sense that its inserted over a minimal set of edges. Also, the 00029 // algorithm makes sure than initialization, path increment and counter update 00030 // can be collapsed into minimum number of edges. 00031 // 00032 //===----------------------------------------------------------------------===// 00033 00034 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 00035 #include "llvm/Support/CFG.h" 00036 #include "llvm/Constants.h" 00037 #include "llvm/DerivedTypes.h" 00038 #include "llvm/Instructions.h" 00039 #include "llvm/Module.h" 00040 #include "Graph.h" 00041 #include <fstream> 00042 #include <cstdio> 00043 00044 namespace llvm { 00045 00046 struct ProfilePaths : public FunctionPass { 00047 bool runOnFunction(Function &F); 00048 00049 // Before this pass, make sure that there is only one 00050 // entry and only one exit node for the function in the CFG of the function 00051 // 00052 void ProfilePaths::getAnalysisUsage(AnalysisUsage &AU) const { 00053 AU.addRequired<UnifyFunctionExitNodes>(); 00054 } 00055 }; 00056 00057 static RegisterOpt<ProfilePaths> X("paths", "Profile Paths"); 00058 00059 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){ 00060 for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){ 00061 if(((*si)->getElement())==BB){ 00062 return *si; 00063 } 00064 } 00065 return NULL; 00066 } 00067 00068 //Per function pass for inserting counters and trigger code 00069 bool ProfilePaths::runOnFunction(Function &F){ 00070 00071 static int mn = -1; 00072 static int CountCounter = 1; 00073 if(F.isExternal()) { 00074 return false; 00075 } 00076 00077 //increment counter for instrumented functions. mn is now function# 00078 mn++; 00079 00080 // Transform the cfg s.t. we have just one exit node 00081 BasicBlock *ExitNode = 00082 getAnalysis<UnifyFunctionExitNodes>().getReturnBlock(); 00083 00084 //iterating over BBs and making graph 00085 std::vector<Node *> nodes; 00086 std::vector<Edge> edges; 00087 00088 Node *exitNode = 0, *startNode = 0; 00089 00090 // The nodes must be uniquely identified: 00091 // That is, no two nodes must hav same BB* 00092 00093 for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) { 00094 Node *nd=new Node(BB); 00095 nodes.push_back(nd); 00096 if(&*BB == ExitNode) 00097 exitNode=nd; 00098 if(BB==F.begin()) 00099 startNode=nd; 00100 } 00101 00102 // now do it again to insert edges 00103 for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB){ 00104 Node *nd=findBB(nodes, BB); 00105 assert(nd && "No node for this edge!"); 00106 00107 for(succ_iterator s=succ_begin(BB), se=succ_end(BB); s!=se; ++s){ 00108 Node *nd2=findBB(nodes,*s); 00109 assert(nd2 && "No node for this edge!"); 00110 Edge ed(nd,nd2,0); 00111 edges.push_back(ed); 00112 } 00113 } 00114 00115 Graph g(nodes,edges, startNode, exitNode); 00116 00117 #ifdef DEBUG_PATH_PROFILES 00118 std::cerr<<"Original graph\n"; 00119 printGraph(g); 00120 #endif 00121 00122 BasicBlock *fr = &F.front(); 00123 00124 // The graph is made acyclic: this is done 00125 // by removing back edges for now, and adding them later on 00126 std::vector<Edge> be; 00127 std::map<Node *, int> nodePriority; //it ranks nodes in depth first order traversal 00128 g.getBackEdges(be, nodePriority); 00129 00130 #ifdef DEBUG_PATH_PROFILES 00131 std::cerr<<"BackEdges-------------\n"; 00132 for (std::vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){ 00133 printEdge(*VI); 00134 cerr<<"\n"; 00135 } 00136 std::cerr<<"------\n"; 00137 #endif 00138 00139 #ifdef DEBUG_PATH_PROFILES 00140 cerr<<"Backedges:"<<be.size()<<endl; 00141 #endif 00142 //Now we need to reflect the effect of back edges 00143 //This is done by adding dummy edges 00144 //If a->b is a back edge 00145 //Then we add 2 back edges for it: 00146 //1. from root->b (in vector stDummy) 00147 //and 2. from a->exit (in vector exDummy) 00148 std::vector<Edge> stDummy; 00149 std::vector<Edge> exDummy; 00150 addDummyEdges(stDummy, exDummy, g, be); 00151 00152 #ifdef DEBUG_PATH_PROFILES 00153 std::cerr<<"After adding dummy edges\n"; 00154 printGraph(g); 00155 #endif 00156 00157 // Now, every edge in the graph is assigned a weight 00158 // This weight later adds on to assign path 00159 // numbers to different paths in the graph 00160 // All paths for now are acyclic, 00161 // since no back edges in the graph now 00162 // numPaths is the number of acyclic paths in the graph 00163 int numPaths=valueAssignmentToEdges(g, nodePriority, be); 00164 00165 //if(numPaths<=1) return false; 00166 00167 static GlobalVariable *threshold = NULL; 00168 static bool insertedThreshold = false; 00169 00170 if(!insertedThreshold){ 00171 threshold = new GlobalVariable(Type::IntTy, false, 00172 GlobalValue::ExternalLinkage, 0, 00173 "reopt_threshold"); 00174 00175 F.getParent()->getGlobalList().push_back(threshold); 00176 insertedThreshold = true; 00177 } 00178 00179 assert(threshold && "GlobalVariable threshold not defined!"); 00180 00181 00182 if(fr->getParent()->getName() == "main"){ 00183 //initialize threshold 00184 00185 // FIXME: THIS IS HORRIBLY BROKEN. FUNCTION PASSES CANNOT DO THIS, EXCEPT 00186 // IN THEIR INITIALIZE METHOD!! 00187 Function *initialize = 00188 F.getParent()->getOrInsertFunction("reoptimizerInitialize", Type::VoidTy, 00189 PointerType::get(Type::IntTy), 0); 00190 00191 std::vector<Value *> trargs; 00192 trargs.push_back(threshold); 00193 new CallInst(initialize, trargs, "", fr->begin()); 00194 } 00195 00196 00197 if(numPaths<=1 || numPaths >5000) return false; 00198 00199 #ifdef DEBUG_PATH_PROFILES 00200 printGraph(g); 00201 #endif 00202 00203 //create instruction allocation r and count 00204 //r is the variable that'll act like an accumulator 00205 //all along the path, we just add edge values to r 00206 //and at the end, r reflects the path number 00207 //count is an array: count[x] would store 00208 //the number of executions of path numbered x 00209 00210 Instruction *rVar=new 00211 AllocaInst(Type::IntTy, 00212 ConstantUInt::get(Type::UIntTy,1),"R"); 00213 00214 //Instruction *countVar=new 00215 //AllocaInst(Type::IntTy, 00216 // ConstantUInt::get(Type::UIntTy, numPaths), "Count"); 00217 00218 //initialize counter array! 00219 std::vector<Constant*> arrayInitialize; 00220 for(int xi=0; xi<numPaths; xi++) 00221 arrayInitialize.push_back(ConstantSInt::get(Type::IntTy, 0)); 00222 00223 const ArrayType *ATy = ArrayType::get(Type::IntTy, numPaths); 00224 Constant *initializer = ConstantArray::get(ATy, arrayInitialize); 00225 char tempChar[20]; 00226 sprintf(tempChar, "Count%d", CountCounter); 00227 CountCounter++; 00228 std::string countStr = tempChar; 00229 GlobalVariable *countVar = new GlobalVariable(ATy, false, 00230 GlobalValue::InternalLinkage, 00231 initializer, countStr, 00232 F.getParent()); 00233 00234 // insert initialization code in first (entry) BB 00235 // this includes initializing r and count 00236 insertInTopBB(&F.getEntryBlock(), numPaths, rVar, threshold); 00237 00238 //now process the graph: get path numbers, 00239 //get increments along different paths, 00240 //and assign "increments" and "updates" (to r and count) 00241 //"optimally". Finally, insert llvm code along various edges 00242 processGraph(g, rVar, countVar, be, stDummy, exDummy, numPaths, mn, 00243 threshold); 00244 00245 return true; // Always modifies function 00246 } 00247 00248 } // End llvm namespace