[llvm] [M68k] CallSeq assertion failure in SelectionDAG

[knickish]

; RUN: llc < %s -mtriple=m68k-linux | FileCheck %s

define double @minimized() {
start:
  %_58 = call double null(double 0.000000e+00)
  %_60 = load double, ptr null, align 8
  %_57 = fmul double 0.000000e+00, %_60
  store double %_57, ptr null, align 8
  ret double 0.000000e+00
}

fails with .../bin/FileCheck .../llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:510: llvm::SDNode* FindCallSeqStart(llvm::SDNode*, unsigned int&, unsigned int&, const llvm::TargetInstrInfo*): Assertion 'Best' failed.

Something appears to be wrong with the callseq_start/end ordering with these instructions, but not yet sure what the exact problem is

[llvmbot]

@llvm/issue-subscribers-backend-m68k

Author: None (knickish)

```ll ; RUN: llc < %s -mtriple=m68k-linux | FileCheck %s

define double @minimized() {
start:
%_58 = call double null(double 0.000000e+00)
%_60 = load double, ptr null, align 8
%_57 = fmul double 0.000000e+00, %_60
store double %_57, ptr null, align 8
ret double 0.000000e+00
}

fails with `.../bin/FileCheck .../llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:510: llvm::SDNode* FindCallSeqStart(llvm::SDNode*, unsigned int&, unsigned int&, const llvm::TargetInstrInfo*): Assertion 'Best' failed.`

Something appears to be wrong with the `callseq_start/end` ordering with these instructions, but not yet sure what the exact problem is


</details>

[llvmbot]

@llvm/issue-subscribers-bug

Author: None (knickish)

```ll ; RUN: llc < %s -mtriple=m68k-linux | FileCheck %s

define double @minimized() {
start:
%_58 = call double null(double 0.000000e+00)
%_60 = load double, ptr null, align 8
%_57 = fmul double 0.000000e+00, %_60
store double %_57, ptr null, align 8
ret double 0.000000e+00
}

fails with `.../bin/FileCheck .../llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:510: llvm::SDNode* FindCallSeqStart(llvm::SDNode*, unsigned int&, unsigned int&, const llvm::TargetInstrInfo*): Assertion 'Best' failed.`

Something appears to be wrong with the `callseq_start/end` ordering with these instructions, but not yet sure what the exact problem is


</details>

[knickish]

@mshockwave not sure if you're still doing any m68k stuff, but I'm kind of stuck on this and would appreciate some pointers if you have the time/inclination. I went through all the x86 call lowering code and didn't find any large differences that would seem to account for this

[mshockwave]

yeah I think I ran into this problem a few years ago too: https://discourse.llvm.org/t/finding-the-start-sdnode-of-a-call-sequence/62806
Personally I think the fundamental problem is that callseq_start and callseq_end are not connected directly, but through a sequence of chain. Therefore, there is a non-zero chance we might not be able to trace from callseq_end to callseq_start.
On top of that, there is an even more fundamental problem: I think the majority of the targets are no longer doing instruction scheduling on SelectionDAG/ScheduleDAG, but switching to MachineScheduler which does it on MachineIR. So fixing ScheduleDAGRR might not be the most fruitful solution. It might be easier to just switching 68k to using MachineScheduler. I'll play around and see how we can do it.

[mshockwave]

It turned out I was wrong about switching to MachineScheduler -- it wouldn't solve the problem as the routine that tries to find matching callseq_start / callseq_end and caused all these problems here, will always be called.

To be more specific, here is part of the SelectionDAG that triggers the problem:

The aforementioned routine that tries to find a matching callseq_start / callseq_end starts from the bottom of this diagram and goes up along the sequence of chain values. When it hits a TokenFactor, the current algorithm does a DFS-ish search and branch our for each operands of the TokenFactor. For all results returned from different DFS search paths, the current algorithm makes a selection from them by picking the one with largest nested level -- which increases by one for every callseq_end encounters on the way and decreases when it see a callseq_start.

The problem here is that, for the TokenFactor above callseq_end (B), both path have the same nested level, and ScheduleDAGRR simply bails out when there is no absolute maximal nested level, hence the assertion failure we saw here.

There is also other problems like the current algorithm is not really doing a DFS (thus I said "DFS-ish") and might visit a callseq_start twice, which is a problem for counting the nested level. Even it uses a tie-breaker at the TokenFactor above callseq_end (B) to solve the aforementioned problem where every single path has the same nested level, I'm not sure whether new problems will emerge when we backtrack to the bottom TokenFactor (the one above callseq_end (A)).

I eventually solved this problem by rewriting the whole searching routine with a more straightforward, and hopefully more stable algorithm. I'll send the patch shortly.