| blob | 51986b51a11660d2e4414147ae6e8816b1bb1349 |
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 <!-- *********************************************************************** -->
48 <div>
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 <!-- *********************************************************************** -->
76 <div>
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 <!-- *********************************************************************** -->
150 <div>
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 <!-- *********************************************************************** -->
331 <div>
333 <p>Now that we know the sort of problem we want to tackle, lets see what this
334 looks like in the context of our little Kaleidoscope language. We're going to
335 add two features:</p>
337 <ol>
340 </ol>
342 <p>While the first item is really what this is about, we only have variables
343 for incoming arguments as well as for induction variables, and redefining those only
344 goes so far :). Also, the ability to define new variables is a
345 useful thing regardless of whether you will be mutating them. Here's a
346 motivating example that shows how we could use these:</p>
349 <pre>
350 # Define ':' for sequencing: as a low-precedence operator that ignores operands
351 # and just returns the RHS.
352 def binary : 1 (x y) y;
354 # Recursive fib, we could do this before.
355 def fib(x)
357 1
358 else
361 # Iterative fib.
362 def fibi(x)
368 b;
370 # Call it.
371 fibi(10);
372 </pre>
373 </div>
375 <p>
376 In order to mutate variables, we have to change our existing variables to use
377 the "alloca trick". Once we have that, we'll add our new operator, then extend
378 Kaleidoscope to support new variable definitions.
379 </p>
381 </div>
383 <!-- *********************************************************************** -->
385 <!-- *********************************************************************** -->
387 <div>
389 <p>
390 The symbol table in Kaleidoscope is managed at code generation time by the
392 "Value*" that holds the double value for the named variable. In order to
393 support mutation, we need to change this slightly, so that it
395 question. Note that this change is a refactoring: it changes the structure of
396 the code, but does not (by itself) change the behavior of the compiler. All of
397 these changes are isolated in the Kaleidoscope code generator.</p>
399 <p>
400 At this point in Kaleidoscope's development, it only supports variables for two
401 things: incoming arguments to functions and the induction variable of 'for'
402 loops. For consistency, we'll allow mutation of these variables in addition to
403 other user-defined variables. This means that these will both need memory
404 locations.
405 </p>
407 <p>To start our transformation of Kaleidoscope, we'll change the
409 Once we do this, the C++ compiler will tell us what parts of the code we need to
410 update:</p>
414 future to be more type safe.</p>
417 <pre>
418 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
419 </pre>
420 </div>
422 <p>Also, since we will need to create these alloca's, we'll use a helper
423 function that ensures that the allocas are created in the entry block of the
424 function:</p>
427 <pre>
428 (* Create an alloca instruction in the entry block of the function. This
429 * is used for mutable variables etc. *)
430 let create_entry_block_alloca the_function var_name =
431 let builder = builder_at (instr_begin (entry_block the_function)) in
432 build_alloca double_type var_name builder
433 </pre>
434 </div>
437 pointing at the first instruction of the entry block. It then creates an alloca
438 with the expected name and returns it. Because all values in Kaleidoscope are
439 doubles, there is no need to pass in a type to use.</p>
441 <p>With this in place, the first functionality change we want to make is to
442 variable references. In our new scheme, variables live on the stack, so code
443 generating a reference to them actually needs to produce a load from the stack
444 slot:</p>
447 <pre>
448 let rec codegen_expr = function
449 ...
450 | Ast.Variable name ->
451 let v = try Hashtbl.find named_values name with
453 in
454 <b>(* Load the value. *)
455 build_load v name builder</b>
456 </pre>
457 </div>
459 <p>As you can see, this is pretty straightforward. Now we need to update the
460 things that define the variables to set up the alloca. We'll start with
462 for the unabridged code):</p>
465 <pre>
466 | Ast.For (var_name, start, end_, step, body) ->
467 let the_function = block_parent (insertion_block builder) in
469 (* Create an alloca for the variable in the entry block. *)
472 (* Emit the start code first, without 'variable' in scope. *)
473 let start_val = codegen_expr start in
475 <b>(* Store the value into the alloca. *)
476 ignore(build_store start_val alloca builder);</b>
478 ...
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
488 ...
490 (* Compute the end condition. *)
491 let end_cond = codegen_expr end_ in
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>
504 The big difference is that we no longer have to construct a PHI node, and we use
505 load/store to access the variable as needed.</p>
507 <p>To support mutable argument variables, we need to also make allocas for them.
508 The code for this is also pretty simple:</p>
511 <pre>
512 (* Create an alloca for each argument and register the argument in the symbol
513 * table so that references to it will succeed. *)
514 let create_argument_allocas the_function proto =
515 let args = match proto with
516 | Ast.Prototype (_, args) | Ast.BinOpPrototype (_, args, _) -> 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
523 (* Store the initial value into the alloca. *)
524 ignore(build_store ai alloca builder);
526 (* Add arguments to variable symbol table. *)
527 Hashtbl.add named_values var_name alloca;
528 ) (params the_function)
529 </pre>
530 </div>
532 <p>For each argument, we make an alloca, store the input value to the function
533 into the alloca, and register the alloca as the memory location for the
535 it sets up the entry block for the function.</p>
537 <p>The final missing piece is adding the mem2reg pass, which allows us to get
538 good codegen once again:</p>
541 <pre>
542 let main () =
543 ...
544 let the_fpm = PassManager.create_function Codegen.the_module in
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;
550 <b>(* Promote allocas to registers. *)
551 add_memory_to_register_promotion the_fpm;</b>
553 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
554 add_instruction_combining the_fpm;
556 (* reassociate expressions. *)
557 add_reassociation the_fpm;
558 </pre>
559 </div>
561 <p>It is interesting to see what the code looks like before and after the
562 mem2reg optimization runs. For example, this is the before/after code for our
563 recursive fib function. Before the optimization:</p>
566 <pre>
567 define double @fib(double %x) {
568 entry:
569 <b>%x1 = alloca double
570 store double %x, double* %x1
571 %x2 = load double* %x1</b>
572 %cmptmp = fcmp ult double %x2, 3.000000e+00
573 %booltmp = uitofp i1 %cmptmp to double
574 %ifcond = fcmp one double %booltmp, 0.000000e+00
575 br i1 %ifcond, label %then, label %else
577 then: ; preds = %entry
578 br label %ifcont
580 else: ; preds = %entry
582 %subtmp = fsub double %x3, 1.000000e+00
583 %calltmp = call double @fib(double %subtmp)
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
590 ifcont: ; preds = %else, %then
591 %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
592 ret double %iftmp
593 }
594 </pre>
595 </div>
597 <p>Here there is only one variable (x, the input argument) but you can still
598 see the extremely simple-minded code generation strategy we are using. In the
599 entry block, an alloca is created, and the initial input value is stored into
600 it. Each reference to the variable does a reload from the stack. Also, note
601 that we didn't modify the if/then/else expression, so it still inserts a PHI
602 node. While we could make an alloca for it, it is actually easier to create a
603 PHI node for it, so we still just make the PHI.</p>
608 <pre>
609 define double @fib(double %x) {
610 entry:
612 %booltmp = uitofp i1 %cmptmp to double
613 %ifcond = fcmp one double %booltmp, 0.000000e+00
614 br i1 %ifcond, label %then, label %else
616 then:
617 br label %ifcont
619 else:
621 %calltmp = call double @fib(double %subtmp)
623 %calltmp6 = call double @fib(double %subtmp5)
624 %addtmp = fadd double %calltmp, %calltmp6
625 br label %ifcont
627 ifcont: ; preds = %else, %then
628 %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
629 ret double %iftmp
630 }
631 </pre>
632 </div>
634 <p>This is a trivial case for mem2reg, since there are no redefinitions of the
635 variable. The point of showing this is to calm your tension about inserting
636 such blatent inefficiencies :).</p>
641 <pre>
642 define double @fib(double %x) {
643 entry:
644 %cmptmp = fcmp ult double %x, 3.000000e+00
645 %booltmp = uitofp i1 %cmptmp to double
646 %ifcond = fcmp ueq double %booltmp, 0.000000e+00
647 br i1 %ifcond, label %else, label %ifcont
649 else:
650 %subtmp = fsub double %x, 1.000000e+00
651 %calltmp = call double @fib(double %subtmp)
652 %subtmp5 = fsub double %x, 2.000000e+00
653 %calltmp6 = call double @fib(double %subtmp5)
654 %addtmp = fadd double %calltmp, %calltmp6
655 ret double %addtmp
657 ifcont:
658 ret double 1.000000e+00
659 }
660 </pre>
661 </div>
663 <p>Here we see that the simplifycfg pass decided to clone the return instruction
664 into the end of the 'else' block. This allowed it to eliminate some branches
665 and the PHI node.</p>
667 <p>Now that all symbol table references are updated to use stack variables,
668 we'll add the assignment operator.</p>
670 </div>
672 <!-- *********************************************************************** -->
674 <!-- *********************************************************************** -->
676 <div>
678 <p>With our current framework, adding a new assignment operator is really
679 simple. We will parse it just like any other binary operator, but handle it
680 internally (instead of allowing the user to define it). The first step is to
681 set a precedence:</p>
684 <pre>
685 let main () =
686 (* Install standard binary operators.
687 * 1 is the lowest precedence. *)
690 Hashtbl.add Parser.binop_precedence '+' 20;
691 Hashtbl.add Parser.binop_precedence '-' 20;
692 ...
693 </pre>
694 </div>
696 <p>Now that the parser knows the precedence of the binary operator, it takes
697 care of all the parsing and AST generation. We just need to implement codegen
698 for the assignment operator. This looks like:</p>
701 <pre>
702 let 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
711 in
712 </pre>
713 </div>
715 <p>Unlike the rest of the binary operators, our assignment operator doesn't
716 follow the "emit LHS, emit RHS, do computation" model. As such, it is handled
717 as a special case before the other binary operators are handled. The other
718 strange thing is that it requires the LHS to be a variable. It is invalid to
720 </p>
724 <pre>
725 (* Codegen the rhs. *)
726 let val_ = codegen_expr rhs in
728 (* Lookup the name. *)
729 let variable = try Hashtbl.find named_values name with
731 in
732 ignore(build_store val_ variable builder);
733 val_
734 | _ ->
735 ...
736 </pre>
737 </div>
739 <p>Once we have the variable, codegen'ing the assignment is straightforward:
740 we emit the RHS of the assignment, create a store, and return the computed
743 <p>Now that we have an assignment operator, we can mutate loop variables and
744 arguments. For example, we can now run code like this:</p>
747 <pre>
748 # Function to print a double.
749 extern printd(x);
751 # Define ':' for sequencing: as a low-precedence operator that ignores operands
752 # and just returns the RHS.
753 def binary : 1 (x y) y;
755 def test(x)
756 printd(x) :
757 x = 4 :
758 printd(x);
760 test(123);
761 </pre>
762 </div>
765 actually mutate the value! Okay, we have now officially implemented our goal:
766 getting this to work requires SSA construction in the general case. However,
767 to be really useful, we want the ability to define our own local variables, lets
768 add this next!
769 </p>
771 </div>
773 <!-- *********************************************************************** -->
775 <!-- *********************************************************************** -->
777 <div>
779 <p>Adding var/in is just like any other other extensions we made to
780 Kaleidoscope: we extend the lexer, the parser, the AST and the code generator.
781 The first step for adding our new 'var/in' construct is to extend the lexer.
782 As before, this is pretty trivial, the code looks like this:</p>
785 <pre>
786 type token =
787 ...
788 <b>(* var definition *)
789 | Var</b>
791 ...
793 and lex_ident buffer = parser
794 ...
799 ...
800 </pre>
801 </div>
803 <p>The next step is to define the AST node that we will construct. For var/in,
804 it looks like this:</p>
807 <pre>
808 type expr =
809 ...
810 (* variant for var/in. *)
811 | Var of (string * expr option) array * expr
812 ...
813 </pre>
814 </div>
816 <p>var/in allows a list of names to be defined all at once, and each name can
817 optionally have an initializer value. As such, we capture this information in
818 the VarNames vector. Also, var/in has a body, this body is allowed to access
819 the variables defined by the var/in.</p>
821 <p>With this in place, we can define the parser pieces. The first thing we do
822 is add it as a primary expression:</p>
825 <pre>
826 (* primary
827 * ::= identifier
828 * ::= numberexpr
829 * ::= parenexpr
830 * ::= ifexpr
831 * ::= forexpr
833 let 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'";
846 Ast.Var (Array.of_list (List.rev var_names), body)</b>
848 ...
850 and parse_var_init = parser
851 (* read in the optional initializer. *)
855 and parse_var_names accumulator = parser
856 | [< 'Token.Kwd ',';
857 'Token.Ident id ?? "expected identifier list after var";
858 init=parse_var_init;
861 </pre>
862 </div>
864 <p>Now that we can parse and represent the code, we need to support emission of
865 LLVM IR for it. This code starts out with:</p>
868 <pre>
869 let rec codegen_expr = function
870 ...
871 | Ast.Var (var_names, body)
872 let old_bindings = ref [] in
874 let the_function = block_parent (insertion_block builder) in
876 (* Register all variables and emit their initializer. *)
877 Array.iter (fun (var_name, init) ->
878 </pre>
879 </div>
881 <p>Basically it loops over all the variables, installing them one at a time.
882 For each variable we put into the symbol table, we remember the previous value
883 that we replace in OldBindings.</p>
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. *)
897 in
899 let alloca = create_entry_block_alloca the_function var_name in
900 ignore(build_store init_val alloca builder);
902 (* Remember the old variable binding so that we can restore the binding
903 * when we unrecurse. *)
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;
912 (* Remember this binding. *)
913 Hashtbl.add named_values var_name alloca;
914 ) var_names;
915 </pre>
916 </div>
918 <p>There are more comments here than code. The basic idea is that we emit the
919 initializer, create the alloca, then update the symbol table to point to it.
920 Once all the variables are installed in the symbol table, we evaluate the body
921 of the var/in expression:</p>
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>
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;
939 (* Return the body computation. *)
940 body_val
941 </pre>
942 </div>
944 <p>The end result of all of this is that we get properly scoped variable
945 definitions, and we even (trivially) allow mutation of them :).</p>
947 <p>With this, we completed what we set out to do. Our nice iterative fib
948 example from the intro compiles and runs just fine. The mem2reg pass optimizes
949 all of our stack variables into SSA registers, inserting PHI nodes where needed,
950 and our front-end remains simple: no "iterated dominance frontier" computation
951 anywhere in sight.</p>
953 </div>
955 <!-- *********************************************************************** -->
957 <!-- *********************************************************************** -->
959 <div>
961 <p>
962 Here is the complete code listing for our running example, enhanced with mutable
963 variables and var/in support. To build this example, use:
964 </p>
967 <pre>
968 # Compile
969 ocamlbuild toy.byte
970 # Run
971 ./toy.byte
972 </pre>
973 </div>
977 <dl>
980 <pre>
985 </pre>
986 </dd>
990 <pre>
991 open Ocamlbuild_plugin;;
993 ocaml_lib ~extern:true "llvm";;
994 ocaml_lib ~extern:true "llvm_analysis";;
995 ocaml_lib ~extern:true "llvm_executionengine";;
996 ocaml_lib ~extern:true "llvm_target";;
997 ocaml_lib ~extern:true "llvm_scalar_opts";;
1001 </pre>
1002 </dd>
1006 <pre>
1007 (*===----------------------------------------------------------------------===
1008 * Lexer Tokens
1009 *===----------------------------------------------------------------------===*)
1011 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
1012 * these others for known things. *)
1013 type token =
1014 (* commands *)
1015 | Def | Extern
1017 (* primary *)
1018 | Ident of string | Number of float
1020 (* unknown *)
1021 | Kwd of char
1023 (* control *)
1024 | If | Then | Else
1025 | For | In
1027 (* operators *)
1028 | Binary | Unary
1030 (* var definition *)
1031 | Var
1032 </pre>
1033 </dd>
1037 <pre>
1038 (*===----------------------------------------------------------------------===
1039 * Lexer
1040 *===----------------------------------------------------------------------===*)
1042 let rec lex = parser
1043 (* Skip any whitespace. *)
1046 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
1048 let buffer = Buffer.create 1 in
1049 Buffer.add_char buffer c;
1050 lex_ident buffer stream
1054 let buffer = Buffer.create 1 in
1055 Buffer.add_char buffer c;
1056 lex_number buffer stream
1058 (* Comment until end of line. *)
1060 lex_comment stream
1062 (* Otherwise, just return the character as its ascii value. *)
1066 (* end of stream. *)
1069 and lex_number buffer = parser
1071 Buffer.add_char buffer c;
1072 lex_number buffer stream
1076 and lex_ident buffer = parser
1078 Buffer.add_char buffer c;
1079 lex_ident buffer stream
1081 match Buffer.contents buffer with
1094 and lex_comment = parser
1098 </pre>
1099 </dd>
1103 <pre>
1104 (*===----------------------------------------------------------------------===
1105 * Abstract Syntax Tree (aka Parse Tree)
1106 *===----------------------------------------------------------------------===*)
1108 (* expr - Base type for all expression nodes. *)
1109 type expr =
1110 (* variant for numeric literals like "1.0". *)
1111 | Number of float
1113 (* variant for referencing a variable, like "a". *)
1114 | Variable of string
1116 (* variant for a unary operator. *)
1117 | Unary of char * expr
1119 (* variant for a binary operator. *)
1120 | Binary of char * expr * expr
1122 (* variant for function calls. *)
1123 | Call of string * expr array
1125 (* variant for if/then/else. *)
1126 | If of expr * expr * expr
1128 (* variant for for/in. *)
1129 | For of string * expr * expr * expr option * expr
1131 (* variant for var/in. *)
1132 | Var of (string * expr option) array * expr
1134 (* proto - This type represents the "prototype" for a function, which captures
1135 * its name, and its argument names (thus implicitly the number of arguments the
1136 * function takes). *)
1137 type proto =
1138 | Prototype of string * string array
1139 | BinOpPrototype of string * string array * int
1141 (* func - This type represents a function definition itself. *)
1142 type func = Function of proto * expr
1143 </pre>
1144 </dd>
1148 <pre>
1149 (*===---------------------------------------------------------------------===
1150 * Parser
1151 *===---------------------------------------------------------------------===*)
1153 (* binop_precedence - This holds the precedence for each binary operator that is
1154 * defined *)
1155 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
1157 (* precedence - Get the precedence of the pending binary operator token. *)
1160 (* primary
1161 * ::= identifier
1162 * ::= numberexpr
1163 * ::= parenexpr
1164 * ::= ifexpr
1165 * ::= forexpr
1166 * ::= varexpr *)
1167 let rec parse_primary = parser
1168 (* numberexpr ::= number *)
1171 (* parenexpr ::= '(' expression ')' *)
1174 (* identifierexpr
1175 * ::= identifier
1176 * ::= identifier '(' argumentexpr ')' *)
1178 let rec parse_args accumulator = parser
1180 begin parser
1183 end stream
1185 in
1186 let rec parse_ident id = parser
1187 (* Call. *)
1188 | [< 'Token.Kwd '(';
1189 args=parse_args [];
1191 Ast.Call (id, Array.of_list (List.rev args))
1193 (* Simple variable ref. *)
1195 in
1196 parse_ident id stream
1198 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
1199 | [< 'Token.If; c=parse_expr;
1200 'Token.Then ?? "expected 'then'"; t=parse_expr;
1202 Ast.If (c, t, e)
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";
1210 begin parser
1211 | [<
1212 start=parse_expr;
1213 'Token.Kwd ',' ?? "expected ',' after for";
1214 end_=parse_expr;
1216 let step =
1217 begin parser
1220 end stream
1221 in
1222 begin parser
1224 Ast.For (id, start, end_, step, body)
1226 raise (Stream.Error "expected 'in' after for")
1227 end stream
1229 raise (Stream.Error "expected '=' after for")
1230 end stream
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'";
1243 Ast.Var (Array.of_list (List.rev var_names), body)
1247 (* unary
1248 * ::= primary
1249 * ::= '!' unary *)
1250 and parse_unary = parser
1251 (* If this is a unary operator, read it. *)
1253 Ast.Unary (op, operand)
1255 (* If the current token is not an operator, it must be a primary expr. *)
1258 (* binoprhs
1259 * ::= ('+' primary)* *)
1260 and parse_bin_rhs expr_prec lhs stream =
1261 match Stream.peek stream with
1262 (* If this is a binop, find its precedence. *)
1263 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
1264 let token_prec = precedence c in
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;
1272 (* Parse the primary expression after the binary operator. *)
1273 let rhs = parse_unary stream in
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
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
1294 and parse_var_init = parser
1295 (* read in the optional initializer. *)
1299 and parse_var_names accumulator = parser
1300 | [< 'Token.Kwd ',';
1301 'Token.Ident id ?? "expected identifier list after var";
1302 init=parse_var_init;
1306 (* expression
1307 * ::= primary binoprhs *)
1308 and parse_expr = parser
1311 (* prototype
1312 * ::= id '(' id* ')'
1313 * ::= binary LETTER number? (id, id)
1314 * ::= unary LETTER number? (id) *)
1315 let parse_prototype =
1316 let rec parse_args accumulator = parser
1319 in
1320 let parse_operator = parser
1323 in
1324 let parse_binary_precedence = parser
1327 in
1328 parser
1329 | [< 'Token.Ident id;
1330 'Token.Kwd '(' ?? "expected '(' in prototype";
1331 args=parse_args [];
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 [];
1342 let name = prefix ^ (String.make 1 op) in
1343 let args = Array.of_list (List.rev args) in
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)
1354 raise (Stream.Error "expected function name in prototype")
1356 (* definition ::= 'def' prototype expression *)
1357 let parse_definition = parser
1359 Ast.Function (p, e)
1361 (* toplevelexpr ::= expression *)
1362 let parse_toplevel = parser
1364 (* Make an anonymous proto. *)
1365 Ast.Function (Ast.Prototype ("", [||]), e)
1367 (* external ::= 'extern' prototype *)
1368 let parse_extern = parser
1370 </pre>
1371 </dd>
1375 <pre>
1376 (*===----------------------------------------------------------------------===
1377 * Code Generation
1378 *===----------------------------------------------------------------------===*)
1380 open Llvm
1382 exception Error of string
1384 let context = global_context ()
1385 let the_module = create_module context "my cool jit"
1386 let builder = builder context
1387 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
1388 let double_type = double_type context
1390 (* Create an alloca instruction in the entry block of the function. This
1391 * is used for mutable variables etc. *)
1392 let create_entry_block_alloca the_function var_name =
1393 let builder = builder_at context (instr_begin (entry_block the_function)) in
1394 build_alloca double_type var_name builder
1396 let 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
1401 in
1402 (* Load the value. *)
1403 build_load v name builder
1404 | Ast.Unary (op, operand) ->
1405 let operand = codegen_expr operand in
1407 let callee =
1408 match lookup_function callee the_module with
1409 | Some callee -> callee
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
1422 in
1424 (* Codegen the rhs. *)
1425 let val_ = codegen_expr rhs in
1427 (* Lookup the name. *)
1428 let variable = try Hashtbl.find named_values name with
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
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. *)
1449 let callee =
1450 match lookup_function callee the_module with
1451 | Some callee -> callee
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
1463 in
1464 let params = params callee in
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
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
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
1483 let then_bb = append_block context "then" the_function in
1485 (* Emit 'then' value. *)
1486 position_at_end then_bb builder;
1487 let then_val = codegen_expr then_ in
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
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
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
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
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);
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);
1518 (* Finally, set the builder to the end of the merge block. *)
1519 position_at_end merge_bb builder;
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: *)
1543 let the_function = block_parent (insertion_block builder) in
1545 (* Create an alloca for the variable in the entry block. *)
1546 let alloca = create_entry_block_alloca the_function var_name in
1548 (* Emit the start code first, without 'variable' in scope. *)
1549 let start_val = codegen_expr start in
1551 (* Store the value into the alloca. *)
1552 ignore(build_store start_val alloca builder);
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
1558 (* Insert an explicit fall through from the current block to the
1559 * loop_bb. *)
1560 ignore (build_br loop_bb builder);
1562 (* Start insertion in loop_bb. *)
1563 position_at_end loop_bb builder;
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;
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);
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. *)
1584 in
1586 (* Compute the end condition. *)
1587 let end_cond = codegen_expr end_ in
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);
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
1599 (* Create the "after loop" block and insert it. *)
1600 let after_bb = append_block context "afterloop" the_function in
1602 (* Insert the conditional branch into the end of loop_end_bb. *)
1603 ignore (build_cond_br end_cond loop_bb after_bb builder);
1605 (* Any new code will be inserted in after_bb. *)
1606 position_at_end after_bb builder;
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;
1614 (* for expr always returns 0.0. *)
1615 const_null double_type
1616 | Ast.Var (var_names, body) ->
1617 let old_bindings = ref [] in
1619 let the_function = block_parent (insertion_block builder) in
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. *)
1633 in
1635 let alloca = create_entry_block_alloca the_function var_name in
1636 ignore(build_store init_val alloca builder);
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;
1647 (* Remember this binding. *)
1648 Hashtbl.add named_values var_name alloca;
1649 ) var_names;
1651 (* Codegen the body, now that all vars are in scope. *)
1652 let body_val = codegen_expr body in
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;
1659 (* Return the body computation. *)
1660 body_val
1662 let 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
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");
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
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
1692 (* Create an alloca for each argument and register the argument in the symbol
1693 * table so that references to it will succeed. *)
1694 let create_argument_allocas the_function proto =
1695 let args = match proto with
1696 | Ast.Prototype (_, args) | Ast.BinOpPrototype (_, args, _) -> 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
1703 (* Store the initial value into the alloca. *)
1704 ignore(build_store ai alloca builder);
1706 (* Add arguments to variable symbol table. *)
1707 Hashtbl.add named_values var_name alloca;
1708 ) (params the_function)
1710 let codegen_func the_fpm = function
1711 | Ast.Function (proto, body) ->
1712 Hashtbl.clear named_values;
1713 let the_function = codegen_proto proto in
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;
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;
1727 try
1728 (* Add all arguments to the symbol table and create their allocas. *)
1729 create_argument_allocas the_function proto;
1731 let ret_val = codegen_expr body in
1733 (* Finish off the function. *)
1734 let _ = build_ret ret_val builder in
1736 (* Validate the generated code, checking for consistency. *)
1737 Llvm_analysis.assert_valid_function the_function;
1739 (* Optimize the function. *)
1740 let _ = PassManager.run_function the_function the_fpm in
1742 the_function
1743 with e ->
1744 delete_function the_function;
1745 raise e
1746 </pre>
1747 </dd>
1751 <pre>
1752 (*===----------------------------------------------------------------------===
1753 * Top-Level parsing and JIT Driver
1754 *===----------------------------------------------------------------------===*)
1756 open Llvm
1757 open Llvm_executionengine
1759 (* top ::= definition | external | expression | ';' *)
1760 let rec main_loop the_fpm the_execution_engine stream =
1761 match Stream.peek stream with
1762 | None -> ()
1764 (* ignore top-level semicolons. *)
1765 | Some (Token.Kwd ';') ->
1766 Stream.junk stream;
1767 main_loop the_fpm the_execution_engine stream
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;
1787 (* JIT the function, returning a function pointer. *)
1788 let result = ExecutionEngine.run_function the_function [||]
1789 the_execution_engine in
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>
1806 <pre>
1807 (*===----------------------------------------------------------------------===
1808 * Main driver code.
1809 *===----------------------------------------------------------------------===*)
1811 open Llvm
1812 open Llvm_executionengine
1813 open Llvm_target
1814 open Llvm_scalar_opts
1816 let main () =
1817 ignore (initialize_native_target ());
1819 (* Install standard binary operators.
1820 * 1 is the lowest precedence. *)
1821 Hashtbl.add Parser.binop_precedence '=' 2;
1823 Hashtbl.add Parser.binop_precedence '+' 20;
1824 Hashtbl.add Parser.binop_precedence '-' 20;
1825 Hashtbl.add Parser.binop_precedence '*' 40; (* highest. *)
1827 (* Prime the first token. *)
1828 print_string "ready> "; flush stdout;
1829 let stream = Lexer.lex (Stream.of_channel stdin) in
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
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;
1839 (* Promote allocas to registers. *)
1840 add_memory_to_register_promotion the_fpm;
1842 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
1843 add_instruction_combination the_fpm;
1845 (* reassociate expressions. *)
1846 add_reassociation the_fpm;
1848 (* Eliminate Common SubExpressions. *)
1849 add_gvn the_fpm;
1851 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
1852 add_cfg_simplification the_fpm;
1854 ignore (PassManager.initialize the_fpm);
1856 (* Run the main "interpreter loop" now. *)
1857 Toplevel.main_loop the_fpm the_execution_engine stream;
1859 (* Print out all the generated code. *)
1860 dump_module Codegen.the_module
1861 ;;
1863 main ()
1864 </pre>
1865 </dd>
1869 <pre>
1872 /* putchard - putchar that takes a double and returns 0. */
1873 extern double putchard(double X) {
1874 putchar((char)X);
1875 return 0;
1876 }
1879 extern double printd(double X) {
1880 printf("%f\n", X);
1881 return 0;
1882 }
1883 </pre>
1884 </dd>
1885 </dl>
1888 </div>
1890 <!-- *********************************************************************** -->
1891 <hr>
1892 <address>
1901 Last modified: $Date$
1902 </address>
1903 </body>
1904 </html>