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

Question

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

132

这是一个问题，当我阅读由Mysticial在问题为什么处理已排序的数组比未排序的数组快所给出的杰出答案时，它在我的脑海中浮现。

涉及类型的上下文：

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

希望Mysticial（或其他人）能给出同样出色的回答。我以前从未学过那个问题中讨论的优化方法，所以我对此非常感激。

- jhabbott

14

这可能只有英特尔知道。我不知道它运行优化过程的顺序。显然，在循环置换后，它不会进行循环合并处理。 - Mysticial

7

只有在数据数组中包含的值不可变时，此优化才有效。例如，如果它们是内存映射到输入/输出设备，则每次读取data[0]都会产生不同的值... - Thomas C. G. de Vilhena

2

这是什么数据类型，整数还是浮点数？在浮点数中重复加法与乘法会给出非常不同的结果。 - Ben Voigt

6

如果数据是“易失性的”，那么循环交换也将成为一种无效的优化。 - Ben Voigt

3

GNAT（使用GCC 4.6的Ada编译器）在O3优化级别下不会交换循环，但如果循环被交换，它将把其转换为乘法。 - prosfilaes

显示剩余9条评论

7个回答

48

这个答案不适用于所链接的具体案例，但适用于问题标题，并且对未来的读者可能是有趣的:

由于有限精度，重复的浮点数加法与乘法并不等价。考虑以下情况:

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

演示

- Ben Voigt

10

这不是对所询问问题的回答。尽管提供了有趣的信息（对于任何 C/C++ 程序员来说都必须知道），但这不是一个论坛，也不属于此处。 - orlp

31

StackOverflow的表述目标是建立一个对未来用户有用的可搜索答案库。而这就是对所提出问题的回答……只是恰巧有一些没有被明确说明的信息，使得这个回答在针对原帖作者时不适用。但它仍然可能适用于其他有同样问题的人。 - Ben Voigt

12

这可能是回答__标题__问题的答案，但不是该问题的答案。 - orlp

7

正如我所说，这是一条有趣的信息。然而，对我来说仍然似乎不正确，值得注意的是问题的__最佳答案__并没有回答当前问题。这不是英特尔编译器决定不优化的原因，就是这样。 - orlp

4

我也认为这是顶部答案似乎不正确。我希望有人发布一个在得分上超过此答案的整数情况下的真正好答案。不幸的是，我认为对于整数情况而言，"不能"没有答案，因为这种转换是合法的，所以我们只能讨论"为什么不"，但实际上这会违反“太局限”关闭的原因，因为它特定于特定编译器版本。在我看来，我回答的问题更加重要。 - Ben Voigt

显示剩余6条评论

6

编译器包含许多优化步骤。通常，在每个步骤中，要么对语句进行优化，要么对循环进行优化。目前没有一种模型能够根据循环头部对循环体进行优化，因为这很难检测并且不常见。

已经完成的优化是循环不变代码移动。可以使用一组技术来实现。

- knightrider

6

现在确实如此 -- 至少，clang是这样做的：

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

整数溢出与此无关；如果有导致未定义行为的整数溢出，它可以在任何一种情况下发生。这里是使用int而不是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

- Jason S

4

我猜很多编译器可能会进行这种优化，假设我们讨论的是整数算术。

同时，有些编译器可能拒绝这样做，因为用乘法代替重复的加法可能会改变代码的溢出行为。对于无符号整型来说，它不应该有任何区别，因为它们的溢出行为完全由语言规定。但对于带符号的整型来说，它可能会（虽然在二进制补码平台上可能不会）。事实上，有符号溢出在 C 中实际上会导致未定义的行为，也就是说忽略溢出语义理论上是完全可以接受的，但并不是所有编译器都勇敢到那个地步。这经常会引起“C 只是高级汇编语言”的人群的批评。（还记得当 GCC 引入了基于严格别名语义的优化时发生了什么吗？）

从历史上看，GCC 已经证明自己是一个有能力采取如此激烈措施的编译器，但其他编译器可能更愿意坚持被认为是“用户预期”的行为，即使这是语言中不确定的。

- AnT stands with Russia

我更愿意知道是否不小心依赖于未定义的行为，但我猜编译器无法知道，因为溢出将是运行时问题 :/ - jhabbott

2

@jhabbott：如果发生溢出，那么行为是未定义的。除非数字在运行时输入，否则无法确定行为是否已定义 :P。 - orlp

2

这种优化存在一个概念上的障碍。编译器作者花费了很多精力在强度降低上，例如用加法和移位来替换乘法。他们习惯于认为乘法是不好的。因此，需要反其道而行之的情况会让人感到惊讶和违反直觉。所以没有人想去实现它。

- zwol

3

用一个封闭形式的计算代替循环也是强度降低，是吗？ - Ben Voigt

严格来说，是的，我想是这样，但我从未听过有人这样谈论它。（不过，我对文献有点过时了。） - zwol

1

开发和维护编译器的人在工作中有限的时间和精力，因此通常希望专注于他们的用户最关心的事情：将良好编写的代码转换为快速的代码。他们不想浪费时间试图将愚蠢的代码变成快速的代码，这就是代码审查的目的。在高级语言中，可能会有“愚蠢”的代码表达了重要的思想，使得开发人员值得花费时间来加速——例如，短路消耗和流式融合允许Haskell程序结构基于某些懒惰产生的数据结构被编译成不分配内存的紧密循环。但是，这种激励方式根本不适用于将循环加法转换为乘法。如果你想它跑得快，那就直接用乘法写吧。

- dfeuer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

编译器通常无法转换。

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，而如果100000次将30000添加到sum中，则如果没有溢出，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所说的，“显然，在循环交换后它没有运行循环折叠过程”。

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

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这样的条件，它可以对正数和负数都成立吗？）。我曾经遇到过编译器进行无效优化的情况（例如，几年前，我使用ICC（11.0，我记得）在1.0/n中使用了有符号32位整数转换为double，其中n是unsigned int。速度是gcc输出的两倍左右。但是错误的是，很多值大于2 ^ 31，糟糕。）。