UNREACHABLE Impossible reg-to-reg copy

[dylanmckay]

This bug occurs in my LLVM 6.0 branch at #91 when I compile stock libcore.

Impossible reg-to-reg copy
UNREACHABLE executed at /home/dylan/projects/llvm-project/llvm/lib/Target/AVR/AVRInstrInfo.cpp:75!
#0 0x00007fd02d6f8cc6 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/dylan/projects/llvm-project/llvm/lib/Support/Unix/Signals.inc:398:11
#1 0x00007fd02d6f8ec9 PrintStackTraceSignalHandler(void*) /home/dylan/projects/llvm-project/llvm/lib/Support/Unix/Signals.inc:462:1
#2 0x00007fd02d6f7260 llvm::sys::RunSignalHandlers() /home/dylan/projects/llvm-project/llvm/lib/Support/Signals.cpp:0:5
#3 0x00007fd02d6f92ba SignalHandler(int) /home/dylan/projects/llvm-project/llvm/lib/Support/Unix/Signals.inc:0:3
#4 0x00007fd02c5d6dd0 __restore_rt (/usr/lib/libpthread.so.0+0x11dd0)
#5 0x00007fd02b958860 __GI_raise (/usr/lib/libc.so.6+0x34860)
#6 0x00007fd02b959ec9 __GI_abort (/usr/lib/libc.so.6+0x35ec9)
#7 0x00007fd02d5f71f0 llvm::install_out_of_memory_new_handler() /home/dylan/projects/llvm-project/llvm/lib/Support/ErrorHandling.cpp:193:0
#8 0x00007fd032637599 llvm::AVRInstrInfo::copyPhysReg(llvm::MachineBasicBlock&, llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>, llvm::DebugLoc const&, unsigned int, unsigned int, bool) const /home/dylan/projects/llvm-project/llvm/lib/Target/AVR/AVRInstrInfo.cpp:0:7
#9 0x00007fd03004dd3b (anonymous namespace)::ExpandPostRA::LowerCopy(llvm::MachineInstr*) /home/dylan/projects/llvm-project/llvm/lib/CodeGen/ExpandPostRAPseudos.cpp:166:7
#10 0x00007fd03004d189 (anonymous namespace)::ExpandPostRA::runOnMachineFunction(llvm::MachineFunction&) /home/dylan/projects/llvm-project/llvm/lib/CodeGen/ExpandPostRAPseudos.cpp:212:23
#11 0x00007fd030230e61 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /home/dylan/projects/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:62:8
#12 0x00007fd02f76fdff llvm::FPPassManager::runOnFunction(llvm::Function&) /home/dylan/projects/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1520:27
#13 0x00007fd02f770152 llvm::FPPassManager::runOnModule(llvm::Module&) /home/dylan/projects/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1541:16
#14 0x00007fd02f7709b0 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/dylan/projects/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1597:27
#15 0x00007fd02f770436 llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/dylan/projects/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1700:16
#16 0x00007fd02f770f21 llvm::legacy::PassManager::run(llvm::Module&) /home/dylan/projects/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1731:3
#17 0x00005579e90cf34a compileModule(char**, llvm::LLVMContext&) /home/dylan/projects/llvm-project/llvm/tools/llc/llc.cpp:577:41
#18 0x00005579e90cd800 main /home/dylan/projects/llvm-project/llvm/tools/llc/llc.cpp:347:13
#19 0x00007fd02b944f4a __libc_start_main (/usr/lib/libc.so.6+0x20f4a)
#20 0x00005579e90cceea _start (./bin/llc+0x22eea)
Stack dump:
0.	Program arguments: ./bin/llc -march=avr -mcpu=atmega328p bugpoint-reduced-simplified.ll -o /dev/null 
1.	Running pass 'Function Pass Manager' on module 'bugpoint-reduced-simplified.ll'.
2. Running pass 'Post-RA pseudo instruction expansion pass' on function '@_ZN3lib3num7flt2dec8strategy5grisu22max_pow10_no_more_than17h83b3c65a945b5158E'

Note that this is coming from @_ZN3lib3num7flt2dec8strategy5grisu22max_pow10_no_more_than17h83b3c65a945b5158E - the Grisu float-string algorithm.

I have minimised down to a testcase, and also collected llc debug outputs

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

define { i8, i32 } @chapstick() {
start:
  ret { i8, i32 } zeroinitializer
}

You can see the build artifacts here.

[shepmaster]

lib::num::flt2dec::strategy

In our own libcore, we've disabled a lot of this code because it's simply too big. This may not be an extra blocker from moving to LLVM 6.

[brainlag]

Do I understand this code correct. It tries to return a struct with the fields initialized to zero?

And if this is the machine code:

bb.0.start:
  %2:ld8 = LDIRdK 0
  %3:dldregs = LDIWRdK 0
  $r21r20 = COPY %2
  $r23r22 = COPY %3
  $r24 = COPY %3
  RET implicit $r21r20, implicit $r23r22, implicit $r24

Then the for some reason the copy instructions for 16bit registers and 8bit registers get mixed up.
This doesn't sound to hard to fix.

[shepmaster]

It tries to return a struct with the fields initialized to zero?

That seems like it to me!

This doesn't sound to hard to fix.

Awesome!

[brainlag]

~~~The patch is pretty messy because my C++ is in a really rusty state and I'm unable to reverse the const vector of the source registers.~~~

