编译原理-之-代码生成【VIP专享】课件

1、第十二章 代码生成代码生成概述简单代码生成程序一个假想的计算机模型简单的代码生成算法代码生成器的自动生成技术12.1 代码生成概述将经过语法分析或优化后的中间代码, 转换成特定目标机器的机器语言或汇编语言, 这样的转换程序称为代码生成程序.目标代码与具体的计算机体系结构、指令格式、字长、寄存器的个数和种类等，并和指令的语义、操作系统、存储管理相关，增大了代码生成程序的复杂性.一个简单的代码生成程序的构造.目标代码的执行效率很大程度依赖寄存器的使用.12.1.1 代码生成器(程序)在编译系统中的位置将经过语法分析或优化后的中间代码,转换成特定机器的目标代码.完成代码生成这一过程的程序称为代码生成

2、器,如图所示.图12.1 代码生成器在编译系统中的位置代码生成器的输入中间代码符号表中的信息能够立即执行的机器语言代码，所有地址均已定位，通常位于固定的存储区域中，编译后可直接运行.待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码.汇编语言代码。尚需经过汇编程序汇编，转换成可执行的机器语言代码. 返回目标代码一般有三种形式：12.1.2 代码生成要考虑的基本问题目标代码与具体的目标机结构、指令系统、操作系统有关.代码生成要考虑存储管理、寄存器分配等方面的问题.代码生成要使生成的目标代码较短 充分利用计算机的寄存器，减少目标代码中访问存储

3、单元的次数.1. 代码生成程序的输入中间代码. 线性表示法（后缀式）、三地址（四元式）等.符号表中的信息. 代码生成根据符号表中的信息来决定中间代码中的名字所指示的数据对象的运行时地址.有时需要作类型检查.2. 指令选择指令选择-寻找一个合适的目标机指令序列以实现给定的中间表示.如果目标机不能支持指令集的所有类型，那么对每一种例外要做特别处理.多数CPU的指令集合具有冗余性，也即，同一计算可用两个或多个不同的指令序列完成。指令选择器选择其中之一以产生最好的代码.例：“加1”的两种代码生成方式 如：中间代码a:=a+1: 实现1：INCa 实现2：LDR0，a ADD R0, #1 ST R0，

4、a减小产生代码的尺寸减小目标代码的执行时间降低目标代码的能耗指令选择的基本原则3. 寄存器分配通常情况下，指令在寄存器中访问操作数的开销要比在内存中访问小。许多指令不能直接访问内存。如果操作数在内存中，需要显式地取入到寄存器中。将经常使用的操作数保存在寄存器中是比较有利的。3. 寄存器分配寄存器是比较稀少的资源，计算机程序所需要的寄存器要比可用的寄存器多。寄存器分配负责确定在程序的哪个点将哪些值放在寄存器中比较有益。寄存器分配可以分成分配和指派两个阶段来考虑在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量；在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器。寄存器分配原则生成某变

5、量的目标代码时，尽量让变量的值或计算结果保留在寄存器中直到寄存器不够分配为止。这样，访问变量值时可减少对内存的存取次数，以提高运行速度;在同一基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用率;寄存器分配原则当到基本块出口时，将变量的值存放在内存中，因为一个基本块可能有多个后继结点或多个前驱结点，同一变量名在不同前驱结点的基本块内出口前存放的R可能不同，或没有定值，所以应在出口前把寄存器的内容放在内存中，这样从基本块外入口的变量值都在内存中.寄存器分配与寄存器赋值寄存器分配确定在程序的某个点将哪些值放在寄存器中寄存器赋值确定分配有寄存器的值应该在哪个寄存器中。由于一些目

6、标机可能具有不同类型的寄存器，因此，对寄存器使用的一致性方面也存在着一定的约束。例如，a：bcRi中存放了b的值，而Rj中存放了c的值,且b在此语句之后不再活跃。 ADD Rj，Ri 其开销为1,结果在Ri中.b存放在Ri中,而c在一个存储单元里,并假定b不再活跃。 ADD c，Ri其开销为2或者 MOV c，Rj ADD Rj，Ri 其开销为34. 指令调度指令调度确定程序指令的执行顺序对具有流水线限制的体系结构，这个阶段是必须的。如：RISC体系结构一个通用的流水线限制为：从内存中取入寄存器中的值在随后的某几个周期中是不能用的。在这几个周期期间，调出不依赖于该取入值的指令来执行是很重要的。

7、必须找一个指令（与被取值无关）在取指令之后立即执行，如果找不到相应的指令，这些周期就会被浪费。在代码生成过程中，这三者的关系非常密切。在进行寄存器分配和指令调度之时，假定指令选择已经完成；若先进行调度，寄存器趋向于过度分配；若先进行寄存器分配，对于给定的寄存器分配，可供调度的指令可能太少，可能不包含任何好的调度。选择最优的寄存器分配是困难的，这是NP完全问题（多项式条件下不可求解）指令选择,寄存器分配,指令调度间的关系12.2 一个简单的代码生成器介绍一个简单的代码生成程序以四元式的中间代码作为输入,将其转换成给定的M计算机的目标代码讨论一个基本块内如何充分利用寄存器以提高目标代码的效率给出寄

8、存器分配的一般算法12.2.1 一个假想的计算机模型设计一个好的代码生成器，必须熟习目标机器和它的指令系统假定一种计算机由n个通用寄存器R0, R1, , Rn-1R既可作累加器也可作变址器op表示运算符，M表示内存单元C表示常量，*表示间址方式存取机器指令类型类型指令形式意义(op是二目运算符)直接地址型op Ri, M(Ri)op(M) Ri寄存器型op Ri, Rj(Ri)op(Rj) Ri变址型op Ri, c(Rj)(Ri)op(Rj)+c) Ri间接型op Ri, *M(Ri)op(M) Riop Ri, * Rj(Ri)op(Rj) Riop Ri, *c(Rj)(Ri)op(R

9、j)+c) Ri某些指令意义说明如果op是一目运算符， op Ri, M的意义为op(M) Ri，其余类型类推以上指令中的运算符(操作码)op包括一般计算机上的一些运算符某些指令的意义说明见下表某些指令意义说明指令意义LD Ri,B把B单元的内容取到寄存器RiST Ri,B把寄存器Ri的内容取到B单元J X无条件转向X单元CMP A,B把A,B单元的值进行比较,并根据比较情况把机器内部特征寄存器CT置成相应状态.CT占两个进位. 根据AB分别置成0,1,2某些指令意义说明(续)指令意义JX如CT=2,转向X单元JX如CT=1或CT=2,转向X单元12.2.2 待用信息链表法在一个基本块范围内考

10、虑如何充分利用寄存器问题： 尽可能地让该变量的值保留在寄存器中尽可能引用变量在寄存器中的值 待用信息：若在一个基本块中，变量 A在四元式i中被定值，在i后面的四元式j中要引用A值，且从i到j之间没有其它对A的定值点，这时我们称 j是四元式i中对变量A的待用信息或称下次引用信息，同时也称A是活跃的，若A被多次引用则可构成待用信息链与活跃信息链。可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。计算待用信息的算法： 对各基本块的符号表中的“待用信息”栏和“活跃信息”栏置初值，即把“待用信息”栏置“非待用”，对“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”或“非活

11、跃”。这里假定变量都是活跃的，临时变量都是非活跃的。符号表中增加“待用信息”栏和“活跃信息”栏 从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式i: A:=B op C，依次执行下述步骤：a） 把符号表中变量A的待用信息和活跃信息附加到四元式i上。b） 把符号表中变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”。（由于在i中对A的定值只能在i以后的四元式才能引用，因而对i以前的四元式来说A是不活跃也不可能是待用的）c） 把符号表中变量B和C的待用信息和活跃信息附加到四元式i上。d） 把符号表中变量B和C的待用信息栏置为“i”，活跃信息栏置为“活跃”。注意，以上a）和

12、b），c）和d）的次序不能颠倒。如果中间代码出现A = op B或者A=B形式,以上步骤相同,只是其中不涉及到C例： 若用A，B，C，D表示变量，用T，U，V表示中间变量，有四元式如下：T:=A-BU:=A-CV:=T+UD:=V+U其名字表中的待用信息和活跃信息如下表，用“F”表示“非待用”“非活跃”，用“L”表示活跃。(1)(2)(3)(4)表示四元式序号。D :=V +U变量名 待用信息 活跃信息初值 待用信息链初值 活跃信息链A BCD T U V 表中“待用信息链”与“活跃信息链”的每列从左至右为每从后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化.FFFFFFFLLLL

13、FFFFLFFFFFF(4)(4)LLV :=T +U(4)LFFFF(4)L(3)(3)LLU :=A - C (3)LFFFLFLT :=A - B(3)LFF(2)LFL(2)(2)LL(1)(1)LL寄存器描述和地址描述寄存器描述数组RVALUE: 描述每个寄存器当前的状况,当对基本块进行代码生成时,每个寄存器在任一给定时刻将保留零个或多个名字的值.变量地址描述数组AVALUE：表示变量的存放情况,地址描述器记录在运行时刻的一个名字的当前值存放的一个位置或多个位置.12.2.3 代码生成算法RVALUERi=A表示的现行值是变量A的值RVALUERi=A,C表示的现行值是变量A,C的值

14、RVALUERi= 表示Ri未分配AVALUEA=A表示A的值在内存中AVALUEA=Ri,A表示A的值在内存中又在Ri中AVALUEA=Ri表示A的值在Ri中寄存器分配算法GETREG函数R=GETREG(i: A:=B op C)如果B的现行值在某个Ri中，且该寄存器只包含B的值，或者B和A是同一标识符，或B在该四元式后不会再被引用，则可选取Ri为所需的寄存器R，并转(4).如果有尚未分配的寄存器，则从中选择一个Ri作为所需的R，并转(4).从已分配的寄存器中选择一个Ri作为所需寄存器R，选取原则为：占用Ri的变量同时也在主存中，或者在基本块中最远的地方才会引用到. 这样对寄存器Ri所含的

15、变量和变量在主存中的情况必须作如下调整： 对RVALUERi中的每一个M，如果M不是A且AVALUEM不包含M，则： 生成目标代码ST Ri, M;即把Ri中非A的变量值送入内存中. 如果M不是B，则令AVALUEM=M,如果M是B，则令AVALUEM=M, Ri. 删除RVALUERi中的M. 给出R，返回. 对于其它形式的四元式也可以仿照以上算法生成其目标代码.代码生成算法假设基本块中代码形式都是A:=B op C四元式对每个四元式i: A:=B op C依次执行下述步骤：以四元式i: A:=B op C为参数, 调用过程GETREG(i: A:=B op C). 从GETREG返回时,得

16、到一寄存器R, 用它作存放A现行值的寄存器;利用地址描述数组AVALUEB和AVALUEC，确定出B和C现行值存放位置B和C，如果其现行值在寄存器中，则把寄存器取作B和C;如BR，则生成目标代码LD R， Bop R， C 否则，生成目标代码 op R，C如B为R，修改B的地址描述，即删除AVALUEB中的R, 即， AVALUEB:= AVALUEB-R 如C为R，修改C的地址描述，即删除AVALUEC中的R, 即， AVALUEC:= AVALUEC-R.如B或C的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量(由四元式i上的附加信息知道), 并且其现行值在某个寄存器Rk中

17、，则删除RVALUERk中的B或C以及AVALUEB或AVALUEC中的Rk， RVALUERk:= RVALUERk-B AVALUEB:= AVALUEB-Rk 或 RVALUERk:= RVALUERk-C AVALUEC:= AVALUEC-Rk 就是说释放B, C占用的寄存器,使该寄存器不再为B或C所占用.修改A的地址描述. 令AVALUEA=R, 并令RVALUER=A, 以表示变量A的现行值只在R中并且R中的值只代表A的现行值； 处理完基本块中所有四元式之后，对现行值在某寄存器R中的每个变量M，若它在出口之后是活跃的，则生成ST R，M，放到主存中。例：将下列赋值语句对应的三地址

18、（四元式）语句序列翻译成目标代码，假定在基本块的出口d是活跃的，并且只有两个寄存器R0和R1可以用。语句生成的代码 寄存器描述器地址描述器空寄存器t:=a-bMOV a, R0SUB b, R0R0包含tt在R0中u:=a-cMOV a, R1SUB c, R1R0包含tR1包含ut在R0中u在R1中v:=t+uADD R1, R0R0包含vR1包含uu在R1中v在R0中d:=v+uADD R1, R0R0包含dd在R0中MOV R0, dd在R0中和内存中函数GETREG(t:=a-b)第一次调用返回R0作为计算t的寄存器，因为a不在R0中，生成指令MOV a, R0和SUB b, R0,

19、然后更新寄存器描述器以记录R0包含t.依次处理每条四元式，直到最后一条三地址语句d:=v+u处理完为止. 注意因为u没有下次引用，R1将变为空. 最后在基本块的出口处生成指令MOV R0, d，存储活跃变量d.12.3 代码生成器的自动生成技术代码生成是编译的关键环节机器体系结构不统一等是代码自动生成的难题代码自动生成器注意采用由形式描述进行驱动的技术目标机每条指令的形式描述中间代码和指令的形式描述进行匹配，产生相应的指令本章习题：目标代码的形式有那些？什么是待用信息?什么是活跃信息?寄存器分配要解决哪些问题？如何解决？生成代码生成器的自动生成器需要解决哪些问题？实现函数getreg(i：x:

20、=y op z)的简单方法:（1）y的值是在一个寄存器中，且该寄存器不保留其它任何名字的值(只包含y的值)，并 且在执行 x：y op z以后y为“非活跃”“无下次引用”，那么就返回y的寄存器作为R,并更新 y的地址描述器以表示y已不在R;（2）如果(1)失败，则当有空寄存器时,就返回一个这样的寄存器; （3）如果(2)失败，若x在该基本块中有一个下次引用，或者op是一个需要寄存器的算符(如索引)，则找一个已被占用的寄存器R.如果R的值尚未在存储单元中，则将R的值存放到一个单元M中，并且更新地址描述器为M. 如果R同时保存了几个变量的值，则对每个需要存储的变量值都应生成一条MOV指令.（4）如

21、果x在该基本块中不再被引用，或者没有找到合适的被占用的寄存器，则选择x的存储单元作为R.从dag生成目标代码T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R-rB:=A*T6例：赋值语句 T4:=A+B-(E-(C+D)四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG： A B E C Dn9n3n8n1n2n7n6n4n5 T4 T1 T3 T2 +

22、 - - +T4:=A+B-(E-(C+D)T1:= A+B MOV A,R0T2:=C+D ADD B,R0T3:=E-T2 MOV C,R1T4:=T1-T3 ADD D,R1 MOV R0,T1 MOV E, R0 SUB R1,R0 MOV T1,R1 SUB R0,R1 MOV R1, T4排序T2:=C+D MOV C,R0 T3:=E-T2 ADD D,R0T1:= A+B MOV E,R1T4:=T1-T3 SUB R0,R1 MOV A,R0 ADD B, R0 SUB R1,R0 MOV R0,T4原因：T4的计算紧跟在T1之后 尽可能使一个结点的求值紧接着它的最左变量的求

23、值之后启发式排序算法(1) while存在未列入表的内部结点do(2) begin选取一个未列入表的但其全部父结点均已列 入表的结点n; (3) 将n列入表中; (4) while n的最左子结点m不是叶结点并且其所有 父结点均已列入表中do(5) begin将m列入表中;(6) n: =m(7) end(8) end代码生成器的开发方法常用方法解释性代码生成 模式匹配代码生成 表驱动代码生成 解释性代码生成解释性代码生成方法针对虚拟机产生代码然后扩展为实际目标代码 。首先，建立一个代码生成专用语言，用这种语言以宏定义、子程序等形式描述代码生成过程，通过宏定义和子程序把中间语言解释为目标代码。

24、机器描述是通过过程的形式提供的，如：Miller曾采用如下方法进行代码生成，它把源程序映象成两地址代码序列，然后进行代码生成。解释性代码生成（续） Macro Add x, y if type of x=integer and type of y=integer then Iadd x, y else if type of x=float and type of y=float then Fadd x, y else error解释性代码生成（续）调用宏Iadd与Fadd生成目标机上的整数和浮点数加法指令，如对IBM360机，Iadd可写成macro Iadd a, b from a in R1 , b in R2 emit (AR a,b) result in R1 from a in R , b in M emit (A a,b) result in R from a in M , b in R emit (A b, a) result in R 解释性代码生成（续） 在上例中宏Add包含着实际的代码生成算法，Iadd和Fadd的任务是生成机器指令。相对来说，Add较