Suboptimal eq compilation on structs compared to equivalent C++ code

The eq implementation produces worse code than the equivalent C++ code (Rust, C++)

I tried this code:

pub struct S {
    a: u8,
    b: u8,
    c: u8,
    d: u8,
}

pub fn eq(s1: &S, s2: &S) -> bool {
    s1.a == s2.a && s1.b == s2.b && s1.c == s2.c && s1.d == s2.d
}

I expected to see this happen:

The resulting assembly should load and compare a single u64:

example::eq:
        ldr     w8, [x0]
        ldr     w9, [x1]
        cmp     w8, w9
        cset    w0, eq
        ret

Instead, this happened:

The assembly loads and compares each u8 individually:

example::eq:
        ldrb    w9, [x0]
        mov     w8, wzr
        ldrb    w10, [x1]
        cmp     w9, w10
        b.ne    .LBB0_4
        ldrb    w9, [x0, #1]
        ldrb    w10, [x1, #1]
        cmp     w9, w10
        b.ne    .LBB0_4
        ldrb    w8, [x0, #2]
        ldrb    w9, [x1, #2]
        cmp     w8, w9
        b.ne    .LBB0_5
        ldrb    w8, [x0, #3]
        ldrb    w9, [x1, #3]
        cmp     w8, w9
        cset    w8, eq
.LBB0_4:
        mov     w0, w8
        ret
.LBB0_5:
        mov     w0, wzr
        ret

Meta

rustc --version --verbose:

rustc 1.68.0-nightly (88c58e3c2 2022-12-26)
binary: rustc
commit-hash: 88c58e3c2c097ebffac425d9e080dcb1aadf790e
commit-date: 2022-12-26
host: x86_64-unknown-linux-gnu
release: 1.68.0-nightly
LLVM version: 15.0.6
Compiler returned: 0

With more aggressive compilation flags I am seeing (latest Nightly):

example::eq:
        mov     eax, dword ptr [rdi]
        cmp     eax, dword ptr [rsi]
        sete    al
        ret

With more aggressive compilation flags I am seeing (latest Nightly):

example::eq:
        mov     eax, dword ptr [rdi]
        cmp     eax, dword ptr [rsi]
        sete    al
        ret

What flags did you use?

-O -Z mir-opt-level=4

Looks like the first two comparisons gets flattened into one block, and that prevents detection of the whole pattern.

SeparateConstSwitch (enabled at mir-opt-level >= 4) is the MIR opt which merges the short-circuiting failure paths into 1, and allows SimplifyCFG to reduce this to a pattern which can be turned into a memcmp.

#106294 might improve this.

I noticed in https://rust.godbolt.org/z/q768EYdqq that it's doing <2 x i8> dances:

  %0 = load <2 x i8>, ptr %s1, align 1, !dbg !11
  %1 = load <2 x i8>, ptr %s2, align 1, !dbg !12
  %2 = icmp eq <2 x i8> %0, %1, !dbg !11
  %3 = extractelement <2 x i1> %2, i64 0, !dbg !11
  %4 = extractelement <2 x i1> %2, i64 1, !dbg !11

which might be no longer needed once it's !noundef and it can thus just compare them both directly.

There's also something going on here related to the short-circuiting that I don't understand.

If I change it to

pub fn eq(s1: &S, s2: &S) -> bool {
    (s1.a == s2.a) & (s1.b == s2.b) & (s1.c == s2.c) & (s1.d == s2.d)
}

Then it optimizes as expected

define noundef zeroext i1 @_ZN7example2eq17h1d431ecac5604099E(ptr noalias nocapture noundef readonly align 1 dereferenceable(4) %s1, ptr noalias nocapture noundef readonly align 1 dereferenceable(4) %s2) unnamed_addr #0 !dbg !6 {
  %0 = load i32, ptr %s1, align 1, !dbg !11
  %1 = load i32, ptr %s2, align 1, !dbg !12
  %2 = icmp eq i32 %0, %1, !dbg !13
  ret i1 %2, !dbg !14
}

https://rust.godbolt.org/z/ThfqaW3cr

It's definitely marked dereferenceable(4) either way, so LLVM ought to be able to move the loads early either way.

@scottmcm

@scottmcm Short-circuiting is relevant in that moving everything into one block is generally non-profitable. There is a special pass that detects this pattern (MergeICmps) and converts it into memcmp/bcmp, which is then later expanded into a target-specific efficient comparison sequence. This is a backend IR pass, so you don't see it in --emit=llvm-ir output.

However, it requires a pretty specific pattern, and does not handle the case where the control flow has been partially flattened and one pair of comparisons uses a select rather than a branch.

Your X86 example adds insult to injury by actually vectorizing those two i8 comparisons: https://llvm.godbolt.org/z/qPe6Kfq6e That looks pretty clearly non-profitable: https://llvm.godbolt.org/z/dT85WE8xn

Edit: Filed llvm/llvm-project#59867 for the SLPVectorizer issue.

I suppose this opt would be specifically enabled by our optimization semantics allowing spurious reads. No change since the noundef add, though. The SeparateConstSwitch pass may be affected by #107009 being accepted.

Looks like this is fixed now, we should have a test for this if we don't already

Auto merge of rust-lang#124299 - clubby789:106269-test, r=nikic

Rollup merge of rust-lang#124299 - clubby789:106269-test, r=nikic

Unrolled build for rust-lang#124299

Navigation Menu

Repository navigation

Suboptimal `eq` compilation on structs compared to equivalent C++ code #106269

I tried this code:

I expected to see this happen:

Instead, this happened:

Meta

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Suboptimal eq compilation on structs compared to equivalent C++ code #106269

Description

I tried this code:

I expected to see this happen:

Instead, this happened:

Meta

Activity

leonardo-m commented on Dec 29, 2022

Kmeakin commented on Dec 29, 2022

leonardo-m commented on Dec 29, 2022

nikic commented on Dec 29, 2022

clubby789 commented on Jan 2, 2023

scottmcm commented on Jan 6, 2023

nikic commented on Jan 6, 2023

workingjubilee commented on Feb 20, 2023

clubby789 commented on Apr 13, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Suboptimal `eq` compilation on structs compared to equivalent C++ code #106269