指令選擇

在計算機科學中，指令選擇（Instruction selection）是編譯過程中的其中一個環節，位於編譯器後端。其工作是將中層的中間語言（IR）轉換為底層的中間語言。對於一般的編譯器，這個階段會執行於指令調度和寄存器配置這兩個階段之前，因此該編譯環節產出的IR一般允許程序中存在無限個偽寄存器（也作臨時變量，Temporaries），並且窺孔優化依舊適用於該IR。忽略這些特性，該中間語言已經與目標的機器碼、字節碼或匯編語言非常相近。

例子

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

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

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

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

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

實現方案

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

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

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