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 DEBUG( //print all back, st and ex dummy
359 cerr<<"BackEdges---------------\n";
360 for(vec_iter VI=be.begin(); VI!=be.end(); ++VI)
362 cerr<<"StEdges---------------\n";
363 for(vec_iter VI=stDummy.begin(); VI!=stDummy.end(); ++VI)
365 cerr<<"ExitEdges---------------\n";
366 for(vec_iter VI=exDummy.begin(); VI!=exDummy.end(); ++VI)
368 cerr<<"------end all edges\n");
370 std::vector<Edge> toErase;
371 for(map<Edge,getEdgeCode *>::iterator MI=insertions.begin(),
372 ME=insertions.end(); MI!=ME; ++MI){
374 getEdgeCode *edCd=MI->second;
375 bool dummyHasIt=false;
377 DEBUG(cerr<<"Current edge considered---\n";
380 //now check if stDummy has ed
381 for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt;
384 DEBUG(cerr<<"Edge matched with stDummy\n");
387 bool dummyInBe=false;
388 //dummy edge with code
389 for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe; ++BE){
391 Node *st=backEdge.getSecond();
392 Node *dm=ed.getSecond();
394 //so this is the back edge to use
395 DEBUG(cerr<<"Moving to backedge\n";
396 printEdge(backEdge));
398 getEdgeCode *ged=new getEdgeCode();
400 toErase.push_back(ed);
401 insertions[backEdge]=ged;
409 //so exDummy may hv it
410 bool inExDummy=false;
411 for(vec_iter VI=exDummy.begin(), VE=exDummy.end(); VI!=VE && !inExDummy;
415 DEBUG(cerr<<"Edge matched with exDummy\n");
416 bool dummyInBe2=false;
417 //dummy edge with code
418 for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe2;
421 Node *st=backEdge.getFirst();
422 Node *dm=ed.getFirst();
424 //so this is the back edge to use
426 if(insertions[backEdge]==NULL)
427 ged=new getEdgeCode();
429 ged=insertions[backEdge];
430 toErase.push_back(ed);
432 insertions[backEdge]=ged;
442 DEBUG(cerr<<"size of deletions: "<<toErase.size()<<"\n");
444 for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
446 insertions.erase(*vmi);
448 DEBUG(cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n");
451 //Do graph processing: to determine minimal edge increments,
452 //appropriate code insertions etc and insert the code at
453 //appropriate locations
454 void processGraph(Graph &g,
456 Instruction *countInst,
458 vector<Edge >& stDummy,
459 vector<Edge >& exDummy){
460 //Given a graph: with exit->root edge, do the following in seq:
462 //2. insert dummy edges and remove back edges
463 //3. get edge assignments
464 //4. Get Max spanning tree of graph:
465 // -Make graph g2=g undirectional
466 // -Get Max spanning tree t
467 // -Make t undirectional
468 // -remove edges from t not in graph g
469 //5. Get edge increments
470 //6. Get code insertions
471 //7. move code on dummy edges over to the back edges
474 //This is used as maximum "weight" for
476 //This would hold all
477 //right as long as number of paths in the graph
479 const int INFINITY=99999999;
482 //step 1-3 are already done on the graph when this function is called
483 DEBUG(printGraph(g));
485 //step 4: Get Max spanning tree of graph
487 //now insert exit to root edge
488 //if its there earlier, remove it!
489 //assign it weight INFINITY
490 //so that this edge IS ALWAYS IN spanning tree
491 //Note than edges in spanning tree do not get
492 //instrumented: and we do not want the
493 //edge exit->root to get instrumented
494 //as it MAY BE a dummy edge
495 Edge ed(g.getExit(),g.getRoot(),INFINITY);
496 g.addEdge(ed,INFINITY);
499 //make g2 undirectional: this gives a better
500 //maximal spanning tree
501 g2.makeUnDirectional();
502 DEBUG(printGraph(g2));
504 Graph *t=g2.getMaxSpanningTree();
505 DEBUG(printGraph(*t));
507 //now edges of tree t have weights reversed
508 //(negative) because the algorithm used
509 //to find max spanning tree is
510 //actually for finding min spanning tree
511 //so get back the original weights
514 //Ordinarily, the graph is directional
515 //lets converts the graph into an
516 //undirectional graph
517 //This is done by adding an edge
518 //v->u for all existing edges u->v
519 t->makeUnDirectional();
521 //Given a tree t, and a "directed graph" g
522 //replace the edges in the tree t with edges that exist in graph
523 //The tree is formed from "undirectional" copy of graph
524 //So whatever edges the tree has, the undirectional graph
525 //would have too. This function corrects some of the directions in
526 //the tree so that now, all edge directions in the tree match
527 //the edge directions of corresponding edges in the directed graph
528 removeTreeEdges(g, *t);
530 DEBUG(cerr<<"Spanning tree---------\n";
532 cerr<<"-------end spanning tree\n");
534 //now remove the exit->root node
535 //and re-add it with weight 0
536 //since infinite weight is kinda confusing
538 Edge edNew(g.getExit(), g.getRoot(),0);
548 //step 5: Get edge increments
550 //Now we select a subset of all edges
551 //and assign them some values such that
552 //if we consider just this subset, it still represents
553 //the path sum along any path in the graph
554 map<Edge, int> increment=getEdgeIncrements(g,*t);
556 DEBUG(//print edge increments for debugging
557 for(map<Edge, int>::iterator MI=increment.begin(), ME = increment.end();
559 printEdge(MI->first);
560 cerr << "Increment for above:" << MI->second << "\n";
563 //step 6: Get code insertions
565 //Based on edgeIncrements (above), now obtain
566 //the kind of code to be inserted along an edge
567 //The idea here is to minimize the computation
568 //by inserting only the needed code
570 getChords(chords, g, *t);
572 map<Edge, getEdgeCode *> codeInsertions;
573 getCodeInsertions(g, codeInsertions, chords,increment);
575 DEBUG (//print edges with code for debugging
576 cerr<<"Code inserted in following---------------\n";
577 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
578 cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
579 printEdge(cd_i->first);
580 cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
582 cerr<<"-----end insertions\n");
584 //step 7: move code on dummy edges over to the back edges
586 //Move the incoming dummy edge code and outgoing dummy
587 //edge code over to the corresponding back edge
588 moveDummyCode(stDummy, exDummy, be, codeInsertions);
590 DEBUG(//debugging info
591 cerr<<"After moving dummy code\n";
592 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
593 cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
594 printEdge(cd_i->first);
595 cerr<<cd_i->second->getCond()<<":"
596 <<cd_i->second->getInc()<<"\n";
598 cerr<<"Dummy end------------\n");
600 //see what it looks like...
601 //now insert code along edges which have codes on them
602 for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
603 ME=codeInsertions.end(); MI!=ME; ++MI){
605 insertBB(ed, MI->second, rInst, countInst);
611 //print the graph (for debugging)
612 void printGraph(Graph &g){
613 list<Node *> lt=g.getAllNodes();
614 cerr<<"Graph---------------------\n";
615 for(list<Node *>::iterator LI=lt.begin();
617 cerr<<((*LI)->getElement())->getName()<<"->";
618 Graph::nodeList nl=g.getNodeList(*LI);
619 for(Graph::nodeList::iterator NI=nl.begin();
621 cerr<<":"<<"("<<(NI->element->getElement())
622 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
626 cerr<<"--------------------Graph\n";