Process unsigned overflow relations for plus and minus in range-ops.

From f02cb8601792be310e8760b082e0c3213129639a Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Tue, 23 Aug 2022 10:17:02 -0400
Subject: [PATCH 6/6] Process unsigned overflow relations for plus and minus is
 range-ops.

If a relation is available, calculate overflow and normal ranges. Then
apply as appropriate.

	gcc/
	* range-op.cc (plus_minus_ranges): New.
	(adjust_op1_for_overflow): New.
	(operator_plus::op1_range): Use new adjustment.
	(operator_plus::op2_range): Ditto.
	(operator_minus::op1_range): Ditto.
	* value-relation.h (relation_lt_le_gt_ge_p): New.

	gcc/testsuite/
	* gcc.dg/tree-ssa/pr79095.c: Test evrp pass rather than vrp1.
---
 gcc/range-op.cc                         | 121 +++++++++++++++++++++++-
 gcc/testsuite/gcc.dg/tree-ssa/pr79095.c |   6 +-
 gcc/value-relation.h                    |   2 +
 3 files changed, 121 insertions(+), 8 deletions(-)

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 9bb04c361d0..830c64bd6b9 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -1305,22 +1305,123 @@  operator_plus::wi_fold (irange &r, tree type,
   value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
 }
 
+// Given addition or subtraction, determine the possible NORMAL ranges and
+// OVERFLOW ranges given an OFFSET range.  ADD_P is true for addition.
+// Return the relation that exists between the LHS and OP1 in order for the
+// NORMAL range to apply.
+// a return value of VREL_VARYING means no ranges were applicable.
+
+static relation_kind
+plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
+		bool add_p)
+{
+  relation_kind kind = VREL_VARYING;
+  // For now, only deal with constant adds.  This could be extended to ranges
+  // when someone is so motivated.
+  if (!offset.singleton_p () || offset.zero_p ())
+    return kind;
+
+  // Always work with a positive offset.  ie a+ -2 -> a-2  and a- -2 > a+2
+  wide_int off = offset.lower_bound ();
+  if (wi::neg_p (off, SIGNED))
+    {
+      add_p = !add_p;
+      off = wi::neg (off);
+    }
+
+  wi::overflow_type ov;
+  tree type = offset.type ();
+  unsigned prec = TYPE_PRECISION (type);
+  wide_int ub;
+  wide_int lb;
+  // calculate the normal range and relation for the operation.
+  if (add_p)
+    {
+      //  [ 0 , INF - OFF]
+      lb = wi::zero (prec);
+      ub = wi::sub (wi::to_wide (vrp_val_max (type)), off, UNSIGNED, &ov);
+      kind = VREL_GT;
+    }
+  else
+    {
+      //  [ OFF, INF ]
+      lb = off;
+      ub = wi::to_wide (vrp_val_max (type));
+      kind = VREL_LT;
+    }
+  int_range<2> normal_range (type, lb, ub);
+  int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
+
+  r_ov = ov_range;
+  r_normal = normal_range;
+  return kind;
+}
+
+// Once op1 has been calculated by operator_plus or operator_minus, check
+// to see if the relation passed causes any part of the calculation to
+// be not possible.  ie
+// a_2 = b_3 + 1  with a_2 < b_3 can refine the range of b_3 to [INF, INF]
+// and that further refines a_2 to [0, 0].
+// R is the value of op1, OP2 is the offset being added/subtracted, REL is the
+// relation between LHS relatoin OP1  and ADD_P is true for PLUS, false for
+// MINUS.    IF any adjustment can be made, R will reflect it.
+
+static void
+adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
+			 bool add_p)
+{
+  tree type = r.type ();
+  // Check for unsigned overflow and calculate the overflow part.
+  signop s = TYPE_SIGN (type);
+  if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
+    return;
+
+  // Only work with <, <=, >, >= relations.
+  if (!relation_lt_le_gt_ge_p (rel))
+    return;
+
+  // Get the ranges for this offset.
+  int_range_max normal, overflow;
+  relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p);
+
+  // VREL_VARYING means there are no adjustments.
+  if (k == VREL_VARYING)
+    return;
+
+  // If the relations match use the normal range, otherwise use overflow range.
+  if (relation_intersect (k, rel) == k)
+    r.intersect (normal);
+  else
+    r.intersect (overflow);
+  return;
+}
+
 bool
 operator_plus::op1_range (irange &r, tree type,
 			  const irange &lhs,
 			  const irange &op2,
-			  relation_kind rel ATTRIBUTE_UNUSED) const
+			  relation_kind rel) const
 {
-  return range_op_handler (MINUS_EXPR, type).fold_range (r, type, lhs, op2);
+  if (lhs.undefined_p ())
+    return false;
+  // Start with the default operation.
+  range_op_handler minus (MINUS_EXPR, type);
+  if (!minus)
+    return false;
+  bool res = minus.fold_range (r, type, lhs, op2);
+  // Check for a relation refinement.
+  if (res)
+    adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */);
+  return res;
 }
 
 bool
 operator_plus::op2_range (irange &r, tree type,
 			  const irange &lhs,
 			  const irange &op1,
-			  relation_kind rel ATTRIBUTE_UNUSED) const
+			  relation_kind rel) const
 {
-  return range_op_handler (MINUS_EXPR, type).fold_range (r, type, lhs, op1);
+  return op1_range (r, type, lhs, op1, rel);
 }
 
 
