LLVM 別名分析基礎架構¶

簡介 ¶

別名分析 (又稱指標分析) 是一類嘗試判斷兩個指標是否可能指向記憶體中相同物件的技術。別名分析有許多不同的演算法和許多不同的分類方式：流敏感與流不敏感、上下文敏感與上下文不敏感、欄位敏感與欄位不敏感、基於聯合與基於子集等等。傳統上，別名分析會以 Must、May 或 No 別名回應來回答查詢，表示兩個指標總是指向相同的物件、可能指向相同的物件，或是已知永遠不會指向相同的物件。

LLVM AliasAnalysis 類別是 LLVM 系統中客戶端和別名分析實作所使用的主要介面。此類別是別名分析資訊的客戶端和提供資訊的實作之間的通用介面，旨在支援廣泛的實作和客戶端 (但目前所有客戶端都假設為流不敏感)。除了簡單的別名分析資訊外，此類別還公開來自那些可以提供 Mod/Ref 資訊的實作，允許強大的分析和轉換協同工作。

本文檔包含成功實作此介面、使用它以及測試雙方所需的資訊。它還解釋了關於結果究竟意味著什麼的一些更精細的點。

`AliasAnalysis` 類別概觀 ¶

AliasAnalysis 類別定義了各種別名分析實作應支援的介面。此類別匯出兩個重要的列舉：AliasResult 和 ModRefResult，分別代表別名查詢或 mod/ref 查詢的結果。

AliasAnalysis 介面公開了關於記憶體的資訊，以幾種不同的方式表示。特別是，記憶體物件表示為起始位址和大小，函數呼叫表示為執行呼叫的實際 call 或 invoke 指令。AliasAnalysis 介面還公開了一些輔助方法，允許您取得任意指令的 mod/ref 資訊。

所有 AliasAnalysis 介面都要求在涉及多個值的查詢中，不是常數的值都在同一個函數中定義。

指標的表示法 ¶

最重要的是，AliasAnalysis 類別提供了幾種方法，用於查詢兩個記憶體物件是否互為別名、函數呼叫是否可以修改或讀取記憶體物件等等。對於所有這些查詢，記憶體物件都表示為其起始位址 (符號 LLVM Value*) 和靜態大小的組合。

將記憶體物件表示為起始位址和大小對於正確的別名分析至關重要。例如，考慮以下 (看似愚蠢但可能) 的 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 */
}

在這種情況下，basic-aa pass 會消除對 C[0] 和 C[1] 的儲存的歧義，因為它們是對相隔一個位元組的兩個不同位置的存取，並且每次存取都是一個位元組。在這種情況下，迴圈不變程式碼移動 (LICM) pass 可以使用儲存移動來從迴圈中移除儲存。相比之下，以下程式碼

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 的兩個儲存互為別名，因為對 &C[0] 元素的存取是兩個位元組的存取。如果在查詢中沒有大小資訊，即使是第一種情況也必須保守地假設存取互為別名。

`alias` 方法 ¶

alias 方法是用於判斷兩個記憶體物件是否互為別名的主要介面。它以兩個記憶體物件作為輸入，並根據情況傳回 MustAlias、PartialAlias、MayAlias 或 NoAlias。

與所有 AliasAnalysis 介面一樣，alias 方法要求兩個指標值在同一個函數中定義，或者至少其中一個值是常數。

Must、May 和 No 別名回應 ¶

當基於一個指標的任何記憶體參考與基於另一個指標的任何記憶體參考之間永遠不存在直接依賴關係時，可以使用 NoAlias 回應。最明顯的例子是當兩個指標指向不重疊的記憶體範圍時。另一個例子是當兩個指標僅用於讀取記憶體時。還有一個例子是當記憶體在透過一個指標的存取和透過另一個指標的存取之間被釋放和重新分配時 — 在這種情況下，存在依賴關係，但它是透過釋放和重新分配來調節的。

作為一個例外，是 noalias 關鍵字；「不相關」的依賴關係會被忽略。

每當兩個指標可能指向相同的物件時，就會使用 MayAlias 回應。

