跳转至

8 Instruction Selection

指令选择是将 IR 树翻译为机器指令的过程。核心抽象是用一组模式 (Pattern / Tile) 覆盖整棵 IR 树，每个 Tile 对应一条或多条机器指令，目标是找到代价最小的覆盖方案。

8.1 Problem Modeling

Tile (瓷砖)：一个 IR 子树片段，对应一条机器指令。例如 Tile MEM(BINOP(PLUS, CONST c, TEMP r)) 对应 x86 的 mov r, [r+c]。

TEMP Tile：特殊的零代价 Tile，表示值已在寄存器中，无需额外指令加载。

树覆盖 (Tiling)：用一组 Tile 无重叠、全覆盖地铺满 IR 树。同一棵树通常有多种铺法

Optimal vs Optimum：

概念 含义 性质
Optimal 局部最优——没有两个相邻 Tile 可合并为代价更低的 Tile 局部极小值
Optimum 全局最优——所有 Tile 代价之和最小 全局极小值

所有的 Optimum 都是 Optimal，反之不成立。Optimum ⊂ Optimal。

8.2 Core Algorithms

8.2.1 Maximal Munch

贪心 + 自上而下。在每个节点选择覆盖节点数最多的 Tile，然后递归处理未覆盖的子树。

munch(node):
    找能匹配 node 的最大 Tile（节点数最多）
    为 Tile 中每个叶子节点递归调用 munch
    生成本条指令
  • 优点：速度快，实现简单。
  • 局限：只能保证 Optimal，不能保证 Optimum。但在 RISC 架构下（指令代价相近）差别不大。
  • 指令生成顺序：后序遍历（先子树再父节点），自然产生逆序代码。

8.2.2 Dynamic Programming

自下而上。分两阶段——先算代价，再生成代码。

阶段 1 — 计算代价：对每个节点 n，尝试所有能匹配的 Tile t：

cost[n] = min( tile_cost[t] + Σ cost[leaf_of_t] )

记录取得最小代价的 Tile（即选择路径）。

阶段 2 — 生成代码：从根节点出发，沿记录的最优 Tile 后序遍历，逐条生成指令。

  • 优点：保证找到 Optimum（全局最优）。
  • 代价：需遍历所有 Tile 匹配，但当 Tile 集固定时仍是线性时间 \(O(N)\)。

8.2.3 Tree Grammars

将指令选择转化为解析问题：用类似 CFG 的产生式描述 Tile，非终结符代表寄存器类或存储位置，每条规则对应零条或多条机器指令。

适用场景：复杂 CISC 架构（指令集庞大、寻址模式多）。典型工具：BURG、LLVM TableGen。

8.3 RISC vs CISC

RISC CISC
指令特点 定长，寻址模式少，寄存器多 变长，寻址模式多，寄存器少且有特殊用途
指令代价 均匀，Optimal ≈ Optimum 不均匀，Optimal 与 Optimum 差异大
推荐算法 Maximal Munch 足够 DP 或 Tree Grammars
内存访问 显式 Load/Store 算术指令可直接含内存操作数
额外问题 少 双地址指令需插入 MOVE、寄存器分类需转换指令、副作用指令（自增寻址）难以用树表示

CISC 的关键对策：

  • 寄存器少 → 先多生成 TEMP 节点，交给寄存器分配器统一处理溢出。
  • 寄存器分类（如地址寄存器 vs 数据寄存器）→ 在不同类间插入 MOVE 指令桥接。
  • 双地址指令（r1 = r1 + r2 会破坏 r1）→ 先插入 MOVE 保留原值，后续由寄存器分配器删除冗余移动。

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！