1、編編 譯譯 原原 理理2022年3月17日S.PO.P語義分析、生成中間代碼語義分析、生成中間代碼目標代碼生成目標代碼生成代碼優化代碼優化語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理編編 譯譯 原原 理理2022年3月17日第第7 7章代碼優化章代碼優化要求明確代碼優化的目的和分類要求明確代碼優化的目的和分類掌握基本塊的劃分方法，基本塊內的三種優化掌握基本塊的劃分方法，基本塊內的三種優化方法方法掌握程序流圖的構造方法，循環優化的三種優掌握程序流圖的構造方法，循環優化的三種優化方法化方法教學目標教學目標編編 譯譯 原原 理理2022年3月17日 7.1 局

2、部優化局部優化 7.2 循環優化循環優化教學內容教學內容編編 譯譯 原原 理理2022年3月17日7.17.1代碼優化代碼優化原則：原則： 不能改變原有不能改變原有程序語義程序語義 時間效率（減少運行時間）時間效率（減少運行時間）空間效率（減少內存容量）空間效率（減少內存容量）目的：目的：提高目標代碼提高目標代碼運行效率運行效率 優化實質上是對代碼進行優化實質上是對代碼進行等價變換等價變換，變，變換后換后代碼結構不同但運行結果相同代碼結構不同但運行結果相同。 編編 譯譯 原原 理理2022年3月17日代碼優化分類代碼優化分類 從優化的層次，從優化的層次，與機器是否有關與機器是否有關q與機器無關

3、：與機器無關：與目標機無關，在中間代碼上優化與目標機無關，在中間代碼上優化q與機器有關：與機器有關：充分利用系統資源，（指令系統，寄存器）充分利用系統資源，（指令系統，寄存器） 從優化從優化涉及的范圍涉及的范圍局部優化：局部優化：在在基本塊基本塊內進行優化。內進行優化。循環優化：循環優化：對對循環語句循環語句所生成的中間代碼進行優化。所生成的中間代碼進行優化。全局優化：全局優化：跨越多個基本塊的跨越多個基本塊的全局范圍內全局范圍內的優化，復雜。的優化，復雜。編編 譯譯 原原 理理2022年3月17日7.27.2局部優化局部優化基本塊：基本塊：程序中一個程序中一個順序執行順序執行的語句序列，的語

4、句序列，即一個程序段，它只有即一個程序段，它只有一個入口一個入口和和一個出一個出口口，入口是第一條語句，出口是最后一條，入口是第一條語句，出口是最后一條語句。語句。 在一個在一個基本塊上基本塊上進行的優化進行的優化 編編 譯譯 原原 理理2022年3月17日基本塊劃分方法基本塊劃分方法 （1 1）確定各個基本塊的的入口語句（基本塊的第）確定各個基本塊的的入口語句（基本塊的第一個語句）一個語句） 語句序列的語句序列的第一個語句第一個語句是入口語句；是入口語句； 能由能由條件轉移語句或無條件轉移語句條件轉移語句或無條件轉移語句轉到的語句轉到的語句是入口語句；是入口語句； 緊跟在緊跟在條件轉移語句或

5、無條件轉移語句后面的語條件轉移語句或無條件轉移語句后面的語句是入口語句。句是入口語句。編編 譯譯 原原 理理2022年3月17日基本塊劃分方法基本塊劃分方法（2 2）對于每個入口語句，構造其所屬的基本塊。它）對于每個入口語句，構造其所屬的基本塊。它是以下三種情況之一：是以下三種情況之一： 該入口語句到該入口語句到下一條入口下一條入口語句（不包括該入口語語句（不包括該入口語句）之間的語句序列；句）之間的語句序列； 該入口語句到該入口語句到一條轉移語句一條轉移語句（包括該轉移語句）（包括該轉移語句）之間的語句序列；之間的語句序列； 該入口語句到該入口語句到一條停語句一條停語句（包括該停語句（包括該

6、停語句）之間之間的語句序列；的語句序列；（3 3）凡）凡未被納入未被納入某一基本塊的語句，都是程序中控某一基本塊的語句，都是程序中控制流程無法到達的語句，從而也是不會被執行到制流程無法到達的語句，從而也是不會被執行到的語句，將其的語句，將其刪除刪除。 編編 譯譯 原原 理理2022年3月17日【例例8.18.1】（1 1）read Xread X（2 2）read Yread Y（3 3）R=X mod YR=X mod Y（4 4）if R= =0 gotoif R= =0 goto（8 8）（5 5）X=YX=Y（6 6）Y=RY=R（7 7）gotogoto（3 3）（8 8）write

7、 Ywrite Y（9 9）halthalt編編 譯譯 原原 理理2022年3月17日1345620101121 FACTOR=2EXP 1=IF ( )GOTO 10 BASE=2.0FACTOR=FACTOR*2GOTO 2010. BASE=11. FACTOR20. Q=21. RETURN基本塊基本塊基本塊基本塊基本塊基本塊基本塊基本塊練習：練習：編編 譯譯 原原 理理2022年3月17日基本塊內的優化方法基本塊內的優化方法1.1.合并常量：合并常量：編譯時就計算表達式中的編譯時就計算表達式中的常量運算常量運算x=1x=1a=2a=2* *x+1x+1b=x+10b=x+10c=a+

8、bc=a+b（1 1）x=1x=1（2 2）a= 3a= 3（3 3）b=11b=11（4 4）c=14c=14合并常量合并常量（1 1）x=1x=1（2 2）T T1 1=2=2* *x x（3 3）a= Ta= T1 1+1+1（4 4）b=x+10b=x+10（5 5）c=a+bc=a+b四元式四元式編編 譯譯 原原 理理2022年3月17日基本塊內的優化方法基本塊內的優化方法2 2刪除公共子表達式刪除公共子表達式 x=ax=a* *b+cb+cy=ay=a* *b+xb+xz=az=a* *b+yb+y（1 1）T T1 1= a= a* *b b（2 2）x= Tx= T1 1+c+

9、c（3 3）y= Ty= T1 1+x+x（4 4）z=Tz=T1 1+y+y刪除公共刪除公共子表達式子表達式（1 1）T T1 1= a= a* *b b（2 2）x=Tx=T1 1+c+c（3 3）T T2 2= a= a* *b b（4 4）y=Ty=T2 2+x+x（5 5）T T3 3= a= a* *b b（6 6）z=Tz=T3 3+y+y四元式四元式編編 譯譯 原原 理理2022年3月17日基本塊內的優化方法基本塊內的優化方法3 3刪除無用賦值刪除無用賦值 （1 1）x=10+ax=10+a（2 2）y=x+by=x+b（1 1）x=1x=1（2 2）x=10+ax=10+a（

10、3 3）y=x+by=x+b編編 譯譯 原原 理理2022年3月17日 7.3 7.3 基本塊的基本塊的DAGDAG表示表示 DAG(Directed Acyclic Graph)DAG(Directed Acyclic Graph)是一種有向圖，常是一種有向圖，常常用來對基本塊進行優化。一個基本塊的常用來對基本塊進行優化。一個基本塊的DAGDAG是一種其是一種其結點帶有下述標記或附加信息的結點帶有下述標記或附加信息的DAGDAG： (1) (1) 圖的葉結點圖的葉結點( (無后繼的結點無后繼的結點) )以一標識符以一標識符( (變量名變量名) )或常數作為標記，表示該結點代表該變量或常數的值

11、。或常數作為標記，表示該結點代表該變量或常數的值。如果葉結點用來表示一變量如果葉結點用來表示一變量A A的地址，則用的地址，則用addr(A)addr(A)作為作為該結點的標記。通常把葉結點上作為標記的標識符加上該結點的標記。通常把葉結點上作為標記的標識符加上下標下標0 0，以表示它是該變量的初值。，以表示它是該變量的初值。 (2) (2) 圖的內部結點圖的內部結點( (有后繼的結點有后繼的結點) )以一運算符作為以一運算符作為標記，表示該結點代表應用該運算符對其直接后繼結點標記，表示該結點代表應用該運算符對其直接后繼結點所代表的值進行運算的結果。所代表的值進行運算的結果。 (3) (3) 圖

12、中各個結點上可能附加一個或多個標識符，圖中各個結點上可能附加一個或多個標識符，表示這些變量具有該結點所代表的值。表示這些變量具有該結點所代表的值。編編 譯譯 原原 理理2022年3月17日 一個基本塊由一個四元式序列組成，且一個基本塊由一個四元式序列組成，且每一個四元式都可以用相應的每一個四元式都可以用相應的DAGDAG結點表示。圖結點表示。圖7 71 1給出了不同四元式和與其對應的給出了不同四元式和與其對應的DAGDAG結點形結點形式。圖中，各結點圓圈中的式。圖中，各結點圓圈中的nini是構造是構造DAGDAG過程中過程中各結點的編號，而各結點下面的符號各結點的編號，而各結點下面的符號( (

13、運算符、運算符、標識符或常數標識符或常數) )是各結點的標記，各結點右邊的是各結點的標記，各結點右邊的標識符是結點上的附加標識符。除了對應轉移標識符是結點上的附加標識符。除了對應轉移語句的結點右邊可附加一語句位置來指示轉移語句的結點右邊可附加一語句位置來指示轉移目標外，其余各類結點的右邊只允許附加標識目標外，其余各類結點的右邊只允許附加標識符。除對應于數組元素賦值的結點符。除對應于數組元素賦值的結點( (標記為標記為 =) =)有三個后繼外，其余結點最多只有兩個后繼。有三個后繼外，其余結點最多只有兩個后繼。編編 譯譯 原原 理理2022年3月17日n1BA(1) ABn2n1ABop(2) A

14、op Bn1Bn2Cn3opA(3) AB op Cn1Bn2Cn3 (4) AB Cn1Bn2Cn3rop(S)(5) if B rop C goto (S)n1Dn3n4(6) DCBn2 CBn1(S)(7) goto (S)圖71 四元式與DAG結點編編 譯譯 原原 理理2022年3月17日 利用利用DAGDAG進行基本塊優化的基本思想是進行基本塊優化的基本思想是：首：首先按基本塊內的四元式序列順序將所有的四元先按基本塊內的四元式序列順序將所有的四元式構造成一個式構造成一個DAGDAG，然后按構造結點的次序將，然后按構造結點的次序將DAGDAG還原成四元式序列。由于在構造還原成四元式序

15、列。由于在構造DAGDAG的同時的同時已作了局部優化，所以最后所得到的是優化過已作了局部優化，所以最后所得到的是優化過的四元式序列。的四元式序列。 為了為了DAGDAG構造算法的需要，我們將圖構造算法的需要，我們將圖7 71 1中中的四元式按照其對應結點的后繼結點個數分為的四元式按照其對應結點的后繼結點個數分為四類：四類：編編 譯譯 原原 理理2022年3月17日 (1) 0(1) 0型四元式：后繼結點個數為型四元式：后繼結點個數為0 0，如圖，如圖7 71(1)1(1)所示；所示； (2) 1(2) 1型四元式：有一個后繼結點，如圖型四元式：有一個后繼結點，如圖7 71(2)1(2)所示；所

16、示； (3) 2(3) 2型四元式：有兩個后繼結點，如圖型四元式：有兩個后繼結點，如圖7 71(3)1(3)、(4)(4)、(5)(5)所示；所示； (4) (4) 3 3型四元式：有三個后繼結點，如圖型四元式：有三個后繼結點，如圖7 71(6)1(6)所示。所示。 我們規定：用大寫字母我們規定：用大寫字母( (如如A A、B B等等) )表示四元式中表示四元式中的變量名的變量名( (或常數或常數) )；用函數；用函數Node(A)Node(A)表示表示A A在在DAGDAG中的中的相應結點，其值可為相應結點，其值可為n n或者無定義，并用或者無定義，并用n n表示表示DAGDAG中中的一個結

17、點值。這樣，每個基本塊僅含的一個結點值。這樣，每個基本塊僅含0 0、1 1、2 2型四型四元式的元式的DAGDAG構造算法如下構造算法如下( (對基本塊的每一個四元式依對基本塊的每一個四元式依次執行該算法次執行該算法) )：編編 譯譯 原原 理理2022年3月17日 (1) (1) 若若Node(B)Node(B)無定義，則構造一標記為無定義，則構造一標記為B B的的葉結點并定義葉結點并定義Node(B)Node(B)為這個結點，然后根據下為這個結點，然后根據下列情況做不同處理：列情況做不同處理： 若當前四元式是若當前四元式是0 0型，則記型，則記Node(B)Node(B)的值為的值為n n

18、，轉，轉(4)(4)。 若當前四元式是若當前四元式是1 1型，則轉型，則轉(2)(2)。 若當前四元式是若當前四元式是2 2型，則：型，則： i. i. 如果如果Node(C)Node(C)無定義，則構造一標記為無定義，則構造一標記為C C的的葉結點，并定義葉結點，并定義Node(C)Node(C)為這個結點；為這個結點；ii. ii. 轉轉(2)(2)。編編 譯譯 原原 理理2022年3月17日 (2) (2) 若若Node(B)Node(B)是以常數標記的葉結點，是以常數標記的葉結點，則轉則轉(2)(2)，否則轉，否則轉(3)(3)。 若若Node(B)Node(B)和和Node(C)No

19、de(C)都是以常數標記的葉結點，則轉都是以常數標記的葉結點，則轉(2)(2)，否則轉否則轉(3)(3)。 執行執行op B(op B(即合并已知量即合并已知量) )，令得到的新常數為令得到的新常數為P P。若。若Node(B)Node(B)是處理當前四是處理當前四元式時新建立的結點，則刪除它；若元式時新建立的結點，則刪除它；若Node(P)Node(P)無無定義，則構造一用定義，則構造一用P P做標記的葉結點做標記的葉結點n n并置并置Node(P)= nNode(P)= n；轉；轉(4)(4)。 執行執行B op C(B op C(即合并即合并已知量已知量) )，令得到的新常數為，令得到的

20、新常數為P P。若。若Node(B)Node(B)或或Node(C)Node(C)是處理當前四元式時新建立的結點，則是處理當前四元式時新建立的結點，則刪除它；若刪除它；若Node(P)Node(P)無定義，則構造一用無定義，則構造一用P P做標做標記的葉結點記的葉結點n n并置并置Node(P)= nNode(P)= n；轉；轉(4)(4)。編編 譯譯 原原 理理2022年3月17日 (3) (3) 檢查檢查DAGDAG中是否有標記為中是否有標記為opop且以且以Node(B)Node(B)為惟一后繼的結點為惟一后繼的結點( (即查找公共子表達式即查找公共子表達式) )。若。若有，則把已有的結

21、點作為它的結點并設該結點有，則把已有的結點作為它的結點并設該結點為為n n；若沒有，則構造一個新結點；轉；若沒有，則構造一個新結點；轉(4)(4)。 檢查檢查DAGDAG中是否有標記為中是否有標記為opop且其左后繼且其左后繼為為Node(B)Node(B)、右后繼為、右后繼為Node(C)Node(C)的結點的結點( (即查找公即查找公共子表達式共子表達式) )。若有，則把已有的結點作為它的。若有，則把已有的結點作為它的結點并設該結點為結點并設該結點為n n；若沒有，則構造一個新結；若沒有，則構造一個新結點；轉點；轉(4)(4)。編編 譯譯 原原 理理2022年3月17日 (4) (4) 若

22、若Node(A)Node(A)無定義，則把無定義，則把A A附加在結點附加在結點n n上上并令并令Node(A)= nNode(A)= n；否則，先從；否則，先從Node(A)Node(A)的附加標的附加標識符集中將識符集中將A A刪去刪去( (注意，若注意，若Node(A)Node(A)是葉結點，是葉結點，則不能將則不能將A A刪去刪去) )，然后再把，然后再把A A附加到新結點附加到新結點n n上，上，并令并令Node(A)=nNode(A)=n。 解答解答 按照算法順序處理每一四元式后構按照算法順序處理每一四元式后構造出的造出的DAGDAG如圖如圖7 72 2所示，其中每一子圖所示，其中

