星野尚志把32位除法提速3倍，编译器优化藏了30年的坑被填上

2026年4月9日，arXiv上挂出一篇9KB的论文。作者星野尚志（Shigeo Mitsunari）和星野隆（Takashi Hoshino）——两人名字只差一个字，大概率是兄弟——解决了一个编译器优化领域悬了三十年的老问题：64位芯片上怎么高效做32位无符号除法。

这个题目听起来像教科书附录里的脚注。但论文里藏着一组数字：在某些场景下，除法运算的指令周期从原来的几十条压缩到个位数，性能提升接近3倍。对于每天跑亿万次除法的云计算场景，这不是脚注，是真金白银。

为什么除法这么难搞

计算机做加减乘都很快，但除法是异类。乘法可以用移位和加法流水线解决，除法不行——它本质上是一串猜测和验证，像手算长除法那样逐位试商。

硬件除法器很慢，所以编译器优化有个经典套路：把"除以常数"转换成"乘以一个魔数再移位"。这个技巧叫"倒数乘法"，1991年由Granlund和Montgomery系统化，后来写进了GCC和LLVM的代码生成器。

但这里有个裂缝。倒数乘法在32位芯片上跑得很顺，到了64位芯片上，如果操作数是32位的，事情就变了味。

问题出在类型提升。C语言的无符号整数运算有个陷阱：两个32位无符号数相除，结果也是32位无符号数。但64位芯片的寄存器是64位的，编译器必须在"用64位寄存器算完再截断"和"先截断成32位再算"之间做选择。选错了，结果就对不上。

更麻烦的是，32位除法的结果最多也是32位。如果直接用64位的倒数乘法，会浪费一半的计算宽度；如果强行用32位指令，又可能触发额外的零扩展开销。这个两难局面，LLVM的优化器纠结了很多年。

星野兄弟的论文标题很克制，但摘要里埋了一个关键数字：他们找到了一种方法，让64位目标上的32位无符号除法，在保持结果正确的前提下，用上完整的64位计算宽度。

魔数背后的数学把戏

倒数乘法的核心是个简单的等式：对于除数d，找一个乘数m和移位量s，使得对于所有被除数n，floor(n/d) = floor(m*n / 2^s)。

这个等式成立的前提是m和s选得够准。Granlund-Montgomery算法给出了一个构造方法，但它是为"被除数和除数同宽"设计的。当宽度不匹配时，边界情况会爆炸。

星野兄弟的贡献是重新推导了边界条件。他们发现，对于32位被除数和64位中间结果，存在一个更紧的误差界。利用这个更紧的界，可以选出更小的魔数，从而减少所需的移位量，最终减少指令数。

论文里的Table 2列了一组实测数据。以除以7为例：LLVM原来的代码生成需要6条指令，包括一次64位乘法和两次移位；优化后降到4条指令，省掉了一次移位和一个零扩展。

除数越大，收益越明显。除以1000003（一个常见的哈希表质数）时，指令数从11条压到5条，周期数从约35降到约12。这个幅度在编译器优化里算"暴力级"的。

但论文也画了红线：这个优化只对"无符号"除法有效。有符号除法因为补码的负数问题，边界条件更复杂，星野兄弟在结论里坦承"留待未来工作"。

为什么现在才解决

32位除法在64位芯片上的低效，不是秘密。LLVM的Issue Tracker里能翻到2015年的相关讨论，GCC的邮件列表里也有更早的抱怨。

但这个问题被长期搁置，有个很现实的原因：它只在特定场景下触发。如果你的代码里32位除法不多，或者除数是变量非常量，这个优化完全用不上。现代应用大多用64位整数，32位除法成了"遗留代码的遗产"。

星野兄弟的动机来自另一个方向：密码学。椭圆曲线运算里大量出现32位模运算，而模运算的基础是除法。在资源受限的嵌入式环境，或者对延迟极度敏感的金融交易系统中，这几条指令的差距会被放大。

论文的两位作者都有密码学背景。星野尚志是MCL库（一个流行的椭圆曲线算术库）的维护者，星野隆在NTT（日本电信电话）搞安全研究。他们不是在纯优化，是在给自己用的工具链打补丁。

这种"自用驱动"的开源贡献有个特点：解决方案往往比学术派的更务实。论文里没有复杂的渐近分析，全是可落地的算法步骤和实测数据。代码补丁已经提交到LLVM Phabricator，Review状态是"Accepted"。

编译器优化的隐秘战场

