編譯器中的圖論算法

1. 前言

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

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

圖1. LLVM的應(yīng)用

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

本文的目的是以一種通俗易懂的方式給需要了解這個(gè)算法的朋友一個(gè)感性的認(rèn)識(shí)。如果需要看原論文或者關(guān)于深度學(xué)習(xí)編譯器論文的可以后臺(tái)回復(fù)idom獲取。

2. 支配樹簡介

2.1 支配樹定義

對(duì)于一張有向圖(可以有環(huán))，我們規(guī)定一個(gè)起點(diǎn)，從點(diǎn)到圖上另一個(gè)點(diǎn)可能存在多條路徑,對(duì)于從到的任意路徑中，都存在一個(gè)點(diǎn) ，即從到必須經(jīng)過，那么我們稱為的支配點(diǎn)。

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

2.2 支配樹在編譯器中的應(yīng)用

• 計(jì)算支配邊界，構(gòu)造SSA
• 循環(huán)不變量提升

更多應(yīng)用歡迎補(bǔ)充。

3. 基本概念

3.1 DFS樹

對(duì)圖進(jìn)行深度優(yōu)先遍歷得到的一顆樹稱為DFS樹。樹上的每一個(gè)節(jié)點(diǎn)都有一個(gè)按照深度優(yōu)先遍歷的順序得到的編號(hào)。

圖2.深度優(yōu)先搜索樹

如圖2所示，節(jié)點(diǎn)和實(shí)線虛線共同構(gòu)成了一個(gè)有向圖，對(duì)有向圖進(jìn)行深度優(yōu)先遍歷就形成了DFS樹。其中實(shí)線是DFS的樹邊。紅色數(shù)字表示按照深度優(yōu)先遍歷的順序得到的編號(hào)，紅色字母表示該節(jié)點(diǎn)的半必經(jīng)節(jié)點(diǎn)。

3.2 樹邊與非樹邊

如果在DFS樹中存在一條由到的邊，則頂點(diǎn)是頂點(diǎn)的父節(jié)點(diǎn)，這條邊稱為樹邊。

記作

如果在有向圖中存在一條到的邊，則頂點(diǎn)是頂點(diǎn)的前驅(qū)節(jié)點(diǎn)。注意要與父節(jié)點(diǎn)相區(qū)別，因?yàn)楦腹?jié)點(diǎn)是在DFS樹上存在由到的邊。到的邊中除去樹邊以外的邊稱作非樹邊。

的前驅(qū)節(jié)點(diǎn)記作

非樹邊記作

如圖2中是的父節(jié)點(diǎn)。到的邊為樹邊

3.3 祖先與完全祖先

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

記作

如圖2中都是的祖先，因?yàn)檫@些點(diǎn)都可以沿著實(shí)線邊(DFS樹邊)到點(diǎn)

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

記作

如圖2中都是的完全祖先，因?yàn)檫@些點(diǎn)都可以沿著實(shí)線邊(DFS 樹邊)到點(diǎn)。與祖先的唯一區(qū)別就是不包括自身。

3.4 橫跨邊與返祖邊

右子樹的節(jié)點(diǎn)指向左子樹節(jié)點(diǎn)的邊。橫跨邊的起點(diǎn)永遠(yuǎn)大與終點(diǎn)編號(hào)，因?yàn)镈FS樹中右子樹的遍號(hào)永遠(yuǎn)大于左子樹的編號(hào)。

記作

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

子節(jié)點(diǎn)到其完全祖先的邊叫返祖邊。

記作

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

4. 半支配路徑與半支配節(jié)點(diǎn)

在求支配節(jié)點(diǎn)之前，我們首先需要了解半支配路徑，然后求出半必經(jīng)節(jié)點(diǎn)及必經(jīng)節(jié)點(diǎn)，最終得到整個(gè)支配節(jié)點(diǎn)樹。

圖3. 求支配節(jié)點(diǎn)樹路線圖

4.1 半支配路徑

公式表示:

通俗解釋：

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

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

• 樹邊半支配路徑

樹邊半支配路徑比較特殊，只包含兩個(gè)點(diǎn)，這兩個(gè)點(diǎn)在一條樹邊上。

