2022年編譯原理分知識(shí)點(diǎn)習(xí)題代碼優(yōu)化2

1、1與機(jī)器有關(guān)的代碼優(yōu)化有那些種類(lèi)，請(qǐng)分別舉例說(shuō)明。解答：與機(jī)器有關(guān)的優(yōu)化有：寄存器優(yōu)化，多處理優(yōu)化，特殊的指令優(yōu)化，無(wú)用的指令消除等四類(lèi)。冗余指令刪除假設(shè)源程序指令序列a:=b+c; c:=a-d; 編譯程序?yàn)槠渖傻拇a很可能是下列指令序列：mov b, r0add c, r0mov r0,a sub d, r0mov r0,c 假如第四條指令沒(méi)有標(biāo)號(hào)， 上述兩個(gè)賦值語(yǔ)句在一個(gè)基本塊內(nèi)，則第四條指令是多余的，可刪除。特殊指令的使用例如，如果目標(biāo)機(jī)器指令系統(tǒng)包含增1 指令 inc，對(duì)于 i:=i+1 的目標(biāo)代碼mov i, r0add #1, r0mov r0, i 便可被代之以 1 條指令i

2、nc i 說(shuō)明：優(yōu)化的特點(diǎn)是每個(gè)改進(jìn)可能會(huì)引發(fā)新的改進(jìn)機(jī)會(huì)，為了得到最好的改進(jìn)，一般可能需要對(duì)目標(biāo)代碼重復(fù)掃描進(jìn)行優(yōu)化。2設(shè)有語(yǔ)句序列a:=20 b:=a*(a+10); c:=a*b; 試寫(xiě)出合并常量后的三元式序列。解答：該語(yǔ)句序列對(duì)應(yīng)的三元式序列為：（1）（:=, 20,a）（2）(+, a, 10) （3）(*, a, (2) ) （4）(:=, a, b) （5）(* a, b) （6）(:=, (5), c) 合并常量后的三元式序列為：（1） （:=, 20，a）（2）(:=, 600, b) （3）(:=, 12000, c) 3、試寫(xiě)出算術(shù)表達(dá)式a+b*c-(c*b+a-e)/(

3、b*c+d) 優(yōu)化后的四元式序列。解答：該表達(dá)式的四元式序列為：（1） （*，b,c,t1）（2）(+,a,t1,t2) 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁(yè)，共 14 頁(yè) - - - - - - - - -（3）(*,c,b,t3) （4）(+,t3,a,t4) （5）(-,t4,e,t5) （6）(*,b,c,t6) （7）(+,t6,d,t7) （8）(/,t5,t7,t8) （9）(-,t2,t8,t9) 可對(duì)該表達(dá)式進(jìn)行刪除公共子表達(dá)式的優(yōu)化。優(yōu)化后的四元式序列為：（1）（*，b,c,t1）（2）(+,a,t1,t2) （

