指令选择
本文简要介绍了指令选择问题中的两种主要方法：
- 使用贪心策略的 Maximal Munch 算法，通过选择最大图块覆盖 IR 树节点，快速生成指令。
- 基于动态规划的算法，自下而上地计算最优代价，获得更精确的整体最优解。
通过对比这两种方法，可以在编译过程中更好地进行目标代码生成。
（摘要由 OpenAI o1-preview 生成）
基于模式匹配的指令选择¶
基于树的模式匹配¶
中间表示树上的一个部分作为一个单元，对应可供选择的某条汇编指令。
将指令选择问题转变为图的覆盖问题（选择代价最小的覆盖）
Optimum Tiling vs Optimal Tiling¶
Optimum Tiling: 全局最优，整体代价最低。
Optimal Tiling: 局部最优，每个片段最优但整体不一定最优。
指令选择的算法¶
Maximal Munch 算法¶
Maximal Munch 算法：找到 Optimal Tiling。这是一个贪心算法，认为选择越大的 Tile 导致的代价越小。
Tile 的「大小」 := Tile 包含的节点数。
在 Maximal Munch 算法中，遇到相同大小的 Tile 将会任意选择其中之一。
从 IR 树的根节点开始，每次选择能够覆盖当前节点的最大图块，这将把原先的 IR 树分割为若干子树。
对每个被分割出的子树，重复相同的算法。
在完成 Tile 的放置后，以相反的顺序生成指令（从叶节点向根节点生成）。
基于动态规划的算法¶
动态规划：找到 Optimum Tiling。
自下而上地计算每个节点的最小成本。对于每个节点，首先计算其子节点的最小总成本 Tiling。每个节点的成本 := 所选 Tile 的成本 + 产生的子树的成本。
对于节点 \(x\)，定义 \(f(x)\) 为以 \(x\) 为根节点的树的 Optimal Tiling 的总成本，\(f(x)\) 以下面的公式计算：
当整棵 IR 树的根节点的最小代价被找到，根据 IR 树的所有结点的代价状态，可以确定指令的选择（这个过程被称为 instruction emission ），方法为：
Emission(node n)：对于 n 选择的 Tile 产生的每一个子树的根节点 li，执行 Emission(li)，然后发射节点 n 选择的 Tile 对应的指令。