diff mbox series

[COMMITTED,4/7] Add relations between LHS and op1/op2 for PLUS_EXPR.

Message ID 9103ab49-d653-fc55-0ef6-6465bde4913c@redhat.com
State New
Headers show
Series [COMMITTED,1/7] Initial value-relation code. | expand

Commit Message

Andrew MacLeod June 22, 2021, 1:18 p.m. UTC 
This patch demonstrates how to add relation generation between the LHS 
of an expression and one of the operands in range-ops, using PLUS_EXPR.

a_2 = b_3 + c_1

if c_1 == [0, 0], we know a_2 == b_3

if c_1 > 0, and there is no overflow/wrapping, we know a_2 > b_3

likewise, if c1 < 0 we know a_2 < b_3

if c_1 does not contain zero, we also know a_2 != b_3.

plus is symmetrical, so we can draw similar conclusions about the 
relation between a_2 and c_1 based on what we know about b_3's range.

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

Andrew
diff mbox series

Patch

From c526de3f432a037bdbdd44eb6fa43af4f3b22694 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Thu, 17 Jun 2021 13:35:10 -0400
Subject: [PATCH 4/7] Add relations between LHS and op1/op2 for PLUS_EXPR.

	* range-op.cc (operator_plus::lhs_op1_relation): New.
	(operator_plus::lhs_op2_relation): New.
---
 gcc/range-op.cc | 80 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index d807693900a..a7698f21b0d 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -1150,8 +1150,88 @@  public:
 		        const wide_int &lh_ub,
 		        const wide_int &rh_lb,
 		        const wide_int &rh_ub) const;
+  virtual enum tree_code lhs_op1_relation (const irange &lhs, const irange &op1,
+					   const irange &op2) const;
+  virtual enum tree_code lhs_op2_relation (const irange &lhs, const irange &op1,
+					   const irange &op2) const;
 } op_plus;
 
+// Check to see if the range of OP2 indicates anything about the relation
+// between LHS and OP1.
+
+enum tree_code
+operator_plus::lhs_op1_relation (const irange &lhs,
+				 const irange &op1,
+				 const irange &op2) const
+{
+  if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
+    return VREL_NONE;
+
+  tree type = lhs.type ();
+  unsigned prec = TYPE_PRECISION (type);
+  wi::overflow_type ovf1, ovf2;
+  signop sign = TYPE_SIGN (type);
+
+  // LHS = OP1 + 0  indicates LHS == OP1.
+  if (op2.zero_p ())
+    return EQ_EXPR;
+
+  if (TYPE_OVERFLOW_WRAPS (type))
+    {
+      wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1);
+      wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2);
+    }
+  else
+    ovf1 = ovf2 = wi::OVF_NONE;
+
+  // Never wrapping additions.
+  if (!ovf1 && !ovf2)
+    {
+      // Positive op2 means lhs > op1.
+      if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
+	return GT_EXPR;
+      if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
+	return GE_EXPR;
+
+      // Negative op2 means lhs < op1.
+      if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
+	return LT_EXPR;
+      if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
+	return LE_EXPR;
+    }
+  // Always wrapping additions.
+  else if (ovf1 && ovf1 == ovf2)
+    {
+      // Positive op2 means lhs < op1.
+      if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
+	return LT_EXPR;
+      if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
+	return LE_EXPR;
+
+      // Negative op2 means lhs > op1.
+      if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
+	return GT_EXPR;
+      if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
+	return GE_EXPR;
+    }
+
+  // If op2 does not contain 0, then LHS and OP1 can never be equal.
+  if (!range_includes_zero_p (&op2))
+    return NE_EXPR;
+
+  return VREL_NONE;
+}
+
+// PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
+// operands.
+
+enum tree_code
+operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
+				 const irange &op2) const
+{
+  return lhs_op1_relation (lhs, op2, op1);
+}
+
 void
 operator_plus::wi_fold (irange &r, tree type,
 			const wide_int &lh_lb, const wide_int &lh_ub,
-- 
2.17.2