编译原理第三版-第十章-代码优化.ppt

第十章 代码优化 结论： 循环不变运算 A:=B op C,可以外提的条件是： 1）不变运算所在的结点是循环所有出口结点的必经结点； 2）把循环中不变运算A:=B op C外提时，要求循环中其他地方不再有A的定值点； 3） 循环中A的所有引用点只有当前不变运算对A的定值可以到达。 * 本章要点 阶段: 编译的第四阶段 任务:对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。 重点: 局部优化 循环优化 表 格 管 理 出 错 处 理 词 法 分 析 语 法 分 析 中间代码生成 优 化 目标代码生成 源程序 目标程序 10.1 优化概述 1. 问题的提出 (1) 编译程序的作用 使计算机的使用方式从用机器语言编程发展到用高级语言编程。是计算机发展史上的一次飞跃。 (2) 早期编译程序的不足 占用的空间大 目标程序质量差 运行的时间长 2. 解决的方法: 代码优化:即对程序进行各种等价变换，使得从变换后的程序出发能生成更有效的目标代码。 优化原则:等价、有效、合算 优化不是目的，只是手段 3. 优化方法 按优化所涉及的程序范围分： 局部优化: 在基本块上进行的优化 合并已知量 删除无用赋值（无用代码） 删除多余运算（公共子表达式） 方法：DAG； 特点： 简单、成熟。 循环优化：在循环块上进行的优化 代码外提 运算强度削弱 删除归纳变量 方法：循环查找算法、数据流分析；复杂、高效。 全局优化：在整个程序上的优化 方法：全局控制流分析、全局数据流分析; 特点：代价大、高效。 10.2 局部优化 问题： 什么是基本块？ 怎样划分基本块？ 在基本块中可以进行哪些优化？ 怎样进行局部优化？ 10.2.1 基本块和流图 对一给定的程序，将其划分为若干个基本块， 在各个基本块中分别进行优化即称为局部优化。 基本块是指: 程序中一顺序执行的语句(四元式)序列, 其中只有一个入口 (第一个语句), 一个出口(最后一 个语句),执行时只能从入口进入, 出口退出。 2. 划分基本块算法 步骤1. 求出四元式程序中各基本块的入口语句, 它们是: (1) 程序的第一个语句, 或 (2) 由条件或无条件转移语句转到的语句, 或 (3) 紧跟在条件转移语句后面的语句; 步骤2. 构造每一个入口语句所属的基本块, 它们是从入口语句到: (1) 下一个入口语句(不包括它), 或 (2) 一转移语句(包括它), 或 (3) 一停语句; 步骤3. 未纳入任一基本块的语句 为控制无法到达的语句, 可予删除。 〖例〗求最大公因子程序 (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt 3. 程序流图（程序控制流程图） 在基本块的集合上增加控制流信息来表示一个程序。 控制流程图是: 具有唯一首结点的有向图 G = ( N, E, n0 )。 其中：N为结点集, E为有向边集, n0为首结点 所谓首结点, 即它到图中任一结点均有通路。 控制流程图简称为流图。 (2) 程序流图: 流图G = ( N, E, n0 ) 中 结点集N为基本块集； 首结点n0为含有第一个语句的基本块； 有向边集E的构成规则: i j 基本块j紧跟在基本块 i 之后, 且基本块 i 的出口语句不是无条件转移语句或停语句； 基本块i 的出口语句是 goto (s) 或 if . . . goto (s) 且 (s) 是基本块j 的入口语句 ； [例]程序的四元式序列: (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:= Y (6) Y:=R (7) goto (3) (8) write Y (9) halt (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:= Y (6) Y:=R (7) goto (3) (8) write Y (9) halt B1 B2 B3 B4 程 序 流