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/Pass.h"
11 #include "llvm/Module.h"
12 #include "llvm/iTerminators.h"
13 #include "Support/Statistic.h"
22 //check if 2 edges are equal (same endpoints and same weight)
23 static bool edgesEqual(Edge ed1, Edge ed2){
24 return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
27 //Get the vector of edges that are to be instrumented in the graph
28 static void getChords(vector<Edge > &chords, Graph &g, Graph st){
29 //make sure the spanning tree is directional
30 //iterate over ALL the edges of the graph
31 vector<Node *> allNodes=g.getAllNodes();
32 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
34 Graph::nodeList node_list=g.getNodeList(*NI);
35 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
37 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
38 if(!(st.hasEdgeAndWt(f)))//addnl
44 //Given a tree t, and a "directed graph" g
45 //replace the edges in the tree t with edges that exist in graph
46 //The tree is formed from "undirectional" copy of graph
47 //So whatever edges the tree has, the undirectional graph
48 //would have too. This function corrects some of the directions in
49 //the tree so that now, all edge directions in the tree match
50 //the edge directions of corresponding edges in the directed graph
51 static void removeTreeEdges(Graph &g, Graph& t){
52 vector<Node* > allNodes=t.getAllNodes();
53 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
55 Graph::nodeList nl=t.getNodeList(*NI);
56 for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
57 Edge ed(NLI->element, *NI, NLI->weight);
58 if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
59 //between any pair of vertices, so no need to delete by edge wt
64 //Assign a value to all the edges in the graph
65 //such that if we traverse along any path from root to exit, and
66 //add up the edge values, we get a path number that uniquely
67 //refers to the path we travelled
68 int valueAssignmentToEdges(Graph& g, map<Node *, int> nodePriority,
70 vector<Node *> revtop=g.reverseTopologicalSort();
71 map<Node *,int > NumPaths;
72 for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end();
79 // Modified Graph::nodeList &nlist=g.getNodeList(*RI);
80 Graph::nodeList &nlist=g.getSortedNodeList(*RI, be);
82 //sort nodelist by increasing order of numpaths
86 for(int i=0;i<sz-1; i++){
88 for(int j=i+1; j<sz; j++){
89 BasicBlock *bb1 = nlist[j].element->getElement();
90 BasicBlock *bb2 = nlist[min].element->getElement();
92 if(bb1 == bb2) continue;
94 if(*RI == g.getRoot()){
95 assert(nodePriority[nlist[min].element]!=
96 nodePriority[nlist[j].element]
97 && "priorities can't be same!");
99 if(nodePriority[nlist[j].element] <
100 nodePriority[nlist[min].element])
105 TerminatorInst *tti = (*RI)->getElement()->getTerminator();
107 BranchInst *ti = cast<BranchInst>(tti);
108 assert(ti && "not a branch");
109 assert(ti->getNumSuccessors()==2 && "less successors!");
111 BasicBlock *tB = ti->getSuccessor(0);
112 BasicBlock *fB = ti->getSuccessor(1);
114 if(tB == bb1 || fB == bb2)
119 graphListElement tempEl=nlist[min];
125 for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
127 GLI->weight=NumPaths[*RI];
128 NumPaths[*RI]+=NumPaths[GLI->element];
132 return NumPaths[g.getRoot()];
135 //This is a helper function to get the edge increments
136 //This is used in conjuntion with inc_DFS
137 //to get the edge increments
138 //Edge increment implies assigning a value to all the edges in the graph
139 //such that if we traverse along any path from root to exit, and
140 //add up the edge values, we get a path number that uniquely
141 //refers to the path we travelled
142 //inc_Dir tells whether 2 edges are in same, or in different directions
143 //if same direction, return 1, else -1
144 static int inc_Dir(Edge e, Edge f){
148 //check that the edges must have atleast one common endpoint
149 assert(*(e.getFirst())==*(f.getFirst()) ||
150 *(e.getFirst())==*(f.getSecond()) ||
151 *(e.getSecond())==*(f.getFirst()) ||
152 *(e.getSecond())==*(f.getSecond()));
154 if(*(e.getFirst())==*(f.getSecond()) ||
155 *(e.getSecond())==*(f.getFirst()))
162 //used for getting edge increments (read comments above in inc_Dir)
163 //inc_DFS is a modification of DFS
164 static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare2>& Increment,
165 int events, Node *v, Edge e){
167 vector<Node *> allNodes=t.getAllNodes();
169 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
171 Graph::nodeList node_list=t.getNodeList(*NI);
172 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
174 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
175 if(!edgesEqual(f,e) && *v==*(f.getSecond())){
176 int dir_count=inc_Dir(e,f);
177 int wt=1*f.getWeight();
178 inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
183 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
185 Graph::nodeList node_list=t.getNodeList(*NI);
186 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
188 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
189 if(!edgesEqual(f,e) && *v==*(f.getFirst())){
190 int dir_count=inc_Dir(e,f);
191 int wt=f.getWeight();
192 inc_DFS(g,t, Increment, dir_count*events+wt,
198 allNodes=g.getAllNodes();
199 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
201 Graph::nodeList node_list=g.getNodeList(*NI);
202 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
204 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
205 if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
206 *v==*(f.getFirst()))){
207 int dir_count=inc_Dir(e,f);
208 Increment[f]+=dir_count*events;
214 //Now we select a subset of all edges
215 //and assign them some values such that
216 //if we consider just this subset, it still represents
217 //the path sum along any path in the graph
218 static map<Edge, int, EdgeCompare2> getEdgeIncrements(Graph& g, Graph& t,
220 //get all edges in g-t
221 map<Edge, int, EdgeCompare2> Increment;
223 vector<Node *> allNodes=g.getAllNodes();
225 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
227 Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
228 //modified g.getNodeList(*NI);
229 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
231 Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
232 if(!(t.hasEdgeAndWt(ed))){
239 inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
241 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
243 Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
244 //modified g.getNodeList(*NI);
245 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
247 Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
248 if(!(t.hasEdgeAndWt(ed))){
249 int wt=ed.getWeight();
259 const graphListElement *findNodeInList(const Graph::nodeList &NL,
262 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
265 //Based on edgeIncrements (above), now obtain
266 //the kind of code to be inserted along an edge
267 //The idea here is to minimize the computation
268 //by inserting only the needed code
269 static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare2> &instr,
270 vector<Edge > &chords,
271 map<Edge,int, EdgeCompare2> &edIncrements){
273 //Register initialization code
275 ws.push_back(g.getRoot());
280 Graph::nodeList succs=g.getNodeList(v);
282 for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
284 int edgeWt=nl->weight;
287 Edge ed(v,w, edgeWt, nl->randId);
289 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
290 CI!=CE && !hasEdge;++CI){
291 if(*CI==ed && CI->getWeight()==edgeWt){//modf
296 if(hasEdge){//so its a chord edge
297 getEdgeCode *edCd=new getEdgeCode();
299 edCd->setInc(edIncrements[ed]);
302 else if(g.getNumberOfIncomingEdges(w)==1){
306 getEdgeCode *edCd=new getEdgeCode();
314 /////Memory increment code
315 ws.push_back(g.getExit());
324 vector<Node *> lllt=g.getAllNodes();
325 for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
327 Graph::nodeList &nl = g.getNodeList(lnode);
328 //graphListElement *N = findNodeInList(nl, w);
329 for(Graph::nodeList::const_iterator N = nl.begin(),
330 NNEN = nl.end(); N!= NNEN; ++N){
331 if (*N->element == *w){
335 Edge ed(v,w, N->weight, N->randId);
336 getEdgeCode *edCd=new getEdgeCode();
338 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
340 if(*CI==ed && CI->getWeight()==N->weight){
347 if(instr[ed]!=NULL && instr[ed]->getCond()==1){
348 instr[ed]->setCond(4);
352 edCd->setInc(edIncrements[ed]);
357 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 *, EdgeCompare2> &insertions,
421 typedef vector<Edge >::iterator vec_iter;
423 map<Edge,getEdgeCode *, EdgeCompare2> temp;
424 //iterate over edges with code
425 std::vector<Edge> toErase;
426 for(map<Edge,getEdgeCode *, EdgeCompare2>::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 *, EdgeCompare2>::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,
484 vector<Edge >& stDummy,
485 vector<Edge >& exDummy,
486 int numPaths, int MethNo,
489 //Given a graph: with exit->root edge, do the following in seq:
491 //2. insert dummy edges and remove back edges
492 //3. get edge assignments
493 //4. Get Max spanning tree of graph:
494 // -Make graph g2=g undirectional
495 // -Get Max spanning tree t
496 // -Make t undirectional
497 // -remove edges from t not in graph g
498 //5. Get edge increments
499 //6. Get code insertions
500 //7. move code on dummy edges over to the back edges
503 //This is used as maximum "weight" for
505 //This would hold all
506 //right as long as number of paths in the graph
508 const int Infinity=99999999;
511 //step 1-3 are already done on the graph when this function is called
512 DEBUG(printGraph(g));
514 //step 4: Get Max spanning tree of graph
516 //now insert exit to root edge
517 //if its there earlier, remove it!
518 //assign it weight Infinity
519 //so that this edge IS ALWAYS IN spanning tree
520 //Note than edges in spanning tree do not get
521 //instrumented: and we do not want the
522 //edge exit->root to get instrumented
523 //as it MAY BE a dummy edge
524 Edge ed(g.getExit(),g.getRoot(),Infinity);
525 g.addEdge(ed,Infinity);
528 //make g2 undirectional: this gives a better
529 //maximal spanning tree
530 g2.makeUnDirectional();
531 DEBUG(printGraph(g2));
533 Graph *t=g2.getMaxSpanningTree();
534 #ifdef DEBUG_PATH_PROFILES
535 std::cerr<<"Original maxspanning tree\n";
538 //now edges of tree t have weights reversed
539 //(negative) because the algorithm used
540 //to find max spanning tree is
541 //actually for finding min spanning tree
542 //so get back the original weights
545 //Ordinarily, the graph is directional
546 //lets converts the graph into an
547 //undirectional graph
548 //This is done by adding an edge
549 //v->u for all existing edges u->v
550 t->makeUnDirectional();
552 //Given a tree t, and a "directed graph" g
553 //replace the edges in the tree t with edges that exist in graph
554 //The tree is formed from "undirectional" copy of graph
555 //So whatever edges the tree has, the undirectional graph
556 //would have too. This function corrects some of the directions in
557 //the tree so that now, all edge directions in the tree match
558 //the edge directions of corresponding edges in the directed graph
559 removeTreeEdges(g, *t);
561 #ifdef DEBUG_PATH_PROFILES
562 cerr<<"Final Spanning tree---------\n";
564 cerr<<"-------end spanning tree\n";
567 //now remove the exit->root node
568 //and re-add it with weight 0
569 //since infinite weight is kinda confusing
571 Edge edNew(g.getExit(), g.getRoot(),0);
581 //step 5: Get edge increments
583 //Now we select a subset of all edges
584 //and assign them some values such that
585 //if we consider just this subset, it still represents
586 //the path sum along any path in the graph
588 map<Edge, int, EdgeCompare2> increment=getEdgeIncrements(g,*t, be);
589 #ifdef DEBUG_PATH_PROFILES
590 //print edge increments for debugging
591 std::cerr<<"Edge Increments------\n";
592 for(map<Edge, int, EdgeCompare2>::iterator MMI=increment.begin(), MME=increment.end(); MMI != MME; ++MMI){
593 printEdge(MMI->first);
594 std::cerr<<"Increment for above:"<<MMI->second<<"\n";
596 std::cerr<<"-------end of edge increments\n";
600 //step 6: Get code insertions
602 //Based on edgeIncrements (above), now obtain
603 //the kind of code to be inserted along an edge
604 //The idea here is to minimize the computation
605 //by inserting only the needed code
607 getChords(chords, g, *t);
610 map<Edge, getEdgeCode *, EdgeCompare2> codeInsertions;
611 getCodeInsertions(g, codeInsertions, chords,increment);
613 #ifdef DEBUG_PATH_PROFILES
614 //print edges with code for debugging
615 cerr<<"Code inserted in following---------------\n";
616 for(map<Edge, getEdgeCode *, EdgeCompare2>::iterator cd_i=codeInsertions.begin(),
617 cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
618 printEdge(cd_i->first);
619 cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
621 cerr<<"-----end insertions\n";
624 //step 7: move code on dummy edges over to the back edges
626 //Move the incoming dummy edge code and outgoing dummy
627 //edge code over to the corresponding back edge
629 moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
631 #ifdef DEBUG_PATH_PROFILES
633 cerr<<"After moving dummy code\n";
634 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
635 cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
636 printEdge(cd_i->first);
637 cerr<<cd_i->second->getCond()<<":"
638 <<cd_i->second->getInc()<<"\n";
640 cerr<<"Dummy end------------\n";
644 //see what it looks like...
645 //now insert code along edges which have codes on them
646 for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
647 ME=codeInsertions.end(); MI!=ME; ++MI){
649 insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo, threshold);
653 //print the graph (for debugging)
654 void printGraph(Graph &g){
655 vector<Node *> lt=g.getAllNodes();
656 cerr<<"Graph---------------------\n";
657 for(vector<Node *>::iterator LI=lt.begin();
659 cerr<<((*LI)->getElement())->getName()<<"->";
660 Graph::nodeList nl=g.getNodeList(*LI);
661 for(Graph::nodeList::iterator NI=nl.begin();
663 cerr<<":"<<"("<<(NI->element->getElement())
664 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
669 cerr<<"--------------------Graph\n";