lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp

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