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"
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){
72 vector<Node *> revtop=g.reverseTopologicalSort();
73 map<Node *,int > NumPaths;
74 for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end();
81 Graph::nodeList &nlist=g.getNodeList(*RI);
82 //sort nodelist by increasing order of numpaths
87 //std::cerr<<"node list------------\n";
88 //for(Graph::nodeList::iterator NLI=nlist.begin(), NLE=nlist.end();
90 //std::cerr<<NLI->element->getElement()->getName()<<"->";
92 //std::cerr<<"\n-----------\n";
94 for(int i=0;i<sz-1; i++){
96 for(int j=i+1; j<sz; j++){
97 BasicBlock *bb1 = nlist[j].element->getElement();
98 BasicBlock *bb2 = nlist[min].element->getElement();
99 assert(bb1->getParent() == bb2->getParent() &&
100 "BBs with diff parents");
101 TerminatorInst *ti = bb1->getTerminator();
103 //compare the order of BBs in the terminator instruction
104 for(int x=0, y = ti->getNumSuccessors(); x < y; x++){
105 if(ti->getSuccessor(x) == bb1){ //bb1 occurs first
109 if(ti->getSuccessor(x) == bb2) //bb2 occurs first
114 graphListElement tempEl=nlist[min];
120 for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
122 GLI->weight=NumPaths[*RI];
123 NumPaths[*RI]+=NumPaths[GLI->element];
127 return NumPaths[g.getRoot()];
130 //This is a helper function to get the edge increments
131 //This is used in conjuntion with inc_DFS
132 //to get the edge increments
133 //Edge increment implies assigning a value to all the edges in the graph
134 //such that if we traverse along any path from root to exit, and
135 //add up the edge values, we get a path number that uniquely
136 //refers to the path we travelled
137 //inc_Dir tells whether 2 edges are in same, or in different directions
138 //if same direction, return 1, else -1
139 static int inc_Dir(Edge e, Edge f){
143 //check that the edges must have atleast one common endpoint
144 assert(*(e.getFirst())==*(f.getFirst()) ||
145 *(e.getFirst())==*(f.getSecond()) ||
146 *(e.getSecond())==*(f.getFirst()) ||
147 *(e.getSecond())==*(f.getSecond()));
149 if(*(e.getFirst())==*(f.getSecond()) ||
150 *(e.getSecond())==*(f.getFirst()))
157 //used for getting edge increments (read comments above in inc_Dir)
158 //inc_DFS is a modification of DFS
159 static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare>& Increment,
160 int events, Node *v, Edge e){
162 vector<Node *> allNodes=t.getAllNodes();
164 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
166 Graph::nodeList node_list=t.getNodeList(*NI);
167 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
169 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
170 if(!edgesEqual(f,e) && *v==*(f.getSecond())){
171 int dir_count=inc_Dir(e,f);
172 int wt=1*f.getWeight();
173 inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
178 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
180 Graph::nodeList node_list=t.getNodeList(*NI);
181 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
183 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
184 if(!edgesEqual(f,e) && *v==*(f.getFirst())){
185 int dir_count=inc_Dir(e,f);
186 int wt=f.getWeight();
187 inc_DFS(g,t, Increment, dir_count*events+wt,
193 allNodes=g.getAllNodes();
194 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
196 Graph::nodeList node_list=g.getNodeList(*NI);
197 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
199 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
200 if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
201 *v==*(f.getFirst()))){
202 int dir_count=inc_Dir(e,f);
203 Increment[f]+=dir_count*events;
209 //Now we select a subset of all edges
210 //and assign them some values such that
211 //if we consider just this subset, it still represents
212 //the path sum along any path in the graph
213 static map<Edge, int, EdgeCompare> getEdgeIncrements(Graph& g, Graph& t){
214 //get all edges in g-t
215 map<Edge, int, EdgeCompare> Increment;
217 vector<Node *> allNodes=g.getAllNodes();
219 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
221 Graph::nodeList node_list=g.getNodeList(*NI);
222 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
224 Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
225 if(!(t.hasEdgeAndWt(ed))){
232 inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
234 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
236 Graph::nodeList node_list=g.getNodeList(*NI);
237 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
239 Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
240 if(!(t.hasEdgeAndWt(ed))){
241 int wt=ed.getWeight();
251 const graphListElement *findNodeInList(const Graph::nodeList &NL,
254 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
257 //Based on edgeIncrements (above), now obtain
258 //the kind of code to be inserted along an edge
259 //The idea here is to minimize the computation
260 //by inserting only the needed code
261 static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare> &instr,
262 vector<Edge > &chords,
263 map<Edge,int, EdgeCompare> &edIncrements){
265 //Register initialization code
267 ws.push_back(g.getRoot());
272 Graph::nodeList succs=g.getNodeList(v);
274 for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
276 int edgeWt=nl->weight;
279 Edge ed(v,w, edgeWt, nl->randId);
281 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
282 CI!=CE && !hasEdge;++CI){
283 if(*CI==ed && CI->getWeight()==edgeWt){//modf
288 if(hasEdge){//so its a chord edge
289 getEdgeCode *edCd=new getEdgeCode();
291 edCd->setInc(edIncrements[ed]);
294 else if(g.getNumberOfIncomingEdges(w)==1){
296 //std::cerr<<"Added w\n";
299 getEdgeCode *edCd=new getEdgeCode();
303 //std::cerr<<"Case 2\n";
308 /////Memory increment code
309 ws.push_back(g.getExit());
318 vector<Node *> lllt=g.getAllNodes();
319 for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
321 Graph::nodeList &nl = g.getNodeList(lnode);
322 graphListElement *N = findNodeInList(nl, w);
327 Edge ed(v,w, N->weight, N->randId);
328 getEdgeCode *edCd=new getEdgeCode();
330 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
332 if(*CI==ed && CI->getWeight()==N->weight){
339 if(instr[ed]!=NULL && instr[ed]->getCond()==1){
340 instr[ed]->setCond(4);
344 edCd->setInc(edIncrements[ed]);
349 else if(g.getNumberOfOutgoingEdges(v)==1)
358 ///// Register increment code
359 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
360 getEdgeCode *edCd=new getEdgeCode();
361 if(instr[*CI]==NULL){
363 edCd->setInc(edIncrements[*CI]);
369 //Add dummy edges corresponding to the back edges
370 //If a->b is a backedge
371 //then incoming dummy edge is root->b
372 //and outgoing dummy edge is a->exit
374 void addDummyEdges(vector<Edge > &stDummy,
375 vector<Edge > &exDummy,
376 Graph &g, vector<Edge> &be){
377 for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
379 Node *first=ed.getFirst();
380 Node *second=ed.getSecond();
383 if(!(*second==*(g.getRoot()))){
384 Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
385 stDummy.push_back(*st);
389 if(!(*first==*(g.getExit()))){
390 Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
391 exDummy.push_back(*ex);
397 //print a given edge in the form BB1Label->BB2Label
398 void printEdge(Edge ed){
399 cerr<<((ed.getFirst())->getElement())
400 ->getName()<<"->"<<((ed.getSecond())
401 ->getElement())->getName()<<
402 ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
405 //Move the incoming dummy edge code and outgoing dummy
406 //edge code over to the corresponding back edge
407 static void moveDummyCode(vector<Edge> &stDummy,
408 vector<Edge> &exDummy,
410 map<Edge, getEdgeCode *, EdgeCompare> &insertions,
412 typedef vector<Edge >::iterator vec_iter;
414 map<Edge,getEdgeCode *, EdgeCompare> temp;
415 //iterate over edges with code
416 std::vector<Edge> toErase;
417 for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=insertions.begin(),
418 ME=insertions.end(); MI!=ME; ++MI){
420 getEdgeCode *edCd=MI->second;
423 //iterate over be, and check if its starts and end vertices hv code
424 for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
425 if(ed.getRandId()==BEI->getRandId()){
428 temp[*BEI]=new getEdgeCode();
430 //so ed is either in st, or ex!
431 if(ed.getFirst()==g.getRoot()){
434 temp[*BEI]->setCdIn(edCd);
435 toErase.push_back(ed);
437 else if(ed.getSecond()==g.getExit()){
440 toErase.push_back(ed);
441 temp[*BEI]->setCdOut(edCd);
444 assert(false && "Not found in either start or end! Rand failed?");
450 for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
452 insertions.erase(*vmi);
453 g.removeEdgeWithWt(*vmi);
456 for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=temp.begin(),
457 ME=temp.end(); MI!=ME; ++MI){
458 insertions[MI->first]=MI->second;
461 #ifdef DEBUG_PATH_PROFILES
462 cerr<<"size of deletions: "<<toErase.size()<<"\n";
463 cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
468 //Do graph processing: to determine minimal edge increments,
469 //appropriate code insertions etc and insert the code at
470 //appropriate locations
471 void processGraph(Graph &g,
473 Instruction *countInst,
475 vector<Edge >& stDummy,
476 vector<Edge >& exDummy,
479 static int MethNo=-1;
481 //Given a graph: with exit->root edge, do the following in seq:
483 //2. insert dummy edges and remove back edges
484 //3. get edge assignments
485 //4. Get Max spanning tree of graph:
486 // -Make graph g2=g undirectional
487 // -Get Max spanning tree t
488 // -Make t undirectional
489 // -remove edges from t not in graph g
490 //5. Get edge increments
491 //6. Get code insertions
492 //7. move code on dummy edges over to the back edges
495 //This is used as maximum "weight" for
497 //This would hold all
498 //right as long as number of paths in the graph
500 const int INFINITY=99999999;
503 //step 1-3 are already done on the graph when this function is called
504 DEBUG(printGraph(g));
506 //step 4: Get Max spanning tree of graph
508 //now insert exit to root edge
509 //if its there earlier, remove it!
510 //assign it weight INFINITY
511 //so that this edge IS ALWAYS IN spanning tree
512 //Note than edges in spanning tree do not get
513 //instrumented: and we do not want the
514 //edge exit->root to get instrumented
515 //as it MAY BE a dummy edge
516 Edge ed(g.getExit(),g.getRoot(),INFINITY);
517 g.addEdge(ed,INFINITY);
520 //make g2 undirectional: this gives a better
521 //maximal spanning tree
522 g2.makeUnDirectional();
523 DEBUG(printGraph(g2));
525 Graph *t=g2.getMaxSpanningTree();
526 #ifdef DEBUG_PATH_PROFILES
527 std::cerr<<"Original maxspanning tree\n";
530 //now edges of tree t have weights reversed
531 //(negative) because the algorithm used
532 //to find max spanning tree is
533 //actually for finding min spanning tree
534 //so get back the original weights
537 //Ordinarily, the graph is directional
538 //lets converts the graph into an
539 //undirectional graph
540 //This is done by adding an edge
541 //v->u for all existing edges u->v
542 t->makeUnDirectional();
544 //Given a tree t, and a "directed graph" g
545 //replace the edges in the tree t with edges that exist in graph
546 //The tree is formed from "undirectional" copy of graph
547 //So whatever edges the tree has, the undirectional graph
548 //would have too. This function corrects some of the directions in
549 //the tree so that now, all edge directions in the tree match
550 //the edge directions of corresponding edges in the directed graph
551 removeTreeEdges(g, *t);
553 #ifdef DEBUG_PATH_PROFILES
554 cerr<<"Final Spanning tree---------\n";
556 cerr<<"-------end spanning tree\n";
559 //now remove the exit->root node
560 //and re-add it with weight 0
561 //since infinite weight is kinda confusing
563 Edge edNew(g.getExit(), g.getRoot(),0);
573 //step 5: Get edge increments
575 //Now we select a subset of all edges
576 //and assign them some values such that
577 //if we consider just this subset, it still represents
578 //the path sum along any path in the graph
580 map<Edge, int, EdgeCompare> increment=getEdgeIncrements(g,*t);
581 #ifdef DEBUG_PATH_PROFILES
582 //print edge increments for debugging
584 for(map<Edge, int, EdgeCompare>::iterator M_I=increment.begin(), M_E=increment.end();
586 printEdge(M_I->first);
587 cerr<<"Increment for above:"<<M_I->second<<"\n";
592 //step 6: Get code insertions
594 //Based on edgeIncrements (above), now obtain
595 //the kind of code to be inserted along an edge
596 //The idea here is to minimize the computation
597 //by inserting only the needed code
599 getChords(chords, g, *t);
602 //cerr<<"Graph before getCodeInsertion:\n";
604 map<Edge, getEdgeCode *, EdgeCompare> codeInsertions;
605 getCodeInsertions(g, codeInsertions, chords,increment);
607 #ifdef DEBUG_PATH_PROFILES
608 //print edges with code for debugging
609 cerr<<"Code inserted in following---------------\n";
610 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
611 cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
612 printEdge(cd_i->first);
613 cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
615 cerr<<"-----end insertions\n";
618 //step 7: move code on dummy edges over to the back edges
620 //Move the incoming dummy edge code and outgoing dummy
621 //edge code over to the corresponding back edge
623 moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
625 #ifdef DEBUG_PATH_PROFILES
627 cerr<<"After moving dummy code\n";
628 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
629 cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
630 printEdge(cd_i->first);
631 cerr<<cd_i->second->getCond()<<":"
632 <<cd_i->second->getInc()<<"\n";
634 cerr<<"Dummy end------------\n";
638 //see what it looks like...
639 //now insert code along edges which have codes on them
640 for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
641 ME=codeInsertions.end(); MI!=ME; ++MI){
643 insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo);
647 //print the graph (for debugging)
648 void printGraph(Graph &g){
649 vector<Node *> lt=g.getAllNodes();
650 cerr<<"Graph---------------------\n";
651 for(vector<Node *>::iterator LI=lt.begin();
653 cerr<<((*LI)->getElement())->getName()<<"->";
654 Graph::nodeList nl=g.getNodeList(*LI);
655 for(Graph::nodeList::iterator NI=nl.begin();
657 cerr<<":"<<"("<<(NI->element->getElement())
658 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
663 cerr<<"--------------------Graph\n";