Suboptimal order of tests in `match`
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 119k
- Forks
- 16.1k
- PR merge metrics
- PR metrics pending
Description
I tried this code (godbolt):
extern "Rust" {
fn foo() -> u32;
fn bar() -> u32;
fn baz() -> u32;
}
pub fn src(x: u32, y: u32) -> u32 {
unsafe {
match (x, y) {
(1, 10) => foo(),
(2, 10) => bar(),
(3, 10) => baz(),
_ => 0,
}
}
}
pub fn tgt(x: u32, y: u32) -> u32 {
unsafe {
match (y, x) {
(10, 1) => foo(),
(10, 2) => bar(),
(10, 3) => baz(),
_ => 0,
}
}
}
I expected to see this happen:
src should produce assembly as efficient as tgt, since they are both equivalent on all inputs. tgt first checks y against 10, then checks x against 1, 2 and 3:
example::tgt:
cmp w1, #10
b.ne .LBB1_5
cmp w0, #3
b.eq .LBB1_6
cmp w0, #2
b.eq .LBB1_7
cmp w0, #1
b.ne .LBB1_5
b foo
.LBB1_5:
mov w0, wzr
ret
.LBB1_6:
b baz
.LBB1_7:
b bar
Instead, this happened:
src checks x against 3, then checks y against 10, then checks x against 2, then checks y against 10, then checks x against 1, then checks y against 10:
example::src:
cmp w0, #3
b.eq .LBB0_5
cmp w0, #2
b.eq .LBB0_7
cmp w0, #1
b.ne .LBB0_9
cmp w1, #10
b.ne .LBB0_9
b foo
.LBB0_5:
cmp w1, #10
b.ne .LBB0_9
b baz
.LBB0_7:
cmp w1, #10
b.ne .LBB0_9
b bar
.LBB0_9:
mov w0, wzr
ret
Meta
rustc --version --verbose:
rustc 1.76.0-nightly (6b771f6b5 2023-11-15)
binary: rustc
commit-hash: 6b771f6b5a6c8b03b6322a9c77ac77cb346148f0
commit-date: 2023-11-15
host: x86_64-unknown-linux-gnu
release: 1.76.0-nightly
LLVM version: 17.0.5
Backtrace
<backtrace>
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
No repository file or test is named. Start by reproducing the Rust snippet and comparing the generated assembly for src and tgt; then locate the compiler's match-lowering path responsible for test ordering. Done means equivalent matches produce similarly efficient checks without regressing existing compiler tests.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100