Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[X86] Recognize Clang's <=> code pattern #60012

Open
scottmcm opened this issue Jan 13, 2023 · 1 comment
Open

[X86] Recognize Clang's <=> code pattern #60012

scottmcm opened this issue Jan 13, 2023 · 1 comment

Comments

@scottmcm
Copy link

scottmcm commented Jan 13, 2023

Today, this code https://cpp.godbolt.org/z/e8q15zzK1

#include <compare>
std::strong_ordering cmp(int a, int b) {
    return a <=> b;
}

gives this select chain

define dso_local i8 @_Z3cmpii(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = icmp slt i32 %0, %1
  %4 = select i1 %3, i8 -1, i8 1
  %5 = icmp eq i32 %0, %1
  %6 = select i1 %5, i8 0, i8 %4
  ret i8 %6
}

which compiles to some pretty verbose assembly:

cmp(int, int):                               # @cmp(int, int)
        cmp     edi, esi
        setl    al
        neg     al
        or      al, 1
        xor     ecx, ecx
        cmp     edi, esi
        movzx   eax, al
        cmove   eax, ecx
        ret

There are other ways of doing this that are definitely better for size, and plausibly better for speed too https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign

For example, it could be

cmp(int, int):                               # @cmp(int, int)
        cmp     edi, esi
        setg    al
        setl    cl
        sub     al, cl
        ret

(I've filed this as x86-specific because the selects in LLVM-IR might be better for optimizations to use, as more obvious than the subtraction. The specific pattern that Clang emits for <=> is most important, but it would be nice if it also recognized -- or canonicalized in IR -- the bunch of equivalent select chains.)

@zygoloid
Copy link
Collaborator

There are a few other formulations here that don't canonicalize to the same thing; maybe that should be looked at too: https://godbolt.org/z/7fcrczYeo

rotateright added a commit that referenced this issue Jan 16, 2023
(A s>> (BW - 1)) + (zext (A s> 0)) --> (A s>> (BW - 1)) | (zext (A != 0))

https://alive2.llvm.org/ce/z/V-nM8N

This is not the form that we currently match as m_Signum(),
but I'm not sure if one is better than the other, so there's
a follow-up patch needed either way.

For this patch, it should be better for analysis to use a
not-null test and bitwise logic rather than >0 with add.
Codegen doesn't seem significantly different on any targets
that I looked at.

Also note that none of these variants is shown in issue #60012 -
those generally include at least one 'select', so that's likely
where these patterns will end up.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants