Optimize 32-bit unsigned division by constants on 64-bit targets.
New expansion strategy for constant division on 64-bit targets reduces instruction count.
GCC now employs a new strategy for 32-bit unsigned integer division by constants on 64-bit targets when the division requires a wide magic multiplier. This method uses a pre-shifted magic constant in a doubled-width mode, enabling a single high-part multiply operation. The compiler selects this approach only when its instruction count is comparable to or better than the traditional sub/shift/add sequence, reducing instructions from 7 to 4 for divisions like x/7 on x86_64.
In Details
The expand_divmod function in expmed.cc now calls expand_wide_mulh_udiv for 32-bit unsigned constant division on 64-bit targets where the magic multiplier mh is non-zero. This new function constructs a (size+1)-bit magic constant pre-shifted by (size - post_shift) bits. It then performs a widened multiply and truncates the result, which is then used to compute the quotient directly from the high part. This sequence is enabled only if seq_cost indicates it's not more expensive than the classic approach.
- magic multiplier
- A precomputed constant used in optimized division algorithms. It's often derived from the divisor and can involve large numbers, sometimes requiring more bits than the dividend.
- high-part multiply
- A multiplication operation where only the most significant portion of the result is relevant or used. This is often employed in division algorithms to derive the quotient.
- seq_cost
- An internal cost model within GCC used to estimate the performance impact (e.g., instruction count, latency) of different code generation sequences. It helps the compiler choose the most efficient option.