最近在整理LLVM后端的学习笔记写到第三十六篇终于到了指令调度Instruction scheduling。说实话前面看SelectionDAG、看寄存器分配的时候我一度以为指令调度只是把指令换个顺序让CPU执行得更快而已。真正读下来才发现这块内容横跨了目标描述、机器模型、数据依赖分析和后端Pass管线是整个代码生成阶段里最需要“硬件常识”的部分。这篇笔记我会直接把指令调度放在LLVM整个后端的上下文里去拆讲清楚它为什么存在、在哪几个环节生效、内部怎么算、以及实际调试时怎么观察和干预。系列笔记越写到后面我越有一个感觉LLVM的后端不像前端那样有大量“人尽皆知”的规则它很多设计是围绕目标CPU的物理特性展开的。指令调度就是最典型的例子。1. 指令调度要解决的核心矛盾编译器排序CPU也在排序我们在学校学体系结构的时候最先接触的是五级流水线取指、译码、执行、访存、写回。如果每条指令都老老实实按顺序走完一个流水级那么相邻两条指令之间一旦存在数据依赖后者就必须等前者的结果写回这个等待周期就是流水线空泡。指令调度要做的事情直观说就是从语义上合法的指令序列中找一种重排方案让流水线尽量不停顿把空泡藏到别的指令后面去。1.1 编译器看到的“顺序”和CPU实际执行的“顺序”不是一回事这里有个初学者很容易混淆的点我们平常说“指令顺序”至少有三层含义。第一层是源代码里的顺序这是程序员视角第二层是编译器生成的机器指令顺序这是汇编代码里的顺序第三层是CPU实际发射和完成指令的顺序这是微架构视角。编译器指令调度主要改的是第二层影响的是第三层。乱序执行CPU内部有重排序缓冲区、保留站、寄存器重命名这些硬件机制它会自己尝试找出可并行执行的指令。但这不代表编译器可以把第二层顺序随便排因为CPU的重排窗口是有限的一般是几十条到上百条指令一旦关键指令之间的间隔超过硬件重排窗口硬件也无力回天。所以现代编译器在乱序CPU上同样要做调度只是目标变了不是简单地把执行时间往前挪而是让数据依赖链尽量短让每条指令的延迟可以被其他独立的计算掩盖掉。1.2 为什么不能直接用“生成顺序”作为最终顺序很多人在自己写简单后端或者看LLVM源码的时候都会有疑问指令选择做完以后生成的MachineInstr顺序已经是从SelectionDAG按拓扑序输出的为什么不直接用问题在于语义合法的拓扑序有很多种。同一个DAG里只要不破坏依赖边A和B谁先发都可以。但不同的顺序对CPU执行效率影响很大。比如A是一条load延迟12个周期才需要用到B是一条乘法延迟4个周期。如果先发A再发B等A结果回来的12个周期里B已经算完了时间被藏起来。如果反过来先把B发了再发AB的结果可能要空等总完成时间就会拉长。所以指令调度在本质上不是“排个队”而是在数据依赖约束和硬件资源约束围出来的可行域里尽量压缩关键路径的长度。这个概念后面理解调度器代码时会反复用到。用一句话给这块做个小结指令调度的输入是带依赖关系的指令图输出是一个指令序列目标是用最少的时钟周期跑完整个基本块同时不改变程序语义。2. LLVM后端里的指令调度不是只有一次DAG调度、pre-RA调度、post-RA调度读LLVM源码时最容易被绕晕的就是调度器怎么好像出现了好几次其实LLVM后端现在大致有三个阶段会做指令重排它们的入口不同、目标也不同。2.1 SelectionDAG阶段的调度把“抽象的DAG”变成“具体的指令顺序”第一个阶段出现在指令选择完成之后。SelectionDAG本身是一个数据依赖图节点是SDNode边是数据依赖和链式依赖。在Legalize、Combine、Select这些步骤之后SelectionDAG要变成MachineInstr序列这时候就会用到SelectionDAG调度器。这个阶段的核心类叫做ScheduleDAGSDNodes它负责把这个SelectionDAG按某种启发式顺序排出来。虽然这个阶段生成的MachineInstr顺序不是最终顺序但它决定了MachineBasicBlock里指令的初始摆放。说得再直白一点如果第一阶段排出来的顺序太差后面的MachineScheduler可能要花很大力气才能把关键路径重新拉短。2.2 Pre-RA机器调度现代LLVM后端的调度主力第二个阶段是在机器指令已经生成、但寄存器分配还没做的时候也就是pre-RA调度。现代LLVM后端大多数默认开启MachineScheduler这个调度器作用在MachineInstr这一层底层数据结构是ScheduleDAGMachineInstr。它会重新读取基本块中的MachineInstr之间的依赖关系重新排一遍序。你可能想问指令选择阶段已经排过一次了为什么还要再排一次原因是这时候信息更完整。SelectionDAG阶段的DAG还是偏图论的表达MachineInstr阶段已经明确了每条指令的目标寄存器、源寄存器、内存操作数。依赖关系更准确尤其是可以识别反依赖和输出依赖这是之前阶段不容易精确判断的。另外在这两个阶段之间还经过了一些机器指令层级的优化和规整比如栈帧调整、伪指令展开。这些变化都会改变指令间的真实依赖关系原有的顺序可能已经不再合适。所以在我的理解里pre-RA调度才是LLVM后端真正意义上的“指令调度器”它承担了让依赖链最短、隐藏延迟的主要责任。2.3 Post-RA调度寄存器分配完成后还得再修一次第三个阶段是post-RA调度发生在寄存器分配之后。寄存器分配会产生一个新的问题原来寄存器分配器里的虚拟寄存器会被替换成物理寄存器甚至因为寄存器不够用而产生spill和reload指令这些新指令会插入在原来的指令流中间很可能破坏pre-RA调度辛苦排出来的顺序。这些额外依赖主要来自物理寄存器上的反依赖和输出依赖。比如两条指令都用x0寄存器即使它们没有真正的数据传递关系由于不能同时写x0也会形成一种伪依赖。Post-RA调度就是把寄存器分配引入的新约束考虑进去再对指令顺序做一次修正。它还能做一件事就是把长延迟指令尽量往前挪给后面的load结果留出等待时间或者在指令之间塞入可以并行的其他指令降低stall周期。LLVM里post-RA调度主要通过PostMachineScheduler和ScheduleDAGMI这套机制来实现但并不是每个后端都会启用。AArch64和x86这些主流后端一般会开一些简单的或资源较少的后端可能只依赖pre-RA。这样梳理下来三个调度阶段的关系就清晰了调度阶段触发时机主要依赖信息来源核心作用SelectionDAG调度SelectionDAG转MachineInstr时SDNode依赖、链式依赖生成初始指令顺序Pre-RA调度指令选择后、寄存器分配前MachineInstr物理/虚拟寄存器依赖压缩关键路径隐藏延迟Post-RA调度寄存器分配后物理寄存器依赖、spill/reload插桩修正伪依赖降低stall这三个阶段不是每个后端都必须同时开最优配置完全取决于目标CPU的微架构设计。3. 调度器内部到底在算什么依赖DAG、延迟表和资源模型不管哪个阶段的调度器底层框架其实都差不多先构建一个调度单元DAG再按启发式算法逐个选择“可以发射”的指令。LLVM把这个调度单元叫做SUnit。3.1 SUnit与SDepDAG的节点和边在LLVM调度器里每个SUnit对应一个调度单元。对MachineScheduler来说一个SUnit通常就是一条MachineInstr。SUnit之间通过SDep连接SDep的类型决定了这条边的含义。LLVM里常见的有这么几种依赖Data依赖真正的数据传递后一条指令要读前一条指令写的结果这是最刚性的依赖。Anti依赖后一条指令写的寄存器前一条指令正在读反过来形成一种“写不能早于读”的约束。Output依赖两条指令写同一个目标顺序不能随便换。Order依赖一般由内存操作、调用边界、内联汇编等带来的顺序约束比如两个可能访问同一片内存的操作不能乱换位置。刚开始读代码时我只关注Data依赖结果导致调度出的顺序总是出现寄存器被提前覆盖的问题。后来才发现Anti和Output依赖虽然不影响最终计算结果却会严重限制指令的可并行空间尤其在寄存器数量有限的CPU上。所以看到调度器在构造DAG时疯狂给寄存器依赖加边千万别觉得多余那都是在模拟真实的硬件限制。3.2 每条指令的“延迟”是从哪来的Itinerary与SchedMachineModel指令调度器光知道依赖关系还不够还得知道每条指令执行要花几个周期这样才能估算关键路径。在LLVM里这个信息来自目标后端定义的机器模型。老一点的LLVM后端习惯用Itinerary也就是定义每类指令或者说每个指令集族经过哪些功能单元每个单元花多少个周期。这种表达方式比较直观但粒度不够细而且不好表达现代CPU的乱序执行、多发射行为。所以LLVM后来又推出基于SchedMachineModel的机器模型。它在TableGen里定义通过ProcessorModel把CPU型号和调度模型绑定起来。每个SchedMachineModel里可以定义指令的读写延迟、微指令数量、端口占用情况等。用AArch64后端举例你会在AArch64SchedA55.td这类文件里看到类似这样的定义def CortexA55Model : SchedMachineModel { let MicroOpBufferSize 0; let LoopMicroOpBufferSize 0; let CompleteModel 1; let PostRAScheduler 1; }MicroOpBufferSize表示乱序窗口的大小设置成0说明是顺序执行的CPU。CompleteModel表示这个模型足够完整所有指令都能查到调度信息。真正给具体指令定义延迟的地方是类似def : InstRW[WriteLD4], (instregex LDP.*);这种写法把指令匹配到相应的调度类调度类又对应到WriteRes和ReadAdvance。调度器通过这些信息计算出前一条指令最短要隔几个周期才能把结果交给下一条指令也就是SchedModel里的latency。很多初学者会觉得调试LLVM调度器时排出来的顺序“不符合常识”大半原因不是调度器算法错而是机器模型里定义的latency和资源数有问题。调度的结果好不好很大程度上取决于你喂给它的CPU参数准不准。3.3 列表调度一个朴素但有效的贪心框架理清DAG和延迟之后调度器怎么从DAG里产生指令序列呢LLVM的默认调度器大多基于经典的列表调度算法也就是List Scheduling。思路是这样的找出所有前驱依赖已经满足的SUnit放到就绪队列里。根据某种优先级策略从就绪队列里选一条指令发射。发射后更新依赖关系新增就绪指令。重复直到所有SUnit都被发射完。优先级策略有很多种常见的有“最高延迟优先”“最长路径优先”“最少资源剩余优先”。LLVM的MachineScheduler里有一套基于启发式评分的机制叫Bottleneck分析会综合考虑深度、高度、资源压力等因素给每条就绪指令打分再选分最高的。这个框架看起来简单但实际工程里要处理的情况非常多。比如就绪队列里有两条指令都能发射选哪个会导致资源冲突最少要不要为了隐藏一条长延迟load提前把一条优先级不高但可并行的指令插进去这些都是调度器做的启发式判断。所以你能看到同样的底层算法在不同后端、不同CPU型号下表现完全不同。LLVM没有试图搞一个“万能调度器”包治百病而是把框架搭好把决策点留给了机器模型和可插拔的策略。4. 现在LLVM里我能见到的调度器类型怎么选我第一次接触LLVM调度器的时候总想找到一个开关直接切到“最优”模式。但现实是LLVM里调度器有很多入口不同后端用到的还经常不一样。4.1 旧式SelectionDAG调度器依然存在LLVM官方文档里管这个叫SelectionDAG Scheduling。它位于SelectionDAG阶段选择DAG后生成MachineInstr的顺序。我在这个话题上花过不少时间后来才意识到对于大多数后端你不用去改这一层的调度策略因为它的主要任务是生成一个比较合理的初始顺序真正的优化重心已经不在这一层了。只有在一些尚未迁移到MachineScheduler的旧后端里这一层调度器还承担比较重的优化职责。4.2 MachineScheduler是当前的主力MachineScheduler是LLVM代码生成器中的一个通用框架它运行的时机在机器指令层可以配置在寄存器分配前或分配后。它的优势在于模块化程度高。LLVM把调度策略拆成了多个可以配置的阶段比如前导阶段处理一些特殊指令的聚类比如把相关的load排在一起。主调度阶段就是上面说的列表调度循环。收尾阶段做一些边界清理和最终检查。每个阶段都可以被目标后端覆盖这给后端开发者留了很大的定制空间。拿AArch64来说machine scheduling会在misched阶段生效你可以通过llc的-misched选项切换不同策略。比如想看看默认调度和禁用调度的区别可以这么试llc -mtripleaarch64 -mcpucortex-a55 -mischeddefault input.ll -o default.s llc -mtripleaarch64 -mcpucortex-a55 -misched0 input.ll -o nosched.s留意一下输出汇编的指令顺序尤其是load、store和乘法、除法指令的分布位置。4.3 目标后端怎么介入自定义调度当你觉得默认调度器不够好用可以走后端Subtarget的入口来自定义。LLVM里最常用的是这两个接口一是重写TargetSubtargetInfo中的enableMachineScheduler决定pre-RA阶段是否启用MachineScheduler。二是重写MachineSchedStrategy。这个类才是真正决定“从就绪队列里挑哪条指令”的决策者。LLVM提供了一个默认实现叫GenericScheduler大多数后端直接用这个。如果你的CPU有非常特殊的执行约束比如某些指令必须成对发射或者有资源约束导致某些指令不能靠太近你完全可以从MachineSchedStrategy派生出自己的策略然后用OverrideSchedStrategy之类的方式注入到调度流程里。但我的建议是**不要一开始就想着写自定义调度器。尽量先把机器模型调准确。**很多调度问题其实是SchedMachineModel参数不准导致的模型调好了GenericScheduler就能给出接近手写调度的效果。5. 实际调试指令调度时的几个手段指令调度是后端里出了名的“黑盒”光靠读汇编很难判断调度器到底在做些什么。好在LLVM提供了一些调试入口可以让我们把黑盒打开看一眼。5.1 用debug日志追踪调度决策最直接的方式是用llc跑一个小的IR文件打开misched的调试输出llc -mtripleaarch64 -mcpucortex-a55 -debug-onlymisched input.ll -o /dev/null注意这需要你的LLVM是Debug或带足够日志符号的构建版本。Release构建通常不带这些日志。日志里会打出依赖图的构建过程、每个SUnit的关键信息、就绪队列的变化以及调度器最终选择的顺序。这是理解调度器行为最有效的方法。我自己常用的技巧是先把代码量降到最小写一个只含几条算术指令的IR函数然后盯着日志看每条指令被调度到什么位置。看得多了就能建立“DAG结构和机器码顺序”之间的直觉。5.2 查看调度后的DAG视图LLVM在Debug构建下还支持把调度DAG可视化导出。misched阶段通常对应一个Graphviz输出选项不同版本名字不完全一样但类似-view-misched-dags这样。如果LLVM编译时带了Graphviz支持跑完命令后会弹出DAG图。节点上会标注SUnit编号、所属指令、依赖关系。线下调试时这种图比几百行日志直观得多。我调试时习惯把关键路径上的节点用颜色区分开。这样一眼就能看出来到底是指令延迟太长导致关键路径难压缩还是依赖关系太紧密导致没办法乱序。5.3 如何判断调度是否真的在发挥作用看调度器有没有用最朴素的方法还是对比禁用和启用调度后的汇编顺序。但汇编顺序本身不等于执行性能关键还得看实际运行周期。在算法层面你可以给目标CPU写一个小微基准比如用循环做一连串存在依赖的浮点运算分别编译成启用调度和不启用调度的版本再在真机或模拟器上统计周期数。要注意的是现代CPU乱序执行能力很强如果基准代码非常短硬件本身的reorder能力会把调度的差异抹平。所以测试代码最好足够长让调度窗口的效应累积起来才能看出差距。另外一个容易被忽略的观察点是spill和reload的数量。有时候调度器为了压短关键路径会把太多独立指令塞到一起导致寄存器分配阶段临时变量变多反而触发更多溢出。这是pre-RA调度和寄存器分配之间最常见的冲突。最终性能是否提高一定要以整体输出为准不能只看局部指令顺序。6. 学习过程中踩过的几个概念坑篇幅有限最后补充几个我自己反复踩的坑。这些不是代码错误而是概念理解上的偏差但同样会让人在调试时走很多弯路。6.1 Pre-RA和Post-RA的优化目标不一样我一开始以为既然pre-RA已经做了一遍调度post-RA再做一遍不是重复劳动吗后来才意识到pre-RA的约束是虚拟寄存器它假设虚拟寄存器无限多所以很多反依赖根本不存在。而寄存器分配完成后物理寄存器数量有限真实的反依赖、输出依赖大量出现原有的顺序突然有了新的牵制。post-RA才是真正贴近硬件可见约束的那一次调度。这也解释了我之前遇到过的一个现象一个后端明明开了pre-RA调度性能却没有明显提升。后来查了一下发现它的SchedMachineModel里没有设置PostRAScheduler和适合post-RA的调度模型所以关键的后置优化根本没跑。6.2 乱序执行CPU上编译器调度照样重要有段时间我和同事争论说x86的CPU乱序窗口那么大是不是编译器调度不重要了。实际数据告诉我们不是。乱序执行CPU的重排窗口虽然大但硬件里用来隐藏延迟的资源是有限的比如ROB条目、物理寄存器堆、load/store队列。一旦指令密度过高保留站被占满硬件就不得不保守发射。编译器预先在软件层面把长延迟指令提前相当于帮硬件分担了重排压力。所以在ARM Cortex-A55这种顺序执行的CPU上编译器调度直接决定指令间空泡在高端的Cortex-X系列上编译器调度更多是辅助硬件把乱序资源用在真正需要的地方。6.3 没有准确的机器模型谈调度优化就是空中楼阁前阵子我在一个实验后端上看到调度顺序一直不理想排查了很久最后发现问题出在SchedMachineModel上某些访存指令根本没有定义延迟调度器只能按默认值处理结果就是把长延迟load排在了太靠后的位置。这件事给我的教训很深。指令调度器和机器模型是紧密结合的调度器从模型里读延迟和资源信息模型不准调度器再聪明也没用。拿到一个新CPU时先把指令延迟表、端口占用数、发射宽度这些基础数据填准再去优化调度算法顺序一定不要反。6.4 不是每个基本块都需要拼命调度调度器虽然会把每个基本块都过一遍但真正值得花重兵优化的基本块很少。循环体内的代码是热点中的热点而一些只会执行一次的基本块强行调度反而可能因为指令重排增加代码体积或者让栈帧更加拥挤。现代LLVM里已经有很复杂的启发式来判断“这个块值不值得调度”比如分析数据依赖深度、估计资源压力。但也别迷信启发式后端做性能分析时用perf看热点函数在哪个基本块再针对性地看那块机器码的调度质量永远是更靠谱的方法。指令调度这块内容我是越学越觉得它像桥梁一边连着编译器的DAG和算法另一边连着CPU的流水线和微架构。如果目的只是让编译器“能工作”完全不了解调度也可以但如果想让生成代码的效率逼近手写汇编这一块是绕不开的。而且这里面的坑基本都是“不知道有约束”造成的不是“不知道怎么做”造成的。把依赖关系、机器模型、硬件执行模型这三本账摆清楚后面再看调度器源码就不会觉得是一团乱麻了。