chapter9.ppt

第九章 独立于机器的优化,第九章 独立于机器的优化,代码优化通过程序变换（局部变换和全局变换）来改进程序，称为优化代码改进变换的标准代码变换必须保程序的含义采取安全稳妥的策略变换减少程序的运行时间平均达到一个可度量的值变换所作的努力是值得的,第九章 独立于机器的优化,本章介绍独立于机器的优化，即不考虑任何依赖目标机器性质的优化变换 通过实例来介绍代码改进的主要机会 数据流分析包括的几类重要的全局收集的信息 数据流分析的一般框架 和一般框架有区别的常量传播 部分冗余删除的优化技术 循环的识别和分析,9.1 优化的主要种类,9.1.1 优化的主要源头程序中存在许多程序员无法避免的冗余运算对于Aij和X.f1这样访问数组元素和结构体的域的操作（例如，Aij=Aij+10）随着程序被编译，这些访问操作展开成多步低级算术运算对同一个数据结构的多次访问导致许多公共的低级运算程序员没有办法删除这些冗余,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 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 优化的主要种类,程序流图,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=xgoto B2,9.1 优化的主要种类,局部公共子表达式删除,复写传播,删除死代码B5 x=ai;ai=aj;aj=x;,t6=4 ix=at6t7=4 i t8=4 jt9=at8at7=t9t10=4 jat10=xgoto B2,t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgoto B2,9.1 优化的主要种类,9.1 优化的主要种类,全局公共子表达式删除,复写传播,删除死代码B5 x=ai;ai=aj;aj=x;,t6=4 ix=at6t7=4 i t8=4 jt9=at8at7=t9t10=4 jat10=xgoto B2,t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgoto B2,9.1 优化的主要种类,全局公共子表达式删除,复写传播,删除死代码B5 x=ai;ai=aj;aj=x;,t6=4 ix=at6t7=4 i t8=4 jt9=at8at7=t9t10=4 jat10=xgoto B2,t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgoto B2,x=at2t9=at4at2=t9at4=xgoto B2,9.1 优化的主要种类,9.1 优化的主要种类,全局公共子表达式删除,复写传播,删除死代码B5 x=ai;ai=aj;aj=x;,t6=4 ix=at6t7=4 i t8=4 jt9=at8at7=t9t10=4 jat10=xgoto B2,t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgoto B2,x=at2t9=at4at2=t9at4=xgoto B2,9.1 优化的主要种类,全局公共子表达式删除,复写传播,删除死代码B5 x=ai;ai=aj;aj=x;,t6=4 ix=at6t7=4 i t8=4 jt9=at8at7=t9t10=4 jat10=xgoto B2,t6=4 ix=at6t8=4 jt9=at8at6=t9at8=xgoto B2,x=at2t9=at4at2=t9at4=xgoto B2,x=t3at2=t5at4=xgoto B2,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=x,9.1 优化的主要种类,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,9.1 优化的主要种类,i=m 1j=nt1=4 nv=at1,i=i+1t2=4 it3=at2if t3 v goto B2,B1,B2,j=j 1t4=4 jt5=at4if t5 v goto B3,if i=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=t3at2=t5at4=t3goto B2,x=t3at2=t5at4=xgoto B2,9.1 优化的主要种类,9.1.4 复写传播复写语句：形式为f=g的赋值优化过程中会大量引入复写复写传播变换的做法是在复写语句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 靠优化来保证目标代码中没有该条件语句部分,9.1 优化的主要种类,9.1.5 死代码删除死代码是指计算的结果决不被引用的语句一些优化变换可能会引起死代码例：复写传播可能会引起死代码删除B5,x=t3at2=t5at4=t3goto B2,at2=t5at4=t3goto B2,x=t3at2=t5at4=xgoto B2,9.1 优化的主要种类,9.1.6 代码外提代码外提是循环优化的一种循环优化的其它重要技术归纳变量删除强度削弱例：while(i=limit 2)代码外提后变换成t=limit 2;while(i=t),9.1 优化的主要种类,9.1.7 强度削弱和归纳变量删除j和t4的值步伐一致地变化这样的变量叫做归纳变量在循环中有多个归纳变量时，也许只需要留下一个这个操作由归纳变量删除 过程来完成对本例可以先做强度削弱 它给删除归纳变量创造机会,9.1 优化的主要种类,j=j 1t4=4 jt5=at4if 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 数据流抽象流图上的点基本块中，两个相邻的语句之间为程序的一个点基本块的开始点和结束点流图上的路径点序列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,3,4,5,6,7,8,3,4,5,6,7,8,)路径长度无限-路径数无限,9.2 数据流分析介绍,9.2.1 数据流抽象 分析程序的行为时，必须在其流图上考虑所有的执行路径（在调用或返回语句被执行时，还需要考虑执行路径在多个流图之间的跳转）-通常，从流图得到的程序执行路径数无限，且执行路径长度没有有限的上界,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)不是 常量,9.2 数据流分析介绍,9.2.3 到达-定值到达一个程序点的所有定值可用来判断一个变量在某程序点是否为常量可用来判断一个变量在某程序点是否无初值别名给到达-定值的计算带来困难过程参数、数组访问、间接引用等都有可能引起别名例如：若p=q，则p-next和q-next互为别名程序分析必须是稳妥的本章其余部分仅考虑变量无别名的情况,9.2 数据流分析介绍,9.2.3 到达-定值到达一个程序点的所有定值可用来判断一个变量在某程序点是否为常量可用来判断一个变量在某程序点是否无初值别名给到达-定值的计算带来困难定值的注销在一条执行路径上，对x的赋值注销先前对x的所有赋值,9.2 数据流分析介绍,gen和kill分别表示一个基本块生成和注销的定值,gen B1=d1,d2,d3kill B1=d4,d5,d6,d7,gen B2=d4,d5kill B2=d1,d2,d7,gen B3=d6kill B3=d3,gen B4=d7kill 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有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和OUT）INB=P是B的前驱 OUTP OUTB=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,d3kill B1=d4,d5,d6,d7,gen B2=d4,d5kill B2=d1,d2,d7,gen B3=d6kill B3=d3,gen B4=d7kill B4=d1,d4,9.2 数据流分析介绍,IN B OUT B B1 000 0000 000 0000 B2 000 0000 B3 000 0000 B4 000 0000,gen B1=d1,d2,d3kill B1=d4,d5,d6,d7,gen B2=d4,d5kill B2=d1,d2,d7,gen B3=d6kill B3=d3,gen B4=d7kill 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,d3kill B1=d4,d5,d6,d7,gen B2=d4,d5kill B2=d1,d2,d7,gen B3=d6kill B3=d3,gen B4=d7kill 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,d3kill B1=d4,d5,d6,d7,gen B2=d4,d5kill B2=d1,d2,d7,gen B3=d6kill B3=d3,gen B4=d7kill 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,d3kill B1=d4,d5,d6,d7,gen B2=d4,d5kill B2=d1,d2,d7,gen B3=d6kill B3=d3,gen B4=d7kill B4=d1,d4,9.2 数据流分析介绍,IN B OUT B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 001 1100 000 0000 B4 000 0000,gen B1=d1,d2,d3kill B1=d4,d5,d6,d7,gen B2=d4,d5kill B2=d1,d2,d7,gen B3=d6kill B3=d3,gen B4=d7kill 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,d3kill B1=d4,d5,d6,d7,gen B2=d4,d5kill B2=d1,d2,d7,gen B3=d6kill B3=d3,gen B4=d7kill B4=d1,d4,