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);
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);
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);
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);
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);
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);
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,
62 Instruction *countInst,
64 vector<Edge >& stDummy,
65 vector<Edge >& exDummy){
66 //Given a graph: with exit->root edge, do the following in seq:
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
80 //This is used as maximum "weight" for
83 //right as long as number of paths in the graph
85 const int INFINITY=99999999;
88 //step 1-3 are already done on the graph when this function is called
89 #ifdef DEBUG_PATH_PROFILES
92 //step 4: Get Max spanning tree of graph
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);
106 //make g2 undirectional: this gives a better
107 //maximal spanning tree
108 g2.makeUnDirectional();
109 #ifdef DEBUG_PATH_PROFILES
112 Graph *t=g2.getMaxSpanningTree();
113 #ifdef DEBUG_PATH_PROFILES
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
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();
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";
141 cerr<<"-------end spanning tree\n";
143 //now remove the exit->root node
144 //and re-add it with weight 0
145 //since infinite weight is kinda confusing
147 Edge edNew(g.getExit(), g.getRoot(),0);
154 #ifdef DEBUG_PATH_PROFILES
158 //step 5: Get edge increments
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();
169 printEdge(M_I->first);
170 cerr<<"Increment for above:"<<M_I->second<<"\n";
174 //step 6: Get code insertions
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
181 getChords(chords, g, *t);
183 map<Edge, getEdgeCode *> codeInsertions;
184 getCodeInsertions(g, codeInsertions, chords,increment);
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";
194 cerr<<"-----end insertions\n";
196 //step 7: move code on dummy edges over to the back edges
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);
202 #ifdef DEBUG_PATH_PROFILES
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";
211 cerr<<"Dummy end------------\n";
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){
219 insertBB(ed, MI->second, rInst, countInst);
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());
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;
237 Graph::nodeList node_list=g.getNodeList(*NI);
238 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
240 Edge f(*NI, NLI->element,NLI->weight);
241 if(!(st.hasEdgeAndWt(f)))//addnl
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;
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
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){
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]);
284 NumPaths[*RI]+=NumPaths[*SI];
288 return NumPaths[g.getRoot()];
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){
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()));
310 if(*(e.getFirst())==*(f.getSecond()) ||
311 *(e.getSecond())==*(f.getFirst()))
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){
322 list<Node *> allNodes=t.getAllNodes();
324 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
326 Graph::nodeList node_list=t.getNodeList(*NI);
327 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
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);
338 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
340 Graph::nodeList node_list=t.getNodeList(*NI);
341 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
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,
353 allNodes=g.getAllNodes();
354 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
356 Graph::nodeList node_list=g.getNodeList(*NI);
357 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
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;
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;
377 list<Node *> allNodes=g.getAllNodes();
379 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
381 Graph::nodeList node_list=g.getNodeList(*NI);
382 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
384 Edge ed(*NI, NLI->element,NLI->weight);
385 if(!(t.hasEdge(ed))){
392 inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
395 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
397 Graph::nodeList node_list=g.getNodeList(*NI);
398 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
400 Edge ed(*NI, NLI->element,NLI->weight);
401 if(!(t.hasEdge(ed))){
402 int wt=ed.getWeight();
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){
419 //Register initialization code
421 ws.push_back(g.getRoot());
426 Graph::nodeList succs=g.getNodeList(v);
428 for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
430 int edgeWt=nl->weight;
436 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
437 CI!=CE && !hasEdge;++CI){
443 getEdgeCode *edCd=new getEdgeCode();
445 edCd->setInc(edIncrements[ed]);
448 else if((g.getPredNodes(w)).size()==1){
452 getEdgeCode *edCd=new getEdgeCode();
460 /////Memory increment code
461 ws.push_back(g.getExit());
468 list<Node *> preds=g.getPredNodes(w);
469 for(list<Node *>::iterator pd=preds.begin(), pe=preds.end(); pd!=pe; ++pd){
474 getEdgeCode *edCd=new getEdgeCode();
476 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
485 if(instr[ed]!=NULL && instr[ed]->getCond()==1){
486 instr[ed]->setCond(4);
490 edCd->setInc(edIncrements[ed]);
495 else if(g.getSuccNodes(v).size()==1)
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){
509 edCd->setInc(edIncrements[*CI]);
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){
524 Node *first=ed.getFirst();
525 Node *second=ed.getSecond();
528 if(!(*second==*(g.getRoot()))){
529 Edge *st=new Edge(g.getRoot(), second);
531 //check if stDummy doesn't have it already
532 if(find(stDummy.begin(), stDummy.end(), *st) == stDummy.end())
533 stDummy.push_back(*st);
537 if(!(*first==*(g.getExit()))){
538 Edge *ex=new Edge(first, g.getExit());
540 if (find(exDummy.begin(), exDummy.end(), *ex) == exDummy.end()) {
541 exDummy.push_back(*ex);
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";
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;
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)
569 cerr<<"StEdges---------------\n";
570 for(vec_iter VI=stDummy.begin(); VI!=stDummy.end(); ++VI)
572 cerr<<"ExitEdges---------------\n";
573 for(vec_iter VI=exDummy.begin(); VI!=exDummy.end(); ++VI)
575 cerr<<"------end all edges\n";
578 std::vector<Edge> toErase;
579 for(map<Edge,getEdgeCode *>::iterator MI=insertions.begin(),
580 ME=insertions.end(); MI!=ME; ++MI){
582 getEdgeCode *edCd=MI->second;
583 bool dummyHasIt=false;
584 #ifdef DEBUG_PATH_PROFILES
585 cerr<<"Current edge considered---\n";
588 //now check if stDummy has ed
589 for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt;
592 #ifdef DEBUG_PATH_PROFILES
593 cerr<<"Edge matched with stDummy\n";
596 bool dummyInBe=false;
597 //dummy edge with code
598 for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe; ++BE){
600 Node *st=backEdge.getSecond();
601 Node *dm=ed.getSecond();
603 //so this is the back edge to use
604 #ifdef DEBUG_PATH_PROFILES
605 cerr<<"Moving to backedge\n";
608 getEdgeCode *ged=new getEdgeCode();
610 toErase.push_back(ed);
611 insertions[backEdge]=ged;
619 //so exDummy may hv it
620 bool inExDummy=false;
621 for(vec_iter VI=exDummy.begin(), VE=exDummy.end(); VI!=VE && !inExDummy;
625 #ifdef DEBUG_PATH_PROFILES
626 cerr<<"Edge matched with exDummy\n";
628 bool dummyInBe2=false;
629 //dummy edge with code
630 for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe2;
633 Node *st=backEdge.getFirst();
634 Node *dm=ed.getFirst();
636 //so this is the back edge to use
638 if(insertions[backEdge]==NULL)
639 ged=new getEdgeCode();
641 ged=insertions[backEdge];
642 toErase.push_back(ed);
644 insertions[backEdge]=ged;
654 #ifdef DEBUG_PATH_PROFILES
655 cerr<<"size of deletions: "<<toErase.size()<<"\n";
658 for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
660 insertions.erase(*vmi);
662 #ifdef DEBUG_PATH_PROFILES
663 cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
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();
674 cerr<<((*LI)->getElement())->getName()<<"->";
675 Graph::nodeList nl=g.getNodeList(*LI);
676 for(Graph::nodeList::iterator NI=nl.begin();
678 cerr<<":"<<"("<<(NI->element->getElement())
679 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
683 cerr<<"--------------------Graph\n";