編譯原理第六章 代碼優(yōu)化ok

第六章代碼優(yōu)化6.1概述本節(jié)內(nèi)容一.代碼優(yōu)化概念、目的與原則二.代碼優(yōu)化器的地位和結(jié)構(gòu)三.代碼優(yōu)化分類四.代碼優(yōu)化涉及的各個環(huán)節(jié)五.四元式的改寫六.引例：優(yōu)化主要方法簡介一.代碼優(yōu)化概念、目的與原則優(yōu)化的目的是為了產(chǎn)生更高效的代碼。對程序進行各種等價變換，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼，我們通常稱這種變換為優(yōu)化。優(yōu)化的原則：(1)等價原則(3)合算原則(2)有效原則經(jīng)過優(yōu)化后不應(yīng)改變程序運行的結(jié)果。使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運行時間較短，占用的存儲空間較小。應(yīng)盡可能以較低的代價取得較好的優(yōu)化效果。二.代碼優(yōu)化器的地位和結(jié)構(gòu)編譯前端代碼生成代碼優(yōu)化器控制流分析代碼變換數(shù)據(jù)流分析三.代碼優(yōu)化分類另一類重要的優(yōu)化是在生成目標(biāo)代碼時進行的這類優(yōu)化很大程序上依賴于具體的計算機。優(yōu)化可在編譯的各個階段進行，不是“最佳化”最主要一類優(yōu)化是在目標(biāo)代碼生成以前，對語法分析后的中間代碼進行的。這類優(yōu)化不依賴于具體的計算機。1.

按所處階段分類高級語言的源程序代碼優(yōu)化，由編程人員根據(jù)程序設(shè)計技術(shù)來進行；三.代碼優(yōu)化分類單個基本塊內(nèi)局部優(yōu)化2.

按所涉及范圍循環(huán)優(yōu)化涉及所有代碼全局優(yōu)化可能涉及多個基本塊四.代碼優(yōu)化涉及的各個環(huán)節(jié)選擇適當(dāng)?shù)乃惴ㄔ创a安排適當(dāng)?shù)膶崿F(xiàn)語句源代碼的優(yōu)化很重要設(shè)計語義動作時考慮產(chǎn)生更加高效的中間代碼為后面的優(yōu)化階段做一些可能的預(yù)備工作中間代碼安排專門的優(yōu)化階段，進行各種等價變換本章討論的重點目標(biāo)代碼有效地利用寄存器選擇指令五.四元式的改寫(:=,B,,A)改寫成A:=B(op,B,,A)改寫成A:=opB(op,B,C,A)改寫成A:=BopC(=[],B,C,A)改寫成A:=B[C]([]=,B,,D[C])改寫成D[C]:=B(jrop,B,C,L)改寫成ifBropCgotoL(j,,,L)改寫成gotoL6.2局部優(yōu)化本節(jié)內(nèi)容

一.基本塊二.基本塊內(nèi)的優(yōu)化方法三.流圖四.基本塊的DAG表示及其應(yīng)用五.應(yīng)用DAG時的相關(guān)問題一.基本塊及流圖2.各個操作按代碼的排列順序執(zhí)行；3.若任一語句被執(zhí)行，則塊內(nèi)所有語句都被執(zhí)行；否則，塊內(nèi)語句都不執(zhí)行。1.入口就是其中的第一個語句；出口就是其中的最后一個語句，都是唯一的局限于基本塊范圍內(nèi)的優(yōu)化稱為基本塊內(nèi)的優(yōu)化，或稱為局部優(yōu)化。所謂基本塊，是指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口。1.基本塊在一個基本塊中的一個名字，在程序中的某個給定點是活躍的，是指如果在程序中（包括在本基本塊或在其他基本塊中）它的值在該點以后被引用如果一條三地址語句為x：=y+z，則稱對x定值

并引用y和z此時T2被定值引用了a和b2.定值與引用此點T2是活躍的因為后面兩處引用了T2T2T2T21.確定四元式程序中各個基本塊的入口語句6.2.1.

劃分四元式程序為基本塊的算法(1)程序的第一個語句(2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句(3)緊跟在條件轉(zhuǎn)移語句后面的語句2.對以上求出的每一入口語句，構(gòu)造其所屬的基本塊它是由該入口語句（開始）到另一入口語句(不包括該入口語句)，或到一停語句(包括該停語句)一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)，或到之間的語句序列組成的3.刪除無用代碼凡未被納入某一基本塊中的語句，都是程序中控制流程無法到達的語句，從而也是不會被執(zhí)行到的語句，我們可把它們從程序中刪除入口語句4.劃分基本塊示例readXreadYR:=XmodYifR=0goto(8)X:=YY:=Rgoto(3)writeYhalt程序的第一條語句條件轉(zhuǎn)移語句轉(zhuǎn)到的語句在條件轉(zhuǎn)移語句后的語句無條件轉(zhuǎn)移語句轉(zhuǎn)到的語句基本塊二.基本塊內(nèi)的優(yōu)化方法如：對于

T1:=2...T2:=4*T1此時可把T2:=4*T1

變換為T2:=8若兩個運算對象都是編譯時的已知量?？梢栽诰幾g時計算出它的值，而不必等到程序運行時再計算。我們稱這種變換為合并已知量。1.合并常數(shù)和已知量

