| blob | 780cab819142a70c29619fae6bb500dd9f8af810 |
4 <html>
5 <head>
11 </head>
13 <body>
17 <ul>
20 <ol>
27 </ol>
28 </li>
30 Variables / SSA Construction</li>
31 </ul>
34 <p>
37 </p>
38 </div>
40 <!-- *********************************************************************** -->
42 <!-- *********************************************************************** -->
47 with LLVM</a>" tutorial. At this point in our tutorial, we now have a fully
48 functional language that is fairly minimal, but also useful. There
49 is still one big problem with it, however. Our language doesn't have many
50 useful operators (like division, logical negation, or even any comparisons
51 besides less-than).</p>
53 <p>This chapter of the tutorial takes a wild digression into adding user-defined
54 operators to the simple and beautiful Kaleidoscope language. This digression now
55 gives us a simple and ugly language in some ways, but also a powerful one at the
56 same time. One of the great things about creating your own language is that you
57 get to decide what is good or bad. In this tutorial we'll assume that it is
58 okay to use this as a way to show some interesting parsing techniques.</p>
60 <p>At the end of this tutorial, we'll run through an example Kaleidoscope
62 an example of what you can build with Kaleidoscope and its feature set.</p>
64 </div>
66 <!-- *********************************************************************** -->
68 <!-- *********************************************************************** -->
72 <p>
73 The "operator overloading" that we will add to Kaleidoscope is more general than
74 languages like C++. In C++, you are only allowed to redefine existing
75 operators: you can't programatically change the grammar, introduce new
76 operators, change precedence levels, etc. In this chapter, we will add this
77 capability to Kaleidoscope, which will let the user round out the set of
78 operators that are supported.</p>
80 <p>The point of going into user-defined operators in a tutorial like this is to
81 show the power and flexibility of using a hand-written parser. Thus far, the parser
82 we have been implementing uses recursive descent for most parts of the grammar and
83 operator precedence parsing for the expressions. See <a
85 precedence parsing, it would be very difficult to allow the programmer to
86 introduce new operators into the grammar: the grammar is dynamically extensible
87 as the JIT runs.</p>
89 <p>The two specific features we'll add are programmable unary operators (right
90 now, Kaleidoscope has no unary operators at all) as well as binary operators.
91 An example of this is:</p>
94 <pre>
95 # Logical unary not.
96 def unary!(v)
97 if v then
98 0
99 else
100 1;
104 RHS < LHS;
107 def binary| 5 (LHS RHS)
108 if LHS then
109 1
110 else if RHS then
111 1
112 else
113 0;
115 # Define = with slightly lower precedence than relationals.
116 def binary= 9 (LHS RHS)
118 </pre>
119 </div>
121 <p>Many languages aspire to being able to implement their standard runtime
122 library in the language itself. In Kaleidoscope, we can implement significant
123 parts of the language in the library!</p>
125 <p>We will break down implementation of these features into two parts:
126 implementing support for user-defined binary operators and adding unary
127 operators.</p>
129 </div>
131 <!-- *********************************************************************** -->
133 <!-- *********************************************************************** -->
137 <p>Adding support for user-defined binary operators is pretty simple with our
138 current framework. We'll first add support for the unary/binary keywords:</p>
141 <pre>
142 type token =
143 ...
144 <b>(* operators *)
145 | Binary | Unary</b>
147 ...
149 and lex_ident buffer = parser
150 ...
155 </pre>
156 </div>
158 <p>This just adds lexer support for the unary and binary keywords, like we
160 thing about our current AST, is that we represent binary operators with full
161 generalisation by using their ASCII code as the opcode. For our extended
162 operators, we'll use this same representation, so we don't need any new AST or
163 parser support.</p>
165 <p>On the other hand, we have to be able to represent the definitions of these
166 new operators, in the "def binary| 5" part of the function definition. In our
167 grammar so far, the "name" for the function definition is parsed as the
169 represent our new user-defined operators as prototypes, we have to extend
173 <pre>
174 (* proto - This type represents the "prototype" for a function, which captures
175 * its name, and its argument names (thus implicitly the number of arguments the
176 * function takes). *)
177 type proto =
178 | Prototype of string * string array
180 </pre>
181 </div>
183 <p>Basically, in addition to knowing a name for the prototype, we now keep track
184 of whether it was an operator, and if it was, what precedence level the operator
185 is at. The precedence is only used for binary operators (as you'll see below,
186 it just doesn't apply for unary operators). Now that we have a way to represent
187 the prototype for a user-defined operator, we need to parse it:</p>
190 <pre>
191 (* prototype
192 * ::= id '(' id* ')'
193 <b>* ::= binary LETTER number? (id, id)
194 * ::= unary LETTER number? (id) *)</b>
195 let parse_prototype =
196 let rec parse_args accumulator = parser
199 in
200 let parse_operator = parser
203 in
204 let parse_binary_precedence = parser
207 in
208 parser
209 | [< 'Token.Ident id;
210 'Token.Kwd '(' ?? "expected '(' in prototype";
211 args=parse_args [];
213 (* success. *)
214 Ast.Prototype (id, Array.of_list (List.rev args))
216 'Token.Kwd op ?? "expected an operator";
217 (* Read the precedence if present. *)
218 binary_precedence=parse_binary_precedence;
219 'Token.Kwd '(' ?? "expected '(' in prototype";
220 args=parse_args [];
222 let name = prefix ^ (String.make 1 op) in
223 let args = Array.of_list (List.rev args) in
225 (* Verify right number of arguments for operator. *)
226 if Array.length args != kind
227 then raise (Stream.Error "invalid number of operands for operator")
228 else
229 if kind == 1 then
230 Ast.Prototype (name, args)
231 else
232 Ast.BinOpPrototype (name, args, binary_precedence)</b>
234 raise (Stream.Error "expected function name in prototype")
235 </pre>
236 </div>
238 <p>This is all fairly straightforward parsing code, and we have already seen
239 a lot of similar code in the past. One interesting part about the code above is
242 advantage of the fact that symbol names in the LLVM symbol table are allowed to
243 have any character in them, including embedded nul characters.</p>
245 <p>The next interesting thing to add, is codegen support for these binary
246 operators. Given our current structure, this is a simple addition of a default
247 case for our existing binary operator node:</p>
250 <pre>
251 let codegen_expr = function
252 ...
253 | Ast.Binary (op, lhs, rhs) ->
254 let lhs_val = codegen_expr lhs in
255 let rhs_val = codegen_expr rhs in
256 begin
257 match op with
263 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
264 build_uitofp i double_type "booltmp" builder
266 (* If it wasn't a builtin binary operator, it must be a user defined
267 * one. Emit a call to it. *)
269 let callee =
270 match lookup_function callee the_module with
271 | Some callee -> callee
273 in
275 end
276 </pre>
277 </div>
279 <p>As you can see above, the new code is actually really simple. It just does
280 a lookup for the appropriate operator in the symbol table and generates a
281 function call to it. Since user-defined operators are just built as normal
282 functions (because the "prototype" boils down to a function with the right
283 name) everything falls into place.</p>
288 <pre>
289 let codegen_func the_fpm = function
290 | Ast.Function (proto, body) ->
291 Hashtbl.clear named_values;
292 let the_function = codegen_proto proto in
294 <b>(* If this is an operator, install it. *)
295 begin match proto with
296 | Ast.BinOpPrototype (name, args, prec) ->
297 let op = name.[String.length name - 1] in
298 Hashtbl.add Parser.binop_precedence op prec;
299 | _ -> ()
300 end;</b>
302 (* Create a new basic block to start insertion into. *)
303 let bb = append_block "entry" the_function in
304 position_at_end bb builder;
305 ...
306 </pre>
307 </div>
309 <p>Basically, before codegening a function, if it is a user-defined operator, we
310 register it in the precedence table. This allows the binary operator parsing
311 logic we already have in place to handle it. Since we are working on a
312 fully-general operator precedence parser, this is all we need to do to "extend
315 <p>Now we have useful user-defined binary operators. This builds a lot
316 on the previous framework we built for other operators. Adding unary operators
317 is a bit more challenging, because we don't have any framework for it yet - lets
318 see what it takes.</p>
320 </div>
322 <!-- *********************************************************************** -->
324 <!-- *********************************************************************** -->
328 <p>Since we don't currently support unary operators in the Kaleidoscope
329 language, we'll need to add everything to support them. Above, we added simple
330 support for the 'unary' keyword to the lexer. In addition to that, we need an
331 AST node:</p>
334 <pre>
335 type expr =
336 ...
337 (* variant for a unary operator. *)
338 | Unary of char * expr
339 ...
340 </pre>
341 </div>
343 <p>This AST node is very simple and obvious by now. It directly mirrors the
344 binary operator AST node, except that it only has one child. With this, we
345 need to add the parsing logic. Parsing a unary operator is pretty simple: we'll
346 add a new function to do it:</p>
349 <pre>
350 (* unary
351 * ::= primary
352 * ::= '!' unary *)
353 and parse_unary = parser
354 (* If this is a unary operator, read it. *)
356 Ast.Unary (op, operand)
358 (* If the current token is not an operator, it must be a primary expr. *)
360 </pre>
361 </div>
363 <p>The grammar we add is pretty straightforward here. If we see a unary
364 operator when parsing a primary operator, we eat the operator as a prefix and
365 parse the remaining piece as another unary operator. This allows us to handle
366 multiple unary operators (e.g. "!!x"). Note that unary operators can't have
367 ambiguous parses like binary operators can, so there is no need for precedence
368 information.</p>
370 <p>The problem with this function, is that we need to call ParseUnary from
371 somewhere. To do this, we change previous callers of ParsePrimary to call
375 <pre>
376 (* binoprhs
377 * ::= ('+' primary)* *)
378 and parse_bin_rhs expr_prec lhs stream =
379 ...
380 <b>(* Parse the unary expression after the binary operator. *)
381 let rhs = parse_unary stream in</b>
382 ...
384 ...
386 (* expression
387 * ::= primary binoprhs *)
388 and parse_expr = parser
390 </pre>
391 </div>
393 <p>With these two simple changes, we are now able to parse unary operators and build the
394 AST for them. Next up, we need to add parser support for prototypes, to parse
395 the unary operator prototype. We extend the binary operator code above
396 with:</p>
399 <pre>
400 (* prototype
401 * ::= id '(' id* ')'
402 * ::= binary LETTER number? (id, id)
404 let parse_prototype =
405 let rec parse_args accumulator = parser
408 in
409 <b>let parse_operator = parser
412 in</b>
413 let parse_binary_precedence = parser
416 in
417 parser
418 | [< 'Token.Ident id;
419 'Token.Kwd '(' ?? "expected '(' in prototype";
420 args=parse_args [];
422 (* success. *)
423 Ast.Prototype (id, Array.of_list (List.rev args))
425 'Token.Kwd op ?? "expected an operator";
426 (* Read the precedence if present. *)
427 binary_precedence=parse_binary_precedence;
428 'Token.Kwd '(' ?? "expected '(' in prototype";
429 args=parse_args [];
431 let name = prefix ^ (String.make 1 op) in
432 let args = Array.of_list (List.rev args) in
434 (* Verify right number of arguments for operator. *)
435 if Array.length args != kind
436 then raise (Stream.Error "invalid number of operands for operator")
437 else
438 if kind == 1 then
439 Ast.Prototype (name, args)
440 else
441 Ast.BinOpPrototype (name, args, binary_precedence)</b>
443 raise (Stream.Error "expected function name in prototype")
444 </pre>
445 </div>
447 <p>As with binary operators, we name unary operators with a name that includes
448 the operator character. This assists us at code generation time. Speaking of,
449 the final piece we need to add is codegen support for unary operators. It looks
450 like this:</p>
453 <pre>
454 let rec codegen_expr = function
455 ...
456 | Ast.Unary (op, operand) ->
457 let operand = codegen_expr operand in
459 let callee =
460 match lookup_function callee the_module with
461 | Some callee -> callee
463 in
464 build_call callee [|operand|] "unop" builder
465 </pre>
466 </div>
468 <p>This code is similar to, but simpler than, the code for binary operators. It
469 is simpler primarily because it doesn't need to handle any predefined operators.
470 </p>
472 </div>
474 <!-- *********************************************************************** -->
476 <!-- *********************************************************************** -->
480 <p>It is somewhat hard to believe, but with a few simple extensions we've
481 covered in the last chapters, we have grown a real-ish language. With this, we
482 can do a lot of interesting things, including I/O, math, and a bunch of other
483 things. For example, we can now add a nice sequencing operator (printd is
484 defined to print out the specified value and a newline):</p>
487 <pre>
489 Read extern: declare double @printd(double)
491 ..
493 123.000000
494 456.000000
495 789.000000
496 Evaluated to 0.000000
497 </pre>
498 </div>
503 <pre>
504 # Logical unary not.
505 def unary!(v)
506 if v then
507 0
508 else
509 1;
511 # Unary negate.
512 def unary-(v)
513 0-v;
517 RHS < LHS;
519 # Binary logical or, which does not short circuit.
520 def binary| 5 (LHS RHS)
521 if LHS then
522 1
523 else if RHS then
524 1
525 else
526 0;
528 # Binary logical and, which does not short circuit.
530 if !LHS then
531 0
532 else
533 !!RHS;
535 # Define = with slightly lower precedence than relationals.
536 def binary = 9 (LHS RHS)
539 </pre>
540 </div>
543 <p>Given the previous if/then/else support, we can also define interesting
544 functions for I/O. For example, the following prints out a character whose
545 "density" reflects the value passed in: the lower the value, the denser the
546 character:</p>
549 <pre>
550 ready>
551 <b>
552 extern putchard(char)
553 def printdensity(d)
555 putchard(32) # ' '
557 putchard(46) # '.'
559 putchard(43) # '+'
560 else
562 ...
565 *++..
566 Evaluated to 0.000000
567 </pre>
568 </div>
570 <p>Based on these simple primitive operations, we can start to define more
571 interesting things. For example, here's a little function that solves for the
572 number of iterations it takes a function in the complex plane to
573 converge:</p>
576 <pre>
577 # determine whether the specific location diverges.
578 # Solve for z = z^2 + c in the complex plane.
579 def mandleconverger(real imag iters creal cimag)
581 iters
582 else
583 mandleconverger(real*real - imag*imag + creal,
584 2*real*imag + cimag,
585 iters+1, creal, cimag);
587 # return the number of iterations required for the iteration to escape
588 def mandleconverge(real imag)
589 mandleconverger(real, imag, 0, real, imag);
590 </pre>
591 </div>
594 for computation of the <a
597 for a complex orbit to escape, saturating to 255. This is not a very useful
598 function by itself, but if you plot its value over a two-dimensional plane,
599 you can see the Mandelbrot set. Given that we are limited to using putchard
600 here, our amazing graphical output is limited, but we can whip together
601 something using the density plotter above:</p>
604 <pre>
605 # compute and plot the mandlebrot set with the specified 2 dimensional range
606 # info.
607 def mandelhelp(xmin xmax xstep ymin ymax ystep)
608 for y = ymin, y < ymax, ystep in (
609 (for x = xmin, x < xmax, xstep in
610 printdensity(mandleconverge(x,y)))
611 : putchard(10)
612 )
614 # mandel - This is a convenient helper function for ploting the mandelbrot set
615 # from the specified position with the specified Magnification.
616 def mandel(realstart imagstart realmag imagmag)
617 mandelhelp(realstart, realstart+realmag*78, realmag,
618 imagstart, imagstart+imagmag*40, imagmag);
619 </pre>
620 </div>
625 <pre>
627 *******************************+++++++++++*************************************
628 *************************+++++++++++++++++++++++*******************************
629 **********************+++++++++++++++++++++++++++++****************************
630 *******************+++++++++++++++++++++.. ...++++++++*************************
631 *****************++++++++++++++++++++++.... ...+++++++++***********************
632 ***************+++++++++++++++++++++++..... ...+++++++++*********************
633 **************+++++++++++++++++++++++.... ....+++++++++********************
634 *************++++++++++++++++++++++...... .....++++++++*******************
635 ************+++++++++++++++++++++....... .......+++++++******************
636 ***********+++++++++++++++++++.... ... .+++++++*****************
637 **********+++++++++++++++++....... .+++++++****************
638 *********++++++++++++++........... ...+++++++***************
639 ********++++++++++++............ ...++++++++**************
640 ********++++++++++... .......... .++++++++**************
641 *******+++++++++..... .+++++++++*************
642 *******++++++++...... ..+++++++++*************
643 *******++++++....... ..+++++++++*************
644 *******+++++...... ..+++++++++*************
645 *******.... .... ...+++++++++*************
646 *******.... . ...+++++++++*************
647 *******+++++...... ...+++++++++*************
648 *******++++++....... ..+++++++++*************
649 *******++++++++...... .+++++++++*************
650 *******+++++++++..... ..+++++++++*************
651 ********++++++++++... .......... .++++++++**************
652 ********++++++++++++............ ...++++++++**************
653 *********++++++++++++++.......... ...+++++++***************
654 **********++++++++++++++++........ .+++++++****************
655 **********++++++++++++++++++++.... ... ..+++++++****************
656 ***********++++++++++++++++++++++....... .......++++++++*****************
657 ************+++++++++++++++++++++++...... ......++++++++******************
658 **************+++++++++++++++++++++++.... ....++++++++********************
659 ***************+++++++++++++++++++++++..... ...+++++++++*********************
660 *****************++++++++++++++++++++++.... ...++++++++***********************
661 *******************+++++++++++++++++++++......++++++++*************************
662 *********************++++++++++++++++++++++.++++++++***************************
663 *************************+++++++++++++++++++++++*******************************
664 ******************************+++++++++++++************************************
665 *******************************************************************************
666 *******************************************************************************
667 *******************************************************************************
668 Evaluated to 0.000000
670 **************************+++++++++++++++++++++++++++++++++++++++++++++++++++++
671 ***********************++++++++++++++++++++++++++++++++++++++++++++++++++++++++
672 *********************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
673 *******************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
674 *****************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.....
675 ***************++++++++++++++++++++++++++++++++++++++++++++++++++++++++........
676 **************++++++++++++++++++++++++++++++++++++++++++++++++++++++...........
677 ************+++++++++++++++++++++++++++++++++++++++++++++++++++++..............
678 ***********++++++++++++++++++++++++++++++++++++++++++++++++++........ .
679 **********++++++++++++++++++++++++++++++++++++++++++++++.............
680 ********+++++++++++++++++++++++++++++++++++++++++++..................
681 *******+++++++++++++++++++++++++++++++++++++++.......................
682 ******+++++++++++++++++++++++++++++++++++...........................
683 *****++++++++++++++++++++++++++++++++............................
684 *****++++++++++++++++++++++++++++...............................
685 ****++++++++++++++++++++++++++...... .........................
686 ***++++++++++++++++++++++++......... ...... ...........
687 ***++++++++++++++++++++++............
688 **+++++++++++++++++++++..............
689 **+++++++++++++++++++................
690 *++++++++++++++++++.................
691 *++++++++++++++++............ ...
692 *++++++++++++++..............
693 *+++....++++................
694 *.......... ...........
695 *
696 *.......... ...........
697 *+++....++++................
698 *++++++++++++++..............
699 *++++++++++++++++............ ...
700 *++++++++++++++++++.................
701 **+++++++++++++++++++................
702 **+++++++++++++++++++++..............
703 ***++++++++++++++++++++++............
704 ***++++++++++++++++++++++++......... ...... ...........
705 ****++++++++++++++++++++++++++...... .........................
706 *****++++++++++++++++++++++++++++...............................
707 *****++++++++++++++++++++++++++++++++............................
708 ******+++++++++++++++++++++++++++++++++++...........................
709 *******+++++++++++++++++++++++++++++++++++++++.......................
710 ********+++++++++++++++++++++++++++++++++++++++++++..................
711 Evaluated to 0.000000
713 *******************************************************************************
714 *******************************************************************************
715 *******************************************************************************
716 **********+++++++++++++++++++++************************************************
717 *+++++++++++++++++++++++++++++++++++++++***************************************
718 +++++++++++++++++++++++++++++++++++++++++++++**********************************
719 ++++++++++++++++++++++++++++++++++++++++++++++++++*****************************
720 ++++++++++++++++++++++++++++++++++++++++++++++++++++++*************************
721 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++**********************
722 +++++++++++++++++++++++++++++++++.........++++++++++++++++++*******************
723 +++++++++++++++++++++++++++++++.... ......+++++++++++++++++++****************
724 +++++++++++++++++++++++++++++....... ........+++++++++++++++++++**************
725 ++++++++++++++++++++++++++++........ ........++++++++++++++++++++************
726 +++++++++++++++++++++++++++......... .. ...+++++++++++++++++++++**********
727 ++++++++++++++++++++++++++........... ....++++++++++++++++++++++********
728 ++++++++++++++++++++++++............. .......++++++++++++++++++++++******
729 +++++++++++++++++++++++............. ........+++++++++++++++++++++++****
730 ++++++++++++++++++++++........... ..........++++++++++++++++++++++***
731 ++++++++++++++++++++........... .........++++++++++++++++++++++*
732 ++++++++++++++++++............ ...........++++++++++++++++++++
733 ++++++++++++++++............... .............++++++++++++++++++
734 ++++++++++++++................. ...............++++++++++++++++
735 ++++++++++++.................. .................++++++++++++++
736 +++++++++.................. .................+++++++++++++
737 ++++++........ . ......... ..++++++++++++
738 ++............ ...... ....++++++++++
739 .............. ...++++++++++
740 .............. ....+++++++++
741 .............. .....++++++++
742 ............. ......++++++++
743 ........... .......++++++++
744 ......... ........+++++++
745 ......... ........+++++++
746 ......... ....+++++++
747 ........ ...+++++++
748 ....... ...+++++++
749 ....+++++++
750 .....+++++++
751 ....+++++++
752 ....+++++++
753 ....+++++++
754 Evaluated to 0.000000
756 </pre>
757 </div>
759 <p>At this point, you may be starting to realize that Kaleidoscope is a real
760 and powerful language. It may not be self-similar :), but it can be used to
761 plot things that are!</p>
764 tutorial. We have successfully augmented our language, adding the ability to
765 extend the language in the library, and we have shown how this can be used to
766 build a simple but interesting end-user application in Kaleidoscope. At this
767 point, Kaleidoscope can build a variety of applications that are functional and
768 can call functions with side-effects, but it can't actually define and mutate a
769 variable itself.</p>
771 <p>Strikingly, variable mutation is an important feature of some
774 phase to your front-end. In the next chapter, we will describe how you can
775 add variable mutation without building SSA in your front-end.</p>
777 </div>
780 <!-- *********************************************************************** -->
782 <!-- *********************************************************************** -->
786 <p>
787 Here is the complete code listing for our running example, enhanced with the
788 if/then/else and for expressions.. To build this example, use:
789 </p>
792 <pre>
793 # Compile
794 ocamlbuild toy.byte
795 # Run
796 ./toy.byte
797 </pre>
798 </div>
802 <dl>
805 <pre>
810 </pre>
811 </dd>
815 <pre>
816 open Ocamlbuild_plugin;;
818 ocaml_lib ~extern:true "llvm";;
819 ocaml_lib ~extern:true "llvm_analysis";;
820 ocaml_lib ~extern:true "llvm_executionengine";;
821 ocaml_lib ~extern:true "llvm_target";;
822 ocaml_lib ~extern:true "llvm_scalar_opts";;
826 </pre>
827 </dd>
831 <pre>
832 (*===----------------------------------------------------------------------===
833 * Lexer Tokens
834 *===----------------------------------------------------------------------===*)
836 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
837 * these others for known things. *)
838 type token =
839 (* commands *)
840 | Def | Extern
842 (* primary *)
843 | Ident of string | Number of float
845 (* unknown *)
846 | Kwd of char
848 (* control *)
849 | If | Then | Else
850 | For | In
852 (* operators *)
853 | Binary | Unary
854 </pre>
855 </dd>
859 <pre>
860 (*===----------------------------------------------------------------------===
861 * Lexer
862 *===----------------------------------------------------------------------===*)
864 let rec lex = parser
865 (* Skip any whitespace. *)
868 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
870 let buffer = Buffer.create 1 in
871 Buffer.add_char buffer c;
872 lex_ident buffer stream
876 let buffer = Buffer.create 1 in
877 Buffer.add_char buffer c;
878 lex_number buffer stream
880 (* Comment until end of line. *)
882 lex_comment stream
884 (* Otherwise, just return the character as its ascii value. *)
888 (* end of stream. *)
891 and lex_number buffer = parser
893 Buffer.add_char buffer c;
894 lex_number buffer stream
898 and lex_ident buffer = parser
900 Buffer.add_char buffer c;
901 lex_ident buffer stream
903 match Buffer.contents buffer with
915 and lex_comment = parser
919 </pre>
920 </dd>
924 <pre>
925 (*===----------------------------------------------------------------------===
926 * Abstract Syntax Tree (aka Parse Tree)
927 *===----------------------------------------------------------------------===*)
929 (* expr - Base type for all expression nodes. *)
930 type expr =
931 (* variant for numeric literals like "1.0". *)
932 | Number of float
934 (* variant for referencing a variable, like "a". *)
935 | Variable of string
937 (* variant for a unary operator. *)
938 | Unary of char * expr
940 (* variant for a binary operator. *)
941 | Binary of char * expr * expr
943 (* variant for function calls. *)
944 | Call of string * expr array
946 (* variant for if/then/else. *)
947 | If of expr * expr * expr
949 (* variant for for/in. *)
950 | For of string * expr * expr * expr option * expr
952 (* proto - This type represents the "prototype" for a function, which captures
953 * its name, and its argument names (thus implicitly the number of arguments the
954 * function takes). *)
955 type proto =
956 | Prototype of string * string array
957 | BinOpPrototype of string * string array * int
959 (* func - This type represents a function definition itself. *)
960 type func = Function of proto * expr
961 </pre>
962 </dd>
966 <pre>
967 (*===---------------------------------------------------------------------===
968 * Parser
969 *===---------------------------------------------------------------------===*)
971 (* binop_precedence - This holds the precedence for each binary operator that is
972 * defined *)
973 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
975 (* precedence - Get the precedence of the pending binary operator token. *)
978 (* primary
979 * ::= identifier
980 * ::= numberexpr
981 * ::= parenexpr
982 * ::= ifexpr
983 * ::= forexpr *)
984 let rec parse_primary = parser
985 (* numberexpr ::= number *)
988 (* parenexpr ::= '(' expression ')' *)
991 (* identifierexpr
992 * ::= identifier
993 * ::= identifier '(' argumentexpr ')' *)
995 let rec parse_args accumulator = parser
997 begin parser
1000 end stream
1002 in
1003 let rec parse_ident id = parser
1004 (* Call. *)
1005 | [< 'Token.Kwd '(';
1006 args=parse_args [];
1008 Ast.Call (id, Array.of_list (List.rev args))
1010 (* Simple variable ref. *)
1012 in
1013 parse_ident id stream
1015 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
1016 | [< 'Token.If; c=parse_expr;
1017 'Token.Then ?? "expected 'then'"; t=parse_expr;
1019 Ast.If (c, t, e)
1021 (* forexpr
1022 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
1023 | [< 'Token.For;
1024 'Token.Ident id ?? "expected identifier after for";
1025 'Token.Kwd '=' ?? "expected '=' after for";
1027 begin parser
1028 | [<
1029 start=parse_expr;
1030 'Token.Kwd ',' ?? "expected ',' after for";
1031 end_=parse_expr;
1033 let step =
1034 begin parser
1037 end stream
1038 in
1039 begin parser
1041 Ast.For (id, start, end_, step, body)
1043 raise (Stream.Error "expected 'in' after for")
1044 end stream
1046 raise (Stream.Error "expected '=' after for")
1047 end stream
1051 (* unary
1052 * ::= primary
1053 * ::= '!' unary *)
1054 and parse_unary = parser
1055 (* If this is a unary operator, read it. *)
1057 Ast.Unary (op, operand)
1059 (* If the current token is not an operator, it must be a primary expr. *)
1062 (* binoprhs
1063 * ::= ('+' primary)* *)
1064 and parse_bin_rhs expr_prec lhs stream =
1065 match Stream.peek stream with
1066 (* If this is a binop, find its precedence. *)
1067 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
1068 let token_prec = precedence c in
1070 (* If this is a binop that binds at least as tightly as the current binop,
1071 * consume it, otherwise we are done. *)
1072 if token_prec < expr_prec then lhs else begin
1073 (* Eat the binop. *)
1074 Stream.junk stream;
1076 (* Parse the unary expression after the binary operator. *)
1077 let rhs = parse_unary stream in
1079 (* Okay, we know this is a binop. *)
1080 let rhs =
1081 match Stream.peek stream with
1082 | Some (Token.Kwd c2) ->
1083 (* If BinOp binds less tightly with rhs than the operator after
1084 * rhs, let the pending operator take rhs as its lhs. *)
1085 let next_prec = precedence c2 in
1086 if token_prec < next_prec
1087 then parse_bin_rhs (token_prec + 1) rhs stream
1088 else rhs
1089 | _ -> rhs
1090 in
1092 (* Merge lhs/rhs. *)
1093 let lhs = Ast.Binary (c, lhs, rhs) in
1094 parse_bin_rhs expr_prec lhs stream
1095 end
1096 | _ -> lhs
1098 (* expression
1099 * ::= primary binoprhs *)
1100 and parse_expr = parser
1103 (* prototype
1104 * ::= id '(' id* ')'
1105 * ::= binary LETTER number? (id, id)
1106 * ::= unary LETTER number? (id) *)
1107 let parse_prototype =
1108 let rec parse_args accumulator = parser
1111 in
1112 let parse_operator = parser
1115 in
1116 let parse_binary_precedence = parser
1119 in
1120 parser
1121 | [< 'Token.Ident id;
1122 'Token.Kwd '(' ?? "expected '(' in prototype";
1123 args=parse_args [];
1125 (* success. *)
1126 Ast.Prototype (id, Array.of_list (List.rev args))
1127 | [< (prefix, kind)=parse_operator;
1128 'Token.Kwd op ?? "expected an operator";
1129 (* Read the precedence if present. *)
1130 binary_precedence=parse_binary_precedence;
1131 'Token.Kwd '(' ?? "expected '(' in prototype";
1132 args=parse_args [];
1134 let name = prefix ^ (String.make 1 op) in
1135 let args = Array.of_list (List.rev args) in
1137 (* Verify right number of arguments for operator. *)
1138 if Array.length args != kind
1139 then raise (Stream.Error "invalid number of operands for operator")
1140 else
1141 if kind == 1 then
1142 Ast.Prototype (name, args)
1143 else
1144 Ast.BinOpPrototype (name, args, binary_precedence)
1146 raise (Stream.Error "expected function name in prototype")
1148 (* definition ::= 'def' prototype expression *)
1149 let parse_definition = parser
1151 Ast.Function (p, e)
1153 (* toplevelexpr ::= expression *)
1154 let parse_toplevel = parser
1156 (* Make an anonymous proto. *)
1157 Ast.Function (Ast.Prototype ("", [||]), e)
1159 (* external ::= 'extern' prototype *)
1160 let parse_extern = parser
1162 </pre>
1163 </dd>
1167 <pre>
1168 (*===----------------------------------------------------------------------===
1169 * Code Generation
1170 *===----------------------------------------------------------------------===*)
1172 open Llvm
1174 exception Error of string
1176 let the_module = create_module "my cool jit"
1177 let builder = builder ()
1178 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
1180 let rec codegen_expr = function
1181 | Ast.Number n -> const_float double_type n
1182 | Ast.Variable name ->
1183 (try Hashtbl.find named_values name with
1185 | Ast.Unary (op, operand) ->
1186 let operand = codegen_expr operand in
1188 let callee =
1189 match lookup_function callee the_module with
1190 | Some callee -> callee
1192 in
1193 build_call callee [|operand|] "unop" builder
1194 | Ast.Binary (op, lhs, rhs) ->
1195 let lhs_val = codegen_expr lhs in
1196 let rhs_val = codegen_expr rhs in
1197 begin
1198 match op with
1204 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
1205 build_uitofp i double_type "booltmp" builder
1206 | _ ->
1207 (* If it wasn't a builtin binary operator, it must be a user defined
1208 * one. Emit a call to it. *)
1210 let callee =
1211 match lookup_function callee the_module with
1212 | Some callee -> callee
1214 in
1215 build_call callee [|lhs_val; rhs_val|] "binop" builder
1216 end
1217 | Ast.Call (callee, args) ->
1218 (* Look up the name in the module table. *)
1219 let callee =
1220 match lookup_function callee the_module with
1221 | Some callee -> callee
1223 in
1224 let params = params callee in
1226 (* If argument mismatch error. *)
1227 if Array.length params == Array.length args then () else
1228 raise (Error "incorrect # arguments passed");
1229 let args = Array.map codegen_expr args in
1230 build_call callee args "calltmp" builder
1231 | Ast.If (cond, then_, else_) ->
1232 let cond = codegen_expr cond in
1234 (* Convert condition to a bool by comparing equal to 0.0 *)
1235 let zero = const_float double_type 0.0 in
1236 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
1238 (* Grab the first block so that we might later add the conditional branch
1239 * to it at the end of the function. *)
1240 let start_bb = insertion_block builder in
1241 let the_function = block_parent start_bb in
1243 let then_bb = append_block "then" the_function in
1245 (* Emit 'then' value. *)
1246 position_at_end then_bb builder;
1247 let then_val = codegen_expr then_ in
1249 (* Codegen of 'then' can change the current block, update then_bb for the
1250 * phi. We create a new name because one is used for the phi node, and the
1251 * other is used for the conditional branch. *)
1252 let new_then_bb = insertion_block builder in
1254 (* Emit 'else' value. *)
1255 let else_bb = append_block "else" the_function in
1256 position_at_end else_bb builder;
1257 let else_val = codegen_expr else_ in
1259 (* Codegen of 'else' can change the current block, update else_bb for the
1260 * phi. *)
1261 let new_else_bb = insertion_block builder in
1263 (* Emit merge block. *)
1264 let merge_bb = append_block "ifcont" the_function in
1265 position_at_end merge_bb builder;
1266 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
1267 let phi = build_phi incoming "iftmp" builder in
1269 (* Return to the start block to add the conditional branch. *)
1270 position_at_end start_bb builder;
1271 ignore (build_cond_br cond_val then_bb else_bb builder);
1273 (* Set a unconditional branch at the end of the 'then' block and the
1274 * 'else' block to the 'merge' block. *)
1275 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
1276 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
1278 (* Finally, set the builder to the end of the merge block. *)
1279 position_at_end merge_bb builder;
1281 phi
1282 | Ast.For (var_name, start, end_, step, body) ->
1283 (* Emit the start code first, without 'variable' in scope. *)
1284 let start_val = codegen_expr start in
1286 (* Make the new basic block for the loop header, inserting after current
1287 * block. *)
1288 let preheader_bb = insertion_block builder in
1289 let the_function = block_parent preheader_bb in
1290 let loop_bb = append_block "loop" the_function in
1292 (* Insert an explicit fall through from the current block to the
1293 * loop_bb. *)
1294 ignore (build_br loop_bb builder);
1296 (* Start insertion in loop_bb. *)
1297 position_at_end loop_bb builder;
1299 (* Start the PHI node with an entry for start. *)
1300 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
1302 (* Within the loop, the variable is defined equal to the PHI node. If it
1303 * shadows an existing variable, we have to restore it, so save it
1304 * now. *)
1305 let old_val =
1306 try Some (Hashtbl.find named_values var_name) with Not_found -> None
1307 in
1308 Hashtbl.add named_values var_name variable;
1310 (* Emit the body of the loop. This, like any other expr, can change the
1311 * current BB. Note that we ignore the value computed by the body, but
1312 * don't allow an error *)
1313 ignore (codegen_expr body);
1315 (* Emit the step value. *)
1316 let step_val =
1317 match step with
1318 | Some step -> codegen_expr step
1319 (* If not specified, use 1.0. *)
1321 in
1323 let next_var = build_add variable step_val "nextvar" builder in
1325 (* Compute the end condition. *)
1326 let end_cond = codegen_expr end_ in
1328 (* Convert condition to a bool by comparing equal to 0.0. *)
1329 let zero = const_float double_type 0.0 in
1330 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
1332 (* Create the "after loop" block and insert it. *)
1333 let loop_end_bb = insertion_block builder in
1334 let after_bb = append_block "afterloop" the_function in
1336 (* Insert the conditional branch into the end of loop_end_bb. *)
1337 ignore (build_cond_br end_cond loop_bb after_bb builder);
1339 (* Any new code will be inserted in after_bb. *)
1340 position_at_end after_bb builder;
1342 (* Add a new entry to the PHI node for the backedge. *)
1343 add_incoming (next_var, loop_end_bb) variable;
1345 (* Restore the unshadowed variable. *)
1346 begin match old_val with
1347 | Some old_val -> Hashtbl.add named_values var_name old_val
1348 | None -> ()
1349 end;
1351 (* for expr always returns 0.0. *)
1352 const_null double_type
1354 let codegen_proto = function
1355 | Ast.Prototype (name, args) | Ast.BinOpPrototype (name, args, _) ->
1356 (* Make the function type: double(double,double) etc. *)
1357 let doubles = Array.make (Array.length args) double_type in
1358 let ft = function_type double_type doubles in
1359 let f =
1360 match lookup_function name the_module with
1361 | None -> declare_function name ft the_module
1363 (* If 'f' conflicted, there was already something named 'name'. If it
1364 * has a body, don't allow redefinition or reextern. *)
1365 | Some f ->
1366 (* If 'f' already has a body, reject this. *)
1367 if block_begin f <> At_end f then
1368 raise (Error "redefinition of function");
1370 (* If 'f' took a different number of arguments, reject. *)
1371 if element_type (type_of f) <> ft then
1372 raise (Error "redefinition of function with different # args");
1373 f
1374 in
1376 (* Set names for all arguments. *)
1377 Array.iteri (fun i a ->
1378 let n = args.(i) in
1379 set_value_name n a;
1380 Hashtbl.add named_values n a;
1381 ) (params f);
1382 f
1384 let codegen_func the_fpm = function
1385 | Ast.Function (proto, body) ->
1386 Hashtbl.clear named_values;
1387 let the_function = codegen_proto proto in
1389 (* If this is an operator, install it. *)
1390 begin match proto with
1391 | Ast.BinOpPrototype (name, args, prec) ->
1392 let op = name.[String.length name - 1] in
1393 Hashtbl.add Parser.binop_precedence op prec;
1394 | _ -> ()
1395 end;
1397 (* Create a new basic block to start insertion into. *)
1398 let bb = append_block "entry" the_function in
1399 position_at_end bb builder;
1401 try
1402 let ret_val = codegen_expr body in
1404 (* Finish off the function. *)
1405 let _ = build_ret ret_val builder in
1407 (* Validate the generated code, checking for consistency. *)
1408 Llvm_analysis.assert_valid_function the_function;
1410 (* Optimize the function. *)
1411 let _ = PassManager.run_function the_function the_fpm in
1413 the_function
1414 with e ->
1415 delete_function the_function;
1416 raise e
1417 </pre>
1418 </dd>
1422 <pre>
1423 (*===----------------------------------------------------------------------===
1424 * Top-Level parsing and JIT Driver
1425 *===----------------------------------------------------------------------===*)
1427 open Llvm
1428 open Llvm_executionengine
1430 (* top ::= definition | external | expression | ';' *)
1431 let rec main_loop the_fpm the_execution_engine stream =
1432 match Stream.peek stream with
1433 | None -> ()
1435 (* ignore top-level semicolons. *)
1436 | Some (Token.Kwd ';') ->
1437 Stream.junk stream;
1438 main_loop the_fpm the_execution_engine stream
1440 | Some token ->
1441 begin
1442 try match token with
1443 | Token.Def ->
1444 let e = Parser.parse_definition stream in
1445 print_endline "parsed a function definition.";
1446 dump_value (Codegen.codegen_func the_fpm e);
1447 | Token.Extern ->
1448 let e = Parser.parse_extern stream in
1449 print_endline "parsed an extern.";
1450 dump_value (Codegen.codegen_proto e);
1451 | _ ->
1452 (* Evaluate a top-level expression into an anonymous function. *)
1453 let e = Parser.parse_toplevel stream in
1454 print_endline "parsed a top-level expr";
1455 let the_function = Codegen.codegen_func the_fpm e in
1456 dump_value the_function;
1458 (* JIT the function, returning a function pointer. *)
1459 let result = ExecutionEngine.run_function the_function [||]
1460 the_execution_engine in
1462 print_string "Evaluated to ";
1463 print_float (GenericValue.as_float double_type result);
1464 print_newline ();
1465 with Stream.Error s | Codegen.Error s ->
1466 (* Skip token for error recovery. *)
1467 Stream.junk stream;
1468 print_endline s;
1469 end;
1470 print_string "ready> "; flush stdout;
1471 main_loop the_fpm the_execution_engine stream
1472 </pre>
1473 </dd>
1477 <pre>
1478 (*===----------------------------------------------------------------------===
1479 * Main driver code.
1480 *===----------------------------------------------------------------------===*)
1482 open Llvm
1483 open Llvm_executionengine
1484 open Llvm_target
1485 open Llvm_scalar_opts
1487 let main () =
1488 (* Install standard binary operators.
1489 * 1 is the lowest precedence. *)
1491 Hashtbl.add Parser.binop_precedence '+' 20;
1492 Hashtbl.add Parser.binop_precedence '-' 20;
1493 Hashtbl.add Parser.binop_precedence '*' 40; (* highest. *)
1495 (* Prime the first token. *)
1496 print_string "ready> "; flush stdout;
1497 let stream = Lexer.lex (Stream.of_channel stdin) in
1499 (* Create the JIT. *)
1500 let the_module_provider = ModuleProvider.create Codegen.the_module in
1501 let the_execution_engine = ExecutionEngine.create the_module_provider in
1502 let the_fpm = PassManager.create_function the_module_provider in
1504 (* Set up the optimizer pipeline. Start with registering info about how the
1505 * target lays out data structures. *)
1506 TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
1508 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
1509 add_instruction_combining the_fpm;
1511 (* reassociate expressions. *)
1512 add_reassociation the_fpm;
1514 (* Eliminate Common SubExpressions. *)
1515 add_gvn the_fpm;
1517 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
1518 add_cfg_simplification the_fpm;
1520 (* Run the main "interpreter loop" now. *)
1521 Toplevel.main_loop the_fpm the_execution_engine stream;
1523 (* Print out all the generated code. *)
1524 dump_module Codegen.the_module
1525 ;;
1527 main ()
1528 </pre>
1529 </dd>
1533 <pre>
1536 /* putchard - putchar that takes a double and returns 0. */
1537 extern double putchard(double X) {
1538 putchar((char)X);
1539 return 0;
1540 }
1543 extern double printd(double X) {
1544 printf("%f\n", X);
1545 return 0;
1546 }
1547 </pre>
1548 </dd>
1549 </dl>
1552 SSA construction</a>
1553 </div>
1555 <!-- *********************************************************************** -->
1556 <hr>
1557 <address>
1567 </address>
1568 </body>
1569 </html>