编译原理第6章代码优化.ppt

第6部分 代码优化 ;　　　 源程序经过词法分析、语法分析、语义分析等阶段的编译工作，得到了与源程序功能等价的中间代码。 但是，由于这种中间代码是“机械生成”的结果，因而必然存在效率不高和有冗余代码的现象，还需进行代码优化。 所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。;　优化（变换）的宗旨是： 等价----经优化工作变换后的代码运行结果应与原来程序运行结果一样。 有效----经优化工作变换后的代码应运行时间较短，占用的存储空间较小。 合算----获得较好性能的目标代码是优化工作的意图，而优化本身包括大量的代码分析和变换工作，这里有个权衡：应尽可能以较低的代价取得较好的优化效果。 ;　　　 一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行，如下图所示：;代码优化的种类：;与机器无关的优化 ; 窥孔优化器的工作方式是在中间代码上滑动一个包含几条代码的窗口（窥孔），找出其中不够好（优化）的相邻代码序列。;局部优化 ;循环优化 ; 是在整个程序范围内进行的优化, 需进行数据流分析, 花费代价很高。;6.1 局 部 优 化; 6.1.1 基本块的划分方法 所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是该序列的第一个语句，出口就是该序列的最后一个语句。 对一个基本块来说，执行时只能从其入口进入，从其出口退出。 对一个给定的程序，我们可以把它划分为一系列基本块，在各个基本块范围内进行的优化称为局部优化。; 划分基本块的关键问题是准确定义入口语句和出口语句。 (1) 从四元式序列确定满足以下条件的入口语句： ① 四元式序列的第一个语句； ② 能由条件转移语句或无条件转移语句转移到的语句； ③ 紧跟在条件转移语句后面的语句。 (2) 确定满足以下条件的出口语句： ① 下一个入口语句的前导语句； ② 转移语句(包括转移语句自身)； ③ 停语句(包括停语句自身)。;例如，考察下面求最大公因子的三地址代码程序： (1) ?read X (2) ?read Y (3) ?R=X % Y (4) ?if R=0 goto (8) (5) ?X=Y (6) ?Y=R (7)? goto (3) (8) ?write Y (9) ?halt; 6.1.2 基本块的DAG表示 DAG(Directed Acyclic Graph)是一种有向图，常常用来对基本块进行优化。 一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG：; (1) 图的叶结点(无后继的结点)以一标识符(变量名)或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来表示一变量A的地址，则用addr(A)作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。 (2) 图的内部结点(有后继的结点)以一运算符作为标记，表示该结点代表应用该运算符对其直接后继结点所代表的值进行运算的结果。 (3) 图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。 一个基本块由一个四元式序列组成，且每一个四元式都可以用相应的DAG结点表示。;图6–1 四元式与DAG结点; 利用DAG进行基本块优化的基本思想是： 首先按基本块内的四元式序列顺序将所有的四元式构造成一个DAG; 然后按构造结点的次序将DAG还原成四元式序列。 由于在构造DAG的同时已作了局部优化，所以最后所得到的是优化过的四元式序列。 ; 为了DAG构造算法的需要，我们将图6–1中的四元式按照其对应结点的后继结点个数分为四类： (1) 0型四元式：后继结点个数为0，如图6–1(1)所示； (2) 1型四元式：有一个后继结点，如图6–1(2)所示； (3) 2型四元式：有两个后继结点，如图6–1(3)、(4)、(5)所示； (4) 3型四元式：有三个后继结点，如图6–1(6)所示。;