编译原理第三版 第十章 代码优化

1、本章要点本章要点 阶段阶段: : 编译的第四阶段编译的第四阶段 任务任务: :对程序进行各种对程序进行各种等价变换等价变换，使得从变换后，使得从变换后的程序出发，能生成更有的程序出发，能生成更有效的目标代码。效的目标代码。 重点重点: : 局部优化局部优化 循环优化循环优化表表格格管管理理出出错错处处理理 词词 法法 分分 析析语语 法法 分分 析析中间代码生成中间代码生成优优 化化目标代码生成目标代码生成源程序源程序目标程序目标程序10.1 优化概述优化概述1. 问题的提出问题的提出(1) 编译程序的作用编译程序的作用 使计算机的使用方式从用机器语言编程发展到用使计算机的使用方式从用机器语言

2、编程发展到用高级语言编程。是计算机发展史上的一次飞跃。高级语言编程。是计算机发展史上的一次飞跃。(2) 早期编译程序的不足早期编译程序的不足 占用的空间大占用的空间大目标程序质量差目标程序质量差 运行的时间长运行的时间长2. 解决的方法解决的方法:代码优化代码优化:即对程序进行各种等价变换，使得从变即对程序进行各种等价变换，使得从变换后的程序出发能生成更有效的目标代码。换后的程序出发能生成更有效的目标代码。u 优化原则优化原则:等价、有效、合算等价、有效、合算优化不是目的，只是手段优化不是目的，只是手段3. 优化方法优化方法 按优化所涉及的按优化所涉及的程序范围程序范围分：分： 局部优化局部优

3、化: 在基本块上进行的优化在基本块上进行的优化 合并已知量合并已知量 删除无用赋值（无用代码）删除无用赋值（无用代码） 删除多余运算（公共子表达式）删除多余运算（公共子表达式） 方法：方法：DAG； 特点：特点： 简单、成熟。简单、成熟。 循环优化：循环优化：在循环块上进行的优化在循环块上进行的优化 代码外提代码外提 运算强度削弱运算强度削弱 删除归纳变量删除归纳变量 方法：循环查找算法、数据流分析；复杂、高效。方法：循环查找算法、数据流分析；复杂、高效。 全局优化：全局优化：在整个程序上的优化在整个程序上的优化 方法：全局控制流分析、全局数据流分析方法：全局控制流分析、全局数据流分析; 特点

4、：代价大、高效。特点：代价大、高效。10.2 局部优化局部优化 问题：问题： 什么是基本块？什么是基本块？ 怎样划分基本块？怎样划分基本块？ 在基本块中可以进行哪些优化？在基本块中可以进行哪些优化？ 怎样进行局部优化？怎样进行局部优化？10.2.1 基本块和流图基本块和流图 对一给定的程序，将其划分为若干个基本块，对一给定的程序，将其划分为若干个基本块， 在各个基本块中分别进行优化即在各个基本块中分别进行优化即称为局部优化称为局部优化。1. 基本块是指基本块是指: 程序中一顺序执行的语句程序中一顺序执行的语句(四元式四元式)序列序列, 其中只有一个入口其中只有一个入口 (第一个语句第一个语句)

5、, 一个出口一个出口(最后一最后一个语句个语句),执行时只能从入口进入执行时只能从入口进入, 出口退出。出口退出。 2. 划分基本块算法划分基本块算法步骤步骤1. 求出四元式程序中各基本块的入口语句求出四元式程序中各基本块的入口语句, 它们是它们是:(1) 程序的程序的第一个第一个语句语句, 或或(2) 由条件或无条件转移语句由条件或无条件转移语句转到转到的语句的语句, 或或(3) 紧跟在紧跟在条件转移语句后面条件转移语句后面的语句的语句;步骤步骤2. 构造每一个入口语句所属的基本块构造每一个入口语句所属的基本块, 它们是它们是从入口语句到从入口语句到:(1) 下一个入口语句下一个入口语句(不

6、包括它不包括它), 或或(2) 一转移语句一转移语句(包括它包括它), 或或(3) 一停语句一停语句;步骤步骤3. 未纳入任一基本块的语句未纳入任一基本块的语句为控制无法到达的语句为控制无法到达的语句, 可予删除。可予删除。例例求最大公因子程序求最大公因子程序(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) halt3. 程序流图（程序控制流程图程序流图（程序控制流程图） 在基本块的集合上增加控制流信息来表示一个程序。在基本块的集合上增加控制流信息来表示

7、一个程序。(1)控制流程图是控制流程图是: 具有唯一首结点的有向图具有唯一首结点的有向图 G = ( N, E, n0 )。 其中：其中：N为结点集为结点集, E为有向边集为有向边集, n0为首结点为首结点 所谓首结点所谓首结点, 即它到图中任一结点均有通路。即它到图中任一结点均有通路。 控制流程图简称为控制流程图简称为流图流图。(2) 程序流图程序流图: 流图流图G = ( N, E, n0 ) 中中 结点集结点集N为基本块集；为基本块集； 首结点首结点n0为含有第一个语句的基本块；为含有第一个语句的基本块； 有向边集有向边集E的构成规则的构成规则:i ju 基本块基本块j紧跟在基本块紧跟在

8、基本块 i 之后之后, 且基本块且基本块 i 的出口语句不是无条件转移语句或停语句；的出口语句不是无条件转移语句或停语句；u 基本块基本块i 的出口语句是的出口语句是 goto (s) 或或 if . . . goto (s) 且且 (s) 是基本块是基本块j 的入口语句的入口语句 ； 例例 程序的四元式序列程序的四元式序列: :(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

9、Y(4) if R=0 goto (8)(5) X:= Y(6) Y:=R(7) goto (3)(8) write Y(9) haltB1B2B3B4程程 序序 流流 图图4.4.基本块内的优化基本块内的优化 例例对以下求向量内积的对以下求向量内积的PASCAL程序段的中间代码进行优化程序段的中间代码进行优化:P := 0; (设设low=1,w=4)for I := 1 to 20 do (AI地址：地址：I*w+(base-low*w)P:= P + AI * BI(1) P:=0(2) I:=1(3) T1:=4*I(4) T2:=addr(A) - 4(5) T3:=T2T1 B2(

10、6) T4:=4*I(7) T5:=addr(B) - 4(8) T6:=T5T4(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if I20 goto (3)删除公共子表达式删除公共子表达式 (3)、(6)为公共子式为公共子式 可将可将(6)改为改为T4:=T1B1(1) P:=0(2) I:=1 B1(3)T1:=4*I B2(4) T2:=addr(A) - 4(5) T3:=T2T1 (6) T4:=T1(7) T5:=addr(B) - 4 (8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if

11、 I20 goto (3)图图1 1 优化前的四元优化前的四元式式图图2 删除公共子表达式和复写传播删除公共子表达式和复写传播进行复写传播进行复写传播 B2中中(6) T4:=T1 (8) T6:=T5T4 可改为可改为(8)T6:=T5T1T4：=T1T6:=T5T1(1) P:=0 B1(2) I:=1(3)T1:=4* I B2 (4) T2:=addr(A) - 4(5) T3:=T2T1 (6) T4:=T1(7) T5:=addr(B) - 4 (8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if I20 goto (3)(

12、1) P:=0(2) I:=1 B1(4) T2:=addr(A) - 4(7) T5:=addr(B) - 4(3)T1:=4*I(5) T3:=T2T1 B2(8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if I20 goto (3)外提循环不变外提循环不变式式：(4)、(7)为循环为循环不变式，可外提至不变式，可外提至B1中中删除无用代码删除无用代码图图2 2 删除公共子表达式和删除公共子表达式和复写传播复写传播图图3 3删除无用代码和代码外删除无用代码和代码外提提(1) P:=0(2) I:=1 B1(4) T2:=addr(

13、A) - 4(7) T5:=addr(B) - 4(3)T1:=4*I(5) T3:=T2T1 B2(8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if I20 goto (3)(1) P:=0(2) I:=1 B1(4) T2:=addr(A) - 4(7) T5:=addr(B) - 4(3) T1:=4*I(5) T3:=T2T1 B2(8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(3) T1:=T1+4(12) if I20 goto (5)运算强度削弱运算强度削弱 由由(3)

14、T1:=4*I (11) I:=I+1 可改为可改为: 将将(3)外提至外提至B1 (11)后增加后增加(3) (3) T1:=T1+4图图3 删除无用代码和代码外提删除无用代码和代码外提图图4 运算强度削弱运算强度削弱(1) P:=0(2) I:=1 B1(4) T2:=addr(A) - 4(7) T5:=addr(B) - 4(3) T1:=4*I(5) T3:=T2T1 B2(8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(3) T1:=T1+4(12) if I20 goto (5)(5) T3:=T2T1 B2(8) T6:=T5T1

15、(9) T7:=T3*T6(10) P:=P+T7(3) T1:=T1+4(12) if T180 goto (5)(1) P:=0 B1(4) T2:=addr(A) - 4(7) T5:=addr(B) - 4(3) T1:=4变换循环控制条件变换循环控制条件删除归纳变量删除归纳变量 (12) if I20 goto (5) 分析分析I的作用的作用:计算计算 T1:=4*I循环控制条件循环控制条件 I20递归赋值递归赋值: I:=I+1 变换控制条件变换控制条件:计数法计数法: I20比较法比较法: T180 删除删除(11)图图4. 4. 运算强度削弱运算强度削弱合并已知量合并已知量 B

16、1中中(2) I:=1 (3)T1:=4*I (3) 可改为可改为: (3) T1:=4 删除删除(2)图图5. 变换循环控制条件与合并变换循环控制条件与合并已知量已知量小结小结 局部优化局部优化: 删除公共子表达式删除公共子表达式 合并已知量合并已知量 复写传播复写传播 删除无用赋值删除无用赋值 循环优化循环优化: 外提循环不变式外提循环不变式 运算强度削弱运算强度削弱 变换循环控制条件变换循环控制条件 优化前后比较优化前后比较:循环循环B2 优化前优化前 优化后优化后 四元式个数四元式个数 10 6乘法个数乘法个数 3 1 以上优化方法均可用算法实现以上优化方法均可用算法实现基本块内还可进

17、行以下几种变换基本块内还可进行以下几种变换临时变量改名临时变量改名. 交换语句的位置交换语句的位置. 代数变换代数变换. u说明说明: 无用赋值的判定无用赋值的判定: 对对A赋值后赋值后, A不被引用不被引用 (全局数据流分析全局数据流分析) 对对A赋值后赋值后, 引用前又重新赋值引用前又重新赋值 ( 容易判定容易判定) A仅在递归赋值仅在递归赋值(A:=A+C)中被引用中被引用(全局数据全局数据流分析流分析) #10.2.2. 基本块的基本块的DAG表示及其应用表示及其应用1. 无环路有向图无环路有向图DAG (Directed Acyclic Graph)(1) 定义定义: 若有向图中所有

18、通路均非环路若有向图中所有通路均非环路, 则称其为则称其为DAG(2) 基本块的基本块的DAG(用于描述计算过程用于描述计算过程): 是为结点是为结点附加了信息附加了信息的的DAG。 叶结点叶结点:下标记下标记: 常数或标识符常数或标识符右标记右标记: 标识符标识符 内结点内结点: 下标记下标记: 运算符运算符 右标记右标记: 标识符标识符(3) 结点形式结点形式 (1) A:=Bn1 AB 0 0型型 n2n1n1 n2n3 AopopB1 1型型A:=a+*bca:=b*-c+b*-c的的DAG（中间代（中间代 码的图形表码的图形表 示）示）2型型BC(2) A:= op B(3) A:=

19、B op C2. 基本块基本块DAG构造算法构造算法构造构造还原还原四元式序列四元式序列DAG 基本思想基本思想: 构造算法构造算法: 表格结构表格结构:标识符标识符(常数常数)结点对应表结点对应表,函数函数NODE(A)=算法大意：算法大意：对基本块中每一个四元式对基本块中每一个四元式A:=B op C 执行以下步骤：执行以下步骤： 构造叶结点构造叶结点 NODEB、NODEC, 按四元式类型判转按四元式类型判转;检查合并已知量检查合并已知量:若四元式的运算对象均为常数若四元式的运算对象均为常数, 则生成该运算结果的结点则生成该运算结果的结点; 检查公共子表达式检查公共子表达式:若四元式为公

20、共子表达式若四元式为公共子表达式, 则把已有的结点作为它的结点则把已有的结点作为它的结点(即加右标记即加右标记); 检查无用赋值检查无用赋值: 若若NODEA已是某结点的右标记已是某结点的右标记, 则从该右标记集合中删除后再建立新结点。则从该右标记集合中删除后再建立新结点。n无定义无定义初始化初始化取下一条四元式取下一条四元式 (0)A:=B、（、（1）A:=opB、（、（2）A:=BopCNODE（B）定义）定义？构造新结点构造新结点n标记为标记为B找到标记为找到标记为B B的结点，设为的结点，设为nB为常数叶结点为常数叶结点？计算计算P=op B删除刚生成删除刚生成B结点结点DAG中有唯一

21、后继中有唯一后继为为B且标记为且标记为op的结的结？NODE（P）定义）定义？生成新结生成新结n标为标为P找到结点设找到结点设n有有,设为设为n构造新结点构造新结点n标为标为P，令，令B为其唯一为其唯一后继后继NODE（A）定义？）定义？将将A标记在结点标记在结点n上上NODE（C）定义）定义？生成新结生成新结n标为标为C找到结点设为找到结点设为nB和和C都为常数都为常数？计算计算P=Bop C删除刚生成删除刚生成的新结的新结B和和CDAG中有以中有以B、C为后继且标记为后继且标记为为op的结点？的结点？有，设为有，设为n 构造新结点构造新结点n标为标为P，令，令B、C为其为其左右后继左右后继

22、NODE（P）定义）定义？生成新结生成新结n标为标为P找到结点设找到结点设nNYYNNYNY将将A从原从原结删除结删除NNYYNY(0)(1)(2)算法框图：算法框图：例例 试构造以下基本块的试构造以下基本块的DAG(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+S(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+S(8) T5:=T3*T4(9) T6:=R - S(10) B:=T5*T6n1n2n3n4n5n6n8n7 T6 _ 构造构造DAG还原为四元式还原为四元式(1)T0:=3.14(2)T1:=6.28(3)T3:=6.28(

23、4)T2:=R+S(5)T4:=T2(6)A:=6.28*T2(7)T5:=A(8)T6:=R - S(9)B:=A*T6 效果分析效果分析比较比较 运运 算算已知量已知量 公共公共 无用无用 乘乘 法法 加、减法加、减法 总条数总条数 子式子式 赋值赋值 优化前优化前 (2) (6) (3) (7) (5) 5条条 3条条 10条条优化后优化后 已合并已合并 已删除已删除 已删除已删除 2条条 2条条 9条条 3.14T0n226.28T1RS+T2*AT3,T4,T5*B,B3. DAG的其它优化信息的其它优化信息(1) 优化信息优化信息叶结点的下标记标识符：块外定值叶结点的下标记标识符：

24、块外定值, 块内引用的标块内引用的标识符识符各结点的右标记标识符：块内定值各结点的右标记标识符：块内定值, 块外可引用的块外可引用的标识符标识符(2) 进一步优化进一步优化: 删除其它形式的无用赋值删除其它形式的无用赋值 A被赋值被赋值,永远不引用永远不引用:A不出现在任何基本块的叶不出现在任何基本块的叶结点下标记中，且结点下标记中，且A无前驱无前驱; A被定值被定值, 仅递归赋值中引用仅递归赋值中引用; A:=B op C之后为之后为 D:=A A仅此引用仅此引用 , 则可改为则可改为 D:=B op C. 例例 基本块基本块P: (1) A:=B*C (2) D:=B/C (3) E:=A

25、+D (4) F:=2*E (5) G:=B*C (6) H:=G*G (7) F:=H*G (8) L:=F (9) M:=Ln1 n2 n3A,G n4 D* /n8 H *n9 F,L,M n5 E* +n6n72 B CF *还原还原: (1) A:=B*C (2) G:=A (3) D:=B/C (4) E:=A+D (5) H:=G*G (6) F:=H*G (7) L:=F (8) M:=L若仅若仅G,L,M后面引用后面引用:(1) G:=B*C(2) H:=G*G(3) L:=H*G(4) M:=L若仅仅若仅仅L后面引用后面引用:(1) G:=B*C(2) H:=G*G(3)

26、L:=H*G4. DAG构造算法的进一步讨论构造算法的进一步讨论 对数组元素赋值对数组元素赋值 多个变量共用单元多个变量共用单元 间接赋值间接赋值(1) 对数组元素赋值对数组元素赋值例例 源程序源程序: (1) X:=AI (2) AJ:=Y (3) Z:=AI四元式四元式: (1) S1:=addr(A) - 1 (2) X:=S1I (3) S2:=addr(A) - 1 (4) S2J:=Y (5) S3:=addr(A) - 1 (6) Z:=S3I问题问题: (2),(6)是否为公共子式是否为公共子式? I=J , YAI时时, XZn5 X,Z n8 = = n3 S1,S2,S3

27、n1 n2 n4 n6 n7addr(A) 1 I J Y解决方法解决方法: 构造构造 =结点时结点时把把addr(A)祖先结点中祖先结点中= 结点注销结点注销即不可再附加右标记但可引用。即不可再附加右标记但可引用。(取消作为公共子式的资格取消作为公共子式的资格)n9 Z-(2) 多个变量共享同一单元多个变量共享同一单元 问题问题: 对其中一个变量赋值对其中一个变量赋值, 即对其它变量赋值。即对其它变量赋值。 解决方法解决方法:构造此类结点时构造此类结点时, 把把DAG中结点上与它有该关系中结点上与它有该关系的标识符注销即不可再引用该结点的值的标识符注销即不可再引用该结点的值, 若需要引用若需

28、要引用, 则重则重新构造叶结点。新构造叶结点。(3) 间接赋值间接赋值: *P:=W 问题问题: P指向哪一个变量指向哪一个变量? 解决方法解决方法: 为保险计为保险计, 把把DAG各结点上标识符均注销。各结点上标识符均注销。(4) 如果不是按构造结点的顺序重写代码，那么将如果不是按构造结点的顺序重写代码，那么将DAG还原时还原时 需要遵循一定的次序：需要遵循一定的次序： 对数组对数组A任何元素引用或赋值任何元素引用或赋值, 必须跟在原来位于其前面必须跟在原来位于其前面的对数组的对数组A任何元素的赋值之后。任何元素的赋值之后。 对共享同一单元的变量引用或赋值对共享同一单元的变量引用或赋值,必须

29、跟在原来位于其必须跟在原来位于其前面的任何赋值之后。前面的任何赋值之后。 对任何变量的引用或赋值对任何变量的引用或赋值, 必须跟在原来位于其前面的任必须跟在原来位于其前面的任何过程调用或间接赋值之后。何过程调用或间接赋值之后。#10.3 循环优化循环优化 1.循环的定义：循环的定义： 程序流图中满足下述性质的结点序列程序流图中满足下述性质的结点序列称为循环：称为循环：它们是强连通的。它们是强连通的。 即其中任何两个结点间必有通路即其中任何两个结点间必有通路, 且该通路上的结点都属于该结点序列且该通路上的结点都属于该结点序列;单结点时有自回路。单结点时有自回路。 有且仅有一个入口结点。有且仅有一

30、个入口结点。 所谓入口结点为从序列外某结点有一有向边引向它或所谓入口结点为从序列外某结点有一有向边引向它或它为程序流图的首结点。它为程序流图的首结点。 例例 1234567循环循环: : 6 4, 5, 6, 7 2, 3, 4, 5, 6, 7 非循环非循环: 2, 4 2, 3, 4 4, 6, 7 4, 5, 7 程程 序序 流流 图图说明说明: :用用SPSP方法写方法写的程序的程序, ,其流其流图中任何反图中任何反复执行的代复执行的代码均归入某码均归入某个循环个循环(入口结点入口结点不唯一不唯一)2.循环优化方法循环优化方法 代码外提代码外提 强度削弱强度削弱 删除归纳变量删除归纳变量(1)代码外提代码外提 1)循环不变运算循环不变运算: 对于循环中形如对于循环中形如 A:=B op C的代码，如果的代码，如果B和和C均为常数均为常数, 或到达它们的定值点在循环外或到达它们的定值点在循环外(由由ud链可知链可