LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

RetracePath.cpp

Go to the documentation of this file.
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