On 5/2/2026 11:34 PM, [email protected] wrote:
> From: MITSUNARI Shigeo <[email protected]>
>
> For 32-bit unsigned integer division by constants that require 33-bit
> magic multipliers (mh != 0, IsAdd case), use a pre-shifted 64-bit magic
> constant and a single 64-bit high-part multiply instead of the traditional
> sub/shift/add sequence.
>
> The 33-bit magic constant (2^32 + ml) is pre-shifted by (32 - post_shift)
> bits, allowing the quotient to be obtained directly from the upper 64 bits
> of a 64x64 multiplication, then truncated to 32 bits.
>
> 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_divmod): For 32-bit unsigned division with
> 33-bit magic on 64-bit targets, use pre-shifted 64-bit multiply.
> ---
> gcc/expmed.cc | 86 ++++++++++++++++++++++++++++++++++++---------------
> 1 file changed, 61 insertions(+), 25 deletions(-)
>
> diff --git a/gcc/expmed.cc b/gcc/expmed.cc
> index d57ea78d6b1..443ac09caeb 100644
> --- a/gcc/expmed.cc
> +++ b/gcc/expmed.cc
> @@ -4523,31 +4523,67 @@ expand_divmod (int rem_flag, enum tree_code code,
> machine_mode mode,
>
> + bool did_64bit_opt = false;
> +
> + /* For 32-bit unsigned division on 64-bit targets,
> + pre-shift the 33-bit magic constant (2^32 + ml)
> + into a 64-bit value and use a single 64-bit
> + high-part multiply instead of the sub/shift/add
> + sequence.
> + Pre-shift by (32 - post_shift) so that the high
> + 64 bits of (x64 * magic) give the quotient
> + directly.
> + Note: mh!=0 implies pre_shift==0. */
> + if (size == 32 && post_shift >= 1)
So rather than a magic "32" constant is there something better we can
test? If I understand everything correctly, this would work any time we
have a high part multiply irrespective of the underlying types. One
could imagine an 8 bit target with a mulh insn that gives the upper 8
bits of the 16 bit multiply result.
Rather than calling this "did_64bit_opt", perhaps "did_mulh_opt" or
something else that is agnostic of the actual sizes.
> + {
> + scalar_int_mode wide_mode
> + = GET_MODE_WIDER_MODE (int_mode).require ();
> + unsigned HOST_WIDE_INT magic
> + = (ml + (HOST_WIDE_INT_1U << 32))
> + << (32 - post_shift);
Isn't this going to fail on a host where HOST_WIDE_INT is just 32 bits?
I believe that's the case for windows. You can't shift a 32 bit object
by 32 bit positions.
What would happen if we didn't find a wider mode? Isn't that going to
fail poorly (internal error)? What happens on targets that do not have
a high part multiply?
I'd really like to see a testcase included as well. I don't mind if
it's specific to a particular target like x86_64, I just want to have
some degree of coverage on a commonly tested target.
I think much of this is sound, it's really more a matter of getting
details nailed down.
On a non-technical note, you need to explicitly contribute this under
the DCO terms or get a copyright assignment on file with the FSF before
we can include anything.
jeff
