編譯原理教程課后習(xí)題答案-第七章

第七章目標(biāo)代碼生成

7.1對下列四元式序列生成目標(biāo)代碼：

T=A-B

S=C+D

W=E-F

U=W/T

V=U*S

其中，V是基本塊出口的活躍變量，R0和R1是可用寄存器。

【解答】簡單代碼生成算法依次對四元式進(jìn)行翻譯。我們以四元式T=a+b為例來說明其

翻譯過程。

匯編語言的加法指令代碼形式為

ADDR,X

其中，ADD為加法指令；R為第一操作數(shù)，第一操作數(shù)必須為寄存器類型；X為

第二操作數(shù)，它可以是寄存器類型，也可以是內(nèi)存型的變量。ADDR,X指令的含意是：將

第一操作數(shù)R與第二操作數(shù)相加后，再將累加結(jié)果存放到第一操作數(shù)所在的寄存器中。要

完整地翻譯出四元式T=a+b，則可能需要下面三條匯編指令：

MOVR,a

ADDR,b

MOVT,R

第一條指令是將第一操作數(shù)a由內(nèi)存取到寄存器R中；第二條指令完成加法運算；

第三條指令將累加后的結(jié)果送回內(nèi)存中的變量T。是否在翻譯成目標(biāo)代碼時都必須生成這三

條匯編指令呢？從目標(biāo)代碼生成的優(yōu)化角度考慮，

即為了使生成的目標(biāo)代碼更短以及充分利

用寄存器，上面的三條指令中，第一條和第三條指令在某些情況下是不必要的。這是因為，

如果下一個四元式緊接著需要引用操作數(shù)T，則第三條指令就不急于生成，可以推遲到以后

適當(dāng)?shù)臅r機(jī)再生成。

此外，如果必須使用第一條指令，即第一操作數(shù)不在寄存器而是在內(nèi)存中，且此時所有可用

寄存器都已分配完畢，這時就要根據(jù)寄存器中所有變量的待用信息(也即引用點)來決定淘汰

哪一個寄存器留給當(dāng)前的四元式使用。寄存器的淘汰策略如下：

(1)如果某寄存器中的變量已無后續(xù)引用點且該變量是非活躍的，則可直接將該寄

存器作為空閑寄存器使用。

(2)如果所有寄存器中的變量在基本塊內(nèi)仍有引用點且都是活躍的，則將引用點最

遠(yuǎn)的變量所占用寄存器中的值存放到內(nèi)存與該變量對應(yīng)的單元中，后再將此寄存器分配給

然

當(dāng)前的指令使用。

因此，本題所給四元式序列生成的目標(biāo)代碼如下：

MOVR0,A

SUBR0,C

/*R0=T*/

MOVR1,C

ADDR1,D

/*R1=S*/

MOVS,R1

/*S引用點較T引用點遠(yuǎn)，故將R1的值送內(nèi)存單元S*/

MOVR1,E

SUBR1,F

/*R1=W*/

SUBR1,R0

/*R1=U*/

MULR1,S

/*R1=V*/

7.2假設(shè)可用的寄存器為R0和R1，且所有臨時單元都是非活躍的，試將以下四元式基本

塊：

T1=B-C

T2=A*T1

T3=D+1

T4=E-F

T5=T3*T4

W=T2/T5

用簡單代碼生成算法生成其目標(biāo)代碼。

【解答】該基本塊的目標(biāo)代碼如下(指令后面為相應(yīng)的注釋)：

MOV

R0,B/*取第一個空閑寄存器R0*/

SUB

R0,C

/*運算結(jié)束后R0中為T1結(jié)果，內(nèi)存中無該結(jié)果*/

MOV

R1,A/*取一個空閑寄存器R1*/

MUL

R1,R0/*運算結(jié)束后R1中為T2結(jié)果，內(nèi)存中無該結(jié)果*/

MOV

R0,D/*此時R0中結(jié)果T1已經(jīng)沒有引用點，且臨時單元T1是非

活躍的，所以，寄存器R0可作為空閑寄存器使用*/

ADD

R0,″1″

/*運算結(jié)束后R0中為T3結(jié)果，內(nèi)存中無該結(jié)果*/

MOVT2,R1/*翻譯四元式T4=E-F時，所有寄存器已經(jīng)分配完畢，寄存器R0中存的T3

和寄存器R1中存的T2都是有用的。由于T2的下一個引用點較T3的下一個引用點更遠(yuǎn)，

所以暫時可將寄存器R1中的結(jié)果存回到內(nèi)存的變量T2中，

從而將寄存器R1空閑以備使用

*/

MOV

R1,E

SUBR1,F

/*運算結(jié)束后R1中為T4結(jié)果，內(nèi)存中無該結(jié)果*/

MULR0,R1

/*運算結(jié)束后R0中為T5結(jié)果，內(nèi)存中無該結(jié)果。注意，該指

令將寄存器R0中原來的結(jié)果T3沖掉了?？梢赃@么做的原因是，T3在該指令后不再有引用

點，且是非活躍變量*/

MOVR1,T2/*此時R1中結(jié)果T4已經(jīng)沒有引用點，且臨時單元T4是非活躍的，因此

寄存器R1可作為空閑寄存器使用*/

DIVR1,R0

/*運算結(jié)束后R1中為W結(jié)果，內(nèi)存中無該結(jié)果。此時所有指令部分已經(jīng)

翻譯完畢*/

MOVW,R1

/*指令翻譯完畢時，寄存器中存有最新的計算結(jié)果，必須將它們存回到內(nèi)

存相應(yīng)的單元中去，

否則，在翻譯下一個基本塊時，

所有的寄存器被當(dāng)成空閑的寄存器使用，

從而造成計算結(jié)果的丟失?？紤]到寄存器R0中的T5和寄存器R1中的W，臨時單元T5是

非活躍的，因此只要將結(jié)果W存回對應(yīng)單元即可*/

7.3對基本塊P：

S0=2

S1=3/S0

S2=T-C

S3=T+C

R=S0/S3

H=R

S4=3/S1

S5=T+C

S6=S4/S5

H=S6*S2

(1)試應(yīng)用DAG進(jìn)行優(yōu)化；

(2)假定只有R、H在基本塊出口是活躍的，寫出優(yōu)化后的四元式序列；

(3)假定只有兩個寄存器AX、BX，試寫出上述優(yōu)化后的四元式序列的目標(biāo)代碼。

【解答】(1)根據(jù)DAG的構(gòu)造算法構(gòu)造基本塊P的DAG步驟如圖7-1所示的(a)

到(h)。

n4S2

n5S3

Sn24S2

－

n0S0

n0S0

n1S1

n0S0

n1S1

n2

n3

n0S0

n1S1

＋

－

n2

n3

2

(a)

2

(b)

n6

1.5

2

1.5

(c)

T

C

2

1.5

(d)

T

C

R

n5S3

Sn24S2

n6

R,H

n5S3

Sn24S2

/

＋

－

/

＋

－

n0S0

n1S1

n2

n3

n0S0

n1S1

n2

n3

2

1.5

(e)

T

C

2

1.5

(f)

T

C

n7H

n6

R,H,S6

n5S3

Sn24S2

n6

R,H,S6

n5S3,S5Sn24S2

/

＋

n0S0,S4n1S1

n2

/

－

n3

＋

－

n0S0,S4n1S1

n2

n3

2

1.5

(g)

T

C

2

1.5

(h)

T

C

圖7-1基本塊P的DAG

按圖7-1(h)和原來構(gòu)造結(jié)點的順序，優(yōu)化后的四元式序列為

S0=2

S4=2

S1=1.5

S2=T-C

S3=T+C

S5=S3

R=2/S3

S6=R

H=S6*S2

(2)假定只有R、H在基本塊出口是活躍的，則上述優(yōu)化后的四元式序列可進(jìn)一步優(yōu)化為

S0=T-C

S3=T+C

R=2/S3

H=R*S2

(3)假定只有兩個寄存器AX、BX，上述優(yōu)化后的四元式序列的目標(biāo)代碼為

MOVAX,T

SUBAX,C

MOVAX,S2

MOVAX,T

ADDAX,C

MOVBX,2

DIVBX

MOVAX,S2

MULBX

MOVBX,H

7.4參考附錄1和附錄2(《編譯原理教程》一書)，將下列匯編程序片段翻譯為對應(yīng)的

8086/8088機(jī)器語言代碼(匯編地