lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp

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