課件代碼生成

第12章代碼生成學(xué)習(xí)目標(biāo)掌握：基本塊代碼生成算法，寄存器分配算法理解：待用信息，活躍信息代碼生成概述一個計算機(jī)模型一個簡單的代碼生成器12.1

代碼生成概述代碼生成的任務(wù)把中間代碼（經(jīng)過優(yōu)化或未經(jīng)過優(yōu)化）作為輸入，將其轉(zhuǎn)換成特定機(jī)器的機(jī)器語言或匯編語言作為輸出，這樣的轉(zhuǎn)換程序稱為代碼生成器(Code

Generator)。目標(biāo)代碼生成需要考慮的基本問題：如何使生成的目標(biāo)代碼較短如何充分利用計算機(jī)的寄存器，減少目標(biāo)代碼訪問存儲單元的次數(shù)目標(biāo)代碼生成的一些共同的問題，而不討論某個特定機(jī)器的代碼生成問題寄存器分配算法目標(biāo)代碼的執(zhí)行效率很大程度依賴于寄存器的使用；基本塊的代碼生成算法寄存器分配算法僅限定在一個基本塊的范圍內(nèi)，以四元式的中間代碼作為輸入，以一個稱作M

的模型機(jī)的匯編語言作為輸出。12.2

一個計算機(jī)模型M模型機(jī)具有n個通用寄存器R1,R2,R3,…,Rn，它們既可以作為累加器，又可以作為變址器。約定：op表示運(yùn)算，C表示常量；M表示內(nèi)存單元（用變量名表示該變量所在的單元），Ri表示寄存器；*表示間接尋址尋址類型指令格式意義（設(shè)op是二目算符）直接型op Ri

,

M(Ri)

op

(M)

=>

Ri寄存器型op Ri

,

Rj(Ri)

op

(Rj)

=>

Ri變址型op Ri

,

c(Rj)(Ri)

op

((Rj)+c)

=>

Ri間接型op Ri

,

*M(Ri)

op

((M))

=>

Riop Ri

,

*Rj(Ri)

op

((Rj))=>

Riop Ri

,

*c(Rj)(Ri)

op

(((Rj)+c))

=>

Ri1.

指令系統(tǒng)與尋址方式令X代表Ri或者M(jìn)，則(X)表示直接取X的內(nèi)容作為操作對象，((X))表示一層間接，即取X的內(nèi)容作為地址特殊指令除了上述的尋址方式和一般的運(yùn)算指令之外，計算機(jī)模型的指令系統(tǒng)中還包括如下特殊指令主要有兩大類：內(nèi)存與寄存器交換類：包括LD與ST；比較與轉(zhuǎn)移類：如CMP與J

X指令意義指令意義LD Ri

,

B把存儲單元B

的內(nèi)容裝入寄存器Ri，即(B)=>RiJ<

X小于轉(zhuǎn)X單元ST Ri

,

B把寄存器Ri

的內(nèi)容存回存儲單元B

，即(Ri)=>BJ=

X等于轉(zhuǎn)X單元J

X無條件轉(zhuǎn)向X單元Jnz

X不為零轉(zhuǎn)X單元CMP

A,

B將A單元與B單元的值進(jìn)行比較，把結(jié)果置入狀態(tài)字Jz

X等于零轉(zhuǎn)X單元例：條件語句

if

A>B

goto X中間代碼：（

J>,

A,

B,

X

）目標(biāo)代碼：

CMP

A,

BJ>

X12.3

一個簡單的代碼生成器一個基于基本塊的代碼生成器它的輸入是四元式中間代碼，輸出是M機(jī)器的匯編代碼著重討論在基本塊內(nèi)如何充分利用寄存器12.3.1

