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

1、1 .與機器有關(guān)的代碼優(yōu)化有那些種類，請分別舉例說明。解答：與機器有關(guān)的優(yōu)化有：寄存器優(yōu)化，多處理優(yōu)化，特殊的指令優(yōu)化，無用的指令消除等四類。冗余指令刪除假設(shè)源程序指令序列a:=b+c;c:=a-d;編譯程序為其生成的代碼很可能是下列指令序列：MOVb,RoADDc,RoMOVRo,aSUBd,RoMOVRo,c假如第四條指令沒有標(biāo)號，上述兩個賦值語句在一個基本塊內(nèi)，則第四條指令是多余的，可刪除。特殊指令的使用例如，如果目標(biāo)機器指令系統(tǒng)包含增1指令I(lǐng)NC,對于i:=i+1的目標(biāo)代碼MOVi,RoADD#1,RoMOVRo,i便可被代之以1條指令I(lǐng)nci說明：優(yōu)化的特點是每個改進可能會引發(fā)新的改

2、進機會，為了得到最好的改進，一般可能需要對目標(biāo)代碼重復(fù)掃描進行優(yōu)化。2 .設(shè)有語句序列a:=20b:=a*(a+10);c:=a*b;試寫出合并常量后的三元式序列。解答：該語句序列對應(yīng)的三元式序列為：(1) (k,20,a)(2) (+,a,10)(3) (*,a,(2)(4) (:=,a,b)(5) (*a,b)(6) (:=,(5),c)合并常量后的三元式序列為：(1)(k,20,a)(2) (:=,600,b)(3) (:=,12000,c)3、試寫出算術(shù)表達式a+b*c-(c*b+a-e)/(b*c+d)優(yōu)化后的四元式序列。解答：該表達式的四元式序列為：(1) (*,b,c,)(2)

3、(+,a,Ti,T2)(3) (*,c,b,T3)(4) (+,T3,a,T4)(5) (-,T4,e,T5)(6) (*,b,c,T6)(+,T6,d,T7)(8) (/,T5,T7,T8)(9) (-,T2,T8,T9)可對該表達式進行刪除公共子表達式的優(yōu)化。優(yōu)化后的四元式序列為:(1) (*,b,c,Ti)(2) (+,a,Ti,T2)(3) (-,T2,e,T5)(4) (+,Ti,d,T7)(5) (/,T5,T7,T8)(6) (-,T2,T8,T9)4.設(shè)有算術(shù)表示式(a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c)試給出其優(yōu)化后的三元式序列。解答：該算術(shù)表達式的

4、三元序列為：(1) (*,a,b)(2) (+,(1),c)(3) (*,a,b)(4) (-,(3),c)(5) (/,(2),(4)(6) (*,c,b)(7) (+,(6),a)(8) 37),d)(9) (*,a,b)(10) (+,(9),c)(11) (/,(8),(10)(12) (+,(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),(

5、8)5: 試對以下基本塊B1和B2應(yīng)用DAG進行優(yōu)化81: A:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:二FM:二L82: B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L并就以下兩種情況分別寫出優(yōu)化后的四元式序列：(1)假設(shè)GL、M在基本塊后面要被引用；(2)假設(shè)只有L在基本塊后面要被引用。解答：一般應(yīng)用DAGS一個基本塊內(nèi)可以進行三種優(yōu)化：合并常量、刪除無用賦值以及多余運算。所示。對于基本塊B,其DAG®圖7.1如下、1優(yōu)化后的四元式C圖7.12基本塊；B124

6、DAG圖6(1)若只有GL、M在基本塊后面要被引用G:=B*C或G:=B*CH:=G*GS:=G*GL:=H*GL:=S*GM:=LM:=L（S為臨時變量）（2）若只有L在基本塊后面要被引用G:=B*C或Si：=B*CH:=G*GS2：=Si*SiL:=H*GL:=S2*Si（S1、&為臨時變量）對于基本塊B2,其DAGta圖7.2所示。+*3AC 15圖7.2基本塊B2的DAGffl優(yōu)化后的四元式序列如下：(1)若只有GL、M在基本塊后面要被引用D:=A+CE:=A*CF:=D+EG:=3*FL:=F+15M:=L(S1、S2、S3為臨時變量)(2)若只有L在基本塊后面要被引用D:=

7、A+C或S1：=A+CE:=A*CS2：=A*CF:=D+ES3：=S1+S2L:=F+15L:=S3+156.對于基本塊PSo:=2Si：=3/SoS2：=T-CS3：=T+CR:=S0/S3H:二RS4：=3/S1S5：=T+CS6：=S4/S5H：=S6*S2(1)試應(yīng)用DAG!行優(yōu)化。假定只有R、H在基本塊出口是活躍的，試寫出優(yōu)化后的四元式序列。(3)假定只有兩個寄存器的、R試寫出上述優(yōu)化后的四元式序列的目標(biāo)代碼。解答：(1) 構(gòu)造DAGfc圖7.3所示H圖7.3基本塊P的DAGS優(yōu)化后的四元式序列為：S0：=2S4：=2Si：=1.5S2：=T-CS3：=T+CS5：=S3R:=2/

8、S3S6：=RH：=S6*S2(2)若只有R、H在基本塊出口是活躍的，優(yōu)化后的四元式序列為XS2：=T-CS3：=T+CR:=2/S3H:=RS2(3)假定只有兩個寄存器R0、Ri,上述優(yōu)化后的四元式序列的目標(biāo)代碼為LDRoTSUBRoCSTRoS2LDRoTADDRoCLDRi2DIVRiRoLDRoS2MULRiRoSTRiH7.設(shè)有入圖7.4所示的程序流程圖圖7.4程序流圖(1)求出流圖中各個結(jié)點n的必經(jīng)結(jié)點集D(n);(2)求出該流圖中的回邊；(3)求出該流圖中的循環(huán)。解答：(1)在程序流圖中，對任意的結(jié)點ni和nj,如果從流圖的首結(jié)點出發(fā)，到達nj的任一通路都必須經(jīng)過ni,則稱ni是

9、nj的必經(jīng)結(jié)點，記為niDOMp流圖中結(jié)點n的所有必經(jīng)結(jié)點稱為結(jié)點n的必經(jīng)結(jié)點集，記為D(n)。流圖中各結(jié)點n的必經(jīng)結(jié)點集D(n)為：D(Bi)=B1D(B2)=B1,B2D(B3)=B1,B2,B3D(B4)=B1舊2舊3舊4D(B5)=B1,B2,B3,B5D(B6)=B1,B2,B3,B6D(B7)=B1,B2,B7D(B8)=B1,B2,B7,B8(2)流圖的回邊是指：若a-b是流圖中一條有向邊，且有bDOMa,則稱a-b是流圖的一條回邊。題目所給流圖中，有有向邊6B2,又有D(B7)=B1,B2,B7,所以，B2DOM用即曲一B2是流圖的回邊。且無其他回邊。(3)該流圖中的循環(huán)可利用

10、回邊求得。如果以知有向邊n-d是一回邊，由它組成的循環(huán)就是由結(jié)點d、結(jié)點n以及有通路到達n而該通路不經(jīng)過d的所有結(jié)點組成，且d是該循環(huán)的唯一入口結(jié)點。題目所給出流圖中，只有一條回邊B7一電在該流圖中，凡是不能經(jīng)過結(jié)點B2有通路到達結(jié)點B7的結(jié)點，只有&舊4舊5舊6,所以，由回邊&一場組成的循環(huán)是B2,B3,B4,B5,B6,B7。8.(中國科學(xué)院計算機所1997年)試畫出如下中間代碼序列的程序流圖，并求出：(1) 各結(jié)點的必經(jīng)結(jié)點集合D(n);(2) 流圖中的回邊與循環(huán)。J:=0;L1:I:=0;ifI<8gotoL3;L2:A:=B+C;B:=D*C;L3:ifB=0g

11、otoL4;WriteB;gotoL5;L4:I:=I+1;ifI<8gotoL2;L5:J:=J+1;ifJ<=3gotoL1;HALT解答：程序的流圖入圖7.5所示(1)各結(jié)點的必經(jīng)結(jié)點集分別為D(n0)=n0D(n1)=no,n1D(n2)=no,ni,n2D(n3)=no,ni,n3D(n4)=no,ni,n3,n4D(n5)=no,ni,n3,n5D(n6)=no,ni,n3,n6D(n7)=no,ni,n3,n6,n7J:=0;no1'oLi:I:=0;ifI<8gotoL3;niL2:A:=B+C;n2B:=D*C;L3:ifB=0gotoL4;n3n4

12、WriteB;gotoL5;n5L4:I:=I+i;ifI<8gotoL2;L5:J:=J+i;ifJ<=3gotoLi;n6n7HALT圖7.5程序流圖(2)流圖中的回邊有一條：即n6ni該回邊表示的循環(huán)為：(ni,n2,n3,n4,n5,n6),入口為ni,出口為防9.（武漢大學(xué)1991年）試對下面的程序段進行盡可能的優(yōu)化:i：=1j:=10readkl：x：=k*iy:=j*iz:=x*ywriteji:=i+1ifi<100gotolhalt并指明你進行了何種優(yōu)化，給出優(yōu)化過程的簡要說明及每種優(yōu)化后的結(jié)果形式。解答：程序的流程圖如下所示：i：=1j:=10readkl

13、：x：=k*iB 2:y:=j*iz:=x*ywriteji:=i+1ifi<100gotolhaltB3:圖7.6程序流圖由程序流圖可知，B2為一個循環(huán)。對于本題中的循環(huán)可進行以下優(yōu)化：削減強度循環(huán)中有x:=x*iy:=y*ij,k在循環(huán)中不改變值。i每次增加1,x和y的賦值運算可進行強度削減,于是程序流圖變?yōu)閳D7.7所示。B1:i：=1j:=10readkx:=0y:=0B211:x：=x+ky：=y+10z:=x*ywriteji：=i+1ifijh<100gotol1haltB3:圖7.7削減強度后的程序流圖刪除歸納變量由于i是循環(huán)中的基本歸納變量，x、y是與y同族的歸納變

14、量，且有線性關(guān)系x：=k*iy:=j*i所以，i<100完全可用x<100*k或y<100*j代替。于是，進一步優(yōu)化為圖7.8所示。代碼外提將循環(huán)中不變運算writejtl:=100*k提到循環(huán)外的前置節(jié)點B21中，于是程序流圖變?yōu)?.9所示的情形。i：=1j:=10readkx:=0y:=011：x：=x+ky:=y+10z:=x*ywritejtl:=100*kifijh<tlgotol1R:BI23：圖7.8歸納變量后的程序流圖i：=1j:=10readk2I:x:=0y:=0writejtl:=100*k2：l1:x:=x+ky：=y+10z:=x*yifijh

15、<tlgotol13：halt圖7.9代碼外提后的程序流圖10 .在循環(huán)優(yōu)化中，為什么要代碼外提？試說明在哪些情況下代碼可外提？解答：代碼外提可以減少循環(huán)中的指令數(shù)目，從而節(jié)省目標(biāo)代碼運行的時間。對于循環(huán)中L的每一個不變運算s：A:=BopC或A:=B檢查它是否滿足以下兩個條件：（1） （a）s所在的節(jié)點是L的所有的出口節(jié)點的必經(jīng)節(jié)點；（b） A在L中其他地方未再定值；（c） L中所有A的引用點只有s中A的定植才能到達。（2） A離開L后不再是活躍的，并且條件（1）中的（a）和（b）成立，所謂A離開L后不再是活躍的，是指A在L的任何出口節(jié)點的后繼節(jié)點（當(dāng)然是指那些不屬于L的后繼）入口處不

16、是活躍的。符合上述（1）或（2）的不變運算s可以外提到L的前置節(jié)點中。但是。S的運算對象（8或。）是在L中定植的，那么只有當(dāng)這些定植代碼都已外提到前置節(jié)點中時。才能把s也提到前置節(jié)點中。11 .以下循環(huán)是最內(nèi)循環(huán)，是對其進行循環(huán)優(yōu)化。A:=0I :=1II :B:=J+1C:=B+IA:=C+AIFI=100GOTOL21 :=I+1GOTOL1L2:解答：程序的流程圖如圖所表示BlB2B3有流程圖可見，B2,B3是一個循環(huán)，該循環(huán)可進行以下有話：代碼外提B2中的B:=J+1是循環(huán)的不變運算，可提到循環(huán)外。刪除歸納變量I是循環(huán)的基本歸納變量，C是與I同組的歸納變量，且二者有如下線性關(guān)系：C:=

17、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)語句FORi:=1TOnDOBEGINaa:=u*vb:=m*mc:=c+b*bEND試寫出循環(huán)外提后的結(jié)果。解答：該語句的四元式為：(1) (：=,1,i)(2) )(-,n,i,To)(3) (BMZ,To,(14)(4) (*,u,v,Ti)(5)(k,Ti,a)(6) (*,m,m,T2)(k,T2,b)(8) (*,b,b,T3)(9) (+,c,T3,T4)(10) (:二,T4,c)(11) (+,1,i,T5)(12) (:=,T5,i)(13) (BR,(2)由于a:=u*v；b:=m*m是循環(huán)的不變運算，均可外提；且b:=m*m;外提后，b*b也是循環(huán)的不變運算，也可外提。優(yōu)化后的四元式如下：(1) (：=,1,i)(2) (*,u,v,Ti)(3)(k,Ti,a)(4) (*,m,m,T2)(5)(k,T2,b)(6)(*,b,b,T3)(k，0,c)(8) )(-,n,i,To)(9) (BMZ,To,(14)(10) (+,C,T3,T4)(11