第 09 篇用 alloca/load/store 把可变变量映射到 LLVM IR 的栈槽，if/else 和 while 通过 LLVM 的基本块和条件跳转来实现。程序跑起来了，但控制流完全藏在 LLVM 里——我们自己的编译器看到的仍然是一棵 HIR 树，无法对分支和循环做任何分析。第 11–12 篇要构造 SSA，前提是程序已经被拆成显式的基本块和跳转。本篇就来做这件事。

什么是基本块

基本块（basic block）是一段顺序执行的指令序列，满足两个约束：

  1. 控制流只能从第一条指令进入。不存在从外部跳到块中间的边。
  2. 控制流只能从最后一条指令离开。这条指令叫做终结指令（terminator），它要么跳转到另一个块，要么从函数返回。块内其余指令不改变控制流。

换句话说，基本块要么整体执行，要么整体不执行。这个性质让后续的数据流分析可以把整个块当作一个节点处理，而不必逐条指令跟踪控制流。

终结指令只有三种形式就够了：

  • 无条件跳转：执行完本块，跳到目标块继续。
  • 条件分支：根据一个布尔值，跳到两个目标块之一。
  • 返回：离开当前函数，把值交给调用者。

一个块如果没有终结指令，就不知道执行完之后去哪里。一个块如果在终结指令之后还有普通指令，那些指令永远不会被执行。两种情况都是 IR 构造错误。

控制流图

把函数里的所有基本块当作节点，把跳转关系当作有向边，就得到控制流图（Control Flow Graph, CFG）。每个函数恰好有一个入口块（entry block），没有前驱，对应函数参数的绑定位置。以 Return 结尾的块是出口块，一个函数可以有多个出口。

CFG 是编译器中间表示的骨架。支配关系、活跃变量、SSA 构造、不可达代码检测——全都建立在 CFG 上。没有 CFG，这些分析无从开始。

Block 与 Term 的 Rust 定义

以下是本系列编译器的自制 CFG 数据结构。每个函数被表示为一组 Block，每个 Block 以一个 Term 结尾：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/// 基本块的唯一标识。
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct BlockId(u32);

/// 基本块。
pub struct Block {
    pub id: BlockId,
    /// 块参数，等价于其他表示中的 phi 节点（后文解释）。
    pub params: Vec<(VarId, Ty)>,
    /// 顺序执行的普通指令。
    pub body: Vec<Inst>,
    /// 终结指令，决定离开本块后的去向。
    pub terminator: Term,
}

/// 终结指令。
pub enum Term {
    /// 无条件跳转到目标块，携带块参数。
    Jump(BlockId, Vec<Operand>),
    /// 条件分支。cond 为 true 跳 then_block，否则跳 else_block。
    Branch {
        cond: Operand,
        then_block: BlockId,
        else_block: BlockId,
    },
    /// 函数返回。
    Return(Operand),
}

Inst 是普通指令，包括算术、比较、函数调用等——它们不改变控制流。Operand 是指令的操作数，可以是常量、变量引用或临时值。这些类型在前几篇已经存在，这里不再重复。

关键设计决策：Block 的 terminator 字段不是 Option<Term>，而是必须存在的 Term。一个没有终结指令的块在类型层面就构造不出来。Rust 的类型系统替我们排除了一类错误。

从 HIR 降低到 CFG

HIR 是树形结构，CFG 是图。降低（lowering）过程把嵌套的 if/else 和 while 拆成扁平的块和跳转。

if/else → 菱形分支

源码：

1
2
3
4
5
6
if cond {
    a = 1;
} else {
    a = 2;
}
// use a

生成四个块：

1
2
3
4
5
6
7
8
9
10
11
12
bb0:                          // 计算 cond
    %c = ...
    Branch(%c, bb1, bb2)

bb1:                          // then
    Jump(bb3, 1)

bb2:                          // else
    Jump(bb3, 2)

bb3(a: i64):                  // merge，接收块参数
    // use a

bb1 和 bb2 分别带着不同的值跳到 bb3。bb3 声明了一个块参数 a，在运行时它会接收到来自实际执行路径的值。这就是用块参数替代 phi 节点的做法（下一节详述）。

while → 循环头与回边

源码：

1
2
3
while cond {
    body;
}

生成三个块：

1
2
3
4
5
6
7
8
9
10
bb_header:                    // 循环头，判断条件
    %c = ...
    Branch(%c, bb_body, bb_exit)

bb_body:                      // 循环体
    ...
    Jump(bb_header)           // 回边

