DAG构造与优化

DAG 节点类型

• 叶节点：标识符（变量名）或常量
• 内部节点：运算符，子节点为运算分量

四元式 $\to$ DAG 节点对应

按操作数类型分为三种：

类型	四元式形式	DAG 节点
0型	(=, A, _, B)	叶节点（标识符）
1型	(op, A, _, B)	一个子节点的内部节点
2型	(op, A, B, C)	两个子节点的内部节点

DAG 四步构造算法

重点 DAG 四步构造算法（每年易错）。

第一步：建叶节点

对每个四元式 (op, A, B, C)：

• 若操作数（A/B）无对应叶节点，建立叶节点
• 为结果创建对应的节点

第二步：合并常数

• 若运算分量都是常数，直接计算常数结果
• 用常数结果替换后续使用

第三步：捕捉公共子表达式

• 构造新节点前，检查是否已有相同运算的节点存在
• 若存在，直接使用已有节点，不创建新节点

第四步：删除无用赋值

• 对不活跃的赋值（后续不再使用），标记或删除对应节点

完整构造示例

对以下四元式序列构造 DAG：

(1) T0 = 3.14
(2) T1 = 2 * T0
(3) T2 = R + r
(4) A = T1 * T2
(5) B = A
(6) T3 = 2 * T0
(7) T4 = R + r
(8) T5 = T3 * T4
(9) T6 = R - r
(10) B = T5 * T6

逐步构造：

1. T0 = 3.14 → 建叶节点 3.14，标记 T0
2. T1 = 2 * T0 → 建叶节点 2，内部节点 *，标记 T1
3. T2 = R + r → 建叶节点 R、r，内部节点 +，标记 T2
4. A = T1 * T2 → 内部节点 *（左=T1，右=T2），标记 A
5. B = A → B 与 A 共享同一节点
6. T3 = 2 * T0 → 检查已存在 2 * T0（步骤 2），T3 与 T1 共享节点
7. T4 = R + r → 检查已存在 R + r（步骤 3），T4 与 T2 共享节点
8. T5 = T3 * T4 → 检查已存在 T1 * T2（步骤 4），T5 与 A 共享节点
9. T6 = R - r → 建内部节点 -，标记 T6
10. B = T5 * T6 → B 从共享 A 改为新节点 *（左=T5/A, 右=T6）

优化结果：原 10 个四元式经 DAG 优化后，消除重复计算（步骤 6-8 共享节点），最终重新生成代码可减少运算次数。

重点 DAG 构造的关键是捕捉公共子表达式（步骤 6-8）。

DAG 用途

1. 常量合并：编译时计算常量表达式
2. 公共子表达式提取：消除重复计算
3. 无用赋值删除：删除对后继无影响的赋值
4. 重写中间代码：根据 DAG 图重新生成优化后的四元式序列

重点 DAG 用途：常量合并、公共子表达式提取、无用赋值删除、重写中间代码。

DAG vs 控制流图

	DAG	控制流图
粒度	基本块内部	基本块之间
节点	表达式/运算	基本块
用途	局部优化	全局/循环优化

DAG 以基本块为单位构建，基于 基本块与控制流图 提供的块划分和流图结构进行局部优化。