譯原理課件第8章-優(yōu)化

第八章代碼優(yōu)化8.1什么是代碼優(yōu)化8.2局部?jī)?yōu)化8.3循環(huán)優(yōu)化8.4數(shù)據(jù)流分析第八章代碼優(yōu)化8.1什么是代碼優(yōu)化22022/12/238.1什么是代碼優(yōu)化1、優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使變換后的程序能生成更有效的目標(biāo)代碼。優(yōu)化可在編譯的任何階段進(jìn)行，但最主要的一類優(yōu)化是對(duì)中間代碼進(jìn)行優(yōu)化。2、常見(jiàn)的優(yōu)化方式①刪除多余運(yùn)算（又稱刪除公共子表達(dá)式）②代碼外提：循環(huán)體中不變的運(yùn)算提到循環(huán)體外③強(qiáng)度削弱：把乘法變成加法22022/12/198.1什么是代碼優(yōu)化1、優(yōu)化：32022/12/23④變換循環(huán)控制條件：目的是刪除那些純粹為控制循環(huán)而設(shè)立的語(yǔ)句，因此又稱刪除歸納變量。⑤合并已知量：對(duì)于那些編譯時(shí)便可靜態(tài)確定的運(yùn)算結(jié)果事先運(yùn)算出來(lái)，不必等到運(yùn)行程序時(shí)再執(zhí)行。⑥復(fù)寫傳播：某些變量的值并未被改變，便賦給其他變量，則可直接引用原值本身。⑦刪除無(wú)用賦值：有些變量在賦值后并未引用，卻又被重新賦值了，稱為無(wú)用賦值（前面的賦值）32022/12/19④變換循環(huán)控制條件：目的是刪除那些42022/12/233、優(yōu)化分類按階段分:

與機(jī)器無(wú)關(guān)的優(yōu)化---對(duì)中間代碼進(jìn)行依賴于機(jī)器的優(yōu)化--對(duì)目標(biāo)代碼進(jìn)行根據(jù)優(yōu)化所涉及的程序范圍分成:(1)局部?jī)?yōu)化:在程序基本塊內(nèi)進(jìn)行的優(yōu)化。

(2)循環(huán)優(yōu)化:在程序循環(huán)體內(nèi)進(jìn)行的優(yōu)化。

(3)全局優(yōu)化:在整個(gè)程序范圍內(nèi)進(jìn)行的優(yōu)化。優(yōu)化工作數(shù)據(jù)流分析(control-flowanalysis)

控制流分析(data-flowanalysis)變換(transformations)42022/12/193、優(yōu)化分類按階段分:52022/12/234、優(yōu)化技術(shù)簡(jiǎn)介

1.刪除多余運(yùn)算

2.循環(huán)不變代碼外提

3.強(qiáng)度削弱

4.變換循環(huán)控制條件

5.合并已知量與復(fù)寫傳播

6.刪除無(wú)用賦值例：

P:=0forI:=1to20doP:=P+A[I]*B[I]52022/12/194、優(yōu)化技術(shù)簡(jiǎn)介62022/12/23(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)(1)P:=0(2)I:=1(3)T1:=4*I(5)T3:=T2[T1](8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T162022/12/19(1)P:=0(1)P:=0(4)T272022/12/23(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)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(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(5)(3)T1:=4*I(3‘)T1:=T1+472022/12/19(1)P:=0(1)P:=0(3)T182022/12/23(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)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)if<=80goto(5)(3)T1:=4T1T182022/12/19(1)P:=0(1)P:=0(3)T192022/12/23(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)(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1<=80goto(5)92022/12/19(1)P:=0(1)P:=0102022/12/23對(duì)程序以基本塊為范圍來(lái)討論的優(yōu)化，稱為局部?jī)?yōu)化?；緣K：指程序中一順序執(zhí)行的語(yǔ)句序列，它只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句?；緣K的入口語(yǔ)句：

1.程序的第一個(gè)語(yǔ)句；或者，

2.條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句的轉(zhuǎn)移目標(biāo)語(yǔ)句；或者

