Improve MIR match generation so that we more effecitvely rule out inapplicable match-pairs #29623
Labels
A-MIR
Area: Mid-level IR (MIR) - https://blog.rust-lang.org/2016/04/19/MIR.html
C-enhancement
Category: An issue proposing an enhancement or a PR with one.
T-compiler
Relevant to the compiler team, which will review and decide on the PR/issue.
Comments
nikomatsakis
added
A-MIR
|
There are FIXMEs in the code related to this issue. |
|
How hard is this to work on? |
|
@Eh2406 The code is mainly located in Grepping for |
|
Triage: FIXMEs are still there, so I assume this is still an issue. |
bors
added a commit
that referenced
this issue
Dec 17, 2018
Improve MIR match generation for ranges
Improves MIR match generation to rule out ranges/values distinct from the range that has been tested. e.g., for this code:
```rust
match x {
0..=5 if b => 0,
6..=10 => 1,
_ => 2,
}
```
MIR (before):
```rust
bb0: { ...; _4 = Le(const 0i32, _1); switchInt(move _4) -> [false: bb6, otherwise: bb5]; }
bb1: { _3 = const 0i32; goto -> bb8; }
bb2: { _6 = _2; switchInt(move _6) -> [false: bb6, otherwise: bb1]; } // If `!b`, jumps to test if `6 <= x <= 10`.
bb3: { _3 = const 1i32; goto -> bb8; }
bb4: { _3 = const 2i32; goto -> bb8; }
bb5: { _5 = Le(_1, const 5i32); switchInt(move _5) -> [false: bb6, otherwise: bb2]; }
bb6: { _7 = Le(const 6i32, _1); switchInt(move _7) -> [false: bb4, otherwise: bb7]; }
bb7: { _8 = Le(_1, const 10i32); switchInt(move _8) -> [false: bb4, otherwise: bb3]; }
```
MIR (after):
```rust
bb0: { ...; _4 = Le(const 0i32, _1); switchInt(move _4) -> [false: bb5, otherwise: bb6]; }
bb1: { _3 = const 0i32; goto -> bb8; }
bb2: { _6 = _2; switchInt(move _6) -> [false: bb4, otherwise: bb1]; } // If `!b`, jumps to `_ =>` arm.
bb3: { _3 = const 1i32; goto -> bb8; }
bb4: { _3 = const 2i32; goto -> bb8; }
bb5: { _7 = Le(const 6i32, _1); switchInt(move _7) -> [false: bb4, otherwise: bb7]; }
bb6: { _5 = Le(_1, const 5i32); switchInt(move _5) -> [false: bb5, otherwise: bb2]; }
bb7: { _8 = Le(_1, const 10i32); switchInt(move _8) -> [false: bb4, otherwise: bb3]; }
```
cc #29623
bors
added a commit
that referenced
this issue
Dec 17, 2018
Improve MIR match generation for ranges
Improves MIR match generation to rule out ranges/values distinct from the range that has been tested. e.g., for this code:
```rust
match x {
0..=5 if b => 0,
6..=10 => 1,
_ => 2,
}
```
MIR (before):
```rust
bb0: { ...; _4 = Le(const 0i32, _1); switchInt(move _4) -> [false: bb6, otherwise: bb5]; }
bb1: { _3 = const 0i32; goto -> bb8; }
bb2: { _6 = _2; switchInt(move _6) -> [false: bb6, otherwise: bb1]; } // If `!b`, jumps to test if `6 <= x <= 10`.
bb3: { _3 = const 1i32; goto -> bb8; }
bb4: { _3 = const 2i32; goto -> bb8; }
bb5: { _5 = Le(_1, const 5i32); switchInt(move _5) -> [false: bb6, otherwise: bb2]; }
bb6: { _7 = Le(const 6i32, _1); switchInt(move _7) -> [false: bb4, otherwise: bb7]; }
bb7: { _8 = Le(_1, const 10i32); switchInt(move _8) -> [false: bb4, otherwise: bb3]; }
```
MIR (after):
```rust
bb0: { ...; _4 = Le(const 0i32, _1); switchInt(move _4) -> [false: bb5, otherwise: bb6]; }
bb1: { _3 = const 0i32; goto -> bb8; }
bb2: { _6 = _2; switchInt(move _6) -> [false: bb4, otherwise: bb1]; } // If `!b`, jumps to `_ =>` arm.
bb3: { _3 = const 1i32; goto -> bb8; }
bb4: { _3 = const 2i32; goto -> bb8; }
bb5: { _7 = Le(const 6i32, _1); switchInt(move _7) -> [false: bb4, otherwise: bb7]; }
bb6: { _5 = Le(_1, const 5i32); switchInt(move _5) -> [false: bb5, otherwise: bb2]; }
bb7: { _8 = Le(_1, const 10i32); switchInt(move _8) -> [false: bb4, otherwise: bb3]; }
```
cc #29623
jonas-schievink
added
the
T-compiler
bors
added a commit
to rust-lang-ci/rust
that referenced
this issue
Mar 31, 2024
match lowering: sort `Eq` candidates in the failure case too
This is a slight tweak to MIR gen of matches. Take a match like:
```rust
match (s, flag) {
("a", _) if foo() => 1,
("b", true) => 2,
("a", false) => 3,
(_, true) => 4,
_ => 5,
}
```
If we switch on `s == "a"`, the first candidate matches, and we learn almost nothing about the second candidate. So there's a choice:
1. (what we do today) stop sorting candidates, keep the "b" case grouped with everything below. This could allow us to be clever here and test on `flag == true` next.
2. (what this PR does) sort "b" into the failure case. The "b" will be alone (fewer opportunities for picking a good test), but that means the two "a" cases require a single test.
Today, we aren't clever in which tests we pick, so this is an unambiguous win. In a future where we pick tests better, idk. Grouping tests as much as possible feels like a generally good strategy.
This was proposed in rust-lang#29623 (9 years ago :D)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Once we perform a test -- such as checking a value or a variant -- we then weed out the matches that are invalidated by this test. The current code is no as smart as it could be: for example, if we test and find that a value equals 'c', we ought to be able to rule out that the character also equals 'd'. But, because the test tells us nothing if we find that the character is NOT equal to 'c', we take the simple path right now and say that an equality test against 'c' and an equality test against 'd' are completely orthogonal from one another. Similar limitations exist for range tests, slice length tests, etc. We should do better!
The text was updated successfully, but these errors were encountered: