x86的MOV真的可以“免费”吗？为什么我不能复制这个呢？

Question

我一直看到有人声称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 ms\n", (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

那是什么呢？为什么电影不是“免费的”？这个循环对于x86来说太复杂了吗<有没有一个例子可以证明MOV像人们所说的那样是自由的<如果是，是什么？如果不是，为什么每个人都声称MOV是免费的？

Answer 1

以下是两个小测试，我认为它们最终证明了mov消除的证据：

__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，这是不可能发生的。

Answer 2

注册副本对于前端来说从来都不是免费的，只有通过以下CPU上的发布/重命名阶段才能在后端实际执行：

• AMD推土机系列用于XMM矢量寄存器，而不是整数

问题中循环的吞吐量不取决于MOV的延迟，也不取决于（Haswell）不使用执行单元的好处。

循环仍然只有4个UOP供前端发布到无序后端。（mov即使不需要执行单元，也必须由无序后端跟踪，但宏会融合到单个uop中）。

自Core 2以来，Intel CPU的问题宽度为每时钟4 UOP，因此mov不会阻止它在Haswell上每时钟执行一个iter（接近）。它也会在Ivybridge上以每个时钟运行一次（使用mov消除），但在Sandybridge上不会运行（没有mov消除）。在SnB上，大约是每1.333c周期一个iter，ALU吞吐量瓶颈，因为mov总是需要一个iter。（SnB/IvB只有三个ALU端口，而Haswell有四个）。

请注意，重命名阶段的特殊处理对于x87 FXCHG（与st1交换st0）来说比MOV长得多。Agner Fog将FXCHG列为PPro/PII/PIII（第一代P6内核）上的0延迟。

问题中的循环有两个互锁的依赖链（add edi， esi依赖于EDI和循环计数器ESI），这使得它对不完美的调度更加敏感。由于看似不相关的指令，与理论预测相比，2%的减速并不罕见，指令顺序的微小变化可能会产生这种差异。要以每位正好1c的速度运行，每个循环都需要运行一个INC和一个ADD。由于所有INC和ADD都依赖于之前的迭代，因此乱序执行无法通过在单个循环中运行两个来赶上。更糟糕的是，ADD依赖于上一个周期中的INC，这就是我所说的“互锁”，因此在INC dep链中失去一个周期也会使ADD dep链停顿。

此外，预测获取的分支只能在port6上运行，因此port6不执行cmp/jc的任何循环都是吞吐量丢失的循环。每次INC或ADD窃取port6上的循环而不是在端口0、1或5上运行时都会发生这种情况。IDK，如果这是罪魁祸首，或者如果INC/ADD dep链本身中的丢失循环是问题，或者两者兼而有之。

添加额外的MOV不会增加任何执行端口压力，假设它已消除100%，但它确实会阻止前端在后端执行单元之前运行。（循环中4个UOP中只有3个需要执行单元，Haswell CPU可以运行INC并添加其4个ALU端口中的任何一个：0、1、5和6。因此，瓶颈是：

• 前端最大吞吐量为每个时钟4个UOP。（没有MOV的环路只有3个UOP，因此前端可以提前运行）
• 每个时钟的分支吞吐量为1
• 涉及esi的依赖链（INC延迟为每个时钟1次）
• 涉及edi的依赖链（每个时钟增加1个延迟，还取决于上一次迭代的INC）

如果没有MOV，前端可以以每个时钟4的速度发出环路的三个UOP，直到无序后端满为止。（AFAICT，它“展开”循环缓冲区中的微小循环（循环流检测器：LSD），因此带有ABC UOP的循环可以在ABCA BCAB CABC中发出。。。图案lsd的性能计数器。cycles\u 4\u UOP确认，在发布任何UOP时，它主要以4人一组的形式发布。）

英特尔CPU在端口发出到乱序后端时将uops分配给端口。该决定基于计数器来跟踪调度程序中每个端口的uops数量（又名Reservation Station，RS）。当RS中有大量uops等待执行时，这很有效，通常应该避免将INC或ADD调度到port6。我想还可以避免调度INC和ADD，从而避免这些dep链中的任何一个丢失时间。但是如果RS为空或几乎为空，计数器不会阻止ADD或INC窃取port6上的周期。

我认为我在这里有所发现，但是任何次优调度都应该让前端赶上并保持后端满员。我认为我们不应该期望前端在管道中引起足够的泡沫来解释低于最大吞吐量2%的下降，因为小循环应该以非常一致的每时钟4个吞吐量从循环缓冲区中运行。也许还有别的原因。

我使用lea构建了一个每个时钟只有一个mov的循环，创建了一个完美的演示，其中mov消除100%成功，或者使用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-Counters只测量循环，启动/关闭开销可以忽略不计。（perf stat与将perf-Counter查询放入程序本身相比非常容易）

$ 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次（分支~=10亿）。超过2G的“额外”111k周期是其他测试中也存在的开销，包括没有mov的测试。这不是因为偶尔出现的mov消除失败，而是因为迭代次数增加，所以不仅仅是启动开销。这可能是计时器中断造成的，因为IIRCLinuxperf在处理中断时不会乱动perf计数器，只是让它们继续计数。（perf虚拟化了硬件性能计数器，因此即使线程跨CPU迁移，您也可以获得每个进程的计数。）此外，共享相同物理内核的兄弟逻辑内核上的计时器中断会有点干扰。

瓶颈是涉及循环计数器的循环承载依赖链。1G ITER的2G周期为每次迭代2个时钟，或每次减量1个时钟。这证实dep链的长度为2个周期。只有当mov的延迟为零时，这才可能实现。（我知道这并不能证明没有其他瓶颈。如果你不相信我关于延迟是唯一瓶颈的断言，它实际上只能证明延迟最多为2个周期。有一个资源暂停。任何性能计数器，但它没有很多选项来分解耗尽了哪些微体系结构资源。）

环路有3个融合域UOP：mov、lea和宏融合的dec/jnz。3G已发布uops\U。任何计数都确认：它在融合域中计数，这是从解码器到退役的所有管道，除了调度程序（RS）和执行单元。（宏融合指令对在任何地方都保持为单个uop。只有在存储或ALU加载的微融合中，ROB中的1个融合域uop才能跟踪两个未融合域uop的进度。）

2G执行uops\U。线程（未使用的域）告诉我们，所有mov UOP都已消除（即，由发布/重命名阶段处理，并以已执行状态放置在ROB中）。它们仍然占用问题/失效带宽、uop缓存中的空间和代码大小。它们占据了ROB中的空间，限制了无序窗口的大小。mov指令从来都不是免费的。除了延迟和执行端口之外，还有许多可能的微体系结构瓶颈，最重要的往往是前端的4宽问题率。

在Intel CPU上，零延迟通常比不需要执行单元更重要，尤其是在Haswell和更高版本中，那里有4个ALU端口。（但其中只有3个可以处理向量UOP，因此未消除的向量移动更容易成为瓶颈，尤其是在没有大量加载或存储的代码中，前端带宽（每个时钟4个融合域UOP）远离ALU UOP。此外，将UOP调度到执行单元并不完美（更像是最早的就绪优先），因此不在关键路径上的UOP可以从关键路径窃取周期。）

如果我们将nop或xor edx、edx放入循环，这些也会发出，但不会在Intel SnB系列CPU上执行。

零延迟mov消除对于从32位到64位的零扩展以及8位到64位的零扩展非常有用。（movzx-eax，bl已消除，movzx-eax，bx未消除）。

所有支持mov消除的当前CPU都不支持它用于mov same，same，所以在罕见的情况下，为从32位到64位的零扩展整数选择不同的寄存器，或者为从vmovdqa xmm，xmm到零扩展到YMM的寄存器。（除非您需要寄存器中的结果，否则它已经在寄存器中。跳转到不同的寄存器并返回通常更糟。）例如，在Intel上，这同样适用于movzx eax、al。（AMD Ryzen没有消除movzx。）Agner Fog的指令表显示了在Ryzen上总是被消除的mov，但我猜他的意思是，它不能像在Intel上那样在两个不同的reg之间失败。

我们可以利用这一限制创建一个故意击败它的微观基准。

mov ecx, ecx      # CPUs 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% )

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

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

改变的是，现在未融合的域uop计数与融合的域相同。所有UOP都需要一个执行单元；没有一条mov指令被删除，因此它们都为环载dep链增加了1c延迟。

（当存在微熔合UOP时，如添加eax、[rsi]，执行的UOP\u计数可能高于发布的UOP\u，但我们没有。）

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-6700kSkylake上进行了测试。对于所有perf事件，我在Haswell i5-4210U上得到了相同的结果（在1G计数的40k内）。这与在同一系统上重新运行的误差幅度大致相同。

请注意，如果我以root1运行perf，并计算周期而不是周期：u（仅限用户空间），它会将CPU频率测量为恰好3.900 GHz。（IDK为什么Linux只在重新启动后立即遵守max turbo的bios设置，但如果我让它空闲几分钟，则会降至3.9GHz。华硕Z170 Pro Gaming mobo，ArchLinux内核4.10.11-1-ARCH。在Ubuntu中看到了同样的事情。将balance_performance写入每个/sys/设备/system/cpu/cpufreq/策略[0-9]*/energy_performance_preferencefrom/etc/rc.local修复它，但编写balance_power会使它稍后再次回落到3.9GHz。）

1：更新：作为运行sudo perf的更好选择，我在/etc/syctl. d/99-local.conf中设置sysctlkernel.perf_event_paranoid=0

在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

但Intel Sandybridge无法消除移动，因此它将在3个执行端口的4个ALU UOP上出现瓶颈。如果它是PX或xmm0，xmm0而不是movaps，那么SnB也可以支持每个时钟一次迭代。（但是推土机系列不能，因为异或归零仍然需要AMD上的执行单元，即使它独立于寄存器的旧值。而推土机系列对于PXOR只有0.5c的吞吐量。）

一行中的两个相关MOV指令暴露了Haswell和Skylake之间的差异。

.loop:
  mov eax, ecx
  mov ecx, eax

  sub ecx, 2
  jnz .loop

哈斯韦尔：较小的运行间变化（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\U和循环非常相似并非巧合。所有UOP都是单个依赖链的一部分，因此不可能存在并行性<无论运行到运行的变化如何，代码>周期总是比执行的uops\U高出约5M，所以我猜在其他地方只有500万个周期被使用。

Skylake：比HSW结果更稳定，并且更多的mov消除：每2个MOV中只有0.6666个需要执行单元。

 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占了所有的uops。（0.745*4~=3）。因此，几乎在发出任何uops的每个循环中，都会发出一组完整的4（来自循环缓冲区。我可能应该查看一个不同的计数器，它不在乎它们来自哪里，比如uops_issued.stall_cycles来计算没有发出uops的循环）。

但在SKL上，0.66666*4=2.66664小于3，因此在某些周期中，前端发出的UOP少于4个。（通常它会暂停，直到无序后端有足够的空间来发布4个完整组，而不是发布非完整组）。

很奇怪，IDK微架构的确切限制是什么。由于循环只有3个uops，每个4个uops的问题组不仅仅是一个完整的迭代。所以一个问题组最多可以包含3个依赖的MOV。也许Skylake的设计有时会打破这种局面，以允许更多的mov消除？

更新：实际上，这对于Skylake上的3-uop循环是正常的<代码>uops\U发布。stall\u cycles显示HSW和SKL发出一个简单的3 uop循环，没有mov消除，与发出此循环的方式相同。因此，更好地消除mov是出于其他原因而拆分问题组的副作用。（这不是一个瓶颈，因为无论分支发出的速度有多快，每个时钟执行的速度都不能超过1个）。我仍然不知道SKL为什么不同，但我不认为这有什么好担心的。

在不太极端的情况下，SKL和HSW是相同的，两者都未能消除每2个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                  

所有UOP以4人一组的形式发布。任何连续的4个UOP组将正好包含两个MOV UOP，它们是候选的消除对象。由于它在某些周期中显然成功地消除了这两种情况，IDK解释了为什么它不能始终做到这一点。

英特尔的优化手册说，尽早覆盖mov消除的结果可以释放微架构资源，以便它可以更频繁地成功，至少对于movzx。参见示例3-23。重新排序序列以提高零延迟MOV指令的有效性。

那么，也许它是通过一个有限大小的参考计数表进行内部跟踪的？当物理寄存器文件条目不再需要作为原始体系结构寄存器的值时，如果它仍然需要作为mov目标的值，则必须阻止它被释放。尽快释放PRF条目是关键，因为PRF大小可以将无序窗口限制为小于ROB大小。

我在Haswell和Skylake上尝试了这些例子，发现mov消除实际上在这样做的时候起作用的时间要长得多，但实际上它在总循环中稍微慢一点，而不是更快。该示例旨在展示IvyBridge的优势，它可能会在其3个ALU端口上出现瓶颈，但HSW/SKL只会在dep链中的资源冲突上出现瓶颈，并且似乎不会为更多的movzx指令需要一个ALU端口而烦恼。

另请参见为什么XCHG reg，reg是现代英特尔体系结构上的3微操作指令？更多关于mov消除如何工作的研究猜测，以及它是否适用于xchg eax、ecx。（实际上，在Intel上，reg是3个ALU UOP，但在Ryzen上有2个消除了UOP。猜测Intel是否可以更有效地实现它很有意思。）

顺便说一句，作为Haswell上勘误表的解决方法，Linux在启用超线程时不提供uops_executed.thread，只有uops_executed.core。另一个核心肯定一直处于空闲状态，甚至没有计时器中断，因为我使用ech0使其离线