[Bug tree-optimization/64454] New: optimize (x%5)%5

[Bug tree-optimization/64454] New: optimize (x%5)%5

[glisse at gcc dot gnu.org]

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

            Bug ID: 64454
           Summary: optimize (x%5)%5
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org

unsigned f(unsigned x){
  return (x%5)%5;
}

gives:

  _2 = x_1(D) % 5;
  _3 = _2 % 5;
  return _3;

It seems we could easily do better in 2 ways:

1) (x%y)%y could be simplified to x%y in match.pd. This would work even when y
is not a constant.

2) with VRP, depending on the interval for x, we may be able to simplify x%CST
to just x (or sometimes x+CST).

[Bug tree-optimization/64454] optimize (x%5)%5

[glisse at gcc dot gnu.org]

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

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Folding (x%y)<y (with unsigned) would help as well. VRP already handles the
case where y is a constant.

[Bug tree-optimization/64454] optimize (x%5)%5

[jakub at gcc dot gnu.org]

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

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

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

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

Untested fix (for the constant modulo only).

[Bug tree-optimization/64454] optimize (x%5)%5

[glisse at gcc dot gnu.org]

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

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> ---
Thanks, it looks good and it covers the most important case.

Not sure why you are testing "tree_int_cst_sgn (vr->min) >= 0" but it doesn't
hurt. Typo " or signed" -> " for signed" in the first comment.

[Bug tree-optimization/64454] optimize (x%5)%5

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Mon Jan 12 20:44:32 2015
New Revision: 219491

URL: https://gcc.gnu.org/viewcvs?rev=219491&root=gcc&view=rev
Log:
    PR tree-optimization/64454
    * tree-vrp.c (simplify_div_or_mod_using_ranges): Optimize
    op0 % op1 into op0 if op0 is in range [-op1 + 1, op1 - 1]
    for signed or [0, op1 - 1] for unsigned modulo.
    (simplify_stmt_using_ranges): Call simplify_div_or_mod_using_ranges
    even if op1 does not satisfy integer_pow2p.

    * gcc.dg/pr64454.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/pr64454.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c

[Bug tree-optimization/64454] optimize (x%5)%5

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-01-12
     Ever confirmed|0                           |1

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The reason for tree_int_cst_sgn (vr->min) >= 0 was that I don't want to let 0
through and for negative values, handling those would require computing
absolute value, but as match.pd already folds x % -5 already into x % 5, there
is no need to bother with it, so I'm just trying to play safe.

Anyway, keeping this open, as the (x%y)<y case is not handled yet.

[Bug tree-optimization/64454] optimize (x%5)%5

[jakub at gcc dot gnu.org]

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #6)
> (In reply to Jakub Jelinek from comment #5)
> > The reason for tree_int_cst_sgn (vr->min) >= 0 was that I don't want to let
> > 0 through and for negative values, handling those would require computing
> > absolute value, but as match.pd already folds x % -5 already into x % 5,
> > there is no need to bother with it, so I'm just trying to play safe.
> 
> I don't think we are talking about the same thing. Restricting to positive
> op1 is good. What I find a little strange is:
> 
> +      if (TYPE_UNSIGNED (TREE_TYPE (op0))
> +	  || tree_int_cst_sgn (vr->min) >= 0
> +	  || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1), op1),
> +			      vr->min))
> 
> where condition 2: min>=0 is more restrictive than condition 3: min>-op1
> (since op1 is known to be positive) so we could skip condition 2.

Ah, this, I just didn't want to call fold_unary to create GC garbage when I can
cheaply see that it is ok.  If I were to remove something, the TYPE_UNSIGNED
(TREE_TYPE (op0)) check could go (as tree_int_csg_sgn (vr->min) will be then >=
0 always).
>From gcc-bugs-return-472879-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Mon Jan 12 21:20:34 2015
Return-Path: <gcc-bugs-return-472879-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 13770 invoked by alias); 12 Jan 2015 21:20:33 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 13730 invoked by uid 48); 12 Jan 2015 21:20:27 -0000
From: "glisse at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/64454] optimize (x%5)%5
Date: Mon, 12 Jan 2015 21:20:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords: missed-optimization
X-Bugzilla-Severity: normal
X-Bugzilla-Who: glisse at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-64454-4-Dw8wLUKqMw@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-64454-4@http.gcc.gnu.org/bugzilla/>
References: <bug-64454-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-01/txt/msg00873.txt.bz2
Content-length: 314

