【LLVM】AliasAnalysis别名分析的介绍与使用
一、介绍
Alias Analysis (又名 Pointer Analysis)是用于确定两个指针是否指向内存中的同一对象，这里有很多不同的别名分析算法，分为几种类型：流敏感vs流非敏感、上下文敏感vs上下文非敏感、域敏感vs域非敏感、基于一致性的vs基于子集的。传统的别名分析用于回答must、may、no的问题，也即两个指针总是指向同一对象，可能指向同一对象以及绝不会指向同一对象。(SSA—静态单一赋值，将同一变量名用多个名表示，被赋值的变量名不会重复，便于寻找变量的产生与使用点)。
LLVM AliasAnalysis类是实现别名分析的基础类，能够提供简单的别名分析信息，且能提供Mod/Ref信息，有利于进行更复杂的分析。本文介绍了该接口的实现与使用。
首先，我们来了解一下别名分析，以及别名分析该如何使用。
1.别名分析的作用
例如以下c代码：
int foo (int __attribute__((address_space(0)))* a,
int __attribute__((address_space(1)))* b) {
*a = 42;
*b = 20;
return *a;
}
转换成llvm如下：
define i32 @foo(i32 addrspace(0)* %a, i32 addrspace(1)* %b) #0 {
entry:
store i32 42, i32 addrspace(0)* %a, align 4
store i32 20, i32 addrspace(1)* %b, align 4
%0 = load i32, i32* %a, align 4
ret i32 %0
}
现在需要对foo进行优化，去掉不必要的load：
define i32 @foo(i32 addrspace(0)* %a, i32 addrspace(1)* %b) #0 {
entry:
store i32 42, i32 addrspace(0)* %a, align 4
store i32 20, i32 addrspace(1)* %b, align 4
ret i32 42
}
但是这个优化的前提是，a和b不能别名，否则会导致错误如下：
int i = 0;
int result = foo(&i, &i);
以上可以看到，以上调用会使a和b别名，本应该返回20，结果因为优化的缘故返回了42，导致错误。所以编译器只有确定两个指针不会产生别名时，才能进行以上优化。
2.使用方法
一种实现是利用 llvm::AAResultBase，如果我们的目标是TAR，则可以创建一个从AAResultBase<TARAAResult>继承的类TARAAResult：
class TARAAResult : public AAResultBase<TARAAResult> {
public:
explicit TARAAResult() : AAResultBase() {}
TARAAResult(TARAAResult &&Arg) : AAResultBase(std::move(Arg)) {}
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
};
alias函数的输入是两个MemoryLocation，返回AliasResult。返回结果显示内存对象绝不别名、可能别名、部分别名或正好别名。
AliasResult TARAAResult::alias(const MemoryLocation &LocA,
const MemoryLocation &LocB) {
auto AsA = LocA.Ptr->getType()->getPointerAddressSpace();
auto AsB = LocB.Ptr->getType()->getPointerAddressSpace();
if (AsA != AsB) {
return NoAlias;
}
// Forward the query to the next analysis.
return AAResultBase::alias(LocA, LocB);
}
二、AliasAnalysis类总览
AliasAnalysis定义了别名分析必须支持的接口，并且导出了两个重要方法，AliasResult和ModRefResult输出别名结果和mod/ref结果。
AliasAnalysis接口能够用不同的方式输出内存信息，例如，内存对象表示成开始地址和size，函数调用表示成实际的call和invoke指令。AliasAnalysis接口也提供了helper方法，允许你获取任意指令的mod/ref信息。
1.指针表示
AliasAnalysis类提供了不同的方法，来query两个内存对象是否别名，以及函数调用是否可以修改或读内存对象。对于所有query，内存对象表示为开始地址(符号化的LLVM值)+size。
内存对象的表示对于正确的别名分析至关重要，例如以下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 */
}
对于以上代码，basicaa pass将消除对C[0]和C[1]的store，因为他们都是访问不同地址的单个字节，互不干扰，Loop Invariant Code Motion (LICM) pass会使用store motion移除循环中的store。
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的store会分开，因为访问&C[0]元素是2个字节访问；如果query中没有size信息，第一个案例也会别名。
2.alias方法
alias方法用于确定两个内存对象是否别名，它输入两个内存对象，输出MustAlias, PartialAlias, MayAlias, 或 NoAlias。对于所有AliasAnalysis接口，alias方法要求两个指针值在同一个函数中定义，或者至少1个值是常数。
NoAlias表示两个内存对象没有任何重叠区域；MayAlias表示两个指针可能指向同一对象；PartialAlias表示两个内存对象可能有重叠；MustAlias表示两个内存对象总是从同一位置开始。
3.GetModRefInfo方法
GetModRefInfo方法返回信息是，指令是否可以读或修改某个内存区域。Mod/Ref信息是保守的，如果一条指令可能读或写某区域，就返回ModRef。
4.其他AliasAnalysis方法
（1）pointsToConstantMemory方法
若能确定指针仅指向不变的内存区域(函数，全局常量，null指针)则返回true，该信息可以优化mod/ref信息：因为不变的内存区域是不能被修改的。
(2)doesNotAccessMemory和onlyReadsMemory方法
若确定函数从不读写内存，或者函数仅从常量内存读，则doesNotAccessMemory返回true。
若确定函数仅从非易失性内存读，则onlyReadsMemory返回true。注意，满足doesNotAccessMemory方法的所有函数也都满足onlyReadsMemory。
三、实现新的AliasAnalysis
1.不同的Pass类型
选择使用哪种LLVM pass来做别名分析取决于你想要解决哪种问题。
- 做过程间分析，用Pass
- 做局部函数的分析，用FunctionPass子类
- 若不需要看程序，则选择ImmutablePass
除了继承以上pass，你也需要继承AliasAnalysis接口，当然，也可以用RegisterAnalysisGroup模板去注册AliasAnalysis实现。
2.进行初始化所需的调用
所写的AliasAnalysis的子类需调用AliasAnalysis基类的两个方法：getAnalysisUsage和InitializeAliasAnalysis。例如，实现你的getAnalysisUsage时，除了声明pass依赖，还需显式调用AliasAnalysis::getAnalysisUsage方法。
void getAnalysisUsage(AnalysisUsage &AU) const {
AliasAnalysis::getAnalysisUsage(AU);
// declare your dependencies here.
}
另外，在你的run方法中需调用InitializeAliasAnalysis方法（Pass—run；FunctionPass—runOnFunction；ImmutablePass—InitializePass）。
bool run(Module &M) {
InitializeAliasAnalysis(this);
// Perform analysis here...
return false;
}
3.需要覆盖的方法
在你的AliasAnalysis子类中必须覆盖getAdjustedAnalysisPointer方法，例如：
void *getAdjustedAnalysisPointer(const void* ID) override {
if (ID == &AliasAnalysis::ID)
return (AliasAnalysis*)this;
return this;
}
4.可指定的接口
所有AliasAnalysis虚方法都默认为其他别名分析提供一个链接，最终能返回正确结果(为alias query和mod/ref query返回May和Mod/Ref)，根据你分析的功能，覆盖相应的接口即可。
5.AliasAnalysis链接行为
除了-no-aa pass，每个分析pass都链接到另一个别名分析的实现(例如，可以使用"-basicaa -ds-aa -licm"来从多个别名分析达到最大优化)。别名分析会自动处理你未覆盖的方法，对于已覆盖的方法，若需返回AmayAlias或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);
}
除了分析查询，如果你需要覆盖某方法，需将更新通知传给超类，这样就允许所有别名分析进行更新。
6.更新代码转换后的分析结果
别名分析最初用于建立程序的静态快照，但用户也用于进行代码转换。所有别名分析都需要更新分析结果，以反映代码转换所做的变换。AliasAnalysis接口提供了4个方法来更新程序变化后的分析结果。
(1)deleteValue方法
当从程序删除某个指令或值(包括不使用指针的值)时调用deleteValue方法。通常，别名分析会保留数据结构，这些数据结构包含程序中每个值的条目。调用此方法时，则删除指定值的任何条目（如果存在）。
(2)copyValue方法
当程序引入新的值时调用copyValue方法。通常不会引入程序中不存在的值(编译器安全转换)，所以这是引入新值的唯一方法，这个方法指示新值和拷贝值有相同的属性。
(3)replaceWithNewValue方法
用新值替换旧值，该方法不能被别名分析实现所覆盖。
(4)addEscapingUse方法
当指针的使用导致之前计算的分析结果无效时，调用addEscapingUse方法。该方法会提供保守的返回，或者重新计算分析结果。
总之，只要有新的指针使用，就需要调用该方法，除了一下3种情况：
- 指针的bitcast或getelementptr
- 通过指针来store，但并非存指针
- 通过指针load
四、使用别名分析结果
1.使用MemoryDependenceAnalysis Pass
memdep pass使用别名分析来提供内存使用指令的高级依赖信息，例如，告诉你哪个store提供给了load。它也使用缓存等技术提高效率，一般用于Dead Store Elimination, GVN 和 memcpy优化。
2.使用AliasSetTracker类
有些代码转换需要某个代码区域内的活跃的别名集，而不是成对的别名信息。AliasSetTracker类可以根据AliasAnalysis接口提供的成对的别名分析信息，高效的构建所需的别名集。
首先需要调用add方法对AliasSetTracker进行初始化，添加该代码区域内可能导致别名的指令。当别名集构建完成后，你可以利用AliasSetTrackerbegin() / end()方法迭代访问该别名集。
AliasSetTracker构造的AliasSets是不相交的，计算mod/ref信息，并跟踪记录该集合所有指针是否是Must aliases。
例如，Loop Invariant Code Motion pass使用AliasSetTracker来计算每个循环嵌套的别名集，如果循环的某个AliasSet没有被修改，则该集合所有的load指令可能被提出循环。如果所有别名集是store to 和must alias集，则store 在循环外部使用，这样在循环时将内存位置放入进村器。只有当指针参数是循环不变的，才采用这些转换。
3.直接使用AliasAnalysis接口
如果这些功能类都用不到，你可以直接使用AliasAnalysis类。尽量使用高级方法，以获取更高的准确率和效率。
五、现有的别名分析实现
1.可用的AliasAnalysis实现
(1)-no-aa pass
不做别名分析。
(2)-basicaa pass
(3)-globalsmodref-aa pass
(4)-steens-aa pass
(5)-ds-aa pass
(6)-scev-aa pass
注意：basicaa和steens-aa这类标准的LLVM pass太耗时了，Anderson Analysis也很耗时耗内存，已经有一些工作在优化别名分析。
2.别名分析驱动的转换
(1)-adce pass
(2)-licm pass
(3)-argpromotion pass
(4)-gvn -memcpyopt -dse pass
3.用于调试和评估的client
命令：% opt -ds-aa -aa-eval foo.bc -disable-output -stats
(1)-print-alias-sets pass
% opt -ds-aa -print-alias-sets -disable-output
(2)-aa-eval pass
4.内存依赖分析
正在将MemoryDependenceAnalysis迁移到MemorySSA。
参考：
https://llvm.org/docs/AliasAnalysis.html
