編譯原理教程課后習(xí)題答案-第五章

第五章代碼優(yōu)化5.1完成以下選擇題： (1)優(yōu)化可生成的目標(biāo)代碼。 a.運(yùn)行時(shí)間較短 b.占用存儲(chǔ)空間較小 c.運(yùn)行時(shí)間短但占用內(nèi)存空間大 d.運(yùn)行時(shí)間短且占用存儲(chǔ)空間小(2)下列優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。 a.強(qiáng)度削弱b.刪除歸納變量 c.刪除多余運(yùn)算d.代碼外提 (3)基本塊內(nèi)的優(yōu)化為。 a.代碼外提，刪除歸納變量 b.刪除多余運(yùn)算，刪除無(wú)用賦值 c.強(qiáng)度削弱，代碼外提 d.循環(huán)展開(kāi)，循環(huán)合并(4)在程序流圖中，我們稱具有下述性質(zhì)的結(jié)點(diǎn)序列為一個(gè)循環(huán)。 a.它們是非連通的且只有一個(gè)入口結(jié)點(diǎn) b.它們是強(qiáng)連通的但有多個(gè)入口結(jié)點(diǎn) c.它們是非連通的但有多個(gè)入口結(jié)點(diǎn) d.它們是強(qiáng)連通的且只有一個(gè)入口結(jié)點(diǎn) (5)關(guān)于必經(jīng)結(jié)點(diǎn)的二元關(guān)系，下列敘述中不正確的是。 a.滿足自反性b.滿足傳遞性 c.滿足反對(duì)稱性d.滿足對(duì)稱性 【解答】 (1)d(2)c(3)b(4)d(5)d5.2何謂局部?jī)?yōu)化、循環(huán)優(yōu)化和全局優(yōu)化？?jī)?yōu)化工作在編譯的哪個(gè)階段進(jìn)行？ 【解答】?jī)?yōu)化根據(jù)涉及的程序范圍可分為三種。 (1)局部?jī)?yōu)化是指局限于基本塊范圍內(nèi)的一種優(yōu)化。一個(gè)基本塊是指程序中一組順序執(zhí)行的語(yǔ)句序列(或四元式序列)，其中只有一個(gè)入口(第一個(gè)語(yǔ)句)和一個(gè)出口(最后一個(gè)語(yǔ)句)。對(duì)于一個(gè)給定的程序，我們可以把它劃分為一系列的基本塊，然后在各個(gè)基本塊范圍內(nèi)分別進(jìn)行優(yōu)化。通常應(yīng)用DAG方法進(jìn)行局部?jī)?yōu)化。 (2)循環(huán)優(yōu)化是指對(duì)循環(huán)中的代碼進(jìn)行優(yōu)化。例如，如果在循環(huán)語(yǔ)句中某些運(yùn)算結(jié)果不隨循環(huán)的重復(fù)執(zhí)行而改變，那么該運(yùn)算可以提到循環(huán)外，其運(yùn)算結(jié)果仍保持不變，但程序運(yùn)行的效率卻提高了。循環(huán)優(yōu)化包括代碼外提、強(qiáng)度削弱、刪除歸納變量、循環(huán)合并和循環(huán)展開(kāi)。5.3將下面程序劃分為基本塊并作出其程序流圖。read(A,B)F=1C=A*AD=B*BifC<DgotoL1E=A*AF=F+1E=E+Fwrite(E)haltL1:E=B*BF=F+2E=E+Fwrite(E)ifE>100gotoL2haltL2:F=F-1gotoL1【解答】先求出四元式程序中各基本塊的入口語(yǔ)句，即程序的第一個(gè)語(yǔ)句，或者能由條件語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或者條件轉(zhuǎn)移語(yǔ)句的后繼語(yǔ)句。然后對(duì)求出的每一入口語(yǔ)句構(gòu)造其所屬的基本塊，它是由該入口語(yǔ)句至下一入口語(yǔ)句(不包括該入口語(yǔ)句)或轉(zhuǎn)移語(yǔ)句(包括該轉(zhuǎn)移語(yǔ)句)或停語(yǔ)句(包括該停語(yǔ)句)之間的語(yǔ)句序列組成的。凡未被納入某一基本塊的語(yǔ)句都從程序中刪除。要注意基本塊的核心只有一個(gè)入口和一個(gè)出口，入口就是其中第一個(gè)語(yǔ)句，出口就是其中最后一個(gè)語(yǔ)句。如果發(fā)現(xiàn)某基本塊有兩個(gè)以上的入口或兩個(gè)以上的出口，則劃分基本塊有誤。程序流圖畫法是當(dāng)下述條件(1)和(2)有一個(gè)成立時(shí)，從結(jié)點(diǎn)i有一有向邊引到結(jié)點(diǎn)j： (1)基本塊j在程序中的位置緊跟在基本塊i之后，并且基本塊i的出口語(yǔ)句不是無(wú)條件轉(zhuǎn)移語(yǔ)句goto(s)或停語(yǔ)句。 (2)基本塊i的出口語(yǔ)句是goto(s)或if…goto(s)，并且(s)是基本塊j的入口語(yǔ)句。 應(yīng)用上述方法求出本題所給程序的基本塊及程序流圖見(jiàn)圖5-1，圖中的有向邊、實(shí)線是按流圖畫法(1)畫出的，虛線是按流圖畫法(2)畫出的。圖5-1程序流圖5.4基本塊的DAG如圖5-2所示。若： (1)b在該基本塊出口處不活躍； (2)b在該基本塊出口處活躍； 請(qǐng)分別給出下列代碼經(jīng)過(guò)優(yōu)化之后的代碼： (1)a=b+c(2)b=a-d(3)c=b+c(4)d=a-d圖5-2習(xí)題5.4的DAG圖【解答】(1)當(dāng)b在出口處不活躍時(shí)，生成優(yōu)化后的代碼為a=b0+c0d=a-d0c=d+c0 (2)當(dāng)b在出口活躍時(shí)，生成優(yōu)化后的代碼為a=b0+c0b=a-d0d=bc=d+c05.5對(duì)于基本塊P： S0=2 S1=3/S0 S2=T-C S3=T+C R=S0/S3 H=R S4=3/S1 S5=T+C S6=S4/S5 H=S6*S2(1)應(yīng)用DAG對(duì)該基本塊進(jìn)行優(yōu)化； (2)假定只有R、H在基本塊出口是活躍的，試寫出優(yōu)化后的四元式序列。 【解答】(1)根據(jù)DAG圖得到優(yōu)化后的四元式序列為 S0=2 S4=2 S1=1.5 S2=T-CS3=T+C S5=S3 R=2/S3 S6=R H=S6*S2 (2)若只有R、H在基本塊出口是活躍的，優(yōu)化后的四元式序列為 S2=T-C S3=T+C R=2/S3 H=R*S25.6試畫出如下中間代碼序列的程序流圖，并求出： (1)各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集合D(n)； (2)流圖中的回邊與循環(huán)。 J=0 L1：I=0 if

I<8gotoL3 L2：A=B+C B=D*C L3：if

B=0gotoL4 writeB gotoL5 L4：I=I+1 ifI<8gotoL2 L5：J=J+1 if

J<=3gotoL1 halt【解答】(1)各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集分別為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} 程序流圖如圖5-3所示。圖5-3習(xí)題5.6的程序流圖由于有n5→n2和n6→n1，而n2不是n5的必經(jīng)結(jié)點(diǎn)，n1是n6的必經(jīng)結(jié)點(diǎn)，所以n6→n1為回邊；即該回邊表示的循環(huán)為{n1,n2,n3,n4,n5,n6}，入口結(jié)點(diǎn)為n1，出口結(jié)點(diǎn)為n6。 5.7證明：如果已知有向邊n→d是一回邊，則由結(jié)點(diǎn)d、結(jié)點(diǎn)n以及有通路到達(dá)n而該通路不經(jīng)過(guò)d的所有結(jié)點(diǎn)組成一個(gè)循環(huán)。 【解答】根據(jù)題意畫出示意圖，如圖5-4所示。圖5-4具有回邊n→d的流圖證明過(guò)程如下： (1)令結(jié)點(diǎn)d、結(jié)點(diǎn)n以及有通路到達(dá)n而該通路不經(jīng)過(guò)d的所有結(jié)點(diǎn)構(gòu)成集合L(即圖5-4中的全部結(jié)點(diǎn))，則L必定是強(qiáng)連通的。為了證明這一點(diǎn)，令M=L-{d,n}。由L的組成成分可知M中每一結(jié)點(diǎn)ni都可以不經(jīng)過(guò)d而到達(dá)n。又因dDOMn(已知n→d為回邊，由回邊定義知必有dDOMn)，所以必有dDOMni，如圖5-4所示。如不然，則從首結(jié)點(diǎn)就可以不經(jīng)過(guò)d而到達(dá)ni，從而也可以不經(jīng)過(guò)d到達(dá)n，這與dDOMn矛盾。因dDOMni所以d必有通路到達(dá)M中任一結(jié)點(diǎn)ni，而M中任一結(jié)點(diǎn)又可以通過(guò)n到達(dá)d(n→d為回邊)，從而M中任意兩個(gè)結(jié)點(diǎn)之間必有一通路，L中任意兩個(gè)結(jié)點(diǎn)之間亦必有一通路。此外，由M中結(jié)點(diǎn)性質(zhì)可知：d到M中任一結(jié)點(diǎn)ni的通路上所有結(jié)點(diǎn)都應(yīng)屬于M，ni到n的通路上所有結(jié)點(diǎn)也都屬于M。因此，L中任意兩結(jié)點(diǎn)間通路上所有結(jié)點(diǎn)都屬于L，也即，L是強(qiáng)連通的。(2)因?yàn)閷?duì)所有ni∈L，都有dDOMni，所以d必為L(zhǎng)的一個(gè)入口結(jié)點(diǎn)。我們說(shuō)d也一定是L的唯一入口結(jié)點(diǎn)。如不然，必有另一入口結(jié)點(diǎn)d1∈L且d1≠d。d1不可能是首結(jié)點(diǎn)，否則dDOMn不成立(因?yàn)橛衐DOMd1，如果d1是首結(jié)點(diǎn)，則d就是首結(jié)點(diǎn)d1的必經(jīng)結(jié)點(diǎn)，則只能是d=d1，與d≠d1矛盾)。現(xiàn)設(shè)d1不是首結(jié)點(diǎn)，且設(shè)d1在L之外的前驅(qū)是d2，那么，d2和n之間必有一條通路d2→d1→…→n，且該通路不經(jīng)過(guò)d，從而d2應(yīng)屬于M，這與d2∈L矛盾。所以不可能存在上述結(jié)點(diǎn)d1，也即d是循環(huán)的唯一入口結(jié)點(diǎn)。 至此，我們已經(jīng)滿足了循環(huán)的定義：循環(huán)是程序流圖中具有唯一入口結(jié)點(diǎn)的強(qiáng)連通子圖，也即，L是包含回邊n→d的循環(huán)，d是循環(huán)的唯一入口結(jié)點(diǎn)。5.8對(duì)下面四元式代碼序列： A=0 I=1L1: B=J+1 C=B+I A=C+A ifI=100gotoL2 I=I+1 gotoL1L2: writeA halt(1)畫出其控制流程圖； (2)求出循環(huán)并進(jìn)行循環(huán)的代碼外提和強(qiáng)度削弱優(yōu)化。 【解答】(1)在構(gòu)造程序的基本塊的基礎(chǔ)上畫出該程序的流圖，如圖5-5所示。圖5-6習(xí)題5.8中代碼外提后的程序流圖我們知道，強(qiáng)度削弱不僅可對(duì)乘法運(yùn)算進(jìn)行，也可對(duì)加法運(yùn)算進(jìn)行。由于本題中的四元式程序不存在乘法運(yùn)算，所以只能進(jìn)行加法運(yùn)算的強(qiáng)度削弱。從圖5-5中可以看到，B2中的C=B+I，變量B因代碼外提其定值點(diǎn)已在循環(huán)之外，故相當(dāng)于常數(shù)。而另一加數(shù)I值由B3中的I=I+1決定，即每循環(huán)一次I值增1；也即每循環(huán)一次，B2中的C=B+I其C值增量與B3中的I相同，即常數(shù)1。因此，我們可以對(duì)C進(jìn)行強(qiáng)度削弱，即將B2中的四元式C=B+I外提到前置結(jié)點(diǎn)B2′中，同時(shí)在B3中I=I+1之后給C增加一個(gè)常量1。進(jìn)行強(qiáng)度削弱后的結(jié)果如圖5-7所示。圖5-7習(xí)題5.8中強(qiáng)度削弱后的程序流圖5.9某程序流圖如圖5-8所示。 (1)給出該流圖中的循環(huán)； (2)指出循環(huán)不變運(yùn)算； (3)指出哪些循環(huán)不變運(yùn)算可以外提。圖5-8習(xí)題5.9的程序流圖【解答】(1)流圖中的循環(huán)為{B2,B3,B4}。 (2)B3中的i=2是循環(huán)不變運(yùn)算。 (3)循環(huán)不變運(yùn)算外提的條件是： ①該不變運(yùn)算所在的結(jié)點(diǎn)是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)； ②當(dāng)把循環(huán)不變運(yùn)算A=BopC(B或opC可以沒(méi)有)外提時(shí)，要求循環(huán)中其他地方不再有A的定值點(diǎn)； ③當(dāng)把循環(huán)不變運(yùn)算A=BopC外提時(shí)，要求循環(huán)中A的所有引用點(diǎn)都是而且僅僅是這個(gè)定值所能到達(dá)的。 由于i=2所在的結(jié)點(diǎn)不是循環(huán)所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)，故不能外提。5.10一程序流圖如圖5-9所示，試分別對(duì)其進(jìn)行代碼外提、強(qiáng)度削弱和刪除歸納變量等優(yōu)化。