From 4495a6b141ebf55bd1d7de48f3c0920c50cc9a77 Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Fri, 12 Jun 2020 11:15:26 +0100 Subject: [PATCH] [BreakCritEdges] Add option to opt-out of perserving loop-simplify. This patch adds a new option to CriticalEdgeSplittingOptions to control whether loop-simplify form must be preserved. It is them used by GVN to indicate that loop-simplify form does not have to be preserved. This fixes a crash exposed by 189efe295b6e. If the critical edge we are splitting goes from a block inside a loop to a block outside the loop, splitting the edge will create a new exit block. As a result, the new block will branch to the original exit block, which will add a non-loop predecessor, breaking loop-simplify form. To preserve loop-simplify form, the predecessor blocks of the original exit are split, but that does not work for blocks with indirectbr terminators. If preserving loop-simplify form is requested, bail out , before making any changes. Reviewers: reames, hfinkel, davide, efriedma Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D81582 --- .../llvm/Transforms/Utils/BasicBlockUtils.h | 9 +++ llvm/lib/Transforms/Scalar/GVN.cpp | 8 ++- llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp | 64 ++++++++++++++-------- .../GVN/critical-edge-split-indbr-pred-in-loop.ll | 46 ++++++++++++++++ llvm/test/Transforms/GVN/preserve-analysis.ll | 2 +- 5 files changed, 102 insertions(+), 27 deletions(-) create mode 100644 llvm/test/Transforms/GVN/critical-edge-split-indbr-pred-in-loop.ll diff --git a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h index 26ef08b..0a63654 100644 --- a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -141,6 +141,10 @@ struct CriticalEdgeSplittingOptions { bool KeepOneInputPHIs = false; bool PreserveLCSSA = false; bool IgnoreUnreachableDests = false; + /// SplitCriticalEdge is guaranteed to preserve loop-simplify form if LI is + /// provided. If it cannot be preserved, no splitting will take place. If it + /// is not set, preserve loop-simplify form if possible. + bool PreserveLoopSimplify = true; CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, @@ -167,6 +171,11 @@ struct CriticalEdgeSplittingOptions { IgnoreUnreachableDests = true; return *this; } + + CriticalEdgeSplittingOptions &unsetPreserveLoopSimplify() { + PreserveLoopSimplify = false; + return *this; + } }; /// If this edge is a critical edge, insert a new node to split the critical diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp index eae6de2..b16f859 100644 --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -2506,8 +2506,11 @@ bool GVN::performPRE(Function &F) { /// Split the critical edge connecting the given two blocks, and return /// the block inserted to the critical edge. BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) { - BasicBlock *BB = - SplitCriticalEdge(Pred, Succ, CriticalEdgeSplittingOptions(DT, LI)); + // GVN does not require loop-simplify, do not try to preserve it if it is not + // possible. + BasicBlock *BB = SplitCriticalEdge( + Pred, Succ, + CriticalEdgeSplittingOptions(DT, LI).unsetPreserveLoopSimplify()); if (MD) MD->invalidateCachedPredecessors(); InvalidBlockRPONumbers = true; @@ -2746,7 +2749,6 @@ public: AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); - AU.addPreservedID(LoopSimplifyID); AU.addRequired(); } diff --git a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp index 9c995de..ba3cb8f 100644 --- a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -158,6 +158,47 @@ llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum, isa(DestBB->getFirstNonPHIOrDbgOrLifetime())) return nullptr; + auto *LI = Options.LI; + SmallVector LoopPreds; + // Check if extra modifications will be required to preserve loop-simplify + // form after splitting. If it would require splitting blocks with IndirectBr + // terminators, bail out if preserving loop-simplify form is requested. + if (LI) { + if (Loop *TIL = LI->getLoopFor(TIBB)) { + + // The only that we can break LoopSimplify form by splitting a critical + // edge is if after the split there exists some edge from TIL to DestBB + // *and* the only edge into DestBB from outside of TIL is that of + // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB + // is the new exit block and it has no non-loop predecessors. If the + // second isn't true, then DestBB was not in LoopSimplify form prior to + // the split as it had a non-loop predecessor. In both of these cases, + // the predecessor must be directly in TIL, not in a subloop, or again + // LoopSimplify doesn't hold. + for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; + ++I) { + BasicBlock *P = *I; + if (P == TIBB) + continue; // The new block is known. + if (LI->getLoopFor(P) != TIL) { + // No need to re-simplify, it wasn't to start with. + LoopPreds.clear(); + break; + } + LoopPreds.push_back(P); + } + // Loop-simplify form can be preserved, if we can split all in-loop + // predecessors. + if (any_of(LoopPreds, [](BasicBlock *Pred) { + return isa(Pred->getTerminator()); + })) { + if (Options.PreserveLoopSimplify) + return nullptr; + LoopPreds.clear(); + } + } + } + // Create a new basic block, linking it into the CFG. BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); @@ -212,7 +253,6 @@ llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum, // If we have nothing to update, just return. auto *DT = Options.DT; auto *PDT = Options.PDT; - auto *LI = Options.LI; auto *MSSAU = Options.MSSAU; if (MSSAU) MSSAU->wireOldPredecessorsToNewImmediatePredecessor( @@ -281,28 +321,6 @@ llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum, createPHIsForSplitLoopExit(TIBB, NewBB, DestBB); } - // The only that we can break LoopSimplify form by splitting a critical - // edge is if after the split there exists some edge from TIL to DestBB - // *and* the only edge into DestBB from outside of TIL is that of - // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB - // is the new exit block and it has no non-loop predecessors. If the - // second isn't true, then DestBB was not in LoopSimplify form prior to - // the split as it had a non-loop predecessor. In both of these cases, - // the predecessor must be directly in TIL, not in a subloop, or again - // LoopSimplify doesn't hold. - SmallVector LoopPreds; - for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; - ++I) { - BasicBlock *P = *I; - if (P == NewBB) - continue; // The new block is known. - if (LI->getLoopFor(P) != TIL) { - // No need to re-simplify, it wasn't to start with. - LoopPreds.clear(); - break; - } - LoopPreds.push_back(P); - } if (!LoopPreds.empty()) { assert(!DestBB->isEHPad() && "We don't split edges to EH pads!"); BasicBlock *NewExitBB = SplitBlockPredecessors( diff --git a/llvm/test/Transforms/GVN/critical-edge-split-indbr-pred-in-loop.ll b/llvm/test/Transforms/GVN/critical-edge-split-indbr-pred-in-loop.ll new file mode 100644 index 0000000..f53e0a4 --- /dev/null +++ b/llvm/test/Transforms/GVN/critical-edge-split-indbr-pred-in-loop.ll @@ -0,0 +1,46 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -gvn -S -verify-loop-info %s | FileCheck %s + +; Make sure we do not try to preserve loop-simplify form, if it would mean +; splitting blocks with indirectbr predecessors. + +declare i1 @cond() + +define i32 @foo(i8* %p1, i8* %p2, i32* %p3) { +; CHECK-LABEL: @foo( +; CHECK-NEXT: bb: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: store i32 0, i32* [[P3:%.*]], align 4 +; CHECK-NEXT: indirectbr i8* [[P1:%.*]], [label [[LOOP_LATCH1:%.*]], label %loop.latch2] +; CHECK: loop.latch1: +; CHECK-NEXT: [[C:%.*]] = call i1 @cond() +; CHECK-NEXT: br i1 [[C]], label [[LOOP_HEADER]], label [[LOOP_LATCH1_EXIT_CRIT_EDGE:%.*]] +; CHECK: loop.latch1.exit_crit_edge: +; CHECK-NEXT: [[X_PRE:%.*]] = load i32, i32* [[P3]], align 4 +; CHECK-NEXT: br label [[EXIT:%.*]] +; CHECK: loop.latch2: +; CHECK-NEXT: indirectbr i8* [[P2:%.*]], [label [[LOOP_HEADER]], label %exit] +; CHECK: exit: +; CHECK-NEXT: [[X:%.*]] = phi i32 [ [[X_PRE]], [[LOOP_LATCH1_EXIT_CRIT_EDGE]] ], [ 0, [[LOOP_LATCH2:%.*]] ] +; CHECK-NEXT: ret i32 [[X]] +; +bb: + br label %loop.header + +loop.header: ; preds = %loop.latch2, %loop.latch1, %bb + store i32 0, i32* %p3, align 4 + indirectbr i8* %p1, [label %loop.latch1, label %loop.latch2] + +loop.latch1: ; preds = %loop.header + %c = call i1 @cond() + br i1 %c, label %loop.header, label %exit + +loop.latch2: ; preds = %loop.header + indirectbr i8* %p2, [label %loop.header, label %exit] + +exit: ; preds = %loop.latch2, %loop.latch1 + %x = load i32, i32* %p3, align 4 + %y = add i32 %x, 0 + ret i32 %y +} diff --git a/llvm/test/Transforms/GVN/preserve-analysis.ll b/llvm/test/Transforms/GVN/preserve-analysis.ll index 2454bb1a..d17cf05 100644 --- a/llvm/test/Transforms/GVN/preserve-analysis.ll +++ b/llvm/test/Transforms/GVN/preserve-analysis.ll @@ -12,7 +12,7 @@ ; CHECK: Global Value Numbering ; CHECK-NOT: Dominator Tree Construction ; CHECK-NOT: Natural Loop Information -; CHECK-NOT: Canonicalize natural loops +; CHECK: Canonicalize natural loops ; NEW-PM-DAG: Running analysis: LoopAnalysis on test ; NEW-PM-DAG: Running analysis: DominatorTreeAnalysis on test -- 2.7.4