lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp

   1 //===-- ProfilePaths.cpp - interface to insert instrumentation ---*- C++ -*--=//
   2 //
   3 // This inserts intrumentation for counting
   4 // execution of paths though a given function
   5 // Its implemented as a "Function" Pass, and called using opt
   6 //
   7 // This pass is implemented by using algorithms similar to
   8 // 1."Efficient Path Profiling": Ball, T. and Larus, J. R.,
   9 // Proceedings of Micro-29, Dec 1996, Paris, France.
  10 // 2."Efficiently Counting Program events with support for on-line
  11 //   "queries": Ball T., ACM Transactions on Programming Languages
  12 //   and systems, Sep 1994.
  13 //
  14 // The algorithms work on a Graph constructed over the nodes
  15 // made from Basic Blocks: The transformations then take place on
  16 // the constucted graph (implementation in Graph.cpp and GraphAuxillary.cpp)
  17 // and finally, appropriate instrumentation is placed over suitable edges.
  18 // (code inserted through EdgeCode.cpp).
  19 //
  20 // The algorithm inserts code such that every acyclic path in the CFG
  21 // of a function is identified through a unique number. the code insertion
  22 // is optimal in the sense that its inserted over a minimal set of edges. Also,
  23 // the algorithm makes sure than initialization, path increment and counter
  24 // update can be collapsed into minimum number of edges.
  25 //===----------------------------------------------------------------------===//
  26
  27 #include "llvm/Transforms/Instrumentation/ProfilePaths.h"
  28 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
  29 #include "llvm/Transforms/Instrumentation/Graph.h"
  30 #include "llvm/Support/CFG.h"
  31 #include "llvm/Constants.h"
  32 #include "llvm/DerivedTypes.h"
  33 #include "llvm/iMemory.h"
  34 #include "llvm/GlobalVariable.h"
  35 #include "llvm/Module.h"
  36 #include <iostream>
  37 #include <fstream>
  38
  39 using std::vector;
  40
  41 struct ProfilePaths : public FunctionPass {
  42   bool runOnFunction(Function &F);
  43
  44   // Before this pass, make sure that there is only one
  45   // entry and only one exit node for the function in the CFG of the function
  46   //
  47   void ProfilePaths::getAnalysisUsage(AnalysisUsage &AU) const {
  48     AU.addRequired<UnifyFunctionExitNodes>();
  49   }
  50 };
  51
  52 static RegisterOpt<ProfilePaths> X("paths", "Profile Paths");
  53
  54 // createProfilePathsPass - Create a new pass to add path profiling
  55 //
  56 Pass *createProfilePathsPass() {
  57   return new ProfilePaths();
  58 }
  59
  60
  61 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
  62   for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
  63     if(((*si)->getElement())==BB){
  64       return *si;
  65     }
  66   }
  67   return NULL;
  68 }
  69
  70 //Per function pass for inserting counters and trigger code
  71 bool ProfilePaths::runOnFunction(Function &F){
  72
  73   static int mn = -1;
  74
  75   if(F.isExternal()) {
  76     return false;
  77   }
  78
  79   //increment counter for instrumented functions. mn is now function#
  80   mn++;
  81
  82   // Transform the cfg s.t. we have just one exit node
  83   BasicBlock *ExitNode = getAnalysis<UnifyFunctionExitNodes>().getExitNode();
  84
  85   //iterating over BBs and making graph
  86   std::vector<Node *> nodes;
  87   std::vector<Edge> edges;
  88
  89   Node *tmp;
  90   Node *exitNode, *startNode;
  91
  92   // The nodes must be uniquesly identified:
  93   // That is, no two nodes must hav same BB*
  94
  95   for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) {
  96     Node *nd=new Node(BB);
  97     nodes.push_back(nd);
  98     if(&*BB == ExitNode)
  99       exitNode=nd;
 100     if(&*BB==F.begin())
 101       startNode=nd;
 102   }
 103
 104   // now do it againto insert edges
 105   for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB){
 106     Node *nd=findBB(nodes, BB);
 107     assert(nd && "No node for this edge!");
 108
 109     for(BasicBlock::succ_iterator s=succ_begin(BB), se=succ_end(BB);
 110         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   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(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   vector<Edge> stDummy;
 152   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 || numPaths >5000) return false;
 169
 170 #ifdef DEBUG_PATH_PROFILES
 171   printGraph(g);
 172 #endif
 173
 174   //create instruction allocation r and count
 175   //r is the variable that'll act like an accumulator
 176   //all along the path, we just add edge values to r
 177   //and at the end, r reflects the path number
 178   //count is an array: count[x] would store
 179   //the number of executions of path numbered x
 180
 181   Instruction *rVar=new
 182     AllocaInst(Type::IntTy,
 183                ConstantUInt::get(Type::UIntTy,1),"R");
 184
 185   Instruction *countVar=new
 186     AllocaInst(Type::IntTy,
 187                ConstantUInt::get(Type::UIntTy, numPaths), "Count");
 188
 189   static GlobalVariable *threshold = NULL;
 190   static bool insertedThreshold = false;
 191
 192   if(!insertedThreshold){
 193     threshold = new GlobalVariable(Type::IntTy, false, true, 0,
 194                                                    "reopt_threshold");
 195
 196     F.getParent()->getGlobalList().push_back(threshold);
 197     insertedThreshold = true;
 198   }
 199
 200   assert(threshold && "GlobalVariable threshold not defined!");
 201
 202   // insert initialization code in first (entry) BB
 203   // this includes initializing r and count
 204   insertInTopBB(&F.getEntryNode(),numPaths, rVar, countVar, threshold);
 205
 206   //now process the graph: get path numbers,
 207   //get increments along different paths,
 208   //and assign "increments" and "updates" (to r and count)
 209   //"optimally". Finally, insert llvm code along various edges
 210   processGraph(g, rVar, countVar, be, stDummy, exDummy, numPaths, mn,
 211                threshold);
 212
 213   return true;  // Always modifies function
 214 }