~~~But here we go [gist](https://gist.github.com/brainlag/309d47cd78aedc081773d7e14a65468d):~~~


```diff
diff --git a/lib/Target/AVR/AVRISelLowering.cpp b/lib/Target/AVR/AVRISelLowering.cpp
index 7ac8a136e6b..4f7d3d6a815 100644
--- a/lib/Target/AVR/AVRISelLowering.cpp
+++ b/lib/Target/AVR/AVRISelLowering.cpp
@@ -1371,16 +1371,12 @@ AVRTargetLowering::LowerReturn(SDValue Chain, CallingConv::ID CallConv,
   MachineFunction &MF = DAG.getMachineFunction();
   unsigned e = RVLocs.size();
 
-  // Reverse splitted return values to get the "big endian" format required
-  // to agree with the calling convention ABI.
-  if (e > 1) {
-    std::reverse(RVLocs.begin(), RVLocs.end());
-  }
-
   SDValue Flag;
   SmallVector<SDValue, 4> RetOps(1, Chain);
   // Copy the result values into the output registers.
-  for (unsigned i = 0; i != e; ++i) {
+  // Reverse loop to get the "big endian" format required
+  // to agree with the calling convention ABI.
+  for (int i = (e - 1); i < 0; --i) {
     CCValAssign &VA = RVLocs[i];
     assert(VA.isRegLoc() && "Can only return in registers!");
 
diff --git a/test/CodeGen/AVR/rust-avr-bug-92.ll b/test/CodeGen/AVR/rust-avr-bug-92.ll
new file mode 100644
index 00000000000..f93bf7a152d
--- /dev/null
+++ b/test/CodeGen/AVR/rust-avr-bug-92.ll
@@ -0,0 +1,6 @@
+; RUN: llc < %s -march=avr | FileCheck %s
+
+define { i8, i32 } @chapstick() {
+start:
+  ret { i8, i32 } zeroinitializer
+}
\ No newline at end of file
```

[shepmaster]

Can you narrow down what exactly the problem is? Is it just that the condition (if (e > 1)) has been removed? Is it that the call to std::reverse is "broken"?

I wonder if it would still work if the only change was removing if (e > 1) {.

[brainlag]

Damn, I should have run the tests before. It breaks a lot of stuff. It made so much sense.

[brainlag]

I think I know whats going on. The AVR couldn't handle returning structs like this at all (see #57).
It only expects to ever return an iXX and only when XX is >=32 it needs to reverse the registers because of the calling convention. Now for this bug where we have { i8, i32 } and registers {[0] = i8, [1] = i16, [2] = i16} it only should reverse registers 1 and 2 but not 0.

[brainlag]

I don't know if this produces correct output but it prevents the crash. This patch just avoids to return a struct through registers. Which only works for a few/small structs anyway.

https://gist.github.com/brainlag/4d9217eefcac1f06df682415975d97c3

diff --git a/lib/Target/AVR/AVRISelLowering.cpp b/lib/Target/AVR/AVRISelLowering.cpp
index 7ac8a136e6b..e0bb2f317d1 100644
--- a/lib/Target/AVR/AVRISelLowering.cpp
+++ b/lib/Target/AVR/AVRISelLowering.cpp
@@ -1346,7 +1346,7 @@ AVRTargetLowering::CanLowerReturn(CallingConv::ID CallConv,
   CCState CCInfo(CallConv, isVarArg, MF, RVLocs, Context);
 
   auto CCFunction = CCAssignFnForReturn(CallConv);
-  return CCInfo.CheckReturn(Outs, CCFunction);
+  return !MF.getFunction().getReturnType()->isStructTy() && CCInfo.CheckReturn(Outs, CCFunction);
 }
 
 SDValue
diff --git a/test/CodeGen/AVR/rust-avr-bug-92.ll b/test/CodeGen/AVR/rust-avr-bug-92.ll
new file mode 100644
index 00000000000..e76ce630c67
--- /dev/null
+++ b/test/CodeGen/AVR/rust-avr-bug-92.ll
@@ -0,0 +1,7 @@
+; RUN: llc < %s -march=avr | FileCheck %s
+
+; CHECK-LABEL: main
+define { i8, i32 } @main() {
+start:
+  ret { i8, i32 } zeroinitializer
+}
\ No newline at end of file

[dylanmckay]

I think I know whats going on. The AVR couldn't handle returning structs like this at all (see #57).
It only expects to ever return an iXX and only when XX is >=32 it needs to reverse the registers because of the calling convention. Now for this bug where we have { i8, i32 } and registers {[0] = i8, [1] = i16, [2] = i16} it only should reverse registers 1 and 2 but not 0.

This makes a lot of sense. Sounds like we need to adjust this logic and write some more calling convention tests.

I don't know if this produces correct output but it prevents the crash.
This patch just avoids to return a struct through registers. Which only works for
a few/small structs anyway.

I suspect that this patch will break the calling convention for all functions which return structs, as they will now always be passed on the stack. FWIW, code compiled with this patch will work with code compiled under the same patch, but it would not work when compiling against objects from an older version of LLVM or AVR-GCC generated objects.

I am fairly busy the next handful of days, but after that this bug is at the top of my priority list. If anybody wants to look at this in the interim (please do!), feel free to ask questions on this issue, or ping me on Gitter.