MergeFunctions 遍 traversal，如何運作¶

簡介 ¶

有時，程式碼會包含相同的函數，或者即使在 IR 層級上不相同但執行完全相同操作的函數（例如：乘以 2 和「shl 1」）。這可能會因為多種原因而發生：主要是使用模板和自動程式碼產生器。不過，有時使用者本身可能會寫兩次相同的東西 :-)

此遍 traversal 的主要目的是識別此類函數並將其合併。

本文檔是遍 traversal 註釋的延伸，並描述了遍 traversal 的邏輯。它描述了用於比較函數的演算法，並解釋了如何正確組合相同的函數以保持模組有效。

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

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

我需要了解哪些內容才能理解本文檔？¶

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

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

萬花筒教學是一個很好的起點

LLVM 教學：目錄

理解教學的第三章尤為重要

萬花筒教學

讀者也應該知道 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 ¶

這個演算法非常簡單

將所有模組的函數放入「工作清單」中。

2. 掃描「工作清單」中的函數兩次：第一次僅列舉強函數，然後僅列舉弱函數。

2.1. 迴圈主體：從「工作清單」中取出一個函數（稱為「FCur」），並嘗試將其插入「FnTree」中：檢查「FCur」是否等於「FnTree」中的其中一個函數。如果在「FnTree」中存在相等的函數（稱為「FExists」）：將函數「FCur」與「FExists」合併。否則，將「工作清單」中的函數添加到「FnTree」中。

3. 一旦「工作清單」掃描和合併操作完成，請檢查「Deferred」清單。如果它不為空：用「Deferred」清單重新填充「工作清單」的內容，並重做步驟 2，如果「Deferred」清單為空，則退出方法。

比較和對數搜尋 ¶

讓我們回顧一下我們的任務：對於模組「M」中的每個函數「F」，我們必須在最短的時間內找到相等的函數「F'」，並將它們合併成單個函數。

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

我們必須引入一個適用於每對函數的單一規則，並遵循此規則，然後評估哪個函數更大。它會是什麼樣的規則？讓我們將其聲明為「compare」方法，它返回 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*。

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

*可變參數*。 *LHS* 和 *RHS* 應該都必須有或都沒有 *可變參數*。

*呼叫慣例* 應該相同。

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

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

函式主體比較。正如方法註釋中所寫：

「我們按照 CFG 的順序進行遍歷，因為連結串列中區塊的實際順序並不重要。我們的遍歷從兩個函式的入口區塊開始，然後按照順序從每個終止符號中取出每個區塊。作為一個結果，這也意味著無法到達的區塊將被忽略。」

因此，使用這種遍歷方式，我們可以按照相同的順序從「*左*」和「*右*」獲取 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 傳遞版本中實作。但遺憾的是，它不具備遞移性。這是我們唯一無法轉換為小於-等於-大於比較的案例。這是一個罕見的情況，10000 個函數中有 4-5 個函數（在測試套件中檢查過），我們希望讀者能原諒我們為了獲得 O(log(N)) 傳遞時間而做出的這種犧牲。

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

合併過程，mergeTwoFunctions ¶

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

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

方法如下：

1. 最理想的情況：當我們可以使用別名，並且 F 和 G 都是弱函數時。我們讓它們都使用指向第三個強函數 H 的別名。實際上 H 就是 F。請參閱下方如何實現（但最好直接查看原始碼）。這是一種我們可以在任何地方用 F 替換 G 的情況，我們在這裡使用 replaceAllUsesWith 操作 (RAUW)。

2. F 不能被覆寫，而 G 可以。最好執行以下操作：在合併使用可覆寫函數的位置之後，仍然使用可覆寫的 stub。因此，嘗試使 G 成為 F 的別名，或者在 F 周圍創建可覆寫的尾調用包裝器，並用該調用替換 G。

3. F 和 G 都不能被覆寫。我們不能使用 RAUW。我們只能更改調用者：調用 F 而不是 G。這就是 replaceDirectCallers 的作用。

以下是詳細的正文描述。

如果「F」可以被覆寫 ¶

從 mayBeOverridden 的註釋中可以看出：「這個全局變量的定義是否可以在連結時被替換為不等價的東西」。如果是這樣，那就沒問題：我們可以使用指向 F 的別名來代替 G，或者更改調用指令本身。

HasGlobalAliases、removeUsers ¶

首先考慮我們有一個函數名稱的全局別名指向另一個函數名稱的情況。我們的目的是讓它們都使用指向第三個強函數的別名。但是，如果我們保持 F 存活並且不做重大更改，我們可以將其保留在 FnTree 中。嘗試結合這兩個目標。

使用指向 F 的別名對 F 本身進行 stub 替換。

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 的連結設定為私有。使其強連結。

無全域別名，replaceDirectCallers ¶

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

如果「F」無法被覆寫，請修復它！¶

我們呼叫 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。

文件

參與

其他連結

本頁