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