LLVMによるガベージコレクション

概要

このドキュメントでは、ガベージコレクションをサポートする言語のコンパイラにLLVMを統合する方法について説明します。**LLVM自体はガベージコレクターを提供しません。**独自のガベージコレクターを提供する必要があります。

クイックスタート

最初に、コレクター戦略を選択する必要があります。LLVMにはいくつかの組み込み戦略が含まれていますが、カスタム定義でロード可能なプラグインを実装することもできます。コレクター戦略は、コレクター自体ではなく、LLVMがコレクターおよびランタイムと対話するようにコードを生成する方法の記述であることに注意してください。

次に、生成された関数を、選択したコレクター戦略を使用するようにマークします。C++から、次のように呼び出すことができます。

F.setGC(<collector description name>);

これにより、次の断片のようなIRが生成されます。

define void @foo() gc "<collector description name>" { ... }

関数のLLVM IRを生成する際には、次の点に注意する必要があります。

  • 標準のロードおよびストア命令の代わりに、@llvm.gcreadおよび/または@llvm.gcwriteを使用します。これらの組み込み関数は、ロードおよびストアバリアを表すために使用されます。コレクターがそのようなバリアを必要としない場合は、この手順をスキップできます。

  • ガベージコレクターのランタイムライブラリによって提供されるメモリ割り当てルーチンを使用します。

  • コレクターが必要とする場合、ランタイムのバイナリインターフェースに従って型マップを生成します。LLVMはこのプロセスに関与しません。特に、LLVMの型システムは、コンパイラを通じてそのような情報を伝達するのに適していません。

  • コレクターとの対話に必要な調整コードを挿入します。多くのコレクターでは、アプリケーションコードを実行して定期的にフラグをチェックし、条件付きでランタイム関数を呼び出す必要があります。これは、多くの場合、セーフポイントポーリングと呼ばれます。

生成されたIRでルート（つまり、コレクターが認識する必要があるヒープオブジェクトへの参照）を識別する必要があります。これにより、LLVMはそれらを最終的なスタックマップにエンコードできます。選択したコレクター戦略によっては、@llvm.gcroot組み込み関数またはgc.statepointリロケーションシーケンスを使用して実現されます。

式を評価するときに生成される中間値ごとにルートを作成することを忘れないでください。h(f(), g())では、g()の評価がコレクションをトリガーした場合、f()の結果は簡単に収集される可能性があります。

最後に、生成されたプログラム実行ファイル（静的コンパイラの場合）にランタイムライブラリをリンクするか、ランタイムリンカー（JITコンパイラの場合）で適切なシンボルが使用可能であることを確認する必要があります。

はじめに

ガベージコレクションとは何か？

ガベージコレクションは、プログラマーがヒープオブジェクトのライフタイムを知る必要がないようにする広く使用されている手法であり、ソフトウェアの作成と保守を容易にします。多くのプログラミング言語は、自動メモリ管理にガベージコレクションに依存しています。ガベージコレクションには、保守的なものと正確なものの2つの主要な形式があります。

保守的なガベージコレクションは、多くの場合、言語やコンパイラからの特別なサポートを必要としません。型安全ではないプログラミング言語（C/C++など）を処理でき、コンパイラから特別な情報を必要としません。Boehmコレクターは、最先端の保守的なコレクターの例です。

正確なガベージコレクションでは、実行時にプログラム内のすべてのポインタを識別する機能が必要です（ほとんどの場合、ソース言語が型安全である必要があります）。実行時にポインタを識別するには、実行時にアクティブなすべてのポインタ変数を含む場所（プロセッサスタックとレジスタを含む）を見つけるためのコンパイラのサポートが必要です。

保守的なガベージコレクションは、特別なコンパイラのサポートを必要としないため魅力的ですが、問題もあります。特に、保守的なガベージコレクターは、マシンの特定のワードがポインタであることを知ることができないため、ヒープ内のライブオブジェクトを移動できず（コンパクト化と世代別GCアルゴリズムの使用を防ぎます）、プログラム内のオブジェクトを指す整数値のために、メモリリークが発生することがあります。さらに、一部のアグレッシブなコンパイラ変換は、保守的なガベージコレクターを壊す可能性があります（ただし、実際にはまれのようです）。

正確なガベージコレクターは、これらの問題のいずれも発生しませんが、プログラムのスカラー最適化が低下する可能性があります。特に、ランタイムはプログラムでアクティブなすべてのポインタを識別して更新できる必要があるため、一部の最適化は効果が低くなります。しかし実際には、アグレッシブなガベージコレクション手法を使用することによる局所性とパフォーマンスの利点が、低レベルの損失を上回ります。

このドキュメントでは、正確なガベージコレクションをサポートするためにLLVMによって提供されるメカニズムとインターフェースについて説明します。

目標と非目標

LLVMの中間表現は、幅広いコレクターモデルをサポートするガベージコレクション組み込み関数を提供します。たとえば、組み込み関数は次のことを許可します。

  • セミスペースコレクター

  • マークアンドスイープコレクター

  • 世代別コレクター

  • 増分コレクター

  • 並列コレクター

  • 協調的コレクター

  • 参照カウント

LLVM IRに組み込まれたサポートは、Scheme、ML、Java、C#、Perl、Python、Lua、Ruby、その他のスクリプト言語などを含む幅広いガベージコレクション言語をサポートするのに十分であると期待しています。

LLVMは**ガベージコレクター自体を提供しません**—これは、言語のランタイムライブラリの一部である必要があります。LLVMは、コンパイラにガベージコレクターの要件を記述するためのフレームワークを提供します。具体的には、LLVMは、呼び出しサイトでのスタックマップの生成、セーフポイントのポーリング、ロードおよびストアバリアの出力のサポートを提供します。また、ロード可能なコード生成プラグインを通じてLLVMを拡張して、*ランタイムライブラリ*によって指定されたバイナリインターフェースに準拠するコードとデータ構造を生成することもできます。これは、たとえばLLVMとDWARFデバッグ情報の関係に似ています。違いは主に、ガベージコレクションの分野で確立された標準がないことにあるため、柔軟な拡張メカニズムが必要になります。

LLVMのGCサポートが関係するバイナリインターフェースの側面は次のとおりです。

  • コレクションを安全に実行できるコード内のGCセーフポイントの作成。

  • スタックマップの計算。コード内の各セーフポイントについて、スタックフレーム内のオブジェクト参照を識別する必要があります。これにより、コレクターはそれらをトラバースして、場合によっては更新することができます。

  • ヒープにオブジェクト参照を格納する場合のライトバリア。これらは、世代別コレクターの増分スキャンを最適化するために一般的に使用されます。

  • オブジェクト参照を読み込む場合のリードバリアの出力。これらは、並列コレクターとの相互運用に役立ちます。

LLVMが直接対処しない追加の領域があります。

  • ランタイムへのグローバルルートの登録。

  • ランタイムへのスタックマップエントリの登録。

  • プログラムで使用されるメモリ割り当て、コレクションのトリガーなどを行う関数。

  • 型マップの計算またはコンパイル、またはランタイムへのそれらの登録。これらは、ヒープ内のオブジェクト参照をクロールするために使用されます。

一般的に、LLVMのGCサポートには、IRの他の機能で十分に対処できる機能は含まれておらず、特定のバイナリインターフェースを指定していません。良い面としては、既存のランタイムにLLVMを統合できることを意味します。一方、新しい言語の開発者にとって多くの作業が残される可能性があります。これは、多くの一般的なコレクター設計と容易な拡張ポイントで動作できる組み込みコレクター戦略記述を提供することで軽減しようと努めています。サポートする必要がある特定のバイナリインターフェースがない場合は、これらの組み込みコレクター戦略のいずれかを使用することをお勧めします。

LLVM IR機能

このセクションでは、LLVM中間表現によって提供されるガベージコレクション機能について説明します。これらのIR機能の正確な動作は、選択されたGC戦略記述によって指定されます。

GCコード生成の指定: gc "..."

define <returntype> @name(...) gc "name" { ... }

gc 関数属性は、コンパイラに目的のGC戦略を指定するために使用されます。そのプログラム的な同等物は、Function の setGC メソッドです。

関数に gc "name" を設定すると、GCStrategy の一致するサブクラスの検索がトリガーされます。いくつかのコレクタ戦略は組み込みです。ロード可能なプラグイン機構を使用するか、LLVMのコピーをパッチすることで、他の戦略を追加できます。生成されるGCをサポートするコードの正確な性質は、選択されたGC戦略によって定義されます。一致するものが見つからない場合、コンパイラはエラーを発生させます。

関数ごとにGCスタイルを指定することにより、LLVMは異なるガベージコレクションアルゴリズム（または全く使用しない場合）を使用するプログラムをリンクすることができます。

スタック上のGCルートの特定

LLVMは現在、セーフポイントでのコンパイル済みコード内の参照を記述するための2つの異なるメカニズムをサポートしています。llvm.gcroot は古いメカニズムです。gc.statepoint は最近追加されました。現時点では、どちらの実装も選択できます（GC戦略単位）。長期的に見ると、llvm.gcroot から完全に移行するか、実装を大幅にマージする可能性が高いでしょう。新しい開発作業のほとんどはgc.statepointに焦点を当てていることに注意してください。