23、每一子圖(1)(1)、(2)(2)、(10)(10)分別對應四元式分別對應四元式(1)(1)(10)(10)的的DAGDAG構造。構造。編編 譯譯 原原 理理2022年3月17日n6n1n2T0T1, T3n3n4n5n7n8B*A, T5T6T2, T4*3.146.28Rr( 10 ) BT5*T6(9) T6Rrn6n1n2T0T1, T3n3n4n5A, B, T5T2, T4*3.146.28Rr(8) T5T3*T4n6n1n2T0T1, T3n3n4n5n7A, B, T5T6T2, T4*3.146.28Rrn6n1n2T0T1, T3n3n4n5A, BT2, T4*3.14

24、6.28Rr(7) T4Rr(6) T32*T0n6n1n2T0T1n3n4n5A, BT2*3.146.28Rr(5) B An6n1n2T0T1, T3n3n4n5A, BT2*3.146.28Rrn6n1n2T0T1n3n4n5AT2*3.146.28Rr(4) T4T1*T2(3) T3Rrn1T0n1n2n3T1*3.143.142(2) T12*T0n1n2T0T1n3n4n5T23.146.28Rr6.28(1) T03.14圖52 DAG編編 譯譯 原原 理理2022年3月17日 構造過程說明如下：構造過程說明如下： (1) (1) 對應圖對應圖7 72(2)2(2)，四元式，

