第7章 代码生成（目标机器码） Code Generation

一、导读

1.1 本章学习目标

理解代码生成在编译器后端的核心地位及其与前端、优化器的接口关系

掌握指令选择（Instruction Selection）的主要方法：基于树覆盖、基于动态规划和基于表驱动的方法

深入理解寄存器分配（Register Allocation）的问题本质、图着色算法及其工程实现

掌握指令调度（Instruction Scheduling）的原理，理解流水线、数据冒险和控制冒险的处理

了解活动记录（Activation Record）的设计和函数调用的底层实现机制

理解目标机器描述（Machine Description）的抽象方法及其对编译器可移植性的影响

掌握代码生成的质量评估方法：代码大小、执行速度和编译时间的权衡

1.2 为什么本章如此重要

代码生成是编译过程的最终阶段，它将抽象的中间表示转化为目标机器能够直接执行的指令序列。这一阶段的质量直接决定了最终程序的性能表现——即使前端和优化器做得再好，如果代码生成阶段不能有效地利用目标机器的特性，生成的程序也无法发挥硬件的全部潜力。

代码生成也是编译器工程中最具机器相关性的部分。不同的处理器架构（x86、ARM、RISC-V、MIPS）有不同的指令集、寄存器数量、寻址模式和流水线特性。一个优秀的代码生成器需要深入理解目标机器的微架构，将优化后的中间表示映射为最高效的指令序列。这种"从抽象到具体"的映射过程，体现了编译器设计中"关注点分离"和"抽象层次管理"的核心思想。

从工业实践角度看，代码生成技术的影响远超编译器本身。硬件设计者使用代码生成器评估新指令集的性能（如 LLVM 的 TableGen）；性能工程师使用指令调度技术分析流水线瓶颈；嵌入式开发者需要理解寄存器分配和栈帧布局以优化资源受限环境下的代码。掌握代码生成的知识，使你能够在软件和硬件的交界处做出更明智的工程决策。

1.3 核心问题引导

指令选择为什么不是简单的"一对一映射"？如何处理中间代码操作与目标指令之间的语义差距？

寄存器分配为什么是 NP 难问题？图着色算法如何将其转化为可解的近似问题？

当寄存器不够时，溢出（Spill）策略如何选择哪些变量溢出到内存？如何最小化溢出代价？

指令调度如何处理流水线中的数据冒险（RAW、WAR、WAW）和控制冒险？

活动记录（栈帧）的布局如何影响函数调用的效率和正确性？

如何设计一个机器描述，使得同一套代码生成逻辑能支持多种目标架构？

现代处理器的超标量执行和乱序执行对编译器的指令调度提出了什么新要求？

二、核心概念详解

2.1 指令选择（约 700 字）

指令选择（Instruction Selection）是将中间表示的操作映射到目标机器指令的过程。这是代码生成的第一步，也是最基础的步骤。指令选择的质量直接影响生成代码的效率和紧凑性。

最简单的指令选择方法是逐条翻译（Linear Selection）：遍历中间代码的每条指令，为每条中间指令选择一条或一组等价的目标机器指令。例如，三地址码 t = a + b 可以映射为 x86 的 mov eax, [a]; add eax, [b]; mov [t], eax。这种方法实现简单，但往往不能利用目标机器的复杂寻址模式和复合指令。

更高级的方法是基于树模式匹配（Tree-Pattern Matching）的指令选择。它将中间代码表示为表达式树（或 DAG），然后用目标机器的指令模式去覆盖（Tile）这棵树。每个指令模式对应一条目标指令或指令序列，带有相应的代价（代码大小或执行周期）。指令选择的目标是找到代价最小的覆盖方案。

例如，表达式 a + b * c 的树表示为 +(a, *(b, c))。x86 架构有一条复合指令 add eax, [b + c * 4]（基址加变址寻址），它可以一步完成乘法和加法，代价为 1 个周期。而分别选择乘法和加法指令需要 2 条指令、2 个周期。树模式匹配能够发现并利用这种复合指令，生成更优的代码。

动态规划（Dynamic Programming）是解决最优树覆盖的经典算法。对于树的每个子树，计算所有可能的覆盖方式及其代价，选择代价最小的方案。由于树的子问题具有最优子结构和重叠子问题性质，动态规划能在多项式时间内找到全局最优解。

BURS（Bottom-Up Rewriting System）是一种高效的基于动态规划的指令选择算法，被广泛应用于实际编译器中。它将指令模式表示为树重写规则，自底向上地计算每个子树的最优覆盖。LLVM 的 ISel（Instruction Selection）模块使用 DAGCombiner 和 SelectionDAG 实现了类似的指令选择机制。

实际编译器中的指令选择还需要处理许多细节：不同类型（int、float、pointer）需要不同的指令；不同的寻址模式（立即数、寄存器、基址偏移、基址加变址）影响指令的选择和代价；条件码（Condition Code）的设置和使用需要协调；多字操作（如 64 位整数在 32 位机器上需要两条指令）需要特殊处理。

2.2 寄存器分配（约 800 字）

寄存器分配（Register Allocation）是代码生成中最复杂也最关键的优化问题。寄存器是 CPU 中最快的存储单元，访问寄存器只需 0 个周期（与指令同步），而访问内存可能需要数十到数百个周期。将频繁使用的变量分配到寄存器中，可以极大地提升程序性能。然而，寄存器的数量是有限的（x86 有 16 个通用寄存器，ARM 有 31 个），不可能将所有变量都放入寄存器。

寄存器分配问题可以形式化为：给定一组变量和有限的寄存器数量，决定哪些变量分配到寄存器、哪些变量溢出到内存，使得溢出代价最小。这是一个 NP 难问题，实际编译器使用启发式算法求解。

图着色算法（Graph Coloring）是最经典的寄存器分配方法，由 Chaitin 和 Briggs 在 1980 年代提出。其核心思想是：构建干扰图（Interference Graph），图的节点是变量（或变量的活跃范围），如果两个变量的活跃范围重叠（即它们在程序的某点同时活跃），则在它们之间连一条边。寄存器分配等价于对干扰图进行 K-着色（K 为可用寄存器数量），使得相邻节点颜色不同。每个颜色对应一个物理寄存器。

如果干扰图不能用 K 种颜色着色（变量太多，寄存器不够），则需要溢出（Spill）：选择某些节点"溢出"到内存，将它们从干扰图中移除（因为溢出变量的值存储在内存中，不再占用寄存器），然后对剩余节点进行着色。溢出节点在每次使用前从内存加载（Load），在每次定义后存储（Store）到内存。

图着色寄存器分配的流程如下：首先进行活性分析（Liveness Analysis），确定每个变量在哪些点活跃；然后构建干扰图；尝试用 K 种颜色着色；如果着色失败，选择溢出候选变量（通常选择活跃范围最长或访问频率最低的变量），将其溢出，简化干扰图，重新尝试着色；重复直到着色成功。

溢出代价的估计是算法的关键。一个变量的溢出代价等于它在程序中被加载和存储的总次数乘以内存访问的延迟。精确的溢出代价估计需要考虑循环权重（循环内的访问比循环外的访问代价更高）和共轭关系（如果两个变量总是同时溢出和加载，它们可以共享同一个溢出位置——溢出共轭，Spill Coalescing）。

现代编译器的寄存器分配通常结合指令选择和调度进行（称为联合优化），以获得全局最优的代码生成效果。例如，LLVM 的 Greedy Register Allocator 在着色基础上增加了溢出替换（Rematerialization）、溢出共轭和拆分（Splitting）等高级技术。

2.3 指令调度（约 600 字）

指令调度（Instruction Scheduling）是重新排列指令顺序以充分利用处理器流水线和其他并行执行资源的技术。现代处理器采用流水线架构，将每条指令的执行分为取指（Fetch）、译码（Decode）、执行（Execute）、访存（Memory）、写回（Write Back）等阶段。理想情况下，流水线每个时钟周期可以完成一条指令，但数据冒险和控制冒险会导致流水线停顿（Stall）。

数据冒险有三种类型：RAW（Read After Write，读后写），后续指令需要读取前一条指令写入的结果，必须等待前一条指令写回完成；WAR（Write After Read，写后读），后续指令写入的位置是前一条指令需要读取的，不能提前写入；WAW（Write After Write，写后写），两条指令写入同一位置，必须保持写入顺序。在指令调度中，RAW 是最常见的冒险，通过重新排列指令顺序，在相关指令之间插入无关指令来填充流水线空隙。

控制冒险由分支指令引起：分支目标在译码后才能确定，在确定之前流水线无法继续取指。解决方案包括分支预测（硬件层面）和分支延迟槽（软件层面，在分支指令后放置无论分支方向都会执行的指令）。

指令调度的算法主要有两种。列表调度（List Scheduling）在基本块内进行，维护一个就绪列表（Ready List），包含所有操作数已就绪的指令。每个时钟周期从就绪列表中选择优先级最高的指令发射（Issue）。优先级通常基于关键路径（Critical Path）长度：位于关键路径上的指令优先调度。

全局调度跨越基本块边界，可以将指令移出循环或移入分支的公共路径。全局调度更复杂，需要处理跨基本块的寄存器活性变化和异常语义保持。

2.4 活动记录与函数调用实现（约 600 字）

活动记录（Activation Record），也称为栈帧（Stack Frame），是函数调用时在运行时栈上分配的内存区域，用于存储函数的局部变量、参数、返回地址和保存的寄存器。活动记录的设计直接影响函数调用的效率和正确性。

一个典型的活动记录包含以下区域（从高地址到低地址）：参数区（调用者存放传递给被调用函数的参数）、返回地址（调用者存放函数返回后的下一条指令地址）、动态链（指向上一个活动记录的指针，用于访问外层作用域的变量）、保存的寄存器（被调用者保存的、需要在返回时恢复的寄存器值）、局部变量区（函数的局部变量）。

调用约定（Calling Convention）定义了调用者和被调用者之间的协议：哪些寄存器用于传递参数（如 x86-64 System V ABI 使用 rdi、rsi、rdx、rcx、r8、r9 传递前六个整数参数）、哪些寄存器由调用者保存（Caller-Saved）、哪些由被调用者保存（Callee-Saved）、栈指针对齐要求等。调用约定是二进制兼容性的基础——不同编译器生成的代码能够互相调用，前提是遵循相同的调用约定。

函数调用的代码生成流程：调用者在调用前将参数放入约定寄存器或压栈，执行 call 指令（将返回地址压栈并跳转到目标函数）；被调用者首先保存需要使用的 callee-saved 寄存器，分配局部变量空间，执行函数体，将返回值放入约定寄存器，恢复 callee-saved 寄存器，执行 ret 指令返回；调用者从约定寄存器获取返回值，清理参数区（如果需要）。

栈帧布局的优化包括：减少栈帧大小（使用更多寄存器减少内存存储）、消除栈帧（如果函数是叶函数且不需要额外栈空间）、栈帧指针省略（Frame Pointer Omission, FPO，用栈指针直接访问局部变量，释放一个寄存器）。

三、深入分析与讨论

3.1 图着色寄存器分配的深入分析（约 500 字）

图着色寄存器分配的实际实现比理论描述复杂得多。几个关键的工程问题需要解决：

溢出选择策略：当着色失败时，选择哪个变量溢出对代码性能影响巨大。简单的策略是选择度数最高（干扰最多）的节点溢出，因为它移除后能最大程度简化干扰图。更精细的策略考虑变量的活跃范围长度、访问频率和循环权重。

共轭（Coalescing）：如果两条赋值指令 a = b 的源和目标目前分配到不同寄存器，可以尝试将它们合并（Coalesce）到同一寄存器，消除复制指令。但合并会增加节点的度数，可能导致着色失败。保守共轭（Conservative Coalescing）只在合并不会导致着色失败时才执行。

位预着色（Biased Pre-coloring）：某些变量需要分配到特定寄存器（如函数参数必须使用约定寄存器、系统调用参数必须使用特定寄存器）。这些约束通过预着色（Pre-coloring）处理：将需要固定寄存器的变量预先着色，然后对其他变量进行着色。

