LLVM 別名分析基礎架構¶

簡介 ¶

別名分析（又稱指標分析）是一類技術，試圖確定兩個指標是否可以指向記憶體中的同一個物件。別名分析有許多不同的演算法，也有許多不同的分類方式：流程敏感與流程不敏感、上下文敏感與上下文不敏感、欄位敏感與欄位不敏感、基於統一與基於子集等等。傳統上，別名分析以必須、可能或否別名回應來回應查詢，表示兩個指標始終指向同一個物件、可能指向同一個物件，或者已知永遠不會指向同一個物件。

LLVM AliasAnalysis 類別是 LLVM 系統中用戶端和別名分析實作使用的主要介面。這個類別是別名分析資訊的用戶端和提供它的實作之間的通用介面，旨在支援廣泛的實作和用戶端（但目前所有用戶端都假設為流程不敏感）。除了簡單的別名分析資訊之外，這個類別還公開了那些可以提供修改/參考資訊的實作的修改/參考資訊，允許強大的分析和轉換很好地協同工作。

本文件包含成功實作此介面、使用它以及測試雙方所需的資訊。它還解釋了一些關於結果的確切含義的細節。

`AliasAnalysis` 類別概覽 ¶

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

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

所有 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 Alias 回應 ¶

當基於一個指標的任何內存引用與基於另一個指標的任何內存引用之間從來沒有直接相依性時，可以使用 NoAlias 回應。最明顯的例子是當兩個指標指向不重疊的內存範圍時。另一個例子是當兩個指標僅用於讀取內存時。另一個例子是在通過一個指標進行存取和通過另一個指標進行存取之間釋放並重新分配內存時——在這種情況下，存在相依性，但它是由釋放和重新分配來調節的。

一個例外是使用 noalias 關鍵字；“無關”的相依性將被忽略。

當兩個指標可能引用同一個物件時，使用 MayAlias 回應。

當已知兩個內存物件以某種方式重疊時，使用 PartialAlias 回應，無論它們是否從同一個地址開始。

僅當保證兩個內存物件始終從完全相同的位置開始時，才能返回 MustAlias 回應。MustAlias 回應並不意味著指標比較相等。

`getModRefInfo` 方法 ¶

getModRefInfo 方法返回有關指令的執行是否可以讀取或修改內存位置的資訊。修改/引用資訊始終是保守的：如果指令**可能**讀取或寫入某個位置，則返回 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 查詢返回「可能」別名和「修改/引用」）。根據您正在實作的分析的功能，您只需覆寫可以改進的介面。

`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 的角度來看，要提供高效的別名分析，您唯一需要做的是確保 **查詢** 別名分析的速度很快。實際計算別名分析結果（「執行」方法）只會執行一次，但可能會執行許多（可能是重複的）查詢。因此，盡可能將計算移至執行方法中（在合理範圍內）。

限制 ¶

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

無法覆寫預設的別名分析。如果能做到像 “opt -my-aa -O2” 這樣的事情，並讓所有需要 AliasAnalysis 的 pass 都使用 -my-aa，那將會非常有用，但目前不支援這樣做，除非修改原始碼並重新編譯。同樣地，也沒有辦法設定一連串的分析作為預設值。

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

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

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

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

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

許多別名查詢可以根據其他別名查詢重新表述。當多個 AliasAnalysis 查詢鏈接在一起時，從鏈的開頭開始這些查詢是有意義的，需要注意避免無限循環，但是目前想要這樣做的實作只能從自身開始此類查詢。

使用別名分析結果 ¶

有幾種不同的方法可以使用別名分析結果。按優先順序排列，這些方法是

使用 `MemoryDependenceAnalysis` Pass ¶

memdep 階段會使用別名分析來提供關於使用記憶體指令的高階相依性資訊。例如，這會告訴您哪個存放指令會饋入載入指令。它使用快取和其他技術來提高效率，並由 Dead Store Elimination、GVN 和 memcpy 優化使用。

使用 `AliasSetTracker` 類別 ¶

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

首先，您需要使用「add」方法初始化 AliasSetTracker，以新增關於您感興趣範圍內各種可能別名指令的資訊。完成所有別名集合後，您的階段應該使用 AliasSetTracker 的 begin()/end() 方法迭代建構的別名集合。

AliasSetTracker 形成的 AliasSet 保證是不相交的，計算集合的 mod/ref 資訊和易變性，並追蹤集合中的所有指標是否都是 Must 別名。AliasSetTracker 還確保由於呼叫指令而正確折疊集合，並且可以提供每個集合中的指標清單。

作為此類別的一個使用者範例，迴圈不變代碼移動階段使用 AliasSetTracker 來計算每個迴圈巢狀的別名集合。如果迴圈中的 AliasSet 未被修改，則可以將該集合中的所有載入指令提升到迴圈之外。如果任何別名集合都被儲存到**並且**是 Must 別名集合，則可以將儲存指令下沉到迴圈之外，將記憶體位置提升為暫存器，持續迴圈巢狀的持續時間。這兩種轉換僅在指標引數是迴圈不變的情況下才適用。

AliasSetTracker 的實現 ¶

AliasSetTracker 類別的實現盡可能高效。當將別名多個集合的指標插入 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 信息。這允許優化器知道對函數的調用不會覆蓋或讀取全局變數的值，從而可以消除加載和存儲。

注意

此 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))。

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

注意

-ds-aa 可在可選的「poolalloc」模組中使用。它不是 LLVM 核心的組成部分。

`-scev-aa` pass ¶

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

別名分析驅動的轉換 ¶

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

`-adce` pass ¶

實作積極死碼消除的 -adce pass 使用 AliasAnalysis 介面來刪除對沒有副作用且未使用的函式的呼叫。

`-licm` pass ¶

-licm pass 實作了與迴圈不變代碼移動相關的各種轉換。它將 AliasAnalysis 介面用於多種不同的轉換

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

`-argpromotion` pass ¶

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

`-gvn`、`-memcpyopt` 和 `-dse` 遍歷 ¶

這些遍歷使用 AliasAnalysis 資訊來推斷載入和儲存操作。

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

這些遍歷對於評估各種別名分析實現非常有用。您可以將它們與以下命令一起使用，例如

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

`-print-alias-sets` 遍歷 ¶

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

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

`-aa-eval` 遍歷 ¶

-aa-eval 遍歷只是迭代函數中的所有指標對，並詢問別名分析這些指標是否為別名。這給出了別名分析精度的指示。統計數據會顯示找到的無/可能/必須別名的百分比（更精確的演算法會具有較少數量的可能別名）。

記憶體依賴性分析 ¶

注意

我們目前正在將程式碼從 MemoryDependenceAnalysis 遷移到 MemorySSA。請盡量改用它。

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