如：假定在一個基本塊里有語句：

（1）T1:=A*B（6）T4:=A*B四元式（1）和（6）中，它們的運算相同而且值不變，因此（6）的運算是多余的，可將它等價變換為：（6'）T4:=T1消除多余運算是指對程序中重復(fù)而且結(jié)果不變的運算，2.消除多余運算；

如：（5）C:=2

（6）T4:=A*B

（7）T5:=18+C

（8）T6:=4*T5

（9）Y:=T6消除無用賦值是指對程序中的無用賦值予以消除。3.消除無用賦值

如：語句

x:=y**2中的乘方運算，通常需要調(diào)用一個函數(shù)來實現(xiàn)?？梢杂么鷶?shù)上等價的形式，用簡單的運算替換。

x:=y*y對基本塊中求值的表達式，用代數(shù)上等價的形式替換，以期使復(fù)雜運算變成簡單運算。我們稱這種變換為代數(shù)變換。4.

代數(shù)變換如果一個表達式E在前面已計算過，并且在這之后E中變量的值沒有改變，則稱E為公共子表達式。刪除公共子表示式(刪除多余運算)對于公共子表達式，我們可以避免對它的重復(fù)計算，稱為刪除公共子表達式(有時稱刪除多余運算)。公共子表達式可以在基本塊內(nèi)，也可以在全局范圍內(nèi)消除。T6：=T2(復(fù)寫語句)把T2賦給T6，x：=a[T6]中引用了T6的值，而這中間沒有改變T6的值。因此，可以把x：=a[T6]變換為x：=a[T2]這種變換稱為復(fù)寫傳播。5.復(fù)寫傳播(重復(fù)傳送)“復(fù)寫”強調(diào)了重復(fù)性，傳播是由復(fù)寫引起的復(fù)寫傳播的目的是使對某些變量的賦值變?yōu)闊o用換言之，將來可以刪除這些無用賦值語句6.復(fù)寫傳播示例T6:=T2x:=a[T6]x:=a[T2]T6:=T2T7:=T6T7:=T2T6:=T2a[T7]:=T9a[T2]:=T9T7:=T6T8:=T4T9:=a[T8]T9:=a[T4]T8:=T4T10:=T8T10:=T4T8:=T4a[T10]:=xa[T4]:=xT10:=T8在B2中有T3:=a[T2]x:=a[T2]x:=T3在B2中有T3:=a[T2]a[T4]:=xa[T4]:=T3x:=a[T2]在B3中有T5:=a[T4]T9:=a[T4]T9:=T5在B3中有T5:=a[T4]a[T2]:=T9a[T2]:=T5T9:=a[T4]由于某些變量的值在整個程序中不再被使用，因此，這些變量的賦值對程序運算結(jié)果沒有任何作用。我們可以刪除對這些變量賦值的代碼。我們稱之為刪除無用賦值或刪除無用代碼。7.

刪除無用代碼(刪除無用賦值)8.

刪除無用代碼示例a[T2]:=T5a[T4]:=T3gotoB2無用代碼三.基本塊的DAG表示及其應(yīng)用DAG(DirectedAcyclicGraph)無環(huán)路有向圖一個基本塊的DAG是一種其結(jié)點帶有下述標(biāo)記或附加信息的DAG，描述出基本塊中每個運算結(jié)果如何用于塊中后續(xù)運算。1.

概念1.葉結(jié)點——值3.結(jié)點標(biāo)識符2.其他結(jié)點——運算或變量圖的葉結(jié)點以一標(biāo)識符(變量名)或常數(shù)作為標(biāo)記，表示該結(jié)點代表該變量或常數(shù)的值。如果葉結(jié)點用來代表某變量A的地址，則用addr(A)作為該結(jié)點的標(biāo)記內(nèi)部結(jié)點以一運算符作為標(biāo)記，表示該結(jié)點代表應(yīng)用該運算符對其后繼結(jié)點所代表的值進行運算的結(jié)果圖中各個結(jié)點上可能附加一個或多個標(biāo)識符，表示這些變量具有該結(jié)點所代表的值四元式的類型與DAG結(jié)點數(shù)組元素的賦值A(chǔ)[B]:=C為3型四元式，將在6.2.4節(jié)討論；轉(zhuǎn)移goto(s)是一個孤立結(jié)點。2.

構(gòu)造基本塊的DAG的思想對于基本塊中的每個四元式A:=BopC

1.如果它們都是葉結(jié)點，且其標(biāo)記均為常數(shù)，則直接執(zhí)行運算BopC，然后建立以其運算結(jié)果P為標(biāo)記的葉結(jié)點并把A附加到此結(jié)點上去

（如果以B或C為標(biāo)記的結(jié)點是為處理本四元式才建立的，則將它們刪除）。首先找出（或建立）代表B和C“當(dāng)前值”的結(jié)點2.如果B或（和）C是內(nèi)部結(jié)點，則建立以op為標(biāo)記的新結(jié)點，此結(jié)點分別以B、C所標(biāo)記的結(jié)點為其左、右直接后繼結(jié)點，并將A附加到新建的結(jié)點上。

