[Bug tree-optimization/95433] New: Failure to completely optimize simple compare after operations

[Bug tree-optimization/95433] New: Failure to completely optimize simple compare after operations

[gabravier at gmail dot com]

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

            Bug ID: 95433
           Summary: Failure to completely optimize simple compare after
                    operations
           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: ---

auto f(int x)
{
    return (2 * x) + 5 == 3;
}

This can be optimized to `x == -1`. This transformation is done by LLVM, but
not by GCC.

[Bug tree-optimization/95433] Failure to completely optimize simple compare after operations

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2020-05-30

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
It is 2*x==-2 that we fail to simplify. match.pd has code for x*2==y*2 or
x*2==0 or even x*2.==-2. for floats, but apparently not for the special case of
other constants for integers.

[Bug tree-optimization/95433] Failure to completely optimize simple compare after operations

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hmm, are we supposed to solve/simplify arbitrary linear equations?

3 * x * x * x + 5 == 8

is equal to x == 1.

3 * x * x + 5 == 8

is equal to abs(x) == 1.

But sure, simple cases.  I wonder if something more "general" can be done
by reassoc rather than dealing with this in pattern matching.

[Bug tree-optimization/95433] Failure to completely optimize simple compare after operations

[joseph at codesourcery dot com]

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

--- Comment #3 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
This is of course only valid because signed overflow is undefined; it 
wouldn't be a valid optimization with -fwrapv (unless x were narrower than 
int so no overflow could occur).

[Bug tree-optimization/95433] Failure to completely optimize simple compare after operations

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

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

--- Comment #4 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> Hmm, are we supposed to solve/simplify arbitrary linear equations?
> 
> 3 * x * x * x + 5 == 8
> 
> is equal to x == 1.
> 
> 3 * x * x + 5 == 8
> 
> is equal to abs(x) == 1.

Solving linear equations is at least tractable, which is not the case of
general polynomial equations, especially if the degree is greater than 4. ;-)

[Bug tree-optimization/95433] Failure to completely optimize simple compare after operations

[glisse at gcc dot gnu.org]

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

--- Comment #5 from Marc Glisse <glisse at gcc dot gnu.org> ---
Patch posted at
https://gcc.gnu.org/pipermail/gcc-patches/2020-August/551154.html for the
original testcase.

Note that solving univariate polynomial equations *in the integers* (the
rationals are not much harder) is actually rather simple, just enumerate the
divisors of the constant term and evaluate the polynomial on each of them to
check which ones are roots. If someone wants to implement that...

[Bug tree-optimization/95433] Failure to completely optimize simple compare after operations

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Marc Glisse <glisse@gcc.gnu.org>:

https://gcc.gnu.org/g:ca2b8c082c4f16919071c9f8de8db0b33b54c405

commit r11-2550-gca2b8c082c4f16919071c9f8de8db0b33b54c405
Author: Marc Glisse <marc.glisse@inria.fr>
Date:   Tue Aug 4 17:30:16 2020 +0200

    Simplify X * C1 == C2 with undefined overflow

    this transformation is quite straightforward, without overflow, 3*X==15 is
    the same as X==5 and 3*X==5 cannot happen. Adding a single_use restriction
    for the first case didn't seem necessary, although of course it can
    slightly increase register pressure in some cases.

    2020-08-04  Marc Glisse  <marc.glisse@inria.fr>

            PR tree-optimization/95433
            * match.pd (X * C1 == C2): New transformation.

            * gcc.c-torture/execute/pr23135.c: Add -fwrapv to avoid
            undefined behavior.
            * gcc.dg/tree-ssa/pr95433.c: New file.

[Bug tree-optimization/95433] Failure to completely optimize simple compare after operations

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Marc Glisse <glisse@gcc.gnu.org>:

https://gcc.gnu.org/g:287522613d661b4c5ba8403b051eb470c1674cba

commit r11-2629-g287522613d661b4c5ba8403b051eb470c1674cba
Author: Marc Glisse <marc.glisse@inria.fr>
Date:   Mon Aug 10 12:50:42 2020 +0200

    Simplify X * C1 == C2 with wrapping overflow

    Odd numbers are invertible in Z / 2^n Z, so X * C1 == C2 can be rewritten
    as X == C2 * inv(C1) when overflow wraps.

    mod_inv should probably be updated to better match the other wide_int
    functions, but that's a separate issue.

    2020-08-10  Marc Glisse  <marc.glisse@inria.fr>

            PR tree-optimization/95433
            * match.pd (X * C1 == C2): Handle wrapping overflow.
            * expr.c (maybe_optimize_mod_cmp): Qualify call to mod_inv.
            (mod_inv): Move...
            * wide-int.cc (mod_inv): ... here.
            * wide-int.h (mod_inv): Declare it.

            * gcc.dg/tree-ssa/pr95433-2.c: New file.

[Bug tree-optimization/95433] Failure to completely optimize simple compare after operations

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
   Target Milestone|---                         |11.0
             Status|NEW                         |RESOLVED

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed in GCC 11 by the commits.