第11章-代碼優(yōu)化課件

第11章代碼優(yōu)化11.1代碼優(yōu)化技術(shù)

11.2局部優(yōu)化11.3控制流程分析和循環(huán)第11章代碼優(yōu)化11.1代碼優(yōu)化技術(shù)【學(xué)習(xí)目標】

通過本章學(xué)習(xí)：

理解所謂代碼優(yōu)化是指什么？

知道最常用的代碼優(yōu)化技術(shù)有哪些？

知道實現(xiàn)代碼優(yōu)化要進行哪些工作？【學(xué)習(xí)指南】

所謂代碼優(yōu)化是指對程序代碼進行等價變換。程序代碼可以是中間代碼(如四元式代碼)，也可以是目標代碼。優(yōu)化的含義是最終生成的目標代碼短(而運行速度快)，時空效率優(yōu)化。最常用的代碼優(yōu)化技術(shù)有刪除多余運算，循環(huán)不變代碼外提，強度削弱，變換循環(huán)控制條件，合并已知量與復(fù)寫傳播，以及刪除無用賦值等等。

【難重點】

從概念上理解什么是代碼優(yōu)化，編譯過程中可進行哪些優(yōu)化，以及進行優(yōu)化所需要的基礎(chǔ)都沒有難點，但在實現(xiàn)上是有相當復(fù)雜的工作?！緦W(xué)習(xí)目標】11.0概述源語言程序經(jīng)過詞法分析、語法分析、語義分析和中間代碼生成等編譯前期工作（編譯前端），得到了與源程序等價的中間代碼程序。中間代碼程序的質(zhì)量將直接影響目標程序執(zhí)行的效率。程序執(zhí)行的效率體現(xiàn)在兩個方面：目標程序運行時刻所占用的存儲空間和目標程序運行時刻所耗費的時間。所謂優(yōu)化，是為了提高程序的執(zhí)行效率而對程序代碼進行的等價變換。使得變換后的代碼運行結(jié)果與變換前代碼運行結(jié)果相同，而運行速度加大或占用存儲空間少，或兩者都有。編譯過程中可進行的優(yōu)化可按階段劃分：優(yōu)化可在編譯的不同階段進行，分為中間代碼一級和目標代碼一級的優(yōu)化。可按優(yōu)化涉及的程序范圍劃分：對同一階段，分為局部優(yōu)化,循環(huán)優(yōu)化和全局優(yōu)化?？砂磧?yōu)化是否涉及具體計算機來劃分：分為與計算機有關(guān)的優(yōu)化和與計算機無關(guān)的優(yōu)化。11.0概述源語言程序經(jīng)過詞法分析、語法分析、語義分析和優(yōu)化可在編譯的不同階段進行，對同一階段，涉及的程序范圍也有所不同，在同一范圍內(nèi)，可進行多種優(yōu)化。目前編譯程序的優(yōu)化工作一般是在中間代碼生成之后和（或）目標代碼生成之后進行。如圖11.1所示。編譯前端代碼生成中間代碼優(yōu)化目標代碼目標代碼優(yōu)化中間代碼源程序目標程序優(yōu)化可在編譯的不同階段進行，對同一階段，涉及的程序范圍也有所中間代碼的優(yōu)化是對中間代碼進行等價變換。目標代碼的優(yōu)化是在目標代碼生成之后進行的，因為生成的目標代碼對應(yīng)于具體的計算機，因此，這一類優(yōu)化在很大程度上依賴于具體的機器，我們不做詳細討論。另外依據(jù)優(yōu)化所涉及的程序范圍，又可分為局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三個不同的級別。局部優(yōu)化指的是在只有一個入口、一個出口的基本程序塊上進行的優(yōu)化。循環(huán)優(yōu)化是對循環(huán)中的代碼進行的優(yōu)化。全局優(yōu)化是在整個程序范圍內(nèi)進行的優(yōu)化。中間代碼的優(yōu)化是對中間代碼進行等價變換。目標代碼的優(yōu)化是在目

編譯程序的優(yōu)化工作旨在生成較好性能的目標代碼，為此，編譯程序需要對代碼（中間代碼或目標代碼）進行各種方式的變換。變換的宗旨是：等價－經(jīng)優(yōu)化工作變換后的代碼運行結(jié)果應(yīng)與原來程序運行結(jié)果一樣。有效－經(jīng)優(yōu)化工作變換后的代碼應(yīng)運行時間較短，占用的存儲空間較小。合算－獲得較好性能的目標代碼是優(yōu)化工作的意圖，而優(yōu)化本身包括大量的代碼分析和變換工作，這里有個權(quán)衡：應(yīng)盡可能以較低的代價取得較好的優(yōu)化效果。編譯程序的優(yōu)化工作旨在生成較好性能的目標代11.1代碼優(yōu)化技術(shù)

常用的優(yōu)化技術(shù)有：刪除多余運算；循環(huán)不變代碼外提；強度削弱；變換循環(huán)控制條件；合并已知量與復(fù)寫傳播；刪除無用賦值。為了說明這些常用的優(yōu)化技術(shù)，我們來看下面這個例子。例11.1

源程序是：

P∶=0for（I=1；I<=20；I=++）

P∶=P+A[I]*B[I]；經(jīng)過編譯得到的中間代碼如圖11.2所示，這個程序段由B1和B2兩個部分組成，B2是一個循環(huán)，假定每個元素按4字節(jié)編址。那么，對于這個中間代碼段，如何進行上述優(yōu)化。11.1代碼優(yōu)化技術(shù)常用的優(yōu)化技術(shù)有：例11.1源圖11.2中間代碼段(1)P:＝0(2)I:＝1(3)T1:＝4*I(4)T2:＝addr(A)-4(5)T3:＝T2[T1](6)T4:＝4*I(7)T5:＝addr(B)-4(8)T6:＝T5[T4](9)T7:＝T3*T6(10)P:＝P+T7(11)I:＝I+1(12)ifI≤20goto(3)B1B2數(shù)組元素地址計算的常量部分T2數(shù)組元素地址計算的增量部分T1P∶=0for（I=1；I<=20；I=++）

P∶=P+A[I]*B[I]；圖11.2中間代碼段(1)P:＝0(3)T1:＝4*IB11）刪除多余運算（刪除公共子表達式）優(yōu)化的目的在于使生成的目標代碼較少而執(zhí)行速度較快。四元式（6）變換成：T4∶=T1。這種優(yōu)化稱為刪除多余運算或稱為刪除公共子表達式。圖11.2中間代碼段(1)P:＝0(2)I:＝1(3)T1:＝4*I(4)T2:＝addr(A)-4(5)T3:＝T2[T1](6)T4:＝4*I(7)T5:＝addr(B)-4(8)T6:＝T5[T4](9)T7:＝T3*T6(10)P:＝P+T7(11)I:＝I+1(12)ifI≤20goto(3)B1B21）刪除多余運算（刪除公共子表達式）優(yōu)化的目的在于使生成的2）代碼外提減少循環(huán)中代碼總數(shù)的一個重要辦法是循環(huán)不變代碼外提。這種變換把循環(huán)不變運算，即其結(jié)果獨立于循環(huán)執(zhí)行次數(shù)的表達式，提到循環(huán)的前面,使之只在循環(huán)外計算一次。上例中，我們可以把四元式（4）和四元式（7）提到循環(huán)外。經(jīng)過刪除多余運算和代碼外提后，代碼變換成圖11.3。圖11.3刪除公共子表達式和代碼外提(1)P:＝0(2)I:＝1(4)T2:＝addr(A)-4(7)T5:＝addr(B)-4(3)T1:＝4*I(5)T3:＝T2[T1](6)T4:＝T1(8)T6:＝T5[T4](9)T7:＝T3*T6(10)P:＝P+T7(11)I:＝I+1(12)ifI≤20goto(3)B1B22）代碼外提減少循環(huán)中代碼總數(shù)的一個重要辦法是循環(huán)不變代碼3）強度削弱強度削弱的思想是把強度大的運算換算成強度小的運算。循環(huán)中計算T1值的乘法運算變換成在循環(huán)前進行一次乘法運算，而在循環(huán)中將其變換成加法運算。變換后如圖11.4所示。圖11.4強度削弱(1)P:＝0(2)I:＝1(4)T2:＝addr(A)-4(7)T5:＝addr(B)-4(3)T1:＝4*I(5)T3:＝T2[T1](6)T4:＝T1(8)T6:＝T5[T4](9)T7:＝T3*T6(10)P:＝P+T7(11)I:＝I+1(3)T1:＝T1+4(12)ifI≤20goto(5)B1B23）強度削弱強度削弱的思想是把強度大的運算換算成強度小的運4）變換循環(huán)控制條件圖11.4的代碼中，四元式（12）的循環(huán)控制條件I≤20變換成T1≤80，這樣整個程序的運行結(jié)果不變。這種變換稱為變換循環(huán)控制條件。經(jīng)過這一變換后，循環(huán)中I的值在循環(huán)后不會被引用，四元式（11）成為多余運算，可以從循環(huán)中刪除。變換循環(huán)控制條件可以達到代碼優(yōu)化的目的。(1)P:＝0(2)I:＝1(4)T2:＝addr(A)-4(7)T5:＝addr(B)-4(3)T1:＝4*I(5)T3:＝T2[T1](6)T4:＝T1(8)T6:＝T5[T4](9)T7:＝T3*T6(10)P:＝P+T7(11)I:＝I+1(3)T1:＝T1+4(12)ifT1≤80goto(5)B1B2圖11.5變換循環(huán)控制條件，合并已知量，復(fù)寫傳播4）變換循環(huán)控制條件圖11.4的代碼中，四元式（12）的循圖11.4中，四元式（3）可變?yōu)門1＝4，這種變換稱為合并已知量。圖11.4中，四元式(6)把T1的值復(fù)寫到T4中，四元式（8）要引用T4的值，而從四元式（6）到四元式（8）之間未改變T4和T1的值，則將四元式（8）改為T6∶=T5[T1]，這種變換稱為復(fù)寫傳播.復(fù)寫傳播之后運算結(jié)果保持不變。圖11.4經(jīng)過變換循環(huán)控制條件，合并已知量和復(fù)寫傳播等變換后，變?yōu)閳D11.5。圖11.5變換循環(huán)控制條件，合并已知量，復(fù)寫傳播(1)P:＝0(2)I:＝1(4)T2:＝addr(A)-4(7)T5:＝addr(B)-4(3)T1:＝4(5)T3:＝T2[T1](6)T4:＝T1(8)T6:＝T5[T1](9)T7:＝T3*T6(10)P:＝P+T7(11)I:＝I+1(3)T1:＝T1+4(12)ifT1≤80goto(5)B1B2圖11.4中，四元式（3）可變?yōu)門1＝4，這種變換稱為合并已6）刪除無用賦值在圖11.5中，（6）對T4賦值，但T4未被引用；另外，（2）和（11）對I賦值，但只有（11）引用I。所以，只要程序中其它地方不需要引用T4和I，則（6），（2）和（11）對程序的運行結(jié)果無任何作用。我們稱之為無用賦值，無用賦值可以從程序中刪除，如圖11.6所示。比較圖11.2和圖11.6可看出，經(jīng)過優(yōu)化后的代碼的執(zhí)行效率提高了很多。當然，實現(xiàn)這些優(yōu)化的一系列工作是非常復(fù)雜的，代價也是很大的。圖11.6刪除無用賦值(1)P:＝0(2)I:＝1(4)T2:＝addr(A)-4(7)T5:＝addr(B)-4(3)T1:＝4(5)T3:＝T2[T1](6)T4:＝T1(8)T6:＝T5[T1](9)T7:＝T3*T6(10)P:＝P+T7(11)I:＝I+1(3)T1:＝T1+4(12)ifT1≤80goto(5)B1B26）刪除無用賦值在圖11.5中，（6）對T4賦值，但T4未被11.2局部優(yōu)化我們所說的局部優(yōu)化是指基本塊內(nèi)的優(yōu)化。所謂基本塊，是指程序中一個單入口、單出口的線性程序塊（順序執(zhí)行的語句序列）?？刂屏髦荒軓钠淙肟谡Z句進入，從其出口語句退出,沒有中途停止或分支。局部優(yōu)化工作包括對于一個給定的程序，把它劃分為一系列的基本塊,在各個基本塊范圍內(nèi)分別進行優(yōu)化。局限于基本塊范圍內(nèi)的優(yōu)化稱為基本塊內(nèi)的優(yōu)化，也稱為局部優(yōu)化。11.2局部優(yōu)化我們所說的局部優(yōu)化是指基本塊內(nèi)的優(yōu)化。所謂11.2.1基本塊的劃分

