编译原理英文课件：TargetCodeGen

1、Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-1-Compiler Construction Principles & Implementation TechniquesDr. Zheng XiaojuanProfessorSoftware College of Northeast Normal UniversityJune. 2014Software College of Northeast Normal

2、University Compiler Construction Principles & Implementation Techniques-2-Where we are?Lexical Analysis scanningSyntax Analysis ParsingSemantic AnalysisIntermediate Code OptimizationIntermediate Code GenerationTarget Code Generationanalysis/front endsynthesis/back end运运行行时时存存储储环环境境Software Colle

3、ge of Northeast Normal University Compiler Construction Principles & Implementation Techniques-3-Main Content of Chapter 1010. Target Code Generation 10.1 Introduction 10.2 Target Language 10.3 Temporary Variable 10.4 Registers Allocation 10.5 Generating Target Code from QuadruplesSoftware Colle

4、ge of Northeast Normal University Compiler Construction Principles & Implementation Techniques-4-Knowledge Relation GraphTarget CodeGenerationwhatwhat从中间代码生成目标代码从中间代码生成目标代码( (四元式四元式 目标机器指令目标机器指令) )目标代码目标代码( (目标机器指令集目标机器指令集) )转换转换 抽象地址抽象地址目标地址目标地址生成目标代码生成目标代码函数相关函数相关函数入口函数入口函数出口函数出口函数调用函数调用函数值返回函

5、数值返回操作型操作型赋值赋值Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-5-From Intermediate Code to Target Code目目标标代代码码中中间间代代码码源源程程序序翻译过程特点翻译过程特点: :(1)(1)执行过程的直译执行过程的直译; ;(2)(2)采用抽象地址采用抽象地址; ;翻译过程特点翻译过程特点: :(1)(1)执行过程的具体全执行过程的具体全 部实现部实现; ;(2)(2)

6、采用具体地址采用具体地址; ;(3)(3)需要考虑运行时存需要考虑运行时存 储空间问题储空间问题; ;(4) (4) 函数返回地址函数返回地址; ;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-6-10.1 Introduction to Target Code Generation Main task:在把中间代码翻译成目标代码的同时在把中间代码翻译成目标代码的同时, ,1.1.给变量分配实际地址给变量分配实际地址

7、2.2.寄存器分配寄存器分配 3. 生成管理过程生成管理过程ARAR的代码的代码 Depends on target machine and target machine language;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-7-10.2 Target Language (目标代码目标代码) ) 目标语言目标语言( (目标代码目标代码) )虚拟机代码虚拟机代码 (JVM)(JVM) portabilityp

8、ortability目标机器代码目标机器代码 ()() 目标代码有三种形式：目标代码有三种形式： 可以立即执行的机器语言代码，所有地址都重定位；可以立即执行的机器语言代码，所有地址都重定位； 待装配的机器语言模块，待装配的机器语言模块，当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码；换成能执行的机器语言代码； 汇编语言代码，须经过汇编程序汇编后，成为可执行的汇编语言代码，须经过汇编程序汇编后，成为可执行的机器语言代码。机器语言代码。Software College of Northeast Nor

9、mal University Compiler Construction Principles & Implementation Techniques-8-10.2 Target Language (目标代码目标代码) ) 目标代码生成阶段应考虑直接影响到目标代码速度的目标代码生成阶段应考虑直接影响到目标代码速度的三个问题：三个问题：一一如何生成较短的目标代码；如何生成较短的目标代码；二二如何充分利用计算机中的寄存器，减少目标代码访问存如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数；储单元的次数；三三如何充分利用计算机指令系统的特点，以提高目标代码如何充分利用计算机指令系

10、统的特点，以提高目标代码的质量。的质量。Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-9-一种目标机器语言一种目标机器语言目标地址形式目标地址形式假设假设: C: C是常量是常量, R, R是寄存器是寄存器, d, d是偏移量是偏移量表示方法表示方法: (R): (R)代表代表R R地址对应的内容地址对应的内容; ;立即式立即式: #C - C: #C - C是值是值寄存器式寄存器式: R - R: R - R本身就

11、是一个地址本身就是一个地址; ;变址式变址式: dR - d+(R) , R: dR - d+(R) , R的内容加上偏移的内容加上偏移d d得到的地址得到的地址间接寄存器间接寄存器: : * *R - (R), RR - (R), R的内容对应的地址的内容对应的地址间接变址间接变址: : * *dR- (d+(R), RdR- (d+(R), R的内容加上偏移的内容加上偏移d d后得到的地址的内容后得到的地址的内容; ;Software College of Northeast Normal University Compiler Construction Principles &

12、Implementation Techniques-10-From Abstract Address to Object Address (C Programming Language) (0, off, dir) (0, off, indir) (1, off, dir) (1, off, indir) (-1, off, dir) (-1, off, indir)抽象地址形式抽象地址形式offgp* offgp(off+InitOff)sp*(off+InitOff)sp(off+InitOff)sp*(off+InitOff)sp目标地址计算目标地址计算Software College

13、of Northeast Normal University Compiler Construction Principles & Implementation Techniques-11-一种目标机器语言一种目标机器语言 指令格式指令格式 ( (依赖于具体的目标机器）依赖于具体的目标机器）Op R , #C Op R , #C （立即立即-寄存器）寄存器） 含义是含义是 (R)(R)与与C C做做opop操作后操作后, ,结果送到结果送到 R R对应地址中对应地址中; ;Op R2, d(R1) Op R2, d(R1) （存储器存储器-寄存器）寄存器） 含义是含义是 (R2)(R2

14、)和和(R1)+d)(R1)+d)做做opop操作后操作后, ,结果送到结果送到 R2R2对应地址中对应地址中; ;Op R1, R2 Op R1, R2 （寄存器寄存器-寄存器）寄存器） 含义是含义是 (R2)(R2)和和(R1)(R1)做做opop操作后操作后, ,结果送到结果送到 R1R1对应地址中对应地址中; ;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-12-一种目标机器语言一种目标机器语言 基本指令集合

15、基本指令集合 ： Load R , Source -从从Source 读出送入读出送入R R Store R , Target - R的内容送入的内容送入Target Add R, Source - R+Source结果结果 送入送入R R Jump(0/1) label - 跳转到跳转到label对应的地址对应的地址 IN R - 输入值到输入值到R OUT R -输出输出R的值的值 LEA R, A - A的地址送给的地址送给RSoftware College of Northeast Normal University Compiler Construction Principles &

16、amp; Implementation Techniques-13-10.3 Temporary Variable (临时变量临时变量) 临时变量的特点临时变量的特点 数量多，寿命短；数量多，寿命短； 不优化，只定义一次，使用一次，且定义点和使用点在不优化，只定义一次，使用一次，且定义点和使用点在同一个基本块内；同一个基本块内； 公共表达式节省，将出现多次引用。公共表达式节省，将出现多次引用。 临时变量的存储空间临时变量的存储空间 x:=a+b-c+d ,则产生的中间代码为则产生的中间代码为： (+,a,b,t1) (-,t1,c,t2) (+,t2,d,t3) (:=, t3,x) 3 3个

17、临时变量可共享一个临时单元个临时变量可共享一个临时单元。Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-14-临时变量的空间分配临时变量的空间分配 可以在中间代码生成或者目标代码生成时做可以在中间代码生成或者目标代码生成时做; ; 静态分配法（共享法）静态分配法（共享法） 将临时变量的空间安排在将临时变量的空间安排在ARAR栈区。计算出临时变量栈区。计算出临时变量的活动区间，如果两个活动区间不相交，则可以共的活动区间，

18、如果两个活动区间不相交，则可以共享同一单元。享同一单元。 动态分配法（随用随分配法）动态分配法（随用随分配法） 过程调用时分配的过程调用时分配的ARAR区中不含临时变量部分，以后区中不含临时变量部分，以后每当要保存临时变量的值时，动态分配到栈区。当每当要保存临时变量的值时，动态分配到栈区。当临时变量所占的空间比较大时，这种方法比较好。临时变量所占的空间比较大时，这种方法比较好。Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniqu

19、es-15-10.4 Register Allocation (寄存器分配寄存器分配) ) 寄存器分配应遵循的原则：寄存器分配应遵循的原则： 寄存器优先原则：即变量的值尽可能的存放在寄存器中寄存器优先原则：即变量的值尽可能的存放在寄存器中 寄存器活跃原则：即变量的值至少有下一次的引用时才寄存器活跃原则：即变量的值至少有下一次的引用时才分配寄存器分配寄存器 寄存器多载原则：即一个寄存器中可能存放多个变量的寄存器多载原则：即一个寄存器中可能存放多个变量的值。典型的例子是通过赋值操作的结果。源变量和被赋值。典型的例子是通过赋值操作的结果。源变量和被赋值的变量共用一个寄存器值的变量共用一个寄存器 Re

20、gisterAlloc() does register allocation, and returns an available register;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-16-10.5 Generating Target Code from Quadruples 四元式种类四元式种类 运算型运算型: (op, A, B , T) 赋值赋值: (Assig, A, _, B) 跳转和标号跳转和标

21、号 函数相关函数相关 (ENTRY, label, size, level) (ENDFUNC, _, _) 参数传递参数传递 (CALL, f, true/false, result) (RETURN, _, _, t)Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-17-运算型目标代码生成运算型目标代码生成 (op,A, B,T)的代码生成算法要点的代码生成算法要点( (不考虑优化不考虑优化) )确定确定 A, B

22、 A, B 和和 T T 的目标地址的目标地址, , 记为记为A.addr, B.addr和和T.addr;找到一个可用的寄存器找到一个可用的寄存器R = R = RegisterAlloc(), , 生成如下目标代码生成如下目标代码Load R , A.addr Op R, B.addr Store R , T.addrSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-18-Example(+, a, b, t), 其

23、中其中 a:(0, 2, dir); b:(1, 2, indir), t: (-1, 5, dir)a的目标地址的目标地址: 2gpb的目标地址的目标地址: *(2+InitOff)spt的目标地址的目标地址: (5+InitOff)spLoad R, 2gp Add R, *(2+InitOff)sp Store R, (5+InitOff)sp Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-19-（Assig,

24、 A, _, B ）的代码生成的代码生成 算法要点算法要点( (不考虑优化不考虑优化) )： 求求A A和和B B的地址。的地址。 申请寄存器申请寄存器R, R, 生成生成(Load R , A.addr)指令指令, 生成指令生成指令(Store R , B );Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-20- 标号和标号和JUMPJUMP的代码生成的代码生成(1)(1)思想思想：遇到：遇到( (LABEL,L)

25、LABEL,L)时，不生成代码，保留（时，不生成代码，保留（L,PcL,Pc）,Pc,Pc为当为当前代码下一条指令；当遇到（前代码下一条指令；当遇到（JUMP, LJUMP, L）时，则生成对应的转时，则生成对应的转向指令（向指令（JUMP,PcJUMP,Pc）(2)(2)关键问题关键问题：可能出现标号使用在前定义在后，则需要构造转向：可能出现标号使用在前定义在后，则需要构造转向标号链，进行回填。（保留各个位置也可以）标号链，进行回填。（保留各个位置也可以）中间代码中间代码(JUMP, L)(JUMP, L)(JUMP,L)(LABEL,L)目标代码目标代码Pc:标号地址表标号地址表： P1:

26、(JUMP , nil )(0,L, P1)Pi:(JUMP, P1 )(0,L, Pi)Pk:(JUMP, Pi )(0,L, Pk)(1,L, Pc)PcPcPcSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-21-过程过程/ /函数代码生成函数代码生成(1)相关四元式相关四元式：(VALACT , a, off, size ) ; (VARACT , a, off, size ) (PROACT, p, off,

27、 size ) ; (FUNACT, a , off, size ) (CALL, , true/false, result ) (ENTRY, Label, Level, size ) (ENDFUNC, -,-,-)(2) 过函调用时，需要加入一些目标代码，用于完成如下工作：过函调用时，需要加入一些目标代码，用于完成如下工作： 申请新申请新ARAR空间空间 参数传递参数传递 填写某些填写某些ARAR内容内容 转向相应过程体转向相应过程体 过程过程/ /函数返回时：函数返回时： 释放释放AR AR 恢复信息恢复信息 返回值返回值Software College of Northeast No

28、rmal University Compiler Construction Principles & Implementation Techniques-22- (3)参数传递的代码：参数传递的代码：sp:sp:当前当前ARAR的首地址；的首地址；top:top:栈顶指针：栈顶指针： （VALACT, c, offset, 1） Load R, #c Store R, (offset+InitOff)top (VALACT, a, offset, 1) Load R, a.addr Store R, (offset+InitOff)top 参数传递的目标代码生成参数传递的目标代码生成

29、Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-23- (3) (3)参数传递的代码参数传递的代码：sp:当前当前ARAR的首地址的首地址；top:栈顶指针栈顶指针： (VARACT, a, offset ,1 ) LEA R, a.addr Store R, (offset+InitOff)top参数传递的目标代码生成参数传递的目标代码生成 Software College of Northeast Normal U

30、niversity Compiler Construction Principles & Implementation Techniques-24- (3)参数传递的代码：参数传递的代码：sp:sp:当前当前ARAR的首地址；的首地址；top:top:栈顶指针：栈顶指针： 实在函数实在函数: : (FUNACT, p, offset, 1) Load R, EntryAddr(p) Store R, (offset+InitOff)top 其中其中EntryAddr(p)代表代表的是函数的是函数p p的入口地址的入口地址 ; 形参函数形参函数: (FUNACT, P, offset,

31、1) Load R , P.addr Store R , (offset+InitOff)top 其中其中P.addrP.addr是指形参函数是指形参函数P P对应的单元地址对应的单元地址; ;参数传递的目标代码生成参数传递的目标代码生成 Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-25-（4）过程过程/ /函数调用函数调用 （call, , true, result） LEA R , result.addr (S

32、tore R, Re_Valtop) (Load R, pc+3) (Store R, Re_Atop) (JUMP EntryAddr(f) )(1)(1)返回值对应变量的地址返回值对应变量的地址 新新ARAR的相应位置的相应位置(2)(2)返回地址返回地址 新新ARAR相应位置相应位置(3)(3)调转到函数的入口地址调转到函数的入口地址; ;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-26-（4）过程过程/ /

33、函数调用函数调用 (call, , false, result) LEA R , result.addr (Store R, Re_Valtop) (Load R, pc+4) (Store R, Re_Atop) (Load R, f.addr) (JUMP, R)(1)(1)返回值对应变量的地址返回值对应变量的地址 新新ARAR的相应位置的相应位置(2)(2)返回地址返回地址 新新ARAR相应位置相应位置(3)(3)调转到函数的入口地址调转到函数的入口地址; ;Software College of Northeast Normal University Compiler Construc

34、tion Principles & Implementation Techniques-27-（5）过过/ /函入口函入口： （Entry, Label , size, Level ） (Store sp, DLtop ) -保留保留oldsp (Load R, Level) -保留层数保留层数 (Store R, Ltop) (C语言没有必要语言没有必要) (Load sp, top) -修改修改sp (ADD top, size) -修改修改top记住记住label对应的对应的代码地址代码地址; ;Software College of Northeast Normal Unive

35、rsity Compiler Construction Principles & Implementation Techniques-28-（6）过过/ /函出口函出口： （ENDFUN, -,-,-） 恢复寄存器内容恢复寄存器内容 （Load top, sp）- top=sp (Load sp, DLsp ) - sp=CurrentAR.sp ( (Load R , Re_Atop ) ) (JUMP, R) Software College of Northeast Normal University Compiler Construction Principles &

36、Implementation Techniques-29-（7）返回语句返回语句： （RETUTRN, -,-, result） LEA R1, Re_Valsp Load R2, result.addr Store R2, *R1 (Jump EndFun) 对应本函数中对应本函数中 (ENDFUN, _, _, _) 对应目标代码地址对应目标代码地址 Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-30-Examp

37、le const int n=5; int sum = 0; int fac(int i) if i=0 return 1; if i0 return -1; return (i*fac(i-1); void main () 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) (-,

38、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, _, _ , _)Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-31-Target Code

39、Generation Four registers sp :保存当前保存当前ARAR的首地址的首地址; ;top:top:保存当前保存当前栈顶地址栈顶地址; ;gp:gp:保存静态保存静态区的首地址区的首地址; ;pc: pc: 程序计数程序计数器器; ; Activation RecordActivation Record动态链地址动态链地址 0sp0sp返回地址返回地址 1sp1sp返回值返回值 2sp2sp临时变量临时变量形参形参局部变量局部变量空间大小空间大小 3sp3spspoffsetInitOff= 4topSoftware College of Northeast Normal

40、 University Compiler Construction Principles & Implementation Techniques-32-目标地址目标地址抽象地址抽象地址目标地址目标地址sumi(fac)t1,t2, t3,t4(fac)n(main)(0, 0, dir)0gp(1, 0, dir)4sp(-1, 1, dir)5sp(1, 0, dir)4spSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Tech

41、niques-33-Target Code GenerationP1: Load R , #0 P2: Store R, 0gp P3: Jump P40 P4:Store sp, 0topP5:Load sp, topP6:ADD 6, top (ENTRY, L1, 2 , 0)(EQ, i, 0, t1)(JUMP0, t1,_, L2)(RETURN, _, _, 1)(LABEL, _, _, L2)(assign, 0, _, sum)保存动态链地址保存动态链地址修改修改sp修改修改topP7: Load R , #0 P8: EQ R ,4sp P9: Store R, 5sp

42、P10: Jump0 R, P11: Load R , #1 P12: Store R, *2spP13: Jump P36P14Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-34-(LT, i, 0, t1)(JUMP0, t1,_, L3)(RETURN, _, _, -1)(LABEL, _, _, L3) Target Code GenerationP14: Load R , #0 P15: LT R ,4s

43、p P16: Store R, 5sp P17: Jump0 R, P18: Load R , #(-1) P19: Store R, *2spP20: Jump P36P21Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-35-Target Code Generation (-, i, 1, t2)(VALACT, t2,0, 1)(CALL, fac, true, t3)(*, i, t3, t4)(RETURN, _, _, t4)(