| blob | d356f126a4c1a744da93e4b99277e0002ac92dd6 |
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 <!-- *********************************************************************** -->
58 <div>
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 <!-- *********************************************************************** -->
75 <div>
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 <!-- ======================================================================= -->
117 <!-- ======================================================================= -->
120 <div>
122 <p>The lexer extensions are straightforward. First we add new variants
123 for the relevant tokens:</p>
126 <pre>
127 (* control *)
128 | If | Then | Else | For | In
129 </pre>
130 </div>
132 <p>Once we have that, we recognize the new keywords in the lexer. This is pretty simple
133 stuff:</p>
136 <pre>
137 ...
138 match Buffer.contents buffer with
147 </pre>
148 </div>
150 </div>
152 <!-- ======================================================================= -->
154 <!-- ======================================================================= -->
156 <div>
161 <pre>
162 type expr =
163 ...
164 (* variant for if/then/else. *)
165 | If of expr * expr * expr
166 </pre>
167 </div>
171 </div>
173 <!-- ======================================================================= -->
175 <!-- ======================================================================= -->
177 <div>
179 <p>Now that we have the relevant tokens coming from the lexer and we have the
180 AST node to build, our parsing logic is relatively straightforward. First we
181 define a new parsing function:</p>
184 <pre>
185 let rec parse_primary = parser
186 ...
187 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
188 | [< 'Token.If; c=parse_expr;
189 'Token.Then ?? "expected 'then'"; t=parse_expr;
191 Ast.If (c, t, e)
192 </pre>
193 </div>
198 <pre>
199 let rec parse_primary = parser
200 ...
201 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
202 | [< 'Token.If; c=parse_expr;
203 'Token.Then ?? "expected 'then'"; t=parse_expr;
205 Ast.If (c, t, e)
206 </pre>
207 </div>
209 </div>
211 <!-- ======================================================================= -->
213 <!-- ======================================================================= -->
215 <div>
217 <p>Now that we have it parsing and building the AST, the final piece is adding
218 LLVM code generation support. This is the most interesting part of the
219 if/then/else example, because this is where it starts to introduce new concepts.
220 All of the code above has been thoroughly described in previous chapters.
221 </p>
223 <p>To motivate the code we want to produce, lets take a look at a simple
224 example. Consider:</p>
227 <pre>
228 extern foo();
229 extern bar();
230 def baz(x) if x then foo() else bar();
231 </pre>
232 </div>
234 <p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
235 looks like this:</p>
238 <pre>
239 declare double @foo()
241 declare double @bar()
243 define double @baz(double %x) {
244 entry:
245 %ifcond = fcmp one double %x, 0.000000e+00
246 br i1 %ifcond, label %then, label %else
248 then: ; preds = %entry
249 %calltmp = call double @foo()
250 br label %ifcont
252 else: ; preds = %entry
253 %calltmp1 = call double @bar()
254 br label %ifcont
256 ifcont: ; preds = %else, %then
257 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
258 ret double %iftmp
259 }
260 </pre>
261 </div>
263 <p>To visualize the control flow graph, you can use a nifty feature of the LLVM
267 see this graph:</p>
274 is a "<tt>Function</tt>") either by inserting actual calls into the code and
275 recompiling or by calling these in the debugger. LLVM has many nice features
276 for visualizing various graphs.</p>
278 <p>Getting back to the generated code, it is fairly simple: the entry block
279 evaluates the conditional expression ("x" in our case here) and compares the
281 instruction ('one' is "Ordered and Not Equal"). Based on the result of this
283 the expressions for the true/false cases.</p>
285 <p>Once the then/else blocks are finished executing, they both branch back to the
286 'ifcont' block to execute the code that happens after the if/then/else. In this
287 case the only thing left to do is to return to the caller of the function. The
288 question then becomes: how does the code know which expression to return?</p>
290 <p>The answer to this question involves an important SSA operation: the
294 article</a> is a good introduction and there are various other introductions to
295 it available on your favorite search engine. The short version is that
297 from. The Phi operation takes on the value corresponding to the input control
298 block. In this case, if control comes in from the "then" block, it gets the
303 simple and elegant front-end will have to start generating SSA form in order to
304 use LLVM!". Fortunately, this is not the case, and we strongly advise
306 unless there is an amazingly good reason to do so. In practice, there are two
307 sorts of values that float around in code written for your average imperative
308 programming language that might need Phi nodes:</p>
310 <ol>
312 <li>Values that are implicit in the structure of your AST, such as the Phi node
313 in this case.</li>
314 </ol>
318 in depth. For now, just believe me that you don't need SSA construction to
319 handle this case. For #2, you have the choice of using the techniques that we will
320 describe for #1, or you can insert Phi nodes directly, if convenient. In this
321 case, it is really really easy to generate the Phi node, so we choose to do it
322 directly.</p>
326 </div>
328 <!-- ======================================================================= -->
330 <!-- ======================================================================= -->
332 <div>
338 <pre>
339 let rec codegen_expr = function
340 ...
341 | Ast.If (cond, then_, else_) ->
342 let cond = codegen_expr cond in
344 (* Convert condition to a bool by comparing equal to 0.0 *)
345 let zero = const_float double_type 0.0 in
346 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
347 </pre>
348 </div>
350 <p>This code is straightforward and similar to what we saw before. We emit the
351 expression for the condition, then compare that value to zero to get a truth
355 <pre>
356 (* Grab the first block so that we might later add the conditional branch
357 * to it at the end of the function. *)
358 let start_bb = insertion_block builder in
359 let the_function = block_parent start_bb in
361 let then_bb = append_block context "then" the_function in
362 position_at_end then_bb builder;
363 </pre>
364 </div>
366 <p>
368 our basic blocks bottom up since we can't have dangling BasicBlocks. We start
369 off by saving a pointer to the first block (which might not be the entry
370 block), which we'll need to build a conditional branch later. We do this by
372 gets the current Function object that is being built. It gets this by the
374 into).</p>
376 <p>Once it has that, it creates one block. It is automatically appended into
377 the function's list of blocks.</p>
380 <pre>
381 (* Emit 'then' value. *)
382 position_at_end then_bb builder;
383 let then_val = codegen_expr then_ in
385 (* Codegen of 'then' can change the current block, update then_bb for the
386 * phi. We create a new name because one is used for the phi node, and the
387 * other is used for the conditional branch. *)
388 let new_then_bb = insertion_block builder in
389 </pre>
390 </div>
393 speaking, this call moves the insertion point to be at the end of the specified
394 block. However, since the "then" block is empty, it also starts out by
395 inserting at the beginning of the block. :)</p>
398 from the AST.</p>
400 <p>The final line here is quite subtle, but is very important. The basic issue
401 is that when we create the Phi node in the merge block, we need to set up the
402 block/value pairs that indicate how the Phi will work. Importantly, the Phi
403 node expects to have an entry for each predecessor of the block in the CFG. Why
404 then, are we getting the current block when we just set it to ThenBB 5 lines
405 above? The problem is that the "Then" expression may actually itself change the
406 block that the Builder is emitting into if, for example, it contains a nested
407 "if/then/else" expression. Because calling Codegen recursively could
408 arbitrarily change the notion of the current block, we are required to get an
409 up-to-date value for code that will set up the Phi node.</p>
412 <pre>
413 (* Emit 'else' value. *)
414 let else_bb = append_block context "else" the_function in
415 position_at_end else_bb builder;
416 let else_val = codegen_expr else_ in
418 (* Codegen of 'else' can change the current block, update else_bb for the
419 * phi. *)
420 let new_else_bb = insertion_block builder in
421 </pre>
422 </div>
424 <p>Code generation for the 'else' block is basically identical to codegen for
425 the 'then' block.</p>
428 <pre>
429 (* Emit merge block. *)
430 let merge_bb = append_block context "ifcont" the_function in
431 position_at_end merge_bb builder;
432 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
433 let phi = build_phi incoming "iftmp" builder in
434 </pre>
435 </div>
438 to the Function object. The second block changes the insertion point so that
439 newly created code will go into the "merge" block. Once that is done, we need
440 to create the PHI node and set up the block/value pairs for the PHI.</p>
443 <pre>
444 (* Return to the start block to add the conditional branch. *)
445 position_at_end start_bb builder;
446 ignore (build_cond_br cond_val then_bb else_bb builder);
447 </pre>
448 </div>
450 <p>Once the blocks are created, we can emit the conditional branch that chooses
451 between them. Note that creating new blocks does not implicitly affect the
452 IRBuilder, so it is still inserting into the block that the condition
456 <pre>
457 (* Set a unconditional branch at the end of the 'then' block and the
458 * 'else' block to the 'merge' block. *)
459 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
460 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
462 (* Finally, set the builder to the end of the merge block. *)
463 position_at_end merge_bb builder;
465 phi
466 </pre>
467 </div>
469 <p>To finish off the blocks, we create an unconditional branch
470 to the merge block. One interesting (and very important) aspect of the LLVM IR
473 instruction</a> such as return or branch. This means that all control flow,
475 violate this rule, the verifier will emit an error.
477 <p>Finally, the CodeGen function returns the phi node as the value computed by
478 the if/then/else expression. In our example above, this returned value will
479 feed into the code for the top-level function, which will create the return
480 instruction.</p>
482 <p>Overall, we now have the ability to execute conditional code in
483 Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
484 that can calculate a wide variety of numeric functions. Next up we'll add
485 another useful expression that is familiar from non-functional languages...</p>
487 </div>
489 </div>
491 <!-- *********************************************************************** -->
493 <!-- *********************************************************************** -->
495 <div>
497 <p>Now that we know how to add basic control flow constructs to the language,
498 we have the tools to add more powerful things. Lets add something more
499 aggressive, a 'for' expression:</p>
502 <pre>
503 extern putchard(char);
504 def printstar(n)
508 # print 100 '*' characters
509 printstar(100);
510 </pre>
511 </div>
514 a starting value, while the condition ("i < n" in this case) is true,
515 incrementing by an optional step value ("1.0" in this case). If the step value
516 is omitted, it defaults to 1.0. While the loop is true, it executes its
517 body expression. Because we don't have anything better to return, we'll just
518 define the loop as always returning 0.0. In the future when we have mutable
519 variables, it will get more useful.</p>
521 <p>As before, lets talk about the changes that we need to Kaleidoscope to
522 support this.</p>
524 <!-- ======================================================================= -->
526 <!-- ======================================================================= -->
528 <div>
533 <pre>
534 ... in Token.token ...
535 (* control *)
536 | If | Then | Else
539 ... in Lexer.lex_ident...
540 match Buffer.contents buffer with
549 </pre>
550 </div>
552 </div>
554 <!-- ======================================================================= -->
556 <!-- ======================================================================= -->
558 <div>
560 <p>The AST variant is just as simple. It basically boils down to capturing
561 the variable name and the constituent expressions in the node.</p>
564 <pre>
565 type expr =
566 ...
567 (* variant for for/in. *)
568 | For of string * expr * expr * expr option * expr
569 </pre>
570 </div>
572 </div>
574 <!-- ======================================================================= -->
576 <!-- ======================================================================= -->
578 <div>
580 <p>The parser code is also fairly standard. The only interesting thing here is
581 handling of the optional step value. The parser code handles it by checking to
582 see if the second comma is present. If not, it sets the step value to null in
583 the AST node:</p>
586 <pre>
587 let rec parse_primary = parser
588 ...
589 (* forexpr
590 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
591 | [< 'Token.For;
592 'Token.Ident id ?? "expected identifier after for";
593 'Token.Kwd '=' ?? "expected '=' after for";
595 begin parser
596 | [<
597 start=parse_expr;
598 'Token.Kwd ',' ?? "expected ',' after for";
599 end_=parse_expr;
601 let step =
602 begin parser
605 end stream
606 in
607 begin parser
609 Ast.For (id, start, end_, step, body)
611 raise (Stream.Error "expected 'in' after for")
612 end stream
614 raise (Stream.Error "expected '=' after for")
615 end stream
616 </pre>
617 </div>
619 </div>
621 <!-- ======================================================================= -->
623 <!-- ======================================================================= -->
625 <div>
627 <p>Now we get to the good part: the LLVM IR we want to generate for this thing.
628 With the simple example above, we get this LLVM IR (note that this dump is
629 generated with optimizations disabled for clarity):
630 </p>
633 <pre>
634 declare double @putchard(double)
636 define double @printstar(double %n) {
637 entry:
638 ; initial value = 1.0 (inlined into phi)
639 br label %loop
641 loop: ; preds = %loop, %entry
642 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
643 ; body
644 %calltmp = call double @putchard(double 4.200000e+01)
645 ; increment
646 %nextvar = fadd double %i, 1.000000e+00
648 ; termination test
649 %cmptmp = fcmp ult double %i, %n
650 %booltmp = uitofp i1 %cmptmp to double
651 %loopcond = fcmp one double %booltmp, 0.000000e+00
652 br i1 %loopcond, label %loop, label %afterloop
654 afterloop: ; preds = %loop
655 ; loop always returns 0.0
656 ret double 0.000000e+00
657 }
658 </pre>
659 </div>
661 <p>This loop contains all the same constructs we saw before: a phi node, several
662 expressions, and some basic blocks. Lets see how this fits together.</p>
664 </div>
666 <!-- ======================================================================= -->
668 <!-- ======================================================================= -->
670 <div>
672 <p>The first part of Codegen is very simple: we just output the start expression
673 for the loop value:</p>
676 <pre>
677 let rec codegen_expr = function
678 ...
679 | Ast.For (var_name, start, end_, step, body) ->
680 (* Emit the start code first, without 'variable' in scope. *)
681 let start_val = codegen_expr start in
682 </pre>
683 </div>
685 <p>With this out of the way, the next step is to set up the LLVM basic block
686 for the start of the loop body. In the case above, the whole loop body is one
687 block, but remember that the body code itself could consist of multiple blocks
688 (e.g. if it contains an if/then/else or a for/in expression).</p>
691 <pre>
692 (* Make the new basic block for the loop header, inserting after current
693 * block. *)
694 let preheader_bb = insertion_block builder in
695 let the_function = block_parent preheader_bb in
696 let loop_bb = append_block context "loop" the_function in
698 (* Insert an explicit fall through from the current block to the
699 * loop_bb. *)
700 ignore (build_br loop_bb builder);
701 </pre>
702 </div>
704 <p>This code is similar to what we saw for if/then/else. Because we will need
705 it to create the Phi node, we remember the block that falls through into the
706 loop. Once we have that, we create the actual block that starts the loop and
707 create an unconditional branch for the fall-through between the two blocks.</p>
710 <pre>
711 (* Start insertion in loop_bb. *)
712 position_at_end loop_bb builder;
714 (* Start the PHI node with an entry for start. *)
715 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
716 </pre>
717 </div>
720 for the loop body. To begin with, we move the insertion point and create the
721 PHI node for the loop induction variable. Since we already know the incoming
722 value for the starting value, we add it to the Phi node. Note that the Phi will
723 eventually get a second value for the backedge, but we can't set it up yet
724 (because it doesn't exist!).</p>
727 <pre>
728 (* Within the loop, the variable is defined equal to the PHI node. If it
729 * shadows an existing variable, we have to restore it, so save it
730 * now. *)
731 let old_val =
732 try Some (Hashtbl.find named_values var_name) with Not_found -> None
733 in
734 Hashtbl.add named_values var_name variable;
736 (* Emit the body of the loop. This, like any other expr, can change the
737 * current BB. Note that we ignore the value computed by the body, but
738 * don't allow an error *)
739 ignore (codegen_expr body);
740 </pre>
741 </div>
743 <p>Now the code starts to get more interesting. Our 'for' loop introduces a new
744 variable to the symbol table. This means that our symbol table can now contain
745 either function arguments or loop variables. To handle this, before we codegen
746 the body of the loop, we add the loop variable as the current value for its
747 name. Note that it is possible that there is a variable of the same name in the
748 outer scope. It would be easy to make this an error (emit an error and return
749 null if there is already an entry for VarName) but we choose to allow shadowing
750 of variables. In order to handle this correctly, we remember the Value that
752 no shadowed variable).</p>
754 <p>Once the loop variable is set into the symbol table, the code recursively
755 codegen's the body. This allows the body to use the loop variable: any
756 references to it will naturally find it in the symbol table.</p>
759 <pre>
760 (* Emit the step value. *)
761 let step_val =
762 match step with
763 | Some step -> codegen_expr step
764 (* If not specified, use 1.0. *)
766 in
768 let next_var = build_add variable step_val "nextvar" builder in
769 </pre>
770 </div>
772 <p>Now that the body is emitted, we compute the next value of the iteration
773 variable by adding the step value, or 1.0 if it isn't present.
775 of the loop.</p>
778 <pre>
779 (* Compute the end condition. *)
780 let end_cond = codegen_expr end_ in
782 (* Convert condition to a bool by comparing equal to 0.0. *)
783 let zero = const_float double_type 0.0 in
784 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
785 </pre>
786 </div>
788 <p>Finally, we evaluate the exit value of the loop, to determine whether the
789 loop should exit. This mirrors the condition evaluation for the if/then/else
790 statement.</p>
793 <pre>
794 (* Create the "after loop" block and insert it. *)
795 let loop_end_bb = insertion_block builder in
796 let after_bb = append_block context "afterloop" the_function in
798 (* Insert the conditional branch into the end of loop_end_bb. *)
799 ignore (build_cond_br end_cond loop_bb after_bb builder);
801 (* Any new code will be inserted in after_bb. *)
802 position_at_end after_bb builder;
803 </pre>
804 </div>
806 <p>With the code for the body of the loop complete, we just need to finish up
807 the control flow for it. This code remembers the end block (for the phi node), then creates the block for the loop exit ("afterloop"). Based on the value of the
808 exit condition, it creates a conditional branch that chooses between executing
809 the loop again and exiting the loop. Any future code is emitted in the
813 <pre>
814 (* Add a new entry to the PHI node for the backedge. *)
815 add_incoming (next_var, loop_end_bb) variable;
817 (* Restore the unshadowed variable. *)
818 begin match old_val with
819 | Some old_val -> Hashtbl.add named_values var_name old_val
820 | None -> ()
821 end;
823 (* for expr always returns 0.0. *)
824 const_null double_type
825 </pre>
826 </div>
828 <p>The final code handles various cleanups: now that we have the
829 "<tt>next_var</tt>" value, we can add the incoming value to the loop PHI node.
830 After that, we remove the loop variable from the symbol table, so that it isn't
831 in scope after the for loop. Finally, code generation of the for loop always
835 the tutorial. In this chapter we added two control flow constructs, and used
836 them to motivate a couple of aspects of the LLVM IR that are important for
837 front-end implementors to know. In the next chapter of our saga, we will get
839 to our poor innocent language.</p>
841 </div>
843 </div>
845 <!-- *********************************************************************** -->
847 <!-- *********************************************************************** -->
849 <div>
851 <p>
852 Here is the complete code listing for our running example, enhanced with the
853 if/then/else and for expressions.. To build this example, use:
854 </p>
857 <pre>
858 # Compile
859 ocamlbuild toy.byte
860 # Run
861 ./toy.byte
862 </pre>
863 </div>
867 <dl>
870 <pre>
875 </pre>
876 </dd>
880 <pre>
881 open Ocamlbuild_plugin;;
883 ocaml_lib ~extern:true "llvm";;
884 ocaml_lib ~extern:true "llvm_analysis";;
885 ocaml_lib ~extern:true "llvm_executionengine";;
886 ocaml_lib ~extern:true "llvm_target";;
887 ocaml_lib ~extern:true "llvm_scalar_opts";;
891 </pre>
892 </dd>
896 <pre>
897 (*===----------------------------------------------------------------------===
898 * Lexer Tokens
899 *===----------------------------------------------------------------------===*)
901 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
902 * these others for known things. *)
903 type token =
904 (* commands *)
905 | Def | Extern
907 (* primary *)
908 | Ident of string | Number of float
910 (* unknown *)
911 | Kwd of char
913 (* control *)
914 | If | Then | Else
915 | For | In
916 </pre>
917 </dd>
921 <pre>
922 (*===----------------------------------------------------------------------===
923 * Lexer
924 *===----------------------------------------------------------------------===*)
926 let rec lex = parser
927 (* Skip any whitespace. *)
930 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
932 let buffer = Buffer.create 1 in
933 Buffer.add_char buffer c;
934 lex_ident buffer stream
938 let buffer = Buffer.create 1 in
939 Buffer.add_char buffer c;
940 lex_number buffer stream
942 (* Comment until end of line. *)
944 lex_comment stream
946 (* Otherwise, just return the character as its ascii value. *)
950 (* end of stream. *)
953 and lex_number buffer = parser
955 Buffer.add_char buffer c;
956 lex_number buffer stream
960 and lex_ident buffer = parser
962 Buffer.add_char buffer c;
963 lex_ident buffer stream
965 match Buffer.contents buffer with
975 and lex_comment = parser
979 </pre>
980 </dd>
984 <pre>
985 (*===----------------------------------------------------------------------===
986 * Abstract Syntax Tree (aka Parse Tree)
987 *===----------------------------------------------------------------------===*)
989 (* expr - Base type for all expression nodes. *)
990 type expr =
991 (* variant for numeric literals like "1.0". *)
992 | Number of float
994 (* variant for referencing a variable, like "a". *)
995 | Variable of string
997 (* variant for a binary operator. *)
998 | Binary of char * expr * expr
1000 (* variant for function calls. *)
1001 | Call of string * expr array
1003 (* variant for if/then/else. *)
1004 | If of expr * expr * expr
1006 (* variant for for/in. *)
1007 | For of string * expr * expr * expr option * expr
1009 (* proto - This type represents the "prototype" for a function, which captures
1010 * its name, and its argument names (thus implicitly the number of arguments the
1011 * function takes). *)
1012 type proto = Prototype of string * string array
1014 (* func - This type represents a function definition itself. *)
1015 type func = Function of proto * expr
1016 </pre>
1017 </dd>
1021 <pre>
1022 (*===---------------------------------------------------------------------===
1023 * Parser
1024 *===---------------------------------------------------------------------===*)
1026 (* binop_precedence - This holds the precedence for each binary operator that is
1027 * defined *)
1028 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
1030 (* precedence - Get the precedence of the pending binary operator token. *)
1033 (* primary
1034 * ::= identifier
1035 * ::= numberexpr
1036 * ::= parenexpr
1037 * ::= ifexpr
1038 * ::= forexpr *)
1039 let rec parse_primary = parser
1040 (* numberexpr ::= number *)
1043 (* parenexpr ::= '(' expression ')' *)
1046 (* identifierexpr
1047 * ::= identifier
1048 * ::= identifier '(' argumentexpr ')' *)
1050 let rec parse_args accumulator = parser
1052 begin parser
1055 end stream
1057 in
1058 let rec parse_ident id = parser
1059 (* Call. *)
1060 | [< 'Token.Kwd '(';
1061 args=parse_args [];
1063 Ast.Call (id, Array.of_list (List.rev args))
1065 (* Simple variable ref. *)
1067 in
1068 parse_ident id stream
1070 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
1071 | [< 'Token.If; c=parse_expr;
1072 'Token.Then ?? "expected 'then'"; t=parse_expr;
1074 Ast.If (c, t, e)
1076 (* forexpr
1077 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
1078 | [< 'Token.For;
1079 'Token.Ident id ?? "expected identifier after for";
1080 'Token.Kwd '=' ?? "expected '=' after for";
1082 begin parser
1083 | [<
1084 start=parse_expr;
1085 'Token.Kwd ',' ?? "expected ',' after for";
1086 end_=parse_expr;
1088 let step =
1089 begin parser
1092 end stream
1093 in
1094 begin parser
1096 Ast.For (id, start, end_, step, body)
1098 raise (Stream.Error "expected 'in' after for")
1099 end stream
1101 raise (Stream.Error "expected '=' after for")
1102 end stream
1106 (* binoprhs
1107 * ::= ('+' primary)* *)
1108 and parse_bin_rhs expr_prec lhs stream =
1109 match Stream.peek stream with
1110 (* If this is a binop, find its precedence. *)
1111 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
1112 let token_prec = precedence c in
1114 (* If this is a binop that binds at least as tightly as the current binop,
1115 * consume it, otherwise we are done. *)
1116 if token_prec < expr_prec then lhs else begin
1117 (* Eat the binop. *)
1118 Stream.junk stream;
1120 (* Parse the primary expression after the binary operator. *)
1121 let rhs = parse_primary stream in
1123 (* Okay, we know this is a binop. *)
1124 let rhs =
1125 match Stream.peek stream with
1126 | Some (Token.Kwd c2) ->
1127 (* If BinOp binds less tightly with rhs than the operator after
1128 * rhs, let the pending operator take rhs as its lhs. *)
1129 let next_prec = precedence c2 in
1130 if token_prec < next_prec
1131 then parse_bin_rhs (token_prec + 1) rhs stream
1132 else rhs
1133 | _ -> rhs
1134 in
1136 (* Merge lhs/rhs. *)
1137 let lhs = Ast.Binary (c, lhs, rhs) in
1138 parse_bin_rhs expr_prec lhs stream
1139 end
1140 | _ -> lhs
1142 (* expression
1143 * ::= primary binoprhs *)
1144 and parse_expr = parser
1147 (* prototype
1148 * ::= id '(' id* ')' *)
1149 let parse_prototype =
1150 let rec parse_args accumulator = parser
1153 in
1155 parser
1156 | [< 'Token.Ident id;
1157 'Token.Kwd '(' ?? "expected '(' in prototype";
1158 args=parse_args [];
1160 (* success. *)
1161 Ast.Prototype (id, Array.of_list (List.rev args))
1164 raise (Stream.Error "expected function name in prototype")
1166 (* definition ::= 'def' prototype expression *)
1167 let parse_definition = parser
1169 Ast.Function (p, e)
1171 (* toplevelexpr ::= expression *)
1172 let parse_toplevel = parser
1174 (* Make an anonymous proto. *)
1175 Ast.Function (Ast.Prototype ("", [||]), e)
1177 (* external ::= 'extern' prototype *)
1178 let parse_extern = parser
1180 </pre>
1181 </dd>
1185 <pre>
1186 (*===----------------------------------------------------------------------===
1187 * Code Generation
1188 *===----------------------------------------------------------------------===*)
1190 open Llvm
1192 exception Error of string
1194 let context = global_context ()
1195 let the_module = create_module context "my cool jit"
1196 let builder = builder context
1197 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
1198 let double_type = double_type context
1200 let rec codegen_expr = function
1201 | Ast.Number n -> const_float double_type n
1202 | Ast.Variable name ->
1203 (try Hashtbl.find named_values name with
1205 | Ast.Binary (op, lhs, rhs) ->
1206 let lhs_val = codegen_expr lhs in
1207 let rhs_val = codegen_expr rhs in
1208 begin
1209 match op with
1215 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
1216 build_uitofp i double_type "booltmp" builder
1218 end
1219 | Ast.Call (callee, args) ->
1220 (* Look up the name in the module table. *)
1221 let callee =
1222 match lookup_function callee the_module with
1223 | Some callee -> callee
1225 in
1226 let params = params callee in
1228 (* If argument mismatch error. *)
1229 if Array.length params == Array.length args then () else
1230 raise (Error "incorrect # arguments passed");
1231 let args = Array.map codegen_expr args in
1232 build_call callee args "calltmp" builder
1233 | Ast.If (cond, then_, else_) ->
1234 let cond = codegen_expr cond in
1236 (* Convert condition to a bool by comparing equal to 0.0 *)
1237 let zero = const_float double_type 0.0 in
1238 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
1240 (* Grab the first block so that we might later add the conditional branch
1241 * to it at the end of the function. *)
1242 let start_bb = insertion_block builder in
1243 let the_function = block_parent start_bb in
1245 let then_bb = append_block context "then" the_function in
1247 (* Emit 'then' value. *)
1248 position_at_end then_bb builder;
1249 let then_val = codegen_expr then_ in
1251 (* Codegen of 'then' can change the current block, update then_bb for the
1252 * phi. We create a new name because one is used for the phi node, and the
1253 * other is used for the conditional branch. *)
1254 let new_then_bb = insertion_block builder in
1256 (* Emit 'else' value. *)
1257 let else_bb = append_block context "else" the_function in
1258 position_at_end else_bb builder;
1259 let else_val = codegen_expr else_ in
1261 (* Codegen of 'else' can change the current block, update else_bb for the
1262 * phi. *)
1263 let new_else_bb = insertion_block builder in
1265 (* Emit merge block. *)
1266 let merge_bb = append_block context "ifcont" the_function in
1267 position_at_end merge_bb builder;
1268 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
1269 let phi = build_phi incoming "iftmp" builder in
1271 (* Return to the start block to add the conditional branch. *)
1272 position_at_end start_bb builder;
1273 ignore (build_cond_br cond_val then_bb else_bb builder);
1275 (* Set a unconditional branch at the end of the 'then' block and the
1276 * 'else' block to the 'merge' block. *)
1277 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
1278 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
1280 (* Finally, set the builder to the end of the merge block. *)
1281 position_at_end merge_bb builder;
1283 phi
1284 | Ast.For (var_name, start, end_, step, body) ->
1285 (* Emit the start code first, without 'variable' in scope. *)
1286 let start_val = codegen_expr start in
1288 (* Make the new basic block for the loop header, inserting after current
1289 * block. *)
1290 let preheader_bb = insertion_block builder in
1291 let the_function = block_parent preheader_bb in
1292 let loop_bb = append_block context "loop" the_function in
1294 (* Insert an explicit fall through from the current block to the
1295 * loop_bb. *)
1296 ignore (build_br loop_bb builder);
1298 (* Start insertion in loop_bb. *)
1299 position_at_end loop_bb builder;
1301 (* Start the PHI node with an entry for start. *)
1302 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
1304 (* Within the loop, the variable is defined equal to the PHI node. If it
1305 * shadows an existing variable, we have to restore it, so save it
1306 * now. *)
1307 let old_val =
1308 try Some (Hashtbl.find named_values var_name) with Not_found -> None
1309 in
1310 Hashtbl.add named_values var_name variable;
1312 (* Emit the body of the loop. This, like any other expr, can change the
1313 * current BB. Note that we ignore the value computed by the body, but
1314 * don't allow an error *)
1315 ignore (codegen_expr body);
1317 (* Emit the step value. *)
1318 let step_val =
1319 match step with
1320 | Some step -> codegen_expr step
1321 (* If not specified, use 1.0. *)
1323 in
1325 let next_var = build_add variable step_val "nextvar" builder in
1327 (* Compute the end condition. *)
1328 let end_cond = codegen_expr end_ in
1330 (* Convert condition to a bool by comparing equal to 0.0. *)
1331 let zero = const_float double_type 0.0 in
1332 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
1334 (* Create the "after loop" block and insert it. *)
1335 let loop_end_bb = insertion_block builder in
1336 let after_bb = append_block context "afterloop" the_function in
1338 (* Insert the conditional branch into the end of loop_end_bb. *)
1339 ignore (build_cond_br end_cond loop_bb after_bb builder);
1341 (* Any new code will be inserted in after_bb. *)
1342 position_at_end after_bb builder;
1344 (* Add a new entry to the PHI node for the backedge. *)
1345 add_incoming (next_var, loop_end_bb) variable;
1347 (* Restore the unshadowed variable. *)
1348 begin match old_val with
1349 | Some old_val -> Hashtbl.add named_values var_name old_val
1350 | None -> ()
1351 end;
1353 (* for expr always returns 0.0. *)
1354 const_null double_type
1356 let codegen_proto = function
1357 | Ast.Prototype (name, args) ->
1358 (* Make the function type: double(double,double) etc. *)
1359 let doubles = Array.make (Array.length args) double_type in
1360 let ft = function_type double_type doubles in
1361 let f =
1362 match lookup_function name the_module with
1363 | None -> declare_function name ft the_module
1365 (* If 'f' conflicted, there was already something named 'name'. If it
1366 * has a body, don't allow redefinition or reextern. *)
1367 | Some f ->
1368 (* If 'f' already has a body, reject this. *)
1369 if block_begin f <> At_end f then
1370 raise (Error "redefinition of function");
1372 (* If 'f' took a different number of arguments, reject. *)
1373 if element_type (type_of f) <> ft then
1374 raise (Error "redefinition of function with different # args");
1375 f
1376 in
1378 (* Set names for all arguments. *)
1379 Array.iteri (fun i a ->
1380 let n = args.(i) in
1381 set_value_name n a;
1382 Hashtbl.add named_values n a;
1383 ) (params f);
1384 f
1386 let codegen_func the_fpm = function
1387 | Ast.Function (proto, body) ->
1388 Hashtbl.clear named_values;
1389 let the_function = codegen_proto proto in
1391 (* Create a new basic block to start insertion into. *)
1392 let bb = append_block context "entry" the_function in
1393 position_at_end bb builder;
1395 try
1396 let ret_val = codegen_expr body in
1398 (* Finish off the function. *)
1399 let _ = build_ret ret_val builder in
1401 (* Validate the generated code, checking for consistency. *)
1402 Llvm_analysis.assert_valid_function the_function;
1404 (* Optimize the function. *)
1405 let _ = PassManager.run_function the_function the_fpm in
1407 the_function
1408 with e ->
1409 delete_function the_function;
1410 raise e
1411 </pre>
1412 </dd>
1416 <pre>
1417 (*===----------------------------------------------------------------------===
1418 * Top-Level parsing and JIT Driver
1419 *===----------------------------------------------------------------------===*)
1421 open Llvm
1422 open Llvm_executionengine
1424 (* top ::= definition | external | expression | ';' *)
1425 let rec main_loop the_fpm the_execution_engine stream =
1426 match Stream.peek stream with
1427 | None -> ()
1429 (* ignore top-level semicolons. *)
1430 | Some (Token.Kwd ';') ->
1431 Stream.junk stream;
1432 main_loop the_fpm the_execution_engine stream
1434 | Some token ->
1435 begin
1436 try match token with
1437 | Token.Def ->
1438 let e = Parser.parse_definition stream in
1439 print_endline "parsed a function definition.";
1440 dump_value (Codegen.codegen_func the_fpm e);
1441 | Token.Extern ->
1442 let e = Parser.parse_extern stream in
1443 print_endline "parsed an extern.";
1444 dump_value (Codegen.codegen_proto e);
1445 | _ ->
1446 (* Evaluate a top-level expression into an anonymous function. *)
1447 let e = Parser.parse_toplevel stream in
1448 print_endline "parsed a top-level expr";
1449 let the_function = Codegen.codegen_func the_fpm e in
1450 dump_value the_function;
1452 (* JIT the function, returning a function pointer. *)
1453 let result = ExecutionEngine.run_function the_function [||]
1454 the_execution_engine in
1456 print_string "Evaluated to ";
1457 print_float (GenericValue.as_float Codegen.double_type result);
1458 print_newline ();
1459 with Stream.Error s | Codegen.Error s ->
1460 (* Skip token for error recovery. *)
1461 Stream.junk stream;
1462 print_endline s;
1463 end;
1464 print_string "ready> "; flush stdout;
1465 main_loop the_fpm the_execution_engine stream
1466 </pre>
1467 </dd>
1471 <pre>
1472 (*===----------------------------------------------------------------------===
1473 * Main driver code.
1474 *===----------------------------------------------------------------------===*)
1476 open Llvm
1477 open Llvm_executionengine
1478 open Llvm_target
1479 open Llvm_scalar_opts
1481 let main () =
1482 ignore (initialize_native_target ());
1484 (* Install standard binary operators.
1485 * 1 is the lowest precedence. *)
1487 Hashtbl.add Parser.binop_precedence '+' 20;
1488 Hashtbl.add Parser.binop_precedence '-' 20;
1489 Hashtbl.add Parser.binop_precedence '*' 40; (* highest. *)
1491 (* Prime the first token. *)
1492 print_string "ready> "; flush stdout;
1493 let stream = Lexer.lex (Stream.of_channel stdin) in
1495 (* Create the JIT. *)
1496 let the_execution_engine = ExecutionEngine.create Codegen.the_module in
1497 let the_fpm = PassManager.create_function Codegen.the_module in
1499 (* Set up the optimizer pipeline. Start with registering info about how the
1500 * target lays out data structures. *)
1501 TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
1503 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
1504 add_instruction_combination the_fpm;
1506 (* reassociate expressions. *)
1507 add_reassociation the_fpm;
1509 (* Eliminate Common SubExpressions. *)
1510 add_gvn the_fpm;
1512 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
1513 add_cfg_simplification the_fpm;
1515 ignore (PassManager.initialize the_fpm);
1517 (* Run the main "interpreter loop" now. *)
1518 Toplevel.main_loop the_fpm the_execution_engine stream;
1520 (* Print out all the generated code. *)
1521 dump_module Codegen.the_module
1522 ;;
1524 main ()
1525 </pre>
1526 </dd>
1530 <pre>
1533 /* putchard - putchar that takes a double and returns 0. */
1534 extern double putchard(double X) {
1535 putchar((char)X);
1536 return 0;
1537 }
1538 </pre>
1539 </dd>
1540 </dl>
1543 operators</a>
1544 </div>
1546 <!-- *********************************************************************** -->
1547 <hr>
1548 <address>
1557 Last modified: $Date$
1558 </address>
1559 </body>
1560 </html>