第九章 独立于机器的优化.ppt

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

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

3、2 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=an; an=x; . . .,9.1 优化的主要种类,程序流图

4、,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 优化的主要种类,局部公共子表达式删除, 复写传播, 删除死代码 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 = a

5、t8 at6 = t9 at8 = 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,9.1 优化的主要种类,全局公共子表达式删除, 复写传播, 删除死代码 B5 x=ai; ai=aj; aj=x;,t6 =

6、 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,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

7、 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 = a

8、t8 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 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、,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 优化的主要种类,i = m 1 j = n t1 = 4 n v = at1,i = i + 1 t2 = 4 i t3 = at2 if t3 v goto B2,B1,B2,j = j 1 t4 = 4 j t5 = at4 if t5 v goto B3,if i =

10、j goto B6,B4,B3,B5,B6,把at1作为公共子表达式是不稳妥的因为B5有对下标变量at2和at4的赋值,9.1 优化的主要种类,9.1.4 复写传播 复写语句：形式为f = g的赋值 优化过程中会大量引入复写,9.1 优化的主要种类,9.1.4 复写传播 复写语句：形式为f = g的赋值 优化过程中会大量引入复写 复写传播变换的做法是在复写语句f = g后，尽可能用g代表fB5,x = t3 at2 = t5 at4 = t3 goto B2,x = t3 at2 = t5 at4 = x goto B2,9.1 优化的主要种类,9.1.4 复写传播 复写语句：形式为f = g

11、的赋值 优化过程中会大量引入复写 复写传播变换的做法是在复写语句f = g后，尽可能用g代表f 复写传播变换本身并不是优化，但它给其它优化带来机会 常量合并（编译时可完成的计算） 死代码删除,pi = 3.14 y = pi 5,9.1 优化的主要种类,9.1.5 死代码删除 死代码是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码例： 为便于调试，可能在程序中加打印语句，测试 后改成右边的形式debug = true; | debug = false;. . . | . . .if (debug) print | if (debug) print 靠优化来保证目标代码中没有该条件语

12、句部分,9.1 优化的主要种类,9.1.5 死代码删除 死代码是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码 例：复写传播可能会引起死代码删除B5,x = t3 at2 = t5 at4 = t3 goto B2,at2 = t5 at4 = t3 goto B2,x = t3 at2 = t5 at4 = x goto B2,9.1 优化的主要种类,9.1.6 代码外提 代码外提是循环优化的一种 循环优化的其它重要技术 归纳变量删除 强度削弱 例：while (i = limit 2 ) 代码外提后变换成t = limit 2;while (i = t ) ,9.1 优化的主要

13、种类,9.1.7 强度削弱和归纳变量删除 j和t4的值步伐一致地变化 这样的变量叫做归纳变量 在循环中有多个归纳变量时，也许只需要留下一个 这个操作由归纳变量删除过程来完成 对本例可以先做强度削弱它给删除归纳变量创造机会,9.1 优化的主要种类,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 优化的主要种类,9.1 优化的主要种类,9.1 优化的主要种类,9.1 优化的主要种类,9.2 数据流分析介绍,9.2.1 数据流抽象 流图上的

14、点 基本块中，两个相邻的语句之间为程序的一个点 基本块的开始点和结束点 流图上的路径 点序列p1, p2, , pn，对1和n - 1间的每个i，满足 (1) pi是先于一个语句的点，pi1是同一块中位于该语句后的点，或者 (2) pi是某块的结束点，pi1是后继块的开始点,9.2 数据流分析介绍,9.2.1 数据流抽象 流图上路径实例- (1, 2, 3, 4, 9)- (1, 2, 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, 9)- (1, 2, 3, 4, 5, 6, 7, 8,

15、 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, )路径长度无限- 路径数无限,9.2 数据流分析介绍,9.2.1 数据流抽象分析程序的行为时，必 须在其流图上考虑所有的 执行路径（在调用或返回 语句被执行时，还需要考 虑执行路径在多个流图之 间的跳转）- 通常，从流图得到的程序执行路径数无限，且执行路径长度没有有限的上界,9.2 数据流分析介绍,9.2.1 数据流抽象分析程序的行为时，必 须在其流图上考虑所有的 执行路径（在调用或返回 语句被执行时，还需要考 虑执行路径在多个流图之 间的跳转）- 每个程序点的不同状态数也可能无限程序状态：存储单元到值的映射,9.2 数

16、据流分析介绍,9.2.1 数据流抽象把握所有执行路径上的所有程序状态一般来说是不可能的数据流分析并不打算区分到达一个程序点的不同执行路径，也不试图掌握该点每个完整的状态它从这些状态中抽取解决特定数据流分析所需信息，以总结出用于该分析目的的一组有限的事实并且这组事实和到达这个程序点的路径无关，即从任何路径到达该程序点都有这样的事实分析的目的不同，从程序状态提炼的信息也不同,9.2 数据流分析介绍,9.2.1 数据流抽象 点(5)所有程序状态： a 1, 243 由d1, d3定值 (1) 到达定值- d1, d3的定值到达点(5) (2) 常量合并- a在点(5)不是常量,9.2 数据流分析介绍

17、,9.2.3 到达-定值 到达一个程序点的所有定值 可用来判断一个变量在某程序点是否为常量 可用来判断一个变量在某程序点是否无初值 别名给到达-定值的计算带来困难 过程参数、数组访问、间接引用等都有可能引起别名例如：若p=q，则p-next和q-next互为别名 程序分析必须是稳妥的 本章其余部分仅考虑变量无别名的情况,9.2 数据流分析介绍,9.2.3 到达-定值 到达一个程序点的所有定值 可用来判断一个变量在某程序点是否为常量 可用来判断一个变量在某程序点是否无初值 别名给到达-定值的计算带来困难定值的注销 在一条执行路径上，对x的赋值注销先前对x的所有赋值,9.2 数据流分析介绍,gen

