1 ==================================================
2 Kaleidoscope: Extending the Language: Control Flow
3 ==================================================
8 Written by `Chris Lattner <mailto:sabre@nondot.org>`_ and `Erick
9 Tryzelaar <mailto:idadesub@users.sourceforge.net>`_
11 Chapter 5 Introduction
12 ======================
14 Welcome to Chapter 5 of the "`Implementing a language with
15 LLVM <index.html>`_" tutorial. Parts 1-4 described the implementation of
16 the simple Kaleidoscope language and included support for generating
17 LLVM IR, followed by optimizations and a JIT compiler. Unfortunately, as
18 presented, Kaleidoscope is mostly useless: it has no control flow other
19 than call and return. This means that you can't have conditional
20 branches in the code, significantly limiting its power. In this episode
21 of "build that compiler", we'll extend Kaleidoscope to have an
22 if/then/else expression plus a simple 'for' loop.
27 Extending Kaleidoscope to support if/then/else is quite straightforward.
28 It basically requires adding lexer support for this "new" concept to the
29 lexer, parser, AST, and LLVM code emitter. This example is nice, because
30 it shows how easy it is to "grow" a language over time, incrementally
31 extending it as new ideas are discovered.
33 Before we get going on "how" we add this extension, lets talk about
34 "what" we want. The basic idea is that we want to be able to write this
45 In Kaleidoscope, every construct is an expression: there are no
46 statements. As such, the if/then/else expression needs to return a value
47 like any other. Since we're using a mostly functional form, we'll have
48 it evaluate its conditional, then return the 'then' or 'else' value
49 based on how the condition was resolved. This is very similar to the C
52 The semantics of the if/then/else expression is that it evaluates the
53 condition to a boolean equality value: 0.0 is considered to be false and
54 everything else is considered to be true. If the condition is true, the
55 first subexpression is evaluated and returned, if the condition is
56 false, the second subexpression is evaluated and returned. Since
57 Kaleidoscope allows side-effects, this behavior is important to nail
60 Now that we know what we "want", lets break this down into its
63 Lexer Extensions for If/Then/Else
64 ---------------------------------
66 The lexer extensions are straightforward. First we add new variants for
72 | If | Then | Else | For | In
74 Once we have that, we recognize the new keywords in the lexer. This is
80 match Buffer.contents buffer with
81 | "def" -> [< 'Token.Def; stream >]
82 | "extern" -> [< 'Token.Extern; stream >]
83 | "if" -> [< 'Token.If; stream >]
84 | "then" -> [< 'Token.Then; stream >]
85 | "else" -> [< 'Token.Else; stream >]
86 | "for" -> [< 'Token.For; stream >]
87 | "in" -> [< 'Token.In; stream >]
88 | id -> [< 'Token.Ident id; stream >]
90 AST Extensions for If/Then/Else
91 -------------------------------
93 To represent the new expression we add a new AST variant for it:
99 (* variant for if/then/else. *)
100 | If of expr * expr * expr
102 The AST variant just has pointers to the various subexpressions.
104 Parser Extensions for If/Then/Else
105 ----------------------------------
107 Now that we have the relevant tokens coming from the lexer and we have
108 the AST node to build, our parsing logic is relatively straightforward.
109 First we define a new parsing function:
111 .. code-block:: ocaml
113 let rec parse_primary = parser
115 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
116 | [< 'Token.If; c=parse_expr;
117 'Token.Then ?? "expected 'then'"; t=parse_expr;
118 'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
121 Next we hook it up as a primary expression:
123 .. code-block:: ocaml
125 let rec parse_primary = parser
127 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
128 | [< 'Token.If; c=parse_expr;
129 'Token.Then ?? "expected 'then'"; t=parse_expr;
130 'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
133 LLVM IR for If/Then/Else
134 ------------------------
136 Now that we have it parsing and building the AST, the final piece is
137 adding LLVM code generation support. This is the most interesting part
138 of the if/then/else example, because this is where it starts to
139 introduce new concepts. All of the code above has been thoroughly
140 described in previous chapters.
142 To motivate the code we want to produce, lets take a look at a simple
149 def baz(x) if x then foo() else bar();
151 If you disable optimizations, the code you'll (soon) get from
152 Kaleidoscope looks like this:
156 declare double @foo()
158 declare double @bar()
160 define double @baz(double %x) {
162 %ifcond = fcmp one double %x, 0.000000e+00
163 br i1 %ifcond, label %then, label %else
165 then: ; preds = %entry
166 %calltmp = call double @foo()
169 else: ; preds = %entry
170 %calltmp1 = call double @bar()
173 ifcont: ; preds = %else, %then
174 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
178 To visualize the control flow graph, you can use a nifty feature of the
179 LLVM '`opt <http://llvm.org/cmds/opt.html>`_' tool. If you put this LLVM
180 IR into "t.ll" and run "``llvm-as < t.ll | opt -analyze -view-cfg``", `a
181 window will pop up <../ProgrammersManual.html#ViewGraph>`_ and you'll
184 .. figure:: LangImpl5-cfg.png
190 Another way to get this is to call
191 "``Llvm_analysis.view_function_cfg f``" or
192 "``Llvm_analysis.view_function_cfg_only f``" (where ``f`` is a
193 "``Function``") either by inserting actual calls into the code and
194 recompiling or by calling these in the debugger. LLVM has many nice
195 features for visualizing various graphs.
197 Getting back to the generated code, it is fairly simple: the entry block
198 evaluates the conditional expression ("x" in our case here) and compares
199 the result to 0.0 with the "``fcmp one``" instruction ('one' is "Ordered
200 and Not Equal"). Based on the result of this expression, the code jumps
201 to either the "then" or "else" blocks, which contain the expressions for
202 the true/false cases.
204 Once the then/else blocks are finished executing, they both branch back
205 to the 'ifcont' block to execute the code that happens after the
206 if/then/else. In this case the only thing left to do is to return to the
207 caller of the function. The question then becomes: how does the code
208 know which expression to return?
210 The answer to this question involves an important SSA operation: the
212 operation <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_.
213 If you're not familiar with SSA, `the wikipedia
214 article <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_
215 is a good introduction and there are various other introductions to it
216 available on your favorite search engine. The short version is that
217 "execution" of the Phi operation requires "remembering" which block
218 control came from. The Phi operation takes on the value corresponding to
219 the input control block. In this case, if control comes in from the
220 "then" block, it gets the value of "calltmp". If control comes from the
221 "else" block, it gets the value of "calltmp1".
223 At this point, you are probably starting to think "Oh no! This means my
224 simple and elegant front-end will have to start generating SSA form in
225 order to use LLVM!". Fortunately, this is not the case, and we strongly
226 advise *not* implementing an SSA construction algorithm in your
227 front-end unless there is an amazingly good reason to do so. In
228 practice, there are two sorts of values that float around in code
229 written for your average imperative programming language that might need
232 #. Code that involves user variables: ``x = 1; x = x + 1;``
233 #. Values that are implicit in the structure of your AST, such as the
234 Phi node in this case.
236 In `Chapter 7 <OCamlLangImpl7.html>`_ of this tutorial ("mutable
237 variables"), we'll talk about #1 in depth. For now, just believe me that
238 you don't need SSA construction to handle this case. For #2, you have
239 the choice of using the techniques that we will describe for #1, or you
240 can insert Phi nodes directly, if convenient. In this case, it is really
241 really easy to generate the Phi node, so we choose to do it directly.
243 Okay, enough of the motivation and overview, lets generate code!
245 Code Generation for If/Then/Else
246 --------------------------------
248 In order to generate code for this, we implement the ``Codegen`` method
251 .. code-block:: ocaml
253 let rec codegen_expr = function
255 | Ast.If (cond, then_, else_) ->
256 let cond = codegen_expr cond in
258 (* Convert condition to a bool by comparing equal to 0.0 *)
259 let zero = const_float double_type 0.0 in
260 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
262 This code is straightforward and similar to what we saw before. We emit
263 the expression for the condition, then compare that value to zero to get
264 a truth value as a 1-bit (bool) value.
266 .. code-block:: ocaml
268 (* Grab the first block so that we might later add the conditional branch
269 * to it at the end of the function. *)
270 let start_bb = insertion_block builder in
271 let the_function = block_parent start_bb in
273 let then_bb = append_block context "then" the_function in
274 position_at_end then_bb builder;
276 As opposed to the `C++ tutorial <LangImpl5.html>`_, we have to build our
277 basic blocks bottom up since we can't have dangling BasicBlocks. We
278 start off by saving a pointer to the first block (which might not be the
279 entry block), which we'll need to build a conditional branch later. We
280 do this by asking the ``builder`` for the current BasicBlock. The fourth
281 line gets the current Function object that is being built. It gets this
282 by the ``start_bb`` for its "parent" (the function it is currently
285 Once it has that, it creates one block. It is automatically appended
286 into the function's list of blocks.
288 .. code-block:: ocaml
290 (* Emit 'then' value. *)
291 position_at_end then_bb builder;
292 let then_val = codegen_expr then_ in
294 (* Codegen of 'then' can change the current block, update then_bb for the
295 * phi. We create a new name because one is used for the phi node, and the
296 * other is used for the conditional branch. *)
297 let new_then_bb = insertion_block builder in
299 We move the builder to start inserting into the "then" block. Strictly
300 speaking, this call moves the insertion point to be at the end of the
301 specified block. However, since the "then" block is empty, it also
302 starts out by inserting at the beginning of the block. :)
304 Once the insertion point is set, we recursively codegen the "then"
305 expression from the AST.
307 The final line here is quite subtle, but is very important. The basic
308 issue is that when we create the Phi node in the merge block, we need to
309 set up the block/value pairs that indicate how the Phi will work.
310 Importantly, the Phi node expects to have an entry for each predecessor
311 of the block in the CFG. Why then, are we getting the current block when
312 we just set it to ThenBB 5 lines above? The problem is that the "Then"
313 expression may actually itself change the block that the Builder is
314 emitting into if, for example, it contains a nested "if/then/else"
315 expression. Because calling Codegen recursively could arbitrarily change
316 the notion of the current block, we are required to get an up-to-date
317 value for code that will set up the Phi node.
319 .. code-block:: ocaml
321 (* Emit 'else' value. *)
322 let else_bb = append_block context "else" the_function in
323 position_at_end else_bb builder;
324 let else_val = codegen_expr else_ in
326 (* Codegen of 'else' can change the current block, update else_bb for the
328 let new_else_bb = insertion_block builder in
330 Code generation for the 'else' block is basically identical to codegen
331 for the 'then' block.
333 .. code-block:: ocaml
335 (* Emit merge block. *)
336 let merge_bb = append_block context "ifcont" the_function in
337 position_at_end merge_bb builder;
338 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
339 let phi = build_phi incoming "iftmp" builder in
341 The first two lines here are now familiar: the first adds the "merge"
342 block to the Function object. The second block changes the insertion
343 point so that newly created code will go into the "merge" block. Once
344 that is done, we need to create the PHI node and set up the block/value
347 .. code-block:: ocaml
349 (* Return to the start block to add the conditional branch. *)
350 position_at_end start_bb builder;
351 ignore (build_cond_br cond_val then_bb else_bb builder);
353 Once the blocks are created, we can emit the conditional branch that
354 chooses between them. Note that creating new blocks does not implicitly
355 affect the IRBuilder, so it is still inserting into the block that the
356 condition went into. This is why we needed to save the "start" block.
358 .. code-block:: ocaml
360 (* Set a unconditional branch at the end of the 'then' block and the
361 * 'else' block to the 'merge' block. *)
362 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
363 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
365 (* Finally, set the builder to the end of the merge block. *)
366 position_at_end merge_bb builder;
370 To finish off the blocks, we create an unconditional branch to the merge
371 block. One interesting (and very important) aspect of the LLVM IR is
372 that it `requires all basic blocks to be
373 "terminated" <../LangRef.html#functionstructure>`_ with a `control flow
374 instruction <../LangRef.html#terminators>`_ such as return or branch.
375 This means that all control flow, *including fall throughs* must be made
376 explicit in the LLVM IR. If you violate this rule, the verifier will
379 Finally, the CodeGen function returns the phi node as the value computed
380 by the if/then/else expression. In our example above, this returned
381 value will feed into the code for the top-level function, which will
382 create the return instruction.
384 Overall, we now have the ability to execute conditional code in
385 Kaleidoscope. With this extension, Kaleidoscope is a fairly complete
386 language that can calculate a wide variety of numeric functions. Next up
387 we'll add another useful expression that is familiar from non-functional
390 'for' Loop Expression
391 =====================
393 Now that we know how to add basic control flow constructs to the
394 language, we have the tools to add more powerful things. Lets add
395 something more aggressive, a 'for' expression:
399 extern putchard(char);
401 for i = 1, i < n, 1.0 in
402 putchard(42); # ascii 42 = '*'
404 # print 100 '*' characters
407 This expression defines a new variable ("i" in this case) which iterates
408 from a starting value, while the condition ("i < n" in this case) is
409 true, incrementing by an optional step value ("1.0" in this case). If
410 the step value is omitted, it defaults to 1.0. While the loop is true,
411 it executes its body expression. Because we don't have anything better
412 to return, we'll just define the loop as always returning 0.0. In the
413 future when we have mutable variables, it will get more useful.
415 As before, lets talk about the changes that we need to Kaleidoscope to
418 Lexer Extensions for the 'for' Loop
419 -----------------------------------
421 The lexer extensions are the same sort of thing as for if/then/else:
423 .. code-block:: ocaml
425 ... in Token.token ...
430 ... in Lexer.lex_ident...
431 match Buffer.contents buffer with
432 | "def" -> [< 'Token.Def; stream >]
433 | "extern" -> [< 'Token.Extern; stream >]
434 | "if" -> [< 'Token.If; stream >]
435 | "then" -> [< 'Token.Then; stream >]
436 | "else" -> [< 'Token.Else; stream >]
437 | "for" -> [< 'Token.For; stream >]
438 | "in" -> [< 'Token.In; stream >]
439 | id -> [< 'Token.Ident id; stream >]
441 AST Extensions for the 'for' Loop
442 ---------------------------------
444 The AST variant is just as simple. It basically boils down to capturing
445 the variable name and the constituent expressions in the node.
447 .. code-block:: ocaml
451 (* variant for for/in. *)
452 | For of string * expr * expr * expr option * expr
454 Parser Extensions for the 'for' Loop
455 ------------------------------------
457 The parser code is also fairly standard. The only interesting thing here
458 is handling of the optional step value. The parser code handles it by
459 checking to see if the second comma is present. If not, it sets the step
460 value to null in the AST node:
462 .. code-block:: ocaml
464 let rec parse_primary = parser
467 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
469 'Token.Ident id ?? "expected identifier after for";
470 'Token.Kwd '=' ?? "expected '=' after for";
475 'Token.Kwd ',' ?? "expected ',' after for";
480 | [< 'Token.Kwd ','; step=parse_expr >] -> Some step
485 | [< 'Token.In; body=parse_expr >] ->
486 Ast.For (id, start, end_, step, body)
488 raise (Stream.Error "expected 'in' after for")
491 raise (Stream.Error "expected '=' after for")
494 LLVM IR for the 'for' Loop
495 --------------------------
497 Now we get to the good part: the LLVM IR we want to generate for this
498 thing. With the simple example above, we get this LLVM IR (note that
499 this dump is generated with optimizations disabled for clarity):
503 declare double @putchard(double)
505 define double @printstar(double %n) {
507 ; initial value = 1.0 (inlined into phi)
510 loop: ; preds = %loop, %entry
511 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
513 %calltmp = call double @putchard(double 4.200000e+01)
515 %nextvar = fadd double %i, 1.000000e+00
518 %cmptmp = fcmp ult double %i, %n
519 %booltmp = uitofp i1 %cmptmp to double
520 %loopcond = fcmp one double %booltmp, 0.000000e+00
521 br i1 %loopcond, label %loop, label %afterloop
523 afterloop: ; preds = %loop
524 ; loop always returns 0.0
525 ret double 0.000000e+00
528 This loop contains all the same constructs we saw before: a phi node,
529 several expressions, and some basic blocks. Lets see how this fits
532 Code Generation for the 'for' Loop
533 ----------------------------------
535 The first part of Codegen is very simple: we just output the start
536 expression for the loop value:
538 .. code-block:: ocaml
540 let rec codegen_expr = function
542 | Ast.For (var_name, start, end_, step, body) ->
543 (* Emit the start code first, without 'variable' in scope. *)
544 let start_val = codegen_expr start in
546 With this out of the way, the next step is to set up the LLVM basic
547 block for the start of the loop body. In the case above, the whole loop
548 body is one block, but remember that the body code itself could consist
549 of multiple blocks (e.g. if it contains an if/then/else or a for/in
552 .. code-block:: ocaml
554 (* Make the new basic block for the loop header, inserting after current
556 let preheader_bb = insertion_block builder in
557 let the_function = block_parent preheader_bb in
558 let loop_bb = append_block context "loop" the_function in
560 (* Insert an explicit fall through from the current block to the
562 ignore (build_br loop_bb builder);
564 This code is similar to what we saw for if/then/else. Because we will
565 need it to create the Phi node, we remember the block that falls through
566 into the loop. Once we have that, we create the actual block that starts
567 the loop and create an unconditional branch for the fall-through between
570 .. code-block:: ocaml
572 (* Start insertion in loop_bb. *)
573 position_at_end loop_bb builder;
575 (* Start the PHI node with an entry for start. *)
576 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
578 Now that the "preheader" for the loop is set up, we switch to emitting
579 code for the loop body. To begin with, we move the insertion point and
580 create the PHI node for the loop induction variable. Since we already
581 know the incoming value for the starting value, we add it to the Phi
582 node. Note that the Phi will eventually get a second value for the
583 backedge, but we can't set it up yet (because it doesn't exist!).
585 .. code-block:: ocaml
587 (* Within the loop, the variable is defined equal to the PHI node. If it
588 * shadows an existing variable, we have to restore it, so save it
591 try Some (Hashtbl.find named_values var_name) with Not_found -> None
593 Hashtbl.add named_values var_name variable;
595 (* Emit the body of the loop. This, like any other expr, can change the
596 * current BB. Note that we ignore the value computed by the body, but
597 * don't allow an error *)
598 ignore (codegen_expr body);
600 Now the code starts to get more interesting. Our 'for' loop introduces a
601 new variable to the symbol table. This means that our symbol table can
602 now contain either function arguments or loop variables. To handle this,
603 before we codegen the body of the loop, we add the loop variable as the
604 current value for its name. Note that it is possible that there is a
605 variable of the same name in the outer scope. It would be easy to make
606 this an error (emit an error and return null if there is already an
607 entry for VarName) but we choose to allow shadowing of variables. In
608 order to handle this correctly, we remember the Value that we are
609 potentially shadowing in ``old_val`` (which will be None if there is no
612 Once the loop variable is set into the symbol table, the code
613 recursively codegen's the body. This allows the body to use the loop
614 variable: any references to it will naturally find it in the symbol
617 .. code-block:: ocaml
619 (* Emit the step value. *)
622 | Some step -> codegen_expr step
623 (* If not specified, use 1.0. *)
624 | None -> const_float double_type 1.0
627 let next_var = build_add variable step_val "nextvar" builder in
629 Now that the body is emitted, we compute the next value of the iteration
630 variable by adding the step value, or 1.0 if it isn't present.
631 '``next_var``' will be the value of the loop variable on the next
632 iteration of the loop.
634 .. code-block:: ocaml
636 (* Compute the end condition. *)
637 let end_cond = codegen_expr end_ in
639 (* Convert condition to a bool by comparing equal to 0.0. *)
640 let zero = const_float double_type 0.0 in
641 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
643 Finally, we evaluate the exit value of the loop, to determine whether
644 the loop should exit. This mirrors the condition evaluation for the
645 if/then/else statement.
647 .. code-block:: ocaml
649 (* Create the "after loop" block and insert it. *)
650 let loop_end_bb = insertion_block builder in
651 let after_bb = append_block context "afterloop" the_function in
653 (* Insert the conditional branch into the end of loop_end_bb. *)
654 ignore (build_cond_br end_cond loop_bb after_bb builder);
656 (* Any new code will be inserted in after_bb. *)
657 position_at_end after_bb builder;
659 With the code for the body of the loop complete, we just need to finish
660 up the control flow for it. This code remembers the end block (for the
661 phi node), then creates the block for the loop exit ("afterloop"). Based
662 on the value of the exit condition, it creates a conditional branch that
663 chooses between executing the loop again and exiting the loop. Any
664 future code is emitted in the "afterloop" block, so it sets the
665 insertion position to it.
667 .. code-block:: ocaml
669 (* Add a new entry to the PHI node for the backedge. *)
670 add_incoming (next_var, loop_end_bb) variable;
672 (* Restore the unshadowed variable. *)
673 begin match old_val with
674 | Some old_val -> Hashtbl.add named_values var_name old_val
678 (* for expr always returns 0.0. *)
679 const_null double_type
681 The final code handles various cleanups: now that we have the
682 "``next_var``" value, we can add the incoming value to the loop PHI
683 node. After that, we remove the loop variable from the symbol table, so
684 that it isn't in scope after the for loop. Finally, code generation of
685 the for loop always returns 0.0, so that is what we return from
686 ``Codegen.codegen_expr``.
688 With this, we conclude the "adding control flow to Kaleidoscope" chapter
689 of the tutorial. In this chapter we added two control flow constructs,
690 and used them to motivate a couple of aspects of the LLVM IR that are
691 important for front-end implementors to know. In the next chapter of our
692 saga, we will get a bit crazier and add `user-defined
693 operators <OCamlLangImpl6.html>`_ to our poor innocent language.
698 Here is the complete code listing for our running example, enhanced with
699 the if/then/else and for expressions.. To build this example, use:
713 <{lexer,parser}.ml>: use_camlp4, pp(camlp4of)
714 <*.{byte,native}>: g++, use_llvm, use_llvm_analysis
715 <*.{byte,native}>: use_llvm_executionengine, use_llvm_target
716 <*.{byte,native}>: use_llvm_scalar_opts, use_bindings
719 .. code-block:: ocaml
721 open Ocamlbuild_plugin;;
723 ocaml_lib ~extern:true "llvm";;
724 ocaml_lib ~extern:true "llvm_analysis";;
725 ocaml_lib ~extern:true "llvm_executionengine";;
726 ocaml_lib ~extern:true "llvm_target";;
727 ocaml_lib ~extern:true "llvm_scalar_opts";;
729 flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
730 dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
733 .. code-block:: ocaml
735 (*===----------------------------------------------------------------------===
737 *===----------------------------------------------------------------------===*)
739 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
740 * these others for known things. *)
746 | Ident of string | Number of float
756 .. code-block:: ocaml
758 (*===----------------------------------------------------------------------===
760 *===----------------------------------------------------------------------===*)
763 (* Skip any whitespace. *)
764 | [< ' (' ' | '\n' | '\r' | '\t'); stream >] -> lex stream
766 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
767 | [< ' ('A' .. 'Z' | 'a' .. 'z' as c); stream >] ->
768 let buffer = Buffer.create 1 in
769 Buffer.add_char buffer c;
770 lex_ident buffer stream
772 (* number: [0-9.]+ *)
773 | [< ' ('0' .. '9' as c); stream >] ->
774 let buffer = Buffer.create 1 in
775 Buffer.add_char buffer c;
776 lex_number buffer stream
778 (* Comment until end of line. *)
779 | [< ' ('#'); stream >] ->
782 (* Otherwise, just return the character as its ascii value. *)
783 | [< 'c; stream >] ->
784 [< 'Token.Kwd c; lex stream >]
789 and lex_number buffer = parser
790 | [< ' ('0' .. '9' | '.' as c); stream >] ->
791 Buffer.add_char buffer c;
792 lex_number buffer stream
793 | [< stream=lex >] ->
794 [< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >]
796 and lex_ident buffer = parser
797 | [< ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream >] ->
798 Buffer.add_char buffer c;
799 lex_ident buffer stream
800 | [< stream=lex >] ->
801 match Buffer.contents buffer with
802 | "def" -> [< 'Token.Def; stream >]
803 | "extern" -> [< 'Token.Extern; stream >]
804 | "if" -> [< 'Token.If; stream >]
805 | "then" -> [< 'Token.Then; stream >]
806 | "else" -> [< 'Token.Else; stream >]
807 | "for" -> [< 'Token.For; stream >]
808 | "in" -> [< 'Token.In; stream >]
809 | id -> [< 'Token.Ident id; stream >]
811 and lex_comment = parser
812 | [< ' ('\n'); stream=lex >] -> stream
813 | [< 'c; e=lex_comment >] -> e
817 .. code-block:: ocaml
819 (*===----------------------------------------------------------------------===
820 * Abstract Syntax Tree (aka Parse Tree)
821 *===----------------------------------------------------------------------===*)
823 (* expr - Base type for all expression nodes. *)
825 (* variant for numeric literals like "1.0". *)
828 (* variant for referencing a variable, like "a". *)
831 (* variant for a binary operator. *)
832 | Binary of char * expr * expr
834 (* variant for function calls. *)
835 | Call of string * expr array
837 (* variant for if/then/else. *)
838 | If of expr * expr * expr
840 (* variant for for/in. *)
841 | For of string * expr * expr * expr option * expr
843 (* proto - This type represents the "prototype" for a function, which captures
844 * its name, and its argument names (thus implicitly the number of arguments the
845 * function takes). *)
846 type proto = Prototype of string * string array
848 (* func - This type represents a function definition itself. *)
849 type func = Function of proto * expr
852 .. code-block:: ocaml
854 (*===---------------------------------------------------------------------===
856 *===---------------------------------------------------------------------===*)
858 (* binop_precedence - This holds the precedence for each binary operator that is
860 let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
862 (* precedence - Get the precedence of the pending binary operator token. *)
863 let precedence c = try Hashtbl.find binop_precedence c with Not_found -> -1
871 let rec parse_primary = parser
872 (* numberexpr ::= number *)
873 | [< 'Token.Number n >] -> Ast.Number n
875 (* parenexpr ::= '(' expression ')' *)
876 | [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
880 * ::= identifier '(' argumentexpr ')' *)
881 | [< 'Token.Ident id; stream >] ->
882 let rec parse_args accumulator = parser
883 | [< e=parse_expr; stream >] ->
885 | [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
886 | [< >] -> e :: accumulator
888 | [< >] -> accumulator
890 let rec parse_ident id = parser
894 'Token.Kwd ')' ?? "expected ')'">] ->
895 Ast.Call (id, Array.of_list (List.rev args))
897 (* Simple variable ref. *)
898 | [< >] -> Ast.Variable id
900 parse_ident id stream
902 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
903 | [< 'Token.If; c=parse_expr;
904 'Token.Then ?? "expected 'then'"; t=parse_expr;
905 'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
909 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
911 'Token.Ident id ?? "expected identifier after for";
912 'Token.Kwd '=' ?? "expected '=' after for";
917 'Token.Kwd ',' ?? "expected ',' after for";
922 | [< 'Token.Kwd ','; step=parse_expr >] -> Some step
927 | [< 'Token.In; body=parse_expr >] ->
928 Ast.For (id, start, end_, step, body)
930 raise (Stream.Error "expected 'in' after for")
933 raise (Stream.Error "expected '=' after for")
936 | [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
939 * ::= ('+' primary)* *)
940 and parse_bin_rhs expr_prec lhs stream =
941 match Stream.peek stream with
942 (* If this is a binop, find its precedence. *)
943 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
944 let token_prec = precedence c in
946 (* If this is a binop that binds at least as tightly as the current binop,
947 * consume it, otherwise we are done. *)
948 if token_prec < expr_prec then lhs else begin
952 (* Parse the primary expression after the binary operator. *)
953 let rhs = parse_primary stream in
955 (* Okay, we know this is a binop. *)
957 match Stream.peek stream with
958 | Some (Token.Kwd c2) ->
959 (* If BinOp binds less tightly with rhs than the operator after
960 * rhs, let the pending operator take rhs as its lhs. *)
961 let next_prec = precedence c2 in
962 if token_prec < next_prec
963 then parse_bin_rhs (token_prec + 1) rhs stream
969 let lhs = Ast.Binary (c, lhs, rhs) in
970 parse_bin_rhs expr_prec lhs stream
975 * ::= primary binoprhs *)
976 and parse_expr = parser
977 | [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream
980 * ::= id '(' id* ')' *)
981 let parse_prototype =
982 let rec parse_args accumulator = parser
983 | [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
984 | [< >] -> accumulator
988 | [< 'Token.Ident id;
989 'Token.Kwd '(' ?? "expected '(' in prototype";
991 'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
993 Ast.Prototype (id, Array.of_list (List.rev args))
996 raise (Stream.Error "expected function name in prototype")
998 (* definition ::= 'def' prototype expression *)
999 let parse_definition = parser
1000 | [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
1003 (* toplevelexpr ::= expression *)
1004 let parse_toplevel = parser
1005 | [< e=parse_expr >] ->
1006 (* Make an anonymous proto. *)
1007 Ast.Function (Ast.Prototype ("", [||]), e)
1009 (* external ::= 'extern' prototype *)
1010 let parse_extern = parser
1011 | [< 'Token.Extern; e=parse_prototype >] -> e
1014 .. code-block:: ocaml
1016 (*===----------------------------------------------------------------------===
1018 *===----------------------------------------------------------------------===*)
1022 exception Error of string
1024 let context = global_context ()
1025 let the_module = create_module context "my cool jit"
1026 let builder = builder context
1027 let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
1028 let double_type = double_type context
1030 let rec codegen_expr = function
1031 | Ast.Number n -> const_float double_type n
1032 | Ast.Variable name ->
1033 (try Hashtbl.find named_values name with
1034 | Not_found -> raise (Error "unknown variable name"))
1035 | Ast.Binary (op, lhs, rhs) ->
1036 let lhs_val = codegen_expr lhs in
1037 let rhs_val = codegen_expr rhs in
1040 | '+' -> build_add lhs_val rhs_val "addtmp" builder
1041 | '-' -> build_sub lhs_val rhs_val "subtmp" builder
1042 | '*' -> build_mul lhs_val rhs_val "multmp" builder
1044 (* Convert bool 0/1 to double 0.0 or 1.0 *)
1045 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
1046 build_uitofp i double_type "booltmp" builder
1047 | _ -> raise (Error "invalid binary operator")
1049 | Ast.Call (callee, args) ->
1050 (* Look up the name in the module table. *)
1052 match lookup_function callee the_module with
1053 | Some callee -> callee
1054 | None -> raise (Error "unknown function referenced")
1056 let params = params callee in
1058 (* If argument mismatch error. *)
1059 if Array.length params == Array.length args then () else
1060 raise (Error "incorrect # arguments passed");
1061 let args = Array.map codegen_expr args in
1062 build_call callee args "calltmp" builder
1063 | Ast.If (cond, then_, else_) ->
1064 let cond = codegen_expr cond in
1066 (* Convert condition to a bool by comparing equal to 0.0 *)
1067 let zero = const_float double_type 0.0 in
1068 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
1070 (* Grab the first block so that we might later add the conditional branch
1071 * to it at the end of the function. *)
1072 let start_bb = insertion_block builder in
1073 let the_function = block_parent start_bb in
1075 let then_bb = append_block context "then" the_function in
1077 (* Emit 'then' value. *)
1078 position_at_end then_bb builder;
1079 let then_val = codegen_expr then_ in
1081 (* Codegen of 'then' can change the current block, update then_bb for the
1082 * phi. We create a new name because one is used for the phi node, and the
1083 * other is used for the conditional branch. *)
1084 let new_then_bb = insertion_block builder in
1086 (* Emit 'else' value. *)
1087 let else_bb = append_block context "else" the_function in
1088 position_at_end else_bb builder;
1089 let else_val = codegen_expr else_ in
1091 (* Codegen of 'else' can change the current block, update else_bb for the
1093 let new_else_bb = insertion_block builder in
1095 (* Emit merge block. *)
1096 let merge_bb = append_block context "ifcont" the_function in
1097 position_at_end merge_bb builder;
1098 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
1099 let phi = build_phi incoming "iftmp" builder in
1101 (* Return to the start block to add the conditional branch. *)
1102 position_at_end start_bb builder;
1103 ignore (build_cond_br cond_val then_bb else_bb builder);
1105 (* Set a unconditional branch at the end of the 'then' block and the
1106 * 'else' block to the 'merge' block. *)
1107 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
1108 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
1110 (* Finally, set the builder to the end of the merge block. *)
1111 position_at_end merge_bb builder;
1114 | Ast.For (var_name, start, end_, step, body) ->
1115 (* Emit the start code first, without 'variable' in scope. *)
1116 let start_val = codegen_expr start in
1118 (* Make the new basic block for the loop header, inserting after current
1120 let preheader_bb = insertion_block builder in
1121 let the_function = block_parent preheader_bb in
1122 let loop_bb = append_block context "loop" the_function in
1124 (* Insert an explicit fall through from the current block to the
1126 ignore (build_br loop_bb builder);
1128 (* Start insertion in loop_bb. *)
1129 position_at_end loop_bb builder;
1131 (* Start the PHI node with an entry for start. *)
1132 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
1134 (* Within the loop, the variable is defined equal to the PHI node. If it
1135 * shadows an existing variable, we have to restore it, so save it
1138 try Some (Hashtbl.find named_values var_name) with Not_found -> None
1140 Hashtbl.add named_values var_name variable;
1142 (* Emit the body of the loop. This, like any other expr, can change the
1143 * current BB. Note that we ignore the value computed by the body, but
1144 * don't allow an error *)
1145 ignore (codegen_expr body);
1147 (* Emit the step value. *)
1150 | Some step -> codegen_expr step
1151 (* If not specified, use 1.0. *)
1152 | None -> const_float double_type 1.0
1155 let next_var = build_add variable step_val "nextvar" builder in
1157 (* Compute the end condition. *)
1158 let end_cond = codegen_expr end_ in
1160 (* Convert condition to a bool by comparing equal to 0.0. *)
1161 let zero = const_float double_type 0.0 in
1162 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
1164 (* Create the "after loop" block and insert it. *)
1165 let loop_end_bb = insertion_block builder in
1166 let after_bb = append_block context "afterloop" the_function in
1168 (* Insert the conditional branch into the end of loop_end_bb. *)
1169 ignore (build_cond_br end_cond loop_bb after_bb builder);
1171 (* Any new code will be inserted in after_bb. *)
1172 position_at_end after_bb builder;
1174 (* Add a new entry to the PHI node for the backedge. *)
1175 add_incoming (next_var, loop_end_bb) variable;
1177 (* Restore the unshadowed variable. *)
1178 begin match old_val with
1179 | Some old_val -> Hashtbl.add named_values var_name old_val
1183 (* for expr always returns 0.0. *)
1184 const_null double_type
1186 let codegen_proto = function
1187 | Ast.Prototype (name, args) ->
1188 (* Make the function type: double(double,double) etc. *)
1189 let doubles = Array.make (Array.length args) double_type in
1190 let ft = function_type double_type doubles in
1192 match lookup_function name the_module with
1193 | None -> declare_function name ft the_module
1195 (* If 'f' conflicted, there was already something named 'name'. If it
1196 * has a body, don't allow redefinition or reextern. *)
1198 (* If 'f' already has a body, reject this. *)
1199 if block_begin f <> At_end f then
1200 raise (Error "redefinition of function");
1202 (* If 'f' took a different number of arguments, reject. *)
1203 if element_type (type_of f) <> ft then
1204 raise (Error "redefinition of function with different # args");
1208 (* Set names for all arguments. *)
1209 Array.iteri (fun i a ->
1212 Hashtbl.add named_values n a;
1216 let codegen_func the_fpm = function
1217 | Ast.Function (proto, body) ->
1218 Hashtbl.clear named_values;
1219 let the_function = codegen_proto proto in
1221 (* Create a new basic block to start insertion into. *)
1222 let bb = append_block context "entry" the_function in
1223 position_at_end bb builder;
1226 let ret_val = codegen_expr body in
1228 (* Finish off the function. *)
1229 let _ = build_ret ret_val builder in
1231 (* Validate the generated code, checking for consistency. *)
1232 Llvm_analysis.assert_valid_function the_function;
1234 (* Optimize the function. *)
1235 let _ = PassManager.run_function the_function the_fpm in
1239 delete_function the_function;
1243 .. code-block:: ocaml
1245 (*===----------------------------------------------------------------------===
1246 * Top-Level parsing and JIT Driver
1247 *===----------------------------------------------------------------------===*)
1250 open Llvm_executionengine
1252 (* top ::= definition | external | expression | ';' *)
1253 let rec main_loop the_fpm the_execution_engine stream =
1254 match Stream.peek stream with
1257 (* ignore top-level semicolons. *)
1258 | Some (Token.Kwd ';') ->
1260 main_loop the_fpm the_execution_engine stream
1264 try match token with
1266 let e = Parser.parse_definition stream in
1267 print_endline "parsed a function definition.";
1268 dump_value (Codegen.codegen_func the_fpm e);
1270 let e = Parser.parse_extern stream in
1271 print_endline "parsed an extern.";
1272 dump_value (Codegen.codegen_proto e);
1274 (* Evaluate a top-level expression into an anonymous function. *)
1275 let e = Parser.parse_toplevel stream in
1276 print_endline "parsed a top-level expr";
1277 let the_function = Codegen.codegen_func the_fpm e in
1278 dump_value the_function;
1280 (* JIT the function, returning a function pointer. *)
1281 let result = ExecutionEngine.run_function the_function [||]
1282 the_execution_engine in
1284 print_string "Evaluated to ";
1285 print_float (GenericValue.as_float Codegen.double_type result);
1287 with Stream.Error s | Codegen.Error s ->
1288 (* Skip token for error recovery. *)
1292 print_string "ready> "; flush stdout;
1293 main_loop the_fpm the_execution_engine stream
1296 .. code-block:: ocaml
1298 (*===----------------------------------------------------------------------===
1300 *===----------------------------------------------------------------------===*)
1303 open Llvm_executionengine
1305 open Llvm_scalar_opts
1308 ignore (initialize_native_target ());
1310 (* Install standard binary operators.
1311 * 1 is the lowest precedence. *)
1312 Hashtbl.add Parser.binop_precedence '<' 10;
1313 Hashtbl.add Parser.binop_precedence '+' 20;
1314 Hashtbl.add Parser.binop_precedence '-' 20;
1315 Hashtbl.add Parser.binop_precedence '*' 40; (* highest. *)
1317 (* Prime the first token. *)
1318 print_string "ready> "; flush stdout;
1319 let stream = Lexer.lex (Stream.of_channel stdin) in
1321 (* Create the JIT. *)
1322 let the_execution_engine = ExecutionEngine.create Codegen.the_module in
1323 let the_fpm = PassManager.create_function Codegen.the_module in
1325 (* Set up the optimizer pipeline. Start with registering info about how the
1326 * target lays out data structures. *)
1327 DataLayout.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
1329 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
1330 add_instruction_combination the_fpm;
1332 (* reassociate expressions. *)
1333 add_reassociation the_fpm;
1335 (* Eliminate Common SubExpressions. *)
1338 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
1339 add_cfg_simplification the_fpm;
1341 ignore (PassManager.initialize the_fpm);
1343 (* Run the main "interpreter loop" now. *)
1344 Toplevel.main_loop the_fpm the_execution_engine stream;
1346 (* Print out all the generated code. *)
1347 dump_module Codegen.the_module
1357 /* putchard - putchar that takes a double and returns 0. */
1358 extern double putchard(double X) {
1363 `Next: Extending the language: user-defined
1364 operators <OCamlLangImpl6.html>`_