5.万花筒：扩展语言：控制流程

    • 第5章简介
    • if/then/ ELSE
    • 用于If / Then / Else的Lexer扩展
    • If / Then / Else的AST扩​​展
    • If / Then / Else的解析扩展
    • 用于If / Then / Else的LLVM IR
    • If / Then / Else的代码生成
    • ‘for’Loop Expression
    • “for”循环的Lexer扩展
    • ‘for’循环的AST扩​​展
    • ‘for’循环的解析器扩展
    • 用于’for’循环的LLVM IR
    • ‘for’循环的代码生成
    • 完整的代码清单

    5.2 if/ Then /

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

    在我们开始“如何”添加此扩展之前，让我们谈谈我们想要的“什么”。基本的想法是我们希望能够写出这样的东西：

    在Kaleidoscope中，每个构造都是一个表达式：没有语句。因此，if / then / else表达式需要返回与其他任何值相同的值。由于我们使用的是大部分功能形式，我们将对其进行评估，然后根据条件的解析方式返回“then”或“else”值。这与C“？：”表达非常相似。

    if / then / else表达式的语义是它将条件计算为布尔相等值：0.0被认为是假，其他一切都被认为是真。如果条件为真，则计算并返回第一个子表达式，如果条件为假，则计算并返回第二个子表达式。由于万花筒允许副作用，因此这种行为对于确定是非常重要的。

    现在我们知道了我们“想要”的东西，让我们把它分解成它的组成部分。

    5.2.1 If / Then / Else的Lexer扩展

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

    2. tok_if = -6,
    3. tok_then = -7,
    4. tok_else = -8,

    一旦我们有了这个，我们就会识别词法分析器中的新关键字。这很简单：

    1. ...
    2. if (IdentifierStr == "def")
    3.   return tok_def;
    4. if (IdentifierStr == "extern")
    5.   return tok_extern;
    6. if (IdentifierStr == "if")
    7.   return tok_if;
    8. if (IdentifierStr == "then")
    9.   return tok_then;
    10. if (IdentifierStr == "else")
    11.   return tok_else;
    12. return tok_identifier;

    5.2.2 If / Then / Else的AST扩​​展

    为了表示新表达式，我们为它添加了一个新的AST节点：

    1. /// IfExprAST - Expression class for if/then/else.
    2. class IfExprAST : public ExprAST {
    3.   std::unique_ptr<ExprAST> Cond, Then, Else;
    5. public:
    6.   IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then,
    7.             std::unique_ptr<ExprAST> Else)
    8.     : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {}
    10.   Value *codegen() override;
    11. };

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

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

    1. /// ifexpr ::= 'if' expression 'then' expression 'else' expression
    2. static std::unique_ptr<ExprAST> ParseIfExpr() {
    3.   getNextToken();  // eat the if.
    5.   // condition.
    6.   auto Cond = ParseExpression();
    7.   if (!Cond)
    8.     return nullptr;
    10.   if (CurTok != tok_then)
    11.     return LogError("expected then");
    12.   getNextToken();  // eat the then
    14.   auto Then = ParseExpression();
    15.   if (!Then)
    16.     return nullptr;
    18.   if (CurTok != tok_else)
    19.     return LogError("expected else");
    21.   getNextToken();
    23.   auto Else = ParseExpression();
    24.   if (!Else)
    25.     return nullptr;
    27.   return llvm::make_unique<IfExprAST>(std::move(Cond), std::move(Then),
    28.                                       std::move(Else));
    29. }

    接下来我们将它作为主要表达式连接起来：

    1. static std::unique_ptr<ExprAST> ParsePrimary() {
    2.   switch (CurTok) {
    3.   default:
    4.     return LogError("unknown token when expecting an expression");
    5.   case tok_identifier:
    6.     return ParseIdentifierExpr();
    7.   case tok_number:
    8.     return ParseNumberExpr();
    9.   case '(':
    10.     return ParseParenExpr();
    11.   case tok_if:
    12.     return ParseIfExpr();
    13.   }
    14. }

    5.2.4 用于If / Then / Else的

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

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

    1. extern foo();
    2. extern bar();
    3. def baz(x) if x then foo() else bar();

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

    1. declare double @foo()
    3. declare double @bar()
    5. define double @baz(double %x) {
    6. entry:
    7.   %ifcond = fcmp one double %x, 0.000000e+00
    8.   br i1 %ifcond, label %then, label %else
    10. then:       ; preds = %entry
    11.   %calltmp = call double @foo()
    13. else:       ; preds = %entry
    14.   %calltmp1 = call double @bar()
    15.   br label %ifcont
    17. ifcont:     ; preds = %else, %then
    18.   %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
    19.   ret double %iftmp
    20. }

    要可视化控制流图，您可以使用LLVM“ opt ”工具的一个漂亮功能。如果你把这个LLVM IR放到“t.ll”并运行“ ”，会弹出一个窗口，你会看到这个图：llvm-as < t.ll | opt -analyze -view-cfg

    5.2.5 If / Then / Else的代码生成

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

    1. Value *IfExprAST::codegen() {
    2.   Value *CondV = Cond->codegen();
    3.   if (!CondV)
    4.     return nullptr;
    6.   // Convert condition to a bool by comparing non-equal to 0.0.
    7.   CondV = Builder.CreateFCmpONE(
    8.       CondV, ConstantFP::get(TheContext, APFloat(0.0)), "ifcond");

    这段代码很简单，与我们之前看到的类似。我们为条件发出表达式，然后将该值与零进行比较，以获得真值作为1位（bool）值。

    此代码创建与if / then / else语句相关的基本块，并直接对应于上例中的块。第一行获取正在构建的当前Function对象。它通过询问构建器当前的BasicBlock，并询问该块的“父”（它当前嵌入的函数）来获得这一点。

    一旦有了，就会创建三个块。请注意，它将“TheFunction”传递给“then”块的构造函数。这会导致构造函数自动将新块插入指定函数的末尾。创建了另外两个块，但尚未插入到该函数中。

    一旦创建了块，我们就可以发出在它们之间选择的条件分支。请注意，创建新块不会隐式影响IRBuilder，因此它仍然会插入条件进入的块中。另请注意，它正在创建“then”块和“else”块的分支，即使“else”块尚未插入到函数中。这一切都很好：它是LLVM支持前向引用的标准方式。

    1. // Emit then value.
    4. Value *ThenV = Then->codegen();
    5. if (!ThenV)
    6.   return nullptr;
    8. Builder.CreateBr(MergeBB);
    9. // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
    10. ThenBB = Builder.GetInsertBlock();

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

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

    这里的最后一行非常微妙，但非常重要。基本问题是当我们在合并块中创建Phi节点时，我们需要设置块/值对，以指示Phi将如何工作。重要的是，Phi节点期望在CFG中具有块的每个前任的条目。那么，为什么我们在将它们设置为ThenBB 5行以上时获取当前块？问题是“Then”表达式实际上可能会改变Builder发出的块，例如，如果它包含嵌套的“if / then / else”表达式。因为codegen()递归调用可以任意改变当前块的概念，所以我们需要获得将设置Phi节点的代码的最新值。

    1. // Emit else block.
    2. TheFunction->getBasicBlockList().push_back(ElseBB);
    3. Builder.SetInsertPoint(ElseBB);
    5. Value *ElseV = Else->codegen();
    6. if (!ElseV)
    7.   return nullptr;
    9. Builder.CreateBr(MergeBB);
    10. // codegen of 'Else' can change the current block, update ElseBB for the PHI.
    11. ElseBB = Builder.GetInsertBlock();

    ‘else’块的代码生成与’then’块的codegen基本相同。唯一显着的区别是第一行，它将’else’块添加到函数中。先前回想一下，’else’块已创建，但未添加到该函数中。既然发出了’then’和’else’块，我们可以使用合并代码完成：

    1.   // Emit merge block.
    2.   TheFunction->getBasicBlockList().push_back(MergeBB);
    3.   Builder.SetInsertPoint(MergeBB);
    4.   PHINode *PN =
    5.     Builder.CreatePHI(Type::getDoubleTy(TheContext), 2, "iftmp");
    7.   PN->addIncoming(ThenV, ThenBB);
    8.   PN->addIncoming(ElseV, ElseBB);
    9.   return PN;
    10. }

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

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

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

    5.3 ‘for’循环表达式

    现在我们知道如何向语言添加基本控制流构造，我们有了添加更多功能的工具。让我们添加更积极的东西，一个’for’表达式：

    1. extern putchard(char);
    2. def printstar(n)
    3.   for i = 1, i < n, 1.0 in
    4.     putchard(42);  # ascii 42 = '*'
    6. # print 100 '*' characters
    7. printstar(100);

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

    词法分析器扩展与if / then / else相同：

    1. ... in enum Token ...
    2. // control
    3. tok_if = -6, tok_then = -7, tok_else = -8,
    4. tok_for = -9, tok_in = -10
    6. ... in gettok ...
    7. if (IdentifierStr == "def")
    8.   return tok_def;
    9. if (IdentifierStr == "extern")
    10.   return tok_extern;
    11. if (IdentifierStr == "if")
    12.   return tok_if;
    13. if (IdentifierStr == "then")
    14.   return tok_then;
    15. if (IdentifierStr == "else")
    16.   return tok_else;
    17. if (IdentifierStr == "for")
    18.   return tok_for;
    19. if (IdentifierStr == "in")
    20.   return tok_in;
    21. return tok_identifier;

    5.3.2 ‘for’循环的AST扩​​展

    AST节点也很简单。它基本上归结为捕获节点中的变量名称和组成表达式。

    1. /// ForExprAST - Expression class for for/in.
    2. class ForExprAST : public ExprAST {
    3.   std::string VarName;
    4.   std::unique_ptr<ExprAST> Start, End, Step, Body;
    6. public:
    7.   ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start,
    8.              std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step,
    9.              std::unique_ptr<ExprAST> Body)
    10.     : VarName(VarName), Start(std::move(Start)), End(std::move(End)),
    11.       Step(std::move(Step)), Body(std::move(Body)) {}
    13.   Value *codegen() override;
    14. };

    5.3.3 ‘for’循环的解析器扩展

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

    1. /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
    2. static std::unique_ptr<ExprAST> ParseForExpr() {
    3.   getNextToken();  // eat the for.
    5.   if (CurTok != tok_identifier)
    6.     return LogError("expected identifier after for");
    8.   std::string IdName = IdentifierStr;
    9.   getNextToken();  // eat identifier.
    11.   if (CurTok != '=')
    12.     return LogError("expected '=' after for");
    13.   getNextToken();  // eat '='.
    16.   auto Start = ParseExpression();
    17.   if (!Start)
    18.     return nullptr;
    19.   if (CurTok != ',')
    20.     return LogError("expected ',' after for start value");
    21.   getNextToken();
    23.   if (!End)
    24.     return nullptr;
    26.   // The step value is optional.
    27.   std::unique_ptr<ExprAST> Step;
    28.   if (CurTok == ',') {
    29.     getNextToken();
    30.     Step = ParseExpression();
    32.       return nullptr;
    33.   }
    35.   if (CurTok != tok_in)
    36.     return LogError("expected 'in' after for");
    37.   getNextToken();  // eat 'in'.
    39.   auto Body = ParseExpression();
    40.   if (!Body)
    41.     return nullptr;
    43.   return llvm::make_unique<ForExprAST>(IdName, std::move(Start),
    44.                                        std::move(End), std::move(Step),
    45.                                        std::move(Body));
    46. }
    1. static std::unique_ptr<ExprAST> ParsePrimary() {
    2.   switch (CurTok) {
    3.   default:
    4.     return LogError("unknown token when expecting an expression");
    5.   case tok_identifier:
    6.     return ParseIdentifierExpr();
    7.   case tok_number:
    8.     return ParseNumberExpr();
    9.   case '(':
    10.     return ParseParenExpr();
    11.   case tok_if:
    12.     return ParseIfExpr();
    13.   case tok_for:
    14.     return ParseForExpr();
    15.   }
    16. }

    5.3.4 用于’for’循环的

    现在我们得到了很好的部分：我们想为这件事生成的LLVM IR。通过上面的简单示例，我们获得了这个LLVM IR（请注意，为了清晰起见，生成此转储并禁用优化）：

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

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

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

    完成此操作后，下一步是为循环体的启动设置LLVM基本块。在上面的例子中，整个循环体是一个块，但请记住，体代码本身可以由多个块组成（例如，如果它包含if / then / else或for / in表达式）。

    1. // Make the new basic block for the loop header, inserting after current
    2. // block.
    3. Function *TheFunction = Builder.GetInsertBlock()->getParent();
    4. BasicBlock *PreheaderBB = Builder.GetInsertBlock();
    5. BasicBlock *LoopBB =
    6.     BasicBlock::Create(TheContext, "loop", TheFunction);
    8. // Insert an explicit fall through from the current block to the LoopBB.
    9. Builder.CreateBr(LoopBB);

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

    1. // Start insertion in LoopBB.
    2. Builder.SetInsertPoint(LoopBB);
    4. // Start the PHI node with an entry for Start.
    5. PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(TheContext),
    6.                                       2, VarName.c_str());
    7. Variable->addIncoming(StartVal, PreheaderBB);

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

    1. // Within the loop, the variable is defined equal to the PHI node.  If it
    2. // shadows an existing variable, we have to restore it, so save it now.
    3. Value *OldVal = NamedValues[VarName];
    4. NamedValues[VarName] = Variable;
    6. // Emit the body of the loop.  This, like any other expr, can change the
    7. // current BB.  Note that we ignore the value computed by the body, but don't
    8. // allow an error.
    9. if (!Body->codegen())
    10.   return nullptr;

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

    一旦将循环变量设置到符号表中，代码就会递归代码为body。这允许正文使用循环变量：对它的任何引用自然会在符号表中找到它。

    1. // Emit the step value.
    2. Value *StepVal = nullptr;
    3. if (Step) {
    4.   StepVal = Step->codegen();
    5.   if (!StepVal)
    6.     return nullptr;
    7. } else {
    8.   // If not specified, use 1.0.
    9.   StepVal = ConstantFP::get(TheContext, APFloat(1.0));
    10. }
    12. Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");

    现在身体被发射，我们通过添加步长值计算迭代变量的下一个值，如果不存在则计算1.0。’ NextVar’将是循环的下一次迭代中循环变量的值。

    1. // Compute the end condition.
    2. Value *EndCond = End->codegen();
    3. if (!EndCond)
    4.   return nullptr;
    6. // Convert condition to a bool by comparing non-equal to 0.0.
    7. EndCond = Builder.CreateFCmpONE(
    8.     EndCond, ConstantFP::get(TheContext, APFloat(0.0)), "loopcond");

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

    1. // Create the "after loop" block and insert it.
    2. BasicBlock *LoopEndBB = Builder.GetInsertBlock();
    3. BasicBlock *AfterBB =
    4.     BasicBlock::Create(TheContext, "afterloop", TheFunction);
    6. // Insert the conditional branch into the end of LoopEndBB.
    7. Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
    9. // Any new code will be inserted in AfterBB.
    10. Builder.SetInsertPoint(AfterBB);

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

    1.   // Add a new entry to the PHI node for the backedge.
    2.   Variable->addIncoming(NextVar, LoopEndBB);
    4.   // Restore the unshadowed variable.
    5.   if (OldVal)
    6.     NamedValues[VarName] = OldVal;
    7.   else
    8.     NamedValues.erase(VarName);
    10.   // for expr always returns 0.0.

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

    有了这个，我们总结了本教程中的“向Kaleidoscope添加控制流”一章。在本章中，我们添加了两个控制流构造，并使用它们来激发LLVM IR的几个方面，这些方面对于前端实现者来说非常重要。在我们的传奇的下一章中，我们会变得有点疯狂，并为我们可怜的无辜语言添加用户定义的运算符。

    5.4 完整的代码清单

    下一页：扩展语言：用户定义的运算符