超标量处理器分支预测基本逻辑

分支预测基本逻辑

超标量处理器遇到分支指令的时候会预测下分支指令的目的地址，然后从预测的地址fetch
指令执行，这些投机执行的指令处于分支预测的路径上，所以处理器只能把它们的结果缓存
在内部，如果后面发现预测的分支是对的，就把投机执行的指令的结果提交，如果后面发现
是分支预测错了就需要把投机执行的执行从流水线里抹去。

所以可以看到硬件上的BP部件一定是顶在流水线最前端的，比如对于一个一拍fetch 4条指令
的超标量处理器，第二拍它又可以去fetch 4条指令，但是从哪个地址上去fetch呢，如果第
一拍fetch的四条指令里就有分支指令，那么分支预测的结果最好第二拍就可以拿到，否则
第二拍的fetch就会空转(stall)，处理器的性能就会下降。

我们先忽略直接跳转的分支指令，其它分支指令可以分为条件跳转和间接跳转，条件跳转通
过动态计算判断条件决定是否发生跳转，一般跳转目的地址的偏移会直接编码到指令里，比
如RISCV中的beq等指令，间接跳转的跳转目的地址存放在一个寄存器里，每次跳转寄存器里
保存的目的地址都可能是不一样的，CPU做分支预测主要面对的就是如上这两种情况。

首先，分支可以做预测，一定是要有规律的，一个没有规律的分支是没有办法做预测的。分
支预测器通过一定的电路就可以把相应的规律捕捉住，这样下次fetch到同样PC上的跳转指令
就可以直接预测跳转的地址。

对于条件跳转，我们可以这样建模，对于一个PC上的条件跳转指令，发生一次跳转记1，没有
发生跳转(就是继续顺序执行指令)记0，那么跳转的历史就是0和1组成的一个序列，对于一个
这样的序列，比如，0001000100010001… 分支预测电路要做的工作是找出其中的规律，比如
这里的规律就是0001在做反复的重复。

严格上来讲，跳转情况是过去所有指令执行的结果，当只看分支指令的变化得到的预测正确
率低的时候，就要考虑把更多的信息一起加进来进行预测，所以CPU里还会把一段时间的跳转
指令的历史保存起来，用这个全局历史信息做分支预测，和这个相比，如上只考虑跳转指令
本身历史情况的预测称为依据局部历史信息的分支预测。

对于间接跳转，一个PC上的跳转指令的目的地址是有限几个，如果用数字标记每个目的地址，
间接跳转形成的序列大概是这样的：134213421342，那么其中的规律是就是1342反复重复。
因为一个间接跳转可能的目的地址是有限的，一般可以把它们保存在一个表(BTB Branch Target Buffer)，
需要做预测的时候，查表即可。

一般，CPU体系架构的手册都会建议尽量少用间接跳转指令，但是在函数跳转时，还是会用到
间接跳转指令，针对函数跳转和返回，CPU里一般采用类似栈的方式保存函数返回指令的跳转
目的地址，这种方式一般叫做RAS(return address stack)，CPU在函数跳转时，把返回地址
保存到内部的这个栈里，执行函数返回指令时从栈中弹出返回地址。

各种分支预测方法

局部历史信息条件跳转预测方法。我们直接直接看书中介绍的方法，必要的时候再看其中的
细节和辅助设计。

首先一个分支指令先对应一个BHR(Branch History Register)，这个寄存器的最大bit数决定
了可以完美预测的跳转序列的”循环节”大小，BHR里的每一个值都对应一个两位饱和计数器，
预测是根据当前BHR的值对应的两位饱和计数器的值来完成的。

如下是一个大概的示意图：

BHR:           PHT(Pattern History Table)
+------+       +------+                             
| 0001 | ----> | 0000 | X
+------+       |      | +-------------------------------+
               |      | |     +-+   +-+   +-+   +-+     |
               | 0001 | |  +--|0|-->|0|-->|1|-->|1|--+  | -> 0
               |      | |  |  | |   | |   | |   | |  |  |
               |      | |  +->|0|-->|1|-->|0|-->|1|<-+  |
               |      | |     +-+   +-+   +-+   +-+     |
               |      | +-------------------------------+
               | 0010 | ...                               -> 0
               |      |                 
               | ...  | X                 
               |      |                 
               | 0100 | ...                               -> 0
               |      |                 
               | ...  | X
               |      |                 
               | 1000 | ...                               -> 1
               |      |                 
               | ...  | X
               +------+

