--- title: "64位目标上的32位无符号除以常数优化：编译器实现与实测加速" route: "/posts/2026/04/13/32-bit-unsigned-division-constant-optimization/" canonical_path: "/posts/2026/04/13/32-bit-unsigned-division-constant-optimization/" canonical_url: "https://blog2.hotdry.top/posts/2026/04/13/32-bit-unsigned-division-constant-optimization/" markdown_path: "/agent/posts/2026/04/13/32-bit-unsigned-division-constant-optimization/index.md" markdown_url: "https://blog2.hotdry.top/agent/posts/2026/04/13/32-bit-unsigned-division-constant-optimization/index.md" agent_public_path: "/agent/posts/2026/04/13/32-bit-unsigned-division-constant-optimization/" agent_public_url: "https://blog2.hotdry.top/agent/posts/2026/04/13/32-bit-unsigned-division-constant-optimization/" kind: "research" generated_at: "2026-04-13T19:18:17.960Z" version: "1" slug: "2026/04/13/32-bit-unsigned-division-constant-optimization" date: "2026-04-13T17:27:55+08:00" category: "compilers" year: "2026" month: "04" day: "13" --- # 64位目标上的32位无符号除以常数优化：编译器实现与实测加速 > 解析基于GM方法改进的32位无符号除以常数编译器优化，在64位CPU上实现1.67x至1.98x性能提升的工程实践。 ## 元数据 - Canonical: /posts/2026/04/13/32-bit-unsigned-division-constant-optimization/ - Agent Snapshot: /agent/posts/2026/04/13/32-bit-unsigned-division-constant-optimization/index.md - 发布时间: 2026-04-13T17:27:55+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 站点: https://blog2.hotdry.top ## 正文 在现代计算场景中，整数除法仍是性能关键路径上的瓶颈之一。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日。 ## 同分类近期文章 ### [追踪 LLVM RISC-V 后端性能回归：二分查找与修复验证全流程](/agent/posts/2026/04/14/llvm-risc-v-regression-debugging/index.md) - 日期: 2026-04-14T01:01:53+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 摘要: 详解 LLVM RISC-V 后端性能回归的定位与修复流程，提供二分查找、回归测试与验证的完整工程参数。 ### [从 ROBDD 到 TDD：有序二叉决策图的规范化推广与形式验证新范式](/agent/posts/2026/04/13/canonical-generalization-obdd-tdd/index.md) - 日期: 2026-04-13T16:30:32+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 摘要: 解析 Tree Decision Diagrams 作为 OBDD 的规范化推广，如何在保持关键运算可判定性的同时突破指数爆炸瓶颈，为模型检查与布尔函数优化提供新思路。 ### [可演进语言设计范式：语言作为自描述的自举系统](/agent/posts/2026/04/13/perfectable-language-design-paradigm/index.md) - 日期: 2026-04-13T16:04:08+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 摘要: 探讨编程语言如何在架构层面支持运行时吸收新特性，实现自举与自改进的工程路径，解析可演进语言的设计哲学与实现参数。 ### [可完美化编程语言：Lean 的设计哲学与工程实践](/agent/posts/2026/04/13/perfectable-programming-language-lean/index.md) - 日期: 2026-04-13T16:04:08+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 摘要: 探讨 Lean 语言「可完美化」的设计理念，分析依赖类型、元编程与自举能力如何共同构建可自我进化的编程系统。 ### [单一二元运算符重构全部初等函数：EML 运算符的数学突破与编译器启示](/agent/posts/2026/04/13/eml-operator-elementary-functions-construction/index.md) - 日期: 2026-04-13T14:30:25+08:00 - 分类: [compilers](/agent/categories/compilers/index.md) - 摘要: 解析 Andrzej Odrzywołek 如何发现 EML 运算符 exp(x)-ln(y) 配合常数 1 可重构完整科学计算器功能，探讨编译器数值计算的新路径与精度权衡。