| blob | 7146a5cacde0cd94df54e99a34458dce95e9ef72 |
4 <html>
5 <head>
6 <title>Kaleidoscope: Extending the Language: Mutable Variables / SSA
7 construction</title>
12 </head>
14 <body>
18 <ul>
21 <ol>
27 Mutation</a></li>
31 </ol>
32 </li>
34 tidbits</li>
35 </ul>
38 <p>
41 </p>
42 </div>
44 <!-- *********************************************************************** -->
46 <!-- *********************************************************************** -->
52 respectable, albeit simple, <a
54 programming language</a>. In our journey, we learned some parsing techniques,
55 how to build and represent an AST, how to build LLVM IR, and how to optimize
56 the resultant code as well as JIT compile it.</p>
58 <p>While Kaleidoscope is interesting as a functional language, the fact that it
59 is functional makes it "too easy" to generate LLVM IR for it. In particular, a
60 functional language makes it very easy to build LLVM IR directly in <a
62 Since LLVM requires that the input code be in SSA form, this is a very nice
63 property and it is often unclear to newcomers how to generate code for an
64 imperative language with mutable variables.</p>
66 <p>The short (and happy) summary of this chapter is that there is no need for
67 your front-end to build SSA form: LLVM provides highly tuned and well tested
68 support for this, though the way it works is a bit unexpected for some.</p>
70 </div>
72 <!-- *********************************************************************** -->
74 <!-- *********************************************************************** -->
78 <p>
79 To understand why mutable variables cause complexities in SSA construction,
80 consider this extremely simple C example:
81 </p>
84 <pre>
85 int G, H;
86 int test(_Bool Condition) {
87 int X;
88 if (Condition)
89 X = G;
90 else
91 X = H;
92 return X;
93 }
94 </pre>
95 </div>
98 executed in the program. Because there are two different possible values for X
99 before the return instruction, a PHI node is inserted to merge the two values.
100 The LLVM IR that we want for this example looks like this:</p>
103 <pre>
104 @G = weak global i32 0 ; type of @G is i32*
105 @H = weak global i32 0 ; type of @H is i32*
107 define i32 @test(i1 %Condition) {
108 entry:
109 br i1 %Condition, label %cond_true, label %cond_false
111 cond_true:
112 %X.0 = load i32* @G
113 br label %cond_next
115 cond_false:
116 %X.1 = load i32* @H
117 br label %cond_next
119 cond_next:
121 ret i32 %X.2
122 }
123 </pre>
124 </div>
126 <p>In this example, the loads from the G and H global variables are explicit in
127 the LLVM IR, and they live in the then/else branches of the if statement
128 (cond_true/cond_false). In order to merge the incoming values, the X.2 phi node
129 in the cond_next block selects the right value to use based on where control
130 flow is coming from: if control flow comes from the cond_false block, X.2 gets
131 the value of X.1. Alternatively, if control flow comes from cond_true, it gets
132 the value of X.0. The intent of this chapter is not to explain the details of
133 SSA form. For more information, see one of the many <a
138 assignments to mutable variables?". The issue here is that LLVM
140 However, SSA construction requires non-trivial algorithms and data structures,
141 so it is inconvenient and wasteful for every front-end to have to reproduce this
142 logic.</p>
144 </div>
146 <!-- *********************************************************************** -->
148 <!-- *********************************************************************** -->
152 <p>The 'trick' here is that while LLVM does require all register values to be
153 in SSA form, it does not require (or permit) memory objects to be in SSA form.
154 In the example above, note that the loads from G and H are direct accesses to
155 G and H: they are not renamed or versioned. This differs from some other
156 compiler systems, which do try to version memory objects. In LLVM, instead of
157 encoding dataflow analysis of memory into the LLVM IR, it is handled with <a
159 demand.</p>
161 <p>
162 With this in mind, the high-level idea is that we want to make a stack variable
163 (which lives in memory, because it is on the stack) for each mutable object in
164 a function. To take advantage of this trick, we need to talk about how LLVM
165 represents stack variables.
166 </p>
168 <p>In LLVM, all memory accesses are explicit with load/store instructions, and
169 it is carefully designed not to have (or need) an "address-of" operator. Notice
170 how the type of the @G/@H global variables is actually "i32*" even though the
173 address for that space. Stack variables work the same way, except that instead of
174 being declared with global variable definitions, they are declared with the
178 <pre>
179 define i32 @example() {
180 entry:
181 %X = alloca i32 ; type of %X is i32*.
182 ...
183 %tmp = load i32* %X ; load the stack value %X from the stack.
184 %tmp2 = add i32 %tmp, 1 ; increment it
185 store i32 %tmp2, i32* %X ; store it back
186 ...
187 </pre>
188 </div>
190 <p>This code shows an example of how you can declare and manipulate a stack
191 variable in the LLVM IR. Stack memory allocated with the alloca instruction is
192 fully general: you can pass the address of the stack slot to functions, you can
193 store it in other variables, etc. In our example above, we could rewrite the
194 example to use the alloca technique to avoid using a PHI node:</p>
197 <pre>
198 @G = weak global i32 0 ; type of @G is i32*
199 @H = weak global i32 0 ; type of @H is i32*
201 define i32 @test(i1 %Condition) {
202 entry:
203 %X = alloca i32 ; type of %X is i32*.
204 br i1 %Condition, label %cond_true, label %cond_false
206 cond_true:
207 %X.0 = load i32* @G
208 store i32 %X.0, i32* %X ; Update X
209 br label %cond_next
211 cond_false:
212 %X.1 = load i32* @H
213 store i32 %X.1, i32* %X ; Update X
214 br label %cond_next
216 cond_next:
217 %X.2 = load i32* %X ; Read X
218 ret i32 %X.2
219 }
220 </pre>
221 </div>
223 <p>With this, we have discovered a way to handle arbitrary mutable variables
224 without the need to create Phi nodes at all:</p>
226 <ol>
231 </ol>
233 <p>While this solution has solved our immediate problem, it introduced another
234 one: we have now apparently introduced a lot of stack traffic for very simple
235 and common operations, a major performance problem. Fortunately for us, the
236 LLVM optimizer has a highly-tuned optimization pass named "mem2reg" that handles
237 this case, promoting allocas like this into SSA registers, inserting Phi nodes
238 as appropriate. If you run this example through the pass, for example, you'll
239 get:</p>
242 <pre>
244 @G = weak global i32 0
245 @H = weak global i32 0
247 define i32 @test(i1 %Condition) {
248 entry:
249 br i1 %Condition, label %cond_true, label %cond_false
251 cond_true:
252 %X.0 = load i32* @G
253 br label %cond_next
255 cond_false:
256 %X.1 = load i32* @H
257 br label %cond_next
259 cond_next:
261 ret i32 %X.01
262 }
263 </pre>
264 </div>
267 algorithm for constructing SSA form and has a number of optimizations that speed
268 up (very common) degenerate cases. The mem2reg optimization pass is the answer
269 to dealing with mutable variables, and we highly recommend that you depend on
270 it. Note that mem2reg only works on variables in certain circumstances:</p>
272 <ol>
273 <li>mem2reg is alloca-driven: it looks for allocas and if it can handle them, it
274 promotes them. It does not apply to global variables or heap allocations.</li>
276 <li>mem2reg only looks for alloca instructions in the entry block of the
277 function. Being in the entry block guarantees that the alloca is only executed
278 once, which makes analysis simpler.</li>
280 <li>mem2reg only promotes allocas whose uses are direct loads and stores. If
281 the address of the stack object is passed to a function, or if any funny pointer
282 arithmetic is involved, the alloca will not be promoted.</li>
286 values (such as pointers, scalars and vectors), and only if the array size
287 of the allocation is 1 (or missing in the .ll file). mem2reg is not capable of
288 promoting structs or arrays to registers. Note that the "scalarrepl" pass is
291 </ol>
293 <p>
294 All of these properties are easy to satisfy for most imperative languages, and
295 we'll illustrate it below with Kaleidoscope. The final question you may be
296 asking is: should I bother with this nonsense for my front-end? Wouldn't it be
297 better if I just did SSA construction directly, avoiding use of the mem2reg
298 optimization pass? In short, we strongly recommend that you use this technique
299 for building SSA form, unless there is an extremely good reason not to. Using
300 this technique is:</p>
302 <ul>
303 <li>Proven and well tested: llvm-gcc and clang both use this technique for local
304 mutable variables. As such, the most common clients of LLVM are using this to
305 handle a bulk of their variables. You can be sure that bugs are found fast and
306 fixed early.</li>
308 <li>Extremely Fast: mem2reg has a number of special cases that make it fast in
309 common cases as well as fully general. For example, it has fast-paths for
310 variables that are only used in a single block, variables that only have one
311 assignment point, good heuristics to avoid insertion of unneeded phi nodes, etc.
312 </li>
315 Debug information in LLVM</a> relies on having the address of the variable
316 exposed so that debug info can be attached to it. This technique dovetails
317 very naturally with this style of debug info.</li>
318 </ul>
320 <p>If nothing else, this makes it much easier to get your front-end up and
321 running, and is very simple to implement. Lets extend Kaleidoscope with mutable
322 variables now!
323 </p>
325 </div>
327 <!-- *********************************************************************** -->
329 Kaleidoscope</a></div>
330 <!-- *********************************************************************** -->
334 <p>Now that we know the sort of problem we want to tackle, lets see what this
335 looks like in the context of our little Kaleidoscope language. We're going to
336 add two features:</p>
338 <ol>
341 </ol>
343 <p>While the first item is really what this is about, we only have variables
344 for incoming arguments as well as for induction variables, and redefining those only
345 goes so far :). Also, the ability to define new variables is a
346 useful thing regardless of whether you will be mutating them. Here's a
347 motivating example that shows how we could use these:</p>
350 <pre>
351 # Define ':' for sequencing: as a low-precedence operator that ignores operands
352 # and just returns the RHS.
353 def binary : 1 (x y) y;
355 # Recursive fib, we could do this before.
356 def fib(x)
358 1
359 else
362 # Iterative fib.
363 def fibi(x)
369 b;
371 # Call it.
372 fibi(10);
373 </pre>
374 </div>
376 <p>
377 In order to mutate variables, we have to change our existing variables to use
378 the "alloca trick". Once we have that, we'll add our new operator, then extend
379 Kaleidoscope to support new variable definitions.
380 </p>
382 </div>
384 <!-- *********************************************************************** -->
386 Mutation</a></div>
387 <!-- *********************************************************************** -->
391 <p>
392 The symbol table in Kaleidoscope is managed at code generation time by the
394 "Value*" that holds the double value for the named variable. In order to
395 support mutation, we need to change this slightly, so that it
397 question. Note that this change is a refactoring: it changes the structure of
398 the code, but does not (by itself) change the behavior of the compiler. All of
399 these changes are isolated in the Kaleidoscope code generator.</p>
401 <p>
402 At this point in Kaleidoscope's development, it only supports variables for two
403 things: incoming arguments to functions and the induction variable of 'for'
404 loops. For consistency, we'll allow mutation of these variables in addition to
405 other user-defined variables. This means that these will both need memory
406 locations.
407 </p>
409 <p>To start our transformation of Kaleidoscope, we'll change the
411 Once we do this, the C++ compiler will tell us what parts of the code we need to
412 update:</p>
416 future to be more type safe.</p>
419 <pre>
420 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
421 </pre>
422 </div>
424 <p>Also, since we will need to create these alloca's, we'll use a helper
425 function that ensures that the allocas are created in the entry block of the
426 function:</p>
429 <pre>
430 (* Create an alloca instruction in the entry block of the function. This
431 * is used for mutable variables etc. *)
432 let create_entry_block_alloca the_function var_name =
433 let builder = builder_at (instr_begin (entry_block the_function)) in
434 build_alloca double_type var_name builder
435 </pre>
436 </div>
439 pointing at the first instruction of the entry block. It then creates an alloca
440 with the expected name and returns it. Because all values in Kaleidoscope are
441 doubles, there is no need to pass in a type to use.</p>
443 <p>With this in place, the first functionality change we want to make is to
444 variable references. In our new scheme, variables live on the stack, so code
445 generating a reference to them actually needs to produce a load from the stack
446 slot:</p>
449 <pre>
450 let rec codegen_expr = function
451 ...
452 | Ast.Variable name ->
453 let v = try Hashtbl.find named_values name with
455 in
456 <b>(* Load the value. *)
457 build_load v name builder</b>
458 </pre>
459 </div>
461 <p>As you can see, this is pretty straightforward. Now we need to update the
462 things that define the variables to set up the alloca. We'll start with
464 for the unabridged code):</p>
467 <pre>
468 | Ast.For (var_name, start, end_, step, body) ->
469 let the_function = block_parent (insertion_block builder) in
471 (* Create an alloca for the variable in the entry block. *)
474 (* Emit the start code first, without 'variable' in scope. *)
475 let start_val = codegen_expr start in
477 <b>(* Store the value into the alloca. *)
478 ignore(build_store start_val alloca builder);</b>
480 ...
482 (* Within the loop, the variable is defined equal to the PHI node. If it
483 * shadows an existing variable, we have to restore it, so save it
484 * now. *)
485 let old_val =
486 try Some (Hashtbl.find named_values var_name) with Not_found -> None
487 in
490 ...
492 (* Compute the end condition. *)
493 let end_cond = codegen_expr end_ in
495 <b>(* Reload, increment, and restore the alloca. This handles the case where
496 * the body of the loop mutates the variable. *)
497 let cur_var = build_load alloca var_name builder in
498 let next_var = build_add cur_var step_val "nextvar" builder in
499 ignore(build_store next_var alloca builder);</b>
500 ...
501 </pre>
502 </div>
506 The big difference is that we no longer have to construct a PHI node, and we use
507 load/store to access the variable as needed.</p>
509 <p>To support mutable argument variables, we need to also make allocas for them.
510 The code for this is also pretty simple:</p>
513 <pre>
514 (* Create an alloca for each argument and register the argument in the symbol
515 * table so that references to it will succeed. *)
516 let create_argument_allocas the_function proto =
517 let args = match proto with
518 | Ast.Prototype (_, args) | Ast.BinOpPrototype (_, args, _) -> args
519 in
520 Array.iteri (fun i ai ->
521 let var_name = args.(i) in
522 (* Create an alloca for this variable. *)
523 let alloca = create_entry_block_alloca the_function var_name in
525 (* Store the initial value into the alloca. *)
526 ignore(build_store ai alloca builder);
528 (* Add arguments to variable symbol table. *)
529 Hashtbl.add named_values var_name alloca;
530 ) (params the_function)
531 </pre>
532 </div>
534 <p>For each argument, we make an alloca, store the input value to the function
535 into the alloca, and register the alloca as the memory location for the
537 it sets up the entry block for the function.</p>
539 <p>The final missing piece is adding the mem2reg pass, which allows us to get
540 good codegen once again:</p>
543 <pre>
544 let main () =
545 ...
546 let the_fpm = PassManager.create_function Codegen.the_module in
548 (* Set up the optimizer pipeline. Start with registering info about how the
549 * target lays out data structures. *)
550 TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
552 <b>(* Promote allocas to registers. *)
553 add_memory_to_register_promotion the_fpm;</b>
555 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
556 add_instruction_combining the_fpm;
558 (* reassociate expressions. *)
559 add_reassociation the_fpm;
560 </pre>
561 </div>
563 <p>It is interesting to see what the code looks like before and after the
564 mem2reg optimization runs. For example, this is the before/after code for our
565 recursive fib function. Before the optimization:</p>
568 <pre>
569 define double @fib(double %x) {
570 entry:
571 <b>%x1 = alloca double
572 store double %x, double* %x1
573 %x2 = load double* %x1</b>
574 %cmptmp = fcmp ult double %x2, 3.000000e+00
575 %booltmp = uitofp i1 %cmptmp to double
576 %ifcond = fcmp one double %booltmp, 0.000000e+00
577 br i1 %ifcond, label %then, label %else
579 then: ; preds = %entry
580 br label %ifcont
582 else: ; preds = %entry
584 %subtmp = fsub double %x3, 1.000000e+00
585 %calltmp = call double @fib(double %subtmp)
587 %subtmp5 = fsub double %x4, 2.000000e+00
588 %calltmp6 = call double @fib(double %subtmp5)
589 %addtmp = fadd double %calltmp, %calltmp6
590 br label %ifcont
592 ifcont: ; preds = %else, %then
593 %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
594 ret double %iftmp
595 }
596 </pre>
597 </div>
599 <p>Here there is only one variable (x, the input argument) but you can still
600 see the extremely simple-minded code generation strategy we are using. In the
601 entry block, an alloca is created, and the initial input value is stored into
602 it. Each reference to the variable does a reload from the stack. Also, note
603 that we didn't modify the if/then/else expression, so it still inserts a PHI
604 node. While we could make an alloca for it, it is actually easier to create a
605 PHI node for it, so we still just make the PHI.</p>
610 <pre>
611 define double @fib(double %x) {
612 entry:
614 %booltmp = uitofp i1 %cmptmp to double
615 %ifcond = fcmp one double %booltmp, 0.000000e+00
616 br i1 %ifcond, label %then, label %else
618 then:
619 br label %ifcont
621 else:
623 %calltmp = call double @fib(double %subtmp)
625 %calltmp6 = call double @fib(double %subtmp5)
626 %addtmp = fadd double %calltmp, %calltmp6
627 br label %ifcont
629 ifcont: ; preds = %else, %then
630 %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
631 ret double %iftmp
632 }
633 </pre>
634 </div>
636 <p>This is a trivial case for mem2reg, since there are no redefinitions of the
637 variable. The point of showing this is to calm your tension about inserting
638 such blatent inefficiencies :).</p>
643 <pre>
644 define double @fib(double %x) {
645 entry:
646 %cmptmp = fcmp ult double %x, 3.000000e+00
647 %booltmp = uitofp i1 %cmptmp to double
648 %ifcond = fcmp ueq double %booltmp, 0.000000e+00
649 br i1 %ifcond, label %else, label %ifcont
651 else:
652 %subtmp = fsub double %x, 1.000000e+00
653 %calltmp = call double @fib(double %subtmp)
654 %subtmp5 = fsub double %x, 2.000000e+00
655 %calltmp6 = call double @fib(double %subtmp5)
656 %addtmp = fadd double %calltmp, %calltmp6
657 ret double %addtmp
659 ifcont:
660 ret double 1.000000e+00
661 }
662 </pre>
663 </div>
665 <p>Here we see that the simplifycfg pass decided to clone the return instruction
666 into the end of the 'else' block. This allowed it to eliminate some branches
667 and the PHI node.</p>
669 <p>Now that all symbol table references are updated to use stack variables,
670 we'll add the assignment operator.</p>
672 </div>
674 <!-- *********************************************************************** -->
676 <!-- *********************************************************************** -->
680 <p>With our current framework, adding a new assignment operator is really
681 simple. We will parse it just like any other binary operator, but handle it
682 internally (instead of allowing the user to define it). The first step is to
683 set a precedence:</p>
686 <pre>
687 let main () =
688 (* Install standard binary operators.
689 * 1 is the lowest precedence. *)
692 Hashtbl.add Parser.binop_precedence '+' 20;
693 Hashtbl.add Parser.binop_precedence '-' 20;
694 ...
695 </pre>
696 </div>
698 <p>Now that the parser knows the precedence of the binary operator, it takes
699 care of all the parsing and AST generation. We just need to implement codegen
700 for the assignment operator. This looks like:</p>
703 <pre>
704 let rec codegen_expr = function
705 begin match op with
706 | '=' ->
707 (* Special case '=' because we don't want to emit the LHS as an
708 * expression. *)
709 let name =
710 match lhs with
711 | Ast.Variable name -> name
713 in
714 </pre>
715 </div>
717 <p>Unlike the rest of the binary operators, our assignment operator doesn't
718 follow the "emit LHS, emit RHS, do computation" model. As such, it is handled
719 as a special case before the other binary operators are handled. The other
720 strange thing is that it requires the LHS to be a variable. It is invalid to
722 </p>
726 <pre>
727 (* Codegen the rhs. *)
728 let val_ = codegen_expr rhs in
730 (* Lookup the name. *)
731 let variable = try Hashtbl.find named_values name with
733 in
734 ignore(build_store val_ variable builder);
735 val_
736 | _ ->
737 ...
738 </pre>
739 </div>
741 <p>Once we have the variable, codegen'ing the assignment is straightforward:
742 we emit the RHS of the assignment, create a store, and return the computed
745 <p>Now that we have an assignment operator, we can mutate loop variables and
746 arguments. For example, we can now run code like this:</p>
749 <pre>
750 # Function to print a double.
751 extern printd(x);
753 # Define ':' for sequencing: as a low-precedence operator that ignores operands
754 # and just returns the RHS.
755 def binary : 1 (x y) y;
757 def test(x)
758 printd(x) :
759 x = 4 :
760 printd(x);
762 test(123);
763 </pre>
764 </div>
767 actually mutate the value! Okay, we have now officially implemented our goal:
768 getting this to work requires SSA construction in the general case. However,
769 to be really useful, we want the ability to define our own local variables, lets
770 add this next!
771 </p>
773 </div>
775 <!-- *********************************************************************** -->
777 Variables</a></div>
778 <!-- *********************************************************************** -->
782 <p>Adding var/in is just like any other other extensions we made to
783 Kaleidoscope: we extend the lexer, the parser, the AST and the code generator.
784 The first step for adding our new 'var/in' construct is to extend the lexer.
785 As before, this is pretty trivial, the code looks like this:</p>
788 <pre>
789 type token =
790 ...
791 <b>(* var definition *)
792 | Var</b>
794 ...
796 and lex_ident buffer = parser
797 ...
802 ...
803 </pre>
804 </div>
806 <p>The next step is to define the AST node that we will construct. For var/in,
807 it looks like this:</p>
810 <pre>
811 type expr =
812 ...
813 (* variant for var/in. *)
814 | Var of (string * expr option) array * expr
815 ...
816 </pre>
817 </div>
819 <p>var/in allows a list of names to be defined all at once, and each name can
820 optionally have an initializer value. As such, we capture this information in
821 the VarNames vector. Also, var/in has a body, this body is allowed to access
822 the variables defined by the var/in.</p>
824 <p>With this in place, we can define the parser pieces. The first thing we do
825 is add it as a primary expression:</p>
828 <pre>
829 (* primary
830 * ::= identifier
831 * ::= numberexpr
832 * ::= parenexpr
833 * ::= ifexpr
834 * ::= forexpr
836 let rec parse_primary = parser
837 ...
838 <b>(* varexpr
839 * ::= 'var' identifier ('=' expression?
840 * (',' identifier ('=' expression)?)* 'in' expression *)
841 | [< 'Token.Var;
842 (* At least one variable name is required. *)
843 'Token.Ident id ?? "expected identifier after var";
844 init=parse_var_init;
845 var_names=parse_var_names [(id, init)];
846 (* At this point, we have to have 'in'. *)
847 'Token.In ?? "expected 'in' keyword after 'var'";
849 Ast.Var (Array.of_list (List.rev var_names), body)</b>
851 ...
853 and parse_var_init = parser
854 (* read in the optional initializer. *)
858 and parse_var_names accumulator = parser
859 | [< 'Token.Kwd ',';
860 'Token.Ident id ?? "expected identifier list after var";
861 init=parse_var_init;
864 </pre>
865 </div>
867 <p>Now that we can parse and represent the code, we need to support emission of
868 LLVM IR for it. This code starts out with:</p>
871 <pre>
872 let rec codegen_expr = function
873 ...
874 | Ast.Var (var_names, body)
875 let old_bindings = ref [] in
877 let the_function = block_parent (insertion_block builder) in
879 (* Register all variables and emit their initializer. *)
880 Array.iter (fun (var_name, init) ->
881 </pre>
882 </div>
884 <p>Basically it loops over all the variables, installing them one at a time.
885 For each variable we put into the symbol table, we remember the previous value
886 that we replace in OldBindings.</p>
889 <pre>
890 (* Emit the initializer before adding the variable to scope, this
891 * prevents the initializer from referencing the variable itself, and
892 * permits stuff like this:
893 * var a = 1 in
894 * var a = a in ... # refers to outer 'a'. *)
895 let init_val =
896 match init with
897 | Some init -> codegen_expr init
898 (* If not specified, use 0.0. *)
900 in
902 let alloca = create_entry_block_alloca the_function var_name in
903 ignore(build_store init_val alloca builder);
905 (* Remember the old variable binding so that we can restore the binding
906 * when we unrecurse. *)
908 begin
909 try
910 let old_value = Hashtbl.find named_values var_name in
911 old_bindings := (var_name, old_value) :: !old_bindings;
912 with Not_found > ()
913 end;
915 (* Remember this binding. *)
916 Hashtbl.add named_values var_name alloca;
917 ) var_names;
918 </pre>
919 </div>
921 <p>There are more comments here than code. The basic idea is that we emit the
922 initializer, create the alloca, then update the symbol table to point to it.
923 Once all the variables are installed in the symbol table, we evaluate the body
924 of the var/in expression:</p>
927 <pre>
928 (* Codegen the body, now that all vars are in scope. *)
929 let body_val = codegen_expr body in
930 </pre>
931 </div>
936 <pre>
937 (* Pop all our variables from scope. *)
938 List.iter (fun (var_name, old_value) ->
939 Hashtbl.add named_values var_name old_value
940 ) !old_bindings;
942 (* Return the body computation. *)
943 body_val
944 </pre>
945 </div>
947 <p>The end result of all of this is that we get properly scoped variable
948 definitions, and we even (trivially) allow mutation of them :).</p>
950 <p>With this, we completed what we set out to do. Our nice iterative fib
951 example from the intro compiles and runs just fine. The mem2reg pass optimizes
952 all of our stack variables into SSA registers, inserting PHI nodes where needed,
953 and our front-end remains simple: no "iterated dominance frontier" computation
954 anywhere in sight.</p>
956 </div>
958 <!-- *********************************************************************** -->
960 <!-- *********************************************************************** -->
964 <p>
965 Here is the complete code listing for our running example, enhanced with mutable
966 variables and var/in support. To build this example, use:
967 </p>
970 <pre>
971 # Compile
972 ocamlbuild toy.byte
973 # Run
974 ./toy.byte
975 </pre>
976 </div>
980 <dl>
983 <pre>
988 </pre>
989 </dd>
993 <pre>
994 open Ocamlbuild_plugin;;
996 ocaml_lib ~extern:true "llvm";;
997 ocaml_lib ~extern:true "llvm_analysis";;
998 ocaml_lib ~extern:true "llvm_executionengine";;
999 ocaml_lib ~extern:true "llvm_target";;
1000 ocaml_lib ~extern:true "llvm_scalar_opts";;
1004 </pre>
1005 </dd>
1009 <pre>
1010 (*===----------------------------------------------------------------------===
1011 * Lexer Tokens
1012 *===----------------------------------------------------------------------===*)
1014 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
1015 * these others for known things. *)
1016 type token =
1017 (* commands *)
1018 | Def | Extern
1020 (* primary *)
1021 | Ident of string | Number of float
1023 (* unknown *)
1024 | Kwd of char
1026 (* control *)
1027 | If | Then | Else
1028 | For | In
1030 (* operators *)
1031 | Binary | Unary
1033 (* var definition *)
1034 | Var
1035 </pre>
1036 </dd>
1040 <pre>
1041 (*===----------------------------------------------------------------------===
1042 * Lexer
1043 *===----------------------------------------------------------------------===*)
1045 let rec lex = parser
1046 (* Skip any whitespace. *)
1049 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
1051 let buffer = Buffer.create 1 in
1052 Buffer.add_char buffer c;
1053 lex_ident buffer stream
1057 let buffer = Buffer.create 1 in
1058 Buffer.add_char buffer c;
1059 lex_number buffer stream
1061 (* Comment until end of line. *)
1063 lex_comment stream
1065 (* Otherwise, just return the character as its ascii value. *)
1069 (* end of stream. *)
1072 and lex_number buffer = parser
1074 Buffer.add_char buffer c;
1075 lex_number buffer stream
1079 and lex_ident buffer = parser
1081 Buffer.add_char buffer c;
1082 lex_ident buffer stream
1084 match Buffer.contents buffer with
1097 and lex_comment = parser
1101 </pre>
1102 </dd>
1106 <pre>
1107 (*===----------------------------------------------------------------------===
1108 * Abstract Syntax Tree (aka Parse Tree)
1109 *===----------------------------------------------------------------------===*)
1111 (* expr - Base type for all expression nodes. *)
1112 type expr =
1113 (* variant for numeric literals like "1.0". *)
1114 | Number of float
1116 (* variant for referencing a variable, like "a". *)
1117 | Variable of string
1119 (* variant for a unary operator. *)
1120 | Unary of char * expr
1122 (* variant for a binary operator. *)
1123 | Binary of char * expr * expr
1125 (* variant for function calls. *)
1126 | Call of string * expr array
1128 (* variant for if/then/else. *)
1129 | If of expr * expr * expr
1131 (* variant for for/in. *)
1132 | For of string * expr * expr * expr option * expr
1134 (* variant for var/in. *)
1135 | Var of (string * expr option) array * expr
1137 (* proto - This type represents the "prototype" for a function, which captures
1138 * its name, and its argument names (thus implicitly the number of arguments the
1139 * function takes). *)
1140 type proto =
1141 | Prototype of string * string array
1142 | BinOpPrototype of string * string array * int
1144 (* func - This type represents a function definition itself. *)
1145 type func = Function of proto * expr
1146 </pre>
1147 </dd>
1151 <pre>
1152 (*===---------------------------------------------------------------------===
1153 * Parser
1154 *===---------------------------------------------------------------------===*)
1156 (* binop_precedence - This holds the precedence for each binary operator that is
1157 * defined *)
1158 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
1160 (* precedence - Get the precedence of the pending binary operator token. *)
1163 (* primary
1164 * ::= identifier
1165 * ::= numberexpr
1166 * ::= parenexpr
1167 * ::= ifexpr
1168 * ::= forexpr
1169 * ::= varexpr *)
1170 let rec parse_primary = parser
1171 (* numberexpr ::= number *)
1174 (* parenexpr ::= '(' expression ')' *)
1177 (* identifierexpr
1178 * ::= identifier
1179 * ::= identifier '(' argumentexpr ')' *)
1181 let rec parse_args accumulator = parser
1183 begin parser
1186 end stream
1188 in
1189 let rec parse_ident id = parser
1190 (* Call. *)
1191 | [< 'Token.Kwd '(';
1192 args=parse_args [];
1194 Ast.Call (id, Array.of_list (List.rev args))
1196 (* Simple variable ref. *)
1198 in
1199 parse_ident id stream
1201 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
1202 | [< 'Token.If; c=parse_expr;
1203 'Token.Then ?? "expected 'then'"; t=parse_expr;
1205 Ast.If (c, t, e)
1207 (* forexpr
1208 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
1209 | [< 'Token.For;
1210 'Token.Ident id ?? "expected identifier after for";
1211 'Token.Kwd '=' ?? "expected '=' after for";
1213 begin parser
1214 | [<
1215 start=parse_expr;
1216 'Token.Kwd ',' ?? "expected ',' after for";
1217 end_=parse_expr;
1219 let step =
1220 begin parser
1223 end stream
1224 in
1225 begin parser
1227 Ast.For (id, start, end_, step, body)
1229 raise (Stream.Error "expected 'in' after for")
1230 end stream
1232 raise (Stream.Error "expected '=' after for")
1233 end stream
1235 (* varexpr
1236 * ::= 'var' identifier ('=' expression?
1237 * (',' identifier ('=' expression)?)* 'in' expression *)
1238 | [< 'Token.Var;
1239 (* At least one variable name is required. *)
1240 'Token.Ident id ?? "expected identifier after var";
1241 init=parse_var_init;
1242 var_names=parse_var_names [(id, init)];
1243 (* At this point, we have to have 'in'. *)
1244 'Token.In ?? "expected 'in' keyword after 'var'";
1246 Ast.Var (Array.of_list (List.rev var_names), body)
1250 (* unary
1251 * ::= primary
1252 * ::= '!' unary *)
1253 and parse_unary = parser
1254 (* If this is a unary operator, read it. *)
1256 Ast.Unary (op, operand)
1258 (* If the current token is not an operator, it must be a primary expr. *)
1261 (* binoprhs
1262 * ::= ('+' primary)* *)
1263 and parse_bin_rhs expr_prec lhs stream =
1264 match Stream.peek stream with
1265 (* If this is a binop, find its precedence. *)
1266 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
1267 let token_prec = precedence c in
1269 (* If this is a binop that binds at least as tightly as the current binop,
1270 * consume it, otherwise we are done. *)
1271 if token_prec < expr_prec then lhs else begin
1272 (* Eat the binop. *)
1273 Stream.junk stream;
1275 (* Parse the primary expression after the binary operator. *)
1276 let rhs = parse_unary stream in
1278 (* Okay, we know this is a binop. *)
1279 let rhs =
1280 match Stream.peek stream with
1281 | Some (Token.Kwd c2) ->
1282 (* If BinOp binds less tightly with rhs than the operator after
1283 * rhs, let the pending operator take rhs as its lhs. *)
1284 let next_prec = precedence c2 in
1285 if token_prec < next_prec
1286 then parse_bin_rhs (token_prec + 1) rhs stream
1287 else rhs
1288 | _ -> rhs
1289 in
1291 (* Merge lhs/rhs. *)
1292 let lhs = Ast.Binary (c, lhs, rhs) in
1293 parse_bin_rhs expr_prec lhs stream
1294 end
1295 | _ -> lhs
1297 and parse_var_init = parser
1298 (* read in the optional initializer. *)
1302 and parse_var_names accumulator = parser
1303 | [< 'Token.Kwd ',';
1304 'Token.Ident id ?? "expected identifier list after var";
1305 init=parse_var_init;
1309 (* expression
1310 * ::= primary binoprhs *)
1311 and parse_expr = parser
1314 (* prototype
1315 * ::= id '(' id* ')'
1316 * ::= binary LETTER number? (id, id)
1317 * ::= unary LETTER number? (id) *)
1318 let parse_prototype =
1319 let rec parse_args accumulator = parser
1322 in
1323 let parse_operator = parser
1326 in
1327 let parse_binary_precedence = parser
1330 in
1331 parser
1332 | [< 'Token.Ident id;
1333 'Token.Kwd '(' ?? "expected '(' in prototype";
1334 args=parse_args [];
1336 (* success. *)
1337 Ast.Prototype (id, Array.of_list (List.rev args))
1338 | [< (prefix, kind)=parse_operator;
1339 'Token.Kwd op ?? "expected an operator";
1340 (* Read the precedence if present. *)
1341 binary_precedence=parse_binary_precedence;
1342 'Token.Kwd '(' ?? "expected '(' in prototype";
1343 args=parse_args [];
1345 let name = prefix ^ (String.make 1 op) in
1346 let args = Array.of_list (List.rev args) in
1348 (* Verify right number of arguments for operator. *)
1349 if Array.length args != kind
1350 then raise (Stream.Error "invalid number of operands for operator")
1351 else
1352 if kind == 1 then
1353 Ast.Prototype (name, args)
1354 else
1355 Ast.BinOpPrototype (name, args, binary_precedence)
1357 raise (Stream.Error "expected function name in prototype")
1359 (* definition ::= 'def' prototype expression *)
1360 let parse_definition = parser
1362 Ast.Function (p, e)
1364 (* toplevelexpr ::= expression *)
1365 let parse_toplevel = parser
1367 (* Make an anonymous proto. *)
1368 Ast.Function (Ast.Prototype ("", [||]), e)
1370 (* external ::= 'extern' prototype *)
1371 let parse_extern = parser
1373 </pre>
1374 </dd>
1378 <pre>
1379 (*===----------------------------------------------------------------------===
1380 * Code Generation
1381 *===----------------------------------------------------------------------===*)
1383 open Llvm
1385 exception Error of string
1387 let context = global_context ()
1388 let the_module = create_module context "my cool jit"
1389 let builder = builder context
1390 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
1391 let double_type = double_type context
1393 (* Create an alloca instruction in the entry block of the function. This
1394 * is used for mutable variables etc. *)
1395 let create_entry_block_alloca the_function var_name =
1396 let builder = builder_at context (instr_begin (entry_block the_function)) in
1397 build_alloca double_type var_name builder
1399 let rec codegen_expr = function
1400 | Ast.Number n -> const_float double_type n
1401 | Ast.Variable name ->
1402 let v = try Hashtbl.find named_values name with
1404 in
1405 (* Load the value. *)
1406 build_load v name builder
1407 | Ast.Unary (op, operand) ->
1408 let operand = codegen_expr operand in
1410 let callee =
1411 match lookup_function callee the_module with
1412 | Some callee -> callee
1414 in
1415 build_call callee [|operand|] "unop" builder
1416 | Ast.Binary (op, lhs, rhs) ->
1417 begin match op with
1418 | '=' ->
1419 (* Special case '=' because we don't want to emit the LHS as an
1420 * expression. *)
1421 let name =
1422 match lhs with
1423 | Ast.Variable name -> name
1425 in
1427 (* Codegen the rhs. *)
1428 let val_ = codegen_expr rhs in
1430 (* Lookup the name. *)
1431 let variable = try Hashtbl.find named_values name with
1433 in
1434 ignore(build_store val_ variable builder);
1435 val_
1436 | _ ->
1437 let lhs_val = codegen_expr lhs in
1438 let rhs_val = codegen_expr rhs in
1439 begin
1440 match op with
1446 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
1447 build_uitofp i double_type "booltmp" builder
1448 | _ ->
1449 (* If it wasn't a builtin binary operator, it must be a user defined
1450 * one. Emit a call to it. *)
1452 let callee =
1453 match lookup_function callee the_module with
1454 | Some callee -> callee
1456 in
1457 build_call callee [|lhs_val; rhs_val|] "binop" builder
1458 end
1459 end
1460 | Ast.Call (callee, args) ->
1461 (* Look up the name in the module table. *)
1462 let callee =
1463 match lookup_function callee the_module with
1464 | Some callee -> callee
1466 in
1467 let params = params callee in
1469 (* If argument mismatch error. *)
1470 if Array.length params == Array.length args then () else
1471 raise (Error "incorrect # arguments passed");
1472 let args = Array.map codegen_expr args in
1473 build_call callee args "calltmp" builder
1474 | Ast.If (cond, then_, else_) ->
1475 let cond = codegen_expr cond in
1477 (* Convert condition to a bool by comparing equal to 0.0 *)
1478 let zero = const_float double_type 0.0 in
1479 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
1481 (* Grab the first block so that we might later add the conditional branch
1482 * to it at the end of the function. *)
1483 let start_bb = insertion_block builder in
1484 let the_function = block_parent start_bb in
1486 let then_bb = append_block context "then" the_function in
1488 (* Emit 'then' value. *)
1489 position_at_end then_bb builder;
1490 let then_val = codegen_expr then_ in
1492 (* Codegen of 'then' can change the current block, update then_bb for the
1493 * phi. We create a new name because one is used for the phi node, and the
1494 * other is used for the conditional branch. *)
1495 let new_then_bb = insertion_block builder in
1497 (* Emit 'else' value. *)
1498 let else_bb = append_block context "else" the_function in
1499 position_at_end else_bb builder;
1500 let else_val = codegen_expr else_ in
1502 (* Codegen of 'else' can change the current block, update else_bb for the
1503 * phi. *)
1504 let new_else_bb = insertion_block builder in
1506 (* Emit merge block. *)
1507 let merge_bb = append_block context "ifcont" the_function in
1508 position_at_end merge_bb builder;
1509 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
1510 let phi = build_phi incoming "iftmp" builder in
1512 (* Return to the start block to add the conditional branch. *)
1513 position_at_end start_bb builder;
1514 ignore (build_cond_br cond_val then_bb else_bb builder);
1516 (* Set a unconditional branch at the end of the 'then' block and the
1517 * 'else' block to the 'merge' block. *)
1518 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
1519 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
1521 (* Finally, set the builder to the end of the merge block. *)
1522 position_at_end merge_bb builder;
1524 phi
1525 | Ast.For (var_name, start, end_, step, body) ->
1526 (* Output this as:
1527 * var = alloca double
1528 * ...
1529 * start = startexpr
1530 * store start -> var
1531 * goto loop
1532 * loop:
1533 * ...
1534 * bodyexpr
1535 * ...
1536 * loopend:
1537 * step = stepexpr
1538 * endcond = endexpr
1539 *
1540 * curvar = load var
1541 * nextvar = curvar + step
1542 * store nextvar -> var
1543 * br endcond, loop, endloop
1544 * outloop: *)
1546 let the_function = block_parent (insertion_block builder) in
1548 (* Create an alloca for the variable in the entry block. *)
1549 let alloca = create_entry_block_alloca the_function var_name in
1551 (* Emit the start code first, without 'variable' in scope. *)
1552 let start_val = codegen_expr start in
1554 (* Store the value into the alloca. *)
1555 ignore(build_store start_val alloca builder);
1557 (* Make the new basic block for the loop header, inserting after current
1558 * block. *)
1559 let loop_bb = append_block context "loop" the_function in
1561 (* Insert an explicit fall through from the current block to the
1562 * loop_bb. *)
1563 ignore (build_br loop_bb builder);
1565 (* Start insertion in loop_bb. *)
1566 position_at_end loop_bb builder;
1568 (* Within the loop, the variable is defined equal to the PHI node. If it
1569 * shadows an existing variable, we have to restore it, so save it
1570 * now. *)
1571 let old_val =
1572 try Some (Hashtbl.find named_values var_name) with Not_found -> None
1573 in
1574 Hashtbl.add named_values var_name alloca;
1576 (* Emit the body of the loop. This, like any other expr, can change the
1577 * current BB. Note that we ignore the value computed by the body, but
1578 * don't allow an error *)
1579 ignore (codegen_expr body);
1581 (* Emit the step value. *)
1582 let step_val =
1583 match step with
1584 | Some step -> codegen_expr step
1585 (* If not specified, use 1.0. *)
1587 in
1589 (* Compute the end condition. *)
1590 let end_cond = codegen_expr end_ in
1592 (* Reload, increment, and restore the alloca. This handles the case where
1593 * the body of the loop mutates the variable. *)
1594 let cur_var = build_load alloca var_name builder in
1595 let next_var = build_add cur_var step_val "nextvar" builder in
1596 ignore(build_store next_var alloca builder);
1598 (* Convert condition to a bool by comparing equal to 0.0. *)
1599 let zero = const_float double_type 0.0 in
1600 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
1602 (* Create the "after loop" block and insert it. *)
1603 let after_bb = append_block context "afterloop" the_function in
1605 (* Insert the conditional branch into the end of loop_end_bb. *)
1606 ignore (build_cond_br end_cond loop_bb after_bb builder);
1608 (* Any new code will be inserted in after_bb. *)
1609 position_at_end after_bb builder;
1611 (* Restore the unshadowed variable. *)
1612 begin match old_val with
1613 | Some old_val -> Hashtbl.add named_values var_name old_val
1614 | None -> ()
1615 end;
1617 (* for expr always returns 0.0. *)
1618 const_null double_type
1619 | Ast.Var (var_names, body) ->
1620 let old_bindings = ref [] in
1622 let the_function = block_parent (insertion_block builder) in
1624 (* Register all variables and emit their initializer. *)
1625 Array.iter (fun (var_name, init) ->
1626 (* Emit the initializer before adding the variable to scope, this
1627 * prevents the initializer from referencing the variable itself, and
1628 * permits stuff like this:
1629 * var a = 1 in
1630 * var a = a in ... # refers to outer 'a'. *)
1631 let init_val =
1632 match init with
1633 | Some init -> codegen_expr init
1634 (* If not specified, use 0.0. *)
1636 in
1638 let alloca = create_entry_block_alloca the_function var_name in
1639 ignore(build_store init_val alloca builder);
1641 (* Remember the old variable binding so that we can restore the binding
1642 * when we unrecurse. *)
1643 begin
1644 try
1645 let old_value = Hashtbl.find named_values var_name in
1646 old_bindings := (var_name, old_value) :: !old_bindings;
1647 with Not_found -> ()
1648 end;
1650 (* Remember this binding. *)
1651 Hashtbl.add named_values var_name alloca;
1652 ) var_names;
1654 (* Codegen the body, now that all vars are in scope. *)
1655 let body_val = codegen_expr body in
1657 (* Pop all our variables from scope. *)
1658 List.iter (fun (var_name, old_value) ->
1659 Hashtbl.add named_values var_name old_value
1660 ) !old_bindings;
1662 (* Return the body computation. *)
1663 body_val
1665 let codegen_proto = function
1666 | Ast.Prototype (name, args) | Ast.BinOpPrototype (name, args, _) ->
1667 (* Make the function type: double(double,double) etc. *)
1668 let doubles = Array.make (Array.length args) double_type in
1669 let ft = function_type double_type doubles in
1670 let f =
1671 match lookup_function name the_module with
1672 | None -> declare_function name ft the_module
1674 (* If 'f' conflicted, there was already something named 'name'. If it
1675 * has a body, don't allow redefinition or reextern. *)
1676 | Some f ->
1677 (* If 'f' already has a body, reject this. *)
1678 if block_begin f <> At_end f then
1679 raise (Error "redefinition of function");
1681 (* If 'f' took a different number of arguments, reject. *)
1682 if element_type (type_of f) <> ft then
1683 raise (Error "redefinition of function with different # args");
1684 f
1685 in
1687 (* Set names for all arguments. *)
1688 Array.iteri (fun i a ->
1689 let n = args.(i) in
1690 set_value_name n a;
1691 Hashtbl.add named_values n a;
1692 ) (params f);
1693 f
1695 (* Create an alloca for each argument and register the argument in the symbol
1696 * table so that references to it will succeed. *)
1697 let create_argument_allocas the_function proto =
1698 let args = match proto with
1699 | Ast.Prototype (_, args) | Ast.BinOpPrototype (_, args, _) -> args
1700 in
1701 Array.iteri (fun i ai ->
1702 let var_name = args.(i) in
1703 (* Create an alloca for this variable. *)
1704 let alloca = create_entry_block_alloca the_function var_name in
1706 (* Store the initial value into the alloca. *)
1707 ignore(build_store ai alloca builder);
1709 (* Add arguments to variable symbol table. *)
1710 Hashtbl.add named_values var_name alloca;
1711 ) (params the_function)
1713 let codegen_func the_fpm = function
1714 | Ast.Function (proto, body) ->
1715 Hashtbl.clear named_values;
1716 let the_function = codegen_proto proto in
1718 (* If this is an operator, install it. *)
1719 begin match proto with
1720 | Ast.BinOpPrototype (name, args, prec) ->
1721 let op = name.[String.length name - 1] in
1722 Hashtbl.add Parser.binop_precedence op prec;
1723 | _ -> ()
1724 end;
1726 (* Create a new basic block to start insertion into. *)
1727 let bb = append_block context "entry" the_function in
1728 position_at_end bb builder;
1730 try
1731 (* Add all arguments to the symbol table and create their allocas. *)
1732 create_argument_allocas the_function proto;
1734 let ret_val = codegen_expr body in
1736 (* Finish off the function. *)
1737 let _ = build_ret ret_val builder in
1739 (* Validate the generated code, checking for consistency. *)
1740 Llvm_analysis.assert_valid_function the_function;
1742 (* Optimize the function. *)
1743 let _ = PassManager.run_function the_function the_fpm in
1745 the_function
1746 with e ->
1747 delete_function the_function;
1748 raise e
1749 </pre>
1750 </dd>
1754 <pre>
1755 (*===----------------------------------------------------------------------===
1756 * Top-Level parsing and JIT Driver
1757 *===----------------------------------------------------------------------===*)
1759 open Llvm
1760 open Llvm_executionengine
1762 (* top ::= definition | external | expression | ';' *)
1763 let rec main_loop the_fpm the_execution_engine stream =
1764 match Stream.peek stream with
1765 | None -> ()
1767 (* ignore top-level semicolons. *)
1768 | Some (Token.Kwd ';') ->
1769 Stream.junk stream;
1770 main_loop the_fpm the_execution_engine stream
1772 | Some token ->
1773 begin
1774 try match token with
1775 | Token.Def ->
1776 let e = Parser.parse_definition stream in
1777 print_endline "parsed a function definition.";
1778 dump_value (Codegen.codegen_func the_fpm e);
1779 | Token.Extern ->
1780 let e = Parser.parse_extern stream in
1781 print_endline "parsed an extern.";
1782 dump_value (Codegen.codegen_proto e);
1783 | _ ->
1784 (* Evaluate a top-level expression into an anonymous function. *)
1785 let e = Parser.parse_toplevel stream in
1786 print_endline "parsed a top-level expr";
1787 let the_function = Codegen.codegen_func the_fpm e in
1788 dump_value the_function;
1790 (* JIT the function, returning a function pointer. *)
1791 let result = ExecutionEngine.run_function the_function [||]
1792 the_execution_engine in
1794 print_string "Evaluated to ";
1795 print_float (GenericValue.as_float Codegen.double_type result);
1796 print_newline ();
1797 with Stream.Error s | Codegen.Error s ->
1798 (* Skip token for error recovery. *)
1799 Stream.junk stream;
1800 print_endline s;
1801 end;
1802 print_string "ready> "; flush stdout;
1803 main_loop the_fpm the_execution_engine stream
1804 </pre>
1805 </dd>
1809 <pre>
1810 (*===----------------------------------------------------------------------===
1811 * Main driver code.
1812 *===----------------------------------------------------------------------===*)
1814 open Llvm
1815 open Llvm_executionengine
1816 open Llvm_target
1817 open Llvm_scalar_opts
1819 let main () =
1820 ignore (initialize_native_target ());
1822 (* Install standard binary operators.
1823 * 1 is the lowest precedence. *)
1824 Hashtbl.add Parser.binop_precedence '=' 2;
1826 Hashtbl.add Parser.binop_precedence '+' 20;
1827 Hashtbl.add Parser.binop_precedence '-' 20;
1828 Hashtbl.add Parser.binop_precedence '*' 40; (* highest. *)
1830 (* Prime the first token. *)
1831 print_string "ready> "; flush stdout;
1832 let stream = Lexer.lex (Stream.of_channel stdin) in
1834 (* Create the JIT. *)
1835 let the_execution_engine = ExecutionEngine.create Codegen.the_module in
1836 let the_fpm = PassManager.create_function Codegen.the_module in
1838 (* Set up the optimizer pipeline. Start with registering info about how the
1839 * target lays out data structures. *)
1840 TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
1842 (* Promote allocas to registers. *)
1843 add_memory_to_register_promotion the_fpm;
1845 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
1846 add_instruction_combination the_fpm;
1848 (* reassociate expressions. *)
1849 add_reassociation the_fpm;
1851 (* Eliminate Common SubExpressions. *)
1852 add_gvn the_fpm;
1854 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
1855 add_cfg_simplification the_fpm;
1857 ignore (PassManager.initialize the_fpm);
1859 (* Run the main "interpreter loop" now. *)
1860 Toplevel.main_loop the_fpm the_execution_engine stream;
1862 (* Print out all the generated code. *)
1863 dump_module Codegen.the_module
1864 ;;
1866 main ()
1867 </pre>
1868 </dd>
1872 <pre>
1875 /* putchard - putchar that takes a double and returns 0. */
1876 extern double putchard(double X) {
1877 putchar((char)X);
1878 return 0;
1879 }
1882 extern double printd(double X) {
1883 printf("%f\n", X);
1884 return 0;
1885 }
1886 </pre>
1887 </dd>
1888 </dl>
1891 </div>
1893 <!-- *********************************************************************** -->
1894 <hr>
1895 <address>
1904 Last modified: $Date$
1905 </address>
1906 </body>
1907 </html>