[Bug tree-optimization/31130] New: [4.3 Regression] VRP no longer derives range for division after negation

[Bug tree-optimization/31130] New: [4.3 Regression] VRP no longer derives range for division after negation

[rguenth at gcc dot gnu dot org]

extern void link_error ();
void foo (int a)
{
  if (a < 0)
    {
      int y;
      a = -a;
      y  = a / 7;
      if (y > 1 << 30)
        link_error ();
    }
}

int main()
{
  return 0;
}

Before the VRP overflow handling changes we have after the first VRP pass:

Value ranges after VRP:

a_1(D): VARYING
a_2: [1, +INF]  EQUIVALENCES: { } (0 elements)
y_3: [0, 306783378]  EQUIVALENCES: { } (0 elements)
a_4: [-INF, -1]  EQUIVALENCES: { a_1(D) } (1 elements)

Substituing values and folding statements

Folding predicate y_3 > 1073741824 to 0
Folded statement: if (y_3 > 1073741824) goto <L1>; else goto <L2>;
            into: if (0) goto <L1>; else goto <L2>;

void foo(int) (a)
{
  int y;

<bb 2>:
  if (a_1(D) < 0) goto <L0>; else goto <L2>;

<L0>:;
  a_2 = -a_1(D);
  y_3 = a_2 / 7;

<L2>:;
  return;

}


while now we get

Value ranges after VRP:

a_1(D): VARYING
a_2: [1, +INF(OVF)]  EQUIVALENCES: { } (0 elements)
y_3: [0, +INF(OVF)]  EQUIVALENCES: { } (0 elements)
a_4: [-INF, -1]  EQUIVALENCES: { a_1(D) } (1 elements)

Substituing values and folding statements

foo (a)
{
  int y;

<bb 2>:
  if (a_1(D) < 0) goto <L0>; else goto <L2>;

<L0>:;
  a_2 = -a_1(D);
  y_3 = a_2 / 7;
  if (y_3 > 1073741824) goto <L1>; else goto <L2>;

<L1>:;
  link_error ();

<L2>:;
  return;

}


without -Wstrict-overflow=N warning about the issues with signed negation
and the [1, +INF(OVF)] derived range.  Note that the testcase is simple
enough that expansion optimizes the comparison, so it will not fail to link.


-- 
           Summary: [4.3 Regression] VRP no longer derives range for
                    division after negation
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at gcc dot gnu dot org


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

[Bug tree-optimization/31130] [4.3 Regression] VRP no longer derives range for division after negation

[ian at airs dot com]

