| blob | 6c77e9fa45e6cd678620b0b2d7e326dee8bf1a07 |
4 <html>
5 <head>
11 </head>
13 <body>
17 <ul>
20 <ol>
23 <ol>
29 </ol>
30 </li>
32 <ol>
38 </ol>
39 </li>
41 </ol>
42 </li>
44 User-defined Operators</li>
45 </ul>
48 <p>
51 </p>
52 </div>
54 <!-- *********************************************************************** -->
56 <!-- *********************************************************************** -->
62 Kaleidoscope language and included support for generating LLVM IR, followed by
63 optimizations and a JIT compiler. Unfortunately, as presented, Kaleidoscope is
64 mostly useless: it has no control flow other than call and return. This means
65 that you can't have conditional branches in the code, significantly limiting its
66 power. In this episode of "build that compiler", we'll extend Kaleidoscope to
67 have an if/then/else expression plus a simple 'for' loop.</p>
69 </div>
71 <!-- *********************************************************************** -->
73 <!-- *********************************************************************** -->
77 <p>
78 Extending Kaleidoscope to support if/then/else is quite straightforward. It
79 basically requires adding lexer support for this "new" concept to the lexer,
80 parser, AST, and LLVM code emitter. This example is nice, because it shows how
81 easy it is to "grow" a language over time, incrementally extending it as new
82 ideas are discovered.</p>
85 want. The basic idea is that we want to be able to write this sort of thing:
86 </p>
89 <pre>
90 def fib(x)
92 1
93 else
95 </pre>
96 </div>
98 <p>In Kaleidoscope, every construct is an expression: there are no statements.
99 As such, the if/then/else expression needs to return a value like any other.
100 Since we're using a mostly functional form, we'll have it evaluate its
101 conditional, then return the 'then' or 'else' value based on how the condition
104 <p>The semantics of the if/then/else expression is that it evaluates the
105 condition to a boolean equality value: 0.0 is considered to be false and
106 everything else is considered to be true.
107 If the condition is true, the first subexpression is evaluated and returned, if
108 the condition is false, the second subexpression is evaluated and returned.
109 Since Kaleidoscope allows side-effects, this behavior is important to nail down.
110 </p>
113 pieces.</p>
115 </div>
117 <!-- ======================================================================= -->
119 If/Then/Else</a></div>
120 <!-- ======================================================================= -->
125 <p>The lexer extensions are straightforward. First we add new variants
126 for the relevant tokens:</p>
129 <pre>
130 (* control *)
131 | If | Then | Else | For | In
132 </pre>
133 </div>
135 <p>Once we have that, we recognize the new keywords in the lexer. This is pretty simple
136 stuff:</p>
139 <pre>
140 ...
141 match Buffer.contents buffer with
150 </pre>
151 </div>
153 </div>
155 <!-- ======================================================================= -->
157 If/Then/Else</a></div>
158 <!-- ======================================================================= -->
165 <pre>
166 type expr =
167 ...
168 (* variant for if/then/else. *)
169 | If of expr * expr * expr
170 </pre>
171 </div>
175 </div>
177 <!-- ======================================================================= -->
179 If/Then/Else</a></div>
180 <!-- ======================================================================= -->
184 <p>Now that we have the relevant tokens coming from the lexer and we have the
185 AST node to build, our parsing logic is relatively straightforward. First we
186 define a new parsing function:</p>
189 <pre>
190 let rec parse_primary = parser
191 ...
192 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
193 | [< 'Token.If; c=parse_expr;
194 'Token.Then ?? "expected 'then'"; t=parse_expr;
196 Ast.If (c, t, e)
197 </pre>
198 </div>
203 <pre>
204 let rec parse_primary = parser
205 ...
206 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
207 | [< 'Token.If; c=parse_expr;
208 'Token.Then ?? "expected 'then'"; t=parse_expr;
210 Ast.If (c, t, e)
211 </pre>
212 </div>
214 </div>
216 <!-- ======================================================================= -->
218 <!-- ======================================================================= -->
222 <p>Now that we have it parsing and building the AST, the final piece is adding
223 LLVM code generation support. This is the most interesting part of the
224 if/then/else example, because this is where it starts to introduce new concepts.
225 All of the code above has been thoroughly described in previous chapters.
226 </p>
228 <p>To motivate the code we want to produce, lets take a look at a simple
229 example. Consider:</p>
232 <pre>
233 extern foo();
234 extern bar();
235 def baz(x) if x then foo() else bar();
236 </pre>
237 </div>
239 <p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
240 looks like this:</p>
243 <pre>
244 declare double @foo()
246 declare double @bar()
248 define double @baz(double %x) {
249 entry:
250 %ifcond = fcmp one double %x, 0.000000e+00
251 br i1 %ifcond, label %then, label %else
253 then: ; preds = %entry
254 %calltmp = call double @foo()
255 br label %ifcont
257 else: ; preds = %entry
258 %calltmp1 = call double @bar()
259 br label %ifcont
261 ifcont: ; preds = %else, %then
262 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
263 ret double %iftmp
264 }
265 </pre>
266 </div>
268 <p>To visualize the control flow graph, you can use a nifty feature of the LLVM
272 see this graph:</p>
279 is a "<tt>Function</tt>") either by inserting actual calls into the code and
280 recompiling or by calling these in the debugger. LLVM has many nice features
281 for visualizing various graphs.</p>
283 <p>Getting back to the generated code, it is fairly simple: the entry block
284 evaluates the conditional expression ("x" in our case here) and compares the
286 instruction ('one' is "Ordered and Not Equal"). Based on the result of this
288 the expressions for the true/false cases.</p>
290 <p>Once the then/else blocks are finished executing, they both branch back to the
291 'ifcont' block to execute the code that happens after the if/then/else. In this
292 case the only thing left to do is to return to the caller of the function. The
293 question then becomes: how does the code know which expression to return?</p>
295 <p>The answer to this question involves an important SSA operation: the
299 article</a> is a good introduction and there are various other introductions to
300 it available on your favorite search engine. The short version is that
302 from. The Phi operation takes on the value corresponding to the input control
303 block. In this case, if control comes in from the "then" block, it gets the
308 simple and elegant front-end will have to start generating SSA form in order to
309 use LLVM!". Fortunately, this is not the case, and we strongly advise
311 unless there is an amazingly good reason to do so. In practice, there are two
312 sorts of values that float around in code written for your average imperative
313 programming language that might need Phi nodes:</p>
315 <ol>
317 <li>Values that are implicit in the structure of your AST, such as the Phi node
318 in this case.</li>
319 </ol>
323 in depth. For now, just believe me that you don't need SSA construction to
324 handle this case. For #2, you have the choice of using the techniques that we will
325 describe for #1, or you can insert Phi nodes directly, if convenient. In this
326 case, it is really really easy to generate the Phi node, so we choose to do it
327 directly.</p>
331 </div>
333 <!-- ======================================================================= -->
335 If/Then/Else</a></div>
336 <!-- ======================================================================= -->
344 <pre>
345 let rec codegen_expr = function
346 ...
347 | Ast.If (cond, then_, else_) ->
348 let cond = codegen_expr cond in
350 (* Convert condition to a bool by comparing equal to 0.0 *)
351 let zero = const_float double_type 0.0 in
352 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
353 </pre>
354 </div>
356 <p>This code is straightforward and similar to what we saw before. We emit the
357 expression for the condition, then compare that value to zero to get a truth
361 <pre>
362 (* Grab the first block so that we might later add the conditional branch
363 * to it at the end of the function. *)
364 let start_bb = insertion_block builder in
365 let the_function = block_parent start_bb in
367 let then_bb = append_block "then" the_function in
368 position_at_end then_bb builder;
369 </pre>
370 </div>
372 <p>
374 our basic blocks bottom up since we can't have dangling BasicBlocks. We start
375 off by saving a pointer to the first block (which might not be the entry
376 block), which we'll need to build a conditional branch later. We do this by
378 gets the current Function object that is being built. It gets this by the
380 into).</p>
382 <p>Once it has that, it creates one block. It is automatically appended into
383 the function's list of blocks.</p>
386 <pre>
387 (* Emit 'then' value. *)
388 position_at_end then_bb builder;
389 let then_val = codegen_expr then_ in
391 (* Codegen of 'then' can change the current block, update then_bb for the
392 * phi. We create a new name because one is used for the phi node, and the
393 * other is used for the conditional branch. *)
394 let new_then_bb = insertion_block builder in
395 </pre>
396 </div>
399 speaking, this call moves the insertion point to be at the end of the specified
400 block. However, since the "then" block is empty, it also starts out by
401 inserting at the beginning of the block. :)</p>
404 from the AST.</p>
406 <p>The final line here is quite subtle, but is very important. The basic issue
407 is that when we create the Phi node in the merge block, we need to set up the
408 block/value pairs that indicate how the Phi will work. Importantly, the Phi
409 node expects to have an entry for each predecessor of the block in the CFG. Why
410 then, are we getting the current block when we just set it to ThenBB 5 lines
411 above? The problem is that the "Then" expression may actually itself change the
412 block that the Builder is emitting into if, for example, it contains a nested
413 "if/then/else" expression. Because calling Codegen recursively could
414 arbitrarily change the notion of the current block, we are required to get an
415 up-to-date value for code that will set up the Phi node.</p>
418 <pre>
419 (* Emit 'else' value. *)
420 let else_bb = append_block "else" the_function in
421 position_at_end else_bb builder;
422 let else_val = codegen_expr else_ in
424 (* Codegen of 'else' can change the current block, update else_bb for the
425 * phi. *)
426 let new_else_bb = insertion_block builder in
427 </pre>
428 </div>
430 <p>Code generation for the 'else' block is basically identical to codegen for
431 the 'then' block.</p>
434 <pre>
435 (* Emit merge block. *)
436 let merge_bb = append_block "ifcont" the_function in
437 position_at_end merge_bb builder;
438 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
439 let phi = build_phi incoming "iftmp" builder in
440 </pre>
441 </div>
444 to the Function object. The second block changes the insertion point so that
445 newly created code will go into the "merge" block. Once that is done, we need
446 to create the PHI node and set up the block/value pairs for the PHI.</p>
449 <pre>
450 (* Return to the start block to add the conditional branch. *)
451 position_at_end start_bb builder;
452 ignore (build_cond_br cond_val then_bb else_bb builder);
453 </pre>
454 </div>
456 <p>Once the blocks are created, we can emit the conditional branch that chooses
457 between them. Note that creating new blocks does not implicitly affect the
458 IRBuilder, so it is still inserting into the block that the condition
462 <pre>
463 (* Set a unconditional branch at the end of the 'then' block and the
464 * 'else' block to the 'merge' block. *)
465 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
466 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
468 (* Finally, set the builder to the end of the merge block. *)
469 position_at_end merge_bb builder;
471 phi
472 </pre>
473 </div>
475 <p>To finish off the blocks, we create an unconditional branch
476 to the merge block. One interesting (and very important) aspect of the LLVM IR
479 instruction</a> such as return or branch. This means that all control flow,
481 violate this rule, the verifier will emit an error.
483 <p>Finally, the CodeGen function returns the phi node as the value computed by
484 the if/then/else expression. In our example above, this returned value will
485 feed into the code for the top-level function, which will create the return
486 instruction.</p>
488 <p>Overall, we now have the ability to execute conditional code in
489 Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
490 that can calculate a wide variety of numeric functions. Next up we'll add
491 another useful expression that is familiar from non-functional languages...</p>
493 </div>
495 <!-- *********************************************************************** -->
497 <!-- *********************************************************************** -->
501 <p>Now that we know how to add basic control flow constructs to the language,
502 we have the tools to add more powerful things. Lets add something more
503 aggressive, a 'for' expression:</p>
506 <pre>
507 extern putchard(char);
508 def printstar(n)
512 # print 100 '*' characters
513 printstar(100);
514 </pre>
515 </div>
518 a starting value, while the condition ("i < n" in this case) is true,
519 incrementing by an optional step value ("1.0" in this case). If the step value
520 is omitted, it defaults to 1.0. While the loop is true, it executes its
521 body expression. Because we don't have anything better to return, we'll just
522 define the loop as always returning 0.0. In the future when we have mutable
523 variables, it will get more useful.</p>
525 <p>As before, lets talk about the changes that we need to Kaleidoscope to
526 support this.</p>
528 </div>
530 <!-- ======================================================================= -->
532 the 'for' Loop</a></div>
533 <!-- ======================================================================= -->
540 <pre>
541 ... in Token.token ...
542 (* control *)
543 | If | Then | Else
546 ... in Lexer.lex_ident...
547 match Buffer.contents buffer with
556 </pre>
557 </div>
559 </div>
561 <!-- ======================================================================= -->
563 the 'for' Loop</a></div>
564 <!-- ======================================================================= -->
568 <p>The AST variant is just as simple. It basically boils down to capturing
569 the variable name and the constituent expressions in the node.</p>
572 <pre>
573 type expr =
574 ...
575 (* variant for for/in. *)
576 | For of string * expr * expr * expr option * expr
577 </pre>
578 </div>
580 </div>
582 <!-- ======================================================================= -->
584 the 'for' Loop</a></div>
585 <!-- ======================================================================= -->
589 <p>The parser code is also fairly standard. The only interesting thing here is
590 handling of the optional step value. The parser code handles it by checking to
591 see if the second comma is present. If not, it sets the step value to null in
592 the AST node:</p>
595 <pre>
596 let rec parse_primary = parser
597 ...
598 (* forexpr
599 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
600 | [< 'Token.For;
601 'Token.Ident id ?? "expected identifier after for";
602 'Token.Kwd '=' ?? "expected '=' after for";
604 begin parser
605 | [<
606 start=parse_expr;
607 'Token.Kwd ',' ?? "expected ',' after for";
608 end_=parse_expr;
610 let step =
611 begin parser
614 end stream
615 in
616 begin parser
618 Ast.For (id, start, end_, step, body)
620 raise (Stream.Error "expected 'in' after for")
621 end stream
623 raise (Stream.Error "expected '=' after for")
624 end stream
625 </pre>
626 </div>
628 </div>
630 <!-- ======================================================================= -->
632 the 'for' Loop</a></div>
633 <!-- ======================================================================= -->
637 <p>Now we get to the good part: the LLVM IR we want to generate for this thing.
638 With the simple example above, we get this LLVM IR (note that this dump is
639 generated with optimizations disabled for clarity):
640 </p>
643 <pre>
644 declare double @putchard(double)
646 define double @printstar(double %n) {
647 entry:
648 ; initial value = 1.0 (inlined into phi)
649 br label %loop
651 loop: ; preds = %loop, %entry
652 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
653 ; body
654 %calltmp = call double @putchard( double 4.200000e+01 )
655 ; increment
656 %nextvar = add double %i, 1.000000e+00
658 ; termination test
659 %cmptmp = fcmp ult double %i, %n
660 %booltmp = uitofp i1 %cmptmp to double
661 %loopcond = fcmp one double %booltmp, 0.000000e+00
662 br i1 %loopcond, label %loop, label %afterloop
664 afterloop: ; preds = %loop
665 ; loop always returns 0.0
666 ret double 0.000000e+00
667 }
668 </pre>
669 </div>
671 <p>This loop contains all the same constructs we saw before: a phi node, several
672 expressions, and some basic blocks. Lets see how this fits together.</p>
674 </div>
676 <!-- ======================================================================= -->
678 the 'for' Loop</a></div>
679 <!-- ======================================================================= -->
683 <p>The first part of Codegen is very simple: we just output the start expression
684 for the loop value:</p>
687 <pre>
688 let rec codegen_expr = function
689 ...
690 | Ast.For (var_name, start, end_, step, body) ->
691 (* Emit the start code first, without 'variable' in scope. *)
692 let start_val = codegen_expr start in
693 </pre>
694 </div>
696 <p>With this out of the way, the next step is to set up the LLVM basic block
697 for the start of the loop body. In the case above, the whole loop body is one
698 block, but remember that the body code itself could consist of multiple blocks
699 (e.g. if it contains an if/then/else or a for/in expression).</p>
702 <pre>
703 (* Make the new basic block for the loop header, inserting after current
704 * block. *)
705 let preheader_bb = insertion_block builder in
706 let the_function = block_parent preheader_bb in
707 let loop_bb = append_block "loop" the_function in
709 (* Insert an explicit fall through from the current block to the
710 * loop_bb. *)
711 ignore (build_br loop_bb builder);
712 </pre>
713 </div>
715 <p>This code is similar to what we saw for if/then/else. Because we will need
716 it to create the Phi node, we remember the block that falls through into the
717 loop. Once we have that, we create the actual block that starts the loop and
718 create an unconditional branch for the fall-through between the two blocks.</p>
721 <pre>
722 (* Start insertion in loop_bb. *)
723 position_at_end loop_bb builder;
725 (* Start the PHI node with an entry for start. *)
726 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
727 </pre>
728 </div>
731 for the loop body. To begin with, we move the insertion point and create the
732 PHI node for the loop induction variable. Since we already know the incoming
733 value for the starting value, we add it to the Phi node. Note that the Phi will
734 eventually get a second value for the backedge, but we can't set it up yet
735 (because it doesn't exist!).</p>
738 <pre>
739 (* Within the loop, the variable is defined equal to the PHI node. If it
740 * shadows an existing variable, we have to restore it, so save it
741 * now. *)
742 let old_val =
743 try Some (Hashtbl.find named_values var_name) with Not_found -> None
744 in
745 Hashtbl.add named_values var_name variable;
747 (* Emit the body of the loop. This, like any other expr, can change the
748 * current BB. Note that we ignore the value computed by the body, but
749 * don't allow an error *)
750 ignore (codegen_expr body);
751 </pre>
752 </div>
754 <p>Now the code starts to get more interesting. Our 'for' loop introduces a new
755 variable to the symbol table. This means that our symbol table can now contain
756 either function arguments or loop variables. To handle this, before we codegen
757 the body of the loop, we add the loop variable as the current value for its
758 name. Note that it is possible that there is a variable of the same name in the
759 outer scope. It would be easy to make this an error (emit an error and return
760 null if there is already an entry for VarName) but we choose to allow shadowing
761 of variables. In order to handle this correctly, we remember the Value that
763 no shadowed variable).</p>
765 <p>Once the loop variable is set into the symbol table, the code recursively
766 codegen's the body. This allows the body to use the loop variable: any
767 references to it will naturally find it in the symbol table.</p>
770 <pre>
771 (* Emit the step value. *)
772 let step_val =
773 match step with
774 | Some step -> codegen_expr step
775 (* If not specified, use 1.0. *)
777 in
779 let next_var = build_add variable step_val "nextvar" builder in
780 </pre>
781 </div>
783 <p>Now that the body is emitted, we compute the next value of the iteration
784 variable by adding the step value, or 1.0 if it isn't present.
786 of the loop.</p>
789 <pre>
790 (* Compute the end condition. *)
791 let end_cond = codegen_expr end_ in
793 (* Convert condition to a bool by comparing equal to 0.0. *)
794 let zero = const_float double_type 0.0 in
795 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
796 </pre>
797 </div>
799 <p>Finally, we evaluate the exit value of the loop, to determine whether the
800 loop should exit. This mirrors the condition evaluation for the if/then/else
801 statement.</p>
804 <pre>
805 (* Create the "after loop" block and insert it. *)
806 let loop_end_bb = insertion_block builder in
807 let after_bb = append_block "afterloop" the_function in
809 (* Insert the conditional branch into the end of loop_end_bb. *)
810 ignore (build_cond_br end_cond loop_bb after_bb builder);
812 (* Any new code will be inserted in after_bb. *)
813 position_at_end after_bb builder;
814 </pre>
815 </div>
817 <p>With the code for the body of the loop complete, we just need to finish up
818 the control flow for it. This code remembers the end block (for the phi node), then creates the block for the loop exit ("afterloop"). Based on the value of the
819 exit condition, it creates a conditional branch that chooses between executing
820 the loop again and exiting the loop. Any future code is emitted in the
824 <pre>
825 (* Add a new entry to the PHI node for the backedge. *)
826 add_incoming (next_var, loop_end_bb) variable;
828 (* Restore the unshadowed variable. *)
829 begin match old_val with
830 | Some old_val -> Hashtbl.add named_values var_name old_val
831 | None -> ()
832 end;
834 (* for expr always returns 0.0. *)
835 const_null double_type
836 </pre>
837 </div>
839 <p>The final code handles various cleanups: now that we have the
840 "<tt>next_var</tt>" value, we can add the incoming value to the loop PHI node.
841 After that, we remove the loop variable from the symbol table, so that it isn't
842 in scope after the for loop. Finally, code generation of the for loop always
846 the tutorial. In this chapter we added two control flow constructs, and used
847 them to motivate a couple of aspects of the LLVM IR that are important for
848 front-end implementors to know. In the next chapter of our saga, we will get
850 to our poor innocent language.</p>
852 </div>
854 <!-- *********************************************************************** -->
856 <!-- *********************************************************************** -->
860 <p>
861 Here is the complete code listing for our running example, enhanced with the
862 if/then/else and for expressions.. To build this example, use:
863 </p>
866 <pre>
867 # Compile
868 ocamlbuild toy.byte
869 # Run
870 ./toy.byte
871 </pre>
872 </div>
876 <dl>
879 <pre>
884 </pre>
885 </dd>
889 <pre>
890 open Ocamlbuild_plugin;;
892 ocaml_lib ~extern:true "llvm";;
893 ocaml_lib ~extern:true "llvm_analysis";;
894 ocaml_lib ~extern:true "llvm_executionengine";;
895 ocaml_lib ~extern:true "llvm_target";;
896 ocaml_lib ~extern:true "llvm_scalar_opts";;
900 </pre>
901 </dd>
905 <pre>
906 (*===----------------------------------------------------------------------===
907 * Lexer Tokens
908 *===----------------------------------------------------------------------===*)
910 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
911 * these others for known things. *)
912 type token =
913 (* commands *)
914 | Def | Extern
916 (* primary *)
917 | Ident of string | Number of float
919 (* unknown *)
920 | Kwd of char
922 (* control *)
923 | If | Then | Else
924 | For | In
925 </pre>
926 </dd>
930 <pre>
931 (*===----------------------------------------------------------------------===
932 * Lexer
933 *===----------------------------------------------------------------------===*)
935 let rec lex = parser
936 (* Skip any whitespace. *)
939 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
941 let buffer = Buffer.create 1 in
942 Buffer.add_char buffer c;
943 lex_ident buffer stream
947 let buffer = Buffer.create 1 in
948 Buffer.add_char buffer c;
949 lex_number buffer stream
951 (* Comment until end of line. *)
953 lex_comment stream
955 (* Otherwise, just return the character as its ascii value. *)
959 (* end of stream. *)
962 and lex_number buffer = parser
964 Buffer.add_char buffer c;
965 lex_number buffer stream
969 and lex_ident buffer = parser
971 Buffer.add_char buffer c;
972 lex_ident buffer stream
974 match Buffer.contents buffer with
984 and lex_comment = parser
988 </pre>
989 </dd>
993 <pre>
994 (*===----------------------------------------------------------------------===
995 * Abstract Syntax Tree (aka Parse Tree)
996 *===----------------------------------------------------------------------===*)
998 (* expr - Base type for all expression nodes. *)
999 type expr =
1000 (* variant for numeric literals like "1.0". *)
1001 | Number of float
1003 (* variant for referencing a variable, like "a". *)
1004 | Variable of string
1006 (* variant for a binary operator. *)
1007 | Binary of char * expr * expr
1009 (* variant for function calls. *)
1010 | Call of string * expr array
1012 (* variant for if/then/else. *)
1013 | If of expr * expr * expr
1015 (* variant for for/in. *)
1016 | For of string * expr * expr * expr option * expr
1018 (* proto - This type represents the "prototype" for a function, which captures
1019 * its name, and its argument names (thus implicitly the number of arguments the
1020 * function takes). *)
1021 type proto = Prototype of string * string array
1023 (* func - This type represents a function definition itself. *)
1024 type func = Function of proto * expr
1025 </pre>
1026 </dd>
1030 <pre>
1031 (*===---------------------------------------------------------------------===
1032 * Parser
1033 *===---------------------------------------------------------------------===*)
1035 (* binop_precedence - This holds the precedence for each binary operator that is
1036 * defined *)
1037 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
1039 (* precedence - Get the precedence of the pending binary operator token. *)
1042 (* primary
1043 * ::= identifier
1044 * ::= numberexpr
1045 * ::= parenexpr
1046 * ::= ifexpr
1047 * ::= forexpr *)
1048 let rec parse_primary = parser
1049 (* numberexpr ::= number *)
1052 (* parenexpr ::= '(' expression ')' *)
1055 (* identifierexpr
1056 * ::= identifier
1057 * ::= identifier '(' argumentexpr ')' *)
1059 let rec parse_args accumulator = parser
1061 begin parser
1064 end stream
1066 in
1067 let rec parse_ident id = parser
1068 (* Call. *)
1069 | [< 'Token.Kwd '(';
1070 args=parse_args [];
1072 Ast.Call (id, Array.of_list (List.rev args))
1074 (* Simple variable ref. *)
1076 in
1077 parse_ident id stream
1079 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
1080 | [< 'Token.If; c=parse_expr;
1081 'Token.Then ?? "expected 'then'"; t=parse_expr;
1083 Ast.If (c, t, e)
1085 (* forexpr
1086 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
1087 | [< 'Token.For;
1088 'Token.Ident id ?? "expected identifier after for";
1089 'Token.Kwd '=' ?? "expected '=' after for";
1091 begin parser
1092 | [<
1093 start=parse_expr;
1094 'Token.Kwd ',' ?? "expected ',' after for";
1095 end_=parse_expr;
1097 let step =
1098 begin parser
1101 end stream
1102 in
1103 begin parser
1105 Ast.For (id, start, end_, step, body)
1107 raise (Stream.Error "expected 'in' after for")
1108 end stream
1110 raise (Stream.Error "expected '=' after for")
1111 end stream
1115 (* binoprhs
1116 * ::= ('+' primary)* *)
1117 and parse_bin_rhs expr_prec lhs stream =
1118 match Stream.peek stream with
1119 (* If this is a binop, find its precedence. *)
1120 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
1121 let token_prec = precedence c in
1123 (* If this is a binop that binds at least as tightly as the current binop,
1124 * consume it, otherwise we are done. *)
1125 if token_prec < expr_prec then lhs else begin
1126 (* Eat the binop. *)
1127 Stream.junk stream;
1129 (* Parse the primary expression after the binary operator. *)
1130 let rhs = parse_primary stream in
1132 (* Okay, we know this is a binop. *)
1133 let rhs =
1134 match Stream.peek stream with
1135 | Some (Token.Kwd c2) ->
1136 (* If BinOp binds less tightly with rhs than the operator after
1137 * rhs, let the pending operator take rhs as its lhs. *)
1138 let next_prec = precedence c2 in
1139 if token_prec < next_prec
1140 then parse_bin_rhs (token_prec + 1) rhs stream
1141 else rhs
1142 | _ -> rhs
1143 in
1145 (* Merge lhs/rhs. *)
1146 let lhs = Ast.Binary (c, lhs, rhs) in
1147 parse_bin_rhs expr_prec lhs stream
1148 end
1149 | _ -> lhs
1151 (* expression
1152 * ::= primary binoprhs *)
1153 and parse_expr = parser
1156 (* prototype
1157 * ::= id '(' id* ')' *)
1158 let parse_prototype =
1159 let rec parse_args accumulator = parser
1162 in
1164 parser
1165 | [< 'Token.Ident id;
1166 'Token.Kwd '(' ?? "expected '(' in prototype";
1167 args=parse_args [];
1169 (* success. *)
1170 Ast.Prototype (id, Array.of_list (List.rev args))
1173 raise (Stream.Error "expected function name in prototype")
1175 (* definition ::= 'def' prototype expression *)
1176 let parse_definition = parser
1178 Ast.Function (p, e)
1180 (* toplevelexpr ::= expression *)
1181 let parse_toplevel = parser
1183 (* Make an anonymous proto. *)
1184 Ast.Function (Ast.Prototype ("", [||]), e)
1186 (* external ::= 'extern' prototype *)
1187 let parse_extern = parser
1189 </pre>
1190 </dd>
1194 <pre>
1195 (*===----------------------------------------------------------------------===
1196 * Code Generation
1197 *===----------------------------------------------------------------------===*)
1199 open Llvm
1201 exception Error of string
1203 let context = global_context ()
1204 let the_module = create_module context "my cool jit"
1205 let builder = builder context
1206 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
1208 let rec codegen_expr = function
1209 | Ast.Number n -> const_float double_type n
1210 | Ast.Variable name ->
1211 (try Hashtbl.find named_values name with
1213 | Ast.Binary (op, lhs, rhs) ->
1214 let lhs_val = codegen_expr lhs in
1215 let rhs_val = codegen_expr rhs in
1216 begin
1217 match op with
1223 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
1224 build_uitofp i double_type "booltmp" builder
1226 end
1227 | Ast.Call (callee, args) ->
1228 (* Look up the name in the module table. *)
1229 let callee =
1230 match lookup_function callee the_module with
1231 | Some callee -> callee
1233 in
1234 let params = params callee in
1236 (* If argument mismatch error. *)
1237 if Array.length params == Array.length args then () else
1238 raise (Error "incorrect # arguments passed");
1239 let args = Array.map codegen_expr args in
1240 build_call callee args "calltmp" builder
1241 | Ast.If (cond, then_, else_) ->
1242 let cond = codegen_expr cond in
1244 (* Convert condition to a bool by comparing equal to 0.0 *)
1245 let zero = const_float double_type 0.0 in
1246 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
1248 (* Grab the first block so that we might later add the conditional branch
1249 * to it at the end of the function. *)
1250 let start_bb = insertion_block builder in
1251 let the_function = block_parent start_bb in
1253 let then_bb = append_block "then" the_function in
1255 (* Emit 'then' value. *)
1256 position_at_end then_bb builder;
1257 let then_val = codegen_expr then_ in
1259 (* Codegen of 'then' can change the current block, update then_bb for the
1260 * phi. We create a new name because one is used for the phi node, and the
1261 * other is used for the conditional branch. *)
1262 let new_then_bb = insertion_block builder in
1264 (* Emit 'else' value. *)
1265 let else_bb = append_block "else" the_function in
1266 position_at_end else_bb builder;
1267 let else_val = codegen_expr else_ in
1269 (* Codegen of 'else' can change the current block, update else_bb for the
1270 * phi. *)
1271 let new_else_bb = insertion_block builder in
1273 (* Emit merge block. *)
1274 let merge_bb = append_block "ifcont" the_function in
1275 position_at_end merge_bb builder;
1276 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
1277 let phi = build_phi incoming "iftmp" builder in
1279 (* Return to the start block to add the conditional branch. *)
1280 position_at_end start_bb builder;
1281 ignore (build_cond_br cond_val then_bb else_bb builder);
1283 (* Set a unconditional branch at the end of the 'then' block and the
1284 * 'else' block to the 'merge' block. *)
1285 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
1286 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
1288 (* Finally, set the builder to the end of the merge block. *)
1289 position_at_end merge_bb builder;
1291 phi
1292 | Ast.For (var_name, start, end_, step, body) ->
1293 (* Emit the start code first, without 'variable' in scope. *)
1294 let start_val = codegen_expr start in
1296 (* Make the new basic block for the loop header, inserting after current
1297 * block. *)
1298 let preheader_bb = insertion_block builder in
1299 let the_function = block_parent preheader_bb in
1300 let loop_bb = append_block "loop" the_function in
1302 (* Insert an explicit fall through from the current block to the
1303 * loop_bb. *)
1304 ignore (build_br loop_bb builder);
1306 (* Start insertion in loop_bb. *)
1307 position_at_end loop_bb builder;
1309 (* Start the PHI node with an entry for start. *)
1310 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
1312 (* Within the loop, the variable is defined equal to the PHI node. If it
1313 * shadows an existing variable, we have to restore it, so save it
1314 * now. *)
1315 let old_val =
1316 try Some (Hashtbl.find named_values var_name) with Not_found -> None
1317 in
1318 Hashtbl.add named_values var_name variable;
1320 (* Emit the body of the loop. This, like any other expr, can change the
1321 * current BB. Note that we ignore the value computed by the body, but
1322 * don't allow an error *)
1323 ignore (codegen_expr body);
1325 (* Emit the step value. *)
1326 let step_val =
1327 match step with
1328 | Some step -> codegen_expr step
1329 (* If not specified, use 1.0. *)
1331 in
1333 let next_var = build_add variable step_val "nextvar" builder in
1335 (* Compute the end condition. *)
1336 let end_cond = codegen_expr end_ in
1338 (* Convert condition to a bool by comparing equal to 0.0. *)
1339 let zero = const_float double_type 0.0 in
1340 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
1342 (* Create the "after loop" block and insert it. *)
1343 let loop_end_bb = insertion_block builder in
1344 let after_bb = append_block "afterloop" the_function in
1346 (* Insert the conditional branch into the end of loop_end_bb. *)
1347 ignore (build_cond_br end_cond loop_bb after_bb builder);
1349 (* Any new code will be inserted in after_bb. *)
1350 position_at_end after_bb builder;
1352 (* Add a new entry to the PHI node for the backedge. *)
1353 add_incoming (next_var, loop_end_bb) variable;
1355 (* Restore the unshadowed variable. *)
1356 begin match old_val with
1357 | Some old_val -> Hashtbl.add named_values var_name old_val
1358 | None -> ()
1359 end;
1361 (* for expr always returns 0.0. *)
1362 const_null double_type
1364 let codegen_proto = function
1365 | Ast.Prototype (name, args) ->
1366 (* Make the function type: double(double,double) etc. *)
1367 let doubles = Array.make (Array.length args) double_type in
1368 let ft = function_type double_type doubles in
1369 let f =
1370 match lookup_function name the_module with
1371 | None -> declare_function name ft the_module
1373 (* If 'f' conflicted, there was already something named 'name'. If it
1374 * has a body, don't allow redefinition or reextern. *)
1375 | Some f ->
1376 (* If 'f' already has a body, reject this. *)
1377 if block_begin f <> At_end f then
1378 raise (Error "redefinition of function");
1380 (* If 'f' took a different number of arguments, reject. *)
1381 if element_type (type_of f) <> ft then
1382 raise (Error "redefinition of function with different # args");
1383 f
1384 in
1386 (* Set names for all arguments. *)
1387 Array.iteri (fun i a ->
1388 let n = args.(i) in
1389 set_value_name n a;
1390 Hashtbl.add named_values n a;
1391 ) (params f);
1392 f
1394 let codegen_func the_fpm = function
1395 | Ast.Function (proto, body) ->
1396 Hashtbl.clear named_values;
1397 let the_function = codegen_proto proto in
1399 (* Create a new basic block to start insertion into. *)
1400 let bb = append_block "entry" the_function in
1401 position_at_end bb builder;
1403 try
1404 let ret_val = codegen_expr body in
1406 (* Finish off the function. *)
1407 let _ = build_ret ret_val builder in
1409 (* Validate the generated code, checking for consistency. *)
1410 Llvm_analysis.assert_valid_function the_function;
1412 (* Optimize the function. *)
1413 let _ = PassManager.run_function the_function the_fpm in
1415 the_function
1416 with e ->
1417 delete_function the_function;
1418 raise e
1419 </pre>
1420 </dd>
1424 <pre>
1425 (*===----------------------------------------------------------------------===
1426 * Top-Level parsing and JIT Driver
1427 *===----------------------------------------------------------------------===*)
1429 open Llvm
1430 open Llvm_executionengine
1432 (* top ::= definition | external | expression | ';' *)
1433 let rec main_loop the_fpm the_execution_engine stream =
1434 match Stream.peek stream with
1435 | None -> ()
1437 (* ignore top-level semicolons. *)
1438 | Some (Token.Kwd ';') ->
1439 Stream.junk stream;
1440 main_loop the_fpm the_execution_engine stream
1442 | Some token ->
1443 begin
1444 try match token with
1445 | Token.Def ->
1446 let e = Parser.parse_definition stream in
1447 print_endline "parsed a function definition.";
1448 dump_value (Codegen.codegen_func the_fpm e);
1449 | Token.Extern ->
1450 let e = Parser.parse_extern stream in
1451 print_endline "parsed an extern.";
1452 dump_value (Codegen.codegen_proto e);
1453 | _ ->
1454 (* Evaluate a top-level expression into an anonymous function. *)
1455 let e = Parser.parse_toplevel stream in
1456 print_endline "parsed a top-level expr";
1457 let the_function = Codegen.codegen_func the_fpm e in
1458 dump_value the_function;
1460 (* JIT the function, returning a function pointer. *)
1461 let result = ExecutionEngine.run_function the_function [||]
1462 the_execution_engine in
1464 print_string "Evaluated to ";
1465 print_float (GenericValue.as_float double_type result);
1466 print_newline ();
1467 with Stream.Error s | Codegen.Error s ->
1468 (* Skip token for error recovery. *)
1469 Stream.junk stream;
1470 print_endline s;
1471 end;
1472 print_string "ready> "; flush stdout;
1473 main_loop the_fpm the_execution_engine stream
1474 </pre>
1475 </dd>
1479 <pre>
1480 (*===----------------------------------------------------------------------===
1481 * Main driver code.
1482 *===----------------------------------------------------------------------===*)
1484 open Llvm
1485 open Llvm_executionengine
1486 open Llvm_target
1487 open Llvm_scalar_opts
1489 let main () =
1490 (* Install standard binary operators.
1491 * 1 is the lowest precedence. *)
1493 Hashtbl.add Parser.binop_precedence '+' 20;
1494 Hashtbl.add Parser.binop_precedence '-' 20;
1495 Hashtbl.add Parser.binop_precedence '*' 40; (* highest. *)
1497 (* Prime the first token. *)
1498 print_string "ready> "; flush stdout;
1499 let stream = Lexer.lex (Stream.of_channel stdin) in
1501 (* Create the JIT. *)
1502 let the_module_provider = ModuleProvider.create Codegen.the_module in
1503 let the_execution_engine = ExecutionEngine.create the_module_provider in
1504 let the_fpm = PassManager.create_function the_module_provider in
1506 (* Set up the optimizer pipeline. Start with registering info about how the
1507 * target lays out data structures. *)
1508 TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
1510 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
1511 add_instruction_combining the_fpm;
1513 (* reassociate expressions. *)
1514 add_reassociation the_fpm;
1516 (* Eliminate Common SubExpressions. *)
1517 add_gvn the_fpm;
1519 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
1520 add_cfg_simplification the_fpm;
1522 (* Run the main "interpreter loop" now. *)
1523 Toplevel.main_loop the_fpm the_execution_engine stream;
1525 (* Print out all the generated code. *)
1526 dump_module Codegen.the_module
1527 ;;
1529 main ()
1530 </pre>
1531 </dd>
1535 <pre>
1538 /* putchard - putchar that takes a double and returns 0. */
1539 extern double putchard(double X) {
1540 putchar((char)X);
1541 return 0;
1542 }
1543 </pre>
1544 </dd>
1545 </dl>
1548 operators</a>
1549 </div>
1551 <!-- *********************************************************************** -->
1552 <hr>
1553 <address>
1563 </address>
1564 </body>
1565 </html>