程序设计语言编译原理第三版第10章.ppt

《程序设计语言编译原理第三版第10章.ppt》由会员分享，可在线阅读，更多相关《程序设计语言编译原理第三版第10章.ppt（22页珍藏版）》请在三一办公上搜索。

1、第十章优化,优化：如何对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。,注：（1）优化可在编译的各个阶段进行,但最主要的一类优化是在 目标代码生成以前,对语法分析后的中间代码进行的;（2）另一类重要的优化是生成目标代码时进行的,它在很大程 度上依赖于具体的计算机 本章不做讨论,10.1 概述10.2 局部优化10.3 循环优化（略）10.4 数据流分析（略）,第十章优化,10.1 概述,一、优化的目的是为了产生更高效的代码,需遵循以下 的原则:,1.等价原则:经过优化后不应改变程序运行的结果。2.有效原则:使优化后所产生的目标代码运行时间较短,占用的存储空间较小。3.合

2、算原则:应尽可能以较低的代价取得较好的优化效果。,二、各个环节的优化,1.源代码设计2.设计语义时3.中间代码生成后4.目标代码,10.1 概述,三、常用的优化技术,1.删除公共子表达式2.复写传播3.删除无用代码4.代码外提5.强度削弱6.删除归约变量,10.1 概述,10.2 局部优化,一、基本块及流图,1.基本块:指程序中一顺序执行的语句序列,其中只有一个 入口和一个出口,入口就是其中的第一个语句,出 口就是其中的最后一个语句。,2.基本块的划分:(1)求出四元式程序中各个基本块的入口语句;(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）halt,10.2 局部优化,3.流图及其生成,举例:对上例中的程序的各基本块构成的流图如下所示:,10.2 局部优化,4.基本块内的变换:(1)合并已知量(2)临时变量改名(3)变换语句的位置(4)代数变换,10.2 局部优化,二、基本块的DAG表示及其应用,1.基本块的DAG:一种结点带有下述标记或附加信息

4、的DAG(1)图的叶结点以一标识符(变量名)或常数作为标记,表示该 结点代表该变量或常数的值。(2)图的内部结点以一运算符作为标记,表示该结点代表应用 该运算符对其后继结点所代表的值进行运算的结果。(3)图中各个结点上可能附加一个或多个标识符,表示这些变 量具有该结点所代表的值。,10.2 局部优化,例:对下面基本块画出DAG图并进行分析:(1)T1:=4*i(2)T2:=aT1(3)T3:=4*i(4)T4:=bT3(5)T5:=T2*T4(6)T6:=prod+T5(7)prod:=T6(8)T7:=i+1(9)i:=T7(10)if i=20 goto(1),10.2 局部优化,基本块的

5、DAG如下所示：,10.2 局部优化,2.构造基本块的GAD的算法(1)前提:假设DAG各结点信息将用某种适当的数据结构来存放(例如链表)标识符(包括常数)-结点 NODE(A)-描述上述对应关系的函数,其值或者是一个结点的编号,或者无定义(2)中间代码的三种形式:A:=BA:=op BA:=B op C 或 A:=BC(3)构造算法:开始,DAG为空 对基本块中每一条中间代码式,依次执行以下步骤:,10.2 局部优化,步骤:1.如果NODE(B)无定义,则构造一标记为B的叶结点并定义 NODE(B)为这个结点如果当前代码是0型,则记NODE(B)的值为n,转4如果当前代码是1型,则转2(1)

6、如果当前代码是2型,则()如果NODE(C)无定义,则构造一标记 为C的叶结点并定义NODE(C)为这个结点;()转2(2),10.2 局部优化,10.2 局部优化,2.(1)如果NODE(B)是标记为常数的叶结点,则转2(3),否则转3(1)(2)如果NODE(B)和NODE(C)都是标记为常数的叶结点,则转2(4),否则转3(2).(3)执行op B(即合并已知量),令得到的新常数为p。如果NODE(p)是处理当前代码时构造出来的结点,则删除它。如果NODE(p)无定义,则构造一用p做标记的叶结点n。置NODE(p)=n,转4。(4)执行B op C(即合并已知量),令得到的新常数为p。如

7、果NODE(B)或NODE(C)是处理当前代码时新构造出来的结点,则删除它。如果NODE(p)无定义,则构造一用p做标记的叶结点n。置NODE(p)=n,转4。,3.(1)检查DAG中是否已有一结点,其唯一后继为NODE(B)且标记为 op(即找公共子表达式)。如果没有,则构造该结点n,否则就把 已有的结点作为它的结点并设该结点为n。转4。(2)检查DAG中是否已有一结点,其左后继为NODE(B),右后继为 NODE(C),且标为op(即找公共子表达式)。如果没有,则构造 该结点n,否则就把已有的结点作为它的结点并设该结点为 n。转4。,10.2 局部优化,10.2 局部优化,4.如果NODE

8、(A)无定义,则把A附加在结点n上并令NODE(A)=n;否则先把A从NODE(A)结点上的附加标识符集中删除(注意,如果NODE(A)是叶结点,则其标记A不删除),把A附加到新结 点n上并令NODE(A)=n。转处理下一条代码。,例:试构造以下基本块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,10.2 局部优化,基本块G的DAG构造过程如图所示:,按原来构造结点的顺序,把构造出的DAG重新写成中间代码:(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,