[Bug tree-optimization/95862] New: Failure to optimize usage of __builtin_mul_overflow to small __int128-based check

[Bug tree-optimization/95862] New: Failure to optimize usage of __builtin_mul_overflow to small __int128-based check

[gabravier at gmail dot com]

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

            Bug ID: 95862
           Summary: Failure to optimize usage of __builtin_mul_overflow to
                    small __int128-based check
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

bool f(int32_t a, int32_t b)
{
    uint64_t r;
    return __builtin_mul_overflow (a, b, &r);
}

This can be optimized to `return ((__uint128_t)(a * (__int128_t)b) >> 64) & 1;`
(idk if this might invoke UB, but rn at least it generates much better code on
x86 than what GCC currently generates for the example I gave). This
transformation is done by LLVM, but not by GCC.

[Bug tree-optimization/95862] Failure to optimize usage of __builtin_mul_overflow to small __int128-based check

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Are you specifically talking about the case where r is unused afterwards, aka
about return __builtin_mul_overflow_p (a, b, (uint64_t) 0); ?
In that case, the overflow is only if a and b have different signs, aka.
(a ^ b) < 0.

[Bug rtl-optimization/95862] Failure to optimize usage of __builtin_mul_overflow to small __int128-based check

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|tree-optimization           |rtl-optimization
   Last reconfirmed|                            |2020-11-24
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I don't really see why it woiuld need to do the 128-bit multiplication at all,
it can just do ((int64_t) a * b) < 0 (aka ((uint64_t) a * b) >> 63).

[Bug rtl-optimization/95862] Failure to optimize usage of __builtin_mul_overflow to small __int128-based check

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 49618
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49618&action=edit
gcc11-pr95862.patch

Untested fix.

[Bug rtl-optimization/95862] Failure to optimize usage of __builtin_mul_overflow to small __int128-based check

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 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:049ce9d233e2d865dc81a5042b1c28ee21d1c9d8

commit r11-5366-g049ce9d233e2d865dc81a5042b1c28ee21d1c9d8
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Nov 25 15:42:38 2020 +0100

    middle-end: __builtin_mul_overflow expansion improvements [PR95862]

    The following patch adds some improvements for __builtin_mul_overflow
    expansion.
    One optimization is for the u1 * u2 -> sr case, as documented we normally
    do:
         u1 * u2 -> sr
            res = (S) (u1 * u2)
            ovf = res < 0 || main_ovf (true)
    where main_ovf (true) stands for jump on unsigned multiplication overflow.
    If we know that the most significant bits of both operands are clear (such
    as when they are zero extended from something smaller), we can
    emit better coe by handling it like s1 * s2 -> sr, i.e. just jump on
    overflow after signed multiplication.

    Another two cases are s1 * s2 -> ur or s1 * u2 -> ur, if we know the
minimum
    precision needed to encode all values of both arguments summed together
    is smaller or equal to destination precision (such as when the two
arguments
    are sign (or zero) extended from half precision types, we know the
overflows
    happen only iff one argument is negative and the other argument is positive
    (not zero), because even if both have maximum possible values, the maximum
    is still representable (e.g. for char * char -> unsigned short
    0x7f * 0x7f = 0x3f01 and for char * unsigned char -> unsigned short
    0x7f * 0xffU = 0x7e81) and as the result is unsigned, all negative results
    do overflow, but are also representable if we consider the result signed
    - all of them have the MSB set.  So, it is more efficient to just
    do the normal multiplication in that case and compare the result considered
    as signed value against 0, if it is smaller, overflow happened.

    And the get_min_precision change is to improve the char to short handling,
    we have there in the IL
      _2 = (int) arg_1(D);
    promotion from C promotions from char or unsigned char arg, and the caller
    adds a NOP_EXPR cast to short or unsigned short.  get_min_precision punts
    on the narrowing cast though, it handled only widening casts, but we can
    handle narrowing casts fine too, by recursing on the narrowing cast
operands
    and using it only if it has in the end smaller minimal precision, which
    would duplicate the sign bits (or zero bits) to both the bits above the
    narrowing conversion and also at least one below that.

    2020-10-25  Jakub Jelinek  <jakub@redhat.com>

            PR rtl-optimization/95862
            * internal-fn.c (get_min_precision): For narrowing conversion,
recurse
            on the operand and if the operand precision is smaller than the
            current one, return that smaller precision.
            (expand_mul_overflow): For s1 * u2 -> ur and s1 * s2 -> ur cases
            if the sum of minimum precisions of both operands is smaller or
equal
            to the result precision, just perform normal multiplication and
            set overflow to the sign bit of the multiplication result.  For
            u1 * u2 -> sr if both arguments have the MSB known zero, use
            normal s1 * s2 -> sr expansion.

            * gcc.dg/builtin-artih-overflow-5.c: New test.

[Bug rtl-optimization/95862] Failure to optimize usage of __builtin_mul_overflow to small __int128-based check

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed on the trunk.

[Bug rtl-optimization/95862] Failure to optimize usage of __builtin_mul_overflow to small __int128-based check

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 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:b13dacdfb315675803982ad5a3098f7b55e6357a

commit r11-5369-gb13dacdfb315675803982ad5a3098f7b55e6357a
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Nov 25 17:25:36 2020 +0100

    testsuite: Rename test to avoid typo in its name [PR95862]

    2020-11-25  Jakub Jelinek  <jakub@redhat.com>

            PR rtl-optimization/95862
            * gcc.dg/builtin-artih-overflow-5.c: Renamed to ...
            * gcc.dg/builtin-arith-overflow-5.c: ... this.