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 //===----------------------------------------------------------------------===//
9 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
10 #include "llvm/Function.h"
11 #include "llvm/Pass.h"
12 #include "llvm/BasicBlock.h"
13 #include "llvm/InstrTypes.h"
14 #include "llvm/Transforms/Instrumentation/Graph.h"
15 #include "llvm/iTerminators.h"
26 //check if 2 edges are equal (same endpoints and same weight)
27 static bool edgesEqual(Edge ed1, Edge ed2){
28 return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
31 //Get the vector of edges that are to be instrumented in the graph
32 static void getChords(vector<Edge > &chords, Graph &g, Graph st){
33 //make sure the spanning tree is directional
34 //iterate over ALL the edges of the graph
35 vector<Node *> allNodes=g.getAllNodes();
36 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
38 Graph::nodeList node_list=g.getNodeList(*NI);
39 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
41 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
42 if(!(st.hasEdgeAndWt(f)))//addnl
48 //Given a tree t, and a "directed graph" g
49 //replace the edges in the tree t with edges that exist in graph
50 //The tree is formed from "undirectional" copy of graph
51 //So whatever edges the tree has, the undirectional graph
52 //would have too. This function corrects some of the directions in
53 //the tree so that now, all edge directions in the tree match
54 //the edge directions of corresponding edges in the directed graph
55 static void removeTreeEdges(Graph &g, Graph& t){
56 vector<Node* > allNodes=t.getAllNodes();
57 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
59 Graph::nodeList nl=t.getNodeList(*NI);
60 for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
61 Edge ed(NLI->element, *NI, NLI->weight);
62 if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
63 //between any pair of vertices, so no need to delete by edge wt
68 //Assign a value to all the edges in the graph
69 //such that if we traverse along any path from root to exit, and
70 //add up the edge values, we get a path number that uniquely
71 //refers to the path we travelled
72 int valueAssignmentToEdges(Graph& g, map<Node *, int> nodePriority){
73 vector<Node *> revtop=g.reverseTopologicalSort();
74 map<Node *,int > NumPaths;
75 for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end();
82 Graph::nodeList &nlist=g.getNodeList(*RI);
83 //sort nodelist by increasing order of numpaths
87 for(int i=0;i<sz-1; i++){
89 for(int j=i+1; j<sz; j++){
90 BasicBlock *bb1 = nlist[j].element->getElement();
91 BasicBlock *bb2 = nlist[min].element->getElement();
93 if(bb1 == bb2) continue;
95 if(*RI == g.getRoot()){
96 assert(nodePriority[nlist[min].element]!=
97 nodePriority[nlist[j].element]
98 && "priorities can't be same!");
100 if(nodePriority[nlist[j].element] <
101 nodePriority[nlist[min].element])
106 TerminatorInst *tti = (*RI)->getElement()->getTerminator();
107 //std::cerr<<*tti<<std::endl;
108 BranchInst *ti = cast<BranchInst>(tti);
109 assert(ti && "not a branch");
110 assert(ti->getNumSuccessors()==2 && "less successors!");
112 BasicBlock *tB = ti->getSuccessor(0);
113 BasicBlock *fB = ti->getSuccessor(1);
115 if(tB == bb1 || fB == bb2)
120 graphListElement tempEl=nlist[min];
126 //std::cerr<<"Considering Order-----\n";
127 for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
129 //std::cerr<<GLI->element->getElement()->getName()<<"->";
130 GLI->weight=NumPaths[*RI];
131 NumPaths[*RI]+=NumPaths[GLI->element];
133 //std::cerr<<"\nend order $$$$$$$$$$$$$$$$$$$$$$$$\n";
136 return NumPaths[g.getRoot()];
139 //This is a helper function to get the edge increments
140 //This is used in conjuntion with inc_DFS
141 //to get the edge increments
142 //Edge increment implies assigning a value to all the edges in the graph
143 //such that if we traverse along any path from root to exit, and
144 //add up the edge values, we get a path number that uniquely
145 //refers to the path we travelled
146 //inc_Dir tells whether 2 edges are in same, or in different directions
147 //if same direction, return 1, else -1
148 static int inc_Dir(Edge e, Edge f){
152 //check that the edges must have atleast one common endpoint
153 assert(*(e.getFirst())==*(f.getFirst()) ||
154 *(e.getFirst())==*(f.getSecond()) ||
155 *(e.getSecond())==*(f.getFirst()) ||
156 *(e.getSecond())==*(f.getSecond()));
158 if(*(e.getFirst())==*(f.getSecond()) ||
159 *(e.getSecond())==*(f.getFirst()))
166 //used for getting edge increments (read comments above in inc_Dir)
167 //inc_DFS is a modification of DFS
168 static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare>& Increment,
169 int events, Node *v, Edge e){
171 vector<Node *> allNodes=t.getAllNodes();
173 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
175 Graph::nodeList node_list=t.getNodeList(*NI);
176 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
178 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
179 if(!edgesEqual(f,e) && *v==*(f.getSecond())){
180 int dir_count=inc_Dir(e,f);
181 int wt=1*f.getWeight();
182 inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
187 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
189 Graph::nodeList node_list=t.getNodeList(*NI);
190 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
192 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
193 if(!edgesEqual(f,e) && *v==*(f.getFirst())){
194 int dir_count=inc_Dir(e,f);
195 int wt=f.getWeight();
196 inc_DFS(g,t, Increment, dir_count*events+wt,
202 allNodes=g.getAllNodes();
203 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
205 Graph::nodeList node_list=g.getNodeList(*NI);
206 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
208 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
209 if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
210 *v==*(f.getFirst()))){
211 int dir_count=inc_Dir(e,f);
212 Increment[f]+=dir_count*events;
218 //Now we select a subset of all edges
219 //and assign them some values such that
220 //if we consider just this subset, it still represents
221 //the path sum along any path in the graph
222 static map<Edge, int, EdgeCompare> getEdgeIncrements(Graph& g, Graph& t){
223 //get all edges in g-t
224 map<Edge, int, EdgeCompare> Increment;
226 vector<Node *> allNodes=g.getAllNodes();
228 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
230 Graph::nodeList node_list=g.getNodeList(*NI);
231 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
233 Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
234 if(!(t.hasEdgeAndWt(ed))){
241 inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
243 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
245 Graph::nodeList node_list=g.getNodeList(*NI);
246 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
248 Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
249 if(!(t.hasEdgeAndWt(ed))){
250 int wt=ed.getWeight();
260 const graphListElement *findNodeInList(const Graph::nodeList &NL,
263 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
266 //Based on edgeIncrements (above), now obtain
267 //the kind of code to be inserted along an edge
268 //The idea here is to minimize the computation
269 //by inserting only the needed code
270 static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare> &instr,
271 vector<Edge > &chords,
272 map<Edge,int, EdgeCompare> &edIncrements){
274 //Register initialization code
276 ws.push_back(g.getRoot());
281 Graph::nodeList succs=g.getNodeList(v);
283 for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
285 int edgeWt=nl->weight;
288 Edge ed(v,w, edgeWt, nl->randId);
290 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
291 CI!=CE && !hasEdge;++CI){
292 if(*CI==ed && CI->getWeight()==edgeWt){//modf
297 if(hasEdge){//so its a chord edge
298 getEdgeCode *edCd=new getEdgeCode();
300 edCd->setInc(edIncrements[ed]);
303 else if(g.getNumberOfIncomingEdges(w)==1){
305 //std::cerr<<"Added w\n";
308 getEdgeCode *edCd=new getEdgeCode();
312 //std::cerr<<"Case 2\n";
317 /////Memory increment code
318 ws.push_back(g.getExit());
327 vector<Node *> lllt=g.getAllNodes();
328 for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
330 Graph::nodeList &nl = g.getNodeList(lnode);
331 graphListElement *N = findNodeInList(nl, w);
336 Edge ed(v,w, N->weight, N->randId);
337 getEdgeCode *edCd=new getEdgeCode();
339 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
341 if(*CI==ed && CI->getWeight()==N->weight){
348 if(instr[ed]!=NULL && instr[ed]->getCond()==1){
349 instr[ed]->setCond(4);
353 edCd->setInc(edIncrements[ed]);
358 else if(g.getNumberOfOutgoingEdges(v)==1)
367 ///// Register increment code
368 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
369 getEdgeCode *edCd=new getEdgeCode();
370 if(instr[*CI]==NULL){
372 edCd->setInc(edIncrements[*CI]);
378 //Add dummy edges corresponding to the back edges
379 //If a->b is a backedge
380 //then incoming dummy edge is root->b
381 //and outgoing dummy edge is a->exit
383 void addDummyEdges(vector<Edge > &stDummy,
384 vector<Edge > &exDummy,
385 Graph &g, vector<Edge> &be){
386 for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
388 Node *first=ed.getFirst();
389 Node *second=ed.getSecond();
392 if(!(*second==*(g.getRoot()))){
393 Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
394 stDummy.push_back(*st);
398 if(!(*first==*(g.getExit()))){
399 Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
400 exDummy.push_back(*ex);
406 //print a given edge in the form BB1Label->BB2Label
407 void printEdge(Edge ed){
408 cerr<<((ed.getFirst())->getElement())
409 ->getName()<<"->"<<((ed.getSecond())
410 ->getElement())->getName()<<
411 ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
414 //Move the incoming dummy edge code and outgoing dummy
415 //edge code over to the corresponding back edge
416 static void moveDummyCode(vector<Edge> &stDummy,
417 vector<Edge> &exDummy,
419 map<Edge, getEdgeCode *, EdgeCompare> &insertions,
421 typedef vector<Edge >::iterator vec_iter;
423 map<Edge,getEdgeCode *, EdgeCompare> temp;
424 //iterate over edges with code
425 std::vector<Edge> toErase;
426 for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=insertions.begin(),
427 ME=insertions.end(); MI!=ME; ++MI){
429 getEdgeCode *edCd=MI->second;
432 //iterate over be, and check if its starts and end vertices hv code
433 for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
434 if(ed.getRandId()==BEI->getRandId()){
437 temp[*BEI]=new getEdgeCode();
439 //so ed is either in st, or ex!
440 if(ed.getFirst()==g.getRoot()){
443 temp[*BEI]->setCdIn(edCd);
444 toErase.push_back(ed);
446 else if(ed.getSecond()==g.getExit()){
449 toErase.push_back(ed);
450 temp[*BEI]->setCdOut(edCd);
453 assert(false && "Not found in either start or end! Rand failed?");
459 for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
461 insertions.erase(*vmi);
462 g.removeEdgeWithWt(*vmi);
465 for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=temp.begin(),
466 ME=temp.end(); MI!=ME; ++MI){
467 insertions[MI->first]=MI->second;
470 #ifdef DEBUG_PATH_PROFILES
471 cerr<<"size of deletions: "<<toErase.size()<<"\n";
472 cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
477 //Do graph processing: to determine minimal edge increments,
478 //appropriate code insertions etc and insert the code at
479 //appropriate locations
480 void processGraph(Graph &g,
482 Instruction *countInst,
484 vector<Edge >& stDummy,
485 vector<Edge >& exDummy,
486 int numPaths, int MethNo){
488 //Given a graph: with exit->root edge, do the following in seq:
490 //2. insert dummy edges and remove back edges
491 //3. get edge assignments
492 //4. Get Max spanning tree of graph:
493 // -Make graph g2=g undirectional
494 // -Get Max spanning tree t
495 // -Make t undirectional
496 // -remove edges from t not in graph g
497 //5. Get edge increments
498 //6. Get code insertions
499 //7. move code on dummy edges over to the back edges
502 //This is used as maximum "weight" for
504 //This would hold all
505 //right as long as number of paths in the graph
507 const int INFINITY=99999999;
510 //step 1-3 are already done on the graph when this function is called
511 DEBUG(printGraph(g));
513 //step 4: Get Max spanning tree of graph
515 //now insert exit to root edge
516 //if its there earlier, remove it!
517 //assign it weight INFINITY
518 //so that this edge IS ALWAYS IN spanning tree
519 //Note than edges in spanning tree do not get
520 //instrumented: and we do not want the
521 //edge exit->root to get instrumented
522 //as it MAY BE a dummy edge
523 Edge ed(g.getExit(),g.getRoot(),INFINITY);
524 g.addEdge(ed,INFINITY);
527 //make g2 undirectional: this gives a better
528 //maximal spanning tree
529 g2.makeUnDirectional();
530 DEBUG(printGraph(g2));
532 Graph *t=g2.getMaxSpanningTree();
533 #ifdef DEBUG_PATH_PROFILES
534 std::cerr<<"Original maxspanning tree\n";
537 //now edges of tree t have weights reversed
538 //(negative) because the algorithm used
539 //to find max spanning tree is
540 //actually for finding min spanning tree
541 //so get back the original weights
544 //Ordinarily, the graph is directional
545 //lets converts the graph into an
546 //undirectional graph
547 //This is done by adding an edge
548 //v->u for all existing edges u->v
549 t->makeUnDirectional();
551 //Given a tree t, and a "directed graph" g
552 //replace the edges in the tree t with edges that exist in graph
553 //The tree is formed from "undirectional" copy of graph
554 //So whatever edges the tree has, the undirectional graph
555 //would have too. This function corrects some of the directions in
556 //the tree so that now, all edge directions in the tree match
557 //the edge directions of corresponding edges in the directed graph
558 removeTreeEdges(g, *t);
560 #ifdef DEBUG_PATH_PROFILES
561 cerr<<"Final Spanning tree---------\n";
563 cerr<<"-------end spanning tree\n";
566 //now remove the exit->root node
567 //and re-add it with weight 0
568 //since infinite weight is kinda confusing
570 Edge edNew(g.getExit(), g.getRoot(),0);
580 //step 5: Get edge increments
582 //Now we select a subset of all edges
583 //and assign them some values such that
584 //if we consider just this subset, it still represents
585 //the path sum along any path in the graph
587 map<Edge, int, EdgeCompare> increment=getEdgeIncrements(g,*t);
588 #ifdef DEBUG_PATH_PROFILES
589 //print edge increments for debugging
591 for(map<Edge, int, EdgeCompare>::iterator M_I=increment.begin(), M_E=increment.end();
593 printEdge(M_I->first);
594 cerr<<"Increment for above:"<<M_I->second<<"\n";
599 //step 6: Get code insertions
601 //Based on edgeIncrements (above), now obtain
602 //the kind of code to be inserted along an edge
603 //The idea here is to minimize the computation
604 //by inserting only the needed code
606 getChords(chords, g, *t);
609 //cerr<<"Graph before getCodeInsertion:\n";
611 map<Edge, getEdgeCode *, EdgeCompare> codeInsertions;
612 getCodeInsertions(g, codeInsertions, chords,increment);
614 #ifdef DEBUG_PATH_PROFILES
615 //print edges with code for debugging
616 cerr<<"Code inserted in following---------------\n";
617 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
618 cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
619 printEdge(cd_i->first);
620 cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
622 cerr<<"-----end insertions\n";
625 //step 7: move code on dummy edges over to the back edges
627 //Move the incoming dummy edge code and outgoing dummy
628 //edge code over to the corresponding back edge
630 moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
632 #ifdef DEBUG_PATH_PROFILES
634 cerr<<"After moving dummy code\n";
635 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
636 cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
637 printEdge(cd_i->first);
638 cerr<<cd_i->second->getCond()<<":"
639 <<cd_i->second->getInc()<<"\n";
641 cerr<<"Dummy end------------\n";
645 //see what it looks like...
646 //now insert code along edges which have codes on them
647 for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
648 ME=codeInsertions.end(); MI!=ME; ++MI){
650 insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo);
654 //print the graph (for debugging)
655 void printGraph(Graph &g){
656 vector<Node *> lt=g.getAllNodes();
657 cerr<<"Graph---------------------\n";
658 for(vector<Node *>::iterator LI=lt.begin();
660 cerr<<((*LI)->getElement())->getName()<<"->";
661 Graph::nodeList nl=g.getNodeList(*LI);
662 for(Graph::nodeList::iterator NI=nl.begin();
664 cerr<<":"<<"("<<(NI->element->getElement())
665 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
670 cerr<<"--------------------Graph\n";