第十二章代碼生成

第12章代碼生成12.1代碼生成概述將中間語言轉(zhuǎn)換成特定目標(biāo)機(jī)的機(jī)器語言或匯編語言。代碼生成要考慮的主要問題：基本塊的代碼生成：在一個(gè)基本塊范圍內(nèi)考慮如何充分利用寄存器的問題。具體細(xì)節(jié)依賴于目標(biāo)機(jī)器的指令系統(tǒng)、硬件配置和操作系統(tǒng)。目標(biāo)代碼的質(zhì)量：占用空間、執(zhí)行效率12.1.1

代碼生成程序在編譯系統(tǒng)中的位置目標(biāo)代碼的三種形式地址代真的機(jī)器代碼待裝配的機(jī)器代碼模塊匯編語言（宏匯編）機(jī)器指令形式源程序編譯前端代碼優(yōu)化代碼生成程序符號(hào)表目標(biāo)程序中間代碼中間代碼12.1.2設(shè)計(jì)代碼生成程序的基本問題1.代碼生成程序的輸入中間代碼和符號(hào)表中的信息語義分析時(shí)直接生成代碼2.指令選擇：指令系統(tǒng)3.寄存器分配：充分利用寄存器4.指令調(diào)度：選擇計(jì)算次序指令選擇選擇計(jì)算機(jī)指令系統(tǒng)基本原則(1)減小產(chǎn)生代碼的尺寸(2)減小目標(biāo)代碼的執(zhí)行時(shí)間(3)降低目標(biāo)代碼的能耗指令選擇對(duì)于同一個(gè)指令系統(tǒng)，對(duì)于同樣的中間代碼，可以選擇不同的指令生成代碼序列。例如：x:=y+z，其中x,y,z均為靜態(tài)變量，代碼序列如下：LDR0,yADDR0,zSTR0,x四元式a:=a+1用INCa一條指令即可實(shí)現(xiàn)。

充分利用寄存器—提高執(zhí)行速度，少占用內(nèi)存，開銷小。通用寄存器、浮點(diǎn)寄存器寄存器的使用：分配和指派（1）分配：為程序的某一點(diǎn)選擇駐留在寄存器中的一組變量。（2）指派：指定變量將要駐留的寄存器—寄存器賦值。寄存器分配

基本塊中和全局的寄存器分配：不把寄存器平均分配給各個(gè)變量使用，而是從可用的寄存器中分出幾個(gè)，固定分配給幾個(gè)變量單獨(dú)使用。標(biāo)準(zhǔn)—以各變量在循環(huán)內(nèi)需要訪問主存單元的次數(shù)為標(biāo)準(zhǔn)。寄存器分配

寄存器分配原則：（1）生成某變量的目標(biāo)對(duì)象值時(shí)，盡量讓變量的值或計(jì)算結(jié)果保留在寄存器中，直到寄存器不夠分配為止。減少對(duì)內(nèi)存的訪問次數(shù)。（2）當(dāng)?shù)交緣K出口時(shí)，將變量的值存放在內(nèi)存中。因?yàn)橐粋€(gè)基本塊可能有多個(gè)后繼或前驅(qū)結(jié)點(diǎn)，同一變量名在不同前驅(qū)結(jié)點(diǎn)的基本塊內(nèi)，出口前存放的寄存器可能不同，或沒有定值，后繼結(jié)點(diǎn)中無法使用。寄存器分配

（3）在同一基本塊內(nèi)后邊不再被引用的變量所占用的寄存器應(yīng)盡早釋放，以提高寄存器的利用率。使用編號(hào)偶奇寄存器對(duì)的方法：乘法指令Mx,yx放在偶寄存器，y放在奇寄存器，積占據(jù)整個(gè)寄存器對(duì)。除法指令Dx,y被除數(shù)x占據(jù)一個(gè)偶奇寄存器對(duì)，y是單個(gè)寄存器，完成時(shí)，偶寄存器保存余數(shù)，奇寄存器保存商。寄存器分配寄存器分配(b)t:=a+bt:=t*ct:=t/dLDR0,aADDR0,bADDR0,cSRDAR0,32DIVR0,dSTR1,t(a)t:=a+bt:=t*ct:=t/dLDR1,aADDR1,bMULR0,cDIVR0,dSTR1,t最優(yōu)的機(jī)器指令序列兩個(gè)三地址代碼序列指令調(diào)度確定程序指令的執(zhí)行順序?qū)崿F(xiàn)(a+b)+c的優(yōu)化與否的兩個(gè)指令序列LDR1,aLDR1,aLDR2,bLDR2,bNOPLDR3,cADDIR1,R1,R2ADDIR1,R1,R2LDR2,c

ADDIR1,R1,R3

NOPADDIR1,R1,R2T4:=A+B-(E-(C+D))T1:=A+BMOVA,R0T2:=C+DADDB,R0T3:=E-T2MOVC,R1T4:=T1-T3ADDD,R1MOVR0,T1MOVE,R0SUBR1,R0MOVT1,R1SUBR0,R1MOVR1,T4對(duì)于同一表達(dá)式的不同順序的四元式序列的目標(biāo)代碼序列T4:=A+B-(E-(C+D))T2:=C+DMOVC,R0T3:=E-T2ADDD,R0T1:=A+BMOVE,R1T4:=T1-T3SUBR0,R1MOVA,R0ADDB,R0SUBR1,R0MOVR0,T4對(duì)于同一表達(dá)式的不同順序的四元式序列的目標(biāo)代碼序列12.2一個(gè)簡(jiǎn)單的代碼生成程序以四元式的中間代碼為輸入，將其轉(zhuǎn)換成給定的M計(jì)算機(jī)的目標(biāo)代碼在一個(gè)基本塊內(nèi)如何充分利用寄存器以提高目標(biāo)代碼的運(yùn)行效率。寄存器分配的一般算法12.2.1計(jì)算機(jī)模型M計(jì)算機(jī)，具有n+1個(gè)寄存器R0~Rn作為累加器和/或變址器‘op’表示運(yùn)算符，‘M’表示內(nèi)存單元，變量名表示變量所在單元，‘C’表示常量，‘*’表示間址方式存取。指令包含四種類型：直接地址型、寄存器型、變址型、間址型模型計(jì)算機(jī)的指令若op是一目運(yùn)算符，則“opRi，M”的意義為：op(M)?Ri，op為二目運(yùn)算符時(shí)如下：類型指令形式意義直接地址型寄存器型變址型間接型opRi,MopRi,RjopRi,c(Rj)opRi,*MopRi,*RjopRi,*c(Rj)(Ri)op(M)?Ri(Ri)op(Rj)?Ri(Ri)op((Rj)+c)?Ri

(Ri)op((M))?Ri(Ri)op((Rj))?Ri(Ri)op(((Rj)+c))?Ri12.2.2待用信息鏈表法盡可能地讓該變量的值保留在寄存器中盡可能引用變量在寄存器中的值釋放基本塊內(nèi)不再引用的變量所占的寄存器可從基本塊的出口由后向前掃描，對(duì)每個(gè)變量建立相應(yīng)的待用信息鏈和活躍變量信息鏈。假定基本塊中的變量在出口處都是活躍的。待用信息若在一個(gè)基本塊中：

變量A在四元式i中被定值在i后面的四元式j(luò)中要引用A值且從i到j(luò)之間沒有其它對(duì)A的定值點(diǎn)，這時(shí)我們稱j是四元式i中對(duì)變量A的待用信息或稱下次引用信息同時(shí)也稱A是活躍的若A被多次引用則可構(gòu)成待用信息鏈與活躍信息鏈計(jì)算待用信息的算法符號(hào)表中增加“待用信息”欄和“活躍信息”欄(1)對(duì)各基本塊的符號(hào)表中的“待用信息”欄和“活躍信息”欄置初值，即把“待用信息”欄置“非待用”。對(duì)“活躍信息”欄按在基本塊出口處是否為活躍而置成“活躍”或“非活躍”。這里假定變量都是活躍的，臨時(shí)變量都是非活躍的。計(jì)算待用信息的算法(2)從基本塊出口到基本塊入口由后向前依次處理每個(gè)四元式。對(duì)每個(gè)四元式i:A:=BopC，依次執(zhí)行下述步驟：a)把符號(hào)表中變量A的待用信息和活躍信息附加到四元式上。計(jì)算待用信息的算法b)把符號(hào)表中變量A的待用信息欄和活躍信息欄分別置為“非待用”和“非活躍”。由于在i中對(duì)A的定值只能在i以后的四元式才能引用，因而對(duì)i以前的四元式來說A是不活躍也不可能是待用的。計(jì)算待用信息的算法c)把符號(hào)表中變量B和C的待用信息和活躍信息附加到四元式i上。d)把符號(hào)表中變量B和C的待用信息欄置為“i”，活躍信息欄置為“活躍”。注意，以上a)和b)，c)和d)的次序不能顛倒。待用信息的例例：若用A，B，C，D表示變量，用T，U，V表示中間變量，有四元式如下：(1)

T:=A-B(2)

U:=A-C(3)

V:=T+U(4)

D:=V+U其名字表中的待用信息和活躍信息如下表，用“F”表示“非待用”“非活躍”，用“L”表示活躍。(1)(2)(3)(4)表示四元式序號(hào)。待用信息和活躍信息鏈待用信息鏈表中“待用信息鏈”與“活躍信息鏈”的每列從左至右為每從后向前掃描一個(gè)四元式時(shí)相應(yīng)變量的信息變化情況，空白處為沒變化。待用信息和活躍信息在四元式上的標(biāo)記如下所示：(1)T(3)L:=A(2)L-BFL(2)U(3)L:=AFL-CFL(3)V(4)L:=TFF+U(4)L(4)DFL:=VFF+UFF12.2.3代碼生成算法寄存器描述和地址描述為隨時(shí)掌握各寄存器的使用情況用寄存器描述數(shù)組RVALUE：描述每個(gè)寄存器當(dāng)前的狀況，為空閑狀態(tài)還是被某幾個(gè)變量占用，用寄存器Ri的編號(hào)值作為下標(biāo)，數(shù)組元素值為變量名。變量地址描述數(shù)組AVALUE：表示變量的存放情況，在寄存器中還是在內(nèi)存中。

代碼生成算法相應(yīng)的表示如下：RVALUE[Ri]={A,C}表示寄存器Ri的現(xiàn)行值是變量A，C的值A(chǔ)VALUE[A]={A}表示A的值在內(nèi)存中AVALUE[A]={Ri,A}表示A的值即在Ri中又在內(nèi)存中AVALUE[A]={Ri}表示A的值即在Ri中基本塊的代碼生成算法設(shè)GETREG是一個(gè)函數(shù)過程，參數(shù)是形如i:A:=BopC的四元式對(duì)每個(gè)四元式，調(diào)用過程：getreg(i:A:=BopC)，返回一個(gè)寄存器R，存放A的結(jié)果值；對(duì)如何分配寄存器R，要用到四元式i上的待用信息。GETREG分配寄存器的算法如果B的現(xiàn)行值在某個(gè)寄存器Ri中，且該寄存器只包含B的值，或者B與A是同一標(biāo)識(shí)符，或B在該四元式后不再被引用，則可選取Ri為所需的寄存器R。如果有尚未分配的寄存器，則從中選用一個(gè)Ri為所需的寄存器R。GETREG分配寄存器的算法從已分配的寄存器中選取一個(gè)Ri作為所需的寄存器R，其選擇原則為：占用該寄存器的變量值同時(shí)在內(nèi)存中，或在基本塊中引用的位置最遠(yuǎn)，這樣對(duì)寄存器Ri所含的變量和變量在內(nèi)存中的情況必須做如下調(diào)整：即對(duì)RVALUE[Ri]中的每一變量M，如果M不是A且AVALUE[M]不包含M，則：GETREG分配寄存器的算法生成目標(biāo)代碼STRi，M；把不是A的變量值有送入內(nèi)存。如果M不是B，則另AVALUE[M]={M}，否則，令A(yù)VALUE[M]={M，Ri}。刪除RVALUE[Ri]中的M。分配寄存器后，進(jìn)行代碼生成，然后修改寄存器的使用信息和地址描述信息?；緣K的代碼生成算法1.分配操作寄存器getreg(i:A:=BopC)2.利用AVALUE[B]和AVALUE[C]，確定出B和C現(xiàn)行值存放位置B’和C’，如果其現(xiàn)行值在寄存器中，則把寄存器取作B’和C’；B’:=AVALUE[B]C’:=AVALUE[C]基本塊的代碼生成算法如B`≠R，則生成目標(biāo)代碼LDR,B’opR,C’否則，生成目標(biāo)代碼opR，C’如B’=Ri或C’=Ri，確定B和C占有寄存器Ri，并在四元式i后不再是活躍的，則刪除AVALUE[B]或AVALUE[