Crash on undef branch with addition

[aykevl]

This piece of IR crashes llc-8 on my laptop. In fact, the first time it managed to crash my whole system, as I didn't notice the memory growing very rapidly. Run it at your own risk:

; ModuleID = 'bugpoint-reduced-simplified.bc'
source_filename = "./testdata/stdlib.go"
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-atmel-none"

define void @"(*strconv.decimal).RoundUp"(i32*) addrspace(1) {
entry:
  br i1 undef, label %deref.nil, label %deref.next

deref.nil:                                      ; preds = %entry
  ret void ; or unreachable

deref.next:                                     ; preds = %entry
  %1 = load i32, i32* %0, align 1
  %2 = add i32 %1, 1
  store i32 %2, i32* %0, align 1
  ret void
}

Actually, the first code I tried to compile simply crashed but that was way too big so I reduced it to this crashing testcase with bugpoint and then further reduced it manually.

I haven't tried tip yet as I don't have a llvm9 build handy.

If you're interested, this is the original code:

// Round a up to nd digits (or fewer).
func (a *decimal) RoundUp(nd int) {
    if nd < 0 || nd >= a.nd {
        return
    }

    // round up
    for i := nd - 1; i >= 0; i-- {
        c := a.d[i]
        if c < '9' { // can stop after this digit
            a.d[i]++
            a.nd = i + 1
            return
        }
    }

    // Number is all 9s.
    // Change to single 1 with adjusted decimal point.
    a.d[0] = '1'
    a.nd = 1
    a.dp++
}

[dsprenkels]

In my case, LLVM seems to just crash:

llc: /home/daan/llvm-project/llvm/lib/CodeGen/ScheduleDAG.cpp:512: void llvm::ScheduleDAGTopologicalSort::InitDAGTopologicalSorting(): Assertion `Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] && "Wrong topological sorting"' failed.
Stack dump:
0.      Program arguments: bin/llc -march=avr ../llvm-project/rust-avr-issue-136.ll 
1.      Running pass 'Function Pass Manager' on module '../llvm-project/rust-avr-issue-136.ll'.
2.      Running pass 'AVR DAG->DAG Instruction Selection' on function '@"(*strconv.decimal).RoundUp"'
 #0 0x00000000023b8f89 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/daan/llvm-project/llvm/lib/Support/Unix/Signals.inc:494:11
 #1 0x00000000023b9139 PrintStackTraceSignalHandler(void*) /home/daan/llvm-project/llvm/lib/Support/Unix/Signals.inc:558:1
 #2 0x00000000023b7a46 llvm::sys::RunSignalHandlers() /home/daan/llvm-project/llvm/lib/Support/Signals.cpp:67:5
 #3 0x00000000023b97db SignalHandler(int) /home/daan/llvm-project/llvm/lib/Support/Unix/Signals.inc:357:1
 #4 0x00007fd333107890 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12890)
 #5 0x00007fd331bb0e97 raise /build/glibc-OTsEL5/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:51:0
 #6 0x00007fd331bb2801 abort /build/glibc-OTsEL5/glibc-2.27/stdlib/abort.c:81:0
 #7 0x00007fd331ba239a __assert_fail_base /build/glibc-OTsEL5/glibc-2.27/assert/assert.c:89:0
 #8 0x00007fd331ba2412 (/lib/x86_64-linux-gnu/libc.so.6+0x30412)
 #9 0x00000000017292e0 llvm::ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() /home/daan/llvm-project/llvm/lib/CodeGen/ScheduleDAG.cpp:510:5
#10 0x00000000020e05d6 (anonymous namespace)::ScheduleDAGRRList::Schedule() /home/daan/llvm-project/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp:370:3
#11 0x00000000020effcd llvm::ScheduleDAGSDNodes::Run(llvm::SelectionDAG*, llvm::MachineBasicBlock*) /home/daan/llvm-project/llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp:64:1
#12 0x00000000021e6d91 llvm::SelectionDAGISel::CodeGenAndEmitDAG() /home/daan/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:953:16
#13 0x00000000021e53e0 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&) /home/daan/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:699:1
#14 0x00000000021e4ecc llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) /home/daan/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:0:7
#15 0x00000000021e256a llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) /home/daan/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:497:22
#16 0x0000000000f147bb llvm::AVRDAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) /home/daan/llvm-project/llvm/lib/Target/AVR/AVRISelDAGToDAG.cpp:61:3
#17 0x000000000152d71a llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /home/daan/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:73:8
#18 0x0000000001a7af68 llvm::FPPassManager::runOnFunction(llvm::Function&) /home/daan/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1648:23
#19 0x0000000001a7b3b2 llvm::FPPassManager::runOnModule(llvm::Module&) /home/daan/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1688:16
#20 0x0000000001a7bb51 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/daan/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1755:23
#21 0x0000000001a7b658 llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/daan/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1868:16
#22 0x0000000001a7c0d1 llvm::legacy::PassManager::run(llvm::Module&) /home/daan/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1899:3
#23 0x0000000000a61e31 compileModule(char**, llvm::LLVMContext&) /home/daan/llvm-project/llvm/tools/llc/llc.cpp:612:41
#24 0x0000000000a604d1 main /home/daan/llvm-project/llvm/tools/llc/llc.cpp:363:13
#25 0x00007fd331b93b97 __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:344:0
#26 0x0000000000a5fb7a _start (bin/llc+0xa5fb7a)
Aborted (core dumped)

LLVM commit: fc59a0326b7c8bf2cf91c0f03cbdd43983608b05

[dylanmckay]

Could be related to #101

From @brainlag's comment

If you compile llvm with asserts you will hit that and don't run into OOM error. I debugged this in the past and IIRC the problem is because 2 nodes in the DAG are glued together > which lead to the cycle. If these 2 nodes would not glued together it would be fine

Definitely sounds like the same issue.

[dylanmckay]

Continuing the discussion on #101.