Lec9: 指令选择

第 9 章关注什么？#

第 8 章已经做完两件事：

1. 把 IR 树变成规范树。
2. 重新排列规范树，使每个 CJUMP 后面紧跟假分支标签。

第 9 章接着做：

指令选择：从规范树生成伪汇编 / 抽象汇编代码。

整体位置：

1
中间表示
2
        |
3
        | 第 8 章
4
        v
5
规范化后的中间表示
6
        |
7
        | 第 9 章：指令选择
8
        v
9
抽象汇编代码
10
        |
11
        | 第 10/11 章：寄存器分配
12
        v
13
汇编代码

后端从 IR 到机器码主要分三步：

第 1 部分：为什么需要指令选择？#

1.1 为什么 IR 不能直接当机器指令？#

IR 树语言中，每个树节点通常只表达一个原始操作：

• 取内存
• 存内存
• 加法
• 减法
• 条件跳转

但真实机器指令经常可以一次完成多个原始操作。

典型例子是：

1
LOAD ri <- M[rj + c]

这条机器指令同时做了：

1. 取寄存器 rj。
2. 加上常量偏移 c。
3. 用得到的地址访问内存。
4. 把内存中的值放入 ri。

对应到 IR 树，大概是：

1
          MEM
2
           |
3
           +
4
         /   \
5
      TEMP   CONST
6
       rj      c

所以指令选择要解决的问题就是：

找到合适的机器指令来实现给定的 IR 树。

1.2 用模式匹配做指令选择#

两类 IR 对应不同的匹配方法：

本章讨论的是树形 IR，所以核心工具是：

树模式 + 瓦片覆盖（tiling）

第 2 部分：树模式与瓦片覆盖#

2.1 树模式#

定义：

每条机器指令都可以表示成一片 IR 树，这片树称为 树模式。

也就是说，一条机器指令可以看成一片 IR 树。

例如 LOAD ri <- M[rj + c] 的模式可以画成：

1
指令：
2
    LOAD ri <- M[rj + c]
3

4
树模式：
5

6
          MEM
7
           |
8
           +
9
         /   \
10
        r   CONST
11
             c

这里的 r 表示某个寄存器值，CONST c 表示常量偏移。

2.2 瓦片覆盖#

定义：

瓦片覆盖：用不重叠的树模式覆盖整棵树。

也就是用一块块树模式覆盖整棵 IR 树：

• 每块 tile（瓦片）对应一条合法机器指令。
• tile 之间不能重叠。
• 整棵 IR 树要被覆盖。
• tile 的叶子处可以留下子树，继续递归处理。

可以把它理解成：

1
IR 树节点          = 原始操作
2
树模式 / tile      = 一条机器指令能实现的一片 IR
3
瓦片覆盖           = 把整棵 IR 树切成若干机器指令

2.3 Jouette 体系结构#

为了说明指令选择，本章使用教材中的假想机器 Jouette。

需要强调几点：

• BINOP(PLUS, x, y) 可以简写成 +(x, y)。
• r0 = 0。
• CONST 和 TEMP 节点的实际值有时不会画出来。
• r0 永远包含 0。
• 有些机器指令对应不止一个树模式。

例如，常量 c 可以通过 r0 得到：

1
ADDI ri <- r0 + c

对应的树模式可以看成：

1
CONST c

因为 r0 固定为 0，所以 r0 + c 就是 c。

第 3 部分：树模式例子：a[i] := x#

用 a[i] := x 展示同一棵 IR 树可以有多种瓦片覆盖方式。

原始树形大致如下：

1
                         MOVE
2
                       /      \
3
                    MEM        MEM
4
                     |          |
5
                     +          +
6
                   /   \      /   \
7
                MEM     *    FP   CONST x
8
                 |     / \
9
                 +  TEMP i CONST 4
10
               /   \
11
             FP   CONST a

这棵树表示：

• 左边 MEM(...) 是赋值目标 a[i] 的地址。
• 右边 MEM(FP + x) 是变量 x 的值。
• MEM(FP + a) 取出数组 a 的基地址。
• TEMP i * CONST 4 计算下标偏移。
• + 把数组基地址和偏移加起来，得到 a[i] 的地址。

3.1 小 Tile#

要点：

总是可以用很小的 tile 覆盖整棵树，让每个 tile 只覆盖一个节点。

也就是说，最保守的做法是每个 tile 只覆盖一个节点。这样一定能翻译，但指令会比较多。

对 a[i] := x，小 tile 风格的指令序列是：

1
ADDI  r1 <- r0 + a
2
ADD   r1 <- fp + r1
3
LOAD  r1 <- M[r1 + 0]
4
ADDI  r2 <- r0 + 4
5
MUL   r2 <- ri * r2
6
ADD   r1 <- r1 + r2
7
ADDI  r2 <- r0 + x
8
ADD   r2 <- fp + r2
9
LOAD  r2 <- M[r2 + 0]
10
STORE M[r1 + 0] <- r2

这里可以看到：小 tile 会把地址计算、常量构造、取内存、存内存都拆得很细。

3.2 两种不同覆盖方式#

还可以比较 a[i] := x 的两种覆盖方式：

1
普通覆盖：6 个单位
2
使用 MOVEM 的覆盖：5 + m 个单位

其中：

• 普通指令代价都是 1。
• MOVEM 的代价是 m。

这说明：大 tile 不一定永远更好，关键要看代价。

第 4 部分：局部最优与全局最优覆盖#

一棵 IR 树可以有多种覆盖方式。所谓最佳覆盖，就是代价最低的指令序列。

在单发射、固定延迟机器上，最低代价通常就是：

指令条数最少

4.1 Optimum Tiling#

定义：

Optimum tiling（全局最优覆盖）：所有 tile 的总代价达到全局最低。

也就是：

1
全局总代价最小

4.2 Optimal Tiling#

定义：

Optimal tiling（局部最优覆盖）：不存在两个相邻 tile 能合并成一个代价更低的 tile。

也就是：

1
局部不能再改进

具体说，如果有两个相邻 tile：

1
       tile A
2
         |
3
       tile B

并且它们能合并成一个更便宜的大 tile：

1
       tile C

那原来的覆盖方式就不是局部最优。

4.3 两者关系#

结论：

每个全局最优覆盖都是局部最优覆盖，但反过来不一定成立。

也就是说：

• 全局最优一定局部最优。
• 局部最优不一定全局最优。

原因很直观：如果一个覆盖方式已经是全局代价最低，那它不可能存在“两个相邻 tile 合并后更便宜”的局部改进；否则总代价还能下降，和“全局最低”矛盾。

反过来不成立，因为没有局部改进，不代表所有全局组合都已经最好。

4.4 模式表的要求#

注意：

如果某个树模式总能拆成若干个总代价更低的小 tile，那么就应该把这个树模式从模式表中删掉。

也就是说，模式表里不该保留“永远比拆开更贵”的 tile。

第 5 部分：Maximal Munch#

5.1 基本思想#

maximal munch 的定位：

Maximal Munch：用于寻找局部最优覆盖的算法。

它假设：

1
越大的 tile 越好

算法思想是贪心：

1. 从根节点开始。
2. 找到能覆盖当前根节点的最大 tile。
3. 用这个 tile 覆盖根节点附近的节点。
4. tile 叶子处留下若干子树。
5. 对这些子树重复同样过程。

“tile 的叶子接子树”的结构可以画成：

1
            当前根节点
2
                 |
3
              [ tile ]
4
              /      \
5
          叶子1      叶子2
6
            |          |
7
          子树1      子树2

其中 [ tile ] 是当前已经选中的机器指令模式；子树1、子树2 是还没覆盖的部分。

5.2 什么叫最大 tile？#

要点：

最大 tile：节点数最多的 tile。

例如：

1
单节点 tile：
2

3
    TEMP
4

5
双节点 tile：
6

7
    MEM
8
     |
9
     r
10

11
三节点 tile：
12

13
      +
14
    /   \
15
   r   CONST

maximal munch 会优先选择能匹配的最大 tile。

如果两个 tile 大小相同，而且都能匹配根节点：

可以任意选择其中一个。

也就是任选一个。

5.3 用 a[i] := x 看自顶向下#

对这棵树：

1
                         MOVE
2
                       /      \
3
                    MEM        MEM
4
                     |          |
5
                     +          +
6
                   /   \      /   \
7
                MEM     *    FP   CONST x
8
                 |     / \
9
                 +  TEMP i CONST 4
10
               /   \
11
             FP   CONST a

maximal munch 的“选择方向”是自顶向下：

1. 先看根节点 MOVE。
2. 找到能匹配 MOVE 的最大存储 / 移动类 tile。
3. 这个 tile 的叶子位置可能留下目标地址子树和右值子树。
4. 再分别处理这些子树。

注意：这里说的是“选择 tile 的方向”。实际输出指令时，子树结果通常要先算出来。

要点：

指令会按反向顺序生成。

一个简单例子：

1
IR 树：
2

3
        *
4
      /   \
5
     +    MEM
6
    / \    |
7
   a  3    p

表示：

1
(a + 3) * M[p]

maximal munch 选择 tile 时先看到根部 *，但真正输出指令要先产生 * 的两个操作数：

1
ADDI t1 <- a + 3     ; 先处理左边叶子子树
2
LOAD t2 <- M[p]      ; 再处理右边叶子子树
3
MUL  t3 <- t1 * t2   ; 最后输出根部 tile 对应的指令

所以它是：

1
选择 tile：先根节点
2
输出指令：先子节点，最后父节点

5.4 Maximal Munch 的实现思想#

只需要掌握这几点：

• 有两个递归函数：
  • munchStm 处理语句。
  • munchExp 处理表达式。
• 每个分支匹配一个 tile。
• 分支按 tile 优先级排列，也就是大 tile 放前面。

所以 maximal munch 的“贪心”在实现上体现为：

1
先尝试大模式
2
匹配不到再尝试小模式

第 6 部分：用动态规划寻找全局最优覆盖#

6.1 为什么 maximal munch 不够？#

要点：

Maximal munch 总能找到局部最优覆盖，但不一定能找到全局最优覆盖。

原因：

• maximal munch 是自顶向下的。
• 它每次在当前根节点处做局部选择。
• 它不知道这个选择会让下面的子树变便宜还是变贵。

如果要找 全局最优覆盖，需要动态规划。

6.2 DP 的核心定义#

定义：

节点 x 的代价记为 f(x)，表示覆盖以 x 为根的子树所需的最小代价。

也就是说：

1
f(x) = 覆盖以 x 为根的整棵子树的最小代价

递推式：

其中：

• t：一个能覆盖当前节点 x 的 tile。
• c_t：tile t 自身的代价。
• leaves(t)：tile 叶子处接上的子树根节点。
• f(i)：这些叶子子树的最优覆盖代价。

6.3 DP 的工作顺序#

给定根节点 n：

1. 先递归求出 n 的子节点、孙节点等所有子树的代价。
2. 然后在 n 处尝试每一种能匹配的树模式。
3. 对每个 tile 计算：

1
tile 自身代价 + 所有叶子子树的 f 值

4. 选择总代价最小的 tile。

所以 DP 是：

1
自底向上

6.4 DP 例子：MEM(+(CONST 1, CONST 2))#

例子是这棵树：

1
          MEM
2
           |
3
           +
4
         /   \
5
   CONST 1   CONST 2

记号：

1
(a, b)

其中：

• a 是最小代价。
• b 是对应的模式编号。

1
CONST 1      CONST 2
2
 (1,8)        (1,8)

1
f(CONST 1) = 1
2
f(CONST 2) = 1

1
             +
2
           /   \
3
     CONST 1   CONST 2
4
      (1,8)     (1,8)

1
             +  (2,6)
2
           /   \
3
     CONST 1   CONST 2
4
      (1,8)     (1,8)

1
          MEM
2
           |
3
          +  (2,6)
4
        /   \
5
  CONST 1   CONST 2
6
   (1,8)     (1,8)

1
          MEM  (2,10)
2
           |
3
          +  (2,6)
4
        /   \
5
  CONST 1   CONST 2
6
   (1,8)     (1,8)

6.5 DP 的指令输出阶段#

一旦根节点的代价找到了，就开始输出指令：

1
输出指令(节点 n):
2
    对节点 n 选中的 tile 的每个叶子 li:
3
        输出指令(li)
4
    输出节点 n 匹配到的指令

对上面的例子，输出是：

1
ADDI r1 <- r0 + 1
2
LOAD r1 <- M[r1 + 2]

对应理解：

• 根节点选择的是 MEM(+(e1, CONST)) 这种读取模式。
• 这个 tile 把 MEM、+、CONST 2 一起覆盖了。
• 它留下的叶子是 CONST 1。
• 所以先发 CONST 1 的指令，再发根部读取指令。

第 7 部分：快速匹配与复杂度#

7.1 快速匹配#

maximal munch 和 DP 都需要检查“哪些 tile 能匹配当前节点”。

tile 能匹配的条件：

tile 中每个非叶节点的标签，都要和 IR 树中对应节点的算子一样。

例如：

1
tile：
2
      MEM
3
       |
4
       +
5
     /   \
6
    r   CONST
7

8
IR 树：
9
      MEM
10
       |
11
       +
12
     /   \
13
   TEMP CONST

这个 tile 可以匹配，因为非叶节点 MEM 和 + 都对上了。

为了快一点，可以按根节点标签分类：

1
如果当前节点是 MEM，只检查以 MEM 为根的模式。
2
如果当前节点是 BINOP，只检查以 BINOP 为根的模式。
3
如果当前节点是 CONST，只检查以 CONST 为根的模式。

目标：

尽量避免反复检查同一个 IR 树节点。

7.2 复杂度中的变量#

定义：

结论：

1
Maximal munch：       正比于 (K' + T') N / K
2
动态规划：             正比于 (K' + T') N

7.3 为什么 maximal munch 是 (K' + T') N / K？#

可以拆成两部分看。

第一，每次 maximal munch 在某个根节点上选 tile，需要做两类工作：

1
检查树节点以判断是否匹配     -> 最多 K'
2
在可匹配模式中做选择         -> 平均 T'

所以一次选择的成本近似是：

1
K' + T'

第二，maximal munch 每选中一个 tile，平均会覆盖 K 个带标签的非叶节点。

整棵树有 N 个节点，所以大约需要选择：

1
N / K

个 tile。

合起来就是：

1
每次选择成本 × 选择次数
2
= (K' + T') × (N / K)
3
= (K' + T') N / K

如果 K、K'、T' 都看成常数，那么：

1
(K' + T') N / K = 常数 × N

所以是线性时间。

7.4 为什么 DP 是 (K' + T') N？#

DP 要给每个树节点都计算一个代价。

对每个节点，仍然要检查：

1
K' + T'

量级的匹配工作。

一共有 N 个节点，所以总成本是：

1
(K' + T') × N

如果 K'、T' 是常数，DP 也是线性时间。

和 maximal munch 相比，DP 这里没有除以 K，因为 DP 不是“每选一个 tile 跳过一片节点”，而是要给每个节点都算一次最优代价。

第 8 部分：树文法#

8.1 为什么需要树文法？#

对于复杂指令集、多个寄存器类别和多种寻址模式：

• 树模式更多。
• 树模式更复杂。
• 手写 tiling 算法会很繁琐，也更容易出错。

因此可以使用指令选择器生成器：

1. 在单独的规格说明中定义树模式。
2. 用通用的树模式匹配算法计算 tiling。

解决方式：

用树文法描述树模式，把指令选择转化成解析问题，并使用推广后的动态规划算法求解。

8.2 简化版 Jouette#

简化版 Jouette 把寄存器分成两类：