bb_exit:                      // 循环出口
    ...

bb_body 末尾跳回 bb_header，这条边叫做回边（back edge），它在 CFG 里形成一个环。回边的存在是循环区别于分支的标志，也是后续数据流分析需要不动点迭代的原因——第 11 篇会详细讨论这一点。

块参数代替 phi 节点

传统 SSA 文献在合流点放置 phi 节点：a = phi [1, bb1], [2, bb2]。phi 的语义是"根据控制流来自哪条边，选择对应的值"。它有效，但构造时必须知道前驱块的顺序，容易出错。

本系列采用块参数（block parameter）。合流块声明参数列表，每个跳转到该块的终结指令在参数位置提供对应的值。效果与 phi 完全等价，但构造更直接：生成跳转时就把值带上，不需要事后回填。

MLIR 和 Cranelift 都使用块参数而非 phi。第 12 篇构造完整 SSA 时，块参数的优势会更明显。现在只需要记住：合流块的参数个数和类型必须与所有跳入它的 Jump/Branch 携带的参数匹配。

sum_to 的 CFG

第 09 篇的 sum_to 函数：

1
2
3
4
5
6
7
8
9
fn sum_to(n: i64) -> i64 {
    let mut sum: i64 = 0;
    let mut i: i64 = 1;
    while i <= n {
        sum = sum + i;
        i = i + 1;
    }
    return sum;
}

降低后的 CFG 文本转储（--emit=cfg 输出）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fn sum_to(n: i64) -> i64 {
  bb0:
    Jump(bb1, 0, 1)              // sum=0, i=1

  bb1(sum: i64, i: i64):         // 循环头
    %0 = le(i, n)
    Branch(%0, bb2, bb3)

  bb2:                           // 循环体
    %1 = add(sum, i)
    %2 = add(i, 1)
    Jump(bb1, %1, %2)            // 回边，更新 sum 和 i

  bb3:                           // 循环出口
    Return(sum)
}

对应的 CFG 图：

1
2
3
4
5
6
7
8
9
10
      bb0
       │
       ▼
┌──→ bb1(sum, i)
│      │
│    Branch
│    ╱    ╲
│  bb2    bb3
│   │     Return
└───┘

四个块，四条边（bb0→bb1, bb1→bb2, bb1→bb3, bb2→bb1）。bb2→bb1 是回边。bb1 有两个块参数 sum 和 i，分别从 bb0 的初始值和 bb2 的更新值中接收。

注意 bb3 里直接使用了 sum——因为 bb3 只能从 bb1 到达，而 bb1 的参数 sum 在 bb3 的作用域内仍然可见。严格来说，bb3 也可以声明自己的块参数来接收 sum，但这里没有合流，直接引用更简洁。第 12 篇统一处理 SSA 重命名时会回到这个问题。

CFG 验证器

IR 在内存里是一堆 Block 结构体，构造过程可能出错。CFG 验证器在每次降低或变换之后检查以下不变量：

  1. 每个块必须以终结指令结尾。 因为 terminator 是必选字段，这条在 Rust 层面已保证。但验证器仍检查 body 中没有混入终结指令。
  2. 终结指令之后不能有普通指令。 终结指令只能出现在 terminator 字段中，body 里的每条 Inst 都必须是非终结的。
  3. 分支和跳转的目标块必须存在。 Jump(bb5, ...) 中的 bb5 必须在当前函数的块集合中。
  4. 块参数个数匹配。 如果 bb1 声明了两个参数，那么所有跳到 bb1 的 Jump 和 Branch 都必须提供恰好两个实参。
  5. 块参数类型匹配。 提供给块参数的值的类型必须与声明类型一致。

验证器的输出是一组诊断，每条指明出错的块和指令位置。通过验证的 CFG 可以安全地交给后续的支配关系计算和 SSA 构造。

核心验证逻辑的结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
fn verify_function(func: &Function) -> Vec<CfgError> {
    let mut errors = Vec::new();
    let block_ids: HashSet<BlockId> =
        func.blocks.iter().map(|b| b.id).collect();

    for block in &func.blocks {
        // 检查 body 中是否混入了终结指令
        for (i, inst) in block.body.iter().enumerate() {
            if inst.is_terminator() {
                errors.push(CfgError::TermInBody(block.id, i));
            }
        }
        // 检查终结指令的目标块存在且参数匹配
        match &block.terminator {
            Term::Jump(target, args) => {
                check_target(&block_ids, func, block.id,
                             *target, args, &mut errors);
            }
            Term::Branch { then_block, else_block, .. } => {
                check_target(&block_ids, func, block.id,
                             *then_block, &[], &mut errors);
                check_target(&block_ids, func, block.id,
                             *else_block, &[], &mut errors);
            }
            Term::Return(_) => {}
        }
    }
    errors
}

check_target 查找目标块是否在 block_ids 中，再比较实参数量和类型与目标块的 params 声明。实际代码比这里更长，但检查逻辑就是这五条规则的直接翻译。

错误注入实验

构造一个故意出错的 CFG，观察验证器的反应。

实验一：移除终结指令。 把 bb2 的 terminator 替换成一个占位的 Jump 指向不存在的 bb99：

1
error: jump target bb99 does not exist (in bb2)

验证器在第三条规则处捕获。如果把 terminator 字段改成 Option<Term> 并设为 None，类型系统本身就会阻止编译——这正是我们把它设为必选字段的原因。

实验二：在 Return 之后追加指令。 假设某次变换不小心在 bb3 的 body 末尾插入了一条 add 指令，而 terminator 仍是 Return。body 中的 add 本身不违反第一条规则（它不是终结指令）。但如果有人错误地把一条 Jump 插进了 body：

1
error: terminator instruction found in body at position 0 (in bb3)

验证器在第二条规则处捕获。终结指令只允许出现在 terminator 字段中。

实验三：块参数个数不匹配。 把 bb0 的 Jump(bb1, 0, 1) 改成 Jump(bb1, 0)，少传一个参数：

1
error: bb0 jumps to bb1 with 1 arg(s), but bb1 expects 2 (in bb0)

验证器在第四条规则处捕获。这类错误在手动构造 IR 时很容易犯，验证器每次变换后都应运行。

从 HIR 树到 CFG 图：降低过程的结构

降低算法维护一个"当前块"。遍历 HIR 时，普通语句追加到当前块的 body；遇到 if/else 或 while 时，创建新块并切换。具体步骤：

  1. 为函数创建入口块 bb0，设为当前块。
  2. 遍历 HIR 语句。遇到赋值、表达式语句，生成 Inst 追加到当前块。
  3. 遇到 if cond { then } else { els }：
    • 在当前块生成 cond 的求值指令。
    • 创建 bb_then、bb_else、bb_merge。
    • 当前块的终结指令设为 Branch(cond, bb_then, bb_else)。
    • 递归降低 then 分支到 bb_then，末尾 Jump(bb_merge, ...)。
    • 递归降低 else 分支到 bb_else，末尾 Jump(bb_merge, ...)。
    • 将 bb_merge 设为新的当前块，继续。
  4. 遇到 while cond { body }：
    • 创建 bb_header、bb_body、bb_exit。
    • 当前块末尾 Jump(bb_header, ...)，携带循环变量初始值。
    • bb_header 中生成条件求值，终结指令 Branch(cond, bb_body, bb_exit)。
    • 递归降低 body 到 bb_body，末尾 Jump(bb_header, ...)，携带更新后的变量值。
    • 将 bb_exit 设为新的当前块，继续。
  5. 遇到 return expr：当前块终结指令设为 Return(val)。

这个过程是一次 HIR 遍历，时间复杂度与 HIR 节点数成正比。降低完成后立即运行验证器。

练习

  1. 为以下函数画出 CFG，标注每个块的终结指令，数清块数和边数：
1
2
3
4
5
6
7
8
9
10
11
12
fn classify(x: i64) -> i64 {
    let mut result: i64 = 0;
    while x > 0 {
        if x > 100 {
            result = result + 10;
        } else {
            result = result + 1;
        }
        x = x - 1;
    }
    return result;
}

提示：while 产生循环头、循环体入口和循环出口；if/else 在循环体内部再产生 then 块、else 块和 merge 块。总共需要多少个块？有几条回边？

  1. 在本篇的 sum_to CFG 中，把 bb1 的 Branch 改成 Jump(bb2)（去掉条件判断），预测这个 CFG 的行为。验证器会报错吗？为什么这种语义错误不在验证器的检查范围内？

资料

Engineering a Compiler, 3rd ed. 第 8 章系统讲述了基本块、CFG 和数据流分析框架。MLIR 的 Block 与 Region 设计采用块参数而非 phi 节点，本篇的设计借鉴了这一选择。Cranelift IR 参考同样使用块参数，其文档中解释了与 phi 的等价关系。

上一篇：09 - 条件、循环和可执行程序。下一篇：11 - 支配关系、活跃变量与数据流。