MemorySSA

简介

MemorySSA 是一种分析，它允许我们廉价地推理各种内存操作之间的交互。它的目标是取代 MemoryDependenceAnalysis 用于大多数（如果不是全部）用例。这是因为，除非您非常小心，否则使用 MemoryDependenceAnalysis 很容易导致 LLVM 中的二次时间复杂度算法。此外，MemorySSA 没有像 MemoryDependenceAnalysis 那样多的任意限制，因此您应该获得更好的结果。 MemorySSA 的一个常见用途是快速找出某些事情绝对不可能发生（例如，推断出循环外提无法发生）。

在高层次上，MemorySSA 的目标之一是为内存提供基于 SSA 的形式，完成 def-use 和 use-def 链，这使使用者能够快速找到内存操作的 may-def 和 may-use。它也可以被认为是廉价地为内存的完整状态赋予版本，并将内存操作与这些版本关联的一种方式。

本文档介绍了 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或两者。这反过来意味着，在不使用 walker（遍历器） 的情况下，最初每个 MemoryDef 都会覆写每个其他 MemoryDef。

MemoryPhi 是 PhiNode，但用于内存操作。如果在任何时候我们有两个（或更多）MemoryDef 可能流入一个 BasicBlock，则该块的顶部 MemoryAccess 将是一个 MemoryPhi。与 LLVM IR 中一样，MemoryPhi 不对应于任何具体操作。因此，BasicBlock 在 MemorySSA 内部映射到 MemoryPhi，而 Instruction 映射到 MemoryUse 和 MemoryDef。

另请注意，在 SSA 中，Phi 节点合并 must-reach 定义（即，必须是变量新版本的定义）。在 MemorySSA 中，PHI 节点合并 may-reach 定义（即，在消除歧义之前，到达 phi 节点的版本可能或可能不覆写给定的变量）。

MemoryUse 是使用但不修改内存的操作。MemoryUse 的一个示例是 load 或 readonly 函数调用。

每个存在的函数都有一个特殊的 MemoryDef，称为 liveOnEntry。它支配着 MemorySSA 正在其上运行的函数中的每个 MemoryAccess，并暗示我们已到达函数的顶部。它是唯一不映射到 LLVM IR 中任何 Instruction 的 MemoryDef。liveOnEntry 的使用意味着正在使用的内存是未定义的或在函数开始之前定义的。

所有这些都覆盖在 LLVM IR 上的一个示例（通过在 .ll 文件上运行 opt -passes='print<memoryssa>' -disable-output 获得）如下所示。查看此示例时，以 clobber（覆写）的角度查看可能很有帮助。给定 MemoryAccess 的操作数是所述 MemoryAccess 的所有（潜在）clobber，并且 MemoryAccess 产生的值可以充当其他 MemoryAccess 的 clobber。

如果 MemoryAccess 是另一个的 clobber，则意味着这两个 MemoryAccess 可能会访问相同的内存。例如，x = MemoryDef(y) 意味着 x 可能会修改 y 修改/约束（或已经修改/约束）的内存。同样，a = MemoryPhi({BB1,b},{BB2,c}) 意味着任何使用 a 的人都可能访问由 b 或 c（或两者）修改/约束的内存。最后，MemoryUse(x) 意味着此 use 访问 x 已修改/约束的内存（例如，考虑如果 x = MemoryDef(...) 和 MemoryUse(x) 在同一循环中，则 use 不能单独外提）。

另一种有用的看待方式是内存版本。在该视图中，给定 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（很像在 LLVM 中可以使用 %1 来引用 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。（请参阅下面的 Use 和 Def 优化 和 精度 部分，了解为什么此 MemoryDef 未链接到单独的、消除歧义的 MemoryPhi。）

• 3 = MemoryDef(6) 注释到 store i8 0, ptr %p2 是一个定义；它的到达定义也是 6。

• 5 = MemoryPhi({if.then,2},{if.else,3}) 注释到此块之前的 clobber 可能是 2 或 3。

• MemoryUse(5) 注释到 load i8, ptr %p1 是内存的使用，并且它被 5 clobber。

• 4 = MemoryDef(5) 注释到 store i8 2, ptr %p2 是一个定义；它的到达定义是 5。

