LLVM API Documentation

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

ProfilePaths.cpp

Go to the documentation of this file.
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