第12章-代碼生成課件

第十二章代碼生成12.1代碼生成概述12.2一個(gè)簡(jiǎn)單的代碼生成程序12.3幾種常用的代碼生成程序的開(kāi)發(fā)方法12.4全局寄存器分配12.5代碼生成程序的自動(dòng)化構(gòu)造第十二章代碼生成12.1代碼生成概述12.1代碼生成概述12.1.1目標(biāo)代碼的三種形式:能夠立即執(zhí)行的機(jī)器語(yǔ)言代碼，所有地址均已定位；待裝配的機(jī)器代碼模塊，當(dāng)需要執(zhí)行時(shí)，由連接裝入程序把它們和某些運(yùn)行程序連接起來(lái)，轉(zhuǎn)換成能執(zhí)行的機(jī)器語(yǔ)言代碼；匯編語(yǔ)言代碼，需經(jīng)過(guò)匯編程序匯編，轉(zhuǎn)換成可立即執(zhí)行的機(jī)器語(yǔ)言代碼。12.1代碼生成概述12.1.1目標(biāo)代碼的三種形式:

12.1.2代碼生成要考慮的主要問(wèn)題——具體細(xì)節(jié)依賴于目標(biāo)機(jī)器和操作系統(tǒng)(1)代碼生成程序的輸入線性表示、三地址表示、圖形表示(2)計(jì)算機(jī)指令的選擇x:=y+zLDR0,yADDR0,zSTR0,xa:=a+1INCa(3)充分利用寄存器(寄存器分配)(4)選擇計(jì)算次序(指令調(diào)度)

12.1.2代碼生成要考慮的主要問(wèn)題——具體細(xì)節(jié)依賴于12.2簡(jiǎn)單的代碼生成程序12.2.1計(jì)算機(jī)模型機(jī)器指令形式指令意義opRi,M(Ri)op(M)=>RiopRi,Rj(Ri)op(Rj)=>RiopRi,c(Rj)(Ri)op((Rj)+c)=>RiopRi,*M(Ri)op((M))=>RiopRi,*Rj(Ri)op((Rj))=>RiopRi,c*(Rj)(Ri)op(((Rj)+c))=>Ri機(jī)器指令開(kāi)銷(cost)opR,M開(kāi)銷2opRi,Rj開(kāi)銷1opRi,*M開(kāi)銷312.2簡(jiǎn)單的代碼生成程序12.2.1計(jì)算機(jī)模型目標(biāo)機(jī)器的地址方式地址方式匯編形式地址增加的開(kāi)銷直接地址方式MM1寄存器方式RR0間接寄存器方式*Rcontents(R)0索引方式c(R)c+contents(R)1間接索引方式*c(R)contents(c+contents(R))1目標(biāo)機(jī)器的地址方式地址方式匯編形式地址增加的開(kāi)銷直接地址方式12.2.2待用信息鏈法在一個(gè)基本塊范圍內(nèi)考慮如何充分利用寄存器的問(wèn)題：l

盡可能地讓該變量的值保留在寄存器中l(wèi)

盡可能引用變量在寄存器中的值

待用信息：若在一個(gè)基本塊中，變量A在四元式i中被定值，在i后面的四元式j(luò)中要引用A值，且從i到j(luò)之間沒(méi)有其它對(duì)A的定值點(diǎn)，這時(shí)我們稱j是四元式i中對(duì)變量A的待用信息或稱下次引用信息，同時(shí)也稱A是活躍的，若A被多次引用則可構(gòu)成待用信息鏈與活躍信息鏈?？蓮幕緣K的出口由后向前掃描，對(duì)每個(gè)變量建立相應(yīng)的待用信息鏈和活躍變量信息鏈。12.2.2待用信息鏈法計(jì)算待用信息的算法：

（1）符號(hào)表中增加“待用信息”欄和“活躍信息”欄:對(duì)各基本塊的符號(hào)表中的“待用信息”欄和“活躍信息”欄置初值，即把“待用信息”欄置“非待用”，對(duì)“活躍信息”欄按在基本塊出口處是否為活躍而置成“活躍”或“非活躍”。這里假定變量都是活躍的，臨時(shí)變量都是非活躍的。計(jì)算待用信息的算法：（1）符號(hào)表中增加“待用信息”欄和“活

（2）從基本塊出口到基本塊入口由后向前依次處理每個(gè)四元式。對(duì)每個(gè)四元式i:A:=BopC，依次執(zhí)行下述步驟：a）

把符號(hào)表中變量A的待用信息和活躍信息附加到四元式i上。b）

把符號(hào)表中變量A的待用信息欄和活躍信息欄分別置為“非待用”和“非活躍”。（由于在i中對(duì)A的定值只能在i以后的四元式才能引用，因而對(duì)i以前的四元式來(lái)說(shuō)A是不活躍也不可能是待用的）c）

把符號(hào)表中變量B和C的待用信息和活躍信息附加到四元式i上。d）

把符號(hào)表中變量B和C的待用信息欄置為“i”，活躍信息欄置為“活躍”。注意，以上a）和b），c）和d）的次序不能顛倒。（2）從基本塊出口到基本塊入口由后向前依次處理每個(gè)四元式。第12章-代碼生成ppt課件第12章-代碼生成ppt課件12.2.3代碼生成算法

基本塊的代碼生成算法假設(shè)只有A:=BopC的四元式序列A．對(duì)每個(gè)四元式i:A:=BopC，依次執(zhí)行下述步驟：(1)以四元式i:A:=BopC為參數(shù)，調(diào)用過(guò)程getreg(i:A:=BopC)。從getreg返回時(shí)，得到一寄存器R，用它作存放A現(xiàn)行值的寄存器；(2)利用AVALUE[B]和AVALUE[C]，確定出B和C現(xiàn)行值存放位置B`和C`，如果其現(xiàn)行值在寄存器中，則把寄存器取作B`和C`；12.2.3代碼生成算法基本塊的代碼生成算法第12章-代碼生成ppt課件其中假定d在基本塊的出口是活躍的。uvdutvcaubatcacabad+=+=-=-=-+-+-=::::)()()(:源代碼：其中假定d在基本塊的出口是活躍的。uvdutvcaubatc代碼序列代碼序列例：賦值語(yǔ)句

T4:=A+B-(E-(C+D))四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG：ABECDn9n3n8n1n2n7n6n4n5T4T1T3T2+--+從DAG生成目標(biāo)代碼例：賦值語(yǔ)句T4:=A+B-(E-(C+D))四元式序列GT4:=A+B-(E-(C+D))T1:=A+BMOVA,R0T2:=C+DADDB,R0T3:=E-T2MOVC,R1T4:=T1-T3ADDD,R1MOVR0,T1MOVE,R0SUBR1,R0MOVT1,R1SUBR0,R1MOVR1,T4T4:=A+B-(E-(C+D))T1:=A+BT2:=C+DMOVC,R0T3:=E-T2ADDD,R0T1:=A+BMOVE,R1T4:=T1-T3SUBR0,R1MOVA,R0ADDB,R0SUBR1,R0MOVR0,T4原因：T4的計(jì)算緊跟在T1之后

T2:=C+DMOVC,R盡可能使一個(gè)結(jié)點(diǎn)的求值緊接著它的最左變量的求值之后啟發(fā)式排序算法(1)while存在未列入表的內(nèi)部結(jié)點(diǎn)do(2)begin選取一個(gè)未列入表的但其全部父結(jié)點(diǎn)均已列入表的結(jié)點(diǎn)n;(3)將n列入表中;(4)whilen的最左子結(jié)點(diǎn)m不是葉結(jié)點(diǎn)并且其所有父結(jié)點(diǎn)均已列入表中do(5)begin將m列入表中;(6)n:=m(7)end(8)end盡可能使一個(gè)結(jié)點(diǎn)的求值緊接著它的最左變量的求值之后第12章-代碼生成ppt課件3t2t:1t4t6t:2te4t:3t8t5t:4tc6t:5tba:6ted:8t*=+=-=*=-=+=+=3t2t:1t4t6t:2te4t:3t8t5t:4tc6t基于樹(shù)重寫(xiě)的代碼生成例: a[i]:=b+1:=ind+Membconst1ind+constiregspconstaregsp++基于樹(shù)重寫(xiě)的代碼生成:=ind+Membconst1indregi+{ADDRj,Ri}regiregjregi+{ADDRj,Ri}regiregj第12章-代碼生成ppt課件第12章-代碼生成ppt課件:=ind+Membconst1ind+constiregSPreg0+(1)Reg0

?

consta{MOV#a,R0}(7)reg0

?{ADDSP,R0}+reg0regSP:=ind+Membconst1ind+constiregindconstiregSP++reg0indconstiregSP+:=indreg0+membconst1ind