Fork me on GitHub

基于 LLVM 自制编译器(7)——语言扩展:可变变量

概述

通过第 1 章至第 6 章,我们实现了一门简单的函数式编程语言。在这个过程中,我们学习了解析器相关的技术,如何构建并表示 AST,如何构建 LLVM IR,如何对生成代码进行优化,如何使用 JIT 进行编译等等。

Kaleidoscope 是一门函数式编程语言,函数式的特点之一是变量不可重复赋值,这使得 LLVM IR 代码生成非常容易。特别是,函数式编程语言能够直接以 SSA 形式构建 LLVM IR。由于 LLVM 要求输入代码使用 SSA 形式,虽然这是一个非常好的特性,但是会让新手不知道如何为命令式编程语言中的可变变量生成代码。

可变变量的实现难点

那么,为什么可变变量难以构建 SSA 呢?下面,我们先来看一个例子,如下所示。

1
2
3
4
5
6
7
8
9
int G, H;
int test(_Bool Condition) {
int X;
if (Condition)
X = G;
else
X = H;
return X;
}

在例子中,我们有一个 X 变量,其值取决于程序的执行路径。由于这里有两个潜在的目标值,我们需要插入一个 phi 节点来合并这两个值。因此,我们希望生成的 LLVM IR 如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@G = weak global i32 0   ; type of @G is i32*
@H = weak global i32 0 ; type of @H is i32*

define i32 @test(i1 %Condition) {
entry:
br i1 %Condition, label %cond_true, label %cond_false

cond_true:
%X.0 = load i32, i32* @G
br label %cond_next

cond_false:
%X.1 = load i32, i32* @H
br label %cond_next

cond_next:
%X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
ret i32 %X.2
}

在生成的 LLVM IR 通过 load 指令显式地加载全局变量 GH,分别用于 if 语句的 then/else 分支逻辑 cond_truecond_false 基本块。为了将传入值进行合并,cond_next 基本块中的 phi 节点 X.2 根据控制流选择正确值。如果控制流来自 cond_false 基本块,则 X.2 使用 X.1 的值;如果控制流来自 cond_true 基本块,则 X.2 使用 X.0 的值。

这里的问题在于:当对可变变量进行赋值时,由谁来负责插入 phi 节点

事实上,通过编译前端创建并插入 phi 节点是一个非常复杂且低效的操作。相对而言,通过编译前端实现控制流的 phi 节点还算简单。

LLVM 内存模型

那么,我们该如何实现可变变量呢?事实上,我们可以借助内存模型原理来解决这个问题。

我们知道,LLVM 要求所有的寄存器值必须采用 SSA 形式,但是 LLVM 并不要求内存对象必须采用 SSA 形式。

基于此,我们可以为函数中的每个可变对象创建一个栈变量(它存在于内存中,因为它在栈上)。为了理解这种方法,我们首先介绍一下 LLVM 如何是表示栈变量的。

在 LLVM 中,所有内存访问都是显式的,使用 load / store 指令,没有(或不需要)address-of 运算符。注意,@G / @H 全局变量的类型实际上是 i32*,即使该变量被定义为 i32。 这意味着 @G 为全局数据区域中的 i32 定义了内存空间,但它的名称实际上是指该内存空间的地址。 栈变量的工作方式类似,只是它们并不使用全局变量进行声明,而使用 alloca 指令进行声明

