3. Kaleidoscope: 代码生成到 LLVM IR¶
3.1. 第 3 章 导言¶
欢迎来到“使用 LLVM 实现语言”教程的第 3 章。本章向您展示如何将第 2 章中构建的 抽象语法树 转换为 LLVM IR。这将教您一些关于 LLVM 如何工作的基础知识，并演示其易用性。构建词法分析器和解析器比生成 LLVM IR 代码要付出更多的工作。:)
请注意：本章及后续章节的代码需要 LLVM 3.7 或更高版本。LLVM 3.6 及更早版本将无法使用。另请注意，您需要使用与您的 LLVM 版本匹配的本教程版本：如果您使用的是 LLVM 官方版本，请使用您的版本或 llvm.org 发布页面 中包含的文档版本。
3.2. 代码生成设置¶
为了生成 LLVM IR，我们希望进行一些简单的设置以开始。首先，我们在每个 AST 类中定义虚拟代码生成 (codegen) 方法
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() = default;
virtual Value *codegen() = 0;
};
/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
double Val;
public:
NumberExprAST(double Val) : Val(Val) {}
Value *codegen() override;
};
...
codegen() 方法表示为该 AST 节点及其所有依赖项发出 IR，并且它们都返回一个 LLVM Value 对象。“Value”是用于表示 LLVM 中的“静态单赋值 (SSA) 寄存器”或“SSA 值”的类。SSA 值最明显的方面是它们的值是在相关指令执行时计算出来的，并且在指令重新执行之前（以及如果重新执行）不会获得新值。换句话说，没有办法“更改”SSA 值。有关更多信息，请阅读 静态单赋值 - 一旦您理解了它们，这些概念实际上非常自然。
请注意，除了向 ExprAST 类层次结构添加虚方法之外，使用 访问者模式 或其他方式来建模也是有意义的。同样，本教程不会赘述良好的软件工程实践：对于我们的目的而言，添加虚方法是最简单的。
我们需要的第二件事是像我们在解析器中使用的“LogError”方法，它将用于报告代码生成期间发现的错误（例如，使用未声明的参数）
static std::unique_ptr<LLVMContext> TheContext;
static std::unique_ptr<IRBuilder<>> Builder;
static std::unique_ptr<Module> TheModule;
static std::map<std::string, Value *> NamedValues;
Value *LogErrorV(const char *Str) {
LogError(Str);
return nullptr;
}
静态变量将在代码生成期间使用。TheContext 是一个不透明的对象，它拥有许多核心 LLVM 数据结构，例如类型和常量值表。我们不需要详细了解它，我们只需要一个实例传递给需要它的 API。
Builder 对象是一个辅助对象，它可以轻松生成 LLVM 指令。IRBuilder 类模板的实例跟踪当前插入指令的位置，并具有创建新指令的方法。
TheModule 是一个 LLVM 构造，其中包含函数和全局变量。在许多方面，它是 LLVM IR 用于包含代码的顶层结构。它将拥有我们生成的所有 IR 的内存，这就是 codegen() 方法返回原始 Value* 而不是 unique_ptr<Value> 的原因。
NamedValues 映射跟踪当前作用域中定义了哪些值以及它们的 LLVM 表示形式是什么。（换句话说，它是代码的符号表）。在这种形式的 Kaleidoscope 中，唯一可以引用的东西是函数参数。因此，在为其函数体生成代码时，函数参数将在此映射中。
有了这些基础知识，我们可以开始讨论如何为每个表达式生成代码。请注意，这假设 Builder 已设置为将代码生成到某些东西中。目前，我们假设这已经完成，我们将仅使用它来发出代码。
3.3. 表达式代码生成¶
为表达式节点生成 LLVM 代码非常简单：对于我们所有的四个表达式节点，注释代码少于 45 行。首先，我们将处理数字字面量
Value *NumberExprAST::codegen() {
return ConstantFP::get(*TheContext, APFloat(Val));
}
在 LLVM IR 中，数字常量由 ConstantFP 类表示，该类在内部保存 APFloat 中的数值（APFloat 具有保存任意精度的浮点常量的能力）。此代码基本上只是创建并返回一个 ConstantFP。请注意，在 LLVM IR 中，常量都是唯一化并共享的。因此，API 使用 “foo::get(…)” 惯用法而不是 “new foo(..)” 或 “foo::Create(..)”。
Value *VariableExprAST::codegen() {
// Look this variable up in the function.
Value *V = NamedValues[Name];
if (!V)
LogErrorV("Unknown variable name");
return V;
}
使用 LLVM 引用变量也非常简单。在 Kaleidoscope 的简单版本中，我们假设变量已经某处发出，并且它的值是可用的。实际上，NamedValues 映射中唯一可以存在的值是函数参数。此代码只是检查指定的名称是否在映射中（如果不在，则正在引用未知变量）并返回其值。在后续章节中，我们将添加对符号表中的循环归纳变量和局部变量的支持。
Value *BinaryExprAST::codegen() {
Value *L = LHS->codegen();
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, Type::getDoubleTy(*TheContext),
"booltmp");
default:
return LogErrorV("invalid binary operator");
}
}
二元运算符开始变得更有趣。这里的基本思想是，我们递归地为表达式的左侧发出代码，然后为右侧发出代码，然后计算二元表达式的结果。在此代码中，我们对操作码进行简单的 switch，以创建正确的 LLVM 指令。
在上面的示例中，LLVM builder 类开始显示其价值。IRBuilder 知道在哪里插入新创建的指令，您只需指定要创建的指令（例如使用 CreateFAdd），要使用的操作数（这里的 L 和 R），并可选择为生成的指令提供名称。
关于 LLVM 的一件好事是，名称只是一个提示。例如，如果上面的代码发出多个 “addtmp” 变量，LLVM 将自动为每个变量提供一个递增的、唯一的数字后缀。指令的局部值名称是纯粹可选的，但它使读取 IR 转储文件更加容易。
LLVM 指令受到严格规则的约束：例如，add 指令的左操作数和右操作数必须具有相同的类型，并且 add 的结果类型必须与操作数类型匹配。由于 Kaleidoscope 中的所有值都是双精度浮点数，因此 add、sub 和 mul 的代码非常简单。
另一方面，LLVM 规定 fcmp 指令始终返回一个 ‘i1’ 值（一个比特的整数）。问题是 Kaleidoscope 希望该值为 0.0 或 1.0 值。为了获得这些语义，我们将 fcmp 指令与 uitofp 指令结合使用。此指令通过将输入视为无符号值，将其输入整数转换为浮点值。相比之下，如果我们使用 sitofp 指令，Kaleidoscope 的 ‘<’ 运算符将返回 0.0 和 -1.0，具体取决于输入值。
Value *CallExprAST::codegen() {
// Look up the name in the global module table.
Function *CalleeF = TheModule->getFunction(Callee);
if (!CalleeF)
return LogErrorV("Unknown function referenced");
// If argument mismatch error.
if (CalleeF->arg_size() != Args.size())
return LogErrorV("Incorrect # arguments passed");
std::vector<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 来说非常简单。上面的代码最初在 LLVM Module 的符号表中执行函数名称查找。回想一下，LLVM Module 是保存我们 JIT 编译的函数的容器。通过为每个函数提供与用户指定的名称相同的名称，我们可以使用 LLVM 符号表来为我们解析函数名称。
一旦我们有了要调用的函数，我们就递归地为要传入的每个参数生成代码，并创建一个 LLVM call 指令。请注意，LLVM 默认使用本机 C 调用约定，允许这些调用也调用到 “sin” 和 “cos” 等标准库函数，而无需额外的努力。
这总结了我们目前在 Kaleidoscope 中处理的四个基本表达式。随意进去并添加更多。例如，通过浏览 LLVM 语言参考，您会发现一些其他有趣的指令，这些指令非常容易插入到我们的基本框架中。
3.4. 函数代码生成¶
原型和函数的代码生成必须处理许多细节，这使得它们的代码不如表达式代码生成那么美观，但允许我们说明一些重要的点。首先，让我们讨论原型的代码生成：它们既用于函数体，也用于外部函数声明。代码从以下内容开始
Function *PrototypeAST::codegen() {
// Make the function type: double(double,double) etc.
std::vector<Type*> Doubles(Args.size(),
Type::getDoubleTy(*TheContext));
FunctionType *FT =
FunctionType::get(Type::getDoubleTy(*TheContext), Doubles, false);
Function *F =
Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());
这段代码将许多功能打包成几行。首先请注意，此函数返回 “Function*” 而不是 “Value*”。由于“原型”实际上是关于函数的外部接口（而不是表达式计算的值），因此当 codegen 时，它返回它对应的 LLVM 函数是有意义的。
调用 FunctionType::get 创建了应用于给定 Prototype 的 FunctionType。由于 Kaleidoscope 中的所有函数参数都是 double 类型，因此第一行创建了一个包含 “N” 个 LLVM double 类型的向量。然后，它使用 Functiontype::get 方法创建一个函数类型，该类型接受 “N” 个 double 作为参数，返回一个 double 作为结果，并且不是变参函数（false 参数表示这一点）。请注意，LLVM 中的类型与常量一样是唯一化的，因此您不会 “new” 一个类型，而是 “get” 它。
上面的最后一行实际上创建了与 Prototype 对应的 IR 函数。这指示要使用的类型、链接和名称，以及要插入的模块。“外部链接”意味着该函数可能在当前模块外部定义，和/或可以被模块外部的函数调用。传入的 Name 是用户指定的名称：由于指定了 “TheModule”，因此该名称已在 “TheModule” 的符号表中注册。
// Set names for all arguments.
unsigned Idx = 0;
for (auto &Arg : F->args())
Arg.setName(Args[Idx++]);
return F;
最后，我们根据 Prototype 中给出的名称设置每个函数参数的名称。此步骤不是绝对必要的，但是保持名称一致性使 IR 更具可读性，并允许后续代码直接引用参数的名称，而无需在 Prototype AST 中查找它们。
此时，我们有一个没有函数体的函数原型。这就是 LLVM IR 表示函数声明的方式。对于 Kaleidoscope 中的 extern 语句，这就是我们需要做的全部。但是对于函数定义，我们需要生成代码并附加函数体。
Function *FunctionAST::codegen() {
// First, check for an existing function from a previous 'extern' declaration.
Function *TheFunction = TheModule->getFunction(Proto->getName());
if (!TheFunction)
TheFunction = Proto->codegen();
if (!TheFunction)
return nullptr;
if (!TheFunction->empty())
return (Function*)LogErrorV("Function cannot be redefined.");
对于函数定义，我们首先在 TheModule 的符号表中搜索此函数的现有版本，以防已使用 ‘extern’ 语句创建了一个版本。如果 Module::getFunction 返回 null，则表示不存在之前的版本，因此我们将从 Prototype 生成一个版本。无论哪种情况，我们都希望在开始之前断言该函数为空（即，尚未包含函数体）。
// Create a new basic block to start insertion into.
BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);
Builder->SetInsertPoint(BB);
// Record the function arguments in the NamedValues map.
NamedValues.clear();
for (auto &Arg : TheFunction->args())
NamedValues[std::string(Arg.getName())] = &Arg;
现在我们进入了设置 Builder 的阶段。第一行创建一个新的基本块（名为 “entry”），它被插入到 TheFunction 中。第二行然后告诉 builder 新指令应该插入到新基本块的末尾。LLVM 中的基本块是函数的重要组成部分，它们定义了控制流图。由于我们没有任何控制流，因此我们的函数此时仅包含一个块。我们将在第 5 章中修复此问题:)。
接下来，我们将函数参数添加到 NamedValues 映射中（在首先清除它之后），以便 VariableExprAST 节点可以访问它们。
if (Value *RetVal = Body->codegen()) {
// Finish off the function.
Builder->CreateRet(RetVal);
// Validate the generated code, checking for consistency.
verifyFunction(*TheFunction);
return TheFunction;
}
一旦设置了插入点并填充了 NamedValues 映射，我们就为函数的根表达式调用 codegen() 方法。如果没有发生错误，这将发出代码以将表达式计算到入口块中，并返回计算出的值。假设没有错误，我们然后创建一个 LLVM ret 指令，它完成该函数。构建函数后，我们调用 LLVM 提供的 verifyFunction。此函数对生成的代码进行各种一致性检查，以确定我们的编译器是否一切正常。使用它非常重要：它可以捕获许多错误。函数完成并验证后，我们将其返回。
// Error reading body, remove function.
TheFunction->eraseFromParent();
return nullptr;
}
这里剩下的唯一部分是处理错误情况。为了简单起见，我们仅通过使用 eraseFromParent 方法删除我们生成的函数来处理此问题。这允许用户重新定义他们之前错误输入的函数：如果我们不删除它，它将存在于符号表中，带有函数体，从而阻止将来的重新定义。
但是，此代码确实存在一个错误：如果 FunctionAST::codegen() 方法找到现有的 IR 函数，则它不会根据定义的原型验证其签名。这意味着早期的 ‘extern’ 声明将优先于函数定义的签名，这可能会导致代码生成失败，例如，如果函数参数的名称不同。有很多方法可以修复此错误，看看您能想出什么！这是一个测试用例
extern foo(a); # ok, defines foo.
def foo(b) b; # Error: Unknown variable name. (decl using 'a' takes precedence).
3.5. 驱动程序更改和结束语¶
目前，代码生成到 LLVM 实际上并没有给我们带来太多好处，除了我们可以查看漂亮的 IR 调用。示例代码将对 codegen 的调用插入到 “HandleDefinition”、“HandleExtern” 等函数中，然后转储出 LLVM IR。这提供了一种很好的方法来查看简单函数的 LLVM IR。例如
ready> 4+5;
Read top-level expression:
define double @0() {
entry:
ret double 9.000000e+00
}
请注意解析器如何为我们把顶层表达式转换为匿名函数。当我们添加JIT 支持在下一章时，这将非常方便。另请注意，代码被非常字面地转录，除了 IRBuilder 完成的简单常量折叠之外，没有执行任何优化。我们将在下一章中显式地添加优化。
ready> def foo(a b) a*a + 2*a*b + b*b;
Read function definition:
define double @foo(double %a, double %b) {
entry:
%multmp = fmul double %a, %a
%multmp1 = fmul double 2.000000e+00, %a
%multmp2 = fmul double %multmp1, %b
%addtmp = fadd double %multmp, %multmp2
%multmp3 = fmul double %b, %b
%addtmp4 = fadd double %addtmp, %multmp3
ret double %addtmp4
}
这显示了一些简单的算术运算。请注意它与我们用于创建指令的 LLVM builder 调用的惊人相似性。
ready> def bar(a) foo(a, 4.0) + bar(31337);
Read function definition:
define double @bar(double %a) {
entry:
%calltmp = call double @foo(double %a, double 4.000000e+00)
%calltmp1 = call double @bar(double 3.133700e+04)
%addtmp = fadd double %calltmp, %calltmp1
ret double %addtmp
}
这显示了一些函数调用。请注意，如果您调用此函数，它将花费很长时间才能执行。将来，我们将添加条件控制流，以使递归真正有用:)。
ready> extern cos(x);
Read extern:
declare double @cos(double)
ready> cos(1.234);
Read top-level expression:
define double @1() {
entry:
%calltmp = call double @cos(double 1.234000e+00)
ret double %calltmp
}
这显示了 libm “cos” 函数的 extern 声明以及对其的调用。
ready> ^D
; ModuleID = 'my cool jit'
define double @0() {
entry:
%addtmp = fadd double 4.000000e+00, 5.000000e+00
ret double %addtmp
}
define double @foo(double %a, double %b) {
entry:
%multmp = fmul double %a, %a
%multmp1 = fmul double 2.000000e+00, %a
%multmp2 = fmul double %multmp1, %b
%addtmp = fadd double %multmp, %multmp2
%multmp3 = fmul double %b, %b
%addtmp4 = fadd double %addtmp, %multmp3
ret double %addtmp4
}
define double @bar(double %a) {
entry:
%calltmp = call double @foo(double %a, double 4.000000e+00)
%calltmp1 = call double @bar(double 3.133700e+04)
%addtmp = fadd double %calltmp, %calltmp1
ret double %addtmp
}
declare double @cos(double)
define double @1() {
entry:
%calltmp = call double @cos(double 1.234000e+00)
ret double %calltmp
}
当您退出当前演示时（通过在 Linux 上发送 EOF（CTRL+D）或在 Windows 上发送 CTRL+Z 和 ENTER），它会转储出为整个模块生成的 IR。在这里，您可以看到所有函数相互引用的大局。
这总结了 Kaleidoscope 教程的第三章。接下来，我们将介绍如何添加 JIT 代码生成和优化器支持到此，以便我们实际上可以开始运行代码！
3.6. 完整代码清单¶
这是我们正在运行的示例的完整代码清单，其中增强了 LLVM 代码生成器。由于这使用了 LLVM 库，我们需要将它们链接进来。为此，我们使用 llvm-config 工具来告知我们的 makefile/命令行要使用的选项
# Compile
clang++ -g -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -o toy
# Run
./toy
这是代码
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Verifier.h"
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <vector>
using namespace llvm;
//===----------------------------------------------------------------------===//
// Lexer
//===----------------------------------------------------------------------===//
// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
// of these for known things.
enum Token {
tok_eof = -1,
// commands
tok_def = -2,
tok_extern = -3,
// primary
tok_identifier = -4,
tok_number = -5
};
static std::string IdentifierStr; // Filled in if tok_identifier
static double NumVal; // Filled in if tok_number
/// gettok - Return the next token from standard input.
static int gettok() {
static int LastChar = ' ';
// Skip any whitespace.
while (isspace(LastChar))
LastChar = getchar();
if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
IdentifierStr = LastChar;
while (isalnum((LastChar = getchar())))
IdentifierStr += LastChar;
if (IdentifierStr == "def")
return tok_def;
if (IdentifierStr == "extern")
return tok_extern;
return tok_identifier;
}
if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
std::string NumStr;
do {
NumStr += LastChar;
LastChar = getchar();
} while (isdigit(LastChar) || LastChar == '.');
NumVal = strtod(NumStr.c_str(), nullptr);
return tok_number;
}
if (LastChar == '#') {
// Comment until end of line.
do
LastChar = getchar();
while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
if (LastChar != EOF)
return gettok();
}
// Check for end of file. Don't eat the EOF.
if (LastChar == EOF)
return tok_eof;
// Otherwise, just return the character as its ascii value.
int ThisChar = LastChar;
LastChar = getchar();
return ThisChar;
}
//===----------------------------------------------------------------------===//
// Abstract Syntax Tree (aka Parse Tree)
//===----------------------------------------------------------------------===//
namespace {
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() = default;
virtual Value *codegen() = 0;
};
/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
double Val;
public:
NumberExprAST(double Val) : Val(Val) {}
Value *codegen() override;
};
/// VariableExprAST - Expression class for referencing a variable, like "a".
class VariableExprAST : public ExprAST {
std::string Name;
public:
VariableExprAST(const std::string &Name) : Name(Name) {}
Value *codegen() override;
};
/// BinaryExprAST - Expression class for a binary operator.
class BinaryExprAST : public ExprAST {
char Op;
std::unique_ptr<ExprAST> LHS, RHS;
public:
BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,
std::unique_ptr<ExprAST> RHS)
: Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
Value *codegen() override;
};
/// CallExprAST - Expression class for function calls.
class CallExprAST : public ExprAST {
std::string Callee;
std::vector<std::unique_ptr<ExprAST>> Args;
public:
CallExprAST(const std::string &Callee,
std::vector<std::unique_ptr<ExprAST>> Args)
: Callee(Callee), Args(std::move(Args)) {}
Value *codegen() override;
};
/// PrototypeAST - This class represents the "prototype" for a function,
/// which captures its name, and its argument names (thus implicitly the number
/// of arguments the function takes).
class PrototypeAST {
std::string Name;
std::vector<std::string> Args;
public:
PrototypeAST(const std::string &Name, std::vector<std::string> Args)
: Name(Name), Args(std::move(Args)) {}
Function *codegen();
const std::string &getName() const { return Name; }
};
/// FunctionAST - This class represents a function definition itself.
class FunctionAST {
std::unique_ptr<PrototypeAST> Proto;
std::unique_ptr<ExprAST> Body;
public:
FunctionAST(std::unique_ptr<PrototypeAST> Proto,
std::unique_ptr<ExprAST> Body)
: Proto(std::move(Proto)), Body(std::move(Body)) {}
Function *codegen();
};
} // end anonymous namespace
//===----------------------------------------------------------------------===//
// Parser
//===----------------------------------------------------------------------===//
/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
/// token the parser is looking at. getNextToken reads another token from the
/// lexer and updates CurTok with its results.
static int CurTok;
static int getNextToken() { return CurTok = gettok(); }
/// BinopPrecedence - This holds the precedence for each binary operator that is
/// defined.
static std::map<char, int> BinopPrecedence;
/// GetTokPrecedence - Get the precedence of the pending binary operator token.
static int GetTokPrecedence() {
if (!isascii(CurTok))
return -1;
// Make sure it's a declared binop.
int TokPrec = BinopPrecedence[CurTok];
if (TokPrec <= 0)
return -1;
return TokPrec;
}
/// LogError* - These are little helper functions for error handling.
std::unique_ptr<ExprAST> LogError(const char *Str) {
fprintf(stderr, "Error: %s\n", Str);
return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
LogError(Str);
return nullptr;
}
static std::unique_ptr<ExprAST> ParseExpression();
/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
auto Result = std::make_unique<NumberExprAST>(NumVal);
getNextToken(); // consume the number
return std::move(Result);
}
/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
getNextToken(); // eat (.
auto V = ParseExpression();
if (!V)
return nullptr;
if (CurTok != ')')
return LogError("expected ')'");
getNextToken(); // eat ).
return V;
}
/// identifierexpr
/// ::= identifier
/// ::= identifier '(' expression* ')'
static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
std::string IdName = IdentifierStr;
getNextToken(); // eat identifier.
if (CurTok != '(') // Simple variable ref.
return std::make_unique<VariableExprAST>(IdName);
// Call.
getNextToken(); // eat (
std::vector<std::unique_ptr<ExprAST>> Args;
if (CurTok != ')') {
while (true) {
if (auto Arg = ParseExpression())
Args.push_back(std::move(Arg));
else
return nullptr;
if (CurTok == ')')
break;
if (CurTok != ',')
return LogError("Expected ')' or ',' in argument list");
getNextToken();
}
}
// Eat the ')'.
getNextToken();
return std::make_unique<CallExprAST>(IdName, std::move(Args));
}
/// primary
/// ::= identifierexpr
/// ::= numberexpr
/// ::= parenexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
switch (CurTok) {
default:
return LogError("unknown token when expecting an expression");
case tok_identifier:
return ParseIdentifierExpr();
case tok_number:
return ParseNumberExpr();
case '(':
return ParseParenExpr();
}
}
/// binoprhs
/// ::= ('+' primary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
std::unique_ptr<ExprAST> LHS) {
// If this is a binop, find its precedence.
while (true) {
int TokPrec = GetTokPrecedence();
// If this is a binop that binds at least as tightly as the current binop,
// consume it, otherwise we are done.
if (TokPrec < ExprPrec)
return LHS;
// Okay, we know this is a binop.
int BinOp = CurTok;
getNextToken(); // eat binop
// Parse the primary expression after the binary operator.
auto RHS = ParsePrimary();
if (!RHS)
return nullptr;
// If BinOp binds less tightly with RHS than the operator after RHS, let
// the pending operator take RHS as its LHS.
int NextPrec = GetTokPrecedence();
if (TokPrec < NextPrec) {
RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
if (!RHS)
return nullptr;
}
// Merge LHS/RHS.
LHS =
std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
}
}
/// expression
/// ::= primary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
auto LHS = ParsePrimary();
if (!LHS)
return nullptr;
return ParseBinOpRHS(0, std::move(LHS));
}
/// prototype
/// ::= id '(' id* ')'
static std::unique_ptr<PrototypeAST> ParsePrototype() {
if (CurTok != tok_identifier)
return LogErrorP("Expected function name in prototype");
std::string FnName = IdentifierStr;
getNextToken();
if (CurTok != '(')
return LogErrorP("Expected '(' in prototype");
std::vector<std::string> ArgNames;
while (getNextToken() == tok_identifier)
ArgNames.push_back(IdentifierStr);
if (CurTok != ')')
return LogErrorP("Expected ')' in prototype");
// success.
getNextToken(); // eat ')'.
return std::make_unique<PrototypeAST>(FnName, std::move(ArgNames));
}
/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDefinition() {
getNextToken(); // eat def.
auto Proto = ParsePrototype();
if (!Proto)
return nullptr;
if (auto E = ParseExpression())
return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
return nullptr;
}
/// toplevelexpr ::= expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
if (auto E = ParseExpression()) {
// Make an anonymous proto.
auto Proto = std::make_unique<PrototypeAST>("__anon_expr",
std::vector<std::string>());
return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
}
return nullptr;
}
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
getNextToken(); // eat extern.
return ParsePrototype();
}
//===----------------------------------------------------------------------===//
// Code Generation
//===----------------------------------------------------------------------===//
static std::unique_ptr<LLVMContext> TheContext;
static std::unique_ptr<Module> TheModule;
static std::unique_ptr<IRBuilder<>> Builder;
static std::map<std::string, Value *> NamedValues;
Value *LogErrorV(const char *Str) {
LogError(Str);
return nullptr;
}
Value *NumberExprAST::codegen() {
return ConstantFP::get(*TheContext, APFloat(Val));
}
Value *VariableExprAST::codegen() {
// Look this variable up in the function.
Value *V = NamedValues[Name];
if (!V)
return LogErrorV("Unknown variable name");
return V;
}
Value *BinaryExprAST::codegen() {
Value *L = LHS->codegen();
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, Type::getDoubleTy(*TheContext), "booltmp");
default:
return LogErrorV("invalid binary operator");
}
}
Value *CallExprAST::codegen() {
// Look up the name in the global module table.
Function *CalleeF = TheModule->getFunction(Callee);
if (!CalleeF)
return LogErrorV("Unknown function referenced");
// If argument mismatch error.
if (CalleeF->arg_size() != Args.size())
return LogErrorV("Incorrect # arguments passed");
std::vector<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");
}
Function *PrototypeAST::codegen() {
// Make the function type: double(double,double) etc.
std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(*TheContext));
FunctionType *FT =
FunctionType::get(Type::getDoubleTy(*TheContext), Doubles, false);
Function *F =
Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());
// Set names for all arguments.
unsigned Idx = 0;
for (auto &Arg : F->args())
Arg.setName(Args[Idx++]);
return F;
}
Function *FunctionAST::codegen() {
// First, check for an existing function from a previous 'extern' declaration.
Function *TheFunction = TheModule->getFunction(Proto->getName());
if (!TheFunction)
TheFunction = Proto->codegen();
if (!TheFunction)
return nullptr;
// Create a new basic block to start insertion into.
BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);
Builder->SetInsertPoint(BB);
// Record the function arguments in the NamedValues map.
NamedValues.clear();
for (auto &Arg : TheFunction->args())
NamedValues[std::string(Arg.getName())] = &Arg;
if (Value *RetVal = Body->codegen()) {
// Finish off the function.
Builder->CreateRet(RetVal);
// Validate the generated code, checking for consistency.
verifyFunction(*TheFunction);
return TheFunction;
}
// Error reading body, remove function.
TheFunction->eraseFromParent();
return nullptr;
}
//===----------------------------------------------------------------------===//
// Top-Level parsing and JIT Driver
//===----------------------------------------------------------------------===//
static void InitializeModule() {
// Open a new context and module.
TheContext = std::make_unique<LLVMContext>();
TheModule = std::make_unique<Module>("my cool jit", *TheContext);
// Create a new builder for the module.
Builder = std::make_unique<IRBuilder<>>(*TheContext);
}
static void HandleDefinition() {
if (auto FnAST = ParseDefinition()) {
if (auto *FnIR = FnAST->codegen()) {
fprintf(stderr, "Read function definition:");
FnIR->print(errs());
fprintf(stderr, "\n");
}
} else {
// Skip token for error recovery.
getNextToken();
}
}
static void HandleExtern() {
if (auto ProtoAST = ParseExtern()) {
if (auto *FnIR = ProtoAST->codegen()) {
fprintf(stderr, "Read extern: ");
FnIR->print(errs());
fprintf(stderr, "\n");
}
} else {
// Skip token for error recovery.
getNextToken();
}
}
static void HandleTopLevelExpression() {
// Evaluate a top-level expression into an anonymous function.
if (auto FnAST = ParseTopLevelExpr()) {
if (auto *FnIR = FnAST->codegen()) {
fprintf(stderr, "Read top-level expression:");
FnIR->print(errs());
fprintf(stderr, "\n");
// Remove the anonymous expression.
FnIR->eraseFromParent();
}
} else {
// Skip token for error recovery.
getNextToken();
}
}
/// top ::= definition | external | expression | ';'
static void MainLoop() {
while (true) {
fprintf(stderr, "ready> ");
switch (CurTok) {
case tok_eof:
return;
case ';': // ignore top-level semicolons.
getNextToken();
break;
case tok_def:
HandleDefinition();
break;
case tok_extern:
HandleExtern();
break;
default:
HandleTopLevelExpression();
break;
}
}
}
//===----------------------------------------------------------------------===//
// Main driver code.
//===----------------------------------------------------------------------===//
int main() {
// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['<'] = 10;
BinopPrecedence['+'] = 20;
BinopPrecedence['-'] = 20;
BinopPrecedence['*'] = 40; // highest.
// Prime the first token.
fprintf(stderr, "ready> ");
getNextToken();
// Make the module, which holds all the code.
InitializeModule();
// Run the main "interpreter loop" now.
MainLoop();
// Print out all of the generated code.
TheModule->print(errs(), nullptr);
return 0;
}