if(color[BB]!=GREY && color[BB]!=BLACK){
if(!doDFS(BB, color)){
- return 0;
+ return 0;
}
}
M.getGlobalList().push_back(gb);
Constant *constArray = ConstantArray::get(ArrayType::get(Type::SByteTy,
- sBCons.size()),
- sBCons);
+ sBCons.size()),
+ sBCons);
GlobalVariable *funcArray = new GlobalVariable(constArray->getType(), true,
- GlobalValue::ExternalLinkage,
- constArray, "llvmSimpleFunction");
+ GlobalValue::ExternalLinkage,
+ constArray, "llvmSimpleFunction");
M.getGlobalList().push_back(funcArray);
ConstantInt *cnst = ConstantSInt::get(Type::IntTy, counter);
GlobalVariable *fnCount = new GlobalVariable(Type::IntTy, true,
- GlobalValue::ExternalLinkage,
- cnst, "llvmFunctionCount");
+ GlobalValue::ExternalLinkage,
+ cnst, "llvmFunctionCount");
M.getGlobalList().push_back(fnCount);
return true; // Always modifies program
}
enum Color { WHITE, GREY, BLACK };
void getBackEdgesVisit(BasicBlock *u,
- std::map<BasicBlock *, Color > &color,
- std::map<BasicBlock *, int > &d,
- int &time,
- std::map<BasicBlock *, BasicBlock *> &be);
+ std::map<BasicBlock *, Color > &color,
+ std::map<BasicBlock *, int > &d,
+ int &time,
+ std::map<BasicBlock *, BasicBlock *> &be);
void removeRedundant(std::map<BasicBlock *, BasicBlock *> &be);
public:
bool runOnFunction(Function &F);
std::map<BasicBlock *, Color > &color,
std::map<BasicBlock *, int > &d,
int &time,
- std::map<BasicBlock *, BasicBlock *> &be) {
+ std::map<BasicBlock *, BasicBlock *> &be) {
color[u]=GREY;
time++;
else if(color[BB]==GREY){
//so v is ancestor of u if time of u > time of v
if(d[u] >= d[BB]) // u->BB is a backedge
- be[u] = BB;
+ be[u] = BB;
}
}
color[u]=BLACK;//done with visiting the node and its neighbors
std::map<BasicBlock *, int> seenBB;
for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(),
- ME = be.end(); MI != ME; ++MI){
+ ME = be.end(); MI != ME; ++MI){
if(seenBB[MI->second])
continue;
sameTarget.clear();
for(std::map<BasicBlock *, BasicBlock *>::iterator MMI = be.begin(),
- MME = be.end(); MMI != MME; ++MMI){
+ MME = be.end(); MMI != MME; ++MMI){
if(MMI->first == MI->first)
- continue;
+ continue;
if(MMI->second == MI->second)
- sameTarget.push_back(MMI->first);
+ sameTarget.push_back(MMI->first);
}
std::map<PHINode *, std::vector<unsigned int> > phiMap;
for(std::vector<BasicBlock *>::iterator VBI = sameTarget.begin(),
- VBE = sameTarget.end(); VBI != VBE; ++VBI){
-
- BranchInst *ti = cast<BranchInst>((*VBI)->getTerminator());
- unsigned char index = 1;
- if(ti->getSuccessor(0) == MI->second)
- index = 0;
-
- ti->setSuccessor(index, newBB);
-
- for(BasicBlock::iterator BB2Inst = MI->second->begin(),
- BBend = MI->second->end(); BB2Inst != BBend; ++BB2Inst){
-
- if (PHINode *phiInst = dyn_cast<PHINode>(BB2Inst)){
- int bbIndex;
- bbIndex = phiInst->getBasicBlockIndex(*VBI);
- if(bbIndex>=0)
- phiMap[phiInst].push_back(bbIndex);
- }
- }
+ VBE = sameTarget.end(); VBI != VBE; ++VBI){
+
+ BranchInst *ti = cast<BranchInst>((*VBI)->getTerminator());
+ unsigned char index = 1;
+ if(ti->getSuccessor(0) == MI->second)
+ index = 0;
+
+ ti->setSuccessor(index, newBB);
+
+ for(BasicBlock::iterator BB2Inst = MI->second->begin(),
+ BBend = MI->second->end(); BB2Inst != BBend; ++BB2Inst){
+
+
if (PHINode *phiInst = dyn_cast<PHINode>(BB2Inst)){
+ int bbIndex;
+ bbIndex = phiInst->getBasicBlockIndex(*VBI);
+ if(bbIndex>=0)
+ phiMap[phiInst].push_back(bbIndex);
+ }
+ }
}
for(std::map<PHINode *, std::vector<unsigned int> >::iterator
- PI = phiMap.begin(), PE = phiMap.end(); PI != PE; ++PI){
-
- PHINode *phiNode = new PHINode(PI->first->getType(), "phi", newBranch);
- for(std::vector<unsigned int>::iterator II = PI->second.begin(),
- IE = PI->second.end(); II != IE; ++II){
- phiNode->addIncoming(PI->first->getIncomingValue(*II),
- PI->first->getIncomingBlock(*II));
- }
-
- std::vector<BasicBlock *> tempBB;
- for(std::vector<unsigned int>::iterator II = PI->second.begin(),
- IE = PI->second.end(); II != IE; ++II){
- tempBB.push_back(PI->first->getIncomingBlock(*II));
- }
-
- for(std::vector<BasicBlock *>::iterator II = tempBB.begin(),
- IE = tempBB.end(); II != IE; ++II){
- PI->first->removeIncomingValue(*II);
- }
-
- PI->first->addIncoming(phiNode, newBB);
+ PI = phiMap.begin(), PE = phiMap.end(); PI != PE; ++PI){
+
+ PHINode *phiNode = new PHINode(PI->first->getType(), "phi", newBranch);
+ for(std::vector<unsigned int>::iterator II = PI->second.begin(),
+ IE = PI->second.end(); II != IE; ++II){
+ phiNode->addIncoming(PI->first->getIncomingValue(*II),
+ PI->first->getIncomingBlock(*II));
+ }
+
+ std::vector<BasicBlock *> tempBB;
+ for(std::vector<unsigned int>::iterator II = PI->second.begin(),
+ IE = PI->second.end(); II != IE; ++II){
+ tempBB.push_back(PI->first->getIncomingBlock(*II));
+ }
+
+ for(std::vector<BasicBlock *>::iterator II = tempBB.begin(),
+ IE = tempBB.end(); II != IE; ++II){
+ PI->first->removeIncomingValue(*II);
+ }
+
+ PI->first->addIncoming(phiNode, newBB);
}
}
}
//get the code to be inserted on the edge
//This is determined from cond (1-6)
void getEdgeCode::getCode(Instruction *rInst, Value *countInst,
- Function *M, BasicBlock *BB,
+ Function *M, BasicBlock *BB,
vector<Value *> &retVec){
//Instruction *InsertPos = BB->getInstList().begin();
retVec.push_back(trAddIndex);
//insert trigger
//getTriggerCode(M->getParent(), BB, MethNo,
- // ConstantSInt::get(Type::IntTy,inc), newCount, triggerInst);
+ // ConstantSInt::get(Type::IntTy,inc), newCount, triggerInst);
//end trigger code
assert(inc>=0 && "IT MUST BE POSITIVE NOW");
//now load count[addIndex]
Instruction *castInst=new CastInst(addIndex,
- Type::LongTy,"ctin");//, InsertPos);
+ Type::LongTy,"ctin");//, InsertPos);
BB->getInstList().push_back(castInst);
vector<Value *> tmpVec;
//Count is an array, where Count[k] represents
//the number of executions of path k
void insertInTopBB(BasicBlock *front,
- int k,
- Instruction *rVar, Value *threshold){
+ int k,
+ Instruction *rVar, Value *threshold){
//rVar is variable r,
//countVar is count[]
//insert a basic block with appropriate code
//along a given edge
void insertBB(Edge ed,
- getEdgeCode *edgeCode,
- Instruction *rInst,
- Value *countInst,
- int numPaths, int Methno, Value *threshold){
+ getEdgeCode *edgeCode,
+ Instruction *rInst,
+ Value *countInst,
+ int numPaths, int Methno, Value *threshold){
BasicBlock* BB1=ed.getFirst()->getElement();
BasicBlock* BB2=ed.getSecond()->getElement();
namespace llvm {
const graphListElement *findNodeInList(const Graph::nodeList &NL,
- Node *N) {
+ Node *N) {
for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE;
++NI)
if (*NI->element== *N)
//graph constructor with root and exit specified
Graph::Graph(std::vector<Node*> n, std::vector<Edge> e,
- Node *rt, Node *lt){
+ Node *rt, Node *lt){
strt=rt;
ext=lt;
for(vector<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x)
Node *lnode=EI->first;
const nodeList &nl = getNodeList(lnode);
for(Graph::nodeList::const_iterator NI = nl.begin(), NE=nl.end(); NI != NE;
- ++NI)
+ ++NI)
if (*NI->element== *nd)
- count++;
+ count++;
}
return count;
}
//remove u frm vt
for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
if(**VI==*u){
- vt.erase(VI);
- break;
+ vt.erase(VI);
+ break;
}
}
//check if v is in vt
bool contains=false;
for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
- if(**VI==*v){
- contains=true;
- break;
- }
+ if(**VI==*v){
+ contains=true;
+ break;
+ }
}
DEBUG(std::cerr<<"wt:v->wt"<<weight<<":"<<v->getWeight()<<"\n";
printNode(v);std::cerr<<"node wt:"<<(*v).weight<<"\n");
//so if v in in vt, change wt(v) to wt(u->v)
//only if wt(u->v)<wt(v)
if(contains && weight<v->getWeight()){
- parent[v]=u;
- ed_weight[v]=weight;
- v->setWeight(weight);
+ parent[v]=u;
+ ed_weight[v]=weight;
+ v->setWeight(weight);
- DEBUG(std::cerr<<v->getWeight()<<":Set weight------\n";
+ DEBUG(std::cerr<<v->getWeight()<<":Set weight------\n";
printGraph();
printEdge(Edge(u,v,weight)));
}
Graph::nodeList &nl = getNodeList(*LI);
for(Graph::nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
std::cerr<<":"<<"("<<(NI->element->getElement())
- ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
+ ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
}
std::cerr<<"--------\n";
}
for(nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE; ++NLI){
Edge ed(NLI->element, *NI, NLI->weight);
if(!hasEdgeAndWt(ed)){
- DEBUG(std::cerr<<"######doesn't hv\n";
+ DEBUG(std::cerr<<"######doesn't hv\n";
printEdge(ed));
- addEdgeForce(ed);
+ addEdgeForce(ed);
}
}
}
++NI) {
nodeList &node_list = getNodeList(*NI);
for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end();
- NLI!=NLE; ++NLI)
+ NLI!=NLE; ++NLI)
NLI->weight=-NLI->weight;
}
}
//helper function to get back edges: it is called by
//the "getBackEdges" function above
void Graph::getBackEdgesVisit(Node *u, vector<Edge > &be,
- std::map<Node *, Color > &color,
- std::map<Node *, int > &d, int &time) {
+ std::map<Node *, Color > &color,
+ std::map<Node *, int > &d, int &time) {
color[u]=GREY;
time++;
d[u]=time;
vector<graphListElement> &succ_list = getNodeList(u);
for(vector<graphListElement>::iterator vl=succ_list.begin(),
- ve=succ_list.end(); vl!=ve; ++vl){
+ ve=succ_list.end(); vl!=ve; ++vl){
Node *v=vl->element;
if(color[v]!=GREY && color[v]!=BLACK){
getBackEdgesVisit(v, be, color, d, time);
if(color[v]==GREY){
//so v is ancestor of u if time of u > time of v
if(d[u] >= d[v]){
- Edge *ed=new Edge(u, v,vl->weight, vl->randId);
- if (!(*u == *getExit() && *v == *getRoot()))
- be.push_back(*ed); // choose the forward edges
+ Edge *ed=new Edge(u, v,vl->weight, vl->randId);
+ if (!(*u == *getExit() && *v == *getRoot()))
+ be.push_back(*ed); // choose the forward edges
}
}
}
//So we have a back edge when we meet a successor of
//a node with smaller time, and GREY color
void getBackEdgesVisit(Node *u,
- std::vector<Edge > &be,
- std::map<Node *, Color> &clr,
- std::map<Node *, int> &d,
- int &time);
+ std::vector<Edge > &be,
+ std::map<Node *, Color> &clr,
+ std::map<Node *, int> &d,
+ int &time);
public:
typedef nodeMapTy::iterator elementIterator;
//constructor with root and exit node specified
Graph(std::vector<Node*> n,
- std::vector<Edge> e, Node *rt, Node *lt);
+ std::vector<Edge> e, Node *rt, Node *lt);
//add a node
void addNode(Node *nd);
++NI){
Graph::nodeList node_list=g.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
- NLI!=NLE; ++NLI){
+ NLI!=NLE; ++NLI){
Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
if(!(st.hasEdgeAndWt(f)))//addnl
- chords.push_back(f);
+ chords.push_back(f);
}
}
}
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){
+ for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
Edge ed(NLI->element, *NI, NLI->weight);
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
int sz=nlist.size();
for(int i=0;i<sz-1; i++){
- int min=i;
- for(int j=i+1; j<sz; j++){
+ int min=i;
+ for(int j=i+1; j<sz; j++){
BasicBlock *bb1 = nlist[j].element->getElement();
BasicBlock *bb2 = nlist[min].element->getElement();
}
}
- graphListElement tempEl=nlist[min];
- nlist[min]=nlist[i];
- nlist[i]=tempEl;
+ 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];
+ GLI!=GLE; ++GLI){
+ GLI->weight=NumPaths[*RI];
+ NumPaths[*RI]+=NumPaths[GLI->element];
}
}
}
//check that the edges must have at least one common endpoint
assert(*(e.getFirst())==*(f.getFirst()) ||
- *(e.getFirst())==*(f.getSecond()) ||
- *(e.getSecond())==*(f.getFirst()) ||
- *(e.getSecond())==*(f.getSecond()));
+ *(e.getFirst())==*(f.getSecond()) ||
+ *(e.getSecond())==*(f.getFirst()) ||
+ *(e.getSecond())==*(f.getSecond()));
if(*(e.getFirst())==*(f.getSecond()) ||
*(e.getSecond())==*(f.getFirst()))
//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, EdgeCompare2>& Increment,
- int events, Node *v, Edge e){
+ int events, Node *v, Edge e){
vector<Node *> allNodes=t.getAllNodes();
++NI){
Graph::nodeList node_list=t.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
- NLI!= NLE; ++NLI){
+ NLI!= NLE; ++NLI){
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();
- inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
+ int dir_count=inc_Dir(e,f);
+ int wt=1*f.getWeight();
+ inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
}
}
}
++NI){
Graph::nodeList node_list=t.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
- NLI!=NLE; ++NLI){
+ NLI!=NLE; ++NLI){
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=f.getWeight();
- inc_DFS(g,t, Increment, dir_count*events+wt,
- f.getSecond(), f);
+ int dir_count=inc_Dir(e,f);
+ int wt=f.getWeight();
+ inc_DFS(g,t, Increment, dir_count*events+wt,
+ f.getSecond(), f);
}
}
}
++NI){
Graph::nodeList node_list=g.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
- NLI!=NLE; ++NLI){
+ NLI!=NLE; ++NLI){
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;
+ *v==*(f.getFirst()))){
+ int dir_count=inc_Dir(e,f);
+ Increment[f]+=dir_count*events;
}
}
}
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){
+ NLI!=NLE; ++NLI){
Edge ed(*NI, NLI->element,NLI->weight,NLI->randId);
if(!(t.hasEdgeAndWt(ed))){
- Increment[ed]=0;;
+ Increment[ed]=0;;
}
}
}
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){
+ NLI!=NLE; ++NLI){
Edge ed(*NI, NLI->element,NLI->weight, NLI->randId);
if(!(t.hasEdgeAndWt(ed))){
- int wt=ed.getWeight();
- Increment[ed]+=wt;
+ int wt=ed.getWeight();
+ Increment[ed]+=wt;
}
}
}
//push it up: TODO
const graphListElement *findNodeInList(const Graph::nodeList &NL,
- Node *N);
+ Node *N);
graphListElement *findNodeInList(Graph::nodeList &NL, Node *N);
//end TODO
Graph::nodeList succs=g.getNodeList(v);
for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end();
- nl!=ne; ++nl){
+ nl!=ne; ++nl){
int edgeWt=nl->weight;
Node *w=nl->element;
//if chords has v->w
Edge ed(v,w, edgeWt, nl->randId);
bool hasEdge=false;
for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end();
- CI!=CE && !hasEdge;++CI){
- if(*CI==ed && CI->getWeight()==edgeWt){//modf
- hasEdge=true;
- }
+ CI!=CE && !hasEdge;++CI){
+ if(*CI==ed && CI->getWeight()==edgeWt){//modf
+ hasEdge=true;
+ }
}
if(hasEdge){//so its a chord edge
- getEdgeCode *edCd=new getEdgeCode();
- edCd->setCond(1);
- edCd->setInc(edIncrements[ed]);
- instr[ed]=edCd;
+ getEdgeCode *edCd=new getEdgeCode();
+ edCd->setCond(1);
+ edCd->setInc(edIncrements[ed]);
+ instr[ed]=edCd;
}
else if(g.getNumberOfIncomingEdges(w)==1){
- ws.push_back(w);
+ ws.push_back(w);
}
else{
- getEdgeCode *edCd=new getEdgeCode();
- edCd->setCond(2);
- edCd->setInc(0);
- instr[ed]=edCd;
+ getEdgeCode *edCd=new getEdgeCode();
+ edCd->setCond(2);
+ edCd->setInc(0);
+ 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){
+ if (*N->element == *w){
Node *v=lnode;
//if chords has v->w
//and outgoing dummy edge is a->exit
//changed
void addDummyEdges(vector<Edge > &stDummy,
- vector<Edge > &exDummy,
- Graph &g, vector<Edge> &be){
+ vector<Edge > &exDummy,
+ Graph &g, vector<Edge> &be){
for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
Edge ed=*VI;
Node *first=ed.getFirst();
void printEdge(Edge ed){
cerr<<((ed.getFirst())->getElement())
->getName()<<"->"<<((ed.getSecond())
- ->getElement())->getName()<<
+ ->getElement())->getName()<<
":"<<ed.getWeight()<<" rndId::"<<ed.getRandId()<<"\n";
}
vector<Edge> &exDummy,
vector<Edge> &be,
map<Edge, getEdgeCode *, EdgeCompare2> &insertions,
- Graph &g){
+ Graph &g){
typedef vector<Edge >::iterator vec_iter;
map<Edge,getEdgeCode *, EdgeCompare2> temp;
//iterate over edges with code
std::vector<Edge> toErase;
for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=insertions.begin(),
- ME=insertions.end(); MI!=ME; ++MI){
+ ME=insertions.end(); MI!=ME; ++MI){
Edge ed=MI->first;
getEdgeCode *edCd=MI->second;
//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()){
-
- 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?");
- }
+
+ 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?");
+ }
}
}
}
//appropriate code insertions etc and insert the code at
//appropriate locations
void processGraph(Graph &g,
- Instruction *rInst,
- Value *countInst,
- vector<Edge >& be,
- vector<Edge >& stDummy,
- vector<Edge >& exDummy,
- int numPaths, int MethNo,
+ Instruction *rInst,
+ Value *countInst,
+ vector<Edge >& be,
+ vector<Edge >& stDummy,
+ vector<Edge >& exDummy,
+ int numPaths, int MethNo,
Value *threshold){
//Given a graph: with exit->root edge, do the following in seq:
//print edges with code for debugging
cerr<<"Code inserted in following---------------\n";
for(map<Edge, getEdgeCode *, EdgeCompare2>::iterator cd_i=codeInsertions.begin(),
- cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
+ cd_e=codeInsertions.end(); cd_i!=cd_e; ++cd_i){
printEdge(cd_i->first);
cerr<<cd_i->second->getCond()<<":"<<cd_i->second->getInc()<<"\n";
}
//debugging info
cerr<<"After moving dummy code\n";
for(map<Edge, getEdgeCode *,EdgeCompare2>::iterator cd_i=codeInsertions.begin(),
- cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
+ cd_e=codeInsertions.end(); cd_i != cd_e; ++cd_i){
printEdge(cd_i->first);
cerr<<cd_i->second->getCond()<<":"
- <<cd_i->second->getInc()<<"\n";
+ <<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 *,EdgeCompare2>::iterator MI=codeInsertions.begin(),
- ME=codeInsertions.end(); MI!=ME; ++MI){
+ ME=codeInsertions.end(); MI!=ME; ++MI){
Edge ed=MI->first;
insertBB(ed, MI->second, rInst, countInst, numPaths, MethNo, threshold);
}
cerr<<((*LI)->getElement())->getName()<<"->";
Graph::nodeList nl=g.getNodeList(*LI);
for(Graph::nodeList::iterator NI=nl.begin();
- NI!=nl.end(); ++NI){
+ NI!=nl.end(); ++NI){
cerr<<":"<<"("<<(NI->element->getElement())
- ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
- <<NI->randId<<")";
+ ->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<","
+ <<NI->randId<<")";
}
cerr<<"\n";
}
Function *inCountMth;
DominatorSet *DS;
void getBackEdgesVisit(BasicBlock *u,
- std::map<BasicBlock *, Color > &color,
- std::map<BasicBlock *, int > &d,
- int &time, BBMap &be);
+ std::map<BasicBlock *, Color > &color,
+ std::map<BasicBlock *, int > &d,
+ int &time, BBMap &be);
void removeRedundant(BBMap &be);
void findAndInstrumentBackEdges(Function &F);
public:
else if(color[BB]==GREY){
//so v is ancestor of u if time of u > time of v
if(d[u] >= d[BB]){
- //u->BB is a backedge
- be[u] = BB;
+ //u->BB is a backedge
+ be[u] = BB;
}
}
}
void InstLoops::removeRedundant(BBMap &be) {
std::vector<BasicBlock *> toDelete;
for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(),
- ME = be.end(); MI != ME; ++MI)
+ ME = be.end(); MI != ME; ++MI)
for(BBMap::iterator MMI = be.begin(), MME = be.end(); MMI != MME; ++MMI)
if(DS->properlyDominates(MI->first, MMI->first))
- toDelete.push_back(MMI->first);
+ toDelete.push_back(MMI->first);
// Remove all the back-edges we found from be.
for(std::vector<BasicBlock *>::iterator VI = toDelete.begin(),
- VE = toDelete.end(); VI != VE; ++VI)
+ VE = toDelete.end(); VI != VE; ++VI)
be.erase(*VI);
}
removeRedundant(be);
for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(),
- ME = be.end(); MI != ME; ++MI){
+ ME = be.end(); MI != ME; ++MI){
BasicBlock *u = MI->first;
BasicBlock *BB = MI->second;
// We have a back-edge from BB --> u.
//Routines to get the path trace!
void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph &g,
- vector<Edge> &stDummy, vector<Edge> &exDummy,
- vector<Edge> &be,
- double strand){
+ vector<Edge> &stDummy, vector<Edge> &exDummy,
+ vector<Edge> &be,
+ double strand){
Graph::nodeList &nlist = g.getNodeList(n);
//printGraph(g);
nextRoot=NLI->element;
edgeRnd=NLI->randId;
if(isStart)
- strand=NLI->randId;
+ strand=NLI->randId;
}
}
bool has1=false, has2=false;
//check if exit has it
for(vector<Edge>::iterator VI=exDummy.begin(), VE=exDummy.end(); VI!=VE;
- ++VI){
+ ++VI){
if(VI->getRandId()==edgeRnd){
- has2=true;
- break;
+ has2=true;
+ break;
}
}
//check if start has it
for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE;
- ++VI){
+ ++VI){
if(VI->getRandId()==strand){
- has1=true;
- break;
+ 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();
+ assert(vBB.size()>0 && "vector too small");
+ if( VI->getSecond()->getElement() == vBB[1] ){
+ //vBB[0]=VI->getFirst()->getElement();
vBB.erase(vBB.begin());
- break;
- }
+ 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] &&
+ assert(vBB.size()>0 && "vector too small");
+ if( VI->getFirst()->getElement() == vBB[vBB.size()-1] &&
VI->getSecond()->getElement() == vBB[0]){
- //vBB.push_back(VI->getSecond()->getElement());
- break;
- }
+ //vBB.push_back(VI->getSecond()->getElement());
+ break;
+ }
}
}
else
assert(pathNo-maxCount>=0);
return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy,
- exDummy, be, strand);
+ exDummy, be, strand);
}
ModulePass *llvm::createTraceBasicBlockPass()
{
- return new TraceBasicBlocks();
+ return new TraceBasicBlocks();
}
static void InsertInstrumentationCall (BasicBlock *BB,
static cl::list<std::string>
TraceFuncNames("tracefunc", cl::desc("Only trace specific functions in the "
"-trace or -tracem passes"),
- cl::value_desc("function"), cl::Hidden);
+ cl::value_desc("function"), cl::Hidden);
static void TraceValuesAtBBExit(BasicBlock *BB,
Function *Printf, Function* HashPtrToSeqNum,
isa<UnwindInst>(I) || isa<UnreachableInst>(I)) {
// FIXME: Unreachable instructions should not be marked intrinsically
// live here.
- markInstructionLive(I);
+ markInstructionLive(I);
} else if (isInstructionTriviallyDead(I)) {
// Remove the instruction from it's basic block...
BB->getInstList().erase(I);
I.getName()), I);
}
}
-
+
if (Op1)
return new SelectInst(LHSI->getOperand(0), Op1, Op2);
break;
if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
C = CS->getOperand(El);
} else if (isa<ConstantAggregateZero>(C)) {
- C = Constant::getNullValue(STy->getElementType(El));
+ C = Constant::getNullValue(STy->getElementType(El));
} else if (isa<UndefValue>(C)) {
- C = UndefValue::get(STy->getElementType(El));
+ C = UndefValue::get(STy->getElementType(El));
} else {
return 0;
}
} else if (I->hasOneUse() && I->use_back() == Term) {
// Ignore instructions only used by the loop terminator.
} else if (DbgInfoIntrinsic *DbgI = dyn_cast<DbgInfoIntrinsic>(I)) {
- // Ignore debug instructions
+ // Ignore debug instructions
} else {
++Size;
}
// Transform load (constantexpr_GEP global, 0, ...) into the value loaded.
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
if (CE->getOpcode() == Instruction::GetElementPtr)
- if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
- if (GV->isConstant() && !GV->isExternal())
- if (Constant *V =
- GetGEPGlobalInitializer(GV->getInitializer(), CE)) {
- markConstant(IV, &I, V);
- return;
- }
+ if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
+ if (GV->isConstant() && !GV->isExternal())
+ if (Constant *V =
+ GetGEPGlobalInitializer(GV->getInitializer(), CE)) {
+ markConstant(IV, &I, V);
+ return;
+ }
}
// Otherwise we cannot say for certain what value this load will produce.
void SCCPSolver::Solve() {
// Process the work lists until they are empty!
while (!BBWorkList.empty() || !InstWorkList.empty() ||
- !OverdefinedInstWorkList.empty()) {
+ !OverdefinedInstWorkList.empty()) {
// Process the instruction work list...
while (!OverdefinedInstWorkList.empty()) {
Value *I = OverdefinedInstWorkList.back();
//this loop. To fix the phi nodes, we delete incoming branches
//that are not in the trace.
for(std::vector<BasicBlock *>::const_iterator T = origTrace.begin(),
- End = origTrace.end(); T != End; ++T) {
+ End = origTrace.end(); T != End; ++T) {
//Clone Basic Block
BasicBlock *clonedBlock =
//Second loop to do the remapping
for(std::vector<BasicBlock *>::const_iterator BB = clonedTrace.begin(),
- BE = clonedTrace.end(); BB != BE; ++BB) {
+ BE = clonedTrace.end(); BB != BE; ++BB) {
for(BasicBlock::iterator I = (*BB)->begin(); I != (*BB)->end(); ++I) {
//Loop over all the operands of the instruction
for(unsigned op=0, E = I->getNumOperands(); op != E; ++op) {
- const Value *Op = I->getOperand(op);
-
- //Get it out of the value map
- Value *V = ValueMap[Op];
-
- //If not in the value map, then its outside our trace so ignore
- if(V != 0)
- I->setOperand(op,V);
+ const Value *Op = I->getOperand(op);
+
+ //Get it out of the value map
+ Value *V = ValueMap[Op];
+
+ //If not in the value map, then its outside our trace so ignore
+ if(V != 0)
+ I->setOperand(op,V);
}
}
}
bool DontDeleteUselessPHIs) {
assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
- "removePredecessor: BB is not a predecessor!");
+ "removePredecessor: BB is not a predecessor!");
if (InstList.empty()) return;
PHINode *APN = dyn_cast<PHINode>(&front());
BasicBlock *BasicBlock::splitBasicBlock(iterator I, const std::string &BBName) {
assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
assert(I != InstList.end() &&
- "Trying to get me to create degenerate basic block!");
+ "Trying to get me to create degenerate basic block!");
BasicBlock *New = new BasicBlock(BBName, getParent(), getNext());
Roots.clear();
Roots.push_back(Root);
assert(pred_begin(Root) == pred_end(Root) &&
- "Root node has predecessors in function!");
+ "Root node has predecessors in function!");
ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
Doms.clear();
DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
for (; CDFI != CDFE; ++CDFI) {
if (!Node->dominates(DT[*CDFI]))
- S.insert(*CDFI);
+ S.insert(*CDFI);
}
}
projects / oota-llvm.git / commitdiff