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

发表于 更新于 分类于 Waline：

概述

通过第 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 指令显式地加载全局变量 G 和 H，分别用于 if 语句的 then/else 分支逻辑 cond_true 和 cond_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 仅在某些情况下适用于可变变量：

  • mem2reg 是 alloca 驱动的，其查找 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 的代码生成逻辑。

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

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 对大量的 alloc 和 store 指令进行了优化，将它们优化成寄存器操作。 

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 扩展关键词 var 和 in。这里，我们只需要新增 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