------- Comment #1 from ian at airs dot com  2007-03-11 20:39 -------
I am testing this patch.

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c      (revision 122820)
+++ gcc/tree-vrp.c      (working copy)
@@ -2142,13 +2142,11 @@ extract_range_from_unary_expr (value_ran
        min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
       else if (needs_overflow_infinity (TREE_TYPE (expr)))
        {
-         if (supports_overflow_infinity (TREE_TYPE (expr)))
-           min = positive_overflow_infinity (TREE_TYPE (expr));
-         else
-           {
-             set_value_range_to_varying (vr);
-             return;
-           }
+         /* Negating TYPE_MIN_VALUE gives us a minimum value of
+            positive overflow infinity, and there is nothing useful
+            we can do with such a range.  */
+         set_value_range_to_varying (vr);
+         return;
        }
       else
        min = TYPE_MIN_VALUE (TREE_TYPE (expr));
@@ -2161,8 +2159,16 @@ extract_range_from_unary_expr (value_ran
        max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
       else if (needs_overflow_infinity (TREE_TYPE (expr)))
        {
-         if (supports_overflow_infinity (TREE_TYPE (expr)))
-           max = positive_overflow_infinity (TREE_TYPE (expr));
+         /* We have a non-overflowed TYPE_MIN as the minimum value.
+            If TYPE_MIN is also the maximum value, then negating this
+            gives us a positive overflow, and we just go straight to
+            varying since we will get there anyhow at the bottom of
+            this function.  Otherwise TYPE_MIN is a half-range
+            [TYPE_MIN, X] without overflow, so we flip it to a
+            half-range [-X, TYPE_MAX] without overflow.  */
+         if (vr0.max != TYPE_MIN_VALUE (TREE_TYPE (expr))
+             && !is_negative_overflow_infinity (vr0.max))
+           max = TYPE_MAX_VALUE (TREE_TYPE (expr));
          else
            {
              set_value_range_to_varying (vr);


-- 

ian at airs dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |ian at airs dot com
                   |dot org                     |
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-03-11 20:39:57
               date|                            |


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

[Bug tree-optimization/31130] [4.3 Regression] VRP no longer derives range for division after negation

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2007-03-12 05:43 -------

-         if (supports_overflow_infinity (TREE_TYPE (expr)))
-           min = positive_overflow_infinity (TREE_TYPE (expr));
-         else
-           {
-             set_value_range_to_varying (vr);
-             return;
-           }
+         /* Negating TYPE_MIN_VALUE gives us a minimum value of
+            positive overflow infinity, and there is nothing useful
+            we can do with such a range.  */
+         set_value_range_to_varying (vr);


This seems to introduce another missed optimization regression:

int f(int a)
{
  if (a < 0)
    a = -a;
  return a < 0;
}

A more complex example is where you do abs twice:
int f(int a)
{
  if (a < 0)
    a = -a;
  if (a < 0)
    a = -a;
  return a < 0;
}

The second abs should be removed in VRP but now it will not be removed.

-- Pinski who is upset at all these changes to VRP.  Also who is upset we
change GCC for people who don't know the language they are writting in.


-- 


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

[Bug tree-optimization/31130] [4.3 Regression] VRP no longer derives range for division after negation

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2007-03-12 06:11 -------
How about:
extern void link_error ();
void foo (int a)
{
  if (a < 0)
    {
      int y;
      a *=-2;
      y  = a / 7;
      if (y > 1 << 30)
        link_error ();
    }
}

int main()
{
  return 0;
}

Also?  Which is like the below testcase but is not just a = -a;

In fact it is weird to have:
extern void link_error ();
void foo (int a)
{
  if (a < 0)
    {
      int y;
      y  = -a / 7;
      if (y > 1 << 30)
        link_error ();
    }
}

Work and not the testcase in comment #0 to work :)  In fact -Wstrict-overflow
does not even warn about the above testcase :), even though the transformation
between -a / 7 to a/-7 dependings on integer overflow being undefined.  Looks
like someone missed a case in fold-const.c :).  (note I added it so I
remembered about it). 


-- 


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

[Bug tree-optimization/31130] [4.3 Regression] VRP no longer derives range for division after negation

[ian at airs dot com]

------- Comment #4 from ian at airs dot com  2007-03-12 17:08 -------
First test case:

int f(int a)
{
  if (a < 0)
    a = -a;
  return a < 0;
}

As far as I can tell the behaviour of this test case in VRP is unchanged by the
patch in this PR.  And the code is still fully optimized.

Second test case:

int f(int a)
{
  if (a < 0)
    a = -a;
  if (a < 0)
    a = -a;
  return a < 0;
}

In my tests the second conditional is removed during the VRP pass with or
without the patch in this PR.  It is cleaned up by jump threading.

Third test case:

extern void link_error ();
void foo (int a)
{
  if (a < 0)
    {
      int y;
      a *=-2;
      y  = a / 7;
      if (y > 1 << 30)
        link_error ();
    }
}

int main()
{
  return 0;
}

I agree that VRP does not sort this out, although the final generated code is
fine.  I personally think the overflow infinity code does the right thing here.

Fourth test case:

extern void link_error ();
void foo (int a)
{
  if (a < 0)
    {
      int y;
      y  = -a / 7;
      if (y > 1 << 30)
        link_error ();
    }
}

This does give a warning with -Wstrict-overflow=4


-- 


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

[Bug tree-optimization/31130] [4.3 Regression] VRP no longer derives range for division after negation

[ian at airs dot com]

------- Comment #5 from ian at airs dot com  2007-03-12 17:21 -------
Unfortunately my patch in comment #1 doesn't handle this test case correctly:

extern void abort (void);
void
foo (int a)
{
  if (a <= (int) 0x80000001)
    {
      a = - a;
      if (a > 0)
        abort ();
    }
}

It turns it into if (a > 0x80000001) abort(); with no warning.  The
transformation is OK with -fstrict-overflow, but we should get a warning with
-Wstrict-overflow, because it assumes that -INT_MIN > 0 is true.


-- 


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

[Bug tree-optimization/31130] [4.3 Regression] VRP no longer derives range for division after negation

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2007-03-13 09:30 -------
How tracking _two_ value ranges for signed quantities with undefined overflow.
One assuming it is undefined and one with wrapping semantics.  Whenever you
fold
something using the value range you warn if the folding result would differ
if using either or the other variant, if they do not differ, don't warn.  This
way you don't affect existing optimizations and strictly warn in the case the
transformation is done taking advantage of the undefined overflow.


-- 


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

[Bug tree-optimization/31130] [4.2/4.3 Regression] VRP no longer derives range for division after negation

[pinskia at gcc dot gnu dot org]

------- Comment #7 from pinskia at gcc dot gnu dot org  2007-04-28 01:41 -------
This also happens on the 4.2 branch.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.3 Regression] VRP no     |[4.2/4.3 Regression] VRP no
                   |longer derives range for    |longer derives range for
                   |division after negation     |division after negation
   Target Milestone|---                         |4.2.0


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

[Bug tree-optimization/31130] [4.2/4.3 Regression] VRP no longer derives range for division after negation

[ian at airs dot com]

------- Comment #8 from ian at airs dot com  2007-04-28 05:26 -------
I don't see why this PR should count as a regression, since there is no
regression in the generated code.  There is only a change in VRP behaviour. 
The generated code is the same.  This PR is only going to be really interesting
if we find a code regression.


-- 


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

[Bug tree-optimization/31130] [4.2/4.3 Regression] VRP no longer derives range for division after negation

[steven at gcc dot gnu dot org]

------- Comment #9 from steven at gcc dot gnu dot org  2007-04-28 09:56 -------
Re. comment #8, I have to disagree.  Add some flag to disable some optimization
(DOM iiuc) and you do have a code generation regression.


-- 


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

[Bug tree-optimization/31130] [4.2/4.3 Regression] VRP no longer derives range for division after negation

[mmitchel at gcc dot gnu dot org]

------- Comment #10 from mmitchel at gcc dot gnu dot org  2007-04-30 19:51 -------
I think this probably qualifies as a regression, given Stephen's comment #9,
but not an important one.  With all of GCC's optimization options, if we start
worrying about regressions for things outside the {-O0, -O1, -O2, -O3, -Os} set
of options that do not occur with those options, I think we're going to have a
very hard time keeping track of what's going on.  So, I have marked this P4.  


-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P4


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

[Bug tree-optimization/31130] [4.2/4.3 Regression] VRP no longer derives range for division after negation

[mmitchel at gcc dot gnu dot org]

------- Comment #11 from mmitchel at gcc dot gnu dot org  2007-05-14 22:27 -------
Will not be fixed in 4.2.0; retargeting at 4.2.1.


-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.2.0                       |4.2.1


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

[Bug tree-optimization/31130] [4.2/4.3 Regression] VRP no longer derives range for division after negation

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.2.1                       |4.2.2


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

[Bug tree-optimization/31130] [4.2/4.3 Regression] VRP no longer derives range for division after negation

[mmitchel at gcc dot gnu dot org]

------- Comment #12 from mmitchel at gcc dot gnu dot org  2007-10-09 19:22 -------
Change target milestone to 4.2.3, as 4.2.2 has been released.


-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.2.2                       |4.2.3


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

[Bug tree-optimization/31130] [4.2/4.3 Regression] VRP no longer derives range for division after negation

[jsm28 at gcc dot gnu dot org]

------- Comment #13 from jsm28 at gcc dot gnu dot org  2008-02-01 16:53 -------
4.2.3 is being released now, changing milestones of open bugs to 4.2.4.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.2.3                       |4.2.4


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

[Bug tree-optimization/31130] [4.2/4.3/4.4 Regression] VRP no longer derives range for division after negation

[jsm28 at gcc dot gnu dot org]

------- Comment #14 from jsm28 at gcc dot gnu dot org  2008-05-19 20:23 -------
4.2.4 is being released, changing milestones to 4.2.5.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.2.4                       |4.2.5


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

[Bug tree-optimization/31130] [4.2/4.3/4.4 Regression] VRP no longer derives range for division after negation

[pinskia at gcc dot gnu dot org]

------- Comment #15 from pinskia at gcc dot gnu dot org  2009-01-01 21:35 -------
Ian,
  This has been assigned to you for 9 months without any progress, are you
actively working on this?  If not please unassign this bug.


-- 


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

[Bug tree-optimization/31130] [4.2/4.3/4.4 Regression] VRP no longer derives range for division after negation

[ian at airs dot com]

------- Comment #16 from ian at airs dot com  2009-01-04 04:21 -------
I'm not working on this, sorry.


-- 

ian at airs dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|ian at airs dot com         |unassigned at gcc dot gnu
                   |                            |dot org
             Status|ASSIGNED                    |NEW


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

[Bug tree-optimization/31130] [4.3/4.4/4.5 Regression] VRP no longer derives range for division after negation

[jsm28 at gcc dot gnu dot org]

------- Comment #17 from jsm28 at gcc dot gnu dot org  2009-03-31 20:07 -------
Closing 4.2 branch.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.2/4.3/4.4/4.5 Regression]|[4.3/4.4/4.5 Regression] VRP
                   |VRP no longer derives range |no longer derives range for
                   |for division after negation |division after negation
   Target Milestone|4.2.5                       |4.3.4


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

[Bug tree-optimization/31130] [4.3/4.4/4.5 Regression] VRP no longer derives range for division after negation

[rguenth at gcc dot gnu dot org]

------- Comment #18 from rguenth at gcc dot gnu dot org  2009-08-04 12:28 -------
GCC 4.3.4 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.4                       |4.3.5


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

[Bug tree-optimization/31130] [4.3/4.4/4.5/4.6 Regression] VRP no longer derives range for division after negation

[rguenth at gcc dot gnu dot org]

------- Comment #19 from rguenth at gcc dot gnu dot org  2010-05-22 18:11 -------
GCC 4.3.5 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.5                       |4.3.6


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