コンパイラ最適化（ループ変換・ベクトル化・レジスタ割り付け）

コンパイラ最適化

コンパイラはプログラム意味論を保ちつつ高速化する。意味保存のため静的解析は保守的近似に頼り、最適化機会を逃しやすい。代表的な最適化を以下に整理する。

ループ変換と並列化

• 依存解析 (dependence analysis): ループの並列化可能性は data dependence で決まる（Allen & Kennedy の FORTRAN→ベクトル形式変換が古典）。Program Dependence Graph (PDG) を作って loop fusion / peeling / unrolling を導く。
• Polyhedral Model: ループ反復空間を整数多面体（affine 不等式の交差）として表し、affine 変換で並列性・局所性を最適化する枠組み。Pluto などが LLVM Pass として実装。Farkas の補題・線形計画と結びつく。
• Optimistic Loop Optimization: 前提条件を実行時検証し、保守的近似を超えてループ変換を可能にする。

ベクトル化

• SLP (Superword Level Parallelism): マルチメディア命令を使い、隣接スカラ演算を束ねてベクトル化。
• 制御フローの divergence analysis と masked vector intrinsics で分岐を含むコードもベクトル化。
• 等式飽和を使うベクトル化: DSP 向け (diospyros) で書き換え規則と e-graph により命令選択を探索。線形代数では SPORES。

SSA とスカラ最適化

• mem2reg（メモリ→SSA レジスタ昇格）、global value numbering (GVN)、lazy code motion など SSA 上の古典最適化。

レジスタ割り付け

• グラフ彩色ベース（干渉グラフを彩色）と、より軽量な Linear Scan Register Allocation（生存区間を線形に走査）。LLVM・Go・各種教育用コンパイラで実装される。

関連

• 実装基盤はllvm-mlir、書き換え探索はequality-saturation・equality-saturation。
• ML系コンパイラの各段はクロージャ変換も参照。
• _moc-lang-compilers

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

コンパイラのバックエンドが、ターゲット非依存の中間表現 (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。
• フロントエンド寄りの素朴な生成は compiler-optimization、最適化は compiler-optimization。

スタックマシン向けコード生成とラベルバックパッチ

スタックマシン (pl0 のような単純な VM) を対象にした、yacc アクション中で命令列を組み立てるワンパスのコード生成手法。cmm→pl0 コンパイラの拡張を題材に整理する。実例は cmm-pl0-compiler。

スタックマシンと逆ポーランド

pl0 VM は値スタック s とトップ位置 t を持つ。式は 逆ポーランド (後置) の順で命令を並べれば評価できる。

• リテラルは O_LIT でプッシュ (s[++t] = a)。
• 単項演算は s[t] を上書き (位置不変)。
• 二項演算は --t してから s[t] と s[t+1] を演算し s[t] に書き戻す。

例: a + b は「a のコード」「b のコード」「加算命令」の順に連結する。式の評価がそのままスタック操作に対応するため、AST を後行順 (post-order) に辿るのと等価。

命令列の合成 (makecode / mergecode)

pl0 命令は連結リスト struct CODE {next, f, l, a} で表され、cptr {h, t} がリストの head/tail を保持する。基本 API は 2 つ。

• makecode(f, l, a): 1 命令を生成。例えば + は makecode(O_OPR, 0, 2)。
• mergecode(c1, c2): 2 つの命令リストを連結。

yacc アクションでは下位規則の $n.code が部分式の命令列を持つので、それらを mergecode で順に繋いで $$.code に格納する。これは構文主導翻訳 (syntax-directed translation) の最小実装と言える。

mergecode の落とし穴

mergecode は内部で第2引数を free() するため、同じ $n.code を 2 回使うとセグフォになる。a % b を a - b*(a/b) のように a,b を複数回参照する形へ展開しようとすると破綻するので、命令リストの複製関数を作るか、後述のように VM 側に専用命令を足して回避する。

制御構造とラベル

分岐・ループは「ラベル発行 + 条件ジャンプ」で実現する。makelabel() が連番ラベルを返し、O_LAB/O_JMP/O_JPC (条件偽でジャンプ) を配置する。

• for: <初期化> LAB L0 <条件> JPC L1 <本体> <更新> JMP L0 LAB L1。
• switch/case: 構文解析は下位規則から進むため case の時点では判定対象変数 v が未知。各 case を一旦グローバル配列 cases[] (cond, stmt) に退避し、switch v 規則でループしてまとめて生成する。break は末尾 end_label への JMP、default は条件を LIT 1 (常時真) で表す。

ラベルバックパッチ (前方参照)

goto L; ... label L; のように使用が定義より前に来る 前方参照 では、その時点でラベル番号が未確定。対処として goto/label どちらの規則でも「文字列 L が未登録なら makelabel() して登録、登録済みならその番号で生成」という統一規則にする。ラベル文字列↔番号はグローバル labels[] + 線形探索 search_label() で管理 (C にハッシュマップが無いため)。これは一般のアセンブラが行う バックパッチ の素朴版。

VM 拡張による命令追加

コンパイラレベルで合成できない演算は VM に命令を足す。vm/code.h の opecode/oprcode enum に追記し、vm/inter.c の interpreter() の switch に処理を加える。

• 剰余 % / 累乗 **: 合成を諦め P_MOD/P_POW を新設。
• 論理 &&/||/!: P_AND/P_OR/P_NOT。
• 配列: 添字が変数になり定数アドレスの LOD/STO では不可。スタック値をアドレスとして使う 動的ロード/ストア O_DLD/O_DST を追加。さらに変数宣言時の領域計算 vd_backpatch() を、配列長を考慮して複数領域を確保するよう改修 (struct LIST に length を追加)。

関連

• 言語フロントエンドの上位手法: parser-combinator、parser-combinator。
• ツール: lex-yacc。
• 同系統の自作処理系: cmm-pl0-compiler、toy-llvm-compiler、arcturus-interpreter。
• バックエンド寄りの低レベル生成: compiler-optimization。