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