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