Home | History | Annotate | Download | only in tutorial
      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: Extending the Language: Mutable Variables / SSA
      7          construction</title>
      8   <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
      9   <meta name="author" content="Chris Lattner">
     10   <meta name="author" content="Erick Tryzelaar">
     11   <link rel="stylesheet" href="../llvm.css" type="text/css">
     12 </head>
     13 
     14 <body>
     15 
     16 <h1>Kaleidoscope: Extending the Language: Mutable Variables</h1>
     17 
     18 <ul>
     19 <li><a href="index.html">Up to Tutorial Index</a></li>
     20 <li>Chapter 7
     21   <ol>
     22     <li><a href="#intro">Chapter 7 Introduction</a></li>
     23     <li><a href="#why">Why is this a hard problem?</a></li>
     24     <li><a href="#memory">Memory in LLVM</a></li>
     25     <li><a href="#kalvars">Mutable Variables in Kaleidoscope</a></li>
     26     <li><a href="#adjustments">Adjusting Existing Variables for
     27      Mutation</a></li>
     28     <li><a href="#assignment">New Assignment Operator</a></li>
     29     <li><a href="#localvars">User-defined Local Variables</a></li>
     30     <li><a href="#code">Full Code Listing</a></li>
     31   </ol>
     32 </li>
     33 <li><a href="OCamlLangImpl8.html">Chapter 8</a>: Conclusion and other useful LLVM
     34  tidbits</li>
     35 </ul>
     36 
     37 <div class="doc_author">
     38 	<p>
     39 		Written by <a href="mailto:sabre (a] nondot.org">Chris Lattner</a>
     40 		and <a href="mailto:idadesub (a] users.sourceforge.net">Erick Tryzelaar</a>
     41 	</p>
     42 </div>
     43 
     44 <!-- *********************************************************************** -->
     45 <h2><a name="intro">Chapter 7 Introduction</a></h2>
     46 <!-- *********************************************************************** -->
     47 
     48 <div>
     49 
     50 <p>Welcome to Chapter 7 of the "<a href="index.html">Implementing a language
     51 with LLVM</a>" tutorial.  In chapters 1 through 6, we've built a very
     52 respectable, albeit simple, <a
     53 href="http://en.wikipedia.org/wiki/Functional_programming">functional
     54 programming language</a>.  In our journey, we learned some parsing techniques,
     55 how to build and represent an AST, how to build LLVM IR, and how to optimize
     56 the resultant code as well as JIT compile it.</p>
     57 
     58 <p>While Kaleidoscope is interesting as a functional language, the fact that it
     59 is functional makes it "too easy" to generate LLVM IR for it.  In particular, a
     60 functional language makes it very easy to build LLVM IR directly in <a
     61 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">SSA form</a>.
     62 Since LLVM requires that the input code be in SSA form, this is a very nice
     63 property and it is often unclear to newcomers how to generate code for an
     64 imperative language with mutable variables.</p>
     65 
     66 <p>The short (and happy) summary of this chapter is that there is no need for
     67 your front-end to build SSA form: LLVM provides highly tuned and well tested
     68 support for this, though the way it works is a bit unexpected for some.</p>
     69 
     70 </div>
     71 
     72 <!-- *********************************************************************** -->
     73 <h2><a name="why">Why is this a hard problem?</a></h2>
     74 <!-- *********************************************************************** -->
     75 
     76 <div>
     77 
     78 <p>
     79 To understand why mutable variables cause complexities in SSA construction,
     80 consider this extremely simple C example:
     81 </p>
     82 
     83 <div class="doc_code">
     84 <pre>
     85 int G, H;
     86 int test(_Bool Condition) {
     87   int X;
     88   if (Condition)
     89     X = G;
     90   else
     91     X = H;
     92   return X;
     93 }
     94 </pre>
     95 </div>
     96 
     97 <p>In this case, we have the variable "X", whose value depends on the path
     98 executed in the program.  Because there are two different possible values for X
     99 before the return instruction, a PHI node is inserted to merge the two values.
    100 The LLVM IR that we want for this example looks like this:</p>
    101 
    102 <div class="doc_code">
    103 <pre>
    104 @G = weak global i32 0   ; type of @G is i32*
    105 @H = weak global i32 0   ; type of @H is i32*
    106 
    107 define i32 @test(i1 %Condition) {
    108 entry:
    109   br i1 %Condition, label %cond_true, label %cond_false
    110 
    111 cond_true:
    112   %X.0 = load i32* @G
    113   br label %cond_next
    114 
    115 cond_false:
    116   %X.1 = load i32* @H
    117   br label %cond_next
    118 
    119 cond_next:
    120   %X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
    121   ret i32 %X.2
    122 }
    123 </pre>
    124 </div>
    125 
    126 <p>In this example, the loads from the G and H global variables are explicit in
    127 the LLVM IR, and they live in the then/else branches of the if statement
    128 (cond_true/cond_false).  In order to merge the incoming values, the X.2 phi node
    129 in the cond_next block selects the right value to use based on where control
    130 flow is coming from: if control flow comes from the cond_false block, X.2 gets
    131 the value of X.1.  Alternatively, if control flow comes from cond_true, it gets
    132 the value of X.0.  The intent of this chapter is not to explain the details of
    133 SSA form.  For more information, see one of the many <a
    134 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">online
    135 references</a>.</p>
    136 
    137 <p>The question for this article is "who places the phi nodes when lowering
    138 assignments to mutable variables?".  The issue here is that LLVM
    139 <em>requires</em> that its IR be in SSA form: there is no "non-ssa" mode for it.
    140 However, SSA construction requires non-trivial algorithms and data structures,
    141 so it is inconvenient and wasteful for every front-end to have to reproduce this
    142 logic.</p>
    143 
    144 </div>
    145 
    146 <!-- *********************************************************************** -->
    147 <h2><a name="memory">Memory in LLVM</a></h2>
    148 <!-- *********************************************************************** -->
    149 
    150 <div>
    151 
    152 <p>The 'trick' here is that while LLVM does require all register values to be
    153 in SSA form, it does not require (or permit) memory objects to be in SSA form.
    154 In the example above, note that the loads from G and H are direct accesses to
    155 G and H: they are not renamed or versioned.  This differs from some other
    156 compiler systems, which do try to version memory objects.  In LLVM, instead of
    157 encoding dataflow analysis of memory into the LLVM IR, it is handled with <a
    158 href="../WritingAnLLVMPass.html">Analysis Passes</a> which are computed on
    159 demand.</p>
    160 
    161 <p>
    162 With this in mind, the high-level idea is that we want to make a stack variable
    163 (which lives in memory, because it is on the stack) for each mutable object in
    164 a function.  To take advantage of this trick, we need to talk about how LLVM
    165 represents stack variables.
    166 </p>
    167 
    168 <p>In LLVM, all memory accesses are explicit with load/store instructions, and
    169 it is carefully designed not to have (or need) an "address-of" operator.  Notice
    170 how the type of the @G/@H global variables is actually "i32*" even though the
    171 variable is defined as "i32".  What this means is that @G defines <em>space</em>
    172 for an i32 in the global data area, but its <em>name</em> actually refers to the
    173 address for that space.  Stack variables work the same way, except that instead of
    174 being declared with global variable definitions, they are declared with the
    175 <a href="../LangRef.html#i_alloca">LLVM alloca instruction</a>:</p>
    176 
    177 <div class="doc_code">
    178 <pre>
    179 define i32 @example() {
    180 entry:
    181   %X = alloca i32           ; type of %X is i32*.
    182   ...
    183   %tmp = load i32* %X       ; load the stack value %X from the stack.
    184   %tmp2 = add i32 %tmp, 1   ; increment it
    185   store i32 %tmp2, i32* %X  ; store it back
    186   ...
    187 </pre>
    188 </div>
    189 
    190 <p>This code shows an example of how you can declare and manipulate a stack
    191 variable in the LLVM IR.  Stack memory allocated with the alloca instruction is
    192 fully general: you can pass the address of the stack slot to functions, you can
    193 store it in other variables, etc.  In our example above, we could rewrite the
    194 example to use the alloca technique to avoid using a PHI node:</p>
    195 
    196 <div class="doc_code">
    197 <pre>
    198 @G = weak global i32 0   ; type of @G is i32*
    199 @H = weak global i32 0   ; type of @H is i32*
    200 
    201 define i32 @test(i1 %Condition) {
    202 entry:
    203   %X = alloca i32           ; type of %X is i32*.
    204   br i1 %Condition, label %cond_true, label %cond_false
    205 
    206 cond_true:
    207   %X.0 = load i32* @G
    208         store i32 %X.0, i32* %X   ; Update X
    209   br label %cond_next
    210 
    211 cond_false:
    212   %X.1 = load i32* @H
    213         store i32 %X.1, i32* %X   ; Update X
    214   br label %cond_next
    215 
    216 cond_next:
    217   %X.2 = load i32* %X       ; Read X
    218   ret i32 %X.2
    219 }
    220 </pre>
    221 </div>
    222 
    223 <p>With this, we have discovered a way to handle arbitrary mutable variables
    224 without the need to create Phi nodes at all:</p>
    225 
    226 <ol>
    227 <li>Each mutable variable becomes a stack allocation.</li>
    228 <li>Each read of the variable becomes a load from the stack.</li>
    229 <li>Each update of the variable becomes a store to the stack.</li>
    230 <li>Taking the address of a variable just uses the stack address directly.</li>
    231 </ol>
    232 
    233 <p>While this solution has solved our immediate problem, it introduced another
    234 one: we have now apparently introduced a lot of stack traffic for very simple
    235 and common operations, a major performance problem.  Fortunately for us, the
    236 LLVM optimizer has a highly-tuned optimization pass named "mem2reg" that handles
    237 this case, promoting allocas like this into SSA registers, inserting Phi nodes
    238 as appropriate.  If you run this example through the pass, for example, you'll
    239 get:</p>
    240 
    241 <div class="doc_code">
    242 <pre>
    243 $ <b>llvm-as &lt; example.ll | opt -mem2reg | llvm-dis</b>
    244 @G = weak global i32 0
    245 @H = weak global i32 0
    246 
    247 define i32 @test(i1 %Condition) {
    248 entry:
    249   br i1 %Condition, label %cond_true, label %cond_false
    250 
    251 cond_true:
    252   %X.0 = load i32* @G
    253   br label %cond_next
    254 
    255 cond_false:
    256   %X.1 = load i32* @H
    257   br label %cond_next
    258 
    259 cond_next:
    260   %X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
    261   ret i32 %X.01
    262 }
    263 </pre>
    264 </div>
    265 
    266 <p>The mem2reg pass implements the standard "iterated dominance frontier"
    267 algorithm for constructing SSA form and has a number of optimizations that speed
    268 up (very common) degenerate cases. The mem2reg optimization pass is the answer
    269 to dealing with mutable variables, and we highly recommend that you depend on
    270 it.  Note that mem2reg only works on variables in certain circumstances:</p>
    271 
    272 <ol>
    273 <li>mem2reg is alloca-driven: it looks for allocas and if it can handle them, it
    274 promotes them.  It does not apply to global variables or heap allocations.</li>
    275 
    276 <li>mem2reg only looks for alloca instructions in the entry block of the
    277 function.  Being in the entry block guarantees that the alloca is only executed
    278 once, which makes analysis simpler.</li>
    279 
    280 <li>mem2reg only promotes allocas whose uses are direct loads and stores.  If
    281 the address of the stack object is passed to a function, or if any funny pointer
    282 arithmetic is involved, the alloca will not be promoted.</li>
    283 
    284 <li>mem2reg only works on allocas of <a
    285 href="../LangRef.html#t_classifications">first class</a>
    286 values (such as pointers, scalars and vectors), and only if the array size
    287 of the allocation is 1 (or missing in the .ll file).  mem2reg is not capable of
    288 promoting structs or arrays to registers.  Note that the "scalarrepl" pass is
    289 more powerful and can promote structs, "unions", and arrays in many cases.</li>
    290 
    291 </ol>
    292 
    293 <p>
    294 All of these properties are easy to satisfy for most imperative languages, and
    295 we'll illustrate it below with Kaleidoscope.  The final question you may be
    296 asking is: should I bother with this nonsense for my front-end?  Wouldn't it be
    297 better if I just did SSA construction directly, avoiding use of the mem2reg
    298 optimization pass?  In short, we strongly recommend that you use this technique
    299 for building SSA form, unless there is an extremely good reason not to.  Using
    300 this technique is:</p>
    301 
    302 <ul>
    303 <li>Proven and well tested: llvm-gcc and clang both use this technique for local
    304 mutable variables.  As such, the most common clients of LLVM are using this to
    305 handle a bulk of their variables.  You can be sure that bugs are found fast and
    306 fixed early.</li>
    307 
    308 <li>Extremely Fast: mem2reg has a number of special cases that make it fast in
    309 common cases as well as fully general.  For example, it has fast-paths for
    310 variables that are only used in a single block, variables that only have one
    311 assignment point, good heuristics to avoid insertion of unneeded phi nodes, etc.
    312 </li>
    313 
    314 <li>Needed for debug info generation: <a href="../SourceLevelDebugging.html">
    315 Debug information in LLVM</a> relies on having the address of the variable
    316 exposed so that debug info can be attached to it.  This technique dovetails
    317 very naturally with this style of debug info.</li>
    318 </ul>
    319 
    320 <p>If nothing else, this makes it much easier to get your front-end up and
    321 running, and is very simple to implement.  Lets extend Kaleidoscope with mutable
    322 variables now!
    323 </p>
    324 
    325 </div>
    326 
    327 <!-- *********************************************************************** -->
    328 <h2><a name="kalvars">Mutable Variables in Kaleidoscope</a></h2>
    329 <!-- *********************************************************************** -->
    330 
    331 <div>
    332 
    333 <p>Now that we know the sort of problem we want to tackle, lets see what this
    334 looks like in the context of our little Kaleidoscope language.  We're going to
    335 add two features:</p>
    336 
    337 <ol>
    338 <li>The ability to mutate variables with the '=' operator.</li>
    339 <li>The ability to define new variables.</li>
    340 </ol>
    341 
    342 <p>While the first item is really what this is about, we only have variables
    343 for incoming arguments as well as for induction variables, and redefining those only
    344 goes so far :).  Also, the ability to define new variables is a
    345 useful thing regardless of whether you will be mutating them.  Here's a
    346 motivating example that shows how we could use these:</p>
    347 
    348 <div class="doc_code">
    349 <pre>
    350 # Define ':' for sequencing: as a low-precedence operator that ignores operands
    351 # and just returns the RHS.
    352 def binary : 1 (x y) y;
    353 
    354 # Recursive fib, we could do this before.
    355 def fib(x)
    356   if (x &lt; 3) then
    357     1
    358   else
    359     fib(x-1)+fib(x-2);
    360 
    361 # Iterative fib.
    362 def fibi(x)
    363   <b>var a = 1, b = 1, c in</b>
    364   (for i = 3, i &lt; x in
    365      <b>c = a + b</b> :
    366      <b>a = b</b> :
    367      <b>b = c</b>) :
    368   b;
    369 
    370 # Call it.
    371 fibi(10);
    372 </pre>
    373 </div>
    374 
    375 <p>
    376 In order to mutate variables, we have to change our existing variables to use
    377 the "alloca trick".  Once we have that, we'll add our new operator, then extend
    378 Kaleidoscope to support new variable definitions.
    379 </p>
    380 
    381 </div>
    382 
    383 <!-- *********************************************************************** -->
    384 <h2><a name="adjustments">Adjusting Existing Variables for Mutation</a></h2>
    385 <!-- *********************************************************************** -->
    386 
    387 <div>
    388 
    389 <p>
    390 The symbol table in Kaleidoscope is managed at code generation time by the
    391 '<tt>named_values</tt>' map.  This map currently keeps track of the LLVM
    392 "Value*" that holds the double value for the named variable.  In order to
    393 support mutation, we need to change this slightly, so that it
    394 <tt>named_values</tt> holds the <em>memory location</em> of the variable in
    395 question.  Note that this change is a refactoring: it changes the structure of
    396 the code, but does not (by itself) change the behavior of the compiler.  All of
    397 these changes are isolated in the Kaleidoscope code generator.</p>
    398 
    399 <p>
    400 At this point in Kaleidoscope's development, it only supports variables for two
    401 things: incoming arguments to functions and the induction variable of 'for'
    402 loops.  For consistency, we'll allow mutation of these variables in addition to
    403 other user-defined variables.  This means that these will both need memory
    404 locations.
    405 </p>
    406 
    407 <p>To start our transformation of Kaleidoscope, we'll change the
    408 <tt>named_values</tt> map so that it maps to AllocaInst* instead of Value*.
    409 Once we do this, the C++ compiler will tell us what parts of the code we need to
    410 update:</p>
    411 
    412 <p><b>Note:</b> the ocaml bindings currently model both <tt>Value*</tt>s and
    413 <tt>AllocInst*</tt>s as <tt>Llvm.llvalue</tt>s, but this may change in the
    414 future to be more type safe.</p>
    415 
    416 <div class="doc_code">
    417 <pre>
    418 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
    419 </pre>
    420 </div>
    421 
    422 <p>Also, since we will need to create these alloca's, we'll use a helper
    423 function that ensures that the allocas are created in the entry block of the
    424 function:</p>
    425 
    426 <div class="doc_code">
    427 <pre>
    428 (* Create an alloca instruction in the entry block of the function. This
    429  * is used for mutable variables etc. *)
    430 let create_entry_block_alloca the_function var_name =
    431   let builder = builder_at (instr_begin (entry_block the_function)) in
    432   build_alloca double_type var_name builder
    433 </pre>
    434 </div>
    435 
    436 <p>This funny looking code creates an <tt>Llvm.llbuilder</tt> object that is
    437 pointing at the first instruction of the entry block.  It then creates an alloca
    438 with the expected name and returns it.  Because all values in Kaleidoscope are
    439 doubles, there is no need to pass in a type to use.</p>
    440 
    441 <p>With this in place, the first functionality change we want to make is to
    442 variable references.  In our new scheme, variables live on the stack, so code
    443 generating a reference to them actually needs to produce a load from the stack
    444 slot:</p>
    445 
    446 <div class="doc_code">
    447 <pre>
    448 let rec codegen_expr = function
    449   ...
    450   | Ast.Variable name -&gt;
    451       let v = try Hashtbl.find named_values name with
    452         | Not_found -&gt; raise (Error "unknown variable name")
    453       in
    454       <b>(* Load the value. *)
    455       build_load v name builder</b>
    456 </pre>
    457 </div>
    458 
    459 <p>As you can see, this is pretty straightforward.  Now we need to update the
    460 things that define the variables to set up the alloca.  We'll start with
    461 <tt>codegen_expr Ast.For ...</tt> (see the <a href="#code">full code listing</a>
    462 for the unabridged code):</p>
    463 
    464 <div class="doc_code">
    465 <pre>
    466   | Ast.For (var_name, start, end_, step, body) -&gt;
    467       let the_function = block_parent (insertion_block builder) in
    468 
    469       (* Create an alloca for the variable in the entry block. *)
    470       <b>let alloca = create_entry_block_alloca the_function var_name in</b>
    471 
    472       (* Emit the start code first, without 'variable' in scope. *)
    473       let start_val = codegen_expr start in
    474 
    475       <b>(* Store the value into the alloca. *)
    476       ignore(build_store start_val alloca builder);</b>
    477 
    478       ...
    479 
    480       (* Within the loop, the variable is defined equal to the PHI node. If it
    481        * shadows an existing variable, we have to restore it, so save it
    482        * now. *)
    483       let old_val =
    484         try Some (Hashtbl.find named_values var_name) with Not_found -&gt; None
    485       in
    486       <b>Hashtbl.add named_values var_name alloca;</b>
    487 
    488       ...
    489 
    490       (* Compute the end condition. *)
    491       let end_cond = codegen_expr end_ in
    492 
    493       <b>(* Reload, increment, and restore the alloca. This handles the case where
    494        * the body of the loop mutates the variable. *)
    495       let cur_var = build_load alloca var_name builder in
    496       let next_var = build_add cur_var step_val "nextvar" builder in
    497       ignore(build_store next_var alloca builder);</b>
    498       ...
    499 </pre>
    500 </div>
    501 
    502 <p>This code is virtually identical to the code <a
    503 href="OCamlLangImpl5.html#forcodegen">before we allowed mutable variables</a>.
    504 The big difference is that we no longer have to construct a PHI node, and we use
    505 load/store to access the variable as needed.</p>
    506 
    507 <p>To support mutable argument variables, we need to also make allocas for them.
    508 The code for this is also pretty simple:</p>
    509 
    510 <div class="doc_code">
    511 <pre>
    512 (* Create an alloca for each argument and register the argument in the symbol
    513  * table so that references to it will succeed. *)
    514 let create_argument_allocas the_function proto =
    515   let args = match proto with
    516     | Ast.Prototype (_, args) | Ast.BinOpPrototype (_, args, _) -&gt; args
    517   in
    518   Array.iteri (fun i ai -&gt;
    519     let var_name = args.(i) in
    520     (* Create an alloca for this variable. *)
    521     let alloca = create_entry_block_alloca the_function var_name in
    522 
    523     (* Store the initial value into the alloca. *)
    524     ignore(build_store ai alloca builder);
    525 
    526     (* Add arguments to variable symbol table. *)
    527     Hashtbl.add named_values var_name alloca;
    528   ) (params the_function)
    529 </pre>
    530 </div>
    531 
    532 <p>For each argument, we make an alloca, store the input value to the function
    533 into the alloca, and register the alloca as the memory location for the
    534 argument.  This method gets invoked by <tt>Codegen.codegen_func</tt> right after
    535 it sets up the entry block for the function.</p>
    536 
    537 <p>The final missing piece is adding the mem2reg pass, which allows us to get
    538 good codegen once again:</p>
    539 
    540 <div class="doc_code">
    541 <pre>
    542 let main () =
    543   ...
    544   let the_fpm = PassManager.create_function Codegen.the_module in
    545 
    546   (* Set up the optimizer pipeline.  Start with registering info about how the
    547    * target lays out data structures. *)
    548   TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
    549 
    550   <b>(* Promote allocas to registers. *)
    551   add_memory_to_register_promotion the_fpm;</b>
    552 
    553   (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
    554   add_instruction_combining the_fpm;
    555 
    556   (* reassociate expressions. *)
    557   add_reassociation the_fpm;
    558 </pre>
    559 </div>
    560 
    561 <p>It is interesting to see what the code looks like before and after the
    562 mem2reg optimization runs.  For example, this is the before/after code for our
    563 recursive fib function.  Before the optimization:</p>
    564 
    565 <div class="doc_code">
    566 <pre>
    567 define double @fib(double %x) {
    568 entry:
    569   <b>%x1 = alloca double
    570   store double %x, double* %x1
    571   %x2 = load double* %x1</b>
    572   %cmptmp = fcmp ult double %x2, 3.000000e+00
    573   %booltmp = uitofp i1 %cmptmp to double
    574   %ifcond = fcmp one double %booltmp, 0.000000e+00
    575   br i1 %ifcond, label %then, label %else
    576 
    577 then:    ; preds = %entry
    578   br label %ifcont
    579 
    580 else:    ; preds = %entry
    581   <b>%x3 = load double* %x1</b>
    582   %subtmp = fsub double %x3, 1.000000e+00
    583   %calltmp = call double @fib(double %subtmp)
    584   <b>%x4 = load double* %x1</b>
    585   %subtmp5 = fsub double %x4, 2.000000e+00
    586   %calltmp6 = call double @fib(double %subtmp5)
    587   %addtmp = fadd double %calltmp, %calltmp6
    588   br label %ifcont
    589 
    590 ifcont:    ; preds = %else, %then
    591   %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
    592   ret double %iftmp
    593 }
    594 </pre>
    595 </div>
    596 
    597 <p>Here there is only one variable (x, the input argument) but you can still
    598 see the extremely simple-minded code generation strategy we are using.  In the
    599 entry block, an alloca is created, and the initial input value is stored into
    600 it.  Each reference to the variable does a reload from the stack.  Also, note
    601 that we didn't modify the if/then/else expression, so it still inserts a PHI
    602 node.  While we could make an alloca for it, it is actually easier to create a
    603 PHI node for it, so we still just make the PHI.</p>
    604 
    605 <p>Here is the code after the mem2reg pass runs:</p>
    606 
    607 <div class="doc_code">
    608 <pre>
    609 define double @fib(double %x) {
    610 entry:
    611   %cmptmp = fcmp ult double <b>%x</b>, 3.000000e+00
    612   %booltmp = uitofp i1 %cmptmp to double
    613   %ifcond = fcmp one double %booltmp, 0.000000e+00
    614   br i1 %ifcond, label %then, label %else
    615 
    616 then:
    617   br label %ifcont
    618 
    619 else:
    620   %subtmp = fsub double <b>%x</b>, 1.000000e+00
    621   %calltmp = call double @fib(double %subtmp)
    622   %subtmp5 = fsub double <b>%x</b>, 2.000000e+00
    623   %calltmp6 = call double @fib(double %subtmp5)
    624   %addtmp = fadd double %calltmp, %calltmp6
    625   br label %ifcont
    626 
    627 ifcont:    ; preds = %else, %then
    628   %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
    629   ret double %iftmp
    630 }
    631 </pre>
    632 </div>
    633 
    634 <p>This is a trivial case for mem2reg, since there are no redefinitions of the
    635 variable.  The point of showing this is to calm your tension about inserting
    636 such blatent inefficiencies :).</p>
    637 
    638 <p>After the rest of the optimizers run, we get:</p>
    639 
    640 <div class="doc_code">
    641 <pre>
    642 define double @fib(double %x) {
    643 entry:
    644   %cmptmp = fcmp ult double %x, 3.000000e+00
    645   %booltmp = uitofp i1 %cmptmp to double
    646   %ifcond = fcmp ueq double %booltmp, 0.000000e+00
    647   br i1 %ifcond, label %else, label %ifcont
    648 
    649 else:
    650   %subtmp = fsub double %x, 1.000000e+00
    651   %calltmp = call double @fib(double %subtmp)
    652   %subtmp5 = fsub double %x, 2.000000e+00
    653   %calltmp6 = call double @fib(double %subtmp5)
    654   %addtmp = fadd double %calltmp, %calltmp6
    655   ret double %addtmp
    656 
    657 ifcont:
    658   ret double 1.000000e+00
    659 }
    660 </pre>
    661 </div>
    662 
    663 <p>Here we see that the simplifycfg pass decided to clone the return instruction
    664 into the end of the 'else' block.  This allowed it to eliminate some branches
    665 and the PHI node.</p>
    666 
    667 <p>Now that all symbol table references are updated to use stack variables,
    668 we'll add the assignment operator.</p>
    669 
    670 </div>
    671 
    672 <!-- *********************************************************************** -->
    673 <h2><a name="assignment">New Assignment Operator</a></h2>
    674 <!-- *********************************************************************** -->
    675 
    676 <div>
    677 
    678 <p>With our current framework, adding a new assignment operator is really
    679 simple.  We will parse it just like any other binary operator, but handle it
    680 internally (instead of allowing the user to define it).  The first step is to
    681 set a precedence:</p>
    682 
    683 <div class="doc_code">
    684 <pre>
    685 let main () =
    686   (* Install standard binary operators.
    687    * 1 is the lowest precedence. *)
    688   <b>Hashtbl.add Parser.binop_precedence '=' 2;</b>
    689   Hashtbl.add Parser.binop_precedence '&lt;' 10;
    690   Hashtbl.add Parser.binop_precedence '+' 20;
    691   Hashtbl.add Parser.binop_precedence '-' 20;
    692   ...
    693 </pre>
    694 </div>
    695 
    696 <p>Now that the parser knows the precedence of the binary operator, it takes
    697 care of all the parsing and AST generation.  We just need to implement codegen
    698 for the assignment operator.  This looks like:</p>
    699 
    700 <div class="doc_code">
    701 <pre>
    702 let rec codegen_expr = function
    703       begin match op with
    704       | '=' -&gt;
    705           (* Special case '=' because we don't want to emit the LHS as an
    706            * expression. *)
    707           let name =
    708             match lhs with
    709             | Ast.Variable name -&gt; name
    710             | _ -&gt; raise (Error "destination of '=' must be a variable")
    711           in
    712 </pre>
    713 </div>
    714 
    715 <p>Unlike the rest of the binary operators, our assignment operator doesn't
    716 follow the "emit LHS, emit RHS, do computation" model.  As such, it is handled
    717 as a special case before the other binary operators are handled.  The other
    718 strange thing is that it requires the LHS to be a variable.  It is invalid to
    719 have "(x+1) = expr" - only things like "x = expr" are allowed.
    720 </p>
    721 
    722 
    723 <div class="doc_code">
    724 <pre>
    725           (* Codegen the rhs. *)
    726           let val_ = codegen_expr rhs in
    727 
    728           (* Lookup the name. *)
    729           let variable = try Hashtbl.find named_values name with
    730           | Not_found -&gt; raise (Error "unknown variable name")
    731           in
    732           ignore(build_store val_ variable builder);
    733           val_
    734       | _ -&gt;
    735 			...
    736 </pre>
    737 </div>
    738 
    739 <p>Once we have the variable, codegen'ing the assignment is straightforward:
    740 we emit the RHS of the assignment, create a store, and return the computed
    741 value.  Returning a value allows for chained assignments like "X = (Y = Z)".</p>
    742 
    743 <p>Now that we have an assignment operator, we can mutate loop variables and
    744 arguments.  For example, we can now run code like this:</p>
    745 
    746 <div class="doc_code">
    747 <pre>
    748 # Function to print a double.
    749 extern printd(x);
    750 
    751 # Define ':' for sequencing: as a low-precedence operator that ignores operands
    752 # and just returns the RHS.
    753 def binary : 1 (x y) y;
    754 
    755 def test(x)
    756   printd(x) :
    757   x = 4 :
    758   printd(x);
    759 
    760 test(123);
    761 </pre>
    762 </div>
    763 
    764 <p>When run, this example prints "123" and then "4", showing that we did
    765 actually mutate the value!  Okay, we have now officially implemented our goal:
    766 getting this to work requires SSA construction in the general case.  However,
    767 to be really useful, we want the ability to define our own local variables, lets
    768 add this next!
    769 </p>
    770 
    771 </div>
    772 
    773 <!-- *********************************************************************** -->
    774 <h2><a name="localvars">User-defined Local Variables</a></h2>
    775 <!-- *********************************************************************** -->
    776 
    777 <div>
    778 
    779 <p>Adding var/in is just like any other other extensions we made to
    780 Kaleidoscope: we extend the lexer, the parser, the AST and the code generator.
    781 The first step for adding our new 'var/in' construct is to extend the lexer.
    782 As before, this is pretty trivial, the code looks like this:</p>
    783 
    784 <div class="doc_code">
    785 <pre>
    786 type token =
    787   ...
    788   <b>(* var definition *)
    789   | Var</b>
    790 
    791 ...
    792 
    793 and lex_ident buffer = parser
    794       ...
    795       | "in" -&gt; [&lt; 'Token.In; stream &gt;]
    796       | "binary" -&gt; [&lt; 'Token.Binary; stream &gt;]
    797       | "unary" -&gt; [&lt; 'Token.Unary; stream &gt;]
    798       <b>| "var" -&gt; [&lt; 'Token.Var; stream &gt;]</b>
    799       ...
    800 </pre>
    801 </div>
    802 
    803 <p>The next step is to define the AST node that we will construct.  For var/in,
    804 it looks like this:</p>
    805 
    806 <div class="doc_code">
    807 <pre>
    808 type expr =
    809   ...
    810   (* variant for var/in. *)
    811   | Var of (string * expr option) array * expr
    812   ...
    813 </pre>
    814 </div>
    815 
    816 <p>var/in allows a list of names to be defined all at once, and each name can
    817 optionally have an initializer value.  As such, we capture this information in
    818 the VarNames vector.  Also, var/in has a body, this body is allowed to access
    819 the variables defined by the var/in.</p>
    820 
    821 <p>With this in place, we can define the parser pieces.  The first thing we do
    822 is add it as a primary expression:</p>
    823 
    824 <div class="doc_code">
    825 <pre>
    826 (* primary
    827  *   ::= identifier
    828  *   ::= numberexpr
    829  *   ::= parenexpr
    830  *   ::= ifexpr
    831  *   ::= forexpr
    832  <b>*   ::= varexpr</b> *)
    833 let rec parse_primary = parser
    834   ...
    835   <b>(* varexpr
    836    *   ::= 'var' identifier ('=' expression?
    837    *             (',' identifier ('=' expression)?)* 'in' expression *)
    838   | [&lt; 'Token.Var;
    839        (* At least one variable name is required. *)
    840        'Token.Ident id ?? "expected identifier after var";
    841        init=parse_var_init;
    842        var_names=parse_var_names [(id, init)];
    843        (* At this point, we have to have 'in'. *)
    844        'Token.In ?? "expected 'in' keyword after 'var'";
    845        body=parse_expr &gt;] -&gt;
    846       Ast.Var (Array.of_list (List.rev var_names), body)</b>
    847 
    848 ...
    849 
    850 and parse_var_init = parser
    851   (* read in the optional initializer. *)
    852   | [&lt; 'Token.Kwd '='; e=parse_expr &gt;] -&gt; Some e
    853   | [&lt; &gt;] -&gt; None
    854 
    855 and parse_var_names accumulator = parser
    856   | [&lt; 'Token.Kwd ',';
    857        'Token.Ident id ?? "expected identifier list after var";
    858        init=parse_var_init;
    859        e=parse_var_names ((id, init) :: accumulator) &gt;] -&gt; e
    860   | [&lt; &gt;] -&gt; accumulator
    861 </pre>
    862 </div>
    863 
    864 <p>Now that we can parse and represent the code, we need to support emission of
    865 LLVM IR for it.  This code starts out with:</p>
    866 
    867 <div class="doc_code">
    868 <pre>
    869 let rec codegen_expr = function
    870   ...
    871   | Ast.Var (var_names, body)
    872       let old_bindings = ref [] in
    873 
    874       let the_function = block_parent (insertion_block builder) in
    875 
    876       (* Register all variables and emit their initializer. *)
    877       Array.iter (fun (var_name, init) -&gt;
    878 </pre>
    879 </div>
    880 
    881 <p>Basically it loops over all the variables, installing them one at a time.
    882 For each variable we put into the symbol table, we remember the previous value
    883 that we replace in OldBindings.</p>
    884 
    885 <div class="doc_code">
    886 <pre>
    887         (* Emit the initializer before adding the variable to scope, this
    888          * prevents the initializer from referencing the variable itself, and
    889          * permits stuff like this:
    890          *   var a = 1 in
    891          *     var a = a in ...   # refers to outer 'a'. *)
    892         let init_val =
    893           match init with
    894           | Some init -&gt; codegen_expr init
    895           (* If not specified, use 0.0. *)
    896           | None -&gt; const_float double_type 0.0
    897         in
    898 
    899         let alloca = create_entry_block_alloca the_function var_name in
    900         ignore(build_store init_val alloca builder);
    901 
    902         (* Remember the old variable binding so that we can restore the binding
    903          * when we unrecurse. *)
    904 
    905         begin
    906           try
    907             let old_value = Hashtbl.find named_values var_name in
    908             old_bindings := (var_name, old_value) :: !old_bindings;
    909           with Not_found &gt; ()
    910         end;
    911 
    912         (* Remember this binding. *)
    913         Hashtbl.add named_values var_name alloca;
    914       ) var_names;
    915 </pre>
    916 </div>
    917 
    918 <p>There are more comments here than code.  The basic idea is that we emit the
    919 initializer, create the alloca, then update the symbol table to point to it.
    920 Once all the variables are installed in the symbol table, we evaluate the body
    921 of the var/in expression:</p>
    922 
    923 <div class="doc_code">
    924 <pre>
    925       (* Codegen the body, now that all vars are in scope. *)
    926       let body_val = codegen_expr body in
    927 </pre>
    928 </div>
    929 
    930 <p>Finally, before returning, we restore the previous variable bindings:</p>
    931 
    932 <div class="doc_code">
    933 <pre>
    934       (* Pop all our variables from scope. *)
    935       List.iter (fun (var_name, old_value) -&gt;
    936         Hashtbl.add named_values var_name old_value
    937       ) !old_bindings;
    938 
    939       (* Return the body computation. *)
    940       body_val
    941 </pre>
    942 </div>
    943 
    944 <p>The end result of all of this is that we get properly scoped variable
    945 definitions, and we even (trivially) allow mutation of them :).</p>
    946 
    947 <p>With this, we completed what we set out to do.  Our nice iterative fib
    948 example from the intro compiles and runs just fine.  The mem2reg pass optimizes
    949 all of our stack variables into SSA registers, inserting PHI nodes where needed,
    950 and our front-end remains simple: no "iterated dominance frontier" computation
    951 anywhere in sight.</p>
    952 
    953 </div>
    954 
    955 <!-- *********************************************************************** -->
    956 <h2><a name="code">Full Code Listing</a></h2>
    957 <!-- *********************************************************************** -->
    958 
    959 <div>
    960 
    961 <p>
    962 Here is the complete code listing for our running example, enhanced with mutable
    963 variables and var/in support.  To build this example, use:
    964 </p>
    965 
    966 <div class="doc_code">
    967 <pre>
    968 # Compile
    969 ocamlbuild toy.byte
    970 # Run
    971 ./toy.byte
    972 </pre>
    973 </div>
    974 
    975 <p>Here is the code:</p>
    976 
    977 <dl>
    978 <dt>_tags:</dt>
    979 <dd class="doc_code">
    980 <pre>
    981 &lt;{lexer,parser}.ml&gt;: use_camlp4, pp(camlp4of)
    982 &lt;*.{byte,native}&gt;: g++, use_llvm, use_llvm_analysis
    983 &lt;*.{byte,native}&gt;: use_llvm_executionengine, use_llvm_target
    984 &lt;*.{byte,native}&gt;: use_llvm_scalar_opts, use_bindings
    985 </pre>
    986 </dd>
    987 
    988 <dt>myocamlbuild.ml:</dt>
    989 <dd class="doc_code">
    990 <pre>
    991 open Ocamlbuild_plugin;;
    992 
    993 ocaml_lib ~extern:true "llvm";;
    994 ocaml_lib ~extern:true "llvm_analysis";;
    995 ocaml_lib ~extern:true "llvm_executionengine";;
    996 ocaml_lib ~extern:true "llvm_target";;
    997 ocaml_lib ~extern:true "llvm_scalar_opts";;
    998 
    999 flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"; A"-cclib"; A"-rdynamic"]);;
   1000 dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
   1001 </pre>
   1002 </dd>
   1003 
   1004 <dt>token.ml:</dt>
   1005 <dd class="doc_code">
   1006 <pre>
   1007 (*===----------------------------------------------------------------------===
   1008  * Lexer Tokens
   1009  *===----------------------------------------------------------------------===*)
   1010 
   1011 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
   1012  * these others for known things. *)
   1013 type token =
   1014   (* commands *)
   1015   | Def | Extern
   1016 
   1017   (* primary *)
   1018   | Ident of string | Number of float
   1019 
   1020   (* unknown *)
   1021   | Kwd of char
   1022 
   1023   (* control *)
   1024   | If | Then | Else
   1025   | For | In
   1026 
   1027   (* operators *)
   1028   | Binary | Unary
   1029 
   1030   (* var definition *)
   1031   | Var
   1032 </pre>
   1033 </dd>
   1034 
   1035 <dt>lexer.ml:</dt>
   1036 <dd class="doc_code">
   1037 <pre>
   1038 (*===----------------------------------------------------------------------===
   1039  * Lexer
   1040  *===----------------------------------------------------------------------===*)
   1041 
   1042 let rec lex = parser
   1043   (* Skip any whitespace. *)
   1044   | [&lt; ' (' ' | '\n' | '\r' | '\t'); stream &gt;] -&gt; lex stream
   1045 
   1046   (* identifier: [a-zA-Z][a-zA-Z0-9] *)
   1047   | [&lt; ' ('A' .. 'Z' | 'a' .. 'z' as c); stream &gt;] -&gt;
   1048       let buffer = Buffer.create 1 in
   1049       Buffer.add_char buffer c;
   1050       lex_ident buffer stream
   1051 
   1052   (* number: [0-9.]+ *)
   1053   | [&lt; ' ('0' .. '9' as c); stream &gt;] -&gt;
   1054       let buffer = Buffer.create 1 in
   1055       Buffer.add_char buffer c;
   1056       lex_number buffer stream
   1057 
   1058   (* Comment until end of line. *)
   1059   | [&lt; ' ('#'); stream &gt;] -&gt;
   1060       lex_comment stream
   1061 
   1062   (* Otherwise, just return the character as its ascii value. *)
   1063   | [&lt; 'c; stream &gt;] -&gt;
   1064       [&lt; 'Token.Kwd c; lex stream &gt;]
   1065 
   1066   (* end of stream. *)
   1067   | [&lt; &gt;] -&gt; [&lt; &gt;]
   1068 
   1069 and lex_number buffer = parser
   1070   | [&lt; ' ('0' .. '9' | '.' as c); stream &gt;] -&gt;
   1071       Buffer.add_char buffer c;
   1072       lex_number buffer stream
   1073   | [&lt; stream=lex &gt;] -&gt;
   1074       [&lt; 'Token.Number (float_of_string (Buffer.contents buffer)); stream &gt;]
   1075 
   1076 and lex_ident buffer = parser
   1077   | [&lt; ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream &gt;] -&gt;
   1078       Buffer.add_char buffer c;
   1079       lex_ident buffer stream
   1080   | [&lt; stream=lex &gt;] -&gt;
   1081       match Buffer.contents buffer with
   1082       | "def" -&gt; [&lt; 'Token.Def; stream &gt;]
   1083       | "extern" -&gt; [&lt; 'Token.Extern; stream &gt;]
   1084       | "if" -&gt; [&lt; 'Token.If; stream &gt;]
   1085       | "then" -&gt; [&lt; 'Token.Then; stream &gt;]
   1086       | "else" -&gt; [&lt; 'Token.Else; stream &gt;]
   1087       | "for" -&gt; [&lt; 'Token.For; stream &gt;]
   1088       | "in" -&gt; [&lt; 'Token.In; stream &gt;]
   1089       | "binary" -&gt; [&lt; 'Token.Binary; stream &gt;]
   1090       | "unary" -&gt; [&lt; 'Token.Unary; stream &gt;]
   1091       | "var" -&gt; [&lt; 'Token.Var; stream &gt;]
   1092       | id -&gt; [&lt; 'Token.Ident id; stream &gt;]
   1093 
   1094 and lex_comment = parser
   1095   | [&lt; ' ('\n'); stream=lex &gt;] -&gt; stream
   1096   | [&lt; 'c; e=lex_comment &gt;] -&gt; e
   1097   | [&lt; &gt;] -&gt; [&lt; &gt;]
   1098 </pre>
   1099 </dd>
   1100 
   1101 <dt>ast.ml:</dt>
   1102 <dd class="doc_code">
   1103 <pre>
   1104 (*===----------------------------------------------------------------------===
   1105  * Abstract Syntax Tree (aka Parse Tree)
   1106  *===----------------------------------------------------------------------===*)
   1107 
   1108 (* expr - Base type for all expression nodes. *)
   1109 type expr =
   1110   (* variant for numeric literals like "1.0". *)
   1111   | Number of float
   1112 
   1113   (* variant for referencing a variable, like "a". *)
   1114   | Variable of string
   1115 
   1116   (* variant for a unary operator. *)
   1117   | Unary of char * expr
   1118 
   1119   (* variant for a binary operator. *)
   1120   | Binary of char * expr * expr
   1121 
   1122   (* variant for function calls. *)
   1123   | Call of string * expr array
   1124 
   1125   (* variant for if/then/else. *)
   1126   | If of expr * expr * expr
   1127 
   1128   (* variant for for/in. *)
   1129   | For of string * expr * expr * expr option * expr
   1130 
   1131   (* variant for var/in. *)
   1132   | Var of (string * expr option) array * expr
   1133 
   1134 (* proto - This type represents the "prototype" for a function, which captures
   1135  * its name, and its argument names (thus implicitly the number of arguments the
   1136  * function takes). *)
   1137 type proto =
   1138   | Prototype of string * string array
   1139   | BinOpPrototype of string * string array * int
   1140 
   1141 (* func - This type represents a function definition itself. *)
   1142 type func = Function of proto * expr
   1143 </pre>
   1144 </dd>
   1145 
   1146 <dt>parser.ml:</dt>
   1147 <dd class="doc_code">
   1148 <pre>
   1149 (*===---------------------------------------------------------------------===
   1150  * Parser
   1151  *===---------------------------------------------------------------------===*)
   1152 
   1153 (* binop_precedence - This holds the precedence for each binary operator that is
   1154  * defined *)
   1155 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
   1156 
   1157 (* precedence - Get the precedence of the pending binary operator token. *)
   1158 let precedence c = try Hashtbl.find binop_precedence c with Not_found -&gt; -1
   1159 
   1160 (* primary
   1161  *   ::= identifier
   1162  *   ::= numberexpr
   1163  *   ::= parenexpr
   1164  *   ::= ifexpr
   1165  *   ::= forexpr
   1166  *   ::= varexpr *)
   1167 let rec parse_primary = parser
   1168   (* numberexpr ::= number *)
   1169   | [&lt; 'Token.Number n &gt;] -&gt; Ast.Number n
   1170 
   1171   (* parenexpr ::= '(' expression ')' *)
   1172   | [&lt; 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" &gt;] -&gt; e
   1173 
   1174   (* identifierexpr
   1175    *   ::= identifier
   1176    *   ::= identifier '(' argumentexpr ')' *)
   1177   | [&lt; 'Token.Ident id; stream &gt;] -&gt;
   1178       let rec parse_args accumulator = parser
   1179         | [&lt; e=parse_expr; stream &gt;] -&gt;
   1180             begin parser
   1181               | [&lt; 'Token.Kwd ','; e=parse_args (e :: accumulator) &gt;] -&gt; e
   1182               | [&lt; &gt;] -&gt; e :: accumulator
   1183             end stream
   1184         | [&lt; &gt;] -&gt; accumulator
   1185       in
   1186       let rec parse_ident id = parser
   1187         (* Call. *)
   1188         | [&lt; 'Token.Kwd '(';
   1189              args=parse_args [];
   1190              'Token.Kwd ')' ?? "expected ')'"&gt;] -&gt;
   1191             Ast.Call (id, Array.of_list (List.rev args))
   1192 
   1193         (* Simple variable ref. *)
   1194         | [&lt; &gt;] -&gt; Ast.Variable id
   1195       in
   1196       parse_ident id stream
   1197 
   1198   (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
   1199   | [&lt; 'Token.If; c=parse_expr;
   1200        'Token.Then ?? "expected 'then'"; t=parse_expr;
   1201        'Token.Else ?? "expected 'else'"; e=parse_expr &gt;] -&gt;
   1202       Ast.If (c, t, e)
   1203 
   1204   (* forexpr
   1205         ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
   1206   | [&lt; 'Token.For;
   1207        'Token.Ident id ?? "expected identifier after for";
   1208        'Token.Kwd '=' ?? "expected '=' after for";
   1209        stream &gt;] -&gt;
   1210       begin parser
   1211         | [&lt;
   1212              start=parse_expr;
   1213              'Token.Kwd ',' ?? "expected ',' after for";
   1214              end_=parse_expr;
   1215              stream &gt;] -&gt;
   1216             let step =
   1217               begin parser
   1218               | [&lt; 'Token.Kwd ','; step=parse_expr &gt;] -&gt; Some step
   1219               | [&lt; &gt;] -&gt; None
   1220               end stream
   1221             in
   1222             begin parser
   1223             | [&lt; 'Token.In; body=parse_expr &gt;] -&gt;
   1224                 Ast.For (id, start, end_, step, body)
   1225             | [&lt; &gt;] -&gt;
   1226                 raise (Stream.Error "expected 'in' after for")
   1227             end stream
   1228         | [&lt; &gt;] -&gt;
   1229             raise (Stream.Error "expected '=' after for")
   1230       end stream
   1231 
   1232   (* varexpr
   1233    *   ::= 'var' identifier ('=' expression?
   1234    *             (',' identifier ('=' expression)?)* 'in' expression *)
   1235   | [&lt; 'Token.Var;
   1236        (* At least one variable name is required. *)
   1237        'Token.Ident id ?? "expected identifier after var";
   1238        init=parse_var_init;
   1239        var_names=parse_var_names [(id, init)];
   1240        (* At this point, we have to have 'in'. *)
   1241        'Token.In ?? "expected 'in' keyword after 'var'";
   1242        body=parse_expr &gt;] -&gt;
   1243       Ast.Var (Array.of_list (List.rev var_names), body)
   1244 
   1245   | [&lt; &gt;] -&gt; raise (Stream.Error "unknown token when expecting an expression.")
   1246 
   1247 (* unary
   1248  *   ::= primary
   1249  *   ::= '!' unary *)
   1250 and parse_unary = parser
   1251   (* If this is a unary operator, read it. *)
   1252   | [&lt; 'Token.Kwd op when op != '(' &amp;&amp; op != ')'; operand=parse_expr &gt;] -&gt;
   1253       Ast.Unary (op, operand)
   1254 
   1255   (* If the current token is not an operator, it must be a primary expr. *)
   1256   | [&lt; stream &gt;] -&gt; parse_primary stream
   1257 
   1258 (* binoprhs
   1259  *   ::= ('+' primary)* *)
   1260 and parse_bin_rhs expr_prec lhs stream =
   1261   match Stream.peek stream with
   1262   (* If this is a binop, find its precedence. *)
   1263   | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c -&gt;
   1264       let token_prec = precedence c in
   1265 
   1266       (* If this is a binop that binds at least as tightly as the current binop,
   1267        * consume it, otherwise we are done. *)
   1268       if token_prec &lt; expr_prec then lhs else begin
   1269         (* Eat the binop. *)
   1270         Stream.junk stream;
   1271 
   1272         (* Parse the primary expression after the binary operator. *)
   1273         let rhs = parse_unary stream in
   1274 
   1275         (* Okay, we know this is a binop. *)
   1276         let rhs =
   1277           match Stream.peek stream with
   1278           | Some (Token.Kwd c2) -&gt;
   1279               (* If BinOp binds less tightly with rhs than the operator after
   1280                * rhs, let the pending operator take rhs as its lhs. *)
   1281               let next_prec = precedence c2 in
   1282               if token_prec &lt; next_prec
   1283               then parse_bin_rhs (token_prec + 1) rhs stream
   1284               else rhs
   1285           | _ -&gt; rhs
   1286         in
   1287 
   1288         (* Merge lhs/rhs. *)
   1289         let lhs = Ast.Binary (c, lhs, rhs) in
   1290         parse_bin_rhs expr_prec lhs stream
   1291       end
   1292   | _ -&gt; lhs
   1293 
   1294 and parse_var_init = parser
   1295   (* read in the optional initializer. *)
   1296   | [&lt; 'Token.Kwd '='; e=parse_expr &gt;] -&gt; Some e
   1297   | [&lt; &gt;] -&gt; None
   1298 
   1299 and parse_var_names accumulator = parser
   1300   | [&lt; 'Token.Kwd ',';
   1301        'Token.Ident id ?? "expected identifier list after var";
   1302        init=parse_var_init;
   1303        e=parse_var_names ((id, init) :: accumulator) &gt;] -&gt; e
   1304   | [&lt; &gt;] -&gt; accumulator
   1305 
   1306 (* expression
   1307  *   ::= primary binoprhs *)
   1308 and parse_expr = parser
   1309   | [&lt; lhs=parse_unary; stream &gt;] -&gt; parse_bin_rhs 0 lhs stream
   1310 
   1311 (* prototype
   1312  *   ::= id '(' id* ')'
   1313  *   ::= binary LETTER number? (id, id)
   1314  *   ::= unary LETTER number? (id) *)
   1315 let parse_prototype =
   1316   let rec parse_args accumulator = parser
   1317     | [&lt; 'Token.Ident id; e=parse_args (id::accumulator) &gt;] -&gt; e
   1318     | [&lt; &gt;] -&gt; accumulator
   1319   in
   1320   let parse_operator = parser
   1321     | [&lt; 'Token.Unary &gt;] -&gt; "unary", 1
   1322     | [&lt; 'Token.Binary &gt;] -&gt; "binary", 2
   1323   in
   1324   let parse_binary_precedence = parser
   1325     | [&lt; 'Token.Number n &gt;] -&gt; int_of_float n
   1326     | [&lt; &gt;] -&gt; 30
   1327   in
   1328   parser
   1329   | [&lt; 'Token.Ident id;
   1330        'Token.Kwd '(' ?? "expected '(' in prototype";
   1331        args=parse_args [];
   1332        'Token.Kwd ')' ?? "expected ')' in prototype" &gt;] -&gt;
   1333       (* success. *)
   1334       Ast.Prototype (id, Array.of_list (List.rev args))
   1335   | [&lt; (prefix, kind)=parse_operator;
   1336        'Token.Kwd op ?? "expected an operator";
   1337        (* Read the precedence if present. *)
   1338        binary_precedence=parse_binary_precedence;
   1339        'Token.Kwd '(' ?? "expected '(' in prototype";
   1340         args=parse_args [];
   1341        'Token.Kwd ')' ?? "expected ')' in prototype" &gt;] -&gt;
   1342       let name = prefix ^ (String.make 1 op) in
   1343       let args = Array.of_list (List.rev args) in
   1344 
   1345       (* Verify right number of arguments for operator. *)
   1346       if Array.length args != kind
   1347       then raise (Stream.Error "invalid number of operands for operator")
   1348       else
   1349         if kind == 1 then
   1350           Ast.Prototype (name, args)
   1351         else
   1352           Ast.BinOpPrototype (name, args, binary_precedence)
   1353   | [&lt; &gt;] -&gt;
   1354       raise (Stream.Error "expected function name in prototype")
   1355 
   1356 (* definition ::= 'def' prototype expression *)
   1357 let parse_definition = parser
   1358   | [&lt; 'Token.Def; p=parse_prototype; e=parse_expr &gt;] -&gt;
   1359       Ast.Function (p, e)
   1360 
   1361 (* toplevelexpr ::= expression *)
   1362 let parse_toplevel = parser
   1363   | [&lt; e=parse_expr &gt;] -&gt;
   1364       (* Make an anonymous proto. *)
   1365       Ast.Function (Ast.Prototype ("", [||]), e)
   1366 
   1367 (*  external ::= 'extern' prototype *)
   1368 let parse_extern = parser
   1369   | [&lt; 'Token.Extern; e=parse_prototype &gt;] -&gt; e
   1370 </pre>
   1371 </dd>
   1372 
   1373 <dt>codegen.ml:</dt>
   1374 <dd class="doc_code">
   1375 <pre>
   1376 (*===----------------------------------------------------------------------===
   1377  * Code Generation
   1378  *===----------------------------------------------------------------------===*)
   1379 
   1380 open Llvm
   1381 
   1382 exception Error of string
   1383 
   1384 let context = global_context ()
   1385 let the_module = create_module context "my cool jit"
   1386 let builder = builder context
   1387 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
   1388 let double_type = double_type context
   1389 
   1390 (* Create an alloca instruction in the entry block of the function. This
   1391  * is used for mutable variables etc. *)
   1392 let create_entry_block_alloca the_function var_name =
   1393   let builder = builder_at context (instr_begin (entry_block the_function)) in
   1394   build_alloca double_type var_name builder
   1395 
   1396 let rec codegen_expr = function
   1397   | Ast.Number n -&gt; const_float double_type n
   1398   | Ast.Variable name -&gt;
   1399       let v = try Hashtbl.find named_values name with
   1400         | Not_found -&gt; raise (Error "unknown variable name")
   1401       in
   1402       (* Load the value. *)
   1403       build_load v name builder
   1404   | Ast.Unary (op, operand) -&gt;
   1405       let operand = codegen_expr operand in
   1406       let callee = "unary" ^ (String.make 1 op) in
   1407       let callee =
   1408         match lookup_function callee the_module with
   1409         | Some callee -&gt; callee
   1410         | None -&gt; raise (Error "unknown unary operator")
   1411       in
   1412       build_call callee [|operand|] "unop" builder
   1413   | Ast.Binary (op, lhs, rhs) -&gt;
   1414       begin match op with
   1415       | '=' -&gt;
   1416           (* Special case '=' because we don't want to emit the LHS as an
   1417            * expression. *)
   1418           let name =
   1419             match lhs with
   1420             | Ast.Variable name -&gt; name
   1421             | _ -&gt; raise (Error "destination of '=' must be a variable")
   1422           in
   1423 
   1424           (* Codegen the rhs. *)
   1425           let val_ = codegen_expr rhs in
   1426 
   1427           (* Lookup the name. *)
   1428           let variable = try Hashtbl.find named_values name with
   1429           | Not_found -&gt; raise (Error "unknown variable name")
   1430           in
   1431           ignore(build_store val_ variable builder);
   1432           val_
   1433       | _ -&gt;
   1434           let lhs_val = codegen_expr lhs in
   1435           let rhs_val = codegen_expr rhs in
   1436           begin
   1437             match op with
   1438             | '+' -&gt; build_add lhs_val rhs_val "addtmp" builder
   1439             | '-' -&gt; build_sub lhs_val rhs_val "subtmp" builder
   1440             | '*' -&gt; build_mul lhs_val rhs_val "multmp" builder
   1441             | '&lt;' -&gt;
   1442                 (* Convert bool 0/1 to double 0.0 or 1.0 *)
   1443                 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
   1444                 build_uitofp i double_type "booltmp" builder
   1445             | _ -&gt;
   1446                 (* If it wasn't a builtin binary operator, it must be a user defined
   1447                  * one. Emit a call to it. *)
   1448                 let callee = "binary" ^ (String.make 1 op) in
   1449                 let callee =
   1450                   match lookup_function callee the_module with
   1451                   | Some callee -&gt; callee
   1452                   | None -&gt; raise (Error "binary operator not found!")
   1453                 in
   1454                 build_call callee [|lhs_val; rhs_val|] "binop" builder
   1455           end
   1456       end
   1457   | Ast.Call (callee, args) -&gt;
   1458       (* Look up the name in the module table. *)
   1459       let callee =
   1460         match lookup_function callee the_module with
   1461         | Some callee -&gt; callee
   1462         | None -&gt; raise (Error "unknown function referenced")
   1463       in
   1464       let params = params callee in
   1465 
   1466       (* If argument mismatch error. *)
   1467       if Array.length params == Array.length args then () else
   1468         raise (Error "incorrect # arguments passed");
   1469       let args = Array.map codegen_expr args in
   1470       build_call callee args "calltmp" builder
   1471   | Ast.If (cond, then_, else_) -&gt;
   1472       let cond = codegen_expr cond in
   1473 
   1474       (* Convert condition to a bool by comparing equal to 0.0 *)
   1475       let zero = const_float double_type 0.0 in
   1476       let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
   1477 
   1478       (* Grab the first block so that we might later add the conditional branch
   1479        * to it at the end of the function. *)
   1480       let start_bb = insertion_block builder in
   1481       let the_function = block_parent start_bb in
   1482 
   1483       let then_bb = append_block context "then" the_function in
   1484 
   1485       (* Emit 'then' value. *)
   1486       position_at_end then_bb builder;
   1487       let then_val = codegen_expr then_ in
   1488 
   1489       (* Codegen of 'then' can change the current block, update then_bb for the
   1490        * phi. We create a new name because one is used for the phi node, and the
   1491        * other is used for the conditional branch. *)
   1492       let new_then_bb = insertion_block builder in
   1493 
   1494       (* Emit 'else' value. *)
   1495       let else_bb = append_block context "else" the_function in
   1496       position_at_end else_bb builder;
   1497       let else_val = codegen_expr else_ in
   1498 
   1499       (* Codegen of 'else' can change the current block, update else_bb for the
   1500        * phi. *)
   1501       let new_else_bb = insertion_block builder in
   1502 
   1503       (* Emit merge block. *)
   1504       let merge_bb = append_block context "ifcont" the_function in
   1505       position_at_end merge_bb builder;
   1506       let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
   1507       let phi = build_phi incoming "iftmp" builder in
   1508 
   1509       (* Return to the start block to add the conditional branch. *)
   1510       position_at_end start_bb builder;
   1511       ignore (build_cond_br cond_val then_bb else_bb builder);
   1512 
   1513       (* Set a unconditional branch at the end of the 'then' block and the
   1514        * 'else' block to the 'merge' block. *)
   1515       position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
   1516       position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
   1517 
   1518       (* Finally, set the builder to the end of the merge block. *)
   1519       position_at_end merge_bb builder;
   1520 
   1521       phi
   1522   | Ast.For (var_name, start, end_, step, body) -&gt;
   1523       (* Output this as:
   1524        *   var = alloca double
   1525        *   ...
   1526        *   start = startexpr
   1527        *   store start -&gt; var
   1528        *   goto loop
   1529        * loop:
   1530        *   ...
   1531        *   bodyexpr
   1532        *   ...
   1533        * loopend:
   1534        *   step = stepexpr
   1535        *   endcond = endexpr
   1536        *
   1537        *   curvar = load var
   1538        *   nextvar = curvar + step
   1539        *   store nextvar -&gt; var
   1540        *   br endcond, loop, endloop
   1541        * outloop: *)
   1542 
   1543       let the_function = block_parent (insertion_block builder) in
   1544 
   1545       (* Create an alloca for the variable in the entry block. *)
   1546       let alloca = create_entry_block_alloca the_function var_name in
   1547 
   1548       (* Emit the start code first, without 'variable' in scope. *)
   1549       let start_val = codegen_expr start in
   1550 
   1551       (* Store the value into the alloca. *)
   1552       ignore(build_store start_val alloca builder);
   1553 
   1554       (* Make the new basic block for the loop header, inserting after current
   1555        * block. *)
   1556       let loop_bb = append_block context "loop" the_function in
   1557 
   1558       (* Insert an explicit fall through from the current block to the
   1559        * loop_bb. *)
   1560       ignore (build_br loop_bb builder);
   1561 
   1562       (* Start insertion in loop_bb. *)
   1563       position_at_end loop_bb builder;
   1564 
   1565       (* Within the loop, the variable is defined equal to the PHI node. If it
   1566        * shadows an existing variable, we have to restore it, so save it
   1567        * now. *)
   1568       let old_val =
   1569         try Some (Hashtbl.find named_values var_name) with Not_found -&gt; None
   1570       in
   1571       Hashtbl.add named_values var_name alloca;
   1572 
   1573       (* Emit the body of the loop.  This, like any other expr, can change the
   1574        * current BB.  Note that we ignore the value computed by the body, but
   1575        * don't allow an error *)
   1576       ignore (codegen_expr body);
   1577 
   1578       (* Emit the step value. *)
   1579       let step_val =
   1580         match step with
   1581         | Some step -&gt; codegen_expr step
   1582         (* If not specified, use 1.0. *)
   1583         | None -&gt; const_float double_type 1.0
   1584       in
   1585 
   1586       (* Compute the end condition. *)
   1587       let end_cond = codegen_expr end_ in
   1588 
   1589       (* Reload, increment, and restore the alloca. This handles the case where
   1590        * the body of the loop mutates the variable. *)
   1591       let cur_var = build_load alloca var_name builder in
   1592       let next_var = build_add cur_var step_val "nextvar" builder in
   1593       ignore(build_store next_var alloca builder);
   1594 
   1595       (* Convert condition to a bool by comparing equal to 0.0. *)
   1596       let zero = const_float double_type 0.0 in
   1597       let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
   1598 
   1599       (* Create the "after loop" block and insert it. *)
   1600       let after_bb = append_block context "afterloop" the_function in
   1601 
   1602       (* Insert the conditional branch into the end of loop_end_bb. *)
   1603       ignore (build_cond_br end_cond loop_bb after_bb builder);
   1604 
   1605       (* Any new code will be inserted in after_bb. *)
   1606       position_at_end after_bb builder;
   1607 
   1608       (* Restore the unshadowed variable. *)
   1609       begin match old_val with
   1610       | Some old_val -&gt; Hashtbl.add named_values var_name old_val
   1611       | None -&gt; ()
   1612       end;
   1613 
   1614       (* for expr always returns 0.0. *)
   1615       const_null double_type
   1616   | Ast.Var (var_names, body) -&gt;
   1617       let old_bindings = ref [] in
   1618 
   1619       let the_function = block_parent (insertion_block builder) in
   1620 
   1621       (* Register all variables and emit their initializer. *)
   1622       Array.iter (fun (var_name, init) -&gt;
   1623         (* Emit the initializer before adding the variable to scope, this
   1624          * prevents the initializer from referencing the variable itself, and
   1625          * permits stuff like this:
   1626          *   var a = 1 in
   1627          *     var a = a in ...   # refers to outer 'a'. *)
   1628         let init_val =
   1629           match init with
   1630           | Some init -&gt; codegen_expr init
   1631           (* If not specified, use 0.0. *)
   1632           | None -&gt; const_float double_type 0.0
   1633         in
   1634 
   1635         let alloca = create_entry_block_alloca the_function var_name in
   1636         ignore(build_store init_val alloca builder);
   1637 
   1638         (* Remember the old variable binding so that we can restore the binding
   1639          * when we unrecurse. *)
   1640         begin
   1641           try
   1642             let old_value = Hashtbl.find named_values var_name in
   1643             old_bindings := (var_name, old_value) :: !old_bindings;
   1644           with Not_found -&gt; ()
   1645         end;
   1646 
   1647         (* Remember this binding. *)
   1648         Hashtbl.add named_values var_name alloca;
   1649       ) var_names;
   1650 
   1651       (* Codegen the body, now that all vars are in scope. *)
   1652       let body_val = codegen_expr body in
   1653 
   1654       (* Pop all our variables from scope. *)
   1655       List.iter (fun (var_name, old_value) -&gt;
   1656         Hashtbl.add named_values var_name old_value
   1657       ) !old_bindings;
   1658 
   1659       (* Return the body computation. *)
   1660       body_val
   1661 
   1662 let codegen_proto = function
   1663   | Ast.Prototype (name, args) | Ast.BinOpPrototype (name, args, _) -&gt;
   1664       (* Make the function type: double(double,double) etc. *)
   1665       let doubles = Array.make (Array.length args) double_type in
   1666       let ft = function_type double_type doubles in
   1667       let f =
   1668         match lookup_function name the_module with
   1669         | None -&gt; declare_function name ft the_module
   1670 
   1671         (* If 'f' conflicted, there was already something named 'name'. If it
   1672          * has a body, don't allow redefinition or reextern. *)
   1673         | Some f -&gt;
   1674             (* If 'f' already has a body, reject this. *)
   1675             if block_begin f &lt;&gt; At_end f then
   1676               raise (Error "redefinition of function");
   1677 
   1678             (* If 'f' took a different number of arguments, reject. *)
   1679             if element_type (type_of f) &lt;&gt; ft then
   1680               raise (Error "redefinition of function with different # args");
   1681             f
   1682       in
   1683 
   1684       (* Set names for all arguments. *)
   1685       Array.iteri (fun i a -&gt;
   1686         let n = args.(i) in
   1687         set_value_name n a;
   1688         Hashtbl.add named_values n a;
   1689       ) (params f);
   1690       f
   1691 
   1692 (* Create an alloca for each argument and register the argument in the symbol
   1693  * table so that references to it will succeed. *)
   1694 let create_argument_allocas the_function proto =
   1695   let args = match proto with
   1696     | Ast.Prototype (_, args) | Ast.BinOpPrototype (_, args, _) -&gt; args
   1697   in
   1698   Array.iteri (fun i ai -&gt;
   1699     let var_name = args.(i) in
   1700     (* Create an alloca for this variable. *)
   1701     let alloca = create_entry_block_alloca the_function var_name in
   1702 
   1703     (* Store the initial value into the alloca. *)
   1704     ignore(build_store ai alloca builder);
   1705 
   1706     (* Add arguments to variable symbol table. *)
   1707     Hashtbl.add named_values var_name alloca;
   1708   ) (params the_function)
   1709 
   1710 let codegen_func the_fpm = function
   1711   | Ast.Function (proto, body) -&gt;
   1712       Hashtbl.clear named_values;
   1713       let the_function = codegen_proto proto in
   1714 
   1715       (* If this is an operator, install it. *)
   1716       begin match proto with
   1717       | Ast.BinOpPrototype (name, args, prec) -&gt;
   1718           let op = name.[String.length name - 1] in
   1719           Hashtbl.add Parser.binop_precedence op prec;
   1720       | _ -&gt; ()
   1721       end;
   1722 
   1723       (* Create a new basic block to start insertion into. *)
   1724       let bb = append_block context "entry" the_function in
   1725       position_at_end bb builder;
   1726 
   1727       try
   1728         (* Add all arguments to the symbol table and create their allocas. *)
   1729         create_argument_allocas the_function proto;
   1730 
   1731         let ret_val = codegen_expr body in
   1732 
   1733         (* Finish off the function. *)
   1734         let _ = build_ret ret_val builder in
   1735 
   1736         (* Validate the generated code, checking for consistency. *)
   1737         Llvm_analysis.assert_valid_function the_function;
   1738 
   1739         (* Optimize the function. *)
   1740         let _ = PassManager.run_function the_function the_fpm in
   1741 
   1742         the_function
   1743       with e -&gt;
   1744         delete_function the_function;
   1745         raise e
   1746 </pre>
   1747 </dd>
   1748 
   1749 <dt>toplevel.ml:</dt>
   1750 <dd class="doc_code">
   1751 <pre>
   1752 (*===----------------------------------------------------------------------===
   1753  * Top-Level parsing and JIT Driver
   1754  *===----------------------------------------------------------------------===*)
   1755 
   1756 open Llvm
   1757 open Llvm_executionengine
   1758 
   1759 (* top ::= definition | external | expression | ';' *)
   1760 let rec main_loop the_fpm the_execution_engine stream =
   1761   match Stream.peek stream with
   1762   | None -&gt; ()
   1763 
   1764   (* ignore top-level semicolons. *)
   1765   | Some (Token.Kwd ';') -&gt;
   1766       Stream.junk stream;
   1767       main_loop the_fpm the_execution_engine stream
   1768 
   1769   | Some token -&gt;
   1770       begin
   1771         try match token with
   1772         | Token.Def -&gt;
   1773             let e = Parser.parse_definition stream in
   1774             print_endline "parsed a function definition.";
   1775             dump_value (Codegen.codegen_func the_fpm e);
   1776         | Token.Extern -&gt;
   1777             let e = Parser.parse_extern stream in
   1778             print_endline "parsed an extern.";
   1779             dump_value (Codegen.codegen_proto e);
   1780         | _ -&gt;
   1781             (* Evaluate a top-level expression into an anonymous function. *)
   1782             let e = Parser.parse_toplevel stream in
   1783             print_endline "parsed a top-level expr";
   1784             let the_function = Codegen.codegen_func the_fpm e in
   1785             dump_value the_function;
   1786 
   1787             (* JIT the function, returning a function pointer. *)
   1788             let result = ExecutionEngine.run_function the_function [||]
   1789               the_execution_engine in
   1790 
   1791             print_string "Evaluated to ";
   1792             print_float (GenericValue.as_float Codegen.double_type result);
   1793             print_newline ();
   1794         with Stream.Error s | Codegen.Error s -&gt;
   1795           (* Skip token for error recovery. *)
   1796           Stream.junk stream;
   1797           print_endline s;
   1798       end;
   1799       print_string "ready&gt; "; flush stdout;
   1800       main_loop the_fpm the_execution_engine stream
   1801 </pre>
   1802 </dd>
   1803 
   1804 <dt>toy.ml:</dt>
   1805 <dd class="doc_code">
   1806 <pre>
   1807 (*===----------------------------------------------------------------------===
   1808  * Main driver code.
   1809  *===----------------------------------------------------------------------===*)
   1810 
   1811 open Llvm
   1812 open Llvm_executionengine
   1813 open Llvm_target
   1814 open Llvm_scalar_opts
   1815 
   1816 let main () =
   1817   ignore (initialize_native_target ());
   1818 
   1819   (* Install standard binary operators.
   1820    * 1 is the lowest precedence. *)
   1821   Hashtbl.add Parser.binop_precedence '=' 2;
   1822   Hashtbl.add Parser.binop_precedence '&lt;' 10;
   1823   Hashtbl.add Parser.binop_precedence '+' 20;
   1824   Hashtbl.add Parser.binop_precedence '-' 20;
   1825   Hashtbl.add Parser.binop_precedence '*' 40;    (* highest. *)
   1826 
   1827   (* Prime the first token. *)
   1828   print_string "ready&gt; "; flush stdout;
   1829   let stream = Lexer.lex (Stream.of_channel stdin) in
   1830 
   1831   (* Create the JIT. *)
   1832   let the_execution_engine = ExecutionEngine.create Codegen.the_module in
   1833   let the_fpm = PassManager.create_function Codegen.the_module in
   1834 
   1835   (* Set up the optimizer pipeline.  Start with registering info about how the
   1836    * target lays out data structures. *)
   1837   TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
   1838 
   1839   (* Promote allocas to registers. *)
   1840   add_memory_to_register_promotion the_fpm;
   1841 
   1842   (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
   1843   add_instruction_combination the_fpm;
   1844 
   1845   (* reassociate expressions. *)
   1846   add_reassociation the_fpm;
   1847 
   1848   (* Eliminate Common SubExpressions. *)
   1849   add_gvn the_fpm;
   1850 
   1851   (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
   1852   add_cfg_simplification the_fpm;
   1853 
   1854   ignore (PassManager.initialize the_fpm);
   1855 
   1856   (* Run the main "interpreter loop" now. *)
   1857   Toplevel.main_loop the_fpm the_execution_engine stream;
   1858 
   1859   (* Print out all the generated code. *)
   1860   dump_module Codegen.the_module
   1861 ;;
   1862 
   1863 main ()
   1864 </pre>
   1865 </dd>
   1866 
   1867 <dt>bindings.c</dt>
   1868 <dd class="doc_code">
   1869 <pre>
   1870 #include &lt;stdio.h&gt;
   1871 
   1872 /* putchard - putchar that takes a double and returns 0. */
   1873 extern double putchard(double X) {
   1874   putchar((char)X);
   1875   return 0;
   1876 }
   1877 
   1878 /* printd - printf that takes a double prints it as "%f\n", returning 0. */
   1879 extern double printd(double X) {
   1880   printf("%f\n", X);
   1881   return 0;
   1882 }
   1883 </pre>
   1884 </dd>
   1885 </dl>
   1886 
   1887 <a href="OCamlLangImpl8.html">Next: Conclusion and other useful LLVM tidbits</a>
   1888 </div>
   1889 
   1890 <!-- *********************************************************************** -->
   1891 <hr>
   1892 <address>
   1893   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
   1894   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
   1895   <a href="http://validator.w3.org/check/referer"><img
   1896   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
   1897 
   1898   <a href="mailto:sabre (a] nondot.org">Chris Lattner</a><br>
   1899   <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
   1900   <a href="mailto:idadesub (a] users.sourceforge.net">Erick Tryzelaar</a><br>
   1901   Last modified: $Date$
   1902 </address>
   1903 </body>
   1904 </html>
   1905