注意，若在此之前，DAG中已有結(jié)點其上有附加標(biāo)記A，且此結(jié)點無前驅(qū)，則在建立新結(jié)點的同時，應(yīng)把老結(jié)點上附加的A刪除，以表示A的當(dāng)前值由新建立的結(jié)點代表；3.若DAG中原來已有代表BopC的結(jié)點，則不必建立新的結(jié)點，只須把變量A附加到表示BopC之值的結(jié)點上去即可。2.

構(gòu)造基本塊的DAG的算法（算法6.2）1.葉結(jié)點生成代碼類型判斷3.查找、處理公共子表達式2.常數(shù)參數(shù)與非常數(shù)參數(shù)的判斷4.賦值號處理四.基本塊的DAG表示及其應(yīng)用

構(gòu)造基本塊的DAG的算法流程初始化生成B01生成CB是常數(shù)2B不是常數(shù)尋找公共子表達式B、C都是常數(shù)B或者C不是常數(shù)合并已知量生成新常數(shù)P處理賦值號處理A合并已知量生成新常數(shù)P尋找公共子表達式n13.14T0T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R–rB:=T5*T6文法GNODE(3.14)無定義，構(gòu)造一個標(biāo)記為3.14的結(jié)點當(dāng)前代碼為0型，記NODE(3.14)的值為n1,轉(zhuǎn)4T0:=3.14NODE(T0)無定義，將T0附加在結(jié)點n1上令NODE(T0)=n1，轉(zhuǎn)處理下一條代碼T1:=2*T0NODE(2)無定義，構(gòu)造一個標(biāo)記為2的結(jié)點當(dāng)前代碼為2型，NODE(T0)已定義，轉(zhuǎn)2（2）NODE(2)和NODE(T0)均已定義，轉(zhuǎn)2（4）執(zhí)行2*T0，新得到常數(shù)6.28,NODE(2)是處理當(dāng)前代碼時新構(gòu)造出來的，刪除之，NODE(6.28)無定義，構(gòu)造一個標(biāo)記為6.28的結(jié)點n2，置NODE(6.28)=n2，轉(zhuǎn)4NODE(T1)無定義，將T1附加在結(jié)點n2上令NODE(T1)=n2，轉(zhuǎn)處理下一條代碼n22T1n26.28T2:=R+rNODE(R)無定義，構(gòu)造一個標(biāo)記為R的結(jié)點n3，令NODE(R)=n3當(dāng)前代碼為2型，NODE(r)無定義，構(gòu)造一個標(biāo)記為r的結(jié)點n4，令NODE(r)=n4，轉(zhuǎn)2（2）n3Rn4rNODE(R)不是標(biāo)記為常數(shù)的結(jié)點，轉(zhuǎn)3（2）DAG中無結(jié)點其左后繼為NODE(R)，故構(gòu)造一個結(jié)點n5，其左后繼為NODE(R)，右后繼為NODE(r)，轉(zhuǎn)4n5+NODE(T2)無定義，將T2附加在結(jié)點n5上，令NODE(T2)=n5，轉(zhuǎn)處理下一條代碼T2A:=T1*T2NODE(T1)已定義，當(dāng)前代碼為2型，NODE(T2)已定義，轉(zhuǎn)2（2）NODE(T1)不是標(biāo)記為常數(shù)的結(jié)點，轉(zhuǎn)3（2）DAG中無結(jié)點其左后繼為NODE(T1)，故構(gòu)造結(jié)點n6，其左后繼為NODE(T1)，右后繼為NODE(T2)，轉(zhuǎn)4n6*NODE(A)無定義，將A附加到結(jié)點n6上，令NODE(A)=n6，轉(zhuǎn)處理下一條代碼AB:=ANODE(A)已定義，當(dāng)前代碼為0型，轉(zhuǎn)4NODE(B)無定義，將B附加到結(jié)點n6上，令NODE(B)=n6，轉(zhuǎn)處理下一條代碼T3:=2*T0NODE(2)無定義，構(gòu)造一個標(biāo)記為2的結(jié)點n7，令NODE(2)=n7n72當(dāng)前代碼為2型，NODE(T0)已定義，轉(zhuǎn)2（2）NODE(2)和NODE(T0)都為標(biāo)記為常數(shù)的結(jié)點，轉(zhuǎn)2（4）執(zhí)行2*T0，得到6.28，NODE(2)是處理當(dāng)前代碼時構(gòu)造出來的，刪除之；NODE(6.28)已有定義n2，轉(zhuǎn)4NODE(T3)無定義，將T3附加到NODE(6.28)上，即附加到n2上，轉(zhuǎn)處理下一條代碼T1,T3A,BT4:=R+rNODE(R)已定義，當(dāng)前代碼為2型，

