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

Early otherwise branch MIR opt is unsound #95162

Closed
JakobDegen opened this issue Mar 21, 2022 · 2 comments · Fixed by #122387
Closed

Early otherwise branch MIR opt is unsound #95162

JakobDegen opened this issue Mar 21, 2022 · 2 comments · Fixed by #122387
Labels
A-MIR Area: Mid-level IR (MIR) - https://blog.rust-lang.org/2016/04/19/MIR.html A-mir-opt Area: MIR optimizations C-bug Category: This is a bug. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@JakobDegen
Copy link
Contributor

I re-wrote this pass in #91840 ; however, I don't think the new version is sound either (#95161). I'm currently working on a MCVE miscompilation, but quoting from the PR:

This is unsound. Someone could write code like this:

let Q = val;
if discriminant(P) == otherwise {
    let ptr = &mut Q as *mut _ as *mut u8;
    unsafe { *ptr = 10; } // Any invalid value for the type
}

match P {
    A => match Q {
        A => {
            // code
        }
        _ => {
            // don't use Q
        }
    }
    _ => {
        // don't use Q
    }
};

Hoisting the discriminant(Q) out of the A arm causes us to compute the discriminant of an
invalid value, which is UB.

In order to fix this, we would either need to show that the discriminant computation of
place is computed in all branches, including the otherwise branch, or we would need
another analysis pass to determine that the place is fully initialized. It might even be best
to have the hoisting be performed in a different pass and just do the CFG changing in this
pass.

For an example of a test that almost miscompiles, see here. The opt doesn't fire on that particular version, but it would if there was a SimplifyCFG immediately before.

@rustbot label +A-mir +A-mir-opt +T-compiler

@JakobDegen JakobDegen added the C-bug Category: This is a bug. label Mar 21, 2022
@rustbot rustbot added A-MIR Area: Mid-level IR (MIR) - https://blog.rust-lang.org/2016/04/19/MIR.html A-mir-opt Area: MIR optimizations T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. labels Mar 21, 2022
@SparrowLii
Copy link
Member

SparrowLii commented Mar 23, 2022

Regardless of this mir-opt pass, if we write the code like this:

    let Q = val;
    if discriminant(P) == otherwise {
        let ptr = &mut Q as *mut _ as *mut u8;
        unsafe { *ptr = 10; } // Any invalid value for the type
    }

    match (P, Q) {
        (A, A) => {
            // branch1
        }
        _ => {
            // branch2
        }
    }

No problem can arise because in branch2 only discriminant(P) is executed and not discriminant(Q). This is somewhat unreasonable, since it hides potential UB risks. Perhaps match(P, Q) should be treated differently, like executing discriminant(P) and discriminant(Q) at once. In that case, the issue of this mir-opt pass can also be solved.

@JakobDegen
Copy link
Contributor Author

@SparrowLii so, this turns out to not be true right now, see this example. That being said, I do think you make a good point here in general, we could probably make this opt easier to execute (and be sound) by adjusting MIR building

bors added a commit to rust-lang-ci/rust that referenced this issue Feb 29, 2024
… r=<try>

 Re-enable the early otherwise branch optimization

Fixes rust-lang#95162. Fixes rust-lang#119014. Fixes rust-lang#117970.

An invalid enum discriminant can come from anywhere. We have to check to see if all successors contain the discriminant statement.

It should not be UB that we pass in an invalid enum discriminant when calling a function, this is more like LLVM's poison value. UB only when used. Although miri would consider the following code to be UB. (It's fine for miri.)

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=18602870aaeb07cbdf7dfcd2c28961a2

I extended the scenario with scalars and the same target values.

r? compiler
bors added a commit to rust-lang-ci/rust that referenced this issue Mar 3, 2024
… r=<try>

 Re-enable the early otherwise branch optimization

Fixes rust-lang#95162. Fixes rust-lang#119014. Fixes rust-lang#117970.

An invalid enum discriminant can come from anywhere. We have to check to see if all successors contain the discriminant statement.

It should not be UB that we pass in an invalid enum discriminant when calling a function, this is more like LLVM's poison value. UB only when used. Although miri would consider the following code to be UB. (It's fine for miri.)

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=18602870aaeb07cbdf7dfcd2c28961a2

I extended the scenario with scalars and the same target values.

r? compiler
bors added a commit to rust-lang-ci/rust that referenced this issue Mar 27, 2024
…nch, r=<try>

Re-enable the early otherwise branch optimization

Closes rust-lang#95162. Fixes rust-lang#119014.

This is the first part of rust-lang#121397.

An invalid enum discriminant can come from anywhere. We have to check to see if all successors contain the discriminant statement. This should have a pass to hoist instructions.

r? cjgillot
bors added a commit to rust-lang-ci/rust that referenced this issue Apr 7, 2024
…nch, r=cjgillot

Re-enable the early otherwise branch optimization

Closes rust-lang#95162. Fixes rust-lang#119014.

This is the first part of rust-lang#121397.

An invalid enum discriminant can come from anywhere. We have to check to see if all successors contain the discriminant statement. This should have a pass to hoist instructions.

r? cjgillot
@bors bors closed this as completed in 59c808f Apr 9, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-MIR Area: Mid-level IR (MIR) - https://blog.rust-lang.org/2016/04/19/MIR.html A-mir-opt Area: MIR optimizations C-bug Category: This is a bug. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
3 participants