diff mbox series

[3/9] Simplify X /[ex] Y cmp Z -> X cmp (Y * Z)

Message ID 20241018111806.4026759-4-richard.sandiford@arm.com
State New
Headers show
Series Add more folds related to exact division | expand

Commit Message

Richard Sandiford Oct. 18, 2024, 11:18 a.m. UTC 
This patch applies X /[ex] Y cmp Z -> X cmp (Y * Z) when Y * Z is
representable.  The closest check for "is representable" on range
operations seemed to be overflow_free_p.  However, that is designed
for testing existing operations and so takes the definedness of
signed overflow into account.  Here, the question is whether we
can create an entirely new value.

The patch adds a new optional argument to overflow_free_p to
distinguish these cases.  It also adds a wrapper, so that it isn't
necessary to specify TRIO_VARYING.

I couldn't find a good way of removing the duplication between
the two operand orders.  The rules are (in a loose sense) symmetric,
but they're not based on commutativity.

gcc/
	* range-op.h (range_query_type): New enum.
	(range_op_handler::fits_type_p): New function.
	(range_operator::overflow_free_p): Add an argument to specify the
	type of query.
	(range_op_handler::overflow_free_p): Likewise.
	* range-op-mixed.h (operator_plus::overflow_free_p): Likewise.
	(operator_minus::overflow_free_p): Likewise.
	(operator_mult::overflow_free_p): Likewise.
	* range-op.cc (range_op_handler::overflow_free_p): Likewise.
	(range_operator::overflow_free_p): Likewise.
	(operator_plus::overflow_free_p): Likewise.
	(operator_minus::overflow_free_p): Likewise.
	(operator_mult::overflow_free_p): Likewise.
	* match.pd: Simplify X /[ex] Y cmp Z -> X cmp (Y * Z) when
	Y * Z is representable.

gcc/testsuite/
	* gcc.dg/tree-ssa/cmpexactdiv-7.c: New test.
	* gcc.dg/tree-ssa/cmpexactdiv-8.c: Likewise.
---
 gcc/match.pd                                  | 21 +++++++++++++
 gcc/range-op-mixed.h                          |  9 ++++--
 gcc/range-op.cc                               | 19 ++++++------
 gcc/range-op.h                                | 31 +++++++++++++++++--
 gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-7.c | 21 +++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-8.c | 20 ++++++++++++
 6 files changed, 107 insertions(+), 14 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-7.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-8.c
diff mbox series

Patch

diff --git a/gcc/match.pd b/gcc/match.pd
index b952225b08c..1b1d38cf105 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2679,6 +2679,27 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	(le (minus (convert:etype @0) { lo; }) { hi; })
 	(gt (minus (convert:etype @0) { lo; }) { hi; })))))))))
 
+#if GIMPLE
+/* X /[ex] Y cmp Z -> X cmp (Y * Z), if Y * Z is representable.  */
+(for cmp (simple_comparison)
+ (simplify
+  (cmp (exact_div:s @0 @1) @2)
+  (with { int_range_max r1, r2; }
+   (if (INTEGRAL_TYPE_P (type)
+	&& get_range_query (cfun)->range_of_expr (r1, @1)
+	&& get_range_query (cfun)->range_of_expr (r2, @2)
+	&& range_op_handler (MULT_EXPR).fits_type_p (r1, r2))
+    (cmp @0 (mult @1 @2)))))
+ (simplify
+  (cmp @2 (exact_div:s @0 @1))
+  (with { int_range_max r1, r2; }
+   (if (INTEGRAL_TYPE_P (type)
+	&& get_range_query (cfun)->range_of_expr (r1, @1)
+	&& get_range_query (cfun)->range_of_expr (r2, @2)
+	&& range_op_handler (MULT_EXPR).fits_type_p (r1, r2))
+    (cmp (mult @1 @2) @0)))))
+#endif
+
 /* X + Z < Y + Z is the same as X < Y when there is no overflow.  */
 (for op (lt le ge gt)
  (simplify
diff --git a/gcc/range-op-mixed.h b/gcc/range-op-mixed.h
index cc1db2f6775..402cb87c2b2 100644
--- a/gcc/range-op-mixed.h
+++ b/gcc/range-op-mixed.h
@@ -539,7 +539,8 @@  public:
 		       const irange &rh) const final override;
 
   virtual bool overflow_free_p (const irange &lh, const irange &rh,
-				relation_trio = TRIO_VARYING) const;
+				relation_trio = TRIO_VARYING,
+				range_query_type = QUERY_WITH_GIMPLE_UB) const;
   // Check compatibility of all operands.
   bool operand_check_p (tree t1, tree t2, tree t3) const final override
     { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
@@ -615,7 +616,8 @@  public:
 		       const irange &rh) const final override;
 
   virtual bool overflow_free_p (const irange &lh, const irange &rh,
-				relation_trio = TRIO_VARYING) const;
+				relation_trio = TRIO_VARYING,
+				range_query_type = QUERY_WITH_GIMPLE_UB) const;
   // Check compatibility of all operands.
   bool operand_check_p (tree t1, tree t2, tree t3) const final override
     { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
@@ -701,7 +703,8 @@  public:
 		const REAL_VALUE_TYPE &rh_lb, const REAL_VALUE_TYPE &rh_ub,
 		relation_kind kind) const final override;
   virtual bool overflow_free_p (const irange &lh, const irange &rh,
-				relation_trio = TRIO_VARYING) const;
+				relation_trio = TRIO_VARYING,
+				range_query_type = QUERY_WITH_GIMPLE_UB) const;
   // Check compatibility of all operands.
   bool operand_check_p (tree t1, tree t2, tree t3) const final override
     { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 3f5cf083440..1634cebd1bd 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -470,7 +470,8 @@  range_op_handler::op1_op2_relation (const vrange &lhs,
 bool
 range_op_handler::overflow_free_p (const vrange &lh,
 				   const vrange &rh,
-				   relation_trio rel) const
+				   relation_trio rel,
+				   range_query_type query_type) const
 {
   gcc_checking_assert (m_operator);
   switch (dispatch_kind (lh, lh, rh))
@@ -478,7 +479,7 @@  range_op_handler::overflow_free_p (const vrange &lh,
       case RO_III:
 	return m_operator->overflow_free_p(as_a <irange> (lh),
 					   as_a <irange> (rh),
-					   rel);
+					   rel, query_type);
       default:
 	return false;
     }
@@ -823,7 +824,7 @@  range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED,
 
 bool
 range_operator::overflow_free_p (const irange &, const irange &,
-				 relation_trio) const
+				 relation_trio, range_query_type) const
 {
   return false;
 }
@@ -4532,13 +4533,13 @@  range_op_table::initialize_integral_ops ()
 
 bool
 operator_plus::overflow_free_p (const irange &lh, const irange &rh,
-				relation_trio) const
+				relation_trio, range_query_type query_type) const
 {
   if (lh.undefined_p () || rh.undefined_p ())
     return false;
 
   tree type = lh.type ();
-  if (TYPE_OVERFLOW_UNDEFINED (type))
+  if (query_type == QUERY_WITH_GIMPLE_UB && TYPE_OVERFLOW_UNDEFINED (type))
     return true;
 
   wi::overflow_type ovf;
@@ -4563,13 +4564,13 @@  operator_plus::overflow_free_p (const irange &lh, const irange &rh,
 
 bool
 operator_minus::overflow_free_p (const irange &lh, const irange &rh,
-				 relation_trio) const
+				 relation_trio, range_query_type query_type) const
 {
   if (lh.undefined_p () || rh.undefined_p ())
     return false;
 
   tree type = lh.type ();
-  if (TYPE_OVERFLOW_UNDEFINED (type))
+  if (query_type == QUERY_WITH_GIMPLE_UB && TYPE_OVERFLOW_UNDEFINED (type))
     return true;
 
   wi::overflow_type ovf;
@@ -4594,13 +4595,13 @@  operator_minus::overflow_free_p (const irange &lh, const irange &rh,
 
 bool
 operator_mult::overflow_free_p (const irange &lh, const irange &rh,
-				relation_trio) const
+				relation_trio, range_query_type query_type) const
 {
   if (lh.undefined_p () || rh.undefined_p ())
     return false;
 
   tree type = lh.type ();
-  if (TYPE_OVERFLOW_UNDEFINED (type))
+  if (query_type == QUERY_WITH_GIMPLE_UB && TYPE_OVERFLOW_UNDEFINED (type))
     return true;
 
   wi::overflow_type ovf;
diff --git a/gcc/range-op.h b/gcc/range-op.h
index e415f87d7e6..3c69fdd2812 100644
--- a/gcc/range-op.h
+++ b/gcc/range-op.h
@@ -32,6 +32,18 @@  enum range_op_dispatch_type
   DISPATCH_OP1_OP2_RELATION
 };
 
+enum range_query_type
+{
+  // Take advantage of gimple's rules about undefined behavior.  This is
+  // usually the right choice when querying existing operations.
+  QUERY_WITH_GIMPLE_UB,
+
+  // The result of the operation must follow the rules of natural arithmetic.
+  // This is usually the right choice when querying whether we can create
+  // a new operation.
+  QUERY_NATURAL_ARITH
+};
+
 // This class is implemented for each kind of operator supported by
 // the range generator.  It serves various purposes.
 //
@@ -225,7 +237,8 @@  public:
 					  const frange &op2) const;
 
   virtual bool overflow_free_p (const irange &lh, const irange &rh,
-				relation_trio = TRIO_VARYING) const;
+				relation_trio = TRIO_VARYING,
+				range_query_type = QUERY_WITH_GIMPLE_UB) const;
 
   // Compatability check for operands.
   virtual bool operand_check_p (tree, tree, tree) const;