NODE(r)已定義，轉(zhuǎn)2（2）NODE(R)不是標(biāo)記為常數(shù)的葉結(jié)點，轉(zhuǎn)3（2）DAG中結(jié)點n5其左后繼為NODE(R)，右后繼為NODE(r),且其標(biāo)記為+，故將n5作為當(dāng)前結(jié)點，轉(zhuǎn)4NODE(T4)無定義，將T4附加到結(jié)點n5上，令NODE(T4)=n5，轉(zhuǎn)處理下一條代碼T2,T4T5:=T3*T4NODE(T3)已定義，當(dāng)前代碼為2型，NODE(T4)已定義，轉(zhuǎn)2（2）NODE(T4)不是標(biāo)記為常數(shù)的葉結(jié)點，轉(zhuǎn)3（2）DAG中結(jié)點n6其左后繼為NODE(T3)，右后繼為NODE(T4)，且標(biāo)記為*，故將n6作為當(dāng)前結(jié)點，轉(zhuǎn)4NODE(T5)無定義，故將T5附加到結(jié)點n6上，轉(zhuǎn)處理下一條代碼A,B,T5T6:=R–rNODE(R)已定義，當(dāng)前代碼為2型，NODE(r)已定義，轉(zhuǎn)2（2）NODE(R)不是標(biāo)記為常數(shù)的葉結(jié)點，轉(zhuǎn)3（2）DAG中無結(jié)點其左后繼為NODE(R)，右后繼為NODE(r)，且標(biāo)記為-；故構(gòu)造結(jié)點n7，使其左后繼為NODE(R)，右后繼為NODE(r)，且標(biāo)記為-，轉(zhuǎn)4n7-NODE(T6)無定義，將T6附加到結(jié)點n7上，轉(zhuǎn)處理下一條代碼T6B:=T5*T6NODE(T5)已定義，當(dāng)前代碼為2型，NODE(T6)已定義，轉(zhuǎn)2（2）NODE(T5)不是標(biāo)記為常數(shù)的葉結(jié)點，轉(zhuǎn)3（2）DAG中無結(jié)點其左后繼為NODE(T5)，故構(gòu)造結(jié)點n8，使其左后繼為NODE(T5)，右后繼為NODE(T6)，且標(biāo)記為*

，轉(zhuǎn)4n8*NODE(B)已定義，故將B從NODE(B)結(jié)點（當(dāng)前為n6）中的附加標(biāo)識符集中刪除A,T5B將B附加到n8上，令NODE(B)=n8，轉(zhuǎn)處理下一條代碼所有代碼處理完畢，構(gòu)造過程結(jié)束文法G的最終DAG如上圖所示4.

構(gòu)造DAG示例例6.2

對如下的基本塊構(gòu)造基本塊DAG：（1）T1:=A*B（2）T2:=3/2（3）T3:=T1-T2（4）X:=T3（5）C:=5（6）T4:=A*B（7）C:=2（8）T5:=18+C（9）T6:=T4*T5（10）Y:=T基本塊的優(yōu)化處理第一，合并常數(shù)和已知量的運算，并將產(chǎn)生的運算結(jié)果標(biāo)記為葉結(jié)點，不再產(chǎn)生運算的內(nèi)部結(jié)點（見圖6-2(b),(g)）T2:=3/2第二，合并公共子表達式基本塊內(nèi)多次出現(xiàn)同一運算的四元式，僅構(gòu)造第一個四元式運算的內(nèi)部結(jié)點；以后的各次出現(xiàn)，只把要賦予結(jié)果的各變量標(biāo)識符附加到相應(yīng)內(nèi)部結(jié)點（見圖6-2(e)）（1）T1:=A*B（3）T3:=T1-T2（4）X:=T3（6）T4:=A*B第三，消除基本塊內(nèi)無用賦值。在基本塊內(nèi)被多次賦值的變量，若在被引用之前被再次賦值，算法6.2的第（4）步，除了把此變量名附加到新產(chǎn)生的結(jié)點之外，還把它從老結(jié)點的附加標(biāo)識符集中逐出（見圖6-2(f)），使對該變量的前一次賦值無效

C=5

c=2由DAG重寫代碼重寫中間代碼的順序應(yīng)遵循(2)轉(zhuǎn)移語句(如果有的話)仍然是基本塊的最后一個語句(保證基本塊的正確性)(1)其中任一內(nèi)部結(jié)點在其后繼結(jié)點之前被重寫(保證計算的正確性)目的：生成有效目標(biāo)代碼n13.14T0B:=A*T6n26.28n3Rn4rn5+n6*T1,T3T2,T4n7-T6n8*A,T5BT0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R–rT0T1T3T2T4AT5T6B基本塊n1結(jié)點標(biāo)記為常數(shù)，故產(chǎn)生T0:=3.14n2結(jié)點標(biāo)記為常數(shù)，故產(chǎn)生T1:=6.286.

由DAG重寫代碼示例n2結(jié)點標(biāo)記為常數(shù)，故產(chǎn)生T3:=6.28T4與T2同標(biāo)記在一個結(jié)點，故產(chǎn)生

T4:=T2T5與A同標(biāo)記在一個結(jié)點，故產(chǎn)生

