编译原理PPT课件第六章中间代码优化.ppt

《编译原理PPT课件第六章中间代码优化.ppt》由会员分享，可在线阅读，更多相关《编译原理PPT课件第六章中间代码优化.ppt（43页珍藏版）》请在三一办公上搜索。

1、局部优化 循环优化,优化目的:提高运行速度,减少存储空间.,第六章 中间代码优化,内容:,第一节 优化概述,2,右面为循环的中间代码:对该段中间代码,可以进行如下优化:1 删除多余运算 见(3),(6)两四元式的 4*I,(6)可以改写为:T4:=T1,从而减少了一次乘法.参见下页四元式表,(1)PROD:=0(2)I:=1,(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)if I=20 goto(3),3,(

2、1)PROD:=0(2)I:=1,(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=T1(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)if I=20 goto(3),2代码外提(4)与(7)每次循环其值都不变,称为循环不变量.可以放到循环前,减少循环中的运算.参见下页四元式表,4,(1)PROD:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4,(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9

3、)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)if I=20 goto(3),3强度削弱 由于每次循环 I 都增加 1,因此,T1递增 4,可把(3)改为T1:=T1+4,放在(11)之后,并在循环前对 I 赋初值 T1:=4*I.(12)改为 goto(5).参见下页四元式表,5,(1)PROD:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I,(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(3)T1:=T1+

4、4(12)if I=20 goto(5),4变换控制条件 由于 I 只用作循环控制,而 T1=4*I,因此,可用 T1 替换 I,I=20 等价于 T1=80,把(12)改为 if T1=80 goto(5)这样,可以删掉无用的 I.参见下页四元式表,6,(1)PROD:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I,(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(3)T1:=T1+4(12)if T1=80 goto(5),5合并已知量 由于(3)中的 I 在(2

5、)赋值后仍然为 1,因此可改为:T1:=46 复写(6)中 T1 复制到 T4,而(6)到(8)之间没有改变T1 和 T4,因此(8)可以改为:T6:=T5T1,从而使(6)式无用.参见下页四元式表,7,(1)PROD:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4,(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1(9)T7:=T3*T6(10)PROD:=PROD+T7(3)T1:=T1+4(12)if T1=80 goto(5),7删除无用赋值(2)和(6)两四元式为无用四元式,可以删除.最终优化后,得到下页四元式表,8,(

6、1)PROD:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4,(5)T3:=T2T1(8)T6:=T5T1(9)T7:=T3*T6(10)PROD:=PROD+T7(3)T1:=T1+4(12)if T1=80 goto(5),(1)PROD:=0(2)I:=1,(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)if I=20 goto(3),优化前优化后,9,第二节 局部优

7、化,局部优化是指局限于基本块内的优化.一 基本块1 定义:基本块是一顺序执行的中间代码序列,仅包含一个入口 四元式 和一个出口四元式,第一条四元式为入口四元式,最后 一条四元式为出口四元式.中间部分不含转移四元式.2 基本块的划分 给定一四元式程序,可以通过如下算法,划分基本块:,10,基本块划分算法:1)求四元式程序中所有基本入口四元式,包括:a)程序的第一条四元式;b)转移语句转移到的四元式;c)条件语句之后的第一条四元式.2)对每一入口四元式,构造一个基本块:从该入口四元式到下一入口四元式之前的一条四元式,或到一转移语句,或到一停止语句之间的四元式序列 组成.3)凡未纳入这些基本块的四元

8、式,为无用四元式,可以删除.,11,示例:设四元式程序如下:(1)read(X)(2)read(Y)(3)R:=X MOD Y(4)if R=0 goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)write(Y)(9)halt,基本入口四元式包括:(1)程序第一条四元式(3)转移语句转移到的四元式(5)条件语句之后的第一条四元式(8)转移语句转移到的四元式由此可以得到四个基本块.(见下页),12,(8)write(Y)(9)halt,(1)read(X)(2)read(Y),(3)R:=X MOD Y(4)if R=0 goto(8),(5)X:=Y(6)Y:=R(7)got

