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