编译原理 第11章(清华大学1

《编译原理 第11章(清华大学1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11章代码优化11．1什么是代码优化11．2局部优化11．3控制流程分析和循环11．4数据流分析举例何谓代码优化：宗旨：获得较好性能的代码等价意图，结果，权衡阶段：sourcefrontI.Rcodetargetcodeendgeneratorcode用户中间代码优化目标代码优化intarr[10000];voidBinky(){inti;for(i=0;i<10000;i++)arr[i]=1;}intarr[10000];voidWinky(){registerint*p;for(p=arr;p

2、++)*p=1;}优化分类按阶段分:与机器无关的优化---对中间代码进行依赖于机器的优化--对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优化(3)全局优化:大范围的优化优化工作数据流分析(control-flowanalysis)控制流分析(data-flowanalysis)变换(transformations)优化技术简介—常数合并a=10*5+6-b;_tmp0=10;_tmp1=5;_tmp2=_tmp0*_tmp1;_tmp3=6;_tmp4=_tmp2

3、+_tmp3;_tmp5=_tmp4–b;a=_tmp5;_tmp0=56;_tmp1=_tmp0–b;a=_tmp1;优化技术简介—常数传播_tmp4=0;f0=_tmp4;_tmp5=1;f1=_tmp5;_tmp6=2;i=_tmp6;f0=0;f1=1;i=2;优化技术简介—代数简化x+0=x0+x=xx*1=x1*x=x0/x=0x-0=xb&&true=bb&&false=falseb

4、

5、true=trueb

6、

7、false=b优化技术简介—代数简化b=5+a+10;_tmp0=5;_tmp1=_tmp0+a;_t

8、mp2=_tmp1+10;b=_tmp2;_tmp0=15;_tmp1=a+_tmp0;b=_tmp1;优化技术简介—降低运算强度a)i*2=2*i=i+i=i<<2b)i/2=(int)(i*0.5)c)0-1=-1d)f*2=2.0*f=f+fe)f/2.0=f*0.5优化技术简介—复写传播tmp2=tmp1;tmp3=tmp2*tmp1;tmp4=tmp3;tmp5=tmp3*tmp2;c=tmp5+tmp4;tmp3=tmp1*tmp1;tmp5=tmp3*tmp1;c=tmp5+tmp3;main(){intx,

9、y,z;x=(1+20)*-x;y=x*x+(x/y);y=z=(x/y)/(x*x);}tmp1=1+20;tmp2=-x;x=tmp1*tmp2;tmp3=x*x;tmp4=x/y;y=tmp3+tmp4;tmp5=x/y;tmp6=x*x;z=tmp5/tmp6;y=z;优化技术简介1.删除多余运算2.循环不变代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播6.删除无用赋值P:=0forI:=1to20doP:=P+A[I]*B[I](1)P:=0(2)I:=1(3)T1:=4*I(4)T2:

10、=addr(A)-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)(1)P:=0(2)I:=1(3)T1:=4*I(5)T3:=T2[T1](8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T1(1)P:=0(2)

11、I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(5)(

12、3)T1:=4*I(3‘)T1:=T1+4(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1