Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / llvm / 43a699a112c7ac988e25111a3849fa1d73e3b51c / . / docs / tutorial / LangImpl4.html
blob: 8c5c31e76265c67d15f4a9d704c36e4e33c4cd1a [file] [log] [blame]
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3
4<html>
5<head>
6 <title>Kaleidoscope: Adding JIT and Optimizer Support</title>
7 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
8 <meta name="author" content="Chris Lattner">
Daniel Dunbarf2c696f2012-05-02 22:46:36 +0000[diff] [blame]9 <link rel="stylesheet" href="../_static/llvm.css" type="text/css">
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]10</head>
11
12<body>
13
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]14<h1>Kaleidoscope: Adding JIT and Optimizer Support</h1>
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]15
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]16<ul>
Chris Lattner0e555b12007-11-05 20:04:56 +0000[diff] [blame]17<li><a href="index.html">Up to Tutorial Index</a></li>
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]18<li>Chapter 4
19 <ol>
20 <li><a href="#intro">Chapter 4 Introduction</a></li>
21 <li><a href="#trivialconstfold">Trivial Constant Folding</a></li>
22 <li><a href="#optimizerpasses">LLVM Optimization Passes</a></li>
23 <li><a href="#jit">Adding a JIT Compiler</a></li>
24 <li><a href="#code">Full Code Listing</a></li>
25 </ol>
26</li>
Chris Lattner0e555b12007-11-05 20:04:56 +0000[diff] [blame]27<li><a href="LangImpl5.html">Chapter 5</a>: Extending the Language: Control
28Flow</li>
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]29</ul>
30
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]31<div class="doc_author">
32 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
33</div>
34
35<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]36<h2><a name="intro">Chapter 4 Introduction</a></h2>
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]37<!-- *********************************************************************** -->
38
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]39<div>
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]40
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]41<p>Welcome to Chapter 4 of the "<a href="index.html">Implementing a language
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]42with LLVM</a>" tutorial. Chapters 1-3 described the implementation of a simple
43language and added support for generating LLVM IR. This chapter describes
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]44two new techniques: adding optimizer support to your language, and adding JIT
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]45compiler support. These additions will demonstrate how to get nice, efficient code
46for the Kaleidoscope language.</p>
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]47
48</div>
49
50<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]51<h2><a name="trivialconstfold">Trivial Constant Folding</a></h2>
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]52<!-- *********************************************************************** -->
53
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]54<div>
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]55
56<p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]57Our demonstration for Chapter 3 is elegant and easy to extend. Unfortunately,
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]58it does not produce wonderful code. The IRBuilder, however, does give us
59obvious optimizations when compiling simple code:</p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]60
61<div class="doc_code">
62<pre>
63ready&gt; <b>def test(x) 1+2+x;</b>
64Read function definition:
65define double @test(double %x) {
66entry:
Dan Gohmana9445e12010-03-02 01:11:08 +0000[diff] [blame]67 %addtmp = fadd double 3.000000e+00, %x
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]68 ret double %addtmp
69}
70</pre>
71</div>
72
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]73<p>This code is not a literal transcription of the AST built by parsing the
74input. That would be:
75
76<div class="doc_code">
77<pre>
78ready&gt; <b>def test(x) 1+2+x;</b>
79Read function definition:
80define double @test(double %x) {
81entry:
Dan Gohmana9445e12010-03-02 01:11:08 +0000[diff] [blame]82 %addtmp = fadd double 2.000000e+00, 1.000000e+00
83 %addtmp1 = fadd double %addtmp, %x
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]84 ret double %addtmp1
85}
86</pre>
87</div>
88
Gabor Greif94244f32009-03-11 20:04:08 +0000[diff] [blame]89<p>Constant folding, as seen above, in particular, is a very common and very
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]90important optimization: so much so that many language implementors implement
91constant folding support in their AST representation.</p>
92
93<p>With LLVM, you don't need this support in the AST. Since all calls to build
94LLVM IR go through the LLVM IR builder, the builder itself checked to see if
95there was a constant folding opportunity when you call it. If so, it just does
96the constant fold and return the constant instead of creating an instruction.
97
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]98<p>Well, that was easy :). In practice, we recommend always using
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]99<tt>IRBuilder</tt> when generating code like this. It has no
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]100"syntactic overhead" for its use (you don't have to uglify your compiler with
101constant checks everywhere) and it can dramatically reduce the amount of
102LLVM IR that is generated in some cases (particular for languages with a macro
103preprocessor or that use a lot of constants).</p>
104
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]105<p>On the other hand, the <tt>IRBuilder</tt> is limited by the fact
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]106that it does all of its analysis inline with the code as it is built. If you
107take a slightly more complex example:</p>
108
109<div class="doc_code">
110<pre>
111ready&gt; <b>def test(x) (1+2+x)*(x+(1+2));</b>
112ready> Read function definition:
113define double @test(double %x) {
114entry:
Dan Gohmana9445e12010-03-02 01:11:08 +0000[diff] [blame]115 %addtmp = fadd double 3.000000e+00, %x
116 %addtmp1 = fadd double %x, 3.000000e+00
117 %multmp = fmul double %addtmp, %addtmp1
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]118 ret double %multmp
119}
120</pre>
121</div>
122
123<p>In this case, the LHS and RHS of the multiplication are the same value. We'd
124really like to see this generate "<tt>tmp = x+3; result = tmp*tmp;</tt>" instead
Chris Lattner1ace67c2008-04-15 16:59:22 +0000[diff] [blame]125of computing "<tt>x+3</tt>" twice.</p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]126
127<p>Unfortunately, no amount of local analysis will be able to detect and correct
128this. This requires two transformations: reassociation of expressions (to
129make the add's lexically identical) and Common Subexpression Elimination (CSE)
130to delete the redundant add instruction. Fortunately, LLVM provides a broad
131range of optimizations that you can use, in the form of "passes".</p>
132
133</div>
134
135<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]136<h2><a name="optimizerpasses">LLVM Optimization Passes</a></h2>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]137<!-- *********************************************************************** -->
138
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]139<div>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]140
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]141<p>LLVM provides many optimization passes, which do many different sorts of
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]142things and have different tradeoffs. Unlike other systems, LLVM doesn't hold
143to the mistaken notion that one set of optimizations is right for all languages
144and for all situations. LLVM allows a compiler implementor to make complete
145decisions about what optimizations to use, in which order, and in what
146situation.</p>
147
148<p>As a concrete example, LLVM supports both "whole module" passes, which look
149across as large of body of code as they can (often a whole file, but if run
150at link time, this can be a substantial portion of the whole program). It also
151supports and includes "per-function" passes which just operate on a single
152function at a time, without looking at other functions. For more information
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]153on passes and how they are run, see the <a href="../WritingAnLLVMPass.html">How
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]154to Write a Pass</a> document and the <a href="../Passes.html">List of LLVM
155Passes</a>.</p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]156
157<p>For Kaleidoscope, we are currently generating functions on the fly, one at
158a time, as the user types them in. We aren't shooting for the ultimate
159optimization experience in this setting, but we also want to catch the easy and
160quick stuff where possible. As such, we will choose to run a few per-function
161optimizations as the user types the function in. If we wanted to make a "static
162Kaleidoscope compiler", we would use exactly the code we have now, except that
163we would defer running the optimizer until the entire file has been parsed.</p>
164
165<p>In order to get per-function optimizations going, we need to set up a
166<a href="../WritingAnLLVMPass.html#passmanager">FunctionPassManager</a> to hold and
167organize the LLVM optimizations that we want to run. Once we have that, we can
168add a set of optimizations to run. The code looks like this:</p>
169
170<div class="doc_code">
171<pre>
Jeffrey Yasskinf0356fe2010-01-27 20:34:15 +0000[diff] [blame]172 FunctionPassManager OurFPM(TheModule);
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]173
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]174 // Set up the optimizer pipeline. Start with registering info about how the
175 // target lays out data structures.
176 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
Dan Gohmandfa1a792010-11-15 18:41:10 +0000[diff] [blame]177 // Provide basic AliasAnalysis support for GVN.
178 OurFPM.add(createBasicAliasAnalysisPass());
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]179 // Do simple "peephole" optimizations and bit-twiddling optzns.
180 OurFPM.add(createInstructionCombiningPass());
181 // Reassociate expressions.
182 OurFPM.add(createReassociatePass());
183 // Eliminate Common SubExpressions.
184 OurFPM.add(createGVNPass());
185 // Simplify the control flow graph (deleting unreachable blocks, etc).
186 OurFPM.add(createCFGSimplificationPass());
187
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]188 OurFPM.doInitialization();
189
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]190 // Set the global so the code gen can use this.
191 TheFPM = &amp;OurFPM;
192
193 // Run the main "interpreter loop" now.
194 MainLoop();
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]195</pre>
196</div>
197
Jeffrey Yasskinf0356fe2010-01-27 20:34:15 +0000[diff] [blame]198<p>This code defines a <tt>FunctionPassManager</tt>, "<tt>OurFPM</tt>". It
199requires a pointer to the <tt>Module</tt> to construct itself. Once it is set
200up, we use a series of "add" calls to add a bunch of LLVM passes. The first
201pass is basically boilerplate, it adds a pass so that later optimizations know
202how the data structures in the program are laid out. The
203"<tt>TheExecutionEngine</tt>" variable is related to the JIT, which we will get
204to in the next section.</p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]205
206<p>In this case, we choose to add 4 optimization passes. The passes we chose
207here are a pretty standard set of "cleanup" optimizations that are useful for
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]208a wide variety of code. I won't delve into what they do but, believe me,
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]209they are a good starting place :).</p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]210
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]211<p>Once the PassManager is set up, we need to make use of it. We do this by
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]212running it after our newly created function is constructed (in
213<tt>FunctionAST::Codegen</tt>), but before it is returned to the client:</p>
214
215<div class="doc_code">
216<pre>
217 if (Value *RetVal = Body->Codegen()) {
218 // Finish off the function.
219 Builder.CreateRet(RetVal);
220
221 // Validate the generated code, checking for consistency.
222 verifyFunction(*TheFunction);
223
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]224 <b>// Optimize the function.
225 TheFPM-&gt;run(*TheFunction);</b>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]226
227 return TheFunction;
228 }
229</pre>
230</div>
231
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]232<p>As you can see, this is pretty straightforward. The
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]233<tt>FunctionPassManager</tt> optimizes and updates the LLVM Function* in place,
234improving (hopefully) its body. With this in place, we can try our test above
235again:</p>
236
237<div class="doc_code">
238<pre>
239ready&gt; <b>def test(x) (1+2+x)*(x+(1+2));</b>
240ready> Read function definition:
241define double @test(double %x) {
242entry:
Dan Gohmana9445e12010-03-02 01:11:08 +0000[diff] [blame]243 %addtmp = fadd double %x, 3.000000e+00
244 %multmp = fmul double %addtmp, %addtmp
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]245 ret double %multmp
246}
247</pre>
248</div>
249
250<p>As expected, we now get our nicely optimized code, saving a floating point
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]251add instruction from every execution of this function.</p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]252
253<p>LLVM provides a wide variety of optimizations that can be used in certain
Chris Lattner72714232007-10-25 17:52:39 +0000[diff] [blame]254circumstances. Some <a href="../Passes.html">documentation about the various
255passes</a> is available, but it isn't very complete. Another good source of
Michael J. Spencer75338092012-04-19 19:27:54 +0000[diff] [blame]256ideas can come from looking at the passes that <tt>Clang</tt> runs to get
257started. The "<tt>opt</tt>" tool allows you to experiment with passes from the
258command line, so you can see if they do anything.</p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]259
260<p>Now that we have reasonable code coming out of our front-end, lets talk about
261executing it!</p>
262
263</div>
264
265<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]266<h2><a name="jit">Adding a JIT Compiler</a></h2>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]267<!-- *********************************************************************** -->
268
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]269<div>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]270
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]271<p>Code that is available in LLVM IR can have a wide variety of tools
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]272applied to it. For example, you can run optimizations on it (as we did above),
273you can dump it out in textual or binary forms, you can compile the code to an
274assembly file (.s) for some target, or you can JIT compile it. The nice thing
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]275about the LLVM IR representation is that it is the "common currency" between
276many different parts of the compiler.
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]277</p>
278
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]279<p>In this section, we'll add JIT compiler support to our interpreter. The
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]280basic idea that we want for Kaleidoscope is to have the user enter function
281bodies as they do now, but immediately evaluate the top-level expressions they
282type in. For example, if they type in "1 + 2;", we should evaluate and print
283out 3. If they define a function, they should be able to call it from the
284command line.</p>
285
286<p>In order to do this, we first declare and initialize the JIT. This is done
287by adding a global variable and a call in <tt>main</tt>:</p>
288
289<div class="doc_code">
290<pre>
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]291<b>static ExecutionEngine *TheExecutionEngine;</b>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]292...
293int main() {
294 ..
Jeffrey Yasskinf0356fe2010-01-27 20:34:15 +0000[diff] [blame]295 <b>// Create the JIT. This takes ownership of the module.
296 TheExecutionEngine = EngineBuilder(TheModule).create();</b>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]297 ..
298}
299</pre>
300</div>
301
302<p>This creates an abstract "Execution Engine" which can be either a JIT
303compiler or the LLVM interpreter. LLVM will automatically pick a JIT compiler
304for you if one is available for your platform, otherwise it will fall back to
305the interpreter.</p>
306
307<p>Once the <tt>ExecutionEngine</tt> is created, the JIT is ready to be used.
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]308There are a variety of APIs that are useful, but the simplest one is the
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]309"<tt>getPointerToFunction(F)</tt>" method. This method JIT compiles the
310specified LLVM Function and returns a function pointer to the generated machine
311code. In our case, this means that we can change the code that parses a
312top-level expression to look like this:</p>
313
314<div class="doc_code">
315<pre>
316static void HandleTopLevelExpression() {
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]317 // Evaluate a top-level expression into an anonymous function.
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]318 if (FunctionAST *F = ParseTopLevelExpr()) {
319 if (Function *LF = F-&gt;Codegen()) {
320 LF->dump(); // Dump the function for exposition purposes.
321
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]322 <b>// JIT the function, returning a function pointer.
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]323 void *FPtr = TheExecutionEngine-&gt;getPointerToFunction(LF);
324
325 // Cast it to the right type (takes no arguments, returns a double) so we
326 // can call it as a native function.
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]327 double (*FP)() = (double (*)())(intptr_t)FPtr;
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]328 fprintf(stderr, "Evaluated to %f\n", FP());</b>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]329 }
330</pre>
331</div>
332
333<p>Recall that we compile top-level expressions into a self-contained LLVM
334function that takes no arguments and returns the computed double. Because the
335LLVM JIT compiler matches the native platform ABI, this means that you can just
336cast the result pointer to a function pointer of that type and call it directly.
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]337This means, there is no difference between JIT compiled code and native machine
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]338code that is statically linked into your application.</p>
339
340<p>With just these two changes, lets see how Kaleidoscope works now!</p>
341
342<div class="doc_code">
343<pre>
344ready&gt; <b>4+5;</b>
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]345Read top-level expression:
346define double @0() {
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]347entry:
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]348 ret double 9.000000e+00
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]349}
350
351<em>Evaluated to 9.000000</em>
352</pre>
353</div>
354
355<p>Well this looks like it is basically working. The dump of the function
356shows the "no argument function that always returns double" that we synthesize
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]357for each top-level expression that is typed in. This demonstrates very basic
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]358functionality, but can we do more?</p>
359
360<div class="doc_code">
361<pre>
Chris Lattner2e89f3a2007-10-31 07:30:39 +0000[diff] [blame]362ready&gt; <b>def testfunc(x y) x + y*2; </b>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]363Read function definition:
364define double @testfunc(double %x, double %y) {
365entry:
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]366 %multmp = fmul double %y, 2.000000e+00
367 %addtmp = fadd double %multmp, %x
368 ret double %addtmp
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]369}
370
371ready&gt; <b>testfunc(4, 10);</b>
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]372Read top-level expression:
373define double @1() {
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]374entry:
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]375 %calltmp = call double @testfunc(double 4.000000e+00, double 1.000000e+01)
376 ret double %calltmp
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]377}
378
379<em>Evaluated to 24.000000</em>
380</pre>
381</div>
382
Jeffrey Yasskindc857242009-10-27 20:30:28 +0000[diff] [blame]383<p>This illustrates that we can now call user code, but there is something a bit
384subtle going on here. Note that we only invoke the JIT on the anonymous
385functions that <em>call testfunc</em>, but we never invoked it
386on <em>testfunc</em> itself. What actually happened here is that the JIT
387scanned for all non-JIT'd functions transitively called from the anonymous
388function and compiled all of them before returning
389from <tt>getPointerToFunction()</tt>.</p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]390
Jeffrey Yasskindc857242009-10-27 20:30:28 +0000[diff] [blame]391<p>The JIT provides a number of other more advanced interfaces for things like
392freeing allocated machine code, rejit'ing functions to update them, etc.
393However, even with this simple code, we get some surprisingly powerful
394capabilities - check this out (I removed the dump of the anonymous functions,
395you should get the idea by now :) :</p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]396
397<div class="doc_code">
398<pre>
399ready&gt; <b>extern sin(x);</b>
400Read extern:
401declare double @sin(double)
402
403ready&gt; <b>extern cos(x);</b>
404Read extern:
405declare double @cos(double)
406
407ready&gt; <b>sin(1.0);</b>
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]408Read top-level expression:
409define double @2() {
410entry:
411 ret double 0x3FEAED548F090CEE
412}
413
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]414<em>Evaluated to 0.841471</em>
Chris Lattner72714232007-10-25 17:52:39 +0000[diff] [blame]415
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]416ready&gt; <b>def foo(x) sin(x)*sin(x) + cos(x)*cos(x);</b>
417Read function definition:
418define double @foo(double %x) {
419entry:
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]420 %calltmp = call double @sin(double %x)
421 %multmp = fmul double %calltmp, %calltmp
422 %calltmp2 = call double @cos(double %x)
423 %multmp4 = fmul double %calltmp2, %calltmp2
424 %addtmp = fadd double %multmp, %multmp4
425 ret double %addtmp
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]426}
427
428ready&gt; <b>foo(4.0);</b>
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]429Read top-level expression:
430define double @3() {
431entry:
432 %calltmp = call double @foo(double 4.000000e+00)
433 ret double %calltmp
434}
435
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]436<em>Evaluated to 1.000000</em>
437</pre>
438</div>
439
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]440<p>Whoa, how does the JIT know about sin and cos? The answer is surprisingly
441simple: in this
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]442example, the JIT started execution of a function and got to a function call. It
443realized that the function was not yet JIT compiled and invoked the standard set
444of routines to resolve the function. In this case, there is no body defined
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]445for the function, so the JIT ended up calling "<tt>dlsym("sin")</tt>" on the
446Kaleidoscope process itself.
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]447Since "<tt>sin</tt>" is defined within the JIT's address space, it simply
448patches up calls in the module to call the libm version of <tt>sin</tt>
449directly.</p>
450
451<p>The LLVM JIT provides a number of interfaces (look in the
452<tt>ExecutionEngine.h</tt> file) for controlling how unknown functions get
453resolved. It allows you to establish explicit mappings between IR objects and
454addresses (useful for LLVM global variables that you want to map to static
455tables, for example), allows you to dynamically decide on the fly based on the
Jeffrey Yasskindc857242009-10-27 20:30:28 +0000[diff] [blame]456function name, and even allows you to have the JIT compile functions lazily the
457first time they're called.</p>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]458
Chris Lattner72714232007-10-25 17:52:39 +0000[diff] [blame]459<p>One interesting application of this is that we can now extend the language
460by writing arbitrary C++ code to implement operations. For example, if we add:
461</p>
462
463<div class="doc_code">
464<pre>
465/// putchard - putchar that takes a double and returns 0.
466extern "C"
467double putchard(double X) {
468 putchar((char)X);
469 return 0;
470}
471</pre>
472</div>
473
474<p>Now we can produce simple output to the console by using things like:
475"<tt>extern putchard(x); putchard(120);</tt>", which prints a lowercase 'x' on
Chris Lattnera54c2012007-11-07 05:28:43 +0000[diff] [blame]476the console (120 is the ASCII code for 'x'). Similar code could be used to
Chris Lattner72714232007-10-25 17:52:39 +0000[diff] [blame]477implement file I/O, console input, and many other capabilities in
478Kaleidoscope.</p>
479
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]480<p>This completes the JIT and optimizer chapter of the Kaleidoscope tutorial. At
481this point, we can compile a non-Turing-complete programming language, optimize
482and JIT compile it in a user-driven way. Next up we'll look into <a
483href="LangImpl5.html">extending the language with control flow constructs</a>,
484tackling some interesting LLVM IR issues along the way.</p>
485
486</div>
487
488<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]489<h2><a name="code">Full Code Listing</a></h2>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]490<!-- *********************************************************************** -->
491
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]492<div>
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]493
494<p>
495Here is the complete code listing for our running example, enhanced with the
496LLVM JIT and optimizer. To build this example, use:
497</p>
498
499<div class="doc_code">
500<pre>
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]501# Compile
502clang++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
503# Run
504./toy
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]505</pre>
506</div>
507
Chris Lattner7c770892009-02-09 00:04:40 +0000[diff] [blame]508<p>
509If you are compiling this on Linux, make sure to add the "-rdynamic" option
510as well. This makes sure that the external functions are resolved properly
511at runtime.</p>
512
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]513<p>Here is the code:</p>
514
515<div class="doc_code">
516<pre>
517#include "llvm/DerivedTypes.h"
518#include "llvm/ExecutionEngine/ExecutionEngine.h"
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]519#include "llvm/ExecutionEngine/JIT.h"
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]520#include "llvm/LLVMContext.h"
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]521#include "llvm/Module.h"
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]522#include "llvm/PassManager.h"
523#include "llvm/Analysis/Verifier.h"
Dan Gohmanab7fa082010-11-16 17:28:22 +0000[diff] [blame]524#include "llvm/Analysis/Passes.h"
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]525#include "llvm/Target/TargetData.h"
526#include "llvm/Transforms/Scalar.h"
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]527#include "llvm/Support/IRBuilder.h"
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]528#include "llvm/Support/TargetSelect.h"
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]529#include &lt;cstdio&gt;
530#include &lt;string&gt;
531#include &lt;map&gt;
532#include &lt;vector&gt;
533using namespace llvm;
534
535//===----------------------------------------------------------------------===//
536// Lexer
537//===----------------------------------------------------------------------===//
538
539// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
540// of these for known things.
541enum Token {
542 tok_eof = -1,
543
544 // commands
545 tok_def = -2, tok_extern = -3,
546
547 // primary
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]548 tok_identifier = -4, tok_number = -5
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]549};
550
551static std::string IdentifierStr; // Filled in if tok_identifier
552static double NumVal; // Filled in if tok_number
553
554/// gettok - Return the next token from standard input.
555static int gettok() {
556 static int LastChar = ' ';
557
558 // Skip any whitespace.
559 while (isspace(LastChar))
560 LastChar = getchar();
561
562 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
563 IdentifierStr = LastChar;
564 while (isalnum((LastChar = getchar())))
565 IdentifierStr += LastChar;
566
567 if (IdentifierStr == "def") return tok_def;
568 if (IdentifierStr == "extern") return tok_extern;
569 return tok_identifier;
570 }
571
572 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
573 std::string NumStr;
574 do {
575 NumStr += LastChar;
576 LastChar = getchar();
577 } while (isdigit(LastChar) || LastChar == '.');
578
579 NumVal = strtod(NumStr.c_str(), 0);
580 return tok_number;
581 }
582
583 if (LastChar == '#') {
584 // Comment until end of line.
585 do LastChar = getchar();
Chris Lattnerc80c23f2007-12-02 22:46:01 +0000[diff] [blame]586 while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]587
588 if (LastChar != EOF)
589 return gettok();
590 }
591
592 // Check for end of file. Don't eat the EOF.
593 if (LastChar == EOF)
594 return tok_eof;
595
596 // Otherwise, just return the character as its ascii value.
597 int ThisChar = LastChar;
598 LastChar = getchar();
599 return ThisChar;
600}
601
602//===----------------------------------------------------------------------===//
603// Abstract Syntax Tree (aka Parse Tree)
604//===----------------------------------------------------------------------===//
605
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]606/// ExprAST - Base class for all expression nodes.
607class ExprAST {
608public:
609 virtual ~ExprAST() {}
610 virtual Value *Codegen() = 0;
611};
612
613/// NumberExprAST - Expression class for numeric literals like "1.0".
614class NumberExprAST : public ExprAST {
615 double Val;
616public:
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]617 NumberExprAST(double val) : Val(val) {}
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]618 virtual Value *Codegen();
619};
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]620
621/// VariableExprAST - Expression class for referencing a variable, like "a".
622class VariableExprAST : public ExprAST {
623 std::string Name;
624public:
625 VariableExprAST(const std::string &amp;name) : Name(name) {}
626 virtual Value *Codegen();
627};
628
629/// BinaryExprAST - Expression class for a binary operator.
630class BinaryExprAST : public ExprAST {
631 char Op;
632 ExprAST *LHS, *RHS;
633public:
634 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
635 : Op(op), LHS(lhs), RHS(rhs) {}
636 virtual Value *Codegen();
637};
638
639/// CallExprAST - Expression class for function calls.
640class CallExprAST : public ExprAST {
641 std::string Callee;
642 std::vector&lt;ExprAST*&gt; Args;
643public:
644 CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
645 : Callee(callee), Args(args) {}
646 virtual Value *Codegen();
647};
648
649/// PrototypeAST - This class represents the "prototype" for a function,
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]650/// which captures its name, and its argument names (thus implicitly the number
651/// of arguments the function takes).
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]652class PrototypeAST {
653 std::string Name;
654 std::vector&lt;std::string&gt; Args;
655public:
656 PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args)
657 : Name(name), Args(args) {}
658
659 Function *Codegen();
660};
661
662/// FunctionAST - This class represents a function definition itself.
663class FunctionAST {
664 PrototypeAST *Proto;
665 ExprAST *Body;
666public:
667 FunctionAST(PrototypeAST *proto, ExprAST *body)
668 : Proto(proto), Body(body) {}
669
670 Function *Codegen();
671};
672
673//===----------------------------------------------------------------------===//
674// Parser
675//===----------------------------------------------------------------------===//
676
677/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]678/// token the parser is looking at. getNextToken reads another token from the
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]679/// lexer and updates CurTok with its results.
680static int CurTok;
681static int getNextToken() {
682 return CurTok = gettok();
683}
684
685/// BinopPrecedence - This holds the precedence for each binary operator that is
686/// defined.
687static std::map&lt;char, int&gt; BinopPrecedence;
688
689/// GetTokPrecedence - Get the precedence of the pending binary operator token.
690static int GetTokPrecedence() {
691 if (!isascii(CurTok))
692 return -1;
693
694 // Make sure it's a declared binop.
695 int TokPrec = BinopPrecedence[CurTok];
696 if (TokPrec &lt;= 0) return -1;
697 return TokPrec;
698}
699
700/// Error* - These are little helper functions for error handling.
701ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
702PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
703FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
704
705static ExprAST *ParseExpression();
706
707/// identifierexpr
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]708/// ::= identifier
709/// ::= identifier '(' expression* ')'
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]710static ExprAST *ParseIdentifierExpr() {
711 std::string IdName = IdentifierStr;
712
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]713 getNextToken(); // eat identifier.
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]714
715 if (CurTok != '(') // Simple variable ref.
716 return new VariableExprAST(IdName);
717
718 // Call.
719 getNextToken(); // eat (
720 std::vector&lt;ExprAST*&gt; Args;
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]721 if (CurTok != ')') {
722 while (1) {
723 ExprAST *Arg = ParseExpression();
724 if (!Arg) return 0;
725 Args.push_back(Arg);
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]726
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]727 if (CurTok == ')') break;
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]728
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]729 if (CurTok != ',')
Chris Lattner6c4be9c2008-04-14 16:44:41 +0000[diff] [blame]730 return Error("Expected ')' or ',' in argument list");
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]731 getNextToken();
732 }
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]733 }
734
735 // Eat the ')'.
736 getNextToken();
737
738 return new CallExprAST(IdName, Args);
739}
740
741/// numberexpr ::= number
742static ExprAST *ParseNumberExpr() {
743 ExprAST *Result = new NumberExprAST(NumVal);
744 getNextToken(); // consume the number
745 return Result;
746}
747
748/// parenexpr ::= '(' expression ')'
749static ExprAST *ParseParenExpr() {
750 getNextToken(); // eat (.
751 ExprAST *V = ParseExpression();
752 if (!V) return 0;
753
754 if (CurTok != ')')
755 return Error("expected ')'");
756 getNextToken(); // eat ).
757 return V;
758}
759
760/// primary
761/// ::= identifierexpr
762/// ::= numberexpr
763/// ::= parenexpr
764static ExprAST *ParsePrimary() {
765 switch (CurTok) {
766 default: return Error("unknown token when expecting an expression");
767 case tok_identifier: return ParseIdentifierExpr();
768 case tok_number: return ParseNumberExpr();
769 case '(': return ParseParenExpr();
770 }
771}
772
773/// binoprhs
774/// ::= ('+' primary)*
775static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
776 // If this is a binop, find its precedence.
777 while (1) {
778 int TokPrec = GetTokPrecedence();
779
780 // If this is a binop that binds at least as tightly as the current binop,
781 // consume it, otherwise we are done.
782 if (TokPrec &lt; ExprPrec)
783 return LHS;
784
785 // Okay, we know this is a binop.
786 int BinOp = CurTok;
787 getNextToken(); // eat binop
788
789 // Parse the primary expression after the binary operator.
790 ExprAST *RHS = ParsePrimary();
791 if (!RHS) return 0;
792
793 // If BinOp binds less tightly with RHS than the operator after RHS, let
794 // the pending operator take RHS as its LHS.
795 int NextPrec = GetTokPrecedence();
796 if (TokPrec &lt; NextPrec) {
797 RHS = ParseBinOpRHS(TokPrec+1, RHS);
798 if (RHS == 0) return 0;
799 }
800
801 // Merge LHS/RHS.
802 LHS = new BinaryExprAST(BinOp, LHS, RHS);
803 }
804}
805
806/// expression
807/// ::= primary binoprhs
808///
809static ExprAST *ParseExpression() {
810 ExprAST *LHS = ParsePrimary();
811 if (!LHS) return 0;
812
813 return ParseBinOpRHS(0, LHS);
814}
815
816/// prototype
817/// ::= id '(' id* ')'
818static PrototypeAST *ParsePrototype() {
819 if (CurTok != tok_identifier)
820 return ErrorP("Expected function name in prototype");
821
822 std::string FnName = IdentifierStr;
823 getNextToken();
824
825 if (CurTok != '(')
826 return ErrorP("Expected '(' in prototype");
827
828 std::vector&lt;std::string&gt; ArgNames;
829 while (getNextToken() == tok_identifier)
830 ArgNames.push_back(IdentifierStr);
831 if (CurTok != ')')
832 return ErrorP("Expected ')' in prototype");
833
834 // success.
835 getNextToken(); // eat ')'.
836
837 return new PrototypeAST(FnName, ArgNames);
838}
839
840/// definition ::= 'def' prototype expression
841static FunctionAST *ParseDefinition() {
842 getNextToken(); // eat def.
843 PrototypeAST *Proto = ParsePrototype();
844 if (Proto == 0) return 0;
845
846 if (ExprAST *E = ParseExpression())
847 return new FunctionAST(Proto, E);
848 return 0;
849}
850
851/// toplevelexpr ::= expression
852static FunctionAST *ParseTopLevelExpr() {
853 if (ExprAST *E = ParseExpression()) {
854 // Make an anonymous proto.
855 PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
856 return new FunctionAST(Proto, E);
857 }
858 return 0;
859}
860
861/// external ::= 'extern' prototype
862static PrototypeAST *ParseExtern() {
863 getNextToken(); // eat extern.
864 return ParsePrototype();
865}
866
867//===----------------------------------------------------------------------===//
868// Code Generation
869//===----------------------------------------------------------------------===//
870
871static Module *TheModule;
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]872static IRBuilder&lt;&gt; Builder(getGlobalContext());
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]873static std::map&lt;std::string, Value*&gt; NamedValues;
874static FunctionPassManager *TheFPM;
875
876Value *ErrorV(const char *Str) { Error(Str); return 0; }
877
878Value *NumberExprAST::Codegen() {
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]879 return ConstantFP::get(getGlobalContext(), APFloat(Val));
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]880}
881
882Value *VariableExprAST::Codegen() {
883 // Look this variable up in the function.
884 Value *V = NamedValues[Name];
885 return V ? V : ErrorV("Unknown variable name");
886}
887
888Value *BinaryExprAST::Codegen() {
889 Value *L = LHS-&gt;Codegen();
890 Value *R = RHS-&gt;Codegen();
891 if (L == 0 || R == 0) return 0;
892
893 switch (Op) {
Eric Christopher2214b812010-06-14 06:09:39 +0000[diff] [blame]894 case '+': return Builder.CreateFAdd(L, R, "addtmp");
895 case '-': return Builder.CreateFSub(L, R, "subtmp");
896 case '*': return Builder.CreateFMul(L, R, "multmp");
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]897 case '&lt;':
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]898 L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]899 // Convert bool 0/1 to double 0.0 or 1.0
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]900 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
901 "booltmp");
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]902 default: return ErrorV("invalid binary operator");
903 }
904}
905
906Value *CallExprAST::Codegen() {
907 // Look up the name in the global module table.
908 Function *CalleeF = TheModule-&gt;getFunction(Callee);
909 if (CalleeF == 0)
910 return ErrorV("Unknown function referenced");
911
912 // If argument mismatch error.
913 if (CalleeF-&gt;arg_size() != Args.size())
914 return ErrorV("Incorrect # arguments passed");
915
916 std::vector&lt;Value*&gt; ArgsV;
917 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
918 ArgsV.push_back(Args[i]-&gt;Codegen());
919 if (ArgsV.back() == 0) return 0;
920 }
921
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]922 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]923}
924
925Function *PrototypeAST::Codegen() {
926 // Make the function type: double(double,double) etc.
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]927 std::vector&lt;Type*&gt; Doubles(Args.size(),
928 Type::getDoubleTy(getGlobalContext()));
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]929 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
930 Doubles, false);
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]931
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]932 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]933
934 // If F conflicted, there was already something named 'Name'. If it has a
935 // body, don't allow redefinition or reextern.
936 if (F-&gt;getName() != Name) {
937 // Delete the one we just made and get the existing one.
938 F-&gt;eraseFromParent();
939 F = TheModule-&gt;getFunction(Name);
940
941 // If F already has a body, reject this.
942 if (!F-&gt;empty()) {
943 ErrorF("redefinition of function");
944 return 0;
945 }
946
947 // If F took a different number of args, reject.
948 if (F-&gt;arg_size() != Args.size()) {
949 ErrorF("redefinition of function with different # args");
950 return 0;
951 }
952 }
953
954 // Set names for all arguments.
955 unsigned Idx = 0;
956 for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
957 ++AI, ++Idx) {
958 AI-&gt;setName(Args[Idx]);
959
960 // Add arguments to variable symbol table.
961 NamedValues[Args[Idx]] = AI;
962 }
963
964 return F;
965}
966
967Function *FunctionAST::Codegen() {
968 NamedValues.clear();
969
970 Function *TheFunction = Proto-&gt;Codegen();
971 if (TheFunction == 0)
972 return 0;
973
974 // Create a new basic block to start insertion into.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]975 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]976 Builder.SetInsertPoint(BB);
977
978 if (Value *RetVal = Body-&gt;Codegen()) {
979 // Finish off the function.
980 Builder.CreateRet(RetVal);
981
982 // Validate the generated code, checking for consistency.
983 verifyFunction(*TheFunction);
984
985 // Optimize the function.
986 TheFPM-&gt;run(*TheFunction);
987
988 return TheFunction;
989 }
990
991 // Error reading body, remove function.
992 TheFunction-&gt;eraseFromParent();
993 return 0;
994}
995
996//===----------------------------------------------------------------------===//
997// Top-Level parsing and JIT Driver
998//===----------------------------------------------------------------------===//
999
1000static ExecutionEngine *TheExecutionEngine;
1001
1002static void HandleDefinition() {
1003 if (FunctionAST *F = ParseDefinition()) {
1004 if (Function *LF = F-&gt;Codegen()) {
1005 fprintf(stderr, "Read function definition:");
1006 LF-&gt;dump();
1007 }
1008 } else {
1009 // Skip token for error recovery.
1010 getNextToken();
1011 }
1012}
1013
1014static void HandleExtern() {
1015 if (PrototypeAST *P = ParseExtern()) {
1016 if (Function *F = P-&gt;Codegen()) {
1017 fprintf(stderr, "Read extern: ");
1018 F-&gt;dump();
1019 }
1020 } else {
1021 // Skip token for error recovery.
1022 getNextToken();
1023 }
1024}
1025
1026static void HandleTopLevelExpression() {
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1027 // Evaluate a top-level expression into an anonymous function.
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]1028 if (FunctionAST *F = ParseTopLevelExpr()) {
1029 if (Function *LF = F-&gt;Codegen()) {
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]1030 fprintf(stderr, "Read top-level expression:");
1031 LF->dump();
1032
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]1033 // JIT the function, returning a function pointer.
1034 void *FPtr = TheExecutionEngine-&gt;getPointerToFunction(LF);
1035
1036 // Cast it to the right type (takes no arguments, returns a double) so we
1037 // can call it as a native function.
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1038 double (*FP)() = (double (*)())(intptr_t)FPtr;
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]1039 fprintf(stderr, "Evaluated to %f\n", FP());
1040 }
1041 } else {
1042 // Skip token for error recovery.
1043 getNextToken();
1044 }
1045}
1046
1047/// top ::= definition | external | expression | ';'
1048static void MainLoop() {
1049 while (1) {
1050 fprintf(stderr, "ready&gt; ");
1051 switch (CurTok) {
1052 case tok_eof: return;
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1053 case ';': getNextToken(); break; // ignore top-level semicolons.
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]1054 case tok_def: HandleDefinition(); break;
1055 case tok_extern: HandleExtern(); break;
1056 default: HandleTopLevelExpression(); break;
1057 }
1058 }
1059}
1060
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]1061//===----------------------------------------------------------------------===//
1062// "Library" functions that can be "extern'd" from user code.
1063//===----------------------------------------------------------------------===//
1064
1065/// putchard - putchar that takes a double and returns 0.
1066extern "C"
1067double putchard(double X) {
1068 putchar((char)X);
1069 return 0;
1070}
1071
1072//===----------------------------------------------------------------------===//
1073// Main driver code.
1074//===----------------------------------------------------------------------===//
1075
1076int main() {
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1077 InitializeNativeTarget();
1078 LLVMContext &amp;Context = getGlobalContext();
1079
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]1080 // Install standard binary operators.
1081 // 1 is lowest precedence.
1082 BinopPrecedence['&lt;'] = 10;
1083 BinopPrecedence['+'] = 20;
1084 BinopPrecedence['-'] = 20;
1085 BinopPrecedence['*'] = 40; // highest.
1086
1087 // Prime the first token.
1088 fprintf(stderr, "ready&gt; ");
1089 getNextToken();
1090
1091 // Make the module, which holds all the code.
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1092 TheModule = new Module("my cool jit", Context);
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]1093
Jeffrey Yasskinf0356fe2010-01-27 20:34:15 +0000[diff] [blame]1094 // Create the JIT. This takes ownership of the module.
Jeffrey Yasskin42fc5582010-02-11 19:15:20 +0000[diff] [blame]1095 std::string ErrStr;
Bill Wendling545a2be2011-10-16 08:06:54 +0000[diff] [blame]1096 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&amp;ErrStr).create();
Jeffrey Yasskin42fc5582010-02-11 19:15:20 +0000[diff] [blame]1097 if (!TheExecutionEngine) {
1098 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1099 exit(1);
1100 }
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]1101
Jeffrey Yasskinf0356fe2010-01-27 20:34:15 +0000[diff] [blame]1102 FunctionPassManager OurFPM(TheModule);
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]1103
1104 // Set up the optimizer pipeline. Start with registering info about how the
1105 // target lays out data structures.
1106 OurFPM.add(new TargetData(*TheExecutionEngine-&gt;getTargetData()));
Dan Gohmandfa1a792010-11-15 18:41:10 +0000[diff] [blame]1107 // Provide basic AliasAnalysis support for GVN.
1108 OurFPM.add(createBasicAliasAnalysisPass());
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]1109 // Do simple "peephole" optimizations and bit-twiddling optzns.
1110 OurFPM.add(createInstructionCombiningPass());
1111 // Reassociate expressions.
1112 OurFPM.add(createReassociatePass());
1113 // Eliminate Common SubExpressions.
1114 OurFPM.add(createGVNPass());
1115 // Simplify the control flow graph (deleting unreachable blocks, etc).
1116 OurFPM.add(createCFGSimplificationPass());
1117
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1118 OurFPM.doInitialization();
1119
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]1120 // Set the global so the code gen can use this.
1121 TheFPM = &amp;OurFPM;
1122
1123 // Run the main "interpreter loop" now.
1124 MainLoop();
1125
1126 TheFPM = 0;
1127
1128 // Print out all of the generated code.
1129 TheModule-&gt;dump();
1130
Chris Lattner118749e2007-10-25 06:23:36 +0000[diff] [blame]1131 return 0;
1132}
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]1133</pre>
1134</div>
1135
Chris Lattner729eb142008-02-10 19:11:04 +0000[diff] [blame]1136<a href="LangImpl5.html">Next: Extending the language: control flow</a>
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]1137</div>
1138
1139<!-- *********************************************************************** -->
1140<hr>
1141<address>
1142 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1143 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1144 <a href="http://validator.w3.org/check/referer"><img
Chris Lattner8eef4b22007-10-23 06:30:50 +0000[diff] [blame]1145 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]1146
1147 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
NAKAMURA Takumib9a33632011-04-09 02:13:37 +0000[diff] [blame]1148 <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
Dan Gohman523e3922010-02-03 17:27:31 +0000[diff] [blame]1149 Last modified: $Date$
Chris Lattnerc0b42e92007-10-23 06:27:55 +0000[diff] [blame]1150</address>
1151</body>
1152</html>