LLVM 的分析與轉換 Pass¶

簡介 ¶

警告

本文檔不會經常更新，Pass 列表很可能不完整。可以使用 opt -print-passes 列出 opt 工具已知的 Pass。

本文檔作為 LLVM 提供的最佳化功能的高階摘要。最佳化以 Pass 的形式實作，Pass 遍歷程式的某些部分，以收集資訊或轉換程式。下表將 LLVM 提供的 Pass 分為三類。分析 Pass 計算其他 Pass 可以使用的資訊，或用於除錯或程式視覺化目的。轉換 Pass 可以使用（或使失效）分析 Pass。轉換 Pass 都以某種方式變更程式。工具 Pass 提供一些工具功能，但不適合其他分類。例如，將函數提取到位元碼或將模組寫入位元碼的 Pass 既不是分析 Pass 也不是轉換 Pass。上面的目錄提供了每個 Pass 的快速摘要，並連結到文檔後面更完整的 Pass 描述。

分析 Pass ¶

本節描述 LLVM 分析 Pass。

`aa-eval`：詳盡別名分析精確度評估器 ¶

這是一個簡單的 N 平方別名分析精確度評估器。基本上，對於程式中的每個函數，它只是查詢以查看別名分析實作如何回答函數中每對指標之間的別名查詢。

這項工作受到 Naveen Neelakantam、Francesco Spadini 和 Wojciech Stryjewski 的程式碼啟發和改編。

`basic-aa`：基本別名分析（無狀態 AA 實作）¶

一個基本的別名分析 Pass，它實作了恆等式（兩個不同的全域變數不能互為別名，等等），但不執行有狀態分析。

`basiccg`：基本呼叫圖建構 ¶

尚待撰寫。

`da`：相依性分析 ¶

相依性分析框架，用於偵測記憶體存取中的相依性。

`domfrontier`：支配邊界建構 ¶

此 Pass 是一個簡單的支配者建構演算法，用於尋找前向支配邊界。

`domtree`：支配樹建構 ¶

此 Pass 是一個簡單的支配者建構演算法，用於尋找前向支配者。

`dot-callgraph`：將呼叫圖列印到 “dot” 檔案 ¶

此 Pass 僅在 opt 中可用，將呼叫圖列印到 .dot 圖中。然後可以使用 “dot” 工具處理此圖，以將其轉換為 PostScript 或其他合適的格式。

`dot-cfg`：將函數的 CFG 列印到 “dot” 檔案 ¶

此 Pass 僅在 opt 中可用，將控制流程圖列印到 .dot 圖中。然後可以使用 dot 工具處理此圖，以將其轉換為 PostScript 或其他合適的格式。此外，可以使用 -cfg-func-name=<substring> 選項來篩選要列印的函數。將會列印所有包含指定子字串的函數。

`dot-cfg-only`：將函數的 CFG 列印到 “dot” 檔案（不含函數主體）¶

此 Pass 僅在 opt 中可用，將控制流程圖列印到 .dot 圖中，並省略函數主體。然後可以使用 dot 工具處理此圖，以將其轉換為 PostScript 或其他合適的格式。此外，可以使用 -cfg-func-name=<substring> 選項來篩選要列印的函數。將會列印所有包含指定子字串的函數。

`dot-dom`：將函數的支配樹列印到 “dot” 檔案 ¶

此 Pass 僅在 opt 中可用，將支配樹列印到 .dot 圖中。然後可以使用 dot 工具處理此圖，以將其轉換為 PostScript 或其他合適的格式。

`dot-dom-only`：將函數的支配樹列印到 “dot” 檔案（不含函數主體）¶

此 Pass 僅在 opt 中可用，將支配樹列印到 .dot 圖中，並省略函數主體。然後可以使用 dot 工具處理此圖，以將其轉換為 PostScript 或其他合適的格式。

`dot-post-dom`：將函數的後支配樹列印到 “dot” 檔案 ¶

此 Pass 僅在 opt 中可用，將後支配樹列印到 .dot 圖中。然後可以使用 dot 工具處理此圖，以將其轉換為 PostScript 或其他合適的格式。

`dot-post-dom-only`：將函數的後支配樹列印到 “dot” 檔案（不含函數主體）¶

此 Pass 僅在 opt 中可用，將後支配樹列印到 .dot 圖中，並省略函數主體。然後可以使用 dot 工具處理此圖，以將其轉換為 PostScript 或其他合適的格式。

`globals-aa`：全域變數的簡單 mod/ref 分析 ¶

這個簡單的 Pass 為未取得其位址的全域值提供別名和 mod/ref 資訊，並追蹤函數是否讀取或寫入記憶體（是否為「純粹」）。對於這個簡單（但非常常見）的情況，我們可以提供非常準確且有用的資訊。

`instcount`：計算各種 `Instruction` 的類型 ¶

此 Pass 收集所有指令的計數並報告它們。

`iv-users`：歸納變數使用者 ¶

從歸納變數計算的表達式的「有趣」使用者的簿記。

`kernel-info`：GPU 核心資訊 ¶

報告為 GPU 編譯的程式碼的各種統計數據。此 Pass 在單獨的文件中記錄。

`lazy-value-info`：延遲數值資訊分析 ¶

延遲計算數值約束資訊的介面。

`lint`：靜態檢查 LLVM IR ¶

此 Pass 靜態檢查 LLVM IR 中常見且易於識別的結構，這些結構會產生未定義或可能非預期的行為。

它並不能保證正確性，原因有二。首先，它並不全面。有些檢查可以靜態完成，但尚未實作。其中一些檢查由 TODO 註解指示，但這些註解也不全面。其次，許多條件無法靜態檢查。此 Pass 不執行動態檢測，因此它無法檢查所有可能的問題。

另一個限制是它假設所有程式碼都將被執行。在永遠不會到達的基本區塊中透過空指標儲存是無害的，但此 Pass 仍然會警告它。

最佳化 Pass 可能使此 Pass 檢查的條件更明顯或更不明顯。如果最佳化 Pass 似乎引入了警告，則可能是最佳化 Pass 僅僅暴露了程式碼中現有的條件。

此程式碼可能會在 instcombine 之前執行。在許多情況下，instcombine 會檢查相同種類的東西，並將具有未定義行為的指令轉換為不可達（或等效）。因此，此 Pass 會盡力查看位元轉換等等。

`loops`：自然迴圈資訊 ¶

此分析用於識別自然迴圈並確定 CFG 各個節點的迴圈深度。請注意，識別的迴圈實際上可能是多個共享相同標頭節點的自然迴圈…而不僅僅是一個單一的自然迴圈。

`memdep`：記憶體相依性分析 ¶

一種分析，針對給定的記憶體操作，確定它依賴於哪些先前的記憶體操作。它建立在別名分析資訊之上，並嘗試為常見的別名資訊查詢類型提供延遲、快取介面。

`print<module-debuginfo>`：解碼模組層級除錯資訊 ¶

此 Pass 解碼模組中的除錯資訊元數據，並以（充分準備的）人類可讀形式將其列印到標準輸出。

`postdomtree`：後支配樹建構 ¶

此 Pass 是一個簡單的後支配者建構演算法，用於尋找後支配者。

`print-alias-sets`：別名集合印表機 ¶

尚待撰寫。

`print-callgraph`：列印呼叫圖 ¶

此 Pass 僅在 opt 中可用，以人類可讀的形式將呼叫圖列印到標準錯誤。

`print-callgraph-sccs`：列印呼叫圖的 SCC ¶

此 Pass 僅在 opt 中可用，以人類可讀的形式將呼叫圖的 SCC 列印到標準錯誤。

`print-cfg-sccs`：列印每個函數 CFG 的 SCC ¶

此 Pass 僅在 opt 中可用，以人類可讀的形式將每個函數 CFG 的 SCC 列印到標準錯誤。

`function(print)`：將函數列印到 stderr ¶

PrintFunctionPass 類別旨在與其他 FunctionPasses 管線化，並在處理時印出模組的函數。

`module(print)`：將模組列印到 stderr ¶

此 Pass 只是在執行時印出整個模組。

`regions`：偵測單一入口單一出口區域 ¶

