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

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

1、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)

2、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(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代码外提代码外提 (4)与与(7)每次循环其值都每次循环其值都不变不变,称为循环不变量称为循环不变量.可以放可以放到循环前到循环前,减少循环

3、中的运算减少循环中的运算.参见下页四元式表参见下页四元式表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)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)if I强度削弱强度削弱 由于每次循环由于每次循环 I 都增加都增加 1,因此因此,T1递增递增 4,可把可把(3)改为改为T1:=T1+4,放在放在(11)之后之后,并在并在循环前对循环前对 I 赋初值赋初值 T1:=4*I.(12)改为改为 goto(5).参见下页四元

4、式表参见下页四元式表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(12)if I变换控制条件变换控制条件 由于由于 I 只用作循环控制只用作循环控制,而而 T1=4*I ,因此因此,可用可用 T1 替替换换 I,I=20 等价于等价于 T1=80,把把(12)改为改为 if T1=80 goto(5)这样这样,可以删掉无用的可以删掉无用的 I.参见下页四元式表

5、参见下页四元式表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合并已知量合并已知量 由于由于(3)中的中的 I 在在(2)赋值后赋值后仍然为仍然为 1,因此可改为因此可改为:T1:=46 复写复写 (6)中中 T1 复制到复制到 T4,而而(6)到到(8)之间没有改变之间没有改变T1 和和 T4,因此因此(8)可以改为可以改为:T6:=T5T1,从而从而使使(6)

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删除无用赋值删除无用赋值 (2)和和(6)两四元式为无用两四元式为无用四元式四元式,可以删除可以删除.最终优化后最终优化后,得到得到下页四元式表下页四元式表8(1)PROD:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2T

7、1(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 定义定义:基本块是一顺序执行的中间代码序列基本块是一顺序执行的中间代码序列,仅包含一个入口仅包含一个入口 四元式四元式 和一个出口四元式和一个出口四元式,第一条四元式为入口四元式

8、第一条四元式为入口四元式,最后最后 一条四元式为出口四元式一条四元式为出口四元式.中间部分不含转移四元式中间部分不含转移四元式.2 基本块的划分基本块的划分 给定一四元式程序给定一四元式程序,可以通过如下算法可以通过如下算法,划分基本块划分基本块:10基本块划分算法基本块划分算法:1)求四元式程序中所有基本入口四元式求四元式程序中所有基本入口四元式,包括包括:a)程序的第一条四元式程序的第一条四元式;b)转移语句转移到的四元式转移语句转移到的四元式;c)条件语句之后的第一条四元式条件语句之后的第一条四元式.2)对每一入口四元式对每一入口四元式,构造一个基本块构造一个基本块:从该入口四元式到下一

9、入口四元式之前的一条四元式从该入口四元式到下一入口四元式之前的一条四元式,或到一转移语句或到一转移语句,或到一停止语句之间的四元式序列或到一停止语句之间的四元式序列 组成组成.3)凡未纳入这些基本块的四元式凡未纳入这些基本块的四元式,为无用四元式为无用四元式,可以删除可以删除.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)转移语

10、句转移到的四元式转移语句转移到的四元式 (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)goto(3)B1B2B3B413二二 基本块内的优化基本块内的优化 基本块内可以进行以下几种优化基本块内可以进行以下几种优化:合并已知量合并已知量,删除多余运算删除多余运算(公共子表达式公共子表达式)删除无用赋值

11、删除无用赋值 优化手段优化手段:DAG 1 DAG 的定义的定义 DAG 是有向无环路图的简称是有向无环路图的简称,结点的基本形式如右图结点的基本形式如右图:n i 为结点名为结点名,val 为结点值标记为结点值标记,op 为结点的运算为结点的运算.n ini1ni2opval142 四元式的四元式的 DAG 表示表示 考虑下面三种类型的四元式考虑下面三种类型的四元式,DAG表示如右所示表示如右所示0 型型:(:=,B,A)1 型型:(op,B,A)2 型型:(op,B,C,A)n iB,An in k A Bop An ini1ni2 B Cop153 基本块的基本块的 DAG 构造算法及优

12、化构造算法及优化令令 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 的叶结点的叶结点

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

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

15、如右式的子图中存在型如右式的子图 则把则把 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)n n 1n 2 B Cop184 示例示例:设基本块如下设基本块如下:(1)A:=x

16、+y(2)T0:=3.14(3)T1:=2*T0(4)T2:=R+r(5)A:=T1*T2(6)B:=A(7)T3:=2*T0(8)T4:=R+r(9)T5:=T3*T4(10)T6:=R-r(11)B:=T5*T619DAG 如下如下3 1 2 x y+A 4 3.14,T0 5 6.28,T1,T3 6 R7 r8 T2,T410T69 A,B,T511 B+-*20生成生成DAG 后后,实质上已经进行了局部优化实质上已经进行了局部优化,再把再把 DAG 还原得到还原得到如下四元式如下四元式:(1)T0:=3.14(2)T1:=6.28(3)T3:=6.28(4)T2:=R+r(5)T4:

17、=T2(6)A:=6.28*T2(7)T5:=A(8)T6:=R-r(9)B:=A*T621第三节第三节 循环优化循环优化 循环是由循环语句循环是由循环语句,if 及及 goto 语句构成语句构成.为了找出中间代码程为了找出中间代码程序中的所有循环序中的所有循环,就要对程序的流程进行分析就要对程序的流程进行分析,流程是以基本块为流程是以基本块为单位的单位的,因为基本块内无循环因为基本块内无循环.一一 控制流程图与循环的定义控制流程图与循环的定义1控制流程图的控制流程图的 定义定义:控制流程图是具有唯一首结点的有向图控制流程图是具有唯一首结点的有向图,简称为流图简称为流图.可表可表示为三元式示为

18、三元式:G=(N,E,n0)N 为结点集为结点集,每每 一结点为一基本块一结点为一基本块;E 为有向边为有向边,代表流向代表流向;n0为首结点为首结点,它包含了程序的第一条语句它包含了程序的第一条语句.222 流图的构造方法流图的构造方法 (1)若基本块若基本块 j 在程序中的位置紧跟在基本块在程序中的位置紧跟在基本块 i 之后之后,且且 i 的的出口语句非出口语句非 goto(s),则则:(2)若基本块若基本块 i 的出口语句为的出口语句为 goto(s),或或 if.goto(s),而而(s)是基本块是基本块 j 的入口语句的入口语句,则则:示例示例:i j i j 23设四元式程序如下设

19、四元式程序如下:(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)B1B2B3B4流图流图243 循环的定义循环的定义 流图中流图中,满足下面两条性质的结点序列称为一个循环满足下面两条性质的结点序列称为一个循环:(1)结点序列为强连通的结点序列为强连通的;(任意两点间都有通路任意两

20、点间都有通路,且通路上且通路上的结点都属于结点序列的结点都属于结点序列)(2)结点序列中仅有一个入口结点结点序列中仅有一个入口结点.示例示例:右面为一流图右面为一流图结点序列结点序列 6,4,5,6,7,2,3,4,5,6,7是满足以上定义的循环是满足以上定义的循环;但结点序列但结点序列 2,4,2,3,4,4,5,7,4,6,7不是上述意义下的循环不是上述意义下的循环.12 4 3 6 5 7 25二二 查找循环查找循环 为了建立循环的查找算法为了建立循环的查找算法,首先介绍几个基本概念首先介绍几个基本概念:必经结点集必经结点集,回边回边,可归约流图可归约流图1 必经结点集必经结点集定义定义

