MemorySSA

簡介

MemorySSA 是一種分析，讓我們可以輕鬆推斷各種記憶體操作之間的交互作用。它的目標是取代大多數（如果不是全部）用例中的 MemoryDependenceAnalysis。這是因為，除非非常小心，否則使用 MemoryDependenceAnalysis 很容易導致 LLVM 中出現二次時間演算法。此外，MemorySSA 沒有 MemoryDependenceAnalysis 那麼多任意限制，因此您也應該獲得更好的結果。 MemorySSA 的一種常見用途是快速找出絕對不可能發生的事情（例如，推斷無法從迴圈中提升）。

在較高的層面上，MemorySSA 的目標之一是為記憶體提供基於 SSA 的形式，並提供 def-use 和 use-def 鏈，使用戶可以快速找到記憶體操作的可能定義和可能使用。它也可以被認為是一種以低成本為記憶體的完整狀態提供版本，並將記憶體操作與這些版本關聯起來的方法。

本文檔介紹了 MemorySSA 的結構，以及有關 MemorySSA 如何工作的基本概念。

關於 MemorySSA 的論文（包含有關如何在 GCC 中實作的註釋）可以在此處找到。不過，它相對過時了；該論文提到了多個記憶體分割區，但 GCC 最終改為只使用一個，就像我們現在在 LLVM 中所做的那樣。與 GCC 一樣，LLVM 的 MemorySSA 是程序內的。

MemorySSA 結構

MemorySSA 是一種虛擬 IR。建構完成後，MemorySSA 將包含一個結構，將 Instruction 對應到 MemoryAccess，這些是 MemorySSA 中與 LLVM Instruction 平行的部分。

每個 MemoryAccess 可以是以下三種類型之一

• MemoryDef

• MemoryPhi

• MemoryUse

MemoryDef 是一種可能修改記憶體，或導入某種排序限制的操作。 MemoryDef 的例子包括 store、函數呼叫、具有 acquire（或更高）排序的 load、volatile 操作、記憶體柵欄等等。 MemoryDef 總是引入整個記憶體的新版本，並與單個 MemoryDef/MemoryPhi 相連結，後者是新版本所基於的記憶體版本。這意味著存在一條連接所有 Def 的 *單一* Def 鏈，無論是直接還是間接連接。例如，在

b = MemoryDef(a)
c = MemoryDef(b)
d = MemoryDef(c)

d 直接連接到 c，並間接連接到 b。這意味著 d 可能會覆蓋（見下文） c *或* b *或* 兩者。這反過來意味著，如果不使用 The walker，則最初每個 MemoryDef 都會覆蓋所有其他 MemoryDef。

MemoryPhi 是 PhiNode，但用於記憶體操作。如果在任何時候我們有兩個（或更多）MemoryDef 可以流入 BasicBlock，則該區塊的頂部 MemoryAccess 將是一個 MemoryPhi。與 LLVM IR 中一樣，MemoryPhi 不對應於任何具體操作。因此，在 MemorySSA 內部，BasicBlock 映射到 MemoryPhi，而 Instruction 映射到 MemoryUse 和 MemoryDef。

另請注意，在 SSA 中，Phi 節點合併必須到達的定義（即 *必須* 是變數新版本的定義）。在 MemorySSA 中，PHI 節點合併可能到達的定義（也就是說，在消除歧義之前，到達 phi 節點的版本可能會也可能不會覆蓋給定變數）。

MemoryUse 是使用但不修改記憶體的操作。 MemoryUse 的一個例子是 load 或 readonly 函數呼叫。

每個存在的函數都有一個名為 liveOnEntry 的特殊 MemoryDef。它支配著正在運行 MemorySSA 的函數中的每個 MemoryAccess，並暗示我們已到達函數的頂部。它是唯一一個沒有對應到 LLVM IR 中任何 Instruction 的 MemoryDef。使用 liveOnEntry 表示正在使用的內存未定義或在函數開始之前定義。

以下是在 LLVM IR 上覆蓋所有這些內容的示例（通過在 .ll 文件上運行 opt -passes='print<memoryssa>' -disable-output 獲得）。在查看此示例時，從覆蓋的角度查看它可能會有幫助。給定 MemoryAccess 的操作數都是所述 MemoryAccess 的（潛在）覆蓋，並且 MemoryAccess 生成的值可以充當其他 MemoryAccess 的覆蓋。

如果一個 MemoryAccess 是另一個的「覆蓋」，則表示這兩個 MemoryAccess 可能訪問相同的內存。例如，x = MemoryDef(y) 表示 x 可能會修改 y 修改/約束（或已修改/約束）的內存。同樣，a = MemoryPhi({BB1,b},{BB2,c}) 表示任何使用 a 的人都可以訪問可能由 b 或 c（或兩者）修改/約束的內存。最後，MemoryUse(x) 表示此使用訪問了 x 已修改/約束的內存（例如，假設 x = MemoryDef(...) 和 MemoryUse(x) 在同一個循環中，則不能單獨將使用提升到循環外）。

查看它的另一個有用方法是從內存版本的角度。在該視圖中，給定 MemoryAccess 的操作數是操作之前整個內存的版本，如果訪問產生一個值（即 MemoryDef/MemoryPhi），則該值是操作之後內存的新版本。

define void @foo() {
entry:
  %p1 = alloca i8
  %p2 = alloca i8
  %p3 = alloca i8
  ; 1 = MemoryDef(liveOnEntry)
  store i8 0, ptr %p3
  br label %while.cond

while.cond:
  ; 6 = MemoryPhi({entry,1},{if.end,4})
  br i1 undef, label %if.then, label %if.else

if.then:
  ; 2 = MemoryDef(6)
  store i8 0, ptr %p1
  br label %if.end

if.else:
  ; 3 = MemoryDef(6)
  store i8 1, ptr %p2
  br label %if.end

if.end:
  ; 5 = MemoryPhi({if.then,2},{if.else,3})
  ; MemoryUse(5)
  %1 = load i8, ptr %p1
  ; 4 = MemoryDef(5)
  store i8 2, ptr %p2
  ; MemoryUse(1)
  %2 = load i8, ptr %p3
  br label %while.cond
}

「MemorySSA」IR 會顯示在對應指令之前的註解中（如果存在對應指令的話）。舉例來說，1 = MemoryDef(liveOnEntry) 是一個 MemoryAccess（具體來說是一個 MemoryDef），它描述了 LLVM 指令 store i8 0, ptr %p3。在 MemorySSA 中的其他地方會以 1 來表示這個特定的 MemoryDef（就像在 LLVM 中可以使用 %1 來表示 load i8, ptr %p1 一樣）。同樣地，MemoryPhi 並不對應到任何 LLVM 指令，因此 MemoryPhi 下方的程式碼行並無特殊意義。

由上而下：

• 6 = MemoryPhi({entry,1},{if.end,4}) 表示當進入 while.cond 時，其可達定義為 1 或 4。在文字 IR 中，這個 MemoryPhi 以數字 6 表示。

• 2 = MemoryDef(6) 表示 store i8 0, ptr %p1 是一個定義，而其可達定義為 6，也就是 while.cond 之後的 MemoryPhi。（關於為什麼此 MemoryDef 沒有連結到一個獨立的、明確的 MemoryPhi，請參閱下面的「使用與定義最佳化」和「精確度」章節。）

• 3 = MemoryDef(6) 表示 store i8 0, ptr %p2 是一個定義，而其可達定義也是 6。

• 5 = MemoryPhi({if.then,2},{if.else,3}) 表示此區塊之前的覆蓋可能是 2 或 3。

• MemoryUse(5) 表示 load i8, ptr %p1 是記憶體的使用，並且它被 5 覆蓋。

• 4 = MemoryDef(5) 表示 store i8 2, ptr %p2 是一個定義，而其可達定義為 5。

• MemoryUse(1) 指出 load i8, ptr %p3 只是記憶體的一個使用者，而最後可能破壞此使用者的指令是在 while.cond 之前（例如，對 %p3 的存放）。用記憶體版本控制的術語來說，它實際上只依賴於記憶體版本 1，並且不受之後產生的新記憶體版本的影響。

順帶一提，MemoryAccess 作為一個 Value 主要為了方便；它不打算與 LLVM IR 交互。

MemorySSA 的設計

MemorySSA 是一種可以為任何任意函數建立的分析。當它被建立時，它會遍歷函數的 IR 以建立其 MemoryAccess 的映射。然後，您可以查詢 MemorySSA 以獲取諸如 MemoryAccess 之間的支配關係之類的信息，並獲取任何給定 Instruction 的 MemoryAccess 。

當 MemorySSA 建立完成後，它還會向您傳遞一個 MemorySSAWalker 供您使用（見下文）。

漫遊器

幫助 MemorySSA 完成工作的結構是 MemorySSAWalker，或簡稱為漫遊器。漫遊器的目標是為超出 MemoryAccess 直接表示的內容提供關於覆蓋查詢的答案。例如，給定

define void @foo() {
  %a = alloca i8
  %b = alloca i8

  ; 1 = MemoryDef(liveOnEntry)
  store i8 0, ptr %a
  ; 2 = MemoryDef(1)
  store i8 0, ptr %b
}

對 %a 的存放顯然不會覆蓋對 %b 的存放。漫遊器的目標是找出這一點，並在查詢 MemoryAccess 2 的覆蓋時返回 liveOnEntry 。

預設情況下，MemorySSA 提供了一個漫遊器，它可以通過查詢您碰巧正在使用的任何別名分析堆棧來優化 MemoryDef 和 MemoryUse。然而，漫遊器的設計非常靈活，因此創建更專門的漫遊器是完全合理（也是預期的）（例如，一個專門查詢 GlobalsAA 的漫遊器，一個總是在 MemoryPhi 節點停止的漫遊器，等等）。

預設漫遊器 API

有兩個主要 API 用於使用漫遊器檢索覆蓋訪問

• MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA); 返回 MA 的覆蓋記憶體訪問，將沿途計算的所有中間結果作為每個查詢訪問的一部分進行緩存。

• MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, const MemoryLocation &Loc); 會回傳覆蓋記憶體位置 Loc 的存取，從 MA 開始。因為這個 API 並沒有要求特定記憶體存取的覆蓋存取，所以沒有可以被快取的結果。

自行定位覆蓋

如果您選擇自行建立 walker，您可以藉由走訪每個支配該 MemoryAccess 的 MemoryDef 來找到 MemoryAccess 的覆蓋。 MemoryDef 的結構讓這件事相對簡單；它們最終會形成一個連結串列，包含每個支配您嘗試最佳化的 MemoryAccess 的覆蓋。換句話說，MemoryDef 的 definingAccess 永遠是該 MemoryDef 最近的支配 MemoryDef 或 MemoryPhi。

使用與定義最佳化

MemoryUse 會保留一個運算元，也就是它們的定義或最佳化存取。傳統上，MemorySSA 會在建構時最佳化 MemoryUse，直到達到給定的閾值。具體來說，每個 MemoryUse 的運算元都會被最佳化，指向該 MemoryUse 的實際覆蓋。這可以從上面的例子中看出；if.end 中的第二個 MemoryUse 有一個運算元 1，它是來自 entry 區塊的 MemoryDef。這樣做的目的是為了讓走訪、值編號等操作更快更容易。從 這個修訂 開始，預設值已更改為不在建構時最佳化使用，以便在 pass 中不需要走訪時提供減少編譯時間的選項。建議大多數使用者呼叫新的 API ensureOptimizedUses() 來保留先前的行為，並對 MemoryUse 進行一次性最佳化（如果之前沒有這樣做）。建議新的 pass 使用者呼叫 ensureOptimizedUses()。

最初，無法以同樣的方式優化 MemoryDef，因為我們將 MemorySSA 限制為每次存取一個運算元。這已更改，現在 MemoryDef 保留兩個運算元。第一個是定義存取，始終是同一個基本區塊中的前一個 MemoryDef 或 MemoryPhi，或者如果當前區塊沒有任何其他寫入記憶體的存取，則為支配前任中的最後一個。這是走訪 Def 鏈所需的。第二個運算元是經過優化的存取，如果先前在 walker 的 getClobberingMemoryAccess(MA) 上有呼叫的話。這個 API 會將資訊快取為 MA 的一部分。優化所有 MemoryDef 具有平方時間複雜度，預設情況下不會執行。

走訪任何 MemoryDef 的使用可以找到已優化到它的存取。這種走訪的程式碼片段如下所示

MemoryDef *Def;  // find who's optimized or defining for this MemoryDef
for (auto &U : Def->uses()) {
  MemoryAccess *MA = cast<MemoryAccess>(U.getUser());
  if (auto *DefUser = dyn_cast<MemoryDef>(MA))
    if (DefUser->isOptimized() && DefUser->getOptimized() == Def) {
      // User who is optimized to Def
    } else {
      // User who's defining access is Def; optimized to something else or not optimized.
    }
}

當 MemoryUse 被優化時，對於給定的存放，您可以透過走訪存放的直接和遞移使用來找到被該存放覆蓋的所有載入。

checkUses(MemoryAccess *Def) { // Def can be a MemoryDef or a MemoryPhi.
  for (auto &U : Def->uses()) {
    MemoryAccess *MA = cast<MemoryAccess>(U.getUser());
    if (auto *MU = dyn_cast<MemoryUse>(MA)) {
      // Process MemoryUse as needed.
    } else {
      // Process MemoryDef or MemoryPhi as needed.

      // As a user can come up twice, as an optimized access and defining
      // access, keep a visited list.

      // Check transitive uses as needed
      checkUses(MA); // use a worklist for an iterative algorithm
    }
  }
}

可以在 DeadStoreElimination pass 中找到類似走訪的範例。

失效和更新

因為 MemorySSA 會追蹤 LLVM IR，所以只要 IR 更新就需要更新它。在這種情況下，「更新」包括 Instructions 的新增、刪除和移動。更新 API 正在按需製作。如果您想要範例，GVNHoist 和 LICM 是 MemorySSA 更新 API 的使用者。請注意，新增新的 MemoryDef（透過呼叫 insertDef）可能會是一個耗時的更新，如果新的存取觸發許多 MemoryPhi 插入和許多 MemoryAccesses 的重新命名（優化失效）。

Phi 放置

MemorySSA 只在實際需要的地方放置 MemoryPhi。也就是說，它是一種經過修剪的 SSA 形式，就像 LLVM 的 SSA 形式一樣。例如，考慮

define void @foo() {
entry:
  %p1 = alloca i8
  %p2 = alloca i8
  %p3 = alloca i8
  ; 1 = MemoryDef(liveOnEntry)
  store i8 0, ptr %p3
  br label %while.cond

while.cond:
  ; 3 = MemoryPhi({%0,1},{if.end,2})
  br i1 undef, label %if.then, label %if.else

if.then:
  br label %if.end

if.else:
  br label %if.end

if.end:
  ; MemoryUse(1)
  %1 = load i8, ptr %p1
  ; 2 = MemoryDef(3)
  store i8 2, ptr %p2
  ; MemoryUse(1)
  %2 = load i8, ptr %p3
  br label %while.cond
}

因為我們從 if.then 和 if.else 中刪除了存放，所以 if.end 的 MemoryPhi 將毫無意義，因此我們不放置它。因此，如果您需要在 if.then 或 if.else 中放置 MemoryDef，您還需要為 if.end 建立一個 MemoryPhi。

如果事實證明這是一個沉重的負擔，我們可以只在任何地方放置 MemoryPhi。因為我們有能夠優化上述 phi 的 Walker，所以這樣做不應該禁止優化。

非目標

MemorySSA 用於推理記憶體操作之間的關係，並啟用更快的查詢。 它並非所有潛在記憶體相關優化的單一準確來源。 具體來說，在嘗試使用 MemorySSA 推理原子或易失性操作時必須小心，例如

define i8 @foo(ptr %a) {
entry:
  br i1 undef, label %if.then, label %if.end

if.then:
  ; 1 = MemoryDef(liveOnEntry)
  %0 = load volatile i8, ptr %a
  br label %if.end

if.end:
  %av = phi i8 [0, %entry], [%0, %if.then]
  ret i8 %av
}

僅根據 MemorySSA 的分析，將 load 提升到 entry 可能看起來是合法的。 但是，因為它是易失性加載，所以並非如此。

設計上的取捨

精確度

LLVM 中的 MemorySSA 故意犧牲精確度來換取速度。 讓我們將記憶體變數想像成記憶體的不相交分區（也就是說，如果您有一個如上所述的變數，它代表整個記憶體，如果您有多個變數，則每個變數代表記憶體的某些不相交部分）

首先，因為別名分析結果彼此衝突，並且每個結果都可能是分析想要的（例如 TBAA 可能說無別名，而其他東西可能說必須別名），所以不可能以每個優化想要的方式對記憶體進行分區。 其次，一些別名分析結果不可傳遞（例如 A 無別名 B，B 無別名 C，並不意味著 A 無別名 C），因此在沒有變數來表示每對可能別名的情況下，不可能在所有情況下都提出精確的分區。 因此，精確分區可能需要引入至少 N^2 個新的虛擬變數、phi 節點等。

這些變數中的每一個都可能在多個定義位置被覆蓋。

舉個例子，如果您要將結構欄位拆分為單獨的變數，則所有可能定義多個結構欄位的別名操作都將可能定義其中多個欄位。 這很常見（調用、複製、欄位存儲等）。

其他編譯器中記憶體 SSA 形式的經驗表明，根本不可能精確地做到這一點，事實上，精確地做到這一點是不值得的，因為現在所有優化都必須遍歷大量的虛擬變數和 phi 節點。

所以我們進行分區。 在您進行分區的時候，經驗再次告訴我們，分區到多個變數是沒有意義的。 它只會生成更多的 IR，並且優化仍然需要查詢某些東西來進一步消除歧義。

因此，LLVM 分區為一個變數。

實際的精確度

在實際操作中，LLVM 中的一些實現細節也會影響 MemorySSA 所提供結果的精度。例如，AliasAnalysis 有各種限制，或者對 phi 節點的查找限制，這些都會影響 MemorySSA 的推斷能力。不同 pass 所做的更改可能會使 MemorySSA「過度優化」（它可以提供比從頭開始重新計算更準確的結果），或者「優化不足」（如果重新計算，它可以推斷出更多資訊）。當結果依賴於 MemorySSA 透過多個後續 pass 更新後獲得的狀態時，這可能會導致在單個 pass 中單獨重現結果的挑戰。使用和更新 MemorySSA 的 pass 應該透過 MemorySSAUpdater 提供的 API 或透過 Walker 上的呼叫來進行。不允許直接對 MemorySSA 進行優化。目前有一個範圍狹窄的例外，即 DSE（DeadStoreElimination）在保證優化正確的遍歷之後更新 store 的優化訪問。允許這樣做的唯一原因是遍歷和推斷超出了 MemorySSA 所做的工作，而且它們是「免費的」（即 DSE 無論如何都會執行它們）。此例外設置在一個標誌（“-dse-optimize-memoryssa”）下，並且可以禁用以幫助單獨重現優化。

LLVM 開發者會議簡報

• 2016 LLVM 開發者會議：G. Burgess - MemorySSA 五分鐘速成.

• 2020 LLVM 開發者會議：S. Baziotis & S. Moll - 在 LLVM 相依性分析工具中找到方向