MergeFunctions pass，運作方式¶

簡介 ¶

有時程式碼包含相等的函數，或即使它們在 IR 層級上不相等（例如：乘以 2 和 ‘shl 1’），但執行完全相同操作的函數。這可能是由於多種原因造成的：主要是模板和自動程式碼產生器的使用。當然，有時使用者自己可能會寫兩次相同的東西 :-)

此Pass的主要目的是識別這些函數並合併它們。

本文件是 Pass 註解的擴展，並描述了 Pass 邏輯。它描述了用於比較函數的演算法，並解釋了我們如何正確地組合相等的函數以保持模組有效。

材料以由上而下的形式呈現，因此讀者可以從高層次的想法開始學習 Pass，並以低層次的演算法細節結束，從而為他或她閱讀原始碼做好準備。

主要目標是在此描述演算法和邏輯以及概念。如果您*不想*閱讀原始碼，但想了解 Pass 演算法，本文檔非常適合您。作者盡量不重複原始碼，並且僅涵蓋常見情況，以避免在任何小的程式碼變更後需要更新本文檔的情況。

我需要了解什麼才能理解本文檔？¶

讀者應熟悉常見的編譯工程原理和 LLVM 程式碼基礎知識。在本文中，我們假設讀者熟悉單一靜態賦值概念，並且了解IR 結構。

我們將使用諸如「模組」、「函數」、「基本區塊」、「使用者」、「值」、「指令」等術語。

作為一個好的起點，可以使用 Kaleidoscope 教學

LLVM 教學：目錄

理解教學的第 3 章尤其重要

Kaleidoscope 教學

讀者也應該知道 Pass 在 LLVM 中是如何運作的。他們可以使用這篇文章作為參考和起點

撰寫 LLVM Pass（傳統 PM 版本）

還有什麼？也許讀者還應該有一些 LLVM Pass 除錯和錯誤修復的經驗。

敘述結構 ¶

本文由三個部分組成。第一部分解釋了頂層的 Pass 功能。第二部分描述了比較程序本身。第三部分描述了合併過程。

在每個部分中，作者都試圖以由上而下的形式呈現內容。頂層方法將首先被描述，然後是每個部分末尾的終端方法。如果讀者看到對尚未描述的方法的引用，他們將在稍下方找到其描述。

基礎知識 ¶

怎麼做？¶

我們需要合併函數嗎？明顯的答案是：是的，這是一個很有可能發生的情況。我們通常*確實*有重複項，最好擺脫它們。但是我們如何檢測重複項？這就是想法：我們將函數拆分為更小的磚塊或部分，並比較「磚塊」的數量。如果相等，我們比較「磚塊」本身，然後對函數本身做出結論。

可能的區別是什麼？例如，在具有 64 位元指標的機器上（假設我們只有一個位址空間），一個函數儲存一個 64 位元整數，而另一個函數儲存一個指標。如果目標是上面提到的機器，並且如果函數是相同的，除了參數類型（我們可以將其視為函數類型的一部分），那麼我們可以將 uint64_t 和 void* 視為相等。

這只是一個例子；更多可能的細節將在稍後描述。

作為另一個例子，讀者可以想像另外兩個函數。第一個函數執行乘以 2 的運算，而第二個函數執行邏輯左移 1 的運算。

可能的解決方案 ¶

讓我們簡要考慮一下關於如何以及我們必須實作什麼才能創建功能齊全的函數合併，以及這對我們意味著什麼的可能選項。

相等函數檢測顯然假設要實作一個「檢測器」方法，後者應回答「函數是否相等」的問題。這個「檢測器」方法由微小的「子檢測器」組成，每個子檢測器都回答完全相同的問題，但針對函數部分。

作為第二步，我們應該合併相等的函數。因此它應該是一個「合併器」方法。「合併器」接受兩個函數 *F1* 和 *F2*，並產生 *F1F2* 函數，即合併的結果。

有了這些例程，我們就可以處理整個模組，並合併所有相等的函數。

在這種情況下，我們必須將每個函數與每個其他函數進行比較。正如讀者可能注意到的，這種方式似乎相當昂貴。當然，我們可以引入雜湊和其他輔助工具，但它仍然只是一種優化，因此複雜度為 O(N*N) 級別。

