哈里伯顿内部材料.ppt

哈里伯顿内部材料.ppt第八章代码优化
逐条语句进行的代码生成策略经常产生含有大量冗余指令和次最优结构的目标代码。
1
1、源程序级:局部优化、循环优化、全局优化
1、节省时间 2、节省空间
二、优化技术
一、优化目的
2、目标代码级的优化
三、优化原则
1、等价原则
2、有效原则
3、合算原则
2
Void quicksort(a,m,n);
Int m,n,a[];
{ int I,j;
int v,x;
if(n<=m) return;
I=m-1;j=n;v=a[n]
While(1){
Do {I=I+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[n];a[n]=x;
Quicksort(m,j);quicksort(I+1,n); }
例:快速排序程序
优化的主要种类
3
i=m-1
j=n
t1=4*n
v=a[t1]
i=i+1
t2=4*i
t3=a[t2]
If t3<v goto B2
j=j-1
t4=4*j
t5=a[t4]
If t5<v goto B3
If I>=j goto b6
t11=4*I
x=a[t11]
t12=4*I
t13=4*n
t14=a[t13]
a[12]=t14
t14=4*n
a[15]=x
t6=4*I
x=a[t6]
t7=4*i
t8=4*j
t9=a[t8]
a[t7]=t9
t10=4*j
a[t10]x
goto b2
中间代码程序段
B1
B6
B5
B4
B3
B2
i=m-1
j=n
t1=4*n
v=a[t1]
i=i+1
t2=4*i
t3=a[t2]
if t3<v goto B2
j=j-1
t4=4*j
t5=a[t4]
if t5<v goto B3
if i>=j goto B6
t11=4*I
x=a[t11]
t12=4*I
t13=4*n
t14=a[t13]
a[12]=t14
t14=4*n
a[15]=x
t6=4*I
x=a[t6]
t7=4*i
t8=4*j
t9=a[t8]
a[t7]=t9
t10=4*j
a[t10]x
goto b2
4
如果一个表达式E在前面已经定义过,
对于公共子表达式,避免对它的重复计算,称为删除公共子表达式
一、删除公共子表达式
并且在这之后E中的变量的值没有改变,
则称E为公共子表达式
5
t6=4*i
x=a[t6]
t7=4*i
t8=4*j
t9=a[t8]
a[t7]=t9
t10=4*j
a[t10]=x
goto b2
t6=t2
x=a[t6]
t7=t6
t8=t4
t9=a[t8]
a[t7]=t9
t10=t8
a[t10]=x
goto b2
删除公共子表达式
B5
在B2中t2=4*i; 在B3 中t4=4*j
6
t11=t2
x=a[t11]
t12=t11
t13=t1
t14=a[t13]
a[12]=t14
t14=t13
a[15]=x
t11=4*i
x=a[t11]
t12=4*i
t13=4*n
t14=a[t13]
a[12]=t14
t14=4*n
a[15]=x
删除公共子表达式
B6
在B1中t1=4*n;
7
在B5中t6=t2,而x=a[t6]中引用了t6,
二、复写传播。
这种变换称为复写传播。
而在
这中间t6的值没有被改变,
因此可以把x=a[t6]改写为x=a[t2],
8
i=m-1
j=n
t1=4*n
v=a[t1]
i=i+1
t2=4*i
t3=a[t2]
if t3<v goto B2
j=j-1
t4=4*j
t5=a[t4]
tf t5<v goto B3
if I>=j goto B6
t11=t2
x=t3
t12=t2
t13=t1
t14=v
a[t2]=v
t15=t1
a[t1]=t3
t6=t2
x=t3
t7=t2
t8=t4
t9=t5
a[t2]=t5
t10=t4
a[t4]=t3
goto B2
复写传播后
B1
B6
B5
B4
B3
B2
t6=t2
x=t3
t7=t2
t8=t4
t9=t5
a[t2]=t5
t10=t4
a[t4]=t3
goto B2
t11=t2
x=t3
t12=t2
t13=t1
t14=v
a[t2]=v
t15=t1
a[t1]=t3
9
复写传播的目的是使某些变量的赋值变为无用
三、删除无用表达式
对B5进行复写传播后,
在整个程序