迭代分裂（Iterated Splitting）：对于活跃范围很长的变量，可以将其分裂（Split）为多个短活跃范围的版本，每个版本分配到不同寄存器。这减少了单个变量的干扰，提高着色成功率，但需要在分裂点插入复制指令。

3.2 目标机器描述的抽象方法（约 500 字）

为了让编译器支持多种目标架构，需要将机器相关的信息从代码生成逻辑中分离出来，形成独立的机器描述（Machine Description）。

GCC 使用 C 宏和模板文件描述目标机器：每个架构有一个 .md（Machine Description）文件，定义指令模式、寄存器类、代价模型等。LLVM 使用 TableGen 框架：.td（Table Description）文件描述寄存器文件、指令集、寻址模式等，TableGen 工具将其转换为 C++ 代码。

机器描述的核心内容包括：寄存器文件（Register File），定义可用寄存器及其类别（通用寄存器、浮点寄存器等）；指令集（Instruction Set），定义每条指令的语法、语义、操作数类型和延迟；寻址模式（Addressing Modes），定义合法的内存访问方式（立即数、寄存器间接、基址偏移等）；调用约定（Calling Convention），定义参数传递和返回值规则；代价模型（Cost Model），定义各指令的延迟和吞吐量，用于指令调度和优化决策。

良好的机器描述抽象使得添加新架构支持只需编写描述文件，而不需要修改代码生成的核心逻辑。这种"数据驱动"的设计是编译器可移植性的关键。

3.3 现代处理器的挑战（约 400 字）

现代处理器的微架构给代码生成带来了新的挑战。超标量执行允许每个周期发射多条指令，要求指令调度器识别更多的指令级并行性。乱序执行（Out-of-Order Execution）在硬件层面重排指令，使得编译器层面的调度效果减弱，但编译器仍需要避免假共享和内存序问题。SIMD 指令（如 SSE、AVX、NEON）要求编译器将标量代码向量化，这需要在循环分析和依赖分析的基础上进行复杂的变换。

此外，多核处理器要求编译器支持多线程代码生成和内存模型语义；异构计算（CPU + GPU）要求编译器能够将计算任务分配到不同设备；安全特性（如 Intel CET、ARM PAC）要求编译器生成包含安全指令的代码。这些新需求不断推动代码生成技术的发展。

四、实践案例

4.1 案例一：x86-64 函数调用的代码生成（约 400 字）

以 x86-64 System V ABI 为例，展示函数 int add(int a, int b) { return a + b; } 的代码生成过程。

调用者代码：将参数 a 放入 rdi，b 放入 rsi（遵循调用约定），执行 call add 指令。

被调用者（add 函数）代码：

add:
  push rbp           ; 保存基址指针（callee-saved）
  mov rbp, rsp       ; 设置新的基址指针
  mov eax, edi       ; 将参数 a（在 edi 中）移入 eax（返回值寄存器）
  add eax, esi       ; 加上参数 b（在 esi 中）
  pop rbp            ; 恢复基址指针
  ret                ; 返回（弹出返回地址并跳转）

这个简单的例子展示了调用约定的应用：参数通过 rdi/rsi 传递，返回值通过 eax 返回，rbp 由被调用者保存和恢复。由于 add 是叶函数且不需要局部变量，栈帧可以省略（在启用 -fomit-frame-pointer 时连 push/pop rbp 也可以省略）。

4.2 案例二：寄存器分配的图着色过程（约 400 字）

考虑以下基本块的活性分析和干扰图构建：

B1: a = 1; b = 2;
B2: c = a + b; d = c * 2;
B3: e = d + a; f = e - b;

活性分析结果：a 在 B1-B3 活跃，b 在 B1-B3 活跃，c 在 B2-B3 活跃，d 在 B2-B3 活跃，e 在 B3 活跃，f 在 B3 活跃。

干扰图：a 干扰 b、c、d、e（因为 a 与这些变量的活跃范围重叠）；b 干扰 a、c、d、e、f；c 干扰 a、b、d、e；d 干扰 a、b、c、e；e 干扰 a、b、c、d、f；f 干扰 b、e。

