机器无关优化

, ,啊, , ,啊, , ,*,*,机器无关优化,授课：胡静,9/23/2024,1,编译器的结构,出,错,处,理,语法分析程序,语义分析程序,目标代码生成程序,词法分析程序,中间代码生成程序,代码优化程序,表,格,管,理,9/23/2024,2,引言,如果简单的把每个高级语言结构独立的翻译成机器代码，那么会带来相当大的运行时刻的开销。本章讨论如何消除这样的低效率因素代码改进（代码优化）,在目标代码中消除不必要的指令,把一个指令序列替换为一个完成相同功能的较快的指令序列,上部分讲述了局部代码优化的问题，本部分主要简述全局优化问题。,考虑在多个基本块之间发生的事情。,9/23/2024,3,本章基础,大部分全局优化是基于数据流分析（data-flow analyze）技术实现的。,数据流分析技术是一组用以收集程序相关信息的算法。,所有数据流分析的结果都具有相同的形式：对于程序中的每个指令，它们描述了该指令每次执行时必然成立的一些性质,不同性质的分析方法各不相同，比如，对于常量传播分析而言，要判断在程序的每个点上，程序使用的各个变量是否在该点上具有唯一的常量值。,活跃性分析确定在程序的每个点上，在某个变量中存放的值是否一定会在被读取之前被覆盖掉，如果是，我们就不需要在寄存器或内存位置上保留这个值。,9/23/2024,4,本章结构,1、讨论一些主要的代码改进机会,2、介绍数据流分析技术,说明如何使用在全局内收集的信息来改进代码,3、介绍数据流框架的总体思想,上部分中的数据流分析是这个框架的特例,4、总体框架的例子，功能强大,5、“部分冗余消除”的技术，用于优化程序中各个表达式求值的位置。,6、讨论程序中循环的发现和分析,7、在对循环进行识别的基础上，介绍一个用来解决数据流问题的算法族,8、使用层次化分析来消除归纳变量（用来对循环的迭代次数进行计数的变量）,9/23/2024,5,1、优化的主要来源,优化最基本的原则：必须保持源程序的语义。,编译器不可能完全理解一段程序的语义，并将其替换为一个全然不同而更加高效的等价程序。编译器只能利用一些相对低层的语义转换,使用常见的性质：i+0=i，或者一些程序语义（如在同样的值上进行同样的运算必然得到同样的结果）,9/23/2024,6,1.1、冗余的原因,源程序编写过程中出现的冗余,重新计算某些结果更加方便和直接,高级程序设计语言的副产品,例如数组访问。多次引用对某一个数组的访问，可能存在很多重复的计算。,高级程序设计语言屏蔽了低层具体的计算细节程序容易书写、理解和演化,利用编译器来消除这些冗余，使程序获得高效高级程序设计语言屏蔽的底层细节已知。,9/23/2024,7,1.2、本章会用到的一个例子,void quicksort(int m, int n),int i, j;,int v, x;,if(n =m) return;,i= m-1;j=n; v=an;,while(1),do i = j+1; while(aiv);,if(i = j) break;,x=ai; ai=aj; aj=x;,x=ai; ai=aj; aj=x;,quicksort(m,j);quicksort(i+1, n),a0保存了最小元素，,amax保存了最大元素,9/23/2024,8,1.2、本章会用到的一个例子,例子中对地址的计算首先必须要被分解为低层次的算术运算，暴露出冗余之处。,假设中间表达式的结果都由临时变量来存放，并假设整数占用4个字节,赋值运算x=ai的三地址语句,t6=4*i,x=at6,每个数组访问都被翻译成一对语句，一个乘法和一个数组下标运算,9/23/2024,9,1.2、本章会用到的一个例子,(1)i = m -1,(2)j = n,(3) t1 = 4*n,(4)v=at1,(5)i=i+1,(6)t2=4*i,(7)t3=at2,(8)if t3v goto(9),(13)if i=j goto (23),(14)t6=4*i,(15)x=at6,(16)t7=4*i,(17)t8=4*j,(18)t9=at8,(19)at7=t9,(20)t10=4*j,(21)at10=x,(22)goto (5),(23)t11 = 4*i,(24)x=at11,(25)t12=4*i,(26)t13=4*n,(27)t14=at13,(28)at12=t14,(29)t15=4*n,(30)at15=x,9/23/2024,10,1.2、本章会用到的一个例子,i = m -1,j = n,t1 = 4*n,v=at1,i=i+1,t2=4*i,t3=at2,if t3v goto(9),if i=j goto (23),t6=4*i,x=at6,t7=4*i,t8=4*j,t9=at8,at7=t9,t10=4*j,at10=x,goto (5),t11 = 4*i,x=at11,t12=4*i,t13=4*n,t14=at13,at12=t14,t15=4*n,at15=x,B1,B2,B3,B4,B5,B6,B2,B3,B6,B2,9/23/2024,11,1.3、保持语义不变的转换,编译器可以使用多种方法改进程序，并保持语义不变,公共子表达式消除,复制传播,死代码消除,常量折叠,如右图所示，在这个块内，对,4*i和4*j进行了重复计算，虽然这些计算不是程序员显式要求的。,t6=4*i,x=at6,t7=4*i,t8=4*j,t9=at8,at7=t9,t10=4*j,at10=x,goto B2,B5,9/23/2024,12,1.4、全局公共子表达式,如果表达式E在某次出现之前已经被计算过了，,并且,E中的变量的值从那次计算之后就一直没有被改变，那么E的该次出现就称为一个,公共子表达式,。,局部公共子表达式的消除：,t6=4*i,x=at6,t7=4*i,t8=4*j,t9=at8,at7=t9,t10=4*j,at10=x,goto B2,B5,t6=4*i,x=at6,t8=4*j,t9=at8,at6=t9,at8=x,goto B2,B5,9/23/2024,13,t11 = 4*i,x=at11,t12=4*i,t13=4*n,t14=at13,at12=t14,t15=4*n,at15=x,B6,t6=4*i,x=at6,t8=4*j,t9=at8,at6=t9,at8=x,goto B2,B5,j=j-1,t4=4*j,t5=at4,if t5v goto B3,B3,t6=4*i,x=at6,t9=at4,at6=t9,at4=x,goto B2,B5,x=t3,t14=at1,at2=t14,at1=x,B6,x=t3,at2=t5,at4=x,goto B2,B5,i=i+1,t2=4*i,t3=at2,if t3v goto B2,B2,i = m -1,j = n,t1 = 4*n,v=at1,B1,不能用v代替,因为在进入B6之前有可能经过B5，对a进行了赋值,9/23/2024,14,1.5、复制传播,形如u=v这样的语句叫做复制语句，简称复制。这样的语句可以进一步的优化。,a = d + e,b = d + e,c = d + e,a = d + e,b = d + e,c = a,t = d + e,a = t,t = d + e,a = t,c = t,9/23/2024,15,1.5、复制传播,在复制语句u=v之后尽可能的用,v,来代替,u,。,x=t3,at2=t5,at4=x,goto B2,B5,x=t3,at2=t5,at4=t3,goto B2,B5,给了我们消除死代码的机会（对x的赋值）,9/23/2024,16,1.6、死代码消除,如果一个变量在某个程序点上的值可能会在以后被使用，那么我们就说这个变量在该点上活跃。否则它在该点上就是死的。,所谓死代码就是其计算结果永远不会被使用的语句。,死代码多半是因为前面执行过的某些转换造成的。,例如if (debug) print,如果在判断之前，总有一个语句debug = FALSE;那么print语句就不可能被执行到。就可以把这个测试和print语句从目标代码中全部消除。,更一般的说，如果编译时刻推导出一个表达式的值是常量，就可以用常量来代替这个表达式常量折叠。,9/23/2024,17,1.6、死代码消除,复制传播的一个好处就是常会把一些复制语句变为死代码,x=t3,at2=t5,at4=t3,goto B2,B5,at2=t5,at4=t3,goto B2,B5,9/23/2024,18,1.7、代码移动,对于优化工作而言，循环（尤其是循环内部）是一个重要的地方，因为程序常常会将它们的大部分时间花费在这上面。,如果我们减少一个内部循环中的指令个数，即使因此曾加了该循环外的代码，程序的运行时间也会减少。,减少循环内部代码数量的一个重要改动是代码移动。,处理的是那些不管循环执行多少次都得到相同结果的表达式循环不变计算,在进入循环之前就对它们求值。所谓“在循环之前”的说法假设了存在一个循环入口。所谓循环入口就是一个基本块，所有循环外部到循环的跳转指令都以它为目标。,9/23/2024,19,1.7、代码移动,例子：,while(i =limit-2) 进行代码移动后得到如下等价代码：,t = limit-2,while(iv goto B3,B3,i=i+1,t2=4*i,t3=at2,if t3=j goto B6,B4,at2=t5,at4=t3,goto B2,B5,t14=at1,at2=t14,at1=t3,B6,j=j-1,t4=t4-4,t5=at4,if t5v goto B3,B3,i = m -1,j = n,t1 = 4*n,v=at1,t4 = 4*j,B1,9/23/2024,22,i = m -1,j = n,t1 = 4*n,v=at1,t4=4*j,t2=4*i,B1,t4=t4-4,t5=at4,if t5v goto B3,B3,t2=t2+4,t3=at2,if t3=t4 goto B6,B4,at2=t5,at4=t3,goto B2,B5,t14=at1,at2=t14,at1=t3,B6,9/23/2024,23,Thanks for your time!,Questions & Answers,9/23/2024,24,