From: MITSUNARI Shigeo <[email protected]>
For 32-bit unsigned integer division by constants that require a wider
magic multiplier (mh != 0), use a pre-shifted magic constant in a mode
twice as wide and a single high-part multiply instead of the traditional
sub/shift/add sequence, when that is no more expensive.
The (size+1)-bit magic constant (2^size + ml) is pre-shifted by
(size - post_shift) bits so that the quotient is obtained directly from
the high part of the widened multiply, then truncated back to the
original mode. The widened sequence is only used when its cost, measured
with seq_cost, does not exceed that of the classic sub/shift/add sequence.
This reduces the instruction count for divisions like x/7 from 7
instructions to 4 on x86_64.
Before (x / 7):
movl %edi, %eax
imulq $613566757, %rax, %rax
shrq $32, %rax
subl %eax, %edi
shrl %edi
addl %edi, %eax
shrl $2, %eax
After:
movabsq $2635249153617166336, %rcx
movl %edi, %eax
mulq %rcx
movl %edx, %eax
gcc/ChangeLog:
* expmed.cc (expand_wide_mulh_udiv): New function.
(expand_divmod): Use it for unsigned constant division needing a
wide multiplier on 64-bit targets, when no more expensive than the
sub/shift/add sequence.
gcc/testsuite/ChangeLog:
* gcc.target/i386/mulq-highpart.c: New test.
Signed-off-by: MITSUNARI Shigeo <[email protected]>
---
gcc/expmed.cc | 66 +++++++++++++++++++
gcc/testsuite/gcc.target/i386/mulq-highpart.c | 22 +++++++
2 files changed, 88 insertions(+)
create mode 100644 gcc/testsuite/gcc.target/i386/mulq-highpart.c
diff --git a/gcc/expmed.cc b/gcc/expmed.cc
index d57ea78d6b1..84a7a886eca 100644
--- a/gcc/expmed.cc
+++ b/gcc/expmed.cc
@@ -4258,6 +4258,61 @@ expand_sdiv_pow2 (scalar_int_mode mode, rtx op0,
HOST_WIDE_INT d)
(x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
*/
+/* Helper for expand_divmod's unsigned constant division. For OP0 in
+ INT_MODE divided by a constant needing a (SIZE+1)-bit multiplier ML
+ with right shift POST_SHIFT (the mh != 0 case), try to obtain
+ the quotient from the high part of a single multiply in a mode twice
+ as wide as INT_MODE. Return the quotient in INT_MODE, having emitted
+ the insns, or NULL_RTX when the transformation is unavailable or not
+ cheaper than the classic sub/shift/add sequence. EXTRA_COST is the
+ cost of that sequence's follow-up ops, MAX_COST bounds the multiply
+ and SPEED selects the cost model.
+
+ The magic constant occupies at most 2*SIZE bits and so must fit in a
+ HOST_WIDE_INT (always 64 bits today; checked below). A wider INT_MODE
+ such as DImode -- which would need a 128-bit magic and a single-word
+ high-part multiply in a 2x-wide mode that common targets lack -- is
+ therefore excluded. */
+
+static rtx
+expand_wide_mulh_udiv (scalar_int_mode int_mode, rtx op0,
+ unsigned HOST_WIDE_INT ml, int size, int post_shift,
+ int extra_cost, int max_cost, bool speed)
+{
+ scalar_int_mode wide_mode;
+
+ /* We need POST_SHIFT >= 1, a wider integer mode that still fits in a
+ word, and the pre-shifted magic constant to fit in a HOST_WIDE_INT. */
+ if (post_shift < 1
+ || !GET_MODE_2XWIDER_MODE (int_mode).exists (&wide_mode)
+ || GET_MODE_BITSIZE (wide_mode) > BITS_PER_WORD
+ || GET_MODE_BITSIZE (wide_mode) > HOST_BITS_PER_WIDE_INT)
+ return NULL_RTX;
+
+ /* Pre-shift the (SIZE+1)-bit magic constant (2^SIZE + ml) by
+ (SIZE - POST_SHIFT) so that the quotient ends up in the high part
+ of the widened product. */
+ unsigned HOST_WIDE_INT magic
+ = ((HOST_WIDE_INT_1U << size) + ml) << (size - post_shift);
+
+ start_sequence ();
+ rtx x_wide = convert_to_mode (wide_mode, op0, 1);
+ rtx hi = expmed_mult_highpart (wide_mode, x_wide,
+ gen_int_mode (magic, wide_mode),
+ NULL_RTX, 1, max_cost);
+ rtx quotient = hi ? convert_to_mode (int_mode, hi, 1) : NULL_RTX;
+ rtx_insn *insns = end_sequence ();
+
+ /* Use the widened multiply only when it is no more expensive than
+ the classic sub/shift/add sequence. */
+ unsigned classic_cost = mul_highpart_cost (speed, int_mode) + extra_cost;
+ if (quotient == NULL_RTX || seq_cost (insns, speed) > classic_cost)
+ return NULL_RTX;
+
+ emit_insn (insns);
+ return quotient;
+}
+
rtx
expand_divmod (int rem_flag, enum tree_code code, machine_mode mode,
rtx op0, rtx op1, rtx target, int unsignedp,
@@ -4532,6 +4587,16 @@ expand_divmod (int rem_flag, enum tree_code code,
machine_mode mode,
= (shift_cost (speed, int_mode, post_shift - 1)
+ shift_cost (speed, int_mode, 1)
+ 2 * add_cost (speed, int_mode));
+
+ /* Try a single widened multiply first; use it when
+ it is no more expensive. */
+ quotient
+ = expand_wide_mulh_udiv (int_mode, op0, ml, size,
+ post_shift, extra_cost,
+ max_cost, speed);
+ if (quotient != NULL_RTX)
+ goto mh_done;
+
t1 = expmed_mult_highpart
(int_mode, op0, gen_int_mode (ml, int_mode),
NULL_RTX, 1, max_cost - extra_cost);
@@ -4548,6 +4613,7 @@ expand_divmod (int rem_flag, enum tree_code code,
machine_mode mode,
quotient = expand_shift
(RSHIFT_EXPR, int_mode, t4,
post_shift - 1, tquotient, 1);
+ mh_done:;
}
else
{
diff --git a/gcc/testsuite/gcc.target/i386/mulq-highpart.c
b/gcc/testsuite/gcc.target/i386/mulq-highpart.c
new file mode 100644
index 00000000000..56728cd5b7c
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/mulq-highpart.c
@@ -0,0 +1,22 @@
+/* { dg-do compile { target { ! ia32 } } } */
+/* { dg-options "-O2 -mno-bmi2" } */
+/* { dg-final { check-function-bodies "**" "" "" { target *-*-linux* *-*-gnu*
} } } */
+
+/* %rax, %rdx and %edi are fixed by the ISA (mulq) and the ABI (first
+ argument), but the register holding the magic constant is chosen by
+ the register allocator, so match it generically. */
+/*
+**div7:
+** movabsq \$2635249153617166336, (%r[a-z0-9]+)
+** movl %edi, %eax
+** mulq \1
+** movl %edx, %eax
+** ret
+**...
+*/
+
+unsigned int
+div7 (unsigned int x)
+{
+ return x / 7;
+}
\ No newline at end of file
--
2.43.0
