Optimizing 32-bit Unsigned Division by Constants on 64-bit CPUs

In the realm of compiler optimization, the division of 32-bit unsigned integers by constants has traditionally been handled by methods like the GM method, which is widely used in major compilers such as GCC and Clang. However, these methods are optimized for 32-bit CPUs and do not fully exploit the capabilities of 64-bit architectures. This paper introduces a novel optimization technique specifically designed for 64-bit CPUs, which significantly enhances the performance of 32-bit unsigned division by constants.

The proposed method addresses the inefficiencies of the GM method when applied to 64-bit systems. By eliminating the need for 128-bit shifts and utilizing a single multiplication instruction, the new approach streamlines the division process. This is particularly effective for cases where the constant is 33 bits, a scenario that previously required multiple operations. The implementation of this method in LLVM has demonstrated substantial speedups, achieving a 1.67x improvement on Intel Xeon and a 1.98x improvement on Apple M4 processors.

The paper details the theoretical underpinnings of the optimization, including a review of existing methods and the derivation of the new approach. It also provides practical examples of the assembly code generated before and after the optimization, illustrating the reduction in complexity and execution time. Benchmarks conducted on different architectures validate the effectiveness of the proposed method, showing consistent performance gains across various test cases.

This advancement not only enhances the efficiency of compilers but also sets a precedent for future optimizations targeting 64-bit systems. The integration of this method into LLVM and the ongoing review of a corresponding GCC patch highlight its practical applicability and potential for widespread adoption in the software development community.