• MemoryUse(1) 注释到 load i8, ptr %p3 只是内存的使用者，并且可能 clobber 此 use 的最后一件事是在 while.cond 之上（例如，store 到 %p3）。在内存版本控制术语中，它实际上仅取决于内存版本 1，并且不受此后生成的新内存版本的影响。

顺便说一句，MemoryAccess 主要为了方便起见是一个 Value；它并非旨在与 LLVM IR 交互。

MemorySSA 的设计

MemorySSA 是一种可以为任何任意函数构建的分析。构建时，它会对函数的 IR 进行一次遍历，以便构建其 MemoryAccess 的映射。然后，您可以查询 MemorySSA 以获取诸如 MemoryAccess 之间的支配关系之类的信息，并获取任何给定 Instruction 的 MemoryAccess。

当 MemorySSA 完成构建时，它还会向您提供一个 MemorySSAWalker，您可以使用它（见下文）。

walker（遍历器）

帮助 MemorySSA 完成其工作的一个结构是 MemorySSAWalker，或简称 walker（遍历器）。walker（遍历器）的目标是提供超出 MemoryAccess 直接表示的 clobber（覆写）查询的答案。例如，给定

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 的 store 显然不是对 %b 的 store 的 clobber（覆写）。walker（遍历器）的目标是弄清楚这一点，并在查询 MemoryAccess 2 的 clobber（覆写）时返回 liveOnEntry。

默认情况下，MemorySSA 提供了一个 walker（遍历器），可以通过查阅您碰巧正在使用的任何别名分析堆栈来优化 MemoryDef 和 MemoryUse。但是，walker（遍历器）构建为具有灵活性，因此创建更专业的 walker（遍历器）（例如，专门查询 GlobalsAA 的 walker（遍历器），始终在 MemoryPhi 节点处停止的 walker（遍历器）等）完全合理（并且是预期的）。

默认 walker API

有两个主要的 API 用于使用 walker（遍历器）检索 clobber（覆写）访问

• MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA); 返回 MA 的 clobber（覆写）内存访问，缓存沿途计算的所有中间结果，作为每个查询的访问的一部分。

• MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, const MemoryLocation &Loc); 返回 clobber（覆写）内存位置 Loc 的访问，从 MA 开始。由于此 API 不请求特定内存访问的 clobber（覆写）访问，因此没有可以缓存的结果。

自行定位 clobber（覆写）

如果您选择制作自己的 walker（遍历器），则可以通过遍历支配所述 MemoryAccess 的每个 MemoryDef 来找到 MemoryAccess 的 clobber（覆写）。MemoryDef 的结构使这相对简单；它们最终形成一个链接列表，其中包含支配您尝试优化的 MemoryAccess 的每个 clobber（覆写）。换句话说，MemoryDef 的 definingAccess 始终是所述 MemoryDef 的最近支配的 MemoryDef 或 MemoryPhi。

Use 和 Def 优化

MemoryUse 保留一个操作数，即它们的定义或优化访问。传统上，MemorySSA 在构建时优化 MemoryUse，直到给定的阈值。具体来说，每个 MemoryUse 的操作数都经过优化，以指向所述 MemoryUse 的实际 clobber（覆写）。这可以在上面的示例中看到；if.end 中的第二个 MemoryUse 的操作数为 1，它是来自入口块的 MemoryDef。这样做是为了使 walker（遍历器）、值编号等更快、更轻松。截至 此修订版，默认设置已更改为不在构建时优化 use，以便在 pass 中不需要 walker（遍历器）时提供减少编译时间的选项。大多数用户调用新的 API ensureOptimizedUses() 以保持先前的行为，并对 MemoryUse 进行一次性优化（如果之前未完成此操作）。建议新的 pass 用户调用 ensureOptimizedUses()。

最初，不可能以相同的方式优化 MemoryDef，因为我们将 MemorySSA 限制为每个访问一个操作数。这种情况已经改变，MemoryDef 现在保留两个操作数。第一个操作数，即定义访问，始终是同一基本块中的前一个 MemoryDef 或 MemoryPhi，或者如果当前块没有任何其他写入内存的访问，则是支配前驱中的最后一个。Def 链的 walker（遍历器）需要这样做。第二个操作数是优化的访问，如果之前调用过 walker（遍历器）的 getClobberingMemoryAccess(MA)。此 API 将缓存信息作为 MA 的一部分。优化所有 MemoryDef 具有二次时间复杂度，并且默认情况下不执行。

遍历任何 MemoryDef 的 use 可以找到优化到它的访问。此类遍历的代码片段如下所示

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 优化后，对于给定的 store，您可以通过遍历 store 的直接和传递 use 来找到由该 store clobber（覆写）的所有 load。

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 更新时都需要更新。“更新”在这种情况下包括 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 中删除了 store，因此 if.end 的 MemoryPhi 将毫无意义，因此我们不放置一个。因此，如果您需要在 if.then 或 if.else 中放置 MemoryDef，您还需要为 if.end 创建一个 MemoryPhi。

如果事实证明这是一个很大的负担，我们可以只在任何地方放置 MemoryPhi。因为我们有能够优化上述 phi 的 walker（遍历器），所以这样做不应禁止优化。

非目标

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 load，因此不是。

设计权衡

精度

LLVM 中的 MemorySSA 故意牺牲精度以换取速度。让我们将内存变量视为内存的不相交分区（也就是说，如果您有一个变量，如上所述，它代表整个内存，如果您有多个变量，则每个变量代表内存的某些不相交部分）

首先，由于别名分析结果相互冲突，并且每个结果都可能是分析想要的（即 TBAA 可能说 no-alias，而其他东西可能说 must-alias），因此不可能按照每个优化想要的方式对内存进行分区。其次，某些别名分析结果不是传递的（即 A noalias B，B noalias C，并不意味着 A noalias C），因此在所有情况下都不可能得出精确的分区，而无需变量来表示每对可能的别名。因此，精确分区可能需要引入至少 N^2 个新的虚拟变量、phi 节点等。

这些变量中的每一个都可能在多个 def 站点被 clobber（覆写）。

举个例子，如果您要将结构字段拆分为单独的变量，则可能 def 多个结构字段的所有别名操作将可能 def 它们中的多个。这很常见（调用、复制、字段存储等）。

其他编译器中内存 SSA 形式的经验表明，精确地做到这一点根本不可能，事实上，精确地做到这一点是不值得的，因为现在所有的优化都必须遍历大量虚拟变量和 phi 节点。

因此我们进行分区。在您进行分区时，经验再次向我们表明，分区到一个以上的变量是没有意义的。它只会生成更多的 IR，并且优化仍然必须查询某些东西才能进一步消除歧义。

因此，LLVM 分区为一个变量。

实践中的精度

在实践中，LLVM 中存在一些实现细节，这些细节也会影响 MemorySSA 提供的结果的精度。例如，别名分析（AliasAnalysis）有各种限制或约束（例如在查看 phi 节点时），这可能会影响 MemorySSA 可以推断出的内容。不同 Pass 所做的更改可能会使 MemorySSA 变得“过度优化”（它可以提供比从头开始重新计算更准确的结果），或者“优化不足”（如果重新计算，它可以推断出更多）。当结果依赖于 MemorySSA 获取的状态（由于被多个后续 Pass 更新）时，这可能会导致在单个 Pass 中隔离地重现结果时遇到挑战。使用和更新 MemorySSA 的 Pass 应该通过 MemorySSAUpdater 提供的 API 或通过 Walker 上的调用来完成。不允许直接优化 MemorySSA。目前存在一个范围狭窄的例外情况，即 DSE（死存储消除）在保证优化正确的遍历之后，更新对存储的优化访问。之所以允许这样做，仅仅是因为遍历和推断超出了 MemorySSA 的范围，并且它们是“免费的”（即 DSE 无论如何都会执行它们）。此例外情况在标志（“-dse-optimize-memoryssa”）下设置，并且可以禁用它以帮助隔离地重现优化。

LLVM 开发者会议演示文稿

• 2016 年 LLVM 开发者会议：G. Burgess - 五分钟了解 MemorySSA.

• 2020 年 LLVM 开发者会议：S. Baziotis & S. Moll - 探索 LLVM 依赖分析动物园