3.緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。8.2局部?jī)?yōu)化：基本塊內(nèi)的優(yōu)化102022/12/19對(duì)程序以基本塊為范圍來(lái)討論的優(yōu)化，稱112022/12/23基本塊的劃分1、求基本塊入口語(yǔ)句2、尋找基本塊⑴從入口語(yǔ)句到下一入口語(yǔ)句（不包括該入口）；⑵從入口語(yǔ)句到下一轉(zhuǎn)移語(yǔ)句（包括轉(zhuǎn)移語(yǔ)句）；⑶從入口語(yǔ)句到下一停止語(yǔ)句（包括該停止語(yǔ)句）。3、基本塊的整理程序中所有基本塊之外的語(yǔ)句為無(wú)用語(yǔ)句，應(yīng)刪除?；緣K優(yōu)化在一個(gè)基本塊內(nèi)通常可實(shí)行三種優(yōu)化：合并已知量、刪除無(wú)用賦值（難判斷）以及刪除多余運(yùn)算。112022/12/19基本塊的劃分122022/12/23例：

(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)halt122022/12/19例：132022/12/23132022/12/19142022/12/23

基本塊的DAG表示及其應(yīng)用

DAGDirectedAcyclicGraph

無(wú)環(huán)路有向圖基本塊的DAG是在結(jié)點(diǎn)上帶有標(biāo)記的DAG

葉結(jié)點(diǎn)獨(dú)特的標(biāo)識(shí)符(名字,常數(shù))標(biāo)記內(nèi)部結(jié)點(diǎn)運(yùn)算符號(hào)標(biāo)記各個(gè)結(jié)點(diǎn)附加標(biāo)識(shí)符標(biāo)記142022/12/19

基本塊的DAG表示及其應(yīng)用

DAG152022/12/23用DAG進(jìn)行基本塊的優(yōu)化四元式DAG結(jié)點(diǎn)0型：A:=B(:=,B,—,A)n1

AB1型:A:=opB(op,B,

—,A)

n2Aopn1B2型:A:=BopC(op,B,C,A)n3Aop

n1n2BCn1n2n1n3n1n2152022/12/19用DAG進(jìn)行基本塊的優(yōu)化四元式DAG162022/12/23162022/12/19172022/12/23172022/12/19182022/12/23182022/12/19192022/12/23例：192022/12/19例：202022/12/23202022/12/19212022/12/23212022/12/19222022/12/23222022/12/19232022/12/23232022/12/19242022/12/23242022/12/19252022/12/23252022/12/19262022/12/23262022/12/19272022/12/23272022/12/19282022/12/23282022/12/19292022/12/23控制流程圖（流圖）：具有唯一首結(jié)點(diǎn)的有向圖G=（N，E，n0）N：結(jié)點(diǎn)集

基本塊集E：有向邊集

n0：首結(jié)點(diǎn)

包含程序第一個(gè)

語(yǔ)句的基本塊8.3循環(huán)優(yōu)化292022/12/19控制流程圖（流圖）：具有唯一首結(jié)點(diǎn)的302022/12/23302022/12/192022/12/232022/12/19322022/12/23322022/12/19332022/12/23332022/12/19342022/12/23分析程序流圖中結(jié)點(diǎn)間的關(guān)系mDOMn定義在程序流圖中,對(duì)任意兩個(gè)結(jié)點(diǎn)m和n,如果從流圖的首結(jié)點(diǎn)出發(fā),到達(dá)n的任意通路都要經(jīng)過(guò)m,則稱m是n的必經(jīng)結(jié)點(diǎn),記為mDOMn(a,aMODa)必經(jīng)結(jié)點(diǎn)集定義結(jié)點(diǎn)n的所有必經(jīng)結(jié)點(diǎn)的集合,稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集,記為D(n).342022/12/19分析程序流圖中結(jié)點(diǎn)間的關(guān)系352022/12/23例:

6734

1235761212121必經(jīng)結(jié)點(diǎn)

必經(jīng)結(jié)點(diǎn)集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}3352022/12/19例:673412362022/12/23循環(huán)的查找循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。有向邊n→d是回邊，組成的循環(huán)是由結(jié)點(diǎn)d，結(jié)點(diǎn)n以及有通路到達(dá)n而該通路不經(jīng)過(guò)d的所有結(jié)點(diǎn)組成，并且d是該循環(huán)的唯一入口結(jié)點(diǎn)。循環(huán)(結(jié)點(diǎn)序列的性質(zhì))1.強(qiáng)連通的(任意兩結(jié)點(diǎn)間,必有一條通路,且該通路上各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列)2.它們中間有且只有一個(gè)是入口結(jié)點(diǎn).362022/12/19循環(huán)的查找循環(huán)的查找算法回邊：假設(shè)a372022/12/238.4數(shù)據(jù)流分析1.活躍變量數(shù)據(jù)流方程2.到達(dá)--定值數(shù)據(jù)流方程3.討論數(shù)據(jù)流問(wèn)題分類路徑數(shù)據(jù)流方程解不唯一372022/12/198.4數(shù)據(jù)流分析1.活躍變量數(shù)382022/12/23活躍變量的數(shù)據(jù)流分析所謂活躍變量就是它的當(dāng)前值還將被引用（在賦予一個(gè)新值之前）。在全局范圍來(lái)分析的話，一個(gè)變量是活躍的，如果存在一條路徑使得該變量被重新定值之前它的當(dāng)前值還要被引用。通過(guò)全局活躍變量分析，識(shí)別出其當(dāng)前值不再活躍（即，它的值已經(jīng)死了）的那些變量。死變量的值在基本塊的出口處不需要保存。382022/12/19活躍變量的數(shù)據(jù)流分析所謂活躍變量就是392022/12/23令B為一個(gè)基本塊，定義LiveIn(B)為在基本塊B入口處為活躍的變量的集合。定義LiveOut(B)為基本塊B的出口處的活躍變量的集合。LiveIn和LiveOut并不是相互獨(dú)立的，令S（B）為流圖中基本塊B的后繼的集合，則有LiveOut(B)=∪LiveIn(i)i∈s(B)

如果基本塊沒(méi)有后繼，則其LiveOut為空令LiveUse(B)為B中被定值之前要引用變量的集合。這個(gè)集合由基本塊B中的語(yǔ)句唯一確定。容易看出，如果v∈LiveUse(B)，則v∈LiveIn(B)；即LiveIn(B)LiveUse(B)。令Def(B)為在B中定值的變量集合。如果一個(gè)變量在基本塊B的出口處為活躍的且vDef(B)，則它在B的入口處也是活躍的，即：LiveIn(B)LiveOut(B)-Def(B)因此有：LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))即：一個(gè)變量在基本塊入口處為活躍的，則一定有：或者它在基本塊的LiveUse集中，或者它在基本塊的出口處為活躍的且在基本塊中沒(méi)有重新定值

392022/12/19令B為一個(gè)基本塊，402022/12/23a:=1;ifa=bthenb:=1elsec:=1endif;d:=a+ba:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4402022/12/19a:=1;a:=1b:=1c:=1d412022/12/23提取Def和LiveUse集合基本塊DefLiveUseB1{a}B2?B3{c}?B4i20k8w4{a,b}a:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4412022/12/19提取Def和LiveUse集合基本塊422022/12/23從最后一個(gè)基本塊開始由后往前計(jì)算，可以得到一定的解

LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))

LiveOut(B)=∪LiveIn(i)i∈s(B)LiveOut(B4)=?，因此：LiveIn(B4)=LiveUse(B4)={a,b}-c4i6co2現(xiàn)在LiveOut(B2)=LiveIn(B4)={a,b}-c4a4iwoLiveOut(B3)=LiveIn(B4)={a,b}-muukomyLiveIn(B2)=LiveOut(B2)-Def(B2)={a,b}--iwuu04u={a}-acoay4yLiveIn(B3)=LiveOut(B3)-Def(B3)={a,b}–{c}-u04qiky={a,b}–{c}-ow2uu42LiveOut(B1)=LiveIn(B2)∪LiveIn(B3)={a}∪{a,b}-84s6kik={a,b}-yg4oeck–{c}最后LiveIn(B1)=LiveUse(B1)∪(LiveOut(B1)-Def(B1))=∪({a,b}–{c}-aiao02g–{a})=-umcqiui–{c}

a:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4422022/12/19從最后一個(gè)基本塊開始由后往前計(jì)算，可432022/12/23分析程序中所有變量的定值和引用之間的關(guān)系到達(dá)--定值數(shù)據(jù)流方程OUT[B]=(IN[B]-KILL[B])GEN[B]IN[B]=OUT[p]pP[B]P[B]:B的所有前驅(qū)基本塊GEN[B]:B中定值并到達(dá)B出口之后的所有定值點(diǎn)集.KILL[B]:B之外的那些定值點(diǎn)集,其定值的變量在B中又重新定值.IN[B]:到B入口之前(緊)的各變量的所有定值點(diǎn)集OUT[B]:到達(dá)B出口之后(緊)各變量的所有定值點(diǎn)集.432022/12/19分析程序中所有變量的定值和引用之間的442022/12/23442022/12/19452022/12/23GEN位向量KILLB1{d1,d2}11000000011100B2{d3}00100001000000B3{d4}00010000100100B4{d5}00001000101000B5{}00000000000000IN[B]OUT[B]B101111001100000B211111000111100B301111000011000B400110000010100B500111000011100452022/12/19GEN位向量KILLB1{d1,d2462022/12/23462022/12/19472022/12/23472022/12/19482022/12/23

入口結(jié)點(diǎn)

??

循環(huán)L??

前置結(jié)點(diǎn)入口結(jié)點(diǎn)

???

循環(huán)L?482022/12/19492022/12/23492022/12/19502022/12/2312345502022/12/1912345512022/12/23512022/12/19522022/12/23B1B2B3

B4B5(1)I:=1I:=3;(2)ifx<ygoto(3)(3)I:=2(4)x:=x+1(5)y:=y-1(6)ify<=20

gotoB2(7)J:=I522022/12/19532022/12/23B1B2B3

B4B5(1)I:=1(2)ifx<ygoto(3)(3)I:=2(4)x:=x+1(5)k:=I;y:=y-1(6)ify<=20

gotoB2(7)J:=I532022/12/19542022/12/23當(dāng)把循環(huán)中的不變運(yùn)算s:A:=BopC外提時(shí)注意：（2）

要求循環(huán)中其它地方不再有A的定值點(diǎn)。（3）

要求循環(huán)中A的所有引用點(diǎn)都是而且僅僅是這個(gè)定值所能達(dá)到的（1）要求s所在結(jié)點(diǎn)是循環(huán)的所有出口結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)（4）要求A在離開循環(huán)之后不再是活躍的542022/12/19當(dāng)把循環(huán)中的不變運(yùn)算s:A:=Bo552022/12/23中南大學(xué)軟件學(xué)院陳志剛數(shù)據(jù)流問(wèn)題的討論合流問(wèn)題向前流（forward-flow)(信息流的方向與控制流是一致的)和向后流（backward–flow）對(duì)每個(gè)基本塊有一個(gè)IN集合和一個(gè)Out集合,在同一基本塊中，In和Out集合的關(guān)系對(duì)于向前流問(wèn)題：Out(B)=Used(B)∪(In(B)–Killed(B))對(duì)于向后流問(wèn)題：In(B)=Used(B)∪(Out(B)–Killed(B))作為一個(gè)邊界條件，向前流問(wèn)題中的起始基本塊的In和向后流問(wèn)題中最后一個(gè)基本塊的Out集合必須指明，通常，這些邊界條件集或者為空，或者包含所有可能的值，因問(wèn)題而定。如：到達(dá)--定值數(shù)據(jù)流方程

OUT[B]=(IN[B]-KILL[B])GEN[B]活躍變量數(shù)據(jù)流方程LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))552022/12/19中南大學(xué)軟件學(xué)院陳志剛數(shù)據(jù)流問(wèn)題562022/12/23數(shù)據(jù)流問(wèn)題的討論路徑問(wèn)題任意路徑數(shù)據(jù)流分析討論的數(shù)據(jù)流假定這么一個(gè)性質(zhì)，即某條路徑為真，（如果存在某條路徑上被引用這個(gè)變量就認(rèn)為是活躍的；如果存在任何一條路徑上被定值，則就認(rèn)為這個(gè)變量是被定值的）。這種數(shù)據(jù)流問(wèn)題被稱為任意路徑問(wèn)題。任意路徑問(wèn)題的解不能保證所需的性質(zhì)一定會(huì)滿足，僅僅是可能滿足。全路徑數(shù)據(jù)流分析數(shù)據(jù)流問(wèn)題也可以用全路徑（all-path）形式來(lái)解決，使所需的性質(zhì)在所有可能的路徑都滿足。對(duì)于全路徑問(wèn)題的解，所需的性質(zhì)可以保證總是滿足。

562022/12/19數(shù)據(jù)流問(wèn)題的討論路徑問(wèn)題任意路徑數(shù)據(jù)572022/12/23數(shù)據(jù)流問(wèn)題的解不一定唯一考察圖10.20的流圖，其中有一個(gè)簡(jiǎn)單的循環(huán)。在這個(gè)流圖中，沒(méi)有對(duì)任何變量定值，a在B4中被引用。應(yīng)用向后流方法傳播可以得到一個(gè)最明顯的解，即四個(gè)基本塊的LiveIn集合均為{a}。但是，不太合理的解也是可能的。。572022/12/19數(shù)據(jù)流問(wèn)題的解不一定唯一考察圖10.582022/12/23若Def(B1)=

Def(B2)=

Def(B3)=

Def(B4)=Liveuse(B1)=Liveuse(B1)=Liveuse(B1)=Liveuse(B1)={a}則最明顯的解：LiveIn(B1)=LiveIn(B1)=LiveIn(B1)=LiveIn(B1)={a}B1B2B3B4582022/12/19若B1B2B3B4592022/12/23例如，下面解是滿足數(shù)據(jù)流方程的：基本塊LiveInLiveOutB1{a,b}{a,b}B2{a,b}{a,b}B3{a,b}{a,b}B4{a}?注意b沒(méi)有在任何基本塊中被引用！問(wèn)題所在是基本塊B2和B3互為祖先；而且，因?yàn)閎從未定值（所有Def集為空），一旦b被包括在LiveIn集合中，它就永遠(yuǎn)消除不了592022/12/19例如，下面解是滿足數(shù)據(jù)流方程的：基本第八章代碼優(yōu)化8.1什么是代碼優(yōu)化8.2局部?jī)?yōu)化8.3循環(huán)優(yōu)化8.4數(shù)據(jù)流分析第八章代碼優(yōu)化8.1什么是代碼優(yōu)化612022/12/238.1什么是代碼優(yōu)化1、優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使變換后的程序能生成更有效的目標(biāo)代碼。優(yōu)化可在編譯的任何階段進(jìn)行，但最主要的一類優(yōu)化是對(duì)中間代碼進(jìn)行優(yōu)化。2、常見(jiàn)的優(yōu)化方式①刪除多余運(yùn)算（又稱刪除公共子表達(dá)式）②代碼外提：循環(huán)體中不變的運(yùn)算提到循環(huán)體外③強(qiáng)度削弱：把乘法變成加法22022/12/198.1什么是代碼優(yōu)化1、優(yōu)化：622022/12/23④變換循環(huán)控制條件：目的是刪除那些純粹為控制循環(huán)而設(shè)立的語(yǔ)句，因此又稱刪除歸納變量。⑤合并已知量：對(duì)于那些編譯時(shí)便可靜態(tài)確定的運(yùn)算結(jié)果事先運(yùn)算出來(lái)，不必等到運(yùn)行程序時(shí)再執(zhí)行。⑥復(fù)寫傳播：某些變量的值并未被改變，便賦給其他變量，則可直接引用原值本身。⑦刪除無(wú)用賦值：有些變量在賦值后并未引用，卻又被重新賦值了，稱為無(wú)用賦值（前面的賦值）32022/12/19④變換循環(huán)控制條件：目的是刪除那些632022/12/233、優(yōu)化分類按階段分:

