From 8fc5ad33691b2a0672a7487da1f56b6f7f675a1b Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Thu, 3 Sep 2009 16:31:42 +0000 Subject: [PATCH] Add a verifyAnalysis to LoopInfo, LoopSimplify, and LCSSA form that verify that these passes are properly preserved. Fix several transformation passes that claimed to preserve LoopSimplify form but weren't. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@80926 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LoopInfo.h | 72 +++++++++++++- .../llvm/Transforms/Utils/BasicBlockUtils.h | 21 ++-- lib/Analysis/LoopInfo.cpp | 10 ++ lib/Transforms/Scalar/LICM.cpp | 1 + lib/Transforms/Scalar/LoopStrengthReduce.cpp | 15 +-- lib/Transforms/Scalar/LoopUnswitch.cpp | 95 +++++++------------ lib/Transforms/Utils/BasicBlockUtils.cpp | 92 +++++++++++++----- lib/Transforms/Utils/BreakCriticalEdges.cpp | 65 +++++++++++-- lib/Transforms/Utils/LCSSA.cpp | 19 +++- lib/Transforms/Utils/LoopSimplify.cpp | 40 +++----- 10 files changed, 287 insertions(+), 143 deletions(-) diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index b803176d889..1892bc78ae7 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -376,11 +376,73 @@ public: /// verifyLoop - Verify loop structure void verifyLoop() const { #ifndef NDEBUG - assert (getHeader() && "Loop header is missing"); - assert (getLoopPreheader() && "Loop preheader is missing"); - assert (getLoopLatch() && "Loop latch is missing"); - for (iterator I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I) + assert(!Blocks.empty() && "Loop header is missing"); + assert(getHeader() && "Loop header is missing"); + + // Verify the individual blocks. + for (block_iterator I = block_begin(), E = block_end(); I != E; ++I) { + BlockT *BB = *I; + bool HasInsideLoopSuccs = false; + bool HasInsideLoopPreds = false; + SmallVector OutsideLoopPreds; + + typedef GraphTraits BlockTraits; + for (typename BlockTraits::ChildIteratorType SI = + BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB); + SI != SE; ++SI) + if (contains(*SI)) + HasInsideLoopSuccs = true; + typedef GraphTraits > InvBlockTraits; + for (typename InvBlockTraits::ChildIteratorType PI = + InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB); + PI != PE; ++PI) { + if (contains(*PI)) + HasInsideLoopPreds = true; + else + OutsideLoopPreds.push_back(*PI); + } + + if (BB == getHeader()) { + assert(!OutsideLoopPreds.empty() && "Loop is unreachable!"); + } else if (!OutsideLoopPreds.empty()) { + // A non-header loop shouldn't be reachable from outside the loop, + // though it is permitted if the predecessor is not itself actually + // reachable. + BlockT *EntryBB = BB->getParent()->begin(); + for (df_iterator NI = df_begin(EntryBB), + NE = df_end(EntryBB); NI != NE; ++NI) + for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i) + assert(*NI != OutsideLoopPreds[i] && + "Loop has multiple entry points!"); + } + assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!"); + assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!"); + assert(BB != getHeader()->getParent()->begin() && + "Loop contains function entry block!"); + } + + // Verify the subloops. + for (iterator I = begin(), E = end(); I != E; ++I) { + // Each block in each subloop should be contained within this loop. + for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end(); + BI != BE; ++BI) { + assert(contains(*BI) && + "Loop does not contain all the blocks of a subloop!"); + } + // Recursively check the subloop. (*I)->verifyLoop(); + } + + // Verify the parent loop. + if (ParentLoop) { + bool FoundSelf = false; + for (iterator I = ParentLoop->begin(), E = ParentLoop->end(); I != E; ++I) + if (*I == this) { + FoundSelf = true; + break; + } + assert(FoundSelf && "Loop is not a subloop of its parent!"); + } #endif } @@ -873,6 +935,8 @@ public: /// virtual bool runOnFunction(Function &F); + virtual void verifyAnalysis() const; + virtual void releaseMemory() { LI.releaseMemory(); } virtual void print(raw_ostream &O, const Module* M = 0) const; diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 95ffa460696..e766d729e1b 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -126,10 +126,10 @@ bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, /// dest go to one block instead of each going to a different block, but isn't /// the standard definition of a "critical edge". /// -bool SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P = 0, - bool MergeIdenticalEdges = false); +BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, + Pass *P = 0, bool MergeIdenticalEdges = false); -inline bool SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) { +inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) { return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), P); } @@ -143,7 +143,7 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) { TerminatorInst *TI = (*PI)->getTerminator(); for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) if (TI->getSuccessor(i) == Succ) - MadeChange |= SplitCriticalEdge(TI, i, P); + MadeChange |= !!SplitCriticalEdge(TI, i, P); return MadeChange; } @@ -151,8 +151,9 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) { /// and return true, otherwise return false. This method requires that there be /// an edge between the two blocks. If P is specified, it updates the analyses /// described above. -inline bool SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, Pass *P = 0, - bool MergeIdenticalEdges = false) { +inline BasicBlock *SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, + Pass *P = 0, + bool MergeIdenticalEdges = false) { TerminatorInst *TI = Src->getTerminator(); unsigned i = 0; while (1) { @@ -180,8 +181,12 @@ BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P); /// Preds array, which has NumPreds elements in it. The new block is given a /// suffix of 'Suffix'. This function returns the new block. /// -/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and -/// DominanceFrontier, but no other analyses. +/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, +/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. +/// In particular, it does not preserve LoopSimplify (because it's +/// complicated to handle the case where one of the edges being split +/// is an exit of a loop with other exits). +/// BasicBlock *SplitBlockPredecessors(BasicBlock *BB, BasicBlock *const *Preds, unsigned NumPreds, const char *Suffix, Pass *P = 0); diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index 4245702ea10..94dc1541134 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -300,6 +300,9 @@ bool Loop::isLoopSimplifyForm() const { /// void Loop::getUniqueExitBlocks(SmallVectorImpl &ExitBlocks) const { + assert(isLoopSimplifyForm() && + "getUniqueExitBlocks assumes the loop is in canonical form!"); + // Sort the blocks vector so that we can use binary search to do quick // lookups. SmallVector LoopBBs(block_begin(), block_end()); @@ -371,6 +374,13 @@ bool LoopInfo::runOnFunction(Function &) { return false; } +void LoopInfo::verifyAnalysis() const { + for (iterator I = begin(), E = end(); I != E; ++I) { + assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); + (*I)->verifyLoop(); + } +} + void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired(); diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp index 15bb9c70dfe..1c298785da8 100644 --- a/lib/Transforms/Scalar/LICM.cpp +++ b/lib/Transforms/Scalar/LICM.cpp @@ -91,6 +91,7 @@ namespace { AU.addRequired(); AU.addPreserved(); AU.addPreserved(); + AU.addPreservedID(LoopSimplifyID); } bool doFinalization() { diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 0bf62ec9064..82eb14fb2ae 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -484,36 +484,37 @@ void BasedUser::RewriteInstructionToUseNewBase(const SCEV *const &NewBase, // loop because multiple copies sometimes do useful sinking of code in // that case(?). Instruction *OldLoc = dyn_cast(OperandValToReplace); + BasicBlock *PHIPred = PN->getIncomingBlock(i); if (L->contains(OldLoc->getParent())) { // If this is a critical edge, split the edge so that we do not insert // the code on all predecessor/successor paths. We do this unless this // is the canonical backedge for this loop, as this can make some // inserted code be in an illegal position. - BasicBlock *PHIPred = PN->getIncomingBlock(i); if (e != 1 && PHIPred->getTerminator()->getNumSuccessors() > 1 && (PN->getParent() != L->getHeader() || !L->contains(PHIPred))) { // First step, split the critical edge. - SplitCriticalEdge(PHIPred, PN->getParent(), P, false); + BasicBlock *NewBB = SplitCriticalEdge(PHIPred, PN->getParent(), + P, false); // Next step: move the basic block. In particular, if the PHI node // is outside of the loop, and PredTI is in the loop, we want to // move the block to be immediately before the PHI block, not // immediately after PredTI. - if (L->contains(PHIPred) && !L->contains(PN->getParent())) { - BasicBlock *NewBB = PN->getIncomingBlock(i); + if (L->contains(PHIPred) && !L->contains(PN->getParent())) NewBB->moveBefore(PN->getParent()); - } // Splitting the edge can reduce the number of PHI entries we have. e = PN->getNumIncomingValues(); + PHIPred = NewBB; + i = PN->getBasicBlockIndex(PHIPred); } } - Value *&Code = InsertedCode[PN->getIncomingBlock(i)]; + Value *&Code = InsertedCode[PHIPred]; if (!Code) { // Insert the code into the end of the predecessor block. Instruction *InsertPt = (L->contains(OldLoc->getParent())) ? - PN->getIncomingBlock(i)->getTerminator() : + PHIPred->getTerminator() : OldLoc->getParent()->getTerminator(); Code = InsertCodeForBaseAtPosition(NewBase, PN->getType(), Rewriter, InsertPt, L, LI); diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp index 8e7c91a3f28..b49e14a810d 100644 --- a/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -518,7 +518,12 @@ void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, std::swap(TrueDest, FalseDest); // Insert the new branch. - BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt); + BranchInst *BI = BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt); + + // If either edge is critical, split it. This helps preserve LoopSimplify + // form for enclosing loops. + SplitCriticalEdge(BI, 0, this); + SplitCriticalEdge(BI, 1, this); } /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable @@ -575,47 +580,11 @@ void LoopUnswitch::SplitExitEdges(Loop *L, for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { BasicBlock *ExitBlock = ExitBlocks[i]; - std::vector Preds(pred_begin(ExitBlock), pred_end(ExitBlock)); - - for (unsigned j = 0, e = Preds.size(); j != e; ++j) { - BasicBlock* NewExitBlock = SplitEdge(Preds[j], ExitBlock, this); - BasicBlock* StartBlock = Preds[j]; - BasicBlock* EndBlock; - if (NewExitBlock->getSinglePredecessor() == ExitBlock) { - EndBlock = NewExitBlock; - NewExitBlock = EndBlock->getSinglePredecessor(); - } else { - EndBlock = ExitBlock; - } - - std::set InsertedPHIs; - PHINode* OldLCSSA = 0; - for (BasicBlock::iterator I = EndBlock->begin(); - (OldLCSSA = dyn_cast(I)); ++I) { - Value* OldValue = OldLCSSA->getIncomingValueForBlock(NewExitBlock); - PHINode* NewLCSSA = PHINode::Create(OldLCSSA->getType(), - OldLCSSA->getName() + ".us-lcssa", - NewExitBlock->getTerminator()); - NewLCSSA->addIncoming(OldValue, StartBlock); - OldLCSSA->setIncomingValue(OldLCSSA->getBasicBlockIndex(NewExitBlock), - NewLCSSA); - InsertedPHIs.insert(NewLCSSA); - } - - BasicBlock::iterator InsertPt = EndBlock->getFirstNonPHI(); - for (BasicBlock::iterator I = NewExitBlock->begin(); - (OldLCSSA = dyn_cast(I)) && InsertedPHIs.count(OldLCSSA) == 0; - ++I) { - PHINode *NewLCSSA = PHINode::Create(OldLCSSA->getType(), - OldLCSSA->getName() + ".us-lcssa", - InsertPt); - OldLCSSA->replaceAllUsesWith(NewLCSSA); - NewLCSSA->addIncoming(OldLCSSA, NewExitBlock); - } - - } + SmallVector Preds(pred_begin(ExitBlock), + pred_end(ExitBlock)); + SplitBlockPredecessors(ExitBlock, Preds.data(), Preds.size(), + ".us-lcssa", this); } - } /// UnswitchNontrivialCondition - We determined that the loop is profitable @@ -945,27 +914,29 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, // FIXME: This is a hack. We need to keep the successor around // and hooked up so as to preserve the loop structure, because // trying to update it is complicated. So instead we preserve the - // loop structure and put the block on an dead code path. - - BasicBlock *SISucc = SI->getSuccessor(i); - BasicBlock* Old = SI->getParent(); - BasicBlock* Split = SplitBlock(Old, SI, this); - - Instruction* OldTerm = Old->getTerminator(); - BranchInst::Create(Split, SISucc, - ConstantInt::getTrue(Context), OldTerm); - - LPM->deleteSimpleAnalysisValue(Old->getTerminator(), L); - Old->getTerminator()->eraseFromParent(); - - PHINode *PN; - for (BasicBlock::iterator II = SISucc->begin(); - (PN = dyn_cast(II)); ++II) { - Value *InVal = PN->removeIncomingValue(Split, false); - PN->addIncoming(InVal, Old); - } - - SI->removeCase(i); + // loop structure and put the block on a dead code path. + BasicBlock *Switch = SI->getParent(); + SplitEdge(Switch, SI->getSuccessor(i), this); + // Compute the successors instead of relying on the return value + // of SplitEdge, since it may have split the switch successor + // after PHI nodes. + BasicBlock *NewSISucc = SI->getSuccessor(i); + BasicBlock *OldSISucc = *succ_begin(NewSISucc); + // Create an "unreachable" destination. + BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable", + Switch->getParent(), + OldSISucc); + new UnreachableInst(Context, Abort); + // Force the new case destination to branch to the "unreachable" + // block while maintaining a (dead) CFG edge to the old block. + NewSISucc->getTerminator()->eraseFromParent(); + BranchInst::Create(Abort, OldSISucc, + ConstantInt::getTrue(Context), NewSISucc); + // Release the PHI operands for this edge. + for (BasicBlock::iterator II = NewSISucc->begin(); + PHINode *PN = dyn_cast(II); ++II) + PN->setIncomingValue(PN->getBasicBlockIndex(Switch), + UndefValue::get(PN->getType())); break; } } diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp index c165e04fb8a..736d26e75fb 100644 --- a/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -24,6 +24,7 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Target/TargetData.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/ValueHandle.h" #include @@ -319,7 +320,8 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) { ++SplitIt; BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split"); - // The new block lives in whichever loop the old one did. + // The new block lives in whichever loop the old one did. This preserves + // LCSSA as well, because we force the split point to be after any PHI nodes. if (LoopInfo* LI = P->getAnalysisIfAvailable()) if (Loop *L = LI->getLoopFor(Old)) L->addBasicBlockToLoop(New, LI->getBase()); @@ -353,8 +355,12 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) { /// Preds array, which has NumPreds elements in it. The new block is given a /// suffix of 'Suffix'. /// -/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and -/// DominanceFrontier, but no other analyses. +/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, +/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. +/// In particular, it does not preserve LoopSimplify (because it's +/// complicated to handle the case where one of the edges being split +/// is an exit of a loop with other exits). +/// BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, BasicBlock *const *Preds, unsigned NumPreds, const char *Suffix, @@ -366,19 +372,44 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, // The new block unconditionally branches to the old block. BranchInst *BI = BranchInst::Create(BB, NewBB); + LoopInfo *LI = P ? P->getAnalysisIfAvailable() : 0; + Loop *L = LI ? LI->getLoopFor(BB) : 0; + bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID); + // Move the edges from Preds to point to NewBB instead of BB. - for (unsigned i = 0; i != NumPreds; ++i) + // While here, if we need to preserve loop analyses, collect + // some information about how this split will affect loops. + bool HasLoopExit = false; + bool IsLoopEntry = !!L; + bool SplitMakesNewLoopHeader = false; + for (unsigned i = 0; i != NumPreds; ++i) { Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB); - + + if (LI) { + // If we need to preserve LCSSA, determine if any of + // the preds is a loop exit. + if (PreserveLCSSA) + if (Loop *PL = LI->getLoopFor(Preds[i])) + if (!PL->contains(BB)) + HasLoopExit = true; + // If we need to preserve LoopInfo, note whether any of the + // preds crosses an interesting loop boundary. + if (L) { + if (L->contains(Preds[i])) + IsLoopEntry = false; + else + SplitMakesNewLoopHeader = true; + } + } + } + // Update dominator tree and dominator frontier if available. DominatorTree *DT = P ? P->getAnalysisIfAvailable() : 0; if (DT) DT->splitBlock(NewBB); if (DominanceFrontier *DF = P ? P->getAnalysisIfAvailable():0) DF->splitBlock(NewBB); - AliasAnalysis *AA = P ? P->getAnalysisIfAvailable() : 0; - - + // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI // node becomes an incoming value for BB's phi node. However, if the Preds // list is empty, we need to insert dummy entries into the PHI nodes in BB to @@ -389,20 +420,42 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, cast(I)->addIncoming(UndefValue::get(I->getType()), NewBB); return NewBB; } + + AliasAnalysis *AA = P ? P->getAnalysisIfAvailable() : 0; + + if (L) { + if (IsLoopEntry) { + if (Loop *PredLoop = LI->getLoopFor(Preds[0])) { + // Add the new block to the nearest enclosing loop (and not an + // adjacent loop). + while (PredLoop && !PredLoop->contains(BB)) + PredLoop = PredLoop->getParentLoop(); + if (PredLoop) + PredLoop->addBasicBlockToLoop(NewBB, LI->getBase()); + } + } else { + L->addBasicBlockToLoop(NewBB, LI->getBase()); + if (SplitMakesNewLoopHeader) + L->moveToHeader(NewBB); + } + } // Otherwise, create a new PHI node in NewBB for each PHI node in BB. for (BasicBlock::iterator I = BB->begin(); isa(I); ) { PHINode *PN = cast(I++); // Check to see if all of the values coming in are the same. If so, we - // don't need to create a new PHI node. - Value *InVal = PN->getIncomingValueForBlock(Preds[0]); - for (unsigned i = 1; i != NumPreds; ++i) - if (InVal != PN->getIncomingValueForBlock(Preds[i])) { - InVal = 0; - break; - } - + // don't need to create a new PHI node, unless it's needed for LCSSA. + Value *InVal = 0; + if (!HasLoopExit) { + InVal = PN->getIncomingValueForBlock(Preds[0]); + for (unsigned i = 1; i != NumPreds; ++i) + if (InVal != PN->getIncomingValueForBlock(Preds[i])) { + InVal = 0; + break; + } + } + if (InVal) { // If all incoming values for the new PHI would be the same, just don't // make a new PHI. Instead, just remove the incoming values from the old @@ -427,13 +480,6 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, // Add an incoming value to the PHI node in the loop for the preheader // edge. PN->addIncoming(InVal, NewBB); - - // Check to see if we can eliminate this phi node. - if (Value *V = PN->hasConstantValue(DT)) { - PN->replaceAllUsesWith(V); - if (AA) AA->deleteValue(PN); - PN->eraseFromParent(); - } } return NewBB; diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp index 632aa2b723b..f5a136661f5 100644 --- a/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -122,9 +122,9 @@ bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, /// false otherwise. This ensures that all edges to that dest go to one block /// instead of each going to a different block. // -bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P, - bool MergeIdenticalEdges) { - if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return false; +BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, + Pass *P, bool MergeIdenticalEdges) { + if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0; BasicBlock *TIBB = TI->getParent(); BasicBlock *DestBB = TI->getSuccessor(SuccNum); @@ -172,7 +172,7 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P, // If we don't have a pass object, we can't update anything... - if (P == 0) return true; + if (P == 0) return NewBB; // Now update analysis information. Since the only predecessor of NewBB is // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate @@ -254,9 +254,9 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P, // Update LoopInfo if it is around. if (LoopInfo *LI = P->getAnalysisIfAvailable()) { - // If one or the other blocks were not in a loop, the new block is not - // either, and thus LI doesn't need to be updated. - if (Loop *TIL = LI->getLoopFor(TIBB)) + if (Loop *TIL = LI->getLoopFor(TIBB)) { + // If one or the other blocks were not in a loop, the new block is not + // either, and thus LI doesn't need to be updated. if (Loop *DestLoop = LI->getLoopFor(DestBB)) { if (TIL == DestLoop) { // Both in the same loop, the NewBB joins loop. @@ -278,6 +278,55 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P, P->addBasicBlockToLoop(NewBB, LI->getBase()); } } + // If TIBB is in a loop and DestBB is outside of that loop, split the + // other exit blocks of the loop that also have predecessors outside + // the loop, to maintain a LoopSimplify guarantee. + if (!TIL->contains(DestBB) && + P->mustPreserveAnalysisID(LoopSimplifyID)) { + // For each unique exit block... + SmallVector ExitBlocks; + TIL->getExitBlocks(ExitBlocks); + for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { + // Collect all the preds that are inside the loop, and note + // whether there are any preds outside the loop. + SmallVector Preds; + bool AllPredsInLoop = false; + BasicBlock *Exit = ExitBlocks[i]; + for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); + I != E; ++I) + if (TIL->contains(*I)) + Preds.push_back(*I); + else + AllPredsInLoop = true; + // If there are any preds not in the loop, we'll need to split + // the edges. The Preds.empty() check is needed because a block + // may appear multiple times in the list. We can't use + // getUniqueExitBlocks above because that depends on LoopSimplify + // form, which we're in the process of restoring! + if (Preds.empty() || !AllPredsInLoop) continue; + BasicBlock *NewBB = SplitBlockPredecessors(Exit, + Preds.data(), Preds.size(), + "split", P); + // Update LCSSA form. This is fairly simple in LoopSimplify form: + // just move the existing LCSSA-mandated PHI nodes from the old exit + // block to the new one. + if (P->mustPreserveAnalysisID(LCSSAID)) + for (BasicBlock::iterator I = Exit->begin(); + PHINode *PN = dyn_cast(I); ++I) + PN->moveBefore(NewBB->getTerminator()); + } + } + // LCSSA form was updated above for the case where LoopSimplify is + // available, which means that all predecessors of loop exit blocks + // are within the loop. Without LoopSimplify form, it would be + // necessary to insert a new phi. + assert((!P->mustPreserveAnalysisID(LCSSAID) || + P->mustPreserveAnalysisID(LoopSimplifyID)) && + "SplitCriticalEdge doesn't know how to update LCCSA form " + "without LoopSimplify!"); + } + } - return true; + + return NewBB; } diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp index 84fcc643bfb..e0251f83808 100644 --- a/lib/Transforms/Utils/LCSSA.cpp +++ b/lib/Transforms/Utils/LCSSA.cpp @@ -58,6 +58,7 @@ namespace { DominatorTree *DT; std::vector LoopBlocks; PredIteratorCache PredCache; + Loop *L; virtual bool runOnLoop(Loop *L, LPPassManager &LPM); @@ -72,9 +73,9 @@ namespace { AU.setPreservesCFG(); AU.addRequiredID(LoopSimplifyID); AU.addPreservedID(LoopSimplifyID); - AU.addRequired(); + AU.addRequiredTransitive(); AU.addPreserved(); - AU.addRequired(); + AU.addRequiredTransitive(); AU.addPreserved(); AU.addPreserved(); @@ -86,6 +87,17 @@ namespace { AU.addPreserved(); } private: + + /// verifyAnalysis() - Verify loop nest. + virtual void verifyAnalysis() const { +#ifndef NDEBUG + // Sanity check: Check basic loop invariants. + L->verifyLoop(); + // Check the special guarantees that LCSSA makes. + assert(L->isLCSSAForm()); +#endif + } + void getLoopValuesUsedOutsideLoop(Loop *L, SetVector &AffectedValues, const SmallVector& exitBlocks); @@ -107,7 +119,8 @@ Pass *llvm::createLCSSAPass() { return new LCSSA(); } const PassInfo *const llvm::LCSSAID = &X; /// runOnFunction - Process all loops in the function, inner-most out. -bool LCSSA::runOnLoop(Loop *L, LPPassManager &LPM) { +bool LCSSA::runOnLoop(Loop *l, LPPassManager &LPM) { + L = l; PredCache.clear(); LI = &LPM.getAnalysis(); diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index 56e5a46cb78..36709f7b435 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -69,8 +69,8 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { // We need loop information to identify the loops... - AU.addRequired(); - AU.addRequired(); + AU.addRequiredTransitive(); + AU.addRequiredTransitive(); AU.addPreserved(); AU.addPreserved(); @@ -83,9 +83,13 @@ namespace { void verifyAnalysis() const { #ifndef NDEBUG LoopInfo *NLI = &getAnalysis(); - for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I) + for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I) { + // Sanity check: Check basic loop invariants. (*I)->verifyLoop(); -#endif + // Check the special guarantees that LoopSimplify makes. + assert((*I)->isLoopSimplifyForm()); + } +#endif } private: @@ -346,15 +350,6 @@ BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { BasicBlock *NewBB = SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), ".preheader", this); - - - //===--------------------------------------------------------------------===// - // Update analysis results now that we have performed the transformation - // - - // We know that we have loop information to update... update it now. - if (Loop *Parent = L->getParentLoop()) - Parent->addBasicBlockToLoop(NewBB, LI->getBase()); // Make sure that NewBB is put someplace intelligent, which doesn't mess up // code layout too horribly. @@ -377,17 +372,6 @@ BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { LoopBlocks.size(), ".loopexit", this); - // Update Loop Information - we know that the new block will be in whichever - // loop the Exit block is in. Note that it may not be in that immediate loop, - // if the successor is some other loop header. In that case, we continue - // walking up the loop tree to find a loop that contains both the successor - // block and the predecessor block. - Loop *SuccLoop = LI->getLoopFor(Exit); - while (SuccLoop && !SuccLoop->contains(L->getHeader())) - SuccLoop = SuccLoop->getParentLoop(); - if (SuccLoop) - SuccLoop->addBasicBlockToLoop(NewBB, LI->getBase()); - return NewBB; } @@ -521,10 +505,6 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) { else LI->changeTopLevelLoop(L, NewOuter); - // This block is going to be our new header block: add it to this loop and all - // parent loops. - NewOuter->addBasicBlockToLoop(NewBB, LI->getBase()); - // L is now a subloop of our outer loop. NewOuter->addChildLoop(L); @@ -532,6 +512,10 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) { I != E; ++I) NewOuter->addBlockEntry(*I); + // Now reset the header in L, which had been moved by + // SplitBlockPredecessors for the outer loop. + L->moveToHeader(Header); + // Determine which blocks should stay in L and which should be moved out to // the Outer loop now. std::set BlocksInL; -- 2.34.1