Update in V2:
Move the optimization to gimple->RTL expansion phase, query costs
before optimization.
Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}.
Ok for trunk?
When range info proves that a TRUNC_DIV_EXPR divisor is either N or N
+ 1, and one value is a positive power of two, expand the operation as
two constant divisions selected by a conditional move.
Only do this for speed, when conditional moves are available. Cost
the split sequence against a plain DIV/UDIV and keep the original
expansion unless the split is cheaper.
PR middle-end/125708
gcc/ChangeLog:
* expr.cc: Include gimple-range.h.
(near_pow2_divisor_range_p): New function.
(expand_expr_divmod): Split eligible TRUNC_DIV_EXPRs into two
constant divisions selected by a conditional move.
gcc/testsuite/ChangeLog:
* gcc.c-torture/execute/pr125708-1.c: New test.
* gcc.target/i386/pr125708-2.c: New test.
---
gcc/expr.cc | 65 ++++++++++++++++++-
.../gcc.c-torture/execute/pr125708-1.c | 58 +++++++++++++++++
gcc/testsuite/gcc.target/i386/pr125708-2.c | 37 +++++++++++
3 files changed, 159 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr125708-1.c
create mode 100644 gcc/testsuite/gcc.target/i386/pr125708-2.c
diff --git a/gcc/expr.cc b/gcc/expr.cc
index de73215ccc6..438805bc01b 100644
--- a/gcc/expr.cc
+++ b/gcc/expr.cc
@@ -66,6 +66,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-pretty-print.h"
#include "flags.h"
#include "internal-fn.h"
+#include "gimple-range.h"
/* If this is nonzero, we do not bother generating VOLATILE
@@ -9764,6 +9765,28 @@ expand_misaligned_mem_ref (rtx temp, machine_mode mode,
int unsignedp,
return temp;
}
+/* Return true if OP is known to be either LOWER or LOWER + 1, with one
+ value a positive power of two. */
+
+static bool
+near_pow2_divisor_range_p (tree op, wide_int &lower)
+{
+ if (TREE_CODE (op) != SSA_NAME)
+ return false;
+
+ int_range_max range;
+ range_query *query = get_range_query (cfun);
+ if (!query->range_of_expr (range, op, currently_expanding_gimple_stmt)
+ || range.num_pairs () != 1)
+ return false;
+
+ lower = range.lower_bound ();
+ wide_int upper = lower + 1;
+ return (range.upper_bound () == upper
+ && wi::gt_p (lower, 0, TYPE_SIGN (TREE_TYPE (op)))
+ && (wi::popcount (lower) == 1 || wi::popcount (upper) == 1));
+}
+
/* Helper function of expand_expr_2, expand a division or modulo.
op0 and op1 should be already expanded treeop0 and treeop1, using
expand_operands. */
@@ -9774,6 +9797,47 @@ expand_expr_divmod (tree_code code, machine_mode mode,
tree treeop0,
{
bool mod_p = (code == TRUNC_MOD_EXPR || code == FLOOR_MOD_EXPR
|| code == CEIL_MOD_EXPR || code == ROUND_MOD_EXPR);
+ bool speed_p = optimize_insn_for_speed_p ();
+
+ scalar_int_mode int_mode;
+ wide_int lower;
+ /* Split x / y when y is one of two neighboring constants and the target can
+ select between the constant divisions cheaply. */
+ if (code == TRUNC_DIV_EXPR
+ && is_a <scalar_int_mode> (mode, &int_mode)
+ && speed_p
+ && can_conditionally_move_p (int_mode)
+ && near_pow2_divisor_range_p (treeop1, lower))
+ {
+ signop sgn = TYPE_SIGN (TREE_TYPE (treeop1));
+ unsigned int prec = GET_MODE_PRECISION (int_mode);
+ wide_int upper = lower + 1;
+ rtx op_lower
+ = immed_wide_int_const (wide_int::from (lower, prec, sgn), int_mode);
+ rtx op_upper
+ = immed_wide_int_const (wide_int::from (upper, prec, sgn), int_mode);
+
+ do_pending_stack_adjust ();
+ start_sequence ();
+ rtx q_lower = expand_divmod (0, TRUNC_DIV_EXPR, mode, op0, op_lower,
+ NULL_RTX, unsignedp);
+ rtx q_upper = expand_divmod (0, TRUNC_DIV_EXPR, mode, op0, op_upper,
+ NULL_RTX, unsignedp);
+ rtx split_ret
+ = emit_conditional_move (target, { EQ, op1, op_lower, int_mode },
+ q_lower, q_upper, int_mode, unsignedp);
+ rtx_insn *split_insns = end_sequence ();
+
+ /* Cost the unsplit form as a single DIV/UDIV. */
+ rtx div_rtx = gen_rtx_fmt_ee (unsignedp ? UDIV : DIV, int_mode, op0,
op1);
+ unsigned div_cost = set_src_cost (div_rtx, int_mode, speed_p);
+ if (split_ret && seq_cost (split_insns, speed_p) < div_cost)
+ {
+ emit_insn (split_insns);
+ return split_ret;
+ }
+ }
+
if (SCALAR_INT_MODE_P (mode)
&& optimize >= 2
&& get_range_pos_neg (treeop0, currently_expanding_gimple_stmt) == 1
@@ -9782,7 +9846,6 @@ expand_expr_divmod (tree_code code, machine_mode mode,
tree treeop0,
/* If both arguments are known to be positive when interpreted
as signed, we can expand it as both signed and unsigned
division or modulo. Choose the cheaper sequence in that case. */
- bool speed_p = optimize_insn_for_speed_p ();
do_pending_stack_adjust ();
start_sequence ();
rtx uns_ret = expand_divmod (mod_p, code, mode, op0, op1, target, 1);
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr125708-1.c
b/gcc/testsuite/gcc.c-torture/execute/pr125708-1.c
new file mode 100644
index 00000000000..a5f372fee98
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr125708-1.c
@@ -0,0 +1,58 @@
+/* PR middle-end/125708 */
+
+__attribute__((noipa)) int
+foo (int a, _Bool b)
+{
+ return a / (2 - b);
+}
+
+__attribute__((noipa)) int
+foo1 (int a, _Bool b)
+{
+ return a / (4 + b);
+}
+
+__attribute__((noipa)) int
+foo2 (int a, _Bool b)
+{
+ return a / (8 - b);
+}
+
+__attribute__((noipa)) unsigned
+foo3 (unsigned a, _Bool b)
+{
+ return a / (4 + b);
+}
+
+__attribute__((noipa)) int
+foo4 (int a, _Bool b)
+{
+ return a / ((1 << 20) - b);
+}
+
+int
+main (void)
+{
+ static const int vals[] =
+ { 0, 1, 2, 3, 7, 8, 15, 16, 100, -1, -7, -8, -100,
+ 1000000, -1000000, __INT_MAX__, -__INT_MAX__ - 1 };
+
+ for (unsigned i = 0; i < sizeof (vals) / sizeof (vals[0]); i++)
+ {
+ int a = vals[i];
+ for (int b = 0; b <= 1; b++)
+ {
+ if (foo (a, b) != a / (2 - b))
+ __builtin_abort ();
+ if (foo1 (a, b) != a / (4 + b))
+ __builtin_abort ();
+ if (foo2 (a, b) != a / (8 - b))
+ __builtin_abort ();
+ if (foo3 ((unsigned) a, b) != (unsigned) a / (4u + b))
+ __builtin_abort ();
+ if (foo4 (a, b) != a / ((1 << 20) - b))
+ __builtin_abort ();
+ }
+ }
+ return 0;
+}
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..44b7c8e8c81
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/pr125708-2.c
@@ -0,0 +1,37 @@
+/* PR middle-end/125708 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -march=x86-64" } */
+
+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);
+}
+
+int
+foo4 (int a, _Bool b)
+{
+ return a / ((1 << 20) - b);
+}
+
+/* { dg-final { scan-assembler-not "idiv" } } */
+/* { dg-final { scan-assembler-not "\tdiv" } } */
+/* { dg-final { scan-assembler "cmov" } } */
--
2.34.1