寄存器分配原則在指令的執(zhí)行代價中，寄存器的代價是最小的，因此總是希望將盡可能多的運(yùn)算對象放在寄存器中；由于任何一個計算機(jī)模型中的寄存器個數(shù)都是有限的，因而需要根據(jù)一些原則，對寄存器進(jìn)行分配基于基本塊的寄存器分配的一般原則：當(dāng)生成某變量的目標(biāo)代碼時，盡量讓變量的值或中間結(jié)果保留在寄存器中，直到寄存器不夠分配為止，這樣引用變量值時可減少對內(nèi)存的存取次數(shù)，提高運(yùn)行速度進(jìn)入基本塊時所有寄存器是空閑的，當(dāng)?shù)交緣K出口時，將變量的有用值存回內(nèi)存，釋放所有寄存器在基本塊內(nèi)，后邊不再被引用的變量占用的寄存器應(yīng)盡早釋放，以提高寄存器的利用效率12.3.2

待用信息鏈表法1.

引入原因：為了把在基本塊內(nèi)還要被引用的變量值盡可能保存在寄存器中，不再被引用的變量所占的寄存器盡早釋放，在翻譯四元式i:

A:=B

op

C時，必須知道變量A，B，C在基本塊內(nèi)其后的引用情況，即所謂變量的待用信息。2.

基本定義：定值、引用、活躍在形如i:A:=B+C

的代碼中，出現(xiàn)在“:=”左邊和右邊的變量，分別被稱為對變量的定值和引用，i被稱為變量的定值點(diǎn)或引用點(diǎn)。若變量的值在i之后的代碼序列中被引用，則稱變量在i點(diǎn)是活躍的。待用信息在基本塊中，變量A在四元式i中被定值，在i后面的四元式j(luò)中引用A值，且從i到j(luò)之間沒有其他對A的定值點(diǎn)，稱j是i中對變量A的待用信息（下次引用信息）。所有這樣的待用信息jk（k=1,2,…）構(gòu)成待用信息鏈。只在基本塊內(nèi)考慮待用信息，一個變量在基本塊的后繼中是否被引用，可從活躍變量信息得知（出基本塊后，變量是否活躍需要進(jìn)行全局的數(shù)據(jù)流分析才能確定）在基本塊B2內(nèi)：R在(3)處定值，在(4)處被引用，所以(4)是(3)中R的待用信息流程B3->B2：X在(5)處被定值，在(3)處被引用，所以X在(5)處是活躍的(1)

read

X(2)

read

YR:=X

mod

Yif

R=0

goto

(8)write

YhaltB1B2X:=Y

B3Y:=Rgoto

(3)B43.

基本塊內(nèi)求待用信息的算法假設(shè)符號表中含有變量的待用信息和活躍信息欄；四元式表上也有關(guān)于結(jié)果變量、左右操作數(shù)變量的待用和活躍信息欄。1)把基本塊中各變量在符號表的登記項中的待用信息欄置為“非待用”，活躍信息欄按變量在基本塊出口是否活躍而置為“活躍”或“非活躍”（假定用戶變量都是活躍的，臨時變量都是非活躍的）。從基本塊出口的四元式開始由后向前依次處理各個四元式i:

A:=B

op

C

，直到處理完為止：把符號表中變量A的待用信息和活躍信息附加到四元式i上。把符號表中變量A的待用信息欄和活躍信息

欄分別置為“非待用”和“非活躍”。（由于在i中對A的定值只能在i以后引用，而對i

以前的四元式來說A是非活躍和非待用的。）把符號表中變量B和C的待用信息和活躍信息附加到四元式i上。把符號表中變量B和C的待用信息欄置為“i”，活躍信息欄置為“活躍”。注意：i，ii，iii，iv的次序不能顛倒，因?yàn)锽和C也可能是A求待用信息的實(shí)例有如下基本塊T:=A-BU:=A-CV:=T+UD:=V+UA,B,

C,D是用戶變量（在基本塊出口活躍）T,U,V是臨時變量（在基本塊出口不活躍）用“F”表示“非待用”“非活躍”，“L”表示

“活躍”則該基本塊的待用信息及活躍信息的計算結(jié)果如下：序號四元式結(jié)果左操作數(shù)右操作數(shù)1T:=A-B(3,L)(2,L)(F,L)2U:=A-C(3,L)(F,L)(F,L)3V:=T+U(4,L)(F,F)(4,L)4D:=V+U(F,L)(F,F)(F,F)附加在四元式上的待用及活躍信息符號表中的待用及活躍信息變量名初值(4)(3)(2)(1)A(F,L)(2,L)(1,L)B(F,L)(1,L)C(F,L)(2,L)D(F,L)(F,F)T(F,F)(3,L)(F,F)U(F,F)(4,L)(3,L)(F,F)V(F,F)(4,L)(F,F)12.3.3

