Skip to content

Chapter 9: Instruction Select

IR-tree 覆盖 - 不同的覆盖方式

  • a[i]:=x alt text

选取最小的覆盖单元：

Optimal

什么覆盖最好?

  • Best tiling - cost 最小的指令序列
    • 对单发射固定延迟的机器来说，指令条数最小
  • Optimum tiling - cost 最小，全局最优的覆盖
  • Optimal tiling - 无法合并瓦片使得覆盖更优，局部最优的覆盖
    • 不存在分解后更优的情况
    • 不一定是全局最优 e.g. {a,b,c}{d,e} 和 {a,b}{c,d,e} 都无法合并，cost 可能不同

Maximal Munch

  • Main idea - 贪心，top-down
    • 从上到下扫描
    • 找到覆盖当前结点的最大瓦片（旁边的一些结点也可能被覆盖）
    • 在叶子结点的 subtree 上重复
  • Largest tile - 覆盖结点数最多的瓦片

alt text

Implementation

两个递归函数

Maximal Munch 只能找到 Optimal 覆盖，不一定是 Optimum 覆盖

Dynamic Programming

  • bottom-up
  • 给每个结点一个 cost 属性
  • cost of x = 以 x 为根的子树的最小 cost（best tiling）
    • $f(x) = min_{\forall\ tile\ t\ covering\ x}(c_t+\sum_{\forall\ leaf\ i\ of\ t}f(i)) $
  • 记号 (a,b) - (cost, tree pattern 序号)

(a,b): a is the minimum cost,b is the corresponding pattern

复杂度分析

  • 每个瓦片平均有 K 个子树
  • input tree 有 n 个 nodes
  • K' - 最多需要检查几个结点才知道用哪个瓦片匹配
  • T' - 有几个瓦片可以匹配当前结点
  • Maximal Much 复杂度：(K'+T')N/K
  • Dynamic programming: (K'+T')N

Tree Grammars

指令种类很多的情况，用上下文无关语法去匹配 tree pattern

用动态规划

每个非终止符的 cost 会被计算

CISC