RegionInfo Pass 偵測函數中的單一入口單一出口區域，其中區域定義為僅在兩個點連接到剩餘圖的任何子圖。此外，還建構了階層式區域樹。

`scalar-evolution`：純量演化分析 ¶

ScalarEvolution 分析可用於分析和分類迴圈中的純量表達式。它專門識別一般歸納變數，並用抽象且不透明的 SCEV 類別表示它們。透過此分析，可以獲得迴圈的行程計數和其他重要屬性。

此分析主要用於歸納變數替換和強度縮減。

`scev-aa`：基於 ScalarEvolution 的別名分析 ¶

以 ScalarEvolution 查詢實作的簡單別名分析。

這與傳統的迴圈相依性分析不同，因為它測試迴圈單次迭代內的相依性，而不是不同迭代之間的相依性。

ScalarEvolution 比 BasicAliasAnalysis 的特設分析集合更完整地理解指標算術。

`stack-safety`：堆疊安全分析 ¶

StackSafety 分析可用於判斷堆疊配置變數是否可被視為免於記憶體存取錯誤的安全。

此分析的主要目的是供 sanitizers 使用，以避免不必要地對安全變數進行檢測機制。

轉換階段 ¶

本節說明 LLVM 轉換階段。

`adce`：激進式死碼消除 ¶

ADCE 積極嘗試消除程式碼。此階段類似於 DCE，但它假設數值是無效的，直到被證明並非如此。這類似於 SCCP，除了應用於數值的存活狀態。

`always-inline`：用於 `always_inline` 函數的內聯器 ¶

一個自定義的內聯器，僅處理被標記為 “always inline” 的函數。

`argpromotion`：將 'by reference' 參數提升為標量 ¶

此階段將 “by reference” 參數提升為 “by value” 參數。實際上，這意味著尋找具有指標參數的內部函數。如果它可以透過使用別名分析技術證明參數是僅被載入的，那麼它可以將該值傳遞到函數中，而不是該值的地址。這可能會導致程式碼遞迴簡化，並導致消除 allocas（尤其是在例如 C++ STL 樣板程式碼中）。

此階段還處理傳遞到函數中的聚合參數，如果聚合的元素僅被載入，則將它們標量化。請注意，它拒絕對需要傳遞三個以上運算元給函數的聚合進行標量化，因為為大型陣列或結構傳遞數千個運算元是不符成本效益的！

請注意，此轉換也可用於僅用於儲存的參數（而是傳回數值），但目前尚未實作。當 LLVM 開始支援函式多個回傳值時，這種情況將是最適合處理的情況。

`block-placement`：剖析導向的基本區塊佈局 ¶

此階段是一個非常簡單的剖析導向基本區塊佈局演算法。其概念是將經常執行的區塊放在函數的開頭，並期望增加 fall-through 條件分支的數量。如果特定函數沒有剖析資訊，則此階段基本上會以深度優先順序排列區塊。

`break-crit-edges`：中斷 CFG 中的關鍵邊緣 ¶

透過插入虛擬基本區塊來中斷 CFG 中的所有關鍵邊緣。對於無法處理關鍵邊緣的階段來說，這可能是「必需的」。此轉換顯然會使 CFG 失效，但可以更新正向支配者（集合、立即支配者、樹狀結構和邊界）資訊。

`codegenprepare`：為程式碼生成進行優化 ¶

此階段會修改輸入函數中的程式碼，以更好地為基於 SelectionDAG 的程式碼生成做準備。這解決了其基本區塊一次處理方法的限制。最終應將其移除。

`constmerge`：合併重複的全域常數 ¶

將重複的全域常數合併為單一共享的常數。這很有用，因為某些階段（即 TraceValues）會將大量字串常數插入程式中，而不管現有的字串是否可用。

`dce`：死碼消除 ¶

死碼消除類似於無效指令消除，但它會重新檢查被移除指令使用的指令，以查看它們是否是新近的無效指令。

`deadargelim`：無效參數消除 ¶

此階段從內部函數中刪除無效參數。無效參數消除會移除直接無效的參數，以及僅作為其他函數的無效參數傳遞到函數呼叫中的參數。此階段也以類似的方式刪除無效參數。

