[MachineVerifier] infinite recursion?

[JonPsson1]

crash22.tar.gz

clang -O3 -march=z15 crash22.i -o a.out -mllvm -disable-licm-promotion -mllvm -unroll-count=4 -mllvm -verify-misched

4.      Running pass 'Machine Instruction Scheduler' on function '@m'                                                                                                                               
  #0 0x000002aa01eadbd8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/ijonpan/llvm-project/install/bin/clang-20+0x1eadbd8)
  #1 0x000002aa01eab6e0 llvm::sys::RunSignalHandlers() (/home/ijonpan/llvm-project/install/bin/clang-20+0x1eab6e0)                   
  #2 0x000002aa01eab8c4 SignalHandler(int) Signals.cpp:0:0                                                                                                                                          
  #3 0x000002aa08e0f45e                                                                                                                                                                             
  #4 0x000002aa0128383e llvm::DenseMapBase<llvm::DenseMap<llvm::MachineBasicBlock const*, (anonymous namespace)::MachineVerifier::BBInfo, llvm::DenseMapInfo<llvm::MachineBasicBlock const*, void>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock const*, (anonymous namespace)::MachineVerifier::BBInfo>>, llvm::MachineBasicBlock const*, (anonymous namespace)::MachineVerifier::BBInfo, llvm::D
enseMapInfo<llvm::MachineBasicBlock const*, void>, llvm::detail::DenseMapPair<llvm::MachineBasicBlock const*, (anonymous namespace)::MachineVerifier::BBInfo>>::FindAndConstruct(llvm::MachineBasicBlock const* const&) MachineVerifier.cpp:0:0
  #5 0x000002aa01283a64 (anonymous namespace)::MachineVerifier::markReachable(llvm::MachineBasicBlock const*) MachineVerifier.cpp:0:0
  #6 0x000002aa01283abc (anonymous namespace)::MachineVerifier::markReachable(llvm::MachineBasicBlock const*) MachineVerifier.cpp:0:0

...
#254 0x000002aa01283abc (anonymous namespace)::MachineVerifier::markReachable(llvm::MachineBasicBlock const*) MachineVerifier.cpp:0:0
#255 0x000002aa01283abc (anonymous namespace)::MachineVerifier::markReachable(llvm::MachineBasicBlock const*) MachineVerifier.cpp:0:0
clang: error: unable to execute command: Segmentation fault (core dumped)
clang: error: clang frontend command failed due to signal (use -v to see invocation)

@arsenm @michaelmaitland

[michaelmaitland]

Could you clarify what issue you are seeing? The title says infinite recursion but you posted a crash and marked as crash-on-valid.

When I give it a go, I am seeing no termination (cannot reproduce the crash you posted). I am not seeing termination even if I remove -mllvm -verify-misched. It is the -unroll-count=4 that seems to be causing the non-termination for me. Is it possible that this has to do with the loop unroller and not MachineVerifier?

[JonPsson1]

Thanks for taking a look.

If I remove the -verify-misched, it terminates, which is why I thought the problem was in the verifier (and assumed the input was valid). On my machine it terminates after 50s without the verifier, crashes after 39s. Eventhough this is a program of only 35 lines, it has a loop nest with 5 levels, so maybe this is one of those rare cases that are super slow to begin with. The verifier shouldn't crash, though, ideally.

I ran it again on a machine with lots more memory (128Gb), and this time the verifier completed after 13 minutes. Not sure if that makes sense (why wouldn't swapping start with 16Gb RAM...?). It completed without the verifier in 24s.

I'll close this if you think this is isn't worth investigating...

[michaelmaitland]

I did a ctrl-c before ~39s, assuming that I was already hitting non-termination.

Here is what I found on second look:

• It completes without the verifier after 90s without crashing
• Without -unroll-count=4 but keep verify-misched it terminates in under 1s.
• I believe you that it will terminate after a long time with both options (but I did not try it)

There are two things here:

1. Should unroll-count=4 take as long as it does?

   I'm not sure since I am not too familiar with this area of the compiler. My understanding is that we are unrolling a 5x loop nest, so I wouldn't be too surprised if we should expect it to take some time to unroll.

2. Should MachineVerifier take as long as it does?

   The final .s file is a pretty significant number of LOC (800k+). I don't know if we should expect the verifier to finish quickly. It could be nice to emit a warning when the verifier is run on a really large program that it might take some time to finish.

I would be interested to know what others think.

[arsenm]

It would be good to know if it actually doesn't complete or is just slow. It would be good to speed up the verifier. Is this the path it hits when it isn't using LiveIntervals?

[JonPsson1]

I suspect that the loop-unrolling may relate to deep SCEV computations which I have seen (and reported) before in cases where it crashed, but not sure. It was said then that this was a "known issue" or something along those lines...

I guess if the verifier actually completes on a bigger machine the issue I was seeing (verifier crash) may not be quite as serious as i thought - it's an implementation that may run out of memory, not anything like an infinite recursion. Maybe it could be improved in the area encountered here with so many markReachable() calls...?