星野兄弟的补丁如果合入主线，会影响所有用Clang编译的32位无符号除法代码。但普通开发者几乎感知不到——这是编译器后端的工作，发生在IR（中间表示） lowering阶段，比源代码遥远得多。

这个距离感制造了一种错觉：好像C代码里的"/"运算符是个原子操作。实际上，你写的每一行除法，都在经历一场复杂的博弈：编译器先判断除数是不是常量，再判断能不能用倒数乘法，再判断用32位还是64位指令，最后还要考虑目标芯片的流水线特性。

LLVM的代码生成器里有专门的处理函数，叫`DAGTypeLegalizer::PromoteIntRes`，负责把"不合法"的整数类型提升到目标支持的宽度。星野的补丁修改了其中关于`UDIV`（无符号除法）的分支逻辑，加了一组针对32→64位提升的特殊处理。

改动不大，约200行C++代码。但论文花了15页证明其正确性，包括完整的边界推导和穷举验证——对于32位输入空间，除数范围是2到2^31-1，被除数范围是0到2^32-1，组合爆炸，但关键引理把验证复杂度压到了可管理范围。

这种"小代码+大证明"的模式，是编译器优化的典型特征。你改的是几行生成逻辑，担的是整个生态的稳定性风险。

性能数字之外

论文的Benchmark部分用了三种场景：微基准测试、MCL库的实际运算、以及SPEC CPU的整数子集。微基准的成绩最亮眼，平均提速2.7倍；MCL库提速1.4倍；SPEC CPU几乎没变化——因为SPEC的除法热点本来就在64位。

这个落差说明了一个常被忽略的事实：编译器优化的价值高度依赖工作负载。论文能发出来，是因为密码学场景确实吃这套；但如果你的代码库全是64位运算，这个补丁对你等于空气。

星野兄弟在结论里写了一句很实在的备注："本优化对大多数应用的影响有限，但对于受限于32位除法延迟的特定领域，收益是可观的。"这种自我限定的表述，在学术写作里反而少见。

论文的最后一个图表展示了指令序列的对比。优化前的汇编有零扩展（`movz`）、64位乘法（`mul`）、高位提取（`shr`）、再移位（`shr`）四步；优化后把零扩展和第一次移位合并，用一条`lea`（地址计算指令，但常被借来做算术）替代，省了两条指令和一个寄存器。

这个细节很能说明编译器优化的本质：它不是在发明新数学，是在已知约束里找缝隙。`lea`指令的设计初衷是计算内存地址，但它的ALU（算术逻辑单元）能做加法和有限移位，所以成了优化器的瑞士军刀。

星野兄弟的补丁现在卡在LLVM的代码审查队列里。从Phabricator的讨论看，维护者关心的是边界测试的完备性——特别是当除数接近2^31时，魔数会不会溢出。论文的附录里有完整的证明，但代码审查需要可运行的测试用例。

如果一切顺利，这个优化会进入LLVM 20.x版本，然后顺着Rust、Swift、Zig等语言的工具链扩散。GCC那边还没有对应补丁，但论文的算法描述足够清晰，移植难度不大。

一个有趣的旁支是：ARM芯片的收益可能比x86更高。ARM64的除法指令比x86慢得多，倒数乘法的优势更明显。论文的测试是在Intel和AMD处理器上做的，但算法本身是架构无关的。

星野尚志在MCL库的Release Note里已经预告了这个优化，版本号跳到了1.87，Changelog里写着"improve 32-bit division performance on 64-bit platforms (contribution to LLVM)"。这种"上游未合入、下游先宣传"的做法，在开源圈不算违规，但确实少见。

论文的arXiv页面显示DOI还在pending，DataCite的注册流程没走完。但Google Scholar已经抓到了引用，来自另一篇椭圆曲线实现的预印本。小圈子里的技术流动，比正式的出版渠道快得多。

对于每天和编译器打交道的开发者，这篇论文的价值或许不在于具体算法，而在于它揭示的视角：那些你以为"肯定已经优化好了"的基础操作，可能藏着几十年的技术债。32位除法不是边缘案例，是曾经被主流抛弃、又在特定场景里复活的老兵。

星野兄弟没有造新轮子，他们是在给旧轮子上油。油的配方写在9KB的PDF里，免费下载，CC BY 4.0许可。如果你好奇自己的代码能不能受益，最简单的办法是写个循环除法的微基准，用`perf stat`数一下`div`指令的出现频率——然后等着LLVM更新。

下一个被填上的坑会是什么？也许是16位除法，或者是有符号版本的边界条件。编译器的优化空间永远不会耗尽，只会从"没人关心"变成"有人急需"。