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