代碼優(yōu)化定義、方法和技術(shù)

1、代碼優(yōu)化定義、方法和技術(shù)教學(xué)目的：正確理解代碼優(yōu)化的定義和各種可能的優(yōu)化概念；掌握用DAG表示進(jìn)行局部優(yōu)化的方法、循環(huán)優(yōu)化技術(shù)。教學(xué)重點(diǎn)與難點(diǎn)：局部優(yōu)化；DAG的構(gòu)造與應(yīng)用、循環(huán)優(yōu)化。學(xué)時(shí)分配：4學(xué)時(shí)本章知識(shí)點(diǎn)：局部優(yōu)化控制流分析和循環(huán)優(yōu)化數(shù)據(jù)流的分析與全局優(yōu)化優(yōu)化技術(shù)簡介 優(yōu) 化編譯前端代碼優(yōu)化器代碼產(chǎn)生控制流分析數(shù)據(jù)流分析代碼變換代碼優(yōu)化器的地位和結(jié)構(gòu)首頁結(jié)束1、優(yōu)化的概念：優(yōu)化的定義:對程序進(jìn)行各種等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加大，或占用存儲(chǔ)空間減少，或兩者都有。我們通常稱這種變換為優(yōu)化。11.1 優(yōu)化技術(shù)簡介首頁結(jié)束 優(yōu)化的目的是為了產(chǎn)生更高效

2、的代碼。由優(yōu)化編譯程序提供的對代碼的各種變換必須遵循下面的原則： 1)等價(jià)原則 主要指優(yōu)化后的目標(biāo)代碼運(yùn)行時(shí)間較短,以及占用的存儲(chǔ)空間較小。 2)有效原則 使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間確實(shí)較短，占用的空間確實(shí)較小 3）合算原則 應(yīng)盡可能以較低的代價(jià)取得較好的優(yōu)化效果2、優(yōu)化的原則首頁結(jié)束3、代碼優(yōu)化的基本方法按照與機(jī)器相關(guān)的程度，代碼優(yōu)化分為：與機(jī)器相關(guān)的優(yōu)化：在生成目標(biāo)程序時(shí)進(jìn)行的，它在很大程度上與具體的計(jì)算機(jī)有關(guān)。 與機(jī)器無關(guān)的優(yōu)化：在語法、語義分析生成中間代碼之后，在中間代碼上進(jìn)行，這一類優(yōu)化不依賴于具體的計(jì)算機(jī)，而取決于語言的結(jié)構(gòu)。首頁結(jié)束根據(jù)優(yōu)化所涉及的程序范圍分成:局部優(yōu)化：基

3、本塊范圍內(nèi)的優(yōu)化：合并已知量消除公共子表達(dá)式，削減計(jì)算強(qiáng)度和刪除無用代碼循環(huán)優(yōu)化：主要是基于循環(huán)的優(yōu)化，包括循環(huán)不變式外提，歸納變量刪除，計(jì)算強(qiáng)度削減。全局優(yōu)化：主要是在整個(gè)程序范圍內(nèi)進(jìn)行的優(yōu)化。因?yàn)槌绦蚨问欠蔷€性的，因此需要分析程序的控制流和數(shù)據(jù)流，處理比較復(fù)雜。4、優(yōu)化技術(shù)合并常量計(jì)算消除公共子表達(dá)式削減計(jì)算強(qiáng)度刪除無用代碼循環(huán)不變表達(dá)式外提歸納變量刪除首頁結(jié)束演示局限于基本塊范圍內(nèi)的優(yōu)化稱為基本塊內(nèi)的優(yōu)化或局部優(yōu)化 。 1、基本塊的定義 所謂基本塊是指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是其中的第一個(gè)語句，出口就是其中的最后一個(gè)語句。 11.2 局部優(yōu)化首頁結(jié)束

4、劃分四元式程序?yàn)榛緣K的算法如下：（1）求出四元式程序中各個(gè)基本塊的入口語句，它們可以是下述語句之一：程序的第一個(gè)語句；2基本塊的劃分算法緊跟在條件轉(zhuǎn)移語句后面的語句。能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的目標(biāo)語句；首頁結(jié)束（2）對以上求出的每一入口語句構(gòu)造其所屬的基本塊。它是由該入口語句到另一入口語句(不包括該入口語句)，或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)，或到一停語句（包括該停語句)之間的語句序列組成的。（3)凡未被納入某一基本塊的語句，都是程序中控制流程無法到達(dá)的語句，因而也是不會(huì)被執(zhí)行到的語句，將其刪除。2基本塊的劃分算法首頁結(jié)束【例如】有下列三地址代碼程序：1）read X2）rea

5、d Y3）R：=X mod Y4）if R=0 goto (8)5) X:=Y6) Y:=R7) goto (3)8）write Y9) halt劃分為4個(gè)基本塊:B11）、2） B23)、4） B35）、 6）、7）B48）、9） 首頁結(jié)束【例如】劃分基本塊(1) read (C)(2) A:= 0(3) B:= 1(4) L1: A:=A + B(5) if B= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt劃分為4個(gè)基本塊:B1（1）、（2）、（3） B2（4）、（5） B3（ 6）、（7）B4（8）、（9） 首頁結(jié)束3、

6、基本塊的變換基本塊內(nèi)可進(jìn)行的優(yōu)化： 合并已知常量和復(fù)寫傳播臨時(shí)變量改名交換語句的位置刪除公共子表達(dá)式刪除無用代碼首頁結(jié)束刪除公共子表達(dá)式 如果一個(gè)表達(dá)式E的值已計(jì)算過，并且在此之后E中變量的值沒有改變，則稱E為公共子表達(dá)式，為避免重復(fù)計(jì)算而刪除，稱為刪除公共子表達(dá)式【例如】x:=(a+b)*c-(a+b)2t1=a+b;t2=t1*c;t3=a+b;t4=t32X:=t2-t4;t1=a+b; t2=t1*c;t4=t12 X:=t2-t4;變換后首頁結(jié)束x+y*t-a*(x+y*t)/(y*t)(1)( *， y， t， t1 )(2)( +， x， t1， t2 )(3)( *， y，t，

7、 t3 )(4)( +， x， t3， t4 ) (5)( *， a，t4，t5 )(6)( *， y， t， t6 )(7)( /， t5，t1，t7 )(8)( -， t2， t7， t8 )消除公共子表達(dá)式之后：(1)( *， y，t， t1 )(2)( +， x， t1，t2 )(3)( *， a，t2，t5 )(4)( /， t5， t1， t7 )(5)( -， t2，t7，t8 )【例如】返回首頁結(jié)束刪除無用代碼 若某些變量的值在整個(gè)程序中不再使用，那么這些變量的賦值對程序運(yùn)行結(jié)果沒有任何作用，那么就可以刪除對這些變量賦值的代碼，稱為刪除無用代碼或刪除無用賦值?！纠纭咳鬞7、T

8、8、T6在以后的程序中不再使用T6:=T2X:=T3T7:=T2T8:=T4aT2:=T5aT4:=T3變換后aT2:=T5aT4:=T3返回首頁結(jié)束合并已知量a = 10 * 5 + 6 - b;t0 = 10;t1 = 5 ;t2 = t0 * t1 ;t3 = 6 ;t4 = t2 +t3 ；t5 = t4 b;a = t5 ; 合并后： t0 = 56 ; t1 = t0 b ;a = t1 ;首頁結(jié)束【例】d = 2*3.14*r(1) ( *，2，t1 )(2) ( *，t1 ， r，t2 )(3) ( =，t2， ， d )的值在編譯時(shí)刻就可以確定。(1) ( *，r，t2 )(

9、2) ( =，t2， ， d )首頁結(jié)束返回復(fù)寫傳播 形成為f := g的賦值叫做復(fù)寫語句。 。 優(yōu)化過程中會(huì)大量引入復(fù)寫。 復(fù)寫傳播變換的做法是在復(fù)寫語句f:=g后，盡可能用g代表f 。 復(fù)寫傳播變換本身并不是優(yōu)化，但它給其它優(yōu)化如常量合并和死代碼刪除帶來機(jī)會(huì)。t2 = t1 ;t3 = t2 * t1;t4 = t3 ;t5 = t3 * t2 ;c = t5 + t4 ;t3 = t1 * t1 ;t5 = t3 * t1 ;c = t5 + t3 ;【例】返回重新命名臨時(shí)變量例如: t:=b+c u:=b+c返回交換語句次序目的：減少臨時(shí)變量【例如】相鄰兩個(gè)語句t1:=b+c t2:=

10、x+yt2:=x+y t1:=b+c基本塊優(yōu)化的實(shí)現(xiàn)從四元式序列構(gòu)造DAG ，然后再從DAG重寫四元式。4、基本塊的有向圖DAG表示基本塊內(nèi)部優(yōu)化實(shí)現(xiàn)的主要工具為： DAG(Directed Acyclic Graph的縮寫) DAG :如果有向圖中任一通路都不是環(huán)路,則稱該有向圖為無環(huán)路有向圖，也稱有向非循環(huán)圖,簡稱DAG。 用DAG圖表示各個(gè)值的計(jì)算/依賴關(guān)系。演示返回DAG圖中結(jié)點(diǎn)的特點(diǎn)1.葉結(jié)點(diǎn) 標(biāo)記:標(biāo)識(shí)符名(變量名)或常數(shù),寫在結(jié)點(diǎn)下面。代表:該結(jié)點(diǎn)代表該變量或常數(shù)的值。地址的表示：Addr(A)通常將其標(biāo)識(shí)符加上下標(biāo)0,表示該變量的初值。2.內(nèi)部結(jié)點(diǎn)標(biāo)記:一個(gè)運(yùn)算符號，寫在結(jié)點(diǎn)下

11、面。代表:利用后續(xù)結(jié)點(diǎn)運(yùn)算出來的值。3圖中各個(gè)結(jié)點(diǎn)可能附加一個(gè)或多個(gè)標(biāo)識(shí)符,表示這些標(biāo)識(shí)符具有該結(jié)點(diǎn)所代表的值，同一個(gè)結(jié)點(diǎn)的標(biāo)識(shí)符表示相同的值，寫在結(jié)點(diǎn)右面。 四元式相應(yīng)的DAG（1）A：= op B 1型該算法只對如下三種四元式構(gòu)造DAG： 0型 A:=B l型 A:=op B 2型 A:=B op C op是雙目運(yùn)算符還可以是=或=?；緣K的DAG構(gòu)造算法輸入：一個(gè)基本塊輸出：相應(yīng)DAG圖算法說明：通過逐個(gè)掃描四元式來逐漸建立DAG圖。函數(shù)node(A)的值或者是一個(gè)結(jié)點(diǎn)的編號n或者無定義。如果是前一種情況，代表存在一個(gè)結(jié)點(diǎn)n，A是其上的標(biāo)記或附加標(biāo)識(shí)符?；緣K的DAG構(gòu)造算法首先DAG為

12、空。對基本塊的每一四元式，依次執(zhí)行：1如果NODE（B）無定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義NODE（B）為這個(gè)結(jié)點(diǎn)；如果當(dāng)前四元式是0型，則記NODE(B)的值為n，轉(zhuǎn)4。如果當(dāng)前四元式是1型，則轉(zhuǎn)2.(1)。如果當(dāng)前四元式是2型，則： (I)如果NODE(C)無定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)并定義NODE(C) 為這個(gè)結(jié)點(diǎn)； (II)轉(zhuǎn)2.(2) 2（合并已知量）（1）如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點(diǎn) ，則轉(zhuǎn)2(3)，否則轉(zhuǎn)3.（1）。（2）如果NODE(B)和NODE(C)都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)2.（4），否則轉(zhuǎn)3.（2）。（3）執(zhí)行op B（即合并已知量），令得到的新常數(shù)

13、為P。如果NODE(B)是處理當(dāng)前四元式時(shí)新構(gòu)造出來的結(jié)點(diǎn)，則刪除它。如果NODE(P)無定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4。（4）執(zhí)行B op C（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)或NODE(C)是處理當(dāng)前四元式時(shí)新構(gòu)造出來的結(jié)點(diǎn)，則刪除它。如果NODE(P)無定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4?；緣K的DAG構(gòu)造算法基本塊的DAG構(gòu)造算法 3（找公共子表達(dá)式）（1）檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為NODE(B)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)

14、該結(jié)點(diǎn)為n，轉(zhuǎn)4。（2）檢查中DAG中是否已有一結(jié)點(diǎn)，其左后繼為NODE(B)，其右后繼為NODE(C)，且標(biāo)記為op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4。 4. （刪除無用賦值語句）如果NODE(A)無定義，則把A附加在結(jié)點(diǎn)n上并令NODE(A)=n；否則先把A從NODE(A)結(jié)點(diǎn)上附加標(biāo)識(shí)符集中刪除（注意，如果NODE(A)是葉結(jié)點(diǎn)，則其標(biāo)記A不刪除），把A附加到新結(jié)點(diǎn)n上并令NODE(A)=n。轉(zhuǎn)處理下一四元式。僅含0,1,2型四元式的基本塊的DAG構(gòu)造算法:首先：假定DAG為空，即沒有任何結(jié)點(diǎn)。對基本塊中的每一四元式依次執(zhí)行

15、：【例】構(gòu)造下列四元式序列的DAG圖。(1) T0(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6演示根據(jù)DAG圖重寫四元式后得到如下優(yōu)化的四元式序列：(2)T1:=6.28 (合并已知量)(3)T3:=6.28 (合并已知量)(4)T2:=R+r(5)T4:=T2( 刪除公共子表達(dá)式)(6)A:=6.28*T2(7)T5:=A ( 刪除公共子表達(dá)式)(8)T6:=R-r(9)B:=A*T6(刪除無用代碼) 【例】試對以下基本塊B1應(yīng)用D

16、AG進(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)化后的四元式序列：若某個(gè)變量在基本塊后不被引用,可刪除。（1）假設(shè)G、L、M在基本塊后面被引用；（2）假設(shè)只有L在基本塊后被引用。解：對于B1其DAG圖：(1)若只有G、L、M在基本塊后被引用，則優(yōu)化為： G := B*C H := G*G L := H*G M := Ln1+*n3Bn2C*A,Gn4/En62n7F*n8H*F,L,MDn5n9 (2) 若只有L在基本塊后被引用，則優(yōu)化為： G := B*C H :=G*G

17、L := H*G11.3 控制流分析和循環(huán)的優(yōu)化 定義：以基本塊為結(jié)點(diǎn)，將控制流信息增加到基本塊的集合上來表示一個(gè)程序而得到的有向圖，稱為程序流圖。 如果一個(gè)結(jié)點(diǎn)的基本塊入口語句是程序的第一條語句，則此結(jié)點(diǎn)為首結(jié)點(diǎn)。 如果在某個(gè)執(zhí)行順序中基本塊B2緊接在基本塊B1之后執(zhí)行，則從B1到B2有一條有向邊。一、程序流圖【例如】有下列三地址代碼程序，給出程序流程圖。1）read X2）read Y3）R：=X mod Y4）if R=0 goto (8)5) X:=Y6) Y:=R7) goto (3)8）write Y9) halt演示【例】有下列三地址代碼程序，給出程序流程圖。(1）I:= 1(2

18、) if I 10 goto (15)(3) T1:=2*J(4) T2:= 10 * I(5) T3:=T2 + T1(6) T4:=add(A) 11(7) T5:=2 * J(8) T6:= 10 * I(9) T7:= T5 + T6(10) T8:=add(A) - 11 (11) T9:= T8T7(12）T4T3:= T9 + 1(13) I:= I + 1(14) goto (2)(15)演示循環(huán)是程序流圖中具有唯一入口結(jié)點(diǎn)的強(qiáng)連通子圖。說明：1.強(qiáng)連通的(任意兩結(jié)點(diǎn)間,必有一條通路,且該通路上各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列)2.它們中間有且只有一個(gè)是入口結(jié)點(diǎn)。二、循環(huán)的查找必經(jīng)結(jié)點(diǎn)：

19、在程序流圖中，對任意兩個(gè)結(jié)點(diǎn)m和n，若從流圖的首結(jié)點(diǎn)出發(fā)，到達(dá)n的任一通路都要經(jīng)過m，則稱m是n的必經(jīng)結(jié)點(diǎn)，記為 m DOM n,流圖中結(jié)點(diǎn)n的所有必經(jīng)結(jié)點(diǎn)的集合，稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集，記為D(n).回邊：設(shè)n-m是流圖中的一條有向邊，且m DOM n,則稱n-m是流圖中的一條回邊。【例】對下面語句劃分基本塊，畫出程序流程圖a:=1;if a=b then b:=1 else c:=1endif;d:=a+b1、翻譯的四元式是：1）a:=12) IF a=b goto 4)3) goto 6)4)b:=1 5)goto 7)6)c:=17) d:=a+b;步驟：1、翻譯為四元式2、劃分基本塊

20、，畫程序流程圖2、劃分基本塊，畫程序流程圖1）a:=12) IF a=b goto 4)3) goto 6)4)b:=1 5)goto 7)6)c:=17) d:=a+b;(1) read (C)(2) A:= 0(3) B:= 1(4) L1: A:=A + B(5) if B= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt【例】對下面語句劃分基本塊，畫出程序流程圖?！纠纭?6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 1必經(jīng)結(jié)點(diǎn) 必經(jīng)結(jié)點(diǎn)集D(6)=1,2,4,6D(1)=1D(2)=1,2D(3)=1,2

21、,3D(4)=1,2,4D(5)=1,2,4,5D(7)=1,2,4,7 3下圖給出求回邊n-d組成的循環(huán)的算法：procedure insen(m)； if m不屬于loop then begin loop:loop Um； 把m下推進(jìn)棧stack； end；*主程序* Stack：空； loop:d； insert(n)； while stack 非空 dObegin 把stack的棧頂元素m上托出去 for p P(m)dO insert(p)end 其中P(m)表示結(jié)點(diǎn)m的前驅(qū)結(jié)點(diǎn)集，stack為工作棧，loop為所求循環(huán)。insert為一過程。 算法的基本思想是：由于要求回邊n-d組

22、成的循環(huán)，這個(gè)循環(huán)將以d為其唯入口，n是它的一個(gè)出口。若n不等于d，則n的所有前驅(qū)結(jié)點(diǎn)應(yīng)屬于循環(huán)。當(dāng)求出n的所有前驅(qū)后，只要它們不是循環(huán)入口d，就應(yīng)再求出它們的前驅(qū)，新求出的所有前驅(qū)也應(yīng)屬于循環(huán)。然后再對新求出的所有前驅(qū)，重復(fù)以上步驟，直到所求出的前驅(qū)是d為止。此時(shí)算法結(jié)束?；剡?6 6循環(huán) 6 7 4 4,5,6,7 4 2 2,3,4,5,6,7 【例】 6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 3 1四元式序列如下：1）J：=0;2)L1:I=0;3)IF I8 goto L34)L2:A:=B+C5)B:=D*C6)L3:IF B=0 goto L4;7)write

23、 B;8)goto L5;9)L4:I:=I+1;10)IF I8 goto L2;11)L5:J:=J+1;12)IF JB goto B4B1I:=2B:=I+YB3A:=A+1J:=M+NY:=Y-1IF YB goto B4B1I:=2B:=I+YB3A:=A+1Y:=Y-1IF Y 10 goto (15)(3) T1:=2*J(4) T2:= 10 * I(5) T3:=T2 + T1(6) T4:=add(A) 11(7) T5:=2 * J(8) T6:= 10 * I(9) T7:= T5 + T6(10) T8:=add(A) - 11 (11) T9:= T8T7(12）

24、T4T3:= T9 + 1(13) I:= I + 1(14) goto (2)(15) 劃分基本塊并劃出流程圖：（1）I := 1(2) If I 10 goto (15)(3) T1 :=2*J(4) T2 := 10 * I(5) T3 :=T2 + T1(6) T4 :=add(A) 11(7) T5 :=2 * J(8) T6 := 10 * I(9) T7 := T5 + T6(10) T8 :=add(A) - 11 (11) T9 := T8T7(12）T4T3 := T9 + 1(13) I: = I + 1(14) goto (2)(15)B1B2B3B4 代碼外提后： （

25、1） I := 1(3) T1 := 2 * J(6) T4 := add(A) 11(7) T5 := 2 * J(8) T8 := add(A) - 11 ( (2) if I 10 goto (15) (4) T2 := 10* I (5) T3 := T2 + T1 (8) T6 := 10 * I (9) T7 := T6 + T5 (11) T9 := T8T7 (12) T4T3 := T9 +1 (13) I := I + 1 (14) goto （2）(15)B1B2B2B3B4（1） I ：= 1 (3) T1 := 2* J (6) T4 := add(A) 11 (7)

26、 T5 :=2 * J (10) T8 := add(A)-11 (4) T2 := 10 * I (8) T6 := 10 * I(2) If I 10 goto (15)(5) T3 := T2 + T1(9) T7 := T6 + T5(11）T9 := T8T7(12) T4T3 := T9 + 1(13) I := I + 1(4) T2 := T2 + 10(8) T6 := T6 + 10(14) goto B2(15)B1B2B2B3B42 、強(qiáng)度消弱：指把程序中執(zhí)行時(shí)間較長的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算 3、刪除歸納變量再次強(qiáng)度消弱 如果，T2, T6出循環(huán)后不是活動(dòng)變量，則

27、可在循環(huán)后刪除。 (1) I := 1(3) T1 := 2 * J(6) T4 := add(A)-11(7) T5 :=2 * J(10) T8 := add(A)-11(4) T2 := 10*I(8) T6 := 10*I(5) T3 := T2 + T1(9) T7 := T6 + T5(2)if I 10 goto(15) (11)T9 := T8T7(12)T4T3 :=T9 +1(13) I := I+1(4) T2 :=T2 +10(8) T6 :=T6 +10(5) T3 :=T3 +10(9) T7 := T7 +10(14) goto B2(15)B1B2B2B3(15

28、) (2) if T3R goto (15)(3) T1 := 2 * J(6) T4 :add(A) 11(7) T5 := 2 * J(10) T8 :=add(A) 11(4) T2 :=10 * I(8) T6 :=10 * I(5) T3 :=T2 + T1(9) T7 := T6 + T5(2) R = 100 + T1 （1） I ：= 1B1B2(11) T9 := T8T7(12) T4T3 :=T9 + 1(5) T3 := T3 + 10(9) T7 := T7 + 10(14) Goto B2B2B3解： 三地址代碼： (1) I := 1 (2) j := 1B1例3

29、 試寫出以下程序段 for I := 1 to M do for j := 1 to N do AI, j := BI, j 的三地址代碼，然后求出其中的循環(huán)，并進(jìn)行循環(huán)優(yōu)化。 (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) T4T2 := T5T2(11) j := j + 1(12) goto (4)(13) I := I+1(14) j :=1(15) goto (3)(30)B2B3

30、B4B5B6代碼外提：（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) T4T2 := T5T2 (11) j := j + 1 (12) goto (4) (13) I := I + 1 (14) j := 1 (15) goto (3) (30)B1B2B2B3B3B4B5B6強(qiáng)度消弱：I := 1j := 1(7) T3 := N + 1(8

31、) 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) T4T2 := T5T2(11) j := j + 1(12) goto (4)(13) I := I + 1(5) T1 := T1 + N(14) j := 1(15) goto (3)(30)B1B2B2B3B4B5B6強(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) T4T2 := T5T2 (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)B1B2B2B3B3B4B5B6 刪除歸