MemorySSA

簡介

MemorySSA 是一種分析，讓我們能夠以低成本推斷各種記憶體操作之間的互動關係。其目標是在大多數（如果不是全部）使用案例中取代 MemoryDependenceAnalysis。這是因為，除非您非常小心，否則使用 MemoryDependenceAnalysis 很容易在 LLVM 中導致平方時間複雜度的演算法。此外，MemorySSA 沒有像 MemoryDependenceAnalysis 那樣多的任意限制，因此您應該也能獲得更好的結果。MemorySSA 的一個常見用途是快速找出某件事絕對不可能發生（例如，推斷出迴圈外提前載入是不可能發生的）。

在高層次上，MemorySSA 的目標之一是為記憶體提供基於 SSA 形式的表示法，並配備定義-使用和使用-定義鏈，這使使用者能夠快速找到記憶體操作的可能定義和可能使用。它也可以被認為是一種以低成本為記憶體的完整狀態賦予版本，並將記憶體操作與這些版本相關聯的方法。

本文檔概述了 MemorySSA 的結構，以及關於 MemorySSA 如何運作的一些基本直覺。

一篇關於 MemorySSA 的論文（附帶關於它如何在 GCC 中實作的註釋）可以在這裡找到。雖然，它相對過時了；該論文參考了多個記憶體分割區，但 GCC 最終切換到僅使用一個，就像我們現在在 LLVM 中所擁有的那樣。與 GCC 的一樣，LLVM 的 MemorySSA 是程序內 (intraprocedural) 的。

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 或 兩者。這反過來意味著，在不使用 遍歷器 的情況下，最初每個 MemoryDef 都會與每個其他 MemoryDef 衝突。

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

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

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

每個存在的函數都有一個特殊的 MemoryDef 稱為 liveOnEntry。它支配著正在執行 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 中的其他位置將此特定的 MemoryDef 稱為 1（很像人們可以使用 %1 在 LLVM 中引用 load i8, ptr %p1 的方式）。再次強調，MemoryPhi 不對應於任何 LLVM 指令，因此 MemoryPhi 正下方的行沒有任何特殊之處。

從上到下看

• 6 = MemoryPhi({entry,1},{if.end,4}) 註解，當進入 while.cond 時，到達它的定義是 1 或 4。這個 MemoryPhi 在文字 IR 中以數字 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); 返回從 MA 開始衝突記憶體位置 Loc 的存取。由於此 API 不請求特定記憶體存取的衝突存取，因此沒有可以快取的結果。

自行定位衝突

如果您選擇製作自己的遍歷器，您可以透過遍歷支配所述 MemoryAccess 的每個 MemoryDef 來找到 MemoryAccess 的衝突。MemoryDef 的結構使這相對簡單；它們最終形成一個連結列表，其中包含支配您要最佳化的 MemoryAccess 的每個衝突。換句話說，MemoryDef 的 definingAccess 始終是所述 MemoryDef 的最近支配的 MemoryDef 或 MemoryPhi。

使用與定義最佳化

MemoryUse 保留單個運算元，這是它們的定義或最佳化存取。傳統上，MemorySSA 在建構時最佳化 MemoryUse，直到給定的閾值。具體來說，每個 MemoryUse 的運算元都被最佳化為指向所述 MemoryUse 的實際衝突。這可以在上面的範例中看到；if.end 中的第二個 MemoryUse 的運算元為 1，這是來自入口區塊的 MemoryDef。這樣做是為了使遍歷、值編號等更快更輕鬆。截至 此修訂版，預設設定已更改為不在建構時最佳化使用，以便在傳遞中不需要遍歷時提供減少編譯時間的選項。大多數使用者調用新的 API ensureOptimizedUses() 以保持先前的行為並對 MemoryUse 執行一次性最佳化，如果之前沒有執行此操作。建議新的傳遞使用者調用 ensureOptimizedUses()。

最初，無法以相同的方式最佳化 MemoryDef，因為我們將 MemorySSA 限制為每個存取一個運算元。這種情況已經改變，MemoryDef 現在保留兩個運算元。第一個運算元，即定義存取，始終是同一個基本區塊中先前的 MemoryDef 或 MemoryPhi，或者如果當前區塊沒有任何其他寫入記憶體的存取，則為支配前導中的最後一個。這是遍歷 Def 鏈所需要的。第二個運算元是最佳化存取，如果之前調用過遍歷器的 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 傳遞中找到。

失效與更新

由於 MemorySSA 追蹤 LLVM IR，因此每當 IR 更新時，都需要更新它。在這種情況下，「更新」包括 Instruction 的新增、刪除和移動。更新 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 節點之上最佳化的遍歷器，因此這樣做不應禁止最佳化。

非目標

MemorySSA 旨在推斷記憶體操作之間的關係，並實現更快的查詢。它並非旨在成為所有潛在記憶體相關最佳化的單一事實來源。具體來說，當嘗試使用 MemorySSA 推斷原子或 volatile 操作時，必須謹慎，如下所示

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 可能看起來是合法的。但是，由於它是 volatile 載入，因此它不是。

設計權衡

精確度

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

首先，由於別名分析結果彼此衝突，並且每個結果都可能是分析想要的結果（即 TBAA 可能會說 no-alias，而其他一些可能會說 must-alias），因此無法以每個最佳化都想要的方式分割記憶體。其次，某些別名分析結果不是可傳遞的（即 A noalias B，B noalias C，並不意味著 A noalias C），因此在所有情況下都無法提出精確的分割區，而無需變數來表示每對可能的別名。因此，精確分割可能需要引入至少 N^2 個新的虛擬變數、phi 節點等。

這些變數中的每一個都可能在多個定義站點被衝突。

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

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

因此我們進行分割。在您進行分割的點上，經驗再次告訴我們，分割成多於一個變數是沒有意義的。它只會產生更多 IR，並且最佳化仍然需要查詢某些內容以進一步消除歧義。

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

實務中的精確度

實際上，LLVM 中的實作細節也會影響 MemorySSA 提供的結果的精確度。例如，AliasAnalysis 有各種上限或對查看 phi 節點的限制，這可能會影響 MemorySSA 可以推斷的內容。不同傳遞所做的更改可能會使 MemorySSA 要么「過度最佳化」（它可以提供比從頭開始重新計算更準確的結果），要么「最佳化不足」（如果重新計算，它可以推斷更多）。當結果依賴於 MemorySSA 由於被多個後續傳遞更新而獲得的狀態時，這可能會導致在單個傳遞中隔離重現結果的挑戰。使用和更新 MemorySSA 的傳遞應透過 MemorySSAUpdater 提供的 API 或透過調用 Walker 來完成。不允許直接最佳化 MemorySSA。目前有一個範圍狹窄的例外，其中 DSE (DeadStoreElimination) 在遍歷後更新儲存的最佳化存取，該遍歷保證最佳化是正確的。這僅僅是因為遍歷和推斷超出了 MemorySSA 的範圍，並且它們是「免費的」（即 DSE 無論如何都會執行它們）。此例外設定在一個標誌（「-dse-optimize-memoryssa」）下，並且可以禁用以幫助隔離重現最佳化。

LLVM 開發者會議簡報

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

• 2020 LLVM 開發者會議：S. Baziotis & S. Moll - 探索 LLVM 依賴分析動物園