1 //===- RetracePath.cpp ----------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // Retraces a path of BasicBlock, given a path number and a graph!
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Module.h"
15 #include "llvm/Instructions.h"
16 #include "llvm/Support/CFG.h"
26 //Routines to get the path trace!
28 void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph &g,
29 vector<Edge> &stDummy, vector<Edge> &exDummy,
32 Graph::nodeList &nlist = g.getNodeList(n);
35 //std::cerr<<"Path No: "<<pathNo<<"\n";
36 int maxCount=-9999999;
39 if(*n==*g.getRoot())//its root: so first node of path
44 for(Graph::nodeList::iterator NLI = nlist.begin(), NLE=nlist.end(); NLI!=NLE;
46 if(NLI->weight>maxCount && NLI->weight<=pathNo){
48 nextRoot=NLI->element;
56 assert(strand!=-1 && "strand not assigned!");
58 assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go");
59 assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit");
61 vBB.push_back(n->getElement());
63 if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){
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;
70 if(VI->getRandId()==edgeRnd){
76 //check if start has it
77 for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE;
79 if(VI->getRandId()==strand){
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());
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());
109 vBB.push_back(nextRoot->getElement());
114 assert(pathNo-maxCount>=0);
116 return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy,
117 exDummy, be, strand);
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){
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
135 std::vector<Node *> nodes;
136 std::vector<Edge> edges;
137 Node *exitNode=0, *startNode=0;
139 //Creat cfg just once for each function!
140 static std::map<Function *, Graph *> graphMap;
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
148 BasicBlock *ExitNode = 0;
149 for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I){
150 if (isa<ReturnInst>(I->getTerminator())) {
156 assert(ExitNode!=0 && "exitnode not found");
158 //iterating over BBs and making graph
159 //The nodes must be uniquely identified:
160 //That is, no two nodes must hav same BB*
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){
168 if(BB->size()==3 || BB->size() ==2){
169 for(BasicBlock::iterator II = BB->begin(), IE = BB->end();
171 if(CallInst *callInst = dyn_cast<CallInst>(II)){
172 //std::cerr<<*callInst;
173 Function *calledFunction = callInst->getCalledFunction();
174 if(calledFunction && calledFunction->getName() == "trigger"){
177 //std::cerr<<"Found trigger!\n";
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")
195 Node *nd=new Node(BB);
199 if(&*BB==&M->front())
203 assert(exitNode!=0 && startNode!=0 && "Start or exit not found!");
205 for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
206 if(triggerBBs[BB] == 9)
210 //if(CallInst *callInst = dyn_cast<CallInst>(BB->getInstList().begin()))
211 //if(callInst->getCalledFunction()->getName() == "trigger")
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")
224 Node *nd=findBB(nodes, BB);
225 assert(nd && "No node for this edge!");
227 for(succ_iterator s=succ_begin(BB), se=succ_end(BB); s!=se; ++s){
229 if(triggerBBs[*s] == 9){
230 //if(!pathReg[M]){ //Get the path register for this!
232 // if(LoadInst *ldInst = dyn_cast<LoadInst>(BB->getInstList().begin()))
233 // pathReg[M] = ldInst->getPointerOperand();
237 //if((*s)->size()==3)
238 //if(CallInst *callInst =
239 // dyn_cast<CallInst>((*s)->getInstList().begin()))
240 // if(callInst->getCalledFunction()->getName() == "trigger")
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")
253 Node *nd2 = findBB(nodes,*s);
254 assert(nd2 && "No node for this edge!");
260 graphMap[M]= new Graph(nodes,edges, startNode, exitNode);
262 Graph *g = graphMap[M];
264 if (M->size() <= 1) return; //uninstrumented
266 //step 2: getBackEdges
268 std::map<Node *, int> nodePriority;
269 g->getBackEdges(beMap[M], nodePriority);
271 //step 3: add dummy edges
272 //vector<Edge> stDummy;
273 //vector<Edge> exDummy;
274 addDummyEdges(stMap[M], exMap[M], *g, beMap[M]);
276 //step 4: value assgn to edges
277 int numPaths = valueAssignmentToEdges(*g, nodePriority, beMap[M]);
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);
287 //post process vBB to locate instructions to be erased
290 for(vector<BasicBlock *>::iterator VBI = vBB.begin(), VBE = vBB.end();
292 for(BasicBlock::iterator BBI = (*VBI)->begin(), BBE = (*VBI)->end();
294 if(LoadInst *ldInst = dyn_cast<LoadInst>(BBI)){
295 if(pathReg[M] == ldInst->getPointerOperand())
296 instToErase.push_back(ldInst);
298 else if(StoreInst *stInst = dyn_cast<StoreInst>(BBI)){
299 if(pathReg[M] == stInst->getPointerOperand())
300 instToErase.push_back(stInst);
308 } // End llvm namespace