愛の手紙：Purple Garden 仮想マシンとレジスタ割り当ての実装記

記事の概要

「喜びの歌（Ode to Joy）」の精神を受け継ぎ、私のプログラミング言語 Purple Garden の開発について解説します。 このプロジェクトでは、レジスタ指向バイトコード仮想マシン と、x86 アーキテクチャ向けの リアルタイムコンパイラ（JIT コンパイラ） の開発を並行して進めています。

• 生命（ライフ）の分析：本記事で紹介するピクセルアートの象徴は、コード実行におけるデータフローとレジスタのライフサイクルを理解することです🤓
• 開発焦点：レジスタ割り当て（Register Allocation） アルゴリズムの実装と最適化。

---

1. レジスタ割り当てとは何か？

レジスタ割り当てとは、理論上無限にある仮想的なレジスタを、ハードウェアの物理的な制約（GPRs、FPRs、スタック）に合わせて割り当てるプロセスです。

この課題を解決する第一歩となるのは、「活性度分析（Liveness Analysis）」 です。 これは、各変数や値がコード内で実際に使用されている期間（ライフタイム）を追跡し、いつまでメモリまたはレジスタ上に存在させる必要があるかを決定するための解析手法です。

---

2. ガーデニング：最小単位の例題

最適化の原理をわかりやすく解説するために、簡素な関数の変換例を見てみましょう。

プログラム源（Purple Garden）

以下の関数は階乗の計算に関連するロジックを持っています。

fn f(a:Int n:Int acc:Int) Int {
    match {
        n < 1 { a + acc }
        { f(a n-1 acc*n) }
    }
}

C コードへのディスアセンブル

元の IR を理解するために、Max Bernstein の論文「Linear scan register allocation」から引用された C コードと比較します。Purple Garden ではループ構造を明示的に持たないため、等価な呼び出しは

f(a, n, 1)

です。

long f(long a, long n) {
    long acc = 1;
    while (n >= 1) {
        acc = acc * n;
        n = n - 1;
    }
    return a + acc;
}

Purple Garden IR（最適化後）

-I

フラグを使用することで生成される即時表現（Immediate Representation） です。不要な変数が削除され、効率的になっています。

fn f1(%v0:Int, %v1:Int, %v2:Int) -> Int {
    b0(%v0, %v1, %v2):
        %v4:Bool = ILt %v1, 1
        br %v4, b1(%v0, %v1, %v2), b2(%v0, %v1, %v2)
    b1(%v5, %v6, %v7):
        %v8:Int = IAdd %v5, %v7
        ret %v8
    b2(%v9, %v10, %v11):
        %v13:Int = ISub %v10, 1
        %v14:Int = IMul %v11, %v10
        tail f1(%v9, %v13, %v14)
}

---

3. Purple Garden の IR 構造と表記法

Purple Garden の IR は 静的単一割り当て（SSA） 形式に基づいています。

主な特徴

• 不変性：各値／仮想的なレジスタは

  exactly once

  だけ定義され、不変です。
• 表記法：仮想レジスタは

  %vN

  と表記します。
• ブロック構造：Phi ノード（φノード）を使用せず、ブロックパラメータとターミネーターのみで制御流を表現します。

LLVM IR 構造の詳解

各ブロックは「パラメータリスト」＋「指令本体（SSA 形式）」＋「ターミネーター」で構成されます。すべての値はブロックローカルであり、データフローはこの境界を通じてのみ実装されます。

Rust による型定義（参考）

pub struct Block<'b, A: Allocator = Global> {
    pub id: Id,
    pub instructions: Vec<Instr<'b>, A>,
    pub params: ParamsId,
    pub term: Option<Terminator>,
}

// 一部の重要な指令例
pub enum Instr<'i> {
    BinImm { op: BinOp, dst: TypeId<'i>, lhs: Id, imm: i32 },
    // ... 他のインストラクション ...
}

pub enum Terminator {
    Return { value: Option<Id> },
    Tail { func: Id, args: ParamsId },
    // ... 他のターミネーター ...
}

---

4. 仮想的なレジスタのライフタイム分析

SSA IR を可視化することで、各値のライフタイム（開始位置

lo

と終了位置

hi

）を把握できます。

ライフタイムアノテーション付き IR

CLI に

-II

フラグを指定すると、以下の図のように各レジスタの生きている範囲が視覚的に表現されます（ブロックパラメータはオフセット 0 で始まります）。

ライフタイム表（線形化された位置）

value	lo (開始)	hi (終了)
%v0	0	2
%v1	0	2
%v2	0	2
%v4	1	2
%v5	3	4
%v7	3	4
%v8	4	5
%v9	6	9
%v10	6	8
%v11	6	8
%v13	7	9
%v14	8	9

---

5. シンプルかつ効率的な実装（活性度分析）

このアルゴリズムは以下の 4 つのステップに分解できます：

1. ブロックの巡回
2. ターミネーターの観察（使用状況の確認）
3. 指令の逆順処理（定義と使用の観察）
4. パラメータの観察

観察ロジック (

observe

)

値が「現在アクティブ」なことをマークし、ライフタイムを記録します。

/// Oxidised 用語での実装例
fn observe<V: Allocator>(out: &mut Vec<(u32, u32), V>, id: Id, pos: u32) {
    let idx = id.0 as usize;
    let e = &mut out[idx];

    // hi は未定義 (0) の場合のみ設定
    if e.1 == 0 {
        e.1 = pos;
    }
    // lo は常に現在の位置として更新
    e.0 = pos;
}

ヘルパー関数：使用と定義の取得

• def_of

  : 指令内で値が定義されるかどうかを返します。

• for_each_use_of_instr

  : 指令内の値がどこで使用されているかを走査します。

• for_each_use_of_term

  : ターミネーター内のパラメータを使用状況を走査します。

これらの関数は、Rust のパターンマッチングを用いて各インストラクションタイプを細かく分解し、対応する

Id

を集めます。この設計により、複雑な制御フローでも堅牢に活性度解析が可能です。

---

6. 統合された実装とレジスタ割り当てへの適用

計算された活性度セット（Liveset）は、実際のレジスタ割り当てアルゴリズムの入力として機能します。これにより、ハードウェアの物理レジスタやスタックスロットに適切な値を配置できます。

レジスタ割り当て予備パス

Cc::prealloc

を実行することで、降下処理（Lowering）の前に IR を巡回し、簡易的な検索による割り当てを行います。

// 概要：活性度セットの計算 -> prealloc の実行 -> ブロック・指令反復処理
fun.live_set_into(&mut self.live_set);
self.prealloc(fun);

// レジスタ割り当て後のポスト処理（スタックへの溢れ出しなど）
if let Some(Location::Stack(slot)) =
    Func::def_of(instruction).and_then(|dst| self.regalloc.location(dst))
{
    self.emit(Op::StoreSlot { slot, src: TMP });
}

IR 操作の降下処理（Lowering）

Bin

および

BinImm

などの演算子を、VM レジスタ上の物理的な操作に変換します。

• 二項演算：左辺と右辺をレジスタ確保し、オペコードを発行します。
• 即時値演算：即座に命令セット化され、メモリアクセスを減らします。

Rust マクロを活用することで、すべての二項演算とその即時版を約 57 行で記述しています。これはコンパイラ実装における洗練された手法です🤓。

レジスタの確保と定義

仮想レジスタを VM レジスタに変換する際に、以下の 2 つの重要な動作を行います：

1. ensure_register

   ：値が物理レジスタに割り当てられていればそのまま使用し、スタック上であれば一時レジスタを使ってメモリから読み込み（リストア）します。

2. def_register

   ：演算の結果を格納する先頭レジスタを決定します。既にレジスタにあればそれを返し、なければ

   TMP

   を使用します。これにより、溢れ出した結果は自動的にスタックスロットに保存されます。

---

7. バイトコードと JIT アセンブリの統合

活性度解析とレジスタ割り当ての結果が反映されたアセンブル出力を確認できます。

バイトコード生成（-I フラグ）

SSA 値に割り当てられた仮想マシンレジスタが見えます。

000000000 <f>:
  0000:    ilt_imm r3, r1, #1        ; n < 1 の判定
  0001:    jmpf r3, 0004 <f.bb_0004>
  0002:    iadd r0, r0, r2           ; a + acc
  0003:    ret
000000004 <f.bb_0004>:
  0004:    isub_imm r3, r1, #1       ; n - 1
  0005:    imul r2, r2, r1           ; acc * n
  0006:    mov r1, r3                ; 値の移動
  0007:    tail 0000 <f>             ; リカーシブ呼び出し

JIT コンパイル（x86）

JIT モードでは、さらに最適化されたネイティブコードが生成されます。比較命令と条件分岐を単一の指令に統合するなどの高度な技術が使われています🤓。

0000000000000000 <jit_f>:
   0:   48 81 fa 01 00 00 00    cmp    $0x1,%rdx          ; n < 1 の比較（cmp）
   7:   49 c7 c0 00 00 00 00    mov    $0x0,%r8           ; リセットフラグ設定
  ... (最適化されたループと計算ロジック) ...

---

今後の展望

現在、IR デザイン、レジスタアロケーター、バックエンド間の相互作用を「完璧に」調整する段階です。

• 追加の課題：レジスタアロケーターの入力（活性度セット）と出力（物理レジスタ割り当て）については詳述しましたが、ブロック遷移（ジャンプやリターン）をエッジ移動として扱い、これらを解決するための追加の実装についてはまだ未発表です。
• 今後の予定：動機が維持される場合、これらのトピックについてフォローアップの記事を書く予定です。

私の不整合なたわごとを共有するための RSS フィードもありますので、ご興味がある方はぜひそちらもご覧ください。