LLVM 别名分析基础设施¶

简介 ¶

别名分析（又名指针分析）是一类尝试确定两个指针是否可能指向内存中同一对象的技术。别名分析有许多不同的算法，也有许多不同的分类方法：流敏感与流不敏感、上下文敏感与上下文不敏感、字段敏感与字段不敏感、基于统一与基于子集等等。传统上，别名分析使用必须别名、可能别名或无别名响应来回答查询，指示两个指针总是指向同一对象、可能指向同一对象或已知永远不会指向同一对象。

LLVM AliasAnalysis 类是 LLVM 系统中别名分析的客户端和实现使用的主要接口。此类是别名分析信息的客户端和提供信息的实现之间的通用接口，旨在支持广泛的实现和客户端（但目前所有客户端都被假定为流不敏感的）。除了简单的别名分析信息之外，此类还公开了来自可以提供 Mod/Ref 信息的实现的 Mod/Ref 信息，从而允许强大的分析和转换协同工作。

本文档包含成功实现此接口、使用它以及测试双方所需的信息。它还解释了关于结果究竟意味着什么的一些更精细的要点。

`AliasAnalysis` 类概述 ¶

AliasAnalysis 类定义了各种别名分析实现应支持的接口。此类导出两个重要的枚举：AliasResult 和 ModRefResult，它们分别表示别名查询或 mod/ref 查询的结果。

AliasAnalysis 接口公开了关于内存的信息，以几种不同的方式表示。特别是，内存对象表示为起始地址和大小，函数调用表示为执行调用的实际 call 或 invoke 指令。AliasAnalysis 接口还公开了一些辅助方法，允许您获取任意指令的 mod/ref 信息。

所有 AliasAnalysis 接口都要求在涉及多个值的查询中，不是常量的值都定义在同一函数内。

指针的表示 ¶

最重要的是，AliasAnalysis 类提供了几种方法，用于查询两个内存对象是否别名，函数调用是否可以修改或读取内存对象等等。对于所有这些查询，内存对象都表示为其起始地址（符号 LLVM Value*）和静态大小的对。

将内存对象表示为起始地址和大小对于正确的别名分析至关重要。例如，考虑以下（愚蠢但可能）的 C 代码

int i;
char C[2];
char A[10];
/* ... */
for (i = 0; i != 10; ++i) {
  C[0] = A[i];          /* One byte store */
  C[1] = A[9-i];        /* One byte store */
}

在这种情况下，basic-aa pass 将消除对 C[0] 和 C[1] 的存储的歧义，因为它们是对相隔一个字节的两个不同位置的访问，并且每次访问都是一个字节。在这种情况下，循环不变代码移动 (LICM) pass 可以使用存储移动从循环中删除存储。相比之下，以下代码

int i;
char C[2];
char A[10];
/* ... */
for (i = 0; i != 10; ++i) {
  ((short*)C)[0] = A[i];  /* Two byte store! */
  C[1] = A[9-i];          /* One byte store */
}

在这种情况下，对 C 的两个存储相互别名，因为对 &C[0] 元素的访问是两个字节的访问。如果查询中没有大小信息，即使是第一种情况也必须保守地假设访问别名。

`alias` 方法 ¶

alias 方法是用于确定两个内存对象是否相互别名的主要接口。它接受两个内存对象作为输入，并根据需要返回 MustAlias、PartialAlias、MayAlias 或 NoAlias。

与所有 AliasAnalysis 接口一样，alias 方法要求两个指针值要么在同一函数中定义，要么至少其中一个值是常量。

必须别名、可能别名和无别名响应 ¶

当基于一个指针的任何内存引用与基于另一个指针的任何内存引用之间永远没有直接依赖关系时，可以使用 NoAlias 响应。最明显的例子是当两个指针指向不重叠的内存范围时。另一个例子是当两个指针仅用于读取内存时。另一个例子是当内存被释放并在通过一个指针的访问和通过另一个指针的访问之间重新分配时 — 在这种情况下，存在依赖关系，但它是由释放和重新分配介导的。

