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

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

希望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位ints并带有环绕,而100000次将添加30000 sum,如果是不溢出,增加sum3000000000).注意,同样适用于无符号数量,具有不同的数字,溢出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,iirc)使用signed-32-bit-int-to-double转换,1.0/n其中na unsigned int.的速度大约是gcc的两倍.输出.但错了,很多值都比2^31oops大.)

Answer 2

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

由于精度有限,重复浮点加法不等于乘法.考虑:

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

演示:http://ideone.com/7RhfP

Answer 3

现在确实如此——至少 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

Answer 4

编译器包含执行优化的各种传递.通常在每次传递中,都会对语句或循环优化进行优化.目前还没有基于循环头进行循环体优化的模型.这很难检测,也不太常见.

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