目标代码中的地址

代码生成器

根据三地址指令序列生成机器指令，假设每个三地址指令只有一个对应的机器指令，有一组寄存器用于计算基本块内部的值。

主要的目标是减少加载（LD）和保存（ST）指令，即最大限度地利用寄存器。

寄存器的使用方法：

• 执行运算时，运算分量必须放在寄存器中

• 存放临时变量

• 存放全局的值

• 进行运行时管理（比如栈顶指针）

算法的基本思想和数据结构

依次考虑各三地址指令，尽可能地把值保留在寄存器中，以减少寄存器/内存之间的数据交换。为一个三地址指令生成机器指令时：

• 只有当运算分量不在寄存器中时，才从内存载入

• 尽量保证只有当寄存器中值不被使用（称之为不活跃）时，才覆盖掉。

数据结构（编译期）

• 寄存器描述符：跟踪各个寄存器都存放了哪些变量的当前值R1→{x}, R2→{a,b}

• 地址描述符：各个变量的当前值存放在哪些位置（包括内存位置和寄存器）上x→{R1}, a→{a, R2}

代码生成算法

重要子函数：getReg(I)

• 根据寄存器描述符和地址描述符等数据流信息，为三地址指令I选择最佳的寄存器

• 得到的机器指令的质量依赖于getReg函数选取寄存器的算法

代码生成算法逐个地处理三地址指令。

处理指令生成时的LD R,x

R的寄存器描述符只包含x，x地址描述符（R作为新位置加入到x的位置集合中），从任何不同于x的变量的地址描述符中删除R。（让R中只有x，没有其他无关的东西干扰计算）

运算语句x=y+z

1. getReg(x=y+z) 为x，y，z选择寄存器Rx，Ry，Rz

2. 检查Ry的寄存器描述符，如果y不在Ry中则生成指令LD Ry,y ，类似地确定是否生成LD Rz,z

3. 生成指令ADD Rx,Ry,Rz

Rx的寄存器描述符只包含x，x的地址描述符只包含Rx（不包含x的内存位置），从任何不同于x的变量的地址描述符中删除Rx。（保证x和Rx是绝对一对一，保护计算结果）。

赋值语句x=y

1. getReg(x=y) 为x和y选择相同寄存器（运行后值相同）把x加入到Ry的寄存器描述符中（即Ry同时存放了x和y的当前值）。

2. 如果y不在Ry中，则生成指令LD Ry,y

x的地址描述符只包含Ry，不包含x的内存位置。

基本块的收尾

如果变量x活跃，且不在内存中，则生成指令ST x,Rx 。给x的地址描述符新增包含自己的内存位置。

getReg函数

目标是减少LD/ST指令，任务是为运算分量和结果分配寄存器。

对于x=y op z ：

• 如果y已经在某个寄存器中，不需要进行处理，选择这个寄存器作为Ry

• 如果y不在寄存器中，且有空闲寄存器，选择一个空闲寄存器作为Ry

• 如果y不在寄存器中，且没有空闲寄存器，则需要选择一个非空闲寄存器存放值。若选择寄存器R，且已知其寄存器描述符表示某变量v的值在R中，则

  • 如果v的地址描述符表明可以在别的地方找到v，覆盖

  • v就是x（即结果），且x不是运算分量z，覆盖

  • 如果v在此之后不会再被使用（不活跃），覆盖

  • 生成保存指令ST v,R （溢出操作）并修改v的地址描述符；如果R中存放了多个变量的值，那么需要生成多条ST指令。

为结果x选择寄存器Rx的方法基本上和把y从内存LD时一样，但是：

• 只存放x值的寄存器总是可接受的

• 如果y在指令之后不再使用，且Ry仅仅保存了y的值，那么Ry同时也可以作为Rx（对z也一样）。

处理x=y时，先选择Ry，然后让Rx=Ry。

判断一个变量是否活跃

变量值的使用：三地址语句i向变量x赋值，如果另一个语句 j 的运算分量为 x，且从 i 开始有一条路径到 达 j，且路径上没有对 x 赋值，那么 j 就使用了 i 处计算得到的 x 的值

x在语句后的程序点上活跃的定义：程序执行完语句i时，x中存放的值将被后面的语句使用；不活跃是指变量的值不会被使用，而不是变量不会被使用。这些信息可以用于代码生成。