第十二部分代码生成.ppt

《第十二部分代码生成.ppt》由会员分享，可在线阅读，更多相关《第十二部分代码生成.ppt（109页珍藏版）》请在三一文库上搜索。

1、第十二章 代码生成,第一节 代码生成概述,第二节 一个简单的代码生成程序,第三节 几种常用的代码生成程序的开发方法,第四节 全局寄存器分配（图着色法）,第五节 代码生成程序的自动化构造,知识结构,12.1 代码生成概述,代码生成是把经过语法分析或优化后的中间代码转换成 特定目标机的机器语言或汇编语言，这样的转换程序称 为代码生成程序 衡量目标代码的质量主要从占用空间和执行效率两个方 面综合考虑,第十二章 代码生成,一.代码生成程序在编译系统中的位置 代码生成程序在编译系统中的位置如图12.1所示：,目标代码一般有3种形式： （1）能够立即执行的机器语言代码，所有地址均已定位 （2）待装配的机器

2、语言模块，当需要执行时，由连接装入 程序把它们和某些运行程序连接起来，转换成能执行的机 器语言代码 （3）汇编语言代码，尚需经过汇编程序汇编，转换成可执 行的机器语言代码,二.设计代码生成程序的基本问题 1.代码生成程序的输入： 代码生成程序的输入由前端所产生的中间表示和符号表 中的信息组成 代码生成程序可以利用符号表中的信息来决定中间代码 中的名字所指示的数据对象的运行时地址,2.指令选择： 所谓指令选择，是指寻找一个合适的目标机指令序列以 实现给定的中间表示 例如，对中间代码x:=y+z，其中x,y,z均为静态分配的变 量，可以翻译成下述代码序列： LD R0,y /*将y放入寄存器R0*

3、/ ADD R0,z /*将z与R0相加*/ ST R0,x /*将R0的值存入x*/,生成代码的质量取决于它的执行速度和代码序列的长度 例如，如果目标机器有“加1”指令（INC），那么代码 a:=a+1用INC a实现是最有效的，而不是用以下的指令序 列实现： LD R0,a ADD R0,#1 ST R0,a,指令选择的基本原则： （1）减少产生代码的尺寸 （2）减少目标代码的执行时间 （3）降低目标代码的能耗 这三者在某些情况下有可能会出现冲突，在具体选择 的过程中应做折中考虑,3.寄存器分配： 寄存器分配的工作是确定在程序的哪个点将哪些变量或 中间量的值放在寄存器中比较有益 将经常使用

4、的操作数保存在寄存器中是比较有利的 一些目标机可能具有不同类型的寄存器，对寄存器使用 的一致性方面也存在一定的约束,寄存器的使用可以分成： （1）分配阶段：为程序的某一点选择驻留在寄存器中的一 组变量 （2）指派阶段：挑出变量将要驻留的具体寄存器，即寄存 器赋值,寄存器分配原则： （1）生成某变量的目标对象值时，尽量让变量的值或计算 结果保留在寄存器中直到寄存器不够分配为止 （2）当到基本块出口时，将变量的值存放在内存中 （3）在同一基本块内后面不再被引用的变量所占用的寄存 器应迟早释放，以提高寄存器的利用率,例如，考虑图12.2的两个三地址代码序列，它们仅有的区 别是第2个语句的算符不同，其

5、最短代码序列在图12.3中 给出：,4.指令调度： 指令调度是指确定程序指令的执行顺序 例如，若在MIPS 4KC上计算表示式(a+b)+c，可用表 12.1中两个不同的指令序列，它们的主要不同在于指令 顺序和寄存器的赋值：,12.2 一个简单的代码生成程序,一.计算机模型 假定一台M计算机具有n+1个通用寄存器为R0,R1,Rn， 它们既可作为累加器又可作为变址器 如果用op表示运算符，用M表示内存单元，用变量名表示 该变量所在的单元，C表示常量，*表示间址方式存取,指令形式可包含以下四种类型，见表12.2： 若op是一目运算符，则op Ri,M的意义为：op(M) Ri 以上指令中的op包

6、括一般计算机上常见的一些运算符,j,某些指令的意义说明如表12.3：,二.待用信息链表法 若在一个基本块中，变量A在四元式i中被定值，在i后面 的四元式j中要引用A值，且从i到j之间没有其他对A的定 值点，这时称j是四元式i中对变量A的待用信息或称下次 引用信息，同时也称A是活跃的，若A被多处引用则可构 成待用信息链与活跃信息链 为了得到在一个基本块内每个变量的待用信息和活跃信 息，可以从基本块出口的四元式开始由后向前扫描，为 每个变量名建立相应的待用信息链和活跃变量信息链,考虑到处理的方便，假定对基本块中的变量在出口处都是 活跃的，而对基本块内的临时变量可分为两种情况处理： 对于没有经过数据

7、流分析，且中间代码生成的算法中不允 许在基本块外引用的临时变量，则这些临时变量在基本块 出口处都认为是不活跃的 如果中间代码生成时的算法允许某些临时变量在基本块外 引用时，则假定这些临时变量被认为是活跃的,在变量的符号表的记录项中设定了待用信息和活跃信息的 栏目，其算法步骤如下： （1）对各基本块的符号表中的“待用信息”栏置“非待用”， 对“活跃信息”栏，按在基本块出中处是否为活跃而置成“活 跃”或“非活跃”，假定外部变量都是活跃的，临时变量都是 非活跃的,（2）从后向前依次处理每个四元式i ： A:=B op C，在符号 表中依次执行下述步骤： A的待用信息和活跃信息附加到i上 把A置成非待

8、用F和非活跃F B和C的待用信息和活跃信息附加到i上 把B和C待用信息置为i，活跃信息置成活跃L,例如，四元式如下： (A,B,C,D是变量，T,U,V是中间变量) (1)T:=A-B (2)U:=A-C (3)V:=T+U (4)D:=V+U,表12.4 待用信息链和活跃信息链,(4)DFL:=VFF+UFF (3)V(4)L:=TFF+U(4)L (2)U(3)L:=AFL-CFL (1)T(3)L:=A(2)L-BFL,(4)D:=V+U (3)V:=T+U (2)U:=A-C (1)T:=A-B,表12.4中“待用信息链”与“活跃信息链”的每列，从左至右 为每当从后向前扫描一个四元式时

9、相应变量的信息变化情 况，空白处为没变化,三.代码生成算法 寄存器和内存地址的描述： RVALUERi=A,C 表示Ri的现行值是变量A，C的值 AVALUEA=A 表示A的值在内存中 AVALUEA=Ri,A 表示A的值在Ri中又在内存中 AVALUEA=Ri 表示变量A的值在寄存器Ri中,寄存器分配和代码生成的具体算法： 设RETREG是一个函数过程，它的参数是一个形如i: A:=B op C的四元式，每次调用GETREG(i: A:=B op C)则返回 一个寄存器R，用以存放A的结果值 对如何给出寄存器R，要用到四元式i上的待用信息，以使 寄存器分配合理，对每个四元式的代码生成都要调用

10、函数 GETREG,GETREG分配寄存器的算法为： （1）如果B的现行值在某寄存器Ri中，且该寄存器只包含B 的值，或者B与A是同一标识符，或B在该四元式后不会再被 引用，则可选择Ri为所需的寄存器R，并转（4）,（2）如果有尚未分配的寄存器，则从中选用一个Ri为所需的 寄存器R，并转（4）,（3）从已分配的寄存器中选取一个Ri作为所需寄存器R，其 选择原则为：占用该寄存器的变量值同时在主存中，或在基 本块中引用的位置最远，这样对寄存器Ri所含的变量和变量 在主存中的情况必须先做如下调整：即对RVALUERi中的 每一变量M，如果M不是A且AVALUEM不包含M，则需完 成以下处理： 生成目

11、标代码ST Ri，M；即把不是A的变量值由Ri中送 入内存中 如果M不是B，则令AVALUEM=M，否则，令 AVALUEM=M,Ri 删除RVALUERi中的M,（4）给出R，返回,这样，一旦得到一个为四元式运算的操作寄存器R，就可 以进行代码生成，而当目标代码生成完成后，则又需修改 寄存器的使用信息和地址信息 用图12.4和图12.5给出算法的流程图：,12.3 几种常用的代码生成程序的开发方法,一.解释性代码生成法 解释性代码生成文法是建立一个代码生成专用语言，用这 种语言以宏定义、子程序等形式描述代码生成过程 通过这些宏定义和子程序把中间语言解释为目标代码 这种方法使机器描述与代码生成

12、算法结合在一起，与机器 的联系直接反映在算法中 机器描述是通过过程的形式提供的，如采用把源程序映像 成两地址代码序列的方法进行代码生成过程中，对加法的 代码生成算法如下：,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 ADD a,b fr

13、om 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,这种算法的局限性在于： （1）由于目标机的多样性、寻址方式、指令的差异等等， 给中间代码的设计带来困难 （2）代码生成语言与机器密切相关，可移植性受到限制 （3）目标机的描述与代码生成算法混在一起，当描述改变 时，势必引起算法的改变 （4）需进行指令的选择、指令的排序等低层次的繁琐工作 ，产生的目标代码质量依赖于设计者的经验和能力 （

14、5）代码生成的视野有限，虽可进行一定范围的优化，但 对协调上下文有关的优化较困难,二.模式匹配代码生成法 模式匹配代码生成方法是把对机器的描述与代码生成的算 法分开 而对在解释性代码生成方法中，所需做的较繁重的具体情 况分析的解释工作用模式匹配来代替,也就是建立一个代码生成用的机器描述语言，用以形式地 描述目标机的资源、指令及其语义等有关信息 代码生成程序根据这些信息，自动地把中间语言程序翻译 成目标机的汇编语言或机器代码 但在这种方法中，需通过形式描述的模式如实地反应机器 的特性，这并不是一件容易的事，而且进行模式匹配时耗 费时间很长，其目标代码的质量也不太理想,三.表驱动代码生成法 表驱动

15、代码生成方法，实质上是模式匹配代码生成方法的 更进一步自动化，它是模仿从语法描述构造表和表驱动的 一种语法分析方法 首先，把对目标机的形式化描述进行预加工转换成代码生 成表 然后，用表驱动的代码生成程序，来驱动代码生成表 最后，把中间语言的内部表示翻译成目标机的汇编代码 也就是说，它是用一个代码生成程序的生成器自动地构造 一个代码生成程序,这种表驱动代码生成方法的好处是：容易使用和修改，并 且能较容易地为不同的计算机构造适合于它们自己的代码 生成程序 这样将能增强编译程序的可移植性和灵活性，但是它所生 成的目标代码的质量，将依赖于机器描述的完善程序 最好的方法是用形式化的方法完善地描述一台计算

16、机，但 这并不是一件容易的事，因而这种方法有待进一步改进和 完善,12.4 全局寄存器分配（图着色法）,一.概述 为减少存取操作的次数，可以将频繁使用的变量保留在固 定的寄存器中，并使之贯穿不同的基本块边界，这就是全 局寄存器分配问题 1971年John Cokes提出，全局寄存器分配可以视为一种图 着色问题 图着色法最初在实验性编译程序IBM370 PL/I中使用， 且很快得到广泛的推广,图着色法的基本思想：将一个程序的所有对象和可供使用 的实际寄存器视为一个无向图的不同结点 若两个对象间满足下列条件之一，则在它们之间引入一条 边，以表示它们相互干扰： 同时为活跃变量的两个对象 一个对象与之

17、不能也不应该分配的寄存器,通过这种方式，构造出相应程序的干扰图 然后利用最大可供使用寄存器数的颜色种数，对干扰图的 所有结点进行着色 在对干扰图进行着色过程中，用尽量少的颜色、且将相邻 结点赋予不同的颜色,不同的颜色对应于不同的实际寄存器，若目标机具有R个 寄存器，则可用R种颜色对该干扰图进行着色 这个着色过程就是对该干扰图进行有效的寄存器赋值 若不存在R种颜色，必须将其中一些变量或临时变量放在 内存中而不是寄存器中，这个过程称为spilling,图着色的基本算法如下： （1）建立Web对象 （2）用相邻矩阵表示干扰图 （3）利用相邻矩阵合并寄存器，查找拷贝si sj，若si与sj 不相互干扰

18、，将sj的使用替换为si的使用，并将代码中的sj去 掉。若完成寄存器合并,返回到第（1）步，否则继续下一步 （4）构造干扰图的相邻列表表示 （5）计算spill开销。对每个符号寄存器，计算将其spill到内 存后又将其重新存入到寄存器中的开销,（6）干扰图的修剪。从干扰图的相邻列表中排除结点及其 相应的边。所采用的方法为degreeR和消极试探法 （7）寄存器赋值。利用相邻列表，尽量给每个结点着色， 且使没有两个相邻的结点具有同样的颜色。若成功，将每个 符号寄存器用与之具有相同颜色的实际寄存器替换，分配终 止。若失败，进行下一步 （8）寄存器的spill。将需要spill符号寄存器中的值放在内

19、存 中，然后插入spill函数(必要时再重新装入),返回到第（1）步,二.图着色寄存器分配法的相关技术 1.web对象： web是用于分配寄存器的数据对象：一个web要么是一个 定值-引用链，要么是几个相交的链的最大“并集” 图12.6为一个抽象数据流图片断,给出了2个变量（X和Y） 的定义和使用：,可以将其划分为4个web：其中一个web为在块B2定义，由 块B4和B5使用，和另一个块B3中定义，由块B5使用的两个 链的联合。其他的用链形成另外的一些web。4个web如下 所示： web Components w1 def x in B2, def x in B3, use x in B4,

20、 use x in B5 w2 def x in B5, use x in B6 w3 def y in B2, use y in B4 w4 def y in B1, use y in B3 利用web代替变量名的主要好处在于，可以区分程序中具 有相同命名但表示不同意义的变量，以方便寄存器的分配,2.干扰图的表示： 在干扰图中，每个实际寄存器和每个web分别为干扰图的 一个结点 与某个结点相连的边数，称为该结点的度degree 图12.6中4个web间的干扰图如图12.7所示：,若所有的寄存器是同构的，则没有必要将寄存器包括在干 扰图中 若目标机有两个以上的专用寄存器集合，则对这两类寄存 器

21、的分配可以分开处理，这样可以减少干扰图的复杂性， 并使之具有较少的限制,对干扰图所占用空间和访问时间进行折中考虑，采用下述 两种表示方法： （1）相邻矩阵表示法： 相邻矩阵AdjMtx2nwebs,1nwebs-1是一个低三角矩阵, 其中，矩阵的行与列分别表示干扰图中的结点 若第i个寄存器与第j个寄存器是相邻的，则 AdjMtxmax(i,j),min(i,j)的值为真，否则为假 矩阵表示实现了干扰图的快速建立，同时，能快速确定某 两个结点是否是相邻的,（2）相邻列表表示： 相邻列表用具有6个成分的数组表示： color：为一整数，其值为该结点所选颜色的值,初始值 disp：用于寄存器spil

22、ling，表示相应符号寄存器spill到某 个栈的偏移地址，初始值 spcost：spill开销，对符号寄存器,初值为0对实际寄存器， 初值为 nint：图中余下的与之相邻的结点数 adjnds：图中余下的与之相邻的结点列表 rmvadj：已从图中去掉的相邻结点列表,优点：能比较方便地确定有多少结点与给定的结点相邻， 且有哪些结点与之相邻 相邻矩阵主要用于寄存器合并，相邻列表主要用于实际的 着色过程 因此，一般情况下，首先建立相邻矩阵，并在寄存器合并 过程中对其进行不断修改，然后根据相邻矩阵建立相应的 相邻列表,3.寄存器合并： 寄存器合并是一种复写传播变换，用于消除从一个寄存器 到另一个寄存

23、器的拷贝 查找寄存器拷贝指令的中间代码，即sj si，若sj与si不 相互干扰，则查找向si写数据的指令，对其进行修改，并 将其中相应数据写到寄存器sj中，移去拷贝指令；且在干 扰图中将sj与si合并为一个结点。该结点的度为为结点sj和 si度的并集,保证合并后为R可着色的情况下，才进行合并，为此需要 两条安全策略： （1）若合并后所得结点(a,b)具有小于R个度大于或等于R的 邻居，则结点a和结点b是可以合并的 （2）对结点a的每个邻居t,要么t与结点b已是相互干扰的， 要么t的度小于R，则这种合并是安全的,寄存器合并是一种功能强大的变换，其主要作用在于： （1）简化编译过程，如消除不必要的

24、拷贝操作 （2）在过程调用之前，保证参数值被移到合适的寄存器中 （3）对源和目的操作数有特殊要求的机器指令，使其操作 数和结果在适当的位置 （4）对操作数或结果值需要使用寄存器对的指令，保证能 够为其分配寄存器对，等等,4.spilling开销的计算： spilling的结果可能会将一个web分解为两个或多个web， 从而减少干扰图中的干扰 例如,通过将图12.6中引入相应的存取操作,如图12.8所示：,这样web w1被分成4个web: w5、 w6、 w7、 w8： web Components w2 def x in B5, use x in B6 w3 def y in B2, use

25、 y in B4 w4 def y in B1, use y in B3 w5 def x in B2, tmp x in B2 w6 def x in B3, tmp x in B3 w7 x tmp in B4, use x in B4 w8 x tmp in B5, use x in B5,所得的干扰图如图12.9所示：,干扰图的相邻列表中每项有一个成分spcost。spcost用于计 算spilling相应符号寄存器所需要的开销 spill一个web的开销可表示为：,其中，def、use、copy是 web的单个定义、使用和拷贝： defwt 、usewt和 copywt相对权值,在计

26、算spill开销的过程中，应该考虑下述因素： （1）若重新计算一个web的值比重新装载更有效，可对其 进行重新计算，因此，选择重新计算的开销 （2）若spill了某条拷贝指令的源操作数或目的操作数，则 可以不再考虑该指令 （3）若在同一基本块中，某个被spill的值需要多次使用， 且直到最后一次使用，重新装载的值一直是活跃的，则在该 基本块中，只需做一次取操作,5.干扰图的修剪： （1）degreeR规则： 结点的度degree表示与之相邻结点的个数 基本思想：对给定包含一个度小于R的结点的干扰图是R 可着色的，当且仅当不包含该结点的干扰图是可着色的 当然，这种规则并不是对所有的干扰图都适用。

27、如图12.10 可以分别为2可着色的和3可着色的，但却不能利用这 种规则进行修剪：,（2）消极试探法： 消极试探法是通过排除图中degreeR的结点以对第一种 方法进行推广 基本原理：因为某个结点具有R或更多的相邻结点，这些 相邻结点并不需要所有的均具有不同的颜色,进一步地说, 它们并一定能用完R种颜色 通过从图中反复查找度小于R的结点，开始对图进行着色 选择一个degreeR的结点消极地放入栈中，选择原则： 根据其spill cost值除以其目前的度，所得的值最小的结点 优先级最高,三.示例 如图12.11所示，代码片断中使用了符号寄存器：,假设可供分配使用的寄存器为r2 、r3、 r4，分

28、别为其建 立干扰图和相邻矩阵，如图12.12所示：,由于符号寄存器s1在退出块B1时，s0从其定义点之后都不 再是活跃的，因此它们的spill开销值都为无穷大，如图 12.13所示：,符号寄存器s1无相邻结点，首先将其先放入栈中。实际寄 存器r2 、r3、 r4以及符号寄存器s4、s9的度都为2，依次将 它们放入栈中，s9 s4 r4 r3 r2 s1 。干扰图的修剪过程如 图12.14所示：,修剪后的干扰图如图12.14(a)所示，可以看出，结点s8的度 小于3，也将其压入栈中：s8 s9 s4 r4 r3 r2 s1 这时，所得的干扰图如图12.14(b)所示： 在余下的干扰图中，每个结点

29、的度都大于或等于3，只好 使用消极试探法，即把s7放入栈中，这样简化了干扰图使 其变成如图12.14(c)所示： 进而将s5压入栈中。这时所有的结点的度都小于3，将它 们依次都放入栈中：s2 s3 s6 s5 s7 s8 s9 s4 r4 r3 r2 s1,依次将各个结点从栈中弹出的同时给它们赋予不同颜色值, 并根据AdjLsts.rmvadj 域的值重构干扰图 当弹出3个结点时，干扰图如图12.15所示：,当弹出第四个结点，即s5就没有可供使用的颜色。这时就 需要进行寄存器的spilling。分别将块B4中的s7和s5 spilling 到内存中，其基址寄存器为r10，偏移量disp分别为0

30、和4。 所得的代码的片断如图12.16所示：,重新为其建立干扰图，如图12.17所示：,利用degreeR规则对其进行修剪，并将实际寄存器赋给与 之具有相同颜色的符号寄存器，所得的代码片断如图 12.18所示：,12.5 代码生成程序的自动化构造,在20世纪70年代和80年代，开始出现了编译后端的自动构 造技术，开发了一系列代码生成程序的构造器，如：BEG 、iburg、twig、MBURG等 研究声明，这种利用声明性描述构造代码生成程序要比手 工编写容易，而且需要的工作量少，但其产生代码的执行 效率往往还不足手工开发的十分之一，从而很难为广大用 户所接受,如图12.19所示，代码生成程序的构

31、造器的输入是代码生成 描述，输出是代码生成程序：,一.模式匹配与动态规划 这种方法是由Aho、Ganapathi和Tjiang开发的 基本思想：将目标机指令用树重写规则表示，机器指令集 合表示为一个树模式集合，且将描述不同指令的树模式赋 予相对权值以表示执行该指令的相对代价，然后利用动态 规划技术选择最优的指令集合来计算相应的中间表示树。 通过在中间表示树中重复查找与相应模板相匹配的子树并 用相应的替换结点进行重写，即在将每个中间表示树规约 为一个简单的结点过程中产生目标代码,树重写规则可表示为：label:patterncost=action label是与文法规则左边的非终结符相对应的标识

32、符 pattern为树模式 cost部分是由代码生成程序执行的C代码。当某个子树与一 个特定模式相匹配时，它返回一个开销值供动态规划算法 使用，同时确定是否该模式满足匹配子树的语义标准 action部分也是C代码。若模式匹配成功且动态规划算法推 断出该模式是整个树的最小覆盖的一部分，则可执行。 action的可能包含动作有：用另一个树替换被匹配的子树 、输出代码或别的动作 若cost被删除，则返回一个缺省值并假定模式匹配成功 若action被删除，则表示什么都不做,优化原则：若其所有的子问题已经得到比较优化的解，则 通过一种特殊的方法将所有子问题的解结合起来，可以得 到整个问题的最优解 动态规

33、划算法为IR树的每个结点赋一个开销值，其值为以 覆盖该结点为根的子树的最好指令序列的各指令开销的总和,图12.20为简单的树重写系统：,重写规则用树的形式描述，断言IsShort()确定它的参数是 否可以放进SPARC指令的13位常量域k中 相应的twig规格说明如图12.21所示：,prologue实现函数IsShort() Label声明部分列出所有作为标号的标识符 node声明列出除标号标识符之外所有出现在模式中的标识符 $为指向被特定模式匹配的树的根结点的指针 $i$为指向该根结点第i个孩子的指针 ABORT通过返回一个无穷大的开销，终止模式匹配过程 NODEPTR为结点的类型 get

34、reg()是寄存器分配器 Emit_.()子程序的作用是输出指令,考虑下面一段中间代码：st(add(ld(r8,8),add(r2,ld(r8,4) 相应的中间表示树如图12.22所示：,路径串可用整数标号替换结点标识符如图12.23所示：,图12.20的所有规则构造一个自动机，其路径串和规则如图 12.24所示：,结果自动机如图12.25所示：,二.基于语法制导的代码生成程序自动构造技术 也称为Graham-Glanville方法 它利用类似于上下文无关文法的规则和相应的机器指令模 板描述机器操作 当一条代码生成描述规则与一条波兰式中缀表示字符串的 子字符串相匹配，且满足有关的语义限制时，

35、将被匹配的 部分用相应规则左边的符号替代，同时输出实例化后相应 的指令模板 Graham-Glanville代码生成程序由中间语言变换、模式匹 配器和指令生成3部分组成,图12.26中(a)给出了LIR指令的子集，其中每个参数的位置 用一个数字表示，以用于中间表示字符串与代码生成规则 和指令模板的匹配 相应的规则和SPARC的指令模板如图12.26(b)和(c)所示 其中，r.n表示寄存器，k.n表示常量，表示空字符串 数字n的作用：协调模式匹配与代码输出的关系、在规则 中描述语法限制,下面以图12.27的LIR代码序列的目标代码生成为例： 在波兰式代码中，用表示load（取）操作，表示sto

36、re （存）操作，mov表示从寄存器到寄存器的拷贝 图12.28为该代码序列的树形表示 假设当代码序列结束时，寄存器r3和r4不是活跃的 因此，在树形图中不需要显式表示，但r1和r2需要保留 该代码序列用波兰式可表示如下： r2 r8+r8 8+r2r1+r8 4+r8 4-r1 1,如图12.29所示，Graham-Glanville方法在语法分析的过程 中进行模式匹配，同时输出SPARC指令，下划线以上部分 显示被匹配的字符串，下划线以下部分为该字符串归约的 结果：,这种代码生成程序实质上是一个SLR(1)的语法分析器 只是它输出的是机器指令而不是语法分析树或中间代码 这种语法分析器识别一

37、种产生式为机器描述规则的语言,且在 产生式规则中,将表示为非终结符N,并加入产生式S N* 机器描述规则左边出现非终结符是允许的，与语法分析过 程不一样，这里机器描述文法几乎总是具有二义性,解决二义性方法： 在遇到既可以左移又可以归约的状态时，选择左移操作，且 尽可能地匹配最长的字符串 根据机器描述规则的优化级对其进行排序，即在代码生成过 程，用第一个与之相匹配的规则进行归约,三.基于语义制导的代码生成程序自动构造技术 基于语义制导的代码生成程序是由Ganapathi和Fischer开 发的，也称为属性文法或词缀文法方法 通过使用属性，将语义信息加入代码生成规则中 用表示继承属性，表示综合属性

38、，属性值写在箭头的 后面 在代码生成过程中，属性除了传递值之外，还用于控制代 码的生成、产生新的属性值以及产生副作用 控制部分通过断言（用大写斜体字表示）来实现 一条规则是可应用的，当且仅当它与目标字符串语法上相 匹配且满足所有的断言条件,action部分用大写字母表示，主要用于计算新的属性值和产 生副作用。当然，最重要的副作用为输出目标代码 因此，对地上一节讨论的Graham-Glanville方法中的寄存器 内容与常量相加的规则是： r.3 +r.1 k.2 add r.1, k.2, r.3 r.3 +k.2 r.1 add r.1, k.2, r.3 转换为相应的属性文法规则为： rr

39、2 +rr1kk1 IsShort(k1) ALLOC(r2) EMIT3(“add”,r1,k1,r2) rr2 +kk1rr1 IsShort(k1) ALLOC(r2) EMIT3(“add”,r1,k1,r2),除了从低级中间语言中产生目标代码之外，属性文法也用于 存储绑定、将几种窥孔优化技术集成到代码生成中，以及对 目标机描述规则集合进行分解以减少尺寸,【本章小结】 由于代码生成的目标代码取决于具体的机器结构、指令 格式、字长及寄存器的个数和种类，并与指令的语义和所用操 作系统、存储管理等都密切相关，因此实现非常困难。通过本 章学习，仅为学生初步了解一个高级程序设计语言编译程序目 标代码生成需要考虑的问题和解决这些问题的基本原则和方法 ，为今后应用打下初步基础。,第12章 习题 第1题：一个编译程序的代码生成要着重考虑哪些问题? 第2题：决定目标代码的因素有哪些？ 第3题：为什么在代码生成时要考虑充分利用寄存器？ 第4题：寄存器分配的原则是什么？,第12章 作业题 P301： 1.,