• 非樹邊半支配路徑

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

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

圖4. 半支配路徑示意圖

4.2 半支配節(jié)點(diǎn)

公式表示：

通俗解釋：

V的半支配節(jié)點(diǎn)為所有終點(diǎn)為V的半支配路徑中，起點(diǎn)值最小的那個(gè)。

因?yàn)榘胫渎窂接袃深?，一是樹邊半支配路徑，二是非樹邊半支配路徑，因此也可以將半支配?jié)點(diǎn)的求法化簡為這兩類

公式化簡：

根據(jù)圖形理解更加簡單：

其中黃色線對(duì)應(yīng)公式中的第(1)種情況

紫色線和綠色線對(duì)應(yīng)公式中的第(2)種情況

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

圖5.支配節(jié)點(diǎn)的三種情況

求半支配節(jié)點(diǎn)的偽代碼

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 最小的點(diǎn)。因?yàn)槭菍?duì) DFS 樹進(jìn)行逆序，因此求 的時(shí)候紫色線和綠色線上各節(jié)點(diǎn)的 semi 值已經(jīng)是已知的了。

5. 支配節(jié)點(diǎn)與支配樹

LLVM在2017年之前采用的是SLT算法，新的版本使用的是semi-NCA算法。兩者都是在上一節(jié)介紹的半必經(jīng)節(jié)點(diǎn)的基礎(chǔ)上求得必經(jīng)節(jié)點(diǎn)。下文會(huì)分別對(duì)這兩種算法進(jìn)行介紹，并比較其時(shí)間復(fù)雜度。

5.1 SLT 算法

SLT算法會(huì)根據(jù)前文求出的半支配節(jié)點(diǎn)進(jìn)一步求出直接支配節(jié)點(diǎn)。

公式表示：

其中在

u

通俗解釋：

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

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

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

計(jì)算支配節(jié)點(diǎn)樹的偽代碼:

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

以一個(gè)實(shí)例加深對(duì)SLT算法的理解:

• a)此時(shí) semi(4)=2,因此 bucket(2)=4。
• b)此時(shí) semi(3)=1,因此 bucket(1)=3。此時(shí) parent(3)=2,將 bucket(2)中的4彈出，2到4的路徑上3的semi值最小，滿足代碼中的if 條件，因此idom(4)=3
• c)此時(shí)semi(2)=0,因此bucket(0)=2。此時(shí)parent(2)=1,將bucket(1)中的3彈出，1到3的路徑上2的semi值最小，滿足代碼中的if條件，因此idom(3)=2
• d)此時(shí)semi(1)=0,因此 bucket(0)={2,1},此時(shí) parent(1)=0,將 bucket(0)中的棧頂元素 1 彈出，滿足 else 條件，idom(1)=0，繼續(xù)將 bucket(0)中的2彈出，滿足else條件,idom(2)=0
• e)最后執(zhí)行下一個(gè)循環(huán)，直接支配節(jié)點(diǎn)與半支配節(jié)點(diǎn)進(jìn)行比較，此時(shí) 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

為了方便理解，來看下面這個(gè)簡單實(shí)例：

semi-NCA算法實(shí)例

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

小結(jié)

本節(jié)主要介紹了 LLVM 中求支配節(jié)點(diǎn)樹的兩種算法，分別是 SLT 和 semi-NCA 算法。兩種算法的時(shí)間復(fù)雜度和空間復(fù)雜度如下。

對(duì)于算法的詳細(xì)分析、證明和實(shí)驗(yàn)結(jié)果可以參考原論文。

6. 后記

本篇文章缺少算法的證明，僅提供一些自己在學(xué)習(xí)過程中對(duì)這兩個(gè)算法感性的認(rèn)識(shí)，避免枯燥的公式。希望能夠給需要學(xué)習(xí)這個(gè)算法的人提供一些幫助。

后續(xù)準(zhǔn)備寫一個(gè)編譯器中的圖論算法系列，題目如下：

• 編譯器中的圖論算法之支配樹
• 編譯器中的圖論算法之支配邊界

歡迎各位朋友幫忙補(bǔ)充更多的編譯器中用到的圖論算法或者其它感興趣的編譯器中的算法。