作为对此的例外是使用 noalias 关键字；“不相关”的依赖关系被忽略。

每当两个指针可能引用同一对象时，就使用 MayAlias 响应。

当已知两个内存对象以某种方式重叠时，无论它们是否从同一地址开始，都使用 PartialAlias 响应。

只有当保证两个内存对象始终从完全相同的位置开始时，才能返回 MustAlias 响应。MustAlias 响应并不意味着指针比较相等。

`getModRefInfo` 方法 ¶

getModRefInfo 方法返回有关指令的执行是否可以读取或修改内存位置的信息。Mod/Ref 信息始终是保守的：如果指令**可能**读取或写入位置，则返回 ModRef。

AliasAnalysis 类还提供了一个 getModRefInfo 方法，用于测试函数调用之间的依赖关系。此方法接受两个调用站点（CS1 & CS2），如果两个调用都不写入另一个调用的读取或写入的内存，则返回 NoModRef；如果 CS1 读取 CS2 写入的内存，则返回 Ref；如果 CS1 写入 CS2 读取或写入的内存，则返回 Mod；或者如果 CS1 可能读取或写入 CS2 写入的内存，则返回 ModRef。请注意，此关系不是可交换的。

其他有用的 `AliasAnalysis` 方法 ¶

各种别名分析实现通常会收集其他一些有用的信息，并且可以被各种客户端很好地利用。

`getModRefInfoMask` 方法 ¶

getModRefInfoMask 方法根据有关指针是否指向全局常量内存（为其返回 NoModRef）或局部不变内存（为其返回 Ref）的知识，返回所提供指针的 Mod/Ref 信息的界限。全局常量内存包括函数、常量全局变量和空指针。局部不变内存是我们知道在其 SSA 值的生命周期内是不变的内存，但不一定在程序的生命周期内不变：例如，readonly noalias 参数指向的内存在其对应的函数调用期间是已知不变的。给定内存位置 Loc 的 Mod/Ref 信息 MRI，可以使用如下语句细化 MRI：MRI &= AA.getModRefInfoMask(Loc);。另一个有用的习惯用法是 isModSet(AA.getModRefInfoMask(Loc))；这会检查给定位置是否可以被修改。为方便起见，还有一个方法 pointsToConstantMemory(Loc)；这与 isNoModRef(AA.getModRefInfoMask(Loc)) 同义。

`doesNotAccessMemory` 和 `onlyReadsMemory` 方法 ¶

这些方法用于为函数调用提供非常简单的 mod/ref 信息。doesNotAccessMemory 方法对于分析可以证明函数从不读取或写入内存，或者函数仅从常量内存读取的情况，为函数返回 true。具有此属性的函数是无副作用的，并且仅依赖于其输入参数，从而允许在它们形成公共子表达式或被提升到循环之外时消除它们。许多常用函数都以这种方式运行（例如，sin 和 cos），但许多其他函数则不然（例如，acos，它修改 errno 变量）。

对于分析可以证明函数（最多）仅从非易失性内存读取的情况，onlyReadsMemory 方法为函数返回 true。具有此属性的函数是无副作用的，仅依赖于其输入参数和调用它们时内存的状态。此属性允许消除和移动对这些函数的调用，只要没有存储指令更改内存的内容即可。请注意，所有满足 doesNotAccessMemory 方法的函数也满足 onlyReadsMemory。

编写新的 `AliasAnalysis` 实现 ¶

为 LLVM 编写新的别名分析实现非常简单。已经有几个实现可以供您用作示例，以下信息应该有助于填写任何详细信息。有关示例，请查看 LLVM 包含的各种别名分析实现。

不同的 Pass 风格 ¶

确定需要为别名分析使用哪种类型的 LLVM pass 的第一步。与大多数其他分析和转换一样，答案应该从您尝试解决的问题类型中显而易见

