x86的MOV真的可以“免费”吗? 为什么我不能重现这一点?

我一直看到人们声称由于寄存器重命名,MOV指令在x86中可以是免费的。

对于我来说,我无法在单个测试用例中验证这一点。 每一个测试案例我都会尝试揭穿它。

例如,下面是我用Visual C ++编译的代码:

#include <limits.h>
#include <stdio.h>
#include <time.h>

int main(void)
{
    unsigned int k, l, j;
    clock_t tstart = clock();
    for (k = 0, j = 0, l = 0; j < UINT_MAX; ++j)
    {
        ++k;
        k = j;     // <-- comment out this line to remove the MOV instruction
        l += j;
    }
    fprintf(stderr, "%d msn", (int)((clock() - tstart) * 1000 / CLOCKS_PER_SEC));
    fflush(stderr);
    return (int)(k + j + l);
}

这会为循环生成以下汇编代码(无论如何您都可以自由生成此代码;您显然不需要Visual C ++):

LOOP:
    add edi,esi
    mov ebx,esi
    inc esi
    cmp esi,FFFFFFFFh
    jc  LOOP

现在我运行这个程序几次,当MOV指令被删除时,我观察到一个非常一致的2%差异:

Without MOV      With MOV
  1303 ms         1358 ms
  1324 ms         1363 ms
  1310 ms         1345 ms
  1304 ms         1343 ms
  1309 ms         1334 ms
  1312 ms         1336 ms
  1320 ms         1311 ms
  1302 ms         1350 ms
  1319 ms         1339 ms
  1324 ms         1338 ms

那么是什么给了? 为什么不是MOV“免费”? 这个循环对x86来说太复杂了吗?
有没有一个例子可以证明MOV像人们所说的那样是免费的?
如果是这样,那是什么? 如果没有,为什么每个人都声称MOV是免费的?


问题中循环的吞吐量不取决于MOV的延迟,或(在Haswell上)不使用执行单元的好处。

该环路仍然只有4个uops,用于前端发布到乱序内核中。 (即使不需要执行单元, mov仍然必须由无序内核跟踪,但cmp/jc宏 - 融合到单个uop中)。

自从Core2以来,Intel CPU的问题宽度为每个时钟4 uops,所以mov不会阻止它在Haswell上每时钟(靠近)每秒钟执行一次。 它也会在Ivybridge的每个时钟上运行一次(使用mov-elimination),但不会在Sandybridge上运行(不消除mov消除)。 在SnB上,每1.333c周期约需一个周期,对ALU吞吐量产生瓶颈,因为mov总是需要一个 。 (SnB / IvB只有三个ALU端口,而Haswell有四个)。

请注意,重命名阶段的特殊处理对于x87 FXCHG(与st1交换st0 )比MOV更长。 Agner Fog在PPro / PII / PIII(第一代P6内核)上列出FXCHG为0延迟。


问题中的循环有两个互锁的依赖链( add edi,esi取决于EDI和循环计数器ESI),这使得它对不完善的调度更加敏感。 由于看似不相关的指令,对比理论预测的速度下降2%并不罕见,指令顺序的小变化可能会导致这种差异。 要以每秒1c的速度运行,每个周期都需要运行INC和ADD。 由于所有的INCs和ADDs都依赖于前一次迭代,因此无序执行无法在单个周期内运行两次。 更糟糕的是,ADD依赖于前一周期的INC,这就是我所说的“互锁”,所以在INC dep链中丢失一个周期也会拖延ADD dep链。

此外,预测分支只能在port6上运行,因此port6不执行cmp / jc的任何周期都是吞吐量丢失的一个周期 。 每当INC或ADD在端口6上偷一个周期而不是在端口0,1或5上运行时,就会发生这种情况。如果这是罪魁祸首,或者如果在INC / ADD dep链中丢失循环本身就是问题,或者可能是一些都是。

