<div class="doc_title">Kaleidoscope: Extending the Language: User-defined Operators</div>
+<ul>
+<li><a href="index.html">Up to Tutorial Index</a></li>
+<li>Chapter 6
+ <ol>
+ <li><a href="#intro">Chapter 6 Introduction</a></li>
+ <li><a href="#idea">User-defined Operators: the Idea</a></li>
+ <li><a href="#binary">User-defined Binary Operators</a></li>
+ <li><a href="#unary">User-defined Unary Operators</a></li>
+ <li><a href="#example">Kicking the Tires</a></li>
+ <li><a href="#code">Full Code Listing</a></li>
+ </ol>
+</li>
+<li><a href="LangImpl7.html">Chapter 7</a>: Extending the Language: Mutable
+Variables / SSA Construction</li>
+</ul>
+
<div class="doc_author">
<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="intro">Part 6 Introduction</a></div>
+<div class="doc_section"><a name="intro">Chapter 6 Introduction</a></div>
<!-- *********************************************************************** -->
<div class="doc_text">
-<p>Welcome to Part 6 of the "<a href="index.html">Implementing a language with
-LLVM</a>" tutorial. At this point in our tutorial, we now have a fully
-functional language that is fairly minimal, but also useful. One big problem
-with it though is that it doesn't have many useful operators (like division,
-logical negation, or even any comparisons other than less-than.</p>
+<p>Welcome to Chapter 6 of the "<a href="index.html">Implementing a language
+with LLVM</a>" tutorial. At this point in our tutorial, we now have a fully
+functional language that is fairly minimal, but also useful. There
+is still one big problem with it, however. Our language doesn't have many
+useful operators (like division, logical negation, or even any comparisons
+besides less-than).</p>
<p>This chapter of the tutorial takes a wild digression into adding user-defined
-operators to the simple and beautiful Kaleidoscope language, giving us a
-simple and ugly language in some ways, but also a powerful one at the same time.
+operators to the simple and beautiful Kaleidoscope language. This digression now gives
+us a simple and ugly language in some ways, but also a powerful one at the same time.
One of the great things about creating your own language is that you get to
-decide what is good or bad. In this tutorial we'll assume that it is okay and
+decide what is good or bad. In this tutorial we'll assume that it is okay to
use this as a way to show some interesting parsing techniques.</p>
-<p>At the end of this tutorial, we'll <a href="#example">run through a nice
-little example</a> that shows an example application that you can build with
-Kaleidoscope and the feature set it now has.</p>
+<p>At the end of this tutorial, we'll run through an example Kaleidoscope
+application that <a href="#example">renders the Mandelbrot set</a>. This gives
+an example of what you can build with Kaleidoscope and its feature set.</p>
</div>
languages like C++. In C++, you are only allowed to redefine existing
operators: you can't programatically change the grammar, introduce new
operators, change precedence levels, etc. In this chapter, we will add this
-capability to Kaleidoscope, which will allow us to round out the set of
-operators that are supported, culminating in a more interesting example app.</p>
+capability to Kaleidoscope, which will let the user round out the set of
+operators that are supported.</p>
<p>The point of going into user-defined operators in a tutorial like this is to
-show the power and flexibility of using a hand-written parser. The parser we
-are using so far is using recursive descent for most parts of the grammar, and
+show the power and flexibility of using a hand-written parser. Thus far, the parser
+we have been implementing uses recursive descent for most parts of the grammar and
operator precedence parsing for the expressions. See <a
href="LangImpl2.html">Chapter 2</a> for details. Without using operator
precedence parsing, it would be very difficult to allow the programmer to
# Define > with the same precedence as <.
def binary> 10 (LHS RHS)
- !(LHS < RHS); # alternatively, could just use "RHS < LHS"
+ RHS < LHS;
# Binary "logical or", (note that it does not "short circuit")
def binary| 5 (LHS RHS)
<p>This just adds lexer support for the unary and binary keywords, like we
did in <a href="LangImpl5.html#iflexer">previous chapters</a>. One nice thing
-about our current AST is that we represent binary operators fully generally
-with their ASCII code as the opcode. For our extended operators, we'll use the
+about our current AST, is that we represent binary operators with full generalisation
+by using their ASCII code as the opcode. For our extended operators, we'll use this
same representation, so we don't need any new AST or parser support.</p>
<p>On the other hand, we have to be able to represent the definitions of these
-new operators, in the "def binary| 5" part of the function definition. In the
+new operators, in the "def binary| 5" part of the function definition. In our
grammar so far, the "name" for the function definition is parsed as the
"prototype" production and into the <tt>PrototypeAST</tt> AST node. To
represent our new user-defined operators as prototypes, we have to extend
</pre>
</div>
-<p>This is all fairly straight-forward parsing code, and we have already seen
-a lot of similar code in the past. One interesting piece of this is the part
-that sets up <tt>FnName</tt> for binary operators. This builds names like
-"binary@" for a newly defined "@" operator. This takes advantage of the fact
-that symbol names in the LLVM symbol table are allowed to have any character in
-them, inluding embedded nul characters.</p>
+<p>This is all fairly straightforward parsing code, and we have already seen
+a lot of similar code in the past. One interesting part about the code above is
+the couple lines that set up <tt>FnName</tt> for binary operators. This builds names
+like "binary@" for a newly defined "@" operator. This then takes advantage of the
+fact that symbol names in the LLVM symbol table are allowed to have any character in
+them, including embedded nul characters.</p>
-<p>The next interesting piece is codegen support for these binary operators.
+<p>The next interesting thing to add, is codegen support for these binary operators.
Given our current structure, this is a simple addition of a default case for our
existing binary operator node:</p>
case '-': return Builder.CreateSub(L, R, "subtmp");
case '*': return Builder.CreateMul(L, R, "multmp");
case '<':
- L = Builder.CreateFCmpULT(L, R, "multmp");
+ L = Builder.CreateFCmpULT(L, R, "cmptmp");
// Convert bool 0/1 to double 0.0 or 1.0
return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
<b>default: break;</b>
<p>As you can see above, the new code is actually really simple. It just does
a lookup for the appropriate operator in the symbol table and generates a
function call to it. Since user-defined operators are just built as normal
-functions (because the "prototype" boils down into a function with the right
+functions (because the "prototype" boils down to a function with the right
name) everything falls into place.</p>
-<p>The final missing piece is a bit of top level magic, here:</p>
+<p>The final piece of code we are missing, is a bit of top level magic:</p>
<div class="doc_code">
<pre>
BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();</b>
// Create a new basic block to start insertion into.
- BasicBlock *BB = new BasicBlock("entry", TheFunction);
+ BasicBlock *BB = BasicBlock::Create("entry", TheFunction);
Builder.SetInsertPoint(BB);
if (Value *RetVal = Body->Codegen()) {
<p>Basically, before codegening a function, if it is a user-defined operator, we
register it in the precedence table. This allows the binary operator parsing
-logic we already have to handle it. Since it is a fully-general operator
-precedence parser, this is all we need to do to "extend the grammar".</p>
+logic we already have in place to handle it. Since we are working on a fully-general operator precedence parser, this is all we need to do to "extend the grammar".</p>
-<p>With that, we have useful user-defined binary operators. This builds a lot
+<p>Now we have useful user-defined binary operators. This builds a lot
on the previous framework we built for other operators. Adding unary operators
-is a bit more challenging, because we don't have any framework for it yet, lets
+is a bit more challenging, because we don't have any framework for it yet - lets
see what it takes.</p>
</div>
<div class="doc_text">
<p>Since we don't currently support unary operators in the Kaleidoscope
-langugage, we'll need to add everything for them. Above, we added simple
+language, we'll need to add everything to support them. Above, we added simple
support for the 'unary' keyword to the lexer. In addition to that, we need an
AST node:</p>
</pre>
</div>
-<p>The grammar we add is pretty straight-forward here. If we see a unary
+<p>The grammar we add is pretty straightforward here. If we see a unary
operator when parsing a primary operator, we eat the operator as a prefix and
parse the remaining piece as another unary operator. This allows us to handle
multiple unary operators (e.g. "!!x"). Note that unary operators can't have
ambiguous parses like binary operators can, so there is no need for precedence
information.</p>
-<p>The problem with the above is that we need to call ParseUnary from somewhere.
+<p>The problem with this function, is that we need to call ParseUnary from somewhere.
To do this, we change previous callers of ParsePrimary to call ParseUnary
instead:</p>
</pre>
</div>
-<p>With these two simple changes, we now parse unary operators and build the
+<p>With these two simple changes, we are now able to parse unary operators and build the
AST for them. Next up, we need to add parser support for prototypes, to parse
the unary operator prototype. We extend the binary operator code above
with:</p>
def unary-(v)
0-v;
-# Define > with the same precedence as >. We could also easily define
-# <= etc.
+# Define > with the same precedence as >.
def binary> 10 (LHS RHS)
- !(LHS < RHS);
+ RHS < LHS;
# Binary logical or, which does not short circuit.
def binary| 5 (LHS RHS)
<p>Based on these simple primitive operations, we can start to define more
interesting things. For example, here's a little function that solves for the
-number of iterations it takes for a function in the complex plane to
+number of iterations it takes a function in the complex plane to
converge:</p>
<div class="doc_code">
<tt>mandelconverge</tt> function returns the number of iterations that it takes
for a complex orbit to escape, saturating to 255. This is not a very useful
function by itself, but if you plot its value over a two-dimensional plane,
-you can see the mandelbrot set. Given that we are limited to using putchard
+you can see the Mandelbrot set. Given that we are limited to using putchard
here, our amazing graphical output is limited, but we can whip together
something using the density plotter above:</p>
<div class="doc_code">
<pre>
-# compute and plot the mandlebrot set with the specified 2 dimentional range
+# compute and plot the mandlebrot set with the specified 2 dimensional range
# info.
def mandelhelp(xmin xmax xstep ymin ymax ystep)
for y = ymin, y < ymax, ystep in (
)
# mandel - This is a convenient helper function for ploting the mandelbrot set
-# from the specified position with the specified magnification.
+# from the specified position with the specified Magnification.
def mandel(realstart imagstart realmag imagmag)
mandelhelp(realstart, realstart+realmag*78, realmag,
imagstart, imagstart+imagmag*40, imagmag);
plot things that are!</p>
<p>With this, we conclude the "adding user-defined operators" chapter of the
-tutorial. We successfully extended our language with the ability to extend the
-language in the library, and showed how this can be used to build a simple but
-interesting end user application in Kaleidoscope. At this point, Kaleidoscope
+tutorial. We have successfully augmented our language, adding the ability to extend the
+language in the library, and we have shown how this can be used to build a simple but
+interesting end-user application in Kaleidoscope. At this point, Kaleidoscope
can build a variety of applications that are functional and can call functions
with side-effects, but it can't actually define and mutate a variable itself.
</p>
-<p>Strikingly, lack of this feature is an important limitation for some
+<p>Strikingly, variable mutation is an important feature of some
languages, and it is not at all obvious how to <a href="LangImpl7.html">add
support for mutable variables</a> without having to add an "SSA construction"
phase to your front-end. In the next chapter, we will describe how you can
-add this without building SSA in your front-end.</p>
+add variable mutation without building SSA in your front-end.</p>
</div>
<pre>
#include "llvm/DerivedTypes.h"
#include "llvm/ExecutionEngine/ExecutionEngine.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/Transforms/Scalar.h"
-#include "llvm/Support/LLVMBuilder.h"
+#include "llvm/Support/IRBuilder.h"
#include <cstdio>
#include <string>
#include <map>
if (LastChar == '#') {
// Comment until end of line.
do LastChar = getchar();
- while (LastChar != EOF && LastChar != '\n' & LastChar != '\r');
+ while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
if (LastChar != EOF)
return gettok();
static ExprAST *ParseExpression();
/// identifierexpr
-/// ::= identifer
-/// ::= identifer '(' expression* ')'
+/// ::= identifier
+/// ::= identifier '(' expression* ')'
static ExprAST *ParseIdentifierExpr() {
std::string IdName = IdentifierStr;
- getNextToken(); // eat identifer.
+ getNextToken(); // eat identifier.
if (CurTok != '(') // Simple variable ref.
return new VariableExprAST(IdName);
if (CurTok == ')') break;
if (CurTok != ',')
- return Error("Expected ')'");
+ return Error("Expected ')' or ',' in argument list");
getNextToken();
}
}
return new IfExprAST(Cond, Then, Else);
}
-/// forexpr ::= 'for' identifer '=' expr ',' expr (',' expr)? 'in' expression
+/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
static ExprAST *ParseForExpr() {
getNextToken(); // eat the for.
return Error("expected identifier after for");
std::string IdName = IdentifierStr;
- getNextToken(); // eat identifer.
+ getNextToken(); // eat identifier.
if (CurTok != '=')
return Error("expected '=' after for");
//===----------------------------------------------------------------------===//
static Module *TheModule;
-static LLVMFoldingBuilder Builder;
+static IRBuilder<> Builder(getGlobalContext());
static std::map<std::string, Value*> NamedValues;
static FunctionPassManager *TheFPM;
Value *ErrorV(const char *Str) { Error(Str); return 0; }
Value *NumberExprAST::Codegen() {
- return ConstantFP::get(Type::DoubleTy, APFloat(Val));
+ return getGlobalContext().getConstantFP(APFloat(Val));
}
Value *VariableExprAST::Codegen() {
case '-': return Builder.CreateSub(L, R, "subtmp");
case '*': return Builder.CreateMul(L, R, "multmp");
case '<':
- L = Builder.CreateFCmpULT(L, R, "multmp");
+ L = Builder.CreateFCmpULT(L, R, "cmptmp");
// Convert bool 0/1 to double 0.0 or 1.0
return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
default: break;
// Convert condition to a bool by comparing equal to 0.0.
CondV = Builder.CreateFCmpONE(CondV,
- ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
+ getGlobalContext().getConstantFP(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 = new BasicBlock("then", TheFunction);
- BasicBlock *ElseBB = new BasicBlock("else");
- BasicBlock *MergeBB = new BasicBlock("ifcont");
+ BasicBlock *ThenBB = BasicBlock::Create("then", TheFunction);
+ BasicBlock *ElseBB = BasicBlock::Create("else");
+ BasicBlock *MergeBB = BasicBlock::Create("ifcont");
Builder.CreateCondBr(CondV, ThenBB, ElseBB);
// block.
Function *TheFunction = Builder.GetInsertBlock()->getParent();
BasicBlock *PreheaderBB = Builder.GetInsertBlock();
- BasicBlock *LoopBB = new BasicBlock("loop", TheFunction);
+ BasicBlock *LoopBB = BasicBlock::Create("loop", TheFunction);
// Insert an explicit fall through from the current block to the LoopBB.
Builder.CreateBr(LoopBB);
if (StepVal == 0) return 0;
} else {
// If not specified, use 1.0.
- StepVal = ConstantFP::get(Type::DoubleTy, APFloat(1.0));
+ StepVal = getGlobalContext().getConstantFP(APFloat(1.0));
}
Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
// Convert condition to a bool by comparing equal to 0.0.
EndCond = Builder.CreateFCmpONE(EndCond,
- ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
+ getGlobalContext().getConstantFP(APFloat(0.0)),
"loopcond");
// Create the "after loop" block and insert it.
BasicBlock *LoopEndBB = Builder.GetInsertBlock();
- BasicBlock *AfterBB = new BasicBlock("afterloop", TheFunction);
+ BasicBlock *AfterBB = BasicBlock::Create("afterloop", TheFunction);
// Insert the conditional branch into the end of LoopEndBB.
Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
// for expr always returns 0.0.
- return Constant::getNullValue(Type::DoubleTy);
+ return TheFunction->getContext()->getNullValue(Type::DoubleTy);
}
Function *PrototypeAST::Codegen() {
// Make the function type: double(double,double) etc.
std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
- FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
+ FunctionType *FT = getGlobalContext().getFunctionType(Type::DoubleTy, Doubles, false);
- Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
+ Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
// If F conflicted, there was already something named 'Name'. If it has a
// body, don't allow redefinition or reextern.
BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
// Create a new basic block to start insertion into.
- BasicBlock *BB = new BasicBlock("entry", TheFunction);
+ BasicBlock *BB = BasicBlock::Create("entry", TheFunction);
Builder.SetInsertPoint(BB);
if (Value *RetVal = Body->Codegen()) {
getNextToken();
// Make the module, which holds all the code.
- TheModule = new Module("my cool jit");
+ TheModule = new Module("my cool jit", getGlobalContext());
// Create the JIT.
- TheExecutionEngine = ExecutionEngine::create(TheModule);
+ TheExecutionEngine = EngineBuilder(TheModule).create();
{
ExistingModuleProvider OurModuleProvider(TheModule);
MainLoop();
TheFPM = 0;
- } // Free module provider and pass manager.
-
-
- // 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;
}
</pre>
</div>
+<a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a>
</div>
<!-- *********************************************************************** -->
projects / oota-llvm.git / blobdiff