第7章 代码优化 学习目标： 掌握：基本块的划分、基本块的DAG优化 理解：什么是局部优化、循环优化、全局优化 了解：循环优化技术.

Presentation on theme: "第7章 代码优化 学习目标： 掌握：基本块的划分、基本块的DAG优化 理解：什么是局部优化、循环优化、全局优化 了解：循环优化技术."— Presentation transcript:

1 第7章 代码优化 学习目标： 掌握：基本块的划分、基本块的DAG优化 理解：什么是局部优化、循环优化、全局优化 了解：循环优化技术

2 7.1 优化技术简介 什么是优化： 所谓优化是对代码进行等价变换，使得变换后的代码的效率更高（节省运行时间、存储空间或两者兼而有之）
7.1 优化技术简介 什么是优化： 所谓优化是对代码进行等价变换，使得变换后的代码的效率更高（节省运行时间、存储空间或两者兼而有之） 优化可在编译的不同阶段进行，最主要的优化有 中间代码优化（不依赖具体计算机） 目标代码优化（依赖于具体计算机）

3 中间代码优化 中间代码 源代码 编译前端 代码生成 目标代码 目标代码优化 编译的优化工作阶段

4 优化的分类： 根据优化涉及的程序范围，分为： 局部优化：在只有一个入口、一个出口的基 本块上进行优化 循环优化：对循环中的代码进行优化 全局优化：在整个程序范围内进行的优化

5 中间代码优化常用技术 1.  删除多余运算（删除公共子表达式） 如果子表达式E在前面计算过，且之后E中的变量值都未改变，那么E的重复出现称为公共子表达式，可避免重复计算 例 (1) T1 :=4*I (2) T2 :=addr(A)－4 (3) T3 :=T2[T1] T4 :=4*I (5) …… (1)和(4)中都有4*I的运算， (1)到(4)之间无对I的赋值，显然两次计算的值是相等的， (4)的运算是多余的 (4)变换成T4 :=T1

6 2. 合并已知量与复写传播 如果运算量都是已知量，则在编译时就算出它的值，称为合并已知量 若有A:=B，称为把B值复写到A。如果其后有引用A的地方，且其间A、B的值都未改变，则可把对A的引用改为对B引用，称为复写传播。 例： （1）I:=1 （2）T1:=4*I （3）T4:=T1 （4）T6:=T5[T4] I是已知量 （2）T1:= 合并已知量 把T1的值复写到T4 （4）T6:=T5[T1] 复写传播

7 3. 删除无用赋值 有些变量的赋值从未被引用，称为无用赋值，应删除。 无用赋值分三种情况： 变量被赋值，但在程序中从未被引用（在局部范围内难判定）  变量赋值后未被引用又重新赋值，则前面赋值是无用的  变量的赋值只被计算变量自己引用，其他变量都不引用它

8 例 （1） I:=1 （2）T1:=4 （3）T3:=T2[T1] （4）T4:=T1 （5）I:=I+1 （6）T1:=T1+4 （7）if T1≤80 goto (3) （2）T1:=4 （3）T3:=T2 [T1] （6）T1:=T1+4 （7）if T1≤80 goto (3) (4)中对T4赋值，但T4未被引用； (1)和(5)对I赋值，但只有(5)中计算I时引用I 如果程序其他地方不需要引用T4和I，则(4)、(1)和(5)是无用赋值，可删除。

9 4. 其他优化技术 以下优化技术将在循环优化中介绍： 代码外提 强度削弱 变换循环控制条件（删除归纳变量）

10 7.2 局部优化 局部优化是指基本块内的优化 基本块是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从入口语句进入，从其出口语句退出

11 7.2.1 基本块的划分 把程序（中间代码形成）划分成基本块的算法： 1. 求基本块的入口语句，它们是： 程序的第一个语句；或者
基本块的划分 把程序（中间代码形成）划分成基本块的算法： 1.  求基本块的入口语句，它们是： 程序的第一个语句；或者 条件转移或无条件转移语句的转移目标语句；或者 紧跟在条件转移语句后面的语句。

12 2．对每一入口语句，构造其所属的基本块: 它是由该入口语句到下一入口语句(不包括下一入口语句); 或到一转移语句(包括该转移语句); 或到一停止语句(包括该停止语句) 之间的语句序列组成的。 3．凡未被纳入某一基本块的语句，是不会被执行到的语句，可以把它们删除。

13 例： read X read Y R:=X mod Y if R=0 goto (8) X:=Y Y:=R goto (3) write Y halt (1)、(3)、(5)和(8)是入口语句，分别构成基本块 B1 { (1)、(2) } B2 { (3)、(4) } B3 { (5)、(6)、(7) } B4 { (8)、(9) } read X R:=X mod Y X:=Y write Y