@@ -319,7 +332,10 @@  public:
 				  const vrange &op1,
 				  const vrange &op2) const;
   bool overflow_free_p (const vrange &lh, const vrange &rh,
-			relation_trio = TRIO_VARYING) const;
+			relation_trio = TRIO_VARYING,
+			range_query_type = QUERY_WITH_GIMPLE_UB) const;
+  bool fits_type_p (const irange &lh, const irange &rh,
+		    relation_trio = TRIO_VARYING) const;
   bool operand_check_p (tree, tree, tree) const;
 protected:
   unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
@@ -330,6 +346,17 @@  protected:
   range_operator *m_operator;
 };
 
+// Test whether the result of the operator fits within the type.
+// This follows the rules of natural arithmetic and so disallows
+// any form of overflow or wrapping.
+
+inline bool
+range_op_handler::fits_type_p (const irange &lh, const irange &rh,
+			       relation_trio trio) const
+{
+  return overflow_free_p (lh, rh, trio, QUERY_NATURAL_ARITH);
+}
+
 // Cast the range in R to TYPE if R supports TYPE.
 
 inline bool
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-7.c b/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-7.c
new file mode 100644
index 00000000000..8a33bbd30f0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-7.c
@@ -0,0 +1,21 @@ 
+/* { dg-options "-O2 -fdump-tree-optimized-raw" } */
+
+#define TEST_CMP(FN, OP)			\
+  int						\
+  FN (int x, int y)				\
+  {						\
+    if (x & 7)					\
+      __builtin_unreachable ();			\
+    x /= 4;					\
+    return x OP (int) (y & (~0U >> 3));		\
+  }
+
+TEST_CMP (f1, <)
+TEST_CMP (f2, <=)
+TEST_CMP (f3, ==)
+TEST_CMP (f4, !=)
+TEST_CMP (f5, >=)
+TEST_CMP (f6, >)
+
+/* { dg-final { scan-tree-dump-not {<[a-z]*_div_expr, } "optimized" } } */
+/* { dg-final { scan-tree-dump-not {<rshift_expr, } "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-8.c b/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-8.c
new file mode 100644
index 00000000000..0524995a72a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-8.c
@@ -0,0 +1,20 @@ 
+/* { dg-options "-O2 -fdump-tree-optimized-raw" } */
+
+#define TEST_CMP(FN, OP)			\
+  int						\
+  FN (int x, int y)				\
+  {						\
+    if (x & 7)					\
+      __builtin_unreachable ();			\
+    x /= 4;					\
+    return x OP (int) (y & (~0U >> 2));		\
+  }
+
+TEST_CMP (f1, <)
+TEST_CMP (f2, <=)
+TEST_CMP (f3, ==)
+TEST_CMP (f4, !=)
+TEST_CMP (f5, >=)
+TEST_CMP (f6, >)
+
+/* { dg-final { scan-tree-dump-times {<[a-z]*_div_expr, } 6 "optimized" } } */