RAS 分支预测器

RAS介绍

RAS 指的是 “Return Address Stack”，即返回地址栈。它通过跟踪程序的返回地址，帮助确定程序中的分支行为。由前所述，在程序中存在很多分支：if/else、 switch/case、while/for loop、iteration、call/return

等。RAS分支预测器则专门针对 call/return类型。

function _add(a, b){
    return (a > 0 ? a : 0)  + (b > 0? b : 0);
}

function add(a, b){
    return a + b;
}

function sub(a, b){
    return a - b;
}

function main(){
    a = 1;
    b = 2;
    c = add(a, b);
    d = sub(a, b);
}

如上图所示，在main函数中调用了add和sub，add又调用了函数_add。在该过程中，每次调用（call）的跳转地址和返回的地址固定，且在call的时候，就可以同时得到返回地址。函数的调用过程是一个“栈的出入”过程，因此可以通过“栈”结构进行分支预测：每遇到call指令，把当前PC+4（压缩指令和普通指令的偏移不同）进行压栈push操作；遇到return指令，则进行进行pop操作，得到的地址即为目标跳转地址。在基于“预测块”的BPU中，RAS无法知道当前块是否是call或者ret，因此需要依赖其他预测器，利用前级预测器的结果进行RAS操作。

具体的，在香山的RAS预测器中，其s2阶段，需要判断上一级s2的输出是否预测为call或者ret（即输入信号io.s2_full_pred.hit_taken_on_call/ret有效 ），如果是call则push其后续指令地址入栈，是ret则从栈中pop出地址作为预测结果。因为在BPU的预测器中，人为假定s3阶段得到的结果比s2阶段好，所以RAS预测器在s3阶段需要进行检查，如果上一级的s3预测结果与s2不一致，则采信s3的结果，并按需求判断是否需要撤销或者补齐之前s2阶段的栈操作。例如s2阶段预测为call指令，进行了push操作，而s3为普通分支指令，不需要进行任何操作，此时就需要撤销push；如果s2预测为普通分支指令，s3预测为call，则需要进行push操作补齐。

RAS的栈操作

在普通的RAS设计中，通过栈进行预测函数返回地址。在理想情况下，本节假定RAS可进行随时备份，栈顶指针用sp表示，预测地址用paddr表示。RAS的基本操作有以下4种：

1. PUSH

由于预测可能会出错，出错时需要回到原始状态，因此在push时需要对当前栈的状态进行备份（在软件领域，通常称为“快照”，本文在后继内容中也用快照进行称呼），标记为s。当遇到call指令时，获取call指令的返回地址 addr = 当前pc + 4（如果是压缩指令则addr = pc+2），然后压栈：sp = addr；sp += 1。

2. POP

原因同上，对当前栈进行快照，标记为s。当遇到ret指令时，预测的跳转地址 paddr = sp，然后进行出栈， sp = sp - 1。对当前栈进行快照，标记为s。

3. 重定向操作

由于BPU是对程序的分支进行预测，因此就有“预测对”和“预测错”两种情况，当CPU后端发现分支预测错误，就会进行重定向（redirect）操作，告诉BPU哪个地方预测错误，正确结果是多少。重定向时RAS模块会收到正确的分支和当时预测时RAS栈信息。根据正确分支指令类型不同，首先恢复快照s有如下情形：

（1）之前被预测的指令，实际是 call指令，根据redirect中给的addr地址，执行push操作；

（2）之前被预测的指令，实际是 ret指令，执行pop操作；

4. 提交操作

提交（Commit）操作即后端告诉前端，之前预测的结果正确。理想情况下，RAS预测器此时不需要进行任何操作。

昆明湖中RAS的实现

由于处理器在执行过程中可能会进行错误的猜测，导致数据污染，RAS需要通过恢复机制来确保数据的准确性。特别是在昆明湖的实际电路设计中，不可能有无限大的栈，也无法随时备份数据。因此，昆明湖的RAS实现中，使用了基于持久化栈的返回地址预测器。具体来说，将RAS分为提交栈（commit stack）和推测栈（spec queue）两个部分，推测栈利用了香山BPU的预测结果来进行预测，然后根据后端返回的信息将数据压入提交栈中。下面详细介绍昆明湖的RAS设计：

每次预测时，RAS栈的快照如何获得？

为了实现对RAS栈进行快照的功能，昆明湖的RAS推测栈采用了基于循环数组的 “链式表示“ 。设计具体如下：

在这个设计中，数据管理是通过一个循环数组来实现的。循环数组有一个起始地址（BOS）和一个尾指针（TOSW），两者之间的数据是有效数据，其他部分为空闲数据。使用链式结构表示“Sepc栈”，每个栈元素记录其上一个数据的编号，进行栈操作时可以通过该编号获取上一个元素。RAS栈的栈底指针与BOS共用。

