編譯方法、技術(shù)與實踐課件：目標(biāo)代碼生成

目標(biāo)代碼生成?代碼生成概要?指令集架構(gòu)?基本塊與流圖?指令選擇算法?寄存器分配算法?窺孔優(yōu)化?代碼生成器構(gòu)建提綱?根據(jù)中間表示生成代碼?代碼生成器之前可能有一個優(yōu)化組件?代碼生成器的三個主要任務(wù)–指令選擇：選擇適當(dāng)?shù)闹噶顚崿F(xiàn)IR語句–

寄存器分配和指派：把哪個值放在哪個寄存器中–指令排序：按照什么順序安排指令執(zhí)行代碼生成器的位置?正確性、易于實現(xiàn)、測試和維護(hù)?輸入IR的選擇O

四元式、三元式、字節(jié)代碼、堆棧機(jī)代碼、后綴表示、抽象語法樹、DAG、…?目標(biāo)程序O

RISC、CISC、可重定向代碼、匯編語言、堆棧機(jī)?指令選擇O

影響因素：IR層次、指令集特性、目標(biāo)代碼質(zhì)量?寄存器分配和指派?求值順序代碼生成器中的問題?代碼生成概要?指令集架構(gòu)?基本塊與流圖?指令選擇算法?寄存器分配算法?窺孔優(yōu)化?代碼生成器構(gòu)建提綱?三地址機(jī)器的模型目標(biāo)語言?三地址機(jī)器的模型?指令集O

加載：LD

dst,addr?把地址addr中的內(nèi)容加載到dst所指寄存器O保存：ST

x,r?把寄存器r中的內(nèi)容保存到x中目標(biāo)語言?三地址機(jī)器的模型?指令集O加載：LDdst,addr?把地址addr中的內(nèi)容加載到dst所指寄存器O保存：ST

x,r?把寄存器r中的內(nèi)容保存到x中O計算：OPdst,src1,src2?把src1和scr2中的值運(yùn)算后將結(jié)果存放到dst中O無條件跳轉(zhuǎn)：BR

L?控制流轉(zhuǎn)向標(biāo)號L的指令O條件跳轉(zhuǎn)：Bcond

r,L?對r中的值進(jìn)行測試，如果為真則轉(zhuǎn)向L目標(biāo)語言?代碼生成概要?指令集架構(gòu)?基本塊與流圖?指令選擇算法?寄存器分配算法?窺孔優(yōu)化?代碼生成器構(gòu)建提綱?中間代碼的流圖表示法O

中間代碼劃分成為基本塊(basic

block)?控制流只能從第一個指令進(jìn)入?除基本塊的最后一個指令外，控制流不會跳轉(zhuǎn)/停機(jī)O

結(jié)點：基本塊O

邊：指明了基本塊的執(zhí)行順序?流圖可以作為優(yōu)化的基礎(chǔ)O

指出了基本塊之間的控制流O

可以根據(jù)流圖了解到一個值是否會被使用等信息基本塊和流圖?輸入：三地址指令序列?輸出：基本塊的列表?方法：O

確定基本塊的首指令?第一個三地址指令?任意一個條件或無條件轉(zhuǎn)移指令的目標(biāo)指令?緊跟在一個條件/無條件轉(zhuǎn)移指令之后的指令O

確定基本塊?每個首指令對應(yīng)于一個基本塊：從首指令開始到下一

個首指令劃分基本塊的算法?第一個指令O

1?跳轉(zhuǎn)指令的目標(biāo)O

3、2、13?跳轉(zhuǎn)指令的下一條指令O

10、12?基本塊：O

1-1；2-2；3-9；10-11；O

12-12；13-17基本塊劃分的例子(1)b=

1(2)n=10(3)d=l+n(4)c=2(5)t1=4

*a(6)t2=l+

n(7)c=c

+b(8)if

c<n

goto(6)(9)a=a

+b(10)if

a<n

goto(4)(11)c=a

–b練習(xí)?可用于優(yōu)化O

寄存器指派如果當(dāng)前某個變量存放于一個寄存器中，且之后不會再被使用，那么這個寄存器可被分派給別的變量LD

R0,

b

ADD

R1,

R0,

c

ST

a,

R1LD

R1,

a

ADD

R2,

R1,

e

ST

d,

R2后續(xù)使用信息?變量值的使用(use)與活躍(live)O

假設(shè)三地址語句i給x賦了一個值，如果在后

續(xù)的另一語句j的一個運(yùn)算分量為x，且從i開

始有一條沒有對x進(jìn)行賦值的路徑能夠到達(dá)j，那么j就使用了i處計算得到的x的值O

我們可以說稱x在語句i后的程序點上活躍

(live)?即在程序執(zhí)行完語句i的時刻，x中存放的值將被后面的語句使用?不活躍是指變量中存放的值不會被使用，而不是變量

不會被使用后續(xù)使用信息?輸入：基本塊B，開始時B的所有非臨時變量都是活躍的?輸出：各語句i上的變量的活躍性、后續(xù)使用信息?方法：O

從B的最后一個語句開始反向掃描O

對于每個語句i：x=y+z1.令語句i和x、y、z的當(dāng)前活躍性信息/使用信息關(guān)聯(lián)2.設(shè)置x為不活躍、無后續(xù)使用3.設(shè)置y和z為活躍，并指明它們的下一次使用為語句i確定基本塊中的活躍性、后續(xù)使用O

注意：2和3的順序?假設(shè)i,j,a不是臨時變量，它們在出口處活躍，其余變量不活躍O

在8之前的程序點上，i,j,a仍

然活躍；且j在8上被使用O

在7之前的程序點上，i,j,a,t4活躍；且t4被7使用O

在6之前的程序點上，i,j,a,t3活躍，t4不活躍，t3

被6使用O

在5之前的程序點上，i,j,a,t2活躍，t3不活躍O

在4之前的程序點上，…例子?

流圖的頂點是基本塊?

兩個頂點B和C之間有一條有向邊當(dāng)且僅當(dāng)基本塊C的第一個指令可能在B的最后一個指令之后執(zhí)行O

從B的結(jié)尾指令是一條跳轉(zhuǎn)到C的開頭的條件/無條件語句O

在原來的序列中，C緊跟在B之后，且B的結(jié)尾不是無條件跳轉(zhuǎn)語句?

稱B是C的前驅(qū)，C是B的后繼?

入口和出口結(jié)點O

流圖中額外添加的邊，不與中間代碼(基本塊)對應(yīng)O

入口到第一條指令有一條邊O

從任何可能最后執(zhí)行的基本塊到出口有一條邊流圖的構(gòu)造?因跳轉(zhuǎn)而生成的邊O

B3→B3O

B4→B2O

B6→B6?因為順序而生成的邊O

其它流圖的例子?程序的大部分運(yùn)行時間花費(fèi)在循環(huán)上O

循環(huán)是識別的重點?循環(huán)的定義O

循環(huán)L是一個結(jié)點集合O

存在一個循環(huán)入口(loop

entry)結(jié)點，是

唯一的、前驅(qū)可以在循環(huán)L之外的結(jié)點，到達(dá)其余結(jié)點的路徑必然先經(jīng)過這個入口結(jié)點O

其余結(jié)點都存在到達(dá)入口結(jié)點的非空路徑，且路徑都在L中循環(huán)?循環(huán)O

{B3}O

{B6}O

{B2,B3,B4}O

對于{B2,B3,B4}的解釋?B2為入口結(jié)點?B1，B5，B6不在循環(huán)內(nèi)的理由O

到達(dá)B1可不經(jīng)過B2O

B5，B6沒有到達(dá)B2的結(jié)點循環(huán)的例子冗余的指令如果變量a不再被使用了呢？指令選擇冗余的指令?代碼生成概要?指令集架構(gòu)?基本塊與流圖?指令選擇算法?寄存器分配算法?窺孔優(yōu)化?代碼生成器構(gòu)建提綱得考慮指令代價指令選擇?在某些機(jī)器上，同一個三地址指令可以使用多種機(jī)器指令實現(xiàn)；有時多個三地址指令可以使用一個機(jī)器指令實現(xiàn)?指令選擇O

為實現(xiàn)中間表示形式中出現(xiàn)的運(yùn)算符選擇適當(dāng)?shù)臋C(jī)器指令?用樹來表示中間代碼，按照特定的規(guī)則不斷覆蓋這棵樹并生成機(jī)器指令樹重寫實現(xiàn)指令選擇?a[i]=b+1O

a,i：局部變量O

b：全局變量O

Rsp：棧頂指針O

ind：把參數(shù)作為內(nèi)存地址；例子(中間表示)一些重寫規(guī)則(P.360)?規(guī)則1：{LDR0,#a}?規(guī)則7：{ADDR0R0SP}?規(guī)則6：{ADDR0R0i(SP)}?規(guī)則2：{LDR1,b}?規(guī)則8：{INC

R1}?規(guī)則4：{ST*R0R1}覆蓋重寫過程?代碼生成概要?指令集架構(gòu)?基本塊與流圖?指令選擇算法?寄存器分配算法?窺孔優(yōu)化?代碼生成器構(gòu)建提綱?目的：有效利用寄存器?簡單的基本方法：把特定類型的值分配給特定的寄存器O

數(shù)組基地址指派給一組寄存器O

算術(shù)計算分配給一組寄存器O

棧頂指針分配一個寄存器O

……?缺點：寄存器的使用效率較低寄存器分配和指派?在循環(huán)中頻繁使用的值存放在固定寄存器?分配固定多個寄存器來存放內(nèi)部循環(huán)中最活躍的值?可以通過使用計數(shù)的方法來估算把一個變量放到寄存器中會帶來多大好處，然后根據(jù)這個估算來分配寄存器全局寄存器分配?循環(huán)執(zhí)行圖示指令?可否優(yōu)化？?基本塊代碼生成的隱含假設(shè)O

變量使用前要先LoadO

活躍變量在出口處要Store寄存器分配優(yōu)化?如果把x放在寄存器中，每一次引用可以節(jié)省一個單位成本?如果在某個基本塊的結(jié)尾不把x保存回內(nèi)存，可以省略兩個單位的開銷。即如果x被分配在某個寄存器中，對于每個向x賦值且x在其出口處活躍的基本塊，可以節(jié)省兩個單位的開銷?

進(jìn)入循環(huán)和離開循環(huán)的支出成本可以忽略?在循環(huán)L中把一個寄存器分配給x所得到的好處大約：其中，use(x,B)是x在B中被定值之前就被引用的次數(shù)。如果x在B的出口處活躍并在B中被賦予一個值，則live(x,B)的取值為1

， 否則取值為0

。使用計數(shù)?使用全局寄存

器存放a/b/c/d/e/f，分

別可以節(jié)約4/5/3/6/4/4個單位成本使用計數(shù)(續(xù))?基于所獲成本

考慮，可以為a

b

d指派三個

全局寄存器R0R1R2?同時也可以用

R0存e或者f，

這是另外一個選擇使用計數(shù)(續(xù))?代碼生成概要?指令集架構(gòu)?基本塊與流圖?指令選擇算法?寄存器分配算法?窺孔優(yōu)化?代碼生成器構(gòu)建提綱?使用一個滑動窗口(窺孔)來檢查目標(biāo)指令，在窺孔內(nèi)實現(xiàn)優(yōu)化O

冗余指令消除O

不可達(dá)代碼消除O

控制流優(yōu)化窺孔優(yōu)化—先生成，再優(yōu)化?多余的LD/ST指令O

LD

a

R0O

ST

R0

aO

且沒有指令跳轉(zhuǎn)到第二條指令處?級聯(lián)跳轉(zhuǎn)代碼O

if

debug==1goto

L1；goto

L2O

if

debug!=1goto

L2;O

如果已知debug一定是0，那么替換成為gotoL2；冗余指令?gotoL1;……;L1：goto

L2O

goto

L2;……;goto

L2?if

a<b

goto

L1;……;L1:goto

L2O

if

a<b

goto

L2;……;L1:goto

L2?goto

L1;…;L1:if

a<b

goto

L2;L3:O

if

a<b

goto

L2;goto

L3;…;L3:控制流優(yōu)化?代碼生成概要?指令集架構(gòu)?基本塊與流圖?指令選擇算法?寄存器分配算法?窺孔優(yōu)化?代碼生成器構(gòu)建提綱?根據(jù)三地址指令序列生成機(jī)器指令，假設(shè)O

每個三地址指令只有一個對應(yīng)的機(jī)器指令O

有一組寄存器用于計算基本塊內(nèi)部的值?主要目標(biāo)O

盡量減少加載和保存指令，即最大限度利用基本塊的代碼生成器寄存器?變量x：指向分配x的內(nèi)存位置?a(r)：地址是a的左值加上r中的值?constant(r)：寄存器中內(nèi)容加上前面的

常數(shù)即其地址?*r：寄存器r的內(nèi)容為其地址?*constant(r)：r中內(nèi)容加上常量所指地

址中存放的值為其地址?常量#constant尋址模式?一些思考O

如果y已經(jīng)裝載進(jìn)某個寄存器O

R1里面的內(nèi)容是什么O

如果z已經(jīng)裝載進(jìn)某個寄存器O

R2里面的內(nèi)容是什么O

如果x再也沒有被使用O

LD

R1,yO

LD

R2,zO

SUB

R1,R1,R2O

ST

x,R1//R1=y//R2=z//R1=R1-R2//x=R1實例?x=y-z//R1=i//R1=R1*8//R2=contents(a+contents(R1))//b=R2O

ST

a(R2),R1//contents(a+contents(R2))=R1//R1=c//R2=j//R2=R2*8?

a[j]=cO

LDO

LDO

MULR1,iR1,R1,8R2,a(R1)b,R2O

LDO

MULO

LDO

STR1,c

R2,jR2,R2,

8?b=a[i]實例實例?不同的目的有不同的度量O

最短編譯時間、目標(biāo)程序大小、運(yùn)行時間、能耗?假設(shè)：每個指令有固定的代價，設(shè)定為1加上運(yùn)算分量尋址模式的代價O

LD

R0,R1；代價為1O

LD

R0,M；代價是2O

LD

R1,*100(R2)；代價為2?為給定源程序生成最優(yōu)目標(biāo)程序O

不可判定?不可判定問題是可計算性理論和計算復(fù)雜性理論中定義的一類決定性問題，此類問題無法總是用單一算法得出正確的是/否的答案。程序和指令的代價?如何將IR中的名字轉(zhuǎn)換成為目標(biāo)代碼中的地址O

不同的區(qū)域中的名字采用不同的尋址方式?如何為過程調(diào)用和返回生成代碼O

靜態(tài)分配O

棧式分配目標(biāo)代碼中的地址?重點考慮寄存器的使用方法O

執(zhí)行運(yùn)算時，運(yùn)算分量必須放在寄存器中O

用于臨時變量O

存放全局的值O

進(jìn)行運(yùn)行時刻管理(比如：棧頂指針)代碼生成器如果必要才把結(jié)果存入內(nèi)存簡單方法實際情況?

a

=

b

+

c

預(yù)先判斷需要哪些加載指令把

O

LD

R1,

cO

ADD

R2,

R0,

R1

用哪個寄存器

?隱含的假設(shè)O

無限多寄存器O

不知道變量是否在寄存器中O

所有變量以后都有用O

LD

R0,

b

必須的運(yùn)算分量加載進(jìn)寄存器

有限的寄存器，加載時預(yù)判選

O

ST

a,R2?依次考慮各三地址指令，盡可能把值保留在寄存器中，以減少寄存器/內(nèi)存之間的數(shù)據(jù)交換?為一個三地址指令生成機(jī)器指令時O

只有當(dāng)運(yùn)算分量不在寄存器中時，才從內(nèi)存載入O

盡量保證只有當(dāng)寄存器中的值不被使用時，才把它覆蓋掉基本思路?記錄各個值對應(yīng)的位置O

寄存器描述符：跟蹤各個寄存器都存放了哪些變量的當(dāng)前值O

地址描述符：某個變量的當(dāng)前值存放在哪個或哪些位置(包括內(nèi)存位置和寄存器)上基本數(shù)據(jù)結(jié)構(gòu)?getReg的目標(biāo)：減少LD/ST指令?任務(wù)：為運(yùn)算分量和結(jié)果分配寄存器?為x=y+z指令選擇寄存器?為運(yùn)算分量y分配寄存器O

如果已經(jīng)在某個寄存器中，不需要進(jìn)行處理，選擇這個寄存器O

如果不在寄存器中，且有空閑寄存器，選擇

一個空閑寄存器O

如果不在寄存器中，且沒有空閑寄存器？getReg函數(shù)(1)?為運(yùn)算分量y分配寄存器(如果不在寄存器中，且沒有空閑寄存器)O

尋找一個寄存器R，假設(shè)已經(jīng)有某個變量v在R中了(R的寄存器描述符中包含了v)?如果v的地址描述符表明還可以在別的地方找到v，DONE?v就是x(即結(jié)果)，且x不是運(yùn)算分量之一，DONE?如果v在此之后不會被使用，DONE?生成保存指令ST

v

R(溢出操作)并修改v的地址描述符，如果R中存放了多個變量的值，那么需要生成多條ST指令 (選盡可能少ST的)；?關(guān)鍵：借用了v所在的寄存器，不能隨意把v沖掉getReg函數(shù)(2)?為x選擇寄存器Rx(基本方法和把y從內(nèi)存LD時一樣)?區(qū)別O

只存放x的值的寄存器總是可接受的，因為x計算出了一個新的值O

如果y在指令I(lǐng)之后不再使用，且Ry僅僅保存了y的值，那么Ry同時也可以作為Rx?處理x=y時，我們總是讓Rx=RygetReg函數(shù)(3)?重要子函數(shù)：getReg(I)O

根據(jù)寄存器描述符和地址描述符、數(shù)據(jù)流信息，為三地址指令I(lǐng)選擇最佳的寄存器O

得到的機(jī)器指令的質(zhì)量依賴于getReg函數(shù)選取寄存器的算法?代碼生成算法框架O

遍歷三地址指令1.使用getReg()函數(shù)選擇寄存器2.生成指令代碼生成算法(1)?運(yùn)算語句：x=y+zO

調(diào)用getReg(x=y+z)，為x,y,z選擇寄存器Rx,

Ry,RzO

查Ry的寄存器描述符，如果y不在Ry中則生成指令?LD

Ry

y’(y’表示存放y值的當(dāng)前位置)O

類似地，確定是否生成LD

Rz,z’O

生成指令A(yù)DD

Rx,Ry,Rz?

賦值語句：x=yO

getReg(x=y)總是為x和y選擇相同的寄存器O

如果y不在Ry中，生成機(jī)器指令LD

Ry,y?基本塊的收尾O

如果變量x在出口處活躍，且x現(xiàn)在不在內(nèi)存，那么生成指令ST

x,

Rx代碼生成算法(2)?代碼生成同時更新寄存器和地址描述符?處理普通指令時生成LD

R

xO

R的寄存器描述符：只包含xO

x的地址描述符：R作為新位置加入到x的位置集合中O

從任何不同于x的變量的地址描述符中刪除R?STx,RO

修改x的地址描述符，包含自己的內(nèi)存位置代碼生成算法(3)?ADD

Rx,Ry,RzO

Rx的寄存器描述符只包含xO

x的地址描述符只包含Rx(不包含x的內(nèi)存位置！)O

從任何不同于x的變量的地址描述符中