采用LLVM构建语言编译器

作者 Lucyyang 日期 2020-03-14
CS
采用LLVM构建语言编译器

千里之行,始于足下

整体逻辑

Parser->AST->Codegen->IR 代码->pass 进行优化

生成LLVM IR

之前的Parser和AST无需依赖于LLVM的支持,但要生成IR的中间代码,必须从加入LLVM的支持。

具体流程如下: 首先在AST的子类中添加Codegen()函数

/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() {}
virtual Value *codegen() = 0;
};

申明三个重要的全局变量:

static Module Module_Ob;
static IRBuilder<> Builder(getGlobalContext());
static std::map<std::string, Value> Named_values;

其中Module_Ob模块包含了代码中所有的函数和变量;Builder对象用于帮助生成LLVM IR并且记录程序的当前点,用以插入LLVM指令;Named_Values记录当前作用域的定义值,方便查找。

接下来对每个不同类型分别定义代码生成函数,首先

由于Codegen()调用了LLVM内建的函数来生成IR,因此需要引入这些头文件: llvm/IR/Verifier.h, llvm/IR/DerivedTypes.h 。在编译的时候,也需要将这些代码链接到LLVM库中,因此使用llvm-config工具:

llvm-config --cxxflags --ldflags --system-libs --libs core

加入JIT和优化支持

Pass

介绍了如何加入JIT编译器支持和优化支持。

IR builder可以生成中间逻辑代码,对简单的常量加减直接进行优化,但是无法对更复杂的逻辑进行优化。

LLVM 提供了很多passes,可以看作是优化器。Passes作用与LLVM IR,进行分析和优化,一般采用一个FunctionPassManager进行管理需要的passes。

JIT

JIT:Just-In-Time,即时编译,在程序运行时将代码翻译成机器码并执行。与之相对的是AOT(Ahead Of Time), 它在程序运行之前就将代码编译成机器码。JIT结合了AOT和解释执行的优势,能够产生高效的机器码,有较好灵活性。例如,输入1+2时,会自动返回3。

实现步骤:

  • 在代码中定义一个执行引擎作为全局变量
  • 在main()中加入JIT初始化代码
  • 修改顶级表达式的解析器,将执行引擎作用在解析后生成的IR代码上

加入条件语句与循环

从加入条件语句和循环中,我们可以看到如何给自己的语句增加更多的功能。

条件语句

具体流程:

  1. 首先增加if/else/then的token

// control
tok_if = -6,
tok_then = -7,
tok_else = -8,

并在gettok函数中,加入对应的分支:

if (IdentifierStr == "def")
return tok_def;
if (IdentifierStr == "extern")
return tok_extern;
if (IdentifierStr == "if")
return tok_if;
if (IdentifierStr == "then")
return tok_then;
if (IdentifierStr == "else")
return tok_else;
return tok_identifier;

  1. 加入对应的AST的节点

    // 增加选择分支的AST节点
    /// IfExprAST - Expression class for if/then/else.
    class IfExprAST : public ExprAST {
    std::unique_ptr<ExprAST> Cond, Then, Else;
    public:
    IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then,
    std::unique_ptr<ExprAST> Else)
    : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {}
    Value *codegen() override;
    };

  2. 为条件语句扩展parser函数 加入ParseIfExpr()函数,函数中根据Cond->Then->Else的顺序check分支是否完整。

  3. 为条件语句的AST添加codegen函数

条件语句的LLVM IR目标代码如下:

declare double @foo()
declare double @bar()
define double @baz(double %x) {
entry:
%ifcond = fcmp one double %x, 0.000000e+00
br i1 %ifcond, label %then, label %else
then: ; preds = %entry
%calltmp = call double @foo()
br label %ifcont
else: ; preds = %entry
%calltmp1 = call double @bar()
br label %ifcont
ifcont: ; preds = %else, %then
%iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
ret double %iftmp
}

完成前端的解析后,即可加入LLVM IR的代码生成支持。在生成分支代码的时候存在一个问题:条件语句之后的代码模块怎么知道是哪个分支返回的结果?其实是采用了Phi指令,简单来讲就是Phi指令需要记住是哪个代码模块返回的结果。

了解之后,我们来看具体代码,首先是给条件分支的AST节点IfExprAST加入codegen函数生成代码:

Value *IfExprAST::codegen() {
Value *CondV = Cond->codegen();
if (!CondV)
return nullptr;
// Convert condition to a bool by comparing non-equal to 0.0.
CondV = Builder.CreateFCmpONE(
CondV, ConstantFP::get(TheContext, APFloat(0.0)), "ifcond");

类似的,分别再生成Then, Else的代码。

  1. 生成LLVM IR中间代码 TODO: 具体细节

给TOY语言加入分支判断功能的方法总结如下:构建相应的token,AST表达式与解析器,之后代码生成器将AST转成LLVM IR,全部的条件语句也随之生成。

循环语句

我们希望TOY语言实现类似的循环功能:

extern putchard(char);
def printstar(n)
for i = 1, i < n, 1.0 in
putchard(42); # ascii 42 = '*'

循环语句的增加和流程相似:

  1. 增加token和AST节点
  2. 针对循环的AST节点加入解析器,写法非常直接,按照顺序一一进行检查:
    /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
    static std::unique_ptr<ExprAST> ParseForExpr() {
    getNextToken(); // eat the for.
    if (CurTok != tok_identifier)
    return LogError("expected identifier after for");
    std::string IdName = IdentifierStr;
    getNextToken(); // eat identifier.
    if (CurTok != '=')
    return LogError("expected '=' after for");
    getNextToken(); // eat '='.
    auto Start = ParseExpression();
    if (!Start)
    return nullptr;
    if (CurTok != ',')
    return LogError("expected ',' after for start value");
    getNextToken();
    auto End = ParseExpression();
    if (!End)
    return nullptr;
    // The step value is optional.
    std::unique_ptr<ExprAST> Step;
    if (CurTok == ',') {
    getNextToken();
    Step = ParseExpression();
    if (!Step)
    return nullptr;
    }
    if (CurTok != tok_in)
    return LogError("expected 'in' after for");
    getNextToken(); // eat 'in'.
    auto Body = ParseExpression();
    if (!Body)
    return nullptr;
    return std::make_unique<ForExprAST>(IdName, std::move(Start),
    std::move(End), std::move(Step),
    std::move(Body));
    }

接下来要生成LLVM IR代码,循环结构的目标代码样式如下:

declare double @putchard(double)
define double @printstar(double %n) {
entry:
; initial value = 1.0 (inlined into phi)
br label %loop
loop: ; preds = %loop, %entry
%i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
; body
%calltmp = call double @putchard(double 4.200000e+01)
; increment
%nextvar = fadd double %i, 1.000000e+00
; termination test
%cmptmp = fcmp ult double %i, %n
%booltmp = uitofp i1 %cmptmp to double
%loopcond = fcmp one double %booltmp, 0.000000e+00
br i1 %loopcond, label %loop, label %afterloop
afterloop: ; preds = %loop
; loop always returns 0.0
ret double 0.000000e+00
}

  1. 接下来插入codegen生成LLVM IR代码,分别加入Loop, Step, End, After, Body的Builder代码

LLVM用phi指令判断变量具体来自的基本块(不同分支路径),例如在循环中,%entry模块对i进行初始化赋值,%$loop模块对i进行更新。

生成后端代码

LLVM可以通过选择内置的架构生成后端代码,也可以自己写目标文件,对架构进行描述。

为了得到需要的后端代码,编译器需要知道目标平台的各个方面——寄存器、指令集、调用约定、流水线等,因此可以做很多优化。LLVM通过tablegen来定义目标机器,它包含了目标架构的寄存器、指令集、调用约定等。主要步骤如下:LLVM IR->SelectionDAG->MachineDAG->MachineInstr->MCInst。

  1. 通过.td文件定义寄存器和寄存器集合,之后通过tablegen函数将.td文件转为.inc文件,并在.cpp文件中引入进行应用。
  2. 定义调用约定,指值如何传递给函数以及如何从函数返回,即传递参数约定和返回值约定。其中传递参数约定指的是通过栈还是通过寄存器传递,如果是寄存器则通过哪个寄存器来传递;返回值传递指通过哪个寄存器返回。
  3. 定义指令集,指令目标描述文件定义了3样内容:操作数,汇编字符串,指令格式。
  4. Emit Object Code