T5:=An2結(jié)點標(biāo)記為常數(shù)，故產(chǎn)生A:=6.28*T2重寫過程結(jié)束，基本塊如上所示B:=A*T6T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R–rT0:=3.14T1:=2*T0B:=T5*T6T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R–r基本塊G基本塊G’優(yōu)化效果比較消除無用賦值合并公共子表達式合并常數(shù)和已知量的運算五.含有數(shù)組元素的DAG3型四元式B[C]:=D對應(yīng)的DAG結(jié)點形式五.含有數(shù)組元素的DAGx:=a[i]a[j]:=yz:=a[i]四元式序列為：（1）T1:=addr(A)-1（2）X:=T1[i]（3）T2:=addr(A)-1（4）T2[j]:=Y（5）T3:=addr(A)-1（6）Z:=T3[i]例考慮如下的源程序段：基本塊的DAG，算法6.2（1）T1:=addr(A)-1（2）X:=T1[i]（3）T2:=addr(A)-1（4）T2[j]:=Y（5）T3:=addr(A)-1（6）Z:=T3[i]；優(yōu)化：（1）T1:=addr(A)-1（2）X:=T1[i]（3）Z:=X（4）T1[j]:=Y原因：對一個數(shù)組元素賦值時，可能改變表達式a[i]的值，所以即使a和i都沒有改變，其值可能已改變了。優(yōu)化前x:=a[i]a[j]:=yz:=a[i]此時Z=y優(yōu)化后x:=a[i]z:=xa[j]:=y此時Z=a[i]例：在i=j并且y!=a[i]時，2.

數(shù)組元素引用問題解決方法在建立對一個數(shù)組A的元素賦值的結(jié)點時，“封鎖”那些以addr(A)作為它的后代之一、且所標(biāo)記的運算符為“=[]”的結(jié)點。

謂封鎖一個結(jié)點，是指在該結(jié)點上做一個標(biāo)志Δ，表示不允許在這些結(jié)點上再附加任何新的標(biāo)識符，從而取消了它作為公共子表達式的資格。所構(gòu)造的DAG優(yōu)化后的四元式序列

（1）T1:=addr(A)-1（2）X:=T1[i]（3）T1[j]:=Y（4）Z:=T1[i]與原四元式是完全等價6.3全局優(yōu)化全局優(yōu)化需要在整個程序范圍內(nèi)，對程序中的全部變量的定值和引用之間的關(guān)系進行分析，這一分析過程稱為數(shù)據(jù)流分析。確切地查找基本塊中的無用賦值，不僅需要了解基本塊中對變量的定值和引用的情況，還應(yīng)知道在基本塊外變量是否被引用。數(shù)據(jù)流分析作用：對消除無用賦值提供了可靠的依據(jù)，循環(huán)優(yōu)化和全局優(yōu)化一種強有力的工具程序流圖流圖以基本塊為結(jié)點。如果一個結(jié)點的入口語句是程序的第一條語句，則稱此結(jié)點為首結(jié)點。通過構(gòu)造一個有向圖，稱之為流圖，我們可以將控制流的信息增加到基本塊的集合上來表示一個程序。1.

概念程序流圖的結(jié)點集就是程序的基本塊集。構(gòu)造程序流圖的方法是：對于程序中的兩個基本塊Bi和Bj，如果Bj緊接著Bi被執(zhí)行，則從Bi引一條有向邊到結(jié)點Bj，稱Bi為Bj的直接前驅(qū)，Bj為Bi的直接后繼。規(guī)則1：按基本塊在程序中排列的自然次序，Bj緊跟在Bi之后，且Bi的出口語句不是無條件轉(zhuǎn)移或停語句；規(guī)則2：Bi的出口語句是一個無條件轉(zhuǎn)移或條件轉(zhuǎn)移語句，且其目標(biāo)是Bj的入口語句。2.構(gòu)造程序流圖示例

(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)haltB4程序流圖示例(1)I:=0(2)I:=I+1(3)IfI<=Ngoto（5）(4)goto（8）(5)T:=M+I(6)M:=T(7)goto（2）(8)stop6.3.2到達－定值數(shù)據(jù)流方程為了進行循環(huán)優(yōu)化和全局優(yōu)化，需要分析程序中所有變量的定值（指對變量賦值）和引用之間的關(guān)系，這一工作稱為數(shù)據(jù)流分析

一、作用

分析程序中所有變量的定值(指對變量的賦值或輸入值)和引用之間的關(guān)系、基本塊出口的活躍變量信息等，以進行循環(huán)優(yōu)化和全局優(yōu)化。二、方法1、使用變量到達－定值數(shù)據(jù)流方程和變量引用－定值鏈2、使用活躍變量數(shù)據(jù)流方程三、基本概念a)點程序中某一四元式的位置(序號或地址)b)定值點對某變量賦值或輸入值的四元式的位置c)引用點引用某變量的四元式的位置d)變量A的到達與定值若d點是變量A的一個定值點，u點是A的一個引用點，存在一條從d到u的通路，并在此通路上沒有對A的其他定值點，則稱d點對A的定值能達到u點。e)引用－定值鏈假定在程序中某點u引用了變量A，則把能到達u的A的所有定值點的全體，稱為A在引用點u的引用－定值鏈(ud鏈)到達－定值數(shù)據(jù)流方程求解a)基本量1)IN[B]

能到達基本塊B入口點的各個變量的定值點集合。B入口集合

2)OUT[B]

能到達基本塊B出口點的各變量全部定值點集合。B出口集合

3)GEN[B]

基本塊B中定值并能到達B出口點的所有定值點集合。B中“生成”的集合

4)KILL[B]

因B中定值而注銷所有與它相關(guān)變量的定值點集合。B中“殺死”的集合3.

示例(1)a:=d(2)ifa=bthengotoB2(3)b:=1(4)c:=1(5)a:=a+bB1B2B3B4(1)a:=d基本塊InGenKillOutB1?{1}?{1}B2{1}{3}?{1，3}B3{1}{4}?{1，4}B4134{5}{1}345(3)b:=1(4)c:=1(5)a:=a+baab集合GEN[B]及KILL[B]可以根據(jù)程序流圖，對基本塊B的DAG葉結(jié)點所標(biāo)記的標(biāo)識符及內(nèi)部結(jié)點的附加標(biāo)識符進行考察，確定各個定值點。對程序流圖中的所有基本塊B求出相應(yīng)IN[B]之后，按如下規(guī)則確定到達B中點P的任一變量A的全部定值點。規(guī)則1：如果B中P點之前有A的定值（可能為多個），則這些定值點中，離P最近的那個點就是能到達P的唯一定值點；規(guī)則2：如果B中P點之前無A的定值，則能到達P的A的定值點是包含在集合IN[B]中的那些A的定值點。四個集合之間內(nèi)在的關(guān)系首先，程序中某一點d對變量A的定值可到達基本塊B的出口之后，當(dāng)且僅當(dāng)（1）此定值能到達基本塊B的入口之前，且B中不再對A重新定值（即d∈IN[B]-KILL[B]）；（2）或者點d在B中，且對A的定值能到達B的出口之后（即d∈GEN[B]）

OUT[B]=IN[B]–KILL[B]GEN[B](6.1)其次，程序中某一點d對變量A的定值可到達基本塊B的入口之前，當(dāng)且僅當(dāng)此定值能到達B的某一直接前驅(qū)之后。（6.2）。

IN[B]=(Pred[B]代表B的所有前驅(qū)基本塊集合)b)基本方程OUT[B]=IN[B]–KILL[B]GEN[B](6.1)IN[B]=（6.2）

注：1)由于所有KILL[B]和GEN[B]可從給定的流圖中直接求出，所以，上述等式是關(guān)于變量IN[B]和OUT[B]的線性聯(lián)立方程組，稱為到達—定值數(shù)據(jù)流方程。

2)流圖中若有n個基本塊，則此方程共有2n個，其中GEN[B]就是基本塊內(nèi)DAG圖上的附標(biāo)，

KILL[B]指若Ai在本塊內(nèi)定值，就將所有Ai定值點(除本定值點)均注銷。(Pred[B]代表B的所有前驅(qū)基本塊集合)算法6.3迭代法求解集合方程組(6.1)-(6.2)1for(i=1;i<=N;i++){2IN[Bi]=φ;3OUT[Bi]=GEN[Bi];}4CHANGE=1;5while(CHANGE){6CHANGE=0;7for(i=1;i<=N;i++){8NEWIN=;9if(NEWIN!=IN[Bi]){10CHANGE=1;11IN[Bi]=NEWIN;12OUT[Bi]=(IN[Bi]-KILL[Bi])∪GEN[Bi];}}}例6.4圖6-66.3.3引用－定值鏈(ud鏈)的計算及應(yīng)用1、定義假定在程序中某點u引用了變量A，到達u的變量A的定值點集合稱為變量A在u點的ud鏈。2、構(gòu)成規(guī)則a)在基本塊B中，變量A在引用點u前有定值點d，并且d點的定值鏈能到達u，則A在u點的ud鏈=ndwhziz.(6.5)b)若在基本塊B中，在u點之前無對A的定值點，則變量A在u點的ud鏈={IN[B]中有關(guān)A定值的集合}注：這里，鏈?zhǔn)侵笇⒓现懈鞫ㄖ迭c連在一起構(gòu)成鏈，以便于檢索。(6.6)例6.5

變量I的引用點為d2和d6，J的引用為d4，d5和d7。求出它們的ud鏈。對于基本塊B1，由于I的引用點d2之前有唯一的定值點d1，因此，

I在d2的ud鏈為{d1}。對基本塊B3，由于J的引用點d4之前無J的塊內(nèi)定值點，故J在d4的ud鏈為IN[B3]中所包含的J點的定值點，即

{d2，d4，d5}。常數(shù)傳播及相應(yīng)地合并已知量如果能到達某一點P有變量A的唯一定值點d：A:=c（c為常數(shù)）P是A的一個引用點，那么，在P點A的值也必然為c，故可將P點對A的引用代之以常數(shù)c，這種操作稱為常數(shù)傳播。在圖6-6中，由于IN[B5]={d3，d4，d5}，故能到達d6的I的定值點是唯一的，即d3：I:=1從而可知在d6對I的引用可替之以常數(shù)1，也就是可將d6改寫為d6：I:=6算法6.4

常數(shù)傳播和合并已知量的處理CHANGE=1;while(CHANGE){CHANGE=0;for(程序中的每個語句s){for(s的每個運算量v)

if(v在引用點s的ud鏈僅含一個d且語句d為v=C(C為常數(shù))){把s中所有對v的引用均替換為C;CHANGE=1;}

if(s右端含有運算符且每個運算量都為常數(shù)){C=s的右端表達式；把語句s替換為A=C(A為語句的s左部量);CHANGE=1;}}}6.3.4活躍變量及數(shù)據(jù)流方程1、活躍變量變量A在程序中某一點P是活躍的，是指在程序流圖中，存在一條從P到A的引用點的通路。顯然，如果變量A在基本塊B中的P點定值，且從P開始直到B的出口都沒有A的引用點，若A在B的出口之后也不活躍，則A在P點的定值就必然是無用賦值2、活躍變量數(shù)據(jù)流方程a)基本量1)INL[B]

基本塊B入口點之前活躍變量集合。

2)OUTL[B]

基本塊B出口點之后活躍變量集合。3)DEF[B]

基本塊B內(nèi)定值的，但在定值前未曾在B中引用過的變量集合。4)USE[B]

基本塊B中引用，但引用前未曾在B中定值的變量集合(即DAG中葉結(jié)點的標(biāo)識符)。2、活躍變量數(shù)據(jù)流方程b)基本方程

INL[B]=OUTL[B]–DEF[B]USE[B](6.3)OUTL[B]=(6.4)

注：1)USE[B]和DEF[B]可在各基本塊內(nèi)直接求得。2)假定數(shù)據(jù)流有n個基本塊，則上述方程有2n個。3)可通過聯(lián)立方程組求得各基本塊的INL[B]和OUTL[B]。算法6.5求解活躍變量數(shù)據(jù)流方程(6.3)-(6.4)的迭代算法p160(Succ[Bi]代表Bi的所有后繼基本塊集合)例6.6

求出程序流圖6-6的各基本塊的OUTL集和INL集。6.3.5定值-引用鏈對于變量A的定值點P，從P出發(fā)能到達的全部A的引用點所組成的集合，稱為A在定值點P的定值-引用鏈（簡稱為du鏈）。顯然，求變量A在其定值點的du鏈的問題，恰好是求變量A在其引用點的ud鏈的逆問題。6.4循環(huán)優(yōu)化本節(jié)內(nèi)容

一.循環(huán)優(yōu)化概述二.代碼外提三.強度削弱四.刪除歸納變量

循環(huán)優(yōu)化概述循環(huán)中存儲空間變化一般不大因為循環(huán)中代碼可能要反復(fù)執(zhí)行，所以，進行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大的作用。（尤其要注意優(yōu)化內(nèi)層循環(huán)）循環(huán)就是程序中那些可能反復(fù)執(zhí)行的代碼序列。1.概念在程序流圖中，循環(huán)為：1.有唯一的入口結(jié)點，從循環(huán)外到循環(huán)內(nèi)任何結(jié)點的所有通路，都必通過此入口結(jié)點。2.組內(nèi)的結(jié)點是強連通的。即從組內(nèi)的任一結(jié)點出發(fā)，都能到達組中任一的結(jié)點。特別是，當(dāng)組內(nèi)僅含一個結(jié)點時，必有從此結(jié)點到其自身的有向邊。此性質(zhì)說明，如果一組結(jié)點不是強連通的，則至少其中存在一部分結(jié)點不能被重復(fù)地執(zhí)行。循環(huán)優(yōu)化方法可以對循環(huán)代碼實行優(yōu)化：代碼外提、強度削弱、刪除歸納變量。循環(huán)中的某些代碼，其運算的結(jié)果往往是不變的。對于這種不變運算，我們可以把它外提到循環(huán)外。這樣，程序的運行結(jié)果仍保持不變，但程序的運行速度卻提高了。我們稱這種優(yōu)化為代碼外提。一.代碼外提代碼外提需解決如下三個問題：1.如何識別循環(huán)中的不變運算代碼？2.把循環(huán)中的不變運算代碼提到循環(huán)外的什么地方？3.何種循環(huán)不變運算代碼可以外提，而且不會給整個程序的執(zhí)行帶來副作用？或者說在什么條件下才能實現(xiàn)代碼外提？1.如何識別循環(huán)中的不變運算代碼？根據(jù)循環(huán)L中的每個變量在其各引用點的ud鏈，便可確定能到達這些引用點相應(yīng)變量的定值點是否在L之外。2外提到哪里？？循環(huán)前置結(jié)點2.循環(huán)的前置結(jié)點前置結(jié)點的構(gòu)造：1新結(jié)點在循環(huán)入口結(jié)點前面建立一個新結(jié)點(基本塊)，稱為循環(huán)的前置結(jié)點入口結(jié)點循環(huán)L前置結(jié)點2輸出循環(huán)前置結(jié)點以循環(huán)入口結(jié)點為其唯一后繼3輸入

原來流圖中從循環(huán)外引到循環(huán)入口結(jié)點的有向邊，改成引到循環(huán)前置結(jié)點3.例一左圖B3中I:=2是循環(huán)不變運算，能否將其外提（如右圖所示）呢？？當(dāng)X=30Y=25時I=1I=2代碼外提后程序結(jié)果發(fā)生改變，故此時不能外提X所謂出口結(jié)點，是指循環(huán)中從該結(jié)點有一有向邊引到循環(huán)外的某結(jié)點。此處即為B4錯誤原因分析：B3不是此循環(huán)的必經(jīng)結(jié)點（左圖），而將I:=2外提后，將其從非必經(jīng)結(jié)點放入了必經(jīng)結(jié)點（右圖），故程序結(jié)果有所不同解決方法：當(dāng)把一不變運算外提到循環(huán)前置結(jié)點時，要求該不變運算所在的結(jié)點是循環(huán)所有出口結(jié)點的必經(jīng)結(jié)點。4.例二右圖B4中I:=2能否外提？I:=1B1ifX<YgotoB3B2A:=I+1X:=X+1B3