代碼生成算法寄存器描述數(shù)組RVALUE為了掌握各寄存器的使用情況，用數(shù)組RVALUE記錄每個寄存器的當(dāng)前情況：RVALUE[Ri]={A}表示Ri的現(xiàn)行值是變量A的值，或說A獨(dú)占Ri。RVALUE[Rj]={}

表示Rj是空閑的。RVALUE[Ri]={B,

C}表示Ri的現(xiàn)行值是變量

B和C的值，或說B,

C共占Ri。在復(fù)寫（B:＝C）時存在多個變量共占一個寄存器。變量地址描述數(shù)組AVALUE生成目標(biāo)代碼要用到變量的地址，它可能是某寄存器Ri，也可能是內(nèi)存單元（仍用變量名表示）。若變量值同時在寄存器Ri和內(nèi)存，則取Ri為其地址。AVALUE[A]={Ri}

表示變量A的值在Ri中，不在內(nèi)存。AVALUE[B]={Rj,

B}

表示變量B的值在Rj中，又在內(nèi)存。AVALUE[C]={C}

表示變量C的值只在內(nèi)存。3.

寄存器分配函數(shù)GETREG以形如i:A:＝B

op

C

的四元式為輸入，返回一個寄存器R，用以存放A的結(jié)果值其算法為：如果B獨(dú)占Ri，且B與A是同一標(biāo)識符或B值不再引用，則選Ri為R并轉(zhuǎn)（4）如果有空閑Ri，則選Ri為R并轉(zhuǎn)（4）。3)釋放一個Ri作為R，最好占用Ri的變量值同時在主存中，或在基本塊中引用的位置最遠(yuǎn)。對Ri中不是A的變量M，且其值不在內(nèi)存，則做如下處理：生成目標(biāo)代碼

ST

Ri

,M，把變量M的值送入內(nèi)存修改變量地址描述：如M不是B則AVALUE[M]＝{M}，否則AVALUE[M]＝{Ri，M}。修改寄存器描述：刪除RVALUE{Ri}中的M。4)

給出R，返回通過GETREG（i: A:=B

op

C

）返回的寄存器R用于進(jìn)行B

op

C的運(yùn)算，并把結(jié)果（A值）保存在R中。4.

基本塊的代碼生成算法開始時所有寄存器都空閑，順序取出四元式i:

A:＝B

op

C，按下述算法生成目標(biāo)代碼。到達(dá)基本塊出口時，若有活躍變量占用寄存器且其值不在內(nèi)存，則生成存數(shù)指令保存其值并釋放寄存器。分配寄存器

R=GETREG(i: A:=B

op

C)利用地址描述數(shù)組AVALUE[B]和AVALUE[C],確定出B和C現(xiàn)行值的存放位置B’和C’。如果其現(xiàn)行值在寄存器中，則把寄存器取作B’和C’如果B’≠R則生成目標(biāo)代碼LD R

,

B’

;op R

,

C’否則生成

op R

,

C’，如果B’或C’為R，則刪除AVALUE[B]或AVALUE[C]中的R。令A(yù)VALUE[A]={R}，RVALUE[R]={A}。如果B和C的現(xiàn)行值是“非引用”和“非活躍”，且其值在某個Rk中，則刪除RVALUE[Rk]中的

B或C，刪除AVALUE[B]和AVALUE[C]中的Rk。例：假設(shè)只有R1和R2兩個寄存器利用基本塊代碼生成算法生成目標(biāo)代碼四元式選取R目標(biāo)代碼RVALUEAVALUE(1)

T:=A-B空閑的R1LD R1

,

ASUB R1

,

BR1含有TT在R1中(2)U:=A-C空閑的R2LD R2

,

ASUB R2

,

CR1含有TR2含有UT在R1中U在R2中(3)

V:=T+UT獨(dú)占的