Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Incorrect code generated by MIR optimization on nightly #101973

Closed
Amanieu opened this issue Sep 18, 2022 · 14 comments · Fixed by #102045
Closed

Incorrect code generated by MIR optimization on nightly #101973

Amanieu opened this issue Sep 18, 2022 · 14 comments · Fixed by #102045
Labels
A-mir-opt Area: MIR optimizations C-bug Category: This is a bug. I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness P-critical Critical priority regression-from-stable-to-nightly Performance or correctness regression from stable to nightly. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@Amanieu
Copy link
Member

Amanieu commented Sep 18, 2022

#[inline]
pub fn imm8(x: u32) -> u32 {
    let mut out = 0u32;
    out |= (x >> 0) & 0xff;
    out
}

#[inline(never)]
pub fn inner(fields: u32) -> i64 {
    imm8(fields).rotate_right(((fields >> 8) & 0xf) << 1) as i32 as i64
}

fn main() {
    let val = inner(0xe32cf20f);
    println!("{val:#x}");
}

This code normally prints 0xfffffffff0000000 but when compiled with O -C debug-assertions=on -Zmir-opt-level=2 it produces 0x0 instead. This was noticed because MIR optimization is enabled by default on the current nightly.

This is the LLVM IR for the inner function with -C no-prepopulate-passes. Notice how the inputs to llvm.fshr.i32 (used by rotate_right) are 0, which is incorrect.

define i64 @_ZN4test5inner17hd60ec7d5b1d44c39E(i32 %fields) unnamed_addr #0 {
start:
  %0 = alloca i32, align 4
  %_13.0 = lshr i32 %fields, 0
  br label %bb3

bb3:                                              ; preds = %start
  %_10.0 = lshr i32 %fields, 8
  br label %bb1

bb1:                                              ; preds = %bb3
  %_7 = and i32 %_10.0, 15
  %_11.0 = shl i32 %_7, 1
  br label %bb2

bb2:                                              ; preds = %bb1
  call void @llvm.lifetime.start.p0(i64 4, ptr %0)
  %1 = call i32 @llvm.fshr.i32(i32 0, i32 0, i32 %_11.0)
  store i32 %1, ptr %0, align 4
  %_3 = load i32, ptr %0, align 4
  call void @llvm.lifetime.end.p0(i64 4, ptr %0)
  br label %bb4

bb4:                                              ; preds = %bb2
  %2 = sext i32 %_3 to i64
  ret i64 %2
}
@Amanieu Amanieu added the C-bug Category: This is a bug. label Sep 18, 2022
@Amanieu Amanieu changed the title Incorrect code generated with -Z mir-opt-level=2 Incorrect code generated by MIR optimization on nightly Sep 18, 2022
@matthiaskrgr
Copy link
Member

@rustbot prioritize

@rustbot rustbot added the I-prioritize Issue: Indicates that prioritization has been requested for this issue. label Sep 18, 2022
@steffahn
Copy link
Member

@rustbot label regression-from-stable-to-nightly, I-unsound, A-mir-opt, T-compiler

@rustbot rustbot added A-mir-opt Area: MIR optimizations I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness regression-from-stable-to-nightly Performance or correctness regression from stable to nightly. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. labels Sep 18, 2022
@JakobDegen
Copy link
Contributor

Can someone execute the snippet with -Zdump-mir=all and upload the resulting mir-dump directory somewhere? That should allow me to debug from my phone 😆

@Amanieu
Copy link
Member Author

Amanieu commented Sep 19, 2022

@steffahn
Copy link
Member

steffahn commented Sep 19, 2022

I’ve made a gist originally, too, but it looks like you can’t see all the files there. (Afaict only 300 of the 401 files show up.)
Here’s a repo https://github.com/steffahn/rust_issue_101973

Edit: One downside of a repo (compared to a gist) is that I might want to get rid of it eventually; AFAIK, this shouldn’t be needed for too long anyway though.

@tmiasko
Copy link
Contributor

tmiasko commented Sep 19, 2022

With an assertion instead of println:

$ cat a.sh
#!/bin/bash
rustc -O -C debug-assertions=on a.rs && ./a
$ cargo-bisect-rustc --preserve --without-cargo --script ./a.sh
...
********************************************************************************
Regression in bc4b39c271bbd36736cbf1c0a1ac23d5df38d365
********************************************************************************

Individual builds from #101152 (comment), point to #100239 cc @RalfJung

@RalfJung
Copy link
Member

Ouch. That probably means the unsoundness was already possible before my PR (as explained there, the check it removes was ineffective), but is easier to trigger now.

Cc @oli-obk @rust-lang/wg-mir-opt something is wrong in ConstProp handling of shifts and/or casts and/or bit-ops.

Is there a reproducer that does not need shifts and casts and a bitop? That would make the issue easier to track down.

@RalfJung
Copy link
Member

FWIW it prints 0xfffffffff0000000 in Miri so the interpreter is probably fine, and it's probably a problem with the ConstProp pass itself.

@Amanieu
Copy link
Member Author

Amanieu commented Sep 19, 2022

The original code was much more complex. I minimized it as much as I could, but at this point even removing a useless >> 0 will cause the bug to no longer trigger.

@RalfJung
Copy link
Member

