[Bug c/68110] New: __builtin_sub_overflow unsigned performance issue

[Bug c/68110] New: __builtin_sub_overflow unsigned performance issue

[eggert at gnu dot org]

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

            Bug ID: 68110
           Summary: __builtin_sub_overflow unsigned performance issue
           Product: gcc
           Version: 5.2.1
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: eggert at gnu dot org
  Target Milestone: ---

I ran into this minor performance issue when changing Gnulib's lib/intprops.h
to use the new __builtin_sub_overflow function. I found that
__builtin_sub_overflow is less efficient than the portable C code that it
replaced, when the operands and result are unsigned, or unsigned long, or
unsigned long long. To reproduce the problem, compile and run the following
program with 'gcc -O2 -S' on x86-64:

  _Bool f1 (unsigned long long a, unsigned long long b)
  {
    return a < b;
  }

  _Bool f2 (unsigned long long a, unsigned long long b)
  {
    unsigned long long r;
    return __builtin_sub_overflow (a, b, &r);
  }

Although the functions are semantically equivalent, f1 uses only 3
instructions:

        f1:
                cmpq    %rsi, %rdi
                setb    %al
                ret

whereas f2 uses 5 instructions:

        f2:
                movq    %rdi, %rax
                subq    %rsi, %rax
                cmpq    %rdi, %rax
                seta    %al
                ret

There is a similar problem for x86.

[Bug target/68110] __builtin_sub_overflow unsigned performance issue

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |x86_64*-* i686-*-*
          Component|c                           |target

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Looks like the unused sub is not being removed.
Normally when someone uses __builtin_sub_overflow, the sub will not be unused.

[Bug target/68110] __builtin_sub_overflow unsigned performance issue

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So the question is does anyone use this function without "a - b" later on?  If
not then it is just a microbenchmark of this code is showing the regression and
I would say the microbenchmark is wrong.

[Bug target/68110] __builtin_sub_overflow unsigned performance issue

[eggert at gnu dot org]

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

--- Comment #3 from Paul Eggert <eggert at gnu dot org> ---
(In reply to Andrew Pinski from comment #2)
> So the question is does anyone use this function without "a - b" later on? 

Not that I know of. The usual pattern for callers of the Gnulib macro is to use
the macro to check whether there's overflow, and then to subtract if the result
wouldn't overflow. So you're correct that my example is a microbenchmark and is
not a good representative.

That being said, and I'm just thinking aloud here, it may be helpful for GCC to
try "a < b" as an alternative way to test for unsigned subtraction overflow, or
conversely to have GCC use __builtin_sub_overflow as an alternative way to
compute "a < b". Here's a slightly-more-realistic example:

  unsigned long
  sub1 (unsigned long a, unsigned long b)
  {
    if (a < b)
      return b - a;
    else
      return a - b;
  }

  unsigned long
  sub2 (unsigned long a, unsigned long b)
  {
    unsigned long c;
    if (__builtin_sub_overflow (a, b, &c))
      return b - a;
    else
      return c;
  }

On x86-64, gcc -O2 -S generates this:

  sub1:
          movq    %rsi, %rdx
          movq    %rdi, %rax
          subq    %rdi, %rdx
          subq    %rsi, %rax
          cmpq    %rsi, %rdi
          cmovb   %rdx, %rax
          ret

  sub2:
          movq    %rdi, %rax
          subq    %rsi, %rax
          cmpq    %rdi, %rax
          ja      .L13
          rep ret
  .L13:
          movq    %rsi, %rax
          subq    %rdi, %rax
          ret

The two functions have the same behavior. Presumably one implementation is
better than the other, and could be used for both sub1 and sub2.

[Bug target/68110] __builtin_sub_overflow unsigned performance issue

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
value-numbering would need to special-case them via the insertion trick it does
for conversions.  somehow.  not sure if feasible or worthwhile.

[Bug tree-optimization/68110] __builtin_sub_overflow unsigned performance issue

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|target                      |tree-optimization
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-08-21

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The testcase is fixed on rtl level since gcc 6 for x86_64.

For aarch64, it was fixed on the rtl level since GCC 9.

On the gimple level we still have:
  _4 = .SUB_OVERFLOW (a_2(D), b_3(D));
  _1 = IMAGPART_EXPR <_4>;

Maybe a simple match.pd pattern is needed:
(if (TYPE_SIGN (type) == UNSIGNED)
 (simplify
  (imagpart (sub_overflow:s @0 @1))
  (convert (le @0 @1))))

[Bug tree-optimization/68110] __builtin_sub_overflow unsigned performance issue

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #4)
> but since we don't
> have any pass to generate __builtin_sub_overflow from a-b and a<b and don't
> CSE __builtin_sub_overflow with either of those, I am a bit wary of dropping
> the builtin too early.

That changed in GCC 10 IIRC.

[Bug tree-optimization/68110] __builtin_sub_overflow unsigned performance issue

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Mine to finish up later on.