與機(jī)器無(wú)關(guān)的優(yōu)化---對(duì)中間代碼進(jìn)行依賴于機(jī)器的優(yōu)化--對(duì)目標(biāo)代碼進(jìn)行根據(jù)優(yōu)化所涉及的程序范圍分成:(1)局部?jī)?yōu)化:在程序基本塊內(nèi)進(jìn)行的優(yōu)化。

(2)循環(huán)優(yōu)化:在程序循環(huán)體內(nèi)進(jìn)行的優(yōu)化。

(3)全局優(yōu)化:在整個(gè)程序范圍內(nèi)進(jìn)行的優(yōu)化。優(yōu)化工作數(shù)據(jù)流分析(control-flowanalysis)

控制流分析(data-flowanalysis)變換(transformations)42022/12/193、優(yōu)化分類按階段分:642022/12/234、優(yōu)化技術(shù)簡(jiǎn)介

1.刪除多余運(yùn)算

2.循環(huán)不變代碼外提

3.強(qiáng)度削弱

4.變換循環(huán)控制條件

5.合并已知量與復(fù)寫傳播

6.刪除無(wú)用賦值例：

P:=0forI:=1to20doP:=P+A[I]*B[I]52022/12/194、優(yōu)化技術(shù)簡(jiǎn)介652022/12/23(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)(1)P:=0(2)I:=1(3)T1:=4*I(5)T3:=T2[T1](8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T162022/12/19(1)P:=0(1)P:=0(4)T2662022/12/23(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)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(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(5)(3)T1:=4*I(3‘)T1:=T1+472022/12/19(1)P:=0(1)P:=0(3)T1672022/12/23(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)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)if<=80goto(5)(3)T1:=4T1T182022/12/19(1)P:=0(1)P:=0(3)T1682022/12/23(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)(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1<=80goto(5)92022/12/19(1)P:=0(1)P:=0692022/12/23對(duì)程序以基本塊為范圍來(lái)討論的優(yōu)化，稱為局部?jī)?yōu)化?；緣K：指程序中一順序執(zhí)行的語(yǔ)句序列，它只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句。基本塊的入口語(yǔ)句：

1.程序的第一個(gè)語(yǔ)句；或者，

2.條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句的轉(zhuǎn)移目標(biāo)語(yǔ)句；或者

3.緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。8.2局部?jī)?yōu)化：基本塊內(nèi)的優(yōu)化102022/12/19對(duì)程序以基本塊為范圍來(lái)討論的優(yōu)化，稱702022/12/23基本塊的劃分1、求基本塊入口語(yǔ)句2、尋找基本塊⑴從入口語(yǔ)句到下一入口語(yǔ)句（不包括該入口）；⑵從入口語(yǔ)句到下一轉(zhuǎn)移語(yǔ)句（包括轉(zhuǎn)移語(yǔ)句）；⑶從入口語(yǔ)句到下一停止語(yǔ)句（包括該停止語(yǔ)句）。3、基本塊的整理程序中所有基本塊之外的語(yǔ)句為無(wú)用語(yǔ)句，應(yīng)刪除。基本塊優(yōu)化在一個(gè)基本塊內(nèi)通?？蓪?shí)行三種優(yōu)化：合并已知量、刪除無(wú)用賦值（難判斷）以及刪除多余運(yùn)算。112022/12/19基本塊的劃分712022/12/23例：

(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)halt122022/12/19例：722022/12/23132022/12/19732022/12/23

基本塊的DAG表示及其應(yīng)用

DAGDirectedAcyclicGraph

無(wú)環(huán)路有向圖基本塊的DAG是在結(jié)點(diǎn)上帶有標(biāo)記的DAG

葉結(jié)點(diǎn)獨(dú)特的標(biāo)識(shí)符(名字,常數(shù))標(biāo)記內(nèi)部結(jié)點(diǎn)運(yùn)算符號(hào)標(biāo)記各個(gè)結(jié)點(diǎn)附加標(biāo)識(shí)符標(biāo)記142022/12/19

基本塊的DAG表示及其應(yīng)用

DAG742022/12/23用DAG進(jìn)行基本塊的優(yōu)化四元式DAG結(jié)點(diǎn)0型：A:=B(:=,B,—,A)n1

AB1型:A:=opB(op,B,

—,A)