要点：

每个 tile 的根和叶子都必须标记为 a 或 d。

也就是说，一个 tile 不只要说明树形结构，还要说明：

1
这个表达式算出来以后放在地址寄存器还是数据寄存器？

8.3 树文法的非终结符#

对应的非终结符：

LOAD、MOVEA、MOVED 的规则可以写成：

1
d -> MEM(+(a, CONST))
2
d -> MEM(+(CONST, a))
3
d -> MEM(CONST)
4
d -> MEM(a)
5
d -> a
6
a -> d

8.4 树文法的歧义#

要点：

这样的文法高度歧义。

同一个表达式可能有许多条不同的指令序列实现它。

因此第 3 章的普通解析技术不太有用。更合适的是 DP 的推广：

对每个节点，记录它作为每个非终结符时的最小代价匹配。

例如：

1
节点 x：
2
    作为 a 寄存器表达式的最小代价
3
    作为 d 寄存器表达式的最小代价

用表格表示：

这样就能处理寄存器类别。

第 9 部分：CISC 机器#

9.1 RISC 与 CISC#

RISC 和 CISC 的对照表：

9.2 寄存器较少#

问题：

1
CISC 寄存器较少。

解决办法：

自由生成 TEMP 节点，并假设寄存器分配器会处理好。

也就是指令选择阶段先自由地产生临时值，寄存器数量问题留给寄存器分配。

9.3 寄存器类别#

例子：Pentium 乘法指令。

• 左操作数必须放在 eax
• 结果的高位放进 edx
• Tiger 程序不需要这些高位

解决办法：

显式移动操作数和结果。

例子：

1
目标: t1 <- t2 * t3
2

3
mov eax, t2       eax <- t2
4
mul t3            eax <- eax * t3; edx <- 无用值
5
mov t1, eax       t1 <- eax

重点：如果某条指令会额外写坏某些寄存器，要让后续寄存器分配器知道。

9.4 二地址指令#

问题：

目标寄存器必须和第一个源寄存器相同。

例如想实现：

1
t1 <- t2 + t3

在二地址机器上可以生成：

1
mov t1, t2     t1 <- t2
2
add t1, t3     t1 <- t1 + t3

之后希望寄存器分配器能把 t1 和 t2 分配到同一个寄存器，这样 mov 可以被删除。

9.5 算术运算可以访问内存#

CISC 算术指令可以直接访问内存。下面是两段等价代码：

1
mov eax, [ebp - 8]
2
add eax, ecx
3
mov [ebp - 8], eax

和：

1
add [ebp - 8], ecx

右边更简洁，但这两段代码速度差不多。

左边的明显缺点是：

1
它会破坏 eax。

解决办法：

运算前先把所有操作数取到寄存器中，运算后再把结果存回内存。

9.6 多种寻址模式#

一个完成六件事的寻址模式通常也要六步执行。

复杂寻址模式的两个优势：

• 破坏更少寄存器
• 指令编码更短

结论：

• 通过树匹配式指令选择，可以选择 CISC 的复杂寻址模式。
• 但使用简单的 RISC 风格指令，程序也可能一样快。

9.7 变长指令#

要点：

这对编译器来说并不是真正的问题。

一旦指令选好了，具体编码交给汇编器做。

9.8 带副作用的指令#

例子：自增式内存读取。

1
r2 <- M[r1]
2
r1 <- r1 + 4

问题：

1
一条指令产生两个结果

这很难用树模式表示。

三个解决办法：

1. 忽略自动递增指令，不使用它们。
2. 用临时特判的方式匹配特殊代码习惯。
3. 使用 DAG 模式，而不是树模式。

9.9 RISC 和 CISC 对算法选择的影响#

总结：

• 求 optimal tiling 的算法比求 optimum tiling 的算法更简单。
• 对 CISC 来说，optimum 和 optimal 的差异比较明显。
• 对 RISC 来说，optimum 和 optimal 通常几乎没有差异。
• 因此，对 RISC 来说，较简单的 tiling 算法就足够了。

原因：

1
CISC：某些指令每条能完成多个操作。
2
RISC：tile 小，而且代价比较统一。

第 10 部分：Tiger 的指令选择#

这一部分的重点不是具体写代码，而是说明指令选择和寄存器分配如何衔接。

10.1 为什么寄存器分配放在指令选择后？#

问题：

在一棵由指令模式覆盖的树中，每个 tile 的根都会对应一个保存在寄存器中的中间结果。那么该使用哪个寄存器？

回答：

寄存器分配的任务，就是给这些节点分配真实寄存器编号。

如果在指令选择之前做寄存器分配，会有问题：

1
还不知道哪些树节点需要寄存器保存结果

所以：

1
寄存器分配放在指令选择之后。

10.2 抽象汇编指令#

AS_instr 是：

尚未分配真实寄存器的汇编指令。

它有三类：

10.3 OPER 需要记录什么？#

OPER 保存：

如果一个操作总是顺序执行到下一条指令：

1
jumps = NULL

10.4 LABEL 和 MOVE#

LABEL：

• 是跳转可以到达的点。
• assem 说明标签在汇编中长什么样。
• label 是实际使用的标签符号。

MOVE：

• 类似 OPER。
• 但必须只做数据搬运。

MOVE 单独列出来，是因为后续寄存器分配器有机会处理 move 指令。

10.5 机器无关性#

重点：

AS_instr 类型独立于具体选择的目标机器汇编语言。

抽象汇编中还没有真实寄存器。

例如抽象形式：

1
LOAD `d0 <- M[`s0 + 8]

这里：

• `s0 表示第一个源 temp。
• `d0 表示第一个目标 temp。

寄存器分配之后，可能打印成：

1
LOAD r1 <- M[r27 + 8]

也就是说，指令选择先生成带 temp 的抽象汇编；真实寄存器名之后再填。

另一个例子：

1
抽象汇编：
2

3
ADDI `d0 <- `s0 + 3
4
LOAD `d0 <- M[`s0 + 0]
5
MUL  `d0 <- `s0 * `s1

寄存器分配后可能变成：

1
ADDI r1 <- r12 + 3
2
LOAD r2 <- M[r13 + 0]
3
MUL  r1 <- r1 * r2

10.6 抽象汇编中的二地址指令#

例子：

1
add t1, t2

效果：

1
t1 <- t1 + t2

在抽象汇编中可以描述成：

注意：

1
`s0` 隐式出现，但没有显式写在汇编模板字符串中。

意思是：t1 既是目标，也是第一个源。汇编文本里不显式写 `s0，但 src 列表里必须包含它，让后续分析知道它被读了。

10.7 过程调用#

区分：

1
过程调用：EXP(CALL(f, args))
2
函数调用：MOVE(TEMP t, CALL(f, args))

munchArgs 的任务：

生成代码，把所有参数移动到调用约定要求的位置，即寄存器或内存中。

CALL 会破坏一些寄存器：

• 调用者保存寄存器
• 返回地址寄存器
• 返回值寄存器

这些 calldefs 应该列为 CALL 的目标寄存器。

一般原则：

任何带有“写入额外寄存器”副作用的指令，都需要这样处理。

10.8 如果没有帧指针#

传统帧指针做法：

• 每次过程调用时，把栈指针寄存器复制到帧指针寄存器
• 栈指针增加新栈帧的大小

然后给出虚拟帧指针：

优点：

• 节省时间：不需要复制指令
• 节省空间：多出一个寄存器可供其他用途使用

处理方式：

1
把 FP + k 替换成 SP + k + fs

其中 fs 是栈帧大小。

总结#

本章核心脉络可以压成一句话：

指令选择用树模式覆盖规范 IR 树，生成还没有分配真实寄存器的抽象汇编。

关键点：

最容易混淆的两个词：

复杂度也要记住：

1
Maximal munch： (K' + T') N / K
2
动态规划：       (K' + T') N

当 K、K'、T' 都是常数时，两者都是线性时间。