编译器目标代码生成原理

可视化演示

目标代码生成将优化后的IR转换为目标机器指令，涉及指令选择、寄存器分配与指令调度。本文详解基于模式树的指令选择... 切换模式查看不同维度。

后端流程总览

主厨的菜谱写得再漂亮，终究要落到后厨的锅碗瓢盆上。菜谱上写着“鸡丁炒青椒”，但鸡丁是要焯水还是过油？青椒是先下锅还是后下锅？这些细节主厨没写，全靠后厨团队根据自家厨房的条件临场发挥。编译器的前端和优化器就是那位“主厨”，它们产出的中间表示（IR）就是这份菜谱——描述了计算“做什么”，却不关心目标 CPU 具体“怎么做”。

在编译器中，这份菜谱的“后厨”叫目标代码生成。它是编译流程的最后一个主要阶段，位置在“优化 IR”之后。它读入优化后的中间表示，输出目标机器的汇编代码或机器码。真正落地时，它内部并不是一步到位的傻瓜翻译，而是一条环环相扣的流水线，分成四个子任务：先给每条 IR 操作挑一条目标指令（指令选择），再给指令中的变量分配物理寄存器（寄存器分配），然后重排指令顺序让 CPU 的多个执行单元都忙起来（指令调度），最后把加工好的序列输出成汇编文本（代码发射）。

$$\displaystyle ASM = \text{Emitting}(\text{Scheduling}(\text{Allocating}(\text{Selecting}(IR))))$$

1. IR：输入——优化后的中间表示，像后厨收到的菜谱，描述了要做的运算。

$$\text{IR}$$

2. Selecting：指令选择，把 IR 操作映射为目标机器的指令，相当于为每道菜挑一口合适的锅。

$$\text{Selecting}(IR)$$

3. Allocating：寄存器分配，把虚拟变量安排到有限的物理寄存器上，相当于把菜分配到有限的灶台。

$$\text{Allocating}(\text{Selecting}(IR))$$

4. Scheduling：指令调度，重排指令顺序以减少流水线停顿，相当于安排做菜先后顺序。

$$\text{Scheduling}(\cdots)$$

5. Emitting：代码发射，把最终指令序列输出成汇编或机器码文件，相当于把成品菜端出后厨。

所以，后端一次完整的运转，就像后厨的四道工位依次开动：菜谱入场、选锅、分灶、排顺序、出锅装盘。任何一个环节偷懒，最终端到客人桌上的菜都会慢半拍。理解了这条总流水线，我们就能逐个工位拆开，看看每一道工序背后藏着什么算法。

指令选择算法

菜谱上说“把鸡丁炒熟”。炒、炸、炖、烤都能把鸡丁做熟，但耗时和口感天差地别。经验丰富的厨师不会老老实实每种方法试一遍，而是瞄一眼食材和灶台条件，直接从炊具库里选最合适的一口锅。指令选择要解决的正是同一个问题：IR 里写的是“把 a 和 b 相加”，而 CPU 的指令集里有加法指令、有带偏移的寻址加载指令、有乘加融合指令……选哪一条，决定了代码的最终质量。

编译器在这个环节把 IR 看作一棵“表达式树”：根节点是最终结果，子节点是操作数。目标机器指令则被描述成一个个“模板小树”——比如“加法指令”这个小树有两个叶子，能接住两个子表达式。指令选择的本质，就是用一组模板小树去覆盖 IR 大树，使总代价最小。最经典的解法叫“基于模式树的动态规划选择”：自底向上遍历 IR 树，对每个节点，枚举所有能覆盖它的指令模板，计算“用这个模板的代价 + 覆盖剩余子节点的最小代价”，取最小值。这样每个节点都记住自己最便宜的覆盖方案，最后自顶向下输出指令序列。

$$\displaystyle \text{cost}(n) = \min_{p \in P(n)} \left[ \text{cost}(p) + \sum_{c \in \text{sub}(n,p)} \text{cost}(c) \right]$$

1. cost(n)：以节点 n 为根的子树生成目标代码的最小代价，好比“把这盘鸡丁做完的最短时间”。

$$\text{cost}(n)$$

2. P(n)：能覆盖节点 n 的所有指令模板集合，相当于面对“炒鸡丁”时厨师脑子里闪过的所有炊具方案。

$$p \in P(n)$$

