编译原理十代码优化.docVIP

第十章 代码优化 某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化。一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行。中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化对循环中的代码进行的优化。全局优化是在整个程序范围内进行的优化。 本章重点：局部优化 基本块的DAG表示 第一节 优化技术简介 为了说明问题，我们来看下面这个例子，源程序是： P :=0 For I :=1 to 20 do P :=P+A[I]*B[I]; 经过编译得到的中间代码如图10-1-1所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。那么，对于这个中间代码段，可进行如下这些优化。 1、删除多余运算（删除公共子表达式）优化的目的在于使目标代码执行速度较快。图10-1-1中间代码（3）和（6）中都有4＊I的运算，而从（3）到（6）没有对I赋值，显然，两次计算机的值是相等的。所以，（6）的运算是多余的。我们可以把（6）变换成：T4 :=T1。这种优化称为删除多余运算或称为删除公共子表达式。 2、代码外提 减少循环中代码总数的一个重要办法是代码外提。这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。使之只在循环外计算一次，上例中，我们可以把（4）和（7）提到循环外。经过删除多余运算和代码外提后，代码变成图10-1-2。 3、强度削弱 强度削弱的思想是把强度大的运算换算成强度小的运算。例如把乘法运算换成加法运算等等。在图10-1-2的循环中，每循环一次，I的值增1，T1的值与I保持线性关系，每次总是增加4。因此，我们可以把循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算，而在循环中将其变换成加法运算。变换后如图10-1-3所示。 4、变换循环控制条件 图10-1-3的代码中，I和T1始终保持T1= 4 * I的线性关系，这样可以把（12）的循环控制条件I≤20变换成T1≤80，这样整个程序的运行结果不变。这种变换称为变换循环控制条件。经过这一变换后，循环中I的值在循环后不会被引用，四元式（11）可以从循环中删除，这就是我们的目的所在。 5、合并已知量与复写传播 图10-1-3中，四元式（3）计算4 * I时，I必为1。所以（3）中的4 * I的两个运算对象都是编码时的已知量，可在编译时计算出它的值，即（3）可变为T1= 4这种变换称为合并已知量。 图10-1-3中，（6）把T1的值复写到T4中，四元式（8）要引用T4的值，而（6）到（8）之间未改变T4和T1的值，则（8）改为T6 : =T5[T1]，之后运算结果保持不变。这种变换称为复写传播。图10-1-3经过变换循环控制条件，合并已知量和复写传播等变换后，变为图10-1-4。 6、删除无用赋值 在图11.5中，（6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋 6、删除无用赋值 在图10-1-4中，（6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋值，但只有（11）引用I。所以，只要程序中其它地方不需要引用T4和I，则（6），（2）和（11）对程序的运行结果无任何作用。我们称之为无用赋值，无用赋值可以从程序中删除，如图10-1-5所示（设（6）（2）（11）为无用赋值）。 比较图10-1-1和图10-1-5可看出，经过优化后的代码的执行效率提高了很多。当然，实现这些优化的代价也是很大的。 第二节 局部优化 我们所说的局部优化是指基本块内的优化，所谓基本块，是指程序中一顺序执行语句序列，其中只有一个入口语句和一个出口语句。执行时只能从其入口语句进入，从其出口语句退出。对于一个给定的程序，我们可以把它划分为一系列的基本块。在各基本块的范围内分别进行优化。 一、基本块的划分 在介绍基本块的构造之前，我们先定义基本块的入口语句，所谓入口语句，严格地说来就是： 1、程序的第一语句；或者， 2、条件转移语句或无条件转移语句的转移目标语句；或者， 3、紧跟在条件转移语句后面的语句。 有了入口语句的概念之后，我们就可以给出划分中间代码（四元