如果您需要过程间分析，它应该是 Pass。
如果您是函数局部分析，请继承 FunctionPass。
如果您根本不需要查看程序，请继承 ImmutablePass。

除了您继承的 pass 之外，您还应该继承 AliasAnalysis 接口，当然，并使用 RegisterAnalysisGroup 模板注册为 AliasAnalysis 的实现。

必需的初始化调用 ¶

您的 AliasAnalysis 子类需要调用 AliasAnalysis 基类上的两个方法：getAnalysisUsage 和 InitializeAliasAnalysis。特别是，您的 getAnalysisUsage 实现除了声明 pass 具有的任何 pass 依赖项之外，还应显式调用 AliasAnalysis::getAnalysisUsage 方法。因此，您应该有类似这样的内容

void getAnalysisUsage(AnalysisUsage &AU) const {
  AliasAnalysis::getAnalysisUsage(AU);
  // declare your dependencies here.
}

此外，您必须从分析运行方法（Pass 的 run、FunctionPass 的 runOnFunction 或 ImmutablePass 的 InitializePass）中调用 InitializeAliasAnalysis 方法。例如（作为 Pass 的一部分）

bool run(Module &M) {
  InitializeAliasAnalysis(this);
  // Perform analysis here...
  return false;
}

要重写的必需方法 ¶

您必须重写 AliasAnalysis 所有子类上的 getAdjustedAnalysisPointer 方法。此方法的示例实现如下所示

void *getAdjustedAnalysisPointer(const void* ID) override {
  if (ID == &AliasAnalysis::ID)
    return (AliasAnalysis*)this;
  return this;
}

可以指定的接口 ¶

所有 AliasAnalysis 虚方法都默认为提供链接到另一个别名分析实现，最终返回保守的正确信息（别名和 mod/ref 查询分别返回“可能”别名和“Mod/Ref”）。根据您正在实现的分析的功能，您只需重写您可以改进的接口。

`AliasAnalysis` 链接行为 ¶

每个别名分析 pass 都链接到另一个别名分析实现（例如，用户可以指定“-basic-aa -ds-aa -licm”以从两个别名分析中获得最大收益）。对于您未重写的方法，别名分析类会自动处理大部分此操作。对于您重写的方法，在返回保守的 MayAlias 或 Mod/Ref 结果的代码路径中，只需返回超类计算的任何内容。例如

AliasResult alias(const Value *V1, unsigned V1Size,
                  const Value *V2, unsigned V2Size) {
  if (...)
    return NoAlias;
  ...

  // Couldn't determine a must or no-alias result.
  return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
}

除了分析查询之外，如果您重写了 LLVM 更新通知方法，则必须确保无条件地将它们传递给超类，这也允许更新更改中的所有别名分析。

更新转换的分析结果 ¶

别名分析信息最初是针对程序的静态快照计算的，但客户端将使用此信息对代码进行转换。除了最简单的形式的别名分析之外，还需要更新其分析结果以反映这些转换所做的更改。

AliasAnalysis 接口公开了四种方法，用于将程序更改从客户端传达给分析实现。各种别名分析实现应使用这些方法来确保其内部数据结构在程序更改时（例如，当指令被删除时）保持最新，并且别名分析的客户端必须确保适当地调用这些接口。

`deleteValue` 方法 ¶

当转换从程序中删除指令或任何其他值（包括不使用指针的值）时，会调用 deleteValue 方法。通常，别名分析会保留数据结构，这些数据结构具有程序中每个值的条目。当调用此方法时，它们应删除指定值的任何条目（如果存在）。

`copyValue` 方法 ¶

当将新值引入程序时，使用 copyValue 方法。没有办法将以前不存在的值引入程序（对于安全的编译器转换来说，这是没有意义的），因此这是引入新值的唯一方法。此方法指示新值具有与复制的值完全相同的属性。

`replaceWithNewValue` 方法 ¶

