[游戏开发]CPU架构的llvm后端

Creating an LLVM Backend for the Cpu0 Architecture
Backend structure
? TargetMachine structure
? Add AsmPrinter
? Add Cpu0DAGToDAGISel class
? Handle return register $lr
? Add Prologue/Epilogue functions
o Concept
o Prologue and Epilogue functions
o Handle stack slot for local variables
o Large stack
? Data operands DAGs
? Summary of this Chapter

Fig. 14 Cpu0 backend class access link
图 14 Cpu0 后端类访问链接
添加了大多数 Cpu0 后端类，代码可以概括为图14。类 Cpu0Subtarget 提供接口 getInstrInfo()，getFrameLowering()，…，获取其它 Cpu0 类。大多数类（如 Cpu0InstrInfo，Cpu0RegisterInfo 等），都有 Subtarget 引用成员，允许通过 Cpu0Subtarget 接口，访问其它类。如果后端模块没有 Subtarget 引用，这些类仍然可以通过 static_cast<Cpu0TargetMachine &>?.getSubtargetImpl()，通过 Cpu0TargetMachine（通常使用 TM 作为符号）访问 Subtarget 类。一旦获取到 Subtarget 类，后端代码就可以访问其它类。对于 Cpu0SExx 类的名称，表示标准32 位类。遵循 llvm 3.5 Mips 后端风格。Mips 后端使用 Mips16，MipsSE 和 Mips64 文件/类名称，分别为 16，32 和 64 位架构定义类。
图15显示了 Cpu0 TableGen 的继承关系。后端类可以包含 TableGen 生成的类并从中继承。Cpu0后端的所有TableGen生成的类，都在build/lib/Target/Cpu0/*.inc中。通过 C++ 继承机制，TableGen 为后端程序员，提供了一种灵活的方式，使用生成的代码。如果需要，程序员有机会覆盖此功能。

图 15继承自 TableGen 生成文件的 Cpu0 类
Fig. 15 Cpu0 classes inherited from TableGen generated files
由于llvm有很深的继承树，这里就不深挖了。受益于继承树结构，不需要在指令，帧/堆栈和选择 DAG 类中，实现太多代码，很多代码是由父类实现的。llvm-tblgen 根据Cpu0InstrInfo.td 的信息，生成 Cpu0GenInstrInfo.inc。Cpu0InstrInfo.h 通过定义“#define GET_INSTRINFO_HEADER”，从 Cpu0GenInstrInfo.inc 中，提取需要的代码。使用TabelGen，通过编译器开发的模式匹配理论，减少了后端的代码量。这在 “DAG”和“指令选择”中，都有解释。
To make the registration clearly, summary as the following diagram, Fig. 16.

图 16 Tblgen 为 Cpu0 后端生成文件
Fig. 16 Tblgen generate files for Cpu0 backend
createCpu0MCAsmInfo() 为目标 TheCpu0Target 和 TheCpu0elTarget，注册了类 Cpu0MCAsmInfo 的对象。TheCpu0Target 用于大端，TheCpu0elTarget 用于小端。Cpu0MCAsmInfo 派生自 MCAsmInfo，一个 llvm 内置类。大多数代码在父级中实现，后端通过继承重用这些代码。
createCpu0MCInstrInfo() 实例化 MCInstrInfo 对象X，通过 InitCpu0MCInstrInfo(X) ，进行初始化。由于 InitCpu0MCInstrInfo(X) 是在 Cpu0GenInstrInfo.inc 中定义的，所以这个函数会添加指定的 Cpu0InstrInfo.td 中的信息。
createCpu0MCInstPrinter() 实例化 Cpu0InstPrinter，支持打印功能的说明。
createCpu0MCRegisterInfo()类似于“MC指令信息的注册函数”，初始化了Cpu0RegisterInfo.td中，指定的寄存器信息。共享来自指令/寄存器 td 描述的一些值，如果与 td 描述文件一致，无需在 Initialize 例程中，再次指定。
createCpu0MCSubtargetInfo() 实例化 MCSubtargetInfo 对象，使用 Cpu0.td 信息，进行初始化。
根据“目标注册部分” ，可以通过动态注册机制，在 LLVMInitializeCpu0TargetMC() 按需注册 Cpu0 后端类，如上述函数 LLVMInitializeCpu0TargetMC()。
现在，可以使用 AsmPrinter，如下所示，
Summary above translation into Table: Chapter 3 .bc IR instructions.
Table 10 Chapter 3 .bc IR instructions
以上摘要翻译成表：第 3 章 .bc IR 指令。
表 10第 3 章 .bc IR 指令

? 下层：初始选择 DAG（Cpu0ISelLowering.cpp，LowerReturn(…)）
? ISel：指令选择
? RVR：重写虚拟寄存器，删除 CopyToReg
? AsmP：Cpu0 Asm 打印
? Post-RA：Post-RA 伪指令扩展pass
从上面的llc -print-before-all -print-after-all显示，ret在stage Optimized legalized selection DAG中，翻译成 Cpu0ISD::Ret，最后翻译成Cpu0指令ret。由于 ret 使用常量 0（在此示例中为ret i32 0），因此常量 0通过Cpu0InstrInfo.td 中定义的以下模式，转换为“addiu $2, $zero, 0”。
Cpu0ISelLowering.cpp 的函数LowerReturn() 正确处理返回变量。Chapter3_4/Cpu0ISelLowering.cpp在LowerReturn()中创建Cpu0ISD::Ret节点，当llvm系统遇到C的return关键字时调用。创建 DAG（Cpu0ISD::Ret (CopyToReg %X, %V0, %Y), %V0, Flag）。由于 V0 寄存器，在 CopyToReg 中分配，Cpu0ISD::Ret 使用 V0，带有 V0 寄存器的 CopyToReg，继续存在，不会在任何后续优化步骤中删除。如果使用“return DAG.getNode(Cpu0ISD::Ret, DL, MVT::Other, Chain, DAG.getRegister(Cpu0::LR, MVT::i32));”，不是“返回 DAG.getNode (Cpu0ISD::Ret, DL, MVT::Other, &RetOps[0], RetOps.size());”，V0 寄存器将不会生效，DAG（CopyToReg %X, %V0, %Y）将在以后的优化步骤中删除。
添加序言/尾声功能
概念
以下来自 tricore_llvm.pdf 部分“4.4.2 非静态寄存器信息”。
对于某些目标架构，目标架构的寄存器集的某些方面，取决于可变因素，必须在运行时确定。不能从 TableGen，描述静态生成——尽管在 TriCore 后端，大部分是可能的。有以下几点：
? 调用者保存的寄存器。通常，ABI 指定一组寄存器，如果内容在执行期间可能被修改，函数必须在进入时，保存这些寄存器，在返回时，恢复这些寄存器。
? 保留寄存器。尽管 TableGen 文件中，已经定义了一组不可用的寄存器，TriCoreRegisterInfo 包含一个方法，用于在位向量中，标记所有不可分配的寄存器编号。
实现了以下方法：
? emitPrologue() 在函数的开头，插入序言代码。由于 TriCore 的上下文模型，这是一项微不足道的任务，不需要手动保存任何寄存器。唯一需要做的，通过递减堆栈指针，为函数的堆栈帧保留空间。如果函数需要一个帧指针，帧寄存器 %a14 被预先设置为堆栈指针的旧值。
? emitEpilogue() 旨在发出指令，在从函数返回之前，销毁堆栈帧，恢复所有先前保存的寄存器。由于 %a10（堆栈指针），%a11（返回地址）和 %a14（帧指针，如果有），都是上层上下文的一部分，根本不需要结尾代码。所有清理操作，都由 ret 指令隐式执行。
? 对于引用堆栈槽中，一个数据字的每条指令，都调用消除帧索引（）。代码生成器之前的所有过程，都通过抽象帧索引和立即偏移量，寻址堆栈槽。此函数的目的，将这样的引用转换为寄存器-偏移对。根据包含指令的机器函数，是否具有固定或可变堆栈帧，使用堆栈指针 %a10，或帧指针 %a14，作为基址寄存器。相应计算偏移量。图 17展示了两种情况下，堆栈槽的寻址方式。
如果受影响指令的寻址模式，由于偏移量太大，无法处理该地址（偏移字段对于 BO 寻址模式，有 10 位，对于 BOL 模式，有 16 位），发出一系列指令，显式计算有效地址。临时结果，放入一个未使用的地址寄存器。如果没有可用的，清除已占用的地址寄存器。LLVM 的框架提供了一个名为 RegScavenger 的类，负责处理所有细节。
able 11 Handle return register lr
表 11处理返回寄存器 lr

图 17位于堆栈上的变量 a 的寻址。如果堆栈帧具有可变大小，必须相对于帧指针寻址槽
Fig. 17 Addressing of a variable a located on the stack. If the stack frame has a variable size, slot must be addressed relative to the frame pointer

Table 12 Backend functions called in PrologEpilogInserter.cpp
表 12 PrologEpilogInserter.cpp 中调用的后端函数

File PrologEpilogInserter.cpp includes the calling of backend functions spillCalleeSavedRegisters(), emitProlog(), emitEpilog() and eliminateFrameIndex() as follows,
文件 PrologEpilogInserter.cpp，包括调用后端函数，spillCalleeSavedRegisters(), emitProlog(), emitEpilog() ，eliminateFrameIndex()。
Table 13 Cpu0 stack adjustment instructions before replace addiu and shl with lui instruction

Cpu0AnalyzeImmediate.cpp递归方式编写，逻辑上有点复杂。不过前端编译，用到了递归技巧。不跟踪代码，列出“表：用lui指令替换addiu和shl之前的Cpu0堆栈，调整指令”和“表：用lui指令替换addiu和shl之后的Cpu0堆栈，调整指令”中的堆栈大小和指令。
表13用lui指令，替换addiu和shl前的cpu0栈调整指令。

Table 14 Cpu0 stack adjustment instructions after replace addiu and shl with lui instruction

由于 Cpu0 堆栈是 8 字节对齐，从 0x7ff9 到 0x7fff 的地址，不可能存在的。
假设 sp = 0xa0008000，stack size = 0x90008000, (0xa0008000 - 0x90008000) => 0x10000000。使用 Cpu0 Prologue 说明，进行验证，如下所示，

1. “addiu $1, $zero, -9” => ($1 = 0 + 0xfffffff7) => $1 = 0xfffffff7.
2. “shl $1, $1, 28;” => $1 = 0x70000000.
3. “addiu $1, $1, -32768” => $1 = (0x70000000 + 0xffff8000) => $1 = 0x6fff8000.
4. “addu $sp, $sp, $1” => $sp = (0xa0008000 + 0x6fff8000) => $sp = 0x10000000.
   使用 sp = 0x10000000，堆栈大小stack size = 0x90008000 的 Cpu0 Epilogue 指令，进行验证。
5. “addiu $1, $zero, -28671” => ($1 = 0 + 0xffff9001) => $1 = 0xffff9001.
6. “shl $1, $1, 16;” => $1 = 0x90010000.
7. “addiu $1, $1, -32768” => $1 = (0x90010000 + 0xffff8000) => $1 = 0x90008000.
8. “addu $sp, $sp, $1” => $sp = (0x10000000 + 0x90008000) => $sp = 0xa0008000.
   Cpu0AnalyzeImmediate::GetShortestSeq() ，将调用 Cpu0AnalyzeImmediate:: ReplaceADDiuSHLWithLUi() ，仅用单个指令 lui，替换 addiu 和 shl。
   假设 sp = 0xa0008000 和堆栈大小 = 0x90008000，那么 (0xa0008000 - 0x90008000) => 0x10000000。使用 Cpu0 Prologue 说明进行验证，如下所示，
9. “lui $1, 28671” => $1 = 0x6fff0000。
10. “ori $1, $1, 32768” => $1 = (0x6fff0000 + 0x00008000) => $1 = 0x6fff8000。
11. “addu $sp, $sp, $1” => $sp = (0xa0008000 + 0x6fff8000) => $sp = 0x10000000。
    使用 sp = 0x10000000 和堆栈大小 = 0x90008000 的 Cpu0 Epilogue 指令进行验证，如下所示，
12. “lui $1, 36865” => $1 = 0x90010000。
13. “addiu $1, $1, -32768” => $1 = (0x90010000 + 0xffff8000) => $1 = 0x90008000。
14. “addu $sp, $sp, $1” => $sp = (0x10000000 + 0x90008000) => $sp = 0xa0008000。
    表 15 llvm 后端阶段的函数
    able 15 Functions for llvm backend stages
    

在“添加 Cpu0DAGToDAGISel 类”部分的指令，添加了一个pass。可以将代码嵌入到其它类似的pass中。有关信息，请查看 CodeGen/Passes.h。根据llc -debug-pass=Structure 指示的功能单元，调用pass。
已经完成了一个简单的 cpu0 编译器，只支持ld， st，addiu，ori，lui，addu，shl和ret 8 条指令。
可能会想“在编写了这么多代码之后，只需得到这 8 条指令！”。重点是已经为 Cpu0 目标机，创建了一个框架（llvm 后端结构类继承树）。有超过 3000 行带有注释的源代码，包括文件 .cpp，.h，.td 和 CMakeLists.txt。可以通过命令计数wc find dir -name *.cpp对于文件 .cpp，.h，.td，*.txt。LLVM 前端，总共有 700 行源代码，没有注释。实际上，编写后端是启动缓慢，但运行很快。Clang 在 clang/lib 目录中，有超过 500,000 行，带有注释的源代码，包括 C++ 和 Obj C 支持。llvm 3.1 的 Mips 后端，只有 15,000 行，带有注释。即使是复杂的X86 CPU，外有CISC，内有RISC（微指令），在llvm 3.1中，也只有45000行注释。

Fig. 20 Code generation and execution flow
图20的上半部分，生成和执行计算机程序，工作流程和软件包。IR代表中间表示。中间部分是工作流程。除了clang，其它块都需要扩展，进行新的后端开发（许多后端也扩展clang，Cpu0后端没有这个需求）。实现了黄框部分。该图的绿色部分，用于 Cpu0 后端的 lld 和 elf2hex，可以在http://jonathan2251.github.io/lbt/index.html上找到 。十六进制是 ascii 文件格式，使用“0”到“9”和“a”到“f”，表示十六进制值，因为 Verilog 语言机器，用作输入文件。

参考链接：
http://jonathan2251.github.io/lbd/ctrlflow.html