【正文】 法和流圖中自然循環(huán)的識(shí)別算法 ? 對(duì)各種數(shù)據(jù)流分析方程的認(rèn)識(shí)和區(qū)分 ， 和對(duì)這些方程迭代求解方法的理解 ? 了解如何利用控制流分析的信息和各種數(shù)據(jù)流分析的信息進(jìn)行各類代碼改進(jìn)變換 例題與習(xí)題解答 [例 10。 1]試對(duì)以下基本塊 B1應(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 F:=H*G L:=F M:=L 并就以下兩種情況分別寫出優(yōu)化后的四元式序列： （ 1）假設(shè) G、 L、 M在基本塊后面背引用； （ 2）假設(shè)只有 L在基本塊后被引用。 解：對(duì)于 B1其 DAG圖： n1 B n2 C n3 * A,G n4 / D n5 + E n6 2 n7 F * n8 * H n9 * F,L,M (1)若只有 G、 L、 M在基本塊后被引用，則優(yōu)化為： G := B*C H := G*G L := H*G M := L (2) 若只有 L在基本塊后被引用，則優(yōu)化為： G := B*C H :=G*G L := H*G [例 10。 2] 試寫出以下程序段 for I := 1 to M do for j := 1 to N do A[I, j ] := B[I, j ] 的三地址代碼，然后求出其中的循環(huán)，并進(jìn)行循環(huán)優(yōu)化。 解： 三地址代碼： (1) I := 1 (2) j := 1 B1 (3) If IM goto (30) (4) If jN goto (13) (5) T1 := I * N (6) T2 := T1 + j (7) T3 := N + 1 (8) T4 := add(A)T3 (9) T5 := add(B)T3 (10) T4[T2] := T5[T2] (11) j := j + 1 (12) Goto (4) (13) I := I+1 (14) j :=1 (15) goto (3) (30) B2 B3 B4 B5 B6 代碼外提： （ 1） I := 1 (2) j := 1 (7) T3 := N + 1 (8) T4 := add(A)T3 (9) T5 := add(B)T3 (3) If IM goto (30) (5) T1 := I * N (4) If j N goto (13) (6) T2 := T1 + j (10) T4[T2] := T5[T2] (11) j := j + 1 (12) goto (4) (13) I := I + 1 (14) j := 1 (15) goto (3) (30) B1 B2’ B2 B3’ B3 B4 B5 B6 強(qiáng)度消弱： (1) I := 1 (2) j := 1 (7) T3 := N + 1 (8) T4 :=add(A) T3 (9) T5 :=add(B)T3 (5’) T1 :=I * N (3) if I M goto (30) (4) If j N goto (13) (6) T2 := T1 + j (10) T4[T2] := T5[T2] (11) j := j + 1 (12) Goto (4) (13) I := I + 1 (5) T1 := T1 + N (14) j := 1 (15) Goto (3) (30) B1 B2’ B2 B3 B4 B5 B6 強(qiáng)度消弱 (1): （ 1） I := 1 (2) j := 1 (7) T3 := N + 1 (8) T4 := add(A)T3 (9) T5 := add(B)T3 (5) T1 := I * N (3) If IM goto (30) (5) T2 := T1 + j (4) If j N goto (13) (10) T4[T2] := T5[T2] (11) j := j + 1 (6)’ T2 := T2 + 1 (12) goto (4) (13) I := I + 1 (5)’ T1 := I + N (14) j := 1 (15) goto (3) (30) B1 B2’ B2 B3’ B3 B4 B5 B6 刪除歸納變量： (1) I := 1 (2) j := 1 (7) T3 := N + 1 (8) T4 := add(A) – T3 (9) T5 := add(B) – T3 (5) T1 := I*N (3’) R := M*N (3) If T1 R goto (30) (4‘ ) Q := T1 + N (4) If T2 Q goto (13) (10) T4[T2] := T5[T2] (11) T2 := T2 + 1 (12) Goto (4) (13) T1 := T1 + 1 (14) T2 := T1 + 1 (15) Goto (3) (30) B1 B2’ B2 B3’ B3 B4 B5 B6 [例 10。 3]給出下面循環(huán)語句的流圖并進(jìn)行優(yōu)化： 語句： for I := 1 to 10 do A[I, J*5] := J+2 （ 其中 A 為 10X10二維數(shù)組） 解 : （ 1） I := 1 (2) If I10 goto (11) (3) T1:= J*5 (4) T2 := I*10 (5) T3 := T1 + T2 (6） T4 := add(A)11 (7) T5 := J + 2 (8) T4[T3] := T5 (9) I := I + 1 (10) Goto B2 (11) B1 B2 B3 B4 代碼外提： （ 1） I := 1 (3） T1 := J* 5 (6) T4 :=add(A) – 11 (7) T5 := J + 2 (2) If I10 goto (11) (4) T2 :=I * 10 (5) T3 := T1 + T2 (8) T4[T3] ： = T5 (9) I := I + 1 (10) Goto B2 (11) B1 B2’ B2 B3 B4 強(qiáng)度消弱： （ 1） I := 1 (3) T1 := J * 5 (6） T4 := Add(A) – 11 (7) T5 := J + 2 (4) T2 := I * 10 (5) T3 := T1 + T2 (2) If I10 goto (11) (8)T4[T3] := T5 (9) I := I + 1 (4’) T2 := T2 + 10 (5’) T3 := T3 + 10 (10) goto B2 (11) B1 B2’ B2 B3 B4 刪除歸納變量： (1) I := 1 (3) T1 := J * 5 (6) T4 := Add(A) – 11 (7) T5 := J + 2 (4) T2 := I * 10 (5) T3 := T1 + T2 (2’) R := T1 + 100 (2) If T3 R goto (11) (8) T4[T3] := T5 (5) T3 := T3 + 10 (10) Goto B2 (11) 例 題 1 UNIX 下的 C編譯命令 cc的選擇項(xiàng) g和 O的解釋如下 , 其中 dbx 的解釋是 “ dbx is an utility for sourcelevel debugging and execution of programs written in C”。 試說明為什 么用了選擇項(xiàng) g后 ， 選擇項(xiàng) O便被忽略 。 g Produce additional symbol table information for dbx(1) and dbxtool(1) and pass lg option to ld(1) (so as to include the g library, that is: /usr/lib/). When this option is given, the O and R options are suppressed. O[level] Optimize the object code. Ignored when either g, go, or a is used. ... 例 題 2 一個(gè) C語言程序如下： main() pushl %ebp { movl %esp,%ebp int i,j,k。 movl $1,%eax j=1 i=5。 movl $6,%edx k=6 j=1。 L4: while(j100){ addl %edx,%eax j=j+6 k=i+1。 cmpl $99,%eax j=j+k。 jle .L4 while(j?99) } } 例 題 2 一個(gè) C語言程序如下： main() pushl %ebp { movl %esp,%ebp int i,j,k。 movl $1,%eax j=1 i=5。 movl $6,%edx k=6 j=1。 L4: while(j100){ addl %edx,%eax j=j+6 k=i+1。 cmpl $99,%eax j=j+k。 jle .L4 while(j?99) } 復(fù)寫傳播 、 常量合并 、 代碼外提 、 刪除無用賦值 } 對(duì) i， j和 k分配內(nèi)存單元也成為多余 ， 從而被取消 例 題 3 一個(gè) C語言程序 main() { long i,j。 while (i) { if (j) { i = j。 } } } 生成的匯編碼見右邊 pushl %ebp movl %esp,%ebp subl $8,%esp .L2: cmpl $0,4(%ebp) jne .L4 jmp .L3 .L4: cmpl $0,8(%ebp) je .L5 movl 8(%ebp),%eax movl %eax,4(%ebp) .L5: jmp .L2 .L3: 例 題 3 一個(gè) C語言程序 main() { long i,j。 while (i) { if (j) { i = j。 } } } 優(yōu)化編譯的匯編碼見右邊 pushl %ebp movl %esp,%ebp .L7: testl %eax,%eax je .L3 testl %edx,%edx je .L7 movl %edx,%eax jmp .L7 .L3: 例 題 4 求最大公約數(shù)的函數(shù) long gcd(p,q) long p,q。 { if (p%q == 0) return q。 else return gcd(q, p%q)。 } 其中的遞歸調(diào)用稱為尾遞歸 .對(duì)于尾遞歸 ,編譯器可以產(chǎn)生和一般的函數(shù)調(diào)用不同的代碼 ,使得目標(biāo)程序運(yùn)行時(shí) ,這種遞歸調(diào)用所需的存儲(chǔ)空間大大減少 ,也縮短了運(yùn)行時(shí)間 .對(duì)于尾遞歸 ,編譯器應(yīng)怎樣產(chǎn)生代碼 ? 例 題 4 求最大公約數(shù)的函數(shù) long gcd(p,q) long p,q。 { if (p%q == 0) return q。 else return gcd(q, p%q)。 } ? 計(jì)算調(diào)用的實(shí)在參數(shù) q和 p%q， 存放在不同的寄存器中 ? 將上述寄存器中實(shí)在參數(shù)的值存入當(dāng)前活動(dòng)記錄中形式參數(shù) p和 q的存儲(chǔ)單元 ? 轉(zhuǎn)到本函數(shù)第一條語