//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
-#include "llvm/Function.h"
-#include "llvm/Pass.h"
-#include "llvm/BasicBlock.h"
#include "llvm/Transforms/Instrumentation/Graph.h"
+#include "llvm/Pass.h"
+#include "llvm/Module.h"
+#include "llvm/iTerminators.h"
+#include "Support/Statistic.h"
#include <algorithm>
-#include <iostream>
//using std::list;
using std::map;
Graph::nodeList nl=t.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
Edge ed(NLI->element, *NI, NLI->weight);
- //if(!g.hasEdge(ed)) t.removeEdge(ed);
if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
//between any pair of vertices, so no need to delete by edge wt
}
//such that if we traverse along any path from root to exit, and
//add up the edge values, we get a path number that uniquely
//refers to the path we travelled
-int valueAssignmentToEdges(Graph& g){
+int valueAssignmentToEdges(Graph& g, map<Node *, int> nodePriority,
+ vector<Edge> &be){
vector<Node *> revtop=g.reverseTopologicalSort();
- /*
- std::cerr<<"-----------Reverse topological sort\n";
- for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
- std::cerr<<(*RI)->getElement()->getName()<<":";
- }
- std::cerr<<"\n----------------------"<<std::endl;
- */
map<Node *,int > NumPaths;
- for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end(); RI!=RE; ++RI){
+ for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end();
+ RI!=RE; ++RI){
if(g.isLeaf(*RI))
NumPaths[*RI]=1;
else{
NumPaths[*RI]=0;
- /////
- Graph::nodeList &nlist=g.getNodeList(*RI);
+
+ // Modified Graph::nodeList &nlist=g.getNodeList(*RI);
+ Graph::nodeList &nlist=g.getSortedNodeList(*RI, be);
+
//sort nodelist by increasing order of numpaths
int sz=nlist.size();
+
for(int i=0;i<sz-1; i++){
int min=i;
- for(int j=i+1; j<sz; j++)
- if(NumPaths[nlist[j].element]<NumPaths[nlist[min].element]) min=j;
-
+ for(int j=i+1; j<sz; j++){
+ BasicBlock *bb1 = nlist[j].element->getElement();
+ BasicBlock *bb2 = nlist[min].element->getElement();
+
+ if(bb1 == bb2) continue;
+
+ if(*RI == g.getRoot()){
+ assert(nodePriority[nlist[min].element]!=
+ nodePriority[nlist[j].element]
+ && "priorities can't be same!");
+
+ if(nodePriority[nlist[j].element] <
+ nodePriority[nlist[min].element])
+ min = j;
+ }
+
+ else{
+ TerminatorInst *tti = (*RI)->getElement()->getTerminator();
+
+ BranchInst *ti = cast<BranchInst>(tti);
+ assert(ti && "not a branch");
+ assert(ti->getNumSuccessors()==2 && "less successors!");
+
+ BasicBlock *tB = ti->getSuccessor(0);
+ BasicBlock *fB = ti->getSuccessor(1);
+
+ if(tB == bb1 || fB == bb2)
+ min = j;
+ }
+
+ }
graphListElement tempEl=nlist[min];
nlist[min]=nlist[i];
nlist[i]=tempEl;
}
+
//sorted now!
-
for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
GLI!=GLE; ++GLI){
- GLI->weight=NumPaths[*RI];
+ GLI->weight=NumPaths[*RI];
NumPaths[*RI]+=NumPaths[GLI->element];
}
}
//used for getting edge increments (read comments above in inc_Dir)
//inc_DFS is a modification of DFS
-static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare>& Increment,
+static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare2>& Increment,
int events, Node *v, Edge e){
vector<Node *> allNodes=t.getAllNodes();
-
- //cerr<<"Called for\n";
- //if(!e.isNull())
- //printEdge(e);
-
-
for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
Graph::nodeList node_list=t.getNodeList(*NI);
*v==*(f.getFirst()))){
int dir_count=inc_Dir(e,f);
Increment[f]+=dir_count*events;
- //cerr<<"assigned "<<Increment[f]<<" to"<<endl;
- //printEdge(f);
}
}
}
//and assign them some values such that
//if we consider just this subset, it still represents
//the path sum along any path in the graph
-static map<Edge, int, EdgeCompare> getEdgeIncrements(Graph& g, Graph& t){
+static map<Edge, int, EdgeCompare2> getEdgeIncrements(Graph& g, Graph& t,
+ vector<Edge> &be){
//get all edges in g-t
- map<Edge, int, EdgeCompare> Increment;
+ map<Edge, int, EdgeCompare2> Increment;
vector<Node *> allNodes=g.getAllNodes();
for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
- Graph::nodeList node_list=g.getNodeList(*NI);
+ Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
+ //modified g.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
NLI!=NLE; ++NLI){
Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
- Graph::nodeList node_list=g.getNodeList(*NI);
+ Graph::nodeList node_list=g.getSortedNodeList(*NI, be);
+ //modified g.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
NLI!=NLE; ++NLI){
Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
//the kind of code to be inserted along an edge
//The idea here is to minimize the computation
//by inserting only the needed code
-static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare> &instr,
+static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare2> &instr,
vector<Edge > &chords,
- map<Edge,int, EdgeCompare> &edIncrements){
+ map<Edge,int, EdgeCompare2> &edIncrements){
//Register initialization code
vector<Node *> ws;
Node *w=nl->element;
//if chords has v->w
Edge ed(v,w, edgeWt, nl->randId);
- //cerr<<"Assign:\n";
- //printEdge(ed);
bool hasEdge=false;
for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
CI!=CE && !hasEdge;++CI){
edCd->setCond(1);
edCd->setInc(edIncrements[ed]);
instr[ed]=edCd;
- //std::cerr<<"Case 1\n";
}
else if(g.getNumberOfIncomingEdges(w)==1){
ws.push_back(w);
- //std::cerr<<"Added w\n";
}
else{
getEdgeCode *edCd=new getEdgeCode();
edCd->setCond(2);
edCd->setInc(0);
instr[ed]=edCd;
- //std::cerr<<"Case 2\n";
}
}
}
for(vector<Node *>::iterator EII=lllt.begin(); EII!=lllt.end() ;++EII){
Node *lnode=*EII;
Graph::nodeList &nl = g.getNodeList(lnode);
- //cerr<<"Size:"<<lllt.size()<<"\n";
- //cerr<<lnode->getElement()->getName()<<"\n";
- graphListElement *N = findNodeInList(nl, w);
- if (N){// lt.push_back(lnode);
-
- //Node *v=*pd;
- //Node *v=N->element;
- Node *v=lnode;
- //if chords has v->w
-
- Edge ed(v,w, N->weight, N->randId);
- getEdgeCode *edCd=new getEdgeCode();
- bool hasEdge=false;
- for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
- ++CI){
- if(*CI==ed && CI->getWeight()==N->weight){
- hasEdge=true;
- break;
- }
- }
- if(hasEdge){
- char str[100];
- if(instr[ed]!=NULL && instr[ed]->getCond()==1){
- instr[ed]->setCond(4);
- }
- else{
- edCd->setCond(5);
- edCd->setInc(edIncrements[ed]);
- instr[ed]=edCd;
- }
-
- }
- else if(g.getNumberOfOutgoingEdges(v)==1)
- ws.push_back(v);
- else{
- edCd->setCond(6);
- instr[ed]=edCd;
- }
+ //graphListElement *N = findNodeInList(nl, w);
+ for(Graph::nodeList::const_iterator N = nl.begin(),
+ NNEN = nl.end(); N!= NNEN; ++N){
+ if (*N->element == *w){
+ Node *v=lnode;
+
+ //if chords has v->w
+ Edge ed(v,w, N->weight, N->randId);
+ getEdgeCode *edCd=new getEdgeCode();
+ bool hasEdge=false;
+ for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
+ ++CI){
+ if(*CI==ed && CI->getWeight()==N->weight){
+ hasEdge=true;
+ break;
+ }
+ }
+ if(hasEdge){
+ //char str[100];
+ if(instr[ed]!=NULL && instr[ed]->getCond()==1){
+ instr[ed]->setCond(4);
+ }
+ else{
+ edCd->setCond(5);
+ edCd->setInc(edIncrements[ed]);
+ instr[ed]=edCd;
+ }
+
+ }
+ else if(g.getNumberOfOutgoingEdges(v)==1)
+ ws.push_back(v);
+ else{
+ edCd->setCond(6);
+ instr[ed]=edCd;
+ }
+ }
}
}
}
static void moveDummyCode(vector<Edge> &stDummy,
vector<Edge> &exDummy,
vector<Edge> &be,
- map<Edge, getEdgeCode *, EdgeCompare> &insertions,
+ map<Edge, getEdgeCode *, EdgeCompare2> &insertions,
Graph &g){
typedef vector<Edge >::iterator vec_iter;
- map<Edge,getEdgeCode *, EdgeCompare> temp;
+ map<Edge,getEdgeCode *, EdgeCompare2> temp;
//iterate over edges with code
std::vector<Edge> toErase;
- for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=insertions.begin(),
+ for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=insertions.begin(),
ME=insertions.end(); MI!=ME; ++MI){
Edge ed=MI->first;
getEdgeCode *edCd=MI->second;
for(vector<Edge>::iterator BEI=be.begin(), BEE=be.end(); BEI!=BEE; ++BEI){
if(ed.getRandId()==BEI->getRandId()){
- //cerr<<"Looking at edge--------\n";
- //printEdge(ed);
-
if(temp[*BEI]==0)
temp[*BEI]=new getEdgeCode();
//so ed is either in st, or ex!
if(ed.getFirst()==g.getRoot()){
+
//so its in stDummy
temp[*BEI]->setCdIn(edCd);
toErase.push_back(ed);
}
else if(ed.getSecond()==g.getExit()){
+
//so its in exDummy
toErase.push_back(ed);
temp[*BEI]->setCdOut(edCd);
for(vector<Edge >::iterator vmi=toErase.begin(), vme=toErase.end(); vmi!=vme;
++vmi){
insertions.erase(*vmi);
- //cerr<<"Erasing from insertion\n";
- //printEdge(*vmi);
g.removeEdgeWithWt(*vmi);
}
- for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=temp.begin(),
+ for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=temp.begin(),
ME=temp.end(); MI!=ME; ++MI){
insertions[MI->first]=MI->second;
- //cerr<<"inserting into insertion-----\n";
- //printEdge(MI->first);
- }
- //cerr<<"----\n";
-
- /*
- ///---new code end
- bool dummyHasIt=false;
-
- DEBUG(cerr<<"Current edge considered---\n";
- printEdge(ed));
-
- //now check if stDummy has ed
- for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt;
- ++VI){
- if(*VI==ed){
- //#ifdef DEBUG_PATH_PROFILES
- cerr<<"Edge matched with stDummy\n";
- printEdge(ed);
- //#endif
- dummyHasIt=true;
- bool dummyInBe=false;
- //dummy edge with code
- for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe; ++BE){
- Edge backEdge=*BE;
- Node *st=backEdge.getSecond();
- Node *dm=ed.getSecond();
- if(*dm==*st){
- //so this is the back edge to use
- //#ifdef DEBUG_PATH_PROFILES
- cerr<<"Moving to backedge\n";
- printEdge(backEdge);
- //#endif
- getEdgeCode *ged=new getEdgeCode();
- ged->setCdIn(edCd);
- toErase.push_back(ed);//MI);//ed);
- insertions[backEdge]=ged;
- dummyInBe=true;
- }
- }
- assert(dummyInBe);
- //modf
- //new
- //vec_iter VII=VI;
- stDummy.erase(VI);
- break;
- //end new
- }
- }
- if(!dummyHasIt){
- //so exDummy may hv it
- bool inExDummy=false;
- for(vec_iter VI=exDummy.begin(), VE=exDummy.end(); VI!=VE && !inExDummy;
- ++VI){
- if(*VI==ed){
- inExDummy=true;
-
- //#ifdef DEBUG_PATH_PROFILES
- cerr<<"Edge matched with exDummy\n";
- //#endif
- bool dummyInBe2=false;
- //dummy edge with code
- for(vec_iter BE=be.begin(), BEE=be.end(); BE!=BEE && !dummyInBe2;
- ++BE){
- Edge backEdge=*BE;
- Node *st=backEdge.getFirst();
- Node *dm=ed.getFirst();
- if(*dm==*st){
- //so this is the back edge to use
- cerr<<"Moving to backedge\n";
- printEdge(backEdge);
- getEdgeCode *ged;
- if(insertions[backEdge]==NULL)
- ged=new getEdgeCode();
- else
- ged=insertions[backEdge];
- toErase.push_back(ed);//MI);//ed);
- ged->setCdOut(edCd);
- insertions[backEdge]=ged;
- dummyInBe2=true;
- }
- }
- assert(dummyInBe2);
- //modf
- //vec_iter VII=VI;
- exDummy.erase(VI);
- break;
- //end
- }
- }
- }
}
-
- */
+
#ifdef DEBUG_PATH_PROFILES
cerr<<"size of deletions: "<<toErase.size()<<"\n";
-#endif
-
- /*
- for(vector<map<Edge, getEdgeCode *>::iterator>::iterator
- vmi=toErase.begin(), vme=toErase.end(); vmi!=vme; ++vmi)
-
- insertions.erase(*vmi);
- */
-#ifdef DEBUG_PATH_PROFILES
cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n";
#endif
vector<Edge >& be,
vector<Edge >& stDummy,
vector<Edge >& exDummy,
- int numPaths){
+ int numPaths, int MethNo,
+ Value *threshold){
- static int MethNo=0;
- MethNo++;
//Given a graph: with exit->root edge, do the following in seq:
//1. get back edges
//2. insert dummy edges and remove back edges
//This would hold all
//right as long as number of paths in the graph
//is less than this
- const int INFINITY=99999999;
+ const int Infinity=99999999;
//step 1-3 are already done on the graph when this function is called
//now insert exit to root edge
//if its there earlier, remove it!
- //assign it weight INFINITY
+ //assign it weight Infinity
//so that this edge IS ALWAYS IN spanning tree
//Note than edges in spanning tree do not get
//instrumented: and we do not want the
//edge exit->root to get instrumented
//as it MAY BE a dummy edge
- Edge ed(g.getExit(),g.getRoot(),INFINITY);
- g.addEdge(ed,INFINITY);
+ Edge ed(g.getExit(),g.getRoot(),Infinity);
+ g.addEdge(ed,Infinity);
Graph g2=g;
//make g2 undirectional: this gives a better
DEBUG(printGraph(g2));
Graph *t=g2.getMaxSpanningTree();
- //#ifdef DEBUG_PATH_PROFILES
- //cerr<<"Original maxspanning tree\n";
- //printGraph(*t);
- //#endif
+#ifdef DEBUG_PATH_PROFILES
+ std::cerr<<"Original maxspanning tree\n";
+ printGraph(*t);
+#endif
//now edges of tree t have weights reversed
//(negative) because the algorithm used
//to find max spanning tree is
//if we consider just this subset, it still represents
//the path sum along any path in the graph
- map<Edge, int, EdgeCompare> increment=getEdgeIncrements(g,*t);
+ map<Edge, int, EdgeCompare2> increment=getEdgeIncrements(g,*t, be);
#ifdef DEBUG_PATH_PROFILES
//print edge increments for debugging
-
- for(map<Edge, int, EdgeCompare>::iterator M_I=increment.begin(), M_E=increment.end();
- M_I!=M_E; ++M_I){
- printEdge(M_I->first);
- cerr<<"Increment for above:"<<M_I->second<<"\n";
+ std::cerr<<"Edge Increments------\n";
+ for(map<Edge, int, EdgeCompare2>::iterator MMI=increment.begin(), MME=increment.end(); MMI != MME; ++MMI){
+ printEdge(MMI->first);
+ std::cerr<<"Increment for above:"<<MMI->second<<"\n";
}
+ std::cerr<<"-------end of edge increments\n";
#endif
getChords(chords, g, *t);
- //cerr<<"Graph before getCodeInsertion:\n";
- //printGraph(g);
- map<Edge, getEdgeCode *, EdgeCompare> codeInsertions;
+ map<Edge, getEdgeCode *, EdgeCompare2> codeInsertions;
getCodeInsertions(g, codeInsertions, chords,increment);
#ifdef DEBUG_PATH_PROFILES
//print edges with code for debugging
cerr<<"Code inserted in following---------------\n";
- for(map<Edge, getEdgeCode *>::iterator cd_i=codeInsertions.begin(),
+ for(map<Edge, getEdgeCode *, EdgeCompare2>::iterator cd_i=codeInsertions.begin(),
cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
printEdge(cd_i->first);
cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
//edge code over to the corresponding back edge
moveDummyCode(stDummy, exDummy, be, codeInsertions, g);
- //cerr<<"After dummy removals\n";
- //printGraph(g);
-
+
#ifdef DEBUG_PATH_PROFILES
//debugging info
cerr<<"After moving dummy code\n";
for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
ME=codeInsertions.end(); MI!=ME; ++MI){
Edge ed=MI->first;
- insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo);
+ insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo, threshold);
}
}
-
-
//print the graph (for debugging)
void printGraph(Graph &g){
vector<Node *> lt=g.getAllNodes();
}
cerr<<"--------------------Graph\n";
}
-
-
-/*
-////////// Getting back BBs from path number
-
-#include "llvm/Constants.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/iMemory.h"
-#include "llvm/iTerminators.h"
-#include "llvm/iOther.h"
-#include "llvm/iOperators.h"
-
-#include "llvm/Support/CFG.h"
-#include "llvm/BasicBlock.h"
-#include "llvm/Pass.h"
-
-void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph g,
- vector<Edge> &stDummy, vector<Edge> &exDummy, vector<Edge> &be,
- double strand){
- Graph::nodeList nlist=g.getNodeList(n);
- int maxCount=-9999999;
- bool isStart=false;
-
- if(*n==*g.getRoot())//its root: so first node of path
- isStart=true;
-
- double edgeRnd=0;
- Node *nextRoot=n;
- for(Graph::nodeList::iterator NLI=nlist.begin(), NLE=nlist.end(); NLI!=NLE;
- ++NLI){
- //cerr<<"Saw:"<<NLI->weight<<endl;
- if(NLI->weight>maxCount && NLI->weight<=pathNo){
- maxCount=NLI->weight;
- nextRoot=NLI->element;
- edgeRnd=NLI->randId;
- if(isStart)
- strand=NLI->randId;
- }
- }
- //cerr<<"Max:"<<maxCount<<endl;
-
- if(!isStart)
- assert(strand!=-1 && "strand not assigned!");
-
- assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go");
- assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit");
-
- vBB.push_back(n->getElement());
-
- if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){
-
- //look for strnd and edgeRnd now:
- bool has1=false, has2=false;
- //check if exit has it
- for(vector<Edge>::iterator VI=exDummy.begin(), VE=exDummy.end(); VI!=VE;
- ++VI){
- if(VI->getRandId()==edgeRnd){
- has2=true;
- //cerr<<"has2: looking at"<<std::endl;
- //printEdge(*VI);
- break;
- }
- }
-
- //check if start has it
- for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE;
- ++VI){
- if(VI->getRandId()==strand){
- //cerr<<"has1: looking at"<<std::endl;
- //printEdge(*VI);
- has1=true;
- break;
- }
- }
-
- if(has1){
- //find backedge with endpoint vBB[1]
- for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
- assert(vBB.size()>0 && "vector too small");
- if( VI->getSecond()->getElement() == vBB[1] ){
- vBB[0]=VI->getFirst()->getElement();
- break;
- }
- }
- }
-
- if(has2){
- //find backedge with startpoint vBB[vBB.size()-1]
- for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
- assert(vBB.size()>0 && "vector too small");
- if( VI->getFirst()->getElement() == vBB[vBB.size()-1] ){
- //if(vBB[0]==VI->getFirst()->getElement())
- //vBB.erase(vBB.begin()+vBB.size()-1);
- //else
- vBB.push_back(VI->getSecond()->getElement());
- break;
- }
- }
- }
- else
- vBB.push_back(nextRoot->getElement());
-
- return;
- }
-
- assert(pathNo-maxCount>=0);
-
- return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy,
- exDummy, be, strand);
-}
-
-
-static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
- for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
- if(((*si)->getElement())==BB){
- return *si;
- }
- }
- return NULL;
-}
-
-void getBBtrace(vector<BasicBlock *> &vBB, int pathNo, Function *M){
-
- //step 1: create graph
- //Transform the cfg s.t. we have just one exit node
-
- std::vector<Node *> nodes;
- std::vector<Edge> edges;
- Node *tmp;
- Node *exitNode=0, *startNode=0;
-
- BasicBlock *ExitNode = 0;
- for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I) {
- BasicBlock *BB = *I;
- if (isa<ReturnInst>(BB->getTerminator())) {
- ExitNode = BB;
- break;
- }
- }
-
- assert(ExitNode!=0 && "exitnode not found");
-
- //iterating over BBs and making graph
- //The nodes must be uniquesly identified:
- //That is, no two nodes must hav same BB*
-
- //First enter just nodes: later enter edges
- for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
- Node *nd=new Node(*BB);
- nodes.push_back(nd);
- if(*BB==ExitNode)
- exitNode=nd;
- if(*BB==M->front())
- startNode=nd;
- }
-
- assert(exitNode!=0 && startNode!=0 && "Start or exit not found!");
-
- for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
- Node *nd=findBB(nodes, *BB);
- assert(nd && "No node for this edge!");
-
- for(BasicBlock::succ_iterator s=succ_begin(*BB), se=succ_end(*BB);
- s!=se; ++s){
- Node *nd2=findBB(nodes,*s);
- assert(nd2 && "No node for this edge!");
- Edge ed(nd,nd2,0);
- edges.push_back(ed);
- }
- }
-
- static bool printed=false;
- Graph g(nodes,edges, startNode, exitNode);
-
- //if(!printed)
- //printGraph(g);
-
- if (M->getBasicBlocks().size() <= 1) return; //uninstrumented
-
- //step 2: getBackEdges
- vector<Edge> be;
- g.getBackEdges(be);
-
- //cerr<<"BackEdges\n";
- //for(vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
- //printEdge(*VI);
- //cerr<<"\n";
- //}
- //cerr<<"------\n";
- //step 3: add dummy edges
- vector<Edge> stDummy;
- vector<Edge> exDummy;
- addDummyEdges(stDummy, exDummy, g, be);
-
- //cerr<<"After adding dummy edges\n";
- //printGraph(g);
-
- //step 4: value assgn to edges
- int numPaths=valueAssignmentToEdges(g);
-
- //if(!printed){
- //printGraph(g);
- //printed=true;
- //}
-
- //step 5: now travel from root, select max(edge) < pathNo,
- //and go on until reach the exit
- return getPathFrmNode(g.getRoot(), vBB, pathNo, g, stDummy, exDummy, be, -1);
-}
-
-*/
projects / oota-llvm.git / blobdiff