添加额外的MOV不会增加任何执行端口压力,假设它被100%取消,但它确实阻止了前端在执行核心之前运行 。 (循环中的4个uop中只有3个需要执行单元,并且您的Haswell CPU可以在其4个ALU端口中的任何一个上运行INC和ADD:0,1,5和6.所以瓶颈是:

  • 每个时钟的前端最大吞吐量为4 uops。 (没有MOV的环路只有3个uops,所以前端可以跑到前面)。
  • 分支吞吐量每时钟一个。
  • 涉及esi的依赖链(每个时钟1个INC延迟)
  • 涉及edi的依赖关系链(每个时钟的ADD延迟为1,也取决于先前迭代的INC)
  • 如果没有MOV,前端可以在每个时钟周期发出4个循环的三个uops,直到无序内核已满。 (AFAICT,它“解开”循环缓冲(循环流检测微小循环:LSD),所以用ABC微指令的循环可以在ABCA BCAB CABC ...模式发出的性能计数器lsd.cycles_4_uops证实,当它发布任何微软的时候,大多数是4人组。)

    英特尔CPU在端口发出乱序内核时将端口分配给端口。 该决定基于追踪每个端口在调度程序中已经有多少微软的计数器(又名保留站,RS)。 当等待执行的RS中有很多的uops时,这很好,通常应该避免将INC或ADD调度到port6。 我想也可以避免安排INC和ADD,这样任何一个dep链都会丢失时间。 但是如果RS空或接近空,计数器不会阻止ADD或INC窃取端口6上的一个周期。

    我认为我在这里做了一些事情,但是任何次优调度都应该让前端赶上并保持后端充满。 我认为我们不应该期望前端在流水线中产生足够的气泡来解释最大吞吐量下降2%,因为微小的循环应该从循环缓冲区以非常一致的4每时钟吞吐量运行。 也许还有其他事情正在发生。


    mov消除的好处的一个真实例子。

    我使用lea构建了一个每个时钟只有一个mov的循环,创建了一个完美的演示,其中MOV消除100%成功,或0%的时间与mov same,same以展示产生的延迟瓶颈。

    由于宏融合dec/jnz是涉及循环计数器的依赖链的一部分,不完善的调度不能延迟它。 这与每次迭代时cmp/jc “从关键路径依赖链中分离出来”的情况都不同。

    _start:
        mov     ecx, 2000000000 ; each iteration decrements by 2, so this is 1G iters
    align 16  ; really align 32 makes more sense in case the uop-cache comes into play, but alignment is actually irrelevant for loops that fit in the loop buffer.
    .loop:
        mov eax, ecx
        lea ecx, [rax-1]    ; we vary these two instructions
    
        dec ecx             ; dec/jnz macro-fuses into one uop in the decoders, on Intel
        jnz .loop
    
    .end:
        xor edi,edi    ; edi=0
        mov eax,231    ; __NR_exit_group from /usr/include/asm/unistd_64.h
        syscall        ; sys_exit_group(0)
    

    在Intel SnB系列中,寻址模式下具有一个或两个组件的LEA以1c延迟运行(请参阅http://agner.org/optimize/以及x86标记wiki中的其他链接)。

    我在Linux上构建并将其作为静态二进制文件运行,因此整个过程的用户空间性能计数器仅测量启动/关闭开销可忽略的循环。 (与将perf-counter查询放入程序本身相比, perf stat非常简单)

    $ yasm -felf64 -Worphan-labels -gdwarf2 mov-elimination.asm && ld -o mov-elimination mov-elimination.o &&
      objdump -Mintel -drwC mov-elimination &&
      taskset -c 1 ocperf.py stat -etask-clock,context-switches,page-faults,cycles,instructions,branches,uops_issued.any,uops_executed.thread  -r2 ./mov-elimination
    
    Disassembly of section .text:
    
    00000000004000b0 <_start>:
      4000b0:       b9 00 94 35 77          mov    ecx,0x77359400
      4000b5:       66 66 2e 0f 1f 84 00 00 00 00 00        data16 nop WORD PTR cs:[rax+rax*1+0x0]
    
    00000000004000c0 <_start.loop>:
      4000c0:       89 c8                   mov    eax,ecx
      4000c2:       8d 48 ff                lea    ecx,[rax-0x1]
      4000c5:       ff c9                   dec    ecx
      4000c7:       75 f7                   jne    4000c0 <_start.loop>
    
    00000000004000c9 <_start.end>:
      4000c9:       31 ff                   xor    edi,edi
      4000cb:       b8 e7 00 00 00          mov    eax,0xe7
      4000d0:       0f 05                   syscall 
    
    perf stat -etask-clock,context-switches,page-faults,cycles,instructions,branches,cpu/event=0xe,umask=0x1,name=uops_issued_any/,cpu/event=0xb1,umask=0x1,name=uops_executed_thread/ -r2 ./mov-elimination
    
     Performance counter stats for './mov-elimination' (2 runs):
    
        513.242841      task-clock:u (msec)       #    1.000 CPUs utilized    ( +-  0.05% )
                 0      context-switches:u        #    0.000 K/sec                  
                 1      page-faults:u             #    0.002 K/sec                  
     2,000,111,934      cycles:u                  #    3.897 GHz              ( +-  0.00% )
     4,000,000,161      instructions:u            #    2.00  insn per cycle   ( +-  0.00% )
     1,000,000,157      branches:u                # 1948.396 M/sec            ( +-  0.00% )
     3,000,058,589      uops_issued_any:u         # 5845.300 M/sec            ( +-  0.00% )
     2,000,037,900      uops_executed_thread:u    # 3896.865 M/sec            ( +-  0.00% )
    
       0.513402352 seconds time elapsed                                          ( +-  0.05% )
    

    如预期的那样,循环运行1G次( branches 〜= 10亿)。 额外的超过2G的111k周期是其他测试中的开销,也包括没有mov 。 这不是偶尔的mov-elimination失败,而是随着迭代次数的增加而扩展,所以它不仅仅是启动开销。 这可能来自定时器中断,因为IIRC Linux perf在处理中断时不会干扰perf-counter,只是让它们继续计数。 ( perf虚拟化硬件性能计数器,因此即使在线程在CPU之间迁移时,也可以获得每个进程的计数。)另外,共享相同物理内核的同级逻辑内核上的计时器中断会干扰一些事情。

    瓶颈是涉及循环计数器的循环携带依赖链。 1G iters的2G周期是每次迭代2个时钟,或者每个递减1个时钟。 证实dep链的长度是2个周期。 这只有在mov有零延迟时才可能 。 (我知道它并不能证明没有其他瓶颈,如果你不相信我的断言延迟是唯一的瓶颈,那么它确实只能证明延迟最多只有2个周期,有一个resource_stalls.any perf计数器,但它没有很多选项来分解哪些微架构资源耗尽。)

    该循环具有3个融合域uops: movlea和宏融合dec/jnz 。 3G uops_issued.any计数证实:它计算在融合域中,除了调度器(RS)和执行单元之外,它是从解码器到引退的所有流水线。 (宏指令对在所有地方都保持单一uop状态,仅用于商店或ALU +负载的微融合,ROB中的1个融合域uop跟踪两个未融合域uop的进展。)

    2G uops_executed.threaduops_executed.thread -domain)告诉我们,所有的mov uops都被消除了(即,通过发布/重命名阶段来处理,并且以已执行的状态放置在ROB中)。 它们仍然占用uop缓存中的问题/退休带宽和空间,以及代码大小。 它们在ROB中占用空间,限制无序窗口大小。 mov指令永远不会自由。 除了延迟和执行端口之外,还有许多可能的微架构瓶颈,最重要的通常是前端4倍的问题率。

    在Intel CPU上,零延迟通常比不需要执行单元更重要,特别是在Haswell和后来有4个ALU端口的情况下。 (但是其中只有3个可以处理矢量微操作,所以未消除的矢量移动将更容易成为瓶颈,特别是在没有很多负载或商店的代码中,从ALU微处理器开始获得前端带宽(每个时钟4个融合域微操器)另外,将uops安排到执行单元并不完美(更像是最先做好准备的),所以不在关键路径上的uops可能会从关键路径中窃取周期。)

    如果我们在循环中放入一个nop或一个xor edx,edx ,这些也会在Intel SnB系列CPU上发布但不能执行。

    零延迟mov-elimination可用于从32位扩展到64位,以及8到64位。( movzx eax, bl被消除, movzx eax, bx不是)。


    没有mov消除

    mov ecx, ecx      # Intel can't eliminate  mov same,same
    lea ecx, [rcx-1]
    
    dec ecx
    jnz .loop
    
     3,000,320,972      cycles:u                  #    3.898 GHz                      ( +-  0.00% )
     4,000,000,238      instructions:u            #    1.33  insn per cycle           ( +-  0.00% )
     1,000,000,234      branches:u                # 1299.225 M/sec                    ( +-  0.00% )
     3,000,084,446      uops_issued_any:u         # 3897.783 M/sec                    ( +-  0.00% )
     3,000,058,661      uops_executed_thread:u    # 3897.750 M/sec                    ( +-  0.00% )
    

    这需要1G迭代的3G周期,因为依赖链的长度现在是3个周期。

    融合域uop计数没有改变,仍然是3G。

    现在变化的是现在的未融合域uop数与融合域相同。 所有的微软都需要一个执行单元; 没有任何mov指令被淘汰,所以它们都给循环运行的dep链增加了1c的延迟。

    (当有微uops_executed ,比如add eax, [rsi]uops_executed可以高于uops_issued ,但我们没有。)


    完全没有mov

    lea ecx, [rcx-1]
    
    dec ecx
    jnz .loop
    
    
     2,000,131,323      cycles:u                  #    3.896 GHz                      ( +-  0.00% )
     3,000,000,161      instructions:u            #    1.50  insn per cycle         
     1,000,000,157      branches:u                # 1947.876 M/sec                  
     2,000,055,428      uops_issued_any:u         # 3895.859 M/sec                    ( +-  0.00% )
     2,000,039,061      uops_executed_thread:u    # 3895.828 M/sec                    ( +-  0.00% )
    

    现在我们回到循环运行dep链的2个周期延迟。

    没有东西被淘汰。


    我在3.9GHz i7-6700k Skylake上测试过。 对于所有的perf事件,Haswell i5-4210U的结果都相同(在1G计数内为40k)。 这与在同一系统上重新运行的误差大致相同。

    请注意,如果我以root身份运行perf ,并计算cycles而不是cycles:u (仅用户空间),它会测量CPU频率精确到3.900 GHz。 (IDK为什么Linux只在重新启动后服从max turbo的bios设置,但是如果我让它闲置几分钟,则会降至3.9GHz。Asus Z170 Pro游戏主板,Arch Linux,内核4.10.11-1-ARCH 。用Ubuntu写同样的东西写balance_performance到每个/sys/devices/system/cpu/cpufreq/policy[0-9]*/energy_performance_preference from /etc/rc.local修复它,但是写balance_power使它回落再到3.9GHz。)


    你应该在AMD Ryzen上得到相同的结果,因为它可以消除整数mov 。 AMD推土机系列只能消除xmm寄存器副本。 (根据Agner Fog的说法, ymm寄存器副本是一个被取消的低半部分,而ALU则是高半部分)。

    例如,AMD Bulldozer和Intel Ivybridge每个时钟的吞吐量可以达到1

     movaps  xmm0, xmm1
     movaps  xmm2, xmm3
     movaps  xmm4, xmm5
     dec
     jnz .loop
    

    但是英特尔Sandybridge无法消除动作,所以它会对3个执行端口的4个ALU uops造成瓶颈。 如果它是pxor xmm0,xmm0而不是movaps,那么SnB也可以在每个时钟中持续一次迭代。 (但是推土机系列不能,因为xor-zeroing仍然需要AMD的执行单元,尽管它独立于旧的寄存器值,而Bulldozer系列的PXOR只有0.5c的吞吐量。)


    mov消除的局限性

    连续两条相关的MOV指令揭示了Haswell和Skylake之间的区别。

    .loop:
      mov eax, ecx
      mov ecx, eax
    
      sub ecx, 2
      jnz .loop
    

    Haswell:较小的运行间差异(1.746到1.749 c / iter),但这是典型的:

     1,749,102,925      cycles:u                  #    2.690 GHz                    
     4,000,000,212      instructions:u            #    2.29  insn per cycle         
     1,000,000,208      branches:u                # 1538.062 M/sec                  
     3,000,079,561      uops_issued_any:u         # 4614.308 M/sec                  
     1,746,698,502      uops_executed_core:u      # 2686.531 M/sec                  
       745,676,067      lsd_cycles_4_uops:u       # 1146.896 M/sec                  
    

    并非所有的MOV指令都被消除了:每次迭代2次中有0.75次使用了一个执行端口。 每个执行而不是被消除的MOV会为循环运行的dep链增加1c的延迟,所以uops_executedcycles非常相似并不是巧合。 所有的uops都是单个依赖链的一部分,所以没有可能的并行性。 无论运行间uops_executed如何, cycles总是比uops_executed高出大约5M,所以我猜测其他地方只有5M周期。

    Skylake:比HSW结果更稳定,更多的mov消除:每2个MOV需要一个执行单元,只有0.6666个MOV。

     1,666,716,605      cycles:u                  #    3.897 GHz
     4,000,000,136      instructions:u            #    2.40  insn per cycle
     1,000,000,132      branches:u                # 2338.050 M/sec
     3,000,059,008      uops_issued_any:u         # 7014.288 M/sec
     1,666,548,206      uops_executed_thread:u    # 3896.473 M/sec
       666,683,358      lsd_cycles_4_uops:u       # 1558.739 M/sec
    

    在Haswell, lsd.cycles_4_uops占了所有的lsd.cycles_4_uops 。 (0.745 * 4〜= 3)。 所以在几乎每一个发出uops的循环中,都会发出一个完整的4个循环(来自循环缓冲区),我应该看看另一个不关心它们来自哪里的计数器,比如uops_issued.stall_cycles来计数周期没有uops发出)。

    但是在SKL上, 0.66666 * 4 = 2.66664小于3,所以在某些周期中,前端发布的数量少于4个。 (通常它会停止运行,直到在乱序核心中有空间发出一个完整的4个组,而不是发出非完整组)。

    这很奇怪,IDK确切的微架构限制是什么。 由于循环只有3次,所以4次uop的每个问题组都超过了完整的迭代次数。 所以一个问题组最多可以包含3个相关的MOV。 也许Skylake有时会打破这种局面,让更多的mov消除?

    更新 :实际上,这对于Skylake上的3-uop循环是正常的。 uops_issued.stall_cycles表明HSW和SKL发出一个简单的3 uop循环,没有mov-elimination,就像它们发出这个一样。 所以更好的mov-elimination是出于其他原因分解问题组的副作用。 (这不是瓶颈,因为无论分发速度有多快,分支机构每个时钟的执行速度都不会超过1个)。 我仍然不知道为什么SKL不同,但我不认为这是值得担心的。


    在一个不太极端的情况下,SKL和HSW是相同的,两个MOV指令都没有消除0.3333:

    .loop:
      mov eax, ecx
      dec eax
      mov ecx, eax
    
      sub ecx, 1
      jnz .loop
    

     2,333,434,710      cycles:u                  #    3.897 GHz                    
     5,000,000,185      instructions:u            #    2.14  insn per cycle         
     1,000,000,181      branches:u                # 1669.905 M/sec                  
     4,000,061,152      uops_issued_any:u         # 6679.720 M/sec                  
     2,333,374,781      uops_executed_thread:u    # 3896.513 M/sec                  
     1,000,000,942      lsd_cycles_4_uops:u       # 1669.906 M/sec                  
    

    所有的uops以4个组为单位发布。任何连续的4个uop组将包含两个可作为消除候选的MOV uop。 由于它明显成功地消除了一些周期,因此IDK为什么不能总是这样做。


    英特尔的优化手册说,尽可能早地覆盖mov-elimination的结果可以释放微架构资源,以便更频繁地获得成功,至少对于movzx来说是movzx 。 见例3-25。 重新排序序列以提高零延迟MOV指令的有效性。

    那么也许它是在内部使用有限尺寸的ref-counts表进行追踪的? 如果物理寄存器文件条目不再需要作为原始体系结构寄存器的值,则必须停止该物理寄存器文件条目的释放,如果它仍然需要作为mov目标的值。 尽快释放PRF条目是关键,因为PRF大小可以将乱序窗口限制为小于ROB大小。

    我尝试了Haswell和Skylake上的例子,发现mov-elimination事实上在这么做的时候确实有更多的工作时间,但实际上它在总周期中实际上稍慢,而不是更快。 这个例子是为了展示IvyBridge的好处,它可能在其3个ALU端口上出现瓶颈,但是HSW / SKL仅仅是dep链中资源冲突的瓶颈,似乎并不需要为更多的ALU端口提供ALU端口movzx说明。

    另请参见XCHG reg,为什么要在现代英特尔架构上使用3微操作指令? 进行更多的研究+猜测消除运动的方式,以及它是否可以用于xchg eax, ecx 。 (在实践中, xchg reg,reg是英特尔的3个ALU uops,但是2个排除了Ryzen上的uops。猜测Intel是否可以更有效地实现它是很有趣的。)


    顺便说一句,作为Haswell uops_executed.thread的解决方法,Linux在启用超线程时不提供uops_executed.thread ,只有uops_executed.core 。 另一个内核肯定是空闲的,甚至没有定时器中断,因为我使用echo 0 > /sys/devices/system/cpu/cpu3/online离线了它。 不幸的是,这不能在perf决定启用HT之前完成,而我的Dell笔记本电脑没有BIOS选项来禁用HT。 所以,我不能让perf使用所有8个硬件PMU计数器立即在该系统上,只有4:/


    这里有两个小测试,我认为这些测试确实证明了mov-elimination:

    __loop1:
        add edx, 1
        add edx, 1
        add ecx, 1
        jnc __loop1
    

    __loop2:
        mov eax, edx
        add eax, 1
        mov edx, eax
        add edx, 1
        add ecx, 1
        jnc __loop2
    

    如果mov向一个依赖链增加一个周期,那么预计第二个版本每次迭代大约需要4个周期。 在我的Haswell中,每次迭代都需要大约2个周期,如果没有mov消除就不会发生。

    链接地址: http://www.djcxy.com/p/28769.html

    上一篇: Can x86's MOV really be "free"? Why can't I reproduce this at all?

    下一篇: Why are mov ah,bh and mov al, bl together much faster than single instruction mov ax, bx?