3. cost(p)：指令模板 p 自身的执行代价，比如用炒锅的代价是 2 个周期，用烤箱是 20 个周期。

$$\text{cost}(p)$$

4. sub(n,p)：套用模板 p 后，模板的叶子位置对应的、还需要继续处理的子节点集合。

$$c \in \text{sub}(n, p)$$

5. min：遍历所有候选模板，取总代价最小的一个——这就是动态规划的“决策”步骤。

$$\min_{p \in P(n)}$$

优质指令选择对性能的影响立竿见影。就像后厨里“会用一口锅顺手完成三道菜”的老师傅，同样的菜单，他的出菜速度能快出一倍。选择完之后，指令是选好了，可新的麻烦来了：这些指令里出现的变量，该放哪儿？这就是寄存器分配的故事。

寄存器分配

后厨的灶台永远不够用。菜谱可能同时要求 8 道菜各占一个灶，但厨房只有 4 个灶台。总厨的解决办法是错峰：不冲突的两道菜可以轮流用同一个灶，实在撞在一起的就先端到备餐台上放着，等灶腾出来再回锅。CPU 里的寄存器就是“灶台”——数量极少（通常几十个），但访问速度比内存快几个数量级；而 IR 里的临时变量可能成百上千。寄存器分配的任务，就是决定每个变量在每一刻占哪个寄存器，装不下的变量“溢出”到内存（相当于备餐台）。

经典的寄存器分配算法叫图着色。先把问题画成一张冲突图：每个变量是一个节点；如果两个变量在某段指令里同时处于活跃状态（都需要寄存器），就在它们之间连一条边。然后给这张图染色——每种颜色代表一个物理寄存器，规则是“一条边两端的节点颜色必须不同”。如果整张图能用 k 种颜色染完，说明 k 个寄存器完全够用。染不过来时，就挑一些“代价最小”的变量溢出到内存，重新染色。除图着色外，还有更轻量的线性扫描算法：按变量活跃区间顺序扫描，能分就分、分不下就溢出，特别适合即时编译（JIT）这类对速度敏感的场景。

$$\displaystyle \exists\, c: V \to \{1,\ldots,k\} \;\; \text{s.t.} \;\; (u,v) \in E \Rightarrow c(u) \neq c(v)$$

1. ∃c：存在一个染色函数 c，也就是存在一种把变量分给寄存器的方案。

$$\exists\, c$$

2. V：所有变量节点的集合，对应后厨里所有需要灶台的菜。

$$V$$

3. {1,…,k}：k 种颜色编号，对应 k 个物理寄存器，也就是 k 个灶台。

$$\{1,\ldots,k\}$$

4. s.t.：使得（such that），表示后面的是这个染色方案必须满足的约束条件。

$$\text{s.t.}$$

5. (u,v)∈E ⇒ c(u)≠c(v)：只要两个变量在冲突图里有边相连（活跃区间重叠），它们的颜色就必须不同。

$$(u,v) \in E \Rightarrow c(u) \neq c(v)$$

图着色把“灶台分配”变成了一道漂亮的数学题。总厨排灶台排得再周密，也只能保证“够不够用”，却保证不了“上菜顺序最优”——因为同样一盘菜，先切蒜还是先烧油，顺序不同，总耗时也不同。这就是指令调度要操心的事。

指令调度

一位熟练的厨师绝不会傻等水烧开再切菜——他会先烧上水，利用等待时间切葱姜蒜。现代 CPU 也是这个脾气：处理器内部有多个功能单元（就好比多个厨师），能同时执行好几条指令。但指令之间不是你想重排就能重排的。如果指令 B 要使用指令 A 的计算结果，B 必须等到 A 完成——这叫数据依赖。此外还有控制依赖（分支指令决定后面能不能执行）。指令调度要做的，是在满足所有依赖的前提下，重排指令顺序，让 CPU 的各执行单元尽量别闲着。

调度的第一步是构建依赖图：每个节点是一条指令，有依赖关系的指令之间连一条有向边，边上的权重是延迟——例如加法 2 拍、乘法 5 拍。然后从依赖图出发做调度。最常用的是列表调度算法：维护一个“就绪队列”，里面是所有前驱都已完成、可以立即发射的指令。每一步从就绪队列里挑一条“优先级最高”的发射。优先级怎么定？最经典的启发式是关键路径长度：从这条指令出发，沿依赖图走到出口节点，把沿途所有延迟加起来，路径越长优先级越高。因为关键路径决定了整个指令序列执行时间的下界，优先安排它准没错。

$$\displaystyle \text{priority}(n) = \text{delay}(n) + \max_{m \in \text{succ}(n)} \text{priority}(m)$$

1. priority(n)：指令 n 的调度优先级，数值越大越先发射，好比“越拖后腿的工序越要早点动手”。

$$\text{priority}(n)$$

2. delay(n)：指令 n 自身的执行延迟，比如乘法器要 5 拍、加法器只要 2 拍。

$$\text{delay}(n)$$

3. succ(n)：依赖图中 n 的后继指令集合，也就是必须等 n 完成后才能执行的指令。

$$m \in \text{succ}(n)$$

4. max：取后继指令中最大的优先级——把最长的等待链传递上来。

$$\max$$

5. 递归定义：优先级从出口节点倒推回入口，本质上是在计算“关键路径长度”。

$$\text{priority}(m)$$

列表调度就像一位给全厨房排时间表的管家：先把最耗时的那条“炖汤链”安排得明明白白，再把切菜、备料等零碎活穿插进等待时间。经过调度，CPU 的流水线被喂得满满当当。但调度再完美，指令序列里仍可能藏着一些“多余动作”，这时候就需要最后一位老师傅出场——窥孔优化。

窥孔优化

经验丰富的大厨经过操作台时，偶尔会透过传菜口的小窗瞟一眼眼前的几道工序，突然发现：“哎，这盘菜不是已经放过盐了吗？怎么又撒了一把？”于是顺手把多余的盐抖回盐罐。这种改进不需要把整个菜单从头捋一遍，只需要反复看眼前一小段操作。窥孔优化（peephole optimization）就是这个思路：生成目标指令后，编译器用一个只有几条指令宽的“小窗口”在指令序列上滑动，每看到一个符合规则的模式，就用一个更优的等价模式替换掉。

窥孔优化的规则都是些“局部小手术”。常见的有四类：冗余消除——刚加载了变量又立刻存回去，直接删掉后面的操作；强度削减——把昂贵的指令换成廉价指令，比如用左移代替乘以 2 的幂；跳转优化——一个跳转指令恰好跳到下一条指令，那这个跳转就是废话，直接删除；常量合并——编译期就把 2 + 3 这类常量表达式的值算出来。因为窗口极小、规则固定，窥孔优化既安全又高效，是每个成熟编译器后端必备的收尾工序。

$$\displaystyle x \times 2^k \;\Longrightarrow\; x \ll k$$

1. x：任意整型变量，被乘数。

$$x$$

2. ×2^k：乘以 2 的 k 次幂，例如乘以 2、4、8……

$$\times 2^k$$

3. ⟹：等价替换符号，表示左右两边计算结果完全一致，可以安全替换。

$$\Longrightarrow$$

4. ≪k：左移 k 位，二进制每左移一位相当于乘以一次 2。

$$\ll k$$

5. 收益：左边是昂贵的 MUL 指令，右边是廉价的 SHL 指令，替换后程序语义不变但执行更快。

窥孔优化每一次只省一点点，但正如大厨每次顺手省掉一个多余动作，一天下来能省出半小时——整个指令序列经它打磨后，体积更小、执行更快。不过，以上所有优化都建立在一个假设上：CPU 是“听话”地一条接一条执行指令。可现代 CPU 是流水线作业，遇到岔路口（分支）时，总会有一个让人头疼的等待间隙。

分支延迟槽

传菜员端着菜走到后厨岔路口，得先确认“这道菜是去 1 号桌还是 2 号桌？”在等答复的这一个瞬间，人只能原地站着，白白浪费时间。CPU 的流水线也有类似的“岔路口”：当执行到分支指令时，后面预取进流水线的指令还不确定该不该执行，硬件得等分支结果算出来，流水线因此“打嗝”停顿一拍。在早期的 RISC 架构（如 MIPS）中，编译器被要求主动解决这个问题，办法就是在分支指令后面留一个延迟槽：槽里必须放一条指令，这条指令无论分支跳不跳都会执行。

