From 0df7ddbd31397356ef2ac0b44a2f188353ceeed9 Mon Sep 17 00:00:00 2001 From: Anand Shukla Date: Fri, 18 Jul 2003 16:08:32 +0000 Subject: [PATCH] A pass to combine multiple backedges that go to same target git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7201 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../ProfilePaths/CombineBranch.cpp | 227 ++++++++++++++++++ 1 file changed, 227 insertions(+) create mode 100644 lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp diff --git a/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp b/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp new file mode 100644 index 00000000000..f92de7000f8 --- /dev/null +++ b/lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp @@ -0,0 +1,227 @@ +//===-- InstLoops.cpp ---------------------------------------- ---*- C++ -*--=// +// Pass to instrument loops +// +// At every backedge, insert a counter for that backedge and a call function +//===----------------------------------------------------------------------===// + +#include "llvm/Reoptimizer/InstLoops.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Support/CFG.h" +#include "llvm/Constants.h" +#include "llvm/iMemory.h" +#include "llvm/GlobalVariable.h" +#include "llvm/DerivedTypes.h" +#include "llvm/iOther.h" +#include "llvm/iOperators.h" +#include "llvm/iTerminators.h" +#include "llvm/iPHINode.h" +#include "llvm/Module.h" +#include "llvm/Function.h" +#include "llvm/Pass.h" + +//this is used to color vertices +//during DFS + +enum Color{ + WHITE, + GREY, + BLACK +}; + +namespace{ + struct CombineBranches : public FunctionPass { + private: + //DominatorSet *DS; + void getBackEdgesVisit(BasicBlock *u, + std::map &color, + std::map &d, + int &time, + std::map &be); + void removeRedundant(std::map &be); + void getBackEdges(Function &F); + public: + bool runOnFunction(Function &F); + }; + + RegisterOpt X("branch-combine", "Multiple backedges going to same target are merged"); +} + +// Create a new pass to merge branches +// +Pass *createCombineBranchesPass() { + return new CombineBranches(); +} + + +//helper function to get back edges: it is called by +//the "getBackEdges" function below +void CombineBranches::getBackEdgesVisit(BasicBlock *u, + std::map &color, + std::map &d, + int &time, + std::map &be) { + + color[u]=GREY; + time++; + d[u]=time; + + for(BasicBlock::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 CombineBranches::removeRedundant(std::map &be){ + std::vector toDelete; + std::map seenBB; + + for(std::map::iterator MI = be.begin(), + ME = be.end(); MI != ME; ++MI){ + + if(seenBB[MI->second]) + continue; + + seenBB[MI->second] = 1; + + std::vector sameTarget; + sameTarget.clear(); + + for(std::map::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->getInstList().push_back(newBranch); + + std::map > phiMap; + + + for(std::vector::iterator VBI = sameTarget.begin(), + VBE = sameTarget.end(); VBI != VBE; ++VBI){ + + //std::cerr<<(*VBI)->getName()<<"\n"; + + BranchInst *ti = cast((*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(BB2Inst)){ + int bbIndex; + bbIndex = phiInst->getBasicBlockIndex(*VBI); + if(bbIndex>=0){ + phiMap[phiInst].push_back(bbIndex); + //phiInst->setIncomingBlock(bbIndex, newBB); + } + } + } + } + + for(std::map >::iterator + PI = phiMap.begin(), PE = phiMap.end(); PI != PE; ++PI){ + + PHINode *phiNode = new PHINode(PI->first->getType(), "phi", newBranch); + for(std::vector::iterator II = PI->second.begin(), + IE = PI->second.end(); II != IE; ++II){ + phiNode->addIncoming(PI->first->getIncomingValue(*II), + PI->first->getIncomingBlock(*II)); + } + + std::vector tempBB; + for(std::vector::iterator II = PI->second.begin(), + IE = PI->second.end(); II != IE; ++II){ + tempBB.push_back(PI->first->getIncomingBlock(*II)); + } + + for(std::vector::iterator II = tempBB.begin(), + IE = tempBB.end(); II != IE; ++II){ + PI->first->removeIncomingValue(*II); + } + + PI->first->addIncoming(phiNode, newBB); + } + //std::cerr<<"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n"; + //std::cerr<second; + //std::cerr<<"-----------------------------------\n"; + //std::cerr< color; + std::map d; + std::map be; + int time=0; + getBackEdgesVisit(F.begin(), color, d, time, be); + + removeRedundant(be); +} + +//Per function pass for inserting counters and call function +bool CombineBranches::runOnFunction(Function &F){ + + if(F.isExternal()) { + return false; + } + + //if(F.getName() == "main"){ + // F.setName("llvm_gprof_main"); + //} + + //std::cerr<