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/Transforms/Instrumentation/Graph.h"
   8 #include "llvm/Module.h"
   9 #include "llvm/BasicBlock.h"
  10 #include "llvm/iTerminators.h"
  11 #include "llvm/Support/CFG.h"
  12 #include "llvm/Function.h"
  13 #include "llvm/iOther.h"
  14 #include "Support/Casting.h"
  15 #include <iostream>
  16 #include <vector>
  17 #include <map>
  18
  19 using std::vector;
  20 using std::map;
  21 using std::cerr;
  22
  23 //Routines to get the path trace!
  24
  25 void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph g,
  26                     vector<Edge> &stDummy, vector<Edge> &exDummy,
  27                     vector<Edge> &be,
  28                     double strand){
  29   Graph::nodeList nlist=g.getNodeList(n);
  30
  31   int maxCount=-9999999;
  32   bool isStart=false;
  33
  34   if(*n==*g.getRoot())//its root: so first node of path
  35     isStart=true;
  36
  37   double edgeRnd=0;
  38   Node *nextRoot=n;
  39   for(Graph::nodeList::iterator NLI=nlist.begin(), NLE=nlist.end(); NLI!=NLE;
  40       ++NLI){
  41     if(NLI->weight>maxCount && NLI->weight<=pathNo){
  42       maxCount=NLI->weight;
  43       nextRoot=NLI->element;
  44       edgeRnd=NLI->randId;
  45       if(isStart)
  46         strand=NLI->randId;
  47     }
  48   }
  49
  50   if(!isStart)
  51     assert(strand!=-1 && "strand not assigned!");
  52
  53   assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go");
  54   assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit");
  55
  56   vBB.push_back(n->getElement());
  57
  58   if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){
  59
  60     //look for strnd and edgeRnd now:
  61     bool has1=false, has2=false;
  62     //check if exit has it
  63     for(vector<Edge>::iterator VI=exDummy.begin(), VE=exDummy.end(); VI!=VE;
  64         ++VI){
  65       if(VI->getRandId()==edgeRnd){
  66         has2=true;
  67         break;
  68       }
  69     }
  70
  71     //check if start has it
  72     for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE;
  73         ++VI){
  74       if(VI->getRandId()==strand){
  75         has1=true;
  76         break;
  77       }
  78     }
  79
  80     if(has1){
  81       //find backedge with endpoint vBB[1]
  82       for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
  83         assert(vBB.size()>0 && "vector too small");
  84         if( VI->getSecond()->getElement() == vBB[1] ){
  85           //vBB[0]=VI->getFirst()->getElement();
  86           vBB.erase(vBB.begin());
  87           break;
  88         }
  89       }
  90     }
  91
  92     if(has2){
  93       //find backedge with startpoint vBB[vBB.size()-1]
  94       for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
  95         assert(vBB.size()>0 && "vector too small");
  96         if( VI->getFirst()->getElement() == vBB[vBB.size()-1] &&
  97             VI->getSecond()->getElement() == vBB[0]){
  98           //vBB.push_back(VI->getSecond()->getElement());
  99           break;
 100         }
 101       }
 102     }
 103     else
 104       vBB.push_back(nextRoot->getElement());
 105
 106     return;
 107   }
 108
 109   assert(pathNo-maxCount>=0);
 110
 111   return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy,
 112                         exDummy, be, strand);
 113 }
 114
 115
 116 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
 117   for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
 118     if(((*si)->getElement())==BB){
 119       return *si;
 120     }
 121   }
 122   return NULL;
 123 }
 124
 125 void getBBtrace(vector<BasicBlock *> &vBB, int pathNo, Function *M){
 126   //step 1: create graph
 127   //Transform the cfg s.t. we have just one exit node
 128
 129   std::vector<Node *> nodes;
 130   std::vector<Edge> edges;
 131   Node *tmp;
 132   Node *exitNode=0, *startNode=0;
 133   static std::map<Function *, Graph *> graphMap;
 134   static std::map<Function *, vector<Edge> > stMap, exMap, beMap;
 135
 136   if(!graphMap[M]){
 137     BasicBlock *ExitNode = 0;
 138     for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I){
 139       if (isa<ReturnInst>(I->getTerminator())) {
 140         ExitNode = &*I;
 141         break;
 142       }
 143     }
 144
 145     assert(ExitNode!=0 && "exitnode not found");
 146
 147     //iterating over BBs and making graph
 148     //The nodes must be uniquely identified:
 149     //That is, no two nodes must hav same BB*
 150
 151     //First enter just nodes: later enter edges
 152     for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
 153       if(BB->size()==2){
 154         const Instruction *inst = BB->getInstList().begin();
 155         if(isa<CallInst>(inst)){
 156           Instruction *ii1 = BB->getInstList().begin();
 157           CallInst *callInst = dyn_cast<CallInst>(ii1);
 158           if(callInst->getCalledFunction()->getName()=="trigger")
 159             continue;
 160         }
 161       }
 162       Node *nd=new Node(BB);
 163       nodes.push_back(nd);
 164       if(&*BB==ExitNode)
 165         exitNode=nd;
 166       if(&*BB==&M->front())
 167         startNode=nd;
 168     }
 169
 170     assert(exitNode!=0 && startNode!=0 && "Start or exit not found!");
 171
 172     for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
 173       if(BB->size()==2){
 174         const Instruction *inst = BB->getInstList().begin();
 175         if(isa<CallInst>(inst)){
 176           Instruction *ii1 = BB->getInstList().begin();
 177           CallInst *callInst = dyn_cast<CallInst>(ii1);
 178           if(callInst->getCalledFunction()->getName()=="trigger")
 179             continue;
 180         }
 181       }
 182
 183       Node *nd=findBB(nodes, BB);
 184       assert(nd && "No node for this edge!");
 185
 186       for(BasicBlock::succ_iterator s=succ_begin(&*BB), se=succ_end(&*BB);
 187           s!=se; ++s){
 188         if((*s)->size()==2){
 189           const Instruction *inst = (*s)->getInstList().begin();
 190           if(isa<CallInst>(inst)){
 191             Instruction *ii1 = (*s)->getInstList().begin();
 192             CallInst *callInst = dyn_cast<CallInst>(ii1);
 193             if(callInst->getCalledFunction()->getName()=="trigger")
 194               continue;
 195           }
 196         }
 197
 198         Node *nd2=findBB(nodes,*s);
 199         assert(nd2 && "No node for this edge!");
 200         Edge ed(nd,nd2,0);
 201         edges.push_back(ed);
 202       }
 203     }
 204
 205     graphMap[M]= new Graph(nodes,edges, startNode, exitNode);
 206
 207     Graph *g = graphMap[M];
 208
 209     if (M->size() <= 1) return; //uninstrumented
 210
 211     //step 2: getBackEdges
 212     //vector<Edge> be;
 213     std::map<Node *, int> nodePriority;
 214     g->getBackEdges(beMap[M], nodePriority);
 215
 216     //step 3: add dummy edges
 217     //vector<Edge> stDummy;
 218     //vector<Edge> exDummy;
 219     addDummyEdges(stMap[M], exMap[M], *g, beMap[M]);
 220
 221     //step 4: value assgn to edges
 222     int numPaths = valueAssignmentToEdges(*g, nodePriority, beMap[M]);
 223   }
 224
 225   //step 5: now travel from root, select max(edge) < pathNo,
 226   //and go on until reach the exit
 227   return getPathFrmNode(graphMap[M]->getRoot(), vBB, pathNo, *graphMap[M],
 228                         stMap[M], exMap[M], beMap[M], -1);
 229 }