延迟槽怎么填，有讲究。编译器有三种经典策略：从分支之前的指令挪一条下来——这是最安全的，因为那条指令本来就要执行；从跳转目标处挪一条——但只在分支真的跳转时才安全；从分支不跳转时紧接着的下一条指令挪过来——只在分支不跳时安全。第三种情况还要小心：如果挪过来的指令会改变分支要判断的条件，那就不能挪。实在找不到合适的填充指令，就放一条空操作 NOP 占位——但那等于承认这一拍浪费了。

$$\displaystyle T_{\text{branch}} = \begin{cases} T_{\text{jump}} + T_{\text{stall}}, & \text{empty slot} \\ T_{\text{jump}}, & \text{filled slot} \end{cases}$$

1. T_branch：执行一条分支指令总共需要的时间。

$$T_{\text{branch}}$$

2. T_jump：分支跳转本身的时间，也就是在岔路口完成转向所需的一拍。

$$T_{\text{jump}}$$

3. T_stall：流水线停顿时间，即传菜员站在原地等答复的那一拍。

$$T_{\text{stall}}$$

4. empty slot：延迟槽没有填入有效指令，等待被白白浪费。

$$\text{empty slot}$$

5. filled slot：延迟槽被一条无关指令填满，等待被利用，总耗时下降。

延迟槽就像等红灯时顺手系好安全带——本来要浪费的等待时间，塞进一件小事就赚了。后来，现代 CPU 用硬件分支预测取代了编译器延迟槽，但理解延迟槽依然是理解流水线冲突、推测执行这些底层原理的最佳入门课。到这儿，定制后厨的每一道工序都过了一遍。最后我们看看，现代工业界的“中央厨房”—— LLVM——是怎么把这些工序标准化的。

LLVM实践

前面讲的是“定制后厨”：为一家特定的餐厅、一套特定的炊具量身设计流程。而 LLVM 是一套能把任意餐厅快速搭建起来的“中央厨房模板”：它把后厨的工位抽象成标准接口，你要开一家川菜馆还是西餐厅，只需要按接口提交一份“炊具清单”——目标机器有哪些指令、每条指令长什么样、代价多少——中央厨房的整套流水线就自动为你运转。这份“炊具清单”在 LLVM 里用 TableGen 描述语言编写。

LLVM 后端的主干流水线非常清晰。第一步，SelectionDAG 构建：把 LLVM IR 转换成一种面向指令选择的 DAG（有向无环图）表示，相当于把菜谱整理成“哪些食材要合并处理”的操作图。第二步，指令选择：DAG 匹配阶段，用 TableGen 生成的匹配器把 IR 操作对应到目标指令，输出机器级 DAG。第三步，寄存器分配：LLVM 默认使用贪心寄存器分配器，也支持基本寄存器分配器，底层思想正是我们前面讲的冲突图与着色，并处理溢出。第四步，指令调度：根据目标机的调度模型重排指令。最后，MC 层发射：把机器指令输出成汇编文本、目标文件甚至直接的内嵌机器码。每一步都是独立的 pass，用户可以像插件一样在任意环节插入自定义优化。

$$\displaystyle \text{IR} \xrightarrow{\text{SDAG}} \text{DAG} \xrightarrow{\text{Select}} \text{M-DAG} \xrightarrow{\text{Alloc}} \text{Seq} \xrightarrow{\text{Emit}} \text{ASM}$$

1. IR：LLVM 中间表示，后端的输入菜谱。

$$\text{IR}$$

2. SDAG：SelectionDAG 构建阶段，把 IR 转成适合做指令选择的图结构。

$$\xrightarrow{\text{SDAG}} \text{DAG}$$

3. Select：指令选择，DAG 上的模式匹配，把通用运算映射到目标指令。

$$\xrightarrow{\text{Select}} \text{M-DAG}$$

4. Alloc：寄存器分配，把虚拟寄存器占用的“伪灶台”落实到真实物理寄存器。

$$\xrightarrow{\text{Alloc}} \text{Seq}$$

5. Emit：MC 层发射，输出汇编或机器码，相当于把菜装盘端出。

$$\xrightarrow{\text{Emit}} \text{ASM}$$

LLVM 的巧妙之处在于“接口标准化，细节可插拔”。就像中央厨房的统一流水线：你只需要写一份炊具说明书，选锅、分灶、排顺序、装盘全都自动完成。理解了前面六节讲的基本原理，你就已经掌握了读懂 LLVM 后端源码的完整地图——从 IR 入口到汇编出口，每一步都逃不出“指令选择、寄存器分配、指令调度、窥孔优化”这几位老伙计的手掌心。

