第12章 代码生成

1、第十二章 代码生成 代码生成要考虑的主要问题代码生成要考虑的主要问题 基本块的代码生成(在一个基本块范围内在一个基本块范围内考虑如何充分利用寄存器的问题考虑如何充分利用寄存器的问题) ) 基于树重写的代码生成l 代码生成要考虑的主要问题代码生成要考虑的主要问题具体细节依赖于目标机器和操作系统具体细节依赖于目标机器和操作系统共同的问题：共同的问题：1. 充分利用寄存器充分利用寄存器基本块中基本块中全局全局 寄存器分配：不把寄存器平均分配给各个变量使寄存器分配：不把寄存器平均分配给各个变量使用，而是从可用的寄存器中分出几个，固定分配给几个变量单用，而是从可用的寄存器中分出几个，固定分配给几个变量单

2、独使用。标准独使用。标准以各变量在循环内需要访问主存单元的次数以各变量在循环内需要访问主存单元的次数为标准。为标准。2. 选择计算机指令系统选择计算机指令系统3. 选择计算次序选择计算次序 目标代码的三种形式目标代码的三种形式 地址代真的机器代码地址代真的机器代码 待装配的机器代码模块待装配的机器代码模块 汇编语言汇编语言（宏汇编）（宏汇编）机器指令形式机器指令形式(op source ,destination)ADD s,d / d+s SUB s,d /d-s MOV s,d /s d机器指令开销机器指令开销 ( (cost)cost)MOV R,M 开销开销 2ADD #1 ,R 开销开

3、销 2MOV R0,R1 开销开销 1目标机器的地址方式地址方式汇编形式地址增加的开销直接地址方式MM1寄存器方式RR0间接寄存器方式*Rcontents(R)0索引方式c(R)c+contents(R)1间接索引方式*c(R)contents(c+contents(R)1a:=b+c1. MOV b, R0ADD c,R0cost=6MOV R0, a2.MOV b,aADD c,acost=6 假定R0, R1和R2中分别存放了a, b和c的地址, 我们采用:3.MOV *R1,*R0ADD *R2,*R0cost=2 假定R1和R2中分别包含b和c的值, 并且b的值在这个赋值以后不再需要

4、, 则我们还有4.ADD R2,R1MOV R1,acost=3T4:=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, T4T2:=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 简单的代码生成器简单的代码

5、生成器 （基本块内）（基本块内）在一个基本块范围内考虑如何充分利用寄存器的问题：在一个基本块范围内考虑如何充分利用寄存器的问题：l 尽可能地让该变量的值保留在寄存器中尽可能地让该变量的值保留在寄存器中l 尽可能引用变量在寄存器中的值尽可能引用变量在寄存器中的值1 待用信息：若在一个基本块中，变量待用信息：若在一个基本块中，变量 A在四元式在四元式i中被定中被定值，在值，在i后面的四元式后面的四元式j中要引用中要引用A值，且从值，且从i到到 j之间没有其之间没有其它对它对A的定值点，这时我们称的定值点，这时我们称 j是四元式是四元式i中对变量中对变量A的待用的待用信息或称下次引用信息，同时也称信

6、息或称下次引用信息，同时也称 A是活跃的，若是活跃的，若A被多次被多次引用则可构成待用信息链与活跃信息链。引用则可构成待用信息链与活跃信息链。可从基本块的出口由后向前扫描，对每个变量建立相应的待用可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。信息链和活跃变量信息链。计算待用信息的算法：计算待用信息的算法：1 对各基本块的符号表中的对各基本块的符号表中的“待用信息”栏和“待用信息”栏和“活跃信息”“活跃信息”栏置初值，即把栏置初值，即把“待用信息”栏置“待用信息”栏置“非待用”，对“非待用”，对“活跃“活跃信息”栏按在基本块出口处是否为活跃而置成信息”栏按在基本块

7、出口处是否为活跃而置成“活跃”或“活跃”或“非活跃”。这里假定变量都是活跃的，临时变量都是非“非活跃”。这里假定变量都是活跃的，临时变量都是非活跃的。活跃的。1 从基本块出口到基本块入口由后向前依次处理每个四元从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式式。对每个四元式 i: A:=B op C，依次执行下述步骤：，依次执行下述步骤：a） 把符号表中变量把符号表中变量 A的待用信息和活跃信息附加到四元式的待用信息和活跃信息附加到四元式 i上。上。b） 把符号表中变量把符号表中变量 A的待用信息栏和活跃信息栏分别置为的待用信息栏和活跃信息栏分别置为“非待用”和“非待用”和“非

8、活跃”。“非活跃”。（由于在（由于在 i 中对中对 A的定值只能的定值只能在在 i以后的四元式才能引用，因而对以后的四元式才能引用，因而对 i 以前的四元式来说以前的四元式来说 A是不活跃也不可能是待用的）是不活跃也不可能是待用的）c） 把符号表中变量把符号表中变量 B和和 C的待用信息和活跃信息附加到四元的待用信息和活跃信息附加到四元式式 i上。上。d） 把符号表中变量把符号表中变量 B和和 C的待用信息栏置为的待用信息栏置为“i”，活跃信”，活跃信息栏置为息栏置为“活跃”。“活跃”。注意，以上注意，以上 a）和）和 b），），c）和）和 d）的次序不能颠倒。）的次序不能颠倒。例：例： 若用

9、若用 A，B，C，D表示变量，用表示变量，用 T，U，V 表示中间变表示中间变量，有四元式如下：量，有四元式如下：（1） T:=A-B（2） U:=A-C（3） V:=T+U（4） D:=V+U其名字表中的待用信息和活跃信息如下表，用其名字表中的待用信息和活跃信息如下表，用“F”表示”表示“非“非待用”待用”“非活跃”，用“非活跃”，用“L”表示活跃。”表示活跃。(1)(2)(3)(4)表示四元表示四元式序号。式序号。待用信息和活跃信息待用信息和活跃信息 待用信息待用信息 活跃信息活跃信息变变量量名名初值初值 待用信息链待用信息链初值初值 活跃信息链活跃信息链A F(2)(1) L L LB

10、F(1) L LC F(2) L LD F F L FT F(3) F F L FU F(4)(3) F F L L FV F(4) F F L F表中表中“待用信息链”与“待用信息链”与“活跃信息链”的每列从左至右为每从“活跃信息链”的每列从左至右为每从后向前扫描一个四元式时相应变量的信息变化情况，空白处为后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化。没变化。待用信息和活跃信息在四元式上的标记如下所示：待用信息和活跃信息在四元式上的标记如下所示：(1) T(3)L:=A(2)L-BFL(2) U(3)L:=AFL-CFL(3) V(4)L:=TFF+U(4)L(4) DFL:

11、=VFF+UFF2 寄存器描述和地址描述寄存器描述和地址描述为随时掌握各寄存器的情况，为随时掌握各寄存器的情况， 寄存器描述数组寄存器描述数组 RVALUE: 描述每个寄存器当前的状况描述每个寄存器当前的状况 变量地址描述数组变量地址描述数组 AVALUE：表示变量的存放情况：表示变量的存放情况3 基本块的代码生成算法基本块的代码生成算法假设只有假设只有 A:=B op C的四元式序列的四元式序列A 对每个四元式对每个四元式 i: A:=B op C，依次执行下述步骤：，依次执行下述步骤：1 以四元式以四元式 i: A:=B op C为参数，调用过程为参数，调用过程 getreg(i: A:=

12、B opC)。从。从 getreg 返回时，得到一寄存器返回时，得到一寄存器 R，用它作存放，用它作存放 A现现行值的寄存器；行值的寄存器；2 利用利用 AVALUEB和和 AVALUEC，确定出，确定出 B和和 C 现行值现行值存放位置存放位置 B和和 C，如果其现行值在寄存器中，则把寄存器，如果其现行值在寄存器中，则把寄存器取作取作 B和和 C；1 如如 BR，则生成目标代码，则生成目标代码LD R ， Bop R ， C 否则，生成目标代码否则，生成目标代码 op R，C 如如 B或或 C为为 R，则删除，则删除 AVALUEB或或 AVALUEC中中的的 R2 令令 AVALUEB=R

13、，并令，并令 RVALUER=A，以表示变，以表示变量量 A的现行值只在的现行值只在 R中并且中并且 R中的值只代表中的值只代表 A的现行值；的现行值；3 如如 B或或 C的现行值在基本块中不再被引用，它们也不是基的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量本块出口之后的活跃变量（由四元式（由四元式 i 上的附加信息知上的附加信息知道），并且其现行值在某个寄存器道），并且其现行值在某个寄存器 Rk中，则删除中，则删除RVALUERk中的中的 B或或 C以及以及 AVALUEB或或AVALUEC中的中的 Rk，使该寄存器不再为，使该寄存器不再为 B或或 C 所占用。所占用。B

14、处理完基本块中所有四元式之后，对现行值在某寄存器处理完基本块中所有四元式之后，对现行值在某寄存器 R中的每个变量中的每个变量 M，若它在出口之后使活跃的，则生成，若它在出口之后使活跃的，则生成 STR，M，放到主存中。，放到主存中。其中d在基本块的出口, 假定它是活跃的。uvdutvcaubatcacabad:)()()(:代码序列语句生成的代码 寄存器描述器地址描述器t: = abMOV a,R0SUB b,R0空寄存器R0包含 tt 在 R0中u: = acMOV a,R1SUB c,R1R0包含 tR1包含 ut 在 R0中u 在 R1中v: = tuADD R1,R0R0包含 vR1包

15、含 uu 在 R1中v 在 R0中d: = vuADD R1,R0MOV R0,dR0包含 dd 在 R0中d 在 R0中和存储器中启发式排序算法(1) while存在未列入表的内部结点do(2) 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例：赋值语句例：赋值语句 T4:=A+B-(E-(C+D)四元式序列

16、四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG： A B E C Dn9n3n8n1n2n7n6n4n5 T4 T1 T3 T2 + - - +基于树重写的代码生成基于树重写的代码生成例例:ai:=b+1: =ind+Membconst1ind+constiregspconstaregsp+regi+ADD Rj,Riregiregj(1) regi constcMOV #c, Ri(2) regi memaMOV a, Ri(3) mem MOV Ri, a(4) mem MOV Rj, *Ri(5) regi MOV c(Rj), Ri: =memaregi: =memaregjindconstcregjregi+(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+