docs/tutorial/OCamlLangImpl4.html

   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   <meta name="author" content="Erick Tryzelaar">
  10   <link rel="stylesheet" href="../llvm.css" type="text/css">
  11 </head>
  12
  13 <body>
  14
  15 <div class="doc_title">Kaleidoscope: Adding JIT and Optimizer Support</div>
  16
  17 <ul>
  18 <li><a href="index.html">Up to Tutorial Index</a></li>
  19 <li>Chapter 4
  20   <ol>
  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>
  26   </ol>
  27 </li>
  28 <li><a href="OCamlLangImpl5.html">Chapter 5</a>: Extending the Language: Control
  29 Flow</li>
  30 </ul>
  31
  32 <div class="doc_author">
  33         <p>
  34                 Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>
  35                 and <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a>
  36         </p>
  37 </div>
  38
  39 <!-- *********************************************************************** -->
  40 <div class="doc_section"><a name="intro">Chapter 4 Introduction</a></div>
  41 <!-- *********************************************************************** -->
  42
  43 <div class="doc_text">
  44
  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>
  51
  52 </div>
  53
  54 <!-- *********************************************************************** -->
  55 <div class="doc_section"><a name="trivialconstfold">Trivial Constant
  56 Folding</a></div>
  57 <!-- *********************************************************************** -->
  58
  59 <div class="doc_text">
  60
  61 <p><b>Note:</b> the default <tt>IRBuilder</tt> now always includes the constant
  62 folding optimisations below.<p>
  63
  64 <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>
  68
  69 <div class="doc_code">
  70 <pre>
  71 ready&gt; <b>def test(x) 1+2+x;</b>
  72 Read function definition:
  73 define double @test(double %x) {
  74 entry:
  75         %addtmp = fadd double 1.000000e+00, 2.000000e+00
  76         %addtmp1 = fadd double %addtmp, %x
  77         ret double %addtmp1
  78 }
  79 </pre>
  80 </div>
  81
  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>
  88
  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>
  94 class does.
  95
  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>
 100
 101 <div class="doc_code">
 102 <pre>
 103 ready&gt; <b>def test(x) 1+2+x;</b>
 104 Read function definition:
 105 define double @test(double %x) {
 106 entry:
 107         %addtmp = fadd double 3.000000e+00, %x
 108         ret double %addtmp
 109 }
 110 </pre>
 111 </div>
 112
 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>
 119
 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>
 123
 124 <div class="doc_code">
 125 <pre>
 126 ready&gt; <b>def test(x) (1+2+x)*(x+(1+2));</b>
 127 ready&gt; Read function definition:
 128 define double @test(double %x) {
 129 entry:
 130         %addtmp = fadd double 3.000000e+00, %x
 131         %addtmp1 = fadd double %x, 3.000000e+00
 132         %multmp = fmul double %addtmp, %addtmp1
 133         ret double %multmp
 134 }
 135 </pre>
 136 </div>
 137
 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>
 141
 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>
 147
 148 </div>
 149
 150 <!-- *********************************************************************** -->
 151 <div class="doc_section"><a name="optimizerpasses">LLVM Optimization
 152  Passes</a></div>
 153 <!-- *********************************************************************** -->
 154
 155 <div class="doc_text">
 156
 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
 162 situation.</p>
 163
 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
 171 Passes</a>.</p>
 172
 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>
 180
 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>
 185
 186 <div class="doc_code">
 187 <pre>
 188   (* Create the JIT. *)
 189   let the_execution_engine = ExecutionEngine.create Codegen.the_module in
 190   let the_fpm = PassManager.create_function Codegen.the_module in
 191
 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;
 195
 196   (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
 197   add_instruction_combining the_fpm;
 198
 199   (* reassociate expressions. *)
 200   add_reassociation the_fpm;
 201
 202   (* Eliminate Common SubExpressions. *)
 203   add_gvn the_fpm;
 204
 205   (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
 206   add_cfg_simplification the_fpm;
 207
 208   ignore (PassManager.initialize the_fpm);
 209
 210   (* Run the main "interpreter loop" now. *)
 211   Toplevel.main_loop the_fpm the_execution_engine stream;
 212 </pre>
 213 </div>
 214
 215 <p>The meat of the matter here, is the definition of "<tt>the_fpm</tt>".  It
 216 requires a pointer to the <tt>the_module</tt> to construct itself.  Once it is
 217 set up, we use a series of "add" calls to add a bunch of LLVM passes.  The
 218 first pass is basically boilerplate, it adds a pass so that later optimizations
 219 know how the data structures in the program are laid out.  The
 220 "<tt>the_execution_engine</tt>" variable is related to the JIT, which we will
 221 get to in the next section.</p>
 222
 223 <p>In this case, we choose to add 4 optimization passes.  The passes we chose
 224 here are a pretty standard set of "cleanup" optimizations that are useful for
 225 a wide variety of code.  I won't delve into what they do but, believe me,
 226 they are a good starting place :).</p>
 227
 228 <p>Once the <tt>Llvm.PassManager.</tt> is set up, we need to make use of it.
 229 We do this by running it after our newly created function is constructed (in
 230 <tt>Codegen.codegen_func</tt>), but before it is returned to the client:</p>
 231
 232 <div class="doc_code">
 233 <pre>
 234 let codegen_func the_fpm = function
 235       ...
 236       try
 237         let ret_val = codegen_expr body in
 238
 239         (* Finish off the function. *)
 240         let _ = build_ret ret_val builder in
 241
 242         (* Validate the generated code, checking for consistency. *)
 243         Llvm_analysis.assert_valid_function the_function;
 244
 245         (* Optimize the function. *)
 246         let _ = PassManager.run_function the_function the_fpm in
 247
 248         the_function
 249 </pre>
 250 </div>
 251
 252 <p>As you can see, this is pretty straightforward.  The <tt>the_fpm</tt>
 253 optimizes and updates the LLVM Function* in place, improving (hopefully) its
 254 body.  With this in place, we can try our test above again:</p>
 255
 256 <div class="doc_code">
 257 <pre>
 258 ready&gt; <b>def test(x) (1+2+x)*(x+(1+2));</b>
 259 ready&gt; Read function definition:
 260 define double @test(double %x) {
 261 entry:
 262         %addtmp = fadd double %x, 3.000000e+00
 263         %multmp = fmul double %addtmp, %addtmp
 264         ret double %multmp
 265 }
 266 </pre>
 267 </div>
 268
 269 <p>As expected, we now get our nicely optimized code, saving a floating point
 270 add instruction from every execution of this function.</p>
 271
 272 <p>LLVM provides a wide variety of optimizations that can be used in certain
 273 circumstances.  Some <a href="../Passes.html">documentation about the various
 274 passes</a> is available, but it isn't very complete.  Another good source of
 275 ideas can come from looking at the passes that <tt>llvm-gcc</tt> or
 276 <tt>llvm-ld</tt> run to get started.  The "<tt>opt</tt>" tool allows you to
 277 experiment with passes from the command line, so you can see if they do
 278 anything.</p>
 279
 280 <p>Now that we have reasonable code coming out of our front-end, lets talk about
 281 executing it!</p>
 282
 283 </div>
 284
 285 <!-- *********************************************************************** -->
 286 <div class="doc_section"><a name="jit">Adding a JIT Compiler</a></div>
 287 <!-- *********************************************************************** -->
 288
 289 <div class="doc_text">
 290
 291 <p>Code that is available in LLVM IR can have a wide variety of tools
 292 applied to it.  For example, you can run optimizations on it (as we did above),
 293 you can dump it out in textual or binary forms, you can compile the code to an
 294 assembly file (.s) for some target, or you can JIT compile it.  The nice thing
 295 about the LLVM IR representation is that it is the "common currency" between
 296 many different parts of the compiler.
 297 </p>
 298
 299 <p>In this section, we'll add JIT compiler support to our interpreter.  The
 300 basic idea that we want for Kaleidoscope is to have the user enter function
 301 bodies as they do now, but immediately evaluate the top-level expressions they
 302 type in.  For example, if they type in "1 + 2;", we should evaluate and print
 303 out 3.  If they define a function, they should be able to call it from the
 304 command line.</p>
 305
 306 <p>In order to do this, we first declare and initialize the JIT.  This is done
 307 by adding a global variable and a call in <tt>main</tt>:</p>
 308
 309 <div class="doc_code">
 310 <pre>
 311 ...
 312 let main () =
 313   ...
 314   <b>(* Create the JIT. *)
 315   let the_execution_engine = ExecutionEngine.create Codegen.the_module in</b>
 316   ...
 317 </pre>
 318 </div>
 319
 320 <p>This creates an abstract "Execution Engine" which can be either a JIT
 321 compiler or the LLVM interpreter.  LLVM will automatically pick a JIT compiler
 322 for you if one is available for your platform, otherwise it will fall back to
 323 the interpreter.</p>
 324
 325 <p>Once the <tt>Llvm_executionengine.ExecutionEngine.t</tt> is created, the JIT
 326 is ready to be used.  There are a variety of APIs that are useful, but the
 327 simplest one is the "<tt>Llvm_executionengine.ExecutionEngine.run_function</tt>"
 328 function.  This method JIT compiles the specified LLVM Function and returns a
 329 function pointer to the generated machine code.  In our case, this means that we
 330 can change the code that parses a top-level expression to look like this:</p>
 331
 332 <div class="doc_code">
 333 <pre>
 334             (* Evaluate a top-level expression into an anonymous function. *)
 335             let e = Parser.parse_toplevel stream in
 336             print_endline "parsed a top-level expr";
 337             let the_function = Codegen.codegen_func the_fpm e in
 338             dump_value the_function;
 339
 340             (* JIT the function, returning a function pointer. *)
 341             let result = ExecutionEngine.run_function the_function [||]
 342               the_execution_engine in
 343
 344             print_string "Evaluated to ";
 345             print_float (GenericValue.as_float Codegen.double_type result);
 346             print_newline ();
 347 </pre>
 348 </div>
 349
 350 <p>Recall that we compile top-level expressions into a self-contained LLVM
 351 function that takes no arguments and returns the computed double.  Because the
 352 LLVM JIT compiler matches the native platform ABI, this means that you can just
 353 cast the result pointer to a function pointer of that type and call it directly.
 354 This means, there is no difference between JIT compiled code and native machine
 355 code that is statically linked into your application.</p>
 356
 357 <p>With just these two changes, lets see how Kaleidoscope works now!</p>
 358
 359 <div class="doc_code">
 360 <pre>
 361 ready&gt; <b>4+5;</b>
 362 define double @""() {
 363 entry:
 364         ret double 9.000000e+00
 365 }
 366
 367 <em>Evaluated to 9.000000</em>
 368 </pre>
 369 </div>
 370
 371 <p>Well this looks like it is basically working.  The dump of the function
 372 shows the "no argument function that always returns double" that we synthesize
 373 for each top level expression that is typed in.  This demonstrates very basic
 374 functionality, but can we do more?</p>
 375
 376 <div class="doc_code">
 377 <pre>
 378 ready&gt; <b>def testfunc(x y) x + y*2; </b>
 379 Read function definition:
 380 define double @testfunc(double %x, double %y) {
 381 entry:
 382         %multmp = fmul double %y, 2.000000e+00
 383         %addtmp = fadd double %multmp, %x
 384         ret double %addtmp
 385 }
 386
 387 ready&gt; <b>testfunc(4, 10);</b>
 388 define double @""() {
 389 entry:
 390         %calltmp = call double @testfunc( double 4.000000e+00, double 1.000000e+01 )
 391         ret double %calltmp
 392 }
 393
 394 <em>Evaluated to 24.000000</em>
 395 </pre>
 396 </div>
 397
 398 <p>This illustrates that we can now call user code, but there is something a bit
 399 subtle going on here.  Note that we only invoke the JIT on the anonymous
 400 functions that <em>call testfunc</em>, but we never invoked it
 401 on <em>testfunc</em> itself.  What actually happened here is that the JIT
 402 scanned for all non-JIT'd functions transitively called from the anonymous
 403 function and compiled all of them before returning
 404 from <tt>run_function</tt>.</p>
 405
 406 <p>The JIT provides a number of other more advanced interfaces for things like
 407 freeing allocated machine code, rejit'ing functions to update them, etc.
 408 However, even with this simple code, we get some surprisingly powerful
 409 capabilities - check this out (I removed the dump of the anonymous functions,
 410 you should get the idea by now :) :</p>
 411
 412 <div class="doc_code">
 413 <pre>
 414 ready&gt; <b>extern sin(x);</b>
 415 Read extern:
 416 declare double @sin(double)
 417
 418 ready&gt; <b>extern cos(x);</b>
 419 Read extern:
 420 declare double @cos(double)
 421
 422 ready&gt; <b>sin(1.0);</b>
 423 <em>Evaluated to 0.841471</em>
 424
 425 ready&gt; <b>def foo(x) sin(x)*sin(x) + cos(x)*cos(x);</b>
 426 Read function definition:
 427 define double @foo(double %x) {
 428 entry:
 429         %calltmp = call double @sin( double %x )
 430         %multmp = fmul double %calltmp, %calltmp
 431         %calltmp2 = call double @cos( double %x )
 432         %multmp4 = fmul double %calltmp2, %calltmp2
 433         %addtmp = fadd double %multmp, %multmp4
 434         ret double %addtmp
 435 }
 436
 437 ready&gt; <b>foo(4.0);</b>
 438 <em>Evaluated to 1.000000</em>
 439 </pre>
 440 </div>
 441
 442 <p>Whoa, how does the JIT know about sin and cos?  The answer is surprisingly
 443 simple: in this example, the JIT started execution of a function and got to a
 444 function call.  It realized that the function was not yet JIT compiled and
 445 invoked the standard set of routines to resolve the function.  In this case,
 446 there is no body defined for the function, so the JIT ended up calling
 447 "<tt>dlsym("sin")</tt>" on the Kaleidoscope process itself.  Since
 448 "<tt>sin</tt>" is defined within the JIT's address space, it simply patches up
 449 calls in the module to call the libm version of <tt>sin</tt> directly.</p>
 450
 451 <p>The LLVM JIT provides a number of interfaces (look in the
 452 <tt>llvm_executionengine.mli</tt> file) for controlling how unknown functions
 453 get resolved.  It allows you to establish explicit mappings between IR objects
 454 and addresses (useful for LLVM global variables that you want to map to static
 455 tables, for example), allows you to dynamically decide on the fly based on the
 456 function name, and even allows you to have the JIT compile functions lazily the
 457 first time they're called.</p>
 458
 459 <p>One interesting application of this is that we can now extend the language
 460 by writing arbitrary C code to implement operations.  For example, if we add:
 461 </p>
 462
 463 <div class="doc_code">
 464 <pre>
 465 /* putchard - putchar that takes a double and returns 0. */
 466 extern "C"
 467 double putchard(double X) {
 468   putchar((char)X);
 469   return 0;
 470 }
 471 </pre>
 472 </div>
 473
 474 <p>Now we can produce simple output to the console by using things like:
 475 "<tt>extern putchard(x); putchard(120);</tt>", which prints a lowercase 'x' on
 476 the console (120 is the ASCII code for 'x').  Similar code could be used to
 477 implement file I/O, console input, and many other capabilities in
 478 Kaleidoscope.</p>
 479
 480 <p>This completes the JIT and optimizer chapter of the Kaleidoscope tutorial. At
 481 this point, we can compile a non-Turing-complete programming language, optimize
 482 and JIT compile it in a user-driven way.  Next up we'll look into <a
 483 href="OCamlLangImpl5.html">extending the language with control flow
 484 constructs</a>, tackling some interesting LLVM IR issues along the way.</p>
 485
 486 </div>
 487
 488 <!-- *********************************************************************** -->
 489 <div class="doc_section"><a name="code">Full Code Listing</a></div>
 490 <!-- *********************************************************************** -->
 491
 492 <div class="doc_text">
 493
 494 <p>
 495 Here is the complete code listing for our running example, enhanced with the
 496 LLVM JIT and optimizer.  To build this example, use:
 497 </p>
 498
 499 <div class="doc_code">
 500 <pre>
 501 # Compile
 502 ocamlbuild toy.byte
 503 # Run
 504 ./toy.byte
 505 </pre>
 506 </div>
 507
 508 <p>Here is the code:</p>
 509
 510 <dl>
 511 <dt>_tags:</dt>
 512 <dd class="doc_code">
 513 <pre>
 514 &lt;{lexer,parser}.ml&gt;: use_camlp4, pp(camlp4of)
 515 &lt;*.{byte,native}&gt;: g++, use_llvm, use_llvm_analysis
 516 &lt;*.{byte,native}&gt;: use_llvm_executionengine, use_llvm_target
 517 &lt;*.{byte,native}&gt;: use_llvm_scalar_opts, use_bindings
 518 </pre>
 519 </dd>
 520
 521 <dt>myocamlbuild.ml:</dt>
 522 <dd class="doc_code">
 523 <pre>
 524 open Ocamlbuild_plugin;;
 525
 526 ocaml_lib ~extern:true "llvm";;
 527 ocaml_lib ~extern:true "llvm_analysis";;
 528 ocaml_lib ~extern:true "llvm_executionengine";;
 529 ocaml_lib ~extern:true "llvm_target";;
 530 ocaml_lib ~extern:true "llvm_scalar_opts";;
 531
 532 flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
 533 dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
 534 </pre>
 535 </dd>
 536
 537 <dt>token.ml:</dt>
 538 <dd class="doc_code">
 539 <pre>
 540 (*===----------------------------------------------------------------------===
 541  * Lexer Tokens
 542  *===----------------------------------------------------------------------===*)
 543
 544 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
 545  * these others for known things. *)
 546 type token =
 547   (* commands *)
 548   | Def | Extern
 549
 550   (* primary *)
 551   | Ident of string | Number of float
 552
 553   (* unknown *)
 554   | Kwd of char
 555 </pre>
 556 </dd>
 557
 558 <dt>lexer.ml:</dt>
 559 <dd class="doc_code">
 560 <pre>
 561 (*===----------------------------------------------------------------------===
 562  * Lexer
 563  *===----------------------------------------------------------------------===*)
 564
 565 let rec lex = parser
 566   (* Skip any whitespace. *)
 567   | [&lt; ' (' ' | '\n' | '\r' | '\t'); stream &gt;] -&gt; lex stream
 568
 569   (* identifier: [a-zA-Z][a-zA-Z0-9] *)
 570   | [&lt; ' ('A' .. 'Z' | 'a' .. 'z' as c); stream &gt;] -&gt;
 571       let buffer = Buffer.create 1 in
 572       Buffer.add_char buffer c;
 573       lex_ident buffer stream
 574
 575   (* number: [0-9.]+ *)
 576   | [&lt; ' ('0' .. '9' as c); stream &gt;] -&gt;
 577       let buffer = Buffer.create 1 in
 578       Buffer.add_char buffer c;
 579       lex_number buffer stream
 580
 581   (* Comment until end of line. *)
 582   | [&lt; ' ('#'); stream &gt;] -&gt;
 583       lex_comment stream
 584
 585   (* Otherwise, just return the character as its ascii value. *)
 586   | [&lt; 'c; stream &gt;] -&gt;
 587       [&lt; 'Token.Kwd c; lex stream &gt;]
 588
 589   (* end of stream. *)
 590   | [&lt; &gt;] -&gt; [&lt; &gt;]
 591
 592 and lex_number buffer = parser
 593   | [&lt; ' ('0' .. '9' | '.' as c); stream &gt;] -&gt;
 594       Buffer.add_char buffer c;
 595       lex_number buffer stream
 596   | [&lt; stream=lex &gt;] -&gt;
 597       [&lt; 'Token.Number (float_of_string (Buffer.contents buffer)); stream &gt;]
 598
 599 and lex_ident buffer = parser
 600   | [&lt; ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream &gt;] -&gt;
 601       Buffer.add_char buffer c;
 602       lex_ident buffer stream
 603   | [&lt; stream=lex &gt;] -&gt;
 604       match Buffer.contents buffer with
 605       | "def" -&gt; [&lt; 'Token.Def; stream &gt;]
 606       | "extern" -&gt; [&lt; 'Token.Extern; stream &gt;]
 607       | id -&gt; [&lt; 'Token.Ident id; stream &gt;]
 608
 609 and lex_comment = parser
 610   | [&lt; ' ('\n'); stream=lex &gt;] -&gt; stream
 611   | [&lt; 'c; e=lex_comment &gt;] -&gt; e
 612   | [&lt; &gt;] -&gt; [&lt; &gt;]
 613 </pre>
 614 </dd>
 615
 616 <dt>ast.ml:</dt>
 617 <dd class="doc_code">
 618 <pre>
 619 (*===----------------------------------------------------------------------===
 620  * Abstract Syntax Tree (aka Parse Tree)
 621  *===----------------------------------------------------------------------===*)
 622
 623 (* expr - Base type for all expression nodes. *)
 624 type expr =
 625   (* variant for numeric literals like "1.0". *)
 626   | Number of float
 627
 628   (* variant for referencing a variable, like "a". *)
 629   | Variable of string
 630
 631   (* variant for a binary operator. *)
 632   | Binary of char * expr * expr
 633
 634   (* variant for function calls. *)
 635   | Call of string * expr array
 636
 637 (* proto - This type represents the "prototype" for a function, which captures
 638  * its name, and its argument names (thus implicitly the number of arguments the
 639  * function takes). *)
 640 type proto = Prototype of string * string array
 641
 642 (* func - This type represents a function definition itself. *)
 643 type func = Function of proto * expr
 644 </pre>
 645 </dd>
 646
 647 <dt>parser.ml:</dt>
 648 <dd class="doc_code">
 649 <pre>
 650 (*===---------------------------------------------------------------------===
 651  * Parser
 652  *===---------------------------------------------------------------------===*)
 653
 654 (* binop_precedence - This holds the precedence for each binary operator that is
 655  * defined *)
 656 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
 657
 658 (* precedence - Get the precedence of the pending binary operator token. *)
 659 let precedence c = try Hashtbl.find binop_precedence c with Not_found -&gt; -1
 660
 661 (* primary
 662  *   ::= identifier
 663  *   ::= numberexpr
 664  *   ::= parenexpr *)
 665 let rec parse_primary = parser
 666   (* numberexpr ::= number *)
 667   | [&lt; 'Token.Number n &gt;] -&gt; Ast.Number n
 668
 669   (* parenexpr ::= '(' expression ')' *)
 670   | [&lt; 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" &gt;] -&gt; e
 671
 672   (* identifierexpr
 673    *   ::= identifier
 674    *   ::= identifier '(' argumentexpr ')' *)
 675   | [&lt; 'Token.Ident id; stream &gt;] -&gt;
 676       let rec parse_args accumulator = parser
 677         | [&lt; e=parse_expr; stream &gt;] -&gt;
 678             begin parser
 679               | [&lt; 'Token.Kwd ','; e=parse_args (e :: accumulator) &gt;] -&gt; e
 680               | [&lt; &gt;] -&gt; e :: accumulator
 681             end stream
 682         | [&lt; &gt;] -&gt; accumulator
 683       in
 684       let rec parse_ident id = parser
 685         (* Call. *)
 686         | [&lt; 'Token.Kwd '(';
 687              args=parse_args [];
 688              'Token.Kwd ')' ?? "expected ')'"&gt;] -&gt;
 689             Ast.Call (id, Array.of_list (List.rev args))
 690
 691         (* Simple variable ref. *)
 692         | [&lt; &gt;] -&gt; Ast.Variable id
 693       in
 694       parse_ident id stream
 695
 696   | [&lt; &gt;] -&gt; raise (Stream.Error "unknown token when expecting an expression.")
 697
 698 (* binoprhs
 699  *   ::= ('+' primary)* *)
 700 and parse_bin_rhs expr_prec lhs stream =
 701   match Stream.peek stream with
 702   (* If this is a binop, find its precedence. *)
 703   | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c -&gt;
 704       let token_prec = precedence c in
 705
 706       (* If this is a binop that binds at least as tightly as the current binop,
 707        * consume it, otherwise we are done. *)
 708       if token_prec &lt; expr_prec then lhs else begin
 709         (* Eat the binop. *)
 710         Stream.junk stream;
 711
 712         (* Parse the primary expression after the binary operator. *)
 713         let rhs = parse_primary stream in
 714
 715         (* Okay, we know this is a binop. *)
 716         let rhs =
 717           match Stream.peek stream with
 718           | Some (Token.Kwd c2) -&gt;
 719               (* If BinOp binds less tightly with rhs than the operator after
 720                * rhs, let the pending operator take rhs as its lhs. *)
 721               let next_prec = precedence c2 in
 722               if token_prec &lt; next_prec
 723               then parse_bin_rhs (token_prec + 1) rhs stream
 724               else rhs
 725           | _ -&gt; rhs
 726         in
 727
 728         (* Merge lhs/rhs. *)
 729         let lhs = Ast.Binary (c, lhs, rhs) in
 730         parse_bin_rhs expr_prec lhs stream
 731       end
 732   | _ -&gt; lhs
 733
 734 (* expression
 735  *   ::= primary binoprhs *)
 736 and parse_expr = parser
 737   | [&lt; lhs=parse_primary; stream &gt;] -&gt; parse_bin_rhs 0 lhs stream
 738
 739 (* prototype
 740  *   ::= id '(' id* ')' *)
 741 let parse_prototype =
 742   let rec parse_args accumulator = parser
 743     | [&lt; 'Token.Ident id; e=parse_args (id::accumulator) &gt;] -&gt; e
 744     | [&lt; &gt;] -&gt; accumulator
 745   in
 746
 747   parser
 748   | [&lt; 'Token.Ident id;
 749        'Token.Kwd '(' ?? "expected '(' in prototype";
 750        args=parse_args [];
 751        'Token.Kwd ')' ?? "expected ')' in prototype" &gt;] -&gt;
 752       (* success. *)
 753       Ast.Prototype (id, Array.of_list (List.rev args))
 754
 755   | [&lt; &gt;] -&gt;
 756       raise (Stream.Error "expected function name in prototype")
 757
 758 (* definition ::= 'def' prototype expression *)
 759 let parse_definition = parser
 760   | [&lt; 'Token.Def; p=parse_prototype; e=parse_expr &gt;] -&gt;
 761       Ast.Function (p, e)
 762
 763 (* toplevelexpr ::= expression *)
 764 let parse_toplevel = parser
 765   | [&lt; e=parse_expr &gt;] -&gt;
 766       (* Make an anonymous proto. *)
 767       Ast.Function (Ast.Prototype ("", [||]), e)
 768
 769 (*  external ::= 'extern' prototype *)
 770 let parse_extern = parser
 771   | [&lt; 'Token.Extern; e=parse_prototype &gt;] -&gt; e
 772 </pre>
 773 </dd>
 774
 775 <dt>codegen.ml:</dt>
 776 <dd class="doc_code">
 777 <pre>
 778 (*===----------------------------------------------------------------------===
 779  * Code Generation
 780  *===----------------------------------------------------------------------===*)
 781
 782 open Llvm
 783
 784 exception Error of string
 785
 786 let context = global_context ()
 787 let the_module = create_module context "my cool jit"
 788 let builder = builder context
 789 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
 790 let double_type = double_type context
 791
 792 let rec codegen_expr = function
 793   | Ast.Number n -&gt; const_float double_type n
 794   | Ast.Variable name -&gt;
 795       (try Hashtbl.find named_values name with
 796         | Not_found -&gt; raise (Error "unknown variable name"))
 797   | Ast.Binary (op, lhs, rhs) -&gt;
 798       let lhs_val = codegen_expr lhs in
 799       let rhs_val = codegen_expr rhs in
 800       begin
 801         match op with
 802         | '+' -&gt; build_add lhs_val rhs_val "addtmp" builder
 803         | '-' -&gt; build_sub lhs_val rhs_val "subtmp" builder
 804         | '*' -&gt; build_mul lhs_val rhs_val "multmp" builder
 805         | '&lt;' -&gt;
 806             (* Convert bool 0/1 to double 0.0 or 1.0 *)
 807             let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
 808             build_uitofp i double_type "booltmp" builder
 809         | _ -&gt; raise (Error "invalid binary operator")
 810       end
 811   | Ast.Call (callee, args) -&gt;
 812       (* Look up the name in the module table. *)
 813       let callee =
 814         match lookup_function callee the_module with
 815         | Some callee -&gt; callee
 816         | None -&gt; raise (Error "unknown function referenced")
 817       in
 818       let params = params callee in
 819
 820       (* If argument mismatch error. *)
 821       if Array.length params == Array.length args then () else
 822         raise (Error "incorrect # arguments passed");
 823       let args = Array.map codegen_expr args in
 824       build_call callee args "calltmp" builder
 825
 826 let codegen_proto = function
 827   | Ast.Prototype (name, args) -&gt;
 828       (* Make the function type: double(double,double) etc. *)
 829       let doubles = Array.make (Array.length args) double_type in
 830       let ft = function_type double_type doubles in
 831       let f =
 832         match lookup_function name the_module with
 833         | None -&gt; declare_function name ft the_module
 834
 835         (* If 'f' conflicted, there was already something named 'name'. If it
 836          * has a body, don't allow redefinition or reextern. *)
 837         | Some f -&gt;
 838             (* If 'f' already has a body, reject this. *)
 839             if block_begin f &lt;&gt; At_end f then
 840               raise (Error "redefinition of function");
 841
 842             (* If 'f' took a different number of arguments, reject. *)
 843             if element_type (type_of f) &lt;&gt; ft then
 844               raise (Error "redefinition of function with different # args");
 845             f
 846       in
 847
 848       (* Set names for all arguments. *)
 849       Array.iteri (fun i a -&gt;
 850         let n = args.(i) in
 851         set_value_name n a;
 852         Hashtbl.add named_values n a;
 853       ) (params f);
 854       f
 855
 856 let codegen_func the_fpm = function
 857   | Ast.Function (proto, body) -&gt;
 858       Hashtbl.clear named_values;
 859       let the_function = codegen_proto proto in
 860
 861       (* Create a new basic block to start insertion into. *)
 862       let bb = append_block context "entry" the_function in
 863       position_at_end bb builder;
 864
 865       try
 866         let ret_val = codegen_expr body in
 867
 868         (* Finish off the function. *)
 869         let _ = build_ret ret_val builder in
 870
 871         (* Validate the generated code, checking for consistency. *)
 872         Llvm_analysis.assert_valid_function the_function;
 873
 874         (* Optimize the function. *)
 875         let _ = PassManager.run_function the_function the_fpm in
 876
 877         the_function
 878       with e -&gt;
 879         delete_function the_function;
 880         raise e
 881 </pre>
 882 </dd>
 883
 884 <dt>toplevel.ml:</dt>
 885 <dd class="doc_code">
 886 <pre>
 887 (*===----------------------------------------------------------------------===
 888  * Top-Level parsing and JIT Driver
 889  *===----------------------------------------------------------------------===*)
 890
 891 open Llvm
 892 open Llvm_executionengine
 893
 894 (* top ::= definition | external | expression | ';' *)
 895 let rec main_loop the_fpm the_execution_engine stream =
 896   match Stream.peek stream with
 897   | None -&gt; ()
 898
 899   (* ignore top-level semicolons. *)
 900   | Some (Token.Kwd ';') -&gt;
 901       Stream.junk stream;
 902       main_loop the_fpm the_execution_engine stream
 903
 904   | Some token -&gt;
 905       begin
 906         try match token with
 907         | Token.Def -&gt;
 908             let e = Parser.parse_definition stream in
 909             print_endline "parsed a function definition.";
 910             dump_value (Codegen.codegen_func the_fpm e);
 911         | Token.Extern -&gt;
 912             let e = Parser.parse_extern stream in
 913             print_endline "parsed an extern.";
 914             dump_value (Codegen.codegen_proto e);
 915         | _ -&gt;
 916             (* Evaluate a top-level expression into an anonymous function. *)
 917             let e = Parser.parse_toplevel stream in
 918             print_endline "parsed a top-level expr";
 919             let the_function = Codegen.codegen_func the_fpm e in
 920             dump_value the_function;
 921
 922             (* JIT the function, returning a function pointer. *)
 923             let result = ExecutionEngine.run_function the_function [||]
 924               the_execution_engine in
 925
 926             print_string "Evaluated to ";
 927             print_float (GenericValue.as_float Codegen.double_type result);
 928             print_newline ();
 929         with Stream.Error s | Codegen.Error s -&gt;
 930           (* Skip token for error recovery. *)
 931           Stream.junk stream;
 932           print_endline s;
 933       end;
 934       print_string "ready&gt; "; flush stdout;
 935       main_loop the_fpm the_execution_engine stream
 936 </pre>
 937 </dd>
 938
 939 <dt>toy.ml:</dt>
 940 <dd class="doc_code">
 941 <pre>
 942 (*===----------------------------------------------------------------------===
 943  * Main driver code.
 944  *===----------------------------------------------------------------------===*)
 945
 946 open Llvm
 947 open Llvm_executionengine
 948 open Llvm_target
 949 open Llvm_scalar_opts
 950
 951 let main () =
 952   ignore (initialize_native_target ());
 953
 954   (* Install standard binary operators.
 955    * 1 is the lowest precedence. *)
 956   Hashtbl.add Parser.binop_precedence '&lt;' 10;
 957   Hashtbl.add Parser.binop_precedence '+' 20;
 958   Hashtbl.add Parser.binop_precedence '-' 20;
 959   Hashtbl.add Parser.binop_precedence '*' 40;    (* highest. *)
 960
 961   (* Prime the first token. *)
 962   print_string "ready&gt; "; flush stdout;
 963   let stream = Lexer.lex (Stream.of_channel stdin) in
 964
 965   (* Create the JIT. *)
 966   let the_execution_engine = ExecutionEngine.create Codegen.the_module in
 967   let the_fpm = PassManager.create_function Codegen.the_module in
 968
 969   (* Set up the optimizer pipeline.  Start with registering info about how the
 970    * target lays out data structures. *)
 971   TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
 972
 973   (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
 974   add_instruction_combination the_fpm;
 975
 976   (* reassociate expressions. *)
 977   add_reassociation the_fpm;
 978
 979   (* Eliminate Common SubExpressions. *)
 980   add_gvn the_fpm;
 981
 982   (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
 983   add_cfg_simplification the_fpm;
 984
 985   ignore (PassManager.initialize the_fpm);
 986
 987   (* Run the main "interpreter loop" now. *)
 988   Toplevel.main_loop the_fpm the_execution_engine stream;
 989
 990   (* Print out all the generated code. *)
 991   dump_module Codegen.the_module
 992 ;;
 993
 994 main ()
 995 </pre>
 996 </dd>
 997
 998 <dt>bindings.c</dt>
 999 <dd class="doc_code">
1000 <pre>
1001 #include &lt;stdio.h&gt;
1002
1003 /* putchard - putchar that takes a double and returns 0. */
1004 extern double putchard(double X) {
1005   putchar((char)X);
1006   return 0;
1007 }
1008 </pre>
1009 </dd>
1010 </dl>
1011
1012 <a href="OCamlLangImpl5.html">Next: Extending the language: control flow</a>
1013 </div>
1014
1015 <!-- *********************************************************************** -->
1016 <hr>
1017 <address>
1018   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1019   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1020   <a href="http://validator.w3.org/check/referer"><img
1021   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1022
1023   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1024   <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br>
1025   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1026   Last modified: $Date$
1027 </address>
1028 </body>
1029 </html>