1
2
3
4
5
6
7
8
define i32 @example() {
entry:
%X = alloca i32 ; type of %X is i32*.
...
%tmp = load i32, i32* %X ; load the stack value %X from the stack.
%tmp2 = add i32 %tmp, 1 ; increment it
store i32 %tmp2, i32* %X ; store it back
...

上述代码展示了如何在 LLVM IR 中声明和操作栈变量。使用 alloca 指令分配的栈内存是完全通用的,我们可以将栈槽的地址传递给函数,也可以将其存储在其他变量中。下面,我们通过 alloca 指令来代替使用 phi 节点,具体如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@G = weak global i32 0   ; type of @G is i32*
@H = weak global i32 0 ; type of @H is i32*

define i32 @test(i1 %Condition) {
entry:
%X = alloca i32 ; type of %X is i32*.
br i1 %Condition, label %cond_true, label %cond_false

cond_true:
%X.0 = load i32, i32* @G
store i32 %X.0, i32* %X ; Update X
br label %cond_next

cond_false:
%X.1 = load i32, i32* @H
store i32 %X.1, i32* %X ; Update X
br label %cond_next

cond_next:
%X.2 = load i32, i32* %X ; Read X
ret i32 %X.2
}

通过基于栈变量的方式,我们无需创建 phi 节点也能够处理任意可变变量,具体包含以下几个点。

  • 将可变变量转换成栈变量
  • 将读取可变变量转换成加载栈变量
  • 将更新可变变量转换成存储栈变量
  • 将读取可变变量地址转换成读取栈变量地址

简而言之,我们通过一个额外的栈变量来存储不同分支所计算得到值,从而避免手动构建 phi 节点。

虽然基于栈变量的方法解决了我们当前的问题,但是它引入了另一个问题。很显然,这种情况下,对于非常简单和常见的操作,我们也会引入了大量的栈操作,从而引发性能问题。幸运的是,LLVM 优化器有一个名为 mem2reg 的优化通道能够对此进行优化,该优化通道能将类似的栈分配提优化为寄存器,并在适当的时候插入 phi 节点。例如,我们通过执行 mem2reg Pass,可以得到如下所示的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
$ llvm-as < example.ll | opt -mem2reg | llvm-dis
@G = weak global i32 0
@H = weak global i32 0

define i32 @test(i1 %Condition) {
entry:
br i1 %Condition, label %cond_true, label %cond_false

cond_true:
%X.0 = load i32, i32* @G
br label %cond_next

cond_false:
%X.1 = load i32, i32* @H
br label %cond_next

cond_next:
%X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
ret i32 %X.01
}

mem2reg Pass 实现了用于构造 SSA 的标准 迭代支配边界(Iterated Dominance Frontier)算法,并包含大量优化手段。mem2reg 优化通道可以用来处理可变变量,我们强烈建议使用它。注意,mem2reg 仅在某些情况下适用于可变变量:

  • mem2regalloca 驱动的,其查找 alloca 指令,如果可以处理,则对它们进行优化。它不适用于全局变量或堆分配。
  • mem2reg 仅在函数的入口块中查找 alloca 指令。在入口块即保证了 alloca 只会执行一次,这样能够使分析更加简单。
  • mem2reg 只优化用于直接加载和存储的 alloca 指令。如果将栈对象的地址传递给函数,或者涉及任何指针运算,则不会优化 alloca
  • mem2reg 仅适用于一等类型的值的分配(例如指针、标量和向量),并且仅当分配的数组大小为 1(或 .ll 文件丢失)时。 mem2reg 不能将结构体或数组优化为寄存器。 注意,LLVM 还有其他更加强大的优化通道,如:sroa Pass,其能够在很多情况下可以优化结构体、联合体、数组。

我们强烈建议使用上述方式来构建 SSA,通过额外的栈变量避免手动构建 phi 节点,然后使用 LLVM 优化通道进行优化,内部自动构建 phi 节点,如:mem2reg Pass。推荐使用这种方式主要有几个原因:

  • 具备良好的验证和测试。经典的 Clang 编译器就采用该方法来处理局部可变变量。
  • 构建速度快。mem2reg 支持在多种场景下进行加速构建。
  • 支持生成调试所需信息。LLVM 中的调试信息依赖于公开变量的地址,基于变量地址才能将调试信息附加至变量中。这种技术与这种调试信息风格非常自然地吻合。

这种方式能够让我们的编译前端的启动和运行变得更加容易,并且实现起来非常简单。下面,让我们在 Kaleidoscope 中扩展可变变量!

可变变量

上文,我们介绍了可变变量的实现难点,以及一种基于栈变量的解决方案。接下来,我们来进行实战,为 Kaleidoscope 进行语言扩展,支持可变变量。

为了支持可变变量,我们期望实现两个功能:

  • 基于 = 运算符实现已有变量可变
  • 基于 var/in 关键词实现局部变量定义

如下所示,是我们期望实现的最终目标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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);

