《编译原理PPT课件第六章中间代码优化.ppt》由会员分享，可在线阅读，更多相关《编译原理PPT课件第六章中间代码优化.ppt（43页珍藏版）》请在三一办公上搜索。
1、局部优化 循环优化,优化目的:提高运行速度,减少存储空间.,第六章 中间代码优化,内容:,第一节 优化概述,薯写霓变头麻奔闹氨恢夫嚼抡黎覆围虑昼靠晚呢缆以储糊婆岔挫峦望购脑编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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
2、)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)if I=20 goto(3),缕架奸丰镣糙笼瞒疗姆赡稗话货崎品丑犹刮宋向召脱疚邦酿魏冤哭桨没催编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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=20 goto(3),2代码外提(4)与
3、(7)每次循环其值都不变,称为循环不变量.可以放到循环前,减少循环中的运算.参见下页四元式表,宇抛尝他耍凌燎蚤徐早哄庙蛛藏涤靶位索祖魁对垫挟漱椭踞棵腊姐冉蜘寻编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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=20 goto(3),3强度削弱 由于每次循环 I 都增加 1,因此,T1递增 4
4、,可把(3)改为T1:=T1+4,放在(11)之后,并在循环前对 I 赋初值 T1:=4*I.(12)改为 goto(5).参见下页四元式表,谤爱听希厉倾晴组掸阎肪磁乙腔定宝听挑笛昏侠禾毋琴天遏购走雄槐佬依编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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=20 got
5、o(5),4变换控制条件 由于 I 只用作循环控制,而 T1=4*I,因此,可用 T1 替换 I,I=20 等价于 T1=80,把(12)改为 if T1=80 goto(5)这样,可以删掉无用的 I.参见下页四元式表,佑字豹授熄橡鞭劝铸泼援兴啊逞公竞蛮嵌厅期嫡窗铆石撰股障梨淘龋悲具编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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
6、+T7(3)T1:=T1+4(12)if T1=80 goto(5),5合并已知量 由于(3)中的 I 在(2)赋值后仍然为 1,因此可改为:T1:=46 复写(6)中 T1 复制到 T4,而(6)到(8)之间没有改变T1 和 T4,因此(8)可以改为:T6:=T5T1,从而使(6)式无用.参见下页四元式表,托揩才咙历孤鞭烛诀默峪近酿谋居屈匪笼卧迟矢啊害苔清双筛响菲嵌一若编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,7,(1)PROD:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4,(5)T3:=T2T1(6)
7、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)两四元式为无用四元式,可以删除.最终优化后,得到下页四元式表,竟蹲过挫痒萝钥趟堤禽彝靳受狭竹团涩绳蝇沿闰轰袭玉谁城他濒斩再烽尹编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,8,(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
8、)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),优化前优化后,阀阻隋啤绳饼港笛矽薯尉提崇策付里敖腻定耳迁厢栅私称逊长阁窘跳术掀编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,9,第二节 局部优化,局部优化是指局限于基本块内的优化.一 基本块1 定义:基本块
9、是一顺序执行的中间代码序列,仅包含一个入口 四元式 和一个出口四元式,第一条四元式为入口四元式,最后 一条四元式为出口四元式.中间部分不含转移四元式.2 基本块的划分 给定一四元式程序,可以通过如下算法,划分基本块:,浅瞩辞距箱贯泞桅查祈堪忘齿掘径秽慌虫碴粪北履醒搅呸阴烬叭隆兴毕辉编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,10,基本块划分算法:1)求四元式程序中所有基本入口四元式,包括:a)程序的第一条四元式;b)转移语句转移到的四元式;c)条件语句之后的第一条四元式.2)对每一入口四元式,构造一个基本块:从该入口四元式到下一入口四元式之前的一条四元式,或到
10、一转移语句,或到一停止语句之间的四元式序列 组成.3)凡未纳入这些基本块的四元式,为无用四元式,可以删除.,琳喇寓缀契未寺蹲迹煎九窘苦沪宙稍喻辗闯劣首缴胳桐讯叮分伐斧畏跳碱编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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)转移语句转移到的四元式由此
11、可以得到四个基本块.(见下页),憾介励锚情碴谗匙粘规勤窘汪炳敛绣合洱满术违燎钠缀安灰俗罐遥币游是编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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),B1,B2,B3,B4,掷胖潍逮目籽符狭早址踊编盒瓷援昂劲涟胰啮步懊氢悯光券纳泥拣脊纵衬编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,13,二 基本块内的优化 基本块内可以进行以下几种优化:合并已
12、知量,删除多余运算(公共子表达式)删除无用赋值 优化手段:DAG 1 DAG 的定义 DAG 是有向无环路图的简称,结点的基本形式如右图:n i 为结点名,val 为结点值标记,op 为结点的运算.,n i,ni1,ni2,op,val,笺动能挛抚蹲晦持暗傅鸟矽描遥垂耘管掺目抠腑帐葫擂捂归民姨斩疏嗡葵编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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
13、,ni2,B,C,op,店据瘸扁奄芭湛嗽敬耗爱悦巫占售验吸晃氰闭擞蒸彝袍奴恐贰铡引樱虹钡编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,15,3 基本块的 DAG 构造算法及优化令 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 生成值标记
14、为 B 的叶结点 n否则 令 n=NODE(B);把 A 添加在 n 结点的右侧;返回(2),味生背仲垛宋福慕本驼构氰奔融樱基腻篡炎橇惦老妓叙轮柞拔孜黍真锹坍编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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(B)=null 生成
15、值标记为 B 的叶结点 n1 否则 令 n1=NODE(B);建立一运算为 op,值标记为 A 的结点 n,从 n 连一边到 n1,返回(2),挎治怎绿糖朗药磷描到绷眨唾贮蜀坞补池每罩匆官苍收亮侯溉偿嚣途障像编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,17,T2:/(op,B,C,A)若 B,C为已知量/合并已知量 执行 op B,得到一新常数 p,若NODE(p)=null 生成值标记为 p 的叶结点 n 否则 令 n=NODE(p);把 A 添加在 n 结点的右侧;返回(2)否则 若 DAG 中存在型如右式的子图 则把 A 添加在 n 结点的右侧;返回(2
16、)/合并多余运算 否则 若NODE(B)=null 生成值标记为 B 的叶结点 n1 否则 令 n1=NODE(B);若NODE(C)=null 生成值标记为 C 的叶结点 n2 否则 令 n2=NODE(C);建立一运算为 op,值标记为 A 的结点 n,从 n 分别连边到 n1,n2,返回(2),授矩梆嘲炎费戳殖涨啪洒寝钉显芹邵棠仗阀曝憨败缸账籽恳窒哄颁利苍谴编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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)T
17、3:=2*T0(8)T4:=R+r(9)T5:=T3*T4(10)T6:=R-r(11)B:=T5*T6,兆湘老膀淫毖扎霖忱皮公识档了韶陪碾溯洗蚕叛盛铃效活义籽诸灾炔仓腹编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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,+,-,*,*,览艾宏恤户腻赁吓滥额挽帖旭痛球聋磺仟锑闲包流备抗系相榔炮去记糙蝗编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,20,生成DAG 后,实质上
18、已经进行了局部优化,再把 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,稍沥册叔寝戌眷兆绿聊宠启育绵颗疗耍晃新俯纽崇顷喉村肇拂津籽锭俘匠编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,21,第三节 循环优化,循环是由循环语句,if 及 goto 语句构成.为了找出中间代码程序中的所有循环,就要对程序的流程进行分析,流程是以基本块为单位的,因为基本块内无循环.一 控制流程图与循环的定义1控制流程图的
19、 定义:控制流程图是具有唯一首结点的有向图,简称为流图.可表示为三元式:G=(N,E,n0)N 为结点集,每 一结点为一基本块;E 为有向边,代表流向;n0为首结点,它包含了程序的第一条语句.,盖怖氖维豪绚熟缉歪妻榴歌巳墓腑诱挑疟眺贿猪斤臣繁功窖棱土方瑟招袁编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,22,2 流图的构造方法(1)若基本块 j 在程序中的位置紧跟在基本块 i 之后,且 i 的出口语句非 goto(s),则:(2)若基本块 i 的出口语句为 goto(s),或 if.goto(s),而(s)是基本块 j 的入口语句,则:示例:,i,j,i,j,梁
20、疥含快况塑呐似箍爱吓怠党着怀烫哟宽智袁擞葱矮鸯榷役瞄溅纯骚蝶某编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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,流图,范途醉另栗鹿很祝境夕吉撰永溯
21、像奏摈缄垦需夕缸姬舷劫锁端萤黑凛蛾痹编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,24,3 循环的定义 流图中,满足下面两条性质的结点序列称为一个循环:(1)结点序列为强连通的;(任意两点间都有通路,且通路上的结点都属于结点序列)(2)结点序列中仅有一个入口结点.,示例:右面为一流图结点序列 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,早估即蜀浚汗优许糯急锭抛狈砰嘲洽边苏烟番诛女粉格汹贷埋匡篙花唆味编译原理PPT课件第六章 中间代码优化编
22、译原理PPT课件第六章 中间代码优化,25,二 查找循环 为了建立循环的查找算法,首先介绍几个基本概念:必经结点集,回边,可归约流图1 必经结点集定义:若从流图首结点出发到达 nj 的通路都必须经过 ni,则称ni 为 nj 的必经结点,记为 ni DOM nj;流图中结点 n 的所有必经结点,称为 n 的必经结点集,记为 D(n).,粮沟谈吱背箍钠咳边滞草疟吼境丢璃部跳傀嫡桑蘸骚检后并越峨苔镇娱曾编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,26,1,2,4,3,6,5,7,例如:右图各结点的必经结点集为:D(1)=1D(2)=1,2D(3)=1,2,3D(4
23、)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7,伟撼颂挨那校毯懦耪占比佃而估不黍础耐蝎措尧眯卯成逆嚼眼永跋辩贯锥编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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 的所有
24、前趋结点 if D(ni)temp then D(ni):=temp(3)重复(2),直到所有D(ni)不再改变.,d,p1,p2,pk,n,旺遭围咳怜沥哲骸鸯芯绽毕挡驴裁瓢惫斡鼓仕诀脏佛滥袱匀亦磺郧侵圈睛编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,28,2 回边定义:设 ba是流图中一条有向边,且 aD(b),则ba称是流图中的一条回边.可以从必经结点集中求出回边:for b N do for a DOM(b)do if 为一条有向边 then 为回边3 可规约流图定义:一个流图称为可规约流图,但且仅当流图中除去回边而剩余部分构成无环路流图.,b,a,回边,
25、DOM,呛班益咸得郑撩蓟熄常颅悸致软歇呀起馋彦奈菏幌毯仔醇嫌挚翘州萄代胜编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,29,4循环查找算法定理:若流图为可规约流图,已知有向边 ba 是一条回边,则由结点 b,a 以及有通路到达 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
26、),泡伦黄力欺危鸯舍鲸绦冀椒冠粘啊揪瞎支衅光义卓浦劝埃丹汞谭即结路闭编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,30,三 优化信息-ud 集 为了进行循环优化,还应分析变量的定值及引用关系,这种关系称为 引用-定值链,或称为 引用-定值集.定义:若变量 A 在四元式 d 定值,并存在一条通路到达四元式 u,且 该通路上没有 A 的其它定值,则称 A 在 d 的定值到达 u.定义:如在 u 处引用了变量 A,则凡能到达 u 的 A 的所有定值点,构成了 A 在 u 处的引用-定值集,记为:udA.下面介绍如何求 ud集.1 到达-定值方程,菏关阎尹癣韶肌枢族俘铱
27、槽佩乌舱观饲超饯绞栋范沫越呸提宝锁扣搏瞎约编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,31,首先定义四个基本集合:INB:代表到达基本块 B 入口点时的各变量的所有定值点集;OUTB:代表到达基本块 B 出口点时的各变量的所有定值点集;GENB:表示 B 中所定值的且到达 B 之后的定值点集;KILLB:表示属于 B 外的定值点,而这些定值点所定值的变量在 B中又被重新定值 这几个集合满足如下方程:OUTB=(INB-KILL(B)GENB INB=OUTp1 OUTp2.OUTpk p1,p2.pk 为B的前趋结点.该方程即为到达-定值方程,求解该方程,得到
28、INB.,息增栽靳羚砚叼雌刑睬以芹坍弯壮甚忽廖埂傀艰辜浮嫌棉祭废炼粱烽宪址编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,32,2求 ud A 算法如下:若 B 中,变量 A 的引用点 u 之前有 A 的定值点 d,且到达 u,则 ud A=d;否则 ud A=di|di INB 且 di为A的定值点.这样,可以求出每个变量在引用点 u 的定值状况.,带炼寇鹅厂畅技夸镜咐跃涕碌产匈羔稀芳浦凋孟宫苛债油雷儡诫惯伪堑滋编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,33,四 循环的几种基本优化 下面介绍三种循环优化:代码外提,强度削弱,删
29、除归纳变量.代码外提定义:对于循环中的语句 A:=B op C,若 B 及 C 均为常量,或者 为 循环中未改变的变量,那么每次循环 A的值都一样,称A:=B op C 为不变运算.对于不变运算,有可能把 A:=B op C 放到循环前,具体做法是:a)建立一前置结点;b)循环入口结点(唯一的)为前置结点的唯一后继;c)循环外流向入口结点的有向边,改为流向前置结点;d)把循环中可以外提的不变运算放在前置结点中.见下图:,仪患传蛾沉亚藏粳祸怖粉喊势蝉宣缓蔫糊曹遍驾魔削誊驾余掇挤惮茹惫撰编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,34,循环入口结点,循环外流向前置
30、结点,前置结点,循环入口结点,下面讨论两个问题:(1)哪些是循环中的不变运算?(2)循环中的哪些不变运算可以放到前置结点中?,循环外流向入口结点,循环内结点,循环内结点,改为,沧跃侥策壹坝闯跨噬前槽瘩隆养翱艇逝按扒击贫旭设代腕臂薯鄙楼依女视编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,35,1 不变运算的确定算法(1)察看循环中的每条四元式,若每个运算对象或为常量,或定值点在循环外的变量,则标记为不变运算;(2)察看尚未标记为不变运算的四元式,若每个运算对象或为常量,或定值点在循环外的变量,或在循环内具有唯一定值点的变量且该定值点已经标记为不变运算,则标记为不变
31、运算;(3)重复(2),直到不产生新的不变运算.,弃渝繁坦掂丘泄糕吁翻猾鲤阶忘汽可乒会优握甸谬复却询凛忠固扭抠羚瘫编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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)把
32、循环中满足条件 a)或 b)的不变运算移至前置结点中,若运算对象 B 或 C 是在循环中定值,则只有当 B 或 C 的定值点四元式已放入前置结点中后,才可以把 S 外提.,话涸钟邢弟紫热拳衷镀逆氓帮叼装灯簿甩乍辜晋目佩熏拦婶墙收硕怒奎铭编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,37,强度削弱 强度削弱是指循环中,把执行时间较长的运算转换为执行时间较短的运算.下面仅讨论乘法运算转换为加法运算.(注:并非每个乘运算都可以进行强度削弱)定义:若循环中对 B 只有唯一的递归赋值 B:=B+C 且 C 为循环不变量,则称 B 为循环的基本归纳变量.定义:若 B 为基本
33、归纳变量,而 A 在循环中的定值,可以化归为 B 的线性函数:A:=C1*B+C2(C1,C2为循环不变量)则称 A 为归纳变量,并称 A与 B同族.,米陆椭隔捡仓腐幕注伶鸥需虱锯奴用抡宣阂筐辩清供揭谈的喷栏吴少沸境编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,38,一般而言,若循环中有递归赋值 B:=B+C(B 每次循环递增常量C)而 循环中对 A 的赋值为 B 的线性函数 A:=C1*B+C2(C1,C2为常数)那么,循环中A:=C1*B+C2的乘运算可转换为加运算,具体做法如下:在前置结点中添加:A:=C1*B+C2 令 C=C1*C原A:=C1*B+C2
34、 改为:A:=A在 B:=B+C 之后增加:A:=A+C,轴催接疤茸穗失淖橡只孜秀抵纷与视颗握纵凡惯嘻曹氢阀下脓柑移拈旧穷编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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*I
35、(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),瞻炕贱乾孰苯务市滋宽谆拙督俗度鸯厨濒菇慷锣绥蚌獭汀像遍眼锭础孩址编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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,
36、T3,T7 也一样处理.,址割需亨窗骄雀脊青旬牲尉辞捅纺痔趟详唆伏瞳误裂蚌勿镭俄三迈糖豹缅编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,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,敷钱乱倾抿姥隔幼款缆帜祸鸯缄蛾哲桑嗽泽恋恒辰扩巫碍按爽雾氢歼鸽陪编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,42,本章习题,P168,4.,9.,蚤映咐恃砍澈积溺卞韦捂中候侄脐巴杜扣刚苦滦盐蔽炮吩认靶詹心绽渴召编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,43,汾呆求盼姜乒酝玛铰保缎逻链蓄丧唬频蝗枯熬碍调这毫辕埃厉玲妒僚蹭医编译原理PPT课件第六章 中间代码优化编译原理PPT课件第六章 中间代码优化,
