机器无关优化

《机器无关优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、机器无关优化授课：胡静编译器的结构出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理10/26/20212编译技术引言如果简单的把每个高级语言结构独立的翻译成机器代码，那么会带来相当大的运行时刻的开销。本章讨论如何消除这样的低效率因素——代码改进（代码优化）在目标代码中消除不必要的指令把一个指令序列替换为一个完成相同功能的较快的指令序列上部分讲述了局部代码优化的问题，本部分主要简述全局优化问题。考虑在多个基本块之间发生的事情。10/26/20213编译技术本章基础大部分全局

2、优化是基于数据流分析（data-flowanalyze）技术实现的。数据流分析技术是一组用以收集程序相关信息的算法。所有数据流分析的结果都具有相同的形式：对于程序中的每个指令，它们描述了该指令每次执行时必然成立的一些性质不同性质的分析方法各不相同，比如，对于常量传播分析而言，要判断在程序的每个点上，程序使用的各个变量是否在该点上具有唯一的常量值。活跃性分析确定在程序的每个点上，在某个变量中存放的值是否一定会在被读取之前被覆盖掉，如果是，我们就不需要在寄存器或内存位置上保留这个值。10/26/20214编译技术本章结构1

3、、讨论一些主要的代码改进机会2、介绍数据流分析技术说明如何使用在全局内收集的信息来改进代码3、介绍数据流框架的总体思想上部分中的数据流分析是这个框架的特例4、总体框架的例子，功能强大5、“部分冗余消除”的技术，用于优化程序中各个表达式求值的位置。6、讨论程序中循环的发现和分析7、在对循环进行识别的基础上，介绍一个用来解决数据流问题的算法族8、使用层次化分析来消除归纳变量（用来对循环的迭代次数进行计数的变量）10/26/20215编译技术1、优化的主要来源优化最基本的原则：必须保持源程序的语义。编译器不可能完全理解一段程

4、序的语义，并将其替换为一个全然不同而更加高效的等价程序。编译器只能利用一些相对低层的语义转换使用常见的性质：i+0=i，或者一些程序语义（如在同样的值上进行同样的运算必然得到同样的结果）10/26/20216编译技术1.1、冗余的原因源程序编写过程中出现的冗余重新计算某些结果更加方便和直接高级程序设计语言的副产品例如数组访问。多次引用对某一个数组的访问，可能存在很多重复的计算。高级程序设计语言屏蔽了低层具体的计算细节——程序容易书写、理解和演化利用编译器来消除这些冗余，使程序获得高效——高级程序设计语言屏蔽的底层细节已

5、知。10/26/20217编译技术1.2、本章会用到的一个例子voidquicksort(intm,intn){inti,j;intv,x;if(n<=m)return;i=m-1;j=n;v=a[n];while(1){doi=j+1;while(a[i]v);if(i>=j)break;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[j];a[j]=x;quicksort(m,j);quicksort(i+1,n)}a[0]保存了最小元素，

6、a[max]保存了最大元素10/26/20218编译技术1.2、本章会用到的一个例子例子中对地址的计算首先必须要被分解为低层次的算术运算，暴露出冗余之处。假设中间表达式的结果都由临时变量来存放，并假设整数占用4个字节赋值运算x=a[i]的三地址语句t6=4*ix=a[t6]每个数组访问都被翻译成一对语句，一个乘法和一个数组下标运算10/26/20219编译技术1.2、本章会用到的一个例子(1)i=m-1(2)j=n(3)t1=4*n(4)v=a[t1](5)i=i+1(6)t2=4*i(7)t3=a[t2](8)ift

7、3vgoto(9)(13)ifi>=jgoto(23)(14)t6=4*i(15)x=a[t6](16)t7=4*i(17)t8=4*j(18)t9=a[t8](19)a[t7]=t9(20)t10=4*j(21)a[t10]=x(22)goto(5)(23)t11=4*i(24)x=a[t11](25)t12=4*i(26)t13=4*n(27)t14=a[t13](28)a[t12]=t14(29)t15=4*n(30)

8、a[t15]=x10/26/202110编译技术1.2、本章会用到的一个例子i=m-1j=nt1=4*nv=a[t1]i=i+1t2=4*it3=a[t2]ift3vgoto(9)ifi>=jgoto(23)t6=4*ix=a[t6]t7=4*it8=4*jt9=a