[Bug rtl-optimization/94795] New: Failure to use fast sbb method on x86 for spreading any set bit to all bits

[Bug rtl-optimization/94795] New: Failure to use fast sbb method on x86 for spreading any set bit to all bits

[gabravier at gmail dot com]

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

            Bug ID: 94795
           Summary: Failure to use fast sbb method on x86 for spreading
                    any set bit to all bits
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

int isNonzero(int x)
{
    if (x == 0)
        return 0x00000000;
    else
        return 0xFFFFFFFF;
}

On x86, this can be simplified to a `neg`+`sbb`. LLVM does this transformation,
but GCC doesn't

Comparison here : https://godbolt.org/z/QFz9to

[Bug rtl-optimization/94795] Failure to use fast sbb method on x86 for spreading any set bit to all bits

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Target|                            |x86_64-*-* i?86-*-*
   Last reconfirmed|                            |2020-04-27
           Keywords|                            |missed-optimization
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.

[Bug rtl-optimization/94795] Failure to use fast sbb method on x86 for spreading any set bit to all bits

[gabravier at gmail dot com]

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

--- Comment #2 from Gabriel Ravier <gabravier at gmail dot com> ---
Also, I can also provide this a very similar function for which such an
optimization could be helpful : 

int f(int x)
{
    return -(x == 0);
}

LLVM optimises that function to this : 

f(int):
  cmp edi, 1
  sbb eax, eax
  ret

Whereas GCC currently does 

f(int):
  xor eax, eax
  test edi, edi
  sete al
  neg eax
  ret

instead (see also https://godbolt.org/z/5_bRCR)

[Bug rtl-optimization/94795] Failure to use fast sbb method on x86 for spreading any set bit to all bits

[ubizjak at gmail dot com]

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

--- Comment #3 from Uroš Bizjak <ubizjak at gmail dot com> ---
(In reply to Gabriel Ravier from comment #2)
> Also, I can also provide this a very similar function for which such an

This optimization could be implemented with a simple combine splitter:

--cut here--
diff --git a/gcc/config/i386/i386.md b/gcc/config/i386/i386.md
index b426c21d3dd..8ea3a4a141a 100644
--- a/gcc/config/i386/i386.md
+++ b/gcc/config/i386/i386.md
@@ -17979,6 +18045,18 @@
              (clobber (reg:CC FLAGS_REG))])]
   "operands[2] = GEN_INT (INTVAL (operands[2]) + 1);")

+(define_split
+  [(set (match_operand:SWI48 0 "register_operand")
+       (neg:SWI48
+         (eq:SWI48
+           (match_operand:SWI 1 "nonimmediate_operand")
+           (const_int 0))))]
+  ""
+  [(set (reg:CC FLAGS_REG) (compare:CC (match_dup 1) (const_int 1)))
+   (parallel [(set (match_dup 0)
+                  (neg:SWI48 (ltu:SWI48 (reg:CC FLAGS_REG) (const_int 0))))
+             (clobber (reg:CC FLAGS_REG))])])
+
 (define_insn "*mov<mode>cc_noc"
   [(set (match_operand:SWI248 0 "register_operand" "=r,r")
        (if_then_else:SWI248 (match_operator 1 "ix86_comparison_operator"
--cut here--

(QImode and HImode modes have to be added to *x86_mov<mode>cc_0_m1_neg pattern
for the above splitter to also output to QImode and HImode operands.)

[Bug rtl-optimization/94795] Failure to use fast sbb method on x86 for spreading any set bit to all bits

[ubizjak at gmail dot com]

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

Uroš Bizjak <ubizjak at gmail dot com> changed:

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

--- Comment #4 from Uroš Bizjak <ubizjak at gmail dot com> ---
Created attachment 48386
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=48386&action=edit
Proof of concept patch

Proof of concept patch that implements both suggestions and results in:

        negl    %edi
        sbbl    %eax, %eax
        ret

for the first case and:

        cmpl    $1, %edi
        sbbl    %eax, %eax
        ret

for the second.

For the record, the transformation triggers:

- for linux x86_64 defconfig: 338 times neg/sbb and 28 times cmp/sbb

- for GCC bootstrap: 296 times neg/sbb and 1246 times cmp/sbb

[Bug rtl-optimization/94795] Failure to use fast sbb method on x86 for spreading any set bit to all bits

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Uros Bizjak <uros@gcc.gnu.org>:

https://gcc.gnu.org/g:9decd08b7b153a593a0b61e4f5373cb9574a1973

commit r11-45-g9decd08b7b153a593a0b61e4f5373cb9574a1973
Author: Uros Bizjak <ubizjak@gmail.com>
Date:   Mon May 4 18:53:30 2020 +0200

    i386: Use SBB more [PR94650]

    When returning 0 or -1, "SBB reg,reg" instruction that borrows carry
    flag can be used.  Carry flag can be generated by converting compare
    with zero to a LTU compare with one, so e.g.

            return -(x == 0)

    generates:

            cmpq    $1, %rdi
            sbbq    %rax, %rax

    instead of:

            xorl    %eax, %eax
            testq   %rdi, %rdi
            sete    %al
            negq    %rax

    A similar conversion can be used for

            return -(x != 0)

    where NEG insn can be used instead of compare.  According to x86 ISA,
    NEG insn sets carry flag when the source operand is != 0, resulting in:

            negq    %rdi
            sbbq    %rax, %rax

    The conversion avoids partial register stall with SETcc instructions.

            PR target/94795
            * config/i386/i386.md (*neg<mode>_ccc): New insn pattern.
            (EQ compare->LTU compare splitter): New splitter.
            (NE compare->NEG splitter): Ditto.

    testsuite/ChangeLog:

            PR target/94795
            * gcc.target/i386/pr94795-1.c: New test.
            * gcc.target/i386/pr94795-2.c: New test.

[Bug target/94795] Failure to use fast sbb method on x86 for spreading any set bit to all bits

[ubizjak at gmail dot com]

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

Uroš Bizjak <ubizjak at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
   Target Milestone|---                         |11.0
             Status|ASSIGNED                    |RESOLVED
          Component|rtl-optimization            |target

--- Comment #6 from Uroš Bizjak <ubizjak at gmail dot com> ---
Implemented for gcc-11.

[Bug target/94795] Failure to use fast sbb method on x86 for spreading any set bit to all bits

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vegard.nossum at oracle dot com

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 85224 has been marked as a duplicate of this bug. ***