3-way comparison is branchier after 1.71

[mqudsi]

Code

The following code contains two impls of the same (or what should be the same) logic. Prior to 1.71.0, the first impl (using Option::map() instead of match) would generate llvm ir that could be optimized to use cmov instructions, but the second impl (using match instead) would use jumps instead.

1.71.0+ generate the same (branchy) llvm ir for both implementations.
The regression goes away if compiling with -Zinline-mir=no, but the match implementation remains branchy.

#[derive(PartialEq)]
pub enum WSL {
    Any,
    V1,
    V2,
}

#[inline(never)]
pub fn is_wsl(wsl: Option<WSL>, v: WSL) -> bool {
    wsl.map(|wsl| v == WSL::Any || wsl == v).unwrap_or(false)
}

#[inline(never)]
pub fn is_wsl2(wsl: Option<WSL>, v: WSL) -> bool {
    match (wsl, v) {
        (Some(_), WSL::Any) => true,
        (Some(x), y) => x == y,
        _ => false
    }
}

Godbolt link

Optimized IR:

define noundef zeroext i1 @_ZN7example6is_wsl17h6965abaffb382d78E(i8 noundef %wsl, i8 noundef %0) unnamed_addr #0 {
start:
  %1 = icmp ne i8 %wsl, 3
  %_3.i.i = icmp eq i8 %0, 0
  %_4.i.i = icmp eq i8 %0, %wsl
  %.0.i.i = or i1 %_3.i.i, %_4.i.i
  %.0 = and i1 %1, %.0.i.i
  ret i1 %.0
}

compiling to following x86_64:

example::is_wsl::h6965abaffb382d78:
        cmp     dil, 3
        setne   cl
        test    sil, sil
        sete    dl
        cmp     sil, dil
        sete    al
        or      al, dl
        and     al, cl
        ret

vs unoptimized ir and asm:

define noundef zeroext i1 @_ZN7example7is_wsl217h164d1336a42bfb8dE(i8 noundef %wsl, i8 noundef %v) unnamed_addr #0 {
start:
  %.not = icmp eq i8 %wsl, 3
  br i1 %.not, label %bb5, label %bb2

bb2:                                              ; preds = %start
  %0 = icmp eq i8 %v, 0
  %1 = icmp eq i8 %wsl, %v
  %spec.select = or i1 %0, %1
  br label %bb5

bb5:                                              ; preds = %bb2, %start
  %.0 = phi i1 [ false, %start ], [ %spec.select, %bb2 ]
  ret i1 %.0
}

example::is_wsl2::h164d1336a42bfb8d:
        cmp     dil, 3
        jne     .LBB1_2
        xor     eax, eax
        ret
.LBB1_2:
        test    sil, sil
        sete    cl
        cmp     dil, sil
        sete    al
        or      al, cl
        ret

Version it worked on

It most recently worked on: 1.70.0

Version with regression

rustc --version --verbose:

1.71.0-stable

@rustbot modify labels: +regression-from-stable-to-stable -regression-untriaged +A-codegen +C-bug +I-slow +T-compiler

cc #91743

[dianqk]

Alive2: https://alive2.llvm.org/ce/z/VqNWdC

Related code: https://github.com/llvm/llvm-project/blob/3fa6b3bbdb0f9de18def8596d1f7fcec2ef77b5e/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L2992-L3012

There are many limitations to hoisting branch instructions. I am not sure if it is better to change these limitations.

[mqudsi]

It's actually a more fundamental issue than the case in the original post; even stripping down the code to just a binary enum still puts a branch in there. Godbolt

#[derive(PartialEq)]
pub enum WSL {
    Any,
    V1,
}

#[inline(never)]
pub fn is_wsl(wsl: Option<WSL>, v: WSL) -> bool {
    wsl.map(|wsl| wsl == v).unwrap_or(false)
}

example::is_wsl::h2f539bf0253b949c:
        cmp     dil, 2
        jne     .LBB0_2
        xor     eax, eax
        ret
.LBB0_2:
        test    dil, 1
        sete    al
        xor     al, sil
        ret

I'm going to leave the repro in the first post unmodified as the ideal fix would apply to that more difficult case as well, as this is just a contrived example.

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-medium