https://gcc.gnu.org/bugzilla/show_bug.cgi?idd454

--- Comment #8 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #7)
> Ah, this, I just didn't want to call fold_unary to create GC garbage when I
> can cheaply see that it is ok.

Makes sense, thanks for the explanation.

[Bug tree-optimization/64454] optimize (x%5)%5

[glisse at gcc dot gnu.org]

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

--- Comment #9 from Marc Glisse <glisse at gcc dot gnu.org> ---
VRP could still do better:

typedef unsigned short T;
T f(T x, T y){
  // Avoid narrowing in the front-end
  int ix=x;
  int iy=y;
  T z=ix%iy;
  int iz=z;
  return z%iy;
}

ix and iy both have range [0, 65535], but we don't optimize

_9 = _5 & 65535;

because

Visiting statement:
_5 = ix_2 % iy_4;
Found new range for _5: VARYING

Whereas (since the type is unsigned, the signed case is slightly more
complicated but should still be doable) the range for _5 should be the
intersection of [0, 65535] (at most max(ix_2)) and [0, 65534] (at most
max(iy_4)-1).

Even in the constant case, if x has range [0, 3], VRP currently says that x%7
has range [0, 6].

[Bug tree-optimization/64454] optimize (x%5)%5

[glisse at gcc dot gnu.org]

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

--- Comment #10 from Marc Glisse <glisse at gcc dot gnu.org> ---
Author: glisse
Date: Sat May  9 15:40:05 2015
New Revision: 222970

URL: https://gcc.gnu.org/viewcvs?rev=222970&root=gcc&view=rev
Log:
2015-05-09  Marc Glisse  <marc.glisse@inria.fr>

        PR tree-optimization/64454
gcc/
        * tree-vrp.c (extract_range_from_binary_expr_1) <TRUNC_MOD_EXPR>:
        Rewrite.
gcc/testsuite/
        * gcc.dg/tree-ssa/vrp97.c: New file.
        * gcc.dg/vect/slp-perm-7.c: Update.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp97.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/vect/slp-perm-7.c
    trunk/gcc/tree-vrp.c

[Bug tree-optimization/64454] optimize (x%5)%5

[glisse at gcc dot gnu.org]

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

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

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

--- Comment #12 from Marc Glisse <glisse at gcc dot gnu.org> ---
One last thing that would have been nice: in VRP, if the range of X is included
in [10,14], X%5 can be simplified to X-10. But it is probably not worth the
trouble.

[Bug tree-optimization/64454] optimize (x%5)%5

[pinskia at gcc dot gnu.org]

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

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #12)
> One last thing that would have been nice: in VRP, if the range of X is
> included in [10,14], X%5 can be simplified to X-10. But it is probably not
> worth the trouble.

It might also be useful if the range is [0,10] for x%5 to be simplified down to
just "t = x-5; x>=5?t:x;"  And yes this shows up in some places; mainly dealing
with character digit to number conversions.

[Bug tree-optimization/64454] optimize (x%5)%5

[glisse at gcc dot gnu.org]

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

--- Comment #14 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #13)
> It might also be useful if the range is [0,10] for x%5 to be simplified down
> to just "t = x-5; x>=5?t:x;"

(I assume you meant [0,9])
I agree, but the profitability is less obvious with branches/cmov.

> And yes this shows up in some places; mainly
> dealing with character digit to number conversions.

I expect one of the most common cases to be a loop that does x=(x+1)%5; at each
iteration (so x is always in [0,4]), which can be rewritten as if(++x==5)x=0.

Maybe we could open a new PR for those...

[Bug tree-optimization/64454] optimize (x%5)%5

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |6.0