6. 模拟
指令選擇器的最後一個分類是那些通過分析及比較一條指令在目标機器上的作用，決定選擇哪條指令。與輸入程式給定部分具有相同作用的一條指令是相容的，是以該部分可由這條指令來達成（參考圖6.1）。我們稱這些概念為模拟（simulation）。模拟與基于覆寫方法間的一個關鍵差別是，在輸入程式不能觀察到所有輸出模式（即模式不是确切比對輸入圖）時，後者通常不能利用具有多個輸出的模式。相反，基于模拟的做法能夠忽略這些不可見的影響。事實上，幾個這些模拟方法在内部應用覆寫技術以确定相容性。
圖6.1：加法指令的效果可以如何模拟，以在一個輸入程式上執行指令選擇的例子。
模拟的思想可以直接應用于彙程式設計式，即比較一個機器指令序列是否等效于單個複雜機器指令。如果單個指令的開銷比長序列的開銷小，那麼替換它将産生該程式的一個改進。這樣的優化程式，稱為窺孔優化器，首先被用作一個代碼生成後步驟（post-code generation step）以提高代碼指令，但我們将看到如何可以改造這個技術來執行指令選擇。
6.1. 窺孔優化
一個早期——但仍然在應用的——提升代碼品質的方法是在生成代碼中執行局部檢查，力圖改進低效的指令序列。這個早在1965年McKeeman就主張【171】的技術，稱為窺孔優化，因為在其分析的任何時間，該優化例程通常局限于程式一個很窄的視窗。最簡單的窺孔優化器在彙編代碼中檢查特定的線性指令序列，以更廉價的等價物來替換它們。是以這樣的優化器在代碼已經被流出後，但在連結器運作前執行。第一批實作，就像最早的指令選擇器，通常是手寫并為特定的目标架構特别設計。
在1979年Fraser【96】展示了這樣的優化例程減少重指向開銷的第一個做法（這也在Davidson與Fraser【62】在更長的一篇論文裡描述了）。不是把目标彙編指令編碼進優化器，Fraser開發了一個窺孔優化器，稱為PO，從一個符号化的機器描述提取這些知識。這個描述通過描述一條指令對機器寄存器的作用，定義了它的語義。Fraser稱這些作用為寄存器傳輸，是以每條指令具有一個相應的寄存器傳輸模式或寄存器傳輸清單（RTL）。在這篇報告裡我們将始終使用後者。例如，這個形式的3位址中間加法指令的RTL
add $r[d], $r[s], #imm
它還設定一個0符号Z，将是
rd ← rs+ imm; Z ← rs + imm = 0
為了處理跳轉指令，這個做法假定機器使用一個跳轉時會設定的程式計數器。它進一步假設寄存器不受程式外部事件的影響。
PO通過綜合鄰接指令對的效果，然後檢查是否存在單條可以導緻相同結果的指令（通過一系列字元串比較）來改進給定的彙程式設計式。如果找到了這樣一條指令，替換這個指令對。這個實作是簡單的。在輸入程式上進行一個第一次後向遍來确定每條指令的作用。這個遍向後忽略對程式行為沒有影響的結果（即一個條件标記的值是不可見的，如果沒有後續使用它的指令，或者它被其他指令改寫了）。後跟一個第二遍，它合并了兩條字母序相鄰指令的效果，并查找帶有相比對效果的單條指令。如果替換了，優化器後退以檢查新指令與其鄰居的組合。這樣多個單條指令可以通過級聯替換來合并，但這要求存在實作每個中間替換步驟效果的指令。
盡管先進，PO也有幾個局限。主要的缺點是它僅能處理兩條指令的組合，而且在輸入代碼中這些指令必須字母序相鄰。也不允許指令對越過标記邊界（即屬于不同的基本塊）。後來Davidson與Fraser【60】通過在資料流圖而不是直接在文本輸入上建構及操作，消除了字母序相鄰的限制。他們還把指令組合從對擴充到了三元組。
已經有許多技術專門緻力于改善窺孔優化，我們将僅簡單論及某些多年來做出的進步。Giegerich【109】開發了一個形式化的做法，消除了窄視窗的需求。Kessler【144】提出了一個方法，在編譯器建構時完成模拟，是以減少了編譯時間。後來Kessler将在【143】的做法擴充到長度為n的指令視窗，雖然是指數級開銷。Massalin【170】開發了實作在Superoptimizer的一個算法，它詳盡地組合了機器指令序列以找出實作了與給定彙程式設計式相同行為的最小程式。後來Granlund與Kenner【118】采納了Massalin的工作，從給定的彙程式設計式中消除跳轉。兩者都不保證确性，是以要求人工檢查任何要執行的優化。最近，Joshi等【134，135】提出了一個方法幫助自動化編寫特别的優化例程過程。不像之前的優化器，他們的算法通過使用SAT解決的自動定理證明，找出給定程式的最優實作。不過，這是一個指數級開銷。
6.2. 通過窺孔優化的指令選擇
在1984年，Davidson與Fraser【60】将窺孔優化的思想整合進執行指令選擇。該思想首先使用宏展開流出指令代碼，然後通過窺孔優化後續優化它。當時樹比對算法仍然在開發，這個做法使用了更為成熟的技術。現在這個做法被稱為Davidson-Fraser方法，顯示在圖6.2裡。
圖6.2：Davidson-Fraser指令選擇方法的概覽（來自【60】）
這個指令選擇器包含兩個部分：一個擴充器及一個組合器。擴充器的任務是使用寄存器傳遞實作中間形式的輸入程式。這個做法假定一個不變量，稱為機器不變量，即每個RTL必須可由至少一條機器指令實作。組合器的任務是将多個RTL組合為一個也可由某條機器指令實作的更大的RTL。這步通過我們前面讨論的窺孔優化來完成。因為代碼将由組合器改進，擴充器可由簡化為一個簡單的一對多映射器，将一個IR操作轉換為許多連續的RTL。例如，一個記憶體到記憶體的移動
$m[@a + 8] ← $m[@a + 12]
可以被擴充為以下的RTL，每個僅包含一個操作：
r1 ← 12
r2 ← @a + r1
r3 ← $m[t2]
r4 ← 8
r5 ← @a + r4
$m[t5] ← r3
這樣的映射器通常使用宏擴充來實作，一個我們之前就知道實作與重指位都很簡單的技術（參考第二章）。
Davidson與Fraser在他們的YC編譯器中實作了這個做法——它還在RTL層次執行公共子表達式消除（參考Davidson與Fraser【61】）——但他們不是第一個這樣做的。類似的，一開始流出低效的代碼，然後改進它的更早期的政策被Auslander與Hopkins【21】以及Harrison【123】采用。不過，Davidson與Fraser堅持在可重指向性及代碼品質間合适的平衡，使得他們的做法超過了之前的嘗試。這個技術随後的實作在由Appel等開發的Zephyr/VPO系統【14】，由Tanenbaum等開發的Amsterdam Compiler Kit（ACK）及gcc（在【146，214】中讨論）這個最著名應用中。
與在本報告中讨論的其他做法相比，Davidson-Fraser做法的優點是其可擴充的機器指令支援。例如，對比基于樹覆寫及DAG覆寫的做法，應用Davidson-Fraser技術的指令選擇器可以更容易地處理跳轉及多個輸出的機器指令。這是可能的，因為組合器可以分析任何指令組合，潛在地跨過基本塊邊界。不過為了适用，某些指令可能要求一個過分大的指令視窗。另外，為機器指令模組化的寄存器傳遞清單排除了基于循環的機器指令，因為沒有處理指令内循環的概念。是以，雖然窺孔優化器在理論上可用于非常複雜的機器指令，在實踐中這樣做的代價通常太高了。此外，不确定這些類型的指令選擇器是否能夠适用于産生最優代碼。
Dias及Ramsey采用了與Davidson-Fraser方法稍微不同的做法。在Davidson-Fraser的做法裡，機器不變量通過每個優化例程來強制實施。相反，Dias與Ramsey采用了一個檢查優化步驟是否違反該不變量的識别器（參考圖6.3）。如果違反，拒絕該優化，復原彙編代碼。這簡化了優化例程，因為它們不再需要擔心遵守這個不變量。在【66】Dias與Ramsey展示了如何自動地從一個以λ-RTL編寫的聲明性機器模式産生這個識别器。由Ramsey與Davidson【192】開發的λ-RTL是一個基于ML的進階、強類型、多态、純函數式寄存器轉移語言，它提高了編寫寄存器傳遞清單的抽象層次。它是一個稱為計算機系統描述語言（CSDL）架構的部分，這個架構是緻力于自動化生成有用編譯器工具的Zephyr/VPO系統的部分。通過将RTL從機器描述轉換為線性化樹模式生成這個識别器。是以檢查一個RTL是否滿足該機器不變量簡化為一個存在高效算法的樹模式比對問題（參考第三章）。雖然這将識别器局限于在一個文法尺寸上推理RTL，效率的需求阻止了更昂貴的文法分析（記得對于每個要執行的優化步驟都需要查詢識别器）。
圖6.3：Dias與Ramsey對Davidson-Fraser方法改編的概覽（來自【66】）
後來Dias與Ramsey【65，193】開發了一個設計，減少了新目标機器，比如X86與PowerPC，甚至每個新架構族，比如基于寄存器及基于棧的機器，手動重指向的工作量。這個思想在于一組預定義的，特定于一個特定目标架構族的覆瓦（tiles）。一個覆瓦代表一個屬于該架構族任何機器上必須的簡單操作。例如，基于棧的機器要求push與pop操作的覆瓦，它們在具有寄存器的機器上不是必須的。現在，不是在輸入程式中将每個IR節點展開一系列RTL，擴充器将其擴充為一系列的覆瓦。因為覆瓦集對同一個族的每個機器都是相同的，實作的正确性僅需要被證明一次。在他們的工作中，Dias與Ramsey使用一個了貪婪的（maximum-munch）樹覆寫方法（參考第三章）來實作擴充器。假定合并器可以很好地改進流出代碼，指令選擇問題被歸約為選擇合适的機器指令來實作每個覆瓦。幸運地，Dias與Ramsey發現這個過程可以被自動化。通過使用λ-RTL描述覆瓦集機器指令，Dias與Ramsey開發了一個技術，其中機器指令的RTL被合并，使得效果等同于一個覆瓦的RTL。直覺是維護一個RTL池，然後使用順序和代數法則疊代地增長它，直到實作所有的覆瓦，或到達某個終止條件。後者是必須的，因為Dias與Ramsey證明查找一個覆瓦的實作是不可判定的（即沒有算法可以保證對所有可能的覆瓦能終止且找到一個實作）。
Dias與Ramsey方法比之Davidson與Fraser方法——及其他許多方法的主要優點，就此而言，是基于λ-RTL的機器描述比例如gcc的要更短、更簡單。此外，聲明性的描述更精确、明白，使得自動驗證指令說明成為可能（參考Fernández與Ramsey【89】以及Bailey與Davidson【22】）。不過，因為Dias與Ramsey的工作在于促進可重指向性，它并不必然提高代碼指令。此外，λ-RTL也不能用于一條機器指令内循環的模組化。
6.3. 其他基于模拟的做法
在他們的調查論文裡Ganapathi等【108】讨論了一個稱為UGEN的代碼生成器，它跟蹤每個IR節點在一個虛拟U代碼機器【185】上的改變。使用預定義的綱要（schemata），代碼生成器流出在目标機器上具有相同效果的代碼。是以重指向的努力被隔離為重寫綱要。不幸，UGEN沒有更多的資訊了，因為該論文缺少對這項工作的引用，并且在相關的文獻中也沒有被援引。
Fraser與Wendt【95】開發了一個方法，其中指令選擇器在兩步裡生成。在第一步，指令選擇器包含一系列switch語句以及實作一個簡單宏展開器的goto語句。宏展開器一開始僅将輸入DAG中的每個節點替換為單條機器指令。接着在一個仔細選擇的訓練集上執行它。同宏展開器合作，針對已發現的，可以在生成代碼上執行的優化機會，一個可重指向窺孔優化器收集其追蹤資訊及統計資料。這通過内嵌在指令選擇器中的函數調用來實作。基于這些結果，指令選擇器被增強為帶有條件語句以及額外的goto語句，這些語句實際上包含了選中的優化，是以消除了一個獨立窺孔優化器的需要。另外，因為僅實作了被認為有用的優化，代碼指令以最小的開銷得到改善。後來Wendt【235】通過提供一個允許IR操作及表示目标機器指令為RTL的規範，改進了這個方法。這個系統可以自動地推導如何将每個IR映射為機器代碼，一個之前的方法必須用手工實作的任務。這還演變為一個用于編寫這樣代碼生成器的緊湊語言（參考Fraser【94】）。
Hoover與Zadeck【131】開發了一個稱為TOAST（定制優化與語義翻譯，Tailored Optimisation and Semantic Translation）的系統，嘗試從一個給定的聲明性機器描述，自動地生成整個編譯器架構。至于指令選擇他們應用了一個算法，對于輸入中每個IR節點，遞歸地枚舉機器指令的所有組合，其集合效果等同于那個節點的作用。如果由選中機器指令實作的操作覆寫了由該IR節點生成的RTL圖，效果是相同的。通過檢查剩下未覆寫的節點是否仍然可覆寫，應用一個啟發式來限制查找空間。
6.4. 總結
在本章我們讨論了依賴于某種形式模拟的方法。在這樣的做法中，通常使用精确捕捉了指令效果的寄存器傳遞清單（RTL）來描述機器指令。通過流出總體效果與輸入IR效果相同的指令來執行指令選擇。為了簡化這個任務，首先以簡捷、缺乏效率的方式完成代碼流出，随後使用窺孔優化（這通常被稱為Davidson-Fraser方法）來改進代碼。窺孔優化器合并、比較，并使用單一等價對象替換多态指令，是以比基于樹或DAG覆寫的指令選擇器有更強的處理複雜指令能力。這是因為沒有限制窺孔優化器将機器指令模組化為限制圖形。另一個結果是它看起來還使得基于模拟的指令選擇器更容易重指向。不過，這樣優化器的效率受該優化器一次可以分析的指令樹的限制。此外，在目前基于RTL的做法中，用于機器指令模組化的寄存器傳遞清單不能捕捉基于循環的機器指令的特性。
這些做法的另一個重要的缺點是沒有嘗試去生成最優代碼。這應該要求，不清楚如何及它們是否可以擴充來實作這樣一個目标。另外，基于Davidson-Fraser方法的代碼品質關鍵依賴于窺孔優化器的效率，是以使得這些方法不可能用于高度受限的目标環境，比如DSP及嵌入式系統。
7. 結論
在本報告中我們考察并評估了所有現存、可以找到的關于指令選擇的文獻。該工作被分為5個部分——宏展開，樹覆寫，DAG覆寫，圖覆寫，以及模拟——它們都具有各自的優缺點。在附錄C有一張圖顯示看每個類别的研究如何随時間進展的。我們已經看到這個領域如何從專有的、手寫的一體程式開始，逐漸地在某種程度上，為更形式化的技術所替代。不僅最新的指令選擇器産生更好的代碼品質并擴充了對機器指令的支援，而且它們還改善了編譯器的可重指向性，因為指令選擇器的一大部分可以從一個聲明性的機器描述自動生成。不過，這些新方法增強的能力和效能是以增加複雜性換來的。例如，随着輸入表示從樹轉換到DAG，指令選擇從一個可以線上性時間最優解決的任務變為一個NP完全問題。因為這本質上是一個困難的問題，大多數方法應用啟發式來控制複雜度——許多以線性時間運作，并據報道通常生成近似最優的品質。
盡管這些巨大的進步，最先進的方法仍然具有幾個重大的缺陷。最顯著的缺點是，就我所知，沒有一個能模組化包含内部跳轉或循環的機器指令。這通常包括實作了算術操作的指令，這些操作之前通過編譯器固有函數（compiler intrinsics）及調用直接以彙編實作的庫函數來處理。雖然這使得指令選擇器部分地擴充了其對機器指令的支援，但這方法遠不算理想；以新固有函數擴充編譯器要求大量的人力；而且對每個目标機器都需要重寫庫函數。是以許多機器指令仍然沒有完全支援，而是要求編譯器開發者實作定制的例程以輔助指令選擇器。另外，基于啟發式的展開選擇器通常依賴于目标機器的假設，使得它非常難重指向，以及為複雜的架構，比如DSP與嵌入式系統，生成高效代碼。
另一個一再出現的限制是指令選擇通常局限在基本塊。考慮整個函數的方法——因而執行全局指令選擇——開始出現，但這些通常受其他方面的限制，比如機器指令的支援。
最後，為了實作全局最優代碼生成，必須同時考慮代碼生成的所有三個方面。換而言之，最優指令選擇如果孤立完成，本質上是徒勞的。例如，不考慮排程，有效利用條件代碼（也稱之為狀态标記）是不可能的，因為必須确定這些标記沒有過早地被其他指令改寫。這同樣适用于能并行執行多條指令的VLIW架構。另一個情形是重新實作（rematerialisation），其中選中的指令被允許重合，因而形成一種重複形式。在儲存一個值于後面使用比重新計算它開銷更大的情形下，這是有利的。不過，僅當減少的寄存器壓力确實幫助了寄存器配置設定器，這才是有用的。在帶有多個寄存器類别，對通路每個寄存器類别要求特殊指令集的目标機器裡，指令選擇與寄存器配置設定間的聯系變得更為緊密。話雖如此，大多數現代的方法僅孤立地考慮指令選擇，是以很難完整及有效地整合指令排程與寄存器配置設定。
盡管有這些問題，幾個基于源自運籌學領域研究技術的方法顯示出很大的前景。追求最優，這些想法通常也能處理更複雜的機器指令，以及可以擴充到考慮整個函數。特别的，新興的研究針對基于限制規劃的方法（參考Bashford與Leupers【24】，Kuchcinski【155】，及Castañeda Lozano等【39】）顯示代碼生成的各個方面可以被整合入一個單一限制模型，因為目标機器的任意限制可以很容易地被表示為額外的限制，以重指向性而言，它極端彈性及靈活的。不過，目前的實作通常比啟發式的對手慢上一個數量級，這意味着它仍然是一個不成熟的技術，需要進一步的研究。
最後，雖然這個領域自1960年代肇始，已經有了長足的進步，指令選擇仍然是——盡管有共識——一個難以了解的問題。另外，目前嵌入式系統、DSP與應用特定加速處理器更緊密結合的潮流意味着目标機器隻會變得更複雜，而不是更簡單。是以，以這個觀點看來，指令選擇比之以前更需要增加了解。