此方法是一个简单的辅助方法，旨在使客户端更易于使用。它通过将旧的分析信息复制到新值，然后删除旧值来实现。别名分析实现无法重写此方法。

`addEscapingUse` 方法 ¶

当指针值的使用方式发生更改，可能使预先计算的分析信息无效时，使用 addEscapingUse 方法。实现可以使用此回调为使用方式自分析以来已更改的点提供保守响应，或者可以重新计算其部分或全部内部状态以继续提供准确的响应。

一般来说，指针值的任何新用途都被视为转义用途，并且必须通过此回调报告，**除了**以下用途

指针的 bitcast 或 getelementptr
通过指针的 store （但不是指针**的** store）
通过指针的 load

效率问题 ¶

从 LLVM 的角度来看，您需要做的提供高效别名分析的唯一事情是确保别名分析**查询**能够快速响应。别名分析结果的实际计算（“run”方法）仅执行一次，但可能会执行许多（可能是重复的）查询。因此，请尝试在合理的范围内将尽可能多的计算移动到 run 方法。

局限性 ¶

别名分析基础设施有几个局限性，这使得编写新的 AliasAnalysis 实现变得困难。

无法覆盖默认别名分析。能够执行类似“opt -my-aa -O2”的操作并使其对所有需要 AliasAnalysis 的 pass 使用 -my-aa 将非常有用，但目前不支持这样做，除非更改源代码并重新编译。同样，也没有办法将分析链设置为默认值。

转换 pass 无法声明它们保留 AliasAnalysis 实现。AliasAnalysis 接口包括 deleteValue 和 copyValue 方法，这些方法旨在允许 pass 保持 AliasAnalysis 的一致性，但是 pass 无法在其 getAnalysisUsage 中声明它这样做。某些 pass 尝试使用 AU.addPreserved<AliasAnalysis>，但这实际上没有任何效果。

同样，opt -p 选项在每个 pass 之间引入 ModulePass pass，这阻止了使用 FunctionPass 别名分析 pass。

AliasAnalysis API 确实具有在值被删除或复制时通知实现的功能，但是这些功能是不够的。还有许多其他可以修改 LLVM IR 的方式，这些方式可能与无法表达的 AliasAnalysis 实现相关。

AliasAnalysisDebugger 实用程序似乎表明 AliasAnalysis 实现可以期望在别名查询中出现任何相关的 Value 之前，它们会被告知。但是，流行的客户端（如 GVN）不支持此功能，并且已知在与 AliasAnalysisDebugger 一起运行时会触发错误。

AliasSetTracker 类（由 LICM 使用）进行非确定性数量的别名查询。这可能会导致涉及在预定数量的查询后暂停执行的调试技术变得不可靠。

许多别名查询可以用其他别名查询来重新表述。当多个 AliasAnalysis 查询链接在一起时，从链的开头开始这些查询是有意义的，并注意避免无限循环，但是当前想要执行此操作的实现只能从自身开始此类查询。

使用别名分析结果 ¶

有几种不同的方法可以使用别名分析结果。按优先级顺序，这些是

使用 `MemoryDependenceAnalysis` Pass ¶

memdep pass 使用别名分析来提供有关使用内存的指令的高级依赖信息。例如，这将告诉您哪个存储馈送到加载中。它使用缓存和其他技术来提高效率，并被死存储消除、GVN 和 memcpy 优化使用。

使用 `AliasSetTracker` 类 ¶

许多转换需要关于在某个作用域中活跃的别名集合的信息，而不是关于成对别名的信息。 AliasSetTracker 类用于从 AliasAnalysis 接口提供的成对别名分析信息中高效地构建这些别名集合。

首先，您需要使用 “add” 方法初始化 AliasSetTracker，以添加有关您感兴趣的作用域中各种可能存在别名指令的信息。一旦所有别名集合构建完成，您的pass应该简单地遍历构建好的别名集合，使用 AliasSetTracker 的 begin()/end() 方法。

由 AliasSetTracker 创建的 AliasSet 保证是不相交的，可以计算集合的修改/引用信息和易变性，并跟踪集合中所有指针是否都是 Must 别名。AliasSetTracker 还可以确保由于调用指令而正确地折叠集合，并可以提供每个集合中指针的列表。

作为它的一个示例用户，循环不变代码移动 pass 使用 AliasSetTracker 为每个循环嵌套计算别名集合。如果循环中的一个 AliasSet 没有被修改，那么来自该集合的所有 load 指令都可以被提升到循环外部。如果任何别名集合被存储并且是 must 别名集合，那么这些存储可以被下沉到循环外部，从而在循环嵌套期间将内存位置提升为寄存器。这两种转换都只在指针参数是循环不变的情况下适用。

AliasSetTracker 的实现 ¶

AliasSetTracker 类的实现尽可能高效。它使用 union-find 算法来高效地合并 AliasSet，当指针被插入到 AliasSetTracker 中并且该指针与多个集合存在别名关系时。主要的数据结构是一个哈希表，用于将指针映射到它们所属的 AliasSet。

AliasSetTracker 类必须维护一个列表中，包含每个 AliasSet 中的所有 LLVM Value*。由于哈希表已经为每个感兴趣的 LLVM Value* 准备了条目，因此 AliasesSets 通过这些哈希表节点将链表串联起来，以避免不必要的内存分配，并使合并别名集合非常高效（链表合并是常数时间）。

如果您只是 AliasSetTracker 的客户端，则无需理解这些细节，但是如果您查看代码，希望这个简短的描述将有助于理解为什么事物以这种方式设计。

直接使用 `AliasAnalysis` 接口 ¶

如果这些实用程序类都不是您的 pass 所需的，您应该直接使用 AliasAnalysis 类公开的接口。尽可能尝试使用更高级别的方法（例如，如果可能，使用修改/引用信息而不是直接使用 alias 方法），以获得最佳的精度和效率。

现有的别名分析实现和客户端 ¶

如果您要使用 LLVM 别名分析基础设施，您应该了解有哪些可用的别名分析客户端和实现。特别是，如果您正在实现别名分析，您应该了解客户端，这些客户端对于监控和评估不同的实现非常有用。

可用的 `AliasAnalysis` 实现 ¶

本节列出了 AliasAnalysis 接口的各种实现。所有这些实现都链接到其他别名分析实现。

`-basic-aa` pass ¶

-basic-aa pass 是一种激进的本地分析，它*知道*许多重要的事实

不同的全局变量、栈分配和堆分配永远不会互为别名。
全局变量、栈分配和堆分配永远不会是空指针的别名。
结构体的不同字段不会互为别名。
具有静态不同下标的数组索引不能互为别名。
许多常见的标准 C 库函数从不访问内存或只读取内存。
明显指向常量全局变量的指针 “pointToConstantMemory”。
如果函数调用永远不会从分配它们的函数中逃逸（自动数组的常见情况），则函数调用不能修改或引用栈分配。

`-globalsmodref-aa` pass ¶

此 pass 为“未取地址”的内部全局变量实现了一个简单的上下文敏感的修改/引用和别名分析。如果一个全局变量未取地址，则该 pass 知道没有指针是该全局变量的别名。此 pass 还跟踪它知道从不访问内存或从不读取内存的函数。这允许某些优化（例如 GVN）完全消除调用指令。

此 pass 的真正威力在于它为调用指令提供了上下文敏感的修改/引用信息。这允许优化器知道对函数的调用不会破坏或读取全局变量的值，从而可以消除 load 和 store 操作。

注意

此 pass 在其范围上有些限制（仅支持未取地址的全局变量），但分析速度非常快。

`-steens-aa` pass ¶

-steens-aa pass 实现了著名的“Steensgaard 算法”的一种变体，用于过程间别名分析。Steensgaard 算法是一种基于合一、流不敏感、上下文不敏感和字段不敏感的别名分析，它也具有非常好的可扩展性（有效线性时间）。

LLVM -steens-aa pass 使用数据结构分析框架实现了 Steensgaard 算法的“推测性字段敏感 ”版本。这使其比标准算法具有更高的精度，同时保持了出色的分析可扩展性。

注意

-steens-aa 在可选的 “poolalloc” 模块中可用。它不是 LLVM 核心的一部分。

`-ds-aa` pass ¶

-ds-aa pass 实现了完整的数据结构分析算法。数据结构分析是一种模块化的、基于合一的、流不敏感的、上下文敏感的和推测性字段敏感的别名分析，它也具有很好的可扩展性，通常为 O(n * log(n))。

该算法能够响应各种别名分析查询，并且还可以提供上下文敏感的修改/引用信息。目前尚未实现的主要功能是支持 must-alias 信息。

注意

-ds-aa 在可选的 “poolalloc” 模块中可用。它不是 LLVM 核心的一部分。

`-scev-aa` pass ¶

-scev-aa pass 通过将 AliasAnalysis 查询转换为 ScalarEvolution 查询来实现它们。与其他别名分析相比，这使其能够更完整地理解 getelementptr 指令和循环归纳变量。

别名分析驱动的转换 ¶

LLVM 包含多个别名分析驱动的转换，可以与上述任何实现一起使用。

`-adce` pass ¶

-adce pass，它实现了激进的死代码消除，使用 AliasAnalysis 接口来删除对没有副作用且未被使用的函数的调用。

`-licm` pass ¶

-licm pass 实现了各种与循环不变代码移动相关的转换。它为几种不同的转换使用 AliasAnalysis 接口

它使用修改/引用信息来提升或下沉循环外部的 load 指令，如果在循环中没有指令修改加载的内存。
它使用修改/引用信息来提升循环外部的函数调用，这些函数调用不写入内存并且是循环不变的。
它使用别名信息来提升在循环中加载和存储的内存对象，使其驻留在寄存器中。如果加载/存储的内存位置没有 may 别名，则可以这样做。

`-argpromotion` pass ¶

-argpromotion pass 将按引用传递的参数提升为按值传递。特别是，如果指针参数仅从中加载，则它传递加载的值而不是函数的地址。此 pass 使用别名信息来确保从参数指针加载的值在函数入口和任何指针加载之间未被修改。

`-gvn`、`-memcpyopt` 和 `-dse` passes ¶

这些 pass 使用 AliasAnalysis 信息来推断 load 和 store 操作。

用于调试和评估实现的客户端 ¶

这些 pass 对于评估各种别名分析实现非常有用。您可以将它们与如下命令一起使用

% opt -ds-aa -aa-eval foo.bc -disable-output -stats

`-print-alias-sets` pass ¶

-print-alias-sets pass 作为 opt 工具的一部分公开，用于打印由 AliasSetTracker 类形成的别名集合。如果您正在使用 AliasSetTracker 类，这将非常有用。要使用它，请使用如下命令

% opt -ds-aa -print-alias-sets -disable-output

`-aa-eval` pass ¶

-aa-eval pass 简单地遍历函数中的所有指针对，并询问别名分析指针是否互为别名。这指示了别名分析的精度。打印的统计信息指示找到的 no/may/must 别名的百分比（更精确的算法将具有更少的 may 别名）。

内存依赖性分析 ¶

注意

我们目前正在将内容从 MemoryDependenceAnalysis 迁移到 MemorySSA。请尝试使用后者。

如果您只是想成为别名分析信息的客户端，请考虑使用内存依赖性分析接口。MemDep 是别名分析之上的一个惰性缓存层，它能够回答给定指令依赖于哪些先前的内存操作的问题，无论是在块内还是块间级别。由于其惰性和缓存策略，使用 MemDep 可以比直接访问别名分析获得显着的性能提升。