第7章：代码优化解析

1、2021/3/261 第7章代码优化 2021/3/262 词法分析器词法分析器 语法分析器语法分析器 中间代码生成器中间代码生成器 优化段优化段 源程序源程序 单词符号单词符号 语法单位语法单位 四元式四元式 表表 格格 管管 理理 出出 错错 处处 理理 目标代码生成器目标代码生成器 四元式四元式 目标代码目标代码 2021/3/263 7.17.1 优化概述 优化是一种等价的、有效的程序变换。优化的目 的是为了产生更高效的代码。由优化的编译程序 提供的对代码的各种变换必须遵循下面的原则: 等价原则:是指经过优化后不应改变源程序运行的 结果。 有效原则:经优化后所产生的目标代码运行时间较

2、短,占用存储空间较小。 合算原则:应尽可能以较低的代价取得较好的优化 效果。 编译前端编译前端代码优化器代码优化器编译后端编译后端 控制流分析控制流分析数据流分析数据流分析 代码变换代码变换 2021/3/264 优化技术分类 代码优化实际上是对代码进行等价变换, 由一组代码变成运行结果相同的另一组代 码。 源程序一级的优化:对中间代码的优化,与 机器无关,面向各种语言.主要包括:局部 优化、循环优化、全局优化 目标代码的优化:与具体机器有关. .主要 包括对寄存器的优化,多处理机的优化、 特殊指令的优化等 2021/3/265 优化技术分类优化技术分类 局部优化:程序中顺序执行的语句序 列

3、循环优化:程序中循环语句的优化 全局优化:整个程序范围内的优化 2021/3/266 优化的种类优化的种类: : 删除多余运算删除多余运算( (或称删除公用子表达式或称删除公用子表达式) ) 代码外提代码外提 强度消弱强度消弱 变换循环控制条件变换循环控制条件 合并已知量合并已知量 复写传播复写传播 删除无用赋值删除无用赋值 2021/3/267 中间代码优化举例 设、为两个一维数组设、为两个一维数组,他们的初始地址他们的初始地址 分别为分别为addr(A),addr(B), 源程序段是源程序段是 S=0 FOR (i=1,i=20;i+) S=S+Ai+Bi 2021/3/268 假设机器按

4、字节编制 根据程序流向的特点,分为B1,B2两块. B1是循环体外的语句,B2是可重复执行的循 环语句序列 原则:通过等价变换,将尽量减少循环体中 的语句,同时尽可能减少无实际意义的重复 计算与赋值,尽可能降低机器运算强度,运 算的级别. 2021/3/269 删除公共子表达式删除公共子表达式(删除多删除多 余运算余运算) 公共子表达式是指在一个基本程序块内计公共子表达式是指在一个基本程序块内计 算结果相同的子表达式算结果相同的子表达式 代码外提代码外提 是指把循环不变的运算提到循环体前面是指把循环不变的运算提到循环体前面 优化前的中间代码优化前的中间代码 2021/3/2610 经删除公共子

5、表达式和代码经删除公共子表达式和代码 外提后的中间代码外提后的中间代码 3.降低运算强度降低运算强度 主要指不改变运算结果的主要指不改变运算结果的 前提下前提下,将程序执行时间长的将程序执行时间长的 运算替换成执行时间短的运运算替换成执行时间短的运 算降低运算级别算降低运算级别 2021/3/2611 经强度削弱后的中间代码经强度削弱后的中间代码 4.变换循环控制变量(删除归纳变 量) 如果在循环体内存在一个变量(或临时 变量)T与循环控制变量 i保持线性关系, 同时在循环后面不引用I,而除去i又不影 响程序运行结果,则可由T取代循环控制 变量变量 I, 这种方法称为变换循环控制 变量(删除归

6、纳变量) 5.合并已知量 合并已知量是指若参加运算的两个对象在编 译时都是已知量,则可以在编译时直接计算 出它们的运算结果 6.复写传播 是指尽量不引用那些在程序中仅仅只传递信 息而不改变其值,也不影响其运行结果的变 量. 2021/3/2612 经变换循环控制变量经变换循环控制变量, ,合并合并 已知量已知量, ,复写传播后的中间复写传播后的中间 代码代码 7,删除无用赋值删除无用赋值 减少无用的变量,使代 码更简洁 2021/3/2613 假 (1) S=0 (4) T2=addr(A)-4 (7) T5=addr(B)-4 (3) T1=4 (5) T3= T2T1 (8) T6= T5

