第9章目標(biāo)代碼生成課件

第9章目標(biāo)代碼生成（1）源程序編譯前端中間代碼代碼優(yōu)化中間代碼代碼生成器目標(biāo)程序符號表代碼生成器的位置第十一章目標(biāo)代碼生成第9章目標(biāo)代碼生成（1）源程序編譯前端中間代碼代碼優(yōu)化中間代1代碼生成器的輸入包括中間代碼和符號表中的信息。目標(biāo)代碼一般有以下三種形式：（1）能獨(dú)立執(zhí)行的機(jī)器語言代碼，所有地址均以定位（代真）。（2）待裝配的機(jī)器語言模塊。當(dāng)需要執(zhí)行時，由連接裝入程序把它們和某些運(yùn)行程序連接起來，轉(zhuǎn)換成能執(zhí)行的機(jī)器語言代碼。（3）匯編語言代碼，尚須經(jīng)過匯編程序匯編，轉(zhuǎn)換成可執(zhí)行的機(jī)器代碼。代碼生成器著重考慮兩個問題:一是如何使生成的目標(biāo)代碼較短；另一個是如何充分利用計(jì)算機(jī)的寄存器，減少目標(biāo)代碼中訪問存儲單元的次數(shù)。這兩個問題直接影響代碼的執(zhí)行速度。第十一章目標(biāo)代碼生成代碼生成器的輸入包括中間代碼和符號表中的信息。第十一2基本問題:所有代碼生成器都要面對何種中間代碼輸入,（是式逆波蘭，四元式，還是三元式？等問題）何種代碼做為目標(biāo)程序,選擇適當(dāng)?shù)拇a指令,最優(yōu)的寄存器分配方案,和計(jì)算順序等基本問提.為此本書見立了目標(biāo)機(jī)器模型:并把中間代碼對應(yīng)的目標(biāo)代碼做了規(guī)定.利用待用信息,寄存器描述數(shù)組RVALUE,變量地址描述數(shù)組AVALUE等概念建立了代碼生成算法.P316[例11。2]同學(xué)們應(yīng)該好好研究。P317表11。4各中間代碼對應(yīng)的目標(biāo)代碼應(yīng)該背過。寄存器分配：利用執(zhí)行代價的概念說明如何建立更佳的寄存器分配方案。對于循環(huán)L中某變量M，如果分配一個寄存器給它專用，那么，每執(zhí)行循環(huán)一次，執(zhí)行代價的節(jié)省數(shù)可用公式（11。1）計(jì)算。這個計(jì)算公式應(yīng)該掌握。第十一章目標(biāo)代碼生成基本問題:所有代碼生成器都要面對何種中間代碼輸入,（是式逆3[例11。3]圖11。4代表某程序的最內(nèi)層循環(huán)，其中無條件轉(zhuǎn)移和條件轉(zhuǎn)移指令均以改用箭頭來表示。各基本塊入口之前和出口之后的活躍變量已列在圖中。假定R0,R1和R2三個寄存器在該循環(huán)中將固定分配給某三個變量使用?，F(xiàn)在，我們利用公式（11。1）計(jì)算各變量的執(zhí)行代價節(jié)省數(shù)，并且取執(zhí)行代價節(jié)省數(shù)最高的來確定這三個變量。解：因?yàn)锽1中引用a前已對a定值，所以use(a,B1)=0;在B2,B3中a被各引用一次，且在引用前未對a定值，所以use(a,B2)=use(a,B3)=1;B4中未引用a，所以use(a,B4)=0.因?yàn)閍在B1中被定值且a在B1出口是活躍的，a在B2,B3和B4出口后不是活躍的則：live(a,B1)=1Live(a,B2)=live(a,B3)=live(a,B4)=0;所以代價節(jié)省數(shù)為：1+1+2*1=4。第十一章目標(biāo)代碼生成[例11。3]圖11。4代表某程序的最內(nèi)層循環(huán)，其中無條4同樣可以算出b,c,d,e,f的執(zhí)行代價節(jié)省數(shù)分別為：6，3，6，4，4。按照代價節(jié)省數(shù)的大小我們把寄存器R0分配給d,R1分配給b;a,e,f的執(zhí)行代價相同,可人選其一將R2分配給a.DAG的目標(biāo)代碼為了生成更有效的目標(biāo)代碼，要考慮的另一個問題是，對基本塊中中間代碼序列，我們應(yīng)按怎樣的次序來生成其目標(biāo)代碼呢？本節(jié)P323給出了利用基本塊的DAG圖給出了基本塊中中間代碼序列排序的方法，以便生成較優(yōu)的目標(biāo)代碼。下面我們學(xué)習(xí)一個例子，一加深其理解：[例11。6]考察下面中間代碼序列G1:第十一章目標(biāo)代碼生成同樣可以算出b,c,d,e,f的執(zhí)行5T1:=A+BT2:=A-BF:=T1*T2T1:=A-BT2:=A–CT3:=B-CT1:=T1*T2G:=T1*T3其對應(yīng)的DAG如圖ABC+n1--n2n4T2**-Fn3*Gn7T3n5T1n6A第十一章目標(biāo)代碼生成T1:=A+BABC+n1--n2n46上圖的DAG含有7個結(jié)點(diǎn)，我們應(yīng)用課本中的算法。把它們排序，主要步驟如下。第一步置初值：i=7；T的所有元素全為空null。內(nèi)部結(jié)點(diǎn)n3和n7均滿足第三步的要求，假定我們選取T[7]為結(jié)點(diǎn)n3。結(jié)點(diǎn)n3的最左子結(jié)點(diǎn)（內(nèi)部）n1滿足第5步的要求，因此按第6步，T[6]=n1.但n1的最左子結(jié)A為葉結(jié)，不滿足第6步的要求。則現(xiàn)在只有n7滿足第3步要求，于是T[5]=n7。結(jié)點(diǎn)n7的最左子結(jié)n6滿足第5步的要求，因此T[4]=n6。結(jié)點(diǎn)n6的最左子結(jié)點(diǎn)n2同樣滿足第5步的要求，因此T[3]=n2.余下的滿足第3步要求的尚有n4和n5，假定選取T[2]=n4。當(dāng)把n5列為T[1]后，算法工作結(jié)束。至此，我們求出的圖的內(nèi)結(jié)點(diǎn)順序?yàn)椋簄5,n4,n2,n6,n1,n3.按這個次序從新表示中間代碼序列為G1‘為：T3:=B-C;T2:=A-C;S1:=A–B;T1:=S1*T2;G:=T1*T3;S2:=A+B;F:=S2*S1。如前所述按后一個中間代碼序列生成中間代碼將會較優(yōu)。第十一章目標(biāo)代碼生成上圖的DAG含有7個結(jié)點(diǎn)，我們應(yīng)用課本中的算法。把它們7窺孔優(yōu)化幾種窺孔優(yōu)化的方法都比較好理解，這里不再重述課本內(nèi)容。第十一章目標(biāo)代碼生成窺孔優(yōu)化第十一章目標(biāo)代碼生成8例題與習(xí)題解答[例11。1]假設(shè)只有R0和R1兩個寄存器，對賦值語句d=(a-b)+(a-c)+(a-c)生成目標(biāo)代碼。并寫出寄存器描述數(shù)組RVALUE和變量地址描述數(shù)組AVALUE.該賦值語句的三地址序列：t:=a-bt1:=a-ct2:=t+t1d:=t1+t2將此代碼看成一基本塊，并設(shè)在基本塊末尾，變量d是活躍的。生成目標(biāo)代碼表如圖：第十一章目標(biāo)代碼生成例題與習(xí)題解答[例11。1]假設(shè)只有R0和R1兩個寄存器，對9

中間代碼目標(biāo)代碼RVALUEAVALUEt:=a-bLDR0,aR0含tt在R0中SUBR0,bt1:=a-cLDR1,aR0含tt在R0中SUBR1,cR1含t1t1在R1中t2:=t+t1ADDR0,R1R0含t2t2在R0中R1含t1t1在R1中d:=t1+t2ADDR0,R1R0含dd在R0中STR0,dd在R0和存儲器中第十一章目標(biāo)代碼生成第十一章目標(biāo)代碼生成10[例11。2]（k3）假設(shè)R0,R1和R2為可用寄存器，試對以下各表達(dá)式分別生成最優(yōu)目標(biāo)代碼。A+(B+(C*(D+E/F+G)*H))+(I*J)解：首先生成三地址中間代碼序列：T1:=E/FT2:=D+T1T3:=G+T2T4:=C*T3T5:=H*T4T6:=B+T5T7:=A+T6T8:=I*JT9:=T7+T8第十一章目標(biāo)代碼生成[例11。2]（k3）第十一章目標(biāo)代碼生成11最優(yōu)的目標(biāo)代碼：LDR0,EDIVR0,FADDR0,GMULR0,HMULR0,CADDR0,BADDR0,ALDR1,IMULR1,JADDR0,R1[例11。3]（K1）對以下中間代碼序列G:第十一章目標(biāo)代碼生成最優(yōu)的目標(biāo)代碼：第十一章目標(biāo)代碼生成12T1:=B–CT2:=A*T1T3:=D+1T4:=E–FT5:=T3*T4W:=T2/T5假設(shè)可用寄存器為R0和R1，W是基本塊出口的活躍變量，用簡單代碼生成算法生成目標(biāo)代碼，同時列出代碼生成過程中的寄存器描述和變量地址描述。中間代碼目標(biāo)代碼RVALUEAVALUET1:=B-CLDR0,BR0含T1T1在R0中SUBR0,CT2:=A*T1MULR0,AR0含T2T2在R0中STR0,T2T2同時在R0和存儲器中T3:=D+1LDR1,DR1含T3T3在R1中第十一章目標(biāo)代碼生成T1:=B–C第十一章目標(biāo)代碼生成13ADDR1,#1T4:=E-FLDR0,ER0含T4T4在R0中SUBR0,FT5:=T3*T4MULR1,R0R1含T5T5在R1中LDR0,T2R0含T2T2在R0和存儲器中W:=T2/T5DIVR0,R1R0含WW在R0中STR0,WW在R0和存儲器中第十一章目標(biāo)代碼生成ADDR1,14第十一章目標(biāo)代碼生成第十一章目標(biāo)代碼生成15編譯原理

優(yōu)化和目標(biāo)代碼生成(2h)主講：蔣偉進(jìn)教授2007.03-05第十一章目標(biāo)代碼生成編譯原理

優(yōu)化和目標(biāo)代碼生成(2h)第十一章目標(biāo)代碼生成16第七章編譯程序

７．1

編譯程序考慮的因素７．2

執(zhí)行時的內(nèi)存分配７．3

代碼優(yōu)化第十一章目標(biāo)代碼生成第七章編譯程序７．1編譯程序考慮的因素７．2執(zhí)行時177.1編譯程序考慮的因素編譯程序設(shè)計(jì)時，除了需要用到前面介紹的分析技術(shù)和制導(dǎo)翻譯外，還要考慮如何從源程序數(shù)據(jù)空間映射到具體物理存儲空間，也就是運(yùn)行時的數(shù)據(jù)表示。在運(yùn)行的時候如何組織或存放數(shù)據(jù)、在源程序中同名標(biāo)識符是怎么樣描述不同的對象、運(yùn)行時的程序控制權(quán)是如何轉(zhuǎn)移的，參數(shù)是如何傳遞以及如何生成質(zhì)量較高的目標(biāo)代碼都是編譯程序設(shè)計(jì)者應(yīng)該考慮的問題。第十一章目標(biāo)代碼生成7.1編譯程序考慮的因素編譯程序設(shè)計(jì)時，除了需要用到187.1.1數(shù)據(jù)類型類型的合法性檢查是判斷數(shù)據(jù)類型是否與上下文的要求一致數(shù)據(jù)類型是對該類型數(shù)據(jù)（變量或常量）的取值是否合法以及對該類型數(shù)據(jù)的運(yùn)算是否合法的一種說明。第十一章目標(biāo)代碼生成7.1.1數(shù)據(jù)類型類型的合法性檢查是判斷數(shù)據(jù)類型是否與上下197.1.2數(shù)據(jù)結(jié)構(gòu)一個程序設(shè)計(jì)語言如允許使用的數(shù)組、記錄、字符串、表、棧等形式的數(shù)據(jù)結(jié)構(gòu)，在編譯程序中應(yīng)為它們提供相應(yīng)的翻譯。為了能對數(shù)據(jù)結(jié)構(gòu)中的元素進(jìn)行引用，必須完成從邏輯結(jié)構(gòu)到能夠訪問這些數(shù)據(jù)元素的物理結(jié)構(gòu)的映射。應(yīng)考慮：１映射算法相對簡單，根據(jù)邏輯結(jié)構(gòu)容易計(jì)算出物理地址２從邏輯結(jié)構(gòu)投影到物理結(jié)構(gòu)時，不至于超界或存儲溢出３使用的數(shù)據(jù)結(jié)構(gòu)承擔(dān)這種程序設(shè)計(jì)語言的主要功能４在這些數(shù)據(jù)結(jié)構(gòu)定義相關(guān)的運(yùn)算第十一章目標(biāo)代碼生成7.1.2數(shù)據(jù)結(jié)構(gòu)一個程序設(shè)計(jì)語言如允許使用的數(shù)組、記207.1.3作用域規(guī)則一個程序設(shè)計(jì)語言的作用域規(guī)則確定了該程序設(shè)計(jì)語言的某個程序的不同程序塊中所說明的標(biāo)識符的可訪問性。從另外一個角度看，在程序中當(dāng)訪問一個標(biāo)識符通過作用域規(guī)則可確定究竟訪問的是哪一個實(shí)體中說明的標(biāo)識符。通常一個程序設(shè)計(jì)語言的一個標(biāo)識符或數(shù)據(jù)項(xiàng)的作用域是在說明該標(biāo)識符或數(shù)據(jù)項(xiàng)的程序塊內(nèi)。第十一章目標(biāo)代碼生成7.1.3作用域規(guī)則一個程序設(shè)計(jì)語言的作用域規(guī)則確定了該程217.1.4控制結(jié)構(gòu)一個程序設(shè)計(jì)語言的控制結(jié)構(gòu)是該語言在程序運(yùn)行期間用于改變控制流的語言特征集合。第十一章目標(biāo)代碼生成7.1.4控制結(jié)構(gòu)一個程序設(shè)計(jì)語言的控制結(jié)構(gòu)是該語言在程序22７.2執(zhí)行時的內(nèi)存分配編譯程序需要為源程序中的數(shù)據(jù)分配執(zhí)行時的存儲空間，編譯程序從操作系統(tǒng)中申請編譯程序計(jì)算出的所需的內(nèi)存，或編譯程序生成在運(yùn)行時需申請內(nèi)存的指令。（１）確定用來表示某一數(shù)據(jù)項(xiàng)的內(nèi)存大小。（２）使用適當(dāng)?shù)膬?nèi)存分配策略，實(shí)現(xiàn)具體數(shù)據(jù)的作用域和生存期。（３）確定以適當(dāng)?shù)乃惴ㄔL問生存期內(nèi)的數(shù)據(jù)，包括基本型數(shù)據(jù)結(jié)構(gòu)構(gòu)造類型。第十一章目標(biāo)代碼生成７.2執(zhí)行時的內(nèi)存分配編譯程序需要為源程序中的數(shù)據(jù)分配執(zhí)23為目標(biāo)程序分配執(zhí)行時所需的存儲空間：一種是在目標(biāo)程序運(yùn)行前，由編譯程序?yàn)閿?shù)據(jù)結(jié)構(gòu)分配存儲空間，在程序的執(zhí)行期間不再分配和解除這種內(nèi)存分配。叫做靜態(tài)存儲分配。一種在程序運(yùn)行期間均可以對內(nèi)存實(shí)現(xiàn)分配或解除分配，一旦存儲分配解除該存儲空間內(nèi)的數(shù)據(jù)便失去意義。叫做動態(tài)存儲分配。第十一章目標(biāo)代碼生成為目標(biāo)程序分配執(zhí)行時所需的存儲空間：第十一章目標(biāo)代碼生成24宗旨：

獲得較好性能的代碼

階段：sourcefrontI.Rcodetargetcodeendgeneratorcode用戶中間代碼優(yōu)化目標(biāo)代碼優(yōu)化什么是代碼優(yōu)化７.３代碼優(yōu)化第十一章目標(biāo)代碼生成宗旨：獲得較好性能的代碼25例：intarr[10000];voidBinky(){inti;for(i=0;i<10000;i++)arr[i]=1;}intarr[10000];voidWinky(){registerint*p;for(p=arr;p<arr+10000;p++)*p=1;}第十一章目標(biāo)代碼生成例：intarr[10000];intarr[1000026目標(biāo)：作為一個高級語言的使用者很希望編譯程序所產(chǎn)生的代碼能夠和直接用機(jī)器語言編寫的程序效果一樣好。代碼優(yōu)化是指對原代碼進(jìn)行的變換，從而獲得在時間和空間上效率相對高的程序，且一般也不是在時間和空間上最省的程序，在進(jìn)行優(yōu)化時應(yīng)該做到：１代碼的變換必須保持原程序的語義。２從理論上，變換加快了程序的速度。３這種變換是值得的第十一章目標(biāo)代碼生成目標(biāo)：作為一個高級語言的使用者很希望編譯程序所產(chǎn)生的代碼能27優(yōu)化分類按階段分:與機(jī)器無關(guān)的優(yōu)化---對中間代碼進(jìn)行依賴于機(jī)器的優(yōu)化---對目標(biāo)代碼進(jìn)行根據(jù)優(yōu)化所涉及的程序范圍分成:(1)局部優(yōu)化:(基本塊)應(yīng)用于僅包含少量語句的小程序的優(yōu)化變換。(2)循環(huán)優(yōu)化:對循環(huán)中的代碼進(jìn)行優(yōu)化(3)全局優(yōu)化:大范圍的優(yōu)化應(yīng)用于一個程序單元，如一個函數(shù)或一個過程的優(yōu)化變換。第十一章目標(biāo)代碼生成優(yōu)化分類按階段分:第十一章目標(biāo)代碼生成28程序的執(zhí)行效率是可以通過在編譯期間進(jìn)行優(yōu)化變換，不改變語義重寫程序段以提高程序的工作效率。雖然變換的方法很多，但是常用的大致有以下幾種：１編譯求值２合并預(yù)算３刪除死碼４減少頻率５強(qiáng)度削弱和變換循環(huán)條件６減少重寫傳播第十一章目標(biāo)代碼生成程序的執(zhí)行效率是可以通過在編譯期間進(jìn)行優(yōu)化變換，不改變語義重29局部優(yōu)化：所需要的開銷相對較低，因此從優(yōu)化所得到的收益也相對較低。局部優(yōu)化只是在較小的程序段中進(jìn)行優(yōu)化，從而到達(dá)優(yōu)化的目的。這種程序段稱為基本段。全局優(yōu)化：要產(chǎn)生高效的代碼，編譯程序僅在基本塊內(nèi)優(yōu)化是不夠的，編譯程序應(yīng)把程序作為一個整體來考慮，對各個基本塊的信息進(jìn)行數(shù)據(jù)流的分析從而達(dá)到優(yōu)化的目的。全局優(yōu)化同局部優(yōu)化相比，全局優(yōu)化需要更多的分析，以便確定優(yōu)化的可行性。第十一章目標(biāo)代碼生成局部優(yōu)化：所需要的開銷相對較低，因此從優(yōu)化所得到的收益也相30優(yōu)化的原則等價原則有效原則時間空間合算原則優(yōu)化的代價效果第十一章目標(biāo)代碼生成優(yōu)化的原則等價原則第十一章目標(biāo)代碼生成31優(yōu)化的基本方法去處冗余削減強(qiáng)度使用更快的指令第十一章目標(biāo)代碼生成優(yōu)化的基本方法去處冗余第十一章目標(biāo)代碼生成32局部優(yōu)化方法合并已知量臨時變量改名交換語句位置代數(shù)變換第十一章目標(biāo)代碼生成局部優(yōu)化方法第十一章目標(biāo)代碼生成33循環(huán)優(yōu)化代碼外提強(qiáng)度削弱A=A+1A++刪除歸納變量例如循環(huán)中加法變?yōu)?，循環(huán)外乘法第十一章目標(biāo)代碼生成循環(huán)優(yōu)化代碼外提第十一章目標(biāo)代碼生成34窺孔優(yōu)化窺孔目標(biāo)程序中的一個可以移動的窗口優(yōu)化方法冗余存取不可到達(dá)代碼控制流優(yōu)化強(qiáng)度削弱刪除無用操作第十一章目標(biāo)代碼生成窺孔優(yōu)化窺孔第十一章目標(biāo)代碼生成35

7.4代碼生成要考慮的主要問題——具體細(xì)節(jié)依賴于目標(biāo)機(jī)器和操作系統(tǒng)共同的問題：充分利用寄存器基本塊中全局寄存器分配：不把寄存器平均分配給各個變量使用，而是從可用的寄存器中分出幾個，固定分配給幾個變量單獨(dú)使用。標(biāo)準(zhǔn)：以各變量在循環(huán)內(nèi)需要訪問主存單元的次數(shù)為標(biāo)準(zhǔn)。選擇計(jì)算機(jī)指令系統(tǒng)選擇計(jì)算次序第十一章目標(biāo)代碼生成7.4代碼生成要考慮的主要問題——具體細(xì)節(jié)依賴于目標(biāo)機(jī)器36

目標(biāo)代碼的三種形式

地址代真的機(jī)器代碼待裝配的機(jī)器代碼模塊匯編語言（宏匯編）

機(jī)器指令形式(opsource,destination)ADDs