LLVM 中的依存圖¶
簡介¶
依存圖是編譯器中用於分析各種程式元素之間關係的有用工具，以幫助指導優化。這些圖背後的概念在論文 [1] 和 [2] 中有描述。
LLVM 中這些概念的實現可能與論文中提到的略有不同。這些差異記錄在 實作細節 中。
資料依存圖¶
在其最簡單的形式中，資料依存圖（或 DDG）表示單個指令之間的資料依賴關係。此類圖中的每個節點表示單個指令，稱為「原子」節點。也可以將一些在其之間具有簡單定義-使用依賴關係的原子節點組合成包含多個指令的更大節點。
如 [1] 中所述，DDG 使用圖抽象將圖的強連通分量中的一部分節點分組到稱為 pi 塊的特殊節點中。pi 塊表示阻止重新排序轉換的資料依賴關係循環。由於圖的任何強連通分量都是形成循環的所有節點的最大子圖，因此 pi 塊最多只有一層深。換句話說，沒有 pi 塊嵌套在另一個 pi 塊中，從而產生最多只有一層深的層次結構表示。
例如，請考慮以下內容
for (int i = 1; i < n; i++) {
b[i] = c[i] + b[i-1];
}
這段程式碼包含一個語句，該語句對自身具有循環攜帶依賴關係，從而在 DDG 中創建一個循環。下圖說明了依賴關係循環如何通過多個定義-使用關係和記憶體存取依賴關係進行。
對應於此範例的 DDG 將具有一個包含參與循環的所有節點的 pi 塊，如下所示
程式依存圖¶
程式依存圖（或 PDG）的結構與 DDG 類似，但它能夠表示程式元素（如指令、指令組、基本塊或基本塊組）之間的資料依賴關係和控制流程依賴關係。
高階設計¶
DDG 和 PDG 都是有向圖，它們繼承自 DirectedGraph 類別。每個實作都擴展了其對應的節點和邊緣類型，從而產生如下方 UML 圖所示的繼承關係。
圖形建構¶
圖形建構演算法會考慮給定指令集或基本塊元素之間的依賴關係。任何進出不屬於該範圍的指令的依賴關係都將被忽略。DDG 的建構演算法步驟與 PDG 的建構演算法步驟非常相似。因此，其中一個設計目標是重複使用建構演算法程式碼，以便在允許兩種實作定義自己獨特且獨立的節點和邊緣類型的同時，建立 DDG 和 PDG 表示。這是透過使用著名的建構器設計模式來實現的，該模式將依賴圖的建構從其具體表示中隔離出來。
以下 UML 圖描述了設計模式應用於依賴圖實作的整體結構。
請注意，用於建構兩種圖表的通用程式碼在 DependenceGraphBuilder 類別中提供，而 DDGBuilder 和 PDGBuilder 則透過覆寫 DependenceGraphBuilder 中定義的虛擬方法來控制圖表建構的某些方面。
另請注意，此圖表中使用的步驟和名稱僅供說明之用，可能與實際實作中的步驟和名稱不同。
設計權衡¶
優點：¶
建構器允許針對 DDG 和 PDG 重複使用圖形建構程式碼。
建構器允許我們將 DDG 和 PDG 建立為獨立的圖表。
DDG 節點和邊緣與 PDG 節點和邊緣完全分離，允許它們輕鬆且獨立地更改。
缺點：¶
建構器一開始可能會被認為是過度工程。
與 PDG 節點和邊緣相比，DDG 節點和邊緣之間存在一些相似之處，但類別定義很少重複使用。
鑑於節點和邊緣類型相當簡單，而且無論如何程式碼重複使用的機會很少，因此這是可以容忍的。
實作細節¶
DDG 的當前實作與 [1] 中描述的依賴圖略有不同，其差異如下：
本文中的圖形節點表示三個主要的程式組成部分，即*賦值語句*、*for 迴圈標頭*和*while 迴圈標頭*。在這個實作中，DDG 節點自然地表示 LLVM IR 指令。此實作中的賦值語句通常包含一個表示
store指令的節點，以及一些計算賦值右側並透過 def-use 邊緣連接到store節點的個別節點。迴圈標頭指令在此實作中並未表示為特殊節點，因為它們的使用有限，並且可以輕鬆識別，例如透過LoopAnalysis。本文描述了節點之間的五種類型的依賴邊緣，即*迴圈依賴*、*資料流*、*反*、*輸出*和*輸入*依賴。在此實作中，*記憶體*邊緣表示*資料流*、*反*、*輸出*和*輸入*依賴。但是，*迴圈依賴*並未明確表示，因為它們主要表示迴圈結構與迴圈內程式元素之間的關聯，而這種關聯在 LLVM IR 本身中相當明顯。
本文描述了兩種 pi 塊；主體是 SCC 的*遞迴*和主體不屬於任何 SCC 的*IN* 節點。在此實作中，僅為*遞迴*建立 pi 塊。*IN* 節點在圖形中保留為簡單的 DDG 節點。