Miscompilation of AVX2 code under --release

[tarcieri]

Apologies for not having a minimal reproduction, but this was an extremely difficult bug to even isolate occurring inside some complicated AVX2 code.

The bug is causing the wrong values to be computed. Whether or not it occurs depends on the following conditions:

• With target-cpu unset, the bug does NOT occur in debug builds, but DOES occur with --release
• With target-cpu=haswell, the bug does NOT occur in --release builds and both debug and release builds are OK

I can attempt to further isolate and reduce the problem, but there's a lot of spooky-action-at-a-distance happening making that rather difficult.

For now, here is the best reproduction I can provide:

EDIT: I've deleted the poly1305/avx2-bug branch as there is now a much smaller repro, but so long as GitHub hasn't GC'd it here's the original commit:

RustCrypto/universal-hashes@7485010

git clone https://github.com/RustCrypto/universal-hashes
cd universal-hashes/poly1305
git checkout poly1305/avx2-bug

NOTE: if you git show from here, I've included lots of notes in the latest commit about the bug in the commit message. The commit also contains comments indicating lines you can comment or uncomment to make the tests succeed or fail.

Commands to run which DON'T trigger the bug

• cargo test donna_self_test1 -- --nocapture
• RUSTFLAGS="-Ctarget-cpu=haswell" cargo test donna_self_test1 --release -- --nocapture

Commands to run which DO trigger the bug

NOTE: as this is a bug in the AVX2 backend, you'll need to run it on an AVX2-capable host to trigger the bug.

• cargo test donna_self_test1 --release -- --nocapture

This test fails with a miscomputed result (as do all of the tests across the board if you run the whole suite):

thread 'donna_self_test1' panicked at 'assertion failed: `(left == right)`
  left: `[3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]`,
 right: `[254, 255, 255, 255, 255, 255, 239, 255, 255, 63, 0, 0, 0, 254, 255, 255]`', poly1305/tests/lib.rs:47:5

Things which mysteriously make the tests pass

The aforementioned cargo test ... --release ... will pass if any of the following things which are documented in the 74850109 commit (git show) message and comments introduced in that commit are changed:

• A commented out dbg! statement near the first observation of the miscompilation is uncommented (heisenbug!)
• The #[target_feature(enable = "avx2")] attribute on the finalize function is commented out. This function is in a completely different module, hence my descriptions of "spooky action at a distance" (the function in which the bug is occurring is annotated #[inline(always)], but the bug still occurs if that attribute is commented out)

Meta

This bug is easily reproducible and occurs on all versions of the Rust compiler and all operating systems I've tried. I've reproduced it locally on macOS and it also occurred on Linux/Ubuntu via GitHub Actions.

Here are some compiler versions I've tried:

rustc 1.48.0 (7eac88abb 2020-11-16)

Latest nightly as of opening this ticket:

rustc 1.50.0-nightly (1700ca07c 2020-12-08)

It also broke in CI which tests it under the MSRV of 1.41.0.

[tarcieri]

If this is helpful, this is the code closest to where the problem is occurring:

                let v0 = _mm256_add_epi64(
                    _mm256_and_si256(v0, _mm256_set_epi64x(-1, 0x3ffffff, 0x3ffffff, 0x3ffffff)),
                    _mm256_permute4x64_epi64(
                        _mm256_srlv_epi64(v0, _mm256_set_epi64x(64, 26, 26, 26)),
                        set02(2, 1, 0, 3),
                    ),
                );

[jyn514]

@rustbot ping llvm

[rustbot]

Hey LLVM ICE-breakers! This bug has been identified as a good
"LLVM ICE-breaking candidate". In case it's useful, here are some
instructions for tackling these sorts of bugs. Maybe take a look?
Thanks! <3

cc @camelid @comex @cuviper @DutchGhost @hdhoang @heyrutvik @higuoxing @JOE1994 @jryans @mmilenko @nagisa @nikic @Noah-Kennedy @SiavoshZarrasvand @spastorino @vertexclique

[tarcieri]

I found a workaround for this issue which suffices for my purposes, but also hopefully helps track down the bug.

The miscompilation was occurring inside of a lambda.

I extracted the lambda(s) into named functions and that worked around the problem successfully:

RustCrypto/universal-hashes@b5abdc1

[camelid]

This is unsound and it impacts cryptographic code, so we decided on P-critical.

Assigning P-critical and removing I-prioritize as discussed in the prioritization working group.

[cuviper]

meta: I thought I-unsound was more about language issues -- are all LLVM codegen bugs going to be flagged this way?

[camelid]

@cuviper I think I-unsound is generally used for miscompilations as well.

[lqd]

I've removed cpuid, universal-hash, generic_array, typenum, subtle, and hex-literal, it's not exactly minimal (900 lines) but here you go https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=9235420e8d6a2f066d3636f0ecf9f9b3

I may have inadvertently removed a couple target features specific-code or attributes, or too much of the cpu autodetection, as it now doesn't build with RUSTFLAGS="-C target-feature=+avx2" ? The error is still the same as the OP (and reproduces on the playground) so maybe it is useful to @tarcieri.

I haven't looked at the issue much though, and am not sure what to expect here (especially if code using target features is built without them enabled).

[spastorino]

@rustbot ping cleanup

Would be nice to get an MCVE for this one.

[rustbot]

Hey Cleanup Crew ICE-breakers! This bug has been identified as a good
"Cleanup ICE-breaking candidate". In case it's useful, here are some
instructions for tackling these sorts of bugs. Maybe take a look?
Thanks! <3

cc @AminArria @camelid @chrissimpkins @contrun @DutchGhost @elshize @ethanboxx @h-michael @HallerPatrick @hdhoang @hellow554 @imtsuki @JamesPatrickGill @kanru @KarlK90 @LeSeulArtichaut @MAdrianMattocks @matheus-consoli @mental32 @nmccarty @Noah-Kennedy @pard68 @PeytonT @pierreN @Redblueflame @RobbieClarken @RobertoSnap @robjtede @SarthakSingh31 @shekohex @sinato @smmalis37 @steffahn @Stupremee @tamuhey @turboladen @woshilapin @yerke

[Stupremee]

I've got it down to 280 lines with just some abstractions and the raw SIMD code left

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=84a7bdf70b575fd022a352dcc6f5ac06

Edit: down to 55 lines
https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=8c70293c639d84fb32dacf728f815d06

[Stupremee]

This is the smallest version I can get
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=39e13cba6015a856b6f88526024efd61

[nikic]

Looks like this still reproduces on nightly, so not fixed by LLVM 12.

[nikic]

I believe this is an ABI mismatch problem. Argument promotion converts the by-pointer arguments into by-value arguments, so we pass <4 x i64> by value across and avx2 ABI boundary. The caller passes two yym registers, the callee expects four xmm registers. cc @nagisa

[nagisa]

This sounds very similar to why we are passing the SIMD arguments by-pointer in the first place – in attempt to avoid this exact kind of ABI mismatch.

[nikic]

It looks like ArgPromotion does check for ABI compatibility: https://github.com/llvm/llvm-project/blob/237526319cb3a17852a0e732f85f1562e42d73cc/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp#L843 Either it's not doing that right, or there's some more complex interaction here.

[nikic]

This is fixed upstream (cf llvm/llvm-project#52660) and will be pulled in with the LLVM 14 update.

[tarcieri]

Fantastic! Thank you!

[nikic]

This is fixed by the LLVM 14 upgrade on beta/nightly.

[nagisa]

I think we still want a regression test for this issue, right?