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 <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@nondot.org">Chris Lattner</a>
  40                 and <a href="mailto:idadesub@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 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 <h2><a name="why">Why is this a hard problem?</a></h2>
  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 <h2><a name="memory">Memory in LLVM</a></h2>
 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 <h2><a name="kalvars">Mutable Variables in Kaleidoscope</a></h2>
 329 <!-- *********************************************************************** -->
 330
 331 <div class="doc_text">
 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 class="doc_text">
 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 class="doc_text">
 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 class="doc_text">
 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 class="doc_text">
 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@nondot.org">Chris Lattner</a><br>
1899   <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
1900   <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br>
1901   Last modified: $Date$
1902 </address>
1903 </body>
1904 </html>