08 中间代码优化 | 《编译原理》笔记

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

流图

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

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

2023_11_04_ZI7DcAn

常用的代码优化方法

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

基本块的优化

可以看到,基本块的 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 也是自然循环中的节点,以此类推。

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

代码移动

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

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

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

2023_11_12_OMdjntg

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

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



归纳变量的删除

08 中间代码优化 | 《编译原理》笔记

http://www.zh0ngtian.tech/posts/df7b651.html

作者

zhongtian

发布于

2023-11-02

更新于

2023-12-16

许可协议

评论