# TableGen语法简介

TableGen是LLVM后端用于保存机器平台信息的一种工具语言。与架构相关的各类优化常需要知道指令的某些“特性”，比如指令调度器需要知道指令是否存在读、写延迟；寄存器分配器需要知道指令是否绑定某个物理寄存器…… 而在LLVM中，不同的优化在流程上是分开的，那么实现这些优化的源文件自然也是分开存放的。如果编译开发过程中需要在这些分散的源文件中各自书写一遍架构相关指令特性，就势必造成信息冗杂，难以维护。  
TableGen于是应运而生，它是为LLVM编译开发的轻量化语言，专门用来书写架构相关的信息供LLVM后端使用。TableGen文件（后缀为.td）使编译器开发人员得以采用“中心化”的方式书写架构相关的信息，也就是将属于同一条指令的不同特性写在一起，生成一份清单，不同的优化再从同一份清单中获取其所需的信息。  
虽然TableGen的使用场景局限于LLVM框架内，它本质上还是一门独立的语言（就像C、Python、Java一样）。只不过，这门语言的功能比较有限，它不能用来写程序，只用于罗列信息并生成C++可以引入的.inc文件。源码位于llvm/lib/TableGen子文件夹，包括Lexer、Parser与其它辅助工具。  
## TableGen能做什么
TableGen的本质是用于生成records（可以类比为C语言中的结构体，其中包含多种不同数据类型），每一个record是包含多个基本数据类型的清单。
```
def JALR : RVInstI<0b000, OPC_JALR, (outs GPR:$rd),
                              (ins GPR:$rs1, simm12:$imm12),
                              "jalr", "$rd, ${imm12}(${rs1})">,
                Sched<[WriteJalr, ReadJalr]>;
```
上面这个例子截选自llvm/lib/Target/RISCV/RISCVInstrInfo.td, 是riscv架构中的JALR指令（jump and link relative）的TableGen定义。哪怕不熟悉TableGen的语法，依然可以大致猜测一下这条record的含义：它定义了一条名为JALR的record, 而这条record继承了RVInstI类型模版。它的func3域被硬编码为000，操作码被硬编码为OPC_JALR（再稍微查找一下会找到OPC_JALR=1100111）；在指令选择阶段，它会生成一个DAG，输出为单个通用寄存器（General Purpose Register, 即GPR），并命名为rd，输入是一个通用寄存器rs1和一个有符号的12位立即数（注意simm12中的前缀"s"），名称为imm12；在后续的汇编生成阶段，这条指令会写作"jalr $rd, $imm12($rs1)"，而以美元符号"$"开头的rd、rs1这些临时变量名最终会被替换为寄存器分配阶段实际分配到的物理寄存器名，imm12也类似，替换为实际的立即数。  
使用`llvm-tblgen -print-records <...>.td`命令可以将一个.td文件展开，变成最终可以被各个LLVM Pass读取的形式。由于一些特别的依赖关系，直接展开某个像RISCVInstrInfo.td这样的次级.td文件会遇到record未定义错误，可以直接展开最顶层的.td文件后在其中查找关键字，在llvm/lib/Target/RISCV目录下使用命令: `llvm-tblgen -print-records RISCV.td -I ../../../include | grep JALR -A 10` 得到如下输出。  
```
def JALR {     // InstructionEncoeding Instruction RVInst RVInstI Sched
    field bits<32> Inst = { imm12{11}, imm12{10}, imm12{9}, imm12{8}, imm12{7}, imm12{6}, im
h12{5}, imm12{4}, imm12{3}, imm12{2}, imm12{1}, imm12{0}, rs1{4}, rs1{3}, rs1{2}, rs1{1},
rs1{0}, 0, 0, 0, rd{4}, rd{3}, rd{2}, rd{1}, rd{0}, 1, 1, 0, 0, 1, 1, 1 };
    field bits<32> SoftFail ={ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
, 0,0,0,0,0,0,0,0,0,0,0};
    int Size = 4;
    string DecoderNamespace =
    list<Predicate> Predicates = [];
    string DecoderMethod = "";
    bit hasCompleteDecoder =  1;
    string Namespace = "RISCV";
    dag OutOperandList = (outs GPR:$rd);
    dag InOperandlList = (ins GPR:$rs1, simm12:$imm12);
    string AsmString = "jalr        $rd, ${imm12}(${rs1})";
...(下略)
```
在源码中定义的编码信息、DAG信息等，一个不落地出现在展开后的record中。从这个例子中能有一个直观的感受：TableGen的功能就如它的名字，是用来生成表格、清单的。一条指令有许多方面的特性需要记录，使用TableGen将它们统一起来，书写在同一份文件中无疑是个好方法。另外，展开后的record多了许多内容，这是由于JALR这一条record继承了RVInstI与Sched两个模版，而这些模版又继承自其它模版，利用TableGen模版复用代码可以减少工作量；同时，一款指令集中的指令往往是可以大致分成几个类别，使用模版由粗到细地书写既不容易出错，又增加了源码可读性。  
使用-print-records指令可以打印一条record全部的信息，然而在编译的不同阶段，需要的可能只是其中一部分。TableGen也提供了不同的命令用于从同一份.td源码中生成不同的指令信息清单，举几个例子。  
`-gen-instr-info`生成一个enum类型，其中包含机器指令在LLVM内部使用的编号
```
namespace RISCV{
  enum {
    PHI = 0,
    INLINEASM = 1,
    ...
    JALR = 11116,
    ...(下略)
```
`-gen-emitter`生成CodeEmitter的函数定义, 其作用是写明各个域如何组成生成最后的二进制。
```
uint64_t RISCVMCCodeEmitter::getBinaryCodeForInstr(const MCInst &MI, 
SmallVectorImpl<MCFixup> &Fixups,
const MCSubtargetInfo &STI) const{
...
const unsigned opcode = MI.getOpCode();
uint64_t Value = InstBits[opcode];
...
switch (opcode) {
    ...
    case RISCV::JALR: {
    // op: imm12
    op = getImmOpValue(MI, 2, Fixups, STI);
    op &=UINT64_C(4095);
    op<<=20;
    Value |= op;
    // op: rs1
    op = getMachineOpValue(MI, MI.getOperand(1), Fixups, STI);
    op &= UINT64_C(31);
    op<<=15;
    Value |= op;
    // op: rd
    op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
    op &= UINT64_C(31);
    op<<=7;
    Value |= op;
    break;
...(下略)
```
## TableGen语法
### 关键字
书写TableGen有一个特点：除了少量基本的内建语法 (built-in grammar) 之外，几乎所有能见到的API都是在其它.td文件中定义的。但凡事总要有起点，以下是TableGen中自带的保留字：  
**数据类型关键字**：
      
