[SimplifyCFG] Be more aggressive when sinking into unreachable-post-dominated block

[lebedev.ri]

Summary

I strongly believe we need some variant of this.

The main problem is e.g. that the glibc's assert has 4 parameters,
but the profitability check is only okay with one extra phi node,
so D116692 doesn't even trigger on most of the expected cases.

While that restriction probably makes sense in normal code, if we
are about to run off of a cliff (into an unreachable), this
successor block is unlikely so the cost to setup these PHI nodes
should not be on the hotpath, and shouldn't matter performance-wise.

Likewise, we don't sink if there are unconditional predecessors
UNLESS we'd sink at least one non-speculatable instruction,
which is a performance workaround, but if we are about to run into
unreachable, it shouldn't matter.

One open question is whether to only allow simple control flow
that directly unconditionally leads to unreachable,
or instead check that all the function terminator blocks
that post-dominate the block into which we are sinking
are unreachable (i.e. allow loops).

[efriedma]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2056

Where is the implementation of IsBlockPostDominatedByDeoptOrUnreachable?

In any case, just from the name, I'm not sure this quite captures the property you want here. There's a difference between sinking into a block that ends in unreachable, vs. a block where the control flow eventually leads to unreachable. There could be a non-trivial amount of code between the code you're transforming, and the actual unreachable instruction. (e.g. the main loop of a program likely ends with a call to exit(), so all blocks in the main function are post-dominated by unreachable).

[lebedev.ri]

Actually upload the whole diff this time.

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2056

Where is the implementation of IsBlockPostDominatedByDeoptOrUnreachable?

Uploaded now.

<...>

Yes, that's the question. Okay, let's not do that.

[lebedev.ri]

Don't allow loops inbeteen.

[lebedev.ri]

I think i'm just going to land this particular patch, especially now that it doesn't allow loops.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

while (LRI.isValid() &&
     ++ScanIdx;
     --LRI;
   }
 
   // If no instructions can be sunk, early-return.
   if (ScanIdx == 0)
     return false;
 
+  bool PostDominatedByUnreachable =
+      IsBlockPostDominatedByDeoptOrUnreachable(BB, /*FollowDivergence=*/true);
+
+  if (!PostDominatedByUnreachable) {
     // Okay, we *could* sink last ScanIdx instructions. But how many can we
-  // actually sink before encountering instruction that is unprofitable to sink?
+    // actually sink before encountering instruction that is unprofitable to
+    // sink?
     auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
       unsigned NumPHIdValues = 0;
       for (auto *I : *LRI)
         for (auto *V : PHIOperands[I]) {
           if (!InstructionsToSink.contains(V))
             ++NumPHIdValues;
           // FIXME: this check is overly optimistic. We may end up not sinking
           // said instruction, due to the very same profitability check.
           // See @creating_too_many_phis in sink-common-code.ll.
         }
       LLVM_DEBUG(dbgs() << "SINK: #phid values: " << NumPHIdValues << "\n");
       unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.size();
       if ((NumPHIdValues % UnconditionalPreds.size()) != 0)
         NumPHIInsts++;
 
       return NumPHIInsts <= 1;
     };
 
     // We've determined that we are going to sink last ScanIdx instructions,
     // and recorded them in InstructionsToSink. Now, some instructions may be
     // unprofitable to sink. But that determination depends on the instructions
     // that we are going to sink.
 
     // First, forward scan: find the first instruction unprofitable to sink,
     // recording all the ones that are profitable to sink.
     // FIXME: would it be better, after we detect that not all are profitable.
     // to either record the profitable ones, or erase the unprofitable ones?
