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

Question

这是在阅读 Mysticial 的精彩回答时想到的一个问题。问题:why is it faster to process a sorted array than an unsorted array ？

所涉及类型的上下文:

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

优化器认识到它们是等价的，因此是 exchanging the loops , 将分支移到内部循环之外。非常聪明!

但为什么它不这样做呢？

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

希望 Mysticial(或其他任何人)能给出同样出色的答案。我以前从未了解过其他问题中讨论的优化，所以对此我真的很感激。

Answer 1

编译器一般不能转换

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 位 int 具有回绕功能，而将 30000 添加到 sum 100000 次，如果没有溢出，则增加 sum 3000000000)。请注意，对于具有不同数字的无符号数量，100000 * data[c] 的溢出通常会引入一个不得出现在最终结果。

它可以将它转化为

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

不过，如果像往常一样，long long 比 int 足够大。

为什么它不这样做，我说不出来，我猜是因为什么Mysticial said ，“显然，它不会在循环交换后运行循环崩溃 channel ”。

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

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

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

不过，我不太确定编译器是否考虑到了这一点(@Mysticial，您可以尝试使用像 data[c] & 0x80 这样的条件吗？正值和负值？)。我让编译器进行了无效的优化(例如，几年前，我有一个 ICC(11.0，iirc)在 1.0/n 中使用 signed-32-bit-int-to-double 转换，其中n 是一个 unsigned int。大约是 gcc 输出速度的两倍。但错误的是，很多值都大于 2^31，糟糕。)。