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