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

《编译原理独立于机器的优化9.ppt》由会员分享，可在线阅读，更多相关《编译原理独立于机器的优化9.ppt（134页珍藏版）》请在三一文库上搜索。

1、第九章 独立于机器的优化,通过程序变换（局部变换和全局变换）来改 进程序，称为优化 代码改进变换的标准 代码变换必须保程序的含义 采取安全稳妥的策略 变换减少程序的运行时间平均达到一个可度量的值 变换所作的努力是值得的,第九章 独立于机器的优化,本章介绍独立于机器的优化，即不考虑任何依赖目标机器性质的优化变换 通过实例来介绍代码改进的主要机会 数据流分析包括的几类重要的全局收集的信息 数据流分析的一般框架 和一般框架有区别的常量传播 部分冗余删除的优化技术 循环的识别和分析,9.1 优化的主要种类,9.1.1 优化的主要源头 程序中存在许多程序员无法避免的冗余运算 通过像Aij和X.f1的方式

2、引用数组元素和结构的域 随着程序被编译，对这样高级数据结构的访问展开成多步低级算术运算 对同一个数据结构的多次访问导致许多公共的低级运算 程序员没有办法删除这些冗余,9.1 优化的主要种类,9.1.2 一个实例 i = m 1; j = n; v = an; (1) i = m 1 while (1) (2) j = n do i = i +1; while(aiv); (4) v = at1 if (i = j) break; (5) i = i + 1 x=ai; ai=aj; aj=x; (6) t2 = 4 i (7) t3 = at2 x=ai; ai=an; an=x; (8) i

3、f t3 v goto (5),9.1 优化的主要种类,9.1.2 一个实例 i = m 1; j = n; v = an; (9) j = j 1 while (1) (10) t4 = 4 j do i = i +1; while(aiv); (12) if t5v goto (9) if (i = j) break; (13) if i =j goto (23) x=ai; ai=aj; aj=x; (14) t6 = 4 i (15 ) x = at6 x=ai; ai=an; an=x; . . .,9.1 优化的主要种类,9.1 优化的主要种类,9.1.3 公共子表达式删除 B5

4、x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,9.1 优化的主要种类,B5 x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,t6 = 4 i x = at6 t8 = 4 j t9 = at8 at6 = t9 at8 = x goto B2,9.1 优化的主要种类,9.1 优化的主要种类,B5

5、x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,t6 = 4 i x = at6 t8 = 4 j t9 = at8 at6 = t9 at8 = x goto B2,9.1 优化的主要种类,B5 x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,t6 = 4 i x = at6 t8 = 4 j t

6、9 = at8 at6 = t9 at8 = x goto B2,x = at2 t9 = at4 at2 = t9 at4 = x goto B2,9.1 优化的主要种类,9.1 优化的主要种类,B5 x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,t6 = 4 i x = at6 t8 = 4 j t9 = at8 at6 = t9 at8 = x goto B2,x = at2 t9 = at4 at2 = t9 at4 = x goto

7、B2,9.1 优化的主要种类,B5 x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,t6 = 4 i x = at6 t8 = 4 j t9 = at8 at6 = t9 at8 = x goto B2,x = at2 t9 = at4 at2 = t9 at4 = x goto B2,x = t3 at2 = t5 at4 = x goto B2,9.1 优化的主要种类,B6 x = ai; ai = an; an = x;,t11 = 4 i

8、 x = at11 t12 = 4 i t13 = 4 n t14 = at13 at12 = t14 t15 = 4 n at15 = x,x = t3 t14 = at1 at2 = t14 at1 = x,9.1 优化的主要种类,B6 x = ai; ai = an; an = x; at1能否作为公共子表达式？,t11 = 4 i x = at11 t12 = 4 i t13 = 4 n t14 = at13 at12 = t14 t15 = 4 n at15 = x,x = t3 t14 = at1 at2 = t14 at1 = x,9.1 优化的主要种类,9.1 优化的主要种类,

9、9.1.4 复写传播 形成为f = g的赋值叫做复写语句 优化过程中会大量引入复写,9.1 优化的主要种类,9.1.4 复写传播 形成为f = g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换的做法是在复写语句f = g后，尽可能用g代表f,x = t3 at2 = t5 at4 = t3 goto B2,x = t3 at2 = t5 at4 = x goto B2,9.1 优化的主要种类,9.1.4 复写传播 形成为f = g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换的做法是在复写语句f = g后，尽可能用g代表f 复写传播变换本身并不是优化，但它给其它优化带来

10、机会 常量合并 死代码删除,9.1 优化的主要种类,9.1.5 死代码删除 死代码是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码 例： debug = true; debug = false; . . . 测试后改成 . . . if (debug) print if (debug) print ,9.1 优化的主要种类,9.1.5 死代码删除 死代码是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码 例：复写传播可能会引起死代码删除,x = t3 at2 = t5 at4 = t3 goto B2,at2 = t5 at4 = t3 goto B2,9.1 优化的主要

11、种类,9.1.6 代码外提 代码外提是循环优化的一种 循环优化的其它重要技术 归纳变量删除 强度削弱 例：while (i = limit 2 ) 变换成 t = limit 2; while (i = t ) ,9.1 优化的主要种类,9.1.7 强度削弱和归纳变量删除 j和t4的值步伐一致地变化 这样的变量叫做归纳变量 在循环中有多个归纳变量时， 也许只需要留下一个 这个操作由归纳变量删除 过程来完成 对本例可以先做强度削弱 它给删除归纳变量创造机会,9.1 优化的主要种类,j = j 1 t4 = 4 j t5 = at4 if t5 v goto B3,B3,除第一次外， t4 = 4

12、 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是先于一个语句的点，pi1是同一块中位于该语句后的点，或者 pi是某块的结束点，pi1是后继块的开始点,9.2 数据流分析介绍,9.2.1 数据流抽象 路径实例 -（1, 2, 3, 4, 9） -（1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 9）,9.

13、2 数据流分析介绍,9.2.1 数据流抽象 分析程序的行为时，必须在其流图上考虑所有的执行路径（在调用或返回语句被执行时，还需要考虑路径在多个流图之间的跳转） 然后从每个程序点的所有可能状态中抽取解决特定数据流分析所需信息 通常，从流图得到的程序执行路径数无限，且执行路径长度没有有限的上界 程序分析从程序点的所有可能状态中为该点总结出一组有限的事实,9.2 数据流分析介绍,9.2.1 数据流抽象 明了所有路径上所有程序状态是不可能的 数据流分析不打算区分到达一个程序点的不同路径，也不试图掌握完整的状态 它抽取出某些细节，以获取用于分析目的的数据 从同样的状态，根据程序分析的不同目的，可以提炼出

14、不同的信息,9.2 数据流分析介绍,9.2.1 数据流抽象 点(5)所有程序状态： - a 1, 243 - 由d1, d3定值 1、到达定值 - d1, d3的定值 到达点(5) 2、常量合并 - a在点(5)不是 常量,9.2 数据流分析介绍,9.2.2 数据流分析模式 数据流值 数据流分析总把程序点和数据流值联系起来 数据流值代表在程序点能观测到的所有可能程序状态集合的一个抽象 语句s前后两点数据流值用INs和OUTs来表示 数据流问题就是通过基于语句语义的约束（迁移函数）和基于控制流的约束来寻找所有语句s的INs和OUTs 的一个解,9.2 数据流分析介绍,9.2.2 数据流分析模式

15、迁移函数 f 语句前后两点的数据流值受该语句的语义约束 沿执行路径正向传播 OUTs = fs(INs) 沿执行路径逆向传播 INs = fs(OUTs) 基本块B由语句s1, s2, , sn依次组成 INsi+1 = OUTsi, i = 1, 2, , n1 fB = fn . . . f2 f1 (逆向 fB = f1 . . . fn - 1 fn ) OUTB = fB (INB) (逆向 INB = fB (OUTB) ),9.2 数据流分析介绍,9.2.2 数据流分析模式 控制流约束 正向传播 INB = P是B的前驱OUTP 逆向转播 OUTB = S是B的后继INS 约束方

16、程组通常不是唯一解 求解的目标是要找到满足这两组约束（控制流约束和迁移约束）的最“精确”解,9.2 数据流分析介绍,9.2.3 到达-定值 到达程序点的所有定值 可用来判断一个变量在某程序点是否为常量 可用来判断一个变量在某程序点是否无初值 别名给到达-定值的计算带来困难 过程参数、数组访问、间接引用等都可能引起别名 如何判断对p-next的赋值没有改变q-next 程序分析必须是稳妥的 本章其余部分仅考虑变量无别名的情况,9.2 数据流分析介绍,9.2.3 到达-定值 到达程序点的所有定值 可用来判断一个变量在某程序点是否为常量 可用来判断一个变量在某程序点是否无初值 别名给到达-定值的计算

17、带来困难 注销 在一条路径上，先前对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 = k

