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/Transforms/Instrumentation/Graph.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.hasEdge(ed)) t.removeEdge(ed);
59 if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
60 //between any pair of vertices, so no need to delete by edge wt
65 //Assign a value to all the edges in the graph
66 //such that if we traverse along any path from root to exit, and
67 //add up the edge values, we get a path number that uniquely
68 //refers to the path we travelled
69 int valueAssignmentToEdges(Graph& g){
70 vector<Node *> revtop=g.reverseTopologicalSort();
72 std::cerr<<"-----------Reverse topological sort\n";
73 for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
74 std::cerr<<(*RI)->getElement()->getName()<<":";
76 std::cerr<<"\n----------------------"<<std::endl;
78 map<Node *,int > NumPaths;
79 for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
85 Graph::nodeList &nlist=g.getNodeList(*RI);
86 //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 if(NumPaths[nlist[j].element]<NumPaths[nlist[min].element]) min=j;
94 graphListElement tempEl=nlist[min];
100 for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
102 GLI->weight=NumPaths[*RI];
103 NumPaths[*RI]+=NumPaths[GLI->element];
107 return NumPaths[g.getRoot()];
110 //This is a helper function to get the edge increments
111 //This is used in conjuntion with inc_DFS
112 //to get the edge increments
113 //Edge increment implies assigning a value to all the edges in the graph
114 //such that if we traverse along any path from root to exit, and
115 //add up the edge values, we get a path number that uniquely
116 //refers to the path we travelled
117 //inc_Dir tells whether 2 edges are in same, or in different directions
118 //if same direction, return 1, else -1
119 static int inc_Dir(Edge e, Edge f){
123 //check that the edges must have atleast one common endpoint
124 assert(*(e.getFirst())==*(f.getFirst()) ||
125 *(e.getFirst())==*(f.getSecond()) ||
126 *(e.getSecond())==*(f.getFirst()) ||
127 *(e.getSecond())==*(f.getSecond()));
129 if(*(e.getFirst())==*(f.getSecond()) ||
130 *(e.getSecond())==*(f.getFirst()))
137 //used for getting edge increments (read comments above in inc_Dir)
138 //inc_DFS is a modification of DFS
139 static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare>& Increment,
140 int events, Node *v, Edge e){
142 vector<Node *> allNodes=t.getAllNodes();
145 //cerr<<"Called for\n";
150 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
152 Graph::nodeList node_list=t.getNodeList(*NI);
153 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
155 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
156 if(!edgesEqual(f,e) && *v==*(f.getSecond())){
157 int dir_count=inc_Dir(e,f);
158 int wt=1*f.getWeight();
159 inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
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.getFirst())){
171 int dir_count=inc_Dir(e,f);
172 int wt=f.getWeight();
173 inc_DFS(g,t, Increment, dir_count*events+wt,
179 allNodes=g.getAllNodes();
180 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
182 Graph::nodeList node_list=g.getNodeList(*NI);
183 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
185 Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
186 if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
187 *v==*(f.getFirst()))){
188 int dir_count=inc_Dir(e,f);
189 Increment[f]+=dir_count*events;
190 //cerr<<"assigned "<<Increment[f]<<" to"<<endl;
197 //Now we select a subset of all edges
198 //and assign them some values such that
199 //if we consider just this subset, it still represents
200 //the path sum along any path in the graph
201 static map<Edge, int, EdgeCompare> getEdgeIncrements(Graph& g, Graph& t){
202 //get all edges in g-t
203 map<Edge, int, EdgeCompare> Increment;
205 vector<Node *> allNodes=g.getAllNodes();
207 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
209 Graph::nodeList node_list=g.getNodeList(*NI);
210 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
212 Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
213 if(!(t.hasEdgeAndWt(ed))){
220 inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
222 for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
224 Graph::nodeList node_list=g.getNodeList(*NI);
225 for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
227 Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
228 if(!(t.hasEdgeAndWt(ed))){
229 int wt=ed.getWeight();
239 const graphListElement *findNodeInList(const Graph::nodeList &NL,
242 graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
245 //Based on edgeIncrements (above), now obtain
246 //the kind of code to be inserted along an edge
247 //The idea here is to minimize the computation
248 //by inserting only the needed code
249 static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare> &instr,
250 vector<Edge > &chords,
251 map<Edge,int, EdgeCompare> &edIncrements){
253 //Register initialization code
255 ws.push_back(g.getRoot());
260 Graph::nodeList succs=g.getNodeList(v);
262 for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
264 int edgeWt=nl->weight;
267 Edge ed(v,w, edgeWt, nl->randId);
271 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
272 CI!=CE && !hasEdge;++CI){
273 if(*CI==ed && CI->getWeight()==edgeWt){//modf
278 if(hasEdge){//so its a chord edge
279 getEdgeCode *edCd=new getEdgeCode();
281 edCd->setInc(edIncrements[ed]);
283 //std::cerr<<"Case 1\n";
285 else if(g.getNumberOfIncomingEdges(w)==1){
287 //std::cerr<<"Added w\n";
290 getEdgeCode *edCd=new getEdgeCode();
294 //std::cerr<<"Case 2\n";
299 /////Memory increment code
300 ws.push_back(g.getExit());
309 vector<Node *> lllt=g.getAllNodes();
310 for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
312 Graph::nodeList &nl = g.getNodeList(lnode);
313 //cerr<<"Size:"<<lllt.size()<<"\n";
314 //cerr<<lnode->getElement()->getName()<<"\n";
315 graphListElement *N = findNodeInList(nl, w);
316 if (N){// lt.push_back(lnode);
319 //Node *v=N->element;
323 Edge ed(v,w, N->weight, N->randId);
324 getEdgeCode *edCd=new getEdgeCode();
326 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
328 if(*CI==ed && CI->getWeight()==N->weight){
335 if(instr[ed]!=NULL && instr[ed]->getCond()==1){
336 instr[ed]->setCond(4);
340 edCd->setInc(edIncrements[ed]);
345 else if(g.getNumberOfOutgoingEdges(v)==1)
354 ///// Register increment code
355 for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
356 getEdgeCode *edCd=new getEdgeCode();
357 if(instr[*CI]==NULL){
359 edCd->setInc(edIncrements[*CI]);
365 //Add dummy edges corresponding to the back edges
366 //If a->b is a backedge
367 //then incoming dummy edge is root->b
368 //and outgoing dummy edge is a->exit
370 void addDummyEdges(vector<Edge > &stDummy,
371 vector<Edge > &exDummy,
372 Graph &g, vector<Edge> &be){
373 for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
375 Node *first=ed.getFirst();
376 Node *second=ed.getSecond();
379 if(!(*second==*(g.getRoot()))){
380 Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
381 stDummy.push_back(*st);
385 if(!(*first==*(g.getExit()))){
386 Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
387 exDummy.push_back(*ex);
393 //print a given edge in the form BB1Label->BB2Label
394 void printEdge(Edge ed){
395 cerr<<((ed.getFirst())->getElement())
396 ->getName()<<"->"<<((ed.getSecond())
397 ->getElement())->getName()<<
398 ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
401 //Move the incoming dummy edge code and outgoing dummy
402 //edge code over to the corresponding back edge
403 static void moveDummyCode(vector<Edge> &stDummy,
404 vector<Edge> &exDummy,
406 map<Edge, getEdgeCode *, EdgeCompare> &insertions,
408 typedef vector<Edge >::iterator vec_iter;
410 map<Edge,getEdgeCode *, EdgeCompare> temp;
411 //iterate over edges with code
412 std::vector<Edge> toErase;
413 for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=insertions.begin(),
414 ME=insertions.end(); MI!=ME; ++MI){
416 getEdgeCode *edCd=MI->second;
419 //iterate over be, and check if its starts and end vertices hv code
420 for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
421 if(ed.getRandId()==BEI->getRandId()){
423 //cerr<<"Looking at edge--------\n";
427 temp[*BEI]=new getEdgeCode();
429 //so ed is either in st, or ex!
430 if(ed.getFirst()==g.getRoot()){
432 temp[*BEI]->setCdIn(edCd);
433 toErase.push_back(ed);
435 else if(ed.getSecond()==g.getExit()){
437 toErase.push_back(ed);
438 temp[*BEI]->setCdOut(edCd);
441 assert(false && "Not found in either start or end! Rand failed?");
447 for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
449 insertions.erase(*vmi);
450 //cerr<<"Erasing from insertion\n";
452 g.removeEdgeWithWt(*vmi);
455 for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=temp.begin(),
456 ME=temp.end(); MI!=ME; ++MI){
457 insertions[MI->first]=MI->second;
458 //cerr<<"inserting into insertion-----\n";
459 //printEdge(MI->first);
465 bool dummyHasIt=false;
467 DEBUG(cerr<<"Current edge considered---\n";
470 //now check if stDummy has ed
471 for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt;
474 //#ifdef DEBUG_PATH_PROFILES
475 cerr<<"Edge matched with stDummy\n";
479 bool dummyInBe=false;
480 //dummy edge with code
481 for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe; ++BE){
483 Node *st=backEdge.getSecond();
484 Node *dm=ed.getSecond();
486 //so this is the back edge to use
487 //#ifdef DEBUG_PATH_PROFILES
488 cerr<<"Moving to backedge\n";
491 getEdgeCode *ged=new getEdgeCode();
493 toErase.push_back(ed);//MI);//ed);
494 insertions[backEdge]=ged;
508 //so exDummy may hv it
509 bool inExDummy=false;
510 for(vec_iter VI=exDummy.begin(), VE=exDummy.end(); VI!=VE && !inExDummy;
515 //#ifdef DEBUG_PATH_PROFILES
516 cerr<<"Edge matched with exDummy\n";
518 bool dummyInBe2=false;
519 //dummy edge with code
520 for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe2;
523 Node *st=backEdge.getFirst();
524 Node *dm=ed.getFirst();
526 //so this is the back edge to use
527 cerr<<"Moving to backedge\n";
530 if(insertions[backEdge]==NULL)
531 ged=new getEdgeCode();
533 ged=insertions[backEdge];
534 toErase.push_back(ed);//MI);//ed);
536 insertions[backEdge]=ged;
552 #ifdef DEBUG_PATH_PROFILES
553 cerr<<"size of deletions: "<<toErase.size()<<"\n";
557 for(vector<map<Edge, getEdgeCode *>::iterator>::iterator
558 vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; ++vmi)
560 insertions.erase(*vmi);
562 #ifdef DEBUG_PATH_PROFILES
563 cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
568 //Do graph processing: to determine minimal edge increments,
569 //appropriate code insertions etc and insert the code at
570 //appropriate locations
571 void processGraph(Graph &g,
573 Instruction *countInst,
575 vector<Edge >& stDummy,
576 vector<Edge >& exDummy,
581 //Given a graph: with exit->root edge, do the following in seq:
583 //2. insert dummy edges and remove back edges
584 //3. get edge assignments
585 //4. Get Max spanning tree of graph:
586 // -Make graph g2=g undirectional
587 // -Get Max spanning tree t
588 // -Make t undirectional
589 // -remove edges from t not in graph g
590 //5. Get edge increments
591 //6. Get code insertions
592 //7. move code on dummy edges over to the back edges
595 //This is used as maximum "weight" for
597 //This would hold all
598 //right as long as number of paths in the graph
600 const int INFINITY=99999999;
603 //step 1-3 are already done on the graph when this function is called
604 DEBUG(printGraph(g));
606 //step 4: Get Max spanning tree of graph
608 //now insert exit to root edge
609 //if its there earlier, remove it!
610 //assign it weight INFINITY
611 //so that this edge IS ALWAYS IN spanning tree
612 //Note than edges in spanning tree do not get
613 //instrumented: and we do not want the
614 //edge exit->root to get instrumented
615 //as it MAY BE a dummy edge
616 Edge ed(g.getExit(),g.getRoot(),INFINITY);
617 g.addEdge(ed,INFINITY);
620 //make g2 undirectional: this gives a better
621 //maximal spanning tree
622 g2.makeUnDirectional();
623 DEBUG(printGraph(g2));
625 Graph *t=g2.getMaxSpanningTree();
626 //#ifdef DEBUG_PATH_PROFILES
627 //cerr<<"Original maxspanning tree\n";
630 //now edges of tree t have weights reversed
631 //(negative) because the algorithm used
632 //to find max spanning tree is
633 //actually for finding min spanning tree
634 //so get back the original weights
637 //Ordinarily, the graph is directional
638 //lets converts the graph into an
639 //undirectional graph
640 //This is done by adding an edge
641 //v->u for all existing edges u->v
642 t->makeUnDirectional();
644 //Given a tree t, and a "directed graph" g
645 //replace the edges in the tree t with edges that exist in graph
646 //The tree is formed from "undirectional" copy of graph
647 //So whatever edges the tree has, the undirectional graph
648 //would have too. This function corrects some of the directions in
649 //the tree so that now, all edge directions in the tree match
650 //the edge directions of corresponding edges in the directed graph
651 removeTreeEdges(g, *t);
653 #ifdef DEBUG_PATH_PROFILES
654 cerr<<"Final Spanning tree---------\n";
656 cerr<<"-------end spanning tree\n";
659 //now remove the exit->root node
660 //and re-add it with weight 0
661 //since infinite weight is kinda confusing
663 Edge edNew(g.getExit(), g.getRoot(),0);
673 //step 5: Get edge increments
675 //Now we select a subset of all edges
676 //and assign them some values such that
677 //if we consider just this subset, it still represents
678 //the path sum along any path in the graph
680 map<Edge, int, EdgeCompare> increment=getEdgeIncrements(g,*t);
681 #ifdef DEBUG_PATH_PROFILES
682 //print edge increments for debugging
684 for(map<Edge, int, EdgeCompare>::iterator M_I=increment.begin(), M_E=increment.end();
686 printEdge(M_I->first);
687 cerr<<"Increment for above:"<<M_I->second<<"\n";
692 //step 6: Get code insertions
694 //Based on edgeIncrements (above), now obtain
695 //the kind of code to be inserted along an edge
696 //The idea here is to minimize the computation
697 //by inserting only the needed code
699 getChords(chords, g, *t);
702 //cerr<<"Graph before getCodeInsertion:\n";
704 map<Edge, getEdgeCode *, EdgeCompare> codeInsertions;
705 getCodeInsertions(g, codeInsertions, chords,increment);
707 #ifdef DEBUG_PATH_PROFILES
708 //print edges with code for debugging
709 cerr<<"Code inserted in following---------------\n";
710 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
711 cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
712 printEdge(cd_i->first);
713 cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
715 cerr<<"-----end insertions\n";
718 //step 7: move code on dummy edges over to the back edges
720 //Move the incoming dummy edge code and outgoing dummy
721 //edge code over to the corresponding back edge
723 moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
724 //cerr<<"After dummy removals\n";
727 #ifdef DEBUG_PATH_PROFILES
729 cerr<<"After moving dummy code\n";
730 for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
731 cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
732 printEdge(cd_i->first);
733 cerr<<cd_i->second->getCond()<<":"
734 <<cd_i->second->getInc()<<"\n";
736 cerr<<"Dummy end------------\n";
740 //see what it looks like...
741 //now insert code along edges which have codes on them
742 for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
743 ME=codeInsertions.end(); MI!=ME; ++MI){
745 insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo);
751 //print the graph (for debugging)
752 void printGraph(Graph &g){
753 vector<Node *> lt=g.getAllNodes();
754 cerr<<"Graph---------------------\n";
755 for(vector<Node *>::iterator LI=lt.begin();
757 cerr<<((*LI)->getElement())->getName()<<"->";
758 Graph::nodeList nl=g.getNodeList(*LI);
759 for(Graph::nodeList::iterator NI=nl.begin();
761 cerr<<":"<<"("<<(NI->element->getElement())
762 ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
767 cerr<<"--------------------Graph\n";
772 ////////// Getting back BBs from path number
774 #include "llvm/Constants.h"
775 #include "llvm/DerivedTypes.h"
776 #include "llvm/iMemory.h"
777 #include "llvm/iTerminators.h"
778 #include "llvm/iOther.h"
779 #include "llvm/iOperators.h"
781 #include "llvm/Support/CFG.h"
782 #include "llvm/BasicBlock.h"
783 #include "llvm/Pass.h"
785 void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph g,
786 vector<Edge> &stDummy, vector<Edge> &exDummy, vector<Edge> &be,
788 Graph::nodeList nlist=g.getNodeList(n);
789 int maxCount=-9999999;
792 if(*n==*g.getRoot())//its root: so first node of path
797 for(Graph::nodeList::iterator NLI=nlist.begin(), NLE=nlist.end(); NLI!=NLE;
799 //cerr<<"Saw:"<<NLI->weight<<endl;
800 if(NLI->weight>maxCount && NLI->weight<=pathNo){
801 maxCount=NLI->weight;
802 nextRoot=NLI->element;
808 //cerr<<"Max:"<<maxCount<<endl;
811 assert(strand!=-1 && "strand not assigned!");
813 assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go");
814 assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit");
816 vBB.push_back(n->getElement());
818 if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){
820 //look for strnd and edgeRnd now:
821 bool has1=false, has2=false;
822 //check if exit has it
823 for(vector<Edge>::iterator VI=exDummy.begin(), VE=exDummy.end(); VI!=VE;
825 if(VI->getRandId()==edgeRnd){
827 //cerr<<"has2: looking at"<<std::endl;
833 //check if start has it
834 for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE;
836 if(VI->getRandId()==strand){
837 //cerr<<"has1: looking at"<<std::endl;
845 //find backedge with endpoint vBB[1]
846 for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
847 assert(vBB.size()>0 && "vector too small");
848 if( VI->getSecond()->getElement() == vBB[1] ){
849 vBB[0]=VI->getFirst()->getElement();
856 //find backedge with startpoint vBB[vBB.size()-1]
857 for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
858 assert(vBB.size()>0 && "vector too small");
859 if( VI->getFirst()->getElement() == vBB[vBB.size()-1] ){
860 //if(vBB[0]==VI->getFirst()->getElement())
861 //vBB.erase(vBB.begin()+vBB.size()-1);
863 vBB.push_back(VI->getSecond()->getElement());
869 vBB.push_back(nextRoot->getElement());
874 assert(pathNo-maxCount>=0);
876 return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy,
877 exDummy, be, strand);
881 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
882 for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
883 if(((*si)->getElement())==BB){
890 void getBBtrace(vector<BasicBlock *> &vBB, int pathNo, Function *M){
892 //step 1: create graph
893 //Transform the cfg s.t. we have just one exit node
895 std::vector<Node *> nodes;
896 std::vector<Edge> edges;
898 Node *exitNode=0, *startNode=0;
900 BasicBlock *ExitNode = 0;
901 for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I) {
903 if (isa<ReturnInst>(BB->getTerminator())) {
909 assert(ExitNode!=0 && "exitnode not found");
911 //iterating over BBs and making graph
912 //The nodes must be uniquesly identified:
913 //That is, no two nodes must hav same BB*
915 //First enter just nodes: later enter edges
916 for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
917 Node *nd=new Node(*BB);
925 assert(exitNode!=0 && startNode!=0 && "Start or exit not found!");
927 for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
928 Node *nd=findBB(nodes, *BB);
929 assert(nd && "No node for this edge!");
931 for(BasicBlock::succ_iterator s=succ_begin(*BB), se=succ_end(*BB);
933 Node *nd2=findBB(nodes,*s);
934 assert(nd2 && "No node for this edge!");
940 static bool printed=false;
941 Graph g(nodes,edges, startNode, exitNode);
946 if (M->getBasicBlocks().size() <= 1) return; //uninstrumented
948 //step 2: getBackEdges
952 //cerr<<"BackEdges\n";
953 //for(vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
958 //step 3: add dummy edges
959 vector<Edge> stDummy;
960 vector<Edge> exDummy;
961 addDummyEdges(stDummy, exDummy, g, be);
963 //cerr<<"After adding dummy edges\n";
966 //step 4: value assgn to edges
967 int numPaths=valueAssignmentToEdges(g);
974 //step 5: now travel from root, select max(edge) < pathNo,
975 //and go on until reach the exit
976 return getPathFrmNode(g.getRoot(), vBB, pathNo, g, stDummy, exDummy, be, -1);