[Bug tree-optimization/64130] New: vrp: handle non zero constant divided by range cannot be zero.

[Bug tree-optimization/64130] New: vrp: handle non zero constant divided by range cannot be zero.

[andi-gcc at firstfloor dot org]

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

            Bug ID: 64130
           Summary: vrp: handle non zero constant divided by range cannot
                    be zero.
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: andi-gcc at firstfloor dot org

The following two functions should always be optimized to return 0
because x > 0, x / a cannot be 0. But VRP misses this case for unknown 
reasons, even though it has some code for it in ranges_from_anti_range()

int fsigned(int a)
{
        return 100 / a == 0;
}

int funsigned(unsigned a)
{
        return 100 / a == 0;
}

gcc50 -fno-non-call-exceptions -O2 -S tvrpdiv.c

gcc version 5.0.0 20141111 (experimental) (GCC) 

        movl    $100, %eax
        cltd
        idivl   %edi
        testl   %eax, %eax
        sete    %al
        movzbl  %al, %eax
        ret

        xorl    %edx, %edx
        movl    $100, %eax
        divl    %edi
        testl   %eax, %eax
        sete    %al
        movzbl  %al, %eax

[Bug tree-optimization/64130] vrp: handle non zero constant divided by range cannot be zero.

[glisse at gcc dot gnu.org]

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

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Uh? 100/1000==0, I don't understand your point.

[Bug tree-optimization/64130] vrp: handle non zero constant divided by range cannot be zero.

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So this should be optimized to a > 100 instead.

[Bug tree-optimization/64130] vrp: handle non zero constant divided by range cannot be zero.

[andi-gcc at firstfloor dot org]

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

--- Comment #3 from Andi Kleen <andi-gcc at firstfloor dot org> ---
You're right. I actually meant

x >= maxval(typeof(a)), x / a   cannot be 0.

Corrected test case (assuming 64bit target):

#include <limits.h>

int fsigned(int a)
{
        return 0x1fffffffL / a == 0;
}

int funsigned(unsigned a)
{
        return 0x1fffffffL / a == 0;
}

>So this should be optimized to a > 100 instead.

Yes this would make sense too.

[Bug tree-optimization/64130] vrp: handle non zero constant divided by range cannot be zero.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-12-01
     Ever confirmed|0                           |1

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andi Kleen from comment #3)
> You're right. I actually meant
> 
> x >= maxval(typeof(a)), x / a   cannot be 0.
> 
> Corrected test case (assuming 64bit target):
> 
> #include <limits.h>
> 
> int fsigned(int a)
> {
>         return 0x1fffffffL / a == 0;
> }

0x1fffffffL / 0x20000000 == 0

Maybe you meant 0x1fffffffffffffffL / a == 0?

> int funsigned(unsigned a)
> {
>         return 0x1fffffffL / a == 0;
> }
> 
> >So this should be optimized to a > 100 instead.
> 
> Yes this would make sense too.

Yes.

[Bug tree-optimization/64130] vrp: handle non zero constant divided by range cannot be zero.

[kugan at gcc dot gnu.org]

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

kugan at gcc dot gnu.org changed:

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

--- Comment #5 from kugan at gcc dot gnu.org ---
I think it should be in from front-end? 

Tried fixing it in VRP like:

--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -9943,12 +9943,43 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
     {
       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
       tree rhs1 = gimple_assign_rhs1 (stmt);
+      tree rhs2 = gimple_assign_rhs2 (stmt);

       switch (rhs_code)
        {
        case EQ_EXPR:
        case NE_EXPR:
-          /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
+
+         /* PR64130.  If there is a statement (integer_cst / var == 0) and
+            integer_cst >= TYPE_MAX (TREE_TYPE (var))
+            then (integer_cst / var) cannot be 0. Hence this condition will
+            be always false.  */
+         if (rhs_code == EQ_EXPR
+             && TREE_CODE (rhs1) == SSA_NAME
+             && integer_zerop (rhs2))
+           {
+             gimple g = SSA_NAME_DEF_STMT (rhs1);
+
+             if (is_gimple_assign (g)
+                 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (g)))
+                 && TREE_CODE (gimple_assign_rhs1 (g)) == INTEGER_CST
+                 && TREE_CODE (gimple_assign_rhs2 (g)) == SSA_NAME
+                 && gimple_assign_rhs_code (g) == TRUNC_DIV_EXPR)
+               {
+                 tree r1 = gimple_assign_rhs1 (g);
+                 tree r2 = gimple_assign_rhs2 (g);
+                 tree max = TYPE_MAX_VALUE (TREE_TYPE (r2));
+                 if (compare_values (r1, max) == -1
+                     || compare_values (r1, max) == 0)
+                   {
+                     gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, rhs2);
+                     update_stmt (stmt);
+                     return true;
+                   }
+               }
+           }
+
+         /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
             if the RHS is zero or one, and the LHS are known to be boolean
             values.  */
          if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))


