第九章第九章 独立于机器的优化独立于机器的优化 通过程序变换（局部变换和全局变换）来改通过程序变换（局部变换和全局变换）来改进程序，称为优化进程序，称为优化代码改进变换的标准代码改进变换的标准 代码变换必须保程序的含义代码变换必须保程序的含义 采取安全稳妥的策略采取安全稳妥的策略 变换减少程序的运行时间平均达到一个可度量变换减少程序的运行时间平均达到一个可度量的值的值 变换所作的努力是值得的变换所作的努力是值得的第九章第九章 独立于机器的优化独立于机器的优化本章介绍独立于机器的优化，即不考虑任何本章介绍独立于机器的优化，即不考虑任何依赖依赖目标机器性质的优化变换目标机器性质的优化变换通过实例来介绍代码改进的主要机会通过实例来介绍代码改进的主要机会 数据流分析包括的几类重要的全局收集的信息数据流分析包括的几类重要的全局收集的信息数据流分析的一般框架数据流分析的一般框架 和一般框架有区别的常量传播和一般框架有区别的常量传播部分冗余删除的优化技术部分冗余删除的优化技术循环的识别和分析循环的识别和分析9.1 优化的主要种类优化的主要种类9.1.1优化的主要源头优化的主要源头程序中存在许多程序员无法避免的冗余运算程序中存在许多程序员无法避免的冗余运算通过像通过像Aij和和X.f1的方式引用数组元素和结构的方式引用数组元素和结构的域的域随着程序被编译，对这样高级数据结构的访问展随着程序被编译，对这样高级数据结构的访问展开成多步低级算术运算开成多步低级算术运算对同一个数据结构的多次访问导致许多公共的低对同一个数据结构的多次访问导致许多公共的低级运算级运算程序员没有办法删除这些冗余程序员没有办法删除这些冗余9.1 优化的主要种类优化的主要种类9.1.2一个实例一个实例i=m 1;j=n;v=an;(1)i=m 1while(1)(2)j=ndoi=i+1;while(aiv);(4)v=at1if(i=j)break;(5)i=i+1x=ai;ai=aj;aj=x;(6)t2=4 i(7)t3=at2x=ai;ai=an;an=x;(8)ift3vgoto(5)9.1 优化的主要种类优化的主要种类9.1.2一个实例一个实例i=m 1;j=n;v=an;(9)j=j 1while(1)(10)t4=4 jdoi=i+1;while(aiv);(12)ift5vgoto(9)if(i=j)break;(13)ifi=jgoto(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=at2ift3vgotoB3ifi=jgotoB6B4B3B5B69.1 优化的主要种类优化的主要种类9.1.3公共子表达式删除公共子表达式删除B5x=ai;ai=aj;aj=x;t6=4 ix=at6t7=4 it8=4 jt9=at8at7=t9t10=4 jat10=xgotoB29.1 优化的主要种类优化的主要种类B5x=ai;ai=aj;aj=x;t6=4 ix=at6t7=4 it8=4 jt9=at8at7=t9t10=4 jat10=xgotoB2t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgotoB29.1 优化的主要种类优化的主要种类i=m 1j=nt1=4 nv=at1i=i+1t2=4 it3=at2ift3vgotoB3ifi=jgotoB6B4B3B5B69.1 优化的主要种类优化的主要种类B5x=ai;ai=aj;aj=x;t6=4 ix=at6t7=4 it8=4 jt9=at8at7=t9t10=4 jat10=xgotoB2t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgotoB29.1 优化的主要种类优化的主要种类B5x=ai;ai=aj;aj=x;t6=4 ix=at6t7=4 it8=4 jt9=at8at7=t9t10=4 jat10=xgotoB2t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgotoB2x=at2t9=at4at2=t9at4=xgotoB29.1 优化的主要种类优化的主要种类i=m 1j=nt1=4 nv=at1i=i+1t2=4 it3=at2ift3vgotoB3ifi=jgotoB6B4B3B5B69.1 优化的主要种类优化的主要种类B5x=ai;ai=aj;aj=x;t6=4 ix=at6t7=4 it8=4 jt9=at8at7=t9t10=4 jat10=xgotoB2t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgotoB2x=at2t9=at4at2=t9at4=xgotoB29.1 优化的主要种类优化的主要种类B5x=ai;ai=aj;aj=x;t6=4 ix=at6t7=4 it8=4 jt9=at8at7=t9t10=4 jat10=xgotoB2t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgotoB2x=at2t9=at4at2=t9at4=xgotoB2x=t3at2=t5at4=xgotoB29.1 优化的主要种类优化的主要种类B6x=ai;ai=an;an=x;t11=4 ix=at11t12=4 it13=4 nt14=at13at12=t14t15=4 nat15=xx=t3t14=at1at2=t14at1=x9.1 优化的主要种类优化的主要种类B6x=ai;ai=an;an=x;at1能否作为公共子表达式？能否作为公共子表达式？t11=4 ix=at11t12=4 it13=4 nt14=at13at12=t14t15=4 nat15=xx=t3t14=at1at2=t14at1=x9.1 优化的主要种类优化的主要种类i=m 1j=nt1=4 nv=at1i=i+1t2=4 it3=at2ift3vgotoB3ifi=jgotoB6B4B3B5B6把把at1作作为公共子表达为公共子表达式是不稳妥的式是不稳妥的9.1 优化的主要种类优化的主要种类9.1.4复写传播复写传播形成为形成为f=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=t3gotoB2x=t3at2=t5at4=xgotoB29.1 优化的主要种类优化的主要种类9.1.4复写传播复写传播形成为形成为f=g的赋值叫做的赋值叫做复写语句复写语句优化过程中会大量引入复写优化过程中会大量引入复写复写传播变换的做法是在复写语句复写传播变换的做法是在复写语句f=g后，尽后，尽可能用可能用g代表代表f复写传播变换本身并不是优化，但它给其它复写传播变换本身并不是优化，但它给其它优化带来机会优化带来机会常量合并常量合并死代码删除死代码删除9.1 优化的主要种类优化的主要种类9.1.5死代码删除死代码删除死代码死代码是指计算的结果决不被引用的语句是指计算的结果决不被引用的语句一些优化变换可能会引起死代码一些优化变换可能会引起死代码例：例：debug=true;debug=false;.测试后改成测试后改成.if(debug)printif(debug)print9.1 优化的主要种类优化的主要种类9.1.5死代码删除死代码删除死代码死代码是指计算的结果决不被引用的语句是指计算的结果决不被引用的语句一些优化变换可能会引起死代码一些优化变换可能会引起死代码例：复写传播可能会引起例：复写传播可能会引起死代码删除死代码删除x=t3at2=t5at4=t3gotoB2at2=t5at4=t3gotoB29.1 优化的主要种类优化的主要种类9.1.6代码外提代码外提代码外提是代码外提是循环优化的一种循环优化的一种循环优化的其它重要技术循环优化的其它重要技术归纳变量删除归纳变量删除强度削弱强度削弱例：例：while(i =limit 2)变换成变换成t=limit 2;while(ivgotoB3B39.1 优化的主要种类优化的主要种类i=m 1j=nt1=4 nv=at1B1B2j=j 1t4=t4 4t5=at4ift5vgotoB3B4B3B5B6t4=4 jifi=jgotoB6j=j 1t4=4 jt5=at4ift5vgotoB3B3除第一次外，除第一次外，t4=4 j在在B3的入的入口一定保持口一定保持在在j=j 1后，后，关系关系t4=4 j+4也也保持保持9.1 优化的主要种类优化的主要种类i=m 1j=nt1=4 nv=at1i=i+1t2=4 it3=at2ift3vgotoB3ifi=jgotoB6B4B3B5B6B B2也可以进行也可以进行类似的变换类似的变换循环控制条件循环控制条件可以用可以用t2和和t4来表示来表示9.1 优化的主要种类优化的主要种类i=m 1j=nt1=4 nv=at1t2=4 it4=4 jt2=t2+4t3=at2ift3vgotoB3ift2=t4gotoB6at2=t5at4=t3gotoB2B4B3B5t14=at1at2=t14at1=t3B69.2 数据流分析介绍数据流分析介绍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,3,4,9） B1(1)d2:b=ad3:a=243gotoB3B4B2B3ifread()=0gotoB4d1:a=1(2)(3)(4)(5)(6)(7)(8)(9)9.2 数据流分析介绍数据流分析介绍9.2.1数据流抽象数据流抽象分析程序的行为时，必须在其流图上考虑分析程序的行为时，必须在其流图上考虑所有的所有的执行路径执行路径（在调用或返回语句被执行时，还需要（在调用或返回语句被执行时，还需要考虑路径在多个流图之间的跳转）考虑路径在多个流图之间的跳转）然后从每个程序点的然后从每个程序点的所有可能状态所有可能状态中抽取解决特中抽取解决特定数据流分析所需信息定数据流分析所需信息通常，从流图得到的程序通常，从流图得到的程序执行路径数无限执行路径数无限，且执，且执行路径长度没有有限的上界行路径长度没有有限的上界程序分析从程序点的所有可能状态中为该点程序分析从程序点的所有可能状态中为该点总结总结出一组有限的事实出一组有限的事实9.2 数据流分析介绍数据流分析介绍9.2.1数据流抽象数据流抽象 明了所有路径上所有程序状态是不可能的明了所有路径上所有程序状态是不可能的数据流分析不打算区分到达一个程序点的不同路数据流分析不打算区分到达一个程序点的不同路径，也不试图掌握完整的状态径，也不试图掌握完整的状态它抽取出某些细节，以获取用于分析目的的数据它抽取出某些细节，以获取用于分析目的的数据从同样的状态，根据程序分析的不同目的，可以从同样的状态，根据程序分析的不同目的，可以提炼出不同的信息提炼出不同的信息9.2 数据流分析介绍数据流分析介绍9.2.1数据流抽象数据流抽象点点(5)所有程序状态：所有程序状态：-a 1,243-由由d1,d3定值定值1、到达、到达定值定值 - d1,d3的定值的定值到达点到达点(5)2、常量合并、常量合并-a在点在点(5)不是不是常量常量B1(1)d2:b=ad3:a=243gotoB3B4B2B3ifread()next的赋值没有改变的赋值没有改变q-next程序分析必须是稳妥的程序分析必须是稳妥的本章其余部分仅考虑变量无别名的情况本章其余部分仅考虑变量无别名的情况9.2 数据流分析介绍数据流分析介绍9.2.3到达到达- -定值定值到达程序点的所有定值到达程序点的所有定值 可用来判断一个变量在某程序点是否为常量可用来判断一个变量在某程序点是否为常量 可用来判断一个变量在某程序点是否无初值可用来判断一个变量在某程序点是否无初值别名给别名给到达到达- -定值的计算带来困难定值的计算带来困难注销注销在一条路径上，先前对在一条路径上，先前对x的赋值被后面对的赋值被后面对x的赋值的赋值所注销所注销9.2 数据流分析介绍数据流分析介绍gen和和kill分别表示基本块生成和注销的定值分别表示基本块生成和注销的定值d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B3genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d49.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有有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的结束点的定值集合的结束点的定值集合两组等式（根据两组等式（根据gen和和kill定义定义in和和out） inB= P是是B的前驱的前驱outP outB=genB (inB killB)outENTRY=到达到达-定值方程组的迭代求解定值方程组的迭代求解9.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000000000000B200000000000000B300000000000000B400000000000000genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000000000000B200000000000000B300000000000000B400000000000000genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000001110000B200000000000000B300000000000000B400000000000000genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000001110000B211100000000000B300000000000000B400000000000000genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000001110000B211100000011100B300000000000000B400000000000000genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000001110000B211100000011100B300111000000000B400000000000000genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000001110000B211100000011100B300111000001110B400000000000000genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000001110000B211100000011100B300111000001110B400111100000000genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000001110000B211100000011100B300111000001110B400111100010111genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000001110000B211101110011100B300111000001110B400111100010111genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000001110000B211101110011110B300111000001110B400111100010111genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍 in Bout BB1 00000001110000B211101110011110B300111100001110B400111100010111不再继续计算不再继续计算genB1=d1,d2,d3killB1=d4,d5,d6,d7genB2=d4,d5killB2=d1,d2,d7genB3=d6killB3=d3genB4=d7killB4=d1,d4d1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍到达到达- -定值等式是定值等式是正向正向的方程的方程 inB= P是是B的前驱的前驱out P另一类数据流等式是另一类数据流等式是反向反向的的到达到达- -定值等式的合流算符是求并集定值等式的合流算符是求并集out B=gen B (in B kill B) 另一类数据流等式的合流算符是求交集另一类数据流等式的合流算符是求交集9.2 数据流分析介绍数据流分析介绍9.2.4活跃变量活跃变量定义定义x的值在的值在p点开始的路径上被引用，则说点开始的路径上被引用，则说x在在p点活点活跃，否则称跃，否则称x在在p点是死亡的点是死亡的 inB：块块B B开始点的活跃变量集合开始点的活跃变量集合 outB：块块B B结束点的活跃变量集合结束点的活跃变量集合 useB：块块B B中有引用且在引用前无定值的变量集中有引用且在引用前无定值的变量集 defB：块块B B中有定值的变量集中有定值的变量集应用应用一种重要应用就是基本块的寄存器分配一种重要应用就是基本块的寄存器分配9.2 数据流分析介绍数据流分析介绍9.2.4活跃变量活跃变量例例 useB2=i,jdefB2=i,jd1:i=m 1d2:j=nd3:a=u1B1B2d7:i=u3B4d4:i=i+1d5:j=j 1d6:a=u2B39.2 数据流分析介绍数据流分析介绍9.2.4活跃变量活跃变量活跃变量数据流等式活跃变量数据流等式 inB=useB (outB defB) outB= S是是B的后继的后继inS inEXIT=和到达和到达定值等式之间的联系与区别定值等式之间的联系与区别都以集合并算符作为它们的汇合算符都以集合并算符作为它们的汇合算符信息流动方向相反，信息流动方向相反，IN和和OUT的作用相互交换的作用相互交换 use和和def分别代替分别代替gen和和kill，最小解代替最大解，最小解代替最大解9.2 数据流分析介绍数据流分析介绍9.2.5可用表达式可用表达式x=y+zx=y+zx=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=4 iB1B2B39.2 数据流分析介绍数据流分析介绍9.2.5可用表达式可用表达式定义定义 若到点若到点p的每条路径都计算的每条路径都计算x+y，并且计算后没，并且计算后没有对有对x或或y赋值，那么称赋值，那么称x+y在点在点p可用可用e_genB：块：块B产生的可用表达式集合产生的可用表达式集合e_killB：块：块B注销的可用表达式集合注销的可用表达式集合 inB：块块B入口的可用表达式集合入口的可用表达式集合outB：块：块B出口的可用表达式集合出口的可用表达式集合9.2 数据流分析介绍数据流分析介绍9.2.5可用表达式可用表达式数据流等式数据流等式 outB=e_genB (inB e_killB) inB=P是是B的前驱的前驱outP inENTRY=同先前的主要区别同先前的主要区别使用使用 而不是而不是 作为这里数据流等式的汇合算符作为这里数据流等式的汇合算符9.2 数据流分析介绍数据流分析介绍in集合的不同初值比较集合的不同初值比较inB2=out B1 out B2（以以B2为例）为例） outB2=G (in B2 K)B1B2O j+1=G (I j K)Ij+1=outB1 O j+1I 0=I 0=UO 1=G O 1=U KI 1=outB1 G I 1=outB1 KO 2=G O 2=G (outB1 K)9.2 数据流分析介绍数据流分析介绍9.2.6小结小结三个数据流问题三个数据流问题到达到达定值、活跃变量、可用表达式定值、活跃变量、可用表达式每个问题的组成每个问题的组成数据流值的论域、数据流的方向、迁移函数、边数据流值的论域、数据流的方向、迁移函数、边界条件、汇合算符、数据流等式界条件、汇合算符、数据流等式见书上表见书上表9.29.3 数据流分析的基础数据流分析的基础本节内容本节内容1、把各种数据流模式作为一个整体抽象地研究、把各种数据流模式作为一个整体抽象地研究2、形式地回答数据流算法的下列几个基本问题、形式地回答数据流算法的下列几个基本问题在什么情况下数据流分析中使用的迭代算法是正在什么情况下数据流分析中使用的迭代算法是正确的确的迭代算法所得解的精度如何迭代算法所得解的精度如何迭代算法是否收敛迭代算法是否收敛数据流方程的解的含义是什么数据流方程的解的含义是什么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中的所有中的所有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此外，关系此外，关系的定义的定义xy当且仅当当且仅当(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是顶元，是顶元，是底元是底元，对对应二元关系是应二元关系是 数据流方程组通常有很多解，但是按偏序数据流方程组通常有很多解，但是按偏序意义意义上的最大解是最精确的上的最大解是最精确的 到达到达定值：最精确的解含最少定值定值：最精确的解含最少定值 可用表达式：最精确的解含最多表达式可用表达式：最精确的解含最多表达式 9.3 数据流分析的基础数据流分析的基础9.3.1半格半格格图格图这是一个格，本课程这是一个格，本课程用半格概念就够了用半格概念就够了 是是 x y的最大下界的最大下界 x yd1d2d3d1, d2d1, d3d2, d3d1, d2, d3()( )9.3 数据流分析的基础数据流分析的基础9.3.1半格半格积半格（定义略）积半格（定义略）上例数据流值的集合是定值集合的幂集上例数据流值的集合是定值集合的幂集可以用从每个变量的一个简单半格构造出的积半可以用从每个变量的一个简单半格构造出的积半格来表示整个定值半格格来表示整个定值半格半格的高度半格的高度上升链是序列上升链是序列x1x2xn 半格的高度就是其中最长上升链中半格的高度就是其中最长上升链中的个数的个数若半格的高度有限，证明数据流分析迭代算法的若半格的高度有限，证明数据流分析迭代算法的收敛则非常容易收敛则非常容易9.3 数据流分析的基础数据流分析的基础9.3.2迁移函数迁移函数迁移函数族迁移函数族F :VV有下列性质有下列性质 F有一个恒等函数有一个恒等函数I F封闭于复合封闭于复合 若若F中所有函数中所有函数f 都有单调性，即都有单调性，即 xy蕴涵蕴涵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)的形式的形式分配性可以由检查下面的条件得到分配性可以由检查下面的条件得到 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一般框架的迭代算法一般框架的迭代算法算法的一些可以证明的性质算法的一些可以证明的性质如果算法收敛，则结果是数据流方程组的一个解如果算法收敛，则结果是数据流方程组的一个解如果框架单调，则所求得的解是数据流方程组的如果框架单调，则所求得的解是数据流方程组的最大不动点最大不动点如果框架单调并且半格的高度有限，那么可以保如果框架单调并且半格的高度有限，那么可以保证算法收敛证算法收敛9.3 数据流分析的基础数据流分析的基础9.3.4数据流解的含义数据流解的含义结论：算法所得解是理想解的稳妥近似结论：算法所得解是理想解的稳妥近似理想解所考虑的路径理想解所考虑的路径执行路径集：流图上每一条路径都属于该集合执行路径集：流图上每一条路径都属于该集合若流图有环，则执行路径数是无界的若流图有环，则执行路径数是无界的程序可能的执行路径集：程序执行所走的路径属程序可能的执行路径集：程序执行所走的路径属于该集合于该集合理想解所考虑的路径理想解所考虑的路径程序可能的执行路径集程序可能的执行路径集 执行路径集执行路径集寻找所有可能执行路径是不可判定的寻找所有可能执行路径是不可判定的讨论正向数据流分析讨论正向数据流分析9.3 数据流分析的基础数据流分析的基础9.3.4数据流解的含义数据流解的含义理想解理想解若路径若路径P=ENTRYB1B2Bk，定义，定义 fPfk 1 f2 f1IDEALB=/P是从是从ENTRY到到B的一条可能路径的一条可能路径fP(vENTRY)有关理解解的结论有关理解解的结论任何大于理想解任何大于理想解IDEAL的回答一定是不对的的回答一定是不对的任何小于或等于任何小于或等于IDEAL的值是稳妥的的值是稳妥的在稳妥的值中，越接近在稳妥的值中，越接近IDEAL的值越精确的值越精确 9.3 数据流分析的基础数据流分析的基础9.3.4数据流解的含义数据流解的含义执行路径上的解（执行路径上的解（meet over paths）MOPB=/P是从是从ENTRY到到B的一条路径的一条路径fP(vENTRY)MOP解不仅汇集了所有可能路径的数据流值，而解不仅汇集了所有可能路径的数据流值，而且还包括了那些不可能被执行路径的数据流值且还包括了那些不可能被执行路径的数据流值对所有的块对所有的块B，MOPBIDEALB，简写成，简写成MOPIDEALMOP的定义并没有通向一个直接算法的定义并没有通向一个直接算法9.3 数据流分析的基础数据流分析的基础9.3.4数据流解的含义数据流解的含义先前算法得到的最大不动点解先前算法得到的最大不动点解MFP不是先找出到达一个块的所有路径，然后用汇合不是先找出到达一个块的所有路径，然后用汇合运算，而是运算，而是访问每个基本块，并且不一定按照程序执行时的访问每个基本块，并且不一定按照程序执行时的次序次序在每个汇合点，把汇合运算作用在到目前为止得在每个汇合点，把汇合运算作用在到目前为止得到的数据流值上，其中所用一些初值是人工引入到的数据流值上，其中所用一些初值是人工引入的的9.3 数据流分析的基础数据流分析的基础9.3.4数据流解的含义数据流解的含义MFP与与MOP的联系的联系MFP访问块未必遵循次序访问块未必遵循次序由初值和单调性保证一致由初值和单调性保证一致MFP较早地使用汇合运算较早地使用汇合运算MOPB4=(f3 f1)(vENTRY) (f3 f2)(vENTRY)INB4=f3(f1(vENTRY) f2(vENTRY)数据流分析框架具有分配性时，结果是一样的数据流分析框架具有分配性时，结果是一样的MFPMOPIDEALB1ENTRYB4B3B29.4 常常 量量 传传 播播9.4.1常量传播框架的数据流值常量传播框架的数据流值单个变量的数据流值半格单个变量的数据流值半格变量的类型所允许的所有常量变量的类型所允许的所有常量值值NAC表示不是常量表示不是常量值值UNDEF表示没有定义表示没有定义程序中各变量的程序中各变量的半格的积半格的积把程序中每个变量映射到把程序中每个变量映射到该半格上的一个值该半格上的一个值 UNDEFNAC 3 2 101239.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)都是常量值都是常量值 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 UNDEFNACNACUNDEFUNDEFc1c2c1+c2NACNACUNDEFNACNACc2NACNACNAC除了除了s的右部是的右部是y +z这种情况外，其它所这种情况外，其它所有情况，有情况，fs不改变不改变m(x)的值，或者改变到返的值，或者改变到返回一个常量回一个常量在这些情况下，在这些情况下，fs肯定是单调的肯定是单调的9.4 常常 量量 传传 播播9.4.4常量传播框架的非分配性常量传播框架的非分配性不管取什么路径，在块不管取什么路径，在块B3的出口，的出口，z的值是的值是5迭代算法在块迭代算法在块B3的入口而的入口而不是出口使用汇合运算不是出口使用汇合运算 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代替代替和执行路径和执行路径B1B3B4B5不符不符若程序正确的话，若程序正确的话，认为认为x在块在块B5入口的值入口的值只能为只能为10是合适的是合适的 ifQgotoB2B1B2B4B3x=10ifQ gotoB5B5B7B6=x9.5 部部 分分 冗冗 余余 删删 除除内容简介内容简介冗余计算以公共子表达式的形式出现，或以循环冗余计算以公共子表达式的形式出现，或以循环不变表达式的形式出现不变表达式的形式出现冗余可能只出现在一部分路径上冗余可能只出现在一部分路径上讨论最小化讨论最小化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是是完全冗余完全冗余的，的，因为所有到达因为所有到达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的副本来使的副本来使B4中的中的b+c完全冗余完全冗余 B1B2B4B3a=b+cd=b+cB1B2B4B3t=b+ct=b+ca=td=t9.5 部部 分分 冗冗 余余 删删 除除9.5.2能否删除所有的冗余能否删除所有的冗余B3B4是一条关键边：是一条关键边：源结点有多个后继源结点有多个后继目标结点有多个前驱目标结点有多个前驱B1B2B3B4d=b+ca=b+cB5B1B2B3B6t=b+ct=b+ca=tB5d=tB4增加新块增加新块9.5 部部 分分 冗冗 余余 删删 除除复制代码以删除冗余复制代码以删除冗余 B1B2B3B4a=b+cB5B6B7d=b+cB1B2B3B4t=b+ca=tB4 B5d=td=b+cB6B6 B79.5 部部 分分 冗冗 余余 删删 除除9.5.3惰性代码移动问题惰性代码移动问题部分冗余删除算法部分冗余删除算法优化后程序具有下列性质优化后程序具有下列性质无需通过复制代码就可删除的冗余计算都被删除无需通过复制代码就可删除的冗余计算都被删除若是部分冗余，则通过放置副本形成完全冗余若是部分冗余，则通过放置副本形成完全冗余优化后程序不会执行原来程序中没有的任何计算优化后程序不会执行原来程序中没有的任何计算表达式的计算尽可能推迟表达式的计算尽可能推迟 尽可能延迟值的计算就是最小化它的生存期，尽可能延迟值的计算就是最小化它的生存期，也就是最小化它占用寄存器的时间也就是最小化它占用寄存器的时间9.5 部部 分分 冗冗 余余 删删 除除9.5.4预期表达式预期表达式 预期的预期的不可用的不可用的B1 B2B5 B4c=2 B3B6B7d=b+ca=b+ ce=b+cB8B9B10B11 b+c部分冗余部分冗余 不可能提前到不可能提前到B1计算计算 B5的的计算不能计算不能再推迟再推迟 添加的计算最添加的计算最迟放在迟放在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+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) 需要定义需要定义可用可用表达式数据流问表达式数据流问题题 表达式在点表达式在点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 B3B6B7d=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支配结点支配结点结点结点d是结点是结点n的支配结点，的支配结点，如果从初始结点起，每条如果从初始结点起，每条到达到达n的路径都要经过的路径都要经过d，写成写成ddom n 每个结点是它本身的支配每个结点是它本身的支配结点结点 循环的入口是循环中所有循环的入口是循环中所有结点的支配结点结点的支配结点123456789109.6 流图中的循环流图中的循环1234567891012345678910深度优先生成树深度优先生成树9.6 流图中的循环流图中的循环9.6.2回边和可归约性回边和可归约性深度优先生成树深度优先生成树前进边前进边后撤边后撤边43、74、107、83和和91 交叉边交叉边23和和57 123456789109.6 流图中的循环流图中的循环9.6.2回边和可归约性回边和可归约性回边回边如果有如果有adom b，那么那么边边b a叫做回边叫做回边如果流图可归约，则如果流图可归约，则后撤边正好就是回边后撤边正好就是回边123456789109.6 流图中的循环流图中的循环9.6.2回边和可归约性回边和可归约性回边回边如果有如果有adom b，那么那么边边b a叫做回边叫做回边如果流图可归约，则如果流图可归约，则后撤边正好就是回边后撤边正好就是回边123456789109.6 流图中的循环流图中的循环9.6.2回边和可归约性回边和可归约性可归约可归约流图流图如果把一个流图中所有回边删掉后，剩余的图无如果把一个流图中所有回边删掉后，剩余的图无环环例例初始结点是初始结点是123和和32都不是回边都不是回边该图不是无环的该图不是无环的从结点从结点2和和3两处都能进入两处都能进入由它们构成的环由它们构成的环3219.6 流图中的循环流图中的循环9.6.3流图的深度流图的深度深度是在无环路径上的深度是在无环路径上的最大回边数最大回边数深度不大于流图中深度不大于流图中循环嵌套的层数循环嵌套的层数该例深度为该例深度为310743123456789109.6 流图中的循环流图中的循环9.6.4 自自然循环然循环自自然循环的性质然循环的性质 有唯一的入口结点，叫做有唯一的入口结点，叫做首结点首结点，首结点，首结点支配支配该循环中所有结点该循环中所有结点至少存在一条回边进入该循环首结点至少存在一条回边进入该循环首结点回边回边nd确定的自然循环确定的自然循环d加上不经过加上不经过d能到达能到达n的所有结点的所有结点结点结点d是该循环的首结点是该循环的首结点9.6 流图中的循环流图中的循环9.6.4 自自然循环然循环回边回边107循环循环7,8,10回边回边74循环循环4,5,6,7,8,10回边回边43和和83循环循环3,4,5,6,7,8,10回边回边911,2,3,4,5,6,7,8,9,10123456789109.6 流图中的循环流图中的循环内循环内循环 若一个循环的结点集合是另一个循环的结点集若一个循环的结点集合是另一个循环的结点集合的子集合的子集两个循环有相同的首结点两个循环有相同的首结点, ,但并非一个结点集是另一个但并非一个结点集是另一个的子集，则看成一个循环的子集，则看成一个循环1234本本 章章 要要 点点1、对各类优化的理解，包括常量合并、公共子表达式、对各类优化的理解，包括常量合并、公共子表达式删除、复写传播、死代码删除、循环优化等删除、复写传播、死代码删除、循环优化等2、到达定值、活跃变量、可用表达式等几种常用的、到达定值、活跃变量、可用表达式等几种常用的数据流抽象实例数据流抽象实例3、把各种数据流模式作为整体来抽象地研究的共同理把各种数据流模式作为整体来抽象地研究的共同理论框架论框架4、常量传播的特点、常量传播的特点5、最小化表达式计算次数的一种方法、最小化表达式计算次数的一种方法部分冗余删部分冗余删除方法除方法6、自然循环的概念及自然循环的识别、自然循环的概念及自然循环的识别例例 题题 1UNIX下下的的C编编译译命命令令cc的的选选择择项项g和和O的的解解释释如如下下,其其中中dbx的的 解解 释释 是是 “dbx is an utility for source-leveldebuggingandexecutionofprogramswritteninC”。试说明为什试说明为什么用了选择项么用了选择项g后，选择项后，选择项O便被忽略。便被忽略。-gProduceadditionalsymboltableinformationfordbx(1)anddbxtool(1)andpass-lgoptiontold(1)(soastoincludetheglibrary,thatis:/usr/lib/libg.a).Whenthisoptionisgiven,the-Oand-Roptionsaresuppressed.-OlevelOptimizetheobjectcode.Ignoredwheneither-g,-go,or-aisused.例例 题题 2一个一个C语言程序如下，右边是优化后的目标代码语言程序如下，右边是优化后的目标代码main()pushl%ebpmovl%esp,%ebpinti,j,k;movl$1,%eax-j=1i=5;movl$6,%edx-k=6j=1;L4:while(j100)addl%edx,%eax-j=j+6k=i+1;cmpl$99,%eaxj=j+k;jle.L4 -while(j 99)例例 题题 2一个一个C语言程序如下，右边是优化后的目标代码语言程序如下，右边是优化后的目标代码main()pushl%ebpmovl%esp,%ebpinti,j,k;movl$1,%eax-j=1i=5;movl$6,%edx-k=6j=1;L4:while(j100)addl%edx,%eax-j=j+6k=i+1;cmpl$99,%eaxj=j+k;jle.L4 -while(j 99) 完成了哪些完成了哪些优化？化？例例 题题 2一个一个C语言程序如下，右边是优化后的目标代码语言程序如下，右边是优化后的目标代码main()pushl%ebpmovl%esp,%ebpinti,j,k;movl$1,%eax-j=1i=5;movl$6,%edx-k=6j=1;L4:while(j100)addl%edx,%eax-j=j+6k=i+1;cmpl$99,%eaxj=j+k;jle.L4 -while(j 99)复写传播、常量合并、代码外提、删除无用赋值复写传播、常量合并、代码外提、删除无用赋值 对对i，j和和k分配内存单元也成为多余，从而被取消分配内存单元也成为多余，从而被取消例例 题题 3一个一个C语言程序语言程序main()longi,j;while(i)if(j)i=j;生成的汇编码见右边生成的汇编码见右边为什么会有连续跳转？为什么会有连续跳转？pushl%ebpmovl%esp,%ebpsubl$8,%esp.L2:cmpl$0,-4(%ebp)jne.L4jmp.L3.L4:cmpl$0,-8(%ebp)je.L5movl-8(%ebp),%eaxmovl%eax,-4(%ebp).L5:jmp.L2.L3:例例 题题 3whileE1doS1L2： E1的代码的代码真转真转L4无条件转无条件转L3L4： S1的代码的代码JMPL2L3:ifE2thenS2 E2的代码的代码假转假转L5S2的代码的代码L5：例例 题题 3whileE1doS1当它们嵌套时，代码结构变成当它们嵌套时，代码结构变成 L2： E1的代码的代码L2： E1的代码的代码真转真转L4真转真转L4 无条件转无条件转L3无条件转无条件转L3L4： S1的代码的代码L4： E2的代码的代码 JMPL2假转假转L5 L3:S2的代码的代码ifE2thenS2L5： JMPL2 E2的代码的代码L3： 假转假转L5S2的代码的代码L5：例例 题题 3whileE1doS1当它们嵌套时，代码结构变成当它们嵌套时，代码结构变成 L2： E1的代码的代码L2： E1的代码的代码真转真转L4真转真转L4 无条件转无条件转L3无条件转无条件转L3L4： S1的代码的代码L4： E2的代码的代码 JMPL2假转假转L5 L3:S2的代码的代码ifE2thenS2L5： JMPL2 E2的代码的代码L3： 假转假转L5S2的代码的代码L5：例例 题题 3whileE1doS1当它们嵌套时，代码结构变成当它们嵌套时，代码结构变成 L2： E1的代码的代码L2： E1的代码的代码真转真转L4真转真转L4 无条件转无条件转L3无条件转无条件转L3L4： S1的代码的代码L4： E2的代码的代码 JMPL2假转假转L5 L3:S2的代码的代码ifE2thenS2L5： JMPL2 E2的代码的代码L3： 假转假转L5S2的代码的代码L5：例例 题题 3whileE1doS1当它们嵌套时，代码结构变成当它们嵌套时，代码结构变成 L2： E1的代码的代码L2： E1的代码的代码真转真转L4真转真转L4 无条件转无条件转L3无条件转无条件转L3L4： S1的代码的代码L4： E2的代码的代码 JMPL2假转假转L5 L3:S2的代码的代码ifE2thenS2L5： JMPL2 E2的代码的代码L3： 假转假转L5S2的代码的代码L5：可优化为假转可优化为假转例例 题题 3一个一个C语言程序语言程序main()longi,j;while(i)if(j)i=j;优化编译的汇编码见右边优化编译的汇编码见右边pushl%ebpmovl%esp,%ebp.L7:testl%eax,%eaxje.L3testl%edx,%edxje.L7movl%edx,%eaxjmp.L7.L3:例例 题题 4求最大公约数的函数求最大公约数的函数longgcd(p,q)longp,q;if(p%q=0)returnq;elsereturngcd(q,p%q);其其中中的的递递归归调调用用称称为为尾尾递递归归. .对对于于尾尾递递归归, ,编编译译器器可可以以产产生生和和一一般般的的函函数数调调用用不不同同的的代代码码, ,使使得得目目标标程程序序运运行行时时, ,这这种种递递归归调调用用所所需需的的存存储储空空间间大大大大减减少少, ,也也缩缩短短了了运运行行时时间间. .对对于于尾尾递递归归, ,编编译译器器应应怎怎样样产产生生代码代码? ?例例 题题 4求最大公约数的函数求最大公约数的函数longgcd(p,q)longp,q;if(p%q=0)returnq;elsereturngcd(q,p%q);计计算算调调用用的的实实在在参参数数q和和p%q，存存放放在在不不同同的的寄存器中寄存器中将将上上述述寄寄存存器器中中实实在在参参数数的的值值存存入入当当前前活活动动记记录录中中形形式式参参数数p和和q的的存存储单元储单元转转到到本本函函数数第第一一条条语语句句的起始地址继续执行的起始地址继续执行例例 题题 4求最大公约数的函数求最大公约数的函数longgcd(p,q)longp,q;if(p%q=0)returnq;elsereturngcd(q,p%q);movl8(%ebp),%esipmovl12(%ebp),%ebxq.L4:movl%esi,%eaxcltdidivl%ebxmovl%edx,%ecxp%qtestl%ecx,%ecxp%qje.L2movl%ebx,%esiqpmovl%ecx,%ebxp%qqjmp.L4.L2:C语言程序引用语言程序引用sizeof（求字节数运算符）时，求字节数运算符）时，该运算是在编译该程序时完成，还是在运行该该运算是在编译该程序时完成，还是在运行该程序时完成？说明理由。程序时完成？说明理由。 例例 题题 5ProgramStmtStmtid:=Exp|read(id)|write(Exp)|Stmt;Stmt|while(Exp)dobeginStmtend|if(Exp)thenbeginStmtendelsebeginStmtendExpid|lit|ExpOPExp定义定义Stmt的两个属性的两个属性MayDef表示它可能定值的变量集合表示它可能定值的变量集合MayUse表示它可能引用的变量集合表示它可能引用的变量集合写一个语法制导定义或翻译方案，它计算写一个语法制导定义或翻译方案，它计算Stmt的上的上述述MayDef和和MayUse属性属性例例 题题 6Stmt id:=ExpStmt.MayDef=id.name;Stmt.MayUse=Exp.MayUseStmt read(id)Stmt.MayUse=;Stmt.MayDef=id.nameStmt write(Exp)Stmt.MayDef=;Stmt.MayUse=Exp.MayUse例例 题题 6Stmt Stmt1;Stmt2Stmt.MayUse=Stmt1.MayUse Stmt2.MayUse;Stmt.MayDef=Stmt1.MayDef Stmt2.MayDefStmt if(Exp)thenbeginStmt1endelsebeginStmt2endStmt.MayUse=Stmt1.MayUse Stmt2.MayUse Exp.MayUse;Stmt.MayDef=Stmt1.MayDef Stmt2.MayDef例例 题题 6Stmt while(Exp)dobeginStmt1endStmt.MayUse=Stmt1.MayUse Exp.MayUse;Stmt.MayDef=Stmt1.MayDefExpidExp.MayUse=id.nameExplitExp.MayUse=ExpExp1OPExp2Exp.MayUse=Exp1.MayUse Exp2.MayUse例例 题题 6基于基于MayDef和和MayUse属性属性,说明说明Stmt1;Stmt2和和Stmt2;Stmt1在什么情况下有同样的语义在什么情况下有同样的语义Stmt1.MayDef Stmt2.MayUse = andStmt2.MayDef Stmt1.MayUse = andStmt1.MayDef Stmt2. MayDef =例例 题题 6习习题题第一次：第一次：9.12,9.15第二次：第二次：9.18,9.25