From 928a75f057fc5efa74d6fc512449bddb10df20ff Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Sat, 31 Oct 2009 14:37:31 +0000 Subject: Rename UnrollLoop.cpp to LoopUnroll.cpp, and LoopUnroll.cpp to LoopUnrollPass.cpp, for consistency with other passes which are similarly split. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85659 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnroll.cpp | 177 --------------- lib/Transforms/Scalar/LoopUnrollPass.cpp | 177 +++++++++++++++ lib/Transforms/Utils/LoopUnroll.cpp | 372 +++++++++++++++++++++++++++++++ lib/Transforms/Utils/UnrollLoop.cpp | 372 ------------------------------- 4 files changed, 549 insertions(+), 549 deletions(-) delete mode 100644 lib/Transforms/Scalar/LoopUnroll.cpp create mode 100644 lib/Transforms/Scalar/LoopUnrollPass.cpp create mode 100644 lib/Transforms/Utils/LoopUnroll.cpp delete mode 100644 lib/Transforms/Utils/UnrollLoop.cpp diff --git a/lib/Transforms/Scalar/LoopUnroll.cpp b/lib/Transforms/Scalar/LoopUnroll.cpp deleted file mode 100644 index 837ec59dbb..0000000000 --- a/lib/Transforms/Scalar/LoopUnroll.cpp +++ /dev/null @@ -1,177 +0,0 @@ -//===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass implements a simple loop unroller. It works best when loops have -// been canonicalized by the -indvars pass, allowing it to determine the trip -// counts of loops easily. -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "loop-unroll" -#include "llvm/IntrinsicInst.h" -#include "llvm/Transforms/Scalar.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/LoopPass.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/UnrollLoop.h" -#include - -using namespace llvm; - -static cl::opt -UnrollThreshold("unroll-threshold", cl::init(100), cl::Hidden, - cl::desc("The cut-off point for automatic loop unrolling")); - -static cl::opt -UnrollCount("unroll-count", cl::init(0), cl::Hidden, - cl::desc("Use this unroll count for all loops, for testing purposes")); - -static cl::opt -UnrollAllowPartial("unroll-allow-partial", cl::init(false), cl::Hidden, - cl::desc("Allows loops to be partially unrolled until " - "-unroll-threshold loop size is reached.")); - -namespace { - class LoopUnroll : public LoopPass { - public: - static char ID; // Pass ID, replacement for typeid - LoopUnroll() : LoopPass(&ID) {} - - /// A magic value for use with the Threshold parameter to indicate - /// that the loop unroll should be performed regardless of how much - /// code expansion would result. - static const unsigned NoThreshold = UINT_MAX; - - bool runOnLoop(Loop *L, LPPassManager &LPM); - - /// This transformation requires natural loop information & requires that - /// loop preheaders be inserted into the CFG... - /// - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequiredID(LoopSimplifyID); - AU.addRequiredID(LCSSAID); - AU.addRequired(); - AU.addPreservedID(LCSSAID); - AU.addPreserved(); - // FIXME: Loop unroll requires LCSSA. And LCSSA requires dom info. - // If loop unroll does not preserve dom info then LCSSA pass on next - // loop will receive invalid dom info. - // For now, recreate dom info, if loop is unrolled. - AU.addPreserved(); - AU.addPreserved(); - } - }; -} - -char LoopUnroll::ID = 0; -static RegisterPass X("loop-unroll", "Unroll loops"); - -Pass *llvm::createLoopUnrollPass() { return new LoopUnroll(); } - -/// ApproximateLoopSize - Approximate the size of the loop. -static unsigned ApproximateLoopSize(const Loop *L) { - unsigned Size = 0; - for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); - I != E; ++I) { - BasicBlock *BB = *I; - Instruction *Term = BB->getTerminator(); - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { - if (isa(I) && BB == L->getHeader()) { - // Ignore PHI nodes in the header. - } else if (I->hasOneUse() && I->use_back() == Term) { - // Ignore instructions only used by the loop terminator. - } else if (isa(I)) { - // Ignore debug instructions - } else if (isa(I) && I->hasOneUse()) { - // Ignore GEP as they generally are subsumed into a load or store. - } else if (isa(I)) { - // Estimate size overhead introduced by call instructions which - // is higher than other instructions. Here 3 and 10 are magic - // numbers that help one isolated test case from PR2067 without - // negatively impacting measured benchmarks. - Size += isa(I) ? 3 : 10; - } else { - ++Size; - } - - // TODO: Ignore expressions derived from PHI and constants if inval of phi - // is a constant, or if operation is associative. This will get induction - // variables. - } - } - - return Size; -} - -bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { - assert(L->isLCSSAForm()); - LoopInfo *LI = &getAnalysis(); - - BasicBlock *Header = L->getHeader(); - DEBUG(errs() << "Loop Unroll: F[" << Header->getParent()->getName() - << "] Loop %" << Header->getName() << "\n"); - (void)Header; - - // Find trip count - unsigned TripCount = L->getSmallConstantTripCount(); - unsigned Count = UnrollCount; - - // Automatically select an unroll count. - if (Count == 0) { - // Conservative heuristic: if we know the trip count, see if we can - // completely unroll (subject to the threshold, checked below); otherwise - // try to find greatest modulo of the trip count which is still under - // threshold value. - if (TripCount == 0) - return false; - Count = TripCount; - } - - // Enforce the threshold. - if (UnrollThreshold != NoThreshold) { - unsigned LoopSize = ApproximateLoopSize(L); - DEBUG(errs() << " Loop Size = " << LoopSize << "\n"); - uint64_t Size = (uint64_t)LoopSize*Count; - if (TripCount != 1 && Size > UnrollThreshold) { - DEBUG(errs() << " Too large to fully unroll with count: " << Count - << " because size: " << Size << ">" << UnrollThreshold << "\n"); - if (!UnrollAllowPartial) { - DEBUG(errs() << " will not try to unroll partially because " - << "-unroll-allow-partial not given\n"); - return false; - } - // Reduce unroll count to be modulo of TripCount for partial unrolling - Count = UnrollThreshold / LoopSize; - while (Count != 0 && TripCount%Count != 0) { - Count--; - } - if (Count < 2) { - DEBUG(errs() << " could not unroll partially\n"); - return false; - } - DEBUG(errs() << " partially unrolling with count: " << Count << "\n"); - } - } - - // Unroll the loop. - Function *F = L->getHeader()->getParent(); - if (!UnrollLoop(L, Count, LI, &LPM)) - return false; - - // FIXME: Reconstruct dom info, because it is not preserved properly. - DominatorTree *DT = getAnalysisIfAvailable(); - if (DT) { - DT->runOnFunction(*F); - DominanceFrontier *DF = getAnalysisIfAvailable(); - if (DF) - DF->runOnFunction(*F); - } - return true; -} diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp new file mode 100644 index 0000000000..837ec59dbb --- /dev/null +++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -0,0 +1,177 @@ +//===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass implements a simple loop unroller. It works best when loops have +// been canonicalized by the -indvars pass, allowing it to determine the trip +// counts of loops easily. +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "loop-unroll" +#include "llvm/IntrinsicInst.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/UnrollLoop.h" +#include + +using namespace llvm; + +static cl::opt +UnrollThreshold("unroll-threshold", cl::init(100), cl::Hidden, + cl::desc("The cut-off point for automatic loop unrolling")); + +static cl::opt +UnrollCount("unroll-count", cl::init(0), cl::Hidden, + cl::desc("Use this unroll count for all loops, for testing purposes")); + +static cl::opt +UnrollAllowPartial("unroll-allow-partial", cl::init(false), cl::Hidden, + cl::desc("Allows loops to be partially unrolled until " + "-unroll-threshold loop size is reached.")); + +namespace { + class LoopUnroll : public LoopPass { + public: + static char ID; // Pass ID, replacement for typeid + LoopUnroll() : LoopPass(&ID) {} + + /// A magic value for use with the Threshold parameter to indicate + /// that the loop unroll should be performed regardless of how much + /// code expansion would result. + static const unsigned NoThreshold = UINT_MAX; + + bool runOnLoop(Loop *L, LPPassManager &LPM); + + /// This transformation requires natural loop information & requires that + /// loop preheaders be inserted into the CFG... + /// + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredID(LoopSimplifyID); + AU.addRequiredID(LCSSAID); + AU.addRequired(); + AU.addPreservedID(LCSSAID); + AU.addPreserved(); + // FIXME: Loop unroll requires LCSSA. And LCSSA requires dom info. + // If loop unroll does not preserve dom info then LCSSA pass on next + // loop will receive invalid dom info. + // For now, recreate dom info, if loop is unrolled. + AU.addPreserved(); + AU.addPreserved(); + } + }; +} + +char LoopUnroll::ID = 0; +static RegisterPass X("loop-unroll", "Unroll loops"); + +Pass *llvm::createLoopUnrollPass() { return new LoopUnroll(); } + +/// ApproximateLoopSize - Approximate the size of the loop. +static unsigned ApproximateLoopSize(const Loop *L) { + unsigned Size = 0; + for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); + I != E; ++I) { + BasicBlock *BB = *I; + Instruction *Term = BB->getTerminator(); + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { + if (isa(I) && BB == L->getHeader()) { + // Ignore PHI nodes in the header. + } else if (I->hasOneUse() && I->use_back() == Term) { + // Ignore instructions only used by the loop terminator. + } else if (isa(I)) { + // Ignore debug instructions + } else if (isa(I) && I->hasOneUse()) { + // Ignore GEP as they generally are subsumed into a load or store. + } else if (isa(I)) { + // Estimate size overhead introduced by call instructions which + // is higher than other instructions. Here 3 and 10 are magic + // numbers that help one isolated test case from PR2067 without + // negatively impacting measured benchmarks. + Size += isa(I) ? 3 : 10; + } else { + ++Size; + } + + // TODO: Ignore expressions derived from PHI and constants if inval of phi + // is a constant, or if operation is associative. This will get induction + // variables. + } + } + + return Size; +} + +bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { + assert(L->isLCSSAForm()); + LoopInfo *LI = &getAnalysis(); + + BasicBlock *Header = L->getHeader(); + DEBUG(errs() << "Loop Unroll: F[" << Header->getParent()->getName() + << "] Loop %" << Header->getName() << "\n"); + (void)Header; + + // Find trip count + unsigned TripCount = L->getSmallConstantTripCount(); + unsigned Count = UnrollCount; + + // Automatically select an unroll count. + if (Count == 0) { + // Conservative heuristic: if we know the trip count, see if we can + // completely unroll (subject to the threshold, checked below); otherwise + // try to find greatest modulo of the trip count which is still under + // threshold value. + if (TripCount == 0) + return false; + Count = TripCount; + } + + // Enforce the threshold. + if (UnrollThreshold != NoThreshold) { + unsigned LoopSize = ApproximateLoopSize(L); + DEBUG(errs() << " Loop Size = " << LoopSize << "\n"); + uint64_t Size = (uint64_t)LoopSize*Count; + if (TripCount != 1 && Size > UnrollThreshold) { + DEBUG(errs() << " Too large to fully unroll with count: " << Count + << " because size: " << Size << ">" << UnrollThreshold << "\n"); + if (!UnrollAllowPartial) { + DEBUG(errs() << " will not try to unroll partially because " + << "-unroll-allow-partial not given\n"); + return false; + } + // Reduce unroll count to be modulo of TripCount for partial unrolling + Count = UnrollThreshold / LoopSize; + while (Count != 0 && TripCount%Count != 0) { + Count--; + } + if (Count < 2) { + DEBUG(errs() << " could not unroll partially\n"); + return false; + } + DEBUG(errs() << " partially unrolling with count: " << Count << "\n"); + } + } + + // Unroll the loop. + Function *F = L->getHeader()->getParent(); + if (!UnrollLoop(L, Count, LI, &LPM)) + return false; + + // FIXME: Reconstruct dom info, because it is not preserved properly. + DominatorTree *DT = getAnalysisIfAvailable(); + if (DT) { + DT->runOnFunction(*F); + DominanceFrontier *DF = getAnalysisIfAvailable(); + if (DF) + DF->runOnFunction(*F); + } + return true; +} diff --git a/lib/Transforms/Utils/LoopUnroll.cpp b/lib/Transforms/Utils/LoopUnroll.cpp new file mode 100644 index 0000000000..4d838b50e3 --- /dev/null +++ b/lib/Transforms/Utils/LoopUnroll.cpp @@ -0,0 +1,372 @@ +//===-- UnrollLoop.cpp - Loop unrolling utilities -------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements some loop unrolling utilities. It does not define any +// actual pass or policy, but provides a single function to perform loop +// unrolling. +// +// It works best when loops have been canonicalized by the -indvars pass, +// allowing it to determine the trip counts of loops easily. +// +// The process of unrolling can produce extraneous basic blocks linked with +// unconditional branches. This will be corrected in the future. +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "loop-unroll" +#include "llvm/Transforms/Utils/UnrollLoop.h" +#include "llvm/BasicBlock.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Transforms/Utils/Local.h" +#include + +using namespace llvm; + +// TODO: Should these be here or in LoopUnroll? +STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled"); +STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)"); + +/// RemapInstruction - Convert the instruction operands from referencing the +/// current values into those specified by ValueMap. +static inline void RemapInstruction(Instruction *I, + DenseMap &ValueMap) { + for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) { + Value *Op = I->getOperand(op); + DenseMap::iterator It = ValueMap.find(Op); + if (It != ValueMap.end()) Op = It->second; + I->setOperand(op, Op); + } +} + +/// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it +/// only has one predecessor, and that predecessor only has one successor. +/// The LoopInfo Analysis that is passed will be kept consistent. +/// Returns the new combined block. +static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) { + // Merge basic blocks into their predecessor if there is only one distinct + // pred, and if there is only one distinct successor of the predecessor, and + // if there are no PHI nodes. + BasicBlock *OnlyPred = BB->getSinglePredecessor(); + if (!OnlyPred) return 0; + + if (OnlyPred->getTerminator()->getNumSuccessors() != 1) + return 0; + + DEBUG(errs() << "Merging: " << *BB << "into: " << *OnlyPred); + + // Resolve any PHI nodes at the start of the block. They are all + // guaranteed to have exactly one entry if they exist, unless there are + // multiple duplicate (but guaranteed to be equal) entries for the + // incoming edges. This occurs when there are multiple edges from + // OnlyPred to OnlySucc. + FoldSingleEntryPHINodes(BB); + + // Delete the unconditional branch from the predecessor... + OnlyPred->getInstList().pop_back(); + + // Move all definitions in the successor to the predecessor... + OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); + + // Make all PHI nodes that referred to BB now refer to Pred as their + // source... + BB->replaceAllUsesWith(OnlyPred); + + std::string OldName = BB->getName(); + + // Erase basic block from the function... + LI->removeBlock(BB); + BB->eraseFromParent(); + + // Inherit predecessor's name if it exists... + if (!OldName.empty() && !OnlyPred->hasName()) + OnlyPred->setName(OldName); + + return OnlyPred; +} + +/// Unroll the given loop by Count. The loop must be in LCSSA form. Returns true +/// if unrolling was succesful, or false if the loop was unmodified. Unrolling +/// can only fail when the loop's latch block is not terminated by a conditional +/// branch instruction. However, if the trip count (and multiple) are not known, +/// loop unrolling will mostly produce more code that is no faster. +/// +/// The LoopInfo Analysis that is passed will be kept consistent. +/// +/// If a LoopPassManager is passed in, and the loop is fully removed, it will be +/// removed from the LoopPassManager as well. LPM can also be NULL. +bool llvm::UnrollLoop(Loop *L, unsigned Count, LoopInfo* LI, LPPassManager* LPM) { + assert(L->isLCSSAForm()); + + BasicBlock *Header = L->getHeader(); + BasicBlock *LatchBlock = L->getLoopLatch(); + BranchInst *BI = dyn_cast(LatchBlock->getTerminator()); + + if (!BI || BI->isUnconditional()) { + // The loop-rotate pass can be helpful to avoid this in many cases. + DEBUG(errs() << + " Can't unroll; loop not terminated by a conditional branch.\n"); + return false; + } + + // Find trip count + unsigned TripCount = L->getSmallConstantTripCount(); + // Find trip multiple if count is not available + unsigned TripMultiple = 1; + if (TripCount == 0) + TripMultiple = L->getSmallConstantTripMultiple(); + + if (TripCount != 0) + DEBUG(errs() << " Trip Count = " << TripCount << "\n"); + if (TripMultiple != 1) + DEBUG(errs() << " Trip Multiple = " << TripMultiple << "\n"); + + // Effectively "DCE" unrolled iterations that are beyond the tripcount + // and will never be executed. + if (TripCount != 0 && Count > TripCount) + Count = TripCount; + + assert(Count > 0); + assert(TripMultiple > 0); + assert(TripCount == 0 || TripCount % TripMultiple == 0); + + // Are we eliminating the loop control altogether? + bool CompletelyUnroll = Count == TripCount; + + // If we know the trip count, we know the multiple... + unsigned BreakoutTrip = 0; + if (TripCount != 0) { + BreakoutTrip = TripCount % Count; + TripMultiple = 0; + } else { + // Figure out what multiple to use. + BreakoutTrip = TripMultiple = + (unsigned)GreatestCommonDivisor64(Count, TripMultiple); + } + + if (CompletelyUnroll) { + DEBUG(errs() << "COMPLETELY UNROLLING loop %" << Header->getName() + << " with trip count " << TripCount << "!\n"); + } else { + DEBUG(errs() << "UNROLLING loop %" << Header->getName() + << " by " << Count); + if (TripMultiple == 0 || BreakoutTrip != TripMultiple) { + DEBUG(errs() << " with a breakout at trip " << BreakoutTrip); + } else if (TripMultiple != 1) { + DEBUG(errs() << " with " << TripMultiple << " trips per branch"); + } + DEBUG(errs() << "!\n"); + } + + std::vector LoopBlocks = L->getBlocks(); + + bool ContinueOnTrue = L->contains(BI->getSuccessor(0)); + BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue); + + // For the first iteration of the loop, we should use the precloned values for + // PHI nodes. Insert associations now. + typedef DenseMap ValueMapTy; + ValueMapTy LastValueMap; + std::vector OrigPHINode; + for (BasicBlock::iterator I = Header->begin(); isa(I); ++I) { + PHINode *PN = cast(I); + OrigPHINode.push_back(PN); + if (Instruction *I = + dyn_cast(PN->getIncomingValueForBlock(LatchBlock))) + if (L->contains(I->getParent())) + LastValueMap[I] = I; + } + + std::vector Headers; + std::vector Latches; + Headers.push_back(Header); + Latches.push_back(LatchBlock); + + for (unsigned It = 1; It != Count; ++It) { + char SuffixBuffer[100]; + sprintf(SuffixBuffer, ".%d", It); + + std::vector NewBlocks; + + for (std::vector::iterator BB = LoopBlocks.begin(), + E = LoopBlocks.end(); BB != E; ++BB) { + ValueMapTy ValueMap; + BasicBlock *New = CloneBasicBlock(*BB, ValueMap, SuffixBuffer); + Header->getParent()->getBasicBlockList().push_back(New); + + // Loop over all of the PHI nodes in the block, changing them to use the + // incoming values from the previous block. + if (*BB == Header) + for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) { + PHINode *NewPHI = cast(ValueMap[OrigPHINode[i]]); + Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock); + if (Instruction *InValI = dyn_cast(InVal)) + if (It > 1 && L->contains(InValI->getParent())) + InVal = LastValueMap[InValI]; + ValueMap[OrigPHINode[i]] = InVal; + New->getInstList().erase(NewPHI); + } + + // Update our running map of newest clones + LastValueMap[*BB] = New; + for (ValueMapTy::iterator VI = ValueMap.begin(), VE = ValueMap.end(); + VI != VE; ++VI) + LastValueMap[VI->first] = VI->second; + + L->addBasicBlockToLoop(New, LI->getBase()); + + // Add phi entries for newly created values to all exit blocks except + // the successor of the latch block. The successor of the exit block will + // be updated specially after unrolling all the way. + if (*BB != LatchBlock) + for (Value::use_iterator UI = (*BB)->use_begin(), UE = (*BB)->use_end(); + UI != UE;) { + Instruction *UseInst = cast(*UI); + ++UI; + if (isa(UseInst) && !L->contains(UseInst->getParent())) { + PHINode *phi = cast(UseInst); + Value *Incoming = phi->getIncomingValueForBlock(*BB); + phi->addIncoming(Incoming, New); + } + } + + // Keep track of new headers and latches as we create them, so that + // we can insert the proper branches later. + if (*BB == Header) + Headers.push_back(New); + if (*BB == LatchBlock) { + Latches.push_back(New); + + // Also, clear out the new latch's back edge so that it doesn't look + // like a new loop, so that it's amenable to being merged with adjacent + // blocks later on. + TerminatorInst *Term = New->getTerminator(); + assert(L->contains(Term->getSuccessor(!ContinueOnTrue))); + assert(Term->getSuccessor(ContinueOnTrue) == LoopExit); + Term->setSuccessor(!ContinueOnTrue, NULL); + } + + NewBlocks.push_back(New); + } + + // Remap all instructions in the most recent iteration + for (unsigned i = 0; i < NewBlocks.size(); ++i) + for (BasicBlock::iterator I = NewBlocks[i]->begin(), + E = NewBlocks[i]->end(); I != E; ++I) + RemapInstruction(I, LastValueMap); + } + + // The latch block exits the loop. If there are any PHI nodes in the + // successor blocks, update them to use the appropriate values computed as the + // last iteration of the loop. + if (Count != 1) { + SmallPtrSet Users; + for (Value::use_iterator UI = LatchBlock->use_begin(), + UE = LatchBlock->use_end(); UI != UE; ++UI) + if (PHINode *phi = dyn_cast(*UI)) + Users.insert(phi); + + BasicBlock *LastIterationBB = cast(LastValueMap[LatchBlock]); + for (SmallPtrSet::iterator SI = Users.begin(), SE = Users.end(); + SI != SE; ++SI) { + PHINode *PN = *SI; + Value *InVal = PN->removeIncomingValue(LatchBlock, false); + // If this value was defined in the loop, take the value defined by the + // last iteration of the loop. + if (Instruction *InValI = dyn_cast(InVal)) { + if (L->contains(InValI->getParent())) + InVal = LastValueMap[InVal]; + } + PN->addIncoming(InVal, LastIterationBB); + } + } + + // Now, if we're doing complete unrolling, loop over the PHI nodes in the + // original block, setting them to their incoming values. + if (CompletelyUnroll) { + BasicBlock *Preheader = L->getLoopPreheader(); + for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) { + PHINode *PN = OrigPHINode[i]; + PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader)); + Header->getInstList().erase(PN); + } + } + + // Now that all the basic blocks for the unrolled iterations are in place, + // set up the branches to connect them. + for (unsigned i = 0, e = Latches.size(); i != e; ++i) { + // The original branch was replicated in each unrolled iteration. + BranchInst *Term = cast(Latches[i]->getTerminator()); + + // The branch destination. + unsigned j = (i + 1) % e; + BasicBlock *Dest = Headers[j]; + bool NeedConditional = true; + + // For a complete unroll, make the last iteration end with a branch + // to the exit block. + if (CompletelyUnroll && j == 0) { + Dest = LoopExit; + NeedConditional = false; + } + + // If we know the trip count or a multiple of it, we can safely use an + // unconditional branch for some iterations. + if (j != BreakoutTrip && (TripMultiple == 0 || j % TripMultiple != 0)) { + NeedConditional = false; + } + + if (NeedConditional) { + // Update the conditional branch's successor for the following + // iteration. + Term->setSuccessor(!ContinueOnTrue, Dest); + } else { + Term->setUnconditionalDest(Dest); + // Merge adjacent basic blocks, if possible. + if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI)) { + std::replace(Latches.begin(), Latches.end(), Dest, Fold); + std::replace(Headers.begin(), Headers.end(), Dest, Fold); + } + } + } + + // At this point, the code is well formed. We now do a quick sweep over the + // inserted code, doing constant propagation and dead code elimination as we + // go. + const std::vector &NewLoopBlocks = L->getBlocks(); + for (std::vector::const_iterator BB = NewLoopBlocks.begin(), + BBE = NewLoopBlocks.end(); BB != BBE; ++BB) + for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ) { + Instruction *Inst = I++; + + if (isInstructionTriviallyDead(Inst)) + (*BB)->getInstList().erase(Inst); + else if (Constant *C = ConstantFoldInstruction(Inst, + Header->getContext())) { + Inst->replaceAllUsesWith(C); + (*BB)->getInstList().erase(Inst); + } + } + + NumCompletelyUnrolled += CompletelyUnroll; + ++NumUnrolled; + // Remove the loop from the LoopPassManager if it's completely removed. + if (CompletelyUnroll && LPM != NULL) + LPM->deleteLoopFromQueue(L); + + // If we didn't completely unroll the loop, it should still be in LCSSA form. + if (!CompletelyUnroll) + assert(L->isLCSSAForm()); + + return true; +} diff --git a/lib/Transforms/Utils/UnrollLoop.cpp b/lib/Transforms/Utils/UnrollLoop.cpp deleted file mode 100644 index 4d838b50e3..0000000000 --- a/lib/Transforms/Utils/UnrollLoop.cpp +++ /dev/null @@ -1,372 +0,0 @@ -//===-- UnrollLoop.cpp - Loop unrolling utilities -------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements some loop unrolling utilities. It does not define any -// actual pass or policy, but provides a single function to perform loop -// unrolling. -// -// It works best when loops have been canonicalized by the -indvars pass, -// allowing it to determine the trip counts of loops easily. -// -// The process of unrolling can produce extraneous basic blocks linked with -// unconditional branches. This will be corrected in the future. -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "loop-unroll" -#include "llvm/Transforms/Utils/UnrollLoop.h" -#include "llvm/BasicBlock.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/ConstantFolding.h" -#include "llvm/Analysis/LoopPass.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Transforms/Utils/Cloning.h" -#include "llvm/Transforms/Utils/Local.h" -#include - -using namespace llvm; - -// TODO: Should these be here or in LoopUnroll? -STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled"); -STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)"); - -/// RemapInstruction - Convert the instruction operands from referencing the -/// current values into those specified by ValueMap. -static inline void RemapInstruction(Instruction *I, - DenseMap &ValueMap) { - for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) { - Value *Op = I->getOperand(op); - DenseMap::iterator It = ValueMap.find(Op); - if (It != ValueMap.end()) Op = It->second; - I->setOperand(op, Op); - } -} - -/// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it -/// only has one predecessor, and that predecessor only has one successor. -/// The LoopInfo Analysis that is passed will be kept consistent. -/// Returns the new combined block. -static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) { - // Merge basic blocks into their predecessor if there is only one distinct - // pred, and if there is only one distinct successor of the predecessor, and - // if there are no PHI nodes. - BasicBlock *OnlyPred = BB->getSinglePredecessor(); - if (!OnlyPred) return 0; - - if (OnlyPred->getTerminator()->getNumSuccessors() != 1) - return 0; - - DEBUG(errs() << "Merging: " << *BB << "into: " << *OnlyPred); - - // Resolve any PHI nodes at the start of the block. They are all - // guaranteed to have exactly one entry if they exist, unless there are - // multiple duplicate (but guaranteed to be equal) entries for the - // incoming edges. This occurs when there are multiple edges from - // OnlyPred to OnlySucc. - FoldSingleEntryPHINodes(BB); - - // Delete the unconditional branch from the predecessor... - OnlyPred->getInstList().pop_back(); - - // Move all definitions in the successor to the predecessor... - OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); - - // Make all PHI nodes that referred to BB now refer to Pred as their - // source... - BB->replaceAllUsesWith(OnlyPred); - - std::string OldName = BB->getName(); - - // Erase basic block from the function... - LI->removeBlock(BB); - BB->eraseFromParent(); - - // Inherit predecessor's name if it exists... - if (!OldName.empty() && !OnlyPred->hasName()) - OnlyPred->setName(OldName); - - return OnlyPred; -} - -/// Unroll the given loop by Count. The loop must be in LCSSA form. Returns true -/// if unrolling was succesful, or false if the loop was unmodified. Unrolling -/// can only fail when the loop's latch block is not terminated by a conditional -/// branch instruction. However, if the trip count (and multiple) are not known, -/// loop unrolling will mostly produce more code that is no faster. -/// -/// The LoopInfo Analysis that is passed will be kept consistent. -/// -/// If a LoopPassManager is passed in, and the loop is fully removed, it will be -/// removed from the LoopPassManager as well. LPM can also be NULL. -bool llvm::UnrollLoop(Loop *L, unsigned Count, LoopInfo* LI, LPPassManager* LPM) { - assert(L->isLCSSAForm()); - - BasicBlock *Header = L->getHeader(); - BasicBlock *LatchBlock = L->getLoopLatch(); - BranchInst *BI = dyn_cast(LatchBlock->getTerminator()); - - if (!BI || BI->isUnconditional()) { - // The loop-rotate pass can be helpful to avoid this in many cases. - DEBUG(errs() << - " Can't unroll; loop not terminated by a conditional branch.\n"); - return false; - } - - // Find trip count - unsigned TripCount = L->getSmallConstantTripCount(); - // Find trip multiple if count is not available - unsigned TripMultiple = 1; - if (TripCount == 0) - TripMultiple = L->getSmallConstantTripMultiple(); - - if (TripCount != 0) - DEBUG(errs() << " Trip Count = " << TripCount << "\n"); - if (TripMultiple != 1) - DEBUG(errs() << " Trip Multiple = " << TripMultiple << "\n"); - - // Effectively "DCE" unrolled iterations that are beyond the tripcount - // and will never be executed. - if (TripCount != 0 && Count > TripCount) - Count = TripCount; - - assert(Count > 0); - assert(TripMultiple > 0); - assert(TripCount == 0 || TripCount % TripMultiple == 0); - - // Are we eliminating the loop control altogether? - bool CompletelyUnroll = Count == TripCount; - - // If we know the trip count, we know the multiple... - unsigned BreakoutTrip = 0; - if (TripCount != 0) { - BreakoutTrip = TripCount % Count; - TripMultiple = 0; - } else { - // Figure out what multiple to use. - BreakoutTrip = TripMultiple = - (unsigned)GreatestCommonDivisor64(Count, TripMultiple); - } - - if (CompletelyUnroll) { - DEBUG(errs() << "COMPLETELY UNROLLING loop %" << Header->getName() - << " with trip count " << TripCount << "!\n"); - } else { - DEBUG(errs() << "UNROLLING loop %" << Header->getName() - << " by " << Count); - if (TripMultiple == 0 || BreakoutTrip != TripMultiple) { - DEBUG(errs() << " with a breakout at trip " << BreakoutTrip); - } else if (TripMultiple != 1) { - DEBUG(errs() << " with " << TripMultiple << " trips per branch"); - } - DEBUG(errs() << "!\n"); - } - - std::vector LoopBlocks = L->getBlocks(); - - bool ContinueOnTrue = L->contains(BI->getSuccessor(0)); - BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue); - - // For the first iteration of the loop, we should use the precloned values for - // PHI nodes. Insert associations now. - typedef DenseMap ValueMapTy; - ValueMapTy LastValueMap; - std::vector OrigPHINode; - for (BasicBlock::iterator I = Header->begin(); isa(I); ++I) { - PHINode *PN = cast(I); - OrigPHINode.push_back(PN); - if (Instruction *I = - dyn_cast(PN->getIncomingValueForBlock(LatchBlock))) - if (L->contains(I->getParent())) - LastValueMap[I] = I; - } - - std::vector Headers; - std::vector Latches; - Headers.push_back(Header); - Latches.push_back(LatchBlock); - - for (unsigned It = 1; It != Count; ++It) { - char SuffixBuffer[100]; - sprintf(SuffixBuffer, ".%d", It); - - std::vector NewBlocks; - - for (std::vector::iterator BB = LoopBlocks.begin(), - E = LoopBlocks.end(); BB != E; ++BB) { - ValueMapTy ValueMap; - BasicBlock *New = CloneBasicBlock(*BB, ValueMap, SuffixBuffer); - Header->getParent()->getBasicBlockList().push_back(New); - - // Loop over all of the PHI nodes in the block, changing them to use the - // incoming values from the previous block. - if (*BB == Header) - for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) { - PHINode *NewPHI = cast(ValueMap[OrigPHINode[i]]); - Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock); - if (Instruction *InValI = dyn_cast(InVal)) - if (It > 1 && L->contains(InValI->getParent())) - InVal = LastValueMap[InValI]; - ValueMap[OrigPHINode[i]] = InVal; - New->getInstList().erase(NewPHI); - } - - // Update our running map of newest clones - LastValueMap[*BB] = New; - for (ValueMapTy::iterator VI = ValueMap.begin(), VE = ValueMap.end(); - VI != VE; ++VI) - LastValueMap[VI->first] = VI->second; - - L->addBasicBlockToLoop(New, LI->getBase()); - - // Add phi entries for newly created values to all exit blocks except - // the successor of the latch block. The successor of the exit block will - // be updated specially after unrolling all the way. - if (*BB != LatchBlock) - for (Value::use_iterator UI = (*BB)->use_begin(), UE = (*BB)->use_end(); - UI != UE;) { - Instruction *UseInst = cast(*UI); - ++UI; - if (isa(UseInst) && !L->contains(UseInst->getParent())) { - PHINode *phi = cast(UseInst); - Value *Incoming = phi->getIncomingValueForBlock(*BB); - phi->addIncoming(Incoming, New); - } - } - - // Keep track of new headers and latches as we create them, so that - // we can insert the proper branches later. - if (*BB == Header) - Headers.push_back(New); - if (*BB == LatchBlock) { - Latches.push_back(New); - - // Also, clear out the new latch's back edge so that it doesn't look - // like a new loop, so that it's amenable to being merged with adjacent - // blocks later on. - TerminatorInst *Term = New->getTerminator(); - assert(L->contains(Term->getSuccessor(!ContinueOnTrue))); - assert(Term->getSuccessor(ContinueOnTrue) == LoopExit); - Term->setSuccessor(!ContinueOnTrue, NULL); - } - - NewBlocks.push_back(New); - } - - // Remap all instructions in the most recent iteration - for (unsigned i = 0; i < NewBlocks.size(); ++i) - for (BasicBlock::iterator I = NewBlocks[i]->begin(), - E = NewBlocks[i]->end(); I != E; ++I) - RemapInstruction(I, LastValueMap); - } - - // The latch block exits the loop. If there are any PHI nodes in the - // successor blocks, update them to use the appropriate values computed as the - // last iteration of the loop. - if (Count != 1) { - SmallPtrSet Users; - for (Value::use_iterator UI = LatchBlock->use_begin(), - UE = LatchBlock->use_end(); UI != UE; ++UI) - if (PHINode *phi = dyn_cast(*UI)) - Users.insert(phi); - - BasicBlock *LastIterationBB = cast(LastValueMap[LatchBlock]); - for (SmallPtrSet::iterator SI = Users.begin(), SE = Users.end(); - SI != SE; ++SI) { - PHINode *PN = *SI; - Value *InVal = PN->removeIncomingValue(LatchBlock, false); - // If this value was defined in the loop, take the value defined by the - // last iteration of the loop. - if (Instruction *InValI = dyn_cast(InVal)) { - if (L->contains(InValI->getParent())) - InVal = LastValueMap[InVal]; - } - PN->addIncoming(InVal, LastIterationBB); - } - } - - // Now, if we're doing complete unrolling, loop over the PHI nodes in the - // original block, setting them to their incoming values. - if (CompletelyUnroll) { - BasicBlock *Preheader = L->getLoopPreheader(); - for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) { - PHINode *PN = OrigPHINode[i]; - PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader)); - Header->getInstList().erase(PN); - } - } - - // Now that all the basic blocks for the unrolled iterations are in place, - // set up the branches to connect them. - for (unsigned i = 0, e = Latches.size(); i != e; ++i) { - // The original branch was replicated in each unrolled iteration. - BranchInst *Term = cast(Latches[i]->getTerminator()); - - // The branch destination. - unsigned j = (i + 1) % e; - BasicBlock *Dest = Headers[j]; - bool NeedConditional = true; - - // For a complete unroll, make the last iteration end with a branch - // to the exit block. - if (CompletelyUnroll && j == 0) { - Dest = LoopExit; - NeedConditional = false; - } - - // If we know the trip count or a multiple of it, we can safely use an - // unconditional branch for some iterations. - if (j != BreakoutTrip && (TripMultiple == 0 || j % TripMultiple != 0)) { - NeedConditional = false; - } - - if (NeedConditional) { - // Update the conditional branch's successor for the following - // iteration. - Term->setSuccessor(!ContinueOnTrue, Dest); - } else { - Term->setUnconditionalDest(Dest); - // Merge adjacent basic blocks, if possible. - if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI)) { - std::replace(Latches.begin(), Latches.end(), Dest, Fold); - std::replace(Headers.begin(), Headers.end(), Dest, Fold); - } - } - } - - // At this point, the code is well formed. We now do a quick sweep over the - // inserted code, doing constant propagation and dead code elimination as we - // go. - const std::vector &NewLoopBlocks = L->getBlocks(); - for (std::vector::const_iterator BB = NewLoopBlocks.begin(), - BBE = NewLoopBlocks.end(); BB != BBE; ++BB) - for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ) { - Instruction *Inst = I++; - - if (isInstructionTriviallyDead(Inst)) - (*BB)->getInstList().erase(Inst); - else if (Constant *C = ConstantFoldInstruction(Inst, - Header->getContext())) { - Inst->replaceAllUsesWith(C); - (*BB)->getInstList().erase(Inst); - } - } - - NumCompletelyUnrolled += CompletelyUnroll; - ++NumUnrolled; - // Remove the loop from the LoopPassManager if it's completely removed. - if (CompletelyUnroll && LPM != NULL) - LPM->deleteLoopFromQueue(L); - - // If we didn't completely unroll the loop, it should still be in LCSSA form. - if (!CompletelyUnroll) - assert(L->isLCSSAForm()); - - return true; -} -- cgit v1.2.3