When op1's range is [N, N + 1] and one of N or N + 1 is a power of
two, split a TRUNC_DIV_EXPR into two divisions by constants selected
by a compare:
op0 / op1 -> op1 == N ? op0 / N : op0 / (N + 1)
Each arm divides by a constant, so expansion strength-reduces it (a
shift on the power-of-two arm) and the divide instruction is avoided.
This grows code, so gate it on optimize_bb_for_speed_p.
Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}.
Ok for trunk?
PR middle-end/125708
gcc/ChangeLog:
* vr-values.cc
(simplify_using_ranges::simplify_div_or_mod_using_ranges):
Compute op1's upper bound for all codes and add the
near-power-of-two TRUNC_DIV_EXPR split, guarded on
optimize_bb_for_speed_p.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/pr125708-1.c: New test.
* gcc.target/i386/pr125708-2.c: New test.
---
gcc/testsuite/gcc.dg/tree-ssa/pr125708-1.c | 42 +++++++++++++++++++++
gcc/testsuite/gcc.target/i386/pr125708-2.c | 31 +++++++++++++++
gcc/vr-values.cc | 44 +++++++++++++++++++---
3 files changed, 112 insertions(+), 5 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr125708-1.c
create mode 100644 gcc/testsuite/gcc.target/i386/pr125708-2.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr125708-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr125708-1.c
new file mode 100644
index 00000000000..56b4f8519d5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr125708-1.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#include <stdbool.h>
+
+/* op1 in [1, 2]: the divisor==1 arm degenerates to op0. */
+int
+foo (int a, bool b)
+{
+ return a / (2 - b);
+}
+
+/* op1 in [4, 5]: power of two is the lower bound. */
+int
+foo1 (int a, bool b)
+{
+ return a / (4 + b);
+}
+
+/* op1 in [7, 8]: power of two is the upper bound. */
+int
+foo2 (int a, bool b)
+{
+ return a / (8 - b);
+}
+
+/* Unsigned dividend. */
+unsigned
+foo3 (unsigned a, bool b)
+{
+ return a / (4 + b);
+}
+
+/* Negative dividend. */
+int
+foo4 (int a, bool b)
+{
+ return -a / (8 - b);
+}
+
+/* No division by an SSA name should survive. */
+/* { dg-final { scan-tree-dump-not " / _" "optimized" } } */
diff --git a/gcc/testsuite/gcc.target/i386/pr125708-2.c
b/gcc/testsuite/gcc.target/i386/pr125708-2.c
new file mode 100644
index 00000000000..853543695ba
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr125708-2.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+#include <stdbool.h>
+
+int
+foo (int a, bool b)
+{
+ return a / (2 - b);
+}
+
+int
+foo1 (int a, bool b)
+{
+ return a / (4 + b);
+}
+
+int
+foo2 (int a, bool b)
+{
+ return a / (8 - b);
+}
+
+unsigned
+foo3 (unsigned a, bool b)
+{
+ return a / (4 + b);
+}
+
+/* { dg-final { scan-assembler-not "idiv" } } */
+/* { dg-final { scan-assembler-not "\tdiv" } } */
diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
index f0d9a71bd40..f27cf01e485 100644
--- a/gcc/vr-values.cc
+++ b/gcc/vr-values.cc
@@ -594,7 +594,8 @@ simplify_using_ranges::simplify_truth_ops_using_ranges
constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
optimize it into just op0 if op0's range is known to be a subset of
[-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
- modulo. */
+ modulo. Also optimize TRUNC_DIV_EXPR op0 / op1 when op1 is known to be
+ N or N + 1 and one of them is a power of two. */
bool
simplify_using_ranges::simplify_div_or_mod_using_ranges
@@ -606,7 +607,7 @@ simplify_using_ranges::simplify_div_or_mod_using_ranges
tree op0 = gimple_assign_rhs1 (stmt);
tree op1 = gimple_assign_rhs2 (stmt);
tree op0min = NULL_TREE, op0max = NULL_TREE;
- tree op1min = op1;
+ tree op1min = op1, op1max = NULL_TREE;
int_range_max vr;
if (TREE_CODE (op0) == INTEGER_CST)
@@ -626,15 +627,19 @@ simplify_using_ranges::simplify_div_or_mod_using_ranges
}
}
- if (rhs_code == TRUNC_MOD_EXPR
- && TREE_CODE (op1) == SSA_NAME)
+ if (TREE_CODE (op1) == SSA_NAME)
{
int_range_max vr1;
if (!query->range_of_expr (vr1, op1, stmt))
vr1.set_varying (TREE_TYPE (op1));
if (!vr1.varying_p () && !vr1.undefined_p ())
- op1min = wide_int_to_tree (vr1.type (), vr1.lower_bound ());
+ {
+ op1min = wide_int_to_tree (vr1.type (), vr1.lower_bound ());
+ if (rhs_code == TRUNC_DIV_EXPR)
+ op1max = wide_int_to_tree (vr1.type (), vr1.upper_bound ());
+ }
}
+
if (rhs_code == TRUNC_MOD_EXPR
&& TREE_CODE (op1min) == INTEGER_CST
&& tree_int_cst_sgn (op1min) == 1
@@ -653,6 +658,35 @@ simplify_using_ranges::simplify_div_or_mod_using_ranges
}
}
+ if (rhs_code == TRUNC_DIV_EXPR
+ && TREE_CODE (op1min) == INTEGER_CST
+ && op1max
+ && TREE_CODE (op1max) == INTEGER_CST
+ && tree_int_cst_sgn (op1min) == 1
+ && wi::to_wide (op1max) == wi::to_wide (op1min) + 1
+ && (integer_pow2p (op1min) || integer_pow2p (op1max))
+ && optimize_bb_for_speed_p (gimple_bb (stmt)))
+ {
+ /* op1 == N ? op0 / N : op0 / (N + 1). Both arms divide by a
+ constant, so expansion avoids the divide instruction. */
+ location_t loc = gimple_location (stmt);
+ tree div_min = (integer_onep (op1min)
+ ? op0
+ : gimple_build (gsi, true, GSI_SAME_STMT, loc,
+ TRUNC_DIV_EXPR, TREE_TYPE (op0),
+ op0, op1min));
+ tree div_max = gimple_build (gsi, true, GSI_SAME_STMT, loc,
+ TRUNC_DIV_EXPR, TREE_TYPE (op0),
+ op0, op1max);
+ tree cond = gimple_build (gsi, true, GSI_SAME_STMT, loc,
+ EQ_EXPR, boolean_type_node, op1, op1min);
+
+ gimple_assign_set_rhs_with_ops (gsi, COND_EXPR, cond, div_min, div_max);
+ update_stmt (gsi_stmt (*gsi));
+ fold_stmt (gsi, follow_single_use_edges);
+ return true;
+ }
+
if (TREE_CODE (op0) != SSA_NAME)
return false;
--
2.34.1
