为什么编译器不能(或不能)优化一个可预测的加法循环到乘法？

这是我在阅读 神秘对这个问题的精彩回答时想到的一个问题: 为什么处理排序的数组比处理未排序的数组更快？

所涉及类型的上下文:

const unsigned arraySize = 32768;
int data[arraySize];
long long sum = 0;

在他的回答中，他解释说英特尔编译器(ICC)对此进行了优化:

for (int i = 0; i < 100000; ++i)
for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
sum += data[c];

变成这样的东西:

for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
for (int i = 0; i < 100000; ++i)
sum += data[c];

优化器认识到这些是等价的，因此是 交换循环，将分支移到内部循环之外。非常聪明！

但它为什么不这样做呢？

for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
sum += 100000 * data[c];

希望神秘博士(或者其他人)能够给出一个同样精彩的答案。我以前从来没有学过这个问题中讨论的优化，所以我真的很感激。

19010 次浏览
小开

编译器包含执行优化的各种步骤。通常在每一次传递中，要么对语句进行优化，要么对循环进行优化。目前还没有一种基于循环头的循环体优化模型。这种情况很难发现，也不太常见。

所做的优化是循环不变的代码运动。这可以用一套技术来完成。

小开

我猜有些编译器可能会做这种优化，假设我们讨论的是整数算术。

同时，一些编译器可能会拒绝这样做，因为用乘法代替重复加法可能会改变代码的溢出行为。对于无符号整数类型，由于它们的溢出行为完全由该语言指定，因此不会产生任何差异。但是对于签名的，它可能(可能不在2的补语平台上)。的确，签名溢出实际上导致了 C 语言中的未定义行为，这意味着完全可以忽略溢出语义，但并非所有编译器都有足够的勇气这样做。它经常招致“ C 只是一种更高级别的汇编语言”人群的大量批评。(还记得当 GCC 引入基于严格混淆语义的优化时发生了什么吗?)

从历史上看，GCC 已经证明了自己是一个能够采取如此激烈步骤的编译器，但是其他编译器可能更愿意坚持感知到的“用户意图”行为，即使它没有被语言定义。

小开

这个答案不适用于相关的具体案例，但适用于问题的标题，可能会引起未来读者的兴趣:

由于精度有限，重复的浮点加法不等同于乘法 :

float const step = 1e-15;
float const init = 1;
long int const count = 1000000000;


float result1 = init;
for( int i = 0; i < count; ++i ) result1 += step;


float result2 = init;
result2 += step * count;


cout << (result1 - result2);

演示

小开

这种优化存在概念上的障碍。编译器作者在 强度降低上花费了大量精力——例如，用增加和移位代替乘法。他们习惯于认为繁殖是不好的。因此，一个人应该走另一条路的情况是令人惊讶和违反直觉的。所以没有人想要实施它。

小开
最佳答案

编译器通常不能转换

for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
for (int i = 0; i < 100000; ++i)
sum += data[c];

进入

for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
sum += 100000 * data[c];

因为后者可能导致有符号整数溢出，而前者不会。即使对于有符号2的补整数的溢出保证了环绕行为，它也会改变结果(如果 data[c]是30000，对于典型的环绕32位 int，产品将变成 -1294967296，而100000次向 sum添加30000，如果没有溢出，将使 sum增加300000000)。注意，对于无符号量，如果数字不同，100000 * data[c]的溢出通常会引入一个模 2^32，这个模 2^32不能出现在最终结果中。

它可以把它变成

for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
sum += 100000LL * data[c];  // resp. 100000ull

但是，如果像往常一样，long long足够大于 int。

为什么它不这样做，我不知道，我猜这是什么 神秘人说，“显然，它不运行循环折叠通过后循环交换”。

注意，循环交换本身通常是无效的(对于有符号整数) ，因为

for (int c = 0; c < arraySize; ++c)
if (condition(data[c]))
for (int i = 0; i < 100000; ++i)
sum += data[c];

可能导致溢出

for (int i = 0; i < 100000; ++i)
for (int c = 0; c < arraySize; ++c)
if (condition(data[c]))
sum += data[c];

不会。这里是合法的，因为这个条件确保所有添加的 data[c]都有相同的符号，所以如果一个溢出，两个都会溢出。

不过，我不太确定编译器是否考虑到了这一点(@Mystiical，你可以尝试使用类似 data[c] & 0x80的条件吗? 对于正值和负值，这个条件都可以为真。).我让编译器进行了无效的优化(例如，几年前，我在 1.0/n中使用了 ICC (11.0，iirc)的有符号 -32位 int-to-double 转换，其中 n是 unsigned int。是 GCC 输出速度的两倍。但是错了，很多值都大于 2^31，哎呀。).

小开

开发和维护编译器的人员花在工作上的时间和精力是有限的，因此他们通常希望将重点放在用户最关心的事情上: 将编写良好的代码转换为快速代码。他们不想把时间花费在寻找将愚蠢的代码转化为快速代码的方法上ーー这就是代码审查的目的。在高级语言中，可能存在表达重要想法的“愚蠢”代码，这使得开发人员有必要花时间来加快速度。例如，砍伐森林和流融合的捷径使得 Haskell 程序能够围绕某种延迟生成的数据结构编译成不分配内存的紧密循环。但是，这种激励机制并不适用于将循环加法转化为乘法。如果你想要它快一点，只要用乘法写出来就行了。

小开

现在有了:

long long add_100k_signed(int *data, int arraySize)
{
long long sum = 0;


for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
for (int i = 0; i < 100000; ++i)
sum += data[c];
return sum;
}

用 -O1编译到

add_100k_signed:                        # @add_100k_signed
test    esi, esi
jle     .LBB0_1
mov     r9d, esi
xor     r8d, r8d
xor     esi, esi
xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
movsxd  rdx, dword ptr [rdi + 4*rsi]
imul    rcx, rdx, 100000
cmp     rdx, 127
cmovle  rcx, r8
add     rax, rcx
add     rsi, 1
cmp     r9, rsi
jne     .LBB0_4
ret
.LBB0_1:
xor     eax, eax
ret

整数溢出与此无关，如果整数溢出导致了未定义行为，那么两种情况都可能发生。这里是 使用 ABC0而不是 long的同类函数:

int add_100k_signed(int *data, int arraySize)
{
int sum = 0;


for (int c = 0; c < arraySize; ++c)
if (data[c] >= 128)
for (int i = 0; i < 100000; ++i)
sum += data[c];
return sum;
}

用 -O1编译到

add_100k_signed:                        # @add_100k_signed
test    esi, esi
jle     .LBB0_1
mov     r9d, esi
xor     r8d, r8d
xor     esi, esi
xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
mov     edx, dword ptr [rdi + 4*rsi]
imul    ecx, edx, 100000
cmp     edx, 127
cmovle  ecx, r8d
add     eax, ecx
add     rsi, 1
cmp     r9, rsi
jne     .LBB0_4
ret
.LBB0_1:
xor     eax, eax
ret

提交答案