命令選択とレジスタ割り付け (コンパイラバックエンド)

コンパイラのバックエンドが、ターゲット非依存の中間表現 (LLVM IR) を特定 ISA の機械語へ落とす過程の中核技術。LLVM RISC-V バックエンド (MYRISCVX) の実装を題材にした整理。全体像は llvm-riscv-backend、IR 基盤は llvm-mlir。

llc のパイプライン

llc (LLVM IR → アセンブリ) は概ね次の段階を踏む。

1. LLVM IR → SelectionDAG: 各基本ブロックの計算を有向非巡回グラフ (DAG) に変換。
2. Legalize: ターゲットが直接扱えない型・操作 (例: 64bit op を 32bit ターゲットで) を合法な形へ変換。
3. Instruction Selection (命令選択): DAG のパターンを ISA の命令にマッチさせる。.td のパターンマッチで「この DAG 部分木 → この命令」を宣言する。
4. SelectionDAG → MachineInstr: 仮想レジスタ上の機械命令列へ。
5. Register Allocation (レジスタ割り付け) + 関数のプロローグ/エピローグ挿入。
6. MachineInstr → MCInst → 最終的な命令へ。

命令選択

中間表現の演算を、ターゲット命令の 被覆 (tiling) 問題として解く。LLVM では .td (ターゲット記述ファイル) に DAG パターンと命令の対応を書き、TableGen (tablegen) がマッチャを生成する。型はモードで切り替えられ、def XLenVT: ValueTypeByHwMode<[RV32,RV64,...],[i32,i64,...]> のようにレジスタ幅を抽象化する。命令定義は MYRISCVXInst<outs, ins, asmstr, pattern> の形で opcode/アセンブリ文字列/マッチパターンを束ねる。

レジスタ割り付け

無限にある仮想レジスタを、有限な物理レジスタ (RISC-V は汎用32本) へ写す。同時に生存する値が物理レジスタ数を超えると スピル (メモリへ退避) する。.td の RegInfo<レジスタサイズ, spill サイズ, spill アライン> がスピル時の挙動を規定する。割り付けは呼び出し規約 (ABI) と密接で、

• 引数は reg で8個まで、超過分は mem。戻り値は reg 2つまで。
• t レジスタ = caller saved (呼び出し側が退避)、s レジスタ = callee saved (呼び出され側が ret 前に復元)。

プロローグ/エピローグで s レジスタの退避・復元とスタックフレーム (局所変数領域) の確保を挿入する。フレーム関連は FrameLowering、命令生成 (lowering) は TargetLowering、命令定義は InstrInfo、レジスタアクセスは RegisterInfo が担当する。

ポイント

• 命令選択 = パターンマッチによる IR→命令の被覆。レジスタ割り付け = 仮想→物理 + スピル。
• ターゲット固有部は宣言的な .td + TableGen 生成に寄せ、C++ 側は lowering の隙間を埋める。
• ABI (呼び出し規約・caller/callee saved) がレジスタ割り付けとフレーム生成の制約になる。

関連

• llvm-riscv-backend、tablegen、llvm-mlir、risc-v-isa。
• フロントエンド寄りの素朴な生成は stack-machine-codegen、最適化は compiler-optimization。