logo标签列表

为什么当循环限制为959时，简单的循环得到了优化，但是当限制为960时却没有？

cgccoptimizationclang
134

考虑这个简单的循环：

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 959; i++)
    p += 1;
  return p;
}

如果您使用gcc 7（快照）或clang（trunk）编译并带有-march=core-avx2 -Ofast，您会得到非常相似的东西。

.LCPI0_0:
        .long   1148190720              # float 960
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

换句话说，它只是将答案设置为960而不需要循环。

但是，如果您更改代码为：

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 960; i++)
    p += 1;
  return p;
}

生成的汇编代码实际执行了循环求和操作吗？例如，clang 的输出结果如下：

.LCPI0_0:
        .long   1065353216              # float 1
.LCPI0_1:
        .long   1086324736              # float 6
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        vxorps  ymm1, ymm1, ymm1
        mov     eax, 960
        vbroadcastss    ymm2, dword ptr [rip + .LCPI0_1]
        vxorps  ymm3, ymm3, ymm3
        vxorps  ymm4, ymm4, ymm4
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        vaddps  ymm0, ymm0, ymm2
        vaddps  ymm1, ymm1, ymm2
        vaddps  ymm3, ymm3, ymm2
        vaddps  ymm4, ymm4, ymm2
        add     eax, -192
        jne     .LBB0_1
        vaddps  ymm0, ymm1, ymm0
        vaddps  ymm0, ymm3, ymm0
        vaddps  ymm0, ymm4, ymm0
        vextractf128    xmm1, ymm0, 1
        vaddps  ymm0, ymm0, ymm1
        vpermilpd       xmm1, xmm0, 1   # xmm1 = xmm0[1,0]
        vaddps  ymm0, ymm0, ymm1
        vhaddps ymm0, ymm0, ymm0
        vzeroupper
        ret

为什么无论是clang还是gcc，如果将float替换为double，相同的循环限制为479。

更新1：

事实证明，gcc 7（快照版）和clang（trunk）的行为差异很大。就我所知，对于所有小于960的限制，clang都会优化掉循环。另一方面，gcc对精确值非常敏感，并没有上限。例如，当限制为200（以及许多其他值）时，它不会优化循环，但当限制为202和20002（以及许多其他值）时，它会优化循环。

3
Sulthan的意思可能是，编译器会展开循环，然后发现加法操作可以合并为一个。如果不展开循环，则无法将这些操作合并。 - Jean-François Fabre
3
它还针对小于959的任何数字进行了优化。 - Simd
6
通常应该使用归纳变量消除来完成这个任务，而不是展开如此庞大的循环。以959的因数展开是非常疯狂的。 - harold
3
960有许多因数（共28个）。不确定这是否对它成为截止点产生影响。 - dan04
4
@eleanora 我玩了一下编译器资源管理器，以下情况似乎成立（仅针对gcc快照版本）：如果循环计数是4的倍数并且至少为72，则循环不会展开（或者说，按4个展开）；否则，整个循环将被替换为一个常量——即使循环计数为2000000001。 我的怀疑是：过早的优化（就像是过早地“嘿，4的倍数，这对展开很好”，阻碍了更深入的优化，而不是更彻底地“这个循环到底有什么问题？”） - Hagen von Eitzen
显示剩余16条评论
3个回答
90

TL;DR

当前快照版本的GCC 7默认表现不一致，而之前的版本由于PARAM_MAX_COMPLETELY_PEEL_TIMES的默认限制为16。可以通过命令行进行覆盖。

限制的理由是防止过度的循环展开，这可能是一个双刃剑。

GCC版本 <= 6.3.0

GCC的相关优化选项是-fpeel-loops, 它会随着标志-Ofast（强调是我的）间接启用：

对于那些已经有足够信息表明它们不滚动（来自配置文件反馈或 静态分析）的剥离循环。它还启用完整的循环剥离（即 完全删除具有小常数迭代次数的循环）。

使用 -O3 和/或 -fprofile-use 启用。

可以通过添加 -fdump-tree-cunroll 来获取更多详细信息：

$ head test.c.151t.cunroll 

;; Function f (f, funcdef_no=0, decl_uid=1919, cgraph_uid=0, symbol_order=0)

Not peeling: upper bound is known so can unroll completely

这条消息来自/gcc/tree-ssa-loop-ivcanon.c：

if (maxiter >= 0 && maxiter <= npeel)
    {
      if (dump_file)
        fprintf (dump_file, "Not peeling: upper bound is known so can "
         "unroll completely\n");
      return false;
    }

因此try_peel_loop函数返回false。
可以使用-fdump-tree-cunroll-details选项获得更详细的输出：
Loop 1 iterates 959 times.
Loop 1 iterates at most 959 times.
Not unrolling loop 1 (--param max-completely-peeled-times limit reached).
Not peeling: upper bound is known so can unroll completely