25、四元式T1=2T1=2* *T0T0首先執首先執行算法中的步驟行算法中的步驟(1)(1)，因，因Node(B)Node(B)無定義，所以無定義，所以構造一個標記為構造一個標記為2 2的葉結點并定義的葉結點并定義Node(2)Node(2)為這為這個結點；因當前四元式是個結點；因當前四元式是2 2型且型且Node(C)Node(C)已有定已有定義義( (此時為此時為Node(T0)Node(T0)，轉算法步驟，轉算法步驟(2)(2)；因；因Node(B)=Node(2)Node(B)=Node(2)和和Node(C)=Node(T0)Node(C)=Node(T0)都是標記都是標記為常數的葉結點

26、，則執行為常數的葉結點，則執行B op CB op C并令新結點為并令新結點為P(=6.28)P(=6.28)；由于；由于Node(P)Node(P)無定義，故構造無定義，故構造Node(P)=Node(6.28)Node(P)=Node(6.28)； 編編 譯譯 原原 理理2022年3月17日 此外，因此外，因Node(B)=Node(2)Node(B)=Node(2)是處理當前四元是處理當前四元式時新構造出來的結點，故刪除式時新構造出來的結點，故刪除n2n2；接下來執；接下來執行算法步驟行算法步驟(4)(4)，因，因Node(A)Node(A)無定義而將無定義而將T1T1附加附加在結點在結

27、點n3n3上，并令上，并令Node(T1)=6.28Node(T1)=6.28；最后；最后DAGDAG生生成了成了2 2個結點個結點n1n1和和n3n3，因結點，因結點n2n2被刪除而將被刪除而將n3n3改改名為名為n2n2。圖。圖5 52(2)2(2)的形成過程實際上也是合并的形成過程實際上也是合并已知量的優化過程。已知量的優化過程。 (2) (2) 圖圖5 52(4)2(4)中中T1T1、T2T2已有定義，則僅生成已有定義，則僅生成一個新結點一個新結點n6n6并將并將A A附加在附加在n6n6上。圖上。圖5-2(5)5-2(5)中結中結點點B B已有定義，故直接附加在已有定義，故直接附加在

28、n6n6上。上。編編 譯譯 原原 理理2022年3月17日 (3) (3) 圖圖5 52(6)2(6)的處理過程與圖的處理過程與圖5 52(2)2(2)略同，略同，但在生成但在生成P P時因其已在時因其已在DAGDAG中中( (即即 Node(6.28)Node(6.28)，故不生成新結點而直接將故不生成新結點而直接將T3T3附加在結點附加在結點6.286.28上。上。 (4) (4) 圖圖5 52(7)2(7)的生成過程實質上是刪除多余的生成過程實質上是刪除多余運算運算( (刪除公共子表達式刪除公共子表達式) )的優化。因為的優化。因為DAGDAG中已中已有葉結點有葉結點R R與葉結點與葉結

29、點r r，并且執行，并且執行opop操作后得到操作后得到的新結點的新結點T2T2也已經在也已經在DAGDAG中，故執行算法步驟中，故執行算法步驟(4)(4)時因時因T4T4無定義而將無定義而將T4T4附加在結點附加在結點n5n5上。上。編編 譯譯 原原 理理2022年3月17日 (5) (5) 圖圖5 52(9)2(9)中，變量中，變量R R和和r r已在已在DAGDAG中有相中有相應的結點，執行應的結點，執行“”操作后，產生的新結點操作后，產生的新結點P P無定義，故僅生成一個新結點無定義，故僅生成一個新結點n7n7并將并將T6T6標記于標記于其上。其上。 (6) (6) 圖圖5 52(10

30、)2(10)中，對當前四元式中，對當前四元式B=T5B=T5* *T6T6，DAGDAG中已有結點中已有結點T5T5和和T6T6；執行算法步驟；執行算法步驟(4)(4)時因時因結點結點B B已有定義且不是葉結點，故先將原已有定義且不是葉結點，故先將原B B從從DAGDAG中刪除，然后生成一個新結點中刪除，然后生成一個新結點n8n8，將，將B B附加其上附加其上并令并令Node(B)=n8Node(B)=n8。這一處理過程實質上是刪除。這一處理過程實質上是刪除了無用賦值了無用賦值B=AB=A。編編 譯譯 原原 理理2022年3月17日 7.2.2 7.2.2 利用利用DAGDAG進行基本塊的優化

31、處理進行基本塊的優化處理 利用利用DAGDAG進行基本塊優化處理的基本思想是：進行基本塊優化處理的基本思想是：按照構造按照構造DAGDAG結點的順序，對每一個結點寫出其結點的順序，對每一個結點寫出其相應的四元式表示。相應的四元式表示。 我們根據例我們根據例5.1DAG5.1DAG結點的構造順序，按照結點的構造順序，按照圖圖7 72(10)2(10)寫出四元式序列寫出四元式序列GG如下：如下：編編 譯譯 原原 理理2022年3月17日(1) (1) T0=3.14T0=3.14(2) (2) T1=6.28T1=6.28(3) (3) T3=6.28T3=6.28(4) (4) T2=R+rT2

32、=R+r(5) (5) T4=T2T4=T2(6) (6) A=6.28A=6.28* *T2T2(7) (7) T5=AT5=A(8) (8) T6= RT6= Rr r (9) (9) B=AB=A* *T6T6編編 譯譯 原原 理理2022年3月17日將將GG和原基本塊和原基本塊G G相比，我們看到：相比，我們看到：(1) (1) G G中四元式中四元式(2)(2)和和(6)(6)都是已知量和已知量的都是已知量和已知量的運算，運算，GG已合并；已合并；(2) (2) G G中四元式中四元式(5)(5)是一種無用賦值，是一種無用賦值，GG已將它刪已將它刪除；除；(3) (3) G G中四元

33、式中四元式(3)(3)和和(7)(7)的的R+rR+r是公共子表達是公共子表達式式, ,GG只對它們計算了一次，即刪除了多余的只對它們計算了一次，即刪除了多余的R+rR+r運算。運算。因此，因此，GG是對是對G G實現上述三種優化的結果。實現上述三種優化的結果。編編 譯譯 原原 理理2022年3月17日 通過觀察圖通過觀察圖7 72(10)2(10)中的所有葉結點和內部中的所有葉結點和內部結點以及其上的附加標識符，還可以得出以下結點以及其上的附加標識符，還可以得出以下結論：結論： (1) (1) 在基本塊外被定值并在基本塊內被引用在基本塊外被定值并在基本塊內被引用的所有標識符就是的所有標識符就

34、是DAGDAG中相應葉結點上標記的標中相應葉結點上標記的標識符；識符； (2) (2) 在基本塊內被定值且該值能在基本塊后在基本塊內被定值且該值能在基本塊后面被引用的標識符就是面被引用的標識符就是DAGDAG各結點上的附加標識各結點上的附加標識符。符。編編 譯譯 原原 理理2022年3月17日 這些結論可以引導優化工作的進一步深入，這些結論可以引導優化工作的進一步深入，尤其是無用賦值的優化，也即：尤其是無用賦值的優化，也即： (1) (1) 如果如果DAGDAG中某結點上的標識符在該基本中某結點上的標識符在該基本塊之后不會被引用，就可以不生成對該標識符塊之后不會被引用，就可以不生成對該標識符賦

35、值的四元式。賦值的四元式。 (2) (2) 如果某結點如果某結點nini上沒有任何附加標識符，上沒有任何附加標識符，或者或者nini上的附加標識符在該基本塊之后不會被上的附加標識符在該基本塊之后不會被引用，而且引用，而且nini也沒有前驅結點，這表明在基本也沒有前驅結點，這表明在基本塊內和基本塊之后都不會引用塊內和基本塊之后都不會引用nini的值，那么就的值，那么就不生成計算不生成計算nini結點值的四元式。結點值的四元式。編編 譯譯 原原 理理2022年3月17日 (3) (3) 如果有兩個相鄰的四元式如果有兩個相鄰的四元式A=C op DA=C op D和和B=AB=A，其中第一條代碼計算

36、出來的，其中第一條代碼計算出來的A A值僅在第二值僅在第二個四元式中被引用，則將個四元式中被引用，則將DAGDAG中相應結點重寫成中相應結點重寫成四元式時，原來的兩個四元式可以優化為四元式時，原來的兩個四元式可以優化為B=C B=C op Dop D。 假設例假設例7.17.1中中T0T0、T1T1、T2T2、T3T3、T4T4、T5T5和和T6T6在在基本塊后都不會被引用，則圖基本塊后都不會被引用，則圖7-2(10)7-2(10)中的中的DAGDAG就可重寫為如下的四元式序列：就可重寫為如下的四元式序列：編編 譯譯 原原 理理2022年3月17日(1) (1) S1=R+r /S1=R+r

37、/* *S1S1、S2S2為存放中間結果的臨時變量為存放中間結果的臨時變量* */ /(2) (2) A=6.28A=6.28* *S1S1(3) (3) S2=RS2=Rr r(4) (4) B=AB=A* *S2S2編編 譯譯 原原 理理2022年3月17日 以上把以上把DAGDAG重寫成四元式序列時，是按照原重寫成四元式序列時，是按照原來構造來構造DAGDAG結點的順序結點的順序( (即即n5n5、n6n6、n7n7、n8)n8)依次依次進行的。實際上，我們還可以采用其它順序進行的。實際上，我們還可以采用其它順序( (如如自下而上自下而上) )重寫，只要其中的任何一個內部結點重寫，只要其

38、中的任何一個內部結點是在其后繼結點之后被重寫并且轉移語句是在其后繼結點之后被重寫并且轉移語句( (如果如果有的話有的話) )仍然是基本塊的最后一個語句即可。仍然是基本塊的最后一個語句即可。編編 譯譯 原原 理理2022年3月17日7.27.2循環優化循環優化首結點首結點：從它開始到有向圖中任何結點都從它開始到有向圖中任何結點都有一條通路的結點。有一條通路的結點。 一個一個程序流圖程序流圖是具有唯一首結點的有向圖。是具有唯一首結點的有向圖。 程序流圖（控制流程圖或流圖程序流圖（控制流程圖或流圖 ）：三元組三元組G=(NG=(N，E E，n n0 0) )N N：結點（基本塊）集：結點（基本塊）集

39、E E：邊集：邊集n n0 0：首結點。：首結點。編編 譯譯 原原 理理2022年3月17日(1) read X(2) read Y(3) R=X % Y(4) if R=0 goto (8)(5) X=Y(6) Y=R(7) goto (3)(8) write Y(9) halt(1) read X(2) read Y (3) RX%Y (4) if R0 goto(8) (5) XY (6) YR (7) goto(3) (8) write Y (9) haltB1B2B3B4圖73 求最大公因子的程序流圖編編 譯譯 原原 理理2022年3月17日 我們知道，該程序的基本塊分別為：我們知道

40、，該程序的基本塊分別為：(1)(2)(1)(2)，(3)(4)(3)(4)，(5)(6)(7)(5)(6)(7)和和(8)(9)(8)(9)，按構造，按構造流圖結點間有向邊的方法，我們得到該程序的程流圖結點間有向邊的方法，我們得到該程序的程序流圖如圖序流圖如圖7 73 3所示。所示。 有了程序流圖，我們就可以對所要討論的有了程序流圖，我們就可以對所要討論的循環結構給出定義。在程序流圖中，我們稱具有循環結構給出定義。在程序流圖中，我們稱具有下列性質的結點序列為一個循環：下列性質的結點序列為一個循環：編編 譯譯 原原 理理2022年3月17日 (1) (1) 它們是強連通的，其中任意兩個結點之它們

41、是強連通的，其中任意兩個結點之間必有一條通路，而且該通路上各結點都屬于該間必有一條通路，而且該通路上各結點都屬于該結點序列；如果序列只包含一個結點，則必有一結點序列；如果序列只包含一個結點，則必有一條有向邊從該結點引到其自身。條有向邊從該結點引到其自身。 (2) (2) 它們中間有一個而且只有一個是入口結它們中間有一個而且只有一個是入口結點。點。 所謂入口結點，是指序列中具有下述性質的所謂入口結點，是指序列中具有下述性質的結點：從序列外某結點有一條有向邊引到它，或結點：從序列外某結點有一條有向邊引到它，或者它就是程序流圖的首結點。者它就是程序流圖的首結點。 編編 譯譯 原原 理理2022年3月

42、17日 例如，對圖例如，對圖7 73 3所示的程序流圖，由上所示的程序流圖，由上述循環的定義可知，結點序列述循環的定義可知，結點序列B2B2，B3B3是是程序中的一個循環，其中，程序中的一個循環，其中，B2B2是循環的惟是循環的惟一入口結點。一入口結點。 對圖對圖7 74 4所示的程序流圖，所示的程序流圖，編編 譯譯 原原 理理2022年3月17日1243576圖74 程序流圖 結點序列結點序列6因其只有一個結點因其只有一個結點且有一有向邊引到自身，并且且有一有向邊引到自身，并且只有惟一的入口結點只有惟一的入口結點6，故是，故是我們所定義的循環；而我們所定義的循環；而2, 3, 4, 5, 6

43、, 7中的任意兩個結點中的任意兩個結點之間都存在通路之間都存在通路(即為強連通即為強連通)，且有惟一的入口結點且有惟一的入口結點2，故也是，故也是我們所定義的循環；此外，我們所定義的循環；此外，4, 5, 6, 7也是強連通且有惟一也是強連通且有惟一入口結點入口結點4，雖然到入口結點，雖然到入口結點4的的有向邊不止一條，但仍然是我們有向邊不止一條，但仍然是我們所定義的循環。所定義的循環。而而2, 4和和2, 3, 4，它們雖然，它們雖然是強連通的，但卻存在兩個入是強連通的，但卻存在兩個入口結點口結點2、4，故不是我們所定，故不是我們所定義的循環；義的循環；4, 5, 7和和4, 6, 7也因其

44、存在兩個入口結點也因其存在兩個入口結點4、7而不是我們所定義的循環。而不是我們所定義的循環。編編 譯譯 原原 理理2022年3月17日 7.2.2 7.2.2 循環的查棧循環的查棧 1 1必經結點集必經結點集 為了找出程序流圖中的循環，需要分析流圖為了找出程序流圖中的循環，需要分析流圖中結點的控制關系，為此我們引入必經結點和必中結點的控制關系，為此我們引入必經結點和必經結點集的定義。經結點集的定義。 在程序流圖中，對任意結點在程序流圖中，對任意結點m m和和n n，如果從流，如果從流圖的首結點出發，到達圖的首結點出發，到達n n的任一通路都要經過的任一通路都要經過m m，則稱則稱m m是是n

45、n的必經結點，記為的必經結點，記為m DOM nm DOM n；流圖中結；流圖中結點點n n的所有必經結點的集合稱為結點的所有必經結點的集合稱為結點n n的必經結點的必經結點集，記為集，記為D(n)D(n)。編編 譯譯 原原 理理2022年3月17日 顯然，循環的入口結點是循環中所有結點的顯然，循環的入口結點是循環中所有結點的必經結點；此外，對任何結點必經結點；此外，對任何結點n n來說都有來說都有n DOM nn DOM n。 如果把如果把DOMDOM看作流圖結點集上定義的一個關看作流圖結點集上定義的一個關系，則由定義容易看出它具有下述性質：系，則由定義容易看出它具有下述性質： (1) (1

46、) 自反性：對流圖中任意結點自反性：對流圖中任意結點a a，都有，都有a a DOM aDOM a。 (2) (2) 傳遞性：對流圖中任意結點傳遞性：對流圖中任意結點a a、b b、c c，若存在若存在a DOM ba DOM b和和b DOM c,b DOM c,則必有則必有a DOM ca DOM c。 (3) (3) 反對稱性：若存在反對稱性：若存在a DOM ba DOM b和和b DOM ab DOM a，則必有則必有a=ba=b。編編 譯譯 原原 理理2022年3月17日 例例7.2 7.2 求圖求圖7 74 4中流圖各結點的中流圖各結點的D(n)D(n)。 解答解答 考察圖考察圖

47、7 74 4的流圖并由必經結點的定的流圖并由必經結點的定義容易看出：首結點義容易看出：首結點1 1是所有結點的必經結點；是所有結點的必經結點；結點結點2 2是除去結點是除去結點1 1之外所有結點的必經結點；結之外所有結點的必經結點；結點點4 4是結點是結點4 4、5 5、6 6、7 7的必經結點；而結點的必經結點；而結點3 3、5 5、6 6、7 7都只是其自身的必經結點。因此，直接由定都只是其自身的必經結點。因此，直接由定義和義和DOMDOM的性質可求得：的性質可求得：編編 譯譯 原原 理理2022年3月17日D(1)=1D(1)=1D(2)=1D(2)=1，22D(3)=1D(3)=1，2

48、 2，33D(4)=1D(4)=1，2 2，44D(5)=1D(5)=1，2 2，4 4，55D(6)=1D(6)=1，2 2，4 4，66D(7)=1D(7)=1，2 2，4 4，771243576編編 譯譯 原原 理理2022年3月17日 下面我們給出求流圖下面我們給出求流圖G=(NG=(N，E E，n0)n0)的所有結點的所有結點n n的必經結的必經結點集點集D(n)D(n)的算法；其中，的算法；其中，P(n)P(n)代表結點代表結點n n的前驅結點集，它可的前驅結點集，它可以從邊集以從邊集E E中直接求出。中直接求出。 D(n0)=n0;D(n0)=n0; for (nN for (n

49、Nn0) D(n)=N; /n0) D(n)=N; /* *置初值置初值* */ / change=true; change=true; while (change) while (change) change=false; change=false; for (nN for (nNn0)n0) m mi i P(n) new=n P(n) new=nD(mD(m1 1)D(m)D(m2 2) D(m) D(m3 3) ) if (new!=D(n) if (new!=D(n) change=true; change=true; D(n)=new; D(n)=new; 編編 譯譯 原原 理理2

50、022年3月17日nink1nk2nknnj圖75 ni為nj的必經結點示意 編編 譯譯 原原 理理2022年3月17日例例7.3 7.3 應用求流圖必經結點集的應用求流圖必經結點集的算法求圖算法求圖7 74 4流圖各結點流圖各結點n n的的D(n)D(n)。 解答解答 算法求解過程如下：算法求解過程如下： 首先置初值：首先置初值： D(1)=1D(1)=1 D(2)=D(3)=D(4)=D(5)=D(6)=D(7)D(2)=D(3)=D(4)=D(5)=D(6)=D(7) =1,2,3,4,5,6,7=1,2,3,4,5,6,7 置置changechange為為falsefalse，然后從結

51、點，然后從結點2 2到結點到結點7 7依次執行第二個依次執行第二個forfor循環。循環。1243576編編 譯譯 原原 理理2022年3月17日對結點對結點2 2，因，因 new=2D(1)D(4)new=2D(1)D(4)=211,2,3,4,5,6,7=211,2,3,4,5,6,7=21=1,2=21=1,2但迭代前但迭代前D(2)=1,2,3,4,5,6,7D(2)=1,2,3,4,5,6,7，故故D(2)newD(2)new，因此置，因此置change=truechange=true并令并令D(2)=1,2D(2)=1,2。對結點對結點3 3，因，因 new=3D(2)=31,2=

52、1,2,new=3D(2)=31,2=1,2,33但迭代前但迭代前D(3)=1,2,3,4,5,6,7D(3)=1,2,3,4,5,6,7，故故D(3) newD(3) new，因此令，因此令D(3)=1D(3)=1，2 2，33。其余各結點按照上述步驟可求出：其余各結點按照上述步驟可求出：D(4)=4D(2)D(3)D(7)=4D(4)=4D(2)D(3)D(7)=41,21,2,31,2,3,4,5,6,1,21,2,31,2,3,4,5,6,7=1,2,47=1,2,41243576編編 譯譯 原原 理理2022年3月17日D(5)=5D(4)=1,2,4,5D(5)=5D(4)=1,2

53、,4,5D(6)=6D(4)=1,2,4,6D(6)=6D(4)=1,2,4,6D(7)=7D(5)D(6)=7D(7)=7D(5)D(6)=71,2,4,51,2,4,6=1,1,2,4,51,2,4,6=1,2,4,72,4,7一次迭代完畢后，因一次迭代完畢后，因changechange為為truetrue，故還要進行下一次，故還要進行下一次迭代。迭代。先令先令changechange為為falsefalse，然后繼，然后繼續從結點續從結點2 2到結點到結點7 7依次執行依次執行第二個第二個forfor循環。循環。對結點對結點2 2，因，因 new=2D(1)D(4) new=2D(1)D

54、(4) =211,2,4=211,2,4=21=1,2=21=1,21243576編編 譯譯 原原 理理2022年3月17日 而迭代前而迭代前D(2)=1,2D(2)=1,2，所，所以以D(2)=newD(2)=new，故，故D(2)D(2)不變。不變。 對結點對結點3 3，因，因 new=3D(2) new=3D(2) =31,2=1,2,3=31,2=1,2,3 及迭代前及迭代前D(3)=1,2,3D(3)=1,2,3，所以所以D(3)=newD(3)=new，故，故D(3)D(3)不變。不變。對其余結點對其余結點n(n=4n(n=47)7)求出的求出的newnew均有均有D(n)=new

55、D(n)=new，所以第二，所以第二次迭代后次迭代后changechange為為falsefalse，迭，迭代結束，第一次迭代求出的代結束，第一次迭代求出的各個各個D(n)D(n)就是最后的結果。就是最后的結果。1243576編編 譯譯 原原 理理2022年3月17日 2 2回邊回邊 查找循環的方法是：首先應用必經結點集來查找循環的方法是：首先應用必經結點集來求出流圖中的回邊，然后利用回邊找出流圖中的求出流圖中的回邊，然后利用回邊找出流圖中的循環的。循環的。 回邊的定義如下：假設回邊的定義如下：假設abab是流圖中一條有是流圖中一條有向邊，如果向邊，如果b DOM ab DOM a，則稱，則稱

56、abab是流圖中的一條是流圖中的一條回邊。回邊。 對于一已知流圖對于一已知流圖G G，只要求出各結點，只要求出各結點n n的必經的必經結點集，就可以立即求出流圖中的所有回邊。在結點集，就可以立即求出流圖中的所有回邊。在求出流圖求出流圖G G中的所有回邊后，就可以求出流圖中中的所有回邊后，就可以求出流圖中的循環。如果已知有向邊的循環。如果已知有向邊ndnd是一條回邊，則由是一條回邊，則由它組成的循環就是由結點它組成的循環就是由結點d d、結點、結點n n以及有通路到以及有通路到達達n n 但該通路不經過但該通路不經過d d的所有結點組成的。的所有結點組成的。編編 譯譯 原原 理理2022年3月1

57、7日例例7.4 7.4 求出圖求出圖7 74 4流圖的所有流圖的所有回邊。回邊。 解答解答 (1) (1) 已知已知D(6)=1,2,4,6D(6)=1,2,4,6，因存在因存在6666且且6 DOM 66 DOM 6，故，故6666是回邊；是回邊； (2) (2) 已知已知D(7)=1,2,4,7D(7)=1,2,4,7，因存在因存在7474且且4 DOM 74 DOM 7，故，故7474是回邊；是回邊； (3) (3) 已知已知D(4)=1,2,4D(4)=1,2,4，因，因存在存在4242且且2 DOM 42 DOM 4，故，故4242是是回邊。容易看出，其它有向邊回邊。容易看出，其它有

58、向邊都不是回邊。都不是回邊。1243576編編 譯譯 原原 理理2022年3月17日尋找由回邊組成循環的算法如下：尋找由回邊組成循環的算法如下：main (main () ) stack= stack=空空;/;/* *stackstack是一個工作棧是一個工作棧* */ / loop=d;/ loop=d;/* *looploop是所求的循環是所求的循環* */ / insert(m); insert(m); while (stack while (stack非空非空) ) 彈出彈出stackstack棧頂元素棧頂元素m;m; for (pP(m) / for (pP(m) /* *P(m)

59、P(m)為結點為結點m m的前驅結點集的前驅結點集* */ / insert (p); insert (p); void insert (m)void insert (m) if (m if (mloop) loop) loop=loopm; loop=loopm; 把把m m壓入棧壓入棧stack;stack; 1243576編編 譯譯 原原 理理2022年3月17日 此算法在求回邊此算法在求回邊ndnd組組成循環的所有結點的方法是：成循環的所有結點的方法是：由于循環以由于循環以d d為其惟一入口，為其惟一入口，n n是循環的一個出口，只要是循環的一個出口，只要n n不同時是循環入口不同時是

60、循環入口d d，那么，那么n n的所有前驅就應屬于循環。的所有前驅就應屬于循環。在求出在求出n n的所有前驅之后，的所有前驅之后，只要它們不是循環入口只要它們不是循環入口d d，就應再繼續求出它們的前驅，就應再繼續求出它們的前驅，而這些新求出的所有前驅也而這些新求出的所有前驅也應屬于循環。然后再對新求應屬于循環。然后再對新求出的所有前驅重復上述過程，出的所有前驅重復上述過程，直到所求出的前驅都是直到所求出的前驅都是d d為為止。止。1243576編編 譯譯 原原 理理2022年3月17日 3 3可歸約流圖可歸約流圖 一個流圖被稱為可歸一個流圖被稱為可歸約的，當且僅當流圖中約的，當且僅當流圖中除