为什么 ICC 以这种方式展开这个循环并使用 lea 进行算术运算？

Question

查看 ICC 17 生成的用于迭代 std::unordered_map<>（使用 https://godbolt.org）的代码让我很困惑。

我将示例提炼为：

long count(void** x)
{
  long i = 0;
  while (*x)
  {
    ++i;
    x = (void**)*x;
  }
  return i;
}

使用 ICC 17 编译它，使用 -O3 标志，导致以下反汇编：

count(void**):
        xor       eax, eax                                      #6.10
        mov       rcx, QWORD PTR [rdi]                          #7.11
        test      rcx, rcx                                      #7.11
        je        ..B1.6        # Prob 1%                       #7.11
        mov       rdx, rax                                      #7.3
..B1.3:                         # Preds ..B1.4 ..B1.2
        inc       rdx                                           #7.3
        mov       rcx, QWORD PTR [rcx]                          #7.11
        lea       rsi, QWORD PTR [rdx+rdx]                      #9.7
        lea       rax, QWORD PTR [-1+rdx*2]                     #9.7
        test      rcx, rcx                                      #7.11
        je        ..B1.6        # Prob 18%                      #7.11
        mov       rcx, QWORD PTR [rcx]                          #7.11
        mov       rax, rsi                                      #9.7
        test      rcx, rcx                                      #7.11
        jne       ..B1.3        # Prob 82%                      #7.11
..B1.6:                         # Preds ..B1.3 ..B1.4 ..B1.1
        ret                                                     #12.10

与明显的实现（gcc 和 clang 使用，甚至是 -O3）相比，它似乎做了一些不同的事情：

它展开循环，在循环返回之前有两次递减 - 但是，在这一切的中间有一个条件跳转。
它使用 lea 进行一些运算
它为 while 循环的每两次次迭代保留一个计数器 (inc rdx)，并立即为每次迭代计算相应的计数器（进入 rax 和 rsi）

做这一切的潜在好处是什么？我想这可能与日程安排有关？

只是为了比较，这是 gcc 6.2 生成的代码：

count(void**):
        mov     rdx, QWORD PTR [rdi]
        xor     eax, eax
        test    rdx, rdx
        je      .L4
.L3:
        mov     rdx, QWORD PTR [rdx]
        add     rax, 1
        test    rdx, rdx
        jne     .L3
        rep ret
.L4:
        rep ret

Answer 1

对于它为什么这样做没有明确的答案，因为它是一个专有的编译器。只有英特尔知道为什么。也就是说，英特尔编译器在循环优化方面通常更加积极。这并不意味着它更好。我见过英特尔的积极内联导致性能比 clang/gcc 更差的情况。在那种情况下，我不得不明确禁止在某些调用站点进行内联。同样，有时需要在 Intel C++ 中禁止通过 pragma 展开以获得更好的性能。
lea 是一个特别有用的指令。它允许在一条指令中完成一次移位、两次加法和一次移动。这比将这四个操作分开进行要快得多。但是，它并不总是有所作为。如果 lea 仅用于加法或移动，它可能会更好，也可能不会更好。所以你看到在 7.11 中它使用了一个移动，而在接下来的两行中 lea 用于执行加法加移动，加法，移位，加移动
我没看到这里有可选的好处

Answer 2

这不是一个很好的例子，因为循环会在指针追逐延迟上造成瓶颈，而不是 uop 吞吐量或任何其他类型的循环开销。但是在某些情况下，更少的 uops 可能有助于乱序 CPU 看得更远。 或者我们可以只讨论循环结构的优化并假装它们很重要，例如用于执行其他操作的循环。

展开通常很有用，即使循环行程计数无法提前计算。（例如，在这样的搜索循环中，当它找到哨兵时停止）。未采用的条件分支与采用的分支不同，因为它对前端没有任何负面影响（当它预测正确时）。

基本上 ICC 在展开这个循环时做得很糟糕。 它使用 LEA 和 MOV 来处理 i 的方式相当脑残，因为它使用的微指令比两条 inc rax 指令。（虽然它确实使关键路径更短，但在 IvB 和更高版本上具有零延迟 mov r64, r64，因此乱序执行可以在运行那些 uops 上领先）。

当然，由于这个特定的循环瓶颈对指针追逐的延迟造成了瓶颈，您最多只能获得每 4 个时钟一个的长链吞吐量（Skylake 上的 L1 加载使用延迟，对于整数寄存器），或者在大多数其他英特尔微体系结构上每 5 个时钟一个。（我没有仔细检查这些延迟；不要相信那些特定的数字，但它们差不多是正确的）。

IDK 如果 ICC 分析循环携带的依赖链来决定如何优化。如果是这样，它可能根本就没有展开，如果它在尝试展开时知道自己做得不好的话。

对于短链，乱序执行可能会在循环后的运行处开始，if循环出口分支预测正确。在这种情况下，优化循环很有用。

展开还会在问题上抛出更多分支预测器条目。 而不是一个具有长模式的循环退出分支（例如，在 15 次采用后未采用），您有两个分支。同一个例子，一个没考过，一个考了7次，第8次没考。

这是手写的二元展开实现的样子:

在其中一个退出点的循环退出路径中修复 i，这样您就可以在循环内轻松处理它。

count(void**):
    xor       eax, eax              # counter
    mov       rcx, QWORD PTR [rdi]  # *x
    test      rcx, rcx
    je        ..B1.6
.p2align 4   # mostly to make it more likely that the previous test/je doesn't decode in the same block at the following test/je, so it doesn't interfere with macro-fusion on pre-HSW
.loop:
    mov       rcx, QWORD PTR [rcx]
    test      rcx, rcx
    jz        .plus1

    mov       rcx, QWORD PTR [rcx]
    add       rax, 2
    test      rcx, rcx
    jnz       .loop
..B1.6:
    ret

.plus1:           # exit path for odd counts
    inc       rax
    ret

如果两个 TEST/JCC 对宏融合，这会使循环体有 5 个融合域微指令。 Haswell 可以在单个解码组中进行两次融合，但更早的 CPUs 不能。

gcc 的实现只有 3 微指令，小于 CPU 的问题宽度。请参阅关于从循环缓冲区发出的小循环。没有 CPU 实际上每个时钟可以 execute/retire 多于一个采用的分支，因此不容易测试 CPUs 如何以小于 4 微指令发出循环，但显然 Haswell 可以发出 5 -uop 每 1.25 个周期循环一次。较早的 CPUs 可能只会每 2 个周期发出一次。

为什么 ICC 以这种方式展开这个循环并使用 lea 进行算术运算？

Why does ICC unroll this loop in this way and use lea for arithmetic?

c++

assembly

x86-64

icc