1

在为布尔数组编写“不等式扫描”的过程中，我最终编写了这个循环：

// 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 循环。这有点不直观，因为加法的循环计数分析应该比 IMO 更简单。我怀疑 gcc 确实知道 s=s+s 循环计数，只是有点害羞。

有谁知道 gcc 的这种行为是否有充分的理由？我是出于好奇问这个...

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

谢谢，罗伯特

4

2 回答 2

0

这是有趣的。

第一个猜测

我的第一个猜测是 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 认为展开效率低下的可能性。

有趣的是，尝试使用 clang at 编译会-O3立即展开循环。众所周知， clang 会更积极地展开，但这似乎不是一个令人满意的答案。

我可以让 gcc 通过使其添加一个常量而不是s自身来展开加法循环，也就是说，我这样做了s = s + 2。然后循环展开。

第二次猜测

这导致我推测如果循环的增加值不止一次地取决于计数器的值，gcc 无法理解循环将运行多少次迭代（展开所必需的）。我改变循环如下：

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

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

于 2016-11-04T22:30:12.327 回答
0

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

如果不是这样，那么我认为这是 gcc 中的一个错误。使用 s+s 计算循环计数的分析（略微）比使用 s*2 的分析更简单，所以我希望 gcc （略微）更有可能展开 s+s 的情况。

于 2016-12-08T19:13:40.667 回答