我一直看到人们声称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
什么给出了什么?为什么MOV不“免费”?这个循环对于x86来说太复杂了吗? 是否有一个例子可以证明MOV像人们声称的那样是免费的? 如果是这样,它是什么?如果没有,为什么每个人都声称MOV是免费的?
问题中循环的吞吐量不依赖于MOV的延迟,或(在Haswell上)不使用执行单元的好处。
对于前端发出无序核心,循环仍然只有4微秒。 (即使它不需要执行单元,mov
仍然必须被无序核心跟踪,但是cmp/jc
宏融合成一个单独的uop)。
自Core2以来,Intel CPU的每个时钟的问题宽度为4 uop,因此mov
不会阻止它在Haswell上每个时钟执行一次(接近)。它也会在Ivybridge上每次运行一次(使用mov-elimination),但不会在Sandybridge上运行(没有mov-elimination)。在SnB上,它将是每1.333c周期大约一个,在ALU吞吐量上存在瓶颈,因为mov
总是需要一个。 (SnB / IvB只有三个ALU端口,而Haswell有四个)。
请注意,重命名阶段的特殊处理对于x87 FXCHG来说(与st0
交换st1
)比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上运行时就会发生这种情况。如果这是罪魁祸首,或者如果INC / ADD dep链中丢失循环本身就是问题,或者可能两者中的一些。
添加额外的MOV不会增加任何执行端口压力,假设它已经消除了100%,但它确实阻止了前端在执行核心之前运行。 (循环中4个uop中只有3个需要一个执行单元,Haswell CPU可以在其4个ALU端口中的任何一个上运行INC和ADD:0,1,5和6.所以瓶颈是:
esi
的依赖链(每个时钟的INC延迟为1)edi
的依赖关系链(每个时钟的ADD延迟为1,并且还取决于前一次迭代的INC)如果没有MOV,前端可以每时钟4个发出循环的三个微指令,直到无序核心已满。 (AFAICT,it "unrolls" tiny loops in the loop-buffer (Loop Stream Detector: LSD), so a loop with ABC uops can issue in an ABCA BCAB CABC ... pattern. lsd.cycles_4_uops
的perf计数器证实,当它发出任何uops时,它主要以4个为一组发布。)
Intel CPUs assign uops to ports as they issue into the out-of-order core。该决定基于计数器,该计数器跟踪调度程序(也称为预约站,RS)中每个端口已经有多少uop。当RS中有大量的uop等待执行时,这很有效,通常应避免将INC或ADD调度到port6。而且我猜也避免安排INC和ADD,以便从这些dep链中的任何一个丢失时间。但是如果RS为空或接近空,则计数器不会阻止ADD或INC在端口6上窃取一个周期。
我以为我在这里做了一些事情,但任何次优调度应该让前端赶上并保持后端满。我认为我们不应该期望前端在管道中产生足够的气泡来解释低于最大吞吐量2%的下降,因为微小的环路应该以非常一致的4个时钟吞吐量从环路缓冲器运行。也许还有别的事情发生了。
mov
elimination.我使用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计数器仅测量循环,启动/关闭开销可忽略不计。 (与将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
性能计数器,但它没有很多选项来分解哪些微架构资源已经耗尽。)
该循环有3个融合域uops:mov
,lea
和macro-fused dec/jnz
。 3G uops_issued.any
计数证实:它在融合域中计数,这是从解码器到退役的所有流水线,除了调度程序(RS)和执行单元。 (宏融合指令对在任何地方都保持单个uop。只有商店的微融合或ALU +负载,the ROB中的1个融合域uop跟踪两个未融合域uop的进度。)
2G uops_executed.thread
(unfused-domain)告诉我们所有的mov
uops都被消除了(即由发布/重命名阶段处理,并且在已经执行的状态下放置在ROB中)。他们仍然占用问题/退休带宽,uop缓存中的空间和代码大小。它们占用了ROB中的空间,限制了无序窗口大小。 mov
指令永远不会自由。除了延迟和执行端口之外,还存在许多可能的微体系结构瓶颈,最重要的通常是前端的4宽发布率。
在Intel CPU上,零延迟通常比不需要执行单元更重要,特别是在Haswell以及后来有4个ALU端口的情况下。 (但是其中只有3个可以处理向量uop,因此未消除的向量移动将更容易成为瓶颈,特别是在没有很多负载或存储的代码中,从ALU uops获取前端带宽(每个时钟4个融合域uop)另外,将uop调度到执行单元并不完美(更像是最早就绪的),因此不在关键路径上的uop可以从关键路径中窃取循环。)
如果我们将nop
或xor edx,edx
放入循环中,那些也会发出但不会在Intel SnB系列CPU上执行。
零延迟mov-elimination对于从32位到64位以及8到64位的零扩展非常有用。(movzx eax, bl
is eliminated, movzx eax, bx
isn't)。
所有支持mov-elimination的当前CPU都不支持mov same,same
,因此选择不同的寄存器用于从32位到64位的零扩展整数,或者在极少数情况下将vmovdqa xmm,xmm
零扩展到YMM,这是必要的。 (除非你需要在寄存器中的结果它已经存在。弹跳到另一个寄存器并返回通常更糟。)而在英特尔,同样适用于movzx eax,al
。 (AMD Ryzen没有移动删除movzx。)Agner Fog的指令表显示mov
在Ryzen上一直被淘汰,但我猜他的意思是它在两个不同的注册表之间不会像英特尔那样失败。
我们可以利用这个限制来创建一个有目的地击败它的微基准。
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计数与融合域相同。所有的uops都需要一个执行单元;没有任何mov
指令被消除,因此它们都为循环携带的dep链添加了1c延迟。
(当存在微融合的uops,如add eax, [rsi]
时,uops_executed
计数可能高于uops_issued
。但我们没有。)
mov
at all: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上测试过。对于所有性能事件,我在Haswell i5-4210U上获得相同的结果(在1G计数中超出40k)。这与在同一系统上重新运行的误差大致相同。
请注意,如果我将perf
作为root1运行,并计算cycles
而不是cycles:u
(仅限用户空间),则它将CPU频率精确地测量为3.900 GHz。 (IDK为什么Linux只在重启后才服从max turbo的bios设置,但如果我让它闲置几分钟则降到3.9GHz。华硕Z170 Pro游戏主板,Arch Linux内核4.10.11-1-ARCH在Ubuntu上看到同样的事情。将balance_performance
写入/sys/devices/system/cpu/cpufreq/policy[0-9]*/energy_performance_preference
的每个/etc/rc.local
修复它,但写balance_power
使它再次降回到3.9GHz。)
1:更新:作为运行sudo perf
的更好的替代方案,我在kernel.perf_event_paranoid = 0
中设置了sysctl /etc/syctl.d/99-local.conf
您应该在AMD Ryzen上获得相同的结果,因为它可以消除整数mov
。 AMD Bulldozer系列只能消除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 uop的瓶颈。如果它是pxor xmm0,xmm0
而不是movaps,SnB也可以维持每个时钟一次迭代。 (但Bulldozer家族不能,因为xor-zeroing仍需要AMD的执行单元,即使它与寄存器的旧值无关。而Bulldozer-family只有0.5c的PXOR吞吐量。)
连续两个相关的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指令都被消除:每次迭代中约有0.75使用执行端口。执行而不是被消除的每个MOV都会为循环携带的dep链增加1c的延迟,因此uops_executed
和cycles
非常相似并不是巧合。所有uops都是单个依赖链的一部分,因此不存在并行性。 cycles
总是比uops_executed
高出约5M,无论运行间的变化如何,所以我猜在其他地方只有5M周期用完了。
Skylake:比HSW结果更稳定,更多移动消除:每2只需要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
占了所有的uops。 (0.745 * 4~ = 3)。所以在几乎每个发布任何uop的周期中,都会发出一个完整的4组(来自循环缓冲区。我可能应该看一个不关心它们来自哪里的不同计数器,比如uops_issued.stall_cycles
来计算周期没有发布uops)。
但是在SKL上,0.66666 * 4 = 2.66664
小于3,因此在某些周期中,前端的发布不到4次。 (通常它会停止,直到无序核心中的空间发出一个完整的4组,而不是发出非完整的组)。
这很奇怪,IDK确切的微架构限制是什么。由于循环只有3个uop,因此每个4个uop的发布组不仅仅是完整的迭代。因此,问题组最多可包含3个依赖MOV。也许Skylake有时会打破它,以允许更多的移动消除?
更新:实际上这对于Skylake的3-uop循环来说是正常的。 uops_issued.stall_cycles
表明HSW和SKL发出一个简单的3 uop循环,没有mov-elimination,就像发布这个循环一样。因此,更好的移动消除是由于某些其他原因而拆分问题组的副作用。 (这不是瓶颈,因为无论发出多快,所采用的分支都不能以超过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
所有的uops都以4个为一组进行发布。任何连续的4个uop组都将包含两个MOV uop,它们是淘汰的候选者。由于它在某些周期中明显成功地消除了两者,因此IDK为什么不能总是这样做。
Intel's optimization manual说,尽早覆盖mov-elimination的结果可以释放微架构资源,这样它就能更频繁地成功,至少对于movzx
来说。见例3-25。重新排序序列以提高零延迟MOV指令的有效性。
那么也许在内部跟踪一个有限大小的引用计数表?如果物理寄存器文件条目不再需要作为原始架构寄存器的值(如果它仍然需要作为mov目标的值),则必须停止释放物理寄存器文件条目。尽快释放PRF条目是关键,因为PRF size can limit the out-of-order window要小于ROB大小。
我在Haswell和Skylake上尝试了一些例子,发现mov-elimination确实在更多的时候做了更多的工作,但是它实际上在总周期中稍微慢了一些,而不是更快。该示例旨在显示IvyBridge的好处,它可能在其3个ALU端口上存在瓶颈,但HSW / SKL仅是dep链中资源冲突的瓶颈,并且似乎不需要ALU端口来解决更多问题。 movzx
说明。
另请参阅Why is XCHG reg, reg a 3 micro-op instruction on modern Intel architectures?以获取更多关于mov-elimination如何工作的猜测和猜测,以及它是否适用于xchg eax, ecx
。 (实际上,xchg reg,reg
在英特尔上有3个ALU uop,但有2个在Ryzen上消除了uops。有趣的是猜测英特尔能否更有效地实现它。)
顺便说一句,作为Haswell的错误解决方案,Linux在启用超线程时不提供uops_executed.thread
,只有uops_executed.core
。另一个核心肯定是空闲的,甚至没有计时器中断,because I took it offline with echo 0 > /sys/devices/system/cpu/cpu3/online
。不幸的是,在perf
决定启用HT之前无法完成此操作,而且我的戴尔笔记本电脑没有禁用HT的BIOS选项。所以我无法让perf
在该系统上同时使用所有8个硬件PMU计数器,只有4.:/
以下是两个小测试,我相信这些测试最终会显示出消除移动的证据:
__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-elimination就不会发生。