Skip to content

Instruction Selection

:material-circle-edit-outline: 约 245 个字 :material-clock-time-two-outline: 预计阅读时间 1 分钟

Instruction selection: tiling the tree with a minimal set of tree patterns.

Tiling: cover the tree with nonoverlapping tree patterns

The Jouette architecture

image-20250422210711594

Some instructions correspond to more than one tree pattern

image-20250422210917462

It is always possible to tile the tree with tiny tiles, each covering only one node

image-20250422210939895

Optimal and Optimum Tilings

  • Best tiling: 理论最最优
  • Optimum tiling：全局最优，cost 最小的覆盖
  • Optimal tiling: 局部最优，选择任意两个瓦片进行合并，代价没有变得更低

Every optimum tiling is also optimal, but not vice versa

image-20250422211351723

Algorithms for Instruction Selection

Maximal Munch

能找到局部最优，能保证任意两个瓦片都不能合并

认为越大的瓦片越好，采用贪心算法，自顶向下遍历 IR tree，用尽可能大的瓦片进行覆盖当前的结点，再递归检查剩下的

遇到多个选择时随便选一个即可

Dynamic Programming

能找到全局最优

我们对树中每个结点赋予一个 cost：

image-20250428160452799

image-20250615141346177

就是自底向上，每到一个结点，计算最小的 cost，一直到根节点