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 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
4、 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=at6x=ai;ai=an;an=x;.9.1 优化的主要种类优化的主要种类i=m 1j=nt1=4 nv=at1i=i+1t2=4 it3=at2if t3 v goto B3if i=j goto B6B4B3B5B69.1
5、优化的主要种类优化的主要种类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=xgoto B29.1 优化的主要种类优化的主要种类i=m 1j=nt1=4 nv=at1i=i+1t2=4 it3=at2i
6、f 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;t6=4 ix=at6t7=4 i t8=4 jt9=at8at7=t9t10=4 jat10=xgoto B2t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgot
7、o 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=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 优化的主要种类优化
8、的主要种类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 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 优化的主
9、要种类优化的主要种类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 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
10、=g的赋值叫做的赋值叫做复写语句复写语句 优化过程中会大量引入复写优化过程中会大量引入复写t=d+ea=t 删除局部公共子表达式期间引进复写删除局部公共子表达式期间引进复写t=d+eb=tc=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 优化
11、的主要种类优化的主要种类9.1.4 复写传播复写传播 形成为形成为f=g的赋值叫做的赋值叫做复写语句复写语句 优化过程中会大量引入复写优化过程中会大量引入复写 复写传播变换的做法是在复写语句复写传播变换的做法是在复写语句f=g后，后，尽可能用尽可能用g代表代表f 复写传播变换本身并不是优化，但它给其它复写传播变换本身并不是优化，但它给其它优化带来机会优化带来机会 常量合并常量合并 死代码删除死代码删除9.1 优化的主要种类优化的主要种类9.1.5 死代码删除死代码删除 死代码死代码是指计算的结果决不被引用的语句是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码一些优化变换可能会引起死
12、代码例：例：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 代码外提代码外提 代码外提是代码外提是循环优化的一种循环优化
13、的一种 循环优化的其它重要技术循环优化的其它重要技术 归纳变量删除归纳变量删除 强度削弱强度削弱例：例：while(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也也
14、保持保持9.1 优化的主要种类优化的主要种类i=m 1j=nt1=4 nv=at1i=i+1t2=4 it3=at2if t3 v goto B3if i=j goto B6B4B3B5B6B B2也可以进行也可以进行类似的变换类似的变换循环控制条件循环控制条件可以用可以用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 数据流分析介绍
15、数据流分析介绍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,
16、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 数据流抽象数据流抽象 分析程序的行为时，必须在其流图上考虑分析程序的行为时，必须在其流图上考虑所有的所有的执行路径执行路径（在调用或返回语句被执行时，还需要（在调用或返回语句被执行时，还需要考虑路径在多个流图之间的跳转）考虑路径在多个流图之间的跳转）然后从每个程序点的然后从每个程序点的所有可能状态所有可能状态中抽取解决特中抽取解决特定数据流分析所需信息定数据流分析所需信息
17、通常，从流图得到的程序通常，从流图得到的程序执行路径数无限执行路径数无限，且执，且执行路径长度没有有限的上界行路径长度没有有限的上界 程序分析从程序点的所有可能状态中为该点程序分析从程序点的所有可能状态中为该点总结总结出一组有限的事实出一组有限的事实9.2 数据流分析介绍数据流分析介绍9.2.1 数据流抽象数据流抽象 明了所有路径上所有程序状态是不可能的明了所有路径上所有程序状态是不可能的 数据流分析不打算区分到达一个程序点的不同路数据流分析不打算区分到达一个程序点的不同路径，也不试图掌握完整的状态径，也不试图掌握完整的状态 它抽取出某些细节，以获取用于分析目的的数据它抽取出某些细节，以获取用
18、于分析目的的数据 从同样的状态，根据程序分析的不同目的，可以从同样的状态，根据程序分析的不同目的，可以提炼出不同的信息提炼出不同的信息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 程序分析必须是稳妥的程序分析必须是稳妥的 本章其余部分仅考
19、虑变量无别名的情况本章其余部分仅考虑变量无别名的情况9.2 数据流分析介绍数据流分析介绍9.2.3 到达到达-定值定值 到达程序点的所有定值到达程序点的所有定值 可用来判断一个变量在某程序点是否为常量可用来判断一个变量在某程序点是否为常量 可用来判断一个变量在某程序点是否无初值可用来判断一个变量在某程序点是否无初值 别名给别名给到达到达-定值的计算带来困难定值的计算带来困难 注销注销 在一条路径上，先前对在一条路径上，先前对x的赋值被后面对的赋值被后面对x的赋值的赋值所注销所注销9.2 数据流分析介绍数据流分析介绍 gen和和kill分别表示基本块生成和注销的定值分别表示基本块生成和注销的定值
20、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)=gen1 (x kill1),f2(x)=gen
21、2 (x kill2)f2(f1(x)=gen2 (gen1 (x kill1)kill2)=(gen2 (gen1 kill2)(x (kill1 kill2)若基本块若基本块B有有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：整个程序中决不会到达整个程序中决不会到达
22、B结束点的定值结束点的定值 inB：能到达能到达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
23、 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 000 0000 B2 000 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000gen B1=d1,d2,d3kill B1=d4,d5
24、,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 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
25、=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,d5,d6,d7gen B2=d4,d5kill B2=d1,d2,d7gen B3=d6kill B3
26、=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,d3kill B1=d4,d5,d6,d7gen B2=d4,d5kill B2=d1,d2,d7gen B3=d6kill B3=d3gen B4=d7kill B4=d1,d4
27、d1: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 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=u1B1B2
28、d7: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 0000 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 1
29、d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in B out B B1 000 0000 111 0000 B2 111 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=u2B39.2 数据流分析介绍数据流分析
30、介绍 in B out B B1 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=u2B39.2 数据流分析介绍数据流分析介绍 in B out B B1 000 0000
31、 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=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in B out B B1 000 0000 111 0000 B2 111 0111 001
32、 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 B1 000 0000 111 0000 B2 111 0111 001 1110 B3 001 1110 000 111
33、0 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 数据流分析介绍数据流分析介绍 到达到达-定值等式是定值等式是正向正向的方程的方程 in B =P是是B的前驱的前驱 out P 另一类数据流等式是另一类数据流等式是反向反向的的 到达到达-定值等式的合
34、流算符是求并集定值等式的合流算符是求并集out B=gen B (in B kill B)另一类数据流等式的合流算符是求交集另一类数据流等式的合流算符是求交集9.2 数据流分析介绍数据流分析介绍9.2.4 活跃变量活跃变量 定义定义 x的值在的值在p点开始的路径上被引用，则说点开始的路径上被引用，则说x在在p点活点活跃，否则称跃，否则称x在在p点是死亡的点是死亡的 in B：块块B B开始点的活跃变量集合开始点的活跃变量集合 outB：块块B B结束点的活跃变量集合结束点的活跃变量集合 useB：块块B B中有引用且在引用前无定值的变量集中有引用且在引用前无定值的变量集 defB：块块B B中
35、有定值的变量集中有定值的变量集 应用应用 一种重要应用就是基本块的寄存器分配一种重要应用就是基本块的寄存器分配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=u2B39.2 数据流分析介绍数据流分析介绍9.2.4 活跃变量活跃变量 活跃变量数据流等式活跃变量数据流等式 in B=useB (out B defB)outB=S是是B的后继的后继 in S in EXIT=和到达和到达 定值等式之间的联系与区别定值等式之间的联
36、系与区别 都以集合并算符作为它们的汇合算符都以集合并算符作为它们的汇合算符 信息流动方向相反，信息流动方向相反，IN和和OUT的作用相互交换的作用相互交换 use和和def分别代替分别代替gen和和kill，最小解代替最大解，最小解代替最大解9.2 数据流分析介绍数据流分析介绍9.2.5 可用表达式可用表达式 x=y+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=4 i?t2=4 iB1B2B3t1=4 ii =t0=4 it2=
37、4 iB1B2B39.2 数据流分析介绍数据流分析介绍9.2.5 可用表达式可用表达式 定义定义 若到点若到点p的每条路径都计算的每条路径都计算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_
38、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=G O 2=G (out B1 K)
39、9.2 数据流分析介绍数据流分析介绍9.2.6 小结小结 三个数据流问题三个数据流问题 到达到达 定值、活跃变量、可用表达式定值、活跃变量、可用表达式 每个问题的组成每个问题的组成 数据流值的论域、数据流的方向、迁移函数、边数据流值的论域、数据流的方向、迁移函数、边界条件、汇合算符、数据流等式界条件、汇合算符、数据流等式 见书上表见书上表9.29.3 数据流分析的基础数据流分析的基础本节内容本节内容1、把各种数据流模式作为一个整体抽象地研究、把各种数据流模式作为一个整体抽象地研究2、形式地回答数据流算法的下列几个基本问题、形式地回答数据流算法的下列几个基本问题 在什么情况下数据流分析中使用的迭
40、代算法是正在什么情况下数据流分析中使用的迭代算法是正确的确的 迭代算法所得解的精度如何迭代算法所得解的精度如何 迭代算法是否收敛迭代算法是否收敛 数据流方程的解的含义是什么数据流方程的解的含义是什么9.3 数据流分析的基础数据流分析的基础 数据流分析框架数据流分析框架(D,V,F)包括包括 数据流分析的方向数据流分析的方向D，它可以是正向或逆向，它可以是正向或逆向 数据流值的论域数据流值的论域 半格半格V、汇合算子、汇合算子 V到到V的迁移函数族的迁移函数族F 包括适用于边界条件（包括适用于边界条件（ENTRY和和EXIT结点）结点）的常函数的常函数9.3 数据流分析的基础数据流分析的基础9.
41、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
42、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的最大下界的
43、最大下界9.3 数据流分析的基础数据流分析的基础9.3.1 半格半格 例：半格的论域例：半格的论域V是是U的幂集的幂集 集合并作为汇合运算：集合并作为汇合运算：是顶元，是顶元，U是底元，是底元，x=x并且并且U x=U，对应二元关系是，对应二元关系是 集合交作为汇合运算：集合交作为汇合运算：U是顶元，是顶元，是底元是底元，对对应二元关系是应二元关系是 数据流方程组通常有很多解，但是按偏序数据流方程组通常有很多解，但是按偏序意义意义上的最大解是最精确的上的最大解是最精确的 到达到达 定值：最精确的解含最少定值定值：最精确的解含最少定值 可用表达式：最精确的解含最多表达式可用表达式：最精确的解含最
44、多表达式 9.3 数据流分析的基础数据流分析的基础9.3.1 半格半格 格图格图 这是一个格，本课程这是一个格，本课程用半格概念就够了用半格概念就够了 是是 x y的最大下界的最大下界 x y d1d2d3d1,d2d1,d3d2,d3d1,d2,d3()()9.3 数据流分析的基础数据流分析的基础9.3.1 半格半格 积半格（定义略）积半格（定义略）上例数据流值的集合是定值集合的幂集上例数据流值的集合是定值集合的幂集 可以用从每个变量的一个简单半格构造出的积半可以用从每个变量的一个简单半格构造出的积半格来表示整个定值半格格来表示整个定值半格 半格的高度半格的高度 上升链是序列上升链是序列x1
45、 x2 xn 半格的高度就是其中最长上升链中半格的高度就是其中最长上升链中的个数的个数 若半格的高度有限，证明数据流分析迭代算法的若半格的高度有限，证明数据流分析迭代算法的收敛则非常容易收敛则非常容易9.3 数据流分析的基础数据流分析的基础9.3.2 迁移函数迁移函数 迁移函数族迁移函数族F:V V有下列性质有下列性质 F有一个恒等函数有一个恒等函数I F封闭于复合封闭于复合 若若F中所有函数中所有函数f 都有单调性，即都有单调性，即 x y蕴涵蕴涵f(x)f(y)，或，或 f(x y)f(x)f(y)则称框架则称框架(D,V,F)是单调的是单调的 框架框架(D,V,F)的分配性的分配性 对对
46、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 (y K)(G (z K)9.3 数据流分析的基础数据流分析的基础9.3.
47、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 一般框架的迭代算法一般框架的迭代算法 算法的一些可以证明的性质算法的一些可以证明的性质 如果算法收敛，则结果是数据流方程组的一个解如果算法收敛，则结果是
48、数据流方程组的一个解 如果框架单调，则所求得的解是数据流方程组的如果框架单调，则所求得的解是数据流方程组的最大不动点最大不动点 如果框架单调并且半格的高度有限，那么可以保如果框架单调并且半格的高度有限，那么可以保证算法收敛证算法收敛9.3 数据流分析的基础数据流分析的基础9.3.4 数据流解的含义数据流解的含义 结论：算法所得解是理想解的稳妥近似结论：算法所得解是理想解的稳妥近似 理想解所考虑的路径理想解所考虑的路径 执行路径集：流图上每一条路径都属于该集合执行路径集：流图上每一条路径都属于该集合 若流图有环，则执行路径数是无界的若流图有环，则执行路径数是无界的 程序可能的执行路径集：程序执行
49、所走的路径属程序可能的执行路径集：程序执行所走的路径属于该集合于该集合 理想解所考虑的路径理想解所考虑的路径 程序可能的执行路径集程序可能的执行路径集 执行路径集执行路径集 寻找所有可能执行路径是不可判定的寻找所有可能执行路径是不可判定的 讨论正向数据流分析讨论正向数据流分析9.3 数据流分析的基础数据流分析的基础9.3.4 数据流解的含义数据流解的含义 理想解理想解若路径若路径P=ENTRY B1 B2 Bk，定义，定义 fP fk 1 f2 f1 IDEALB=/P是从是从ENTRY到到B的一条可能路径的一条可能路径 fP(vENTRY)有关理解解的结论有关理解解的结论 任何大于理想解任何
50、大于理想解IDEAL的回答一定是不对的的回答一定是不对的 任何小于或等于任何小于或等于IDEAL的值是稳妥的的值是稳妥的 在稳妥的值中，越接近在稳妥的值中，越接近IDEAL的值越精确的值越精确 9.3 数据流分析的基础数据流分析的基础9.3.4 数据流解的含义数据流解的含义 执行路径上的解（执行路径上的解（meet over paths）MOPB=/P是从是从ENTRY到到B的一条路径的一条路径 fP(vENTRY)MOP解不仅汇集了所有可能路径的数据流值，而解不仅汇集了所有可能路径的数据流值，而且还包括了那些不可能被执行路径的数据流值且还包括了那些不可能被执行路径的数据流值 对所有的块对所有
