第7章 黑底.ppt

求流图中所有结点n 的必经结点集D(n)的算法思想： 结点n∪n 的所有前驱结点的必经结点的交，即如果某结点d是结点n的所有前驱结点的必经结点，则d为n的必经结点。 7.3.2 循环查找 B1 B2 B3 B4 B5 B6 B7 B8 D(B8) = { B1, B2, B7, B8} 流图中各结点的必经结点集： 例 D(B1) = {B1} D(B2) = { B1, B2} D(B3) = { B1, B2, B3} D(B4) = { B1, B2, B3, B4} D(B5) = { B1, B2, B3,B5} D(B6) = { B1, B2, B3, B6} D(B7) = { B1, B2, B7} 求流图中的回边 设a→b是流图中的一条有向边，若b DOM a，则称a→b是流图中的一条回边。 7.3.2 循环查找 流图中的回边： 因为B2 DOM B7，所以B7→B2是流图中的回边，且是流图中的唯一回边。 7.3.2 循环查找 B1 B2 B3 B4 B5 B6 B7 B8 求循环的算法思想： 回边n到d组成的循环: d是循环的入口，n是循环的出口，循环出口n的前驱属于循环，前驱不是d，再求前驱, 直到入口d为止。 7.3.2 循环查找 流图中的循环： 由回边B7→B2组成的循环是{ B2,B3, B4,B5, B6,B7 } 7.3.2 循环查找 B1 B2 B3 B4 B5 B6 B7 B8 窥孔优化方法是一种简单有效地改进代码质量的技术。 主要包括： 删除冗余存取指令 删除不可达代码 控制流优化 强度削弱 删除无用操作 7.4 窥孔优化 本章小结 1. 掌握优化的基本概念 (1) 什么是代码优化 (2) 什么是局部优化、循环优化 本章小结 局部优化 是指局限于程序基本块范围内的一种优化。 局部优化包括: 合并已知量 删除公共子表达式(删除多余的运算) 删除无用赋值 本章小结 循环优化 是指对循环中的代码进行优化。 循环优化包括: 代码外提 删除归纳变量 强度削弱 本章小结 (1) 划分基本块的方法 2. 利用DAG实现局部优化 (2) 基本块 DAG 还原 本章小结 3. 循环查找 求流图中所有结点n 的必经结点 集D(n) (2) 求流图中的回边 (3) 根据回边求循环 本章小结 例1 试对下面基本块进行优化 X=B*C Y=B/C Z=X+Y W=9*Z G=B*C T=G*G W=T*G L=W M=L 1. 应用DAG对该基本块进行优化,给出优化后的语句序列 2. 给出当只有L在基本块出口后为活跃时的优化结果 n1 B n2 C n3 X, * n9 W, * L, G M n4 Y / 本章小结 n5 Z + n6 9 n7 W T n8 * * X=B*C Y=B/C Z=X+Y W=9*Z G=B*C T=G*G W=T*G L=W M=L — 本章小结 X=B*C G=X Y=B/C Z=X+Y T=G*G W=T*G L=W M=L n1 B n2 C n3 X, * n9 W, * L, G M n4 Y / n5 Z + n6 9 n7 W T n8 * * — 按照构造DAG结点 次序重写四元式序列 本章小结 G=B*C T=G*G L=T*G 优化后的语句序列: X=B*C G=X Y=B/C Z=X+Y T=G*G W=T*G L=W M=L 又因为只有L在基本块出口后为活跃, 即只有L在基本块出口处要引用, 因此其他变量赋值语句可删去, 其优化结果为: 例2 设有如左图所示的程序流图: 1 3 4 6 5 7 8 2 求流图中各结点 n 的 必经结点集D(n) (2) 求出该流图中的回边 (3) 求出该流图中的循环 D(1)={1} D(2)={1, 2} D(3)={1, 2, 3} D(4)={1, 2, 4} D(5)={1, 2, 4, 5} D(6)={1, 2, 4, 6} D(7)={1, 2, 4, 7} D(8)={1, 2, 4, 7, 8} 7→2为回边 3不是6的必经结点 4不是2的必经结点 回边组成的循环 : {2, 3, 4, 5, 6, 7} 1 3 4 6 5 7 8 2 2是7的必经结点 7.1 优化概述 (1) S=0 I=1× (4) T2=addr(A)－4 (7) T5=addr(B)－4 (3) T1=4 (5) T3=T2[T1] (6) T4=T1× (8) T6=T5[T1] (9) T7=T3*T6 (10) S=S+T7 I=I+1