Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets Mitsunari Shigeo, Hoshino Takashi Abstract Granlund and Montgomery proposed an optimization method for unsigned integer division by constants [ 3 ] . Their method (called the GM method in this paper) was further improved in part by works such as [ 1 ] and [ 7 ] , and is now adopted by major compilers including GCC, Clang, Microsoft Compiler, and Apple Clang. However, for example, for x/7, the generated code is designed for 32-bit CPUs and therefore does not fully exploit 64-bit capabilities. This paper proposes an optimization method for 32-bit unsigned division by constants targeting 64-bit CPUs. We implemented patches for LLVM/GCC and achieved speedups of 1.67x on Intel Xeon w9-3495X (Sapphire Rapids) and 1.98x on Apple M4 (Apple M-series SoC) in the microbenchmark described later. The LLVM patch has already been merged into llvm:main [ 5 ] , demonstrating the practical applicability of the proposed method. Keywords: optimization of division by constants, compiler 1 Notation We use the following notation. Let \mathbb{Z} be the set of integers. For a,b\in\mathbb{Z} , define [a,b]:=\Set{c\in\mathbb{Z}\mid a\leq c\leq b} . For a real number x , define \lfloor x\rfloor:=\max\Set{y\in\mathbb{Z}\mid y\leq x} and \lceil x\rceil:=\min\Set{y\in\mathbb{Z}\mid y\geq x} . For integers a\geq 0 and b\geq 1 , let q and r be the quotient and remainder of dividing a by b : q:=a{\mathbin{/\mkern-4.0mu/}}b=\lfloor a/b\rfloor , r:=a{\rm\%}b . That is, a=bq+r and 0\leq rM{\mathbin{/\mkern-4.0mu/}}2 Since x{\mathbin{/\mkern-4.0mu/}}d\in\Set{0,1} , it can be implemented as x{\mathbin{/\mkern-4.0mu/}}d=\mathsf{select}(x> 32; 5 u32 t = (( x - y ) >> 1) + y ; 6 return t >> ( a - 33); 7 } We explain Listing 2 . When c is 33 bits, a\geq 33 , and (xc)\gg a=(((xc)\gg 32)\gg 1)\gg(a-33) can be rewritten as three shifts. Let c_{L} be the low 32 bits of c , then c=2^{32}+c_{L} and xc=x(2^{32}+c_{L})=x2^{32}+xc_{L} . Let y:=(xc_{L})\gg 32 , then (xc)\gg 32=y+x . Using y=(xc_{L}){\mathbin{/\mkern-4.0mu/}}2^{32}\leq(x2^{32}){\mathbin{/\mkern-4.0mu/}}2^{32}=x , we get 2^{32}>(y+x){\mathbin{/\mkern-4.0mu/}}2=(x-y+2y){\mathbin{/\mkern-4.0mu/}}2=(x-y){\mathbin{/\mkern-4.0mu/}}2+y . This transformation avoids intermediate values exceeding 32 bits. For example, Listing 3 is the assembly output for d=7 when Listing 1 is compiled with -Ofast (parameters: a=35 , c={\tt 0x124924925} ). Listing 3: Apple M4 Clang assembly output ⬇ 1 ; input : x = w0 2 ; output : w0 3 ; d = 7 4 ; a = 35 5 udiv : 6 ; cL = w8 = 0 x24924925 7 mov w8 , #18725 ; =0 x4925 8 movk w8 , #9362 , lsl #16 9 ; x8 = cL * x 10 umull x8 , w0 , w8 11 ; y = x8 = ( cL * x ) >> 32 12 lsr x8 , x8 , #32 13 ; w9 = x - y 14 sub w9 , w0 , w8 15 ; t = (( x - y ) >> 1) + y 16 add w8 , w8 , w9 , lsr #1 17 ; t >> ( a - 33) 18 lsr w0 , w8 , #2 19 ret 3 Proposed Method Listing 2 is designed so that intermediate values (except for multiplication itself) fit within 32 bits. On 64-bit CPUs, this constraint is no longer necessary. A straightforward approach would be to directly compute the u64 × u64 = u128 multiplication and then right-shift the result. However, this is inefficient on x86-64 architectures because the 128-bit logical right-shift instruction shrd requires the same latency and throughput as mul on Skylake-X [ 2 ] . A similar trend was observed on Sapphire Rapids used in our benchmark. Table 1: Skylake-X architecture: latency and throughput [ 2 ] Instruction Latency Throughput add/sub 1 0.25 shr 1 0.5 imul 3 1 shrd 3 1 Therefore, we propose the following optimization. (xc){\mathbin{/\mkern-4.0mu/}}2^{a}=(x(2^{64-a}c)){\mathbin{/\mkern-4.0mu/}}2^{64} where x is zero-extended to 64 bits. Since c is 33 bits and d\leq M{\mathbin{/\mkern-4.0mu/}}2 , we have 33\leq a\leq 63 , so 2^{64-a}c fits in 64 bits. A 128-bit value is represented by two 64-bit registers (H,L) , so a 64-bit logical right shift is just extracting H . Except for loading the immediate constant, only one multiplication instruction is needed. On AArch64 architectures such as Apple M4, the u64 × u64 = u128 multiplication is split into umulh , which returns the upper 64 bits, and mul , which returns the lower 64 bits. This transformation allows the computation to be implemented with a single umulh instruction. The x86-64 form is Listing 4 and the M4 form is Listing 5 . In loops with repeated divisions by the same constant, the immediate is reused by optimization, so it is effectively one multiply instruction. Listing 4: Proposed method for x86-64 ⬇ 1 // input: x 2 // output: rax = x // d 3 // destroy: t 4 mov ( t , c << (64 - a )); 5 mulx ( rax , t , x ); // [rax:t] = x * t Listing 5: Proposed method for M4 ⬇ 1 // input: x 2 // output: x0 = x // d 3 // destroy: t 4 mov_imm ( t , c << (64 - a )); 5 umulh ( x0 , t , x ); // x0 = (t * x) >> 64 4 LLVM/GCC Improvements and Benchmark We implemented the proposed optimization in LLVM (the compiler infrastructure of Clang) [ 5 ] . To evaluate the effect, we prepared benchmark code for 32-bit unsigned division by constants. In Listing 6 , divisors 7, 19, and 107 are cases where c becomes 33 bits. Listing 6: bench.c ⬇ 1 int test ( uint32_t ret ) { 2 for ( int i = 0; i < 1000000000; i ++) { 3 ret ^= ( i ^ ret ) / 7; 4 ret ^= ( i ^ ret ) / 19; 5 ret ^= ( i ^ ret ) / 107; 6 } 7 return ret ; 8 } First, we generated LLVM IR bench.ll with clang-18 -O2 -S -emit-llvm bench.c -o bench.ll . Then we used LLVM’s llc to generate assembly for each CPU. For Xeon: llc -O2 -mattr=+bmi2 bench.ll -o .s . For M4: llc -O2 -mtriple=arm64-apple-macosx -mcpu=apple-m4 bench.ll -o .s . We compare the code generated by the original LLVM 23.0.0 llc with the code generated by llc modified to support the proposed method. Listing 7: bench-x64-org.s ⬇ 1 test : 2 movl % edi , % eax 3 xorl % ecx , % ecx 4 movl $2938661835, % edx # imm = 0xAF286BCB 5 . p2align 4, 0 x90 6 . lp : 7 movl % ecx , % esi 8 xorl % eax , % esi 9 # begin x/7 sequence 10 imulq $613566757, % rsi , % rdi # imm = 0x24924925 11 shrq $32, % rdi 12 subl % edi , % esi 13 shrl % esi 14 addl % edi , % esi 15 shrl $2, % esi 16 # end x/7 sequence 17 xorl % eax , % esi 18 movl % esi , % edi 19 xorl % ecx , % edi 20 movq % rdi , % rax 21 # begin x/19 sequence 22 imulq % rdx , % rax 23 shrq $32, % rax 24 subl % eax , % edi 25 shrl % edi 26 addl % eax , % edi 27 shrl $4, % edi 28 # end x/19 sequence 29 xorl % esi , % edi 30 movl % edi , % eax 31 xorl % ecx , % eax 32 # begin x/107 sequence 33 imulq $842937507, % rax , % rsi # imm = 0x323E34A3 34 shrq $32, % rsi 35 subl % esi , % eax 36 shrl % eax 37 addl % esi , % eax 38 shrl $6, % eax 39 # end x/107 sequence 40 xorl % edi , % eax 41 incl % ecx 42 cmpl $1000000000, % ecx # imm = 0x3B9ACA00 43 jne . lp Listing 8: bench-x64-opt.s ⬇ 1 test : 2 movl % edi , % eax 3 xorl % ecx , % ecx 4 movabsq $2635249153617166336, % rsi # imm = 0x24924924A0000000 5 movabsq $970881267157434368, % rdi # imm = 0xD79435E58000000 6 movabsq $172399477334736896, % r8 # imm = 0x2647C6946000000 7 . p2align 4 8 . lp : 9 movl % ecx , % edx 10 xorl % eax , % edx 11 mulxq % rsi , % r9 , % r9 # corresponds to x/7 12 xorl % eax , % r9d 13 movl % r9d , % edx 14 xorl % ecx , % edx 15 mulxq % rdi , % r10 , % r10 # corresponds to x/19 16 xorl % r9d , % r10d 17 movl % r10d , % edx 18 xorl % ecx , % edx 19 mulxq % r8 , % rax , % rax # corresponds to x/107 20 xorl % r10d , % eax 21 incl % ecx 22 cmpl $1000000000, % ecx 23 jne . lp Listing 9: bench-m4-org.s ⬇ 1 . lp : 2 eor w13 , w8 , w0 3 # begin x/7 sequence 4 umull x14 , w13 , w9 5 lsr x14 , x14 , #32 6 sub w13 , w13 , w14 7 add w13 , w14 , w13 , lsr #1 8 # end x/7 sequence 9 eor w13 , w0 , w13 , lsr #2 10 eor w14 , w13 , w8 11 # begin x/19 sequence 12 umull x15 , w14 , w10 13 lsr x15 , x15 , #32 14 sub w14 , w14 , w15 15 add w14 , w15 , w14 , lsr #1 16 # end x/19 sequence 17 eor w13 , w13 , w14 , lsr #4 18 eor w14 , w13 , w8 19 add w8 , w8 , #1 20 # begin x/107 sequence 21 umull x15 , w14 , w11 22 cmp w8 , w12 23 lsr x15 , x15 , #32 24 sub w14 , w14 , w15 25 add w14 , w15 , w14 , lsr #1 26 # end x/107 sequence 27 eor w0 , w13 , w14 , lsr #6 28 b . ne . lp Listing 10: bench-m4-opt.s ⬇ 1 . lp : 2 eor w13 , w8 , w0 3 umulh x13 , x13 , x9 4 eor w13 , w13 , w0 5 eor w14 , w13 , w8 6 umulh x14 , x14 , x10 7 eor w13 , w14 , w13 8 eor w14 , w13 , w8 9 add w8 , w8 , #1 10 umulh x14 , x14 , x11 11 cmp w8 , w12 12 eor w0 , w14 , w13 13 b . ne . lp Listings 7 and 8 are for x86-64, and Listings 9 and 10 are for Apple M4. Comparing each pair shows that before the change, 33-bit constant division is implemented with a three-stage shift sequence, whereas after the change it is implemented by a single multiply, resulting in a more compact loop. Next, we assembled these files into executables and measured runtime with the time command. Results are shown in Table 2 . Table 2: Runtime comparison on Xeon/Apple M4 (sec) CPU Before After Speedup Xeon 6.33 3.80 x1.67 M4 6.70 3.38 x1.98 Measurement environments were Xeon w9-3495X (Sapphire Rapids)/Ubuntu 24.04.4 LTS and Apple M4 MacBook Pro/Tahoe 26.4. Each measurement was repeated 10 times and the average was taken. CPU settings were the default frequency/performance settings. The average runtime improved from 6.33 sec to 3.80 sec (x1.67) on Xeon and from 6.70 sec to 3.38 sec (x1.98) on M4. The sample standard deviations on Xeon were 0.013 sec (before) and 0.009 sec (after), indicating low variance. This LLVM change has been merged into llvm:main. We also prepared a corresponding GCC patch [ 6 ] , which is currently under review. 5 Conclusion This paper proposed an optimization method for 32-bit unsigned division by constants under a 64-bit CPU assumption. For the 33-bit-constant case in the conventional GM method, we showed that implementation is possible with a single multiplication instruction without a 128-bit shift. With the LLVM implementation, we confirmed up to 1.67x (Sapphire Rapids) and 1.98x (Apple M4) speedups in real machine benchmarks. We also prepared a corresponding GCC patch.