《编译原理 第九章 代码优化》由会员分享，可在线阅读，更多相关《编译原理 第九章 代码优化（31页珍藏版）》请在金锄头文库上搜索。
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 = x 0+x = x x*1 = x 1*x = x 0/x = 0 x-0
3、= x b & true = b b & false = false b | true = true b | false = b,削弱运算强度,a) i*2 = 2*i = i+i = i2 b) i/2 = (int)(i*0.5) c) f*2 = 2.0 * f = f + f,复写传播,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:
4、=T2T1 (6) T4:=4*I (7) T5:=addr(B)-4 (8) T6:=T5T4 (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (12) if I=20 goto(3),优化技术实例: P:=0 for I:=1 to 20 do P:=P+AI*BI,删除多余运算,(6) T4:=T1,代码外提,强度削弱,变换循环控制条件,(12) if T1=80 goto(5),复写传播,(8) T6:= T5T1,删除无用赋值,(1) P:=0 (4) T2:=addr(A)-4 (7) T5:=addr(B)-4 (3) T1:=4,(5) T3:=T
5、2T1 (8) T6:=T5T1 (9) T7:=T3*T6 (10) P:=P+T7 (3)T1:=T1+4 (12) if T1=80 goto(5),代码优化的理论基础,相关的描述工具： 中间表示：四元式 DAG图 控制流图 数据流方程 问题复杂度：往往是NP 完全或NP难 简化，小规模问题 优化算法 ,代码优化的基本过程,代码的描述 数据流分析(data-flow analysis) 控制流分析(control-flow analysis) 变换 (transformations),基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。 入口语句： 程序的第一个语
6、句；或者， 条件转移语句或无条件转移语句的转移目标语句；或者 紧跟在条件转移语句后面的语句。 划分基本块的算法： 求出四元式程序之中各个基本块的入口语句。 对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括），或到一转移语句（包括），或到一停语句（包括）之间的语句序列组成的。 凡未被纳入某一基本块的语句，把它们删除。,9.2 局部优化：基本块内的优化,(1) read (C) (2) A:= 0 (3) B:= 1 (4) L1: A:=A + B (5) if B= C goto L2 (6) B:=B+1 (7) goto L1 (8) L2: write (A) (9
7、) halt,基本块内实行的优化: 合并已知量 删除多余运算 删除无用赋值,DAG(Directed Acyclic Graph): 无环有向图 基本块的DAG是在结点上带有标记的DAG:,一个基本块一个DAG（体现基本块内各语句的联系）,ni,X,A，B，,结点形式：,运算符（OP）-内部结点,标识符,常数,叶结点,标记,编号,变量A，具有所代表的值,基本块的DAG表示及其应用,利用DAG进行基本块优化的基本思想是： 四元式序列 = DAG = 四元式序列 四类四元式： 0型四元式：后继结点个数为0，如图 (1)所示； 1型四元式：有一个后继结点，如图(2)所示； 2型四元式：有两个后继结点
8、，如图(3)(4)(5) 3型四元式：有三个后继结点，如图(6)所示。,图51 四元式与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= Rr (10) B=T5*T6,(1) T0=3.14 (2) T1=6.28 (3) T3=6.28 (4) T2=R+r (5) T4=T2 (6) A=6.28*T2 (7) T5=A (8) T6= Rr (9) B=A*T6,若T0、T1、T6在基本快后面不被引用，则： (1) T2=R+r
9、 (2) A=6.28*T2 (3) T6= Rr (4) B=A*T6,9.3 控制流分析和循环优化,一个控制流程图(简称流图)就是具有惟一首结点的有向图。所谓首结点，就是从它开始到控制流程图中任何一个结点都有一条通路的结点。,例如，考察下面求最大公因子的三地址代码程序： *(1) read X (2) read Y *(3) R=X % Y (4) if(R=0) goto(8) *(5) X=Y (6) Y=R (7) goto(3) *(8) write Y (9) halt,循环的查找,循环优化,寻找循环,循环定义,直观上循环的构成,=,=,直观上，入口结点是循环中其它结点的必经结点
10、。 在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n (a,a DOM a) 结点n的所有必经结点的集合,称为结点n的必经结点集D(n).,D(1)=1 D(2)=1，2 D(3)=1，2，3 D(4)=1，2，4 D(5)=1，2，4，5 D(6)=1，2，4，6 D(7)=1，2，4，7,回边：ab是流图中的一条有向边，如果b DOM a 。,回边：6 -6、7-4、4-2,循环：回边ab组成的循环是由结点b、a以及有通路到达a而该通路不经过b的所有结点组成，并且b是该循环的唯一入口结点。,6,4,5,6,7,
11、2,3,4,5,6,7,图58 给循环建立前置结点,9.3 代码优化示例,通过一个快速排序子程序来了解代码优化的全过程。 void quicksort (int m, int n) int i, j, v, x; if(n=m) return; /*fragment begins here*/ i=m1; j=n; v=an; while(1) do i=i+1; while(aiv);,do j=j1; while(ajv); if(i=j) break; x=ai; ai=aj; aj=x; x=ai; ai=an; an=x; /*fragment ends here*/ quickso
12、rt(m, j); quicksort(i+1,n); ,图521给出了程序中两个注解行之间的语句翻译成中间代码序列后所对应的程序流图，其代码优化如下。 1删除公共子表达式 在B5中分别把公共子表达式4*i和4*j的值赋给T7和T10，因此这种重复计算可以消除，即B5中的代码变换成：,B5:T6=4*i x=aT6 T7=T6 T8=4*j T9=aT8 aT7=T9 T10=T8 aT10=x goto B2,可以在更大范围内来考虑删除公共子表达式的问题，即利用B3中的四元式T4= 4*j可以把B5中的代码T8= 4*j替换为T8= T4。 同样，可以把B5中的代码T6= 4*i替换为T6=
13、T2。对于B6也可以同样考虑，最后，删除公共子表达式后的程序流图如图522所示。,图521 程序流图,T6=T2 x=aT6 T7=T6 T8=T4 T9=aT8 aT7 = T9 T10=T8 aT10 =x goto B2,T11=T2 x=aT11 T12=T11 T13=T1 T14=aT13 aT12 = T14 T15=T1 aT15 =x,图522 删除公共子表达式后的程序流图,2复写传播 图522中的B5还可以把x=aT6变换为x=aT2。这种变换称为复写传播。B5变为：,T6=T2 x=aT2 T7=T2 T8=T4 T9=aT4 aT2= T9 T10=T4 aT4=x g
14、oto B2,进一步，在B5中可把x=aT2替换为x=T3，并继续通过复写传播，把B5中的aT4=x替换为aT4 =T3。同样，把B5中的T9=aT4替换为T9=T5，aT2=T9替换为 aT2=T5。B5变为：,T6=T2 x= T3 T7=T2 T8=T4 T9=T5,aT2= T5 T10=T4 aT4= T3 goto B2,3删除无用赋值 进行了复写传播后的B5，其中的变量x及临时变量T6、T7、T8、T9、T10在整个程序中不再使用，故可以删除对这些变量赋值的四元式。B5变为： aT2= T5 aT4= T3 goto B2 对B6进行相同的处理后变为： aT2= v aT1= T
15、3 复写传播和删除无用赋值后的程序流图如图5-23所示。,图523 复写传播和删除无用赋值后的程序流图,4代码外提：没有可外提到循环之外的不变运算。 5强度削弱 观察图523的内循环B3，可以把循环中计算T4值的乘法运算变为在循环前进行一次乘法运算而在循环中进行减法运算。同样，对循环B2中的T2=4*i也可以进行强度削弱。经过强度削弱后的程序流图如图5-24所示。 6删除归纳变量 由图524可知，B2中T2与i之间保持着T2=4*i的线性关系；而B3中T4与j之间保持着T4=4*j的线性关系。在对T2=4*i和T4=4*j进行了强度削弱后，i和j仅出现在条件句if Ij goto B6中。因此，可以变换归纳变量而把此条件句变换为：if T2T4 goto B6。经过这种变换，我们又可以将无用赋值i=i+1和j=j1删去。最后如图525所示。试与开始时比较,图524 强度削弱后的程序流图,图525 删除归纳变量后的程序流图,
