lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp

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