Kaleidoscope: Code generation to LLVM IR

Posted on Edited on In

Chapter 3 Introduction

本章主要是将 Chapter 2 中构建的抽象语法树 (AST) 转化成 LLVM IR. 这章主要讲述 LLVM 能做哪些工作, 并且告诉你怎么使用.

Note: 这章的代码需要 LLVM 3.7 或更新版.

Code Generation Setup

为了能生成 IR, 我们首先在每个 AST 类中定义一个生成代码的虚方法 (virtual code generation method).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// ExprAST - Base class for all expression nodes
class ExprAST
{
public:
    virtual ~ExprAST(){};
    virtual llvm::Value *codegen() = 0;
};

// NumberExprAST - Expression class for numeric literals like "1.0"
class NumberExprAST : public ExprAST
{
    double Val;

public:
    NumberExprAST(double Val) : Val(Val) {}
    virtual llvm::Value *codegen();
};

codegen() 方法会根据每个不同的类生成 IR, 都返回一个 class Value 对象的指针. class Value 表示 LLVM 中的一个 SSA (Static Single Assignment) register 或者 SSA value. SSA 表示每个变量都只能被赋值一次, 而且必须在使用前被定义.

同时我们添加一个 LogError() 方法来记录生成 IR 时的错误:

1
2
3
4
llvm::Value *LogErrorV(const char *Str) {
    LogError(Str);
    return nullptr;
}

并声明可能需要的静态变量:

1
2
3
4
static llvm::LLVMContext TheContext;
static llvm::IRBuilder<> Builder{TheContext};
static std::unique_ptr<llvm::Module> TheModule;
static std::map<std::string, llvm::Value *> NamedValues;

LLVMContext TheContext 是一个包含大量 LLVM 核心数据结构的对象, 比如包含类型和常量表 (the type and constant value tables). IRBuilder Builder 是一个辅助对象, 能简化 LLVM 指令的生成. 这个对象能够追踪当前需要插入指令的位置, 并有创建新指令的方法. class Module 的实例用来存储和 一个LLVM module 相关的所有信息. 在 LLVM 中, 一个 Module 表示能被处理的单个代码单元 (a single unit of code that is to be processed together), 差不多就是一个源代码文件. TheModule 会拥有我们生成所有 IR 的内存, 这就是我们申明 codegen() 时, 让它返回裸指针 Value * 而不是 unique_ptr<Value> 的原因. map<string, Value *> NamedValues 主要追踪当前作用域内定义的值, 和它们的 LLVM representation. 换句话说 NamedValues 就是一个符号表 (symbol table for the code). 目前在 Kaleidoscope 中, 只有函数参数能被引用, 所以当生成函数体里面的代码时, 我们就会用到存储在它里面的函数参数.

我们现在假设 IRBuilder Builder 已经被设置好可以生成代码.

Expression Code Generation

为表达式节点生成 LLVM code 非常直接, 直接调用相应的函数即可, 首先是对数字常量表达式的代码生成:

1
2
3
llvm::Value *NumberExprAST::codegen() {
    return llvm::ConstantFP::get(TheContext, llvm::APFloat(Val));
}

在 LLVM IR 中, 字面常量是用 class ConstantFP 表示的, 字面常量的值由 class APFloat 持有, 即后者是前者的一个成员变量 (AP 表示 Arbitrary Precision). 然后是变量表达式的 codegen():

1
2
3
4
5
6
7
llvm::Value *VariableExprAST::codegen() {
    llvm::Value *V = NamedValues[Name];
    if (!V) {
        LogErrorV("Unknown variable name");
    }
    return V;
}

目前针对变量的引用只有在函数体内才有, 所以我们先检查被引用的变量名是否在 map<string, Value*> NamedValues 中, 然后直接返回它的值即可. 在教程后面我们会加上对循环变量和局部变量的支持 (loop induction variables and local variables).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
llvm::Value *BinaryExprAST::codegen() {
    llvm::Value *L = LHS -> codegen();
    llvm::Value *R = RHS -> codegen();
    if (!L || !R){
        return nullptr;
    }

    switch (Op)
    {
    case '+':
        return Builder.CreateFAdd(L, R, "addtmp");
    case '-':
        return Builder.CreateFSub(L, R, "subtmp");
    case '*':
        return Builder.CreateFMul(L, R, "multmp");
    case '<':
        L = Builder.CreateFCmpULT(L, R, "cmptmp");
        // Convert bool 0/1 to double 0.0 or 1.0
        return Builder.CreateUIToFP(L, llvm::Type::getDoubleTy(TheContext), "booltmp");
    default:
        return LogErrorV("invalid binary operator");
    }
}

二元操作符表达式也是递归进行操作, 左表达式先进行代码生成, 然后是右表达式, 然后生成二元操作符表达式的代码. 在上述代码中, class IRBuilder 调用自己的成员方法, 例如 CreateFAdd(), 通过传入的参数来生成新的指令. 在 CreateFAdd() 方法中传入的名字仅仅只是一个提示, 如果上面的代码生成函数有多个 CreateFAdd(L, R, "addtmp"), 那么 LLVM 会自动给每个都加上一个唯一的后缀.

LLVM 指令是被严格约束的: 对于加法指令, 左操作数和右操作数必须是相同类型, 且结果的类型和操作数的类型必须相同. Kaleidoscope 中的所有值都是 double, 所以这里不需要考虑类型.

并且, 在 LLVM 文档中, fcmp 指令返回的是 1个 bit 的整数 i1. 我们的数据类型中没有整数, 所以我们要转化为 0.0 或者 1.0. 所有我们使用 uitofp 指令, 它将第一个参数视为无符号的整数类型， 并把它转化为第二个参数表示的浮点类型 (double). 同时 sitofp 指令也可以完成类似的功能, 不过它是把第一个参数视为有符号的整数类型.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
llvm::Value *CallExprAST::codegen() {
    // Lookup the name in the global module table
    llvm::Function *CalleeF = TheModule -> getFunction(Callee);
    if (!CalleeF) {
        LogErrorV("Unknown function referenced");
    }

    // Argument checking
    if (CalleeF -> arg_size() != Args.size()) {
        return LogErrorV("Incorrect number of arguments passed");
    }

    std::vector<llvm::Value *> ArgsV;
    for (unsigned i = 0, e = Args.size(); i != e; ++i) {
        ArgsV.push_back(Args[i] -> codegen());
        if (!ArgsV.back()) {
            return nullptr;
        }
    }

    return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
}

函数调用的代码生成也是很直接的, 首先在 LLVM Module 的符号表里面查找这个函数名. LLVM Module 是用来持有函数的容器, 并且通过解析 Module 的符号表, 我们就能引用这些函数.

一旦我们找到函数之后, 就检查它在符号表中的参数数量和实际获取的参数数量是否一致. 并且递归的解析传给它的每个参数. 然后就能创建一个 LLVM call 指令.

Function Code Generation

对函数原型和函数定义的代码生成包含不少细节, 不像上面表达式生成代码时那么直观和简洁. 但是我们同时也能看到一些比较重要的概念. 下面是函数原型的代码生成:

1
2
3
4
5
llvm::Function *PrototypeAST::codegen() {
    // Make the function prototype: double(double, double).
    std::vector<llvm::Type *> Doubles(Args.size(), llvm::Type::getDoubleTy(TheContext));
    llvm::FunctionType *FT = llvm::FunctionType::get(llvm::Type::getDoubleTy(TheContext), Doubles, false);
    llvm::Function *F = llvm::Function::Create(FT, llvm::Function::ExternalLinkage, Name, TheModule.get());

这部分的代码包含了很多重要内容. 首先 Function *PrototypeAST::codegen() 返回值的类型是 Function * 而不是 Value *, 因为一个函数原型主要是表示函数的外部接口, 而不是像表达式一样能被计算出值. 对 FunctionType::get() 的调用可以得到函数类型, 第一个参数是返回值类型, 第二个参数是参数类型的列表, 第三个是是否支持可变参数列表.

最后一行就是实际生成 IR 代码的一行, Function::Create() 的参数分别为函数类型, Linkage 类型 (一般熟知的有 external linkage 和 internal linkage, 分别表示能被外部 translation unit (Module) 访问和不能. 例如 c/c++ 关键字 extern 和 static), 函数名, 和 TheModule. 在之前版本的 LLVM 文档中, 直接传了 TheModule (unique_ptr) 而不是 TheModule.get(), 会造成编译器错误.

1
2
3
4
5
6
7
8
    // Set names for all arguments
    unsigned Idx = 0;
    for (auto &Arg: F -> args()) {
        Arg.setName(Args[Idx++]);
    }

    return F;
}

然后根据函数原型的参数名字, 给 IR 的参数命名, 增加 IR 生成之后的可读性, 并且后续操作中, 能直接根据参数名对参数进行引用, 不需要再到函数原型的 AST 节点中查找.

然后就是函数定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
llvm::Function *FunctionAST::codegen() {
    // Check for an existing function from a previous `extern` declaration
    llvm::Function *TheFunction = TheModule -> getFunction(Proto -> getName());

    if (!TheFunction) {
        TheFunction = Proto -> codegen();
    }

    if (!TheFunction) {
        return nullptr;
    }

    if (!TheFunction -> empty()) {
        return (llvm::Function *)LogErrorV("Function cannot be redefined");
    }

对于函数定义, 我们首先查找 TheModule 的符号表, 看看有没有匹配的函数名. 这样就可以看出这个函数有没有使用 extern 的前向声明. 如果没有声明, 那么我们就生成函数原型的代码. 并且, 我们断言这个时候函数体是没有生成代码的, 也就是说我们这次定义并不是重复定义.

1
2
3
4
5
6
7
8
9
// Create a new Basic Block to start insertion into.
llvm::BasicBlock *BB = llvm::BasicBlock::Create(TheContext, "entry", TheFunction);
Builder.SetInsertPoint(BB);

// Record the function arguments in the NamedValues map.
NamedValues.clear();
for (auto &Arg : TheFunction -> args()) {
    NamedValues[Arg.getName()] = &Arg;
}

第一行创建了一个新的 basic block, 并把它插入到 TheFunction 中. 第二行就告诉 Builder, 新的指令应该被插入到这个 basic block 的末尾. Basic block 定义了 LLVM 中的控制流图 (Control flow graph). 虽然我们现在没有控制流, 但在 Chapter 5 会加上.

然后就是将函数参数添加到 map<string, Value *> NamedValues, 这样 VariableExprAST 的节点就能在函数定义里面来引用它们.

1
2
3
4
5
6
7
8
9
10
11
12
    if (llvm::Value *RetVal = Body -> codegen()) {
        // Finish off the function
        Builder.CreateRet(RetVal);
        // Validate the generated code, checking for consistency
        llvm::verifyFunction(*TheFunction);

        return TheFunction;
    }

    TheFunction -> eraseFromParent();
    return nullptr;
}

一旦代码的插入点被设置完毕, 我们就调用函数体的 codegen() 方法, 如果没有错误发生的话, 它就会将生成函数体里面表达式的代码, 然后将这些代码插入到上面定义的 entry basic block 中, 然后返回这些表达式计算出来的值. 接着创建 ret 指令完成函数. 生成完毕后使用 verifyFunction() 来检查生成代码的一致性. 如果生成函数体代码失败, 那就调用 eraseFromParent() 删除生成的函数.

但是这部分的代码也有问题, 如果 FunctionAST::codegen() 方法已经找到一个存在的函数声明, 那么它就跳过了函数原型代码的生成, 就导致跳过了对参数名的设置, 所以当前向声明中的参数名和函数定义使用的参数名不一致时, 会发生错误:

1
2
extern foo(a);   # ok, declare foo
def foo(b);      # Error: Unknown variable name

Driver changes and Closing Thoughts

主要就是在 main() 和相应的 HandleDefinition() 之类的函数中， 相应的更改用 preprocess macro 做了判断, 直接看代码即可.