此階段通常作為清理階段很有用，可在積極的跨程序階段之後執行，這些階段會新增可能無效的參數。

`dse`：無效儲存消除 ¶

一個簡單的無效儲存消除，僅考慮基本區塊本機的冗餘儲存。

`function-attrs`：推導函數屬性 ¶

一個簡單的跨程序階段，它會走訪呼叫圖，尋找不存取或僅讀取非本機記憶體的函數，並將它們標記為 readnone/readonly。此外，如果對函數的呼叫未建立任何超出呼叫生命週期的指標值副本，則將函數參數（指標類型）標記為 “nocapture”。這或多或少意味著指標僅被取消引用，而不是從函數傳回或儲存在全域變數中。此階段實作為呼叫圖的由下而上遍歷。

`globaldce`：無效全域變數消除 ¶

此轉換旨在從程式中消除無法存取到的內部全域變數。它使用積極的演算法，搜尋已知為存活的全域變數。在找到所有需要的全域變數後，它會刪除剩餘的任何內容。這使其可以刪除無法存取的程式的遞迴區塊。

`globalopt`：全域變數優化器 ¶

此階段轉換從未取得其位址的簡單全域變數。如果明顯為真，它會將讀/寫全域變數標記為常數，刪除僅儲存的全域變數等。

`gvn`：全域數值編號 ¶

此階段執行全域數值編號，以消除完全和部分冗餘的指令。它還執行冗餘載入消除。

`indvars`：標準化歸納變數 ¶

此轉換分析歸納變數（以及從它們衍生的計算），並將其轉換為更簡單的形式，以適用於後續的分析和轉換。

此轉換對每個具有可識別歸納變數的迴圈進行以下變更

所有迴圈都轉換為具有單一標準歸納變數，該變數從零開始並以一為步進。
標準歸納變數保證是迴圈標頭區塊中的第一個 PHI 節點。
任何指標算術遞迴都會被提升為使用陣列下標。

如果迴圈的行程計數是可計算的，則此階段也會進行以下變更

迴圈的退出條件被標準化為將歸納值與退出值進行比較。這將迴圈變成類似
```
for (i = 7; i*i < 1000; ++i)

into
```
```
for (i = 0; i != 25; ++i)
```
迴圈外部對從 indvar 衍生的表達式的任何使用都會被更改為在迴圈外部計算衍生值，從而消除對歸納變數退出值的依賴性。如果迴圈的唯一目的是計算某些衍生表達式的退出值，則此轉換將使迴圈無效。

在執行所有所需的迴圈轉換之後，應接著進行強度縮減。此外，在有利可圖的目標上，可以將迴圈轉換為倒數到零（「do 迴圈」優化）。

`inline`：函數整合/內聯 ¶

由下而上將函數內聯到被呼叫者中。

`instcombine`：合併冗餘指令 ¶

合併指令以形成更少、更簡單的指令。此階段不會修改 CFG。代數簡化在此階段發生。

此階段合併類似於

%Y = add i32 %X, 1
%Z = add i32 %Y, 1

成為

%Z = add i32 %X, 2

這是一個簡單的工作列表驅動演算法。

此階段保證對程式執行以下標準化

如果二元運算子具有常數運算元，則會將其移至右側。
具有常數運算元的位元運算子始終分組，以便先執行位移，然後是 or，然後是 and，然後是 xor。
如果可能，比較指令會從 <、>、≤ 或 ≥ 轉換為 = 或 ≠。
布林值上的所有 cmp 指令都會替換為邏輯運算。
add X, X 表示為 mul X, 2 ⇒ shl X, 1
與常數二次方引數的乘法會轉換為位移。
… 等。

此階段還可以簡化對特定已知函數呼叫（例如，執行時期程式庫函數）的呼叫。例如，在 main() 函數中發生的呼叫 exit(3) 可以簡單地轉換為 return 3。是否簡化程式庫呼叫由 -function-attrs 階段和 LLVM 對不同目標上的程式庫呼叫的知識控制。

`aggressive-instcombine`：合併表達式模式 ¶

合併表達式模式以形成具有更少、更簡單指令的表達式。

例如，此階段會在適用時將 TruncInst 後支配的表達式寬度縮減為較小的寬度。

它與 instcombine 階段的不同之處在於它可以修改 CFG，並且包含比 O(1) 需要更高複雜度的模式優化，因此，它應該比 instcombine 階段執行的次數更少。

`internalize`：內部化全域符號 ¶

此階段會迴圈遍歷輸入模組中的所有函數，尋找 main 函數。如果找到 main 函數，則所有其他函數和具有初始化器的所有全域變數都會標記為內部。

`ipsccp`：跨程序稀疏條件常數傳播 ¶

一個稀疏條件常數傳播的跨程序變體。

`ir-normalizer`：將 IR 轉換為更易於 diff 的標準形式 ¶

此階段旨在透過重新排序和重新命名指令，同時保留相同的語意，將 LLVM 模組轉換為標準形式。標準化器使在 diff 兩個已進行兩個不同階段的模組時，更容易發現語意差異。

`jump-threading`：跳躍線程化 ¶

跳躍線程化嘗試尋找通過基本區塊運行的不同控制流程線程。此階段查看具有多個前導區塊和多個後繼區塊的區塊。如果可以證明區塊的一個或多個前導區塊始終會導致跳躍到其中一個後繼區塊，我們會透過複製此區塊的內容，將邊緣從前導區塊轉發到後繼區塊。

發生這種情況的一個範例是類似以下的程式碼

