这篇文章上次修改于 902 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
本文跟着 LLVM Tutorial 教程完成，加上了一些注释。本文中的代码并非工程最佳实践。
1 目标
用 LLVM 实现一门简单的语言 Kaleidoscope，实现对如下代码的编译运行：
# 斐波那契数列函数定义
def fib(x)
if x < 3 then
1
else
fib(x - 1) + fib(x - 2)
fib(40)
# 函数声明
extern sin(arg)
extern cos(arg)
extern atan2(arg1 arg2)
# 声明后的函数可调用
atan2(sin(.4), cos(42))为方便，Kaleidoscope 只支持 float64 数据类型。
2 词法分析 Lexer
词法分析是把程序分割成一个个 Token 的过程。Token 包括 if、else、int 等关键字，age 等标识符，+、-、= 等操作符，以及数字、字符串变量等。
2.1 Token 种类
// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
// of these for known things.
enum Token {
TOKEN_EOF = -1,
// commands
TOKEN_DEF = -2,
TOKEN_EXTERN = -3,
// primary
TOKEN_IDENTIFIER = -4,
TOKEN_NUMBER = -5,
};
// 如果当前 Token 是 TOKEN_IDENTIFIER，记录变量
static std::string g_identifier_str;
// 如果当前 Token 是 TOKEN_NUMBER，记录数值
static double g_num_val; 2.2 识别 Token
/// 返回从标准输入中解析出的 token
// TOKEN_EOF: 'def'
// TOKEN_EXTERN: 'extern'
// TOKEN_IDENTIFIER: [a-zA-Z][a-zA-Z0-9]*
// TOKEN_NUMBER: [0-9.]+
static int GetToken() {
static int last_char = ' ';
// 跳过空格
while (isspace(last_char))
last_char = getchar();
// 识别关键字或变量 [a-zA-Z][a-zA-Z0-9]*
if (isalpha(last_char)) {
g_identifier_str = last_char;
while (isalnum((last_char = getchar())))
g_identifier_str += last_char;
if (g_identifier_str == "def")
return TOEKN_DEF;
if (g_identifier_str == "extern")
return TOKEN_EXTERN;
return TOKEN_IDENTIFIER;
}
// 识别数字: [0-9.]+
if (isdigit(last_char) || last_char == '.') {
std::string num_str;
do {
num_str += last_char;
last_char = getchar();
} while (isdigit(last_char) || last_char == '.');
g_num_val = strtod(num_str.c_str(), nullptr);
return TOKEN_NUMBER;
}
// 跳过注释
if (last_char == '#') {
// Comment until end of line.
do
last_char = getchar();
while (last_char != EOF && last_char != '\n' && last_char != '\r');
if (last_char != EOF)
return GetToken();
}
// 识别文件结束
if (last_char == EOF)
return TOEKN_EOF;
// 未知，直接返回 ascii 码
int this_char = last_char;
last_char = getchar();
return this_char;
}3 语法分析 Parser
语法分析是在词法分析的基础上识别出程序的语法结构，这个结构是树状的，称为抽象语法树（Abstract Syntax Tree，AST）。形成 AST 后，计算机就会比较容易处理，比如从根节点遍历整棵树就可以获得表达式的值。
3.1 定义 AST 节点
/// 所有表达式节点的基类
class ExprAST {
public:
virtual ~ExprAST() {}
};
/// 数值表达式
class NumberExprAST : public ExprAST {
double val_;
public:
NumberExprAST(double val) : val_(val) {}
};
/// 变量表达式
class VariableExprAST : public ExprAST {
std::string name_;
public:
VariableExprAST(const std::string &name) : name_(name) {}
};
/// 二元运算表达式
class BinaryExprAST : public ExprAST {
char opcode_;
std::unique_ptr<ExprAST> lhs, rhs;
public:
BinaryExprAST(char opcode, std::unique_ptr<ExprAST> lhs,
std::unique_ptr<ExprAST> rhs)
: opcode_(opcode), lhs_(std::move(lhs)), rhs_(std::move(rhs)) {}
};
/// 函数调用表达式
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)) {}
};
/// 函数接口
/// 包含函数名称，参数名称
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)) {}
const std::string &name() const { return name_; }
};
/// 函数表达式
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)) {}
};后面的章节中会讨论条件表达式。
3.2 解析基本表达式
为方便，定义一个 helper 函数：
// parser 正在查看的 token
static int g_cur_token;
// 从 lexer 中读取下一个 token 并更新 g_cur_token
static int NextToken() {
return g_cur_token = GetToken();
}解析基本表达式：
/// numberexpr ::= number
// 解析数值，构造 NumberExprAST
// 如果当前 token 是 TOKEN_NUMBER，获取数字变量并创建 NumberExprAST，然后将 lexer 前进到下一个 token
static std::unique_ptr<ExprAST> ParseNumberExpr() {
auto result = std::make_unique<NumberExprAST>(g_num_val);
NextToken(); // consume the number
return std::move(result);
}
/// parenexpr ::= '(' expression ')'
// 解析括号表达式，构造 ExprAST
// 如果当前 token 是 '('，获取括号里面的表达式
static std::unique_ptr<ExprAST> ParseParenExpr() {
NextToken(); // eat (.
auto expr = ParseExpression();
if (!expr)
return nullptr;
if (g_cur_token != ')')
return LogError("expected ')'");
NextToken(); // eat ).
return expr;
}
/// identifierexpr
/// ::= identifier
/// ::= identifier '(' expression* ')'
// 解析变量，构造 VariableExprAST；或解析函数调用，构造 CallExprAST
// 如果当前 token 是 TOEN_IDENTIFIER，
// 会预读一个 token，根据其是否为 '(' 来决定当前 identifier 是变量还是函数调用
static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
std::string id_name = g_identifier_str;
NextToken(); // eat identifier.
if (g_cur_token != '(') // Simple variable ref.
return std::make_unique<VariableExprAST>(id_name);
// Call.
NextToken(); // eat (
std::vector<std::unique_ptr<ExprAST>> args;
if (g_cur_token != ')') {
while (1) {
if (auto arg = ParseExpression())
args.push_back(std::move(arg));
else
return nullptr;
if (g_cur_token == ')')
break;
if (g_cur_token != ',')
return LogError("Expected ')' or ',' in argument list");
NextToken();
}
}
// Eat the ')'.
NextToken();
return std::make_unique<CallExprAST>(id_name, std::move(args));
}
/// primary
/// ::= identifierexpr
/// ::= numberexpr
/// ::= parenexpr
// 解析基本表达式
static std::unique_ptr<ExprAST> ParsePrimary() {
switch (g_cur_token) {
default:
return LogError("unknown token when expecting an expression");
case TOKEN_IDENTIFIER:
return ParseIdentifierExpr();
case TOKEN_NUMBER:
return ParseNumberExpr();
case '(':
return ParseParenExpr();
}3.3 解析二元表达式
接下来解析二元表达式，Kaleidoscope 只支持 4 种二元操作符，优先级从低到高为：
< + - *其中，+ 和 - 的优先级相同。
定义优先级：
/// BinopPrecedence - This holds the precedence for each binary operator that is
/// defined.
static std::map<char, int> g_binop_precedence;
/// GetTokenPrecedence - Get the precedence of the pending binary operator token.
static int GetTokenPrecedence() {
if (!isascii(g_cur_token))
return -1;
// Make sure it's a declared binop.
int tok_prec = g_binop_precedence[g_cur_token];
if (tok_prec <= 0) return -1;
return tok_prec;
}
int main() {
// Install standard binary operators.
// 1 is lowest precedence.
g_binop_precedence['<'] = 10;
g_binop_precedence['+'] = 20;
g_binop_precedence['-'] = 20;
g_binop_precedence['*'] = 40; // highest.
...
}对于表达式 a+b+(c+d)*e*f+g，可看作是被二元操作符分隔的基本表达式流，先解析第一个基本表达式 a，然后解析剩余的 [+, b] [+, (c+d)] [*, e] [*, f] 和 [+, g]。即，复杂表达式可以抽象为一个 primaryexpr 跟着多个[binop, primaryexpr]二元组。
/// expression
/// ::= primary binoprhs
static std::unique_ptr<ExprAST> ParseExpression() {
auto lhs = ParsePrimary();
if (!lhs)
return nullptr;
return ParseBinOpRHS(0, std::move(lhs));
}对于表达式 a+b+(c+d)*e*f+g，a 会被传入 ParseBinOpRHS，且当前 token 是 +。
ParseBinOpRHS 的第一个参数表示可被消耗的操作符的最小优先级，假如该值是 40，而当前被解析流是 [+, a]，该函数将不会消耗任何 token，因为 + 的优先级仅为 20，比 40 小。
因为非法二元操作符的优先级是 -1，所以如果遇到一元表达式，该函数会直接返回的。
/// binoprhs
/// ::= ('+' primary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int min_precedence,
std::unique_ptr<ExprAST> lhs) {
// If this is a binop, find its precedence.
while (true) {
int tok_prec = GetTokenPrecedence();
// If this is a binop that binds at least as tightly as the current binop,
// consume it, otherwise we are done.
// 因为非法二元操作符的优先级是 -1，所以如果遇到一元表达式，该函数会直接返回的
if (tok_prec < min_precedence)
return lhs;
// Okay, we know this is a binop.
int binop = g_cur_token;
NextToken(); // 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.
// 有两种可能的解析方式
// (lhs binop rhs) binop unparsed
// lhs binop (rhs binop unparsed)
int next_prec = GetTokenPrecedence();
if (tok_prec < next_prec) {
rhs = ParseBinOpRHS(tok_prec + 1, std::move(rhs));
if (!rhs)
return nullptr;
}
// Merge lhs/rhs.
lhs =
std::make_unique<BinaryExprAST>(binop, std::move(lhs), std::move(rhs));
}
}3.4 解析剩余部分
解析函数原型：
/// prototype
/// ::= id '(' id* ')'
static std::unique_ptr<PrototypeAST> ParsePrototype() {
if (g_cur_token != TOKEN_IDENTIFIER)
return LogErrorP("Expected function name in prototype");
std::string fn_name = g_identifier_str;
NextToken();
if (g_cur_token != '(')
return LogErrorP("Expected '(' in prototype");
// Read the list of argument names.
std::vector<std::string> arg_names;
while (NextToken() == TOKEN_IDENTIFIER)
arg_names.push_back(g_dentifier_str);
if (g_cur_token != ')')
return LogErrorP("Expected ')' in prototype");
// success.
NextToken(); // eat ')'.
return std::make_unique<PrototypeAST>(fn_name, std::move(arg_names));
}解析函数：def + 函数原型 + 函数体，函数体是一个表达式。
/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDefinition() {
NextToken(); // eat def.
auto proto = ParsePrototype();
if (!proto) return nullptr;
if (auto expr = ParseExpression())
return std::make_unique<FunctionAST>(std::move(proto), std::move(expr));
return nullptr;
}解析 extern 表达式：
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
NextToken(); // eat extern.
return ParsePrototype();
}为顶层代码实现匿名函数：
/// toplevelexpr ::= expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
if (auto expr = ParseExpression()) {
// Make an anonymous proto.
auto proto = std::make_unique<PrototypeAST>("", std::vector<std::string>());
return std::make_unique<FunctionAST>(std::move(proto), std::move(expr));
}
return nullptr;
}3.5 Driver
/// top ::= definition | external | expression | ';'
static void MainLoop() {
while (1) {
fprintf(stderr, "ready> ");
switch (g_cur_token) {
case TOKEN_EOF:
return;
case ';': // ignore top-level semicolons.
NextToken();
break;
case TOKEN_DEF:
HandleDefinition();
break;
case TOKEN_EXTERN:
HandleExtern();
break;
default:
HandleTopLevelExpression();
break;
}
}
}编译运行：
# Compile
$ clang++ -g -O3 toy.cpp `llvm-config --cxxflags`
# Run
$ ./a.out
ready> def foo(x y) x+foo(y, 4.0);
Parsed a function definition.
ready> def foo(x y) x+y y;
Parsed a function definition.
Parsed a top-level expr
ready> def foo(x y) x+y );
Parsed a function definition.
Error: unknown token when expecting an expression
ready> extern sin(a);
ready> Parsed an extern
ready> ^D4 语义分析
语义分析是消除语义模糊，比如：
- 数据类型不匹配是否要做自动转换？由于本文中涉及的数据类型都是 float64 类型，所以不涉及数据类型推导、转换等。
- 如果一个代码块内部和外部有相同名称的变量，用哪个？
- 同一个作用域内，不允许有两个相同名称的变量。
语义分析还会生成一些属性信息，并标注在 AST 上。
5 生成 LLVM IR
IR 指中间表达方式，介于高级语言和汇编语言之间。与高级语言相比，丢弃了语法和语义特征，比如作用域、面向对象等；与汇编语言相比，不会有硬件相关的细节，比如目标机器架构、操作系统等。
先 include 一些 LLVM 头文件并定义全局变量：
#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/LegacyPassManager.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/TargetSelect.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Transforms/InstCombine/InstCombine.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/GVN.h"
// 记录一些全局数据，比如各模块中用到的类型和常量
static std::unique_ptr<LLVMContext> g_llvm_context;
// 一个文件就是一个模块
// 模块中包含函数、全局变量
static std::unique_ptr<Module> g_llvm_module;
// 用于创建 LLVM 指令
static std::unique_ptr<IRBuilder<>> g_ir_builder;
// 用于记录函数的变量参数
static std::map<std::string, Value *> g_named_values;5.1 添加 Codegen()
在每个 AST 类中添加 Codegen()，用于生成 LLVM IR。
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() {}
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) {}
virtual Value *Codegen();
};
...也可以通过 visitor 模式生成 LLVM IR，本文并非工程最佳实践，添加 Codegen() 会更简单一些。Codegen() 会返回 LLVM Value，Value 用来表示 SSA（Static Single Assignment）值，一个变量只能被定义一次，然后多次使用，便于代码优化。
5.2 实现 Codegen()
实现 NumberExprAST 的 Codegen()：
Value *NumberExprAST::Codegen() {
return ConstantFP::get(g_llvm_context, APFloat(val_));
}在 LLVM IR 中，所有常量都是唯一且共享的，所以使用 get 而不是 new/create。
实现 VariableExprAST 的 Codegen()：
Value *VariableExprAST::Codegen() {
// Look this variable up in the function.
Value *v = g_named_values[name_];
if (!v)
LogErrorV("Unknown variable name");
return v;
}
目前 g_named_values 中仅保存函数参数，在生成的函数的 IR 时，会生成参数的 IR，并存放到 g_named_values 中，所以这里仅仅是获取。后面 g_named_values 中会保存循环中的变量和本地变量。
实现 BinaryExprAST 的 Codegen()：
Value *BinaryExprAST::Codegen() {
Value *l = lhs_->Codegen();
Value *r = rhs_->Codegen();
if (!l || !r)
return nullptr;
switch (opcode_) {
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::GetDoubleTypepe(*g_llvm_context),
"booltmp");
default:
return LogErrorV("invalid binary operator");
}
}递归地生成左边表达式是 IR 和右边表达式的 IR，然后计算结果。Builder.CreateFAdd() 用来插入加法的 IR 指令，第三个参数表示名称，使得生成的 IR 便于阅读。
LLVM 指令要求比较严格，比如，加法指令的 L 和 R 的数据类型必须相同，结果类型必须和操作数类型匹配。
另外，CreateFCmpULT() 返回 bool 型，但 Kaleidoscope 中的数据类型都为 float64，所以需要通过 CreateUIToFP() 转换一下。
实现 CallExprAST 的 Codegen()：
Value *CallExprAST::Codegen() {
// Look up the name in the global module table.
// LLVM Module 中存放了所有的函数
Function *callee = g_llvm_module->getFunction(callee_);
if (!callee)
return LogErrorV("Unknown function referenced");
// If argument mismatch error.
if (callee->arg_size() != args.size())
return LogErrorV("Incorrect # arguments passed");
std::vector<Value *> args_v;
for (unsigned i = 0, e = args_.size(); i != e; ++i) {
args_v.push_back(args_[i]->Codegen());
if (!args_v.back())
return nullptr;
}
return g_ir_builder.CreateCall(callee, args_v, "calltmp");
}
实现 PrototypeAST 的 Codegen()：
// 返回的是 Function* 而非 Value*
Function *PrototypeAST::Codegen() {
// Make the function type: double(double, double) etc.
std::vector<Type*> doubles(args_.size(),
Type::GetDoubleTypepe(*g_llvm_context));
// 在 LLVM 中，Types 是唯一的，所以使用 get 而非 new
// false 表示参数个数是固定的
FunctionType *f_type =
FunctionType::get(Type::GetDoubleTypepe(*g_llvm_context), doubles, false);
// 生成 IR
// 第 2 个参数表明函数可能定义在当前模块外，或者本函数可被其它模块调用
// 第 4 个参数表明了要插入到哪个模块
Function *fun =
Function::Create(f_type, Function::ExternalLinkage, name_, g_llvm_module.get());
// Set names for all arguments.
// 本步骤不是必须的，可以使得生成的 IR 更具可读性
// 也使得后续的代码可以直接通过参数名称引用参数，而避免遍历 PrototypeAST
unsigned idx = 0;
for (auto &arg : fun->args())
arg.setName(args[Idx++]);
return fun;
}实现 FunctionAST 的 Codegen()：会加上函数体
Function *FunctionAST::Codegen() {
// First, check for an existing function from a previous 'extern' declaration.
// 可能会有 extern 声明
Function *function = g_llvm_module->getFunction(proto_->name());
if (!function)
function = proto_->Codegen();
if (!function)
return nullptr;
if (!function->empty())
return (Function*)LogErrorV("Function cannot be redefined.");
// Create a new basic block to start insertion into.
// 创建一个名称为 entry 的基本块，会被插入到 function
// llvm block 用于定义control flow graph, 但我们暂不实现 control flow，创建一个单独的 block 即可
BasicBlock *bb = BasicBlock::Create(g_llvm_context, "entry", function);
// 设置指令插入点，即后面的指令会被插入到 bb
Builder.SetInsertPoint(bb);
// Record the function arguments in the g_named_values map.
// g_named_values 会被 VariableExprAST 访问
g_named_values.clear();
for (auto &arg : function->args())
g_named_values[arg.getName()] = &arg;
// 会将计算表达式的 IR 发送到 entry block 中，并返回计算结果
if (Value *ret_val = body_->Codegen()) {
// Finish off the function.
// 利用计算结果创建返回值
g_ir_builder.CreateRet(ret_val);
// Validate the generated code, checking for consistency.
verifyFunction(*function);
return function;
}
// Error reading body, remove function.
function->eraseFromParent();
return nullptr;
}该代码目前还存在一个问题，如果 FunctionAST::Codegen() 发现了一个已经存在的 IR，并不会检查其签名。
5.3 运行
ready> 4+5;
Read top-level expression:
define double @0() {
entry:
ret double 9.000000e+00
}
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
}6 优化
IRBuilder 生成的 IR 如下：
ready> def test(x) 1+2+x;
Read function definition:
define double @test(double %x) {
entry:
%addtmp = fadd double 3.000000e+00, %x
ret double %addtmp
}可以看到，自动进行了常量折叠。
但是如果想对如下 IR 优化，还需要引入 LLVM 中的 pass。
ready> def test(x) (1+2+x)*(x+(1+2));
ready> Read function definition:
define double @test(double %x) {
entry:
%addtmp = fadd double 3.000000e+00, %x
%addtmp1 = fadd double %x, 3.000000e+00
%multmp = fmul double %addtmp, %addtmp1
ret double %multmp
}可以选择是否启用 pass，并调整 pass 的顺序。
LLVM 既提供针对整个 Module 的 pass，也提供针对单个函数的 pass。
本文中，对每个函数单独优化，初始化 pass 管理器：
static std::unique_ptr<legacy::FunctionPassManager> g_fpm;
void InitializeModuleAndPassManager(void) {
// Open a new module.
g_llvm_module = std::make_unique<Module>("my cool jit", g_llvm_context);
// Create a new pass manager attached to it.
g_fpm = std::make_unique<legacy::FunctionPassManager>(g_llvm_module.get());
// Do simple "peephole" optimizations and bit-twiddling optzns.
g_fpm->add(createInstructionCombiningPass());
// Reassociate expressions.
g_fpm->add(createReassociatePass());
// Eliminate Common SubExpressions.
g_fpm->add(createGVNPass());
// Simplify the control flow graph (deleting unreachable blocks, etc).
g_fpm->add(createCFGSimplificationPass());
g_fpm->doInitialization();
}在 FunctionAST::Codegen() 中添加如下代码：
if (Value *ret_val = body_->Codegen()) {
// Finish off the function.
g_ir_builder.CreateRet(ret_val);
// Validate the generated code, checking for consistency.
verifyFunction(*function);
// Optimize the function.
g_fpm->run(*function);
return function;
}测试并查看效果：
ready> def test(x) (1+2+x)*(x+(1+2));
ready> Read function definition:
define double @test(double %x) {
entry:
%addtmp = fadd double %x, 3.000000e+00
%multmp = fmul double %addtmp, %addtmp
ret double %multmp
}7 添加 JIT
提前编译（AOT）：编译成可执行文件后，再执行。
即时编译（JIT）：在需要运行某段代码的时候，再编译。Java、JavaScript 等语言都是通过即时编译提高性能的
JIT 原理：动态申请内存，加载目标代码到内存，并赋予内存可执行权限。
定义 JIT 的全局变量，并通过 InitializeNativeTarget* 函数初始化环境。
#include "KaleidoscopeJIT.h"
static std::unique_ptr<KaleidoscopeJIT> g_jit;
...
int main() {
InitializeNativeTarget();
InitializeNativeTargetAsmPrinter();
InitializeNativeTargetAsmParser();
g_jit = std::make_unique<KaleidoscopeJIT>();
...
return 0;
}其中，KaleidoscopeJIT.h 是从 LLVM 的源码 llvm-src/examples/Kaleidoscope/include/KaleidoscopeJIT.h 中拷贝过来的。
为 JIT 设置数据布局：
void InitializeModuleAndPassManager(void) {
// Open a new module.
g_llvm_module = std::make_unique<Module>("my cool jit", g_llvm_context);
g_llvm_module->setDataLayout(g_jit->getTargetMachine().createDataLayout());
// Create a new pass manager attached to it.
g_fpm = std::make_unique<legacy::FunctionPassManager>(g_llvm_module.get());
...修改顶层解析函数：
static void HandleTopLevelExpression() {
// Evaluate a top-level expression into an anonymous function.
if (auto fn_ast = ParseTopLevelExpr()) {
if (fn_ast->Codegen()) {
// 顶层函数 Codegen 后，将包含顶层函数的模块添加到 JIT
// addModule 会触发模块中所有函数的 Codegen，并返回一个句柄 handle
// 后续可以通过 handle 删除该模块
auto handle = g_jit->addModule(std::move(g_llvm_module));
// 一旦模块被添加到JIT中，就不能再对其进行修改
// 因此我们还通过调用InitializeModuleAndPassManager（）打开一个新模块来保存后续代码。
InitializeModuleAndPassManager();
// 通过顶层函数的名称搜索其符号
auto expr_symbol = g_jit->findSymbol("__anon_expr");
assert(expr_symbol && "Function not found");
// 获取符号地址，强制转换为函数指针 (double (*)())（无参数，并返回一个 double）
double (*fp)() = (double (*)())(intptr_t)expr_symbol.getAddress();
fprintf(stderr, "Evaluated to %f\n", fp());
// Delete the anonymous expression module from the JIT.
g_jit->removeModule(handle);
}运行：
ready> def testfunc(x y) x + y*2;
Read function definition:
define double @testfunc(double %x, double %y) {
entry:
%multmp = fmul double %y, 2.000000e+00
%addtmp = fadd double %multmp, %x
ret double %addtmp
}
ready> testfunc(4, 10);
Read top-level expression:
define double @1() {
entry:
%calltmp = call double @testfunc(double 4.000000e+00, double 1.000000e+01)
ret double %calltmp
}
Evaluated to 24.000000
ready> testfunc(5, 10);
ready> LLVM ERROR: Program used external function 'testfunc' which could not be resolved!可以看到存在一个问题，所有函数都在同一个模块中，当模块被删除并释放后，函数定义也随之被删除。
最简单的解决方式是将顶层函数和其它函数定义分别放在不同的模块中，这样即时顶层函数所在模块被删掉，也不会影响到其它函数。
我们也可以更进一步，将每个函数都放在自己的模块中，这样函数就可以被多次添加到 JIT 中了。当我们在 JIT 中查找函数符号时，总是会返回被最新定义的：
ready> def foo(x) x + 1;
Read function definition:
define double @foo(double %x) {
entry:
%addtmp = fadd double %x, 1.000000e+00
ret double %addtmp
}
ready> foo(2);
Evaluated to 3.000000
ready> def foo(x) x + 2;
define double @foo(double %x) {
entry:
%addtmp = fadd double %x, 2.000000e+00
ret double %addtmp
}
ready> foo(2);
Evaluated to 4.000000在每个新打开的模块中重新生成函数定义：
static std::unique_ptr<KaleidoscopeJIT> g_jit;
// 存放函数的最新定义
static std::map<std::string, std::unique_ptr<PrototypeAST>> g_function_protos;
...
Function *GetFunction(std::string Name) {
// 首先，在模块中搜寻函数定义
if (auto *f = g_llvm_module->getFunction(Name))
return f;
// 如果没有找到，就根据 g_function_protos 新生成定义
auto fn = g_function_protos.find(Name);
if (fn != g_function_protos.end())
return fn->second->Codegen();
// If no existing prototype exists, return null.
return nullptr;
}
...
Value *CallExprAST::Codegen() {
// Look up the name in the global module table.
// 替换 g_llvm_module->getFunction()
Function *callee = GetFunction(Callee);
...
Function *FunctionAST::Codegen() {
// Transfer ownership of the prototype to the g_function_protos map, but keep a
// reference to it for use below.
auto &proto = *proto_;
// 先更新 g_function_protos，然后再调用 getFunction
g_function_protos[proto_->name()] = std::move(proto_);
Function *function = GetFunction(proto.name());
if (!function)
return nullptr;还需要更新 HandleDefinition 和 HandleExtern：
static void HandleDefinition() {
if (auto fn_ast = ParseDefinition()) {
if (auto *fn_ir = fn_ast->Codegen()) {
fprintf(stderr, "Read function definition:");
fn_ir->print(errs());
fprintf(stderr, "\n");
// 将最新定义的函数添加到 JIT
g_jit->addModule(std::move(g_llvm_module));
// 打开新模块
InitializeModuleAndPassManager();
}
} else {
// Skip token for error recovery.
NextToken();
}
}
static void HandleExtern() {
if (auto proto_ast = ParseExtern()) {
if (auto *fn_ir = proto_ast->Codegen()) {
fprintf(stderr, "Read extern: ");
fn_ir->print(errs());
fprintf(stderr, "\n");
// 更新 g_function_protos
g_function_protos[proto_ast->name()] = std::move(proto_ast);
}
} else {
// Skip token for error recovery.
NextToken();
}
}再次运行：
ready> def foo(x) x + 1;
ready> foo(2);
Evaluated to 3.000000
ready> def foo(x) x + 2;
ready> foo(2);
Evaluated to 4.0000008 控制流
8.1 支持 If/Then/Else
在 lexer 中支持新的 token：
// control
TOKEN_IF = -6,
TOKEN_then_ = -7,
TOKEN_else_ = -8,识别新 token：
...
if (g_identifier_str == "if")
return TOKEN_IF;
if (g_identifier_str == "then")
return TOKEN_THEN;
if (g_identifier_str == "else")
return TOKEN_ELSE;添加新的 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;
};定义新的解析函数：
/// ifexpr ::= 'if' expression 'then' expression 'else' expression
static std::unique_ptr<ExprAST> ParseIfExpr() {
NextToken(); // eat the if.
// condition.
auto cond = ParseExpression();
if (!cond)
return nullptr;
if (g_cur_token != TOKEN_THEN)
return LogError("expected then");
NextToken(); // eat the then
auto then_expr = ParseExpression();
if (!then_expr)
return nullptr;
if (g_cur_token != TOKEN_ELSE)
return LogError("expected else");
NextToken();
auto else_expr = ParseExpression();
if (!else)
return nullptr;
return std::make_unique<IfExprAST>(std::move(cond), std::move(then_expr),
std::move(else_expr));
}修改基本表达式的解析：
static std::unique_ptr<ExprAST> ParsePrimary() {
switch (g_cur_token) {
default:
return LogError("unknown token when expecting an expression");
case TOKEN_IDENTIFIER:
return ParseIdentifierExpr();
case TOKEN_NUMBER:
return ParseNumberExpr();
case '(':
return ParseParenExpr();
case TOKEN_IF:
return ParseIfExpr();
}
}生成 IR：
Value *IfExprAST::Codegen() {
Value *cond_v = cond_->Codegen();
if (!cond_v)
return nullptr;
// Convert condition to a bool by comparing non-equal to 0.0.
// 创建fcmp one指令, cond_value = (cond_value != 0.0)
cond_v = g_ir_builder.CreateFCmpONE(
cond_v, ConstantFP::get(g_llvm_context, APFloat(0.0)), "ifcond");
// 获取要插入指令的函数
Function *function = g_ir_builder.GetInsertBlock()->getParent();
// Create blocks for the then and else cases. Insert the 'then' block at the
// end of the function.
// 创建 3 个 block，并将 then block 插入到函数中
// 另外两个 block 还没有被插入到函数中，因为后面要先为 then_bb 生成指令
BasicBlock *then_bb = BasicBlock::Create(*g_llvm_context, "then", function);
BasicBlock *else_bb = BasicBlock::Create(*g_llvm_context, "else");
BasicBlock *merge_bb = BasicBlock::Create(*g_llvm_context, "ifcond");
// 创建条件跳转指令，cond_v 是 1 的时候跳转到 then_bb，0 的时候跳转到 else_bb
Builder.CreateCondBr(cond_v, then_bb, else_bb);
// ---------------------- Emit then value.
// 将指令插入点移到 then_bb
g_ir_builder.SetInsertPoint(then_bb);
Value *then_v = then_->Codegen();
if (!then_v)
return nullptr;
// 为了结束 then_bb，创建了一个到 merge_bb 的无条件跳转指令
g_ir_builder.CreateBr(merge_bb);
// Codegen of 'Then' can change the current block, update ThenBB for the PHI.
// 更新 ThenBB，因为 ThenBB 可能已经改变了 Builder 要插入指令的 block
// 比如内部可能会有 if/then/else，而我们需要获取最终有结果的 block
then_bb = g_ir_builder.GetInsertBlock();
// ----------------------- Emit else block.
// 将 ElseBB 添加到函数中
function->getBasicBlockList().push_back(else_bb);
g_ir_builder.SetInsertPoint(else_bb);
Value *else_v = else_->Codegen();
if (!else_v)
return nullptr;
g_ir_builder.CreateBr(MergeBB);
// Codegen of 'else_' can change the current block, update else_bb for the PHI.
else_bb = g_ir_builder.GetInsertBlock();
// ------------------------ Emit merge block.
function->getBasicBlockList().push_back(merge_bb);
g_ir_builder.SetInsertPoint(merge_bb);
// 创建 PHI 指令：浮点型，2 个候选值
PHINode *pn =
Builder.CreatePHI(Type::GetDoubleTypepe(g_llvm_context), 2, "iftmp");
pn->addIncoming(then_v, then_bb); // 如果是来自 then_bb 的跳转，采用 then_v
pn->addIncoming(else_v, else_bb); // 如果是来自 else_bb 的跳转，采用 else_v
return pn;
}8.2 支持 for 循环表达式
接下来支持 for 表达式：
extern putchard(char);
def printstar(n)
for i = 1, i < n, 1.0 in
putchard(42); # ascii 42 = '*'
# print 100 '*' characters
printstar(100);扩展 lexer：
... in enum Token ...
TOKEN_FOR = -9,
TOKEN_IN = -10,
... in GetToken ...
if (g_identifier_str == "for")
return TOKEN_FOR;
if (g_identifier_str == "in")
return TOKEN_IN;
return TOKEN_IDENTIFIER;扩展 AST：
/// ForExprAST - Expression class for for/in.
class ForExprAST : public ExprAST {
std::string var_name_;
std::unique_ptr<ExprAST> start_, end_, step_, body_;
public:
ForExprAST(const std::string &var_name, std::unique_ptr<ExprAST> start,
std::unique_ptr<ExprAST> end, std::unique_ptr<ExprAST> step,
std::unique_ptr<ExprAST> body;)
: var_name_(var_name), start_(std::move(start)), end_(std::move(end)),
step_(std::move(step)), body_(std::move(body)) {}
Value *Codegen() override;
};扩展 Parser：
/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
static std::unique_ptr<ExprAST> ParseForExpr() {
NextToken(); // eat the for.
if (g_cur_token != TOKEN_IDENTIFIER)
return LogError("expected identifier after for");
std::string identifier_name = g_identifier_str;
NextToken(); // eat identifier.
if (g_cur_token != '=')
return LogError("expected '=' after for");
NextToken(); // eat '='.
auto start = ParseExpression();
if (!start)
return nullptr;
if (g_cur_token != ',')
return LogError("expected ',' after for start_ value");
NextToken();
auto end = ParseExpression();
if (!end)
return nullptr;
// The step value is optional.
std::unique_ptr<ExprAST> step;
if (g_cur_token == ',') {
NextToken();
step = ParseExpression();
if (!step)
return nullptr;
}
if (g_cur_token != TOKEN_IN)
return LogError("expected 'in' after for");
NextToken(); // eat 'in'.
auto body = ParseExpression();
if (!body)
return nullptr;
return std::make_unique<ForExprAST>(identifier_name, std::move(start), std::move(end),
std::move(step), std::move(body));
}再次更新对基本表达式的解析：
static std::unique_ptr<ExprAST> ParsePrimary() {
switch (g_cur_token) {
...
case TOKEN_FOR:
return ParseForExpr();
}
}生成 IR：
// Output for-loop as:
// var = alloca double
// ...
// start = startexpr
// store start -> var
// goto loop
// loop:
// ...
// bodyexpr
// ...
// loopend:
// step = stepexpr
// endcond = endexpr
//
// curvar = load var
// nextvar = curvar + step
// store nextvar -> var
// br endcond, loop, endloop
// outloop:
Value *ForExprAST::Codegen() {
// Emit the start code first, without 'variable' in scope.
Value *start_val = start_->Codegen();
if (!start_val)
return nullptr;
// Make the new basic block for the loop header, inserting after current
// block.
Function *function = g_ir_builder->GetInsertBlock()->getParent();
// 获得当前 block
BasicBlock *preheader_bb = g_ir_builder->GetInsertBlock();
// 新增 loop_bb
BasicBlock *loop_bb =
BasicBlock::Create(g_llvm_context, "loop", function);
// Insert an explicit fall through from the current block to the LoopBB.
// 添加从当前 block 到 loop_bb 的跳转指令
g_ir_builder.CreateBr(loop_bb);
// Start insertion in loop_bb.
// 开始在 loop_bb 内增加指令
g_ir_builder.SetInsertPoint(loop_bb);
// Start the PHI node with an entry for Start.
// 新增 PHI 指令
PHINode *variable = Builder.CreatePHI(Type::GetDoubleTypepe(g_llvm_context),
2, var_name_.c_str())
// 如果是来自 preheader_bb 的跳转，则取 start_val 的值
variable->addIncoming(start_val, preheader_bb);
// Within the loop, the variable is defined equal to the PHI node. If it
// shadows an existing variable, we have to restore it, so save it now.
// 防止 loop 中的变量覆盖已有的同名变量
Value *old_val = g_named_values[var_name_];
g_named_values[var_name_] = variable;
// Emit the body of the loop.
// This, like any other expr, can change the
// current BB. Note that we ignore the value computed by the body, but don't
// allow an error.
// body 可能会用到刚刚更新到 g_named_values 中的 loop 变量
if (!body_->Codegen())
return nullptr;
// Emit the step value.
Value *step_val = nullptr;
if (step_) {
step_val = step_->Codegen();
if (!step_val)
return nullptr;
} else {
// If not specified, use 1.0.
step_val = ConstantFP::get(g_llvm_context, APFloat(1.0));
}
// 生成 body 后，需要计算下次循环中的变量值
Value *next_var = g_ir_builder.CreateFAdd(variable, step_val, "nextvar");
// Compute the end condition.
Value *end_cond = end_->Codegen();
if (!end_ond)
return nullptr;
// Convert condition to a bool by comparing non-equal to 0.0.
end_cond = g_ir_builder.CreateFCmpONE(
end_cond, ConstantFP::get(g_llvm_context, APFloat(0.0)), "loopcond");
// Create the "after loop" block and insert it.
BasicBlock *loop_end_bb = g_ir_builder.GetInsertBlock();
BasicBlock *after_bb =
BasicBlock::Create(g_llvm_context, "afterloop", function);
// Insert the conditional branch into the end of loop_end_bb.
// 创建条件跳转指令，决定是否要退出循环
g_ir_builder.CreateCondBr(end_cond, loop_bb, after_bb);
// Any new code will be inserted in after_bb.
// 后续的指令会插入到 after_bb 中
g_ir_builder.SetInsertPoint(after_bb);
// Add a new entry to the PHI node for the backedge.
// 如果是再次循环，则取 next_var 值
variable->addIncoming(next_var, loop_end_bb);
// Restore the unshadowed variable.
// loop 中的变量只能在 loop 作用域内使用
if (old_val)
g_g_named_values[var_name_] = old_val;
else
g_named_values.erase(var_name_);
// for expr always returns 0.0.
return Constant::getNullValue(Type::GetDoubleTypepe(g_llvm_context));
}可以看到，loop 中也用到了 PHI 指令，如果是第一次循环，则循环变量取 StartVal 值；否则，取 NextVal 值。
编译运行：
# Compile
clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy
# Run
./toy9 用户自定义运算符
我们将允许用户新增不存在的运算符，比如：
# 定义一元运算符 !
def unary!(v)
if v then
0
else
1;
# 定义二元运算符 >，优先级为 10
def binary> 10 (LHS RHS)
RHS < LHS;
# Binary "logical or", (note that it does not "short circuit")
# 定义二元运算符 |，优先级为 5
def binary| 5 (LHS RHS)
if LHS then
1
else if RHS then
1
else
0;
# Define = with slightly lower precedence than relationals.
# 定义二元运算符 =，优先级为 9
def binary= 9 (LHS RHS)
!(LHS < RHS | LHS > RHS);9.1 自定义二元运算符
扩展 Lexer：
enum Token {
...
// operators
TOKEN_BINARY = -11,
TOKEN_UNARY = -12,
};
...
static int GetToken() {
...
if (g_identifier_str == "binary")
return TOKEN_BINARY;
if (g_identifier_str == "unary")
return TOKEN_UNARY;
return TOKEN_IDENTIFIER;
}新增的二元操作符会被视为一个函数，所以不需要新增 AST 节点，只需扩展 PrototypeAST 节点即可：
/// PrototypeAST - This class represents the "prototype" for a function,
/// which captures its argument names as well as if it is an operator.
class PrototypeAST {
std::string name_;
std::vector<std::string> args_;
bool is_operator_; // 是否为操作符
unsigned precedence_; // 二元操作符的优先级
public:
PrototypeAST(const std::string &name,
std::vector<std::string> args_, bool is_operator = false,
unsigned prec = 0)
: name_(name), args_(std::move(args)), is_operator_(is_operator),
precedence_(prec) {}
Function *Codegen();
const std::string &name() const { return name_; }
bool IsUnaryOpcode() const { return is_operator_ && args_.size() == 1; }
bool IsBinaryOpcode() const { return is_operator_ && args_.size() == 2; }
char operator_name() const {
assert(IsUnaryOpcode() || IsBinaryOpcode());
return name_[name_.size() - 1];
}
unsigned binary_precedence() const { return precedence_; }
};修改 Parser：
/// prototype
/// ::= id '(' id* ')'
/// ::= binary LETTER number? (id, id)
static std::unique_ptr<PrototypeAST> ParsePrototype() {
std::string fn_name;
unsigned kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
unsigned binary_precedence = 30;
switch (g_cur_token) {
default:
return LogErrorP("Expected function name in prototype");
case TOKEN_IDENTIFIER:
fn_name = g_identifier_str;
kind = 0;
NextToken();
break;
// 解析二元操作符名称和优先级
case TOKEN_BINARY:
NextToken();
if (!isascii(g_cur_token))
return LogErrorP("Expected binary operator");
fn_name = "binary";
fn_name += (char)g_cur_token;
kind = 2;
NextToken();
// Read the precedence if present.
if (g_cur_token == TOKEN_NUMBER) {
if (g_num_val < 1 || g_num_val > 100)
return LogErrorP("Invalid precedence: must be 1..100");
binary_precedence = (unsigned)g_num_val;
NextToken();
}
break;
}
if (g_cur_token != '(')
return LogErrorP("Expected '(' in prototype");
std::vector<std::string> arg_names;
while (NextToken() == TOKEN_IDENTIFIER)
arg_names.push_back(g_identifier_str);
if (g_cur_token != ')')
return LogErrorP("Expected ')' in proto_type");
// success.
NextToken(); // eat ')'.
// Verify right number of names for operator.
if (kind && arg_names.size() != kind)
return LogErrorP("Invalid number of oprand_s for operator");
return std::make_unique<PrototypeAST>(fn_name, arg_names, kind != 0,
binary_precedence);
}生成 IR：
Value *BinaryExprAST::Codegen() {
Value *l = lhs_->Codegen();
Value *r = rhs_->Codegen();
if (!l || !r)
return nullptr;
switch (opcode_) {
case '+':
return g_ir_builder->CreateFAdd(l, r, "addtmp");
case '-':
return g_ir_builder->CreateFSub(l, r, "subtmp");
case '*':
return g_ir_builder->CreateFMul(l, r, "multmp");
case '<':
l = g_ir_builder->CreateFCmpULT(l, r, "cmptmp");
// Convert bool 0/1 to double 0.0 or 1.0
return g_ir_builder->CreateUIToFP(l, Type::GetDoubleTypepe(*g_llvm_context), "booltmp");
default:
break;
}
// If it wasn't a builtin binary operator, it must be a user defined one. Emit
// a call to it.
Function *f = GetFunction(std::string("binary") + opcode_);
assert(f && "binary operator not found!");
Value *opcodes[] = {l, r};
return g_ir_builder->CreateCall(f, opcodes, "binopcode");
}顶层函数的 IR：
Function *FunctionAST::Codegen() {
// Transfer ownership of the prototype to the g_function_protos map, but keep a
// reference to it for use below.
auto &proto = *proto_;
g_function_protos[proto_->name()] = std::move(proto_);
Function *function = GetFunction(proto.name());
if (!function)
return nullptr;
// If this is an operator, install it.
if (P.IsBinaryOp())
// 注册优先级，为后续 Codegen 作准备
g_binopcode_precedence[proto.operator_name()] = proto.binary_precedence();
// Create a new basic block to start insertion into.
BasicBlock *bb = BasicBlock::Create(*g_llvm_context, "entry", function);
...9.2 自定义一元运算符
支持自定义二元操作符只是扩展了已有框架，而支持一元操作符会更具挑战。
添加 AST 节点：
/// UnaryExprAST - Expression class for a unary operator.
class UnaryExprAST : public ExprAST {
char opcode_;
std::unique_ptr<ExprAST> operand_;
public:
UnaryExprAST(char opcode, std::unique_ptr<ExprAST> oprand)
: opcode_(opcode), oprand_(std::move(oprand)) {}
Value *Codegen() override;
};添加 Parser：
/// unary
/// ::= primary
/// ::= '!' unary
static std::unique_ptr<ExprAST> ParseUnary() {
// If the current token is not an operator, it must be a primary expr.
if (!isascii(g_cur_token) || g_cur_token == '(' || g_cur_token == ',')
return ParsePrimary();
// If this is a unary operator, read it.
int opcode = g_cur_token;
NextToken();
if (auto operand = ParseUnary())
return std::make_unique<UnaryExprAST>(opcode, std::move(operand));
return nullptr;
}以上代码先处理一元运算符，然后将剩余部分看作另外一个一元运算表达式，这样的话就能处理有多个一元运算符的情况了，比如 !!x。
接下来，需要想办法让 ParseUnary 被调用到。可以将调用 ParsePrimary 的地方替换为调用 ParseUnary：
/// binoprhs
/// ::= ('+' unary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int min_expr_prec,
std::unique_ptr<ExprAST> lhs) {
...
// Parse the unary expression after the binary operator.
auto rhs = ParseUnary();
if (!rhs)
return nullptr;
...
}
/// expression
/// ::= unary binoprhs
static std::unique_ptr<ExprAST> ParseExpression() {
auto lhs = ParseUnary();
if (!lhs)
return nullptr;
return ParseBinOpRHS(0, std::move(lhs));
}扩展对 Prototype 的解析：
/// prototype
/// ::= id '(' id* ')'
/// ::= binary LETTER number? (id, id)
/// ::= unary LETTER (id)
static std::unique_ptr<PrototypeAST> ParsePrototype() {
std::string fn_name;
unsigned kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
unsigned binary_precedence = 30;
switch (g_cur_token) {
default:
return LogErrorP("Expected function name in prototype");
case TOKEN_IDENTIFIER:
fn_name = g_identifier_str;
kind = 0;
NextToken();
break;
case TOKEN_UNARY:
NextToken();
if (!isascii(g_cur_token))
return LogErrorP("Expected unary operator");
fn_name = "unary";
fn_name += (char)g_cur_token;
kind = 1;
NextToken();
break;
case TOKEN_BINARY:
...生成 IR：
Value *UnaryExprAST::Codegen() {
Value *oprand_v = oprand_->Codegen();
if (!oprand_v)
return nullptr;
Function *f = GetFunction(std::string("unary") + opcode_);
if (!f)
return LogErrorV("Unknown unary operator");
g_ir_builder->CreateCall(f, oprand_v, "unopcode");
}
10 可变变量
接下来将支持如下两个功能：
- 通过等号给变量赋值。
- 定义新变量。
比如支持如下示例：
# Define ':' for sequencing: as a low-precedence operator that ignores operands
# and just returns the RHS.
def binary : 1 (x y) y;
# Recursive fib, we could do this before.
def fib(x)
if (x < 3) then
1
else
fib(x-1)+fib(x-2);
# Iterative fib.
def fibi(x)
var a = 1, b = 1, c in
(for i = 3, i < x in
c = a + b :
a = b :
b = c) :
b;
# Call it.
fibi(10);为了改变变量，需要改变变量申请方式，并添加新的操作符。
10.1 修改已有变量
g_named_values 中存放对应符号名称的 LLVM Value*，为了支持变量，需要改为存放符号的”内存地址“。
首先，将 g_named_values 改为映射 AllocaInst*，而不再映射 Value*：
static std::map<std::string, AllocaInst*> g_named_values;需要一个 helper 函数确保在函数的入口块中创建 alloca：
/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
/// the function. This is used for mutable variables etc.
static AllocaInst *CreateEntryBlockAlloca(Function *function,
const std::string &var_name) {
// 创建 IRBuilder，指向了入口块的第一条指令
IRBuilder<> tmp_b(&function->getEntryBlock(),
function->getEntryBlock().begin());
// 创建 alloca
return tmp_b.CreateAlloca(Type::GetDoubleTypepe(g_llvm_context), 0,
var_name.c_str());
}在新模式中，变量位于栈中，所以要使用它们的话，需要从栈中加载：
Value *VariableExprAST::Codegen() {
// Look this variable up in the function.
Value *v = g_named_values[name_];
if (!v)
return LogErrorV("Unknown variable name");
// Load the value.
g_ir_builder->CreateLoad(Type::GetDoubleTypepe(*g_llvm_context), v, name_.c_str());
}接下来需要更新定义变量的地方以使用 alloca，先从 ForExprAST::Codegen() 开始：
Function *function = Builder.GetInsertBlock()->getParent();
// Create an alloca for the variable in the entry block.
AllocaInst *alloca = CreateEntryBlockAlloca(function, var_name_);
// Emit the start code first, without 'variable' in scope.
Value *start_val = start_->Codegen();
if (!start_val)
return nullptr;
// Store the value into the alloca.
g_ir_builder->CreateStore(start_val, alloca);
...
// Compute the end condition.
Value *end_condition = end_->Codegen();
if (!end_condition)
return nullptr;
// Reload, increment, and restore the alloca. This handles the case where
// the body of the loop mutates the variable.
Value *cur_var = g_ir_builder->CreateLoad(Type::GetDoubleTypepe(*g_llvm_context), alloca,
var_name_.c_str());
Value *next_var = g_ir_builder->CreateFAdd(cur_var, step_val, "nextvar");
g_ir_builder->CreateStore(next_var, alloca);
...可以看到，使用了变量后，便不需要再创建 PHI 节点了，而是通过 load/store 访问所需的变量。
支持函数参数变量：
Function *FunctionAST::Codegen() {
...
g_ir_builder->SetInsertPoint(bb);
// Record the function arguments in the g_named_values map.
g_named_values.clear();
for (auto &arg : function->args()) {
// Create an alloca for this variable.
AllocaInst *alloca = CreateEntryBlockAlloca(function, arg.name());
// Store the initial value into the alloca.
g_ir_builder->CreateStore(&arg, alloca);
// Add arguments to variable symbol table.
g_named_values[std::string(arg.name())] = alloca;
}
if (Value *ret_val = body_->Codegen()) {
...为每个参数创建一个 alloca，即在栈上申请内存，然后将参数值保存进去，最后将 alloca 更新到 g_named_values 中。
使用内存保存临时变量的性能比较低，可以使用 mem2reg 优化，使用寄存器存放变量：
// Promote allocas to registers.
g_fpm->add(createPromoteMemoryToRegisterPass());
// Do simple "peephole" optimizations and bit-twiddling optzns.
g_fpm->add(createInstructionCombiningPass());
// Reassociate expressions.
g_fpm->add(createReassociatePass());
...10.2 新的赋值符号
设置优先级：
int main() {
// Install standard binary operators.
// 1 is lowest precedence.
g_binopcode_precedence['='] = 2;
g_binopcode_precedence['<'] = 10;
g_binopcode_precedence['+'] = 20;
g_binopcode_precedence['-'] = 20;生成 IR：
Value *BinaryExprAST::Codegen() {
// Special case '=' because we don't want to emit the LHS as an expression.
if (opcode_ == '=') {
// Assignment requires the LHS to be an identifier.
// 左值必须是个变量
VariableExprAST *lhs = static_cast<VariableExprAST *>(lhs_.get());
if (!lhs)
return LogErrorV("destination of '=' must be a variable");
// Codegen the RHS.
// 生成右值
Value *val = rhs_->Codegen();
if (!val)
return nullptr;
// Look up the name.
Value *variable = g_named_values[lhs->name()];
if (!variable)
return LogErrorV("Unknown variable name");
// 赋值
g_ir_builder->CreateStore(val, variable);
return val;
}
...因为有了赋值符号和变量，所以可运行如下代码：
# Function to print a double.
extern printd(x);
# Define ':' for sequencing: as a low-precedence operator that ignores operands
# and just returns the RHS.
def binary : 1 (x y) y;
def test(x)
printd(x) :
x = 4 :
printd(x);
test(123);10.3 自定义本地变量
添加 var/in，和之前一样，扩展 Kaleidoscope 一般需要扩展：Lexer、Parser、AST 和生成 IR。
扩展 Lexer：
enum Token {
...
// var definition
TOKEN_VAR = -13
...
}
...
static int GetToken() {
...
if (g_identifier_str == "var")
return TOKEN_VAR;
return TOKEN_IDENTIFIER;
...定义 AST 节点：
/// VarExprAST - Expression class for var/in
// 可以一次性定义多个变量
class VarExprAST : public ExprAST {
std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> var_names_;
std::unique_ptr<ExprAST> body_; // 对变量要执行的操作
public:
VarExprAST(
std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> var_names_,
std::unique_ptr<ExprAST> body)
: var_names_(std::move(var_names_)), body_(std::move(body)) {}
Value *Codegen() override;
};扩展 Parser。
先添加到基本表达式中：
/// primary
/// ::= identifierexpr
/// ::= numberexpr
/// ::= parenexpr
/// ::= ifexpr
/// ::= forexpr
/// ::= varexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
switch (g_cur_token) {
...
case TOKEN_VAR:
return ParseVarExpr();
}
}然后定义 ParseVarExpr：
/// varexpr ::= 'var' identifier ('=' expression)?
// (',' identifier ('=' expression)?)* 'in' expression
static std::unique_ptr<ExprAST> ParseVarExpr() {
NextToken(); // eat the var.
std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> var_names;
// At least one variable name is required.
if (g_cur_token != TOKEN_IDENTIFIER)
return LogError("expected identifier after var");
// 解析所有变量
while (1) {
std::string name = g_identifier_str;
NextToken(); // eat identifier.
// Read the opcodetional initializer.
std::unique_ptr<ExprAST> init = nullptr;
if (g_cur_token == '=') {
NextToken(); // eat the '='.
init = ParseExpression();
if (!init)
return nullptr;
}
var_names.push_back(std::make_pair(name, std::move(init)));
// End of var list, exit loop.
if (g_cur_token != ',')
break;
NextToken(); // eat the ','.
if (g_cur_token != TOKEN_IDENTIFIER)
return LogError("expected identifier list after var");
}
// At this point, we have to have 'in'.
if (g_cur_token != TOKEN_IN)
return LogError("expected 'in' keyword after 'var'");
NextToken(); // eat 'in'.
// 针对变量要执行的操作
auto body = ParseExpression();
if (!body)
return nullptr;
return std::make_unique<VarExprAST>(std::move(var_names), std::move(body));
}生成 IR：
Value *VarExprAST::Codegen() {
std::vector<AllocaInst *> old_bindings;
Function *function = Builder.GetInsertBlock()->getParent();
// Register all variables and emit their initializer.
// 初始化每个变量，并注册到符号表中
for (unsigned i = 0, e = var_names_.size(); i != e; ++i) {
const std::string &var_name = var_names_[i].first;
ExprAST *init = var_names[i].second.get();
// Emit the initializer before adding the variable to scope, this prevents
// the initializer from referencing the variable itself, and permits stuff
// like this:
// var a = 1 in
// var a = a in ... # refers to outer 'a'.
Value *init_val;
if (init) {
init_val = init->Codegen();
if (!init_val)
return nullptr;
} else { // If not specified, use 0.0.
init_val = ConstantFP::get(*g_llvm_context, APFloat(0.0));
}
AllocaInst *alloca = CreateEntryBlockAlloca(function, var_name);
g_ir_builder->CreateStore(init_val, alloca);
// Remember the old variable binding so that we can restore the binding when
// we unrecurse.
old_bindings.push_back(g_named_values[var_name]);
// Remember this binding.
g_named_values[var_name] = alloca;
}
// Codegen the body, now that all vars are in scope.
// body 可以访问到所有的自定义变量
Value *body_val = body_->Codegen();
if (!body_val)
return nullptr;
// Pop all our variables from scope.
for (unsigned i = 0, e = var_names_.size(); i != e; ++i)
g_named_values[var_names_[i].first] = old_bindings[i];
// Return the body computation.
return body_val;
}现在可以支持如下示例了：
extern printd(x)
def foo(x)
if x < 3 then
1
else
foo(x - 1) + foo(x - 2)
for i = 1, i < 10, 1.0 in
printd(foo(i))编译运行：
# Compile
clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy
# Run
./toy11 编译生成目标文件
LLVM 支持跨平台编译，可使用“target triple”的字符串指定体系结构，其形式为<arch><sub>-<vendor>-<sys>-<abi>。例如，clang 认为我们的体系结构为：
$ clang --version | grep Target
Target: x86_64-unknown-linux-gnu我们并不需要硬编码体系结构，LLVM 的 sys::getDefaultTargetTriple 会返回当前机器的体系结构：
auto target_triple = sys::getDefaultTargetTriple();TargetMachine 类提供了对机器的完整描述，可以帮助我们配置特定的 feature 或特定的 CPU。比如，我们可以查看支持哪些 feature 和 CPU：
$ llvm-as < /dev/null | llc -march=x86 -mattr=help
Available CPUs for this target:
amdfam10 - Select the amdfam10 processor.
athlon - Select the athlon processor.
athlon-4 - Select the athlon-4 processor.
...
Available features for this target:
16bit-mode - 16-bit mode (i8086).
32bit-mode - 32-bit mode (80386).
3dnow - Enable 3DNow! instructions.
3dnowa - Enable 3DNow! Athlon instructions.
...比如，我们可以使用不包含任何附加 feature 的通用 CPU：
auto cpu = "generic";
auto features = "";
TargetOptions opt;
auto rm = Optional<Reloc::Model>();
auto target_machine = target->createTargetMachine(target_triple, cpu, features, opt, rm);完整代码如下：
int main() {
...
// Run the main "interpreter loop" now.
MainLoop();
// Initialize the target registry etc.
// 初始化生成 IR 的所有 target
// LLVM 并不要求我们链接所有的 target，如果我们只是使用 JIT，可以不组装打印机
InitializeAllTargetInfos();
InitializeAllTargets();
InitializeAllTargetMCs();
InitializeAllAsmParsers();
InitializeAllAsmPrinters();
// 返回当前机器的体系结构
auto target_triple = sys::getDefaultTargetTriple();
g_llvm_module->setTargetTriple(target_triple);
// 获取 Target
std::string error;
auto target = TargetRegistry::lookupTarget(target_triple, error);
// Print an error and exit if we couldn't find the requested target.
// This generally occurs if we've forgotten to initialise the
// TargetRegistry or we have a bogus target triple.
if (!target) {
errs() << error;
return 1;
}
// 使用不包含任何附加 feature 的通用 CPU
auto cpu = "generic";
auto features = "";
TargetOptions opt;
auto rm = Optional<Reloc::Model>();
// TargetMachine 类提供对机器的完整描述
auto target_machine =
target->createTargetMachine(target_triple, cpu, features, opt, rm);
// 配置 Module，这一步不是必须的，但是有助于优化
g_llvm_module->setDataLayout(target_machine->createDataLayout());
g_llvm_module->setTargetTriple(target_triple);
// 目标文件
auto filename = "output.o";
std::error_code err_code;
raw_fd_ostream dest(filename, err_code, sys::fs::OF_None);
if (err_code) {
errs() << "Could not open file: " << err_code.message();
return 1;
}
// 定义一个生成目标的 pass
legacy::PassManager pass;
auto file_type = CGFT_ObjectFile;
if (target_machine->addPassesToEmitFile(pass, dest, nullptr, file_type)) {
errs() << "TheTargetMachine can't emit a file of this type";
return 1;
}
// 运行 pass
pass.run(*g_llvm_module);
dest.flush();
outs() << "Wrote " << filename << "\n";
return 0;
}编译运行：
$ clang++ -g -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs all` -o toy
$ ./toy
ready> def average(x y) (x + y) * 0.5;
^D
Wrote output.o12 添加 Debug 信息
12.1 提前编译模式
我们无法在 JIT 模式下 debug，而是需要进行提前编译（AOT），为此需要一个源码文件。
优化会将多条指令合并成一个，还可能会去掉一些变量，所以为了 debug，我们先去掉优化。
首先，我们将包含顶级语句的匿名函数设为“main”：
auto proto = std::make_unique<PrototypeAST>("main", std::vector<std::string>());然后去掉命令行代码：
@@ -1129,7 +1129,6 @@ static void HandleTopLevelExpression() {
/// top ::= definition | external | expression | ';'
static void MainLoop() {
while (1) {
- fprintf(stderr, "ready> ");
switch (g_cur_token) {
case TOKEN_EOF:
return;
@@ -1184,7 +1183,6 @@ int main() {
g_binop_precedence['*'] = 40; // highest.
// Prime the first token.
- fprintf(stderr, "ready> ");
NextToken();最后，关掉所有的优化和 JIT：
static void HandleTopLevelExpression() {
// Evaluate a top-level expression into an anonymous function.
if (auto fn_ast = ParseTopLevelExpr()) {
if (!fn_ast->codegen()) {
fprintf(stderr, "Error generating code for top level expr");
}
} else {
// Skip token for error recovery.
NextToken();
}
}通过以上改动，我们便可通过如下命令将 Kaleidoscope 编译为一个可执行程序 a.out/a.exe：
Kaleidoscope-Ch9 < fib.ks | & clang -x ir -12.2 DWARF 设置
源码级调试需要使用格式化的数据，以便调试器将二进制文件和机器码转换回源代码。LLVM 中，通常使用 DWARF 格式，一种表示类型、源位置和变量位置的紧凑编码。
与 IRBuilder 类似，DIBuilder 可以为 LLVM IR 文件构建 debug 元数据。我们将使用 DIBuilder 来构建所有 IR 级别的描述。
static std::unique_ptr<DIBuilder> g_di_builder;
struct DebugInfo {
DICompileUnit *compile_unit_; // 编译单元，可以理解为是一个源码文件
DIType *di_type_;
DIType *GetDoubleTypepe();
} g_dbg_info;
// 只需要考虑 double 类型就好了
DIType *DebugInfo::GetDoubleType() {
if (di_type_)
return di_type_;
di_type_ = g_di_builder->createBasicType("double", 64, dwarf::DW_ATE_float);
return di_type_;
}在 main 中构建 module 时：
g_di_builder = new DIBuilder(*g_llvm_module);
g_dbg_info.compile_unit_ = g_di_builder->createCompileUnit(
// 使用了 C 中的常量，
// 因为调试器不一定理解它不识别的语言的调用约定或默认 ABI，
// 所以在 LLVM 代码生成中遵循 C ABI 是最准确的。
// 这确保了我们可以从调试器中调用函数并让它们执行
dwarf::DW_LANG_C,
// 硬编码了文件名
g_di_builder->createFile("fib.ks", "."),
"Kaleidoscope Compiler", 0, "", 0);在 main 的末尾处添加：
g_di_builder->finalize();12.3 函数
接下来需要将一些函数定义添加到 debug 信息中。在 PrototypeAST::Codegen() 中添加几行代码来描述程序的上下文。本例中是“文件”和函数本身的定义。
上下文：
DIFile *unit = DBuilder->createFile(g_dbg_info.compile_unit_.getFilename(),
g_dbg_info.compile_unit_.getDirectory());使用源位置 0（因为 AST 还没有源码位置信息） 并构建函数定义：
DIScope *f_context = unit;
unsigned line_no = p.line();
unsigned scope_line = line_no;
// DISubprogram 中包含了函数的所有元数据
DISubprogram *sp = g_di_builder->createFunction(
f_context, p.name(), StringRef(), unit, line_no,
CreateFunctionType(function->arg_size(), unit), scope_line,
DINode::Flagprototyped, DISubprogram::SPFlagDefinition);
function->setSubprogram(sp);12.4 源位置
debug 最重要的就是精确的源位置。
在 Lexer 中添加源位置信息，跟踪行号和列号：
struct SourceLocation {
int line_;
int col_;
};
static SourceLocation g_cur_loc;
static SourceLocation g_lex_loc = {1, 0};
static int Advance() {
int last_char = getchar();
if (last_char == '\n' || last_char == '\r') {
g_lex_loc.line_++;
g_lex_loc.col_ = 0;
} else
g_lex_loc.col_++;
return last_char;
}在 AST 中添加源位置信息：
class ExprAST {
SourceLocation loc_;
public:
ExprAST(SourceLocation loc = g_cur_loc) : loc_(loc) {}
virtual ~ExprAST() {}
virtual Value *Codegen() = 0;
int line() const { return loc_.line_; }
int col() const { return loc_.col_; }
virtual raw_ostream &Dump(raw_ostream &out, int ind) {
return out << ':' << line() << ':' << col() << '\n';
}
};创建 AST 的时候将源位置信息传进去：
lhs = std::make_unique<BinaryExprAST>(bin_loc, binopcode, std::move(lhs),
std::move(rhs));为了确保每条指令都能获得正确的源位置，每到达一个新位置时都需要告诉 Builder。使用一个 helper 函数来实现此功能：
void DebugInfo::EmitLocation(ExprAST *ast) {
DIScope *scope;
if (lexical_blocks_.empty())
scope = compile_unit_;
else
scope = lexical_blocks_.back();
g_ir_builder->SetCurrentDebugLocation(DILocation::get(
scope->getContext(), ast->line(), ast->col(), scope));
}这既告诉了 main IRBuilder 我们在哪里，也告诉了我们在什么作用域内。在 DebugInfo 创建了一个栈作用域：
std::vector<DIScope *> lexical_blocks_;每当为一个函数生成 code 时，便将该函数的作用域入栈：
// Push the current scope.
g_dbg_info.lexical_blocks_.push_back(sp);结束生成 code 时，将该函数的作用域出栈：
// Pop off the lexical block for the function since we added it
// unconditionally.
g_dbg_info.lexical_blocks_.pop_back();每当为一个新的 AST 生成 code 时，都需要发射位置：
g_dbg_info.EmitLocation(this);12.5 变量
现在有了函数，我们需要能够打印出作用域内的变量。
// Record the function arguments in the g_named_values map.
g_named_values.clear();
unsigned arg_idx = 0;
for (auto &arg : function->args()) {
// Create an alloca for this variable.
AllocaInst *alloca = CreateEntryBlockAlloca(function, arg.name());
// Create a debug descriptor for the variable.
// 给变量一个作用域（sp），源码位置，类型和参数下标
DILocalVariable *des = g_di_builder->createParameterVariable(
sp, arg.name(), ++arg_idx, unit, line_no, g_dbg_info.GetDoubleType(),
true);
// 告诉 IR 我们在 alloca 中获取到一个变量（给出了变量的位置）
// 并在 declare 上为作用域的起始位置设置源位置
g_di_builder->insertDeclare(alloca, des, g_di_builder->createExpression(),
DILocation::get(SP->getContext(), line_no, 0, sp),
g_ir_builder->GetInsertBlock());
// Store the initial value into the alloca.
g_ir_builder.CreateStore(&arg, alloca);
// Add arguments to variable symbol table.
g_named_values[arg.name()] = alloca;
}在 FunctionST::Codegen中，添加了几行，避免为函数序言生成行信息，以便调试器知道在设置断点时跳过这些指令：
// Unset the location for the prologue emission (leading instructions with no
// location in a function are considered part of the prologue and the debugger
// will run past them when breaking on a function)
g_dbg_info.EmitLocation(nullptr);当真正开始为函数体生成 code 时发射位置：
g_dbg_info.EmitLocation(body_.get());有了这些，我们就有了足够的调试信息，可以在函数中设置断点、打印参数变量和调用函数。
编译运行：
# Compile
clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy
# Run
./toy参考
https://llvm.org/docs/tutorial/index.html
宫文学. 编译原理之美.
没有评论