Lines Matching +full:end +full:- +full:of +full:- +full:stream
11 Welcome to Chapter 5 of the "`Implementing a language with
12 LLVM <index.html>`_" tutorial. Parts 1-4 described the implementation of
18 of "build that compiler", we'll extend Kaleidoscope to have an
32 sort of thing:
40 fib(x-1)+fib(x-2);
49 The semantics of the if/then/else expression is that it evaluates the
54 Kaleidoscope allows side-effects, this behavior is important to nail
61 ---------------------------------
66 .. code-block:: ocaml
74 .. code-block:: ocaml
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 >]
88 -------------------------------
92 .. code-block:: ocaml
97 | If of expr * expr * expr
102 ----------------------------------
108 .. code-block:: ocaml
115 'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
120 .. code-block:: ocaml
127 'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
131 ------------------------
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
151 .. code-block:: llvm
175 To visualize the control flow graph, you can use a nifty feature of the
177 IR into "t.ll" and run "``llvm-as < t.ll | opt -analyze -view-cfg``", `a
178 window will pop up <../ProgrammersManual.html#viewing-graphs-while-debugging-code>`_ and you'll
181 .. figure:: LangImpl05-cfg.png
197 and Not Equal"). Based on the result of this expression, the code jumps
204 caller of the function. The question then becomes: how does the code
214 "execution" of the Phi operation requires "remembering" which block
217 "then" block, it gets the value of "calltmp". If control comes from the
218 "else" block, it gets the value of "calltmp1".
221 simple and elegant front-end will have to start generating SSA form in
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
230 #. Values that are implicit in the structure of your AST, such as the
233 In `Chapter 7 <OCamlLangImpl7.html>`_ of this tutorial ("mutable
236 the choice of using the techniques that we will describe for #1, or you
240 Okay, enough of the motivation and overview, lets generate code!
243 --------------------------------
248 .. code-block:: ocaml
252 | Ast.If (cond, then_, else_) ->
261 a truth value as a 1-bit (bool) value.
263 .. code-block:: ocaml
266 * to it at the end of the function. *)
283 into the function's list of blocks.
285 .. code-block:: ocaml
291 (* Codegen of 'then' can change the current block, update then_bb for the
297 speaking, this call moves the insertion point to be at the end of the
299 starts out by inserting at the beginning of the block. :)
308 of the block in the CFG. Why then, are we getting the current block when
313 the notion of the current block, we are required to get an up-to-date
316 .. code-block:: ocaml
323 (* Codegen of 'else' can change the current block, update else_bb for the
330 .. code-block:: ocaml
344 .. code-block:: ocaml
355 .. code-block:: ocaml
357 (* Set a unconditional branch at the end of the 'then' block and the
362 (* Finally, set the builder to the end of the merge block. *)
368 block. One interesting (and very important) aspect of the LLVM IR is
378 value will feed into the code for the top-level function, which will
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
416 -----------------------------------
418 The lexer extensions are the same sort of thing as for if/then/else:
420 .. code-block:: ocaml
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 >]
439 ---------------------------------
444 .. code-block:: ocaml
449 | For of string * expr * expr * expr option * expr
452 ------------------------------------
455 is handling of the optional step value. The parser code handles it by
459 .. code-block:: ocaml
468 stream >] ->
474 stream >] ->
477 | [< 'Token.Kwd ','; step=parse_expr >] -> Some step
478 | [< >] -> None
479 end stream
482 | [< 'Token.In; body=parse_expr >] ->
484 | [< >] ->
485 raise (Stream.Error "expected 'in' after for")
486 end stream
487 | [< >] ->
488 raise (Stream.Error "expected '=' after for")
489 end stream
492 --------------------------
498 .. code-block:: llvm
530 ----------------------------------
532 The first part of Codegen is very simple: we just output the start
535 .. code-block:: ocaml
539 | Ast.For (var_name, start, end_, step, body) ->
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
546 of multiple blocks (e.g. if it contains an if/then/else or a for/in
549 .. code-block:: ocaml
564 the loop and create an unconditional branch for the fall-through between
567 .. code-block:: ocaml
582 .. code-block:: ocaml
588 try Some (Hashtbl.find named_values var_name) with Not_found -> None
592 (* Emit the body of the loop. This, like any other expr, can change the
600 before we codegen the body of the loop, we add the loop variable as the
602 variable of the same name in the outer scope. It would be easy to make
604 entry for VarName) but we choose to allow shadowing of variables. In
614 .. code-block:: ocaml
619 | Some step -> codegen_expr step
621 | None -> const_float double_type 1.0
626 Now that the body is emitted, we compute the next value of the iteration
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. *)
640 Finally, we evaluate the exit value of the loop, to determine whether
644 .. code-block:: ocaml
650 (* Insert the conditional branch into the end of loop_end_bb. *)
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
659 on the value of the exit condition, it creates a conditional branch that
664 .. code-block:: ocaml
671 | Some old_val -> Hashtbl.add named_values var_name old_val
672 | None -> ()
673 end;
681 that it isn't in scope after the for loop. Finally, code generation of
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
698 .. code-block:: bash
716 .. code-block:: ocaml
726 flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
730 .. code-block:: ocaml
732 (*===----------------------------------------------------------------------===
734 *===----------------------------------------------------------------------===*)
736 (* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
743 | Ident of string | Number of float
746 | Kwd of char
753 .. code-block:: ocaml
755 (*===----------------------------------------------------------------------===
757 *===----------------------------------------------------------------------===*)
761 | [< ' (' ' | '\n' | '\r' | '\t'); stream >] -> lex stream
763 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
764 | [< ' ('A' .. 'Z' | 'a' .. 'z' as c); stream >] ->
767 lex_ident buffer stream
769 (* number: [0-9.]+ *)
770 | [< ' ('0' .. '9' as c); stream >] ->
773 lex_number buffer stream
775 (* Comment until end of line. *)
776 | [< ' ('#'); stream >] ->
777 lex_comment stream
780 | [< 'c; stream >] ->
781 [< 'Token.Kwd c; lex stream >]
783 (* end of stream. *)
784 | [< >] -> [< >]
787 | [< ' ('0' .. '9' | '.' as c); stream >] ->
789 lex_number buffer stream
790 | [< stream=lex >] ->
791 [< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >]
794 | [< ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream >] ->
796 lex_ident buffer stream
797 | [< stream=lex >] ->
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 >]
809 | [< ' ('\n'); stream=lex >] -> stream
810 | [< 'c; e=lex_comment >] -> e
811 | [< >] -> [< >]
814 .. code-block:: ocaml
816 (*===----------------------------------------------------------------------===
818 *===----------------------------------------------------------------------===*)
820 (* expr - Base type for all expression nodes. *)
823 | Number of float
826 | Variable of string
829 | Binary of char * expr * expr
832 | Call of string * expr array
835 | If of expr * expr * expr
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
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
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
870 | [< 'Token.Number n >] -> Ast.Number n
873 | [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
878 | [< 'Token.Ident id; stream >] ->
880 | [< e=parse_expr; stream >] ->
882 | [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
883 | [< >] -> e :: accumulator
884 end stream
885 | [< >] -> accumulator
891 'Token.Kwd ')' ?? "expected ')'">] ->
895 | [< >] -> Ast.Variable id
897 parse_ident id stream
902 'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
910 stream >] ->
916 stream >] ->
919 | [< 'Token.Kwd ','; step=parse_expr >] -> Some step
920 | [< >] -> None
921 end stream
924 | [< 'Token.In; body=parse_expr >] ->
926 | [< >] ->
927 raise (Stream.Error "expected 'in' after for")
928 end stream
929 | [< >] ->
930 raise (Stream.Error "expected '=' after for")
931 end stream
933 | [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
937 and parse_bin_rhs expr_prec lhs stream =
938 match Stream.peek stream with
940 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
947 Stream.junk stream;
950 let rhs = parse_primary stream in
954 match Stream.peek stream with
955 | Some (Token.Kwd c2) ->
960 then parse_bin_rhs (token_prec + 1) rhs stream
962 | _ -> rhs
967 parse_bin_rhs expr_prec lhs stream
968 end
969 | _ -> lhs
974 | [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream
980 | [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
981 | [< >] -> accumulator
988 'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
992 | [< >] ->
993 raise (Stream.Error "expected function name in prototype")
997 | [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
1002 | [< e=parse_expr >] ->
1008 | [< 'Token.Extern; e=parse_prototype >] -> e
1011 .. code-block:: ocaml
1013 (*===----------------------------------------------------------------------===
1015 *===----------------------------------------------------------------------===*)
1019 exception Error of string
1028 | Ast.Number n -> const_float double_type n
1029 | Ast.Variable name ->
1031 | Not_found -> raise (Error "unknown variable name"))
1032 | Ast.Binary (op, lhs, rhs) ->
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
1040 | '<' ->
1044 | _ -> raise (Error "invalid binary operator")
1045 end
1046 | Ast.Call (callee, args) ->
1050 | Some callee -> callee
1051 | None -> raise (Error "unknown function referenced")
1060 | Ast.If (cond, then_, else_) ->
1068 * to it at the end of the function. *)
1078 (* Codegen of 'then' can change the current block, update then_bb for the
1088 (* Codegen of 'else' can change the current block, update else_bb for the
1102 (* Set a unconditional branch at the end of the 'then' block and the
1107 (* Finally, set the builder to the end of the merge block. *)
1111 | Ast.For (var_name, start, end_, step, body) ->
1135 try Some (Hashtbl.find named_values var_name) with Not_found -> None
1139 (* Emit the body of the loop. This, like any other expr, can change the
1147 | Some step -> codegen_expr step
1149 | None -> const_float double_type 1.0
1154 (* Compute the end condition. *)
1165 (* Insert the conditional branch into the end of loop_end_bb. *)
1176 | Some old_val -> Hashtbl.add named_values var_name old_val
1177 | None -> ()
1178 end;
1184 | Ast.Prototype (name, args) ->
1190 | None -> declare_function name ft the_module
1194 | Some f ->
1197 raise (Error "redefinition of function");
1199 (* If 'f' took a different number of arguments, reject. *)
1201 raise (Error "redefinition of function with different # args");
1206 Array.iteri (fun i a ->
1214 | Ast.Function (proto, body) ->
1235 with e ->
1240 .. code-block:: ocaml
1242 (*===----------------------------------------------------------------------===
1243 * Top-Level parsing and JIT Driver
1244 *===----------------------------------------------------------------------===*)
1250 let rec main_loop the_fpm the_execution_engine stream =
1251 match Stream.peek stream with
1252 | None -> ()
1254 (* ignore top-level semicolons. *)
1255 | Some (Token.Kwd ';') ->
1256 Stream.junk stream;
1257 main_loop the_fpm the_execution_engine stream
1259 | Some token ->
1262 | Token.Def ->
1263 let e = Parser.parse_definition stream in
1266 | Token.Extern ->
1267 let e = Parser.parse_extern stream in
1270 | _ ->
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";
1284 with Stream.Error s | Codegen.Error s ->
1286 Stream.junk stream;
1288 end;
1290 main_loop the_fpm the_execution_engine stream
1293 .. code-block:: ocaml
1295 (*===----------------------------------------------------------------------===
1297 *===----------------------------------------------------------------------===*)
1311 Hashtbl.add Parser.binop_precedence '-' 20;
1316 let stream = Lexer.lex (Stream.of_channel stdin) in
1326 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
1341 Toplevel.main_loop the_fpm the_execution_engine stream;
1350 .. code-block:: c
1354 /* putchard - putchar that takes a double and returns 0. */
1360 `Next: Extending the language: user-defined