LLVM 之后端篇（6）：如何基于 Pattern 实现指令选择
Author: stormQ
Created: Friday, 13. May 2022 11:00PM
Last Modified: Sunday, 29. May 2022 09:51AM
本文基于release/13.x版本的 LLVM 源码，介绍了DAG-to-DAG指令选择的一种实现方式——Pattern Matching。包括如何描述SDNode类型约束，如何定义机器相关的SDNode，以及编写Pattern的方法和注意事项等。从而，能够通过Pattern实现大多数情况时的指令选择。
LLVM中，不同的目标后端是通过实现各自的<Target>DAGToDAGISel::Select()函数来进行指令选择的。Select()函数选择机器指令的方式包括两种：Pattern和自定义的 C++ 代码。其代码实现形如（位于llvm/lib/Target/<Target>/<Target>ISelDAGToDAG.cpp文件）：
void <Target>DAGToDAGISel::Select(SDNode *N) {
switch (N->getOpcode()) {
// custom C++ code
}
// pattern matching
SelectCode(N);
}
函数SelectCode()（位于<build_dir>/lib/Target/<Target>/<Target>GenDAGISel.inc文件）是TableGen根据.td文件中的Patterns自动生成的。需要注意地是，自定义的 C++ 代码必须位于调用SelectCode()函数地方的前面。这里因为，函数SelectCode()选择机器指令失败时会直接coredump。
抽象记录基类SDTypeConstraint及其派生类定义了SDNode所有的类型约束。其定义如下（位于llvm/include/llvm/Target/TargetSelectionDAG.td文件）：
class SDTypeConstraint<int opnum> {
int OperandNum = opnum;
}
抽象记录基类SDTypeConstraint中的字段OperandNum表示操作数的索引（从 0 开始）。需要注意地是， 这里的操作数包括SDNode定义的值和（通常意义上的）操作数。节点第一个定义的值（如果有的话）对应的OperandNum值为 0，依次类推。
抽象记录基类SDTypeConstraint的派生类可以分为如下 3 种：
（单个操作数）指定的类型约束。比如：SDTCisVT、SDTCVecEltisVT。
（单个操作数）固定的类型约束。比如：SDTCisPtrTy、SDTCisInt、SDTCisFP、SDTCisVec。
两个操作数之间的类型约束。比如：SDTCisSameAs、SDTCisVTSmallerThanOp、SDTCisOpSmallerThanOp、SDTCisEltOfVec、SDTCisSubVecOfVec、SDTCisSameNumEltsAs、SDTCisSameSizeAs。
类型约束SDTCisVT，表示索引为OpNum（由第 1 个参数指定）的操作数的类型必须为vt（由第 2 个参数指定）。其定义如下：
class SDTCisVT<int OpNum, ValueType vt> : SDTypeConstraint<OpNum> {
ValueType VT = vt;
}
参数vt的数据类型为抽象记录基类ValueType，可取值为ValueType的具象派生类。其定义如下（位于llvm/include/llvm/CodeGen/ValueTypes.td文件）：
class ValueType<int size, int value> {
string Namespace = "MVT";
int Size = size;
int Value = value;
}
字段Namespace，表示类型所在的命名空间。
字段Size，表示类型实际占用的空间大小（单位：bit）。比如：具象派生类OtherVT表示一种抽象类型，不占用任何空间，因此其Size字段的值为 0。
字段Value，表示类型的标识符。该值必须与枚举类型MVT::SimpleValueType（位于llvm/include/llvm/Support/MachineValueType.h文件）中所对应枚举成员的值保持一致。比如：具象派生类OtherVT的标识符值为 1，那么所对应枚举成员MVT::Other的枚举值也必须为 1。
类型约束SDTCVecEltisVT，表示索引为OpNum的操作数的类型是元素类型为vt的向量。其定义如下：
class SDTCVecEltisVT<int OpNum, ValueType vt> : SDTypeConstraint<OpNum> {
ValueType VT = vt;
}
需要注意地是， 参数vt的取值要么为整型标量（比如：i1、i128等），要么为浮点型标量（比如：bf16、ppcf128等）。
类型约束SDTCisPtrTy，表示索引为OpNum的操作数的类型是指针。其定义如下：
class SDTCisPtrTy<int OpNum> : SDTypeConstraint<OpNum>;
类型约束SDTCisInt，表示索引为OpNum的操作数的类型是整型（包括整型标量和整型向量）。其定义如下：
class SDTCisInt<int OpNum> : SDTypeConstraint<OpNum>;
类型约束SDTCisFP，表示索引为OpNum的操作数的类型是浮点型（包括浮点型标量和浮点型向量）。其定义如下：
class SDTCisFP<int OpNum> : SDTypeConstraint<OpNum>;
类型约束SDTCisVec，表示索引为OpNum的操作数的类型是向量。其定义如下：
class SDTCisVec<int OpNum> : SDTypeConstraint<OpNum>;
类型约束SDTCisSameAs，表示两个操作数（由参数OpNum和OtherOp指定）的类型相同。其定义如下：
class SDTCisSameAs<int OpNum, int OtherOp> : SDTypeConstraint<OpNum> {
int OtherOperandNum = OtherOp;
}
类型约束SDTCisVTSmallerThanOp，表示操作数（由OpNum指定）的类型所占用的空间小于另一个操作数（由OtherOp指定）的类型所占用的空间。其定义如下：
class SDTCisVTSmallerThanOp<int OpNum, int OtherOp> : SDTypeConstraint<OpNum> {
int OtherOperandNum = OtherOp;
}
需要注意地是， 类型约束SDTCisVTSmallerThanOp仅允许相似类型之间进行比较。包括如下 4 种情况：
两个操作数的类型都是整型标量。
两个操作数的类型都是整型向量。
两个操作数的类型都是浮点型标量。
两个操作数的类型都是浮点型向量。
示例：
def SDT_TEST : SDTypeProfile<1, 2, [
SDTCisVTSmallerThanOp<2, 1>
]>;
def TEST_SDNode : SDNode<"MyRISCVISD::TEST", SDT_TEST>;
def : Pat<(i32 (TEST_SDNode i32:$rs1, i16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v32i1 (TEST_SDNode v32i1:$rs1, v16i1:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(f16 (TEST_SDNode f32:$rs1, f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v2i16 (TEST_SDNode v2i16:$rs1, v1i16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v2f16 (TEST_SDNode v2f16:$rs1, v1f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
类型约束SDTCisOpSmallerThanOp，表示操作数（由SmallOp指定）的类型所占用的空间小于另一个操作数（由BigOp指定）的类型所占用的空间。其定义如下：
class SDTCisOpSmallerThanOp<int SmallOp, int BigOp> : SDTypeConstraint<SmallOp>{
int BigOperandNum = BigOp;
}
同样地，类型约束SDTCisOpSmallerThanOp也仅允许相似类型之间进行比较。包括如下 4 种情况：
两个操作数的类型都是整型标量。
两个操作数的类型都是整型向量。
两个操作数的类型都是浮点型标量。
两个操作数的类型都是浮点型向量。
需要注意地是， 类型约束SDTCisOpSmallerThanOp要求显式地指定两个操作数的类型，否则缺省情况下两个操作数的类型要么都是整型标量，要么都是整型向量。而类型约束SDTCisVTSmallerThanOp没有这一限制。
示例（缺省情况）：
def SDT_TEST : SDTypeProfile<1, 2, [
SDTCisOpSmallerThanOp<2, 1>
]>;
def TEST_SDNode : SDNode<"MyRISCVISD::TEST", SDT_TEST>;
def : Pat<(i32 (TEST_SDNode i32:$rs1, i16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v32i1 (TEST_SDNode v32i1:$rs1, v16i1:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v2i16 (TEST_SDNode v2i16:$rs1, v1i16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
// def : Pat<(f16 (TEST_SDNode f32:$rs1, f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>; // compile error
// def : Pat<(v2f16 (TEST_SDNode v2f16:$rs1, v1f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>; // compile error
对于两个操作数的类型都是相似浮点型的情况，类型约束SDTCisOpSmallerThanOp要求必须显式地指定两个操作数都是浮点型，并且都要先于类型约束SDTCisOpSmallerThanOp进行说明。
示例（正确地）：
def SDT_TEST : SDTypeProfile<1, 2, [
SDTCisFP<1>, SDTCisFP<2>, SDTCisOpSmallerThanOp<2, 1>
]>;
def TEST_SDNode : SDNode<"MyRISCVISD::TEST", SDT_TEST>;
def : Pat<(f16 (TEST_SDNode f32:$rs1, f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v2f16 (TEST_SDNode v2f16:$rs1, v1f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
示例（错误地）：
def SDT_TEST : SDTypeProfile<1, 2, [
SDTCisFP<1>, SDTCisOpSmallerThanOp<2, 1>, SDTCisFP<2>
]>;
def TEST_SDNode : SDNode<"MyRISCVISD::TEST", SDT_TEST>;
// def : Pat<(f16 (TEST_SDNode f32:$rs1, f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>; // compile error
// def : Pat<(v2f16 (TEST_SDNode v2f16:$rs1, v1f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>; // compile error
类型约束SDTCisEltOfVec，表示操作数（由OtherOp指定）的类型必须是向量，并且操作数（由ThisOp指定）的类型必须与该向量的元素类型相同。其定义如下：
class SDTCisEltOfVec<int ThisOp, int OtherOp>
: SDTypeConstraint<ThisOp> {
int OtherOpNum = OtherOp;
}
示例：
def SDT_TEST : SDTypeProfile<1, 2, [
SDTCisEltOfVec<2, 1>
]>;
def TEST_SDNode : SDNode<"MyRISCVISD::TEST", SDT_TEST>;
def : Pat<(v32i1 (TEST_SDNode v32i1:$rs1, i1:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v2i16 (TEST_SDNode v2i16:$rs1, i16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v2f16 (TEST_SDNode v2f16:$rs1, f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
类型约束SDTCisSubVecOfVec，表示两个操作数是元素类型相同的向量（包括整型向量和浮点型向量），并且前者（由ThisOp指定）中的元素数量少于后者（由OtherOp指定）。其定义如下：
class SDTCisSubVecOfVec<int ThisOp, int OtherOp>
: SDTypeConstraint<ThisOp> {
int OtherOpNum = OtherOp;
}
示例：
def SDT_TEST : SDTypeProfile<1, 2, [
SDTCisSubVecOfVec<2, 1>
]>;
def TEST_SDNode : SDNode<"MyRISCVISD::TEST", SDT_TEST>;
def : Pat<(v32i1 (TEST_SDNode v32i1:$rs1, v16i1:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v2i16 (TEST_SDNode v2i16:$rs1, v1i16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v2f16 (TEST_SDNode v2f16:$rs1, v1f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
类型约束SDTCisSameNumEltsAs，表示两个操作数要么都是标量（两个标量的类型可以相同，也可以不同），要么都是元素数量相同的向量（两个向量的元素类型可以相同，也可以不同）。其定义如下：
class SDTCisSameNumEltsAs<int OpNum, int OtherOp> : SDTypeConstraint<OpNum> {
int OtherOperandNum = OtherOp;
}
示例：
def SDT_TEST : SDTypeProfile<1, 2, [
SDTCisSameNumEltsAs<2, 1>
]>;
def TEST_SDNode : SDNode<"MyRISCVISD::TEST", SDT_TEST>;
def : Pat<(v32i1 (TEST_SDNode v2i16:$rs1, v2f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v32i1 (TEST_SDNode i32:$rs1, i32:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(f16 (TEST_SDNode f32:$rs1, f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(f16 (TEST_SDNode f32:$rs1, i32:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
类型约束SDTCisSameSizeAs，表示两个操作数的类型所占用的空间大小相等。其定义如下：
class SDTCisSameSizeAs<int OpNum, int OtherOp> : SDTypeConstraint<OpNum> {
int OtherOperandNum = OtherOp;
}
示例：
def SDT_TEST : SDTypeProfile<1, 2, [
SDTCisSameSizeAs<2, 1>
]>;
def TEST_SDNode : SDNode<"MyRISCVISD::TEST", SDT_TEST>;
def : Pat<(v32i1 (TEST_SDNode v2i16:$rs1, i32:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(v32i1 (TEST_SDNode i32:$rs1, f32:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
def : Pat<(f16 (TEST_SDNode f32:$rs1, v2f16:$rs2)), (ADD GPR:$rs1, GPR:$rs2)>;
LLVM中，tblgen会在编译期检查patterns中SDNode的类型约束是否满足。如果不满足，则编译失败。
抽象记录基类SDTypeProfile用于描述SDNode定义的值和操作数需要满足的类型约束。其定义如下（位于llvm/include/llvm/Target/TargetSelectionDAG.td文件）：
class SDTypeProfile<int numresults, int numoperands,
list<SDTypeConstraint> constraints> {
int NumResults = numresults;
int NumOperands = numoperands;
list<SDTypeConstraint> Constraints = constraints;
}
参数numresults，表示SDNode定义了多少个值。
参数numoperands，表示SDNode的操作数数量。特殊地，-1 表示操作数的数量不确定。
参数constraints，表示SDNode定义的值和操作数需要满足的类型约束。
比如：
def SDTIntBinOp : SDTypeProfile<1, 2, [ // add, and, or, xor, udiv, etc.
SDTCisSameAs<0, 1>, SDTCisSameAs<0, 2>, SDTCisInt<0>
]>;
上述代码定义了类型约束SDTIntBinOp。满足该约束的SDNode形如：节点定义了 1 个值，有 2 个操作数，并且三者的数据类型都是相同的整型或者整型向量。
抽象记录基类SDNodeProperty及其派生类定义了SDNode所有的属性。其定义如下（位于llvm/include/llvm/CodeGen/SDNodeProperties.td文件）：
class SDNodeProperty;
def SDNPCommutative : SDNodeProperty; // X op Y == Y op X
def SDNPAssociative : SDNodeProperty; // (X op Y) op Z == X op (Y op Z)
def SDNPHasChain : SDNodeProperty; // R/W chain operand and result
def SDNPOutGlue : SDNodeProperty; // Write a flag result
def SDNPInGlue : SDNodeProperty; // Read a flag operand
def SDNPOptInGlue : SDNodeProperty; // Optionally read a flag operand
def SDNPMayStore : SDNodeProperty; // May write to memory, sets 'mayStore'.
def SDNPMayLoad : SDNodeProperty; // May read memory, sets 'mayLoad'.
def SDNPSideEffect : SDNodeProperty; // Sets 'HasUnmodelledSideEffects'.
def SDNPMemOperand : SDNodeProperty; // Touches memory, has assoc MemOperand
def SDNPVariadic : SDNodeProperty; // Node has variable arguments.
def SDNPWantRoot : SDNodeProperty; // ComplexPattern gets the root of match
def SDNPWantParent : SDNodeProperty; // ComplexPattern gets the parent
关于这些属性的行为以及注意事项，待补充。
要定义特定于目标机器的节点，我们需要继承抽象记录基类SDNode。其定义如下（位于llvm/include/llvm/Target/TargetSelectionDAG.td文件）：
class SDNode<string opcode, SDTypeProfile typeprof,
list<SDNodeProperty> props = [], string sdclass = "SDNode">
: SDPatternOperator {
string Opcode = opcode;
string SDClass = sdclass;
let Properties = props;
SDTypeProfile TypeProfile = typeprof;
}
参数opcode，表示SDNode的操作码。
参数typeprof，表示SDNode的类型约束。
参数props，表示SDNode的属性列表。
参数sdclass，表示SDNode所对应的 C++ 类名。
step 1： 定义特定于目标机器的操作码
通常情况下，特定于目标机器的操作码定义在<Target>ISD::NodeType中（位于llvm/lib/Target/<Target>/<Target>ISelLowering.h文件）。
如果节点涉及内存操作，那么其操作码（这里为MyRISCVISD::TEST_MEM）的值应该大于等于ISD::FIRST_TARGET_MEMORY_OPCODE。比如：
namespace MyRISCVISD {
enum NodeType {
TEST_MEM = ISD::FIRST_TARGET_MEMORY_OPCODE,
};
} // // end namespace MyRISCVISD
如果节点不涉及内存操作，其操作码（这里为MyRISCVISD::TEST_NOMEM）的值应该大于ISD::BUILTIN_OP_END并且小于ISD::FIRST_TARGET_MEMORY_OPCODE。比如：
namespace MyRISCVISD {
enum NodeType {
FIRST_NUMBER = ISD::BUILTIN_OP_END,
TEST_NOMEM,
TEST_MEM = ISD::FIRST_TARGET_MEMORY_OPCODE,
};
} // // end namespace MyRISCVISD
除了ISD::BUILTIN_OP_END和ISD::FIRST_TARGET_MEMORY_OPCODE这两个特殊的值以外，还有一个特殊的值ISD::FIRST_TARGET_STRICTFP_OPCODE，有兴趣的可以研究下其使用场景。
step 2： 打印节点名称
为了打印SelectionDAG时能够显示自定义节点的名称，我们需要在子类<Target>TargetLowering中覆写TargetLowering::getTargetNodeName()函数。实现如下：
const char *MyRISCVTargetLowering::getTargetNodeName(unsigned Opcode) const {
switch (Opcode) {
// ...
case MyRISCVISD::TEST_NOMEM:
return "MyRISCVISD::TEST_NOMEM";
case MyRISCVISD::TEST_MEM:
return "MyRISCVISD::TEST_MEM";
default:
return nullptr;
}
}
step 3： 定义特定于目标机器的节点
在.td文件中定义特定于目标机器的节点TEST_SDNode。比如：
def SDT_TEST : SDTypeProfile<1, 2, [
SDTCisVTSmallerThanOp<2, 1>
]>;
def TEST_SDNode : SDNode<"MyRISCVISD::TEST_NOMEM", SDT_TEST>;
LLVM中，常见的定义Pattern的方式包括如下 2 种：
定义指令（派生自抽象记录基类Instruction）时设置其Pattern字段的值。
定义抽象记录基类Pat或ComplexPattern的派生类。
抽象记录基类Pat，用于描述由参数pattern指定的legal DAG可以匹配为由参数result指定的机器指令（该方式可满足大多数情况的需要）。其定义如下（位于llvm/include/llvm/Target/TargetSelectionDAG.td文件）：
class Pat<dag pattern, dag result> : Pattern<pattern, [result]>;
参数pattern，表示legal DAG中一个或多个嵌套的SDNode（可以是机器无关的节点，也可以是机器相关的节点）。
参数result，表示一条或多条嵌套的机器指令。Pattern匹配成功后，指令选择器会将参数pattern所表示的节点替换为这些表示机器指令的节点，从而达到指令选择的目的。
需要注意地是， 这里所说的嵌套表示两个节点之间存在regular-edge。通俗地讲，就是一个节点所定义的具象值（比如i32）作为另一个节点的输入。比如：
Optimized legalized selection DAG: %bb.0 'test:'
SelectionDAG has 9 nodes:
t0: ch = EntryToken
t2: i32,ch = CopyFromReg t0, Register:i32 %0
t4: i32,ch = CopyFromReg t0, Register:i32 %1
t5: i32 = add t2, t4
t7: ch,glue = CopyToReg t0, Register:i32 $x10, t5
t8: ch = MyRISCVISD::RET_FLAG t7, Register:i32 $x10
上述legal DAG中，节点t4所定义的具象值i32作为节点t5的输入，那么这两个节点就是嵌套的节点。
我们可以通过-debug-only=isel选项打印指令选择过程中各阶段的SelectionDAG，并且以Optimized legalized selection DAG中的SelectionDAG为准确定我们想要匹配的一个或多个嵌套节点，从而确定如何编写参数pattern。
需要注意地是， 参数result中操作数的名称和类型必须与参数pattern中的保持一致，但操作数出现的顺序不必相同。除此之外，参数result中的操作数与指令（派生自抽象记录基类Instruction）的InOperandList字段中操作数之间的对应关系是由操作数出现的先后顺序而非操作数名称决定的。比如：
def ADDI : RV32 {
let OutOperandList = (outs GPR:$rd);
let InOperandList = (ins simm12:$imm12, GPR:$rs1);
let AsmString = "addi $rd, $rs1, $imm12";
bits<5> rd;
bits<5> rs1;
bits<12> imm12;
let Inst{31-20} = imm12;
let Inst{19-15} = rs1;
let Inst{14-12} = 0b000;
let Inst{11-7} = rd;
let Inst{6-0} = 0b0010011;
}
def : Pat<(add GPR:$a, i32:$b), (ADDI simm12:$b, GPR:$a)>;
为了便于理解，参数pattern和指令中对应操作数的名称通常保持一致。
见 《LLVM 之后端篇（3）：如何添加 MyRISCV 目标后端的第一条指令》。
下一篇：上一级目录