为LLVM添加简易RISCV后端(五)：算术指令
LLVM
为一个新的指令集编写编译器是一件复杂的事情，尽管LLVM的出现使这个过程比之前简单多了！ 一个匪夷所思的困难是缺乏一个简单的、循序渐进的教程12。 因此，本系列博客试图提供一个从头开始编写LLVM后端的简易教程来解决（部分）问题。
算术指令
现在，我们将把上一篇文章讨论的关于LLVM后端中的指令选择付诸实践。 我们将通过查看RISCW后端的算术指令(比如加法、减法和乘法)的具体实现来做到这一点。
注意：这篇文章中讨论的代码可以在这里找到。
RISCW的算术指令相对简单， 在指令选择过程中仅需要配置指令选择器和合法化器，这主要需编写三部分代码。 首先，使用TableGen描述目标平台支持的指令集。 其次，通知LLVM需要合法化的算术运算和类型。 最后，添加自定义C++代码来增强指令选择器的功能。
注意：在为不同体系结构实现指令选择时，总体思路大致相似，但是具体情况将有所不同。 例如，您的指令集可能具有有趣的/复杂的算术指令，例如长乘或多次累加，可能需要额外的代码来正确地支持这些指令。 另外，我们不会自定义优化，但是您可以查看其他后端有关自定义优化的内容，例如XCore和ARM有很多很好的例子。
注意：这里显示的大部分代码最初来自LLVM现有的RISCV后端，但是为了照顾本教程的读者，它已经被大大简化了。
TableGen
TableGen是描述体系结构（包括寄存器，指令集，调用约定等）的专用编程语言， 其目标是创建可维护、易于阅读的代码来描述体系结构。 在构建LLVM时，TableGen工具将TableGen代码翻译为C++并将其与手工编码的C++文件一起编译。
注意：实际上，我发现TableGen代码很难阅读，更难编码！
简而言之，TableGen是具有以下功能的声明性编程语言：
有两个主要组件：
record和class。record是class的实例，包含了名称和相关字段的值。class是record的抽象，可用于生成具体的record。 两者相互配合可以很好地提取公共代码并减少重复。record可以从一个或多个class继承，还可以定义自己的字段。字段具有名称和值（或值列表），值具有特定的类型（如bit或int）。这是类型列表。
include指令用于将TableGen代码从一个文件包含到另一个文件中，就像C的#include一样。
以下是从LLVM文档中获取的示例，其中显示了一个非常简单的TableGen文件。 它包含一个classC，该class定义了值为1的bit类型的字段V， 还声明了一个从类C派生的记录X。
class C {
bit V = 1;
}
def X : C;后端需要定义TableGen的record，用以声明指令、寄存器等。 这些record必须从内部类继承，这样TableGen工具才能魔术地为这些record生成适当的C++代码。 例如，声明寄存器的record必须从内部的Register类继承。 在这篇文章中，我们将查看声明寄存器和指令的TableGen代码。
注意:TableGen文档在解释它是什么和语法方面做得很好。 但是，介绍后端应该重用的内部类和预定义记录的文档却很少；要了解这些内容您必须查看源代码。
注意:回想一下之前的文章， 我们的CMake文件使用带各种参数的TableGen命令把扩展名为.td的TableGen代码文件转化为扩展名为.inc的C++文件。 在构建系统发出TableGen命令之后，可以在build/lib/Target/RISCW的构建目录中找到生成的文件。 Tablegen的参数可以这里(非常简短地)查看。
注意:TableGen还可以配置指令选择过程中的调度和形成阶段，但是我不会在本教程中讨论这一点。 如果你感兴趣，可以看看这个视频。
定义寄存器
RISCW的寄存器定义非常简单， 可以在llvm/lib/Target/RISCW/RISCWRegisterInfo.td中找到。 让我们对其进行剖析，以了解TableGen的工作方式。
在文件的顶部，我们找到以下类。
let Namespace = "RISCW" in {
class RISCWReg<bits<5> Enc, string n, list<string> alt = []> : Register<n> {
let HWEncoding{4-0} = Enc;
let AltNames = alt;
}
} // end Namespace该代码声明了一个RISCWReg类，该类继承自在include/llvm/Target/Target.td中定义的内部类Register。 该代码还告诉我们，从此类继承时，我们必须提供最多三个参数：
寄存器编码
Enc，它是类型为bits<5>的5位整数。字符串
n，表示人类可读的寄存器名称，如RISCV中的x0、x1等。寄存器的别名列表，该列表是可选的。 例如，RISCV中的x2也可以称为sp，即堆栈指针。 但请注意，此列表是可选的，因为可以声明没有别名的寄存器，如果寄存器没有别名，则把
alt设置[]。
另外，请注意Register类接受一个参数：类型为字符串的寄存器名称。 RISCWReg的其余两个参数（Enc和alt）被let语句用于覆盖Register类定义的HWEncoding和AltNames域。 您可以在这里和这里阅读Register的代码。
接下来，我们在该文件中找到以下Register定义。 每一行代码都是一个record，它定义了一个寄存器。 这些record继承自两个类:RISCWReg(我们已经讨论过了)和DwarfRegNum。 DwarfRegNum是这里定义的另一个内部类，用于为GCC和GDB提供调试信息。
def X0 : RISCWReg<0, "x0", ["zero"]>, DwarfRegNum<[0]>;
...
def X31 : RISCWReg<31,"x31", ["t6"]>, DwarfRegNum<[31]>;文件的最后几行定义寄存器组， RISCW定义了两种寄存器组：GPR通用寄存器和堆栈指针SP寄存器。
def GPR : RegisterClass<"RISCW", [i32], 32, (add
(sequence "X%u", 10, 17),
(sequence "X%u", 5, 7),
(sequence "X%u", 28, 31),
(sequence "X%u", 8, 9),
(sequence "X%u", 18, 27),
(sequence "X%u", 0, 4)
)>;
def SP : RegisterClass<"RISCW", [i32], 32, (add X2)>;定义Register组的record继承自RegisterClass类，后者具有四个参数（还有一个可选的第五个参数，我们将不讨论）：
命名空间在我们的例子中是RISCW，这与我们在上面的RISCWReg类中重写的名称空间字段相匹配。
此组寄存器支持的数据类型列表。 这是一个列表，因为某些体系结构中的寄存器可以支持多种数据类型。 例如，一些64位计算机的寄存器可以在32位和64位模式下工作。 RISCW只适用于32位机器，因此寄存器总是32位，它们的类型就是i32。
从内存中存储或加载寄存器时寄存器的对齐方式。
一个DAG，指示此寄存器组包含的寄存器。还有…
我是说DAG！注意，
GPR的DAG有一个ADD模式，该模式有6个sequence节点。sequence是一种操作，它接受字符串格式参数以及起始值和结束值。 序列中的每个元素都是TableGen工具根据格式参数指定的格式生成。 所以，这个DAG的另一种写法是(add X10, X17,…, X3, X4)。此DAG还指定了寄存器分配器使用寄存器的顺序。 例如，如果两者都可用，分配器将优先使用来自GPR的
x10而不是x4。
寄存器组稍后用于配置合法化器。
定义指令
计算机体系结构使用一组格式对指令进行编码。 例如，RISCV体系结构使用32位编码和4种基本指令格式来编码指令3。 此外，每种格式都有一组唯一的操作码(或操作码)。 然后使用格式和操作码对特定指令进行编码，这使处理器能够识别指令并确定它们的操作数。
在LLVM中，定义指令的方式与定义指令集编码的方式类似。 定义指令的代码通常由两部分组成: 格式定义和指令定义。
定义格式
定义格式的同时也定义了唯一的标识符， 这些标识符指示指令的格式， C++代码使用它来正确地发出指令编码。 RISCW后端定义格式的代码，如下所示:
class InstFormat<bits<5> val> {
bits<5> Value = val;
}
def InstFormatPseudo : InstFormat<0>;
def InstFormatR : InstFormat<1>;
...
def InstFormatOther : InstFormat<17>;注意： 在LLVM后端中，定义指令格式的代码通常在文件llvm/lib/Target/<BACKEND>/<BACKEND>InstrFormats.td中， 而实际定义指令的代码在文件llvm/lib/Target/<BACKEND>/<BACKEND>InstrInfo.td中。 但是在复杂的后端中， 指令定义可以拆分为多个文件， 例如，RISCV的每个扩展都对应一个不同的文件。 这些文件称为llvm/lib/Target/RISCV/RISCVInstrInfo<EXT>.td， 其中<EXT>是扩展字母，如M，A等。 RISCW后端相对简单， 用于定义格式和指令的TableGen代码分别存储在llvm/lib/Target/RISCW/RISCWInstrFormats.td和llvm/lib/Target/RISCWInstrInfo.td中。
注意:RISCW后端基于RISCV后端。 两者都试图严格地根据RISCV的参考手册定义指令， 但这不是必须的。 你也可以针对你的体系结构和编译器构造只属于你的TableGen代码。
RISCW后端为操作码定义了如下record:
class RISCWOpcode<bits<7> val> {
bits<7> Value = val;
}
def OPC_LOAD : RISCWOpcode<0b0000011>;
def OPC_LOAD_FP : RISCWOpcode<0b0000111>;
...
def OPC_SYSTEM : RISCWOpcode<0b1110011>;所有指令必须继承自LLVM内部的Instruction类。 方便起见，RISCW后端还定义了Instruction的子类RWInst， 它覆盖了许多字段，例如Size和TSFlags，同时添加了额外的字段。 Instruction类实际上非常庞大， 需要配置许多选项， 我建议您通读LLVM的源代码以了解什么样的配置可以满足你的需求。
class RWInst<dag outs, dag ins, string opcodestr, string argstr,
list<dag> pattern, InstFormat format>
: Instruction {
field bits<32> Inst;
field bits<32> SoftFail = 0;
let Size = 4;
...
let TSFlags{4-0} = format.Value;
}注意：Instruction类中的许多字段仅对特定任务有用。 例如，仅当发出目标代码时才使用Inst字段和opcode。 因此，不要理会您不需要的东西！
再次为方便起见， RISCW后端为每种格式定义了RWInst类的子类。 我们实际的指令将继承这些“低级的”格式，以避免代码重复。
格式类根据相关格式的编码覆盖Inst字段的值。 另外，还有一个特殊的Pseudo类，用于设置Instruction类中的isPseudo字段。 这些pseudo指令通常是栈调整和函数返回等操作的占位符， 我们将在后面的文章中进行探讨。
class Pseudo<dag outs, dag ins, list<dag> pattern, string opcodestr = "",
string argstr = "">
: RWInst<outs, ins, opcodestr, argstr, pattern, InstFormatPseudo>,
Sched<[]> {
let isPseudo = 1;
let isCodeGenOnly = 1;
}
class RWInstR<bits<7> funct7, bits<3> funct3, RISCWOpcode opcode, dag outs,
dag ins, string opcodestr, string argstr>
: RWInst<outs, ins, opcodestr, argstr, [], InstFormatR> {
bits<5> rs2;
bits<5> rs1;
bits<5> rd;
let Inst{31-25} = funct7;
...
let Opcode = opcode.Value;
}
...关于这些TableGen类，有几点需要强调：
funct *和opcode参数用于形成唯一的操作码，该操作码用于将指令编码为二进制。outs和ins参数是DAG，分别指定指令的输出和输入操作数。 操作数通常是寄存器或立即数，但也可以是堆栈帧位置，全局地址等。opcodestr是指令的助记符，例如ADD用于加法，SUB用于减法，等等。argstr参数是一种格式字符串，用于告诉LLVM如何在汇编中打印指令的操作数。 例如，如果outs参数说有一个$r1寄存器操作数， 而ins参数说有一个$r2寄存器操作数并且argstr的格式为"$r1,$r2"， 则该指令的汇编将首先显示输出操作数（即紧随助记符之后）然后显示,，然后显示输入操作数。在
Pseudo中，还有一个pattern操作数， 它告诉LLVM在目标指令选择阶段可以用该指令替换DAG中的哪些节点。 更详细的细节以后再讨论！
定义指令
为了方便起见，还定义了另一个类， 该类可以根据操作数以及操作是否涉及ALU、内存等来简化指令的定义。 例如，我们有下面的ALU_rr类来定义使用ALU（算数逻辑单元）的指令， 该类有三个GPR类型的操作数:两个是输入，一个是输出。 显然，所有ALU_rr指令都是R格式的，因为该类继承自 RWInstR。 另外，ALU_rr的定义位于let块中， 它覆盖了Instruction中值为0的hasSideEffects、mayLoad和mayStore字段； 这些字段中的大多数都是不言自明的，不过我鼓励您阅读代码以获得更多信息。
let hasSideEffects = 0, mayLoad = 0, mayStore = 0 in
class ALU_rr<bits<7> funct7, bits<3> funct3, string opcodestr>
: RWInstR<funct7, funct3, OPC_OP, (outs GPR:$rd), (ins GPR:$rs1, GPR:$rs2),
opcodestr, "$rd, $rs1, $rs2">;通过继承ALU_rr类来定义指令实际上非常简单。 例如，以下是定义ADD指令的代码：
def ADD : ALU_rr<0b0000000, 0b000, "add">, Sched<[WriteIALU, ReadIALU, ReadIALU]>;TableGen代码很难理解，因为大多数后端都使用深层继承来减少代码重复。 您可能需要拿出笔和纸来手动展开一些记录，以了解其工作原理。 例如，展开ADD的第一级看起来如下所示。 这个较长版本的ADD也是有效的TableGen代码， 将以前版本的ADD替换为这个较长的版本， LLVM仍然可以毫无问题地构建！
let hasSideEffects = 0, mayLoad = 0, mayStore = 0 in
def ADD : RWInstR<0b0000000, 0b000, OPC_OP, (outs GPR:$rd),
(ins GPR:$rs1, GPR:$rs2), "add", "$rd, $rs1, $rs2">,
Sched<[WriteIALU, ReadIALU, ReadIALU]>;定义带有立即数(而不是寄存器)的指令的方法大致相同， 但必须调整输入操作数。 例如，下面显示的ALU_ri类的第二个输入是名为$imm12的12位立即数(类型为simm12)。 simm12的定义证实该类的类型为i32还指明了编译器后端处理该操作数时， 解码器和编码器使用的C++类。 最后，simm12继承自ImmLeaf类， 该类带有一个必须满足的条件， 指令选择期间， DAG中的叶节点必须满足该条件才能匹配simm12类(稍后将详细介绍!)。
def simm12 : Operand<i32>, ImmLeaf<i32, [{return isInt<12>(Imm);}]> {
let ParserMatchClass = SImmAsmOperand<12>;
let EncoderMethod = "getImmOpValue";
let DecoderMethod = "decodeSImmOperand<12>";
let MCOperandPredicate = [{
int64_t Imm;
if (MCOp.evaluateAsConstantImm(Imm))
return isInt<12>(Imm);
return MCOp.isBareSymbolRef();
}];
let OperandType = "OPERAND_SIMM12";
let OperandNamespace = "RISCWOp";
}
...
let hasSideEffects = 0, mayLoad = 0, mayStore = 0 in
class ALU_ri<bits<3> funct3, string opcodestr>
: RWInstI<funct3, OPC_OP_IMM, (outs GPR:$rd), (ins GPR:$rs1, simm12:$imm12)
opcodestr, "$rd, $rs1, $imm12">,
Sched<[WriteIALU, ReadIALU]>;在一些计算机体系结构中（如RISCV）有一些指令是其他指令的别名。 通常，这样做只是为了方便或提高汇编代码的可读性。 例如，RISCV没有专门的寄存器-寄存器移动指令，只能使用不带立即数的ADDI指令代替。 我们可以通过InstAlias和MnemonicAlias类告诉LLVM我们的别名:
合法化
类型和操作的合法化阶段均在后端的TargetLowering子类中使用C++代码进行配置。 在RISCW中，此类为RISCWTargetLowering，其代码在lib/Target/RISCW/RISCWISelLowering.cpp和lib/Target/RISCW/RISCWISelLowering.h中。 我们为支持算术指令所做的大多数更改实际上都在构造函数中。
RISCWTargetLowering::RISCWTargetLowering(const TargetMachine &TM,
const RISCWSubtarget &STI)
: TargetLowering(TM), Subtarget(STI)
{
addRegisterClass(MVT::i32, &RISCW::GPRRegClass);
...
setSchedulingPreference(Sched::RegPressure);
...
setOperationAction(ISD::SRA_PARTS, MVT::i32, Custom);
...
setOperationAction(ISD::ROTL, MVT::i32, Expand);
...
}有几件事值得注意：
addRegisterClass用于配置LLVM寄存器组和对应的寄存器类型，此信息用于类型合法化。setSchedulingPreference用于配置调度和形成阶段。这里我们告诉LLVM使用一个最小化寄存器压力的算法。setOperationAction用于配置LLVM如何使操作合法化，即合法化Section DAG中的节点。 回想一下，有三个选项：扩展、提升和自定义。 LLVM会自动处理前两个操作， 例如，RISCV没有位旋转指令，因此我们要求编译器将该操作扩展为其他操作，如移位和ors以模拟旋转。 标记为自定义的操作在TargetLowering子类中由C++代码处理。
每当LLVM在合法化过程中遇到具有custom操作的DAG节点时， 都会生成对TargetLoweing类的LowerOperation方法的回调。 例如，SHL_PARTS操作用于将64位整数左移。 我们通过构造函数中的setOperationAction(ISD:：SHL_PARTS，MVT:：i32，Custom)来告诉LLVM， 我们实现了一个LowerShlParts函数来来合法化此操作。 LowerShlParts用32位移位和ors等其他合法操作来代替SHL_PARTS节点。 我鼓励您看看代码，看看这是如何工作的！
注意：需要合法化的操作完全取决于后端实现的指令集， 以及TableGen代码中DAG节点与指令匹配的程度（下一节将对此进行详细介绍！）。 如果使某些操作合法化太复杂或发出的代码效率低下， 则说明您的指令集可能缺少某些指令！
目标指令选择
目标指令选择阶段将后端TableGen文件中提供的DAG模式匹配到Section DAG中的节点。 匹配成功时，Section DAG中的节点将被替换为具体机器(或伪)指令的节点。 因此，TableGen定义的模式的质量对于发出好的代码至关重要， 您应该多花费些时间来调整这些模式!
注意：TableGen模式通常定义在llvm/lib/Target/<BACKEND>/<BACKEND>InstrInfo.td文件的末尾。
模式records继承自LLVM的Pat类， 该类有两个参数， 第一个参数是一个包含要匹配的模式DAG，第二个参数是一个带有机器指令的DAG。 当模式匹配DAG中的某个内容时，匹配的节点被第二个参数中的DAG替换。
不出所料，我们将使用一些类来帮助我们简化模式的定义。 这里有两个这样的类：
class PatGprGpr<SDPatternOperator OpNode, RWInst Inst>
: Pat<(OpNode GPR:$rs1, GPR:$rs2), (Inst GPR:$rs1, GPR:$rs2)>;
class PatGprSimm12<SDPatternOperator OpNode, RWInstI Inst>
: Pat<(OpNode GPR:$rs1, simm12:$imm12), (Inst GPR:$rs1, simm12:$imm12)>;PatGprGpr用带有两个通用寄存器操作数作为输入的指令替换DAG中的节点。 例如，下面是ADD指令的模式声明:
def : PatGprGpr<add, ADD>;PatGprSimm12将DAG中的节点替换为具有一个通用输入操作数和一个12位立即数的指令。 为了实现这一点，用simm12取代了Pat中第一个和第二个参数中的GPR。 回想一下，simm12是我们在本文前一节中讨论过的一个record。 它继承自Operand类，因此可以在指令的定义中使用。 simm12也继承自ImmLeaf类，因此也可以在模式定义中使用。 下面是ADDI指令的定义，该指令接受一个立即数:
def : PatGprSimm12<add, ADDI>;注意：ImmLeaf类是用于匹配立即数的模式。 它的参数是即时类型，例如I32、I16以及谓词等。 谓词即C++代码块， 它检查指定模式必须满足的条件。 例如，simm12有一个谓词return isInt<12>(Imm)来检查整数是否在12位范围内。
注意：有时，同一条指令可以与Selection DAG中的多个模式匹配。 在这种情况下，使用LLVM的PatFrag类和Pat来避免代码重复， 如RISCW的bit-shift模式。
注意:RISCW和RISCV后端首先声明指令， 并分别提供模式record。 然而，其他后端，如ARM或XCore，以不同的方式创建Instruction的子类，以便它们接受一个模式参数。 这种方法减少了代码行数，因为模式可以在定义指令的同一record中提供， 但在我看来，这使得TableGen代码更难阅读(也更难解释!)
当在DAG中找到匹配时， Pat的第二个参数也可以转换操作数(通常是立即数)。 为此，我们首先需要声明一个继承自SDNodeXForm的操作节点。 SDNodeXForm以实现所需转换的一段c++代码作为参数。 然后，我们在模式中使用新声明的节点，如下面的示例所示。 在本例中，HI20节点提取立即数的20个最重要的比特位。
def HI20 : SDNodeXForm<imm, [{
return CurDAG->getTargetConstant(((N->getZExtValue()+0x800) >> 12) & 0xfffff,
SDLoc(N), N->getValueType(0));
}]>;
def : Pat<(simm32hi20:$imm), (LUI (HI20 imm:$imm))>;注意：SDNodeXForm节点不插入实际指令。 它们通常用于转换即时数据，因此可以在代码发出之前就完全解析。
随着指令选择的进行，LLVM每个Selection DAG节点调用SelectionDAGISel子类的Select方法。 因此，后端可以在Select方法中提供代码， 实现复杂的模式匹配， 而这种匹配在TableGen中很难表达。 例如，RISCW的Select方法包括用x0寄存器来替换常量0的代码。
注意:SelectionDAGISel子类通常在文件llvm/lib/Target/<backend>/<backend>ISelDAGToDAG.h和llvm/lib/Target/<backend>/<backend>ISelDAGToDAG.cpp中。 例如，RISCW后端相关代码在llvm/lib/Target/RISCW/RISCWISelDAGToDAG.h和llvm/lib/Target/RISCW/RISCWISelDAGToDAG.cpp中。
结束语
实际上有很多方法可以实现一个体系结构的LLVM后端， 所以在使用任何一种方法之前，请确保评估最适合您的需求的方法。 另外，请记住下面的TableGen类的简介，在编写后端时几乎肯定需要这些类。
Register //Register declarations
RegisterClass //Register Class declarations
Instruction //Instruction declarations
Operand //Instruction operands
ImmLeaf //Pattern-matching immediates
SDNodeXForm //Transforming immediates after a match
Pat //Providing a pattern to match in the Selection DAG
PatFrag //Providing a pattern fragment with multiple patterns to match in the Selection DAG