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

Question

这是在阅读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];

希望神秘主义者（或其他任何人）可以给出同样出色的答案。我之前从未了解过其他问题中讨论的优化，所以我非常感谢。

score 106 · 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，则乘积将变为具有回绕-1294967296的典型 32 位s，而 100000 次加上 30000会，如果不溢出，增加3000000000）。请注意，对于具有不同数字的无符号量也是如此，溢出通常会引入一个不能出现在最终结果中的约简模数。intsumsum100000 * 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] & 0x80or 这样的条件，这对于正值和负值来说都是正确的？）。我让编译器进行了无效的优化（例如，几年前，我有一个 ICC（11.0，iirc）使用有符号的 32 位整数到双精度转换，1.0/n其中n是一个unsigned int。大约是 gcc 的两倍输出。但是错了，很多值都大于2^31，哎呀。）。

score 48 · Accepted Answer

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

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

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

演示

score 6 · Accepted Answer

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

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

score 4 · Accepted Answer

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

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

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

score 4 · Accepted Answer

现在可以了——至少，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

整数溢出与它无关；如果存在导致未定义行为的整数溢出，则在任何一种情况下都可能发生。这是使用代替的相同类型的函数intlong：

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

score 2 · Accepted Answer

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

score 1 · Accepted Answer

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

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

7 回答 7

Related

Reference