lib/Transforms/Instrumentation/ProfilePaths/RetracePath.cpp

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