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 --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" } } */
