[RFC] Optimizing Comparisons Chains

Hi all,

I’m working on a new pass to optimize comparison chains.


Clang currently generates inefficient code when dealing with contiguous member-by-member structural equality. Consider:

struct A {

bool operator==(const A& o) const { return i == o.i && j == o.j; }

uint32 i;

uint32 j;


This generates:

mov eax, dword ptr [rdi]

cmp eax, dword ptr [rsi]

jne .LBB0_1

mov eax, dword ptr [rdi + 4]

cmp eax, dword ptr [rsi + 4]

sete al



xor eax, eax


I’ve been working on an LLVM pass that detects this pattern at IR level and turns it into a memcmp() call. This generates more efficient code:

mov rax, qword ptr [rdi]

cmp rax, qword ptr [rsi]

sete al


And thanks to recent improvements in the memcmp codegen, this can be made to work for all sizes.

Impact of the change

I’ve measured the change on std:pair/std::tuple. The pass typically makes the code 2-3 times faster with code that’s typically 2-3x times smaller.

A more detailed description can be found here and a proof of concept can be seen here.

Do you see any aspect of this that I may have missed?

For now I’ve implemented this as a separate pass. Would there be a better way to integrate it?

Thanks !

Hi Clement -

I started looking at CGP memcmp expansion for x86 more closely yesterday with:

And just made another change here:

This is part of solving:

So we want to enable the CGP expansion without regressing the optimal x86 memcmp codegen for the power-of-2 cases that are currently handled by SDAG builder. If this works out, we’ll abandon the memcmp SDAG transforms for x86 (and hopefully other targets too) because we’ll take care of all memcmp expansion in CGP.

I didn’t look closely at your new pass proposal, but I think you’ll see bigger improvements once we have the optimal x86 memcmp expansion in place for all sizes.

That sounds perfect, thanks. Indeed my pass currently improves performance only for small powers of two, and I’m waiting for the CGP approach to be enabled to make it work for all sizes !

This sounds useful and I’ve subscribed to the patch to watch it as I’d like to try it out on PPC as well. We’d certainly get better code gen on PPC with memcmp than we currently do. Thanks for working on this.