已有变量可变

首先,我们来实现第一个功能——已有变量可变。

在我们之前的实现中,Kaleidoscope 在代码生成时的符号表是由 NamedValues 负责管理。符号表存储的键值对,键位变量名,值为 LLVM Value*

为了实现已有变量可变,我们需要修改一下 NamedValues 存储的键值对的类型,使得 NamedValues 能够保存可变变量的内存位置。

目前,Kaleidoscope 只支持两种类型的变量:函数的传入参数、for 循环的归纳变量。为了保持一致性,除了其他用户定义的变量外,我们还允许对这些变量进行更新。 这意味着它们都需要占用内存空间。

对此,我们首先对符号表 NamedValues 进行修改,将键值对中值的类型修改为 AllocaInst*

1
static std::map<std::string, AllocaInst*> NamedValues;

由于我们需要创建 alloca 指令,我们还需要一个辅助函数来保证 alloca 指令在函数入口块创建。

1
2
3
4
5
6
7
8
9
/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
/// the function. This is used for mutable variables etc.
static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
const std::string &VarName) {
IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
TheFunction->getEntryBlock().begin());
return TmpB.CreateAlloca(Type::getDoubleTy(TheContext), 0,
VarName.c_str());
}

上述代码创建了一个 IRBuilder 对象,它指向入口块的第一条指令(.begin())。然后创建一个具有指定名称的 alloca 并返回。由于 Kaleidoscope 中的所有值都是双精度类型,所以不需要传入要使用的类型。

接下来,我们分别对变量表达式、for 表达式、函数表达式的代码生成逻辑进行修改,从而支持已有变量可变。

VariableExprAST 代码生成

首先,对于变量,我们需要修改引用方式。基于栈变量的实现中,变量存储于栈中,因此,我们必须通过加载栈槽,从而引用栈变量。

1
2
3
4
5
6
7
8
9
Value *VariableExprAST::codegen() {
// Look this variable up in the function.
AllocaInst *A = NamedValues[Name];
if (!A)
return LogErrorV("Unknown variable name");

// Load the value.
return Builder->CreateLoad(A->getAllocatedType(), A, Name.c_str());
}

ForExprAST 代码生成

VariableExprAST 实现了栈变量的读取逻辑,那么如何实现写入逻辑呢?由于 for 表达式包含了归纳变量,因此,我们首先了修改 ForExprAST 的代码生成逻辑。

如下所示,首先,我们在入口块创建一个栈变量,当设置初始值时,通过 BuilderCreateStore() 方法将初始值写入栈变量。当归纳变量迭代时,通过 BuilderCreateLoad() 方法读取栈变量,并与步长值相加,然后再写入栈变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Value *ForExprAST::codegen() {
Function *TheFunction = Builder->GetInsertBlock()->getParent();

// Create an alloca for the variable in the entry block.
AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);

// Emit the start code first, without 'variable' in scope.
Value *StartVal = Start->codegen();
if (!StartVal)
return nullptr;

// Store the value into the alloca.
Builder->CreateStore(StartVal, Alloca);

...

// Compute the end condition.
Value *EndCond = End->codegen();
if (!EndCond)
return nullptr;

// Reload, increment, and restore the alloca. This handles the case where
// the body of the loop mutates the variable.
Value *CurVar =
Builder->CreateLoad(Alloca->getAllocatedType(), Alloca, VarName.c_str());
Value *NextVar = Builder->CreateFAdd(CurVar, StepVal, "nextvar");
Builder->CreateStore(NextVar, Alloca);

...

}

FunctionAST 代码生成

