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/Utils/UnifyFunctionExitNodes.h"
  28 #include "llvm/Support/CFG.h"
  29 #include "llvm/Constants.h"
  30 #include "llvm/DerivedTypes.h"
  31 #include "llvm/iMemory.h"
  32 #include "llvm/iOperators.h"
  33 #include "llvm/iOther.h"
  34 #include "llvm/Module.h"
  35 #include "Graph.h"
  36 #include <fstream>
  37 #include "Config/stdio.h"
  38
  39 struct ProfilePaths : public FunctionPass {
  40   bool runOnFunction(Function &F);
  41
  42   // Before this pass, make sure that there is only one
  43   // entry and only one exit node for the function in the CFG of the function
  44   //
  45   void ProfilePaths::getAnalysisUsage(AnalysisUsage &AU) const {
  46     AU.addRequired<UnifyFunctionExitNodes>();
  47   }
  48 };
  49
  50 static RegisterOpt<ProfilePaths> X("paths", "Profile Paths");
  51
  52 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
  53   for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
  54     if(((*si)->getElement())==BB){
  55       return *si;
  56     }
  57   }
  58   return NULL;
  59 }
  60
  61 //Per function pass for inserting counters and trigger code
  62 bool ProfilePaths::runOnFunction(Function &F){
  63
  64   static int mn = -1;
  65   static int CountCounter = 1;
  66   if(F.isExternal()) {
  67     return false;
  68   }
  69
  70   //increment counter for instrumented functions. mn is now function#
  71   mn++;
  72
  73   // Transform the cfg s.t. we have just one exit node
  74   BasicBlock *ExitNode =
  75     getAnalysis<UnifyFunctionExitNodes>().getReturnBlock();
  76
  77   //iterating over BBs and making graph
  78   std::vector<Node *> nodes;
  79   std::vector<Edge> edges;
  80
  81   Node *tmp;
  82   Node *exitNode = 0, *startNode = 0;
  83
  84   // The nodes must be uniquesly identified:
  85   // That is, no two nodes must hav same BB*
  86
  87   for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) {
  88     Node *nd=new Node(BB);
  89     nodes.push_back(nd);
  90     if(&*BB == ExitNode)
  91       exitNode=nd;
  92     if(BB==F.begin())
  93       startNode=nd;
  94   }
  95
  96   // now do it againto insert edges
  97   for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB){
  98     Node *nd=findBB(nodes, BB);
  99     assert(nd && "No node for this edge!");
 100
 101     for(BasicBlock::succ_iterator s=succ_begin(BB), se=succ_end(BB);
 102         s!=se; ++s){
 103       Node *nd2=findBB(nodes,*s);
 104       assert(nd2 && "No node for this edge!");
 105       Edge ed(nd,nd2,0);
 106       edges.push_back(ed);
 107     }
 108   }
 109
 110   Graph g(nodes,edges, startNode, exitNode);
 111
 112 #ifdef DEBUG_PATH_PROFILES
 113   std::cerr<<"Original graph\n";
 114   printGraph(g);
 115 #endif
 116
 117   BasicBlock *fr = &F.front();
 118
 119   // The graph is made acyclic: this is done
 120   // by removing back edges for now, and adding them later on
 121   std::vector<Edge> be;
 122   std::map<Node *, int> nodePriority; //it ranks nodes in depth first order traversal
 123   g.getBackEdges(be, nodePriority);
 124
 125 #ifdef DEBUG_PATH_PROFILES
 126   std::cerr<<"BackEdges-------------\n";
 127   for (std::vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
 128     printEdge(*VI);
 129     cerr<<"\n";
 130   }
 131   std::cerr<<"------\n";
 132 #endif
 133
 134 #ifdef DEBUG_PATH_PROFILES
 135   cerr<<"Backedges:"<<be.size()<<endl;
 136 #endif
 137   //Now we need to reflect the effect of back edges
 138   //This is done by adding dummy edges
 139   //If a->b is a back edge
 140   //Then we add 2 back edges for it:
 141   //1. from root->b (in vector stDummy)
 142   //and 2. from a->exit (in vector exDummy)
 143   std::vector<Edge> stDummy;
 144   std::vector<Edge> exDummy;
 145   addDummyEdges(stDummy, exDummy, g, be);
 146
 147 #ifdef DEBUG_PATH_PROFILES
 148   std::cerr<<"After adding dummy edges\n";
 149   printGraph(g);
 150 #endif
 151
 152   // Now, every edge in the graph is assigned a weight
 153   // This weight later adds on to assign path
 154   // numbers to different paths in the graph
 155   //  All paths for now are acyclic,
 156   // since no back edges in the graph now
 157   // numPaths is the number of acyclic paths in the graph
 158   int numPaths=valueAssignmentToEdges(g, nodePriority, be);
 159
 160   //if(numPaths<=1) return false;
 161
 162   static GlobalVariable *threshold = NULL;
 163   static bool insertedThreshold = false;
 164
 165   if(!insertedThreshold){
 166     threshold = new GlobalVariable(Type::IntTy, false,
 167                                    GlobalValue::ExternalLinkage, 0,
 168                                    "reopt_threshold");
 169
 170     F.getParent()->getGlobalList().push_back(threshold);
 171     insertedThreshold = true;
 172   }
 173
 174   assert(threshold && "GlobalVariable threshold not defined!");
 175
 176
 177   if(fr->getParent()->getName() == "main"){
 178     //intialize threshold
 179
 180     // FIXME: THIS IS HORRIBLY BROKEN.  FUNCTION PASSES CANNOT DO THIS, EXCEPT
 181     // IN THEIR INITIALIZE METHOD!!
 182     Function *initialize =
 183       F.getParent()->getOrInsertFunction("reoptimizerInitialize", Type::VoidTy,
 184                                          PointerType::get(Type::IntTy), 0);
 185
 186     std::vector<Value *> trargs;
 187     trargs.push_back(threshold);
 188     new CallInst(initialize, trargs, "", fr->begin());
 189   }
 190
 191
 192   if(numPaths<=1 || numPaths >5000) return false;
 193
 194 #ifdef DEBUG_PATH_PROFILES
 195   printGraph(g);
 196 #endif
 197
 198   //create instruction allocation r and count
 199   //r is the variable that'll act like an accumulator
 200   //all along the path, we just add edge values to r
 201   //and at the end, r reflects the path number
 202   //count is an array: count[x] would store
 203   //the number of executions of path numbered x
 204
 205   Instruction *rVar=new
 206     AllocaInst(Type::IntTy,
 207                ConstantUInt::get(Type::UIntTy,1),"R");
 208
 209   //Instruction *countVar=new
 210   //AllocaInst(Type::IntTy,
 211   //           ConstantUInt::get(Type::UIntTy, numPaths), "Count");
 212
 213   //initialize counter array!
 214   std::vector<Constant*> arrayInitialize;
 215   for(int xi=0; xi<numPaths; xi++)
 216     arrayInitialize.push_back(ConstantSInt::get(Type::IntTy, 0));
 217
 218   const ArrayType *ATy = ArrayType::get(Type::IntTy, numPaths);
 219   Constant *initializer =  ConstantArray::get(ATy, arrayInitialize);
 220   char tempChar[20];
 221   sprintf(tempChar, "Count%d", CountCounter);
 222   CountCounter++;
 223   std::string countStr = tempChar;
 224   GlobalVariable *countVar = new GlobalVariable(ATy, false,
 225                                                 GlobalValue::InternalLinkage,
 226                                                 initializer, countStr,
 227                                                 F.getParent());
 228
 229   // insert initialization code in first (entry) BB
 230   // this includes initializing r and count
 231   insertInTopBB(&F.getEntryBlock(), numPaths, rVar, threshold);
 232
 233   //now process the graph: get path numbers,
 234   //get increments along different paths,
 235   //and assign "increments" and "updates" (to r and count)
 236   //"optimally". Finally, insert llvm code along various edges
 237   processGraph(g, rVar, countVar, be, stDummy, exDummy, numPaths, mn,
 238                threshold);
 239
 240   return true;  // Always modifies function
 241 }