一、介紹
Alias Analysis (又名 Pointer Analysis)是用于確定兩個指針是否指向內(nèi)存中的同一對象，這里有很多不同的別名分析算法决采，分為幾種類型：流敏感vs流非敏感脱羡、上下文敏感vs上下文非敏感罚渐、域敏感vs域非敏感捏膨、基于一致性的vs基于子集的秧均。傳統(tǒng)的別名分析用于回答must、may脊奋、no的問題熬北，也即兩個指針總是指向同一對象疙描，可能指向同一對象以及絕不會指向同一對象诚隙。(SSA—靜態(tài)單一賦值，將同一變量名用多個名表示起胰，被賦值的變量名不會重復久又，便于尋找變量的產(chǎn)生與使用點)。
LLVM AliasAnalysis類是實現(xiàn)別名分析的基礎(chǔ)類效五，能夠提供簡單的別名分析信息地消，且能提供Mod/Ref信息，有利于進行更復雜的分析畏妖。本文介紹了該接口的實現(xiàn)與使用脉执。
首先，我們來了解一下別名分析戒劫，以及別名分析該如何使用半夷。
1.別名分析的作用
例如以下c代碼：
int foo (int __attribute__((address_space(0)))* a,
int __attribute__((address_space(1)))* b) {
*a = 42;
*b = 20;
return *a;
}
轉(zhuǎn)換成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
}
現(xiàn)在需要對foo進行優(yōu)化婆廊，去掉不必要的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
}
但是這個優(yōu)化的前提是，a和b不能別名巫橄，否則會導致錯誤如下：
int i = 0;
int result = foo(&i, &i);
以上可以看到淘邻，以上調(diào)用會使a和b別名，本應該返回20湘换，結(jié)果因為優(yōu)化的緣故返回了42宾舅，導致錯誤。所以編譯器只有確定兩個指針不會產(chǎn)生別名時彩倚，才能進行以上優(yōu)化筹我。
2.使用方法
一種實現(xiàn)是利用 llvm::AAResultBase，如果我們的目標是TAR帆离，則可以創(chuàng)建一個從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函數(shù)的輸入是兩個MemoryLocation崎溃，返回AliasResult。返回結(jié)果顯示內(nèi)存對象絕不別名盯质、可能別名袁串、部分別名或正好別名。
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輸出別名結(jié)果和mod/ref結(jié)果王悍。
AliasAnalysis接口能夠用不同的方式輸出內(nèi)存信息破镰，例如，內(nèi)存對象表示成開始地址和size压储，函數(shù)調(diào)用表示成實際的call和invoke指令鲜漩。AliasAnalysis接口也提供了helper方法，允許你獲取任意指令的mod/ref信息集惋。
1.指針表示
AliasAnalysis類提供了不同的方法孕似，來query兩個內(nèi)存對象是否別名，以及函數(shù)調(diào)用是否可以修改或讀內(nèi)存對象刮刑。對于所有query喉祭，內(nèi)存對象表示為開始地址(符號化的LLVM值)+size。
內(nèi)存對象的表示對于正確的別名分析至關(guān)重要雷绢，例如以下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，因為他們都是訪問不同地址的單個字節(jié)翘紊，互不干擾蔽氨，Loop Invariant Code Motion (LICM) pass會使用store motion移除循環(huán)中的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個字節(jié)訪問；如果query中沒有size信息坊饶，第一個案例也會別名泄伪。
2.alias方法
alias方法用于確定兩個內(nèi)存對象是否別名，它輸入兩個內(nèi)存對象匿级，輸出MustAlias, PartialAlias, MayAlias, 或 NoAlias蟋滴。對于所有AliasAnalysis接口，alias方法要求兩個指針值在同一個函數(shù)中定義痘绎，或者至少1個值是常數(shù)津函。
NoAlias表示兩個內(nèi)存對象沒有任何重疊區(qū)域；MayAlias表示兩個指針可能指向同一對象孤页；PartialAlias表示兩個內(nèi)存對象可能有重疊尔苦；MustAlias表示兩個內(nèi)存對象總是從同一位置開始。
3.GetModRefInfo方法
GetModRefInfo方法返回信息是行施，指令是否可以讀或修改某個內(nèi)存區(qū)域允坚。Mod/Ref信息是保守的，如果一條指令可能讀或?qū)懩硡^(qū)域蛾号，就返回ModRef稠项。
4.其他AliasAnalysis方法
（1）pointsToConstantMemory方法
若能確定指針僅指向不變的內(nèi)存區(qū)域(函數(shù)，全局常量鲜结，null指針)則返回true展运，該信息可以優(yōu)化mod/ref信息：因為不變的內(nèi)存區(qū)域是不能被修改的。
(2)doesNotAccessMemory和onlyReadsMemory方法
若確定函數(shù)從不讀寫內(nèi)存精刷，或者函數(shù)僅從常量內(nèi)存讀拗胜，則doesNotAccessMemory返回true。
若確定函數(shù)僅從非易失性內(nèi)存讀怒允，則onlyReadsMemory返回true埂软。注意，滿足doesNotAccessMemory方法的所有函數(shù)也都滿足onlyReadsMemory误算。
三仰美、實現(xiàn)新的AliasAnalysis
1.不同的Pass類型
選擇使用哪種LLVM pass來做別名分析取決于你想要解決哪種問題。
- 做過程間分析儿礼，用Pass
- 做局部函數(shù)的分析，用FunctionPass子類
- 若不需要看程序庆寺，則選擇ImmutablePass
除了繼承以上pass蚊夫，你也需要繼承AliasAnalysis接口，當然懦尝，也可以用RegisterAnalysisGroup模板去注冊AliasAnalysis實現(xiàn)知纷。
2.進行初始化所需的調(diào)用
所寫的AliasAnalysis的子類需調(diào)用AliasAnalysis基類的兩個方法：getAnalysisUsage和InitializeAliasAnalysis壤圃。例如，實現(xiàn)你的getAnalysisUsage時琅轧，除了聲明pass依賴伍绳，還需顯式調(diào)用AliasAnalysis::getAnalysisUsage方法。
void getAnalysisUsage(AnalysisUsage &AU) const {
AliasAnalysis::getAnalysisUsage(AU);
// declare your dependencies here.
}
另外乍桂，在你的run方法中需調(diào)用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虛方法都默認為其他別名分析提供一個鏈接，最終能返回正確結(jié)果(為alias query和mod/ref query返回May和Mod/Ref)憋沿，根據(jù)你分析的功能旺芽，覆蓋相應的接口即可。
5.AliasAnalysis鏈接行為
除了-no-aa pass辐啄，每個分析pass都鏈接到另一個別名分析的實現(xiàn)(例如采章，可以使用"-basicaa -ds-aa -licm"來從多個別名分析達到最大優(yōu)化)。別名分析會自動處理你未覆蓋的方法壶辜，對于已覆蓋的方法共缕，若需返回AmayAlias或Mod/Ref結(jié)果，只需返回超類計算的結(jié)果士复。
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.更新代碼轉(zhuǎn)換后的分析結(jié)果
別名分析最初用于建立程序的靜態(tài)快照，但用戶也用于進行代碼轉(zhuǎn)換冗荸。所有別名分析都需要更新分析結(jié)果承璃，以反映代碼轉(zhuǎn)換所做的變換。AliasAnalysis接口提供了4個方法來更新程序變化后的分析結(jié)果蚌本。
(1)deleteValue方法
當從程序刪除某個指令或值(包括不使用指針的值)時調(diào)用deleteValue方法盔粹。通常，別名分析會保留數(shù)據(jù)結(jié)構(gòu)程癌，這些數(shù)據(jù)結(jié)構(gòu)包含程序中每個值的條目舷嗡。調(diào)用此方法時，則刪除指定值的任何條目（如果存在）嵌莉。
(2)copyValue方法
當程序引入新的值時調(diào)用copyValue方法进萄。通常不會引入程序中不存在的值(編譯器安全轉(zhuǎn)換)，所以這是引入新值的唯一方法，這個方法指示新值和拷貝值有相同的屬性中鼠。
(3)replaceWithNewValue方法
用新值替換舊值可婶，該方法不能被別名分析實現(xiàn)所覆蓋。
(4)addEscapingUse方法
當指針的使用導致之前計算的分析結(jié)果無效時援雇，調(diào)用addEscapingUse方法矛渴。該方法會提供保守的返回，或者重新計算分析結(jié)果惫搏。
總之具温，只要有新的指針使用，就需要調(diào)用該方法晶府，除了一下3種情況：
- 指針的bitcast或getelementptr
- 通過指針來store桂躏，但并非存指針
- 通過指針load
四、使用別名分析結(jié)果
1.使用MemoryDependenceAnalysis Pass
memdep pass使用別名分析來提供內(nèi)存使用指令的高級依賴信息川陆，例如剂习，告訴你哪個store提供給了load。它也使用緩存等技術(shù)提高效率较沪，一般用于Dead Store Elimination, GVN 和 memcpy優(yōu)化鳞绕。
2.使用AliasSetTracker類
有些代碼轉(zhuǎn)換需要某個代碼區(qū)域內(nèi)的活躍的別名集，而不是成對的別名信息尸曼。AliasSetTracker類可以根據(jù)AliasAnalysis接口提供的成對的別名分析信息们何，高效的構(gòu)建所需的別名集。
首先需要調(diào)用add方法對AliasSetTracker進行初始化控轿，添加該代碼區(qū)域內(nèi)可能導致別名的指令冤竹。當別名集構(gòu)建完成后，你可以利用AliasSetTrackerbegin() / end()方法迭代訪問該別名集茬射。
AliasSetTracker構(gòu)造的AliasSets是不相交的鹦蠕，計算mod/ref信息，并跟蹤記錄該集合所有指針是否是Must aliases在抛。
例如钟病，Loop Invariant Code Motion pass使用AliasSetTracker來計算每個循環(huán)嵌套的別名集，如果循環(huán)的某個AliasSet沒有被修改刚梭，則該集合所有的load指令可能被提出循環(huán)肠阱。如果所有別名集是store to 和must alias集，則store 在循環(huán)外部使用朴读，這樣在循環(huán)時將內(nèi)存位置放入進村器屹徘。只有當指針參數(shù)是循環(huán)不變的，才采用這些轉(zhuǎn)換磨德。
3.直接使用AliasAnalysis接口
如果這些功能類都用不到缘回，你可以直接使用AliasAnalysis類吆视。盡量使用高級方法典挑，以獲取更高的準確率和效率酥宴。
五、現(xiàn)有的別名分析實現(xiàn)
1.可用的AliasAnalysis實現(xiàn)
(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也很耗時耗內(nèi)存，已經(jīng)有一些工作在優(yōu)化別名分析琳水。
2.別名分析驅(qū)動的轉(zhuǎn)換
(1)-adce pass
(2)-licm pass
(3)-argpromotion pass
(4)-gvn -memcpyopt -dse pass
3.用于調(diào)試和評估的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.內(nèi)存依賴分析
正在將MemoryDependenceAnalysis遷移到MemorySSA肆糕。
參考：
https://llvm.org/docs/AliasAnalysis.html