當已知兩個記憶體物件以某種方式重疊時，無論它們是否從相同的位址開始，都會使用 PartialAlias 回應。

只有當保證兩個記憶體物件始終從完全相同的位置開始時，才能傳回 MustAlias 回應。MustAlias 回應並不意味著指標比較相等。

`getModRefInfo` 方法 ¶

getModRefInfo 方法傳回關於指令的執行是否可以讀取或修改記憶體位置的資訊。Mod/Ref 資訊始終是保守的：如果指令可能讀取或寫入位置，則傳回 ModRef。

AliasAnalysis 類別還提供了一個 getModRefInfo 方法，用於測試函數呼叫之間的依賴關係。此方法接受兩個呼叫站點 (CS1 & CS2)，如果兩個呼叫都不寫入另一個呼叫讀取或寫入的記憶體，則傳回 NoModRef；如果 CS1 讀取 CS2 寫入的記憶體，則傳回 Ref；如果 CS1 寫入 CS2 讀取或寫入的記憶體，則傳回 Mod；如果 CS1 可能讀取或寫入 CS2 寫入的記憶體，則傳回 ModRef。請注意，此關係不是可交換的。

其他有用的 `AliasAnalysis` 方法 ¶

各種別名分析實作通常會收集其他一些資訊片段，並且可以被各種客戶端充分利用。

`getModRefInfoMask` 方法 ¶

getModRefInfoMask 方法根據關於指標是否指向全域常數記憶體 (為此它傳回 NoModRef) 或區域不變記憶體 (為此它傳回 Ref) 的知識，傳回所提供指標的 Mod/Ref 資訊的界限。全域常數記憶體包括函數、常數全域變數和空指標。區域不變記憶體是我們知道在其 SSA 值的生命週期內是不變的記憶體，但不一定是程式的生命週期：例如，readonly noalias 參數指向的記憶體在相應函數呼叫的持續時間內是已知不變的。給定記憶體位置 Loc 的 Mod/Ref 資訊 MRI，可以使用類似 MRI &= AA.getModRefInfoMask(Loc); 的語句來完善 MRI。另一個有用的慣用語是 isModSet(AA.getModRefInfoMask(Loc))；這檢查以查看給定的位置是否可以被修改。為了方便起見，還有一個方法 pointsToConstantMemory(Loc)；這與 isNoModRef(AA.getModRefInfoMask(Loc)) 是同義的。

`doesNotAccessMemory` 和 `onlyReadsMemory` 方法 ¶

這些方法用於為函數呼叫提供非常簡單的 mod/ref 資訊。doesNotAccessMemory 方法對於函數傳回 true，如果分析可以證明該函數從不讀取或寫入記憶體，或者如果該函數僅從常數記憶體讀取。具有此屬性的函數是無副作用的，並且僅依賴於其輸入參數，從而允許它們在形成常見子表達式時被消除或從迴圈中提升出來。許多常見函數都以這種方式運作 (例如，sin 和 cos)，但許多其他函數則不然 (例如，acos，它會修改 errno 變數)。

如果分析可以證明函數 (最多) 僅從非揮發性記憶體讀取，則 onlyReadsMemory 方法對於函數傳回 true。具有此屬性的函數是無副作用的，僅依賴於其輸入參數以及呼叫它們時的記憶體狀態。此屬性允許消除和移動對這些函數的呼叫，只要沒有儲存指令會更改記憶體的內容。請注意，所有滿足 doesNotAccessMemory 方法的函數也滿足 onlyReadsMemory。

撰寫新的 `AliasAnalysis` 實作 ¶

為 LLVM 撰寫新的別名分析實作非常簡單。已經有幾個實作可以用作範例，以下資訊應有助於填補任何細節。有關範例，請查看 LLVM 包含的各種別名分析實作。

不同的 Pass 風格 ¶

確定您的別名分析需要使用哪種類型的 LLVM pass 的第一步。與大多數其他分析和轉換一樣，答案應該從您嘗試解決的問題類型中顯而易見

如果您需要跨程序分析，它應該是一個 Pass。
如果您是函數本地分析，請子類別化 FunctionPass。
如果您根本不需要查看程式，請子類別化 ImmutablePass。

除了您子類別化的 pass 之外，您還應該繼承 AliasAnalysis 介面，當然，並使用 RegisterAnalysisGroup 模板註冊為 AliasAnalysis 的實作。

必要的初始化呼叫 ¶

AliasAnalysis 的子類別需要調用 AliasAnalysis 基類上的兩個方法：getAnalysisUsage 和 InitializeAliasAnalysis。特別是，您的 getAnalysisUsage 實作除了宣告您的 pass 具有的任何 pass 依賴關係之外，還應顯式調用 AliasAnalysis::getAnalysisUsage 方法。因此，您應該有類似這樣的東西

void getAnalysisUsage(AnalysisUsage &AU) const {
  AliasAnalysis::getAnalysisUsage(AU);
  // declare your dependencies here.
}

此外，您必須從您的分析執行方法 (Pass 的 run、FunctionPass 的 runOnFunction 或 ImmutablePass 的 InitializePass) 中調用 InitializeAliasAnalysis 方法。例如 (作為 Pass 的一部分)

bool run(Module &M) {
  InitializeAliasAnalysis(this);
  // Perform analysis here...
  return false;
}

必要覆寫的方法 ¶

您必須在 AliasAnalysis 的所有子類別上覆寫 getAdjustedAnalysisPointer 方法。此方法的範例實作如下所示

void *getAdjustedAnalysisPointer(const void* ID) override {
  if (ID == &AliasAnalysis::ID)
    return (AliasAnalysis*)this;
  return this;
}

可以指定的介面 ¶

所有 AliasAnalysis 虛擬方法預設為提供到另一個別名分析實作的鏈結，最終傳回保守的正確資訊 (別名和 mod/ref 查詢分別傳回「May」別名和「Mod/Ref」)。根據您正在實作的分析的功能，您只需覆寫可以改進的介面。

`AliasAnalysis` 鏈結行為 ¶

每個別名分析 pass 都鏈結到另一個別名分析實作 (例如，使用者可以指定「-basic-aa -ds-aa -licm」以從兩個別名分析中獲得最大收益)。別名分析類別自動處理您未覆寫的大多數方法。對於您覆寫的方法，在傳回保守的 MayAlias 或 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);
}

除了分析查詢之外，如果您覆寫了 LLVM 更新通知方法，您還必須確保無條件地將它們傳遞給超類別，這允許更新變更中的所有別名分析。

為轉換更新分析結果 ¶

別名分析資訊最初是針對程式的靜態快照計算的，但客戶端將使用此資訊來對程式碼進行轉換。除了最簡單形式的別名分析之外，所有別名分析都需要更新其分析結果以反映這些轉換所做的變更。

AliasAnalysis 介面公開了四種方法，用於將程式變更從客戶端傳達給分析實作。各種別名分析實作應使用這些方法來確保它們的內部資料結構在程式變更時 (例如，當指令被刪除時) 保持最新，並且別名分析的客戶端必須確保適當地呼叫這些介面。

`deleteValue` 方法 ¶

當轉換從程式中移除指令或任何其他值 (包括不使用指標的值) 時，會呼叫 deleteValue 方法。通常，別名分析會保留資料結構，這些資料結構具有程式中每個值的條目。當呼叫此方法時，它們應移除指定值的任何條目 (如果存在)。

`copyValue` 方法 ¶

當將新值引入程式時，會使用 copyValue 方法。沒有辦法將以前不存在的值引入程式 (這對於安全的編譯器轉換沒有意義)，因此這是引入新值的唯一方法。此方法指示新值與正在複製的值具有完全相同的屬性。

`replaceWithNewValue` 方法 ¶

此方法是一個簡單的輔助方法，旨在使客戶端更易於使用。它的實作方式是將舊的分析資訊複製到新值，然後刪除舊值。別名分析實作無法覆寫此方法。

`addEscapingUse` 方法 ¶

