指令选择

在计算机科学中，指令选择（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]

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.