资源目录
压缩包内文档预览：
编号：21836409
类型：共享资源
大小：13.06MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
编译
原理
实用教程
杨德芳
课件
ppt
- 资源描述：
-
大学编译原理实用教程-杨德芳-课件PPT,大学,编译,原理,实用教程,杨德芳,课件,ppt
- 内容简介：
-
第11章 目标代码的生成本章学习目标代码生成工作一般在语法分析后或优化后的中间代码形式上进行，其功能是将这种中间代码的形式转换为某种结果代码的形式。本章主要内容有：从各种中间代码生成目标代码代码生成程序的自动构造技术目标代码生成实例11.1中间代码生成目标代码代码生成工作一般在语法分析后的中间代码形式上进行，其功能是将这种中间代码形式转换成某种结果代码形式。常用的结果代码的格式有3种：（1）可以立即执行的机器语言代码，它们通常放在固定的存储区中，编译后可以直接执行。（2）待装配的机器语言代码，为了这种形式的代码，必须经由连接装配程序将它们与另外一些运行子程序连接装配起来，组成可以执行的机器语言代码。（3）汇编语言程序，必须通过汇编程序将其汇编成可以执行的机器语言代码。在3种形式中，最容易生成的是汇编语言程序，它无须生成二进制形式代码，只要生成相应的符号化指令即可。表11-1假想的计算机中的符号指令11.1.2从四元式生成代码在四元式序列中，运算是按照执行顺序排列的，只要顺次扫描四元式，就能逐个生成代码。由于所有的运算都要在累加器中进行，所以，在生成一条代码前，需要知道累加器的内容。为此，引进全局量ACC，它是编译时刻的变量，用以指明运行时刻累加器的状态。ACC为空，则表示运行时累加器为空。若ACC不空，则表示累加器中有变量名和临时变量的值。过程INACC有两个参数，功能为：在生成可交换的双边运算（如*，+）指令之前，调用该过程。将其中一个参数放到累加器。对于不可交换的指令（如或），要求将第一个运算量对象放到累加器中。例如，在生成A/B时，先调用INACC(A, )，它生成把A存入累加器的指令。无论在哪种情况下，若累加器当前不为空，则INACC先生成一条保留累加器内容的指令。过程INACC如下：procedure INACC(A,B)string A,B;begin string T;if ACC=then begin GEN(LD,A); ACC:=A;returnend;if ACC=B then begin T:=A;A:=B;B:=Aendelse if ACC A then begin GEN(ST,ACC); GEN(LD,A); ACC:=A; end; end;这里采用的方法是顺序扫描四元式，并逐个生成每个四元式的代码。假定用计数器i控制顺序，并假定第 i个四元式的4个字段分别为（guad(i).OP，guad(i).oper1， guad(i).oper2和guad(i).RESULT表示，即（运算符，第一操作数，第二操作数，运算结果），以下是四元式的代码生成程序，即对：+，-，*，/和单目减中的每个运算分别给出相应代码时，所要调用的代码生成程序。（1）加法（乘法）四元式的代码生成程序。INACC（guad(i).OPER1, guad(i).OPER2）;GEN(ADD，guad(i).OPER2);或：GEN(MULT，guad(i).OPER2);ACC：= guad(i).RESULT；（2）减法（除法）四元式的代码生成程序。INACC（guad(i).OPER1,）GEN(SUB，guad(i).OPER2);GEN(DIV，guad(i).OPER2);ACC：= guad(i).RESULT；（3）单目减四元式的代码生成程序（3）。INACC（guad(i).OPER1,）GEN(CHS，);ACC：= guad(i).RESULT；应用这些代码生成程序，表达式A*(A*B+C)-C*D)可以生成如表11-2所示的结果代码。表11-2表达式生成的目标代码11.1.3从三元式生成代码从三元式生成代码需要引进和删除一些临时变量，例如，从三元式3）* X Y生成代码时，就需要引进代表结果值的临时变量。而且对于最后一个引进三元式（3）的那个三元式，当生成的代码后，代表（3）的结果值的临时变量就不再需要了，应将其删去。假设临时变量的范围是两两不相交或嵌套的，那么，就能使用一个编译时刻栈去保存和删除这些临时变量。否则，管理就会比较复杂，在这里假设每个临时变量仅需要引用一次。在生成三元式i的代码之前，必须检查两个运算量。如果其中一个运算量引用了前面的三元式，那么就必须用分配给该三元式存放结果值的临时变量名去代替这个运算的对象。这项工作由过程GETTEMP(A，B)来完成。其中A是被检查的运算对象字段，在返回时，B中包含临时变量名或变量名。该过程的编写如下：procedure GETTEMP(A,B)If A 引用三元式 k thenbeginfor i:=j step-1 until 1 doif trip(i)=k then begin B:=TEMP(i); goto out end;out:endelse B:=A;end;当生成三元式i的代码之后，还必须产生一个临时变量，用以描述执行该代码后所得到的值。然后将该临时变量和三元式编号下推到TEMP和TRIP栈中。因为执行刚生成的代码的结果在累加器中，因此要改变累加器的状态。这些工作是由过程NEMTEMP来实现的。procedure NEWTEMPbeginT:=新的临时变量名；j:=j+1;TRIP(j):=i;TEMP(j):=T;ACC:=Tend;为了从三元式生成代码，根据计数器i的值顺次扫描三元式。假定用TR(i).OP、TR(i).OPER1和TR(i).OPER2分别引用第i个三元式的三个字段。此外，由于假设两个临时变量的范围是不相交的或嵌套的，因此，当生成引用临时变量的代码时，相应的临时变量名总是在两个栈顶元素中的某一个之内。即只需要在栈顶元素查找它而无须查找整个栈。下面给出的是从三元式生成代码的程序。1)加法三元式的代码生成程序GETTEMP（TR(i).OPER1，Y1）；GETTEMP（TR(i).OPER2，Y2）；INACC（Y1，Y2）GEN（ADD，Y2）；If TR(i).OPER1 引用了三元式 then j:=j-1;If TR(i).OPER2 引用了三元式 then j:=j-1;NEWTEMP;3)单目减的三元式代码生成程序GETTEMP（TR(i).OPER1，Y1）；INACC（Y1，）；GEN（CHS，）；If TR(i).OPER1 引用了三元式 then j:=j-1;NEWTEMP；2)减法三元式的代码生成程序GETTEMP（TR(i).OPER1，Y1）；GETTEMP（TR(i).OPER2，Y2）；INACC（Y1，）；GEN（SUB，Y2）；If TR(i).OPER1 引用了三元式 then j:=j-1;If TR(i).OPER2 引用了三元式 then j:=j-1;NEWTEMP；11.1.4从树形表示到生成代码把单个表达式的i个三元组序列想像成一棵树，并用TR(i)表示根的分支。例如A*(A*B+C)-C*D)表示成三元式为:（1）* A B（2）+ （1） C（3）* C D（4） （2） （3）（5）* A （4）表示成树型如图11.2所示： 以前面的表达式A*(A*B+C)-C*D)为例，从三元式生成代码的过程如表11.3所示。表11.3表达式生成的目标代码根据有关的动作表，如果TR(i).OPER1和TR(i).OPER2都是变量名，那么先生成一条“LD TR(i)OPER1”指令，再生成一条“ADD TR(i)OPER2”指令。如果OPER1是一个变量，而OPER2是一个以运算符为根的子树，那么，在三元式TR的表中TR(i).OPER2是该根的序号。递归地调用COMP去生成该子树的代码。它将生成一条把相应表达式的值取进累加器的代码。从COMP返回后，将生成一条以OPER1作为运算对象的加法指令。如果两个运算符都是以运算符为根的子树，则先调用COMP，对第一个运算量生成代码；然后改变运算对象TR(i).OPER1,以表示这个值在累加器中。动作repeat指再一次使用动作表去决定所要做的工作。即执行“TR(i).OPER1=ACC”和“TR(i).OPER1=子树”所指定的动作。此时，产生一个新的临时变量名，生成一条保存累加器内容的ST指令。接着对第二个运算量生成代码，最后生产ADD指令。表11.5是以上面树型表示为例，给出了调用COMP（5）时所需的动作序列及所生成的代码。表11-5(c) TR(i).oper1 TR(i).oper211.1.5从逆波兰表示生成代码从左至右顺序扫描逆波兰式表示中的运算符和运算量。当扫描到运算量时，将运算符的名字存入运算量栈中，当扫描到一个二目运算符时，利用栈顶和两个运算量的名字生成相应的代码。生成代码后，就用存放结果值的变量名替代栈顶的两个运算量。由于二目运算总是使用两个栈顶运算量，因此，如果任一其他栈元素描述了累加器中的内容，那么，在生成二目运算代码前，必须生成一条保存累加器的指令。由此，可以采用另外一种保存累加器内容的方法，即允许栈内容能包含“ACC”，用以指明其值在累加器中。当扫描逆波兰表示式遇到一个运算量的名字时，就做 如下的工作：(1)若次栈顶元素是“ACC”，那么，产生一个新的临时变量名Ti，生成一条“ST Ti”指令，然后把该名字Ti存入这个栈元素中。(2)把运算量名下推进栈。从前面的分析可以看出，对于任何算术运算或逻辑运算，其代码生成的一般过程可以归纳为：（1）生成建立运算量地址的代码。（2）生成实现任何必要的类型转换的代码。（3）生成把一运算量取到累加器中的代码。（4）生成该运算的代码。根据这个过程，可以设计一个通用的代码生成程序，用以生成所有的算术运算或逻辑运算代码。11.1.6寄存器的分配任何计算机系统都有寄存器，但是寄存器的数量是十分有限的。如何合理、有效的使用这些寄存器是编译程序设计中需要重视的问题。寄存器的分配就是在计算一个表达式时，如何使用的寄存器的数目最少。表达式的内部形式可以用一棵树表示出来，在此基础上另加一遍扫描，顺序扫描该树，对每个运算确定各个运算对象所需要的寄存器的个数。并标记每个运算结点，用以指示首先应该计算的运算对象，然后生成相应的代码。从另一个角度提出的寄存器分配问题可以描述为：已知n个可以使用的寄存器R1, R2, Rn,，计算表达式如何使所需要的存取指令的条数最少。假定（1）不允许重新排列子表达式。（2）每个值必须先取到某个寄存器后才能使用。那么，当计算一个表达式时，在某一时刻需要使用变量V的值，此时，会出现如下的情况：（1）该值已经在寄存器Ri中，此时它用这个寄存器。（2）还没有给V分配寄存器，但此时有空的寄存器，此时把该寄存器分配给该值。（3）如果没有空闲寄存器，而V需要空闲寄存器，就存起其中一个值，将该值的寄存器分配给V。应该将哪个值的寄存器释放？把运算次序中下次使用且离现行位置最远的那个寄存器的内容保存起来。11.2常用的代码生成程序的开发方法由于代码生成部分与目标计算机硬件的结构紧密相关，这就导致了代码生成的可移植性及自动生成算法的研究和实现比较困难，目前常用的目标生成代码的开发方法有3种。分述如下。11.2.1 解释性的代码生成法解释性的代码生成法是建立一个代码生成专用语言，用这种语言以宏定义、子程序等形式描述代码生成结果。通过这些宏定义和子程序把中间语言解释为目标代码。这种方法使机器描述与代码生成算法结合在一起，与机器的联系直接反应在算法中。机器描述是通过过程的形式提供的，如采用把源程序映像成两地址代码序列的方法进行代码生成过程中，加法的代码生成算法如下：macro ADD x,yif type of x=integer and type of y=integerthen IADD x,yelse if type of x=float and type of y=floatthen FADD x,yelse error在上例中，宏ADD包含着实际的代码生成算法，IADD和FADD的任务是发射机器指令，相对来说ADD较独立于机器，而IADD与FADD才是真正与机器相关的。因此当把一个编译程序移植到一台新机器上的时候，IADD与FADD必须重写，而ADD却可以保持不变。这种算法的局限性在于：（1）由于目标机的多样性、寻址方式、指令的差异等，给中间代码的设计带来困难；（2）代码生成语言与机器密切相关，可移置性受到限制。（3）目标机的描述与代码生成算法混在一起，当描述改变时，势必引起算法的改变；（4）需进行指令的选择、指令的排列等低层次的烦琐工作，产生的目标代码的质量依赖于设计者的经验和能力。（5）代码生成的视野有限，虽可进行一定范围的优化，但对于协调上下文有关的优化较困难。11.2.2 模式匹配代码生成法模式匹配代码生成法是把对机器的描述与代码生成的算法分开。而对在解释性代码生成算法中，所需要的繁重的解释工作用模式匹配来代替。也就是建立一个代码生成用的机器描述语言，用以形式地描述目标机的资源、指令及其语义等有关信息。代码生成程序根据这些信息，自动地将中间语言程序翻译成目标机的汇编语言或机器语言代码。但是在这种方法中，需要通过形式描述的模式如实反映机器的特性。11.2.3 表驱动代码生成法表驱动代码生成算法，实质上是模式匹配代码生成算法的更进一步自动化，它是模仿语法描述构造表和表驱动的一种语法分析算法。首先，把对目标机的形式化描述进行预加工转换成代码生成表；然后用表驱动的代码生产程序来驱动代码生成表；最后把中间语言的内部表示翻译成目标机的汇编代码；也就是说用一个代码生成程序的生成器自动构造一个代码生成程序。上述的3种代码生成自动化的方法：解释性代码生成方法目标代码的质量高，代码生成算法简单，可移植性差。模式匹配代码生成算法有较好的可移植性，但是生成高质量的目标代码和算法困难。表驱动代码生成算法有较好的可移植性，它是代码生成程序的生成程序，真正实现了代码生成的自动化。11.3代码生成程序的自动化构造高级程序设计语言与其支撑的机器指令集合体系结构之间存在灵活的、多变的、复杂的对应关系，利用代码生成程序将高级语言程序转换为等价的目标代码程序是不可缺少的。处理器的日益更新，自然对代码生成程序的自动构造提出了更高的要求。在评估一个特殊体系结构与目标代码之间的尺寸和执行时间的有效性方面，代码生成程序的构造程序更显重要。中间代码的语义是内部的。将中间代码的形式化描述转换为目标机器的汇编语言是很复杂的。因此，编译程序的后端的自动构造比前端要困难得多。20世纪80年代以来开发了一些编译程序后端的自动构造工具如BEG、 iburg 、twig和MBURG等，比手工编写容易，且工作量少，但是，代码的执行效率不如手工开发的容易，并且很难被用户接受。为了简化开发过程，提高开发质量，编译程序的后端的自动开发成为关键技术和主要的难点。自动开发的总体结构如图11-3所示。11.3.1基于语法制导翻译的代码生成程序自动构造技术基于语法制导的代码生成程序自动构造技术就是利用类似于上下文无关文法的规则和相应的机器指令模板描述机器操作。当一条代码生成描述规则与一条波兰式中缀表示字符串的子字符串相匹配，且满足有关的语义限制时，将被匹配的部分用相应规则左边的符号替代，同时输出实例化后相应的指令模板。基于语法制导的代码生成程序自动构造技术由中间语言变换、模式匹配器和指令生成3部分组成。图11-4(a)给出了LIR指令的子集，其中每个参数的位置用一个数字表示，以用于中间表示字符串与代码生成规则和指令模板的匹配。相应的规则和SPACE的指令模板如图11-4(b)和11-4(c)所示。其中r.n表示寄存器，k.n表示常量，表示空字符串。数字n有双重作用，一是协调模式匹配与代码输出的关系，二是在规则中描述语法限制。例如，若某条指令的第1个操作数与第2个操作数必须使用相同的寄存器，这样匹配才能成功，则它们需要使用相同的参数。其中含有对IADD与FADD的宏调用，以生成目标代码机上的整数和浮点加法指令，对于IBM360机，IADD可以写为：macro IADD x,yfrom a in R1, a in R2emit (AR a,b) result in R1from a in R, b in Memit (A a,b) result in Rfrom a in M, b in Remit (A b,a) result in Rr.2r8 r.1r8 +4r3r2+ r1r8 +8r3r4r11r8 +4 r4下面给出基于语法制导的代码生成程序在语法分析过程中进行模式匹配，同时输出SPARC指令。r2r8+ r88+ r2 r1+ r84+ r8 4r1 1ld r8,0, r2r2r8+ r88+ r2 r1+ r84+ r8 4r1 1ld r8,0, r2在上面的匹配过程中，r2r8匹配成功，归约为。+ r88+ r2 r1+ r84+ r8 4r1 1ld r8,0, r1r1+ r8归约为r1+ r88+ r2 r1+ r8 4r1 1add r2, r1, r3+ r2 r1归约为r3+ r8 8+ r3+ r8 4r1 1st r3,r8,4+ r8 8+ r3归约为+ r8 8+ r3+ r8 4r1 1sub r1,1,r4,r1 1归约为r4+ r8 4r4st r4, r8,4图11-7模式匹配过程11.3.2基于语义制导的代码生成程序自动构造技术基于语义制导的代码生成程序也称为属性文法或词缀文法方法。通过使用属性，将语义信息加入代码生成规则中。这里使用符号“”表示继承属性，“”表示综合属性，属性的值写在箭头的后面。在代码生成过程中，属性除了传递值之外，还用于控制代码的生成、产生新的属性值以及产生副作用。控制部分通过断言来实现。action部分用大写字母来表示，主要用于计算新的属性值和产生副作用。当然，最重要的副作用为输出目标代码。因此，对于基于语法制导翻译的代码生成程序中的寄存器与常量相加的规则是：r.3+r.1 k.2add r.1, k.2, r.3r.3+k.1 r.2add r.1, k.2, r.3转换为相应的属性文法规则为：r r2+rr1 kk1 IsShort(k1) ALLOC(r2) EMIT3(“ADD”, r1, k1 ,r2)r r2+kk1 rr1 IsShort(k1) ALLOC(r2) EMIT3(“ADD”, r1, k1 ,r2)其中，在规则中加入了一些断言，如常量是否在允许的范围之内，且包含了代码输出和寄存器分配。第一条规则表示为：对于给定形式为+rk的字符串，若寄存器号为r1，常量值为k1，且满足断言IsShort(k1)，将结果放在寄存器r2中，通过替换相关寄存器和常量的值，输出一条三操作数加法指令，并将字符串归约为r，同时将r2的值向上传递为非终结符r的综合属性。11.3.3模式匹配和动态规划基于模式匹配和动态规划的方法自动构造代码生成程序的基本思想是将目标机指令用树重写规则表示，机器指令集合表示为一个树模式集合，且将描述不同的指令的树模式赋予相对权值以表示执行该指令的相对代价，然后利用动态规划技术选择最优的指令集合来计算相应的中间表示树。通过在中间表示树中重复查找与相应模板相匹配的子树并用相应的替换结点进行重写，即在将每个中间表示树归约为一个简单的结点过程中产生目标代码。该方法在此不做详细介绍，有兴趣的读者可以参看相关文献。11.4目标代码生成器设计实例下面首先介绍一个简单的代码生成器，此生成器依次将每条中间代码转换成目标代码，并且在一个基本块范围内考虑如何充分利用寄存器的问题。一方面，在基本块中，当生成计算某个变量值的目标代码时，尽可能地让该变量的值保留在寄存器中，直到该寄存器必须用来存放其他变量的值或已达基本块出口为止。另一方面，后续的目标代码尽可能地引用变量在寄存器中的值而不访问内存。例如，一C语言语句为A=（B+C）*D+E，把它翻译成四元式G：T1=B+CT2= T1*DA= T2+E如果不考虑代码的效率，可以简单地把每条中间代码（四元式）映射成若干条目标指令，如将x=y+z映射为：MOV AX,y/*AX为寄存器*/ADD AX,zMOV x,AX其中，x,y,z均为数据区的内存变量。这样，上述四元式的序列G就可以翻译为：（1）MOV AX,B（2）ADD AX,C（3）MOV T1,AX（4）MOV AX,T1（5）MUL AX,D（6）MOV T2,AX（7）MOV AX, T2（8）ADD AX,E（9）MOV A,AX虽然从正确性来看，这种翻译不存在问题，但是，它却存在冗余。在上述指令序列中，（4）和（7）两条指令是多余的；而T1，T2均是中间代码生成时的临时变量，它们在出了基本块后不再使用，故（3）和（6）两条指令也删去。所以，在考虑了效率和充分使用寄存器之后，应生成如下的代码：（1）MOV AX，B（2）ADD AX，C （3）MUL AX,D （4）ADD AX,E（5）MOV A,AX为了实现这个目的，代码生成器就必须了解一些信息：在产生与T2 = T1*D对应的目标代码时，为了省去指令MOV AX,T1，就必须知道T1的当前值已在寄存器AX中；为了省去MOV T1,AX，就必须知道除了基本块后T1不再被引用。11.4.1待用信息与活跃信息在一个基本块内的目标代码中，为了提高寄存器的使用效率，应将基本块内还要被引用的值尽可能的保留在寄存器中，而将基本块内不再被引用的变量所占用的寄存器尽早释放。每当翻译一条四元式如：A=B OP C时，需要知道在基本块中还有哪些四元式要对变量A、B、C进行引用。为此，需要收集一些待用信息。在一个基本块中，四元式i对变量A定值，如果i后面的四元式j要引用A且从i到j的四元式没有其他对A的定值点，则称j是四元式i中对变量A的待用信息，同时也称A是活跃的；如果A被多处引用，则构成了A的特用信息链与活跃信息链。为了取得每个变量在基本块内的待用信息和活跃信息，可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链与活跃信息链。如果没有进行数据分析并且临时变量不允许跨基本块引用，则把基本块中的临时变量均看作基本块出口之后的非活跃变量，而把所有的非临时变量均看作基本块出口之后的活跃变量。如果某些临时变量能够跨基本块使用，则把这些临时变量也看成基本块出口之后的活跃变量。假设变量的符号表内有待用信息和活跃信息栏，则计算变量待用信息的算法如下：（1）首先将基本块中各变量的符号表的待用信息栏置为“非待用”，对活跃信息栏则根据该变量在基本块出口之后是否活跃而将该栏中的信息置为“活跃”或“非活跃”。（2）从基本块出口到基本块入口由后向前依次处理每个四元式。对每个“四元式”i：A=B OP C依次执行以下的步骤：1）把符号表中变量A的待用信息和活跃信息附加到四元式i上。2）把符号表中变量A的待用信息和活跃信息分别置为“非待用”和“非活跃”。3）把符号表中变量B和C的待用信息和活跃信息附加到四元式i上。4）把符号表中B和C的待用信息置为i，活跃信息置为“活跃”。例11.1 考察基本块：（1）T=AB（2）U=AC（3）V=T+U（4）D=V+U其中，A、B、C、D为变量，T，U，V为中间变量，试求各变量的待用信息链和活跃信息链。【解】根据计算变量待用信息的算法得到各变量的待用信息链和活跃信息链如表11-6所示。表中的“F”表示“非待用”或“非活跃”，“L”表示“活跃”，（1）（4）分别表示基本块中的4个四元式。待用信息链和活跃信息链的每列从左到右为每行从后向前扫描一个四元式时相应变量的信息变化情况。表11-6待用信息链和活跃信息链待用信息和活跃信息在四元式上的标记如下：（1）T（3）L=A(2)LBFL（2）U（3）L =AFLCFL（3）V（4）L =TFF+U（4）L（4）DFL=VFF+UFF11.4.2代码生成算法为了在代码生成中进行寄存器分配，需要随时掌握各寄存器的使用情况，即它是处于空闲状态还是已分配给某个变量或已分配给某几个变量。通常用一个寄存器描述描述数组RVALUE动态地记录各寄存器的当前状况，并用寄存器Ri编号作为它的下标。此外，还需要建立一个变量地址描述数组AVALUE来记录各变量现行值存放的位置，即它是在某寄存器中还是在某内存单元中，或者同时存在于某寄存器和某内存单元中，可以表示如下：RVALUERi=A/*寄存器Ri分配给变量A*/RVALUERi=A，B/*寄存器Ri分配给变量A和B*/RVALUERi=/*未分配*/AVALUEA=A/*表示A的值在内存中*/AVALUEA= Ri /*表示A的值在寄存器Ri中*/AVALUEA= Ri，A /*表示A的值即在寄存器Ri中又在内存中*/为了简单起见，假设基本块中每个四元式的形式都是A=B op C ，则代码生成算法是对每个四元式 i：A=B op C，执行步骤如下：（1）调用函数GETREG(i: A=B op C)返回存放A值结果的寄存器R。（2）通过地址描述数组AVALUEB和AVALUEC确定出变量B和变量C的现行存放位置B和C。（3）如果BR，则生成目标代码：MOV R, BOP R, C否则生成目标代码：OP R, C如果B或C为R，则删除AVALUEB或AVALUEC中的R。（4）令AVALUEA=R，并令RVALUER=A，表示变量A的现行值只在R中且R中的值只代表A的现行值。（5）如果B和C的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量且它们的现行值存放在寄存器Rk中，则删除RVALUERk中的B和C以及AVALUERk，使Rk不再为B或C所占用。函数GETREG(i: A=B op C)用来得到存放A的当前值的寄存器R；其算法如下：（1）如果B的现行值在某寄存器Ri中，且该寄存器只包含B的值，或者B和A是同一个标识符，或者B在该四元式之后不再被引用，则选取Ri为所需寄存器并转（4）。（2）如果尚未分配寄存器，则从中选取一个寄存器Ri为所需寄存器并转（4）（3）从已分配的寄存器中选取一个Ri为所需要的寄存器R。选取原则为：占用Ri的变量的值也同时放在内存中，或该值在基本块中要在最远的位置才会引用到。这样，对寄存器Ri所含的变量和变量在内存中的情况必须做如下的调整。对RVALUERi中的每一个变量M，如果M不是A或者M即是A又是C，却不是B，而B又不在RVALUERi中，则：如果AVALUERi中不包含M，则生成目标代码MOV M，Ri；当M不是A时，如果M是B或者M是C且同时B也在RVALUERi中，则令AVALUEM=R，M，否则令AVALUEM=M；删除RVALUERi中的M；（4）给出R，返回。例11.2 对上例中，假设AX和BX是可用寄存器，用代码生成算法生成目标代码和相应的RVALUE和AVALUE。【解】用代码生成算法生成的目标代码和相应的RVALUE和AVALUE如表11-7表所示。对其他形式的四元式，也可以按照上面的算法生成目标代码。对形如A=B的复写，如果B的现行值在某寄存器Ri中，那么无需生成目标代码，只需将RVALUERi中的B和AVALUEB中的Ri删除。处理完基本块中的所有四元式后，对现行只在某寄存器中的每个变量，如果它在基本块出口之后是活跃的，则需要用MOV指令把它在寄存器中的值存放在数据区以它命名的内存单元中。为进行这一工作，可利用寄存器描述数组RVALUE来决定其中哪些变量的现行值在寄存器中，再利用地址描述数组AVALUE来决定其中哪些变量的现行值尚不在其内存单元中，最后利用活跃变量信息来决定其中哪些变量是活跃的。11.4.3目标代码生成的具体实例实例： 给定一个四元式序列，将四元式序列生成目标代码题目要求：（1）以简便的方式输入四元式序列，以合适的方式输出相应的虚拟目标代码。（）假定寄存器的数目没有限制。（）应用简单的生成算法和寄存器的获取算法。（）该系统包括：四元式输入、目标代码的生成、目标代码的输出、中间代码的查看（查看GOTO表）。设计如下：2设计思想。在四元式的序列中有3类量，即常量、程序变量及临时变量。常量对应立即数，以#N形式出现在目标指令中，其中N是一个特定常量数值。程序变量是程序中出现的变量，由程序书写者引进，它们通常是存放在存储单元中的存储变量。而临时变量则在生成四元式时由编译程序引进，一般将临时变量安排在寄存器中。为了反映寄存器的使用情况和变量值的存放情况，引进寄存器描述符和地址描述符。寄存器描述符：指明寄存器中存放的是哪个变量的值。寄存器描述符可以是一个数组，寄存器的序号与数组元素的序号一致，每个数组元素是一个结点链，每个结点指明该寄存器中存放的值所属变量的名，当未引用时链指针为NULL。地址描述符：指明变量的值存放在何处。即存放在存储器中还是寄存器中。其结构为：变量名下一个结点指针值存放处所链指针值存放处所链上的结点结构为：存储种类存放处所下一存放处所指针存储种类：寄存器和存储单元。控制转移指令的类型：条件转移指令关系运算符运算分量1运算分量2四元式序号无 条件转移指令：GO四元式序号往往可能在生成目标指令时还不能明确控制转移到目标指令是在在何处，因此需要回填。为此，引进目标指令与四元式对照表与GOTO表。目标指令与四元式对照表反映一个四元式所对应的若干目标指令中第一条的位置，而GOTO表则记录在哪条目标指令中应填入哪个四元式所对应的目标指令第一条的位置。其条目有如下结构：待填之目标指令的序号需找目标指令位置的四元式序号下一条待填目标指令为了最终能正确回填，又避免过多的数据存取，可以对四元式的数据结构做适当的修改，即添加成员：“首目标指令位置”与“目标指令条数”，从而避免引进目标指令与四元式的对照表。当生成全部目标指令之后，查看GOTO表，把四元式所对应的目标指令回填入目标指令中。3数据结构的设计主要包括四元式系列、目标指令序列、GOTO表四元式序列：array1MAXQuadNum of 四元式；四元式：record 操作码：string运算分量1：string 运算分量2：string首目标指令位置：integer目标指令条数：integerend目标指令序列的数据结构：ARRAY1MAXCodeNum OF 目标指令目标指令：RECORD 操作码：string源：string目标：stringEndGOTO 表：pointer(GOTO表条目)；GOTO表条目：record 待填的目标指令序号：integer需要目标指令位置的四元式序号：integer下一GOTO表条目：pointer(GOTO表条目)End5从四元式序列生成目标代码的伪代码程序从四元式序列生成目标代码的伪代码的程序如下：BE
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号