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

MIR-opt not const-folding #81605

Closed
simonvandel opened this issue Jan 31, 2021 · 3 comments · Fixed by #101168
Closed

MIR-opt not const-folding #81605

simonvandel opened this issue Jan 31, 2021 · 3 comments · Fixed by #101168
Labels
A-mir-opt Area: MIR optimizations C-bug Category: This is a bug.

Comments

@simonvandel
Copy link
Contributor

I expected the following:

fn f() -> usize  {       
    1 + if true { 1 } else { 2 }  
}

to const-fold into _0 = 2.

Godbolt: https://godbolt.org/z/e89dYj

Using -Zdump_mir=all shows that this may be a pass ordering issue.

Before SimplifyCfg-final

fn f() -> usize {
    let mut _0: usize;                   // return place in scope 0 at test.rs:2:11: 2:16
    let mut _1: usize;                   // in scope 0 at test.rs:3:9: 3:33
    let mut _2: bool;                    // in scope 0 at test.rs:3:12: 3:16

    bb0: {
        StorageLive(_1);                 // scope 0 at test.rs:3:9: 3:33
        StorageLive(_2);                 // scope 0 at test.rs:3:12: 3:16
        _2 = const true;                 // scope 0 at test.rs:3:12: 3:16
        goto -> bb1;                     // scope 0 at test.rs:3:9: 3:33
    }

    bb1: {
        _1 = const 1_usize;              // scope 0 at test.rs:3:19: 3:20
        goto -> bb3;                     // scope 0 at test.rs:3:9: 3:33
    }

    bb2: {
        _1 = const 2_usize;              // scope 0 at test.rs:3:30: 3:31
        goto -> bb3;                     // scope 0 at test.rs:3:9: 3:33
    }

    bb3: {
        StorageDead(_2);                 // scope 0 at test.rs:3:32: 3:33
        _0 = Add(const 1_usize, move _1); // scope 0 at test.rs:3:5: 3:33
        StorageDead(_1);                 // scope 0 at test.rs:3:32: 3:33
        return;                          // scope 0 at test.rs:4:2: 4:2
    }

    bb4 (cleanup): {
        resume;                          // scope 0 at test.rs:2:1: 4:2
    }
}

After SimplifyCfg-final

fn f() -> usize {
    let mut _0: usize;                   // return place in scope 0 at test.rs:2:11: 2:16
    let mut _1: usize;                   // in scope 0 at test.rs:3:9: 3:33
    let mut _2: bool;                    // in scope 0 at test.rs:3:12: 3:16

    bb0: {
        StorageLive(_1);                 // scope 0 at test.rs:3:9: 3:33
        StorageLive(_2);                 // scope 0 at test.rs:3:12: 3:16
        _2 = const true;                 // scope 0 at test.rs:3:12: 3:16
        _1 = const 1_usize;              // scope 0 at test.rs:3:19: 3:20
        StorageDead(_2);                 // scope 0 at test.rs:3:32: 3:33
        _0 = Add(const 1_usize, move _1); // scope 0 at test.rs:3:5: 3:33
        StorageDead(_1);                 // scope 0 at test.rs:3:32: 3:33
        return;                          // scope 0 at test.rs:4:2: 4:2
    }
}

So after SimplifyCfg-final it is clear that _0 = Add(const 1_usize, move _1) can be folded into _0 = 2. However, this is not done as ConstProp is only running early in the pipeline.

@simonvandel simonvandel added the C-bug Category: This is a bug. label Jan 31, 2021
@klensy
Copy link
Contributor

klensy commented Jan 31, 2021

Godbolt currently shows this on nightly, 1.49 with -O --emit=mir

fn f() -> usize {
    let mut _0: usize;                   // return place in scope 0 at ./example.rs:2:15: 2:20
    let mut _1: usize;                   // in scope 0 at ./example.rs:3:9: 3:33

    bb0: {
        StorageLive(_1);                 // scope 0 at ./example.rs:3:9: 3:33
        _1 = const 1_usize;              // scope 0 at ./example.rs:3:19: 3:20
        _0 = Add(const 1_usize, move _1); // scope 0 at ./example.rs:3:5: 3:33
        StorageDead(_1);                 // scope 0 at ./example.rs:3:32: 3:33
        return;                          // scope 0 at ./example.rs:4:2: 4:2
    }
}

@nagisa
Copy link
Member

nagisa commented Jan 31, 2021

This is a constant/value propagation which I'm sure has an issue for it already.

@camelid camelid added the A-mir-opt Area: MIR optimizations label Feb 1, 2021
@michaelmaitland
Copy link

Is this issue something I could pick up and work on?

@bors bors closed this as completed in 357f660 Nov 15, 2022
Aaron1011 pushed a commit to Aaron1011/rust that referenced this issue Jan 6, 2023
Add new MIR constant propagation based on dataflow analysis

The current constant propagation in `rustc_mir_transform/src/const_prop.rs` fails to handle many cases that would be expected from a constant propagation optimization. For example:
```rust
let x = if true { 0 } else { 0 };
```
This pull request adds a new constant propagation MIR optimization pass based on the existing dataflow analysis framework. Since most of the analysis is not unique to constant propagation, a generic framework has been extracted. It works on top of the existing framework and could be reused for other optimzations.

Closes rust-lang#80038. Closes rust-lang#81605.

## Todo
### Essential
- [x] [Writes to inactive enum variants](rust-lang#101168 (review)). Resolved by rejecting the registration of places with downcast projections for now. Could be improved by flooding other variants if mutable access to a variant is observed.
- [X] Handle [`StatementKind::CopyNonOverlapping`](rust-lang#101168 (comment)). Resolved by flooding the destination.
- [x] Handle `UnsafeCell` / `!Freeze` correctly.
- [X] Overflow propagation of `CheckedBinaryOp`: Decided to not propagate if overflow flag is `true` (`false` will still be propagated)
- [x] More documentation in general.
- [x] Arguments for correctness, documentation of necessary assumptions.
- [x] Better performance, or alternatively, require `-Zmir-opt-level=3` for now.

### Extra
- [x]  Add explicit unreachability, i.e. upgrading the lattice from $\mathbb{P} \to \mathbb{V}$ to $\set{\bot} \cup (\mathbb{P} \to \mathbb{V})$.
- [x] Use storage statements to improve precision.
- [ ] Consider opening issue for duplicate diagnostics: rust-lang#101168 (comment)
- [ ] Flood moved-from places with $\bot$ (requires some changes for places with tracked projections).
- [ ] Add downcast projections back in.
- [ ] [Algebraic simplifications](rust-lang#101168 (comment)) (possibly with a shared API; done by old const prop).
- [ ] Propagation through slices / arrays.
- [ ] Find other optimizations that are done by old `const_prop.rs`, but not by this one.
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.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants