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