電腦科學中,指令選擇(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架構並不存在 R0R1 這兩個暫存器。經過暫存器組態後,這兩個偽暫存器會被替換成 eax 等實際存在的暫存器。

實現方案

編輯

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

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

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

參考文獻

編輯
  1. ^ Blindell, Gabriel S. Hjort. Survey on Instruction Selection: An Extensive and Modern Literature Review (報告). 2013. ISBN 978-91-7501-898-0. arXiv:1306.4898 . 
  2. ^ Blindell, Gabriel S. Hjort. Instruction Selection: Principles, Methods, & Applications. Springer. 2016 [2023-06-09]. ISBN 978-3-319-34017-3. S2CID 13390131. doi:10.1007/978-3-319-34019-7. (原始內容存檔於2021-05-18). 
  3. ^ Brown, P. A Survey of Macro Processors. Annual Review in Automatic Programming. 1969, 6 (2): 37–88. ISSN 0066-4138. doi:10.1016/0066-4138(69)90001-9. 
  4. ^ Cattell, R. G. G. A Survey and Critique of Some Models of Code Generation (PDF). School of Computer Science, Carnegie Mellon University (Technical report). 1979. (原始內容存檔 (PDF)於May 23, 2019). 
  5. ^ Ganapathi, M.; Fischer, C. N.; Hennessy, J. L. Retargetable Compiler Code Generation. Computing Surveys. 1982, 14 (4): 573–592. ISSN 0360-0300. S2CID 2361347. doi:10.1145/356893.356897. 
  6. ^ Lunell, H. Code Generator Writing Systems (Doctoral thesis). Linköping, Sweden: Linköping University. 1983. 
  7. ^ Ammann, U.; Nori, K. V.; Jensen, K.; Nägeli, H. The PASCAL (P) Compiler Implementation Notes. Instituts für Informatik (Technical report). 1974. 
  8. ^ Orgass, R. J.; Waite, W. M. A Base for a Mobile Programming System. Communications of the ACM. 1969, 12 (9): 507–510. S2CID 8164996. doi:10.1145/363219.363226. 
  9. ^ Davidson, J. W.; Fraser, C. W. Code Selection Through Object Code Optimization. ACM Transactions on Programming Languages and Systems. 1984, 6 (4): 505–526. CiteSeerX 10.1.1.76.3796 . ISSN 0164-0925. S2CID 10315537. doi:10.1145/1780.1783. 
  10. ^ Aho, A. V.; Ganapathi, M.; Tjiang, S. W. K. Code Generation Using Tree Matching and Dynamic Programming. ACM Transactions on Programming Languages and Systems. 1989, 11 (4): 491–516. CiteSeerX 10.1.1.456.9102 . S2CID 1165995. doi:10.1145/69558.75700.