通过调整max-completely-peeled-insns=n和max-completely-peel-times=n参数，可以调整限制：

max-completely-peeled-insns

The maximum number of insns of a completely peeled loop. 

max-completely-peel-times

The maximum number of iterations of a loop to be suitable for complete peeling.

如果您想了解有关insns的更多信息，可以参考GCC内部手册。

例如，如果您使用以下选项进行编译：

-march=core-avx2 -Ofast --param max-completely-peeled-insns=1000 --param max-completely-peel-times=1000

然后代码变成：

f:
        vmovss  xmm0, DWORD PTR .LC0[rip]
        ret
.LC0:
        .long   1148207104

Clang

我不确定 Clang 具体是做什么的，也不知道如何调整它的限制，但据我观察，你可以通过使用 展开指示#pragma 标记循环来强制其评估最终值，这将完全删除循环：

#pragma unroll
for (int i = 0; i < 960; i++)
    p++;

结果为：

.LCPI0_0:
        .long   1148207104              # float 961
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret
谢谢您提供这个非常好的答案。正如其他人所指出的那样，gcc似乎对确切的限制大小非常敏感。例如，它无法消除循环912 https://godbolt.org/g/EQJHvT。在这种情况下，fdump-tree-cunroll-details会说什么？ - Simd
@elenora：最新的快照表现不一致，但我不确定根本原因。另一方面，6.3.0没有这样的怪异现象。 - Grzegorz Szpetkowski
13
你解释了去皮的机制，但没有说明960的相关性或为什么有一个限制。 - M.M
1
@M.M：GCC 6.3.0和最新的快照之间的剥离行为完全不同。在前者的情况下，我强烈怀疑硬编码限制是由PARAM_MAX_COMPLETELY_PEEL_TIMES参数强制执行的，该参数在/gcc/params.def:321中定义，值为16。 - Grzegorz Szpetkowski
15
你可能希望说明GCC为什么会有意限制循环展开。具体来说，如果你过分地展开循环，二进制文件会变得更大，而且很可能无法适应L1缓存。相对于节省一些条件跳转（假设分支预测良好，你通常会这样认为），缓存未命中可能是非常昂贵的（请参见https://gist.github.com/jboner/2841832）。 - Kevin
显示剩余4条评论
19
在阅读Sulthan的评论后，我猜测：

  1. 如果循环计数器是常量（且不太高），编译器将完全展开循环。

  2. 展开后，编译器会发现求和操作可以合并为一次。

如果由于某些原因未对循环进行展开（这里：使用1000个语句会生成太多的语句），则无法将操作组合。

编译器可能会看到展开1000条语句相当于执行一次加法，但步骤1和2是两个独立的优化，因此它不能冒险展开，因为它不知道操作是否可以合并（例如：函数调用无法合并）。

注意：这是一个特殊情况：谁会使用循环重复添加相同的东西？在这种情况下，请勿依赖编译器可能的展开/优化；直接以一条指令写出正确的操作。

1
那么你能专注于那个“不太高”的部分吗？我的意思是为什么在“100”的情况下风险不存在？我猜测了一些...在我上面的评论中...这可能是原因？ - user2736738
我认为编译器没有意识到浮点不精确性可能会触发它。我猜这只是一种指令大小限制。你可以在“max-unrolled-times”旁边找到“max-unrolled-insns”。 - Jean-François Fabre
啊，这差不多是我的想法或猜测...希望能得到更清晰的推理。 - user2736738
5
有趣的是，如果你将float改为int，即使迭代次数不同，gcc编译器也能够通过归纳变量优化(-fivopts)来加强减少循环。但是这些优化似乎不能用于float。 - Tavian Barnes
1
@CortAmmon 对的，我记得有些人感到惊讶和不满，因为GCC使用MPFR来精确计算非常大的数字，这会给出与等效浮点运算截然不同的结果，而浮点运算会积累误差和精度损失。这表明很多人计算浮点数的方法是错误的。 - Zan Lynx
显示剩余4条评论
12

非常好的问题！

您似乎已经达到了编译器在简化代码时尝试内联迭代或操作次数的限制。正如Grzegorz Szpetkowski所记录的，有特定于编译器的方式使用#pragma或命令行选项来调整这些限制。

您还可以参考Godbolt's Compiler Explorer，比较不同编译器和选项对生成的代码的影响：gcc 6.2和icc 17仍然会内联代码960次，而clang 3.9则不会（默认情况下，它在73次内停止内联）。

我已经编辑了问题，以明确我使用的gcc和clang版本。请参见https://godbolt.org/g/FfwWjL。例如，我正在使用-Ofast。 - Simd
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接