1、第十二章第十二章 代码生成代码生成 代码生成概述代码生成概述 简单代码生成程序简单代码生成程序一个假想的计算机模型一个假想的计算机模型简单的代码生成算法简单的代码生成算法 代码生成器的自动生成技术代码生成器的自动生成技术12.1 代码生成概述代码生成概述 将经过语法分析或优化后的中间代码,转换成特定目标机器的机器语言或汇编语言,这样的转换程序称为代码生成程序.目标代码与具体的计算机体系结构、指令格式、字长、寄存器的个数和种类等，并和指令的语义、操作系统、存储管理相关，增大了代码生成程序的复杂性.一个简单的代码生成程序的构造.目标代码的执行效率很大程度依赖寄存器的使用.12.1.1 代码生成器代
2、码生成器(程序程序)在编译系统中的位置在编译系统中的位置将经过语法分析或优化后的中间代码,转换成特定机器的目标代码.完成代码生成这一过程的程序称为代码生成器,如图所示.图12.1 代码生成器在编译系统中的位置代码生成器的输入代码生成器的输入中间代码符号表中的信息1.能够立即执行的机器语言代码，所有地址均已定位，通常位于固定的存储区域中，编译后可直接运行.2.待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码.3.汇编语言代码。尚需经过汇编程序汇编，转换成可执行的机器语言代码.返回目标代码一般有三种形式：目标代码一般有三种形式：12.1.2
3、 代码生成要考虑的基本问题代码生成要考虑的基本问题目标代码与具体的目标机结构、指令系统、操作系统有关.代码生成要考虑存储管理、寄存器分配等方面的问题.代码生成要使生成的目标代码较短 充分利用计算机的寄存器，减少目标代码中访问存储单元的次数.1.代码生成程序的输入 中间代码.线性表示法（后缀式）、三地址（四元式）等.符号表中的信息.代码生成根据符号表中的信息来决定中间代码中的名字所指示的数据对象的运行时地址.有时需要作类型检查.2.指令选择指令选择-寻找一个合适的目标机指令序列以实现给定的中间表示.如果目标机不能支持指令集的所有类型，那么对每一种例外要做特别处理.多数CPU的指令集合具有冗余性，
4、也即，同一计算可用两个或多个不同的指令序列完成。指令选择器选择其中之一以产生最好的代码.例：“加1”的两种代码生成方式 如：中间代码a:=a+1:实现1：INCa 实现2：LDR0，a ADD R0,#1 ST R0，a 减小产生代码的尺寸 减小目标代码的执行时间 降低目标代码的能耗指令选择的基本原则3.寄存器分配 通常情况下，指令在寄存器中访问操作数的开销要比在内存中访问小。许多指令不能直接访问内存。如果操作数在内存中，需要显式地取入到寄存器中。将经常使用的操作数保存在寄存器中是比较有利的。3.寄存器分配 寄存器是比较稀少的资源，计算机程序所需要的寄存器要比可用的寄存器多。寄存器分配负责确定
5、在程序的哪个点将哪些值放在寄存器中比较有益。寄存器分配可以分成分配和指派两个阶段来考虑 在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量；在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器。寄存器分配原则生成某变量的目标代码时，尽量让变量的值或计算结果保留在寄存器中直到寄存器不够分配为止。这样，访问变量值时可减少对内存的存取次数，以提高运行速度;在同一基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用率;寄存器分配原则 当到基本块出口时，将变量的值存放在内存中，因为一个基本块可能有多个后继结点或多个前驱结点，同一变量名在不同前驱结点的基本块内出口前存放的R可
6、能不同，或没有定值，所以应在出口前把寄存器的内容放在内存中，这样从基本块外入口的变量值都在内存中.寄存器分配与寄存器赋值寄存器分配与寄存器赋值 寄存器分配寄存器分配确定在程序的某个点将哪些值放在寄存器中 寄存器赋值寄存器赋值确定分配有寄存器的值应该在哪个寄存器中。由于一些目标机可能具有不同类型的寄存器，因此，对寄存器使用的一致性方面也存在着一定的约束。例如，a：bc Ri中存放了b的值，而Rj中存放了c的值,且b在此语句之后不再活跃。ADD Rj，Ri 其开销为1,结果在Ri中.b存放在Ri中,而c在一个存储单元里,并假定b不再活跃。ADD c，Ri其开销为2 或者 MOV c，Rj ADD
7、Rj，Ri 其开销为34.指令调度 指令调度确定程序指令的执行顺序 对具有流水线限制的体系结构，这个阶段是必须的。如：RISC体系结构一个通用的流水线限制为：从内存中取入寄存器中的值在随后的某几个周期中是不能用的。在这几个周期期间，调出不依赖于该取入值的指令来执行是很重要的。必须找一个指令（与被取值无关）在取指令之后立即执行，如果找不到相应的指令，这些周期就会被浪费。在代码生成过程中，这三者的关系非常密切。在进行寄存器分配和指令调度之时，假定指令选择已经完成；若先进行调度，寄存器趋向于过度分配；若先进行寄存器分配，对于给定的寄存器分配，可供调度的指令可能太少，可能不包含任何好的调度。选择最优的
8、寄存器分配是困难的，这是NP完全问题（多项式条件下不可求解）指令选择指令选择,寄存器分配寄存器分配,指令调度间的关系指令调度间的关系12.2 一个简单的代码生成器一个简单的代码生成器 介绍一个简单的代码生成程序 以四元式的中间代码作为输入,将其转换成给定的M计算机的目标代码 讨论一个基本块内如何充分利用寄存器以提高目标代码的效率 给出寄存器分配的一般算法12.2.1 一个假想的计算机模型一个假想的计算机模型 设计一个好的代码生成器，必须熟习目标机器和它的指令系统 假定一种计算机由n个通用寄存器R0,R1,Rn-1 R既可作累加器也可作变址器 op表示运算符，M表示内存单元 C表示常量，*表示间
9、址方式存取机器指令类型类型指令形式意义(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(Rj)+c)Ri某些指令意义说明 如果op是一目运算符，op Ri,M的意义为op(M)Ri，其余类型类推 以上指令中的运算符(操作码)op包括一般计算机上的一些运算符 某些指令的意义说明见下表某些指令意义说明指令意义LD Ri,B把B单元的内容取到寄存器RiST
10、 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 待用信息链表法待用信息链表法在一个基本块范围内考虑如何充分利用寄存器问题：在一个基本块范围内考虑如何充分利用寄存器问题：尽可能地让该变量的值保留在寄存器中尽可能地让该变量的值保留在寄存器中 尽可能引用变量在寄存器中的值尽可能引用变量在寄存器中的值 待用信息待用信息：若在一个基本块中，变量：若在一个基
11、本块中，变量 A在四元式在四元式i中被定中被定值，在值，在i后面的四元式后面的四元式j中要引用中要引用A值，且从值，且从i到到 j之间没有其之间没有其它对它对A的定值点，这时我们称的定值点，这时我们称 j是四元式是四元式i中对变量中对变量A的的待用待用信息信息或称或称下次引用信息下次引用信息，同时也称，同时也称A是是活跃活跃的，若的，若 A 被多次被多次引用则可构成引用则可构成待用信息链与活跃信息链待用信息链与活跃信息链。可从基本块的出口由后向前扫描，对每个变量建立可从基本块的出口由后向前扫描，对每个变量建立相应的待用相应的待用信息链和活跃变量信息链。信息链和活跃变量信息链。计算待用信息的算法
12、：计算待用信息的算法：对各基本块的符号表中的对各基本块的符号表中的“待用信息待用信息”栏和栏和“活跃信息活跃信息”栏置初值，即把栏置初值，即把“待用信息待用信息”栏置栏置“非待用非待用”，对，对“活跃活跃信息信息”栏按在基本块出口处是否为活跃而置成栏按在基本块出口处是否为活跃而置成“活跃活跃”或或“非活跃非活跃”。这里假定变量都是活跃的，临时变量都是非这里假定变量都是活跃的，临时变量都是非活跃的。活跃的。符号表中增加符号表中增加“待用信息待用信息”栏和栏和“活跃信息活跃信息”栏栏 从基本块出口到基本块入口由后向前依次处理每个四元从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式式
13、。对每个四元式i:A:=B op C，依次执行下述步骤：，依次执行下述步骤：a）把符号表中变量把符号表中变量A的待用信息和活跃信息附加到四元式的待用信息和活跃信息附加到四元式i上。上。b）把符号表中变量把符号表中变量A的待用信息栏和活跃信息栏分别置为的待用信息栏和活跃信息栏分别置为“非待用非待用”和和“非活跃非活跃”。（由于在（由于在i 中对中对A的定值只能的定值只能在在 i以后的四元式才能引用，因而对以后的四元式才能引用，因而对 i以前的四元式来说以前的四元式来说A是不活跃也不可能是待用的）是不活跃也不可能是待用的）c）把符号表中变量把符号表中变量B和和 C的待用信息和活跃信息附加到四元的待
14、用信息和活跃信息附加到四元式式 i上。上。d）把符号表中变量把符号表中变量B和和 C的待用信息栏置为的待用信息栏置为“i”，活跃信，活跃信息栏置为息栏置为“活跃活跃”。注意，以上注意，以上a）和）和b），），c）和）和d）的次序不能颠倒。）的次序不能颠倒。如果中间代码出现如果中间代码出现A=op BA=op B或者或者A=BA=B形式形式,以上步骤相同以上步骤相同,只是其只是其中不涉及到中不涉及到C C例：例：若用若用A，B，C，D表示变量，用表示变量，用T，U，V表示中间变量，有四元式如下：表示中间变量，有四元式如下：1.T:=A-B2.U:=A-C3.V:=T+U4.D:=V+U其名字表中
15、的待用信息和活跃信息如下表，其名字表中的待用信息和活跃信息如下表，用用“F”表示表示“非待用非待用”“”“非活跃非活跃”，用，用“L”表示活跃。表示活跃。(1)(2)(3)(4)表示四元式序表示四元式序号。号。D :=V +U变变量量名名 待用信息待用信息 活跃信息活跃信息初值初值 待用信息链待用信息链初值初值 活跃信息链活跃信息链A BCD T U V 表中表中“待用信息链待用信息链”与与“活跃信活跃信息链息链”的每列从左至右为每从后的每列从左至右为每从后向前扫描一个四元式时相应变量向前扫描一个四元式时相应变量的信息变化情况，空白处为没变的信息变化情况，空白处为没变化化.FFFFFFFLLL
16、LFFFFLFFFFFF(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：表示变：表示变量的存放情况量的存放情况,地址描述器记录在运地址描述器
17、记录在运行时刻的一个名字的当前值存放的一行时刻的一个名字的当前值存放的一个位置或多个位置个位置或多个位置.12.2.3 代码生成算法代码生成算法RVALUERi=A表示的现行值是变量表示的现行值是变量A的值的值RVALUERi=A,C表示的现行值是变量表示的现行值是变量A,C的值的值RVALUERi=表示表示Ri未分配未分配AVALUEA=A表示表示A的值在内存中的值在内存中AVALUEA=Ri,A表示表示A的值在内存中又在的值在内存中又在Ri中中AVALUEA=Ri表示表示A的值在的值在Ri中中寄存器分配算法寄存器分配算法GETREG函数函数R=GETREG(i:A:=B op C)1.如果
18、如果B的现行值在某个的现行值在某个Ri中，且该中，且该寄存器只包含寄存器只包含B的值，或者的值，或者B和和A是是同一标识符，或同一标识符，或B在该四元式后不在该四元式后不会再被引用，则可选取会再被引用，则可选取Ri为所需的为所需的寄存器寄存器R，并转，并转(4).2.如果有尚未分配的寄存器，则从中如果有尚未分配的寄存器，则从中选择一个选择一个Ri作为所需的作为所需的R，并转，并转(4).3.从已分配的寄存器中选择一个从已分配的寄存器中选择一个Ri作作为所需寄存器为所需寄存器R，选取原则为：占，选取原则为：占用用Ri的变量同时也在主存中，或者的变量同时也在主存中，或者在基本块中最远的地方才会引用
19、到在基本块中最远的地方才会引用到.这样对寄存器这样对寄存器Ri所含的变量和变量所含的变量和变量在主存中的情况必须作如下调整：在主存中的情况必须作如下调整：对对RVALUERi中的每一个中的每一个M，如果，如果M不是不是A且且AVALUEM不包含不包含M，则：，则：生成目标代码生成目标代码ST Ri,M;即把即把Ri中非中非A的变量值送入内存中的变量值送入内存中.如果如果M不是不是B，则令，则令AVALUEM=M,如果如果M是是B，则令，则令AVALUEM=M,Ri.删除删除RVALUERi中的中的M.4.给出给出R，返回，返回.对于其它形式的四元式也可以仿照以上对于其它形式的四元式也可以仿照以
20、上算法生成其目标代码算法生成其目标代码.代码生成算法代码生成算法假设基本块中代码形式都是假设基本块中代码形式都是A:=B op C四元式四元式对每个四元式对每个四元式i:A:=B op C依次执行下述步骤：依次执行下述步骤：1.以四元式以四元式i:A:=B op C为参数为参数,调用过程调用过程GETREG(i:A:=B op C).从从GETREG返回返回时时,得到一寄存器得到一寄存器R,用它作存放用它作存放A现行值的现行值的寄存器寄存器;2.利用地址描述数组利用地址描述数组AVALUEB和和AVALUEC，确定出，确定出B和和C现行值存放位现行值存放位置置B和和C，如果其现行值在寄存器中，
21、则，如果其现行值在寄存器中，则把寄存器取作把寄存器取作B和和C;3.如如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.4.如如B或或C的现行值在基本块中不再被引用，它的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量们也不是基本块出口之后的活跃变量(由
22、四元由四元式式i上的附加信息知道上的附加信息知道),并且其现行值在某个并且其现行值在某个寄存器寄存器Rk中，则删除中，则删除RVALUERk中的中的B或或C以及以及AVALUEB或或AVALUEC中的中的Rk，RVALUERk:=RVALUERk-B AVALUEB:=AVALUEB-Rk 或或 RVALUERk:=RVALUERk-C AVALUEC:=AVALUEC-Rk 就是说释放就是说释放B,C占用的寄存器占用的寄存器,使该寄存器不使该寄存器不再为再为B或或C所占用所占用.5.修改修改A的地址描述的地址描述.令令AVALUEA=R,并令并令RVALUER=A,以表示变量以表示变量A的现
23、行值只在的现行值只在R中并且中并且R中的值只代表中的值只代表A的现行值；的现行值；处理完基本块中所有四元式之后，对处理完基本块中所有四元式之后，对现行值在某寄存器现行值在某寄存器R中的每个变量中的每个变量M，若它在出口之后是活跃的，则生成若它在出口之后是活跃的，则生成ST R，M，放到主存中。，放到主存中。例：将下列赋值语句对应的三地址（四元式）例：将下列赋值语句对应的三地址（四元式）语句序列翻译成目标代码，假定在基本块的语句序列翻译成目标代码，假定在基本块的出口出口d是活跃的，并且只有两个寄存器是活跃的，并且只有两个寄存器R0和和R1可以用。可以用。uvdutvcaubatcacabad:)
24、()()(:语句语句生成的代码生成的代码 寄存器寄存器描述器描述器地址地址描述器描述器空寄存器空寄存器t:=a-b MOV a,R0SUB b,R0R0包含包含tt在在R0中中u:=a-c MOV a,R1SUB c,R1R0包含包含tR1包含包含ut在在R0中中u在在R1中中v:=t+u ADD R1,R0R0包含包含vR1包含包含uu在在R1中中v在在R0中中d:=v+u ADD R1,R0R0包含包含dd在在R0中中MOV R0,dd在在R0中和内存中中和内存中函数函数GETREG(t:=a-b)第一次调用返回第一次调用返回R0作为计算作为计算t的寄存器，因为的寄存器，因为a不在不在R0
25、中，中，生成指令生成指令MOV a,R0和和SUB b,R0,然后更然后更新寄存器描述器以记录新寄存器描述器以记录R0包含包含t.依次处理每条四元式，直到最后一条三依次处理每条四元式，直到最后一条三地址语句地址语句d:=v+u处理完为止处理完为止.注意因为注意因为u没有下次引用，没有下次引用，R1将变为空将变为空.最后在基本最后在基本块的出口处生成指令块的出口处生成指令MOV R0,d，存储，存储活跃变量活跃变量d.12.3 代码生成器的自动生成技术代码生成器的自动生成技术 代码生成是编译的关键环节代码生成是编译的关键环节 机器体系结构不统一等是代码自动机器体系结构不统一等是代码自动生成的难题
26、生成的难题 代码自动生成器注意采用由形式描代码自动生成器注意采用由形式描述进行驱动的技术述进行驱动的技术目标机每条指目标机每条指令的形式描述令的形式描述 中间代码和指令的形式描述进行匹中间代码和指令的形式描述进行匹配，产生相应的指令配，产生相应的指令本章习题：1.目标代码的形式有那些？2.什么是待用信息?什么是活跃信息?3.寄存器分配要解决哪些问题？如何解决？4.生成代码生成器的自动生成器需要解决哪些问题？实现函数实现函数getreg(i：x:=y op z)的简单方的简单方法法:（1）y的值是在一个寄存器中，且该寄存的值是在一个寄存器中，且该寄存器不保留其它任何名字的值器不保留其它任何名字的
27、值(只包含只包含y的的值值)，并，并 且在执行且在执行 x：y op z以后以后y为为“非活跃非活跃”“”“无下次引用无下次引用”，那么就返，那么就返回回y的寄存器作为的寄存器作为R,并更新并更新 y的地址描述的地址描述器以表示器以表示y已不在已不在R;（2）如果）如果(1)失败，则当有空寄存器时失败，则当有空寄存器时,就就返回一个这样的寄存器返回一个这样的寄存器;（3）如果如果(2)失败，若失败，若x在该基本块中有在该基本块中有一个下次引用，或者一个下次引用，或者op是一个需要寄存是一个需要寄存器的算符器的算符(如索引如索引)，则找一个已被占用的，则找一个已被占用的寄存器寄存器R.如果如果R
28、的值尚未在存储单元中，的值尚未在存储单元中，则将则将R的值存放到一个单元的值存放到一个单元M中，并且更中，并且更新地址描述器为新地址描述器为M.如果如果R同时保存了几同时保存了几个变量的值，则对每个需要存储的变量个变量的值，则对每个需要存储的变量值都应生成一条值都应生成一条MOV指令指令.（4）如果）如果x在该基本块中不再被引用，或在该基本块中不再被引用，或者没有找到合适的被占用的寄存器，则者没有找到合适的被占用的寄存器，则选择选择x的存储单元作为的存储单元作为R.从dag生成目标代码 B *A,T5 *T2,T4 T6 +-T0 T1,T3 3.14 6.28 R r (j)n2n5n3n7
29、n1n4n6n8T0:=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 +-+T4:=A+B-(E-(C+D)T1:=A+B MOV A,R0T2
30、:=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之后之后 尽可能使一个结点的求值紧接着它的最左变量的求值之后启发式排序算法(1)while存在未列入表的内部结点do(2)
31、begin选取一个未列入表的但其全部父结点均已列 入表的结点n;(3)将n列入表中;(4)while n的最左子结点m不是叶结点并且其所有 父结点均已列入表中do(5)begin将m列入表中;(6)n:=m(7)end(8)end3t2t:1t4t6t:2te4t:3t8t5t:4tc6t:5tba:6ted:8t代码生成器的开发方法 常用方法 解释性代码生成 模式匹配代码生成 表驱动代码生成 解释性代码生成 解释性代码生成方法针对虚拟机产生代码然后扩展为实际目标代码。首先，建立一个代码生成专用语言，用这种语言以宏定义、子程序等形式描述代码生成过程，通过宏定义和子程序把中间语言解释为目标代码。
32、机器描述是通过过程的形式提供的，如：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 i
33、n 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较独立于机器，而Iadd和Fadd才与机器相关。因此，当把一个编译程序移植到一台新机器上时，Iadd和Fadd必须重写，而Add却可保持不变。解释性代码生成（续）不足之处：由于目标机的多样性、寻址方式、指令的差异等等，给中间代码的设计带来困难；代码生成语
34、言与机器密切相关，不一定能达到全部可移植；目标机的描述与代码生成算法混在一起，当描述改变时，势必引起算法的改变；需进行指令的选择、指令排序等低层次的繁琐工作，产生的目标代码质量依赖于设计者经验和能力；代码生成的视野有限，虽可进行一定范围的优化，但对协调上下文有关的优化较困难。基本思想中间表示是一序列语法树，而将机器指令用树重写规则表示，其一般形式为：Replacement template其中，Replacement为一个简单的结点，template是一个树模式匹配代码生成(树重写技术)基于树重写的代码生成基于树重写的代码生成例例:ai:=b+1:=ind+Membconst1ind+cons
35、tiregspconstaregsp+regi+ADD Rj,Riregiregj(6)regi ADD c(Rj),Ri(7)regi ADD Rj,Ri(8)regi INC Ri+regiindconstcregj+regicost1+regiregj(1)Reg0 constaMOV#a,R0(7)reg0 ADD SP,R0+reg0regSP:=ind+Membconst1ind+constiregSPreg0+indconstiregSP+reg0indconstiregSP+:=indreg0+membconst1+reg1const1:=indreg1reg0MOV#a,R0
36、ADD SP,R0ADD i(SP),R0MOV b,R1INC R1MOV R1,*R0表驱动代码生成 运用形式化机器描述，利用代码生成器的构造器自动产生代码生成器。实际上是模式匹配生成方法的更进一步自动化，它模仿从语法描述构造表和表驱动的语法分析方法。首先把对目标机的形式化描述进行预加工并转换为代码生成表，然后用代码生成程序驱动代码生成表，把中间语言的内部表示翻译成目标机的汇编代码。表驱动代码生成（续）优点这种表驱动代码生成方法易于使用和修改，便于可重定位目标代码的生成，增强了编译程序的可移植性和灵活性。不足之处它所生成的目标代码的质量依赖于机器描述的完善程度，而形式化、完善地描述一台机器并不是一件容易的事。返回
