查看 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)相比，它似乎做了一些不同的事情:

1. 它展开循环，在返回之前进行两次递减 - 然而，在这一切的中间有一个条件跳转。
2. 它使用 lea 进行一些算术计算
3. 它为 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

最佳答案

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

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

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

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

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

对于短链，无序执行可能能够在循环之后开始运行某些东西，如果循环导出分支预测正确。在这种情况下，优化循环很有用。

展开还会针对该问题抛出更多分支预测器条目。您有两个分支，而不是一个具有长模式的循环退出分支(例如，在 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 可以在单个解码组中进行两次融合，但早期的 CPU 不能。

gcc 的执行只有 3 uops，小于 CPU 的 issue width。参见 this Q&A关于从循环缓冲区发出的小循环。没有 CPU 实际上可以每个时钟执行/退出超过一个采用的分支，因此不容易测试 CPU 如何发出小于 4 微指令的循环，但显然 Haswell 可以每 1.25 个周期发出一个 5 微指令循环。早期的 CPU 可能只会每 2 个周期发出一次。

关于c++ - 为什么 ICC 以这种方式展开这个循环并使用 lea 进行算术运算？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41081115/