diff options
9 files changed, 0 insertions, 3043 deletions
diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp deleted file mode 100644 index 5e4264ebfd5..00000000000 --- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp +++ /dev/null @@ -1,189 +0,0 @@ -//===-- CombineBranch.cpp -------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Combine multiple back-edges going to the same sink into a single -// back-edge. This introduces a new basic block and back-edge branch for each -// such sink. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Support/CFG.h" -#include "llvm/Instructions.h" -#include "llvm/Function.h" -#include "llvm/Pass.h" -#include "llvm/Type.h" - -namespace llvm { - -namespace { - struct CombineBranches : public FunctionPass { - private: - /// Possible colors that a vertex can have during depth-first search for - /// back-edges. - /// - 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); - void removeRedundant(std::map<BasicBlock *, BasicBlock *> &be); - public: - bool runOnFunction(Function &F); - }; - - RegisterOpt<CombineBranches> - X("branch-combine", "Multiple backedges going to same target are merged"); -} - -/// getBackEdgesVisit - Get the back-edges of the control-flow graph for this -/// function. We proceed recursively using depth-first search. We get -/// back-edges by associating a time and a color with each vertex. The time of a -/// vertex is the time when it was first visited. The color of a vertex is -/// initially WHITE, changes to GREY when it is first visited, and changes to -/// BLACK when ALL its neighbors have been visited. So we have a back edge when -/// we meet a successor of a node with smaller time, and GREY color. -/// -void CombineBranches::getBackEdgesVisit(BasicBlock *u, - std::map<BasicBlock *, Color > &color, - std::map<BasicBlock *, int > &d, - int &time, - std::map<BasicBlock *, BasicBlock *> &be) { - - color[u]=GREY; - time++; - d[u]=time; - - for (succ_iterator vl = succ_begin(u), ve = succ_end(u); vl != ve; ++vl){ - BasicBlock *BB = *vl; - - if(color[BB]!=GREY && color[BB]!=BLACK) - getBackEdgesVisit(BB, color, d, time, be); - - //now checking for d and f vals - 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; - } - } - color[u]=BLACK;//done with visiting the node and its neighbors -} - -/// removeRedundant - Remove all back-edges that are dominated by other -/// back-edges in the set. -/// -void CombineBranches::removeRedundant(std::map<BasicBlock *, BasicBlock *> &be){ - std::vector<BasicBlock *> toDelete; - std::map<BasicBlock *, int> seenBB; - - for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(), - ME = be.end(); MI != ME; ++MI){ - - if(seenBB[MI->second]) - continue; - - seenBB[MI->second] = 1; - - std::vector<BasicBlock *> sameTarget; - sameTarget.clear(); - - for(std::map<BasicBlock *, BasicBlock *>::iterator MMI = be.begin(), - MME = be.end(); MMI != MME; ++MMI){ - - if(MMI->first == MI->first) - continue; - - if(MMI->second == MI->second) - sameTarget.push_back(MMI->first); - - } - - //so more than one branch to same target - if(sameTarget.size()){ - - sameTarget.push_back(MI->first); - - BasicBlock *newBB = new BasicBlock("newCommon", MI->first->getParent()); - BranchInst *newBranch = new BranchInst(MI->second, newBB); - - 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); - } - } - } - - 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); - } - } - } -} - -/// runOnFunction - Per function pass for combining branches. -/// -bool CombineBranches::runOnFunction(Function &F){ - if (F.isExternal ()) - return false; - - // Find and remove "redundant" back-edges. - std::map<BasicBlock *, Color> color; - std::map<BasicBlock *, int> d; - std::map<BasicBlock *, BasicBlock *> be; - int time = 0; - getBackEdgesVisit (F.begin (), color, d, time, be); - removeRedundant (be); - - return true; // FIXME: assumes a modification was always made. -} - -FunctionPass *createCombineBranchesPass () { - return new CombineBranches(); -} - -} // End llvm namespace diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp deleted file mode 100644 index bf949437887..00000000000 --- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp +++ /dev/null @@ -1,368 +0,0 @@ -//===-- EdgeCode.cpp - generate LLVM instrumentation code -----------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -//It implements the class EdgeCode: which provides -//support for inserting "appropriate" instrumentation at -//designated points in the graph -// -//It also has methods to insert initialization code in -//top block of cfg -//===----------------------------------------------------------------------===// - -#include "Graph.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Instructions.h" -#include "llvm/Module.h" - -#define INSERT_LOAD_COUNT -#define INSERT_STORE - - -using std::vector; - -namespace llvm { - -static void getTriggerCode(Module *M, BasicBlock *BB, int MethNo, Value *pathNo, - Value *cnt, Instruction *rInst){ - - vector<Value *> tmpVec; - tmpVec.push_back(Constant::getNullValue(Type::LongTy)); - tmpVec.push_back(Constant::getNullValue(Type::LongTy)); - Instruction *Idx = new GetElementPtrInst(cnt, tmpVec, "");//, - BB->getInstList().push_back(Idx); - - const Type *PIntTy = PointerType::get(Type::IntTy); - Function *trigMeth = M->getOrInsertFunction("trigger", Type::VoidTy, - Type::IntTy, Type::IntTy, - PIntTy, PIntTy, (Type *)0); - assert(trigMeth && "trigger method could not be inserted!"); - - vector<Value *> trargs; - - trargs.push_back(ConstantSInt::get(Type::IntTy,MethNo)); - trargs.push_back(pathNo); - trargs.push_back(Idx); - trargs.push_back(rInst); - - Instruction *callInst=new CallInst(trigMeth, trargs, "");//, BB->begin()); - BB->getInstList().push_back(callInst); - //triggerInst = new CallInst(trigMeth, trargs, "");//, InsertPos); -} - - -//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, - vector<Value *> &retVec){ - - //Instruction *InsertPos = BB->getInstList().begin(); - - //now check for cdIn and cdOut - //first put cdOut - if(cdOut!=NULL){ - cdOut->getCode(rInst, countInst, M, BB, retVec); - } - - if(cdIn!=NULL){ - cdIn->getCode(rInst, countInst, M, BB, retVec); - } - - //case: r=k code to be inserted - switch(cond){ - case 1:{ - Value *val=ConstantSInt::get(Type::IntTy,inc); -#ifdef INSERT_STORE - Instruction *stInst=new StoreInst(val, rInst);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - break; - } - - //case: r=0 to be inserted - case 2:{ -#ifdef INSERT_STORE - Instruction *stInst = new StoreInst(ConstantSInt::getNullValue(Type::IntTy), rInst);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - break; - } - - //r+=k - case 3:{ - Instruction *ldInst = new LoadInst(rInst, "ti1");//, InsertPos); - BB->getInstList().push_back(ldInst); - Value *val = ConstantSInt::get(Type::IntTy,inc); - Instruction *addIn = BinaryOperator::create(Instruction::Add, ldInst, val, - "ti2");//, InsertPos); - BB->getInstList().push_back(addIn); -#ifdef INSERT_STORE - Instruction *stInst = new StoreInst(addIn, rInst);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - break; - } - - //count[inc]++ - case 4:{ - vector<Value *> tmpVec; - tmpVec.push_back(Constant::getNullValue(Type::LongTy)); - tmpVec.push_back(ConstantSInt::get(Type::LongTy, inc)); - Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//, - - //Instruction *Idx = new GetElementPtrInst(countInst, - // vector<Value*>(1,ConstantSInt::get(Type::LongTy, inc)), - // "");//, InsertPos); - BB->getInstList().push_back(Idx); - - Instruction *ldInst=new LoadInst(Idx, "ti1");//, InsertPos); - BB->getInstList().push_back(ldInst); - - Value *val = ConstantSInt::get(Type::IntTy, 1); - //Instruction *addIn = - Instruction *newCount = - BinaryOperator::create(Instruction::Add, ldInst, val,"ti2"); - BB->getInstList().push_back(newCount); - - -#ifdef INSERT_STORE - //Instruction *stInst=new StoreInst(addIn, Idx, InsertPos); - Instruction *stInst=new StoreInst(newCount, Idx);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - - Value *trAddIndex = ConstantSInt::get(Type::IntTy,inc); - - retVec.push_back(newCount); - retVec.push_back(trAddIndex); - //insert trigger - //getTriggerCode(M->getParent(), BB, MethNo, - // ConstantSInt::get(Type::IntTy,inc), newCount, triggerInst); - //end trigger code - - assert(inc>=0 && "IT MUST BE POSITIVE NOW"); - break; - } - - //case: count[r+inc]++ - case 5:{ - - //ti1=inc+r - Instruction *ldIndex=new LoadInst(rInst, "ti1");//, InsertPos); - BB->getInstList().push_back(ldIndex); - - Value *val=ConstantSInt::get(Type::IntTy,inc); - Instruction *addIndex=BinaryOperator:: - create(Instruction::Add, ldIndex, val,"ti2");//, InsertPos); - BB->getInstList().push_back(addIndex); - - //now load count[addIndex] - Instruction *castInst=new CastInst(addIndex, - Type::LongTy,"ctin");//, InsertPos); - BB->getInstList().push_back(castInst); - - vector<Value *> tmpVec; - tmpVec.push_back(Constant::getNullValue(Type::LongTy)); - tmpVec.push_back(castInst); - Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//, - // InsertPos); - BB->getInstList().push_back(Idx); - - Instruction *ldInst=new LoadInst(Idx, "ti3");//, InsertPos); - BB->getInstList().push_back(ldInst); - - Value *cons=ConstantSInt::get(Type::IntTy,1); - //count[addIndex]++ - //std::cerr<<"Type ldInst:"<<ldInst->getType()<<"\t cons:"<<cons->getType()<<"\n"; - Instruction *newCount = BinaryOperator::create(Instruction::Add, ldInst, - cons,""); - BB->getInstList().push_back(newCount); - -#ifdef INSERT_STORE - Instruction *stInst = new StoreInst(newCount, Idx);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - - retVec.push_back(newCount); - retVec.push_back(addIndex); - //insert trigger - //getTriggerCode(M->getParent(), BB, MethNo, addIndex, newCount, triggerInst); - //end trigger code - - break; - } - - //case: count[r]+ - case 6:{ - //ti1=inc+r - Instruction *ldIndex=new LoadInst(rInst, "ti1");//, InsertPos); - BB->getInstList().push_back(ldIndex); - - //now load count[addIndex] - Instruction *castInst2=new CastInst(ldIndex, Type::LongTy,"ctin"); - BB->getInstList().push_back(castInst2); - - vector<Value *> tmpVec; - tmpVec.push_back(Constant::getNullValue(Type::LongTy)); - tmpVec.push_back(castInst2); - Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//, - - //Instruction *Idx = new GetElementPtrInst(countInst, - // vector<Value*>(1,castInst2), ""); - - BB->getInstList().push_back(Idx); - - Instruction *ldInst=new LoadInst(Idx, "ti2");//, InsertPos); - BB->getInstList().push_back(ldInst); - - Value *cons=ConstantSInt::get(Type::IntTy,1); - - //count[addIndex]++ - Instruction *newCount = BinaryOperator::create(Instruction::Add, ldInst, - cons,"ti3"); - BB->getInstList().push_back(newCount); - -#ifdef INSERT_STORE - Instruction *stInst = new StoreInst(newCount, Idx);//, InsertPos); - BB->getInstList().push_back(stInst); -#endif - - retVec.push_back(newCount); - retVec.push_back(ldIndex); - break; - } - - } -} - - - -//Insert the initialization code in the top BB -//this includes initializing r, and count -//r is like an accumulator, that -//keeps on adding increments as we traverse along a path -//and at the end of the path, r contains the path -//number of that path -//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){ - //rVar is variable r, - //countVar is count[] - - Value *Int0 = ConstantInt::get(Type::IntTy, 0); - - //now push all instructions in front of the BB - BasicBlock::iterator here=front->begin(); - front->getInstList().insert(here, rVar); - //front->getInstList().insert(here,countVar); - - //Initialize Count[...] with 0 - - //for (int i=0;i<k; i++){ - //Value *GEP2 = new GetElementPtrInst(countVar, - // vector<Value *>(1,ConstantSInt::get(Type::LongTy, i)), - // "", here); - //new StoreInst(Int0, GEP2, here); - //} - - //store uint 0, uint *%R - new StoreInst(Int0, rVar, here); -} - - -//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){ - - BasicBlock* BB1=ed.getFirst()->getElement(); - BasicBlock* BB2=ed.getSecond()->getElement(); - -#ifdef DEBUG_PATH_PROFILES - //debugging info - cerr<<"Edges with codes ######################\n"; - cerr<<BB1->getName()<<"->"<<BB2->getName()<<"\n"; - cerr<<"########################\n"; -#endif - - //We need to insert a BB between BB1 and BB2 - TerminatorInst *TI=BB1->getTerminator(); - BasicBlock *newBB=new BasicBlock("counter", BB1->getParent()); - - //get code for the new BB - vector<Value *> retVec; - - edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB, retVec); - - BranchInst *BI = cast<BranchInst>(TI); - - //Is terminator a branch instruction? - //then we need to change branch destinations to include new BB - - if(BI->isUnconditional()){ - BI->setUnconditionalDest(newBB); - } - else{ - if(BI->getSuccessor(0)==BB2) - BI->setSuccessor(0, newBB); - - if(BI->getSuccessor(1)==BB2) - BI->setSuccessor(1, newBB); - } - - BasicBlock *triggerBB = NULL; - if(retVec.size()>0){ - triggerBB = new BasicBlock("trigger", BB1->getParent()); - getTriggerCode(BB1->getParent()->getParent(), triggerBB, Methno, - retVec[1], countInst, rInst);//retVec[0]); - - //Instruction *castInst = new CastInst(retVec[0], Type::IntTy, ""); - Instruction *etr = new LoadInst(threshold, "threshold"); - - //std::cerr<<"type1: "<<etr->getType()<<" type2: "<<retVec[0]->getType()<<"\n"; - Instruction *cmpInst = new SetCondInst(Instruction::SetLE, etr, - retVec[0], ""); - Instruction *newBI2 = new BranchInst(triggerBB, BB2, cmpInst); - //newBB->getInstList().push_back(castInst); - newBB->getInstList().push_back(etr); - newBB->getInstList().push_back(cmpInst); - newBB->getInstList().push_back(newBI2); - - //triggerBB->getInstList().push_back(triggerInst); - new BranchInst(BB2, 0, 0, triggerBB); - } - else{ - new BranchInst(BB2, 0, 0, newBB); - } - - //now iterate over BB2, and set its Phi nodes right - for(BasicBlock::iterator BB2Inst = BB2->begin(), BBend = BB2->end(); - BB2Inst != BBend; ++BB2Inst){ - - if(PHINode *phiInst=dyn_cast<PHINode>(BB2Inst)){ - int bbIndex=phiInst->getBasicBlockIndex(BB1); - assert(bbIndex>=0); - phiInst->setIncomingBlock(bbIndex, newBB); - - ///check if trigger!=null, then add value corresponding to it too! - if(retVec.size()>0){ - assert(triggerBB && "BasicBlock with trigger should not be null!"); - Value *vl = phiInst->getIncomingValue((unsigned int)bbIndex); - phiInst->addIncoming(vl, triggerBB); - } - } - } -} - -} // End llvm namespace diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp deleted file mode 100644 index c8b1a0dfce0..00000000000 --- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp +++ /dev/null @@ -1,569 +0,0 @@ -//===-- Graph.cpp - Implements Graph class --------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This implements Graph for helping in trace generation This graph gets used by -// "ProfilePaths" class. -// -//===----------------------------------------------------------------------===// - -#include "Graph.h" -#include "llvm/Instructions.h" -#include "llvm/Support/Debug.h" -#include <algorithm> - -using std::vector; - -namespace llvm { - -const graphListElement *findNodeInList(const Graph::nodeList &NL, - Node *N) { - for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE; - ++NI) - if (*NI->element== *N) - return &*NI; - return 0; -} - -graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) { - for(Graph::nodeList::iterator NI = NL.begin(), NE=NL.end(); NI != NE; ++NI) - if (*NI->element== *N) - return &*NI; - return 0; -} - -//graph constructor with root and exit specified -Graph::Graph(std::vector<Node*> n, std::vector<Edge> e, - Node *rt, Node *lt){ - strt=rt; - ext=lt; - for(vector<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x) - //nodes[*x] = list<graphListElement>(); - nodes[*x] = vector<graphListElement>(); - - for(vector<Edge >::iterator x=e.begin(), en=e.end(); x!=en; ++x){ - Edge ee=*x; - int w=ee.getWeight(); - //nodes[ee.getFirst()].push_front(graphListElement(ee.getSecond(),w, ee.getRandId())); - nodes[ee.getFirst()].push_back(graphListElement(ee.getSecond(),w, ee.getRandId())); - } - -} - -//sorting edgelist, called by backEdgeVist ONLY!!! -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() && - 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; - } - } - } - - 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; - *min = *NLI; - *NLI = tmpElmnt; - } - return nl; -} - -//check whether graph has an edge -//having an edge simply means that there is an edge in the graph -//which has same endpoints as the given edge -bool Graph::hasEdge(Edge ed){ - if(ed.isNull()) - return false; - - nodeList &nli= nodes[ed.getFirst()]; //getNodeList(ed.getFirst()); - Node *nd2=ed.getSecond(); - - return (findNodeInList(nli,nd2)!=NULL); - -} - - -//check whether graph has an edge, with a given wt -//having an edge simply means that there is an edge in the graph -//which has same endpoints as the given edge -//This function checks, moreover, that the wt of edge matches too -bool Graph::hasEdgeAndWt(Edge ed){ - if(ed.isNull()) - return false; - - Node *nd2=ed.getSecond(); - nodeList &nli = nodes[ed.getFirst()];//getNodeList(ed.getFirst()); - - for(nodeList::iterator NI=nli.begin(), NE=nli.end(); NI!=NE; ++NI) - if(*NI->element == *nd2 && ed.getWeight()==NI->weight) - return true; - - return false; -} - -//add a node -void Graph::addNode(Node *nd){ - vector<Node *> lt=getAllNodes(); - - for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){ - if(**LI==*nd) - return; - } - //chng - nodes[nd] =vector<graphListElement>(); //list<graphListElement>(); -} - -//add an edge -//this adds an edge ONLY when -//the edge to be added does not already exist -//we "equate" two edges here only with their -//end points -void Graph::addEdge(Edge ed, int w){ - nodeList &ndList = nodes[ed.getFirst()]; - Node *nd2=ed.getSecond(); - - if(findNodeInList(nodes[ed.getFirst()], nd2)) - return; - - //ndList.push_front(graphListElement(nd2,w, ed.getRandId())); - ndList.push_back(graphListElement(nd2,w, ed.getRandId()));//chng - //sortNodeList(ed.getFirst(), ndList); - - //sort(ndList.begin(), ndList.end(), NodeListSort()); -} - -//add an edge EVEN IF such an edge already exists -//this may make a multi-graph -//which does happen when we add dummy edges -//to the graph, for compensating for back-edges -void Graph::addEdgeForce(Edge ed){ - //nodes[ed.getFirst()].push_front(graphListElement(ed.getSecond(), - //ed.getWeight(), ed.getRandId())); - nodes[ed.getFirst()].push_back - (graphListElement(ed.getSecond(), ed.getWeight(), ed.getRandId())); - - //sortNodeList(ed.getFirst(), nodes[ed.getFirst()]); - //sort(nodes[ed.getFirst()].begin(), nodes[ed.getFirst()].end(), NodeListSort()); -} - -//remove an edge -//Note that it removes just one edge, -//the first edge that is encountered -void Graph::removeEdge(Edge ed){ - nodeList &ndList = nodes[ed.getFirst()]; - Node &nd2 = *ed.getSecond(); - - for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) { - if(*NI->element == nd2) { - ndList.erase(NI); - break; - } - } -} - -//remove an edge with a given wt -//Note that it removes just one edge, -//the first edge that is encountered -void Graph::removeEdgeWithWt(Edge ed){ - nodeList &ndList = nodes[ed.getFirst()]; - Node &nd2 = *ed.getSecond(); - - for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) { - if(*NI->element == nd2 && NI->weight==ed.getWeight()) { - ndList.erase(NI); - break; - } - } -} - -//set the weight of an edge -void Graph::setWeight(Edge ed){ - graphListElement *El = findNodeInList(nodes[ed.getFirst()], ed.getSecond()); - if (El) - El->weight=ed.getWeight(); -} - - - -//get the list of successor nodes -vector<Node *> Graph::getSuccNodes(Node *nd){ - nodeMapTy::const_iterator nli = nodes.find(nd); - assert(nli != nodes.end() && "Node must be in nodes map"); - const nodeList &nl = getNodeList(nd);//getSortedNodeList(nd); - - vector<Node *> lt; - for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI) - lt.push_back(NI->element); - - return lt; -} - -//get the number of outgoing edges -int Graph::getNumberOfOutgoingEdges(Node *nd) const { - nodeMapTy::const_iterator nli = nodes.find(nd); - assert(nli != nodes.end() && "Node must be in nodes map"); - const nodeList &nl = nli->second; - - int count=0; - for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI) - count++; - - return count; -} - -//get the list of predecessor nodes -vector<Node *> Graph::getPredNodes(Node *nd){ - vector<Node *> lt; - for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){ - Node *lnode=EI->first; - const nodeList &nl = getNodeList(lnode); - - const graphListElement *N = findNodeInList(nl, nd); - if (N) lt.push_back(lnode); - } - return lt; -} - -//get the number of predecessor nodes -int Graph::getNumberOfIncomingEdges(Node *nd){ - int count=0; - for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){ - Node *lnode=EI->first; - const nodeList &nl = getNodeList(lnode); - for(Graph::nodeList::const_iterator NI = nl.begin(), NE=nl.end(); NI != NE; - ++NI) - if (*NI->element== *nd) - count++; - } - return count; -} - -//get the list of all the vertices in graph -vector<Node *> Graph::getAllNodes() const{ - vector<Node *> lt; - for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x) - lt.push_back(x->first); - - return lt; -} - -//get the list of all the vertices in graph -vector<Node *> Graph::getAllNodes(){ - vector<Node *> lt; - for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x) - lt.push_back(x->first); - - return lt; -} - -//class to compare two nodes in graph -//based on their wt: this is used in -//finding the maximal spanning tree -struct compare_nodes { - bool operator()(Node *n1, Node *n2){ - return n1->getWeight() < n2->getWeight(); - } -}; - - -static void printNode(Node *nd){ - std::cerr<<"Node:"<<nd->getElement()->getName()<<"\n"; -} - -//Get the Maximal spanning tree (also a graph) -//of the graph -Graph* Graph::getMaxSpanningTree(){ - //assume connected graph - - Graph *st=new Graph();//max spanning tree, undirected edges - int inf=9999999;//largest key - vector<Node *> lt = getAllNodes(); - - //initially put all vertices in vector vt - //assign wt(root)=0 - //wt(others)=infinity - // - //now: - //pull out u: a vertex frm vt of min wt - //for all vertices w in vt, - //if wt(w) greater than - //the wt(u->w), then assign - //wt(w) to be wt(u->w). - // - //make parent(u)=w in the spanning tree - //keep pulling out vertices from vt till it is empty - - vector<Node *> vt; - - std::map<Node*, Node* > parent; - std::map<Node*, int > ed_weight; - - //initialize: wt(root)=0, wt(others)=infinity - //parent(root)=NULL, parent(others) not defined (but not null) - for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){ - Node *thisNode=*LI; - if(*thisNode == *getRoot()){ - thisNode->setWeight(0); - parent[thisNode]=NULL; - ed_weight[thisNode]=0; - } - else{ - thisNode->setWeight(inf); - } - st->addNode(thisNode);//add all nodes to spanning tree - //we later need to assign edges in the tree - vt.push_back(thisNode); //pushed all nodes in vt - } - - //keep pulling out vertex of min wt from vt - while(!vt.empty()){ - Node *u=*(std::min_element(vt.begin(), vt.end(), compare_nodes())); - DEBUG(std::cerr<<"popped wt"<<(u)->getWeight()<<"\n"; - printNode(u)); - - if(parent[u]!=NULL){ //so not root - Edge edge(parent[u],u, ed_weight[u]); //assign edge in spanning tree - st->addEdge(edge,ed_weight[u]); - - DEBUG(std::cerr<<"added:\n"; - printEdge(edge)); - } - - //vt.erase(u); - - //remove u frm vt - for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){ - if(**VI==*u){ - vt.erase(VI); - break; - } - } - - //assign wt(v) to all adjacent vertices v of u - //only if v is in vt - Graph::nodeList &nl = getNodeList(u); - for(nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){ - Node *v=NI->element; - int weight=-NI->weight; - //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; - } - } - 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); - - DEBUG(std::cerr<<v->getWeight()<<":Set weight------\n"; - printGraph(); - printEdge(Edge(u,v,weight))); - } - } - } - return st; -} - -//print the graph (for debugging) -void Graph::printGraph(){ - vector<Node *> lt=getAllNodes(); - std::cerr<<"Graph---------------------\n"; - for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){ - std::cerr<<((*LI)->getElement())->getName()<<"->"; - 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<<")"; - } - std::cerr<<"--------\n"; - } -} - - -//get a list of nodes in the graph -//in r-topological sorted order -//note that we assumed graph to be connected -vector<Node *> Graph::reverseTopologicalSort(){ - vector <Node *> toReturn; - vector<Node *> lt=getAllNodes(); - for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){ - if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK) - DFS_Visit(*LI, toReturn); - } - - return toReturn; -} - -//a private method for doing DFS traversal of graph -//this is used in determining the reverse topological sort -//of the graph -void Graph::DFS_Visit(Node *nd, vector<Node *> &toReturn){ - nd->setWeight(GREY); - vector<Node *> lt=getSuccNodes(nd); - for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){ - if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK) - DFS_Visit(*LI, toReturn); - } - toReturn.push_back(nd); -} - -//Ordinarily, the graph is directional -//this converts the graph into an -//undirectional graph -//This is done by adding an edge -//v->u for all existing edges u->v -void Graph::makeUnDirectional(){ - vector<Node* > allNodes=getAllNodes(); - for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; - ++NI) { - nodeList &nl = getNodeList(*NI); - 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"; - printEdge(ed)); - addEdgeForce(ed); - } - } - } -} - -//reverse the sign of weights on edges -//this way, max-spanning tree could be obtained -//using min-spanning tree, and vice versa -void Graph::reverseWts(){ - vector<Node *> allNodes=getAllNodes(); - for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; - ++NI) { - nodeList &node_list = getNodeList(*NI); - for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end(); - NLI!=NLE; ++NLI) - NLI->weight=-NLI->weight; - } -} - - -//getting the backedges in a graph -//Its a variation of DFS to get the backedges in the graph -//We get back edges by associating a time -//and a color with each vertex. -//The time of a vertex is the time when it was first visited -//The color of a vertex is initially WHITE, -//Changes to GREY when it is first visited, -//and changes to BLACK when ALL its neighbors -//have been visited -//So we have a back edge when we meet a successor of -//a node with smaller time, and GREY color -void Graph::getBackEdges(vector<Edge > &be, std::map<Node *, int> &d){ - std::map<Node *, Color > color; - int time=0; - - getBackEdgesVisit(getRoot(), be, color, d, time); -} - -//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) { - 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){ - Node *v=vl->element; - if(color[v]!=GREY && color[v]!=BLACK){ - getBackEdgesVisit(v, be, color, d, time); - } - - //now checking for d and f vals - 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 - } - } - } - color[u]=BLACK;//done with visiting the node and its neighbors -} - -} // End llvm namespace diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/Graph.h b/llvm/lib/Transforms/Instrumentation/ProfilePaths/Graph.h deleted file mode 100644 index 9782ab49172..00000000000 --- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/Graph.h +++ /dev/null @@ -1,480 +0,0 @@ -//===-- Graph.h -------------------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Header file for Graph: This Graph is used by PathProfiles class, and is used -// for detecting proper points in cfg for code insertion -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_GRAPH_H -#define LLVM_GRAPH_H - -#include "llvm/BasicBlock.h" -#include <map> -#include <cstdlib> - -namespace llvm { - -class Module; -class Function; - -//Class Node -//It forms the vertex for the graph -class Node{ -public: - BasicBlock* element; - int weight; -public: - inline Node(BasicBlock* x) { element=x; weight=0; } - inline BasicBlock* &getElement() { return element; } - inline BasicBlock* const &getElement() const { return element; } - inline int getWeight() { return weight; } - inline void setElement(BasicBlock* e) { element=e; } - inline void setWeight(int w) { weight=w;} - inline bool operator<(Node& nd) const { return element<nd.element; } - inline bool operator==(Node& nd) const { return element==nd.element; } -}; - -//Class Edge -//Denotes an edge in the graph -class Edge{ -private: - Node *first; - Node *second; - bool isnull; - int weight; - double randId; -public: - inline Edge(Node *f,Node *s, int wt=0){ - first=f; - second=s; - weight=wt; - randId=rand(); - isnull=false; - } - - inline Edge(Node *f,Node *s, int wt, double rd){ - first=f; - second=s; - weight=wt; - randId=rd; - isnull=false; - } - - inline Edge() { isnull = true; } - inline double getRandId(){ return randId; } - inline Node* getFirst() { assert(!isNull()); return first; } - inline Node* const getFirst() const { assert(!isNull()); return first; } - inline Node* getSecond() { assert(!isNull()); return second; } - inline Node* const getSecond() const { assert(!isNull()); return second; } - - inline int getWeight() { assert(!isNull()); return weight; } - inline void setWeight(int n) { assert(!isNull()); weight=n; } - - inline void setFirst(Node *&f) { assert(!isNull()); first=f; } - inline void setSecond(Node *&s) { assert(!isNull()); second=s; } - - - inline bool isNull() const { return isnull;} - - inline bool operator<(const Edge& ed) const{ - // Can't be the same if one is null and the other isn't - if (isNull() != ed.isNull()) - return true; - - return (*first<*(ed.getFirst()))|| - (*first==*(ed.getFirst()) && *second<*(ed.getSecond())); - } - - inline bool operator==(const Edge& ed) const{ - return !(*this<ed) && !(ed<*this); - } - - inline bool operator!=(const Edge& ed) const{return !(*this==ed);} -}; - - -//graphListElement -//This forms the "adjacency list element" of a -//vertex adjacency list in graph -struct graphListElement{ - Node *element; - int weight; - double randId; - inline graphListElement(Node *n, int w, double rand){ - element=n; - weight=w; - randId=rand; - } -}; - -} // End llvm namespace - - -namespace std { - -using namespace llvm; - - template<> - struct less<Node *> : public binary_function<Node *, Node *,bool> { - bool operator()(Node *n1, Node *n2) const { - return n1->getElement() < n2->getElement(); - } - }; - - template<> - struct less<Edge> : public binary_function<Edge,Edge,bool> { - bool operator()(Edge e1, Edge e2) const { - assert(!e1.isNull() && !e2.isNull()); - - Node *x1=e1.getFirst(); - Node *x2=e1.getSecond(); - Node *y1=e2.getFirst(); - Node *y2=e2.getSecond(); - return (*x1<*y1 ||(*x1==*y1 && *x2<*y2)); - } - }; -} - -namespace llvm { - -struct BBSort{ - bool operator()(BasicBlock *BB1, BasicBlock *BB2) const{ - std::string name1=BB1->getName(); - std::string name2=BB2->getName(); - return name1<name2; - } -}; - -struct NodeListSort{ - bool operator()(graphListElement BB1, graphListElement BB2) const{ - std::string name1=BB1.element->getElement()->getName(); - std::string name2=BB2.element->getElement()->getName(); - return name1<name2; - } -}; - -struct EdgeCompare2{ - bool operator()(Edge e1, Edge e2) const { - assert(!e1.isNull() && !e2.isNull()); - Node *x1=e1.getFirst(); - Node *x2=e1.getSecond(); - Node *y1=e2.getFirst(); - Node *y2=e2.getSecond(); - int w1=e1.getWeight(); - int w2=e2.getWeight(); - 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 -//during DFS -enum Color{ - WHITE, - GREY, - BLACK -}; - - -//For path profiling, -//We assume that the graph is connected (which is true for -//any method CFG) -//We also assume that the graph has single entry and single exit -//(For this, we make a pass over the graph that ensures this) -//The graph is a construction over any existing graph of BBs -//Its a construction "over" existing cfg: with -//additional features like edges and weights to edges - -//graph uses adjacency list representation -class Graph{ -public: - //typedef std::map<Node*, std::list<graphListElement> > nodeMapTy; - typedef std::map<Node*, std::vector<graphListElement> > nodeMapTy;//chng -private: - //the adjacency list of a vertex or node - nodeMapTy nodes; - - //the start or root node - Node *strt; - - //the exit node - Node *ext; - - //a private method for doing DFS traversal of graph - //this is used in determining the reverse topological sort - //of the graph - void DFS_Visit(Node *nd, std::vector<Node *> &toReturn); - - //Its a variation of DFS to get the backedges in the graph - //We get back edges by associating a time - //and a color with each vertex. - //The time of a vertex is the time when it was first visited - //The color of a vertex is initially WHITE, - //Changes to GREY when it is first visited, - //and changes to BLACK when ALL its neighbors - //have been visited - //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); - -public: - typedef nodeMapTy::iterator elementIterator; - typedef nodeMapTy::const_iterator constElementIterator; - typedef std::vector<graphListElement > nodeList;//chng - //typedef std::vector<graphListElement > nodeList; - - //graph constructors - - //empty constructor: then add edges and nodes later on - Graph() {} - - //constructor with root and exit node specified - Graph(std::vector<Node*> n, - std::vector<Edge> e, Node *rt, Node *lt); - - //add a node - void addNode(Node *nd); - - //add an edge - //this adds an edge ONLY when - //the edge to be added doesn not already exist - //we "equate" two edges here only with their - //end points - void addEdge(Edge ed, int w); - - //add an edge EVEN IF such an edge already exists - //this may make a multi-graph - //which does happen when we add dummy edges - //to the graph, for compensating for back-edges - void addEdgeForce(Edge ed); - - //set the weight of an edge - void setWeight(Edge ed); - - //remove an edge - //Note that it removes just one edge, - //the first edge that is encountered - void removeEdge(Edge ed); - - //remove edge with given wt - void removeEdgeWithWt(Edge ed); - - //check whether graph has an edge - //having an edge simply means that there is an edge in the graph - //which has same endpoints as the given edge - //it may possibly have different weight though - bool hasEdge(Edge ed); - - //check whether graph has an edge, with a given wt - bool hasEdgeAndWt(Edge ed); - - //get the list of successor nodes - std::vector<Node *> getSuccNodes(Node *nd); - - //get the number of outgoing edges - int getNumberOfOutgoingEdges(Node *nd) const; - - //get the list of predecessor nodes - std::vector<Node *> getPredNodes(Node *nd); - - - //to get the no of incoming edges - int getNumberOfIncomingEdges(Node *nd); - - //get the list of all the vertices in graph - std::vector<Node *> getAllNodes() const; - std::vector<Node *> getAllNodes(); - - //get a list of nodes in the graph - //in r-topological sorted order - //note that we assumed graph to be connected - std::vector<Node *> reverseTopologicalSort(); - - //reverse the sign of weights on edges - //this way, max-spanning tree could be obtained - //usin min-spanning tree, and vice versa - void reverseWts(); - - //Ordinarily, the graph is directional - //this converts the graph into an - //undirectional graph - //This is done by adding an edge - //v->u for all existing edges u->v - void makeUnDirectional(); - - //print graph: for debugging - void printGraph(); - - //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, std::vector<Edge> &be); - - //Get the Maximal spanning tree (also a graph) - //of the graph - Graph* getMaxSpanningTree(); - - //get the nodeList adjacent to a node - //a nodeList element contains a node, and the weight - //corresponding to the edge for that element - inline nodeList &getNodeList(Node *nd) { - elementIterator nli = nodes.find(nd); - assert(nli != nodes.end() && "Node must be in nodes map"); - return nodes[nd];//sortNodeList(nd, nli->second); - } - - 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], be); - } - - //get the root of the graph - inline Node *getRoot() {return strt; } - inline Node * const getRoot() const {return strt; } - - //get exit: we assumed there IS a unique exit :) - inline Node *getExit() {return ext; } - inline Node * const getExit() const {return ext; } - //Check if a given node is the root - inline bool isRoot(Node *n) const {return (*n==*strt); } - - //check if a given node is leaf node - //here we hv only 1 leaf: which is the exit node - inline bool isLeaf(Node *n) const {return (*n==*ext); } -}; - -//This class is used to generate -//"appropriate" code to be inserted -//along an edge -//The code to be inserted can be of six different types -//as given below -//1: r=k (where k is some constant) -//2: r=0 -//3: r+=k -//4: count[k]++ -//5: Count[r+k]++ -//6: Count[r]++ -class getEdgeCode{ - private: - //cond implies which - //"kind" of code is to be inserted - //(from 1-6 above) - int cond; - //inc is the increment: eg k, or 0 - int inc; - - //A backedge must carry the code - //of both incoming "dummy" edge - //and outgoing "dummy" edge - //If a->b is a backedge - //then incoming dummy edge is root->b - //and outgoing dummy edge is a->exit - - //incoming dummy edge, if any - getEdgeCode *cdIn; - - //outgoing dummy edge, if any - getEdgeCode *cdOut; - -public: - getEdgeCode(){ - cdIn=NULL; - cdOut=NULL; - inc=0; - cond=0; - } - - //set condition: 1-6 - inline void setCond(int n) {cond=n;} - - //get the condition - inline int getCond() { return cond;} - - //set increment - inline void setInc(int n) {inc=n;} - - //get increment - inline int getInc() {return inc;} - - //set CdIn (only used for backedges) - inline void setCdIn(getEdgeCode *gd){ cdIn=gd;} - - //set CdOut (only used for backedges) - inline void setCdOut(getEdgeCode *gd){ cdOut=gd;} - - //get the code to be inserted on the edge - //This is determined from cond (1-6) - void getCode(Instruction *a, Value *b, Function *M, BasicBlock *BB, - std::vector<Value *> &retVec); -}; - - -//auxillary functions on graph - -//print a given edge in the form BB1Label->BB2Label -void printEdge(Edge ed); - -//Do graph processing: to determine minimal edge increments, -//appropriate code insertions etc and insert the code at -//appropriate locations -void processGraph(Graph &g, Instruction *rInst, Value *countInst, std::vector<Edge> &be, std::vector<Edge> &stDummy, std::vector<Edge> &exDummy, int n, int MethNo, Value *threshold); - -//print the graph (for debugging) -void printGraph(Graph &g); - - -//void printGraph(const Graph g); -//insert a basic block with appropriate code -//along a given edge -void insertBB(Edge ed, getEdgeCode *edgeCode, Instruction *rInst, Value *countInst, int n, int Methno, Value *threshold); - -//Insert the initialization code in the top BB -//this includes initializing r, and count -//r is like an accumulator, that -//keeps on adding increments as we traverse along a path -//and at the end of the path, r contains the path -//number of that path -//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); - -//Add dummy edges corresponding to the back edges -//If a->b is a backedge -//then incoming dummy edge is root->b -//and outgoing dummy edge is a->exit -void addDummyEdges(std::vector<Edge> &stDummy, std::vector<Edge> &exDummy, Graph &g, std::vector<Edge> &be); - -//Assign a value to all the edges in 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, - std::vector<Edge> &be); - -void getBBtrace(std::vector<BasicBlock *> &vBB, int pathNo, Function *M); - -} // End llvm namespace - -#endif diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp deleted file mode 100644 index 4ca1c5b92fe..00000000000 --- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp +++ /dev/null @@ -1,679 +0,0 @@ -//===- GraphAuxiliary.cpp - Auxiliary functions on graph ------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// auxiliary function associated with graph: they all operate on graph, and help -// in inserting instrumentation for trace generation -// -//===----------------------------------------------------------------------===// - -#include "llvm/Pass.h" -#include "llvm/Module.h" -#include "llvm/Instructions.h" -#include "llvm/Support/Debug.h" -#include <algorithm> -#include "Graph.h" - -//using std::list; -using std::map; -using std::vector; -using std::cerr; - -namespace llvm { - -//check if 2 edges are equal (same endpoints and same weight) -static bool edgesEqual(Edge ed1, Edge ed2){ - return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight()); -} - -//Get the vector of edges that are to be instrumented in the graph -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 - 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, NLI->randId); - if(!(st.hasEdgeAndWt(f)))//addnl - chords.push_back(f); - } - } -} - -//Given a tree t, and a "directed graph" g -//replace the edges in the tree t with edges that exist in graph -//The tree is formed from "undirectional" copy of graph -//So whatever edges the tree has, the undirectional graph -//would have too. This function corrects some of the directions in -//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){ - 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){ - 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 - } - } -} - -//Assign a value to all the edges in 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, 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(); - RI!=RE; ++RI){ - if(g.isLeaf(*RI)) - NumPaths[*RI]=1; - else{ - NumPaths[*RI]=0; - - // 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++){ - 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]; - NumPaths[*RI]+=NumPaths[GLI->element]; - } - } - } - return NumPaths[g.getRoot()]; -} - -//This is a helper function to get the edge increments -//This is used in conjunction with inc_DFS -//to get the edge increments -//Edge increment implies assigning a value to all the edges in 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 -//inc_Dir tells whether 2 edges are in same, or in different directions -//if same direction, return 1, else -1 -static int inc_Dir(Edge e, Edge f){ - if(e.isNull()) - return 1; - - //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())); - - if(*(e.getFirst())==*(f.getSecond()) || - *(e.getSecond())==*(f.getFirst())) - return 1; - - 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, EdgeCompare2>& Increment, - int events, Node *v, Edge e){ - - vector<Node *> allNodes=t.getAllNodes(); - - 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, 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); - } - } - } - - 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, 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); - } - } - } - - 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, NLI->randId); - if(!(t.hasEdgeAndWt(f)) && (*v==*(f.getSecond()) || - *v==*(f.getFirst()))){ - int dir_count=inc_Dir(e,f); - Increment[f]+=dir_count*events; - } - } - } -} - -//Now we select a subset of all edges -//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, EdgeCompare2> getEdgeIncrements(Graph& g, Graph& t, - vector<Edge> &be){ - //get all edges in g-t - 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.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); - if(!(t.hasEdgeAndWt(ed))){ - Increment[ed]=0;; - } - } - } - - Edge *ed=new Edge(); - inc_DFS(g,t,Increment, 0, g.getRoot(), *ed); - - for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE; - ++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); - if(!(t.hasEdgeAndWt(ed))){ - int wt=ed.getWeight(); - Increment[ed]+=wt; - } - } - } - - 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 *, EdgeCompare2> &instr, - vector<Edge > &chords, - map<Edge,int, EdgeCompare2> &edIncrements){ - - //Register initialization code - vector<Node *> ws; - ws.push_back(g.getRoot()); - while(ws.size()>0){ - Node *v=ws.back(); - ws.pop_back(); - //for each edge v->w - Graph::nodeList succs=g.getNodeList(v); - - for(Graph::nodeList::iterator nl=succs.begin(), ne=succs.end(); - 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; - } - } - - if(hasEdge){//so its a chord edge - getEdgeCode *edCd=new getEdgeCode(); - edCd->setCond(1); - edCd->setInc(edIncrements[ed]); - instr[ed]=edCd; - } - else if(g.getNumberOfIncomingEdges(w)==1){ - ws.push_back(w); - } - else{ - getEdgeCode *edCd=new getEdgeCode(); - edCd->setCond(2); - edCd->setInc(0); - instr[ed]=edCd; - } - } - } - - /////Memory increment code - ws.push_back(g.getExit()); - - while(!ws.empty()) { - Node *w=ws.back(); - ws.pop_back(); - - - /////// - //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); - //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; - } - } - } - } - } - ///// Register increment code - for(vector<Edge>::iterator CI=chords.begin(), CE=chords.end(); CI!=CE; ++CI){ - getEdgeCode *edCd=new getEdgeCode(); - if(instr[*CI]==NULL){ - edCd->setCond(3); - edCd->setInc(edIncrements[*CI]); - instr[*CI]=edCd; - } - } -} - -//Add dummy edges corresponding to the back edges -//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){ - for(vector<Edge >::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){ - Edge ed=*VI; - Node *first=ed.getFirst(); - Node *second=ed.getSecond(); - g.removeEdge(ed); - - if(!(*second==*(g.getRoot()))){ - 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(), ed.getWeight(), ed.getRandId()); - exDummy.push_back(*ex); - g.addEdgeForce(*ex); - } - } -} - -//print a given edge in the form BB1Label->BB2Label -void printEdge(Edge ed){ - cerr<<((ed.getFirst())->getElement()) - ->getName()<<"->"<<((ed.getSecond()) - ->getElement())->getName()<< - ":"<<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(vector<Edge> &stDummy, - vector<Edge> &exDummy, - vector<Edge> &be, - map<Edge, getEdgeCode *, EdgeCompare2> &insertions, - 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){ - 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()){ - - 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); - g.removeEdgeWithWt(*vmi); - } - - for(map<Edge,getEdgeCode *, EdgeCompare2>::iterator MI=temp.begin(), - ME=temp.end(); MI!=ME; ++MI){ - insertions[MI->first]=MI->second; - } - -#ifdef DEBUG_PATH_PROFILES - cerr<<"size of deletions: "<<toErase.size()<<"\n"; - cerr<<"SIZE OF INSERTIONS AFTER DEL "<<insertions.size()<<"\n"; -#endif - -} - -//Do graph processing: to determine minimal edge increments, -//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, - Value *threshold){ - - //Given a graph: with exit->root edge, do the following in seq: - //1. get back edges - //2. insert dummy edges and remove back edges - //3. get edge assignments - //4. Get Max spanning tree of graph: - // -Make graph g2=g undirectional - // -Get Max spanning tree t - // -Make t undirectional - // -remove edges from t not in graph g - //5. Get edge increments - //6. Get code insertions - //7. move code on dummy edges over to the back edges - - - //This is used as maximum "weight" for - //priority queue - //This would hold all - //right as long as number of paths in the graph - //is less than this - const int Infinity=99999999; - - - //step 1-3 are already done on the graph when this function is called - DEBUG(printGraph(g)); - - //step 4: Get Max spanning tree of graph - - //now insert exit to root edge - //if its there earlier, remove it! - //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); - Graph g2=g; - - //make g2 undirectional: this gives a better - //maximal spanning tree - g2.makeUnDirectional(); - DEBUG(printGraph(g2)); - - Graph *t=g2.getMaxSpanningTree(); -#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 - //actually for finding min spanning tree - //so get back the original weights - t->reverseWts(); - - //Ordinarily, the graph is directional - //lets converts the graph into an - //undirectional graph - //This is done by adding an edge - //v->u for all existing edges u->v - t->makeUnDirectional(); - - //Given a tree t, and a "directed graph" g - //replace the edges in the tree t with edges that exist in graph - //The tree is formed from "undirectional" copy of graph - //So whatever edges the tree has, the undirectional graph - //would have too. This function corrects some of the directions in - //the tree so that now, all edge directions in the tree match - //the edge directions of corresponding edges in the directed graph - removeTreeEdges(g, *t); - -#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 - //since infinite weight is kinda confusing - g.removeEdge(ed); - Edge edNew(g.getExit(), g.getRoot(),0); - g.addEdge(edNew,0); - if(t->hasEdge(ed)){ - t->removeEdge(ed); - t->addEdge(edNew,0); - } - - DEBUG(printGraph(g); - printGraph(*t)); - - //step 5: Get edge increments - - //Now we select a subset of all edges - //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, EdgeCompare2> increment=getEdgeIncrements(g,*t, be); -#ifdef DEBUG_PATH_PROFILES - //print edge increments for debugging - 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 - - - //step 6: Get code insertions - - //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 - vector<Edge> chords; - getChords(chords, g, *t); - - - 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 *, 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"; - } - 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, g); - -#ifdef DEBUG_PATH_PROFILES - //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){ - 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 *,EdgeCompare2>::iterator MI=codeInsertions.begin(), - ME=codeInsertions.end(); MI!=ME; ++MI){ - Edge ed=MI->first; - 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"; - 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<<"," - <<NI->randId<<")"; - } - cerr<<"\n"; - } - cerr<<"--------------------Graph\n"; -} - -} // End llvm namespace diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/InstLoops.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/InstLoops.cpp deleted file mode 100644 index 020388f2b67..00000000000 --- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/InstLoops.cpp +++ /dev/null @@ -1,185 +0,0 @@ -//===-- InstLoops.cpp -----------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This is the first-level instrumentation pass for the Reoptimizer. It -// instrument the back-edges of loops by inserting a basic block -// containing a call to llvm_first_trigger (the first-level trigger function), -// and inserts an initialization call to the main() function. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/Dominators.h" -#include "llvm/Support/CFG.h" -#include "llvm/Instructions.h" -#include "llvm/Module.h" -#include "llvm/Pass.h" -#include "llvm/Type.h" -#include "llvm/Support/Debug.h" -#include "llvm/Transforms/Instrumentation.h" -#include "../ProfilingUtils.h" - -namespace llvm { - -//this is used to color vertices -//during DFS - -enum Color{ - WHITE, - GREY, - BLACK -}; - -namespace { - typedef std::map<BasicBlock *, BasicBlock *> BBMap; - struct InstLoops : public FunctionPass { - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<DominatorSet>(); - } - private: - Function *inCountMth; - DominatorSet *DS; - void getBackEdgesVisit(BasicBlock *u, - std::map<BasicBlock *, Color > &color, - std::map<BasicBlock *, int > &d, - int &time, BBMap &be); - void removeRedundant(BBMap &be); - void findAndInstrumentBackEdges(Function &F); - public: - bool doInitialization(Module &M); - bool runOnFunction(Function &F); - }; - - RegisterOpt<InstLoops> X("instloops", "Instrument backedges for profiling"); -} - -//helper function to get back edges: it is called by -//the "getBackEdges" function below -void InstLoops::getBackEdgesVisit(BasicBlock *u, - std::map<BasicBlock *, Color > &color, - std::map<BasicBlock *, int > &d, - int &time, BBMap &be) { - color[u]=GREY; - time++; - d[u]=time; - - for(succ_iterator vl = succ_begin(u), ve = succ_end(u); vl != ve; ++vl){ - BasicBlock *BB = *vl; - - if(color[BB]!=GREY && color[BB]!=BLACK){ - getBackEdgesVisit(BB, color, d, time, be); - } - - //now checking for d and f vals - 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; - } - } - } - color[u]=BLACK;//done with visiting the node and its neighbors -} - -//look at all BEs, and remove all BEs that are dominated by other BE's in the -//set -void InstLoops::removeRedundant(BBMap &be) { - std::vector<BasicBlock *> toDelete; - for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(), - 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); - // Remove all the back-edges we found from be. - for(std::vector<BasicBlock *>::iterator VI = toDelete.begin(), - VE = toDelete.end(); VI != VE; ++VI) - be.erase(*VI); -} - -//getting the backedges in a graph -//Its a variation of DFS to get the backedges in the graph -//We get back edges by associating a time -//and a color with each vertex. -//The time of a vertex is the time when it was first visited -//The color of a vertex is initially WHITE, -//Changes to GREY when it is first visited, -//and changes to BLACK when ALL its neighbors -//have been visited -//So we have a back edge when we meet a successor of -//a node with smaller time, and GREY color -void InstLoops::findAndInstrumentBackEdges(Function &F){ - std::map<BasicBlock *, Color > color; - std::map<BasicBlock *, int> d; - BBMap be; - int time=0; - getBackEdgesVisit(F.begin(), color, d, time, be); - - removeRedundant(be); - - for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(), - ME = be.end(); MI != ME; ++MI){ - BasicBlock *u = MI->first; - BasicBlock *BB = MI->second; - // We have a back-edge from BB --> u. - DEBUG (std::cerr << "Instrumenting back-edge from " << BB->getName () - << "-->" << u->getName () << "\n"); - // Split the back-edge, inserting a new basic block on it, and modify the - // source BB's terminator accordingly. - BasicBlock *newBB = new BasicBlock("backEdgeInst", u->getParent()); - BranchInst *ti = cast<BranchInst>(u->getTerminator()); - unsigned char index = ((ti->getSuccessor(0) == BB) ? 0 : 1); - - assert(ti->getNumSuccessors() > index && "Not enough successors!"); - ti->setSuccessor(index, newBB); - - BasicBlock::InstListType < = newBB->getInstList(); - lt.push_back(new CallInst(inCountMth)); - new BranchInst(BB, newBB); - - // Now, set the sources of Phi nodes corresponding to the back-edge - // in BB to come from the instrumentation block instead. - for(BasicBlock::iterator BB2Inst = BB->begin(), BBend = BB->end(); - BB2Inst != BBend; ++BB2Inst) { - if (PHINode *phiInst = dyn_cast<PHINode>(BB2Inst)) { - int bbIndex = phiInst->getBasicBlockIndex(u); - if (bbIndex>=0) - phiInst->setIncomingBlock(bbIndex, newBB); - } - } - } -} - -bool InstLoops::doInitialization (Module &M) { - inCountMth = M.getOrInsertFunction("llvm_first_trigger", Type::VoidTy, - (Type *)0); - return true; // Module was modified. -} - -/// runOnFunction - Entry point for FunctionPass that inserts calls to -/// trigger function. -/// -bool InstLoops::runOnFunction(Function &F){ - if (F.isExternal ()) - return false; - - DS = &getAnalysis<DominatorSet> (); - - // Add a call to reoptimizerInitialize() to beginning of function named main. - if (F.getName() == "main") - InsertProfilingInitCall (&F, "reoptimizerInitialize"); - - findAndInstrumentBackEdges(F); - return true; // Function was modified. -} - -FunctionPass *createLoopInstrumentationPass () { - return new InstLoops(); -} - -} // End llvm namespace diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/Makefile b/llvm/lib/Transforms/Instrumentation/ProfilePaths/Makefile deleted file mode 100644 index 5a7477caf32..00000000000 --- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/Makefile +++ /dev/null @@ -1,13 +0,0 @@ -##===- lib/Transforms/Instrumentation/ProfilePaths/Makefile -*- Makefile -*-===## -# -# The LLVM Compiler Infrastructure -# -# This file was developed by the LLVM research group and is distributed under -# the University of Illinois Open Source License. See LICENSE.TXT for details. -# -##===----------------------------------------------------------------------===## -LEVEL = ../../../.. -LIBRARYNAME = LLVMProfilePaths - -include $(LEVEL)/Makefile.common - diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp deleted file mode 100644 index ce9e328c275..00000000000 --- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp +++ /dev/null @@ -1,252 +0,0 @@ -//===-- ProfilePaths.cpp - interface to insert instrumentation --*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This inserts instrumentation for counting execution of paths though a given -// function Its implemented as a "Function" Pass, and called using opt -// -// This pass is implemented by using algorithms similar to -// 1."Efficient Path Profiling": Ball, T. and Larus, J. R., -// Proceedings of Micro-29, Dec 1996, Paris, France. -// 2."Efficiently Counting Program events with support for on-line -// "queries": Ball T., ACM Transactions on Programming Languages -// and systems, Sep 1994. -// -// The algorithms work on a Graph constructed over the nodes made from Basic -// Blocks: The transformations then take place on the constructed graph -// (implementation in Graph.cpp and GraphAuxiliary.cpp) and finally, appropriate -// instrumentation is placed over suitable edges. (code inserted through -// EdgeCode.cpp). -// -// The algorithm inserts code such that every acyclic path in the CFG of a -// function is identified through a unique number. the code insertion is optimal -// in the sense that its inserted over a minimal set of edges. Also, the -// algorithm makes sure than initialization, path increment and counter update -// can be collapsed into minimum number of edges. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/Instrumentation.h" -#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" -#include "llvm/Support/CFG.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Instructions.h" -#include "llvm/Module.h" -#include "Graph.h" -#include <fstream> -#include <cstdio> - -namespace llvm { - -struct ProfilePaths : public FunctionPass { - bool runOnFunction(Function &F); - - // Before this pass, make sure that there is only one - // entry and only one exit node for the function in the CFG of the function - // - void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<UnifyFunctionExitNodes>(); - } -}; - -static RegisterOpt<ProfilePaths> X("paths", "Profile Paths"); - -FunctionPass *createProfilePathsPass() { return new ProfilePaths(); } - -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; -} - -//Per function pass for inserting counters and trigger code -bool ProfilePaths::runOnFunction(Function &F){ - - static int mn = -1; - static int CountCounter = 1; - if(F.isExternal()) { - return false; - } - - //increment counter for instrumented functions. mn is now function# - mn++; - - // Transform the cfg s.t. we have just one exit node - BasicBlock *ExitNode = - getAnalysis<UnifyFunctionExitNodes>().getReturnBlock(); - - //iterating over BBs and making graph - std::vector<Node *> nodes; - std::vector<Edge> edges; - - Node *exitNode = 0, *startNode = 0; - - // The nodes must be uniquely identified: - // That is, no two nodes must hav same BB* - - for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) { - Node *nd=new Node(BB); - nodes.push_back(nd); - if(&*BB == ExitNode) - exitNode=nd; - if(BB==F.begin()) - startNode=nd; - } - - // now do it again to insert edges - for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB){ - Node *nd=findBB(nodes, BB); - assert(nd && "No node for this edge!"); - - for(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); - } - } - - Graph g(nodes,edges, startNode, exitNode); - -#ifdef DEBUG_PATH_PROFILES - std::cerr<<"Original graph\n"; - printGraph(g); -#endif - - BasicBlock *fr = &F.front(); - - // The graph is made acyclic: this is done - // by removing back edges for now, and adding them later on - std::vector<Edge> be; - std::map<Node *, int> nodePriority; //it ranks nodes in depth first order traversal - g.getBackEdges(be, nodePriority); - -#ifdef DEBUG_PATH_PROFILES - std::cerr<<"BackEdges-------------\n"; - for (std::vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){ - printEdge(*VI); - cerr<<"\n"; - } - std::cerr<<"------\n"; -#endif - -#ifdef DEBUG_PATH_PROFILES - cerr<<"Backedges:"<<be.size()<<endl; -#endif - //Now we need to reflect the effect of back edges - //This is done by adding dummy edges - //If a->b is a back edge - //Then we add 2 back edges for it: - //1. from root->b (in vector stDummy) - //and 2. from a->exit (in vector exDummy) - std::vector<Edge> stDummy; - std::vector<Edge> exDummy; - addDummyEdges(stDummy, exDummy, g, be); - -#ifdef DEBUG_PATH_PROFILES - std::cerr<<"After adding dummy edges\n"; - printGraph(g); -#endif - - // Now, every edge in the graph is assigned a weight - // This weight later adds on to assign path - // numbers to different paths in the graph - // All paths for now are acyclic, - // since no back edges in the graph now - // numPaths is the number of acyclic paths in the graph - int numPaths=valueAssignmentToEdges(g, nodePriority, be); - - //if(numPaths<=1) return false; - - static GlobalVariable *threshold = NULL; - static bool insertedThreshold = false; - - if(!insertedThreshold){ - threshold = new GlobalVariable(Type::IntTy, false, - GlobalValue::ExternalLinkage, 0, - "reopt_threshold"); - - F.getParent()->getGlobalList().push_back(threshold); - insertedThreshold = true; - } - - assert(threshold && "GlobalVariable threshold not defined!"); - - - if(fr->getParent()->getName() == "main"){ - //initialize threshold - - // FIXME: THIS IS HORRIBLY BROKEN. FUNCTION PASSES CANNOT DO THIS, EXCEPT - // IN THEIR INITIALIZE METHOD!! - Function *initialize = - F.getParent()->getOrInsertFunction("reoptimizerInitialize", Type::VoidTy, - PointerType::get(Type::IntTy), - (Type *)0); - - std::vector<Value *> trargs; - trargs.push_back(threshold); - new CallInst(initialize, trargs, "", fr->begin()); - } - - - if(numPaths<=1 || numPaths >5000) return false; - -#ifdef DEBUG_PATH_PROFILES - printGraph(g); -#endif - - //create instruction allocation r and count - //r is the variable that'll act like an accumulator - //all along the path, we just add edge values to r - //and at the end, r reflects the path number - //count is an array: count[x] would store - //the number of executions of path numbered x - - Instruction *rVar=new - AllocaInst(Type::IntTy, - ConstantUInt::get(Type::UIntTy,1),"R"); - - //Instruction *countVar=new - //AllocaInst(Type::IntTy, - // ConstantUInt::get(Type::UIntTy, numPaths), "Count"); - - //initialize counter array! - std::vector<Constant*> arrayInitialize; - for(int xi=0; xi<numPaths; xi++) - arrayInitialize.push_back(ConstantSInt::get(Type::IntTy, 0)); - - const ArrayType *ATy = ArrayType::get(Type::IntTy, numPaths); - Constant *initializer = ConstantArray::get(ATy, arrayInitialize); - char tempChar[20]; - sprintf(tempChar, "Count%d", CountCounter); - CountCounter++; - std::string countStr = tempChar; - GlobalVariable *countVar = new GlobalVariable(ATy, false, - GlobalValue::InternalLinkage, - initializer, countStr, - F.getParent()); - - // insert initialization code in first (entry) BB - // this includes initializing r and count - insertInTopBB(&F.getEntryBlock(), numPaths, rVar, threshold); - - //now process the graph: get path numbers, - //get increments along different paths, - //and assign "increments" and "updates" (to r and count) - //"optimally". Finally, insert llvm code along various edges - processGraph(g, rVar, countVar, be, stDummy, exDummy, numPaths, mn, - threshold); - - return true; // Always modifies function -} - -} // End llvm namespace diff --git a/llvm/lib/Transforms/Instrumentation/ProfilePaths/RetracePath.cpp b/llvm/lib/Transforms/Instrumentation/ProfilePaths/RetracePath.cpp deleted file mode 100644 index 8c343df8f69..00000000000 --- a/llvm/lib/Transforms/Instrumentation/ProfilePaths/RetracePath.cpp +++ /dev/null @@ -1,308 +0,0 @@ -//===- RetracePath.cpp ----------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Retraces a path of BasicBlock, given a path number and a graph! -// -//===----------------------------------------------------------------------===// - -#include "llvm/Module.h" -#include "llvm/Instructions.h" -#include "llvm/Support/CFG.h" -#include "Graph.h" -#include <iostream> - -using std::vector; -using std::map; -using std::cerr; - -namespace llvm { - -//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){ - Graph::nodeList &nlist = g.getNodeList(n); - - //printGraph(g); - //std::cerr<<"Path No: "<<pathNo<<"\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){ - if(NLI->weight>maxCount && NLI->weight<=pathNo){ - maxCount=NLI->weight; - nextRoot=NLI->element; - edgeRnd=NLI->randId; - if(isStart) - strand=NLI->randId; - } - } - - 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; - break; - } - } - - //check if start has it - for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE; - ++VI){ - if(VI->getRandId()==strand){ - 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(); - vBB.erase(vBB.begin()); - 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] && - VI->getSecond()->getElement() == vBB[0]){ - //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){//, - // vector<Instruction *> &instToErase){ - //step 1: create graph - //Transform the cfg s.t. we have just one exit node - - std::vector<Node *> nodes; - std::vector<Edge> edges; - Node *exitNode=0, *startNode=0; - - //Creat cfg just once for each function! - static std::map<Function *, Graph *> graphMap; - - //get backedges, exit and start edges for the graphs and store them - static std::map<Function *, vector<Edge> > stMap, exMap, beMap; - static std::map<Function *, Value *> pathReg; //path register - - - if(!graphMap[M]){ - BasicBlock *ExitNode = 0; - for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I){ - if (isa<ReturnInst>(I->getTerminator())) { - ExitNode = I; - break; - } - } - - assert(ExitNode!=0 && "exitnode not found"); - - //iterating over BBs and making graph - //The nodes must be uniquely identified: - //That is, no two nodes must hav same BB* - - //keep a map for trigger basicblocks! - std::map<BasicBlock *, unsigned char> triggerBBs; - //First enter just nodes: later enter edges - for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){ - bool cont = false; - - if(BB->size()==3 || BB->size() ==2){ - for(BasicBlock::iterator II = BB->begin(), IE = BB->end(); - II != IE; ++II){ - if(CallInst *callInst = dyn_cast<CallInst>(II)){ - //std::cerr<<*callInst; - Function *calledFunction = callInst->getCalledFunction(); - if(calledFunction && calledFunction->getName() == "trigger"){ - triggerBBs[BB] = 9; - cont = true; - //std::cerr<<"Found trigger!\n"; - break; - } - } - } - } - - if(cont) - continue; - - // const Instruction *inst = BB->getInstList().begin(); - // if(isa<CallInst>(inst)){ - // Instruction *ii1 = BB->getInstList().begin(); - // CallInst *callInst = dyn_cast<CallInst>(ii1); - // if(callInst->getCalledFunction()->getName()=="trigger") - // continue; - // } - - 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){ - if(triggerBBs[BB] == 9) - continue; - - //if(BB->size()==3) - //if(CallInst *callInst = dyn_cast<CallInst>(BB->getInstList().begin())) - //if(callInst->getCalledFunction()->getName() == "trigger") - //continue; - - // if(BB->size()==2){ - // const Instruction *inst = BB->getInstList().begin(); - // if(isa<CallInst>(inst)){ - // Instruction *ii1 = BB->getInstList().begin(); - // CallInst *callInst = dyn_cast<CallInst>(ii1); - // if(callInst->getCalledFunction()->getName()=="trigger") - // continue; - // } - // } - - Node *nd=findBB(nodes, BB); - assert(nd && "No node for this edge!"); - - for(succ_iterator s=succ_begin(BB), se=succ_end(BB); s!=se; ++s){ - - if(triggerBBs[*s] == 9){ - //if(!pathReg[M]){ //Get the path register for this! - //if(BB->size()>8) - // if(LoadInst *ldInst = dyn_cast<LoadInst>(BB->getInstList().begin())) - // pathReg[M] = ldInst->getPointerOperand(); - //} - continue; - } - //if((*s)->size()==3) - //if(CallInst *callInst = - // dyn_cast<CallInst>((*s)->getInstList().begin())) - // if(callInst->getCalledFunction()->getName() == "trigger") - // continue; - - // if((*s)->size()==2){ - // const Instruction *inst = (*s)->getInstList().begin(); - // if(isa<CallInst>(inst)){ - // Instruction *ii1 = (*s)->getInstList().begin(); - // CallInst *callInst = dyn_cast<CallInst>(ii1); - // if(callInst->getCalledFunction()->getName()=="trigger") - // continue; - // } - // } - - Node *nd2 = findBB(nodes,*s); - assert(nd2 && "No node for this edge!"); - Edge ed(nd,nd2,0); - edges.push_back(ed); - } - } - - graphMap[M]= new Graph(nodes,edges, startNode, exitNode); - - Graph *g = graphMap[M]; - - if (M->size() <= 1) return; //uninstrumented - - //step 2: getBackEdges - //vector<Edge> be; - std::map<Node *, int> nodePriority; - g->getBackEdges(beMap[M], nodePriority); - - //step 3: add dummy edges - //vector<Edge> stDummy; - //vector<Edge> exDummy; - addDummyEdges(stMap[M], exMap[M], *g, beMap[M]); - - //step 4: value assgn to edges - int numPaths = valueAssignmentToEdges(*g, nodePriority, beMap[M]); - } - - - //step 5: now travel from root, select max(edge) < pathNo, - //and go on until reach the exit - getPathFrmNode(graphMap[M]->getRoot(), vBB, pathNo, *graphMap[M], - stMap[M], exMap[M], beMap[M], -1); - - - //post process vBB to locate instructions to be erased - /* - if(pathReg[M]){ - for(vector<BasicBlock *>::iterator VBI = vBB.begin(), VBE = vBB.end(); - VBI != VBE; ++VBI){ - for(BasicBlock::iterator BBI = (*VBI)->begin(), BBE = (*VBI)->end(); - BBI != BBE; ++BBI){ - if(LoadInst *ldInst = dyn_cast<LoadInst>(BBI)){ - if(pathReg[M] == ldInst->getPointerOperand()) - instToErase.push_back(ldInst); - } - else if(StoreInst *stInst = dyn_cast<StoreInst>(BBI)){ - if(pathReg[M] == stInst->getPointerOperand()) - instToErase.push_back(stInst); - } - } - } - } - */ -} - -} // End llvm namespace |
