編譯原理分知識點習題 代碼優(yōu)化

1．與機器有關(guān)的代碼優(yōu)化有那些種類，請分別舉例說明。解答：與機器有關(guān)的優(yōu)化有：寄存器優(yōu)化，多處理優(yōu)化，特殊的指令優(yōu)化，無用的指令消除等四類。冗余指令刪除假設(shè)源程序指令序列a:=b+c;c:=a-d;編譯程序為其生成的代碼很可能是下列指令序列：MOVb,R0ADDc,R0MOVR0,aSUBd,R0MOVR0,c假如第四條指令沒有標號，上述兩個賦值語句在一個基本塊內(nèi)，則第四條指令是多余的，可刪除。特殊指令的使用例如，如果目標機器指令系統(tǒng)包含增1指令I(lǐng)NC，對于i:=i+1的目標代碼MOVi,R0ADD#1,R0MOVR0,i便可被代之以1條指令I(lǐng)nci說明：優(yōu)化的特點是每個改進可能會引發(fā)新的改進機會，為了得到最好的改進，一般可能需要對目標代碼重復(fù)掃描進行優(yōu)化。2．設(shè)有語句序列a:=20b:=a*(a+10);c:=a*b;試寫出合并常量后的三元式序列。解答：該語句序列對應(yīng)的三元式序列為：（1）（:=,20,a）（2）(+,a,10)（3）(*,a,(2))（4）(:=,a,b)（5）(*a,b)（6）(:=,(5),c)合并常量后的三元式序列為：（:=,20，a）(:=,600,b)(:=,12000,c)3、試寫出算術(shù)表達式a+b*c-(c*b+a-e)/(b*c+d)優(yōu)化后的四元式序列。解答：該表達式的四元式序列為：（*，b,c,T1）(+,a,T1,T2)(*,c,b,T3)(+,T3,a,T4)(-,T4,e,T5)(*,b,c,T6)(+,T6,d,T7)(/,T5,T7,T8)(-,T2,T8,T9)可對該表達式進行刪除公共子表達式的優(yōu)化。優(yōu)化后的四元式序列為：（*，b,c,T1）(+,a,T1,T2)(-,T2,e,T5)(+,T1,d,T7)(/,T5,T7,T8)(-,T2,T8,T9)4.設(shè)有算術(shù)表示式（a*b+c）/(a*b-c)+(c*b+a-d)/(a*b+c)試給出其優(yōu)化后的三元式序列。解答：該算術(shù)表達式的三元序列為：（*,a,b）(+,(1),c)(*,a,b)(-,(3),c)(/,(2),(4))(*,c,b)(+,(6),a)(-,(7),d)（*,a,b）(+,(9),c)(/,(8),(10))(+,(5),(11))可對其進行刪除公共子表達式的優(yōu)化。優(yōu)化后的三元式列為：（1）（*，a,b）(2)(+,(1),c)(3)(-,(1),c)(4)(/,(2),(3))(5)(*,c,b)(6)(+,(5),a)(7)(-,(6),d)(8)(/,(7),(2))(9)(+,(4),(8))5.試對以下基本塊B1和B2應(yīng)用DAG進行優(yōu)化B1:A:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:=FM:=LB2:B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L并就以下兩種情況分別寫出優(yōu)化后的四元式序列：假設(shè)G、L、M在基本塊后面要被引用;假設(shè)只有L在基本塊后面要被引用。解答:一般應(yīng)用DAG在一個基本塊內(nèi)可以進行三種優(yōu)化:合并常量、刪除無用賦值以及多余運算。對于基本塊B1,其DAG如圖7.1所示。99857F16342F,L,M*E*+H*A,GD*/BC2圖7.1基本塊B1的DAG圖優(yōu)化后的四元式序列如下:(1)若只有G、L、M在基本塊后面要被引用G:=B*C或G:=B*CH:=G*GS:=G*GL:=H*GL:=S*GM:=LM:=L(S為臨時變量)(2)若只有L在基本塊后面要被引用G:=B*C或S1:=B*CH:=G*GS2:=S1*S1L:=H*GL:=S2*S1(S1、S2為臨時變量)對于基本塊B2,其DAG如圖7.2所示。38381726954 *F,J++D,HE,L+*BK3AC15圖7.2基本塊B2的DAG圖優(yōu)化后的四元式序列如下:(1)若只有G、L、M在基本塊后面要被引用D:=A+CE:=A*CF:=D+EG:=3*FL:=F+15M:=L(2)若只有L在基本塊后面要被引用D:=A+C或S1:=A+CE:=A*CS2:=A*CF:=D+ES3:=S1+S2L:=F+15L:=S3+15(S1、S2、S3為臨時變量)6.對于基本塊PS0:=2S1:=3/S0S2:=T-CS3:=T+CR:=S0/S3H:=RS4:=3/S1S5:=T+CS6:=S4/S5H:=S6*S2試應(yīng)用DAG進行優(yōu)化。假定只有R、H在基本塊出口是活躍的,試寫出優(yōu)化后的四元式序列。假定只有兩個寄存器R0、R1試寫出上述優(yōu)化后的四元式序列的目標代碼。解答:(1)構(gòu)造DAG如圖7.3所示。1H1H0473652R,,S6S2/-S3,S5+S0,S4S121.5TC圖7.3基本塊P的DAG圖優(yōu)化后的四元式序列為:S0:=2S4:=2S1:=1.5S2:=T-CS3:=T+CS5:=S3R:=2/S3S6:=RH:=S6*S2(2)若只有R、H在基本塊出口是活躍的,優(yōu)化后的四元式序列為:S2:=T-CS3:=T+CR:=2/S3H:=R*S2(3)假定只有兩個寄存器R0、R1,上述優(yōu)化后的四元式序列的目標代碼為:LDR0TSUBR0CSTR0S2LDR0TADDR0CLDR12DIVR1R0LDR0S2MULR1R0STR1H7.設(shè)有入圖7.4所示的程序流程圖:B8B8B2B3B4B7B6B5B1圖7.4程序流圖求出流圖中各個結(jié)點n的必經(jīng)結(jié)點集D(n);求出該流圖中的回邊;求出該流圖中的循環(huán)。解答:(1)在程序流圖中,對任意的結(jié)點ni和nj,如果從流圖的首結(jié)點出發(fā),到達nj的任一通路都必須經(jīng)過ni,則稱ni是nj的必經(jīng)結(jié)點,記為niDOMnj。流圖中結(jié)點n的所有必經(jīng)結(jié)點稱為結(jié)點n的必經(jīng)結(jié)點集,記為D(n)。流圖中各結(jié)點n的必經(jīng)結(jié)點集D(n)為:D(B1)={B1}D(B2)={B1,B2}D(B3)={B1,B2,B3}D(B4)={B1,B2,B3,B4}D(B5)={B1,B2,B3,B5}D(B6)={B1,B2,B3,B6}D(B7)={B1,B2,B7}D(B8)={B1,B2,B7,B8}(2)流圖的回邊是指:若a→b是流圖中一條有向邊,且有bDOMa,則稱a→b是流圖的一條回邊。題目所給流圖中,有有向邊B7→B2,又有D(B7)={B1,B2,B7},所以,B2DOMB7,即B7→B2是流圖的回邊。且無其他回邊。(3)該流圖中的循環(huán)可利用回邊求得。如果以知有向邊n→d是一回邊,由它組成的循環(huán)就是由結(jié)點d、結(jié)點n以及有通路到達n而該通路不經(jīng)過d的所有結(jié)點組成,且d是該循環(huán)的唯一入口結(jié)點。題目所給出流圖中,只有一條回邊B7→B2,在該流圖中,凡是不能經(jīng)過結(jié)點B2有通路到達結(jié)點B7的結(jié)點,只有B3,B4,B5,B6,所以,由回邊B7→B2組成的循環(huán)是{B2,B3,B4,B5,B6,B7}。8.(中國科學院計算機所1997年)試畫出如下中間代碼序列的程序流圖,并求出:各結(jié)點的必經(jīng)結(jié)點集合D(n);流圖中的回邊與循環(huán)。J:=0;L1:I:=0;ifI<8gotoL3;L2:A:=B+C;B:=D*C;L3:ifB=0gotoL4;WriteB;gotoL5;L4:I:=I+1;ifI<8gotoL2;L5:J:=J+1;ifJ<=3gotoL1;HALT解答:程序的流圖入圖7.5所示。(1)各結(jié)點的必經(jīng)結(jié)點集分別為:D(n0)={n0}D(n1)={n0,n1}D(n2)={n0,n1,n2}D(n3)={n0,n1,n3}D(n4)={n0,n1,n3,n4}D(n5)={n0,n1,n3,n5}D(n6)={n0,n1,n3,n6}D(n7)={n0,n1,n3,n6,n7}J:=0;L1:I:=0;ifI<8gotoL3;J:=0;L1:I:=0;ifI<8gotoL3;L2:A:=B+C;B:=D*C;L3:ifB=0gotoL4;WriteB;gotoL5;L4:I:=I+1;ifI<8gotoL2;L5:J:=J+1;ifJ<=3gotoL1;HALTn1n2n3n4n5n6n7圖7.5程序流圖（2）流圖中的回邊有一條：即n6 n1該回邊表示的循環(huán)為：（n1,n2,n3,n4,n5,n6）,入口為n1,出口為n69.(武漢大學1991年)試對下面的程序段進行盡可能的優(yōu)化： i：=１ j：=１０readkl：x：=k*iy:=j*iz:=x*ywriteji:=i+1ifi<100gotolhalt并指明你進行了何種優(yōu)化，給出優(yōu)化過程的簡要說明及每種優(yōu)化后的結(jié)果形式。解答：程序的流程圖如下所示：i：=１ j：=１０i：=１ j：=１０readkＢ1：l：x：=k*iy:=j*il：x：=k*iy:=j*iz:=x*ywriteji:=i+1ifi<100gotolhaltＢ2:halthaltＢ3:圖7.6程序流圖由程序流圖可知，｛Ｂ２｝為一個循環(huán)。對于本題中的循環(huán)可進行以下優(yōu)化：·削減強度循環(huán)中有x:=x*iy:=y*ij,k在循環(huán)中不改變值。i每次增加１,x和y的賦值運算可進行強度削減，于是程序流圖變?yōu)閳D7.7所示。i：=１i：=１ j：=１０readkB1:x：x：=0y：=0B2ˊ:l1l1：x：=x+ky：=y+10z：=x*ywriteji：=i+1ifijh<100gotol1Ｂ２：haltB3:halt圖7.7削減強度后的程序流圖·刪除歸納變量由于i是循環(huán)中的基本歸納變量，x、y是與y同族的歸納變量，且有線性關(guān)系x：=k*iy：=j*i所以，i<100完全可用x<100*k或y<100*j代替。于是，進一步優(yōu)化為圖7.8所示?！ごa外提將循環(huán)中不變運算writejtl:=100*k提到循環(huán)外的前置節(jié)點B21中，于是程序流圖變?yōu)?.9所示的情形。i：=１ j：=１０readkx：=0y：=0li：=１ j：=１０readkx：=0y：=0l1：x：=x+ky：=y+10z：=x*ywritejtl:=100*kifijh<tlgotol1halt B1: B12 B2: B3: 圖7.8歸納變量后的程序流圖i：=１ j：=１０i：=１ j：=１０readk B1: x：x：=0y：=0writejtl:=100*k B21:l1：x：l1：x：=x+ky：=y+10z：=x*yifijh<tlgotol1 B2:halt B3:halt 圖7.9代碼外提后的程序流圖10.在循環(huán)優(yōu)化中，為什么要代碼外提？試說明在哪些情況下代碼可外提？解答：代碼外提可以減少循環(huán)中的指令數(shù)目，從而節(jié)省目標代碼運行的時間。對于循環(huán)中L的每一個不變運算s：A：=BopC或A：=B檢查它是否滿足以下兩個條件：（a）s所在的節(jié)點是L的所有的出口節(jié)點的必經(jīng)節(jié)點；（b）Ａ在Ｌ中其他地方未再定值；（c）Ｌ中所有Ａ的引用點只有s中Ａ的定植才能到達。Ａ離開Ｌ后不再是活躍的，并且條件（１）中的（a）和（b）成立，所謂Ａ離開Ｌ后不再是活躍的，是指Ａ在Ｌ的任何出口節(jié)點的后繼節(jié)點（當然是指那些不屬于Ｌ的后繼）入口處不是活躍的。符合上述（１）或（２）的不變運算s可以外提到Ｌ的前置節(jié)點中。但是。S的運算對象（Ｂ或Ｃ）是在Ｌ中定植的，那么只有當這些定植代碼都已外提到前置節(jié)點中時。才能把s也提到前置節(jié)點中。11.以下循環(huán)是最內(nèi)循環(huán)，是對其進行循環(huán)優(yōu)化。A:=0I:=1L1:B:=J+1C:=B+IA:=C+AIFI=100GOTOL2I:=I+1GOTOL1L2:解答：程序的流程圖如圖所表示有流程圖可見，{B2,B3}是一個循環(huán)，該循環(huán)可進行以下有話：代碼外提B2中的B:=J+1是循環(huán)的不變運算，可提到循環(huán)外。刪除歸納變量I是循環(huán)的基本歸納變量，C是與I同組的歸納變量，且二者有如下線性關(guān)系：C::=B+I于是I=100完全可用C=B+100代替。相應(yīng)的I:=I+1可用C:=C+1代替。于是流程圖變?yōu)閳D所表示 圖7.10優(yōu)化后的程序流圖14．設(shè)有循環(huán)語句FOR