| 关键字         | 定义                                                         |
| -------------- | ------------------------------------------------------------ |
| int            | 64位整数                                                     |
| string         | 双引号包括的字符串                                           |
| bit            | 比特值0或1                                                   |
| bits<n>        | n个比特组成的二进制数，使用形如{1,0,1,?}的表达式初始化       |
| list<type>     | 类似c++的list                                                |
| dag            | llvm DAG，形如(record op1 op2 op3 ...)首位必须是一个已定义的record |
| code           | 形如["int main(){}"]，一段代码的字面量                       |
| let            | 用于覆盖一个已赋值变量                                       |
| **定义关键字** |                                                              |

| 关键字             | 定义                                                     |
| ------------------ | -------------------------------------------------------- |
| def<LABEL>         | 定义一条record,命名为LABEL                               |
| class              | 定义一个类                                               |
| multiclass         | 是class的语法糖，可用于一组相近，仅少许变量不同的records |
| defm               | 配合multiclass使用                                       |
| **流程控制关键字** |                                                          |

| 关键字                   | 定义                                                         |
| ------------------------ | ------------------------------------------------------------ |
| foreach i in [start-end] | 循环迭代器，但只能用于数字                                   |
| in                       | 指定作用域，单条record可以直接跟在in之后，多条records须使用{}形成域 |
| if/then/else             | 分支                                                         |

**内建函数(Bang Operators)**：以!开头

