指令选择

excerpt

基于模式匹配的指令选择

中间表示树上的一个部分作为一个单元，对应可供选择的某条汇编指令。

将指令选择问题转变为图的覆盖问题（选择代价最小的覆盖）

Optimum Tiling: 全局最优，整体代价最低。

Optimal Tiling: 局部最优，每个片段最优但整体不一定最优。

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)$$ 以下面的公式计算：

f(x) = \min_{\forall T\text{ covering }x}\left( \text{cots}(T) + \sum_{\forall \text{ child }y\text{ of tile }T}f(y) \right)

当整棵 IR 树的根节点的最小代价被找到，根据 IR 树的所有结点的代价状态，可以确定指令的选择（这个过程被称为 instruction emission ），方法为：

Emission(node n)：对于 n 选择的 Tile 产生的每一个子树的根节点 li，执行 Emission(li)，然后发射节点 n 选择的 Tile 对应的指令。