8.2 目标语言

使用三地址机器的模型：

• 加载：LD dst, addr
• 保存：ST x, r
• 计算：OP dst, src1, src2
• 无条件跳转：BR L
• 条件跳转：Bcond r L

寻址模式：

• 变量$x$
• $a(r)$：$a$地址加偏移量$r$
• $constant(r)$
• $*r$：$r$对应的地址上的内容
• $*constant(r)$
• $#constant$：常量

8.3 目标代码中的地址

8.3.1 静态分配

每个过程静态地分配一个数据区域，其开始位置用staticArea表示。

• call callee的实现：
  • ST callee.staticArea, #here + 20 存放返回地址
  • BR callee.codeArea
• return语句的实现
  • BR *callee.staticArea

问题：不能实现递归调用。

8.3.2 栈分配

• 寄存器SP指向栈顶
• 第一个过程（main）初始化栈区
• 过程调用指令序列：
  • ADD SP, SP, #caller.recordSize 增大栈顶指针
  • ST 0(SP), #here + 16 保存返回地址
  • BR callee.codeArea
• 返回指令序列
  • BR *0(SP)
  • SUB SP, SP, #caller.recordSize 减小栈顶指针

8.3.3 名字的运行时刻地址

在三地址语句中使用名字（指向符号表条目）来引用变量。

如语句x = 0：

• 静态区域 LD xxx, #0
• 栈区 LD xx(SP), #0

8.4 基本块和流图

中间代码的流图表示法：

• 中间代码划分成为基本块（basic block）
  • 控制流只能从基本块的第一条指令进入
  • 除基本块的最后一条指令外，控制流不会跳转/停机
• 流图的结点是基本块，流图的边指明了哪些基本块可以跟在一个基本块之后运行

8.4.1 基本块

划分基本块的算法：

• 确定首指令leader（基本块的第一个指令）
  • 第一个三地址指令
  • 任意一个转移指令的目标指令
  • 任意一个转移指令之后的指令
• 确定基本块：从首指令到下一个首指令构成一个基本块

8.4.2 后续使用信息

变量值的使用：

• 三地址语句$i$向变量$x$赋值，如果另一个语句$j$的运算分量为$x$，且从$i$开始有一条路径到达$j$，路径上没有对$x$赋值，那么$j$就使用了$i$处计算得到的$x$的值。
• 我们说变量$x$在语句$i$后的程序点上活跃（指值被使用）

如果$x$在$i$处不活跃，且$x$占用了一个寄存器，则可以把这个寄存器用于其他目的。

算法：确定基本块中的活跃性、后续使用

• 从基本块$B$的最后一个语句开始反向扫描
• 刚开始时$B$中的所有非临时变量都是活跃的
• 对于每个语句$i: x = y + z$
  • 令语句$i$和$x$、$y$、$z$的当前活跃性信息/使用信息关联
  • 设置$x$为“不活跃”和“无后续使用”
  • 设置$y$、$z$为“活跃”，并指明它们的下一次使用为语句$i$

8.4.3 流图

流图的结点是基本块：两个结点$B$和$C$之间有一条有向边当且仅当基本块$C$的第一个指令可能在$B$的最后一个指令之后执行。

入口/出口结点：不和任何中间指令对应，入口到第一条指令有一条边，任何可能最后执行的基本块到出口有一条边。

8.4.5 循环

循环的定义：

• 循环$L$是一个结点集合
• 存在一个循环入口（loop entry）结点，是唯一的、前驱可以在循环$L$之外的结点，到达其余结点的路径必然先经过这个入口结点
• 其余结点都存在到达入口结点的非空路径，且路径都在$L$中

8.5 基本块的优化

8.5.1 基本块的DAG表示

DAG图可以反映变量及其值对其他变量的依赖关系：

• 每个变量都有一个对应的DAG结点表示其初始值
• 每个语句$s$都有一个相关的结点$N$，代表此计算得到的值

构造DAG图的方法：顺序扫描各三地址指令，进行如下处理：

• 指令x = y op z
  • 为该指令建立结点$N$，标号为op，令$x$和$N$关联
  • $N$的子结点为$y$、$z$当前关联的结点
• 指令x = y
  • 假设$y$关联到$N$，那么$x$现在也关联到$N$

DAG图的作用：

• 寻找局部公共子表达式
• 消除死代码
• 代数恒等式的使用
• 数组引用的表示
• 指针赋值和过程调用

8.5.2 局部公共子表达式

建立某个结点$M$之前，检查是否存在一个结点$N$，它和$M$具有相同的运算符和子结点（顺序也相同）。

如果存在，则不需要生成新的结点，用$N$代表$M$。

8.5.3 消除死代码

在DAG图上消除没有附加活跃变量的根节点，即消除死代码。

8.5.4 代数恒等式

• 消除计算步骤
• 降低计算强度
• 常量合并

8.5.5 数组引用

• 从数组取值的运算x = a[i]对应于=[]的结点
  • 左右子结点是数组初始值$a_0$和下标$i$
  • 变量$x$是这个结点的标号之一
• 对数组赋值的运算a[j] = y对应于[]=的结点
  • 这个结点的三个子结点分别代表$a_0$、$j$和$y$
  • 杀死所有依赖于$a_0$的变量

8.5.6 指针赋值和过程调用

• 通过指针进行取值/赋值：x = *p、*q = y
  • $x$使用了任意变量，因此无法消除死代码
  • *q = y对任意变量赋值，因此杀死了全部其他结点
• 可通过全部/局部指针分析部分地解决这个问题

过程调用也蕾丝，必须安全地假设它

• 使用了可访问范围内的所有变量
• 修改了可访问范围内的所有变量

8.5.7 从DAG到基本块的重组

重构的方法：

• 每个结点构造一个三地址语句，计算对应的值
• 结果应该尽量赋给一个活跃的变量
• 如果结点有多个关联的变量，则需要用复制语句进行赋值

重组的规则：如果两个指令之间相互影响，他们的顺序就不该改变。

8.6 代码生成器

• 根据三地址指令序列生成机器指令
  • 假设每个三地址指令只有一个对应的机器指令
  • 有一组寄存器用于计算基本块内部的值
• 主要的目标是减少加载和保存指令，即最大限度地利用寄存器
• 寄存器的使用方法
  • 执行运算时，运算分量必须放在寄存器中
  • 存放临时变量
  • 存放全局的值
  • 进行运行时刻管理（如SP指针）

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

• 为一个三地址指令生成机器指令时：
  • 只有当运算分量不在寄存器中时，才从内存载入
  • 尽量保证只有当寄存器中的值不被使用时，才覆盖掉
• 数据结构：
  • 寄存器描述符：跟踪各个寄存器都存放了哪些变量的当前值
  • 地址描述符：各个变量的当前值存放在哪些位置（包括内存位置和寄存器）上

重要子函数$getReg(I)$：

• 根据寄存器描述符和地址描述符等信息，为三地址代码指令$I$选择最佳的寄存器
• 得到的机器指令的质量依赖于$getReg$函数选取寄存器的算法
• 代码生成算法逐个处理三地址指令

运算语句x = y + z：

• $getReg$为$x$、$y$、$z$选择寄存器$R_x$、$R_y$、$R_z$
• 检查$R_y$的寄存器描述符，如果$y$不在$R_y$中则生成指令LD Ry, y'，$y'$表示存放$y$值的当前位置
• 类似的确定是否生成LD Rz, z'
• 生成指令ADD Rx, Ry, Rz

赋值语句x = y：

• $getReg$为$x$、$y$选择相同的寄存器
• 如果$y$不在$R_y$中，生成指令LD Ry, y

基本块的收尾：如果变量$x$活跃且不在内存中，则生成指令ST x, Rx。

代码生成的同时更新寄存器和地址描述符：

• 处理指令时生成的LD R, x
  • $R$的寄存器描述符：只包含$x$
  • $x$的地址描述符：$R$作为新位置加入到$x$的位置集合中
  • 任何不同于$x$的变量的地址描述符中删除$R$
• 生成的ST x, R
  • $x$的地址描述符：包含自己的内存位置（新增）
• ADD Rx, Ry, Rz
  • $R_x$的寄存器描述符：只包含$x$
  • $x$的地址描述符：只包含$R_x$（不包含内存地址）
  • 从任何不同于$x$的变量的地址描述符中删除$R_x$
• x = y
  • 如果生成加载指令，同第一个规则处理
  • 把$x$加入到$R_y$的寄存器描述符中
  • $x$的地址描述符：只包含$R_y$（不包含内存地址）

$getReg$函数：

• x = y op z的运算分量$y$和$z$：
  • 如果$y$已经在某个寄存器中，不需要进行处理，直接选择这个寄存器；
  • 如果$y$不在寄存器中，且有空闲寄存器，选择一个空寄存器作为$R_y$；
  • 如果不在寄存器中也没有空闲寄存器：寻找一个寄存器$R$，其寄存器描述符表示$v$在$R$中
    • 如果$v$的地址描述符表明还可以在别的地方找到它，则选它；
    • $v$即为$x$（运算结果）且$x$不是运算分量$z$，则选它；
    • 如果$v$在此之后不会被使用（不活跃），则选它；
    • 最差情况下，生成保存指令并修改$v$的地址描述符。如果$R$中存放了多个变量的值则需要生成多个保存指令。
• x = y op z的结果$x$：
  • 和选择$y$类似，但是可以选择只存放$x$值的寄存器；
  • 如果$y$在指令之后不再使用，且$R_y$仅仅保存了$y$的值，那么$R_y / R_z$也可以作为$R_x$。
• x = y：先选择$R_y$，然后让$R_x = R_y$。

8.7 窥孔优化

使用一个滑动窗口（窥孔）来检查目标指令，在窥孔内实现优化：

• 冗余指令消除
• 控制流优化
• 代数化简/强度消减
• 机器特有指令的使用

8.7.1 消除冗余的加载和保存指令

LD R0, a
ST a, R0

• 没有进行任何修改又保存回去
• 且保存代码不是跳转目标

8.7.2 消除不可达代码

if debug == 1 goto L1
goto L2

• 可以将条件取反并交换目标代码顺序；
• 如果已知debug是常量，那么可以将条件跳转替换为跳转语句

8.7.3 控制流优化：

if ... goto L1
L1: goto L2

连续的跳转可以优化，如上面的代码中goto L1可以直接变成goto L2

8.7.4 代数化简和强度消减

• 优化x = x + 0
• 优化x = x * 1
• 用x * x替换$x^2$等

8.7.5 使用机器特有的指令

• 如使用INC、DEC等指令

8.8 寄存器分配和指派

• 寄存器分配：确定在程序的每个点上，哪个值应该存放在寄存器中
• 寄存器指派：各个值应该存放在哪个寄存器中

8.8.1 全局寄存器分配

在循环中频繁使用的值放在固定寄存器，如分配固定多个寄存器来存放内部循环中最活跃的值。

可以通过使用计数的方法来估算把一个变量放到寄存器中会带来多大好处，然后根据这个估算来分配寄存器。

8.8.2 通过覆盖一个输入树来生成代码

指令选择：

• 为中间代码中出现的运算符选择适当的机器指令
• 用树来表示中间代码，按照特定的规则不断覆盖这颗树并生成机器指令

目标指令选择：

• 通过应用一个树重写规则来生成
• 重写规则形式 $$replacement \leftarrow template \ \lbrace action \rbrace$$
• 将模板替换为替换结点，并生成对应的机器代码

如何完成树匹配？

• 把树重写规则替换成相应的上下文无关文法的产生式
• 产生式的右部是其指令模板的前缀表示
• 如果在某个时刻有多个模板可以匹配，匹配到大树优先