lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp

   1 //===-- GrapAuxillary.cpp- Auxillary functions on graph ----------*- C++ -*--=//
   2 //
   3 //auxillary function associated with graph: they
   4 //all operate on graph, and help in inserting
   5 //instrumentation for trace generation
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
  10 #include "llvm/Transforms/Instrumentation/Graph.h"
  11 #include "llvm/Pass.h"
  12 #include "llvm/Module.h"
  13 #include "llvm/InstrTypes.h"
  14 #include "llvm/iTerminators.h"
  15 #include <algorithm>
  16 #include <iostream>
  17 #include <sstream>
  18 #include <vector>
  19
  20 //using std::list;
  21 using std::map;
  22 using std::vector;
  23 using std::cerr;
  24
  25 //check if 2 edges are equal (same endpoints and same weight)
  26 static bool edgesEqual(Edge  ed1, Edge ed2){
  27   return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
  28 }
  29
  30 //Get the vector of edges that are to be instrumented in the graph
  31 static void getChords(vector<Edge > &chords, Graph &g, Graph st){
  32   //make sure the spanning tree is directional
  33   //iterate over ALL the edges of the graph
  34   vector<Node *> allNodes=g.getAllNodes();
  35   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
  36       ++NI){
  37     Graph::nodeList node_list=g.getNodeList(*NI);
  38     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
  39         NLI!=NLE; ++NLI){
  40       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
  41       if(!(st.hasEdgeAndWt(f)))//addnl
  42         chords.push_back(f);
  43     }
  44   }
  45 }
  46
  47 //Given a tree t, and a "directed graph" g
  48 //replace the edges in the tree t with edges that exist in graph
  49 //The tree is formed from "undirectional" copy of graph
  50 //So whatever edges the tree has, the undirectional graph
  51 //would have too. This function corrects some of the directions in
  52 //the tree so that now, all edge directions in the tree match
  53 //the edge directions of corresponding edges in the directed graph
  54 static void removeTreeEdges(Graph &g, Graph& t){
  55   vector<Node* > allNodes=t.getAllNodes();
  56   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
  57       ++NI){
  58     Graph::nodeList nl=t.getNodeList(*NI);
  59     for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
  60       Edge ed(NLI->element, *NI, NLI->weight);
  61       if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
  62       //between any pair of vertices, so no need to delete by edge wt
  63     }
  64   }
  65 }
  66
  67 //Assign a value to all the edges in the graph
  68 //such that if we traverse along any path from root to exit, and
  69 //add up the edge values, we get a path number that uniquely
  70 //refers to the path we travelled
  71 int valueAssignmentToEdges(Graph& g,  map<Node *, int> nodePriority,
  72                            vector<Edge> &be){
  73   vector<Node *> revtop=g.reverseTopologicalSort();
  74   map<Node *,int > NumPaths;
  75   for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end();
  76       RI!=RE; ++RI){
  77     if(g.isLeaf(*RI))
  78       NumPaths[*RI]=1;
  79     else{
  80       NumPaths[*RI]=0;
  81
  82       // Modified Graph::nodeList &nlist=g.getNodeList(*RI);
  83       Graph::nodeList &nlist=g.getSortedNodeList(*RI, be);
  84
  85       //sort nodelist by increasing order of numpaths
  86
  87       int sz=nlist.size();
  88
  89       for(int i=0;i<sz-1; i++){
  90         int min=i;
  91         for(int j=i+1; j<sz; j++){
  92           BasicBlock *bb1 = nlist[j].element->getElement();
  93           BasicBlock *bb2 = nlist[min].element->getElement();
  94
  95           if(bb1 == bb2) continue;
  96
  97           if(*RI == g.getRoot()){
  98             assert(nodePriority[nlist[min].element]!=
  99                    nodePriority[nlist[j].element]
 100                    && "priorities can't be same!");
 101
 102             if(nodePriority[nlist[j].element] <
 103                nodePriority[nlist[min].element])
 104               min = j;
 105           }
 106
 107           else{
 108             TerminatorInst *tti = (*RI)->getElement()->getTerminator();
 109
 110             BranchInst *ti =  cast<BranchInst>(tti);
 111             assert(ti && "not a branch");
 112             assert(ti->getNumSuccessors()==2 && "less successors!");
 113
 114             BasicBlock *tB = ti->getSuccessor(0);
 115             BasicBlock *fB = ti->getSuccessor(1);
 116
 117             if(tB == bb1 || fB == bb2)
 118               min = j;
 119           }
 120
 121         }
 122         graphListElement tempEl=nlist[min];
 123         nlist[min]=nlist[i];
 124         nlist[i]=tempEl;
 125       }
 126
 127       //sorted now!
 128       for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
 129           GLI!=GLE; ++GLI){
 130         GLI->weight=NumPaths[*RI];
 131         NumPaths[*RI]+=NumPaths[GLI->element];
 132       }
 133     }
 134   }
 135   return NumPaths[g.getRoot()];
 136 }
 137
 138 //This is a helper function to get the edge increments
 139 //This is used in conjuntion with inc_DFS
 140 //to get the edge increments
 141 //Edge increment implies assigning a value to all the edges in the graph
 142 //such that if we traverse along any path from root to exit, and
 143 //add up the edge values, we get a path number that uniquely
 144 //refers to the path we travelled
 145 //inc_Dir tells whether 2 edges are in same, or in different directions
 146 //if same direction, return 1, else -1
 147 static int inc_Dir(Edge e, Edge f){
 148  if(e.isNull())
 149     return 1;
 150
 151  //check that the edges must have atleast one common endpoint
 152   assert(*(e.getFirst())==*(f.getFirst()) ||
 153          *(e.getFirst())==*(f.getSecond()) ||
 154          *(e.getSecond())==*(f.getFirst()) ||
 155          *(e.getSecond())==*(f.getSecond()));
 156
 157   if(*(e.getFirst())==*(f.getSecond()) ||
 158      *(e.getSecond())==*(f.getFirst()))
 159     return 1;
 160
 161   return -1;
 162 }
 163
 164
 165 //used for getting edge increments (read comments above in inc_Dir)
 166 //inc_DFS is a modification of DFS
 167 static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare2>& Increment,
 168              int events, Node *v, Edge e){
 169
 170   vector<Node *> allNodes=t.getAllNodes();
 171
 172   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 173       ++NI){
 174     Graph::nodeList node_list=t.getNodeList(*NI);
 175     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 176         NLI!= NLE; ++NLI){
 177       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
 178       if(!edgesEqual(f,e) && *v==*(f.getSecond())){
 179         int dir_count=inc_Dir(e,f);
 180         int wt=1*f.getWeight();
 181         inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
 182       }
 183     }
 184   }
 185
 186   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 187       ++NI){
 188     Graph::nodeList node_list=t.getNodeList(*NI);
 189     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 190         NLI!=NLE; ++NLI){
 191       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
 192       if(!edgesEqual(f,e) && *v==*(f.getFirst())){
 193         int dir_count=inc_Dir(e,f);
 194         int wt=f.getWeight();
 195         inc_DFS(g,t, Increment, dir_count*events+wt,
 196                 f.getSecond(), f);
 197       }
 198     }
 199   }
 200
 201   allNodes=g.getAllNodes();
 202   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 203       ++NI){
 204     Graph::nodeList node_list=g.getNodeList(*NI);
 205     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 206         NLI!=NLE; ++NLI){
 207       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
 208       if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
 209                                   *v==*(f.getFirst()))){
 210         int dir_count=inc_Dir(e,f);
 211         Increment[f]+=dir_count*events;
 212       }
 213     }
 214   }
 215 }
 216
 217 //Now we select a subset of all edges
 218 //and assign them some values such that
 219 //if we consider just this subset, it still represents
 220 //the path sum along any path in the graph
 221 static map<Edge, int, EdgeCompare2> getEdgeIncrements(Graph& g, Graph& t,
 222                                                       vector<Edge> &be){
 223   //get all edges in g-t
 224   map<Edge, int, EdgeCompare2> Increment;
 225
 226   vector<Node *> allNodes=g.getAllNodes();
 227
 228   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 229       ++NI){
 230     Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
 231     //modified g.getNodeList(*NI);
 232     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 233         NLI!=NLE; ++NLI){
 234       Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
 235       if(!(t.hasEdgeAndWt(ed))){
 236         Increment[ed]=0;;
 237       }
 238     }
 239   }
 240
 241   Edge *ed=new Edge();
 242   inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
 243
 244   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 245       ++NI){
 246     Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
 247     //modified g.getNodeList(*NI);
 248     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 249         NLI!=NLE; ++NLI){
 250       Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
 251       if(!(t.hasEdgeAndWt(ed))){
 252         int wt=ed.getWeight();
 253         Increment[ed]+=wt;
 254       }
 255     }
 256   }
 257
 258   return Increment;
 259 }
 260
 261 //push it up: TODO
 262 const graphListElement *findNodeInList(const Graph::nodeList &NL,
 263                                               Node *N);
 264
 265 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
 266 //end TODO
 267
 268 //Based on edgeIncrements (above), now obtain
 269 //the kind of code to be inserted along an edge
 270 //The idea here is to minimize the computation
 271 //by inserting only the needed code
 272 static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare2> &instr,
 273                               vector<Edge > &chords,
 274                               map<Edge,int, EdgeCompare2> &edIncrements){
 275
 276   //Register initialization code
 277   vector<Node *> ws;
 278   ws.push_back(g.getRoot());
 279   while(ws.size()>0){
 280     Node *v=ws.back();
 281     ws.pop_back();
 282     //for each edge v->w
 283     Graph::nodeList succs=g.getNodeList(v);
 284
 285     for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
 286         nl!=ne; ++nl){
 287       int edgeWt=nl->weight;
 288       Node *w=nl->element;
 289       //if chords has v->w
 290       Edge ed(v,w, edgeWt, nl->randId);
 291       bool hasEdge=false;
 292       for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
 293           CI!=CE && !hasEdge;++CI){
 294         if(*CI==ed && CI->getWeight()==edgeWt){//modf
 295           hasEdge=true;
 296         }
 297       }
 298
 299       if(hasEdge){//so its a chord edge
 300         getEdgeCode *edCd=new getEdgeCode();
 301         edCd->setCond(1);
 302         edCd->setInc(edIncrements[ed]);
 303         instr[ed]=edCd;
 304       }
 305       else if(g.getNumberOfIncomingEdges(w)==1){
 306         ws.push_back(w);
 307       }
 308       else{
 309         getEdgeCode *edCd=new getEdgeCode();
 310         edCd->setCond(2);
 311         edCd->setInc(0);
 312         instr[ed]=edCd;
 313       }
 314     }
 315   }
 316
 317   /////Memory increment code
 318   ws.push_back(g.getExit());
 319
 320   while(!ws.empty()) {
 321     Node *w=ws.back();
 322     ws.pop_back();
 323
 324
 325     ///////
 326     //vector<Node *> lt;
 327     vector<Node *> lllt=g.getAllNodes();
 328     for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
 329       Node *lnode=*EII;
 330       Graph::nodeList &nl = g.getNodeList(lnode);
 331       //graphListElement *N = findNodeInList(nl, w);
 332       for(Graph::nodeList::const_iterator N = nl.begin(),
 333             NNEN = nl.end(); N!= NNEN; ++N){
 334         if (*N->element == *w){
 335           Node *v=lnode;
 336
 337           //if chords has v->w
 338           Edge ed(v,w, N->weight, N->randId);
 339           getEdgeCode *edCd=new getEdgeCode();
 340           bool hasEdge=false;
 341           for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
 342               ++CI){
 343             if(*CI==ed && CI->getWeight()==N->weight){
 344               hasEdge=true;
 345               break;
 346             }
 347           }
 348           if(hasEdge){
 349             //char str[100];
 350             if(instr[ed]!=NULL && instr[ed]->getCond()==1){
 351               instr[ed]->setCond(4);
 352             }
 353             else{
 354               edCd->setCond(5);
 355               edCd->setInc(edIncrements[ed]);
 356               instr[ed]=edCd;
 357             }
 358
 359           }
 360           else if(g.getNumberOfOutgoingEdges(v)==1)
 361             ws.push_back(v);
 362           else{
 363             edCd->setCond(6);
 364             instr[ed]=edCd;
 365           }
 366         }
 367       }
 368     }
 369   }
 370   ///// Register increment code
 371   for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
 372     getEdgeCode *edCd=new getEdgeCode();
 373     if(instr[*CI]==NULL){
 374       edCd->setCond(3);
 375       edCd->setInc(edIncrements[*CI]);
 376       instr[*CI]=edCd;
 377     }
 378   }
 379 }
 380
 381 //Add dummy edges corresponding to the back edges
 382 //If a->b is a backedge
 383 //then incoming dummy edge is root->b
 384 //and outgoing dummy edge is a->exit
 385 //changed
 386 void addDummyEdges(vector<Edge > &stDummy,
 387                    vector<Edge > &exDummy,
 388                    Graph &g, vector<Edge> &be){
 389   for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
 390     Edge ed=*VI;
 391     Node *first=ed.getFirst();
 392     Node *second=ed.getSecond();
 393     g.removeEdge(ed);
 394
 395     if(!(*second==*(g.getRoot()))){
 396       Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
 397       stDummy.push_back(*st);
 398       g.addEdgeForce(*st);
 399     }
 400
 401     if(!(*first==*(g.getExit()))){
 402       Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
 403       exDummy.push_back(*ex);
 404       g.addEdgeForce(*ex);
 405     }
 406   }
 407 }
 408
 409 //print a given edge in the form BB1Label->BB2Label
 410 void printEdge(Edge ed){
 411   cerr<<((ed.getFirst())->getElement())
 412     ->getName()<<"->"<<((ed.getSecond())
 413                           ->getElement())->getName()<<
 414     ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
 415 }
 416
 417 //Move the incoming dummy edge code and outgoing dummy
 418 //edge code over to the corresponding back edge
 419 static void moveDummyCode(vector<Edge> &stDummy,
 420                           vector<Edge> &exDummy,
 421                           vector<Edge> &be,
 422                           map<Edge, getEdgeCode *, EdgeCompare2> &insertions,
 423                           Graph &g){
 424   typedef vector<Edge >::iterator vec_iter;
 425
 426   map<Edge,getEdgeCode *, EdgeCompare2> temp;
 427   //iterate over edges with code
 428   std::vector<Edge> toErase;
 429   for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=insertions.begin(),
 430         ME=insertions.end(); MI!=ME; ++MI){
 431     Edge ed=MI->first;
 432     getEdgeCode *edCd=MI->second;
 433
 434     ///---new code
 435     //iterate over be, and check if its starts and end vertices hv code
 436     for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
 437       if(ed.getRandId()==BEI->getRandId()){
 438
 439         if(temp[*BEI]==0)
 440           temp[*BEI]=new getEdgeCode();
 441
 442         //so ed is either in st, or ex!
 443         if(ed.getFirst()==g.getRoot()){
 444
 445           //so its in stDummy
 446           temp[*BEI]->setCdIn(edCd);
 447           toErase.push_back(ed);
 448         }
 449         else if(ed.getSecond()==g.getExit()){
 450
 451           //so its in exDummy
 452           toErase.push_back(ed);
 453           temp[*BEI]->setCdOut(edCd);
 454         }
 455         else{
 456           assert(false && "Not found in either start or end! Rand failed?");
 457         }
 458       }
 459     }
 460   }
 461
 462   for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
 463       ++vmi){
 464     insertions.erase(*vmi);
 465     g.removeEdgeWithWt(*vmi);
 466   }
 467
 468   for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=temp.begin(),
 469       ME=temp.end(); MI!=ME; ++MI){
 470     insertions[MI->first]=MI->second;
 471   }
 472
 473 #ifdef DEBUG_PATH_PROFILES
 474   cerr<<"size of deletions: "<<toErase.size()<<"\n";
 475   cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
 476 #endif
 477
 478 }
 479
 480 //Do graph processing: to determine minimal edge increments,
 481 //appropriate code insertions etc and insert the code at
 482 //appropriate locations
 483 void processGraph(Graph &g,
 484                   Instruction *rInst,
 485                   Instruction *countInst,
 486                   vector<Edge >& be,
 487                   vector<Edge >& stDummy,
 488                   vector<Edge >& exDummy,
 489                   int numPaths, int MethNo,
 490                   Value *threshold){
 491
 492   //Given a graph: with exit->root edge, do the following in seq:
 493   //1. get back edges
 494   //2. insert dummy edges and remove back edges
 495   //3. get edge assignments
 496   //4. Get Max spanning tree of graph:
 497   //   -Make graph g2=g undirectional
 498   //   -Get Max spanning tree t
 499   //   -Make t undirectional
 500   //   -remove edges from t not in graph g
 501   //5. Get edge increments
 502   //6. Get code insertions
 503   //7. move code on dummy edges over to the back edges
 504
 505
 506   //This is used as maximum "weight" for
 507   //priority queue
 508   //This would hold all
 509   //right as long as number of paths in the graph
 510   //is less than this
 511   const int Infinity=99999999;
 512
 513
 514   //step 1-3 are already done on the graph when this function is called
 515   DEBUG(printGraph(g));
 516
 517   //step 4: Get Max spanning tree of graph
 518
 519   //now insert exit to root edge
 520   //if its there earlier, remove it!
 521   //assign it weight Infinity
 522   //so that this edge IS ALWAYS IN spanning tree
 523   //Note than edges in spanning tree do not get
 524   //instrumented: and we do not want the
 525   //edge exit->root to get instrumented
 526   //as it MAY BE a dummy edge
 527   Edge ed(g.getExit(),g.getRoot(),Infinity);
 528   g.addEdge(ed,Infinity);
 529   Graph g2=g;
 530
 531   //make g2 undirectional: this gives a better
 532   //maximal spanning tree
 533   g2.makeUnDirectional();
 534   DEBUG(printGraph(g2));
 535
 536   Graph *t=g2.getMaxSpanningTree();
 537 #ifdef DEBUG_PATH_PROFILES
 538   std::cerr<<"Original maxspanning tree\n";
 539   printGraph(*t);
 540 #endif
 541   //now edges of tree t have weights reversed
 542   //(negative) because the algorithm used
 543   //to find max spanning tree is
 544   //actually for finding min spanning tree
 545   //so get back the original weights
 546   t->reverseWts();
 547
 548   //Ordinarily, the graph is directional
 549   //lets converts the graph into an
 550   //undirectional graph
 551   //This is done by adding an edge
 552   //v->u for all existing edges u->v
 553   t->makeUnDirectional();
 554
 555   //Given a tree t, and a "directed graph" g
 556   //replace the edges in the tree t with edges that exist in graph
 557   //The tree is formed from "undirectional" copy of graph
 558   //So whatever edges the tree has, the undirectional graph
 559   //would have too. This function corrects some of the directions in
 560   //the tree so that now, all edge directions in the tree match
 561   //the edge directions of corresponding edges in the directed graph
 562   removeTreeEdges(g, *t);
 563
 564 #ifdef DEBUG_PATH_PROFILES
 565   cerr<<"Final Spanning tree---------\n";
 566   printGraph(*t);
 567   cerr<<"-------end spanning tree\n";
 568 #endif
 569
 570   //now remove the exit->root node
 571   //and re-add it with weight 0
 572   //since infinite weight is kinda confusing
 573   g.removeEdge(ed);
 574   Edge edNew(g.getExit(), g.getRoot(),0);
 575   g.addEdge(edNew,0);
 576   if(t->hasEdge(ed)){
 577     t->removeEdge(ed);
 578     t->addEdge(edNew,0);
 579   }
 580
 581   DEBUG(printGraph(g);
 582         printGraph(*t));
 583
 584   //step 5: Get edge increments
 585
 586   //Now we select a subset of all edges
 587   //and assign them some values such that
 588   //if we consider just this subset, it still represents
 589   //the path sum along any path in the graph
 590
 591   map<Edge, int, EdgeCompare2> increment=getEdgeIncrements(g,*t, be);
 592 #ifdef DEBUG_PATH_PROFILES
 593   //print edge increments for debugging
 594   std::cerr<<"Edge Increments------\n";
 595   for(map<Edge, int, EdgeCompare2>::iterator MMI=increment.begin(), MME=increment.end(); MMI != MME; ++MMI){
 596     printEdge(MMI->first);
 597     std::cerr<<"Increment for above:"<<MMI->second<<"\n";
 598   }
 599   std::cerr<<"-------end of edge increments\n";
 600 #endif
 601
 602
 603   //step 6: Get code insertions
 604
 605   //Based on edgeIncrements (above), now obtain
 606   //the kind of code to be inserted along an edge
 607   //The idea here is to minimize the computation
 608   //by inserting only the needed code
 609   vector<Edge> chords;
 610   getChords(chords, g, *t);
 611
 612
 613   map<Edge, getEdgeCode *, EdgeCompare2> codeInsertions;
 614   getCodeInsertions(g, codeInsertions, chords,increment);
 615
 616 #ifdef DEBUG_PATH_PROFILES
 617   //print edges with code for debugging
 618   cerr<<"Code inserted in following---------------\n";
 619   for(map<Edge, getEdgeCode *, EdgeCompare2>::iterator cd_i=codeInsertions.begin(),
 620         cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
 621     printEdge(cd_i->first);
 622     cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
 623   }
 624   cerr<<"-----end insertions\n";
 625 #endif
 626
 627   //step 7: move code on dummy edges over to the back edges
 628
 629   //Move the incoming dummy edge code and outgoing dummy
 630   //edge code over to the corresponding back edge
 631
 632   moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
 633
 634 #ifdef DEBUG_PATH_PROFILES
 635   //debugging info
 636   cerr<<"After moving dummy code\n";
 637   for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
 638         cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
 639     printEdge(cd_i->first);
 640     cerr<<cd_i->second->getCond()<<":"
 641         <<cd_i->second->getInc()<<"\n";
 642   }
 643   cerr<<"Dummy end------------\n";
 644 #endif
 645
 646
 647   //see what it looks like...
 648   //now insert code along edges which have codes on them
 649   for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
 650         ME=codeInsertions.end(); MI!=ME; ++MI){
 651     Edge ed=MI->first;
 652     insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo, threshold);
 653   }
 654 }
 655
 656 //print the graph (for debugging)
 657 void printGraph(Graph &g){
 658   vector<Node *> lt=g.getAllNodes();
 659   cerr<<"Graph---------------------\n";
 660   for(vector<Node *>::iterator LI=lt.begin();
 661       LI!=lt.end(); ++LI){
 662     cerr<<((*LI)->getElement())->getName()<<"->";
 663     Graph::nodeList nl=g.getNodeList(*LI);
 664     for(Graph::nodeList::iterator NI=nl.begin();
 665         NI!=nl.end(); ++NI){
 666       cerr<<":"<<"("<<(NI->element->getElement())
 667         ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
 668           <<NI->randId<<")";
 669     }
 670     cerr<<"\n";
 671   }
 672   cerr<<"--------------------Graph\n";
 673 }