LLVM 别名分析基础设施¶

简介 ¶

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

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

本文档包含成功实现此接口、使用它以及测试两方面所需的信息。它还解释了关于结果的确切含义的一些更细致的要点。

`AliasAnalysis` 类概述 ¶

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

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

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

指针的表示 ¶

最重要的是，the 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 */
}

在这种情况下，the 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] 元素的访问是两个字节的访问。如果查询中没有大小信息，即使是第一种情况也必须保守地假设访问别名。

the `alias` 方法 ¶

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

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

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

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

作为对此的一个例外是使用 noalias 关键字；忽略“无关”的依赖关系。

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

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

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

the `getModRefInfo` 方法 ¶

the 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 &= AA.getModRefInfoMask(Loc); 的语句来细化 MRI。另一个有用的习惯用法是 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 查询返回“May”别名和“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 基础设施有一些限制，使得编写新的 AliasAnalysis 实现变得困难。

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

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

类似地，opt -p 选项在每个传递之间引入 ModulePass 传递，这会阻止使用 FunctionPass 别名分析传递。

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

AliasAnalysisDebugger 实用程序似乎表明 AliasAnalysis 实现可以预期在别名查询中出现之前会被告知任何相关的 Value。但是，像 GVN 这样的常用客户端不支持这一点，并且已知在与 AliasAnalysisDebugger 一起运行时会触发错误。

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

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

使用别名分析结果 ¶

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

使用 `MemoryDependenceAnalysis` 传递 ¶

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

使用 `AliasSetTracker` 类 ¶

许多转换需要有关某个范围内活动别名集的信息，而不是有关成对别名关系的信息。 AliasSetTracker 类用于根据 AliasAnalysis 接口提供的成对别名分析信息有效地构建这些别名集。

首先，使用“add”方法添加有关您感兴趣范围内的各种可能存在别名关系的指令的信息，从而初始化 AliasSetTracker。所有别名集完成后，您的传递只需遍历构造的别名集，使用 AliasSetTracker 的 begin()/end() 方法。

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

例如，循环不变代码移动传递使用 AliasSetTracker 计算每个循环嵌套的别名集。如果循环中的 AliasSet 未被修改，则该集合中的所有加载指令都可以从循环中提升出来。如果任何别名集都被存储到并且是必须别名集，则存储可以下沉到循环外部，在循环嵌套期间将内存位置提升到寄存器。这两种转换仅在指针参数是循环不变的情况下才适用。

AliasSetTracker 实现 ¶

AliasSetTracker 类旨在尽可能高效地实现。它使用并查集算法，在将与多个集合存在别名关系的指针插入 AliasSetTracker 时有效地合并 AliasSet。主要数据结构是将指针映射到它们所在的 AliasSet 的哈希表。

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

如果您只是 AliasSetTracker 的客户端，则无需了解这些细节，但是如果您查看代码，希望此简要说明将有助于理解事物设计的原因。

直接使用 `AliasAnalysis` 接口 ¶

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

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

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

可用的 `AliasAnalysis` 实现 ¶

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

`-basic-aa` 传递 ¶

-basic-aa 传递是一种积极的局部分析，它知道许多重要的信息

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

`-globalsmodref-aa` 传递 ¶

此传递为不“取其地址”的内部全局变量实现了一个简单的上下文相关 mod/ref 和别名分析。如果全局变量没有取其地址，则传递知道没有指针与该全局变量发生别名。此传递还跟踪它已知从不访问内存或从不读取内存的函数。这允许某些优化（例如 GVN）完全消除调用指令。

此传递的真正威力在于它为调用指令提供了上下文相关的 mod/ref 信息。这允许优化器知道对函数的调用不会破坏或读取全局变量的值，从而允许消除加载和存储。

注意

此传递的范围有些受限（仅支持未取地址的全局变量），但分析速度非常快。

`-steens-aa` 传递 ¶

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

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

注意

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

`-ds-aa` 传递 ¶

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

此算法能够响应各种别名分析查询，并且还可以提供上下文相关的 mod/ref 信息。到目前为止，唯一尚未实现的主要功能是对必须别名信息的支持。

注意

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

`-scev-aa` 传递 ¶

-scev-aa 传递通过将别名分析查询转换为标量演化查询来实现。这使得它比其他别名分析更全面地了解 getelementptr 指令和循环归纳变量。

别名分析驱动的转换 ¶

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

`-adce` 传递 ¶

-adce 传递实现了积极的死代码消除，它使用 AliasAnalysis 接口删除对没有副作用且未使用的函数的调用。

`-licm` 传递 ¶

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

它使用 mod/ref 信息将加载指令从循环中提升或下沉，如果循环中没有修改加载内存的指令。
它使用 mod/ref 信息将对不写入内存且循环不变的函数的调用从循环中提升。
它使用别名信息将循环中加载和存储的内存对象提升到寄存器中。如果加载/存储内存位置没有可能别名，则可以执行此操作。

`-argpromotion` 传递 ¶

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

`-gvn`、`-memcpyopt` 和 `-dse` 传递 ¶

这些传递使用别名分析信息来推断加载和存储。

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

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

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

`-print-alias-sets` 传递 ¶

-print-alias-sets 传递作为 opt 工具的一部分公开，用于打印出由 AliasSetTracker 类形成的别名集。如果您正在使用 AliasSetTracker 类，这将非常有用。要使用它，请使用类似以下内容：

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

`-aa-eval` 传递 ¶

-aa-eval 传递只是迭代函数中所有指针对，并询问别名分析这些指针是否发生别名。这可以指示别名分析的精度。打印统计信息，指示找到的无/可能/必须别名的百分比（更精确的算法将具有更少的可能别名）。

内存相关性分析 ¶

注意

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

如果您只是希望成为别名分析信息的客户端，请考虑改用内存相关性分析接口。MemDep 是建立在别名分析之上的一个延迟缓存层，能够回答给定指令依赖于哪些前面的内存操作的问题，无论是在块内还是块间级别。由于其延迟和缓存策略，使用 MemDep 与直接访问别名分析相比，可以显著提高性能。