指令選擇

在電腦科學中，指令選擇（Instruction selection）是編譯過程中的其中一個環節，位於編譯器後端。其工作是將中層的中間語言（IR）轉換為底層的中間語言。對於一般的編譯器，這個階段會執行於指令排程和暫存器組態這兩個階段之前，因此該編譯環節產出的IR一般允許程式中存在無限個偽暫存器（也作臨時變數，Temporaries），並且窺孔最佳化依舊適用於該IR。忽略這些特性，該中間語言已經與目標的機器碼、位元組碼或組合語言非常相近。 ^{[1] [2]}

例子

假設目標機器碼為x86指令集，則對於以下中層中間語言：

t1 = a
t2 = b
t3 = add t1, t2

經過指令選擇以後，會產生以下底層中間語言：

MOV R0, a
MOV R1, b
ADD R1, R0

注意x86架構並不存在 R0 與 R1 這兩個暫存器。經過暫存器組態後，這兩個偽暫存器會被替換成 eax 等實際存在的暫存器。

實現方案

最簡單的指令選擇實現方案是宏擴充（Macro expansion）方案^[3]，亦稱作解釋性代碼生成^[4]。使用宏擴充的指令選擇器會在中階 IR 上進行模板匹配的操作，並且在匹配成功時執行相應的宏，此時該宏以匹配到的中層 IR 部分作為輸入，輸出對應的目標底層 IR。 宏擴充可以直接在文字形式的中層 IR 上完成，也可以將中層 IR 首先轉換為圖形，然後對其進行深度優先遍歷。^[5][6][7][8]

除非目標機器的指令集非常簡單，否則宏擴充演算法生成出來的代碼一般會存在效率低下的問題。為了緩解這個問題，應用此方案的編譯器通常將其與窺孔最佳化相結合，以將簡單指令的組合替換為更複雜的等效單一指令，從而提高效能並減少代碼大小。這個方法被稱作 Davidson-Fraser 方法，目前在 GCC 中得到應用。^[9]

另外一種實現方案是圖形覆蓋（Covering the graph）方案。^[10]