我們可以達到另一個層次嗎？我們可以引入對數搜尋或隨機存取查找嗎？答案是：「可以」。

隨機存取 ¶

這怎麼能做到呢？只需將每個函數轉換為數字，並將它們全部收集在一個特殊的雜湊表中。具有相等雜湊值的函數是相等的。良好的雜湊表示必須考慮每個函數部分。這意味著我們必須將每個函數部分轉換為某個數字，然後將其添加到雜湊中。查找時間會很短，但這種方法由於雜湊例程而增加了一些延遲。

對數搜尋 ¶

我們可以在函數集中引入總排序，一旦排序完成，我們就可以實作對數搜尋。查找時間仍然取決於 N，但增加了一點延遲 (*log(N)*)。

目前狀態 ¶

這兩種方法（隨機存取和對數）都已實作和測試，並且都取得了非常好的改進。最令人驚訝的是，對數搜尋更快；有時快達 15%。雜湊方法需要額外的 CPU 時間，這是它運行較慢的主要原因；在大多數情況下，總「雜湊」時間大於總「對數搜尋」時間。

因此，優先選擇了「對數搜尋」。

儘管在需要的情況下，*對數搜尋*（讀作「總排序」）可以用作我們邁向 *隨機存取* 實作的里程碑。

每次比較都基於數字或標誌比較。在 *隨機存取* 方法中，我們可以使用相同的比較演算法。在比較期間，一旦我們發現差異，我們就會退出，但在這裡我們可能必須每次都掃描整個函數體（請注意，這可能會更慢）。就像在「總排序」中一樣，我們將追蹤每個數字和標誌，但不是比較，我們應該獲得數字序列，然後創建雜湊數字。因此，再一次，*總排序* 可以被認為是更快（理論上）隨機存取方法的里程碑。

MergeFunctions，主要欄位和 runOnModule ¶

類別中有兩個主要的重要欄位

FnTree – 所有唯一函數的集合。它保留了無法彼此合併的項目。它被定義為

std::set<FunctionNode> FnTree;

這裡 FunctionNode 是 llvm::Function 類別的包裝器，在函數集中實作了「<」運算符（下面我們將解釋它如何準確地工作；這是快速函數比較的關鍵點）。

Deferred – 合併過程可能會影響已在 FnTree 中的函數體。顯然，應該再次檢查這些函數。在這種情況下，我們將它們從 FnTree 中移除，並將它們標記為要重新掃描，即將它們放入 Deferred 列表中。

runOnModule ¶

演算法非常簡單

將所有模組的函數放入 *worklist* 中。

2. 掃描 *worklist* 的函數兩次：首先僅枚舉強函數，然後僅枚舉弱函數

2.1. 迴圈主體：從 *worklist* 中取一個函數（稱為 *FCur*）並嘗試將其插入 *FnTree*：檢查 *FCur* 是否等於 *FnTree* 中的函數之一。如果 *FnTree* 中*有*一個相等的函數（稱為 *FExists*）：將函數 *FCur* 與 *FExists* 合併。否則將 *worklist* 中的函數添加到 *FnTree*。

3. 一旦 *worklist* 掃描和合併操作完成，檢查 *Deferred* 列表。如果它不為空：用 *Deferred* 列表重新填充 *worklist* 內容並重做步驟 2，如果 *Deferred* 列表為空，則退出方法。

比較和對數搜尋 ¶

讓我們回顧一下我們的任務：對於模組 *M* 中的每個函數 *F*，我們必須在盡可能短的時間內找到相等的函數 *F`*，並將它們合併為一個函數。

在函數集中定義總排序允許我們將函數組織成二元樹。在這種情況下，查找程序的複雜度估計為 O(log(N))。但是我們如何定義 *總排序* 呢？

我們必須引入適用於每對函數的單一規則，並遵循此規則，然後評估哪個函數更大。這會是什麼樣的規則？讓我們將其聲明為「比較」方法，該方法返回 3 個可能值之一

-1，左邊小於右邊，

0，左邊和右邊相等，

1，左邊大於右邊。

當然，這意味著我們必須維護*嚴格和非嚴格的順序關係屬性*

自反性 (a <= a, a == a, a >= a)，
反對稱性（如果 a <= b 且 b <= a 則 a == b），
傳遞性（a <= b 且 b <= c，則 a <= c）
非對稱性（如果 a < b，則 a > b 或 a == b）。

如前所述，比較例程由「子比較例程」組成，其中每個子比較例程也由「子比較例程」組成，依此類推。最後，它以基本比較結束。

下面，我們將使用以下操作

cmpNumbers(number1, number2) 是一種方法，如果左邊小於右邊則返回 -1；如果左邊和右邊相等則返回 0；否則返回 1。
cmpFlags(flag1, flag2) 是一種假設的方法，用於比較兩個標誌。邏輯與 cmpNumbers 相同，其中 true 為 1，false 為 0。

本文的其餘部分基於 *MergeFunctions.cpp* 原始碼（位於 *<llvm_dir>/lib/Transforms/IPO/MergeFunctions.cpp* 中）。我們希望讀者保持打開此文件，以便我們可以將其用作進一步解釋的參考。

現在，我們準備好繼續下一章，看看它是如何運作的。

函數比較 ¶

首先，讓我們定義我們如何準確地比較複雜的物件。

複雜物件比較（函數、基本區塊等）主要基於其子物件比較結果。它類似於下一個「樹」物件比較

對於兩棵樹 *T1* 和 *T2*，我們執行 *深度優先遍歷*，並得到兩個序列作為產品：「*T1Items*」和「*T2Items*」。
然後我們以最重要的項目優先順序比較鏈「*T1Items*」和「*T2Items*」。項目比較的結果將是 *T1* 和 *T2* 本身比較的結果。

FunctionComparator::compare(void)¶

簡要查看原始碼告訴我們，比較從「int FunctionComparator::compare(void)」方法開始。

1. 要比較的首要部分是函數的屬性和一些超出「屬性」術語的屬性，但仍然可以在不更改其主體的情況下使函數不同。比較的這部分通常在簡單的 cmpNumbers 或 cmpFlags 操作中完成（例如 cmpFlags(F1->hasGC(), F2->hasGC())）。以下是在此階段要比較的函數屬性的完整列表

*屬性*（這些由 Function::getAttributes() 方法返回）。

*GC*，為了等效性，*RHS* 和 *LHS* 應該都既沒有 *GC* 或具有相同的 *GC*。

*Section*，就像 *GC* 一樣：*RHS* 和 *LHS* 應該在同一區段中定義。

*可變參數*。 *LHS* 和 *RHS* 應該都既有或沒有 *var-args*。

*調用約定* 應該相同。

2. 函數類型。由 FunctionComparator::cmpType(Type*, Type*) 方法檢查。它檢查返回類型和參數類型；該方法本身稍後將描述。

3. 將函數形式參數彼此關聯。然後比較函數體，如果我們在 *LHS* 的主體中看到 *LHS* 的第 *i* 個參數的使用，那麼我們希望在 *RHS* 的主體中的相同位置看到 *RHS* 的第 *i* 個參數的使用，否則函數是不同的。在此階段，我們優先考慮在函數體中稍後遇到的那些（我們首先遇到的值會*更小*）。這是通過「FunctionComparator::cmpValues(const Value*, const Value*)」方法完成的（稍後將描述）。

函數體比較。正如方法註解中所寫

「我們執行 CFG 順序的遍歷，因為鏈結串列中區塊的實際順序是無關緊要的。我們的遍歷從兩個函數的入口區塊開始，然後按順序從每個終結符中獲取每個區塊。作為一個人工產物，這也意味著無法訪問的區塊被忽略。」

因此，使用此遍歷，我們以相同的順序從 *left* 和 *right* 獲取 BB，並通過「FunctionComparator::compare(const BasicBlock*, const BasicBlock*)」方法比較它們。

我們也將 BB 彼此關聯，就像我們對函數形式參數所做的那樣（請參閱下面的 cmpValues 方法）。

FunctionComparator::cmpType ¶

考慮類型比較如何運作。

1. 將指標強制轉換為整數。如果左類型是指標，請嘗試將其強制轉換為整數類型。如果其位址空間為 0，或者如果完全忽略位址空間，則可以執行此操作。對於右類型執行相同的操作。

2. 如果左類型和右類型相等，則返回 0。否則，我們需要優先考慮其中一個。因此繼續下一步。

3. 如果類型種類不同（不同的類型 ID）。返回類型 ID 比較的結果，將它們視為數字（使用 cmpNumbers 操作）。

4. 如果類型是向量或整數，則返回其指標比較的結果，將它們作為數字進行比較。

檢查類型 ID 是否屬於下一個組（稱為等效組）
- Void
- Float
- Double
- X86_FP80
- FP128
- PPC_FP128
- Label
- Metadata。
如果 ID 屬於上面的組，則返回 0。因為看到類型具有相同的 TypeID 就足夠了。不需要額外的資訊。

6. 左邊和右邊都是指標。返回位址空間比較的結果（數字比較）。

7. 複雜類型（結構、陣列等）。遵循複雜物件比較技術（請參閱本章的第一段）。 *左邊* 和 *右邊* 都將被擴展，並且它們的元素類型將以相同的方式檢查。如果我們在某個階段得到 -1 或 1，則返回它。否則返回 0。

8. 步驟 1-6 描述了所有可能的情況，如果我們通過了步驟 1-6 並且沒有得到任何結論，則調用 llvm_unreachable，因為這是一個非常意外的情況。

cmpValues(const Value, const Value)¶

比較本地值的方法。

此方法為我們提供了一個非常有趣的問題的答案：我們是否可以將本地值視為相等，以及哪個值在其他情況下更大。最好從例子開始

考慮這樣一種情況，當我們在左函數「*FL*」和右函數「*FR*」中查看相同的位置時。 *左邊* 位置的每個部分都等於 *右邊* 位置的相應部分，並且（！）兩個部分都使用 *Value* 實例，例如

instr0 i32 %LV   ; left side, function FL
instr0 i32 %RV   ; right side, function FR

因此，現在我們的結論取決於 *Value* 實例比較。

此方法的主要目的是確定此類值之間的關係。

我們對相等的函數有什麼期望？在相同的位置，在函數「*FL*」和「*FR*」中，我們期望看到*相等*的值，或在「*FL*」和「*FR*」中相同位置*定義*的值。

在此考慮一個小例子

define void %f(i32 %pf0, i32 %pf1) {
  instr0 i32 %pf0 instr1 i32 %pf1 instr2 i32 123
}

define void %g(i32 %pg0, i32 %pg1) {
  instr0 i32 %pg0 instr1 i32 %pg0 instr2 i32 123
}

在此範例中，*pf0* 與 *pg0* 相關聯，*pf1* 與 *pg1* 相關聯，我們也聲明 *pf0* < *pf1*，因此 *pg0* < *pf1*。

運算碼為「*instr0*」的指令將是*相等的*，因為它們的類型和運算碼相等，並且值是*關聯的*。

來自 *f* 的運算碼為「*instr1*」的指令*大於*來自 *g* 的運算碼為「*instr1*」的指令；在這裡，我們有相等的類型和運算碼，但「*pf1* 大於「*pg0*」」。

運算碼為「*instr2*」的指令是相等的，因為它們的運算碼和類型相等，並且使用了相同的常數作為值。

我們在 cmpValues 中關聯什麼？¶

函數參數。來自左函數的第 *i* 個參數與來自右函數的第 *i* 個參數相關聯。
BasicBlock 實例。在基本區塊枚舉迴圈中，我們將來自左函數的第 *i* 個 BasicBlock 與來自右函數的第 *i* 個 BasicBlock 相關聯。
指令。
指令運算元。請注意，我們在這裡可能會遇到從未見過的 *Value*。在這種情況下，它既不是函數參數，也不是 *BasicBlock*，也不是 *Instruction*。它是一個全域值。它是一個常數，因為它是這裡唯一應該有的全域值。該方法還比較：類型相同的常數，如果右常數可以無損地位元轉換為左常數，那麼我們也比較它們。

如何實作 cmpValues？¶

*關聯* 對我們來說是一種相等的情況。我們只是將這些值視為相等，但總的來說，我們需要實作反對稱關係。如上所述，要理解什麼是*更小*，我們可以使用我們遇到值的順序。如果兩個值在函數中具有相同的順序（同時遇到），那麼我們將值視為*關聯的*。否則 – 這取決於誰先出現。

每次我們運行頂層比較方法時，我們都會初始化兩個相同的映射（一個用於左側，另一個用於右側）

map<Value, int> sn_mapL, sn_mapR;

映射的鍵是 *Value* 本身，*值* – 是它的順序（稱為 *序號*）。

要添加值 *V*，我們需要執行下一個程序

sn_map.insert(std::make_pair(V, sn_map.size()));

對於第一個 *Value*，映射將返回 *0*，對於第二個 *Value*，映射將返回 *1*，依此類推。

然後我們可以通過簡單的比較來檢查左值和右值是否同時遇到

cmpNumbers(sn_mapL[Left], sn_mapR[Right]);

當然，我們可以組合插入和比較

std::pair<iterator, bool>
  LeftRes = sn_mapL.insert(std::make_pair(Left, sn_mapL.size())), RightRes
  = sn_mapR.insert(std::make_pair(Right, sn_mapR.size()));
return cmpNumbers(LeftRes.first->second, RightRes.first->second);

讓我們看看，整個方法是如何實作的。

1. 我們必須從壞消息開始。考慮函數自身和交叉引用案例

// self-reference unsigned fact0(unsigned n) { return n > 1 ? n
* fact0(n-1) : 1; } unsigned fact1(unsigned n) { return n > 1 ? n *
fact1(n-1) : 1; }

// cross-reference unsigned ping(unsigned n) { return n!= 0 ? pong(n-1) : 0;
} unsigned pong(unsigned n) { return n!= 0 ? ping(n-1) : 0; }

此比較已在初始 *MergeFunctions* Pass 版本中實作。但是，不幸的是，它不是傳遞的。這是我們無法轉換為小於等於大於比較的唯一情況。這是一個罕見的情況，在 10000 個函數中只有 4-5 個（在測試套件中檢查過），我們希望讀者能原諒我們為了獲得 O(log(N)) Pass 時間而做出的犧牲。

2. 如果左/右 *Value* 是常數，我們必須比較它們。如果它是相同的常數，則返回 0，否則使用 cmpConstants 方法。

3. 如果左/右是 *InlineAsm* 實例。返回 *Value* 指標比較的結果。

4. *L*（左值）和 *R*（右值）的顯式關聯。我們需要找出值是否同時遇到，因此是*關聯的*。或者我們需要制定規則：當我們將 *L* < *R* 對待時。現在很容易了：我們只需返回數字比較的結果

std::pair<iterator, bool>
  LeftRes = sn_mapL.insert(std::make_pair(Left, sn_mapL.size())),
  RightRes = sn_mapR.insert(std::make_pair(Right, sn_mapR.size()));
if (LeftRes.first->second == RightRes.first->second) return 0;
if (LeftRes.first->second < RightRes.first->second) return -1;
return 1;

現在當 cmpValues 返回 0 時，我們可以繼續比較程序。否則，如果我們得到 (-1 或 1)，我們需要將此結果傳遞到頂層，並完成比較程序。

cmpConstants ¶

執行常數比較如下

1. 使用 cmpType 方法比較常數類型。如果結果為 -1 或 1，則轉到步驟 2，否則繼續步驟 3。

2. 如果類型不同，我們仍然可以檢查常數是否可以彼此無損地位元轉換。進一步的解釋是 canLosslesslyBitCastTo 方法的修改。

2.1 檢查常數是否屬於第一類類型（isFirstClassType 檢查）

2.1.1. 如果兩個常數都*不是*第一類類型：返回 cmpType 的結果。

2.1.2. 否則，如果左類型不是第一類，則返回 -1。如果右類型不是第一類，則返回 1。

2.1.3. 如果兩個類型都是第一類類型，則繼續下一步（2.1.3.1）。

2.1.3.1. 如果類型是向量，則使用 *cmpNumbers* 比較它們的位寬。如果結果不是 0，則返回它。

2.1.3.2. 不同的類型，但不是向量

如果它們都是指標，對我們來說很好，我們可以繼續步驟 3。

如果其中一種類型是指標，則返回 *isPointer* 標誌比較的結果（*cmpFlags* 操作）。

否則我們沒有方法證明位元轉換性，因此返回類型比較的結果（-1 或 1）。

以下步驟適用於類型相等的情況，或常數可位元轉換的情況

3. 其中一個常數是「*null*」值。返回 cmpFlags(L->isNullValue, R->isNullValue) 比較的結果。

比較值 ID，如果結果不是 0，則返回結果

if (int Res = cmpNumbers(L->getValueID(), R->getValueID()))
  return Res;

5. 比較常數的內容。比較取決於常數的種類，但在這個階段，它只是一個詞典比較。只需查看「*函數比較*」段落開頭的描述。在數學上，它等於下一個案例：我們編碼左常數和右常數（以類似於 *bitcode-writer* 的方式）。然後比較左程式碼序列和右程式碼序列。

compare(const BasicBlock, const BasicBlock)¶

比較兩個 *BasicBlock* 實例。

它枚舉來自左 *BB* 和右 *BB* 的指令。

1. 它使用 cmpValues 方法為左右指令分配序號。

2. 如果左側或右側其中之一是 GEP (GetElementPtr)，則將 GEP 視為大於其他指令。如果兩個指令都是 GEP，則使用 cmpGEP 方法進行比較。如果結果為 -1 或 1，則將其傳遞到頂層比較（返回它）。

3.1. 比較操作。呼叫 cmpOperation 方法。如果結果為 -1 或 1，則返回它。

3.2. 比較運算元數量，如果結果為 -1 或 1，則返回它。

3.3. 比較運算元本身，使用 cmpValues 方法。如果結果為 -1 或 1，則返回結果。

3.4. 比較運算元類型，使用 cmpType 方法。如果結果為 -1 或 1，則返回結果。

3.5. 繼續到下一個指令。

我們可以在 3 種情況下完成指令枚舉

4.1. 我們到達了左右基本區塊的末尾。我們沒有在步驟 1-3 中退出，因此內容相等，返回 0。

4.2. 我們已到達左側基本區塊的末尾。返回 -1。

4.3. 返回 1（我們到達了右側基本區塊的末尾）。

cmpGEP ¶

比較兩個 GEP（getelementptr 指令）。

它與常規操作比較的不同之處僅在於：可以使用 accumulateConstantOffset 方法。

因此，如果我們獲得左右 GEP 的常數偏移量，則將其作為數字進行比較，並返回比較結果。

否則，將其視為常規操作（請參閱上一段）。

cmpOperation ¶

比較指令操作碼和一些重要的操作屬性。

比較操作碼，如果不同則返回結果。
比較運算元數量。如果不同 – 返回結果。

3. 比較操作類型，使用 cmpType。同樣 – 如果類型不同，則返回結果。

4. 比較 subclassOptionalData，使用 getRawSubclassOptionalData 方法獲取它，並像數字一樣比較它。

比較運算元類型。

6. 對於某些特定指令，檢查一些重要屬性的等效性（在我們的例子中是關係）。例如，我們必須比較 load 指令的對齊方式。

O(log(N))¶

上述方法實作了順序關係。後者可以用於二元樹中節點的比較。因此，我們可以將函數集組織到二元樹中，並將查找過程的成本從 O(N*N) 降低到 O(log(N))。

Merging process, mergeTwoFunctions ¶

一旦 MergeFunctions 檢測到當前函數 (G) 等於之前分析過的函數（函數 F），它就會呼叫 mergeTwoFunctions(Function*, Function*)。

操作會以下列方式影響 FnTree 的內容：F 將保留在 FnTree 中。與 F 相等的 G 不會被添加到 FnTree 中。對 G 的呼叫將被替換為其他內容。它會更改呼叫者的主體。因此，呼叫 G 的函數將被放入 Deferred 集合中，並從 FnTree 中移除，然後再次分析。

方法如下

1. 最理想的情況：當我們可以使用別名，並且 F 和 G 都是弱的。我們將它們都設為第三個強函數 H 的別名。實際上 H 就是 F。請參閱下文了解其製作方式（但最好直接查看原始碼）。嗯，在這種情況下，我們可以將所有地方的 G 都替換為 F，我們在這裡使用 replaceAllUsesWith 操作 (RAUW)。

2. F 無法被覆寫，而 G 可以。接下來的做法會很好：在合併了使用可覆寫函數的地方之後，仍然使用可覆寫的 Stub。因此，嘗試將 G 設為 F 的別名，或在 F 周圍建立可覆寫的尾部呼叫包裝器，並將 G 替換為該呼叫。

3. F 和 G 都無法被覆寫。我們不能使用 RAUW。我們只能更改呼叫者：呼叫 F 而不是 G。這就是 replaceDirectCallers 所做的。

以下是詳細的主體描述。

If “F” may be overridden ¶

正如 mayBeOverridden 註解所述：“是否可以在連結時將此全域變數的定義替換為不相等的東西”。如果是這樣，那就沒問題：我們可以使用 F 的別名而不是 G，或更改呼叫指令本身。

HasGlobalAliases, removeUsers ¶

首先考慮我們有一個函數名稱到另一個函數名稱的全域別名的情況。我們的目的是使它們都成為第三個強函數的別名。雖然如果我們保持 F 存活並且沒有重大更改，我們可以將其保留在 FnTree 中。嘗試結合這兩個目標。

對 F 本身進行 Stub 替換，使用 F 的別名。

1. 建立 Stub 函數 H，其名稱和屬性與函數 F 相同。它採用 F 和 G 的最大對齊方式。

2. 將所有函數 F 的使用替換為函數 H 的使用。這是一個兩步驟的過程。首先，我們必須考慮到，所有呼叫 F 的函數都將被更改：因為我們更改了呼叫引數（從 F 到 H）。如果是這樣，我們必須在此過程之後再次審查這些呼叫者函數。我們從 FnTree 中移除呼叫者，名為 removeUsers(F) 的方法會執行此操作（不要與 replaceAllUsesWith 混淆）

2.1. 在 removeUsers(Value* V) 內部，我們遍歷所有使用值 V（或在我們的上下文中為 F）的值。如果值是指令，我們會轉到持有此指令的函數，並將其標記為待重新分析（放入 Deferred 集合），我們也會從 FnTree 中移除呼叫者。

2.2. 現在我們可以進行替換：呼叫 F->replaceAllUsesWith(H)。

3. H（現在“正式”扮演 F 的角色）被替換為 F 的別名。對 G 執行相同的操作：將其替換為 F 的別名。因此，最終在所有使用 F 的地方，我們都使用 H，而它是 F 的別名，並且在所有使用 G 的地方，我們也都有 F 的別名。

將 F 連結設定為私有。使其強大 :-)

No global aliases, replaceDirectCallers ¶

如果不支持全域別名。我們呼叫 replaceDirectCallers。只需遍歷所有對 G 的呼叫，並將其替換為對 F 的呼叫。如果您查看該方法，您將看到它也會掃描所有對 G 的使用，如果使用是被呼叫者（如果使用者是呼叫指令並且 G 用作要呼叫的內容），我們會將其替換為對 F 的使用。

If “F” could not be overridden, fix it!¶

我們呼叫 writeThunkOrAlias(Function *F, Function *G)。在這裡，我們首先嘗試將 G 替換為 F 的別名。以下條件至關重要

目標應支援全域別名，
G 的位址本身應該不重要、未命名且未在任何地方被引用，
函數應具有外部、本地或弱連結。

否則，我們編寫 thunk：一些具有 G 介面並呼叫 F 的包裝器，以便可以用此包裝器替換 G。

writeAlias

正如 llvm 參考文獻所述

“別名充當別名值的第二個名稱”。因此，我們只想為 F 建立第二個名稱，並使用它來代替 G

建立全域別名本身 (GA)，
調整 F 的對齊方式，使其必須是當前對齊方式和 G 對齊方式的最大值；
替換 G 的使用

3.1. 首先使用 removeUsers 方法（請參閱上一章）將所有 G 的呼叫者標記為待重新分析，

3.2. 呼叫 G->replaceAllUsesWith(GA)。
擺脫 G。

writeThunk

正如方法註解中所寫

“將 G 替換為對 bitcast(F) 的簡單尾部呼叫。也將 G 的直接使用替換為 bitcast(F)。刪除 G。”

一般來說，當我們想要替換被呼叫者時，它與通常的做法相同，除了第一點

1. 我們在 F 周圍產生尾部呼叫包裝器，但具有允許使用它來代替 G 的介面。

“像往常一樣”：然後是 removeUsers 和 replaceAllUsesWith。
擺脫 G。

文件

參與

額外連結

本頁