[PR86153] simplify more overflow tests in VRP

[Alexandre Oliva <aoliva at redhat dot com>]

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

diff --git a/gcc/testsuite/gcc.dg/vrp-overflow-1.c b/gcc/testsuite/gcc.dg/vrp-overflow-1.c
new file mode 100644
index 000000000000..8e5794c77b6d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vrp-overflow-1.c
@@ -0,0 +1,151 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fno-tree-forwprop" } */
+
+extern void __attribute__((noreturn)) unreachable (void);
+
+int fle22 (int a)
+{
+  unsigned i = a / 4;
+  unsigned j = i - 2;
+
+  if (j == 7) /* A dynamic range excludes a value from j for the rest of f1.  */
+    return -1;
+
+  if (i <= 2) /* This dynamic range cannot be combined or compared with that of j.  */
+    return 0;
+
+  if (i <= j) /* And so we couldn't compute this result.  */
+    unreachable ();
+
+  return 1;
+}
+
+int fle32 (int a)
+{
+  unsigned i = a / 4;
+  unsigned j = i - 3;
+
+  if (j == 7) /* A dynamic range excludes a value from j for the rest of f1.  */
+    return -1;
+
+  if (i <= 2) /* This dynamic range cannot be combined or compared with that of j.  */
+    return 0;
+
+  if (i <= j) /* And so we couldn't compute this result.  */
+    unreachable ();
+
+  return 1;
+}
+
+int flt22 (int a)
+{
+  unsigned i = a / 4;
+  unsigned j = i - 2;
+
+  if (j == 7)
+    return -1;
+
+  if (i <= 2)
+    return 0;
+
+  if (i < j)
+    unreachable ();
+
+  return 1;
+}
+
+int flt32 (int a)
+{
+  unsigned i = a / 4;
+  unsigned j = i - 3;
+
+  if (j == 7)
+    return -1;
+
+  if (i <= 2)
+    return 0;
+
+  if (i < j)
+    unreachable ();
+
+  return 1;
+}
+
+int fgt22 (int a)
+{
+  unsigned i = a / 4;
+  unsigned j = i + 2;
+
+  if (j == -7)
+    return -1;
+
+  if (i >= -3)
+    return 0;
+
+  if (i > j)
+    unreachable ();
+
+  return 1;
+}
+
+int fgt32 (int a)
+{
+  unsigned i = a / 4;
+  unsigned j = i + 3;
+
+  if (j == -7)
+    return -1;
+
+  if (i >= -3)
+    return 0;
+
+  if (i > j)
+    unreachable ();
+
+  return 1;
+}
+
+int fge22 (int a)
+{
+  unsigned i = a / 4;
+  unsigned j = i + 2;
+
+  if (j == -7)
+    return -1;
+
+  if (i >= -3)
+    return 0;
+
+  if (i >= j)
+    unreachable ();
+
+  return 1;
+}
+
+int fge32 (int a)
+{
+  unsigned i = a / 4;
+  unsigned j = i + 3;
+
+  if (j == -7)
+    return -1;
+
+  if (i >= -3)
+    return 0;
+
+  if (i >= j)
+    unreachable ();
+
+  return 1;
+}
+
+int main (int argc, char *argv[]) {
+  fle22 (argc);
+  fle32 (argc);
+  flt22 (argc);
+  flt32 (argc);
+  fgt22 (argc);
+  fgt32 (argc);
+  fge22 (argc);
+  fge32 (argc);
+}
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.  */
+	  vro.intersect (vr0);
+	  if (vro.undefined_p ())
+	    return boolean_false_node;
+	  vri.intersect (vr0);
+	  if (vri.undefined_p ())
+	    return boolean_true_node;
+	}
     }
 
   if ((ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges

-- 
Alexandre Oliva, freedom fighter   https://FSFLA.org/blogs/lxo
Be the change, be Free!         FSF Latin America board member
GNU Toolchain Engineer                Free Software Evangelist
Hay que enGNUrecerse, pero sin perder la terGNUra jamás-GNUChe