编译原理课件cap10.ppt

第十章 优化 第十章 优化 本章讨论如何对程序进行各种等价变幻，使得从变换后的程序出发，能生成更有效的目标代码，我们通常称这种变换为优化。优化可以在编译的各个阶段进行，但最主要的一类优化是在目标代码生成以前，对语法分析后的中间代码进行的。这类优化不依赖于具体的计算机。另一类重要的优化是在目标代码生成时进行的它在很大程度上依赖于具体的计算机。本章讨论前一类优化。 有很多技术和手段可以用于中间代码这一级上的优化。总体上讲在一个编译程序中优化器的地位和结构如下图： 优 化 10。1 概述 由于本章讲的方法在计算机的很多领域都很有用，所以应作为学习的重点内容。 优化的目的是为了产生更高效的代码。由优化编译程序提供的对代码的各种变换必须遵循下面的原则： （1）等价原则。 （2）有效原则。 （3）核算原则。 本章我们着重讨论中间代码这一级上的优化，其应掌握优化的一般方法：删除公共子表达式、复写传播、删除无用代码、代码外提、强度消弱、删除归纳变量 10。2 局部优化 10。2。1基本块及流图 所谓基本块是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。 这里应掌握划分四元式程序为基本块的算法。 在基本块内，可以以进行删除公共子表达式和删除无用赋值这两种优化外，还可以实现下面几种变换。 1。合并已知量 2。临时变量改名 3。交换语句位置 4。代数变换 10。2。2基本块的DAG表示及其应用 一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG。 1。图的叶结点（没有后继的结点 ）以一标识符（变量明）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用add(A)作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。 2。图的内部结点（有后继的结点）以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。 3。图中各结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。 用DAG图优化程序应掌握。 10。3 循环优化 循环就是程序中那些可能反复执行的代码序列。 对循环中的代码，可以实行代码外提、强度消弱和删除归纳变量等优化。 这部分应作为重点，作一部分习题。 10。3。1代码外提 所谓变量A在某点d 的定值到达另一点u（或称变量A的定值点d 到达另一点u ），是指流图中从d有一通路到达u且该通路上没有A的其它定值。 实行代码外提时，我们在循环入口结点前建立一个新的结点（基本块），称循环的前置结点。循环前置结点以循环入口为其为以后继，原来流图中从循环外引到循环入口结点的有向边，改成引到循环前置结点。 [例10。5] 对下面一段Pascal元程序： for I:= 1 to 10 do A[I, 2*J] := A[I, 2*J] + 1 （ 其中A是 10 X10 的二维数组） 产生中间代码如图10。11。 代码外提后： 10.3.2 强度消弱： 再次强度消弱 如果，T2, T6出循环后不是活动变量，则可在循环后删除。 10。3。3删除归纳变量 例题与习题解答 [例10。1]试对以下基本块B1应用DAG进行优化。 B1: A:=B*C D:=B/C E:=A+D F:=E*2 G:=B*C H:=G*G F:=H*G L:=F M:=L 并就以下两种情况分别写出优化后的四元式序列： （1）假设G、L、M在基本块后面背引用； （2）假设只有L在基本块后被引用。 解：对于B1其DAG图： (2) 若只有L在基本块后被引用，则优化为： G := B*C H :=G*G L := H*G [例10。2] 试写出以下程序段 for I := 1 to M do for j := 1 to N do