文档介绍：机器无关优化
授课:胡静
8/28/20182004年12月28日
1
编译器的结构
出
错
处
理
语法分析程序
语义分析程序
目标代码生成程序
词法分析程序
中间代码生成程序
代码优化程序
表
格
管
理
8/28/2018
2
编译技术
引言
如果简单的把每个高级语言结构独立的翻译成机器代码,那么会带来相当大的运行时刻的开销。本章讨论如何消除这样的低效率因素——代码改进(代码优化)
在目标代码中消除不必要的指令
把一个指令序列替换为一个完成相同功能的较快的指令序列
上部分讲述了局部代码优化的问题,本部分主要简述全局优化问题。
考虑在多个基本块之间发生的事情。
8/28/2018
3
编译技术
本章基础
大部分全局优化是基于数据流分析(data-flow analyze)技术实现的。
数据流分析技术是一组用以收集程序相关信息的算法。
所有数据流分析的结果都具有相同的形式:对于程序中的每个指令,它们描述了该指令每次执行时必然成立的一些性质
不同性质的分析方法各不相同,比如,对于常量传播分析而言,要判断在程序的每个点上,程序使用的各个变量是否在该点上具有唯一的常量值。
活跃性分析确定在程序的每个点上,在某个变量中存放的值是否一定会在被读取之前被覆盖掉,如果是,我们就不需要在寄存器或内存位置上保留这个值。
8/28/2018
4
编译技术
本章结构
1、讨论一些主要的代码改进机会
2、介绍数据流分析技术
说明如何使用在全局内收集的信息来改进代码
3、介绍数据流框架的总体思想
上部分中的数据流分析是这个框架的特例
4、总体框架的例子,功能强大
5、“部分冗余消除”的技术,用于优化程序中各个表达式求值的位置。
6、讨论程序中循环的发现和分析
7、在对循环进行识别的基础上,介绍一个用来解决数据流问题的算法族
8、使用层次化分析来消除归纳变量(用来对循环的迭代次数进行计数的变量)
8/28/2018
5
编译技术
1、优化的主要来源
优化最基本的原则:必须保持源程序的语义。
编译器不可能完全理解一段程序的语义,并将其替换为一个全然不同而更加高效的等价程序。编译器只能利用一些相对低层的语义转换
使用常见的性质:i+0=i,或者一些程序语义(如在同样的值上进行同样的运算必然得到同样的结果)
8/28/2018
6
编译技术
、冗余的原因
源程序编写过程中出现的冗余
重新计算某些结果更加方便和直接
高级程序设计语言的副产品
例如数组访问。多次引用对某一个数组的访问,可能存在很多重复的计算。
高级程序设计语言屏蔽了低层具体的计算细节——程序容易书写、理解和演化
利用编译器来消除这些冗余,使程序获得高效——高级程序设计语言屏蔽的底层细节已知。
8/28/2018
7
编译技术
、本章会用到的一个例子
void quicksort(int m, int n)
{
int i, j;
int v, x;
if(n <=m) return;
i= m-1;j=n; v=a[n];
while(1)
{
do i = j+1; while(a[i]<v);
do j = j-1; while(a[j]>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]保存了最小元素,
a[max]保存了最大元素
8/28/2018
8
编译技术
、本章会用到的一个例子
例子中对地址的计算首先必须要被分解为低层次的算术运算,暴露出冗余之处。
假设中间表达式的结果都由临时变量来存放,并假设整数占用4个字节
赋值运算x=a[i]的三地址语句
t6=4*i
x=a[t6]
每个数组访问都被翻译成一对语句,一个乘法和一个数组下标运算
8/28/2018
9
编译技术
、本章会用到的一个例子
(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) if t3<v goto (5)
(9) j=j-1
(10) t4=4*j
(11) t5=a[t4]
(12) if t5>v goto(9)
(13) if i>=j goto (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