Miscompilation under target-cpu >= haswell

[alecmocatta]

This example fails when compiled with target-cpu "haswell" or more recent:

[dependencies]
aes-soft = "=0.3.3"

use aes_soft::{block_cipher_trait::BlockCipher, Aes128};

fn main() {
    let plain = [127, 0, 0, 1, 174, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    let key = [0; 16];
    let encrypted = [222, 157, 168, 71, 195, 237, 77, 237, 182, 194, 17, 235, 182, 214, 204, 80];

    let output = encrypt(plain, key);
    assert_eq!(output, encrypted);

    println!("success");
}

fn encrypt(input: [u8; 16], key: [u8; 16]) -> [u8; 16] {
    let key = key.into();
    let mut block = input.into();
    let cipher = Aes128::new(&key);
    cipher.encrypt_block(&mut block);
    block.into()
}

> RUSTFLAGS='-C target-cpu=ivybridge' cargo run --release
success
> RUSTFLAGS='-C target-cpu=haswell' cargo run --release
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `[103, 175, 2, 16, 66, 180, 192, 20, 55, 121, 111, 21, 82, 184, 106, 59]`,
 right: `[222, 157, 168, 71, 195, 237, 77, 237, 182, 194, 17, 235, 182, 214, 204, 80]`', src/main.rs:9:5
> RUSTFLAGS='-C target-cpu=broadwell' cargo run --release
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `[103, 175, 2, 16, 66, 180, 192, 20, 55, 121, 111, 21, 82, 184, 106, 59]`,
 right: `[222, 157, 168, 71, 195, 237, 77, 237, 182, 194, 17, 235, 182, 214, 204, 80]`', src/main.rs:9:5
> RUSTFLAGS='-C target-cpu=skylake' cargo run --release
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `[103, 175, 2, 16, 66, 180, 192, 20, 55, 121, 111, 21, 82, 184, 106, 59]`,
 right: `[222, 157, 168, 71, 195, 237, 77, 237, 182, 194, 17, 235, 182, 214, 204, 80]`', src/main.rs:9:5

I bumped into this when compiling with target-cpu=native and assumed it was related to #54688, but after minimising the testcase I don't think it is. My next guess is an llvm bug but I thought I'd make an issue here in case anyone else bumps into it or wants to help investigate.

I've created a self-contained godbolt: https://rust.godbolt.org/z/ChdU6w

The two uses of unsafe I believe are sound. I think I've ruled out target-features being the cause, because this succeeds:

RUSTFLAGS='-C target-cpu=ivybridge -C target-feature=-slow-unaligned-mem-32,+avx2,+bmi,+bmi2,+ermsb,+fma,+invpcid,+lzcnt,+movbe,+false-deps-lzcnt-tzcnt' cargo run --release

Which should enable identical features to haswell given https://github.com/llvm-mirror/llvm/blob/release_90/lib/Target/X86/X86.td#L542-L568.

This occurs on nightly and stables back to 1.34.0, though 1.33.0 and prior seem to work correctly.

Tested on Broadwell (Intel(R) Xeon(R) CPU E5-2673 v3 @ 2.40GHz) and Skylake (Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz).

Same issue filed against aes_soft crate: RustCrypto/block-ciphers#51

[gnzlbg]

It would help tremendously if you could reduce that example further.

[mati865]

You can use C-Reduce to achieve that.

[alecmocatta]

I'll look into using bugpoint and -opt-bisect-limit to narrow this down. Any other suggestions welcome.

@mati865 Thanks for the suggestion, I didn't know C-Reduce worked for Rust! My suspicion is in llvm's optimization passes, i.e. LLVM IR -> assembly, so I'll give llvm's bugpoint a go first.

[bjorn3]

I didn't know C-Reduce worked for Rust!

It works for pretty much any language. It just does changes like removing a line or changing it a bit, so it often generates invalid C as well. Only a few passes assume C, but those will just not reduce the test case for Rust. See https://embed.cs.utah.edu/creduce/pldi12_talk.pdf

[Aaron1011]

Unforunately, C-Reduce proved to be too clever when I ran it: it replaced:

if output != encrypted {
    std::process::abort();
}

with

std::process::abort();

While this is technically a 'minimization', it's not a very useful one.

[JakubValtar]

Not sure if it helps, but git bisect revealed df0466d to be the first bad commit.

[Aaron1011]

THe problem appears to be related to the deconstruct function inside un_bit_slice_4x4_with_u16. For some reason, the high-order bit in a (computed as pb(x7, bit + 12, 31)) seems to be getting left off.

The earliest point at which this occurs appears to be the call un_bit_slice_4x4_with_u16(Bs8State(61439, 65535, 0, 4369, 273, 65535, 61439, 4369)). The correct result is (2868640763, 1667457891, 1667457891, 1667457891), but with -C target-cpu=haswell, it gets miscompiled somehow to return (721157115, 1667457891, 1667457891, 1667457891). Note that 2868640763 = 721157115 | (1 << 31).

Unfortunately, the problem disappeared when I made a standalone project with un_bit_slice_4x4_with_u16 and Bs8State.

[JakubValtar]

I decided to give it a try and managed to simplify the code:

fn main() {
    let x = [0, 0, 0, 0, 0, 0, 0, 1];
    let x = unslice(x).0;
    assert_eq!(x, 1 << 31);
}

#[inline(never)] // can't reproduce without inline(never)
fn unslice(x: [u16; 8]) -> (u32, u32, u32) {
    let a = deconstruct(x, 0);
    let b = deconstruct(x, 1); // needs two calls with different parameter
    (a, b, 0) // can't reproduce without the third value in the tuple
}

#[inline(never)] // can't reproduce without inline(never)
fn deconstruct(x: [u16; 8], bit: u32) -> u32 {
    // this part needs to get vectorized
    pb(x[0], bit + 1, 16) | pb(x[1], bit + 1, 17)
        | pb(x[2], bit + 1, 18) | pb(x[3], bit + 1, 19)
        | pb(x[4], bit + 1, 20) | pb(x[5], bit + 1, 21)
        | pb(x[6], bit + 1, 22) | pb(x[7], bit + 1, 23)
        | pb(x[0], bit, 24) | pb(x[1], bit, 25)
        | pb(x[2], bit, 26) | pb(x[3], bit, 27)
        | pb(x[4], bit, 28) | pb(x[5], bit, 29)
        | pb(x[6], bit, 30) | pb(x[7], bit, 31)
}

fn pb(x: u16, bit: u32, shift: u32) -> u32 {
    u32::from((x >> bit) & 1) << shift // can't reproduce with different order (e.g. mask then shift)
}

Assembly output from 1.33.0 and 1.34.0 is identical, except for this block of AVX instructions:

1.33.0
vpunpckhwd ymm4, ymm3, ymm1
vpunpckhwd ymm0, ymm0, ymm3
vpsrlvd ymm0, ymm4, ymm0
vpsrld ymm0, ymm0, 16
vpunpcklwd ymm1, ymm3, ymm1
vpsrld ymm1, ymm1, 1
vpsrld ymm1, ymm1, 16
vpackusdw ymm0, ymm1, ymm0

1.34.0
vpunpckhwd ymm1, ymm3, ymm1
vpunpckhwd ymm0, ymm0, ymm3
vpsrlvd ymm0, ymm1, ymm0

Looks like some of them got incorrectly optimized away. I'm not familiar with how LLVM vectorizes and optimizes things, so sadly this is as far as I can get on my own.

Edit: Just to confirm, running with -opt-bisect-limit points to SLP Vectorizer on function (deconstruct).