diff options
author | Daniel Jasper <djasper@google.com> | 2017-06-25 17:58:25 +0000 |
---|---|---|
committer | Daniel Jasper <djasper@google.com> | 2017-06-25 17:58:25 +0000 |
commit | 4c6cd4ccb77cc994765dc9677278e48abf08ed69 (patch) | |
tree | 68eb8f6f65f6ff089b74b62e78976173f4746615 /llvm/lib/Transforms/Utils/LoopSimplify.cpp | |
parent | 18e6b57cdf6e5373d09b3ee198834f4e655f1b1c (diff) | |
download | bcm5719-llvm-4c6cd4ccb77cc994765dc9677278e48abf08ed69.tar.gz bcm5719-llvm-4c6cd4ccb77cc994765dc9677278e48abf08ed69.zip |
Revert "[LoopSimplify] Factor the logic to form dedicated exits into a utility."
This leads to a segfault. Chandler already has a test case and should be
able to recommit with a fix soon.
llvm-svn: 306252
Diffstat (limited to 'llvm/lib/Transforms/Utils/LoopSimplify.cpp')
-rw-r--r-- | llvm/lib/Transforms/Utils/LoopSimplify.cpp | 83 |
1 files changed, 62 insertions, 21 deletions
diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/llvm/lib/Transforms/Utils/LoopSimplify.cpp index e21e34df8de..f3db278ef1e 100644 --- a/llvm/lib/Transforms/Utils/LoopSimplify.cpp +++ b/llvm/lib/Transforms/Utils/LoopSimplify.cpp @@ -72,6 +72,7 @@ using namespace llvm; #define DEBUG_TYPE "loop-simplify" +STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); STATISTIC(NumNested , "Number of nested loops split out"); // If the block isn't already, move the new block to right after some 'outside @@ -151,6 +152,37 @@ BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT, return PreheaderBB; } +/// \brief Ensure that the loop preheader dominates all exit blocks. +/// +/// This method is used to split exit blocks that have predecessors outside of +/// the loop. +static BasicBlock *rewriteLoopExitBlock(Loop *L, BasicBlock *Exit, + DominatorTree *DT, LoopInfo *LI, + bool PreserveLCSSA) { + SmallVector<BasicBlock*, 8> LoopBlocks; + 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<IndirectBrInst>(P->getTerminator())) return nullptr; + + LoopBlocks.push_back(P); + } + } + + assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); + BasicBlock *NewExitBB = nullptr; + + NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", DT, LI, + PreserveLCSSA); + if (!NewExitBB) + return nullptr; + + DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " + << NewExitBB->getName() << "\n"); + return NewExitBB; +} + /// Add the specified block, and all of its predecessors, to the specified set, /// if it's not already in there. Stop predecessor traversal when we reach /// StopBlock. @@ -314,7 +346,16 @@ static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader, // Split edges to exit blocks from the inner loop, if they emerged in the // process of separating the outer one. - formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA); + SmallVector<BasicBlock *, 8> ExitBlocks; + L->getExitBlocks(ExitBlocks); + SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(), + ExitBlocks.end()); + for (BasicBlock *ExitBlock : ExitBlockSet) { + if (any_of(predecessors(ExitBlock), + [L](BasicBlock *BB) { return !L->contains(BB); })) { + rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA); + } + } if (PreserveLCSSA) { // Fix LCSSA form for L. Some values, which previously were only used inside @@ -522,16 +563,29 @@ ReprocessLoop: BasicBlock *Preheader = L->getLoopPreheader(); if (!Preheader) { Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA); - if (Preheader) + if (Preheader) { + ++NumInserted; Changed = true; + } } // Next, check to make sure that all exit nodes of the loop only have // predecessors that are inside of the loop. This check guarantees that the // loop preheader/header will dominate the exit blocks. If the exit block has // predecessors from outside of the loop, split the edge now. - if (formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA)) - Changed = true; + SmallVector<BasicBlock*, 8> ExitBlocks; + L->getExitBlocks(ExitBlocks); + + SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(), + ExitBlocks.end()); + for (BasicBlock *ExitBlock : ExitBlockSet) { + if (any_of(predecessors(ExitBlock), + [L](BasicBlock *BB) { return !L->contains(BB); })) { + rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA); + ++NumInserted; + Changed = true; + } + } // If the header has more than two predecessors at this point (from the // preheader and from multiple backedges), we must adjust the loop. @@ -560,8 +614,10 @@ ReprocessLoop: // insert a new block that all backedges target, then make it jump to the // loop header. LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI); - if (LoopLatch) + if (LoopLatch) { + ++NumInserted; Changed = true; + } } const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); @@ -589,22 +645,7 @@ ReprocessLoop: // loop-invariant instructions out of the way to open up more // opportunities, and the disadvantage of having the responsibility // to preserve dominator information. - auto HasUniqueExitBlock = [&]() { - BasicBlock *UniqueExit = nullptr; - for (auto *ExitingBB : ExitingBlocks) - for (auto *SuccBB : successors(ExitingBB)) { - if (L->contains(SuccBB)) - continue; - - if (!UniqueExit) - UniqueExit = SuccBB; - else if (UniqueExit != SuccBB) - return false; - } - - return true; - }; - if (HasUniqueExitBlock()) { + if (ExitBlockSet.size() == 1) { for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { BasicBlock *ExitingBlock = ExitingBlocks[i]; if (!ExitingBlock->getSinglePredecessor()) continue; |