本文分享自華為雲社區《華為雲論壇_雲計算論壇_開發者論壇_技術論壇-華為雲》，作者：畢昇小助手。
1.簡介别名分析是編譯器理論中的一種技術，用于确定存儲位置是否可以以多種方式訪問。如果兩個指針指向相同的位置，則稱這兩個指針為别名。 但是，它不能與指針分析混淆，指針分析解決的問題是一個指針可能指向哪些對象或者指向哪些地址，而别名分析解決的是兩個指針指向的是否是同一個對象。指針分析和别名分析通常通過靜态代碼分析來實現。
别名分析在編譯器理論中非常重要，在代碼優化和安全方面有着非常廣泛且重要的應用。編譯器級優化需要指針别名信息來執行死代碼消除（删除不影響程序結果的代碼）、冗餘加載/存儲指令消除、指令調度（重排列指令）等。編譯器級别的程序安全使用别名分析來檢測内存洩漏和内存相關的安全漏洞。
2.别名分析分類别名分析種類繁多，通常按如下屬性進行分類：域敏感（field-sensitivity）、過程内分析（Intra-Procedural）v.s.過程間分析（Inter-Procedural）、上下文敏感度（context-sensitivity）和流敏感度（flow-sensitivity）。
2.1 域敏感（Field-Sensitivity）域敏感是對用戶自定義類型進行分析的一種策略（亦可以處理數組）。在域敏感維度共有三種分析策略：域敏感（field-sensitive）、域非敏感（field-insensitive）、域基礎分析（field-based）。以下面代碼為例：
struct Test {
int field1;
int field2;
}
Test a1;
Test a2;
Note：field這裡為結構體或者類的數據成員。
域非敏感：對每個對象建模，而對對象中的成員不進行處理；其建模後的結果如下圖，僅有a1.*和a2.*的區别：
域基礎分析：僅對結構體中的成員進行建模，而不感知對象。其建模後的結果如下圖，僅有*.field1和*.field2：
域敏感：既對對象建模，又對成員變量進行處理。其建模後的結果如下圖，有a1.field1、a1.field2、a2.field1、a2.field2：
處理數組時，相同的原則亦适用。以C整數數組為例：int a[10]，域非敏感分析僅使用一個節點建模：a[*]，而域敏感分析創建10個節點：a[0]、a[1]、...、a[9]。
2.2 過程内分析（Intra-Procedural）v.s.過程間分析（Inter-Procedural）總結：域敏感别名分析準确性高，但是當存在嵌套結構或者大數組時，節點數量會迅速增加，分析成本也會陡然上升。
過程内分析僅分析函數體内部的指針，并沒有考慮與其他函數之間的相互影響。需要特别指出的是，過程内分析當處理包含指針入參的函數或者返回指針的函數時，其分析可能不夠準确。相反，過程間分析會在函數調用過程中處理指針的行為。
過程内分析不易于擴展，精度較低。相比過程間分析，過程内分析更容易實現，且過程内/間分析與上下文敏感度分析高度相關，因為一個上下文敏感分析必定是一個過程間分析。
2.3 上下文敏感度（Context-Sensitivity）上下文敏感度用來控制函數調用該如何分析。有兩種分析方法：上下文敏感（context-sensitive） 和上下文非敏感（context-insensitive）。上下文敏感在分析函數調用的目标（被調用者）時考慮調用上下文（調用者）。以如下代碼為參考[1]：
1 public static void main(String[] args) {
2 String name1 = getName(3); // Tainted
3 String sql1 = "select * from user where name = " name1;
4 sqlExecute(sql1); // Taint Sink
5
6 String name2 = getName(-1); // Not Tainted
7 String sql2 = "select * from user where name = " name2;
8 sqlExecute(sql2);
9 }
10
11 private static String getName(int x) {
12 if (x > 0) {
13 return System.getProperty("name");
14 } else {
15 return "zhangsan";
16 }
17 }
如上所示，getName()方法基于入參的不同，會返回不同的結果，在第2行和第6行，獲取到的name1和name2的污點信息不同，當入參為3時，返回的是一個從環境變量中獲取的污染的數據，導緻sql注入，而當入參為-1時，返回的是一個常量，不是污染數據，不會有問題。 在上下文敏感的分析中，在第4行應該報一個sql注入問題，而在第8行則不應該報sql注入問題。而上下文非敏感的分析中，不考慮傳入參數的不同，getName()方法則全部返回一個{System.getProperty("name")}∨{zhangsan}，從而導緻第4行和第8行都會報一個sql注入的問題。
上下文敏感别名分析需要有一種方法，為函數getName創建抽象描述，以便每次調用它時，分析器都可以将調用上下文應用于抽象描述。
2.4 流敏感度Flow-Sensitivity總結：上下文敏感分析比較準确，但是增加了複雜度。
流敏感度是一種是否考慮代碼順序的原則。有兩種方法：流敏感（flow-sensitive）和流非敏感（flow-insensitive）。
流非敏感不考慮代碼順序，并為整個程序生成一組别名分析結果，而流敏感考慮代碼順序，計算程序中每個指針出現的位置的别名信息。以如下代碼為例：
1 int a,b;
2 int *p;
3 p = &a;
4 p = &b;
流非敏感的分析結果是針對整個代碼塊，其結果應該是：指針p可能指向變量a或者變量b。流敏感生成的别名信息是，在第3行，指針p指向變量a，在第4行以後指針p指向變量b。
3.别名分析常見算法介紹Note：當程序具有許多條件語句、循環或遞歸函數時，流敏感分析的複雜性會大大增加。要執行流敏感分析，需要完整的控制流圖。因此，流敏感分析非常精确，但對于大多數情況來說，它的分析成本過高，無法在整個程序上執行。
常見的别名算法共有三種：Andersen's指針分析算法、Steensgaard's指針分析算法和數據結構分析算法。
Andersen's指針分析是一種流非敏感和上下文非敏感的分析算法。Andersen's指針分析算法複雜度較高，實踐應用性較差，其時間複雜度為，其中n為指針節點個數。
Steensgaard's指針分析算法也是一種流非敏感，上下文非敏感且域非敏感的别名分析算法。其時間複雜度較低，實現相對簡單，實踐應用廣，其時間複雜度為，其中無限接近于1，但是其别名分析的準确性較低。
數據結構分析算法是一種流非敏感，上下文敏感和域敏感的算法。其時間複雜度較低，為O(n * log(n)) ，應用性較好，但是由于不支持MustAlias（參考“AliasAnalysis Class概覽”章節），導緻其應用有局限性。
4.别名分析在LLVM中的應用與實現4.1 應用别名分析在代碼優化和安全方面有着非常重要且廣泛的應用，以下面C代碼為例，來簡單介紹别名分析在代碼優化方面的應用[2]。
int foo (int __attribute__((address_space(0)))* a,
int __attribute__((address_space(1)))* b) {
*a = 42;
*b = 20;
return *a;
}
__attribute__屬性指定了變量a指向地址0，變量b指向地址1。我們知道在ARM架構中，地址0和地址1是完全不同的，修改地址0中的内存永遠不會修改地址1中的内存。以下為該函數可能生成的LLVM IR信息：
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
}
第一個store将42存儲到變量a指向的地址，第二個store指令将20存儲到變量b指向的地址。%0 = ... 指向的行将變量a中的值加載到一個臨時變量0中，并在最後一行返回該臨時變量0。
上述代碼是未對foo函數進行優化的情況，下面我們考慮對foo函數進行優化。
我們優化後的代碼可能如下：删除了load指令對應的行，最後一行直接返回了常量42。
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指向的地址不會相互影響時有效。例如：當我們給foo函數傳遞的指針相互影響時：
int i = 0;
int result = foo(&i, &i);
在未開啟優化的版本中，變量i将先被設置為42，然後被設置為20，最後返回20。然而，在優化版本中，雖然我們執行了兩次store操作依次将42、20賦值給變量i，但是返回值是42，而不是20。因此優化版本破壞了foo函數本身的行為。
如果應用了别名分析，編譯器能夠合理的執行上述優化。在執行優化前判斷入參a和b是否為别名，如果是别名，則不執行删除load指令對應行的操作，否則執行删除操作。
4.2 實現本文以LLVM16.0.0版本為參考，從代碼接口入手，帶領大家學習别名分析的代碼實現。
LLVM AliasAnalysis類是LLVM系統中客戶使用和别名分析實現的主要接口，或者說一個“基類” 。除了簡單的别名分析信息外，這個類還聲明了Mod/Ref信息，從而使強大的分析和轉換能夠很好地協同工作。
源碼參考鍊接：AliasAnalysis.h[3]、AliasAnalysis.cpp[4]。
4.2.1 基礎知識MemoryLocation：LLVM中對内存地址的描述，主要應用在别名分析中，我們需要掌握該類中三個屬性：
其中，Ptr表示内存開始地址，Size表示内存大小，AATags是描述内存位置别名的metadata節點集合 。
4.2.2 AliasAnalysis Class 概覽AliasAnalysis類定義了各種别名分析實現應該支持的接口。這個類導出兩個重要的枚舉:AliasResult和ModRefResult，它們分别表示别名查詢或mod/ref查詢的結果。
1、關鍵代碼如下，AliasAnalysis為AAResults類别名：
2、AliasResult關鍵代碼如下：
其中NoAlias表示兩個内存對象沒有任何重疊區域；MayAlias表示兩個指針可能指向同一對象；PartialAlias表示兩個内存對象對應的地址空間有重疊；MustAlias表示兩個内存對象總是從同一位置開始。
3、ModRefResult關鍵代碼
其中NoModRef表示訪問内存的操作既不會修改該内存也不會引用該内存； Ref表示訪問内存的操作會可能引用該内存；Mod表示訪問内存的操作可能會修改該内存；ModRef表示訪問内存的操作既可能引用該内存也可能修改該内存。
alias接口其接口定義如下：
别名方法是用于确定兩個MemoryLocation對象是否相互别名的主要接口。它接受兩個MemoryLocation對象作為輸入，并根據需要返回MustAlias、PartialAlias、MayAlias或NoAlias。 與所有AliasAnalysis接口一樣，alias方法要求其入參的兩個MemoryLocation對象定義在同一個函數中，或者至少有一個值是常量。
其接口實現如下：
getModRefInfo 接口
getModReInfo方法返回關于給定的指令執行是否可以讀取或修改給定内存位置的信息。Mod/Ref信息具有保守性：如果一條指令可能讀或寫一個位置，則返回ModRef。 其接口定義衆多，我們以如下接口為例來進行學習。
其接口實現如下：
從上述代碼可知，處理共分為四步：
（1）遍曆AAs，如果發現其任一結果是NoModRef，則直接返回，對應代碼行228-234；
（2）調用節點（call）操作中是否訪問了一個在LLVM IR中無法訪問的地址，如果是的話，直接返回NoModRef，否則獲取其調用節點的ModRefInfo信息，對應代碼行239-240；
（3）處理調用節點中指針入參的ModRefInfo信息，如果發現是NoModRef，則直接返回NoModRef，否則将ModRefInfo信息和之前的結果合并，對應代碼行247-266；
（4）如果getModRefInfo函數中的入參Loc指定的内存地址具有常量屬性并且ModRefInfo信息包含Mod，則調用節點一定不會修改Loc内存，因此需要将Ref屬于與之前的結果做邏輯與操作，對應代碼行271-272。
4.2.3 LLVM中已經實現的别名分析-basic-aa pass-basic-aa pass是一種激進的本地分析，它提供許多重要的事實信息[5]：
這個pass實現了一個簡單的對内部全局變量（該變量的地址沒有被獲取過）進行上下文敏感的mod/ref分析和别名分析。 如果某個全局變量的地址沒有被獲取，則該pass可以得出如下結論：沒有指針作為該全局變量的别名。該pass還會識别從不訪問内存或從不讀取内存的函數。這允許某些指定的優化(例如GVN)完全消除調用指令。
這個pass的真正威力在于它為調用指令提供了上下文敏感的mod/ref信息。這使優化器清楚的了解到對于某些函數的調用不會破壞或讀取全局變量的值，從而允許消除加載和存儲指令。
Note：該pass在使用範圍上有一定限制，僅支持沒有被取過地址的全局變量，但是該pass分析速度非常快。
除了上述pass外，LLVM中還實現了cfl-steens-aa、cfl-anders-aa、tbaa、scev-aa。目前LLVM中O1，O2，O3優化默認開啟的别名分析是basic-aa，globals-aa和tb-aa。
5.寫在最後編譯器技術從20世紀50年代起，已經發展了近70年的曆史，但是編譯器技術發展到今天，依然是一個非常熱門的技術，各大硬件廠商都在開發自己的編譯器，包括因特爾推出的Inter C 、ARM公司推出的armclang以及華為推出的畢昇編譯器等，且上述三款編譯器都是基于LLVM開發。
編譯器技術是一門龐大且繁雜的技術，對于初學者來說，這條學習之路道阻且長，盼那些熱愛這門技術的趕路人能夠行而不辍，未來可期。
點擊下方，第一時間了解華為雲新鮮技術~
華為雲博客_大數據博客_AI博客_雲計算博客_開發者中心-華為雲
,更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
