lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp

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