n2Aopn1B2型:A:=BopC(op,B,C,A)n3Aop

n1n2BCn1n2n1n3n1n2152022/12/19用DAG進(jìn)行基本塊的優(yōu)化四元式DAG752022/12/23162022/12/19762022/12/23172022/12/19772022/12/23182022/12/19782022/12/23例：192022/12/19例：792022/12/23202022/12/19802022/12/23212022/12/19812022/12/23222022/12/19822022/12/23232022/12/19832022/12/23242022/12/19842022/12/23252022/12/19852022/12/23262022/12/19862022/12/23272022/12/19872022/12/23282022/12/19882022/12/23控制流程圖（流圖）：具有唯一首結(jié)點(diǎn)的有向圖G=（N，E，n0）N：結(jié)點(diǎn)集

基本塊集E：有向邊集

n0：首結(jié)點(diǎn)

包含程序第一個(gè)

語(yǔ)句的基本塊8.3循環(huán)優(yōu)化292022/12/19控制流程圖（流圖）：具有唯一首結(jié)點(diǎn)的892022/12/23302022/12/192022/12/232022/12/19912022/12/23322022/12/19922022/12/23332022/12/19932022/12/23分析程序流圖中結(jié)點(diǎn)間的關(guān)系mDOMn定義在程序流圖中,對(duì)任意兩個(gè)結(jié)點(diǎn)m和n,如果從流圖的首結(jié)點(diǎn)出發(fā),到達(dá)n的任意通路都要經(jīng)過(guò)m,則稱m是n的必經(jīng)結(jié)點(diǎn),記為mDOMn(a,aMODa)必經(jīng)結(jié)點(diǎn)集定義結(jié)點(diǎn)n的所有必經(jīng)結(jié)點(diǎn)的集合,稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集,記為D(n).342022/12/19分析程序流圖中結(jié)點(diǎn)間的關(guān)系942022/12/23例:

6734

1235761212121必經(jīng)結(jié)點(diǎn)

必經(jīng)結(jié)點(diǎn)集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}3352022/12/19例:673412952022/12/23循環(huán)的查找循環(huán)的查找算法回邊：假設(shè)a→b是流圖中的一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。有向邊n→d是回邊，組成的循環(huán)是由結(jié)點(diǎn)d，結(jié)點(diǎn)n以及有通路到達(dá)n而該通路不經(jīng)過(guò)d的所有結(jié)點(diǎn)組成，并且d是該循環(huán)的唯一入口結(jié)點(diǎn)。循環(huán)(結(jié)點(diǎn)序列的性質(zhì))1.強(qiáng)連通的(任意兩結(jié)點(diǎn)間,必有一條通路,且該通路上各結(jié)點(diǎn)都屬于該結(jié)點(diǎn)序列)2.它們中間有且只有一個(gè)是入口結(jié)點(diǎn).362022/12/19循環(huán)的查找循環(huán)的查找算法回邊：假設(shè)a962022/12/238.4數(shù)據(jù)流分析1.活躍變量數(shù)據(jù)流方程2.到達(dá)--定值數(shù)據(jù)流方程3.討論數(shù)據(jù)流問(wèn)題分類路徑數(shù)據(jù)流方程解不唯一372022/12/198.4數(shù)據(jù)流分析1.活躍變量數(shù)972022/12/23活躍變量的數(shù)據(jù)流分析所謂活躍變量就是它的當(dāng)前值還將被引用（在賦予一個(gè)新值之前）。在全局范圍來(lái)分析的話，一個(gè)變量是活躍的，如果存在一條路徑使得該變量被重新定值之前它的當(dāng)前值還要被引用。通過(guò)全局活躍變量分析，識(shí)別出其當(dāng)前值不再活躍（即，它的值已經(jīng)死了）的那些變量。死變量的值在基本塊的出口處不需要保存。382022/12/19活躍變量的數(shù)據(jù)流分析所謂活躍變量就是982022/12/23令B為一個(gè)基本塊，定義LiveIn(B)為在基本塊B入口處為活躍的變量的集合。定義LiveOut(B)為基本塊B的出口處的活躍變量的集合。LiveIn和LiveOut并不是相互獨(dú)立的，令S（B）為流圖中基本塊B的后繼的集合，則有LiveOut(B)=∪LiveIn(i)i∈s(B)

