1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
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 <meta name="author" content="Erick Tryzelaar">
10 <link rel="stylesheet" href="../llvm.css" type="text/css">
15 <div class="doc_title">Kaleidoscope: Adding JIT and Optimizer Support</div>
18 <li><a href="index.html">Up to Tutorial Index</a></li>
21 <li><a href="#intro">Chapter 4 Introduction</a></li>
22 <li><a href="#trivialconstfold">Trivial Constant Folding</a></li>
23 <li><a href="#optimizerpasses">LLVM Optimization Passes</a></li>
24 <li><a href="#jit">Adding a JIT Compiler</a></li>
25 <li><a href="#code">Full Code Listing</a></li>
28 <li><a href="OCamlLangImpl5.html">Chapter 5</a>: Extending the Language: Control
32 <div class="doc_author">
34 Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>
35 and <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a>
39 <!-- *********************************************************************** -->
40 <div class="doc_section"><a name="intro">Chapter 4 Introduction</a></div>
41 <!-- *********************************************************************** -->
43 <div class="doc_text">
45 <p>Welcome to Chapter 4 of the "<a href="index.html">Implementing a language
46 with LLVM</a>" tutorial. Chapters 1-3 described the implementation of a simple
47 language and added support for generating LLVM IR. This chapter describes
48 two new techniques: adding optimizer support to your language, and adding JIT
49 compiler support. These additions will demonstrate how to get nice, efficient code
50 for the Kaleidoscope language.</p>
54 <!-- *********************************************************************** -->
55 <div class="doc_section"><a name="trivialconstfold">Trivial Constant
57 <!-- *********************************************************************** -->
59 <div class="doc_text">
61 <p><b>Note:</b> the ocaml bindings already use <tt>LLVMFoldingBuilder</tt>.<p>
64 Our demonstration for Chapter 3 is elegant and easy to extend. Unfortunately,
65 it does not produce wonderful code. For example, when compiling simple code,
66 we don't get obvious optimizations:</p>
68 <div class="doc_code">
70 ready> <b>def test(x) 1+2+x;</b>
71 Read function definition:
72 define double @test(double %x) {
74 %addtmp = add double 1.000000e+00, 2.000000e+00
75 %addtmp1 = add double %addtmp, %x
81 <p>This code is a very, very literal transcription of the AST built by parsing
82 the input. As such, this transcription lacks optimizations like constant folding
83 (we'd like to get "<tt>add x, 3.0</tt>" in the example above) as well as other
84 more important optimizations. Constant folding, in particular, is a very common
85 and very important optimization: so much so that many language implementors
86 implement constant folding support in their AST representation.</p>
88 <p>With LLVM, you don't need this support in the AST. Since all calls to build
89 LLVM IR go through the LLVM builder, it would be nice if the builder itself
90 checked to see if there was a constant folding opportunity when you call it.
91 If so, it could just do the constant fold and return the constant instead of
92 creating an instruction. This is exactly what the <tt>LLVMFoldingBuilder</tt>
95 <p>All we did was switch from <tt>LLVMBuilder</tt> to
96 <tt>LLVMFoldingBuilder</tt>. Though we change no other code, we now have all of our
97 instructions implicitly constant folded without us having to do anything
98 about it. For example, the input above now compiles to:</p>
100 <div class="doc_code">
102 ready> <b>def test(x) 1+2+x;</b>
103 Read function definition:
104 define double @test(double %x) {
106 %addtmp = add double 3.000000e+00, %x
112 <p>Well, that was easy :). In practice, we recommend always using
113 <tt>LLVMFoldingBuilder</tt> when generating code like this. It has no
114 "syntactic overhead" for its use (you don't have to uglify your compiler with
115 constant checks everywhere) and it can dramatically reduce the amount of
116 LLVM IR that is generated in some cases (particular for languages with a macro
117 preprocessor or that use a lot of constants).</p>
119 <p>On the other hand, the <tt>LLVMFoldingBuilder</tt> is limited by the fact
120 that it does all of its analysis inline with the code as it is built. If you
121 take a slightly more complex example:</p>
123 <div class="doc_code">
125 ready> <b>def test(x) (1+2+x)*(x+(1+2));</b>
126 ready> Read function definition:
127 define double @test(double %x) {
129 %addtmp = add double 3.000000e+00, %x
130 %addtmp1 = add double %x, 3.000000e+00
131 %multmp = mul double %addtmp, %addtmp1
137 <p>In this case, the LHS and RHS of the multiplication are the same value. We'd
138 really like to see this generate "<tt>tmp = x+3; result = tmp*tmp;</tt>" instead
139 of computing "<tt>x*3</tt>" twice.</p>
141 <p>Unfortunately, no amount of local analysis will be able to detect and correct
142 this. This requires two transformations: reassociation of expressions (to
143 make the add's lexically identical) and Common Subexpression Elimination (CSE)
144 to delete the redundant add instruction. Fortunately, LLVM provides a broad
145 range of optimizations that you can use, in the form of "passes".</p>
149 <!-- *********************************************************************** -->
150 <div class="doc_section"><a name="optimizerpasses">LLVM Optimization
152 <!-- *********************************************************************** -->
154 <div class="doc_text">
156 <p>LLVM provides many optimization passes, which do many different sorts of
157 things and have different tradeoffs. Unlike other systems, LLVM doesn't hold
158 to the mistaken notion that one set of optimizations is right for all languages
159 and for all situations. LLVM allows a compiler implementor to make complete
160 decisions about what optimizations to use, in which order, and in what
163 <p>As a concrete example, LLVM supports both "whole module" passes, which look
164 across as large of body of code as they can (often a whole file, but if run
165 at link time, this can be a substantial portion of the whole program). It also
166 supports and includes "per-function" passes which just operate on a single
167 function at a time, without looking at other functions. For more information
168 on passes and how they are run, see the <a href="../WritingAnLLVMPass.html">How
169 to Write a Pass</a> document and the <a href="../Passes.html">List of LLVM
172 <p>For Kaleidoscope, we are currently generating functions on the fly, one at
173 a time, as the user types them in. We aren't shooting for the ultimate
174 optimization experience in this setting, but we also want to catch the easy and
175 quick stuff where possible. As such, we will choose to run a few per-function
176 optimizations as the user types the function in. If we wanted to make a "static
177 Kaleidoscope compiler", we would use exactly the code we have now, except that
178 we would defer running the optimizer until the entire file has been parsed.</p>
180 <p>In order to get per-function optimizations going, we need to set up a
181 <a href="../WritingAnLLVMPass.html#passmanager">Llvm.PassManager</a> to hold and
182 organize the LLVM optimizations that we want to run. Once we have that, we can
183 add a set of optimizations to run. The code looks like this:</p>
185 <div class="doc_code">
187 (* Create the JIT. *)
188 let the_module_provider = ModuleProvider.create Codegen.the_module in
189 let the_execution_engine = ExecutionEngine.create the_module_provider in
190 let the_fpm = PassManager.create_function the_module_provider in
192 (* Set up the optimizer pipeline. Start with registering info about how the
193 * target lays out data structures. *)
194 TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
196 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
197 add_instruction_combining the_fpm;
199 (* reassociate expressions. *)
200 add_reassociation the_fpm;
202 (* Eliminate Common SubExpressions. *)
205 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
206 add_cfg_simplification the_fpm;
208 (* Run the main "interpreter loop" now. *)
209 Toplevel.main_loop the_fpm the_execution_engine stream;
213 <p>This code defines two values, an <tt>Llvm.llmoduleprovider</tt> and a
214 <tt>Llvm.PassManager.t</tt>. The former is basically a wrapper around our
215 <tt>Llvm.llmodule</tt> that the <tt>Llvm.PassManager.t</tt> requires. It
216 provides certain flexibility that we're not going to take advantage of here,
217 so I won't dive into any details about it.</p>
219 <p>The meat of the matter here, is the definition of "<tt>the_fpm</tt>". It
220 requires a pointer to the <tt>the_module</tt> (through the
221 <tt>the_module_provider</tt>) to construct itself. Once it is set up, we use a
222 series of "add" calls to add a bunch of LLVM passes. The first pass is
223 basically boilerplate, it adds a pass so that later optimizations know how the
224 data structures in the program are layed out. The
225 "<tt>the_execution_engine</tt>" variable is related to the JIT, which we will
226 get to in the next section.</p>
228 <p>In this case, we choose to add 4 optimization passes. The passes we chose
229 here are a pretty standard set of "cleanup" optimizations that are useful for
230 a wide variety of code. I won't delve into what they do but, believe me,
231 they are a good starting place :).</p>
233 <p>Once the <tt>Llvm.PassManager.</tt> is set up, we need to make use of it.
234 We do this by running it after our newly created function is constructed (in
235 <tt>Codegen.codegen_func</tt>), but before it is returned to the client:</p>
237 <div class="doc_code">
239 let codegen_func the_fpm = function
242 let ret_val = codegen_expr body in
244 (* Finish off the function. *)
245 let _ = build_ret ret_val builder in
247 (* Validate the generated code, checking for consistency. *)
248 Llvm_analysis.assert_valid_function the_function;
250 (* Optimize the function. *)
251 let _ = PassManager.run_function the_function the_fpm in
257 <p>As you can see, this is pretty straightforward. The <tt>the_fpm</tt>
258 optimizes and updates the LLVM Function* in place, improving (hopefully) its
259 body. With this in place, we can try our test above again:</p>
261 <div class="doc_code">
263 ready> <b>def test(x) (1+2+x)*(x+(1+2));</b>
264 ready> Read function definition:
265 define double @test(double %x) {
267 %addtmp = add double %x, 3.000000e+00
268 %multmp = mul double %addtmp, %addtmp
274 <p>As expected, we now get our nicely optimized code, saving a floating point
275 add instruction from every execution of this function.</p>
277 <p>LLVM provides a wide variety of optimizations that can be used in certain
278 circumstances. Some <a href="../Passes.html">documentation about the various
279 passes</a> is available, but it isn't very complete. Another good source of
280 ideas can come from looking at the passes that <tt>llvm-gcc</tt> or
281 <tt>llvm-ld</tt> run to get started. The "<tt>opt</tt>" tool allows you to
282 experiment with passes from the command line, so you can see if they do
285 <p>Now that we have reasonable code coming out of our front-end, lets talk about
290 <!-- *********************************************************************** -->
291 <div class="doc_section"><a name="jit">Adding a JIT Compiler</a></div>
292 <!-- *********************************************************************** -->
294 <div class="doc_text">
296 <p>Code that is available in LLVM IR can have a wide variety of tools
297 applied to it. For example, you can run optimizations on it (as we did above),
298 you can dump it out in textual or binary forms, you can compile the code to an
299 assembly file (.s) for some target, or you can JIT compile it. The nice thing
300 about the LLVM IR representation is that it is the "common currency" between
301 many different parts of the compiler.
304 <p>In this section, we'll add JIT compiler support to our interpreter. The
305 basic idea that we want for Kaleidoscope is to have the user enter function
306 bodies as they do now, but immediately evaluate the top-level expressions they
307 type in. For example, if they type in "1 + 2;", we should evaluate and print
308 out 3. If they define a function, they should be able to call it from the
311 <p>In order to do this, we first declare and initialize the JIT. This is done
312 by adding a global variable and a call in <tt>main</tt>:</p>
314 <div class="doc_code">
320 (* Create the JIT. *)
321 let the_module_provider = ModuleProvider.create Codegen.the_module in
322 let the_execution_engine = ExecutionEngine.create the_module_provider in</b>
327 <p>This creates an abstract "Execution Engine" which can be either a JIT
328 compiler or the LLVM interpreter. LLVM will automatically pick a JIT compiler
329 for you if one is available for your platform, otherwise it will fall back to
332 <p>Once the <tt>Llvm_executionengine.ExecutionEngine.t</tt> is created, the JIT
333 is ready to be used. There are a variety of APIs that are useful, but the
334 simplest one is the "<tt>Llvm_executionengine.ExecutionEngine.run_function</tt>"
335 function. This method JIT compiles the specified LLVM Function and returns a
336 function pointer to the generated machine code. In our case, this means that we
337 can change the code that parses a top-level expression to look like this:</p>
339 <div class="doc_code">
341 (* Evaluate a top-level expression into an anonymous function. *)
342 let e = Parser.parse_toplevel stream in
343 print_endline "parsed a top-level expr";
344 let the_function = Codegen.codegen_func the_fpm e in
345 dump_value the_function;
347 (* JIT the function, returning a function pointer. *)
348 let result = ExecutionEngine.run_function the_function [||]
349 the_execution_engine in
351 print_string "Evaluated to ";
352 print_float (GenericValue.as_float double_type result);
357 <p>Recall that we compile top-level expressions into a self-contained LLVM
358 function that takes no arguments and returns the computed double. Because the
359 LLVM JIT compiler matches the native platform ABI, this means that you can just
360 cast the result pointer to a function pointer of that type and call it directly.
361 This means, there is no difference between JIT compiled code and native machine
362 code that is statically linked into your application.</p>
364 <p>With just these two changes, lets see how Kaleidoscope works now!</p>
366 <div class="doc_code">
368 ready> <b>4+5;</b>
369 define double @""() {
371 ret double 9.000000e+00
374 <em>Evaluated to 9.000000</em>
378 <p>Well this looks like it is basically working. The dump of the function
379 shows the "no argument function that always returns double" that we synthesize
380 for each top level expression that is typed in. This demonstrates very basic
381 functionality, but can we do more?</p>
383 <div class="doc_code">
385 ready> <b>def testfunc(x y) x + y*2; </b>
386 Read function definition:
387 define double @testfunc(double %x, double %y) {
389 %multmp = mul double %y, 2.000000e+00
390 %addtmp = add double %multmp, %x
394 ready> <b>testfunc(4, 10);</b>
395 define double @""() {
397 %calltmp = call double @testfunc( double 4.000000e+00, double 1.000000e+01 )
401 <em>Evaluated to 24.000000</em>
405 <p>This illustrates that we can now call user code, but there is something a bit
406 subtle going on here. Note that we only invoke the JIT on the anonymous
407 functions that <em>call testfunc</em>, but we never invoked it on <em>testfunc
410 <p>What actually happened here is that the anonymous function was JIT'd when
411 requested. When the Kaleidoscope app calls through the function pointer that is
412 returned, the anonymous function starts executing. It ends up making the call
413 to the "testfunc" function, and ends up in a stub that invokes the JIT, lazily,
414 on testfunc. Once the JIT finishes lazily compiling testfunc,
415 it returns and the code re-executes the call.</p>
417 <p>In summary, the JIT will lazily JIT code, on the fly, as it is needed. The
418 JIT provides a number of other more advanced interfaces for things like freeing
419 allocated machine code, rejit'ing functions to update them, etc. However, even
420 with this simple code, we get some surprisingly powerful capabilities - check
421 this out (I removed the dump of the anonymous functions, you should get the idea
424 <div class="doc_code">
426 ready> <b>extern sin(x);</b>
428 declare double @sin(double)
430 ready> <b>extern cos(x);</b>
432 declare double @cos(double)
434 ready> <b>sin(1.0);</b>
435 <em>Evaluated to 0.841471</em>
437 ready> <b>def foo(x) sin(x)*sin(x) + cos(x)*cos(x);</b>
438 Read function definition:
439 define double @foo(double %x) {
441 %calltmp = call double @sin( double %x )
442 %multmp = mul double %calltmp, %calltmp
443 %calltmp2 = call double @cos( double %x )
444 %multmp4 = mul double %calltmp2, %calltmp2
445 %addtmp = add double %multmp, %multmp4
449 ready> <b>foo(4.0);</b>
450 <em>Evaluated to 1.000000</em>
454 <p>Whoa, how does the JIT know about sin and cos? The answer is surprisingly
455 simple: in this example, the JIT started execution of a function and got to a
456 function call. It realized that the function was not yet JIT compiled and
457 invoked the standard set of routines to resolve the function. In this case,
458 there is no body defined for the function, so the JIT ended up calling
459 "<tt>dlsym("sin")</tt>" on the Kaleidoscope process itself. Since
460 "<tt>sin</tt>" is defined within the JIT's address space, it simply patches up
461 calls in the module to call the libm version of <tt>sin</tt> directly.</p>
463 <p>The LLVM JIT provides a number of interfaces (look in the
464 <tt>llvm_executionengine.mli</tt> file) for controlling how unknown functions
465 get resolved. It allows you to establish explicit mappings between IR objects
466 and addresses (useful for LLVM global variables that you want to map to static
467 tables, for example), allows you to dynamically decide on the fly based on the
468 function name, and even allows you to have the JIT abort itself if any lazy
469 compilation is attempted.</p>
471 <p>One interesting application of this is that we can now extend the language
472 by writing arbitrary C code to implement operations. For example, if we add:
475 <div class="doc_code">
477 /* putchard - putchar that takes a double and returns 0. */
479 double putchard(double X) {
486 <p>Now we can produce simple output to the console by using things like:
487 "<tt>extern putchard(x); putchard(120);</tt>", which prints a lowercase 'x' on
488 the console (120 is the ASCII code for 'x'). Similar code could be used to
489 implement file I/O, console input, and many other capabilities in
492 <p>This completes the JIT and optimizer chapter of the Kaleidoscope tutorial. At
493 this point, we can compile a non-Turing-complete programming language, optimize
494 and JIT compile it in a user-driven way. Next up we'll look into <a
495 href="OCamlLangImpl5.html">extending the language with control flow
496 constructs</a>, tackling some interesting LLVM IR issues along the way.</p>
500 <!-- *********************************************************************** -->
501 <div class="doc_section"><a name="code">Full Code Listing</a></div>
502 <!-- *********************************************************************** -->
504 <div class="doc_text">
507 Here is the complete code listing for our running example, enhanced with the
508 LLVM JIT and optimizer. To build this example, use:
513 <dd class="doc_code">
515 <{lexer,parser}.ml>: use_camlp4, pp(camlp4of)
516 <*.{byte,native}>: g++, use_llvm, use_llvm_analysis
517 <*.{byte,native}>: use_llvm_executionengine, use_llvm_target
518 <*.{byte,native}>: use_llvm_scalar_opts, use_bindings
522 <dt>myocamlbuild.ml:</dt>
523 <dd class="doc_code">
525 open Ocamlbuild_plugin;;
527 ocaml_lib ~extern:true "llvm";;
528 ocaml_lib ~extern:true "llvm_analysis";;
529 ocaml_lib ~extern:true "llvm_executionengine";;
530 ocaml_lib ~extern:true "llvm_target";;
531 ocaml_lib ~extern:true "llvm_scalar_opts";;
533 flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
534 dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
539 <dd class="doc_code">
541 (*===----------------------------------------------------------------------===
543 *===----------------------------------------------------------------------===*)
545 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
546 * these others for known things. *)
552 | Ident of string | Number of float
560 <dd class="doc_code">
562 (*===----------------------------------------------------------------------===
564 *===----------------------------------------------------------------------===*)
567 (* Skip any whitespace. *)
568 | [< ' (' ' | '\n' | '\r' | '\t'); stream >] -> lex stream
570 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
571 | [< ' ('A' .. 'Z' | 'a' .. 'z' as c); stream >] ->
572 let buffer = Buffer.create 1 in
573 Buffer.add_char buffer c;
574 lex_ident buffer stream
576 (* number: [0-9.]+ *)
577 | [< ' ('0' .. '9' as c); stream >] ->
578 let buffer = Buffer.create 1 in
579 Buffer.add_char buffer c;
580 lex_number buffer stream
582 (* Comment until end of line. *)
583 | [< ' ('#'); stream >] ->
586 (* Otherwise, just return the character as its ascii value. *)
587 | [< 'c; stream >] ->
588 [< 'Token.Kwd c; lex stream >]
591 | [< >] -> [< >]
593 and lex_number buffer = parser
594 | [< ' ('0' .. '9' | '.' as c); stream >] ->
595 Buffer.add_char buffer c;
596 lex_number buffer stream
597 | [< stream=lex >] ->
598 [< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >]
600 and lex_ident buffer = parser
601 | [< ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream >] ->
602 Buffer.add_char buffer c;
603 lex_ident buffer stream
604 | [< stream=lex >] ->
605 match Buffer.contents buffer with
606 | "def" -> [< 'Token.Def; stream >]
607 | "extern" -> [< 'Token.Extern; stream >]
608 | id -> [< 'Token.Ident id; stream >]
610 and lex_comment = parser
611 | [< ' ('\n'); stream=lex >] -> stream
612 | [< 'c; e=lex_comment >] -> e
613 | [< >] -> [< >]
618 <dd class="doc_code">
620 (*===----------------------------------------------------------------------===
621 * Abstract Syntax Tree (aka Parse Tree)
622 *===----------------------------------------------------------------------===*)
624 (* expr - Base type for all expression nodes. *)
626 (* variant for numeric literals like "1.0". *)
629 (* variant for referencing a variable, like "a". *)
632 (* variant for a binary operator. *)
633 | Binary of char * expr * expr
635 (* variant for function calls. *)
636 | Call of string * expr array
638 (* proto - This type represents the "prototype" for a function, which captures
639 * its name, and its argument names (thus implicitly the number of arguments the
640 * function takes). *)
641 type proto = Prototype of string * string array
643 (* func - This type represents a function definition itself. *)
644 type func = Function of proto * expr
649 <dd class="doc_code">
651 (*===---------------------------------------------------------------------===
653 *===---------------------------------------------------------------------===*)
655 (* binop_precedence - This holds the precedence for each binary operator that is
657 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
659 (* precedence - Get the precedence of the pending binary operator token. *)
660 let precedence c = try Hashtbl.find binop_precedence c with Not_found -> -1
666 let rec parse_primary = parser
667 (* numberexpr ::= number *)
668 | [< 'Token.Number n >] -> Ast.Number n
670 (* parenexpr ::= '(' expression ')' *)
671 | [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
675 * ::= identifier '(' argumentexpr ')' *)
676 | [< 'Token.Ident id; stream >] ->
677 let rec parse_args accumulator = parser
678 | [< e=parse_expr; stream >] ->
680 | [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
681 | [< >] -> e :: accumulator
683 | [< >] -> accumulator
685 let rec parse_ident id = parser
687 | [< 'Token.Kwd '(';
689 'Token.Kwd ')' ?? "expected ')'">] ->
690 Ast.Call (id, Array.of_list (List.rev args))
692 (* Simple variable ref. *)
693 | [< >] -> Ast.Variable id
695 parse_ident id stream
697 | [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
700 * ::= ('+' primary)* *)
701 and parse_bin_rhs expr_prec lhs stream =
702 match Stream.peek stream with
703 (* If this is a binop, find its precedence. *)
704 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
705 let token_prec = precedence c in
707 (* If this is a binop that binds at least as tightly as the current binop,
708 * consume it, otherwise we are done. *)
709 if token_prec < expr_prec then lhs else begin
713 (* Parse the primary expression after the binary operator. *)
714 let rhs = parse_primary stream in
716 (* Okay, we know this is a binop. *)
718 match Stream.peek stream with
719 | Some (Token.Kwd c2) ->
720 (* If BinOp binds less tightly with rhs than the operator after
721 * rhs, let the pending operator take rhs as its lhs. *)
722 let next_prec = precedence c2 in
723 if token_prec < next_prec
724 then parse_bin_rhs (token_prec + 1) rhs stream
730 let lhs = Ast.Binary (c, lhs, rhs) in
731 parse_bin_rhs expr_prec lhs stream
736 * ::= primary binoprhs *)
737 and parse_expr = parser
738 | [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream
741 * ::= id '(' id* ')' *)
742 let parse_prototype =
743 let rec parse_args accumulator = parser
744 | [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
745 | [< >] -> accumulator
749 | [< 'Token.Ident id;
750 'Token.Kwd '(' ?? "expected '(' in prototype";
752 'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
754 Ast.Prototype (id, Array.of_list (List.rev args))
757 raise (Stream.Error "expected function name in prototype")
759 (* definition ::= 'def' prototype expression *)
760 let parse_definition = parser
761 | [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
764 (* toplevelexpr ::= expression *)
765 let parse_toplevel = parser
766 | [< e=parse_expr >] ->
767 (* Make an anonymous proto. *)
768 Ast.Function (Ast.Prototype ("", [||]), e)
770 (* external ::= 'extern' prototype *)
771 let parse_extern = parser
772 | [< 'Token.Extern; e=parse_prototype >] -> e
777 <dd class="doc_code">
779 (*===----------------------------------------------------------------------===
781 *===----------------------------------------------------------------------===*)
785 exception Error of string
787 let the_module = create_module "my cool jit"
788 let builder = builder ()
789 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
791 let rec codegen_expr = function
792 | Ast.Number n -> const_float double_type n
793 | Ast.Variable name ->
794 (try Hashtbl.find named_values name with
795 | Not_found -> raise (Error "unknown variable name"))
796 | Ast.Binary (op, lhs, rhs) ->
797 let lhs_val = codegen_expr lhs in
798 let rhs_val = codegen_expr rhs in
801 | '+' -> build_add lhs_val rhs_val "addtmp" builder
802 | '-' -> build_sub lhs_val rhs_val "subtmp" builder
803 | '*' -> build_mul lhs_val rhs_val "multmp" builder
805 (* Convert bool 0/1 to double 0.0 or 1.0 *)
806 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
807 build_uitofp i double_type "booltmp" builder
808 | _ -> raise (Error "invalid binary operator")
810 | Ast.Call (callee, args) ->
811 (* Look up the name in the module table. *)
813 match lookup_function callee the_module with
814 | Some callee -> callee
815 | None -> raise (Error "unknown function referenced")
817 let params = params callee in
819 (* If argument mismatch error. *)
820 if Array.length params == Array.length args then () else
821 raise (Error "incorrect # arguments passed");
822 let args = Array.map codegen_expr args in
823 build_call callee args "calltmp" builder
825 let codegen_proto = function
826 | Ast.Prototype (name, args) ->
827 (* Make the function type: double(double,double) etc. *)
828 let doubles = Array.make (Array.length args) double_type in
829 let ft = function_type double_type doubles in
831 match lookup_function name the_module with
832 | None -> declare_function name ft the_module
834 (* If 'f' conflicted, there was already something named 'name'. If it
835 * has a body, don't allow redefinition or reextern. *)
837 (* If 'f' already has a body, reject this. *)
838 if block_begin f <> At_end f then
839 raise (Error "redefinition of function");
841 (* If 'f' took a different number of arguments, reject. *)
842 if element_type (type_of f) <> ft then
843 raise (Error "redefinition of function with different # args");
847 (* Set names for all arguments. *)
848 Array.iteri (fun i a ->
851 Hashtbl.add named_values n a;
855 let codegen_func the_fpm = function
856 | Ast.Function (proto, body) ->
857 Hashtbl.clear named_values;
858 let the_function = codegen_proto proto in
860 (* Create a new basic block to start insertion into. *)
861 let bb = append_block "entry" the_function in
862 position_at_end bb builder;
865 let ret_val = codegen_expr body in
867 (* Finish off the function. *)
868 let _ = build_ret ret_val builder in
870 (* Validate the generated code, checking for consistency. *)
871 Llvm_analysis.assert_valid_function the_function;
873 (* Optimize the function. *)
874 let _ = PassManager.run_function the_function the_fpm in
878 delete_function the_function;
883 <dt>toplevel.ml:</dt>
884 <dd class="doc_code">
886 (*===----------------------------------------------------------------------===
887 * Top-Level parsing and JIT Driver
888 *===----------------------------------------------------------------------===*)
891 open Llvm_executionengine
893 (* top ::= definition | external | expression | ';' *)
894 let rec main_loop the_fpm the_execution_engine stream =
895 match Stream.peek stream with
898 (* ignore top-level semicolons. *)
899 | Some (Token.Kwd ';') ->
901 main_loop the_fpm the_execution_engine stream
907 let e = Parser.parse_definition stream in
908 print_endline "parsed a function definition.";
909 dump_value (Codegen.codegen_func the_fpm e);
911 let e = Parser.parse_extern stream in
912 print_endline "parsed an extern.";
913 dump_value (Codegen.codegen_proto e);
915 (* Evaluate a top-level expression into an anonymous function. *)
916 let e = Parser.parse_toplevel stream in
917 print_endline "parsed a top-level expr";
918 let the_function = Codegen.codegen_func the_fpm e in
919 dump_value the_function;
921 (* JIT the function, returning a function pointer. *)
922 let result = ExecutionEngine.run_function the_function [||]
923 the_execution_engine in
925 print_string "Evaluated to ";
926 print_float (GenericValue.as_float double_type result);
928 with Stream.Error s | Codegen.Error s ->
929 (* Skip token for error recovery. *)
933 print_string "ready> "; flush stdout;
934 main_loop the_fpm the_execution_engine stream
939 <dd class="doc_code">
941 (*===----------------------------------------------------------------------===
943 *===----------------------------------------------------------------------===*)
946 open Llvm_executionengine
948 open Llvm_scalar_opts
951 (* Install standard binary operators.
952 * 1 is the lowest precedence. *)
953 Hashtbl.add Parser.binop_precedence '<' 10;
954 Hashtbl.add Parser.binop_precedence '+' 20;
955 Hashtbl.add Parser.binop_precedence '-' 20;
956 Hashtbl.add Parser.binop_precedence '*' 40; (* highest. *)
958 (* Prime the first token. *)
959 print_string "ready> "; flush stdout;
960 let stream = Lexer.lex (Stream.of_channel stdin) in
962 (* Create the JIT. *)
963 let the_module_provider = ModuleProvider.create Codegen.the_module in
964 let the_execution_engine = ExecutionEngine.create the_module_provider in
965 let the_fpm = PassManager.create_function the_module_provider in
967 (* Set up the optimizer pipeline. Start with registering info about how the
968 * target lays out data structures. *)
969 TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
971 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
972 add_instruction_combining the_fpm;
974 (* reassociate expressions. *)
975 add_reassociation the_fpm;
977 (* Eliminate Common SubExpressions. *)
980 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
981 add_cfg_simplification the_fpm;
983 (* Run the main "interpreter loop" now. *)
984 Toplevel.main_loop the_fpm the_execution_engine stream;
986 (* Print out all the generated code. *)
987 dump_module Codegen.the_module
995 <dd class="doc_code">
997 #include <stdio.h>
999 /* putchard - putchar that takes a double and returns 0. */
1000 extern double putchard(double X) {
1008 <a href="OCamlLangImpl5.html">Next: Extending the language: control flow</a>
1011 <!-- *********************************************************************** -->
1014 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1015 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1016 <a href="http://validator.w3.org/check/referer"><img
1017 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1019 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1020 <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br>
1021 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1022 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $