编译原理第九章代码优化ppt课件.ppt

《编译原理第九章代码优化ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章代码优化9.1代码优化概述9.2局部优化9.3控制流程分析和循环优化9.4数据流分析9.1代码优化概述代码优化代码优化的层次代码优化的评价代码优化实例代码优化：时空寄存器、多处理器、特殊指令优化等代码优化的层次窥孔优化：目标代码级别，滑动窗口局部优化：中间代码级别，以基本块为单位循环优化：目标代码级别，针对循环全局优化：中间代码级别，过程内代码优化评价优化效率：优化前后代码性能的提高基准测试程序，相同运行环境优化开销：优化所花费的代价：时间、存储空间等不同方法对不同程序的优化效果不同取决于程序本身的算法不同优化方法同时使用可能有副作用合并已知量常数传播代数化简强度削弱复写传播删除

2、多余运算循环不变代码外提变换循环控制条件删除无用赋值基本优化技术常数合并a=10*5-b;_tmp0=10;_tmp1=5;_tmp2=_tmp0*_tmp1;_tmp3=_tmp2–b;a=_tmp3;_tmp0=56;_tmp1=_tmp0–b;a=_tmp1;常数传播_tmp3=0;f0=_tmp3;f0=0;代数化简x+0=x0+x=xx*1=x1*x=x0/x=0x-0=xb&&true=bb&&false=falseb

3、

4、true=trueb

5、

6、false=b削弱运算强度a)i*2=2*i=i+i=i<<2b)i/2=(int)(i*0.5)c)f*2=2.0*f=f+f复

7、写传播tmp2=tmp1;tmp3=tmp2*tmp1;tmp5=tmp3*tmp2;tmp3=tmp1*tmp1;tmp5=tmp3*tmp1;(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=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)优化技术实例:P:=0forI:=1to20doP:=P+A[I]*B[I]①删除多余运算(6)T4:=T1②代码外提(1)P:=0(2)I:=1(4)T2:=

8、addr(A)-4(7)T5:=addr(B)-4③强度削弱(3’)T1:=T1+4(3)T1:=4④变换循环控制条件(12)ifT1<=80goto(5)⑤复写传播(8)T6:=T5[T1]⑥删除无用赋值(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3‘)T1:=T1+4(12)ifT1<=80goto(5)代码优化的理论基础相关的描述工具：中间表示：四元式DAG图控制流图数据流方程问题复杂度：往往是NP完全或NP难简化，小规模问题优化算

9、法…代码优化的基本过程代码的描述数据流分析(data-flowanalysis)控制流分析(control-flowanalysis)变换(transformations)基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。入口语句：程序的第一个语句；或者，条件转移语句或无条件转移语句的转移目标语句；或者紧跟在条件转移语句后面的语句。划分基本块的算法：求出四元式程序之中各个基本块的入口语句。对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括），或到一转移语句（包括），或到一停语句（包括）之间的语句序列组成的。凡未被纳入某一基本块的语句，把它们

10、删除。9.2局部优化：基本块内的优化(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB>=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt基本块内实行的优化:合并已知量删除多余运算删除无用赋值DAG(DirectedAcyclicGraph):无环有向图基本块的DAG是在结点上带有标记的DAG:一个基本块＝>一个DAG（体现基本块内各语句的联系）niXA，B，…结点形式：运算符（OP）---内部结点标识符常数叶结点标记编号变量A，…具有所代表的值基本块的DAG表示及其应用利用DAG进行基本块优化的基本思想是：

11、四元式序列=>DAG=>四元式序列四类四元式：0型四元式：后继结点个数为0，如图(1)所示；1型四元式：有一个后继结点，如图(2)所示；2型四元式：有两个后继结点，如图(3)(4)(5)3型四元式：有三个后继结点，如图(6)所示。图5–1四元式与DAG结点(1) T0=3.14(2) T1=2*T0(3) T2=R+r(4) A=T1*T2(5) B=A(6) T3=2*T0(7) T4=R+r(8) T5=T3*T4(9) T6=R−r(10