docs/tutorial/OCamlLangImpl5.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: Control Flow</title>
   7   <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
   8   <meta name="author" content="Chris Lattner">
   9   <meta name="author" content="Erick Tryzelaar">
  10   <link rel="stylesheet" href="../_static/llvm.css" type="text/css">
  11 </head>
  12
  13 <body>
  14
  15 <h1>Kaleidoscope: Extending the Language: Control Flow</h1>
  16
  17 <ul>
  18 <li><a href="index.html">Up to Tutorial Index</a></li>
  19 <li>Chapter 5
  20   <ol>
  21     <li><a href="#intro">Chapter 5 Introduction</a></li>
  22     <li><a href="#ifthen">If/Then/Else</a>
  23     <ol>
  24       <li><a href="#iflexer">Lexer Extensions</a></li>
  25       <li><a href="#ifast">AST Extensions</a></li>
  26       <li><a href="#ifparser">Parser Extensions</a></li>
  27       <li><a href="#ifir">LLVM IR</a></li>
  28       <li><a href="#ifcodegen">Code Generation</a></li>
  29     </ol>
  30     </li>
  31     <li><a href="#for">'for' Loop Expression</a>
  32     <ol>
  33       <li><a href="#forlexer">Lexer Extensions</a></li>
  34       <li><a href="#forast">AST Extensions</a></li>
  35       <li><a href="#forparser">Parser Extensions</a></li>
  36       <li><a href="#forir">LLVM IR</a></li>
  37       <li><a href="#forcodegen">Code Generation</a></li>
  38     </ol>
  39     </li>
  40     <li><a href="#code">Full Code Listing</a></li>
  41   </ol>
  42 </li>
  43 <li><a href="OCamlLangImpl6.html">Chapter 6</a>: Extending the Language:
  44 User-defined Operators</li>
  45 </ul>
  46
  47 <div class="doc_author">
  48         <p>
  49                 Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>
  50                 and <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a>
  51         </p>
  52 </div>
  53
  54 <!-- *********************************************************************** -->
  55 <h2><a name="intro">Chapter 5 Introduction</a></h2>
  56 <!-- *********************************************************************** -->
  57
  58 <div>
  59
  60 <p>Welcome to Chapter 5 of the "<a href="index.html">Implementing a language
  61 with LLVM</a>" tutorial.  Parts 1-4 described the implementation of the simple
  62 Kaleidoscope language and included support for generating LLVM IR, followed by
  63 optimizations and a JIT compiler.  Unfortunately, as presented, Kaleidoscope is
  64 mostly useless: it has no control flow other than call and return.  This means
  65 that you can't have conditional branches in the code, significantly limiting its
  66 power.  In this episode of "build that compiler", we'll extend Kaleidoscope to
  67 have an if/then/else expression plus a simple 'for' loop.</p>
  68
  69 </div>
  70
  71 <!-- *********************************************************************** -->
  72 <h2><a name="ifthen">If/Then/Else</a></h2>
  73 <!-- *********************************************************************** -->
  74
  75 <div>
  76
  77 <p>
  78 Extending Kaleidoscope to support if/then/else is quite straightforward.  It
  79 basically requires adding lexer support for this "new" concept to the lexer,
  80 parser, AST, and LLVM code emitter.  This example is nice, because it shows how
  81 easy it is to "grow" a language over time, incrementally extending it as new
  82 ideas are discovered.</p>
  83
  84 <p>Before we get going on "how" we add this extension, lets talk about "what" we
  85 want.  The basic idea is that we want to be able to write this sort of thing:
  86 </p>
  87
  88 <div class="doc_code">
  89 <pre>
  90 def fib(x)
  91   if x &lt; 3 then
  92     1
  93   else
  94     fib(x-1)+fib(x-2);
  95 </pre>
  96 </div>
  97
  98 <p>In Kaleidoscope, every construct is an expression: there are no statements.
  99 As such, the if/then/else expression needs to return a value like any other.
 100 Since we're using a mostly functional form, we'll have it evaluate its
 101 conditional, then return the 'then' or 'else' value based on how the condition
 102 was resolved.  This is very similar to the C "?:" expression.</p>
 103
 104 <p>The semantics of the if/then/else expression is that it evaluates the
 105 condition to a boolean equality value: 0.0 is considered to be false and
 106 everything else is considered to be true.
 107 If the condition is true, the first subexpression is evaluated and returned, if
 108 the condition is false, the second subexpression is evaluated and returned.
 109 Since Kaleidoscope allows side-effects, this behavior is important to nail down.
 110 </p>
 111
 112 <p>Now that we know what we "want", lets break this down into its constituent
 113 pieces.</p>
 114
 115 <!-- ======================================================================= -->
 116 <h4><a name="iflexer">Lexer Extensions for If/Then/Else</a></h4>
 117 <!-- ======================================================================= -->
 118
 119
 120 <div>
 121
 122 <p>The lexer extensions are straightforward.  First we add new variants
 123 for the relevant tokens:</p>
 124
 125 <div class="doc_code">
 126 <pre>
 127   (* control *)
 128   | If | Then | Else | For | In
 129 </pre>
 130 </div>
 131
 132 <p>Once we have that, we recognize the new keywords in the lexer. This is pretty simple
 133 stuff:</p>
 134
 135 <div class="doc_code">
 136 <pre>
 137       ...
 138       match Buffer.contents buffer with
 139       | "def" -&gt; [&lt; 'Token.Def; stream &gt;]
 140       | "extern" -&gt; [&lt; 'Token.Extern; stream &gt;]
 141       | "if" -&gt; [&lt; 'Token.If; stream &gt;]
 142       | "then" -&gt; [&lt; 'Token.Then; stream &gt;]
 143       | "else" -&gt; [&lt; 'Token.Else; stream &gt;]
 144       | "for" -&gt; [&lt; 'Token.For; stream &gt;]
 145       | "in" -&gt; [&lt; 'Token.In; stream &gt;]
 146       | id -&gt; [&lt; 'Token.Ident id; stream &gt;]
 147 </pre>
 148 </div>
 149
 150 </div>
 151
 152 <!-- ======================================================================= -->
 153 <h4><a name="ifast">AST Extensions for If/Then/Else</a></h4>
 154 <!-- ======================================================================= -->
 155
 156 <div>
 157
 158 <p>To represent the new expression we add a new AST variant for it:</p>
 159
 160 <div class="doc_code">
 161 <pre>
 162 type expr =
 163   ...
 164   (* variant for if/then/else. *)
 165   | If of expr * expr * expr
 166 </pre>
 167 </div>
 168
 169 <p>The AST variant just has pointers to the various subexpressions.</p>
 170
 171 </div>
 172
 173 <!-- ======================================================================= -->
 174 <h4><a name="ifparser">Parser Extensions for If/Then/Else</a></h4>
 175 <!-- ======================================================================= -->
 176
 177 <div>
 178
 179 <p>Now that we have the relevant tokens coming from the lexer and we have the
 180 AST node to build, our parsing logic is relatively straightforward.  First we
 181 define a new parsing function:</p>
 182
 183 <div class="doc_code">
 184 <pre>
 185 let rec parse_primary = parser
 186   ...
 187   (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
 188   | [&lt; 'Token.If; c=parse_expr;
 189        'Token.Then ?? "expected 'then'"; t=parse_expr;
 190        'Token.Else ?? "expected 'else'"; e=parse_expr &gt;] -&gt;
 191       Ast.If (c, t, e)
 192 </pre>
 193 </div>
 194
 195 <p>Next we hook it up as a primary expression:</p>
 196
 197 <div class="doc_code">
 198 <pre>
 199 let rec parse_primary = parser
 200   ...
 201   (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
 202   | [&lt; 'Token.If; c=parse_expr;
 203        'Token.Then ?? "expected 'then'"; t=parse_expr;
 204        'Token.Else ?? "expected 'else'"; e=parse_expr &gt;] -&gt;
 205       Ast.If (c, t, e)
 206 </pre>
 207 </div>
 208
 209 </div>
 210
 211 <!-- ======================================================================= -->
 212 <h4><a name="ifir">LLVM IR for If/Then/Else</a></h4>
 213 <!-- ======================================================================= -->
 214
 215 <div>
 216
 217 <p>Now that we have it parsing and building the AST, the final piece is adding
 218 LLVM code generation support.  This is the most interesting part of the
 219 if/then/else example, because this is where it starts to introduce new concepts.
 220 All of the code above has been thoroughly described in previous chapters.
 221 </p>
 222
 223 <p>To motivate the code we want to produce, lets take a look at a simple
 224 example.  Consider:</p>
 225
 226 <div class="doc_code">
 227 <pre>
 228 extern foo();
 229 extern bar();
 230 def baz(x) if x then foo() else bar();
 231 </pre>
 232 </div>
 233
 234 <p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
 235 looks like this:</p>
 236
 237 <div class="doc_code">
 238 <pre>
 239 declare double @foo()
 240
 241 declare double @bar()
 242
 243 define double @baz(double %x) {
 244 entry:
 245   %ifcond = fcmp one double %x, 0.000000e+00
 246   br i1 %ifcond, label %then, label %else
 247
 248 then:    ; preds = %entry
 249   %calltmp = call double @foo()
 250   br label %ifcont
 251
 252 else:    ; preds = %entry
 253   %calltmp1 = call double @bar()
 254   br label %ifcont
 255
 256 ifcont:    ; preds = %else, %then
 257   %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
 258   ret double %iftmp
 259 }
 260 </pre>
 261 </div>
 262
 263 <p>To visualize the control flow graph, you can use a nifty feature of the LLVM
 264 '<a href="http://llvm.org/cmds/opt.html">opt</a>' tool.  If you put this LLVM IR
 265 into "t.ll" and run "<tt>llvm-as &lt; t.ll | opt -analyze -view-cfg</tt>", <a
 266 href="../ProgrammersManual.html#ViewGraph">a window will pop up</a> and you'll
 267 see this graph:</p>
 268
 269 <div style="text-align: center"><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
 270 height="315"></div>
 271
 272 <p>Another way to get this is to call "<tt>Llvm_analysis.view_function_cfg
 273 f</tt>" or "<tt>Llvm_analysis.view_function_cfg_only f</tt>" (where <tt>f</tt>
 274 is a "<tt>Function</tt>") either by inserting actual calls into the code and
 275 recompiling or by calling these in the debugger.  LLVM has many nice features
 276 for visualizing various graphs.</p>
 277
 278 <p>Getting back to the generated code, it is fairly simple: the entry block
 279 evaluates the conditional expression ("x" in our case here) and compares the
 280 result to 0.0 with the "<tt><a href="../LangRef.html#i_fcmp">fcmp</a> one</tt>"
 281 instruction ('one' is "Ordered and Not Equal").  Based on the result of this
 282 expression, the code jumps to either the "then" or "else" blocks, which contain
 283 the expressions for the true/false cases.</p>
 284
 285 <p>Once the then/else blocks are finished executing, they both branch back to the
 286 'ifcont' block to execute the code that happens after the if/then/else.  In this
 287 case the only thing left to do is to return to the caller of the function.  The
 288 question then becomes: how does the code know which expression to return?</p>
 289
 290 <p>The answer to this question involves an important SSA operation: the
 291 <a href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Phi
 292 operation</a>.  If you're not familiar with SSA, <a
 293 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">the wikipedia
 294 article</a> is a good introduction and there are various other introductions to
 295 it available on your favorite search engine.  The short version is that
 296 "execution" of the Phi operation requires "remembering" which block control came
 297 from.  The Phi operation takes on the value corresponding to the input control
 298 block.  In this case, if control comes in from the "then" block, it gets the
 299 value of "calltmp".  If control comes from the "else" block, it gets the value
 300 of "calltmp1".</p>
 301
 302 <p>At this point, you are probably starting to think "Oh no! This means my
 303 simple and elegant front-end will have to start generating SSA form in order to
 304 use LLVM!".  Fortunately, this is not the case, and we strongly advise
 305 <em>not</em> implementing an SSA construction algorithm in your front-end
 306 unless there is an amazingly good reason to do so.  In practice, there are two
 307 sorts of values that float around in code written for your average imperative
 308 programming language that might need Phi nodes:</p>
 309
 310 <ol>
 311 <li>Code that involves user variables: <tt>x = 1; x = x + 1; </tt></li>
 312 <li>Values that are implicit in the structure of your AST, such as the Phi node
 313 in this case.</li>
 314 </ol>
 315
 316 <p>In <a href="OCamlLangImpl7.html">Chapter 7</a> of this tutorial ("mutable
 317 variables"), we'll talk about #1
 318 in depth.  For now, just believe me that you don't need SSA construction to
 319 handle this case.  For #2, you have the choice of using the techniques that we will
 320 describe for #1, or you can insert Phi nodes directly, if convenient.  In this
 321 case, it is really really easy to generate the Phi node, so we choose to do it
 322 directly.</p>
 323
 324 <p>Okay, enough of the motivation and overview, lets generate code!</p>
 325
 326 </div>
 327
 328 <!-- ======================================================================= -->
 329 <h4><a name="ifcodegen">Code Generation for If/Then/Else</a></h4>
 330 <!-- ======================================================================= -->
 331
 332 <div>
 333
 334 <p>In order to generate code for this, we implement the <tt>Codegen</tt> method
 335 for <tt>IfExprAST</tt>:</p>
 336
 337 <div class="doc_code">
 338 <pre>
 339 let rec codegen_expr = function
 340   ...
 341   | Ast.If (cond, then_, else_) -&gt;
 342       let cond = codegen_expr cond in
 343
 344       (* Convert condition to a bool by comparing equal to 0.0 *)
 345       let zero = const_float double_type 0.0 in
 346       let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
 347 </pre>
 348 </div>
 349
 350 <p>This code is straightforward and similar to what we saw before.  We emit the
 351 expression for the condition, then compare that value to zero to get a truth
 352 value as a 1-bit (bool) value.</p>
 353
 354 <div class="doc_code">
 355 <pre>
 356       (* Grab the first block so that we might later add the conditional branch
 357        * to it at the end of the function. *)
 358       let start_bb = insertion_block builder in
 359       let the_function = block_parent start_bb in
 360
 361       let then_bb = append_block context "then" the_function in
 362       position_at_end then_bb builder;
 363 </pre>
 364 </div>
 365
 366 <p>
 367 As opposed to the <a href="LangImpl5.html">C++ tutorial</a>, we have to build
 368 our basic blocks bottom up since we can't have dangling BasicBlocks.  We start
 369 off by saving a pointer to the first block (which might not be the entry
 370 block), which we'll need to build a conditional branch later.  We do this by
 371 asking the <tt>builder</tt> for the current BasicBlock.  The fourth line
 372 gets the current Function object that is being built.  It gets this by the
 373 <tt>start_bb</tt> for its "parent" (the function it is currently embedded
 374 into).</p>
 375
 376 <p>Once it has that, it creates one block.  It is automatically appended into
 377 the function's list of blocks.</p>
 378
 379 <div class="doc_code">
 380 <pre>
 381       (* Emit 'then' value. *)
 382       position_at_end then_bb builder;
 383       let then_val = codegen_expr then_ in
 384
 385       (* Codegen of 'then' can change the current block, update then_bb for the
 386        * phi. We create a new name because one is used for the phi node, and the
 387        * other is used for the conditional branch. *)
 388       let new_then_bb = insertion_block builder in
 389 </pre>
 390 </div>
 391
 392 <p>We move the builder to start inserting into the "then" block.  Strictly
 393 speaking, this call moves the insertion point to be at the end of the specified
 394 block.  However, since the "then" block is empty, it also starts out by
 395 inserting at the beginning of the block.  :)</p>
 396
 397 <p>Once the insertion point is set, we recursively codegen the "then" expression
 398 from the AST.</p>
 399
 400 <p>The final line here is quite subtle, but is very important.  The basic issue
 401 is that when we create the Phi node in the merge block, we need to set up the
 402 block/value pairs that indicate how the Phi will work.  Importantly, the Phi
 403 node expects to have an entry for each predecessor of the block in the CFG.  Why
 404 then, are we getting the current block when we just set it to ThenBB 5 lines
 405 above?  The problem is that the "Then" expression may actually itself change the
 406 block that the Builder is emitting into if, for example, it contains a nested
 407 "if/then/else" expression.  Because calling Codegen recursively could
 408 arbitrarily change the notion of the current block, we are required to get an
 409 up-to-date value for code that will set up the Phi node.</p>
 410
 411 <div class="doc_code">
 412 <pre>
 413       (* Emit 'else' value. *)
 414       let else_bb = append_block context "else" the_function in
 415       position_at_end else_bb builder;
 416       let else_val = codegen_expr else_ in
 417
 418       (* Codegen of 'else' can change the current block, update else_bb for the
 419        * phi. *)
 420       let new_else_bb = insertion_block builder in
 421 </pre>
 422 </div>
 423
 424 <p>Code generation for the 'else' block is basically identical to codegen for
 425 the 'then' block.</p>
 426
 427 <div class="doc_code">
 428 <pre>
 429       (* Emit merge block. *)
 430       let merge_bb = append_block context "ifcont" the_function in
 431       position_at_end merge_bb builder;
 432       let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
 433       let phi = build_phi incoming "iftmp" builder in
 434 </pre>
 435 </div>
 436
 437 <p>The first two lines here are now familiar: the first adds the "merge" block
 438 to the Function object.  The second block changes the insertion point so that
 439 newly created code will go into the "merge" block.  Once that is done, we need
 440 to create the PHI node and set up the block/value pairs for the PHI.</p>
 441
 442 <div class="doc_code">
 443 <pre>
 444       (* Return to the start block to add the conditional branch. *)
 445       position_at_end start_bb builder;
 446       ignore (build_cond_br cond_val then_bb else_bb builder);
 447 </pre>
 448 </div>
 449
 450 <p>Once the blocks are created, we can emit the conditional branch that chooses
 451 between them.  Note that creating new blocks does not implicitly affect the
 452 IRBuilder, so it is still inserting into the block that the condition
 453 went into.  This is why we needed to save the "start" block.</p>
 454
 455 <div class="doc_code">
 456 <pre>
 457       (* Set a unconditional branch at the end of the 'then' block and the
 458        * 'else' block to the 'merge' block. *)
 459       position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
 460       position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
 461
 462       (* Finally, set the builder to the end of the merge block. *)
 463       position_at_end merge_bb builder;
 464
 465       phi
 466 </pre>
 467 </div>
 468
 469 <p>To finish off the blocks, we create an unconditional branch
 470 to the merge block.  One interesting (and very important) aspect of the LLVM IR
 471 is that it <a href="../LangRef.html#functionstructure">requires all basic blocks
 472 to be "terminated"</a> with a <a href="../LangRef.html#terminators">control flow
 473 instruction</a> such as return or branch.  This means that all control flow,
 474 <em>including fall throughs</em> must be made explicit in the LLVM IR.  If you
 475 violate this rule, the verifier will emit an error.
 476
 477 <p>Finally, the CodeGen function returns the phi node as the value computed by
 478 the if/then/else expression.  In our example above, this returned value will
 479 feed into the code for the top-level function, which will create the return
 480 instruction.</p>
 481
 482 <p>Overall, we now have the ability to execute conditional code in
 483 Kaleidoscope.  With this extension, Kaleidoscope is a fairly complete language
 484 that can calculate a wide variety of numeric functions.  Next up we'll add
 485 another useful expression that is familiar from non-functional languages...</p>
 486
 487 </div>
 488
 489 </div>
 490
 491 <!-- *********************************************************************** -->
 492 <h2><a name="for">'for' Loop Expression</a></h2>
 493 <!-- *********************************************************************** -->
 494
 495 <div>
 496
 497 <p>Now that we know how to add basic control flow constructs to the language,
 498 we have the tools to add more powerful things.  Lets add something more
 499 aggressive, a 'for' expression:</p>
 500
 501 <div class="doc_code">
 502 <pre>
 503  extern putchard(char);
 504  def printstar(n)
 505    for i = 1, i &lt; n, 1.0 in
 506      putchard(42);  # ascii 42 = '*'
 507
 508  # print 100 '*' characters
 509  printstar(100);
 510 </pre>
 511 </div>
 512
 513 <p>This expression defines a new variable ("i" in this case) which iterates from
 514 a starting value, while the condition ("i &lt; n" in this case) is true,
 515 incrementing by an optional step value ("1.0" in this case).  If the step value
 516 is omitted, it defaults to 1.0.  While the loop is true, it executes its
 517 body expression.  Because we don't have anything better to return, we'll just
 518 define the loop as always returning 0.0.  In the future when we have mutable
 519 variables, it will get more useful.</p>
 520
 521 <p>As before, lets talk about the changes that we need to Kaleidoscope to
 522 support this.</p>
 523
 524 <!-- ======================================================================= -->
 525 <h4><a name="forlexer">Lexer Extensions for the 'for' Loop</a></h4>
 526 <!-- ======================================================================= -->
 527
 528 <div>
 529
 530 <p>The lexer extensions are the same sort of thing as for if/then/else:</p>
 531
 532 <div class="doc_code">
 533 <pre>
 534   ... in Token.token ...
 535   (* control *)
 536   | If | Then | Else
 537   <b>| For | In</b>
 538
 539   ... in Lexer.lex_ident...
 540       match Buffer.contents buffer with
 541       | "def" -&gt; [&lt; 'Token.Def; stream &gt;]
 542       | "extern" -&gt; [&lt; 'Token.Extern; stream &gt;]
 543       | "if" -&gt; [&lt; 'Token.If; stream &gt;]
 544       | "then" -&gt; [&lt; 'Token.Then; stream &gt;]
 545       | "else" -&gt; [&lt; 'Token.Else; stream &gt;]
 546       <b>| "for" -&gt; [&lt; 'Token.For; stream &gt;]
 547       | "in" -&gt; [&lt; 'Token.In; stream &gt;]</b>
 548       | id -&gt; [&lt; 'Token.Ident id; stream &gt;]
 549 </pre>
 550 </div>
 551
 552 </div>
 553
 554 <!-- ======================================================================= -->
 555 <h4><a name="forast">AST Extensions for the 'for' Loop</a></h4>
 556 <!-- ======================================================================= -->
 557
 558 <div>
 559
 560 <p>The AST variant is just as simple.  It basically boils down to capturing
 561 the variable name and the constituent expressions in the node.</p>
 562
 563 <div class="doc_code">
 564 <pre>
 565 type expr =
 566   ...
 567   (* variant for for/in. *)
 568   | For of string * expr * expr * expr option * expr
 569 </pre>
 570 </div>
 571
 572 </div>
 573
 574 <!-- ======================================================================= -->
 575 <h4><a name="forparser">Parser Extensions for the 'for' Loop</a></h4>
 576 <!-- ======================================================================= -->
 577
 578 <div>
 579
 580 <p>The parser code is also fairly standard.  The only interesting thing here is
 581 handling of the optional step value.  The parser code handles it by checking to
 582 see if the second comma is present.  If not, it sets the step value to null in
 583 the AST node:</p>
 584
 585 <div class="doc_code">
 586 <pre>
 587 let rec parse_primary = parser
 588   ...
 589   (* forexpr
 590         ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
 591   | [&lt; 'Token.For;
 592        'Token.Ident id ?? "expected identifier after for";
 593        'Token.Kwd '=' ?? "expected '=' after for";
 594        stream &gt;] -&gt;
 595       begin parser
 596         | [&lt;
 597              start=parse_expr;
 598              'Token.Kwd ',' ?? "expected ',' after for";
 599              end_=parse_expr;
 600              stream &gt;] -&gt;
 601             let step =
 602               begin parser
 603               | [&lt; 'Token.Kwd ','; step=parse_expr &gt;] -&gt; Some step
 604               | [&lt; &gt;] -&gt; None
 605               end stream
 606             in
 607             begin parser
 608             | [&lt; 'Token.In; body=parse_expr &gt;] -&gt;
 609                 Ast.For (id, start, end_, step, body)
 610             | [&lt; &gt;] -&gt;
 611                 raise (Stream.Error "expected 'in' after for")
 612             end stream
 613         | [&lt; &gt;] -&gt;
 614             raise (Stream.Error "expected '=' after for")
 615       end stream
 616 </pre>
 617 </div>
 618
 619 </div>
 620
 621 <!-- ======================================================================= -->
 622 <h4><a name="forir">LLVM IR for the 'for' Loop</a></h4>
 623 <!-- ======================================================================= -->
 624
 625 <div>
 626
 627 <p>Now we get to the good part: the LLVM IR we want to generate for this thing.
 628 With the simple example above, we get this LLVM IR (note that this dump is
 629 generated with optimizations disabled for clarity):
 630 </p>
 631
 632 <div class="doc_code">
 633 <pre>
 634 declare double @putchard(double)
 635
 636 define double @printstar(double %n) {
 637 entry:
 638         ; initial value = 1.0 (inlined into phi)
 639   br label %loop
 640
 641 loop:    ; preds = %loop, %entry
 642   %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
 643         ; body
 644   %calltmp = call double @putchard(double 4.200000e+01)
 645         ; increment
 646   %nextvar = fadd double %i, 1.000000e+00
 647
 648         ; termination test
 649   %cmptmp = fcmp ult double %i, %n
 650   %booltmp = uitofp i1 %cmptmp to double
 651   %loopcond = fcmp one double %booltmp, 0.000000e+00
 652   br i1 %loopcond, label %loop, label %afterloop
 653
 654 afterloop:    ; preds = %loop
 655         ; loop always returns 0.0
 656   ret double 0.000000e+00
 657 }
 658 </pre>
 659 </div>
 660
 661 <p>This loop contains all the same constructs we saw before: a phi node, several
 662 expressions, and some basic blocks.  Lets see how this fits together.</p>
 663
 664 </div>
 665
 666 <!-- ======================================================================= -->
 667 <h4><a name="forcodegen">Code Generation for the 'for' Loop</a></h4>
 668 <!-- ======================================================================= -->
 669
 670 <div>
 671
 672 <p>The first part of Codegen is very simple: we just output the start expression
 673 for the loop value:</p>
 674
 675 <div class="doc_code">
 676 <pre>
 677 let rec codegen_expr = function
 678   ...
 679   | Ast.For (var_name, start, end_, step, body) -&gt;
 680       (* Emit the start code first, without 'variable' in scope. *)
 681       let start_val = codegen_expr start in
 682 </pre>
 683 </div>
 684
 685 <p>With this out of the way, the next step is to set up the LLVM basic block
 686 for the start of the loop body.  In the case above, the whole loop body is one
 687 block, but remember that the body code itself could consist of multiple blocks
 688 (e.g. if it contains an if/then/else or a for/in expression).</p>
 689
 690 <div class="doc_code">
 691 <pre>
 692       (* Make the new basic block for the loop header, inserting after current
 693        * block. *)
 694       let preheader_bb = insertion_block builder in
 695       let the_function = block_parent preheader_bb in
 696       let loop_bb = append_block context "loop" the_function in
 697
 698       (* Insert an explicit fall through from the current block to the
 699        * loop_bb. *)
 700       ignore (build_br loop_bb builder);
 701 </pre>
 702 </div>
 703
 704 <p>This code is similar to what we saw for if/then/else.  Because we will need
 705 it to create the Phi node, we remember the block that falls through into the
 706 loop.  Once we have that, we create the actual block that starts the loop and
 707 create an unconditional branch for the fall-through between the two blocks.</p>
 708
 709 <div class="doc_code">
 710 <pre>
 711       (* Start insertion in loop_bb. *)
 712       position_at_end loop_bb builder;
 713
 714       (* Start the PHI node with an entry for start. *)
 715       let variable = build_phi [(start_val, preheader_bb)] var_name builder in
 716 </pre>
 717 </div>
 718
 719 <p>Now that the "preheader" for the loop is set up, we switch to emitting code
 720 for the loop body.  To begin with, we move the insertion point and create the
 721 PHI node for the loop induction variable.  Since we already know the incoming
 722 value for the starting value, we add it to the Phi node.  Note that the Phi will
 723 eventually get a second value for the backedge, but we can't set it up yet
 724 (because it doesn't exist!).</p>
 725
 726 <div class="doc_code">
 727 <pre>
 728       (* Within the loop, the variable is defined equal to the PHI node. If it
 729        * shadows an existing variable, we have to restore it, so save it
 730        * now. *)
 731       let old_val =
 732         try Some (Hashtbl.find named_values var_name) with Not_found -&gt; None
 733       in
 734       Hashtbl.add named_values var_name variable;
 735
 736       (* Emit the body of the loop.  This, like any other expr, can change the
 737        * current BB.  Note that we ignore the value computed by the body, but
 738        * don't allow an error *)
 739       ignore (codegen_expr body);
 740 </pre>
 741 </div>
 742
 743 <p>Now the code starts to get more interesting.  Our 'for' loop introduces a new
 744 variable to the symbol table.  This means that our symbol table can now contain
 745 either function arguments or loop variables.  To handle this, before we codegen
 746 the body of the loop, we add the loop variable as the current value for its
 747 name.  Note that it is possible that there is a variable of the same name in the
 748 outer scope.  It would be easy to make this an error (emit an error and return
 749 null if there is already an entry for VarName) but we choose to allow shadowing
 750 of variables.  In order to handle this correctly, we remember the Value that
 751 we are potentially shadowing in <tt>old_val</tt> (which will be None if there is
 752 no shadowed variable).</p>
 753
 754 <p>Once the loop variable is set into the symbol table, the code recursively
 755 codegen's the body.  This allows the body to use the loop variable: any
 756 references to it will naturally find it in the symbol table.</p>
 757
 758 <div class="doc_code">
 759 <pre>
 760       (* Emit the step value. *)
 761       let step_val =
 762         match step with
 763         | Some step -&gt; codegen_expr step
 764         (* If not specified, use 1.0. *)
 765         | None -&gt; const_float double_type 1.0
 766       in
 767
 768       let next_var = build_add variable step_val "nextvar" builder in
 769 </pre>
 770 </div>
 771
 772 <p>Now that the body is emitted, we compute the next value of the iteration
 773 variable by adding the step value, or 1.0 if it isn't present.
 774 '<tt>next_var</tt>' will be the value of the loop variable on the next iteration
 775 of the loop.</p>
 776
 777 <div class="doc_code">
 778 <pre>
 779       (* Compute the end condition. *)
 780       let end_cond = codegen_expr end_ in
 781
 782       (* Convert condition to a bool by comparing equal to 0.0. *)
 783       let zero = const_float double_type 0.0 in
 784       let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
 785 </pre>
 786 </div>
 787
 788 <p>Finally, we evaluate the exit value of the loop, to determine whether the
 789 loop should exit.  This mirrors the condition evaluation for the if/then/else
 790 statement.</p>
 791
 792 <div class="doc_code">
 793 <pre>
 794       (* Create the "after loop" block and insert it. *)
 795       let loop_end_bb = insertion_block builder in
 796       let after_bb = append_block context "afterloop" the_function in
 797
 798       (* Insert the conditional branch into the end of loop_end_bb. *)
 799       ignore (build_cond_br end_cond loop_bb after_bb builder);
 800
 801       (* Any new code will be inserted in after_bb. *)
 802       position_at_end after_bb builder;
 803 </pre>
 804 </div>
 805
 806 <p>With the code for the body of the loop complete, we just need to finish up
 807 the control flow for it.  This code remembers the end block (for the phi node), then creates the block for the loop exit ("afterloop").  Based on the value of the
 808 exit condition, it creates a conditional branch that chooses between executing
 809 the loop again and exiting the loop.  Any future code is emitted in the
 810 "afterloop" block, so it sets the insertion position to it.</p>
 811
 812 <div class="doc_code">
 813 <pre>
 814       (* Add a new entry to the PHI node for the backedge. *)
 815       add_incoming (next_var, loop_end_bb) variable;
 816
 817       (* Restore the unshadowed variable. *)
 818       begin match old_val with
 819       | Some old_val -&gt; Hashtbl.add named_values var_name old_val
 820       | None -&gt; ()
 821       end;
 822
 823       (* for expr always returns 0.0. *)
 824       const_null double_type
 825 </pre>
 826 </div>
 827
 828 <p>The final code handles various cleanups: now that we have the
 829 "<tt>next_var</tt>" value, we can add the incoming value to the loop PHI node.
 830 After that, we remove the loop variable from the symbol table, so that it isn't
 831 in scope after the for loop.  Finally, code generation of the for loop always
 832 returns 0.0, so that is what we return from <tt>Codegen.codegen_expr</tt>.</p>
 833
 834 <p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
 835 the tutorial.  In this chapter we added two control flow constructs, and used
 836 them to motivate a couple of aspects of the LLVM IR that are important for
 837 front-end implementors to know.  In the next chapter of our saga, we will get
 838 a bit crazier and add <a href="OCamlLangImpl6.html">user-defined operators</a>
 839 to our poor innocent language.</p>
 840
 841 </div>
 842
 843 </div>
 844
 845 <!-- *********************************************************************** -->
 846 <h2><a name="code">Full Code Listing</a></h2>
 847 <!-- *********************************************************************** -->
 848
 849 <div>
 850
 851 <p>
 852 Here is the complete code listing for our running example, enhanced with the
 853 if/then/else and for expressions..  To build this example, use:
 854 </p>
 855
 856 <div class="doc_code">
 857 <pre>
 858 # Compile
 859 ocamlbuild toy.byte
 860 # Run
 861 ./toy.byte
 862 </pre>
 863 </div>
 864
 865 <p>Here is the code:</p>
 866
 867 <dl>
 868 <dt>_tags:</dt>
 869 <dd class="doc_code">
 870 <pre>
 871 &lt;{lexer,parser}.ml&gt;: use_camlp4, pp(camlp4of)
 872 &lt;*.{byte,native}&gt;: g++, use_llvm, use_llvm_analysis
 873 &lt;*.{byte,native}&gt;: use_llvm_executionengine, use_llvm_target
 874 &lt;*.{byte,native}&gt;: use_llvm_scalar_opts, use_bindings
 875 </pre>
 876 </dd>
 877
 878 <dt>myocamlbuild.ml:</dt>
 879 <dd class="doc_code">
 880 <pre>
 881 open Ocamlbuild_plugin;;
 882
 883 ocaml_lib ~extern:true "llvm";;
 884 ocaml_lib ~extern:true "llvm_analysis";;
 885 ocaml_lib ~extern:true "llvm_executionengine";;
 886 ocaml_lib ~extern:true "llvm_target";;
 887 ocaml_lib ~extern:true "llvm_scalar_opts";;
 888
 889 flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
 890 dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
 891 </pre>
 892 </dd>
 893
 894 <dt>token.ml:</dt>
 895 <dd class="doc_code">
 896 <pre>
 897 (*===----------------------------------------------------------------------===
 898  * Lexer Tokens
 899  *===----------------------------------------------------------------------===*)
 900
 901 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
 902  * these others for known things. *)
 903 type token =
 904   (* commands *)
 905   | Def | Extern
 906
 907   (* primary *)
 908   | Ident of string | Number of float
 909
 910   (* unknown *)
 911   | Kwd of char
 912
 913   (* control *)
 914   | If | Then | Else
 915   | For | In
 916 </pre>
 917 </dd>
 918
 919 <dt>lexer.ml:</dt>
 920 <dd class="doc_code">
 921 <pre>
 922 (*===----------------------------------------------------------------------===
 923  * Lexer
 924  *===----------------------------------------------------------------------===*)
 925
 926 let rec lex = parser
 927   (* Skip any whitespace. *)
 928   | [&lt; ' (' ' | '\n' | '\r' | '\t'); stream &gt;] -&gt; lex stream
 929
 930   (* identifier: [a-zA-Z][a-zA-Z0-9] *)
 931   | [&lt; ' ('A' .. 'Z' | 'a' .. 'z' as c); stream &gt;] -&gt;
 932       let buffer = Buffer.create 1 in
 933       Buffer.add_char buffer c;
 934       lex_ident buffer stream
 935
 936   (* number: [0-9.]+ *)
 937   | [&lt; ' ('0' .. '9' as c); stream &gt;] -&gt;
 938       let buffer = Buffer.create 1 in
 939       Buffer.add_char buffer c;
 940       lex_number buffer stream
 941
 942   (* Comment until end of line. *)
 943   | [&lt; ' ('#'); stream &gt;] -&gt;
 944       lex_comment stream
 945
 946   (* Otherwise, just return the character as its ascii value. *)
 947   | [&lt; 'c; stream &gt;] -&gt;
 948       [&lt; 'Token.Kwd c; lex stream &gt;]
 949
 950   (* end of stream. *)
 951   | [&lt; &gt;] -&gt; [&lt; &gt;]
 952
 953 and lex_number buffer = parser
 954   | [&lt; ' ('0' .. '9' | '.' as c); stream &gt;] -&gt;
 955       Buffer.add_char buffer c;
 956       lex_number buffer stream
 957   | [&lt; stream=lex &gt;] -&gt;
 958       [&lt; 'Token.Number (float_of_string (Buffer.contents buffer)); stream &gt;]
 959
 960 and lex_ident buffer = parser
 961   | [&lt; ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream &gt;] -&gt;
 962       Buffer.add_char buffer c;
 963       lex_ident buffer stream
 964   | [&lt; stream=lex &gt;] -&gt;
 965       match Buffer.contents buffer with
 966       | "def" -&gt; [&lt; 'Token.Def; stream &gt;]
 967       | "extern" -&gt; [&lt; 'Token.Extern; stream &gt;]
 968       | "if" -&gt; [&lt; 'Token.If; stream &gt;]
 969       | "then" -&gt; [&lt; 'Token.Then; stream &gt;]
 970       | "else" -&gt; [&lt; 'Token.Else; stream &gt;]
 971       | "for" -&gt; [&lt; 'Token.For; stream &gt;]
 972       | "in" -&gt; [&lt; 'Token.In; stream &gt;]
 973       | id -&gt; [&lt; 'Token.Ident id; stream &gt;]
 974
 975 and lex_comment = parser
 976   | [&lt; ' ('\n'); stream=lex &gt;] -&gt; stream
 977   | [&lt; 'c; e=lex_comment &gt;] -&gt; e
 978   | [&lt; &gt;] -&gt; [&lt; &gt;]
 979 </pre>
 980 </dd>
 981
 982 <dt>ast.ml:</dt>
 983 <dd class="doc_code">
 984 <pre>
 985 (*===----------------------------------------------------------------------===
 986  * Abstract Syntax Tree (aka Parse Tree)
 987  *===----------------------------------------------------------------------===*)
 988
 989 (* expr - Base type for all expression nodes. *)
 990 type expr =
 991   (* variant for numeric literals like "1.0". *)
 992   | Number of float
 993
 994   (* variant for referencing a variable, like "a". *)
 995   | Variable of string
 996
 997   (* variant for a binary operator. *)
 998   | Binary of char * expr * expr
 999
1000   (* variant for function calls. *)
1001   | Call of string * expr array
1002
1003   (* variant for if/then/else. *)
1004   | If of expr * expr * expr
1005
1006   (* variant for for/in. *)
1007   | For of string * expr * expr * expr option * expr
1008
1009 (* proto - This type represents the "prototype" for a function, which captures
1010  * its name, and its argument names (thus implicitly the number of arguments the
1011  * function takes). *)
1012 type proto = Prototype of string * string array
1013
1014 (* func - This type represents a function definition itself. *)
1015 type func = Function of proto * expr
1016 </pre>
1017 </dd>
1018
1019 <dt>parser.ml:</dt>
1020 <dd class="doc_code">
1021 <pre>
1022 (*===---------------------------------------------------------------------===
1023  * Parser
1024  *===---------------------------------------------------------------------===*)
1025
1026 (* binop_precedence - This holds the precedence for each binary operator that is
1027  * defined *)
1028 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
1029
1030 (* precedence - Get the precedence of the pending binary operator token. *)
1031 let precedence c = try Hashtbl.find binop_precedence c with Not_found -&gt; -1
1032
1033 (* primary
1034  *   ::= identifier
1035  *   ::= numberexpr
1036  *   ::= parenexpr
1037  *   ::= ifexpr
1038  *   ::= forexpr *)
1039 let rec parse_primary = parser
1040   (* numberexpr ::= number *)
1041   | [&lt; 'Token.Number n &gt;] -&gt; Ast.Number n
1042
1043   (* parenexpr ::= '(' expression ')' *)
1044   | [&lt; 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" &gt;] -&gt; e
1045
1046   (* identifierexpr
1047    *   ::= identifier
1048    *   ::= identifier '(' argumentexpr ')' *)
1049   | [&lt; 'Token.Ident id; stream &gt;] -&gt;
1050       let rec parse_args accumulator = parser
1051         | [&lt; e=parse_expr; stream &gt;] -&gt;
1052             begin parser
1053               | [&lt; 'Token.Kwd ','; e=parse_args (e :: accumulator) &gt;] -&gt; e
1054               | [&lt; &gt;] -&gt; e :: accumulator
1055             end stream
1056         | [&lt; &gt;] -&gt; accumulator
1057       in
1058       let rec parse_ident id = parser
1059         (* Call. *)
1060         | [&lt; 'Token.Kwd '(';
1061              args=parse_args [];
1062              'Token.Kwd ')' ?? "expected ')'"&gt;] -&gt;
1063             Ast.Call (id, Array.of_list (List.rev args))
1064
1065         (* Simple variable ref. *)
1066         | [&lt; &gt;] -&gt; Ast.Variable id
1067       in
1068       parse_ident id stream
1069
1070   (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
1071   | [&lt; 'Token.If; c=parse_expr;
1072        'Token.Then ?? "expected 'then'"; t=parse_expr;
1073        'Token.Else ?? "expected 'else'"; e=parse_expr &gt;] -&gt;
1074       Ast.If (c, t, e)
1075
1076   (* forexpr
1077         ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
1078   | [&lt; 'Token.For;
1079        'Token.Ident id ?? "expected identifier after for";
1080        'Token.Kwd '=' ?? "expected '=' after for";
1081        stream &gt;] -&gt;
1082       begin parser
1083         | [&lt;
1084              start=parse_expr;
1085              'Token.Kwd ',' ?? "expected ',' after for";
1086              end_=parse_expr;
1087              stream &gt;] -&gt;
1088             let step =
1089               begin parser
1090               | [&lt; 'Token.Kwd ','; step=parse_expr &gt;] -&gt; Some step
1091               | [&lt; &gt;] -&gt; None
1092               end stream
1093             in
1094             begin parser
1095             | [&lt; 'Token.In; body=parse_expr &gt;] -&gt;
1096                 Ast.For (id, start, end_, step, body)
1097             | [&lt; &gt;] -&gt;
1098                 raise (Stream.Error "expected 'in' after for")
1099             end stream
1100         | [&lt; &gt;] -&gt;
1101             raise (Stream.Error "expected '=' after for")
1102       end stream
1103
1104   | [&lt; &gt;] -&gt; raise (Stream.Error "unknown token when expecting an expression.")
1105
1106 (* binoprhs
1107  *   ::= ('+' primary)* *)
1108 and parse_bin_rhs expr_prec lhs stream =
1109   match Stream.peek stream with
1110   (* If this is a binop, find its precedence. *)
1111   | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c -&gt;
1112       let token_prec = precedence c in
1113
1114       (* If this is a binop that binds at least as tightly as the current binop,
1115        * consume it, otherwise we are done. *)
1116       if token_prec &lt; expr_prec then lhs else begin
1117         (* Eat the binop. *)
1118         Stream.junk stream;
1119
1120         (* Parse the primary expression after the binary operator. *)
1121         let rhs = parse_primary stream in
1122
1123         (* Okay, we know this is a binop. *)
1124         let rhs =
1125           match Stream.peek stream with
1126           | Some (Token.Kwd c2) -&gt;
1127               (* If BinOp binds less tightly with rhs than the operator after
1128                * rhs, let the pending operator take rhs as its lhs. *)
1129               let next_prec = precedence c2 in
1130               if token_prec &lt; next_prec
1131               then parse_bin_rhs (token_prec + 1) rhs stream
1132               else rhs
1133           | _ -&gt; rhs
1134         in
1135
1136         (* Merge lhs/rhs. *)
1137         let lhs = Ast.Binary (c, lhs, rhs) in
1138         parse_bin_rhs expr_prec lhs stream
1139       end
1140   | _ -&gt; lhs
1141
1142 (* expression
1143  *   ::= primary binoprhs *)
1144 and parse_expr = parser
1145   | [&lt; lhs=parse_primary; stream &gt;] -&gt; parse_bin_rhs 0 lhs stream
1146
1147 (* prototype
1148  *   ::= id '(' id* ')' *)
1149 let parse_prototype =
1150   let rec parse_args accumulator = parser
1151     | [&lt; 'Token.Ident id; e=parse_args (id::accumulator) &gt;] -&gt; e
1152     | [&lt; &gt;] -&gt; accumulator
1153   in
1154
1155   parser
1156   | [&lt; 'Token.Ident id;
1157        'Token.Kwd '(' ?? "expected '(' in prototype";
1158        args=parse_args [];
1159        'Token.Kwd ')' ?? "expected ')' in prototype" &gt;] -&gt;
1160       (* success. *)
1161       Ast.Prototype (id, Array.of_list (List.rev args))
1162
1163   | [&lt; &gt;] -&gt;
1164       raise (Stream.Error "expected function name in prototype")
1165
1166 (* definition ::= 'def' prototype expression *)
1167 let parse_definition = parser
1168   | [&lt; 'Token.Def; p=parse_prototype; e=parse_expr &gt;] -&gt;
1169       Ast.Function (p, e)
1170
1171 (* toplevelexpr ::= expression *)
1172 let parse_toplevel = parser
1173   | [&lt; e=parse_expr &gt;] -&gt;
1174       (* Make an anonymous proto. *)
1175       Ast.Function (Ast.Prototype ("", [||]), e)
1176
1177 (*  external ::= 'extern' prototype *)
1178 let parse_extern = parser
1179   | [&lt; 'Token.Extern; e=parse_prototype &gt;] -&gt; e
1180 </pre>
1181 </dd>
1182
1183 <dt>codegen.ml:</dt>
1184 <dd class="doc_code">
1185 <pre>
1186 (*===----------------------------------------------------------------------===
1187  * Code Generation
1188  *===----------------------------------------------------------------------===*)
1189
1190 open Llvm
1191
1192 exception Error of string
1193
1194 let context = global_context ()
1195 let the_module = create_module context "my cool jit"
1196 let builder = builder context
1197 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
1198 let double_type = double_type context
1199
1200 let rec codegen_expr = function
1201   | Ast.Number n -&gt; const_float double_type n
1202   | Ast.Variable name -&gt;
1203       (try Hashtbl.find named_values name with
1204         | Not_found -&gt; raise (Error "unknown variable name"))
1205   | Ast.Binary (op, lhs, rhs) -&gt;
1206       let lhs_val = codegen_expr lhs in
1207       let rhs_val = codegen_expr rhs in
1208       begin
1209         match op with
1210         | '+' -&gt; build_add lhs_val rhs_val "addtmp" builder
1211         | '-' -&gt; build_sub lhs_val rhs_val "subtmp" builder
1212         | '*' -&gt; build_mul lhs_val rhs_val "multmp" builder
1213         | '&lt;' -&gt;
1214             (* Convert bool 0/1 to double 0.0 or 1.0 *)
1215             let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
1216             build_uitofp i double_type "booltmp" builder
1217         | _ -&gt; raise (Error "invalid binary operator")
1218       end
1219   | Ast.Call (callee, args) -&gt;
1220       (* Look up the name in the module table. *)
1221       let callee =
1222         match lookup_function callee the_module with
1223         | Some callee -&gt; callee
1224         | None -&gt; raise (Error "unknown function referenced")
1225       in
1226       let params = params callee in
1227
1228       (* If argument mismatch error. *)
1229       if Array.length params == Array.length args then () else
1230         raise (Error "incorrect # arguments passed");
1231       let args = Array.map codegen_expr args in
1232       build_call callee args "calltmp" builder
1233   | Ast.If (cond, then_, else_) -&gt;
1234       let cond = codegen_expr cond in
1235
1236       (* Convert condition to a bool by comparing equal to 0.0 *)
1237       let zero = const_float double_type 0.0 in
1238       let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
1239
1240       (* Grab the first block so that we might later add the conditional branch
1241        * to it at the end of the function. *)
1242       let start_bb = insertion_block builder in
1243       let the_function = block_parent start_bb in
1244
1245       let then_bb = append_block context "then" the_function in
1246
1247       (* Emit 'then' value. *)
1248       position_at_end then_bb builder;
1249       let then_val = codegen_expr then_ in
1250
1251       (* Codegen of 'then' can change the current block, update then_bb for the
1252        * phi. We create a new name because one is used for the phi node, and the
1253        * other is used for the conditional branch. *)
1254       let new_then_bb = insertion_block builder in
1255
1256       (* Emit 'else' value. *)
1257       let else_bb = append_block context "else" the_function in
1258       position_at_end else_bb builder;
1259       let else_val = codegen_expr else_ in
1260
1261       (* Codegen of 'else' can change the current block, update else_bb for the
1262        * phi. *)
1263       let new_else_bb = insertion_block builder in
1264
1265       (* Emit merge block. *)
1266       let merge_bb = append_block context "ifcont" the_function in
1267       position_at_end merge_bb builder;
1268       let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
1269       let phi = build_phi incoming "iftmp" builder in
1270
1271       (* Return to the start block to add the conditional branch. *)
1272       position_at_end start_bb builder;
1273       ignore (build_cond_br cond_val then_bb else_bb builder);
1274
1275       (* Set a unconditional branch at the end of the 'then' block and the
1276        * 'else' block to the 'merge' block. *)
1277       position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
1278       position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
1279
1280       (* Finally, set the builder to the end of the merge block. *)
1281       position_at_end merge_bb builder;
1282
1283       phi
1284   | Ast.For (var_name, start, end_, step, body) -&gt;
1285       (* Emit the start code first, without 'variable' in scope. *)
1286       let start_val = codegen_expr start in
1287
1288       (* Make the new basic block for the loop header, inserting after current
1289        * block. *)
1290       let preheader_bb = insertion_block builder in
1291       let the_function = block_parent preheader_bb in
1292       let loop_bb = append_block context "loop" the_function in
1293
1294       (* Insert an explicit fall through from the current block to the
1295        * loop_bb. *)
1296       ignore (build_br loop_bb builder);
1297
1298       (* Start insertion in loop_bb. *)
1299       position_at_end loop_bb builder;
1300
1301       (* Start the PHI node with an entry for start. *)
1302       let variable = build_phi [(start_val, preheader_bb)] var_name builder in
1303
1304       (* Within the loop, the variable is defined equal to the PHI node. If it
1305        * shadows an existing variable, we have to restore it, so save it
1306        * now. *)
1307       let old_val =
1308         try Some (Hashtbl.find named_values var_name) with Not_found -&gt; None
1309       in
1310       Hashtbl.add named_values var_name variable;
1311
1312       (* Emit the body of the loop.  This, like any other expr, can change the
1313        * current BB.  Note that we ignore the value computed by the body, but
1314        * don't allow an error *)
1315       ignore (codegen_expr body);
1316
1317       (* Emit the step value. *)
1318       let step_val =
1319         match step with
1320         | Some step -&gt; codegen_expr step
1321         (* If not specified, use 1.0. *)
1322         | None -&gt; const_float double_type 1.0
1323       in
1324
1325       let next_var = build_add variable step_val "nextvar" builder in
1326
1327       (* Compute the end condition. *)
1328       let end_cond = codegen_expr end_ in
1329
1330       (* Convert condition to a bool by comparing equal to 0.0. *)
1331       let zero = const_float double_type 0.0 in
1332       let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
1333
1334       (* Create the "after loop" block and insert it. *)
1335       let loop_end_bb = insertion_block builder in
1336       let after_bb = append_block context "afterloop" the_function in
1337
1338       (* Insert the conditional branch into the end of loop_end_bb. *)
1339       ignore (build_cond_br end_cond loop_bb after_bb builder);
1340
1341       (* Any new code will be inserted in after_bb. *)
1342       position_at_end after_bb builder;
1343
1344       (* Add a new entry to the PHI node for the backedge. *)
1345       add_incoming (next_var, loop_end_bb) variable;
1346
1347       (* Restore the unshadowed variable. *)
1348       begin match old_val with
1349       | Some old_val -&gt; Hashtbl.add named_values var_name old_val
1350       | None -&gt; ()
1351       end;
1352
1353       (* for expr always returns 0.0. *)
1354       const_null double_type
1355
1356 let codegen_proto = function
1357   | Ast.Prototype (name, args) -&gt;
1358       (* Make the function type: double(double,double) etc. *)
1359       let doubles = Array.make (Array.length args) double_type in
1360       let ft = function_type double_type doubles in
1361       let f =
1362         match lookup_function name the_module with
1363         | None -&gt; declare_function name ft the_module
1364
1365         (* If 'f' conflicted, there was already something named 'name'. If it
1366          * has a body, don't allow redefinition or reextern. *)
1367         | Some f -&gt;
1368             (* If 'f' already has a body, reject this. *)
1369             if block_begin f &lt;&gt; At_end f then
1370               raise (Error "redefinition of function");
1371
1372             (* If 'f' took a different number of arguments, reject. *)
1373             if element_type (type_of f) &lt;&gt; ft then
1374               raise (Error "redefinition of function with different # args");
1375             f
1376       in
1377
1378       (* Set names for all arguments. *)
1379       Array.iteri (fun i a -&gt;
1380         let n = args.(i) in
1381         set_value_name n a;
1382         Hashtbl.add named_values n a;
1383       ) (params f);
1384       f
1385
1386 let codegen_func the_fpm = function
1387   | Ast.Function (proto, body) -&gt;
1388       Hashtbl.clear named_values;
1389       let the_function = codegen_proto proto in
1390
1391       (* Create a new basic block to start insertion into. *)
1392       let bb = append_block context "entry" the_function in
1393       position_at_end bb builder;
1394
1395       try
1396         let ret_val = codegen_expr body in
1397
1398         (* Finish off the function. *)
1399         let _ = build_ret ret_val builder in
1400
1401         (* Validate the generated code, checking for consistency. *)
1402         Llvm_analysis.assert_valid_function the_function;
1403
1404         (* Optimize the function. *)
1405         let _ = PassManager.run_function the_function the_fpm in
1406
1407         the_function
1408       with e -&gt;
1409         delete_function the_function;
1410         raise e
1411 </pre>
1412 </dd>
1413
1414 <dt>toplevel.ml:</dt>
1415 <dd class="doc_code">
1416 <pre>
1417 (*===----------------------------------------------------------------------===
1418  * Top-Level parsing and JIT Driver
1419  *===----------------------------------------------------------------------===*)
1420
1421 open Llvm
1422 open Llvm_executionengine
1423
1424 (* top ::= definition | external | expression | ';' *)
1425 let rec main_loop the_fpm the_execution_engine stream =
1426   match Stream.peek stream with
1427   | None -&gt; ()
1428
1429   (* ignore top-level semicolons. *)
1430   | Some (Token.Kwd ';') -&gt;
1431       Stream.junk stream;
1432       main_loop the_fpm the_execution_engine stream
1433
1434   | Some token -&gt;
1435       begin
1436         try match token with
1437         | Token.Def -&gt;
1438             let e = Parser.parse_definition stream in
1439             print_endline "parsed a function definition.";
1440             dump_value (Codegen.codegen_func the_fpm e);
1441         | Token.Extern -&gt;
1442             let e = Parser.parse_extern stream in
1443             print_endline "parsed an extern.";
1444             dump_value (Codegen.codegen_proto e);
1445         | _ -&gt;
1446             (* Evaluate a top-level expression into an anonymous function. *)
1447             let e = Parser.parse_toplevel stream in
1448             print_endline "parsed a top-level expr";
1449             let the_function = Codegen.codegen_func the_fpm e in
1450             dump_value the_function;
1451
1452             (* JIT the function, returning a function pointer. *)
1453             let result = ExecutionEngine.run_function the_function [||]
1454               the_execution_engine in
1455
1456             print_string "Evaluated to ";
1457             print_float (GenericValue.as_float Codegen.double_type result);
1458             print_newline ();
1459         with Stream.Error s | Codegen.Error s -&gt;
1460           (* Skip token for error recovery. *)
1461           Stream.junk stream;
1462           print_endline s;
1463       end;
1464       print_string "ready&gt; "; flush stdout;
1465       main_loop the_fpm the_execution_engine stream
1466 </pre>
1467 </dd>
1468
1469 <dt>toy.ml:</dt>
1470 <dd class="doc_code">
1471 <pre>
1472 (*===----------------------------------------------------------------------===
1473  * Main driver code.
1474  *===----------------------------------------------------------------------===*)
1475
1476 open Llvm
1477 open Llvm_executionengine
1478 open Llvm_target
1479 open Llvm_scalar_opts
1480
1481 let main () =
1482   ignore (initialize_native_target ());
1483
1484   (* Install standard binary operators.
1485    * 1 is the lowest precedence. *)
1486   Hashtbl.add Parser.binop_precedence '&lt;' 10;
1487   Hashtbl.add Parser.binop_precedence '+' 20;
1488   Hashtbl.add Parser.binop_precedence '-' 20;
1489   Hashtbl.add Parser.binop_precedence '*' 40;    (* highest. *)
1490
1491   (* Prime the first token. *)
1492   print_string "ready&gt; "; flush stdout;
1493   let stream = Lexer.lex (Stream.of_channel stdin) in
1494
1495   (* Create the JIT. *)
1496   let the_execution_engine = ExecutionEngine.create Codegen.the_module in
1497   let the_fpm = PassManager.create_function Codegen.the_module in
1498
1499   (* Set up the optimizer pipeline.  Start with registering info about how the
1500    * target lays out data structures. *)
1501   TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
1502
1503   (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
1504   add_instruction_combination the_fpm;
1505
1506   (* reassociate expressions. *)
1507   add_reassociation the_fpm;
1508
1509   (* Eliminate Common SubExpressions. *)
1510   add_gvn the_fpm;
1511
1512   (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
1513   add_cfg_simplification the_fpm;
1514
1515   ignore (PassManager.initialize the_fpm);
1516
1517   (* Run the main "interpreter loop" now. *)
1518   Toplevel.main_loop the_fpm the_execution_engine stream;
1519
1520   (* Print out all the generated code. *)
1521   dump_module Codegen.the_module
1522 ;;
1523
1524 main ()
1525 </pre>
1526 </dd>
1527
1528 <dt>bindings.c</dt>
1529 <dd class="doc_code">
1530 <pre>
1531 #include &lt;stdio.h&gt;
1532
1533 /* putchard - putchar that takes a double and returns 0. */
1534 extern double putchard(double X) {
1535   putchar((char)X);
1536   return 0;
1537 }
1538 </pre>
1539 </dd>
1540 </dl>
1541
1542 <a href="OCamlLangImpl6.html">Next: Extending the language: user-defined
1543 operators</a>
1544 </div>
1545
1546 <!-- *********************************************************************** -->
1547 <hr>
1548 <address>
1549   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1550   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1551   <a href="http://validator.w3.org/check/referer"><img
1552   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1553
1554   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1555   <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br>
1556   <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
1557   Last modified: $Date$
1558 </address>
1559 </body>
1560 </html>