整数除法在除数为常量时的优化原理
搬运自我的知乎回答:编译器是如何实现 32 位整型的常量整数除法优化的?
题主说的应该是将除以编译期常量的除法变换为一次乘法和一堆加减法和按位右移的优化吧:
unsigned test(unsigned x) {
return x / 10;
}
被编译器优化为:
test:
mov eax, edi
mov edx, 3435973837
imul rax, rdx
shr rax, 35
ret
这是一个很经典的优化,在 1994 年的论文 Division by Invariant Integers using Multiplication 中提出了明确的构造方法及其正确性证明。
现代 CPU 内部的硬件除法器通常延迟很高。以 x86 架构为例,uops.info 上给出了 Alder Lake 架构下 32 位整数除法指令 idiv 的延迟为 10-15 个周期左右,相比之下 32 位整数乘法指令 imul 的延迟为 3-4 个周期。因此,将除法操作替换为若干其他算术运算操作是有效的优化。
无符号整数除法
记被除数为
这个优化的基本原理其实非常简单。我们知道,在计算整数除法时,如果除数是 2 的整数次幂 ,那么这个除法操作可以被一个非常高效的按位右移操作取代。因此我们可以考虑把除数换为 2 的某个整数次幂,并将原来的除法操作替换为一次乘法和一个按位右移操作:
进一步,这里虽然
因此,只要能找到这样一组
假设被除数
那么一定有:
证明也不难,只需要证明
即可。感兴趣的读者可以在论文中找到具体证明细节。
有了这个结论就很好构造了。根据条件 (1),我们需要在区间
从优化原理也不难看出,对于同一个优化前的除法操作,可能存在多种
上面的理论优化方案在实际应用过程中会遇到问题。我们有:
且当
因此,编译器一般会首先尝试令
实例:对于以下函数 test1
:
unsigned test1(unsigned n) {
return n / 10;
}
目前最新的 gcc 和 clang 编译器都把它优化为了:
unsigned test1(unsigned n) {
// mov ecx, $n
// mov eax, 3435973837
// imul rax, rcx
// shr rax, 35
// ret
return (uint64_t)n * 3435973837 >> 35;
}
这里
如果对于所有
此时
实例:对于以下函数 test2
:
unsigned test2(unsigned n) {
return n / 42;
}
目前最新的 clang 编译器把它优化为了:
unsigned test2(unsigned n) {
// shr $n
// imul rax, rdi, 818089009
// shr rax, 34
// ret
return (uint64_t)(n >> 1) * 818089009 >> 34;
}
当 n / 42
可以被变换为 (n >> 1) / 21
,因此优化后的代码有一个将 x
逻辑右移 1 位的操作。新的除数为
在尝试了上面所有办法后,如果 (1) 中的区间内仍然不存在
为了解决
这样就避免了乘法计算过程中的溢出。
记
其中
实例:对于以下函数 test3
:
unsigned test3(unsigned n) {
return n / 31;
}
目前最新的 clang 编译器把它优化为了:
unsigned test3(unsigned n) {
// mov eax, $n
// imul rax, rax, 138547333
// shr rax, 32
// sub $n, eax
// shr $n
// add eax, $n
// shr eax, 4
// ret
unsigned k = (uint64_t)n * 138547333 >> 32;
return (((n - k) >> 1) + k) >> 4;
}
对于所有 k
时用到的魔数。k值计算得到后再直接套用 (3) 并带入
有符号整数除法
针对有符号整数除以常数的优化方案可以基于无符号整数的优化方案进行针对性调整。假设被除数为
从前述论文中的定理 5.1 可以引申出定理 (2) 在有符号整数上的情况。如果有:
那么一定有:
其中若
实例:对于以下函数:
int test(int n) {
return n / -10;
}
目前最新的 clang 编译器把它优化为了:
int test(int n) {
// movsxd rax, $n
// imul rax, rax, -1717986919
// mov rcx, rax
// shr rcx, 63
// sar rax, 34
// add eax, ecx
// ret
int64_t k = (int64_t)n * -1717986919;
return (k >> 34) + (k < 0);
}
优化后代码的最后一步就是判断 k
是否为负并在其为负时将结果加 1 。对于优化后代码中的两个魔数,则是完全按照无符号除法的优化方法计算得到的。我们尝试分别令
与无符号整数除法类似,如果当
其中
实例:对于以下函数:
int test(int n) {
return n / 15;
}
目前最新的 clang 编译器把它优化为了:
int test(int n) {
// movsxd rax, $n
// imul rcx, rax, -2004318071
// shr rcx, 32
// add eax, ecx
// mov ecx, eax
// shr ecx, 31
// sar eax, 3
// add eax, ecx
// ret
int t1 = (uint64_t)((int64_t)n * -2004318071) >> 32;
int t2 = n + t1;
return (t2 >> 3) + (n < 0);
}
同样,优化后代码的最后一步加法就是判断除法结果是否为负并在其为负时将结果加 1 。由于当 t2
右移