From 6cf9acbae60a358f912106d368e6b7dcc094ac66 Mon Sep 17 00:00:00 2001 From: Daniel Jasper Date: Sun, 25 Jun 2017 17:58:25 +0000 Subject: [PATCH] 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@306252 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/Utils/LoopUtils.h | 8 --- lib/Transforms/Utils/LoopSimplify.cpp | 83 ++++++++++++++++------ lib/Transforms/Utils/LoopUtils.cpp | 62 ---------------- .../LoopUnswitch/2011-11-18-SimpleSwitch.ll | 1 + .../2011-11-18-TwoSwitches-Threshold.ll | 1 + .../LoopUnswitch/2011-11-18-TwoSwitches.ll | 1 + 6 files changed, 65 insertions(+), 91 deletions(-) diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h index 0397eb95e76..561f9488062 100644 --- a/include/llvm/Transforms/Utils/LoopUtils.h +++ b/include/llvm/Transforms/Utils/LoopUtils.h @@ -362,14 +362,6 @@ private: BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA); -/// Ensure that all exit blocks of the loop are dedicated exits. -/// -/// For any loop exit block with non-loop predecessors, we split the loop -/// predecessors to use a dedicated loop exit block. We update the dominator -/// tree and loop info if provided, and will preserve LCSSA if requested. -bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, - bool PreserveLCSSA); - /// Ensures LCSSA form for every instruction from the Worklist in the scope of /// innermost containing loop. /// diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index e21e34df8de..f3db278ef1e 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/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 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(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 ExitBlocks; + L->getExitBlocks(ExitBlocks); + SmallSetVector 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 ExitBlocks; + L->getExitBlocks(ExitBlocks); + + SmallSetVector 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; diff --git a/lib/Transforms/Utils/LoopUtils.cpp b/lib/Transforms/Utils/LoopUtils.cpp index 88fa9812da4..e545bc0eb36 100644 --- a/lib/Transforms/Utils/LoopUtils.cpp +++ b/lib/Transforms/Utils/LoopUtils.cpp @@ -29,7 +29,6 @@ #include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" #include "llvm/Support/Debug.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" using namespace llvm; using namespace llvm::PatternMatch; @@ -923,67 +922,6 @@ bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop, return true; } -bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, - bool PreserveLCSSA) { - bool Changed = false; - - // We re-use a vector for the in-loop predecesosrs. - SmallVector InLoopPredecessors; - - auto RewriteExit = [&](BasicBlock *BB) { - // See if there are any non-loop predecessors of this exit block and - // keep track of the in-loop predecessors. - bool IsDedicatedExit = true; - for (auto *PredBB : predecessors(BB)) - if (L->contains(PredBB)) { - if (isa(PredBB->getTerminator())) - // We cannot rewrite exiting edges from an indirectbr. - return false; - - InLoopPredecessors.push_back(PredBB); - } else { - IsDedicatedExit = false; - } - - // Nothing to do if this is already a dedicated exit. - if (IsDedicatedExit) { - InLoopPredecessors.clear(); - return false; - } - - assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!"); - auto *NewExitBB = SplitBlockPredecessors( - BB, InLoopPredecessors, ".loopexit", DT, LI, PreserveLCSSA); - - if (!NewExitBB) - DEBUG(dbgs() << "WARNING: Can't create a dedicated exit block for loop: " - << *L << "\n"); - else - DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " - << NewExitBB->getName() << "\n"); - InLoopPredecessors.clear(); - return true; - }; - - // Walk the exit blocks directly rather than building up a data structure for - // them, but only visit each one once. - SmallPtrSet Visited; - for (auto *BB : L->blocks()) - for (auto *SuccBB : successors(BB)) { - // We're looking for exit blocks so skip in-loop successors. - if (L->contains(SuccBB)) - continue; - - // Visit each exit block exactly once. - if (!Visited.insert(SuccBB).second) - continue; - - Changed |= RewriteExit(SuccBB); - } - - return Changed; -} - /// \brief Returns the instructions that use values defined in the loop. SmallVector llvm::findDefsUsedOutsideOfLoop(Loop *L) { SmallVector UsedOutside; diff --git a/test/Transforms/LoopUnswitch/2011-11-18-SimpleSwitch.ll b/test/Transforms/LoopUnswitch/2011-11-18-SimpleSwitch.ll index d115787b6ea..a35596aff11 100644 --- a/test/Transforms/LoopUnswitch/2011-11-18-SimpleSwitch.ll +++ b/test/Transforms/LoopUnswitch/2011-11-18-SimpleSwitch.ll @@ -2,6 +2,7 @@ ; RUN: opt -loop-unswitch -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s ; RUN: opt -S -loop-unswitch -verify-loop-info -verify-dom-info < %s | FileCheck %s +; STATS: 1 loop-simplify - Number of pre-header or exit blocks inserted ; STATS: 2 loop-unswitch - Number of switches unswitched ; CHECK: %1 = icmp eq i32 %c, 1 diff --git a/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches-Threshold.ll b/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches-Threshold.ll index c4e8d6f8898..393dd5c313a 100644 --- a/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches-Threshold.ll +++ b/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches-Threshold.ll @@ -2,6 +2,7 @@ ; RUN: opt -loop-unswitch -loop-unswitch-threshold 13 -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s ; RUN: opt -S -loop-unswitch -loop-unswitch-threshold 13 -verify-loop-info -verify-dom-info < %s | FileCheck %s +; STATS: 1 loop-simplify - Number of pre-header or exit blocks inserted ; STATS: 1 loop-unswitch - Number of switches unswitched ; ModuleID = '../llvm/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll' diff --git a/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll b/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll index 18e544d86ca..20f03c987eb 100644 --- a/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll +++ b/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll @@ -2,6 +2,7 @@ ; RUN: opt -loop-unswitch -loop-unswitch-threshold 1000 -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s ; RUN: opt -S -loop-unswitch -loop-unswitch-threshold 1000 -verify-loop-info -verify-dom-info < %s | FileCheck %s +; STATS: 1 loop-simplify - Number of pre-header or exit blocks inserted ; STATS: 3 loop-unswitch - Number of switches unswitched ; CHECK: %1 = icmp eq i32 %c, 1 -- 2.11.0