[LoopFusion] Assert "No dominance relationship between these fusion candidates"

[sjoerdmeijer]

This is split off from #80301 as this looks like a different assert/problem.

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

This IR:

define void @dep_free_parametric(ptr noalias %A, ptr noalias %B, i64 %N, i64 %M) {
entry:
  %cmp = icmp slt i64 0, %M
  br i1 %cmp, label %inverse1, label %inverse2

inverse1:
  br i1 %cmp, label %done, label %A_guard
  
inverse2:
  br i1 %cmp, label %B_guard, label %done

A_guard:
   br i1 %cmp, label %A_preheader, label %A_exit

A_preheader:
  br label %A_loop
 
A_loop:
  %A_iv = phi i64 [ %A_inc, %A_loop ], [ 0, %A_preheader ]
  %A_inc = add nsw i64 %A_iv, 1
  %A_cmp = icmp slt i64 %A_inc, %N
  br i1 %A_cmp, label %A_loop, label %A_exit

A_exit:
  br label %done

B_guard:
   br i1 %cmp, label %B_preheader, label %B_exit

B_preheader:
  br label %B_loop
 
B_loop:
  %B_iv = phi i64 [ %B_inc, %B_loop ], [ 0, %B_preheader ]
  %B_inc = add nsw i64 %B_iv, 1
  %B_cmp = icmp slt i64 %B_inc, %N
  br i1 %B_cmp, label %B_loop, label %B_exit

B_exit:
  br label %done

done:
  ret void
}

triggers this assert:

No dominance relationship between these fusion candidates!
UNREACHABLE executed at /root/llvm-project/llvm/lib/Transforms/Scalar/LoopFuse.cpp:444!
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 <source>
1.	Running pass "function(loop-fusion)" on module "<source>"
2.	Running pass "loop-fusion" on function "dep_free_parametric"
 #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 0x000071c466442520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #3 0x000071c4664969fc pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x969fc)
 #4 0x000071c466442476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #5 0x000071c4664287f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #6 0x00000000058b727a (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x58b727a)
 #7 0x000000000469ff10 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
 #8 0x00000000046ab600 llvm::LoopFusePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x46ab600)

[amehsan]

entry:
%cmp = icmp slt i64 0, %M
br i1 %cmp, label %inverse1, label %inverse2

inverse1:
br i1 %cmp, label %done, label %A_guard

inverse2:
br i1 %cmp, label %B_guard, label %done

currently the conditions above are investigated, and we conclude that the two loops are control flow equivalent. We can argue that this is correct because both loops are unreachable from entry; we go straight to %done and exit the function without executing any of the two loops.

Not sure at the moment what is the best strategy to address this.

If I change the initial conditions to the following, there is no failure (still we need to fix the original IR):

entry:
  %cmp = icmp slt i64 0, %M
  br i1 %cmp, label %inverse1, label %inverse2

inverse1:
  br i1 %cmp, label %A_guard, label %done

inverse2:
  br i1 %cmp, label %done, label %B_guard

@1997alireza Let's discuss this as well. Assign it to you for the moment.

[Meinersbur]

as this looks like a different assert/problem.

Different assert, same problem: "isControlFlowEquivalent" (two BBs are executed under the same logical condition) does not imply a specific CFG structure, in particular: (post-)dominance.

I think that any correct solution involves removing any use of isControlFlowEquivalent from LoopFuse. In literature, I find the use of "control flow equivalence" only in the sense of isomorphism between CFGs (e.g. https://www.sciencedirect.com/science/article/abs/pii/S0167404822000074). The use in LLVM is our own invention.

[amehsan]

I think that any correct solution involves removing any use of isControlFlowEquivalent from LoopFuse. In literature, I find the use of "control flow equivalence" only in the sense of isomorphism between CFGs

I don't remember the details right now, but there was a good reason to check two BBs are executed under the same logical conditions. The implementation may miss something, but as long as we can make it work correctly for loop fusion, we don't need to worry about the fact that it is our own invention.

Also the current code doesn't purely check the condition under which the BBs executed. It also looks at the structure of CFG. (finding the common dominator). Again, I would need to dig into the motivating case here (and recall details), but I wouldn't quickly dismiss the idea due to existence of some bugs and mismatch with how other people use the term.

[amehsan]

but I wouldn't quickly dismiss the idea due to existence of some bugs and mismatch with how other people use the term

That said, I need to dig deeper into it. I may or may not eventually agree with you. I just have a vague memory right now, that there was a case for introducing this. my point here is mainly that, we should not be concerned with the fact that our use of the term is different from literature.

[sjoerdmeijer]

as this looks like a different assert/problem.

Different assert, same problem: "isControlFlowEquivalent" (two BBs are executed under the same logical condition) does not imply a specific CFG structure, in particular: (post-)dominance.

I think that any correct solution involves removing any use of isControlFlowEquivalent from LoopFuse. In literature, I find the use of "control flow equivalence" only in the sense of isomorphism between CFGs (e.g. https://www.sciencedirect.com/science/article/abs/pii/S0167404822000074). The use in LLVM is our own invention.

I am hitting these issues (a lot) in testing, and am hitting them separately. For tracking known test failures, it was easier for me to have separate issues for different behaviour, but if this is a duplicate, feel free to close this.

[madhur13490]

@amehsan, Assigned to you as you are actively looking at it.