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/Support/CFG.h"
  30 #include "llvm/Constants.h"
  31 #include "llvm/DerivedTypes.h"
  32 #include "llvm/iMemory.h"
  33 #include "llvm/Transforms/Instrumentation/Graph.h"
  34 #include <iostream>
  35 #include <fstream>
  36
  37 using std::vector;
  38
  39 struct ProfilePaths : public FunctionPass {
  40   const char *getPassName() const { return "ProfilePaths"; }
  41
  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::ID);
  49   }
  50 };
  51
  52 // createProfilePathsPass - Create a new pass to add path profiling
  53 //
  54 Pass *createProfilePathsPass() {
  55   return new ProfilePaths();
  56 }
  57
  58
  59 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
  60   for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
  61     if(((*si)->getElement())==BB){
  62       return *si;
  63     }
  64   }
  65   return NULL;
  66 }
  67
  68 //Per function pass for inserting counters and trigger code
  69 bool ProfilePaths::runOnFunction(Function &F){
  70
  71   static int mn = -1;
  72   // Transform the cfg s.t. we have just one exit node
  73   BasicBlock *ExitNode = getAnalysis<UnifyFunctionExitNodes>().getExitNode();
  74
  75   //iterating over BBs and making graph
  76   std::vector<Node *> nodes;
  77   std::vector<Edge> edges;
  78
  79   Node *tmp;
  80   Node *exitNode, *startNode;
  81
  82   // The nodes must be uniquesly identified:
  83   // That is, no two nodes must hav same BB*
  84
  85   // First enter just nodes: later enter edges
  86   //<<<<<<< ProfilePaths.cpp
  87   //for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
  88   //Node *nd=new Node(*BB);
  89   //nodes.push_back(nd);
  90   //if(*BB==ExitNode)
  91   //=======
  92   for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) {
  93     Node *nd=new Node(BB);
  94     nodes.push_back(nd);
  95     if(&*BB == ExitNode)
  96       //>>>>>>> 1.13
  97       exitNode=nd;
  98     if(&*BB==F.begin())
  99       startNode=nd;
 100   }
 101
 102   // now do it againto insert edges
 103   for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB){
 104     Node *nd=findBB(nodes, BB);
 105     assert(nd && "No node for this edge!");
 106
 107     for(BasicBlock::succ_iterator s=succ_begin(BB), se=succ_end(BB);
 108         s!=se; ++s){
 109       //tempVec.push_back(*s);
 110       //}
 111
 112     //sort(tempVec.begin(), tempVec.end(), BBSort());
 113
 114     //for(vector<BasicBlock *>::iterator s=tempVec.begin(), se=tempVec.end();
 115       //s!=se; ++s){
 116       Node *nd2=findBB(nodes,*s);
 117       assert(nd2 && "No node for this edge!");
 118       Edge ed(nd,nd2,0);
 119       edges.push_back(ed);
 120     }
 121   }
 122
 123   Graph g(nodes,edges, startNode, exitNode);
 124
 125   //#ifdef DEBUG_PATH_PROFILES
 126   //std::cerr<<"Original graph\n";
 127   //printGraph(g);
 128   //#endif
 129
 130   BasicBlock *fr=&F.front();
 131
 132   // If only one BB, don't instrument
 133   if (++F.begin() == F.end()) {
 134     mn++;
 135     // The graph is made acyclic: this is done
 136     // by removing back edges for now, and adding them later on
 137     vector<Edge> be;
 138     g.getBackEdges(be);
 139
 140     //std::cerr<<"BackEdges-------------\n";
 141     //   for(vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
 142     //printEdge(*VI);
 143       //cerr<<"\n";
 144     //}
 145     //std::cerr<<"------\n";
 146
 147 #ifdef DEBUG_PATH_PROFILES
 148     cerr<<"Backedges:"<<be.size()<<endl;
 149 #endif
 150     //Now we need to reflect the effect of back edges
 151     //This is done by adding dummy edges
 152     //If a->b is a back edge
 153     //Then we add 2 back edges for it:
 154     //1. from root->b (in vector stDummy)
 155     //and 2. from a->exit (in vector exDummy)
 156     vector<Edge> stDummy;
 157     vector<Edge> exDummy;
 158     addDummyEdges(stDummy, exDummy, g, be);
 159
 160     //std::cerr<<"After adding dummy edges\n";
 161     //printGraph(g);
 162
 163     // Now, every edge in the graph is assigned a weight
 164     // This weight later adds on to assign path
 165     // numbers to different paths in the graph
 166     //  All paths for now are acyclic,
 167     // since no back edges in the graph now
 168     // numPaths is the number of acyclic paths in the graph
 169     int numPaths=valueAssignmentToEdges(g);
 170
 171     //std::cerr<<"Numpaths="<<numPaths<<std::endl;
 172     //printGraph(g);
 173     //create instruction allocation r and count
 174     //r is the variable that'll act like an accumulator
 175     //all along the path, we just add edge values to r
 176     //and at the end, r reflects the path number
 177     //count is an array: count[x] would store
 178     //the number of executions of path numbered x
 179
 180     Instruction *rVar=new
 181       AllocaInst(PointerType::get(Type::IntTy),
 182                  ConstantUInt::get(Type::UIntTy,1),"R");
 183
 184     Instruction *countVar=new
 185       AllocaInst(PointerType::get(Type::IntTy),
 186                  ConstantUInt::get(Type::UIntTy, numPaths), "Count");
 187
 188     // insert initialization code in first (entry) BB
 189     // this includes initializing r and count
 190     insertInTopBB(&F.getEntryNode(),numPaths, rVar, countVar);
 191
 192     //now process the graph: get path numbers,
 193     //get increments along different paths,
 194     //and assign "increments" and "updates" (to r and count)
 195     //"optimally". Finally, insert llvm code along various edges
 196     processGraph(g, rVar, countVar, be, stDummy, exDummy, numPaths);
 197     /*
 198     //get the paths
 199     static std::ofstream to("paths.sizes");
 200     static std::ofstream bbs("paths.look");
 201     assert(to && "Cannot open file\n");
 202     assert(bbs && "Cannot open file\n");
 203     for(int i=0;i<numPaths; ++i){
 204     std::vector<BasicBlock *> vBB;
 205
 206     getBBtrace(vBB, i, M);
 207     //get total size of vector
 208     int size=0;
 209     bbs<<"Meth:"<<mn<<" Path:"<<i<<"\n-------------\n";
 210     for(vector<BasicBlock *>::iterator VBI=vBB.begin(); VBI!=vBB.end();
 211     ++VBI){
 212     BasicBlock *BB=*VBI;
 213     size+=BB->size();
 214     if(BB==M->front())
 215     size-=numPaths;
 216     bbs<<BB->getName()<<"->";
 217     }
 218     bbs<<"\n--------------\n";
 219     to<<"::::: "<<mn<<" "<<i<<" "<<size<<"\n";
 220     }
 221     */
 222   }
 223
 224   return true;  // Always modifies function
 225 }