为了让函数的入参支持可变,我们还需要对 FunctionAST 的代码逻辑进行修改。如下所示,我们遍历函数的入参,为每一个参数创建一个栈变量,并存储初始值,同时将入参的变量名写入符号表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Function *FunctionAST::codegen() {
...

Builder->SetInsertPoint(BB);

// Record the function arguments in the NamedValues map.
NamedValues.clear();
for (auto &Arg : TheFunction->args()) {
// Create an alloca for this variable.
AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, Arg.getName());

// Store the initial value into the alloca.
Builder->CreateStore(&Arg, Alloca);

// Add arguments to variable symbol table.
NamedValues[std::string(Arg.getName())] = Alloca;
}

if (Value *RetVal = Body->codegen()) {
...
}

优化通道

最后,我们向通道管理器注册一部分优化通道,包括 mem2reg,从而能够生成优化后的 LLVM IR。

1
2
3
4
5
6
7
// Promote allocas to registers.
TheFPM->add(createPromoteMemoryToRegisterPass());
// Do simple "peephole" optimizations and bit-twiddling optzns.
TheFPM->add(createInstructionCombiningPass());
// Reassociate expressions.
TheFPM->add(createReassociatePass());
...

LLVM IR 对比

我们以递归版本的 fib 函数作为测试用例,来对比 mem2reg 优化通道执行前后的 LLVM IR。

1
2
3
4
5
def fib(x)
if (x < 3) then
1
else
fib(x-1)+fib(x-2);

如下所示,为执行 mem2reg 前生成的 LLVM IR。其中,只有一个函数入参变量 x。在入口块中,LLVM 创建了一个 alloca 指令,并将初始输入值存入其中。 对变量的每个引用都会从栈中进行加载。由于我们没有修改 if/then/else 表达式,所以在 ifcont 基本块中仍然插入了一个 phi 节点。对于 if/then/else 表达式,其实我们也可以为它创建 alloca 指令,不过,为它构建一个 phi 节点反而会更容易,所以这里我们仍然手动构建 phi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
define double @fib(double %x) {
entry:
%x1 = alloca double
store double %x, double* %x1
%x2 = load double, double* %x1
%cmptmp = fcmp ult double %x2, 3.000000e+00
%booltmp = uitofp i1 %cmptmp to double
%ifcond = fcmp one double %booltmp, 0.000000e+00
br i1 %ifcond, label %then, label %else

then: ; preds = %entry
br label %ifcont

else: ; preds = %entry
%x3 = load double, double* %x1
%subtmp = fsub double %x3, 1.000000e+00
%calltmp = call double @fib(double %subtmp)
%x4 = load double, double* %x1
%subtmp5 = fsub double %x4, 2.000000e+00
%calltmp6 = call double @fib(double %subtmp5)
%addtmp = fadd double %calltmp, %calltmp6
br label %ifcont

ifcont: ; preds = %else, %then
%iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
ret double %iftmp
}

如下所示,为执行 mem2reg 后生成的 LLVM IR。很明显,mem2reg 对大量的 allocstore 指令进行了优化,将它们优化成寄存器操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
define double @fib(double %x) {
entry:
%cmptmp = fcmp ult double %x, 3.000000e+00
%booltmp = uitofp i1 %cmptmp to double
%ifcond = fcmp one double %booltmp, 0.000000e+00
br i1 %ifcond, label %then, label %else

then:
br label %ifcont

else:
%subtmp = fsub double %x, 1.000000e+00
%calltmp = call double @fib(double %subtmp)
%subtmp5 = fsub double %x, 2.000000e+00
%calltmp6 = call double @fib(double %subtmp5)
%addtmp = fadd double %calltmp, %calltmp6
br label %ifcont

ifcont: ; preds = %else, %then
%iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
ret double %iftmp
}

如下所示,为所有优化通道执行完毕之后的 LLVM IR。很显然,LLVM IR 得到了进一步的优化。其中,simplifycfg 优化通道将返回指令拷贝至 else 基本块的末尾,从而消除部分分支代码和 phi 节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
define double @fib(double %x) {
entry:
%cmptmp = fcmp ult double %x, 3.000000e+00
%booltmp = uitofp i1 %cmptmp to double
%ifcond = fcmp ueq double %booltmp, 0.000000e+00
br i1 %ifcond, label %else, label %ifcont

else:
%subtmp = fsub double %x, 1.000000e+00
%calltmp = call double @fib(double %subtmp)
%subtmp5 = fsub double %x, 2.000000e+00
%calltmp6 = call double @fib(double %subtmp5)
%addtmp = fadd double %calltmp, %calltmp6
ret double %addtmp

ifcont:
ret double 1.000000e+00
}

赋值运算符

至此,我们已经将符号表的引用修改为栈变量。接下来,我们来添加赋值运算符 =,从而实现变量可变。

基于当前的框架,添加一个新的赋值运算符非常简单。首先,我们对赋值运算符设置优先级。

1
2
3
4
5
6
7
int main() {
// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['='] = 2;
BinopPrecedence['<'] = 10;
BinopPrecedence['+'] = 20;
BinopPrecedence['-'] = 20;

由于赋值运算符是一个二元运算符,且赋值运算符已经设置了运算符优先级。因此,我们只需要修改 BinaryExprAST 的代码生成逻辑,使其支持赋值运算符。具体如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Value *BinaryExprAST::codegen() {
// Special case '=' because we don't want to emit the LHS as an expression.
if (Op == '=') {
// Assignment requires the LHS to be an identifier.
// This assume we're building without RTTI because LLVM builds that way by
// default. If you build LLVM with RTTI this can be changed to a
// dynamic_cast for automatic error checking.
VariableExprAST *LHSE = static_cast<VariableExprAST *>(LHS.get());
if (!LHSE)
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 = NamedValues[LHSE->getName()];
if (!Variable)
return LogErrorV("Unknown variable name");

Builder->CreateStore(Val, Variable);
return Val;
}
...
}

与其他二元运算符不同,赋值运算符不遵循 “生成 LHS,生成 RHS,再进行计算” 的模型。因此,对于赋值运算符,我们要对它进行特殊处理。此外,赋值运算符要求 LHS 必须是一个变量,比如:(x+1) = expr 语句是无效的,x = expr 是有效的。

因此,BinaryExprAST::codegen 的解析逻辑中,会先检查 LHS 是否有效。如果有效,则将 LHS 注册至符号表并进一步计算 RHS,最终将 RHS 的结果存入变量。

测试

至此,我们为 Kaleidoscope 扩展支持了变量可变的能力。下面,我们来进行一个简单的测试。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 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);

当输入测试代码后,程序先打印了 123,然后打印了 4,运行结果证明了变量的值发生了变化!

局部变量定义

我们的第二个目标功能是:基于 var/in 关键词实现局部变量定义,使其能够编写如下所示的代码。

1
2
3
4
5
6
7
def fibi(x)
var a = 1, b = 1, c in
(for i = 3, i < x in
c = a + b :
a = b :
b = c) :
b;

下面,我们分别对编译器的各个部分进行扩展。

词法分析器扩展

