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/Function.h"
12 #include "llvm/Pass.h"
13 #include "llvm/Module.h"
14 #include "llvm/Function.h"
15 #include "llvm/BasicBlock.h"
16 #include "llvm/InstrTypes.h"
17 #include "llvm/iTerminators.h"
29 //check if 2 edges are equal (same endpoints and same weight)
30 static bool edgesEqual(Edge ed1, Edge ed2){
31 return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
34 //Get the vector of edges that are to be instrumented in the graph
35 static void getChords(vector<Edge > &chords, Graph &g, Graph st){
36 //make sure the spanning tree is directional
37 //iterate over ALL the edges of the graph
38 vector<Node *> allNodes=g.getAllNodes();
39 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
41 Graph::nodeList node_list=g.getNodeList(*NI);
42 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
44 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
45 if(!(st.hasEdgeAndWt(f)))//addnl
51 //Given a tree t, and a "directed graph" g
52 //replace the edges in the tree t with edges that exist in graph
53 //The tree is formed from "undirectional" copy of graph
54 //So whatever edges the tree has, the undirectional graph
55 //would have too. This function corrects some of the directions in
56 //the tree so that now, all edge directions in the tree match
57 //the edge directions of corresponding edges in the directed graph
58 static void removeTreeEdges(Graph &g, Graph& t){
59 vector<Node* > allNodes=t.getAllNodes();
60 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
62 Graph::nodeList nl=t.getNodeList(*NI);
63 for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
64 Edge ed(NLI->element, *NI, NLI->weight);
65 if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
66 //between any pair of vertices, so no need to delete by edge wt
71 //Assign a value to all the edges in the graph
72 //such that if we traverse along any path from root to exit, and
73 //add up the edge values, we get a path number that uniquely
74 //refers to the path we travelled
75 int valueAssignmentToEdges(Graph& g, map<Node *, int> nodePriority,
77 vector<Node *> revtop=g.reverseTopologicalSort();
78 map<Node *,int > NumPaths;
79 for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end();
86 // Modified Graph::nodeList &nlist=g.getNodeList(*RI);
87 Graph::nodeList &nlist=g.getSortedNodeList(*RI, be);
89 //sort nodelist by increasing order of numpaths
93 for(int i=0;i<sz-1; i++){
95 for(int j=i+1; j<sz; j++){
96 BasicBlock *bb1 = nlist[j].element->getElement();
97 BasicBlock *bb2 = nlist[min].element->getElement();
99 if(bb1 == bb2) continue;
101 if(*RI == g.getRoot()){
102 assert(nodePriority[nlist[min].element]!=
103 nodePriority[nlist[j].element]
104 && "priorities can't be same!");
106 if(nodePriority[nlist[j].element] <
107 nodePriority[nlist[min].element])
112 TerminatorInst *tti = (*RI)->getElement()->getTerminator();
114 BranchInst *ti = cast<BranchInst>(tti);
115 assert(ti && "not a branch");
116 assert(ti->getNumSuccessors()==2 && "less successors!");
118 BasicBlock *tB = ti->getSuccessor(0);
119 BasicBlock *fB = ti->getSuccessor(1);
121 if(tB == bb1 || fB == bb2)
126 graphListElement tempEl=nlist[min];
132 for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
134 GLI->weight=NumPaths[*RI];
135 NumPaths[*RI]+=NumPaths[GLI->element];
139 return NumPaths[g.getRoot()];
142 //This is a helper function to get the edge increments
143 //This is used in conjuntion with inc_DFS
144 //to get the edge increments
145 //Edge increment implies assigning a value to all the edges in the graph
146 //such that if we traverse along any path from root to exit, and
147 //add up the edge values, we get a path number that uniquely
148 //refers to the path we travelled
149 //inc_Dir tells whether 2 edges are in same, or in different directions
150 //if same direction, return 1, else -1
151 static int inc_Dir(Edge e, Edge f){
155 //check that the edges must have atleast one common endpoint
156 assert(*(e.getFirst())==*(f.getFirst()) ||
157 *(e.getFirst())==*(f.getSecond()) ||
158 *(e.getSecond())==*(f.getFirst()) ||
159 *(e.getSecond())==*(f.getSecond()));
161 if(*(e.getFirst())==*(f.getSecond()) ||
162 *(e.getSecond())==*(f.getFirst()))
169 //used for getting edge increments (read comments above in inc_Dir)
170 //inc_DFS is a modification of DFS
171 static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare2>& Increment,
172 int events, Node *v, Edge e){
174 vector<Node *> allNodes=t.getAllNodes();
176 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
178 Graph::nodeList node_list=t.getNodeList(*NI);
179 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
181 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
182 if(!edgesEqual(f,e) && *v==*(f.getSecond())){
183 int dir_count=inc_Dir(e,f);
184 int wt=1*f.getWeight();
185 inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
190 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
192 Graph::nodeList node_list=t.getNodeList(*NI);
193 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
195 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
196 if(!edgesEqual(f,e) && *v==*(f.getFirst())){
197 int dir_count=inc_Dir(e,f);
198 int wt=f.getWeight();
199 inc_DFS(g,t, Increment, dir_count*events+wt,
205 allNodes=g.getAllNodes();
206 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
208 Graph::nodeList node_list=g.getNodeList(*NI);
209 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
211 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
212 if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
213 *v==*(f.getFirst()))){
214 int dir_count=inc_Dir(e,f);
215 Increment[f]+=dir_count*events;
221 //Now we select a subset of all edges
222 //and assign them some values such that
223 //if we consider just this subset, it still represents
224 //the path sum along any path in the graph
225 static map<Edge, int, EdgeCompare2> getEdgeIncrements(Graph& g, Graph& t,
227 //get all edges in g-t
228 map<Edge, int, EdgeCompare2> Increment;
230 vector<Node *> allNodes=g.getAllNodes();
232 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
234 Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
235 //modified g.getNodeList(*NI);
236 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
238 Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
239 if(!(t.hasEdgeAndWt(ed))){
246 inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
248 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
250 Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
251 //modified g.getNodeList(*NI);
252 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
254 Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
255 if(!(t.hasEdgeAndWt(ed))){
256 int wt=ed.getWeight();
266 const graphListElement *findNodeInList(const Graph::nodeList &NL,
269 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
272 //Based on edgeIncrements (above), now obtain
273 //the kind of code to be inserted along an edge
274 //The idea here is to minimize the computation
275 //by inserting only the needed code
276 static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare2> &instr,
277 vector<Edge > &chords,
278 map<Edge,int, EdgeCompare2> &edIncrements){
280 //Register initialization code
282 ws.push_back(g.getRoot());
287 Graph::nodeList succs=g.getNodeList(v);
289 for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
291 int edgeWt=nl->weight;
294 Edge ed(v,w, edgeWt, nl->randId);
296 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
297 CI!=CE && !hasEdge;++CI){
298 if(*CI==ed && CI->getWeight()==edgeWt){//modf
303 if(hasEdge){//so its a chord edge
304 getEdgeCode *edCd=new getEdgeCode();
306 edCd->setInc(edIncrements[ed]);
309 else if(g.getNumberOfIncomingEdges(w)==1){
313 getEdgeCode *edCd=new getEdgeCode();
321 /////Memory increment code
322 ws.push_back(g.getExit());
331 vector<Node *> lllt=g.getAllNodes();
332 for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
334 Graph::nodeList &nl = g.getNodeList(lnode);
335 //graphListElement *N = findNodeInList(nl, w);
336 for(Graph::nodeList::const_iterator N = nl.begin(),
337 NNEN = nl.end(); N!= NNEN; ++N){
338 if (*N->element == *w){
342 Edge ed(v,w, N->weight, N->randId);
343 getEdgeCode *edCd=new getEdgeCode();
345 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
347 if(*CI==ed && CI->getWeight()==N->weight){
354 if(instr[ed]!=NULL && instr[ed]->getCond()==1){
355 instr[ed]->setCond(4);
359 edCd->setInc(edIncrements[ed]);
364 else if(g.getNumberOfOutgoingEdges(v)==1)
374 ///// Register increment code
375 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
376 getEdgeCode *edCd=new getEdgeCode();
377 if(instr[*CI]==NULL){
379 edCd->setInc(edIncrements[*CI]);
385 //Add dummy edges corresponding to the back edges
386 //If a->b is a backedge
387 //then incoming dummy edge is root->b
388 //and outgoing dummy edge is a->exit
390 void addDummyEdges(vector<Edge > &stDummy,
391 vector<Edge > &exDummy,
392 Graph &g, vector<Edge> &be){
393 for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
395 Node *first=ed.getFirst();
396 Node *second=ed.getSecond();
399 if(!(*second==*(g.getRoot()))){
400 Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
401 stDummy.push_back(*st);
405 if(!(*first==*(g.getExit()))){
406 Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
407 exDummy.push_back(*ex);
413 //print a given edge in the form BB1Label->BB2Label
414 void printEdge(Edge ed){
415 cerr<<((ed.getFirst())->getElement())
416 ->getName()<<"->"<<((ed.getSecond())
417 ->getElement())->getName()<<
418 ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
421 //Move the incoming dummy edge code and outgoing dummy
422 //edge code over to the corresponding back edge
423 static void moveDummyCode(vector<Edge> &stDummy,
424 vector<Edge> &exDummy,
426 map<Edge, getEdgeCode *, EdgeCompare2> &insertions,
428 typedef vector<Edge >::iterator vec_iter;
430 map<Edge,getEdgeCode *, EdgeCompare2> temp;
431 //iterate over edges with code
432 std::vector<Edge> toErase;
433 for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=insertions.begin(),
434 ME=insertions.end(); MI!=ME; ++MI){
436 getEdgeCode *edCd=MI->second;
439 //iterate over be, and check if its starts and end vertices hv code
440 for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
441 if(ed.getRandId()==BEI->getRandId()){
444 temp[*BEI]=new getEdgeCode();
446 //so ed is either in st, or ex!
447 if(ed.getFirst()==g.getRoot()){
450 temp[*BEI]->setCdIn(edCd);
451 toErase.push_back(ed);
453 else if(ed.getSecond()==g.getExit()){
456 toErase.push_back(ed);
457 temp[*BEI]->setCdOut(edCd);
460 assert(false && "Not found in either start or end! Rand failed?");
466 for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
468 insertions.erase(*vmi);
469 g.removeEdgeWithWt(*vmi);
472 for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=temp.begin(),
473 ME=temp.end(); MI!=ME; ++MI){
474 insertions[MI->first]=MI->second;
477 #ifdef DEBUG_PATH_PROFILES
478 cerr<<"size of deletions: "<<toErase.size()<<"\n";
479 cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
484 //Do graph processing: to determine minimal edge increments,
485 //appropriate code insertions etc and insert the code at
486 //appropriate locations
487 void processGraph(Graph &g,
489 Instruction *countInst,
491 vector<Edge >& stDummy,
492 vector<Edge >& exDummy,
493 int numPaths, int MethNo){
495 //Given a graph: with exit->root edge, do the following in seq:
497 //2. insert dummy edges and remove back edges
498 //3. get edge assignments
499 //4. Get Max spanning tree of graph:
500 // -Make graph g2=g undirectional
501 // -Get Max spanning tree t
502 // -Make t undirectional
503 // -remove edges from t not in graph g
504 //5. Get edge increments
505 //6. Get code insertions
506 //7. move code on dummy edges over to the back edges
509 //This is used as maximum "weight" for
511 //This would hold all
512 //right as long as number of paths in the graph
514 const int INFINITY=99999999;
517 //step 1-3 are already done on the graph when this function is called
518 DEBUG(printGraph(g));
520 //step 4: Get Max spanning tree of graph
522 //now insert exit to root edge
523 //if its there earlier, remove it!
524 //assign it weight INFINITY
525 //so that this edge IS ALWAYS IN spanning tree
526 //Note than edges in spanning tree do not get
527 //instrumented: and we do not want the
528 //edge exit->root to get instrumented
529 //as it MAY BE a dummy edge
530 Edge ed(g.getExit(),g.getRoot(),INFINITY);
531 g.addEdge(ed,INFINITY);
534 //make g2 undirectional: this gives a better
535 //maximal spanning tree
536 g2.makeUnDirectional();
537 DEBUG(printGraph(g2));
539 Graph *t=g2.getMaxSpanningTree();
540 #ifdef DEBUG_PATH_PROFILES
541 std::cerr<<"Original maxspanning tree\n";
544 //now edges of tree t have weights reversed
545 //(negative) because the algorithm used
546 //to find max spanning tree is
547 //actually for finding min spanning tree
548 //so get back the original weights
551 //Ordinarily, the graph is directional
552 //lets converts the graph into an
553 //undirectional graph
554 //This is done by adding an edge
555 //v->u for all existing edges u->v
556 t->makeUnDirectional();
558 //Given a tree t, and a "directed graph" g
559 //replace the edges in the tree t with edges that exist in graph
560 //The tree is formed from "undirectional" copy of graph
561 //So whatever edges the tree has, the undirectional graph
562 //would have too. This function corrects some of the directions in
563 //the tree so that now, all edge directions in the tree match
564 //the edge directions of corresponding edges in the directed graph
565 removeTreeEdges(g, *t);
567 #ifdef DEBUG_PATH_PROFILES
568 cerr<<"Final Spanning tree---------\n";
570 cerr<<"-------end spanning tree\n";
573 //now remove the exit->root node
574 //and re-add it with weight 0
575 //since infinite weight is kinda confusing
577 Edge edNew(g.getExit(), g.getRoot(),0);
587 //step 5: Get edge increments
589 //Now we select a subset of all edges
590 //and assign them some values such that
591 //if we consider just this subset, it still represents
592 //the path sum along any path in the graph
594 map<Edge, int, EdgeCompare2> increment=getEdgeIncrements(g,*t, be);
595 #ifdef DEBUG_PATH_PROFILES
596 //print edge increments for debugging
597 std::cerr<<"Edge Increments------\n";
598 for(map<Edge, int, EdgeCompare2>::iterator MMI=increment.begin(), MME=increment.end(); MMI != MME; ++MMI){
599 printEdge(MMI->first);
600 std::cerr<<"Increment for above:"<<MMI->second<<"\n";
602 std::cerr<<"-------end of edge increments\n";
606 //step 6: Get code insertions
608 //Based on edgeIncrements (above), now obtain
609 //the kind of code to be inserted along an edge
610 //The idea here is to minimize the computation
611 //by inserting only the needed code
613 getChords(chords, g, *t);
616 map<Edge, getEdgeCode *, EdgeCompare2> codeInsertions;
617 getCodeInsertions(g, codeInsertions, chords,increment);
619 #ifdef DEBUG_PATH_PROFILES
620 //print edges with code for debugging
621 cerr<<"Code inserted in following---------------\n";
622 for(map<Edge, getEdgeCode *, EdgeCompare2>::iterator cd_i=codeInsertions.begin(),
623 cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
624 printEdge(cd_i->first);
625 cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
627 cerr<<"-----end insertions\n";
630 //step 7: move code on dummy edges over to the back edges
632 //Move the incoming dummy edge code and outgoing dummy
633 //edge code over to the corresponding back edge
635 moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
637 #ifdef DEBUG_PATH_PROFILES
639 cerr<<"After moving dummy code\n";
640 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
641 cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
642 printEdge(cd_i->first);
643 cerr<<cd_i->second->getCond()<<":"
644 <<cd_i->second->getInc()<<"\n";
646 cerr<<"Dummy end------------\n";
650 //see what it looks like...
651 //now insert code along edges which have codes on them
652 for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
653 ME=codeInsertions.end(); MI!=ME; ++MI){
655 insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo);
659 //print the graph (for debugging)
660 void printGraph(Graph &g){
661 vector<Node *> lt=g.getAllNodes();
662 cerr<<"Graph---------------------\n";
663 for(vector<Node *>::iterator LI=lt.begin();
665 cerr<<((*LI)->getElement())->getName()<<"->";
666 Graph::nodeList nl=g.getNodeList(*LI);
667 for(Graph::nodeList::iterator NI=nl.begin();
669 cerr<<":"<<"("<<(NI->element->getElement())
670 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
675 cerr<<"--------------------Graph\n";