假设可用 3 个寄存器（K=3），尝试 3-着色。由于干扰图较密集，可能需要溢出某些变量。选择度数最高的 b 溢出到内存，移除 b 后重新着色，如果成功则为 a、c、d、e、f 分配寄存器，b 在使用时从内存加载，定义后存储到内存。

五、常见误区与注意事项

5.1 误区一：寄存器越多越好

虽然更多寄存器通常意味着更少的溢出和更好的性能，但过多的寄存器也有代价：增加指令编码长度（需要更多位来指定寄存器）、增加上下文切换开销（需要保存和恢复更多寄存器）、增加芯片面积和功耗。ARM 选择 31 个通用寄存器、RISC-V 选择 32 个，是经过仔细权衡的结果。

5.2 误区二：指令调度只在编译时重要

现代处理器的乱序执行在硬件层面做了大量调度工作，但这不意味着编译时调度无关紧要。硬件调度的窗口有限（通常只有几十条指令），编译器层面的全局调度可以跨越更大的范围发现并行性。此外，编译时调度还可以优化指令编码、对齐和缓存局部性，这些是硬件调度无法处理的。

5.3 误区三：生成的汇编代码越短越快

代码长度和执行速度并不总是正相关。某些短指令可能需要更多周期执行（如复杂的寻址模式），而某些长指令序列可能通过利用流水线并行性达到更高的吞吐量。此外，代码长度影响指令缓存命中率，过长的代码可能导致频繁的缓存未命中。代码生成需要在代码大小和执行速度之间权衡。

5.4 注意事项：ABI 兼容性与稳定性

调用约定和 ABI（Application Binary Interface）是二进制兼容性的基础。编译器生成的代码必须严格遵循目标平台的 ABI，否则无法与其他编译器生成的代码或系统库正确链接和交互。ABI 的变化（如新增寄存器、修改栈对齐要求）需要整个工具链的协调更新。在跨平台开发中，理解目标平台的 ABI 是避免链接错误和运行时崩溃的关键。

六、本章小结

本章系统讲解了编译器代码生成的核心技术。指令选择将中间表示映射到目标机器指令，树模式匹配和动态规划算法能够发现并利用复合指令的优势。寄存器分配通过图着色算法将变量分配到有限的物理寄存器，溢出策略处理寄存器不足的情况。指令调度重排指令顺序以填充流水线空隙、减少冒险停顿。活动记录的设计实现了函数调用的底层机制，调用约定保证了二进制兼容性。机器描述的抽象使得编译器能够支持多种目标架构。现代处理器的超标量、乱序执行和 SIMD 特性对代码生成提出了新的挑战，推动着技术的持续演进。掌握代码生成技术，是构建完整编译器的最后也是最关键的一步。

七、思考题与练习

为三地址码 t = a + b * c 生成 x86-64 汇编代码，分别使用"逐条翻译"和"利用复合寻址模式"两种策略，比较生成代码的效率。

为以下代码构建干扰图，并进行 3-着色寄存器分配：a = 1; b = 2; c = a + b; d = c * a; e = d - b;

分析以下代码的活性变量，确定哪些变量可以共享同一寄存器：x = 1; y = 2; z = x + y; w = z * 2; x = w + 1;

设计一个基本的指令调度算法，处理以下指令序列的 RAW 冒险：load r1, [addr]; add r2, r1, r3; store r2, [addr2];

调研 x86-64 System V ABI 和 Windows x64 调用约定的差异，说明参数传递、返回值和寄存器保存规则的不同之处。

阅读 LLVM 的 TableGen 文件（如 X86InstrInfo.td），说明指令模式定义的语法和语义。

分析 SIMD 向量化对代码生成的挑战：如何将标量循环 for (i=0; i<n; i++) a[i] = b[i] + c[i]; 转换为 SIMD 指令？

调研 RISC-V 的指令集架构设计，说明其寄存器文件、指令格式和调用约定的特点，并与 x86-64 和 ARM 进行比较。