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/Transforms/Instrumentation/Graph.h"
  14 #include <algorithm>
  15 #include <iostream>
  16
  17 //using std::list;
  18 using std::map;
  19 using std::vector;
  20 using std::cerr;
  21
  22 //check if 2 edges are equal (same endpoints and same weight)
  23 static bool edgesEqual(Edge  ed1, Edge ed2){
  24   return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
  25 }
  26
  27 //Get the vector of edges that are to be instrumented in the graph
  28 static void getChords(vector<Edge > &chords, Graph &g, Graph st){
  29   //make sure the spanning tree is directional
  30   //iterate over ALL the edges of the graph
  31   vector<Node *> allNodes=g.getAllNodes();
  32   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
  33       ++NI){
  34     Graph::nodeList node_list=g.getNodeList(*NI);
  35     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
  36         NLI!=NLE; ++NLI){
  37       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
  38       if(!(st.hasEdgeAndWt(f)))//addnl
  39         chords.push_back(f);
  40     }
  41   }
  42 }
  43
  44 //Given a tree t, and a "directed graph" g
  45 //replace the edges in the tree t with edges that exist in graph
  46 //The tree is formed from "undirectional" copy of graph
  47 //So whatever edges the tree has, the undirectional graph
  48 //would have too. This function corrects some of the directions in
  49 //the tree so that now, all edge directions in the tree match
  50 //the edge directions of corresponding edges in the directed graph
  51 static void removeTreeEdges(Graph &g, Graph& t){
  52   vector<Node* > allNodes=t.getAllNodes();
  53   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
  54       ++NI){
  55     Graph::nodeList nl=t.getNodeList(*NI);
  56     for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
  57       Edge ed(NLI->element, *NI, NLI->weight);
  58       //if(!g.hasEdge(ed)) t.removeEdge(ed);
  59       if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
  60       //between any pair of vertices, so no need to delete by edge wt
  61     }
  62   }
  63 }
  64
  65 //Assign a value to all the edges in the graph
  66 //such that if we traverse along any path from root to exit, and
  67 //add up the edge values, we get a path number that uniquely
  68 //refers to the path we travelled
  69 int valueAssignmentToEdges(Graph& g){
  70   vector<Node *> revtop=g.reverseTopologicalSort();
  71   /*
  72   std::cerr<<"-----------Reverse topological sort\n";
  73   for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
  74     std::cerr<<(*RI)->getElement()->getName()<<":";
  75   }
  76   std::cerr<<"\n----------------------"<<std::endl;
  77   */
  78   map<Node *,int > NumPaths;
  79   for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
  80     if(g.isLeaf(*RI))
  81       NumPaths[*RI]=1;
  82     else{
  83       NumPaths[*RI]=0;
  84       /////
  85       Graph::nodeList &nlist=g.getNodeList(*RI);
  86       //sort nodelist by increasing order of numpaths
  87
  88       int sz=nlist.size();
  89       for(int i=0;i<sz-1; i++){
  90         int min=i;
  91         for(int j=i+1; j<sz; j++)
  92           if(NumPaths[nlist[j].element]<NumPaths[nlist[min].element]) min=j;
  93
  94         graphListElement tempEl=nlist[min];
  95         nlist[min]=nlist[i];
  96         nlist[i]=tempEl;
  97       }
  98       //sorted now!
  99
 100       for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
 101           GLI!=GLE; ++GLI){
 102         GLI->weight=NumPaths[*RI];
 103         NumPaths[*RI]+=NumPaths[GLI->element];
 104       }
 105     }
 106   }
 107   return NumPaths[g.getRoot()];
 108 }
 109
 110 //This is a helper function to get the edge increments
 111 //This is used in conjuntion with inc_DFS
 112 //to get the edge increments
 113 //Edge increment implies assigning a value to all the edges in the graph
 114 //such that if we traverse along any path from root to exit, and
 115 //add up the edge values, we get a path number that uniquely
 116 //refers to the path we travelled
 117 //inc_Dir tells whether 2 edges are in same, or in different directions
 118 //if same direction, return 1, else -1
 119 static int inc_Dir(Edge e, Edge f){
 120  if(e.isNull())
 121     return 1;
 122
 123  //check that the edges must have atleast one common endpoint
 124   assert(*(e.getFirst())==*(f.getFirst()) ||
 125          *(e.getFirst())==*(f.getSecond()) ||
 126          *(e.getSecond())==*(f.getFirst()) ||
 127          *(e.getSecond())==*(f.getSecond()));
 128
 129   if(*(e.getFirst())==*(f.getSecond()) ||
 130      *(e.getSecond())==*(f.getFirst()))
 131     return 1;
 132
 133   return -1;
 134 }
 135
 136
 137 //used for getting edge increments (read comments above in inc_Dir)
 138 //inc_DFS is a modification of DFS
 139 static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare>& Increment,
 140              int events, Node *v, Edge e){
 141
 142   vector<Node *> allNodes=t.getAllNodes();
 143
 144
 145   //cerr<<"Called for\n";
 146   //if(!e.isNull())
 147   //printEdge(e);
 148
 149
 150   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 151       ++NI){
 152     Graph::nodeList node_list=t.getNodeList(*NI);
 153     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 154         NLI!= NLE; ++NLI){
 155       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
 156       if(!edgesEqual(f,e) && *v==*(f.getSecond())){
 157         int dir_count=inc_Dir(e,f);
 158         int wt=1*f.getWeight();
 159         inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
 160       }
 161     }
 162   }
 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.getFirst())){
 171         int dir_count=inc_Dir(e,f);
 172         int wt=f.getWeight();
 173         inc_DFS(g,t, Increment, dir_count*events+wt,
 174                 f.getSecond(), f);
 175       }
 176     }
 177   }
 178
 179   allNodes=g.getAllNodes();
 180   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 181       ++NI){
 182     Graph::nodeList node_list=g.getNodeList(*NI);
 183     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 184         NLI!=NLE; ++NLI){
 185       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
 186       if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
 187                                   *v==*(f.getFirst()))){
 188         int dir_count=inc_Dir(e,f);
 189         Increment[f]+=dir_count*events;
 190         //cerr<<"assigned "<<Increment[f]<<" to"<<endl;
 191         //printEdge(f);
 192       }
 193     }
 194   }
 195 }
 196
 197 //Now we select a subset of all edges
 198 //and assign them some values such that
 199 //if we consider just this subset, it still represents
 200 //the path sum along any path in the graph
 201 static map<Edge, int, EdgeCompare> getEdgeIncrements(Graph& g, Graph& t){
 202   //get all edges in g-t
 203   map<Edge, int, EdgeCompare> Increment;
 204
 205   vector<Node *> allNodes=g.getAllNodes();
 206
 207   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 208       ++NI){
 209     Graph::nodeList node_list=g.getNodeList(*NI);
 210     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 211         NLI!=NLE; ++NLI){
 212       Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
 213       if(!(t.hasEdgeAndWt(ed))){
 214         Increment[ed]=0;;
 215       }
 216     }
 217   }
 218
 219   Edge *ed=new Edge();
 220   inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
 221
 222   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
 223       ++NI){
 224     Graph::nodeList node_list=g.getNodeList(*NI);
 225     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
 226         NLI!=NLE; ++NLI){
 227       Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
 228       if(!(t.hasEdgeAndWt(ed))){
 229         int wt=ed.getWeight();
 230         Increment[ed]+=wt;
 231       }
 232     }
 233   }
 234
 235   return Increment;
 236 }
 237
 238 //push it up: TODO
 239 const graphListElement *findNodeInList(const Graph::nodeList &NL,
 240                                               Node *N);
 241
 242 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
 243 //end TODO
 244
 245 //Based on edgeIncrements (above), now obtain
 246 //the kind of code to be inserted along an edge
 247 //The idea here is to minimize the computation
 248 //by inserting only the needed code
 249 static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare> &instr,
 250                               vector<Edge > &chords,
 251                               map<Edge,int, EdgeCompare> &edIncrements){
 252
 253   //Register initialization code
 254   vector<Node *> ws;
 255   ws.push_back(g.getRoot());
 256   while(ws.size()>0){
 257     Node *v=ws.back();
 258     ws.pop_back();
 259     //for each edge v->w
 260     Graph::nodeList succs=g.getNodeList(v);
 261
 262     for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
 263         nl!=ne; ++nl){
 264       int edgeWt=nl->weight;
 265       Node *w=nl->element;
 266       //if chords has v->w
 267       Edge ed(v,w, edgeWt, nl->randId);
 268       //cerr<<"Assign:\n";
 269       //printEdge(ed);
 270       bool hasEdge=false;
 271       for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
 272           CI!=CE && !hasEdge;++CI){
 273         if(*CI==ed && CI->getWeight()==edgeWt){//modf
 274           hasEdge=true;
 275         }
 276       }
 277
 278       if(hasEdge){//so its a chord edge
 279         getEdgeCode *edCd=new getEdgeCode();
 280         edCd->setCond(1);
 281         edCd->setInc(edIncrements[ed]);
 282         instr[ed]=edCd;
 283         //std::cerr<<"Case 1\n";
 284       }
 285       else if(g.getNumberOfIncomingEdges(w)==1){
 286         ws.push_back(w);
 287         //std::cerr<<"Added w\n";
 288       }
 289       else{
 290         getEdgeCode *edCd=new getEdgeCode();
 291         edCd->setCond(2);
 292         edCd->setInc(0);
 293         instr[ed]=edCd;
 294         //std::cerr<<"Case 2\n";
 295       }
 296     }
 297   }
 298
 299   /////Memory increment code
 300   ws.push_back(g.getExit());
 301
 302   while(!ws.empty()) {
 303     Node *w=ws.back();
 304     ws.pop_back();
 305
 306
 307     ///////
 308     //vector<Node *> lt;
 309     vector<Node *> lllt=g.getAllNodes();
 310     for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
 311       Node *lnode=*EII;
 312       Graph::nodeList &nl = g.getNodeList(lnode);
 313       //cerr<<"Size:"<<lllt.size()<<"\n";
 314       //cerr<<lnode->getElement()->getName()<<"\n";
 315       graphListElement *N = findNodeInList(nl, w);
 316       if (N){// lt.push_back(lnode);
 317
 318         //Node *v=*pd;
 319         //Node *v=N->element;
 320         Node *v=lnode;
 321         //if chords has v->w
 322
 323         Edge ed(v,w, N->weight, N->randId);
 324         getEdgeCode *edCd=new getEdgeCode();
 325         bool hasEdge=false;
 326         for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
 327             ++CI){
 328           if(*CI==ed && CI->getWeight()==N->weight){
 329             hasEdge=true;
 330             break;
 331           }
 332         }
 333         if(hasEdge){
 334           char str[100];
 335           if(instr[ed]!=NULL && instr[ed]->getCond()==1){
 336             instr[ed]->setCond(4);
 337           }
 338           else{
 339             edCd->setCond(5);
 340             edCd->setInc(edIncrements[ed]);
 341             instr[ed]=edCd;
 342           }
 343
 344         }
 345         else if(g.getNumberOfOutgoingEdges(v)==1)
 346           ws.push_back(v);
 347         else{
 348           edCd->setCond(6);
 349           instr[ed]=edCd;
 350         }
 351       }
 352     }
 353   }
 354   ///// Register increment code
 355   for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
 356     getEdgeCode *edCd=new getEdgeCode();
 357     if(instr[*CI]==NULL){
 358       edCd->setCond(3);
 359       edCd->setInc(edIncrements[*CI]);
 360       instr[*CI]=edCd;
 361     }
 362   }
 363 }
 364
 365 //Add dummy edges corresponding to the back edges
 366 //If a->b is a backedge
 367 //then incoming dummy edge is root->b
 368 //and outgoing dummy edge is a->exit
 369 //changed
 370 void addDummyEdges(vector<Edge > &stDummy,
 371                    vector<Edge > &exDummy,
 372                    Graph &g, vector<Edge> &be){
 373   for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
 374     Edge ed=*VI;
 375     Node *first=ed.getFirst();
 376     Node *second=ed.getSecond();
 377     g.removeEdge(ed);
 378
 379     if(!(*second==*(g.getRoot()))){
 380       Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
 381       stDummy.push_back(*st);
 382       g.addEdgeForce(*st);
 383     }
 384
 385     if(!(*first==*(g.getExit()))){
 386       Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
 387       exDummy.push_back(*ex);
 388       g.addEdgeForce(*ex);
 389     }
 390   }
 391 }
 392
 393 //print a given edge in the form BB1Label->BB2Label
 394 void printEdge(Edge ed){
 395   cerr<<((ed.getFirst())->getElement())
 396     ->getName()<<"->"<<((ed.getSecond())
 397                           ->getElement())->getName()<<
 398     ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
 399 }
 400
 401 //Move the incoming dummy edge code and outgoing dummy
 402 //edge code over to the corresponding back edge
 403 static void moveDummyCode(vector<Edge> &stDummy,
 404                           vector<Edge> &exDummy,
 405                           vector<Edge> &be,
 406                           map<Edge, getEdgeCode *, EdgeCompare> &insertions,
 407                           Graph &g){
 408   typedef vector<Edge >::iterator vec_iter;
 409
 410   map<Edge,getEdgeCode *, EdgeCompare> temp;
 411   //iterate over edges with code
 412   std::vector<Edge> toErase;
 413   for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=insertions.begin(),
 414         ME=insertions.end(); MI!=ME; ++MI){
 415     Edge ed=MI->first;
 416     getEdgeCode *edCd=MI->second;
 417
 418     ///---new code
 419     //iterate over be, and check if its starts and end vertices hv code
 420     for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
 421       if(ed.getRandId()==BEI->getRandId()){
 422
 423         //cerr<<"Looking at edge--------\n";
 424         //printEdge(ed);
 425
 426         if(temp[*BEI]==0)
 427           temp[*BEI]=new getEdgeCode();
 428
 429         //so ed is either in st, or ex!
 430         if(ed.getFirst()==g.getRoot()){
 431           //so its in stDummy
 432           temp[*BEI]->setCdIn(edCd);
 433           toErase.push_back(ed);
 434         }
 435         else if(ed.getSecond()==g.getExit()){
 436           //so its in exDummy
 437           toErase.push_back(ed);
 438           temp[*BEI]->setCdOut(edCd);
 439         }
 440         else{
 441           assert(false && "Not found in either start or end! Rand failed?");
 442         }
 443       }
 444     }
 445   }
 446
 447   for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
 448       ++vmi){
 449     insertions.erase(*vmi);
 450     //cerr<<"Erasing from insertion\n";
 451     //printEdge(*vmi);
 452     g.removeEdgeWithWt(*vmi);
 453   }
 454
 455   for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=temp.begin(),
 456       ME=temp.end(); MI!=ME; ++MI){
 457     insertions[MI->first]=MI->second;
 458     //cerr<<"inserting into insertion-----\n";
 459     //printEdge(MI->first);
 460   }
 461   //cerr<<"----\n";
 462
 463   /*
 464     ///---new code end
 465     bool dummyHasIt=false;
 466
 467     DEBUG(cerr<<"Current edge considered---\n";
 468           printEdge(ed));
 469
 470     //now check if stDummy has ed
 471     for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt;
 472         ++VI){
 473       if(*VI==ed){
 474         //#ifdef DEBUG_PATH_PROFILES
 475         cerr<<"Edge matched with stDummy\n";
 476         printEdge(ed);
 477         //#endif
 478         dummyHasIt=true;
 479         bool dummyInBe=false;
 480         //dummy edge with code
 481         for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe; ++BE){
 482           Edge backEdge=*BE;
 483           Node *st=backEdge.getSecond();
 484           Node *dm=ed.getSecond();
 485           if(*dm==*st){
 486             //so this is the back edge to use
 487             //#ifdef DEBUG_PATH_PROFILES
 488             cerr<<"Moving to backedge\n";
 489             printEdge(backEdge);
 490             //#endif
 491             getEdgeCode *ged=new getEdgeCode();
 492             ged->setCdIn(edCd);
 493             toErase.push_back(ed);//MI);//ed);
 494             insertions[backEdge]=ged;
 495             dummyInBe=true;
 496           }
 497         }
 498         assert(dummyInBe);
 499         //modf
 500         //new
 501         //vec_iter VII=VI;
 502         stDummy.erase(VI);
 503         break;
 504         //end new
 505       }
 506     }
 507     if(!dummyHasIt){
 508       //so exDummy may hv it
 509       bool inExDummy=false;
 510       for(vec_iter VI=exDummy.begin(), VE=exDummy.end(); VI!=VE && !inExDummy;
 511           ++VI){
 512         if(*VI==ed){
 513           inExDummy=true;
 514
 515           //#ifdef DEBUG_PATH_PROFILES
 516           cerr<<"Edge matched with exDummy\n";
 517           //#endif
 518           bool dummyInBe2=false;
 519           //dummy edge with code
 520           for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe2;
 521               ++BE){
 522             Edge backEdge=*BE;
 523             Node *st=backEdge.getFirst();
 524             Node *dm=ed.getFirst();
 525             if(*dm==*st){
 526               //so this is the back edge to use
 527               cerr<<"Moving to backedge\n";
 528               printEdge(backEdge);
 529               getEdgeCode *ged;
 530               if(insertions[backEdge]==NULL)
 531                 ged=new getEdgeCode();
 532               else
 533                 ged=insertions[backEdge];
 534               toErase.push_back(ed);//MI);//ed);
 535               ged->setCdOut(edCd);
 536               insertions[backEdge]=ged;
 537               dummyInBe2=true;
 538             }
 539           }
 540           assert(dummyInBe2);
 541           //modf
 542           //vec_iter VII=VI;
 543           exDummy.erase(VI);
 544           break;
 545           //end
 546         }
 547       }
 548     }
 549   }
 550
 551   */
 552 #ifdef DEBUG_PATH_PROFILES
 553   cerr<<"size of deletions: "<<toErase.size()<<"\n";
 554 #endif
 555
 556   /*
 557   for(vector<map<Edge, getEdgeCode *>::iterator>::iterator
 558         vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; ++vmi)
 559
 560     insertions.erase(*vmi);
 561   */
 562 #ifdef DEBUG_PATH_PROFILES
 563   cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
 564 #endif
 565
 566 }
 567
 568 //Do graph processing: to determine minimal edge increments,
 569 //appropriate code insertions etc and insert the code at
 570 //appropriate locations
 571 void processGraph(Graph &g,
 572                   Instruction *rInst,
 573                   Instruction *countInst,
 574                   vector<Edge >& be,
 575                   vector<Edge >& stDummy,
 576                   vector<Edge >& exDummy,
 577                   int numPaths){
 578
 579   static int MethNo=0;
 580   MethNo++;
 581   //Given a graph: with exit->root edge, do the following in seq:
 582   //1. get back edges
 583   //2. insert dummy edges and remove back edges
 584   //3. get edge assignments
 585   //4. Get Max spanning tree of graph:
 586   //   -Make graph g2=g undirectional
 587   //   -Get Max spanning tree t
 588   //   -Make t undirectional
 589   //   -remove edges from t not in graph g
 590   //5. Get edge increments
 591   //6. Get code insertions
 592   //7. move code on dummy edges over to the back edges
 593
 594
 595   //This is used as maximum "weight" for
 596   //priority queue
 597   //This would hold all
 598   //right as long as number of paths in the graph
 599   //is less than this
 600   const int INFINITY=99999999;
 601
 602
 603   //step 1-3 are already done on the graph when this function is called
 604   DEBUG(printGraph(g));
 605
 606   //step 4: Get Max spanning tree of graph
 607
 608   //now insert exit to root edge
 609   //if its there earlier, remove it!
 610   //assign it weight INFINITY
 611   //so that this edge IS ALWAYS IN spanning tree
 612   //Note than edges in spanning tree do not get
 613   //instrumented: and we do not want the
 614   //edge exit->root to get instrumented
 615   //as it MAY BE a dummy edge
 616   Edge ed(g.getExit(),g.getRoot(),INFINITY);
 617   g.addEdge(ed,INFINITY);
 618   Graph g2=g;
 619
 620   //make g2 undirectional: this gives a better
 621   //maximal spanning tree
 622   g2.makeUnDirectional();
 623   DEBUG(printGraph(g2));
 624
 625   Graph *t=g2.getMaxSpanningTree();
 626   //#ifdef DEBUG_PATH_PROFILES
 627   //cerr<<"Original maxspanning tree\n";
 628   //printGraph(*t);
 629   //#endif
 630   //now edges of tree t have weights reversed
 631   //(negative) because the algorithm used
 632   //to find max spanning tree is
 633   //actually for finding min spanning tree
 634   //so get back the original weights
 635   t->reverseWts();
 636
 637   //Ordinarily, the graph is directional
 638   //lets converts the graph into an
 639   //undirectional graph
 640   //This is done by adding an edge
 641   //v->u for all existing edges u->v
 642   t->makeUnDirectional();
 643
 644   //Given a tree t, and a "directed graph" g
 645   //replace the edges in the tree t with edges that exist in graph
 646   //The tree is formed from "undirectional" copy of graph
 647   //So whatever edges the tree has, the undirectional graph
 648   //would have too. This function corrects some of the directions in
 649   //the tree so that now, all edge directions in the tree match
 650   //the edge directions of corresponding edges in the directed graph
 651   removeTreeEdges(g, *t);
 652
 653 #ifdef DEBUG_PATH_PROFILES
 654   cerr<<"Final Spanning tree---------\n";
 655   printGraph(*t);
 656   cerr<<"-------end spanning tree\n";
 657 #endif
 658
 659   //now remove the exit->root node
 660   //and re-add it with weight 0
 661   //since infinite weight is kinda confusing
 662   g.removeEdge(ed);
 663   Edge edNew(g.getExit(), g.getRoot(),0);
 664   g.addEdge(edNew,0);
 665   if(t->hasEdge(ed)){
 666     t->removeEdge(ed);
 667     t->addEdge(edNew,0);
 668   }
 669
 670   DEBUG(printGraph(g);
 671         printGraph(*t));
 672
 673   //step 5: Get edge increments
 674
 675   //Now we select a subset of all edges
 676   //and assign them some values such that
 677   //if we consider just this subset, it still represents
 678   //the path sum along any path in the graph
 679
 680   map<Edge, int, EdgeCompare> increment=getEdgeIncrements(g,*t);
 681 #ifdef DEBUG_PATH_PROFILES
 682   //print edge increments for debugging
 683
 684   for(map<Edge, int, EdgeCompare>::iterator M_I=increment.begin(), M_E=increment.end();
 685       M_I!=M_E; ++M_I){
 686     printEdge(M_I->first);
 687     cerr<<"Increment for above:"<<M_I->second<<"\n";
 688   }
 689 #endif
 690
 691
 692   //step 6: Get code insertions
 693
 694   //Based on edgeIncrements (above), now obtain
 695   //the kind of code to be inserted along an edge
 696   //The idea here is to minimize the computation
 697   //by inserting only the needed code
 698   vector<Edge> chords;
 699   getChords(chords, g, *t);
 700
 701
 702   //cerr<<"Graph before getCodeInsertion:\n";
 703   //printGraph(g);
 704   map<Edge, getEdgeCode *, EdgeCompare> codeInsertions;
 705   getCodeInsertions(g, codeInsertions, chords,increment);
 706
 707 #ifdef DEBUG_PATH_PROFILES
 708   //print edges with code for debugging
 709   cerr<<"Code inserted in following---------------\n";
 710   for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
 711         cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
 712     printEdge(cd_i->first);
 713     cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
 714   }
 715   cerr<<"-----end insertions\n";
 716 #endif
 717
 718   //step 7: move code on dummy edges over to the back edges
 719
 720   //Move the incoming dummy edge code and outgoing dummy
 721   //edge code over to the corresponding back edge
 722
 723   moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
 724   //cerr<<"After dummy removals\n";
 725   //printGraph(g);
 726
 727 #ifdef DEBUG_PATH_PROFILES
 728   //debugging info
 729   cerr<<"After moving dummy code\n";
 730   for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
 731         cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
 732     printEdge(cd_i->first);
 733     cerr<<cd_i->second->getCond()<<":"
 734         <<cd_i->second->getInc()<<"\n";
 735   }
 736   cerr<<"Dummy end------------\n";
 737 #endif
 738
 739
 740   //see what it looks like...
 741   //now insert code along edges which have codes on them
 742   for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
 743         ME=codeInsertions.end(); MI!=ME; ++MI){
 744     Edge ed=MI->first;
 745     insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo);
 746   }
 747 }
 748
 749
 750
 751 //print the graph (for debugging)
 752 void printGraph(Graph &g){
 753   vector<Node *> lt=g.getAllNodes();
 754   cerr<<"Graph---------------------\n";
 755   for(vector<Node *>::iterator LI=lt.begin();
 756       LI!=lt.end(); ++LI){
 757     cerr<<((*LI)->getElement())->getName()<<"->";
 758     Graph::nodeList nl=g.getNodeList(*LI);
 759     for(Graph::nodeList::iterator NI=nl.begin();
 760         NI!=nl.end(); ++NI){
 761       cerr<<":"<<"("<<(NI->element->getElement())
 762         ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
 763           <<NI->randId<<")";
 764     }
 765     cerr<<"\n";
 766   }
 767   cerr<<"--------------------Graph\n";
 768 }
 769
 770
 771 /*
 772 ////////// Getting back BBs from path number
 773
 774 #include "llvm/Constants.h"
 775 #include "llvm/DerivedTypes.h"
 776 #include "llvm/iMemory.h"
 777 #include "llvm/iTerminators.h"
 778 #include "llvm/iOther.h"
 779 #include "llvm/iOperators.h"
 780
 781 #include "llvm/Support/CFG.h"
 782 #include "llvm/BasicBlock.h"
 783 #include "llvm/Pass.h"
 784
 785 void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph g,
 786                     vector<Edge> &stDummy, vector<Edge> &exDummy, vector<Edge> &be,
 787                     double strand){
 788   Graph::nodeList nlist=g.getNodeList(n);
 789   int maxCount=-9999999;
 790   bool isStart=false;
 791
 792   if(*n==*g.getRoot())//its root: so first node of path
 793     isStart=true;
 794
 795   double edgeRnd=0;
 796   Node *nextRoot=n;
 797   for(Graph::nodeList::iterator NLI=nlist.begin(), NLE=nlist.end(); NLI!=NLE;
 798       ++NLI){
 799     //cerr<<"Saw:"<<NLI->weight<<endl;
 800     if(NLI->weight>maxCount && NLI->weight<=pathNo){
 801       maxCount=NLI->weight;
 802       nextRoot=NLI->element;
 803       edgeRnd=NLI->randId;
 804       if(isStart)
 805         strand=NLI->randId;
 806     }
 807   }
 808   //cerr<<"Max:"<<maxCount<<endl;
 809
 810   if(!isStart)
 811     assert(strand!=-1 && "strand not assigned!");
 812
 813   assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go");
 814   assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit");
 815
 816   vBB.push_back(n->getElement());
 817
 818   if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){
 819
 820     //look for strnd and edgeRnd now:
 821     bool has1=false, has2=false;
 822     //check if exit has it
 823     for(vector<Edge>::iterator VI=exDummy.begin(), VE=exDummy.end(); VI!=VE;
 824         ++VI){
 825       if(VI->getRandId()==edgeRnd){
 826         has2=true;
 827         //cerr<<"has2: looking at"<<std::endl;
 828         //printEdge(*VI);
 829         break;
 830       }
 831     }
 832
 833     //check if start has it
 834     for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE;
 835         ++VI){
 836       if(VI->getRandId()==strand){
 837         //cerr<<"has1: looking at"<<std::endl;
 838         //printEdge(*VI);
 839         has1=true;
 840         break;
 841       }
 842     }
 843
 844     if(has1){
 845       //find backedge with endpoint vBB[1]
 846       for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
 847         assert(vBB.size()>0 && "vector too small");
 848         if( VI->getSecond()->getElement() == vBB[1] ){
 849           vBB[0]=VI->getFirst()->getElement();
 850           break;
 851         }
 852       }
 853     }
 854
 855     if(has2){
 856       //find backedge with startpoint vBB[vBB.size()-1]
 857       for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
 858         assert(vBB.size()>0 && "vector too small");
 859         if( VI->getFirst()->getElement() == vBB[vBB.size()-1] ){
 860           //if(vBB[0]==VI->getFirst()->getElement())
 861           //vBB.erase(vBB.begin()+vBB.size()-1);
 862           //else
 863           vBB.push_back(VI->getSecond()->getElement());
 864           break;
 865         }
 866       }
 867     }
 868     else
 869       vBB.push_back(nextRoot->getElement());
 870
 871     return;
 872   }
 873
 874   assert(pathNo-maxCount>=0);
 875
 876   return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy,
 877                         exDummy, be, strand);
 878 }
 879
 880
 881 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
 882   for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
 883     if(((*si)->getElement())==BB){
 884       return *si;
 885     }
 886   }
 887   return NULL;
 888 }
 889
 890 void getBBtrace(vector<BasicBlock *> &vBB, int pathNo, Function *M){
 891
 892   //step 1: create graph
 893   //Transform the cfg s.t. we have just one exit node
 894
 895   std::vector<Node *> nodes;
 896   std::vector<Edge> edges;
 897   Node *tmp;
 898   Node *exitNode=0, *startNode=0;
 899
 900   BasicBlock *ExitNode = 0;
 901   for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I) {
 902     BasicBlock *BB = *I;
 903     if (isa<ReturnInst>(BB->getTerminator())) {
 904       ExitNode = BB;
 905       break;
 906     }
 907   }
 908
 909   assert(ExitNode!=0 && "exitnode not found");
 910
 911   //iterating over BBs and making graph
 912   //The nodes must be uniquesly identified:
 913   //That is, no two nodes must hav same BB*
 914
 915   //First enter just nodes: later enter edges
 916   for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
 917     Node *nd=new Node(*BB);
 918     nodes.push_back(nd);
 919     if(*BB==ExitNode)
 920       exitNode=nd;
 921     if(*BB==M->front())
 922       startNode=nd;
 923   }
 924
 925   assert(exitNode!=0 && startNode!=0 && "Start or exit not found!");
 926
 927   for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
 928     Node *nd=findBB(nodes, *BB);
 929     assert(nd && "No node for this edge!");
 930
 931     for(BasicBlock::succ_iterator s=succ_begin(*BB), se=succ_end(*BB);
 932         s!=se; ++s){
 933       Node *nd2=findBB(nodes,*s);
 934       assert(nd2 && "No node for this edge!");
 935       Edge ed(nd,nd2,0);
 936       edges.push_back(ed);
 937     }
 938   }
 939
 940   static bool printed=false;
 941   Graph g(nodes,edges, startNode, exitNode);
 942
 943   //if(!printed)
 944   //printGraph(g);
 945
 946   if (M->getBasicBlocks().size() <= 1) return; //uninstrumented
 947
 948   //step 2: getBackEdges
 949   vector<Edge> be;
 950   g.getBackEdges(be);
 951
 952   //cerr<<"BackEdges\n";
 953   //for(vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
 954     //printEdge(*VI);
 955     //cerr<<"\n";
 956   //}
 957   //cerr<<"------\n";
 958   //step 3: add dummy edges
 959   vector<Edge> stDummy;
 960   vector<Edge> exDummy;
 961   addDummyEdges(stDummy, exDummy, g, be);
 962
 963   //cerr<<"After adding dummy edges\n";
 964   //printGraph(g);
 965
 966   //step 4: value assgn to edges
 967   int numPaths=valueAssignmentToEdges(g);
 968
 969   //if(!printed){
 970   //printGraph(g);
 971   //printed=true;
 972   //}
 973
 974   //step 5: now travel from root, select max(edge) < pathNo,
 975   //and go on until reach the exit
 976   return getPathFrmNode(g.getRoot(), vBB, pathNo, g, stDummy, exDummy, be, -1);
 977 }
 978
 979 */