@@ -1472,7 +1573,17 @@  operator_minus::op1_range (irange &r, tree type,
 			   const irange &op2,
 			   relation_kind rel ATTRIBUTE_UNUSED) const
 {
-  return range_op_handler (PLUS_EXPR, type).fold_range (r, type, lhs, op2);
+  if (lhs.undefined_p ())
+    return false;
+  // Start with the default operation.
+  range_op_handler minus (PLUS_EXPR, type);
+  if (!minus)
+    return false;
+  bool res = minus.fold_range (r, type, lhs, op2);
+  if (res)
+    adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */);
+  return res;
+
 }
 
 bool
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c
index f635fcafe4f..b1751877756 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c
@@ -1,5 +1,5 @@ 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-ipa-icf -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fno-ipa-icf -fdump-tree-evrp" } */
 
 extern void arf (unsigned x, unsigned y);
 extern void baz (unsigned x, unsigned y);
@@ -429,8 +429,8 @@  f4nro (unsigned a, unsigned b)
 }
 
 /* All calls to baz should still reference a & b as arguments. */
-/* { dg-final { scan-tree-dump-times "baz \\(a_\[0-9\]+\\(D\\), b_\[0-9\]+\\)" 32 "vrp1"} } */
+/* { dg-final { scan-tree-dump-times "baz \\(a_\[0-9\]+\\(D\\), b_\[0-9\]+\\)" 32 "evrp"} } */
 
 
 /* All calls to arf should have constant arguments.  */
-/* { dg-final { scan-tree-dump-times "arf \\(\[0-9\]+, \[0-9\]+\\)" 32 "vrp1"} } */
+/* { dg-final { scan-tree-dump-times "arf \\(\[0-9\]+, \[0-9\]+\\)" 32 "evrp"} } */
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
index f3b18ac62ef..e1347ea8ad8 100644
--- a/gcc/value-relation.h
+++ b/gcc/value-relation.h
@@ -78,6 +78,8 @@  relation_kind relation_union (relation_kind r1, relation_kind r2);
 relation_kind relation_intersect (relation_kind r1, relation_kind r2);
 relation_kind relation_negate (relation_kind r);
 relation_kind relation_swap (relation_kind r);
+inline bool relation_lt_le_gt_ge_p (relation_kind r)
+				    { return (r >= VREL_LT && r <= VREL_GE); }
 void print_relation (FILE *f, relation_kind rel);
 
 class relation_oracle
-- 
2.37.3