[Bug target/103973] New: x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[Bug target/103973] New: x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[nekotekina at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

            Bug ID: 103973
           Summary: x86: 4-way comparison of floats/doubles with spaceship
                    operator possibly suboptimal
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
          Assignee: unassigned at gcc dot gnu.org
          Reporter: nekotekina at gmail dot com
  Target Milestone: ---

Hello, I may be missing something here but the generated code seems strange and
suboptimal. It looks like all 4 possible paths can use flags from a single
UCOMISD instruction, not calling it 3 times in worst case.

cmp4way(double, double):
        ucomisd xmm0, xmm1
        jp      .L8
        mov     eax, 0
        jne     .L8
.L2:
        ret
.L8:
        comisd  xmm1, xmm0
        mov     eax, -1
        ja      .L2
        ucomisd xmm0, xmm1
        setbe   al
        add     eax, 1
        ret

https://godbolt.org/z/j1j7G1MYP

#include <compare>

auto cmp4way(double a, double b)
{
    return a <=> b;
}

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[crazylht at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

Hongtao.liu <crazylht at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |crazylht at gmail dot com

--- Comment #1 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to Ivan from comment #0)
> Hello, I may be missing something here but the generated code seems strange
> and suboptimal. It looks like all 4 possible paths can use flags from a
> single UCOMISD instruction, not calling it 3 times in worst case.
There're also COMISD which is defferent from UCOMISD as

---cut from intel sdm---------
The UCOMISD instruction differs from the COMISD instruction in that it signals
a SIMD floating-point invalid oper-
ation exception (#I) only when a source operand is an SNaN. The COMISD
instruction signals an invalid operation
exception only if a source operand is either an SNaN or a QNaN.
----cut end---------------------

And they're different in GCC rtl representation, that's why CSE doesn't helps
here.

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[crazylht at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

--- Comment #2 from Hongtao.liu <crazylht at gmail dot com> ---
W/ -ffast-math only one COMISD is used.

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
With -O2 -fno-trapping-math, we get:
        ucomisd %xmm1, %xmm0
        jp      .L9
        movl    $0, %eax
        jne     .L9
        ret
        .p2align 4,,10
        .p2align 3
.L9:
        ucomisd %xmm0, %xmm1
        ja      .L12
        ucomisd %xmm1, %xmm0
        setbe   %al
        addl    $1, %eax
        ret
        .p2align 4,,10
        .p2align 3
.L12:
        movl    $-1, %eax
        ret


With -O2 -fno-trapping-math -ffinite-math-only we get:
        comisd  %xmm1, %xmm0
        je      .L12
        jb      .L13
        movl    $1, %edx
        movl    $2, %eax
        cmova   %edx, %eax
        ret
        .p2align 4,,10
        .p2align 3
.L12:
        xorl    %eax, %eax
        ret
        .p2align 4,,10
        .p2align 3
.L13:
        movl    $-1, %eax
        ret

The main reason is NaNs are interesting and trapping comparisons are also
interesting. Note LLVM does not implement trapping math at all which is why
their code gen is different too.

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[nekotekina at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

--- Comment #4 from Ivan <nekotekina at gmail dot com> ---
So there is nothing to improve here? That's good to know, I suppose it can be
closed then.

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2022-01-11
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
             Target|                            |x86_64-*-* i?86-*-*

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
We are lowering this to

return <retval> = TARGET_EXPR <D.8264, SAVE_EXPR <a> != SAVE_EXPR <b> ?
SAVE_EXPR <a> < SAVE_EXPR <b> ? less : SAVE_EXPR <b> < SAVE_EXPR <a> ? greater
: unordered : equivalent>>>;

I don't think we can elide the first ucomisd, but we should be able to CSE the
last (from the original quoted assembler), not sure if it ultimatively results
in better code though.

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #5)
> We are lowering this to
> 
> return <retval> = TARGET_EXPR <D.8264, SAVE_EXPR <a> != SAVE_EXPR <b> ?
> SAVE_EXPR <a> < SAVE_EXPR <b> ? less : SAVE_EXPR <b> < SAVE_EXPR <a> ?
> greater : unordered : equivalent>>>;
> 
> I don't think we can elide the first ucomisd, but we should be able to CSE
> the last (from the original quoted assembler), not sure if it ultimatively
> results in better code though.

Why we couldn't do that?  It is true that GIMPLE starts with != comparison that
shouldn't raise exceptions if a or b is qNaN, but if one or both of the
operands is qNaN, then they will compare unequal and < comparison that should
raise exceptions if a or b is qNaN is done.
So, it would be nice if we could at gimple_isel or expansion or later pattern
recognize this and emit optimal code for it.

C testcase:
int
foo (double a, double b)
{
  if (a == b)
    return 0;
  if (a < b)
    return -1;
  if (a > b)
    return 1;
  return 2;
}

We should have something like:
comisd %xmm0, %xmm1
jp 1f
movl $0, %eax
jne 2f
3:
ret
2:
sbbl %eax, %eax
andl $2, %eax
subl $1, %eax
ret
1:
movl $2, %eax
ret

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Perhaps add a new starship<mode>3 optab for it and pattern recognize it in
gimple_isel?  Though that would most likely handle just the 0, -1, 1, 2 case
that <=> emits and not say other constants that one could get e.g. with the
(much less likely):
#include <compare>
int cmp4way(double a, double b)
{
    auto c = a <=> b;
    if (c == std::partial_ordering::equivalent) return 42;
    if (c == std::partial_ordering::less) return 137;
    if (c == std::partial_ordering::unordered) return -35;
    return 139;
}

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 52195
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52195&action=edit
gcc12-pr103973.patch

Untested fix.

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:463d9108766dcbb6a1051985e6c840a46897fe10

commit r12-6637-g463d9108766dcbb6a1051985e6c840a46897fe10
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Jan 17 13:39:05 2022 +0100

    widening_mul, i386: Improve spaceship expansion on x86 [PR103973]

    C++20:
     #include <compare>
     auto cmp4way(double a, double b)
     {
       return a <=> b;
     }
    expands to:
            ucomisd %xmm1, %xmm0
            jp      .L8
            movl    $0, %eax
            jne     .L8
    .L2:
            ret
            .p2align 4,,10
            .p2align 3
    .L8:
            comisd  %xmm0, %xmm1
            movl    $-1, %eax
            ja      .L2
            ucomisd %xmm1, %xmm0
            setbe   %al
            addl    $1, %eax
            ret
    That is 3 comparisons of the same operands.
    The following patch improves it to just one comparison:
            comisd  %xmm1, %xmm0
            jp      .L4
            seta    %al
            movl    $0, %edx
            leal    -1(%rax,%rax), %eax
            cmove   %edx, %eax
            ret
    .L4:
            movl    $2, %eax
            ret
    While a <=> b expands to a == b ? 0 : a < b ? -1 : a > b ? 1 : 2
    where the first comparison is equality and this shouldn't raise
    exceptions on qNaN operands, if the operands aren't equal (which
    includes unordered cases), then it immediately performs < or >
    comparison and that raises exceptions even on qNaNs, so we can just
    perform a single comparison that raises exceptions on qNaN.
    As the 4 different cases are encoded as
    ZF CF PF
    1  1  1  a unordered b
    0  0  0  a > b
    0  1  0  a < b
    1  0  0  a == b
    we can emit optimal sequence of comparions, first jp
    for the unordered case, then je for the == case and finally jb
    for the < case.

    The patch pattern recognizes spaceship-like comparisons during
    widening_mul if the spaceship optab is implemented, and replaces
    those comparisons with comparisons of .SPACESHIP ifn which returns
    -1/0/1/2 based on the comparison.  This seems to work well both for the
    case of just returning the -1/0/1/2 (when we have just a common
    successor with a PHI) or when the different cases are handled with
    various other basic blocks.  The testcases cover both of those cases,
    the latter with different function calls in those.

    2022-01-17  Jakub Jelinek  <jakub@redhat.com>

            PR target/103973
            * tree-cfg.h (cond_only_block_p): Declare.
            * tree-ssa-phiopt.c (cond_only_block_p): Move function to ...
            * tree-cfg.c (cond_only_block_p): ... here.  No longer static.
            * optabs.def (spaceship_optab): New optab.
            * internal-fn.def (SPACESHIP): New internal function.
            * internal-fn.h (expand_SPACESHIP): Declare.
            * internal-fn.c (expand_PHI): Formatting fix.
            (expand_SPACESHIP): New function.
            * tree-ssa-math-opts.c (optimize_spaceship): New function.
            (math_opts_dom_walker::after_dom_children): Use it.
            * config/i386/i386.md (spaceship<mode>3): New define_expand.
            * config/i386/i386-protos.h (ix86_expand_fp_spaceship): Declare.
            * config/i386/i386-expand.c (ix86_expand_fp_spaceship): New
function.
            * doc/md.texi (spaceship@var{m}3): Document.

            * gcc.target/i386/pr103973-1.c: New test.
            * gcc.target/i386/pr103973-2.c: New test.
            * gcc.target/i386/pr103973-3.c: New test.
            * gcc.target/i386/pr103973-4.c: New test.
            * gcc.target/i386/pr103973-5.c: New test.
            * gcc.target/i386/pr103973-6.c: New test.
            * gcc.target/i386/pr103973-7.c: New test.
            * gcc.target/i386/pr103973-8.c: New test.
            * gcc.target/i386/pr103973-9.c: New test.
            * gcc.target/i386/pr103973-10.c: New test.
            * gcc.target/i386/pr103973-11.c: New test.
            * gcc.target/i386/pr103973-12.c: New test.
            * gcc.target/i386/pr103973-13.c: New test.
            * gcc.target/i386/pr103973-14.c: New test.
            * gcc.target/i386/pr103973-15.c: New test.
            * gcc.target/i386/pr103973-16.c: New test.
            * gcc.target/i386/pr103973-17.c: New test.
            * gcc.target/i386/pr103973-18.c: New test.
            * gcc.target/i386/pr103973-19.c: New test.
            * gcc.target/i386/pr103973-20.c: New test.
            * g++.target/i386/pr103973-1.C: New test.
            * g++.target/i386/pr103973-2.C: New test.
            * g++.target/i386/pr103973-3.C: New test.
            * g++.target/i386/pr103973-4.C: New test.
            * g++.target/i386/pr103973-5.C: New test.
            * g++.target/i386/pr103973-6.C: New test.
            * g++.target/i386/pr103973-7.C: New test.
            * g++.target/i386/pr103973-8.C: New test.
            * g++.target/i386/pr103973-9.C: New test.
            * g++.target/i386/pr103973-10.C: New test.
            * g++.target/i386/pr103973-11.C: New test.
            * g++.target/i386/pr103973-12.C: New test.
            * g++.target/i386/pr103973-13.C: New test.
            * g++.target/i386/pr103973-14.C: New test.
            * g++.target/i386/pr103973-15.C: New test.
            * g++.target/i386/pr103973-16.C: New test.
            * g++.target/i386/pr103973-17.C: New test.
            * g++.target/i386/pr103973-18.C: New test.
            * g++.target/i386/pr103973-19.C: New test.
            * g++.target/i386/pr103973-20.C: New test.

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.

[Bug target/103973] x86: 4-way comparison of floats/doubles with spaceship operator possibly suboptimal

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103973

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by hongtao Liu <liuhongt@gcc.gnu.org>:

https://gcc.gnu.org/g:5e26bf17220926d308d0e3bb82bae6e592d2e485

commit r12-6655-g5e26bf17220926d308d0e3bb82bae6e592d2e485
Author: liuhongt <hongtao.liu@intel.com>
Date:   Tue Jan 18 10:45:10 2022 +0800

    Adjust testcase for --target_board='unix{-m64\ -march=cascadelake}'

    Change scan-assembler from "\tucomisd" to "\t\[v\]?ucomisd".

    gcc/testsuite/ChangeLog:

            PR target/103973
            * g++.target/i386/pr103973-1.C: Change scan-assembler from
            "\tucomisd" to "\t\[v\]?ucomisd".
            * g++.target/i386/pr103973-11.C: Ditto.
            * g++.target/i386/pr103973-13.C: Ditto.
            * g++.target/i386/pr103973-15.C: Ditto.
            * g++.target/i386/pr103973-3.C: Ditto.
            * g++.target/i386/pr103973-5.C: Ditto.
            * g++.target/i386/pr103973-7.C: Ditto.
            * g++.target/i386/pr103973-9.C: Ditto.
            * gcc.target/i386/pr103973-1.c: Ditto.
            * gcc.target/i386/pr103973-11.c: Ditto.
            * gcc.target/i386/pr103973-13.c: Ditto.
            * gcc.target/i386/pr103973-15.c: Ditto.
            * gcc.target/i386/pr103973-3.c: Ditto.
            * gcc.target/i386/pr103973-5.c: Ditto.
            * gcc.target/i386/pr103973-7.c: Ditto.
            * gcc.target/i386/pr103973-9.c: Ditto.