gc.statepoint の使用

このページには、gc.statepointの詳細なドキュメントが含まれています。

llvm.gcwrite の使用

void @llvm.gcroot(i8** %ptrloc, i8* %metadata)

llvm.gcroot イントリンシックは、スタック変数がヒープ上のオブジェクトを参照しており、ガベージコレクションのために追跡されるべきであることをLLVMに通知するために使用されます。生成されたコードへの正確な影響は、関数の選択されたGC戦略によって指定されます。llvm.gcrootへのすべての呼び出しは、**必ず**最初の基本ブロック内になければなりません。

最初の引数は、alloca命令を参照する値、またはallocaのビットキャストで**なければなりません**。2番目の引数は、ポインタに関連付けるべきメタデータへのポインタを含み、**必ず**定数またはグローバル値のアドレスでなければなりません。ターゲットコレクタがタグを使用する場合は、メタデータにヌルポインタを使用してください。

手動でSSA構築を行うコンパイラは、GC参照を表すSSA値が、それぞれのgcrootに渡されるallocaに、すべての呼び出しサイトの前に格納され、すべての呼び出し後に再ロードされることを**必ず**保証しなければなりません。allocaを使用して命令型コードをSSA形式に上げるmem2regを使用するコンパイラは、GCヒープへのポインタである変数に対してのみ、@llvm.gcrootへの呼び出しを追加する必要があります。

中間値にもllvm.gcrootでマークすることが重要です。たとえば、h(f(), g())を考えてみましょう。g()がコレクションをトリガーした場合に、f()の結果がリークすることに注意してください。スタック変数は、関数のプロローグで初期化され、llvm.gcrootでマークされている必要があります。

%metadata引数は、ヒープオブジェクトに'isa'ポインタやタグビットを必要としないようにするために使用できます。[Appel89、Goldberg91、Tolmach94] 指定された場合、その値はスタックフレーム内のポインタの位置とともに追跡されます。

次のJavaコードの断片を考えてみましょう

{
  Object X;   // A null-initialized reference to an object
  ...
}

このブロック（関数の途中またはループネスト内にある可能性があります）は、このLLVMコードにコンパイルできます

Entry:
   ;; In the entry block for the function, allocate the
   ;; stack space for X, which is an LLVM pointer.
   %X = alloca %Object*

   ;; Tell LLVM that the stack space is a stack root.
   ;; Java has type-tags on objects, so we pass null as metadata.
   %tmp = bitcast %Object** %X to i8**
   call void @llvm.gcroot(i8** %tmp, i8* null)
   ...

   ;; "CodeBlock" is the block corresponding to the start
   ;;  of the scope above.
CodeBlock:
   ;; Java null-initializes pointers.
   store %Object* null, %Object** %X

   ...

   ;; As the pointer goes out of scope, store a null value into
   ;; it, to indicate that the value is no longer live.
   store %Object* null, %Object** %X
   ...

ヒープ内の参照の読み書き

一部のコレクタは、ミューテータ（ガベージコレクションが必要なプログラム）がヒープオブジェクトのフィールドからポインタを読み取るか、ポインタを書き込むときに通知される必要があります。これらの時点で挿入されるコード断片は、それぞれ読み込みバリアと書き込みバリアと呼ばれます。実行する必要があるコードの量は通常非常に小さく、計算のクリティカルパス上にはないため、バリア全体の性能への影響は許容範囲内です。

バリアは、多くの場合、派生ポインタ（オブジェクト内のフィールドへのポインタ）ではなく、オブジェクトポインタへのアクセスを必要とします。したがって、これらのイントリンシックは完全を期すために両方のポインタを引数として受け取ります。このスニペットでは、%objectはオブジェクトポインタであり、%derivedは派生ポインタです。

;; An array type.
%class.Array = type { %class.Object, i32, [0 x %class.Object*] }
...

;; Load the object pointer from a gcroot.
%object = load %class.Array** %object_addr

;; Compute the derived pointer.
%derived = getelementptr %object, i32 0, i32 2, i32 %n

LLVMは、オブジェクトと派生ポインタ間のこの関係を強制しません（特定のコレクタ戦略が強制する可能性がありますが）。ただし、それを違反するコレクタは珍しいでしょう。

ターゲットGCが対応するバリアを必要としない場合、これらのイントリンシックの使用は当然オプションです。そのようなコレクタで使用されるGC戦略は、イントリンシック呼び出しを対応するloadまたはstore命令に置き換える必要があります。

現在の設計における既知の欠点の1つは、バリアイントリンシックが基礎となる操作のサイズまたはアライメントを含んでいないことです。操作はポインタサイズであると仮定され、アライメントはターゲットマシンのデフォルトアライメントであると仮定されています。

書き込みバリア：llvm.gcwrite

void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)

書き込みバリアの場合、LLVMはllvm.gcwriteイントリンシック関数を提供します。これは、派生ポインタ（3番目の引数）への非揮発性storeとまったく同じセマンティクスを持ちます。生成される正確なコードは、関数の選択されたGC戦略によって指定されます。

世代別コレクタや同時コレクタなど、多くの重要なアルゴリズムは書き込みバリアを必要とします。さらに、書き込みバリアは参照カウントを実装するために使用できます。

読み込みバリア：llvm.gcread

i8* @llvm.gcread(i8* %object, i8** %derived)

読み込みバリアの場合、LLVMはllvm.gcreadイントリンシック関数を提供します。これは、派生ポインタ（2番目の引数）からの非揮発性loadとまったく同じセマンティクスを持ちます。生成される正確なコードは、関数の選択されたGC戦略によって指定されます。

読み込みバリアは、書き込みバリアよりも少ないアルゴリズムで必要とされ、ポインタの読み取りは書き込みよりも頻繁であるため、パフォーマンスへの影響が大きくなる可能性があります。

組み込みGC戦略

LLVMには、いくつかの種類のガベージコレクタに対する組み込みサポートが含まれています。

シャドウスタックGC

このコレクタ戦略を使用するには、関数に次のマークを付けます。

F.setGC("shadow-stack");

スタックマップのコンパイルに協調的なコードジェネレータに依存する多くのGCアルゴリズムとは異なり、このアルゴリズムはスタックルートのリンクリストを慎重に維持します[Henderson2002]。このいわゆる「シャドウスタック」は、マシンスタックをミラーリングしています。このデータ構造の維持は、定数データとして実行可能ファイルにコンパイルされたスタックマップを使用するよりも遅くなりますが、ターゲットコードジェネレータからの特別なサポートを必要とせず、マシンスタックをクロールするための複雑なプラットフォーム固有のコードを必要としないため、移植性の利点が大きいです。

このシンプルさと移植性に対するトレードオフは次のとおりです。

  • 関数呼び出しあたりのオーバーヘッドが高い。

  • スレッドセーフではない。

それでも、簡単に始めることができます。コンパイラとランタイムが稼働したら、プラグインを記述することで、パフォーマンスを向上させるためにLLVMの高度なGC機能を利用できます。

シャドウスタックはメモリ割り当てアルゴリズムを暗示しません。セミスペースコレクタまたはmallocの上に構築することは、始めるのに最適な場所であり、非常に少ないコードで実装できます。

ただし、収集する際には、ランタイムがスタックルートをトラバースする必要があり、そのためにはシャドウスタックと統合する必要があります。幸いなことに、これは非常に簡単です。（このコードはデータ構造を理解するのに役立つようにコメントが豊富ですが、意味のあるコードはわずか20行です。）

/// The map for a single function's stack frame.  One of these is
///        compiled as constant data into the executable for each function.
///
/// Storage of metadata values is elided if the %metadata parameter to
/// @llvm.gcroot is null.
struct FrameMap {
  int32_t NumRoots;    //< Number of roots in stack frame.
  int32_t NumMeta;     //< Number of metadata entries.  May be < NumRoots.
  const void *Meta[0]; //< Metadata for each root.
};

/// A link in the dynamic shadow stack.  One of these is embedded in
///        the stack frame of each function on the call stack.
struct StackEntry {
  StackEntry *Next;    //< Link to next stack entry (the caller's).
  const FrameMap *Map; //< Pointer to constant FrameMap.
  void *Roots[0];      //< Stack roots (in-place array).
};

/// The head of the singly-linked list of StackEntries.  Functions push
///        and pop onto this in their prologue and epilogue.
///
/// Since there is only a global list, this technique is not threadsafe.
StackEntry *llvm_gc_root_chain;

