Chapter 5 Introduction
-Welcome to Chapter 5 of the "Implementing a language with LLVM" tutorial. Parts 1-4 described the implementation of the simple @@ -65,14 +65,14 @@ 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 -basically requires adding lexer support for this "new" concept to the lexer, +basically requires adding support for this "new" concept to the lexer, parser, AST, and LLVM code emitter. This example is nice, because it shows how easy it is to "grow" a language over time, incrementally extending it as new ideas are discovered.
@@ -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
-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
-To represent the new expression we add a new AST node for it:
@@ -172,11 +168,10 @@ public: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 }
Another way to get this is to call "F->viewCFG()" or "F->viewCFGOnly()" (where F is a "Function*") either by @@ -347,11 +342,10 @@ directly.
Code Generation for If/Then/Else
-In order to generate code for this, we implement the Codegen method for IfExprAST:
@@ -364,7 +358,7 @@ Value *IfExprAST::Codegen() { // Convert condition to a bool by comparing equal to 0.0. CondV = Builder.CreateFCmpONE(CondV, - getGlobalContext().getConstantFP(APFloat(0.0)), + ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond");'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 @@ -532,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
-The lexer extensions are the same sort of thing as for if/then/else:
@@ -565,11 +559,10 @@ the 'for' LoopAST 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.
@@ -592,11 +585,10 @@ public: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 @@ -652,11 +644,10 @@ static ExprAST *ParseForExpr() {
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 @@ -669,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 = add 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 }
Code Generation for the 'for' Loop
-The first part of Codegen is very simple: we just output the start expression for the loop value:
@@ -727,7 +717,7 @@ block, but remember that the body code itself could consist of multiple blocks // block. Function *TheFunction = Builder.GetInsertBlock()->getParent(); BasicBlock *PreheaderBB = Builder.GetInsertBlock(); - BasicBlock *LoopBB = BasicBlock::Create("loop", TheFunction); + BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction); // Insert an explicit fall through from the current block to the LoopBB. Builder.CreateBr(LoopBB); @@ -745,7 +735,7 @@ create an unconditional branch for the fall-through between the two blocks. Builder.SetInsertPoint(LoopBB); // Start the PHI node with an entry for Start. - PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str()); + PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str()); Variable->addIncoming(StartVal, PreheaderBB);
// Create the "after loop" block and insert it.
BasicBlock *LoopEndBB = Builder.GetInsertBlock();
- BasicBlock *AfterBB = BasicBlock::Create("afterloop", TheFunction);
+ BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
// Insert the conditional branch into the end of LoopEndBB.
Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
@@ -839,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.
@@ -856,7 +847,7 @@ the loop again and exiting the loop. Any future code is emitted in the
NamedValues.erase(VarName);
// for expr always returns 0.0.
- return TheFunction->getContext().getNullValue(Type::DoubleTy);
+ return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
}
Full Code Listing
-Here is the complete code listing for our running example, enhanced with the @@ -888,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
#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/ModuleProvider.h"
#include "llvm/PassManager.h"
#include "llvm/Analysis/Verifier.h"
-#include "llvm/Target/TargetData.h"
+#include "llvm/Analysis/Passes.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>
@@ -1059,7 +1054,8 @@ public:
};
/// PrototypeAST - This class represents the "prototype" for a function,
-/// which captures its argument names as well as if it is an operator.
+/// which captures its name, and its argument names (thus implicitly the number
+/// of arguments the function takes).
class PrototypeAST {
std::string Name;
std::vector<std::string> Args;
@@ -1086,7 +1082,7 @@ public:
//===----------------------------------------------------------------------===//
/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
-/// token the parser it looking at. getNextToken reads another token from the
+/// 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() {
@@ -1134,9 +1130,9 @@ static ExprAST *ParseIdentifierExpr() {
ExprAST *Arg = ParseExpression();
if (!Arg) return 0;
Args.push_back(Arg);
-
+
if (CurTok == ')') break;
-
+
if (CurTok != ',')
return Error("Expected ')' or ',' in argument list");
getNextToken();
@@ -1236,7 +1232,6 @@ static ExprAST *ParseForExpr() {
return new ForExprAST(IdName, Start, End, Step, Body);
}
-
/// primary
/// ::= identifierexpr
/// ::= numberexpr
@@ -1360,7 +1355,7 @@ static FunctionPassManager *TheFPM;
Value *ErrorV(const char *Str) { Error(Str); return 0; }
Value *NumberExprAST::Codegen() {
- return getGlobalContext().getConstantFP(APFloat(Val));
+ return ConstantFP::get(getGlobalContext(), APFloat(Val));
}
Value *VariableExprAST::Codegen() {
@@ -1375,13 +1370,14 @@ Value *BinaryExprAST::Codegen() {
if (L == 0 || R == 0) return 0;
switch (Op) {
- case '+': return Builder.CreateAdd(L, R, "addtmp");
- case '-': return Builder.CreateSub(L, R, "subtmp");
- case '*': return Builder.CreateMul(L, R, "multmp");
+ 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::DoubleTy, "booltmp");
+ return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
+ "booltmp");
default: return ErrorV("invalid binary operator");
}
}
@@ -1402,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() {
@@ -1411,16 +1407,16 @@ Value *IfExprAST::Codegen() {
// Convert condition to a bool by comparing equal to 0.0.
CondV = Builder.CreateFCmpONE(CondV,
- getGlobalContext().getConstantFP(APFloat(0.0)),
+ ConstantFP::get(getGlobalContext(), 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("then", TheFunction);
- BasicBlock *ElseBB = BasicBlock::Create("else");
- BasicBlock *MergeBB = BasicBlock::Create("ifcont");
+ BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
+ BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
+ BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
Builder.CreateCondBr(CondV, ThenBB, ElseBB);
@@ -1448,7 +1444,8 @@ Value *IfExprAST::Codegen() {
// Emit merge block.
TheFunction->getBasicBlockList().push_back(MergeBB);
Builder.SetInsertPoint(MergeBB);
- PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
+ PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
+ "iftmp");
PN->addIncoming(ThenV, ThenBB);
PN->addIncoming(ElseV, ElseBB);
@@ -1480,7 +1477,7 @@ Value *ForExprAST::Codegen() {
// block.
Function *TheFunction = Builder.GetInsertBlock()->getParent();
BasicBlock *PreheaderBB = Builder.GetInsertBlock();
- BasicBlock *LoopBB = BasicBlock::Create("loop", TheFunction);
+ BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
// Insert an explicit fall through from the current block to the LoopBB.
Builder.CreateBr(LoopBB);
@@ -1489,7 +1486,7 @@ Value *ForExprAST::Codegen() {
Builder.SetInsertPoint(LoopBB);
// Start the PHI node with an entry for Start.
- PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
+ PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
Variable->addIncoming(StartVal, PreheaderBB);
// Within the loop, the variable is defined equal to the PHI node. If it
@@ -1510,10 +1507,10 @@ Value *ForExprAST::Codegen() {
if (StepVal == 0) return 0;
} else {
// If not specified, use 1.0.
- StepVal = getGlobalContext().getConstantFP(APFloat(1.0));
+ StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
}
- Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
+ Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
// Compute the end condition.
Value *EndCond = End->Codegen();
@@ -1521,12 +1518,12 @@ Value *ForExprAST::Codegen() {
// Convert condition to a bool by comparing equal to 0.0.
EndCond = Builder.CreateFCmpONE(EndCond,
- getGlobalContext().getConstantFP(APFloat(0.0)),
+ ConstantFP::get(getGlobalContext(), APFloat(0.0)),
"loopcond");
// Create the "after loop" block and insert it.
BasicBlock *LoopEndBB = Builder.GetInsertBlock();
- BasicBlock *AfterBB = BasicBlock::Create("afterloop", TheFunction);
+ BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
// Insert the conditional branch into the end of LoopEndBB.
Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
@@ -1545,13 +1542,15 @@ Value *ForExprAST::Codegen() {
// for expr always returns 0.0.
- return getGlobalContext().getNullValue(Type::DoubleTy);
+ return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
}
Function *PrototypeAST::Codegen() {
// Make the function type: double(double,double) etc.
- std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
- FunctionType *FT = getGlobalContext().getFunctionType(Type::DoubleTy, Doubles, false);
+ std::vector<Type*> Doubles(Args.size(),
+ Type::getDoubleTy(getGlobalContext()));
+ FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
+ Doubles, false);
Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
@@ -1596,7 +1595,7 @@ Function *FunctionAST::Codegen() {
return 0;
// Create a new basic block to start insertion into.
- BasicBlock *BB = BasicBlock::Create("entry", TheFunction);
+ BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
Builder.SetInsertPoint(BB);
if (Value *RetVal = Body->Codegen()) {
@@ -1648,7 +1647,7 @@ static void HandleExtern() {
}
static void HandleTopLevelExpression() {
- // Evaluate a top level expression into an anonymous function.
+ // Evaluate a top-level expression into an anonymous function.
if (FunctionAST *F = ParseTopLevelExpr()) {
if (Function *LF = F->Codegen()) {
// JIT the function, returning a function pointer.
@@ -1656,7 +1655,7 @@ static void HandleTopLevelExpression() {
// Cast it to the right type (takes no arguments, returns a double) so we
// can call it as a native function.
- double (*FP)() = (double (*)())FPtr;
+ double (*FP)() = (double (*)())(intptr_t)FPtr;
fprintf(stderr, "Evaluated to %f\n", FP());
}
} else {
@@ -1671,7 +1670,7 @@ static void MainLoop() {
fprintf(stderr, "ready> ");
switch (CurTok) {
case tok_eof: return;
- case ';': getNextToken(); break; // ignore top level semicolons.
+ case ';': getNextToken(); break; // ignore top-level semicolons.
case tok_def: HandleDefinition(); break;
case tok_extern: HandleExtern(); break;
default: HandleTopLevelExpression(); break;
@@ -1679,8 +1678,6 @@ static void MainLoop() {
}
}
-
-
//===----------------------------------------------------------------------===//
// "Library" functions that can be "extern'd" from user code.
//===----------------------------------------------------------------------===//
@@ -1697,6 +1694,9 @@ double putchard(double X) {
//===----------------------------------------------------------------------===//
int main() {
+ InitializeNativeTarget();
+ LLVMContext &Context = getGlobalContext();
+
// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['<'] = 10;
@@ -1709,38 +1709,45 @@ int main() {
getNextToken();
// Make the module, which holds all the code.
- TheModule = new Module("my cool jit", getGlobalContext());
-
- // Create the JIT.
- TheExecutionEngine = EngineBuilder(TheModule).create();
+ TheModule = new Module("my cool jit", Context);
+
+ // Create the JIT. This takes ownership of the module.
+ std::string ErrStr;
+ TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
+ if (!TheExecutionEngine) {
+ fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
+ exit(1);
+ }
- {
- ExistingModuleProvider OurModuleProvider(TheModule);
- FunctionPassManager OurFPM(&OurModuleProvider);
-
- // Set up the optimizer pipeline. Start with registering info about how the
- // target lays out data structures.
- OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
- // Do simple "peephole" optimizations and bit-twiddling optzns.
- OurFPM.add(createInstructionCombiningPass());
- // Reassociate expressions.
- OurFPM.add(createReassociatePass());
- // Eliminate Common SubExpressions.
- OurFPM.add(createGVNPass());
- // Simplify the control flow graph (deleting unreachable blocks, etc).
- OurFPM.add(createCFGSimplificationPass());
- // Set the global so the code gen can use this.
- TheFPM = &OurFPM;
-
- // Run the main "interpreter loop" now.
- MainLoop();
-
- TheFPM = 0;
+ FunctionPassManager OurFPM(TheModule);
+
+ // Set up the optimizer pipeline. Start with registering info about how the
+ // target lays out data structures.
+ OurFPM.add(new DataLayout(*TheExecutionEngine->getDataLayout()));
+ // Provide basic AliasAnalysis support for GVN.
+ OurFPM.add(createBasicAliasAnalysisPass());
+ // Do simple "peephole" optimizations and bit-twiddling optzns.
+ OurFPM.add(createInstructionCombiningPass());
+ // Reassociate expressions.
+ OurFPM.add(createReassociatePass());
+ // Eliminate Common SubExpressions.
+ OurFPM.add(createGVNPass());
+ // Simplify the control flow graph (deleting unreachable blocks, etc).
+ OurFPM.add(createCFGSimplificationPass());
+
+ OurFPM.doInitialization();
+
+ // Set the global so the code gen can use this.
+ TheFPM = &OurFPM;
+
+ // Run the main "interpreter loop" now.
+ MainLoop();
+
+ TheFPM = 0;
+
+ // Print out all of the generated code.
+ TheModule->dump();
- // Print out all of the generated code.
- TheModule->dump();
- } // Free module provider (and thus the module) and pass manager.
-
return 0;
}
@@ -1758,8 +1765,8 @@ int main() {
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!">
Chris Lattner- The LLVM Compiler Infrastructure
- Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date$