BreakCriticalEdges: do not split the critical edge from a CallBr indirect successor

[nickdesaulniers]

Summary

Otherwise we'll fail the assertion in SplitBlockPredecessors() related
to splitting the edges from CallBr's.

Fixes: https://github.com/ClangBuiltLinux/linux/issues/1161
Fixes: https://github.com/ClangBuiltLinux/linux/issues/1252

[void]

I believe that a critical edge may be split on the default path, but not the indirect path.

[nickdesaulniers]

In D88438#2304941, @void wrote:

I believe that a critical edge may be split on the default path, but not the indirect path.

I don't think https://github.com/llvm/llvm-project/commit/2fe457690da0fc38bc7f9f1d0aee2ba6a6a16ada made a similar distinction?

I think if I add a bool CallBrInst::isIndirectDest(BasicBlock&); method, I would be able to use that here and in the above cases linked without regressing the test case added in the above link.

The concept of splitting a critical edge is still relatively new to me; any thoughts on *why* it would not be ok to split a critical branch of an indirect-like jump?

[nickdesaulniers]

(oh, I never git add'ed my test case, let me do so now).

[nickdesaulniers]

• add test case

[nickdesaulniers]

llvm/test/CodeGen/PowerPC/loop-reduce-callbr.ll

1 ↗

(On Diff #295437)

is there a better way to express: "this should not trip an assertion build?"

5 ↗

(On Diff #295437)

TODO(Nick): delete

[efriedma]

The concept of splitting a critical edge is still relatively new to me; any thoughts on *why* it would not be ok to split a critical branch of an indirect-like jump?

The problem has to do with blockaddress.

For normal branches, splitting an edge is usually straightforward: you just introduce a new block that branches to the original block, and then you rewrite the branch in the predecessor. But suppose you have a block with two indirectbr predecessors, and you want to split the edge. In that case, the "rewrite the branch" step doesn't work: you can't rewrite the address argument to the indirectbr. (Or at least, you can't without performing some invasive rewrite like indirectbr->switch lowering.)

[efriedma]

llvm/test/CodeGen/PowerPC/loop-reduce-callbr.ll

1 ↗

(On Diff #295437)

Just running opt will automatically check the exit code, so this works. Generally you'd want to add a few CHECK lines to ensure loop-reduce is actually doing what you expect it to, though, so the test doesn't bitrot.

[void]

In D88438#2305068, @efriedma wrote:

The concept of splitting a critical edge is still relatively new to me; any thoughts on *why* it would not be ok to split a critical branch of an indirect-like jump?

The problem has to do with blockaddress.

For normal branches, splitting an edge is usually straightforward: you just introduce a new block that branches to the original block, and then you rewrite the branch in the predecessor. But suppose you have a block with two indirectbr predecessors, and you want to split the edge. In that case, the "rewrite the branch" step doesn't work: you can't rewrite the address argument to the indirectbr. (Or at least, you can't without performing some invasive rewrite like indirectbr->switch lowering.)

Correkt. We had a long discussion during the original implementation. I eventually relented, because I couldn't figure out a way to implement it without making the code unbearably horrible.

The best way to think about critical edges is to imagine trying to resolve a PHI node in block BB. The PHI node is a pseudo instruction, which has to become a concrete instruction during code gen. Let's take a simple case where the value is an immediate: 42 on branch A (from predecessor P1) and 37 on branch B (from predecessor P2), and further that the result of the PHI node is some register rN. When resolving the PHI node, you'll push rN <- 42 to the bottom of P1 and rN <- 37 to the bottom of P2. Nice!

Now if you have critical edges, things get messy. You can no longer push rN <- 42 and rN <- 37 into the predecessor blocks, because rN may be used for another value on edges not going to BB. In this case, we "split" the critical edge. I.e. we create an empty block between P1 and BB on edge A and another between P2 and BB on edge B. This provides us with a place to insert the rN <- 42 and rN <- 37 instructions respectively.

[void]

In D88438#2304953, @nickdesaulniers wrote:

In D88438#2304941, @void wrote:

I believe that a critical edge may be split on the default path, but not the indirect path.

I don't think https://github.com/llvm/llvm-project/commit/2fe457690da0fc38bc7f9f1d0aee2ba6a6a16ada made a similar distinction?

Yeah. I made an error there...

I think if I add a bool CallBrInst::isIndirectDest(BasicBlock&); method, I would be able to use that here and in the above cases linked without regressing the test case added in the above link.

It should be enough that the block isn't the default destination. (Though recent bug reports seem troubling for this.)

I don't know if it's important enough to allow splitting default edges right now. It may be okay to wait.

[nickdesaulniers]

• rebase, fix check for only non-default destination edges as per Bill
• looks like this also fixes Fixes: https://github.com/ClangBuiltLinux/linux/issues/1252 / D94470
• Added test case from D94470.

[nickdesaulniers]

• remove comment from test, simplify lambda

[nickdesaulniers]

• mv my test

[nickdesaulniers]

• add comments and FileCheck to tests

[nickdesaulniers]

In D88438#2305129, @void wrote:

In D88438#2305068, @efriedma wrote:

The concept of splitting a critical edge is still relatively new to me; any thoughts on *why* it would not be ok to split a critical branch of an indirect-like jump?

The problem has to do with blockaddress.

For normal branches, splitting an edge is usually straightforward: you just introduce a new block that branches to the original block, and then you rewrite the branch in the predecessor. But suppose you have a block with two indirectbr predecessors, and you want to split the edge. In that case, the "rewrite the branch" step doesn't work: you can't rewrite the address argument to the indirectbr. (Or at least, you can't without performing some invasive rewrite like indirectbr->switch lowering.)

Isn't "the address argument in the indirectbr" derived from a blockaddress? So couldn't you just find the blockaddress and rewrite it (or create a new one) that referred to the newly created block?

Correkt. We had a long discussion during the original implementation. I eventually relented, because I couldn't figure out a way to implement it without making the code unbearably horrible.

The best way to think about critical edges is to imagine trying to resolve a PHI node in block BB. The PHI node is a pseudo instruction, which has to become a concrete instruction during code gen. Let's take a simple case where the value is an immediate: 42 on branch A (from predecessor P1) and 37 on branch B (from predecessor P2), and further that the result of the PHI node is some register rN. When resolving the PHI node, you'll push rN <- 42 to the bottom of P1 and rN <- 37 to the bottom of P2. Nice!

Now if you have critical edges, things get messy. You can no longer push rN <- 42 and rN <- 37 into the predecessor blocks, because rN may be used for another value on edges not going to BB. In this case, we "split" the critical edge. I.e. we create an empty block between P1 and BB on edge A and another between P2 and BB on edge B. This provides us with a place to insert the rN <- 42 and rN <- 37 instructions respectively.

Thanks! I found https://www.inf.ed.ac.uk/teaching/courses/copt/lecture-4-from-ssa.pdf pretty instructive, too.

[nickdesaulniers]

• run the same invocations for both tests, remove unnecessary target_triple

[jyknight]

Looks totally reasonable to me.

[MaskRay]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

Just use the new PM way: -passes='loop(loop-reduce)'

4

Please add some CHECK lines to prevent bitrot.

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

4

Beyond the one related to actual critical edge? Aren't those just noise?

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

If I do that for both tests:

1. this one passes before this patch has been applied. (bad)(lol, wut)
2. the other test still fails. (good)

Is there something funny with NPM that I need to specify additional passes in addition to loop(loop-reduce)?

[MaskRay]

LGTM.

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

4

One RUN line opt -passes='loop(loop-reduce)' %s is sufficient.

-passes=loop-reduce is the same, just getting an implicit loop pass adapter.

The legacy PM test does not add too much value for new tests as we'll soon make a switch.

16

-NEXT

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting2.ll

24

-NEXT

[nickdesaulniers]

• use CHECK-NEXT, drop -passes=loop-reduce

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

Let me be more precise:

Before this patch is applied:

-loop-reduce:

callbr-critical-edge-splitting.ll:  fail
callbr-critical-edge-splitting2.ll: fail

-passes=loop-reduce:

callbr-critical-edge-splitting.ll:  pass (WTF)
callbr-critical-edge-splitting2.ll: fail

-passes='loop(loop-reduce)':

callbr-critical-edge-splitting.ll:  pass (WTF)
callbr-critical-edge-splitting2.ll: fail

So I guess it makes sense to drop -passes=loop-reduce if that's covered by -passes='loop(loop-reduce)', but it's curious to me from a TDD perspective why the test is green pre-patch for one pass manager (the new one) and red pre-patch for another pass manager (the old one).

The legacy PM test does not add too much value for new tests as we'll soon make a switch.

But the test is red pre-patch for legacy PM. WTF

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

The output between -debug-only=loop-pass is a bit different between -loop-reduce and -passes='loop(loop-reduce)' as well...

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

Interesting, ok, so -print-after-all shows that -loop-reduce (ie. old PM) runs more passes than just -loop-reduce. Looks like -loop-reduce additionally runs:

1. -loop-simplify
2. -loop-reduce
3. -verify

I don't know how to run -loop-simplify with NPM (guessed: -passes='loop(loop-simplify,loop-reduce)'; doesn't work), but if I did I guess that might also make callbr-critical-edge-splitting2.ll pass pre-patch.

In that case, unless it's possible to run -loop-simplify with NPM, then I think I will simply drop the OPM run from callbr-critical-edge-splitting2.ll, since it doesn't add any signal, but keep OPM for callbr-critical-edge-splitting.ll since it does. Thoughts?

[nickdesaulniers]

drop old pass manager test from callbr-critical-edge-splitting2.ll since it does not add signal

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

Aha, -passes='loop-simplify,loop(loop-reduce)'!

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

I would have expected -passes='loop-simplify,loop(loop-reduce)' (new pass manager) to fail pre-patch similar to -lood-reduce (old pass manager). It does not. I'm out of ideas here. Anyone know any tips or reasons why we get different results between new and old pass manager for loop reduction?

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

similar to -lood-reduce

similar to -loop-reduce (I don't have it misspelled locally or copy+paste mistakes)

Otherwise, I'm thinking of committing this as is.

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

@aeubanks I saw https://lists.llvm.org/pipermail/llvm-dev/2021-January/147695.html / https://bugs.llvm.org/show_bug.cgi?id=46649; is this thread of questions about different behavior between OPM and NPM something we should worry about?

[aeubanks]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

The new PM will run LCSSA and LoopSimplify before any loop passes: https://github.com/llvm/llvm-project/blob/6227069bdce6b0c3c22f0a0c8f1aef705985125a/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h#L415.

The legacy PM does not by default, but the loop-reduce legacy pass depends on loop-simplify. Adding -loop-simplify -lcssa at the beginning will probably make both RUN lines behave the same. Or just you can make the input already in LCSSA form.

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

I tried -passes='loop-simplify,lcssa,loop(loop-reduce)' (and -passes='loop-simplify,lcssa,loop-reduce'), but callbr-critical-edge-splitting.ll still seems to pass before this patch is applied, which is unexpected. So there's still something different here between pass managers. (Also, I'm surprised that -print-after-all and -print-before-all don't seem to mention anything related to lcssa for LPM/OPM.)

Ok, this is weird: comparing the output of -print-before-all between -loop-reduce and -passes='loop-simplify,loop(loop-reduce)':

-loop-reduce:

*** IR Dump Before Canonicalize natural loops ***
*** IR Dump Before Loop Strength Reduction ***

-passes='loop-simplify,loop(loop-reduce)':

*** IR Dump Before VerifierPass ***
*** IR Dump Before LoopSimplifyPass ***
*** IR Dump Before LoopSimplifyPass ***
*** IR Dump Before LCSSAPass ***
*** IR Dump Before LoopStrengthReducePass ***
*** IR Dump Before LoopStrengthReducePass ***
*** IR Dump Before VerifierPass ***
*** IR Dump Before PrintModulePass ***

Canonicalize natural loops looks to me like loop-simplify, and yet when I explicitly run loop-simplify via NPM, the printed pass name is LoopSimplifyPass (I would have expected Canonicalize natural loops). What is going on?

[nickdesaulniers]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

llvm-project/llvm/lib/Transforms/Utils/LoopSimplify.cpp has the following:

INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
                "Canonicalize natural loops", false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
                "Canonicalize natural loops", false, false)

so it looks like -loop-simplify is silently running 3 additional passes? (That's annoying that those passes don't print anything via -print-before-all, unless they're not being run). Looking at DominatorTreeWrapperPass, it looks like that's not ported to run with NPM? Same for LoopInfoWrapperPass.

At this point; I'm just going to commit this test invoking both pass managers: this is a bug visible with LPM, but it should not regress for NPM.

[aeubanks]

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

2

Canonicalize natural loops = LoopSimplifyPass. The naming is different for implementation reasons.

AssumptionCacheTracker/DomTree/LoopInfo are analysis passes that the pass uses, they won't show up in --print-before/after-all. The new PM has a different way of querying analyses.

The legacy PM doesn't automatically run LCSSA, so you won't see it unless the pass depends on it.

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

BasicBlock *llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
   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.
+  // or CallBr 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
+      // The only way 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;
+      for (BasicBlock *P : predecessors(DestBB)) {
         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());
+            const Instruction *T = Pred->getTerminator();
+            if (const auto *CBR = dyn_cast<CallBrInst>(T))
+              return CBR->getDefaultDest() != Pred;
+            return isa<IndirectBrInst>(T);
           })) {
         if (Options.PreserveLoopSimplify)
           return nullptr;
         LoopPreds.clear();
       }
     }
   }
 

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

+; RUN: opt -loop-reduce %s -o - -S | FileCheck %s
+; RUN: opt -passes='loop(loop-reduce)' %s -o - -S | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+define dso_local i32 @test1() local_unnamed_addr {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+; It's ok to modify this test in the future should be able to split critical
+; edges here, just noting that this is the critical edge that we care about.
+; CHECK: callbr void asm sideeffect "", "X,X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@test1, %cond.true.i), i8* blockaddress(@test1, %for.end))
+; CHECK-NEXT: to label %asm.fallthrough.i.i [label %cond.true.i, label %for.end]
+  callbr void asm sideeffect "", "X,X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@test1, %cond.true.i), i8* blockaddress(@test1, %for.end))
+          to label %asm.fallthrough.i.i [label %cond.true.i, label %for.end]
+
+asm.fallthrough.i.i:                              ; preds = %for.cond
+  unreachable
+
+cond.true.i:                                      ; preds = %for.cond
+  br label %do.body.i.i.do.body.i.i_crit_edge
+
+do.body.i.i.do.body.i.i_crit_edge:                ; preds = %do.body.i.i.do.body.i.i_crit_edge, %cond.true.i
+  %pgocount711 = phi i64 [ %0, %do.body.i.i.do.body.i.i_crit_edge ], [ 0, %cond.true.i ]
+  %0 = add nuw nsw i64 %pgocount711, 1
+  br i1 undef, label %do.body.i.i.rdrand_int.exit.i_crit_edge, label %do.body.i.i.do.body.i.i_crit_edge
+
+do.body.i.i.rdrand_int.exit.i_crit_edge:          ; preds = %do.body.i.i.do.body.i.i_crit_edge
+  %1 = add i64 %0, undef
+  br i1 undef, label %for.end, label %for.inc
+
+for.inc:                                          ; preds = %do.body.i.i.rdrand_int.exit.i_crit_edge
+  br label %for.cond
+
+for.end:                                          ; preds = %do.body.i.i.rdrand_int.exit.i_crit_edge, %for.cond
+  %pgocount.promoted24 = phi i64 [ undef, %for.cond ], [ %1, %do.body.i.i.rdrand_int.exit.i_crit_edge ]
+  ret i32 undef
+}

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting2.ll

+; RUN: opt -passes='loop(loop-reduce)' %s -o - -S | FileCheck %s
+
+; Required metadata to trigger previously failing assertion.
+target datalayout = "e-m:e-i64:64-n32:64"
+
+@f = external dso_local local_unnamed_addr global i32, align 4
+
+declare i32 @a() local_unnamed_addr
+declare i32 @e(i32) local_unnamed_addr
+
+define dso_local i32 @b() {
+entry:
+  %call = tail call i32 @a()
+  %tobool.not = icmp eq i32 %call, 0
+  br i1 %tobool.not, label %cleanup.cont.critedge, label %if.then
+
+if.then:                                          ; preds = %entry
+; It's ok to modify this test in the future should be able to split critical
+; edges here, just noting that this is the critical edge that we care about.
+; CHECK: callbr void asm sideeffect "", "X"(i8* blockaddress(@b, %cleanup.cont.critedge))
+; CHECK-NEXT: to label %return [label %cleanup.cont.critedge]
+  callbr void asm sideeffect "", "X"(i8* blockaddress(@b, %cleanup.cont.critedge))
+          to label %return [label %cleanup.cont.critedge]
+
+cleanup.cont.critedge:                            ; preds = %entry, %if.then
+  br label %return
+
+return:                                           ; preds = %if.then, %cleanup.cont.critedge
+  %retval.0 = phi i32 [ 4, %cleanup.cont.critedge ], [ 0, %if.then ]
+  ret i32 %retval.0
+}
+
+define dso_local i32 @do_pages_move_nr_pages() local_unnamed_addr {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %if.end3, %entry
+  %g.0 = phi i32 [ undef, %entry ], [ %inc, %if.end3 ]
+  %0 = load i32, i32* @f, align 4
+  %tobool.not = icmp eq i32 %0, 0
+  br i1 %tobool.not, label %if.end3, label %if.then
+
+if.then:                                          ; preds = %for.cond
+  %call.i = tail call i32 @a()
+  %tobool.not.i = icmp eq i32 %call.i, 0
+  br i1 %tobool.not.i, label %if.then2, label %if.then.i
+
+if.then.i:                                        ; preds = %if.then
+  callbr void asm sideeffect "", "X"(i8* blockaddress(@do_pages_move_nr_pages, %if.then2))
+          to label %if.end3 [label %if.then2]
+
+if.then2:                                         ; preds = %if.then, %if.then.i
+  %g.0.lcssa = phi i32 [ %g.0, %if.then ], [ %g.0, %if.then.i ]
+  %call4 = tail call i32 @e(i32 %g.0.lcssa)
+  ret i32 undef
+
+if.end3:                                          ; preds = %for.cond, %if.then.i
+  %inc = add nsw i32 %g.0, 1
+  br label %for.cond
+}
+