編譯原理之

代碼生成華東交通大學(xué)軟件學(xué)院萬仲保代碼生成概述目標代碼的主要目標目標代碼的主要形式生成目標代碼衡量指標計算機模型簡單的代碼生成器全局寄存器分配代碼生成概述代碼生成是把經(jīng)過語法分析或優(yōu)化后的中間代碼作為輸入，將其轉(zhuǎn)換成特定機器的機器語言或匯編語言作為輸出，這樣的轉(zhuǎn)換程序稱為代碼生成器。代碼生成的任務(wù)是在編譯前端生成的中間代碼的基礎(chǔ)上，生成等價有效的目標代碼，這也是一種程序變換，變換的結(jié)果是產(chǎn)生目標代碼。等價是任一種程序變換的基本要求，因此討論將集中在目標代碼和如何產(chǎn)生有效的目標代碼上。有效，是指目標代碼占用的空間要省，運行的時間要短，這涉及充分利用寄存器和生成優(yōu)化的代碼序列的問題。目標代碼的主要目標第一．使所生成的目標代碼盡可能地短。第二，能較充分地發(fā)揮目標計算機可用資源的效率，如盡可能地使用執(zhí)行速度較快的指令；充分利用計算機的寄存器或變址器，以節(jié)省訪問內(nèi)存的時間，等等。目標代碼的主要形式具有絕對地址的機器語言程序可浮動的機器語言程序匯編語言形式的程序絕對地址的機器語言程序優(yōu)點：最為有效，因為它們在存儲空間中有固定的位置，一旦產(chǎn)生出此種形式的目標程序之后，便可直接投入運行。缺點：不能獨立地完成源程序各程序塊的編譯，即使是供源程序調(diào)用的子程序也必須同時進行編譯，因而靈活性較差。通常是在程序較短，而調(diào)試工作量較大的情況下，采用此種方式?？筛拥臋C器語言程序有較大的靈活性，故為許多編譯程序所采用，只有執(zhí)行連接裝入程序本身需耗費一些時間。目標程序由若干個目的模塊組成，各個模塊中都包含目標程序中的一部分代碼，且這些代碼可在存儲空間進行浮動(即可將它們裝入到存儲空間的任何位置)。此外，在各目的模塊中還含有一些連接信息(如本模塊需引用的其它模塊中的符號名或子程序入口名)。對此種形式的目標代碼，需經(jīng)過連接裝入程序把它們和所需的運行子程序的目的模塊連接起來之后，才能投入運行。匯編語言形式的程序匯編語言形式較容易實現(xiàn)一些，但需在編譯完畢之后額外增加一個匯編目標程序的階段。盡管此種方式有某些優(yōu)點，但并不是一種最好的方案。計算機模型假定一個計算機具有n個通用寄存器為R0，R1，…，Rn-l。它們既可作為累加器又可作為變址器，設(shè)定：用“op”表示運算符；用“M”表示內(nèi)存單元；用變量名表示該變量所在的單元；“C”表示常量；“*”表示間址方式存取。模型機的指令形式模型機主要指令的意義模型機尋址方式模型機的指令形式類型指令形式意義（設(shè)op是二目運算符）直接地址型opRi,M(Ri)opM?Ri寄存器型opRi,Rj(Ri)op(Rj)?Ri變址型opRi,c(Rj)(Ri)op((Rj)+c)?Ri間接型opRi,*M(Ri)op(M)?RiopRi,*Rj(Ri)op((Rj))?RiopRi,*c(Rj)(Ri)op(((Rj)+c))?Ri模型機主要指令的意義指令意義指令意義LDRi，B把B單元的內(nèi)容取到寄存器R，即(B)?RiJ<XJ≤X如CT＝0轉(zhuǎn)X單元。如CT=0或CT＝1轉(zhuǎn)X單元。STRi，B把寄存器Ri的內(nèi)容存到B單元，即(Ri)?BJ=X如CT＝1轉(zhuǎn)X單元。JB無條件轉(zhuǎn)向X單元J≠X如CT≠1轉(zhuǎn)X單元。CMPA，B把A單元和B單元的值進行比較，并根據(jù)比較情況把機器內(nèi)部特征寄存器CT置成相應(yīng)狀態(tài)。根據(jù)A＜B或A＝B或A>B分別置CT為0或1或2。J>X

J≥X如CT＝2轉(zhuǎn)X單元。如CT＝2或CT=1轉(zhuǎn)X單元。模型機尋址方式編碼名稱助記符含義匯編后的情況1寄存器模式R(R)為操作數(shù)2間接寄存模式*R(R)為操作數(shù)地址3變址模式X(R)(R)+X為操作數(shù)地址X之值在本指令之后的單元中4間接變址模式*X(R)(R)+X為存放操作數(shù)地址的單元地址X之值在本指令之后的單元中5直接操作數(shù)#XX為操作數(shù)文字常數(shù)X在本指令之后的單元中6絕對地址XX為符號名，其值為操作數(shù)X的數(shù)據(jù)單元地址在本指令之后的單元中7間接地址*XX為符號名，其值為操作數(shù)地址X的數(shù)據(jù)單元地址在本指令之后的單元中生成目標代碼衡量指標目標程序（指令條數(shù)）；執(zhí)行目標程序所占的機器時間；目標程序所有指令執(zhí)行代價的總和。簡單的代碼生成器寄存器分配的原則待用信息鏈表法代碼生成算法寄存器分配的原則(1)當(dāng)生成某變量的目標代碼時，盡量讓變量的值或計算結(jié)果保留在寄存器中直到寄存器不夠分配時為止，這樣引用變量值時可減少對內(nèi)存的存取次數(shù)，以提高運行速度。(2)當(dāng)?shù)交緣K出口時，將變量的值存放在內(nèi)存中，因為一個基本塊可能有多個后繼結(jié)點或多個前驅(qū)結(jié)點，同一個變量名在不同前驅(qū)結(jié)點的基本塊內(nèi)出口前存放的R可能不同，或沒有定值，所以應(yīng)在出口前把寄存器的內(nèi)容放在內(nèi)存中，這樣從基本塊外入口的變量值都在內(nèi)存中。(3)對于在一個基本塊內(nèi)后邊不再被引用的變量所占用的寄存器應(yīng)盡早釋放，以提高寄存器的利用效率。待用信息鏈表法待用信息：在基本塊B中，變量A在i點的值，j點引用，并且i→j的通路上沒有A的其他定值和引用，則j為i處A的下一個引用點，即待用信息。計算變量待用信息的步驟示例計算變量待用信息的步驟(1)對各基本塊的符號表中的“待用信息”欄和“活躍信息”欄置初值，即把“待用作息”欄置“非待用”，對“活躍信息”欄按在基本塊出口處是否為活躍而置成“活躍”或“非活躍”。這里假定變量都是活躍的，臨時變量都是非活躍的。(2)從基本塊出口到基本塊入口由后向前依次處理每個四元式i：A：=BopC，依次執(zhí)行下述步驟：a)把符號表中變量A的待用信息和活躍信息附加到四元式i上。b)把符號表中變量A的待用信息欄和活躍信息欄分別置為“非待用”和“非活躍”。(由于在i中對A的定值只能在i以后的四元式才能引用，因而對i以前的四元式卻說，A是不活躍也不可能是待用的）c)把符號表中B和C的待用信息和活躍信息附加到四元式i上。d)把符號表中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待用信息和活躍信息在四元式上的標記四元式的序號四元式上的標記(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+UFF代碼生成算法寄存器描述:為了在代碼生成中充分利用寄存器，生成盡可能簡短的代碼，將使用寄存器描述數(shù)組RVALUE[Ri]記錄寄存器Ri是空閑著，還是已分配給某些變量。地址描述：將使用變量地址描述數(shù)組AVALUE[A]來記錄變量A的現(xiàn)行值是存放在某個寄存器中，還是在某個主存單元中，或者既在寄存器中又在主存中。相關(guān)約定GETREG分配寄存器的算法代碼生成算法相關(guān)約定過程函數(shù)GETREG(P:x:=yopz)給出參數(shù)P：x:=yopz，當(dāng)然也意味著給出了語句P處的待用信息、活躍信息及當(dāng)時各寄存器描述數(shù)組和變量地址描述數(shù)組，據(jù)此，為變量x分配寄存器R，以R作為函數(shù)值返回。RVALUE[Ri]＝{A，C}表示Ri的現(xiàn)行值是變量A，C的值。VALUE[A]＝{A}表示A的值在內(nèi)存中。AVALUE[A]＝{Ri，A}表示A的值在寄存器Ri中又在內(nèi)存中。AVALUE[A]＝{Ri}表示變量A的值在寄存器Ri中。GETREG分配寄存器的算法(1)如果B的現(xiàn)行值在某寄存器Ri中，且該寄存器只包含B的值，或者B與A是同一標識符，或B在該四元式后不會再被引用，則可選取Ri為所需的寄存器R，并轉(zhuǎn)(4)。(2)如果有尚未分配的寄存器，則從中選用一個Ri為所需的寄存器R，并轉(zhuǎn)(4)。(3)從已分配的寄存器中選取一個Ri作為所需寄存器R，其選擇原則為：占用該寄存器的變量值同時在主存中，或在基本塊中引用的位置最遠。這樣對寄存器Ri所含的變量和變量在主存中的情況必須先做如下調(diào)整：即對RVALU[Ri]中的每一變量M，如果M不是A且AVALUE[M]不包含M，則需完成以下處理：a)生成目標代碼STRi，M；即把不是A的變量值由Ri中送入內(nèi)存中。b)如果M不是B，則令A(yù)VALUE[M]={M}，否則，令A(yù)VALUE[M]={M，R}。c)刪除RVALU[Ri]中的M。(4)給出R，返回。這樣，一旦得到了一個為四元式運算的操作寄存器R，就可以進行代碼生成，而當(dāng)目標代碼生成完成后，則又需修改寄存器的使用信息和地址描述信息。算法的流程圖GETREG算法的流程圖開始B’=R?C’=R?B’是否待用?B’=Ri?C’是否待用?C’=Ri?修改B的地址描述AVALUE[B]：=AVALUE[B]-{R}修改C的地址描述AVALUE[C]：=AVALUE[C]-{R}修改A的地址描述AVALUE[A]：={R}AVALUE[R]：={A}釋放B所占用的寄存器RiRVALUE[Ri]：=RVALUE[Ri]-{B}AVALUE[B]：=AVALUE[B]-{Ri}釋放C所占用的寄存器RiRVALUE[Ri]：=RVALUE[Ri]-{C}AVALUE[C]：=AVALUE[C]-{Ri}結(jié)束YNYYYNNNNYY代碼生成算法對于語句P：x:=yopz，執(zhí)行下列步驟：(1)調(diào)用GETREG(P：x:=yopz)，設(shè)返回的寄存器為R，供x存放現(xiàn)行值。(2)由變量地址描述數(shù)組AVALUE[y]、AVALUE[z]確定變量y、z的現(xiàn)行值存放位置y′，z′，當(dāng)現(xiàn)行值在寄存器中時，便將該寄存器作為y′或z′。(3)如果y′≠R，生成目標代碼MOVy′RopRz′否則只生成目標代碼opRz′。當(dāng)y′或z′為R時，刪除AVALUE[y]或AVALUE[z]中的R。(4)修改兩個描述數(shù)組，表示x占用R，即含AVALUE[x]={R}，RVALUE[R]={x}。

(5)如果在P點y或z不再被引用(不待用，不活躍)，并且其現(xiàn)行值占用某寄存器R′，則釋放該寄存器R′，即從RVALUE[R′]中刪去y或z，從AVALUE[y]或AVALUE[z]中刪去R′。代碼生成算法的流程圖開始結(jié)束分配操作寄存器R：GETREG（i：A：=BopC）取B，C現(xiàn)行存放的位置B’，C’B：=AVALUE[B]C：=AVALUE[C]B’=R?生成目標碼opRC’生成目標碼LDR，B’opRC’修改寄存器使用的信息和地址描述信息YN全局寄存器分配四元式的目標代碼形式分配寄存器的原則：降低目標代碼執(zhí)行代價。分配寄存器的策略計算目標代碼執(zhí)行代價的方法執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行代價總數(shù)計算執(zhí)行代價需考慮因素示例四元式的目標代碼形式四元式指令說明A：=BMOVB，R若當(dāng)前B的值在其一寄存器R中，則不必產(chǎn)生目標代碼，而只須把A添加到R的描述符中，并把A的地址描述符置為R(即指明A的當(dāng)前值僅在R中)即可。當(dāng)B在塊中不再被引用且在塊的出口之后不活躍時，還應(yīng)從R的描述符中刪去B，從B的地址描述符中刪去R。但若B的當(dāng)前值只在內(nèi)存單元中，如果僅簡單地把A的地址描述符置為B的內(nèi)存地址，那么，若不對A的值采取保護措施，A的值就會為B的再定值所影響?？梢?，在此情況下，還是為它產(chǎn)生一條形如MOVB，R的指令較為穩(wěn)妥。R是分配給A的寄存器。A：=opB對它的處理與對二元運算的處理極為類似。A：=B[I]MOVI，RMOVB(R),R執(zhí)行代價為5，I的當(dāng)前值不在寄存器中，則產(chǎn)生之。MOVB(Ri),R執(zhí)行代價為3，I的當(dāng)前值在某一寄存器Ri中時，則僅產(chǎn)生之。A[T]:=BMOVI,RMOVB,A(Ri)執(zhí)行代價為6，I的當(dāng)前值不在寄存器中，則產(chǎn)生之。MOVB,A(Ri)執(zhí)行代價為4，I的當(dāng)前值在某一寄存器Ri中時，則僅產(chǎn)生之。四元式的目標代碼形式(二)四元式指令說明A:=P↑MOV*P,A執(zhí)行代價為4MOVP,RMOV*R,R執(zhí)行代價為4MOV*Ri,R2，特別，當(dāng)P的當(dāng)前值在某一寄存器R6中時，可產(chǎn)生的指令。如果A的當(dāng)前值在塊內(nèi)還會被引用，且此時尚有未被占用的寄存器R供A使用，則最好按第二或第三種形式產(chǎn)生目標代碼。P↑:=AMOVA,*PMOVA,RMOVR,*PMOVA,*RgotoXBRX’X’是序號為X的四元式的目標代碼首址。IfAropbgotoXCMPA,BJropX’X’是序號為X的四元式的目標代碼首址。如果A和(或)B的當(dāng)前值在寄存器中，則在產(chǎn)生目標代碼時，應(yīng)盡可能用寄存器尋址模式。分配寄存器的策略首先，所考慮的范圍需從一個基本塊擴大至一個循環(huán)L，故對于在L的某基本塊B中定值的變量V，如果它已占用一個固定的寄存器，而且V在B的出口之后活躍，則不必再把V的值存放到內(nèi)存單元之中。其次，對于循環(huán)中的每一變量V，還需估計當(dāng)它獨占一個寄存器時，對于降低執(zhí)行代價的效果有多大。顯然，應(yīng)將寄存器優(yōu)先分配給那些降低執(zhí)行代價效果最為顯著的一些變量。計算目標代碼執(zhí)行代價的方法如果V在B中被定值，且V的定值點之后有其引用點，則按生成代碼算法為B生成代碼時，一般是把V的當(dāng)前值保留在某一寄存器R中。如果在整個循環(huán)L中，把R作為V的一個獨占寄存器，則對于基本塊B而言，不僅V的定值點之后的引用點可引用R中之值，而且其前的V的引用點也可以引用(甚至在L的其它基本塊中也同樣可以引用，如果該V的定值能到達這些引用點的話)。然而，在生成代碼算法中，僅考慮了前一情況，而對后一情況卻未加以考慮(因為生成代碼算法并未把R作為V的一個獨占寄存器)，因此，在現(xiàn)在的情況下，對于B中V的定值點之前的那些四元式，如果在為它們生成目標代碼時，也把對v的引用處理為對R內(nèi)容的引用，則使其中的每一個對V的引用都節(jié)省了執(zhí)行代價1。由于現(xiàn)在已為B中的變量V分配了固定的寄存器，因此，當(dāng)V在B的出口之后活躍時，也就不必把V的值送入內(nèi)存，這樣一來，就使執(zhí)行代價又節(jié)省了2。執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行代價總數(shù)對于循環(huán)L中的某一變量，當(dāng)給它分配了一個固定的寄存器之后，則每執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行代價總數(shù)(相對于按代碼生成算法生成的代碼)為：

＝(USE(V，B)+2*LIVE(V，B))（B?L）其中：USE(V，B)為基本塊B中V的定值點之前對V引用的次數(shù)；1當(dāng)V在B中定值，且V在B的出口之后活躍LIVE（V，B）＝0其它計算執(zhí)行代價需考慮因素1．若V在L的入口之前是活躍的，且在L中已給V分配了固定的寄存器R，則應(yīng)在L的前置結(jié)點中，產(chǎn)生將V之值從內(nèi)存單元取至R的指令，故所增加的執(zhí)行代價為2。此外，對于循環(huán)的每一出口塊B，設(shè)B’是B在循環(huán)外的一個直接后繼塊，若V在B’前活躍，則當(dāng)由B退出循環(huán)時，應(yīng)將V的當(dāng)前值由R送入內(nèi)存，由此可能增加的執(zhí)行代價為2，好在上述兩方面的操作僅分別在循環(huán)的入口之前和退出循環(huán)時執(zhí)行一次，故將它們略去不計將不會對之值產(chǎn)生太大的影響。2．執(zhí)行代價計算公式是在這樣的假定下推出的，即每循環(huán)一次都遍及循環(huán)中的各個基本塊，然而實際情況并非總是如此，有時甚至?xí)?/p>