[LoopFusion] Triggers "SCEVAddRecExpr operand is not available at loop entry"

[sjoerdmeijer]

This IR:

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128-Fn32"
target triple = "aarch64-unknown-linux-gnu"

; Function Attrs: mustprogress
define void @_Z1fPA4_A4_bPA0_i(i64 %0, i1 %tobool.not) #0 {
entry:
  br i1 false, label %for.cond1.preheader.us.preheader, label %for.cond43.preheader

for.cond1.preheader.us.preheader:                 ; preds = %entry
  %add = select i1 %tobool.not, i64 0, i64 0
  br label %for.cond1.preheader.us

for.cond1.preheader.us:                           ; preds = %for.cond12.preheader.us.us.1, %for.cond1.preheader.us.preheader
  %indvars.iv106 = phi i64 [ 0, %for.cond1.preheader.us.preheader ], [ %indvars.iv.next107, %for.cond12.preheader.us.us.1 ]
  %invariant.gep.us = getelementptr i8, ptr null, i64 %indvars.iv106
  br label %for.cond12.preheader.us.us

for.cond12.preheader.us.us:                       ; preds = %for.cond12.preheader.us.us, %for.cond1.preheader.us
  %indvars.iv = phi i64 [ %indvars.iv.next, %for.cond12.preheader.us.us ], [ %0, %for.cond1.preheader.us ]
  %gep.us.us = getelementptr [4 x i8], ptr %invariant.gep.us, i64 %indvars.iv
  %1 = load i8, ptr %gep.us.us, align 1
  %indvars.iv.next = add nsw i64 %indvars.iv, %add
  %cmp9.us.us = icmp slt i64 %indvars.iv, 0
  br i1 %cmp9.us.us, label %for.cond12.preheader.us.us, label %for.cond12.preheader.us.us.1

for.cond12.preheader.us.us.1:                     ; preds = %for.cond12.preheader.us.us
  %indvars.iv.next107 = add i64 %indvars.iv106, 3
  %cmp.us = icmp ult i64 %indvars.iv106, 11
  br i1 %cmp.us, label %for.cond1.preheader.us, label %for.cond12.preheader.us.us.1.for.cond43.preheader_crit_edge

for.cond12.preheader.us.us.1.for.cond43.preheader_crit_edge: ; preds = %for.cond12.preheader.us.us.1
  br label %for.cond43.preheader

for.cond43.preheader:                             ; preds = %for.cond12.preheader.us.us.1.for.cond43.preheader_crit_edge, %entry
  br i1 false, label %for.cond43.preheader.for.cond47.preheader.us_crit_edge, label %for.cond.cleanup45

for.cond43.preheader.for.cond47.preheader.us_crit_edge: ; preds = %for.cond43.preheader
  br label %for.cond47.preheader.us

for.cond47.preheader.us:                          ; preds = %for.cond43.preheader.for.cond47.preheader.us_crit_edge, %for.cond47.preheader.us
  %indvars.iv108 = phi i64 [ %indvars.iv.next109, %for.cond47.preheader.us ], [ 0, %for.cond43.preheader.for.cond47.preheader.us_crit_edge ]
  store i32 0, ptr null, align 4
  %indvars.iv.next109 = add i64 %indvars.iv108, 3
  %cmp44.us = icmp ult i64 %indvars.iv108, 12
  br i1 %cmp44.us, label %for.cond47.preheader.us, label %for.cond47.preheader.us.for.cond.cleanup45_crit_edge

for.cond47.preheader.us.for.cond.cleanup45_crit_edge: ; preds = %for.cond47.preheader.us
  br label %for.cond.cleanup45

for.cond.cleanup45:                               ; preds = %for.cond47.preheader.us.for.cond.cleanup45_crit_edge, %for.cond43.preheader
  ret void

; uselistorder directives
  uselistorder label %for.cond47.preheader.us, { 1, 0 }
}

attributes #0 = { mustprogress }

results in LoopFusion triggering this assert:

