[LSR] Don't break a critical edge if parent ends with "callbr"

[void]

Summary

The 'callbr' instruction doesn't have a good place to put values from a
split critical edge. This is similar to indirect branch and case switch
instructions.

[nickdesaulniers]

I guess the presence of the profile data makes it difficult to use bugpoint to reduce the test case more?

[MaskRay]

The test should be added in test/Transforms/PGOProfile/, see D87435

[void]

In D94470#2493295, @MaskRay wrote:

The test should be added in test/Transforms/PGOProfile/, see D87435

The error isn't in opt but in llc though. In fact, I don't think it's specific to PGO, but only triggered by it.

[void]

Reduce the testcase.

[void]

In D94470#2493138, @nickdesaulniers wrote:

I guess the presence of the profile data makes it difficult to use bugpoint to reduce the test case more?

It looks like I was able to reduce it. PTAL.

[nickdesaulniers]

In D94470#2493986, @void wrote:

In D94470#2493138, @nickdesaulniers wrote:

I guess the presence of the profile data makes it difficult to use bugpoint to reduce the test case more?

It looks like I was able to reduce it. PTAL.

The test case passes for me on ToT; was it over-reduced perhaps?

[void]

In D94470#2494138, @nickdesaulniers wrote:

In D94470#2493986, @void wrote:

In D94470#2493138, @nickdesaulniers wrote:

I guess the presence of the profile data makes it difficult to use bugpoint to reduce the test case more?

It looks like I was able to reduce it. PTAL.

The test case passes for me on ToT; was it over-reduced perhaps?

It fails for me. Are you running it with assertions enabled?

[nickdesaulniers]

ah! probably not, let me rebuild

[nickdesaulniers]

Patch LGTM; just curious about the comment, since that's not what's occurring in the test AFAICT. Thanks for the patch!

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5594–5595

Can this comment be made more precise, I don't think what's described is what's being tested?

llvm/test/CodeGen/Generic/callbr-critical-edge-splitting.ll

21 ↗

