使用 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 編譯器）。

簡介

什麼是垃圾收集？

垃圾收集是一種廣泛使用的技術，它可以將程式設計師從必須了解堆積物件的生命週期中解放出來，從而使軟體更易於生產和維護。 許多程式設計語言都依賴垃圾收集來進行自動記憶體管理。 垃圾收集主要有兩種形式：保守式和精確式。

保守式垃圾收集通常不需要來自語言或編譯器的任何特殊支援：它可以處理非型別安全的程式設計語言（例如 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 目前支援兩種不同的機制來描述安全點處編譯代碼中的參考。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 的位元轉換的值。 第二個引數包含指向應與指標關聯的中繼資料的指標，並且必須是常數或全域值位址。 如果您的目標收集器使用標籤，請使用空指標作為中繼資料。

執行手動 SSA 建構的編譯器必須確保表示 GC 參考的 SSA 值儲存到傳遞給每個呼叫站點之前的相應 gcroot 的 alloca 中，並在每次呼叫後重新載入。 使用 mem2reg 將使用 alloca 的命令式代碼提升為 SSA 形式的編譯器只需要為那些是指向 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 指令。

目前設計的一個已知缺陷是屏障內建函數不包含執行的底層操作的大小或對齊方式。 目前假設操作是指標大小，並且對齊方式假設為目標機器的預設對齊方式。

寫入屏障：llvm.gcwrite

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

對於寫入屏障，LLVM 提供了 llvm.gcwrite 內建函數。 它與對衍生指標（第三個引數）的非揮發性 store 具有完全相同的語意。 生成的確切代碼由函數的選定GC 策略指定。

許多重要的演算法都需要寫入屏障，包括分代收集器和並行收集器。 此外，寫入屏障可用於實作參考計數。

讀取屏障：llvm.gcread

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

對於讀取屏障，LLVM 提供了 llvm.gcread 內建函數。 它與從衍生指標（第二個引數）的非揮發性 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 機制的範例收集器。 據我們所知，這些實際上並未被任何語言運行時使用，但它們確實為有興趣編寫與 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 範例 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 提供了一系列功能，外掛程式可以透過這些功能執行有用的工作。其中一些是回呼，一些是可以啟用、停用或自訂的演算法。此矩陣總結了支援（和計畫中）的功能，並將它們與通常需要它們的垃圾收集技術相關聯。

演算法	完成	影子堆疊	參考計數	標記-清除	複製	增量式	多執行緒	並行
堆疊映射表	✔			✘	✘	✘	✘	✘
初始化根	✔	✘	✘	✘	✘	✘	✘	✘
衍生指標	否						否*	否*
自訂降低	✔
gcroot	✔	✘	✘
gcwrite	✔		✘			✘		✘
gcread	✔							✘
安全點
在呼叫中	✔			✘	✘	✘	✘	✘
在呼叫之前	✔						✘	✘
for 迴圈	否						否	否
在跳脫之前	✔						✘	✘
在安全點發射程式碼	否						否	否
輸出
組合語言	✔			✘	✘	✘	✘	✘
JIT	否			?	?	?	?	?
物件	否			?	?	?	?	?
即時分析	否			?	?	?	?	?
暫存器映射表	否			?	?	?	?	?
* 衍生指標僅對複製收集構成危害。
? 表示如果可用即可利用的功能。

為了清楚起見，上述的收集技術定義為

影子堆疊

Mutator 小心維護堆疊根的連結串列。

參考計數

Mutator 維護每個物件的參考計數，並在物件的計數降至零時釋放物件。

標記-清除

當堆積耗盡時，收集器從根開始標記可觸及的物件，然後在清除階段釋放不可觸及的物件。

複製

隨著可觸及性分析的進行，收集器將物件從一個堆積區域複製到另一個堆積區域，在此過程中壓縮它們。複製收集器能夠實現高效的「碰撞指標」分配，並可以提高參考的局部性。

增量式

（包括世代收集器。）增量式收集器通常具有複製收集器的所有特性（無論成熟堆積是否正在壓縮），但帶來了需要寫入屏障的額外複雜性。

多執行緒

表示多執行緒 mutator；收集器仍然必須在開始可觸及性分析之前停止 mutator（「停止世界」）。停止多執行緒 mutator 是一個複雜的問題。它通常需要在執行時期具有高度平台特定的程式碼，以及在安全點產生精心設計的機器碼。

並行

在這種技術中，mutator 和收集器並行執行，目標是消除暫停時間。在協作式收集器中，如果發生暫停，mutator 會進一步協助收集，允許收集利用多處理器主機。多執行緒收集器的「停止世界」問題通常仍然在有限程度上存在。複雜的標記演算法是必要的。可能需要讀取屏障。

正如矩陣所示，LLVM 的垃圾收集基礎架構已經適用於各種收集器，但目前尚未擴展到多執行緒程式。這將在未來有需求時添加。

計算堆疊映射表

LLVM 自動計算堆疊映射表。GCStrategy 最重要的功能之一是以執行時期函式庫預期的二進位表示法將此資訊編譯到可執行檔中。

堆疊映射表包含模組中每個函式中每個 GC 根的位置和身分。對於每個根

• RootNum：根的索引。

• StackOffset：物件相對於框架指標的偏移量。

• RootMetadata：作為 `%metadata` 參數傳遞給 `@llvm.gcroot` 內建函數的值。

此外，對於整個函式

• 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 的函式中所有對應內建函數的實例。此類傳遞的最佳範例是 ShadowStackGC 及其 ShadowStackGCLowering 傳遞。

目前沒有辦法在不建置 LLVM 自訂副本的情況下註冊此類自訂降低傳遞。

產生安全點

LLVM 提供了將堆疊映射表與呼叫的返回位址相關聯的支援。給定收集器設計所需的任何迴圈或返回安全點都可以透過呼叫執行時期常式或潛在的可修補呼叫序列來建模。使用 gcroot，所有呼叫指令都被推斷為可能的安全點，因此將具有相關聯的堆疊映射表。

發射組合語言程式碼：`GCMetadataPrinter`

LLVM 允許外掛程式在模組其餘部分的組合語言程式碼之前和之後列印任意組合語言程式碼。在模組結束時，GC 可以將 LLVM 堆疊映射表編譯為組合語言程式碼。（在開始時，此資訊尚未計算。）

由於 AsmWriter 和 CodeGen 是 LLVM 的獨立元件，因此為列印組合語言程式碼提供了單獨的抽象基底類別和註冊表，即 `GCMetadaPrinter` 和 `GCMetadataPrinterRegistry`。如果 `GCStrategy` 設定了 `UsesMetadata`，AsmWriter 將尋找這樣的子類別

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

這種分離允許僅限 JIT 的用戶端更小。

請注意，LLVM 目前沒有類似的 API 來支援 JIT 中的程式碼生成，也沒有使用物件寫入器。

// 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] Uncooperative Environment 中的精確垃圾收集