Kaleidoscope 系列第五章：扩展语言—控制流

原文链接: Kaleidoscope 系列第五章：扩展语言---控制流

本文是使用 LLVM 开发新语言 Kaleidoscope 教程系列第五章，主要扩展 Kaleidoscope 语言特性，增加多种控制流处理。

第五章简介

欢迎来到“使用 LLVM 开发新语言 Kaleidoscope 教程”教程的第五章。第 1-4 部分描述了简单的 Kaleidoscope 语言的实现，并包括对生成 LLVM IR 的支持，随后是优化和 JIT 编译器。不幸的是，如前所述，Kaleidoscope 几乎没有用：除了调用和返回外，它没有控制流。这意味着您在代码中不能有条件分支，从而大大限制了它的功能。在本章节中，我们将扩展 Kaleidoscope，使其具有 if / then / else 表达式以及一个简单的“ for”循环。

增加 If/Then/Else

扩展 Kaleidoscope 以支持 if / then / else 非常简单。基本上，它需要向词法分析器，解析器，AST 和 LLVM 代码发射器添加对此“新”概念的支持。这个例子很好，因为它显示了随着时间的推移“增长”一种语言并随着发现新想法而逐步扩展它是多么容易。

在开始“如何添加”之前，我们要添加此扩展，让我们先讨论一下“我们想要什么”。基本思想是我们希望能够编写此类内容：

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

在 Kaleidoscope 中，每个构造都是一个表达式：没有语句。因此，if / then / else 表达式需要像其他值一样返回一个值。由于我们使用的主要是函数形式，因此我们将让它评估其条件，然后根据条件的解决方式返回“ then”或“ else”值。这与 C 语言中三元运算符 ? : 非常相似。

if / then / else 表达式的语义是将条件评估为布尔相等值：0 被认为是错误的，其他所有事物都被认为是真实的。如果条件为 true，则评估并返回第一个子表达式；如果条件为 false，则将评估并返回第二个子表达式。由于 Kaleidoscope 具有 side-effects，因此确定这种行为很重要。

现在我们知道了我们“想要”什么，下面我们将其分解为各个组成部分。

词法分析扩展

词法分析器扩展很简单。首先，我们为相关 token 添加新的枚举值：

// control
tok_if = -6,
tok_then = -7,
tok_else = -8,

一旦有了这些，就可以在词法分析器中识别新的关键字。这是非常简单的东西：

...
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;
return tok_identifier;

AST 扩展

为了表示新表达式，我们为其添加了一个新的 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;
};

AST 节点仅具有指向各种子表达式的指针。

解析器扩展

现在我们有了来自词法分析器的相关 token，并且我们要构建 AST 节点，我们的解析逻辑相对简单。首先，我们定义一个新的解析函数：

/// 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));
}

接下来，我们将其连接为主表达式：

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();
  }
}

LLVM IR 生成扩展

现在我们已经解析并构建了 AST，最后一步是添加 LLVM 代码生成支持。这是 if / then / else 示例中最有趣的部分，因为这是开始引入新概念的地方。以上所有代码已在前面的章节中进行了详细介绍。

为了激励我们想要产生的代码，让我们看一个简单的例子。考虑：

extern foo();
extern bar();
def baz(x) if x then foo() else bar();

如果禁用优化，我们（很快）将从 Kaleidoscope 中获取的代码如下所示：

declare double @foo()

declare double @bar()

define double @baz(double %x) {
entry:
  %ifcond = fcmp one double %x, 0.000000e+00
  br i1 %ifcond, label %then, label %else

then:       ; preds = %entry
  %calltmp = call double @foo()
  br label %ifcont

else:       ; preds = %entry
  %calltmp1 = call double @bar()
  br label %ifcont

ifcont:     ; preds = %else, %then
  %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
  ret double %iftmp
}

以可视化的控制流图，你可以使用 LLVM “的一个很棒的功能 opt”工具。如果将此 LLVM IR 放入“ t.ll”并运行 llvm-as < t.ll | opt -analyze -view-cfg ，则会弹出一个窗口，我们将看到以下图形：

实现此目的的另一种方法是通过在代码中插入实际的调用并重新编译，或者在调试器中调用它们来调用 F->viewCFG() 或 F->viewCFGOnly() （其中 F 是 Function* ）。LLVM 具有许多很棒的功能，可用于可视化各种图形。

回到生成的代码，这非常简单：入口块评估条件表达式（在本例中为“ x”），然后使用 fcmp one 指令将结果与 0 进行比较（“ one”为“ Ordered and Not Equal” ）。根据该表达式的结果，代码跳转到“ then”或“ else”块，其中包含对/错情况的表达式。

一旦 then / else 块完成执行，它们都分支回到 ifcont 块以执行在 if / then / else 之后发生的代码。在这种情况下，剩下要做的就是返回函数的调用者。问题就变成了：代码如何知道要返回哪个表达式？

该问题的答案涉及一个重要的 SSA 操作：Phi 操作。如果您不熟悉 SSA，那么这篇 Wikipedia 文章是不错的介绍，并且在搜索引擎上还有其他各种介绍。简短的版本是，“执行” Phi 操作需要“记住”块控制来自何处。Phi 操作采用与输入控制块相对应的值。在这种情况下，如果控件来自 then 块，则它将获得 calltmp 的值。如果控件来自 else 块，则它将获得 calltmp1 的值。

此时，您可能开始思考“不对！这意味着我简单优雅的前端必须开始生成 SSA 表单才能使用 LLVM！”幸运的是，事实并非如此，我们强烈建议 不要 在前端中实施 SSA 构造算法，除非有令人惊讶的充分理由。实际上，在为我们的平均命令式编程语言编写的可能需要 Phi 节点的代码中，存在两种类型的值：

1. 涉及用户变量的代码：x=1;x=x+1;

2. AST 结构中隐含的值，例如本例中的 Phi 节点。

在本教程的第 7 章（“可变变量”）中，我们将深入讨论＃1。现在，你不需要 SSA 构造即可处理这种情况。对于＃2，你可以选择使用我们将针对＃1 描述的技术，或者，如果方便的话，可以直接插入 Phi 节点。在这种情况下，生成 Phi 节点真的很容易，因此我们选择直接执行。

好的，有了以上足够的动机和概述，接下来看生成代码部分！

代码生成扩展

为了为此生成代码，我们为实现以下 codegen 方法 IfExprAST：

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");

该代码非常简单，与我们之前看到的类似。我们发出条件的表达式，然后将该值与零进行比较，以得到 1 位（布尔）值的真值。

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);

这段代码创建与 if / then / else 语句相关的基本块，并直接与上面示例中的块相对应。第一行获取正在构建的当前 Function 对象。通过向构建器询问当前的 BasicBlock，并向该块询问其“parent”（当前嵌入到其中的函数），可以实现此目的。

一旦有了它，它将创建三个块。请注意，它将 TheFunction 传递到 then 块的构造函数中。这使构造函数自动将新块插入到指定函数的末尾。其他两个块已创建，但尚未插入到函数中。

一旦创建了块，我们就可以发出在它们之间进行选择的条件分支。请注意，创建新块不会隐式影响 IRBuilder，因此它仍会插入条件所进入的块中。还要注意，即使尚未将 else 块插入功能中，它也会创建一个到 then 块和 else 块的分支。没关系：这是 LLVM 支持前向引用的标准方式。

// 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();

插入条件分支后，我们将移动构建器以开始插入 then 块中。严格来说，此调用将插入点移动到指定块的末尾。但是，由于 then 块为空，因此它也通过在该块的开头插入而开始。

设置插入点后，我们递归地对 AST 中的 then 表达式进行编码。为了完成 then 块，我们创建了无条件分支到 merge 块。LLVM IR 的一个有趣的（也是非常重要的）方面是，它要求所有基本块都必须通过控制流指令例如 return 或 branch“终止”。这意味着必须在 LLVM IR 中明确所有控制流。如果违反此规则，则验证程序将发出错误。

最后一行非常短小，但非常重要。基本的问题是，当我们在合并块中创建 Phi 节点时，我们需要设置指示 Phi 将如何工作的块/值对。重要的是，Phi 节点希望为 CFG 中该块的每个前身都有一个条目。那么，为什么仅将其设置为上面的 ThenBB 5 行呢？问题是 Then 表达式本身实际上可以更改生成器要发送到的块，例如，如果它包含嵌套的 if / then / else 表达式。因为 codegen() 递归调用可以任意更改当前块的概念，所以我们需要获取用于设置 Phi 节点的代码的最新值。

// Emit else block.
TheFunction->getBasicBlockList().push_back(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();

else 块的代码生成基本上与 then 块的代码生成相同。唯一的不同是第一行，该行在函数中添加了 else 块。之前回想过，else 块已创建，但未添加到函数中。现在发出了 then 和 else 块，我们可以完成合并代码：

  // Emit merge block.
  TheFunction->getBasicBlockList().push_back(MergeBB);
  Builder.SetInsertPoint(MergeBB);
  PHINode *PN =
    Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, "iftmp");

  PN->addIncoming(ThenV, ThenBB);
  PN->addIncoming(ElseV, ElseBB);
  return PN;
}

现在，这里的前两行很熟悉：第一行将 merge 块添加到 Function 对象（它以前是浮动的，就像上面的 else 块一样）。第二个更改插入点，以便新创建的代码将进入“合并”块。完成后，我们需要创建 PHI 节点并为 PHI 设置块/值对。

最后，CodeGen 函数将 phi 节点作为由 if / then / else 表达式计算的值返回。在上面的示例中，此返回值将馈送到顶层函数的代码中，该函数将创建返回指令。

总的来说，我们现在可以在万花筒中执行条件代码。通过此扩展，Kaleidoscope 是一种相当完整的语言，可以计算各种数值函数。接下来，我们将添加另一个有用的表达式，这些表达式是非功能性语言所熟悉的。

增加 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);

该表达式定义一个新变量（在这种情况下为 i ），该变量从起始值开始迭代，而条件（在这种情况下为“ i <n”）为真，并以可选的步长值（在这种情况下为“ 1.0”）递增）。如果省略步长值，则默认为 1.0。当循环为 true 时，它将执行其主体表达式。由于没有更好的返回值，因此将循环定义为始终返回 0.0。将来，当我们有了可变变量时，它将变得更加有用。

和以前一样，下面我们看看支持 for 时 Kaleidoscope 所需的更改。

词法分析扩展

lexer 扩展与 if / then / else 类似：

... in enum Token ...
// control
tok_if = -6, tok_then = -7, tok_else = -8,
tok_for = -9, tok_in = -10

... in gettok ...
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;
return tok_identifier;

AST 扩展

AST 节点非常简单。基本上可以归结为捕获节点中的变量名称和组成表达式。

/// 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;
};

解析器扩展

解析器代码也是相当规范的。唯一有趣的是处理可选的步长值。解析器代码通过检查是否存在第二个逗号来处理它。如果不是，它将在 AST 节点中将 step 值设置为 null：

/// 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));
}

再次，我们将其作为主要表达式：

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();
  }
}

LLVM IR 生成扩展

现在，我们进入了一个很关键的部分：我们要为此生成的 LLVM IR。通过上面的简单示例，我们得到以下 LLVM IR（请注意，为清楚起见，此转储是在禁用优化的情况下生成的）：

declare double @putchard(double)

define double @printstar(double %n) {
entry:
  ; initial value = 1.0 (inlined into phi)
  br label %loop

loop:       ; preds = %loop, %entry
  %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
  ; body
  %calltmp = call double @putchard(double 4.200000e+01)
  ; increment
  %nextvar = fadd double %i, 1.000000e+00

  ; termination test
  %cmptmp = fcmp ult double %i, %n
  %booltmp = uitofp i1 %cmptmp to double
  %loopcond = fcmp one double %booltmp, 0.000000e+00
  br i1 %loopcond, label %loop, label %afterloop

afterloop:      ; preds = %loop
  ; loop always returns 0.0
  ret double 0.000000e+00
}

该循环包含我们之前看到的所有相同构造：一个 phi 节点，几个表达式和一些基本块。让我们看看它们如何结合在一起。

代码生成扩展

代码生成的第一部分非常简单：我们只输出循环值的起始表达式：

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

这样，下一步就是为循环体的开始设置 LLVM 基本块。在上述情况下，整个循环主体是一个块，但是请记住主体代码本身可以包含多个块（例如，如果其中包含 if / then / else 或 for / in 表达式）。

// Make the new basic block for the loop header, inserting after current
// block.
Function *TheFunction = Builder.GetInsertBlock()->getParent();
BasicBlock *PreheaderBB = Builder.GetInsertBlock();
BasicBlock *LoopBB =
    BasicBlock::Create(TheContext, "loop", TheFunction);

// Insert an explicit fall through from the current block to the LoopBB.
Builder.CreateBr(LoopBB);

此代码类似于我们在 if / then / else 中看到的代码。因为我们将需要它来创建 Phi 节点，所以我们记住掉入循环的块。一旦有了这些，就可以创建一个实际的块来启动循环，并为两个块之间创建一个无条件分支。

// Start insertion in LoopBB.
Builder.SetInsertPoint(LoopBB);

// Start the PHI node with an entry for Start.
PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(TheContext),
                                      2, VarName.c_str());
Variable->addIncoming(StartVal, PreheaderBB);

现在已经为循环设置了 preheader ，我们切换到为循环主体生成代码。首先，我们移动插入点并为循环归纳变量创建 PHI 节点。由于我们已经知道起始值的传入值，因此将其添加到 Phi 节点。请注意，Phi 最终将获得第二个后沿值，但我们尚无法设置（因为它不存在！）。

// 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.
Value *OldVal = NamedValues[VarName];
NamedValues[VarName] = 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.
if (!Body->codegen())
  return nullptr;

现在，代码开始变得更加有趣。我们的 for 循环为符号表引入了一个新变量。这意味着我们的符号表现在可以包含函数参数或循环变量。为了解决这个问题，在对循环主体进行代码生成之前，我们将循环变量添加为其名称的当前值。请注意，在外部作用域中可能存在相同名称的变量。很容易使它成为错误（发出错误，如果已经有 VarName 条目，则返回 null），但是我们选择允许对变量进行阴影处理。为了正确处理此问题，请记住我们可能在 OldVal 其中进行阴影处理的 Value（如果没有隐藏变量，则为 null）。

将循环变量设置到符号表中后，代码将递归代码生成器的主体。这允许主体使用循环变量：对它的任何引用都会自然地在符号表中找到它。

// 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));
}

Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");

现在已经生成了主体，我们通过添加步长值来计算迭代变量的下一个值，如果不存在，则为 1.0。 NextVar 将是循环的下一次迭代时循环变量的值。

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

// Convert condition to a bool by comparing non-equal to 0.0.
EndCond = Builder.CreateFCmpONE(
    EndCond, ConstantFP::get(TheContext, APFloat(0.0)), "loopcond");

最后，我们判断循环的退出值，以确定循环是否应该退出。这反映了 if / then / else 语句的条件正确与否。

// Create the "after loop" block and insert it.
BasicBlock *LoopEndBB = Builder.GetInsertBlock();
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);

完成循环主体的代码后，我们只需要完成其控制流程即可。此代码记住结束块（用于 phi 节点），然后为循环出口（“ afterloop”）创建块。基于退出条件的值，它创建一个条件分支，该分支在再次执行循环和退出循环之间进行选择。任何将来的代码都会在“ afterloop”块中发出，因此它将为其设置插入位置。

  // Add a new entry to the PHI node for the backedge.
  Variable->addIncoming(NextVar, LoopEndBB);

  // 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));
}

最终代码处理各种清理：现在我们有了 NextVar 值，我们可以将输入值添加到循环 PHI 节点中。之后，我们从符号表中删除循环变量，以使它不在 for 循环之后。最后，for 循环的代码生成始终返回 0.0，这就是我们从返回的内容 ForExprAST::codegen()。

这样，我们结束了本教程的“向 Kaleidoscope 添加控制流”一章。在本章中，我们添加了两个控制流构造，并使用它们来补充 LLVM IR 的两个重要功能，这对于前端实现者来说很重要。在我们的下一章中，我们将变得更加有激情，我们要将用户定义运算符添加到我们的 Kaleidoscope 语言中。

完整代码清单

这是我们正在运行的示例的完整代码清单，并增加了 if / then / else 和 for expression 控制流功能。运行并演示此示例，请使用以下命令：

# Compile
clang++ -g chapter5-Extending-the-Language-Control-Flow.cpp `llvm-config --cxxflags --ldflags --system-libs --libs all mcjit native` -O3 -o toy
# Run
./toy

以下是完整代码清单：

chapter5-Extending-the-Language-Control-Flow.cpp

参考: Kaleidoscope: Extending the Language: Control Flow