处理器微架构前端相关
处理器微架构的前端主要负责指令的准备,包括指令拾取(Instruction Fetch)、指令解码(Instruction Decode)和分支预测(Branch Predict)等,其优化主要包括以下两个方面:
- 保证对执行单元稳定的微操作供应:分支预测错误会破坏微操作流,或者导致执行单元在执行非目标分支的微操作流时浪费执行资源,对于这部分的优化,主要集中在分支预测单元上。
- 提供微操作流以尽可能地利用执行带宽和退役带宽:这一方面侧重于保持编译器的高解码吞吐量或保持热代码从解码缓存中运行,对于这部分的优化,主要集中在指令获取与解码优化中。
分支预测优化
分支的优化对性能有很大的影响。通过了解分支的流程并提高它们的可预测性,可以显著提高代码性能。可以帮助分支预测的优化方法有:
保证代码与数据在不同的页(Page)上;
尽可能消除分支;
使代码与静态分支预测算法保持一致;
在自旋等待循环中使用PAUSE指令;
消除分支
消除分支通过降低分支预测错误概率和所需分支目标缓冲区(Branch Target Buffer, BTB)条目数量提升性能,主要方法包括:
- 合理排布代码,使代码块在内存中连续排布;
- 展开循环,降低重复执行循环次数;
- 使用条件传送(Conditional Move, CMOV)指令;
- 使用条件设置(Set Byte on Condition, SETCC)指令;
编译器/汇编规则1 (局部影响:中高,通用性:中)合理排布代码,使代码块在内存中连续排布,并消除不必要的分支;
编译器/汇编规则2 (局部影响:中,通用性:中低)使用条件传送和条件设置指令消除不可预测的条件分支,不要使用这些指令来消除所有不可预测的条件分支(由于这类指令需要执行条件分支的所有路径,因此会带来额外的执行开销);
考虑下述含有条件分支的C代码:
X = (A < B) ? CONST1 : CONST2;
其汇编形式如下所示,可以看到当A和B的数值没有呈现出明显规律时,该分支的结果不可预测:
cmp A, B ;Condition
jbe L30 ;Conditional Branch
mov ebx const1 ;ebx holds X
jmp L31 ;Unconditional Branch
L30:
mov ebx, const2
L31:
...
接下来,通过条件设置指令,可以将不可预测的条件分支消除:
xor ebx, ebx ;Clear ebx (X in the C code)
cmp A, B ;Condition
setge bl ;ebx = 0 when A < B, ebx = 1 when A >= B
sub ebx, 1 ;ebx = 11...1 or 00...0
and ebx, CONST3 ;CONST3 = CONST1 - CONST2, ebx = CONST3 or 0
add ebx, CONST2 ;ebx = CONST1 when A < B, ebx = CONST2 when A >= B
也可以通过条件传送指令消除不可预测的条件分支(x86-64架构下的gcc编译器采用此优化方案):
cmp A, B ;Condition
mov ebx, CONST2 ;ebx = CONST2, and ebx is X in the C code
mov eax, CONST1 ;eax = CONST1
cmovge eax, ebx ;ebx <- eax = CONST1 when A >= B
静态预测
当分支目标缓冲区中没有该分支的历史记录时,条件分支预测一般采用静态算法,即:
- 预测前向条件分支(Forward Conditional Branch, FCB)不发生;
- 预测后向条件分支(Backward Conditional Branch, BCB)发生;
- 预测间接分支(Indirect Branch, IB)不发生;
mov eax, mem
and eax, ebx
imul eax, edx
shld eax, 7
jc Begin ;Forward Conditional Branch
mov eax, 0
Begin: call Convert
Begin: mov eax, mem
and eax, ebx
imul eax, edx
shld eax, 7
jc Begin ;Backward Conditional Branch
Begin: mov ecx, Begin
mov eax, mem
and eax, ebx
imul eax, edx
shld eax, 7
jc ecx ;Indirect Branch
编译器/汇编规则3 (局部影响:中,通用性:高)使代码与静态分支预测算法保持一致,即发生概率高的分支使用后向条件分支,发生概率低的分支使用前向条件分支或间接分支。
内联,调用,与返回
返回地址堆栈是存储返回地址的堆栈,当执行调用指令时,程序计数器的值被压入堆栈,而当执行返回指令时,程序计数器的值则被弹出堆栈,并预测返回指令将会使程序返回到弹出地址处,由于返回指令几乎总是返回到最后一个过程调用指令的地址,因此预测非常准确。但由于返回地址堆栈的大小固定,如果调用和返回链条深度超过堆栈所能容纳的最大嵌套深度,可能会导致程序性能下降。
为充分利用返回地址堆栈机制,调用与返回指令必须成对匹配。
编译器/汇编规则4 (局部影响:中高,通用性:中高)近距离调用必须匹配近距离返回,远距离调用必须匹配远距离返回,不建议手动将返回地址压到堆栈并跳转到要调用的过程上,因为这会造成调用和返回的不匹配。
调用与返回的高昂开销可以通过内联消除,其特点为:
- 可以消除参数传递的开销;
- 在编译器中,对一个函数进行内联会使得编译器获取到更多的优化机会;
- 如果内联过程包含分支,内联所带来的额外上下文信息可以改善分支预测性能;
- 分支预测错误在函数中带来的性能损失要高于内联函数;
编译器/汇编规则5 (局部影响:中高,通用性:中高)如果可以降低代码大小,或所调用函数很小且经常被调用,则可以选择性内联此函数。
编译器/汇编规则6(局部影响:中低,通用性:中低)如果有超过最大嵌套深度的嵌套调用和快速连续返回,可以考虑使用内联函数以减少调用深度。
编译器/汇编规则7(局部影响:中低,通用性:中低)如果分支错误预测导致返回指令被过早预测为执行,可能会导致性能损失,因此当函数包含预测率低的分支时,可以选择性内联此函数。
编译器/汇编规则8(局部影响:低,通用性:低)如果函数中的最后一条语句是对另一个函数的调用,将调用转换为跳转可以节省调用/返回指令的开销及返回地址堆栈缓冲区中的条目。
编译器/汇编规则9(局部影响:中,通用性:低)不要在16
字节代码块中放置超过4
个分支。
编译器/汇编规则10(局部影响:中,通用性:低)不要在16
字节代码块中放置2
个以上的结束循环分支。
对于编译器/汇编规则9和编译器/汇编规则10,猜测与高速缓冲线尺寸有关,仍需继续考证,欢迎讨论。
代码对齐
合理排布代码可以增强缓存和内存的局部性,基本块的可能序列应该在内存中连续排列。
局部性原理:局部性主要分为时间局部性和空间局部性。时间局部性指程序在运行时,最近刚刚被引用过的一个内存位置容易再次被引用,比如在调取函数时,前不久才调取过的本地参数容易再次被使用。空间局部性比较常于循环中,比如在一个数列中,如果第3
个元素在上一个循环中使用,则本次循环中极有可能会使用第4
个元素。
局部性原理可以被用来在处理器内核的指令流水线中进行性能优化,如缓存,内存预读取及分支预测等。
编译器/汇编规则11(局部影响:中,通用性:高)当从解码缓存获取待执行代码时,对于在大多数情况下执行的直接分支,其所有指令应放置在高速缓存线(Cache Line)中,并靠近该高速缓存线的末尾,分支的目标地址应位于或接近高速缓存线的开头,高速缓存线的尺寸视具体架构而定,一般为64
字节。
编译器/汇编规则12(局部影响:中,通用性:高)如果条件分支的代码主体不太可能被执行,则应将其放在程序的另一部分; 如果它极不可能被执行并且代码局部性是需要着重考量的指标,则应将其放置在不同的代码页上。
分支类型选择
间接分支/调用的默认分支预测结果是不发生,如果硬件预测可用于该分支,则默认分支预测结果会被覆盖,间接分支/调用的硬件预测目标为先前执行的分支目标。
编译器/汇编规则13(局部影响:中,通用性:低)当存在间接分支时,尝试将最可能的分支目标紧跟在间接分支之后;如果间接分支出现概率高,但分支预测硬件无法预测,则在间接分支之后跟随一条UD2
(Undefined Instruction)指令,这将阻止处理器沿着后续路径进行解码。
如果一个分支的目标大部分时间指向同一个地址,那么该分支将在大部分时间被准确预测,由于分支目标缓冲区中只能存储一个已获取(非失败)目标,因此具有多个已获取目标的间接分支可能具有较低的预测率。
用户/代码规则1(局部影响:中,通用性:低)如果一个间接分支有两个或多个共同的目标,并且这些目标中的至少一个与导致该分支的分支历史(除最后一个目标外,还包括程序如何到达这一分支的信息)相关,则可以将间接分支转换为一棵树,并在一个或多个间接分支之前,通过条件分支指向原有目标,此方法可以应用于与分支历史相关的间接分支的共同目标。
此建议的目的是通过增强分支的可预测性(即使以添加更多分支为代价)来减少错误预测的总数,因此,添加的分支必须是可预测的。 这种可预测性的一个原因是间接分支与之前的分支历史有很强的相关性。 也就是说,在之前的分支上所采取的预测可以作为当前分支预测的一个重要参考。
下述示例详细解释了用户/代码规则1:
void function() {
int n = rand();
if (!(n & 0x01)) { // n will be 0 half the times
n = 0; // Branch history will be updated.
}
// Indirect branches with multiple taken targets may have lower prediction rates.
switch (n) {
case 0: handle_0();break; // Common Target, correlated with
// branch history that is taken before.
case 1: handle_1();break; // Uncommon Target.
case 3: handle_3();break; // Uncommon Target.
default: handle_others(); // Common Target.
}
}
对于编译器来说,上述代码中的分支间相关性很难通过分析来确定,为了获得最优代码性能,评估采用用户/代码规则1的性能增益是有必要的:
void function ()
{
int n = rand();
if (!(n & 0x01)) {
n = 0; // n will be 0 half the times.
}
if (!n) {
handle_0(); // Peel out the most common target
} // with correlated branch history.
switch (n) {
case 1: handle_1(); break; // Uncommon Target.
case 3: handle_3(); break; // Uncommon Target.
default: handle_other(); // Make the favored target in
// the fall-through path.
}
}
循环展开
循环展开的好处包括:
- 循环展开可以减少分支,并消除管理归纳变量的代码,从而降低分支开销;
- 循环展开允许积极调度(或流水线化)循环以降低延迟;
- 循环展开为其它优化提供机会,例如冗余内存加载的去除和公共子表达式的消除等。
但循环展开也带来了一定问题:
- 代码膨胀;
- 代码可读性降低,除非由编译器透明地执行循环展开;
- 循环体内包含递归时,可能会降低循环展开的性能增益。
编译器/汇编规则14(局部影响:高,通用性:中)展开小循环,直到分支和归纳变量管理的开销占循环执行时间的10%
以下。
编译器/汇编规则15(局部影响:中,通用性:中)展开频繁执行且具有可预测迭代次数的循环,以降低迭代次数(循环展开程度视具体微架构而定,一般在现代Intel
处理器架构下,迭代次数可以达到16次或更少)。除非它增加了代码大小,以至于代码不再匹配指令缓存的大小,否则均应进行循环展开;此外,如果循环体包含多个条件分支,应通过循环展开使迭代次数进一步减小。
void without_unrolling(int x, int y) {
int a[100];
for (int i = 0; i < 100; ++i) {
if (!(i & 0x01)) {
a[i] = x;
}
else {
a[i] = y;
}
}
}
void with_unrolling(int x, int y) {
int a[100];
for (int i = 0; i < 100; i += 2) {
a[i] = y;
a[i + 1] = x;
}
}
在此示例中,循环将x
分配给每个偶数编号的元素,将y
分配给每个奇数编号的元素,通过循环展开可以更有效地进行分配,并消除循环体中的分支。
指令获取与解码优化
指令融合
指令融合将多个微操作融合为一个复杂的微操作,复杂的微操作在乱序执行单元中调度,具有提高指令带宽和降低功耗的优势。指令融合包括:
- 微融合(Micro-fusion):融合的多个微操作来自同一指令;
- 宏融合(Macro-fusion):融合的多个微操作来自不同指令。
编译器/汇编规则16(局部影响:中低,通用性:中)为了提高指令获取与解码吞吐量,如果一条指令能从微融合中受益,那么优先考虑该指令的内存版本,而非寄存器版本。
下列微融合的指令可以被任意解码器处理:
- 所有类型的内存存储(Store)指令(包括立即数的存储),写回内存的指令分为地址存储和数据存储两个步骤;
- 所有读内存与运算的混合指令,如:
ADDPS XMM9, OWORD PTR [RSP+40]
FADD DOUBLE PTR [RDI+RSI*8]
XOR RAX, QWORD PTR [RBP+32]
- 所有读内存与跳转的混合指令,如:
- 操作数为内存和立即数的
CMP
与TEST
指令;
需要注意的是,在下列情况下,具有指令指针寄存器(Instruction Pointer Register, RIP)相对寻址的指令不会被微融合:
- 需要额外的立即数时,如:
CMP [RIP+400], 27
MOV [RIP+3000], 142
- 当指令指针寄存器被用于控制流时,如
JMP [RIP+5000000]
。
对于宏融合操作所融合的指令,第一条必须为CMP
或者TEST
,作用于寄存器之间、寄存器与立即数之间或寄存器与内存之间(内存与立即数之间无法融合),第二条必须为条件跳转指令,并且恰好位于第一条指令之后;此外,CMP
和TEST
指令对第二条指令有不同的匹配要求,并非所有的条件跳转指令都能与第一条指令进行配对融合。
编译器/汇编规则17(局部影响:中,通用性:中低)尽可能使用可以配对的指令进行宏融合,优先选择TEST
指令,尽可能使用无符号整数和无符号跳转,尽量通过逻辑操作验证变量是否为非负数,避免在内存与立即数之间使用CMP
和TEST
指令(但不要通过添加其它指令的方式避免内存与立即数之间的比较)。
对于编译器/汇编规则17,以下例子可以提供参考:
// Without Macro-fusion
for (int i = 0; i < 1000; i++) {
a++;
}
// With Macro-fusion
for (unsigned int i = 0; i < 1000; i++) {
a++;
}
其对应的汇编结果为:
; Without Macro-fusion
mov dword ptr [i], 0
jmp First
Loop:
mov eax, dword ptr [i]
add eax, 1
mov dword ptr [i], eax
First:
cmp dword ptr [i], 3E8H ; Comparison with Memory and Immediate, Inhibit Macro-fusion
jge End
mov eax, dword ptr [a]
addqq eax,1
mov dword ptr [a], eax
jmp Loop
End:
; With Macro-fusion
xor eax, eax
mov dword ptr [i], eax
jmp First
Loop:
mov eax, dword ptr [i]
add eax, 1
mov dword ptr [i], eax
First:
cmp eax, 3E8H ; Comparison with Register and Immediate, Permit Macro-fusion
jae End
mov eax, dword ptr [a]
add eax, 1
mov dword ptr [a], eax
jmp Loop
End:
编译器/汇编规则18(局部影响:中,通用性:中低)当可以从逻辑上确定一个变量在比较时是非负数时,可以触发宏融合;具体地,当将一个变量与0比较时,适当地使用TEST
指令来触发宏融合。
变长指令前缀
指令前缀(Instruction Prefix)一般用于修改操作码(OpCode)解释,分为:
- 重复(
Repeat
)/锁定(Lock
)前缀保证指令将独占使用所有共享内存,直到指令完成执行;
- 字符串操作指令前缀,如
REP
,REPE
和REPNE
等;
- 段覆盖(Segment Override)前缀导致内存访问使用指定的段而不是为指令操作数指定的默认段;
- 操作数尺寸覆盖(Operand Size Override)前缀改变指令的默认模式所期望的数据大小;
- 地址尺寸覆盖(Address Size Override)前缀改变指令的默认模式所期望的地址大小;
参考:http://www.c-jump.com/CIS77/CPU/x86/X77_0240_prefix.htm
一条指令的长度最高可达15字节,指令解码器必须识别到指令的长度,而一些前缀可以动态地改变指令长度,即变长指令前缀。通常情况下,预解码器会在假定没有变长指令前缀的情况下估计字节流中指令的长度,当预解码器在指令获取线(Fetch Line)中遇到变长指令前缀时,则必须使用一个较慢的长度解码算法,导致预解码器在6
个周期内进行解码(通常应在1
个周期内),并且流水线的调度一般不能消除变长指令前缀带来的开销(变长指令前缀停顿)。
可以引起指令长度动态变化的前缀包括:
操作数尺寸前缀(0x66
);
地址尺寸前缀(0x67
)。
当变长指令前缀带来的开销出现在紧循环(Tight Loop)中时,会造成明显的性能下降;但当解码过程并非程序运行的瓶颈时(例如浮点运算密集代码),孤立的变长指令前缀通常不会导致性能下降。
编译器/汇编规则19(局部影响:中高,通用性:中高)倾向于使用8位或32位立即数生成代码,而非16位立即数;当需要使用16位立即数时,加载等价的32位立即数,并仅使用低16位。
双变长指令前缀停顿
导致变长指令前缀停顿的指令在跨越16字节的指令获取线边界时,会导致变长指令前缀停顿触发两次,以下对齐情况可导致双变长指令前缀停顿的发生:
- 一条指令用一个
MODR/M
和SIB
字节进行编码,且指令获取线的边界在MODR/M
和SIB
字节之间。
- 一条指令从指令获取线的
13
偏移量开始,且使用寄存器和立即数字节偏移寻址模式引用一个内存位置。
在双变长指令前缀停顿的情况下,第一次停顿发生在第一个指令获取线上,第二次停顿发生在第二个指令获取线上,将导致2x6-1=11
个周期的惩罚。
下述例子导致单次变长指令前缀停顿,且与指令第一个字节在指令获取线上的位置无关:
ADD DX, 01234H
ADD word ptr [EDX], 01234H
ADD word ptr 012345678H[EDX], 01234H
ADD word ptr [012345678H], 01234H
当指令第一个字节在指令获取线的13
偏移量时,下述例子导致双变长指令前缀停顿:
ADD word ptr [EDX+ESI], 01234H
ADD word ptr 012H[EDX], 01234H
ADD word ptr 012345678H[EDX+ESI], 01234H
(上述例子有待进一步理解)
为了避免双变长指令前缀停顿,不要使用受变长指令前缀停顿影响的指令,即使用MODR/M
和SIB
字节编码或带有字节位移寻址模式的指令。
伪变长指令前缀停顿
伪变长指令前缀停顿与变长指令前缀停顿的特点相同,但发生在没有任何16
位立即数值的指令上。伪变长指令前缀停顿发生在使用F7操作码编码的变长指令前缀指令(not
/neg
/div
/idiv
/mul
/imul
等)且指令位于获取行的偏移量14处时。由于指令长度解码器在下一个指令获取线(包含MODR/M
字节编码的指令操作码)之前无法确定指令长度,伪变长指令前缀也会经历延迟停顿。以下技术可以帮助避免错误的LCP停顿。
- 将F7指令组的所有短操作上报为长操作,使用完整的32位版本;
- 确保F7操作码永远不会从获取行的偏移量14开始。
编译器/汇编规则20(局部影响:中,通用性:中低)确保使用0xF7操作码字节的指令不从获取线的偏移量14开始;并避免使用这些指令对16位数据进行操作,将短数据上传到32位。
循环流检测器
循环流检测器检测具有多个迭代且适合微操作队列的循环,微操作队列将循环流化,直到不可避免的错误分支预测使之结束。循环流检测器提高了指令获取带宽,且在单线程模式下,它通过允许前端睡眠来节省电力;在多线程模式下,前端资源可以更好地服务于其他线程。如果满足以下所有条件,循环就有资格通过循环流检测器被流化:
- 循环体大小不超过
60
微操作,有最多15
个已采取的分支,以及最多15
个64
字节获取线;
- 没有
CALL
或RET
指令
- 没有不匹配的堆栈操作(
PUSH
与POP
不匹配);
- 超过
~20
次的迭代;
许多计算密集型循环、搜索和字符串移动符合这些特征,这些循环超过了分支预测单元的预测能力,并且总是以分支的错误预测结束。
编译器/汇编规则21(局部影响:中高,通用性:中高)将具有长指令序列的循环体分解成不超过循环流检测器大小的短指令块循环。
解码缓存
从解码缓存中运行代码有两个优势:
- 为乱序执行单元提供更高的微操作带宽;
- 处理器前端不需要对解码缓存中的代码进行解码,可以节省功率。
在解码缓存和传统解码流水线之间的切换是有开销的,如果代码在前端和解码缓存之间频繁切换,惩罚可能比只从传统流水线运行要更高。为了确保 "热 "代码从解码缓存中被送入,需要:
- 确保每个热代码块少于
750
条指令。具体来说,不要在一个循环中展开超过750
条指令;
- 对于在一个循环内有非常大的计算块的应用程序,考虑将循环分割成多个适合解码缓存的循环;
- 如果一个程序可以确保每个内核只运行一个线程,它可以将热代码块大小增加到大约
1500
条指令。
密集读取-修改-写入代码
解码缓存在每个32
字节对齐的内存块中最多只能容纳18
个微操作。因此,以少量字节编码但具有许多微操作的指令高度集中的代码可能会溢出18个微操作的限制而不能进入解码缓存,例如读取-修改-写入(Read-Modify-Write, RMW)指令,当编译器针对代码大小进行积极优化时,RMW
指令可能被频繁使用(用1
个指令替代多个指令,可以有效降低代码尺寸)。
RMW
指令接受一个内存源操作数,一个寄存器源操作数,并使用内存源操作数作为目标。 2~3
个指令可以实现相同的功能:第一个读取内存源操作数,第二个执行与第二个寄存器源操作数的操作,最后一个将结果写回内存。 这些指令通常会产生相同数量的微操作,但使用更多字节来编码相同的功能。
以下是一些可能适应解码缓存的解决方案(稀疏化):
- 用两个或三个具有相同功能的指令替换
RMW
指令。 例如,adc [rdi], rcx
只有三个字节长; 等效序列adc rax, [rdi]
+ mov [rdi], rax
占用六个字节;
- 将密集部分分解为两个不同的
32
字节块;
- 通过在循环中添加多个
NOP
指令来分隔代码,需要注意,此解决方案添加了用于执行的微操作。
为解码缓存对齐无条件分支
对于进入解码缓存的代码,每个无条件分支都占用解码缓存路(Decoded ICache Way)的最后一个微操作。因此,每个32
字节对齐块只有3
个无条件分支可以进入解码缓存。无条件分支在跳转表和switch-case
中很常见(与RMW
指令优化同理,使微操作稀疏化):
- 编译器为
C++
虚拟类方法或DLL
调度表创建跳转表,每个无条件分支消耗5
个字节。因此,最多7
个无条件分支可以与32
字节对齐块相关联。如果无条件分支在每个32
字节对齐块中过于密集,则跳转表可能不适合解码缓存,将导致在分支表之前和之后执行的代码的性能下降。 解决的办法是在分支表的分支间添加多字节的NOP
指令(可能会增加代码大小,应谨慎使用)。但是,这些NOP
不会被执行,因此在后面的流水线阶段没有惩罚。
switch-case
结构具有相似的情况,对case
条件的每次评估都会产生一个无条件分支,使用多字节NOP
的相同解决方案可以使结构适合解码缓存。
解码缓存路双分支
一条解码缓存路最多可以容纳两个分支,32
字节对齐块中的密集分支,或者它们与其他指令的顺序可能会阻止块中指令的所有微操作进入解码缓存,可以在适当的地方使用NOP
指令分隔代码,以避免这件事发生。
编译器/汇编规则22(局部影响:中,通用性:中)避免在一系列堆栈操作(POP
/PUSH
/CALL
/RET
)中对ESP
显式引用。
(解码缓存路双分支及编译器/汇编规则22有待进一步理解)
指令获取与解码的其它优化
编译器/汇编规则23(局部影响:中低,通用性:中)使用长度小于 8 个字节的简单指令。
编译器/汇编规则24(局部影响:中,通用性:中高)避免使用前缀来改变立即数/位移的大小。
超过7
个字节的长指令可能会限制每个周期的解码指令数,每个前缀为指令长度增加一个字节,也可能会限制解码器的吞吐量。另外,多个前缀只能由第一个解码器解码(计算机架构中有多个解码器,但每个解码器负责的指令有所差异),这些前缀在解码时也会产生延迟。 如果无法避免多个前缀或改变立即数/位移大小的前缀,可以将它们安排在由于某些其他原因使流水线停止的指令之后。