Broken match statement when compiling for thumbv6-none-eabi (ARM cortex-m0)

[alevy]

After upgrading Tock to use a recent nightly, compilation for the NRF51-DK (a Cortex-M0 based board) results in unexpected assembly for a particular match statement.

The match statement looks like this:

impl kernel::Platform for Platform {
    fn with_driver<F, R>(&self, driver_num: usize, f: F) -> R
        where F: FnOnce(Option<&kernel::Driver>) -> R
    {
        match driver_num {
            0 => f(Some(self.console)),
            1 => f(Some(self.gpio)),
            3 => f(Some(self.timer)),
            8 => f(Some(self.led)),
            9 => f(Some(self.button)),
            14 => f(Some(self.rng)),
            17 => f(Some(self.aes)),
            36 => f(Some(self.temp)),
            _ => f(None),
        }
    }
}

The LLVM IR that (seems to) corresponds is:

bb49.i.i.i.i:                                     ; preds = %_ZN6kernel7process7Process18incr_syscall_count17h073864aec83cd68fE.exit
  %1192 = load volatile i32, i32* %1028, align 4
  switch i32 %1192, label %bb12.i.i.i1127 [
    i32 0, label %bb1.i.i.i.i.i
    i32 1, label %bb2.i.i.i.i.i
    i32 3, label %bb3.i.i.i.i.i
    i32 8, label %bb4.i57.i.i.i.i
    i32 9, label %bb5.i58.i.i.i.i
    i32 14, label %bb6.i.i.i.i.i
    i32 17, label %bb7.i.i.i.i.i
    i32 36, label %bb8.i.i.i.i.i
  ]

which is a fairly straight forward translation.

In general, the template for the expected output in assembly is something like:

;given r1 is `driver_num`, the variable we're matching against
lsls    r1, r1, #1
add     r1, pc
ldrh    r1, [r1, #4] ; load a half-word from the switch's offset table
lsls    r1, r1, #1 ; this half-word is actually 2x what it should be (idk why, just cause)
add     pc, r1 ; use the result as an offset from the current PC and jump there
                     ; (because we're executing a closure

The match statement seems to end up being broken up (makes sense since the matched values are sparse), with one of the cases (which is called at least when driver_num is 3) looking like this:

add     r1, pc, #16
lsls    r1, r1, #1
ldrh    r1, [r1, r1]
lsls    r1, r1, #1
add     pc, r1

This basically doesn't make any sense... it's grabbing a text segment address, multiplying it by two then loading a half-word from an address that's again multiplied by two (and at this point, completely outside the text segment so it could be anything really). In practice, that returns 0xffff, which after shifting left by one results in 0x1fffe. Finally, adding that to the current PC is way way way outside of the text segment and results in a hardware fault.

Notes

We can "fix" this in a variety of ways:

• Commenting out the 17 valued branch (commenting out no other branch seems to do the trick)

• Making the function inline(never)

• Using opt-level 0 or 1

• Compiling for better supported architectures by LLVM (e.g. thumbv7m-none-eabi) although those don't run on the same hardware so I can only confirm

Meta

This is using rustc 1.19.0-nightly (5b13bff52 2017-05-23)

Reproducing

Checkout commit d5565a227f8aa40e8c94efa9877a425003d02752 from helena-project/tock and:

$ make TOCK_BOARD=nrf51dk

the resulting binary will be boards/nrf51dk/target/thumbv6-none-eabi/release/nrf51dk, which you can read with objdump:

$ arm-none-eabi-objdump -d boards/nrf51dk/target/thumbv7-none-eabi/release/nrf51dk

[alevy]

/cc @rkruppe and @nagisa who helped debug this a bit on #rust-internals

[alevy]

The last nightly where this works as expected is rustc 1.17.0 (56124baa9 2017-04-24), which I believe is the last one before the upgrade to LLVM 4.0, which is at least some evidence that this is an LLVM bug.

[alevy]

I also compiled to thumb assembly the same LLVM-IR with llc from

1. an older version of LLVM 3.9 and
2. a newer version of LLVM from git.

LLVM 3.9 seems to use an entirely different mechanism for compiling switch statements to thumb assembly and recent git-LLVM seems to use the same strategy but doesn't result in the same strange compilation bug as described above.

I'm still figuring out if it's possible to link the result and run it on my hardware, but if I can confirm that (2) works as expected, it seems there may be an existing fix somewhere in the LLVM source tree between the 4.0 that Rust uses and bleeding edge.

[ppannuto]

As Tock is moving around this problem with the inline(never) fix, could you add a link to a commit hash that exhibits this issue?

[arielb1]

@ppannuto

LLVM bugs that cause scary miscompilations are not that rare, especially on non-x86 architectures. Normally, we work with the LLVM devs to get them fixed and backport the fixes to our LLVM version.

Can you upload LLVM IR that exhibits the problem?

[arielb1]

This change looks relevant:
llvm-mirror/llvm@a90b36e

It's not on our LLVM. If I had LLVM IR exhibiting the bug I could check whether it fixes the problem.

[arielb1]

Can confirm issue. Let me see whether the LLVM changes fix it.

[alevy]

@arielb1 you are my hero and savior!

[arielb1]

The bug is actually fixed by llvm-mirror/llvm@f4523b0 rather than the other commit. Now we only have to see what scary codegen bugs the other commits to that file fix.

[nikomatsakis]

triage: P-high

[brson]

Will this be fixed by the llvm upgrade #42410?

[brson]

@arielb1 says the upgrade does not include the fix.

[arielb1]

Can you confirm the generated code works @alevy ? I can't read ARM that well.

[alevy]

Appears to as far as I can test. I've not been able to reliably get a minimal, repeatable example of the bug, but on code that breaks with previous nightly doesn't break with this one, so seems fixed to me!

[arielb1]

Yay!

[alevy]

@arielb1 I take it back, I didn't test properly. It looks like the generated code is still incorrect. FWIW, this seems like a difficult thing to fix on the Rust side other than just regularly upgrading LLVM versions, unless we (I?) can identify more clearly why this is happening in the LLVM codegen and where it's been fixed. Sorry @arielb1, I misled you... :/

No no no! False alarm! I hadn't upgraded to the right Rust version when I pushed my changes to Tock upstream! It works! Sorry again!