5. 基于圖的做法
依賴圖覆寫的指令選擇器是目前能得到的最強大的代碼生成器。通過允許輸入及模式具有任意的圖形狀，指令選擇器能夠接受整個函數為輸入——這被稱為全局指令選擇——有可能處理各種機器指令，包括硬體循環及SIMD指令。最重要的，與局限在單個基本塊的基于DAG覆寫的技術相比，全局指令選擇器可以在多個塊間自由地移動及覆寫節點。這增加了應用複雜模式的機會，這可能導緻性能提升及減少功耗。
因為大多數圖覆寫方法通過應用某些通用的子圖同構算法來處理模式比對問題，我們将從簡單地看幾個這樣的算法開始。
圖5.1：圖覆寫問題的一個例子。模式執行個體由虛線及包含了該模式比對節點的陰影面積表示。
5.1. 子圖同構算法
子圖同構問題是檢測是否可以轉動、扭轉或鏡像任意一個圖Ga，使得它成為另一個圖Gb的一個子圖。在這樣的情形裡，稱Ga是Gb的一個子圖同構，它已知是待定的一個NP完全問題【55】。因為在許多其他領域都能發現子圖同構，大量的研究一直緻力于這個問題。在本節，我們将簡單看一下兩個這樣的圖比對算法。
一個早期著名的子圖同構算法由Ullmann開發【226】。在1976年的論文裡，Ullmann将确定一個圖Ga = (Va, Ea)是否子圖同構于另一個圖Gb = (Vb,Eb) 的問題描述為找出一個布爾|Va| × |Vb|矩陣Mꞌ，使得
C = Mꞌ (MꞌB)T
∀i, j, 1 ≤ i ≤ |Va|, 1 ≤ j ≤ |Vb|: (aij= 1) ⇒ (cij = 1)
成立，其中A與B分别是Ga與Gb的相鄰矩陣。在Mꞌ這樣的執行個體裡，每行隻包含一個1，而每列最多包含一個1。通過初始化每個單元mꞌij為1，然後裁剪掉1直到找到一個解答來蠻力查找Mꞌ。為了減少查找空間，Ullmann開發了一個過程在開始查找前消除某些1。不過，該算法的最壞情況時間複雜度是O(n!n2)（根據【57】），并且使用相鄰矩陣排斥了對可能出現在程式表示中多邊界圖的處理。
最近，Cordella等【57】提出了一個稱為VF2的算法，它已經被用在幾個基于DAG及圖覆寫的指令選擇器。特别的，它已經用于輔助指令集提取（instruction set extraction，ISE；參考【10，50，75】為例）。大緻上，通過一個疊代的方式把一個新對加入集合，VF2算法遞歸地構造“(n,m)對”的一個映射集，其中n ∈ Ga而m ∈ Gb。該算法的核心是一個規則，它禁止添加阻止形成從Ga到Gb一個有效子圖同構映射的對。在最壞情形下，該算法具有O(n!n)時間複雜度，但報告表示它已經被成功地應用于包含超過一千個節點的圖，因為在最好的情形下，它具有多項式時間複雜度。另外，VF2算法可以處理多邊界圖（multi-edge graphs）。
在本調查進行中找到的、别的關于子圖同構的論文包括：Guo等【119】，Krissinel與Henrick【152】，Sorlin與Solnon【213】（為查找子圖同構展示了一個全局限制），Gallagher【102】，Fan等【82】，Fan等【83】，及Hino等【129】。
5.2. 第一批方法
在1994年，Liem等【165】在一篇被大量引用的論文裡展示了一個在CDFG（控制及資料流圖）上執行模式比對與選擇的做法。實作在一個稱為CodeSyn的代碼生成系統裡——它又是一個稱為FlexWare的嵌入式開發環境的一部分——這是第一個已知的技術，執行全局指令選擇，同時處理資料流、控制流模式以及控制-資料流混合模式。雖然論文的做法局限于樹模式，Liem等宣稱它可以容易地擴充到DAG模式。他們的比對算法在最壞情形下使用O(n2)時間，類似于Weingart的樹模式比對程式（參考3.1節），模式構成了單個類似樹的結構。從該結構的根節點出發，比對程式比較CDFG中的目前節點，在分支處深入。模式以這樣一種方式排列，如果在該結構中更高處的比對失敗，可以删除整棵子樹，是以減少了比對時間。選擇通過動态規劃來完成。不過，Liem等沒有提供一個方法來自動地排序模式以建構樹，模式是否可以擴充到多個無關的圖還存在疑問。
同一年，Van Praet等【227，228】開發了另一個方法，它實作在CHESS中，一個作為歐洲項目部分的面向DSP的編譯器。在這個做法裡，模式被自動從一個以nML編寫的處理器描述導出——nML是一個由Fauth等構想的一個領域特定語言【85】——它指定了一幅由兩部分構成，代表了目标處理器資料路徑的圖。在一個輸入CDFG的代碼生成過程裡，處理器描述中的單元被分為包。然後這些包被轉換為對應的模式（它可以是任意圖形），接着比對與選擇模式。如果能産生一個更好的結果，模式允許重疊。論文沒有讨論比對過程，但聲明使用了一個分支界定算法（branch-and-bound algorithm）完成選擇。這個算法也假定所有的模式具有非負、不變的開銷，這允許受處理的圖被分解為更小、更簡單，可以被單獨覆寫的執行個體。不過，這阻止了對可以并行執行機器指令的利用，因為這樣指令的選擇不需要承擔額外的開銷。另外，不清楚在他們的方法中複雜處理器是否可以被正确地建構。
5.3. 單邊及雙邊覆寫技術
解決模式選擇問題的另一個方式是把它轉換為一個等價的單邊或雙邊覆寫問題。雖然基于雙邊覆寫的技術先出現，我們将先讨論單邊覆寫，因為雙邊覆寫是單邊覆寫的一個擴充。
5.3.1. 單邊覆寫
Clark等【51】發表了一篇論文描述了用于非循環計算加速器（acycliccomputation accelerators）的代碼生成方法。一個程式的部分可以由定制的加速器實作并執行，是以得到性能提升，在這個層面上，這樣的加速器是可程式設計的。算法首先在輸入的DAG上使用一個修改的Ullmann算法修剪不是子圖同構的子圖，枚舉所有可能的子圖（即模式）。一旦枚舉了所有的模式，模式選擇任務就被闡述為一個單邊覆寫問題。這個問題包含了一個布爾矩陣M，其中列代表模式執行個體，行代表被覆寫的圖形節點。是以，如果mij = 1，那節點i為模式執行個體j覆寫。這也顯示在了圖5.2裡。是以，目标是選擇列，使得每個節點以最小的代價被至少一個模式覆寫（該算法阻止重疊，Clark等辯論這減少了生成代碼的功耗）。換而言之，如果N是輸入圖中的節點集合，P是模式執行個體的集合，那麼
必須成立，同時最小化選中模式的總開銷。作者在論文中（即【58,113】）提到他們考慮後認為，單邊覆寫是解決這些問題已有、高效的啟發式，他們的實驗顯示該算法顯示出了線性的運作時間複雜度。這個方法後來被Hormati等【132】擴充，以減少加速器設計的互聯與資料中樞的延遲。
圖5.2：單邊覆寫的例子。矩陣中以星号标記的1代表潛在、但沒選中的覆寫，沒有标記的1表示最優、選中的覆寫。假定所有的模式都有相同的機關開銷。
單邊覆寫也被Martin等【168】使用，但不像Clark等，他們把這個問題闡述為一個限制程式設計模型（CP）。然後，合并了指令排程，尋找這個CP模型的最優解決。這個做法也被Floch等【91】擴充來适應VLIW架構。
5.3.2. 雙邊覆寫
單邊覆寫問題的矩陣可以重寫為一個包含非互補析取的合取（conjunctions of uncomplemented disjunctions）的布爾公式。我們将每個析取記為一個子句（clause）。作為一個例子，圖5.2（b）中的布爾矩陣可以重寫為
f = (p1 + p2)(p2+ p3)(p3 + p4)(p4 + p5)p6
是以目标是以最小開銷滿足f。不過，單邊覆寫的問題是，它不能捕捉所有指令選擇所必須的限制。大多數模式假定輸入具有某個類型或位于一個特定的資料位置。在文法裡，這通過非終結符來表示。使用相同的例子，讓我們假設節點n1可以被多個單節點模式p1，pꞌ1，及pꞌꞌ1覆寫。讓我們進一步假設模式p3，如果選中，要求節點n1必須被模式p1覆寫，且僅為該模式覆寫。這樣的限制，對指令選擇來說是常見的，不能被表示為一個單邊覆寫問題的部分。這個缺點通過雙邊覆寫來解決。不像單邊覆寫，雙邊覆寫允許析取包含非互補及互補的字面（即 )。現在我們剛讨論的限制可以被表達為 + p1，即如果我們選擇p3，那麼我們必須也選擇p1，以使該子句為真。是以這樣的子句被稱為暗示子句（implication clauses），因為它等同于p3 ⇒ p1。
通過使用雙邊覆寫解決內建電路合成（VLSI synthesis）的DAG覆寫，Rudell【197】[1]引領了雙邊覆寫的應用。它也被Servít與Yi【206】應用來解決或多或少類似的技術變換（technology mapping）問題。
這個做法後來被Liao等【163，164】修改來處理指令選擇。在他們分别發表在1995與1998年的論文裡，Liao等描述了目标是一個寄存器的機器并優化代碼大小的方法。為了控制複雜度，首先通過忽略資料傳輸及寄存器濺出開銷來解決模式選擇問題。在選擇了複雜模式後，被覆寫節點縮合為單個節點，建構第二個雙邊覆寫問題以最小化資料傳輸的開銷。雖然這兩個問題可以被同時解決，Liao等選擇不這樣做，因為需要的子句數目會變得極大。
最近，Cong等【53】也把雙邊覆寫應用于指令選擇，作為可配置處理器架構應用程式特定指令生成的一部分。不過，作者僅利用了之前的研究，而沒有貢獻将進一步推進指令選擇的新知識。
雖然上面讨論的做法将自身局限于DAG，模式選擇的雙邊覆寫思想可以擴充到任意圖形模式。這，連同存在許多精确及近似解決雙邊覆寫問題的研究這個事實，使得它成為未來指令選擇研究中一個有前途的候選。
1.2. 基于PBQP的做法
在2003年，Eckstein等【73】開發了第一個直接在SSA圖上工作的技術。SSA代表靜态、單指派（static, single assignment），是一個程式表示形式，其中每個變量或臨時變量僅定義一次。效果就是每個變量的生命周期是連續的，這簡化了許多優化過程。是以，基于SSA的IR為許多現代編譯器所使用，包括LLVM與gcc。關于SSA的更多資訊，建議讀者參考編譯器教材【8】或【56】。
Eckstein等認識到在專用的DSP上執行定點算術運算的情形下，将指令選擇限定在基本塊會導緻次優的代碼。例如，在圖5.3（a）中，我們看到一小段定點值乘法的代碼。對于定點乘法，一個公共的乘法特性是，結果向左移一位。是以，為了有效地利用這樣的乘法單元，在行4上的變量s中的結果在循環裡必須維持左偏差，僅在函數傳回前移回正常的模式。這意味着s的值在函數的不同點必須是不同的形式。不過，在限制在基本塊的指令選擇器中，這樣的資訊很難傳播，因為s的定義與使用發生在不同的樹中（參考圖5.3的（b））。
[1]基于來自【53,163,164】的第二手資料。
圖5.3：一個将使全局指令選擇受益的例子（來自【73】）
相比之下，全局指令選擇器能夠與模式選擇合作做出這些決定。首先，輸入程式被重寫為SSA形式，從中導出對應的SSA圖。圖5.4顯示目前這個例子的這些資料結構。因為SSA變量僅可以在一個點上定義，使用ɸ函數來定義循環變量以繞開這個限制。另外，因為SSA圖不能包含控制流資訊，代碼流出必須把輸入程式作為額外輸入，以推斷如何安排機器指令。
假定模式被表示為一個線性文法（參考20頁的描述）。所有正常的文法可以容易地重寫為線性形式的文法。對于SSA圖中的每個節點ni，我們定義一個布爾向量xi，長度等于比對該節點的基本規則數。在這裡，比對僅意味着一個基本規則的操作符比對這個節點。它不一定意味着對子節點存在一個有效的規則推理，使得父規則可以被實際選中。相反，這将被我們很快會讨論的鍊開銷來接管。是以我們可以認為這稍微把比對問題放松了一點，然後将有效的比對推論為部分模式選擇問題。進一步假定适用的基本規則的權重開銷由等長的另一個向量ci給出。權重通常是估計的，節點操作的相對執行頻率。給予循環中的低開銷指令更高優先級是需要的，因為它們對性能有更大的影響。使用這些定義，SSA圖被變換為一個分區布爾二次問題（partitioned Boolean quadratic problem，PBQP；也是由Scholz與Eckstein描述【203】），這被定義為查找對xi的指派，使得
是最小的，其中n是SSA圖中的節點數。解也被限制在那些在每個向量xi（即xi⋅1T = 1）隻有一個1的解。PBQP是二次分派問題（the quadratic assignmentproblem，QAP）的一個擴充，它是一個基本的組合優化問題。QAP與PBQP都顯然是NP完全問題，Eckstein等開發了自己的啟發式解答，這也在論文中描述了。
圖5.4：圖5.3的SSA形式（來自【73】）
顯然，這個目标函數包含兩部分：積累的鍊開銷（這是第一個項），及積累的基本開銷（這是第二個項）。基本開銷是顯而易見的，将不再進一步讨論。鍊開銷是通過鍊規則從一個基本規則遷移到另一個基本規則的開銷。這個開銷由開銷矩陣Cij給出，它代表在SSA圖中從節點j遷移到節點i的鍊開銷。假定SSA圖的邊必須排序，節點j是節點i的第m個子節點。那麼，這個矩陣的元素ckl給出了使用規則l的非終結符作為規則k的第m個參數所必須的鍊規則的最小開銷。如果非終結符是相同的，這個開銷是0。如果不存在這樣的鍊規則，開銷值則設為∞，禁止這樣規則組合的選擇。通過為所有的鍊規則計算傳遞閉包來計算鍊開銷，可以使用Floyd-Warshall算法【92】（雖然也存在其他算法）。後來Schäfer與Scholz【201】發現一個如何最優地應用這些鍊規則的方法。
精明的讀者可能注意到這個規劃假定SSA圖不包含重邊（multi-edges）。這阻止了比如：y = x + x的表達式直接模組化。幸運的是，重邊可以通過引入新的臨時變量，并通過值拷貝連接配接它們來删除。即
Eckstein等在標明的問題上測試了他們的實作。結果顯示，對比傳統的樹模式比對程式，這個做法提升了代碼品質40–60%（對于一個問題最多到90%）。PBQP求解器對幾乎所有測試用例産生了最優結果。不過，這個方法局限于樹模式，這阻礙了對許多複雜機器指令的利用。
這個局限後來被Ebner等【72】去除。首先文法被擴充為對給定的模式允許規則元組（tuples of rules），即一條開銷為2的除法-求模指令可以被表示為下面的複雜模式：
⟨lo → div(x : reg1,y : reg2), hi → mod(x, y)⟩
[2]{emit divmod r(reg1),r(reg2)}
x和y是允許div及mod操作的規則表示共享相同輸入的索引。自此之後，從屬于複雜模式的基本規則被稱為代理規則（proxy rules）。那麼PBQP問題被修改為包容複雜模式的選擇。本質上，這必須引入新的表示一個複雜模式是否被使用的變量，連同強制一個選中作為複雜模式部分的所有代理規則也被選中的限制。我們還需要防止選中導緻循環依賴的複雜模式的限制。讓我們進入細節。
首先，從比對節點i的複雜模式推導的代理規則擴充節點i的向量xi。如果來自不同複雜模式的兩個或更多代理規則是相同的， 向量的長度仍然僅增長1個元素。
其次，為獨立節點的每個組合建立一個複雜模式執行個體，其中比對的代理規可以合并為該複雜規則。每個執行個體産生了一個決策向量xl，表示該執行個體l是否被選中。讓我們把所有的xi向量集合進一個變量類别X1，并把所有的決策向量xl集合進另一個變量類别X2。X1與X2之間的聯系是這樣的，如果xl是選中的集合，其中i是作為l部分的一個代理規則比對的節點，那麼xi中所有對應的代理規則必須也是選中的集合。這需要額外的開銷矩陣 ，其中對應下者之一進制素的值設定為0：
· xl将被設為沒有選中，或者
· xi将被設定為不與複雜模式執行個體l關聯的一個基本規則或代理規則。
其他所有值設為∞。不過，如果所有代理規則的開銷都是0，那麼允許這樣的解答，其中一個複雜模式l的所有代理規則被選中，但該複雜模式本身沒有。Ebner等通過對所有代理模式設定一個高的開銷M，并把所有複雜模式的開銷修改為cost(l) – |l|M，其中|l|是l中代理規則數，來解決這個問題。這抵消了選中的代理模式的人為開銷，将選中代理規則與複雜模式的總體開銷降低到cost(l)。
最後，如果兩個複雜模式執行個體u與v重疊或選中會導緻循環資料依賴，我們需要一個防止它們被同時選中的開銷矩陣 。這可以通過将對應違反這兩個條件情形的 元素的值設定為∞，其他設定為0來保證。
是以，如果我們将原來PBQP問題中的Cij開銷矩陣重命名為 ，新的目标函數變成
其中p是複雜模式執行個體的數目。以ARMv5作為目标處理器與LLVM 2.1比較，對于一組標明的問題，以執行時間衡量，PBQP解決方案平均改善了13%。在編譯時間上總體的影響可以忽略不計。
另一個将第一個PBQP實作擴充為一般圖形模式的技術由Buchwald與Zwinkau【35】展示。Buchwald與Zwinkau将指令選擇作為一個形式化的圖形轉換問題來着手，其中許多之前的工作業已存在，機器指令被表示為重寫規則，而不是文法規則。除了擴充模式的支援，形式化的基礎可以驗證得到的指令選擇器可以處理所有可接受的輸入。如果驗證失敗，可以自動推導必須的，缺失的重寫規則。在為SSA圖找到所有适用的重寫規則（這相當于比對模式）後[1]，形成一個對應的PBQP執行個體，并如前求解。Buchwald與Zwinkau還發現并處理了這些情景，因為資訊的傳播不足夠，Eckstein等的啟發式求解程式的實作可能不能找到一個解答。不過在論文裡，Buchwald與Zwinkau提到在重疊模式數量增加時，他們目前實作的伸縮性不好。
對比其他技術，依賴于PBQP的做法看起來在機器指令支援、代碼品質及運作時方面非常有希望。不過，因為基于PBQP的指令選擇器是相當新的發明，引用數及在工業級編譯器中的應用仍十分少。另外，尚不清楚它們是否能處理所有類型的機器指令，特别是那些有特别限制的DSP指令。
5.5. 其他基于圖的做法
Yu與Hu【245】展示了一個技術，對模式選擇，它依賴一個基于手段目的分析（means-end analysis）的遞歸、啟發式的搜尋方法[2]。據稱，這個做法強大到足以将整個函數作為輸入，但作者沒有進入細節。這裡提這篇論文隻是為了完整。
一個非傳統的技術由Visser提出【229】，他對代碼生成應用了模拟退火的理論【147】。雖然有趣，指令選擇問題不幸被簡化為IR節點與選中機器指令間的一一映射，因而在實踐中沒有什麼用。
5.6. 總結
在本章，我們考慮了若幹依賴圖覆寫的指令選擇技術。對比工作在樹或DAG上的代碼生成器，基于圖形覆寫的指令選擇器是最強大的，因為程式輸入及機器指令可以是任意圖形。這使包含整個函數，包括控制流，比對并選擇不能被樹或DAG模組化的更複雜機器指令的全局指令選擇器成為可能。
不過，因為子圖同構是一個NP完全問題，最優圖覆寫要求兩個NP完全問題，而不“隻是” DAG覆寫的一個。因為這惡化了本已巨大的挑戰，最有可能，我們将隻在可以承受用非常長的編譯時間換取最優或近似最優代碼品質的編譯器中看到這樣的做法（即在有極端高的性能、代碼大小或功耗要求的嵌入式系統裡）。
[1] 實際上，通過将ɸ節點分裂為兩個節點打破回環，SSA圖首先被轉換到一個DAG。
[2] 類似的思想之前由Newell與Ernst【178】應用于基于樹覆寫的指令選擇（參考第7頁）。