【编译原理笔记20】代码生成：代码生成器的主要任务，一个简单的目标机模型，指令选择，寄存器的选择，寄存器选择函数getReg的设计，窥孔优化

2024-02-01 14:01:46

本次笔记内容：
9-1 代码生成器的主要任务
9-2 一个简单的目标机模型
9-3 指令选择
9-4 寄存器的选择
9-5 寄存器选择函数getReg的设计
9-6 窥孔优化

本节课幻灯片，见于我的 GitHub 仓库：第20讲代码生成.pdf

文章目录

代码生成器的主要任务
一个简单的目标机模型
- 目标机器的主要指令
- 寻址模式
指令选择
寄存器的选择
寄存器选择函数getReg的设计
- 计算R的“费用”
- 寄存器Rx的选择
窥孔优化

代码生成器的主要任务

一、指令选择

选择适当的目标机指令来实现中间表示(IR)语句，例如：

三地址语句 x = y + z
目标代码

LD R0, y      /* 把y的值加载到寄存器R0中*/
ADD R0, R0, z /* z加到R0上*/
ST x, R0      /* 把R0的值保存到x中*/

如上，直接进行生成，会产生一些冗余指令。目标代码需要进一步优化。

二、寄存器分配和指派：把哪个值放在哪个寄存器中

三、指令排序：按照什么顺序来安排指令的执行

一个简单的目标机模型

三地址机器模型：

加载、保存、运算、跳转等操作
内存按字节寻址
n个通用寄存器 R 0 , R 1 , … , R n − 1 R_0, R_1, …, R_{n-1} R0,R1,…,Rn−1
假设所有的运算分量都是整数
指令之间可能有一个标号

目标机器的主要指令

加载指令 LD dst, addr
- LD r, x
- LD r1, r2
保存指令 ST x, r
运算指令 OP dst, src1, src2
无条件跳转指令 BR L
条件跳转指令 Bcond r, L
- 例： BLTZ r, L

寻址模式

变量名 a a a，例如：LD R1, a，即R1 = contents(a)，将地址 a 中的内容放到寄存器 R1
a ( r ) a(r) a(r)，a是一个变量，r是一个寄存器，例如：LD R1, a(R2)，即R1 = contents(a + contents(R2))
c ( r ) c(r) c(r)，c是一个整数，例如：LD R1, 100(R2)，即R1 = contents(contents(R2) + 100)，表示寄存器 R2 中存放的地址，加上整数c，其表示的地址所存放的内容。
∗ r *r ∗r，在寄存器r的内容所表示的位置上存放的内存位置，例如：LD R1, *R2，即R1 = contents(contents(contents(R2)))，这是间接寻址模式
∗ c ( r ) *c(r) ∗c(r)，在寄存器r中内容加上c后所表示的位置上存放的内存位置，例如：LD R1, *100(R2)，即R1 = contents(contents(contents(R2) + 100))
KaTeX parse error: Expected 'EOF', got '#' at position 1: #̲c，例如LD R1, #100，即R1 = 100。

指令选择

运算语句的目标代码

三地址语句:

x = y - z

目标代码：

LD R1 , y        // R1 = y
LD R2 , z        // R2 = z
SUB R1 , R1 , R2 // R1 = R1 - R2
ST x , R1        // x = R1

尽可能避免使用上面的全部四个指令，如果：

所需的运算分量已经在寄存器中了
运算结果不需要存放回内存

数组寻址语句的目标代码

三地址语句：

b = a[ i ]
a是一个实数数组，每个实数占8个字节

目标代码：

LD R1 , i      // R1 = i
MUL R1 , R1, 8 // R1=R1 * 8
LD R2 , a(R1)  // R2=contents ( a + contents(R1) )
ST b , R2      // b = R2

三地址语句

a [ j ] = c
a是一个实数数组，每个实数占8个字节

目标代码：

LD R1 , c       // R1 = c
LD R2 , j       // R2 = j
MUL R2 , R2 , 8 //R2 = R2 * 8
ST a(R2) , R1   // contents(a+contents(R2))=R1

指针存取语句的目标代码

三地址语句：

x = *p

目标代码：

LD R1, p      // R1 = p
LD R2, 0 (R1) // R2 = contents ( 0 + contents (R1) )
ST x , R2     // x = R2

三地址语句：

*p = y

目标代码：

LD R1 , p    // R1 = p
LD R2 , y    // R2 = y
ST 0(R1), R2 //contents ( 0 + contents ( R1 ) ) = R2

条件跳转语句的目标代码

三地址语句：

if x < y goto L

目标代码：

LD R1 , x        // R1 = x
LD R2 , y        // R2 = y
SUB R1 , R1 , R2 // R1=R1 - R2
BLTZ R1 , M      // if R1 < 0 jump to M

M是标号为L的三地址指令所产生的目标代码中的第一个指令的标号。

过程调用和返回的目标代码

静态区存储分配

我们假设，活动记录的第一个位置用来存放过程调用的返回地址。因此，上面的ST指令将返回地址赋给了被调用过程活动记录的开始处。BR则负责将空值转到目标代码上。

栈式存储分配

寄存器的选择

三地址语句的目标代码生成

对每个形如x = y op z的三地址指令I，执行如下动作：

调用函数 g e t r e g ( I ) getreg( I ) getreg(I)来为x、y、z选择寄存器，把这些寄存器称为 R x R_x Rx、 R y R_y Ry、 R z R_z Rz
如果 R y R_y Ry中存放的不是y ，则生成指令“ L D R y , y ′ LD\; R_y ,\; y′ LDRy,y′”。y′是存放y的内存位置之一
类似的，如果Rz中存放的不是z，生成指令“ L D R z , z ′ LD\; R_z,\; z′ LDRz,z′”
生成目标指令“ O P R x , R y , R z OP\; R_x,\; R_y,\; R_z OPRx,Ry,Rz”

寄存器描述符和地址描述符

寄存器描述符(register descriptor)：

记录每个寄存器当前存放的是哪些变量的值

地址描述符(address descriptor)：

记录运行时每个名字的当前值存放在哪个或哪些位置
该位置可能是寄存器、栈单元、内存地址或者是它们的某个集合
这些信息可以存放在该变量名对应的符号表条目中

基本块的收尾处理

对于一个在基本块的出口处可能活跃的变量x，如果它的地址描述符表明它的值没有存放在x的内存位置上，则生成指令“ST x, R” ( R是在基本块结尾处存放x值的寄存器)

管理寄存器和地址描述符

当代码生成算法生成加载、保存和其他指令时，它必须同时更新寄存器和地址描述符。

对于指令“LD R , x”：

修改R的寄存器描述符，使之只包含x
修改x的地址描述符，把R 作为新增位置加入到x的位置集合中
从任何不同于x的地址描述符中删除R

对于指令“ O P R x , R y , R z OP\; R_x ,\; R_y\; , R_z OPRx,Ry,Rz”：

修改 R x R_x Rx的寄存器描述符，使之只包含x
从任何不同于 R x R_x Rx的寄存器描述符中删除x
修改x的地址描述符，使之只包含位置 R x R_x Rx
从任何不同于x的地址描述符中删除 R x R_x Rx

对于指令“ST x , R”：

修改x的地址描述符，使之包含自己的内存位置

对于复制语句x=y，如果需要生成加载指令“ L D R y , y LD\; R_y ,\; y LDRy,y′ ”则：

修改 R y R_y Ry的寄存器描述符，使之只包含y
修改y的地址描述符，把 R y R_y Ry作为新增位置加入到y的位置集合中
从任何不同于y的变量的地址描述符中删除 R y R_y Ry
修改 R y R_y Ry的寄存器描述符，使之也包含x
修改x的地址描述符，使之只包含 R y R_y Ry

例

假设t、u、v是该基本块的局部临时变量；a、b、c、d在基本块的出口处活跃。

左边是寄存器描述符，右边是地址描述符。

我个人总结是：地址描述符中，R1、R2、R3只能出现一次（如果寄存器在寄存器描述符是一一对应的话）。

如山，a的R1会被删除。

如上，c的R3将被删除。

如上，t的R2被删除。

五句话都处理完了，发现，变量a和d还都保存在寄存器中，而不在地址中。因为其在出口处是活跃的，因此生成两条保存质量，保存其地址。