21、:若从流图首结点出发到达若从流图首结点出发到达 nj 的通路都必须经过的通路都必须经过 ni ,则称则称ni 为为 nj 的必经结点的必经结点,记为记为 ni DOM nj ;流图中结点流图中结点 n 的所有必的所有必经结点经结点,称为称为 n 的必经结点集的必经结点集,记为记为 D(n).2612 4 3 6 5 7 例如例如:右图各结点的必经结点集为右图各结点的必经结点集为:D(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,727 设设 p1,p2.pk 是是 n 的所有前趋结点的所有前趋结点,根据定义

22、根据定义,若若 所有所有 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),直到所有直到所有D(ni)不再改变不再改变.d p1 p2 pk n282 回边回边定义定义:设设 ba是流图中一条有向边是流图中一条有向

23、边,且且 aD(b),则则ba称是流图称是流图中的一条回边中的一条回边.可以从必经结点集中求出回边可以从必经结点集中求出回边:for b N do for a DOM(b)do if 为一条有向边为一条有向边 then 为回边为回边3 可规约流图可规约流图定义定义:一个流图称为可规约流图一个流图称为可规约流图,但且仅当流图中除去回边而剩余但且仅当流图中除去回边而剩余部分构成无环路流图部分构成无环路流图.ba回边回边DOM294循环查找算法循环查找算法定理定理:若流图为可规约流图若流图为可规约流图,已知有向边已知有向边 ba 是一条回边是一条回边,则由结则由结点点 b,a 以及有通路到达以及有通

24、路到达 b 而不经过而不经过 a 的所有结点序列构成流图的的所有结点序列构成流图的一个循环一个循环.查找回边查找回边ba构成的循环算法构成的循环算法:(1)令令 loop:=b,a;push(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 集集 为了进行循环优化为了进行循环优化,还应分析变量的定值及引用关系还应分析变量的定值及引用关系,这种关系这种关系称为称为 引用引用-

25、定值链定值链,或称为或称为 引用引用-定值集定值集.定义定义:若变量若变量 A 在四元式在四元式 d 定值定值,并存在一条通路到达四元式并存在一条通路到达四元式 u,且且 该通路上没有该通路上没有 A 的其它定值的其它定值,则称则称 A 在在 d 的定值到达的定值到达 u.定义定义:如在如在 u 处引用了变量处引用了变量 A,则凡能到达则凡能到达 u 的的 A 的所有定值点的所有定值点,构成构成了了 A 在在 u 处的处的引用引用-定值集定值集,记为记为:udA.下面介绍如何求下面介绍如何求 ud集集.1 到达到达-定值方程定值方程 31首先定义四个基本集合首先定义四个基本集合:INB:代表到

26、达基本块代表到达基本块 B 入口点时的各变量的所有定值点集入口点时的各变量的所有定值点集;OUTB:代表到达基本块代表到达基本块 B 出口点时的各变量的所有定值点集出口点时的各变量的所有定值点集;GENB:表示表示 B 中所定值的且到达中所定值的且到达 B 之后的定值点集之后的定值点集;KILLB:表示属于表示属于 B 外的定值点外的定值点,而这些定值点所定值的变量在而这些定值点所定值的变量在 B中又被重新定值中又被重新定值 这几个集合满足如下方程这几个集合满足如下方程:OUTB=(INB -KILL(B)GENB INB=OUTp1 OUTp2.OUTpk p1,p2.pk 为为B的前趋结点

27、的前趋结点.该方程即为该方程即为到达到达-定值方程定值方程,求解该方程求解该方程,得到得到INB.322求求 ud A 算法如下算法如下:若若 B 中中,变量变量 A 的引用点的引用点 u 之前有之前有 A 的定值点的定值点 d,且到达且到达 u,则则 ud A=d;否则否则 ud A=di|di INB 且且 di为为A的定值点的定值点.这样这样,可以求出每个变量在引用点可以求出每个变量在引用点 u 的定值状况的定值状况.33四四 循环的几种基本优化循环的几种基本优化 下面介绍三种循环优化下面介绍三种循环优化:代码外提代码外提,强度削弱强度削弱,删除归纳变量删除归纳变量.代码外提代码外提定义

28、定义:对于循环中的语句对于循环中的语句 A:=B op C,若若 B 及及 C 均为常量均为常量,或者或者 为为 循环中未改变的变量循环中未改变的变量,那么每次循环那么每次循环 A的值都一样的值都一样,称称A:=B op C 为不变运算为不变运算.对于不变运算对于不变运算,有可能把有可能把 A:=B op C 放到循环前放到循环前,具体做法是具体做法是:a)建立一前置结点建立一前置结点;b)循环入口结点循环入口结点(唯一的唯一的)为前置结点的唯一后继为前置结点的唯一后继;c)循环外流向入口结点的有向边循环外流向入口结点的有向边,改为流向前置结点改为流向前置结点;d)把循环中把循环中可以外提可以

29、外提的不变运算放在前置结点中的不变运算放在前置结点中.见下图见下图:34循环入口结点循环入口结点循环外流向前置结点循环外流向前置结点前置结点前置结点循环入口结点循环入口结点 下面讨论两个问题下面讨论两个问题:(1)哪些是循环中的不变运算哪些是循环中的不变运算?(2)循环中的哪些不变运算可以放到前置结点中循环中的哪些不变运算可以放到前置结点中?循环外流向入口结点循环外流向入口结点循环内结点循环内结点循环内结点循环内结点改为改为351 不变运算的确定算法不变运算的确定算法 (1)察看循环中的每条四元式察看循环中的每条四元式,若每个运算对象或为常量若每个运算对象或为常量,或定或定值点在循环外的变量值

30、点在循环外的变量,则标记为不变运算则标记为不变运算;(2)察看尚未标记为不变运算的四元式察看尚未标记为不变运算的四元式,若每个运算对象或为若每个运算对象或为常量常量,或定值点在循环外的变量或定值点在循环外的变量,或在循环内具有唯一定值点的变或在循环内具有唯一定值点的变量且该定值点已经标记为不变运算量且该定值点已经标记为不变运算,则标记为不变运算则标记为不变运算;(3)重复重复(2),直到不产生新的不变运算直到不产生新的不变运算.362 代码外提算法代码外提算法 (1)对循环中每一不变运算对循环中每一不变运算 (S)A:=B op C(包括包括 A:=op C 或或 A:=B),检查是否满足如下

31、条件之一检查是否满足如下条件之一:a)S所在的结点是循环所有出口结点的必经结点所在的结点是循环所有出口结点的必经结点,且且 S为变量为变量A 在循环中唯一在循环中唯一 定值点定值点,且且 A 的定值点的定值点 S 能到达循环中所有能到达循环中所有 A 的引用点的引用点;b)S为为 变量变量 A 在循环中唯一在循环中唯一 定值点定值点,且且 A 的定值点的定值点 S 能到达循环中所有能到达循环中所有 A 的引用点的引用点,且且 A 在循环之后不再引用在循环之后不再引用.(2)把循环中满足条件把循环中满足条件 a)或或 b)的不变运算移至前置结点中的不变运算移至前置结点中,若运算对象若运算对象 B

32、 或或 C 是在循环中定值是在循环中定值,则只有当则只有当 B 或或 C 的的定值点四元式已放入前置结点中后定值点四元式已放入前置结点中后,才可以把才可以把 S 外提外提.37强度削弱强度削弱 强度削弱是指循环中强度削弱是指循环中,把执行时间较长的运算转换为执行时把执行时间较长的运算转换为执行时间较短的运算间较短的运算.下面仅讨论乘法运算转换为加法运算下面仅讨论乘法运算转换为加法运算.(注注:并非每个乘运算都可以进行强度削弱并非每个乘运算都可以进行强度削弱)定义定义:若循环中对若循环中对 B 只有唯一的递归赋值只有唯一的递归赋值 B:=B+C 且且 C 为循环不为循环不变量变量,则称则称 B

33、为循环的基本归纳变量为循环的基本归纳变量.定义定义:若若 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为常数为常数)那么那么,循环中循环中A:=C1*B+C2的乘运算可转换为加

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

35、I:=1(2)T1:=2*J(3)T4:=addr(A)-11(4)T5:=2*J(5)T8:=addr(A)-11(7)T2:=10*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

36、之后增加之后增加: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