第5章 中间表示

为什么最终输出正确仍然不够

、、、、共同构成本页坐标。在树、图、线性ILOC、SSA和符号表之间建立显式映射，确保值、内存、控制流和名字空间不因表示切换而丢失。

编译器是一串互相依赖的转换。错误的扫描器可能恰好产生可解析token，错误的语法树可能在语义动作中被修补，错误的数据流事实可能只在冷路径触发，错误的指令调度也可能在当前处理器上没有暴露。因此必须逐层保存输入、输出和不变量，定位最早偏离，而不能把“样例跑通”当作完整证明。

可复查的编译工程台账

实验固定源程序、编译器提交、ILOC方言、目标机模型、优化级别与随机种子。前端保存token、推导、AST与类型环境；中端保存基本块、CFG、支配关系、数据流集合、SSA和每个pass的前后IR；后端保存模式覆盖、依赖DAG、寄存器映射、逐出代码和最终指令。每份产物都带生成命令、退出状态与摘要值。

样本分为四组。正常样本证明主路径；边界样本覆盖空输入、深嵌套、临界立即数、不可归约控制流、寄存器压力和长延迟；失败样本只破坏一个语法、类型、数据流或机器约束；优化样本则同时保存未优化与优化版本，并用解释器或差分执行核对可观察行为。

诊断必须包含阶段、源位置或IR位置、实际状态、期望状态、相关前驱和首要根因。某一阶段失败后，不得继续消费旧缓存伪造下游结果。修改算法后先清理生成目录，再重建全部受影响事实；若一个pass令支配、活跃或别名信息失效，就必须显式重算或证明仍然有效。

性能结论与正确性结论分开记录。正确性要求语义等价和机器约束成立；性能要求给出静态成本、动态计数、代码大小、编译时间与硬件环境。一次偶然加速不能证明算法更优，一次慢化也不必然否定变换，关键是解释成本模型与实际瓶颈为何一致或偏离。

正式目录项映射到可追溯矩阵：每项至少关联一个输入、一个算法前提、一份结构化产物、一个失败对照和一个回归断言。跨章接口同时记录生产者与消费者，因而能发现“提到概念却没有验证”的空洞覆盖，也能在实现变化后只重放受影响的实验。

六阶段证据链

1. 选择IR层级

围绕图IR预测输入和结构化结果，执行后比较第一条差分。进入“线性化表达式”前，确认语义、算法前提与成本记录均完整。

2. 线性化表达式

围绕三地址代码预测输入和结构化结果，执行后比较第一条差分。进入“划分基本块”前，确认语义、算法前提与成本记录均完整。

3. 划分基本块

围绕控制流图预测输入和结构化结果，执行后比较第一条差分。进入“建立CFG”前，确认语义、算法前提与成本记录均完整。

4. 建立CFG

围绕SSA预测输入和结构化结果，执行后比较第一条差分。进入“命名SSA值”前，确认语义、算法前提与成本记录均完整。

5. 命名SSA值

围绕符号表预测输入和结构化结果，执行后比较第一条差分。进入“验证内存模型”前，确认语义、算法前提与成本记录均完整。

6. 验证内存模型

围绕图IR预测输入和结构化结果，执行后比较第一条差分。进入“选择IR层级”前，确认语义、算法前提与成本记录均完整。

可运行骨架

mult r2, r3 => r4
add r1, r4 => r5
storeAI r5 => rarp, 0

B0: compare -> B1, B2
B1: x1 = 1 -> B3
B2: x2 = 2 -> B3
B3: x3 = phi(x1, x2)

leaders = {entry, branch targets, instruction after branch}
blocks = partition(code, leaders)

正式目录逐项讲解

第二部分 从源码映射到IR

“第二部分 从源码映射到IR”不能只作为名词记忆。本节先在“选择IR层级”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“线性化表达式”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

第5章 中间表示

“第5章 中间表示”不能只作为名词记忆。本节先在“线性化表达式”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“划分基本块”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.1 简介

“5.1 简介”不能只作为名词记忆。本节先在“划分基本块”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“建立CFG”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.1.1 中间表示的分类

“5.1.1 中间表示的分类”不能只作为名词记忆。本节先在“建立CFG”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“命名SSA值”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.2 图IR

“5.2 图IR”不能只作为名词记忆。本节先在“命名SSA值”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“验证内存模型”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.2.1 与语法相关的树

“5.2.1 与语法相关的树”不能只作为名词记忆。本节先在“验证内存模型”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“选择IR层级”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.2.2 图

“5.2.2 图”不能只作为名词记忆。本节先在“选择IR层级”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“线性化表达式”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.3 线性IR

“5.3 线性IR”不能只作为名词记忆。本节先在“线性化表达式”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“划分基本块”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.3.1 堆栈机代码

“5.3.1 堆栈机代码”不能只作为名词记忆。本节先在“划分基本块”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“建立CFG”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.3.2 三地址代码

“5.3.2 三地址代码”不能只作为名词记忆。本节先在“建立CFG”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“命名SSA值”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.3.3 线性代码的表示

“5.3.3 线性代码的表示”不能只作为名词记忆。本节先在“命名SSA值”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“验证内存模型”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.3.4 根据线性代码建立控制流图

“5.3.4 根据线性代码建立控制流图”不能只作为名词记忆。本节先在“验证内存模型”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“选择IR层级”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.4 将值映射到名字

“5.4 将值映射到名字”不能只作为名词记忆。本节先在“选择IR层级”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“线性化表达式”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.4.1 临时值的命名

“5.4.1 临时值的命名”不能只作为名词记忆。本节先在“线性化表达式”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“划分基本块”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.4.2 静态单赋值形式

“5.4.2 静态单赋值形式”不能只作为名词记忆。本节先在“划分基本块”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“建立CFG”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.4.3 内存模型

“5.4.3 内存模型”不能只作为名词记忆。本节先在“建立CFG”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“命名SSA值”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.5 符号表

“5.5 符号表”不能只作为名词记忆。本节先在“命名SSA值”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“验证内存模型”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.5.1 散列表

“5.5.1 散列表”不能只作为名词记忆。本节先在“验证内存模型”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“选择IR层级”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.5.2 建立符号表

“5.5.2 建立符号表”不能只作为名词记忆。本节先在“选择IR层级”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“线性化表达式”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.5.3 处理嵌套的作用域

“5.5.3 处理嵌套的作用域”不能只作为名词记忆。本节先在“线性化表达式”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“划分基本块”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.5.4 符号表的许多用途

“5.5.4 符号表的许多用途”不能只作为名词记忆。本节先在“划分基本块”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“建立CFG”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.5.5 符号表技术的其他用途

“5.5.5 符号表技术的其他用途”不能只作为名词记忆。本节先在“建立CFG”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“命名SSA值”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

5.6 小结和展望

“5.6 小结和展望”不能只作为名词记忆。本节先在“命名SSA值”阶段固定输入、数据结构、前置事实与成本模型，再预测进入“验证内存模型”前应出现的IR、集合、图、表项、目标指令或运行时状态。实现时只改变一个条件，记录第一条结构或行为差分，避免最终程序碰巧正确掩盖中间错误。

验收时同时问四个问题：转换是否保持可观察语义，算法前提是否真的成立，时间与空间代价是否符合输入规模，以及失败是否停在最早可诊断边界。把答案连同原始产物、工具版本和最小反例写入台账，修复后清理旧输出并从源程序重建，才能证明本目录项被实际掌握。

分步视觉验证

先预测当前阶段的图、表、集合或指令，再运行变换；若不同，停在第一处分叉并保留原始证据。

常见误区

四类样本与通过条件

练习

小结

• 图IR：连接“选择IR层级”的算法前提、结构化产物、成本与回归证据。
• 三地址代码：连接“线性化表达式”的算法前提、结构化产物、成本与回归证据。
• 控制流图：连接“划分基本块”的算法前提、结构化产物、成本与回归证据。
• SSA：连接“建立CFG”的算法前提、结构化产物、成本与回归证据。
• 符号表：连接“命名SSA值”的算法前提、结构化产物、成本与回归证据。
• 本页23个目录层级均已进入可追溯的编译工程证据链。

术语表