第6章
TableGen介绍

编译器最为基础的功能之一是将高级语言转换成可以在硬件上执行的机器码，为了支持尽可能多的硬件，通用编译器需要为每一款硬件都实现这一转换。为了更好地生成高质量的目标机器码，编译器后端开发者需要了解目标机器的指令集信息（包括具体支持哪些指令、指令有什么属性、应该使用什么寄存器、指令间存在什么样的依赖）。虽然每一款不同的硬件指令集都不相同，但都包含指令、寄存器、调用约定等信息，所以可以将这些信息进行抽象。这样编译器后端实现时就可以分为两层：具体硬件信息和与硬件无关的编译框架。不同的目标硬件都包含了丰富的指令、寄存器信息等，直接描述这些信息将会非常冗杂，并且很难做到格式统一，所以很有必要设计一种通用的后端信息描述语言，这就是目标描述语言TableGen。

因为TableGen和代码生成过程密切相关，所以本章简单介绍TableGen的词法、语法，并且演示如何从目标描述语言转换为C++代码，从而和编译器的代码生成框架结合起来。本章最后将以指令匹配为例介绍如何写TD文件。

6.1 目标描述语言

下面分别从TableGen的词法和语法展开介绍。

6.1.1 词法

TableGen作为一门DSL（Domain Specific Language，领域描述语言）语言，提供了关键字、标识符、特殊运算符等信息，在词法分析阶段对TD文件进行分析可以得到对应的token（单词符号）。

1） 数值字面量 ：表示TD文件直接给出的数值，只支持整数字面量，可以定义十进制、十六进制和二进制，其文法如代码清单6-1所示。

代码清单6-1 数值字面量文法

上述文法含义：TokInteger表示整数，可以是十进制整数、十六进制整数或二进制整数；其中十进制整数以“+”或“-”符号开头（“+”可以省略），后面是一个或多个0～9的数字；十六进制整数以“0x”开头，后面是一个或多个0～9的数字或a～f的字母；二进制整数以“0b”开头，后面是一个或多个数字0或者数字1。

2） 字符串字面量 ：表示TD文件中的字符串常量，其文法如代码清单6-2所示。

代码清单6-2 字符串字面量文法

上述文法含义：TokString表示单行的字符串字面量，以双引号““”作为开头和结尾，中间可以是非双引号的“"”字符和转义字符“\”；TokCode，表示跨行的字符串字面量，以“[{”开头、以“}]”结尾，中间可以是非“}]”的字符串。

3） 关键字 ：TableGen定义了一些关键字，这些关键字都有特殊的含义。目前的关键字有assert、bit、bits、class、code、dag、def、dump、else、false、foreach、defm、defset、defvar、field、if、include、int、let、list、multiclass、string、then、true。这些关键字分别描述类型、语法结构等信息，6.1.2节将对部分重要关键字进行介绍。

4） 标识符 ：定义了变量，其文法如代码清单6-3所示。

代码清单6-3 标识符文法

上述文法含义：TokIdentifier表示标识符，以0个或多个0～9的数字开头，中间是字母或者下划线，后面是0个或多个字母、下划线或者数字；TokVarName表示别名，以$开头，中间是字母或者下划线，后面是0个或多个字母、下划线或者数字。其中标识符是大小写敏感的。另外，标识符也可以是数字开头，如果标识符只有数字，则TableGen会将它解释为整数字面量。

注意

TokVarName仅仅适用于dag中。

5） 特殊运算符 ：TableGen还提供了“!”运算符，以“!”开头，后跟一些运算。例如，!add表示对多个操作数进行求和计算，“!”运算符可以认为是TableGen内置的处理方式。关于“!”运算符的更多介绍可以参见官网 。

6） 基本分隔符 ：TableGen还提供了一些基础符号（参见6.1.2节），例如-、+、[、]、{、}、(、)、<、>、:、;、.、...、=、?、＃等，这些符号作为分界符通常要配合语法来使用，例如<>用于定义模板参数，[]用于定义列表数据。

7） 其他词法 ：TableGen提供了include语法，可以在本文件中引入其他的TD文件，并提供了预处理的功能，详细内容可以参考官网。

6.1.2 语法

TableGen提供的语法比较丰富，限于篇幅无法展开介绍，本节仅介绍类型（type）、值（value）和记录（record）相关的内容，其他内容请参考官网。

1.类型

TableGen定义了如下数据类型。

1）bit：表示布尔类型，可以取值0或1。

2）int：表示64位的整数。

3）string：表示任意长度的字符串。

4）dag：表示可嵌套的DAG。DAG的节点由一个运算符、0个或多个参数（即操作数）组成，节点中的运算符必须是一个实例化的记录。DAG的大小等于参数的数量。

5）bits<n>：表示大小为 n 的位数组（数组中的每个元素占用一位）。

6）list<type>：表示元素的数据类型为类型的列表。列表元素的下标从0开始。

注意

位数组bits<n>中的索引值是从右往左递增的，即索引为0的元素位于最右侧。比如bits<2> val={1,0}，表示十进制整数2。

注意，在TableGen中，一个无环图可以使用dag数据类型直接表示。dag节点由一个运算符和0个或多个参数组成，每个参数可以是任何类型，例如使用其他dag节点作为参数可以构建基于dag节点的任意图。

dag节点的语法是(operator argument1,argument2,…,argument n )，其中operator为操作数，必须显式定义，且必须是一个记录，其后可以有零个或多个参数，参数之间用逗号分隔。参数可以有3种格式：value（参数值类型）、value:name（参数值类型和相关名字）、name（未设置值类型的参数名字）。

2.值

TableGen中的值可以通过如代码清单6-4所示的文法进行描述。

代码清单6-4 值的文法

值可以分为3类，分别是简单值、后缀值以及复合值。其中：

1）简单值（SimpleValue）可以是整数、字符串或者代码。例如“int a=1;”表示变量a的赋值为1。

2）后缀值（ValueSuffix*）是在简单值后面增加约束。例如“let a{1-3}=0b110; ”表示a的赋值为二进制值“0b0110”。

3）复合值（Value“＃”[Value]）表示将多个值通过连接符“＃”进行组合。例如“let str="12" ＃ "ab";”表示将两个字符串连接形成一个新的值。

3.记录

TableGen最主要的目的之一是生成记录，然后后端基于记录进行分析得到最终结果。记录可以被看作是有名字、有类型、具有特定属性的结构体。TableGen分别通过def和class定义记录，并在此基础上提供批量定义记录的高级语法mutliclass、defm。

1）用def定义一个具体的记录：非常类似于C语言中用struct定义的结构体，包含了名字、类型和属性，def示例如代码清单6-5所示。

代码清单6-5 def示例

代码清单6-5定义了一个记录，名字为record_example，它包含了两个字段：a和b。其中，a的类型为整型，值为1；b的类型为字符型，值为def example。

2）用class定义一个记录类：该记录类可以被实例化为记录，它非常类似于C++中的class。来看一个calss的应用示例，示例首先用class定义一个记录类，然后通过def来实例化记录，如代码清单6-6所示。

代码清单6-6 使用class定义记录类，使用def实例化记录示例

代码清单6-6首先通过class定义记录类TestInst，然后通过def实例化两个记录——ADD和MUL。在实例化的过程中，要用let关键字对class中定义的字段进行赋值，例如class中定义了asmname，在ADD中通过let asmname="add"对asmname进行赋值。

我们还可以定义class层次，并通过继承的方式来使用（所以它非常类似于C++中的class）。使用class可以大大简化记录的定义，将公共的信息通过class定义，然后通过def进行实例化。

3）用multiclass和defm定义一组记录。虽然可以通过class对记录进行抽象，然后通过def实例化。但是在实际工作中会遇到这样的问题：很多记录类也比较类似，例如在后端中存在add指令，add指令接收两个操作数，第一种合法的指令是两个操作数都是寄存器；第二种合法的指令是一个操作数是寄存器，另一个操作数是立即数。此时需要利用两个class对add指令进行抽象。因为这两个class非常类似，只有一个操作数不相同而已，所以TableGen引入multiclass来一次定义多个class。multiclass定义的多个类可以通过defm进行实例化，使用multiclass和defm同时定义多个记录的示例如代码清单6-7所示。

代码清单6-7 使用multiclass和defm同时定义多个记录示例

multiclass比较抽象，上面的例子相当于使用multiclass定义了两个记录类，分别为rr和rm，伪代码如代码清单6-8所示。

代码清单6-8 用multiclass分别定义rr和rm的伪代码

然后通过def进行实例化，实例化对象分别是MyBackend_rm和MyBackend_rr。可以直接使用llvm-tblgen编译代码清单6-7，生成的MyBackend_rm和MyBackend_rr记录如代码清单6-9所示。

代码清单6-9 生成的MyBackend_rm和MyBackend_rr记录示例

注意

llvm-tblgen在输出记录时并没有显式地展开（即未拆分）multiclass。

本节仅简单示范了def、class、multiclass、defm的使用，并未介绍更高级的语法的应用。希望通过本节的介绍，读者能够读懂TD文件，知道如何从TD文件生成对应的记录。关于TableGen还有很多内容，限于篇幅无法在本书中展开介绍，如文法的定义、使用方式等，以及一些高级功能（如foreach、defvar、defset、assert等语法），读者可参考官网深入了解TableGen。

6.2 TableGen工具链

LLVM提供的工具llvm-tblgen可将TD文件转换成和LLVM框架配合的C++代码，整个转换过程实际分成两步。

1）将TD文件转换成记录，llvm-tblgen处理该过程的部分也称为工具链前端。

2）对记录中的信息进行抓取、分析和组合以生成inc头文件，通常和LLVM框架配合使用。llvm-tblgen处理该过程的部分也称为工具链后端。需要注意的是，后端的选型完全是领域相关的，用什么后端完全由开发者定义。目前常见的后端可以分为以下3种。

①LLVM后端：解析记录以生成与架构相关的一些信息，如描述架构寄存器和指令信息的头文件，或用于指导代码生成、指令选择的代码片段。

②Clang后端：解析记录以生成与架构无关的一些信息，如语法树的信息、诊断信息、类属性等。

③通用后端：该后端对记录进行简单的处理，而不对记录中的具体内容进行解析，比如打印条目信息、可搜索表信息（如AArch64架构生成的系统寄存器表）。

llvm-tblgen工具链工作流程示意图如图6-1所示。

实际上现在TD的使用场景已经不局限于上面介绍的3种后端，其适用范围越来越广，比如MLIR也是基于TD文件设计方言（dialect）、算子（operator）等关键信息，当然MLIR也需要实现自己的后端，以生成自己所需要的内容。

下面以BPF后端为例介绍如何通过TD文件生成和LLVM框架匹配的代码。

6.2.1 从TD定义到记录

如前所述，TableGen前端解析TD文件后就可以得到记录。因为LLVM支持多种后端，所以在设计TD文件的记录类时又进行了抽象，将记录类分成：适用于所有后端的基类记录类、适用于某一后端的派生记录类。下面以加法指令add的定义为例进行介绍。首先定义指令基类，然后定义指令的派生类，最后定义具体的指令，如代码清单6-10所示。

代码清单6-10 BPF中add指令相关的TD描述

使用llvm-tblgen命令可以将上述相关TD文件转换成记录，BPF相关信息定义在BPF.td文件中，相关命令如代码清单6-11所示（其中，your_dir需要替换为你自己的目录名）。

代码清单6-11 使用llvm-tblgen命令将TD文件转换为记录

下面以ADD_rr为例展示生成的记录的部分片段，如代码清单6-12所示。

代码清单6-12 生成ADD_rr记录的代码片段

可以看到ADD_rr定义了加法指令，它包含指令匹配模式（InOperandList）、指令匹配后的输出序列（OutOperandList）、指令匹配规则模板（Pattern）、对应的汇编代码（AsmString）等信息。

6.2.2 从记录到C++代码

接下来需要对记录进一步处理，根据后端功能需要提取不同的信息。图6-1所示的后端功能非常多，不同功能需要的信息有所不同，这里以指令匹配为例介绍如何从记录提取指令匹配所需要的信息。

仍然以BPF后端为例，在使用llvm-tblgen工具时传入-gen-dag-isel参数，就可以生成指令选择相关信息。一般会生成专门的头文件来保存相关信息，例如BPF指令选择对应的头文件为BPFGenDAGISel.inc。BPFGenDAGISel.inc文件中最为重要的一部分内容是指令匹配表（MatcherTable），它描述了将LLVM IR匹配到特定后端架构指令的过程。指令匹配表中ADD_rr指令对应的指令匹配片段如代码清单6-13所示。

代码清单6-13 ADD_rr指令对应的匹配片段

第7章会介绍如何使用指令匹配表，这里暂不展开。我们先简单看一下如何从记录中提取指令匹配信息。实际上这个过程的逻辑并不复杂，可以简单地总结为先从ADD_rr的记录中提取Pattern字段（list<dag> Pattern=[(set GPR:$dst, (add i64:$src2, i64:$src))];），然后对Pattern字段进行解析。根据该字段内容生成对应的匹配信息。例如，以上述Pattern字段中的(add i64:$src2, i64:$src)作为源模板，表示待匹配的中间表达式需要带有两个64位寄存器作为操作数的ISD::ADD节点（ISD::ADD节点包含在add指令的定义中）。如果待匹配的中间表达式为i64:$temp=(add i64:$src2,i64:$src)，则(set GPR:$dst,i64:$temp)为相应的匹配结果，表示将i64类型的$temp结果存放到GPR类型的寄存器中。相应地，该待匹配中间表达式可以被映射为ADD_rr指令，其输出为$dst，输入为$src2和$src。匹配过程示意图如图6-2所示。

TableGen工具链根据对上述Pattern的解释来生成对应的匹配规则信息，在生成匹配信息时还需要对操作符、操作数的类型进行约束，只有类型相同才能匹配（如OPC_CheckType,MVT::i64描述的就是类型的约束），最后得到如代码清单6-13所示的匹配表。

虽然生成指令匹配表的逻辑比较简单，但是匹配表的细节非常多，不仅需要考虑匹配能否成功，还需要考虑匹配性能（如何布局不同匹配路径的顺序、当前匹配失败后如何快速跳转到下一条匹配路径等），这个过程非常琐碎，我们不再介绍。如果读者感兴趣，可以参考相关源码。这里读者只需要了解从记录的相关字段生成匹配表的过程即可。

6.3 扩展阅读：如何在TD文件中定义匹配

6.2节通过ADD_rr指令演示了在定义记录时指定指令的匹配规则，进而生成匹配表的过程。但是实际情况往往会更为复杂。例如在需要了解输入参数情况才能进行指令匹配的场景，就无法使用上述方案。在LLVM的TD文件中也可以看到有很多关于匹配的实现，比如Pat、ComplexPattern、PatLeaf、PatFrag等定义记录类，这些匹配记录类和指令中的直接匹配规则一起构成了指令选择中的匹配规则。在这4个记录类中，Pat和ComplexPattern会直接生成匹配规则，而PatLeaf和PatFrag主要用于在TD文件中快速写匹配规则。下面简单介绍通过Pat实现的隐式定义匹配模块，通过ComplexPattern定义的复杂匹配模板以及匹配规则支撑类。

6.3.1 隐式定义匹配模板

在BPF后端的指令选择阶段，LLVM IR中的call指令首先被转换为BPFcall节点（BPFcall是一个特殊的SNDode，转换细节参见第7章）。指令选择就是指从BPFcall节点转换到JAX和JAXL的过程，该过程通常是通过匹配规则实现的。鉴于call指令需要转换为两条不同的后端指令，常见的做法是定义两条匹配规则，分别生成相应的后端指令。匹配规则中只有参数类型不同，其他信息都是一致的。为此LLVM社区提供了可以提取公共的匹配规则（即将要介绍的Pat记录类）的方法，以将存在差异的部分抽象出来，从而简化了指令的匹配定义的过程。BPFcall节点匹配模板定义如代码清单6-14所示。

代码清单6-14 BPFcall节点匹配模板定义

代码清单6-14定义了针对BPFcall节点的匹配规则，当BPFcall的目的地址为立即数时，将其匹配为JAL指令；当BPFcall的目的地址为通用寄存器类型（GPR）时，将其匹配为JALX指令。其中，Pat是匹配记录，它的定义非常简单，如代码清单6-15所示。

代码清单6-15 Pat定义

从Pat的定义来看，它接收两个参数：第一个参数（输入）表示待匹配的形式；第二个参数（输出）表示匹配后的指令形式。

那如何生成匹配表？实际上也非常简单，TableGen工具链在遇到使用def : Pat定义的记录时，会生成一个匿名的记录，其中PatternToMatch字段是待匹配信息，ResultInstrs是输出信息，然后工具链后端从记录中抓取相关信息，从而生成匹配信息。例如在代码清单6-14中，两个def : Pat定义的记录实际会生成两个匿名类。隐式模板如代码清单6-16所示。

