[LLVM 2026] Beyond the Legacy: Speeding Up 32-bit Division on 64-bit Targets

TL;DR

Modern compilers like GCC and Clang have long relied on the Granlund-Montgomery (GM) method to replace slow division instructions with faster multiplications. However, for a significant portion of divisors, the generated code remains stuck in a "32-bit mindset," using complex instruction sequences to prevent overflows that modern 64-bit registers can handle with ease. This paper proposes a simplified 64-bit-native approach that reduces the operation to a single multiplication, delivering nearly 2x speedups on Apple M4 and Intel Sapphire Rapids.

The Problem: The 32-bit "Ghost" in 64-bit Machines

Integer division is notoriously expensive in terms of CPU cycles. To optimize this, compilers use "magic constants"—precomputed numbers that allow $x/d$ to be calculated via $(x\cdot c)\gg a$.

However, for about 23% of constant divisors (like 7, 19, or 107), the magic constant $c$ requires 33 bits. To avoid overflowing a 32-bit result during intermediate steps, current compilers generate a "shift-add-shift" dance:

1. Multiply $x$ by the lower 32 bits of $c$.
2. Perform a subtraction and a right shift.
3. Add the results back and shift again.

While this was necessary for 32-bit CPUs, it is a bottleneck on modern 64-bit hardware where we have plenty of register "headroom."

The Insight: Native 64-bit Scaling

The authors realized that if we are running on a 64-bit target, we can treat the 32-bit dividend $x$ as a 64-bit value and scale the magic constant $c$ such that the result resides purely in the upper bits of a 128-bit product.

Specifically, the operation is transformed to: $(x\cdot c)//2^a=(x\cdot (2^{64-a}\cdot c))//2^{64}$

By pre-calculating $t=c\ll (64-a)$, the division $x//d$ simply becomes the high 64 bits of the product of $x$ and $t$.

Methodology & Architecture

The beauty of this method lies in its simplicity. Instead of the multi-line assembly sequence seen in Listing 2 of the paper, the proposed method utilizes the high-magnitude multiplication instructions available in modern ISAs.

• On x86-64 (BMI2): It uses the mulx instruction, which computes a 128-bit product and stores the high/low parts in separate registers.
• On AArch64 (Apple M4): It uses umulh (Unsigned Multiply High), which directly returns the top 64 bits of the product.

Experimental Results: Real-World Gains

The authors implemented this in LLVM and tested it against a sequence of divisions by 7, 19, and 107.

As shown in the assembly comparison (Listing 7 vs 8 in the paper), the loop body shrinks dramatically. The "sequence" of shifts and adds is replaced by a high-throughput multiplication, allowing the CPU's out-of-order execution engine to process iterations much faster.

Critical Analysis & Conclusion

The core contribution here is not a new mathematical theory, but a practical engineering refinement. It identifies a "performance debt" in compiler backends—where code generation strategies failed to evolve alongside register width.

Limitations:

• This optimization is only applicable when the target is 64-bit; 32-bit embedded systems must still use the legacy GM method.
• It specifically targets the "33-bit constant" case; the ~77% of cases where $c$ fits in 32 bits already use a single multiply-shift.

Takeaway: This work has already been merged into llvm:main. For developers using Clang or eventually GCC, 32-bit unsigned division—a fundamental building block of many algorithms—just got nearly twice as fast on modern hardware. It serves as a reminder that even "solved" problems in computer science often have room for optimization when hardware assumptions change.