在现代计算场景中，整数除法仍是性能关键路径上的瓶颈之一。2026 年 4 月发表于 arXiv 的一篇论文《Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets》提出了针对 64 位 CPU 优化的 32 位无符号除以常数新方法，已被 LLVM 采纳并合并至主线，同时提供 GCC patch 供社区使用。该工作在 Intel Xeon w9-3495X 上实现 1.67x 加速，在 Apple M4 上更达到 1.98x 加速，为编译器优化领域提供了重要的工程实践参考。

背景：GM 方法与现有编译器的局限

整数除以常数的优化是编译器基础设施中的经典问题。1992 年，Granlund 和 Montgomery 提出了一种革命性的方法（后称 GM 方法），通过乘法和移位操作替代昂贵的硬件除法。该方法的核心思想是将除法转换为以下形式的表达式：x /d ≈ (x * m) >> k，其中 m 是一个 “魔术数”（magic number），k 是移位量。这种方法利用了整数乘法的低延迟特性，在大多数现代 CPU 上远快于直接执行除法指令。

当前主流编译器包括 GCC、Clang、Microsoft Compiler 和 Apple Clang 都已实现 GM 方法及其改进版本。然而，一个长期被忽视的问题是：这些优化实现大多基于 32 位 CPU 的假设，针对的是 32 位寄存器宽度进行计算。当编译目标为 64 位 CPU 时，这种优化策略未能充分利用 64 位寄存器的宽度优势。具体而言，传统实现在计算过程中会将中间结果限制在 32 位或 64 位范围内，但未考虑如何利用 64 位算术单元直接处理 32 位被除数与 32 位除数的组合，从而产生更优的指令序列。

新方法的优化思路

该论文的核心贡献在于重新审视了 32 位无符号除以常数在 64 位目标上的优化策略。传统方法在处理 x / 7 这类常见除数时，生成的代码遵循以下模式：首先计算乘法产生 64 位结果，然后通过右移提取所需位。这种方式在 64 位 CPU 上并未充分发挥硬件能力，因为 64 位乘法单元可以在单周期内完成运算，而现有的代码生成策略往往引入不必要的位宽转换或额外的算术操作。

新方法的关键改进在于：当除数的位宽恰好为 33 位（即常数值超过 32 位有符号整数范围但未达到 64 位）时，通过精心选择的魔术数和移位量，可以完全在 64 位算术路径上完成计算，避免了传统方法中 128 位中间值的处理。论文详细分析了 33 位除数场景下的优化策略，指出此时乘法优先的方法比传统的 128 位移位路径更具性能优势。

这一改进的理论基础在于：64 位 CPU 的乘法单元可以单周期产生完整的 64 位结果，而传统方法中为了处理可能溢出的 128 位中间值，需要额外的指令和寄存器。通过重新设计魔术数的选择算法，使得所有中间运算都可以在 64 位范围内完成，从而生成更加紧凑高效的指令序列。

LLVM 与 GCC 实现

作者团队实现了针对 LLVM 和 GCC 的 patch，并详细描述了将新优化策略集成到编译器后端的工程过程。LLVM patch 已成功合并至 llvm:main 分支，这意味着最新版本的 Clang 编译器已经支持该优化。对于 GCC patch，作者提供了完整的实现代码，开发者可从论文关联的代码仓库获取并手动应用。

集成过程中最关键的挑战在于魔术数表的扩展。传统 GM 方法使用的魔术数表针对 32 位目标优化，新方法需要计算并验证一套全新的魔术数集合。论文附录中提供了针对常见除数（7、19、107 等）的优化参数，包括推荐的魔术数、移位量以及调整因子，供编译器开发者直接引用或验证。

性能实测数据

论文在两款主流服务器和桌面 CPU 上进行了微基准测试。Intel Xeon w9-3495X（代号 Sapphire Rapids）代表当代 x86-64 服务器处理器，Apple M4 则代表基于 ARM 架构的桌面级 SoC。测试结果表明，新优化方法带来的加速比在 1.67x 至 1.98x 之间，具体数值取决于除数的分布特征。

值得注意的是，加速效果并非对所有除数均一致。论文指出，当除数的位宽恰好为 33 位时，加速效果最为显著。这是因为 33 位除数正是传统方法与新方法产生最大差异的边界情况：传统方法需要处理 128 位中间值，而新方法可以利用 64 位算术路径完整覆盖。对于位宽为 32 位及以下的除数，加速效果相对较小，但仍有收益。

对编译器开发者的启示

该工作为编译器优化开发者提供了多层次的参考价值。首先，它提醒社区：即使是被广泛采用的经典优化算法，也可能存在针对新硬件架构改进的空间。其次，论文采用的性能分析方法 —— 通过对比不同指令序列的延迟和吞吐量来选择最优生成策略 —— 可以作为其他整数运算优化的参考范式。

对于专注于性能优化的工程师而言，理解除法优化的原理有助于在特定场景下做出更好的编译决策。例如，在嵌入式系统调优中，了解编译器如何处理除以常数可以帮助开发者手动优化热点代码；而在编译器开发中，该工作展示了如何通过系统性的基准测试验证优化效果。

此外，该工作也暗示了编译器与硬件协同设计的潜力。随着 CPU 架构持续演进，编译器后端需要不断重新审视既有优化策略，评估新硬件特性（如更宽的 SIMD 单元、更快的乘法延迟）如何影响指令选择决策。

资料来源：arXiv:2604.07902, Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets, Shigeo Mitsunari, Takashi Hoshino, 2026 年 4 月 9 日。