GCC循环展开异常

Question

在对布尔数组进行"不相等扫描"的过程中，我最后写了这个循环:

// Heckman recursive doubling
#ifdef STRENGTHREDUCTION // Haswell/gcc does not like the multiply
    for( s=1; s<BITSINWORD; s=s*2) { 
#else // STRENGTHREDUCTION
    for( s=1; s<BITSINWORD; s=s+s) { 
#endif // STRENGTHREDUCTION
      w = w XOR ( w >> s);
    }

我观察到的是gcc将展开s=s*2循环，但不是s=s+s循环。这有点不直观，因为在我看来，加法的循环计数分析应该更简单而不是乘法。我怀疑gcc确实知道s=s+s循环计数，只是忸怩作态。

有人知道这是否有一些好的理由吗gcc方面的行为?我是出于好奇才问这个问题的。

[展开的版本，顺便说一句，比循环运行得慢一些。]

谢谢,罗伯特。

Answer 1

这很有趣。

第一个猜测

我的第一个猜测是gcc的循环展开分析预计加法情况从循环展开中获益较少，因为s增长得更慢。

我对下面的代码进行了实验:

#include <stdio.h>
int main(int argc, char **args) {
    int s;
    int w = 255;
    for (s = 1; s < 32; s = s * 2)
    {
        w = w ^ (w >> s);
    }
    printf("%d", w); // To prevent everything from being optimized away
    return 0;
}

另一个版本是相同的，除了循环中有s = s + s。我发现gcc 4.9.2在乘法版本中展开循环，而不是加法版本。这是用

编译的

gcc -S -O3 test.c

所以我的第一个猜测是gcc假设添加版本，如果展开，将导致更多字节的代码适合icache，因此没有优化。然而，在添加版本中将循环条件从s < 32更改为s < 4仍然不会导致优化，尽管看起来gcc应该很容易识别出循环的迭代次数很少。

我的下一个尝试(回到s < 32作为条件)是显式地告诉gcc展开循环最多100次:

gcc -S -O3 -fverbose-asm --param max-unroll-times=100 test.c

这仍然会在程序集中产生一个循环。尝试使用——param max-unrolled-insns在展开循环中允许更多指令，也保留了循环。因此，我们几乎可以消除gcc认为展开效率低下的可能性。

有趣的是，在-O3上使用clang编译会立即展开循环。众所周知，Clang的展开更有攻击性，但这似乎不是一个令人满意的答案。

我可以让gcc通过添加一个常量而不是s本身来展开加法循环，也就是说，我执行s = s + 2。然后循环展开。

猜第二次

这导致我推断，如果循环的增加值不止一次依赖于计数器的值，gcc将无法理解循环将运行多少次迭代(展开所必需的)。我将循环修改如下:

for (s = 2; s < 32; s = s*s)

它不与gcc展开，而clang展开它。因此，最后，我最好的猜测是，当循环的增量语句为s = s (op) s形式时，gcc无法计算迭代次数。

Answer 2

编译器通常执行强度降低，所以我希望如此GCC将在这里使用它，将s*2替换为s+s，此时两者的形式源代码表达式将匹配。

如果不是这样，那么我认为这是gcc中的一个bug。分析使用s+s计算循环计数(稍微)简单一些使用s*2，所以我预计gcc将(略微)更有可能展开s+s的情况。