如图所示的初始状态S，RAS栈的元素为0、1、4、5。元素5记录了其上一个元素的位置4，元素4记录了其上一个元素的位置1。在状态S下进行push操作时，RAS栈顶指针TOSR等于TOSW，在新的TOSR位置7存入新元素，并记录其上一个元素的位置5，然后TOSW后移（TOSW = TOSW + 1）。进行pop操作时，RAS栈顶指针TOSR根据栈顶元素保存的索引移动到上一个元素的位置4，但不会修改内存分配指针TOSW，因此Spec栈的元素不一定是连续的。

在栈不溢出的情况下，RAS栈每次通过TOSW在数组上分配新数据，因此在正常的Push/Pop操作中，所有过程状态和中间数据都被保存。当需要恢复到状态S时，只需复位相应的栈指针。因此，在每次RAS预测时，需要将操作前的栈指针（BOS、TOSR、TOSW）保存于预测结果中，以便用于commit栈操作和在重定向时恢复状态。该结构的优点是可以保存完整的过程数据，但频繁的push操作会导致较大的空间资源消耗。

链式RAS浪费存储空间？

当预测结果被确认（commit）后，表示预测是正确的，不会再进行“栈”回滚。也就是说，RAS预测器在收到预测块“P”的commit消息后，不会再收到P块的重定向消息，因此在对P块进行push操作时的快照将不会被用到。

为了优化，RAS栈中的元素被分类处理：未commit的元素存储在链式结构的推测栈中，已commit的元素存储在基于循环数组的提交栈中。这样，原始的RAS栈被拆分成两部分：未commit的部分用链式结构保存，以便需要时可以恢复快照；已commit的部分用普通栈结构保存，因为它们不需要快速恢复。优化后的RAS结构如下所示：

如上图所示，根据普通预测的call/ret和commit提交的call/ret，把原始的RAS栈可以拆分成两个独立的栈，分别称为“预测栈”（ spec_stack，链式结构）和“提交栈”（commit_stack，普通结构），由于RASStack对外表现为当拍内就能完成任务，因此在Stack内需要进行数据旁路，对数据进行缓存，由于栈结构发生了变化，具体的Pop/Push操作如下：

1、遇到普通call和ret：

（1）预测块为call正确，在spec_stack上进行push操作，具体为上述链式栈Push过程，并将产生的快照信息送到FTQ存储；

（2）预测块为ret正确，利用spec_stack的栈顶作为预测值，然后进行pop操作，并将产生的快照信息送到FTQ存储，如果spec_stack为空，则使用commit_stack的栈顶元素作为预测结果（不进行pop操作）。

2、Commit操作：

（1）FTQ执行结果为call正确，通过FTQ传回来的快照信息对commit_stack进行push操作，同时更新spec栈的BOS指针，将此次commit的数据及其之前的数据设置为无效数据。

（2）FTQ执行结果为ret正确，通过FTQ传回来的快照信息对commit_stack上进行普通pop操作，注意到在commit pop之前会先对spec栈进行pop操作，所以commit栈弹出来的地址不需要使用。

3、Redirect操作：

（1）从redirect消息中获取之前预测时的栈指针（BOS、TOSR、TOSW，ssp），覆盖当前值指针值完成预测栈状态回滚，若此时为Call指令或者Ret指令，则再对Spec栈进行对应的操作。

（2）该操作不影响提交栈。

输入端，S3的预测结果和S2不一致时该如何处理？

由于昆明湖 BPU 的假定S3的结果比S2好，因此发生不一致时，需要再次对RAS栈进行修复。具体不一致情况和对应的修复操作如下表所示：

因为SC预测器的特性，S2和S3的操作不存在pop/push或者push/pop情况

其他优化

1. 每个RAS的spec栈和commit栈的元素都有一个counter计数器，用于节约重复值（递归调用）。例如：当第一次push地址为0xff00，第二次push的也为0xff00时，则只需要把栈顶元素的 counter 进行+1，不需真的进行push操作。

接口说明

在RAS预测器中，核心组件为 RASStack ，其接口说明如下:

RASStack模块与BasePredictor的接口关系如下：

时序说明

在RAS中，只涉及到2拍，S2和S3。

S2中的主要工作：

1、根据上一个预测器的S2预测结果，完成通过Push/PoP过程完成预测，并得到结果sepc_pop_addr。

2、根据commit信号执行更新操作

S3中的主要工作：

1、根据上一个预测器S3中的预测结果，以及S2进行的操作，判断是否需要进行Pop/Push的撤销操作。预测器假定S3的预测结果比S2好，如果发生S2和S3预测不一致时，RAS预测器采信S3结果进行栈操作。

2、S3和S2的预测过程一致，只是数据不同。

3、执行重定向（重定向信息由前一拍获得）操作