if () { ...
  X = 4;
}
if (X < 3) {

在這種情況下，第一個 if 結尾的無條件分支可以重新導向到第二個 if 的 false 分支。

`lcssa`：迴圈封閉 SSA 形式階段 ¶

此階段透過在迴圈末尾放置 phi 節點來轉換迴圈，以用於所有跨越迴圈邊界的存活數值。例如，它將左側程式碼變成右側程式碼

for (...)                for (...)
    if (c)                   if (c)
        X1 = ...                 X1 = ...
    else                     else
        X2 = ...                 X2 = ...
    X3 = phi(X1, X2)         X3 = phi(X1, X2)
... = X3 + 4              X4 = phi(X3)
                            ... = X4 + 4

這仍然是有效的 LLVM；額外的 phi 節點純粹是冗餘的，並且將被 InstCombine 輕鬆消除。此轉換的主要好處是，它使許多其他迴圈優化（例如 LoopUnswitch）更簡單。您可以在 LCSSA 形式的迴圈術語章節中閱讀更多內容。

`licm`：迴圈不變程式碼外移 ¶

此階段執行迴圈不變程式碼外移，嘗試從迴圈主體中移除盡可能多的程式碼。它透過將程式碼提升到前置標頭區塊中，或在安全的情況下將程式碼下沉到退出區塊來實現此目的。此階段還將迴圈中必須別名的記憶體位置提升到暫存器中，從而提升和下沉「不變」的載入和儲存。

將運算外移到迴圈之外是一種標準化轉換。它啟用並簡化了中後端的後續優化。為了減少暫存器壓力而重新實體化提升的指令是後端的責任，後端具有更準確的暫存器壓力資訊，並且還處理其他優化，而不是增加存活範圍的 LICM。

此階段將別名分析用於兩個目的

將迴圈不變的載入和呼叫移出迴圈。如果我們可以確定迴圈內的載入或呼叫永遠不會別名任何儲存的內容，我們可以像任何其他指令一樣提升或下沉它。
記憶體的純量提升。如果迴圈內有儲存指令，我們會嘗試將儲存移動到迴圈之後而不是迴圈內部發生。只有在幾個條件為真的情況下，才會發生這種情況
1. 儲存所通過的指標是不變的迴圈。
2. 迴圈中沒有可能別名指標的儲存或載入。迴圈中沒有修改/引用指標的呼叫。
如果這些條件為真，我們可以將迴圈中指標的載入和儲存提升為使用暫時分配的變數。然後，我們使用 mem2reg 功能來為變數建構適當的 SSA 形式。

`loop-deletion`：刪除無效迴圈 ¶

此檔案實作了無效迴圈刪除階段。此階段負責消除具有非無限可計算行程計數的迴圈，這些迴圈沒有副作用或 volatile 指令，並且不貢獻於函數傳回值的計算。

`loop-extract`：將迴圈提取到新的函數中 ¶

一個圍繞 ExtractLoop() 純量轉換的階段包裝器，用於將每個頂層迴圈提取到其自身的新函數中。如果迴圈是給定函數中唯一的迴圈，則不會觸及它。這是一個對於透過 bugpoint 進行偵錯最有用的階段。

`loop-reduce`：迴圈強度縮減 ¶

此階段對迴圈內部的陣列參考執行強度縮減，其中陣列參考的一個或多個組件是迴圈歸納變數。這是透過建立一個新值來保存第一次迭代的陣列存取的初始值，然後在迴圈中建立一個新的 GEP 指令來按適當的量遞增該值來完成的。

`loop-rotate`：旋轉迴圈 ¶

一個簡單的迴圈旋轉轉換。可以在旋轉迴圈的迴圈術語中找到它的摘要。

`loop-simplify`：標準化自然迴圈 ¶

此階段執行多個轉換，以將自然迴圈轉換為更簡單的形式，這使得後續的分析和轉換更簡單且更有效。可以在迴圈術語，迴圈簡化形式中找到它的摘要。

迴圈前置標頭插入保證從迴圈外部到迴圈標頭存在單一的非關鍵進入邊緣。這簡化了許多分析和轉換，例如 LICM。

迴圈退出區塊插入保證來自迴圈的所有退出區塊（迴圈外部的區塊，其前導區塊在迴圈內部）僅具有來自迴圈內部的先前區塊（因此受迴圈標頭支配）。這簡化了諸如內建於 LICM 的儲存下沉之類的轉換。

此階段還保證迴圈將恰好有一個反向邊緣。

請注意，simplifycfg 階段將清理被分割出來但最終變得不必要的區塊，因此使用此階段不應使生成的程式碼變差。

此階段顯然會修改 CFG，但會更新迴圈資訊和支配者資訊。

`loop-unroll`：展開迴圈 ¶

此階段實作了一個簡單的迴圈展開器。當迴圈已由 indvars 階段標準化時，它的效果最佳，從而使其可以輕鬆確定迴圈的行程計數。

`loop-unroll-and-jam`：展開和擠塞迴圈 ¶

此階段實作了一個簡單的展開和擠塞經典迴圈優化階段。它將迴圈從

for i.. i+= 1              for i.. i+= 4
  for j..                    for j..
    code(i, j)                 code(i, j)
                               code(i+1, j)
                               code(i+2, j)
                               code(i+3, j)
                           remainder loop

轉換而來，這可以看作是展開外部迴圈並將內部迴圈「擠塞」（融合）成一個。當變數或載入可以在新的內部迴圈中共享時，這可能會導致顯著的效能提升。它使用相依性分析來證明轉換是安全的。

`lower-global-dtors`：降低全域解構子 ¶

此階段透過建立包裝函式來降低全域模組解構子 (llvm.global_dtors)，這些包裝函式在 llvm.global_ctors 中註冊為全域建構子，並且其中包含對 __cxa_atexit 的呼叫以註冊其解構子函數。

`lower-atomic`：將原子內建函數降低為非原子形式 ¶

此階段將原子內建函數降低為非原子形式，以用於已知的非搶佔環境中。

此階段不會驗證環境是否為非搶佔式（一般而言，這需要了解程式的整個呼叫圖，包括任何可能無法以位元碼形式提供的程式庫）；它只是降低每個原子內建函數。

`lower-invoke`：將 invokes 降低為 calls，用於無堆疊展開程式碼產生器 ¶

此轉換旨在供尚不支援堆疊展開的程式碼產生器使用。此階段將 invoke 指令轉換為 call 指令，以便任何異常處理 landingpad 區塊都變成無效程式碼（可以透過在之後執行 -simplifycfg 階段來移除）。

`lower-switch`：將 `SwitchInst` 降低為分支 ¶

使用分支序列重寫 switch 指令，這允許目標在方便之前不必實作 switch 指令。

`mem2reg`：將記憶體提升為暫存器 ¶

此檔案將記憶體參考提升為暫存器參考。它提升僅將載入和儲存作為用途的 alloca 指令。alloca 透過使用支配者邊界來放置 phi 節點，然後以深度優先順序遍歷函數以適當地重寫載入和儲存來轉換。這只是用於建構「修剪」SSA 形式的標準 SSA 建構演算法。

`memcpyopt`：MemCpy 優化 ¶

此階段執行與消除 memcpy 呼叫或將儲存集合轉換為 memset 相關的各種轉換。

`mergefunc`：合併函數 ¶

此階段尋找可合併且等效的函數並將它們摺疊起來。

在函數集中引入了全序關係：我們定義了比較，以回答每兩個函數中哪個函數更大。它允許將函數排列到二元樹中。

對於每個新函數，我們都會檢查樹中是否存在等效函數。

如果存在等效函數，我們會摺疊這些函數。如果兩個函數都是可覆寫的，我們會將功能移至新的內部函數，並為其保留兩個可覆寫的 thunk。

如果不存在等效函數，則我們會將此函數新增到樹中。

查詢常式具有 O(log(n)) 的複雜度，而整個合併過程的複雜度為 O(n*log(n))。

閱讀本文以了解更多詳細資訊。

`mergereturn`：統一函數退出節點 ¶

確保函數中最多只有一個 ret 指令。此外，它還會追蹤哪個節點是 CFG 的新退出節點。

`partial-inliner`：部分內聯器 ¶

此階段執行部分內聯，通常是透過內聯包圍函數主體的 if 語句。

`reassociate`：重新關聯表達式 ¶

此階段以旨在促進更好的常數傳播、GCSE、LICM、PRE 等的順序重新關聯可交換表達式。

例如：4 + (x + 5) ⇒ x + (4 + 5)

在此演算法的實作中，常數被賦予等級 = 0，函數參數的等級 = 1，其他值被賦予與當前函數的反向後序遍歷相對應的等級（從 2 開始），這有效地使深層迴圈中的值比不在迴圈中的值具有更高的等級。

`rel-lookup-table-converter`：相對查找表轉換器 ¶

此階段將查找表轉換為 PIC 友好的相對查找表。

`reg2mem`：將所有數值降級為堆疊槽 ¶

此檔案將所有暫存器降級為記憶體參考。它旨在成為 mem2reg 的逆過程。透過轉換為 load 指令，跨基本區塊存活的唯一數值是 alloca 指令和 phi 節點之前的 load 指令。它的目的是使 CFG hacking 更加容易。為了使後續的 hacking 更容易，進入區塊被分割成兩個，使得所有引入的 alloca 指令（以及其他任何指令）都在進入區塊中。

`sroa`：聚合的純量替換 ¶

眾所周知的聚合純量替換轉換。如果可能，此轉換會將聚合類型（結構或陣列）的 alloca 指令分解為每個成員的個別 alloca 指令。然後，如果可能，它會將個別的 alloca 指令轉換為良好的純淨純量 SSA 形式。

`sccp`：稀疏條件常數傳播 ¶

稀疏條件常數傳播和合併，可以總結為

假設數值是常數，除非另有證明
假設基本區塊是無效的，除非另有證明
證明數值是常數，並將它們替換為常數
證明條件分支是無條件的

請注意，此階段有使定義變為無效的習慣。在執行此階段之後的某個時間執行 DCE 階段是個好主意。

`simplifycfg`：簡化 CFG ¶

執行死碼消除和基本區塊合併。具體而言

移除沒有前導區塊的基本區塊。
如果基本區塊只有一個前導區塊，並且前導區塊只有一個後繼區塊，則將基本區塊合併到其前導區塊中。
消除具有單一前導區塊的基本區塊的 PHI 節點。
消除僅包含無條件分支的基本區塊。

`sink`：程式碼下沉 ¶

此階段在可能的情況下將指令移動到後繼區塊中，以便它們不會在不需要其結果的路徑上執行。

`simple-loop-unswitch`：Unswitch 迴圈 ¶

此階段轉換包含迴圈不變條件分支的迴圈，使其具有多個迴圈。例如，它將左側程式碼變成右側程式碼

for (...)                  if (lic)
    A                          for (...)
    if (lic)                       A; B; C
        B                  else
    C                          for (...)
                                   A; C

這會以指數方式增加程式碼的大小（每次迴圈 unswitch 時都會使其加倍），因此我們僅在結果程式碼小於閾值時才執行 unswitch。

此階段期望在它之前執行 LICM 以將不變條件提升出迴圈，以使 unswitch 機會顯而易見。

`strip`：從模組中移除所有符號 ¶

執行程式碼移除（stripping）。此轉換可以刪除：

虛擬暫存器的名稱
內部全域變數和函式的符號
除錯資訊

請注意，此轉換會使程式碼的可讀性大幅降低，因此僅應在會使用 strip 工具的情況下使用，例如縮減程式碼大小或使其更難以進行逆向工程。

`strip-dead-debug-info`：移除未使用符號的除錯資訊 ¶

執行程式碼移除。與 strip 類似，但僅移除未使用符號的除錯資訊。

`strip-dead-prototypes`：移除未使用的函式原型 ¶

此 pass 會遍歷輸入模組中的所有函式，尋找未使用的宣告並移除它們。未使用的宣告是指沒有實作可用的函式宣告（即，未使用程式庫函式的宣告）。

strip-debug-declare：移除所有 llvm.dbg.declare 內建函數和 #dbg_declare 紀錄。 ——————————————————————-

執行程式碼移除。與 strip 類似，但僅移除 llvm.dbg.declare 內建函數。

`strip-nondebug`：從模組中移除所有符號，除了 dbg 符號 ¶

執行程式碼移除。與 strip 類似，但會保留 dbg 資訊。

`tailcallelim`：尾呼叫消除 ¶

此檔案轉換對目前函式的呼叫（自我遞迴），接著是返回指令，並分支到函式的入口，從而建立迴圈。此 pass 也實作了對基本演算法的以下擴展：

呼叫和返回之間的瑣碎指令不會阻止轉換發生，儘管目前分析無法支援移動任何真正有用的指令（僅限於未使用的指令）。
此 pass 轉換因結合律表達式而無法進行尾部遞迴的函式，以使用累加器變數，從而將典型的 naive 階乘或 fib 實作編譯成高效的程式碼。
如果函式返回 void、如果返回傳回呼叫傳回的結果，或者如果函式在函式的所有出口都返回執行時期常數，則執行 TRE。返回傳回其他內容（例如常數 0），但仍然可以進行 TRE，這是可能但不常見的情況。如果函式中*所有其他*返回指令都傳回完全相同的值，則可以進行 TRE。
如果它可以證明被呼叫者不會存取其呼叫者的堆疊框架，則它們會被標記為符合尾呼叫消除的條件（由程式碼產生器執行）。

二元運算子的兩個參數都是相同的類型。
驗證記憶體存取指令的索引是否與其他運算元匹配。
驗證算術和其他操作是否僅對 first-class 類型執行。驗證位移和邏輯運算是否僅發生在整數上，例如。
switch 語句中的所有常數都是正確的類型。
程式碼採用有效的 SSA 形式。
將標籤放入任何其他類型（如結構）或傳回標籤是非法的。
只有 phi 節點可以自我參照：%x = add i32 %x，%x 無效。
PHI 節點必須為每個前導節點都有一個條目，且不能有多餘的條目。
PHI 節點必須是基本區塊中的第一個項目，全部組合在一起。
PHI 節點必須至少有一個條目。
所有基本區塊都應僅以終止指令結束，而不應包含它們。
函式的入口節點不得有前導節點。
所有指令都必須嵌入到基本區塊中。
函式不能採用 void 類型的參數。
驗證函式的引數列表是否與其宣告的類型一致。
為 void 值指定名稱是非法的。
擁有沒有初始設定式的內部全域變數是非法的。
擁有 ret 指令傳回的值與函式傳回值類型不一致是非法的。
函式呼叫引數類型與函式原型匹配。
程式碼中散佈的斷言測試的所有其他事項。

請注意，這不提供完整的安全性驗證（如 Java），而只是嘗試確保程式碼格式良好。