4、3）(-,t2,e,t5) （4）(+,t1,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ù)表達(dá)式的三元序列為：（1） （*,a,b）（2）(+,(1),c) （3）(*,a,b) （4）(-,(3),c) （5）(/,(2),(4) （6）(*,c,b) （7）(+,(6),a) （8）(-,(7),d) （9） （*,a,b）（10）(+,(9),c) （11）(/,(8),(10) （12）(+,(5),(11) 可對(duì)其進(jìn)行刪除公共子

5、表達(dá)式的優(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.試對(duì)以下基本塊b1和 b2應(yīng)用 dag 進(jìn)行優(yōu)化b1: a:=b*c d:=b/c e:=a+d f:=e*2 g:=b*c h:=g*g 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁(yè)，共 14 頁(yè) - - - - - - - - -9 8 5 7 f 1

6、 6 3 4 2 f:=h*g l:=f m:=l b2: b:=3 d:=a+c e:=a*c f:=d+e g:=b*f h:=a+c i:=a*c j:=h+i k:=b*5 l:=k+j m:=l并就以下兩種情況分別寫(xiě)出優(yōu)化后的四元式序列：（1） 假設(shè) g 、l、m在基本塊后面要被引用 ; （2） 假設(shè)只有 l 在基本塊后面要被引用。解答: 一般應(yīng)用 dag 在一個(gè)基本塊內(nèi)可以進(jìn)行三種優(yōu)化: 合并常量、刪除無(wú)用賦值以及多余運(yùn)算。對(duì)于基本塊 b1, 其 dag 如圖 7.1 所示。f , l , m * e * + h * a , g d * / b c 2 圖 7.1 基本塊 b1的

7、dag圖優(yōu)化后的四元式序列如下: (1) 若只有 g 、l、m在基本塊后面要被引用 g:=b*c 或 g:=b*c h:=g*g s:=g*g l:=h*g l:=s*g m:=l m:=l (s為臨時(shí)變量 ) (2) 若只有 l 在基本塊后面要被引用g:=b*c 或 s1:=b*c 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁(yè)，共 14 頁(yè) - - - - - - - - -3 8 1 7 2 6 9 5 4 h:=g*g s2:=s1*s1 l:=h*g l:=s2*s1 (s1、s2為臨時(shí)變量 ) 對(duì)于基本塊 b2, 其 dag 如圖

8、 7.2 所示。 g l,m * f,j + + d,h e,l + * b k 3 a c 15 圖 7.2 基本塊 b2的 dag 圖優(yōu)化后的四元式序列如下: (1) 若只有 g 、l、m在基本塊后面要被引用d:=a+c e:=a*c f:=d+e g:=3*f l:=f+15 m:=l (2) 若只有 l 在基本塊后面要被引用d:=a+c 或 s1:=a+c e:=a*c s2:=a*c f:=d+e s3:=s1+s2l:=f+15 l:=s3+15 (s1、s2、s3為臨時(shí)變量 ) 6. 對(duì)于基本塊 p s0:=2 s1:=3/s0 s2:=t-c s3:=t+c r:=s0/s3

9、h:=r s4:=3/s1 s5:=t+c 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁(yè)，共 14 頁(yè) - - - - - - - - -1 h 0 4 7 3 6 5 2 s6:=s4/s5h:=s6*s2(1) 試應(yīng)用 dag 進(jìn)行優(yōu)化。(2) 假定只有 r 、h在基本塊出口是活躍的 , 試寫(xiě)出優(yōu)化后的四元式序列。(3) 假定只有兩個(gè)寄存器r0、r1試寫(xiě)出上述優(yōu)化后的四元式序列的目標(biāo)代碼。解答: (1) 構(gòu)造 dag 如圖 7.3 所示。 h r, ,s6 s2 / - s3,s5 + s0,s4 s1 2 1.5 t c 圖 7.3

10、基本塊 p的 dag 圖優(yōu)化后的四元式序列為 : s0:=2 s4:=2s1:=1.5 s2:=t-c s3:=t+c s5:=s3r:=2/s3s6:=r h:=s6*s2(2) 若只有 r、h在基本塊出口是活躍的 , 優(yōu)化后的四元式序列為 : s2:=t-c s3:=t+c r:=2/s3h:=r*s2(3) 假定只有兩個(gè)寄存器r0、r1,上述優(yōu)化后的四元式序列的目標(biāo)代碼為: ld r0 t sub r0 c st r0 s2 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁(yè)，共 14 頁(yè) - - - - - - - - -b8 b2 b3

11、 b4 b7 b6 b5 b1 ld r0 t add r0 c ld r1 2 div r1 r0 ld r0 s2 mul r1 r0 st r1 h 7. 設(shè)有入圖 7.4 所示的程序流程圖 : 圖 7.4 程序流圖(1)求出流圖中各個(gè)結(jié)點(diǎn)n 的必經(jīng)結(jié)點(diǎn)集 d(n); (2)求出該流圖中的回邊 ; (3)求出該流圖中的循環(huán)。解答: (1) 在程序流圖中 , 對(duì)任意的結(jié)點(diǎn) ni和 nj, 如果從流圖的首結(jié)點(diǎn)出發(fā) , 到達(dá) nj的任一通路都必須經(jīng)過(guò)ni, 則稱(chēng) ni是 nj的必經(jīng)結(jié)點(diǎn) , 記為 ni dom nj。流圖中結(jié)點(diǎn) n的所有必經(jīng)結(jié)點(diǎn)稱(chēng)為結(jié)點(diǎn)n 的必經(jīng)結(jié)點(diǎn)集 , 記為 d (n) 。

12、流圖中各結(jié)點(diǎn) n 的必經(jīng)結(jié)點(diǎn)集 d (n) 為: d (b1) =b1 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁(yè)，共 14 頁(yè) - - - - - - - - -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) 流圖的回邊是指 : 若 ab 是流圖中一條有向邊 , 且有 b dom a,則稱(chēng) ab 是流圖的一條回邊。題目所給流

13、圖中 , 有有向邊 b7b2, 又有 d (b7)=b1,b2,b7, 所以, b2dom b7, 即 b7b2是流圖的回邊。且無(wú)其他回邊。(3) 該流圖中的循環(huán)可利用回邊求得。如果以知有向邊 nd 是一回邊 , 由它組成的循環(huán)就是由結(jié)點(diǎn)d、結(jié)點(diǎn) n 以及有通路到達(dá) n而該通路不經(jīng)過(guò) d 的所有結(jié)點(diǎn)組成 , 且 d是該循環(huán)的唯一入口結(jié)點(diǎn)。題目所給出流圖中 , 只有一條回邊 b7b2, 在該流圖中 , 凡是不能經(jīng)過(guò)結(jié)點(diǎn)b2有通路到達(dá)結(jié)點(diǎn)b7的結(jié)點(diǎn) , 只有b3,b4,b5,b6, 所以 , 由回邊b7b2組成的循環(huán)是 b2,b3,b4,b5,b6,b7 。8. ( 中國(guó)科學(xué)院計(jì)算機(jī)所1997 年

14、) 試畫(huà)出如下中間代碼序列的程序流圖, 并求出: (1)各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集合d (n); (2)流圖中的回邊與循環(huán)。j:=0; l1: i:=0; if i8 goto l3; l2: a:=b+c; b:=d*c; l3: if b=0 goto l4; write b; goto l5; l4: i:=i+1; if i8 goto l2; l5: j:=j+1; if j=3 goto l1; halt 解答: 程序的流圖入圖 7.5 所示。 (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

15、,n3 d (n4) =n0,n1,n3,n4 d (n5) =n0,n1,n3,n5 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁(yè)，共 14 頁(yè) - - - - - - - - -j:=0; l1: i:=0; if i8 goto l3; l2: a:=b+c; b:=d*c; l3: if b=0 goto l4; write b; goto l5; l4: i:=i+1; if i8 goto l2; l5: j:=j+1; if j=3 goto l1; haltd (n6) =n0,n1,n3,n6 d (n7) =n0,n1,

16、n3,n6,n7 n0 n1n2n3n4n5n6n7 圖 7.5 程序流圖（2） 流圖中的回邊有一條：即n6n1 該回邊表示的循環(huán)為： （n1,n2,n3,n4,n5,n6）, 入口為 n1, 出口為 n6 9.( 武漢大學(xué) 1991 年) 試對(duì)下面的程序段進(jìn)行盡可能的優(yōu)化：i ：= j：=read k l ： x ：=k* i y: =j* i z: =x*y write j i:=i+1 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁(yè)，共 14 頁(yè) - - - - - - - - - if i100 goto l halt 并指明你進(jìn)行了

17、何種優(yōu)化，給出優(yōu)化過(guò)程的簡(jiǎn)要說(shuō)明及每種優(yōu)化后的結(jié)果形式。解答：程序的流程圖如下所示：1：2: 3: 圖 7.6 程序流圖由程序流圖可知，為一個(gè)循環(huán)。對(duì)于本題中的循環(huán)可進(jìn)行以下優(yōu)化：削減強(qiáng)度循環(huán)中有x:=x*i y:=y*i j,k在循環(huán)中不改變值。 i 每次增加 ,x 和 y 的賦值運(yùn)算可進(jìn)行強(qiáng)度削減，于是程序流圖變?yōu)閳D7.7 所示。 b1: b2: i ：=j ：=read k l ： x ：=k* i y: =j* i z: =x*y write j i:=i+1 if i100 goto l halt i ：=j ：=readk x：=0 y：=0 l1： x：=x+k y： =y+10

18、 z： =x*y write j i：=i+1 if ijh100 goto l 1精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁(yè)，共 14 頁(yè) - - - - - - - - -：b3: 圖 7.7 削減強(qiáng)度后的程序流圖刪除歸納變量由于 i 是循環(huán)中的基本歸納變量，x、y 是與 y 同族的歸納變量，且有線(xiàn)性關(guān)系x：=k*i y：=j*i 所以， i100 完全可用 x100*k 或 y100*j 代替。于是，進(jìn)一步優(yōu)化為圖7.8所示。代碼外提將循環(huán)中不變運(yùn)算write j tl:=100*k 提到循環(huán)外的前置節(jié)點(diǎn)b21中，于是程序流圖變?yōu)?

19、.9 所示的情形。 b1: b12b2: halt i ：=j ：=readk x：=0 y：=0 l1： x：=x+k y：=y+10 z：=x*y write j tl:=100*k if ijhtl goto l 1精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 10 頁(yè)，共 14 頁(yè) - - - - - - - - - b3: 圖 7.8 歸納變量后的程序流圖b1: b21: b2: b3: 圖 7.9 代碼外提后的程序流圖10. 在循環(huán)優(yōu)化中，為什么要代碼外提？試說(shuō)明在哪些情況下代碼可外提？解答：代碼外提可以減少循環(huán)中的指令數(shù)目，從而節(jié)省目

20、標(biāo)代碼運(yùn)行的時(shí)間。對(duì)于循環(huán)中 l 的每一個(gè)不變運(yùn)算s：a：=b op c 或 a：=b 檢查它是否滿(mǎn)足以下兩個(gè)條件：（1） （a）s 所在的節(jié)點(diǎn)是 l 的所有的出口節(jié)點(diǎn)的必經(jīng)節(jié)點(diǎn)；（b）在中其他地方未再定值；（c）中所有的引用點(diǎn)只有s 中的定植才能到達(dá)。(2)離開(kāi)后不再是活躍的，并且條件（）中的（a）和（ b）成立，所謂離開(kāi)后不再是活躍的，是指在的任何出口節(jié)點(diǎn)的后繼節(jié)點(diǎn)（當(dāng)然是指那些不屬于的后繼）入口處不是活躍的。符合上述（）或（）的不變運(yùn)算 s 可以外提到的前置節(jié)點(diǎn)中。 但是。s的運(yùn)算對(duì)象（或）是在中定植的，那么只有當(dāng)這些定植代碼都已外提到前置節(jié)點(diǎn)中時(shí)。才能把s 也提到前置節(jié)點(diǎn)中。11. 以

21、下循環(huán)是最內(nèi)循環(huán)，是對(duì)其進(jìn)行循環(huán)優(yōu)化。 a := 0 i ：=j ：=readk x：=0 y：=0 write j tl:=100*k l1： x：=x+k y：=y+10 z：=x*y if ijhtl goto l 1halt 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 11 頁(yè)，共 14 頁(yè) - - - - - - - - - i := 1 l1: b := j + 1 c := b + i a := c + a if i = 100 goto l2 i := i + 1 goto l1 l2: 解答：程序的流程圖如圖所表示有流程圖可見(jiàn)，

22、 b2, b3 是一個(gè)循環(huán)，該循環(huán)可進(jìn)行以下有話(huà)：代碼外提 b2中的 b := j + 1是循環(huán)的不變運(yùn)算，可提到循環(huán)外。刪除歸納變量 i 是循環(huán)的基本歸納變量， c是與 i 同組的歸納變量，且二者有如下線(xiàn)性關(guān)系： c: := b + i于是 i = 100 完全可用 c = b + 100代替。相應(yīng)的i := i +1可用 c := c + 1代替。 于是流程圖變?yōu)閳D所表示精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 12 頁(yè)，共 14 頁(yè) - - - - - - - - -圖 7.10 優(yōu)化后的程序流圖14設(shè)有循環(huán)語(yǔ)句for i:=1 to n do begina a:=u*v b:=m*m c:=c+b*b end 試寫(xiě)出循環(huán)外提后的結(jié)果。解答：該語(yǔ)句的四元式為：（1） （:=，1, , i）（2）) (-, n, i, t0 ) （3）(bmz, t0, ， （14）) （4） （*，u, v, t1 ）（5） （:=, t1， ， a）（6） （*， m, m, t2）（7） （:=, t2， ， b）（8） （*，b, b, t3）（9） （+， c，t3，t4）（10） （：=，t4 ， ， c）