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

《程序设计语言编译原理第三版第10章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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）ReadX（2）ReadY（3）R:=XmodY（4）ifR=0goto(8)（5）X:=Y（6）Y:=R（7）goto(3)（8）writeY（9）haltB1B2B3B4B1B2B3B4§10.2局部优化3.流图及其生成举例:对上例中的程序的各基本块构成的流图如下所示:(1)RealX(2)RealY(3)R:=XmodY(4)IfR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)WriteY(9)halt§10.2局部优化4.基本块内的变换:(1)合并已知量(2)临时变量改名(3)变换语句的位

4、置(4)代数变换§10.2局部优化二、基本块的DAG表示及其应用1.基本块的DAG:一种结点带有下述标记或附加信息的DAG(1)图的叶结点以一标识符(变量名)或常数作为标记,表示该结点代表该变量或常数的值。(2)图的内部结点以一运算符作为标记,表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。(3)图中各个结点上可能附加一个或多个标识符,表示这些变量具有该结点所代表的值。§10.2局部优化例:对下面基本块画出DAG图并进行分析:(1)T1:=4*i(2)T2:=a[T1](3)T3:=4*i(4)T4:=b[T3](5)T5:=T2*T4(6)T6:=prod+T5(7)prod

5、:=T6(8)T7:=i+1(9)i:=T7(10)ifi<=20goto(1)§10.2局部优化基本块的DAG如下所示：n10n8n9n7n5n6n4n2n1n11n13n3n12n14T6,prod+T5prod0*T4(1)T2<=[]T1,T3[]T7,i*+20ab4i01§10.2局部优化2.构造基本块的GAD的算法(1)前提:假设DAG各结点信息将用某种适当的数据结构来存放(例如链表)标识符(包括常数)-结点NODE(A)-描述上述对应关系的函数,其值或者是一个结点的编号,或者无定义(2)中间代码的三种形式:A:=BA:=opBA:=BopC或A:=B[C](3)构造算法:①开始

6、,DAG为空②对基本块中每一条中间代码式,依次执行以下步骤:§10.2局部优化步骤:1.如果NODE(B)无定义,则构造一标记为B的叶结点并定义NODE(B)为这个结点如果当前代码是0型,则记NODE(B)的值为n,转4如果当前代码是1型,则转2(1)如果当前代码是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

7、B(即合并已知量),令得到的新常数为p。如果NODE(p)是处理当前代码时构造出来的结点,则删除它。如果NODE(p)无定义,则构造一用p做标记的叶结点n。置NODE(p)=n,转4。(4)执行BopC(即合并已知量),令得到的新常数为p。如果NODE(B)或NODE(C)是处理当前代码时新构造出来的结点,则删除它。如果NODE(p)无定义,则构造一用p做标记的叶结点n。置NODE(p)=n,转4