热门问题
时间线
聊天
视角

指令选择

来自维基百科,自由的百科全书

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架构并不存在 R0R1 这两个寄存器。经过寄存器配置后,这两个伪寄存器会被替换成 eax 等实际存在的寄存器。

实现方案

最简单的指令选择实现方案是宏扩展(Macro expansion)方案[3],亦称作解释性代码生成[4]。使用宏扩展的指令选择器会在中级 IR 上进行模板匹配的操作,并且在匹配成功时执行相应的宏,此时该宏以匹配到的中层 IR 部分作为输入,输出对应的目标底层 IR。 宏扩展可以直接在文本形式的中层 IR 上完成,也可以将中层 IR 首先转换为图形,然后对其进行深度优先遍历。[5][6][7][8]

除非目标机器的指令集非常简单,否则宏扩展算法生成出来的代码一般会存在效率低下的问题。为了缓解这个问题,应用此方案的编译器通常将其与窥孔优化相结合,以将简单指令的组合替换为更复杂的等效单一指令,从而提高性能并减少代码大小。这个方法被称作 Davidson-Fraser 方法,目前在 GCC 中得到应用。[9]

另外一种实现方案是图形覆盖(Covering the graph)方案。[10]

参考文献

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads