本系列是编译原理 (哈工大陈鄞、郭勇)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。

流图

一个基本块中的代码要么全都执行，要么全都不执行。

指令 8 跳转到 指令 5，所以指令 5 和指令 9 都是首指令。同理指令 13 和指令 23 也是首指令。

常用的代码优化方法

复制传播本身不会优化代码，但是可以给删除无用代码带来机会。

基本块的优化

可以看到，基本块的 DAG 可以检测公共子表达式。除此之外，基本块的 DAG 还可以删除无用代码。

• 首先删除没有附加活跃变量的根节点，所以删除 G
• 一个节点对应多个定值变量时，只需保留其中一个，所以删除 M、J、I、H

数据流分析

到达定值分析

• d1、d2、d3 在到达 B2 入口处的某条路径上其对应的变量 i 没有被重新赋值，所以是到达 B2 的
• d4 在到达 B2 入口处的某条路径上其对应的变量 i 被 d7 重新赋值，所以 d4 不可到达 B2 的
• 其他语句同理

• fd(x)：定值 d 以后所有到达定值的集合

基本块 B 的入口到达定值等于其各个前驱基本块的出口到达定值的并集。

到达定值方程的计算

• 上角标表示迭代次数，从 1 开始
• 第 2 次迭代结果和第 3 次迭代结果相同，停止迭代

简单来说，ud 链就是通过变量的引用找到对变量的赋值的地方。

活跃变量分析

• x：基本块出口处的活跃变量的集合
• fB(x)：基本块入口处的活跃变量的集合
• defB：基本块中首次出现的以定值形式出现的变量的集合。defB 杀死了某些变量在基本块入口处成为活跃变量的可能性
• useB：基本块中首次出现的以引用形式出现的变量的集合

简单来说，du 链就是通过变量的赋值找到该变量被引用的地方。

可用表达式分析

上述例子中如果 t2 是公共子表达式，就要求 B2 中没有对 i 进行重新赋值，或者对 i 进行了重新赋值，但是也对 4 * i 做了计算。

• x：基本块 B 入口处可用表达式的集合
• fB(x)：基本块 B 出口处可用表达式的集合

支配结点和回边

比如，8 是 9、10 的直接支配节点。

OUT[B] = IN[B]+ B。

N 是全局节点。

每个节点的支配节点即 IN[B]。

自然循环及其识别

在这个例子中，循环既可以从 2 开始，也可以从 3 开始，循环的入口节点不唯一。

以回边 4-3 为例：首先将 3、4 放入自然循环汇总，然后看 4 的前驱节点 7，该节点符合不经过 3 而到达 4 的要求，所以把 7 放到自然循环中；接下来继续分析 7 的前驱结点，因此 5、6、10 也是自然循环中的节点，以此类推。

删除全局公共子表达式和删除复制语句

代码移动

代码移动就是将循环中的不变量的运算移动到循环之外，包括两部分工作：循环不变计算的检测和代码外提。

循环不变计算有三种情况：

• 常量
• 运算分量的所有定值点都在循环外
• 运算分量只有一个到达定值且循环内，而且其到达定值本身就是该循环的不变计算

在这个例子中，i = 2 并不是每次循环都会执行，所以移动到循环之外是不恰当的。

作用于归纳变量的强度削弱

归纳变量的删除