首先,我们要为 Kaleidoscope 扩展关键词 varin。这里,我们只需要新增 var 关键词即可,in 关键词在 for/in 语句中已经支持了。具体扩展如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
enum Token {
...
// var definition
tok_var = -13
...
}
...
static int gettok() {
...
if (IdentifierStr == "in")
return tok_in;
if (IdentifierStr == "binary")
return tok_binary;
if (IdentifierStr == "unary")
return tok_unary;
if (IdentifierStr == "var")
return tok_var;
return tok_identifier;
...

AST 扩展

为了表示 var/in 语句,我们定义一个表达式子类的 AST 节点类型 VarExprAST,具体如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
/// VarExprAST - Expression class for var/in
class VarExprAST : public ExprAST {
std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;
std::unique_ptr<ExprAST> Body;

public:
VarExprAST(std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames,
std::unique_ptr<ExprAST> Body)
: VarNames(std::move(VarNames)), Body(std::move(Body)) {}

Value *codegen() override;
};

我们扩展的 var/in 允许一次定义一组变量,并且每个变量都可以有一个初始值。因此,我们通过 VarNames 数组来存储多个变量。此外,var/in 支持设置一个表达式体,用于对变量进行初始化。同时,表达式体能够访问 var/in 所定义的变量。

解析器扩展

接下来,我们为 var/in 表达式定义解析函数,具体如下所示。在 ParseVarExpr 解析函数中,我们首先对 token 进行遍历,将局部变量存入 VarNames 中。然后解析表达式体,将其存入 Body 中。最后返回表达式的 AST 节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
static std::unique_ptr<ExprAST> ParseVarExpr() {
getNextToken(); // eat the var.

std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames;

// At least one variable name is required.
if (CurTok != tok_identifier)
return LogError("expected identifier after var");

while (true) {
std::string Name = IdentifierStr;
getNextToken(); // eat identifier.

// Read the optional initializer.
std::unique_ptr<ExprAST> Init = nullptr;
if (CurTok == '=') {
getNextToken(); // eat the '='.

Init = ParseExpression();
if (!Init)
return nullptr;
}

VarNames.push_back(std::make_pair(Name, std::move(Init)));

// End of var list, exit loop.
if (CurTok != ',')
break;
getNextToken(); // eat the ','.

if (CurTok != tok_identifier)
return LogError("expected identifier list after var");
}

// At this point, we have to have 'in'.
if (CurTok != tok_in)
return LogError("expected 'in' keyword after 'var'");
getNextToken(); // eat 'in'.

auto Body = ParseExpression();
if (!Body)
return nullptr;

return std::make_unique<VarExprAST>(std::move(VarNames), std::move(Body));
}

与其他表达式相同,我们也把 ParseForExpr 解析函数方法插入到主表达式的解析函数 ParsePrimary 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/// primary
/// ::= identifierexpr
/// ::= numberexpr
/// ::= parenexpr
/// ::= ifexpr
/// ::= forexpr
/// ::= varexpr
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();
case tok_if:
return ParseIfExpr();
case tok_for:
return ParseForExpr();
case tok_var:
return ParseVarExpr();
}
}

代码生成

下面,我们来为 VarExprAST 实现代码生成的逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Value *VarExprAST::codegen() {
std::vector<AllocaInst *> OldBindings;

Function *TheFunction = Builder->GetInsertBlock()->getParent();

// Register all variables and emit their initializer.
for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
const std::string &VarName = VarNames[i].first;
ExprAST *Init = VarNames[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 *InitVal;
if (Init) {
InitVal = Init->codegen();
if (!InitVal)
return nullptr;
} else { // If not specified, use 0.0.
InitVal = ConstantFP::get(*TheContext, APFloat(0.0));
}

AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
Builder->CreateStore(InitVal, Alloca);

// Remember the old variable binding so that we can restore the binding when
// we unrecurse.
OldBindings.push_back(NamedValues[VarName]);

// Remember this binding.
NamedValues[VarName] = Alloca;
}

// Codegen the body, now that all vars are in scope.
Value *BodyVal = Body->codegen();
if (!BodyVal)
return nullptr;

// Pop all our variables from scope.
for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
NamedValues[VarNames[i].first] = OldBindings[i];

// Return the body computation.
return BodyVal;
}

VarExprAST 代码生成的基本逻辑包括以下几部分:

  • 遍历所有变量,对于每个变量,将其存入符号表,并使用 OldBindings 保存旧值,因为存在嵌套的同名变量。
  • 对于每个变量,构造对应的 alloca 指令,并更新符号表,使该变量指向生成的 alloca 指令,即 AllocaInst
  • 当所有变量都保存至符号表后,对 var/in 语句中的表达式体进行代码生成。
  • 在返回之前,通过 OldBindings 恢复旧值。

通过这部分的扩展,我们实现了在作用域中定义局部变量的功能。类似的,我们也可以对实现的程序进行测试,输入迭代版本的 fib 函数,查看最终的执行结果以及生成的 LLVM IR。

总结

通过本章,我们进一步扩展了 Kaleidoscope 语言,实现了可变变量的能力。至此,Kaleidoscope 已经具备了工业级编程语言的基本雏形。下一章,我们来进一步增加 Kaleidoscope 的能力。

参考

  1. Kaleidoscope: Extending the Language: Mutable Variables
欣赏此文?求鼓励,求支持!