[LLVM 8.0] Assertion failed: Couldn't find the register class

[TimNN]

The following IR was obtained by compiling libcore with -C opt-level=1 to IR and then minimizing. The LLVM version is from a recent rust-lang/rust commit with some patches to work around other issues.

Compile with llc -O1 to reproduce.

Edit: smaller repro below.

target datalayout = "e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-a:8"
target triple = "avr-unknown-unknown"

%"num::flt2dec::decoder::Decoded" = type { [0 x i8], i64, [0 x i8], i64, [0 x i8], i64, [0 x i8], i16, [0 x i8], i8, [0 x i8] }
%"option::Option<(usize, i16)>" = type { [0 x i8], i8, [4 x i8] }

define void @"core::num::flt2dec::strategy::grisu::format_shortest_opt"(%"option::Option<(usize, i16)>"* noalias nocapture sret dereferenceable(5), %"num::flt2dec::decoder::Decoded"* noalias nocapture readonly dereferenceable(27) %d, [0 x i8]* nonnull %buf.0, i16 %buf.1) unnamed_addr addrspace(1) {
start:
  %1 = add i64 undef, 1
  %2 = mul i64 1, 10
  br i1 undef, label %bb41, label %panic4

bb41:                                             ; preds = %start
  %3 = sub i64 %1, 0
  %4 = mul i64 %2, %3
  call addrspace(1) void @"core::num::flt2dec::strategy::grisu::format_shortest_opt::round_and_weed"(%"option::Option<(usize, i16)>"* noalias nocapture nonnull sret dereferenceable(5) %0, [0 x i8]* nonnull undef, i16 undef, i16 undef, i64 undef, i64 undef, i64 %4, i64 undef, i64 %2)
  ret void

panic4:                                           ; preds = %start
  unreachable
}

declare void @"core::num::flt2dec::strategy::grisu::format_shortest_opt::round_and_weed"(%"option::Option<(usize, i16)>"* noalias nocapture sret dereferenceable(5), [0 x i8]* nonnull, i16, i16, i64, i64, i64, i64, i64) unnamed_addr addrspace(1)

Output:

Assertion failed: (BestRC && "Couldn't find the register class"), function getMinimalPhysRegClass, file /Users/logic/Projects/rustc/dev/src/llvm/lib/CodeGen/TargetRegisterInfo.cpp, line 203.
Stack dump:
0.  Program arguments: llc -O1 min02-man.ll
1.  Running pass 'Function Pass Manager' on module 'min02-man.ll'.
2.  Running pass 'AVR DAG->DAG Instruction Selection' on function '@"core::num::flt2dec::strategy::grisu::format_shortest_opt"'
0  llc                      0x000000010e460d7c llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 60
1  llc                      0x000000010e461349 PrintStackTraceSignalHandler(void*) + 25
2  llc                      0x000000010e45da1d llvm::sys::RunSignalHandlers() + 989
3  llc                      0x000000010e461fd5 SignalHandler(int) + 485
4  libsystem_platform.dylib 0x00007fff7b932f5a _sigtramp + 26
5  llc                      0x000000010d3b1e54 llvm::ScheduleDAGTopologicalSort::DFS(llvm::SUnit const*, int, bool&) + 2724
6  libsystem_c.dylib        0x00007fff7b75d312 abort + 127
7  libsystem_c.dylib        0x00007fff7b725368 basename_r + 0
8  llc                      0x000000010d4a5933 llvm::TargetRegisterInfo::getMinimalPhysRegClass(unsigned int, llvm::MVT) const + 467
9  llc                      0x000000010e0a06fa (anonymous namespace)::ScheduleDAGRRList::PickNodeToScheduleBottomUp() + 2122
10 llc                      0x000000010e09f198 (anonymous namespace)::ScheduleDAGRRList::ListScheduleBottomUp() + 680
11 llc                      0x000000010e09e395 (anonymous namespace)::ScheduleDAGRRList::Schedule() + 1861
12 llc                      0x000000010e0ba057 llvm::ScheduleDAGSDNodes::Run(llvm::SelectionDAG*, llvm::MachineBasicBlock*) + 679
13 llc                      0x000000010e2018b4 llvm::SelectionDAGISel::CodeGenAndEmitDAG() + 11972
14 llc                      0x000000010e1fe840 llvm::SelectionDAGISel::SelectBasicBlock(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, true, false, void>, false, true>, llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, true, false, void>, false, true>, bool&) + 336
15 llc                      0x000000010e1fcb4c llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) + 10524
16 llc                      0x000000010e1f864c llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) + 2636
17 llc                      0x000000010c8a064b llvm::AVRDAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) + 59
18 llc                      0x000000010d0f6721 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) + 449
19 llc                      0x000000010d7a846b llvm::FPPassManager::runOnFunction(llvm::Function&) + 475
20 llc                      0x000000010d7a8a75 llvm::FPPassManager::runOnModule(llvm::Module&) + 117
21 llc                      0x000000010d7a95bb (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) + 1515
22 llc                      0x000000010d7a8d4e llvm::legacy::PassManagerImpl::run(llvm::Module&) + 366
23 llc                      0x000000010d7aa041 llvm::legacy::PassManager::run(llvm::Module&) + 33
24 llc                      0x000000010c39ae48 compileModule(char**, llvm::LLVMContext&) + 24104
25 llc                      0x000000010c394414 main + 5460
26 libdyld.dylib            0x00007fff7b6b1115 start + 1
27 libdyld.dylib            0x0000000000000003 start + 2224353007

[TimNN]

To debug this issue, I added an extra assert in getPhysicalRegisterVT, which is triggered by the repro instead of the one above: https://gist.github.com/2255d0d389b30edbaea43e26bbdbdd1c

While I don't really understand the code, the way it is written suggests to me that the for loop not finding a match should be an error (If someone could confirm that, that would be great).

I ran the LLVM testsuite with the extra assert applied, and except for 11k unsupported tests and 7 failing AVR tests (none of which is hitting the assertion, they are likely failing due to other patches), everything passes.

[TimNN]

Alright, so I don't believe I can properly explain why I think the following, nor am I even remotely sure that it is correct, however here are some thoughts:

• The issue appears to be "interference" between the two calls in bb41 (the mul and the actual call).
• SU1 is scheduled first.
• SU13 is attempted to be scheduled later but there is interference with SU1. The interfering register is 53, which is one higher than last index of a physical register and represents a special "CallResource" register. The interference is registered.
• Later, an attempt is made a solving the interference. It is determined that backtracking won't work.
• At this point, I believe, the code no longer correctly handles our interference: It attempts to solve the issue by inserting a copy. This, of course can't work here because our interference is not caused by an actual physical register.
• While there is an attempt made to gracefully handle this, or a similar error situation, we hit an assert before then. First, an attempt is made to find the type stored in the register. This either triggers the assert added in my patch above or erroneously returns "glue". Afterwards, an attempt is made to determine the physical register class of the found type. This then hits the original assertion, since there is no physical register class for glue.

At this point, I think that I know what is going on, but once again I have no idea how to fix this.

Input DAG


Schedule DAG


[TimNN]

Not quite progress, but:

First of all, here is a much further (by hand) minimized IR:

target triple = "avr-unknown-unknown"

define void @"main"() addrspace(1) {
start:
  %0 = or i64 undef, undef
  br i1 undef, label %mul_and_call, label %fail

mul_and_call:
  %1 = mul i64 %0, %0
  call addrspace(1) void @"three_ints"(i64 undef, i64 %1, i64 %0)
  ret void

fail:
  ret void
}

declare void @"three_ints"(i64, i64, i64) addrspace(1)

Then, two graphs:

GOOD: SUnit DAG from O0


BAD: SUnit DAG from O1


Things to note:

• In both graphs, SU1 is the the call to three_ints and SU2 is the call to mul.
• The call to three_ints requires some arguments to be passed on the stack.
• In the good graph, the ADJCALLSTACK instructions are (or can be) paired (i.e. we have on down/call/up sequence before we have the next down/call/up sequence).
• In the bad graph, this is not possible (if I interpret the colors of the arrows correctly): We are forced to schedule down/down/call/up/call/up. I believe that this may be the issue.

[TimNN]

cc @brainlag: You previously commented on an issue with ADJCALLSTACK* (#103), do you have any ideas here?

[TimNN]

The "bad" transformation happens in RegReductionPQBase::initNodes, more specifically in PrescheduleNodesWithMultipleUses. This means that either

SUnit DAG from O1 before PrescheduleNodesWithMultipleUses


a) PrescheduleNodesWithMultipleUses performs an unsafe transformation or b) the AVR backend doesn't correctly handle the result.

It would be extremely helpful if someone could weigh in on the following questions (which determines if this is a general LLVM or an AVR-specific bug (cc @dylanmckay)):

Are nested ADJCALLSTACK- DOWN / UP pairs valid? i.e. is down/down/up/up valid or only down/up/down/up?

[brainlag]

I would say that nested ADJCALLSTACK down/up pairs are not valid but only some real llvm developers on the mailing list can confirm that for you.

It is really hard to say if a bug is llvm bug or a AVR backend bug. Often the AVR code triggers a bug in llvm no other backend does, because AVR doesn't have enough registers.

[TimNN]

Thanks for the reply! I guess I'll write to the mailing list again.

[TimNN]

LLVM thread: http://lists.llvm.org/pipermail/llvm-dev/2018-October/127077.html

[TimNN]

Well, isn't it nice if a reply to a question starts with "The answer is probably: Nobody knows" :weary:.

In any case, the reply contains some interesting information, the most interesting being

The reason that brought me looking into the whole issue was some pattern getting turned into a compiler library call late. Back then I sidestepped the whole discussion by stopping to emit ADJCALLSTACK UP/DOWN of zero byte call frames https://reviews.llvm.org/D42006 so they wouldn’t nest anymore for the helpers functions in question…

Adding a similar patch to AVR fixes my repro (haven't tried it on all of libcore yet), so maybe that is the way to go.

[dylanmckay]

Patch upstreamed, was already and still is in the cherry-pick.