编译原理优化.ppt

第八章 代码优化 代码优化指对代码进行等价变换, 使变换后的代码具有更高的时间和空间效率。 代码优化可在编译的不同阶段进行, 但最主要的优化在目标代码生成前进行, 这类优化不依赖于具体计算机; 另一类优化在生成目标化码时进行, 它依赖于具体计算机。 根据优化对象涉及的程序范围, 优化可分为: 局部优化、循环优化、全局优化。 局部优化 局部优化指对代码的每个线性部分所进行的优化。每个线性部分只有一个入口和一个出口, 称为基本块。 基本块是程序中一段顺序执行的语句序列, 其中只有一个入口和一个出口。基本块的执行只能从入口进入、从出口退出。 一个给定的程序可划分为一系列基本块,在基本块范围内进行的优化称为局部优化。 基本块的划分方法 关键是确定入口语句和出口语句。 (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 基本块分别为: (1)(2), (3)(4), (5)(6)(7), (8)(9) 基本块的DAG表示 DAG(Directed Acyclic Graph)主要用于对基本块进行优化。它是一种结点带有下述标记或附加信息的有向图(树): (1)叶结点以标识符(变量名)或常数作为标记, 表示该变量或常数的值。若叶结点表示一变量A的地址, 则用addr(A)作为标记。 　　(2)内部结点以运算符作为标记, 表示用该运算符对其直接后继结点进行运算的结果。 　　(3)各个结点可附加一个或多个标识符, 表示这些变量具有该结点代表的值。 　　通常把叶结点上的标识符加下标0 (初值) 不同的三地址代码与其对应的DAG结点形式 上图中, 各结点圆圈中的ni是构造DAG过程中各结点的编号, 各结点下面的符号(运算符、标识符或常数)是各结点的标记,各结点右边的标识符是结点的附加标识符。 　　 注意: 转移语句结点的右边可附加一语句位置用于指示转移目标, 其余结点的右边只允许附加标识符; 数组元素赋值的结点有三个后继, 其余结点最多只有两个后继。 利用DAG进行基本块优化的基本思想 　　 首先按基本块内三地址代码序列顺序把所有的三地址代码构造成一个DAG, 然后按构造结点的次序将DAG还原成三地址代码序列。 　　 由于在构造DAG的同时作了局部优化(合并已知量、删除公共子表达式、删除无用赋值), 故所得到的是优化的三地址代码序列。 为了便于叙述DAG构造算法, 把三地址代码按其对应结点的后继结点个数分为四类: 　　(1) 0型三地址代码: 后继结点个数为0 　　(2) 1型三地址代码: 有一个后继结点 　　(3) 2型三地址代码: 有两个后继结点 　　(4) 3型三地址代码: 有三个后继结点 　　约定: 用大写字母表示三地址代码中的变量名(或常数); 用Node(A)表示A在DAG中的相 应结点。 DAG构造算法的基本步骤 (1) 构造叶结点 (2) 合并已知量 (3) 构造op结点(删除公共子表达式) (4) 添加附加信息(删除无用赋值) 基本块的DAG构造算法 仅含0,1,2型代码: A=B, A= op B, A=B op C (1) 构造叶结点 若Node(B)无定义, 则构造一标记为B的叶结点, 并按下列情况做不同处理: ①若当前三地址代码是0型, 转(4); ②若当前三地址代码是1型, 转(2)①; ③若当前三地址代码是2型, 则 若Node(C)无定义, 则构造一标记为C的叶结点; 转(2)②; (2)合并已知量 ①若Node(B)为常数, 转(2)③, 否则转(3)①; ②若Node(B)和Node(C)都为常数, 转(2)④,否则转(3)②; ③执行op B, 令新得常数为P。若Node(B)是处理当前三地址代码时新建结点, 则删除它。 若Node(P)无定义, 则构造一标记为P的叶结点; 转(4); ④执行B op C, 令新得常数为P。若Node(B)或Node(C)是处理当前三地址代码时新建结点,则删除它。若Node(P)无定义, 则构造一标记为P的叶结点; 转(4); (3)构造op结点