當指標值的使用方式發生變更，可能會使預先計算的分析資訊失效時，會使用 addEscapingUse 方法。實作可以選擇使用此回呼為自分析時間以來使用方式已變更的點提供保守的回應，或者可以重新計算它們的部分或全部內部狀態以繼續提供準確的回應。

一般來說，指標值的任何新使用都被視為逸出使用，並且必須透過此回呼報告，但以下使用除外

指標的 bitcast 或 getelementptr
透過指標的 store (但不是指標的 store)
透過指標的 load

效率問題 ¶

從 LLVM 的角度來看，您需要做的唯一一件事才能提供高效的別名分析是確保別名分析查詢得到快速服務。「run」方法) 的實際計算只執行一次，但可能會執行許多 (可能是重複的) 查詢。因此，請嘗試將盡可能多的計算移動到 run 方法 (在合理範圍內)。

限制 ¶

別名分析基礎架構有幾個限制，這使得撰寫新的 AliasAnalysis 實作變得困難。

沒有辦法覆寫預設的別名分析。如果能夠執行類似「opt -my-aa -O2」的操作，並讓它將 -my-aa 用於所有需要 AliasAnalysis 的 passes，那將非常有用，但目前沒有對此的支援，除非更改原始程式碼並重新編譯。同樣地，也沒有辦法將分析鏈設定為預設值。

轉換 passes 無法宣告它們保留 AliasAnalysis 實作。AliasAnalysis 介面包括 deleteValue 和 copyValue 方法，這些方法旨在允許 pass 保持 AliasAnalysis 的一致性，但是 pass 無法在其 getAnalysisUsage 中宣告它這樣做。有些 passes 嘗試使用 AU.addPreserved<AliasAnalysis>，但這實際上沒有任何效果。

同樣地，opt -p 選項在每個 pass 之間引入 ModulePass passes，這會阻止使用 FunctionPass 別名分析 passes。

AliasAnalysis API 確實有函數可以在值被刪除或複製時通知實作，但這些並不充分。還有許多其他修改 LLVM IR 的方式可能與 AliasAnalysis 實作相關，但無法表達。

AliasAnalysisDebugger 工具似乎表明 AliasAnalysis 實作可以預期在任何相關的 Value 出現在別名查詢之前，它們都會被告知。然而，像 GVN 這樣常見的客戶端並不支援這一點，並且已知在與 AliasAnalysisDebugger 一起執行時會觸發錯誤。

AliasSetTracker 類別（由 LICM 使用）會進行非決定數量的別名查詢。這可能會導致涉及在預定查詢次數後暫停執行的除錯技術變得不可靠。

許多別名查詢可以用其他別名查詢來重新表述。當多個 AliasAnalysis 查詢鏈接在一起時，從鏈的開頭開始這些查詢會比較合理，並注意避免無限迴圈，然而目前想要這樣做的實作只能從自身開始這樣的查詢。

使用別名分析結果 ¶

有幾種不同的方法可以使用別名分析結果。依偏好順序，這些是：

使用 `MemoryDependenceAnalysis` Pass ¶

memdep pass 使用別名分析來提供關於使用記憶體的指令的高階依賴性資訊。例如，這會告訴你哪個 store 指令餵入 load 指令。它使用快取和其他技術來提高效率，並被 Dead Store Elimination、GVN 和 memcpy 優化所使用。

使用 `AliasSetTracker` 類別 ¶

許多轉換需要關於在某些作用域中活動的別名集合的資訊，而不是關於成對別名的資訊。AliasSetTracker 類別用於從 AliasAnalysis 介面提供的成對別名分析資訊中有效率地建立這些別名集合。

首先，您需要使用 “add” 方法初始化 AliasSetTracker，以添加關於您感興趣的作用域中各種可能產生別名的指令的資訊。一旦所有別名集合都完成後，您的 pass 應該只需迭代遍歷建構的別名集合，使用 AliasSetTracker 的 begin()/end() 方法。

由 AliasSetTracker 形成的 AliasSet 保證是不相交的，計算集合的 mod/ref 資訊和變動性，並追蹤集合中所有指標是否為 Must aliases。AliasSetTracker 還確保集合由於呼叫指令而被正確摺疊，並且可以提供每個集合中指標的列表。

作為一個使用範例，Loop Invariant Code Motion pass 使用 AliasSetTracker 來計算每個迴圈巢狀結構的別名集合。如果迴圈中的 AliasSet 未被修改，那麼來自該集合的所有 load 指令都可以被提升到迴圈之外。如果任何別名集合被儲存且是 must alias 集合，那麼這些 store 指令可以被下沉到迴圈之外，將記憶體位置提升為在迴圈巢狀結構持續期間的暫存器。這兩種轉換都僅在指標參數是迴圈不變量時才適用。

AliasSetTracker 的實作 ¶

AliasSetTracker 類別的實作旨在盡可能有效率。它使用 union-find 演算法在指標被插入到 AliasSetTracker 中且該指標與多個集合產生別名時，有效率地合併 AliasSet。主要的資料結構是一個雜湊表，將指標映射到它們所在的 AliasSet。

AliasSetTracker 類別必須維護每個 AliasSet 中所有 LLVM Value* 的列表。由於雜湊表已經為每個感興趣的 LLVM Value* 提供了條目，AliasesSets 將鏈結串列穿過這些雜湊表節點，以避免不必要地分配記憶體，並使合併別名集合變得極其有效率（鏈結串列合併是常數時間）。

如果您只是 AliasSetTracker 的客戶端，您不需要理解這些細節，但是如果您查看程式碼，希望這個簡短的描述將有助於理解為什麼事情會以目前的方式設計。

直接使用 `AliasAnalysis` 介面 ¶

如果這些實用類別都不是您的 pass 所需要的，您應該直接使用 AliasAnalysis 類別公開的介面。盡可能嘗試使用更高階的方法（例如，如果可能，使用 mod/ref 資訊而不是直接使用 alias 方法），以獲得最佳的精確度和效率。

現有的別名分析實作和客戶端 ¶

如果您要使用 LLVM 別名分析基礎架構，您應該了解有哪些別名分析的客戶端和實作可用。特別是，如果您正在實作別名分析，您應該了解客戶端，它們對於監控和評估不同的實作非常有用。

可用的 `AliasAnalysis` 實作 ¶

本節列出了 AliasAnalysis 介面的各種實作。所有這些都鏈接到其他別名分析實作。

`-basic-aa` pass ¶

-basic-aa pass 是一種積極的本地分析，它*知道*許多重要的事實：

不同的全域變數、堆疊分配和堆積分配永遠不會產生別名。
全域變數、堆疊分配和堆積分配永遠不會與空指標產生別名。
結構的不同欄位不會產生別名。
具有靜態不同下標的陣列索引不能產生別名。
許多常見的標準 C 程式庫函數從不存取記憶體或僅讀取記憶體。
明顯指向常數全域變數的指標 “pointToConstantMemory”。
如果函數呼叫永遠不會從分配它們的函數中逸出（自動陣列的常見情況），則函數呼叫不能修改或引用堆疊分配。

`-globalsmodref-aa` pass ¶

此 pass 針對沒有「取得其位址」的內部全域變數實作了簡單的上下文敏感 mod/ref 和別名分析。如果全域變數沒有取得其位址，則此 pass 知道沒有指標與該全域變數產生別名。此 pass 還追蹤它知道從不存取記憶體或從不讀取記憶體的函數。這允許某些優化（例如 GVN）完全消除呼叫指令。

此 pass 的真正威力在於它為呼叫指令提供了上下文敏感的 mod/ref 資訊。這允許優化器知道對函數的呼叫不會覆蓋或讀取全域變數的值，從而允許消除 load 和 store 指令。

注意：

此 pass 在其範圍上有些限制（僅支援未取得位址的全域變數），但分析速度非常快。

`-steens-aa` pass ¶

-steens-aa pass 實作了著名的「Steensgaard 演算法」的變體，用於程序間別名分析。Steensgaard 演算法是一種基於統一、流不敏感、上下文不敏感和欄位不敏感的別名分析，並且具有非常好的可擴展性（實際上是線性時間）。

