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="../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 (a] nondot.org">Chris Lattner</a> 50 and <a href="mailto:idadesub (a] 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 < 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" -> [< 'Token.Def; stream >] 140 | "extern" -> [< 'Token.Extern; stream >] 141 | "if" -> [< 'Token.If; stream >] 142 | "then" -> [< 'Token.Then; stream >] 143 | "else" -> [< 'Token.Else; stream >] 144 | "for" -> [< 'Token.For; stream >] 145 | "in" -> [< 'Token.In; stream >] 146 | id -> [< 'Token.Ident id; stream >] 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 | [< 'Token.If; c=parse_expr; 189 'Token.Then ?? "expected 'then'"; t=parse_expr; 190 'Token.Else ?? "expected 'else'"; e=parse_expr >] -> 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 | [< 'Token.If; c=parse_expr; 203 'Token.Then ?? "expected 'then'"; t=parse_expr; 204 'Token.Else ?? "expected 'else'"; e=parse_expr >] -> 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 < 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_) -> 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 < 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 < 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" -> [< 'Token.Def; stream >] 542 | "extern" -> [< 'Token.Extern; stream >] 543 | "if" -> [< 'Token.If; stream >] 544 | "then" -> [< 'Token.Then; stream >] 545 | "else" -> [< 'Token.Else; stream >] 546 <b>| "for" -> [< 'Token.For; stream >] 547 | "in" -> [< 'Token.In; stream >]</b> 548 | id -> [< 'Token.Ident id; stream >] 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 | [< 'Token.For; 592 'Token.Ident id ?? "expected identifier after for"; 593 'Token.Kwd '=' ?? "expected '=' after for"; 594 stream >] -> 595 begin parser 596 | [< 597 start=parse_expr; 598 'Token.Kwd ',' ?? "expected ',' after for"; 599 end_=parse_expr; 600 stream >] -> 601 let step = 602 begin parser 603 | [< 'Token.Kwd ','; step=parse_expr >] -> Some step 604 | [< >] -> None 605 end stream 606 in 607 begin parser 608 | [< 'Token.In; body=parse_expr >] -> 609 Ast.For (id, start, end_, step, body) 610 | [< >] -> 611 raise (Stream.Error "expected 'in' after for") 612 end stream 613 | [< >] -> 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) -> 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 -> 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 -> codegen_expr step 764 (* If not specified, use 1.0. *) 765 | None -> 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 -> Hashtbl.add named_values var_name old_val 820 | None -> () 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 <{lexer,parser}.ml>: use_camlp4, pp(camlp4of) 872 <*.{byte,native}>: g++, use_llvm, use_llvm_analysis 873 <*.{byte,native}>: use_llvm_executionengine, use_llvm_target 874 <*.{byte,native}>: 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 | [< ' (' ' | '\n' | '\r' | '\t'); stream >] -> lex stream 929 930 (* identifier: [a-zA-Z][a-zA-Z0-9] *) 931 | [< ' ('A' .. 'Z' | 'a' .. 'z' as c); stream >] -> 932 let buffer = Buffer.create 1 in 933 Buffer.add_char buffer c; 934 lex_ident buffer stream 935 936 (* number: [0-9.]+ *) 937 | [< ' ('0' .. '9' as c); stream >] -> 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 | [< ' ('#'); stream >] -> 944 lex_comment stream 945 946 (* Otherwise, just return the character as its ascii value. *) 947 | [< 'c; stream >] -> 948 [< 'Token.Kwd c; lex stream >] 949 950 (* end of stream. *) 951 | [< >] -> [< >] 952 953 and lex_number buffer = parser 954 | [< ' ('0' .. '9' | '.' as c); stream >] -> 955 Buffer.add_char buffer c; 956 lex_number buffer stream 957 | [< stream=lex >] -> 958 [< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >] 959 960 and lex_ident buffer = parser 961 | [< ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream >] -> 962 Buffer.add_char buffer c; 963 lex_ident buffer stream 964 | [< stream=lex >] -> 965 match Buffer.contents buffer with 966 | "def" -> [< 'Token.Def; stream >] 967 | "extern" -> [< 'Token.Extern; stream >] 968 | "if" -> [< 'Token.If; stream >] 969 | "then" -> [< 'Token.Then; stream >] 970 | "else" -> [< 'Token.Else; stream >] 971 | "for" -> [< 'Token.For; stream >] 972 | "in" -> [< 'Token.In; stream >] 973 | id -> [< 'Token.Ident id; stream >] 974 975 and lex_comment = parser 976 | [< ' ('\n'); stream=lex >] -> stream 977 | [< 'c; e=lex_comment >] -> e 978 | [< >] -> [< >] 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 -> -1 1032 1033 (* primary 1034 * ::= identifier 1035 * ::= numberexpr 1036 * ::= parenexpr 1037 * ::= ifexpr 1038 * ::= forexpr *) 1039 let rec parse_primary = parser 1040 (* numberexpr ::= number *) 1041 | [< 'Token.Number n >] -> Ast.Number n 1042 1043 (* parenexpr ::= '(' expression ')' *) 1044 | [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e 1045 1046 (* identifierexpr 1047 * ::= identifier 1048 * ::= identifier '(' argumentexpr ')' *) 1049 | [< 'Token.Ident id; stream >] -> 1050 let rec parse_args accumulator = parser 1051 | [< e=parse_expr; stream >] -> 1052 begin parser 1053 | [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e 1054 | [< >] -> e :: accumulator 1055 end stream 1056 | [< >] -> accumulator 1057 in 1058 let rec parse_ident id = parser 1059 (* Call. *) 1060 | [< 'Token.Kwd '('; 1061 args=parse_args []; 1062 'Token.Kwd ')' ?? "expected ')'">] -> 1063 Ast.Call (id, Array.of_list (List.rev args)) 1064 1065 (* Simple variable ref. *) 1066 | [< >] -> Ast.Variable id 1067 in 1068 parse_ident id stream 1069 1070 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *) 1071 | [< 'Token.If; c=parse_expr; 1072 'Token.Then ?? "expected 'then'"; t=parse_expr; 1073 'Token.Else ?? "expected 'else'"; e=parse_expr >] -> 1074 Ast.If (c, t, e) 1075 1076 (* forexpr 1077 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *) 1078 | [< 'Token.For; 1079 'Token.Ident id ?? "expected identifier after for"; 1080 'Token.Kwd '=' ?? "expected '=' after for"; 1081 stream >] -> 1082 begin parser 1083 | [< 1084 start=parse_expr; 1085 'Token.Kwd ',' ?? "expected ',' after for"; 1086 end_=parse_expr; 1087 stream >] -> 1088 let step = 1089 begin parser 1090 | [< 'Token.Kwd ','; step=parse_expr >] -> Some step 1091 | [< >] -> None 1092 end stream 1093 in 1094 begin parser 1095 | [< 'Token.In; body=parse_expr >] -> 1096 Ast.For (id, start, end_, step, body) 1097 | [< >] -> 1098 raise (Stream.Error "expected 'in' after for") 1099 end stream 1100 | [< >] -> 1101 raise (Stream.Error "expected '=' after for") 1102 end stream 1103 1104 | [< >] -> 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 -> 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 < 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) -> 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 < next_prec 1131 then parse_bin_rhs (token_prec + 1) rhs stream 1132 else rhs 1133 | _ -> 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 | _ -> lhs 1141 1142 (* expression 1143 * ::= primary binoprhs *) 1144 and parse_expr = parser 1145 | [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream 1146 1147 (* prototype 1148 * ::= id '(' id* ')' *) 1149 let parse_prototype = 1150 let rec parse_args accumulator = parser 1151 | [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e 1152 | [< >] -> accumulator 1153 in 1154 1155 parser 1156 | [< 'Token.Ident id; 1157 'Token.Kwd '(' ?? "expected '(' in prototype"; 1158 args=parse_args []; 1159 'Token.Kwd ')' ?? "expected ')' in prototype" >] -> 1160 (* success. *) 1161 Ast.Prototype (id, Array.of_list (List.rev args)) 1162 1163 | [< >] -> 1164 raise (Stream.Error "expected function name in prototype") 1165 1166 (* definition ::= 'def' prototype expression *) 1167 let parse_definition = parser 1168 | [< 'Token.Def; p=parse_prototype; e=parse_expr >] -> 1169 Ast.Function (p, e) 1170 1171 (* toplevelexpr ::= expression *) 1172 let parse_toplevel = parser 1173 | [< e=parse_expr >] -> 1174 (* Make an anonymous proto. *) 1175 Ast.Function (Ast.Prototype ("", [||]), e) 1176 1177 (* external ::= 'extern' prototype *) 1178 let parse_extern = parser 1179 | [< 'Token.Extern; e=parse_prototype >] -> 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 -> const_float double_type n 1202 | Ast.Variable name -> 1203 (try Hashtbl.find named_values name with 1204 | Not_found -> raise (Error "unknown variable name")) 1205 | Ast.Binary (op, lhs, rhs) -> 1206 let lhs_val = codegen_expr lhs in 1207 let rhs_val = codegen_expr rhs in 1208 begin 1209 match op with 1210 | '+' -> build_add lhs_val rhs_val "addtmp" builder 1211 | '-' -> build_sub lhs_val rhs_val "subtmp" builder 1212 | '*' -> build_mul lhs_val rhs_val "multmp" builder 1213 | '<' -> 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 | _ -> raise (Error "invalid binary operator") 1218 end 1219 | Ast.Call (callee, args) -> 1220 (* Look up the name in the module table. *) 1221 let callee = 1222 match lookup_function callee the_module with 1223 | Some callee -> callee 1224 | None -> 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_) -> 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) -> 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 -> 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 -> codegen_expr step 1321 (* If not specified, use 1.0. *) 1322 | None -> 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 -> Hashtbl.add named_values var_name old_val 1350 | None -> () 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) -> 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 -> 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 -> 1368 (* If 'f' already has a body, reject this. *) 1369 if block_begin f <> 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) <> 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 -> 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) -> 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 -> 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 -> () 1428 1429 (* ignore top-level semicolons. *) 1430 | Some (Token.Kwd ';') -> 1431 Stream.junk stream; 1432 main_loop the_fpm the_execution_engine stream 1433 1434 | Some token -> 1435 begin 1436 try match token with 1437 | Token.Def -> 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 -> 1442 let e = Parser.parse_extern stream in 1443 print_endline "parsed an extern."; 1444 dump_value (Codegen.codegen_proto e); 1445 | _ -> 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 -> 1460 (* Skip token for error recovery. *) 1461 Stream.junk stream; 1462 print_endline s; 1463 end; 1464 print_string "ready> "; 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 '<' 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> "; 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 <stdio.h> 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 (a] nondot.org">Chris Lattner</a><br> 1555 <a href="mailto:idadesub (a] 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> 1561
