Kaleidoscope: Extending the Language: Control Flow

Welcome to Chapter 5 of the "Implementing a language with LLVM" tutorial. Parts 1-4 described the implementation of the simple @@ -65,10 +65,10 @@ have an if/then/else expression plus a simple 'for' loop.

If/Then/Else

Extending Kaleidoscope to support if/then/else is quite straightforward. It @@ -108,15 +108,12 @@ Since Kaleidoscope allows side-effects, this behavior is important to nail down.

Now that we know what we "want", lets break this down into its constituent pieces.

- -

Lexer Extensions for -If/Then/Else

Lexer Extensions for If/Then/Else

The lexer extensions are straightforward. First we add new enum values for the relevant tokens:

@@ -146,11 +143,10 @@ stuff:

AST Extensions for - If/Then/Else

AST Extensions for If/Then/Else

To represent the new expression we add a new AST node for it:

@@ -172,11 +168,10 @@ public:

Parser Extensions for -If/Then/Else

Parser Extensions for If/Then/Else

Now that we have the relevant tokens coming from the lexer and we have the AST node to build, our parsing logic is relatively straightforward. First we @@ -231,10 +226,10 @@ static ExprAST *ParsePrimary() {

LLVM IR for If/Then/Else

Now that we have it parsing and building the AST, the final piece is adding LLVM code generation support. This is the most interesting part of the @@ -264,20 +259,20 @@ declare double @bar() define double @baz(double %x) { entry: - %ifcond = fcmp one double %x, 0.000000e+00 - br i1 %ifcond, label %then, label %else + %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 + %calltmp = call double @foo() + br label %ifcont else: ; preds = %entry - %calltmp1 = call double @bar() - br label %ifcont + %calltmp1 = call double @bar() + br label %ifcont ifcont: ; preds = %else, %then - %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ] - ret double %iftmp + %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ] + ret double %iftmp }

@@ -347,11 +342,10 @@ directly.

Code Generation for -If/Then/Else

Code Generation for If/Then/Else

In order to generate code for this, we implement the Codegen method for IfExprAST:

@@ -500,11 +494,13 @@ another useful expression that is familiar from non-functional languages...

+ -

'for' Loop Expression

Now that we know how to add basic control flow constructs to the language, we have the tools to add more powerful things. Lets add something more @@ -533,14 +529,11 @@ variables, it will get more useful.

As before, lets talk about the changes that we need to Kaleidoscope to support this.

- -

Lexer Extensions for -the 'for' Loop

Lexer Extensions for the 'for' Loop

The lexer extensions are the same sort of thing as for if/then/else:

@@ -566,11 +559,10 @@ the 'for' Loop

AST Extensions for -the 'for' Loop

AST Extensions for the 'for' Loop

The AST node is just as simple. It basically boils down to capturing the variable name and the constituent expressions in the node.

@@ -593,11 +585,10 @@ public:

Parser Extensions for -the 'for' Loop

Parser Extensions for the 'for' Loop

The parser code is also fairly standard. The only interesting thing here is handling of the optional step value. The parser code handles it by checking to @@ -653,11 +644,10 @@ static ExprAST *ParseForExpr() {

LLVM IR for -the 'for' Loop

LLVM IR for the 'for' Loop

Now we get to the good part: the LLVM IR we want to generate for this thing. With the simple example above, we get this LLVM IR (note that this dump is @@ -670,25 +660,25 @@ declare double @putchard(double) define double @printstar(double %n) { entry: - ; initial value = 1.0 (inlined into phi) - br label %loop + ; 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 + %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 + ; loop always returns 0.0 + ret double 0.000000e+00 }

@@ -699,11 +689,10 @@ expressions, and some basic blocks. Lets see how this fits together.

Code Generation for -the 'for' Loop

Code Generation for the 'for' Loop

The first part of Codegen is very simple: we just output the start expression for the loop value:

@@ -840,10 +829,11 @@ statement.

With the code for the body of the loop complete, we just need to finish up -the control flow for it. This code remembers the end block (for the phi node), then creates the block for the loop exit ("afterloop"). Based on the value of the -exit condition, it creates a conditional branch that chooses between executing -the loop again and exiting the loop. Any future code is emitted in the -"afterloop" block, so it sets the insertion position to it.

+the control flow for it. This code remembers the end block (for the phi node), +then creates the block for the loop exit ("afterloop"). Based on the value of +the exit condition, it creates a conditional branch that chooses between +executing the loop again and exiting the loop. Any future code is emitted in +the "afterloop" block, so it sets the insertion position to it.

@@ -876,11 +866,13 @@ language.

+ -

Full Code Listing

Here is the complete code listing for our running example, enhanced with the @@ -889,10 +881,10 @@ if/then/else and for expressions.. To build this example, use:

-   # Compile
-   g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
-   # Run
-   ./toy
+# Compile
+clang++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
+# Run
+./toy

@@ -903,15 +895,15 @@ if/then/else and for expressions.. To build this example, use: #include "llvm/DerivedTypes.h" #include "llvm/ExecutionEngine/ExecutionEngine.h" #include "llvm/ExecutionEngine/JIT.h" +#include "llvm/IRBuilder.h" #include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/PassManager.h" #include "llvm/Analysis/Verifier.h" #include "llvm/Analysis/Passes.h" -#include "llvm/Target/TargetData.h" -#include "llvm/Target/TargetSelect.h" +#include "llvm/DataLayout.h" #include "llvm/Transforms/Scalar.h" -#include "llvm/Support/IRBuilder.h" +#include "llvm/Support/TargetSelect.h" #include <cstdio> #include <string> #include <map> @@ -1406,7 +1398,7 @@ Value *CallExprAST::Codegen() { if (ArgsV.back() == 0) return 0; } - return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp"); + return Builder.CreateCall(CalleeF, ArgsV, "calltmp"); } Value *IfExprAST::Codegen() { @@ -1555,8 +1547,8 @@ Value *ForExprAST::Codegen() { Function *PrototypeAST::Codegen() { // Make the function type: double(double,double) etc. - std::vector<const Type*> Doubles(Args.size(), - Type::getDoubleTy(getGlobalContext())); + std::vector<Type*> Doubles(Args.size(), + Type::getDoubleTy(getGlobalContext())); FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false); @@ -1721,7 +1713,7 @@ int main() { // Create the JIT. This takes ownership of the module. std::string ErrStr; - TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create(); + TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create(); if (!TheExecutionEngine) { fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str()); exit(1); @@ -1731,7 +1723,7 @@ int main() { // Set up the optimizer pipeline. Start with registering info about how the // target lays out data structures. - OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData())); + OurFPM.add(new DataLayout(*TheExecutionEngine->getDataLayout())); // Provide basic AliasAnalysis support for GVN. OurFPM.add(createBasicAliasAnalysisPass()); // Do simple "peephole" optimizations and bit-twiddling optzns.