编译原理独立于机器的优化学习培训模板课件

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 1while (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) if t3 v goto (5)9

3、.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 = at6x=ai; ai=an; an=x;. . .9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3

4、v goto B3if i = j goto B6B4B3B5B69.1 优化的主要种类9.1.3 公共子表达式删除B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 = xgoto B29.1 优化的主要种类B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 = xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 =

5、xgoto B29.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B69.1 优化的主要种类B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 = xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 = xgoto B29.1 优化的主要种类B5 x=ai; ai=aj; aj=x;t

6、6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 = xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 = xgoto B2x = at2t9 = at4at2 = t9at4 = xgoto B29.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B69.1 优化的主要种类B5 x=ai; ai=aj; aj=x;t6 =

7、4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 = xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 = xgoto B2x = at2t9 = at4at2 = t9at4 = xgoto B29.1 优化的主要种类B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 = xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9

8、at8 = xgoto B2x = at2t9 = at4at2 = t9at4 = xgoto B2x = t3at2 = t5at4 = xgoto B29.1 优化的主要种类B6 x = ai; ai = an; an = x;t11 = 4 ix = at11t12 = 4 i t13 = 4 nt14 = at13at12 = t14t15 = 4 n at15 = x x = t3t14 = at1at2 = t14at1 = x 9.1 优化的主要种类B6 x = ai; ai = an; an = x;at1能否作为公共子表达式？t11 = 4 ix = at11t12 = 4

9、 i t13 = 4 nt14 = at13at12 = t14t15 = 4 n at15 = x x = t3t14 = at1at2 = t14at1 = x 9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6把at1作为公共子表达式是不稳妥的 9.1 优化的主要种类9.1.4 复写传播形成为f = g的赋值叫做复写语句优化过程中会大量引入复写t = d + ea = t 删除局部公共子表达式期间引进复写t = d + eb = tc

10、= tc = d + eb = d + ea = d + e9.1 优化的主要种类9.1.4 复写传播形成为f = g的赋值叫做复写语句优化过程中会大量引入复写复写传播变换的做法是在复写语句f = g后，尽可能用g代表fx = t3at2 = t5at4 = t3goto B2x = t3at2 = t5at4 = xgoto B29.1 优化的主要种类9.1.4 复写传播形成为f = g的赋值叫做复写语句优化过程中会大量引入复写复写传播变换的做法是在复写语句f = g后，尽可能用g代表f复写传播变换本身并不是优化，但它给其它优化带来机会常量合并死代码删除9.1 优化的主要种类9.1.5 死代

11、码删除死代码是指计算的结果决不被引用的语句一些优化变换可能会引起死代码例：debug = true; debug = false;. . . 测试后改成 . . .if (debug) print if (debug) print 9.1 优化的主要种类9.1.5 死代码删除死代码是指计算的结果决不被引用的语句一些优化变换可能会引起死代码例：复写传播可能会引起死代码删除x = t3at2 = t5at4 = t3goto B2at2 = t5at4 = t3goto B29.1 优化的主要种类9.1.6 代码外提代码外提是循环优化的一种循环优化的其它重要技术归纳变量删除强度削弱例：while

12、(i = limit 2 ) 变换成t = limit 2;while (i v goto B3B39.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1B1B2j = j 1t4 = t4 4t5 = at4if t5 v goto B3B4B3B5B6t4 = 4 jif i = j goto B6j = j 1t4 = 4 jt5 = at4if t5 v goto B3B3除第一次外，t4 = 4 j在B3的入口一定保持在j = j 1后，关系t4 = 4 j + 4也保持9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1i = i +

13、1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6B2也可以进行类似的变换循环控制条件可以用t2和t4来表示9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1t2 = 4 it4 = 4 jt2 = t2 + 4t3 = at2if t3 v goto B3if t2 = t4 goto B6at2 = t5at4 = t3goto B2B4B3B5t14 = at1at2 = t14at1 = t3B69.2 数据流分析介绍9.2.1 数据流抽象点基本块中，两个相邻的语句之间为程序的一个点基本块的开始点和

14、结束点路径点序列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） B1(1)d2: b = ad3: a = 243 goto B3B4B2B3if read()=0 goto B4d1: a = 1(2)(3)(4)(5)(6)(7)(8)(9)9.2 数据流分析介绍9.2.1 数据流抽象 分析程序的行为时，必须在其流图上考虑

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

16、1, 243 - 由d1, d3定值1、到达定值 - d1, d3的定值 到达点(5)2、常量合并 - a在点(5)不是 常量B1(1)d2: b = ad3: a = 243 goto B3B4B2B3if read()next的赋值没有改变q-next 程序分析必须是稳妥的 本章其余部分仅考虑变量无别名的情况9.2 数据流分析介绍9.2.3 到达-定值到达程序点的所有定值 可用来判断一个变量在某程序点是否为常量 可用来判断一个变量在某程序点是否无初值别名给到达-定值的计算带来困难注销 在一条路径上，先前对x的赋值被后面对x的赋值所注销9.2 数据流分析介绍gen和kill分别表示基本块生成

17、和注销的定值d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d49.2 数据流分析介绍基本块的gen和kill是怎样计算的对三地址指令 d: u = v + w，它的迁移函数是 fd(x) = gend (x killd)若f1(x)

18、= 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 killn genB = genn (genn1 killn) (genn2 killn1 killn) (gen1 kill2 kill3 killn) 9.2 数据流分析介绍到达-定值的数据流等式 genB：B中能到达B的结束点的定值语句 killB：整个程序中决不会到达B结束点的定值 inB：能

19、到达B的开始点的定值集合 outB：能到达B的结束点的定值集合两组等式（根据gen和kill定义in和out） inB = P是B的前驱 outP outB = genB (inB killB) outENTRY = 到达-定值方程组的迭代求解9.2 数据流分析介绍 in B out B B1 000 0000 000 0000 B2 000 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2

20、, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B1 000 0000 000 0000 B2 000 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5ki

21、ll B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B1 000 0000 111 0000 B2 000 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen

22、 B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B1 000 0000 111 0000 B2 111 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000gen B1 = d1, d2, d3kill B1=d4,

23、 d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 000 0000 000 0000 B4 000 0000 000 0000gen B1 = d1, d2,

24、 d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 0000 B4 000 0000 000 0000ge

25、n B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 1110 B4 000 0

26、000 000 0000gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000

27、 1110 B4 001 1110 000 0000gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B1 000 0000 111 0000 B2 111 0000 001 1100 B

28、3 001 1100 000 1110 B4 001 1110 001 0111gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B1 000 0000 111 0000 B2 111 0

29、111 001 1100 B3 001 1100 000 1110 B4 001 1110 001 0111gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B1 000 0000 111

30、 0000 B2 111 0111 001 1110 B3 001 1100 000 1110 B4 001 1110 001 0111gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍 in B out B B

31、1 000 0000 111 0000 B2 111 0111 001 1110 B3 001 1110 000 1110 B4 001 1110 001 0111不再继续计算gen B1 = d1, d2, d3kill B1=d4, d5, d6, d7gen B2 = d4, d5kill B2 = d1, d2, d7gen B3 = d6kill B3 = d3gen B4 = d7kill B4 = d1, d4d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2

32、数据流分析介绍到达-定值等式是正向的方程 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开始点的活跃变量集合 outB：块B结束点的活跃变量集合 useB：块B中有引用且在引用前无定值的变量集 defB：块B中有定值的变量集应用 一种重要应用就是基本块的寄存器分配9.2 数据流分析介绍9.2.4 活跃变量例 useB2 =

33、i, j defB2 = i, j d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B39.2 数据流分析介绍9.2.4 活跃变量活跃变量数据流等式 in B = useB (out B defB ) outB = S是B的后继 in S in EXIT = 和到达定值等式之间的联系与区别 都以集合并算符作为它们的汇合算符 信息流动方向相反，IN和OUT的作用相互交换 use和def分别代替gen和kill，最小解代替最大解9.2 数据流分析介绍9.2.5 可用表达式 x = y +

34、 z x = y + z x = y + z . . . . y = z = . . . p ppy + z 在p点 y + z 在p点 y + z 在p点可用不可用不可用9.2 数据流分析介绍9.2.5 可用表达式t1 = 4i?t2 = 4iB1B2B3t1 = 4ii =t0 = 4it2 = 4iB1B2B39.2 数据流分析介绍9.2.5 可用表达式定义 若到点p的每条路径都计算x + y，并且计算后没有对x或y赋值，那么称x + y在点p可用e_genB：块B产生的可用表达式集合e_killB：块B注销的可用表达式集合 in B： 块B入口的可用表达式集合out B：块B出口的可用

35、表达式集合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) B1B2O j+1 = G (I j K)I j+1 = out B1 O j+1I 0 = I 0 = UO 1 = G O 1 = U KI 1 = out B1 G I 1 = out B1 KO 2

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

37、 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

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

39、的解含最少定值 可用表达式：最精确的解含最多表达式 9.3 数据流分析的基础9.3.1 半格格图 这是一个格，本课程用半格概念就够了 是x y的最大下界 x y d1d2d3d1, d2d1, d3d2, d3d1, d2, d3( )( )9.3 数据流分析的基础9.3.1 半格积半格（定义略）上例数据流值的集合是定值集合的幂集 可以用从每个变量的一个简单半格构造出的积半格来表示整个定值半格半格的高度 上升链是序列x1 x2 xn 半格的高度就是其中最长上升链中的个数 若半格的高度有限，证明数据流分析迭代算法的收敛则非常容易9.3 数据流分析的基础9.3.2 迁移函数迁移函数族F : V V

40、有下列性质 F有一个恒等函数I F封闭于复合 若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)的形式分配性可以

41、由检查下面的条件得到 G (y z) K) = (G (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 一般框架的迭代算法算法的一些可以证明的性质 如果算法收敛，则结果是数据流方程组的一个解 如果框架单调，则所求得的

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

43、 fP(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 数据流解的含义先前算法得到的最大不动点解MFP 不

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

45、 常量传播框架的数据流值单个变量的数据流值半格 变量的类型所允许的所有常量 值NAC表示不是常量 值UNDEF表示没有定义程序中各变量的半格的积把程序中每个变量映射到 该半格上的一个值 UNDEFNAC 3 2 1 0 1 2 3 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)都是常量值

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

47、合运算 f3(f1(m0) f2(m0) f3(f1(m0) f3(f2(m0) 这个结果虽不精确，但是安全的B1EXITz = x + yx = 2y = 3B3B2x = 3y = 29.4 常 量 传 播9.4.5 结果的解释ENTRY块置初值UNDEF 其它块置初值UNDEFx在块B4入口是10块B5的x引用可以用10代替和执行路径B1 B3 B4 B5不符若程序正确的话，认为x在块B5入口的值只能为10是合适的 if Q goto B2B1B2B4B3x = 10if Q goto B5B5B7B6 = x9.5 部 分 冗 余 删 除内容简介 冗余计算以公共子表达式的形式出现，或以

48、循环不变表达式的形式出现 冗余可能只出现在一部分路径上 讨论最小化x + y这样表达式的计算次数的方法 策略是，一个计算尽量不做，除非它不得不做 首先讨论冗余的不同形式，以建立直观认识，然后描述广义的冗余删除问题，最后提出算法 算法涉及到求解多个正向或逆向的数据流问题9.5 部 分 冗 余 删 除9.5.1 冗余的根源公共子表达式B1B2B4B3b = 7d = b + ca = b + ce = b + cB1B2B4B3b = 7t = b + cd = tt = b + ca = te = t9.5 部 分 冗 余 删 除9.5.1 冗余的根源完全冗余块B4的表达式b + c是完全冗余的

49、，因为所有到达B4的路径都计算b + c ，并且b和c都未重新定值B2和B3的出边的集合形成一个割集，若把该割集删掉，则从起点到B4的路径都被割断 B1B2B4B3b = 7d = b + ca = b + ce = b + c9.5 部 分 冗 余 删 除9.5.1 冗余的根源循环不变表达式a = b + ct = b + ca = t9.5 部 分 冗 余 删 除9.5.1 冗余的根源部分冗余表达式B1B2B4B3a = b + cd = b + cB1B2B4B3t = b + ct = b + ca = td = t9.5 部 分 冗 余 删 除9.5.1 冗余的根源放置b + c的副

50、本来使B4中的b + c完全冗余 B1B2B4B3a = b + cd = b + cB1B2B4B3t = b + ct = b + ca = td = t9.5 部 分 冗 余 删 除9.5.2 能否删除所有的冗余B3 B4是一条关键边：源结点有多个后继目标结点有多个前驱B1B2B3B4d = b + ca = b + cB5B1B2B3B6t = b + ct = b + ca = tB5d = tB4增加新块9.5 部 分 冗 余 删 除复制代码以删除冗余 B1B2B3B4a = b + cB5B6B7d = b + cB1B2B3B4t = b + ca = tB4B5d = td

51、= b + cB6B6B79.5 部 分 冗 余 删 除9.5.3 惰性代码移动问题部分冗余删除算法优化后程序具有下列性质无需通过复制代码就可删除的冗余计算都被删除 若是部分冗余，则通过放置副本形成完全冗余 优化后程序不会执行原来程序中没有的任何计算 表达式的计算尽可能推迟 尽可能延迟值的计算就是最小化它的生存期，也就是最小化它占用寄存器的时间9.5 部 分 冗 余 删 除9.5.4 预期表达式 预期的不可用的B1 B2B5 B4c = 2 B3B6B7d = b + ca = b + ce = b + cB8B9B10B11 b + c部分冗余 不可能提前到B1计算 B5的计算不能再推迟 添

52、加的计算最迟放在B49.5 部 分 冗 余 删 除9.5.4 预期表达式 预期的不可用的B1 B2B5 B4c = 2 B3B6B7t = b+cd = tt = b + ca = te = tB8B9B10B11 b + c部分冗余 不可能提前到B1计算 B5的计算不能再推迟 添加的计算最迟放在B4 期望的优化结果如图9.5 部 分 冗 余 删 除9.5.4 预期表达式 预期的不可用的B1 B2B5 B4c = 2 B3B6B7d = b + ca = b + ce = b + cB8B9B10B11表达式b + c在点p被预期，若所有从p开始的路径上都从p点可用的b和c来计算表达式b +

53、c的值b + c被块B3，B4，B5，B6，B7和B9预期 9.5 部 分 冗 余 删 除9.5.5 惰性代码移动算法预期的不可用的B1 B2B5 B4c = 2 B3B6B7d = b + ca = b + ce = b + cB8B9B10B111、使用预期来决定表达式可以放置的位置 可以建立数据流方程来求解预期表达式9.5 部 分 冗 余 删 除9.5.5 惰性代码移动算法预期的不可用的B1 B2B5 B4c = 2 B3B6B7d = b + ca = b + ce = b + cB8B9B10B112、表达式的副本被放置到该表达式最早被期望的程序点(B3, B5) 需要定义可用表达式

54、数据流问题 表达式在点p可用，若在到达p的所有路径上它都被期望 9.5 部 分 冗 余 删 除9.5.5 惰性代码移动算法3、在保语义且最小化冗余前提下，尽可能延迟表达式的计算 放置在从可延迟到不可延迟的边界上(B4, B5) 需要定义可延迟表达式数据流问题最早的可延迟的B1 B2B5 B4c = 2 B3B6B7d = b + ca = b + ce = b + cB8B9B10B119.5 部 分 冗 余 删 除9.5.5 惰性代码移动算法4、确定表达式被引用的位置，以便改成引用临时变量 需要定义引用表达式数据流问题，类似于活跃变量分析最早的可延迟的B1 B2B5 B4c = 2 B3B6

55、B7d = b + ca = b + ce = b + cB8B9B10B119.5 部 分 冗 余 删 除9.5.5 惰性代码移动算法实施该算法后的结果最早的可延迟的B1 B2B5 B4c = 2 B3B6B7t = b+cd = tt = b + ca = te = tB8B9B10B119.6 流图中的循环标识循环并对循环专门处理的重要性 程序执行的大部分时间消耗在循环上，改进循环性能的优化会对程序执行产生显著影响 循环也会影响程序分析的运行时间本节内容介绍概念：支配结点、深度优先排序、回边、图的深度和可归约性 用于寻找循环和迭代数据流分析收敛速度的讨论9.6 流图中的循环9.6.1 支

56、配结点结点d是结点n的支配结点，如果从初始结点起，每条到达n的路径都要经过d，写成d dom n 每个结点是它本身的支配结点 循环的入口是循环中所有结点的支配结点123456789109.6 流图中的循环1234567891012345678910深度优先生成树9.6 流图中的循环9.6.2 回边和可归约性深度优先生成树 前进边 后撤边4 3、7 4、10 7、8 3和9 1 交叉边2 3和5 7 123456789109.6 流图中的循环9.6.2 回边和可归约性回边如果有a dom b ，那么边b a叫做回边如果流图可归约，则后撤边正好就是回边123456789109.6 流图中的循环9.

57、6.2 回边和可归约性回边如果有a dom b ，那么边b a叫做回边如果流图可归约，则后撤边正好就是回边123456789109.6 流图中的循环9.6.2 回边和可归约性可归约流图 如果把一个流图中所有回边删掉后，剩余的图无环例初始结点是12 3和3 2都不是回边该图不是无环的从结点2和3两处都能进入由它们构成的环 3219.6 流图中的循环9.6.3 流图的深度深度是在无环路径上的最大回边数深度不大于流图中循环嵌套的层数该例深度为310 7 4 3123456789109.6 流图中的循环9.6.4 自然循环自然循环的性质 有唯一的入口结点，叫做首结点，首结点支配该循环中所有结点 至少存

58、在一条回边进入该循环首结点回边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 11, 2, 3, 4, 5, 6, 7, 8, 9, 10123456789109.6 流图中的循环内循环 若一个循环的结点集合是另一个循环的结点集合的子集两个循环有相同的首结点,但并非一个结点集是另一个的子集，则看成一个循环 1 2 3 4本 章 要 点1、对各类优化的理解，包括常量合并、公共

59、子表达式删除、复写传播、死代码删除、循环优化等2、到达定值、活跃变量、可用表达式等几种常用的数据流抽象实例3、把各种数据流模式作为整体来抽象地研究的共同理论框架4、常量传播的特点5、最小化表达式计算次数的一种方法部分冗余删除方法6、自然循环的概念及自然循环的识别例 题 1UNIX 下的C编译命令cc的选择项g和O的解释如下, 其中dbx的解释是“dbx is an utility for source-level debugging and execution of programs written in C”。试说明为什么用了选择项g后，选择项O便被忽略。-g Produce additio

60、nal symbol table information for dbx(1) and dbxtool(1) and pass -lg option to ld(1) (so as to include the g library, that is: /usr/lib/libg.a). When this option is given, the -O and -R options are suppressed.-Olevel Optimize the object code. Ignored when either -g, -go, or -a is used. .例 题 2一个C语言程序如