--- title: 命令選択 url: https://doc.liz6.com/ja/compilers/06-code-generation/01-instruction-selection locale: ja area: compilers tags: - compilers - code-generation date: 2026-06-30 modified: 2026-07-19 description: IR 演算をターゲットのマシン命令にマッピングする——1対1の対応ではなく、木のカバー問題である：命令パターンで IR 式木をマッチングさせ、最小コストのカバー方案を見つける。貪欲な maximal munch から動的計画法、そしてオートマトン化された BURS へ。 --- # 命令選択 > IR 演算をターゲットのマシン命令にマッピングする——1対1の対応ではなく、木のカバー問題である：命令パターンで IR 式木をマッチングさせ、最小コストのカバー方案を見つける。貪欲な maximal munch から動的計画法、そしてオートマトン化された BURS へ。 ## 概要 [中間表現](/compilers/04-intermediate-representation/01-ssa-form.md) はマシン非依存である——`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 の baseline compiler）。 ### 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-bit 値を store ARM64: 64-bit store をサポート → 合法 16-bit MCU: サポートしない → 2回の 32-bit store に分解 (legalize) ``` LLVM の SelectionDAG は合法化と命令選択を交互に行う——`LegalizeDAG` パスはサポートされていない操作を同等の列に分解し、SelectionDAG が命令を選択する。 ## 命令スケジューリングとレジスタ割り当てとの干渉命令選択の後、**命令スケジューリング**(パイプラインストールを減らすために順序を再配置)と**レジスタ割り当て**(IR の仮想レジスタ→限られた物理レジスタ)が残っている。これら3つは互いに干渉する： ``` 命令選択: 命令を選択 → レジスタの使用を定義命令スケジューリング: 順序を再配置 → アクティブ範囲を変更レジスタ割り当て: スパリングの可能性 → load/store を挿入 → 命令列を変更 ``` 後者は [レジスタ割り当て](/compilers/05-optimization/03-register-allocation.md) で展開される。命令選択とレジスタ割り当ての間には位相の順序問題がある：先にレジスタを割り当ててから命令を選択するか（使わないレジスタを使う命令を選ぶ可能性がある）、先に命令を選択してから割り当てるか（選択後にレジスタが足りない可能性がある）。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, アドレス指定モード, 複数出力命令, 命令スケジューリング干渉*