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

1、第九章第九章 独立于机器的优化独立于机器的优化 通过程序变换（局部变换和全局变换）来改通过程序变换（局部变换和全局变换）来改 进程序，称为优化进程序，称为优化 代码改进变换的标准代码改进变换的标准 代码变换必须保程序的含义代码变换必须保程序的含义 采取安全稳妥的策略采取安全稳妥的策略 变换减少程序的运行时间平均达到一个可度量变换减少程序的运行时间平均达到一个可度量 的值的值 变换所作的努力是值得的变换所作的努力是值得的 第九章第九章 独立于机器的优化独立于机器的优化 本章介绍独立于机器的优化，即不考虑任何本章介绍独立于机器的优化，即不考虑任何 依赖依赖目标机器性质的优化变换目标机器性质的优化变

2、换 通过实例来介绍代码改进的主要机会通过实例来介绍代码改进的主要机会 数据流分析包括的几类重要的全局收集的信息数据流分析包括的几类重要的全局收集的信息 数据流分析的一般框架数据流分析的一般框架 和一般框架有区别的常量传播和一般框架有区别的常量传播 部分冗余删除的优化技术部分冗余删除的优化技术 循环的识别和分析循环的识别和分析 9.1 优化的主要种类优化的主要种类 9.1.1 优化的主要源头优化的主要源头 程序中存在许多程序员无法避免的冗余运算程序中存在许多程序员无法避免的冗余运算 通过像通过像aij和和x.f1的方式引用数组元素和结构的方式引用数组元素和结构 的域的域 随着程序被编译，对这样高

3、级数据结构的访问展随着程序被编译，对这样高级数据结构的访问展 开成多步低级算术运算开成多步低级算术运算 对同一个数据结构的多次访问导致许多公共的低对同一个数据结构的多次访问导致许多公共的低 级运算级运算 程序员没有办法删除这些冗余程序员没有办法删除这些冗余 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

4、=x;(6) t2 = 4 i (7) t3 = at2 x=ai; ai=an; an=x;(8) if 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

5、=an; an=x;. . . 9.1 优化的主要种类优化的主要种类 i = m 1 j = n t1 = 4 n v = at1 i = i + 1 t2 = 4 i t3 = at2 if t3 v goto b3 if i = j goto b6 b4 b3 b5 b6 9.1 优化的主要种类优化的主要种类 9.1.3 公共子表达式删除公共子表达式删除 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 9.1 优化的主要种类优化的主要种

6、类 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 优化的主要种类优化的主要种类 i = m 1 j = n t1 = 4 n v = at1 i = i + 1 t2 = 4 i t3 = at2 if t3 v goto b3 if i = j goto b6 b4 b3 b5 b6 9.1 优化的主要种类优化

7、的主要种类 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 优化的主要种类优化的主要种类 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

8、= at6 t8 = 4 j t9 = at8 at6 = t9 at8 = x goto b2 x = at2 t9 = at4 at2 = t9 at4 = x goto b2 9.1 优化的主要种类优化的主要种类 i = m 1 j = n t1 = 4 n v = at1 i = i + 1 t2 = 4 i t3 = at2 if t3 v goto b3 if i = j goto b6 b4 b3 b5 b6 9.1 优化的主要种类优化的主要种类 b5 x=ai; ai=aj; aj=x; t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 a

9、t7 = 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 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 = t

10、9 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 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;

11、 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 优化的主要种类优化的主要种类 i = m 1 j = n t1 = 4 n v = at1 i = i + 1 t2 = 4 i t3 = at2 if t3 v goto b3 if i = j goto b6 b4 b3 b5 b6 把把at1作作 为公共子表达为公共子表达 式是不稳妥的式是不稳妥的 9

12、.1 优化的主要种类优化的主要种类 9.1.4 复写传播复写传播 形成为形成为f = g的赋值叫做的赋值叫做复写语句复写语句 优化过程中会大量引入复写优化过程中会大量引入复写 t = d + e a = t 删除局部公共子表达式期间引进复写删除局部公共子表达式期间引进复写 t = d + e b = t c = t c = d + e b = d + ea = d + e 9.1 优化的主要种类优化的主要种类 9.1.4 复写传播复写传播 形成为形成为f = g的赋值叫做的赋值叫做复写语句复写语句 优化过程中会大量引入复写优化过程中会大量引入复写 复写传播变换的做法是在复写语句复写传播变换的做

13、法是在复写语句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 复写传播变换本身并不是优化，但它给其它复写传播变换本身并不是优化，但它给其它 优化带来机会优化带来机会 常量合并常量合

14、并 死代码删除死代码删除 9.1 优化的主要种类优化的主要种类 9.1.5 死代码删除死代码删除 死代码死代码是指计算的结果决不被引用的语句是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码一些优化变换可能会引起死代码 例：例： debug = true; debug = false; . . . 测试后改成测试后改成 . . . if (debug) print if (debug) print 9.1 优化的主要种类优化的主要种类 9.1.5 死代码删除死代码删除 死代码死代码是指计算的结果决不被引用的语句是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码一些优化变换可

15、能会引起死代码 例：复写传播可能会引起例：复写传播可能会引起死代码删除死代码删除 x = t3 at2 = t5 at4 = t3 goto b2 at2 = t5 at4 = t3 goto b2 9.1 优化的主要种类优化的主要种类 9.1.6 代码外提代码外提 代码外提是代码外提是循环优化的一种循环优化的一种 循环优化的其它重要技术循环优化的其它重要技术 归纳变量删除归纳变量删除 强度削弱强度削弱 例：例：while (i = limit 2 ) 变换成变换成 t = limit 2; while (i v goto b3 b3 9.1 优化的主要种类优化的主要种类 i = m 1 j

16、= n t1 = 4 n v = at1 b1 b2 j = j 1 t4 = t4 4 t5 = at4 if t5 v goto b3 b4 b3 b5b6 t4 = 4 j if i = j goto b6 j = j 1 t4 = 4 j t5 = at4 if t5 v goto b3 b3 除第一次外，除第一次外， t4 = 4 j在在b3的入的入 口一定保持口一定保持 在在j = j 1后，后， 关系关系t4 = 4 j + 4也也 保持保持 9.1 优化的主要种类优化的主要种类 i = m 1 j = n t1 = 4 n v = at1 i = i + 1 t2 = 4 i

17、t3 = at2 if t3 v goto b3 if i = j goto b6 b4 b3 b5 b6 b b2也可以进行也可以进行 类似的变换类似的变换 循环控制条件循环控制条件 可以用可以用t2和和t4 来表示来表示 9.1 优化的主要种类优化的主要种类 i = m 1 j = n t1 = 4 n v = at1 t2 = 4 i t4 = 4 j t2 = t2 + 4 t3 = at2 if t3 v goto b3 if t2 = t4 goto b6 at2 = t5 at4 = t3 goto b2 b4 b3 b5t14 = at1 at2 = t14 at1 = t3

18、b6 9.2 数据流分析介绍数据流分析介绍 9.2.1 数据流抽象数据流抽象 点点 基本块中，两个相邻的语句之间为程序的一个基本块中，两个相邻的语句之间为程序的一个点点 基本块的开始点和结束点基本块的开始点和结束点 路径路径 点序列点序列p1, p2, , pn，对对1和和n - 1间的每个间的每个i，满满 足足 pi是先于一个语句的点，是先于一个语句的点，pi 1是同一块中位于该语 是同一块中位于该语 句后的点，或者句后的点，或者 pi是某块的结束点，是某块的结束点，pi 1是后继块的开始点 是后继块的开始点 9.2 数据流分析介绍数据流分析介绍 9.2.1 数据流抽象数据流抽象 路径实例路

19、径实例 -（1, 2, 3, 4, 9） -（1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 9） b1 (1) d2: b = a d3: a = 243 goto b3 b4 b2 b3 if read()=0 goto b4 d1: a = 1 (2) (3) (4) (5) (6) (7) (8) (9) 9.2 数据流分析介绍数据流分析介绍 9.2.1 数据流抽象数据流抽象 分析程序的行为时，必须在其流图上考虑分析程序的行为时，必须在其流图上考虑所有的所有的 执行路径执行路径（在调用或返回语句被执行时，还需要（在调用或返回语句被执行时，还需要 考虑路径在多个流图之间的跳转

20、）考虑路径在多个流图之间的跳转） 然后从每个程序点的然后从每个程序点的所有可能状态所有可能状态中抽取解决特中抽取解决特 定数据流分析所需信息定数据流分析所需信息 通常，从流图得到的程序通常，从流图得到的程序执行路径数无限执行路径数无限，且执，且执 行路径长度没有有限的上界行路径长度没有有限的上界 程序分析从程序点的所有可能状态中为该点程序分析从程序点的所有可能状态中为该点总结总结 出一组有限的事实出一组有限的事实 9.2 数据流分析介绍数据流分析介绍 9.2.1 数据流抽象数据流抽象 明了所有路径上所有程序状态是不可能的明了所有路径上所有程序状态是不可能的 数据流分析不打算区分到达一个程序点的

21、不同路数据流分析不打算区分到达一个程序点的不同路 径，也不试图掌握完整的状态径，也不试图掌握完整的状态 它抽取出某些细节，以获取用于分析目的的数据它抽取出某些细节，以获取用于分析目的的数据 从同样的状态，根据程序分析的不同目的，可以从同样的状态，根据程序分析的不同目的，可以 提炼出不同的信息提炼出不同的信息 9.2 数据流分析介绍数据流分析介绍 9.2.1 数据流抽象数据流抽象 点点(5)所有程序状态：所有程序状态： - a 1, 243 - 由由d1, d3定值定值 1、到达、到达 定值定值 - d1, d3的定值的定值 到达点到达点(5) 2、常量合并、常量合并 - a在点在点(5)不是不

22、是 常量常量 b1 (1) d2: b = a d3: a = 243 goto b3 b4 b2 b3 if read()next的赋值没有改变的赋值没有改变q-next 程序分析必须是稳妥的程序分析必须是稳妥的 本章其余部分仅考虑变量无别名的情况本章其余部分仅考虑变量无别名的情况 9.2 数据流分析介绍数据流分析介绍 9.2.3 到达到达- -定值定值 到达程序点的所有定值到达程序点的所有定值 可用来判断一个变量在某程序点是否为常量可用来判断一个变量在某程序点是否为常量 可用来判断一个变量在某程序点是否无初值可用来判断一个变量在某程序点是否无初值 别名给别名给到达到达- -定值的计算带来困

23、难定值的计算带来困难 注销注销 在一条路径上，先前对在一条路径上，先前对x的赋值被后面对的赋值被后面对x的赋值的赋值 所注销所注销 9.2 数据流分析介绍数据流分析介绍 gen和和kill分别表示基本块生成和注销的定值分别表示基本块生成和注销的定值 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 gen b1 = d1, d2, d3 kill b1=d4, d5, d6, d7 gen b2 = d4, d5 kill b2 = d1, d2, d7 gen

24、 b3 = d6 kill b3 = d3 gen b4 = d7 kill b4 = d1, d4 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

25、有有n条三地址指令条三地址指令 killb = kill1 kill2 killn genb = genn (genn 1 killn) (genn 2 killn 1 killn) (gen1 kill2 kill3 killn) 9.2 数据流分析介绍数据流分析介绍 到达到达-定值的数据流等式定值的数据流等式 genb：b中能到达中能到达b的结束点的定值语句的结束点的定值语句 killb：整个程序中决不会到达整个程序中决不会到达b结束点的定值结束点的定值 inb：能到达能到达b的开始点的定值集合的开始点的定值集合 outb：能到达能到达b的结束点的定值集合的结束点的定值集合 两组等式（根据

26、两组等式（根据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 0000 gen b1 = d1, d2, d3 kill b1=d4, d5, d6, d7 gen b2 = d4, d5 kill b2 = d1, d

27、2, d7 gen b3 = d6 kill b3 = d3 gen b4 = d7 kill b4 = d1, d4 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 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 0000 gen b1 = d1, d2, d3 kill b1=d4, d5

28、, d6, d7 gen b2 = d4, d5 kill b2 = d1, d2, d7 gen b3 = d6 kill b3 = d3 gen b4 = d7 kill b4 = d1, d4 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 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

29、 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 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 9.2 数据流分析介绍数据流分析介绍 in b out b b1 000 0000 111 0000 b2 111 0000 000 0

30、000 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 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 9.2 数据流分析介绍数据流分析介绍 in b out

31、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 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d

32、6: a = u2b3 9.2 数据流分析介绍数据流分析介绍 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 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d

33、7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 9.2 数据流分析介绍数据流分析介绍 in b out b b1 000 0000 111 0000 b2 111 0000 001 1100 b3 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

34、d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 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 kill b1=d4, d5, d6, d7 gen b2 = d4, d5 kill b2 = d1, d2, d7 gen b3 = d6 ki

35、ll b3 = d3 gen b4 = d7 kill b4 = d1, d4 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 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

36、, d5 kill b2 = d1, d2, d7 gen b3 = d6 kill b3 = d3 gen b4 = d7 kill b4 = d1, d4 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 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, d

37、2, 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 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 9.2 数据流分析介绍数据流分析介绍 in b out b b1 000 0000 111 0000 b2 111 0111 001 1110 b3 001 1100 000

38、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 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a = u2b3 9.2 数据流分析介绍数据流分析介绍 in b out b b1 000 0000 111 00

39、00 b2 111 0111 001 1110 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 d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i = i + 1 d5: j = j 1 d6: a =

40、u2b3 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点是死亡的点

41、是死亡的 in b：块块b b开始点的活跃变量集合开始点的活跃变量集合 outb：块块b b结束点的活跃变量集合结束点的活跃变量集合 useb：块块b b中有引用且在引用前无定值的变量集中有引用且在引用前无定值的变量集 defb：块块b b中有定值的变量集中有定值的变量集 应用应用 一种重要应用就是基本块的寄存器分配一种重要应用就是基本块的寄存器分配 9.2 数据流分析介绍数据流分析介绍 9.2.4 活跃变量活跃变量 例例 useb2 = i, j defb2 = i, j d1: i = m 1 d2: j = n d3: a = u1 b1 b2 d7: i = u3 b4 d4: i =

42、 i + 1 d5: j = j 1 d6: a = u2b3 9.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 数据

43、流分析介绍数据流分析介绍 9.2.5 可用表达式可用表达式 x = y + z x = y + z x = y + z . . . . y = z = . . . p pp y + z 在在p点点 y + z 在在p点点 y + z 在在p点点 可用可用不可用不可用不可用不可用 9.2 数据流分析介绍数据流分析介绍 9.2.5 可用表达式可用表达式 t1 = 4 i ? t2 = 4 i b1 b2 b3 t1 = 4 i i = t0 = 4 i t2 = 4 i b1 b2 b3 9.2 数据流分析介绍数据流分析介绍 9.2.5 可用表达式可用表达式 定义定义 若到点若到点p的每条路径都计

44、算的每条路径都计算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

45、 = 同先前的主要区别同先前的主要区别 使用使用 而不是而不是 作为这里数据流等式的汇合算符作为这里数据流等式的汇合算符 9.2 数据流分析介绍数据流分析介绍 in集合的不同初值比较集合的不同初值比较 in b2 = out b1 out b2 （以以b2为例）为例） out b2 = g (in b2 k) b1 b2 o j+1 = g (i j k) i j+1 = out b1 o j+1 i 0 = i 0 = u o 1 = g o 1 = u k i 1 = out b1 g i 1 = out b1 k o 2 = g o 2 = g (out b1 k) 9.2 数据流分析介

46、绍数据流分析介绍 9.2.6 小结小结 三个数据流问题三个数据流问题 到达到达 定值、活跃变量、可用表达式定值、活跃变量、可用表达式 每个问题的组成每个问题的组成 数据流值的论域、数据流的方向、迁移函数、边数据流值的论域、数据流的方向、迁移函数、边 界条件、汇合算符、数据流等式界条件、汇合算符、数据流等式 见书上表见书上表9.2 9.3 数据流分析的基础数据流分析的基础 本节内容本节内容 1、把各种数据流模式作为一个整体抽象地研究、把各种数据流模式作为一个整体抽象地研究 2、形式地回答数据流算法的下列几个基本问题、形式地回答数据流算法的下列几个基本问题 在什么情况下数据流分析中使用的迭代算法是

47、正在什么情况下数据流分析中使用的迭代算法是正 确的确的 迭代算法所得解的精度如何迭代算法所得解的精度如何 迭代算法是否收敛迭代算法是否收敛 数据流方程的解的含义是什么数据流方程的解的含义是什么 9.3 数据流分析的基础数据流分析的基础 数据流分析框架数据流分析框架(d, v, , f)包括包括 数据流分析的方向数据流分析的方向d，它可以是正向或逆向，它可以是正向或逆向 数据流值的论域数据流值的论域 半格半格v、汇合算子、汇合算子 v到到v的迁移函数族的迁移函数族f 包括适用于边界条件（包括适用于边界条件（entry和和exit结点）结点） 的常函数的常函数 9.3 数据流分析的基础数据流分析的

48、基础 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上的

49、关系上的关系 自反性：对自反性：对所有的所有的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当且仅

50、当当且仅当x y = x 若若x y等于等于g，则，则g就是就是x和和y的最大下界的最大下界 9.3 数据流分析的基础数据流分析的基础 9.3.1 半格半格 例：半格的论域例：半格的论域v是是u的幂集的幂集 集合并作为汇合运算：集合并作为汇合运算：是顶元，是顶元，u是底元，是底元， x = x并且并且u x = u，对应二元关系是，对应二元关系是 集合交作为汇合运算：集合交作为汇合运算：u是顶元，是顶元， 是底元是底元，对对 应二元关系是应二元关系是 数据流方程组通常有很多解，但是按偏序数据流方程组通常有很多解，但是按偏序意义意义 上的最大解是最精确的上的最大解是最精确的 到达到达 定值：最精

51、确的解含最少定值定值：最精确的解含最少定值 可用表达式：最精确的解含最多表达式可用表达式：最精确的解含最多表达式 9.3 数据流分析的基础数据流分析的基础 9.3.1 半格半格 格图格图 这是一个格，本课程这是一个格，本课程 用半格概念就够了用半格概念就够了 是是 x y的最大下界的最大下界 x y d1d2d3 d1, d2 d1, d3d2, d3 d1, d2, d3 ( ) ( ) 9.3 数据流分析的基础数据流分析的基础 9.3.1 半格半格 积半格（定义略）积半格（定义略） 上例数据流值的集合是定值集合的幂集上例数据流值的集合是定值集合的幂集 可以用从每个变量的一个简单半格构造出的

52、积半可以用从每个变量的一个简单半格构造出的积半 格来表示整个定值半格格来表示整个定值半格 半格的高度半格的高度 上升链是序列上升链是序列x1 x2 xn 半格的高度就是其中最长上升链中 半格的高度就是其中最长上升链中的个数的个数 若半格的高度有限，证明数据流分析迭代算法的若半格的高度有限，证明数据流分析迭代算法的 收敛则非常容易收敛则非常容易 9.3 数据流分析的基础数据流分析的基础 9.3.2 迁移函数迁移函数 迁移函数族迁移函数族f : v v有下列性质有下列性质 f有一个恒等函数有一个恒等函数i f封闭于复合封闭于复合 若若f中所有函数中所有函数f 都有单调性，即都有单调性，即 x y蕴

53、涵蕴涵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

54、的复合的复合f为为f = g (x k)的形式的形式 分配性可以由检查下面的条件得到分配性可以由检查下面的条件得到 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是 是

55、b的前驱的前驱 outp; (6) outb = fb(inb); (7) 9.3 数据流分析的基础数据流分析的基础 9.3.3 一般框架的迭代算法一般框架的迭代算法 算法的一些可以证明的性质算法的一些可以证明的性质 如果算法收敛，则结果是数据流方程组的一个解如果算法收敛，则结果是数据流方程组的一个解 如果框架单调，则所求得的解是数据流方程组的如果框架单调，则所求得的解是数据流方程组的 最大不动点最大不动点 如果框架单调并且半格的高度有限，那么可以保如果框架单调并且半格的高度有限，那么可以保 证算法收敛证算法收敛 9.3 数据流分析的基础数据流分析的基础 9.3.4 数据流解的含义数据流解的含

56、义 结论：算法所得解是理想解的稳妥近似结论：算法所得解是理想解的稳妥近似 理想解所考虑的路径理想解所考虑的路径 执行路径集：流图上每一条路径都属于该集合执行路径集：流图上每一条路径都属于该集合 若流图有环，则执行路径数是无界的若流图有环，则执行路径数是无界的 程序可能的执行路径集：程序执行所走的路径属程序可能的执行路径集：程序执行所走的路径属 于该集合于该集合 理想解所考虑的路径理想解所考虑的路径 程序可能的执行路径集程序可能的执行路径集 执行路径集执行路径集 寻找所有可能执行路径是不可判定的寻找所有可能执行路径是不可判定的 讨论正向数据流分析讨论正向数据流分析 9.3 数据流分析的基础数据流

57、分析的基础 9.3.4 数据流解的含义数据流解的含义 理想解理想解 若路径若路径p = entry b1 b2 bk，定义，定义 fp fk 1 f2 f1 idealb = /p是从 是从entry到到b的一条可能路径的一条可能路径 fp(ventry) 有关理解解的结论有关理解解的结论 任何大于理想解任何大于理想解ideal的回答一定是不对的的回答一定是不对的 任何小于或等于任何小于或等于ideal的值是稳妥的的值是稳妥的 在稳妥的值中，越接近在稳妥的值中，越接近ideal的值越精确的值越精确 9.3 数据流分析的基础数据流分析的基础 9.3.4 数据流解的含义数据流解的含义 执行路径上的

58、解（执行路径上的解（meet over paths） mopb = /p是从 是从entry到到b的一条路径的一条路径 fp(ventry) mop解不仅汇集了所有可能路径的数据流值，而解不仅汇集了所有可能路径的数据流值，而 且还包括了那些不可能被执行路径的数据流值且还包括了那些不可能被执行路径的数据流值 对所有的块对所有的块b，mopb idealb，简写成，简写成 mop ideal mop的定义并没有通向一个直接算法的定义并没有通向一个直接算法 9.3 数据流分析的基础数据流分析的基础 9.3.4 数据流解的含义数据流解的含义 先前算法得到的最大不动点解先前算法得到的最大不动点解mfp

59、不是先找出到达一个块的所有路径，然后用汇合不是先找出到达一个块的所有路径，然后用汇合 运算，而是运算，而是 访问每个基本块，并且不一定按照程序执行时的访问每个基本块，并且不一定按照程序执行时的 次序次序 在每个汇合点，把汇合运算作用在到目前为止得在每个汇合点，把汇合运算作用在到目前为止得 到的数据流值上，其中所用一些初值是人工引入到的数据流值上，其中所用一些初值是人工引入 的的 9.3 数据流分析的基础数据流分析的基础 9.3.4 数据流解的含义数据流解的含义 mfp与与mop的联系的联系 mfp访问块未必遵循次序访问块未必遵循次序 由初值和单调性保证一致由初值和单调性保证一致 mfp较早地使

60、用汇合运算较早地使用汇合运算 mopb4 = (f3 f1) (ventry) (f3 f2) (ventry) inb4 = f3(f1(ventry) f2(ventry) 数据流分析框架具有分配性时，结果是一样的数据流分析框架具有分配性时，结果是一样的 mfp mop ideal b1 entry b4 b3 b2 9.4 常常 量量 传传 播播 9.4.1 常量传播框架的数据流值常量传播框架的数据流值 单个变量的数据流值半格单个变量的数据流值半格 变量的类型所允许的所有常量变量的类型所允许的所有常量 值值nac表示不是常量表示不是常量 值值undef表示没有定义表示没有定义 程序中各变