编译器可以优化不依赖于for循环变量的for循环中的计算吗？

Question

假设我有一个看起来像这样的热循环（它是用 C 语言编写的，但这个问题通常适用于编译命令式语言）：

int max_dist = some_value;

for (int x = min_x; x <= max_x; ++x)
{
    for (int y = min_y; y <= max_y; ++y)
    {
        if (x * x + y * y > max_dist * max_dist)
            continue;
        
        do_something(x, y);
    }
}

像 Roslyn、MSVC 或 GCC 这样的编译器能够优化循环，使其看起来像这样吗？

int max_dist = some_value;
int max_dist_sq = max_dist * max_dist;

for (int x = min_x; x <= max_x; ++x)
{
    int x_sq = x * x;
    for (int y = min_y; y <= max_y; ++y)
    {
        if (x_sq + y * y > max_dist_sq)
            continue;
        
        do_something(x, y);
    }
}

或者这超出了编译器通常尝试的范围？

Answer 1

这称为循环不变代码运动（LICM）并且很常见。也就是说，即使看起来有可能，它也可能不会发生，例如：

• 编译器必须知道，当然，相关计算是不变的，并且可以移动。对于编译器来说，这种分析可能比人类更难理解。
• 根据编译器分配的启发式成本，将计算移出循环可能不会有利可图。这个决定可能是正确的，也可能是错误的，它毕竟只是基于启发式，而不是对这两个选项进行基准测试。

将计算移出循环并不一定会有帮助，因为由于不同的原因，计算的成本可能（几乎）微不足道：例如，延迟有限循环中的备用 ALU 容量，或“免费”操作作为复杂寻址模式的一部分完成。同时，将操作移出循环会占用一个寄存器，该寄存器的生存范围跨越整个循环，这可能会使寄存器分配复杂化，甚至会导致额外的溢出，因此它可能不是免费的。

根据情况，可能会执行其他优化，从而无需使用 LCM。例如，如果在循环中计算的值从未使用过，则计算可能不会被移动而是完全删除。或者，如果一个值是常数，则可能不会有任何关联的计算。例如这段代码：

extern void do_something(int x, int y);

void test(int min_x, int max_x, int min_y, int max_y)
{
    int max_dist = 9999;

    for (int x = min_x; x <= max_x; ++x)
    {
        for (int y = min_y; y <= max_y; ++y)
        {
            if (x * x + y * y > max_dist * max_dist)
                continue;
            
            do_something(x, y);
        }
    }
}

使用 Clang 18.1.0 编译

-O2

，内循环如下所示：

.LBB0_4:                                #   Parent Loop BB0_2 Depth=1
        mov     eax, r12d
        imul    eax, r12d
        add     eax, ebx
        cmp     eax, 99980001
        ja      .LBB0_6
        mov     edi, r15d
        mov     esi, r12d
        call    do_something(int, int)@PLT
        jmp     .LBB0_6

y

在这里是平方的，但是

x * x

是在此循环之外计算的，并且

max_dist * max_dist

是一个常数。

作为另一个例子，如果我更改

max_dist

使其平方超出

int

的范围（以编译时已知的形式触发 UB），那么 Clang 只会对整个事情进行核攻击，所以实际上并没有LCM 值得一提..