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