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