[LoopFusion] Assertion "DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock())"

[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"

define void @_Z1dbPA2_A2_lPA2_A2_iS1_() {
entry:
  br i1 false, label %if.else.1, label %for.inc23.1

if.else.1:                                        ; preds = %entry
  br i1 false, label %if.else.2, label %for.body8.1

for.body8.1:                                      ; preds = %for.body8.1, %if.else.1
  br i1 false, label %for.body8.1, label %if.else.2

for.inc23.1:                                      ; preds = %entry
  br i1 false, label %if.else.2, label %if.else.3

if.else.2:                                        ; preds = %for.inc23.1, %for.body8.1, %if.else.1
  br i1 false, label %if.else.3, label %for.body8.2

for.body8.2:                                      ; preds = %for.body8.2, %if.else.2
  br i1 false, label %for.body8.2, label %if.else.3

if.else.3:                                        ; preds = %for.body8.2, %if.else.2, %for.inc23.1
  ret void
}

Triggers this assert in LoopFusion:

opt: /root/llvm-project/llvm/lib/Transforms/Scalar/LoopFuse.cpp:1441: bool {anonymous}::LoopFuser::dependencesAllowFusion(const {anonymous}::FusionCandidate&, const {anonymous}::FusionCandidate&): Assertion `DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock())' 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 -passes=loop-fusion -S <source>
1.	Running pass "function(loop-fusion)" on module "<source>"
2.	Running pass "loop-fusion" on function "_Z1dbPA2_A2_lPA2_A2_iS1_"
 #0 0x00000000059a4608 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x59a4608)
 #1 0x00000000059a14b4 SignalHandler(int, siginfo_t*, void*) Signals.cpp:0:0
 #2 0x000075e1da242520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #3 0x000075e1da2969fc pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x969fc)
 #4 0x000075e1da242476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #5 0x000075e1da2287f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #6 0x000075e1da22871b (/lib/x86_64-linux-gnu/libc.so.6+0x2871b)
 #7 0x000075e1da239e96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
 #8 0x00000000046c3deb (anonymous namespace)::LoopFuser::dependencesAllowFusion((anonymous namespace)::FusionCandidate const&, (anonymous namespace)::FusionCandidate const&) LoopFuse.cpp:0:0
 #9 0x00000000046c511c (anonymous namespace)::LoopFuser::fuseCandidates() LoopFuse.cpp:0:0
#10 0x00000000046c7df1 llvm::LoopFusePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x46c7df1)

See also: https://godbolt.org/z/78E5G4GdY

Reproduced from this source code reproducer:

int a, c;
extern char b;
void d(bool e, long f[][2][2], int g[][2][2], long h[][2][2]) {
  for (short i;; i += 3)
    for (short j = 0; j < short(27 - 704147732729819636) - 3601; j += 3)
      if (h[1][1][i])
        b = 0;
      else
        for (int k(e); k < 22; k += 3)
          if (f[3][1][1] != f[2][3][i])
            a = c = g[3][i][3];
}

[amehsan]

This is likely similar to two other issues, related to dominance. I seem to be done with DA. I will start looking into the issue of how we check dominance in loop fuse tomorrow.

[amehsan]

Same problem as #166560

IsControlFlowEquivalent returns true but the entry block of the two guarded loops do not dominate each other. I expect the fix suggested in the edits of this #166560 (comment) will fix this issue as well.

[amehsan]

Same problem as #166560

IsControlFlowEquivalent returns true but the entry block of the two guarded loops do not dominate each other. I expect the fix suggested in the edits of this #166560 (comment) will fix this issue as well.

As reflected in the edits of my comment on #166560 my understanding of it changed a little bit. So I need to double check this issue again to make sure this is the same issue. Will do this tomorrow.

---

EDIT: Yes, I confirmed this is caused by the flexible isControlFlowEquivalent. entry block of FC0 is if.else.1 and entry block of FC1 is if.else.2 which is not dominated by if.else.1 but the assertion requires the dominance.