Software Systems Atlas

中文

English

中文

English

主题

7.3 IR、控制流图与 SSA：为分析暴露数据依赖 ​

源语言的语法树太贴近写法，不利于追踪值和控制流，高塔需要一层更稳定的中间表示。

AST 适合表达源语言结构，却不适合直接回答“这个值从哪里来”“这条指令位于哪条控制流路径”。中间表示通过降低语法糖、显式化控制流和规范化操作，让优化与代码生成面对更小、更稳定的语义集合。

本课目标 ​

  • 区分树形 AST、线性三地址码与控制流图；
  • 构造基本块和 CFG；
  • 理解 SSA 定义唯一性、支配与 φ 节点；
  • 说明为什么编译器通常使用多层 IR。

1. 降低不是简单“铺平” ​

表达式：

text
(a + b) * c

三地址形式：

text
t1 = add a, b
t2 = mul t1, c

但语句、短路逻辑、异常和循环需要控制流。IR 通常组织为函数、基本块和指令：

text
entry:
    br cond, then, else
then:
    x1 = const 1
    jump merge
else:
    x2 = const 2
    jump merge
merge:
    ...

基本块只有一个入口，内部除末尾 terminator 外不发生跳转；CFG 的节点是基本块，边是可能的控制转移。

2. 找基本块边界 ​

在线性 TAC 中，leader 通常包括：

  • 函数第一条指令；
  • 跳转目标；
  • 条件或无条件跳转后的下一条指令。

每个 leader 到下一个 leader 前形成基本块。再根据末尾 terminator 建边：条件分支两条，无条件跳转一条，return 无后继。

隐式异常边、finally、协程挂起和不可恢复 trap 会让 CFG 更复杂。IR 必须明确哪些操作可能转移控制，否则数据流分析会把不可同时发生的路径混在一起。

3. SSA 的核心是每个定义一个名字 ​

非 SSA：

text
x = 0
x = x + 1

SSA 重命名：

text
x0 = 0
x1 = add x0, 1

每个 SSA value 只有一个定义点，使用直接指向该定义。它简化 def-use 链、常量传播和死值判断，但内存位置不会自动变成单赋值；别名分析和 memory SSA 等技术处理 load/store 依赖。

4. φ 节点按前驱边选择值 ​

控制流汇合：

text
then:
    x1 = 1
    jump merge
else:
    x2 = 2
    jump merge
merge:
    x3 = phi [x1, then], [x2, else]

φ 的语义是：控制从哪个前驱边进入，就取该边关联的值。它不是普通运行时函数调用，也不能把所有参数先计算后再选择。

降低出 SSA 时，φ 通常转为前驱边上的并行复制。若边上无法直接插入指令，需要拆分 critical edge；并行复制还要处理交换值产生的循环，可能需要临时位置。

5. 支配关系决定 φ 放置 ​

若从函数入口到块 $B$ 的每条路径都经过块 $A$，则 $A$ 支配 $B$。定义要安全到达使用点，定义块通常必须支配使用块；φ 的输入按前驱边使用，规则略有特殊。

构造 SSA 的经典流程：

  1. 计算 CFG 与支配树；
  2. 根据 dominance frontier 为多定义变量放置 φ；
  3. 沿支配树重命名变量；
  4. 建立 def-use 链并验证 SSA 不变量。

实践中也有 sealed-block 等增量构造方法。无论算法如何，必须在每次 CFG 改写后维护或重算相关分析。

6. IR 需要显式类型和效果 ​

一条 add 指令至少要明确：

  • 整数还是浮点；
  • 位宽与溢出语义；
  • 是否可产生 trap；
  • 是否允许重排；
  • 操作数与结果类型。

函数调用、原子操作、volatile、内存读写和异常具有副作用。死代码消除不能仅凭“结果没人用”删除有可观察效果的指令。

7. 多层 IR 服务不同问题 ​

常见层次：

text
AST / typed tree
  ↓ 去语法糖、名称已绑定
High-level IR
  ↓ 显式控制流与操作
SSA / optimizer IR
  ↓ 类型与操作合法化
Machine IR
  ↓ 物理寄存器与指令编码
Machine code

层数并无固定答案。高层 IR 保留数组、闭包或异步语义，便于领域优化；低层 IR 暴露地址、调用约定和目标指令约束。过早降低会丢失信息，过晚降低又让每个后端重复处理高层特性。

8. IR 验证器是必要门禁 ​

每个 pass 后可验证：

  • 每块恰有合法 terminator；
  • CFG 前驱与后继对称；
  • 每个 value 定义后再使用；
  • SSA 定义支配使用；
  • φ 输入与前驱一一对应；
  • 指令操作数类型匹配；
  • block/value ID 引用有效。

验证器越靠近引入错误的 pass，定位越容易。只在最终生成汇编时报“内部错误”，已经丢失了最关键的现场。

常见误区 ​

  • TAC 是一条没有结构的线性列表：跨分支分析必须恢复基本块与 CFG。
  • SSA 让所有存储都单赋值：普通内存仍可多次写，需要别名与内存依赖模型。
  • φ 是 CPU 执行的条件选择指令：它按 CFG 前驱表达值合并，后续会被消除或映射。
  • 一个通用 IR 适合所有阶段：不同抽象层需要保留不同信息和不变量。

练习 ​

  1. 把一个 if/else TAC 划分为基本块并画 CFG。
  2. 为循环变量构造 SSA，指出循环头 φ 的两个输入。
  3. 解释为什么删除结果未使用的函数调用可能改变程序。
  4. 为你设计的 IR 写五条 verifier 不变量。

小结 ​

IR 把源语言结构降低为显式操作和控制流，CFG 提供路径骨架，SSA 给每个计算结果唯一身份。它们让分析更直接，却不消除内存、副作用和异常的复杂性。

最后一章将在这些不变量上做优化，再把虚拟操作映射到具体目标机器，同时保证所有可观察行为符合源语言规则。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang