称为优化代码改进变换的标准代码变换必须保程序的含义采取安全课件

1、第九章 独立于机器的优化词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码符号表第1页，共140页。第九章 独立于机器的优化代码优化通过程序变换（局部变换和全局变换）来改进程序，称为优化代码改进变换的标准代码变换必须保程序的含义采取安全稳妥的策略变换减少程序的运行时间平均达到一个可度量的值变换所作的努力是值得的第2页，共140页。第九章 独立于机器的优化本章介绍独立于机器的优化，即不考虑任何依赖目标机器性质的优化变换 通过实例来介绍代码改进的主要机会 数据流分析包括的几类重要的全局收集的信息 数据流分析的一般框架 和一般框架有区

2、别的常量传播 部分冗余删除的优化技术 循环的识别和分析第3页，共140页。9.1 优化的主要种类9.1.1 优化的主要源头程序中存在许多程序员无法避免的冗余运算对于Aij和X.f1这样访问数组元素和结构体的域的操作（例如， Aij = Aij + 10）随着程序被编译，这些访问操作展开成多步低级算术运算对同一个数据结构的多次访问导致许多公共的低级运算程序员没有办法删除这些冗余第4页，共140页。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

3、) 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)第5页，共140页。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=

4、ai; ai=aj; aj=x;(14) t6 = 4 i(15 ) x = at6x=ai; ai=an; an=x;. . .第6页，共140页。9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6程序流图第7页，共140页。9.1 优化的主要种类9.1.3 公共子表达式删除B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 =

5、 xgoto B2第8页，共140页。9.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 B2第9页，共140页。9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto

6、 B6B4B3B5B6第10页，共140页。9.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 B2第11页，共140页。9.1 优化的主要种类全局公共子表达式删除, 复写传播, 删除死代码B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 j

7、t9 = at8at7 = t9t10 = 4 jat10 = xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 = xgoto B2x = at2t9 = at4at2 = t9at4 = xgoto B2第12页，共140页。9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6第13页，共140页。9.1 优化的主要种类全局公共子表达式删除, 复写传播, 删除死代码B5 x=ai; ai=

8、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 B2x = at2t9 = at4at2 = t9at4 = xgoto B2第14页，共140页。9.1 优化的主要种类全局公共子表达式删除, 复写传播, 删除死代码B5 x=ai; ai=aj; aj=x;t6 = 4 ix = at6t7 = 4 i t8 = 4 jt9 = at8at7 = t9t10 = 4 jat10 =

9、 xgoto B2t6 = 4 ix = at6t8 = 4 jt9 = at8at6 = t9at8 = xgoto B2x = at2t9 = at4at2 = t9at4 = xgoto B2x = t3at2 = t5at4 = xgoto B2第15页，共140页。9.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 =

10、x 第16页，共140页。9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6第17页，共140页。9.1 优化的主要种类B6 x = ai; ai = an; an = x;at1能否作为公共子表达式？t11 = 4 ix = at11t12 = 4 i t13 = 4 nt14 = at13at12 = t14t15 = 4 n at15 = x x = t3t14 = at1at2 = t14at1 = x 第18页，共140页。9.1

11、优化的主要种类i = m 1j = nt1 = 4 nv = at1i = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6 把at1作为公共子表达式是不稳妥的 因为B5有对下标变量at2和at4的赋值第19页，共140页。9.1 优化的主要种类9.1.4 复写传播复写语句：形式为f = g的赋值优化过程中会大量引入复写t = d + ea = t 删除局部公共子表达式期间引进复写t = d + eb = tc = tc = d + eb = d + ea = d + e第20页，共140页。9.1 优化的主要种类9.1.

12、4 复写传播复写语句：形式为f = g的赋值优化过程中会大量引入复写复写传播变换的做法是在复写语句f = g后，尽可能用g代表fB5x = t3at2 = t5at4 = t3goto B2x = t3at2 = t5at4 = xgoto B2第21页，共140页。9.1 优化的主要种类9.1.4 复写传播复写语句：形式为f = g的赋值优化过程中会大量引入复写复写传播变换的做法是在复写语句f = g后，尽可能用g代表f复写传播变换本身并不是优化，但它给其它优化带来机会常量合并（编译时可完成的计算）死代码删除pi = 3.14 y = pi 5第22页，共140页。9.1 优化的主要种类9.

13、1.5 死代码删除死代码是指计算的结果决不被引用的语句一些优化变换可能会引起死代码例： 为便于调试，可能在程序中加打印语句，测试后改成右边的形式 debug = true;| debug = false; . . .|. . . if (debug) print |if (debug) print 靠优化来保证目标代码中没有该条件语句部分第23页，共140页。9.1 优化的主要种类9.1.5 死代码删除死代码是指计算的结果决不被引用的语句一些优化变换可能会引起死代码例：复写传播可能会引起死代码删除B5x = t3at2 = t5at4 = t3goto B2at2 = t5at4 = t3go

14、to B2x = t3at2 = t5at4 = xgoto B2第24页，共140页。9.1 优化的主要种类9.1.6 代码外提代码外提是循环优化的一种循环优化的其它重要技术归纳变量删除强度削弱例：while (i = limit 2 ) 代码外提后变换成t = limit 2;while (i v goto B3B3第26页，共140页。9.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 j

15、t5 = at4if t5 v goto B3B3除第一次外，t4 = 4 j在B3的入口一定保持在j = j 1后，关系t4 = 4 j + 4也保持第27页，共140页。9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1t4 = 4 ji = i + 1t2 = 4 it3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6B2也可以进行类似的变换第28页，共140页。9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1t4 = 4 jt2 = 4 ii = i + 1t2 = t2+ 4t3 = at

16、2if t3 v goto B3if i = j goto B6B4B3B5B6第29页，共140页。9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1t4 = 4 jt2 = 4 ii = i + 1t2 = t2+ 4t3 = at2if t3 v goto B3if i = j goto B6B4B3B5B6循环控制条件可以用t2和t4来表示第30页，共140页。9.1 优化的主要种类i = m 1j = nt1 = 4 nv = at1t2 = 4 it4 = 4 jt2 = t2 + 4t3 = at2if t3 v goto B3if t2 = t4 go

17、to B6at2 = t5at4 = t3goto B2B4B3B5t14 = at1at2 = t14at1 = t3B6第31页，共140页。9.2 数据流分析介绍9.2.1 数据流抽象流图上的点基本块中，两个相邻的语句之间为程序的一个点基本块的开始点和结束点流图上的路径点序列p1, p2, , pn，对1和n - 1间的每个i，满足(1) pi是先于一个语句的点，pi1是同一块中位于该语句后的点，或者(2) pi是某块的结束点，pi1是后继块的开始点第32页，共140页。9.2 数据流分析介绍9.2.1 数据流抽象流图上路径实例 - (1, 2, 3, 4, 9) - (1, 2, 3,

18、 4, 5, 6, 7, 8, 3, 4, 9) - (1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, 3, 4, 9) - (1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, )路径长度无限 - 路径数无限B1(1)d2: b = ad3: a = 243 goto B3B4B2B3if read()=0 goto B4d1: a = 1(2)(3)(4)(5)(6)(7)(8)(9)第33页，共140页。9.2 数据流分析介绍9.2.1 数据流抽象 分析程序的行为时，必须在其流图上考虑

19、所有的执行路径（在调用或返回语句被执行时，还需要考虑执行路径在多个流图之间的跳转） - 通常，从流图得到的程序执行路径数无限，且执行路径长度没有有限的上界B1(1)d2: b = ad3: a = 243 goto B3B4B2B3if read()=0 goto B4d1: a = 1(2)(3)(4)(5)(6)(7)(8)(9)第34页，共140页。9.2 数据流分析介绍9.2.1 数据流抽象 分析程序的行为时，必须在其流图上考虑所有的执行路径（在调用或返回语句被执行时，还需要考虑执行路径在多个流图之间的跳转） - 每个程序点的不同状态数也可能无限程序状态：存储单元到值的映射B1(1)d

20、2: b = ad3: a = 243 goto B3B4B2B3if read()=0 goto B4d1: a = 1(2)(3)(4)(5)(6)(7)(8)(9)第35页，共140页。9.2 数据流分析介绍9.2.1 数据流抽象把握所有执行路径上的所有程序状态一般来说是不可能的 数据流分析并不打算区分到达一个程序点的不同执行路径，也不试图掌握该点每个完整的状态 它从这些状态中抽取解决特定数据流分析所需信息，以总结出用于该分析目的的一组有限的事实 并且这组事实和到达这个程序点的路径无关，即从任何路径到达该程序点都有这样的事实 分析的目的不同，从程序状态提炼的信息也不同第36页，共140页

21、。9.2 数据流分析介绍9.2.1 数据流抽象点(5)所有程序状态：a 1, 243 由d1, d3定值(1) 到达定值 - d1, d3的定值 到达点(5)(2) 常量合并 - a在点(5)不是 常量B1(1)d2: b = ad3: a = 243 goto B3B4B2B3if read()next和q-next互为别名程序分析必须是稳妥的本章其余部分仅考虑变量无别名的情况第38页，共140页。9.2 数据流分析介绍9.2.3 到达-定值到达一个程序点的所有定值可用来判断一个变量在某程序点是否为常量可用来判断一个变量在某程序点是否无初值别名给到达-定值的计算带来困难定值的注销在一条执行路

22、径上，对x的赋值注销先前对x的所有赋值第39页，共140页。9.2 数据流分析介绍gen和kill分别表示一个基本块生成和注销的定值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, d4第40页，共140页。9.2 数据流分析介绍基本块的

23、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 killn genB = genn (genn1 killn) (genn2 killn1 killn) (gen1 kill2 kill3 kill

24、n) 第41页，共140页。9.2 数据流分析介绍到达-定值的数据流等式 genB：B中能到达B的结束点的定值语句 killB：整个程序中决不会到达B结束点的定值 INB：能到达B的开始点的定值集合 OUTB：能到达B的结束点的定值集合两组等式（根据gen和kill定义IN和OUT） INB = P是B的前驱 OUTP OUTB = genB (INB killB) OUTENTRY = 到达-定值方程组的迭代求解第42页，共140页。9.2 数据流分析介绍 IN B OUT B B1 000 0000 B2 000 0000 B3 000 0000 B4 000 0000gen B1 = d

25、1, 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 = u2B3第43页，共140页。9.2 数据流分析介绍 IN B OUT B B1 000 0000 000 0000 B2 000 0000 B3 000 0000 B4 000 0000gen B1 = d1,

26、 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 = u2B3第44页，共140页。9.2 数据流分析介绍 IN B OUT B B1 000 0000 111 0000 B2 000 0000 B3 000 0000 B4 000 0000gen B1 = d1, d

27、2, 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 = u2B3第45页，共140页。9.2 数据流分析介绍 IN B OUT B B1 000 0000 111 0000 B2 111 0000 000 0000 B3 000 0000 B4 000 0000gen B1

28、= 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 = u2B3第46页，共140页。9.2 数据流分析介绍 IN B OUT B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 000 0000 B4 000 0000

29、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 = u2B3第47页，共140页。9.2 数据流分析介绍 IN B OUT B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000

30、0000 B4 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 = u2B3第48页，共140页。9.2 数据流分析介绍 IN B OUT B B1 000 0000 111 0000 B2 111 0000 001 1100

31、B3 001 1100 000 1110 B4 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 = u2B3第49页，共140页。9.2 数据流分析介绍 IN B OUT B B1 000 0000 111 0000 B2 11

32、1 0000 001 1100 B3 001 1100 000 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 = u2B3第50页，共140页。9.2 数据流分析介绍 IN B OUT B B

33、1 000 0000 111 0000 B2 111 0000 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 = u2B3第51页，共140页

34、。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 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 =

35、j 1d6: a = u2B3第52页，共140页。9.2 数据流分析介绍 IN B OUT B B1 000 0000 111 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 =

36、u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第53页，共140页。9.2 数据流分析介绍 IN BOUT B B1 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 =

37、m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第54页，共140页。9.2 数据流分析介绍到达-定值数据流等式是正向的方程 OUT B = gen B (IN B kill B)IN B = P是B的前驱 OUT P某些数据流等式是反向的到达-定值数据流等式的合流运算是求并集 IN B = P是B的前驱 OUT P 某些数据流等式的合流运算是求交集对到达-定值数据流方程，迭代求它的最小解某些数据流方程可能需要求最大解第55页，共140页。9.2 数据流分析介绍9.2.2 数据流分析模式数据流值

38、数据流分析总把程序点和数据流值联系起来数据流值代表在程序点能观测到的所有可能程序状态集合的一个抽象语句s前后两点数据流值用INs和OUTs来表示数据流问题就是通过基于语句语义的约束（迁移函数）和基于控制流的约束来寻找所有语句s的INs和OUTs 的一个解第56页，共140页。9.2 数据流分析介绍9.2.2 数据流分析模式迁移函数 f语句前后两点的数据流值受该语句的语义约束若沿执行路径正向传播，则OUTs = fs(INs)若沿执行路径逆向传播，则INs = fs(OUTs)若基本块B由语句s1, s2, , sn依次组成，则INsi+1 = OUTsi, i = 1, 2, , n1（逆向）

39、fB = fn . . . f2 f1 (逆向 fB = f1 . . . fn - 1 fn )OUTB = fB (INB) (逆向 INB = fB (OUTB) )第57页，共140页。9.2 数据流分析介绍9.2.2 数据流分析模式控制流约束正向传播 INB = P是B的前驱OUTP（可能用）逆向传播 OUTB = S是B的后继INS （可能用）约束方程组的解通常不是唯一的求解的目标是要找到满足这两组约束（控制流约束和迁移约束）的最“精确”解第58页，共140页。9.2 数据流分析介绍9.2.4 活跃变量定义 x的值在p点开始的某条执行路径上被引用，则说x在p点活跃，否则称x在p点已

40、经死亡 INB：块B开始点的活跃变量集合 OUTB：块B结束点的活跃变量集合 useB：块B中有引用且在引用前无定值的变量集 defB：块B中有定值的变量集应用 一种重要应用就是基本块的寄存器分配第59页，共140页。9.2 数据流分析介绍9.2.4 活跃变量例 useB2 = i, j defB2 = i, j d1: i = m 1d2: j = nd3: a = u1B1B2d7: i = u3B4d4: i = i + 1d5: j = j 1d6: a = u2B3第60页，共140页。9.2 数据流分析介绍9.2.4 活跃变量活跃变量数据流等式 IN B = useB (OUT B

41、 defB ) OUTB = S是B的后继 IN S IN EXIT = 和到达定值等式之间的联系与区别 都以集合并算符作为它们的汇合算符 信息流动方向相反，IN和OUT的作用相互交换 use和def分别取代gen和kill 仍然需要最小解第61页，共140页。9.2 数据流分析介绍9.2.5 可用表达式 x = y + z x = y + z x = y + z . . . . y = z = . . . p p py + z 在p点 y + z 在p点 y + z 在p点可用不可用不可用第62页，共140页。9.2 数据流分析介绍9.2.5 可用表达式下面两种情况下， 4i在B3的入口都可

42、用t1 = 4i没有对i 赋值t2 = 4iB1B2B3t1 = 4ii =t0 = 4it2 = 4iB1B2B3第63页，共140页。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出口的可用表达式集合应用公共子表达式删除第64页，共140页。9.2 数据流分析介绍9.2.5 可用表达式数据流等式 OUT B = e_genB (IN B e_killB ) IN

43、 B = P是B的前驱 OUT P IN ENTRY = 同先前的主要区别 使用而不是作为这里数据流等式的汇合算符 求最大解而不是最小解第65页，共140页。9.2 数据流分析介绍IN集合的不同初值比较 （以B2为例）B1B2简写成：I j+1 = OUTB1 O jO j+1 = G (I j+1 K)O0 = （初值为空集）O0 = U （初值为全集）I 1 = I 1 = OUTB1 O1 = GO1 = G (OUTB1 K)I 2 = OUTB1 GI2=(OUTB1G) (OUTB1K)O 2 = G O 2 = G (OUTB1 K)INB2= OUTB1 OUTB2OUTB2

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

45、据流值的论域 半格V、汇合算子 V到V的迁移函数族F 包括适用于边界条件（ENTRY和EXIT结点）的常函数第69页，共140页。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 = 第70页，共140页。9.3 数据流分析的基础9.3.1 半格偏序关系集合V上的关系 自反性：对所有的x，x x 反对称性

46、：对所有的x和y，如果x y并且y x,那么x = y 传递性：对所有的x, y和z，如果x y并且y z，那么x z此外，关系的定义x y当且仅当(x y)并且(x y) 第71页，共140页。9.3 数据流分析的基础9.3.1 半格半格和偏序关系之间的联系 半格(V, )的汇合运算确定了半格值集V上一种偏序 ： 对V中所有的x和y，x y当且仅当x y = x 若x y等于g，则g就是x和y的最大下界第72页，共140页。9.3 数据流分析的基础9.3.1 半格例半格的论域V是先前全域U的幂集集合并作为汇合运算：是顶元，U是底元， x = x并且U x = U，对应的偏序关系是 集合交作为

47、汇合运算：U是顶元， 是底元，对应偏序关系是 数据流方程组通常有很多解，但是按偏序意义上的最大解是最精确的(1) 到达定值：最精确的解含最少定值(2) 可用表达式：最精确的解含最多表达式 第73页，共140页。9.3 数据流分析的基础9.3.1 半格格图右边是定值子集形成的格这是一个格，本课程用半格概念就够了 是x y的最大下界 x y d1d2d3d1, d2d1, d3d2, d3d1, d2, d3( )( )第74页，共140页。9.3 数据流分析的基础9.3.1 半格积半格（定义略）上一页数据流值的集合是定值集合的幂集可以用从每个变量的一个简单定值半格构造出的积半格来表示整个定值半格

48、半格的高度上升链是序列x1 x2 xn半格的高度就是其中最长上升链中的个数若半格的高度有限，证明数据流分析迭代算法的收敛则非常容易第75页，共140页。9.3 数据流分析的基础9.3.2 迁移函数迁移函数族F : V V有下列性质 F包括恒等函数 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) 第76页，共140页。9.3 数据流分析的基础9.3.2 迁移函数例到达定值分析若f1(x) = G1 (x

49、 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)分配性： f(y z) = f(y) f(z) 第77页，共140页。9.3 数据流分析的基础9.3.3 一般框架的迭代算法以正向数据流分析为例(1) OUTENTRY = vENTRY;(2) for (除了ENTRY以外的每个块B) OUTB =;(3) while (任

50、何一个OUT出现变化)(4) for (除了ENTRY以外的每个块B) (5) INB = /P是B的前驱 OUTP;(6) OUTB = fB(INB);(7) 第78页，共140页。9.3 数据流分析的基础9.3.3 一般框架的迭代算法算法的一些可以证明的性质如果算法收敛，则结果是数据流方程组的一个解如果框架单调，则所求得的解是数据流方程组的最大不动点如果框架单调并且半格的高度有限，那么可以保证算法收敛第79页，共140页。9.3 数据流分析的基础9.3.4 数据流解的含义结论：算法所得解是理想解的稳妥近似理想解所考虑的路径执行路径集：流图上每一条路径都属于该集合 若流图有环，则执行路径数

51、是无限的程序可能的执行路径集：程序执行所走的路径属于该集合 这是理想解所考虑的路径集可能的执行路径集 执行路径集寻找所有可能执行路径是不可判定的以下讨论以正向数据流分析为例第80页，共140页。9.3 数据流分析的基础9.3.4 数据流解的含义理想解若路径P = ENTRY B1 B2 Bk，定义 fP fk1 f2 f1IDEALB = /P是从ENTRY到B的一条可能路径 fP(vENTRY)有关理解解的结论任何大于理想解IDEAL的回答一定是不对的任何小于或等于IDEAL的值是稳妥的在稳妥的值中，越接近IDEAL的值越精确第81页，共140页。9.3 数据流分析的基础9.3.4 数据流解

52、的含义执行路径上的解（meet over paths）MOPB = /P是从ENTRY到B的一条路径 fP(vENTRY)MOP解不仅汇集了所有可能路径的数据流值，而且还包括了那些不可能被执行路径的数据流值对所有的块B，MOPB IDEALB，简写成MOP IDEALMOP的定义并没有通向一个直接算法第82页，共140页。9.3 数据流分析的基础9.3.4 数据流解的含义先前算法得到的最大不动点解MFP不是先找出到达一个块的所有路径，然后用汇合运算，而是访问每个基本块，并且不一定按照程序执行时的次序在每个汇合点，把汇合运算作用在到目前为止得到的数据流值上，其中所用一些初值是人工引入的 MFP:

53、 maximal fixed point B1ENTRYB4B3B2第83页，共140页。9.3 数据流分析的基础9.3.4 数据流解的含义MFP与MOP的联系MFP访问块未必遵循次序由各块的初值和迁移函数的单调性保证结果一致MFP较早地使用汇合运算 迭代算法的INB4 = f3(f1(vENTRY) f2(vENTRY) 而MOPB4 = (f3 f1) (vENTRY) (f3 f2) (vENTRY) 数据流分析框架具有分配性时，结果是一样的MFP MOP IDEALB1ENTRYB4B3B2第84页，共140页。9.4 常 量 传 播9.4.1 常量传播框架的数据流值单个变量的数据流值

54、半格 变量的类型所允许的所有常量 值NAC表示不是常量 值UNDEF表示没有定义程序中各变量的半格的积把程序中每个变量映射到 该半格上的一个“值”UNDEFNAC 3 2 1 0 1 2 3 第85页，共140页。9.4 常 量 传 播9.4.2 常量传播框架的迁移函数 令fs是语句s的迁移函数，m = fs(m)，用m和m之间的联系来表达fs (m是变量到“值”的映射)(1) 如果s不是赋值语句，则fs是恒等函数(2) 若s对变量x赋值，则对所有v x，m(v) = m(v)，再看m(x)：若s的右部是一个常量c，则m(x) = c若s的右部是y + z m(x) = m(y) + m(z)

55、，若m(y)和m(z)都是常量值 m(x) = NAC，若m(y)或m(z)是NAC m(x) = UNDEF， 否则第86页，共140页。9.4 常 量 传 播9.4.3 常量传播框架的单调性 m(y)m(z)m(x)UNDEF UNDEF UNDEFc2 UNDEFNACNACUNDEFUNDEF c1 c2 c1 + c2NACNACUNDEFNACNAC c2NACNACNAC(1) 赋值语句的形式不是x = y + z fs不改变m(x)的值，或者改变成一个常量 在这些情况下，fs肯定是单调的第87页，共140页。9.4 常 量 传 播9.4.3 常量传播框架的单调性 m(y)m(z

56、)m(x)UNDEF UNDEF UNDEFc2 UNDEFNACNACUNDEFUNDEF c1 c2 c1 + c2NACNACUNDEFNACNAC c2NACNACNAC(1) 赋值语句的形式不是x = y + z fs不改变m(x)的值，或者改变成一个常量 在这些情况下，fs肯定是单调的(2) 赋值语句的形式是x = y + z见右边， fs单调第88页，共140页。9.4 常 量 传 播9.4.4 常量传播框架的非分配性不管取什么路径，在块B3的出口，z的值是5迭代算法在块B3的入口而不是出口使用汇合运算 f3(f1(m0) f2(m0) f3(f1(m0) f3(f2(m0)不具

57、有分配性算法未能发现B3出口z是5，这个结果虽不精确但安全B1EXITz = x + yx = 2y = 3B3B2x = 3y = 2第89页，共140页。9.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 = x第90页，共140页。9.5 部 分 冗 余 删 除本节内容 冗余计算以公共子表达式的形式出现，或以循环不变

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

59、块B4的表达式b + c是完全冗余的，因为所有到达B4的路径都计算b + c ，并且b和c都未重新定值B2和B3的出边的集合形成一个割集，若把该割集删掉，则从起点到B4的路径都被割断 B1B2B4B3b = 7d = b + ca = b + ce = b + c第93页，共140页。9.5 部 分 冗 余 删 除9.5.1 冗余的根源循环不变表达式a = b + ct = b + ca = t第94页，共140页。9.5 部 分 冗 余 删 除9.5.1 冗余的根源部分冗余表达式B1B2B4B3a = b + cd = b + cB1B2B4B3t = b + ct = b + ca = t

60、d = t第95页，共140页。9.5 部 分 冗 余 删 除9.5.1 冗余的根源放置b + c的副本来使B4中的b + c完全冗余 B1B2B4B3a = b + cd = b + cB1B2B4B3t = b + ct = b + ca = td = t第96页，共140页。9.5 部 分 冗 余 删 除9.5.2 能否删除所有的冗余B3 B4是一条关键边：源结点有多个后继目标结点有多个前驱B1B2B3B4d = b + ca = b + cB5B1B2B3B6t = b + ct = b + ca = tB5d = tB4增加新块来删除冗余第97页，共140页。9.5 部 分 冗 余