为什么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;
}

使用-O3标志对ICC 17进行编译会导致以下反汇编:

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

Answer 1

这不是一个很好的例子,因为循环在指针追逐延迟方面存在微不足道的瓶颈,而不是uop吞吐量或任何其他类型的循环开销.但是,可能存在这样的情况:较少的uops可以帮助无序的CPU看到更远的地方. 或者我们可以谈谈对循环结构的优化并假装它们很重要,例如对于做其他事情的循环.

一般情况下,展开可能是有用的,即使循环行程计数不能提前计算.(例如在像这样的搜索循环中,当它找到哨兵时停止).未采用的条件分支与采用的分支不同,因为它对前端没有任何负面影响(当它正确预测时).

基本上ICC只是做了一个糟糕的工作展开这个循环. 它使用LEA和MOV处理的方式i是相当大脑,因为它使用了比两条inc rax指令更多的uops .(尽管它确实使关键路径更短,但在IvB及更高版本上具有零延迟mov r64, r64,因此无序执行可以在运行那些uop时提前).

当然,由于这个特定的循环会阻碍指针追踪的延迟,因此您最多可获得每4个时钟一个的长链吞吐量(Skylake上的L1负载使用延迟,整数寄存器),或者每5个一个大多数其他英特尔微体系结构上的时钟.(我没有仔细检查这些延迟;不要相信那些特定的数字,但它们是正确的).

IDK如果ICC分析循环携带的依赖链以决定如何优化.如果是这样的话,它可能根本就没有完全展开,如果它知道它在尝试展开时做得很差.

对于短链,如果 loop-exit分支正确预测,乱序执行可能能够在循环之后运行某些东西.在这种情况下,优化循环是有用的.

展开还会在问题上引发更多分支预测器条目. 你有两个分支,而不是一个带有长模式的循环出口分支(例如,在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融合域uops.Haswell可以在单个解码组中进行两次融合,但早期的CPU不能.

gcc的实现只有3个uop,小于CPU的发布宽度.请参阅此问答,了解从循环缓冲区发出的小循环.没有CPU实际上每个时钟可以执行/退出一个以上的分支,因此不太可能测试CPU如何发出小于4微秒的循环,但显然Haswell可以每1.25个循环发出一个5-uop循环.早期的CPU可能每2个周期只发一次.