Bug 31130 - [7 Regression] VRP no longer derives range for division after negation
Summary: [7 Regression] VRP no longer derives range for division after negation
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.3.0
: P4 normal
Target Milestone: 8.0
Assignee: Not yet assigned to anyone
URL:
Keywords: missed-optimization
Depends on:
Blocks: VRP
  Show dependency treegraph
 
Reported: 2007-03-11 11:43 UTC by Richard Biener
Modified: 2019-11-15 01:02 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work: 8.1.0
Known to fail:
Last reconfirmed: 2007-03-11 20:39:57


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Richard Biener 2007-03-11 11:43:02 UTC
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.
Comment 1 Ian Lance Taylor 2007-03-11 20:39:57 UTC
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);
Comment 2 Andrew Pinski 2007-03-12 05:43:11 UTC
-         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.
Comment 3 Andrew Pinski 2007-03-12 06:11:59 UTC
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). 
Comment 4 Ian Lance Taylor 2007-03-12 17:08:20 UTC
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
Comment 5 Ian Lance Taylor 2007-03-12 17:21:58 UTC
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.
Comment 6 Richard Biener 2007-03-13 09:30:15 UTC
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.
Comment 7 Andrew Pinski 2007-04-28 01:41:39 UTC
This also happens on the 4.2 branch.
Comment 8 Ian Lance Taylor 2007-04-28 05:26:16 UTC
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.
Comment 9 Steven Bosscher 2007-04-28 09:56:07 UTC
Re. comment #8, I have to disagree.  Add some flag to disable some optimization (DOM iiuc) and you do have a code generation regression.
Comment 10 Mark Mitchell 2007-04-30 19:51:18 UTC
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.  
Comment 11 Mark Mitchell 2007-05-14 22:27:30 UTC
Will not be fixed in 4.2.0; retargeting at 4.2.1.
Comment 12 Mark Mitchell 2007-10-09 19:22:08 UTC
Change target milestone to 4.2.3, as 4.2.2 has been released.
Comment 13 Joseph S. Myers 2008-02-01 16:53:51 UTC
4.2.3 is being released now, changing milestones of open bugs to 4.2.4.
Comment 14 Joseph S. Myers 2008-05-19 20:23:02 UTC
4.2.4 is being released, changing milestones to 4.2.5.
Comment 15 Andrew Pinski 2009-01-01 21:35:41 UTC
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.
Comment 16 Ian Lance Taylor 2009-01-04 04:21:43 UTC
I'm not working on this, sorry.
Comment 17 Joseph S. Myers 2009-03-31 20:07:32 UTC
Closing 4.2 branch.
Comment 18 Richard Biener 2009-08-04 12:28:03 UTC
GCC 4.3.4 is being released, adjusting target milestone.
Comment 19 Richard Biener 2010-05-22 18:11:26 UTC
GCC 4.3.5 is being released, adjusting target milestone.
Comment 20 Richard Biener 2011-06-27 12:12:00 UTC
4.3 branch is being closed, moving to 4.4.7 target.
Comment 21 Jakub Jelinek 2012-03-13 12:44:46 UTC
4.4 branch is being closed, moving to 4.5.4 target.
Comment 22 Jakub Jelinek 2013-04-12 15:15:29 UTC
GCC 4.6.4 has been released and the branch has been closed.
Comment 23 Richard Biener 2014-06-12 13:41:12 UTC
The 4.7 branch is being closed, moving target milestone to 4.8.4.
Comment 24 Jakub Jelinek 2014-12-19 13:31:23 UTC
GCC 4.8.4 has been released.
Comment 25 Richard Biener 2015-06-23 08:12:57 UTC
The gcc-4_8-branch is being closed, re-targeting regressions to 4.9.3.
Comment 26 Jakub Jelinek 2015-06-26 19:55:55 UTC
GCC 4.9.3 has been released.
Comment 27 Richard Biener 2016-08-03 10:43:08 UTC
GCC 4.9 branch is being closed
Comment 28 Richard Biener 2017-05-04 07:30:31 UTC
Author: rguenth
Date: Thu May  4 07:29:55 2017
New Revision: 247578

URL: https://gcc.gnu.org/viewcvs?rev=247578&root=gcc&view=rev
Log:
2017-05-04  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/31130
	* tree-vrp.c (needs_overflow_infinity): Remove as always returning
	false.
	(supports_overflow_infinity): Likewise.
	(is_negative_overflow_infinity): Likewise.
	(is_positive_overflow_infinity): Likewise.
	(is_overflow_infinity): Likewise.
	(stmt_overflow_infinity): Likewise.
	(overflow_infinity_range_p): Likewise.
	(usable_range_p): Remove as always returning true.
	(make_overflow_infinity): Remove.
	(negative_overflow_infinity): Likewise.
	(positive_overflow_infinity): Likewise.
	(avoid_overflow_infinity): Likewise.
	(set_value_range): Adjust accordingly.
	(set_value_range_to_nonnegative): Likewise, remove now unused
	overflow_infinity arg.
	(vrp_operand_equal_p): Adjust.
	(update_value_range): Likewise.
	(range_int_cst_singleton_p): Likewise.
	(operand_less_p): Likewise.
	(compare_values_warnv): Likewise.
	(extract_range_for_var_from_comparison_expr): Likewise.
	(vrp_int_const_binop): Likewise.
	(zero_nonzero_bits_from_vr): Likewise.
	(extract_range_from_multiplicative_op_1): Likewise.
	(extract_range_from_binary_expr_1): Likewise.
	(extract_range_from_unary_expr): Likewise.
	(extract_range_from_comparison): Likewise.
	(extract_range_basic): Likewise.
	(adjust_range_with_scev): Likewise.
	(compare_ranges): Likewise.
	(compare_range_with_value): Likewise.
	(dump_value_range): Likewise.
	(test_for_singularity): Likewise, remove strict_overflow_p parameter
	never used.
	(simplify_cond_using_ranges): Adjust.

	* gcc.dg/Wstrict-overflow-12.c: XFAIL.
	* gcc.dg/Wstrict-overflow-13.c: Likewise.
	* gcc.dg/Wstrict-overflow-21.c: Likewise.
	* gcc.dg/pr52904.c: Remove XFAIL.
	* gcc.dg/tree-ssa/vrp114.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp114.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/Wstrict-overflow-12.c
    trunk/gcc/testsuite/gcc.dg/Wstrict-overflow-13.c
    trunk/gcc/testsuite/gcc.dg/Wstrict-overflow-21.c
    trunk/gcc/testsuite/gcc.dg/pr52904.c
    trunk/gcc/tree-vrp.c
Comment 29 Jakub Jelinek 2018-10-26 10:18:13 UTC
GCC 6 branch is being closed
Comment 30 Michael Matz 2018-11-19 19:52:45 UTC
As far as I can tell this is fixed in gcc-9 (and should be in gcc-8 as well).
Certainly all testcases herein are optimized as expected.
Comment 31 Richard Biener 2018-11-20 08:10:33 UTC
Yeah, should be fixed with the removal of -fno-strict-overflow.
Comment 32 Richard Biener 2019-11-14 09:08:24 UTC
Fixed in GCC 8.