Bad codegen for comparing struct of two 16bit ints

I tried this code:

#[derive(Clone, Copy, PartialEq)]
pub struct Foo {
    pub x: u16,
    pub y: u16,
}

#[no_mangle]
fn eq(a: &Foo, b: &Foo) -> bool {
    a == b
}

I expected to see this happen: a and b are loaded into a single register each and then the registers are compared against each other.

Instead, this happened: https://rust.godbolt.org/z/8zaxKG8vx

For -Copt-level=2:

eq:
        movzx   eax, word ptr [rdi]
        movzx   ecx, word ptr [rdi + 2]
        xor     ax, word ptr [rsi]
        movzx   edx, word ptr [rsi + 2]
        xor     edx, ecx
        or      dx, ax
        sete    al
        ret

For -Copt-level=3:

eq:
        movd    xmm0, dword ptr [rdi]
        movd    xmm1, dword ptr [rsi]
        pcmpeqw xmm1, xmm0
        pshuflw xmm0, xmm1, 80
        pshufd  xmm0, xmm0, 80
        movmskpd        eax, xmm0
        cmp     eax, 3
        sete    al
        ret

Meta

rustc --version --verbose:
Both 1.86 and nightly.

Using transmute::<_, u32>(read_unaligned(self)) and transmute::<_, u32>(read_unaligned(other)) inside of the PartialEq impl produces the expected codegen.

Trying this in C shows that it is also unable to optimize (the equivalent of) Foo::eq, but it is able to generate good code when memcmp is used:

https://godbolt.org/z/cqhM9hThK

#include <stdint.h>
#include <stdbool.h>
#include <string.h>

typedef struct {
    uint16_t x;
    uint16_t y;
} Foo;

bool eq(const Foo* a, const Foo* b) {
    return memcmp(a, b, sizeof(Foo)) == 0;
}

bool partial_eq(const Foo* a, const Foo* b) {
    return a->x == b->x && a->y == b->y;
}

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

partial_eq:
        movzx   eax, word ptr [rdi]
        cmp     ax, word ptr [rsi]
        jne     .LBB1_1
        movzx   eax, word ptr [rdi + 2]
        cmp     ax, word ptr [rsi + 2]
        sete    al
        ret
.LBB1_1:
        xor     eax, eax
        ret

