LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

GraphAuxiliary.cpp

Go to the documentation of this file.
00001 //===- GraphAuxiliary.cpp - Auxiliary functions on graph ------------------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // auxiliary function associated with graph: they all operate on graph, and help
00011 // in inserting instrumentation for trace generation
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Pass.h"
00016 #include "llvm/Module.h"
00017 #include "llvm/Instructions.h"
00018 #include "llvm/Support/Debug.h"
00019 #include <algorithm>
00020 #include "Graph.h"
00021 
00022 //using std::list;
00023 using std::map;
00024 using std::vector;
00025 using std::cerr;
00026 
00027 namespace llvm {
00028 
00029 //check if 2 edges are equal (same endpoints and same weight)
00030 static bool edgesEqual(Edge  ed1, Edge ed2){
00031   return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
00032 }
00033 
00034 //Get the vector of edges that are to be instrumented in the graph
00035 static void getChords(vector<Edge > &chords, Graph &g, Graph st){
00036   //make sure the spanning tree is directional
00037   //iterate over ALL the edges of the graph
00038   vector<Node *> allNodes=g.getAllNodes();
00039   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
00040       ++NI){
00041     Graph::nodeList node_list=g.getNodeList(*NI);
00042     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
00043   NLI!=NLE; ++NLI){
00044       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
00045       if(!(st.hasEdgeAndWt(f)))//addnl
00046   chords.push_back(f);
00047     }
00048   }
00049 }
00050 
00051 //Given a tree t, and a "directed graph" g
00052 //replace the edges in the tree t with edges that exist in graph
00053 //The tree is formed from "undirectional" copy of graph
00054 //So whatever edges the tree has, the undirectional graph 
00055 //would have too. This function corrects some of the directions in 
00056 //the tree so that now, all edge directions in the tree match
00057 //the edge directions of corresponding edges in the directed graph
00058 static void removeTreeEdges(Graph &g, Graph& t){
00059   vector<Node* > allNodes=t.getAllNodes();
00060   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
00061       ++NI){
00062     Graph::nodeList nl=t.getNodeList(*NI);
00063     for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
00064       Edge ed(NLI->element, *NI, NLI->weight);
00065       if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
00066       //between any pair of vertices, so no need to delete by edge wt
00067     }
00068   }
00069 }
00070 
00071 //Assign a value to all the edges in the graph
00072 //such that if we traverse along any path from root to exit, and
00073 //add up the edge values, we get a path number that uniquely
00074 //refers to the path we travelled
00075 int valueAssignmentToEdges(Graph& g,  map<Node *, int> nodePriority, 
00076                            vector<Edge> &be){
00077   vector<Node *> revtop=g.reverseTopologicalSort();
00078   map<Node *,int > NumPaths;
00079   for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); 
00080       RI!=RE; ++RI){
00081     if(g.isLeaf(*RI))
00082       NumPaths[*RI]=1;
00083     else{
00084       NumPaths[*RI]=0;
00085 
00086       // Modified Graph::nodeList &nlist=g.getNodeList(*RI);
00087       Graph::nodeList &nlist=g.getSortedNodeList(*RI, be);
00088 
00089       //sort nodelist by increasing order of numpaths
00090       
00091       int sz=nlist.size();
00092       
00093       for(int i=0;i<sz-1; i++){
00094   int min=i;
00095   for(int j=i+1; j<sz; j++){
00096           BasicBlock *bb1 = nlist[j].element->getElement();
00097           BasicBlock *bb2 = nlist[min].element->getElement();
00098           
00099           if(bb1 == bb2) continue;
00100           
00101           if(*RI == g.getRoot()){
00102             assert(nodePriority[nlist[min].element]!= 
00103                    nodePriority[nlist[j].element] 
00104                    && "priorities can't be same!");
00105             
00106             if(nodePriority[nlist[j].element] < 
00107                nodePriority[nlist[min].element])
00108               min = j; 
00109           }
00110 
00111           else{
00112             TerminatorInst *tti = (*RI)->getElement()->getTerminator();
00113             
00114             BranchInst *ti =  cast<BranchInst>(tti);
00115             assert(ti && "not a branch");
00116             assert(ti->getNumSuccessors()==2 && "less successors!");
00117             
00118             BasicBlock *tB = ti->getSuccessor(0);
00119             BasicBlock *fB = ti->getSuccessor(1);
00120             
00121             if(tB == bb1 || fB == bb2)
00122               min = j;
00123           }
00124           
00125         }
00126   graphListElement tempEl=nlist[min];
00127   nlist[min]=nlist[i];
00128   nlist[i]=tempEl;
00129       }
00130       
00131       //sorted now!
00132       for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
00133     GLI!=GLE; ++GLI){
00134         GLI->weight=NumPaths[*RI];
00135   NumPaths[*RI]+=NumPaths[GLI->element];
00136       }
00137     }
00138   }
00139   return NumPaths[g.getRoot()];
00140 }
00141 
00142 //This is a helper function to get the edge increments
00143 //This is used in conjunction with inc_DFS
00144 //to get the edge increments
00145 //Edge increment implies assigning a value to all the edges in the graph
00146 //such that if we traverse along any path from root to exit, and
00147 //add up the edge values, we get a path number that uniquely
00148 //refers to the path we travelled
00149 //inc_Dir tells whether 2 edges are in same, or in different directions
00150 //if same direction, return 1, else -1
00151 static int inc_Dir(Edge e, Edge f){ 
00152  if(e.isNull()) 
00153     return 1;
00154  
00155  //check that the edges must have at least one common endpoint
00156   assert(*(e.getFirst())==*(f.getFirst()) ||
00157    *(e.getFirst())==*(f.getSecond()) || 
00158    *(e.getSecond())==*(f.getFirst()) ||
00159    *(e.getSecond())==*(f.getSecond()));
00160 
00161   if(*(e.getFirst())==*(f.getSecond()) || 
00162      *(e.getSecond())==*(f.getFirst()))
00163     return 1;
00164   
00165   return -1;
00166 }
00167 
00168 
00169 //used for getting edge increments (read comments above in inc_Dir)
00170 //inc_DFS is a modification of DFS 
00171 static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare2>& Increment, 
00172        int events, Node *v, Edge e){
00173   
00174   vector<Node *> allNodes=t.getAllNodes();
00175 
00176   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
00177       ++NI){
00178     Graph::nodeList node_list=t.getNodeList(*NI);
00179     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
00180   NLI!= NLE; ++NLI){
00181       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
00182       if(!edgesEqual(f,e) && *v==*(f.getSecond())){
00183   int dir_count=inc_Dir(e,f);
00184   int wt=1*f.getWeight();
00185   inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
00186       }
00187     }
00188   }
00189 
00190   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
00191       ++NI){
00192     Graph::nodeList node_list=t.getNodeList(*NI);
00193     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
00194   NLI!=NLE; ++NLI){
00195       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
00196       if(!edgesEqual(f,e) && *v==*(f.getFirst())){
00197         int dir_count=inc_Dir(e,f);
00198   int wt=f.getWeight();
00199   inc_DFS(g,t, Increment, dir_count*events+wt, 
00200     f.getSecond(), f);
00201       }
00202     }
00203   }
00204 
00205   allNodes=g.getAllNodes();
00206   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
00207       ++NI){
00208     Graph::nodeList node_list=g.getNodeList(*NI);
00209     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
00210   NLI!=NLE; ++NLI){
00211       Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
00212       if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) || 
00213           *v==*(f.getFirst()))){
00214   int dir_count=inc_Dir(e,f);
00215   Increment[f]+=dir_count*events;
00216       }
00217     }
00218   }
00219 }
00220 
00221 //Now we select a subset of all edges
00222 //and assign them some values such that 
00223 //if we consider just this subset, it still represents
00224 //the path sum along any path in the graph
00225 static map<Edge, int, EdgeCompare2> getEdgeIncrements(Graph& g, Graph& t, 
00226                                                       vector<Edge> &be){
00227   //get all edges in g-t
00228   map<Edge, int, EdgeCompare2> Increment;
00229 
00230   vector<Node *> allNodes=g.getAllNodes();
00231  
00232   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
00233       ++NI){
00234     Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
00235     //modified g.getNodeList(*NI);
00236     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
00237   NLI!=NLE; ++NLI){
00238       Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
00239       if(!(t.hasEdgeAndWt(ed))){
00240   Increment[ed]=0;;
00241       }
00242     }
00243   }
00244 
00245   Edge *ed=new Edge();
00246   inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
00247 
00248   for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; 
00249       ++NI){
00250     Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
00251     //modified g.getNodeList(*NI);
00252     for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end(); 
00253   NLI!=NLE; ++NLI){
00254       Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
00255       if(!(t.hasEdgeAndWt(ed))){
00256   int wt=ed.getWeight();
00257   Increment[ed]+=wt;
00258       }
00259     }
00260   }
00261 
00262   return Increment;
00263 }
00264 
00265 //push it up: TODO
00266 const graphListElement *findNodeInList(const Graph::nodeList &NL,
00267                 Node *N);
00268 
00269 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
00270 //end TODO
00271 
00272 //Based on edgeIncrements (above), now obtain
00273 //the kind of code to be inserted along an edge
00274 //The idea here is to minimize the computation
00275 //by inserting only the needed code
00276 static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare2> &instr,
00277                               vector<Edge > &chords, 
00278                               map<Edge,int, EdgeCompare2> &edIncrements){
00279 
00280   //Register initialization code
00281   vector<Node *> ws;
00282   ws.push_back(g.getRoot());
00283   while(ws.size()>0){
00284     Node *v=ws.back();
00285     ws.pop_back();
00286     //for each edge v->w
00287     Graph::nodeList succs=g.getNodeList(v);
00288     
00289     for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
00290   nl!=ne; ++nl){
00291       int edgeWt=nl->weight;
00292       Node *w=nl->element;
00293       //if chords has v->w
00294       Edge ed(v,w, edgeWt, nl->randId);
00295       bool hasEdge=false;
00296       for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
00297     CI!=CE && !hasEdge;++CI){
00298   if(*CI==ed && CI->getWeight()==edgeWt){//modf
00299     hasEdge=true;
00300   }
00301       }
00302 
00303       if(hasEdge){//so its a chord edge
00304   getEdgeCode *edCd=new getEdgeCode();
00305   edCd->setCond(1);
00306   edCd->setInc(edIncrements[ed]);
00307   instr[ed]=edCd;
00308       }
00309       else if(g.getNumberOfIncomingEdges(w)==1){
00310   ws.push_back(w);
00311       }
00312       else{
00313   getEdgeCode *edCd=new getEdgeCode();
00314   edCd->setCond(2);
00315   edCd->setInc(0);
00316   instr[ed]=edCd;
00317       }
00318     }
00319   }
00320 
00321   /////Memory increment code
00322   ws.push_back(g.getExit());
00323   
00324   while(!ws.empty()) {
00325     Node *w=ws.back();
00326     ws.pop_back();
00327 
00328 
00329     ///////
00330     //vector<Node *> lt;
00331     vector<Node *> lllt=g.getAllNodes();
00332     for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
00333       Node *lnode=*EII;
00334       Graph::nodeList &nl = g.getNodeList(lnode);
00335       //graphListElement *N = findNodeInList(nl, w);
00336       for(Graph::nodeList::const_iterator N = nl.begin(), 
00337             NNEN = nl.end(); N!= NNEN; ++N){
00338         if (*N->element == *w){ 
00339           Node *v=lnode;
00340           
00341           //if chords has v->w
00342           Edge ed(v,w, N->weight, N->randId);
00343           getEdgeCode *edCd=new getEdgeCode();
00344           bool hasEdge=false;
00345           for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
00346               ++CI){
00347             if(*CI==ed && CI->getWeight()==N->weight){
00348               hasEdge=true;
00349               break;
00350             }
00351           }
00352           if(hasEdge){
00353             //char str[100];
00354             if(instr[ed]!=NULL && instr[ed]->getCond()==1){
00355               instr[ed]->setCond(4);
00356             }
00357             else{
00358               edCd->setCond(5);
00359               edCd->setInc(edIncrements[ed]);
00360               instr[ed]=edCd;
00361             }
00362             
00363           }
00364           else if(g.getNumberOfOutgoingEdges(v)==1)
00365             ws.push_back(v);
00366           else{
00367             edCd->setCond(6);
00368             instr[ed]=edCd;
00369           }
00370         }
00371       }
00372     }
00373   }
00374   ///// Register increment code
00375   for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
00376     getEdgeCode *edCd=new getEdgeCode();
00377     if(instr[*CI]==NULL){
00378       edCd->setCond(3);
00379       edCd->setInc(edIncrements[*CI]);
00380       instr[*CI]=edCd;
00381     }
00382   }
00383 }
00384 
00385 //Add dummy edges corresponding to the back edges
00386 //If a->b is a backedge
00387 //then incoming dummy edge is root->b
00388 //and outgoing dummy edge is a->exit
00389 //changed
00390 void addDummyEdges(vector<Edge > &stDummy, 
00391        vector<Edge > &exDummy, 
00392        Graph &g, vector<Edge> &be){
00393   for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
00394     Edge ed=*VI;
00395     Node *first=ed.getFirst();
00396     Node *second=ed.getSecond();
00397     g.removeEdge(ed);
00398 
00399     if(!(*second==*(g.getRoot()))){
00400       Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
00401       stDummy.push_back(*st);
00402       g.addEdgeForce(*st);
00403     }
00404 
00405     if(!(*first==*(g.getExit()))){
00406       Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
00407       exDummy.push_back(*ex);
00408       g.addEdgeForce(*ex);
00409     }
00410   }
00411 }
00412 
00413 //print a given edge in the form BB1Label->BB2Label
00414 void printEdge(Edge ed){
00415   cerr<<((ed.getFirst())->getElement())
00416     ->getName()<<"->"<<((ed.getSecond())
00417         ->getElement())->getName()<<
00418     ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
00419 }
00420 
00421 //Move the incoming dummy edge code and outgoing dummy
00422 //edge code over to the corresponding back edge
00423 static void moveDummyCode(vector<Edge> &stDummy, 
00424                           vector<Edge> &exDummy, 
00425                           vector<Edge> &be,  
00426                           map<Edge, getEdgeCode *, EdgeCompare2> &insertions, 
00427         Graph &g){
00428   typedef vector<Edge >::iterator vec_iter;
00429   
00430   map<Edge,getEdgeCode *, EdgeCompare2> temp;
00431   //iterate over edges with code
00432   std::vector<Edge> toErase;
00433   for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=insertions.begin(), 
00434   ME=insertions.end(); MI!=ME; ++MI){
00435     Edge ed=MI->first;
00436     getEdgeCode *edCd=MI->second;
00437 
00438     ///---new code
00439     //iterate over be, and check if its starts and end vertices hv code
00440     for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
00441       if(ed.getRandId()==BEI->getRandId()){
00442   
00443   if(temp[*BEI]==0)
00444     temp[*BEI]=new getEdgeCode();
00445   
00446   //so ed is either in st, or ex!
00447   if(ed.getFirst()==g.getRoot()){
00448 
00449     //so its in stDummy
00450     temp[*BEI]->setCdIn(edCd);
00451     toErase.push_back(ed);
00452   }
00453   else if(ed.getSecond()==g.getExit()){
00454 
00455     //so its in exDummy
00456     toErase.push_back(ed);
00457     temp[*BEI]->setCdOut(edCd);
00458   }
00459   else{
00460     assert(false && "Not found in either start or end! Rand failed?");
00461   }
00462       }
00463     }
00464   }
00465   
00466   for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; 
00467       ++vmi){
00468     insertions.erase(*vmi);
00469     g.removeEdgeWithWt(*vmi);
00470   }
00471   
00472   for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=temp.begin(), 
00473       ME=temp.end(); MI!=ME; ++MI){
00474     insertions[MI->first]=MI->second;
00475   }
00476     
00477 #ifdef DEBUG_PATH_PROFILES
00478   cerr<<"size of deletions: "<<toErase.size()<<"\n";
00479   cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
00480 #endif
00481 
00482 }
00483 
00484 //Do graph processing: to determine minimal edge increments, 
00485 //appropriate code insertions etc and insert the code at
00486 //appropriate locations
00487 void processGraph(Graph &g, 
00488       Instruction *rInst, 
00489       Value *countInst, 
00490       vector<Edge >& be, 
00491       vector<Edge >& stDummy, 
00492       vector<Edge >& exDummy, 
00493       int numPaths, int MethNo, 
00494                   Value *threshold){
00495 
00496   //Given a graph: with exit->root edge, do the following in seq:
00497   //1. get back edges
00498   //2. insert dummy edges and remove back edges
00499   //3. get edge assignments
00500   //4. Get Max spanning tree of graph:
00501   //   -Make graph g2=g undirectional
00502   //   -Get Max spanning tree t
00503   //   -Make t undirectional
00504   //   -remove edges from t not in graph g
00505   //5. Get edge increments
00506   //6. Get code insertions
00507   //7. move code on dummy edges over to the back edges
00508   
00509 
00510   //This is used as maximum "weight" for 
00511   //priority queue
00512   //This would hold all 
00513   //right as long as number of paths in the graph
00514   //is less than this
00515   const int Infinity=99999999;
00516 
00517 
00518   //step 1-3 are already done on the graph when this function is called
00519   DEBUG(printGraph(g));
00520 
00521   //step 4: Get Max spanning tree of graph
00522 
00523   //now insert exit to root edge
00524   //if its there earlier, remove it!
00525   //assign it weight Infinity
00526   //so that this edge IS ALWAYS IN spanning tree
00527   //Note than edges in spanning tree do not get 
00528   //instrumented: and we do not want the
00529   //edge exit->root to get instrumented
00530   //as it MAY BE a dummy edge
00531   Edge ed(g.getExit(),g.getRoot(),Infinity);
00532   g.addEdge(ed,Infinity);
00533   Graph g2=g;
00534 
00535   //make g2 undirectional: this gives a better
00536   //maximal spanning tree
00537   g2.makeUnDirectional();
00538   DEBUG(printGraph(g2));
00539 
00540   Graph *t=g2.getMaxSpanningTree();
00541 #ifdef DEBUG_PATH_PROFILES
00542   std::cerr<<"Original maxspanning tree\n";
00543   printGraph(*t);
00544 #endif
00545   //now edges of tree t have weights reversed
00546   //(negative) because the algorithm used
00547   //to find max spanning tree is 
00548   //actually for finding min spanning tree
00549   //so get back the original weights
00550   t->reverseWts();
00551 
00552   //Ordinarily, the graph is directional
00553   //lets converts the graph into an 
00554   //undirectional graph
00555   //This is done by adding an edge
00556   //v->u for all existing edges u->v
00557   t->makeUnDirectional();
00558 
00559   //Given a tree t, and a "directed graph" g
00560   //replace the edges in the tree t with edges that exist in graph
00561   //The tree is formed from "undirectional" copy of graph
00562   //So whatever edges the tree has, the undirectional graph 
00563   //would have too. This function corrects some of the directions in 
00564   //the tree so that now, all edge directions in the tree match
00565   //the edge directions of corresponding edges in the directed graph
00566   removeTreeEdges(g, *t);
00567 
00568 #ifdef DEBUG_PATH_PROFILES
00569   cerr<<"Final Spanning tree---------\n";
00570   printGraph(*t);
00571   cerr<<"-------end spanning tree\n";
00572 #endif
00573 
00574   //now remove the exit->root node
00575   //and re-add it with weight 0
00576   //since infinite weight is kinda confusing
00577   g.removeEdge(ed);
00578   Edge edNew(g.getExit(), g.getRoot(),0);
00579   g.addEdge(edNew,0);
00580   if(t->hasEdge(ed)){
00581     t->removeEdge(ed);
00582     t->addEdge(edNew,0);
00583   }
00584 
00585   DEBUG(printGraph(g);
00586         printGraph(*t));
00587 
00588   //step 5: Get edge increments
00589 
00590   //Now we select a subset of all edges
00591   //and assign them some values such that 
00592   //if we consider just this subset, it still represents
00593   //the path sum along any path in the graph
00594 
00595   map<Edge, int, EdgeCompare2> increment=getEdgeIncrements(g,*t, be);
00596 #ifdef DEBUG_PATH_PROFILES
00597   //print edge increments for debugging
00598   std::cerr<<"Edge Increments------\n";
00599   for(map<Edge, int, EdgeCompare2>::iterator MMI=increment.begin(), MME=increment.end(); MMI != MME; ++MMI){
00600     printEdge(MMI->first);
00601     std::cerr<<"Increment for above:"<<MMI->second<<"\n";
00602   }
00603   std::cerr<<"-------end of edge increments\n";
00604 #endif
00605 
00606  
00607   //step 6: Get code insertions
00608   
00609   //Based on edgeIncrements (above), now obtain
00610   //the kind of code to be inserted along an edge
00611   //The idea here is to minimize the computation
00612   //by inserting only the needed code
00613   vector<Edge> chords;
00614   getChords(chords, g, *t);
00615 
00616 
00617   map<Edge, getEdgeCode *, EdgeCompare2> codeInsertions;
00618   getCodeInsertions(g, codeInsertions, chords,increment);
00619   
00620 #ifdef DEBUG_PATH_PROFILES
00621   //print edges with code for debugging
00622   cerr<<"Code inserted in following---------------\n";
00623   for(map<Edge, getEdgeCode *, EdgeCompare2>::iterator cd_i=codeInsertions.begin(), 
00624   cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
00625     printEdge(cd_i->first);
00626     cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
00627   }
00628   cerr<<"-----end insertions\n";
00629 #endif
00630 
00631   //step 7: move code on dummy edges over to the back edges
00632 
00633   //Move the incoming dummy edge code and outgoing dummy
00634   //edge code over to the corresponding back edge
00635 
00636   moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
00637   
00638 #ifdef DEBUG_PATH_PROFILES
00639   //debugging info
00640   cerr<<"After moving dummy code\n";
00641   for(map<Edge, getEdgeCode *,EdgeCompare2>::iterator cd_i=codeInsertions.begin(), 
00642   cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
00643     printEdge(cd_i->first);
00644     cerr<<cd_i->second->getCond()<<":"
00645   <<cd_i->second->getInc()<<"\n";
00646   }
00647   cerr<<"Dummy end------------\n";
00648 #endif
00649 
00650 
00651   //see what it looks like...
00652   //now insert code along edges which have codes on them
00653   for(map<Edge, getEdgeCode *,EdgeCompare2>::iterator MI=codeInsertions.begin(), 
00654   ME=codeInsertions.end(); MI!=ME; ++MI){
00655     Edge ed=MI->first;
00656     insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo, threshold);
00657   } 
00658 }
00659 
00660 //print the graph (for debugging)
00661 void printGraph(Graph &g){
00662   vector<Node *> lt=g.getAllNodes();
00663   cerr<<"Graph---------------------\n";
00664   for(vector<Node *>::iterator LI=lt.begin(); 
00665       LI!=lt.end(); ++LI){
00666     cerr<<((*LI)->getElement())->getName()<<"->";
00667     Graph::nodeList nl=g.getNodeList(*LI);
00668     for(Graph::nodeList::iterator NI=nl.begin(); 
00669   NI!=nl.end(); ++NI){
00670       cerr<<":"<<"("<<(NI->element->getElement())
00671   ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
00672     <<NI->randId<<")";
00673     }
00674     cerr<<"\n";
00675   }
00676   cerr<<"--------------------Graph\n";
00677 }
00678 
00679 } // End llvm namespace