opt: /root/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:3706: const llvm::SCEV* llvm::ScalarEvolution::getAddRecExpr(llvm::SmallVectorImpl<const llvm::SCEV*>&, const llvm::Loop*, llvm::SCEV::NoWrapFlags): Assertion `isAvailableAtLoopEntry(Op, L) && "SCEVAddRecExpr operand is not available at loop entry!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace and instructions to reproduce the bug.
Stack dump:
0.	Program arguments: /opt/compiler-explorer/clang-assertions-trunk/bin/opt -o /app/output.s -S -S -passes=loop-fusion <source>
1.	Running pass "function(loop-fusion)" on module "<source>"
2.	Running pass "loop-fusion" on function "_Z1fPA4_A4_bPA0_i"
 #0 0x0000000005989ef8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x5989ef8)
 #1 0x0000000005986da4 SignalHandler(int, siginfo_t*, void*) Signals.cpp:0:0
 #2 0x00007d7df5642520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #3 0x00007d7df56969fc pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x969fc)
 #4 0x00007d7df5642476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #5 0x00007d7df56287f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #6 0x00007d7df562871b (/lib/x86_64-linux-gnu/libc.so.6+0x2871b)
 #7 0x00007d7df5639e96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
 #8 0x0000000004fb8775 llvm::ScalarEvolution::getAddRecExpr(llvm::SmallVectorImpl<llvm::SCEV const*>&, llvm::Loop const*, llvm::SCEV::NoWrapFlags) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4fb8775)
 #9 0x00000000046a5841 llvm::SCEVRewriteVisitor<(anonymous namespace)::LoopFuser::AddRecLoopReplacer>::visit(llvm::SCEV const*) LoopFuse.cpp:0:0
#10 0x00000000046a5ef0 (anonymous namespace)::LoopFuser::dependencesAllowFusion((anonymous namespace)::FusionCandidate const&, (anonymous namespace)::FusionCandidate const&, llvm::Instruction&, llvm::Instruction&, bool, FusionDependenceAnalysisChoice) LoopFuse.cpp:0:0
#11 0x00000000046a5b5b (anonymous namespace)::LoopFuser::dependencesAllowFusion((anonymous namespace)::FusionCandidate const&, (anonymous namespace)::FusionCandidate const&, llvm::Instruction&, llvm::Instruction&, bool, FusionDependenceAnalysisChoice) LoopFuse.cpp:0:0
#12 0x00000000046a6d44 (anonymous namespace)::LoopFuser::dependencesAllowFusion((anonymous namespace)::FusionCandidate const&, (anonymous namespace)::FusionCandidate const&) LoopFuse.cpp:0:0
#13 0x00000000046a821c (anonymous namespace)::LoopFuser::fuseCandidates() LoopFuse.cpp:0:0
#14 0x00000000046aaef1 llvm::LoopFusePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x46aaef1)

when compiled with opt -S -passes=loop-fusion with assertions enabled.

See also: https://godbolt.org/z/ch47jTnrq

The IR reproduced was reproduced from this C-code reproducer:

extern int a[];
int b;
long c;
short d, e;
void f(bool g[][4][4], int h[][0]) {
  for (short i = 0; i < 14; i += 3)
    for (short j = 0; j < 14; j += 4)
      for (short k(c); k < 4; k += !d + 4)
        for (char l; l < e; l++)
          a[k * i] = g[i][k][i];
  for (unsigned m = 2; m < 017; m += 3)
    for (char n = 0; n < 21; n += 2)
      for (int o = 0; o < d; o += 2)
        b = h[2][m];
}

[amehsan]

I will take a look at this one

[amehsan]

Most likely we need to entirely remove the path in loop fusion code that triggers this bug and then this testcase will pass. details below.

Currently there are two paths for dependency check in loop fusion. One relies on DA. The other one relies on rewriting AddRecs in a common loop and then uses SCEV to check whether there is a dependency that prevents fusion or not (at least that is my impression from a quick reading of the code. there is a possibilty that I miss something here)

DA path was very weak before but after the recent changes in #128782 and #146383 this path is now much more capable.

The bug reported here occurs in SCEV path of dep check and I suspect we should be able to entirely remove this path. Right now we go through both paths, and try to prove legality using one of the paths. But with the patches above I doubt that SCEV path is really needed. (Having one DA mechanism is enough work, we shouldn't need two :)

If there is a case that SCEV path can correctly prove independence but DA path fails, it should be an idea for improving DA, but not a reason to keep SCEV path.

As a first check I tested test cases in LoopFusion test directory. Only one fails if we limit loop fusion to use DA. But that one is not fused anyways. The reason for failure is that we check a debug message printed in SCEV pass.

In all likelihood, we need to entirely remove SCEV path and this bug will go away when that happens.

As for the testcase here, when compiled with --loop-fusion-dependence-analysis=da it passes and the loops are fused.