rust-lang / rust-lang/rust

Suboptimal order of tests in `match`

Open
#117,970 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-LLVM A-mir-opt C-bug I-slow
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.