But by the time we are in VRP, variable "a" is already promoted to that fits
the constant.

[Bug tree-optimization/64130] vrp: handle non zero constant divided by range cannot be zero.

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #6)
> (In reply to kugan from comment #5)
> > I think it should be in from front-end? 
> 
> ?

Yes this is really not a good comment to make.  This is not even front-end
specific optimization and can happen in Fortran, Ada, etc.
Basically when a > 100, 100/a is 0 so 100/a == 0 is the same as a > 100.

[Bug tree-optimization/64130] vrp: handle non zero constant divided by range cannot be zero.

[glisse at gcc dot gnu.org]

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

--- Comment #9 from Marc Glisse <glisse at gcc dot gnu.org> ---
Forget comment #8, it can introduce abs(INT_MIN) which would be bad.

[Bug tree-optimization/64130] vrp: handle non zero constant divided by range cannot be zero.

[kugan at gcc dot gnu.org]

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

--- Comment #10 from kugan at gcc dot gnu.org ---
(In reply to Marc Glisse from comment #6)
> (In reply to kugan from comment #5)
> > I think it should be in from front-end? 
> 
> ?

Sorry for the confusing terminology.

for the case
int fsigned(int a)
{
  return 0xffffffffffffffL / a == 0;
}

004t.gimple has:

  int D.4228;
  long long int D.4229;
  long long int D.4230;
  _Bool D.4231;

  D.4229 = (long long int) a;
  D.4230 = 72057594037927935 / D.4229;
  D.4231 = D.4230 == 0;


So based on the "x >= maxval(typeof(a)), x / a   cannot be 0" the
maxval(typeof(a)) is now maxval(long long int) in the case of ARM. Thats why I
was asking if it is to be done before gimple is generated. As I see, the above
statement does not rely on value ranges.


> 
> > Tried fixing it in VRP like:
> 
> You don't seem to use ranges at all. This might be the right place to
> implement the suggestion from comment #2 (though if it does not use ranges,
> match.pd would be better), but for the original optimization, what you want
> to improve is the computation of the range of a division. When a has range
> [0, 4294967295] we compute for 2305843009213693951 / a the range [0,
> 2305843009213693951] which is not optimal, the left bound should be
> 536870912 not 0. If the good interval is computed, VRP will automatically
> fold == 0 to false without extra code. We already get this right when a has
> range [1, 4294967295].

How about something like this:

--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -3158,7 +3158,14 @@ extract_range_from_binary_expr_1 (value_range_t *vr,
                type = VR_VARYING;
              cmp = compare_values (vr0.min, zero);
              if (cmp == 1)
-               min = zero;
+               {
+                 if (vr1.type == VR_RANGE
+                     && !symbolic_range_p (&vr0)
+                     && !symbolic_range_p (&vr1))
+                   min = int_const_binop (code, vr0.min, vr1.max);
+                 else
+                   min = zero;
+               }
              else if (cmp == 0 || cmp == -1)
                min = vr0.min;
              else

[Bug tree-optimization/64130] vrp: handle non zero constant divided by range cannot be zero.

[kugan at gcc dot gnu.org]

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

--- Comment #11 from kugan at gcc dot gnu.org ---
Author: kugan
Date: Mon Jun 29 00:15:41 2015
New Revision: 225108

URL: https://gcc.gnu.org/viewcvs?rev=225108&root=gcc&view=rev
Log:
gcc/ChangeLog:

2015-06-29  Kugan Vivekanandarajah  <kuganv@linaro.org>

        PR middle-end/64130
        * tree-vrp.c (extract_range_from_binary_expr_1): For unsigned
        division, compute max and min when value ranges for dividend and
        divisor are available.


gcc/testsuite/ChangeLog:

2015-06-29  Kugan Vivekanandarajah  <kuganv@linaro.org>

        PR middle-end/64130
        * gcc.dg/tree-ssa/pr64130.c: New test.


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

[Bug tree-optimization/64130] vrp: handle non zero constant divided by range cannot be zero.

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk.