1 //===----Instrumentation/ProfilePaths/RetracePath.cppTrigger.cpp--*- C++ -*--=//
3 // Retraces a path of BasicBlock, given a path number and a graph!
5 //===----------------------------------------------------------------------===//
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"
23 //Routines to get the path trace!
25 void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph g,
26 vector<Edge> &stDummy, vector<Edge> &exDummy,
29 Graph::nodeList nlist=g.getNodeList(n);
31 int maxCount=-9999999;
34 if(*n==*g.getRoot())//its root: so first node of path
39 for(Graph::nodeList::iterator NLI=nlist.begin(), NLE=nlist.end(); NLI!=NLE;
41 if(NLI->weight>maxCount && NLI->weight<=pathNo){
43 nextRoot=NLI->element;
51 assert(strand!=-1 && "strand not assigned!");
53 assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go");
54 assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit");
56 vBB.push_back(n->getElement());
58 if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){
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;
65 if(VI->getRandId()==edgeRnd){
71 //check if start has it
72 for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE;
74 if(VI->getRandId()==strand){
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());
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());
104 vBB.push_back(nextRoot->getElement());
109 assert(pathNo-maxCount>=0);
111 return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy,
112 exDummy, be, strand);
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){
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
129 std::vector<Node *> nodes;
130 std::vector<Edge> edges;
132 Node *exitNode=0, *startNode=0;
133 static std::map<Function *, Graph *> graphMap;
134 static std::map<Function *, vector<Edge> > stMap, exMap, beMap;
137 BasicBlock *ExitNode = 0;
138 for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I){
139 if (isa<ReturnInst>(I->getTerminator())) {
145 assert(ExitNode!=0 && "exitnode not found");
147 //iterating over BBs and making graph
148 //The nodes must be uniquely identified:
149 //That is, no two nodes must hav same BB*
151 //First enter just nodes: later enter edges
152 for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
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")
162 Node *nd=new Node(BB);
166 if(&*BB==&M->front())
170 assert(exitNode!=0 && startNode!=0 && "Start or exit not found!");
172 for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
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")
183 Node *nd=findBB(nodes, BB);
184 assert(nd && "No node for this edge!");
186 for(BasicBlock::succ_iterator s=succ_begin(&*BB), se=succ_end(&*BB);
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")
198 Node *nd2=findBB(nodes,*s);
199 assert(nd2 && "No node for this edge!");
205 graphMap[M]= new Graph(nodes,edges, startNode, exitNode);
207 Graph *g = graphMap[M];
209 if (M->size() <= 1) return; //uninstrumented
211 //step 2: getBackEdges
213 std::map<Node *, int> nodePriority;
214 g->getBackEdges(beMap[M], nodePriority);
216 //step 3: add dummy edges
217 //vector<Edge> stDummy;
218 //vector<Edge> exDummy;
219 addDummyEdges(stMap[M], exMap[M], *g, beMap[M]);
221 //step 4: value assgn to edges
222 int numPaths = valueAssignmentToEdges(*g, nodePriority, beMap[M]);
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);