blob: d356f126a4c1a744da93e4b99277e0002ac92dd6 [file] [log] [blame]
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3
4<html>
5<head>
6 <title>Kaleidoscope: Extending the Language: Control Flow</title>
7 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
8 <meta name="author" content="Chris Lattner">
9 <meta name="author" content="Erick Tryzelaar">
10 <link rel="stylesheet" href="../llvm.css" type="text/css">
11</head>
12
13<body>
14
NAKAMURA Takumi05d02652011-04-18 23:59:50 +000015<h1>Kaleidoscope: Extending the Language: Control Flow</h1>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +000016
17<ul>
18<li><a href="index.html">Up to Tutorial Index</a></li>
19<li>Chapter 5
20 <ol>
21 <li><a href="#intro">Chapter 5 Introduction</a></li>
22 <li><a href="#ifthen">If/Then/Else</a>
23 <ol>
24 <li><a href="#iflexer">Lexer Extensions</a></li>
25 <li><a href="#ifast">AST Extensions</a></li>
26 <li><a href="#ifparser">Parser Extensions</a></li>
27 <li><a href="#ifir">LLVM IR</a></li>
28 <li><a href="#ifcodegen">Code Generation</a></li>
29 </ol>
30 </li>
31 <li><a href="#for">'for' Loop Expression</a>
32 <ol>
33 <li><a href="#forlexer">Lexer Extensions</a></li>
34 <li><a href="#forast">AST Extensions</a></li>
35 <li><a href="#forparser">Parser Extensions</a></li>
36 <li><a href="#forir">LLVM IR</a></li>
37 <li><a href="#forcodegen">Code Generation</a></li>
38 </ol>
39 </li>
40 <li><a href="#code">Full Code Listing</a></li>
41 </ol>
42</li>
43<li><a href="OCamlLangImpl6.html">Chapter 6</a>: Extending the Language:
44User-defined Operators</li>
45</ul>
46
47<div class="doc_author">
48 <p>
49 Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>
50 and <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a>
51 </p>
52</div>
53
54<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +000055<h2><a name="intro">Chapter 5 Introduction</a></h2>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +000056<!-- *********************************************************************** -->
57
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +000058<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +000059
60<p>Welcome to Chapter 5 of the "<a href="index.html">Implementing a language
61with LLVM</a>" tutorial. Parts 1-4 described the implementation of the simple
62Kaleidoscope language and included support for generating LLVM IR, followed by
63optimizations and a JIT compiler. Unfortunately, as presented, Kaleidoscope is
64mostly useless: it has no control flow other than call and return. This means
65that you can't have conditional branches in the code, significantly limiting its
66power. In this episode of "build that compiler", we'll extend Kaleidoscope to
67have an if/then/else expression plus a simple 'for' loop.</p>
68
69</div>
70
71<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +000072<h2><a name="ifthen">If/Then/Else</a></h2>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +000073<!-- *********************************************************************** -->
74
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +000075<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +000076
77<p>
78Extending Kaleidoscope to support if/then/else is quite straightforward. It
79basically requires adding lexer support for this "new" concept to the lexer,
80parser, AST, and LLVM code emitter. This example is nice, because it shows how
81easy it is to "grow" a language over time, incrementally extending it as new
82ideas are discovered.</p>
83
84<p>Before we get going on "how" we add this extension, lets talk about "what" we
85want. The basic idea is that we want to be able to write this sort of thing:
86</p>
87
88<div class="doc_code">
89<pre>
90def fib(x)
91 if x &lt; 3 then
92 1
93 else
94 fib(x-1)+fib(x-2);
95</pre>
96</div>
97
98<p>In Kaleidoscope, every construct is an expression: there are no statements.
99As such, the if/then/else expression needs to return a value like any other.
100Since we're using a mostly functional form, we'll have it evaluate its
101conditional, then return the 'then' or 'else' value based on how the condition
102was resolved. This is very similar to the C "?:" expression.</p>
103
104<p>The semantics of the if/then/else expression is that it evaluates the
105condition to a boolean equality value: 0.0 is considered to be false and
106everything else is considered to be true.
107If the condition is true, the first subexpression is evaluated and returned, if
108the condition is false, the second subexpression is evaluated and returned.
109Since Kaleidoscope allows side-effects, this behavior is important to nail down.
110</p>
111
112<p>Now that we know what we "want", lets break this down into its constituent
113pieces.</p>
114
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000115<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000116<h4><a name="iflexer">Lexer Extensions for If/Then/Else</a></h4>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000117<!-- ======================================================================= -->
118
119
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000120<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000121
122<p>The lexer extensions are straightforward. First we add new variants
123for the relevant tokens:</p>
124
125<div class="doc_code">
126<pre>
127 (* control *)
128 | If | Then | Else | For | In
129</pre>
130</div>
131
132<p>Once we have that, we recognize the new keywords in the lexer. This is pretty simple
133stuff:</p>
134
135<div class="doc_code">
136<pre>
137 ...
138 match Buffer.contents buffer with
139 | "def" -&gt; [&lt; 'Token.Def; stream &gt;]
140 | "extern" -&gt; [&lt; 'Token.Extern; stream &gt;]
141 | "if" -&gt; [&lt; 'Token.If; stream &gt;]
142 | "then" -&gt; [&lt; 'Token.Then; stream &gt;]
143 | "else" -&gt; [&lt; 'Token.Else; stream &gt;]
144 | "for" -&gt; [&lt; 'Token.For; stream &gt;]
145 | "in" -&gt; [&lt; 'Token.In; stream &gt;]
146 | id -&gt; [&lt; 'Token.Ident id; stream &gt;]
147</pre>
148</div>
149
150</div>
151
152<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000153<h4><a name="ifast">AST Extensions for If/Then/Else</a></h4>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000154<!-- ======================================================================= -->
155
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000156<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000157
158<p>To represent the new expression we add a new AST variant for it:</p>
159
160<div class="doc_code">
161<pre>
162type expr =
163 ...
164 (* variant for if/then/else. *)
165 | If of expr * expr * expr
166</pre>
167</div>
168
169<p>The AST variant just has pointers to the various subexpressions.</p>
170
171</div>
172
173<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000174<h4><a name="ifparser">Parser Extensions for If/Then/Else</a></h4>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000175<!-- ======================================================================= -->
176
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000177<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000178
179<p>Now that we have the relevant tokens coming from the lexer and we have the
180AST node to build, our parsing logic is relatively straightforward. First we
181define a new parsing function:</p>
182
183<div class="doc_code">
184<pre>
185let rec parse_primary = parser
186 ...
187 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
188 | [&lt; 'Token.If; c=parse_expr;
189 'Token.Then ?? "expected 'then'"; t=parse_expr;
190 'Token.Else ?? "expected 'else'"; e=parse_expr &gt;] -&gt;
191 Ast.If (c, t, e)
192</pre>
193</div>
194
195<p>Next we hook it up as a primary expression:</p>
196
197<div class="doc_code">
198<pre>
199let rec parse_primary = parser
200 ...
201 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
202 | [&lt; 'Token.If; c=parse_expr;
203 'Token.Then ?? "expected 'then'"; t=parse_expr;
204 'Token.Else ?? "expected 'else'"; e=parse_expr &gt;] -&gt;
205 Ast.If (c, t, e)
206</pre>
207</div>
208
209</div>
210
211<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000212<h4><a name="ifir">LLVM IR for If/Then/Else</a></h4>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000213<!-- ======================================================================= -->
214
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000215<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000216
217<p>Now that we have it parsing and building the AST, the final piece is adding
218LLVM code generation support. This is the most interesting part of the
219if/then/else example, because this is where it starts to introduce new concepts.
220All of the code above has been thoroughly described in previous chapters.
221</p>
222
223<p>To motivate the code we want to produce, lets take a look at a simple
224example. Consider:</p>
225
226<div class="doc_code">
227<pre>
228extern foo();
229extern bar();
230def baz(x) if x then foo() else bar();
231</pre>
232</div>
233
234<p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
235looks like this:</p>
236
237<div class="doc_code">
238<pre>
239declare double @foo()
240
241declare double @bar()
242
243define double @baz(double %x) {
244entry:
245 %ifcond = fcmp one double %x, 0.000000e+00
246 br i1 %ifcond, label %then, label %else
247
248then: ; preds = %entry
249 %calltmp = call double @foo()
250 br label %ifcont
251
252else: ; preds = %entry
253 %calltmp1 = call double @bar()
254 br label %ifcont
255
256ifcont: ; preds = %else, %then
257 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
258 ret double %iftmp
259}
260</pre>
261</div>
262
263<p>To visualize the control flow graph, you can use a nifty feature of the LLVM
264'<a href="http://llvm.org/cmds/opt.html">opt</a>' tool. If you put this LLVM IR
265into "t.ll" and run "<tt>llvm-as &lt; t.ll | opt -analyze -view-cfg</tt>", <a
266href="../ProgrammersManual.html#ViewGraph">a window will pop up</a> and you'll
267see this graph:</p>
268
Benjamin Kramere15192b2009-08-05 15:42:44 +0000269<div style="text-align: center"><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
270height="315"></div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000271
272<p>Another way to get this is to call "<tt>Llvm_analysis.view_function_cfg
273f</tt>" or "<tt>Llvm_analysis.view_function_cfg_only f</tt>" (where <tt>f</tt>
274is a "<tt>Function</tt>") either by inserting actual calls into the code and
275recompiling or by calling these in the debugger. LLVM has many nice features
276for visualizing various graphs.</p>
277
278<p>Getting back to the generated code, it is fairly simple: the entry block
279evaluates the conditional expression ("x" in our case here) and compares the
280result to 0.0 with the "<tt><a href="../LangRef.html#i_fcmp">fcmp</a> one</tt>"
281instruction ('one' is "Ordered and Not Equal"). Based on the result of this
282expression, the code jumps to either the "then" or "else" blocks, which contain
283the expressions for the true/false cases.</p>
284
285<p>Once the then/else blocks are finished executing, they both branch back to the
286'ifcont' block to execute the code that happens after the if/then/else. In this
287case the only thing left to do is to return to the caller of the function. The
288question then becomes: how does the code know which expression to return?</p>
289
290<p>The answer to this question involves an important SSA operation: the
291<a href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Phi
292operation</a>. If you're not familiar with SSA, <a
293href="http://en.wikipedia.org/wiki/Static_single_assignment_form">the wikipedia
294article</a> is a good introduction and there are various other introductions to
295it available on your favorite search engine. The short version is that
296"execution" of the Phi operation requires "remembering" which block control came
297from. The Phi operation takes on the value corresponding to the input control
298block. In this case, if control comes in from the "then" block, it gets the
299value of "calltmp". If control comes from the "else" block, it gets the value
300of "calltmp1".</p>
301
302<p>At this point, you are probably starting to think "Oh no! This means my
303simple and elegant front-end will have to start generating SSA form in order to
304use LLVM!". Fortunately, this is not the case, and we strongly advise
305<em>not</em> implementing an SSA construction algorithm in your front-end
306unless there is an amazingly good reason to do so. In practice, there are two
307sorts of values that float around in code written for your average imperative
308programming language that might need Phi nodes:</p>
309
310<ol>
311<li>Code that involves user variables: <tt>x = 1; x = x + 1; </tt></li>
312<li>Values that are implicit in the structure of your AST, such as the Phi node
313in this case.</li>
314</ol>
315
316<p>In <a href="OCamlLangImpl7.html">Chapter 7</a> of this tutorial ("mutable
317variables"), we'll talk about #1
318in depth. For now, just believe me that you don't need SSA construction to
319handle this case. For #2, you have the choice of using the techniques that we will
320describe for #1, or you can insert Phi nodes directly, if convenient. In this
321case, it is really really easy to generate the Phi node, so we choose to do it
322directly.</p>
323
324<p>Okay, enough of the motivation and overview, lets generate code!</p>
325
326</div>
327
328<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000329<h4><a name="ifcodegen">Code Generation for If/Then/Else</a></h4>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000330<!-- ======================================================================= -->
331
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000332<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000333
334<p>In order to generate code for this, we implement the <tt>Codegen</tt> method
335for <tt>IfExprAST</tt>:</p>
336
337<div class="doc_code">
338<pre>
339let rec codegen_expr = function
340 ...
341 | Ast.If (cond, then_, else_) -&gt;
342 let cond = codegen_expr cond in
343
344 (* Convert condition to a bool by comparing equal to 0.0 *)
345 let zero = const_float double_type 0.0 in
346 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
347</pre>
348</div>
349
350<p>This code is straightforward and similar to what we saw before. We emit the
351expression for the condition, then compare that value to zero to get a truth
352value as a 1-bit (bool) value.</p>
353
354<div class="doc_code">
355<pre>
356 (* Grab the first block so that we might later add the conditional branch
357 * to it at the end of the function. *)
358 let start_bb = insertion_block builder in
359 let the_function = block_parent start_bb in
360
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +0000361 let then_bb = append_block context "then" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000362 position_at_end then_bb builder;
363</pre>
364</div>
365
366<p>
367As opposed to the <a href="LangImpl5.html">C++ tutorial</a>, we have to build
368our basic blocks bottom up since we can't have dangling BasicBlocks. We start
369off by saving a pointer to the first block (which might not be the entry
370block), which we'll need to build a conditional branch later. We do this by
371asking the <tt>builder</tt> for the current BasicBlock. The fourth line
372gets the current Function object that is being built. It gets this by the
373<tt>start_bb</tt> for its "parent" (the function it is currently embedded
374into).</p>
375
376<p>Once it has that, it creates one block. It is automatically appended into
377the function's list of blocks.</p>
378
379<div class="doc_code">
380<pre>
381 (* Emit 'then' value. *)
382 position_at_end then_bb builder;
383 let then_val = codegen_expr then_ in
384
385 (* Codegen of 'then' can change the current block, update then_bb for the
386 * phi. We create a new name because one is used for the phi node, and the
387 * other is used for the conditional branch. *)
388 let new_then_bb = insertion_block builder in
389</pre>
390</div>
391
392<p>We move the builder to start inserting into the "then" block. Strictly
393speaking, this call moves the insertion point to be at the end of the specified
394block. However, since the "then" block is empty, it also starts out by
395inserting at the beginning of the block. :)</p>
396
397<p>Once the insertion point is set, we recursively codegen the "then" expression
398from the AST.</p>
399
400<p>The final line here is quite subtle, but is very important. The basic issue
401is that when we create the Phi node in the merge block, we need to set up the
402block/value pairs that indicate how the Phi will work. Importantly, the Phi
403node expects to have an entry for each predecessor of the block in the CFG. Why
404then, are we getting the current block when we just set it to ThenBB 5 lines
405above? The problem is that the "Then" expression may actually itself change the
406block that the Builder is emitting into if, for example, it contains a nested
407"if/then/else" expression. Because calling Codegen recursively could
408arbitrarily change the notion of the current block, we are required to get an
409up-to-date value for code that will set up the Phi node.</p>
410
411<div class="doc_code">
412<pre>
413 (* Emit 'else' value. *)
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +0000414 let else_bb = append_block context "else" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000415 position_at_end else_bb builder;
416 let else_val = codegen_expr else_ in
417
418 (* Codegen of 'else' can change the current block, update else_bb for the
419 * phi. *)
420 let new_else_bb = insertion_block builder in
421</pre>
422</div>
423
424<p>Code generation for the 'else' block is basically identical to codegen for
425the 'then' block.</p>
426
427<div class="doc_code">
428<pre>
429 (* Emit merge block. *)
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +0000430 let merge_bb = append_block context "ifcont" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000431 position_at_end merge_bb builder;
432 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
433 let phi = build_phi incoming "iftmp" builder in
434</pre>
435</div>
436
437<p>The first two lines here are now familiar: the first adds the "merge" block
438to the Function object. The second block changes the insertion point so that
439newly created code will go into the "merge" block. Once that is done, we need
440to create the PHI node and set up the block/value pairs for the PHI.</p>
441
442<div class="doc_code">
443<pre>
444 (* Return to the start block to add the conditional branch. *)
445 position_at_end start_bb builder;
446 ignore (build_cond_br cond_val then_bb else_bb builder);
447</pre>
448</div>
449
450<p>Once the blocks are created, we can emit the conditional branch that chooses
451between them. Note that creating new blocks does not implicitly affect the
Duncan Sands89f6d882008-04-13 06:22:09 +0000452IRBuilder, so it is still inserting into the block that the condition
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000453went into. This is why we needed to save the "start" block.</p>
454
455<div class="doc_code">
456<pre>
457 (* Set a unconditional branch at the end of the 'then' block and the
458 * 'else' block to the 'merge' block. *)
459 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
460 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
461
462 (* Finally, set the builder to the end of the merge block. *)
463 position_at_end merge_bb builder;
464
465 phi
466</pre>
467</div>
468
469<p>To finish off the blocks, we create an unconditional branch
470to the merge block. One interesting (and very important) aspect of the LLVM IR
471is that it <a href="../LangRef.html#functionstructure">requires all basic blocks
472to be "terminated"</a> with a <a href="../LangRef.html#terminators">control flow
473instruction</a> such as return or branch. This means that all control flow,
474<em>including fall throughs</em> must be made explicit in the LLVM IR. If you
475violate this rule, the verifier will emit an error.
476
477<p>Finally, the CodeGen function returns the phi node as the value computed by
478the if/then/else expression. In our example above, this returned value will
479feed into the code for the top-level function, which will create the return
480instruction.</p>
481
482<p>Overall, we now have the ability to execute conditional code in
483Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
484that can calculate a wide variety of numeric functions. Next up we'll add
485another useful expression that is familiar from non-functional languages...</p>
486
487</div>
488
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000489</div>
490
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000491<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000492<h2><a name="for">'for' Loop Expression</a></h2>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000493<!-- *********************************************************************** -->
494
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000495<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000496
497<p>Now that we know how to add basic control flow constructs to the language,
498we have the tools to add more powerful things. Lets add something more
499aggressive, a 'for' expression:</p>
500
501<div class="doc_code">
502<pre>
503 extern putchard(char);
504 def printstar(n)
505 for i = 1, i &lt; n, 1.0 in
506 putchard(42); # ascii 42 = '*'
507
508 # print 100 '*' characters
509 printstar(100);
510</pre>
511</div>
512
513<p>This expression defines a new variable ("i" in this case) which iterates from
514a starting value, while the condition ("i &lt; n" in this case) is true,
515incrementing by an optional step value ("1.0" in this case). If the step value
516is omitted, it defaults to 1.0. While the loop is true, it executes its
517body expression. Because we don't have anything better to return, we'll just
518define the loop as always returning 0.0. In the future when we have mutable
519variables, it will get more useful.</p>
520
521<p>As before, lets talk about the changes that we need to Kaleidoscope to
522support this.</p>
523
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000524<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000525<h4><a name="forlexer">Lexer Extensions for the 'for' Loop</a></h4>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000526<!-- ======================================================================= -->
527
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000528<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000529
530<p>The lexer extensions are the same sort of thing as for if/then/else:</p>
531
532<div class="doc_code">
533<pre>
534 ... in Token.token ...
535 (* control *)
536 | If | Then | Else
537 <b>| For | In</b>
538
539 ... in Lexer.lex_ident...
540 match Buffer.contents buffer with
541 | "def" -&gt; [&lt; 'Token.Def; stream &gt;]
542 | "extern" -&gt; [&lt; 'Token.Extern; stream &gt;]
543 | "if" -&gt; [&lt; 'Token.If; stream &gt;]
544 | "then" -&gt; [&lt; 'Token.Then; stream &gt;]
545 | "else" -&gt; [&lt; 'Token.Else; stream &gt;]
546 <b>| "for" -&gt; [&lt; 'Token.For; stream &gt;]
547 | "in" -&gt; [&lt; 'Token.In; stream &gt;]</b>
548 | id -&gt; [&lt; 'Token.Ident id; stream &gt;]
549</pre>
550</div>
551
552</div>
553
554<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000555<h4><a name="forast">AST Extensions for the 'for' Loop</a></h4>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000556<!-- ======================================================================= -->
557
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000558<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000559
560<p>The AST variant is just as simple. It basically boils down to capturing
561the variable name and the constituent expressions in the node.</p>
562
563<div class="doc_code">
564<pre>
565type expr =
566 ...
567 (* variant for for/in. *)
568 | For of string * expr * expr * expr option * expr
569</pre>
570</div>
571
572</div>
573
574<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000575<h4><a name="forparser">Parser Extensions for the 'for' Loop</a></h4>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000576<!-- ======================================================================= -->
577
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000578<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000579
580<p>The parser code is also fairly standard. The only interesting thing here is
581handling of the optional step value. The parser code handles it by checking to
582see if the second comma is present. If not, it sets the step value to null in
583the AST node:</p>
584
585<div class="doc_code">
586<pre>
587let rec parse_primary = parser
588 ...
589 (* forexpr
590 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
591 | [&lt; 'Token.For;
592 'Token.Ident id ?? "expected identifier after for";
593 'Token.Kwd '=' ?? "expected '=' after for";
594 stream &gt;] -&gt;
595 begin parser
596 | [&lt;
597 start=parse_expr;
598 'Token.Kwd ',' ?? "expected ',' after for";
599 end_=parse_expr;
600 stream &gt;] -&gt;
601 let step =
602 begin parser
603 | [&lt; 'Token.Kwd ','; step=parse_expr &gt;] -&gt; Some step
604 | [&lt; &gt;] -&gt; None
605 end stream
606 in
607 begin parser
608 | [&lt; 'Token.In; body=parse_expr &gt;] -&gt;
609 Ast.For (id, start, end_, step, body)
610 | [&lt; &gt;] -&gt;
611 raise (Stream.Error "expected 'in' after for")
612 end stream
613 | [&lt; &gt;] -&gt;
614 raise (Stream.Error "expected '=' after for")
615 end stream
616</pre>
617</div>
618
619</div>
620
621<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000622<h4><a name="forir">LLVM IR for the 'for' Loop</a></h4>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000623<!-- ======================================================================= -->
624
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000625<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000626
627<p>Now we get to the good part: the LLVM IR we want to generate for this thing.
628With the simple example above, we get this LLVM IR (note that this dump is
629generated with optimizations disabled for clarity):
630</p>
631
632<div class="doc_code">
633<pre>
634declare double @putchard(double)
635
636define double @printstar(double %n) {
637entry:
638 ; initial value = 1.0 (inlined into phi)
639 br label %loop
640
641loop: ; preds = %loop, %entry
642 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
643 ; body
Dan Gohman3dfb3cf2010-05-28 17:07:41 +0000644 %calltmp = call double @putchard(double 4.200000e+01)
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000645 ; increment
Dan Gohmana9445e12010-03-02 01:11:08 +0000646 %nextvar = fadd double %i, 1.000000e+00
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000647
648 ; termination test
649 %cmptmp = fcmp ult double %i, %n
650 %booltmp = uitofp i1 %cmptmp to double
651 %loopcond = fcmp one double %booltmp, 0.000000e+00
652 br i1 %loopcond, label %loop, label %afterloop
653
654afterloop: ; preds = %loop
655 ; loop always returns 0.0
656 ret double 0.000000e+00
657}
658</pre>
659</div>
660
661<p>This loop contains all the same constructs we saw before: a phi node, several
662expressions, and some basic blocks. Lets see how this fits together.</p>
663
664</div>
665
666<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000667<h4><a name="forcodegen">Code Generation for the 'for' Loop</a></h4>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000668<!-- ======================================================================= -->
669
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000670<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000671
672<p>The first part of Codegen is very simple: we just output the start expression
673for the loop value:</p>
674
675<div class="doc_code">
676<pre>
677let rec codegen_expr = function
678 ...
679 | Ast.For (var_name, start, end_, step, body) -&gt;
680 (* Emit the start code first, without 'variable' in scope. *)
681 let start_val = codegen_expr start in
682</pre>
683</div>
684
685<p>With this out of the way, the next step is to set up the LLVM basic block
686for the start of the loop body. In the case above, the whole loop body is one
687block, but remember that the body code itself could consist of multiple blocks
688(e.g. if it contains an if/then/else or a for/in expression).</p>
689
690<div class="doc_code">
691<pre>
692 (* Make the new basic block for the loop header, inserting after current
693 * block. *)
694 let preheader_bb = insertion_block builder in
695 let the_function = block_parent preheader_bb in
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +0000696 let loop_bb = append_block context "loop" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000697
698 (* Insert an explicit fall through from the current block to the
699 * loop_bb. *)
700 ignore (build_br loop_bb builder);
701</pre>
702</div>
703
704<p>This code is similar to what we saw for if/then/else. Because we will need
705it to create the Phi node, we remember the block that falls through into the
706loop. Once we have that, we create the actual block that starts the loop and
707create an unconditional branch for the fall-through between the two blocks.</p>
708
709<div class="doc_code">
710<pre>
711 (* Start insertion in loop_bb. *)
712 position_at_end loop_bb builder;
713
714 (* Start the PHI node with an entry for start. *)
715 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
716</pre>
717</div>
718
719<p>Now that the "preheader" for the loop is set up, we switch to emitting code
720for the loop body. To begin with, we move the insertion point and create the
721PHI node for the loop induction variable. Since we already know the incoming
722value for the starting value, we add it to the Phi node. Note that the Phi will
723eventually get a second value for the backedge, but we can't set it up yet
724(because it doesn't exist!).</p>
725
726<div class="doc_code">
727<pre>
728 (* Within the loop, the variable is defined equal to the PHI node. If it
729 * shadows an existing variable, we have to restore it, so save it
730 * now. *)
731 let old_val =
732 try Some (Hashtbl.find named_values var_name) with Not_found -&gt; None
733 in
734 Hashtbl.add named_values var_name variable;
735
736 (* Emit the body of the loop. This, like any other expr, can change the
737 * current BB. Note that we ignore the value computed by the body, but
738 * don't allow an error *)
739 ignore (codegen_expr body);
740</pre>
741</div>
742
743<p>Now the code starts to get more interesting. Our 'for' loop introduces a new
744variable to the symbol table. This means that our symbol table can now contain
745either function arguments or loop variables. To handle this, before we codegen
746the body of the loop, we add the loop variable as the current value for its
747name. Note that it is possible that there is a variable of the same name in the
748outer scope. It would be easy to make this an error (emit an error and return
749null if there is already an entry for VarName) but we choose to allow shadowing
750of variables. In order to handle this correctly, we remember the Value that
751we are potentially shadowing in <tt>old_val</tt> (which will be None if there is
752no shadowed variable).</p>
753
754<p>Once the loop variable is set into the symbol table, the code recursively
755codegen's the body. This allows the body to use the loop variable: any
756references to it will naturally find it in the symbol table.</p>
757
758<div class="doc_code">
759<pre>
760 (* Emit the step value. *)
761 let step_val =
762 match step with
763 | Some step -&gt; codegen_expr step
764 (* If not specified, use 1.0. *)
765 | None -&gt; const_float double_type 1.0
766 in
767
768 let next_var = build_add variable step_val "nextvar" builder in
769</pre>
770</div>
771
772<p>Now that the body is emitted, we compute the next value of the iteration
773variable by adding the step value, or 1.0 if it isn't present.
774'<tt>next_var</tt>' will be the value of the loop variable on the next iteration
775of the loop.</p>
776
777<div class="doc_code">
778<pre>
779 (* Compute the end condition. *)
780 let end_cond = codegen_expr end_ in
781
782 (* Convert condition to a bool by comparing equal to 0.0. *)
783 let zero = const_float double_type 0.0 in
784 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
785</pre>
786</div>
787
788<p>Finally, we evaluate the exit value of the loop, to determine whether the
789loop should exit. This mirrors the condition evaluation for the if/then/else
790statement.</p>
791
792<div class="doc_code">
793<pre>
794 (* Create the "after loop" block and insert it. *)
795 let loop_end_bb = insertion_block builder in
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +0000796 let after_bb = append_block context "afterloop" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000797
798 (* Insert the conditional branch into the end of loop_end_bb. *)
799 ignore (build_cond_br end_cond loop_bb after_bb builder);
800
801 (* Any new code will be inserted in after_bb. *)
802 position_at_end after_bb builder;
803</pre>
804</div>
805
806<p>With the code for the body of the loop complete, we just need to finish up
807the control flow for it. This code remembers the end block (for the phi node), then creates the block for the loop exit ("afterloop"). Based on the value of the
808exit condition, it creates a conditional branch that chooses between executing
809the loop again and exiting the loop. Any future code is emitted in the
810"afterloop" block, so it sets the insertion position to it.</p>
811
812<div class="doc_code">
813<pre>
814 (* Add a new entry to the PHI node for the backedge. *)
815 add_incoming (next_var, loop_end_bb) variable;
816
817 (* Restore the unshadowed variable. *)
818 begin match old_val with
819 | Some old_val -&gt; Hashtbl.add named_values var_name old_val
820 | None -&gt; ()
821 end;
822
823 (* for expr always returns 0.0. *)
824 const_null double_type
825</pre>
826</div>
827
828<p>The final code handles various cleanups: now that we have the
829"<tt>next_var</tt>" value, we can add the incoming value to the loop PHI node.
830After that, we remove the loop variable from the symbol table, so that it isn't
831in scope after the for loop. Finally, code generation of the for loop always
832returns 0.0, so that is what we return from <tt>Codegen.codegen_expr</tt>.</p>
833
834<p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
835the tutorial. In this chapter we added two control flow constructs, and used
836them to motivate a couple of aspects of the LLVM IR that are important for
837front-end implementors to know. In the next chapter of our saga, we will get
838a bit crazier and add <a href="OCamlLangImpl6.html">user-defined operators</a>
839to our poor innocent language.</p>
840
841</div>
842
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000843</div>
844
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000845<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000846<h2><a name="code">Full Code Listing</a></h2>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000847<!-- *********************************************************************** -->
848
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000849<div>
Erick Tryzelaar35295ff2008-03-31 08:44:50 +0000850
851<p>
852Here is the complete code listing for our running example, enhanced with the
853if/then/else and for expressions.. To build this example, use:
854</p>
855
856<div class="doc_code">
857<pre>
858# Compile
859ocamlbuild toy.byte
860# Run
861./toy.byte
862</pre>
863</div>
864
865<p>Here is the code:</p>
866
867<dl>
868<dt>_tags:</dt>
869<dd class="doc_code">
870<pre>
871&lt;{lexer,parser}.ml&gt;: use_camlp4, pp(camlp4of)
872&lt;*.{byte,native}&gt;: g++, use_llvm, use_llvm_analysis
873&lt;*.{byte,native}&gt;: use_llvm_executionengine, use_llvm_target
874&lt;*.{byte,native}&gt;: use_llvm_scalar_opts, use_bindings
875</pre>
876</dd>
877
878<dt>myocamlbuild.ml:</dt>
879<dd class="doc_code">
880<pre>
881open Ocamlbuild_plugin;;
882
883ocaml_lib ~extern:true "llvm";;
884ocaml_lib ~extern:true "llvm_analysis";;
885ocaml_lib ~extern:true "llvm_executionengine";;
886ocaml_lib ~extern:true "llvm_target";;
887ocaml_lib ~extern:true "llvm_scalar_opts";;
888
889flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
890dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
891</pre>
892</dd>
893
894<dt>token.ml:</dt>
895<dd class="doc_code">
896<pre>
897(*===----------------------------------------------------------------------===
898 * Lexer Tokens
899 *===----------------------------------------------------------------------===*)
900
901(* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
902 * these others for known things. *)
903type token =
904 (* commands *)
905 | Def | Extern
906
907 (* primary *)
908 | Ident of string | Number of float
909
910 (* unknown *)
911 | Kwd of char
912
913 (* control *)
914 | If | Then | Else
915 | For | In
916</pre>
917</dd>
918
919<dt>lexer.ml:</dt>
920<dd class="doc_code">
921<pre>
922(*===----------------------------------------------------------------------===
923 * Lexer
924 *===----------------------------------------------------------------------===*)
925
926let rec lex = parser
927 (* Skip any whitespace. *)
928 | [&lt; ' (' ' | '\n' | '\r' | '\t'); stream &gt;] -&gt; lex stream
929
930 (* identifier: [a-zA-Z][a-zA-Z0-9] *)
931 | [&lt; ' ('A' .. 'Z' | 'a' .. 'z' as c); stream &gt;] -&gt;
932 let buffer = Buffer.create 1 in
933 Buffer.add_char buffer c;
934 lex_ident buffer stream
935
936 (* number: [0-9.]+ *)
937 | [&lt; ' ('0' .. '9' as c); stream &gt;] -&gt;
938 let buffer = Buffer.create 1 in
939 Buffer.add_char buffer c;
940 lex_number buffer stream
941
942 (* Comment until end of line. *)
943 | [&lt; ' ('#'); stream &gt;] -&gt;
944 lex_comment stream
945
946 (* Otherwise, just return the character as its ascii value. *)
947 | [&lt; 'c; stream &gt;] -&gt;
948 [&lt; 'Token.Kwd c; lex stream &gt;]
949
950 (* end of stream. *)
951 | [&lt; &gt;] -&gt; [&lt; &gt;]
952
953and lex_number buffer = parser
954 | [&lt; ' ('0' .. '9' | '.' as c); stream &gt;] -&gt;
955 Buffer.add_char buffer c;
956 lex_number buffer stream
957 | [&lt; stream=lex &gt;] -&gt;
958 [&lt; 'Token.Number (float_of_string (Buffer.contents buffer)); stream &gt;]
959
960and lex_ident buffer = parser
961 | [&lt; ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream &gt;] -&gt;
962 Buffer.add_char buffer c;
963 lex_ident buffer stream
964 | [&lt; stream=lex &gt;] -&gt;
965 match Buffer.contents buffer with
966 | "def" -&gt; [&lt; 'Token.Def; stream &gt;]
967 | "extern" -&gt; [&lt; 'Token.Extern; stream &gt;]
968 | "if" -&gt; [&lt; 'Token.If; stream &gt;]
969 | "then" -&gt; [&lt; 'Token.Then; stream &gt;]
970 | "else" -&gt; [&lt; 'Token.Else; stream &gt;]
971 | "for" -&gt; [&lt; 'Token.For; stream &gt;]
972 | "in" -&gt; [&lt; 'Token.In; stream &gt;]
973 | id -&gt; [&lt; 'Token.Ident id; stream &gt;]
974
975and lex_comment = parser
976 | [&lt; ' ('\n'); stream=lex &gt;] -&gt; stream
977 | [&lt; 'c; e=lex_comment &gt;] -&gt; e
978 | [&lt; &gt;] -&gt; [&lt; &gt;]
979</pre>
980</dd>
981
982<dt>ast.ml:</dt>
983<dd class="doc_code">
984<pre>
985(*===----------------------------------------------------------------------===
986 * Abstract Syntax Tree (aka Parse Tree)
987 *===----------------------------------------------------------------------===*)
988
989(* expr - Base type for all expression nodes. *)
990type expr =
991 (* variant for numeric literals like "1.0". *)
992 | Number of float
993
994 (* variant for referencing a variable, like "a". *)
995 | Variable of string
996
997 (* variant for a binary operator. *)
998 | Binary of char * expr * expr
999
1000 (* variant for function calls. *)
1001 | Call of string * expr array
1002
1003 (* variant for if/then/else. *)
1004 | If of expr * expr * expr
1005
1006 (* variant for for/in. *)
1007 | For of string * expr * expr * expr option * expr
1008
1009(* proto - This type represents the "prototype" for a function, which captures
1010 * its name, and its argument names (thus implicitly the number of arguments the
1011 * function takes). *)
1012type proto = Prototype of string * string array
1013
1014(* func - This type represents a function definition itself. *)
1015type func = Function of proto * expr
1016</pre>
1017</dd>
1018
1019<dt>parser.ml:</dt>
1020<dd class="doc_code">
1021<pre>
1022(*===---------------------------------------------------------------------===
1023 * Parser
1024 *===---------------------------------------------------------------------===*)
1025
1026(* binop_precedence - This holds the precedence for each binary operator that is
1027 * defined *)
1028let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
1029
1030(* precedence - Get the precedence of the pending binary operator token. *)
1031let precedence c = try Hashtbl.find binop_precedence c with Not_found -&gt; -1
1032
1033(* primary
1034 * ::= identifier
1035 * ::= numberexpr
1036 * ::= parenexpr
1037 * ::= ifexpr
1038 * ::= forexpr *)
1039let rec parse_primary = parser
1040 (* numberexpr ::= number *)
1041 | [&lt; 'Token.Number n &gt;] -&gt; Ast.Number n
1042
1043 (* parenexpr ::= '(' expression ')' *)
1044 | [&lt; 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" &gt;] -&gt; e
1045
1046 (* identifierexpr
1047 * ::= identifier
1048 * ::= identifier '(' argumentexpr ')' *)
1049 | [&lt; 'Token.Ident id; stream &gt;] -&gt;
1050 let rec parse_args accumulator = parser
1051 | [&lt; e=parse_expr; stream &gt;] -&gt;
1052 begin parser
1053 | [&lt; 'Token.Kwd ','; e=parse_args (e :: accumulator) &gt;] -&gt; e
1054 | [&lt; &gt;] -&gt; e :: accumulator
1055 end stream
1056 | [&lt; &gt;] -&gt; accumulator
1057 in
1058 let rec parse_ident id = parser
1059 (* Call. *)
1060 | [&lt; 'Token.Kwd '(';
1061 args=parse_args [];
1062 'Token.Kwd ')' ?? "expected ')'"&gt;] -&gt;
1063 Ast.Call (id, Array.of_list (List.rev args))
1064
1065 (* Simple variable ref. *)
1066 | [&lt; &gt;] -&gt; Ast.Variable id
1067 in
1068 parse_ident id stream
1069
1070 (* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
1071 | [&lt; 'Token.If; c=parse_expr;
1072 'Token.Then ?? "expected 'then'"; t=parse_expr;
1073 'Token.Else ?? "expected 'else'"; e=parse_expr &gt;] -&gt;
1074 Ast.If (c, t, e)
1075
1076 (* forexpr
1077 ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
1078 | [&lt; 'Token.For;
1079 'Token.Ident id ?? "expected identifier after for";
1080 'Token.Kwd '=' ?? "expected '=' after for";
1081 stream &gt;] -&gt;
1082 begin parser
1083 | [&lt;
1084 start=parse_expr;
1085 'Token.Kwd ',' ?? "expected ',' after for";
1086 end_=parse_expr;
1087 stream &gt;] -&gt;
1088 let step =
1089 begin parser
1090 | [&lt; 'Token.Kwd ','; step=parse_expr &gt;] -&gt; Some step
1091 | [&lt; &gt;] -&gt; None
1092 end stream
1093 in
1094 begin parser
1095 | [&lt; 'Token.In; body=parse_expr &gt;] -&gt;
1096 Ast.For (id, start, end_, step, body)
1097 | [&lt; &gt;] -&gt;
1098 raise (Stream.Error "expected 'in' after for")
1099 end stream
1100 | [&lt; &gt;] -&gt;
1101 raise (Stream.Error "expected '=' after for")
1102 end stream
1103
1104 | [&lt; &gt;] -&gt; raise (Stream.Error "unknown token when expecting an expression.")
1105
1106(* binoprhs
1107 * ::= ('+' primary)* *)
1108and parse_bin_rhs expr_prec lhs stream =
1109 match Stream.peek stream with
1110 (* If this is a binop, find its precedence. *)
1111 | Some (Token.Kwd c) when Hashtbl.mem binop_precedence c -&gt;
1112 let token_prec = precedence c in
1113
1114 (* If this is a binop that binds at least as tightly as the current binop,
1115 * consume it, otherwise we are done. *)
1116 if token_prec &lt; expr_prec then lhs else begin
1117 (* Eat the binop. *)
1118 Stream.junk stream;
1119
1120 (* Parse the primary expression after the binary operator. *)
1121 let rhs = parse_primary stream in
1122
1123 (* Okay, we know this is a binop. *)
1124 let rhs =
1125 match Stream.peek stream with
1126 | Some (Token.Kwd c2) -&gt;
1127 (* If BinOp binds less tightly with rhs than the operator after
1128 * rhs, let the pending operator take rhs as its lhs. *)
1129 let next_prec = precedence c2 in
1130 if token_prec &lt; next_prec
1131 then parse_bin_rhs (token_prec + 1) rhs stream
1132 else rhs
1133 | _ -&gt; rhs
1134 in
1135
1136 (* Merge lhs/rhs. *)
1137 let lhs = Ast.Binary (c, lhs, rhs) in
1138 parse_bin_rhs expr_prec lhs stream
1139 end
1140 | _ -&gt; lhs
1141
1142(* expression
1143 * ::= primary binoprhs *)
1144and parse_expr = parser
1145 | [&lt; lhs=parse_primary; stream &gt;] -&gt; parse_bin_rhs 0 lhs stream
1146
1147(* prototype
1148 * ::= id '(' id* ')' *)
1149let parse_prototype =
1150 let rec parse_args accumulator = parser
1151 | [&lt; 'Token.Ident id; e=parse_args (id::accumulator) &gt;] -&gt; e
1152 | [&lt; &gt;] -&gt; accumulator
1153 in
1154
1155 parser
1156 | [&lt; 'Token.Ident id;
1157 'Token.Kwd '(' ?? "expected '(' in prototype";
1158 args=parse_args [];
1159 'Token.Kwd ')' ?? "expected ')' in prototype" &gt;] -&gt;
1160 (* success. *)
1161 Ast.Prototype (id, Array.of_list (List.rev args))
1162
1163 | [&lt; &gt;] -&gt;
1164 raise (Stream.Error "expected function name in prototype")
1165
1166(* definition ::= 'def' prototype expression *)
1167let parse_definition = parser
1168 | [&lt; 'Token.Def; p=parse_prototype; e=parse_expr &gt;] -&gt;
1169 Ast.Function (p, e)
1170
1171(* toplevelexpr ::= expression *)
1172let parse_toplevel = parser
1173 | [&lt; e=parse_expr &gt;] -&gt;
1174 (* Make an anonymous proto. *)
1175 Ast.Function (Ast.Prototype ("", [||]), e)
1176
1177(* external ::= 'extern' prototype *)
1178let parse_extern = parser
1179 | [&lt; 'Token.Extern; e=parse_prototype &gt;] -&gt; e
1180</pre>
1181</dd>
1182
1183<dt>codegen.ml:</dt>
1184<dd class="doc_code">
1185<pre>
1186(*===----------------------------------------------------------------------===
1187 * Code Generation
1188 *===----------------------------------------------------------------------===*)
1189
1190open Llvm
1191
1192exception Error of string
1193
Erick Tryzelaar1f3d2762009-08-19 17:32:38 +00001194let context = global_context ()
1195let the_module = create_module context "my cool jit"
1196let builder = builder context
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001197let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +00001198let double_type = double_type context
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001199
1200let rec codegen_expr = function
1201 | Ast.Number n -&gt; const_float double_type n
1202 | Ast.Variable name -&gt;
1203 (try Hashtbl.find named_values name with
1204 | Not_found -&gt; raise (Error "unknown variable name"))
1205 | Ast.Binary (op, lhs, rhs) -&gt;
1206 let lhs_val = codegen_expr lhs in
1207 let rhs_val = codegen_expr rhs in
1208 begin
1209 match op with
1210 | '+' -&gt; build_add lhs_val rhs_val "addtmp" builder
1211 | '-' -&gt; build_sub lhs_val rhs_val "subtmp" builder
1212 | '*' -&gt; build_mul lhs_val rhs_val "multmp" builder
1213 | '&lt;' -&gt;
1214 (* Convert bool 0/1 to double 0.0 or 1.0 *)
1215 let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
1216 build_uitofp i double_type "booltmp" builder
1217 | _ -&gt; raise (Error "invalid binary operator")
1218 end
1219 | Ast.Call (callee, args) -&gt;
1220 (* Look up the name in the module table. *)
1221 let callee =
1222 match lookup_function callee the_module with
1223 | Some callee -&gt; callee
1224 | None -&gt; raise (Error "unknown function referenced")
1225 in
1226 let params = params callee in
1227
1228 (* If argument mismatch error. *)
1229 if Array.length params == Array.length args then () else
1230 raise (Error "incorrect # arguments passed");
1231 let args = Array.map codegen_expr args in
1232 build_call callee args "calltmp" builder
1233 | Ast.If (cond, then_, else_) -&gt;
1234 let cond = codegen_expr cond in
1235
1236 (* Convert condition to a bool by comparing equal to 0.0 *)
1237 let zero = const_float double_type 0.0 in
1238 let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
1239
1240 (* Grab the first block so that we might later add the conditional branch
1241 * to it at the end of the function. *)
1242 let start_bb = insertion_block builder in
1243 let the_function = block_parent start_bb in
1244
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +00001245 let then_bb = append_block context "then" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001246
1247 (* Emit 'then' value. *)
1248 position_at_end then_bb builder;
1249 let then_val = codegen_expr then_ in
1250
1251 (* Codegen of 'then' can change the current block, update then_bb for the
1252 * phi. We create a new name because one is used for the phi node, and the
1253 * other is used for the conditional branch. *)
1254 let new_then_bb = insertion_block builder in
1255
1256 (* Emit 'else' value. *)
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +00001257 let else_bb = append_block context "else" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001258 position_at_end else_bb builder;
1259 let else_val = codegen_expr else_ in
1260
1261 (* Codegen of 'else' can change the current block, update else_bb for the
1262 * phi. *)
1263 let new_else_bb = insertion_block builder in
1264
1265 (* Emit merge block. *)
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +00001266 let merge_bb = append_block context "ifcont" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001267 position_at_end merge_bb builder;
1268 let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
1269 let phi = build_phi incoming "iftmp" builder in
1270
1271 (* Return to the start block to add the conditional branch. *)
1272 position_at_end start_bb builder;
1273 ignore (build_cond_br cond_val then_bb else_bb builder);
1274
1275 (* Set a unconditional branch at the end of the 'then' block and the
1276 * 'else' block to the 'merge' block. *)
1277 position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
1278 position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
1279
1280 (* Finally, set the builder to the end of the merge block. *)
1281 position_at_end merge_bb builder;
1282
1283 phi
1284 | Ast.For (var_name, start, end_, step, body) -&gt;
1285 (* Emit the start code first, without 'variable' in scope. *)
1286 let start_val = codegen_expr start in
1287
1288 (* Make the new basic block for the loop header, inserting after current
1289 * block. *)
1290 let preheader_bb = insertion_block builder in
1291 let the_function = block_parent preheader_bb in
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +00001292 let loop_bb = append_block context "loop" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001293
1294 (* Insert an explicit fall through from the current block to the
1295 * loop_bb. *)
1296 ignore (build_br loop_bb builder);
1297
1298 (* Start insertion in loop_bb. *)
1299 position_at_end loop_bb builder;
1300
1301 (* Start the PHI node with an entry for start. *)
1302 let variable = build_phi [(start_val, preheader_bb)] var_name builder in
1303
1304 (* Within the loop, the variable is defined equal to the PHI node. If it
1305 * shadows an existing variable, we have to restore it, so save it
1306 * now. *)
1307 let old_val =
1308 try Some (Hashtbl.find named_values var_name) with Not_found -&gt; None
1309 in
1310 Hashtbl.add named_values var_name variable;
1311
1312 (* Emit the body of the loop. This, like any other expr, can change the
1313 * current BB. Note that we ignore the value computed by the body, but
1314 * don't allow an error *)
1315 ignore (codegen_expr body);
1316
1317 (* Emit the step value. *)
1318 let step_val =
1319 match step with
1320 | Some step -&gt; codegen_expr step
1321 (* If not specified, use 1.0. *)
1322 | None -&gt; const_float double_type 1.0
1323 in
1324
1325 let next_var = build_add variable step_val "nextvar" builder in
1326
1327 (* Compute the end condition. *)
1328 let end_cond = codegen_expr end_ in
1329
1330 (* Convert condition to a bool by comparing equal to 0.0. *)
1331 let zero = const_float double_type 0.0 in
1332 let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
1333
1334 (* Create the "after loop" block and insert it. *)
1335 let loop_end_bb = insertion_block builder in
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +00001336 let after_bb = append_block context "afterloop" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001337
1338 (* Insert the conditional branch into the end of loop_end_bb. *)
1339 ignore (build_cond_br end_cond loop_bb after_bb builder);
1340
1341 (* Any new code will be inserted in after_bb. *)
1342 position_at_end after_bb builder;
1343
1344 (* Add a new entry to the PHI node for the backedge. *)
1345 add_incoming (next_var, loop_end_bb) variable;
1346
1347 (* Restore the unshadowed variable. *)
1348 begin match old_val with
1349 | Some old_val -&gt; Hashtbl.add named_values var_name old_val
1350 | None -&gt; ()
1351 end;
1352
1353 (* for expr always returns 0.0. *)
1354 const_null double_type
1355
1356let codegen_proto = function
1357 | Ast.Prototype (name, args) -&gt;
1358 (* Make the function type: double(double,double) etc. *)
1359 let doubles = Array.make (Array.length args) double_type in
1360 let ft = function_type double_type doubles in
1361 let f =
1362 match lookup_function name the_module with
1363 | None -&gt; declare_function name ft the_module
1364
1365 (* If 'f' conflicted, there was already something named 'name'. If it
1366 * has a body, don't allow redefinition or reextern. *)
1367 | Some f -&gt;
1368 (* If 'f' already has a body, reject this. *)
1369 if block_begin f &lt;&gt; At_end f then
1370 raise (Error "redefinition of function");
1371
1372 (* If 'f' took a different number of arguments, reject. *)
1373 if element_type (type_of f) &lt;&gt; ft then
1374 raise (Error "redefinition of function with different # args");
1375 f
1376 in
1377
1378 (* Set names for all arguments. *)
1379 Array.iteri (fun i a -&gt;
1380 let n = args.(i) in
1381 set_value_name n a;
1382 Hashtbl.add named_values n a;
1383 ) (params f);
1384 f
1385
1386let codegen_func the_fpm = function
1387 | Ast.Function (proto, body) -&gt;
1388 Hashtbl.clear named_values;
1389 let the_function = codegen_proto proto in
1390
1391 (* Create a new basic block to start insertion into. *)
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +00001392 let bb = append_block context "entry" the_function in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001393 position_at_end bb builder;
1394
1395 try
1396 let ret_val = codegen_expr body in
1397
1398 (* Finish off the function. *)
1399 let _ = build_ret ret_val builder in
1400
1401 (* Validate the generated code, checking for consistency. *)
1402 Llvm_analysis.assert_valid_function the_function;
1403
1404 (* Optimize the function. *)
1405 let _ = PassManager.run_function the_function the_fpm in
1406
1407 the_function
1408 with e -&gt;
1409 delete_function the_function;
1410 raise e
1411</pre>
1412</dd>
1413
1414<dt>toplevel.ml:</dt>
1415<dd class="doc_code">
1416<pre>
1417(*===----------------------------------------------------------------------===
1418 * Top-Level parsing and JIT Driver
1419 *===----------------------------------------------------------------------===*)
1420
1421open Llvm
1422open Llvm_executionengine
1423
1424(* top ::= definition | external | expression | ';' *)
1425let rec main_loop the_fpm the_execution_engine stream =
1426 match Stream.peek stream with
1427 | None -&gt; ()
1428
1429 (* ignore top-level semicolons. *)
1430 | Some (Token.Kwd ';') -&gt;
1431 Stream.junk stream;
1432 main_loop the_fpm the_execution_engine stream
1433
1434 | Some token -&gt;
1435 begin
1436 try match token with
1437 | Token.Def -&gt;
1438 let e = Parser.parse_definition stream in
1439 print_endline "parsed a function definition.";
1440 dump_value (Codegen.codegen_func the_fpm e);
1441 | Token.Extern -&gt;
1442 let e = Parser.parse_extern stream in
1443 print_endline "parsed an extern.";
1444 dump_value (Codegen.codegen_proto e);
1445 | _ -&gt;
1446 (* Evaluate a top-level expression into an anonymous function. *)
1447 let e = Parser.parse_toplevel stream in
1448 print_endline "parsed a top-level expr";
1449 let the_function = Codegen.codegen_func the_fpm e in
1450 dump_value the_function;
1451
1452 (* JIT the function, returning a function pointer. *)
1453 let result = ExecutionEngine.run_function the_function [||]
1454 the_execution_engine in
1455
1456 print_string "Evaluated to ";
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +00001457 print_float (GenericValue.as_float Codegen.double_type result);
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001458 print_newline ();
1459 with Stream.Error s | Codegen.Error s -&gt;
1460 (* Skip token for error recovery. *)
1461 Stream.junk stream;
1462 print_endline s;
1463 end;
1464 print_string "ready&gt; "; flush stdout;
1465 main_loop the_fpm the_execution_engine stream
1466</pre>
1467</dd>
1468
1469<dt>toy.ml:</dt>
1470<dd class="doc_code">
1471<pre>
1472(*===----------------------------------------------------------------------===
1473 * Main driver code.
1474 *===----------------------------------------------------------------------===*)
1475
1476open Llvm
1477open Llvm_executionengine
1478open Llvm_target
1479open Llvm_scalar_opts
1480
1481let main () =
Erick Tryzelaar46262682009-09-14 21:54:32 +00001482 ignore (initialize_native_target ());
1483
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001484 (* Install standard binary operators.
1485 * 1 is the lowest precedence. *)
1486 Hashtbl.add Parser.binop_precedence '&lt;' 10;
1487 Hashtbl.add Parser.binop_precedence '+' 20;
1488 Hashtbl.add Parser.binop_precedence '-' 20;
1489 Hashtbl.add Parser.binop_precedence '*' 40; (* highest. *)
1490
1491 (* Prime the first token. *)
1492 print_string "ready&gt; "; flush stdout;
1493 let stream = Lexer.lex (Stream.of_channel stdin) in
1494
1495 (* Create the JIT. *)
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +00001496 let the_execution_engine = ExecutionEngine.create Codegen.the_module in
1497 let the_fpm = PassManager.create_function Codegen.the_module in
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001498
1499 (* Set up the optimizer pipeline. Start with registering info about how the
1500 * target lays out data structures. *)
1501 TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
1502
1503 (* Do simple "peephole" optimizations and bit-twiddling optzn. *)
Erick Tryzelaar9ef76b92010-03-08 19:32:18 +00001504 add_instruction_combination the_fpm;
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001505
1506 (* reassociate expressions. *)
1507 add_reassociation the_fpm;
1508
1509 (* Eliminate Common SubExpressions. *)
1510 add_gvn the_fpm;
1511
1512 (* Simplify the control flow graph (deleting unreachable blocks, etc). *)
1513 add_cfg_simplification the_fpm;
1514
Erick Tryzelaar126d86b2009-09-14 21:54:15 +00001515 ignore (PassManager.initialize the_fpm);
1516
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001517 (* Run the main "interpreter loop" now. *)
1518 Toplevel.main_loop the_fpm the_execution_engine stream;
1519
1520 (* Print out all the generated code. *)
1521 dump_module Codegen.the_module
1522;;
1523
1524main ()
1525</pre>
1526</dd>
1527
1528<dt>bindings.c</dt>
1529<dd class="doc_code">
1530<pre>
1531#include &lt;stdio.h&gt;
1532
1533/* putchard - putchar that takes a double and returns 0. */
1534extern double putchard(double X) {
1535 putchar((char)X);
1536 return 0;
1537}
1538</pre>
1539</dd>
1540</dl>
1541
1542<a href="OCamlLangImpl6.html">Next: Extending the language: user-defined
1543operators</a>
1544</div>
1545
1546<!-- *********************************************************************** -->
1547<hr>
1548<address>
1549 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1550 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1551 <a href="http://validator.w3.org/check/referer"><img
1552 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1553
1554 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1555 <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br>
NAKAMURA Takumib9a33632011-04-09 02:13:37 +00001556 <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
Dan Gohman523e3922010-02-03 17:27:31 +00001557 Last modified: $Date$
Erick Tryzelaar35295ff2008-03-31 08:44:50 +00001558</address>
1559</body>
1560</html>