LLVM -steens-aa pass 使用資料結構分析框架實作了 Steensgaard 演算法的「推測性欄位敏感」版本。這使其比標準演算法具有更高的精確度，同時保持了出色的分析可擴展性。

注意：

-steens-aa 在可選的 “poolalloc” 模組中可用。它不是 LLVM 核心的一部分。

`-ds-aa` pass ¶

-ds-aa pass 實作了完整的資料結構分析演算法。資料結構分析是一種模組化的、基於統一、流不敏感、上下文敏感和推測性欄位敏感的別名分析，它也具有相當好的可擴展性，通常為 O(n * log(n))。

此演算法能夠回應各種別名分析查詢，並且還可以提供上下文敏感的 mod/ref 資訊。目前尚未實作的唯一主要功能是支援 must-alias 資訊。

注意：

-ds-aa 在可選的 “poolalloc” 模組中可用。它不是 LLVM 核心的一部分。

`-scev-aa` pass ¶

-scev-aa pass 通過將別名分析查詢轉換為 ScalarEvolution 查詢來實作別名分析查詢。這使其比其他別名分析更完整地理解 getelementptr 指令和迴圈歸納變數。

別名分析驅動的轉換 ¶

LLVM 包含幾個別名分析驅動的轉換，可以與上述任何實作一起使用。

`-adce` pass ¶

-adce pass 實作了 Aggressive Dead Code Elimination，它使用 AliasAnalysis 介面來刪除對沒有副作用且未使用的函數的呼叫。

`-licm` pass ¶

-licm pass 實作了各種與 Loop Invariant Code Motion 相關的轉換。它將 AliasAnalysis 介面用於幾種不同的轉換：

如果迴圈中沒有指令修改載入的記憶體，它會使用 mod/ref 資訊將 load 指令提升或下沉到迴圈之外。
它使用 mod/ref 資訊將不寫入記憶體且為迴圈不變量的函數呼叫提升到迴圈之外。
它使用別名資訊將在迴圈中載入和儲存的記憶體物件提升為改為存活在暫存器中。如果載入/儲存的記憶體位置沒有 may alias，它可以執行此操作。

`-argpromotion` pass ¶

-argpromotion pass 將按引用傳遞的參數提升為改為按值傳遞。特別是，如果指標參數僅從中載入，它會將載入的值而不是位址傳遞給函數。此 pass 使用別名資訊來確保從參數指標載入的值在函數入口和任何指標載入之間不會被修改。

`-gvn`、`-memcpyopt` 和 `-dse` passes ¶

這些 pass 使用 AliasAnalysis 資訊來推理 load 和 store。

用於除錯和評估實作的客戶端 ¶

這些 pass 對於評估各種別名分析實作非常有用。您可以使用類似以下的命令來使用它們：

% opt -ds-aa -aa-eval foo.bc -disable-output -stats

`-print-alias-sets` pass ¶

-print-alias-sets pass 作為 opt 工具的一部分公開，用於印出由 AliasSetTracker 類別形成的別名集合。如果您正在使用 AliasSetTracker 類別，這將非常有用。要使用它，請使用類似以下的命令：

% opt -ds-aa -print-alias-sets -disable-output

`-aa-eval` pass ¶

-aa-eval pass 只是迭代函數中的所有指標對，並詢問別名分析指標是否產生別名。這指示了別名分析的精確度。印出的統計資訊指示了找到的 no/may/must 別名的百分比（更精確的演算法將具有較低的 may 別名數量）。

記憶體依賴性分析 ¶

注意：

我們目前正在將內容從 MemoryDependenceAnalysis 遷移到 MemorySSA。請嘗試改用它。

如果您只是想成為別名分析資訊的客戶端，請考慮改用記憶體依賴性分析介面。MemDep 是別名分析之上的惰性快取層，能夠回答給定指令依賴於哪些先前的記憶體操作的問題，無論是在區塊內還是區塊間層級。由於其惰性和快取策略，使用 MemDep 可以比直接存取別名分析獲得顯著的效能提升。