lib/Transforms/Instrumentation/ProfilePaths/RetracePath.cpp

   1 //===- RetracePath.cpp ----------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Retraces a path of BasicBlock, given a path number and a graph!
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Module.h"
  15 #include "llvm/Instructions.h"
  16 #include "llvm/Support/CFG.h"
  17 #include "Graph.h"
  18 #include <iostream>
  19
  20 using std::vector;
  21 using std::map;
  22 using std::cerr;
  23
  24 namespace llvm {
  25
  26 //Routines to get the path trace!
  27
  28 void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph &g,
  29                     vector<Edge> &stDummy, vector<Edge> &exDummy,
  30                     vector<Edge> &be,
  31                     double strand){
  32   Graph::nodeList &nlist = g.getNodeList(n);
  33
  34   //printGraph(g);
  35   //std::cerr<<"Path No: "<<pathNo<<"\n";
  36   int maxCount=-9999999;
  37   bool isStart=false;
  38
  39   if(*n==*g.getRoot())//its root: so first node of path
  40     isStart=true;
  41
  42   double edgeRnd=0;
  43   Node *nextRoot=n;
  44   for(Graph::nodeList::iterator NLI = nlist.begin(), NLE=nlist.end(); NLI!=NLE;
  45       ++NLI){
  46     if(NLI->weight>maxCount && NLI->weight<=pathNo){
  47       maxCount=NLI->weight;
  48       nextRoot=NLI->element;
  49       edgeRnd=NLI->randId;
  50       if(isStart)
  51         strand=NLI->randId;
  52     }
  53   }
  54
  55   if(!isStart)
  56     assert(strand!=-1 && "strand not assigned!");
  57
  58   assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go");
  59   assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit");
  60
  61   vBB.push_back(n->getElement());
  62
  63   if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){
  64
  65     //look for strnd and edgeRnd now:
  66     bool has1=false, has2=false;
  67     //check if exit has it
  68     for(vector<Edge>::iterator VI=exDummy.begin(), VE=exDummy.end(); VI!=VE;
  69         ++VI){
  70       if(VI->getRandId()==edgeRnd){
  71         has2=true;
  72         break;
  73       }
  74     }
  75
  76     //check if start has it
  77     for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE;
  78         ++VI){
  79       if(VI->getRandId()==strand){
  80         has1=true;
  81         break;
  82       }
  83     }
  84
  85     if(has1){
  86       //find backedge with endpoint vBB[1]
  87       for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
  88         assert(vBB.size()>0 && "vector too small");
  89         if( VI->getSecond()->getElement() == vBB[1] ){
  90           //vBB[0]=VI->getFirst()->getElement();
  91           vBB.erase(vBB.begin());
  92           break;
  93         }
  94       }
  95     }
  96
  97     if(has2){
  98       //find backedge with startpoint vBB[vBB.size()-1]
  99       for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
 100         assert(vBB.size()>0 && "vector too small");
 101         if( VI->getFirst()->getElement() == vBB[vBB.size()-1] &&
 102             VI->getSecond()->getElement() == vBB[0]){
 103           //vBB.push_back(VI->getSecond()->getElement());
 104           break;
 105         }
 106       }
 107     }
 108     else
 109       vBB.push_back(nextRoot->getElement());
 110
 111     return;
 112   }
 113
 114   assert(pathNo-maxCount>=0);
 115
 116   return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy,
 117                         exDummy, be, strand);
 118 }
 119
 120
 121 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
 122   for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
 123     if(((*si)->getElement())==BB){
 124       return *si;
 125     }
 126   }
 127   return NULL;
 128 }
 129
 130 void getBBtrace(vector<BasicBlock *> &vBB, int pathNo, Function *M){//,
 131   //                vector<Instruction *> &instToErase){
 132   //step 1: create graph
 133   //Transform the cfg s.t. we have just one exit node
 134
 135   std::vector<Node *> nodes;
 136   std::vector<Edge> edges;
 137   Node *exitNode=0, *startNode=0;
 138
 139   //Creat cfg just once for each function!
 140   static std::map<Function *, Graph *> graphMap;
 141
 142   //get backedges, exit and start edges for the graphs and store them
 143   static std::map<Function *, vector<Edge> > stMap, exMap, beMap;
 144   static std::map<Function *, Value *> pathReg; //path register
 145
 146
 147   if(!graphMap[M]){
 148     BasicBlock *ExitNode = 0;
 149     for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I){
 150       if (isa<ReturnInst>(I->getTerminator())) {
 151         ExitNode = I;
 152         break;
 153       }
 154     }
 155
 156     assert(ExitNode!=0 && "exitnode not found");
 157
 158     //iterating over BBs and making graph
 159     //The nodes must be uniquely identified:
 160     //That is, no two nodes must hav same BB*
 161
 162     //keep a map for trigger basicblocks!
 163     std::map<BasicBlock *, unsigned char> triggerBBs;
 164     //First enter just nodes: later enter edges
 165     for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
 166       bool cont = false;
 167
 168       if(BB->size()==3 || BB->size() ==2){
 169         for(BasicBlock::iterator II = BB->begin(), IE = BB->end();
 170             II != IE; ++II){
 171           if(CallInst *callInst = dyn_cast<CallInst>(II)){
 172             //std::cerr<<*callInst;
 173             Function *calledFunction = callInst->getCalledFunction();
 174             if(calledFunction && calledFunction->getName() == "trigger"){
 175               triggerBBs[BB] = 9;
 176               cont = true;
 177               //std::cerr<<"Found trigger!\n";
 178               break;
 179             }
 180           }
 181         }
 182       }
 183
 184       if(cont)
 185         continue;
 186
 187       // const Instruction *inst = BB->getInstList().begin();
 188       // if(isa<CallInst>(inst)){
 189       // Instruction *ii1 = BB->getInstList().begin();
 190       // CallInst *callInst = dyn_cast<CallInst>(ii1);
 191       // if(callInst->getCalledFunction()->getName()=="trigger")
 192       // continue;
 193       // }
 194
 195       Node *nd=new Node(BB);
 196       nodes.push_back(nd);
 197       if(&*BB==ExitNode)
 198         exitNode=nd;
 199       if(&*BB==&M->front())
 200         startNode=nd;
 201     }
 202
 203     assert(exitNode!=0 && startNode!=0 && "Start or exit not found!");
 204
 205     for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
 206       if(triggerBBs[BB] == 9)
 207         continue;
 208
 209       //if(BB->size()==3)
 210       //if(CallInst *callInst = dyn_cast<CallInst>(BB->getInstList().begin()))
 211       //if(callInst->getCalledFunction()->getName() == "trigger")
 212       //continue;
 213
 214       // if(BB->size()==2){
 215       //         const Instruction *inst = BB->getInstList().begin();
 216       //         if(isa<CallInst>(inst)){
 217       //           Instruction *ii1 = BB->getInstList().begin();
 218       //           CallInst *callInst = dyn_cast<CallInst>(ii1);
 219       //           if(callInst->getCalledFunction()->getName()=="trigger")
 220       //             continue;
 221       //         }
 222       //       }
 223
 224       Node *nd=findBB(nodes, BB);
 225       assert(nd && "No node for this edge!");
 226
 227       for(succ_iterator s=succ_begin(BB), se=succ_end(BB); s!=se; ++s){
 228
 229         if(triggerBBs[*s] == 9){
 230           //if(!pathReg[M]){ //Get the path register for this!
 231           //if(BB->size()>8)
 232           //  if(LoadInst *ldInst = dyn_cast<LoadInst>(BB->getInstList().begin()))
 233           //    pathReg[M] = ldInst->getPointerOperand();
 234           //}
 235           continue;
 236         }
 237         //if((*s)->size()==3)
 238         //if(CallInst *callInst =
 239         //   dyn_cast<CallInst>((*s)->getInstList().begin()))
 240         //  if(callInst->getCalledFunction()->getName() == "trigger")
 241         //    continue;
 242
 243         //  if((*s)->size()==2){
 244         //           const Instruction *inst = (*s)->getInstList().begin();
 245         //           if(isa<CallInst>(inst)){
 246         //             Instruction *ii1 = (*s)->getInstList().begin();
 247         //             CallInst *callInst = dyn_cast<CallInst>(ii1);
 248         //             if(callInst->getCalledFunction()->getName()=="trigger")
 249         //               continue;
 250         //           }
 251         //         }
 252
 253         Node *nd2 = findBB(nodes,*s);
 254         assert(nd2 && "No node for this edge!");
 255         Edge ed(nd,nd2,0);
 256         edges.push_back(ed);
 257       }
 258     }
 259
 260     graphMap[M]= new Graph(nodes,edges, startNode, exitNode);
 261
 262     Graph *g = graphMap[M];
 263
 264     if (M->size() <= 1) return; //uninstrumented
 265
 266     //step 2: getBackEdges
 267     //vector<Edge> be;
 268     std::map<Node *, int> nodePriority;
 269     g->getBackEdges(beMap[M], nodePriority);
 270
 271     //step 3: add dummy edges
 272     //vector<Edge> stDummy;
 273     //vector<Edge> exDummy;
 274     addDummyEdges(stMap[M], exMap[M], *g, beMap[M]);
 275
 276     //step 4: value assgn to edges
 277     int numPaths = valueAssignmentToEdges(*g, nodePriority, beMap[M]);
 278   }
 279
 280
 281   //step 5: now travel from root, select max(edge) < pathNo,
 282   //and go on until reach the exit
 283   getPathFrmNode(graphMap[M]->getRoot(), vBB, pathNo, *graphMap[M],
 284                  stMap[M], exMap[M], beMap[M], -1);
 285
 286
 287   //post process vBB to locate instructions to be erased
 288   /*
 289   if(pathReg[M]){
 290     for(vector<BasicBlock *>::iterator VBI = vBB.begin(), VBE = vBB.end();
 291         VBI != VBE; ++VBI){
 292       for(BasicBlock::iterator BBI = (*VBI)->begin(), BBE = (*VBI)->end();
 293           BBI != BBE; ++BBI){
 294         if(LoadInst *ldInst = dyn_cast<LoadInst>(BBI)){
 295           if(pathReg[M] == ldInst->getPointerOperand())
 296             instToErase.push_back(ldInst);
 297         }
 298         else if(StoreInst *stInst = dyn_cast<StoreInst>(BBI)){
 299           if(pathReg[M] == stInst->getPointerOperand())
 300             instToErase.push_back(stInst);
 301         }
 302       }
 303     }
 304   }
 305   */
 306 }
 307
 308 } // End llvm namespace