《程序设计语言 编译原理(第三版)第10章》由会员分享，可在线阅读，更多相关《程序设计语言 编译原理(第三版)第10章（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),
5、10.2 局部优化,基本块的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)的值
6、为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 B(即合并已知量),令得到的新常数为p。 如果NODE(p)是处理当前代码时构造出来的结点,则删除它。 如果NODE(p)无定义,则构造一用p做标记的叶结点n。 置NODE(p)=n,转4。(4)执行B
7、 op C(即合并已知量),令得到的新常数为p。 如果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。
8、,10.2 局部优化,10.2 局部优化,4.如果NODE(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,
