Welcome to the "Implementing a language with LLVM" tutorial. This tutorial runs through the implementation of a simple language, showing how fun and @@ -123,10 +123,10 @@ languages!

This tutorial will be illustrated with a toy language that we'll call "Kaleidoscope" (derived @@ -181,10 +181,10 @@ a Mandelbrot Set at various levels of magnification.

When it comes to implementing a language, the first thing needed is the ability to process a text file and recognize what it says. The traditional @@ -341,8 +341,8 @@ so that you can use the lexer and parser together. src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"> Chris Lattner
- The LLVM Compiler Infrastructure
- Last modified: $Date: 2010-05-07 02:28:04 +0200 (Fri, 07 May 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/LangImpl2.html b/docs/tutorial/LangImpl2.html index f39ed6ccffefd..c6a9bb1ec1c31 100644 --- a/docs/tutorial/LangImpl2.html +++ b/docs/tutorial/LangImpl2.html @@ -11,7 +11,7 @@ -

Kaleidoscope: Implementing a Parser and AST

Up to Tutorial Index

Chapter 2 Introduction

Welcome to Chapter 2 of the "Implementing a language with LLVM" tutorial. This chapter shows you how to use the lexer, built in @@ -61,10 +61,10 @@ Tree.

The Abstract Syntax Tree (AST)

The AST for a program captures its behavior in such a way that it is easy for later stages of the compiler (e.g. code generation) to interpret. We basically @@ -178,10 +178,10 @@ bodies in Kaleidoscope.

Parser Basics

Now that we have an AST to build, we need to define the parser code to build it. The idea here is that we want to parse something like "x+y" (which is @@ -239,11 +239,10 @@ piece of our grammar: numeric literals.

Basic Expression - Parsing

Basic Expression Parsing

We start with numeric literals, because they are the simplest to process. For each production in our grammar, we'll define a function which parses that @@ -394,11 +393,10 @@ They are a bit more complex.

Binary Expression - Parsing

Binary Expression Parsing

Binary expressions are significantly harder to parse because they are often ambiguous. For example, when given the string "x+y*z", the parser can choose @@ -617,10 +615,10 @@ handle function definitions, etc.

Parsing the Rest

The next thing missing is handling of function prototypes. In Kaleidoscope, @@ -714,10 +712,10 @@ actually execute this code we've built!

The Driver

The driver for this simply invokes all of the parsing pieces with a top-level dispatch loop. There isn't much interesting here, so I'll just include the @@ -753,10 +751,10 @@ type "4+5;", and the parser will know you are done.

Conclusions

With just under 400 lines of commented code (240 lines of non-comment, non-blank code), we fully defined our minimal language, including a lexer, @@ -790,10 +788,10 @@ Representation (IR) from the AST.

Full Code Listing

Here is the complete code listing for this and the previous chapter. @@ -1226,8 +1224,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: 2010-05-07 02:28:04 +0200 (Fri, 07 May 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/LangImpl3.html b/docs/tutorial/LangImpl3.html index a320ff7e9064f..47406ca36e418 100644 --- a/docs/tutorial/LangImpl3.html +++ b/docs/tutorial/LangImpl3.html @@ -11,7 +11,7 @@ -

Kaleidoscope: Code generation to LLVM IR

Up to Tutorial Index

Chapter 3 Introduction

Welcome to Chapter 3 of the "Implementing a language with LLVM" tutorial. This chapter shows you how to transform the .

Code Generation Setup

In order to generate LLVM IR, we want some simple setup to get started. First @@ -147,10 +147,10 @@ has already been done, and we'll just use it to emit code.

Expression Code Generation

Generating LLVM code for expression nodes is very straightforward: less than 45 lines of commented code for all four of our expression nodes. First @@ -293,10 +293,10 @@ basic framework.

Function Code Generation

Code generation for prototypes and functions must handle a number of details, which make their code less beautiful than expression code @@ -515,11 +515,10 @@ def bar() foo(1, 2); # error, unknown function "foo"

Driver Changes and -Closing Thoughts

Driver Changes and Closing Thoughts

For now, code generation to LLVM doesn't really get us much, except that we can @@ -657,10 +656,10 @@ support to this so we can actually start running code!

Full Code Listing

Here is the complete code listing for our running example, enhanced with the @@ -1262,8 +1261,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: 2011-02-15 01:24:32 +0100 (Tue, 15 Feb 2011) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/LangImpl4.html b/docs/tutorial/LangImpl4.html index a2511d959e7b9..5b8990e441e46 100644 --- a/docs/tutorial/LangImpl4.html +++ b/docs/tutorial/LangImpl4.html @@ -11,7 +11,7 @@ -

Kaleidoscope: Adding JIT and Optimizer Support

Up to Tutorial Index

Chapter 4 Introduction

Welcome to Chapter 4 of the "Implementing a language with LLVM" tutorial. Chapters 1-3 described the implementation of a simple @@ -48,11 +48,10 @@ for the Kaleidoscope language.

Trivial Constant -Folding

Trivial Constant Folding

Our demonstration for Chapter 3 is elegant and easy to extend. Unfortunately, @@ -134,11 +133,10 @@ range of optimizations that you can use, in the form of "passes".

LLVM Optimization - Passes

LLVM Optimization Passes

LLVM provides many optimization passes, which do many different sorts of things and have different tradeoffs. Unlike other systems, LLVM doesn't hold @@ -266,10 +264,10 @@ executing it!

Adding a JIT Compiler

Code that is available in LLVM IR can have a wide variety of tools applied to it. For example, you can run optimizations on it (as we did above), @@ -474,10 +472,10 @@ tackling some interesting LLVM IR issues along the way.

Full Code Listing

Here is the complete code listing for our running example, enhanced with the @@ -1078,7 +1076,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); @@ -1130,8 +1128,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: 2010-11-16 18:28:22 +0100 (Tue, 16 Nov 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/LangImpl5.html b/docs/tutorial/LangImpl5.html index d2c3bd03dc4ec..4fc23a1494295 100644 --- a/docs/tutorial/LangImpl5.html +++ b/docs/tutorial/LangImpl5.html @@ -11,7 +11,7 @@ -

Kaleidoscope: Extending the Language: Control Flow

Up to Tutorial Index

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

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 @@ -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:

@@ -472,7 +466,7 @@ are emitted, we can finish up with the merge code:

// Emit merge block. TheFunction->getBasicBlockList().push_back(MergeBB); Builder.SetInsertPoint(MergeBB); - PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), + PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp"); PN->addIncoming(ThenV, ThenBB); @@ -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 @@ -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:

@@ -746,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::getDoubleTy(getGlobalContext()), VarName.c_str()); + PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str()); Variable->addIncoming(StartVal, PreheaderBB);

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

+ -

Full Code Listing

Here is the complete code listing for our running example, enhanced with the @@ -1452,7 +1443,7 @@ Value *IfExprAST::Codegen() { // Emit merge block. TheFunction->getBasicBlockList().push_back(MergeBB); Builder.SetInsertPoint(MergeBB); - PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), + PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp"); PN->addIncoming(ThenV, ThenBB); @@ -1494,7 +1485,7 @@ Value *ForExprAST::Codegen() { Builder.SetInsertPoint(LoopBB); // Start the PHI node with an entry for Start. - PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 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 @@ -1721,7 +1712,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); @@ -1773,8 +1764,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: 2010-11-16 18:28:22 +0100 (Tue, 16 Nov 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/LangImpl6.html b/docs/tutorial/LangImpl6.html index 7ddf3a099cbc3..31d7ff4cd2155 100644 --- a/docs/tutorial/LangImpl6.html +++ b/docs/tutorial/LangImpl6.html @@ -11,7 +11,7 @@ -

Kaleidoscope: Extending the Language: User-defined Operators

Up to Tutorial Index

Chapter 6 Introduction

Welcome to Chapter 6 of the "Implementing a language with LLVM" tutorial. At this point in our tutorial, we now have a fully @@ -60,10 +60,10 @@ an example of what you can build with Kaleidoscope and its feature set.

User-defined Operators: the Idea

The "operator overloading" that we will add to Kaleidoscope is more general than @@ -125,10 +125,10 @@ operators.

User-defined Binary Operators

Adding support for user-defined binary operators is pretty simple with our current framework. We'll first add support for the unary/binary keywords:

@@ -342,10 +342,10 @@ see what it takes.

User-defined Unary Operators

Since we don't currently support unary operators in the Kaleidoscope language, we'll need to add everything to support them. Above, we added simple @@ -491,10 +491,10 @@ is simpler primarily because it doesn't need to handle any predefined operators.

Kicking the Tires

It is somewhat hard to believe, but with a few simple extensions we've covered in the last chapters, we have grown a real-ish language. With this, we @@ -796,10 +796,10 @@ add variable mutation without building SSA in your front-end.

Full Code Listing

Here is the complete code listing for our running example, enhanced with the @@ -1475,7 +1475,7 @@ Value *IfExprAST::Codegen() { // Emit merge block. TheFunction->getBasicBlockList().push_back(MergeBB); Builder.SetInsertPoint(MergeBB); - PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), + PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp"); PN->addIncoming(ThenV, ThenBB); @@ -1517,7 +1517,7 @@ Value *ForExprAST::Codegen() { Builder.SetInsertPoint(LoopBB); // Start the PHI node with an entry for Start. - PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 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 @@ -1758,7 +1758,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); @@ -1810,8 +1810,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: 2010-11-16 18:28:22 +0100 (Tue, 16 Nov 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/LangImpl7.html b/docs/tutorial/LangImpl7.html index 3b36129d67163..a4a21f1aed22e 100644 --- a/docs/tutorial/LangImpl7.html +++ b/docs/tutorial/LangImpl7.html @@ -12,7 +12,7 @@ -

Kaleidoscope: Extending the Language: Mutable Variables

Up to Tutorial Index

Chapter 7 Introduction

Welcome to Chapter 7 of the "Implementing a language with LLVM" tutorial. In chapters 1 through 6, we've built a very @@ -66,10 +66,10 @@ support for this, though the way it works is a bit unexpected for some.

Why is this a hard problem?

To understand why mutable variables cause complexities in SSA construction, @@ -140,10 +140,10 @@ logic.

Memory in LLVM

The 'trick' here is that while LLVM does require all register values to be in SSA form, it does not require (or permit) memory objects to be in SSA form. @@ -321,11 +321,10 @@ variables now!

Mutable Variables in -Kaleidoscope

Mutable Variables in Kaleidoscope

Now that we know the sort of problem we want to tackle, lets see what this looks like in the context of our little Kaleidoscope language. We're going to @@ -378,11 +377,10 @@ Kaleidoscope to support new variable definitions.

Adjusting Existing Variables for -Mutation

Adjusting Existing Variables for Mutation

The symbol table in Kaleidoscope is managed at code generation time by the @@ -648,10 +646,10 @@ we'll add the assignment operator.

New Assignment Operator

With our current framework, adding a new assignment operator is really simple. We will parse it just like any other binary operator, but handle it @@ -745,11 +743,10 @@ add this next!

User-defined Local -Variables

User-defined Local Variables

Adding var/in is just like any other other extensions we made to Kaleidoscope: we extend the lexer, the parser, the AST and the code generator. @@ -979,10 +976,10 @@ anywhere in sight.

Full Code Listing

Here is the complete code listing for our running example, enhanced with mutable @@ -1755,7 +1752,7 @@ Value *IfExprAST::Codegen() { // Emit merge block. TheFunction->getBasicBlockList().push_back(MergeBB); Builder.SetInsertPoint(MergeBB); - PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), + PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp"); PN->addIncoming(ThenV, ThenBB); @@ -2160,8 +2157,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: 2010-11-16 18:28:22 +0100 (Tue, 16 Nov 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/LangImpl8.html b/docs/tutorial/LangImpl8.html index fe42a22e03040..cc55d401a4c76 100644 --- a/docs/tutorial/LangImpl8.html +++ b/docs/tutorial/LangImpl8.html @@ -11,8 +11,7 @@ -

Kaleidoscope: Conclusion and other useful LLVM - tidbits

Kaleidoscope: Conclusion and other useful LLVM tidbits

Up to Tutorial Index

Tutorial Conclusion

Welcome to the the final chapter of the "Implementing a language with LLVM" tutorial. In the course of this tutorial, we have grown @@ -154,23 +153,19 @@ are very useful if you want to take advantage of LLVM's capabilities.

Properties of the LLVM -IR

Properties of the LLVM IR

We have a couple common questions about code in the LLVM IR form - lets just get these out of the way right now, shall we?

- -

Target -Independence

Target Independence

Kaleidoscope is an example of a "portable language": any program written in Kaleidoscope will work the same way on any target that it runs on. Many other @@ -221,10 +216,10 @@ in-kernel language.

Safety Guarantees

Many of the languages above are also "safe" languages: it is impossible for a program written in Java to corrupt its address space and crash the process @@ -243,11 +238,10 @@ list if you are interested in more details.

Language-Specific -Optimizations

Language-Specific Optimizations

One thing about LLVM that turns off many people is that it does not solve all the world's problems in one system (sorry 'world hunger', someone else will have @@ -297,24 +291,23 @@ language-specific AST.

+ -

Tips and Tricks

There is a variety of useful tips and tricks that you come to know after working on/with LLVM that aren't obvious at first glance. Instead of letting everyone rediscover them, this section talks about some of these issues.

- -

Implementing portable -offsetof/sizeof

Implementing portable offsetof/sizeof

One interesting thing that comes up, if you are trying to keep the code generated by your compiler "target independent", is that you often need to know @@ -331,11 +324,10 @@ in a portable way.

Garbage Collected -Stack Frames

Garbage Collected Stack Frames

Some languages want to explicitly manage their stack frames, often so that they are garbage collected or to allow easy implementation of closures. There @@ -349,6 +341,8 @@ Passing Style and the use of tail calls (which LLVM also supports).

@@ -358,8 +352,8 @@ Passing Style and the use of tail calls (which LLVM also supports).

src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"> Chris Lattner
- The LLVM Compiler Infrastructure
- Last modified: $Date: 2010-05-07 02:28:04 +0200 (Fri, 07 May 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $

diff --git a/docs/tutorial/OCamlLangImpl1.html b/docs/tutorial/OCamlLangImpl1.html index 44106132fbe8f..7cae68c988abb 100644 --- a/docs/tutorial/OCamlLangImpl1.html +++ b/docs/tutorial/OCamlLangImpl1.html @@ -12,7 +12,7 @@ -

Kaleidoscope: Tutorial Introduction and the Lexer

Up to Tutorial Index

Tutorial Introduction

Welcome to the "Implementing a language with LLVM" tutorial. This tutorial runs through the implementation of a simple language, showing how fun and @@ -130,10 +130,10 @@ languages!

The Basic Language

This tutorial will be illustrated with a toy language that we'll call "Kaleidoscope" (derived @@ -188,10 +188,10 @@ a Mandelbrot Set at various levels of magnification.

The Lexer

When it comes to implementing a language, the first thing needed is the ability to process a text file and recognize what it says. The traditional @@ -358,8 +358,8 @@ include a driver so that you can use the lexer and parser together. Chris Lattner
Erick Tryzelaar
- The LLVM Compiler Infrastructure
- Last modified: $Date: 2010-05-07 02:28:04 +0200 (Fri, 07 May 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/OCamlLangImpl2.html b/docs/tutorial/OCamlLangImpl2.html index 41d0956e46202..e1bb871225060 100644 --- a/docs/tutorial/OCamlLangImpl2.html +++ b/docs/tutorial/OCamlLangImpl2.html @@ -12,7 +12,7 @@ -

Kaleidoscope: Implementing a Parser and AST

Up to Tutorial Index

Chapter 2 Introduction

Welcome to Chapter 2 of the "Implementing a language with LLVM in Objective Caml" tutorial. This chapter shows you how to use @@ -65,10 +65,10 @@ Tree.

The Abstract Syntax Tree (AST)

The AST for a program captures its behavior in such a way that it is easy for later stages of the compiler (e.g. code generation) to interpret. We basically @@ -146,10 +146,10 @@ bodies in Kaleidoscope.

Parser Basics

Now that we have an AST to build, we need to define the parser code to build it. The idea here is that we want to parse something like "x+y" (which is @@ -181,11 +181,10 @@ piece of our grammar: numeric literals.

Basic Expression - Parsing

Basic Expression Parsing

We start with numeric literals, because they are the simplest to process. For each production in our grammar, we'll define a function which parses that @@ -303,11 +302,10 @@ They are a bit more complex.

Binary Expression - Parsing

Binary Expression Parsing

Binary expressions are significantly harder to parse because they are often ambiguous. For example, when given the string "x+y*z", the parser can choose @@ -517,10 +515,10 @@ handle function definitions, etc.

Parsing the Rest

The next thing missing is handling of function prototypes. In Kaleidoscope, @@ -596,10 +594,10 @@ actually execute this code we've built!

The Driver

The driver for this simply invokes all of the parsing pieces with a top-level dispatch loop. There isn't much interesting here, so I'll just include the @@ -652,10 +650,10 @@ type "4+5;", and the parser will know you are done.

Conclusions

With just under 300 lines of commented code (240 lines of non-comment, non-blank code), we fully defined our minimal language, including a lexer, @@ -689,10 +687,10 @@ Representation (IR) from the AST.

Full Code Listing

Here is the complete code listing for this and the previous chapter. @@ -1038,8 +1036,8 @@ main () Chris Lattner Erick Tryzelaar
- The LLVM Compiler Infrastructure
- Last modified: $Date: 2010-05-07 02:28:04 +0200 (Fri, 07 May 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/OCamlLangImpl3.html b/docs/tutorial/OCamlLangImpl3.html index c7c53709a0607..e52bb6c9008db 100644 --- a/docs/tutorial/OCamlLangImpl3.html +++ b/docs/tutorial/OCamlLangImpl3.html @@ -12,7 +12,7 @@ -

Kaleidoscope: Code generation to LLVM IR

Up to Tutorial Index

Chapter 3 Introduction

Welcome to Chapter 3 of the "Implementing a language with LLVM" tutorial. This chapter shows you how to transform the

Code Generation Setup

In order to generate LLVM IR, we want some simple setup to get started. First @@ -128,10 +128,10 @@ that this has already been done, and we'll just use it to emit code.

Expression Code Generation

Generating LLVM code for expression nodes is very straightforward: less than 30 lines of commented code for all four of our expression nodes. First @@ -263,10 +263,10 @@ basic framework.

Function Code Generation

Code generation for prototypes and functions must handle a number of details, which make their code less beautiful than expression code @@ -466,11 +466,10 @@ def bar() foo(1, 2); # error, unknown function "foo"

Driver Changes and -Closing Thoughts

Driver Changes and Closing Thoughts

For now, code generation to LLVM doesn't really get us much, except that we can @@ -607,10 +606,10 @@ support to this so we can actually start running code!

Full Code Listing

Here is the complete code listing for our running example, enhanced with the @@ -1086,8 +1085,8 @@ main () Chris Lattner
Erick Tryzelaar
- The LLVM Compiler Infrastructure
- Last modified: $Date: 2010-05-28 19:07:41 +0200 (Fri, 28 May 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/OCamlLangImpl4.html b/docs/tutorial/OCamlLangImpl4.html index a86184c945203..db164d5e6a1af 100644 --- a/docs/tutorial/OCamlLangImpl4.html +++ b/docs/tutorial/OCamlLangImpl4.html @@ -12,7 +12,7 @@ -

Kaleidoscope: Adding JIT and Optimizer Support

Up to Tutorial Index

Chapter 4 Introduction

Welcome to Chapter 4 of the "Implementing a language with LLVM" tutorial. Chapters 1-3 described the implementation of a simple @@ -52,11 +52,10 @@ for the Kaleidoscope language.

Trivial Constant -Folding

Trivial Constant Folding

Note: the default IRBuilder now always includes the constant folding optimisations below.

@@ -148,11 +147,10 @@ range of optimizations that you can use, in the form of "passes".

LLVM Optimization - Passes

LLVM Optimization Passes

LLVM provides many optimization passes, which do many different sorts of things and have different tradeoffs. Unlike other systems, LLVM doesn't hold @@ -283,10 +281,10 @@ executing it!

Adding a JIT Compiler

Code that is available in LLVM IR can have a wide variety of tools applied to it. For example, you can run optimizations on it (as we did above), @@ -486,10 +484,10 @@ constructs, tackling some interesting LLVM IR issues along the way.

Full Code Listing

Here is the complete code listing for our running example, enhanced with the @@ -1022,8 +1020,8 @@ extern double putchard(double X) { Chris Lattner
Erick Tryzelaar
- The LLVM Compiler Infrastructure
- Last modified: $Date: 2010-05-28 19:07:41 +0200 (Fri, 28 May 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/OCamlLangImpl5.html b/docs/tutorial/OCamlLangImpl5.html index 3173803cfa6b6..ca796916ef145 100644 --- a/docs/tutorial/OCamlLangImpl5.html +++ b/docs/tutorial/OCamlLangImpl5.html @@ -12,7 +12,7 @@ -

Kaleidoscope: Extending the Language: Control Flow

Up to Tutorial Index

Chapter 5 Introduction

Welcome to Chapter 5 of the "Implementing a language with LLVM" tutorial. Parts 1-4 described the implementation of the simple @@ -69,10 +69,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 @@ -112,15 +112,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 variants for the relevant tokens:

@@ -153,11 +150,10 @@ stuff:

AST Extensions for - If/Then/Else

AST Extensions for If/Then/Else

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

@@ -175,11 +171,10 @@ type expr =

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 @@ -214,10 +209,10 @@ let rec parse_primary = parser

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 @@ -331,11 +326,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:

@@ -492,11 +486,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 @@ -525,14 +521,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:

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

AST Extensions for -the 'for' Loop

AST Extensions for the 'for' Loop

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

@@ -580,11 +572,10 @@ type expr =

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 @@ -628,11 +619,10 @@ let rec parse_primary = parser

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 @@ -674,11 +664,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:

@@ -851,11 +840,13 @@ to our poor innocent language.

+ -

Full Code Listing

Here is the complete code listing for our running example, enhanced with the @@ -1562,8 +1553,8 @@ operators Chris Lattner
Erick Tryzelaar
- The LLVM Compiler Infrastructure
- Last modified: $Date: 2010-05-28 19:07:41 +0200 (Fri, 28 May 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/OCamlLangImpl6.html b/docs/tutorial/OCamlLangImpl6.html index 1d4f8c7509f8a..bde429b5afcf9 100644 --- a/docs/tutorial/OCamlLangImpl6.html +++ b/docs/tutorial/OCamlLangImpl6.html @@ -12,7 +12,7 @@ -

Kaleidoscope: Extending the Language: User-defined Operators

Up to Tutorial Index

Chapter 6 Introduction

Welcome to Chapter 6 of the "Implementing a language with LLVM" tutorial. At this point in our tutorial, we now have a fully @@ -64,10 +64,10 @@ an example of what you can build with Kaleidoscope and its feature set.

User-defined Operators: the Idea

The "operator overloading" that we will add to Kaleidoscope is more general than @@ -129,10 +129,10 @@ operators.

User-defined Binary Operators

Adding support for user-defined binary operators is pretty simple with our current framework. We'll first add support for the unary/binary keywords:

@@ -320,10 +320,10 @@ see what it takes.

User-defined Unary Operators

Since we don't currently support unary operators in the Kaleidoscope language, we'll need to add everything to support them. Above, we added simple @@ -472,10 +472,10 @@ is simpler primarily because it doesn't need to handle any predefined operators.

Kicking the Tires

It is somewhat hard to believe, but with a few simple extensions we've covered in the last chapters, we have grown a real-ish language. With this, we @@ -778,10 +778,10 @@ add variable mutation without building SSA in your front-end.

Full Code Listing

Here is the complete code listing for our running example, enhanced with the @@ -1567,8 +1567,8 @@ SSA construction Chris Lattner
Erick Tryzelaar
- The LLVM Compiler Infrastructure
- Last modified: $Date: 2010-06-21 22:31:30 +0200 (Mon, 21 Jun 2010) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/OCamlLangImpl7.html b/docs/tutorial/OCamlLangImpl7.html index a9fcd704cf8b5..a48e679cecef0 100644 --- a/docs/tutorial/OCamlLangImpl7.html +++ b/docs/tutorial/OCamlLangImpl7.html @@ -13,7 +13,7 @@ -

Kaleidoscope: Extending the Language: Mutable Variables

Up to Tutorial Index

Chapter 7 Introduction

Welcome to Chapter 7 of the "Implementing a language with LLVM" tutorial. In chapters 1 through 6, we've built a very @@ -70,10 +70,10 @@ support for this, though the way it works is a bit unexpected for some.

Why is this a hard problem?

To understand why mutable variables cause complexities in SSA construction, @@ -144,10 +144,10 @@ logic.

Memory in LLVM

The 'trick' here is that while LLVM does require all register values to be in SSA form, it does not require (or permit) memory objects to be in SSA form. @@ -325,11 +325,10 @@ variables now!

Mutable Variables in -Kaleidoscope

Mutable Variables in Kaleidoscope

Now that we know the sort of problem we want to tackle, lets see what this looks like in the context of our little Kaleidoscope language. We're going to @@ -382,11 +381,10 @@ Kaleidoscope to support new variable definitions.

Adjusting Existing Variables for -Mutation

Adjusting Existing Variables for Mutation

The symbol table in Kaleidoscope is managed at code generation time by the @@ -672,10 +670,10 @@ we'll add the assignment operator.

New Assignment Operator

With our current framework, adding a new assignment operator is really simple. We will parse it just like any other binary operator, but handle it @@ -773,11 +771,10 @@ add this next!

User-defined Local -Variables

User-defined Local Variables

Adding var/in is just like any other other extensions we made to Kaleidoscope: we extend the lexer, the parser, the AST and the code generator. @@ -956,10 +953,10 @@ anywhere in sight.

Full Code Listing

Here is the complete code listing for our running example, enhanced with mutable @@ -1887,7 +1884,7 @@ extern double printd(double X) { -Next: Conclusion and other useful LLVM tidbits +Next: Conclusion and other useful LLVM tidbits

@@ -1899,9 +1896,9 @@ extern double printd(double X) { src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"> Chris Lattner
- The LLVM Compiler Infrastructure
+ The LLVM Compiler Infrastructure
Erick Tryzelaar
- Last modified: $Date: 2011-01-01 04:27:43 +0100 (Sat, 01 Jan 2011) $ + Last modified: $Date: 2011-04-23 02:30:22 +0200 (Sat, 23 Apr 2011) $ diff --git a/docs/tutorial/OCamlLangImpl8.html b/docs/tutorial/OCamlLangImpl8.html index 64a62002c4ccd..eed8c03d21cac 100644 --- a/docs/tutorial/OCamlLangImpl8.html +++ b/docs/tutorial/OCamlLangImpl8.html @@ -11,8 +11,7 @@ -

Kaleidoscope: Conclusion and other useful LLVM - tidbits

Kaleidoscope: Conclusion and other useful LLVM tidbits

Up to Tutorial Index

Tutorial Conclusion

Properties of the LLVM -IR

Properties of the LLVM IR

We have a couple common questions about code in the LLVM IR form - lets just get these out of the way right now, shall we?

- -

Target -Independence

Target Independence

Kaleidoscope is an example of a "portable language": any program written in Kaleidoscope will work the same way on any target that it runs on. Many other @@ -221,10 +216,10 @@ in-kernel language.

Safety Guarantees

Language-Specific -Optimizations

Language-Specific Optimizations

+ -

Tips and Tricks

- -

Implementing portable -offsetof/sizeof

Implementing portable offsetof/sizeof

One interesting thing that comes up, if you are trying to keep the code generated by your compiler "target independent", is that you often need to know @@ -331,11 +324,10 @@ in a portable way.

Garbage Collected -Stack Frames

Garbage Collected Stack Frames

@@ -358,7 +352,7 @@ Passing Style and the use of tail calls (which LLVM also supports).

src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"> Chris Lattner
- The LLVM Compiler Infrastructure
+ The LLVM Compiler Infrastructure
Last modified: $Date$

diff --git a/docs/tutorial/index.html b/docs/tutorial/index.html index 11dd5e2d732a5..0a8cae2c2c9b4 100644 --- a/docs/tutorial/index.html +++ b/docs/tutorial/index.html @@ -12,7 +12,7 @@ -

LLVM Tutorial: Table of Contents

Kaleidoscope: Implementing a Language with LLVM -- cgit v1.3