18、和kill分别表示一个基本块生成和注销的定值,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 数据流分析介绍,基本块的gen和kill是怎样计算的 对三地址指令 d: u = v + w，它的状态迁移函数是fd(x) = gend (x killd) 若：f1(x) = gen1 (x kill1), f2(x) = gen2 (x kill2)则： f2(f1(x)

19、= 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：能到达B的开始点的定值集合OUTB：能到达B的结束点的定值集合两组等式（根据gen和kill定义IN和O

20、UT）INB = P是B的前驱 OUTPOUTB = genB (INB killB)OUTENTRY = 到达-定值方程组的迭代求解,9.2 数据流分析介绍,IN B OUT B B1 000 0000 B2 000 0000 B3 000 0000 B4 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 0

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

22、5, 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 B4 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 B

23、4 = d7 kill B4 = d1, d4,9.2 数据流分析介绍,IN B OUT B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 000 0000 B4 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 00

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

25、l 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 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,ge

26、n 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, 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 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 数据流分析介绍,IN B OUT B B1 000 0000 111 0000 B2 111 0111 001 1110 B

28、3 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 1110 B3 001 1110 000 1110 B4 001 1110 001 0111不再继续演示迭代计算,gen B1 =

29、 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 数据流分析介绍,到达-定值数据流等式是正向的方程OUT B = gen B (IN B kill B)IN B = P是B的前驱 OUT P某些数据流等式是反向的 到达-定值数据流等式的合流运算是求并集IN B = P是B的前驱 OUT P 某些数据流等式的合流运算是求交集 对到达-定值数据流方程，迭代求它的最小解某些数据流方程可能需要求

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

31、Nsi+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 （可能用） 约束方程组的解通常不是唯一的 求解的目标是要找到满足这两组约束（控制流约束和迁移约束）的最“精确”解,9.2 数据流分析介绍,9.2.4 活跃变量 定义x的值在p点开始的某条执行路径上被

32、引用，则说x在p点活跃，否则称x在p点已经死亡INB：块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 SIN EXIT = 和到达定值等式之间的联系与区别都以集合并算符作为它们的汇合算符信息流动方向相反，IN和OUT的作用

33、相互交换use和def分别取代gen和kill仍然需要最小解,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点 可用 不可用 不可用,9.2 数据流分析介绍,9.2.5 可用表达式下面两种情况下， 4i在B3的入口都可用,9.2 数据流分析介绍,9.2.5 可用表达式 定义若到点p的每条执行路径都计算x + y，并且计算后没有对x或y赋值，那么称x + y在点p可用 e_genB：块B产生的可用表达式集合 e_killB： 块B注销

34、的可用表达式集合 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集合的不同初值比较 （以B2为例）,简写成： I j+1 = OUTB1 O j O j+1 = G (I j+1 K),O0 = （初值为空集） O0 = U （初值为全集） I 1 = I 1

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

36、代算法是正确的 迭代算法所得解的精度如何 迭代算法是否收敛 数据流方程的解的含义是什么,9.3 数据流分析的基础,数据流分析框架(D, V, , F)包括数据流分析的方向D，它可以是正向或逆向数据流值的论域半格V、汇合算子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中

37、的所有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并且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

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

39、整个定值半格 半格的高度 上升链是序列x1 x2 xn 半格的高度就是其中最长上升链中的个数 若半格的高度有限，证明数据流分析迭代算法的收敛则非常容易,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),9.3 数据流分析的基础,9.3.2 迁移函数 例 到达定值分析 若f1(x) = G1 (x K1)，f2(x)

40、 = 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),9.3 数据流分析的基础,9.3.3 一般框架的迭代算法 以正向数据流分析为例 (1) OUTENTRY = vENTRY; (2) for (除了ENTRY以外的每个块B) OUTB =; (3) while (任何一个OUT出现变化) (4)

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

42、属于该集合 这是理想解所考虑的路径集 可能的执行路径集 执行路径集 寻找所有可能执行路径是不可判定的 以下讨论以正向数据流分析为例,9.3 数据流分析的基础,9.3.4 数据流解的含义 理想解 若路径P = ENTRY B1 B2 Bk，定义fP fk1 f2 f1 IDEALB = /P是从ENTRY到B的一条可能路径 fP(vENTRY) 有关理解解的结论 任何大于理想解IDEAL的回答一定是不对的 任何小于或等于IDEAL的值是稳妥的 在稳妥的值中，越接近IDEAL的值越精确,9.3 数据流分析的基础,9.3.4 数据流解的含义 执行路径上的解（meet over paths） MOPB

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

44、9.3.4 数据流解的含义 MFP与MOP的联系 MFP访问块未必遵循次序由各块的初值和迁移函数 的单调性保证结果一致 MFP较早地使用汇合运算迭代算法的INB4 = f3(f1(vENTRY) f2(vENTRY)而MOPB4 = (f3 f1) (vENTRY) (f3 f2) (vENTRY)数据流分析框架具有分配性时，结果是一样的 MFP MOP IDEAL,9.4 常 量 传 播,9.4.1 常量传播框架的数据流值 单个变量的数据流值半格变量的类型所允许的所有常量值NAC表示不是常量值UNDEF表示没有定义 程序中各变量的半格的积 把程序中每个变量映射到该半格上的一个“值”,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)，若m(y)和m(z)都是常量值 m(x) = NAC，若m(y)或m(z)是NAC m(x) = UNDEF， 否则,