(On Diff #316193)

(I'm surprised we can refer to values in the IR before they've been assigned to).

[MaskRay]

In D94470#2493961, @void wrote:

In D94470#2493295, @MaskRay wrote:

The test should be added in test/Transforms/PGOProfile/, see D87435

The error isn't in opt but in llc though. In fact, I don't think it's specific to PGO, but only triggered by it.

Then it should be in llvm/test/Transforms/LoopStrengthReduce/

[MaskRay]

llvm/test/CodeGen/Generic/callbr-critical-edge-splitting.ll

1 ↗

(On Diff #316193)

Can you write a opt -passes='loop(loop-reduce)' test?

Checking a command returns 0 is not a useful test. Checking some desired instructions makes the test not only useful for one particular regression, but also useful for some other scenarios.

[void]

In D94470#2494271, @MaskRay wrote:

In D94470#2493961, @void wrote:

In D94470#2493295, @MaskRay wrote:

The test should be added in test/Transforms/PGOProfile/, see D87435

The error isn't in opt but in llc though. In fact, I don't think it's specific to PGO, but only triggered by it.

Then it should be in llvm/test/Transforms/LoopStrengthReduce/

This is a code-gen bug. I'm not sure how else to put this. If I run it through opt, it doesn't reproduce.

[void]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5594–5595

It's pretty accurate as is. :) I'm not sure how else to word it.

llvm/test/CodeGen/Generic/callbr-critical-edge-splitting.ll

1 ↗

(On Diff #316193)

It replicates only with llc, not with opt.

21 ↗

(On Diff #316193)

Might be some PHI node weirdness.

[MaskRay]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5594–5595

The change only affects llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp, not any codegen part, so I hope this can be tested with opt. Usually this should check the produced instructions.

If the resulting IR is correct but codegen somehow crashes, then it is probably a codegen bug which should be separately fixed. If the output IR is actually incorrect, then the IR verifier should be fixed instead.

Anyway I think the test should be added in an appropriate place and if this uncovers other issues those other issues should be reported as well.

[nickdesaulniers]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5594–5595

Ah, yes sorry, I was looking at the first phi thinking WTF; didn't notice the second phi until just now.

[void]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5594–5595

It appears that this pass is added only during code-gen:

llvm/lib/CodeGen/TargetPassConfig.cpp:      addPass(createLoopStrengthReducePass());
llvm/lib/Passes/PassBuilder.cpp:#include "llvm/Transforms/Scalar/LoopStrengthReduce.h"
llvm/lib/Passes/PassRegistry.def:LOOP_PASS("loop-reduce", LoopStrengthReducePass())
llvm/lib/Target/NVPTX/NVPTXISelLowering.cpp:/// (LoopStrengthReduce.cpp) and memory optimization for address mode
llvm/lib/Target/NVPTX/NVPTXISelLowering.h:  /// reduction (LoopStrengthReduce.cpp) and memory optimization for
llvm/lib/Transforms/Scalar/CMakeLists.txt:  LoopStrengthReduce.cpp
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp://===- LoopStrengthReduce.cpp - Strength Reduce IVs in Loops --------------===//
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:#include "llvm/Transforms/Scalar/LoopStrengthReduce.h"
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:class LoopStrengthReduce : public LoopPass {
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:  LoopStrengthReduce();
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:LoopStrengthReduce::LoopStrengthReduce() : LoopPass(ID) {
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:  initializeLoopStrengthReducePass(*PassRegistry::getPassRegistry());
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const {
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) {
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:PreservedAnalyses LoopStrengthReducePass::run(Loop &L, LoopAnalysisManager &AM,
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:char LoopStrengthReduce::ID = 0;
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce",
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:INITIALIZE_PASS_END(LoopStrengthReduce, "loop-reduce",
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp:Pass *llvm::createLoopStrengthReducePass() { return new LoopStrengthReduce(); }
llvm/lib/Transforms/Scalar/Scalar.cpp:  initializeLoopStrengthReducePass(Registry);

[nickdesaulniers]

llvm/test/CodeGen/Generic/callbr-critical-edge-splitting.ll

1 ↗

(On Diff #316193)

I'm also having trouble reproducing with opt. If this relies on CodeGen specific transforms, do we need a target triple for the module? https://lists.llvm.org/pipermail/llvm-dev/2020-July/143666.html seems to allude to this problem (I haven't read the whole thread yet to see whether/how it's been resolved).

[nickdesaulniers]

llvm/test/CodeGen/Generic/callbr-critical-edge-splitting.ll

1 ↗

(On Diff #316193)

adding

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

allows

opt -loop-reduce /tmp/foo.ll -S -o -

to repro.

[nickdesaulniers]

llvm/test/CodeGen/Generic/callbr-critical-edge-splitting.ll

1 ↗

(On Diff #316193)

opt -mcpu=alderlake -loop-reduce -S /tmp/foo.ll repros also works; guessing that cpu specifies a datalayout?

[void]

Move testcase.

[void]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5594–5595

Sorry. Fixed.

[MaskRay]

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

10

@fhahn

The exiting edge (%do.body.i.i.rdrand_int.exit.i_crit_edge -> %for.end) is a critical edge.

SplitBlockPredecessors is called with LoopPreds being BBs other than TIBB.
SplitBlockPredecessors asserts if one such BB (%for.cond) has an IndirectBr/CallBr terminator.

24

Perhaps simplify the BB names. For example _crit_edge can be dropped as it is the name introduced by a previous critical edge breaking step.

[void]

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

24

No. Please stop. I'm not going to rename BB names. That's just busy work.

[nickdesaulniers]

@nathanchance also pointed out I had https://reviews.llvm.org/D88438 to fix a similar issue (I forgot about that patch, I should try it with this test case, too).

[void]

• Add FileCheck to testcase.

[nickdesaulniers]

This patch also fixes the test case in D88438 (and D88438 also fixes this test case). So two different ways of solving similar bugs.
(ie. either would fix https://github.com/ClangBuiltLinux/linux/issues/1161 and https://github.com/ClangBuiltLinux/linux/issues/1252). I don't feel strongly either way; maybe reviewers could take a look at both approaches?

[jyknight]

This patch also fixes the test case in D88438 (and D88438 also fixes this test case).

Does that other review fix this test case intrinsically -- in that this patch is definitely not necessary if that is committed? Or might it just be fixed by accident -- e.g. this particular test-case doesn't trigger the problem anymore, but something else might, without this patch?

[nickdesaulniers]

In D94470#2499394, @jyknight wrote:

This patch also fixes the test case in D88438 (and D88438 also fixes this test case).

Does that other review fix this test case intrinsically -- in that this patch is definitely not necessary if that is committed? Or might it just be fixed by accident -- e.g. this particular test-case doesn't trigger the problem anymore, but something else might, without this patch?

From the github links posted above; both traces from the unwind post-failed-assertion look the same. I assume this patch terminates LoopReduce sooner than D88438 would (though SplitCriticalEdge is called from many other passes than just LoopReduce).

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

LSRInstance::LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE,
   unsigned NumUsers = 0;
   for (const IVStrideUse &U : IU) {
     if (++NumUsers > MaxIVUsers) {
       (void)U;
       LLVM_DEBUG(dbgs() << "LSR skipping loop, too many IV Users in " << U
                         << "\n");
       return;
     }
-    // Bail out if we have a PHI on an EHPad that gets a value from a
-    // CatchSwitchInst.  Because the CatchSwitchInst cannot be split, there is
-    // no good place to stick any instructions.
+
     if (auto *PN = dyn_cast<PHINode>(U.getUser())) {
        auto *FirstNonPHI = PN->getParent()->getFirstNonPHI();
        if (isa<FuncletPadInst>(FirstNonPHI) ||
            isa<CatchSwitchInst>(FirstNonPHI))
+         // Bail out if we have a PHI on an EHPad that gets a value from a
+         // CatchSwitchInst. Because the CatchSwitchInst cannot be split, there
+         // is no good place to stick any instructions.
          for (BasicBlock *PredBB : PN->blocks())
            if (isa<CatchSwitchInst>(PredBB->getFirstNonPHI()))
              return;
+
+       // Also bail out if we have a PHI with a value from a block ending in a
+       // CallBrInst, because those also can't be split for similar reasons.
+       for (BasicBlock *PredBB : PN->blocks())
+         if (isa<CallBrInst>(PredBB->getTerminator()))
+           return;
     }
   }
 
 #ifndef NDEBUG
   // All dominating loops must have preheaders, or SCEVExpander may not be able
   // to materialize an AddRecExpr whose Start is an outer AddRecExpr.
   //
   // IVUsers analysis should only create users that are dominated by simple loop

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -loop-reduce | 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"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Test that we don't try to break a critical edge to a block ending in a callbr
+; instruction. See https://github.com/ClangBuiltLinux/linux/issues/1252
+
+define dso_local i32 @test1() local_unnamed_addr {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    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]
+; CHECK:       asm.fallthrough.i.i:
+; CHECK-NEXT:    unreachable
+; CHECK:       cond.true.i:
+; CHECK-NEXT:    br label [[DO_BODY_I_I_DO_BODY_I_I_CRIT_EDGE:%.*]]
+; CHECK:       do.body.i.i.do.body.i.i_crit_edge:
+; CHECK-NEXT:    [[PGOCOUNT711:%.*]] = phi i64 [ [[TMP0:%.*]], [[DO_BODY_I_I_DO_BODY_I_I_CRIT_EDGE]] ], [ 0, [[COND_TRUE_I]] ]
+; CHECK-NEXT:    [[TMP0]] = add nuw nsw i64 [[PGOCOUNT711]], 1
+; CHECK-NEXT:    br i1 true, label [[DO_BODY_I_I_RDRAND_INT_EXIT_I_CRIT_EDGE:%.*]], label [[DO_BODY_I_I_DO_BODY_I_I_CRIT_EDGE]]
+; CHECK:       do.body.i.i.rdrand_int.exit.i_crit_edge:
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[TMP0]], undef
+; CHECK-NEXT:    br i1 true, label [[FOR_END]], label [[FOR_INC:%.*]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[PGOCOUNT_PROMOTED24:%.*]] = phi i64 [ undef, [[FOR_COND]] ], [ [[TMP1]], [[DO_BODY_I_I_RDRAND_INT_EXIT_I_CRIT_EDGE]] ]
+; CHECK-NEXT:    ret i32 undef
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  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
+}