Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces an optimization method for 32-bit unsigned integer division by constants on 64-bit CPUs, addressing the limitations of existing methods like the Granlund-Montgomery (GM) method which generate code optimized for 32-bit architectures. By better leveraging 64-bit capabilities, the proposed method achieves significant speedups, with microbenchmark results showing 1.67x improvement on Intel Xeon w9-3495X and 1.98x on Apple M4. The successful integration of the LLVM patch into llvm:main validates the method's practical utility.
32-bit division on your fancy 64-bit CPU is slower than it needs to be: this optimization speeds it up by almost 2x.
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 [6], demonstrating the practical applicability of the proposed method.