#include "llvm/iOperators.h"
#include "llvm/iPHINode.h"
#include "llvm/Module.h"
-#include <string.h>
#include <stdio.h>
#define INSERT_LOAD_COUNT
static void getTriggerCode(Module *M, BasicBlock *BB, int MethNo, Value *pathNo,
Value *cnt, Instruction *InsertPos){
- static int i=-1;
- i++;
- char gstr[100];
- sprintf(gstr,"globalVar%d",i);
- std::string globalVarName=gstr;
+
vector<const Type*> args;
//args.push_back(PointerType::get(Type::SByteTy));
args.push_back(Type::IntTy);
args.push_back(Type::IntTy);
const FunctionType *MTy = FunctionType::get(Type::VoidTy, args, false);
- // Function *triggerMeth = M->getOrInsertFunction("trigger", MTy);
Function *trigMeth = M->getOrInsertFunction("trigger", MTy);
assert(trigMeth && "trigger method could not be inserted!");
- //if (Value *triggerMeth = ST->lookup(PointerType::get(MTy), "trigger")) {
- //Function *trigMeth = cast<Function>(triggerMeth);
- vector<Value *> trargs;
-
- //pred_iterator piter=BB->pred_begin();
- //std::string predName = "uu";//BB->getName();
- //Constant *bbName=ConstantArray::get(predName);//BB->getName());
- //GlobalVariable *gbl=new GlobalVariable(ArrayType::get(Type::SByteTy,
- // predName.size()+1),
- // true, true, bbName, gstr);
-
- //M->getGlobalList().push_back(gbl);
- //vector<Value *> elargs;
- //elargs.push_back(ConstantSInt::get(Type::LongTy, 0));
- //elargs.push_back(ConstantSInt::get(Type::LongTy, 0));
-
- // commented out bb name frm which its called
- //Instruction *getElmntInst=new GetElementPtrInst(gbl,elargs,"elmntInst");
-
- //trargs.push_back(ConstantArray::get(BB->getName()));
-
- //trargs.push_back(getElmntInst);
- //trargs.push_back(bbName);
+ vector<Value *> trargs;
trargs.push_back(ConstantSInt::get(Type::IntTy,MethNo));
-
- //trargs.push_back(ConstantSInt::get(Type::IntTy,-1));//erase this
trargs.push_back(pathNo);
trargs.push_back(cnt);
+
Instruction *callInst=new CallInst(trigMeth, trargs, "", InsertPos);
}
Function *M,
BasicBlock *BB, int numPaths, int MethNo){
- Instruction *InsertPos = BB->begin();
+ Instruction *InsertPos = BB->getInstList().begin();
//case: r=k code to be inserted
switch(cond){
Value *val=ConstantSInt::get(Type::IntTy,inc);
Instruction *addIndex=BinaryOperator::
create(Instruction::Add, ldIndex, val,"ti2", InsertPos);
- //erase following 1 line
- //Value *valtemp=ConstantSInt::get(Type::IntTy,999);
- //now load count[addIndex]
+ //now load count[addIndex]
Instruction *castInst=new CastInst(addIndex,
Type::LongTy,"ctin", InsertPos);
Instruction *Idx = new GetElementPtrInst(countInst,
Instruction *ldInst=new LoadInst(Idx, "ti3", InsertPos);
Value *cons=ConstantSInt::get(Type::IntTy,1);
//count[addIndex]++
- Value *addIn = BinaryOperator::create(Instruction::Add, ldInst, cons,
- "ti4", InsertPos);
+ Value *addIn = BinaryOperator::create(Instruction::Add, ldInst,
+ cons,"", InsertPos);
#ifdef INSERT_STORE
- ///*
- new StoreInst(addIn, Idx, InsertPos);
- //*/
+ Instruction *stInst = new StoreInst(addIn, Idx, InsertPos);
#endif
//insert trigger
//insert trigger
getTriggerCode(M->getParent(), BB, MethNo, ldIndex, addIn, InsertPos);
//end trigger code
-
break;
}
//store uint 0, uint *%R
new StoreInst(Int0, rVar, here);
+
+ if(front->getParent()->getName() == "main"){
+
+ //if its a main function, do the following!
+ //A global variable: %llvm_threshold
+ //%llvm_threshold = uninitialized global int
+ GlobalVariable *threshold = new GlobalVariable(Type::IntTy, false, true, 0,
+ "reopt_threshold");
+
+ front->getParent()->getParent()->getGlobalList().push_back(threshold);
+
+ vector<const Type*> initialize_args;
+ initialize_args.push_back(PointerType::get(Type::IntTy));
+
+ const FunctionType *Fty = FunctionType::get(Type::VoidTy, initialize_args,
+ false);
+ Function *initialMeth = front->getParent()->getParent()->getOrInsertFunction("reoptimizerInitialize", Fty);
+ assert(initialMeth && "Initialize method could not be inserted!");
+
+ vector<Value *> trargs;
+ trargs.push_back(threshold);
+
+ new CallInst(initialMeth, trargs, "", front->begin());
+ }
}
Instruction *rInst,
Instruction *countInst,
int numPaths, int Methno){
- static int i=-1;
- i++;
+
BasicBlock* BB1=ed.getFirst()->getElement();
BasicBlock* BB2=ed.getSecond()->getElement();
cerr<<"########################\n";
#endif
- char counterstr[100];
- sprintf(counterstr,"counter%d",i);
- std::string ctr=counterstr;
-
//We need to insert a BB between BB1 and BB2
TerminatorInst *TI=BB1->getTerminator();
- BasicBlock *newBB=new BasicBlock(ctr, BB1->getParent());
+ BasicBlock *newBB=new BasicBlock("counter", BB1->getParent());
//Is terminator a branch instruction?
//then we need to change branch destinations to include new BB
- //std::cerr<<"before cast!\n";
- //std::cerr<<"Method no in Edgecode:"<<Methno<<"\n";
- //std::cerr<<"Instruction\n";
- //std::cerr<<*TI;
BranchInst *BI = cast<BranchInst>(TI);
if(BI->isUnconditional()){
//get code for the new BB
edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB, numPaths, Methno);
-
- //std::cerr<<"After casting\n";
//get code for the new BB
- //now iterate over BB2, and set its Phi nodes right
+ //now iterate over BB2, and set its Phi nodes right
for(BasicBlock::iterator BB2Inst = BB2->begin(), BBend = BB2->end();
BB2Inst != BBend; ++BB2Inst){
}
//sorting edgelist, called by backEdgeVist ONLY!!!
-Graph::nodeList &Graph::sortNodeList(Node *par, nodeList &nl){
+Graph::nodeList &Graph::sortNodeList(Node *par, nodeList &nl, vector<Edge> &be){
assert(par && "null node pointer");
BasicBlock *bbPar = par->getElement();
if(nl.size()<=1) return nl;
+ if(getExit() == par) return nl;
for(nodeList::iterator NLI = nl.begin(), NLE = nl.end()-1; NLI != NLE; ++NLI){
nodeList::iterator min = NLI;
for(nodeList::iterator LI = NLI+1, LE = nl.end(); LI!=LE; ++LI){
//if LI < min, min = LI
- if(min->element->getElement() == LI->element->getElement())
- continue;
-
-
- TerminatorInst *tti = par->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(min->element->getElement() == LI->element->getElement() &&
+ min->element == getExit()){
+
+ //same successors: so might be exit???
+ //if it is exit, then see which is backedge
+ //check if LI is a left back edge!
+
+ TerminatorInst *tti = par->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);
+ //so one of LI or min must be back edge!
+ //Algo: if succ(0)!=LI (and so !=min) then succ(0) is backedge
+ //and then see which of min or LI is backedge
+ //THEN if LI is in be, then min=LI
+ if(LI->element->getElement() != tB){//so backedge must be made min!
+ for(vector<Edge>::iterator VBEI = be.begin(), VBEE = be.end();
+ VBEI != VBEE; ++VBEI){
+ if(VBEI->getRandId() == LI->randId){
+ min = LI;
+ break;
+ }
+ else if(VBEI->getRandId() == min->randId)
+ break;
+ }
+ }
+ else{// if(LI->element->getElement() != fB)
+ for(vector<Edge>::iterator VBEI = be.begin(), VBEE = be.end();
+ VBEI != VBEE; ++VBEI){
+ if(VBEI->getRandId() == min->randId){
+ min = LI;
+ break;
+ }
+ else if(VBEI->getRandId() == LI->randId)
+ break;
+ }
+ }
+ }
- if(tB == LI->element->getElement() || fB == min->element->getElement())
- min = LI;
+ else if (min->element->getElement() != LI->element->getElement()){
+ TerminatorInst *tti = par->getElement()->getTerminator();
+ BranchInst *ti = cast<BranchInst>(tti);
+ assert(ti && "not a branch");
+
+ if(ti->getNumSuccessors()<=1) continue;
+
+ assert(ti->getNumSuccessors()==2 && "less successors!");
+
+ BasicBlock *tB = ti->getSuccessor(0);
+ BasicBlock *fB = ti->getSuccessor(1);
+
+ if(tB == LI->element->getElement() || fB == min->element->getElement())
+ min = LI;
+ }
}
graphListElement tmpElmnt = *min;
DFS_Visit(*LI, toReturn);
}
- //print nodes
- //std::cerr<<"Topological sort--------\n";
- //for(vector<Node *>::iterator VI = toReturn.begin(), VE = toReturn.end();
- // VI!=VE; ++VI)
- //std::cerr<<(*VI)->getElement()->getName()<<"->";
- //std::cerr<<"\n----------------------\n";
return toReturn;
}
//a node with smaller time, and GREY color
void Graph::getBackEdges(vector<Edge > &be, map<Node *, int> &d){
map<Node *, Color > color;
- //map<Node *, int > d;
- //vector<Node *> allNodes=getAllNodes();
int time=0;
- //for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end();
- // NI!=NE; ++NI){
- //if(color[*NI]!=GREY && color[*NI]!=BLACK)
- //printGraph();
- getBackEdgesVisit(getRoot(), be, color, d, time);//*NI, be, color, d, time);
- //}
+
+ getBackEdgesVisit(getRoot(), be, color, d, time);
}
//helper function to get back edges: it is called by
time++;
d[u]=time;
- //std::cerr<<"Node list-----\n";
- vector<graphListElement> succ_list = getSortedNodeList(u);
-
- //for(vector<graphListElement>::iterator vl=succ_list.begin(),
- // ve=succ_list.end(); vl!=ve; ++vl){
- //Node *v=vl->element;
- //std::cerr<<v->getElement()->getName()<<"->";
- //}
- //std::cerr<<"\n-------- end Node list\n";
+ vector<graphListElement> &succ_list = getNodeList(u);
for(vector<graphListElement>::iterator vl=succ_list.begin(),
ve=succ_list.end(); vl!=ve; ++vl){
Node *v=vl->element;
- // for(vector<Node *>::const_iterator v=succ_list.begin(), ve=succ_list.end();
- // v!=ve; ++v){
-
- if(color[v]!=GREY && color[v]!=BLACK){
- getBackEdgesVisit(v, be, color, d, time);
- }
+ if(color[v]!=GREY && color[v]!=BLACK){
+ getBackEdgesVisit(v, be, color, d, time);
+ }
//now checking for d and f vals
if(color[v]==GREY){
return name1<name2;
}
};
-struct EdgeCompare{
+
+struct EdgeCompare2{
bool operator()(Edge e1, Edge e2) const {
assert(!e1.isNull() && !e2.isNull());
Node *x1=e1.getFirst();
Node *y2=e2.getSecond();
int w1=e1.getWeight();
int w2=e2.getWeight();
- return (*x1<*y1 || (*x1==*y1 && *x2<*y2) || (*x1==*y1 && *x2==*y2 && w1<w2));
+ double r1 = e1.getRandId();
+ double r2 = e2.getRandId();
+ //return (*x1<*y1 || (*x1==*y1 && *x2<*y2) || (*x1==*y1 && *x2==*y2 && w1<w2));
+ return (*x1<*y1 || (*x1==*y1 && *x2<*y2) || (*x1==*y1 && *x2==*y2 && w1<w2) || (*x1==*y1 && *x2==*y2 && w1==w2 && r1<r2));
}
};
+//struct EdgeCompare2{
+//bool operator()(Edge e1, Edge e2) const {
+// assert(!e1.isNull() && !e2.isNull());
+// return (e1.getRandId()<e2.getRandId());
+//}
+//};
//this is used to color vertices
//get a vector of back edges in the graph
void getBackEdges(std::vector<Edge> &be, std::map<Node *, int> &d);
- nodeList &sortNodeList(Node *par, nodeList &nl);
+ nodeList &sortNodeList(Node *par, nodeList &nl, std::vector<Edge> &be);
//Get the Maximal spanning tree (also a graph)
//of the graph
return nodes[nd];//sortNodeList(nd, nli->second);
}
- nodeList &getSortedNodeList(Node *nd) {
+ nodeList &getSortedNodeList(Node *nd, std::vector<Edge> &be) {
elementIterator nli = nodes.find(nd);
assert(nli != nodes.end() && "Node must be in nodes map");
- return sortNodeList(nd, nodes[nd]);
+ return sortNodeList(nd, nodes[nd], be);
}
//get the root of the graph
//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, std::map<Node *, int> nodePriority);
+int valueAssignmentToEdges(Graph& g, std::map<Node *, int> nodePriority,
+ std::vector<Edge> &be);
void getBBtrace(std::vector<BasicBlock *> &vBB, int pathNo, Function *M);
#endif
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
+#include "llvm/Transforms/Instrumentation/Graph.h"
#include "llvm/Function.h"
#include "llvm/Pass.h"
+#include "llvm/Module.h"
+#include "llvm/Function.h"
#include "llvm/BasicBlock.h"
#include "llvm/InstrTypes.h"
-#include "llvm/Transforms/Instrumentation/Graph.h"
#include "llvm/iTerminators.h"
#include <algorithm>
#include <iostream>
#include <sstream>
+#include <vector>
#include <string>
//using std::list;
//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, map<Node *, int> nodePriority){
+int valueAssignmentToEdges(Graph& g, map<Node *, int> nodePriority,
+ vector<Edge> &be){
vector<Node *> revtop=g.reverseTopologicalSort();
map<Node *,int > NumPaths;
for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end();
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();
else{
TerminatorInst *tti = (*RI)->getElement()->getTerminator();
- //std::cerr<<*tti<<std::endl;
+
BranchInst *ti = cast<BranchInst>(tti);
assert(ti && "not a branch");
assert(ti->getNumSuccessors()==2 && "less successors!");
}
//sorted now!
- //std::cerr<<"Considering Order-----\n";
for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
GLI!=GLE; ++GLI){
- //std::cerr<<GLI->element->getElement()->getName()<<"->";
- GLI->weight=NumPaths[*RI];
+ GLI->weight=NumPaths[*RI];
NumPaths[*RI]+=NumPaths[GLI->element];
}
- //std::cerr<<"\nend order $$$$$$$$$$$$$$$$$$$$$$$$\n";
}
}
return NumPaths[g.getRoot()];
//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();
//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;
}
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);
- graphListElement *N = findNodeInList(nl, w);
- if (N){
- 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;
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;
}
//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";
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
+#include "llvm/Transforms/Instrumentation/Graph.h"
#include "llvm/Function.h"
#include "llvm/Pass.h"
+#include "llvm/Module.h"
+#include "llvm/Function.h"
#include "llvm/BasicBlock.h"
#include "llvm/InstrTypes.h"
-#include "llvm/Transforms/Instrumentation/Graph.h"
#include "llvm/iTerminators.h"
#include <algorithm>
#include <iostream>
#include <sstream>
+#include <vector>
#include <string>
//using std::list;
//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, map<Node *, int> nodePriority){
+int valueAssignmentToEdges(Graph& g, map<Node *, int> nodePriority,
+ vector<Edge> &be){
vector<Node *> revtop=g.reverseTopologicalSort();
map<Node *,int > NumPaths;
for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end();
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();
else{
TerminatorInst *tti = (*RI)->getElement()->getTerminator();
- //std::cerr<<*tti<<std::endl;
+
BranchInst *ti = cast<BranchInst>(tti);
assert(ti && "not a branch");
assert(ti->getNumSuccessors()==2 && "less successors!");
}
//sorted now!
- //std::cerr<<"Considering Order-----\n";
for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
GLI!=GLE; ++GLI){
- //std::cerr<<GLI->element->getElement()->getName()<<"->";
- GLI->weight=NumPaths[*RI];
+ GLI->weight=NumPaths[*RI];
NumPaths[*RI]+=NumPaths[GLI->element];
}
- //std::cerr<<"\nend order $$$$$$$$$$$$$$$$$$$$$$$$\n";
}
}
return NumPaths[g.getRoot()];
//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();
//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;
}
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);
- graphListElement *N = findNodeInList(nl, w);
- if (N){
- 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;
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;
}
//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";
projects / oota-llvm.git / commitdiff