-  // Maybe we need to choose (at runtime) the one that will touch least instrs?
+    // Maybe we need to choose (at runtime) the one that will touch least
+    // instrs?
     LRI.reset();
     int Idx = 0;
     SmallPtrSet<Value *, 4> InstructionsProfitableToSink;
     while (Idx < ScanIdx) {
       if (!ProfitableToSinkInstruction(LRI)) {
         // Too many PHIs would be created.
         LLVM_DEBUG(
             dbgs() << "SINK: stopping here, too many PHIs would be created!\n");
         break;
       }
       InstructionsProfitableToSink.insert((*LRI).begin(), (*LRI).end());
       --LRI;
       ++Idx;
     }
 
     // If no instructions can be sunk, early-return.
     if (Idx == 0)
       return false;
 
     // Did we determine that (only) some instructions are unprofitable to sink?
     if (Idx < ScanIdx) {
       // Okay, some instructions are unprofitable.
       ScanIdx = Idx;
       InstructionsToSink = InstructionsProfitableToSink;
 
       // But, that may make other instructions unprofitable, too.
-    // So, do a backward scan, do any earlier instructions become unprofitable?
-    assert(!ProfitableToSinkInstruction(LRI) &&
-           "We already know that the last instruction is unprofitable to sink");
+      // So, do a backward scan, do any earlier instructions become
+      // unprofitable?
+      assert(
+          !ProfitableToSinkInstruction(LRI) &&
       ++LRI;
       --Idx;
       while (Idx >= 0) {
         // If we detect that an instruction becomes unprofitable to sink,
         // all earlier instructions won't be sunk either,
         // so preemptively keep InstructionsProfitableToSink in sync.
         // FIXME: is this the most performant approach?
         for (auto *I : *LRI)
           InstructionsProfitableToSink.erase(I);
         if (!ProfitableToSinkInstruction(LRI)) {
           // Everything starting with this instruction won't be sunk.
           ScanIdx = Idx;
           InstructionsToSink = InstructionsProfitableToSink;
         }
         ++LRI;
         --Idx;
       }
     }
 
     // If no instructions can be sunk, early-return.
     if (ScanIdx == 0)
       return false;
+  }
 
   bool Changed = false;
 
   if (HaveNonUnconditionalPredecessors) {
+    if (!PostDominatedByUnreachable) {
       // It is always legal to sink common instructions from unconditional
       // predecessors. However, if not all predecessors are unconditional,
       // this transformation might be pessimizing. So as a rule of thumb,
       // don't do it unless we'd sink at least one non-speculatable instruction.
       // See https://bugs.llvm.org/show_bug.cgi?id=30244
       LRI.reset();
       int Idx = 0;
       bool Profitable = false;
       while (Idx < ScanIdx) {
         if (!isSafeToSpeculativelyExecute((*LRI)[0])) {
           Profitable = true;
           break;
         }
         --LRI;
         ++Idx;
       }
       if (!Profitable)
         return false;
+    }
 
     LLVM_DEBUG(dbgs() << "SINK: Splitting edge\n");
     // We have a conditional edge and we're going to sink some instructions.
     // Insert a new block postdominating all blocks we're going to sink from.
     if (!SplitBlockPredecessors(BB, UnconditionalPreds, ".sink.split", DTU))
       // Edges couldn't be split.
       return false;
     Changed = true;

llvm/test/Transforms/SimplifyCFG/X86/sink-common-code-into-unreachable.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -sink-common-insts -S | FileCheck %s
 ; RUN: opt < %s -passes='simplifycfg<sink-common-insts>' -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-pc-linux-gnu"
 
 ; `unreachable` block has conditional predecessors,
 ; but everything we'd sink from unconditional predecessors are speculatable.
 ; Also, too many phi's would normally be needed.
 define void @t0(i4 %cond,  i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %f, i32 %g, i32 %h) {
 ; CHECK-LABEL: @t0(
 ; CHECK-NEXT:    switch i4 [[COND:%.*]], label [[END:%.*]] [
-; CHECK-NEXT:    i4 0, label [[BB0:%.*]]
-; CHECK-NEXT:    i4 -1, label [[BB0]]
+; CHECK-NEXT:    i4 0, label [[END_SINK_SPLIT:%.*]]
+; CHECK-NEXT:    i4 -1, label [[END_SINK_SPLIT]]
 ; CHECK-NEXT:    i4 1, label [[BB1:%.*]]
 ; CHECK-NEXT:    i4 -2, label [[BB1]]
 ; CHECK-NEXT:    ]
-; CHECK:       bb0:
-; CHECK-NEXT:    [[V0:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[V1:%.*]] = add i32 [[V0]], [[C:%.*]]
-; CHECK-NEXT:    [[V2:%.*]] = add i32 [[D:%.*]], [[E:%.*]]
-; CHECK-NEXT:    [[R3:%.*]] = add i32 [[V1]], [[V2]]
-; CHECK-NEXT:    call void @use32(i32 [[R3]])
-; CHECK-NEXT:    unreachable
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[V4:%.*]] = add i32 [[A]], [[B]]
-; CHECK-NEXT:    [[V5:%.*]] = add i32 [[V4]], [[C]]
-; CHECK-NEXT:    [[V6:%.*]] = add i32 [[G:%.*]], [[H:%.*]]
+; CHECK-NEXT:    br label [[END_SINK_SPLIT]]
+; CHECK:       end.sink.split:
+; CHECK-NEXT:    [[H_SINK:%.*]] = phi i32 [ [[H:%.*]], [[BB1]] ], [ [[E:%.*]], [[TMP0:%.*]] ], [ [[E]], [[TMP0]] ]
+; CHECK-NEXT:    [[G_SINK:%.*]] = phi i32 [ [[G:%.*]], [[BB1]] ], [ [[D:%.*]], [[TMP0]] ], [ [[D]], [[TMP0]] ]
+; CHECK-NEXT:    [[V4:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[V5:%.*]] = add i32 [[V4]], [[C:%.*]]
+; CHECK-NEXT:    [[V6:%.*]] = add i32 [[G_SINK]], [[H_SINK]]
 ; CHECK-NEXT:    [[R7:%.*]] = add i32 [[V5]], [[V6]]
 ; CHECK-NEXT:    call void @use32(i32 [[R7]])
 ; CHECK-NEXT:    unreachable
 ; CHECK:       end:
 ; CHECK-NEXT:    unreachable
 ;
   switch i4 %cond, label %end [
   i4 0, label %bb0

 end:
   unreachable
 }
 
 ; Same, as @t0, but there's also a loop.
 define void @t1(i4 %cond, i1 %cond.loop, i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %f, i32 %g, i32 %h) {
 ; CHECK-LABEL: @t1(
 ; CHECK-NEXT:    switch i4 [[COND:%.*]], label [[END_EARLY:%.*]] [
-; CHECK-NEXT:    i4 0, label [[BB0:%.*]]
-; CHECK-NEXT:    i4 -1, label [[BB0]]
+; CHECK-NEXT:    i4 0, label [[END_EARLY_SINK_SPLIT:%.*]]
+; CHECK-NEXT:    i4 -1, label [[END_EARLY_SINK_SPLIT]]
 ; CHECK-NEXT:    i4 1, label [[BB1:%.*]]
 ; CHECK-NEXT:    i4 -2, label [[BB1]]
 ; CHECK-NEXT:    ]
-; CHECK:       bb0:
-; CHECK-NEXT:    [[V0:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[V1:%.*]] = add i32 [[V0]], [[C:%.*]]
-; CHECK-NEXT:    [[V2:%.*]] = add i32 [[D:%.*]], [[E:%.*]]
-; CHECK-NEXT:    [[R3:%.*]] = add i32 [[V1]], [[V2]]
-; CHECK-NEXT:    call void @use32(i32 [[R3]])
-; CHECK-NEXT:    br label [[END_EARLY]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[V4:%.*]] = add i32 [[A]], [[B]]
-; CHECK-NEXT:    [[V5:%.*]] = add i32 [[V4]], [[C]]
-; CHECK-NEXT:    [[V6:%.*]] = add i32 [[G:%.*]], [[H:%.*]]
+; CHECK-NEXT:    br label [[END_EARLY_SINK_SPLIT]]
+; CHECK:       end.early.sink.split:
+; CHECK-NEXT:    [[H_SINK:%.*]] = phi i32 [ [[H:%.*]], [[BB1]] ], [ [[E:%.*]], [[TMP0:%.*]] ], [ [[E]], [[TMP0]] ]
+; CHECK-NEXT:    [[G_SINK:%.*]] = phi i32 [ [[G:%.*]], [[BB1]] ], [ [[D:%.*]], [[TMP0]] ], [ [[D]], [[TMP0]] ]
+; CHECK-NEXT:    [[V4:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[V5:%.*]] = add i32 [[V4]], [[C:%.*]]
+; CHECK-NEXT:    [[V6:%.*]] = add i32 [[G_SINK]], [[H_SINK]]
 ; CHECK-NEXT:    [[R7:%.*]] = add i32 [[V5]], [[V6]]
 ; CHECK-NEXT:    call void @use32(i32 [[R7]])
 ; CHECK-NEXT:    br label [[END_EARLY]]
 ; CHECK:       end.early:
 ; CHECK-NEXT:    call void @sideeffect()
 ; CHECK-NEXT:    br i1 [[COND_LOOP:%.*]], label [[END_EARLY]], label [[END:%.*]]
 ; CHECK:       end:
 ; CHECK-NEXT:    call void @sideeffect()