Yeah I quite appreciate that it does fit in a few lines now. :)

@RalfJung
Copy link
Member

The -Zmir-opt-level=2 is not needed, but indeed the bug needs -O -C debug-assertions=on to trigger. And inlining. Very strange.

ConstProp code is super hard to read and full of subtle (usually barely documented) invariants, so... this could be an interesting one to track down.

@RalfJung
Copy link
Member

The inlined code looks fine, but it has the basic blocks in a strange order, which might explain why the ConstProp bug only occurs if inlining happens first.

The code just before ConstProp has this


    bb0: {
        StorageLive(_2);                 // scope 0 at ../tmp/constprop.rs:10:5: 10:65
        StorageLive(_3);                 // scope 0 at ../tmp/constprop.rs:10:5: 10:58
        StorageLive(_4);                 // scope 0 at ../tmp/constprop.rs:10:5: 10:17
        StorageLive(_5);                 // scope 0 at ../tmp/constprop.rs:10:10: 10:16
        _5 = _1;                         // scope 0 at ../tmp/constprop.rs:10:10: 10:16
        _4 = const 0_u32;                // scope 1 at ../tmp/constprop.rs:3:19: 3:23
        StorageLive(_12);                // scope 2 at ../tmp/constprop.rs:4:12: 4:27
        StorageLive(_13);                // scope 2 at ../tmp/constprop.rs:4:12: 4:20
        StorageLive(_14);                // scope 2 at ../tmp/constprop.rs:4:13: 4:14
        _14 = _5;                        // scope 2 at ../tmp/constprop.rs:4:13: 4:14
        _15 = CheckedShr(_14, const 0_i32); // scope 2 at ../tmp/constprop.rs:4:12: 4:20
        assert(!move (_15.1: bool), "attempt to shift right by `{}`, which would overflow", const 0_i32) -> bb3; // scope 2 at ../tmp/constprop.rs:4:12: 4:20
    }

    bb1: {
        _8 = move (_10.0: u32);          // scope 0 at ../tmp/constprop.rs:10:32: 10:45
        StorageDead(_9);                 // scope 0 at ../tmp/constprop.rs:10:44: 10:45
        _7 = BitAnd(move _8, const 15_u32); // scope 0 at ../tmp/constprop.rs:10:31: 10:52
        StorageDead(_8);                 // scope 0 at ../tmp/constprop.rs:10:51: 10:52
        _11 = CheckedShl(_7, const 1_i32); // scope 0 at ../tmp/constprop.rs:10:31: 10:57
        assert(!move (_11.1: bool), "attempt to shift left by `{}`, which would overflow", const 1_i32) -> bb2; // scope 0 at ../tmp/constprop.rs:10:31: 10:57
    }

    bb2: {
        _6 = move (_11.0: u32);          // scope 0 at ../tmp/constprop.rs:10:31: 10:57
        StorageDead(_7);                 // scope 0 at ../tmp/constprop.rs:10:56: 10:57
        StorageLive(_16);                // scope 3 at /home/r/src/rust/rustc/library/core/src/num/uint_macros.rs:238:38: 238:42
        _16 = _4;                        // scope 3 at /home/r/src/rust/rustc/library/core/src/num/uint_macros.rs:238:38: 238:42
        StorageLive(_17);                // scope 3 at /home/r/src/rust/rustc/library/core/src/num/uint_macros.rs:238:44: 238:45
        _17 = _6;                        // scope 3 at /home/r/src/rust/rustc/library/core/src/num/uint_macros.rs:238:44: 238:45
        _3 = rotate_right::<u32>(move _16, move _17) -> bb4; // scope 3 at /home/r/src/rust/rustc/library/core/src/num/uint_macros.rs:238:13: 238:56
                                         // mir::Constant
                                         // + span: /home/r/src/rust/rustc/library/core/src/num/uint_macros.rs:238:13: 238:37
                                         // + literal: Const { ty: extern "rust-intrinsic" fn(u32, u32) -> u32 {rotate_right::<u32>}, val: Value(<ZST>) }
    }

One possible explanation would be if ConstProp iterated the basic blocks in order, then by the time it reaches rotate_right, the last assignment to _4 it saw is _4 = const 0_u32 in bb0. There is another assignment to _4 in bb3, which is executed before bb2, but maybe somehow my change made it so that this is not taken into account properly any more.

@RalfJung
Copy link
Member

RalfJung commented Sep 20, 2022

Turns out the actual problem was an early return that I added which skipped more code than it should have -- fixed by #102045.

@apiraino
Copy link
Contributor

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-critical

@rustbot rustbot added P-critical Critical priority and removed I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Sep 20, 2022
Dylan-DPC added a commit to Dylan-DPC/rust that referenced this issue Sep 21, 2022
…, r=oli-obk

fix ConstProp handling of written_only_inside_own_block_locals

Fixes a regression introduced by rust-lang#100239, which adds an early return and thus skips some code in `visit_terminator` that must be run for soundness.

Fixes rust-lang#101973
@bors bors closed this as completed in 7d7f555 Sep 21, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-mir-opt Area: MIR optimizations C-bug Category: This is a bug. I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness P-critical Critical priority regression-from-stable-to-nightly Performance or correctness regression from stable to nightly. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

8 participants