1 ==================================================
2 Kaleidoscope: Extending the Language: Control Flow
3 ==================================================
11 Welcome to Chapter 5 of the "`Implementing a language with
12 LLVM <index.html>`_" tutorial. Parts 1-4 described the implementation of
13 the simple Kaleidoscope language and included support for generating
14 LLVM IR, followed by optimizations and a JIT compiler. Unfortunately, as
15 presented, Kaleidoscope is mostly useless: it has no control flow other
16 than call and return. This means that you can't have conditional
17 branches in the code, significantly limiting its power. In this episode
18 of "build that compiler", we'll extend Kaleidoscope to have an
19 if/then/else expression plus a simple 'for' loop.
24 Extending Kaleidoscope to support if/then/else is quite straightforward.
25 It basically requires adding lexer support for this "new" concept to the
26 lexer, parser, AST, and LLVM code emitter. This example is nice, because
27 it shows how easy it is to "grow" a language over time, incrementally
28 extending it as new ideas are discovered.
30 Before we get going on "how" we add this extension, lets talk about
31 "what" we want. The basic idea is that we want to be able to write this
42 In Kaleidoscope, every construct is an expression: there are no
43 statements. As such, the if/then/else expression needs to return a value
44 like any other. Since we're using a mostly functional form, we'll have
45 it evaluate its conditional, then return the 'then' or 'else' value
46 based on how the condition was resolved. This is very similar to the C
49 The semantics of the if/then/else expression is that it evaluates the
50 condition to a boolean equality value: 0.0 is considered to be false and
51 everything else is considered to be true. If the condition is true, the
52 first subexpression is evaluated and returned, if the condition is
53 false, the second subexpression is evaluated and returned. Since
54 Kaleidoscope allows side-effects, this behavior is important to nail
57 Now that we know what we "want", lets break this down into its
60 Lexer Extensions for If/Then/Else
61 ---------------------------------
63 The lexer extensions are straightforward. First we add new variants for
69 | If | Then | Else | For | In
71 Once we have that, we recognize the new keywords in the lexer. This is
77 match Buffer.contents buffer with
78 | "def" -> [< 'Token.Def; stream >]
79 | "extern" -> [< 'Token.Extern; stream >]
80 | "if" -> [< 'Token.If; stream >]
81 | "then" -> [< 'Token.Then; stream >]
82 | "else" -> [< 'Token.Else; stream >]
83 | "for" -> [< 'Token.For; stream >]
84 | "in" -> [< 'Token.In; stream >]
85 | id -> [< 'Token.Ident id; stream >]
87 AST Extensions for If/Then/Else
88 -------------------------------
90 To represent the new expression we add a new AST variant for it:
96 (* variant for if/then/else. *)
97 | If of expr * expr * expr
99 The AST variant just has pointers to the various subexpressions.
101 Parser Extensions for If/Then/Else
102 ----------------------------------
104 Now that we have the relevant tokens coming from the lexer and we have
105 the AST node to build, our parsing logic is relatively straightforward.
106 First we define a new parsing function:
108 .. code-block:: ocaml
110 let rec parse_primary = parser
112 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
113 | [< 'Token.If; c=parse_expr;
114 'Token.Then ?? "expected 'then'"; t=parse_expr;
115 'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
118 Next we hook it up as a primary expression:
120 .. code-block:: ocaml
122 let rec parse_primary = parser
124 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
125 | [< 'Token.If; c=parse_expr;
126 'Token.Then ?? "expected 'then'"; t=parse_expr;
127 'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
130 LLVM IR for If/Then/Else
131 ------------------------
133 Now that we have it parsing and building the AST, the final piece is
134 adding LLVM code generation support. This is the most interesting part
135 of the if/then/else example, because this is where it starts to
136 introduce new concepts. All of the code above has been thoroughly
137 described in previous chapters.
139 To motivate the code we want to produce, lets take a look at a simple
146 def baz(x) if x then foo() else bar();
148 If you disable optimizations, the code you'll (soon) get from
149 Kaleidoscope looks like this:
153 declare double @foo()
155 declare double @bar()
157 define double @baz(double %x) {
159 %ifcond = fcmp one double %x, 0.000000e+00
160 br i1 %ifcond, label %then, label %else
162 then: ; preds = %entry
163 %calltmp = call double @foo()
166 else: ; preds = %entry
167 %calltmp1 = call double @bar()
170 ifcont: ; preds = %else, %then
171 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
175 To visualize the control flow graph, you can use a nifty feature of the
176 LLVM '`opt <http://llvm.org/cmds/opt.html>`_' tool. If you put this LLVM
177 IR into "t.ll" and run "``llvm-as < t.ll | opt -analyze -view-cfg``", `a
178 window will pop up <../ProgrammersManual.html#ViewGraph>`_ and you'll
181 .. figure:: LangImpl5-cfg.png
187 Another way to get this is to call
188 "``Llvm_analysis.view_function_cfg f``" or
189 "``Llvm_analysis.view_function_cfg_only f``" (where ``f`` is a
190 "``Function``") either by inserting actual calls into the code and
191 recompiling or by calling these in the debugger. LLVM has many nice
192 features for visualizing various graphs.
194 Getting back to the generated code, it is fairly simple: the entry block
195 evaluates the conditional expression ("x" in our case here) and compares
196 the result to 0.0 with the "``fcmp one``" instruction ('one' is "Ordered
197 and Not Equal"). Based on the result of this expression, the code jumps
198 to either the "then" or "else" blocks, which contain the expressions for
199 the true/false cases.
201 Once the then/else blocks are finished executing, they both branch back
202 to the 'ifcont' block to execute the code that happens after the
203 if/then/else. In this case the only thing left to do is to return to the
204 caller of the function. The question then becomes: how does the code
205 know which expression to return?
207 The answer to this question involves an important SSA operation: the
209 operation <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_.
210 If you're not familiar with SSA, `the wikipedia
211 article <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_
212 is a good introduction and there are various other introductions to it
213 available on your favorite search engine. The short version is that
214 "execution" of the Phi operation requires "remembering" which block
215 control came from. The Phi operation takes on the value corresponding to
216 the input control block. In this case, if control comes in from the
217 "then" block, it gets the value of "calltmp". If control comes from the
218 "else" block, it gets the value of "calltmp1".
220 At this point, you are probably starting to think "Oh no! This means my
221 simple and elegant front-end will have to start generating SSA form in
222 order to use LLVM!". Fortunately, this is not the case, and we strongly
223 advise *not* implementing an SSA construction algorithm in your
224 front-end unless there is an amazingly good reason to do so. In
225 practice, there are two sorts of values that float around in code
226 written for your average imperative programming language that might need
229 #. Code that involves user variables: ``x = 1; x = x + 1;``
230 #. Values that are implicit in the structure of your AST, such as the
231 Phi node in this case.
233 In `Chapter 7 <OCamlLangImpl7.html>`_ of this tutorial ("mutable
234 variables"), we'll talk about #1 in depth. For now, just believe me that
235 you don't need SSA construction to handle this case. For #2, you have
236 the choice of using the techniques that we will describe for #1, or you
237 can insert Phi nodes directly, if convenient. In this case, it is really
238 really easy to generate the Phi node, so we choose to do it directly.
240 Okay, enough of the motivation and overview, lets generate code!
242 Code Generation for If/Then/Else
243 --------------------------------
245 In order to generate code for this, we implement the ``Codegen`` method
248 .. code-block:: ocaml
250 let rec codegen_expr = function
252 | Ast.If (cond, then_, else_) ->
253 let cond = codegen_expr cond in
255 (* Convert condition to a bool by comparing equal to 0.0 *)
256 let zero = const_float double_type 0.0 in
257 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
259 This code is straightforward and similar to what we saw before. We emit
260 the expression for the condition, then compare that value to zero to get
261 a truth value as a 1-bit (bool) value.
263 .. code-block:: ocaml
265 (* Grab the first block so that we might later add the conditional branch
266 * to it at the end of the function. *)
267 let start_bb = insertion_block builder in
268 let the_function = block_parent start_bb in
270 let then_bb = append_block context "then" the_function in
271 position_at_end then_bb builder;
273 As opposed to the `C++ tutorial <LangImpl5.html>`_, we have to build our
274 basic blocks bottom up since we can't have dangling BasicBlocks. We
275 start off by saving a pointer to the first block (which might not be the
276 entry block), which we'll need to build a conditional branch later. We
277 do this by asking the ``builder`` for the current BasicBlock. The fourth
278 line gets the current Function object that is being built. It gets this
279 by the ``start_bb`` for its "parent" (the function it is currently
282 Once it has that, it creates one block. It is automatically appended
283 into the function's list of blocks.
285 .. code-block:: ocaml
287 (* Emit 'then' value. *)
288 position_at_end then_bb builder;
289 let then_val = codegen_expr then_ in
291 (* Codegen of 'then' can change the current block, update then_bb for the
292 * phi. We create a new name because one is used for the phi node, and the
293 * other is used for the conditional branch. *)
294 let new_then_bb = insertion_block builder in
296 We move the builder to start inserting into the "then" block. Strictly
297 speaking, this call moves the insertion point to be at the end of the
298 specified block. However, since the "then" block is empty, it also
299 starts out by inserting at the beginning of the block. :)
301 Once the insertion point is set, we recursively codegen the "then"
302 expression from the AST.
304 The final line here is quite subtle, but is very important. The basic
305 issue is that when we create the Phi node in the merge block, we need to
306 set up the block/value pairs that indicate how the Phi will work.
307 Importantly, the Phi node expects to have an entry for each predecessor
308 of the block in the CFG. Why then, are we getting the current block when
309 we just set it to ThenBB 5 lines above? The problem is that the "Then"
310 expression may actually itself change the block that the Builder is
311 emitting into if, for example, it contains a nested "if/then/else"
312 expression. Because calling Codegen recursively could arbitrarily change
313 the notion of the current block, we are required to get an up-to-date
314 value for code that will set up the Phi node.
316 .. code-block:: ocaml
318 (* Emit 'else' value. *)
319 let else_bb = append_block context "else" the_function in
320 position_at_end else_bb builder;
321 let else_val = codegen_expr else_ in
323 (* Codegen of 'else' can change the current block, update else_bb for the
325 let new_else_bb = insertion_block builder in
327 Code generation for the 'else' block is basically identical to codegen
328 for the 'then' block.
330 .. code-block:: ocaml
332 (* Emit merge block. *)
333 let merge_bb = append_block context "ifcont" the_function in
334 position_at_end merge_bb builder;
335 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
336 let phi = build_phi incoming "iftmp" builder in
338 The first two lines here are now familiar: the first adds the "merge"
339 block to the Function object. The second block changes the insertion
340 point so that newly created code will go into the "merge" block. Once
341 that is done, we need to create the PHI node and set up the block/value
344 .. code-block:: ocaml
346 (* Return to the start block to add the conditional branch. *)
347 position_at_end start_bb builder;
348 ignore (build_cond_br cond_val then_bb else_bb builder);
350 Once the blocks are created, we can emit the conditional branch that
351 chooses between them. Note that creating new blocks does not implicitly
352 affect the IRBuilder, so it is still inserting into the block that the
353 condition went into. This is why we needed to save the "start" block.
355 .. code-block:: ocaml
357 (* Set a unconditional branch at the end of the 'then' block and the
358 * 'else' block to the 'merge' block. *)
359 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
360 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
362 (* Finally, set the builder to the end of the merge block. *)
363 position_at_end merge_bb builder;
367 To finish off the blocks, we create an unconditional branch to the merge
368 block. One interesting (and very important) aspect of the LLVM IR is
369 that it `requires all basic blocks to be
370 "terminated" <../LangRef.html#functionstructure>`_ with a `control flow
371 instruction <../LangRef.html#terminators>`_ such as return or branch.
372 This means that all control flow, *including fall throughs* must be made
373 explicit in the LLVM IR. If you violate this rule, the verifier will
376 Finally, the CodeGen function returns the phi node as the value computed
377 by the if/then/else expression. In our example above, this returned
378 value will feed into the code for the top-level function, which will
379 create the return instruction.
381 Overall, we now have the ability to execute conditional code in
382 Kaleidoscope. With this extension, Kaleidoscope is a fairly complete
383 language that can calculate a wide variety of numeric functions. Next up
384 we'll add another useful expression that is familiar from non-functional
387 'for' Loop Expression
388 =====================
390 Now that we know how to add basic control flow constructs to the
391 language, we have the tools to add more powerful things. Lets add
392 something more aggressive, a 'for' expression:
396 extern putchard(char);
398 for i = 1, i < n, 1.0 in
399 putchard(42); # ascii 42 = '*'
401 # print 100 '*' characters
404 This expression defines a new variable ("i" in this case) which iterates
405 from a starting value, while the condition ("i < n" in this case) is
406 true, incrementing by an optional step value ("1.0" in this case). If
407 the step value is omitted, it defaults to 1.0. While the loop is true,
408 it executes its body expression. Because we don't have anything better
409 to return, we'll just define the loop as always returning 0.0. In the
410 future when we have mutable variables, it will get more useful.
412 As before, lets talk about the changes that we need to Kaleidoscope to
415 Lexer Extensions for the 'for' Loop
416 -----------------------------------
418 The lexer extensions are the same sort of thing as for if/then/else:
420 .. code-block:: ocaml
422 ... in Token.token ...
427 ... in Lexer.lex_ident...
428 match Buffer.contents buffer with
429 | "def" -> [< 'Token.Def; stream >]
430 | "extern" -> [< 'Token.Extern; stream >]
431 | "if" -> [< 'Token.If; stream >]
432 | "then" -> [< 'Token.Then; stream >]
433 | "else" -> [< 'Token.Else; stream >]
434 | "for" -> [< 'Token.For; stream >]
435 | "in" -> [< 'Token.In; stream >]
436 | id -> [< 'Token.Ident id; stream >]
438 AST Extensions for the 'for' Loop
439 ---------------------------------
441 The AST variant is just as simple. It basically boils down to capturing
442 the variable name and the constituent expressions in the node.
444 .. code-block:: ocaml
448 (* variant for for/in. *)
449 | For of string * expr * expr * expr option * expr
451 Parser Extensions for the 'for' Loop
452 ------------------------------------
454 The parser code is also fairly standard. The only interesting thing here
455 is handling of the optional step value. The parser code handles it by
456 checking to see if the second comma is present. If not, it sets the step
457 value to null in the AST node:
459 .. code-block:: ocaml
461 let rec parse_primary = parser
464 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
466 'Token.Ident id ?? "expected identifier after for";
467 'Token.Kwd '=' ?? "expected '=' after for";
472 'Token.Kwd ',' ?? "expected ',' after for";
477 | [< 'Token.Kwd ','; step=parse_expr >] -> Some step
482 | [< 'Token.In; body=parse_expr >] ->
483 Ast.For (id, start, end_, step, body)
485 raise (Stream.Error "expected 'in' after for")
488 raise (Stream.Error "expected '=' after for")
491 LLVM IR for the 'for' Loop
492 --------------------------
494 Now we get to the good part: the LLVM IR we want to generate for this
495 thing. With the simple example above, we get this LLVM IR (note that
496 this dump is generated with optimizations disabled for clarity):
500 declare double @putchard(double)
502 define double @printstar(double %n) {
504 ; initial value = 1.0 (inlined into phi)
507 loop: ; preds = %loop, %entry
508 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
510 %calltmp = call double @putchard(double 4.200000e+01)
512 %nextvar = fadd double %i, 1.000000e+00
515 %cmptmp = fcmp ult double %i, %n
516 %booltmp = uitofp i1 %cmptmp to double
517 %loopcond = fcmp one double %booltmp, 0.000000e+00
518 br i1 %loopcond, label %loop, label %afterloop
520 afterloop: ; preds = %loop
521 ; loop always returns 0.0
522 ret double 0.000000e+00
525 This loop contains all the same constructs we saw before: a phi node,
526 several expressions, and some basic blocks. Lets see how this fits
529 Code Generation for the 'for' Loop
530 ----------------------------------
532 The first part of Codegen is very simple: we just output the start
533 expression for the loop value:
535 .. code-block:: ocaml
537 let rec codegen_expr = function
539 | Ast.For (var_name, start, end_, step, body) ->
540 (* Emit the start code first, without 'variable' in scope. *)
541 let start_val = codegen_expr start in
543 With this out of the way, the next step is to set up the LLVM basic
544 block for the start of the loop body. In the case above, the whole loop
545 body is one block, but remember that the body code itself could consist
546 of multiple blocks (e.g. if it contains an if/then/else or a for/in
549 .. code-block:: ocaml
551 (* Make the new basic block for the loop header, inserting after current
553 let preheader_bb = insertion_block builder in
554 let the_function = block_parent preheader_bb in
555 let loop_bb = append_block context "loop" the_function in
557 (* Insert an explicit fall through from the current block to the
559 ignore (build_br loop_bb builder);
561 This code is similar to what we saw for if/then/else. Because we will
562 need it to create the Phi node, we remember the block that falls through
563 into the loop. Once we have that, we create the actual block that starts
564 the loop and create an unconditional branch for the fall-through between
567 .. code-block:: ocaml
569 (* Start insertion in loop_bb. *)
570 position_at_end loop_bb builder;
572 (* Start the PHI node with an entry for start. *)
573 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
575 Now that the "preheader" for the loop is set up, we switch to emitting
576 code for the loop body. To begin with, we move the insertion point and
577 create the PHI node for the loop induction variable. Since we already
578 know the incoming value for the starting value, we add it to the Phi
579 node. Note that the Phi will eventually get a second value for the
580 backedge, but we can't set it up yet (because it doesn't exist!).
582 .. code-block:: ocaml
584 (* Within the loop, the variable is defined equal to the PHI node. If it
585 * shadows an existing variable, we have to restore it, so save it
588 try Some (Hashtbl.find named_values var_name) with Not_found -> None
590 Hashtbl.add named_values var_name variable;
592 (* Emit the body of the loop. This, like any other expr, can change the
593 * current BB. Note that we ignore the value computed by the body, but
594 * don't allow an error *)
595 ignore (codegen_expr body);
597 Now the code starts to get more interesting. Our 'for' loop introduces a
598 new variable to the symbol table. This means that our symbol table can
599 now contain either function arguments or loop variables. To handle this,
600 before we codegen the body of the loop, we add the loop variable as the
601 current value for its name. Note that it is possible that there is a
602 variable of the same name in the outer scope. It would be easy to make
603 this an error (emit an error and return null if there is already an
604 entry for VarName) but we choose to allow shadowing of variables. In
605 order to handle this correctly, we remember the Value that we are
606 potentially shadowing in ``old_val`` (which will be None if there is no
609 Once the loop variable is set into the symbol table, the code
610 recursively codegen's the body. This allows the body to use the loop
611 variable: any references to it will naturally find it in the symbol
614 .. code-block:: ocaml
616 (* Emit the step value. *)
619 | Some step -> codegen_expr step
620 (* If not specified, use 1.0. *)
621 | None -> const_float double_type 1.0
624 let next_var = build_add variable step_val "nextvar" builder in
626 Now that the body is emitted, we compute the next value of the iteration
627 variable by adding the step value, or 1.0 if it isn't present.
628 '``next_var``' will be the value of the loop variable on the next
629 iteration of the loop.
631 .. code-block:: ocaml
633 (* Compute the end condition. *)
634 let end_cond = codegen_expr end_ in
636 (* Convert condition to a bool by comparing equal to 0.0. *)
637 let zero = const_float double_type 0.0 in
638 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
640 Finally, we evaluate the exit value of the loop, to determine whether
641 the loop should exit. This mirrors the condition evaluation for the
642 if/then/else statement.
644 .. code-block:: ocaml
646 (* Create the "after loop" block and insert it. *)
647 let loop_end_bb = insertion_block builder in
648 let after_bb = append_block context "afterloop" the_function in
650 (* Insert the conditional branch into the end of loop_end_bb. *)
651 ignore (build_cond_br end_cond loop_bb after_bb builder);
653 (* Any new code will be inserted in after_bb. *)
654 position_at_end after_bb builder;
656 With the code for the body of the loop complete, we just need to finish
657 up the control flow for it. This code remembers the end block (for the
658 phi node), then creates the block for the loop exit ("afterloop"). Based
659 on the value of the exit condition, it creates a conditional branch that
660 chooses between executing the loop again and exiting the loop. Any
661 future code is emitted in the "afterloop" block, so it sets the
662 insertion position to it.
664 .. code-block:: ocaml
666 (* Add a new entry to the PHI node for the backedge. *)
667 add_incoming (next_var, loop_end_bb) variable;
669 (* Restore the unshadowed variable. *)
670 begin match old_val with
671 | Some old_val -> Hashtbl.add named_values var_name old_val
675 (* for expr always returns 0.0. *)
676 const_null double_type
678 The final code handles various cleanups: now that we have the
679 "``next_var``" value, we can add the incoming value to the loop PHI
680 node. After that, we remove the loop variable from the symbol table, so
681 that it isn't in scope after the for loop. Finally, code generation of
682 the for loop always returns 0.0, so that is what we return from
683 ``Codegen.codegen_expr``.
685 With this, we conclude the "adding control flow to Kaleidoscope" chapter
686 of the tutorial. In this chapter we added two control flow constructs,
687 and used them to motivate a couple of aspects of the LLVM IR that are
688 important for front-end implementors to know. In the next chapter of our
689 saga, we will get a bit crazier and add `user-defined
690 operators <OCamlLangImpl6.html>`_ to our poor innocent language.
695 Here is the complete code listing for our running example, enhanced with
696 the if/then/else and for expressions.. To build this example, use:
710 <{lexer,parser}.ml>: use_camlp4, pp(camlp4of)
711 <*.{byte,native}>: g++, use_llvm, use_llvm_analysis
712 <*.{byte,native}>: use_llvm_executionengine, use_llvm_target
713 <*.{byte,native}>: use_llvm_scalar_opts, use_bindings
716 .. code-block:: ocaml
718 open Ocamlbuild_plugin;;
720 ocaml_lib ~extern:true "llvm";;
721 ocaml_lib ~extern:true "llvm_analysis";;
722 ocaml_lib ~extern:true "llvm_executionengine";;
723 ocaml_lib ~extern:true "llvm_target";;
724 ocaml_lib ~extern:true "llvm_scalar_opts";;
726 flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
727 dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
730 .. code-block:: ocaml
732 (*===----------------------------------------------------------------------===
734 *===----------------------------------------------------------------------===*)
736 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
737 * these others for known things. *)
743 | Ident of string | Number of float
753 .. code-block:: ocaml
755 (*===----------------------------------------------------------------------===
757 *===----------------------------------------------------------------------===*)
760 (* Skip any whitespace. *)
761 | [< ' (' ' | '\n' | '\r' | '\t'); stream >] -> lex stream
763 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
764 | [< ' ('A' .. 'Z' | 'a' .. 'z' as c); stream >] ->
765 let buffer = Buffer.create 1 in
766 Buffer.add_char buffer c;
767 lex_ident buffer stream
769 (* number: [0-9.]+ *)
770 | [< ' ('0' .. '9' as c); stream >] ->
771 let buffer = Buffer.create 1 in
772 Buffer.add_char buffer c;
773 lex_number buffer stream
775 (* Comment until end of line. *)
776 | [< ' ('#'); stream >] ->
779 (* Otherwise, just return the character as its ascii value. *)
780 | [< 'c; stream >] ->
781 [< 'Token.Kwd c; lex stream >]
786 and lex_number buffer = parser
787 | [< ' ('0' .. '9' | '.' as c); stream >] ->
788 Buffer.add_char buffer c;
789 lex_number buffer stream
790 | [< stream=lex >] ->
791 [< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >]
793 and lex_ident buffer = parser
794 | [< ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream >] ->
795 Buffer.add_char buffer c;
796 lex_ident buffer stream
797 | [< stream=lex >] ->
798 match Buffer.contents buffer with
799 | "def" -> [< 'Token.Def; stream >]
800 | "extern" -> [< 'Token.Extern; stream >]
801 | "if" -> [< 'Token.If; stream >]
802 | "then" -> [< 'Token.Then; stream >]
803 | "else" -> [< 'Token.Else; stream >]
804 | "for" -> [< 'Token.For; stream >]
805 | "in" -> [< 'Token.In; stream >]
806 | id -> [< 'Token.Ident id; stream >]
808 and lex_comment = parser
809 | [< ' ('\n'); stream=lex >] -> stream
810 | [< 'c; e=lex_comment >] -> e
814 .. code-block:: ocaml
816 (*===----------------------------------------------------------------------===
817 * Abstract Syntax Tree (aka Parse Tree)
818 *===----------------------------------------------------------------------===*)
820 (* expr - Base type for all expression nodes. *)
822 (* variant for numeric literals like "1.0". *)
825 (* variant for referencing a variable, like "a". *)
828 (* variant for a binary operator. *)
829 | Binary of char * expr * expr
831 (* variant for function calls. *)
832 | Call of string * expr array
834 (* variant for if/then/else. *)
835 | If of expr * expr * expr
837 (* variant for for/in. *)
838 | For of string * expr * expr * expr option * expr
840 (* proto - This type represents the "prototype" for a function, which captures
841 * its name, and its argument names (thus implicitly the number of arguments the
842 * function takes). *)
843 type proto = Prototype of string * string array
845 (* func - This type represents a function definition itself. *)
846 type func = Function of proto * expr
849 .. code-block:: ocaml
851 (*===---------------------------------------------------------------------===
853 *===---------------------------------------------------------------------===*)
855 (* binop_precedence - This holds the precedence for each binary operator that is
857 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
859 (* precedence - Get the precedence of the pending binary operator token. *)
860 let precedence c = try Hashtbl.find binop_precedence c with Not_found -> -1
868 let rec parse_primary = parser
869 (* numberexpr ::= number *)
870 | [< 'Token.Number n >] -> Ast.Number n
872 (* parenexpr ::= '(' expression ')' *)
873 | [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
877 * ::= identifier '(' argumentexpr ')' *)
878 | [< 'Token.Ident id; stream >] ->
879 let rec parse_args accumulator = parser
880 | [< e=parse_expr; stream >] ->
882 | [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
883 | [< >] -> e :: accumulator
885 | [< >] -> accumulator
887 let rec parse_ident id = parser
891 'Token.Kwd ')' ?? "expected ')'">] ->
892 Ast.Call (id, Array.of_list (List.rev args))
894 (* Simple variable ref. *)
895 | [< >] -> Ast.Variable id
897 parse_ident id stream
899 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
900 | [< 'Token.If; c=parse_expr;
901 'Token.Then ?? "expected 'then'"; t=parse_expr;
902 'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
906 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
908 'Token.Ident id ?? "expected identifier after for";
909 'Token.Kwd '=' ?? "expected '=' after for";
914 'Token.Kwd ',' ?? "expected ',' after for";
919 | [< 'Token.Kwd ','; step=parse_expr >] -> Some step
924 | [< 'Token.In; body=parse_expr >] ->
925 Ast.For (id, start, end_, step, body)
927 raise (Stream.Error "expected 'in' after for")
930 raise (Stream.Error "expected '=' after for")
933 | [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
936 * ::= ('+' primary)* *)
937 and parse_bin_rhs expr_prec lhs stream =
938 match Stream.peek stream with
939 (* If this is a binop, find its precedence. *)
940 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
941 let token_prec = precedence c in
943 (* If this is a binop that binds at least as tightly as the current binop,
944 * consume it, otherwise we are done. *)
945 if token_prec < expr_prec then lhs else begin
949 (* Parse the primary expression after the binary operator. *)
950 let rhs = parse_primary stream in
952 (* Okay, we know this is a binop. *)
954 match Stream.peek stream with
955 | Some (Token.Kwd c2) ->
956 (* If BinOp binds less tightly with rhs than the operator after
957 * rhs, let the pending operator take rhs as its lhs. *)
958 let next_prec = precedence c2 in
959 if token_prec < next_prec
960 then parse_bin_rhs (token_prec + 1) rhs stream
966 let lhs = Ast.Binary (c, lhs, rhs) in
967 parse_bin_rhs expr_prec lhs stream
972 * ::= primary binoprhs *)
973 and parse_expr = parser
974 | [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream
977 * ::= id '(' id* ')' *)
978 let parse_prototype =
979 let rec parse_args accumulator = parser
980 | [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
981 | [< >] -> accumulator
985 | [< 'Token.Ident id;
986 'Token.Kwd '(' ?? "expected '(' in prototype";
988 'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
990 Ast.Prototype (id, Array.of_list (List.rev args))
993 raise (Stream.Error "expected function name in prototype")
995 (* definition ::= 'def' prototype expression *)
996 let parse_definition = parser
997 | [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
1000 (* toplevelexpr ::= expression *)
1001 let parse_toplevel = parser
1002 | [< e=parse_expr >] ->
1003 (* Make an anonymous proto. *)
1004 Ast.Function (Ast.Prototype ("", [||]), e)
1006 (* external ::= 'extern' prototype *)
1007 let parse_extern = parser
1008 | [< 'Token.Extern; e=parse_prototype >] -> e
1011 .. code-block:: ocaml
1013 (*===----------------------------------------------------------------------===
1015 *===----------------------------------------------------------------------===*)
1019 exception Error of string
1021 let context = global_context ()
1022 let the_module = create_module context "my cool jit"
1023 let builder = builder context
1024 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
1025 let double_type = double_type context
1027 let rec codegen_expr = function
1028 | Ast.Number n -> const_float double_type n
1029 | Ast.Variable name ->
1030 (try Hashtbl.find named_values name with
1031 | Not_found -> raise (Error "unknown variable name"))
1032 | Ast.Binary (op, lhs, rhs) ->
1033 let lhs_val = codegen_expr lhs in
1034 let rhs_val = codegen_expr rhs in
1037 | '+' -> build_add lhs_val rhs_val "addtmp" builder
1038 | '-' -> build_sub lhs_val rhs_val "subtmp" builder
1039 | '*' -> build_mul lhs_val rhs_val "multmp" builder
1041 (* Convert bool 0/1 to double 0.0 or 1.0 *)
1042 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
1043 build_uitofp i double_type "booltmp" builder
1044 | _ -> raise (Error "invalid binary operator")
1046 | Ast.Call (callee, args) ->
1047 (* Look up the name in the module table. *)
1049 match lookup_function callee the_module with
1050 | Some callee -> callee
1051 | None -> raise (Error "unknown function referenced")
1053 let params = params callee in
1055 (* If argument mismatch error. *)
1056 if Array.length params == Array.length args then () else
1057 raise (Error "incorrect # arguments passed");
1058 let args = Array.map codegen_expr args in
1059 build_call callee args "calltmp" builder
1060 | Ast.If (cond, then_, else_) ->
1061 let cond = codegen_expr cond in
1063 (* Convert condition to a bool by comparing equal to 0.0 *)
1064 let zero = const_float double_type 0.0 in
1065 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
1067 (* Grab the first block so that we might later add the conditional branch
1068 * to it at the end of the function. *)
1069 let start_bb = insertion_block builder in
1070 let the_function = block_parent start_bb in
1072 let then_bb = append_block context "then" the_function in
1074 (* Emit 'then' value. *)
1075 position_at_end then_bb builder;
1076 let then_val = codegen_expr then_ in
1078 (* Codegen of 'then' can change the current block, update then_bb for the
1079 * phi. We create a new name because one is used for the phi node, and the
1080 * other is used for the conditional branch. *)
1081 let new_then_bb = insertion_block builder in
1083 (* Emit 'else' value. *)
1084 let else_bb = append_block context "else" the_function in
1085 position_at_end else_bb builder;
1086 let else_val = codegen_expr else_ in
1088 (* Codegen of 'else' can change the current block, update else_bb for the
1090 let new_else_bb = insertion_block builder in
1092 (* Emit merge block. *)
1093 let merge_bb = append_block context "ifcont" the_function in
1094 position_at_end merge_bb builder;
1095 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
1096 let phi = build_phi incoming "iftmp" builder in
1098 (* Return to the start block to add the conditional branch. *)
1099 position_at_end start_bb builder;
1100 ignore (build_cond_br cond_val then_bb else_bb builder);
1102 (* Set a unconditional branch at the end of the 'then' block and the
1103 * 'else' block to the 'merge' block. *)
1104 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
1105 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
1107 (* Finally, set the builder to the end of the merge block. *)
1108 position_at_end merge_bb builder;
1111 | Ast.For (var_name, start, end_, step, body) ->
1112 (* Emit the start code first, without 'variable' in scope. *)
1113 let start_val = codegen_expr start in
1115 (* Make the new basic block for the loop header, inserting after current
1117 let preheader_bb = insertion_block builder in
1118 let the_function = block_parent preheader_bb in
1119 let loop_bb = append_block context "loop" the_function in
1121 (* Insert an explicit fall through from the current block to the
1123 ignore (build_br loop_bb builder);
1125 (* Start insertion in loop_bb. *)
1126 position_at_end loop_bb builder;
1128 (* Start the PHI node with an entry for start. *)
1129 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
1131 (* Within the loop, the variable is defined equal to the PHI node. If it
1132 * shadows an existing variable, we have to restore it, so save it
1135 try Some (Hashtbl.find named_values var_name) with Not_found -> None
1137 Hashtbl.add named_values var_name variable;
1139 (* Emit the body of the loop. This, like any other expr, can change the
1140 * current BB. Note that we ignore the value computed by the body, but
1141 * don't allow an error *)
1142 ignore (codegen_expr body);
1144 (* Emit the step value. *)
1147 | Some step -> codegen_expr step
1148 (* If not specified, use 1.0. *)
1149 | None -> const_float double_type 1.0
1152 let next_var = build_add variable step_val "nextvar" builder in
1154 (* Compute the end condition. *)
1155 let end_cond = codegen_expr end_ in
1157 (* Convert condition to a bool by comparing equal to 0.0. *)
1158 let zero = const_float double_type 0.0 in
1159 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
1161 (* Create the "after loop" block and insert it. *)
1162 let loop_end_bb = insertion_block builder in
1163 let after_bb = append_block context "afterloop" the_function in
1165 (* Insert the conditional branch into the end of loop_end_bb. *)
1166 ignore (build_cond_br end_cond loop_bb after_bb builder);
1168 (* Any new code will be inserted in after_bb. *)
1169 position_at_end after_bb builder;
1171 (* Add a new entry to the PHI node for the backedge. *)
1172 add_incoming (next_var, loop_end_bb) variable;
1174 (* Restore the unshadowed variable. *)
1175 begin match old_val with
1176 | Some old_val -> Hashtbl.add named_values var_name old_val
1180 (* for expr always returns 0.0. *)
1181 const_null double_type
1183 let codegen_proto = function
1184 | Ast.Prototype (name, args) ->
1185 (* Make the function type: double(double,double) etc. *)
1186 let doubles = Array.make (Array.length args) double_type in
1187 let ft = function_type double_type doubles in
1189 match lookup_function name the_module with
1190 | None -> declare_function name ft the_module
1192 (* If 'f' conflicted, there was already something named 'name'. If it
1193 * has a body, don't allow redefinition or reextern. *)
1195 (* If 'f' already has a body, reject this. *)
1196 if block_begin f <> At_end f then
1197 raise (Error "redefinition of function");
1199 (* If 'f' took a different number of arguments, reject. *)
1200 if element_type (type_of f) <> ft then
1201 raise (Error "redefinition of function with different # args");
1205 (* Set names for all arguments. *)
1206 Array.iteri (fun i a ->
1209 Hashtbl.add named_values n a;
1213 let codegen_func the_fpm = function
1214 | Ast.Function (proto, body) ->
1215 Hashtbl.clear named_values;
1216 let the_function = codegen_proto proto in
1218 (* Create a new basic block to start insertion into. *)
1219 let bb = append_block context "entry" the_function in
1220 position_at_end bb builder;
1223 let ret_val = codegen_expr body in
1225 (* Finish off the function. *)
1226 let _ = build_ret ret_val builder in
1228 (* Validate the generated code, checking for consistency. *)
1229 Llvm_analysis.assert_valid_function the_function;
1231 (* Optimize the function. *)
1232 let _ = PassManager.run_function the_function the_fpm in
1236 delete_function the_function;
1240 .. code-block:: ocaml
1242 (*===----------------------------------------------------------------------===
1243 * Top-Level parsing and JIT Driver
1244 *===----------------------------------------------------------------------===*)
1247 open Llvm_executionengine
1249 (* top ::= definition | external | expression | ';' *)
1250 let rec main_loop the_fpm the_execution_engine stream =
1251 match Stream.peek stream with
1254 (* ignore top-level semicolons. *)
1255 | Some (Token.Kwd ';') ->
1257 main_loop the_fpm the_execution_engine stream
1261 try match token with
1263 let e = Parser.parse_definition stream in
1264 print_endline "parsed a function definition.";
1265 dump_value (Codegen.codegen_func the_fpm e);
1267 let e = Parser.parse_extern stream in
1268 print_endline "parsed an extern.";
1269 dump_value (Codegen.codegen_proto e);
1271 (* Evaluate a top-level expression into an anonymous function. *)
1272 let e = Parser.parse_toplevel stream in
1273 print_endline "parsed a top-level expr";
1274 let the_function = Codegen.codegen_func the_fpm e in
1275 dump_value the_function;
1277 (* JIT the function, returning a function pointer. *)
1278 let result = ExecutionEngine.run_function the_function [||]
1279 the_execution_engine in
1281 print_string "Evaluated to ";
1282 print_float (GenericValue.as_float Codegen.double_type result);
1284 with Stream.Error s | Codegen.Error s ->
1285 (* Skip token for error recovery. *)
1289 print_string "ready> "; flush stdout;
1290 main_loop the_fpm the_execution_engine stream
1293 .. code-block:: ocaml
1295 (*===----------------------------------------------------------------------===
1297 *===----------------------------------------------------------------------===*)
1300 open Llvm_executionengine
1302 open Llvm_scalar_opts
1305 ignore (initialize_native_target ());
1307 (* Install standard binary operators.
1308 * 1 is the lowest precedence. *)
1309 Hashtbl.add Parser.binop_precedence '<' 10;
1310 Hashtbl.add Parser.binop_precedence '+' 20;
1311 Hashtbl.add Parser.binop_precedence '-' 20;
1312 Hashtbl.add Parser.binop_precedence '*' 40; (* highest. *)
1314 (* Prime the first token. *)
1315 print_string "ready> "; flush stdout;
1316 let stream = Lexer.lex (Stream.of_channel stdin) in
1318 (* Create the JIT. *)
1319 let the_execution_engine = ExecutionEngine.create Codegen.the_module in
1320 let the_fpm = PassManager.create_function Codegen.the_module in
1322 (* Set up the optimizer pipeline. Start with registering info about how the
1323 * target lays out data structures. *)
1324 DataLayout.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
1326 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
1327 add_instruction_combination the_fpm;
1329 (* reassociate expressions. *)
1330 add_reassociation the_fpm;
1332 (* Eliminate Common SubExpressions. *)
1335 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
1336 add_cfg_simplification the_fpm;
1338 ignore (PassManager.initialize the_fpm);
1340 (* Run the main "interpreter loop" now. *)
1341 Toplevel.main_loop the_fpm the_execution_engine stream;
1343 (* Print out all the generated code. *)
1344 dump_module Codegen.the_module
1354 /* putchard - putchar that takes a double and returns 0. */
1355 extern double putchard(double X) {
1360 `Next: Extending the language: user-defined
1361 operators <OCamlLangImpl6.html>`_