additions and bug fixes
llvm-svn: 2794
diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxillary.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxillary.cpp
index b2c5445..1eadcb6 100644
--- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxillary.cpp
+++ b/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxillary.cpp
@@ -6,12 +6,15 @@
//
//===----------------------------------------------------------------------===//
-#include "Graph.h"
+#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 <algorithm>
#include <iostream>
-using std::list;
+//using std::list;
using std::map;
using std::vector;
using std::cerr;
@@ -25,13 +28,13 @@
static void getChords(vector<Edge > &chords, Graph &g, Graph st){
//make sure the spanning tree is directional
//iterate over ALL the edges of the graph
- list<Node *> allNodes=g.getAllNodes();
- for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
+ 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);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
NLI!=NLE; ++NLI){
- Edge f(*NI, NLI->element,NLI->weight);
+ Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
if(!(st.hasEdgeAndWt(f)))//addnl
chords.push_back(f);
}
@@ -46,8 +49,8 @@
//the tree so that now, all edge directions in the tree match
//the edge directions of corresponding edges in the directed graph
static void removeTreeEdges(Graph &g, Graph& t){
- list<Node* > allNodes=t.getAllNodes();
- for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
+ vector<Node* > allNodes=t.getAllNodes();
+ for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
Graph::nodeList nl=t.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
@@ -64,18 +67,40 @@
//add up the edge values, we get a path number that uniquely
//refers to the path we travelled
int valueAssignmentToEdges(Graph& g){
- list<Node *> revtop=g.reverseTopologicalSort();
+ 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(list<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;
- list<Node *> succ=g.getSuccNodes(*RI);
- for(list<Node *>::iterator SI=succ.begin(), SE=succ.end(); SI!=SE; ++SI){
- Edge ed(*RI,*SI,NumPaths[*RI]);
- g.setWeight(ed);
- NumPaths[*RI]+=NumPaths[*SI];
+ /////
+ Graph::nodeList &nlist=g.getNodeList(*RI);
+ //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;
+
+ 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];
+ NumPaths[*RI]+=NumPaths[GLI->element];
}
}
}
@@ -108,19 +133,26 @@
return -1;
}
+
//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>& Increment,
+static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare>& Increment,
int events, Node *v, Edge e){
- list<Node *> allNodes=t.getAllNodes();
-
- for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
+ 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);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
NLI!= NLE; ++NLI){
- Edge f(*NI, NLI->element,NLI->weight);
+ Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
if(!edgesEqual(f,e) && *v==*(f.getSecond())){
int dir_count=inc_Dir(e,f);
int wt=1*f.getWeight();
@@ -129,15 +161,15 @@
}
}
- for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
+ for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
Graph::nodeList node_list=t.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
NLI!=NLE; ++NLI){
- Edge f(*NI, NLI->element,NLI->weight);
+ Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
if(!edgesEqual(f,e) && *v==*(f.getFirst())){
int dir_count=inc_Dir(e,f);
- int wt=1*f.getWeight();
+ int wt=f.getWeight();
inc_DFS(g,t, Increment, dir_count*events+wt,
f.getSecond(), f);
}
@@ -145,16 +177,18 @@
}
allNodes=g.getAllNodes();
- for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
+ for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
Graph::nodeList node_list=g.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
NLI!=NLE; ++NLI){
- Edge f(*NI, NLI->element,NLI->weight);
+ Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) ||
*v==*(f.getFirst()))){
int dir_count=inc_Dir(e,f);
Increment[f]+=dir_count*events;
+ //cerr<<"assigned "<<Increment[f]<<" to"<<endl;
+ //printEdge(f);
}
}
}
@@ -164,19 +198,19 @@
//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> getEdgeIncrements(Graph& g, Graph& t){
+static map<Edge, int, EdgeCompare> getEdgeIncrements(Graph& g, Graph& t){
//get all edges in g-t
- map<Edge, int> Increment;
+ map<Edge, int, EdgeCompare> Increment;
- list<Node *> allNodes=g.getAllNodes();
+ vector<Node *> allNodes=g.getAllNodes();
- for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
+ for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
Graph::nodeList node_list=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);
- if(!(t.hasEdge(ed))){
+ Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
+ if(!(t.hasEdgeAndWt(ed))){
Increment[ed]=0;;
}
}
@@ -185,14 +219,13 @@
Edge *ed=new Edge();
inc_DFS(g,t,Increment, 0, g.getRoot(), *ed);
-
- for(list<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
+ for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
Graph::nodeList node_list=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);
- if(!(t.hasEdge(ed))){
+ Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
+ if(!(t.hasEdgeAndWt(ed))){
int wt=ed.getWeight();
Increment[ed]+=wt;
}
@@ -202,13 +235,20 @@
return Increment;
}
+//push it up: TODO
+const graphListElement *findNodeInList(const Graph::nodeList &NL,
+ Node *N);
+
+graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
+//end TODO
+
//Based on edgeIncrements (above), now obtain
//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 *> &instr,
+static void getCodeInsertions(Graph &g, map<Edge, getEdgeCode *, EdgeCompare> &instr,
vector<Edge > &chords,
- map<Edge,int> &edIncrements){
+ map<Edge,int, EdgeCompare> &edIncrements){
//Register initialization code
vector<Node *> ws;
@@ -224,29 +264,34 @@
int edgeWt=nl->weight;
Node *w=nl->element;
//if chords has v->w
- Edge ed(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){
- if(*CI==ed){
+ if(*CI==ed && CI->getWeight()==edgeWt){//modf
hasEdge=true;
}
}
- if(hasEdge){
+
+ if(hasEdge){//so its a chord edge
getEdgeCode *edCd=new getEdgeCode();
edCd->setCond(1);
edCd->setInc(edIncrements[ed]);
instr[ed]=edCd;
+ //std::cerr<<"Case 1\n";
}
- else if((g.getPredNodes(w)).size()==1){
+ 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";
}
}
}
@@ -257,44 +302,55 @@
while(!ws.empty()) {
Node *w=ws.back();
ws.pop_back();
-
- //for each edge v->w
- list<Node *> preds=g.getPredNodes(w);
- for(list<Node *>::iterator pd=preds.begin(), pe=preds.end(); pd!=pe; ++pd){
- Node *v=*pd;
- //if chords has v->w
-
- Edge ed(v,w);
- getEdgeCode *edCd=new getEdgeCode();
- bool hasEdge=false;
- for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE;
- ++CI){
- if(*CI==ed){
- hasEdge=true;
- break;
+
+
+ ///////
+ //vector<Node *> lt;
+ vector<Node *> lllt=g.getAllNodes();
+ 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);
+ 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(5);
- edCd->setInc(edIncrements[ed]);
+ edCd->setCond(6);
instr[ed]=edCd;
}
-
- }
- else if(g.getSuccNodes(v).size()==1)
- ws.push_back(v);
- else{
- edCd->setCond(6);
- instr[ed]=edCd;
}
}
}
-
///// Register increment code
for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){
getEdgeCode *edCd=new getEdgeCode();
@@ -310,6 +366,7 @@
//If a->b is a backedge
//then incoming dummy edge is root->b
//and outgoing dummy edge is a->exit
+//changed
void addDummyEdges(vector<Edge > &stDummy,
vector<Edge > &exDummy,
Graph &g, vector<Edge> &be){
@@ -320,21 +377,15 @@
g.removeEdge(ed);
if(!(*second==*(g.getRoot()))){
- Edge *st=new Edge(g.getRoot(), second);
-
- //check if stDummy doesn't have it already
- if(find(stDummy.begin(), stDummy.end(), *st) == stDummy.end())
- stDummy.push_back(*st);
+ Edge *st=new Edge(g.getRoot(), second, ed.getWeight(), ed.getRandId());
+ stDummy.push_back(*st);
g.addEdgeForce(*st);
}
if(!(*first==*(g.getExit()))){
- Edge *ex=new Edge(first, g.getExit());
-
- if (find(exDummy.begin(), exDummy.end(), *ex) == exDummy.end()) {
- exDummy.push_back(*ex);
- g.addEdgeForce(*ex);
- }
+ Edge *ex=new Edge(first, g.getExit(), ed.getWeight(), ed.getRandId());
+ exDummy.push_back(*ex);
+ g.addEdgeForce(*ex);
}
}
}
@@ -344,34 +395,73 @@
cerr<<((ed.getFirst())->getElement())
->getName()<<"->"<<((ed.getSecond())
->getElement())->getName()<<
- ":"<<ed.getWeight()<<"\n";
+ ":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
}
//Move the incoming dummy edge code and outgoing dummy
//edge code over to the corresponding back edge
-static void moveDummyCode(const vector<Edge> &stDummy,
- const vector<Edge> &exDummy,
- const vector<Edge> &be,
- map<Edge, getEdgeCode *> &insertions){
- typedef vector<Edge >::const_iterator vec_iter;
+static void moveDummyCode(vector<Edge> &stDummy,
+ vector<Edge> &exDummy,
+ vector<Edge> &be,
+ map<Edge, getEdgeCode *, EdgeCompare> &insertions,
+ Graph &g){
+ typedef vector<Edge >::iterator vec_iter;
- DEBUG( //print all back, st and ex dummy
- cerr<<"BackEdges---------------\n";
- for(vec_iter VI=be.begin(); VI!=be.end(); ++VI)
- printEdge(*VI);
- cerr<<"StEdges---------------\n";
- for(vec_iter VI=stDummy.begin(); VI!=stDummy.end(); ++VI)
- printEdge(*VI);
- cerr<<"ExitEdges---------------\n";
- for(vec_iter VI=exDummy.begin(); VI!=exDummy.end(); ++VI)
- printEdge(*VI);
- cerr<<"------end all edges\n");
-
+ map<Edge,getEdgeCode *, EdgeCompare> temp;
+ //iterate over edges with code
std::vector<Edge> toErase;
- for(map<Edge,getEdgeCode *>::iterator MI=insertions.begin(),
+ for(map<Edge,getEdgeCode *, EdgeCompare>::iterator MI=insertions.begin(),
ME=insertions.end(); MI!=ME; ++MI){
Edge ed=MI->first;
getEdgeCode *edCd=MI->second;
+
+ ///---new code
+ //iterate over be, and check if its starts and end vertices hv code
+ 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);
+ }
+ else{
+ assert(false && "Not found in either start or end! Rand failed?");
+ }
+ }
+ }
+ }
+
+ 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(),
+ 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";
@@ -381,8 +471,10 @@
for(vec_iter VI=stDummy.begin(), VE=stDummy.end(); VI!=VE && !dummyHasIt;
++VI){
if(*VI==ed){
- DEBUG(cerr<<"Edge matched with stDummy\n");
-
+ //#ifdef DEBUG_PATH_PROFILES
+ cerr<<"Edge matched with stDummy\n";
+ printEdge(ed);
+ //#endif
dummyHasIt=true;
bool dummyInBe=false;
//dummy edge with code
@@ -392,17 +484,24 @@
Node *dm=ed.getSecond();
if(*dm==*st){
//so this is the back edge to use
- DEBUG(cerr<<"Moving to backedge\n";
- printEdge(backEdge));
-
+ //#ifdef DEBUG_PATH_PROFILES
+ cerr<<"Moving to backedge\n";
+ printEdge(backEdge);
+ //#endif
getEdgeCode *ged=new getEdgeCode();
ged->setCdIn(edCd);
- toErase.push_back(ed);
+ 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){
@@ -412,7 +511,10 @@
++VI){
if(*VI==ed){
inExDummy=true;
- DEBUG(cerr<<"Edge matched with exDummy\n");
+
+ //#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;
@@ -422,30 +524,45 @@
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);
+ 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
}
}
}
}
- DEBUG(cerr<<"size of deletions: "<<toErase.size()<<"\n");
+ */
+#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)
- for(vector<Edge >::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
- DEBUG(cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n");
}
//Do graph processing: to determine minimal edge increments,
@@ -456,7 +573,11 @@
Instruction *countInst,
vector<Edge >& be,
vector<Edge >& stDummy,
- vector<Edge >& exDummy){
+ vector<Edge >& exDummy,
+ int numPaths){
+
+ 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
@@ -502,8 +623,10 @@
DEBUG(printGraph(g2));
Graph *t=g2.getMaxSpanningTree();
- DEBUG(printGraph(*t));
-
+ //#ifdef DEBUG_PATH_PROFILES
+ //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
@@ -527,9 +650,11 @@
//the edge directions of corresponding edges in the directed graph
removeTreeEdges(g, *t);
- DEBUG(cerr<<"Spanning tree---------\n";
- printGraph(*t);
- cerr<<"-------end spanning tree\n");
+#ifdef DEBUG_PATH_PROFILES
+ cerr<<"Final Spanning tree---------\n";
+ printGraph(*t);
+ cerr<<"-------end spanning tree\n";
+#endif
//now remove the exit->root node
//and re-add it with weight 0
@@ -551,14 +676,18 @@
//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
- map<Edge, int> increment=getEdgeIncrements(g,*t);
- DEBUG(//print edge increments for debugging
- for(map<Edge, int>::iterator MI=increment.begin(), ME = increment.end();
- MI != ME; ++MI) {
- printEdge(MI->first);
- cerr << "Increment for above:" << MI->second << "\n";
- });
+ map<Edge, int, EdgeCompare> increment=getEdgeIncrements(g,*t);
+#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";
+ }
+#endif
+
//step 6: Get code insertions
@@ -569,40 +698,51 @@
vector<Edge> chords;
getChords(chords, g, *t);
- map<Edge, getEdgeCode *> codeInsertions;
+
+ //cerr<<"Graph before getCodeInsertion:\n";
+ //printGraph(g);
+ map<Edge, getEdgeCode *, EdgeCompare> codeInsertions;
getCodeInsertions(g, codeInsertions, chords,increment);
- DEBUG (//print edges with code for debugging
- cerr<<"Code inserted in following---------------\n";
- for(map<Edge, getEdgeCode *>::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";
- }
- cerr<<"-----end insertions\n");
+#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(),
+ cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
+ printEdge(cd_i->first);
+ cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
+ }
+ cerr<<"-----end insertions\n";
+#endif
//step 7: move code on dummy edges over to the back edges
//Move the incoming dummy edge code and outgoing dummy
//edge code over to the corresponding back edge
- moveDummyCode(stDummy, exDummy, be, codeInsertions);
-
- DEBUG(//debugging info
- cerr<<"After moving dummy code\n";
- for(map<Edge, getEdgeCode *>::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";
- }
- cerr<<"Dummy end------------\n");
+
+ 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 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";
+ }
+ cerr<<"Dummy end------------\n";
+#endif
+
//see what it looks like...
//now insert code along edges which have codes on them
for(map<Edge, getEdgeCode *>::iterator MI=codeInsertions.begin(),
ME=codeInsertions.end(); MI!=ME; ++MI){
Edge ed=MI->first;
- insertBB(ed, MI->second, rInst, countInst);
+ insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo);
}
}
@@ -610,18 +750,230 @@
//print the graph (for debugging)
void printGraph(Graph &g){
- list<Node *> lt=g.getAllNodes();
+ vector<Node *> lt=g.getAllNodes();
cerr<<"Graph---------------------\n";
- for(list<Node *>::iterator LI=lt.begin();
+ for(vector<Node *>::iterator LI=lt.begin();
LI!=lt.end(); ++LI){
cerr<<((*LI)->getElement())->getName()<<"->";
Graph::nodeList nl=g.getNodeList(*LI);
for(Graph::nodeList::iterator NI=nl.begin();
NI!=nl.end(); ++NI){
cerr<<":"<<"("<<(NI->element->getElement())
- ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
+ ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
+ <<NI->randId<<")";
}
cerr<<"\n";
}
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);
+}
+
+*/