I:=2Y:=Y-1ifY<=0gotoB5B4J:=AB5I:=2當(dāng)X=0Y=2時，執(zhí)行順序為B2B3B4B2B4B5原始結(jié)果J=2外提后結(jié)果J=3I:=1B1ifX<YgotoB3B2A:=I+1X:=X+1B3

Y:=Y-1ifY<=0gotoB5B4J:=AB5I:=2B2’I:=2原始流圖如右圖所示代碼外提后流圖如右圖所示原因分析：外提前A賦值時I的定值為B1中的I:=1，且循環(huán)中的I:=2定值不能到達A的定值點故A最終值為2外提后A賦值時I的定值為B2’中的I:=2，故A最終值為3解決方法：當(dāng)把循環(huán)不變運算A：=BopC外提時，要求循環(huán)中A的所有引用點都是而且僅僅是這個定值所能到達的。依次查看L中各基本塊的每個代碼，如果它的每個運算對象5.查找循環(huán)L的不變運算的算法或為常數(shù)或者定值點在L外則將此代碼標(biāo)記為“不變運算”。(以上兩點根據(jù)數(shù)據(jù)流分析可知)重復(fù)第(3)步直至沒有新的代碼被標(biāo)記為“不變運算”為止。依次查看尚未被標(biāo)記為“不變運算”的代碼，如果它的每個運算對象或為常數(shù)或者定值點在L外則將此代碼標(biāo)記為“不變運算”或只有一個到達一定值點且該點上的代碼已標(biāo)記為“不變運算”(1)不變運算的初始標(biāo)記(2)循環(huán)(3)不變運算的傳播6.

代碼外提示例(2)ifI>10goto(15)B2(15)...B3(3)T1:=2*J(4)T2:=10*I(5)T3:=T2+T1(6)T4:=addr(A)-11(7)T5:=2*J(8)T6:=10*I(9)T7:=T6+T5(10)T8:=ddr(A)-11(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=ddr(A)-11查找不變運算J的定值點在循環(huán)外邊addr(A)的定值點在循環(huán)外邊代碼外提B2’(2)ifI>10goto(15)B2(15)...B3(4)T2:=10*I(5)T3:=T2+T1(8)T6:=10*I(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=ddr(A)-11B2’強度削弱可以強度削弱是指把程序中執(zhí)行時間較長的運算替換為執(zhí)行時間較短的運算。（即將復(fù)雜（高階）運算用“遞歸+低階運算”代替）二.強度削弱對乘法運算使用變址器對加法運算2.強度削弱示例--對乘法運算(2)ifI>10goto(15)B2(15)...(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=ddr(A)-11B2’B3中I是遞歸賦值變量，每循環(huán)一次其值增加1B3中T2是I的線性函數(shù)，每循環(huán)一次其值增加10故可將(4)提到B2’中，并在(13)后增加代碼給T2加常量10，如此程序運行結(jié)果保持不變(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=addr(A)-11B2’(4)T2:=10*IB3(5)T3:=T2+T1(8)T6:=10*I(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2B3(4)T2:=10*I(5)T3:=T2+T1(8)T6:=10*I(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2B3(4’)T2:=T2+10(5)T3:=T2+T1(8)T6:=10*I(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2同理，可將(8)提到B2’中，并在(4’)后增加代碼給T6加常量10，如此程序運行結(jié)果保持不變(5)T3:=T2+T1B3(4’)T2:=T2+10(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=addr(A)-11B2’(4)T2:=10*I(8)T6:=10*IB3(4’)T2:=T2+10(9)T7:=T6+T5(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2(5)T3:=T2+T1(8’)T6:=T6+10(4)T2:=10*I(4’)T2:=T2+10(8)T6:=10*I(8)T6:=10*I如此即對原程序中的乘法運算(4)、(8)進行了強度削弱(8’)T6:=T6+10(13)I:=I+1(4)T2:=10*I(4)T2:=10*I基本歸納變量的作用：如果循環(huán)中對變量I只有唯一的形如I：=I±C的賦值，且其中C為循環(huán)不變量，則稱I為循環(huán)中的基本歸納變量。三.刪除歸納變量用于其自身的遞歸定值在循環(huán)中用來計算其它歸納變量用來控制循環(huán)的進行歸納變量的確定——找與基本歸納變量存在的線性關(guān)系如果I是循環(huán)中一基本歸納變量，J在循環(huán)中的定值總是可化歸為I的同一線性函數(shù)，也即J=C1*I±C2，其中C1和C2都是循環(huán)不變量，則稱J是歸納變量，并稱它與I同族。2.歸納變量(15)...(2)ifI>10goto(15)B2(9)T7:=T6+T5(3)T1:=2*J(6)T4:=addr(A)-11(7)T5:=2*J(10)T8:=ddr(A)-11B2’(4)T2:=10*I(8)T6:=10*I(5)T3:=T2+T1B3(4’)T2:=T2+10(11)T9:=T8[T7](12)T4[T3]:=T9+1(13)I:=I+1(14)gotoB2(5’)T3:=T3+10(8’)T6:=T6+10(9’)T7:=T7+103.示例由B3中(13)可以看出，I是循環(huán)的基本歸納變量由B2