<title>Kaleidoscope: Extending the Language: User-defined Operators</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="author" content="Chris Lattner">
- <link rel="stylesheet" href="../llvm.css" type="text/css">
+ <link rel="stylesheet" href="../_static/llvm.css" type="text/css">
</head>
<body>
-<div class="doc_title">Kaleidoscope: Extending the Language: User-defined Operators</div>
+<h1>Kaleidoscope: Extending the Language: User-defined Operators</h1>
<ul>
<li><a href="index.html">Up to Tutorial Index</a></li>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="intro">Chapter 6 Introduction</a></div>
+<h2><a name="intro">Chapter 6 Introduction</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<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
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="idea">User-defined Operators: the Idea</a></div>
+<h2><a name="idea">User-defined Operators: the Idea</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
The "operator overloading" that we will add to Kaleidoscope is more general than
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="binary">User-defined Binary Operators</a></div>
+<h2><a name="binary">User-defined Binary Operators</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Adding support for user-defined binary operators is pretty simple with our
current framework. We'll first add support for the unary/binary keywords:</p>
static PrototypeAST *ParsePrototype() {
std::string FnName;
- <b>int Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
+ <b>unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
unsigned BinaryPrecedence = 30;</b>
switch (CurTok) {
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");
<b>default: break;</b>
}
Function *F = TheModule->getFunction(std::string("binary")+Op);
assert(F && "binary operator not found!");
- Value *Ops[] = { L, R };
- return Builder.CreateCall(F, Ops, Ops+2, "binop");</b>
+ Value *Ops[2] = { L, R };
+ return Builder.CreateCall(F, Ops, "binop");</b>
}
</pre>
functions (because the "prototype" boils down to a function with the right
name) everything falls into place.</p>
-<p>The final piece of code we are missing, is a bit of top level magic:</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 = BasicBlock::Create("entry", TheFunction);
+ BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
Builder.SetInsertPoint(BB);
if (Value *RetVal = Body->Codegen()) {
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="unary">User-defined Unary Operators</a></div>
+<h2><a name="unary">User-defined Unary Operators</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>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
static PrototypeAST *ParsePrototype() {
std::string FnName;
- int Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
+ unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
unsigned BinaryPrecedence = 30;
switch (CurTok) {
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="example">Kicking the Tires</a></div>
+<h2><a name="example">Kicking the Tires</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>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
<div class="doc_code">
<pre>
ready> <b>extern printd(x);</b>
-Read extern: declare double @printd(double)
+Read extern:
+declare double @printd(double)
+
ready> <b>def binary : 1 (x y) 0; # Low-precedence operator that ignores operands.</b>
..
ready> <b>printd(123) : printd(456) : printd(789);</b>
def unary-(v)
0-v;
-# Define > with the same precedence as >.
+# Define > with the same precedence as <.
def binary> 10 (LHS RHS)
RHS < LHS;
def binary = 9 (LHS RHS)
!(LHS < RHS | LHS > RHS);
+# Define ':' for sequencing: as a low-precedence operator that ignores operands
+# and just returns the RHS.
+def binary : 1 (x y) y;
</pre>
</div>
else
putchard(42); # '*'</b>
...
-ready> <b>printdensity(1): printdensity(2): printdensity(3) :
- printdensity(4): printdensity(5): printdensity(9): putchard(10);</b>
-*++..
+ready> <b>printdensity(1): printdensity(2): printdensity(3):
+ printdensity(4): printdensity(5): printdensity(9):
+ putchard(10);</b>
+**++.
Evaluated to 0.000000
</pre>
</div>
<div class="doc_code">
<pre>
-# determine whether the specific location diverges.
+# Determine whether the specific location diverges.
# Solve for z = z^2 + c in the complex plane.
def mandleconverger(real imag iters creal cimag)
if iters > 255 | (real*real + imag*imag > 4) then
2*real*imag + cimag,
iters+1, creal, cimag);
-# return the number of iterations required for the iteration to escape
+# Return the number of iterations required for the iteration to escape
def mandleconverge(real imag)
mandleconverger(real, imag, 0, real, imag);
</pre>
</div>
-<p>This "z = z<sup>2</sup> + c" function is a beautiful little creature that is the basis
-for computation of the <a
-href="http://en.wikipedia.org/wiki/Mandelbrot_set">Mandelbrot Set</a>. Our
-<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
-here, our amazing graphical output is limited, but we can whip together
+<p>This "<code>z = z<sup>2</sup> + c</code>" function is a beautiful little
+creature that is the basis for computation of
+the <a href="http://en.wikipedia.org/wiki/Mandelbrot_set">Mandelbrot Set</a>.
+Our <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 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 dimensional 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 (
</div>
-
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="code">Full Code Listing</a></div>
+<h2><a name="code">Full Code Listing</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
Here is the complete code listing for our running example, enhanced with the
<div class="doc_code">
<pre>
- # 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
</pre>
</div>
+<p>On some platforms, you will need to specify -rdynamic or -Wl,--export-dynamic
+when linking. This ensures that symbols defined in the main executable are
+exported to the dynamic linker and so are available for symbol resolution at
+run time. This is not needed if you compile your support code into a shared
+library, although doing that will cause problems on Windows.</p>
+
<p>Here is the code:</p>
<div class="doc_code">
<pre>
#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/Analysis/Passes.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Support/IRBuilder.h"
+#include "llvm/Support/TargetSelect.h"
#include <cstdio>
#include <string>
#include <map>
};
/// 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), as well as if it is an operator.
class PrototypeAST {
std::string Name;
std::vector<std::string> Args;
//===----------------------------------------------------------------------===//
/// 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() {
ExprAST *Arg = ParseExpression();
if (!Arg) return 0;
Args.push_back(Arg);
-
+
if (CurTok == ')') break;
-
+
if (CurTok != ',')
return Error("Expected ')' or ',' in argument list");
getNextToken();
return new ForExprAST(IdName, Start, End, Step, Body);
}
-
/// primary
/// ::= identifierexpr
/// ::= numberexpr
static PrototypeAST *ParsePrototype() {
std::string FnName;
- int Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
+ unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
unsigned BinaryPrecedence = 30;
switch (CurTok) {
return Builder.CreateCall(F, OperandV, "unop");
}
-
Value *BinaryExprAST::Codegen() {
Value *L = LHS->Codegen();
Value *R = RHS->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: break;
}
Function *F = TheModule->getFunction(std::string("binary")+Op);
assert(F && "binary operator not found!");
- Value *Ops[] = { L, R };
- return Builder.CreateCall(F, Ops, Ops+2, "binop");
+ Value *Ops[2] = { L, R };
+ return Builder.CreateCall(F, Ops, "binop");
}
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() {
// 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);
// 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);
// 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);
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
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();
// 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);
// for expr always returns 0.0.
- return TheFunction->getContext().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 = FunctionType::get(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);
BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
// 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()) {
}
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.
// 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 {
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;
}
}
-
-
//===----------------------------------------------------------------------===//
// "Library" functions that can be "extern'd" from user code.
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
int main() {
+ InitializeNativeTarget();
+ LLVMContext &Context = getGlobalContext();
+
// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['<'] = 10;
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);
+ }
+
+ FunctionPassManager OurFPM(TheModule);
+
+ // Set up the optimizer pipeline. Start with registering info about how the
+ // target lays out data structures.
+ OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
+ // 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();
- {
- 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;
-
- // Print out all of the generated code.
- TheModule->dump();
- } // Free module provider (and thus the module) and pass manager.
-
return 0;
}
</pre>
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
- <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
- Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
+ <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
+ Last modified: $Date$
</address>
</body>
</html>