LLVM 之 IR 篇（8）：如何编写别名分析 Pass
Author: stormQ
Created: Sunday, 29. August 2021 10:09AM
Last Modified: Wednesday, 01. September 2021 09:13PM
本文基于release/13.x版本的 LLVM 源码，介绍了如何编写别名分析 Pass——must-aa。该 Pass 认为任意两个指针都指向同一个对象。通过实现这样一个简单的 Pass，从而初步了解 LLVM IR 别名分析的运行流程，以便更深入地研究相关内容，比如：basic-aa、globalsmodref-aa、steens-aa、ds-aa、scev-aa 等。
本节介绍了编写别名分析 Pass 的前期准备工作（不涉及具体功能的实现）。
注： 本节涉及的大部分代码是基于传统 Pass 框架在源码中进行扩展的，这里不再赘述源码解析。如有疑问，可参考笔者的另一篇文章：《LLVM 之 IR 篇（4）：如何基于传统 Pass 框架扩展 LLVM IR 优化器》。
step 1： 修改 InitializePasses.h
在llvm/include/llvm/InitializePasses.h文件中添加如下内容：
void initializeEverythingMustAliasLegacyPassPass(PassRegistry &);
修改后的内容为：
namespace llvm {
省略 ...
void initializeEverythingMustAliasLegacyPassPass(PassRegistry &);
} // end namespace llvm
step 2： 添加 Analysis.h
在llvm/include/llvm/Analysis目录中新建Analysis.h文件，内容如下：
1 #ifndef LLVM_ANALYSIS_ANALYSIS_H
2 #define LLVM_ANALYSIS_ANALYSIS_H
3
4 namespace llvm {
5
6 class ImmutablePass;
7
8 ImmutablePass *createEverythingMustAliasLegacyPass();
9
10 } // End llvm namespace
11
12 #endif // LLVM_ANALYSIS_ANALYSIS_H
注： 头文件Analysis.h用于为所有别名分析 Pass 提供创建函数的声明，而各别名分析 Pass 负责实现各自的创建函数。这样做（不是必须的），头文件LinkAllPasses.h中只需要添加一个头文件依赖——Analysis.h，而不需要添加所有别名分析 Pass 的头文件。该思路是源于头文件llvm/Transforms/IPO.h和llvm/Transforms/Scalar.h。
step 3： 修改 LinkAllPasses.h
在llvm/include/llvm/LinkAllPasses.h文件中添加如下内容：
#include "llvm/Analysis/Analysis.h"
另外，在该文件中添加如下内容：
(void) llvm::createEverythingMustAliasLegacyPass();
修改后的内容为：
namespace {
struct ForcePassLinking {
ForcePassLinking() {
省略 ...
(void) llvm::createEverythingMustAliasLegacyPass();
省略 ...
}
} ForcePassLinking; // Force link by creating a global definition.
}
step 4： 修改 Analysis.cpp
在llvm/lib/Analysis/Analysis.cpp文件中添加如下内容
initializeEverythingMustAliasLegacyPassPass(Registry);
修改后的内容为：
void llvm::initializeAnalysis(PassRegistry &Registry) {
省略 ...
initializeEverythingMustAliasLegacyPassPass(Registry);
}
step 5： 修改 Analysis 目录中的 CMakeLists.txt
在llvm/lib/Analysis/CMakeLists.txt文件中添加如下内容：
EverythingMustAlias.cpp
注： 源文件EverythingMustAlias.cpp用于存放别名分析 Pass——must-aa的实现代码。
step 6： 修改 AliasAnalysis.cpp
在llvm/lib/Analysis/AliasAnalysis.cpp文件中添加如下内容：
#include "llvm/Analysis/EverythingMustAlias.h"
注： 头文件EverythingMustAlias.h用于存放别名分析 Pass——must-aa的类定义等。
另外，在该文件的AAResultsWrapperPass::runOnFunction()函数中添加如下内容：
if (auto *WrapperPass = getAnalysisIfAvailable<EverythingMustAliasLegacyPass>())
AAR->addAAResult(WrapperPass->getResult());
注： 上述代码用于将别名分析 Pass——must-aa添加到别名分析 Pass——aa-eval的流水线中。如果运行opt工具时带了-must-aa选项，那么上述代码中if条件语句的求值结果为true；否则，为false。
修改后的内容为：
bool AAResultsWrapperPass::runOnFunction(Function &F) {
省略 ...
AAR.reset(
new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F)));
if (auto *WrapperPass = getAnalysisIfAvailable<EverythingMustAliasLegacyPass>())
AAR->addAAResult(WrapperPass->getResult());
省略 ...
if (!DisableBasicAA)
AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
省略 ...
}
需要注意的是， 为了保证别名分析 Pass——must-aa一定会被调用，别名分析 Pass——must-aa必须作为别名分析 Pass——aa-eval流水线中的第一个 Pass，即上述代码必须在创建对象AAR之后紧接着添加。这样做是因为，别名分析 Pass——aa-eval流水线是顺序执行的，并且当 Pass 的分析结果不是AliasResult::MayAlias时就会结束流水线的执行。相关代码如下（定义在 llvm/lib/Analysis/AliasAnalysis.cpp 文件中）：
AliasResult AAResults::alias(const MemoryLocation &LocA,
const MemoryLocation &LocB, AAQueryInfo &AAQI) {
AliasResult Result = AliasResult::MayAlias;
// 省略 ...
for (const auto &AA : AAs) {
Result = AA->alias(LocA, LocB, AAQI);
if (Result != AliasResult::MayAlias)
break;
}
// 省略 ...
}
本节介绍了自定义别名分析 Pass——must-aa的实现过程。
step 1： 实现自定义的 Pass
1） 添加头文件
在llvm/include/llvm/Analysis目录中新建EverythingMustAlias.h文件，内容如下：
1 #ifndef LLVM_ANALYSIS_EVERYTHINGMUSTALIAS_H
2 #define LLVM_ANALYSIS_EVERYTHINGMUSTALIAS_H
3
4 #include "llvm/Analysis/AliasAnalysis.h"
5 #include "llvm/Pass.h"
6 #include <memory>
7
8 namespace llvm {
9
10 class EverythingMustAliasResult : public AAResultBase<EverythingMustAliasResult> {
11 public:
12 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
13 AAQueryInfo &AAQI);
14 };
15
16 class EverythingMustAliasLegacyPass : public ImmutablePass {
17 public:
18 static char ID;
19
20 EverythingMustAliasLegacyPass();
21
22 bool doInitialization(Module &M) override;
23
24 EverythingMustAliasResult &getResult() { return *Result; }
25 const EverythingMustAliasResult &getResult() const { return *Result; }
26
27 private:
28 std::unique_ptr<EverythingMustAliasResult> Result;
29 };
30
31 } // end namespace llvm
32
33 #endif // LLVM_ANALYSIS_EVERYTHINGMUSTALIAS_H
上述代码的逻辑为：
第 10 行，在版本release/13.x中，别名分析的派生类（这里为EverythingMustAliasResult）都应该继承自模板类AAResultBase<T>。
第 11 行，函数alias()用于分析两个指针是否指向同一个对象，返回结果可以是AliasResult::NoAlias、AliasResult::MayAlias、AliasResult::PartialAlias或AliasResult::MustAlias。对于别名分析 Pass——must-aa，该函数总是返回AliasResult::MustAlias，表示任意两个指针都指向同一个对象。
第 16 行，传统 Pass 类EverythingMustAliasLegacyPass继承自ImmutablePass，表示该 Pass 不需要访问程序中的模块或函数等。
第 22 行，重载类ImmutablePass中的虚函数doInitialization，用于初始化EverythingMustAliasResult对象，该初始化操作仅会执行一次。
第 24~25 行，提供访问EverythingMustAliasResult对象的方法，从而允许调用者（这里为别名分析 Pass——aa-eval）将别名分析 Pass——must-aa添加到其流水线中。
第 28 行，通过智能指针std::unique_ptr维护EverythingMustAliasResult对象的生命周期，从而在类EverythingMustAliasLegacyPass析构时可以自动释放其占用的内存。
2） 添加源文件
在llvm/lib/Analysis目录中新建EverythingMustAlias.cpp文件，内容如下：
1 #include "llvm/Analysis/EverythingMustAlias.h"
2 #include "llvm/Analysis/Analysis.h"
3 #include "llvm/InitializePasses.h"
4
5 using namespace llvm;
6
7 #define DEBUG_TYPE "must-aa"
8
9 AliasResult EverythingMustAliasResult::alias(const MemoryLocation &LocA,
10 const MemoryLocation &LocB,
11 AAQueryInfo &AAQI) {
12 return AliasResult::MustAlias;
13 }
14
15 EverythingMustAliasLegacyPass::EverythingMustAliasLegacyPass()
16 : ImmutablePass(ID) {
17 initializeEverythingMustAliasLegacyPassPass(*PassRegistry::getPassRegistry());
18 }
19
20 bool EverythingMustAliasLegacyPass::doInitialization(Module &M) {
21 Result.reset(new EverythingMustAliasResult());
22 return false;
23 }
24
25 char EverythingMustAliasLegacyPass::ID = 0;
26
27 INITIALIZE_PASS(EverythingMustAliasLegacyPass, DEBUG_TYPE,
28 "Everything Alias (always returns 'must' alias)", true, true)
29
30 ImmutablePass *llvm::createEverythingMustAliasLegacyPass() {
31 return new EverythingMustAliasLegacyPass();
32 }
执行如下命令完成编译安装后，运行以下测试程序观察自定义别名分析 Pass——must-aa的分析结果。
step 1： 编译安装
$ ninja -j8
$ sudo ninja install
安装完成后，查看默认的opt工具是否包含选项must-aa：
$ opt --help | grep must-aa
--must-aa - Everything Alias (always returns 'must' alias)
step 2： 运行测试程序
1） 测试程序
test.c 的内容如下：
void foo(int *out) {
int x = *out;
for (int i = 0; i < 10; i++) {
if (x % 2 == 0) {
x += i;
}
else {
x -= i;
}
}
*out = x;
}
2） 生成 LLVM IR 汇编文件
$ clang -S -emit-llvm test.c -o test.ll
3） 运行
$ opt -must-aa -aa-eval -disable-output test.ll
输出结果如下：
===== Alias Analysis Evaluator Report =====
15 Total Alias Queries Performed
0 no alias responses (0.0%)
0 may alias responses (0.0%)
0 partial alias responses (0.0%)
15 must alias responses (100.0%)
Alias Analysis Evaluator Pointer Alias Summary: 0%/0%/0%/100%
Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!
从上面的结果可以看出，别名分析 Pass——must-aa对测试程序 test.ll 共进行了 15 次别名分析。另外，通过如下的-print-alias-sets选项，可以看出别名分析涉及如下 5 个指针：i32** %out.addr、i32* %0、i32* %x、i32* %i和i32* %10。
那么，上述结果中的 15 次是如何得到的？
通过调试发现，除了上述 5 个指针以外，还有另外一个指针i32* %out，即函数foo的参数。这样，别名分析共涉及 6 个指针，别名分析的次数为 C62，等于 15。也就是说，每两个指针之间都需要比较一次。
4） 打印 LLVM IR 函数中指针所在的指令（optional）
$ opt -print-alias-sets -must-aa -aa-eval -disable-output test.ll
输出结果如下：
Alias sets for function 'foo':
Alias Set Tracker: 1 alias sets for 5 pointer values.
AliasSet[0x5609724cba30, 5] must alias, Mod/Ref Pointers: (i32** %out.addr, LocationSize::upperBound(8)), (i32* %0, LocationSize::precise(4)), (i32* %x, LocationSize::precise(4)), (i32* %i, LocationSize::precise(4)), (i32* %10, LocationSize::precise(4))
===== Alias Analysis Evaluator Report =====
15 Total Alias Queries Performed
0 no alias responses (0.0%)
0 may alias responses (0.0%)
0 partial alias responses (0.0%)
15 must alias responses (100.0%)
Alias Analysis Evaluator Pointer Alias Summary: 0%/0%/0%/100%
Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!
本文所实现的别名分析 Pass——must-aa旨在了解别名分析的运行流程，而不涉及具体算法实现。该 Pass 认为任意两个指针都指向同一个对象。
在release/13.x版本的 LLVM 源码中，别名分析的派生类都应该继承自模板类llvm::AAResultBase<T>，并且实现函数alias()用于分析两个指针是否指向同一个对象。其可能的返回值及意义如下：
AliasResult::NoAlias，表示两个指针不可能指向同一个对象。
AliasResult::MayAlias，表示两个指针可能指向同一个对象。
AliasResult::PartialAlias，表示两个指针所指向的对象有重叠部分。
AliasResult::MustAlias，表示两个指针一定指向同一个对象。
要运行自定义的别名分析 Pass，我们需要将其注册到别名分析 Pass——aa-eval的流水线中。目前，该流水线是顺序执行的，并且当 Pass 的分析结果不是AliasResult::MayAlias时就会结束流水线的执行。这意味着，需要考虑自定义别名分析 Pass 适合放在流水线的什么位置。
除此之外，通过测试程序可以发现，程序中的每两个指针之间都需要比较一次。
下一篇：上一级目录