如果基本塊沒(méi)有后繼，則其LiveOut為空令LiveUse(B)為B中被定值之前要引用變量的集合。這個(gè)集合由基本塊B中的語(yǔ)句唯一確定。容易看出，如果v∈LiveUse(B)，則v∈LiveIn(B)；即LiveIn(B)LiveUse(B)。令Def(B)為在B中定值的變量集合。如果一個(gè)變量在基本塊B的出口處為活躍的且vDef(B)，則它在B的入口處也是活躍的，即：LiveIn(B)LiveOut(B)-Def(B)因此有：LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))即：一個(gè)變量在基本塊入口處為活躍的，則一定有：或者它在基本塊的LiveUse集中，或者它在基本塊的出口處為活躍的且在基本塊中沒(méi)有重新定值

392022/12/19令B為一個(gè)基本塊，992022/12/23a:=1;ifa=bthenb:=1elsec:=1endif;d:=a+ba:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4402022/12/19a:=1;a:=1b:=1c:=1d1002022/12/23提取Def和LiveUse集合基本塊DefLiveUseB1{a}B2?B3{c}?B4yew6sag{a,b}a:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4412022/12/19提取Def和LiveUse集合基本塊1012022/12/23從最后一個(gè)基本塊開始由后往前計(jì)算，可以得到一定的解

LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))

LiveOut(B)=∪LiveIn(i)i∈s(B)LiveOut(B4)=?，因此：LiveIn(B4)=LiveUse(B4)={a,b}-e2cs8km現(xiàn)在LiveOut(B2)=LiveIn(B4)={a,b}-8uqego0LiveOut(B3)=LiveIn(B4)={a,b}-qsmkma0LiveIn(B2)=LiveOut(B2)-Def(B2)={a,b}--4a0c0y6={a}-q68sem4LiveIn(B3)=LiveOut(B3)-Def(B3)={a,b}–{c}-yu8aces={a,b}–{c}-66egkq0LiveOut(B1)=LiveIn(B2)∪LiveIn(B3)={a}∪{a,b}-6kui666={a,b}-ekm0eew–{c}最后LiveIn(B1)=LiveUse(B1)∪(LiveOut(B1)-Def(B1))=∪({a,b}–{c}-ouyscqo–{a})=-2eugsku–{c}

a:=1ifa=bgotoB2b:=1c:=1d:=a+bB1B2B3B4422022/12/19從最后一個(gè)基本塊開始由后往前計(jì)算，可1022022/12/23分析程序中所有變量的定值和引用之間的關(guān)系到達(dá)--定值數(shù)據(jù)流方程OUT[B]=(IN[B]-KILL[B])GEN[B]IN[B]=OUT[p]pP[B]P[B]:B的所有前驅(qū)基本塊GEN[B]:B中定值并到達(dá)B出口之后的所有定值點(diǎn)集.KILL[B]:B之外的那些定值點(diǎn)集,其定值的變量在B中又重新定值.IN[B]:到B入口之前(緊)的各變量的所有定值點(diǎn)集OUT[B]:到達(dá)B出口之后(緊)各變量的所有定值點(diǎn)集.432022/12/19分析程序中所有變量的定值和引用之間的1032022/12/23442022/12/191042022/12/23GEN位向量KILLB1{d1,d2}11000000011100B2{d3}00100001000000B3{d4}00010000100100B4{d5}00001000101000B5{}00000000000000IN[B]OUT[B]B101111001100000B211111000111100B301111000011000B400110000010100B500111000011100452022/12/19GEN位向量KILLB1{d1,d21052022/12/23462022/12/191062022/12/23472022/12/191072022/12/23

入口結(jié)點(diǎn)

??

循環(huán)L??

前置結(jié)點(diǎn)入口結(jié)點(diǎn)

???

循環(huán)L?482022/12/191082022/12/23492022/12/191092022/12/2312345502022/12/19123451102022/12/23512022/12/191112022/12/23B1B2B3