热门问题
时间线
聊天
视角
指令選擇
来自维基百科,自由的百科全书
Remove ads
在電腦科學中,指令選擇(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]
Remove ads
參考文獻
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads