[PR86153] simplify more overflow tests in VRP

Jeff, you mentioned you had changes to the VRP overflow test that would
fix this, but I couldn't figure out whether or not you ever put them in
and it regressed again later, or what.  Anyway, here's my take on it.


PR 86153 was originally filed when changes to the C++11's
implementation of vector resize(size_type) limited inlining that were
required for testsuite/g++.dg/pr83239.C to verify that we did not
issue an undesired warning.

That was worked by increasing the limit for inlining, but that in turn
caused the C++98 implementation of vector resize, that is
significantly different, to also be fully inlined, and that happened
to issue the very warnings the test was meant to verify we did NOT
issue.

The reason we issued the warnings was that we failed to optimize out
some parts of _M_fill_insert, used by the C++98 version of vector
resize, although the call of _M_fill_insert was guarded by a test that
could never pass: test testcase only calls resize when the vector size
is >= 3, to decrement the size by two.  The limitation we hit in VRP
was that the compared values could pass as an overflow test, if the
vector size was 0 or 1 (we knew it wasn't), but even with dynamic
ranges we failed to decide that the test result could be determined at
compile time, even though after the test we introduced ASSERT_EXPRs
that required a condition known to be false from earlier ones.

I pondered turning ASSERT_EXPRs that show impossible conditions into
traps, to enable subsequent instructions to be optimized, but I ended
up finding an earlier spot in which an overflow test that would have
introduced the impossible ASSERT_EXPR can have its result deduced from
earlier known ranges and resolved to the other path.

Although such overflow tests could be uniformly simplified to compares
against a constant, the original code would only perform such
simplifications when the test could be resolved to an equality test
against zero.  I've thus avoided introducing compares against other
constants, and instead added code that will only simplify overflow
tests that weren't simplified before when the condition can be
evaluated at compile time.


Regstrapped on x86_64- and i686-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	PR testsuite/86153
	* vr-values.c
	(vr_values::vrp_evaluate_conditional_warnv_with_ops): Extend
	simplification of overflow tests to cover cases in which we
	can determine the result of the comparison.

for  gcc/testsuite/ChangeLog

	PR testsuite/86153
	* gcc.dg/vrp-overflow-1.c: New.
---
 gcc/testsuite/gcc.dg/vrp-overflow-1.c |  151 +++++++++++++++++++++++++++++++++
 gcc/vr-values.c                       |   32 +++++++
 2 files changed, 183 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/vrp-overflow-1.c

On 12/18/18 3:58 AM, Alexandre Oliva wrote:
> Jeff, you mentioned you had changes to the VRP overflow test that would
> fix this, but I couldn't figure out whether or not you ever put them in
> and it regressed again later, or what.  Anyway, here's my take on it.
No, they're not on the trunk yet.  They're sitting here in my tester --
I lost the testcase I'd written to exercise them and hadn't gone back
and recreated it.

Mine catches fgt32, fge22, fge32, but misses the others in your
testcase.  I was generalizing the code in the same place, targeted
towards the 83239 testcase prior to Jon inserting the
___builtin_unreachable calls into the runtime.  They generalized things
so that instead of +-1 and a comparison against zero, we could have an
arbitrary constant and a relational between A or B and the constant.

I went back and recreated the testcase from 83239 prior to Jon's
patches.  Then verified it will issue a bogus warning on the trunk.
Then I applied your patch to the trunk and verified yours fixes the
warning.  So AFAICT your patch addresses the missed optimization in
83239 as well as the issues in 86153.  Please reference 83239 in your
your ChangeLog and close 83239 when you install  your patch.

I'm going to drop my changes related to 83239.  I don't think they have
much value once your patch is installed, except perhaps to slightly
simplify the code.





> 
> The reason we issued the warnings was that we failed to optimize out
> some parts of _M_fill_insert, used by the C++98 version of vector
> resize, although the call of _M_fill_insert was guarded by a test that
> could never pass: test testcase only calls resize when the vector size
> is >= 3, to decrement the size by two.  The limitation we hit in VRP
> was that the compared values could pass as an overflow test, if the
> vector size was 0 or 1 (we knew it wasn't), but even with dynamic
> ranges we failed to decide that the test result could be determined at
> compile time, even though after the test we introduced ASSERT_EXPRs
> that required a condition known to be false from earlier ones.
> 
> I pondered turning ASSERT_EXPRs that show impossible conditions into
> traps, to enable subsequent instructions to be optimized, but I ended
> up finding an earlier spot in which an overflow test that would have
> introduced the impossible ASSERT_EXPR can have its result deduced from
> earlier known ranges and resolved to the other path.
Right.  IMHO it's better to use the results of the ASSERT_EXPR to deduce
the tighter ranges and either prove a conditional is always true or
always false.


> 
> Although such overflow tests could be uniformly simplified to compares
> against a constant, the original code would only perform such
> simplifications when the test could be resolved to an equality test
> against zero.  I've thus avoided introducing compares against other
> constants, and instead added code that will only simplify overflow
> tests that weren't simplified before when the condition can be
> evaluated at compile time.That limitation was precisely what my (unsubmitted) patch was trying to
address :-)



> 
> 
> Regstrapped on x86_64- and i686-linux-gnu.  Ok to install?
> 
> 
> for  gcc/ChangeLog
> 
> 	PR testsuite/86153
> 	* vr-values.c
> 	(vr_values::vrp_evaluate_conditional_warnv_with_ops): Extend
> 	simplification of overflow tests to cover cases in which we
> 	can determine the result of the comparison.
> 
> for  gcc/testsuite/ChangeLog
> 
> 	PR testsuite/86153
> 	* gcc.dg/vrp-overflow-1.c: New.
> ---
>  gcc/testsuite/gcc.dg/vrp-overflow-1.c |  151 +++++++++++++++++++++++++++++++++
>  gcc/vr-values.c                       |   32 +++++++
>  2 files changed, 183 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/vrp-overflow-1.c
> 

> diff --git a/gcc/vr-values.c b/gcc/vr-values.c
> index cbc759a18e6a..25390ed6ef86 100644
> --- a/gcc/vr-values.c
> +++ b/gcc/vr-values.c
> @@ -2336,6 +2336,38 @@ vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
>  	  op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
>  	  code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
>  	}
> +      else
> +	{
> +	  value_range vro, vri;
> +	  if (code == GT_EXPR || code == GE_EXPR)
> +	    {
> +	      vro.set (VR_ANTI_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x);
> +	      vri.set (VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x);
> +	    }
> +	  else if (code == LT_EXPR || code == LE_EXPR)
> +	    {
> +	      vro.set (VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x);
> +	      vri.set (VR_ANTI_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x);
> +	    }
> +	  else
> +	    gcc_unreachable ();
> +	  value_range *vr0 = get_value_range (op0);
> +	  /* If the range for OP0 to pass the overflow test, namely
> +	     vro, has no intersection with the range for OP0, then the
> +	     overflow test can't pass, so return false.  If it is the
> +	     inverted range, vri, that has no intersection, then the
> +	     overflow test must pass, so return true.  In other cases,
> +	     we could proceed with a simplified condition comparing
> +	     OP0 and X, with LE_EXPR for previously LE_ or LT_EXPR and
> +	     GT_EXPR otherwise, but the comments next ot the enclosing
> +	     if suggest it's not generally profitable to do so.  */
The first sentence doesn't parse well.  s/ot/to in the last sentence.

OK with the comment fixed and addition of PR 83239 to the ChangeLog entry.

jeff

On Dec 18, 2018, Jeff Law <law@redhat.com> wrote:

>> Although such overflow tests could be uniformly simplified to compares
>> against a constant, the original code would only perform such
>> simplifications when the test could be resolved to an equality test
>> against zero.  I've thus avoided introducing compares against other
>> constants, and instead added code that will only simplify overflow
>> tests that weren't simplified before when the condition can be
>> evaluated at compile time.

> That limitation was precisely what my (unsubmitted) patch was trying
> to address :-)

This patch is what I was getting at in my earlier email.

These transformations are already performed elsewhere, e.g. when
forwprop is enabled, but given sufficiently complex code to begin with,
as in the pr83239 testcases, forwprop presumably runs too early to be
able to simplify the tests and then non-early vrp comes to the rescue.

Presumably with more convoluted tests than the ones I'm introducing,
forwprop would be unable to infer the ranges, and then we'd really
depend on vrp, but I didn't dig deep enough to try and create a testcase
that wouldn't be optimized by forwprop, only by vrp.  That's why the
tests disable forwprop.


[PR86153] simplify vrp overflow simplifications

It turns out there was apparently no reason to avoid simplifying every
overflow comparison to a compare with a constant, it was not
profitable because earlier VRP couldn't deal with that as well as it
does now.

So, make the transformation unconditionally, even in cases we'd have
transformed differently before my previous patch, and let the
now-better optimizations resolve them to boolean constants or to
equality tests when possible.

The only significant difference is that where we'd turn A>B after
B=A+1 into B!=0, we'll now turn it into A!=-1u.  That might seem
worse, but considering that test canonicalization will have moved the
(probably) earliest SSA version to the first operand, that form is
more likely to allow the later SSA definition, presumably in terms of
the earlier one, to be completely removed, which would have otherwise
required propagation of the assignment to B into the compare, which is
possible in equality tests, but not in other kinds of overflow tests.

Regstrapped on x86_64- and i686-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	PR testsuite/86153
	PR middle-end/83239
	* vr-values.c
	(vr_values::vrp_evaluate_conditional_warnv_with_ops): Simplify
	the handling of overflow comparisons.

for  gcc/testsuite/ChangeLog

	PR testsuite/86153
	PR middle-end/83239
	* gcc.dg/vrp-overflow-2.c: New.
---
 gcc/testsuite/gcc.dg/vrp-overflow-2.c |   35 ++++++++++++++++++
 gcc/vr-values.c                       |   66 +++------------------------------
 2 files changed, 40 insertions(+), 61 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/vrp-overflow-2.c

diff --git a/gcc/testsuite/gcc.dg/vrp-overflow-2.c b/gcc/testsuite/gcc.dg/vrp-overflow-2.c
new file mode 100644
index 000000000000..a905471bcaa1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vrp-overflow-2.c
@@ -0,0 +1,35 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fno-tree-forwprop" } */
+
+void __attribute__((noreturn)) undefined ();
+
+int tij (unsigned i)
+{
+  unsigned j = i + 1;
+
+  if (j == 0)
+    return 0;
+
+  if (i > j)
+    undefined ();
+
+  return 1;
+}
+
+int tji (unsigned i)
+{
+  unsigned j = i - 1;
+
+  if (i == 0)
+    return 0;
+
+  if (j > i)
+    undefined ();
+
+  return 1;
+}
+
+int main (int argc, char *argv[]) {
+  tij (argc);
+  tji (argc);
+}
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index d71a703ab550..49c5da9cb515 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -2305,70 +2305,14 @@ vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
       && !POINTER_TYPE_P (TREE_TYPE (op0)))
     return NULL_TREE;
 
-  /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
-     as a simple equality test, then prefer that over its current form
-     for evaluation.
-
-     An overflow test which collapses to an equality test can always be
-     expressed as a comparison of one argument against zero.  Overflow
-     occurs when the chosen argument is zero and does not occur if the
-     chosen argument is not zero.  */
+  /* If OP0 CODE OP1 is an overflow comparison, it can be expressed as
+     a test involving only one of the operands and a constant, so
+     prefer that over its current form for evaluation.  */
   tree x;
   if (overflow_comparison_p (code, op0, op1, use_equiv_p, &x))
     {
-      wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED);
-      /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
-         B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
-         B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
-         B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
-      if (integer_zerop (x))
-	{
-	  op1 = x;
-	  code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
-	}
-      /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
-         B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
-         B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
-         B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
-      else if (wi::to_wide (x) == max - 1)
-	{
-	  op0 = op1;
-	  op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
-	  code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
-	}
-      else
-	{
-	  value_range vro, vri;
-	  if (code == GT_EXPR || code == GE_EXPR)
-	    {
-	      vro.set (VR_ANTI_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x);
-	      vri.set (VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x);
-	    }
-	  else if (code == LT_EXPR || code == LE_EXPR)
-	    {
-	      vro.set (VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x);
-	      vri.set (VR_ANTI_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x);
-	    }
-	  else
-	    gcc_unreachable ();
-	  value_range *vr0 = get_value_range (op0);
-	  /* If vro, the range for OP0 to pass the overflow test, has
-	     no intersection with *vr0, OP0's known range, then the
-	     overflow test can't pass, so return the node for false.
-	     If it is the inverted range, vri, that has no
-	     intersection, then the overflow test must pass, so return
-	     the node for true.  In other cases, we could proceed with
-	     a simplified condition comparing OP0 and X, with LE_EXPR
-	     for previously LE_ or LT_EXPR and GT_EXPR otherwise, but
-	     the comments next to the enclosing if suggest it's not
-	     generally profitable to do so.  */
-	  vro.intersect (vr0);
-	  if (vro.undefined_p ())
-	    return boolean_false_node;
-	  vri.intersect (vr0);
-	  if (vri.undefined_p ())
-	    return boolean_true_node;
-	}
+      op1 = x;
+      code = (code == LT_EXPR || code == LE_EXPR) ? LE_EXPR : GT_EXPR;
     }
 
   if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges

On Dec 19, 2018, Alexandre Oliva <aoliva@redhat.com> wrote:

> +      op1 = x;
> +      code = (code == LT_EXPR || code == LE_EXPR) ? LE_EXPR : GT_EXPR;

So...  I've done some more testing, and this alone seems to overlap
nicely with what's in the trunk ATM, with a few exceptions:

- for some reason, LE/GT do not get us some simplifications that EQ/NE
  do when x is zero, despite the unsigned type for op0, that ought to
  make them equivalent.  That could probably be improved elsewhere, but
  it's easy enough to remedy with:

  if (integer_zerop (x))
    code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
  else
    code = (code == LT_EXPR || code == LE_EXPR) ? LE_EXPR : GT_EXPR;
   
- other differences I observed involved other case we currently
  transform to equality, namely, if x is (u)max-1, we test op1 against
  zero.  The transformation quoted above does better than this in at
  least 3 situations: a selftest in vec.c, cp_genericize_r in
  cp/cp-gimplify.c, and cp_maybe_mangle_decomp in cp/decl.c.  In these
  cases, op0 has a known range from 0 to INT_MAX or INT_MAX-1, so a
  compare of op0 vs 2u*INT_MAX can be folded to a constant, but the
  compare of op1 vs 0 we currently use cannot.

- the fact that in some cases a test against one of the overflow-related
  variables can be optimized when a test against the other can't
  surprised me; I would have expected the ranges and equivalences and
  whatnot to be such that this would never happen, but it does.  It
  suggests we could get some additional folding out of trying op1 vs
  max-x when op0 vs x fails to resolve to a constant.


FTR, here's the patchlet (-b) I've used to look for differences.


commit 2fe0b2784815882c3e2821b171979b54c3ffdc55
Author: Alexandre Oliva <aoliva@redhat.com>
Date:   Sat Dec 29 00:21:42 2018 -0200

    [PR86153/83239] identify vrp overflow simplification differences to investigate

diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index d71a703ab550..a40c41e4d139 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -2296,7 +2296,6 @@ vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
 						    bool *strict_overflow_p,
 						    bool *only_ranges)
 {
-  tree ret;
   if (only_ranges)
     *only_ranges = true;
 
@@ -2316,6 +2315,40 @@ vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
   tree x;
   if (overflow_comparison_p (code, op0, op1, use_equiv_p, &x))
     {
+      tree ret1 = ovrflow_vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, x,
+								   use_equiv_p,
+								   strict_overflow_p,
+								   only_ranges);
+
+      op1 = x;
+      if (integer_zerop (x))
+	code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
+      else
+	code = (code == LT_EXPR || code == LE_EXPR) ? LE_EXPR : GT_EXPR;
+
+      tree ret2 = rest_of_vrp_evaluate_conditional_warnv_with_ops (code, op0, op1,
+								   use_equiv_p,
+								   strict_overflow_p,
+								   only_ranges);
+      gcc_assert (ret1 == ret2
+		  || (ret1 && ret2 && operand_equal_p (ret1, ret2, 0)));
+
+      return ret2;
+    }
+  else
+    return rest_of_vrp_evaluate_conditional_warnv_with_ops (code, op0, op1,
+							    use_equiv_p,
+							    strict_overflow_p,
+							    only_ranges);
+}
+
+tree vr_values::
+ovrflow_vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
+						 tree op0, tree op1, tree x,
+						 bool use_equiv_p,
+						 bool *strict_overflow_p,
+						 bool *only_ranges)
+{
   wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED);
   /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
      B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
@@ -2369,7 +2402,21 @@ vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
       if (vri.undefined_p ())
 	return boolean_true_node;
     }
-    }
+
+  return rest_of_vrp_evaluate_conditional_warnv_with_ops (code, op0, op1,
+							  use_equiv_p,
+							  strict_overflow_p,
+							  only_ranges);
+}
+
+tree vr_values::
+rest_of_vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
+						 tree op0, tree op1,
+						 bool use_equiv_p,
+						 bool *strict_overflow_p,
+						 bool *only_ranges)
+{
+  tree ret;
 
   if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges
 	       (code, op0, op1, strict_overflow_p)))
diff --git a/gcc/vr-values.h b/gcc/vr-values.h
index 6785cb68fa76..e30719e82599 100644
--- a/gcc/vr-values.h
+++ b/gcc/vr-values.h
@@ -85,6 +85,17 @@ class vr_values
   tree vrp_evaluate_conditional_warnv_with_ops (enum tree_code,
 						tree, tree, bool,
 						bool *, bool *);
+  tree rest_of_vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
+							tree op0, tree op1,
+							bool use_equiv_p,
+							bool *strict_overflow_p,
+							bool *only_ranges);
+  tree ovrflow_vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
+							tree op0, tree op1, tree x,
+							bool use_equiv_p,
+							bool *strict_overflow_p,
+							bool *only_ranges);
+
   void extract_range_from_assignment (value_range *, gassign *);
   void extract_range_from_assert (value_range *, tree);
   void extract_range_from_ssa_name (value_range *, tree);