基于RISC-V GCC编译器的指令延迟调度

余晓江 罗欣

（西华师范大学 四川省南充市 637000）

1 引言

2014年加州大学伯克利分校（University of Cal-I fornia at Berkeley, 以下简称 UCB）的研究人员Krste Asa-novic、Andrew Waterman、Yunsup Lee 设 计 并 发 布 了RISC-V 指 令 集 架 构[1]。RISC-V 基于精简指令集计算（RISC）原理构建的开放RISC-V 指令集架构（RISC-V instruction set architecture 简称RISC-V ISA）[2]。RISC-V 指令集架构采用的是精简指令集，同时有着非常良好的可扩展性，并且RISC-V 生态系统迅速的发展，促进了这种新型的RISC-V ISA 在各大处理器设计中得到应用。RISC-V 开源自由协议受到个人、科研团队以及商业公司的青睐，各大公司纷纷加入RISC-V 联盟，如蜂鸟、中科院计算所、英伟达、华为、谷歌、阿里巴巴等等[3][4][5]。

大多数早期超标量处理器[6]都是顺序执行，RISC-V 处理器设计初期均采用单发射顺序执行的流水线工艺[7]。

流水线技术之所以能提高性能，其本质是利用了时间上的并行性，让原本应该先后执行的指令在时间上一定程度的并行起来，然而这样也会带来一些冲突和矛盾，进而可能引发错误，这种情况就被称为流水线冒险。数据冒险是流水线冒险中最常见的一种，数据冒险是指令所需要的数据矛盾，如果一条指令需要某个数据而该数据正在被之前的指令操作，那这条指令就无法执行，就导致了数据冒险。针对流水线冒险其中一种解决方案是使用流水线停顿来延迟下一条指令。从而避免流水线冒险带来的程序执行错误。

在传统处理器设计中，流水线借助于一个执行单元队列，让暂未满足各类资源的指令在此等待一定周期，或者采用流水线停顿技术(stall)让整个流水线上相关的资源均陷于一定周期的等待状态，直至问题解除[8][9]。等待的周期主要取决于两个因素：前驱指令的执行开销、以及当前指令所需硬件资源。而这些恰恰是编译器静态指令调度策略中的核心影响因素。因此，如果借助于静态调度策略，为当前指令去权衡计算它需要等待的时间，适当调整指令的位置，在指令排布过程中拉长它和前驱的距离，我们就能保证它在正确的时间完成译码以及到达执行功能部件。

综上所述，虽然成熟的处理器大部分使用动态调度来避免流水线冒险，但是基于RISC-V 指令集的处理器目前尚未成熟，都处在研究设计阶段，所以使用RISC-V ISA 的处理器研发时，为缩短研发周期和研发成本。静态调度是解决流水线冒险最有效的方法。本文提出一种面向RISC-V 处理器的指令调度技术——指令延迟调度技术，用于向RISC-V 处理器研究提供一种实用、有效的软件解决方案。在RISC-V 处理器研发处于萌芽期的大背景下，编译器延迟调度技术是一种实用、有效的途径，使编译器的研发不受硬件时序控制设计与验证的约束，直接在具有基本执行功能的FPGA 或者软件模拟器上进行研发，从而使软件研发与处理器研发同步前行。

2 指令延迟调度技术

本文提出一种基于RISC-V 处理器的编译器调度技术——指令延迟调度技术，它通过一个保守的资源开销评估模型对当前指令的正确发射时间进行评估。通过指令的静态调度对流水线上的指令到达执行部件的时刻进行干涉，从而有效避免由于指令提前到达执行部件所引发的流水线冒险。指令延迟调度技术是一种实用、有效的软件解决方案，使核心软件可以与处理器设计同期同步开展。优化后的表调度分析算法能够准确地记录每一个基本块中指令流中需要插入延迟指令的位置和数量。通过本地延迟指令生成算法，生成占用拍数但又不做任何操作的NOP 指令[10]。指令延迟调度技术根据表调度算法计算出的数据对表调度之后的指令流进行再次调度，使每一拍都有指令发射，从而避免流水线冒险带来的执行错误。经过指令延迟调度的程序在处理器上不需要进行动态调度即可正确高效的执行。为了不影响编译器的功能模块和方便进行对比测试。将指令延迟调度封装在编译选项-fsched-delay 中，在编译时，通过使用编译选项-fsched-delay 来控制编译器使用指令延迟调度技术。

（1）表调度分析算法。要对表调度后的RTL 进行指令延迟调度，需要优化表调度的分析算法。通过指令调度数据流DUMP 算法的输出数据流，直观的显示了指令信息。RTL 中间表示阶段所有指令是由一个结构体存储即INSN。要对指令进行延迟调度，首先需要了解表调度的调度原理，如图1 所示。指令INSN 已提交到计划中，从“Ready”列表移动到“Scheduled”列表。当发生这种情况时，“Pending”列表中的INSN 满足其依赖关系并移动到“Ready”列表或“Queued”集合，具体取决于是否已经有足够的时间使其准备就绪；随着时间的推移，准备就绪的INSN 从“Queued”移动到“Ready”列表；“Pending”列表（P）是未安排的INSN_FORW_DEPS 中的INSN，即准备好，排队和挂起的INSN。“Queued”集合（Q）由变量insn_queue 实现。“Ready”列表（R）由变量ready 和n_ready 实现。“Scheduled”列表（S）是由此传递构建的新INSN 链。当选择最好的调度INSN 时，转换（R-＞ S）在schedule_block 的调度循环中实现。当INSN 从就绪列表移动到调度列表时，转换（P-＞ R 和P-＞ Q）在schedule_insn 中实现。随着时间的推移或引入停顿，转换（Q-＞ R）在queue_to_insn 中实现。为了减小对编译器的影响，对表调度分析算法进行优化，计算出延迟调度的相关信息并记录保存，传递到指令延迟调度中。

图1：编译器指令调度数据流对比

图2：编译器编译出的汇编码对比

图3：指令延迟调度技术优化后的编译器与官方编译器编译SPEC2017 Benchmarks 的耗时对比图

（2）延迟指令生成算法。由于指令流里的指令是由源码翻译过来的，从一开始转换到RTL 时，就生成了双向链表，经过表调度时，指令队列进行指令调度后依然是一个双向链表。那么在进行延迟调度时，要在双向链表中插入延迟指令NOP。就要对双向链表进行维护。每一条指令都有一个前驱和后继，当前指令、前驱指令和后继指令都是相互依赖的。当insn 需要延迟时，首先就要断开双向链表prev 和insn，将nop 指令放在prev 和insn 之间。把insn的前驱设置为nop，prev 的后继修改为nop，并把nop 的前驱设置为prev，后继为insn。根据机器模型获取nop 指令的RTL 结构,设置nop 指令所属的基本块为insn 的基本块。

（3）指令延迟调度算法。指令延迟调度算法根据表调度分析算法记录并传递来的数据使用延迟指令生成算法在需要延迟的指令前插入足够的空操作指令NOP 来占用无指令的拍数。为尽量避免对编译器其他功能的影响，我们选择在编译器表调度完成之后，RTL 翻译成汇编码之前，进行指令延迟调度。首先判断是否在编译时使用了-fsched-delay 编译选项，以下所有操作都是在使用-fscheddelay编译选项的情况下实现。接着判断当前是否属于最后一次调度，即前面说的重载后调度（after reload）。当两个条件同时满足时，对当前基本快中已经调度好的指令流进行遍历，寻找需要延迟的指令。当遍历到INSN 的编号INSN_UID 为表调度分析算法传来数据中的INSN_UID 时，即这条INSN 需要在发射前插入NOP 延迟，根据数据中记录的延迟拍数循环插入NOP 指令。调用延迟指令生成算法进行指令生成。最后对指令在调度过程中的LUID 进行维护，以保证调度过程中每一条指令在调度过程中都有唯一的识别ID。

3 实验结果与分析

（1）指令延迟调度技术是通过静态调度中使用停顿避免流水线冒险带来的执行错误，经过应用该技术的RISC-V GCC 编译器编译程序时，使用-fsched-verbose=n 编译选项可输出指令调度过程，能够直观的看到指令延迟调度的结果，如图1 所示。

另一方面，指令延迟调度技术在静态调度中完成了空拍指令的填充，生成的汇编码中会明确显示NOP 在相应的位置，如图2 所示。

经过如图1 和图2 的试验验证，指令延迟调度技术能够在指定拍数处填充NOP 指令，并且正确的生成对应的汇编码，来延迟下一条指令。编译器的性能是在对编译器改进后的综合评估，主要通过编译时间来进行比较，使SPEC2017 作为测试用例，测试了使用指令延迟调度技术的RISC-V GCC 编译器编译时间。实验编译器运行环境为：32 核Intel Xeon E7-4809 主频2.00GHz 的CPU，64 位ubuntu14.04 系统，一级指令/数据Cache 各32K，二级Cache256K。实验结果如图3 所示。

图3 中分别使用指令延迟调度技术优化后的RISC-V GCC 编译器和官方RISC-V GCC 编译器在相同条件下编译SPEC2017 中使用C 语言编写的Benchmarks，由图可见，优化后的编译器和原编译器编译相同Benchmarks 耗时相差不超过1s，实验证明，指令延迟调度技术对RISC-V GCC 的性能影响很小，达到了设计初期最小化编译器影响的要求。为了验证优化后的编译器编译出的程序可以正确的在RISC-V 处理器上运行，以stream 作为测试程序，分别在超导模拟器和火苗原型系统上测试通过，能够正确的执行完成。超导v1 版本模拟器：位模式32 位，译指队列大小151，一级Cache128byte，二级Cache32K，寄存器个数16。火苗原型系统：4 核Labeled RISC-V 系统，100 MHz rocket 核心， 16KB L1 Icache, 16KB L1 Dcache， 2MB L2 cache，16GB DDR4 SO-DIMMs，Linux 4.6.2 内核。

4 结束语

指令调度在编译器中是非常关键的环节，指令延迟调度技术是RISC-V GCC 编译器在RTL 一级的指令调度优化，在RISC-V 处理器研发过程中作为编译器辅助有着重要作用，尤其是在超导计算机研究中作为编译器优化研究意义重大。本文通过对RISC-V GCC 编译器的改进和优化，为进一步研究和优化RSIC-V GCC 奠定了编译器基础，更为快速研究新型的RISC-V 指令集架构处理器起着重要的推动作用。