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