LLVM API Documentation
00001 //===- GraphAuxiliary.cpp - Auxiliary functions on graph ------------------===// 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 // auxiliary function associated with graph: they all operate on graph, and help 00011 // in inserting instrumentation for trace generation 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Pass.h" 00016 #include "llvm/Module.h" 00017 #include "llvm/Instructions.h" 00018 #include "llvm/Support/Debug.h" 00019 #include <algorithm> 00020 #include "Graph.h" 00021 00022 //using std::list; 00023 using std::map; 00024 using std::vector; 00025 using std::cerr; 00026 00027 namespace llvm { 00028 00029 //check if 2 edges are equal (same endpoints and same weight) 00030 static bool edgesEqual(Edge ed1, Edge ed2){ 00031 return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight()); 00032 } 00033 00034 //Get the vector of edges that are to be instrumented in the graph 00035 static void getChords(vector<Edge > &chords, Graph &g, Graph st){ 00036 //make sure the spanning tree is directional 00037 //iterate over ALL the edges of the graph 00038 vector<Node *> allNodes=g.getAllNodes(); 00039 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 00040 ++NI){ 00041 Graph::nodeList node_list=g.getNodeList(*NI); 00042 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 00043 NLI!=NLE; ++NLI){ 00044 Edge f(*NI, NLI->element,NLI->weight, NLI->randId); 00045 if(!(st.hasEdgeAndWt(f)))//addnl 00046 chords.push_back(f); 00047 } 00048 } 00049 } 00050 00051 //Given a tree t, and a "directed graph" g 00052 //replace the edges in the tree t with edges that exist in graph 00053 //The tree is formed from "undirectional" copy of graph 00054 //So whatever edges the tree has, the undirectional graph 00055 //would have too. This function corrects some of the directions in 00056 //the tree so that now, all edge directions in the tree match 00057 //the edge directions of corresponding edges in the directed graph 00058 static void removeTreeEdges(Graph &g, Graph& t){ 00059 vector<Node* > allNodes=t.getAllNodes(); 00060 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 00061 ++NI){ 00062 Graph::nodeList nl=t.getNodeList(*NI); 00063 for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){ 00064 Edge ed(NLI->element, *NI, NLI->weight); 00065 if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge 00066 //between any pair of vertices, so no need to delete by edge wt 00067 } 00068 } 00069 } 00070 00071 //Assign a value to all the edges in the graph 00072 //such that if we traverse along any path from root to exit, and 00073 //add up the edge values, we get a path number that uniquely 00074 //refers to the path we travelled 00075 int valueAssignmentToEdges(Graph& g, map<Node *, int> nodePriority, 00076 vector<Edge> &be){ 00077 vector<Node *> revtop=g.reverseTopologicalSort(); 00078 map<Node *,int > NumPaths; 00079 for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); 00080 RI!=RE; ++RI){ 00081 if(g.isLeaf(*RI)) 00082 NumPaths[*RI]=1; 00083 else{ 00084 NumPaths[*RI]=0; 00085 00086 // Modified Graph::nodeList &nlist=g.getNodeList(*RI); 00087 Graph::nodeList &nlist=g.getSortedNodeList(*RI, be); 00088 00089 //sort nodelist by increasing order of numpaths 00090 00091 int sz=nlist.size(); 00092 00093 for(int i=0;i<sz-1; i++){ 00094 int min=i; 00095 for(int j=i+1; j<sz; j++){ 00096 BasicBlock *bb1 = nlist[j].element->getElement(); 00097 BasicBlock *bb2 = nlist[min].element->getElement(); 00098 00099 if(bb1 == bb2) continue; 00100 00101 if(*RI == g.getRoot()){ 00102 assert(nodePriority[nlist[min].element]!= 00103 nodePriority[nlist[j].element] 00104 && "priorities can't be same!"); 00105 00106 if(nodePriority[nlist[j].element] < 00107 nodePriority[nlist[min].element]) 00108 min = j; 00109 } 00110 00111 else{ 00112 TerminatorInst *tti = (*RI)->getElement()->getTerminator(); 00113 00114 BranchInst *ti = cast<BranchInst>(tti); 00115 assert(ti && "not a branch"); 00116 assert(ti->getNumSuccessors()==2 && "less successors!"); 00117 00118 BasicBlock *tB = ti->getSuccessor(0); 00119 BasicBlock *fB = ti->getSuccessor(1); 00120 00121 if(tB == bb1 || fB == bb2) 00122 min = j; 00123 } 00124 00125 } 00126 graphListElement tempEl=nlist[min]; 00127 nlist[min]=nlist[i]; 00128 nlist[i]=tempEl; 00129 } 00130 00131 //sorted now! 00132 for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end(); 00133 GLI!=GLE; ++GLI){ 00134 GLI->weight=NumPaths[*RI]; 00135 NumPaths[*RI]+=NumPaths[GLI->element]; 00136 } 00137 } 00138 } 00139 return NumPaths[g.getRoot()]; 00140 } 00141 00142 //This is a helper function to get the edge increments 00143 //This is used in conjunction with inc_DFS 00144 //to get the edge increments 00145 //Edge increment implies assigning a value to all the edges in the graph 00146 //such that if we traverse along any path from root to exit, and 00147 //add up the edge values, we get a path number that uniquely 00148 //refers to the path we travelled 00149 //inc_Dir tells whether 2 edges are in same, or in different directions 00150 //if same direction, return 1, else -1 00151 static int inc_Dir(Edge e, Edge f){ 00152 if(e.isNull()) 00153 return 1; 00154 00155 //check that the edges must have at least one common endpoint 00156 assert(*(e.getFirst())==*(f.getFirst()) || 00157 *(e.getFirst())==*(f.getSecond()) || 00158 *(e.getSecond())==*(f.getFirst()) || 00159 *(e.getSecond())==*(f.getSecond())); 00160 00161 if(*(e.getFirst())==*(f.getSecond()) || 00162 *(e.getSecond())==*(f.getFirst())) 00163 return 1; 00164 00165 return -1; 00166 } 00167 00168 00169 //used for getting edge increments (read comments above in inc_Dir) 00170 //inc_DFS is a modification of DFS 00171 static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare2>& Increment, 00172 int events, Node *v, Edge e){ 00173 00174 vector<Node *> allNodes=t.getAllNodes(); 00175 00176 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 00177 ++NI){ 00178 Graph::nodeList node_list=t.getNodeList(*NI); 00179 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 00180 NLI!= NLE; ++NLI){ 00181 Edge f(*NI, NLI->element,NLI->weight, NLI->randId); 00182 if(!edgesEqual(f,e) && *v==*(f.getSecond())){ 00183 int dir_count=inc_Dir(e,f); 00184 int wt=1*f.getWeight(); 00185 inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f); 00186 } 00187 } 00188 } 00189 00190 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 00191 ++NI){ 00192 Graph::nodeList node_list=t.getNodeList(*NI); 00193 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 00194 NLI!=NLE; ++NLI){ 00195 Edge f(*NI, NLI->element,NLI->weight, NLI->randId); 00196 if(!edgesEqual(f,e) && *v==*(f.getFirst())){ 00197 int dir_count=inc_Dir(e,f); 00198 int wt=f.getWeight(); 00199 inc_DFS(g,t, Increment, dir_count*events+wt, 00200 f.getSecond(), f); 00201 } 00202 } 00203 } 00204 00205 allNodes=g.getAllNodes(); 00206 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 00207 ++NI){ 00208 Graph::nodeList node_list=g.getNodeList(*NI); 00209 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 00210 NLI!=NLE; ++NLI){ 00211 Edge f(*NI, NLI->element,NLI->weight, NLI->randId); 00212 if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) || 00213 *v==*(f.getFirst()))){ 00214 int dir_count=inc_Dir(e,f); 00215 Increment[f]+=dir_count*events; 00216 } 00217 } 00218 } 00219 } 00220 00221 //Now we select a subset of all edges 00222 //and assign them some values such that 00223 //if we consider just this subset, it still represents 00224 //the path sum along any path in the graph 00225 static map<Edge, int, EdgeCompare2> getEdgeIncrements(Graph& g, Graph& t, 00226 vector<Edge> &be){ 00227 //get all edges in g-t 00228 map<Edge, int, EdgeCompare2> Increment; 00229 00230 vector<Node *> allNodes=g.getAllNodes(); 00231 00232 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 00233 ++NI){ 00234 Graph::nodeList node_list=g.getSortedNodeList(*NI, be); 00235 //modified g.getNodeList(*NI); 00236 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 00237 NLI!=NLE; ++NLI){ 00238 Edge ed(*NI, NLI->element,NLI->weight,NLI->randId); 00239 if(!(t.hasEdgeAndWt(ed))){ 00240 Increment[ed]=0;; 00241 } 00242 } 00243 } 00244 00245 Edge *ed=new Edge(); 00246 inc_DFS(g,t,Increment, 0, g.getRoot(), *ed); 00247 00248 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 00249 ++NI){ 00250 Graph::nodeList node_list=g.getSortedNodeList(*NI, be); 00251 //modified g.getNodeList(*NI); 00252 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 00253 NLI!=NLE; ++NLI){ 00254 Edge ed(*NI, NLI->element,NLI->weight, NLI->randId); 00255 if(!(t.hasEdgeAndWt(ed))){ 00256 int wt=ed.getWeight(); 00257 Increment[ed]+=wt; 00258 } 00259 } 00260 } 00261 00262 return Increment; 00263 } 00264 00265 //push it up: TODO 00266 const graphListElement *findNodeInList(const Graph::nodeList &NL, 00267 Node *N); 00268 00269 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N); 00270 //end TODO 00271 00272 //Based on edgeIncrements (above), now obtain 00273 //the kind of code to be inserted along an edge 00274 //The idea here is to minimize the computation 00275 //by inserting only the needed code 00276 static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare2> &instr, 00277 vector<Edge > &chords, 00278 map<Edge,int, EdgeCompare2> &edIncrements){ 00279 00280 //Register initialization code 00281 vector<Node *> ws; 00282 ws.push_back(g.getRoot()); 00283 while(ws.size()>0){ 00284 Node *v=ws.back(); 00285 ws.pop_back(); 00286 //for each edge v->w 00287 Graph::nodeList succs=g.getNodeList(v); 00288 00289 for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end(); 00290 nl!=ne; ++nl){ 00291 int edgeWt=nl->weight; 00292 Node *w=nl->element; 00293 //if chords has v->w 00294 Edge ed(v,w, edgeWt, nl->randId); 00295 bool hasEdge=false; 00296 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); 00297 CI!=CE && !hasEdge;++CI){ 00298 if(*CI==ed && CI->getWeight()==edgeWt){//modf 00299 hasEdge=true; 00300 } 00301 } 00302 00303 if(hasEdge){//so its a chord edge 00304 getEdgeCode *edCd=new getEdgeCode(); 00305 edCd->setCond(1); 00306 edCd->setInc(edIncrements[ed]); 00307 instr[ed]=edCd; 00308 } 00309 else if(g.getNumberOfIncomingEdges(w)==1){ 00310 ws.push_back(w); 00311 } 00312 else{ 00313 getEdgeCode *edCd=new getEdgeCode(); 00314 edCd->setCond(2); 00315 edCd->setInc(0); 00316 instr[ed]=edCd; 00317 } 00318 } 00319 } 00320 00321 /////Memory increment code 00322 ws.push_back(g.getExit()); 00323 00324 while(!ws.empty()) { 00325 Node *w=ws.back(); 00326 ws.pop_back(); 00327 00328 00329 /////// 00330 //vector<Node *> lt; 00331 vector<Node *> lllt=g.getAllNodes(); 00332 for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){ 00333 Node *lnode=*EII; 00334 Graph::nodeList &nl = g.getNodeList(lnode); 00335 //graphListElement *N = findNodeInList(nl, w); 00336 for(Graph::nodeList::const_iterator N = nl.begin(), 00337 NNEN = nl.end(); N!= NNEN; ++N){ 00338 if (*N->element == *w){ 00339 Node *v=lnode; 00340 00341 //if chords has v->w 00342 Edge ed(v,w, N->weight, N->randId); 00343 getEdgeCode *edCd=new getEdgeCode(); 00344 bool hasEdge=false; 00345 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; 00346 ++CI){ 00347 if(*CI==ed && CI->getWeight()==N->weight){ 00348 hasEdge=true; 00349 break; 00350 } 00351 } 00352 if(hasEdge){ 00353 //char str[100]; 00354 if(instr[ed]!=NULL && instr[ed]->getCond()==1){ 00355 instr[ed]->setCond(4); 00356 } 00357 else{ 00358 edCd->setCond(5); 00359 edCd->setInc(edIncrements[ed]); 00360 instr[ed]=edCd; 00361 } 00362 00363 } 00364 else if(g.getNumberOfOutgoingEdges(v)==1) 00365 ws.push_back(v); 00366 else{ 00367 edCd->setCond(6); 00368 instr[ed]=edCd; 00369 } 00370 } 00371 } 00372 } 00373 } 00374 ///// Register increment code 00375 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){ 00376 getEdgeCode *edCd=new getEdgeCode(); 00377 if(instr[*CI]==NULL){ 00378 edCd->setCond(3); 00379 edCd->setInc(edIncrements[*CI]); 00380 instr[*CI]=edCd; 00381 } 00382 } 00383 } 00384 00385 //Add dummy edges corresponding to the back edges 00386 //If a->b is a backedge 00387 //then incoming dummy edge is root->b 00388 //and outgoing dummy edge is a->exit 00389 //changed 00390 void addDummyEdges(vector<Edge > &stDummy, 00391 vector<Edge > &exDummy, 00392 Graph &g, vector<Edge> &be){ 00393 for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){ 00394 Edge ed=*VI; 00395 Node *first=ed.getFirst(); 00396 Node *second=ed.getSecond(); 00397 g.removeEdge(ed); 00398 00399 if(!(*second==*(g.getRoot()))){ 00400 Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId()); 00401 stDummy.push_back(*st); 00402 g.addEdgeForce(*st); 00403 } 00404 00405 if(!(*first==*(g.getExit()))){ 00406 Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId()); 00407 exDummy.push_back(*ex); 00408 g.addEdgeForce(*ex); 00409 } 00410 } 00411 } 00412 00413 //print a given edge in the form BB1Label->BB2Label 00414 void printEdge(Edge ed){ 00415 cerr<<((ed.getFirst())->getElement()) 00416 ->getName()<<"->"<<((ed.getSecond()) 00417 ->getElement())->getName()<< 00418 ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n"; 00419 } 00420 00421 //Move the incoming dummy edge code and outgoing dummy 00422 //edge code over to the corresponding back edge 00423 static void moveDummyCode(vector<Edge> &stDummy, 00424 vector<Edge> &exDummy, 00425 vector<Edge> &be, 00426 map<Edge, getEdgeCode *, EdgeCompare2> &insertions, 00427 Graph &g){ 00428 typedef vector<Edge >::iterator vec_iter; 00429 00430 map<Edge,getEdgeCode *, EdgeCompare2> temp; 00431 //iterate over edges with code 00432 std::vector<Edge> toErase; 00433 for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=insertions.begin(), 00434 ME=insertions.end(); MI!=ME; ++MI){ 00435 Edge ed=MI->first; 00436 getEdgeCode *edCd=MI->second; 00437 00438 ///---new code 00439 //iterate over be, and check if its starts and end vertices hv code 00440 for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){ 00441 if(ed.getRandId()==BEI->getRandId()){ 00442 00443 if(temp[*BEI]==0) 00444 temp[*BEI]=new getEdgeCode(); 00445 00446 //so ed is either in st, or ex! 00447 if(ed.getFirst()==g.getRoot()){ 00448 00449 //so its in stDummy 00450 temp[*BEI]->setCdIn(edCd); 00451 toErase.push_back(ed); 00452 } 00453 else if(ed.getSecond()==g.getExit()){ 00454 00455 //so its in exDummy 00456 toErase.push_back(ed); 00457 temp[*BEI]->setCdOut(edCd); 00458 } 00459 else{ 00460 assert(false && "Not found in either start or end! Rand failed?"); 00461 } 00462 } 00463 } 00464 } 00465 00466 for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; 00467 ++vmi){ 00468 insertions.erase(*vmi); 00469 g.removeEdgeWithWt(*vmi); 00470 } 00471 00472 for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=temp.begin(), 00473 ME=temp.end(); MI!=ME; ++MI){ 00474 insertions[MI->first]=MI->second; 00475 } 00476 00477 #ifdef DEBUG_PATH_PROFILES 00478 cerr<<"size of deletions: "<<toErase.size()<<"\n"; 00479 cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n"; 00480 #endif 00481 00482 } 00483 00484 //Do graph processing: to determine minimal edge increments, 00485 //appropriate code insertions etc and insert the code at 00486 //appropriate locations 00487 void processGraph(Graph &g, 00488 Instruction *rInst, 00489 Value *countInst, 00490 vector<Edge >& be, 00491 vector<Edge >& stDummy, 00492 vector<Edge >& exDummy, 00493 int numPaths, int MethNo, 00494 Value *threshold){ 00495 00496 //Given a graph: with exit->root edge, do the following in seq: 00497 //1. get back edges 00498 //2. insert dummy edges and remove back edges 00499 //3. get edge assignments 00500 //4. Get Max spanning tree of graph: 00501 // -Make graph g2=g undirectional 00502 // -Get Max spanning tree t 00503 // -Make t undirectional 00504 // -remove edges from t not in graph g 00505 //5. Get edge increments 00506 //6. Get code insertions 00507 //7. move code on dummy edges over to the back edges 00508 00509 00510 //This is used as maximum "weight" for 00511 //priority queue 00512 //This would hold all 00513 //right as long as number of paths in the graph 00514 //is less than this 00515 const int Infinity=99999999; 00516 00517 00518 //step 1-3 are already done on the graph when this function is called 00519 DEBUG(printGraph(g)); 00520 00521 //step 4: Get Max spanning tree of graph 00522 00523 //now insert exit to root edge 00524 //if its there earlier, remove it! 00525 //assign it weight Infinity 00526 //so that this edge IS ALWAYS IN spanning tree 00527 //Note than edges in spanning tree do not get 00528 //instrumented: and we do not want the 00529 //edge exit->root to get instrumented 00530 //as it MAY BE a dummy edge 00531 Edge ed(g.getExit(),g.getRoot(),Infinity); 00532 g.addEdge(ed,Infinity); 00533 Graph g2=g; 00534 00535 //make g2 undirectional: this gives a better 00536 //maximal spanning tree 00537 g2.makeUnDirectional(); 00538 DEBUG(printGraph(g2)); 00539 00540 Graph *t=g2.getMaxSpanningTree(); 00541 #ifdef DEBUG_PATH_PROFILES 00542 std::cerr<<"Original maxspanning tree\n"; 00543 printGraph(*t); 00544 #endif 00545 //now edges of tree t have weights reversed 00546 //(negative) because the algorithm used 00547 //to find max spanning tree is 00548 //actually for finding min spanning tree 00549 //so get back the original weights 00550 t->reverseWts(); 00551 00552 //Ordinarily, the graph is directional 00553 //lets converts the graph into an 00554 //undirectional graph 00555 //This is done by adding an edge 00556 //v->u for all existing edges u->v 00557 t->makeUnDirectional(); 00558 00559 //Given a tree t, and a "directed graph" g 00560 //replace the edges in the tree t with edges that exist in graph 00561 //The tree is formed from "undirectional" copy of graph 00562 //So whatever edges the tree has, the undirectional graph 00563 //would have too. This function corrects some of the directions in 00564 //the tree so that now, all edge directions in the tree match 00565 //the edge directions of corresponding edges in the directed graph 00566 removeTreeEdges(g, *t); 00567 00568 #ifdef DEBUG_PATH_PROFILES 00569 cerr<<"Final Spanning tree---------\n"; 00570 printGraph(*t); 00571 cerr<<"-------end spanning tree\n"; 00572 #endif 00573 00574 //now remove the exit->root node 00575 //and re-add it with weight 0 00576 //since infinite weight is kinda confusing 00577 g.removeEdge(ed); 00578 Edge edNew(g.getExit(), g.getRoot(),0); 00579 g.addEdge(edNew,0); 00580 if(t->hasEdge(ed)){ 00581 t->removeEdge(ed); 00582 t->addEdge(edNew,0); 00583 } 00584 00585 DEBUG(printGraph(g); 00586 printGraph(*t)); 00587 00588 //step 5: Get edge increments 00589 00590 //Now we select a subset of all edges 00591 //and assign them some values such that 00592 //if we consider just this subset, it still represents 00593 //the path sum along any path in the graph 00594 00595 map<Edge, int, EdgeCompare2> increment=getEdgeIncrements(g,*t, be); 00596 #ifdef DEBUG_PATH_PROFILES 00597 //print edge increments for debugging 00598 std::cerr<<"Edge Increments------\n"; 00599 for(map<Edge, int, EdgeCompare2>::iterator MMI=increment.begin(), MME=increment.end(); MMI != MME; ++MMI){ 00600 printEdge(MMI->first); 00601 std::cerr<<"Increment for above:"<<MMI->second<<"\n"; 00602 } 00603 std::cerr<<"-------end of edge increments\n"; 00604 #endif 00605 00606 00607 //step 6: Get code insertions 00608 00609 //Based on edgeIncrements (above), now obtain 00610 //the kind of code to be inserted along an edge 00611 //The idea here is to minimize the computation 00612 //by inserting only the needed code 00613 vector<Edge> chords; 00614 getChords(chords, g, *t); 00615 00616 00617 map<Edge, getEdgeCode *, EdgeCompare2> codeInsertions; 00618 getCodeInsertions(g, codeInsertions, chords,increment); 00619 00620 #ifdef DEBUG_PATH_PROFILES 00621 //print edges with code for debugging 00622 cerr<<"Code inserted in following---------------\n"; 00623 for(map<Edge, getEdgeCode *, EdgeCompare2>::iterator cd_i=codeInsertions.begin(), 00624 cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){ 00625 printEdge(cd_i->first); 00626 cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n"; 00627 } 00628 cerr<<"-----end insertions\n"; 00629 #endif 00630 00631 //step 7: move code on dummy edges over to the back edges 00632 00633 //Move the incoming dummy edge code and outgoing dummy 00634 //edge code over to the corresponding back edge 00635 00636 moveDummyCode(stDummy, exDummy, be, codeInsertions, g); 00637 00638 #ifdef DEBUG_PATH_PROFILES 00639 //debugging info 00640 cerr<<"After moving dummy code\n"; 00641 for(map<Edge, getEdgeCode *,EdgeCompare2>::iterator cd_i=codeInsertions.begin(), 00642 cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){ 00643 printEdge(cd_i->first); 00644 cerr<<cd_i->second->getCond()<<":" 00645 <<cd_i->second->getInc()<<"\n"; 00646 } 00647 cerr<<"Dummy end------------\n"; 00648 #endif 00649 00650 00651 //see what it looks like... 00652 //now insert code along edges which have codes on them 00653 for(map<Edge, getEdgeCode *,EdgeCompare2>::iterator MI=codeInsertions.begin(), 00654 ME=codeInsertions.end(); MI!=ME; ++MI){ 00655 Edge ed=MI->first; 00656 insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo, threshold); 00657 } 00658 } 00659 00660 //print the graph (for debugging) 00661 void printGraph(Graph &g){ 00662 vector<Node *> lt=g.getAllNodes(); 00663 cerr<<"Graph---------------------\n"; 00664 for(vector<Node *>::iterator LI=lt.begin(); 00665 LI!=lt.end(); ++LI){ 00666 cerr<<((*LI)->getElement())->getName()<<"->"; 00667 Graph::nodeList nl=g.getNodeList(*LI); 00668 for(Graph::nodeList::iterator NI=nl.begin(); 00669 NI!=nl.end(); ++NI){ 00670 cerr<<":"<<"("<<(NI->element->getElement()) 00671 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<"," 00672 <<NI->randId<<")"; 00673 } 00674 cerr<<"\n"; 00675 } 00676 cerr<<"--------------------Graph\n"; 00677 } 00678 00679 } // End llvm namespace