9、o(3),B1,B2,B3,B4,13,二 基本块内的优化 基本块内可以进行以下几种优化:合并已知量,删除多余运算(公共子表达式)删除无用赋值 优化手段:DAG 1 DAG 的定义 DAG 是有向无环路图的简称,结点的基本形式如右图:n i 为结点名,val 为结点值标记,op 为结点的运算.,n i,ni1,ni2,op,val,14,2 四元式的 DAG 表示 考虑下面三种类型的四元式,DAG表示如右所示0 型:(:=,B,A)1 型:(op,B,A)2 型:(op,B,C,A),n i,B,A,n i,n k,A,B,op,A,n i,ni1,ni2,B,C,op,15,3 基本块的 D

10、AG 构造算法及优化令 NODE(A)=若 DAG 中存在值标记为 A 的结点 n,则返回 n;否则 返回 null.基本块的 DAG 构造算法如下:(1)令 DAG=null(2)for 基本块的 每一四元式 do 若 NODE(A)未被引用,或有多个值标记,则 删除 值标记 A;/(删除无用赋值)根据四元式类型,分别转到 T0,T1,T2 处 T0:/(:=,B,A)若NODE(B)=null 生成值标记为 B 的叶结点 n否则 令 n=NODE(B);把 A 添加在 n 结点的右侧;返回(2),16,T1:/(op,B,A)若 B 为已知量/合并已知量 执行 op B,得到一新常数 p,

11、若NODE(p)=null 生成值标记为 p 的叶结点 n 否则 令 n=NODE(p);把 A 添加在 n 结点的右侧;返回(2)否则 若 DAG 中存在型如右式的子图 则把 A 添加在 n 结点的右侧;返回(2)/合并多余运算 否则 若NODE(B)=null 生成值标记为 B 的叶结点 n1 否则 令 n1=NODE(B);建立一运算为 op,值标记为 A 的结点 n,从 n 连一边到 n1,返回(2),17,T2:/(op,B,C,A)若 B,C为已知量/合并已知量 执行 op B,得到一新常数 p,若NODE(p)=null 生成值标记为 p 的叶结点 n 否则 令 n=NODE(p

12、);把 A 添加在 n 结点的右侧;返回(2)否则 若 DAG 中存在型如右式的子图 则把 A 添加在 n 结点的右侧;返回(2)/合并多余运算 否则 若NODE(B)=null 生成值标记为 B 的叶结点 n1 否则 令 n1=NODE(B);若NODE(C)=null 生成值标记为 C 的叶结点 n2 否则 令 n2=NODE(C);建立一运算为 op,值标记为 A 的结点 n,从 n 分别连边到 n1,n2,返回(2),18,4 示例:设基本块如下:(1)A:=x+y(2)T0:=3.14(3)T1:=2*T0(4)T2:=R+r(5)A:=T1*T2(6)B:=A(7)T3:=2*T0

13、(8)T4:=R+r(9)T5:=T3*T4(10)T6:=R-r(11)B:=T5*T6,19,DAG 如下,3,1,2,x,y,+,A,4,3.14,T0,5,6.28,T1,T3,6,R,7,r,8,T2,T4,10,T6,9,A,B,T5,11,B,+,-,*,*,20,生成DAG 后,实质上已经进行了局部优化,再把 DAG 还原得到如下四元式:(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:=R-r(9)B:=A*T6,21,第三节 循环优化,循环是由循环语句,if 及 go

14、to 语句构成.为了找出中间代码程序中的所有循环,就要对程序的流程进行分析,流程是以基本块为单位的,因为基本块内无循环.一 控制流程图与循环的定义1控制流程图的 定义:控制流程图是具有唯一首结点的有向图,简称为流图.可表示为三元式:G=(N,E,n0)N 为结点集,每 一结点为一基本块;E 为有向边,代表流向;n0为首结点,它包含了程序的第一条语句.,22,2 流图的构造方法(1)若基本块 j 在程序中的位置紧跟在基本块 i 之后,且 i 的出口语句非 goto(s),则:(2)若基本块 i 的出口语句为 goto(s),或 if.goto(s),而(s)是基本块 j 的入口语句,则:示例:,

15、i,j,i,j,23,设四元式程序如下:(1)read(X)(2)read(Y)(3)R:=X MOD Y(4)if R=0 goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)write(Y)(9)halt,(8)write(Y)(9)halt,(1)read(X)(2)read(Y),(3)R:=X MOD Y(4)if R=0 goto(8),(5)X:=Y(6)Y:=R(7)goto(3),B1,B2,B3,B4,流图,24,3 循环的定义 流图中,满足下面两条性质的结点序列称为一个循环:(1)结点序列为强连通的;(任意两点间都有通路,且通路上的结点都属于结点序列)(2

16、)结点序列中仅有一个入口结点.,示例:右面为一流图结点序列 6,4,5,6,7,2,3,4,5,6,7是满足以上定义的循环;但结点序列 2,4,2,3,4,4,5,7,4,6,7不是上述意义下的循环.,1,2,4,3,6,5,7,25,二 查找循环 为了建立循环的查找算法,首先介绍几个基本概念:必经结点集,回边,可归约流图1 必经结点集定义:若从流图首结点出发到达 nj 的通路都必须经过 ni,则称ni 为 nj 的必经结点,记为 ni DOM nj;流图中结点 n 的所有必经结点,称为 n 的必经结点集,记为 D(n).,26,1,2,4,3,6,5,7,例如:右图各结点的必经结点集为:D(

17、1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7,27,设 p1,p2.pk 是 n 的所有前趋结点,根据定义,若 所有 pi(1ik)均有 d DOM pi,则 d DOM n,即D(n)=n D(p1)D(p2).D(pk)求 D(n)的算法(1)令 D(n0)=n0;D(i)=N(i n0);(2)对每一个 ni(i n0),temp=ni D(p1)D(p2).D(pk);/p1,p2.pk 为 ni 的所有前趋结点 if D(ni)temp then D(ni):=temp(3)重复(2),直到所

18、有D(ni)不再改变.,d,p1,p2,pk,n,28,2 回边定义:设 ba是流图中一条有向边,且 aD(b),则ba称是流图中的一条回边.可以从必经结点集中求出回边:for b N do for a DOM(b)do if 为一条有向边 then 为回边3 可规约流图定义:一个流图称为可规约流图,但且仅当流图中除去回边而剩余部分构成无环路流图.,b,a,回边,DOM,29,4循环查找算法定理:若流图为可规约流图,已知有向边 ba 是一条回边,则由结点 b,a 以及有通路到达 b 而不经过 a 的所有结点序列构成流图的一个循环.查找回边ba构成的循环算法:(1)令 loop:=b,a;pus

19、h(S,b);(2)if not empty(S)then n:=pop(s);for(m in pn)do/pn 为 n 的前趋结点集 if(m not in loop)then loop:=loop+m;push(S,m),30,三 优化信息-ud 集 为了进行循环优化,还应分析变量的定值及引用关系,这种关系称为 引用-定值链,或称为 引用-定值集.定义:若变量 A 在四元式 d 定值,并存在一条通路到达四元式 u,且 该通路上没有 A 的其它定值,则称 A 在 d 的定值到达 u.定义:如在 u 处引用了变量 A,则凡能到达 u 的 A 的所有定值点,构成了 A 在 u 处的引用-定值集

20、,记为:udA.下面介绍如何求 ud集.1 到达-定值方程,31,首先定义四个基本集合:INB:代表到达基本块 B 入口点时的各变量的所有定值点集;OUTB:代表到达基本块 B 出口点时的各变量的所有定值点集;GENB:表示 B 中所定值的且到达 B 之后的定值点集;KILLB:表示属于 B 外的定值点,而这些定值点所定值的变量在 B中又被重新定值 这几个集合满足如下方程:OUTB=(INB-KILL(B)GENB INB=OUTp1 OUTp2.OUTpk p1,p2.pk 为B的前趋结点.该方程即为到达-定值方程,求解该方程,得到INB.,32,2求 ud A 算法如下:若 B 中,变量

21、A 的引用点 u 之前有 A 的定值点 d,且到达 u,则 ud A=d;否则 ud A=di|di INB 且 di为A的定值点.这样,可以求出每个变量在引用点 u 的定值状况.,33,四 循环的几种基本优化 下面介绍三种循环优化:代码外提,强度削弱,删除归纳变量.代码外提定义:对于循环中的语句 A:=B op C,若 B 及 C 均为常量,或者 为 循环中未改变的变量,那么每次循环 A的值都一样,称A:=B op C 为不变运算.对于不变运算,有可能把 A:=B op C 放到循环前,具体做法是:a)建立一前置结点;b)循环入口结点(唯一的)为前置结点的唯一后继;c)循环外流向入口结点的有

