[BreakCritEdges] Add option to opt-out of perserving loop-simplify.

[fhahn]

Summary

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.

[fhahn]

Only compute LoopPreds once.

[fhahn]

Updated to introduce new CriticalEdgeSPlittingOption to disable preserving loop-simplify form and use it in GVN.

[efriedma]

I'm a little uncomfortable with making SplitCriticalEdge fail rarely... but I guess if this is the least-nasty solution, it's okay for now. LGTM

[efriedma]

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

193

Really, I'd prefer if the if (Options.PreserveLoopSimplify) return nullptr; check wasn't guarded by the check for indirectbrinsts.

[fhahn]

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

193

Unfortunately there are some places, like LoopRotate & LoopUnswtich that rely on the splitting to happen (and loop-simplify form being preserved here). In most cases they probably reject the indirectbr cases up-front. I'll continue on D81584, which should hopefully eliminate this particular issue.

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

struct CriticalEdgeSplittingOptions {
   DominatorTree *DT;
   PostDominatorTree *PDT;
   LoopInfo *LI;
   MemorySSAUpdater *MSSAU;
   bool MergeIdenticalEdges = false;
   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,
                                MemorySSAUpdater *MSSAU = nullptr,
                                PostDominatorTree *PDT = nullptr)
       : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU) {}
 
   CriticalEdgeSplittingOptions &setMergeIdenticalEdges() {
CriticalEdgeSplittingOptions &setPreserveLCSSA() {
     PreserveLCSSA = true;
     return *this;
   }
 
   CriticalEdgeSplittingOptions &setIgnoreUnreachableDests() {
     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
 /// edge. This will update the analyses passed in through the option struct.
 /// This returns the new block if the edge was split, null otherwise.
 ///
 /// If MergeIdenticalEdges in the options struct is true (not the default),
 /// *all* edges from TI to the specified successor will be merged into the same

llvm/lib/Transforms/Scalar/GVN.cpp

if (splitCriticalEdges())
     Changed = true;
 
   return Changed;
 }
 
 /// 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;
   return BB;
 }
 
 /// Split critical edges found during the previous
 /// iteration that may enable further optimization.
void getAnalysisUsage(AnalysisUsage &AU) const override {
     if (Impl.isMemDepEnabled())
       AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
 
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addPreserved<TargetLibraryInfoWrapperPass>();
     AU.addPreserved<LoopInfoWrapperPass>();
-    AU.addPreservedID(LoopSimplifyID);
     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
   }
 
 private:
   GVN Impl;
 };
 
 char GVNLegacyPass::ID = 0;

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
   // Don't split the non-fallthrough edge from a callbr.
   if (isa<CallBrInst>(TI) && SuccNum > 0)
     return nullptr;
 
   if (Options.IgnoreUnreachableDests &&
       isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime()))
     return nullptr;
 
+  auto *LI = Options.LI;
+  SmallVector<BasicBlock *, 4> 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<IndirectBrInst>(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");
   // Create our unconditional branch.
   BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
   NewBI->setDebugLoc(TI->getDebugLoc());
 
   // Branch to the new block, breaking the edge.
for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
       // We found another edge to DestBB, go to NewBB instead.
       TI->setSuccessor(i, NewBB);
     }
   }
 
   // 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(
         DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);
 
   if (!DT && !PDT && !LI)
     return NewBB;
 
if (Loop *TIL = LI->getLoopFor(TIBB)) {
         assert(!TIL->contains(NewBB) &&
                "Split point for loop exit is contained in loop!");
 
         // Update LCSSA form in the newly created exit block.
         if (Options.PreserveLCSSA) {
           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<BasicBlock *, 4> 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(
               DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
           if (Options.PreserveLCSSA)
             createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
         }
       }

llvm/test/Transforms/GVN/critical-edge-split-indbr-pred-in-loop.ll

+; 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
+}

llvm/test/Transforms/GVN/preserve-analysis.ll

 ; RUN: opt < %s -debug-pass=Structure -indvars -gvn -indvars 2>&1 -S | FileCheck --check-prefix=CHECK --check-prefix=IR %s
 ; RUN: opt < %s -debug-pass-manager -passes='require<domtree>,loop(simplify-cfg),gvn,loop(indvars)' 2>&1 -S | FileCheck --check-prefix=NEW-PM --check-prefix=IR %s
 
 ; Check CFG-only analysis are preserved by SCCP by running it between 2
 ; loop-vectorize runs.
 
 ; CHECK: Dominator Tree Construction
 ; CHECK: Natural Loop Information
 ; CHECK: Canonicalize natural loops
 ; CHECK: LCSSA Verifier
 ; CHECK: Loop-Closed SSA Form Pass
 ; 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
 ; NEW-PM: Running pass: GVN on test
 ; NEW-PM-NOT: Running analysis: LoopAnalysis on test
 ; NEW-PM-NOT: Running analysis: DominatorTreeAnalysis on test
 
 declare i1 @cond()