[LoopFusion] Assert "ThisBlock and OtherBlock must be CFG equivalent"

[sjoerdmeijer]

Compilation of this:

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 @_Z3fn1bis() {
entry:
  br i1 true, label %for.inc68, label %for.cond8thread-pre-split

for.cond8thread-pre-split:                        ; preds = %entry
  br i1 false, label %for.inc68, label %for.inc33

for.inc33:                                        ; preds = %for.inc33, %for.cond8thread-pre-split
  br i1 false, label %for.inc33, label %for.cond52.preheader

for.cond52.preheader:                             ; preds = %for.cond52.preheader, %for.inc33
  br i1 false, label %for.cond52.preheader, label %for.inc68

for.inc68:                                        ; preds = %for.cond52.preheader, %for.cond8thread-pre-split, %entry
  br i1 true, label %for.inc68.2, label %for.cond8thread-pre-split.1

for.cond8thread-pre-split.1:                      ; preds = %for.inc68
  br i1 false, label %for.inc68.2, label %for.inc33.1

for.inc33.1:                                      ; preds = %for.inc33.1, %for.cond8thread-pre-split.1
  br i1 false, label %for.inc33.1, label %for.cond52.preheader.1.preheader

for.cond52.preheader.1.preheader:                 ; preds = %for.inc33.1
  ret void

for.inc68.2:                                      ; preds = %for.cond8thread-pre-split.1, %for.inc68
  ret void
}

with -S -passes=loop-fusion results in this crash:

opt: /root/llvm-project/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp:453: bool llvm::nonStrictlyPostDominate(const llvm::BasicBlock*, const llvm::BasicBlock*, const llvm::DominatorTree*, const llvm::PostDominatorTree*): Assertion `isControlFlowEquivalent(*ThisBlock, *OtherBlock, *DT, *PDT) && "ThisBlock and OtherBlock must be CFG equivalent!"' 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 "_Z3fn1bis"
 #0 0x0000000005965e58 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x5965e58)
 #1 0x0000000005962d04 SignalHandler(int, siginfo_t*, void*) Signals.cpp:0:0
 #2 0x0000723070842520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #3 0x00007230708969fc pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x969fc)
 #4 0x0000723070842476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #5 0x00007230708287f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #6 0x000072307082871b (/lib/x86_64-linux-gnu/libc.so.6+0x2871b)
 #7 0x0000723070839e96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
 #8 0x0000000004a9c0b8 llvm::nonStrictlyPostDominate(llvm::BasicBlock const*, llvm::BasicBlock const*, llvm::DominatorTree const*, llvm::PostDominatorTree const*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4a9c0b8)
 #9 0x0000000004686775 std::pair<std::_Rb_tree_iterator<(anonymous namespace)::FusionCandidate>, bool> std::_Rb_tree<(anonymous namespace)::FusionCandidate, (anonymous namespace)::FusionCandidate, std::_Identity<(anonymous namespace)::FusionCandidate>, (anonymous namespace)::FusionCandidateCompare, std::allocator<(anonymous namespace)::FusionCandidate>>::_M_insert_unique<(anonymous namespace)::FusionCandidate const&>((anonymous namespace)::FusionCandidate const&) LoopFuse.cpp:0:0
#10 0x000000000468fe41 (anonymous namespace)::LoopFuser::fuseCandidates() LoopFuse.cpp:0:0
#11 0x0000000004691861 llvm::LoopFusePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4691861)

See also https://godbolt.org/z/999r9Ksez

LLVM IR reduced test came from this C code reproducer:

#include <algorithm>
int a;
short c, b;
long f, g;
char i;
void fn1(bool d, int e, short h) {
  for (int j = 0; j < 10; j += 4) {
    for (char k; k < i; k += 0301)
      ;
    if (g) {
      for (; f;)
        ;
      for (bool l = 0; l < (bool)b; l = 1) {
        for (long m = 4;
             m < std::max(~d, int((signed char)std::max(h, (short)255))) -
                     18446744073709551608;
             m += 2)
          if (e)
            a = 0;
        for (long n = 4;
             n < std::max(~d, int((signed char)std::max(h, (short)255))) -
                     18446744073709551608;
             n += 2)
          for (short o; o < short(); o += 4)
            c = 0;
      }
    }
  }
}

[sjoerdmeijer]

CC: @madhur13490