指令選擇
在電腦科學中，指令選擇（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]
參考文獻
[編輯]- ^
Blindell, Gabriel S. Hjort. Survey on Instruction Selection: An Extensive and Modern Literature Review (報告). 2013. ISBN 978-91-7501-898-0. arXiv:1306.4898
.
- ^ 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）.
- ^ 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.
- ^ 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）.
- ^ 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.
- ^ Lunell, H. Code Generator Writing Systems (Doctoral thesis). Linköping, Sweden: Linköping University. 1983.
- ^ Ammann, U.; Nori, K. V.; Jensen, K.; Nägeli, H. The PASCAL (P) Compiler Implementation Notes. Instituts für Informatik (Technical report). 1974.
- ^ 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.
- ^ 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.
- ^ 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.