22、向边,改为流向前置结点;d)把循环中可以外提的不变运算放在前置结点中.见下图:,34,循环入口结点,循环外流向前置结点,前置结点,循环入口结点,下面讨论两个问题:(1)哪些是循环中的不变运算?(2)循环中的哪些不变运算可以放到前置结点中?,循环外流向入口结点,循环内结点,循环内结点,改为,35,1 不变运算的确定算法(1)察看循环中的每条四元式,若每个运算对象或为常量,或定值点在循环外的变量,则标记为不变运算;(2)察看尚未标记为不变运算的四元式,若每个运算对象或为常量,或定值点在循环外的变量,或在循环内具有唯一定值点的变量且该定值点已经标记为不变运算,则标记为不变运算;(3)重复(2),直到

23、不产生新的不变运算.,36,2 代码外提算法(1)对循环中每一不变运算(S)A:=B op C(包括 A:=op C 或 A:=B),检查是否满足如下条件之一:a)S所在的结点是循环所有出口结点的必经结点,且 S为变量A 在循环中唯一 定值点,且 A 的定值点 S 能到达循环中所有 A 的引用点;b)S为 变量 A 在循环中唯一 定值点,且 A 的定值点 S 能到达循环中所有 A 的引用点,且 A 在循环之后不再引用.(2)把循环中满足条件 a)或 b)的不变运算移至前置结点中,若运算对象 B 或 C 是在循环中定值,则只有当 B 或 C 的定值点四元式已放入前置结点中后,才可以把 S 外提.

24、,37,强度削弱 强度削弱是指循环中,把执行时间较长的运算转换为执行时间较短的运算.下面仅讨论乘法运算转换为加法运算.(注:并非每个乘运算都可以进行强度削弱)定义:若循环中对 B 只有唯一的递归赋值 B:=B+C 且 C 为循环不变量,则称 B 为循环的基本归纳变量.定义:若 B 为基本归纳变量,而 A 在循环中的定值,可以化归为 B 的线性函数:A:=C1*B+C2(C1,C2为循环不变量)则称 A 为归纳变量,并称 A与 B同族.,38,一般而言,若循环中有递归赋值 B:=B+C(B 每次循环递增常量C)而 循环中对 A 的赋值为 B 的线性函数 A:=C1*B+C2(C1,C2为常数)那

25、么,循环中A:=C1*B+C2的乘运算可转换为加运算,具体做法如下:在前置结点中添加:A:=C1*B+C2 令 C=C1*C原A:=C1*B+C2 改为:A:=A在 B:=B+C 之后增加:A:=A+C,39,示例:根据定义 I 为基本归纳变量;T2,T6 为与 I 同族的归纳变量;T3,T7 可转化为:T3:=10*I+T1(T1为循环不变量)T7:=10*I+T5(T5为循环不变量)也为 与 I 同族的归纳变量;下面是对 T2 进行强度削弱的示例:,(1)I:=1(2)T1:=2*J(3)T4:=addr(A)-11(4)T5:=2*J(5)T8:=addr(A)-11,(7)T2:=10

26、*I(8)T3:=T2+T1(9)T6:=10*I(10)T7:=T6+T5(11)T9:=T8T7(12)T4T3:=T9+1(13)I:=I+1(14)goto(6),(6)if I10 goto(15),40,基本归纳变量:I:=I+1(C=1)T2 与 I 同族:T2:=10*I+0(C1=10,C2=0)在前置结点中添加:T2:=10*I令 C=10原A:=C1*B+C2 改为:T2:=T2在 I:=I+1 之后增加:T2:=T2+10同理,T6,T3,T7 也一样处理.,41,删除基本归纳变量 具体做法如下:若基本归纳变量 B 在循环出口之后不再引用,且在循环中除B:=B+C 处被引用外,只在型如 if B rop Y goto(s)中被引用,则(1)选一与B 同族的归纳变量 M,M与 B 有如下线性关系:M=C1*B+C2(2)建立一临时变量 R,在前置结点中增加 R:=C1*Y+C2(3)用if M rop R goto(s)替换 if B rop Y goto(s)(4)删除循环中四元式 B:=B+C,42,本章习题,P168,4.,9.,43,