我們先定義基本塊的入口語句。所謂入口語句有三種，就是：①程序的第一個語句；②條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標語句；③緊跟在條件轉(zhuǎn)移語句后面的語句。

有了入口語句的概念之后，我們就可以給出劃分中間代碼（四元式程序）為基本塊的算法。11.2.1基本塊的劃分我們先定義基本塊劃分中間代碼（四元式程序）為基本塊的算法：①求出四元式程序中各個基本塊的入口語句。②對每一入口語句，構(gòu)造其所屬的基本塊。它是由該入口語句到下一入口語句（不包括下一入口語句），或到一轉(zhuǎn)移語句（包括該轉(zhuǎn)移語句），或到一停語句（包括該停語句）之間的語句序列組成的。③凡未被納入某一基本塊的語句、都是程序中控制流程無法到達的語句，因而也是不會被執(zhí)行到的語句，可以把它們刪除。劃分中間代碼（四元式程序）為基本塊的算法：①求出四元式程我們以下述四元式程序為例來說明如何劃分基本塊的。例11.1:有四元式程序如下，構(gòu)造其基本塊。(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB>=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt我們以下述四元式程序為例來說明如何劃分基本塊的。

先求出四元式程序中各個基本塊的入口語句：語句（1）是程序的第一個語句，因此它是入口語句。語句（4）和語句（8）是條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標語句，因此是入口語句。語句（6）是緊跟在條件轉(zhuǎn)移語句后面的語句，因此是入口語句。(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB>=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt基本塊：語句（1），（2）和（3）構(gòu)成第一個基本塊；語句（4）和（5）構(gòu)成第二個基本塊；語句（6）和（7）構(gòu)成第三個基本塊；語句（8）和（9）構(gòu)成第四個基本塊。先求出四元式程序中各個基本塊的入口語句：(1)re11.2.2基本塊內(nèi)的優(yōu)化變換很多優(yōu)化變換可作用于基本塊而不改變它計算的表達式集合，這樣的變換對改進代碼的質(zhì)量是很有用的。有兩類重要的局部等價變換可用于基本塊；它們是保結(jié)構(gòu)的變換和代數(shù)變換?；緣K的主要保結(jié)構(gòu)變換是：刪除公共子表達式刪除無用代碼重新命名臨時變量交換語句次序11.2.2基本塊內(nèi)的優(yōu)化變換很多優(yōu)化變換可作用于基本塊對于刪除公共子表達式和刪除無用代碼這兩種優(yōu)化技術(shù)，我們在11.1中已經(jīng)討論過，這里簡單介紹重新命名臨時變量和交換語句次序是什么含義。重新命名臨時變量：假如有語句t∶=b+c，其中t是臨時變量。如果把這個語句改為u∶=b+c，其中u是新的臨時變量，并且把這個t的所有引用改成u，那么基本塊的運算結(jié)果不變。交換語句次序：如果基本塊有兩個相鄰的語句：

t1∶=b+ct2∶=x+y當且僅當x和y都不是t1，b和c都不是t2時，我們可以交換這兩個語句的次序。對于刪除公共子表達式和刪除無用代碼這兩種優(yōu)化技術(shù)，我們在11代數(shù)變換可以把基本塊計算的表達式集合變換成代數(shù)等價的集合。其中常用的變換是那些可以簡化表達式或用較快運算代替較慢運算的變換。例如：x∶=x+0或x∶=x*1這樣的語句可以從基本塊中刪除而不改變它計算的表達式集合，又如x∶=y**2的指數(shù)算符通常要用函數(shù)調(diào)用來實現(xiàn)，使用代數(shù)變換，這個語句可由快速、等價的語句x∶=y*y來代替。代數(shù)變換可以把基本塊計算的表達式集合變換成代數(shù)等價的集合。我們從下面例子理解這些變換。有四元式程序：t1:=4–2t2:=t1/2t3:=a*t2t4:=t3*t1t5:=b+t4c:=t5*t5進行合并已知量變換后得到：t1:=2t2:=t1/2t3:=a*t2t4:=t3*t1t5:=b+t4c:=t5*t5

再進行復(fù)寫傳播和刪除無用賦值等變換后得到：t2:=2/2t3:=a*t2t4:=t3*2t5:=b+t4c:=t5*t5再進行合并已知量變換后得到：t2:=1t3:=a*t2t4:=t3*2t5:=b+t4c:=t5*t5

我們從下面例子理解這些變換。有四元式程序：進行合并已知量變換再進行合并已知量變換后得到：t2:=1t3:=a*t2t4:=t3*2t5:=b+t4c:=t5*t5再進行復(fù)寫傳播和刪除無用賦值等變換后得到：t3:=a*1t4:=t3*2t5:=b+t4c:=t5*t5接著使用代數(shù)變換后有：t3:=at4:=t3*2t5:=b+t4c:=t5*t5

使用復(fù)寫傳播和刪除無用賦值變換后又有：t4:=a*2t5:=b+t4c:=t5*t5

再進行合并已知量變換后得到：再進行復(fù)寫傳播和刪除無用賦值等變再使用代數(shù)變換：t4:=a+at5:=b+t4c:=t5*t5重新命名臨時變量：t1:=a+at5:=b+t1c:=t5*t5還可減少臨時變量：t1:=a+at1:=b+t1c:=t1*t1

使用復(fù)寫傳播和刪除無用賦值變換后又有：t4:=a*2t5:=b+t4c:=t5*t5

再使用代數(shù)變換：重新命名臨時變量：還可減少臨時變量：11.2.3基本塊的DAG表示現(xiàn)在我們介紹如何應(yīng)用有向圖來進行基本塊的優(yōu)化工作。先將所要使用的DAG作一說明。在一個有向圖中，我們稱任一有向邊ni→nj(或表示為有序?qū)Γ╪i，nj）)中的結(jié)點ni為結(jié)點nj的前驅(qū)（父結(jié)），結(jié)點nj為結(jié)點ni的后繼（子結(jié)）。又稱任一有向邊序列n1→n2，n2→n3，…，nk-1→nk為從結(jié)點n1到結(jié)點nk的一條通路。如果其中n1＝nk，則稱該通路為環(huán)路。該結(jié)點序列也記為（n1，n2，…，nk）。圖11.7有向圖n1n2n4n3

例如，圖11.7中有向圖的通路（n2，n2）和（n3，n4，n3）就是環(huán)路。如果有向圖中任一通路都不是環(huán)路，則稱該有向圖為無環(huán)路有向圖，簡稱DAG。11.2.3基本塊的DAG表示現(xiàn)在我們介紹如何應(yīng)用有向圖來圖11.8的有向圖就是一個DAG。在DAG中，如果（n1，n2，…，nk）是其中一條通路，則稱結(jié)點n1為結(jié)點nk的祖先，結(jié)點nk為結(jié)點n1的后代。圖11.8中結(jié)點n6就是結(jié)點n9的祖先，n9是n6的后代。圖11.8DAGn1n2n5n3n4n6n8n9n7圖11.8的有向圖就是一個DAG。在DAG中，如果（n1，n我們要用到的有向圖，是一種其結(jié)點帶有下述標記或附加信息的DAG：圖的葉結(jié)點，即無后繼的結(jié)點，以一標識符（變量名）或常數(shù)作為標記，表示這個結(jié)點代表該變量或常數(shù)的值。如果葉結(jié)點用來代表某變量A的地址，則用addr（A）作為這個結(jié)點的標記。通常把葉結(jié)點上作為標記的標識符加上下標0，以表示它是該變量的初值。圖的內(nèi)部結(jié)點，即有后繼的結(jié)點,以一運算符作為標記，表示這個結(jié)點代表應(yīng)用該運算符對其后繼結(jié)點所代表的值進行運算的結(jié)果。圖中各個結(jié)點上可能附加一個或多個標識符，表示這些變量具有該結(jié)點所代表的值。

上述這種DAG可用來描述計算過程，又稱為描述計算過程的DAG。在以下的討論中，我們簡稱為DAG。我們要用到的有向圖，是一種其結(jié)點帶有下述標記或附加信息的DA基本塊的DAG表示與構(gòu)造:一個基本塊，可用一個DAG來表示。下面列出各種四元式及相對應(yīng)的DAG的結(jié)點形式。圖中ni為結(jié)點編號，結(jié)點下面的符號（運算符、標識符或常數(shù)）是各結(jié)點的標記，各結(jié)點右邊的標識符是結(jié)點的附加標識符。四元式DAG（0）A:=B（:=，B，-，A）（1）A:=opB（op，B，-，A）（2）A:=BopC（op，B，C，A）

基本塊的DAG表示與構(gòu)造:一個基本塊，可用一個DAG來表示（3）A：=B[C]（=[]，B[C]，-，A）（4）ifBropCgoto（s）（jrop，B，C，(s)）n1ropBn3(s)n2C（5）D[C]：=B（[]=，B，-，D[C]）n1[]=Bn4(s)n2Cn2D（6）goto（s）（j，-，-，（s））n1(s)（3）A：=B[C]（=[]，B[C]第11章-代碼優(yōu)化ppt課件第11章-代碼優(yōu)化ppt課件第11章-代碼優(yōu)化ppt課件第11章-代碼優(yōu)化ppt課件(1)

T0:=3.14(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(1)T0:=3.14(2)T1:=2*T0(3)T2T03.14(a)n1(1)T0∶=3.14(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

T03.14(a)n1(1)T0∶=3.14T03.14(b)n1T16.28n2(1)T0∶=3.14(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

T03.14(b)n1T16.28n2(1)T0∶=3.T03.14(c)n1T16.28n2Rn3rn4T2n5+(1)T0∶=3.14(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

T03.14(c)n1T16.28n2Rn3rn4T2n5T03.14n1T16.28n2Rn3rn4T2n5+An6*(d)(1)T0∶=3.14(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

T03.14n1T16.28n2Rn3rn4T2n5+An6(e)T03.14n1T16.28n2Rn3rn4T2n5+A，Bn6*(1)T0∶=3.14(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

(e)T03.14n1T16.28n2Rn3rn4T2n5(1)T0∶=3.14(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

(f)T03.14n1T1,T36.28n2Rn3rn4T2n5+A，Bn6*(1)T0∶=3.14(f)T03.14n1T1,T36(1)T0∶=3.14(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

(g)T03.14n1T1,T36.28n2Rn3rn4T2,T4n5+A,Bn6*(1)T0∶=3.14(g)T03.14n1T1,T36(1)T0∶=3.14(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

(h)T03.14n1T1,T36.28n2Rn3rn4T2,T4n5+A,B,T5n6*(1)T0∶=3.14(h)T03.14n1T1,T36(1)T0∶=3.14(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

(i)T03.14n1T1,T36.28n2Rn3rn4T2,T4n5+A,B,T5n6*T6n7-(1)T0∶=3.14(i)T03.14n1T1,T36圖11.10由四元式構(gòu)造的DAG(j)T03.14n1T1,T36.28n2Rn3rn4T2,T4n5+A,B,T5n6*T6n7-Bn8*＼(1)T0∶=3.14(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

圖11.10由四元式構(gòu)造的DAG(j)T03.14n1T11.2.4DAG的應(yīng)用將四元式表示成相應(yīng)的DAG后，可以利用DAG來進行優(yōu)化。首先由DAG構(gòu)造優(yōu)化的四元式序列?；仡櫼幌翫AG構(gòu)造算法中幾個步驟的作用。對于步驟2，如果參與運算的對象都是編譯時的已知量，則它并不生成計算該結(jié)點值的內(nèi)部結(jié)點，而是執(zhí)行該運算，將計算結(jié)果生成一個葉結(jié)點。顯然，步驟2起到了合并已知量的作用。步驟3的作用是檢查公共子表達式，對具有公共子表達式的所有四元式，它只產(chǎn)生一個計算該表達式值的內(nèi)部結(jié)點，而把那些被賦值的變量標識符附加到該結(jié)點上。這樣可刪除多余運算。步驟4具有刪除無用賦值的作用。如果某變量被賦值后，在它被引用前又被重新賦值，則步驟4把該變量從具有前一個值的結(jié)點上刪除。這樣，在一個基本塊被構(gòu)造成相應(yīng)的DAG的過程中已經(jīng)進行了一些基本的優(yōu)化工作。而后，我們可由DAG重新生成原基本塊的一個優(yōu)化的代碼序列。11.2.4DAG的應(yīng)用將四元式表示成相應(yīng)的DAG后，可例11.5我們將圖11.10（j）的基本塊G的DAG按原來構(gòu)造其結(jié)點的順序，重新寫成四元式。得到以下的四元式序列G'：(1)T0∶=3.14(2)T1∶=6.28(3)T3∶=6.28(4)T2∶=R+r(5)T4∶=T2(6)A∶=6.28*T2(7)T5∶=A(8)T6∶=R–r

(9)B∶=A*T6

(1)T0∶=3.14(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

把G'和原基本塊G相比，可以看出：1．G中的代碼（2）和（6）的已知量都已合并。2．G中（5）的無用賦值已被刪除。3．G中（3）和（7）的公共子表達式R+r只被計算一次，刪除了多余運算。所以G'是G的優(yōu)化結(jié)果。例11.5我們將圖11.10（j）的基本塊G的DAG按原來再來看看DAG提供的優(yōu)化信息:除了可應(yīng)用DAG進行上述的優(yōu)化外，我們還可從基本塊的DAG中得到一些其它優(yōu)化信息。這些信息是：①在基本塊外被定值并在基本塊內(nèi)被引用的所有標識符，就是作為葉子結(jié)點上標記的那些標識符。②在基本塊內(nèi)被定值且該值能在基本塊后被引用的所有標識符，就是DAG各結(jié)點上的那些附加標識符。前面我們所刪除的無用賦值只是其中一種情況，在這里，我們利用這些信息，根據(jù)有關(guān)變量在基本塊后被引用的情況，可以進一步刪除基本塊中的其它情況的無用賦值。再來看看DAG提供的優(yōu)化信息:除了可應(yīng)用DAG進行上述的優(yōu)例11.6上例中，假設(shè)T0，T1，…，T6在基本塊的后面都沒有被引用，則可將G′重寫為如下代碼序列：(1)T0∶=3.14(2)T1∶=6.28(3)T3∶=6.28(4)T2∶=R+r(5)T4∶=T2(6)A∶=6.28*T2(7)T5∶=A(8)T6∶=R–r

(9)B∶=A*T6

(1)S1∶=R+r(2)A∶=6.28*S1(3)S2∶=R-r(4)B∶=A*S2其中S1和S2用于存放中間臨時變量。整個序列中，沒有生成對T0，T1，…T6賦值的代碼。例11.6上例中，假設(shè)T0，T1，…，T6在基本塊的后面都11.3控制流分析和循環(huán)優(yōu)化控制流程圖（流圖）：具有唯一首結(jié)點的有向圖。我們可以把一個控制流程圖表示成一個三元組G。記為：N：結(jié)點集基本塊集E：有向邊集n0：首結(jié)點包含程序第一個語句的基本塊G＝(N，E，n0)

所謂首結(jié)點，就是從它開始到控制流程圖中任何結(jié)點都有一條通路的結(jié)點。11.3控制流分析和循環(huán)優(yōu)化控制流程圖（流圖）：具有唯一11.3.1程序流圖與循環(huán)一個程序可用一個流圖來表示。流圖中的有限結(jié)點集N就是程序的基本塊集，流圖中的結(jié)點就是程序中的基本塊。流圖的首結(jié)點就是包含程序第一個語句的基本塊。程序流圖中的有向邊集E是這樣構(gòu)成的：假設(shè)流圖中結(jié)點i和結(jié)點j分別對應(yīng)于程序的基本塊i和基本塊j，則當下述條件1)或2)有一個成立時，從結(jié)點i有一有向邊引向結(jié)點j：1).基本塊j在程序中的位置緊跟在基本塊i之后，并且基本塊的出口語句不是無條件轉(zhuǎn)移語句goto（s）或停語句。2).基本塊i的出口語句是goto（s）或if…goto（s），并且（s）是基本塊j的入口語句。11.3.1程序流圖與循環(huán)一個程序可用一個流圖來表示。流第11章-代碼優(yōu)化ppt課件圖11．11程序流圖(1)readx(2)readyB1(3)r:=xmody(4)ifr=0goto(8)B2(5)x:=y(6)y:=r(7)goto(3)B3(8)writey(9)haitB4例：*(1)readx(2)ready*(3)r:=xmody(4)ifr=0goto(8)*(5)x:=y(6)y:=r(7)goto(3)*(8)writey(9)halt圖11．11程序流圖(1)readxB1(3)r:=x1243圖11.11a程序流圖的簡潔表示圖11．11程序流圖(1)readx(2)readyB1(3)r:=xmody(4)ifr=0goto(8)B2(5)x:=y(6)y:=r(7)goto(3)B3(8)writey(9)haitB41243圖11.11a程序流圖的簡潔表示圖11．1111.3.2循環(huán)在一個程序流程中，循環(huán)是必不可少的一種控制結(jié)構(gòu)。所謂循環(huán)，粗略地說，就是程序中那些可能反復(fù)執(zhí)行的代碼序列。因為循環(huán)中的代碼要反復(fù)執(zhí)行，因而為了提高目標代碼的效率必須著重考慮循環(huán)的代碼優(yōu)化。要進行循環(huán)優(yōu)化。首先必須找出程序中的循環(huán)，為找出程序中的循環(huán)，就需要對程序的控制流程進行分析。11.3.2循環(huán)在一個程序流程中，循環(huán)是必不可少的一種控制在程序流圖中，我們稱具有下列性質(zhì)的結(jié)點序列為一個循環(huán)：①它們是強連通的。也即，其中任意兩個結(jié)點之間，必有一條通路，而且該通路上各結(jié)點都屬于該結(jié)點序列。如果序列只包含一個結(jié)點，則必有一有向邊從該結(jié)點引到其自身。②它們中間有且只有一個是入口結(jié)點。所謂入口結(jié)點，是指序列中具有下述性質(zhì)的結(jié)點：從序列外某結(jié)點，有一有向邊引到它，或者它就是程序流圖的首結(jié)點。因此，我們定義的循環(huán)就是程序流圖中具有唯一入口結(jié)點的強連通子圖，從循環(huán)外要進入循環(huán)，必須首先經(jīng)過循環(huán)的入口結(jié)點。在程序流圖中，我們稱具有下列性質(zhì)的結(jié)點序列為一個循環(huán)：例11.8圖11.12中的程序流圖，根據(jù)定義，結(jié)點序列｛6｝，｛4，5，6，7｝以及｛2，3，4，5，6，7｝都是循環(huán)；而結(jié)點序列｛2，4｝，｛2，3，4｝，｛4，6，7｝以及｛4，5，7｝雖然都是強連通的，但因它們的入口結(jié)點不唯一，所以都不是上述意義下的循環(huán)。不難看出,圖11.11中的程序流圖里,｛B2，B3｝是程序中的循環(huán)，而B2是唯一的入口結(jié)點圖11.12程序流圖例11.8圖11.12中的程序流圖，根據(jù)定義，結(jié)點序列｛11.3.3循環(huán)的查找為了找出程序流圖中的循環(huán)，需要分析流圖中結(jié)點的控制關(guān)系。為此，我們引入必經(jīng)結(jié)點和必經(jīng)結(jié)點集的定義。在程序流圖中，對任意兩個結(jié)點m和n，如果從流圖的首結(jié)點出發(fā)，到達n的任一通路都要經(jīng)過m，則稱m是n的必經(jīng)結(jié)點，記為mDOMn。流圖中結(jié)點n的所有必經(jīng)結(jié)點的集合，稱為結(jié)點n的必經(jīng)結(jié)點集，記為D（n）。顯然，循環(huán)的入口結(jié)點是循環(huán)中所有結(jié)點的必經(jīng)結(jié)點。11.3.3循環(huán)的查找為了找出程序流圖中的循環(huán)，需要分把DOM可以看作流圖結(jié)點集上定義的一個關(guān)系，則由定義容易看出，它具有以下性質(zhì)：1.自反性：對流圖中任意結(jié)點a，有aDOMa。2.傳遞性：對流圖中任意結(jié)點a、b和c。若aDOMb，bDOMc，則有aDOMc。3.反對稱性：若aDOMb且bDOMa，則必有a＝b。因此，關(guān)系DOM是一個偏序關(guān)系。任何結(jié)點n的必經(jīng)結(jié)點集是一個有序集。把DOM可以看作流圖結(jié)點集上定義的一個關(guān)系，則由定義容易看出例11.8求圖11.12中各結(jié)點的D（n）。直接由定義和DOM的性質(zhì)，可以求得：必經(jīng)結(jié)點集:D(1)={1}D(2)={1,2}D(3)={1,2,3}D(4)={1,2,4}D(5)={1,2,4,5}D(6)={1,2,4,6}D(7)={1,2,4,7}圖11.12程序流圖例11.8求圖11.12中各結(jié)點的D（n）。圖11.1循環(huán)的查找循環(huán)的查找算法:回邊：假設(shè)a→b是流圖中的一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。有向邊n→d是回邊，組成的循環(huán)是由結(jié)點d，結(jié)點n以及有通路到達n而該通路不經(jīng)過d的所有結(jié)點組成，并且d是該循環(huán)的唯一入口結(jié)點。

應(yīng)用上述的必經(jīng)結(jié)點集，可以求出流圖中的回邊，利用回邊，就可以找出流圖中的循環(huán)。循環(huán)的查找循環(huán)的查找算法:回邊：假設(shè)a→b是流圖中的一條有向例11.9求圖11.12中流圖的所有回邊。由流圖可以看出，有向邊6→6、7→4、4→2是回邊。因為根據(jù)前例的結(jié)果有6DOM6，4DOM7，2DOM4，其它有向邊都不是回邊。對于圖11.12流圖中的例子，我們很容易看出。由回邊6→6組成的循環(huán)就是｛6｝,由回邊7→4組成的循環(huán)是｛4，5，6，7｝；由回邊4→2組成的循環(huán)是｛2，3，4，5，6，7｝。圖11.12程序流圖例11.9求圖11.12中流圖的所有回邊。圖11.1211.3.4循環(huán)優(yōu)化在找出了程序流圖中的循環(huán)之后，我們就可以針對每個循環(huán)進行優(yōu)化工作。因為循環(huán)內(nèi)的指令是重復(fù)執(zhí)行的，故而循環(huán)中進行的優(yōu)化在整個優(yōu)化工作中是非常重要的。循環(huán)優(yōu)化的三種重要技術(shù)是：代碼外提；刪除歸納變量和強度削弱。我們只對代碼外提再進行一些討論.代碼外提:減少循環(huán)中代碼數(shù)目的一個重要辦法是代碼外提。11.3.4循環(huán)優(yōu)化在找出了程序流圖中的循環(huán)之后，我們就可前面已經(jīng)介紹了一個代碼外提的例子。這種變換把循環(huán)不變運算，即產(chǎn)生的結(jié)果獨立于循環(huán)執(zhí)行次數(shù)的表達式，放到循環(huán)的前面。這里，所討論的循環(huán)只存在一個入口。實行代碼外提時，在循環(huán)的入口結(jié)點前面建立一個新結(jié)點（基本塊），稱之為循環(huán)的前置結(jié)點。循環(huán)的前置結(jié)點以循環(huán)的入口結(jié)點為其唯一后繼，原來流圖中從循環(huán)外引到循環(huán)入口結(jié)點的有向邊，改成引到循環(huán)前置結(jié)點，如圖11.13所示：圖11.13代碼外提的流圖入口結(jié)點循環(huán)L┇┇入口結(jié)點循環(huán)L┇┇前置結(jié)點前面已經(jīng)介紹了一個代碼外提的例子。這種變換把循環(huán)不變運算，即我們考慮的循環(huán)結(jié)構(gòu)，其入口結(jié)點是唯一的。所以，前置結(jié)點也是唯一的。循環(huán)中外提的代碼將全部提至前置結(jié)點中。前面介紹的圖11.3和圖11.4都是圖11.2的代碼外提的結(jié)果。在那個例子中，我們可以很明顯地看到代碼外提的優(yōu)化作用。是否在任何情況下，都可把循環(huán)不變運算外提呢?下面我們看一個例子。我們考慮的循環(huán)結(jié)構(gòu)，其入口結(jié)點是唯一的。所以，前置結(jié)點也是唯例11.10考察圖11.14的流圖。容易看出｛B2，B3，B4｝是循環(huán)，其中B2是循環(huán)的入口結(jié)點，B4是出口結(jié)點。所謂出口結(jié)點，是指循環(huán)中具有這樣性質(zhì)的結(jié)點：從該結(jié)點有一有向邊引到循環(huán)外的某結(jié)點。圖11.14的B3中i∶=2是循環(huán)不變運算。如果我們把i∶=2提到循環(huán)的前置結(jié)點B′2中，如圖11.15所示。圖11.14程序流圖（1）i:=1B1(2)ifx<ygotoB3