7、T1 (9) T7= T3* T6 (10) S=S+ T7 (3) T1= T1+4 (12)if T180 goto(5) B2 B1 真 经删除无用赋值后的经删除无用赋值后的 中间代码中间代码 2021/3/2614 经过优化后经过优化后, ,代码具有以下特点代码具有以下特点: : (1)(1)减少了循环体内可执行代码减少了循环体内可执行代码:10:10条条6 6条条 (2)(2)减少了乘法运算次数减少了乘法运算次数:3:3次次1 1次次 (3)(3)减少了全程范围内使用的变量减少了全程范围内使用的变量:i,T:i,T4 4 2021/3/2615 7.2 局部优化 合并已知量:运算对象

8、是已知量,编译时直接计算它 们的值,而不必等到程序运行时再计算。 删除公共子表达式:如果一个表达式E的值,前面已 经算过,并且在这之后E的值没有改变,则E称为公 共子表达式,则可以避免它的重复运算,称为删除公 共子表达式。（删除多余运算） 删除无用赋值:如果一些变量的值在整个程序中不 再被使用,则这些变量的赋值对程序的运算结果没 有任何作用,则可以删除对这些变量赋值 的代码,称 为删除无用赋值。 2021/3/2616 局部优化 基本块:一个基本块是指程序中一顺序执行 的语句序列。其中只有一个入口和一个出 口,入口就是其中第一个语句,出口就是最后 一条语句。对于一个基本块来说,执行时只 能从其

9、入口进入,从出口退出。 局限于基本块范围内的优化称为基本块内 的优化,或称局部优化。 2021/3/2617 划分四元式程序为基本块的算法: 1.求出四元式程序中各个基本块的入口语句: 1) 程序第一个语句,或 2) 能由条件转移语句或无条件转移语句转移到 的语句,或 3) 紧跟在条件转移语句后面的语句。 2021/3/2618 2. 对以上求出的每个入口语句,确定其所属 的基本块。它是由该入口语句到下一入口 语句(不包括该入口语句)、或到一转移语 句(包括该转移语句) 、或一停语句(包括 该停语句)之间的语句序列组成的。 入口语句入口语句n 入口语句入口语句m 入口语句入口语句n 转移语句转

10、移语句m 入口语句入口语句n 停语句停语句m 2021/3/2619 3. 凡未被纳入某一基本块中的语句,都是程 序不可到达的语句,可以从程序中删除。 2021/3/2620 例例: :划分基本块划分基本块 (1)read X (2) read Y (3) C:=X mod Y (4) if C=0 goto (8) (5) X:=Y (6) Y:=C (7) goto (3) (8) write Y (9) halt 1.求出四元式程序中各个基本块的入口求出四元式程序中各个基本块的入口 语句语句: 1) 程序第一个语句程序第一个语句,或或 2) 能由条件转移语句或无条件转移语能由条件转移语句

11、或无条件转移语 句转移到的语句句转移到的语句,或或 3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。 2021/3/2621 例例: :划分基本块划分基本块 (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.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语 句句: 1) 程序第一个语句程序第一个语句,或或 2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语 句转移到的语句句

12、转移到的语句,或或 3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。 2021/3/2622 例例: :划分基本块划分基本块 (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.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语 句句: 1) 程序第一个语句程序第一个语句,或或 2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语 句转移到的语句句转移到的语句,或或 3) 紧跟在

13、条件转移语句后面的语句。紧跟在条件转移语句后面的语句。 2021/3/2623 例例: :划分基本块划分基本块 (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.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语 句句: 1) 程序第一个语句程序第一个语句,或或 2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语 句转移到的语句句转移到的语句,或或 3) 紧跟在条件转移语句后面的语句。紧跟在条

14、件转移语句后面的语句。 2021/3/2624 例例: :划分基本块划分基本块 (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.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语 句句: 1) 程序第一个语句程序第一个语句,或或 2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语 句转移到的语句句转移到的语句,或或 3) 紧跟在条件转移语句后面的语句紧跟在条件转移语句后面的语句。 2021/

15、3/2625 例例: :划分基本块划分基本块 (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 2. 对以上求出的对以上求出的 每个入口语句每个入口语句,确确 定其所属的基本定其所属的基本 块。它是由该入块。它是由该入 口语句到口语句到下一入下一入 口语句口语句(不包括该不包括该 入口语句入口语句)、或到、或到 一转移语句一转移语句(包括包括 该转移语句该转移语句)、或、或 一停语句一停语句(包括该包括该 停语句停语句)之间的语之

16、间的语 句序列组成的。句序列组成的。 2021/3/2626 程序流图: (8) write Y (9) halt (5) X:=Y (6) Y:=R (7) goto (3) (3) R:=X mod Y (4) if R=0 goto (8) (1) read X (2) read Y B1 B2 B3 B4 2021/3/2627 程序流图 以基本块作为结点,控制程序流向作为有向 弧,画出的图,称为程序流图。 流图G=（N,E,n0） N:表示流图的有限结点集合,每一个结点对 应一个基本块。 E:流图的有向边集合; n0:表示唯一的首结点,包含程序第一个语 句的基本块。 2021/3/2

17、628 程序流图程序流图 每个流图以基本块为每个流图以基本块为结点结点。如果一个结点的基本。如果一个结点的基本 块的入口语句是程序的第一条语句块的入口语句是程序的第一条语句, ,则称此结点则称此结点为为 首结点首结点。如果在某个执行顺序中。如果在某个执行顺序中, ,基本块基本块B B2 2紧接在紧接在 基本块基本块B B1 1之后执行之后执行, ,则从则从B B1 1到到B B2 2有一条有向边。即有一条有向边。即, , 如果如果 有一个条件或无条件转移语句从有一个条件或无条件转移语句从B B1 1的最后一条的最后一条 语句转移到语句转移到B B2 2的第一条语句的第一条语句; ;或者或者 在

18、程序的序列中在程序的序列中, ,B B2 2紧接在紧接在B B1 1的后面的后面, ,并且并且B B1 1的的 最后一条语句不是一个无条件转移语句。我们最后一条语句不是一个无条件转移语句。我们 就说就说B B1 1是是B B2 2的的前驱前驱, ,B B2 2是是B B1 1的的后继。后继。 2021/3/2629 (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 (8) write Y (9) halt (5) X:=Y (6)

19、 Y:=R (7) goto (3) (3) R:=X mod Y (4) if R=0 goto (8) (1) read X (2) read Y B1 B2 B3 B4 2021/3/2630 对下面的程序段划分基本块,构造程序 的控制流图 (1) read c */1 (2) a:=0 (3)b:=1 (4)a:=a+b */2 (5)if bc goto (10) (6) b:=b+1 */3 (7)goto (4) (8)a:=a+1 (9)b:=a+2 (10)write a */4 (1)halt 基本块划分 块号bfirstbLastb sucbpredb 1(1)(3)2_

20、 2(4)(5)3、41、3 3(6)(7)22 4(10)(11)_2 2021/3/2631 (1)read c 1 (2) a:=0 (3)b:=1 L1:(4)a:=a+b 2 (5)if bc goto L2 (6) b:=b+1 3 (7) goto L1 L2: (10) write A 4 (11) halt 程序流图: 2021/3/2632 基本块的DAG图 DAG(Directed Acyclic Graph)是一种有向 图,常常用来对基本块进行优化。基本块中 的语句的计算过程可以用一张图表示出来, 即一个基本块可用一个DAG图表示。 2021/3/2633 图表示法图表

21、示法 图表示法图表示法 DAGDAG 抽象语法树抽象语法树 无循环有向图无循环有向图( (Directed Acyclic Graph,Directed Acyclic Graph, 简称简称DAG)DAG) 对表达式中的每个子表达式对表达式中的每个子表达式, ,DAGDAG中都有一个结中都有一个结 点点 一个内部结点代表一个操作符一个内部结点代表一个操作符, ,它的孩子代表它的孩子代表 操作数操作数 在一个在一个DAGDAG中代表公共子表达式的结点具有多中代表公共子表达式的结点具有多 个父结点个父结点 2021/3/2634 a:=b*(-c)+b*(-c)的图表示法 assign a+ *

22、 buminus c DAG assign a+ * buminus c 抽象语法树抽象语法树 * buminus c 2021/3/2635 抽象语法树抽象语法树对应的代码对应的代码: T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 assign a+ * buminus c 抽象语法树抽象语法树 * buminus c 2021/3/2636 DAG对应的代码对应的代码: T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5 assign a+ * buminus c DAG 抽象语法树抽象语法树对应的代码对应的代码: T1:=-c

23、 T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 2021/3/2637 描述计算过程的描述计算过程的DAGDAG是一种带有下述标记或附加是一种带有下述标记或附加 信息的信息的DAG:DAG: n1 3.14 n3 n4 Rr n5 + T2, T4 图的图的叶结点叶结点以一以一标识符标识符或或常数常数作为标记作为标记, ,表示该表示该 结点代表该变量或常数的值结点代表该变量或常数的值; ; 图的图的内部结点内部结点以一以一运算符运算符作为作为 标记标记, ,表示该结点代表应用该运表示该结点代表应用该运 算符对其后继结点所代表的值算符对其后继结点所代表的值 进

24、行运算的结果进行运算的结果; ; 图中各个结点上可能图中各个结点上可能 附加一个或多个标识附加一个或多个标识 符符( (称附加标识符称附加标识符) )表表 示这些变量具有该结示这些变量具有该结 点所代表的值。点所代表的值。 2021/3/2638 借助DAG进行优化 利用DAG来进行优化的主要思想:将一基本 块中的每一个四元式依次表示成对应的一 个DAG,再按原来构造DAG结点的顺序重写四 元式序列,便可得到“合并已知常量”、 “删除无用赋值”、“删除多余运算”后 的等价基本块优化了的基本块 。 2021/3/2639 基本块的基本块的DAGDAG表示及应用表示及应用 一个基本块一个基本块,

25、,可用一个可用一个DAGDAG来表示与各四元来表示与各四元 式相对应的式相对应的DAGDAG结点形式结点形式: : 四元式四元式 DAG DAG 图图 (0) 0型型: A:=B (:=,B,-,A) n1 A B 2021/3/2640 四元式四元式 DAG DAG 图图 (1) 1型型: A:=op B (op,B,-,A) n1 A B n2 op (2) 2型型: A:=B op C (op,B,C,A)n2 A B n1 op n3 C 2021/3/2641 四元式四元式 DAG DAG 图图 (3) 2型型: A:=BC (=,BC,-,A) n2 A B n1 = n3 C (

26、4) 2型型: if B rop C goto (s) (jrop,B,C,(s)n2 (s) B n1 rop n3 C 2021/3/2642 四元式四元式 DAG DAG 图图 (5) 3型型: DC:=B (=,B,-,DC) (6) 0型型: goto (s) (j,-,-,(s) (s)n1 n2 B n1 = n4 C n3 D 2021/3/2643 例例: :赋值语句赋值语句T T4 4:=A+B-:=A+B-（E-E-（C+DC+D） 四元式序列G T1:=A+B T2:=C+D T3:=E-T2 T4:=T1-T3 A B E C D n9 n3 n8 n1n2n7 n6

27、 n4 n5 T4 T1 T3 T2 + - - + DAG: 2021/3/2644 例例7.3试构造以下基本块试构造以下基本块G的的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 2021/3/2645 To 3.14 (a) n1 (1) T(1) T0 0:=3.14:=3.14 2021/3/2646 T0 T1 3.14 6.28 (b) n2n1 (1)T(1)T0 0:=

28、3.14:=3.14 (2)T(2)T1 1:=2:=2* *T T0 0 2021/3/2647 (1)T(1)T0 0:=3.14:=3.14 (2)T(2)T1 1:=2:=2* *T T0 0 (3)T(3)T2 2:=R+r:=R+r 2021/3/2648 A * T2 + T0 T1 3.14 6.28 R r (d) n2 n5 n3n1n4 n6 (1)T(1)T0 0:=3.14:=3.14 (2)T(2)T1 1:=2:=2* *T T0 0 (3)T(3)T2 2:=R+r:=R+r (4)A:=T(4)A:=T1 1* *T T2 2 2021/3/2649 A,B

29、* T2 + T0 T1 3.14 6.28 R r (e) n2 n5 n3n1n4 n6 (1)T(1)T0 0:=3.14:=3.14 (2)T(2)T1 1:=2:=2* *T T0 0 (3)T(3)T2 2:=R+r:=R+r (4)A:=T(4)A:=T1 1* *T T2 2 (5)B:=A(5)B:=A 2021/3/2650 A,B * T2 + T0 T1,T3 3.14 6.28 R r (f) n2 n5 n3n1 n4 n6 (1)T(1)T0 0:=3.14:=3.14 (2)T(2)T1 1:=2:=2* *T T0 0 (3)T(3)T2 2:=R+r:=R+

30、r (4)A:=T(4)A:=T1 1* *T T2 2 (5)B:=A(5)B:=A (6)T(6)T3 3:=2:=2* *T T0 0 2021/3/2651 A,B * T2,T4 + T0 T1,T3 3.14 6.28 R r (g) n2 n5 n3n1 n4 n6 (1)T(1)T0 0:=3.14:=3.14 (2)T(2)T1 1:=2:=2* *T T0 0 (3)T(3)T2 2:=R+r:=R+r (4)A:=T(4)A:=T1 1* *T T2 2 (5)B:=A(5)B:=A (6)T(6)T3 3:=2:=2* *T T0 0 (7)T(7)T4 4:=R+r:

31、=R+r 2021/3/2652 A,B,T5 * T2,T4 + T0 T1,T3 3.14 6.28 R r (h) n2 n5 n3n1 n4 n6 (1)T(1)T0 0:=3.14:=3.14 (2)T(2)T1 1:=2:=2* *T T0 0 (3)T(3)T2 2:=R+r:=R+r (4)A:=T(4)A:=T1 1* *T T2 2 (5)B:=A(5)B:=A (6)T(6)T3 3:=2:=2* *T T0 0 (7)T(7)T4 4:=R+r:=R+r (8)T(8)T5 5:=T:=T3 3* *T T4 4 2021/3/2653 (1)T(1)T0 0:=3.1

32、4:=3.14 (2)T(2)T1 1:=2:=2* *T T0 0 (3)T(3)T2 2:=R+r:=R+r (4)A:=T(4)A:=T1 1* *T T2 2 (5)B:=A(5)B:=A (6)T(6)T3 3:=2:=2* *T T0 0 (7)T(7)T4 4:=R+r:=R+r (8)T(8)T5 5:=T:=T3 3* *T T4 4 (9)T(9)T6 6:=R-r:=R-r 2021/3/2654 (1) T0:=3.14 n1 3.14 T0 n2 6.28 T1 n3 n4 Rr n5 + T2 n6 * A, B , T3 , T4 , T5 n7 T6 - n8 * B (2) T1:=2*T0 (3) T2:=R+