[Bug tree-optimization/31522] New: [4.3 Regression] False overflow warning with division

[Bug tree-optimization/31522] New: [4.3 Regression] False overflow warning with division

[pinskia at gcc dot gnu dot org]

Compile this with -O2 -W -Wall and you should not get a warning but you get an
overflow warning which is a false positive as this condition can never be false
even with overflow (as shown by doing -Dint=unsigned):
int bar(int);

int f(int x)
{
  int y;
  if (x<=4)  y = 1;
  else y = x/4;
  return y <=  0;
}

---------------- CUT -------------------
t.c: In function 'f':
t.c:8: warning: assuming signed overflow does not occur when simplifying
conditional to constant

How can x/4 cause an overflow when x>4 and never negative?

Also when I do -Dint=unsigned or even -fwrapv, VRP still is able to say y is
always greater than 0.


-- 
           Summary: [4.3 Regression] False overflow warning with division
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: diagnostic
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] [4.3 Regression] False overflow warning with division

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2007-04-10 08:28 -------
Also now I think this is a 4.2 regression but I don't have 4.2 checked out on
this machine so I cannot check.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.3.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] [4.3 Regression] False overflow warning with division

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2007-04-10 08:30 -------
Note this was found while looking into PR 31521.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] [4.3 Regression] False overflow warning with division phi nodes

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2007-04-10 08:56 -------
IR after assert insertion (plus annotate with ranges found):
f (x)
{
  int y;
  int D.1599;

<bb 2>:
  if (x_2(D) <= 4) goto <L2>; else goto <L1>;

<L1>:;
  x_7 = ASSERT_EXPR <x_2(D), x_2(D) > 4>; // x_7: [5, +INF] 
  y_4 = x_7 / 4; // y_4: [1, 536870911]

  # y_1 = PHI <1(2), y_4(3)> // y_1: [1, +INF(OVF)]
<L2>:;
  D.1599_5 = y_1 <= 0;
  return D.1599_5;

}


Can someone explain how we go from the union of [1,1] and [1, 536870911]  to
get an inf with an overflow?

Here is another example but this time without a division and just plain obvious
no overflow as everything are just compares:
int f(int x)
{
  int y;
  if (x>536870911) y =1;
  else {
  if (x<0)  x = 1;
  y = x <=  0;
  }
  return y > 2;
}


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |blocker
            Summary|[4.3 Regression] False      |[4.3 Regression] False
                   |overflow warning with       |overflow warning with
                   |division                    |division phi nodes


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] [4.3 Regression] False overflow warning with phi nodes

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2007-04-10 13:39 -------
I don't see the warning, but the range with overflow is derived from
vrp_visit_phi_node where we fall back to +INF(OVF) from [1, 536870911] because

  /* To prevent infinite iterations in the algorithm, derive ranges
     when the new value is slightly bigger or smaller than the
     previous one.  */ 

but why exactly do we care bout overflow infinities there at all (apart from
if the new max/min are overflowed)?  Instead we throw away overflowed (and
not overflowed) infinites dropping to VARYING.  Strange....

(of course the whole block preventing inifinite iterations is pessimizing
some cases which is why I introduced all_const -- we might use
all_or_all_but_one_const here ;))


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-04-10 13:39:22
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] False overflow warning with phi nodes

[pinskia at gcc dot gnu dot org]

------- Comment #5 from pinskia at gcc dot gnu dot org  2007-04-11 06:34 -------
It turns out you have to add -Wstrict-overflow to get the warning but this is
still a false warning.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|blocker                     |normal
            Summary|[4.3 Regression] False      |False overflow warning with
                   |overflow warning with phi   |phi nodes
                   |nodes                       |
   Target Milestone|4.3.0                       |---


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] False overflow warning with phi nodes

[ian at airs dot com]

------- Comment #6 from ian at airs dot com  2007-04-11 07:15 -------
When we pick a new range to avoid an infinite iteration, we have to pick an
overflow range.  This is what catches overflows like
    for (i = 1; i > 0; ++i) ++bits;

I've experimented with only doing this in a loop, but it didn't work reliably.

Note that we don't throw away all infinities here, we just throw away
[-INF,+INF].  This is code from before the overflow checks were added.

The suggestion of all_but_one_const sounds reasonable to me.  What do you think
of this patch?

Index: tree-vrp.c
===================================================================
--- tree-vrp.c  (revision 123521)
+++ tree-vrp.c  (working copy)
@@ -5059,7 +5059,7 @@ vrp_visit_phi_node (tree phi)
   tree lhs = PHI_RESULT (phi);
   value_range_t *lhs_vr = get_value_range (lhs);
   value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
-  bool all_const = true;
+  int variable_count;

   copy_value_range (&vr_result, lhs_vr);

@@ -5069,6 +5069,7 @@ vrp_visit_phi_node (tree phi)
       print_generic_expr (dump_file, phi, dump_flags);
     }

