[PATCH v2 0/3] Optimize 32-bit unsigned constant division for 64-bit targets

[herumi@nifty.com]

From: MITSUNARI Shigeo <herumi@nifty.com>

Compiler optimization for constant division of `uint32_t` variables (e.g.,
`x / 7`) is based on the Granlund-Montgomery (GM) method [1].
When the magic multiplier requires 33 bits (`mh != 0`), the GM method uses a
sub/shift/add sequence designed for 32-bit registers.
This patch pre-shifts the 33-bit magic constant into a 64-bit value and uses a
single 64x64->128-bit high-part multiply to obtain the quotient directly,
eliminating the post-multiply add/sub/shift sequence.

On x86_64, `x / 7` is reduced from 7 instructions to 4 (or 3 with BMI2).
A benchmark on Xeon w9-3495X shows a 1.67x speedup.

Changes in v2:
- Rebased on current master (post GCC 16 release).

Affected divisors: 32-bit unsigned constant divisors where `mh != 0`
(7, 19, 21, 27, 31, 35, 37, 107, etc.)
Architectures: 64-bit or wider targets with 64x64->128-bit high-part multiply
(x86_64, AArch64, RISC-V64, etc.)
patch2, patch3: x86_64 BMI2 targets only.

Testing: Ran `make check-gcc RUNTESTFLAGS="i386.exp"` before and after applying
the patches. The results are identical.

Note: The same optimization technique has been applied to LLVM and merged into
llvm:main at https://github.com/llvm/llvm-project/pull/181288.

References:
[1] T. Granlund, P. L. Montgomery, "Division by Invariant Integers using
    Multiplication", PLDI 1994
[2] https://arxiv.org/abs/2604.07902

MITSUNARI Shigeo (3):
  expmed: Optimize 32-bit unsigned division by constants on 64-bit
    targets
  i386: Add BMI2 MULX pattern for highpart-only multiplication
  i386: Add peephole2 to convert highpart mul to mulx

 gcc/config/i386/i386.md | 32 +++++++++++++++
 gcc/expmed.cc           | 86 +++++++++++++++++++++++++++++------------
 2 files changed, 93 insertions(+), 25 deletions(-)

-- 
2.43.0