前言
随着现代程序体量的膨胀，处理器面临越发巨大的前端压力；BTB作为前端的核心组件之一，在微架构的演进中也备受厂商重视。本专栏也不是第一次涉猎BTB相关的话题了：
为了应对巨大的程序代码段带来的海量跳转指令，大部分高性能处理器核心的BTB容量都在不断扩展，前有IBM z系列史诗级的16K+128K（用于mainframe，纯服务器环境），后有Intel GoldenCove、RaptorCove的6K+12K（用于包括消费级在内的商业环境）。其他主流厂家也不逞多让，AMD Zen4（1K+7K）、胎死腹中的三星猫鼬M5、M6等等无一例外拥有巨大的BTB；唯一的例外恐怕是苹果，由于其采用了不一样的前端设计故BTB容量较小，这里暂且不讨论。ARM公版核心主攻移动市场并正向服务器市场进军，不妨看看ARM在BTB设计上采用了什么策略。
本文在8cx Gen3平台上探究了ARM Cortex X1 BTB的基本构造，并对其部分怪异表现作出了猜想，对其部分算法给出了粗糙刻画；结论并不收敛，欢迎讨论。
背景故事
一台开发机（Microsoft windows dev kit 2023）的奇妙旅程：康涅狄格 → 纽约 → 香港 → 澳门 → 湛江 → 广州 → 北京。个人对此类设备抱有极大的好奇与好感，无论是当初的zen/zen+还是后来的m1；而8cx gen3算是第一代真正可用的高通desktop soc了，自然不能错过。但是微软在国内并不对个人出售dev kit，故只能代购转运，也就有了它跋山涉水游历四方的传奇旅途。我们的实验平台便是8cx gen3，其配备了4颗Cortex X1和4颗Cortex A78，本次我们专注于Cortex X1（下文简称X1）的表现。
拿在手里还有点好看，难道这就是田牌的信仰之力吗=-=正文
测试构建
为了反应BTB的容量和速度，我们需要尽量构建一个只有分支指令的测试；根据处理器执行分支指令的性能，BTB的行为可以被大致推演。BTB的设计千奇百怪，其中的学问也十分深奥；但是其基本原理并不复杂，为了构建测试我们需要用到几个BTB的基本特性（简略的）：
- 每个表项记录一条（不一定，比如Zen4在部分情况下可以记录两条）分支指令的PC（不一定是全PC）和其对应的跳转目标地址（不一定是全PC）。
- 只有Taken分支会被BTB记录（不一定）。
既然如此，我们不妨使用一连串非条件跳转，每一条分支指令直接跳转到下一条分支指令。
1: b 1f // b即非条件跳转指令，1f（1 forward）即下一个标号11: b 1f1: b 1f1: b 1f1: b 1f1: b 1f
BTB的设计维度很宽广，那么会影响BTB性能的除了物理上确定的容量和延迟还有什么呢？
- 组织形式。组相联、全相联。
- 索引（index）算法。如果BTB使用了组相联设计，为了提高其在面对不同指令排布时的性能表现，往往会对Set的索引index进行Hash处理。
- Tag 算法。为了减少BTB的存储开销，其往往不会存储分支指令的全PC，因此Tag经历了Hash处理。
- 替换算法。
- 预取算法。
前3点都与指令的PC息息相关，而指令的PC是由指令的排布决定的，我们只需要改变指令的排布即可。为了改变指令的排布我们可以在分支指令间插入一定数量的nop指令，它们不会影响处理器的其他行为，因为现代处理器往往配备了nop指令消除机制（本专栏中的其他文章介绍过），nop指令在经过译码级以后即被消除，不需要被重命名和执行。ARM是定长指令集，指令长度为4 Byte；在不插入nop指令时分支指令的密度为1 br per 4 Byte，即紧紧相连。倘若我们想让所有分支指令的PC的差值为8 Byte，只需在相邻分支指令间插入1条nop指令。
1: b 1f // b即非条件跳转指令，1f（1 forward）即下一个标号1
nop1: b 1f
nop1: b 1f
nop1: b 1f
nop
让所有分支指令的PC的差值为16 Byte，只需在相邻分支指令间插入3条nop指令。
1: b 1f // b即非条件跳转指令，1f（1 forward）即下一个标号1
nop
nop
nop1: b 1f
nop
nop
nop1: b 1f
nop
nop
nop1: b 1f
nop
nop
nop
- 对于全相联的BTB，Tag Hash算法会影响其实际可用容量。倘若分支指令A与分支指令B的PC经过hash之后的值相等，那它们会被视为同一条分支指令，进而产生冲突。
- 对于组相联的BTB，Index与Tag Hash算法会影响其实际可用容量。Index决定了指令会进入哪一个set；每一个set的容量上限为路数，下限由Tag的Hash算法决定，倘若分支指令A与分支指令B的PC经过hash之后的值相等，那它们会被视为同一条分支指令，进而产生冲突导致每个set的容量小于路数。
那么随着我们改变总的分支指令数和它们的排布时，BTB的有效容量会出现抖动；一旦有分支指令经历了BTB miss就会导致分支预测错误，进而导致流水线回滚，每条分支指令的平均执行时长会间接反映这些事件。实际上大部分平台上可以直接通过perf stat抓取相关事件来确认BTB行为，但是本人是在dev kit 2023的WSL2内进行实验（本就不方便，即便安装了microsoft wsl的perf也无法正确识别8cx gen3的性能计数器），X1的perf event又懒得去找（嘿嘿），所以就只能通过执行时长这一较为间接的指标来判断了。但是这也导致了本文只能给出极为粗糙的刻画，因为影响大段分支指令执行速度的因素远不止BTB，还包括：ICacha，uopCache，ITLB等；想要得到相对精确的结论只能通过观察BTB的性能计数器。
此类测试的构建细节在本专栏的其他文章内有详细讲解。简而言之，整个程序分为外循环与内循环，内循环为N组b指令和用于填充的nop指令（指令块）；我们不仅仅使用1个指令块，否则循环相关的指令占比过大，它们不是我们计时的对象，需要通过通过放置N个指令块稀释。外循环为M次循环（多次执行使得总执行时间足够长，方便计时），则共会执行N*M次指令块；我们将总执行时长除以N*M，再通过频率信息就可以得出每个指令块执行所需的cycle数，而每个指令块中仅包含1条b指令。
//测试程序示意，实际程序为嵌入汇编：for(int i=0;i<M;i++){
//共N组b和nop
1: b 1f
nop
1: b 1f
nop
......
1: b 1f
nop
1: b 1f
nop
1:}
注意：
- 尾部需要放置一个标号1以便最后一个b跳转到正确的位置。
- for循环部分需要使用嵌入式汇编实现，否则会引入巨量的栈相关代码影响N较小时的计时精确性；倘若使用的是性能计数器指标而非执行时长指标则无需注意这一点。
基本信息
运行测试后我们将数据整理并绘图：
上图包含了海量信息，我们不妨选定橘黄色曲线并观察其延迟跳变的位置：
- 当分支指令数量小于96条时，平均每条分支指令的执行延迟仅有0.5 cycle；即此时ARM Cortex X1每周期预测2条taken分支且代价为0。这是十分了不起的特性，并不是传统BTB能够实现的。考虑最朴素的设计，（每周期2 taken的BTB当然不会简单得如此设计，只是借此说明这一特性并不平凡）BTB的输入为当周期的PC0，一旦第一条分支指令taken，则PC0会覆写为PC1；以PC1作为输入再次查询BTB，我们才能得到第二条分支，而这也是一条taken分支；那么我们需要将PC1更新为PC2再进入下一周期。上述串行流程都需要在同一个时钟周期内完成，可想而知会给处理器带来巨大的时序压力，进而导致产品无法运行在高频（ARM Cortex X1 能够以短流水线运行在3+GHz，每周期的时间并不宽裕）。现如今的其他消费级处理器中仅有Intel的新产品12代、13代酷睿（GoldenCove等）拥有与之匹敌的特性。96项也对应着X1的L0 BTB容量。
- 当分支指令大于96条小于8192条时，平均每条分支指令的执行延迟仅有1-2 cycle；即此时X1每周期预测1条taken分支的代价在0-1间波动。8192项也对应着X1的L1 BTB容量，容量如此巨大的BTB延迟却如此之低（1-1.5）简直匪夷所思。作为参照，12K项的Intel GoldenCove BTB延迟为2，7K项的AMD Zen4 BTB延迟为1.5-2。
总体而言X1的BTB表现十分惊艳，我们也获得了许多有趣的信息，比如：当前的所有每周期2 taken分支设计都只能在L0 BTB的容量范围内生效，应该是为此对L0 BTB进行了特别优化，用于处理较小的密集分支代码块，提高该场景的性能；这一取舍十分合理，密集的taken热点代码块一般不会很大，提高容量更大的下级BTB吞吐量不但工程实现困难，收益也存疑。
疑点重重
仔细观察上图曲线，我们不难发现一些怪异的现象。在分支最密集的情况下X1的BTB性能特别低，L0 BTB的容量似乎也并不是上文所说的96项（下图所示）。
尽管其他密度曲线的跳变点都在8192附近，但是细节上的行为并不一致（如下图所示）。
显然是BTB的结构导致了这些现象，那么会影响BTB性能表现的除了物理上确定的容量和延迟还有什么呢？
1. 组织形式。组相联、全相联。
2. 索引（index）算法。如果BTB使用了组相联设计，为了提高其在面对不同指令排布时的性能表现，往往会对Set的索引index进行Hash处理。
3. Tag 算法。为了减少BTB的存储开销，其往往不会存储分支指令的全PC，因此Tag经历了Hash处理。
4. 替换算法。
5. 预取算法。
由于无法使用性能计数器，我们实验的精度无法完全解答这些问题；不过我们可以尝试在有限的精度内获取一些力所能及的信息。
组相联or全相联
多层次BTB设计中大容量的BTB往往是组相联的，因为物理上难以实现容量巨大的全相联设计；小容量的BTB可以选择全相联的设计。那么X1的BTB是如何设计的呢？为了得出结论我们需要在更宽的分支间隔范围内进行试验。对于全相联BTB，影响其有效容量的只有实际的物理项数和Tag hash算法这两大因素（当然替换和预取算法也会影响，但目前商业实现的算法都较为简单，不会显著改变有效容量）；只要Tag的Hash算法选取得当，我们预期不会因为分支间隔的变化而观测到有效容量的波动。对于组相联BTB，影响其有效容量的还有Set Hash算法这一因素。
在查询BTB时，我们首先要获得分支对应的set号才能访问Ram读出Tag和其对应的跳转目标，这就决定了Set号的生成是时序敏感的，算法不能过于复杂。而且Set号的位数是固定的，由Ram深度决定。这就意味着当我们改变分支间隔时很容易触及Set Hash算法的盲区，进而使得部分Ram永远无法被索引，导致有效容量减少。以最简单的情形为例，我们截取PC的低2-3位共2 bit作为Set号（0-1位永远为0，因为每条指令的大小为4 Byte）。当分支间隔为4 Byte时：
000000000: b // PC为000000000，二进制，Set号为00000000100: b // Set号为01000001000: b // Set号为10000001100: b // Set号为11000010000: b // Set号为00000010100: b // Set号为01
循环往复，可知Set号也在0，1，2，3之间循环；每一个Set都有机会被访问到。但是倘若分支间隔为8 Byte：
000000000: b // PC为000000000，二进制，Set号为00000000100: nop000001000: b // Set号为10000001100: nop000010000: b // Set号为00000010100: nop000101000: b // Set号为10000101100: nop000110000: b // Set号为00000110100: nop000111000: b // Set号为10000111100: nop
循环往复，可知Set号仅会在0，2之间循环；只有一半的Set有机会被访问到，有效容量仅剩一半。我们观察X1的相关结果，观察的分支间隔范围为4-2048 Byte：
分支间隔4-64 Byte分支间隔128-2048 Byte，保留4 Byte曲线作为参照可以看到L1 BTB有明显的组相联特征，在分支间隔到达一定程度后，间隔每扩大1倍容量缩小1半：
间隔每扩大1倍容量缩小1半而L0 BTB在（无视4 Byte时的情况）8-512 Byte时都稳定表现出96项的有效容量，这似乎是全相联的特征。那么为何在分支间隔达到1024 Byte及以后，L0 BTB的有效容量也出现了衰减了呢？观察跳变点，每隔1024 Byte一条分支指令会使代码段的总大小在跳变点处达到64 * 1024 = 64 KB；每隔2048 Byte一条指令会使得代码段的总大小达到32 * 2048 = 64 KB；这是一个巧合吗？各位可以自行思考（滑稽）。
ITLB
我们一直强调不使用性能计数器难以精确刻画BTB行为，这里给出一个例子。
可以看到，在分支间隔较大时各线条都有多次阶跃。以黄线为例，第一次阶跃在96附近，超出L0 BTB容量；第二次阶跃在128附近；第三次阶跃在384；第四次阶跃在512。那么第三次阶跃为何存在呢？X1的ITLB容量为48 entry，在4KB页下384个512 Byte的代码块会占据48个页，正好超出ITLB容量，ITLB miss会极大影响程序运行速度。因此使用平均执行时长会受到众多因素干扰，难以精确刻画BTB行为。
L1 BTB Index
整理我们获得的数据，所有可以享受到8192项L1 BTB的分支间隔是8-32 Byte
| 分支间隔 （Byte） | 最大L1 BTB容量 （entry） |
|---|
| 4 | 0 |
| 8 | 8192 |
| 16 | 8192 |
| 32 | 8192 |
| 64 | 4096 |
| 128 | 2048 |
| 256 | 1024 |
| 512 | 512 |
| 1024 | 256 |
| 2048 | 128 |
我们可以计算出此时代码块的PC bit（会发生变动的bit的）分布。以8 Byte间隔为例，8192组分支指令会分布在8 * 8192 Byte的空间内，涉及的PC bit为3-15bit（从bit 0开始计算）；以此类推可得：
| 分支间隔 （Byte） | 变动PC bit |
|---|
| 4 | |
| 8 | 3-15（8192组） |
| 16 | 4-16（8192组） |
| 32 | 5-17（8192组） |
| 64 | 6-18（8192组） |
| 128 | 7-19（8192组） |
但是当分支间隔达到64 Byte时，L1 BTB容量只被使用到了1/2：
我们可以借此得知Set Hash算法开始出现瑕疵，一旦PC触及bit 18的变动就不能反映到Set号上，进而导致只能索引到一半的Set号；随着PC触及的bit整体向大于bit 18的方向移动，能够索引到的Set号不断减少。因此，朴素的猜想即X1只使用了bit 17及以下的部分进行Index Hash，但折叠的方式并不平凡。各位可以自行推演，平凡的折叠方式并不能达到这样的效果。考虑到ARM在CMN-700上炫酷的折叠方式，这里就不展开推导了，会掉太多头发。
L1 BTB Tag
我们之间就注意到，尽管分支间隔为8、16、32时都能使用到8192项的L1 BTB，但是细节行为并不相同：
这三条线之间似乎存在某种关系，它们的阶跃点每次前移1/2，它们的延迟与1 cycle的差值每次提升1倍；这两个数量关系并不是偶然，而是可能预示了Tag Hash算法的盲区。在PC触及bit区间移动时，Tag的冲突概率在不断升高，致使执行延迟出现抖动。这一猜想目前无法证实，因为1.我们没有性能计数器来确认这是BTB独自造成的。2.推演Hash算法会掉很多头发（滑稽）。
L1 BTB way
为了验证路数我们更换测试方法，使用更大的分支间隔的同时只使用1-16条分支指令。这样一旦出现Hash算法的冲突，执行延迟就会陡增；同时由于使用的指令数量极少，无关因素也较少。
x方向为分支间隔，单位Byte；y方向为分支指令数量我们可以粗略得看到，无论分支间隔多大总有至少4条指令可以被BTB容纳，即L1 BTB路数大于等于4路。观察红色部分可见交界处并非陡增，因此替换算法可能不是最朴素的LRU，而是考虑了use bit或其他指标。
偷懒的BTB
为何分支间隔为4 Byte的情况下X1的L1 BTB似乎消失了，L0 BTB的容量也并不是上文所说的96项呢？我们不妨做出一个大胆的猜想：PC的bit 2没有参与Index或Tag的Hash，导致最密集的分支在L1 BTB中一定会不断发生冲突，进而无法有效训练L1 BTB。同样，我们暂时无法验证这一猜想，但是它是符合推演的。从设计角度上来说其并非完全不合理，考虑到ARM是使用compare bit的ISA，密集连续的分支指令可能是极少数情况。
L0 BTB
将之前的测试扩展到96条指令（L0 BTB容量），
x方向为分支间隔，单位Byte；y方向为分支指令数量除了4 Byte的情况下X1的L0 BTB容量仅有60项外，其似乎也展现出了组相联设计的可能性。随着分支间隔的不断增加，L0 BTB的有效容量也在不断减少，每次减少至之前的一半。但是需要注意的是，使用Set与Tag Hash的并不只有BTB，还有ICache与ITLB；从延迟判断，此处也很可能是触及了ICache的Hash算法盲区导致了取指miss；因此4路也可能仅仅代表了ICache的路数。
后记
从初步试验来看，Cortex X1的BTB不乏有趣的设计，反映了ARM对处理器前端演化的巧思；在诸如SPEC06、SPEC17的诸多测试中，Cortex X1的分支误预测率也确实不逊于Intel等老牌劲旅，让人十分期待X3乃至X4的前端表现。本次探究也留下了太多悬而未决、模棱两可的论断，希望能够尽快使用性能计数器重测，得到更加可靠的结论。（本专栏干脆改名叫“我与性能计数器的那些事儿”算了23333）
