Assertion failure "There should be at least one conflict." in register coalescing

Hi,

Please take a look at this MIR:

name: f
body: |
   bb.0:
     %0:gr64_with_sub_8bit = COPY $rax
     %1:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit
     %2:gr32 = COPY %1:gr32
     %0.sub_32bit:gr64_with_sub_8bit = COPY %2:gr32
     %3:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit
     %1:gr32 = MOV32rr %2:gr32
     %0.sub_32bit:gr64_with_sub_8bit = COPY %2:gr32

This is heavily reduced from real code, translated to X86 to rule out
the possibility of a bug in the target's register definitions.

When running the Simple Register Coalescing pass on this:

   llc -run-pass=simple-register-coalescing test.mir

It triggers an assert:

   llc: /home/harald/llvm/lib/CodeGen/RegisterCoalescer.cpp:2864: bool {anonymous}::JoinVals::resolveConflicts({anonymous}::JoinVals&): Assertion `!TaintExtent.empty() && "There should be at least one conflict."' failed.
   Stack dump:
   0. Program arguments: llvm/build/bin/llc -run-pass=simple-register-coalescing testx86.mir
   1. Running pass 'Function Pass Manager' on module 'testx86.mir'.
   2. Running pass 'Simple Register Coalescing' on function '@f'
    #0 0x0000563febf583f3 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/harald/llvm/lib/Support/Unix/Signals.inc:532:22
    #1 0x0000563febf58486 PrintStackTraceSignalHandler(void*) /home/harald/llvm/lib/Support/Unix/Signals.inc:593:1
    #2 0x0000563febf56334 llvm::sys::RunSignalHandlers() /home/harald/llvm/lib/Support/Signals.cpp:68:20
    #3 0x0000563febf57dac SignalHandler(int) /home/harald/llvm/lib/Support/Unix/Signals.inc:384:1
    #4 0x00007fdc53042f40 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x13f40)
    #5 0x00007fdc52aebed7 gsignal /build/glibc-KRRWSm/glibc-2.29/signal/../sysdeps/unix/sysv/linux/internal-signals.h:84:10
    #6 0x00007fdc52acd535 abort /build/glibc-KRRWSm/glibc-2.29/stdlib/abort.c:81:7
    #7 0x00007fdc52acd40f __tls_get_addr /build/glibc-KRRWSm/glibc-2.29/intl/loadmsgcat.c:1177:9
    #8 0x00007fdc52add012 (/lib/x86_64-linux-gnu/libc.so.6+0x35012)
    #9 0x0000563feb388d39 (anonymous namespace)::JoinVals::resolveConflicts((anonymous namespace)::JoinVals&) /home/harald/llvm/lib/CodeGen/RegisterCoalescer.cpp:2864:5
   #10 0x0000563feb38b2ee (anonymous namespace)::RegisterCoalescer::joinVirtRegs(llvm::CoalescerPair&) /home/harald/llvm/lib/CodeGen/RegisterCoalescer.cpp:3323:45
   #11 0x0000563feb38bc86 (anonymous namespace)::RegisterCoalescer::joinIntervals(llvm::CoalescerPair&) /home/harald/llvm/lib/CodeGen/RegisterCoalescer.cpp:3417:1
   #12 0x0000563feb3853f3 (anonymous namespace)::RegisterCoalescer::joinCopy(llvm::MachineInstr*, bool&) /home/harald/llvm/lib/CodeGen/RegisterCoalescer.cpp:1868:7
   #13 0x0000563feb38c1cf (anonymous namespace)::RegisterCoalescer::copyCoalesceWorkList(llvm::MutableArrayRef<llvm::MachineInstr*>) /home/harald/llvm/lib/CodeGen/RegisterCoalescer.cpp:3501:28
   #14 0x0000563feb38d0a9 (anonymous namespace)::RegisterCoalescer::joinAllIntervals() /home/harald/llvm/lib/CodeGen/RegisterCoalescer.cpp:3663:30
   #15 0x0000563feb38d3f0 (anonymous namespace)::RegisterCoalescer::runOnMachineFunction(llvm::MachineFunction&) /home/harald/llvm/lib/CodeGen/RegisterCoalescer.cpp:3710:17

This is with current LLVM trunk (r374866), but it is not new. When
running this with the Ubuntu-provided llc 8, it segfaults. Presumably
this has assertions disabled, and would have asserted otherwise.

Is this MIR valid? Does it contain something that Simple Register
Coalescing expects to have been removed by a previous pass already?

The extra output with -debug-only=regalloc is:

   Computing live-in reg-units in ABI blocks.
   Created 0 new intervals.
   ********** INTERVALS **********
   %0 [16r,64r:2)[64r,112r:1)[112r,112d:0) 0@112r 1@64r 2@16r weight:0.000000e+00
   %1 [32r,48r:1)[96r,96d:0) 0@96r 1@32r weight:0.000000e+00
   %2 [48r,112r:0) 0@48r weight:0.000000e+00
   %3 [80r,80d:0) 0@80r weight:0.000000e+00
   RegMasks:
   ********** MACHINEINSTRS **********
   # Machine code for function f: NoPHIs
      0B bb.0:
   16B %0:gr64_with_sub_8bit = COPY $rax
   32B %1:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit
   48B %2:gr32 = COPY %1:gr32
   64B %0.sub_32bit:gr64_with_sub_8bit = COPY %2:gr32
   80B dead %3:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit
   96B dead %1:gr32 = MOV32rr %2:gr32
   112B dead %0.sub_32bit:gr64_with_sub_8bit = COPY %2:gr32
      # End machine code for function f.
      ********** SIMPLE REGISTER COALESCING **********
   ********** Function: f
   ********** JOINING INTERVALS ***********
   :
   16B %0:gr64_with_sub_8bit = COPY $rax
           Considering merging %0 with $rax
           Can only merge into reserved registers.
   48B %2:gr32 = COPY %1:gr32
           Considering merging to GR32 with %2 in %1
                   RHS = %2 [48r,112r:0) 0@48r weight:0.000000e+00
                   LHS = %1 [32r,48r:1)[96r,96d:0) 0@96r 1@32r weight:0.000000e+00
                   merge %2:0@48r into %1:1@32r --> @32r
                   interference at %1:0@96r
           Interference!
   64B %0.sub_32bit:gr64_with_sub_8bit = COPY %2:gr32
           Considering merging to GR64_with_sub_8bit with %2 in %0:sub_32bit
                   RHS = %2 [48r,112r:0) 0@48r weight:0.000000e+00
                   LHS = %0 [16r,64r:2)[64r,112r:1)[112r,112d:0) 0@112r 1@64r 2@16r weight:0.000000e+00
                   merge %0:1@64r into %2:0@48r --> @48r
                   merge %0:0@112r into %2:0@48r --> @48r
                   conflict at %2:0@48r
                   taints local %0:2@16r to 64r
                   pruned %0 at 48r: [16r,48r:2)[64r,112r:1)[112r,112d:0) 0@112r 1@64r 2@16r
                   erased: 112r dead %0.sub_32bit:gr64_with_sub_8bit = COPY %2:gr32
                   erased: 64r %0.sub_32bit:gr64_with_sub_8bit = COPY %2:gr32
                   restoring liveness to 2 points: 64r,48r: %0 [16r,48r:0)[48r,112d:1) 0@16r 1@48r weight:0.000000e+00
   AllocationOrder(GR64) = [ $rax $rcx $rdx $rsi $rdi $r8 $r9 $r10 $r11 $rbx $r14 $r15 $r12 $r13 $rbp ]
   AllocationOrder(GR64_with_sub_8bit) = [ $rax $rcx $rdx $rsi $rdi $r8 $r9 $r10 $r11 $rbx $r14 $r15 $r12 $r13 $rbp ]
                   updated: 48B %0.sub_32bit:gr64_with_sub_8bit = COPY %1:gr32
                   updated: 96B dead %1:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit
           Success: %2:sub_32bit -> %0
           Result = %0 [16r,48r:0)[48r,112d:1) 0@16r 1@48r weight:0.000000e+00
   48B %0.sub_32bit:gr64_with_sub_8bit = COPY %1:gr32
           Considering merging to GR64_with_sub_8bit with %1 in %0:sub_32bit
                   RHS = %1 [32r,48r:1)[96r,96d:0) 0@96r 1@32r weight:0.000000e+00
                   LHS = %0 [16r,48r:0)[48r,112d:1) 0@16r 1@48r weight:0.000000e+00
                   merge %0:1@48r into %1:1@32r --> @32r
                   conflict at %1:0@96r
                   taints local %0:1@48r to 112d

I am trying to understand what this all means, but one thing that
strikes me is that if I manually update the MIR so that the first update
has been performed already:

   name: f
   body: |
     bb.0:
       %0:gr64_with_sub_8bit = COPY $rax
       %1:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit
       %0.sub_32bit:gr64_with_sub_8bit = COPY %1:gr32
       %3:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit
       %1:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit

the pass does run successfully. However, the recalculated intervals are
not identical to what they were thought to be after the first update:

   ********** INTERVALS **********
   %0 [16r,48r:1)[48r,80r:0) 0@48r 1@16r weight:0.000000e+00
   %1 [32r,48r:1)[80r,80d:0) 0@80r 1@32r weight:0.000000e+00
   %2 [64r,64d:0) 0@64r weight:0.000000e+00

Note %0's [48r,80r:0) here, which was [48r,112d) after the initial
update. The instruction at 112 was
%0.sub_32bit:gr64_with_sub_8bit = COPY %2:gr32, which had been deleted.
Could that be the problem, the interval referring to a deleted
instruction?

Cheers,
Harald van Dijk

               restoring liveness to 2 points: 64r,48r:  %0 \[16r,48r:0\)\[48r,112d:1\)  0@16r 1@48r weight:0\.000000e\+00

[...]
I am trying to understand what this all means, but one thing that
strikes me is that if I manually update the MIR so that the first update
has been performed already:

name: f
body: |
bb.0:
%0:gr64_with_sub_8bit = COPY $rax
%1:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit
%0.sub_32bit:gr64_with_sub_8bit = COPY %1:gr32
%3:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit
%1:gr32 = MOV32rr %0.sub_32bit:gr64_with_sub_8bit

the pass does run successfully. However, the recalculated intervals are
not identical to what they were thought to be after the first update:

********** INTERVALS **********
%0 [16r,48r:1)[48r,80r:0) 0@48r 1@16r weight:0.000000e+00
%1 [32r,48r:1)[80r,80d:0) 0@80r 1@32r weight:0.000000e+00
%2 [64r,64d:0) 0@64r weight:0.000000e+00

Note %0's [48r,80r:0) here, which was [48r,112d) after the initial
update. The instruction at 112 was
%0.sub_32bit:gr64_with_sub_8bit = COPY %2:gr32, which had been deleted.
Could that be the problem, the interval referring to a deleted
instruction?

The d in 112d is Slot_Dead, which is documented as:

/// Dead def kill point. Kill slot for a live range that is defined by
/// the same instruction (Slot_Register or Slot_EarlyClobber), but isn't
/// used anywhere.
Slot_Dead,

That seems very wrong: the value defined here is not dead.