为什么编译器不能（或不能）将可预测的加法循环优化为乘法？

编译器一般不能转换

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];

因为后者可能导致有符号整数溢出，而前者不会。即使保证有符号二进制补码整数溢出的回绕行为，它也会改变结果（如果 data[c] 为 30000，则对于典型的 32 位 int 带有回绕的乘积将变为 -1294967296，而将 30000 添加到 sum 100000 次，如果不溢出，则将 sum 增加 3000000000）。请注意，对于具有不同数字的无符号量也是如此，100000 * data[c] 的溢出通常会引入一个不能出现在最终结果中的模 2^32 归约。

它可以把它变成

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

但是，如果像往常一样，long long 比 int 大得多。

为什么它不这样做，我不知道，我猜它是 Mysticial said，“显然，它不会在循环交换后运行循环折叠传递”。

请注意，循环交换本身通常无效（对于有符号整数），因为

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] 都具有相同的符号，所以如果一个溢出，两者都会溢出。

不过，我不太确定编译器是否考虑到了这一点（@Mysticial，您能否尝试使用 data[c] & 0x80 之类的条件，或者这样对于正值和负值都适用？）。我让编译器进行了无效优化（例如，几年前，我在 1.0/n 中有一个 ICC（11.0，iirc）使用有符号 32 位整数到双精度转换，其中 n 是 {4 }。大约是 gcc 输出的两倍。但是错了，很多值都大于 2^31，哎呀。）。

---

此答案不适用于链接的特定案例，但确实适用于问题标题，并且可能对未来的读者感兴趣：

由于精度有限，重复的浮点加法不等于乘法。考虑：

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);

Demo

---

编译器包含进行优化的各种通道。通常在每次传递中，要么对语句进行优化，要么进行循环优化。目前还没有基于循环头对循环体进行优化的模型。这很难检测并且不太常见。

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

---

它现在 - at least, clang does：

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

整数溢出与它无关；如果存在导致未定义行为的整数溢出，则在任何一种情况下都可能发生。这是the same kind of function using int instead of 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

---

好吧，假设我们谈论的是整数运算，我猜一些编译器可能会进行这种优化。

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

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

---

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

---

开发和维护编译器的人花在工作上的时间和精力有限，因此他们通常希望专注于用户最关心的事情：将编写良好的代码转化为快速代码。他们不想花时间试图找到将愚蠢的代码变成快速代码的方法——这就是代码审查的目的。在高级语言中，可能存在表达重要思想的“愚蠢”代码，因此值得开发人员花时间加快速度——例如，捷径砍伐森林和流融合允许 Haskell 程序围绕某些类型的惰性构建生成的数据结构被编译成不分配内存的紧密循环。但这种激励根本不适用于将循环加法转换为乘法。如果你想让它快一点，就用乘法来写。

---