LLVM API Documentation
00001 //===- RetracePath.cpp ----------------------------------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Retraces a path of BasicBlock, given a path number and a graph! 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/Module.h" 00015 #include "llvm/Instructions.h" 00016 #include "llvm/Support/CFG.h" 00017 #include "Graph.h" 00018 #include <iostream> 00019 00020 using std::vector; 00021 using std::map; 00022 using std::cerr; 00023 00024 namespace llvm { 00025 00026 //Routines to get the path trace! 00027 00028 void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph &g, 00029 vector<Edge> &stDummy, vector<Edge> &exDummy, 00030 vector<Edge> &be, 00031 double strand){ 00032 Graph::nodeList &nlist = g.getNodeList(n); 00033 00034 //printGraph(g); 00035 //std::cerr<<"Path No: "<<pathNo<<"\n"; 00036 int maxCount=-9999999; 00037 bool isStart=false; 00038 00039 if(*n==*g.getRoot())//its root: so first node of path 00040 isStart=true; 00041 00042 double edgeRnd=0; 00043 Node *nextRoot=n; 00044 for(Graph::nodeList::iterator NLI = nlist.begin(), NLE=nlist.end(); NLI!=NLE; 00045 ++NLI){ 00046 if(NLI->weight>maxCount && NLI->weight<=pathNo){ 00047 maxCount=NLI->weight; 00048 nextRoot=NLI->element; 00049 edgeRnd=NLI->randId; 00050 if(isStart) 00051 strand=NLI->randId; 00052 } 00053 } 00054 00055 if(!isStart) 00056 assert(strand!=-1 && "strand not assigned!"); 00057 00058 assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go"); 00059 assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit"); 00060 00061 vBB.push_back(n->getElement()); 00062 00063 if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){ 00064 00065 //look for strnd and edgeRnd now: 00066 bool has1=false, has2=false; 00067 //check if exit has it 00068 for(vector<Edge>::iterator VI=exDummy.begin(), VE=exDummy.end(); VI!=VE; 00069 ++VI){ 00070 if(VI->getRandId()==edgeRnd){ 00071 has2=true; 00072 break; 00073 } 00074 } 00075 00076 //check if start has it 00077 for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE; 00078 ++VI){ 00079 if(VI->getRandId()==strand){ 00080 has1=true; 00081 break; 00082 } 00083 } 00084 00085 if(has1){ 00086 //find backedge with endpoint vBB[1] 00087 for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){ 00088 assert(vBB.size()>0 && "vector too small"); 00089 if( VI->getSecond()->getElement() == vBB[1] ){ 00090 //vBB[0]=VI->getFirst()->getElement(); 00091 vBB.erase(vBB.begin()); 00092 break; 00093 } 00094 } 00095 } 00096 00097 if(has2){ 00098 //find backedge with startpoint vBB[vBB.size()-1] 00099 for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){ 00100 assert(vBB.size()>0 && "vector too small"); 00101 if( VI->getFirst()->getElement() == vBB[vBB.size()-1] && 00102 VI->getSecond()->getElement() == vBB[0]){ 00103 //vBB.push_back(VI->getSecond()->getElement()); 00104 break; 00105 } 00106 } 00107 } 00108 else 00109 vBB.push_back(nextRoot->getElement()); 00110 00111 return; 00112 } 00113 00114 assert(pathNo-maxCount>=0); 00115 00116 return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy, 00117 exDummy, be, strand); 00118 } 00119 00120 00121 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){ 00122 for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){ 00123 if(((*si)->getElement())==BB){ 00124 return *si; 00125 } 00126 } 00127 return NULL; 00128 } 00129 00130 void getBBtrace(vector<BasicBlock *> &vBB, int pathNo, Function *M){//, 00131 // vector<Instruction *> &instToErase){ 00132 //step 1: create graph 00133 //Transform the cfg s.t. we have just one exit node 00134 00135 std::vector<Node *> nodes; 00136 std::vector<Edge> edges; 00137 Node *exitNode=0, *startNode=0; 00138 00139 //Creat cfg just once for each function! 00140 static std::map<Function *, Graph *> graphMap; 00141 00142 //get backedges, exit and start edges for the graphs and store them 00143 static std::map<Function *, vector<Edge> > stMap, exMap, beMap; 00144 static std::map<Function *, Value *> pathReg; //path register 00145 00146 00147 if(!graphMap[M]){ 00148 BasicBlock *ExitNode = 0; 00149 for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I){ 00150 if (isa<ReturnInst>(I->getTerminator())) { 00151 ExitNode = I; 00152 break; 00153 } 00154 } 00155 00156 assert(ExitNode!=0 && "exitnode not found"); 00157 00158 //iterating over BBs and making graph 00159 //The nodes must be uniquely identified: 00160 //That is, no two nodes must hav same BB* 00161 00162 //keep a map for trigger basicblocks! 00163 std::map<BasicBlock *, unsigned char> triggerBBs; 00164 //First enter just nodes: later enter edges 00165 for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){ 00166 bool cont = false; 00167 00168 if(BB->size()==3 || BB->size() ==2){ 00169 for(BasicBlock::iterator II = BB->begin(), IE = BB->end(); 00170 II != IE; ++II){ 00171 if(CallInst *callInst = dyn_cast<CallInst>(II)){ 00172 //std::cerr<<*callInst; 00173 Function *calledFunction = callInst->getCalledFunction(); 00174 if(calledFunction && calledFunction->getName() == "trigger"){ 00175 triggerBBs[BB] = 9; 00176 cont = true; 00177 //std::cerr<<"Found trigger!\n"; 00178 break; 00179 } 00180 } 00181 } 00182 } 00183 00184 if(cont) 00185 continue; 00186 00187 // const Instruction *inst = BB->getInstList().begin(); 00188 // if(isa<CallInst>(inst)){ 00189 // Instruction *ii1 = BB->getInstList().begin(); 00190 // CallInst *callInst = dyn_cast<CallInst>(ii1); 00191 // if(callInst->getCalledFunction()->getName()=="trigger") 00192 // continue; 00193 // } 00194 00195 Node *nd=new Node(BB); 00196 nodes.push_back(nd); 00197 if(&*BB==ExitNode) 00198 exitNode=nd; 00199 if(&*BB==&M->front()) 00200 startNode=nd; 00201 } 00202 00203 assert(exitNode!=0 && startNode!=0 && "Start or exit not found!"); 00204 00205 for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){ 00206 if(triggerBBs[BB] == 9) 00207 continue; 00208 00209 //if(BB->size()==3) 00210 //if(CallInst *callInst = dyn_cast<CallInst>(BB->getInstList().begin())) 00211 //if(callInst->getCalledFunction()->getName() == "trigger") 00212 //continue; 00213 00214 // if(BB->size()==2){ 00215 // const Instruction *inst = BB->getInstList().begin(); 00216 // if(isa<CallInst>(inst)){ 00217 // Instruction *ii1 = BB->getInstList().begin(); 00218 // CallInst *callInst = dyn_cast<CallInst>(ii1); 00219 // if(callInst->getCalledFunction()->getName()=="trigger") 00220 // continue; 00221 // } 00222 // } 00223 00224 Node *nd=findBB(nodes, BB); 00225 assert(nd && "No node for this edge!"); 00226 00227 for(succ_iterator s=succ_begin(BB), se=succ_end(BB); s!=se; ++s){ 00228 00229 if(triggerBBs[*s] == 9){ 00230 //if(!pathReg[M]){ //Get the path register for this! 00231 //if(BB->size()>8) 00232 // if(LoadInst *ldInst = dyn_cast<LoadInst>(BB->getInstList().begin())) 00233 // pathReg[M] = ldInst->getPointerOperand(); 00234 //} 00235 continue; 00236 } 00237 //if((*s)->size()==3) 00238 //if(CallInst *callInst = 00239 // dyn_cast<CallInst>((*s)->getInstList().begin())) 00240 // if(callInst->getCalledFunction()->getName() == "trigger") 00241 // continue; 00242 00243 // if((*s)->size()==2){ 00244 // const Instruction *inst = (*s)->getInstList().begin(); 00245 // if(isa<CallInst>(inst)){ 00246 // Instruction *ii1 = (*s)->getInstList().begin(); 00247 // CallInst *callInst = dyn_cast<CallInst>(ii1); 00248 // if(callInst->getCalledFunction()->getName()=="trigger") 00249 // continue; 00250 // } 00251 // } 00252 00253 Node *nd2 = findBB(nodes,*s); 00254 assert(nd2 && "No node for this edge!"); 00255 Edge ed(nd,nd2,0); 00256 edges.push_back(ed); 00257 } 00258 } 00259 00260 graphMap[M]= new Graph(nodes,edges, startNode, exitNode); 00261 00262 Graph *g = graphMap[M]; 00263 00264 if (M->size() <= 1) return; //uninstrumented 00265 00266 //step 2: getBackEdges 00267 //vector<Edge> be; 00268 std::map<Node *, int> nodePriority; 00269 g->getBackEdges(beMap[M], nodePriority); 00270 00271 //step 3: add dummy edges 00272 //vector<Edge> stDummy; 00273 //vector<Edge> exDummy; 00274 addDummyEdges(stMap[M], exMap[M], *g, beMap[M]); 00275 00276 //step 4: value assgn to edges 00277 int numPaths = valueAssignmentToEdges(*g, nodePriority, beMap[M]); 00278 } 00279 00280 00281 //step 5: now travel from root, select max(edge) < pathNo, 00282 //and go on until reach the exit 00283 getPathFrmNode(graphMap[M]->getRoot(), vBB, pathNo, *graphMap[M], 00284 stMap[M], exMap[M], beMap[M], -1); 00285 00286 00287 //post process vBB to locate instructions to be erased 00288 /* 00289 if(pathReg[M]){ 00290 for(vector<BasicBlock *>::iterator VBI = vBB.begin(), VBE = vBB.end(); 00291 VBI != VBE; ++VBI){ 00292 for(BasicBlock::iterator BBI = (*VBI)->begin(), BBE = (*VBI)->end(); 00293 BBI != BBE; ++BBI){ 00294 if(LoadInst *ldInst = dyn_cast<LoadInst>(BBI)){ 00295 if(pathReg[M] == ldInst->getPointerOperand()) 00296 instToErase.push_back(ldInst); 00297 } 00298 else if(StoreInst *stInst = dyn_cast<StoreInst>(BBI)){ 00299 if(pathReg[M] == stInst->getPointerOperand()) 00300 instToErase.push_back(stInst); 00301 } 00302 } 00303 } 00304 } 00305 */ 00306 } 00307 00308 } // End llvm namespace