第十章 优化.pptVIP

中国科大 第十章 优 化 通过程序变换（局部变换和全局变换）来改进程序，称为优化 介绍独立于机器的优化，即不考虑任何目标机器性质的优化变换 优化的方法：删除公共子表达式、复写传播、删除无用代码、强度削弱、删除归纳变量等方案 局部优化的实现：基本块内的优化 数据流分析：全局优化 10.1 概述 代码优化的原则： 等价性原则：优化前后的程序功能等价 有效性原则：优化后的目标代码运行时间更短，占用的存储空间更少 合算原则：以较低的代价取得较好的效果 10.1 概述 本节所用的例子是： i = m ?1; j = n; v = a[n] (1) i := m ?1 while (1) { (2) j := n do i = i +1; while(a[i]v); (3) t1 := 4 * n do j =j ?1;while (a[j]v); (4) v := a[t1] if (i = j) break; (5) i := i + 1 x=a[i]; a[i]=a[j]; a[j]=x; (6) t2 := 4 * i } (7) t3 := a[t2] x=a[i]; a[i]=a[n]; a[n]=x; (8) if t3 v goto (5) 10.1 概述 本节所用的例子 i = m ?1; j = n; v = a[n]; (9) j := j ?1 while (1) { (10) t4 := 4 * j do i = i +1; while(a[i]v); (11) t5 := a[t4] do j =j ?1;while (a[j]v); (12) if t5v goto (9) if (i = j) break; (13) if i =j goto (23) x=a[i]; a[i]=a[j]; a[j]=x; (14) t6 := 4 * i } (15 ) x := a[t6] x=a[i]; a[i]=a[n]; a[n]=x; . . . 优化方法：公共子表达式删除 B5 x=a[i]; a[i]=a[j]; a[j]=x; 优化方法：公共子表达式删除 B5 x=a[i]; a[i]=a[j]; a[j]=x; 优化方法：复写传播 优化方法：无用代码的删除 B5 x=a[i]; a[i]=a[j]; a[j]=x; 涉及循环的优化方法： 代码外提 归纳变量删除 强度削弱 优化方法：代码外提 代码外提是循环体内不变的部分，提到循环体外 例：对于语句while (i = limit ? 2 ) … 若limit在循环体内不变，则可变换成 t = limit ? 2; while (i = t ) … 优化方法：强度削弱 优化方法：归纳变量删除 j和t4的值步伐一致地变化 这样的变量叫做归纳变量 在循环中有多个归纳变量时， 也许只需要留下一个 这个操作由归纳变量删除 过程来完成 优化方法：归纳变量删除 优化方案总结 删除公共子表达式 复写传播 删除无用代码（多余赋值语句） 代码外提 强度削弱 删除归纳变量 10.2 局部优化-基本块内部的优化 基本块划分示例 Read X Read Y R:=x mod y If R=0 goto (8) X:=y Y:=R Goto(3) Write Y Halt 基本块的入口： （1）程序的入口语句 （2）条件转移语句和无条件转移语句所转向的第一条语句 （3）紧跟在条件转移语句之后的语句 基本块内部的优化方案 删除公共子表达式 删除无用变量 合并已知量 临时变量改名 交换语句的位置 代数变换 合并已知量 T1:=2 . . T2:=4*T1 临时变量改名 T=b+c 交换语句的位置 T1:=b+c T2:=x+y 代数变换目的:复杂运算简单化 x=x+0 x=x*1 课上练习 P306—1，2 10.2.2 基本块的DAG图表示及其应用 一个基本块的DAG图是一种其结点带有下述标记或附加信息的DAG 图的叶结点（没有后继的结点）以一个标识符或常数进行标记。如果叶结点用来代表某变量A的地址，则用Addr(A)标记； 内部结点用运算符进行标记，表示该结点应用该运算对其直接后继所代表的值进行运算的结果； 图中各个结点上可能附加一个或多个标记，表示这些变量与拥有该节点所代表的值。 例 试对下面基本块B2应用DAG进行优化，并就以下两种情况秀出优化后的四元式序列，（1）假设只有G、L、M在基本块后面还要被引用（2）假设只有L在基本块后面还要被引用 解：做