命令選択

IR操作からターゲットマシンの命令へのマッピング——1対1対応ではなく、木のカバー問題として捉える：命令パターンでIR式木をマッチングさせ、最小コストのカバー方案を見つける。貪欲法によるmaximal munchから動的計画法、そしてオートマトン化されたBURSまで。

概要

中間表現 は機械非依存である——add i32 %a, %b。一方、ターゲットマシンには独自の命令セットがある：x86-64 には addl %eax, %ebx があり、ARM64 には add w0, w1, w2 がある。これらはオペコードだけでなく、アドレス指定モード、レジスタ制約、命令の組み合わせも考慮する。⁠命令選択(instruction selection) とは、IR操作をターゲットマシンの命令列にマッピングすることである。これは1対1の対応ではない——1つのIR命令が複数の機械命令に対応する場合（複雑な操作が分解される）、あるいは複数のIR命令が1つの機械命令に対応する場合（複合アドレス指定モードや融合命令による）がある。

問題モデリング：木のカバー(tree tiling)

IRは式木として整理される（各木は計算を表す。例えば a[i] = x + 2 は木に展開できる）。ターゲットマシンの各命令も木形パターンとして記述される：

命令選択 = 命令パターン木でIR木をカバー(tile)し、各リーフがちょうど1つのカバーに属し、総コストが最小になるようにする。

これが tree tiling 問題である——各命令 i にはパターン木 p_i と実行コスト c_i があり、総コストを最小化するカバー方案を見つける。

3つのアルゴリズム、コストと精度が順に上昇

1. マクロ展開(macro expansion): 最も単純

IR操作 add → 直接 addl %src, %dst を出力。ターゲットマシンの特性を一切利用せず、生成されるコードは明らかに劣る（例：load + add が2命令に分かれるが、CISCには add [addr], %reg がある）。しかし実装が単純で、JITのベースラインコンパイルやコードサイズが敏感でない場面で使われる。

2. maximal munch: 貪欲法、局所最適

木根から始め、⁠現在のサブツリーをカバーできる最大パターン⁠（最も多くのノード）を選び、残りの部分に対して再帰的に処理する：

munch(node):
    for each pattern from largest to smallest:
        if pattern matches at node:
            emit instruction for that pattern
            for each leaf in pattern that is a subtree root:
                munch(that leaf)
            return

• 貪欲法は大域的最適を保証しないが、実用的には大域的最近傍となる（機械命令パターンは通常「別の命令の全ノードを食べ込むほど大きく」ならないため）。
• 計算量 O(n)、1回のスキャンで完了し、JITコンパイル（例：V8のベースラインコンパイラ）に適している。

3. 動的計画法: 大域的最適

ボトムアップで、各ノードについて「そのノードを根とするサブツリーをカバーする最小コスト」を計算する：

for each node n in postorder:            ← ボトムアップ
    for each pattern p that matches at n:
        cost = p.cost + sum(minCost(leaf) for leaf in p.leaves)
        minCost[n] = min(minCost[n], cost)

その後、トップダウンでバックトラックし、各ノードで使うパターンを選択

• 与えられた命令パターン集合とコストモデルの下で、大域的最適カバーを保証する。
• 計算量 O(n × |patterns|)。多くのIR木と命令セットにおいて、|patterns| は百単位程度であり、許容範囲内。
• BURS(Bottom-Up Rewrite System) はDPをオートマトンに組み込む——「木マッチングから状態への置換」変換表を事前計算し、実行時に O(n) で処理する。ただしBURSの構築は複雑であり、LLVMのSelectionDAGは多くのターゲットでDP（厳密なBURSではない）を使用している。

命令選択の追加的な複雑さ

複数出力命令

divmod x, y は1命令で商と剰余の両方を生成する——2つのIR値、1つの機械命令。木カバーモデルはDAGカバー（有向非巡回グラフ、同一ノードが複数の木で共有可能）に拡張する必要がある。この場合、貪欲法もDPも複雑になる。

可変長命令セット

x86-64 では同一操作に複数のエンコーディングがある：addl $1, %eax(3バイト) vs addl $1, (%esp)(4バイト)。命令選択では「どの命令か」だけでなく「どのバリアントを使うか」も考慮する必要がある——アドレス指定モードの選択が命令選択の一部となる。

合法化(legalization)

一部のIR命令組み合わせは、ターゲットマシンで直接サポートされていない。命令選択の前または最中に合法化を行う必要がある：

IR:  reg内のアドレスに64ビット値をストア
ARM64: 64ビットストアをサポート → 合法
16ビットマイコン: サポートしない → 2回の32ビットストアに分解 (legalize)

LLVMのSelectionDAGでは、合法化と命令選択を交互に行う——LegalizeDAG パスはサポートされていない操作を同等のシーケンスに分解し、SelectionDAGが命令を選択する。

命令スケジューリングとレジスタ割り当てとの干渉

命令選択の後、⁠命令スケジューリング⁠（パイプラインストールを減らすために順序を再配置）とレジスタ割り当て⁠（IRの仮想レジスタ→限られた物理レジスタ）が残っている。これら3つは互いに干渉する：

命令選択: 命令を選択 → レジスタの使用を定義
命令スケジューリング: 順序を再配置 → アクティブ範囲を変更
レジスタ割り当て: スパリングの可能性 → load/storeを挿入 → 命令列を変更

後者は レジスタ割り当て で展開される。命令選択とレジスタ割り当ての間には位相の順序問題がある：先にレジスタ割り当てを行ってから命令選択を行う（そのレジスタを使わない命令を選ぶ可能性がある）、それとも先に命令選択を行ってから割り当てを行う（選択後にレジスタ不足が見つかる可能性がある）。LLVMの手法は、SelectionDAGフェーズで「仮想レジスタは無限」と仮定して命令選択を行い、その後レジスタ割り当て器がスパリングを処理する。

参考文献

• Cooper/Torczon: "Engineering a Compiler", Chapter 11 (Instruction Selection)
• Cattell (1978): Formalization and Automatic Derivation of Code Generators (木パターンマッチングの初期作業)
• LLVM: lib/CodeGen/SelectionDAG/ — 産業レベルのDPベース命令選択; lib/CodeGen/GlobalISel/ — 次世代のグローバル命令選択

Keywords: 命令選択, 木パターンマッチング, タイル, maximal munch, 動的計画法, BURS, マクロ展開, 合法化, ローリング, SelectionDAG, GlobalISel, アドレス指定モード, 複数出力命令, 命令スケジューリング干渉