现代CPU须在指令预取pipeline stage具备性能良好的分支预测器，以给pipeline后端供应充足有效的指令。
大多数CPU会使用 BTB（Branch Target Buffer）或BTAC(Branch Target Address Cache)，Global History Buffer 和 RAS（Return Address Stack） 等部件来分别预测程序中分支语句和函数返回的跳转地址，较新的CPU还可能采用Gshare, TAGE的预测算法。有关这些算法，可以在公开网络找到很多相关信息。
在实践过程中，有时碰到和分支预测相关性能问题，这篇文章分享一下。
问题描述
在某些arm CPU平台上（这次是cortex-r8），跑业务代码，通过PMU观测到分支预测错误的数量比较高，由于这段代码是业务关键部分，明显影响了系统性能。但是如果修改某些跳转无关代码，可以大幅减少分支错误预测数量。
问题分析
由于客户无法分享业务代码，也不能提供简单可以复现的代码，无法定位诸多跳转指令的哪些跳转导致。和客户一起分析实验，排除一些猜测之后，根据我对CPU的理解，怀疑和分支指令地址对齐可能有关系。经过仔细分析反汇编代码中的很多分支跳转，并且在不同的代码位置插入不同数量的NOP指令（空操作，用于填充）的性能测试实验，得到了一些数据。
CPU分支预测BTAC一般采用组相连(set-associative)方式设计。一个BTAC表项记录之前跳转过的指令类型和指令的部分地址(tag)，跳转目标地址。其工作方式和cache类似，如果CPU采用2 ways set-associative, 跳转指令地址(PC)的部分当成Tag, 部分当成Index用于检索BTAC，再对比PC的Tag和Index检索到的那两个BTAC表项中Tag。
某些CPU的Index的粒度为16-byte, 也就是每对齐的16-byte的地址块对应一个Index, 而每个Index中（16-byte block）只能记录2个branch, 因为其是2 ways set-associative。而当一个16-byte block里面有多于2个branch时，就会出现branch alias的问题。如果指令为32bit长度时，在16-byte block里出现多于2条跳转指令的概率是比较小的（４条指令中有３以上的branch），但在Thumb指令中出现的概率就会高一些。
BTAC中出现branch alias之后，会影响分支预测的准确率。
问题简化复现
基于此猜测，我试着去构造一些测试。然而这类问题，你不想它出现时它幽灵般游荡，你想要它出现时却不好造出来。经过一些尝试，终于可以复现它了。
测试代码：
for (i=0;i<N;i++)
{
switch (i&0x3) {
case (0):
ret=func0();
ret=ret+1;
break;
case (1):
ret=func1();
ret=ret+2;
break;
case (2):
ret=func2();
ret=ret+3;
break;
default :
break;
}
sum=sum+ret;
}利用GCC 11.3加-mcpu=cortex-r8, 编译出来的汇编代码为：
106c: e3a05000 mov r5, #0
1070: e3046e20 movw r6, #20000 ; 0x4e20
1074: e1a00005 mov r0, r5
1078: e1a04005 mov r4, r5
107c: ea000005 b 1098 <test+0x58>
1080: e3530000 cmp r3, #0
1084: 0a000014 beq 10dc <test+0x9c>
1088: e2844001 add r4, r4, #1
108c: e1540006 cmp r4, r6
1090: e0855000 add r5, r5, r0
1094: 0a00000a beq 10c4 <test+0x84>
1098: e2043003 and r3, r4, #3
109c: e3530001 cmp r3, #1
10a0: 0a00000a beq 10d0 <test+0x90>
10a4: e3530002 cmp r3, #2
10a8: 1afffff4 bne 1080 <test+0x40>
10ac: eb000041 bl 11b8 <func2>
10b0: e2844001 add r4, r4, #1
10b4: e2800003 add r0, r0, #3
10b8: e1540006 cmp r4, r6
10bc: e0855000 add r5, r5, r0
10c0: 1afffff4 bne 1098 <test+0x58>
10c8: e1a00005 mov r0, r5
10cc: e8bd8070 pop {r4, r5, r6, pc}
10d0: eb000032 bl 11a0 <func1>
10d4: e2800002 add r0, r0, #2
10d8: eaffffea b 1088 <test+0x48>
10dc: eb000029 bl 1188 <func0>
10e0: e2800001 add r0, r0, #1
10e4: eaffffe7 b 1088 <test+0x48>
通过PMU观测到的数据为:
CPU cycles数: 418049
Branch mispredicted数: 11539
Branches总数: 105008可以看到其中有３条指令在同一对齐16-byte的block中：
10a0: 0a00000a beq 10d0 <test+0x90>
10a4: e3530002 cmp r3, #2
10a8: 1afffff4 bne 1080 <test+0x40>
10ac: eb000041 bl 11b8 <func2>然后通过加入一个NOP指令到代码中：
__asm("NOP");
for (i=0;i<N;i++)
{
switch (i&0x3) {
case (0):
ret=func0();
ret=ret+1;
break;
case (1):
ret=func1();
ret=ret+2;
break;
case (2):
ret=func2();
ret=ret+3;
break;
default :
break;
}
sum=sum+ret;
}
得到的汇编代码为：
106c: e320f000 nop {0}
1070: e1a00005 mov r0, r5
1074: e1a04005 mov r4, r5
1078: ea000005 b 1094 <test+0x54>
107c: e3530000 cmp r3, #0
1080: 0a000014 beq 10d8 <test+0x98>
1084: e2844001 add r4, r4, #1
1088: e1540006 cmp r4, r6
108c: e0855000 add r5, r5, r0
1090: 0a00000a beq 10c0 <test+0x80>
1094: e2043003 and r3, r4, #3
1098: e3530001 cmp r3, #1
109c: 0a00000a beq 10cc <test+0x8c>
10a0: e3530002 cmp r3, #2
10a4: 1afffff4 bne 107c <test+0x3c>
10a8: eb000041 bl 11b4 <func2>
10ac: e2844001 add r4, r4, #1
10b0: e2800003 add r0, r0, #3
10b4: e1540006 cmp r4, r6
10b8: e0855000 add r5, r5, r0
10bc: 1afffff4 bne 1094 <test+0x54>
10c4: e1a00005 mov r0, r5
10c8: e8bd8070 pop {r4, r5, r6, pc}
10cc: eb000032 bl 119c <func1>
10d0: e2800002 add r0, r0, #2
10d4: eaffffea b 1084 <test+0x44>
10d8: eb000029 bl 1184 <func0>
10dc: e2800001 add r0, r0, #1
10e0: eaffffe7 b 1084 <test+0x44>
通过PMU观测到的数据为:
CPU cycles数: 265258
Branch mispredicted数: 15
Branches总数: 105008可以看到NOP的加入避免了３条指令在同一对齐16-byte的block中：
109c: 0a00000a beq 10cc <test+0x8c>
――――16-byte boundary―――――
10a0: e3530002 cmp r3, #2
10a4: 1afffff4 bne 107c <test+0x3c>
10a8: eb000041 bl 11b4 <func2>对比两个测试数据可以发现：加入NOP减少了很多的branch miss predict, 对这段代码，提升了一倍的性能。
问题解决和扩展
对于客户的问题，建议他们把这段代码编译为ARM code, 可以完美规避这个问题，得到很大的性能提升。
Arm的一些其他CPU，如Cortex-A9, Cortex-A75也有类似的特性。其中公开的Cortex-A75 Software Optimization Guide文档中，https://developer.arm.com/doc... ，也提到
类似问题偶尔也碰到几次。如果你也不巧碰到类似的问题（概率很小），可以从这方面考虑一下，或许有帮助。