代码清单6-16 隐式模板

它们都有一个字段PatternTomatch用于匹配信息的生成（imm表示立即数，GPR表示通用寄存器），而TableGen后端处理则和6.2.2节内容相同。

6.3.2 复杂匹配模板

TableGen的语言描述能力不是万能的，比如它无法区分数值和地址。当遇到一些访存相关的LLVM IR时，就无法正确进行指令匹配，所以TableGen提供了一种方法，允许开发者在TD文件中编写C++代码，直接和LLVM框架配合，按照这种方式实现的匹配规则称为复杂模式（ComplexPattern）匹配。

以LLVM IR中的load指令为例，它的语义非常丰富，支持从各种源（例如栈、全局地址等）加载数据。后端无法通过简单的指令描述或者隐式匹配来实现指令匹配，一种合适的方式是在load指令中对不同的源进行特殊处理，所以LLVM提供了SelectAddr函数（C++编写）来处理不同的源。SelectAddr函数的定义如代码清单6-17所示。

代码清单6-17 SelectAddr函数的定义

接下来的问题是如何把这个函数和指令匹配过程结合起来，这个时候就用到了ComplexPattern。例如，BPF后端中定义了一个特殊的记录ADDRri，将所有和源相关的工作都委托到SelectAddr函数中实现。ADDRri的定义如代码清单6-18所示。

代码清单6-18 ADDRri的定义

ADDRri经过TableGen工具解析后得到的记录如代码清单6-19所示。

代码清单6-19 ADDRri经过TableGen工具解析后得到的记录

可以看到ADDRri记录中有一个字段为SelectFunc（它的值本质上是一个函数指针），只要在匹配表生成的过程中提取该字段，并且保留相关信息，最后在匹配时就可以使用了。

接下来就是如何使用ADDRri这个记录，因为它可以被视为dag类型，所以可以直接出现在其他的记录中。例如BPF后端定义的LDW记录就可以使用ADDRri作为其模板中的源操作数，如代码清单6-20所示。

代码清单6-20 BPF后端定义的LDW记录

可以看到LDW使用了ADDRri记录，经过TableGen工具链的解析，最终得到的LDW记录如代码清单6-21所示。

代码清单6-21 解析后得到的LDW记录

可以看到，LDW记录本身的匹配模式（字段Pattern）包含了ADDRri记录，而ADDRri又使用了字段SelectFunc将其工作委托到对应的C++函数中，在匹配表生成时需要把这些信息提取出来，然后在对应框架中调用函数指针SelectAddr即可。

6.3.3 匹配规则支撑类

LLVM提供了PatLeaf和PatFrag支撑类的实现，开发者可以利用它们快速编写匹配规则。例如前面的LOADi64记录使用了PatFrag（dag的操作码）匹配过程中需要用到一些公共的匹配能力的抽象，定义为PatFrag后可以在多个记录中使用，例如在多条记录中都可以使用ADDRri。

而PatLeaf描述的是特殊匹配节点（叶子节点），它没有操作数。这样的节点只能被其他匹配记录使用，而不能使用其他的记录。

注意

LLVM中的TableGen和GCC的MD（Machine Description，机器描述）都是目标描述语言，它们有非常多的相似之处。例如，它们都包含指令选择相关的模板、都包含目标指令对应的汇编、都包含了调度相关的指令延迟等信息。它们区别在于，MD文件中不包含寄存器和指令编码等信息，这意味着如果使用MD文件来定义一个编译器后端信息，GCC只能将源码文件编译、生成文本汇编格式，开发者需要自行开发一套汇编器，再根据自定义的编码表将文本汇编文件转换成二进制文件。

6.4 本章小结

本章对目标描述语言进行了简单的介绍，涵盖从目标描述语言到记录，再到C++代码的生成过程。通过本章介绍希望读者可以了解目标描述语言和LLVM框架如何配合工作的。

本章最后对LLVM通过目标描述语言定义的模式匹配进行了总结，它们决定了如何生成匹配表，而匹配表是指令选择的基础。 mQl7bHM4Gm7I70JIB/IqAiP5jKtQclR0E4+A+BJ/EzjK23XPte417iZXBm8fQE+M