Suboptimal order of tests in `match`

[Kmeakin]

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>

[Kmeakin]

@rustbot label I-slow

[saethlin]

alive2 approves: https://alive2.llvm.org/ce/z/NLickb

[Kmeakin]

This could be fixed by better heuristics used by rustc when compiling match to MIR

https://dl.acm.org/doi/pdf/10.1145/1411304.1411311, section 8 gives some heuristics that can be used in selecting the order of tests

[dianqk]

#121397 will fix this issue, but I'm not sure if it is a special case.