/// Calls Visitor(root, meta) for each GC root on the stack.
///        root and meta are exactly the values passed to
///        @llvm.gcroot.
///
/// Visitor could be a function to recursively mark live objects.  Or it
/// might copy them to another heap or generation.
///
/// @param Visitor A function to invoke for every GC root on the stack.
void visitGCRoots(void (*Visitor)(void **Root, const void *Meta)) {
  for (StackEntry *R = llvm_gc_root_chain; R; R = R->Next) {
    unsigned i = 0;

    // For roots [0, NumMeta), the metadata pointer is in the FrameMap.
    for (unsigned e = R->Map->NumMeta; i != e; ++i)
      Visitor(&R->Roots[i], R->Map->Meta[i]);

    // For roots [NumMeta, NumRoots), the metadata pointer is null.
    for (unsigned e = R->Map->NumRoots; i != e; ++i)
      Visitor(&R->Roots[i], NULL);
  }
}

『Erlang』および『OCaml』GC

LLVMには、gcrootメカニズムを利用する2つの例のコレクタが付属しています。私たちの知る限り、これらは実際にはどの言語ランタイムでも使用されていませんが、gcroot互換のGCプラグインの作成に関心のある人にとって妥当な出発点となります。特に、これらはgcroot戦略を使用してカスタムバイナリスタックマップ形式を作成する方法のツリー内の唯一の例です。

名前が示すように、生成されるバイナリ形式は、それぞれErlangおよびOCamlコンパイラで使用されている形式をモデル化することを目的としています。

Statepoint例GC

F.setGC("statepoint-example");

このGCは、gc.statepointによって提供されるインフラストラクチャの使用方法の例を示しています。この例として挙げられるGCは、PlaceSafepointsおよびRewriteStatepointsForGCユーティリティパスと互換性があり、gc.statepointシーケンスの挿入を簡素化します。gc.statepointsメカニズムを中心としたカスタムGC戦略を構築する必要がある場合は、これを出発点として使用することをお勧めします。

このGC戦略は、読み取りまたは書き込みバリアをサポートしていません。そのため、これらのイントリンシックは通常のロードおよびストアにローワーされます。

このGC戦略によって生成されるスタックマップ形式は、スタックマップセクションで確認でき、その形式についてはこちらで説明されています。この形式は、今後LLVMでサポートされる標準形式となる予定です。

CoreCLR GC

F.setGC("coreclr");

このGCは、gc.statepointメカニズムを利用してCoreCLRランタイムをサポートしています。

このGC戦略のサポートは現在開発中です。この戦略は、statepoint-example GC戦略とは、以下の点で異なります。

  • 内部ポインタのベースポインタは、明示的に追跡および報告されません。

  • スタックマップのエンコードに異なる形式が使用されます。

  • セーフポイントのポーリングは、ループバックエッジとテールコールの前でのみ必要です（関数エントリでは不要です）。

カスタムGC戦略

上記の組み込みGC戦略の説明がニーズに合致しない場合は、カスタムGCStrategyと、場合によってはローワーを実行するカスタムLLVMパスを定義する必要があります。カスタムGCStrategyの定義を開始する際の最適な例は、組み込み戦略のいずれかを参照することです。

この追加コードは、ロード可能なプラグインライブラリとして構成できます。ロード可能なプラグインは、組み込み機能の異なる組み合わせを有効にするだけであれば十分ですが、カスタムローワーパスを提供する必要がある場合は、パッチを適用したバージョンのLLVMをビルドする必要があります。パッチを適用したビルドが必要と思われる場合は、llvm-devにアドバイスを求めてください。カスタムビルドを必要とせずにユースケースに対応できるサポートを簡単に拡張できる方法があるかもしれません。

コレクタ要件

以下の要素を含む既存のコレクタライブラリを活用できます。

  1. コンパイル済みコードが呼び出すことができる割り当て関数を公開するメモリアロケータ。

  2. スタックマップのバイナリ形式。スタックマップは、セーフポイントでの参照の位置を記述し、正確なコレクタがマシンスタック上のスタックフレーム内の参照を識別するために使用されます。スタックを保守的にスキャンするコレクタは、このような構造を必要としません。

  3. コールスタック上の関数を検出し、各呼び出しサイトのスタックマップにリストされている参照を列挙するスタッククロール。

  4. グローバルな場所（例：グローバル変数）の参照を識別するためのメカニズム。

  5. コレクタが必要とする場合は、コレクタのロードおよびストアバリアのLLVM IR実装。多くのコレクタはバリアをまったく必要としないため、特に指定しない限り、LLVMはデフォルトでそのようなバリアを通常のロードおよびストアにローワーします。

コレクタプラグインの実装

ユーザーコードは、gc関数属性、または同等のFunctionのsetGCメソッドを使用して、使用するGCコード生成を指定します。

GCプラグインを実装するには、llvm::GCStrategyをサブクラス化する必要があります。これは、いくつかのボイラープレートコードで実現できます。LLVMのインフラストラクチャは、いくつかの重要なアルゴリズムへのアクセスを提供します。問題のないコレクタの場合、残っているのはLLVMが計算したスタックマップをアセンブリコードにコンパイルすること（ランタイムライブラリによって期待されるバイナリ表現を使用）だけです。これは約100行のコードで実現できます。

これは、ガベージコレクションされたヒープまたはガベージコレクタ自体を実装する適切な場所ではありません。そのコードは、言語のランタイムライブラリに存在する必要があります。コンパイラプラグインは、ライブラリによって定義されたバイナリインターフェース、特にスタックマップに準拠したコードを生成する役割を担います。

llvm::GCStrategyをサブクラス化してコンパイラに登録するには

// lib/MyGC/MyGC.cpp - Example LLVM GC plugin

#include "llvm/CodeGen/GCStrategy.h"
#include "llvm/CodeGen/GCMetadata.h"
#include "llvm/Support/Compiler.h"

using namespace llvm;

namespace {
  class LLVM_LIBRARY_VISIBILITY MyGC : public GCStrategy {
  public:
    MyGC() {}
  };

  GCRegistry::Add<MyGC>
  X("mygc", "My bespoke garbage collector.");
}

このボイラープレートコレクタは何も行いません。より具体的には

  • llvm.gcread呼び出しは、対応するload命令に置き換えられます。

  • llvm.gcwrite呼び出しは、対応するstore命令に置き換えられます。

  • コードにセーフポイントは追加されません。

  • スタックマップは実行ファイルにコンパイルされません。

LLVMのMakefileを使用すると、単純なMakefileを使用してこのコードをプラグインとしてコンパイルできます。

# lib/MyGC/Makefile

LEVEL := ../..
LIBRARYNAME = MyGC
LOADABLE_MODULE = 1

include $(LEVEL)/Makefile.common

プラグインがコンパイルされた後、それを使用するコードはllc -load=MyGC.soを使用してコンパイルできます（ただし、MyGC.soにはプラットフォーム固有の拡張子が付く場合があります）。

$ cat sample.ll
define void @f() gc "mygc" {
entry:
  ret void
}
$ llvm-as < sample.ll | llc -load=MyGC.so

コレクタプラグインを言語固有のコンパイラフロントエンドなどのツールに静的にリンクすることも可能です。

利用可能な機能の概要

GCStrategyは、プラグインが有用な作業を実行するためのさまざまな機能を提供します。これらの中にはコールバックがあり、有効化、無効化、またはカスタマイズできるアルゴリズムもあります。このマトリックスは、サポートされている（および計画されている）機能を要約し、それらを通常必要とするコレクション手法と関連付けています。

アルゴリズム

完了

シャドウスタック

参照カウント

マークアンドスイープ

コピー

増分

スレッド化

並行

スタックマップ

✔

✘

✘

✘

✘

✘

ルートの初期化

✔

✘

✘

✘

✘

✘

✘

✘

派生ポインタ

NO

N*

N*

カスタムローワー

✔

gcroot

✔

✘

✘

gcwrite

✔

✘

✘

✘

gcread

✔

✘

セーフポイント

呼び出し内

✔

✘

✘

✘

✘

✘

呼び出し前

✔

✘

✘

ループ用

NO

N

N

エスケープ前

✔

✘

✘

セーフポイントでコードを生成

NO

N

N

出力

アセンブリ

✔

✘

✘

✘

✘

✘

JIT

NO

?

?

?

?

?

obj

NO

?

?

?

?

?

ライブ分析

NO

?

?

?

?

?

レジスタマップ

NO

?

?

?

?

?

* 派生ポインタは、コピーコレクションに対してのみ危険をもたらします。

？は、利用可能な場合に使用できる機能を示します。

明確にするために、上記のコレクション手法は次のように定義されています。

シャドウスタック

ミューテータは、スタックルートのリンクリストを注意深く維持します。

参照カウント

ミューテータは各オブジェクトの参照カウントを維持し、カウントがゼロになるとオブジェクトを解放します。

マークアンドスイープ

ヒープがいっぱいになると、コレクタはルートから開始して到達可能なオブジェクトをマークし、到達不可能なオブジェクトをスイープフェーズで解放します。

コピー

到達可能性分析が進むにつれて、コレクタはオブジェクトをあるヒープ領域から別のヒープ領域にコピーし、その過程で圧縮します。コピーコレクタは、非常に効率的な「バンプポインタ」割り当てを可能にし、参照の局所性を向上させることができます。

増分

（世代別コレクタを含む。）増分コレクタは、一般的にコピーコレクタのすべての特性を持っていますが（成熟ヒープが圧縮されているかどうかに関係なく）、書き込みバリアを必要とするという追加の複雑さを伴います。

スレッド化

マルチスレッドミューテータを示します。コレクタは、到達可能性分析を開始する前に、ミューテータを停止する必要があります（「ワールド停止」）。マルチスレッドミューテータの停止は複雑な問題です。一般的に、ランタイムでは高度にプラットフォーム固有のコードが必要であり、セーフポイントでは慎重に設計されたマシンコードを生成する必要があります。

並行

この手法では、ミューテータとコレクタが同時に実行され、一時停止時間を削減することを目的としています。協調型コレクタでは、一時停止が発生した場合にミューテータがさらにコレクションを支援し、コレクションがマルチプロセッサホストを活用できるようにします。スレッド化コレクタの「ワールド停止」問題は、一般的に限られた範囲で依然として存在します。高度なマーキングアルゴリズムが必要です。読み取りバリアが必要になる場合があります。

マトリックスが示すように、LLVMのガベージコレクションインフラストラクチャは、すでに幅広いコレクタに適していますが、現在ではマルチスレッドプログラムには拡張されていません。関心があれば、将来的に追加されます。

スタックマップの計算

LLVMはスタックマップを自動的に計算します。GCStrategyの最も重要な機能の1つは、この情報をランタイムライブラリによって期待されるバイナリ表現で実行ファイルにコンパイルすることです。

スタックマップは、モジュール内の各関数における各GCルートの位置と識別で構成されます。各ルートについて

  • RootNum：ルートのインデックス。

  • StackOffset：フレームポインタに対するオブジェクトのオフセット。

  • RootMetadata：@llvm.gcrootイントリンシックの%metadataパラメータとして渡される値。

また、関数全体についても

  • getFrameSize()：動的割り当てを考慮しない関数の最初のスタックフレームの全体サイズ。

    動的割り当てを考慮しません。

  • roots_size()：関数内のルートの数。

スタックマップにアクセスするには、GCMetadataPrinterからGCFunctionMetadata::roots_begin()および-end()を使用します。

for (iterator I = begin(), E = end(); I != E; ++I) {
  GCFunctionInfo *FI = *I;
  unsigned FrameSize = FI->getFrameSize();
  size_t RootCount = FI->roots_size();

  for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(),
                                      RE = FI->roots_end();
                                      RI != RE; ++RI) {
    int RootNum = RI->Num;
    int RootStackOffset = RI->StackOffset;
    Constant *RootMetadata = RI->Metadata;
  }
}

カスタムローワーパスによってコード生成前にllvm.gcrootイントリンシックが除去された場合、LLVMは空のスタックマップを計算します。これは、参照カウントまたはシャドウスタックを実装するコレクタプラグインに役立つ場合があります。

ルートのnullへの初期化

最適化器を混乱させる可能性を避けるため、フロントエンドではルートを明示的に初期化することをお勧めします。これにより、GCが初期化されていないポインタにアクセスすることが防止され、クラッシュがほぼ確実に回避されます。

フォールバックとして、LLVMは関数のエントリ時に各ルートをnullに自動的に初期化します。コード生成におけるこのモードのサポートは、主に古いコレクタ実装を動作させるためのレガシーの詳細です。

組み込み関数のカスタムローワーリング

バリアを使用するGCや、スタックルートの処理に特殊な方法を用いるGCの場合、実装者は目的のセマンティクスを持つ組み込み関数をローワーリングするためのカスタムパスを提供する責任があります。特定の組み込み関数のカスタムローワーリングを選択した場合、そのGCを選択する関数内の対応する組み込み関数のすべてのインスタンスを、**必ず**削除する必要があります。このようなパスの最適な例は、ShadowStackGCとそのShadowStackGCLoweringパスです。

現在、カスタムコピーのLLVMをビルドせずに、このようなカスタムローワーリングパスを登録する方法はありません。

セーフポイントの生成

LLVMは、スタックマップを呼び出しの戻りアドレスに関連付けるためのサポートを提供します。特定のコレクタ設計で要求されるループまたは戻りセーフポイントは、ランタイムルーチンへの呼び出し、またはパッチ可能な呼び出しシーケンスを介してモデル化できます。gcrootを使用すると、すべての呼び出し命令は可能性のあるセーフポイントと見なされ、関連付けられたスタックマップを持ちます。

アセンブリコードの出力：GCMetadataPrinter

LLVMでは、プラグインを使用して、モジュールの残りのアセンブリコードの前後に任意のアセンブリコードを出力できます。モジュールの最後に、GCはLLVMスタックマップをアセンブリコードにコンパイルします。（最初に、この情報はまだ計算されていません。）

AsmWriterとCodeGenはLLVMの別々のコンポーネントであるため、アセンブリコードを出力するための別々の抽象基本クラスとレジストリ、GCMetadaPrinterとGCMetadataPrinterRegistryが提供されています。 GCStrategyがUsesMetadataを設定した場合、AsmWriterはこのようなサブクラスを探します。

MyGC::MyGC() {
  UsesMetadata = true;
}

この分離により、JITのみのクライアントを小さくすることができます。

LLVMは現在、JITでのコード生成をサポートする同様のAPIも、オブジェクトライターを使用するAPIもありません。

// lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer

#include "llvm/CodeGen/GCMetadataPrinter.h"
#include "llvm/Support/Compiler.h"

using namespace llvm;

namespace {
  class LLVM_LIBRARY_VISIBILITY MyGCPrinter : public GCMetadataPrinter {
  public:
    virtual void beginAssembly(AsmPrinter &AP);

    virtual void finishAssembly(AsmPrinter &AP);
  };

  GCMetadataPrinterRegistry::Add<MyGCPrinter>
  X("mygc", "My bespoke garbage collector.");
}

コレクタはAsmPrinterを使用して移植可能なアセンブリコードを出力する必要があります。コレクタ自体にはモジュール全体のスタックマップが含まれており、独自のbegin()メソッドとend()メソッドを使用してGCFunctionInfoにアクセスできます。現実的な例を以下に示します。

#include "llvm/CodeGen/AsmPrinter.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/Target/TargetAsmInfo.h"
#include "llvm/Target/TargetMachine.h"

void MyGCPrinter::beginAssembly(AsmPrinter &AP) {
  // Nothing to do.
}

void MyGCPrinter::finishAssembly(AsmPrinter &AP) {
  MCStreamer &OS = AP.OutStreamer;
  unsigned IntPtrSize = AP.getPointerSize();

  // Put this in the data section.
  OS.switchSection(AP.getObjFileLowering().getDataSection());

  // For each function...
  for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {
    GCFunctionInfo &MD = **FI;

    // A compact GC layout. Emit this data structure:
    //
    // struct {
    //   int32_t PointCount;
    //   void *SafePointAddress[PointCount];
    //   int32_t StackFrameSize; // in words
    //   int32_t StackArity;
    //   int32_t LiveCount;
    //   int32_t LiveOffsets[LiveCount];
    // } __gcmap_<FUNCTIONNAME>;

    // Align to address width.
    AP.emitAlignment(IntPtrSize == 4 ? 2 : 3);

    // Emit PointCount.
    OS.AddComment("safe point count");
    AP.emitInt32(MD.size());

    // And each safe point...
    for (GCFunctionInfo::iterator PI = MD.begin(),
                                  PE = MD.end(); PI != PE; ++PI) {
      // Emit the address of the safe point.
      OS.AddComment("safe point address");
      MCSymbol *Label = PI->Label;
      AP.emitLabelPlusOffset(Label/*Hi*/, 0/*Offset*/, 4/*Size*/);
    }

    // Stack information never change in safe points! Only print info from the
    // first call-site.
    GCFunctionInfo::iterator PI = MD.begin();

    // Emit the stack frame size.
    OS.AddComment("stack frame size (in words)");
    AP.emitInt32(MD.getFrameSize() / IntPtrSize);

    // Emit stack arity, i.e. the number of stacked arguments.
    unsigned RegisteredArgs = IntPtrSize == 4 ? 5 : 6;
    unsigned StackArity = MD.getFunction().arg_size() > RegisteredArgs ?
                          MD.getFunction().arg_size() - RegisteredArgs : 0;
    OS.AddComment("stack arity");
    AP.emitInt32(StackArity);

    // Emit the number of live roots in the function.
    OS.AddComment("live root count");
    AP.emitInt32(MD.live_size(PI));

    // And for each live root...
    for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI),
                                       LE = MD.live_end(PI);
                                       LI != LE; ++LI) {
      // Emit live root's offset within the stack frame.
      OS.AddComment("stack index (offset / wordsize)");
      AP.emitInt32(LI->StackOffset);
    }
  }
}

参考文献

[Appel89] Runtime Tags Aren’t Necessary. Andrew W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.

[Goldberg91] Tag-free garbage collection for strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN PLDI’91.

[Tolmach94] Tag-free garbage collection using explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM conference on LISP and functional programming.

[Henderson2002] Accurate Garbage Collection in an Uncooperative Environment