18、ill1 kill2 killn genB = genn (genn1 killn) (genn2 killn1 killn) (gen1 kill2 kill3 killn),9.2 数据流分析介绍,到达-定值的数据流等式 genB：B中能到达B的结束点的定值语句 killB：整个程序中决不会到达B结束点的定值 inB：能到达B的开始点的定值集合 outB：能到达B的结束点的定值集合 两组等式（根据gen和kill定义in和out） inB = P是B的前驱 outP outB = genB (inB killB) outENTRY = 到达-定值方程组的迭代求解,9.2 数据流分析介绍,i

19、n B out B B1 000 0000 000 0000 B2 000 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000,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 B1 000 0000 000 0000 B2 000 0000 000 0000 B3 000

20、0000 000 0000 B4 000 0000 000 0000,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 B1 000 0000 111 0000 B2 000 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000,gen B1 = d1, d2, d3 kill

21、 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 B1 000 0000 111 0000 B2 111 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen

22、 B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,9.2 数据流分析介绍,in B out B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 000 0000 000 0000 B4 000 0000 000 0000,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 数据流分

23、析介绍,in B out B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 0000 B4 000 0000 000 0000,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 B1 000 0000 111 0000 B2 111 0000 001 1100 B3

24、 001 1100 000 1110 B4 000 0000 000 0000,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 B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 1110 B4 001 1110 000 0000,gen B1 = d1, d2, d3

25、 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 B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d

26、7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,9.2 数据流分析介绍,in B out B B1 000 0000 111 0000 B2 111 0111 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111,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

27、 数据流分析介绍,in B out B B1 000 0000 111 0000 B2 111 0111 001 1110 B3 001 1100 000 1110 B4 001 1110 001 0111,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 B1 000 0000 111 0000 B2 111 0111 001 11

28、10 B3 001 1110 000 1110 B4 001 1110 001 0111 不再继续计算,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) 另一类数据流等式的合

29、流算符是求交集,9.2 数据流分析介绍,9.2.4 活跃变量 定义 x的值在p点开始的路径上被引用，则说x在p点活跃，否则称x在p点是死亡的 in B：块B开始点的活跃变量集合 outB：块B结束点的活跃变量集合 useB：块B中有引用且在引用前无定值的变量集 defB：块B中有定值的变量集 应用 一种重要应用就是基本块的寄存器分配,9.2 数据流分析介绍,9.2.4 活跃变量 例 useB2 = i, j defB2 = i, j ,9.2 数据流分析介绍,9.2.4 活跃变量 活跃变量数据流等式 in B = useB (out B defB ) outB = S是B的后继 in S in

30、 EXIT = 和到达定值等式之间的联系与区别 都以集合并算符作为它们的汇合算符 信息流动方向相反，IN和OUT的作用相互交换 use和def分别代替gen和kill，最小解代替最大解,9.2 数据流分析介绍,9.2.5 可用表达式 x = y + z x = y + z x = y + z . . . . y = z = . . . p p p y + z 在p点 y + z 在p点 y + z 在p点 可用 不可用 不可用,9.2 数据流分析介绍,9.2.5 可用表达式,9.2 数据流分析介绍,9.2.5 可用表达式 定义 若到点p的每条路径都计算x + y，并且计算后没有对x或y赋值，那

31、么称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 数据流分析介绍,

32、9.2.6 小结 三个数据流问题 到达定值、活跃变量、可用表达式 每个问题的组成 数据流值的论域、数据流的方向、迁移函数、边界条件、汇合算符、数据流等式 见书上表9.2,9.3 数据流分析的基础,本节内容 1、把各种数据流模式作为一个整体抽象地研究 2、形式地回答数据流算法的下列几个基本问题 在什么情况下数据流分析中使用的迭代算法是正确的 迭代算法所得解的精度如何 迭代算法是否收敛 数据流方程的解的含义是什么,9.3 数据流分析的基础,数据流分析框架(D, V, , F)包括 数据流分析的方向D，它可以是正向或逆向 数据流值的论域 半格V、汇合算子 V到V的迁移函数族F 包括适用于边界条件（E

33、NTRY和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并且

34、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是顶元， 是底元，对应二元关系是 数据流方程组通常有很多解，但是按偏序意义上的最大解是最精确的 到达定值：最精确的解含最少定

35、值 可用表达式：最精确的解含最多表达式,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有一个恒等函数I F封闭于复合 若F中所有函数f 都有单

36、调性，即 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