+  variable_count = 0;
   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
     {
       edge e = PHI_ARG_EDGE (phi, i);
@@ -5089,7 +5090,7 @@ vrp_visit_phi_node (tree phi)
          if (TREE_CODE (arg) == SSA_NAME)
            {
              vr_arg = *(get_value_range (arg));
-             all_const = false;
+             ++variable_count;
            }
          else
            {
@@ -5122,7 +5123,7 @@ vrp_visit_phi_node (tree phi)
      when the new value is slightly bigger or smaller than the
      previous one.  */
   if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE
-      && !all_const)
+      && variable_count > 1)
     {
       if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
        {


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] False overflow warning with phi nodes

[pinskia at gcc dot gnu dot org]

------- Comment #7 from pinskia at gcc dot gnu dot org  2007-04-11 07:38 -------
> What do you think of this patch?
This patch makes cc1 go into an infinite loop for the following code (which you
semi already said why you needed the phi merge to do this):
int f(void)
{
  int i, bits = 0;
   for (i = 1; i > 0; ++i) ++bits;
  if (i > 0)  return 1;
  return bits;
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] False overflow warning with phi nodes

[ian at airs dot com]

------- Comment #8 from ian at airs dot com  2007-04-11 08:04 -------
That's not an infinite loop, it's just a loop with 2^31 iterations.

This patch takes a rather different approach.

Index: tree-vrp.c
===================================================================
--- tree-vrp.c  (revision 123521)
+++ tree-vrp.c  (working copy)
@@ -95,6 +95,11 @@ static sbitmap blocks_visited;
    of values that SSA name N_I may take.  */
 static value_range_t **vr_value;

+/* For a PHI node which sets SSA name N_I, VR_COUNTS[I] holds the
+   number of executable edges we saw the last time we visited the
+   node.  */
+static int *vr_counts;
+

 /* Return whether TYPE should use an overflow infinity distinct from
    TYPE_{MIN,MAX}_VALUE.  We use an overflow infinity value to
@@ -4306,6 +4311,7 @@ vrp_initialize (void)
   basic_block bb;

   vr_value = XCNEWVEC (value_range_t *, num_ssa_names);
+  vr_counts = XCNEWVEC (int, num_ssa_names);

   FOR_EACH_BB (bb)
     {
@@ -5059,7 +5065,7 @@ vrp_visit_phi_node (tree phi)
   tree lhs = PHI_RESULT (phi);
   value_range_t *lhs_vr = get_value_range (lhs);
   value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
-  bool all_const = true;
+  int edges, old_edges;

   copy_value_range (&vr_result, lhs_vr);

@@ -5069,6 +5075,7 @@ vrp_visit_phi_node (tree phi)
       print_generic_expr (dump_file, phi, dump_flags);
     }

+  edges = 0;
   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
     {
       edge e = PHI_ARG_EDGE (phi, i);
@@ -5086,10 +5093,11 @@ vrp_visit_phi_node (tree phi)
          tree arg = PHI_ARG_DEF (phi, i);
          value_range_t vr_arg;

+         ++edges;
+
          if (TREE_CODE (arg) == SSA_NAME)
            {
              vr_arg = *(get_value_range (arg));
-             all_const = false;
            }
          else
            {
@@ -5115,6 +5123,9 @@ vrp_visit_phi_node (tree phi)
        }
     }

+  old_edges = vr_counts[SSA_NAME_VERSION (lhs)];
+  vr_counts[SSA_NAME_VERSION (lhs)] = edges;
+
   if (vr_result.type == VR_VARYING)
     goto varying;

@@ -5122,7 +5133,7 @@ vrp_visit_phi_node (tree phi)
      when the new value is slightly bigger or smaller than the
      previous one.  */
   if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE
-      && !all_const)
+      && edges <= old_edges)
     {
       if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
        {


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] False overflow warning with phi nodes

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2007-04-11 09:14 -------
That looks reasonable.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] False overflow warning with phi nodes

[ian at gcc dot gnu dot org]

------- Comment #10 from ian at gcc dot gnu dot org  2007-04-17 06:33 -------
Subject: Bug 31522

Author: ian
Date: Tue Apr 17 06:33:38 2007
New Revision: 123908

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=123908
Log:
./:
        PR tree-optimization/31522
        * tree-vrp.c (vr_phi_edge_counts): New static variable.
        (vrp_initialize): Allocate vr_phi_edge_counts.
        (vrp_visit_phi_node): Don't push to infinity if we saw a new
        executable edge.  Drop test for all constants.
        (vrp_finalize): Free vrp_phi_edge_counts.
testsuite/:
        PR tree-optimization/31522
        * gcc.dg/Wstrict-overflow-16.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/Wstrict-overflow-16.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522

[Bug tree-optimization/31522] False overflow warning with phi nodes

[ian at airs dot com]

------- Comment #11 from ian at airs dot com  2007-04-17 19:08 -------
Fixed on mainline.


-- 

ian at airs dot com changed:

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


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31522