还是拿如上00010001…这样的条件跳转序列分析，这个序列里，只有四个状态，每个状态
的下一次跳转情况都是确定的，也就是当分支预测器检测到这个分支指令的历史是四个状态
其中之一时，本次的跳转情况就可以确定了。这么看起来如果可以直接确定，那么都不用两位
饱和计数器了，估计这里的两位饱和计数器是防止有零星的意外变化？

上面可以看出来，BHR的位数和跳转序列规律位数相同时，已经可以做完美预测。当BHR位数
比跳转序列规律位数大时，都可以做完美预测，比如，如果这里BHR是5 bit，那么如上序列
的pattern就是：00010/00100/01000/10001，不过就是PHT中没有用到的entry也增多了。

深入看下如上的两位饱和计数器，这个计数器有4个状态，其中两个状态的预测结果是分支跳
转，两个状态的预测结果是分支不跳转，分支跳转或不跳转的两个状态分强和弱状态。

   strong   weak  weak  strong
      no taken      taken
+-------------------------------+
|     +-+   +-+   +-+   +-+     |
|  +--|0|-->|0|-->|1|-->|1|--+  |
|  |  | |   | |   | |   | |  |  |
|  +->|0|-->|1|-->|0|-->|1|<-+  |
|     +-+   +-+   +-+   +-+     |
+-------------------------------+

在如上的状态定义下，各个状态的跳转关系是，当处于strong taken态，如果实际又是taken，
那么保持strong taken不变，如果实际是no taken，也就是预测失败了，状态移动到weak taken，
也就是说一直预测是taken，第一次出现no taken，我们还是认为下次是taken，当处于weak
taken时，如果实际是taken，状体转移到strong taken, 如果实际是no taken，也就是又预测
错了，状态转移到weak no taken，预测器在两次都预测失败的情况下改变了预测方向。

todo: 实际硬件实现上的考虑?

全局历史信息条件跳转预测方法。如上BHR是一个跳转指令taken/not taken的历史，如果BHR
里存放的是程序动态执行路径上之前跳转指令的历史，那么预测就是根据之前的”全局”跳转
信息的，当然受到物理实现的限制，BHR有一定的取值位数，并不是理想的全局信息。

间接跳转预测方法。间接跳转和直接跳转都可以用BTB(Branch Target Buffer)保存跳转的
目的地址，直接跳转在decode阶段就可以得到物理地址，但是超标量处理器一拍可能fetch多
条指令，需要在fetch阶段就得到跳转的目的地址，所以直接跳转也要使用到BTB。

具体看下函数跳转和返回时的跳转预测，函数跳转可能用直接跳转也可能用间接跳转实现，
两者都可以用BTB做跳转预测，一个函数跳转的目的地址是一定的。但是，函数返回一般用
return指令+link寄存器的方式实现，这是一个典型的同一位置根据寄存器内值不同，跳转的
目的地址不同的间接跳转的场景，如果函数返回地址的预测也用BTB，必然存在一个搜索行为，
性能就会比较差。

RAS的预测方法在函数跳转点处把函数返回地址先保存起来，遇到函数return指令直接pop
出RAS中预先保存的函数返回地址。这个方法的关键是要识别函数进入点的跳转指令，因为
函数进入可以用直接跳转或者间接跳转实现，而且并不是所有的直接跳转和间接跳转都是函数
调用点，一旦匹配错误，所有的预测结果都可能是不准的了。而且，这个方法还要识别return
指令，比如在riscv里，return是用jalr指令实现，而jalr可以支持各种间接跳转的场景。

todo: 怎么做这个识别？

分支预测失败恢复

分支预测失败时需要flush掉错误路径上投机执行的指令，关于CPU中flush的一个整体理解
可以参考这里。然后把处理器里各个部件的状态恢复到分支指令对应的点上。