<title>Kaleidoscope: Adding JIT and Optimizer Support</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: Adding JIT and Optimizer Support</div>
+<h1>Kaleidoscope: Adding JIT and Optimizer Support</h1>
<ul>
<li><a href="index.html">Up to Tutorial Index</a></li>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="intro">Chapter 4 Introduction</a></div>
+<h2><a name="intro">Chapter 4 Introduction</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Welcome to Chapter 4 of the "<a href="index.html">Implementing a language
with LLVM</a>" tutorial. Chapters 1-3 described the implementation of a simple
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="trivialconstfold">Trivial Constant
-Folding</a></div>
+<h2><a name="trivialconstfold">Trivial Constant Folding</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
Our demonstration for Chapter 3 is elegant and easy to extend. Unfortunately,
Read function definition:
define double @test(double %x) {
entry:
- %addtmp = add double 3.000000e+00, %x
+ %addtmp = fadd double 3.000000e+00, %x
ret double %addtmp
}
</pre>
Read function definition:
define double @test(double %x) {
entry:
- %addtmp = add double 2.000000e+00, 1.000000e+00
- %addtmp1 = add double %addtmp, %x
+ %addtmp = fadd double 2.000000e+00, 1.000000e+00
+ %addtmp1 = fadd double %addtmp, %x
ret double %addtmp1
}
</pre>
ready> Read function definition:
define double @test(double %x) {
entry:
- %addtmp = add double 3.000000e+00, %x
- %addtmp1 = add double %x, 3.000000e+00
- %multmp = mul double %addtmp, %addtmp1
+ %addtmp = fadd double 3.000000e+00, %x
+ %addtmp1 = fadd double %x, 3.000000e+00
+ %multmp = fmul double %addtmp, %addtmp1
ret double %multmp
}
</pre>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="optimizerpasses">LLVM Optimization
- Passes</a></div>
+<h2><a name="optimizerpasses">LLVM Optimization Passes</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>LLVM provides many optimization passes, which do many different sorts of
things and have different tradeoffs. Unlike other systems, LLVM doesn't hold
<div class="doc_code">
<pre>
- 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();
+ 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();
</pre>
</div>
-<p>This code defines two objects, an <tt>ExistingModuleProvider</tt> and a
-<tt>FunctionPassManager</tt>. The former is basically a wrapper around our
-<tt>Module</tt> that the PassManager requires. It provides certain flexibility
-that we're not going to take advantage of here, so I won't dive into any details
-about it.</p>
-
-<p>The meat of the matter here, is the definition of "<tt>OurFPM</tt>". It
-requires a pointer to the <tt>Module</tt> (through the <tt>ModuleProvider</tt>)
-to construct itself. Once it is set up, we use a series of "add" calls to add
-a bunch of LLVM passes. The first pass is basically boilerplate, it adds a pass
-so that later optimizations know how the data structures in the program are
-layed out. The "<tt>TheExecutionEngine</tt>" variable is related to the JIT,
-which we will get to in the next section.</p>
+<p>This code defines a <tt>FunctionPassManager</tt>, "<tt>OurFPM</tt>". It
+requires a pointer to the <tt>Module</tt> to construct itself. Once it is set
+up, we use a series of "add" calls to add a bunch of LLVM passes. The first
+pass is basically boilerplate, it adds a pass so that later optimizations know
+how the data structures in the program are laid out. The
+"<tt>TheExecutionEngine</tt>" variable is related to the JIT, which we will get
+to in the next section.</p>
<p>In this case, we choose to add 4 optimization passes. The passes we chose
here are a pretty standard set of "cleanup" optimizations that are useful for
ready> Read function definition:
define double @test(double %x) {
entry:
- %addtmp = add double %x, 3.000000e+00
- %multmp = mul double %addtmp, %addtmp
+ %addtmp = fadd double %x, 3.000000e+00
+ %multmp = fmul double %addtmp, %addtmp
ret double %multmp
}
</pre>
<p>LLVM provides a wide variety of optimizations that can be used in certain
circumstances. Some <a href="../Passes.html">documentation about the various
passes</a> is available, but it isn't very complete. Another good source of
-ideas can come from looking at the passes that <tt>llvm-gcc</tt> or
-<tt>llvm-ld</tt> run to get started. The "<tt>opt</tt>" tool allows you to
-experiment with passes from the command line, so you can see if they do
-anything.</p>
+ideas can come from looking at the passes that <tt>Clang</tt> runs to get
+started. The "<tt>opt</tt>" tool allows you to experiment with passes from the
+command line, so you can see if they do anything.</p>
<p>Now that we have reasonable code coming out of our front-end, lets talk about
executing it!</p>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="jit">Adding a JIT Compiler</a></div>
+<h2><a name="jit">Adding a JIT Compiler</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>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),
...
int main() {
..
- <b>// Create the JIT.
- TheExecutionEngine = ExecutionEngine::create(TheModule);</b>
+ <b>// Create the JIT. This takes ownership of the module.
+ TheExecutionEngine = EngineBuilder(TheModule).create();</b>
..
}
</pre>
<div class="doc_code">
<pre>
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()) {
LF->dump(); // Dump the function for exposition purposes.
// 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());</b>
}
</pre>
<div class="doc_code">
<pre>
ready> <b>4+5;</b>
-define double @""() {
+Read top-level expression:
+define double @0() {
entry:
- ret double 9.000000e+00
+ ret double 9.000000e+00
}
<em>Evaluated to 9.000000</em>
<p>Well this looks like it is basically working. The dump of the function
shows the "no argument function that always returns double" that we synthesize
-for each top level expression that is typed in. This demonstrates very basic
+for each top-level expression that is typed in. This demonstrates very basic
functionality, but can we do more?</p>
<div class="doc_code">
Read function definition:
define double @testfunc(double %x, double %y) {
entry:
- %multmp = mul double %y, 2.000000e+00
- %addtmp = add double %multmp, %x
- ret double %addtmp
+ %multmp = fmul double %y, 2.000000e+00
+ %addtmp = fadd double %multmp, %x
+ ret double %addtmp
}
ready> <b>testfunc(4, 10);</b>
-define double @""() {
+Read top-level expression:
+define double @1() {
entry:
- %calltmp = call double @testfunc( double 4.000000e+00, double 1.000000e+01 )
- ret double %calltmp
+ %calltmp = call double @testfunc(double 4.000000e+00, double 1.000000e+01)
+ ret double %calltmp
}
<em>Evaluated to 24.000000</em>
</pre>
</div>
-<p>This illustrates that we can now call user code, but there is something a bit subtle
-going on here. Note that we only invoke the JIT on the anonymous functions
-that <em>call testfunc</em>, but we never invoked it on <em>testfunc
-</em>itself.</p>
-
-<p>What actually happened here is that the anonymous function was
-JIT'd when requested. When the Kaleidoscope app calls through the function
-pointer that is returned, the anonymous function starts executing. It ends up
-making the call to the "testfunc" function, and ends up in a stub that invokes
-the JIT, lazily, on testfunc. Once the JIT finishes lazily compiling testfunc,
-it returns and the code re-executes the call.</p>
-
-<p>In summary, the JIT will lazily JIT code, on the fly, as it is needed. The
-JIT provides a number of other more advanced interfaces for things like freeing
-allocated machine code, rejit'ing functions to update them, etc. However, even
-with this simple code, we get some surprisingly powerful capabilities - check
-this out (I removed the dump of the anonymous functions, you should get the idea
-by now :) :</p>
+<p>This illustrates that we can now call user code, but there is something a bit
+subtle going on here. Note that we only invoke the JIT on the anonymous
+functions that <em>call testfunc</em>, but we never invoked it
+on <em>testfunc</em> itself. What actually happened here is that the JIT
+scanned for all non-JIT'd functions transitively called from the anonymous
+function and compiled all of them before returning
+from <tt>getPointerToFunction()</tt>.</p>
+
+<p>The JIT provides a number of other more advanced interfaces for things like
+freeing allocated machine code, rejit'ing functions to update them, etc.
+However, even with this simple code, we get some surprisingly powerful
+capabilities - check this out (I removed the dump of the anonymous functions,
+you should get the idea by now :) :</p>
<div class="doc_code">
<pre>
declare double @cos(double)
ready> <b>sin(1.0);</b>
+Read top-level expression:
+define double @2() {
+entry:
+ ret double 0x3FEAED548F090CEE
+}
+
<em>Evaluated to 0.841471</em>
ready> <b>def foo(x) sin(x)*sin(x) + cos(x)*cos(x);</b>
Read function definition:
define double @foo(double %x) {
entry:
- %calltmp = call double @sin( double %x )
- %multmp = mul double %calltmp, %calltmp
- %calltmp2 = call double @cos( double %x )
- %multmp4 = mul double %calltmp2, %calltmp2
- %addtmp = add double %multmp, %multmp4
- ret double %addtmp
+ %calltmp = call double @sin(double %x)
+ %multmp = fmul double %calltmp, %calltmp
+ %calltmp2 = call double @cos(double %x)
+ %multmp4 = fmul double %calltmp2, %calltmp2
+ %addtmp = fadd double %multmp, %multmp4
+ ret double %addtmp
}
ready> <b>foo(4.0);</b>
+Read top-level expression:
+define double @3() {
+entry:
+ %calltmp = call double @foo(double 4.000000e+00)
+ ret double %calltmp
+}
+
<em>Evaluated to 1.000000</em>
</pre>
</div>
resolved. It allows you to establish explicit mappings between IR objects and
addresses (useful for LLVM global variables that you want to map to static
tables, for example), allows you to dynamically decide on the fly based on the
-function name, and even allows you to have the JIT abort itself if any lazy
-compilation is attempted.</p>
+function name, and even allows you to have the JIT compile functions lazily the
+first time they're called.</p>
<p>One interesting application of this is that we can now extend the language
by writing arbitrary C++ code to implement operations. For example, if we add:
</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>
<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>
tok_def = -2, tok_extern = -3,
// primary
- tok_identifier = -4, tok_number = -5,
+ tok_identifier = -4, tok_number = -5
};
static std::string IdentifierStr; // Filled in if tok_identifier
};
/// 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;
//===----------------------------------------------------------------------===//
/// 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();
//===----------------------------------------------------------------------===//
static Module *TheModule;
-static IRBuilder<> 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(APFloat(Val));
+ return ConstantFP::get(getGlobalContext(), APFloat(Val));
}
Value *VariableExprAST::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");
}
}
if (ArgsV.back() == 0) return 0;
}
- return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
+ return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
}
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);
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()) {
}
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()) {
+ fprintf(stderr, "Read top-level expression:");
+ LF->dump();
+
// JIT the function, returning a function pointer.
void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
// 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");
-
- // Create the JIT.
- TheExecutionEngine = ExecutionEngine::create(TheModule);
+ 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>
projects / oota-llvm.git / blobdiff