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/Transforms/Instrumentation/Graph.h"
11 #include "llvm/Pass.h"
12 #include "llvm/Module.h"
13 #include "llvm/InstrTypes.h"
14 #include "llvm/iTerminators.h"
25 //check if 2 edges are equal (same endpoints and same weight)
26 static bool edgesEqual(Edge ed1, Edge ed2){
27 return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
30 //Get the vector of edges that are to be instrumented in the graph
31 static void getChords(vector<Edge > &chords, Graph &g, Graph st){
32 //make sure the spanning tree is directional
33 //iterate over ALL the edges of the graph
34 vector<Node *> allNodes=g.getAllNodes();
35 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
37 Graph::nodeList node_list=g.getNodeList(*NI);
38 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
40 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
41 if(!(st.hasEdgeAndWt(f)))//addnl
47 //Given a tree t, and a "directed graph" g
48 //replace the edges in the tree t with edges that exist in graph
49 //The tree is formed from "undirectional" copy of graph
50 //So whatever edges the tree has, the undirectional graph
51 //would have too. This function corrects some of the directions in
52 //the tree so that now, all edge directions in the tree match
53 //the edge directions of corresponding edges in the directed graph
54 static void removeTreeEdges(Graph &g, Graph& t){
55 vector<Node* > allNodes=t.getAllNodes();
56 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
58 Graph::nodeList nl=t.getNodeList(*NI);
59 for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
60 Edge ed(NLI->element, *NI, NLI->weight);
61 if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
62 //between any pair of vertices, so no need to delete by edge wt
67 //Assign a value to all the edges in the graph
68 //such that if we traverse along any path from root to exit, and
69 //add up the edge values, we get a path number that uniquely
70 //refers to the path we travelled
71 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 // Modified Graph::nodeList &nlist=g.getNodeList(*RI);
83 Graph::nodeList &nlist=g.getSortedNodeList(*RI, be);
85 //sort nodelist by increasing order of numpaths
89 for(int i=0;i<sz-1; i++){
91 for(int j=i+1; j<sz; j++){
92 BasicBlock *bb1 = nlist[j].element->getElement();
93 BasicBlock *bb2 = nlist[min].element->getElement();
95 if(bb1 == bb2) continue;
97 if(*RI == g.getRoot()){
98 assert(nodePriority[nlist[min].element]!=
99 nodePriority[nlist[j].element]
100 && "priorities can't be same!");
102 if(nodePriority[nlist[j].element] <
103 nodePriority[nlist[min].element])
108 TerminatorInst *tti = (*RI)->getElement()->getTerminator();
110 BranchInst *ti = cast<BranchInst>(tti);
111 assert(ti && "not a branch");
112 assert(ti->getNumSuccessors()==2 && "less successors!");
114 BasicBlock *tB = ti->getSuccessor(0);
115 BasicBlock *fB = ti->getSuccessor(1);
117 if(tB == bb1 || fB == bb2)
122 graphListElement tempEl=nlist[min];
128 for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
130 GLI->weight=NumPaths[*RI];
131 NumPaths[*RI]+=NumPaths[GLI->element];
135 return NumPaths[g.getRoot()];
138 //This is a helper function to get the edge increments
139 //This is used in conjuntion with inc_DFS
140 //to get the edge increments
141 //Edge increment implies assigning a value to all the edges in the graph
142 //such that if we traverse along any path from root to exit, and
143 //add up the edge values, we get a path number that uniquely
144 //refers to the path we travelled
145 //inc_Dir tells whether 2 edges are in same, or in different directions
146 //if same direction, return 1, else -1
147 static int inc_Dir(Edge e, Edge f){
151 //check that the edges must have atleast one common endpoint
152 assert(*(e.getFirst())==*(f.getFirst()) ||
153 *(e.getFirst())==*(f.getSecond()) ||
154 *(e.getSecond())==*(f.getFirst()) ||
155 *(e.getSecond())==*(f.getSecond()));
157 if(*(e.getFirst())==*(f.getSecond()) ||
158 *(e.getSecond())==*(f.getFirst()))
165 //used for getting edge increments (read comments above in inc_Dir)
166 //inc_DFS is a modification of DFS
167 static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare2>& Increment,
168 int events, Node *v, Edge e){
170 vector<Node *> allNodes=t.getAllNodes();
172 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
174 Graph::nodeList node_list=t.getNodeList(*NI);
175 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
177 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
178 if(!edgesEqual(f,e) && *v==*(f.getSecond())){
179 int dir_count=inc_Dir(e,f);
180 int wt=1*f.getWeight();
181 inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
186 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
188 Graph::nodeList node_list=t.getNodeList(*NI);
189 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
191 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
192 if(!edgesEqual(f,e) && *v==*(f.getFirst())){
193 int dir_count=inc_Dir(e,f);
194 int wt=f.getWeight();
195 inc_DFS(g,t, Increment, dir_count*events+wt,
201 allNodes=g.getAllNodes();
202 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
204 Graph::nodeList node_list=g.getNodeList(*NI);
205 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
207 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
208 if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
209 *v==*(f.getFirst()))){
210 int dir_count=inc_Dir(e,f);
211 Increment[f]+=dir_count*events;
217 //Now we select a subset of all edges
218 //and assign them some values such that
219 //if we consider just this subset, it still represents
220 //the path sum along any path in the graph
221 static map<Edge, int, EdgeCompare2> getEdgeIncrements(Graph& g, Graph& t,
223 //get all edges in g-t
224 map<Edge, int, EdgeCompare2> 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.getSortedNodeList(*NI, be);
231 //modified g.getNodeList(*NI);
232 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
234 Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
235 if(!(t.hasEdgeAndWt(ed))){
242 inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
244 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
246 Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
247 //modified g.getNodeList(*NI);
248 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
250 Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
251 if(!(t.hasEdgeAndWt(ed))){
252 int wt=ed.getWeight();
262 const graphListElement *findNodeInList(const Graph::nodeList &NL,
265 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
268 //Based on edgeIncrements (above), now obtain
269 //the kind of code to be inserted along an edge
270 //The idea here is to minimize the computation
271 //by inserting only the needed code
272 static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare2> &instr,
273 vector<Edge > &chords,
274 map<Edge,int, EdgeCompare2> &edIncrements){
276 //Register initialization code
278 ws.push_back(g.getRoot());
283 Graph::nodeList succs=g.getNodeList(v);
285 for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
287 int edgeWt=nl->weight;
290 Edge ed(v,w, edgeWt, nl->randId);
292 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
293 CI!=CE && !hasEdge;++CI){
294 if(*CI==ed && CI->getWeight()==edgeWt){//modf
299 if(hasEdge){//so its a chord edge
300 getEdgeCode *edCd=new getEdgeCode();
302 edCd->setInc(edIncrements[ed]);
305 else if(g.getNumberOfIncomingEdges(w)==1){
309 getEdgeCode *edCd=new getEdgeCode();
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);
332 for(Graph::nodeList::const_iterator N = nl.begin(),
333 NNEN = nl.end(); N!= NNEN; ++N){
334 if (*N->element == *w){
338 Edge ed(v,w, N->weight, N->randId);
339 getEdgeCode *edCd=new getEdgeCode();
341 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
343 if(*CI==ed && CI->getWeight()==N->weight){
350 if(instr[ed]!=NULL && instr[ed]->getCond()==1){
351 instr[ed]->setCond(4);
355 edCd->setInc(edIncrements[ed]);
360 else if(g.getNumberOfOutgoingEdges(v)==1)
370 ///// Register increment code
371 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
372 getEdgeCode *edCd=new getEdgeCode();
373 if(instr[*CI]==NULL){
375 edCd->setInc(edIncrements[*CI]);
381 //Add dummy edges corresponding to the back edges
382 //If a->b is a backedge
383 //then incoming dummy edge is root->b
384 //and outgoing dummy edge is a->exit
386 void addDummyEdges(vector<Edge > &stDummy,
387 vector<Edge > &exDummy,
388 Graph &g, vector<Edge> &be){
389 for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
391 Node *first=ed.getFirst();
392 Node *second=ed.getSecond();
395 if(!(*second==*(g.getRoot()))){
396 Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
397 stDummy.push_back(*st);
401 if(!(*first==*(g.getExit()))){
402 Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
403 exDummy.push_back(*ex);
409 //print a given edge in the form BB1Label->BB2Label
410 void printEdge(Edge ed){
411 cerr<<((ed.getFirst())->getElement())
412 ->getName()<<"->"<<((ed.getSecond())
413 ->getElement())->getName()<<
414 ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
417 //Move the incoming dummy edge code and outgoing dummy
418 //edge code over to the corresponding back edge
419 static void moveDummyCode(vector<Edge> &stDummy,
420 vector<Edge> &exDummy,
422 map<Edge, getEdgeCode *, EdgeCompare2> &insertions,
424 typedef vector<Edge >::iterator vec_iter;
426 map<Edge,getEdgeCode *, EdgeCompare2> temp;
427 //iterate over edges with code
428 std::vector<Edge> toErase;
429 for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=insertions.begin(),
430 ME=insertions.end(); MI!=ME; ++MI){
432 getEdgeCode *edCd=MI->second;
435 //iterate over be, and check if its starts and end vertices hv code
436 for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
437 if(ed.getRandId()==BEI->getRandId()){
440 temp[*BEI]=new getEdgeCode();
442 //so ed is either in st, or ex!
443 if(ed.getFirst()==g.getRoot()){
446 temp[*BEI]->setCdIn(edCd);
447 toErase.push_back(ed);
449 else if(ed.getSecond()==g.getExit()){
452 toErase.push_back(ed);
453 temp[*BEI]->setCdOut(edCd);
456 assert(false && "Not found in either start or end! Rand failed?");
462 for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
464 insertions.erase(*vmi);
465 g.removeEdgeWithWt(*vmi);
468 for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=temp.begin(),
469 ME=temp.end(); MI!=ME; ++MI){
470 insertions[MI->first]=MI->second;
473 #ifdef DEBUG_PATH_PROFILES
474 cerr<<"size of deletions: "<<toErase.size()<<"\n";
475 cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
480 //Do graph processing: to determine minimal edge increments,
481 //appropriate code insertions etc and insert the code at
482 //appropriate locations
483 void processGraph(Graph &g,
485 Instruction *countInst,
487 vector<Edge >& stDummy,
488 vector<Edge >& exDummy,
489 int numPaths, int MethNo){
491 //Given a graph: with exit->root edge, do the following in seq:
493 //2. insert dummy edges and remove back edges
494 //3. get edge assignments
495 //4. Get Max spanning tree of graph:
496 // -Make graph g2=g undirectional
497 // -Get Max spanning tree t
498 // -Make t undirectional
499 // -remove edges from t not in graph g
500 //5. Get edge increments
501 //6. Get code insertions
502 //7. move code on dummy edges over to the back edges
505 //This is used as maximum "weight" for
507 //This would hold all
508 //right as long as number of paths in the graph
510 const int Infinity=99999999;
513 //step 1-3 are already done on the graph when this function is called
514 DEBUG(printGraph(g));
516 //step 4: Get Max spanning tree of graph
518 //now insert exit to root edge
519 //if its there earlier, remove it!
520 //assign it weight Infinity
521 //so that this edge IS ALWAYS IN spanning tree
522 //Note than edges in spanning tree do not get
523 //instrumented: and we do not want the
524 //edge exit->root to get instrumented
525 //as it MAY BE a dummy edge
526 Edge ed(g.getExit(),g.getRoot(),Infinity);
527 g.addEdge(ed,Infinity);
530 //make g2 undirectional: this gives a better
531 //maximal spanning tree
532 g2.makeUnDirectional();
533 DEBUG(printGraph(g2));
535 Graph *t=g2.getMaxSpanningTree();
536 #ifdef DEBUG_PATH_PROFILES
537 std::cerr<<"Original maxspanning tree\n";
540 //now edges of tree t have weights reversed
541 //(negative) because the algorithm used
542 //to find max spanning tree is
543 //actually for finding min spanning tree
544 //so get back the original weights
547 //Ordinarily, the graph is directional
548 //lets converts the graph into an
549 //undirectional graph
550 //This is done by adding an edge
551 //v->u for all existing edges u->v
552 t->makeUnDirectional();
554 //Given a tree t, and a "directed graph" g
555 //replace the edges in the tree t with edges that exist in graph
556 //The tree is formed from "undirectional" copy of graph
557 //So whatever edges the tree has, the undirectional graph
558 //would have too. This function corrects some of the directions in
559 //the tree so that now, all edge directions in the tree match
560 //the edge directions of corresponding edges in the directed graph
561 removeTreeEdges(g, *t);
563 #ifdef DEBUG_PATH_PROFILES
564 cerr<<"Final Spanning tree---------\n";
566 cerr<<"-------end spanning tree\n";
569 //now remove the exit->root node
570 //and re-add it with weight 0
571 //since infinite weight is kinda confusing
573 Edge edNew(g.getExit(), g.getRoot(),0);
583 //step 5: Get edge increments
585 //Now we select a subset of all edges
586 //and assign them some values such that
587 //if we consider just this subset, it still represents
588 //the path sum along any path in the graph
590 map<Edge, int, EdgeCompare2> increment=getEdgeIncrements(g,*t, be);
591 #ifdef DEBUG_PATH_PROFILES
592 //print edge increments for debugging
593 std::cerr<<"Edge Increments------\n";
594 for(map<Edge, int, EdgeCompare2>::iterator MMI=increment.begin(), MME=increment.end(); MMI != MME; ++MMI){
595 printEdge(MMI->first);
596 std::cerr<<"Increment for above:"<<MMI->second<<"\n";
598 std::cerr<<"-------end of edge increments\n";
602 //step 6: Get code insertions
604 //Based on edgeIncrements (above), now obtain
605 //the kind of code to be inserted along an edge
606 //The idea here is to minimize the computation
607 //by inserting only the needed code
609 getChords(chords, g, *t);
612 map<Edge, getEdgeCode *, EdgeCompare2> codeInsertions;
613 getCodeInsertions(g, codeInsertions, chords,increment);
615 #ifdef DEBUG_PATH_PROFILES
616 //print edges with code for debugging
617 cerr<<"Code inserted in following---------------\n";
618 for(map<Edge, getEdgeCode *, EdgeCompare2>::iterator cd_i=codeInsertions.begin(),
619 cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
620 printEdge(cd_i->first);
621 cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
623 cerr<<"-----end insertions\n";
626 //step 7: move code on dummy edges over to the back edges
628 //Move the incoming dummy edge code and outgoing dummy
629 //edge code over to the corresponding back edge
631 moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
633 #ifdef DEBUG_PATH_PROFILES
635 cerr<<"After moving dummy code\n";
636 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
637 cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
638 printEdge(cd_i->first);
639 cerr<<cd_i->second->getCond()<<":"
640 <<cd_i->second->getInc()<<"\n";
642 cerr<<"Dummy end------------\n";
646 //see what it looks like...
647 //now insert code along edges which have codes on them
648 for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
649 ME=codeInsertions.end(); MI!=ME; ++MI){
651 insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo);
655 //print the graph (for debugging)
656 void printGraph(Graph &g){
657 vector<Node *> lt=g.getAllNodes();
658 cerr<<"Graph---------------------\n";
659 for(vector<Node *>::iterator LI=lt.begin();
661 cerr<<((*LI)->getElement())->getName()<<"->";
662 Graph::nodeList nl=g.getNodeList(*LI);
663 for(Graph::nodeList::iterator NI=nl.begin();
665 cerr<<":"<<"("<<(NI->element->getElement())
666 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
671 cerr<<"--------------------Graph\n";