diff mbox series

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

Message ID 9b234c9a-5020-c97c-c379-877c4c018293@redhat.com
State New, archived
Headers
Series Process unsigned overflow relations for plus and minus in range-ops. |

Commit Message

Andrew MacLeod Sept. 29, 2022, 10:38 p.m. UTC 
  If a relation is available, calculate overflow and normal ranges. Then 
apply as appropriate.

This patch implements operator_plus::op1/op2_range and 
operator_minus::op1_range to utilize any relation passed into properly 
reflect the range.

If the relation between the LHS and the operand being calculated is one 
of <,<=,>,>=, then determine what the overflow and normal ranges are for 
this type, and reflect those in the operand being calculated.

With this patch, we can move the testcase for PR 79095 to an evrp test 
instead of vrp1, so we resolve it much earlier.  This testcase tests 
various overflow conditions to ensure we can detect and propagate 
overflow conditions.  ie, it has a series of tests similar to:

unsigned
f1 (unsigned a, unsigned b)
{
   b = a + 1;
   if (b < a)
     {
       arf (a, b);
       return 42;
     }
   baz (a, b);
   return b;
}

It tests that 'baz' remains a call using symbolic names, and that 'arf' 
can be folded to constant arguments.

Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed.

Andrew

Comments

Bernhard Reutner-Fischer Oct. 1, 2022, 7:47 a.m. UTC | #1 
On Thu, 29 Sep 2022 18:38:10 -0400
Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:

> 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.

Capital A in A return value

> +
> +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.

s/relatoin/relation/
Excess space before the last sentense, or should this go to a new line?

> +
> +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

You could remove ATTRIBUTE_UNUSED above for rel like you did for the
other operators.

>  {
> -  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/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); }

surplus braces.
This could be __attribute__((__pure__)) but that's certainly found by
predict even without the annotation? Probably it makes no difference
because it's inlined anyway.
thanks,

>  void print_relation (FILE *f, relation_kind rel);
>  
>  class relation_oracle
diff mbox series

Patch

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