【留言赠书】一篇讲明白LLVM指令调度算法

一条 CPU 流水线工作示意图如图 8-2 所示。引入流水线工作模式后，后 3 个工作单元 除了在前 3 个时钟周期可以偷懒外，其余的时间都不能闲着。从第 2 个时钟周期开始，当 译码单元在翻译指令 1 时，取指令单元要接着去取指令 2。从第 3 个时钟周期开始，当执行单元执行指令 1 时，译码单元也不能闲着，要接着去翻译指令 2，而取指令单元要去取指令3。从第 5 个时钟周期开始，每个电路单元都会进入满荷负载工作状态，源源不断地执行一 条条指令。

引入流水线后，虽然每一条指令执行流程不变，还是需要 4 个时钟周期，但是从整条 流水线的输出看，差不多平均每个时钟周期都能执行一条指令。原来执行一条指令需要 4个时钟周期，现在平均只需要 1 个时钟周期，CPU 性能提升了近 3 倍。流水线的本质其实是用空间换时间。将每条指令分解为多步来执行，指令的每一步都 由独立的电路来执行，让不同指令的各步并行操作，从而实现几条指令并行处理，加快程 序的运行。但利用流水线并行的前提是指令之间没有依赖关系，如果相邻的两条指令存在数据依 赖，则下一条指令就需要等上一条指令回写完结果才能开始执行，这会使流水线停顿，从 而影响程序的执行效率。指令之间的依赖通常分为结构依赖（也称为结构冲突，指不同指 令使用相同的硬件资源导致流水线停顿）、数据依赖（也称为数据冲突，指的是指令间的数 据有依赖）、控制依赖（也称为控制冲突，指的是由跳转指令确定下一条要执行的指令）。在LLVM 中常见依赖关系（属性）有 3 种。

1. data（数据依赖）：如果下一条指令的操作数为前一条指令的输出结果，那么这两条 指令就存在数据依赖。

2. chain（链依赖）：当前指令调度时不能被移到所依赖的指令之前。通常处于相同内 存的访存操作指令序列可以用这种依赖来固定访存操作的顺序。

3. glue（铰链依赖）：指令序列在调度时不能被分开。

注意：从直观上看，本章仅讨论了数据依赖，实际上结构依赖在出现指令时延时有所涉及， 而控制依赖在进行编译优化时有所涉及。

指令调度的作用就是通过调整指令的顺序，减少指令间依赖对流水线的影响，使得程 序在拥有指令流水线的中央处理器上能够高效运行。根据调度发生的阶段可以将指令调度分为动态调度和静态调度。本文仅讨论静态调度。

1. 动态调度：发生在运行时，需要相应的硬件支持。处理器会在运行时对指令序列进 行重排，并乱序地发送到处理器功能单元，以便处理器能够同时处理更多的指令。

2. 静态调度：在编译阶段对指令重排，消除指令间的依赖，提升指令并行度，从而利 用流水线的空闲周期执行没有依赖冲突的其他指令。根据指令调度的工作范围，通常可以将指令调度分为 3 类。

• 局部调度：针对单基本块进行调度。最典型的算法是 List Scheduling 算法（也称 为表调度），这一类算法采用不同的启发式方法选择合适的指令，比如考虑停滞周期（stall cycles）○一、指令时延、寄存器压力等。论文“ A comparision of List Scheduling Heuristics in LLVM Targeting POWER8”○二将影响调度算法的启发式因素细分为 24 种，我们将在后文介绍 具体的算法时详细描述算法所涉及的启发式因素。

• 全局调度：跨多个基本块进行调度。通常有 Trace Scheduling（识别频率高的执行路 径，并根据路径调度多个基本块）、Superblock Scheduling（通常是选择一些具有单入口、多 出口属性的基本块进行调度）、Hyperblock Scheduling（使用 If-Conversion 算法移除条件分支， 获得超大基本块后进行调度）等调度算法。

