X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FLoopSimplify.cpp;h=6b1eaad68ba31b8c3cd992422056b74a8bd50a2e;hb=481c4c07347c40fa666d09f3b31fbe2ca27e2d52;hp=cfdfcb0f73ac4d3f6928c3e75b07bbc70f357a94;hpb=0df6e09d43d6d733555a10d22572ddb0006e7d23;p=oota-llvm.git diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index cfdfcb0f73a..6b1eaad68ba 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -23,6 +23,11 @@ // // This pass also guarantees that loops will have exactly one backedge. // +// Indirectbr instructions introduce several complications. If the loop +// contains or is entered by an indirectbr instruction, it may not be possible +// to transform the loop and make these guarantees. Client code should check +// that these conditions are true before relying on them. +// // Note that the simplifycfg pass will clean up blocks which are split out but // end up being unnecessary, so usage of this pass should not pessimize // generated code. @@ -36,16 +41,18 @@ #include "llvm/Transforms/Scalar.h" #include "llvm/Constants.h" #include "llvm/Instructions.h" +#include "llvm/IntrinsicInst.h" #include "llvm/Function.h" #include "llvm/LLVMContext.h" #include "llvm/Type.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Support/CFG.h" -#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" #include "llvm/ADT/SetOperations.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" @@ -56,44 +63,47 @@ STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); STATISTIC(NumNested , "Number of nested loops split out"); namespace { - struct VISIBILITY_HIDDEN LoopSimplify : public FunctionPass { + struct LoopSimplify : public LoopPass { static char ID; // Pass identification, replacement for typeid - LoopSimplify() : FunctionPass(&ID) {} + LoopSimplify() : LoopPass(&ID) {} // AA - If we have an alias analysis object to update, this is it, otherwise // this is null. AliasAnalysis *AA; LoopInfo *LI; DominatorTree *DT; - virtual bool runOnFunction(Function &F); + Loop *L; + virtual bool runOnLoop(Loop *L, LPPassManager &LPM); virtual void getAnalysisUsage(AnalysisUsage &AU) const { // We need loop information to identify the loops... - AU.addRequired(); - AU.addRequired(); - - AU.addPreserved(); + AU.addRequiredTransitive(); AU.addPreserved(); + + // Request DominanceFrontier now, even though LoopSimplify does + // not use it. This allows Pass Manager to schedule Dominance + // Frontier early enough such that one LPPassManager can handle + // multiple loop transformation passes. + AU.addRequired(); AU.addPreserved(); + + AU.addRequiredTransitive(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreserved(); AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. } - /// verifyAnalysis() - Verify loop nest. - void verifyAnalysis() const { -#ifndef NDEBUG - LoopInfo *NLI = &getAnalysis(); - for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I) - (*I)->verifyLoop(); -#endif - } + /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. + void verifyAnalysis() const; private: - bool ProcessLoop(Loop *L); + bool ProcessLoop(Loop *L, LPPassManager &LPM); BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); BasicBlock *InsertPreheaderForLoop(Loop *L); - Loop *SeparateNestedLoop(Loop *L); - void InsertUniqueBackedgeBlock(Loop *L); + Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM); + BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader); void PlaceSplitBlockCarefully(BasicBlock *NewBB, SmallVectorImpl &SplitPreds, Loop *L); @@ -106,73 +116,19 @@ X("loopsimplify", "Canonicalize natural loops", true); // Publically exposed interface to pass... const PassInfo *const llvm::LoopSimplifyID = &X; -FunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } +Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } -/// runOnFunction - Run down all loops in the CFG (recursively, but we could do +/// runOnLoop - Run down all loops in the CFG (recursively, but we could do /// it in any convenient order) inserting preheaders... /// -bool LoopSimplify::runOnFunction(Function &F) { +bool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) { + L = l; bool Changed = false; LI = &getAnalysis(); AA = getAnalysisIfAvailable(); DT = &getAnalysis(); - // Check to see that no blocks (other than the header) in loops have - // predecessors that are not in loops. This is not valid for natural loops, - // but can occur if the blocks are unreachable. Since they are unreachable we - // can just shamelessly destroy their terminators to make them not branch into - // the loop! - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { - // This case can only occur for unreachable blocks. Blocks that are - // unreachable can't be in loops, so filter those blocks out. - if (LI->getLoopFor(BB)) continue; - - bool BlockUnreachable = false; - TerminatorInst *TI = BB->getTerminator(); - - // Check to see if any successors of this block are non-loop-header loops - // that are not the header. - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { - // If this successor is not in a loop, BB is clearly ok. - Loop *L = LI->getLoopFor(TI->getSuccessor(i)); - if (!L) continue; - - // If the succ is the loop header, and if L is a top-level loop, then this - // is an entrance into a loop through the header, which is also ok. - if (L->getHeader() == TI->getSuccessor(i) && L->getParentLoop() == 0) - continue; - - // Otherwise, this is an entrance into a loop from some place invalid. - // Either the loop structure is invalid and this is not a natural loop (in - // which case the compiler is buggy somewhere else) or BB is unreachable. - BlockUnreachable = true; - break; - } - - // If this block is ok, check the next one. - if (!BlockUnreachable) continue; - - // Otherwise, this block is dead. To clean up the CFG and to allow later - // loop transformations to ignore this case, we delete the edges into the - // loop by replacing the terminator. - - // Remove PHI entries from the successors. - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) - TI->getSuccessor(i)->removePredecessor(BB); - - // Add a new unreachable instruction before the old terminator. - new UnreachableInst(TI); - - // Delete the dead terminator. - if (AA) AA->deleteValue(TI); - if (!TI->use_empty()) - TI->replaceAllUsesWith(Context->getUndef(TI->getType())); - TI->eraseFromParent(); - Changed |= true; - } - - for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) - Changed |= ProcessLoop(*I); + Changed |= ProcessLoop(L, LPM); return Changed; } @@ -180,24 +136,75 @@ bool LoopSimplify::runOnFunction(Function &F) { /// ProcessLoop - Walk the loop structure in depth first order, ensuring that /// all loops have preheaders. /// -bool LoopSimplify::ProcessLoop(Loop *L) { +bool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) { bool Changed = false; ReprocessLoop: - - // Canonicalize inner loops before outer loops. Inner loop canonicalization - // can provide work for the outer loop to canonicalize. - for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) - Changed |= ProcessLoop(*I); - - assert(L->getBlocks()[0] == L->getHeader() && - "Header isn't first block in loop?"); + + // Check to see that no blocks (other than the header) in this loop have + // predecessors that are not in the loop. This is not valid for natural + // loops, but can occur if the blocks are unreachable. Since they are + // unreachable we can just shamelessly delete those CFG edges! + for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); + BB != E; ++BB) { + if (*BB == L->getHeader()) continue; + + SmallPtrSet BadPreds; + for (pred_iterator PI = pred_begin(*BB), + PE = pred_end(*BB); PI != PE; ++PI) { + BasicBlock *P = *PI; + if (!L->contains(P)) + BadPreds.insert(P); + } + + // Delete each unique out-of-loop (and thus dead) predecessor. + for (SmallPtrSet::iterator I = BadPreds.begin(), + E = BadPreds.end(); I != E; ++I) { + + DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "; + WriteAsOperand(dbgs(), *I, false); + dbgs() << "\n"); + + // Inform each successor of each dead pred. + for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) + (*SI)->removePredecessor(*I); + // Zap the dead pred's terminator and replace it with unreachable. + TerminatorInst *TI = (*I)->getTerminator(); + TI->replaceAllUsesWith(UndefValue::get(TI->getType())); + (*I)->getTerminator()->eraseFromParent(); + new UnreachableInst((*I)->getContext(), *I); + Changed = true; + } + } + + // If there are exiting blocks with branches on undef, resolve the undef in + // the direction which will exit the loop. This will help simplify loop + // trip count computations. + SmallVector ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + for (SmallVectorImpl::iterator I = ExitingBlocks.begin(), + E = ExitingBlocks.end(); I != E; ++I) + if (BranchInst *BI = dyn_cast((*I)->getTerminator())) + if (BI->isConditional()) { + if (UndefValue *Cond = dyn_cast(BI->getCondition())) { + + DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in "; + WriteAsOperand(dbgs(), *I, false); + dbgs() << "\n"); + + BI->setCondition(ConstantInt::get(Cond->getType(), + !L->contains(BI->getSuccessor(0)))); + Changed = true; + } + } // Does the loop already have a preheader? If so, don't insert one. BasicBlock *Preheader = L->getLoopPreheader(); if (!Preheader) { Preheader = InsertPreheaderForLoop(L); - NumInserted++; - Changed = true; + if (Preheader) { + ++NumInserted; + Changed = true; + } } // Next, check to make sure that all exit nodes of the loop only have @@ -207,8 +214,9 @@ ReprocessLoop: SmallVector ExitBlocks; L->getExitBlocks(ExitBlocks); - SetVector ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); - for (SetVector::iterator I = ExitBlockSet.begin(), + SmallSetVector ExitBlockSet(ExitBlocks.begin(), + ExitBlocks.end()); + for (SmallSetVector::iterator I = ExitBlockSet.begin(), E = ExitBlockSet.end(); I != E; ++I) { BasicBlock *ExitBlock = *I; for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); @@ -216,25 +224,25 @@ ReprocessLoop: // Must be exactly this loop: no subloops, parent loops, or non-loop preds // allowed. if (!L->contains(*PI)) { - RewriteLoopExitBlock(L, ExitBlock); - NumInserted++; - Changed = true; + if (RewriteLoopExitBlock(L, ExitBlock)) { + ++NumInserted; + Changed = true; + } break; } } // If the header has more than two predecessors at this point (from the // preheader and from multiple backedges), we must adjust the loop. - unsigned NumBackedges = L->getNumBackEdges(); - if (NumBackedges != 1) { + BasicBlock *LoopLatch = L->getLoopLatch(); + if (!LoopLatch) { // If this is really a nested loop, rip it out into a child loop. Don't do // this for loops with a giant number of backedges, just factor them into a // common backedge instead. - if (NumBackedges < 8) { - if (Loop *NL = SeparateNestedLoop(L)) { + if (L->getNumBackEdges() < 8) { + if (SeparateNestedLoop(L, LPM)) { ++NumNested; // This is a big restructuring change, reprocess the whole loop. - ProcessLoop(NL); Changed = true; // GCC doesn't tail recursion eliminate this. goto ReprocessLoop; @@ -244,9 +252,11 @@ ReprocessLoop: // If we either couldn't, or didn't want to, identify nesting of the loops, // insert a new block that all backedges target, then make it jump to the // loop header. - InsertUniqueBackedgeBlock(L); - NumInserted++; - Changed = true; + LoopLatch = InsertUniqueBackedgeBlock(L, Preheader); + if (LoopLatch) { + ++NumInserted; + Changed = true; + } } // Scan over the PHI nodes in the loop header. Since they now have only two @@ -255,13 +265,13 @@ ReprocessLoop: PHINode *PN; for (BasicBlock::iterator I = L->getHeader()->begin(); (PN = dyn_cast(I++)); ) - if (Value *V = PN->hasConstantValue()) { + if (Value *V = PN->hasConstantValue(DT)) { if (AA) AA->deleteValue(PN); PN->replaceAllUsesWith(V); PN->eraseFromParent(); } - // If this loop has muliple exits and the exits all go to the same + // If this loop has multiple exits and the exits all go to the same // block, attempt to merge the exits. This helps several passes, such // as LoopRotation, which do not support loops with multiple exits. // SimplifyCFG also does this (and this code uses the same utility @@ -270,9 +280,14 @@ ReprocessLoop: // loop-invariant instructions out of the way to open up more // opportunities, and the disadvantage of having the responsibility // to preserve dominator information. - if (ExitBlocks.size() > 1 && L->getUniqueExitBlock()) { - SmallVector ExitingBlocks; - L->getExitingBlocks(ExitingBlocks); + bool UniqueExit = true; + if (!ExitBlocks.empty()) + for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i) + if (ExitBlocks[i] != ExitBlocks[0]) { + UniqueExit = false; + break; + } + if (UniqueExit) { for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { BasicBlock *ExitingBlock = ExitingBlocks[i]; if (!ExitingBlock->getSinglePredecessor()) continue; @@ -286,11 +301,14 @@ ReprocessLoop: bool AllInvariant = true; for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { Instruction *Inst = I++; + // Skip debug info intrinsics. + if (isa(Inst)) + continue; if (Inst == CI) continue; - if (!L->makeLoopInvariant(Inst, Preheader->getTerminator())) { + if (!L->makeLoopInvariant(Inst, Changed, + Preheader ? Preheader->getTerminator() : 0)) { AllInvariant = false; - Changed = true; break; } } @@ -303,6 +321,11 @@ ReprocessLoop: // Success. The block is now dead, so remove it from the loop, // update the dominator tree and dominance frontier, and delete it. + + DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "; + WriteAsOperand(dbgs(), ExitingBlock, false); + dbgs() << "\n"); + assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); Changed = true; LI->removeBlock(ExitingBlock); @@ -311,9 +334,10 @@ ReprocessLoop: DomTreeNode *Node = DT->getNode(ExitingBlock); const std::vector *> &Children = Node->getChildren(); - for (unsigned k = 0, g = Children.size(); k != g; ++k) { - DT->changeImmediateDominator(Children[k], Node->getIDom()); - if (DF) DF->changeImmediateDominator(Children[k]->getBlock(), + while (!Children.empty()) { + DomTreeNode *Child = Children.front(); + DT->changeImmediateDominator(Child, Node->getIDom()); + if (DF) DF->changeImmediateDominator(Child->getBlock(), Node->getIDom()->getBlock(), DT); } @@ -339,23 +363,27 @@ BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { // Compute the set of predecessors of the loop that are not in the loop. SmallVector OutsideBlocks; for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); - PI != PE; ++PI) - if (!L->contains(*PI)) // Coming in from outside the loop? - OutsideBlocks.push_back(*PI); // Keep track of it... + PI != PE; ++PI) { + BasicBlock *P = *PI; + if (!L->contains(P)) { // Coming in from outside the loop? + // If the loop is branched to from an indirect branch, we won't + // be able to fully transform the loop, because it prohibits + // edge splitting. + if (isa(P->getTerminator())) return 0; + + // Keep track of it. + OutsideBlocks.push_back(P); + } + } // Split out the loop pre-header. 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()); + DEBUG(dbgs() << "LoopSimplify: Creating pre-header "; + WriteAsOperand(dbgs(), NewBB, false); + dbgs() << "\n"); // Make sure that NewBB is put someplace intelligent, which doesn't mess up // code layout too horribly. @@ -369,25 +397,24 @@ BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { /// outside of the loop. BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { SmallVector LoopBlocks; - for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) - if (L->contains(*I)) - LoopBlocks.push_back(*I); + for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) { + BasicBlock *P = *I; + if (L->contains(P)) { + // Don't do this if the loop is exited via an indirect branch. + if (isa(P->getTerminator())) return 0; + + LoopBlocks.push_back(P); + } + } assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], 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()); + DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "; + WriteAsOperand(dbgs(), NewBB, false); + dbgs() << "\n"); return NewBB; } @@ -418,14 +445,13 @@ static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ) { PHINode *PN = cast(I); ++I; - if (Value *V = PN->hasConstantValue()) - if (!isa(V) || DT->dominates(cast(V), PN)) { - // This is a degenerate PHI already, don't modify it! - PN->replaceAllUsesWith(V); - if (AA) AA->deleteValue(PN); - PN->eraseFromParent(); - continue; - } + if (Value *V = PN->hasConstantValue(DT)) { + // This is a degenerate PHI already, don't modify it! + PN->replaceAllUsesWith(V); + if (AA) AA->deleteValue(PN); + PN->eraseFromParent(); + continue; + } // Scan this PHI node looking for a use of the PHI node by itself. for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) @@ -492,7 +518,7 @@ void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, /// If we are able to separate out a loop, return the new outer loop that was /// created. /// -Loop *LoopSimplify::SeparateNestedLoop(Loop *L) { +Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { PHINode *PN = FindPHIToPartitionLoops(L, DT, AA); if (PN == 0) return 0; // No known way to partition. @@ -502,8 +528,15 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) { SmallVector OuterLoopPreds; for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) if (PN->getIncomingValue(i) != PN || - !L->contains(PN->getIncomingBlock(i))) + !L->contains(PN->getIncomingBlock(i))) { + // We can't split indirectbr edges. + if (isa(PN->getIncomingBlock(i)->getTerminator())) + return 0; + OuterLoopPreds.push_back(PN->getIncomingBlock(i)); + } + + DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n"); BasicBlock *Header = L->getHeader(); BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0], @@ -523,24 +556,28 @@ 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); + // Add the new loop to the pass manager queue. + LPM.insertLoopIntoQueue(NewOuter); + for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 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; - for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) - if (DT->dominates(Header, *PI)) - AddBlockAndPredsToSet(*PI, Header, BlocksInL); - + for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) { + BasicBlock *P = *PI; + if (DT->dominates(Header, P)) + AddBlockAndPredsToSet(P, Header, BlocksInL); + } // Scan all of the loop children of L, moving them to OuterLoop if they are // not part of the inner loop. @@ -574,23 +611,34 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) { /// backedges to target a new basic block and have that block branch to the loop /// header. This ensures that loops have exactly one backedge. /// -void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { +BasicBlock * +LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); // Get information about the loop - BasicBlock *Preheader = L->getLoopPreheader(); BasicBlock *Header = L->getHeader(); Function *F = Header->getParent(); + // Unique backedge insertion currently depends on having a preheader. + if (!Preheader) + return 0; + // Figure out which basic blocks contain back-edges to the loop header. std::vector BackedgeBlocks; - for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) - if (*I != Preheader) BackedgeBlocks.push_back(*I); + for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I){ + BasicBlock *P = *I; + if (P != Preheader) BackedgeBlocks.push_back(P); + } // Create and insert the new backedge block... - BasicBlock *BEBlock = BasicBlock::Create(Header->getName()+".backedge", F); + BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(), + Header->getName()+".backedge", F); BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); + DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block "; + WriteAsOperand(dbgs(), BEBlock, false); + dbgs() << "\n"); + // Move the new backedge block to right after the last backedge block. Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); @@ -667,4 +715,40 @@ void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { DT->splitBlock(BEBlock); if (DominanceFrontier *DF = getAnalysisIfAvailable()) DF->splitBlock(BEBlock); + + return BEBlock; +} + +void LoopSimplify::verifyAnalysis() const { + // It used to be possible to just assert L->isLoopSimplifyForm(), however + // with the introduction of indirectbr, there are now cases where it's + // not possible to transform a loop as necessary. We can at least check + // that there is an indirectbr near any time there's trouble. + + // Indirectbr can interfere with preheader and unique backedge insertion. + if (!L->getLoopPreheader() || !L->getLoopLatch()) { + bool HasIndBrPred = false; + for (pred_iterator PI = pred_begin(L->getHeader()), + PE = pred_end(L->getHeader()); PI != PE; ++PI) + if (isa((*PI)->getTerminator())) { + HasIndBrPred = true; + break; + } + assert(HasIndBrPred && + "LoopSimplify has no excuse for missing loop header info!"); + } + + // Indirectbr can interfere with exit block canonicalization. + if (!L->hasDedicatedExits()) { + bool HasIndBrExiting = false; + SmallVector ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) + if (isa((ExitingBlocks[i])->getTerminator())) { + HasIndBrExiting = true; + break; + } + assert(HasIndBrExiting && + "LoopSimplify has no excuse for missing exit block info!"); + } }