1 //===-- GrapAuxillary.cpp- Auxillary functions on graph ----------*- C++ -*--=//
3 //auxillary function associated with graph: they
4 //all operate on graph, and help in inserting
5 //instrumentation for trace generation
7 //===----------------------------------------------------------------------===//
10 #include "llvm/BasicBlock.h"
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());
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;
31 Graph::nodeList node_list=g.getNodeList(*NI);
32 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
34 Edge f(*NI, NLI->element,NLI->weight);
35 if(!(st.hasEdgeAndWt(f)))//addnl
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;
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
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){
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]);
78 NumPaths[*RI]+=NumPaths[*SI];
82 return NumPaths[g.getRoot()];
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){
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()));
104 if(*(e.getFirst())==*(f.getSecond()) ||
105 *(e.getSecond())==*(f.getFirst()))
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){
116 list<Node *> allNodes=t.getAllNodes();
118 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
120 Graph::nodeList node_list=t.getNodeList(*NI);
121 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
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);
132 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
134 Graph::nodeList node_list=t.getNodeList(*NI);
135 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
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,
147 allNodes=g.getAllNodes();
148 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
150 Graph::nodeList node_list=g.getNodeList(*NI);
151 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
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;
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;
171 list<Node *> allNodes=g.getAllNodes();
173 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
175 Graph::nodeList node_list=g.getNodeList(*NI);
176 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
178 Edge ed(*NI, NLI->element,NLI->weight);
179 if(!(t.hasEdge(ed))){
186 inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
189 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
191 Graph::nodeList node_list=g.getNodeList(*NI);
192 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
194 Edge ed(*NI, NLI->element,NLI->weight);
195 if(!(t.hasEdge(ed))){
196 int wt=ed.getWeight();
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){
213 //Register initialization code
215 ws.push_back(g.getRoot());
220 Graph::nodeList succs=g.getNodeList(v);
222 for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
224 int edgeWt=nl->weight;
230 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
231 CI!=CE && !hasEdge;++CI){
237 getEdgeCode *edCd=new getEdgeCode();
239 edCd->setInc(edIncrements[ed]);
242 else if((g.getPredNodes(w)).size()==1){
246 getEdgeCode *edCd=new getEdgeCode();
254 /////Memory increment code
255 ws.push_back(g.getExit());
262 list<Node *> preds=g.getPredNodes(w);
263 for(list<Node *>::iterator pd=preds.begin(), pe=preds.end(); pd!=pe; ++pd){
268 getEdgeCode *edCd=new getEdgeCode();
270 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
279 if(instr[ed]!=NULL && instr[ed]->getCond()==1){
280 instr[ed]->setCond(4);
284 edCd->setInc(edIncrements[ed]);
289 else if(g.getSuccNodes(v).size()==1)
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){
303 edCd->setInc(edIncrements[*CI]);
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){
318 Node *first=ed.getFirst();
319 Node *second=ed.getSecond();
322 if(!(*second==*(g.getRoot()))){
323 Edge *st=new Edge(g.getRoot(), second);
325 //check if stDummy doesn't have it already
326 if(find(stDummy.begin(), stDummy.end(), *st) == stDummy.end())
327 stDummy.push_back(*st);
331 if(!(*first==*(g.getExit()))){
332 Edge *ex=new Edge(first, g.getExit());
334 if (find(exDummy.begin(), exDummy.end(), *ex) == exDummy.end()) {
335 exDummy.push_back(*ex);
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";
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;
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)
363 cerr<<"StEdges---------------\n";
364 for(vec_iter VI=stDummy.begin(); VI!=stDummy.end(); ++VI)
366 cerr<<"ExitEdges---------------\n";
367 for(vec_iter VI=exDummy.begin(); VI!=exDummy.end(); ++VI)
369 cerr<<"------end all edges\n";
372 std::vector<Edge> toErase;
373 for(map<Edge,getEdgeCode *>::iterator MI=insertions.begin(),
374 ME=insertions.end(); MI!=ME; ++MI){
376 getEdgeCode *edCd=MI->second;
377 bool dummyHasIt=false;
378 #ifdef DEBUG_PATH_PROFILES
379 cerr<<"Current edge considered---\n";
382 //now check if stDummy has ed
383 for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt;
386 #ifdef DEBUG_PATH_PROFILES
387 cerr<<"Edge matched with stDummy\n";
390 bool dummyInBe=false;
391 //dummy edge with code
392 for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe; ++BE){
394 Node *st=backEdge.getSecond();
395 Node *dm=ed.getSecond();
397 //so this is the back edge to use
398 #ifdef DEBUG_PATH_PROFILES
399 cerr<<"Moving to backedge\n";
402 getEdgeCode *ged=new getEdgeCode();
404 toErase.push_back(ed);
405 insertions[backEdge]=ged;
413 //so exDummy may hv it
414 bool inExDummy=false;
415 for(vec_iter VI=exDummy.begin(), VE=exDummy.end(); VI!=VE && !inExDummy;
419 #ifdef DEBUG_PATH_PROFILES
420 cerr<<"Edge matched with exDummy\n";
422 bool dummyInBe2=false;
423 //dummy edge with code
424 for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe2;
427 Node *st=backEdge.getFirst();
428 Node *dm=ed.getFirst();
430 //so this is the back edge to use
432 if(insertions[backEdge]==NULL)
433 ged=new getEdgeCode();
435 ged=insertions[backEdge];
436 toErase.push_back(ed);
438 insertions[backEdge]=ged;
448 #ifdef DEBUG_PATH_PROFILES
449 cerr<<"size of deletions: "<<toErase.size()<<"\n";
452 for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
454 insertions.erase(*vmi);
456 #ifdef DEBUG_PATH_PROFILES
457 cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
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,
466 Instruction *countInst,
468 vector<Edge >& stDummy,
469 vector<Edge >& exDummy){
470 //Given a graph: with exit->root edge, do the following in seq:
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
484 //This is used as maximum "weight" for
486 //This would hold all
487 //right as long as number of paths in the graph
489 const int INFINITY=99999999;
492 //step 1-3 are already done on the graph when this function is called
493 #ifdef DEBUG_PATH_PROFILES
496 //step 4: Get Max spanning tree of graph
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);
510 //make g2 undirectional: this gives a better
511 //maximal spanning tree
512 g2.makeUnDirectional();
513 #ifdef DEBUG_PATH_PROFILES
516 Graph *t=g2.getMaxSpanningTree();
517 #ifdef DEBUG_PATH_PROFILES
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
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();
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";
545 cerr<<"-------end spanning tree\n";
547 //now remove the exit->root node
548 //and re-add it with weight 0
549 //since infinite weight is kinda confusing
551 Edge edNew(g.getExit(), g.getRoot(),0);
558 #ifdef DEBUG_PATH_PROFILES
562 //step 5: Get edge increments
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();
573 printEdge(M_I->first);
574 cerr<<"Increment for above:"<<M_I->second<<"\n";
578 //step 6: Get code insertions
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
585 getChords(chords, g, *t);
587 map<Edge, getEdgeCode *> codeInsertions;
588 getCodeInsertions(g, codeInsertions, chords,increment);
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";
598 cerr<<"-----end insertions\n";
600 //step 7: move code on dummy edges over to the back edges
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);
606 #ifdef DEBUG_PATH_PROFILES
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";
615 cerr<<"Dummy end------------\n";
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){
623 insertBB(ed, MI->second, rInst, countInst);
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();
635 cerr<<((*LI)->getElement())->getName()<<"->";
636 Graph::nodeList nl=g.getNodeList(*LI);
637 for(Graph::nodeList::iterator NI=nl.begin();
639 cerr<<":"<<"("<<(NI->element->getElement())
640 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
644 cerr<<"--------------------Graph\n";