编译原理独立于机器的优化9.ppt

第九章独立于机器的优化 通过程序变换 局部变换和全局变换 来改进程序 称为优化代码改进变换的标准代码变换必须保程序的含义采取安全稳妥的策略变换减少程序的运行时间平均达到一个可度量的值变换所作的努力是值得的 第九章独立于机器的优化 本章介绍独立于机器的优化 即不考虑任何依赖目标机器性质的优化变换通过实例来介绍代码改进的主要机会数据流分析包括的几类重要的全局收集的信息数据流分析的一般框架和一般框架有区别的常量传播部分冗余删除的优化技术循环的识别和分析 9 1优化的主要种类 9 1 1优化的主要源头程序中存在许多程序员无法避免的冗余运算通过像a i j 和x f1的方式引用数组元素和结构的域随着程序被编译 对这样高级数据结构的访问展开成多步低级算术运算对同一个数据结构的多次访问导致许多公共的低级运算程序员没有办法删除这些冗余 9 1优化的主要种类 9 1 2一个实例i m 1 j n v a n 1 i m 1while 1 2 j ndoi i 1 while a i v 4 v a t1 if i j break 5 i i 1x 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 ift3 vgoto 5 9 1优化的主要种类 9 1 2一个实例i m 1 j n v a n 9 j j 1while 1 10 t4 4 jdoi i 1 while a i v 12 ift5 vgoto 9 if i j break 13 ifi jgoto 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 9 1优化的主要种类 9 1优化的主要种类 9 1 3公共子表达式删除b5x a i a i a j a j x t6 4 ix a t6 t7 4 it8 4 jt9 a t8 a t7 t9t10 4 ja t10 xgotob2 9 1优化的主要种类 b5x a i a i a j a j x t6 4 ix a t6 t7 4 it8 4 jt9 a t8 a t7 t9t10 4 ja t10 xgotob2 t6 4 ix a t6 t8 4 jt9 a t8 a t6 t9a t8 xgotob2 9 1优化的主要种类 9 1优化的主要种类 b5x a i a i a j a j x t6 4 ix a t6 t7 4 it8 4 jt9 a t8 a t7 t9t10 4 ja t10 xgotob2 t6 4 ix a t6 t8 4 jt9 a t8 a t6 t9a t8 xgotob2 9 1优化的主要种类 b5x a i a i a j a j x t6 4 ix a t6 t7 4 it8 4 jt9 a t8 a t7 t9t10 4 ja t10 xgotob2 t6 4 ix a t6 t8 4 jt9 a t8 a t6 t9a t8 xgotob2 x a t2 t9 a t4 a t2 t9a t4 xgotob2 9 1优化的主要种类 9 1优化的主要种类 b5x a i a i a j a j x t6 4 ix a t6 t7 4 it8 4 jt9 a t8 a t7 t9t10 4 ja t10 xgotob2 t6 4 ix a t6 t8 4 jt9 a t8 a t6 t9a t8 xgotob2 x a t2 t9 a t4 a t2 t9a t4 xgotob2 9 1优化的主要种类 b5x a i a i a j a j x t6 4 ix a t6 t7 4 it8 4 jt9 a t8 a t7 t9t10 4 ja t10 xgotob2 t6 4 ix a t6 t8 4 jt9 a t8 a t6 t9a t8 xgotob2 x a t2 t9 a t4 a t2 t9a t4 xgotob2 x t3a t2 t5a t4 xgotob2 9 1优化的主要种类 b6x a i a i a n a n x t11 4 ix a t11 t12 4 it13 4 nt14 a t13 a t12 t14t15 4 na t15 x x t3t14 a t1 a t2 t14a t1 x 9 1优化的主要种类 b6x a i a i a n a n x a t1 能否作为公共子表达式 t11 4 ix a t11 t12 4 it13 4 nt14 a t13 a t12 t14t15 4 na t15 x x t3t14 a t1 a t2 t14a t1 x 9 1优化的主要种类 9 1优化的主要种类 9 1 4复写传播形成为f g的赋值叫做复写语句优化过程中会大量引入复写 9 1优化的主要种类 9 1 4复写传播形成为f g的赋值叫做复写语句优化过程中会大量引入复写复写传播变换的做法是在复写语句f g后 尽可能用g代表f x t3a t2 t5a t4 t3gotob2 x t3a t2 t5a t4 xgotob2 9 1优化的主要种类 9 1 4复写传播形成为f g的赋值叫做复写语句优化过程中会大量引入复写复写传播变换的做法是在复写语句f g后 尽可能用g代表f复写传播变换本身并不是优化 但它给其它优化带来机会常量合并死代码删除 9 1优化的主要种类 9 1 5死代码删除死代码是指计算的结果决不被引用的语句一些优化变换可能会引起死代码例 debug true debug false 测试后改成 if debug print if debug print 9 1优化的主要种类 9 1 5死代码删除死代码是指计算的结果决不被引用的语句一些优化变换可能会引起死代码例 复写传播可能会引起死代码删除 x t3a t2 t5a t4 t3gotob2 a t2 t5a t4 t3gotob2 9 1优化的主要种类 9 1 6代码外提代码外提是循环优化的一种循环优化的其它重要技术归纳变量删除强度削弱例 while i limit 2 变换成t limit 2 while i t 9 1优化的主要种类 9 1 7强度削弱和归纳变量删除j和t4的值步伐一致地变化这样的变量叫做归纳变量在循环中有多个归纳变量时 也许只需要留下一个这个操作由归纳变量删除过程来完成对本例可以先做强度削弱它给删除归纳变量创造机会 9 1优化的主要种类 j j 1t4 4 jt5 a t4 ift5 vgotob3 b3 除第一次外 t4 4 j在b3的入口一定保持在j j 1后 关系t4 4 j 4也保持 9 1优化的主要种类 9 1优化的主要种类 9 2数据流分析介绍 9 2 1数据流抽象点基本块中 两个相邻的语句之间为程序的一个点基本块的开始点和结束点路径点序列p1 p2 pn 对1和n 1间的每个i 满足pi是先于一个语句的点 pi 1是同一块中位于该语句后的点 或者pi是某块的结束点 pi 1是后继块的开始点 9 2数据流分析介绍 9 2 1数据流抽象路径实例 1 2 3 4 9 1 2 3 4 5 6 7 8 3 4 9 9 2数据流分析介绍 9 2 1数据流抽象分析程序的行为时 必须在其流图上考虑所有的执行路径 在调用或返回语句被执行时 还需要考虑路径在多个流图之间的跳转 然后从每个程序点的所有可能状态中抽取解决特定数据流分析所需信息通常 从流图得到的程序执行路径数无限 且执行路径长度没有有限的上界程序分析从程序点的所有可能状态中为该点总结出一组有限的事实 9 2数据流分析介绍 9 2 1数据流抽象明了所有路径上所有程序状态是不可能的数据流分析不打算区分到达一个程序点的不同路径 也不试图掌握完整的状态它抽取出某些细节 以获取用于分析目的的数据从同样的状态 根据程序分析的不同目的 可以提炼出不同的信息 9 2数据流分析介绍 9 2 1数据流抽象点 5 所有程序状态 a 1 243 由 d1 d3 定值1 到达 定值 d1 d3 的定值到达点 5 2 常量合并 a在点 5 不是常量 9 2数据流分析介绍 9 2 2数据流分析模式数据流值数据流分析总把程序点和数据流值联系起来数据流值代表在程序点能观测到的所有可能程序状态集合的一个抽象语句s前后两点数据流值用in s 和out s 来表示数据流问题就是通过基于语句语义的约束 迁移函数 和基于控制流的约束来寻找所有语句s的in s 和out s 的一个解 9 2数据流分析介绍 9 2 2数据流分析模式迁移函数f语句前后两点的数据流值受该语句的语义约束沿执行路径正向传播out s fs in s 沿执行路径逆向传播in s fs out s 基本块b由语句s1 s2 sn依次组成in si 1 out si i 1 2 n 1fb fn f2 f1 逆向fb f1 fn 1 fn out b fb in b 逆向in b fb out b 9 2数据流分析介绍 9 2 2数据流分析模式控制流约束正向传播in b p是b的前驱out p 逆向转播out b s是b的后继in s 约束方程组通常不是唯一解求解的目标是要找到满足这两组约束 控制流约束和迁移约束 的最 精确 解 9 2数据流分析介绍 9 2 3到达 定值到达程序点的所有定值可用来判断一个变量在某程序点是否为常量可用来判断一个变量在某程序点是否无初值别名给到达 定值的计算带来困难过程参数 数组访问 间接引用等都可能引起别名如何判断对p next的赋值没有改变q next程序分析必须是稳妥的本章其余部分仅考虑变量无别名的情况 9 2数据流分析介绍 9 2 3到达 定值到达程序点的所有定值可用来判断一个变量在某程序点是否为常量可用来判断一个变量在某程序点是否无初值别名给到达 定值的计算带来困难注销在一条路径上 先前对x的赋值被后面对x的赋值所注销 9 2数据流分析介绍 gen和kill分别表示基本块生成和注销的定值 9 2数据流分析介绍 基本块的gen和kill是怎样计算的对三地址指令d u v w 它的迁移函数是fd x gend x killd 若f1 x gen1 x kill1 f2 x gen2 x kill2 f2 f1 x gen2 gen1 x kill1 kill2 gen2 gen1 kill2 x kill1 kill2 若基本块b有n条三地址指令killb kill1 kill2 killngenb genn genn 1 killn genn 2 killn 1 killn gen1 kill2 kill3 killn 9 2数据流分析介绍 到达 定值的数据流等式genb b中能到达b的结束点的定值语句killb 整个程序中决不会到达b结束点的定值in b 能到达b的开始点的定值集合out b 能到达b的结束点的定值集合两组等式 根据gen和kill定义in和out in b p是b的前驱out p out b genb in b killb out entry 到达 定值方程组的迭代求解 9 2数据流分析介绍 in b out b b100000000000000b200000000000000b300000000000000b400000000000000 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000000000000b200000000000000b300000000000000b400000000000000 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000001110000b200000000000000b300000000000000b400000000000000 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000001110000b211100000000000b300000000000000b400000000000000 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000001110000b211100000011100b300000000000000b400000000000000 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000001110000b211100000011100b300111000000000b400000000000000 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000001110000b211100000011100b300111000001110b400000000000000 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000001110000b211100000011100b300111000001110b400111100000000 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000001110000b211100000011100b300111000001110b400111100010111 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000001110000b211101110011100b300111000001110b400111100010111 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000001110000b211101110011110b300111000001110b400111100010111 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 in b out b b100000001110000b211101110011110b300111100001110b400111100010111不再继续计算 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b4 d1 d4 9 2数据流分析介绍 到达 定值等式是正向的方程in b p是b的前驱out p 另一类数据流等式是反向的到达 定值等式的合流算符是求并集out b gen b in b kill b 另一类数据流等式的合流算符是求交集 9 2数据流分析介绍 9 2 4活跃变量定义x的值在p点开始的路径上被引用 则说x在p点活跃 否则称x在p点是死亡的in b 块b开始点的活跃变量集合out b 块b结束点的活跃变量集合useb 块b中有引用且在引用前无定值的变量集defb 块b中有定值的变量集应用一种重要应用就是基本块的寄存器分配 9 2数据流分析介绍 9 2 4活跃变量例use b2 i j def b2 i j 9 2数据流分析介绍 9 2 4活跃变量活跃变量数据流等式in b useb out b defb out b s是b的后继in s in exit 和到达 定值等式之间的联系与区别都以集合并算符作为它们的汇合算符信息流动方向相反 in和out的作用相互交换use和def分别代替gen和kill 最小解代替最大解 9 2数据流分析介绍 9 2 5可用表达式x y zx y zx y z y z pppy z在p点y z在p点y z在p点可用不可用不可用 9 2数据流分析介绍 9 2 5可用表达式 9 2数据流分析介绍 9 2 5可用表达式定义若到点p的每条路径都计算x y 并且计算后没有对x或y赋值 那么称x y在点p可用e genb 块b产生的可用表达式集合e killb 块b注销的可用表达式集合in b 块b入口的可用表达式集合out b 块b出口的可用表达式集合 9 2数据流分析介绍 9 2 5可用表达式数据流等式out b e genb in b e killb in b p是b的前驱out p in entry 同先前的主要区别使用 而不是 作为这里数据流等式的汇合算符 9 2数据流分析介绍 in集合的不同初值比较in b2 out b1 out b2 以b2为例 out b2 g in b2 k 9 2数据流分析介绍 9 2 6小结三个数据流问题到达 定值 活跃变量 可用表达式每个问题的组成数据流值的论域 数据流的方向 迁移函数 边界条件 汇合算符 数据流等式见书上表9 2 9 3数据流分析的基础 本节内容1 把各种数据流模式作为一个整体抽象地研究2 形式地回答数据流算法的下列几个基本问题在什么情况下数据流分析中使用的迭代算法是正确的迭代算法所得解的精度如何迭代算法是否收敛数据流方程的解的含义是什么 9 3数据流分析的基础 数据流分析框架 d v f 包括数据流分析的方向d 它可以是正向或逆向数据流值的论域半格v 汇合算子 v到v的迁移函数族f包括适用于边界条件 entry和exit结点 的常函数 9 3数据流分析的基础 9 3 1半格半格 v 是一个集合v和一个二元交运算 汇合运算 交运算满足下面三点性质幂等性 对所有的x x x x交换性 对所有的x和y x y y x结合性 对所有的x y和z x y z x y z半格有顶元 可以还有底元 对v中的所有x x x对v中的所有x x 9 3数据流分析的基础 9 3 1半格偏序关系集合v上的关系 自反性 对所有的x x x反对称性 对所有的x和y 如果x y并且y x 那么x y传递性 对所有的x y和z 如果x y并且y z 那么x z此外 关系 的定义x y当且仅当 x y 并且 x y 9 3数据流分析的基础 9 3 1半格半格和偏序关系之间的联系半格 v 的汇合运算 确定了半格值集v上一种偏序 对v中所有的x和y x y当且仅当x y x若x y等于g 则g就是x和y的最大下界 9 3数据流分析的基础 9 3 1半格例 半格的论域v是u的幂集集合并作为汇合运算 是顶元 u是底元 x x并且u x u 对应二元关系是 集合交作为汇合运算 u是顶元 是底元 对应二元关系是 数据流方程组通常有很多解 但是按偏序 意义上的最大解是最精确的 到达 定值 最精确的解含最少定值 可用表达式 最精确的解含最多表达式 9 3数据流分析的基础 9 3 1半格格图这是一个格 本课程用半格概念就够了 是 x y的最大下界x y 9 3数据流分析的基础 9 3 1半格积半格 定义略 上例数据流值的集合是定值集合的幂集可以用从每个变量的一个简单半格构造出的积半格来表示整个定值半格半格的高度上升链是序列x1 x2 xn半格的高度就是其中最长上升链中 的个数若半格的高度有限 证明数据流分析迭代算法的收敛则非常容易 9 3数据流分析的基础 9 3 2迁移函数迁移函数族f v v有下列性质f有一个恒等函数if封闭于复合若f中所有函数f都有单调性 即x y蕴涵f x f y 或f x y f x f y 则称框架 d v f 是单调的框架 d v f 的分配性对f中所有的f f x y f x f y 9 3数据流分析的基础 9 3 2迁移函数例 到达 定值分析若f1 x g1 x k1 f2 x g2 x k2 若g和k是空集 则f是恒等函数f2 f1 x g2 g1 x k1 k2 g2 g1 k2 x k1 k2 因此f1和f2的复合f为f g x k 的形式分配性可以由检查下面的条件得到g y z k g y k g z k 9 3数据流分析的基础 9 3 3一般框架的迭代算法以正向数据流分析为例 1 out entry ventry 2 for 除了entry以外的每个块b out b 3 while 任何一个out出现变化 4 for 除了entry以外的每个块b 5 in b p是b的前驱out p 6 out b fb in b 7 9 3数据流分析的基础 9 3 3一般框架的迭代算法算法的一些可以证明的性质如果算法收敛 则结果是数据流方程组的一个解如果框架单调 则所求得的解是数据流方程组的最大不动点如果框架单调并且半格的高度有限 那么可以保证算法收敛 9 3数据流分析的基础 9 3 4数据流解的含义结论 算法所得解是理想解的稳妥近似理想解所考虑的路径执行路径集 流图上每一条路径都属于该集合若流图有环 则执行路径数是无界的程序可能的执行路径集 程序执行所走的路径属于该集合 理想解所考虑的路径程序可能的执行路径集 执行路径集寻找所有可能执行路径是不可判定的讨论正向数据流分析 9 3数据流分析的基础 9 3 4数据流解的含义理想解若路径p entry b1 b2 bk 定义fp fk 1 f2 f1ideal b p是从entry到b的一条可能路径fp ventry 有关理解解的结论任何大于理想解ideal的回答一定是不对的任何小于或等于ideal的值是稳妥的在稳妥的值中 越接近ideal的值越精确 9 3数据流分析的基础 9 3 4数据流解的含义执行路径上的解 meetoverpaths mop b p是从entry到b的一条路径fp ventry mop解不仅汇集了所有可能路径的数据流值 而且还包括了那些不可能被执行路径的数据流值对所有的块b mop b ideal b 简写成mop idealmop的定义并没有通向一个直接算法 9 3数据流分析的基础 9 3 4数据流解的含义先前算法得到的最大不动点解mfp不是先找出到达一个块的所有路径 然后用汇合运算 而是访问每个基本块 并且不一定按照程序执行时的次序在每个汇合点 把汇合运算作用在到目前为止得到的数据流值上 其中所用一些初值是人工引入的 9 3数据流分析的基础 9 3 4数据流解的含义mfp与mop的联系mfp访问块未必遵循次序由初值和单调性保证一致mfp较早地使用汇合运算mop b4 f3 f1 ventry f3 f2 ventry in b4 f3 f1 ventry f2 ventry 数据流分析框架具有分配性时 结果是一样的mfp mop ideal 9 4常量传播 9 4 1常量传播框架的数据流值单个变量的数据流值半格变量的类型所允许的所有常量值nac表示不是常量值undef表示没有定义程序中各变量的半格的积把程序中每个变量映射到该半格上的一个值 9 4常量传播 9 4 2常量传播框架的迁移函数令fs是语句s的迁移函数 m fs m 用m和m 之间的联系来表达fs1 如果s不是赋值语句 则fs是恒等函数2 若s对变量x赋值 则对所有v x m v m v 若s的右部是一个常量c 则m x c若s的右部是y z m x m y m z 若m y 和m z 都是常量值 m x nac 若m y 或m z 是nac m x undef 否则 9 4常量传播 9 4 3常量传播框架的单调性m y m z m x undefundefundefc2undefnacnacundefundefc1c2c1 c2nacnacundefnacnacc2nacnacnac 除了s的右部是y z这种情况外 其它所有情况 fs不改变m x 的值 或者改变到返回一个常量在这些情况下 fs肯定是单调的 9 4常量传播 9 4 4常量传播框架的非分配性不管取什么路径 在块b3的出口 z的值是5迭代算法在块b3的入口而不是出口使用汇合运算f3 f1 m0 f2 m0 f3 f1 m0 f3 f2 m0 这个结果虽不精确 但是安全的 9 4常量传播 9 4 5结果的解释entry块置初值undef其它块置初值undefx在块b4入口是10块b5的x引用可以用10代替和执行路径b1 b3 b4 b5不符若程序正确的话 认为x在块b5入口的值只能为10是合适的 9 5部分冗余删除 内容简介冗余计算以公共子表达式的形式出现 或以循环不变表达式的形式出现冗余可能只出现在一部分路径上讨论最小化x y这样表达式的计算次数的方法策略是 一个计算尽量不做 除非它不得不做首先讨论冗余的不同形式 以建立直观认识 然后描述广义的冗余删除问题 最后提出算法算法涉及到求解多个正向或逆向的数据流问题 9 5部分冗余删除 9 5 1冗余的根源公共子表达式 9 5部分冗余删除 9 5 1冗余的根源完全冗余块b4的表达式b c是完全冗余的 因为所有到达b4的路径都计算b c 并且b和c都未重新定值b2和b3的出边的集合形成一个割集 若把该割集删掉 则从起点到b4的路径都被割断 9 5部分冗余删除 9 5 1冗余的根源循环不变表达式 9 5部分冗余删除 9 5 1冗余的根源部分冗余表达式 9 5部分冗余删除 9 5 1冗余的根源放置b c的副本来使b4中的b c完全冗余 9 5部分冗余删除 9 5 2能否删除所有的冗余b3 b4是一条关键边 源结点有多个后继目标结点有多个前驱 增加新块 9 5部分冗余删除 复制代码以删除冗余 9 5部分冗余删除 9 5 3惰性代码移动问题部分冗余删除算法优化后程序具有下列性质无需通过复制代码就可删除的冗余计算都被删除若是部分冗余 则通过放置副本形成完全冗余优化后程序不会执行原来程序中没有的任何计算表达式的计算尽可能推迟尽可能延迟值的计算就是最小化它的生存期 也就是最小化它占用寄存器的时间 9 5部分冗余删除 9 5 4预期表达式 b c部分冗余 不可能提前到b1计算 b5的计算不能再推迟 添加的计算最迟放在b4 9 5部分冗余删除 9 5 4预期表达式 b c部分冗余 不可能提前到b1计算 b5的计算不能再推迟 添加的计算最迟放在b4 期望的优化结果如图 9 5部分冗余删除 9 5 4预期表达式 表达式b c在点p被预期 若所有从p开始的路径上都从p点可用的b和c来计算表达式b c的值b c被块b3 b4 b5 b6 b7和b9预期 9 5部分冗余删除 9 5 5惰性代码移动算法 1 使用预期来决定表达式可以放置的位置 可以建立数据流方程来求解预期表达式 9 5部分冗余删除 9 5 5惰性代码移动算法 2 表达式的副本被放置到该表达式最早被期望的程序点 b3 b5 需要定义可用表达式数据流问题 表达式在点p可用 若在到达p的所有路径上它都被期望 9 5部分冗余删除 9 5 5惰性代码移动算法 3 在保语义且最小化冗余前提下 尽可能延迟表达式的计算 放置在从可延迟到不可延迟的边界上 b4 b5 需要定义可延迟表达式数据流问题 9 5部分冗余删除 9 5 5惰性代码移动算法 4 确定表达式被引用的位置 以便改成引用临时变量 需要定义引用表达式数据流问题 类似于活跃变量分析 9 5部分冗余删除 9 5 5惰性代码移动算法 实施该算法后的结果 9 6流图中的循环 标识循环并对循环专门处理的重要性程序执行的大部分时间消耗在循环上 改进循环性能的优化会对程序执行产生显著影响循环也会影响程序分析的运行时间本节内容介绍概念 支配结点 深度优先排序 回边 图的深度和可归约性用于寻找循环和迭代数据流分析收敛速度的讨论 9 6流图中的循环 9 6 1支配结点结点d是结点n的支配结点 如果从初始结点起 每条到达n的路径都要经过d 写成ddomn 每个结点是它本身的支配结点 循环的入口是循环中所有结点的支配结点 9 6流图中的循环 深度优先生成树 9 6流图中的循环 9 6 2回边和可归约性深度优先生成树前进边后撤边4 3 7 4 10 7 8 3和9 1交叉边2 3和5 7 9 6流图中的循环 9 6 2回边和可归约性回边如果有adomb 那么边b a叫做回边如果流图可归约 则后撤边正好就是回边 9 6流图中的循环 9 6 2回边和可归约性回边如果有adomb 那么边b a叫做回边如果流图可归约 则后撤边正好就是回边 9 6流图中的循环 9 6 2回边和可归约性可归约流图如果把一个流图中所有回边删掉后 剩余的图无环例初始结点是12 3和3 2都不是回边该图不是无环的从结点2和3两处都能进入由它们构成的环 9 6流图中的循环 9 6 3流图的深度深度是在无环路径上的最大回边数深度不大于流图中循环嵌套的层数该例深度为310 7 4 3 9 6流图中的循环 9 6 4自然循环自然循环的性质有唯一的入口结点 叫做首结点 首结点支配该循环中所有结点至少存在一条回边进入该循环首结点回边n d确定的自然循环d加上不经过d能到达n的所有结点结点d是该循环的首结点 9 6流图中的循环 9 6 4自然循环回边10 7循环 7 8 10 回边7 4循环 4 5 6 7 8 10 回边4 3和8 3循环 3 4 5 6 7 8 10 回边9 1 1 2 3 4 5 6 7 8 9 10 9 6流图中的循环 内循环若一个循环的结点集合是另一个循环的结点集合的子集两个循环有相同的首结点 但并非一个结点集是另一个的子集 则看成一个循环 本章要点 1 对各类优化的理解 包括常量合并 公共子表达式删除 复写传播 死代码删除 循环优化等2 到达 定值 活跃变量 可用表达式等几种常用的数据流抽象实例3 把各种数据流模式作为整体来抽象地研究的共同理论框架4 常量传播的特点5 最小化表达式计算次数的一种方法 部分冗余删除方法6 自然循环的概念及自然循环的识别 例题1 unix下的c编译命令cc的选择项g和o的解释如下 其中dbx的解释是 dbxisanutilityforsource leveldebuggingandexecutionofprogramswritteninc 试说明为什么用了选择项g后 选择项o便被忽略 gproduceadditionalsymboltableinformationfordbx 1 anddbxtool 1 andpass lgoptiontold 1 soastoincludetheglibrary thatis usr lib libg a whenthisoptionisgiven the oand roptionsaresuppressed o level optimizetheobjectcode ignoredwheneither g go or aisused 例题2 一个c语言程序如下 右边是优化后的目标代码main pushl ebp movl esp ebpinti j k movl 1 eax j 1i 5 movl 6 edx k 6j 1 l4 while j 100 addl edx eax j j 6k i 1 cmpl 99 eaxj j k jle l4 while j 99 例题2 一个c语言程序如下 右边是优化后的目标代码main pushl ebp movl esp ebpinti j k movl 1 eax j 1i 5 movl 6 edx k 6j 1 l4 while j 100 addl edx eax j j 6k i 1 cmpl 99 eaxj j k jle l4 while j 99 完成了哪些优化 例题2 一个c语言程序如下 右边是优化后的目标代码main pushl ebp movl esp ebpinti j k movl 1 eax j 1i 5 movl 6 edx k 6j 1 l4 while j 100 addl edx eax j j 6k i 1 cmpl 99 eaxj j k jle l4 while j 99 复写传播 常量合并 代码外提 删除无用赋值 对i j和k分配内存单元也成为多余 从而被取消 例题3 一个c语言程序main longi j while i if j i j 生成的汇编码见右边为什么会有连续跳转 pushl ebpmovl esp ebpsubl 8 esp l2 cmpl 0 4 ebp jne l4jmp l3 l4 cmpl 0 8 ebp je l5movl 8 ebp eaxmovl eax 4 ebp l5 jmp l2 l3 例题3 whilee1dos1l2 e1的代码真转l4无条件转l3l4 s1的代码jmpl2l3 ife2thens2e2的代码假转l5s2的代码l5 例题3 whilee1dos1当它们嵌套时 代码结构变成l2 e1的代码l2 e1的代码真转l4真转l4无条件转l3无条件转l3l4 s1的代码l4 e2的代码jmpl2假转l5l3 s2的代码ife2thens2l5 jmpl2e2的代码l3 假转l5s2的代码l5 例题3 whilee1dos1当它们嵌套时 代码结构变成l2 e1的代码l2 e1的代码真转l4真转l4无条件转l3无条件转l3l4 s1的代码l4 e2的代码jmpl2假转l5l3 s2的代码ife2thens2l5 jmpl2e2的代码l3 假转l5s2的代码l5 例题3 whilee1dos1当它们嵌套时 代码结构变成l2 e1的代码l2 e1的代码真转l4真转l4无条件转l3无条件转l3l4 s1的代码l4 e2的代码jmpl2假转l5l3 s2的代码ife2thens2l5 jmpl2e2的代码l3 假转l5s2的代码l5 例题3 whilee1dos1当它们嵌套时 代码结构变成l2 e1的代码l2 e1的代码真转l4真转l4无条件转l3无条件转l3l4 s1的代码l4 e2的代码jmpl2假转l5l3 s2的代码ife2thens2l5 jmpl2e2的代码l3 假转l5s2的代码l5 可优化为假转 例题3 一个c语言程序main lon