diff options
Diffstat (limited to 'lib/Transforms/Instrumentation')
15 files changed, 393 insertions, 393 deletions
diff --git a/lib/Transforms/Instrumentation/BlockProfiling.cpp b/lib/Transforms/Instrumentation/BlockProfiling.cpp index 476a9e8c53..f92f0ef6f0 100644 --- a/lib/Transforms/Instrumentation/BlockProfiling.cpp +++ b/lib/Transforms/Instrumentation/BlockProfiling.cpp @@ -1,10 +1,10 @@ //===- BlockProfiling.cpp - Insert counters for block profiling -----------===// -// +// // 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 pass instruments the specified program with counters for basic block or @@ -51,7 +51,7 @@ bool FunctionProfiler::runOnModule(Module &M) { } unsigned NumFunctions = 0; - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) if (!I->isExternal()) ++NumFunctions; @@ -62,7 +62,7 @@ bool FunctionProfiler::runOnModule(Module &M) { // Instrument all of the functions... unsigned i = 0; - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) if (!I->isExternal()) // Insert counter at the start of the function IncrementCounterInBlock(I->begin(), i++, Counters); @@ -93,7 +93,7 @@ bool BlockProfiler::runOnModule(Module &M) { } unsigned NumBlocks = 0; - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) NumBlocks += I->size(); const Type *ATy = ArrayType::get(Type::UIntTy, NumBlocks); @@ -103,7 +103,7 @@ bool BlockProfiler::runOnModule(Module &M) { // Instrument all of the blocks... unsigned i = 0; - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB) // Insert counter at the start of the block IncrementCounterInBlock(BB, i++, Counters); diff --git a/lib/Transforms/Instrumentation/EdgeProfiling.cpp b/lib/Transforms/Instrumentation/EdgeProfiling.cpp index c453554236..2ac6cc87de 100644 --- a/lib/Transforms/Instrumentation/EdgeProfiling.cpp +++ b/lib/Transforms/Instrumentation/EdgeProfiling.cpp @@ -1,10 +1,10 @@ //===- EdgeProfiling.cpp - Insert counters for edge profiling -------------===// -// +// // 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 pass instruments the specified program with counters for edge profiling. diff --git a/lib/Transforms/Instrumentation/EmitFunctions.cpp b/lib/Transforms/Instrumentation/EmitFunctions.cpp index 16d3687fb1..369a784a4e 100644 --- a/lib/Transforms/Instrumentation/EmitFunctions.cpp +++ b/lib/Transforms/Instrumentation/EmitFunctions.cpp @@ -1,10 +1,10 @@ //===-- EmitFunctions.cpp - interface to insert instrumentation -----------===// -// +// // 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 into the input module three new global constants containing @@ -27,7 +27,7 @@ #include "llvm/Transforms/Instrumentation.h" using namespace llvm; -namespace llvm { +namespace llvm { namespace { enum Color{ @@ -35,11 +35,11 @@ namespace { GREY, BLACK }; - + struct EmitFunctionTable : public ModulePass { bool runOnModule(Module &M); }; - + RegisterOpt<EmitFunctionTable> X("emitfuncs", "Emit a function table for the reoptimizer"); } @@ -48,9 +48,9 @@ static char doDFS(BasicBlock * node,std::map<BasicBlock *, Color > &color){ color[node] = GREY; for(succ_iterator vl = succ_begin(node), ve = succ_end(node); vl != ve; ++vl){ - - BasicBlock *BB = *vl; - + + BasicBlock *BB = *vl; + if(color[BB]!=GREY && color[BB]!=BLACK){ if(!doDFS(BB, color)){ return 0; @@ -75,7 +75,7 @@ static char hasBackEdge(Function *F){ // Per Module pass for inserting function table bool EmitFunctionTable::runOnModule(Module &M){ std::vector<const Type*> vType; - + std::vector<Constant *> vConsts; std::vector<Constant *> sBCons; @@ -83,24 +83,24 @@ bool EmitFunctionTable::runOnModule(Module &M){ for(Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) if (!MI->isExternal()) { vType.push_back(MI->getType()); - + //std::cerr<<MI; vConsts.push_back(MI); sBCons.push_back(ConstantInt::get(Type::SByteTy, hasBackEdge(MI))); - + counter++; } - + StructType *sttype = StructType::get(vType); Constant *cstruct = ConstantStruct::get(sttype, vConsts); GlobalVariable *gb = new GlobalVariable(cstruct->getType(), true, - GlobalValue::ExternalLinkage, + GlobalValue::ExternalLinkage, cstruct, "llvmFunctionTable"); M.getGlobalList().push_back(gb); - Constant *constArray = ConstantArray::get(ArrayType::get(Type::SByteTy, + Constant *constArray = ConstantArray::get(ArrayType::get(Type::SByteTy, sBCons.size()), sBCons); @@ -110,9 +110,9 @@ bool EmitFunctionTable::runOnModule(Module &M){ M.getGlobalList().push_back(funcArray); - ConstantInt *cnst = ConstantSInt::get(Type::IntTy, counter); - GlobalVariable *fnCount = new GlobalVariable(Type::IntTy, true, - GlobalValue::ExternalLinkage, + ConstantInt *cnst = ConstantSInt::get(Type::IntTy, counter); + GlobalVariable *fnCount = new GlobalVariable(Type::IntTy, true, + GlobalValue::ExternalLinkage, cnst, "llvmFunctionCount"); M.getGlobalList().push_back(fnCount); return true; // Always modifies program diff --git a/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp b/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp index 1a7b77387d..e592d28653 100644 --- a/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp +++ b/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp @@ -1,10 +1,10 @@ //===-- 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 @@ -31,14 +31,14 @@ namespace { void getBackEdgesVisit(BasicBlock *u, std::map<BasicBlock *, Color > &color, - std::map<BasicBlock *, int > &d, + 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"); } @@ -53,10 +53,10 @@ namespace { /// void CombineBranches::getBackEdgesVisit(BasicBlock *u, std::map<BasicBlock *, Color > &color, - std::map<BasicBlock *, int > &d, + std::map<BasicBlock *, int > &d, int &time, std::map<BasicBlock *, BasicBlock *> &be) { - + color[u]=GREY; time++; d[u]=time; @@ -66,7 +66,7 @@ void CombineBranches::getBackEdgesVisit(BasicBlock *u, 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 @@ -83,29 +83,29 @@ void CombineBranches::getBackEdgesVisit(BasicBlock *u, 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(), + + 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(), + + 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()){ @@ -126,9 +126,9 @@ void CombineBranches::removeRedundant(std::map<BasicBlock *, BasicBlock *> &be){ ti->setSuccessor(index, newBB); - for(BasicBlock::iterator BB2Inst = MI->second->begin(), + 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); @@ -178,7 +178,7 @@ bool CombineBranches::runOnFunction(Function &F){ int time = 0; getBackEdgesVisit (F.begin (), color, d, time, be); removeRedundant (be); - + return true; // FIXME: assumes a modification was always made. } diff --git a/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp b/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp index 8e7bd78958..aef4681f30 100644 --- a/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp +++ b/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp @@ -1,16 +1,16 @@ //===-- 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 +//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 +//It also has methods to insert initialization code in //top block of cfg //===----------------------------------------------------------------------===// @@ -29,8 +29,8 @@ using std::vector; namespace llvm { static void getTriggerCode(Module *M, BasicBlock *BB, int MethNo, Value *pathNo, - Value *cnt, Instruction *rInst){ - + Value *cnt, Instruction *rInst){ + vector<Value *> tmpVec; tmpVec.push_back(Constant::getNullValue(Type::LongTy)); tmpVec.push_back(Constant::getNullValue(Type::LongTy)); @@ -38,7 +38,7 @@ static void getTriggerCode(Module *M, BasicBlock *BB, int MethNo, Value *pathNo, BB->getInstList().push_back(Idx); const Type *PIntTy = PointerType::get(Type::IntTy); - Function *trigMeth = M->getOrInsertFunction("trigger", Type::VoidTy, + Function *trigMeth = M->getOrInsertFunction("trigger", Type::VoidTy, Type::IntTy, Type::IntTy, PIntTy, PIntTy, 0); assert(trigMeth && "trigger method could not be inserted!"); @@ -58,18 +58,18 @@ static void getTriggerCode(Module *M, BasicBlock *BB, int MethNo, Value *pathNo, //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, +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); } @@ -93,7 +93,7 @@ void getEdgeCode::getCode(Instruction *rInst, Value *countInst, #endif break; } - + //r+=k case 3:{ Instruction *ldInst = new LoadInst(rInst, "ti1");//, InsertPos); @@ -116,33 +116,33 @@ void getEdgeCode::getCode(Instruction *rInst, Value *countInst, tmpVec.push_back(ConstantSInt::get(Type::LongTy, inc)); Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//, - //Instruction *Idx = new GetElementPtrInst(countInst, + //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, + //getTriggerCode(M->getParent(), BB, MethNo, // ConstantSInt::get(Type::IntTy,inc), newCount, triggerInst); //end trigger code @@ -152,7 +152,7 @@ void getEdgeCode::getCode(Instruction *rInst, Value *countInst, //case: count[r+inc]++ case 5:{ - + //ti1=inc+r Instruction *ldIndex=new LoadInst(rInst, "ti1");//, InsertPos); BB->getInstList().push_back(ldIndex); @@ -161,9 +161,9 @@ void getEdgeCode::getCode(Instruction *rInst, Value *countInst, Instruction *addIndex=BinaryOperator:: create(Instruction::Add, ldIndex, val,"ti2");//, InsertPos); BB->getInstList().push_back(addIndex); - + //now load count[addIndex] - Instruction *castInst=new CastInst(addIndex, + Instruction *castInst=new CastInst(addIndex, Type::LongTy,"ctin");//, InsertPos); BB->getInstList().push_back(castInst); @@ -180,10 +180,10 @@ void getEdgeCode::getCode(Instruction *rInst, Value *countInst, 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, + 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); @@ -213,11 +213,11 @@ void getEdgeCode::getCode(Instruction *rInst, Value *countInst, tmpVec.push_back(castInst2); Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//, - //Instruction *Idx = new GetElementPtrInst(countInst, + //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); @@ -237,7 +237,7 @@ void getEdgeCode::getCode(Instruction *rInst, Value *countInst, retVec.push_back(ldIndex); break; } - + } } @@ -245,25 +245,25 @@ void getEdgeCode::getCode(Instruction *rInst, Value *countInst, //Insert the initialization code in the top BB //this includes initializing r, and count -//r is like an accumulator, that +//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, +void insertInTopBB(BasicBlock *front, + int k, Instruction *rVar, Value *threshold){ - //rVar is variable r, + //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++){ @@ -281,22 +281,22 @@ void insertInTopBB(BasicBlock *front, //insert a basic block with appropriate code //along a given edge void insertBB(Edge ed, - getEdgeCode *edgeCode, - Instruction *rInst, - Value *countInst, + 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 + + //We need to insert a BB between BB1 and BB2 TerminatorInst *TI=BB1->getTerminator(); BasicBlock *newBB=new BasicBlock("counter", BB1->getParent()); @@ -316,7 +316,7 @@ void insertBB(Edge ed, else{ if(BI->getSuccessor(0)==BB2) BI->setSuccessor(0, newBB); - + if(BI->getSuccessor(1)==BB2) BI->setSuccessor(1, newBB); } @@ -324,21 +324,21 @@ void insertBB(Edge ed, BasicBlock *triggerBB = NULL; if(retVec.size()>0){ triggerBB = new BasicBlock("trigger", BB1->getParent()); - getTriggerCode(BB1->getParent()->getParent(), triggerBB, Methno, + 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, + + //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); } @@ -347,9 +347,9 @@ void insertBB(Edge ed, } //now iterate over BB2, and set its Phi nodes right - for(BasicBlock::iterator BB2Inst = BB2->begin(), BBend = BB2->end(); + 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); diff --git a/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp b/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp index 21a6e93e04..21883c41b0 100644 --- a/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp +++ b/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp @@ -1,10 +1,10 @@ //===-- 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 @@ -23,7 +23,7 @@ namespace llvm { const graphListElement *findNodeInList(const Graph::nodeList &NL, Node *N) { - for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE; + for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE; ++NI) if (*NI->element== *N) return &*NI; @@ -38,7 +38,7 @@ graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) { } //graph constructor with root and exit specified -Graph::Graph(std::vector<Node*> n, std::vector<Edge> e, +Graph::Graph(std::vector<Node*> n, std::vector<Edge> e, Node *rt, Node *lt){ strt=rt; ext=lt; @@ -49,17 +49,17 @@ Graph::Graph(std::vector<Node*> n, std::vector<Edge> e, 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_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; @@ -79,7 +79,7 @@ Graph::nodeList &Graph::sortNodeList(Node *par, nodeList &nl, vector<Edge> &be){ 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! @@ -109,24 +109,24 @@ Graph::nodeList &Graph::sortNodeList(Node *par, nodeList &nl, vector<Edge> &be){ } } } - + 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; @@ -159,11 +159,11 @@ bool Graph::hasEdgeAndWt(Edge ed){ 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; } @@ -180,9 +180,9 @@ void Graph::addNode(Node *nd){ } //add an edge -//this adds an edge ONLY when +//this adds an edge ONLY when //the edge to be added does not already exist -//we "equate" two edges here only with their +//we "equate" two edges here only with their //end points void Graph::addEdge(Edge ed, int w){ nodeList &ndList = nodes[ed.getFirst()]; @@ -190,7 +190,7 @@ void Graph::addEdge(Edge ed, int w){ 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); @@ -296,7 +296,7 @@ int Graph::getNumberOfIncomingEdges(Node *nd){ 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; + for(Graph::nodeList::const_iterator NI = nl.begin(), NE=nl.end(); NI != NE; ++NI) if (*NI->element== *nd) count++; @@ -340,19 +340,19 @@ static void printNode(Node *nd){ //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 + //for all vertices w in vt, + //if wt(w) greater than //the wt(u->w), then assign //wt(w) to be wt(u->w). // @@ -360,7 +360,7 @@ Graph* Graph::getMaxSpanningTree(){ //keep pulling out vertices from vt till it is empty vector<Node *> vt; - + std::map<Node*, Node* > parent; std::map<Node*, int > ed_weight; @@ -373,7 +373,7 @@ Graph* Graph::getMaxSpanningTree(){ parent[thisNode]=NULL; ed_weight[thisNode]=0; } - else{ + else{ thisNode->setWeight(inf); } st->addNode(thisNode);//add all nodes to spanning tree @@ -396,7 +396,7 @@ Graph* Graph::getMaxSpanningTree(){ } //vt.erase(u); - + //remove u frm vt for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){ if(**VI==*u){ @@ -404,7 +404,7 @@ Graph* Graph::getMaxSpanningTree(){ break; } } - + //assign wt(v) to all adjacent vertices v of u //only if v is in vt Graph::nodeList &nl = getNodeList(u); @@ -438,7 +438,7 @@ Graph* Graph::getMaxSpanningTree(){ return st; } -//print the graph (for debugging) +//print the graph (for debugging) void Graph::printGraph(){ vector<Node *> lt=getAllNodes(); std::cerr<<"Graph---------------------\n"; @@ -469,7 +469,7 @@ vector<Node *> Graph::reverseTopologicalSort(){ } //a private method for doing DFS traversal of graph -//this is used in determining the reverse topological sort +//this is used in determining the reverse topological sort //of the graph void Graph::DFS_Visit(Node *nd, vector<Node *> &toReturn){ nd->setWeight(GREY); @@ -482,13 +482,13 @@ void Graph::DFS_Visit(Node *nd, vector<Node *> &toReturn){ } //Ordinarily, the graph is directional -//this converts the graph into an +//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; + 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){ @@ -507,10 +507,10 @@ void Graph::makeUnDirectional(){ //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; + 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(); + for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end(); NLI!=NLE; ++NLI) NLI->weight=-NLI->weight; } @@ -535,7 +535,7 @@ void Graph::getBackEdges(vector<Edge > &be, std::map<Node *, int> &d){ getBackEdgesVisit(getRoot(), be, color, d, time); } -//helper function to get back edges: it is called by +//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, @@ -545,14 +545,14 @@ void Graph::getBackEdgesVisit(Node *u, vector<Edge > &be, d[u]=time; vector<graphListElement> &succ_list = getNodeList(u); - - for(vector<graphListElement>::iterator vl=succ_list.begin(), + + 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 diff --git a/lib/Transforms/Instrumentation/ProfilePaths/Graph.h b/lib/Transforms/Instrumentation/ProfilePaths/Graph.h index 44b63a91ea..203948454c 100644 --- a/lib/Transforms/Instrumentation/ProfilePaths/Graph.h +++ b/lib/Transforms/Instrumentation/ProfilePaths/Graph.h @@ -1,10 +1,10 @@ //===-- Graph.h -------------------------------------------------*- C++ -*-===// |