lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp

   1 //===-- ProfilePaths.cpp - interface to insert instrumentation --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This inserts instrumentation for counting execution of paths though a given
  11 // function Its implemented as a "Function" Pass, and called using opt
  12 //
  13 // This pass is implemented by using algorithms similar to
  14 // 1."Efficient Path Profiling": Ball, T. and Larus, J. R.,
  15 //    Proceedings of Micro-29, Dec 1996, Paris, France.
  16 // 2."Efficiently Counting Program events with support for on-line
  17 //   "queries": Ball T., ACM Transactions on Programming Languages
  18 //    and systems, Sep 1994.
  19 //
  20 // The algorithms work on a Graph constructed over the nodes made from Basic
  21 // Blocks: The transformations then take place on the constructed graph
  22 // (implementation in Graph.cpp and GraphAuxiliary.cpp) and finally, appropriate
  23 // instrumentation is placed over suitable edges.  (code inserted through
  24 // EdgeCode.cpp).
  25 //
  26 // The algorithm inserts code such that every acyclic path in the CFG of a
  27 // function is identified through a unique number. the code insertion is optimal
  28 // in the sense that its inserted over a minimal set of edges. Also, the
  29 // algorithm makes sure than initialization, path increment and counter update
  30 // can be collapsed into minimum number of edges.
  31 //
  32 //===----------------------------------------------------------------------===//
  33
  34 #include "llvm/Transforms/Instrumentation.h"
  35 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
  36 #include "llvm/Support/CFG.h"
  37 #include "llvm/Constants.h"
  38 #include "llvm/DerivedTypes.h"
  39 #include "llvm/Instructions.h"
  40 #include "llvm/Module.h"
  41 #include "Graph.h"
  42 #include <fstream>
  43 #include <cstdio>
  44
  45 namespace llvm {
  46
  47 struct ProfilePaths : public FunctionPass {
  48   bool runOnFunction(Function &F);
  49
  50   // Before this pass, make sure that there is only one
  51   // entry and only one exit node for the function in the CFG of the function
  52   //
  53   void getAnalysisUsage(AnalysisUsage &AU) const {
  54     AU.addRequired<UnifyFunctionExitNodes>();
  55   }
  56 };
  57
  58 static RegisterOpt<ProfilePaths> X("paths", "Profile Paths");
  59
  60 FunctionPass *createProfilePathsPass() { return new ProfilePaths(); }
  61
  62 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
  63   for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
  64     if(((*si)->getElement())==BB){
  65       return *si;
  66     }
  67   }
  68   return NULL;
  69 }
  70
  71 //Per function pass for inserting counters and trigger code
  72 bool ProfilePaths::runOnFunction(Function &F){
  73
  74   static int mn = -1;
  75   static int CountCounter = 1;
  76   if(F.isExternal()) {
  77     return false;
  78   }
  79
  80   //increment counter for instrumented functions. mn is now function#
  81   mn++;
  82
  83   // Transform the cfg s.t. we have just one exit node
  84   BasicBlock *ExitNode =
  85     getAnalysis<UnifyFunctionExitNodes>().getReturnBlock();
  86
  87   //iterating over BBs and making graph
  88   std::vector<Node *> nodes;
  89   std::vector<Edge> edges;
  90
  91   Node *exitNode = 0, *startNode = 0;
  92
  93   // The nodes must be uniquely identified:
  94   // That is, no two nodes must hav same BB*
  95
  96   for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) {
  97     Node *nd=new Node(BB);
  98     nodes.push_back(nd);
  99     if(&*BB == ExitNode)
 100       exitNode=nd;
 101     if(BB==F.begin())
 102       startNode=nd;
 103   }
 104
 105   // now do it again to insert edges
 106   for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB){
 107     Node *nd=findBB(nodes, BB);
 108     assert(nd && "No node for this edge!");
 109
 110     for(succ_iterator s=succ_begin(BB), se=succ_end(BB); s!=se; ++s){
 111       Node *nd2=findBB(nodes,*s);
 112       assert(nd2 && "No node for this edge!");
 113       Edge ed(nd,nd2,0);
 114       edges.push_back(ed);
 115     }
 116   }
 117
 118   Graph g(nodes,edges, startNode, exitNode);
 119
 120 #ifdef DEBUG_PATH_PROFILES
 121   std::cerr<<"Original graph\n";
 122   printGraph(g);
 123 #endif
 124
 125   BasicBlock *fr = &F.front();
 126
 127   // The graph is made acyclic: this is done
 128   // by removing back edges for now, and adding them later on
 129   std::vector<Edge> be;
 130   std::map<Node *, int> nodePriority; //it ranks nodes in depth first order traversal
 131   g.getBackEdges(be, nodePriority);
 132
 133 #ifdef DEBUG_PATH_PROFILES
 134   std::cerr<<"BackEdges-------------\n";
 135   for (std::vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
 136     printEdge(*VI);
 137     cerr<<"\n";
 138   }
 139   std::cerr<<"------\n";
 140 #endif
 141
 142 #ifdef DEBUG_PATH_PROFILES
 143   cerr<<"Backedges:"<<be.size()<<endl;
 144 #endif
 145   //Now we need to reflect the effect of back edges
 146   //This is done by adding dummy edges
 147   //If a->b is a back edge
 148   //Then we add 2 back edges for it:
 149   //1. from root->b (in vector stDummy)
 150   //and 2. from a->exit (in vector exDummy)
 151   std::vector<Edge> stDummy;
 152   std::vector<Edge> exDummy;
 153   addDummyEdges(stDummy, exDummy, g, be);
 154
 155 #ifdef DEBUG_PATH_PROFILES
 156   std::cerr<<"After adding dummy edges\n";
 157   printGraph(g);
 158 #endif
 159
 160   // Now, every edge in the graph is assigned a weight
 161   // This weight later adds on to assign path
 162   // numbers to different paths in the graph
 163   //  All paths for now are acyclic,
 164   // since no back edges in the graph now
 165   // numPaths is the number of acyclic paths in the graph
 166   int numPaths=valueAssignmentToEdges(g, nodePriority, be);
 167
 168   //if(numPaths<=1) return false;
 169
 170   static GlobalVariable *threshold = NULL;
 171   static bool insertedThreshold = false;
 172
 173   if(!insertedThreshold){
 174     threshold = new GlobalVariable(Type::IntTy, false,
 175                                    GlobalValue::ExternalLinkage, 0,
 176                                    "reopt_threshold");
 177
 178     F.getParent()->getGlobalList().push_back(threshold);
 179     insertedThreshold = true;
 180   }
 181
 182   assert(threshold && "GlobalVariable threshold not defined!");
 183
 184
 185   if(fr->getParent()->getName() == "main"){
 186     //initialize threshold
 187
 188     // FIXME: THIS IS HORRIBLY BROKEN.  FUNCTION PASSES CANNOT DO THIS, EXCEPT
 189     // IN THEIR INITIALIZE METHOD!!
 190     Function *initialize =
 191       F.getParent()->getOrInsertFunction("reoptimizerInitialize", Type::VoidTy,
 192                                          PointerType::get(Type::IntTy), 0);
 193
 194     std::vector<Value *> trargs;
 195     trargs.push_back(threshold);
 196     new CallInst(initialize, trargs, "", fr->begin());
 197   }
 198
 199
 200   if(numPaths<=1 || numPaths >5000) return false;
 201
 202 #ifdef DEBUG_PATH_PROFILES
 203   printGraph(g);
 204 #endif
 205
 206   //create instruction allocation r and count
 207   //r is the variable that'll act like an accumulator
 208   //all along the path, we just add edge values to r
 209   //and at the end, r reflects the path number
 210   //count is an array: count[x] would store
 211   //the number of executions of path numbered x
 212
 213   Instruction *rVar=new
 214     AllocaInst(Type::IntTy,
 215                ConstantUInt::get(Type::UIntTy,1),"R");
 216
 217   //Instruction *countVar=new
 218   //AllocaInst(Type::IntTy,
 219   //           ConstantUInt::get(Type::UIntTy, numPaths), "Count");
 220
 221   //initialize counter array!
 222   std::vector<Constant*> arrayInitialize;
 223   for(int xi=0; xi<numPaths; xi++)
 224     arrayInitialize.push_back(ConstantSInt::get(Type::IntTy, 0));
 225
 226   const ArrayType *ATy = ArrayType::get(Type::IntTy, numPaths);
 227   Constant *initializer =  ConstantArray::get(ATy, arrayInitialize);
 228   char tempChar[20];
 229   sprintf(tempChar, "Count%d", CountCounter);
 230   CountCounter++;
 231   std::string countStr = tempChar;
 232   GlobalVariable *countVar = new GlobalVariable(ATy, false,
 233                                                 GlobalValue::InternalLinkage,
 234                                                 initializer, countStr,
 235                                                 F.getParent());
 236
 237   // insert initialization code in first (entry) BB
 238   // this includes initializing r and count
 239   insertInTopBB(&F.getEntryBlock(), numPaths, rVar, threshold);
 240
 241   //now process the graph: get path numbers,
 242   //get increments along different paths,
 243   //and assign "increments" and "updates" (to r and count)
 244   //"optimally". Finally, insert llvm code along various edges
 245   processGraph(g, rVar, countVar, be, stDummy, exDummy, numPaths, mn,
 246                threshold);
 247
 248   return true;  // Always modifies function
 249 }
 250
 251 } // End llvm namespace