7. Kaleidoscope: 扩展语言：可变变量¶
7.1. 第 7 章 导言¶
欢迎来到“使用 LLVM 实现语言”教程的第 7 章。在第 1 章到第 6 章中，我们构建了一个非常值得尊敬的，虽然简单，但仍然是函数式编程语言。在我们的旅程中，我们学习了一些解析技术，如何构建和表示 AST，如何构建 LLVM IR，以及如何优化结果代码以及 JIT 编译它。
虽然 Kaleidoscope 作为一个函数式语言很有趣，但事实上它是函数式的，这使得为其生成 LLVM IR “太容易”了。特别是，函数式语言使得直接以 SSA 形式构建 LLVM IR 非常容易。由于 LLVM 要求输入代码为 SSA 形式，这是一个非常好的特性，并且对于新手来说，如何为具有可变变量的命令式语言生成代码通常是不清楚的。
本章的简短（且令人高兴的）总结是，您的前端无需构建 SSA 形式：LLVM 提供了高度调整和良好测试的支持，尽管它的工作方式对某些人来说有点出乎意料。
7.2. 为什么这是一个难题？¶
为了理解为什么可变变量会在 SSA 构建中引起复杂性，请考虑这个极其简单的 C 示例
int G, H;
int test(_Bool Condition) {
int X;
if (Condition)
X = G;
else
X = H;
return X;
}
在这种情况下，我们有变量 “X”，其值取决于程序中执行的路径。由于在 return 指令之前 X 有两个不同的可能值，因此插入一个 PHI 节点以合并这两个值。我们希望此示例的 LLVM IR 看起来像这样
@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
}
在此示例中，从 G 和 H 全局变量的加载在 LLVM IR 中是显式的，并且它们存在于 if 语句的 then/else 分支（cond_true/cond_false）中。为了合并传入的值，cond_next 块中的 X.2 phi 节点根据控制流的来源选择要使用的正确值：如果控制流来自 cond_false 块，则 X.2 获取 X.1 的值。或者，如果控制流来自 cond_true，则它获取 X.0 的值。本章的目的不是解释 SSA 形式的细节。有关更多信息，请参阅许多 在线参考资料之一。
本文的问题是“当降低对可变变量的赋值时，谁放置 phi 节点？”。这里的问题是 LLVM *要求* 其 IR 必须是 SSA 形式：没有“非 SSA”模式。但是，SSA 构建需要非平凡的算法和数据结构，因此对于每个前端来说，都必须重现此逻辑，这既不方便又浪费。
7.3. LLVM 中的内存¶
这里的“技巧”是，虽然 LLVM 确实要求所有寄存器值都采用 SSA 形式，但它不要求（或允许）内存对象采用 SSA 形式。在上面的示例中，请注意从 G 和 H 的加载是对 G 和 H 的直接访问：它们没有被重命名或版本化。这与其他一些尝试对内存对象进行版本控制的编译器系统不同。在 LLVM 中，不是将内存的数据流分析编码到 LLVM IR 中，而是通过 分析 Pass 来处理，这些 Pass 是按需计算的。
考虑到这一点，高级思想是，我们希望为函数中的每个可变对象创建一个栈变量（它驻留在内存中，因为它在栈上）。为了利用这个技巧，我们需要讨论 LLVM 如何表示栈变量。
在 LLVM 中，所有内存访问都通过显式的 load/store 指令进行，并且经过精心设计，不需要（或需要）“address-of”运算符。请注意，@G/@H 全局变量的类型实际上是 “i32*”，即使该变量定义为 “i32”。这意味着 @G 在全局数据区域中为 i32 定义了 *空间*，但其 *名称* 实际上是指该空间的地址。栈变量的工作方式相同，只是它们不是用全局变量定义声明的，而是用 LLVM alloca 指令 声明的
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 节点
@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 节点
每个可变变量都变成一个栈分配。
每次读取变量都会变成从栈的加载。
每次更新变量都会变成对栈的存储。
获取变量的地址只是直接使用栈地址。
虽然这个解决方案解决了我们眼前的难题，但它引入了另一个难题：对于非常简单和常见的操作，我们现在显然引入了大量的栈流量，这是一个主要的性能问题。幸运的是，LLVM 优化器有一个名为 “mem2reg” 的高度优化的 Pass 来处理这种情况，将像这样的 allocas 提升到 SSA 寄存器中，并根据需要插入 Phi 节点。例如，如果您通过该 Pass 运行此示例，您将得到
$ llvm-as < example.ll | opt -passes=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 形式的标准 “迭代支配边界” 算法，并具有许多优化，可以加速（非常常见的）退化情况。mem2reg 优化 Pass 是处理可变变量的答案，我们强烈建议您依赖它。请注意，mem2reg 仅在某些情况下适用于变量
mem2reg 是 alloca 驱动的：它查找 allocas，如果可以处理它们，则提升它们。它不适用于全局变量或堆分配。
mem2reg 仅在函数的入口块中查找 alloca 指令。位于入口块中保证了 alloca 只执行一次，这使得分析更简单。
mem2reg 仅提升其用途是直接加载和存储的 allocas。如果栈对象的地址传递给函数，或者如果涉及任何有趣的指针运算，则不会提升 alloca。
mem2reg 仅适用于 first class 值（例如指针、标量和向量）的 allocas，并且仅当分配的数组大小为 1（或 .ll 文件中缺少）时才适用。mem2reg 无法将结构体或数组提升为寄存器。请注意，“sroa” Pass 更强大，可以在许多情况下提升结构体、“联合”和数组。
对于大多数命令式语言来说，所有这些属性都很容易满足，我们将在下面的 Kaleidoscope 中对此进行说明。您可能要问的最后一个问题是：我应该为我的前端费心做这些无意义的事情吗？如果我直接进行 SSA 构建，避免使用 mem2reg 优化 Pass，岂不是更好？简而言之，我们强烈建议您使用此技术来构建 SSA 形式，除非有极其充分的理由不这样做。使用此技术是
经过验证且经过良好测试：clang 使用此技术处理局部可变变量。因此，LLVM 最常见的客户端正在使用此技术来处理他们的大部分变量。您可以确信，bug 会很快被发现并尽早修复。
极其快速：mem2reg 有许多特殊情况，使其在常见情况下以及完全通用情况下都很快。例如，它对仅在单个块中使用的变量、仅具有一个赋值点的变量、避免插入不需要的 phi 节点的良好启发式方法等具有快速路径。
调试信息生成所需：LLVM 中的调试信息 依赖于公开变量的地址，以便可以将调试信息附加到它。这种技术与这种风格的调试信息非常自然地吻合。
如果其他方法都不行，这会使您的前端更容易启动和运行，并且非常容易实现。现在让我们用可变变量扩展 Kaleidoscope！
7.4. Kaleidoscope 中的可变变量¶
现在我们知道了我们要解决的问题类型，让我们看看这在我们的小型 Kaleidoscope 语言的上下文中是什么样的。我们将添加两个功能
使用 ‘=’ 运算符修改变量的能力。
定义新变量的能力。
虽然第一项才是本文的真正目的，但我们只有用于传入参数以及归纳变量的变量，并且重新定义这些变量只能做到这种程度:)。此外，无论您是否要修改它们，定义新变量的能力都是有用的。这是一个激励性的例子，展示了我们如何使用这些
# 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);
为了修改变量，我们必须更改我们现有的变量以使用 “alloca 技巧”。一旦我们有了这个，我们将添加我们的新运算符，然后扩展 Kaleidoscope 以支持新的变量定义。
7.5. 调整现有变量以进行修改¶
Kaleidoscope 中的符号表在代码生成时由 ‘NamedValues’ 映射管理。此映射当前跟踪保存命名变量的双精度值的 LLVM “Value*”。为了支持修改，我们需要稍微更改一下，以便 NamedValues 保存相关变量的 *内存位置*。请注意，此更改是重构：它更改了代码的结构，但（本身）不会更改编译器的行为。所有这些更改都隔离在 Kaleidoscope 代码生成器中。
在 Kaleidoscope 开发的这一点上，它仅支持两个方面的变量：函数的传入参数和 ‘for’ 循环的归纳变量。为了保持一致性，除了其他用户定义的变量之外，我们还将允许修改这些变量。这意味着这些都需要内存位置。
为了开始 Kaleidoscope 的转换，我们将更改 NamedValues 映射，使其映射到 AllocaInst* 而不是 Value*。一旦我们这样做，C++ 编译器将告诉我们需要更新代码的哪些部分
static std::map<std::string, AllocaInst*> NamedValues;
此外，由于我们将需要创建这些 allocas，我们将使用一个辅助函数来确保 allocas 在函数的入口块中创建
/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
/// the function. This is used for mutable variables etc.
static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
StringRef VarName) {
IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
TheFunction->getEntryBlock().begin());
return TmpB.CreateAlloca(Type::getDoubleTy(*TheContext), nullptr,
VarName);
}
这段有趣的代码创建了一个 IRBuilder 对象，该对象指向入口块的第一个指令 (.begin())。然后，它使用预期的名称创建一个 alloca 并返回它。由于 Kaleidoscope 中的所有值都是双精度浮点数，因此无需传入要使用的类型。
有了这个，我们想要做的第一个功能更改属于变量引用。在我们的新方案中，变量驻留在栈上，因此为对它们的引用生成代码实际上需要产生从栈槽的加载
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());
}
如您所见，这非常简单明了。现在我们需要更新定义变量的事物以设置 alloca。我们将从 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);
...
此代码与在我们允许可变变量之前的代码几乎相同。最大的区别在于我们不再需要构造 PHI 节点，并且我们使用 load/store 来根据需要访问变量。
为了支持可变的参数变量，我们还需要为它们创建 allocas。此代码也很简单
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()) {
...
对于每个参数，我们创建一个 alloca，将函数的输入值存储到 alloca 中，并将 alloca 注册为参数的内存位置。此方法在 FunctionAST::codegen() 设置函数的入口块后立即调用。
最后缺少的部分是添加 mem2reg Pass，这使我们能够再次获得良好的代码生成
// Promote allocas to registers.
TheFPM->addPass(PromotePass());
// Do simple "peephole" optimizations and bit-twiddling optzns.
TheFPM->addPass(InstCombinePass());
// Reassociate expressions.
TheFPM->addPass(ReassociatePass());
...
有趣的是，看看 mem2reg 优化运行之前和之后的代码是什么样的。例如，这是我们的递归 fib 函数的优化前/后代码。优化前
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
}
这里只有一个变量（x，输入参数），但您仍然可以看到我们使用的极其简单的代码生成策略。在入口块中，创建一个 alloca，并将初始输入值存储到其中。每次引用变量都会从栈中重新加载。此外，请注意我们没有修改 if/then/else 表达式，因此它仍然插入一个 PHI 节点。虽然我们可以为其创建一个 alloca，但实际上创建 PHI 节点更容易，因此我们仍然只创建 PHI。
这是 mem2reg Pass 运行后的代码
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
}
对于 mem2reg 来说，这是一个微不足道的例子，因为没有变量的重新定义。展示这一点是为了缓解您对插入如此明显的低效率的担忧:)。
在其余优化器运行后，我们得到
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
}
在这里，我们看到 simplifycfg Pass 决定将 return 指令克隆到 ‘else’ 块的末尾。这使其能够消除一些分支和 PHI 节点。
现在所有符号表引用都已更新为使用栈变量，我们将添加赋值运算符。
7.6. 新的赋值运算符¶
使用我们当前的框架，添加新的赋值运算符非常简单。我们将像解析任何其他二元运算符一样解析它，但在内部处理它（而不是允许用户定义它）。第一步是设置优先级
int main() {
// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['='] = 2;
BinopPrecedence['<'] = 10;
BinopPrecedence['+'] = 20;
BinopPrecedence['-'] = 20;
现在解析器知道二元运算符的优先级，它会处理所有解析和 AST 生成。我们只需要为赋值运算符实现代码生成。看起来像这样
Value *BinaryExprAST::codegen() {
// Special case '=' because we don't want to emit the LHS as an expression.
if (Op == '=') {
// 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");
与其余的二元运算符不同，我们的赋值运算符不遵循 “emit LHS, emit RHS, do computation” 模型。因此，在处理其他二元运算符之前，它被作为特殊情况处理。另一个奇怪的事情是它要求 LHS 必须是变量。 иметь “(x+1) = expr” 是无效的 - 只允许像 “x = expr” 这样的内容。
// 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;
}
...
一旦我们有了变量，为赋值生成代码就很简单：我们发出赋值的 RHS，创建一个存储，并返回计算出的值。返回值允许链式赋值，例如 “X = (Y = Z)”。
现在我们有了赋值运算符，我们可以修改循环变量和参数。例如，我们现在可以运行这样的代码
# 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”，表明我们确实修改了该值！好的，我们现在已经正式实现了我们的目标：在一般情况下，要使其工作，需要 SSA 构建。但是，为了真正有用，我们希望能够定义我们自己的局部变量，让我们接下来添加它！
7.7. 用户定义的局部变量¶
添加 var/in 就像我们对 Kaleidoscope 所做的任何其他扩展一样：我们扩展词法分析器、语法分析器、AST 和代码生成器。添加我们的新 ‘var/in’ 构造的第一步是扩展词法分析器。和以前一样，这非常简单，代码如下所示
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，它看起来像这样
/// 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 定义的变量。
有了这个，我们可以定义语法分析器片段。我们做的第一件事是将其添加为主要表达式
/// 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();
}
}
接下来我们定义 ParseVarExpr
/// varexpr ::= 'var' identifier ('=' expression)?
// (',' identifier ('=' expression)?)* 'in' expression
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");
此代码的第一部分将标识符/expr 对列表解析为本地 VarNames 向量。
while (true) {
std::string Name = IdentifierStr;
getNextToken(); // eat identifier.
// Read the optional initializer.
std::unique_ptr<ExprAST> Init;
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");
}
解析完所有变量后，我们然后解析主体并创建 AST 节点
// 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));
}
现在我们可以解析和表示代码了，我们需要支持为其生成 LLVM IR。此代码以
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();
基本上，它循环遍历所有变量，一次安装一个变量。对于我们放入符号表中的每个变量，我们都会记住我们在 OldBindings 中替换的先前值。
// 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;
}
这里的注释比代码还多。基本思想是我们发出初始化器，创建 alloca，然后更新符号表以指向它。将所有变量安装到符号表中后，我们评估 var/in 表达式的主体
// 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;
}
所有这一切的最终结果是，我们获得了正确范围的变量定义，并且我们甚至（微不足道地）允许修改它们:)。
有了这个，我们完成了我们着手要做的事情。我们从介绍中得到的漂亮的迭代 fib 示例可以正常编译和运行。mem2reg Pass 将我们所有的栈变量优化为 SSA 寄存器，在需要的地方插入 PHI 节点，并且我们的前端保持简单：任何地方都没有 “迭代支配边界” 计算。
7.8. 完整代码清单¶
这是我们的运行示例的完整代码清单，增强了可变变量和 var/in 支持。要构建此示例，请使用
# Compile
clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy
# Run
./toy
这是代码
#include "../include/KaleidoscopeJIT.h"
#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/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Passes/PassBuilder.h"
#include "llvm/Passes/StandardInstrumentations.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"
#include "llvm/Transforms/Scalar/Reassociate.h"
#include "llvm/Transforms/Scalar/SimplifyCFG.h"
#include "llvm/Transforms/Utils/Mem2Reg.h"
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <utility>
#include <vector>
using namespace llvm;
using namespace llvm::orc;
//===----------------------------------------------------------------------===//
// Lexer
//===----------------------------------------------------------------------===//
// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
// of these for known things.
enum Token {
tok_eof = -1,
// commands
tok_def = -2,
tok_extern = -3,
// primary
tok_identifier = -4,
tok_number = -5,
// control
tok_if = -6,
tok_then = -7,
tok_else = -8,
tok_for = -9,
tok_in = -10,
// operators
tok_binary = -11,
tok_unary = -12,
// var definition
tok_var = -13
};
static std::string IdentifierStr; // Filled in if tok_identifier
static double NumVal; // Filled in if tok_number
/// gettok - Return the next token from standard input.
static int gettok() {
static int LastChar = ' ';
// Skip any whitespace.
while (isspace(LastChar))
LastChar = getchar();
if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
IdentifierStr = LastChar;
while (isalnum((LastChar = getchar())))
IdentifierStr += LastChar;
if (IdentifierStr == "def")
return tok_def;
if (IdentifierStr == "extern")
return tok_extern;
if (IdentifierStr == "if")
return tok_if;
if (IdentifierStr == "then")
return tok_then;
if (IdentifierStr == "else")
return tok_else;
if (IdentifierStr == "for")
return tok_for;
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;
}
if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
std::string NumStr;
do {
NumStr += LastChar;
LastChar = getchar();
} while (isdigit(LastChar) || LastChar == '.');
NumVal = strtod(NumStr.c_str(), nullptr);
return tok_number;
}
if (LastChar == '#') {
// Comment until end of line.
do
LastChar = getchar();
while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
if (LastChar != EOF)
return gettok();
}
// Check for end of file. Don't eat the EOF.
if (LastChar == EOF)
return tok_eof;
// Otherwise, just return the character as its ascii value.
int ThisChar = LastChar;
LastChar = getchar();
return ThisChar;
}
//===----------------------------------------------------------------------===//
// Abstract Syntax Tree (aka Parse Tree)
//===----------------------------------------------------------------------===//
namespace {
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() = default;
virtual Value *codegen() = 0;
};
/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
double Val;
public:
NumberExprAST(double Val) : Val(Val) {}
Value *codegen() override;
};
/// VariableExprAST - Expression class for referencing a variable, like "a".
class VariableExprAST : public ExprAST {
std::string Name;
public:
VariableExprAST(const std::string &Name) : Name(Name) {}
Value *codegen() override;
const std::string &getName() const { return Name; }
};
/// 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> Operand)
: Opcode(Opcode), Operand(std::move(Operand)) {}
Value *codegen() override;
};
/// BinaryExprAST - Expression class for a binary operator.
class BinaryExprAST : public ExprAST {
char Op;
std::unique_ptr<ExprAST> LHS, RHS;
public:
BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,
std::unique_ptr<ExprAST> RHS)
: Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
Value *codegen() override;
};
/// CallExprAST - Expression class for function calls.
class CallExprAST : public ExprAST {
std::string Callee;
std::vector<std::unique_ptr<ExprAST>> Args;
public:
CallExprAST(const std::string &Callee,
std::vector<std::unique_ptr<ExprAST>> Args)
: Callee(Callee), Args(std::move(Args)) {}
Value *codegen() override;
};
/// 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;
};
/// ForExprAST - Expression class for for/in.
class ForExprAST : public ExprAST {
std::string VarName;
std::unique_ptr<ExprAST> Start, End, Step, Body;
public:
ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start,
std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step,
std::unique_ptr<ExprAST> Body)
: VarName(VarName), Start(std::move(Start)), End(std::move(End)),
Step(std::move(Step)), Body(std::move(Body)) {}
Value *codegen() override;
};
/// 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;
};
/// PrototypeAST - This class represents the "prototype" for a function,
/// which captures its name, and its argument names (thus implicitly the number
/// of arguments the function takes), as well as if it is an operator.
class PrototypeAST {
std::string Name;
std::vector<std::string> Args;
bool IsOperator;
unsigned Precedence; // Precedence if a binary op.
public:
PrototypeAST(const std::string &Name, std::vector<std::string> Args,
bool IsOperator = false, unsigned Prec = 0)
: Name(Name), Args(std::move(Args)), IsOperator(IsOperator),
Precedence(Prec) {}
Function *codegen();
const std::string &getName() const { return Name; }
bool isUnaryOp() const { return IsOperator && Args.size() == 1; }
bool isBinaryOp() const { return IsOperator && Args.size() == 2; }
char getOperatorName() const {
assert(isUnaryOp() || isBinaryOp());
return Name[Name.size() - 1];
}
unsigned getBinaryPrecedence() const { return Precedence; }
};
/// FunctionAST - This class represents a function definition itself.
class FunctionAST {
std::unique_ptr<PrototypeAST> Proto;
std::unique_ptr<ExprAST> Body;
public:
FunctionAST(std::unique_ptr<PrototypeAST> Proto,
std::unique_ptr<ExprAST> Body)
: Proto(std::move(Proto)), Body(std::move(Body)) {}
Function *codegen();
};
} // end anonymous namespace
//===----------------------------------------------------------------------===//
// Parser
//===----------------------------------------------------------------------===//
/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
/// token the parser is looking at. getNextToken reads another token from the
/// lexer and updates CurTok with its results.
static int CurTok;
static int getNextToken() { return CurTok = gettok(); }
/// BinopPrecedence - This holds the precedence for each binary operator that is
/// defined.
static std::map<char, int> BinopPrecedence;
/// GetTokPrecedence - Get the precedence of the pending binary operator token.
static int GetTokPrecedence() {
if (!isascii(CurTok))
return -1;
// Make sure it's a declared binop.
int TokPrec = BinopPrecedence[CurTok];
if (TokPrec <= 0)
return -1;
return TokPrec;
}
/// LogError* - These are little helper functions for error handling.
std::unique_ptr<ExprAST> LogError(const char *Str) {
fprintf(stderr, "Error: %s\n", Str);
return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
LogError(Str);
return nullptr;
}
static std::unique_ptr<ExprAST> ParseExpression();
/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
auto Result = std::make_unique<NumberExprAST>(NumVal);
getNextToken(); // consume the number
return std::move(Result);
}
/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
getNextToken(); // eat (.
auto V = ParseExpression();
if (!V)
return nullptr;
if (CurTok != ')')
return LogError("expected ')'");
getNextToken(); // eat ).
return V;
}
/// identifierexpr
/// ::= identifier
/// ::= identifier '(' expression* ')'
static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
std::string IdName = IdentifierStr;
getNextToken(); // eat identifier.
if (CurTok != '(') // Simple variable ref.
return std::make_unique<VariableExprAST>(IdName);
// Call.
getNextToken(); // eat (
std::vector<std::unique_ptr<ExprAST>> Args;
if (CurTok != ')') {
while (true) {
if (auto Arg = ParseExpression())
Args.push_back(std::move(Arg));
else
return nullptr;
if (CurTok == ')')
break;
if (CurTok != ',')
return LogError("Expected ')' or ',' in argument list");
getNextToken();
}
}
// Eat the ')'.
getNextToken();
return std::make_unique<CallExprAST>(IdName, std::move(Args));
}
/// ifexpr ::= 'if' expression 'then' expression 'else' expression
static std::unique_ptr<ExprAST> ParseIfExpr() {
getNextToken(); // eat the if.
// condition.
auto Cond = ParseExpression();
if (!Cond)
return nullptr;
if (CurTok != tok_then)
return LogError("expected then");
getNextToken(); // eat the then
auto Then = ParseExpression();
if (!Then)
return nullptr;
if (CurTok != tok_else)
return LogError("expected else");
getNextToken();
auto Else = ParseExpression();
if (!Else)
return nullptr;
return std::make_unique<IfExprAST>(std::move(Cond), std::move(Then),
std::move(Else));
}
/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
static std::unique_ptr<ExprAST> ParseForExpr() {
getNextToken(); // eat the for.
if (CurTok != tok_identifier)
return LogError("expected identifier after for");
std::string IdName = IdentifierStr;
getNextToken(); // eat identifier.
if (CurTok != '=')
return LogError("expected '=' after for");
getNextToken(); // eat '='.
auto Start = ParseExpression();
if (!Start)
return nullptr;
if (CurTok != ',')
return LogError("expected ',' after for start value");
getNextToken();
auto End = ParseExpression();
if (!End)
return nullptr;
// The step value is optional.
std::unique_ptr<ExprAST> Step;
if (CurTok == ',') {
getNextToken();
Step = ParseExpression();
if (!Step)
return nullptr;
}
if (CurTok != tok_in)
return LogError("expected 'in' after for");
getNextToken(); // eat 'in'.
auto Body = ParseExpression();
if (!Body)
return nullptr;
return std::make_unique<ForExprAST>(IdName, std::move(Start), std::move(End),
std::move(Step), std::move(Body));
}
/// varexpr ::= 'var' identifier ('=' expression)?
// (',' identifier ('=' expression)?)* 'in' expression
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));
}
/// 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();
}
}
/// 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(CurTok) || CurTok == '(' || CurTok == ',')
return ParsePrimary();
// If this is a unary operator, read it.
int Opc = CurTok;
getNextToken();
if (auto Operand = ParseUnary())
return std::make_unique<UnaryExprAST>(Opc, std::move(Operand));
return nullptr;
}
/// binoprhs
/// ::= ('+' unary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
std::unique_ptr<ExprAST> LHS) {
// If this is a binop, find its precedence.
while (true) {
int TokPrec = GetTokPrecedence();
// If this is a binop that binds at least as tightly as the current binop,
// consume it, otherwise we are done.
if (TokPrec < ExprPrec)
return LHS;
// Okay, we know this is a binop.
int BinOp = CurTok;
getNextToken(); // eat binop
// Parse the unary expression after the binary operator.
auto RHS = ParseUnary();
if (!RHS)
return nullptr;
// If BinOp binds less tightly with RHS than the operator after RHS, let
// the pending operator take RHS as its LHS.
int NextPrec = GetTokPrecedence();
if (TokPrec < NextPrec) {
RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
if (!RHS)
return nullptr;
}
// Merge LHS/RHS.
LHS =
std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
}
}
/// expression
/// ::= unary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
auto LHS = ParseUnary();
if (!LHS)
return nullptr;
return ParseBinOpRHS(0, std::move(LHS));
}
/// prototype
/// ::= id '(' id* ')'
/// ::= binary LETTER number? (id, id)
/// ::= unary LETTER (id)
static std::unique_ptr<PrototypeAST> ParsePrototype() {
std::string FnName;
unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
unsigned BinaryPrecedence = 30;
switch (CurTok) {
default:
return LogErrorP("Expected function name in prototype");
case tok_identifier:
FnName = IdentifierStr;
Kind = 0;
getNextToken();
break;
case tok_unary:
getNextToken();
if (!isascii(CurTok))
return LogErrorP("Expected unary operator");
FnName = "unary";
FnName += (char)CurTok;
Kind = 1;
getNextToken();
break;
case tok_binary:
getNextToken();
if (!isascii(CurTok))
return LogErrorP("Expected binary operator");
FnName = "binary";
FnName += (char)CurTok;
Kind = 2;
getNextToken();
// Read the precedence if present.
if (CurTok == tok_number) {
if (NumVal < 1 || NumVal > 100)
return LogErrorP("Invalid precedence: must be 1..100");
BinaryPrecedence = (unsigned)NumVal;
getNextToken();
}
break;
}
if (CurTok != '(')
return LogErrorP("Expected '(' in prototype");
std::vector<std::string> ArgNames;
while (getNextToken() == tok_identifier)
ArgNames.push_back(IdentifierStr);
if (CurTok != ')')
return LogErrorP("Expected ')' in prototype");
// success.
getNextToken(); // eat ')'.
// Verify right number of names for operator.
if (Kind && ArgNames.size() != Kind)
return LogErrorP("Invalid number of operands for operator");
return std::make_unique<PrototypeAST>(FnName, ArgNames, Kind != 0,
BinaryPrecedence);
}
/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDefinition() {
getNextToken(); // eat def.
auto Proto = ParsePrototype();
if (!Proto)
return nullptr;
if (auto E = ParseExpression())
return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
return nullptr;
}
/// toplevelexpr ::= expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
if (auto E = ParseExpression()) {
// Make an anonymous proto.
auto Proto = std::make_unique<PrototypeAST>("__anon_expr",
std::vector<std::string>());
return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
}
return nullptr;
}
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
getNextToken(); // eat extern.
return ParsePrototype();
}
//===----------------------------------------------------------------------===//
// Code Generation
//===----------------------------------------------------------------------===//
static std::unique_ptr<LLVMContext> TheContext;
static std::unique_ptr<Module> TheModule;
static std::unique_ptr<IRBuilder<>> Builder;
static std::map<std::string, AllocaInst *> NamedValues;
static std::unique_ptr<KaleidoscopeJIT> TheJIT;
static std::unique_ptr<FunctionPassManager> TheFPM;
static std::unique_ptr<LoopAnalysisManager> TheLAM;
static std::unique_ptr<FunctionAnalysisManager> TheFAM;
static std::unique_ptr<CGSCCAnalysisManager> TheCGAM;
static std::unique_ptr<ModuleAnalysisManager> TheMAM;
static std::unique_ptr<PassInstrumentationCallbacks> ThePIC;
static std::unique_ptr<StandardInstrumentations> TheSI;
static std::map<std::string, std::unique_ptr<PrototypeAST>> FunctionProtos;
static ExitOnError ExitOnErr;
Value *LogErrorV(const char *Str) {
LogError(Str);
return nullptr;
}
Function *getFunction(std::string Name) {
// First, see if the function has already been added to the current module.
if (auto *F = TheModule->getFunction(Name))
return F;
// If not, check whether we can codegen the declaration from some existing
// prototype.
auto FI = FunctionProtos.find(Name);
if (FI != FunctionProtos.end())
return FI->second->codegen();
// If no existing prototype exists, return null.
return nullptr;
}
/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
/// the function. This is used for mutable variables etc.
static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
StringRef VarName) {
IRBuilder<> TmpB(&TheFunction->getEntryBlock(),
TheFunction->getEntryBlock().begin());
return TmpB.CreateAlloca(Type::getDoubleTy(*TheContext), nullptr, VarName);
}
Value *NumberExprAST::codegen() {
return ConstantFP::get(*TheContext, APFloat(Val));
}
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());
}
Value *UnaryExprAST::codegen() {
Value *OperandV = Operand->codegen();
if (!OperandV)
return nullptr;
Function *F = getFunction(std::string("unary") + Opcode);
if (!F)
return LogErrorV("Unknown unary operator");
return Builder->CreateCall(F, OperandV, "unop");
}
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;
}
Value *L = LHS->codegen();
Value *R = RHS->codegen();
if (!L || !R)
return nullptr;
switch (Op) {
case '+':
return Builder->CreateFAdd(L, R, "addtmp");
case '-':
return Builder->CreateFSub(L, R, "subtmp");
case '*':
return Builder->CreateFMul(L, R, "multmp");
case '<':
L = Builder->CreateFCmpULT(L, R, "cmptmp");
// Convert bool 0/1 to double 0.0 or 1.0
return Builder->CreateUIToFP(L, Type::getDoubleTy(*TheContext), "booltmp");
default:
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") + Op);
assert(F && "binary operator not found!");
Value *Ops[] = {L, R};
return Builder->CreateCall(F, Ops, "binop");
}
Value *CallExprAST::codegen() {
// Look up the name in the global module table.
Function *CalleeF = getFunction(Callee);
if (!CalleeF)
return LogErrorV("Unknown function referenced");
// If argument mismatch error.
if (CalleeF->arg_size() != Args.size())
return LogErrorV("Incorrect # arguments passed");
std::vector<Value *> ArgsV;
for (unsigned i = 0, e = Args.size(); i != e; ++i) {
ArgsV.push_back(Args[i]->codegen());
if (!ArgsV.back())
return nullptr;
}
return Builder->CreateCall(CalleeF, ArgsV, "calltmp");
}
Value *IfExprAST::codegen() {
Value *CondV = Cond->codegen();
if (!CondV)
return nullptr;
// Convert condition to a bool by comparing non-equal to 0.0.
CondV = Builder->CreateFCmpONE(
CondV, ConstantFP::get(*TheContext, APFloat(0.0)), "ifcond");
Function *TheFunction = Builder->GetInsertBlock()->getParent();
// Create blocks for the then and else cases. Insert the 'then' block at the
// end of the function.
BasicBlock *ThenBB = BasicBlock::Create(*TheContext, "then", TheFunction);
BasicBlock *ElseBB = BasicBlock::Create(*TheContext, "else");
BasicBlock *MergeBB = BasicBlock::Create(*TheContext, "ifcont");
Builder->CreateCondBr(CondV, ThenBB, ElseBB);
// Emit then value.
Builder->SetInsertPoint(ThenBB);
Value *ThenV = Then->codegen();
if (!ThenV)
return nullptr;
Builder->CreateBr(MergeBB);
// Codegen of 'Then' can change the current block, update ThenBB for the PHI.
ThenBB = Builder->GetInsertBlock();
// Emit else block.
TheFunction->insert(TheFunction->end(), ElseBB);
Builder->SetInsertPoint(ElseBB);
Value *ElseV = Else->codegen();
if (!ElseV)
return nullptr;
Builder->CreateBr(MergeBB);
// Codegen of 'Else' can change the current block, update ElseBB for the PHI.
ElseBB = Builder->GetInsertBlock();
// Emit merge block.
TheFunction->insert(TheFunction->end(), MergeBB);
Builder->SetInsertPoint(MergeBB);
PHINode *PN = Builder->CreatePHI(Type::getDoubleTy(*TheContext), 2, "iftmp");
PN->addIncoming(ThenV, ThenBB);
PN->addIncoming(ElseV, ElseBB);
return PN;
}
// 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() {
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);
// Make the new basic block for the loop header, inserting after current
// block.
BasicBlock *LoopBB = BasicBlock::Create(*TheContext, "loop", TheFunction);
// Insert an explicit fall through from the current block to the LoopBB.
Builder->CreateBr(LoopBB);
// Start insertion in LoopBB.
Builder->SetInsertPoint(LoopBB);
// 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.
AllocaInst *OldVal = NamedValues[VarName];
NamedValues[VarName] = Alloca;
// 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.
if (!Body->codegen())
return nullptr;
// Emit the step value.
Value *StepVal = nullptr;
if (Step) {
StepVal = Step->codegen();
if (!StepVal)
return nullptr;
} else {
// If not specified, use 1.0.
StepVal = ConstantFP::get(*TheContext, APFloat(1.0));
}
// 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);
// Convert condition to a bool by comparing non-equal to 0.0.
EndCond = Builder->CreateFCmpONE(
EndCond, ConstantFP::get(*TheContext, APFloat(0.0)), "loopcond");
// Create the "after loop" block and insert it.
BasicBlock *AfterBB =
BasicBlock::Create(*TheContext, "afterloop", TheFunction);
// Insert the conditional branch into the end of LoopEndBB.
Builder->CreateCondBr(EndCond, LoopBB, AfterBB);
// Any new code will be inserted in AfterBB.
Builder->SetInsertPoint(AfterBB);
// Restore the unshadowed variable.
if (OldVal)
NamedValues[VarName] = OldVal;
else
NamedValues.erase(VarName);
// for expr always returns 0.0.
return Constant::getNullValue(Type::getDoubleTy(*TheContext));
}
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;
}
Function *PrototypeAST::codegen() {
// Make the function type: double(double,double) etc.
std::vector<Type *> Doubles(Args.size(), Type::getDoubleTy(*TheContext));
FunctionType *FT =
FunctionType::get(Type::getDoubleTy(*TheContext), Doubles, false);
Function *F =
Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());
// Set names for all arguments.
unsigned Idx = 0;
for (auto &Arg : F->args())
Arg.setName(Args[Idx++]);
return F;
}
Function *FunctionAST::codegen() {
// Transfer ownership of the prototype to the FunctionProtos map, but keep a
// reference to it for use below.
auto &P = *Proto;
FunctionProtos[Proto->getName()] = std::move(Proto);
Function *TheFunction = getFunction(P.getName());
if (!TheFunction)
return nullptr;
// If this is an operator, install it.
if (P.isBinaryOp())
BinopPrecedence[P.getOperatorName()] = P.getBinaryPrecedence();
// Create a new basic block to start insertion into.
BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);
Builder->SetInsertPoint(BB);
// Record the function arguments in the NamedValues map.
NamedValues.clear();
for (auto &Arg : TheFunction->args()) {
// 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()) {
// Finish off the function.
Builder->CreateRet(RetVal);
// Validate the generated code, checking for consistency.
verifyFunction(*TheFunction);
// Run the optimizer on the function.
TheFPM->run(*TheFunction, *TheFAM);
return TheFunction;
}
// Error reading body, remove function.
TheFunction->eraseFromParent();
if (P.isBinaryOp())
BinopPrecedence.erase(P.getOperatorName());
return nullptr;
}
//===----------------------------------------------------------------------===//
// Top-Level parsing and JIT Driver
//===----------------------------------------------------------------------===//
static void InitializeModuleAndManagers() {
// Open a new context and module.
TheContext = std::make_unique<LLVMContext>();
TheModule = std::make_unique<Module>("KaleidoscopeJIT", *TheContext);
TheModule->setDataLayout(TheJIT->getDataLayout());
// Create a new builder for the module.
Builder = std::make_unique<IRBuilder<>>(*TheContext);
// Create new pass and analysis managers.
TheFPM = std::make_unique<FunctionPassManager>();
TheLAM = std::make_unique<LoopAnalysisManager>();
TheFAM = std::make_unique<FunctionAnalysisManager>();
TheCGAM = std::make_unique<CGSCCAnalysisManager>();
TheMAM = std::make_unique<ModuleAnalysisManager>();
ThePIC = std::make_unique<PassInstrumentationCallbacks>();
TheSI = std::make_unique<StandardInstrumentations>(*TheContext,
/*DebugLogging*/ true);
TheSI->registerCallbacks(*ThePIC, TheMAM.get());
// Add transform passes.
// Promote allocas to registers.
TheFPM->addPass(PromotePass());
// Do simple "peephole" optimizations and bit-twiddling optzns.
TheFPM->addPass(InstCombinePass());
// Reassociate expressions.
TheFPM->addPass(ReassociatePass());
// Eliminate Common SubExpressions.
TheFPM->addPass(GVNPass());
// Simplify the control flow graph (deleting unreachable blocks, etc).
TheFPM->addPass(SimplifyCFGPass());
// Register analysis passes used in these transform passes.
PassBuilder PB;
PB.registerModuleAnalyses(*TheMAM);
PB.registerFunctionAnalyses(*TheFAM);
PB.crossRegisterProxies(*TheLAM, *TheFAM, *TheCGAM, *TheMAM);
}
static void HandleDefinition() {
if (auto FnAST = ParseDefinition()) {
if (auto *FnIR = FnAST->codegen()) {
fprintf(stderr, "Read function definition:");
FnIR->print(errs());
fprintf(stderr, "\n");
ExitOnErr(TheJIT->addModule(
ThreadSafeModule(std::move(TheModule), std::move(TheContext))));
InitializeModuleAndManagers();
}
} else {
// Skip token for error recovery.
getNextToken();
}
}
static void HandleExtern() {
if (auto ProtoAST = ParseExtern()) {
if (auto *FnIR = ProtoAST->codegen()) {
fprintf(stderr, "Read extern: ");
FnIR->print(errs());
fprintf(stderr, "\n");
FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST);
}
} else {
// Skip token for error recovery.
getNextToken();
}
}
static void HandleTopLevelExpression() {
// Evaluate a top-level expression into an anonymous function.
if (auto FnAST = ParseTopLevelExpr()) {
if (FnAST->codegen()) {
// Create a ResourceTracker to track JIT'd memory allocated to our
// anonymous expression -- that way we can free it after executing.
auto RT = TheJIT->getMainJITDylib().createResourceTracker();
auto TSM = ThreadSafeModule(std::move(TheModule), std::move(TheContext));
ExitOnErr(TheJIT->addModule(std::move(TSM), RT));
InitializeModuleAndManagers();
// Search the JIT for the __anon_expr symbol.
auto ExprSymbol = ExitOnErr(TheJIT->lookup("__anon_expr"));
// Get the symbol's address and cast it to the right type (takes no
// arguments, returns a double) so we can call it as a native function.
double (*FP)() = ExprSymbol.toPtr<double (*)()>();
fprintf(stderr, "Evaluated to %f\n", FP());
// Delete the anonymous expression module from the JIT.
ExitOnErr(RT->remove());
}
} else {
// Skip token for error recovery.
getNextToken();
}
}
/// top ::= definition | external | expression | ';'
static void MainLoop() {
while (true) {
fprintf(stderr, "ready> ");
switch (CurTok) {
case tok_eof:
return;
case ';': // ignore top-level semicolons.
getNextToken();
break;
case tok_def:
HandleDefinition();
break;
case tok_extern:
HandleExtern();
break;
default:
HandleTopLevelExpression();
break;
}
}
}
//===----------------------------------------------------------------------===//
// "Library" functions that can be "extern'd" from user code.
//===----------------------------------------------------------------------===//
#ifdef _WIN32
#define DLLEXPORT __declspec(dllexport)
#else
#define DLLEXPORT
#endif
/// putchard - putchar that takes a double and returns 0.
extern "C" DLLEXPORT double putchard(double X) {
fputc((char)X, stderr);
return 0;
}
/// printd - printf that takes a double prints it as "%f\n", returning 0.
extern "C" DLLEXPORT double printd(double X) {
fprintf(stderr, "%f\n", X);
return 0;
}
//===----------------------------------------------------------------------===//
// Main driver code.
//===----------------------------------------------------------------------===//
int main() {
InitializeNativeTarget();
InitializeNativeTargetAsmPrinter();
InitializeNativeTargetAsmParser();
// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['='] = 2;
BinopPrecedence['<'] = 10;
BinopPrecedence['+'] = 20;
BinopPrecedence['-'] = 20;
BinopPrecedence['*'] = 40; // highest.
// Prime the first token.
fprintf(stderr, "ready> ");
getNextToken();
TheJIT = ExitOnErr(KaleidoscopeJIT::Create());
InitializeModuleAndManagers();
// Run the main "interpreter loop" now.
MainLoop();
return 0;
}