[Bug rtl-optimization/99620] New: Subtract with borrow (SBB) missed optimization

[Bug rtl-optimization/99620] New: Subtract with borrow (SBB) missed optimization

[chfast at gmail dot com]

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

            Bug ID: 99620
           Summary: Subtract with borrow (SBB) missed optimization
           Product: gcc
           Version: 10.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: chfast at gmail dot com
  Target Milestone: ---

Hi.

For the 128-bit precision subtraction: SUB + SBB the optimization depends on
the how the carry bit condition is specified in the code. In the first case
below everything works nicely, but in the second we have unnecessary CMP in the
final code.

I believe the second carry bit condition is simpler (does not require unsigned
integer wrapping behavior) and does not have dependency on the first
subtraction. 


using u64 = unsigned long;

struct u128
{
    u64 l;
    u64 h;
};

auto sub_good(u128 a, u128 b)
{
    auto l = a.l - b.l;
    auto k = l > a.l;
    auto h = a.h - b.h - k;
    return u128{l, h};
}

auto sub_bad(u128 a, u128 b)
{
    auto l = a.l - b.l;
    auto k = a.l < b.l;
    auto h = a.h - b.h - k;
    return u128{l, h};
}


sub_good(u128, u128):
        mov     rax, rdi
        sub     rax, rdx
        sbb     rsi, rcx
        mov     rdx, rsi
        ret
sub_bad(u128, u128):
        cmp     rdi, rdx
        mov     rax, rdi
        sbb     rsi, rcx
        sub     rax, rdx
        mov     rdx, rsi
        ret


If you think this is easy to fix, I would like to give it a try if I could get
some pointers where to start.

[Bug target/99620] Subtract with borrow (SBB) missed optimization

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|rtl-optimization            |target
           Keywords|                            |missed-optimization
           Severity|normal                      |enhancement

[Bug target/99620] Subtract with borrow (SBB) missed optimization

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |x86_64-linux-gnu

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This works on aarch64:
_Z8sub_good4u128S_:
.LFB0:
        .cfi_startproc
        subs    x0, x0, x2
        sbc     x1, x1, x3
        ret
.....
_Z7sub_bad4u128S_:
.LFB1:
        .cfi_startproc
        subs    x0, x0, x2
        sbc     x1, x1, x3
        ret

[Bug target/99620] Subtract with borrow (SBB) missed optimization

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
      Known to fail|                            |11.0
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-03-17

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  For sub_good we detect .SUB_OVERFLOW while for sub_bad we do not.

[Bug target/99620] Subtract with borrow (SBB) missed optimization

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Yeah.  If you write it explicitly as:
auto sub_good(u128 a, u128 b)
{
    u64 l;
    bool k = __builtin_sub_overflow (a.l, b.l, &l);
    auto h = a.h - b.h - k;
    return u128{l, h};
}
it will be optimized too.

[Bug target/99620] Subtract with borrow (SBB) missed optimization

[chfast at gmail dot com]

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

--- Comment #4 from Paweł Bylica <chfast at gmail dot com> ---
Can you give me introduction where and how to fix it? I have a longer list of
similar issues, so maybe it's good time to learn how to fix them myself.

FYI, clang is unifying both cases by changing `k = l > a.l` into `k = a.l <
b.l` and only having SUB_OVERFLOW match for `k = a.l < b.l` case.

[Bug tree-optimization/99620] Subtract with borrow (SBB) missed optimization

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
  l_7 = a$l_12 - _1;
  k_8 = l_7 > a$l_12;

vs:

  l_6 = a$l_11 - b$l_12;
  k_7 = a$l_11 < b$l_12;