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 策略的基礎上）。從長遠來看，我們可能會完全遷移 away from llvm.gcroot，或者將它們的實現大幅合併。請注意，大多數新的開發工作都集中在 gc.statepoint 上。

使用 gc.statepoint

此頁面 包含 gc.statepoint 的詳細文檔。

使用 llvm.gcwrite

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

llvm.gcroot intrinsic 用於通知 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 與簡化 gc.statepoint 序列插入的 PlaceSafepoints 和 RewriteStatepointsForGC 實用程序傳遞兼容。 如果您需要圍繞 gc.statepoints 機制構建自定義 GC 策略，建議您以此策略為起點。

此 GC 策略不支持讀取或寫入屏障。 因此，這些內建函數會被降低為普通的加載和存儲。

此 GC 策略生成的堆棧映射格式可以在 堆棧映射區段 中找到，使用的格式記錄在 此處。 此格式旨在成為 LLVM 未來支持的標準格式。

CoreCLR GC

F.setGC("coreclr");

此 GC 利用 gc.statepoint 機制來支持 CoreCLR 運行時。

對此 GC 策略的支持正在進行中。 此策略在某些方面將不同於 statepoint-example GC 策略，例如

• 不會明確追蹤及回報內部指標的基底指標。

• 使用不同的格式來編碼堆疊映射圖。

• 僅在迴圈返回邊緣和尾端呼叫之前需要安全點輪詢（函數進入時不需要）。

自訂 GC 策略

如果以上內建的 GC 策略描述都不符合您的需求，您將需要定義自訂的 GCStrategy，並且可能需要自訂 LLVM Pass 來執行降級。若要開始定義自訂 GCStrategy，最佳範例是參考其中一個內建策略。

您可以將此額外程式碼建構為可載入的插件庫。如果您只需要啟用不同的內建功能組合，則可載入的插件就足夠了，但如果您需要提供自訂的降級 Pass，則需要建置 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 提供了一系列功能，插件可以透過這些功能進行有用的工作。其中一些是回調函數，一些是可以啟用、禁用或自訂的演算法。此矩陣總結了支援的（和計劃中的）功能，並將它們與通常需要它們的收集技術相關聯。

演算法	完成	影子堆疊	引用計數	標記清除	複製	增量	線程化	併發
堆疊映射圖	✔			✘	✘	✘	✘	✘
初始化根	✔	✘	✘	✘	✘	✘	✘	✘
衍生指標	否						N*	N*
自訂降低	✔
gcroot	✔	✘	✘
gcwrite	✔		✘			✘		✘
gcread	✔							✘
安全點
在呼叫中	✔			✘	✘	✘	✘	✘
在呼叫前	✔						✘	✘
迴圈	否						N	N
在跳出前	✔						✘	✘
在安全點發出程式碼	否						N	N
輸出
組合語言	✔			✘	✘	✘	✘	✘
JIT	否			?	?	?	?	?
obj	否			?	?	?	?	?
活躍度分析	否			?	?	?	?	?
暫存器映射圖	否			?	?	?	?	?
* 衍生指標只對複製收集構成危害。
? 表示如果可用的話，可以使用該功能。

為清楚起見，上述收集技術的定義如下：

影子堆疊

修改器會仔細維護一個堆疊根的鏈結串列。

引用計數

修改器會為每個物件維護一個引用計數，並在物件的計數降至零時釋放該物件。

標記清除

當堆積空間不足時，收集器會從根開始標記可到達的物件，然後在清除階段釋放不可到達的物件。

複製

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

增量

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

線程化

表示一個多線程修改器；收集器在開始可到達性分析之前仍然必須停止修改器（「停止世界」）。停止多線程修改器是一個複雜的問題。它通常需要在執行階段使用高度平台特定的程式碼，並在安全點產生精心設計的機器碼。

併發

在這種技術中，修改器和收集器同時執行，目標是消除暫停時間。在*合作*收集器中，修改器會在發生暫停時進一步協助收集，允許收集利用多處理器主機的優勢。線程化收集器的「停止世界」問題通常在一定程度上仍然存在。需要複雜的標記演算法。可能需要讀取屏障。

如矩陣所示，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] 運行時標籤不是必需的。Andrew W. Appel。Lisp 和符號計算 19(7):703-705，1989 年 7 月。

[Goldberg91] 強類型程式語言的無標籤垃圾回收。Benjamin Goldberg。ACM SIGPLAN PLDI'91。

[Tolmach94] 使用顯式類型參數的無標籤垃圾回收。Andrew Tolmach。1994 年 ACM LISP 和函數式程式設計會議論文集。

[Henderson2002] 非合作環境中的準確垃圾回收