编译原理(第十一章).pptVIP

第11章 代码优化 11.1 优化技术 11.2 局部优化 11.3 控制流程分析和循环优化 何谓代码优化： 宗旨：获得较好性能的代码(时间和空间) 注意：等价 阶段： source front I.R code target code end generator code 用户 中间代码优化 目标代码优化 一、优化分类 按阶段分: 与机器无关的优化---对中间代码进行 依赖于机器的优化--对目标代码进行 根据优化所涉及的程序范围分成: (1)局部优化:(基本块) (2)循环优化:对循环中的代码进行优化 (3)全局优化:大范围的优化 二、优化技术简介 1.删除多余运算 2.循环不变代码外提 3.强度削弱 4.变换循环控制条件 5.合并已知量与复写传播 6.删除无用赋值 举例 P:=0 for I:=1 to 20 do P:=P+A[I]*B[I] 见：图11.2 图11.6 P249-251 举例： (1) read (C) (2) A:= 0 (3) B:= 1 (4) L1: A:=A + B (5) if B= C goto L2 (6) B:=B+1 (7) goto L1 (8) L2: write (A) (9) halt 基本块的DAG表示及其应用 DAG Directed Acyclic Graph 无环路有向图 基本块的DAG是在结点上带有标记的DAG 叶结点 独特的标识符(名字,常数)标记 内部结点 运算符号标记 各个结点 附加标识符标记 用 DAG 进行基本块的优化 四元式 DAG 结点 0 型： A:=B(:=,B, — ,A) n1 A B 1 型 : A:=op B(op,B, — ,A) n2 A op n1 B 2 型 : A:=B op C(op, B, C ,A) n3 A op n1 n2 B C n1 n2 n1 n3 n1 n2 举例：P255 构造DAG图的过程，实际上已进行了四元的优化。 1.合并已知量(第二步骤) 2.删除多余运算(第三步骤) 3.删除无用赋值(第四步骤) 由DAG图重新生成原基本块的四元式代码序列，就是优化的四元式代码序列。 见：P256-257 11.3 控制流程分析和循环优化 一、程序流图 控制流程图（流图）：具有唯一首结点的有向图。 G=（N，E，n0) ，其中： N：结点集（基本块集） E：有向边集 n0：首结点（包含程序第一个语句的基本块） 二、循环的查找 分析程序流图中结点间的关系 m DOM n 定义 在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n (?a,a MOD a) 必经结点集 定义 结点n的所有必经结点的集合,称为结点n的必经结点集,记为D(n). 举例：图11.12（P259） 利用必经结点集 ，可以求出流图中的回边，从而找出流图中的循环。 回边：假设a→b是流图中的一条有向边，如果 b DOM a ，则称a→b是流图中的一条回边。 有向边n→d是回边，组成的循环是由结点d，结点n以及有通路到达n而该通路不经过d的所有结点组成，并且d是该循环的唯一入口结点。 回边 6 6循环{6} 7 4 {4,5,6,7} 4