That suggests that codegen for Eq could be improved by using memcmp in some cases. (fields must be copy, no padding , probably other conditions that I'm missing).

At the time derives are expanded, field types aren’t known at all. The derive just gets tokens and it might not even see the same tokens as later stages of the compiler. So the derive can’t do the necessary checks (notably including: is bitwise equality even correct for all field types). In theory the built-in derives could expand to some magic intrinsic that’s lowered much later when types are known, but that’s a big hammer. I don’t see any fundamental reason why LLVM shouldn’t be able to do this optimization (at least for Rust) and that would help non-derived code as well. But I haven’t checked Alive2.

Note that a manual (a.x == b.x) && (a.y == b.y) compiles to the same suboptimal codegen (which makes sense, since that's what the derive expands to), but (a.x == b.x) & (a.y == b.y) (non-short-circuiting &) compiles to 32-bit load and compare.

Looks like LLVM in all three cases does 2 vectorized loads of 2 x i16, and then a compare of the vectors, but how it ANDs the resulting 2 x i1 is different: OP and && seems to do like if cmp[0] { cmp[1] } else { false }, while & does something else.

(Note the OP version's LLVM IR is different from the && version, but IIUC only in var names and debug info; they get deduplicated anyway if both are present)

// common prefix
  %0 = load <2 x i16>, ptr %a, align 2
  %1 = load <2 x i16>, ptr %b, align 2
  %2 = icmp eq <2 x i16> %0, %1

// OP and && verison
  %3 = extractelement <2 x i1> %2, i64 0
  %4 = extractelement <2 x i1> %2, i64 1
  %_0.sroa.0.0 = select i1 %3, i1 %4, i1 false
  ret i1 %_0.sroa.0.0

// & verison
  %shift = shufflevector <2 x i1> %2, <2 x i1> poison, <2 x i32> <i32 1, i32 poison>
  %3 = and <2 x i1> %2, %shift
  %_0 = extractelement <2 x i1> %3, i64 0
  ret i1 %_0

godbolt link with asm and llvm ir

(Maybe LLVM is assuming that the second fields could be poison in the && case, so avoiding using their comparison if the first comparison is false?)

but (a.x == b.x) & (a.y == b.y) (non-short-circuiting &) compiles to 32-bit load and compare.

Unfortunately not in the code I minimized this from that does roughly

#[unsafe(no_mangle)]
pub fn foo(a: &Foo) -> bool {
    foo_eq_3(a, &Foo { x: 1, y: 1 })
}

That still results in two separate loads even with non-short-circuiting &:

https://rust.godbolt.org/z/1e47McvW1

foo:
        movzx   eax, word ptr [rdi]
        xor     eax, 1
        movzx   ecx, word ptr [rdi + 2]
        xor     ecx, 1
        or      cx, ax
        sete    al
        ret

memorysafety/rav1d#1400 (comment) suggests that adding !undef to the load would fix this.

I assume they meant !noundef. As noted in a later comment rustc already adds that metadata when it emits LLVM IR, but SimplifyCFG drops them when turning the two branches on icmps into a select.

That's not simply a missed optimization opportunity. While the load of the second field can't load poison/undef, that property is control-dependent. For example, when matching on Option<u32> behind a reference, loading the u32 field in the Some case is also !noundef, but that part of memory will generally be undef/poison on the None branch. Thus, hoisting !noundef loads generally has to drop the !noundef metadata.

Solving this seems hard: I don't think LLVM has a way to express "loading through this pointer always reads initialized bytes" (like how dereferenceable says "loading through this pointer is always okay but may yield poison/undef"). I'm also no sure if we could apply such an attribute to Rust references -- it may break common unsafe patterns that form references to uninitialized memory. The reference conservatively calls that UB for now, but even there it's noted that this is controversial and may end up being non-UB. Miri doesn't enforce any such rule, I believe. So Rust may be unable to justify the desired optimization for the same reason why C compilers can't do it.

This might be a tangent, but it feels related and gives us some very useful building blocks:

If we had something like Plain (previously discussed in the forum) named AllBitPatternsValid<Repr=...> that was derived automatically for structs, and a const stdlib utility function std::mem::all_bit_patterns_valid<T> and std::mem::bitwise_compare<T>, could PartialEq generate code like so?

Fuller example at: https://play.rust-lang.org/?version=stable&mode=release&edition=2024&gist=bc3313d6c653a1c9844c49eaf735528a

unsafe trait AllBitPatternsValid {
    type Repr: AllBitPatternsValid;
}

pub const fn bitwise_compare<T: AllBitPatternsValid>(a: &T, b: &T) -> bool { ... }
pub const fn all_bit_patterns_valid<T: Sized>() -> bool { ... }

impl PartialEq for MyStruct {
    #[inline(always)]
    fn eq(self: &MyStruct, other: &MyStruct) -> bool {
        if all_bit_patterns_valid::<Self>() {
            bitwise_compare(self, other)
        } else {
            self.x == other.x && self.y == other.y
        }
    }
}

This approach wouldn’t directly address the !noundef metadata issue discussed earlier, but it could enable the compiler to perform safe, low-level comparisons for types where all bit patterns are valid, potentially improving performance.

Comparing the assembly when all_bit_patterns_valid returns false vs when all_bit_patterns_valid returns true, we can see that the compiler happily generates the wider comparisons:

-	movq	(%rsp), %rax
-	movq	8(%rsp), %rdi
-	movzwl	(%rax), %ecx
-	cmpw	(%rdi), %cx
-	jne	.LBB4_6
-	movzwl	2(%rax), %eax
-	cmpw	2(%rdi), %ax
-	jne	.LBB4_6
+	movq	8(%rsp), %rax
+	movq	16(%rsp), %rdi
+	movl	(%rax), %ebx
+	movl	(%rdi), %ebp

It's not a full solution. Obviously it would certainly require some nuance around types like Box that are technically AllBitPatternsValid but require pointer chasing to compute equality -- perhaps something like Plain or Pod might be a better approach, but it does seem like these building blocks could be very useful.

@nikic

After reviewing the LLVM issues I linked in my last comment more carefully:

The right combination of existing LLVM passes can optimize this kind of pattern at least in principle. I haven't manage to trigger MergeIcmps on the IR that rustc generates, but I believe that's just due to the very specific pattern matching that pass currently does, not a fundamental issue.
However, that's actually a miscompilation as alive2 shows (see discussion in MergeICmps reorders comparisons and introduces UB llvm/llvm-project#51187 and [MergeICmps] Correctness related to eq-chain comparisons llvm/llvm-project#62459). The problem is indeed, as I rediscovered during my flailing above, that poison infects the wider load we'd like to get. Unsurprisingly, @nikic described this problem and the possible solutions many years ago:

we can't actually fix this right now, because this needs the notion of a frozen load. Unless we want to expand into vector loads and comparisons (which is known to have very bad codegen)

So yeah, I was wrong in my earlier comments in this issue: LLVM could totally do this without any change to rustc's output, or even to Rust's UB rules. But current LLVM can't do it soundly and fixing that would probably require a new LLVM IR construct that does not exist today, the existing "freeze on SSA values" is not enough. (Or I guess someone could "just" fix all the cases of vector loads and comparisons having bad codegen for this use case 🙃)

Part of the problem here is that de facto memory cannot contain poison (making these transforms legal), but de jure it can (because people would like poison in memory in the future). Which gives us the awkward situation where you can't actually put poison in memory without miscompiles, while at the same time we also can't exploit the absence of poison for optimization purposes :)

Part of the problem here is that de facto memory cannot contain poison (making these transforms legal), but de jure it can (because people would like poison in memory in the future)

I'm curious as to how that would work: would each byte have 257 possible bit patterns? Presumably you would store this separately as a validity bitmask (similar to sanitizers, valgrind etc work).

But this would also break common optimised assembly implementations of strlen, memcmp, etc where you do full aligned loads into SIMD registers and deal with "read past the end" in clever ways. So I'm sceptical of people wanting to break backwards compatibility like that, at least on x86-64¹. And LLVM should strive for generating the best possible code for each ISA.

But following the specifics of the architecture manual trumps "there is no implementation that does that", fair enough. (I assume that when you said "de jure" you have such a specific thing to point to? Because otherwise it is not really "de jure".)

But thinking about this from another angle: the Rust type system should be rich enough to allow optimising this anyway: an T& where T contains no MaybeUninit, and is valid for all bit patterns should allow for this. Are there some missing annotations for telling LLVM about this?

Apple or Google on ARM? Anything could happen, they care much less about breaking backward compatibility. ↩

This LLVM issue also seems very relevant: llvm/llvm-project#52930

In that case, could a MIR optimization be an interim solution after all? The MIR for derived Eq for simple structs is very regular, so it should be possible (assuming this is valid according to UCG) to collapse several consecutive comparisons to a u32/u64 comparison, or transform to &[u8; N] and have LLVM figure out how to convert it back to an int compare.

EDIT: HN comment mentions that this is not always guaranteed to be a beneficial transformation.

Maybe rustc could take advantage of StructuralPartialEq to special-case code generation of PartialEq?

fn structural(a: &Foo) -> bool {
    match *a {
        Foo { x: 7, y: 11 } => true,
        _ => false,
    }
}

Derive is generated as a macro without type knowledge, but match code generation is up to the compiler. I hoped it would already have better codegen, but as of 1.86 that's not the case:

https://rust.godbolt.org/z/7eMf9sKbs

In that case, could a MIR optimization be an interim solution after all? The MIR for derived Eq for simple structs is very regular, so it should be possible (assuming this is valid according to UCG) to collapse several consecutive comparisons to a u32/u64 comparison, or transform to &[u8; N] and have LLVM figure out how to convert it back to an int compare.

Rewriting it to loads and comparisons of wider integers needs something like LLVM's (not yet existing) "frozen load" which MIR doesn't have and which rustc can't just introduce without there being something in LLVM it can lower to. Rewriting it as a &[u8; N] comparison seems sound to me, it's essentially the same trick as LLVM's MergeICmps -- punting the "frozen load" problem to the later pass that hopefully specializes the generic memcmp call to something efficient. However, this rewrite should only be done if you know for sure that this specialization will happen, otherwise it's a pessimization. LLVM has hooks that allow MergeICmps to figure this out. In theory rustc could also access those hooks, but this may be tricky because ~~MIR passes may run before a codegen backend is even loaded, and~~ the same optimized MIR can be lowered to LLVM IR several times under different compiler flags that may affect whether any given byte comparison will be efficient or not. (Not to mention that the same optimized MIR can be passed to multiple codegen backends, so it really ought to be LLVM-independent.)

Rewriting it to loads and comparisons of wider integers needs something like LLVM's (not yet existing) "frozen load" which MIR doesn't have and which rustc can't just introduce without there being something in LLVM it can lower to.

Why would that be necessary if we restrict this to derived Eq impls? I would expect it to be library UB to pass an uninitialized struct to a derived Eq impl, so it would be fine for the derive impl to be changed in a way that causes compiler UB in that case. This wouldn't apply to manually implemented Eq however as those may have chosen to not make this library UB.

I agree, if it's restricted to derived impls it's fine, I just hadn't considered the possibility of restricting a MIR pass to code from derived impls. It could be tricky w.r.t. pass ordering though: if you do it before inlining you may not see that the field comparisons are trivial, if you do it after inlining you have to keep track of which code came from derived impls. As discussed up-thread, an alternative is changing the derive's expansion to include something like

if core::intrinsics::can_compare_bitwise::<Self>() {
    core::intrinsics::compare_bitwise(self, other)
} else {
    // as before
}

I'm going to try implementing the intrinsics idea. It's possible it will be unmergeable due to the opsem issues, but if it has compelling perf implications, that could motivate the discussion.

Trying to do this as an optimization in MIR faces essentially the same problem as asking LLVM to do it. We'd need find a way to make programs like the following UB, otherwise the "optimization" would introduce UB1 in such programs:

FYI starting in 1.89, the derived PartialEq tries to compare scalar fields first: https://godbolt.org/z/bT6hn9d8c

And it was pointed out in the precipitating issue #141141 that the comparison order is not documented anywhere.

the derived PartialEq tries to compare scalar fields first

Do we have any evidence that that improves things? It's a bunch of complexity in the derive for a very weak heuristic -- can't even do NonZero<u32> -- that doesn't even seem consistently obviously better (if there's an [u8; 16] in there it's probably better to compare before a bool) and landed with no codegen tests...

Navigation Menu

Repository navigation

Bad codegen for comparing struct of two 16bit ints #140167

Meta

16 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Bad codegen for comparing struct of two 16bit ints #140167

Description

Meta

Activity

bjorn3 commented on Apr 22, 2025

folkertdev commented on Apr 22, 2025

hanna-kruppe commented on Apr 22, 2025

zachs18 commented on Apr 24, 2025

bjorn3 commented on Apr 24, 2025

jrmuizel commented on May 20, 2025

hanna-kruppe commented on May 20, 2025

mmastrac commented on May 22, 2025

16 remaining items

hanna-kruppe commented on May 22, 2025

nikic commented on May 22, 2025

VorpalBlade commented on May 22, 2025

Footnotes

Diggsey commented on May 22, 2025

adrian17 commented on May 23, 2025

kornelski commented on May 23, 2025

hanna-kruppe commented on May 24, 2025

bjorn3 commented on May 24, 2025

hanna-kruppe commented on May 24, 2025

saethlin commented on Nov 23, 2025

saethlin commented on Nov 23, 2025

scottmcm commented on Mar 23, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions