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"
13 //check if 2 edges are equal (same endpoints and same weight)
14 static bool edgesEqual(Edge ed1, Edge ed2);
16 //Get the vector of edges that are to be instrumented in the graph
17 static void getChords(vector<Edge > &chords, Graph g, Graph st);
19 //Given a tree t, and a "directed graph" g
20 //replace the edges in the tree t with edges that exist in graph
21 //The tree is formed from "undirectional" copy of graph
22 //So whatever edges the tree has, the undirectional graph
23 //would have too. This function corrects some of the directions in
24 //the tree so that now, all edge directions in the tree match
25 //the edge directions of corresponding edges in the directed graph
26 static void removeTreeEdges(Graph g, Graph& t);
28 //Now we select a subset of all edges
29 //and assign them some values such that
30 //if we consider just this subset, it still represents
31 //the path sum along any path in the graph
32 static map<Edge, int> getEdgeIncrements(Graph& g, Graph& t);
34 //Based on edgeIncrements (above), now obtain
35 //the kind of code to be inserted along an edge
36 //The idea here is to minimize the computation
37 //by inserting only the needed code
38 static map<Edge, getEdgeCode *>*
39 getCodeInsertions(Graph &g,
40 vector<Edge > &chords,
41 map<Edge,int> &edIncrements);
43 //Move the incoming dummy edge code and outgoing dummy
44 //edge code over to the corresponding back edge
45 static void moveDummyCode(vector<Edge > stDummy,
46 vector<Edge > exDummy,
48 map<Edge, getEdgeCode *> &insertions);
52 //Do graph processing: to determine minimal edge increments,
53 //appropriate code insertions etc and insert the code at
54 //appropriate locations
55 void processGraph(Graph &g,
57 Instruction *countInst,
59 vector<Edge >& stDummy,
60 vector<Edge >& exDummy){
61 //Given a graph: with exit->root edge, do the following in seq:
63 //2. insert dummy edges and remove back edges
64 //3. get edge assignments
65 //4. Get Max spanning tree of graph:
66 // -Make graph g2=g undirectional
67 // -Get Max spanning tree t
68 // -Make t undirectional
69 // -remove edges from t not in graph g
70 //5. Get edge increments
71 //6. Get code insertions
72 //7. move code on dummy edges over to the back edges
75 //This is used as maximum "weight" for
78 //right as long as number of paths in the graph
80 const int INFINITY=99999999;
83 //step 1-3 are already done on the graph when this function is called
84 #ifdef DEBUG_PATH_PROFILES
87 //step 4: Get Max spanning tree of graph
89 //now insert exit to root edge
90 //if its there earlier, remove it!
91 //assign it weight INFINITY
92 //so that this edge IS ALWAYS IN spanning tree
93 //Note than edges in spanning tree do not get
94 //instrumented: and we do not want the
95 //edge exit->root to get instrumented
96 //as it MAY BE a dummy edge
97 Edge ed(g.getExit(),g.getRoot(),INFINITY);
98 g.addEdge(ed,INFINITY);
101 //make g2 undirectional: this gives a better
102 //maximal spanning tree
103 g2.makeUnDirectional();
104 #ifdef DEBUG_PATH_PROFILES
107 Graph *t=g2.getMaxSpanningTree();
108 #ifdef DEBUG_PATH_PROFILES
111 //now edges of tree t have weights reversed
112 //(negative) because the algorithm used
113 //to find max spanning tree is
114 //actually for finding min spanning tree
115 //so get back the original weights
118 //Ordinarily, the graph is directional
119 //lets converts the graph into an
120 //undirectional graph
121 //This is done by adding an edge
122 //v->u for all existing edges u->v
123 t->makeUnDirectional();
125 //Given a tree t, and a "directed graph" g
126 //replace the edges in the tree t with edges that exist in graph
127 //The tree is formed from "undirectional" copy of graph
128 //So whatever edges the tree has, the undirectional graph
129 //would have too. This function corrects some of the directions in
130 //the tree so that now, all edge directions in the tree match
131 //the edge directions of corresponding edges in the directed graph
132 removeTreeEdges(g, *t);
133 #ifdef DEBUG_PATH_PROFILES
134 cerr<<"Spanning tree---------\n";
136 cerr<<"-------end spanning tree\n";
138 //now remove the exit->root node
139 //and re-add it with weight 0
140 //since infinite weight is kinda confusing
142 Edge edNew(g.getExit(), g.getRoot(),0);
149 #ifdef DEBUG_PATH_PROFILES
153 //step 5: Get edge increments
155 //Now we select a subset of all edges
156 //and assign them some values such that
157 //if we consider just this subset, it still represents
158 //the path sum along any path in the graph
159 map<Edge, int> increment=getEdgeIncrements(g,*t);
160 #ifdef DEBUG_PATH_PROFILES
161 //print edge increments for debugging
162 for(map<Edge, int>::iterator M_I=increment.begin(), M_E=increment.end();
164 printEdge(M_I->first);
165 cerr<<"Increment for above:"<<M_I->second<<endl;
169 //step 6: Get code insertions
171 //Based on edgeIncrements (above), now obtain
172 //the kind of code to be inserted along an edge
173 //The idea here is to minimize the computation
174 //by inserting only the needed code
175 map<Edge, getEdgeCode *>* codeInsertions;
176 vector<Edge > chords;
177 getChords(chords, g, *t);
178 codeInsertions=getCodeInsertions(g,chords,increment);
180 #ifdef DEBUG_PATH_PROFILES
181 //print edges with code for debugging
182 cerr<<"Code inserted in following---------------\n";
183 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions->begin(),
184 cd_e=codeInsertions->end(); cd_i!=cd_e; ++cd_i){
185 printEdge(cd_i->first);
186 cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<endl;
188 cerr<<"-----end insertions\n";
190 //step 7: move code on dummy edges over to the back edges
192 //Move the incoming dummy edge code and outgoing dummy
193 //edge code over to the corresponding back edge
194 moveDummyCode(stDummy, exDummy, be, *codeInsertions);
196 #ifdef DEBUG_PATH_PROFILES
198 cerr<<"After moving dummy code\n";
199 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions->begin(),
200 cd_e=codeInsertions->end(); cd_i!=cd_e; ++cd_i){
201 printEdge(cd_i->first);
202 cerr<<cd_i->second->getCond()<<":"
203 <<cd_i->second->getInc()<<endl;
205 cerr<<"Dummy end------------\n";
208 //see what it looks like...
209 //now insert code along edges which have codes on them
210 for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions->begin(),
211 ME=codeInsertions->end(); MI!=ME; ++MI){
213 insertBB(ed, MI->second, rInst, countInst);
219 //check if 2 edges are equal (same endpoints and same weight)
220 static bool edgesEqual(Edge ed1, Edge ed2){
221 return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
224 //Get the vector of edges that are to be instrumented in the graph
225 static void getChords(vector<Edge > &chords, Graph g, Graph st){
226 //make sure the spanning tree is directional
227 //iterate over ALL the edges of the graph
228 list<Node *> allNodes=g.getAllNodes();
229 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
231 Graph::nodeList node_list=g.getNodeList(*NI);
232 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
234 Edge f(*NI, NLI->element,NLI->weight);
235 if(!(st.hasEdgeAndWt(f)))//addnl
241 //Given a tree t, and a "directed graph" g
242 //replace the edges in the tree t with edges that exist in graph
243 //The tree is formed from "undirectional" copy of graph
244 //So whatever edges the tree has, the undirectional graph
245 //would have too. This function corrects some of the directions in
246 //the tree so that now, all edge directions in the tree match
247 //the edge directions of corresponding edges in the directed graph
248 static void removeTreeEdges(Graph g, Graph& t){
249 list<Node* > allNodes=t.getAllNodes();
250 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
252 Graph::nodeList nl=t.getNodeList(*NI);
253 for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
254 Edge ed(NLI->element, *NI, NLI->weight);
255 //if(!g.hasEdge(ed)) t.removeEdge(ed);
256 if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
257 //between any pair of vertices, so no need to delete by edge wt
262 //Assign a value to all the edges in the graph
263 //such that if we traverse along any path from root to exit, and
264 //add up the edge values, we get a path number that uniquely
265 //refers to the path we travelled
266 int valueAssignmentToEdges(Graph& g){
267 list<Node *> revtop=g.reverseTopologicalSort();
268 map<Node *,int > NumPaths;
269 for(list<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
274 list<Node *> succ=g.getSuccNodes(*RI);
275 for(list<Node *>::iterator SI=succ.begin(), SE=succ.end(); SI!=SE; ++SI){
276 Edge ed(*RI,*SI,NumPaths[*RI]);
278 NumPaths[*RI]+=NumPaths[*SI];
282 return NumPaths[g.getRoot()];
285 //This is a helper function to get the edge increments
286 //This is used in conjuntion with inc_DFS
287 //to get the edge increments
288 //Edge increment implies assigning a value to all the edges in the graph
289 //such that if we traverse along any path from root to exit, and
290 //add up the edge values, we get a path number that uniquely
291 //refers to the path we travelled
292 //inc_Dir tells whether 2 edges are in same, or in different directions
293 //if same direction, return 1, else -1
294 static int inc_Dir(Edge e,Edge f){
298 //check that the edges must have atleast one common endpoint
299 assert(*(e.getFirst())==*(f.getFirst()) ||
300 *(e.getFirst())==*(f.getSecond()) ||
301 *(e.getSecond())==*(f.getFirst()) ||
302 *(e.getSecond())==*(f.getSecond()));
304 if(*(e.getFirst())==*(f.getSecond()) ||
305 *(e.getSecond())==*(f.getFirst()))
311 //used for getting edge increments (read comments above in inc_Dir)
312 //inc_DFS is a modification of DFS
313 static void inc_DFS(Graph& g,Graph& t,map<Edge, int>& Increment,
314 int events, Node *v, Edge e){
316 list<Node *> allNodes=t.getAllNodes();
318 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
320 Graph::nodeList node_list=t.getNodeList(*NI);
321 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
323 Edge f(*NI, NLI->element,NLI->weight);
324 if(!edgesEqual(f,e) && *v==*(f.getSecond())){
325 int dir_count=inc_Dir(e,f);
326 int wt=1*f.getWeight();
327 inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
332 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
334 Graph::nodeList node_list=t.getNodeList(*NI);
335 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
337 Edge f(*NI, NLI->element,NLI->weight);
338 if(!edgesEqual(f,e) && *v==*(f.getFirst())){
339 int dir_count=inc_Dir(e,f);
340 int wt=1*f.getWeight();
341 inc_DFS(g,t, Increment, dir_count*events+wt,
347 allNodes=g.getAllNodes();
348 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
350 Graph::nodeList node_list=g.getNodeList(*NI);
351 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
353 Edge f(*NI, NLI->element,NLI->weight);
354 if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
355 *v==*(f.getFirst()))){
356 int dir_count=inc_Dir(e,f);
357 Increment[f]+=dir_count*events;
363 //Now we select a subset of all edges
364 //and assign them some values such that
365 //if we consider just this subset, it still represents
366 //the path sum along any path in the graph
367 static map<Edge, int> getEdgeIncrements(Graph& g, Graph& t){
368 //get all edges in g-t
369 map<Edge, int> Increment;
371 list<Node *> allNodes=g.getAllNodes();
373 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
375 Graph::nodeList node_list=g.getNodeList(*NI);
376 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
378 Edge ed(*NI, NLI->element,NLI->weight);
379 if(!(t.hasEdge(ed))){
386 inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
389 for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
391 Graph::nodeList node_list=g.getNodeList(*NI);
392 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
394 Edge ed(*NI, NLI->element,NLI->weight);
395 if(!(t.hasEdge(ed))){
396 int wt=ed.getWeight();
405 //Based on edgeIncrements (above), now obtain
406 //the kind of code to be inserted along an edge
407 //The idea here is to minimize the computation
408 //by inserting only the needed code
409 static map<Edge, getEdgeCode *>*
410 getCodeInsertions(Graph &g,
411 vector<Edge > &chords,
412 map<Edge,int> &edIncrements){
413 //map of instrumented edges that's returned in the end
414 map<Edge, getEdgeCode *> *instr=
415 new map<Edge, getEdgeCode *>;
417 //Register initialization code
419 ws.push_back(g.getRoot());
422 ws.erase(ws.begin());
424 Graph::nodeList succs=g.getNodeList(v);
426 for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
428 int edgeWt=nl->weight;
434 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
435 CI!=CE && !hasEdge;++CI){
441 getEdgeCode *edCd=new getEdgeCode();
443 edCd->setInc(edIncrements[ed]);
446 else if((g.getPredNodes(w)).size()==1){
450 getEdgeCode *edCd=new getEdgeCode();
458 /////Memory increment code
459 ws.push_back(g.getExit());
466 list<Node *> preds=g.getPredNodes(w);
467 for(list<Node *>::iterator pd=preds.begin(), pe=preds.end(); pd!=pe; ++pd){
472 getEdgeCode *edCd=new getEdgeCode();
474 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
483 if((*instr)[ed]!=NULL && (*instr)[ed]->getCond()==1){
484 (*instr)[ed]->setCond(4);
488 edCd->setInc(edIncrements[ed]);
493 else if(g.getSuccNodes(v).size()==1)
502 ///// Register increment code
503 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
504 getEdgeCode *edCd=new getEdgeCode();
505 if((*instr)[*CI]==NULL){
507 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
534 if(find(stDummy.begin(), stDummy.end(), *st)!=stDummy.end())
538 for(vector<Edge>::iterator DM=stDummy.begin(), DE=stDummy.end(); DM!=DE;
548 stDummy.push_back(*st);
553 if(!(*first==*(g.getExit()))){
554 Edge *ex=new Edge(first, g.getExit());
557 if(find(exDummy.begin(), exDummy.end(), *ex)!=exDummy.end())
561 for(vector<Edge>::iterator DM=exDummy.begin(), DE=exDummy.end(); DM!=DE;
571 exDummy.push_back(*ex);
578 //print a given edge in the form BB1Label->BB2Label
579 void printEdge(Edge ed){
580 cerr<<((ed.getFirst())->getElement())
581 ->getName()<<"->"<<((ed.getSecond())
582 ->getElement())->getName()<<
583 ":"<<ed.getWeight()<<endl;
586 //Move the incoming dummy edge code and outgoing dummy
587 //edge code over to the corresponding back edge
588 static void moveDummyCode(vector<Edge > stDummy,
589 vector<Edge > exDummy,
591 map<Edge, getEdgeCode *> &insertions){
592 typedef vector<Edge >::iterator vec_iter;
594 #ifdef DEBUG_PATH_PROFILES
595 //print all back, st and ex dummy
596 cerr<<"BackEdges---------------\n";
597 for(vec_iter VI=be.begin(); VI!=be.end(); ++VI)
599 cerr<<"StEdges---------------\n";
600 for(vec_iter VI=stDummy.begin(); VI!=stDummy.end(); ++VI)
602 cerr<<"ExitEdges---------------\n";
603 for(vec_iter VI=exDummy.begin(); VI!=exDummy.end(); ++VI)
605 cerr<<"------end all edges\n";
608 std::vector<Edge > toErase;
609 for(map<Edge,getEdgeCode *>::iterator MI=insertions.begin(),
610 ME=insertions.end(); MI!=ME; ++MI){
612 getEdgeCode *edCd=MI->second;
613 bool dummyHasIt=false;
614 #ifdef DEBUG_PATH_PROFILES
615 cerr<<"Current edge considered---\n";
618 //now check if stDummy has ed
619 for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt;
622 #ifdef DEBUG_PATH_PROFILES
623 cerr<<"Edge matched with stDummy\n";
626 bool dummyInBe=false;
627 //dummy edge with code
628 for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe; ++BE){
630 Node *st=backEdge.getSecond();
631 Node *dm=ed.getSecond();
633 //so this is the back edge to use
634 #ifdef DEBUG_PATH_PROFILES
635 cerr<<"Moving to backedge\n";
638 getEdgeCode *ged=new getEdgeCode();
640 toErase.push_back(ed);
641 insertions[backEdge]=ged;
649 //so exDummy may hv it
650 bool inExDummy=false;
651 for(vec_iter VI=exDummy.begin(), VE=exDummy.end(); VI!=VE && !inExDummy;
655 #ifdef DEBUG_PATH_PROFILES
656 cerr<<"Edge matched with exDummy\n";
658 bool dummyInBe2=false;
659 //dummy edge with code
660 for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe2;
663 Node *st=backEdge.getFirst();
664 Node *dm=ed.getFirst();
666 //so this is the back edge to use
668 if(insertions[backEdge]==NULL)
669 ged=new getEdgeCode();
671 ged=insertions[backEdge];
672 toErase.push_back(ed);
674 insertions[backEdge]=ged;
684 #ifdef DEBUG_PATH_PROFILES
685 cerr<<"size of deletions: "<<toErase.size()<<endl;
688 for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
690 insertions.erase(*vmi);
692 #ifdef DEBUG_PATH_PROFILES
693 cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<endl;
698 //print the graph (for debugging)
699 void printGraph(Graph g){
700 list<Node *> lt=g.getAllNodes();
701 cerr<<"Graph---------------------\n";
702 for(list<Node *>::iterator LI=lt.begin();
704 cerr<<((*LI)->getElement())->getName()<<"->";
705 Graph::nodeList nl=g.getNodeList(*LI);
706 for(Graph::nodeList::iterator NI=nl.begin();
708 cerr<<":"<<"("<<(NI->element->getElement())
709 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
713 cerr<<"--------------------Graph\n";