Failure to optimise `std::cmp::{min,max}` on `bool`

[Kmeakin]

I tried this code: (godbolt)

// DOES NOT optimise to `a & b`
pub fn min_std(a: bool, b: bool) -> bool {
    std::cmp::min(a, b)
}

// DOES NOT optimise to `a | b`
pub fn max_std(a: bool, b: bool) -> bool {
    std::cmp::max(a, b)
}

// DOES optimise to `a & b`
pub fn min_if(a: bool, b: bool) -> bool {
    if (a < b) {
        return a;
    }
    b
}

// DOES optimise to `a | b` on x86_64
// DOES NOT optimise to `a | b` on AArch64
pub fn max_if(a: bool, b: bool) -> bool {
    if (a > b) {
        return a;
    }
    b
}

pub fn min_and(a: bool, b: bool) -> bool {
    a & b
}
pub fn max_or(a: bool, b: bool) -> bool {
    a | b
}

I expected to see this happen:
All implementations of max should optimise to a & b. All implementations of min should optimise to a | b

Instead, this happened:
The generated assembly code is suboptimal for min_std, max_std, max_ternary and max_if (on AArch64)

min_std and max_std can be fixed by overriding the default implementation of min and max for bool:

impl Ord for bool {
    fn min(self, other: Self) -> Self { a & b }
    fn max(self, other: Self) -> Self { a | b }
}

But it might be worth investigating the LLVM-IR that rustc generates in min_if/max_if too to see why it isn't optimised to llvm.umin()/llvm.umax()

Meta

rustc --version --verbose:

rustc 1.73.0-nightly (f88a8b71c 2023-08-08)
binary: rustc
commit-hash: f88a8b71cebb730cbd5058c45ebcae1d4d9be377
commit-date: 2023-08-08
host: x86_64-unknown-linux-gnu
release: 1.73.0-nightly
LLVM version: 17.0.0

Backtrace

<backtrace>

[lenawanel]

here is the llvm ir this generates:

@example::min_and = unnamed_addr alias i1 (i1, i1), ptr @example::min_if

; example::min_std
define noundef zeroext i1 @example::min_std(i1 noundef zeroext %a, i1 noundef zeroext %b) unnamed_addr personality ptr @rust_eh_personality {
start:
  %.neg.i = sext i1 %a to i8
  %0 = zext i1 %b to i8
  %1 = xor i8 %0, -1
  %switch.i = icmp eq i8 %1, %.neg.i
  %_0.0.i = select i1 %switch.i, i1 %b, i1 %a
  ret i1 %_0.0.i
}

; example::max_std
define noundef zeroext i1 @example::max_std(i1 noundef zeroext %a, i1 noundef zeroext %b) unnamed_addr personality ptr @rust_eh_personality {
start:
  %.neg.i = sext i1 %a to i8
  %0 = zext i1 %b to i8
  %1 = xor i8 %0, -1
  %switch.i = icmp eq i8 %1, %.neg.i
  %_0.0.i = select i1 %switch.i, i1 %a, i1 %b
  ret i1 %_0.0.i
}

; example::min_if
define noundef zeroext i1 @example::min_if(i1 noundef zeroext %a, i1 noundef zeroext %b) unnamed_addr {
start:
  %a.b = and i1 %a, %b
  ret i1 %a.b
}

; example::max_if
define noundef zeroext i1 @example::max_if(i1 noundef zeroext %a, i1 noundef zeroext %b) unnamed_addr {
start:
  %0 = xor i1 %b, true
  %_3 = and i1 %0, %a
  %a.b = select i1 %_3, i1 %a, i1 %b
  ret i1 %a.b
}

; example::max_or
define noundef zeroext i1 @example::max_or(i1 noundef zeroext %a, i1 noundef zeroext %b) unnamed_addr {
start:
  %_0 = or i1 %a, %b
  ret i1 %_0
}

declare noundef i32 @rust_eh_personality(i32 noundef, i32 noundef, i64 noundef, ptr noundef, ptr noundef) unnamed_addr #1

it first extends the i1s to i8s, negating b and sign extending a, and then finally does an icmp, which seems very convoluted to me.
(it's also interesting that it optimized max_if way better than min_if)

[lenawanel]

https://github.com/rust-lang/rust/tree/master/library/core/src#L1397 explains the zero and sign extensions. ({min,max} call {min,max}_by with Ord::cmp under the hood, and Ord::cmp sign extends them both.)

[Kmeakin]

@rustbot label +I-slow

[Kmeakin]

Corresponding LLVM issue: llvm/llvm-project#64537