Main things I’d flag: - **Likely wrong for `-Os` / cost modeling** - The new wide-mulh path ignores the existing `extra_cost` accounting and calls: - `expmed_mult_highpart (..., max_cost);` - The old path subtracts the cost of the follow-up ops from `max_cost`. - So this can choose the transformation even when the widened sequence is not profitable or exceeds the intended cost budget. At minimum it needs comparable costing, and probably a comparison vs the old `mh != 0` sequence.
On 6/10/2026 9:25 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/testsuite/ChangeLog: > > * gcc.target/i386/mulq-highpart.c: New test. > > Signed-off-by: MITSUNARI Shigeo <[email protected]> > --- > gcc/expmed.cc | 93 +++++++++++++------ > gcc/testsuite/gcc.target/i386/mulq-highpart.c | 19 ++++ > 2 files changed, 85 insertions(+), 27 deletions(-) > create mode 100644 gcc/testsuite/gcc.target/i386/mulq-highpart.c > > diff --git a/gcc/expmed.cc b/gcc/expmed.cc > index d57ea78d6b1..53185050258 100644 > --- a/gcc/expmed.cc > +++ b/gcc/expmed.cc > @@ -4521,33 +4521,72 @@ expand_divmod (int rem_flag, enum tree_code code, > machine_mode mode, > else > pre_shift = 0; > > - if (mh != 0) > - { > - rtx t1, t2, t3, t4; > - > - if (post_shift - 1 >= BITS_PER_WORD) > - goto fail1; > - > - extra_cost > - = (shift_cost (speed, int_mode, post_shift - 1) > - + shift_cost (speed, int_mode, 1) > - + 2 * add_cost (speed, int_mode)); > - t1 = expmed_mult_highpart > - (int_mode, op0, gen_int_mode (ml, int_mode), > - NULL_RTX, 1, max_cost - extra_cost); > - if (t1 == 0) > - goto fail1; > - t2 = force_operand (gen_rtx_MINUS (int_mode, > - op0, t1), > - NULL_RTX); > - t3 = expand_shift (RSHIFT_EXPR, int_mode, > - t2, 1, NULL_RTX, 1); > - t4 = force_operand (gen_rtx_PLUS (int_mode, > - t1, t3), > - NULL_RTX); > - quotient = expand_shift > - (RSHIFT_EXPR, int_mode, t4, > - post_shift - 1, tquotient, 1); > + if (mh != 0) > + { > + bool did_wide_mulh_path = false; > + > + /* For 32-bit unsigned division, if converting to a > wider > + mode lets us obtain the high part of the product > + directly, pre-shift the 33-bit magic constant > + (2^32 + ml) into that wider mode and use the high > + part of the widened multiply instead of the > + sub/shift/add sequence. > + Pre-shift by (32 - post_shift) so that the high > + bits of (x64 * magic) give the quotient directly. > + Note: mh!=0 implies pre_shift==0. */ Looks like formatting is off here. Most likely inconsistent tabs vs spaces. For better or worse, GCC's convention is when you have 8 spaces, you should instead use a tab. The fact that the bool variable declaration and the comment immediately afterwards should be at the same indention level, but are showing up differently here is a good indication that there's a tab vs 8 spaces inconsistency. > + if (size == 32 && post_shift >= 1) We're still using magic numbers. 32 is almost certainly related to a specific mode's bitsize. > + start_sequence (); > + rtx x64 = convert_to_mode (wide_mode, op0, > 1); > + rtx hi = expmed_mult_highpart (wide_mode, > x64, > + gen_int_mode (magic, wide_mode), > + NULL_RTX, 1, max_cost); > + rtx_insn *insns = end_sequence (); > + if (hi != NULL_RTX) > + { > + emit_insn (insns); > + quotient = gen_lowpart (int_mode, hi); Should this be a conversion via convert_modes rather than calling gen_lowpart? What about costing, do you need to verify the cost of the widened multiply is lower than the cost of the other sequence? > 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..133c9b35d57 > --- /dev/null > +++ b/gcc/testsuite/gcc.target/i386/mulq-highpart.c > @@ -0,0 +1,19 @@ > +/* { dg-do compile { target { ! ia32 } } } */ > +/* { dg-options "-O2 -mno-bmi2" } */ > +/* { dg-final { check-function-bodies "**" "" "" { target *-*-linux* > *-*-gnu* } } } */ > + > +/* > +**div7: > +** movabsq \$2635249153617166336, %rcx > +** movl %edi, %eax > +** mulq %rcx > +** movl %edx, %eax > +** ret My x86 is getting rusty, but are these register selections mandated by abi+isa? I suspect at least the %rcx holding the constant is not required to be %ecx. Point being if the register used is not mandated by the ABI or the ISA, then we should use a more generic regexp to match the register. So for example on riscv, there are "a", "t" and "x" registers, so we usually have a regexp that matches all three types of general purpose register along with any subsequent number. That way if register allocation changes the test still passes. Often we don't care about the precise register selection, so embedding whatever the compiler selected is neither necessary nor wise (since it changes, thus making a maintenance burden of false positives). > +**... > +*/ > + > +unsigned int > +div7 (unsigned int x) > +{ > + return x / 7; > +} > \ No newline at end of file
