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 default <tt>IRBuilder</tt> now always includes the constant
62 folding optimisations below.<p>
65 Our demonstration for Chapter 3 is elegant and easy to extend. Unfortunately,
66 it does not produce wonderful code. For example, when compiling simple code,
67 we don't get obvious optimizations:</p>
69 <div class="doc_code">
71 ready> <b>def test(x) 1+2+x;</b>
72 Read function definition:
73 define double @test(double %x) {
75 %addtmp = add double 1.000000e+00, 2.000000e+00
76 %addtmp1 = add double %addtmp, %x
82 <p>This code is a very, very literal transcription of the AST built by parsing
83 the input. As such, this transcription lacks optimizations like constant folding
84 (we'd like to get "<tt>add x, 3.0</tt>" in the example above) as well as other
85 more important optimizations. Constant folding, in particular, is a very common
86 and very important optimization: so much so that many language implementors
87 implement constant folding support in their AST representation.</p>
89 <p>With LLVM, you don't need this support in the AST. Since all calls to build
90 LLVM IR go through the LLVM builder, it would be nice if the builder itself
91 checked to see if there was a constant folding opportunity when you call it.
92 If so, it could just do the constant fold and return the constant instead of
93 creating an instruction. This is exactly what the <tt>LLVMFoldingBuilder</tt>
96 <p>All we did was switch from <tt>LLVMBuilder</tt> to
97 <tt>LLVMFoldingBuilder</tt>. Though we change no other code, we now have all of our
98 instructions implicitly constant folded without us having to do anything
99 about it. For example, the input above now compiles to:</p>
101 <div class="doc_code">
103 ready> <b>def test(x) 1+2+x;</b>
104 Read function definition:
105 define double @test(double %x) {
107 %addtmp = add double 3.000000e+00, %x
113 <p>Well, that was easy :). In practice, we recommend always using
114 <tt>LLVMFoldingBuilder</tt> when generating code like this. It has no
115 "syntactic overhead" for its use (you don't have to uglify your compiler with
116 constant checks everywhere) and it can dramatically reduce the amount of
117 LLVM IR that is generated in some cases (particular for languages with a macro
118 preprocessor or that use a lot of constants).</p>
120 <p>On the other hand, the <tt>LLVMFoldingBuilder</tt> is limited by the fact
121 that it does all of its analysis inline with the code as it is built. If you
122 take a slightly more complex example:</p>
124 <div class="doc_code">
126 ready> <b>def test(x) (1+2+x)*(x+(1+2));</b>
127 ready> Read function definition:
128 define double @test(double %x) {
130 %addtmp = add double 3.000000e+00, %x
131 %addtmp1 = add double %x, 3.000000e+00
132 %multmp = mul double %addtmp, %addtmp1
138 <p>In this case, the LHS and RHS of the multiplication are the same value. We'd
139 really like to see this generate "<tt>tmp = x+3; result = tmp*tmp;</tt>" instead
140 of computing "<tt>x*3</tt>" twice.</p>
142 <p>Unfortunately, no amount of local analysis will be able to detect and correct
143 this. This requires two transformations: reassociation of expressions (to
144 make the add's lexically identical) and Common Subexpression Elimination (CSE)
145 to delete the redundant add instruction. Fortunately, LLVM provides a broad
146 range of optimizations that you can use, in the form of "passes".</p>
150 <!-- *********************************************************************** -->
151 <div class="doc_section"><a name="optimizerpasses">LLVM Optimization
153 <!-- *********************************************************************** -->
155 <div class="doc_text">
157 <p>LLVM provides many optimization passes, which do many different sorts of
158 things and have different tradeoffs. Unlike other systems, LLVM doesn't hold
159 to the mistaken notion that one set of optimizations is right for all languages
160 and for all situations. LLVM allows a compiler implementor to make complete
161 decisions about what optimizations to use, in which order, and in what
164 <p>As a concrete example, LLVM supports both "whole module" passes, which look
165 across as large of body of code as they can (often a whole file, but if run
166 at link time, this can be a substantial portion of the whole program). It also
167 supports and includes "per-function" passes which just operate on a single
168 function at a time, without looking at other functions. For more information
169 on passes and how they are run, see the <a href="../WritingAnLLVMPass.html">How
170 to Write a Pass</a> document and the <a href="../Passes.html">List of LLVM
173 <p>For Kaleidoscope, we are currently generating functions on the fly, one at
174 a time, as the user types them in. We aren't shooting for the ultimate
175 optimization experience in this setting, but we also want to catch the easy and
176 quick stuff where possible. As such, we will choose to run a few per-function
177 optimizations as the user types the function in. If we wanted to make a "static
178 Kaleidoscope compiler", we would use exactly the code we have now, except that
179 we would defer running the optimizer until the entire file has been parsed.</p>
181 <p>In order to get per-function optimizations going, we need to set up a
182 <a href="../WritingAnLLVMPass.html#passmanager">Llvm.PassManager</a> to hold and
183 organize the LLVM optimizations that we want to run. Once we have that, we can
184 add a set of optimizations to run. The code looks like this:</p>
186 <div class="doc_code">
188 (* Create the JIT. *)
189 let the_module_provider = ModuleProvider.create Codegen.the_module in
190 let the_execution_engine = ExecutionEngine.create the_module_provider in
191 let the_fpm = PassManager.create_function the_module_provider in
193 (* Set up the optimizer pipeline. Start with registering info about how the
194 * target lays out data structures. *)
195 TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
197 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
198 add_instruction_combining the_fpm;
200 (* reassociate expressions. *)
201 add_reassociation the_fpm;
203 (* Eliminate Common SubExpressions. *)
206 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
207 add_cfg_simplification the_fpm;
209 ignore (PassManager.initialize the_fpm);
211 (* Run the main "interpreter loop" now. *)
212 Toplevel.main_loop the_fpm the_execution_engine stream;
216 <p>This code defines two values, an <tt>Llvm.llmoduleprovider</tt> and a
217 <tt>Llvm.PassManager.t</tt>. The former is basically a wrapper around our
218 <tt>Llvm.llmodule</tt> that the <tt>Llvm.PassManager.t</tt> requires. It
219 provides certain flexibility that we're not going to take advantage of here,
220 so I won't dive into any details about it.</p>
222 <p>The meat of the matter here, is the definition of "<tt>the_fpm</tt>". It
223 requires a pointer to the <tt>the_module</tt> (through the
224 <tt>the_module_provider</tt>) to construct itself. Once it is set up, we use a
225 series of "add" calls to add a bunch of LLVM passes. The first pass is
226 basically boilerplate, it adds a pass so that later optimizations know how the
227 data structures in the program are laid out. The
228 "<tt>the_execution_engine</tt>" variable is related to the JIT, which we will
229 get to in the next section.</p>
231 <p>In this case, we choose to add 4 optimization passes. The passes we chose
232 here are a pretty standard set of "cleanup" optimizations that are useful for
233 a wide variety of code. I won't delve into what they do but, believe me,
234 they are a good starting place :).</p>
236 <p>Once the <tt>Llvm.PassManager.</tt> is set up, we need to make use of it.
237 We do this by running it after our newly created function is constructed (in
238 <tt>Codegen.codegen_func</tt>), but before it is returned to the client:</p>
240 <div class="doc_code">
242 let codegen_func the_fpm = function
245 let ret_val = codegen_expr body in
247 (* Finish off the function. *)
248 let _ = build_ret ret_val builder in
250 (* Validate the generated code, checking for consistency. *)
251 Llvm_analysis.assert_valid_function the_function;
253 (* Optimize the function. *)
254 let _ = PassManager.run_function the_function the_fpm in
260 <p>As you can see, this is pretty straightforward. The <tt>the_fpm</tt>
261 optimizes and updates the LLVM Function* in place, improving (hopefully) its
262 body. With this in place, we can try our test above again:</p>
264 <div class="doc_code">
266 ready> <b>def test(x) (1+2+x)*(x+(1+2));</b>
267 ready> Read function definition:
268 define double @test(double %x) {
270 %addtmp = add double %x, 3.000000e+00
271 %multmp = mul double %addtmp, %addtmp
277 <p>As expected, we now get our nicely optimized code, saving a floating point
278 add instruction from every execution of this function.</p>
280 <p>LLVM provides a wide variety of optimizations that can be used in certain
281 circumstances. Some <a href="../Passes.html">documentation about the various
282 passes</a> is available, but it isn't very complete. Another good source of
283 ideas can come from looking at the passes that <tt>llvm-gcc</tt> or
284 <tt>llvm-ld</tt> run to get started. The "<tt>opt</tt>" tool allows you to
285 experiment with passes from the command line, so you can see if they do
288 <p>Now that we have reasonable code coming out of our front-end, lets talk about
293 <!-- *********************************************************************** -->
294 <div class="doc_section"><a name="jit">Adding a JIT Compiler</a></div>
295 <!-- *********************************************************************** -->
297 <div class="doc_text">
299 <p>Code that is available in LLVM IR can have a wide variety of tools
300 applied to it. For example, you can run optimizations on it (as we did above),
301 you can dump it out in textual or binary forms, you can compile the code to an
302 assembly file (.s) for some target, or you can JIT compile it. The nice thing
303 about the LLVM IR representation is that it is the "common currency" between
304 many different parts of the compiler.
307 <p>In this section, we'll add JIT compiler support to our interpreter. The
308 basic idea that we want for Kaleidoscope is to have the user enter function
309 bodies as they do now, but immediately evaluate the top-level expressions they
310 type in. For example, if they type in "1 + 2;", we should evaluate and print
311 out 3. If they define a function, they should be able to call it from the
314 <p>In order to do this, we first declare and initialize the JIT. This is done
315 by adding a global variable and a call in <tt>main</tt>:</p>
317 <div class="doc_code">
322 <b>(* Create the JIT. *)
323 let the_module_provider = ModuleProvider.create Codegen.the_module in
324 let the_execution_engine = ExecutionEngine.create the_module_provider in</b>
329 <p>This creates an abstract "Execution Engine" which can be either a JIT
330 compiler or the LLVM interpreter. LLVM will automatically pick a JIT compiler
331 for you if one is available for your platform, otherwise it will fall back to
334 <p>Once the <tt>Llvm_executionengine.ExecutionEngine.t</tt> is created, the JIT
335 is ready to be used. There are a variety of APIs that are useful, but the
336 simplest one is the "<tt>Llvm_executionengine.ExecutionEngine.run_function</tt>"
337 function. This method JIT compiles the specified LLVM Function and returns a
338 function pointer to the generated machine code. In our case, this means that we
339 can change the code that parses a top-level expression to look like this:</p>
341 <div class="doc_code">
343 (* Evaluate a top-level expression into an anonymous function. *)
344 let e = Parser.parse_toplevel stream in
345 print_endline "parsed a top-level expr";
346 let the_function = Codegen.codegen_func the_fpm e in
347 dump_value the_function;
349 (* JIT the function, returning a function pointer. *)
350 let result = ExecutionEngine.run_function the_function [||]
351 the_execution_engine in
353 print_string "Evaluated to ";
354 print_float (GenericValue.as_float double_type result);
359 <p>Recall that we compile top-level expressions into a self-contained LLVM
360 function that takes no arguments and returns the computed double. Because the
361 LLVM JIT compiler matches the native platform ABI, this means that you can just
362 cast the result pointer to a function pointer of that type and call it directly.
363 This means, there is no difference between JIT compiled code and native machine
364 code that is statically linked into your application.</p>
366 <p>With just these two changes, lets see how Kaleidoscope works now!</p>
368 <div class="doc_code">
370 ready> <b>4+5;</b>
371 define double @""() {
373 ret double 9.000000e+00
376 <em>Evaluated to 9.000000</em>
380 <p>Well this looks like it is basically working. The dump of the function
381 shows the "no argument function that always returns double" that we synthesize
382 for each top level expression that is typed in. This demonstrates very basic
383 functionality, but can we do more?</p>
385 <div class="doc_code">
387 ready> <b>def testfunc(x y) x + y*2; </b>
388 Read function definition:
389 define double @testfunc(double %x, double %y) {
391 %multmp = mul double %y, 2.000000e+00
392 %addtmp = add double %multmp, %x
396 ready> <b>testfunc(4, 10);</b>
397 define double @""() {
399 %calltmp = call double @testfunc( double 4.000000e+00, double 1.000000e+01 )
403 <em>Evaluated to 24.000000</em>
407 <p>This illustrates that we can now call user code, but there is something a bit
408 subtle going on here. Note that we only invoke the JIT on the anonymous
409 functions that <em>call testfunc</em>, but we never invoked it
410 on <em>testfunc</em> itself. What actually happened here is that the JIT
411 scanned for all non-JIT'd functions transitively called from the anonymous
412 function and compiled all of them before returning
413 from <tt>run_function</tt>.</p>
415 <p>The JIT provides a number of other more advanced interfaces for things like
416 freeing allocated machine code, rejit'ing functions to update them, etc.
417 However, even with this simple code, we get some surprisingly powerful
418 capabilities - check this out (I removed the dump of the anonymous functions,
419 you should get the idea by now :) :</p>
421 <div class="doc_code">
423 ready> <b>extern sin(x);</b>
425 declare double @sin(double)
427 ready> <b>extern cos(x);</b>
429 declare double @cos(double)
431 ready> <b>sin(1.0);</b>
432 <em>Evaluated to 0.841471</em>
434 ready> <b>def foo(x) sin(x)*sin(x) + cos(x)*cos(x);</b>
435 Read function definition:
436 define double @foo(double %x) {
438 %calltmp = call double @sin( double %x )
439 %multmp = mul double %calltmp, %calltmp
440 %calltmp2 = call double @cos( double %x )
441 %multmp4 = mul double %calltmp2, %calltmp2
442 %addtmp = add double %multmp, %multmp4
446 ready> <b>foo(4.0);</b>
447 <em>Evaluated to 1.000000</em>
451 <p>Whoa, how does the JIT know about sin and cos? The answer is surprisingly
452 simple: in this example, the JIT started execution of a function and got to a
453 function call. It realized that the function was not yet JIT compiled and
454 invoked the standard set of routines to resolve the function. In this case,
455 there is no body defined for the function, so the JIT ended up calling
456 "<tt>dlsym("sin")</tt>" on the Kaleidoscope process itself. Since
457 "<tt>sin</tt>" is defined within the JIT's address space, it simply patches up
458 calls in the module to call the libm version of <tt>sin</tt> directly.</p>
460 <p>The LLVM JIT provides a number of interfaces (look in the
461 <tt>llvm_executionengine.mli</tt> file) for controlling how unknown functions
462 get resolved. It allows you to establish explicit mappings between IR objects
463 and addresses (useful for LLVM global variables that you want to map to static
464 tables, for example), allows you to dynamically decide on the fly based on the
465 function name, and even allows you to have the JIT compile functions lazily the
466 first time they're called.</p>
468 <p>One interesting application of this is that we can now extend the language
469 by writing arbitrary C code to implement operations. For example, if we add:
472 <div class="doc_code">
474 /* putchard - putchar that takes a double and returns 0. */
476 double putchard(double X) {
483 <p>Now we can produce simple output to the console by using things like:
484 "<tt>extern putchard(x); putchard(120);</tt>", which prints a lowercase 'x' on
485 the console (120 is the ASCII code for 'x'). Similar code could be used to
486 implement file I/O, console input, and many other capabilities in
489 <p>This completes the JIT and optimizer chapter of the Kaleidoscope tutorial. At
490 this point, we can compile a non-Turing-complete programming language, optimize
491 and JIT compile it in a user-driven way. Next up we'll look into <a
492 href="OCamlLangImpl5.html">extending the language with control flow
493 constructs</a>, tackling some interesting LLVM IR issues along the way.</p>
497 <!-- *********************************************************************** -->
498 <div class="doc_section"><a name="code">Full Code Listing</a></div>
499 <!-- *********************************************************************** -->
501 <div class="doc_text">
504 Here is the complete code listing for our running example, enhanced with the
505 LLVM JIT and optimizer. To build this example, use:
508 <div class="doc_code">
517 <p>Here is the code:</p>
521 <dd class="doc_code">
523 <{lexer,parser}.ml>: use_camlp4, pp(camlp4of)
524 <*.{byte,native}>: g++, use_llvm, use_llvm_analysis
525 <*.{byte,native}>: use_llvm_executionengine, use_llvm_target
526 <*.{byte,native}>: use_llvm_scalar_opts, use_bindings
530 <dt>myocamlbuild.ml:</dt>
531 <dd class="doc_code">
533 open Ocamlbuild_plugin;;
535 ocaml_lib ~extern:true "llvm";;
536 ocaml_lib ~extern:true "llvm_analysis";;
537 ocaml_lib ~extern:true "llvm_executionengine";;
538 ocaml_lib ~extern:true "llvm_target";;
539 ocaml_lib ~extern:true "llvm_scalar_opts";;
541 flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
542 dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
547 <dd class="doc_code">
549 (*===----------------------------------------------------------------------===
551 *===----------------------------------------------------------------------===*)
553 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
554 * these others for known things. *)
560 | Ident of string | Number of float
568 <dd class="doc_code">
570 (*===----------------------------------------------------------------------===
572 *===----------------------------------------------------------------------===*)
575 (* Skip any whitespace. *)
576 | [< ' (' ' | '\n' | '\r' | '\t'); stream >] -> lex stream
578 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
579 | [< ' ('A' .. 'Z' | 'a' .. 'z' as c); stream >] ->
580 let buffer = Buffer.create 1 in
581 Buffer.add_char buffer c;
582 lex_ident buffer stream
584 (* number: [0-9.]+ *)
585 | [< ' ('0' .. '9' as c); stream >] ->
586 let buffer = Buffer.create 1 in
587 Buffer.add_char buffer c;
588 lex_number buffer stream
590 (* Comment until end of line. *)
591 | [< ' ('#'); stream >] ->
594 (* Otherwise, just return the character as its ascii value. *)
595 | [< 'c; stream >] ->
596 [< 'Token.Kwd c; lex stream >]
599 | [< >] -> [< >]
601 and lex_number buffer = parser
602 | [< ' ('0' .. '9' | '.' as c); stream >] ->
603 Buffer.add_char buffer c;
604 lex_number buffer stream
605 | [< stream=lex >] ->
606 [< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >]
608 and lex_ident buffer = parser
609 | [< ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream >] ->
610 Buffer.add_char buffer c;
611 lex_ident buffer stream
612 | [< stream=lex >] ->
613 match Buffer.contents buffer with
614 | "def" -> [< 'Token.Def; stream >]
615 | "extern" -> [< 'Token.Extern; stream >]
616 | id -> [< 'Token.Ident id; stream >]
618 and lex_comment = parser
619 | [< ' ('\n'); stream=lex >] -> stream
620 | [< 'c; e=lex_comment >] -> e
621 | [< >] -> [< >]
626 <dd class="doc_code">
628 (*===----------------------------------------------------------------------===
629 * Abstract Syntax Tree (aka Parse Tree)
630 *===----------------------------------------------------------------------===*)
632 (* expr - Base type for all expression nodes. *)
634 (* variant for numeric literals like "1.0". *)
637 (* variant for referencing a variable, like "a". *)
640 (* variant for a binary operator. *)
641 | Binary of char * expr * expr
643 (* variant for function calls. *)
644 | Call of string * expr array
646 (* proto - This type represents the "prototype" for a function, which captures
647 * its name, and its argument names (thus implicitly the number of arguments the
648 * function takes). *)
649 type proto = Prototype of string * string array
651 (* func - This type represents a function definition itself. *)
652 type func = Function of proto * expr
657 <dd class="doc_code">
659 (*===---------------------------------------------------------------------===
661 *===---------------------------------------------------------------------===*)
663 (* binop_precedence - This holds the precedence for each binary operator that is
665 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
667 (* precedence - Get the precedence of the pending binary operator token. *)
668 let precedence c = try Hashtbl.find binop_precedence c with Not_found -> -1
674 let rec parse_primary = parser
675 (* numberexpr ::= number *)
676 | [< 'Token.Number n >] -> Ast.Number n
678 (* parenexpr ::= '(' expression ')' *)
679 | [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
683 * ::= identifier '(' argumentexpr ')' *)
684 | [< 'Token.Ident id; stream >] ->
685 let rec parse_args accumulator = parser
686 | [< e=parse_expr; stream >] ->
688 | [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
689 | [< >] -> e :: accumulator
691 | [< >] -> accumulator
693 let rec parse_ident id = parser
695 | [< 'Token.Kwd '(';
697 'Token.Kwd ')' ?? "expected ')'">] ->
698 Ast.Call (id, Array.of_list (List.rev args))
700 (* Simple variable ref. *)
701 | [< >] -> Ast.Variable id
703 parse_ident id stream
705 | [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
708 * ::= ('+' primary)* *)
709 and parse_bin_rhs expr_prec lhs stream =
710 match Stream.peek stream with
711 (* If this is a binop, find its precedence. *)
712 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
713 let token_prec = precedence c in
715 (* If this is a binop that binds at least as tightly as the current binop,
716 * consume it, otherwise we are done. *)
717 if token_prec < expr_prec then lhs else begin
721 (* Parse the primary expression after the binary operator. *)
722 let rhs = parse_primary stream in
724 (* Okay, we know this is a binop. *)
726 match Stream.peek stream with
727 | Some (Token.Kwd c2) ->
728 (* If BinOp binds less tightly with rhs than the operator after
729 * rhs, let the pending operator take rhs as its lhs. *)
730 let next_prec = precedence c2 in
731 if token_prec < next_prec
732 then parse_bin_rhs (token_prec + 1) rhs stream
738 let lhs = Ast.Binary (c, lhs, rhs) in
739 parse_bin_rhs expr_prec lhs stream
744 * ::= primary binoprhs *)
745 and parse_expr = parser
746 | [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream
749 * ::= id '(' id* ')' *)
750 let parse_prototype =
751 let rec parse_args accumulator = parser
752 | [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
753 | [< >] -> accumulator
757 | [< 'Token.Ident id;
758 'Token.Kwd '(' ?? "expected '(' in prototype";
760 'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
762 Ast.Prototype (id, Array.of_list (List.rev args))
765 raise (Stream.Error "expected function name in prototype")
767 (* definition ::= 'def' prototype expression *)
768 let parse_definition = parser
769 | [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
772 (* toplevelexpr ::= expression *)
773 let parse_toplevel = parser
774 | [< e=parse_expr >] ->
775 (* Make an anonymous proto. *)
776 Ast.Function (Ast.Prototype ("", [||]), e)
778 (* external ::= 'extern' prototype *)
779 let parse_extern = parser
780 | [< 'Token.Extern; e=parse_prototype >] -> e
785 <dd class="doc_code">
787 (*===----------------------------------------------------------------------===
789 *===----------------------------------------------------------------------===*)
793 exception Error of string
795 let context = global_context ()
796 let the_module = create_module context "my cool jit"
797 let builder = builder context
798 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
800 let rec codegen_expr = function
801 | Ast.Number n -> const_float double_type n
802 | Ast.Variable name ->
803 (try Hashtbl.find named_values name with
804 | Not_found -> raise (Error "unknown variable name"))
805 | Ast.Binary (op, lhs, rhs) ->
806 let lhs_val = codegen_expr lhs in
807 let rhs_val = codegen_expr rhs in
810 | '+' -> build_add lhs_val rhs_val "addtmp" builder
811 | '-' -> build_sub lhs_val rhs_val "subtmp" builder
812 | '*' -> build_mul lhs_val rhs_val "multmp" builder
814 (* Convert bool 0/1 to double 0.0 or 1.0 *)
815 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
816 build_uitofp i double_type "booltmp" builder
817 | _ -> raise (Error "invalid binary operator")
819 | Ast.Call (callee, args) ->
820 (* Look up the name in the module table. *)
822 match lookup_function callee the_module with
823 | Some callee -> callee
824 | None -> raise (Error "unknown function referenced")
826 let params = params callee in
828 (* If argument mismatch error. *)
829 if Array.length params == Array.length args then () else
830 raise (Error "incorrect # arguments passed");
831 let args = Array.map codegen_expr args in
832 build_call callee args "calltmp" builder
834 let codegen_proto = function
835 | Ast.Prototype (name, args) ->
836 (* Make the function type: double(double,double) etc. *)
837 let doubles = Array.make (Array.length args) double_type in
838 let ft = function_type double_type doubles in
840 match lookup_function name the_module with
841 | None -> declare_function name ft the_module
843 (* If 'f' conflicted, there was already something named 'name'. If it
844 * has a body, don't allow redefinition or reextern. *)
846 (* If 'f' already has a body, reject this. *)
847 if block_begin f <> At_end f then
848 raise (Error "redefinition of function");
850 (* If 'f' took a different number of arguments, reject. *)
851 if element_type (type_of f) <> ft then
852 raise (Error "redefinition of function with different # args");
856 (* Set names for all arguments. *)
857 Array.iteri (fun i a ->
860 Hashtbl.add named_values n a;
864 let codegen_func the_fpm = function
865 | Ast.Function (proto, body) ->
866 Hashtbl.clear named_values;
867 let the_function = codegen_proto proto in
869 (* Create a new basic block to start insertion into. *)
870 let bb = append_block "entry" the_function in
871 position_at_end bb builder;
874 let ret_val = codegen_expr body in
876 (* Finish off the function. *)
877 let _ = build_ret ret_val builder in
879 (* Validate the generated code, checking for consistency. *)
880 Llvm_analysis.assert_valid_function the_function;
882 (* Optimize the function. *)
883 let _ = PassManager.run_function the_function the_fpm in
887 delete_function the_function;
892 <dt>toplevel.ml:</dt>
893 <dd class="doc_code">
895 (*===----------------------------------------------------------------------===
896 * Top-Level parsing and JIT Driver
897 *===----------------------------------------------------------------------===*)
900 open Llvm_executionengine
902 (* top ::= definition | external | expression | ';' *)
903 let rec main_loop the_fpm the_execution_engine stream =
904 match Stream.peek stream with
907 (* ignore top-level semicolons. *)
908 | Some (Token.Kwd ';') ->
910 main_loop the_fpm the_execution_engine stream
916 let e = Parser.parse_definition stream in
917 print_endline "parsed a function definition.";
918 dump_value (Codegen.codegen_func the_fpm e);
920 let e = Parser.parse_extern stream in
921 print_endline "parsed an extern.";
922 dump_value (Codegen.codegen_proto e);
924 (* Evaluate a top-level expression into an anonymous function. *)
925 let e = Parser.parse_toplevel stream in
926 print_endline "parsed a top-level expr";
927 let the_function = Codegen.codegen_func the_fpm e in
928 dump_value the_function;
930 (* JIT the function, returning a function pointer. *)
931 let result = ExecutionEngine.run_function the_function [||]
932 the_execution_engine in
934 print_string "Evaluated to ";
935 print_float (GenericValue.as_float double_type result);
937 with Stream.Error s | Codegen.Error s ->
938 (* Skip token for error recovery. *)
942 print_string "ready> "; flush stdout;
943 main_loop the_fpm the_execution_engine stream
948 <dd class="doc_code">
950 (*===----------------------------------------------------------------------===
952 *===----------------------------------------------------------------------===*)
955 open Llvm_executionengine
957 open Llvm_scalar_opts
960 ignore (initialize_native_target ());
962 (* Install standard binary operators.
963 * 1 is the lowest precedence. *)
964 Hashtbl.add Parser.binop_precedence '<' 10;
965 Hashtbl.add Parser.binop_precedence '+' 20;
966 Hashtbl.add Parser.binop_precedence '-' 20;
967 Hashtbl.add Parser.binop_precedence '*' 40; (* highest. *)
969 (* Prime the first token. *)
970 print_string "ready> "; flush stdout;
971 let stream = Lexer.lex (Stream.of_channel stdin) in
973 (* Create the JIT. *)
974 let the_module_provider = ModuleProvider.create Codegen.the_module in
975 let the_execution_engine = ExecutionEngine.create the_module_provider in
976 let the_fpm = PassManager.create_function the_module_provider in
978 (* Set up the optimizer pipeline. Start with registering info about how the
979 * target lays out data structures. *)
980 TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
982 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
983 add_instruction_combining the_fpm;
985 (* reassociate expressions. *)
986 add_reassociation the_fpm;
988 (* Eliminate Common SubExpressions. *)
991 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
992 add_cfg_simplification the_fpm;
994 ignore (PassManager.initialize the_fpm);
996 (* Run the main "interpreter loop" now. *)
997 Toplevel.main_loop the_fpm the_execution_engine stream;
999 (* Print out all the generated code. *)
1000 dump_module Codegen.the_module
1008 <dd class="doc_code">
1010 #include <stdio.h>
1012 /* putchard - putchar that takes a double and returns 0. */
1013 extern double putchard(double X) {
1021 <a href="OCamlLangImpl5.html">Next: Extending the language: control flow</a>
1024 <!-- *********************************************************************** -->
1027 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1028 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1029 <a href="http://validator.w3.org/check/referer"><img
1030 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1032 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1033 <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br>
1034 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1035 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $