阅读更多

1 代码生成器的主要任务

指令选择

选择适当的目标机指令来实现中间表示（IR）语句
例：
- 三地址语句：$x = y + z$
- 目标代码
  - $LD\;\;R0,y$：把$y$的值加载到寄存器$R0$中
  - $ADD\;\;R0,R0,z$：$z$加到$R0$上
  - $ST\;\;x,R0$：把$R0$的值保存到$x$中

寄存器分配和指派

把哪个值放在哪个寄存器中

指令排序

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

2 一个简单的目标机模型

三地址机器模型

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

2.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$

2.2 寻址模式

变量名$a$
- 例：$LD\;\;R1, a$，即$R1 = contents (a)$
$a(r)$
- $a$是一个变量，$r$是一个寄存器
- 例：$LD\;\;R1, a(R2)$，即$R1 = contents ( a + contents(R2) )$
$c(r)$
- $c$是一个整数
- 例：$LD\;\;R1, 100 (R2)$，即$R1 = contents (contents(R2) + 100 )$
$*r$
- 在寄存器$r$的内容所表示的位置上存放的内存位置
- 例：$LD\;\;R1, * R2$，即$R1 = conents (contents (contents (R2) ) )$
$*c(r)$
- 在寄存器$r$中内容加上$c$后所表示的位置上存放的内存位置
- 例：$LD\;\;R1, *100(R2)$，即$R1 = conents (contents (contents(R2) + 100 ) )$
$\#c$
- 例：$LD\;\;R1, \#100$，即$R1 = 100$

3 指令选择

3.1 运算语句的目标代码

三地址语句

$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$

尽可能避免使用上面的全部四个指令，如果满足以下条件，就可以删去某些目标代码

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

3.2 数组寻址语句的目标代码

访问

三地址语句
- $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$

3.3 指针存取语句的目标代码

访问

三地址语句
- $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$

3.4 条件跳转语句的目标代码

三地址语句

$if\;x \lt 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 \lt 0\;jump\;to\;M$

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

3.5.1 静态存储分配

方法调用

三地址语句
- $call\;\;callee$
目标代码
- $ST\;\;callee.staticArea, \#here + 20$，即$callee$的活动记录在静态区中的起始位置
- $BR\;\;callee.codeArea$，即$callee$的目标代码在代码区中的起始位置

方法返回

三地址语句
- $return$
目标代码
- $BR\;\;*callee.staticArea$

3.5.2 栈式存储分配

方法调用

三地址语句
- $call\;\;callee$
目标代码
- $ADD\;\;SP, SP, \#caller.recordsize$
- $ST\;\;0(SP ), \#here + 16$
- $BR\;\;callee.codeArea$

方法返回

三地址语句
- $return$
目标代码
- 被调用过程
  - $BR\;\;*0(SP )$
- 调用过程
  - $SUB\;\;SP, SP, \#caller.recordsize$

4 寄存器的选择

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

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

调用函数$getreg( I )$来为$x$、$y$、$z$选择寄存器，把这些寄存器称为$R_x$、$R_y$、$R_z$
如果$R_y$中存放的不是$y$ ，则生成指令“$LD\;\;R_y, y^{\prime}$”。$y^{\prime}$是存放$y$的内存位置之一
类似的，如果$R_z$中存放的不是$z$，生成指令“$LD\;\;R_z, z^{\prime}$”
生成目标指令$OP\;\;R_x, R_y, R_z$

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

寄存器描述符(register descriptor)

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

地址描述符(address descriptor)

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

4.3 基本块的收尾处理

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

4.4 管理寄存器和地址描述符

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

对于指令“$LD\;\;R, x$”
- 修改$R$的寄存器描述符，使之只包含$x$
- 修改$x$的地址描述符，把$R$作为新增位置加入到$x$的位置集合中
- 从任何不同于$x$的地址描述符中删除$R$
对于指令“$OP\;\;R_x, R_y, R_z$”
- 修改$R_x$的寄存器描述符，使之只包含$x$
- 从任何不同于$R_x$的寄存器描述符中删除$x$
- 修改$x$的地址描述符，使之只包含位置$R_x$
- 从任何不同于$x$的地址描述符中删除$R_x$
对于指令“$ST\;\;x, R$”
- 修改$x$的地址描述符，使之包含自己的内存位置
对于复制语句$x=y$，如果需要生成加载指令“$LD\;\;R_y, y^{\prime}$”则
- 修改$R_y$的寄存器描述符，使之只包含$y$
- 修改$y$的地址描述符，把$R_y$作为新增位置加入到$y$的位置集合中
- 从任何不同于$y$的变量的地址描述符中删除$R_y$
- 修改$R_y$的寄存器描述符，使之也包含$x$
- 修改$x$的地址描述符，使之只包含$R_y$

5 寄存器选择函数$getReg$的设计

5.1 寄存器$R_x$的选择

选择方法与$R_y$类似，区别之处在于

因为$x$的一个新值正在被计算，因此只存放了$x$的值的寄存器对$R_x$来说总是可接受的，即使$x$就是$y$或$z$之一（因为我们的机器指令允许一个指令中的两个寄存器相同）
如果$y$在指令$I$之后不再使用，且（在必要时加载$y$之后）$R_y$仅仅保存了$y$的值，那么，$R_y$同时也可以用作$R_x$ 。对$z$和$R_z$也有类似选择
当$I$是复制指令$x=y$时，选择好$R_y$后，令$R_x=R_y$

6 参考

7 窥孔优化

窥孔(peephole)是程序上的一个小的滑动窗口

窥孔优化是指在优化的时候，检查目标指令的一个滑动窗口(即窥孔) ，并且只要有可能就在窥孔内用更快或更短的指令来替换窗口中的指令序列

也可以在中间代码生成之后直接应用窥孔优化来提高中间表示形式的质量

7.1 具有窥孔优化特点的程序变换的例子

7.1.1 冗余指令删除

消除冗余的加载和保存指令
消除不可达代码：一个紧跟在无条件跳转之后的不带标号的指令可以被删除

7.1.2 控制流优化

在代码中出现跳转到跳转指令的指令时，某些条件下可以使用一个跳转指令来代替

7.1.3 代数优化

代数恒等式

消除窥孔中类似于$x=x+0$或$x=x*1$的运算指令

强度削弱

对于乘数（除数）是2的幂的定点数乘法（除法），用移位运算实现代价比较低
除数为常量的浮点数除法可以通过乘数为该常量倒数的乘法来求近似值

7.1.4 特殊指令的使用

充分利用目标系统的某些高效的特殊指令来提高代码效率

例如：INC指令可以用来替代加1的操作
《MOOC-编译原理-陈鄞》

Liuye Notebook

编译原理-代码生成