什么是指令选择

指令选择（Instrcution Selection）作为一个独立概念于上个世纪六十年代被提出，它是编译器将平台无关的中间语言（Intermediate Representation）转换为平台相关的机器指令（Machine Instruction）的过程。其目标是尽量高效的选择最优的可用的机器指令。

在传统三段式编译器架构中，指令选择为编译器后端的三大主要优化问题之一，另外两大问题为指令调度与寄存器分配，指令选择早于其他两个模块。

指令选择方法

以下主要介绍指令选择算法的演进。

1. 宏展开(Macro Expansion)

宏展开也被叫做模板匹配（Template Matching），即对于每一条IR或AST结构，都有一条或多条机器指令与其相对应，编译器直接使用预制好的指令或指令模板替换对应的每一条输入IR即可。这种方式简单粗暴，实现简单，易于理解。但缺点也显而易见，这种操作只支持1:1或1:N的情况，无法处理N:1或N:M的场景，即多条IR或AST对应一条或者多条机器指令的场景，致使指令结果不优。

因为产生的指令非常低效，作为指令选择的后续操作，会产生一些指令合并或用更高效更简洁的指令替换原先指令的优化，即我们现在比较熟知的所谓窥孔优化（peephole optimization)。这类优化目前依旧存在于一些现代编译器中。

2. 树覆盖（Tree Covering)

树覆盖解决了宏展开的不支持N:1或N:M的场景，它主要是将IR或AST的前端语法与后端的机器指令都转换为树结构（如下图所示）。这样就把指令选择问题转换为机器指令树覆盖全IR语法树的问题。我们可以将其想象为铺地板的过程，每一个指令数就是各种大小不一的瓷砖（tile），指令选择就比喻成瓷砖铺满屋子的过程，在局部，我们可以选择尽量大的瓷砖优先铺装。在以下的例子中，左侧的add+mul的左子树，如果架构提供FMA（乘加）指令，我们即可直接选择到FMA。

3. DAG覆盖（DAG Covering）

基于树覆盖的不足，产生了DAG 覆盖。DAG（directed acyclic graph）即为有向无环图，即把树覆盖中的数据结构转换为DAG，其主要思路与树覆盖类似，都是采用pattern覆盖的原理，但是DAG覆盖可以解决树无法表示多个输出边的情况。有些指令譬如divmod会有两个输出，DAG覆盖可以表达这种结构。在大多数现代编译器的实现中，基本都采用了这种模式。

指令选择在LLVM中的实现

在LLVM框架中，目前主要有两种指令选择框架：SelectionDAG与GlobalISel，前者为目前正在使用的方案，后者旨在替换前者，本节我们主要介绍SelectionDAG的主要实现原理。

1. SelectionDAG介绍

SelectionDAG为LLVM构造的一种基于DAG数据结构的中间表达，代表一个basic block，输入为LLVMIR，输出为MachineDAG，基本组成为SDNode，代表一条包含操作码与操作数的指令。

我们以下图作为示例介绍SelectionDAG中的主要元素以及相互关系。该图等价于如下的C程序：

unsigned int MUL（unsigned long long int x， unsigned int y）

{

return x*y；

}

（1）三行节点：操作数（寄存器、立即数、索引、数据类型等）。

（2）四行节点：指令（第一行为输入参数，第二行为intrinsic或操作码，第三行为输出参数，第四行为返回类型）。

（3）黑色实现：表示数据依赖，其箭头指向数据输入来源。

（4）蓝色虚线：表示chain dependence，即本节点在后续不能被调度到所指节点之前。

（5）红色实现：表示glue，相比于蓝色虚线，约束更强，即被glue的两个节点不能被分开。

2. SelectionDAG处理步骤

打开SelectionDAG的处理代码，主要分为4个部分，即Lowering、Combine、Legalize、Select。其核心类为SelectionDAGISel，其两个主要的实例化属性CurDAG代表了由SDNode构成的DAG，SDB则是用来将LLVMIR构造为SelectionDAG Node的构造器，关键接口为visit。SelectionDAGISel还提供了目标target处理指令选择的关键接口Select。SelectionDAG类提供了目标target的Lowering、Combine、Legalize三个接口。

（1）Lowering

Lowering的主要工作就是将LLVMIR转换为DAG数据结构。如UML示意图所示，SelectionDAGBuilder类会依据每一条IR中的操作码，调用SelectionDAGBuilder中的visit接口，将每个IR节点转换为DAG节点。我们以Add为例，visit接口会产生visitAdd函数，传入add的两个操作数，并调用getNode接口生成SDNode。

