第九章+优化.ppt

第十章 优化 第九章 优化 本章讨论如何对程序进行各种等价变幻，使得从变换后的程序出发，能生成更有效的目标代码，我们通常称这种变换为优化。优化可以在编译的各个阶段进行，但最主要的一类优化是在目标代码生成以前，对语法分析后的中间代码进行的。这类优化不依赖于具体的计算机。另一类重要的优化是在目标代码生成时进行的它在很大程度上依赖于具体的计算机。本章讨论前一类优化。 有很多技术和手段可以用于中间代码这一级上的优化。总体上讲在一个编译程序中优化器的地位和结构如下图： 优 化 9.1 概述 由于本章讲的方法在计算机的很多领域都很有用，所以应作为学习的重点内容。 优化的目的是为了产生更高效的代码。由优化编译程序提供的对代码的各种变换必须遵循下面的原则： （1）等价原则。 （2）有效原则。 （3）核算原则。 按阶段分类： （1）中间代码优化（与机器无关的） （2）目标代码优化（依赖于机器） 按程序范围分类： : (1)局部优化:(基本块) (2)循环优化:对循环中的代码进行优化 (3)全局优化:大范围的优化 优化的一般方法：删除公共子表达式、复写传播、删除无用代码、代码外提、强度消弱、删除归纳变量 例：有如下源程序段，求其四元式形式的中间代码，并优化之(设A为实型 数组，每个元素占四个字节) 。 P：=0； for i:=1 to 20 do P:=P+A[i]*B[i]; 1、数组的存储空间：设数组中每个元素占t个存储空间，则： 2、程序段对应的中间代码为如下四元式序列： 1）删除公共子表达式(4*i)和代码外提(4)(7) 2）强度削弱(T1的乘法变为加法) 3）变换循环控制条件(T1=80) 、合并已知量(T1:=4)和复写传播(T6:=T5[T1]) 4）删除无用赋值(2)、(6)、(11) 9.2 局部优化 9.2.1基本块及流图 一、基本块： 所谓基本块是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。 在基本块范围内的优化称为局部优化。 二、基本块的算法:（划分四元式程序为基本块） 1、求出四元式程序中各个基本块的入口语句 (1)程序的第一语句;或者 (2)能由条件转移语句或无条件转移语句转到的语句;或者 (3)紧跟在条件转移语句后面的语句 2、对已求出的入口语句,构造其所属基本块的出口语句，出口 语句由该入口语句到另一个入口语句(不包括该入口语句), 或到另一个转移语句(包括该转移语句),或到一个停语句(包 括该停语句), 3、凡未被纳入基本块中的语句,都是程序中控制流无法到达的 语句,删除它们 例:考察下列三地址代码程序 Read x Read y R:=x mod y If r=0 goto (8) X:=Y Y:=R Goto (3) Write r halt 根据算法可得入口语句： （1）、（3）、（8）、（5） 由此可得基本块： （1）（2） （3）（4） （5）（6）（7） （8）（9） 三、程序流图 1、程序流图：以基本块为结点，将控制流的信息增加到基本块的集合上来表示一个程序而得到的有向图，称为程序流图。 2、构造程序流图：如果一个结点的基本块入口语句是程序的第一条语句，称此结点为首结点；如果在执行顺序中，基本块B2紧接在基本块B1后执行，则从B1到B2画一条有向边，即如果 （1）有一个条件或无条件转移语句从B1的最后一条 语句转移到B2的第一条语句；或者 （2）在程序的序列中， B2紧接在B1的后面，并且B1的最后一条语句不是无条件转移语句，我们说B1是B2的前驱， B2是B1的后继 在基本块内，可以以进行删除公共子表达式和删除无用赋值这两种优化外，还可以实现下面几种变换。 1、合并已知量 2、临时变量改名 3、交换语句位置 4、代数变换 9.2.2 基本块的DAG表示及其应用 一、 基本块的DAG表示 1、DAG图即有向无环图 一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG。 1）图的叶结点（没有后继的结点 ）以一标识符（变量明）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用add(A)作为该结点的标记。通