編譯器中的圖論算法

1. 前言

LLVM是一款開源的編譯器框架，近年來已經逐漸超越GCC。

許多深度學習編譯框架TVM、Tensorflow XLA的后端也是使用的它。正是由于其友好的Lisense，模塊化及統一的IR，使得其越來越流行。因此對LLVM的研究很有必要。

圖1. LLVM的應用

文中介紹了LLVM中構造支配樹的兩種算法，分別是SLT算法與Semi-NCA算法。構造支配樹的算法，就是圖論在編譯器中的一個應用。如果蛻去LLVM的外衣，相信很多參加過ACM比賽的選手應該對支配樹的構造很熟悉。

本文的目的是以一種通俗易懂的方式給需要了解這個算法的朋友一個感性的認識。如果需要看原論文或者關于深度學習編譯器論文的可以后臺回復idom獲取。

2. 支配樹簡介

2.1 支配樹定義

對于一張有向圖(可以有環)，我們規定一個起點，從點到圖上另一個點可能存在多條路徑,對于從到的任意路徑中，都存在一個點，即從到必須經過，那么我們稱為的支配點。

用表示離點最近的支配點, 對于原圖除外，每一個點，從向建一條邊，最后我們得到了一顆以為根的樹，這棵樹就是支配樹(Dominator tree)

2.2 支配樹在編譯器中的應用

計算支配邊界，構造SSA
循環不變量提升

更多應用歡迎補充。

3. 基本概念

3.1 DFS樹

對圖進行深度優先遍歷得到的一顆樹稱為DFS樹。樹上的每一個節點都有一個按照深度優先遍歷的順序得到的編號。

圖2.深度優先搜索樹

如圖2所示，節點和實線虛線共同構成了一個有向圖，對有向圖進行深度優先遍歷就形成了DFS樹。其中實線是DFS的樹邊。紅色數字表示按照深度優先遍歷的順序得到的編號，紅色字母表示該節點的半必經節點。

3.2 樹邊與非樹邊

如果在DFS樹中存在一條由到的邊，則頂點是頂點的父節點，這條邊稱為樹邊。

記作

如果在有向圖中存在一條到的邊，則頂點是頂點的前驅節點。注意要與父節點相區別，因為父節點是在DFS樹上存在由到的邊。到的邊中除去樹邊以外的邊稱作非樹邊。

的前驅節點記作

非樹邊記作

如圖2中是的父節點。到的邊為樹邊

3.3 祖先與完全祖先

是的祖先，如果在DFS樹中存在一條由到的路徑，可以等于。

記作

如圖2中都是的祖先，因為這些點都可以沿著實線邊(DFS樹邊)到點

是的完全祖先，如果在樹中存在一條由到的路徑，不等于。

記作

如圖2中都是的完全祖先，因為這些點都可以沿著實線邊(DFS 樹邊)到點。與祖先的唯一區別就是不包括自身。

3.4 橫跨邊與返祖邊

右子樹的節點指向左子樹節點的邊。橫跨邊的起點永遠大與終點編號，因為DFS樹中右子樹的遍號永遠大于左子樹的編號。

記作

如圖2所示，的這四條邊都是橫跨邊

子節點到其完全祖先的邊叫返祖邊。

記作

如圖2所示，這兩條邊都是返祖邊。

4. 半支配路徑與半支配節點

在求支配節點之前，我們首先需要了解半支配路徑，然后求出半必經節點及必經節點，最終得到整個支配節點樹。

圖3. 求支配節點樹路線圖

4.1 半支配路徑

公式表示:

通俗解釋：

在DFS樹中存在一條路徑，如果這條路徑中(不包括起點和終點)的每一個點的編號都大于終點的編號，則該路徑為一條半支配路徑。

根據定義可以將半支配路徑分為兩類：

樹邊半支配路徑

樹邊半支配路徑比較特殊，只包含兩個點，這兩個點在一條樹邊上。

非樹邊半支配路徑

非樹邊半支配路徑即路徑上指向終點的邊為非樹邊，這條非樹邊要么是橫跨邊要么是返祖邊。

如圖4所示，黃色加粗的線為樹邊半支配路徑，綠色和紫色是非樹邊半支配路徑，其中綠色邊含有橫跨邊，紫色邊含有返祖邊。

圖4. 半支配路徑示意圖

4.2 半支配節點

公式表示：

通俗解釋：

V的半支配節點為所有終點為V的半支配路徑中，起點值最小的那個。

因為半支配路徑有兩類，一是樹邊半支配路徑，二是非樹邊半支配路徑，因此也可以將半支配節點的求法化簡為這兩類

公式化簡：

根據圖形理解更加簡單：

其中黃色線對應公式中的第(1)種情況

紫色線和綠色線對應公式中的第(2)種情況

其中的可以取下圖中和兩種情況，可以是綠色線或紫色線上的任意一個點，包括或。綠色線或紫色線就是公式中的條件

圖5.支配節點的三種情況

求半支配節點的偽代碼

Create a DFS tree T.
semi(w) = w | w ∈ V
for w ∈ V ? {r} in reverse preorder by the DFS
    for v ∈ pred G (w)
        u = eval(v)
        if semi(u) < semi(w)
           semi(w) = semi(u)
    end for
    Link parent(w) and w
 end for

其中的 eval(v)就是在求黃色、紫色、綠色各條線上 semi 最小的點。因為是對 DFS 樹進行逆序，因此求的時候紫色線和綠色線上各節點的 semi 值已經是已知的了。

5. 支配節點與支配樹

LLVM在2017年之前采用的是SLT算法，新的版本使用的是semi-NCA算法。兩者都是在上一節介紹的半必經節點的基礎上求得必經節點。下文會分別對這兩種算法進行介紹，并比較其時間復雜度。

5.1 SLT 算法

SLT算法會根據前文求出的半支配節點進一步求出直接支配節點。

公式表示：

其中在

通俗解釋：

在DFS樹中，到的路徑上有一點，的sdom值是該路徑上最小的點，如果等于則等于，否則等于

下面的兩張圖是對求 idom 的公式兩種情況的一個總結，可以讓我們的理解更加直觀。

公式中的情況1公式中的情況2

計算支配節點樹的偽代碼:

Create a DFS tree T.
for w ∈ V ? {r} in reverse preorder by the DFS
  Calculate semi dominator for w
  Add w to bucket of semi(w)
  while bucket of parent(w) is not empty do
    v = pop one element from the bucket
    u = eval(v)
    if semi(u) < semi(v) then
      idom(v) = u
    else
      idom(v) = semi(v)
    end if
  end while
end for
for w ∈ V ? {r} in preorder by the DFS do
  if idom(w) != semi(w) then
    idom(w) = idom(idom(w))
  end if
end for

以一個實例加深對SLT算法的理解:

a)此時 semi(4)=2,因此 bucket(2)=4。
b)此時 semi(3)=1,因此 bucket(1)=3。此時 parent(3)=2,將 bucket(2)中的4彈出，2到4的路徑上3的semi值最小，滿足代碼中的if 條件，因此idom(4)=3
c)此時semi(2)=0,因此bucket(0)=2。此時parent(2)=1,將bucket(1)中的3彈出，1到3的路徑上2的semi值最小，滿足代碼中的if條件，因此idom(3)=2
d)此時semi(1)=0,因此 bucket(0)={2,1},此時 parent(1)=0,將 bucket(0)中的棧頂元素 1 彈出，滿足 else 條件，idom(1)=0，繼續將 bucket(0)中的2彈出，滿足else條件,idom(2)=0
e)最后執行下一個循環，直接支配節點與半支配節點進行比較，此時 idom(3)不等于sdom(3),idom(4)不等于sdom(4)，因此idom(3)=idom(2)=0，idom(4)=idom(idom(3))=0

5.2 semi-NCA 算法

與上文介紹的SLT算法相比，semi-NCA算法無疑更容易理解，這也是目前 LLVM正在使用的算法。下面直接上代碼，相信大家一看就能夠理解。

Create a DFS tree T.
Calculate semidominator for w
Create a tree D and initialize it with r as the root.
for v ∈ V ? {r} in preorder by the DFS do
  Ascend the path r *—>DparentT(v) and ?nd the deepest vertex which number is smaller than or equal to sdom(v).
  set this vertex as parent for v in D.
end for

為了方便理解，來看下面這個簡單實例：

semi-NCA算法實例

圖 a)是已經求出的半支配節點圖，左邊的數字表示每個節點的半支配節點。
圖 b)是支配節點樹(代碼中的 D 樹)，目前只求出來 0 到 4 節點的支配節點。
圖 c)是求節點 5 支配節點的一個實例。節點 5 在 DFS 樹中的父節點是 4。因此在 D 中沿著根節點 0 到 4 的路徑上找到第一個小于 semi(5)的節點，此節點為 0，也就是 5 的直接支配節點。