有两种情况比较特殊，需要单独处理。第一种为函数调用，因为call涉及到架构强依赖，通用的Lowering无法达到直接生成通用SDNode的目的，故只能用target相关的TargetLoweringInfo单独处理。第二种为PHI，因为PHI节点本身是为SSA创建的虚拟节点，对于DAG没有意义，故无需做Lowering。

（2）Combine

DAGCombine即为对一些可以组合或替换的SDNode做合并操作，主要是由DAGCombine类中的combine接口发起，除了LLVM自带的一些常规Combine操作外，用户也可以通过TargetLowering中performDAGCombine接口去处理target相关的Combine操作。

（3）Legalize

SelectionDAG还提供了对操作数与操作码的Legalize操作。主要由SelectionDAGLegalize与DAGTypeLegalizer中的接口实现，同样通过TargetLowering传递到各个子target做架构相关的Legalize，譬如当前架构仅支持32位add操作，但是前端生成了64位add的IR，在Legalize阶段，编译器即会对64位add操作使用一系列的32位操作码来实现，相对应的64位数据类型也会被转换为32位数据类型计算。我们有以下几种Legalize方式：

1）Legalize：该操作码或操作数架构天然支持，无需任何处理。

2）Promote：告知LLVM，操作数应该被提升，例如架构不支持16位但支持32位操作数，在使用16位操作数时，可以考虑Promote到32位。

3）Expand：告知LLVM，该操作架构不支持，请尝试将其展开成其他操作或者使用libcall调用。例如将64位操作Expand成32位操作的组合。

4）LibCall：告知LLVM，该操作架构不支持，需要调用libc接口，譬如软浮点计算，即所有的浮点计算都使用softfloat库来实现而并非硬件指令。

5）Custom：留给用户的hook操作，即用户自己实现对该操作的实现，相关接口为LowerOperation。

（4）Select

以上操作完成后，即开始做指令选择，即将ISD SDNode DAG转换为Machine SDNode的过程。该步骤主要在SelectionDAGAISel类中的CodeGenAndEmitDAG接口中实现，Select操作被定义为虚函数，对应于各个target的具体实现。在一般的target实现中，Select一般由两部分组成：手动编码匹配与自动生成匹配。手动编码匹配即人工通过接口代码实现一些难以通过自动生成匹配生成最佳指令的情况，在手动匹配处理完以后，会调用SelectCode进行自动pattern match匹配。

Matcher Table是LLVM tablegen生成的一个包含所有target指令pattern的集合。它是一个非常庞大的静态数组，以tree pattern的形式来描述，如出现多个输出的情况，LLVM会将其退化（undag）为树表达。

如下图所示为target生成的具体例子（详见build_path/lib/target/targetName/xxxGenDAGISel.inc），其中每行最前边的数字注释代表每行首元素在数组中的下标，方便开发者查找。每一行均以OPC_开头，表示下一个跳转的状态，缩进长度指示了该状态的层级。表中有一些特殊编码，例如第一行中 124|128,62/*8060*/, 是采用了变长编码，其计算方式为 124 + 62 (0x111110)<< 7 = 8060，正好为注释中的值（详见SelectionDAGISel.cpp中的GetVBR()），表示下一个同级的OPC所在的位置。

1）OPC_SwitchOpcode：指示匹配的opcode类别

2）OPC_Scope：指示匹配的operand条件分类

3）OPC_Record*：记录当前匹配成功的节点

4）OPC_Move*：记录当前匹配的operand

5）OPC_Check*：判断是否满足条件

6）OPC_Emit*：匹配成功，创建MachineNode替换SDNode

7）OPC_Morph：类似于OPC_Emit*，但可能有其他引用，不一定会被删除替换

总结

本文简单介绍了指令选择的基本概念，常见的指令选择的pattern方式，以及稍微展开对LLVM架构中基于SelectionDAG的指令选择实现做了初步分析。从Lowering、Combine、Legalize、Select四个方面介绍了指令选择中开发者可以处理的常规操作，最后再着重讲了Matcher Table的主要结构，希望读者对于LLVM的pattern matching方式有了初步的了解。

参考

1. https://www.cnblogs.com/Five100Miles/p/12822190.html

2. https://www.cnblogs.com/wujianming-110117/p/17260223.html

3. https://arxiv.org/ftp/arxiv/papers/1306/1306.4898.pdf