<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 =
- new ExistingModuleProvider(TheModule);
-
- FunctionPassManager OurFPM(OurModuleProvider);
+ 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.
</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. This takes ownership of the module and module provider.
- TheExecutionEngine = EngineBuilder(OurModuleProvider).create();</b>
+ <b>// Create the JIT. This takes ownership of the module.
+ TheExecutionEngine = EngineBuilder(TheModule).create();</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>
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 interpreter 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/Interpreter.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/Target/TargetSelect.h"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Support/IRBuilder.h"
+#include "llvm/Support/TargetSelect.h"
#include <cstdio>
#include <string>
#include <map>
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
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::getDoubleTy(getGlobalContext()));
+ std::vector<Type*> Doubles(Args.size(),
+ Type::getDoubleTy(getGlobalContext()));
FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
Doubles, false);
// 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);
// Make the module, which holds all the code.
TheModule = new Module("my cool jit", Context);
- ExistingModuleProvider *OurModuleProvider =
- new ExistingModuleProvider(TheModule);
-
- // Create the JIT. This takes ownership of the module and module provider.
- TheExecutionEngine = EngineBuilder(OurModuleProvider).create();
+ // 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(OurModuleProvider);
+ 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.
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>