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 method
   5 // Its implemented as a "Method" 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 method 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 minmimum number of edges.
  25 //===----------------------------------------------------------------------===//
  26
  27 #include "llvm/Transforms/Instrumentation/ProfilePaths.h"
  28 #include "llvm/Transforms/UnifyMethodExitNodes.h"
  29 #include "llvm/Support/CFG.h"
  30 #include "llvm/Method.h"
  31 #include "llvm/BasicBlock.h"
  32 #include "llvm/ConstantVals.h"
  33 #include "llvm/DerivedTypes.h"
  34 #include "llvm/iMemory.h"
  35 #include "Graph.h"
  36
  37 using std::vector;
  38
  39 static Node *findBB(std::set<Node *> &st, BasicBlock *BB){
  40   for(std::set<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
  41     if(((*si)->getElement())==BB){
  42       return *si;
  43     }
  44   }
  45   return NULL;
  46 }
  47
  48 //Per method pass for inserting counters and trigger code
  49 bool ProfilePaths::runOnMethod(Method *M){
  50   //Transform the cfg s.t. we have just one exit node
  51   BasicBlock *ExitNode =
  52     getAnalysis<UnifyMethodExitNodes>().getExitNode();
  53
  54   //iterating over BBs and making graph
  55   std::set<Node *> nodes;
  56   std::set<Edge> edges;
  57   Node *tmp;
  58   Node *exitNode, *startNode;
  59
  60   //The nodes must be uniquesly identified:
  61   //That is, no two nodes must hav same BB*
  62
  63   //First enter just nodes: later enter edges
  64   for (Method::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
  65     Node *nd=new Node(*BB);
  66     nodes.insert(nd);
  67     if(*BB==ExitNode)
  68       exitNode=nd;
  69     if(*BB==M->front())
  70       startNode=nd;
  71   }
  72
  73   //now do it againto insert edges
  74   for (Method::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
  75     Node *nd=findBB(nodes, *BB);
  76     assert(nd && "No node for this edge!");
  77     for(BasicBlock::succ_iterator s=succ_begin(*BB), se=succ_end(*BB);
  78         s!=se; ++s){
  79       Node *nd2=findBB(nodes,*s);
  80       assert(nd2 && "No node for this edge!");
  81       Edge ed(nd,nd2,0);
  82       edges.insert(ed);
  83     }
  84   }
  85
  86   Graph g(nodes,edges, startNode, exitNode);
  87
  88 #ifdef DEBUG_PATH_PROFILES
  89   printGraph(g);
  90 #endif
  91
  92   BasicBlock *fr=M->front();
  93
  94   //If only one BB, don't instrument
  95   if (M->getBasicBlocks().size() == 1) {
  96     //The graph is made acyclic: this is done
  97     //by removing back edges for now, and adding them later on
  98     vector<Edge> be;
  99     g.getBackEdges(be);
 100 #ifdef DEBUG_PATH_PROFILES
 101     cerr<<"Backedges:"<<be.size()<<endl;
 102 #endif
 103     //Now we need to reflect the effect of back edges
 104     //This is done by adding dummy edges
 105     //If a->b is a back edge
 106     //Then we add 2 back edges for it:
 107     //1. from root->b (in vector stDummy)
 108     //and 2. from a->exit (in vector exDummy)
 109     vector<Edge> stDummy;
 110     vector<Edge> exDummy;
 111     addDummyEdges(stDummy, exDummy, g, be);
 112
 113     //Now, every edge in the graph is assigned a weight
 114     //This weight later adds on to assign path
 115     //numbers to different paths in the graph
 116     // All paths for now are acyclic,
 117     //since no back edges in the graph now
 118     //numPaths is the number of acyclic paths in the graph
 119     int numPaths=valueAssignmentToEdges(g);
 120
 121     //create instruction allocation r and count
 122     //r is the variable that'll act like an accumulator
 123     //all along the path, we just add edge values to r
 124     //and at the end, r reflects the path number
 125     //count is an array: count[x] would store
 126     //the number of executions of path numbered x
 127     Instruction *rVar=new
 128       AllocaInst(PointerType::get(Type::IntTy),
 129                  ConstantUInt::get(Type::UIntTy,1),"R");
 130
 131     Instruction *countVar=new
 132       AllocaInst(PointerType::get(Type::IntTy),
 133                  ConstantUInt::get(Type::UIntTy, numPaths), "Count");
 134
 135     //insert initialization code in first (entry) BB
 136     //this includes initializing r and count
 137     insertInTopBB(M->getEntryNode(),numPaths, rVar, countVar);
 138
 139     //now process the graph: get path numbers,
 140     //get increments along different paths,
 141     //and assign "increments" and "updates" (to r and count)
 142     //"optimally". Finally, insert llvm code along various edges
 143     processGraph(g, rVar, countVar, be, stDummy, exDummy);
 144   }
 145
 146   return true;  // Always modifies method
 147 }
 148
 149 //Before this pass, make sure that there is only one
 150 //entry and only one exit node for the method in the CFG of the method
 151 void ProfilePaths::getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
 152                                           Pass::AnalysisSet &Destroyed,
 153                                           Pass::AnalysisSet &Provided) {
 154   Requires.push_back(UnifyMethodExitNodes::ID);
 155 }
 156
 157
 158
 159
 160
 161
 162