| 函数名                                                       | 作用       |
| ------------------------------------------------------------ | ---------- |
| !add(a,b,...)                                                | 数字相加   |
| !con(a,b,...)                                                | DAG融合    |
| !strconcat(str1,str2,...)                                    | 字符串合并 |
| 更全的语法手册请阅读[TableGen Language Reference](https://llvm.org/docs/TableGen/ProgRef.html) |            |
### 基本语法
这里举的例子都是很简单的，没有任何依赖，可以直接用`llvm-tblgen -print-records <文件名>.td`展开
#### 示例1：使用def定义record与匿名record
源码
```
def example {
  int i = 1;
  string h = "hello_world";
}

class c1 {
  int i1 = 1;
}

def d1: c1;
def : c1;
```
输出
```
------------- Classes -----------------
class c1 {
  int i1 = 1;
}
------------- Defs -----------------
def anonymous_0 {	// c1
  int i1 = 1;
}
def d1 {	// c1
  int i1 = 1;
}
def example {
  int i = 1;
  string h = "hello_world";
}

```
讲解：
1. 直接写def加大括号的形式定义一条record是最基础的用法，这样定义好的record就已经是最终形式，展开前后不发生变化
2. class是record模版（或者翻译成类型？），其中可以写一些公共的成员（使用场景比如属于同一类型的指令，操作码往往是相同的，写在class中再用def继承就无需在每个def内部写一遍）
3. def后不接任何Label就生成匿名record，在打印时自动生成anonymous_i的名称，注意这个名称只是在打印时出现，LLVM内部使用时是无名称的。匿名record适合用于不想费心起名字，并且该record之后不会被其它record继承的情况。LLVM使用匿名record不会有任何困难，因为只要这些信息写在一起就表明它们是有联系的。比如InstrAlias模版，其作用是在MCCodeEmit阶段使伪指令打印出来的汇编变成伪指令形式。
```
def : InstAlias<"mv $rd, $rs",   (ADDI GPR:$rd, GPR:$rs,       0)>;
```
```
def anonymous_4962 {	// InstAlias
  string AsmString = "mv $rd, $rs";
  dag ResultInst = (ADDI GPR:$rd, GPR:$rs, 0);
  int EmitPriority = 1;
  list<Predicate> Predicates = [];
  bit UseInstAsmMatchConverter = 1;
  string AsmVariantName = "";
}
```
#### 示例2：使用templated class定义带参数的模版
源码
```
class class_parent <int num_parent, string str_parent = "hello"> {
  int i = num_parent;
  string h = str_parent;
}

def rec1 : class_parent <5>;
def : class_parent <3, "world">;
class class_child<int num_child>:class_parent<num_child, "world">{
 int i = num_child;
}
def rec2 : class_child<8>;
```
输出
```
------------- Classes -----------------
class class_child<int class_child:num_child = ?> {	// class_parent
  int i = class_child:num_child;
  string h = "world";
}
class class_parent<int class_parent:num_parent = ?, string class_parent:str_parent = "hello"> {
  int i = class_parent:num_parent;
  string h = class_parent:str_parent;
}
------------- Defs -----------------
def anonymous_0 {	// class_parent
  int i = 3;
  string h = "world";
}
def rec1 {	// class_parent
  int i = 5;
  string h = "hello";
}
def rec2 {	// class_parent class_child
  int i = 8;
  string h = "world";
}
```
讲解：
1. class使用双尖括号定义参数，在class内部使用形参。一个class可以被另一个class或record使用冒号继承。record继承时传入实参，而class继承时传入子类的形参（对父类来说是实参）
2. 在声明形参时可以使用等号设置参数默认值
#### 示例3：使用multiclass与defm批量定义record
源码     
```
class Instruction<string n> {
  string variant = n;
}
multiclass basic_r {
  def rr: Instruction< "rr">;
  def rm: Instruction<"rm">;
}

defm ADD : basic_r;
defm SUB : basic_r;
```
输出
```
------------- Classes -----------------
class Instruction<string Instruction:n = ?> {
  string variant = Instruction:n;
}
------------- Defs -----------------
def ADDrm {	// Instruction
  string variant = "rm";
}
def ADDrr {	// Instruction
  string variant = "rr";
}
def SUBrm {	// Instruction
  string variant = "rm";
}
def SUBrr {	// Instruction
  string variant = "rr";
}
```
#### 示例4：使用let覆盖一个域

源码

```
class c1 {
  int i = 1;
}

def rec1 : c1 {
  let i = 2;
}

class c {
  int i = 1;
  int j = 2;
  int k = 3;
}

def rec: c;

let i = 2 in
  def rec2: c;

let i = 3, j=6, k=9 in {
  def rec3: c;
  def rec4: c;
}

let i=100 in {
  def rec5: c;
  let j=200 in {
    def rec6: c;
    let k=300 in
      def rec7: c;
  }
}
```

输出

```
------------- Classes -----------------
class c {
  int i = 1;
  int j = 2;
  int k = 3;
}
class c1 {
  int i = 1;
}
------------- Defs -----------------
def rec {	// c
  int i = 1;
  int j = 2;
  int k = 3;
}
def rec1 {	// c1
  int i = 2;
}
def rec2 {	// c
  int i = 2;
  int j = 2;
  int k = 3;
}
def rec3 {	// c
  int i = 3;
  int j = 6;
  int k = 9;
}
def rec4 {	// c
  int i = 3;
  int j = 6;
  int k = 9;
}
def rec5 {	// c
  int i = 100;
  int j = 2;
  int k = 3;
}
def rec6 {	// c
  int i = 100;
  int j = 200;
  int k = 3;
}
def rec7 {	// c
  int i = 100;
  int j = 200;
  int k = 300;
}
```

讲解：

1. let的作用是覆盖一个已经定义过的域，覆盖时必须知道将要覆盖的成员类型，否则赋值时会出错
2. let可以用在花括号内部也可以用在外部，区别是作用域不同。在后一种情况下，可以将多个record再用花括号包括形成一个域，再使用let foo=...覆盖其中每个record或class中名为foo的变量。

## 在LLVM框架中使用TableGen