LLVM 之后端篇（5）：理解 SelectionDAG 合法化
Author: stormQ
Created: Friday, 15. April 2022 11:29PM
Last Modified: Friday, 01. July 2022 00:36AM
本文基于release/13.x版本的 LLVM 源码，介绍了如何指定目标机器的合法类型和合法操作，以及如何定制非法类型和非法操作的合法化行为。从而，初步了解SelectionDAG合法化的整体过程。
LLVM默认的指令选择器是基于SelectionDAG实现的。SelectionDAG是一个有向无环图（Directed-Acyclic-Graph，DAG），其节点为SDNode。每个SDNode对应一条指令或一个操作数。从概念上，SelectionDAG分为legal和illegal两种DAG。如果DAG中的所有节点都是目标机器原生支持的，那么称之为legal DAG。也就是说，legal DAG中既不存在目标机器不支持的操作，也不存在目标机器不支持的类型（包括指令的操作数类型及其操作结果类型）。
在指令选择（特指在<Target>DAGToDAGISel::Select()函数被调用）之前，我们需要将illegal DAG转换为legal DAG，该过程称为SelectionDAG合法化。它包括以下两种情况：
类型合法化（Type Legalization），即将SDNode的操作数以及操作结果中的非法类型转换为目标机器支持的类型。
操作合法化（Operation Legalization），即将SDNode所表示的非法操作转换为目标机器支持的操作。
LLVM中，MVT::SimpleValueType定义了所有特定于目标机器的类型（位于llvm/include/llvm/Support/MachineValueType.h文件）。通常情况下，每种目标机器仅支持其中部分类型。对于不支持的类型（illegal type），我们需要将其转换为合法的类型（legal type）。而在类型合法化之前，我们需要指定目标机器中哪些类型是合法的以及如何处理非法类型。
我们通过在子类<Target>TargetLowering的构造函数中调用addRegisterClass()指定目标机器的合法类型，以及这些合法类型各自对应的寄存器类。比如，函数AArch64TargetLowering::AArch64TargetLowering()的部分实现如下：
addRegisterClass(MVT::i32, &AArch64::GPR32allRegClass);
addRegisterClass(MVT::i64, &AArch64::GPR64allRegClass);
上述代码将MVT::i32和MVT::i64指定为目标机器AArch64的合法类型，并分别对应GPR32all、GPR64all寄存器类。
需要注意地是， 目标机器中的每种合法类型只能对应一种寄存器类。这是因为，函数addRegisterClass()的实现如下（位于llvm/include/llvm/CodeGen/TargetLowering.h文件）：
void addRegisterClass(MVT VT, const TargetRegisterClass *RC) {
assert((unsigned)VT.SimpleTy < array_lengthof(RegClassForVT));
RegClassForVT[VT.SimpleTy] = RC;
}
LLVM在类TargetLoweringBase中提供了如下 3 个接口，可用于判断是否为目标机器的合法类型（位于llvm/include/llvm/CodeGen/TargetLowering.h文件）：
bool isTypeLegal(EVT VT) const。该函数的参数VT表示要判断的类型；返回值为true时表示该类型为合法类型，否则为非法类型。
LegalizeTypeAction getTypeAction(LLVMContext &Context, EVT VT) const。该函数的参数Context表示上下文信息，参数VT表示要判断的类型；返回值为TargetLoweringBase::TypeLegal时表示该类型为合法类型，否则为非法类型。
LegalizeTypeAction getTypeAction(MVT VT) const。该函数的参数VT表示要判断的类型；返回值为TargetLoweringBase::TypeLegal时表示该类型为合法类型，否则为非法类型。
方式 1（推荐用法）：
在函数<Target>TargetLoweringBase:ReplaceNodeResults()中判断MVT::i64是否为目标机器的合法类型：
void <Target>TargetLowering::ReplaceNodeResults(SDNode *N,
SmallVectorImpl<SDValue> &Results,
SelectionDAG &DAG) const {
if (isTypeLegal(MVT::i64)) {
// ...
}
}
在函数<Target>DAGToDAGISel::Select()中判断节点N第一个定义的值是否为目标机器的合法类型：
void <Target>DAGToDAGISel::Select(SDNode *N) {
auto RetVT = N->getValueType(0);
if (TLI->isTypeLegal(RetVT)) {
// ...
}
}
在所有调用addRegisterClass()地方的后面，我们通过调用computeRegisterProperties()函数指定目标机器中非法类型的处理方式。比如，函数AArch64TargetLowering::AArch64TargetLowering()的部分实现如下：
addRegisterClass(MVT::i32, &AArch64::GPR32allRegClass);
addRegisterClass(MVT::i64, &AArch64::GPR64allRegClass);
computeRegisterProperties(Subtarget->getRegisterInfo());
LLVM中，TargetLoweringBase::LegalizeTypeAction定义了目标机器中非法类型的所有处理方式（位于llvm/include/llvm/CodeGen/TargetLowering.h文件）。常见的处理方式如下：
TypePromoteInteger，即将小的非法整型提升为大的合法整型（称为promoting）。整型提升默认遵循就近原则。比如，如果目标机器的合法整型为i32和i64，那么i1、i8和i16等非法整型会默认提升到i32而不是i64。
TypeExpandInteger，即将大的非法整型扩展为多个小的合法整型（称为expanding）。整型扩展也默认遵循就近原则。比如，如果目标机器的合法整型为i32和i64，那么非法整型i128会默认扩展成 2 个i64而不是 4 个i32。
TypeSplitVector，即将大的非法向量类型拆分为多个小的合法向量类型（称为splitting）。向量拆分也默认遵循就近原则。特殊地，如果不存在小的合法向量类型，那么非法向量类型的所有元素就会被转换为标量（称为scalarizing）。
TypeWidenVector，即将小的非法向量类型扩展为大的合法向量类型（称为widening）。向量扩展也默认遵循就近原则。
需要注意地是， 对于目标机器中的非法标量类型，LLVM不允许子类<Target>TargetLowering定制其LegalizeTypeAction。而对于目标机器中的非法向量类型，LLVM允许子类<Target>TargetLowering覆写getPreferredVectorAction()函数定制其LegalizeTypeAction。
类型合法化的实现为SelectionDAG::LegalizeTypes()函数（位于llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp文件）。它包括以下三种情况：
非法整型合法化。相关函数如下（位于llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp文件）：
DAGTypeLegalizer::PromoteIntegerResult()，用于将操作结果中的非法整型提升为合法整型。
DAGTypeLegalizer::ExpandIntegerResult()，用于将操作结果中的非法整型扩展为多个合法整型。
DAGTypeLegalizer::PromoteIntegerOperand()，用于将操作数中的非法整型提升为合法整型。
DAGTypeLegalizer::ExpandIntegerOperand()，用于将操作数中的非法整型扩展为多个合法整型。
非法浮点型合法化（位于llvm/lib/CodeGen/SelectionDAG/LegalizeFloatTypes.cpp文件）。
非法向量类型合法化。相关函数如下（位于llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp文件）：
DAGTypeLegalizer::ScalarizeVectorResult()，用于将操作结果中的非法向量类型标量化。
DAGTypeLegalizer::SplitVectorResult()，用于将操作结果中的非法向量类型拆分为多个合法向量类型。
DAGTypeLegalizer::WidenVectorResult()，用于将操作结果中的非法向量类型扩展为合法向量类型。
DAGTypeLegalizer::ScalarizeVectorOperand()，用于将操作数中的非法向量类型标量化。
DAGTypeLegalizer::SplitVectorOperand()，用于将操作数中的非法向量类型拆分为多个合法向量类型。
DAGTypeLegalizer::WidenVectorOperand()，用于将操作数中的非法向量类型扩展为合法向量类型。
需要注意地是：
关于非法向量类型标量化，LLVM 13.0仅支持对元素数量为 1 的非法向量类型进行标量化。对于元素数量大于 1 的非法向量类型，如果目标机器不支持任何向量类型，那么该非法向量类型会经过一系列的widening、splitting处理转化为元素数量为 1 的非法向量类型后再进行标量化。
LLVM允许定制目标机器中非法类型（包括非法的操作数类型和非法的操作结果类型）的合法化行为。
step 1： 指定类型合法化行为是Custom
在子类<Target>TargetLowering的构造函数中调用setOperationAction()函数指明要对哪个节点的哪种非法类型（包括非法的操作数类型和非法的操作结果类型）进行类型合法化行为的定制。比如：
setOperationAction(ISD::ADD, MVT::i8, Custom);
上述代码表示，如果节点的操作码是ISD::ADD，并且该节点的操作数或操作结果的类型为MVT::i8，那么该节点的类型合法化行为是用户自定义的。
step 2： 对于非法操作结果，实现用户自定义的类型合法化行为
在子类<Target>TargetLowering中覆写成员函数ReplaceNodeResults()实现用户自定义的非法操作结果的类型合法化行为。比如：
void <Target>TargetLowering::ReplaceNodeResults(SDNode *N,
SmallVectorImpl<SDValue> &Results,
SelectionDAG &DAG) const {
SDLoc DL(N);
switch (N->getOpcode()) {
case ISD::ADD: {
assert(N->getValueType(0) == MVT::i8 && "Unexpected custom legalisation!");
auto NewOp0 = DAG.getNode(ISD::SIGN_EXTEND, DL, MVT::i32, N->getOperand(0));
auto NewOp1 = DAG.getNode(ISD::SIGN_EXTEND, DL, MVT::i32, N->getOperand(1));
auto NewRes = DAG.getNode(ISD::ADD, DL, MVT::i32, NewOp0, NewOp1);
Results.push_back(NewRes);
break;
}
default:
LLVM_DEBUG({ dbgs() << "ReplaceNodeResults: "; N->dump(&DAG); });
llvm_unreachable("Don't know how to custom type legalize this operation!");
}
}
对于成员函数ReplaceNodeResults()，需要注意地是：
函数返回时，如果第二个参数Results的大小不为 0，那么其大小必须等于节点N所定义值的个数。
函数返回时，如果第二个参数Results的大小为 0，那么用户自定义的类型合法化行为实际上不会对节点N生效。
step 3： 对于非法操作数，实现用户自定义的类型合法化行为
在子类<Target>TargetLowering中覆写成员函数LowerOperationWrapper()实现用户自定义的非法操作数的类型合法化行为。
对于成员函数LowerOperationWrapper()，需要注意地是：
函数返回时，如果第二个参数Results的大小不为 0，那么其大小必须等于节点N所定义值的个数。
函数返回时，如果第二个参数Results的大小为 0，那么用户自定义的类型合法化行为实际上不会对节点N生效。
当用户自定义类型合法化行为时，函数ReplaceNodeResults()先于LowerOperationWrapper()被调用。这意味着，如果函数ReplaceNodeResults()中除了合法化非法的操作结果类型以外，还进行了非法操作数类型的合法化；那么函数LowerOperationWrapper()中的用户自定义的类型合法化行为一定不会生效。
函数TargetLowering::LowerOperationWrapper()的默认实现会调用LowerOperation()虚函数。
LLVM中的操作分为机器无关的和机器相关的。机器无关操作的操作码定义在ISD::NodeType中（位于llvm/include/llvm/CodeGen/ISDOpcodes.h文件）。机器相关操作的操作码通常定义在<Target>ISD::NodeType中（位于llvm/lib/Target/<Target>/<Target>ISelLowering.h文件）。
通常情况下，每种目标机器仅支持部分机器无关的操作。对于不支持的操作，我们需要将其转换为合法操作。而在操作合法化之前，我们需要指定目标机器中哪些操作是合法的以及如何处理非法操作。需要注意地是， 这里的操作是由操作码和类型构成的，而类型包括操作数类型和操作结果类型。比如：如果目标机器的合法类型为MVT::i32和MVT::i64，但操作码为ISD::ADD的机器无关操作仅支持操作数类型为MVT::i32的加法运算，那么操作码为ISD::ADD且操作数类型为MVT::i64的操作就属于非法操作。
我们通过在子类<Target>TargetLowering的构造函数中调用setOperationAction()指定目标机器的合法操作。比如：
setOperationAction(ISD::SDIV, MVT::i32, Legal);
上述代码表示，如果SDNode的操作码为ISD::SDIV，并且操作数和操作结果的类型都是MVT::i32，那么该操作是合法的（Legal）。
需要注意地是， 对于机器无关的操作，函数TargetLoweringBase::initActions()初始化了其默认值（位于llvm/lib/CodeGen/TargetLoweringBase.cpp文件）。因此，只有目标机器所支持的机器无关操作的默认值不是Legal时，我们才需要显式地将其指定为目标机器的合法操作。
LLVM在类TargetLoweringBase中提供了多个接口，可用于判断是否为目标机器的合法操作。推荐使用：bool isOperationLegal(unsigned Op, EVT VT) const（位于llvm/include/llvm/CodeGen/TargetLowering.h文件）。该函数的参数Op表示操作码，参数VT表示操作数和操作结果类型；返回值为true时表示该操作为合法操作，否则为非法操作。
LLVM中，TargetLoweringBase::LegalizeAction定义了目标机器中非法操作的所有处理方式（位于llvm/include/llvm/CodeGen/TargetLowering.h文件），包括如下几种：
Promote，即将非法操作的操作数和操作结果类型进行提升。实现函数为SelectionDAGLegalize::PromoteNode()（位于llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp文件）。
Expand，即将非法操作尝试转换成其它操作，如果转换失败，则作为LibCall进行处理。至于要转换成哪种操作，取决于函数SelectionDAGLegalize::ExpandNode()的实现（位于llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp文件）。需要注意地是， 如果转换成功，那么转换后的操作不一定是合法的。
LibCall，即非法操作是函数调用。
Custom，即定制非法操作的合法化行为。
我们通过在子类<Target>TargetLowering的构造函数中调用setOperationAction()指定目标机器中非法操作的处理方式。
指定目标机器中非法操作的处理方式为Promote：
setOperationAction(ISD::SDIV, MVT::i8, Promote);
上述代码表示，如果SDNode的操作码为ISD::SDIV，并且操作数和操作结果的类型都是MVT::i8，那么该操作是非法的，其操作合法化的处理方式为Promote。对于这种未显式地指定提升到哪种类型的情况，LLVM会默认提升到下一个合法类型，并且要求该合法类型的操作合法化的处理方式不是Promote。需要注意地是， LLVM的这种默认提升行为仅适用于整型标量。
除此之外，也可以显式地指定提升到哪种类型：
setOperationAction(ISD::SDIV, MVT::i8, Promote);
AddPromotedToType(ISD::SDIV, MVT::i8, MVT::i32);
或
setOperationPromotedToType(ISD::SDIV, MVT::i8, MVT::i32);
上述代码表示，如果SDNode的操作码为ISD::SDIV，并且操作数和操作结果的类型都是MVT::i8，那么该操作是非法的，其操作合法化的处理方式为Promote，并且操作数和操作结果的类型会提升为MVT::i32。
指定目标机器中非法操作的处理方式为Expand：
setOperationAction(ISD::SDIV, MVT::i32, Expand);
上述代码表示，如果SDNode的操作码为ISD::SDIV，并且操作数和操作结果的类型都是MVT::i32，那么该操作是非法的，其操作合法化的处理方式为Expand。
step 1： 指定操作合法化行为是Custom
在子类<Target>TargetLowering的构造函数中调用setOperationAction()函数指明要对非法操作进行操作合法化行为的定制。
setOperationAction(ISD::SDIV, MVT::i8, Custom);
上述代码表示，如果节点的操作码是ISD::SDIV，并且该节点的操作数和操作结果的类型为MVT::i8，那么该非法操作的操作合法化行为是用户自定义的。
step 2： 实现用户自定义的操作合法化行为
在子类<Target>TargetLowering中覆写成员函数LowerOperation()实现用户自定义的操作合法化行为。比如：
SDValue <Target>TargetLowering::LowerOperation(SDValue Op,
SelectionDAG &DAG) const {
SDLoc DL(Op);
switch (Op.getOpcode()) {
case ISD::ADD: {
assert(Op.getValueType() == MVT::i8 && "Unexpected custom legalisation!");
auto NewOp0 = DAG.getNode(ISD::SIGN_EXTEND, DL, MVT::i32, Op.getOperand(0));
auto NewOp1 = DAG.getNode(ISD::SIGN_EXTEND, DL, MVT::i32, Op.getOperand(1));
return DAG.getNode(ISD::ADD, DL, MVT::i32, NewOp0, NewOp1);
}
default:
LLVM_DEBUG({ dbgs() << "LowerOperation: "; Op.dump(&DAG); });
llvm_unreachable("Don't know how to custom lower this!");
}
return SDValue();
}
上述代码表示，将非法操作（操作码为ISD::ADD，操作数和操作结果类型为MVT::i8）合法化为如下 DAG（示意）：
t1: i8 = ...
t3: i32 = sign_extend t1
t2: i8 = ...
t4: i32 = sign_extend t2
t5: i32 = add t3, t4
下一篇：LLVM 之后端篇（6）：如何基于 Pattern 实现指令选择