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