AI 应用场景

Python 演示

"""迷你目标代码生成器把三地址码(IR 形态)翻译成假想 RISC 汇编，演示编译后端三个核心环节：指令选择、寄存器分配、窥孔优化。""" import re IR = [    "t1 = a + b",    "t2 = t1 * 2",    "t3 = t1 - t2",    "t4 = t2 + c",    "t5 = t4 - 0",]  class MiniBackend:    """从 IR 到目标汇编的迷你后端"""     def __init__(self, nregs=2):        self.nregs = nregs  # 可用物理寄存器个数     def select(self, ir):        """指令选择: 每个 IR 操作匹配一条目标指令模板"""        ops = {"+": "ADD", "-": "SUB"}        out = []        for line in ir:            lhs, rhs = line.split("=")            lhs = lhs.strip()            parts = rhs.strip().split()            if len(parts) == 3 and parts[1] == "*":                # 乘 2 的强度削减模板: 左移 1 位                out.append(("SHL", lhs, parts[0], "1"))            elif len(parts) == 3:                out.append((ops[parts[1]], lhs, parts[0], parts[2]))        return out     def allocate(self, insts):        """寄存器分配: 高频临时变量占物理寄存器, 其余溢出到栈"""        freq = {}        for inst in insts:            for s in inst[1:]:                if s.isidentifier() and s.startswith("t"):                    freq[s] = freq.get(s, 0) + 1        hot = sorted(freq, key=lambda v: -freq[v])[: self.nregs]        reg = {v: "r%d" % i for i, v in enumerate(hot)}        mem = [v for v in freq if v not in reg]        lines = []        for inst in insts:            dst = reg.get(inst[1], "[sp-%d]" % (mem.index(inst[1]) + 1))            args = [self._arg(s, reg, mem) for s in inst[2:]]            lines.append("%s %s, %s" % (inst[0], dst, ", ".join(args)))        return lines, reg, mem     @staticmethod    def _arg(s, reg, mem):        """把操作数翻译为寄存器 / 立即数 / 栈引用"""        if s in reg:            return reg[s]        if s.isdigit():            return s        if s in mem:            return "[sp-%d]" % (mem.index(s) + 1)        return s  # 全局变量, 直接作为符号地址     def peephole(self, lines):        """窥孔优化: 局部窗口模式替换"""        out = []        for line in lines:            m = re.match(r"SUB (\S+), (\S+), 0$", line)            if m:                line = "MOV %s, %s" % (m.group(1), m.group(2))            out.append(line)        return out  if __name__ == "__main__":    backend = MiniBackend(nregs=2)    insts = backend.select(IR)    print("== 指令选择(IR->目标指令) ==")    for i in insts:        print("  %s" % (i,))    asm, reg, mem = backend.allocate(insts)    print("== 寄存器分配 ==")    print("  寄存器:", reg)    print("  溢出:", mem)    for line in asm:        print("  %s" % line)    opt = backend.peephole(asm)    print("== 窥孔优化后 ==")    for line in opt:        print("  %s" % line)

1. ops = {"+": "ADD", "-": "SUB"}指令模板表：IR 里的加法、减法分别对应目标机哪条指令，是“选锅”的依据。
2. if len(parts) == 3 and parts[1] == "*":乘 2 的特殊模板，直接输出 SHL 左移指令，这是指令选择阶段的“强度削减”。
3. hot = sorted(freq, key=lambda v: -freq[v])[: self.nregs]按变量出现次数排序，最热的两个临时变量优先拿到物理寄存器。
4. dst = reg.get(inst[1], "[sp-%d]" % (mem.index(inst[1]) + 1))目标操作数：如果有寄存器就用寄存器，否则引用栈槽——这就是“溢出到内存”。
5. if s.isdigit(): return s立即数（数字常量）不需要寄存器，直接原样写进指令。
6. m = re.match(r"SUB (\S+), (\S+), 0$", line)窥孔优化规则：识别出“减 0”这种无效指令模式。
7. line = "MOV %s, %s" % (m.group(1), m.group(2))把“减 0”等价替换成更简单的 MOV 指令。
8. backend = MiniBackend(nregs=2)模拟一台只有 2 个物理寄存器的小 CPU，迫使高频变量之外的临时变量溢出到栈。

常见误区

面试题