MemorySSA¶

简介 ¶

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

从高级别来看，MemorySSA 的目标之一是为内存提供基于 SSA 的形式，包括定义-使用和使用-定义链，这使用户能够快速找到内存操作的可能定义和可能使用。它也可以被认为是一种廉价地为内存的完整状态提供版本，并将内存操作与这些版本关联起来的方法。

本文档介绍了 MemorySSA 的结构，以及一些关于 MemorySSA 如何工作的基本直觉。

关于 MemorySSA 的论文（以及关于它在 GCC 中如何实现的注释）可以在这里找到。不过，它已经过时了；该论文提到了多个内存分区，但 GCC 最终切换到只使用一个，就像我们现在在 LLVM 中使用的那样。与 GCC 的类似，LLVM 的 MemorySSA 是过程内的。

MemorySSA 结构 ¶

MemorySSA 是一个虚拟 IR。构建完成后，MemorySSA 将包含一个结构，该结构将 Instruction 映射到 MemoryAccess，MemoryAccess 是 MemorySSA 中与 LLVM Instruction 平行的概念。

每个 MemoryAccess 可以是三种类型之一

MemoryDef
MemoryPhi
MemoryUse

MemoryDef 是可能修改内存或引入某种排序约束的操作。 MemoryDef 的示例包括 store、函数调用、具有 acquire（或更高）排序的 load、易失性操作、内存栅栏等。 MemoryDef 始终引入整个内存的新版本，并与单个 MemoryDef/MemoryPhi 链接，该版本是新版本基于的内存版本。这意味着存在一个单个 Def 链，该链直接或间接地连接所有 Def。例如在

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

d 直接与 c 连接，间接与 b 连接。这意味着 d 可能覆盖（见下文）c或b或两者。这反过来意味着，在不使用遍历器的情况下，最初每个 MemoryDef 都覆盖其他每个 MemoryDef。

MemoryPhi 是 PhiNode，但用于内存操作。如果在任何时候我们有两个（或更多）可能流入 BasicBlock 的 MemoryDef，则该块的顶部 MemoryAccess 将是 MemoryPhi。与 LLVM IR 中一样，MemoryPhi 不对应于任何具体的操作。因此，BasicBlock 在 MemorySSA 内部映射到 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 中的其他地方将此特定 MemoryDef 称为 1（就像人们可以使用 %1 来引用 LLVM 中的 load i8, ptr %p1 一样）。同样，MemoryPhi 不对应于任何 LLVM 指令，因此 MemoryPhi 下面的行没有什么特殊之处。

从上到下

6 = MemoryPhi({entry,1},{if.end,4}) 指出，在进入 while.cond 时，其到达定义（reaching definition）要么是 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}) 指出此块之前的覆盖（clobber）可能是 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 没有请求特定内存访问的覆盖访问，所以没有可以缓存的结果。

自己定位覆盖 ¶

如果您选择制作自己的遍历器，可以通过遍历支配该 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 更新时都需要更新它。“更新”在此处包括 Instructions 的添加、删除和移动。更新 API 正在根据需要进行开发。如果您需要示例，GVNHoist 和 LICM 是 MemorySSA 的更新 API 的用户。请注意，如果新的访问触发了许多 MemoryPhi 插入和许多 MemoryAccesses 的重命名（优化失效），那么添加新的 MemoryDef（通过调用 insertDef）可能是一个耗时的更新操作。

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）在遍历保证优化正确后，更新存储的优化访问。仅允许这样做是因为遍历和推断超出了 MemorySSA 的范围，并且它们是“免费的”（即 DSE 无论如何都会执行它们）。此例外情况是在一个标志（“-dse-optimize-memoryssa”）下设置的，可以禁用它以帮助在隔离中重现优化。

文档

参与贡献

其他链接

本页