文档介绍：代码优化
11/11/2017
1
《编译原理与技术》之代码优化
代码优化的目标
提高最终目标代码的运行效率(性能)
- 时间:运行的更快
- 空间:降低内存需求
保持源程序的语义
11/11/2017
2
《编译原理与技术》之代码优化
代码优化(续)
- 全局数据流分析技术
11/11/2017
3
《编译原理与技术》之代码优化
全局数据流分析
基本块
IN[B]
OUT[B]
KILL[B]
GEN[B]
到达基本块入口处的相关数据流信息
到达基本块出口处的相关数据流信息
基本块“产生”的相关数据流信息
基本块“注销”的相关数据流信息
11/11/2017
4
《编译原理与技术》之代码优化
全局数据流分析
数据流的“方向”
- 正向(向前)数据流:与控制流方向一致
- OUT[B]由IN[B]来计算
- IN[B]则由B的所有前驱结
点的OUT来决定
控制流
数据流
前驱1
前驱2
基本块B
表示数据流信息交汇(合流)处
11/11/2017
5
《编译原理与技术》之代码优化
全局数据流分析
数据流的“方向”
- 反向(向后)数据流:与控制流方向相逆
- IN[B]由OUT[B] 来计算
- OUT [B]则由B的所有后继结
点的IN来决定
控制流
数据流
基本块B
后继1
后继2
表示数据流信息交汇(合流)处
11/11/2017
6
《编译原理与技术》之代码优化
全局数据流分析
向前流
向后流
任意
路径
OUT[B] = GEN[B] ∪(IN[B]-KILL[B])
IN[B] = ∪OUT[P] , P∈Pred(B)
IN[B] = GEN[B] ∪(OUT[B]-KILL[B])
OUT[B] = ∪IN[S] , S∈(B)
全路径
OUT[B] = GEN[B] ∪(IN[B]-KILL[B])
IN[B] = ∩OUT[P] , P∈Pred(B)
IN[B] = GEN[B] ∪(OUT[B]-KILL[B])
OUT[B] = ∩IN[S] , S∈(B)
表1. 数据流分析方程
11/11/2017
7
《编译原理与技术》之代码优化
全局数据流方程求解
迭代计算:直至某先后两次迭代计算结果一样
迭代次序
- 向前流:流图深度优先次序
- 向后流:流图深度优先次序的逆序
- 流图深度优先次序:
- 对流图进行深度优先遍历,得到流图深度
优先扩展树;对该树进行前序遍历时最后
访问结点的逆序
迭代初始计算(值)
11/11/2017
8
《编译原理与技术》之代码优化
1
2
3
4
5
6
7
8
9
10
. 一个流图
1
2
3
4
6
7
8
10
9
5
前序遍历:1->2->3->4->6->7->8->10->8->9->8->7->6->4->5->4->3->2->1
深度优先次序:1,2,3,4,5,6,7,8,9,10
11/11/2017
9
《编译原理与技术》之代码优化
全局数据流方程求解
向前流
向后流
问题
初始值
问题
初始值
任意
路径
到达-定值/ud链
∅
活跃变量
∅
未初始化变量
所有变量
du链
∅
全路径
可用表达式
∅
非常忙表达式
∅
复写传播
∅
表2. 常用的数据流分析
11/11/2017
10
《编译原理与技术》之代码优化