編譯器優化：何為別名分析

摘要：別名分析是編譯器理論中的一種技術，用於確定儲存位置是否可以以多種方式存取。

本文分享自華為雲社群《編譯器優化那些事兒（6）：別名分析概述》，作者：畢昇小助手。

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]：

public static void main(String[] args) {
    String name1 = getName(3);  // Tainted
    String sql1 = "select * from user where name = " + name1;
sqlExecute(sql1);  // Taint Sink

    String name2 = getName(-1);  // Not Tainted
    String sql2 = "select * from user where name = " + name2;
sqlExecute(sql2);
}

private static String getName(int x) {
if (x > 0) {
return System.getProperty("name");
 } else {
return "zhangsan";
 }
}

如上所示，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）。

流非敏感不考慮程式碼順序，併為整個程式生成一組別名分析結果，而流敏感考慮程式碼順序，計算程式中每個指標出現的位置的別名資訊。以如下程式碼為例：

int a,b;
int *p;
 p = &a;
 p = &b;

流非敏感的分析結果是針對整個程式碼塊，其結果應該是：指標p可能指向變數a或者變數b。流敏感生成的別名資訊是，在第3行，指標p指向變數a，在第4行以後指標p指向變數b。

Note：當程式具有許多條件語句、迴圈或遞迴函數時，流敏感分析的複雜性會大大增加。要執行流敏感分析，需要完整的控制流圖。因此，流敏感分析非常精確，但對於大多數情況來說，它的分析成本過高，無法在整個程式上執行。

3.別名分析常見演演算法介紹

常見的別名演演算法共有三種：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]：

不同的全域性變數、堆疊分配和堆分配永遠不能別名。
全域性變數、棧分配的變數和堆分配變數永遠不會和空指標別名。
結構體中的不同欄位不能別名。
同一陣列，索引不同的兩個物件不能別名。
許多通用的標準C庫函數從不存取記憶體或唯讀取記憶體。

-globals-aa pass

這個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開發。

編譯器技術是一門龐大且繁雜的技術，對於初學者來說，這條學習之路道阻且長，盼那些熱愛這門技術的趕路人能夠行而不輟，未來可期。

參考

[1]https://bbs.huaweicloud.com/blogs/234041

[2]https://blog.tartanllama.xyz/llvm-alias-analysis/

[3]https://llvm.org/doxygen/AliasAnalysis_8h_source.html

[4]https://llvm.org/doxygen/AliasAnalysis_8cpp_source.html

[5]https://llvm.org/docs/AliasAnalysis.html

點選關注，第一時間瞭解華為雲新鮮技術~