第11章代碼優(yōu)化,源語言程序經(jīng)過詞法分析、語法分析、語義分析等編譯前期工作，得到了不改變?cè)瓉沓绦蜻\(yùn)行結(jié)果且與原來程序功能等價(jià)的中間代碼。而生成的中間代碼并不是最優(yōu)的，所以要對(duì)中間代碼進(jìn)行優(yōu)化。所謂優(yōu)化，實(shí)質(zhì)上是對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能夠生成更有效的目標(biāo)代碼。所謂有效，無非從時(shí)間和空間兩個(gè)因素來考慮，即使得變換之后的程序運(yùn)行速度更快、占用存儲(chǔ)空間更少，這兩個(gè)因素需要均衡考慮。,詞法分析器,語法分析器,中間代碼生成器,優(yōu)化段,表格管理,出錯(cuò)處理,目標(biāo)代碼生成器,優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼。等價(jià)：指不改變程序的運(yùn)行結(jié)果。有效：指目標(biāo)代碼運(yùn)行時(shí)間短，占用的存儲(chǔ)空間小。,本章教學(xué)內(nèi)容,優(yōu)化的分類；常用的代碼優(yōu)化技術(shù);局部優(yōu)化；循環(huán)優(yōu)化。,一、代碼優(yōu)化的分類,根據(jù)代碼優(yōu)化是否涉及具體的計(jì)算機(jī)來劃分，代碼優(yōu)化可分為兩大類。一類是與機(jī)器有關(guān)的優(yōu)化，這類優(yōu)化一般在目標(biāo)代碼上進(jìn)行，需要依賴于具體的機(jī)器。具體的有對(duì)寄存器優(yōu)化、多處理機(jī)的優(yōu)化、特殊指令的優(yōu)化等。另一類是與機(jī)器無關(guān)的優(yōu)化，在中間代碼上進(jìn)行，我們主要討論這一種優(yōu)化。,另外根據(jù)代碼優(yōu)化所涉及的程序范圍，又可分為局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三個(gè)不同的級(jí)別。局部優(yōu)化指的是在只有一個(gè)入口、一個(gè)出口的基本程序塊上進(jìn)行的優(yōu)化。循環(huán)優(yōu)化是對(duì)循環(huán)中的代碼進(jìn)行的優(yōu)化，在一個(gè)程序運(yùn)行時(shí)，相當(dāng)多的一部分時(shí)間會(huì)花在循環(huán)上，因此，基于循環(huán)的優(yōu)化非常重要。全局優(yōu)化是在整個(gè)程序范圍內(nèi)進(jìn)行的優(yōu)化。,二、常用的代碼優(yōu)化技術(shù),代碼優(yōu)化的目的是為了產(chǎn)生效率更高的代碼。編譯程序中的代碼優(yōu)化階段提供的對(duì)代碼的各種變換必須遵循一定的原則。（1）等價(jià)原則。經(jīng)過優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果。（2）有效原則。使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短，占用的存儲(chǔ)空間較小。（3）合算原則。應(yīng)盡可能以較低的代價(jià)取得較好的優(yōu)化效果。,為了獲得更優(yōu)化的程序，可以從各個(gè)環(huán)節(jié)著手。首先，在源代碼這一級(jí)，程序員可以通過選擇適當(dāng)?shù)乃惴ê桶才胚m當(dāng)?shù)膶?shí)現(xiàn)語句來提高程序的效率。例如，進(jìn)行排序時(shí)，采用“快速排序”比采用“插入排序”就要快得多。其次，在設(shè)計(jì)語義動(dòng)作時(shí)，我們不僅可以考慮產(chǎn)生更加高效的中間代碼，而且還可以為后面的優(yōu)化階段做一些可能的預(yù)備工作。例如，可以在循環(huán)語句的頭和尾對(duì)應(yīng)的中間代碼“打上標(biāo)記”，這樣可以有助于后面的控制流和數(shù)據(jù)流分析；代碼的分叉處和交匯處也可以打上標(biāo)記，以便于識(shí)別程序流圖中的直接前驅(qū)和直接后繼。,對(duì)編譯產(chǎn)生的中間代碼，我們安排專門的優(yōu)化階段，進(jìn)行各種等價(jià)變換，以改進(jìn)代碼的效率。在目標(biāo)代碼這一級(jí)上，我們應(yīng)該考慮如何有效地利用寄存器，如何選擇指令，以及進(jìn)行窺孔優(yōu)化等等。通常為了使優(yōu)化不依賴于目標(biāo)機(jī)器的特性，主要的優(yōu)化工作在中間代碼上進(jìn)行。因此，我們著重討論中間代碼這一級(jí)上的優(yōu)化。這時(shí)的問題是，優(yōu)化應(yīng)用于程序的哪些部分？,示例,【例101】設(shè)A,B分別為兩個(gè)一維數(shù)組，其初始地址分別表示為addr(A),addr(B)。源程序段為：X0；For(i=1;i20;i+)X=X+Ai*Bi；若機(jī)器按字節(jié)編址，按照循環(huán)語句的翻譯，可以得到一組中間代碼。,中間代碼,1.刪除公共子表達(dá)式(刪除多余運(yùn)算),如果一個(gè)表達(dá)式E在前面已經(jīng)計(jì)算過，并且在這之后E中變量的值沒有改變，則稱E為公共子表達(dá)式，是指在一個(gè)基本程序塊內(nèi)計(jì)算結(jié)果相同的子表達(dá)式。對(duì)相同的子表達(dá)式只在第一次出現(xiàn)時(shí)計(jì)算并且僅計(jì)算一次，其結(jié)果暫存入Ti，而不必重復(fù)計(jì)算，這樣既節(jié)約了空間，又節(jié)省了時(shí)間。這種優(yōu)化稱為刪除公共子表達(dá)式，也稱為刪除多余運(yùn)算。,刪除公共子表達(dá)式,2.代碼外提,代碼外提是指將循環(huán)中的不變運(yùn)算提到循環(huán)體前面。處在循環(huán)體內(nèi)的不變運(yùn)算，不論循環(huán)體重復(fù)執(zhí)行多少次都不影響其計(jì)算結(jié)果，這樣的運(yùn)算只會(huì)浪費(fèi)代碼執(zhí)行時(shí)間。因此將這類運(yùn)算提到循環(huán)體外并不影響程序運(yùn)行結(jié)果，還可加快代碼執(zhí)行速度。,代碼外提,3.強(qiáng)度削弱,強(qiáng)度削弱是指用執(zhí)行效率較高的操作等價(jià)地替換原操作。對(duì)于非算術(shù)運(yùn)算可削弱強(qiáng)度，如盡量使用寄存器，少訪問內(nèi)存（或外存）等。例如，對(duì)計(jì)算機(jī)上的二進(jìn)制算術(shù)運(yùn)算，做加法一般比作乘法的速度快。如果能在循環(huán)中進(jìn)行這種變換，其優(yōu)化效果更是顯而易見。因此，推廣到一般，對(duì)中間代碼級(jí)的運(yùn)算盡可能降低運(yùn)算級(jí)別。,強(qiáng)度削弱,T1=T14,4.變換循環(huán)控制條件(刪除歸納變量),for循環(huán)中，控制變量i的作用域是本循環(huán)體。如果在循環(huán)體內(nèi)存在一個(gè)變量（或臨時(shí)變量）T與循環(huán)控制變量i保持線性關(guān)系，同時(shí)在循環(huán)的后面不引用i，而刪去i又不影響程序結(jié)果，則可由T取代i的控制循環(huán)次數(shù)的作用。從循環(huán)中刪除i，這種方法稱為變換循環(huán)控制條件，或者稱為刪除歸納變量。,變換循環(huán)控制條件,T180,5.合并已知變量,已知量是指常數(shù)或在編譯時(shí)就能確定其值的變量。合并已知量是指在編譯時(shí)就將源程序中關(guān)于已知量的表達(dá)式之值先行算出，不必生成計(jì)算該表達(dá)式的代碼。,合并已知變量,4*1=4,6.復(fù)寫傳播,復(fù)寫傳播是指盡量不引用那些在程序中僅僅只傳遞信息而不改變其值，也不影響其運(yùn)行結(jié)果的變量。,復(fù)寫傳播,T1,7.刪除無用賦值,變量的最后一次引用到下次引用之前的最近一次賦值期間，可視為無用變量。在變量的無用期內(nèi)，對(duì)它的任何賦值均可刪除。對(duì)于那些被賦值后從未被引用的變量，對(duì)其進(jìn)行賦值操作也是無用賦值，可刪除。即對(duì)賦值語句XY，若在程序的任何的地方都不引用X，這是該語句執(zhí)行與否對(duì)程序最終運(yùn)行結(jié)果沒有任何作用，這種語句稱為無用賦值語句，可以刪除。刪除無用賦值語句可以減少程序中的無用的變量，還可以使代碼更簡潔。,刪除無用賦值,優(yōu)化后的代碼序列,優(yōu)化后的代碼序列具有以下特點(diǎn)：減少了循環(huán)體內(nèi)可執(zhí)行代碼，由12條減至10條。減少了作乘法運(yùn)算的次數(shù)，由3次降為1次。減少了全程范圍內(nèi)使用的變量，如i,T4等變量。綜上可知，經(jīng)過一系列優(yōu)化后的代碼其執(zhí)行效率明顯提高。當(dāng)然優(yōu)化工作越多，編譯系統(tǒng)的代價(jià)就會(huì)越大。因此，對(duì)某種程序設(shè)計(jì)語言翻譯出來的中間代碼要實(shí)施什么優(yōu)化，就要視語言的特點(diǎn)具體分析，力爭設(shè)計(jì)一個(gè)最適應(yīng)本語言特點(diǎn)的代碼優(yōu)化方案。,三、局部優(yōu)化,局部優(yōu)化（local）是指基本塊內(nèi)的優(yōu)化。對(duì)于給定的程序，我們可以把它劃分為一系列的基本塊。在各個(gè)基本塊的范圍內(nèi)，分別進(jìn)行優(yōu)化。局限在基本塊范圍內(nèi)的優(yōu)化稱為基本塊內(nèi)的優(yōu)化，或者稱為局部優(yōu)化。,1.基本塊的定義,所謂基本塊，是指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口語句和一個(gè)出口語句。執(zhí)行時(shí)只能從其入口語句進(jìn)入，從其出口語句退出，不存在跳轉(zhuǎn)和分叉匯合的情況。,2基本塊的劃分算法,從四元式程序中劃分基本塊的算法步驟如下：第一步：確定四元式程序（中間代碼）中各個(gè)基本塊的人口語句；所謂入口語句，嚴(yán)格地說來就是下述語句之一：程序的第一個(gè)語句；能夠由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的目標(biāo)語句；緊跟在條件轉(zhuǎn)移語句后面的語句。,劃分四元式程序?yàn)榛緣K的算法:第二步：對(duì)以上求出的每個(gè)入口語句，確定其所屬的基本塊。它是由該入口語句到下一入口語句(不包括該入口語句)之間的語句序列組成的。,入口語句n入口語句m,劃分四元式程序?yàn)榛緣K的算法:第二步：對(duì)以上求出的每個(gè)入口語句，確定其所屬的基本塊。它是由該入口語句到下一入口語句(不包括該入口語句)、或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)之間的語句序列組成的。,入口語句n入口語句m,入口語句n轉(zhuǎn)移語句m,劃分四元式程序?yàn)榛緣K的算法:第二步：對(duì)以上求出的每個(gè)入口語句，確定其所屬的基本塊。它是由該入口語句到下一入口語句(不包括該入口語句)、或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)、或一停語句(包括該停語句)之間的語句序列組成的。,入口語句n入口語句m,入口語句n轉(zhuǎn)移語句m,入口語句n停語句m,劃分四元式程序?yàn)榛緣K的算法:第二步：對(duì)以上求出的每個(gè)入口語句，確定其所屬的基本塊。它是由該入口語句到下一入口語句(不包括該入口語句)、或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)、或一停語句(包括該停語句)之間的語句序列組成的。第三步：凡未被納入某一基本塊的語句，都是程序中控制流程無法達(dá)到的語句，因而也是不會(huì)被執(zhí)行到的語句，我們可以把它們刪除。,例：劃分基本塊(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。,例：劃分基本塊(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。,例：劃分基本塊(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。,例：劃分基本塊(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。,例：劃分基本塊(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,1.求出四元式程序中各個(gè)基本塊的入口語句:1)程序第一個(gè)語句，或2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或3)緊跟在條件轉(zhuǎn)移語句后面的語句。,例：劃分基本塊(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,2.對(duì)以上求出的每個(gè)入口語句，確定其所屬的基本塊。它是由該入口語句到下一入口語句(不包括該入口語句)、或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)、或一停語句(包括該停語句)之間的語句序列組成的。,示例,【例102】將下面的四元式序列劃分為基本塊：（1）（，l，_，I）（2）（j，_，_，（4）（3）（，I，1，I）（4）（j，I，N，（6）（5）（j，_，_，（9）（6）（，M，I，T）（7）（，T，_，M）（8）（j，_，_，（3）（9）,3基本塊的變換,基本塊的主要保結(jié)構(gòu)變換是:1刪除公共子表達(dá)式2刪除無用賦值3重新命名臨時(shí)變量4交換語句次序,4.基本塊的DAG表示,DAG（DirectedAcyclicGraph）即無環(huán)有向圖，它是有向圖中的一種，通常用來對(duì)基本塊進(jìn)行優(yōu)化。這種有向圖是一種其結(jié)點(diǎn)帶有下述標(biāo)記或附加信息的DAG：1圖的葉結(jié)點(diǎn)(即沒有后繼的結(jié)點(diǎn))以一標(biāo)識(shí)符(變量名)或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。如果葉結(jié)點(diǎn)用來代表某變量A的地址，則用addr(A)作為該結(jié)點(diǎn)的標(biāo)記。通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo)0，以表示它是該變量的初值。,2圖的內(nèi)部結(jié)點(diǎn)（即有后繼的結(jié)點(diǎn)）以一運(yùn)算符作為標(biāo)記，表示該節(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。3圖中各個(gè)結(jié)點(diǎn)可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。上述這種DAG可用來描述計(jì)算過程，又稱為描述計(jì)算過程的DAG。在以下的討論中，我們簡稱為DAG.,基本塊的DAG表示,一個(gè)基本塊，可用一個(gè)DAG來表示?？梢岳肈AG來描述四元式，如圖所示，列出了各種四元式以及相對(duì)應(yīng)的DAG的結(jié)點(diǎn)形式。圖中為結(jié)點(diǎn)編號(hào)，結(jié)點(diǎn)下面的符號(hào)（運(yùn)算符，標(biāo)識(shí)符或常數(shù)）是各結(jié)點(diǎn)的標(biāo)記，各結(jié)點(diǎn)右邊的標(biāo)識(shí)符是結(jié)點(diǎn)的附加標(biāo)識(shí)符。,四元式,（0）AB（，B，A）對(duì)應(yīng)的DAG結(jié)點(diǎn)為：,四元式,（1）AopB（op，B，A）對(duì)應(yīng)的DAG結(jié)點(diǎn)為：,四元式,（2）ABopC（op，B，C，A）對(duì)應(yīng)的DAG結(jié)點(diǎn)為：,四元式,（3）ABC（，BC，A）對(duì)應(yīng)的DAG結(jié)點(diǎn)為：,四元式,（4）ifBropCgoto（s）（jrop，B，C，（s）對(duì)應(yīng)的DAG結(jié)點(diǎn)為：,四元式,（5）DCB（，B，DC）對(duì)應(yīng)的DAG結(jié)點(diǎn)為：,四元式,（6）goto（s）（j，（s）對(duì)應(yīng)的DAG結(jié)點(diǎn)為：,5.基本塊的DAG構(gòu)造算法,假設(shè)DAG各結(jié)點(diǎn)信息將用某種適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)來存放。并設(shè)有一個(gè)標(biāo)識(shí)符（包括常數(shù)）A與結(jié)點(diǎn)NODE(A)的對(duì)應(yīng)表，即用大寫字母A，B等表示四元式中的變量名或常數(shù)。NODE(A)是描述這種對(duì)應(yīng)關(guān)系的一個(gè)函數(shù)，即用NODE(A)表示A在DAG中的相應(yīng)結(jié)點(diǎn)，它的值可以是一個(gè)結(jié)點(diǎn)的編號(hào)n或者無定義。NODE(A)n代表DAG中存在一個(gè)結(jié)點(diǎn)n，A是其上的標(biāo)記或附加標(biāo)識(shí)符。,四元式分類,把各種形式的四元式按其對(duì)應(yīng)結(jié)點(diǎn)的后繼個(gè)數(shù)分為四類。其中：0型四元式：有0個(gè)后繼結(jié)點(diǎn)，如四元式(0)；1型四元式：有1個(gè)后繼結(jié)點(diǎn)，如四元式(1)；2型四元式：有2個(gè)后繼結(jié)點(diǎn)，如四元式(2)、(3)和(4)；3型四元式：有3個(gè)后繼結(jié)點(diǎn)，如四元式(5)。,對(duì)于3型四元式，由于對(duì)數(shù)組元素賦值的情形需特殊考慮，因此暫不討論，對(duì)四元式(6)也不涉及，下面是僅含0，1，2型四元式的基本塊的DAG構(gòu)造算法。假設(shè)要考慮的中間代碼（四元式）包括如下三種形式：0型四元式AB1型四元式AopB2型四元式ABopC或者ABC,僅含0，1，2型四元式的基本塊的DAG構(gòu)造算法如下：初始時(shí)，DAG為空。對(duì)基本塊中的每一條四元式，依次執(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型，則()如果NODE(C)無定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)并定義NODE(C)為這個(gè)結(jié)點(diǎn)，()轉(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í)行opB(即合并已知量)，令得到的新常數(shù)為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í)行BopC(即合并已知量)，令得到的新常數(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.。,3.(1)檢查DAG中是否已有一結(jié)點(diǎn)，其唯一后繼為NODE(B)，且標(biāo)記為op(即找公共子表達(dá)式)。如果沒有，則構(gòu)造該結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(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)處理下一四元式。,示例,【例103】試構(gòu)造以下基本塊G的DAG。（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,6.基本塊的應(yīng)用,將四元式表示成相應(yīng)的DAG后，可以利用DAG來進(jìn)行優(yōu)化。利用基本塊來進(jìn)行優(yōu)化的主要思想是：首先將一個(gè)基本塊中的每一個(gè)四元式依次表示成對(duì)應(yīng)的DAG，再將這些DAG合成對(duì)于一個(gè)較大的DAG，即為該基本塊的DAG。然后按照構(gòu)造DAG結(jié)點(diǎn)的順序重寫四元式序列，就可以得到經(jīng)過“合并已知量”、“刪除無用賦值”、“刪除公共子表達(dá)式”的等價(jià)的基本塊，即為優(yōu)化后的基本塊。,示例,將前面的DAG按原來構(gòu)造其結(jié)點(diǎn)的順序，重新寫成四元式，得到以下的四元式序列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,優(yōu)化后的四元式若只有A和B是出基本塊之后活躍的(1)T2:=R+r(2)A:=6.28*T2(3)T6:=R-r(4)B:=A*T6(1)S1:=R+r(2)A:=6.28*S1(3)S2:=R-r(4)B:=A*S2,從DAG中還能得到其他的優(yōu)化信息：在基本塊外被定值并在基本塊內(nèi)被引用的所有標(biāo)識(shí)符，就是作為葉子結(jié)點(diǎn)上標(biāo)記的那些標(biāo)識(shí)符。在基本塊內(nèi)被定值并且該值在基本塊后面可以被引用的所有標(biāo)識(shí)符，就是DAG各結(jié)點(diǎn)上的那些附加標(biāo)識(shí)符。,四、循環(huán)優(yōu)化,在程序設(shè)計(jì)語言中，循環(huán)是必不可少的控制結(jié)構(gòu)之一。所謂循環(huán)，粗略地說，就是程序中那些可能反復(fù)執(zhí)行的代碼序列。因?yàn)檠h(huán)中的代碼要反復(fù)執(zhí)行，因而為了提高目標(biāo)代碼的效率必須著重考慮循環(huán)的代碼優(yōu)化。,循環(huán)優(yōu)化是指在循環(huán)體中進(jìn)行的專項(xiàng)優(yōu)化，是提高程序運(yùn)行效率的主要途徑。因?yàn)樵谝粋€(gè)執(zhí)行n次的循環(huán)體內(nèi)進(jìn)行一項(xiàng)優(yōu)化，從運(yùn)行效率上來說，相當(dāng)于進(jìn)行了n項(xiàng)優(yōu)化。為了進(jìn)行循環(huán)優(yōu)化，首先必須找出程序中的循環(huán)，為找出程序中的循環(huán)，就需要對(duì)程序的控制流程進(jìn)行分析。我們將使用程序的控制流程圖對(duì)所討論的循環(huán)給出定義，并介紹怎樣從程序的控制流程圖中找出程序的循環(huán)。對(duì)循環(huán)中的代碼段，可以進(jìn)行代碼外提、強(qiáng)度削弱和刪除歸納變量等優(yōu)化。,1.程序流圖,一個(gè)控制流程圖就是具有唯一首結(jié)點(diǎn)的有向圖。所謂首結(jié)點(diǎn)，就是從它開始到控制流程圖中任何結(jié)點(diǎn)都有一條通路的結(jié)點(diǎn)。一個(gè)控制流程圖表示成一個(gè)三元組G(N，E，n0)，其中，N代表圖中所有結(jié)點(diǎn)集，E代表圖中所有有向邊集，n0代表首結(jié)點(diǎn)。以下把控制流程圖簡稱為流圖。,一個(gè)程序可用一個(gè)流圖來表示。流圖中的有限結(jié)點(diǎn)集N就是程序的基本塊集，流圖中的結(jié)點(diǎn)就是程序中的基本塊。流圖的首結(jié)點(diǎn)就是包含程序第一個(gè)語句的基本塊。,程序流圖中的有向邊集E是這樣構(gòu)成的：假設(shè)流圖中結(jié)點(diǎn)i和結(jié)點(diǎn)j分別對(duì)應(yīng)于程序的基本塊i和基本塊j，則當(dāng)下述條件1.或2.有一個(gè)成立時(shí)，從結(jié)點(diǎn)i有一有向邊引向結(jié)點(diǎn)j：1.基本塊j在程序中的位置緊跟在基本塊i之后，并且基本塊i的出口語句不是無條件轉(zhuǎn)移語句goto(s)或停語句。2基本塊i的出口語句是goto(s)或ifgoto(s)，并且(s)是基本塊j的入口語句。,示例,【例10.4】為以下程序構(gòu)造一個(gè)流圖（1）readx（2）ready（3）z=xmody（4）ifz=0goto(8)（5）x=y（6）y=z（7）goto(3)（8）writey（9）halt,程序流圖,2.循環(huán)的定義,在流圖中,稱具有下列性質(zhì)的結(jié)點(diǎn)序列為一個(gè)循環(huán)：它們是強(qiáng)連通的。即其中任意兩個(gè)結(jié)點(diǎn)之間，必有一條通路，而且該通路上各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列。如果序列只包含一個(gè)結(jié)點(diǎn)，則必有一有向邊從該結(jié)點(diǎn)引到其自身。它們中間有且只有一個(gè)是入口結(jié)點(diǎn)。所謂入口結(jié)點(diǎn)，是指序列中具有下述性質(zhì)的結(jié)點(diǎn)：從序列外某結(jié)點(diǎn)，有一有向邊引到它，或者它就是程序流圖的首結(jié)點(diǎn)。循環(huán)就是流圖中具有唯一入口結(jié)點(diǎn)的強(qiáng)連通子圖，從循環(huán)外要進(jìn)入循環(huán)，必須首先經(jīng)過循環(huán)的入口結(jié)點(diǎn)。,示例,對(duì)此流圖，根據(jù)定義，結(jié)點(diǎn)序列6，4，5，6，7以及2，3，4，5，6，7都是循環(huán)；而結(jié)點(diǎn)序列2，4，2，3，4，4，6，7以及4，5，7雖然都是強(qiáng)連通的，但因它們的入口結(jié)點(diǎn)不唯一，所以都不是上述意義下的循環(huán)。,3.循環(huán)的查找,為了查找循環(huán)，需對(duì)程序流圖中各結(jié)點(diǎn)的控制關(guān)系進(jìn)行分析，即利用控制點(diǎn)（dominator）查找循環(huán)。在一個(gè)已知的程序流圖里，如何確定循環(huán)是由哪些結(jié)點(diǎn)組成的呢？仔細(xì)觀察程序流圖中各結(jié)點(diǎn)的控制關(guān)系，根據(jù)循環(huán)語句的特點(diǎn)和循環(huán)的定義不難發(fā)現(xiàn)，從循環(huán)入口即循環(huán)的首結(jié)點(diǎn)開始，每一個(gè)結(jié)點(diǎn)都有其后繼結(jié)點(diǎn)，直至循環(huán)的出口結(jié)點(diǎn)。,同時(shí)從循環(huán)的出口結(jié)點(diǎn)一定要轉(zhuǎn)向該循環(huán)的入口結(jié)點(diǎn)，這是由循環(huán)語句自身的功能所定。因?yàn)檠h(huán)體被執(zhí)行完后要判斷循環(huán)條件是否成立，若成立，再重復(fù)執(zhí)行循環(huán)體，體現(xiàn)在程序流圖中就是循環(huán)出口結(jié)點(diǎn)至入口結(jié)點(diǎn)一定存在一條有向邊，由這條有向邊的出發(fā)結(jié)點(diǎn)（即循環(huán)出口結(jié)點(diǎn)）開始往回找前驅(qū)結(jié)點(diǎn)，直至循環(huán)入口結(jié)點(diǎn)就是循環(huán)。為了區(qū)別于其他的有向邊，稱上述有向邊為回邊，組成這條邊的關(guān)鍵結(jié)點(diǎn)為必經(jīng)結(jié)點(diǎn)。因此，查找循環(huán)的關(guān)鍵就是找回邊及其所有與回邊有關(guān)聯(lián)的必經(jīng)結(jié)點(diǎn)。,必經(jīng)結(jié)點(diǎn)與必經(jīng)結(jié)點(diǎn)集,【必經(jīng)結(jié)點(diǎn)】在程序流圖中，對(duì)任意兩個(gè)結(jié)點(diǎn)a和b，若從程序流圖中的首結(jié)點(diǎn)到某結(jié)點(diǎn)n的所有路徑都要經(jīng)過結(jié)點(diǎn)m，則稱結(jié)點(diǎn)m控制了結(jié)點(diǎn)n，并稱m是n的必經(jīng)結(jié)點(diǎn)，記作mDOMn?！颈亟?jīng)結(jié)點(diǎn)集】流圖中結(jié)點(diǎn)m的所有必經(jīng)結(jié)點(diǎn)的集合稱為結(jié)點(diǎn)m的必經(jīng)結(jié)點(diǎn)集，記為D（m）。根據(jù)定義，對(duì)任一結(jié)點(diǎn)n，有nDOMn；并且循環(huán)的入口結(jié)點(diǎn)必為循環(huán)中每個(gè)結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)。,性質(zhì),若將DOM看做流圖結(jié)點(diǎn)集上定義的一個(gè)關(guān)系，根據(jù)以上定義，它具有以下性質(zhì)：（1）自反性：對(duì)流圖中任意結(jié)點(diǎn)a，有aDOMa。（2）傳遞性：對(duì)流圖中任意結(jié)點(diǎn)a，b和c，若aDOMb和bDOMc，則aDOMc。（3）反對(duì)稱性：若aDOMb和bDOMa，則ab。由上可見，關(guān)系DOM是一個(gè)偏序關(guān)系，因此，任何結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集是個(gè)有序集。,【例10.5】求解圖中各個(gè)結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集D(n)。,回邊,【回邊】設(shè)ab是流圖中的一條有向邊，如果bDOMa，則稱ab是流圖中的一條回邊。對(duì)于一已知流圖，只要求出各結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集，就可以求出流圖中所有的回邊。利用回邊可以方便地查找循環(huán)。設(shè)nd為流程圖中的一條回邊，則流程圖中那些不經(jīng)過結(jié)點(diǎn)d而能到達(dá)n的所有結(jié)點(diǎn)以及結(jié)點(diǎn)d和結(jié)點(diǎn)n本身，構(gòu)成了流程圖中的一個(gè)循環(huán)，且d為該循環(huán)的唯一入口。有向邊ab是否都是回邊呢？由定義可知，作為回邊的有向邊，必須滿足條件：b是a的必經(jīng)結(jié)點(diǎn)。,示例,【例10.7】計(jì)算前圖中流圖的所有回邊。在圖中，存在有向邊12，但結(jié)點(diǎn)不是結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)，所以不是回邊。對(duì)有向邊66：因?yàn)镈（6）1，2，4，6，所以6DOM6。74：因?yàn)镈（7）1，2，4，7，所以4DOM7。42：因?yàn)镈（4）1，2，4，所以2DOM4。上述三條有向邊滿足回邊的條件，所以它們均為回邊。,顯然，可以驗(yàn)證流圖中其他有向邊均不滿足回邊的定義，所以不是回邊。所以，有向邊66、74、42是回邊，其它有向邊都不是回邊。對(duì)于前面流圖中的例子，很容易看出：由回邊66組成的循環(huán)就是6；由回邊74組成的循環(huán)是4，5，6，7；由回邊42組成的循環(huán)是2，3，4，5，6，7。,利用回邊查找循環(huán)的基本思想,回邊確定之后，如何根據(jù)回邊求循環(huán)呢？如果已知有向邊ab是回邊，根據(jù)循環(huán)的定義可知，該循環(huán)是由從結(jié)點(diǎn)b出發(fā)的，所有有通路到達(dá)結(jié)點(diǎn)a但該通路又不經(jīng)過b的結(jié)點(diǎn)組成，并且b是該循環(huán)的唯一入口結(jié)點(diǎn)。,求由回邊ab組成的循環(huán)的基本思想是：首先確定循環(huán)的出口a，判斷a和b，若ab，求a的所有前驅(qū)結(jié)點(diǎn)（L），若前驅(qū)結(jié)點(diǎn)不是循環(huán)入口，再求前驅(qū)的前驅(qū)（L），直至所求出的前驅(qū)都是b為止。,示例,在前面的流圖中：回邊66組成的循環(huán)是：6?；剡?4組成的循環(huán)是：4，5，6，7，其中結(jié)點(diǎn)，是不經(jīng)過結(jié)點(diǎn)而有通路到達(dá)結(jié)點(diǎn)的結(jié)點(diǎn)。回邊42組成的循環(huán)是：2，3，4，5，6，7。,求回邊ab組成的循環(huán)的算法,voidinsert（x）；ifx不屬于LoopLoopLoopx；把x下推進(jìn)棧stack；,main主函數(shù)中根據(jù)回邊查找循環(huán)的算法：stack空；Loopb；insert（a）；Whilestack非空把stack的棧頂元素x出棧；forpP（x）insert（p）；其中，P（x）表示結(jié)點(diǎn)x的前驅(qū)結(jié)點(diǎn)集，stack為工作棧，Loop為所求循環(huán)中的結(jié)點(diǎn)集。insert為一函數(shù)。,算法的基本思想,算法的基本思想是：由于要求回邊ab組成的循環(huán)，這個(gè)循環(huán)將以b為其唯一入口，a是它的一個(gè)出口。若a不同時(shí)是b，則a的所有前驅(qū)結(jié)點(diǎn)應(yīng)屬于循環(huán)。當(dāng)求出a的所有前驅(qū)后，只要它們不是循環(huán)入口b，就應(yīng)再求出它們的前驅(qū)，新求出的所有前驅(qū)也應(yīng)屬于循環(huán)。然后再對(duì)新求出的所有前驅(qū)，重復(fù)以上步驟，直到所求出的前驅(qū)是b為止。此時(shí)算法結(jié)束。,【例10.8】利用算法求前面流圖中回邊74組成的循環(huán)。,開始，置Loop4，stack為空。由insert把結(jié)點(diǎn)放到棧中，此時(shí)Loop4，7。然后出棧，求的前驅(qū)結(jié)點(diǎn)集P(7)5，6，把和先后放入Loop和stack中，這時(shí)Loop4，7，5，6。結(jié)點(diǎn)的前驅(qū)都不是，再分別求的前驅(qū)和的前驅(qū)。這時(shí)，棧頂元素是結(jié)點(diǎn)，所以出棧，P(6)6，4已在Loop中，故僅出棧而已。此時(shí)棧頂元素為結(jié)點(diǎn)，P(5)4也在Loop中，故也出棧。這是棧stack已空，算法結(jié)束，所求循環(huán)Loop4，5，6，7。所以，得到前面流圖中回邊74組成的循環(huán)為6，5，4，7。,3.可歸約流圖,一個(gè)流圖被稱為可歸約的，當(dāng)且僅當(dāng)流圖中除去回邊外，其余的邊構(gòu)成一個(gè)無環(huán)路流圖?？蓺w約流圖是一類非常重要的流圖。從代碼優(yōu)化的角度來說，它具有下述重要的性質(zhì)：1.圖中任何直觀意義下的環(huán)路，都屬于我們所定義的循環(huán)。2.只要找出圖中所有回邊，對(duì)回邊應(yīng)用前述循環(huán)查找算法，就可找出流圖中所有的循環(huán)。3.圖中任意兩個(gè)循環(huán)要么嵌套，要么不相交(除了可能有公共的入口結(jié)點(diǎn))，對(duì)這類流圖進(jìn)行循環(huán)優(yōu)化較為容易。,4.循環(huán)優(yōu)化方法,在找出了程序流圖中的循環(huán)之后，我們就可以針對(duì)每個(gè)循環(huán)進(jìn)行優(yōu)化工作。因?yàn)檠h(huán)內(nèi)的指令是重復(fù)執(zhí)行的，故而循環(huán)中進(jìn)行的優(yōu)化在整個(gè)優(yōu)化工作中是非常重要的。這里介紹循環(huán)優(yōu)化的三種重要技術(shù)：代碼外提；刪除歸納變量；強(qiáng)度削弱。,代碼外提,減少循環(huán)中程序代碼數(shù)目的一個(gè)重要辦法是代碼外提。這種變換把循環(huán)不變運(yùn)算，即運(yùn)算產(chǎn)生的結(jié)果不受循環(huán)執(zhí)行次數(shù)影響的表達(dá)式，放到循環(huán)的前面。這里，所討論的循環(huán)只存在一個(gè)入口結(jié)點(diǎn)。實(shí)行代碼外提時(shí)，在循環(huán)的入口結(jié)點(diǎn)前面建立一個(gè)新結(jié)點(diǎn)(基本塊)，稱之為循環(huán)的前置結(jié)點(diǎn)。循環(huán)的前置結(jié)點(diǎn)以循環(huán)的入口結(jié)點(diǎn)為其唯一后繼，原來流圖中從循環(huán)外引到循環(huán)入口結(jié)點(diǎn)的有向邊，改成引到循環(huán)前置結(jié)點(diǎn)，如圖所示。,代碼外提時(shí)建立一個(gè)前置結(jié)點(diǎn),示例,示例,查找“不變運(yùn)算”的算法,假設(shè)L為所要處理的循環(huán)。(1)依次查看L中各基本塊的每個(gè)四元式，如果它的每個(gè)運(yùn)算對(duì)象或?yàn)槌?shù)，或者定值點(diǎn)在L外，則將此四元式標(biāo)記為“不變運(yùn)算”；(2)重復(fù)第(3)步直至沒有新的四元式被標(biāo)記為“不變運(yùn)算”為止；(3)依次查看尚未被標(biāo)記為“不變運(yùn)算”的四元式，如果它的每個(gè)運(yùn)算對(duì)象或?yàn)槌?shù)，或者定值點(diǎn)在L之外，或只有一個(gè)到達(dá)定值點(diǎn)且該點(diǎn)上的四元式已被標(biāo)記為“不變運(yùn)算”。則被查看的四元式標(biāo)記為“不變運(yùn)算”。,代碼外提算法,(1)求出循環(huán)L的所有不變運(yùn)算。(2)對(duì)步驟(1)所求得的每一不變運(yùn)算s：ABopC或AopB或AB，檢查它是否滿足以下條件(a)或(b)：(a)()s所在的結(jié)點(diǎn)是L的所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)。()A在L中其它地方未再定值。()L中所有A的引用點(diǎn)只有s中A的定值才能到達(dá)。,(b)A在離開L之后不再是活躍的，并且條件(a)的()和()成立。所謂A在離開L后不再是活躍的是指，A在L的任何出口結(jié)點(diǎn)的后繼結(jié)點(diǎn)的入口處不是活躍的(從此點(diǎn)后不再被引用)。(3)按步驟(1)所找出的不變運(yùn)算的順序，依次把符合(2)的條件(a)或(b)的不變運(yùn)算s外提到L的前置結(jié)點(diǎn)中。如果s的運(yùn)算對(duì)象(B或C)是在L中定值的，則只有當(dāng)這些定值四元式都已外提到前置結(jié)點(diǎn)中時(shí)，才可把s也外提到前置結(jié)點(diǎn)。,注意,如果把滿足條件(2)(b)的不變運(yùn)算ABopC外提到前置結(jié)點(diǎn)中。那么，執(zhí)行完循環(huán)后得到的A值，可能與不進(jìn)行外提的情形所得A值不同。但因?yàn)殡x開循環(huán)后不會(huì)引用該A值。所以不影響程序運(yùn)行結(jié)果。,強(qiáng)度削弱與刪除歸納變量,強(qiáng)度削弱是指把程序中執(zhí)行時(shí)間較長的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算。例如把循環(huán)中的乘法運(yùn)算用遞歸加法運(yùn)算來實(shí)現(xiàn)。,如果循環(huán)中有I的遞歸賦值II土C(C為循環(huán)不變量)，并且循環(huán)中T的賦值運(yùn)算可化歸為TK*I土C1(K和C1為循環(huán)不變量)，則T的賦值運(yùn)算可以進(jìn)行強(qiáng)度削弱，進(jìn)行強(qiáng)度削弱后，循環(huán)中可能出現(xiàn)一些新的無用賦值，如果它們?cè)谘h(huán)出口之后不是活躍變量，則可將其從循環(huán)中刪除。強(qiáng)度削弱在某些情況下進(jìn)行的優(yōu)化是非常有效的。例如對(duì)于下標(biāo)變量的地址計(jì)算就是如此。在循環(huán)優(yōu)化中，強(qiáng)度削弱占很重要的地位。,刪除歸納變量的優(yōu)化,【基本歸納變量】如果循環(huán)中對(duì)變量I只有唯一的形如