編譯原理英文課件：TargetCodeGen

-1-CompilerConstructionPrinciples&ImplementationTechniquesDr.ZhengXiaojuanProfessorSoftwareCollegeofNortheastNormalUniversityJune.2014-2-Whereweare?LexicalAnalysisscanningSyntaxAnalysisParsingSemanticAnalysisIntermediateCodeOptimizationIntermediateCodeGenerationTargetCodeGenerationanalysis/frontendsynthesis/backend運(yùn)行時(shí)存儲(chǔ)環(huán)境-3-MainContentofChapter10§10.TargetCodeGeneration10.1Introduction10.2TargetLanguage10.3TemporaryVariable10.4RegistersAllocation10.5GeneratingTargetCodefromQuadruples-4-KnowledgeRelationGraphTargetCodeGenerationwhat從中間代碼生成目標(biāo)代碼(四元式目標(biāo)機(jī)器指令)目標(biāo)代碼(目標(biāo)機(jī)器指令集)轉(zhuǎn)換抽象地址

目標(biāo)地址生成目標(biāo)代碼函數(shù)相關(guān)函數(shù)入口函數(shù)出口函數(shù)調(diào)用函數(shù)值返回操作型賦值-5-FromIntermediateCodetoTargetCode目標(biāo)代碼中間代碼源程序翻譯過(guò)程特點(diǎn):(1)執(zhí)行過(guò)程的直譯;(2)采用抽象地址;翻譯過(guò)程特點(diǎn):(1)執(zhí)行過(guò)程的具體全部實(shí)現(xiàn);(2)采用具體地址;(3)需要考慮運(yùn)行時(shí)存儲(chǔ)空間問(wèn)題;(4)函數(shù)返回地址;-6-10.1IntroductiontoTargetCodeGenerationMaintask:在把中間代碼翻譯成目標(biāo)代碼的同時(shí),1.給變量分配實(shí)際地址2.寄存器分配3.生成管理過(guò)程AR的代碼Dependsontargetmachineandtargetmachinelanguage;-7-10.2TargetLanguage(目標(biāo)代碼)目標(biāo)語(yǔ)言(目標(biāo)代碼)虛擬機(jī)代碼(JVM)portability目標(biāo)機(jī)器代碼()目標(biāo)代碼有三種形式：

①可以立即執(zhí)行的機(jī)器語(yǔ)言代碼，所有地址都重定位；

②待裝配的機(jī)器語(yǔ)言模塊，當(dāng)需要執(zhí)行時(shí)，由連接裝入程序把它們和某些運(yùn)行程序連接起來(lái)，轉(zhuǎn)換成能執(zhí)行的機(jī)器語(yǔ)言代碼；③匯編語(yǔ)言代碼，須經(jīng)過(guò)匯編程序匯編后，成為可執(zhí)行的機(jī)器語(yǔ)言代碼。-8-10.2TargetLanguage(目標(biāo)代碼)目標(biāo)代碼生成階段應(yīng)考慮直接影響到目標(biāo)代碼速度的三個(gè)問(wèn)題：一﹑如何生成較短的目標(biāo)代碼；二﹑如何充分利用計(jì)算機(jī)中的寄存器，減少目標(biāo)代碼訪問(wèn)存儲(chǔ)單元的次數(shù)；三﹑如何充分利用計(jì)算機(jī)指令系統(tǒng)的特點(diǎn)，以提高目標(biāo)代碼的質(zhì)量。-9-一種目標(biāo)機(jī)器語(yǔ)言目標(biāo)地址形式假設(shè):C是常量,R是寄存器,d是偏移量表示方法:(R)代表R地址對(duì)應(yīng)的內(nèi)容;立即式:#C----C是值寄存器式:R----R本身就是一個(gè)地址;變址式:d[R]----d+(R),R的內(nèi)容加上偏移d得到的地址間接寄存器:*R----(R),R的內(nèi)容對(duì)應(yīng)的地址間接變址:*d[R]----(d+(R)),R的內(nèi)容加上偏移d后得到的地址的內(nèi)容;-10-FromAbstractAddresstoObjectAddress(CProgrammingLanguage)(0,off,dir)(0,off,indir)(1,off,dir)(1,off,indir)(-1,off,dir)(-1,off,indir)抽象地址形式off[gp]*off[gp](off+InitOff)[sp]*(off+InitOff)[sp](off+InitOff)[sp]*(off+InitOff)[sp]目標(biāo)地址計(jì)算-11-一種目標(biāo)機(jī)器語(yǔ)言指令格式(依賴于具體的目標(biāo)機(jī)器）OpR,#C（立即-----寄存器）含義是(R)與C做op操作后,結(jié)果送到

R對(duì)應(yīng)地址中;OpR2,d(R1)（存儲(chǔ)器-----寄存器）含義是(R2)和((R1)+d)做op操作后,結(jié)果送到

R2對(duì)應(yīng)地址中;OpR1,R2（寄存器-----寄存器）含義是(R2)和(R1)做op操作后,結(jié)果送到

R1對(duì)應(yīng)地址中;-12-一種目標(biāo)機(jī)器語(yǔ)言基本指令集合：LoadR,Source------從Source讀出送入RStoreR,Target------R的內(nèi)容送入TargetAddR,Source------R+Source結(jié)果送入RJump(0/1)label-------跳轉(zhuǎn)到label對(duì)應(yīng)的地址INR-------輸入值到ROUTR-------輸出R的值LEAR,A-------A的地址送給R-13-10.3TemporaryVariable(臨時(shí)變量)臨時(shí)變量的特點(diǎn)數(shù)量多，壽命短；不優(yōu)化，只定義一次，使用一次，且定義點(diǎn)和使用點(diǎn)在同一個(gè)基本塊內(nèi)；公共表達(dá)式節(jié)省，將出現(xiàn)多次引用。臨時(shí)變量的存儲(chǔ)空間x:=a+b-c+d,則產(chǎn)生的中間代碼為：(+,a,b,t1)(-,t1,c,t2)(+,t2,d,t3)(:=,t3,x)

3個(gè)臨時(shí)變量可共享一個(gè)臨時(shí)單元。-14-臨時(shí)變量的空間分配可以在中間代碼生成或者目標(biāo)代碼生成時(shí)做;靜態(tài)分配法（共享法）將臨時(shí)變量的空間安排在AR棧區(qū)。計(jì)算出臨時(shí)變量的活動(dòng)區(qū)間，如果兩個(gè)活動(dòng)區(qū)間不相交，則可以共享同一單元。動(dòng)態(tài)分配法（隨用隨分配法）過(guò)程調(diào)用時(shí)分配的AR區(qū)中不含臨時(shí)變量部分，以后每當(dāng)要保存臨時(shí)變量的值時(shí)，動(dòng)態(tài)分配到棧區(qū)。當(dāng)臨時(shí)變量所占的空間比較大時(shí)，這種方法比較好。-15-10.4RegisterAllocation(寄存器分配)寄存器分配應(yīng)遵循的原則：寄存器優(yōu)先原則：即變量的值盡可能的存放在寄存器中寄存器活躍原則：即變量的值至少有下一次的引用時(shí)才分配寄存器寄存器多載原則：即一個(gè)寄存器中可能存放多個(gè)變量的值。典型的例子是通過(guò)賦值操作的結(jié)果。源變量和被賦值的變量共用一個(gè)寄存器RegisterAlloc()doesregisterallocation,andreturnsanavailableregister;-16-10.5GeneratingTargetCodefromQuadruples四元式種類運(yùn)算型:(op,A,B,T)賦值:(Assig,A,_,B)跳轉(zhuǎn)和標(biāo)號(hào)函數(shù)相關(guān)(ENTRY,label,size,level)(ENDFUNC,_,_)參數(shù)傳遞(CALL,f,true/false,result)(RETURN,_,_,t)-17-運(yùn)算型目標(biāo)代碼生成(op,A,B,T)的代碼生成算法要點(diǎn)(不考慮優(yōu)化)確定A,B和T的目標(biāo)地址,記為A.addr,B.addr和T.addr;找到一個(gè)可用的寄存器R=RegisterAlloc(),生成如下目標(biāo)代碼LoadR,A.addrOpR,B.addrStoreR,T.addr-18-Example(+,a,b,t),其中

a:(0,2,dir);b:(1,2,indir),t:(-1,5,dir)a的目標(biāo)地址:2[gp]b的目標(biāo)地址:*(2+InitOff)[sp]t的目標(biāo)地址:(5+InitOff)[sp]LoadR,2[gp]AddR,*(2+InitOff)[sp]StoreR,(5+InitOff)[sp]-19-（Assig,A,_,B）的代碼生成

算法要點(diǎn)(不考慮優(yōu)化)：①

求A和B的地址。②

申請(qǐng)寄存器R,生成(LoadR

,

A.addr)指令,③生成指令(StoreR

,B);-20-

標(biāo)號(hào)和JUMP的代碼生成思想：遇到(LABEL,L)時(shí)，不生成代碼，保留（L,Pc）,Pc為當(dāng)前代碼下一條指令；當(dāng)遇到（JUMP,L）時(shí)，則生成對(duì)應(yīng)的轉(zhuǎn)向指令（JUMP,Pc）關(guān)鍵問(wèn)題：可能出現(xiàn)標(biāo)號(hào)使用在前定義在后，則需要構(gòu)造轉(zhuǎn)向標(biāo)號(hào)鏈，進(jìn)行回填。（保留各個(gè)位置也可以）中間代碼……(JUMP,L)……(JUMP,L)……(JUMP,L)……(LABEL,L)目標(biāo)代碼……………………Pc:標(biāo)號(hào)地址表：

{}P1:(JUMP,nil){(0,L,P1)}Pi:(JUMP,P1){(0,L,Pi)}Pk:(JUMP,Pi){(0,L,Pk)}{(1,L,Pc)}PcPcPc-21-過(guò)程/函數(shù)代碼生成(1)相關(guān)四元式：(VALACT,a,off,size);(VARACT,a,off,size)(PROACT,p,off,size);(FUNACT,a,off,size)(CALL,<f>,true/false,result)(ENTRY,Label,Level,size)(ENDFUNC,-,-,-)(2)過(guò)函調(diào)用時(shí)，需要加入一些目標(biāo)代碼，用于完成如下工作：

①申請(qǐng)新AR空間②參數(shù)傳遞③填寫某些AR內(nèi)容④轉(zhuǎn)向相應(yīng)過(guò)程體過(guò)程/函數(shù)返回時(shí)：①釋放AR②恢復(fù)信息③返回值-22-

(3)參數(shù)傳遞的代碼：sp:當(dāng)前AR的首地址；top:棧頂指針：①（VALACT,c,offset,1）→LoadR,#cStoreR,(offset+InitOff)[top](VALACT,a,offset,1)→LoadR,a.addrStoreR,(offset+InitOff)[top]

參數(shù)傳遞的目標(biāo)代碼生成-23-(3)參數(shù)傳遞的代碼：sp:當(dāng)前AR的首地址；top:棧頂指針：

②(VARACT,a,offset,1)→LEAR,a.addrStoreR,(offset+InitOff)[top]參數(shù)傳遞的目標(biāo)代碼生成-24-(3)參數(shù)傳遞的代碼：sp:當(dāng)前AR的首地址；top:棧頂指針：③實(shí)在函數(shù):(FUNACT,p,offset,1)→LoadR,EntryAddr(p)StoreR,(offset+InitOff)[top]

其中EntryAddr(p)代表的是函數(shù)p的入口地址

;

形參函數(shù):(FUNACT,P,offset,1)→LoadR,P.addrStoreR,(offset+InitOff)[top]

其中P.addr是指形參函數(shù)P對(duì)應(yīng)的單元地址;參數(shù)傳遞的目標(biāo)代碼生成-25-（4）過(guò)程/函數(shù)調(diào)用①（call,<f>,true,result）→LEAR,result.addr(StoreR,Re_Val[top])(LoadR,pc+3)(StoreR,Re_A[top])(JUMPEntryAddr(f))返回值對(duì)應(yīng)變量的地址新AR的相應(yīng)位置(2)返回地址新AR相應(yīng)位置(3)調(diào)轉(zhuǎn)到函數(shù)的入口地址;-26-（4）過(guò)程/函數(shù)調(diào)用(call,<f>,false,result)→LEAR,result.addr(StoreR,Re_Val[top])(LoadR,pc+4)(StoreR,Re_A[top])(LoadR,f.addr)(JUMP,R)返回值對(duì)應(yīng)變量的地址新AR的相應(yīng)位置(2)返回地址新AR相應(yīng)位置(3)調(diào)轉(zhuǎn)到函數(shù)的入口地址;-27-（5）過(guò)/函入口：（Entry,Label,size,Level）(Storesp,

DL[top])------保留oldsp(LoadR,Level)------保留層數(shù)(StoreR,L[top])(C語(yǔ)言沒(méi)有必要)(Loadsp,top)------修改sp

(ADDtop,size)

------修改top記住label對(duì)應(yīng)的代碼地址;-28-（6）過(guò)/函出口：（ENDFUN,-,-,-）

①恢復(fù)寄存器內(nèi)容

②（Loadtop,sp）--------top=sp(Loadsp,DL[sp])------sp=CurrentAR.sp

(LoadR,Re_A[top])

(JUMP,R)-29-（7）返回語(yǔ)句：（RETUTRN,-,-,result）

LEAR1,Re_Val[sp]LoadR2,result.addr

StoreR2,*R1

(JumpEndFun)對(duì)應(yīng)本函數(shù)中(ENDFUN,_,_,_)

對(duì)應(yīng)目標(biāo)代碼地址

-30-Exampleconstintn=5;intsum=0;intfac(inti){ifi=0return1;ifi<0return-1;return(i*fac(i-1));}voidmain(){sum=fac(n);}

(ENTRY,L1,2,0)(EQ,i,0,t1)(JUMP0,t1,_,L2)(RETURN,_,_,1)(LABEL,_,_,L2)(assign,0,_,sum)(LT,i,0,t1)(JUMP0,t1,_,L3)(RETURN,_,_,-1)(LABEL,_,_,L3)

(-,i,1,t2)(VALACT,t2,0,1)(CALL,fac,true,t3)(*,i,t3,t4)(RETURN,_,_,t4)(ENDFUNC,_,_,_)(ENTRY,L4,1,0)(VALACT,n,0,1)(CALL,fac,true,sum)(ENDFUNC,_,_,_)-31-TargetCodeGenerationFourregisterssp:保存當(dāng)前AR的首地址;top:保存當(dāng)前棧頂?shù)刂?gp:保存靜態(tài)區(qū)的首地址;pc:程序計(jì)數(shù)器;

ActivationRecord動(dòng)態(tài)鏈地址0[sp]返回地址1[sp]返回值2[sp]臨時(shí)變量形參局部變量空間大小3[sp]spoffsetInitOff=4top-32-目標(biāo)地址抽象地址目標(biāo)地址sumi(fac)t1,t2,t3,t4(fac)n(main)(0,0,dir)0[gp](1,0,dir)4[sp](-1,1,dir)5[sp](1,0,dir)4[sp]-33-TargetCodeGenerationP1:LoadR,#0P2:StoreR,0[gp]P3:JumpP40

P4:Storesp,0[top]P5:Loadsp,topP6:ADD6,top

(ENTRY,L1,2,0)(EQ,i,0,t1)(JUMP0,t1,_,L2)(RETURN,_,_,1)(LABEL,_,_,L2)(assign,0,_,sum)保存動(dòng)態(tài)鏈地址修改sp修改topP7:LoadR,#0P8:EQR,4[sp]P9:StoreR,5[sp]P10:Jump0R,P11:LoadR,#1P12:StoreR,*2[sp]P13:JumpP36P14-34-(LT,i,0,t1)(JUMP0,t1,_,L3)(RETURN,_,_,-1)(LABEL,_,_,L3)

TargetCodeGenerationP14:LoadR,#0P15:LTR,4[sp]P16:StoreR,5[sp]P17:Jump0R,P18:LoadR,#(-1)P19:StoreR,*2[sp]P20:JumpP36P21-35-TargetCodeGeneration

(-,i,1,t2)(VALACT,t2,0,1)(CALL,fac,true,t3)(*,i,t3,t4)(RETURN,_,_,t4)(ENDFUNC,_,_,_)P21:LoadR,4[sp]P22:SubR,#1P23