On Fri, 5 Jun 2026, Jeffrey Law wrote: > > 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.
HOST_WIDE_INT is always 64bit nowadays, but if you need a 64bit entity use [u]int64_t. HOST_WIDE_INT should be reserved to the case where our internal data structures would expose those. > > 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 -- Richard Biener <[email protected]> SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Jochen Jaser, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
