课题11：控制流图（CFG）生成器
难度：中 | 类型：项目实战 | 源文件：
scratchv/ir/cfg.py| 行数：~450 状态：✅ 已完成
概述
从IR中构建控制流图，实现不可达基本块消除和循环检测，输出可视化图。
理解背景
是什么？
控制流图（Control Flow Graph, CFG）生成器把一段线性排列的 IR 指令，转成一张有向图——每个节点是一个"基本块"（一段连续执行的指令），每条边是一次跳转。
原始 IR（线性） 控制流图（图结构）
entry: ┌───────┐
br x > 0 → then, else │ entry │
then: ───────→│ br x>0│───────
y = 1 │ └───────┘ │
br → end ↓ ↓
else: ┌──────┐ ┌──────┐
y = -1 │ then │ │ else │
br → end │ y=1 │ │ y=-1 │
end: └──┬───┘ └──┬───┘
return y │ ┌──────┐ │
└──────→│ end │←──────┘
│ret y │
└──────┘
CFG 是编译器分析和优化的基础设施——几乎所有"跨基本块"的优化（循环检测、死代码消除、寄存器分配）都依赖它。
为什么？
没有 CFG 时，你只能看到指令的先后顺序；有了 CFG，你能看到：
- 程序结构：哪些是分支，哪些是循环，一目了然
- 不可达代码：从入口走不到的块可以直接删除
- 循环检测：通过回边（back edge）自动识别循环体
- 可视化：导出为 Graphviz DOT 格式，生成图片
核心概念
1. 基本块（Basic Block）
一个基本块是一段只能从第一条进入、从最后一条退出的指令序列。块内没有分支，没有跳转目标。
# 这是一个基本块
t0 = add a, b
t1 = mul t0, c
t2 = sub t1, d
# 这里出现了分支，开始新的基本块
br t2 > 0 → .L_true, .L_false
2. 边类型（EdgeType）
| 类型 | 含义 | 例子 |
|---|---|---|
| FALLTHROUGH | 顺序执行到下个块 | 上一个块没有跳转，自然进入 |
| BRANCH | 条件分支 | beq a0, a1, .L1 |
| JUMP | 无条件跳转 | j .L_end |
| CALL | 函数调用（预留） | — |
3. 控制流分析三件套
CFG Builder 不仅能构建图，还提供： - 不可达代码消除：从入口 DFS，删除走不到的块 - 支配树：块 A 支配块 B = 从入口到 B 的每条路径都经过 A - 自然循环检测：通过回边（目标支配源的边）识别循环
详细任务
- 解析IR，划分基本块（以标签、跳转、返回为边界）。
- 构建有向图：节点为基本块，边为跳转关系（条件/无条件）。
- 实现不可达块消除：从入口块DFS标记可达块，删除不可达块并更新IR。
- 实现循环检测：基于支配树寻找返回边，识别自然循环。
- 使用
graphviz输出CFG为dot格式，并渲染为PNG/PDF。
- 集成到优化管道，添加
--cfg选项输出CFG。
交付产物
cfg_builder.py模块- 可视化脚本
- 测试用例及生成的CFG图片
- 文档：使用方法、算法说明
代码走读
CFG 数据结构
@dataclass
class CFGNode:
name: str # 块名（标签）
instructions: int # 块内指令数
is_entry: bool # 是入口块？
is_exit: bool # 是出口块？
terminator_opcode: str # 结束指令（br/jump/ret）
@dataclass
class CFG:
name: str # 函数名
nodes: list[CFGNode] # 节点列表
edges: list[CFGEdge] # 边列表
entry: str # 入口块名
构建算法
1. 扫描所有 IR 指令，识别"块边界"
块边界 = 标签(label) 或 分支/跳转之后的下一条
2. 将指令分配到各个基本块
3. 根据每个块的结束指令类型添加边：
- ret → 出口（无出边）
- br → 两条出边（true/false 目标）
- j → 一条出边
- 无终止指令 → FALLTHROUGH 到下个块
动手练习
练习 1: 手动画一个 CFG
graphviz输出CFG为dot格式，并渲染为PNG/PDF。--cfg选项输出CFG。cfg_builder.py模块- 可视化脚本
- 测试用例及生成的CFG图片
- 文档：使用方法、算法说明
代码走读
CFG 数据结构
@dataclass
class CFGNode:
name: str # 块名（标签）
instructions: int # 块内指令数
is_entry: bool # 是入口块？
is_exit: bool # 是出口块？
terminator_opcode: str # 结束指令（br/jump/ret）
@dataclass
class CFG:
name: str # 函数名
nodes: list[CFGNode] # 节点列表
edges: list[CFGEdge] # 边列表
entry: str # 入口块名
构建算法
1. 扫描所有 IR 指令，识别"块边界"
块边界 = 标签(label) 或 分支/跳转之后的下一条
2. 将指令分配到各个基本块
3. 根据每个块的结束指令类型添加边：
- ret → 出口（无出边）
- br → 两条出边（true/false 目标）
- j → 一条出边
- 无终止指令 → FALLTHROUGH 到下个块
动手练习
练习 1: 手动画一个 CFG
@dataclass
class CFGNode:
name: str # 块名（标签）
instructions: int # 块内指令数
is_entry: bool # 是入口块？
is_exit: bool # 是出口块？
terminator_opcode: str # 结束指令（br/jump/ret）
@dataclass
class CFG:
name: str # 函数名
nodes: list[CFGNode] # 节点列表
edges: list[CFGEdge] # 边列表
entry: str # 入口块名
构建算法
1. 扫描所有 IR 指令，识别"块边界"
块边界 = 标签(label) 或 分支/跳转之后的下一条
2. 将指令分配到各个基本块
3. 根据每个块的结束指令类型添加边：
- ret → 出口（无出边）
- br → 两条出边（true/false 目标）
- j → 一条出边
- 无终止指令 → FALLTHROUGH 到下个块
动手练习
练习 1: 手动画一个 CFG
1. 扫描所有 IR 指令，识别"块边界"
块边界 = 标签(label) 或 分支/跳转之后的下一条
2. 将指令分配到各个基本块
3. 根据每个块的结束指令类型添加边：
- ret → 出口（无出边）
- br → 两条出边（true/false 目标）
- j → 一条出边
- 无终止指令 → FALLTHROUGH 到下个块
练习 1: 手动画一个 CFG
写一个包含 if/else 的 DSL 程序，先用解析器生成 IR，再画出手工推导的 CFG，最后和 cfg.to_dot() 的输出对比。
练习 2: 可视化 CFG
用 Graphviz 把 CFG 渲染成图片：dot -Tpng cfg.dot -o cfg.png
练习 3: 检测不可达代码
写一个包含 return 后还有代码的 DSL 程序，看 CFG Builder 能否检测到不可达块。
常见坑
| 坑 | 说明 |
|---|---|
| FALLTHROUGH vs JUMP | 一个块以 j 结束时，不要自动加 FALLTHROUGH 边 |
| 空基本块 | 连续两个标签之间可能没有指令，产生空块（应合并或删除） |
| IR 格式依赖 | CFG Builder 依赖 IR 的标签和 BR/JUMP 格式，如果 IR 生成变化需要同步更新 |
| 循环检测的复杂性 | 嵌套循环、多个出口的循环需要正确的支配树计算 |
进阶阅读
- 龙书第 8.4 节：Basic Blocks and Flow Graphs
- 龙书第 9.6 节：Loop Detection and Natural Loops
- Graphviz DOT 语法：DOT Language
- 相关课题: 课题1 — DSL 前端增强器 | 课题21 — IR 验证器
12周每周目标
- W1：学习控制流图概念，阅读IR基本块划分方法。
- W2：实现基本块划分函数：输入IR指令列表，输出块列表（每个块有ID、指令列表、终止指令）。
- W3：构建CFG：遍历每个块，根据最后一条指令（
BR, JMP, RET）添加边。
- W4：输出CFG文本形式（节点列表，边列表），测试
if-else和while示例。
- W5：学习
graphviz的dot语言，生成简单图。
- W6：将CFG转换为
dot格式，节点显示块内前几条指令摘要，边标注跳转条件。
- W7：实现不可达块消除：从入口块BFS/DFS标记可达块，删除不可达块。
- W8：学习支配树概念，实现简单算法计算每个块的直接支配者。
- W9：基于支配树识别自然循环（寻找返回边，循环头是支配者），输出循环结构。
- W10：集成不可达消除到优化管道，添加
--eliminate-unreachable选项。
- W11：优化循环检测，识别嵌套循环，在CFG图中高亮不同深度循环。
- W12：撰写文档，包含算法流程图、使用示例、可视化样例。
- W1：学习控制流图概念，阅读IR基本块划分方法。
- W2：实现基本块划分函数：输入IR指令列表，输出块列表（每个块有ID、指令列表、终止指令）。
- W3：构建CFG：遍历每个块，根据最后一条指令（
BR,JMP,RET）添加边。 - W4：输出CFG文本形式（节点列表，边列表），测试
if-else和while示例。 - W5：学习
graphviz的dot语言，生成简单图。 - W6：将CFG转换为
dot格式，节点显示块内前几条指令摘要，边标注跳转条件。 - W7：实现不可达块消除：从入口块BFS/DFS标记可达块，删除不可达块。
- W8：学习支配树概念，实现简单算法计算每个块的直接支配者。
- W9：基于支配树识别自然循环（寻找返回边，循环头是支配者），输出循环结构。
- W10：集成不可达消除到优化管道，添加
--eliminate-unreachable选项。 - W11：优化循环检测，识别嵌套循环，在CFG图中高亮不同深度循环。
- W12：撰写文档，包含算法流程图、使用示例、可视化样例。