# 指令选择

找出实现一个给定的 IR Tree 的恰当机器指令序列。Mapping IR into abstract assembly code

• Abstract assembly = assembly with infinite registers
  • Invent new temporaries for intermediate results
  • Map to actual registers later
    Tree pattern, 也叫 tile
    本质上是 pattern matching, 我们使用 tree covering 来实现

我们 Jouette 体系将树模式映射为指令:

• 寄存器中可以存储数据或地址，每条指令可以访问任意寄存器
• 寄存器 r0 的值永远是 0
• 每条指令的 latency 都是一周期（除了 MOVEM 的周期是 m）
• 每个周期执行一条指令

将 IR 与后端的机器指令都转换为树结构。这样就把指令选择问题转换为机器指令树覆盖全 IR Tree 的问题。
一棵树可以有多种 tiling 方式

# Optimal Tiling & Optimum Tiling

• Optimum Tiling：使得 tiling 数最少，是全局最优
• Optimal Tiling：No two adjacent tiles can be combined into a single tile of lower cost，是局部最优
  一个 optimum tiling 必定是 optimal tiling
  

# Algorithms for Instruction Selection

# Maximal Munch: Find an optimal tiling

最大匹配：贪心算法、自顶向下
方法：从 IR 树的根节点开始，用最大的 tile 覆盖当前节点（包含最多节点的），然后在子树中重复此过程

# DP

动态规划：自底向上
方法：

1. 递归计算每个子树的最优平铺成本
2. 对于每个节点，考虑所有可能的匹配平铺
3. 对于每个匹配平铺，计算其成本如下：cost = tile_cost + sum（costs_of_children）
4. 选择成本最低的平铺

• 对于$CONST i$，它的代价为 1 (ADD r1, r0, i)
• 对于这棵树，有三种匹配方法
  
  
  因为 2<3，所以我们从 cost=2 的两个任选一个
  接下来对于 MEM，用的都是 LOAD，代价都是 1，2<3 所以选 cost=2 的

1
2
3
4

function Emission(node n):
    For each leaf l_i of the tile selected at node n:
        Emission(l_i) 
    Emit the instruction matched at node n

# 最大匹配 vs 动态规划

• T - tile 的总种类数
• K - 一个 matching tile 平均覆盖的节点数
• K’ - 需要检查的最大 tile 尺寸（即最大的瓦片包含的节点数）
• T’ - 每个树节点平均能匹配上的 tile 数量
• N - 输入的中间表示 IR Tree 中的总节点数

两种算法的运行时间复杂度：

• 最大匹配（Maximal Munch） - 其时间复杂度与

$$\frac{(K' + T') * K}{K} * N = (K' + T') * N$$

成正比

• 动态规划（Dynamic Programming） - 其时间复杂度与

$$(K' + T') * N$$

成正比

# Tree Grammar 树文法

问题：对于具有复杂指令集和多种寄存器类型及寻址模式的机器，难以使用简单的 tree pattern 和 tiling 算法。
用一种文法来描述 tiles，代替手写过程式匹配代码，支持自动化的指令选择，增强了可移植性
图没看懂，后面再回来研究