14 7.2.2 基本块的DAG表示 DAG(Directed Acyclic Graph)是无环路有向图的简称
叶结点(无后继的结点)以一标识符或常数作标记，表示该结点代表该变量或常数的值 内部结点(有后继的结点)以一运算符作标记，表示该结点代表用该算符对其后继结点所代表的值进行运算的结果 各结点都可以附加上一个或多个标识符，表示这些变量具有该结点所代表的值

15 * n5 n7 n2 n3 n4 n1 n6 n8 基本块的DAG的例子 T0:=3.14 T1:=2*T0 T2:=R+r
－ + r T6 A, B,T5 * T1,T3 T0 R 6.28 3.14 T2,T4 n5 n7 n2 n3 n4 n1 B n6 n8 基本块的DAG的例子 T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R－r B:=T5*T6 ni是结点编号 结点下面的符号（运算符、标识符或常量）是各结点的标记 结点右边的标识符是结点的附加标识符

16 2. 四元式及其相应的DAG结点形式 0型： A:=B (:=, B, －,A) B n1 A n2 n1 op B A 1型： 2型：
A:=op B (op , B, －,A) 2型： A:=B op C (op , B , C , A) n3 n1 n2 B C op A

17 3 构造基本块的DAG的算法 算法准备： 假定DAG各结点信息将用适当的数据结构来存放，并设有一个标识符（包括常数）与结点的对应表。NODE(A)是描述这种对应关系的函数，它的值或为n（表示结点n上有A作为标记或附加标识符），或无定义。 算法： 首先DAG为空，对基本块的每一四元式，按其类型分别处理：

18 对0型（A:= B） Y N NODE(B)有定义 构造叶结点B 令该结点为n NODE(A)有定义 从NODE(A)的附加标识符中删去A
在结点n上附加A 下一四元式 n B A

19 对1型（A:= op B） n A p n A op B NODE(B)有定义 构造叶结点B 执行op B 得P NODE(B)标记常数
Y N NODE(B)有定义 构造叶结点B NODE(B)标记常数 执行op B 得P 有标记为op后继为NODE(B)的结点 NODE(B) 为新结点 删除NODE(B)结点 NODE(P)有定义 构造叶结点P 构造该结点 从NODE(A)的附加标识符中删去A 令该结点为n NODE(A)有定义 在结点n上附加A 下一四元式 n p A n B op A

20 对于2型（A:= B op C） n A p n B C op A Y N 删除NODE(C)结点 构造叶结点P 下一四元式
NODE(P)有定义 构造叶结点P 下一四元式 执行B op C得P NODE(B)是新结点 删除NODE(B)结点 NODE(B),NODE(C)均标记常数 NODE(B)有定义 构造叶结点B 构造叶结点C NODE(C)有定义 有标记为op后继为NODE(B)、NODE(C)的结点 构造该结点 令该结点为n NODE(A)有定义 从NODE(A)的附加标识符中删去A 在结点n上附加A n A p n B C op A

21 * * 例：构造以下基本块的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 * n8 B * n6 A ,B ,T5 + n5 － n7 T2 ,T4 T6 3.14 n1 6.28 n2 R n3 r n4 T0 T1 ,T3 2 2

22 7.2.3 DAG的应用 在一个基本块被构造成相应的DAG的过程中，进行了如下基本的优化工作： 合并已知量

23 删除多余运算 对具有公共子表达式的所有四元式，只生成一个计算该表达式的内部结点，所有被赋值的变量都作为该结点的附加标识符，实现了删除多余运算的优化 删除无用赋值 如果变量被赋值后，在它被引用前又被重新赋值，则变量被从具有前一个值的结点上删除

24 由DAG重新生成原基本块的一个优化的代码序列：
－ + r T6 A, T5 * T1,T3 T0 R 6.28 3.14 T2,T4 n5 n7 n2 n3 n4 n1 B n6 n8 (1) T0 :=3.14 (2) T1 :=6.28 (3) T3 :=6.28 (4) T2 :=R+r (5) T4 :=T2 (6) A :=6.28*T2 (7) T5 :=A (8) T6 :=R－r (9) B :=A*T6 由DAG重新生成原基本块的一个优化的代码序列：

25 原基本块的四元式序列G (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 按DAG重新写成的四元式序列G’ (1) T0 :=3.14 (2) T1 :=6.28 (3) T3 :=6.28 (4) T2 :=R+r (5) T4 :=T2 (6) A :=6.28*T2 (7) T5 :=A (8) T6 :=R－r (9) B :=A*T6 G中(2)(6)的已知量已合并 G中(5)的无用赋值已删除 G中(3)(7)的公共子表达式R+r 只计算一次，删除了多余运算

26 假如T0，T1，…，T6在基本块后都不被引用，则这些符号可在DAG附加标识符中删去，重写四元式得到进一步的优化：
删除在基本块后不被引用变量的赋值 r R 6.28 3.14 － + T6 A, T5 * T1,T3 T0 T2,T4 n5 n7 n2 n3 n4 n1 B n6 n8 假如T0，T1，…，T6在基本块后都不被引用，则这些符号可在DAG附加标识符中删去，重写四元式得到进一步的优化： （1） S1:=R+r （2） A:=6.28*S1 （3） S2:=R－r （4） B:=A*S2 其中S1和S2是临时变量。 T0，T1，…，T6被赋值的代码被优化掉

27 7.3 循环优化简介 循环就是程序中那些可能反复执行的代码序列。
7.3 循环优化简介 循环就是程序中那些可能反复执行的代码序列。 因为循环中的代码要反复执行，所以循环的代码优化对提高目标代码的效率将起更大的作用。

28 7.3.1 程序流图 把控制流的信息加到基本块集合上构成的有向图称为表示程序的流图，简称流图。 流图的构造方法：
程序流图 把控制流的信息加到基本块集合上构成的有向图称为表示程序的流图，简称流图。 流图的构造方法： 点集：以基本块为结点，含程序第一条语句的结点为首结点。 边集：从基本块Bi向基本块Bj引有向边，仅当 Bj在程序中的位置紧跟在Bi之后, 且Bi的出口语句不是无条件转移语句或停止语句。或者 Bi的出口是转移语句 (goto (s)或if…goto (s))，并且转移目标(s)是Bj的入口语句。

29 例：构造以下程序的流图 (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt

30 7.3.2 循环优化 1. 代码外提 把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面，使之只在循环外计算一次，这种优化称为代码外提。 循环不变运算：运算量为常量或在循环外定值，每次循环时其值不变的运算。

31 (1) P:=0 (2) I:=1 (4) T2:=addr(A) －4 (7) T5:=addr(B) －4 (3) T1:=4*I (5) T3:=T2[T1] (6) T4:=T1 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (12) If I≤20 goto (3) 代码外提后 B1 B2 (1) P:=0 (2) I:=1 (3) T1:=4*I (4) T2:=addr(A)－4 (5) T3:=T2[T1] (6) T4:=T1 (7) T5:=addr(B) －4 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (12) if I≤20 goto (3) 中间代码段 B1 B2 (4)中的运算量addr(A)是分配的数组A的首地址，是个常量，4也是常量，因而(4)是循环不变运算，同样(7)也是循环不变运算，(4)、(7) 都可提到循环前

32 2. 强度削弱 强度削弱是指把程序中强度大的运算替换成强度小的运算。例如把乘法运算换成加法运算等

33 (1) P:=0 (2) I:=1 (4) T2:=addr(A) －4 (7) T5:=addr(B) －4 (3) T1:=4*I (5) T3:=T2[T1] (6) T4:=T1 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (3’) T1:=T1+4 (12) if I≤20 goto (5) 强度削弱 (1) P:=0 (2) I:=1 (4) T2:=addr(A) －4 (7) T5:=addr(B) －4 (3) T1:=4*I (5) T3:=T2[T1] (6) T4:=T1 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (12) If I≤20 goto (3) 中间代码段

34 变换循环控制条件 I和T1始终保持T1:=4*I的线性关系 (1) P:=0
(4) T2:=addr(A) －4 (7) T5:=addr(B) －4 (3) T1:=4*I (5) T3:=T2[T1] (6) T4:=T1 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (3’) T1:=T1+4 (12) if I≤20 goto (5) I和T1始终保持T1:=4*I的线性关系 这样把(12)的循环控制条件 I≤20变换成T1≤80，程序的运行结果不变 这种变换称为变换循环控制条件 经过这一变换，循环中I的值不被引用，四元式(11)可被删去，这是变换的目的所在。

35 中间代码段 (1) P:=0 (2) I:=1 (4) T2:=addr(A) －4 (7) T5:=addr(B) －4 (3) T1:=4*I (5) T3:=T2[T1] (6) T4:=T1 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (3’) T1:=T1+4 (12) if I≤20 goto (5) (1) P:=0 (2) I:=1 (4) T2:=addr(A) －4 (7) T5:=addr(B) －4 (3) T1:=4*I (5) T3:=T2[T1] (6) T4:=T1 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) P:=P+T7 (3’) T1:=T1+4 (12) if T1≤80 goto (5) 变换循环控制条件

36 本章小结 主要讨论在中间代码级别上进行的优化 优化的种类：局部优化、循环优化、全局优化 基本块内的优化 删除公共子表达式、合并已知量、复写传播、删除无用赋值 借助DAG进行基本块的优化 循环优化 代码外提、强度削弱、变换循环控制条件