37、 (y K) (G (z K),9.3 数据流分析的基础,9.3.3 一般框架的迭代算法 以正向数据流分析为例 (1) OUTENTRY = vENTRY; (2) for (除了ENTRY以外的每个块B) OUTB =; (3) while (任何一个OUT出现变化) (4) for (除了ENTRY以外的每个块B) (5) INB = /P是B的前驱 OUTP; (6) OUTB = fB(INB); (7) ,9.3 数据流分析的基础,9.3.3 一般框架的迭代算法 算法的一些可以证明的性质 如果算法收敛，则结果是数据流方程组的一个解 如果框架单调，则所求得的解是数据流方程组的最大不动点

38、 如果框架单调并且半格的高度有限，那么可以保证算法收敛,9.3 数据流分析的基础,9.3.4 数据流解的含义 结论：算法所得解是理想解的稳妥近似 理想解所考虑的路径 执行路径集：流图上每一条路径都属于该集合 若流图有环，则执行路径数是无界的 程序可能的执行路径集：程序执行所走的路径属于该集合 理想解所考虑的路径 程序可能的执行路径集 执行路径集 寻找所有可能执行路径是不可判定的 讨论正向数据流分析,9.3 数据流分析的基础,9.3.4 数据流解的含义 理想解 若路径P = ENTRY B1 B2 Bk，定义 fP fk1 f2 f1 IDEALB = /P是从ENTRY到B的一条可能路径 fP

39、(vENTRY) 有关理解解的结论 任何大于理想解IDEAL的回答一定是不对的 任何小于或等于IDEAL的值是稳妥的 在稳妥的值中，越接近IDEAL的值越精确,9.3 数据流分析的基础,9.3.4 数据流解的含义 执行路径上的解（meet over paths） MOPB = /P是从ENTRY到B的一条路径 fP(vENTRY) MOP解不仅汇集了所有可能路径的数据流值，而且还包括了那些不可能被执行路径的数据流值 对所有的块B，MOPB IDEALB，简写成MOP IDEAL MOP的定义并没有通向一个直接算法,9.3 数据流分析的基础,9.3.4 数据流解的含义 先前算法得到的最大不动点解

40、MFP 不是先找出到达一个块的所有路径，然后用汇合运算，而是 访问每个基本块，并且不一定按照程序执行时的次序 在每个汇合点，把汇合运算作用在到目前为止得到的数据流值上，其中所用一些初值是人工引入的,9.3 数据流分析的基础,9.3.4 数据流解的含义 MFP与MOP的联系 MFP访问块未必遵循次序 由初值和单调性保证一致 MFP较早地使用汇合运算 MOPB4 = (f3 f1) (vENTRY) (f3 f2) (vENTRY) INB4 = f3(f1(vENTRY) f2(vENTRY) 数据流分析框架具有分配性时，结果是一样的 MFP MOP IDEAL,9.4 常 量 传 播,9.4.

41、1 常量传播框架的数据流值 单个变量的数据流值半格 变量的类型所允许的所有常量 值NAC表示不是常量 值UNDEF表示没有定义 程序中各变量的 半格的积 把程序中每个变量映射到 该半格上的一个值,9.4 常 量 传 播,9.4.2 常量传播框架的迁移函数 令fs是语句s的迁移函数，m = fs(m)，用m和m之 间的联系来表达fs 1、如果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，若

42、m(y)或m(z)是NAC m(x) = UNDEF， 否则,9.4 常 量 传 播,9.4.3 常量传播框架的单调性 m(y) m(z) m(x) UNDEF UNDEF UNDEF c2 UNDEF NAC NAC UNDEF UNDEF c1 c2 c1 + c2 NAC NAC UNDEF NAC NAC c2 NAC NAC NAC,除了s的右部是y + z 这种情况外，其它所 有情况，fs不改变m(x) 的值，或者改变到返 回一个常量 在这些情况下，fs 肯定是单调的,9.4 常 量 传 播,9.4.4 常量传播框架的非分配性 不管取什么路径，在块B3的出口， z的值是5 迭代算法

43、在块B3的入口而 不是出口使用汇合运算 f3(f1(m0) f2(m0) f3(f1(m0) f3(f2(m0) 这个结果虽不精确， 但是安全的,9.4 常 量 传 播,9.4.5 结果的解释 ENTRY块置初值UNDEF 其它块置初值UNDEF x在块B4入口是10 块B5的x引用可以用10代替 和执行路径B1 B3 B4 B5不符 若程序正确的话， 认为x在块B5入口的值 只能为10是合适的,9.5 部 分 冗 余 删 除,内容简介 冗余计算以公共子表达式的形式出现，或以循环不变表达式的形式出现 冗余可能只出现在一部分路径上 讨论最小化x + y这样表达式的计算次数的方法 策略是，一个计算

44、尽量不做，除非它不得不做 首先讨论冗余的不同形式，以建立直观认识，然后描述广义的冗余删除问题，最后提出算法 算法涉及到求解多个正向或逆向的数据流问题,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 惰