[Bug tree-optimization/95852] New: Failure to optimize __builtin_mul_overflow pattern

[Bug tree-optimization/95852] New: Failure to optimize __builtin_mul_overflow pattern

[gabravier at gmail dot com]

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

            Bug ID: 95852
           Summary: Failure to optimize __builtin_mul_overflow pattern
           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(unsigned x, unsigned y, unsigned* res)
{
    *res = x * y;
    return x && ((*res / x) != y);
}

This can be optimized to `return __builtin_mul_overflow(x, y, res);`. This
transformation is done by LLVM, but not by GCC.

[Bug tree-optimization/95852] Failure to optimize __builtin_mul_overflow pattern

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-01-07
     Ever confirmed|0                           |1
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED

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

Untested WIP patch.  This handles the transformation to mullo but doesn't yet
optimize away the x != 0 && (which can be done of course only if the x != 0
guarded basic block contains only specific statements we'd need to pattern
recognize.
Furthermore, signed multiplication can be handled similarly, but it will need
even more work because of the casts.

[Bug tree-optimization/95852] Failure to optimize __builtin_mul_overflow pattern

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #49913|0                           |1
        is obsolete|                            |

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

Full untested patch (so far only for unsigned __builtin_mul_overflow{,_p}
pattern matching though).  Signed will be handled incrementally.

[Bug tree-optimization/95852] Failure to optimize __builtin_mul_overflow pattern

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 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:a2106317cd6673e110b347c70f21e25fbb23379e

commit r11-6579-ga2106317cd6673e110b347c70f21e25fbb23379e
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Jan 11 10:32:07 2021 +0100

    widening_mul: Pattern recognize unsigned multiplication with overflow check
[PR95852]

    The following patch pattern recognizes some forms of multiplication
followed
    by overflow check through division by one of the operands compared to the
    other one, with optional removal of guarding non-zero check for that
operand
    if possible.  The patterns are replaced with effectively
    __builtin_mul_overflow or __builtin_mul_overflow_p.  The testcases cover 64
    different forms of that.

    2021-01-11  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/95852
            * tree-ssa-math-opts.c (maybe_optimize_guarding_check): New
function.
            (uaddsub_overflow_check_p): Renamed to ...
            (arith_overflow_check_p): ... this.  Handle also multiplication
            with overflow check.
            (match_uaddsub_overflow): Renamed to ...
            (match_arith_overflow): ... this.  Add cfg_changed argument. 
Handle
            also multiplication with overflow check.  Adjust function comment.
            (math_opts_dom_walker::after_dom_children): Adjust callers.  Call
            match_arith_overflow also for MULT_EXPR.

            * gcc.target/i386/pr95852-1.c: New test.
            * gcc.target/i386/pr95852-2.c: New test.

[Bug tree-optimization/95852] Failure to optimize __builtin_mul_overflow pattern

[cvs-commit at gcc dot gnu.org]

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

--- 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:9febe9e4be7812519258ea3ed4f38bbc1a61624b

commit r11-6580-g9febe9e4be7812519258ea3ed4f38bbc1a61624b
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Jan 11 10:34:07 2021 +0100

    widening_mul: Pattern recognize also signed multiplication with overflow
check [PR95852]

    On top of the previous widening_mul patch, this one recognizes also
    (non-perfect) signed multiplication with overflow, like:
    int
    f5 (int x, int y, int *res)
    {
      *res = (unsigned) x * y;
      return x && (*res / x) != y;
    }
    The problem with such checks is that they invoke UB if x is -1 and
    y is INT_MIN during the division, but perhaps the code knows that
    those values won't appear.  As that case is UB, we can do for that
    case whatever we want and handling that case as signed overflow
    is the best option.  If x is a constant not equal to -1, then the checks
    are 100% correct though.
    Haven't tried to pattern match bullet-proof checks, because I really don't
    know if users would write it in real-world code like that,
    perhaps
      *res = (unsigned) x * y;
      return x && (x == -1 ? (*res / y) != x : (*res / x) != y);
    ?

   
https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow
    suggests to use twice as wide multiplication (perhaps we should handle that
    too, for both signed and unsigned), or some very large code
    with 4 different divisions nested in many conditionals, no way one can
    match all the possible variants thereof.

    2021-01-11  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/95852
            * tree-ssa-math-opts.c (maybe_optimize_guarding_check): Change
            mul_stmts parameter type to vec<gimple *> &.  Before cond_stmt
            allow in the bb any of the stmts in that vector, div_stmt and
            up to 3 cast stmts.
            (arith_cast_equal_p): New function.
            (arith_overflow_check_p): Add cast_stmt argument, handle signed
            multiply overflow checks.
            (match_arith_overflow): Adjust caller.  Handle signed multiply
            overflow checks.

            * gcc.target/i386/pr95852-3.c: New test.
            * gcc.target/i386/pr95852-4.c: New test.

[Bug tree-optimization/95852] Failure to optimize __builtin_mul_overflow pattern

[jakub at gcc dot gnu.org]

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

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

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

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