LLVM 中的相依性圖¶
簡介¶
相依性圖是編譯器中用於分析各種程式元素之間關係的有用工具，以幫助引導最佳化。這些圖背後的概念在論文 [1] 和 [2] 中有所描述。
這些概念在 LLVM 中的實作可能與論文中提到的略有不同。這些差異記錄在實作細節中。
資料相依性圖¶
在其最簡單的形式中，資料相依性圖 (DDG) 表示個別指令之間的資料相依性。此類圖中的每個節點代表單一指令，並被稱為「原子」節點。也可以將一些在它們之間具有簡單 def-use 相依性的原子節點組合成包含多個指令的較大節點。
如 [1] 中所述，DDG 使用圖抽象化將圖的強連通元件中的節點分組到稱為 pi-block 的特殊節點中。pi-block 代表阻止重新排序轉換的資料相依性循環。由於圖的任何強連通元件都是形成循環的所有節點的最大子圖，因此 pi-block 最多只有一層深度。換句話說，沒有 pi-block 巢狀在另一個 pi-block 內，從而產生最多只有一層深度的階層式表示。
例如，考慮以下程式碼
for (int i = 1; i < n; i++) {
b[i] = c[i] + b[i-1];
}
此程式碼包含一個對自身具有迴圈攜帶相依性的語句，從而在 DDG 中建立一個循環。下圖說明了相依性循環如何通過多個 def-use 關係和記憶體存取相依性傳遞。
此範例對應的 DDG 將具有一個 pi-block，其中包含所有參與循環的節點，如下所示
程式相依性圖¶
程式相依性圖 (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。該論文描述了節點之間五種類型的相依性邊緣，即迴圈相依性、flow-、anti-、output- 和 input- 相依性。在此實作中，記憶體邊緣表示 flow-、anti-、output- 和 input- 相依性。但是，迴圈相依性沒有明確表示，因為它們主要表示迴圈結構與迴圈內程式元素之間的關聯，並且這種關聯在 LLVM IR 本身中非常明顯。
該論文描述了兩種類型的 pi-block；recurrences，其主體是 SCC，以及 IN 節點，其主體不是任何 SCC 的一部分。在此實作中，pi-block 僅為 recurrences 建立。IN 節點仍然是圖中的簡單 DDG 節點。