• 循环调度：针对循环体内的基本块进行指令调度优化，从而提升循环执行的并行性 能，这主要是针对软流水的优化。本书讨论的指令调度算法主要是局部调度和循环调度。其中局部调度适用于所有的后 端，而循环调度目前仅适用于 ARM、PPC 和 Hexagon 后端。

指令调度和寄存器分配会相互影响，所以 LLVM 实现了基于 MIR 的寄存器分配前指令 调度和寄存器分配后指令调度，同时还提供了基于 SelectionDAG（DAG IR）的调度，并未 针对 FastISel、GlobalISel 提供了指令调度算法。下面对 LLVM 中实现的调度算法（也称为调度器）进行介绍，然后介绍指令调度中使用的拓扑排序算法。

01

为什么要在多个阶段配置调度算法？根本原因是指令调度和寄存器分配（第 10 章介绍） 会相互影响。指令调度会调整寄存器的位置，影响寄存器的生命周期，从而影响寄存器分 配；同理，寄存器分配选择物理寄存器会影响指令依赖，从而影响指令调度。所以 LLVM设计了 3 个可以配置调度算法的阶段，具体如下。

阶段①：基于 SelectionDAG 进行调度，Linearize、Fast、BURR List、Source List、Hybrid List 这些调度算法都在此阶段完成指令调度优化。

阶段②：基于寄存器分配前的 MIR 进行调度，调度算法包括 Pre-RA-MISched。这个 阶段的指令调度会着重考虑指令顺序对寄存器分配压力的影响。另外，LLVM 的循环调度SMS（Swing Modulo Scheduling，摇摆模调度）也处于这个阶段。

阶段③：基于寄存器分配后的 MIR 进行调度，调度算法包括 Post-RA-TDList 和 PostRA-MISched。阶段③寄存器分配后的调度算法主要考虑影响指令并行性能的启发式因素，而阶段①、 ②寄存器分配前的调度算法除了考虑并行性能之外，还要综合考虑寄存器分配压力等多种 启发式因素。虽然这三个阶段配置的调度算法实现略有不同（原因是输入不同，如图8-3 所示），但 算法原理相似，有很多代码可以复用。针对不同阶段和具体算法，LLVM 实现的调度类UML 如图 8-4 所示。

这些不同调度算法对应的实现作用于不同的 IR 输入，如表 8-1 所示。

这些调度算法将在后续章节一一展开介绍，有兴趣的话欢迎阅读《深入理解LLVM：代码生成》一书。

02

指令调度算法会在拓扑排序的基础上进行增强，主要是在拓扑排序的第二步通过多种 启发式因素计算出队列中调度优先级最高的节点，然后将该节点作为调度结果。

LLVM 中指令调度，包括 Linearize 调 度 器、Fast 调 度 器、BURR List 调 度 器、Source List 调 度 器、Hybrid 调 度 器、Pre-RAMISched调度器、Post-RA-TDList 调度器、Post-RA-MISched 调度器，更多内容欢迎阅读《深入理解LLVM：代码生成》一书。

本文摘编于《深入理解LLVM：代码生成》（书号：978-7-111-76415-1），经出版方授权发布，转载请标明文章来源。

欢迎预约新书发布会    直播间福利5折购书

 

   互动有奖  

   

按以下方式参与互动，即有机会获赠图书！

活动方式：在评论区留言参与与本书相关的话题互动。活动将产生 5名 获奖用户，每人赠送一本《深入理解LLVM：代码生成》。

说明：留言区收到回复“恭喜中奖”者将免费获赠本图书，中奖者请在收到通知的24小时内将您的“姓名+电话+快递地址”留言至原评论下方处即可，隐私信息不会被放出，未在规定时间内回复视作自动放弃兑奖资格。

活动时间：截至11月14日开奖。

快快拉上你的小伙伴参与进来吧~~

点个在看你最好看

SPRING HAS ARRIVED