编译原理 第十章 代码生成

第十章 代码生成代码生成概述 构造代码生成程序的几种方法

代码生成概述代码生成阶段 构造代码生成程序要考虑的因素 一个简单的代码生成程序的构造

代码生成器(程序)的位置 代码生成器源程序 编译前端 中间 代码 代码优化 中间 代码 代码生成器 目标程序

符号表

代码生成器的位置 代码生成器的输入

–中间代码–符号表中的信息

目标代码一般有三种形式： 能够立即执行的机器语言代码，所有地址均已定位 待装配的机器语言模块。当需要执行时，由连接装

入程序把它们和某些运行程序连接起来，转换成能 执行的机器语言代码 汇编语言代码。尚需经过汇编程序汇编，转换成可

执行的机器语言代码

构造代码生成器所要考虑的主要问题

代码生成所要考虑的主要问题 如何使生成的目标代码较短 如何充分利用计算机的寄存器，减少目标代码中访问存

储单元的次数

返回

代码生成的主要成份

指令选择 寻找一个合适的目标机指令以实现给定的中间表示

寄存器分配 确定在程序的哪个点将哪些值放在寄存器中比较有益

指令调度 确定程序指令的执行顺序

三者的关系

指令选择

如：中间代码 a:=a+1: 实现1:INC a

实现2:LD R0,a ADD R0, #1 ST R0,a

主要功能 多数CPU的指令集合具有冗余性。指令选择器选择其中之 一以产生最好的代码。

指令选择的基本原则 减小产生代码的尺寸 减小目标代码的执行时间

目标机器的地址方式地址方式直接地址方式

汇编形式M R *R c(R)

地址M R contents(R) c+contents(R)

增加的开销1 0 1 1

寄存器方式间接寄存器方式 索引方式 间接索引方式

*c(R)

contents(c+contents(R))

2

每条指令的执行代价=每条指令访问主存单元次数+1

a:=b+c

1.

MOV b,ADD c, MOV R0,

R0R0 a cost=6

2.

MOV b,ADD c,

aa cost=6

假定R0, R1和R2中分别存放了a, b和c的地址, 采用:

3.

MOV *R1,ADD *R2,

*R0*R0 cost=6

假定R1和R2中分别包含b和c的值, 并且b的值在这个赋 值以后不再需要, 则还可有 4. ADD R2, MOV R1, R1 a cost=3

寄存器分配

指令在寄存器中访问操作数的开销要比在内存中访问小。 且许多指令不能直接访问内存。应将经常使用的操作数保 存在寄存器中。寄存器是比较稀少的资源，程序所需要的 寄存器要比可用的寄存器多。寄存器分配负责确定在程序 的哪个点将哪些值放在寄存器中比较有益。 寄存器的分配可以分成两个子问题： 在寄存器分配期间，为程序的某一点选择驻留在寄存器中的

一组变量； 在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器。

寄存器分配原则

尽量让变量的值或计算结果保留在寄存器。这样，访问变 量值时可减少对内存的存取次数，以提高运行速度； 当到基本块出口时，将变量的值存放在内存中，因为一个 基本块可能有多个后继结点或多个前驱结点，同一变量名 在不同前驱结点的基本块内出口前存放的 R 可能不同，或 没有定值，所以应在出口前把寄存器的内容放在内存中， 这样从基本块外入口的变量值都在内存中；

在同一基本块内后边不再被引用的变量所占用的寄存器应 尽早释放，以提高寄存器的利用率。

寄存器分配与寄存器赋值

寄存器分配 确定在程序的某个点将哪些值放在寄存器中

寄存器赋值 确定分配有寄存器的值应该在哪个寄存器中。由于一

些目标机可能具有不同类型的寄存器，因此，对寄存 器使用的一致性方面也存在着一定的约束。

指令调度

对具有流水线限制的体系结构，这个阶段是必须的。如： RISC体系结构一个通用的流水线限制为：从内存中取入 寄存器中的值在随后的某几个周期中是不能用的。在这期 间，调不依赖于该取入值的指令来执行是很重要的。 必须找一个指令(与被取值无关)在取指令之后立即执行， 如果找不到相应的指令，这些周期就会被浪费。 不同在于指 令顺序和寄 存器的赋值 图12.27

一个简单的代码生成器在一个基本块范围内考虑如何充分利用寄存器的问题： 尽可能地让该变量的值保留在寄存器中 尽可能引用变量在寄存器中的值

待用信息：若在一个基本块中，变量A在四元式i中被定值， 在i后面的四元式j中要引用A值，且从i到j之间没有其它对A 的定值点，这时我们称 j是四元式i中对变量A的待用信息， 同时也称A是活跃的，若A被多次引用则可构成待用信息链 与活跃信息链。 可从基本块的出口由后向前扫描，对每个变量建立相应的待 用信息链和活跃变量信息链。

计算待用信息的算法：符号表中增加“待用信息”栏和“活跃信息”栏对各基本块的 符号表中的“待用信息”栏和“活跃信息”栏置初值，即把 “待用信息”栏置“非待用”,对“活跃信息”栏按在基本块 出口处是否为活跃而置成“活跃”或“非活跃”。这里假定变 量都是活跃的，临时变量都是非活跃的。从基本块出口到基本块入口由后向前依次处理每个四元式i, A:=B op C,依次执行下述步骤：

a)把符号表中变量A的待用信息和活跃信息附加到四元式上。

b)把符号表中变量A的待用信息栏和活跃信息栏分别置为“非待用” 和“非活跃”。

c)把符号表中变量B和C的待用信息和活跃信息附加到四元式i上。d)

把符号表中变量B和C的待用信息栏置为“i”,活跃信息栏置为 “活跃”。

注意，以上a)、b)、c)和d)的次序不能颠倒。

四元式序列如下：(1) T:=A-B (2) U:=A-C (3) V:=T+U (4) D:=V+U变 量 名 A B C D T U V 初值 F F F F F F F

待用信息和活跃信息 待用信息 待用信息链 (2) (2) F (4) (4) (3) (3) F F F (1) (1) 活跃信息 初值 L L L L F F F 活跃信息链 L L F L L L L F F F L L

“待用信息”与“活跃信息”的每列从左至右为每从后向前 扫描一个四元式时相应变量的信息变化情况。 待用信息和活跃信息在四元式上的标记如下所示： (1) (2) (3) (4) T(3)L:=A(2)L-BFL U(3)L:=AFL-CFL V(4)L:=TFF+U(4)L DFL:=VFF+UFF