On 6/18/2026 6:32 PM, [email protected] wrote:
> 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;
So the LLMs both flagged the potential for post_shift to be large enough
to cause problems. So for example if post_shift > size, then we end up
with a negative shift count when computing MAGIC. That may not be
possible and I'm not as familiar with this code as perhaps I should be,
so if you chase down if this is a real issue or not and take appropriate
action, it'd be appreciated. And just to be clear if size can never be
greater than post_shift, then there's nothing to do for this "issue".
It's not a correctness issue, but some targets to have highpart
multipliers so there may be ways to handle cases where WIDE_MODE is
wider than a word. But that's (IMHO) something we could tackle in a
follow-up if we were so inclined.
> +
> + /* 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);
Closely related, one flagged this as potentially overflowing depending
on size, so we need to look at that more carefully.
> @@ -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:;
Rather than a goto, can we
if (quotient == NULL_RTX)
{
all the code your patch skipped
}
THat does mean you'd need to reindent that block of code, but that's
better than a goto. It'll make review harder, but we've worked through
all the issues I believe so the final review should be a rubber stamp at
this point.
Otherwise it looks good to me.
Jeff
