Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / 43f51aeca8367ea35adad963c00bd2bc5b8d1391 / . / docs / tutorial / LangImpl5.html
blob: e46ded13ae53cd1a10fa5ac1ac6d1c3bd91df2e2 [file] [log] [blame]
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]1<!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 <link rel="stylesheet" href="../llvm.css" type="text/css">
10</head>
11
12<body>
13
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]14<h1>Kaleidoscope: Extending the Language: Control Flow</h1>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]15
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]16<ul>
Chris Lattner0e555b12007-11-05 20:04:56 +0000[diff] [blame]17<li><a href="index.html">Up to Tutorial Index</a></li>
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]18<li>Chapter 5
19 <ol>
20 <li><a href="#intro">Chapter 5 Introduction</a></li>
21 <li><a href="#ifthen">If/Then/Else</a>
22 <ol>
23 <li><a href="#iflexer">Lexer Extensions</a></li>
24 <li><a href="#ifast">AST Extensions</a></li>
25 <li><a href="#ifparser">Parser Extensions</a></li>
26 <li><a href="#ifir">LLVM IR</a></li>
27 <li><a href="#ifcodegen">Code Generation</a></li>
28 </ol>
29 </li>
30 <li><a href="#for">'for' Loop Expression</a>
31 <ol>
32 <li><a href="#forlexer">Lexer Extensions</a></li>
33 <li><a href="#forast">AST Extensions</a></li>
34 <li><a href="#forparser">Parser Extensions</a></li>
35 <li><a href="#forir">LLVM IR</a></li>
36 <li><a href="#forcodegen">Code Generation</a></li>
37 </ol>
38 </li>
39 <li><a href="#code">Full Code Listing</a></li>
40 </ol>
41</li>
Chris Lattner0e555b12007-11-05 20:04:56 +0000[diff] [blame]42<li><a href="LangImpl6.html">Chapter 6</a>: Extending the Language:
43User-defined Operators</li>
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]44</ul>
45
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]46<div class="doc_author">
47 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
48</div>
49
50<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]51<h2><a name="intro">Chapter 5 Introduction</a></h2>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]52<!-- *********************************************************************** -->
53
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]54<div>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]55
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]56<p>Welcome to Chapter 5 of the "<a href="index.html">Implementing a language
57with LLVM</a>" tutorial. Parts 1-4 described the implementation of the simple
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]58Kaleidoscope language and included support for generating LLVM IR, followed by
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]59optimizations and a JIT compiler. Unfortunately, as presented, Kaleidoscope is
60mostly useless: it has no control flow other than call and return. This means
61that you can't have conditional branches in the code, significantly limiting its
62power. In this episode of "build that compiler", we'll extend Kaleidoscope to
Chris Lattner1092a962007-11-07 05:47:48 +0000[diff] [blame]63have an if/then/else expression plus a simple 'for' loop.</p>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]64
65</div>
66
67<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]68<h2><a name="ifthen">If/Then/Else</a></h2>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]69<!-- *********************************************************************** -->
70
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]71<div>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]72
73<p>
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]74Extending Kaleidoscope to support if/then/else is quite straightforward. It
Duncan Sands60c8bf52011-02-27 13:54:01 +0000[diff] [blame]75basically requires adding support for this "new" concept to the lexer,
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]76parser, AST, and LLVM code emitter. This example is nice, because it shows how
77easy it is to "grow" a language over time, incrementally extending it as new
78ideas are discovered.</p>
79
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]80<p>Before we get going on "how" we add this extension, lets talk about "what" we
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]81want. The basic idea is that we want to be able to write this sort of thing:
82</p>
83
84<div class="doc_code">
85<pre>
86def fib(x)
87 if x &lt; 3 then
88 1
89 else
90 fib(x-1)+fib(x-2);
91</pre>
92</div>
93
94<p>In Kaleidoscope, every construct is an expression: there are no statements.
95As such, the if/then/else expression needs to return a value like any other.
96Since we're using a mostly functional form, we'll have it evaluate its
97conditional, then return the 'then' or 'else' value based on how the condition
98was resolved. This is very similar to the C "?:" expression.</p>
99
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]100<p>The semantics of the if/then/else expression is that it evaluates the
Chris Lattner1092a962007-11-07 05:47:48 +0000[diff] [blame]101condition to a boolean equality value: 0.0 is considered to be false and
102everything else is considered to be true.
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]103If the condition is true, the first subexpression is evaluated and returned, if
104the condition is false, the second subexpression is evaluated and returned.
105Since Kaleidoscope allows side-effects, this behavior is important to nail down.
106</p>
107
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]108<p>Now that we know what we "want", lets break this down into its constituent
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]109pieces.</p>
110
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]111<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]112<h4><a name="iflexer">Lexer Extensions for If/Then/Else</a></h4>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]113<!-- ======================================================================= -->
114
115
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]116<div>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]117
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]118<p>The lexer extensions are straightforward. First we add new enum values
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]119for the relevant tokens:</p>
120
121<div class="doc_code">
122<pre>
123 // control
124 tok_if = -6, tok_then = -7, tok_else = -8,
125</pre>
126</div>
127
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]128<p>Once we have that, we recognize the new keywords in the lexer. This is pretty simple
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]129stuff:</p>
130
131<div class="doc_code">
132<pre>
133 ...
134 if (IdentifierStr == "def") return tok_def;
135 if (IdentifierStr == "extern") return tok_extern;
136 <b>if (IdentifierStr == "if") return tok_if;
137 if (IdentifierStr == "then") return tok_then;
138 if (IdentifierStr == "else") return tok_else;</b>
139 return tok_identifier;
140</pre>
141</div>
142
143</div>
144
145<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]146<h4><a name="ifast">AST Extensions for If/Then/Else</a></h4>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]147<!-- ======================================================================= -->
148
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]149<div>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]150
151<p>To represent the new expression we add a new AST node for it:</p>
152
153<div class="doc_code">
154<pre>
155/// IfExprAST - Expression class for if/then/else.
156class IfExprAST : public ExprAST {
157 ExprAST *Cond, *Then, *Else;
158public:
159 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
160 : Cond(cond), Then(then), Else(_else) {}
161 virtual Value *Codegen();
162};
163</pre>
164</div>
165
166<p>The AST node just has pointers to the various subexpressions.</p>
167
168</div>
169
170<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]171<h4><a name="ifparser">Parser Extensions for If/Then/Else</a></h4>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]172<!-- ======================================================================= -->
173
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]174<div>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]175
176<p>Now that we have the relevant tokens coming from the lexer and we have the
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]177AST node to build, our parsing logic is relatively straightforward. First we
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]178define a new parsing function:</p>
179
180<div class="doc_code">
181<pre>
182/// ifexpr ::= 'if' expression 'then' expression 'else' expression
183static ExprAST *ParseIfExpr() {
184 getNextToken(); // eat the if.
185
186 // condition.
187 ExprAST *Cond = ParseExpression();
188 if (!Cond) return 0;
189
190 if (CurTok != tok_then)
191 return Error("expected then");
192 getNextToken(); // eat the then
193
194 ExprAST *Then = ParseExpression();
195 if (Then == 0) return 0;
196
197 if (CurTok != tok_else)
198 return Error("expected else");
199
200 getNextToken();
201
202 ExprAST *Else = ParseExpression();
203 if (!Else) return 0;
204
205 return new IfExprAST(Cond, Then, Else);
206}
207</pre>
208</div>
209
210<p>Next we hook it up as a primary expression:</p>
211
212<div class="doc_code">
213<pre>
214static ExprAST *ParsePrimary() {
215 switch (CurTok) {
216 default: return Error("unknown token when expecting an expression");
217 case tok_identifier: return ParseIdentifierExpr();
218 case tok_number: return ParseNumberExpr();
219 case '(': return ParseParenExpr();
220 <b>case tok_if: return ParseIfExpr();</b>
221 }
222}
223</pre>
224</div>
225
226</div>
227
228<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]229<h4><a name="ifir">LLVM IR for If/Then/Else</a></h4>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]230<!-- ======================================================================= -->
231
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]232<div>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]233
234<p>Now that we have it parsing and building the AST, the final piece is adding
235LLVM code generation support. This is the most interesting part of the
236if/then/else example, because this is where it starts to introduce new concepts.
Chris Lattner1092a962007-11-07 05:47:48 +0000[diff] [blame]237All of the code above has been thoroughly described in previous chapters.
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]238</p>
239
240<p>To motivate the code we want to produce, lets take a look at a simple
241example. Consider:</p>
242
243<div class="doc_code">
244<pre>
245extern foo();
246extern bar();
247def baz(x) if x then foo() else bar();
248</pre>
249</div>
250
251<p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
252looks like this:</p>
253
254<div class="doc_code">
255<pre>
256declare double @foo()
257
258declare double @bar()
259
260define double @baz(double %x) {
261entry:
262 %ifcond = fcmp one double %x, 0.000000e+00
263 br i1 %ifcond, label %then, label %else
264
265then: ; preds = %entry
266 %calltmp = call double @foo()
267 br label %ifcont
268
269else: ; preds = %entry
270 %calltmp1 = call double @bar()
271 br label %ifcont
272
273ifcont: ; preds = %else, %then
274 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
275 ret double %iftmp
276}
277</pre>
278</div>
279
280<p>To visualize the control flow graph, you can use a nifty feature of the LLVM
281'<a href="http://llvm.org/cmds/opt.html">opt</a>' tool. If you put this LLVM IR
282into "t.ll" and run "<tt>llvm-as &lt; t.ll | opt -analyze -view-cfg</tt>", <a
283href="../ProgrammersManual.html#ViewGraph">a window will pop up</a> and you'll
284see this graph:</p>
285
Benjamin Kramere15192b2009-08-05 15:42:44 +0000[diff] [blame]286<div style="text-align: center"><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
287height="315"></div>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]288
289<p>Another way to get this is to call "<tt>F-&gt;viewCFG()</tt>" or
290"<tt>F-&gt;viewCFGOnly()</tt>" (where F is a "<tt>Function*</tt>") either by
291inserting actual calls into the code and recompiling or by calling these in the
292debugger. LLVM has many nice features for visualizing various graphs.</p>
293
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]294<p>Getting back to the generated code, it is fairly simple: the entry block
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]295evaluates the conditional expression ("x" in our case here) and compares the
296result to 0.0 with the "<tt><a href="../LangRef.html#i_fcmp">fcmp</a> one</tt>"
Chris Lattner1092a962007-11-07 05:47:48 +0000[diff] [blame]297instruction ('one' is "Ordered and Not Equal"). Based on the result of this
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]298expression, the code jumps to either the "then" or "else" blocks, which contain
Chris Lattner1092a962007-11-07 05:47:48 +0000[diff] [blame]299the expressions for the true/false cases.</p>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]300
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]301<p>Once the then/else blocks are finished executing, they both branch back to the
Chris Lattner1092a962007-11-07 05:47:48 +0000[diff] [blame]302'ifcont' block to execute the code that happens after the if/then/else. In this
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]303case the only thing left to do is to return to the caller of the function. The
304question then becomes: how does the code know which expression to return?</p>
305
306<p>The answer to this question involves an important SSA operation: the
307<a href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Phi
308operation</a>. If you're not familiar with SSA, <a
309href="http://en.wikipedia.org/wiki/Static_single_assignment_form">the wikipedia
310article</a> is a good introduction and there are various other introductions to
311it available on your favorite search engine. The short version is that
312"execution" of the Phi operation requires "remembering" which block control came
313from. The Phi operation takes on the value corresponding to the input control
314block. In this case, if control comes in from the "then" block, it gets the
315value of "calltmp". If control comes from the "else" block, it gets the value
316of "calltmp1".</p>
317
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]318<p>At this point, you are probably starting to think "Oh no! This means my
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]319simple and elegant front-end will have to start generating SSA form in order to
320use LLVM!". Fortunately, this is not the case, and we strongly advise
321<em>not</em> implementing an SSA construction algorithm in your front-end
322unless there is an amazingly good reason to do so. In practice, there are two
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]323sorts of values that float around in code written for your average imperative
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]324programming language that might need Phi nodes:</p>
325
326<ol>
327<li>Code that involves user variables: <tt>x = 1; x = x + 1; </tt></li>
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]328<li>Values that are implicit in the structure of your AST, such as the Phi node
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]329in this case.</li>
330</ol>
331
Chris Lattnerb0f0deb2007-11-05 07:02:49 +0000[diff] [blame]332<p>In <a href="LangImpl7.html">Chapter 7</a> of this tutorial ("mutable
333variables"), we'll talk about #1
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]334in depth. For now, just believe me that you don't need SSA construction to
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]335handle this case. For #2, you have the choice of using the techniques that we will
336describe for #1, or you can insert Phi nodes directly, if convenient. In this
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]337case, it is really really easy to generate the Phi node, so we choose to do it
338directly.</p>
339
340<p>Okay, enough of the motivation and overview, lets generate code!</p>
341
342</div>
343
344<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]345<h4><a name="ifcodegen">Code Generation for If/Then/Else</a></h4>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]346<!-- ======================================================================= -->
347
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]348<div>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]349
350<p>In order to generate code for this, we implement the <tt>Codegen</tt> method
351for <tt>IfExprAST</tt>:</p>
352
353<div class="doc_code">
354<pre>
355Value *IfExprAST::Codegen() {
356 Value *CondV = Cond-&gt;Codegen();
357 if (CondV == 0) return 0;
358
359 // Convert condition to a bool by comparing equal to 0.0.
360 CondV = Builder.CreateFCmpONE(CondV,
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]361 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]362 "ifcond");
363</pre>
364</div>
365
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]366<p>This code is straightforward and similar to what we saw before. We emit the
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]367expression for the condition, then compare that value to zero to get a truth
368value as a 1-bit (bool) value.</p>
369
370<div class="doc_code">
371<pre>
372 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
373
374 // Create blocks for the then and else cases. Insert the 'then' block at the
375 // end of the function.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]376 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
377 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
378 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]379
380 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
381</pre>
382</div>
383
384<p>This code creates the basic blocks that are related to the if/then/else
385statement, and correspond directly to the blocks in the example above. The
Chris Lattner1092a962007-11-07 05:47:48 +0000[diff] [blame]386first line gets the current Function object that is being built. It
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]387gets this by asking the builder for the current BasicBlock, and asking that
388block for its "parent" (the function it is currently embedded into).</p>
389
390<p>Once it has that, it creates three blocks. Note that it passes "TheFunction"
391into the constructor for the "then" block. This causes the constructor to
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]392automatically insert the new block into the end of the specified function. The
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]393other two blocks are created, but aren't yet inserted into the function.</p>
394
395<p>Once the blocks are created, we can emit the conditional branch that chooses
396between them. Note that creating new blocks does not implicitly affect the
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]397IRBuilder, so it is still inserting into the block that the condition
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]398went into. Also note that it is creating a branch to the "then" block and the
399"else" block, even though the "else" block isn't inserted into the function yet.
400This is all ok: it is the standard way that LLVM supports forward
401references.</p>
402
403<div class="doc_code">
404<pre>
405 // Emit then value.
406 Builder.SetInsertPoint(ThenBB);
407
408 Value *ThenV = Then-&gt;Codegen();
409 if (ThenV == 0) return 0;
410
411 Builder.CreateBr(MergeBB);
412 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
413 ThenBB = Builder.GetInsertBlock();
414</pre>
415</div>
416
417<p>After the conditional branch is inserted, we move the builder to start
418inserting into the "then" block. Strictly speaking, this call moves the
419insertion point to be at the end of the specified block. However, since the
420"then" block is empty, it also starts out by inserting at the beginning of the
421block. :)</p>
422
423<p>Once the insertion point is set, we recursively codegen the "then" expression
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]424from the AST. To finish off the "then" block, we create an unconditional branch
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]425to the merge block. One interesting (and very important) aspect of the LLVM IR
426is that it <a href="../LangRef.html#functionstructure">requires all basic blocks
427to be "terminated"</a> with a <a href="../LangRef.html#terminators">control flow
428instruction</a> such as return or branch. This means that all control flow,
429<em>including fall throughs</em> must be made explicit in the LLVM IR. If you
430violate this rule, the verifier will emit an error.</p>
431
432<p>The final line here is quite subtle, but is very important. The basic issue
433is that when we create the Phi node in the merge block, we need to set up the
434block/value pairs that indicate how the Phi will work. Importantly, the Phi
Chris Lattnerb5019642007-11-05 17:52:04 +0000[diff] [blame]435node expects to have an entry for each predecessor of the block in the CFG. Why
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]436then, are we getting the current block when we just set it to ThenBB 5 lines
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]437above? The problem is that the "Then" expression may actually itself change the
438block that the Builder is emitting into if, for example, it contains a nested
439"if/then/else" expression. Because calling Codegen recursively could
440arbitrarily change the notion of the current block, we are required to get an
441up-to-date value for code that will set up the Phi node.</p>
442
443<div class="doc_code">
444<pre>
445 // Emit else block.
446 TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
447 Builder.SetInsertPoint(ElseBB);
448
449 Value *ElseV = Else-&gt;Codegen();
450 if (ElseV == 0) return 0;
451
452 Builder.CreateBr(MergeBB);
453 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
454 ElseBB = Builder.GetInsertBlock();
455</pre>
456</div>
457
458<p>Code generation for the 'else' block is basically identical to codegen for
459the 'then' block. The only significant difference is the first line, which adds
460the 'else' block to the function. Recall previously that the 'else' block was
461created, but not added to the function. Now that the 'then' and 'else' blocks
462are emitted, we can finish up with the merge code:</p>
463
464<div class="doc_code">
465<pre>
466 // Emit merge block.
467 TheFunction->getBasicBlockList().push_back(MergeBB);
468 Builder.SetInsertPoint(MergeBB);
Jay Foad3ecfc862011-03-30 11:28:46 +0000[diff] [blame]469 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]470 "iftmp");
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]471
472 PN->addIncoming(ThenV, ThenBB);
473 PN->addIncoming(ElseV, ElseBB);
474 return PN;
475}
476</pre>
477</div>
478
479<p>The first two lines here are now familiar: the first adds the "merge" block
480to the Function object (it was previously floating, like the else block above).
481The second block changes the insertion point so that newly created code will go
482into the "merge" block. Once that is done, we need to create the PHI node and
483set up the block/value pairs for the PHI.</p>
484
485<p>Finally, the CodeGen function returns the phi node as the value computed by
486the if/then/else expression. In our example above, this returned value will
487feed into the code for the top-level function, which will create the return
488instruction.</p>
489
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]490<p>Overall, we now have the ability to execute conditional code in
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]491Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
492that can calculate a wide variety of numeric functions. Next up we'll add
493another useful expression that is familiar from non-functional languages...</p>
494
495</div>
496
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]497</div>
498
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]499<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]500<h2><a name="for">'for' Loop Expression</a></h2>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]501<!-- *********************************************************************** -->
502
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]503<div>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]504
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]505<p>Now that we know how to add basic control flow constructs to the language,
506we have the tools to add more powerful things. Lets add something more
507aggressive, a 'for' expression:</p>
508
509<div class="doc_code">
510<pre>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]511 extern putchard(char)
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]512 def printstar(n)
513 for i = 1, i &lt; n, 1.0 in
514 putchard(42); # ascii 42 = '*'
515
516 # print 100 '*' characters
517 printstar(100);
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]518</pre>
519</div>
520
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]521<p>This expression defines a new variable ("i" in this case) which iterates from
522a starting value, while the condition ("i &lt; n" in this case) is true,
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]523incrementing by an optional step value ("1.0" in this case). If the step value
524is omitted, it defaults to 1.0. While the loop is true, it executes its
525body expression. Because we don't have anything better to return, we'll just
526define the loop as always returning 0.0. In the future when we have mutable
527variables, it will get more useful.</p>
528
529<p>As before, lets talk about the changes that we need to Kaleidoscope to
530support this.</p>
531
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]532<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]533<h4><a name="forlexer">Lexer Extensions for the 'for' Loop</a></h4>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]534<!-- ======================================================================= -->
535
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]536<div>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]537
538<p>The lexer extensions are the same sort of thing as for if/then/else:</p>
539
540<div class="doc_code">
541<pre>
542 ... in enum Token ...
543 // control
544 tok_if = -6, tok_then = -7, tok_else = -8,
545<b> tok_for = -9, tok_in = -10</b>
546
547 ... in gettok ...
548 if (IdentifierStr == "def") return tok_def;
549 if (IdentifierStr == "extern") return tok_extern;
550 if (IdentifierStr == "if") return tok_if;
551 if (IdentifierStr == "then") return tok_then;
552 if (IdentifierStr == "else") return tok_else;
553 <b>if (IdentifierStr == "for") return tok_for;
554 if (IdentifierStr == "in") return tok_in;</b>
555 return tok_identifier;
556</pre>
557</div>
558
559</div>
560
561<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]562<h4><a name="forast">AST Extensions for the 'for' Loop</a></h4>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]563<!-- ======================================================================= -->
564
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]565<div>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]566
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]567<p>The AST node is just as simple. It basically boils down to capturing
Chris Lattner1092a962007-11-07 05:47:48 +0000[diff] [blame]568the variable name and the constituent expressions in the node.</p>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]569
570<div class="doc_code">
571<pre>
572/// ForExprAST - Expression class for for/in.
573class ForExprAST : public ExprAST {
574 std::string VarName;
575 ExprAST *Start, *End, *Step, *Body;
576public:
577 ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
578 ExprAST *step, ExprAST *body)
579 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
580 virtual Value *Codegen();
581};
582</pre>
583</div>
584
585</div>
586
587<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]588<h4><a name="forparser">Parser Extensions for the 'for' Loop</a></h4>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]589<!-- ======================================================================= -->
590
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]591<div>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]592
593<p>The parser code is also fairly standard. The only interesting thing here is
594handling of the optional step value. The parser code handles it by checking to
595see if the second comma is present. If not, it sets the step value to null in
596the AST node:</p>
597
598<div class="doc_code">
599<pre>
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]600/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]601static ExprAST *ParseForExpr() {
602 getNextToken(); // eat the for.
603
604 if (CurTok != tok_identifier)
605 return Error("expected identifier after for");
606
607 std::string IdName = IdentifierStr;
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]608 getNextToken(); // eat identifier.
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]609
610 if (CurTok != '=')
611 return Error("expected '=' after for");
612 getNextToken(); // eat '='.
613
614
615 ExprAST *Start = ParseExpression();
616 if (Start == 0) return 0;
617 if (CurTok != ',')
618 return Error("expected ',' after for start value");
619 getNextToken();
620
621 ExprAST *End = ParseExpression();
622 if (End == 0) return 0;
623
624 // The step value is optional.
625 ExprAST *Step = 0;
626 if (CurTok == ',') {
627 getNextToken();
628 Step = ParseExpression();
629 if (Step == 0) return 0;
630 }
631
632 if (CurTok != tok_in)
633 return Error("expected 'in' after for");
634 getNextToken(); // eat 'in'.
635
636 ExprAST *Body = ParseExpression();
637 if (Body == 0) return 0;
638
639 return new ForExprAST(IdName, Start, End, Step, Body);
640}
641</pre>
642</div>
643
644</div>
645
646<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]647<h4><a name="forir">LLVM IR for the 'for' Loop</a></h4>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]648<!-- ======================================================================= -->
649
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]650<div>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]651
652<p>Now we get to the good part: the LLVM IR we want to generate for this thing.
Gordon Henriksenbb310f12007-11-12 13:46:21 +0000[diff] [blame]653With the simple example above, we get this LLVM IR (note that this dump is
654generated with optimizations disabled for clarity):
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]655</p>
656
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]657<div class="doc_code">
658<pre>
659declare double @putchard(double)
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]660
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]661define double @printstar(double %n) {
662entry:
663 ; initial value = 1.0 (inlined into phi)
664 br label %loop
665
666loop: ; preds = %loop, %entry
667 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
668 ; body
Dan Gohman3dfb3cf2010-05-28 17:07:41 +0000[diff] [blame]669 %calltmp = call double @putchard(double 4.200000e+01)
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]670 ; increment
Dan Gohmana9445e12010-03-02 01:11:08 +0000[diff] [blame]671 %nextvar = fadd double %i, 1.000000e+00
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]672
673 ; termination test
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]674 %cmptmp = fcmp ult double %i, %n
675 %booltmp = uitofp i1 %cmptmp to double
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]676 %loopcond = fcmp one double %booltmp, 0.000000e+00
677 br i1 %loopcond, label %loop, label %afterloop
678
679afterloop: ; preds = %loop
680 ; loop always returns 0.0
681 ret double 0.000000e+00
682}
683</pre>
684</div>
685
686<p>This loop contains all the same constructs we saw before: a phi node, several
687expressions, and some basic blocks. Lets see how this fits together.</p>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]688
689</div>
690
691<!-- ======================================================================= -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]692<h4><a name="forcodegen">Code Generation for the 'for' Loop</a></h4>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]693<!-- ======================================================================= -->
694
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]695<div>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]696
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]697<p>The first part of Codegen is very simple: we just output the start expression
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]698for the loop value:</p>
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]699
700<div class="doc_code">
701<pre>
702Value *ForExprAST::Codegen() {
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]703 // Emit the start code first, without 'variable' in scope.
704 Value *StartVal = Start-&gt;Codegen();
705 if (StartVal == 0) return 0;
706</pre>
707</div>
708
709<p>With this out of the way, the next step is to set up the LLVM basic block
710for the start of the loop body. In the case above, the whole loop body is one
711block, but remember that the body code itself could consist of multiple blocks
Chris Lattner1092a962007-11-07 05:47:48 +0000[diff] [blame]712(e.g. if it contains an if/then/else or a for/in expression).</p>
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]713
714<div class="doc_code">
715<pre>
716 // Make the new basic block for the loop header, inserting after current
717 // block.
718 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
719 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]720 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]721
722 // Insert an explicit fall through from the current block to the LoopBB.
723 Builder.CreateBr(LoopBB);
724</pre>
725</div>
726
727<p>This code is similar to what we saw for if/then/else. Because we will need
728it to create the Phi node, we remember the block that falls through into the
729loop. Once we have that, we create the actual block that starts the loop and
730create an unconditional branch for the fall-through between the two blocks.</p>
731
732<div class="doc_code">
733<pre>
734 // Start insertion in LoopBB.
735 Builder.SetInsertPoint(LoopBB);
736
737 // Start the PHI node with an entry for Start.
Jay Foad3ecfc862011-03-30 11:28:46 +0000[diff] [blame]738 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]739 Variable-&gt;addIncoming(StartVal, PreheaderBB);
740</pre>
741</div>
742
743<p>Now that the "preheader" for the loop is set up, we switch to emitting code
744for the loop body. To begin with, we move the insertion point and create the
Chris Lattner1092a962007-11-07 05:47:48 +0000[diff] [blame]745PHI node for the loop induction variable. Since we already know the incoming
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]746value for the starting value, we add it to the Phi node. Note that the Phi will
747eventually get a second value for the backedge, but we can't set it up yet
748(because it doesn't exist!).</p>
749
750<div class="doc_code">
751<pre>
752 // Within the loop, the variable is defined equal to the PHI node. If it
753 // shadows an existing variable, we have to restore it, so save it now.
754 Value *OldVal = NamedValues[VarName];
755 NamedValues[VarName] = Variable;
756
757 // Emit the body of the loop. This, like any other expr, can change the
758 // current BB. Note that we ignore the value computed by the body, but don't
759 // allow an error.
760 if (Body-&gt;Codegen() == 0)
761 return 0;
762</pre>
763</div>
764
765<p>Now the code starts to get more interesting. Our 'for' loop introduces a new
766variable to the symbol table. This means that our symbol table can now contain
767either function arguments or loop variables. To handle this, before we codegen
768the body of the loop, we add the loop variable as the current value for its
769name. Note that it is possible that there is a variable of the same name in the
770outer scope. It would be easy to make this an error (emit an error and return
771null if there is already an entry for VarName) but we choose to allow shadowing
772of variables. In order to handle this correctly, we remember the Value that
773we are potentially shadowing in <tt>OldVal</tt> (which will be null if there is
774no shadowed variable).</p>
775
776<p>Once the loop variable is set into the symbol table, the code recursively
777codegen's the body. This allows the body to use the loop variable: any
778references to it will naturally find it in the symbol table.</p>
779
780<div class="doc_code">
781<pre>
782 // Emit the step value.
783 Value *StepVal;
784 if (Step) {
785 StepVal = Step-&gt;Codegen();
786 if (StepVal == 0) return 0;
787 } else {
788 // If not specified, use 1.0.
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]789 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]790 }
791
Chris Lattnerf57fcf72010-09-01 20:09:20 +0000[diff] [blame]792 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]793</pre>
794</div>
795
796<p>Now that the body is emitted, we compute the next value of the iteration
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]797variable by adding the step value, or 1.0 if it isn't present. '<tt>NextVar</tt>'
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]798will be the value of the loop variable on the next iteration of the loop.</p>
799
800<div class="doc_code">
801<pre>
802 // Compute the end condition.
803 Value *EndCond = End-&gt;Codegen();
804 if (EndCond == 0) return EndCond;
805
806 // Convert condition to a bool by comparing equal to 0.0.
807 EndCond = Builder.CreateFCmpONE(EndCond,
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]808 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]809 "loopcond");
810</pre>
811</div>
812
813<p>Finally, we evaluate the exit value of the loop, to determine whether the
814loop should exit. This mirrors the condition evaluation for the if/then/else
815statement.</p>
816
817<div class="doc_code">
818<pre>
819 // Create the "after loop" block and insert it.
820 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]821 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]822
823 // Insert the conditional branch into the end of LoopEndBB.
824 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
825
826 // Any new code will be inserted in AfterBB.
827 Builder.SetInsertPoint(AfterBB);
828</pre>
829</div>
830
831<p>With the code for the body of the loop complete, we just need to finish up
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]832the 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
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]833exit condition, it creates a conditional branch that chooses between executing
834the loop again and exiting the loop. Any future code is emitted in the
835"afterloop" block, so it sets the insertion position to it.</p>
836
837<div class="doc_code">
838<pre>
839 // Add a new entry to the PHI node for the backedge.
840 Variable-&gt;addIncoming(NextVar, LoopEndBB);
841
842 // Restore the unshadowed variable.
843 if (OldVal)
844 NamedValues[VarName] = OldVal;
845 else
846 NamedValues.erase(VarName);
847
848 // for expr always returns 0.0.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]849 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]850}
851</pre>
852</div>
853
854<p>The final code handles various cleanups: now that we have the "NextVar"
855value, we can add the incoming value to the loop PHI node. After that, we
856remove the loop variable from the symbol table, so that it isn't in scope after
857the for loop. Finally, code generation of the for loop always returns 0.0, so
858that is what we return from <tt>ForExprAST::Codegen</tt>.</p>
859
860<p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]861the tutorial. In this chapter we added two control flow constructs, and used them to motivate a couple of aspects of the LLVM IR that are important for front-end implementors
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]862to know. In the next chapter of our saga, we will get a bit crazier and add
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]863<a href="LangImpl6.html">user-defined operators</a> to our poor innocent
864language.</p>
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]865
866</div>
867
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]868</div>
869
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]870<!-- *********************************************************************** -->
NAKAMURA Takumi05d02652011-04-18 23:59:50 +0000[diff] [blame]871<h2><a name="code">Full Code Listing</a></h2>
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]872<!-- *********************************************************************** -->
873
NAKAMURA Takumif5af6ad2011-04-23 00:30:22 +0000[diff] [blame]874<div>
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]875
876<p>
877Here is the complete code listing for our running example, enhanced with the
878if/then/else and for expressions.. To build this example, use:
879</p>
880
881<div class="doc_code">
882<pre>
883 # Compile
884 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
885 # Run
886 ./toy
887</pre>
888</div>
889
890<p>Here is the code:</p>
891
892<div class="doc_code">
893<pre>
894#include "llvm/DerivedTypes.h"
895#include "llvm/ExecutionEngine/ExecutionEngine.h"
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]896#include "llvm/ExecutionEngine/JIT.h"
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]897#include "llvm/LLVMContext.h"
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]898#include "llvm/Module.h"
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]899#include "llvm/PassManager.h"
900#include "llvm/Analysis/Verifier.h"
Dan Gohmanab7fa082010-11-16 17:28:22 +0000[diff] [blame]901#include "llvm/Analysis/Passes.h"
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]902#include "llvm/Target/TargetData.h"
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]903#include "llvm/Target/TargetSelect.h"
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]904#include "llvm/Transforms/Scalar.h"
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]905#include "llvm/Support/IRBuilder.h"
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]906#include &lt;cstdio&gt;
907#include &lt;string&gt;
908#include &lt;map&gt;
909#include &lt;vector&gt;
910using namespace llvm;
911
912//===----------------------------------------------------------------------===//
913// Lexer
914//===----------------------------------------------------------------------===//
915
916// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
917// of these for known things.
918enum Token {
919 tok_eof = -1,
920
921 // commands
922 tok_def = -2, tok_extern = -3,
923
924 // primary
925 tok_identifier = -4, tok_number = -5,
926
927 // control
928 tok_if = -6, tok_then = -7, tok_else = -8,
929 tok_for = -9, tok_in = -10
930};
931
932static std::string IdentifierStr; // Filled in if tok_identifier
933static double NumVal; // Filled in if tok_number
934
935/// gettok - Return the next token from standard input.
936static int gettok() {
937 static int LastChar = ' ';
938
939 // Skip any whitespace.
940 while (isspace(LastChar))
941 LastChar = getchar();
942
943 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
944 IdentifierStr = LastChar;
945 while (isalnum((LastChar = getchar())))
946 IdentifierStr += LastChar;
947
948 if (IdentifierStr == "def") return tok_def;
949 if (IdentifierStr == "extern") return tok_extern;
950 if (IdentifierStr == "if") return tok_if;
951 if (IdentifierStr == "then") return tok_then;
952 if (IdentifierStr == "else") return tok_else;
953 if (IdentifierStr == "for") return tok_for;
954 if (IdentifierStr == "in") return tok_in;
955 return tok_identifier;
956 }
957
958 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
959 std::string NumStr;
960 do {
961 NumStr += LastChar;
962 LastChar = getchar();
963 } while (isdigit(LastChar) || LastChar == '.');
964
965 NumVal = strtod(NumStr.c_str(), 0);
966 return tok_number;
967 }
968
969 if (LastChar == '#') {
970 // Comment until end of line.
971 do LastChar = getchar();
Chris Lattnerc80c23f2007-12-02 22:46:01 +0000[diff] [blame]972 while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]973
974 if (LastChar != EOF)
975 return gettok();
976 }
977
978 // Check for end of file. Don't eat the EOF.
979 if (LastChar == EOF)
980 return tok_eof;
981
982 // Otherwise, just return the character as its ascii value.
983 int ThisChar = LastChar;
984 LastChar = getchar();
985 return ThisChar;
986}
987
988//===----------------------------------------------------------------------===//
989// Abstract Syntax Tree (aka Parse Tree)
990//===----------------------------------------------------------------------===//
991
992/// ExprAST - Base class for all expression nodes.
993class ExprAST {
994public:
995 virtual ~ExprAST() {}
996 virtual Value *Codegen() = 0;
997};
998
999/// NumberExprAST - Expression class for numeric literals like "1.0".
1000class NumberExprAST : public ExprAST {
1001 double Val;
1002public:
1003 NumberExprAST(double val) : Val(val) {}
1004 virtual Value *Codegen();
1005};
1006
1007/// VariableExprAST - Expression class for referencing a variable, like "a".
1008class VariableExprAST : public ExprAST {
1009 std::string Name;
1010public:
1011 VariableExprAST(const std::string &amp;name) : Name(name) {}
1012 virtual Value *Codegen();
1013};
1014
1015/// BinaryExprAST - Expression class for a binary operator.
1016class BinaryExprAST : public ExprAST {
1017 char Op;
1018 ExprAST *LHS, *RHS;
1019public:
1020 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
1021 : Op(op), LHS(lhs), RHS(rhs) {}
1022 virtual Value *Codegen();
1023};
1024
1025/// CallExprAST - Expression class for function calls.
1026class CallExprAST : public ExprAST {
1027 std::string Callee;
1028 std::vector&lt;ExprAST*&gt; Args;
1029public:
1030 CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
1031 : Callee(callee), Args(args) {}
1032 virtual Value *Codegen();
1033};
1034
1035/// IfExprAST - Expression class for if/then/else.
1036class IfExprAST : public ExprAST {
1037 ExprAST *Cond, *Then, *Else;
1038public:
1039 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1040 : Cond(cond), Then(then), Else(_else) {}
1041 virtual Value *Codegen();
1042};
1043
1044/// ForExprAST - Expression class for for/in.
1045class ForExprAST : public ExprAST {
1046 std::string VarName;
1047 ExprAST *Start, *End, *Step, *Body;
1048public:
1049 ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
1050 ExprAST *step, ExprAST *body)
1051 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1052 virtual Value *Codegen();
1053};
1054
1055/// PrototypeAST - This class represents the "prototype" for a function,
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1056/// which captures its name, and its argument names (thus implicitly the number
1057/// of arguments the function takes).
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1058class PrototypeAST {
1059 std::string Name;
1060 std::vector&lt;std::string&gt; Args;
1061public:
1062 PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args)
1063 : Name(name), Args(args) {}
1064
1065 Function *Codegen();
1066};
1067
1068/// FunctionAST - This class represents a function definition itself.
1069class FunctionAST {
1070 PrototypeAST *Proto;
1071 ExprAST *Body;
1072public:
1073 FunctionAST(PrototypeAST *proto, ExprAST *body)
1074 : Proto(proto), Body(body) {}
1075
1076 Function *Codegen();
1077};
1078
1079//===----------------------------------------------------------------------===//
1080// Parser
1081//===----------------------------------------------------------------------===//
1082
1083/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1084/// token the parser is looking at. getNextToken reads another token from the
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1085/// lexer and updates CurTok with its results.
1086static int CurTok;
1087static int getNextToken() {
1088 return CurTok = gettok();
1089}
1090
1091/// BinopPrecedence - This holds the precedence for each binary operator that is
1092/// defined.
1093static std::map&lt;char, int&gt; BinopPrecedence;
1094
1095/// GetTokPrecedence - Get the precedence of the pending binary operator token.
1096static int GetTokPrecedence() {
1097 if (!isascii(CurTok))
1098 return -1;
1099
1100 // Make sure it's a declared binop.
1101 int TokPrec = BinopPrecedence[CurTok];
1102 if (TokPrec &lt;= 0) return -1;
1103 return TokPrec;
1104}
1105
1106/// Error* - These are little helper functions for error handling.
1107ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1108PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1109FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1110
1111static ExprAST *ParseExpression();
1112
1113/// identifierexpr
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1114/// ::= identifier
1115/// ::= identifier '(' expression* ')'
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1116static ExprAST *ParseIdentifierExpr() {
1117 std::string IdName = IdentifierStr;
1118
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1119 getNextToken(); // eat identifier.
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1120
1121 if (CurTok != '(') // Simple variable ref.
1122 return new VariableExprAST(IdName);
1123
1124 // Call.
1125 getNextToken(); // eat (
1126 std::vector&lt;ExprAST*&gt; Args;
1127 if (CurTok != ')') {
1128 while (1) {
1129 ExprAST *Arg = ParseExpression();
1130 if (!Arg) return 0;
1131 Args.push_back(Arg);
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1132
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1133 if (CurTok == ')') break;
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1134
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1135 if (CurTok != ',')
Chris Lattner6c4be9c2008-04-14 16:44:41 +0000[diff] [blame]1136 return Error("Expected ')' or ',' in argument list");
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1137 getNextToken();
1138 }
1139 }
1140
1141 // Eat the ')'.
1142 getNextToken();
1143
1144 return new CallExprAST(IdName, Args);
1145}
1146
1147/// numberexpr ::= number
1148static ExprAST *ParseNumberExpr() {
1149 ExprAST *Result = new NumberExprAST(NumVal);
1150 getNextToken(); // consume the number
1151 return Result;
1152}
1153
1154/// parenexpr ::= '(' expression ')'
1155static ExprAST *ParseParenExpr() {
1156 getNextToken(); // eat (.
1157 ExprAST *V = ParseExpression();
1158 if (!V) return 0;
1159
1160 if (CurTok != ')')
1161 return Error("expected ')'");
1162 getNextToken(); // eat ).
1163 return V;
1164}
1165
1166/// ifexpr ::= 'if' expression 'then' expression 'else' expression
1167static ExprAST *ParseIfExpr() {
1168 getNextToken(); // eat the if.
1169
1170 // condition.
1171 ExprAST *Cond = ParseExpression();
1172 if (!Cond) return 0;
1173
1174 if (CurTok != tok_then)
1175 return Error("expected then");
1176 getNextToken(); // eat the then
1177
1178 ExprAST *Then = ParseExpression();
1179 if (Then == 0) return 0;
1180
1181 if (CurTok != tok_else)
1182 return Error("expected else");
1183
1184 getNextToken();
1185
1186 ExprAST *Else = ParseExpression();
1187 if (!Else) return 0;
1188
1189 return new IfExprAST(Cond, Then, Else);
1190}
1191
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1192/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1193static ExprAST *ParseForExpr() {
1194 getNextToken(); // eat the for.
1195
1196 if (CurTok != tok_identifier)
1197 return Error("expected identifier after for");
1198
1199 std::string IdName = IdentifierStr;
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1200 getNextToken(); // eat identifier.
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1201
1202 if (CurTok != '=')
1203 return Error("expected '=' after for");
1204 getNextToken(); // eat '='.
1205
1206
1207 ExprAST *Start = ParseExpression();
1208 if (Start == 0) return 0;
1209 if (CurTok != ',')
1210 return Error("expected ',' after for start value");
1211 getNextToken();
1212
1213 ExprAST *End = ParseExpression();
1214 if (End == 0) return 0;
1215
1216 // The step value is optional.
1217 ExprAST *Step = 0;
1218 if (CurTok == ',') {
1219 getNextToken();
1220 Step = ParseExpression();
1221 if (Step == 0) return 0;
1222 }
1223
1224 if (CurTok != tok_in)
1225 return Error("expected 'in' after for");
1226 getNextToken(); // eat 'in'.
1227
1228 ExprAST *Body = ParseExpression();
1229 if (Body == 0) return 0;
1230
1231 return new ForExprAST(IdName, Start, End, Step, Body);
1232}
1233
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1234/// primary
1235/// ::= identifierexpr
1236/// ::= numberexpr
1237/// ::= parenexpr
1238/// ::= ifexpr
1239/// ::= forexpr
1240static ExprAST *ParsePrimary() {
1241 switch (CurTok) {
1242 default: return Error("unknown token when expecting an expression");
1243 case tok_identifier: return ParseIdentifierExpr();
1244 case tok_number: return ParseNumberExpr();
1245 case '(': return ParseParenExpr();
1246 case tok_if: return ParseIfExpr();
1247 case tok_for: return ParseForExpr();
1248 }
1249}
1250
1251/// binoprhs
1252/// ::= ('+' primary)*
1253static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1254 // If this is a binop, find its precedence.
1255 while (1) {
1256 int TokPrec = GetTokPrecedence();
1257
1258 // If this is a binop that binds at least as tightly as the current binop,
1259 // consume it, otherwise we are done.
1260 if (TokPrec &lt; ExprPrec)
1261 return LHS;
1262
1263 // Okay, we know this is a binop.
1264 int BinOp = CurTok;
1265 getNextToken(); // eat binop
1266
1267 // Parse the primary expression after the binary operator.
1268 ExprAST *RHS = ParsePrimary();
1269 if (!RHS) return 0;
1270
1271 // If BinOp binds less tightly with RHS than the operator after RHS, let
1272 // the pending operator take RHS as its LHS.
1273 int NextPrec = GetTokPrecedence();
1274 if (TokPrec &lt; NextPrec) {
1275 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1276 if (RHS == 0) return 0;
1277 }
1278
1279 // Merge LHS/RHS.
1280 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1281 }
1282}
1283
1284/// expression
1285/// ::= primary binoprhs
1286///
1287static ExprAST *ParseExpression() {
1288 ExprAST *LHS = ParsePrimary();
1289 if (!LHS) return 0;
1290
1291 return ParseBinOpRHS(0, LHS);
1292}
1293
1294/// prototype
1295/// ::= id '(' id* ')'
1296static PrototypeAST *ParsePrototype() {
1297 if (CurTok != tok_identifier)
1298 return ErrorP("Expected function name in prototype");
1299
1300 std::string FnName = IdentifierStr;
1301 getNextToken();
1302
1303 if (CurTok != '(')
1304 return ErrorP("Expected '(' in prototype");
1305
1306 std::vector&lt;std::string&gt; ArgNames;
1307 while (getNextToken() == tok_identifier)
1308 ArgNames.push_back(IdentifierStr);
1309 if (CurTok != ')')
1310 return ErrorP("Expected ')' in prototype");
1311
1312 // success.
1313 getNextToken(); // eat ')'.
1314
1315 return new PrototypeAST(FnName, ArgNames);
1316}
1317
1318/// definition ::= 'def' prototype expression
1319static FunctionAST *ParseDefinition() {
1320 getNextToken(); // eat def.
1321 PrototypeAST *Proto = ParsePrototype();
1322 if (Proto == 0) return 0;
1323
1324 if (ExprAST *E = ParseExpression())
1325 return new FunctionAST(Proto, E);
1326 return 0;
1327}
1328
1329/// toplevelexpr ::= expression
1330static FunctionAST *ParseTopLevelExpr() {
1331 if (ExprAST *E = ParseExpression()) {
1332 // Make an anonymous proto.
1333 PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
1334 return new FunctionAST(Proto, E);
1335 }
1336 return 0;
1337}
1338
1339/// external ::= 'extern' prototype
1340static PrototypeAST *ParseExtern() {
1341 getNextToken(); // eat extern.
1342 return ParsePrototype();
1343}
1344
1345//===----------------------------------------------------------------------===//
1346// Code Generation
1347//===----------------------------------------------------------------------===//
1348
1349static Module *TheModule;
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]1350static IRBuilder&lt;&gt; Builder(getGlobalContext());
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1351static std::map&lt;std::string, Value*&gt; NamedValues;
1352static FunctionPassManager *TheFPM;
1353
1354Value *ErrorV(const char *Str) { Error(Str); return 0; }
1355
1356Value *NumberExprAST::Codegen() {
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1357 return ConstantFP::get(getGlobalContext(), APFloat(Val));
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1358}
1359
1360Value *VariableExprAST::Codegen() {
1361 // Look this variable up in the function.
1362 Value *V = NamedValues[Name];
1363 return V ? V : ErrorV("Unknown variable name");
1364}
1365
1366Value *BinaryExprAST::Codegen() {
1367 Value *L = LHS-&gt;Codegen();
1368 Value *R = RHS-&gt;Codegen();
1369 if (L == 0 || R == 0) return 0;
1370
1371 switch (Op) {
Eric Christopher2214b812010-06-14 06:09:39 +0000[diff] [blame]1372 case '+': return Builder.CreateFAdd(L, R, "addtmp");
1373 case '-': return Builder.CreateFSub(L, R, "subtmp");
1374 case '*': return Builder.CreateFMul(L, R, "multmp");
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1375 case '&lt;':
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]1376 L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1377 // Convert bool 0/1 to double 0.0 or 1.0
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1378 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1379 "booltmp");
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1380 default: return ErrorV("invalid binary operator");
1381 }
1382}
1383
1384Value *CallExprAST::Codegen() {
1385 // Look up the name in the global module table.
1386 Function *CalleeF = TheModule-&gt;getFunction(Callee);
1387 if (CalleeF == 0)
1388 return ErrorV("Unknown function referenced");
1389
1390 // If argument mismatch error.
1391 if (CalleeF-&gt;arg_size() != Args.size())
1392 return ErrorV("Incorrect # arguments passed");
1393
1394 std::vector&lt;Value*&gt; ArgsV;
1395 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1396 ArgsV.push_back(Args[i]-&gt;Codegen());
1397 if (ArgsV.back() == 0) return 0;
1398 }
1399
1400 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1401}
1402
1403Value *IfExprAST::Codegen() {
1404 Value *CondV = Cond-&gt;Codegen();
1405 if (CondV == 0) return 0;
1406
1407 // Convert condition to a bool by comparing equal to 0.0.
1408 CondV = Builder.CreateFCmpONE(CondV,
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1409 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1410 "ifcond");
1411
1412 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1413
1414 // Create blocks for the then and else cases. Insert the 'then' block at the
1415 // end of the function.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1416 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1417 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1418 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1419
1420 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1421
1422 // Emit then value.
1423 Builder.SetInsertPoint(ThenBB);
1424
1425 Value *ThenV = Then-&gt;Codegen();
1426 if (ThenV == 0) return 0;
1427
1428 Builder.CreateBr(MergeBB);
1429 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1430 ThenBB = Builder.GetInsertBlock();
1431
1432 // Emit else block.
1433 TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
1434 Builder.SetInsertPoint(ElseBB);
1435
1436 Value *ElseV = Else-&gt;Codegen();
1437 if (ElseV == 0) return 0;
1438
1439 Builder.CreateBr(MergeBB);
1440 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1441 ElseBB = Builder.GetInsertBlock();
1442
1443 // Emit merge block.
1444 TheFunction-&gt;getBasicBlockList().push_back(MergeBB);
1445 Builder.SetInsertPoint(MergeBB);
Jay Foad3ecfc862011-03-30 11:28:46 +0000[diff] [blame]1446 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1447 "iftmp");
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1448
1449 PN-&gt;addIncoming(ThenV, ThenBB);
1450 PN-&gt;addIncoming(ElseV, ElseBB);
1451 return PN;
1452}
1453
1454Value *ForExprAST::Codegen() {
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1455 // Output this as:
1456 // ...
1457 // start = startexpr
1458 // goto loop
1459 // loop:
1460 // variable = phi [start, loopheader], [nextvariable, loopend]
1461 // ...
1462 // bodyexpr
1463 // ...
1464 // loopend:
1465 // step = stepexpr
1466 // nextvariable = variable + step
1467 // endcond = endexpr
1468 // br endcond, loop, endloop
1469 // outloop:
1470
1471 // Emit the start code first, without 'variable' in scope.
1472 Value *StartVal = Start-&gt;Codegen();
1473 if (StartVal == 0) return 0;
1474
1475 // Make the new basic block for the loop header, inserting after current
1476 // block.
1477 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1478 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1479 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1480
1481 // Insert an explicit fall through from the current block to the LoopBB.
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1482 Builder.CreateBr(LoopBB);
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1483
1484 // Start insertion in LoopBB.
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1485 Builder.SetInsertPoint(LoopBB);
1486
1487 // Start the PHI node with an entry for Start.
Jay Foad3ecfc862011-03-30 11:28:46 +0000[diff] [blame]1488 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1489 Variable-&gt;addIncoming(StartVal, PreheaderBB);
1490
1491 // Within the loop, the variable is defined equal to the PHI node. If it
1492 // shadows an existing variable, we have to restore it, so save it now.
1493 Value *OldVal = NamedValues[VarName];
1494 NamedValues[VarName] = Variable;
1495
1496 // Emit the body of the loop. This, like any other expr, can change the
1497 // current BB. Note that we ignore the value computed by the body, but don't
1498 // allow an error.
1499 if (Body-&gt;Codegen() == 0)
1500 return 0;
1501
1502 // Emit the step value.
1503 Value *StepVal;
1504 if (Step) {
1505 StepVal = Step-&gt;Codegen();
1506 if (StepVal == 0) return 0;
1507 } else {
1508 // If not specified, use 1.0.
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1509 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1510 }
1511
Chris Lattnerf57fcf72010-09-01 20:09:20 +0000[diff] [blame]1512 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1513
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1514 // Compute the end condition.
1515 Value *EndCond = End-&gt;Codegen();
1516 if (EndCond == 0) return EndCond;
1517
1518 // Convert condition to a bool by comparing equal to 0.0.
1519 EndCond = Builder.CreateFCmpONE(EndCond,
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1520 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1521 "loopcond");
1522
1523 // Create the "after loop" block and insert it.
1524 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1525 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1526
1527 // Insert the conditional branch into the end of LoopEndBB.
1528 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1529
1530 // Any new code will be inserted in AfterBB.
1531 Builder.SetInsertPoint(AfterBB);
1532
1533 // Add a new entry to the PHI node for the backedge.
1534 Variable-&gt;addIncoming(NextVar, LoopEndBB);
1535
1536 // Restore the unshadowed variable.
1537 if (OldVal)
1538 NamedValues[VarName] = OldVal;
1539 else
1540 NamedValues.erase(VarName);
1541
1542
1543 // for expr always returns 0.0.
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1544 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1545}
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1546
1547Function *PrototypeAST::Codegen() {
1548 // Make the function type: double(double,double) etc.
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1549 std::vector&lt;const Type*&gt; Doubles(Args.size(),
1550 Type::getDoubleTy(getGlobalContext()));
1551 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1552 Doubles, false);
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1553
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]1554 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1555
1556 // If F conflicted, there was already something named 'Name'. If it has a
1557 // body, don't allow redefinition or reextern.
1558 if (F-&gt;getName() != Name) {
1559 // Delete the one we just made and get the existing one.
1560 F-&gt;eraseFromParent();
1561 F = TheModule-&gt;getFunction(Name);
1562
1563 // If F already has a body, reject this.
1564 if (!F-&gt;empty()) {
1565 ErrorF("redefinition of function");
1566 return 0;
1567 }
1568
1569 // If F took a different number of args, reject.
1570 if (F-&gt;arg_size() != Args.size()) {
1571 ErrorF("redefinition of function with different # args");
1572 return 0;
1573 }
1574 }
1575
1576 // Set names for all arguments.
1577 unsigned Idx = 0;
1578 for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1579 ++AI, ++Idx) {
1580 AI-&gt;setName(Args[Idx]);
1581
1582 // Add arguments to variable symbol table.
1583 NamedValues[Args[Idx]] = AI;
1584 }
1585
1586 return F;
1587}
1588
1589Function *FunctionAST::Codegen() {
1590 NamedValues.clear();
1591
1592 Function *TheFunction = Proto-&gt;Codegen();
1593 if (TheFunction == 0)
1594 return 0;
1595
1596 // Create a new basic block to start insertion into.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1597 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1598 Builder.SetInsertPoint(BB);
1599
1600 if (Value *RetVal = Body-&gt;Codegen()) {
1601 // Finish off the function.
1602 Builder.CreateRet(RetVal);
1603
1604 // Validate the generated code, checking for consistency.
1605 verifyFunction(*TheFunction);
1606
1607 // Optimize the function.
1608 TheFPM-&gt;run(*TheFunction);
1609
1610 return TheFunction;
1611 }
1612
1613 // Error reading body, remove function.
1614 TheFunction-&gt;eraseFromParent();
1615 return 0;
1616}
1617
1618//===----------------------------------------------------------------------===//
1619// Top-Level parsing and JIT Driver
1620//===----------------------------------------------------------------------===//
1621
1622static ExecutionEngine *TheExecutionEngine;
1623
1624static void HandleDefinition() {
1625 if (FunctionAST *F = ParseDefinition()) {
1626 if (Function *LF = F-&gt;Codegen()) {
1627 fprintf(stderr, "Read function definition:");
1628 LF-&gt;dump();
1629 }
1630 } else {
1631 // Skip token for error recovery.
1632 getNextToken();
1633 }
1634}
1635
1636static void HandleExtern() {
1637 if (PrototypeAST *P = ParseExtern()) {
1638 if (Function *F = P-&gt;Codegen()) {
1639 fprintf(stderr, "Read extern: ");
1640 F-&gt;dump();
1641 }
1642 } else {
1643 // Skip token for error recovery.
1644 getNextToken();
1645 }
1646}
1647
1648static void HandleTopLevelExpression() {
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1649 // Evaluate a top-level expression into an anonymous function.
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1650 if (FunctionAST *F = ParseTopLevelExpr()) {
1651 if (Function *LF = F-&gt;Codegen()) {
1652 // JIT the function, returning a function pointer.
1653 void *FPtr = TheExecutionEngine-&gt;getPointerToFunction(LF);
1654
1655 // Cast it to the right type (takes no arguments, returns a double) so we
1656 // can call it as a native function.
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1657 double (*FP)() = (double (*)())(intptr_t)FPtr;
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1658 fprintf(stderr, "Evaluated to %f\n", FP());
1659 }
1660 } else {
1661 // Skip token for error recovery.
1662 getNextToken();
1663 }
1664}
1665
1666/// top ::= definition | external | expression | ';'
1667static void MainLoop() {
1668 while (1) {
1669 fprintf(stderr, "ready&gt; ");
1670 switch (CurTok) {
1671 case tok_eof: return;
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1672 case ';': getNextToken(); break; // ignore top-level semicolons.
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1673 case tok_def: HandleDefinition(); break;
1674 case tok_extern: HandleExtern(); break;
1675 default: HandleTopLevelExpression(); break;
1676 }
1677 }
1678}
Chris Lattnerf5234802007-10-31 06:47:39 +0000[diff] [blame]1679
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1680//===----------------------------------------------------------------------===//
1681// "Library" functions that can be "extern'd" from user code.
1682//===----------------------------------------------------------------------===//
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]1683
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1684/// putchard - putchar that takes a double and returns 0.
1685extern "C"
1686double putchard(double X) {
1687 putchar((char)X);
1688 return 0;
1689}
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]1690
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1691//===----------------------------------------------------------------------===//
1692// Main driver code.
1693//===----------------------------------------------------------------------===//
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]1694
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1695int main() {
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1696 InitializeNativeTarget();
1697 LLVMContext &amp;Context = getGlobalContext();
1698
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1699 // Install standard binary operators.
1700 // 1 is lowest precedence.
1701 BinopPrecedence['&lt;'] = 10;
1702 BinopPrecedence['+'] = 20;
1703 BinopPrecedence['-'] = 20;
1704 BinopPrecedence['*'] = 40; // highest.
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]1705
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1706 // Prime the first token.
1707 fprintf(stderr, "ready&gt; ");
1708 getNextToken();
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]1709
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1710 // Make the module, which holds all the code.
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1711 TheModule = new Module("my cool jit", Context);
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1712
Jeffrey Yasskinf0356fe2010-01-27 20:34:15 +0000[diff] [blame]1713 // Create the JIT. This takes ownership of the module.
Jeffrey Yasskin42fc5582010-02-11 19:15:20 +0000[diff] [blame]1714 std::string ErrStr;
NAKAMURA Takumi4d6deb02011-04-09 09:51:57 +0000[diff] [blame]1715 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&amp;ErrStr).create();
Jeffrey Yasskin42fc5582010-02-11 19:15:20 +0000[diff] [blame]1716 if (!TheExecutionEngine) {
1717 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1718 exit(1);
1719 }
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1720
Jeffrey Yasskinf0356fe2010-01-27 20:34:15 +0000[diff] [blame]1721 FunctionPassManager OurFPM(TheModule);
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]1722
1723 // Set up the optimizer pipeline. Start with registering info about how the
1724 // target lays out data structures.
1725 OurFPM.add(new TargetData(*TheExecutionEngine-&gt;getTargetData()));
Dan Gohmandfa1a792010-11-15 18:41:10 +0000[diff] [blame]1726 // Provide basic AliasAnalysis support for GVN.
1727 OurFPM.add(createBasicAliasAnalysisPass());
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]1728 // Do simple "peephole" optimizations and bit-twiddling optzns.
1729 OurFPM.add(createInstructionCombiningPass());
1730 // Reassociate expressions.
1731 OurFPM.add(createReassociatePass());
1732 // Eliminate Common SubExpressions.
1733 OurFPM.add(createGVNPass());
1734 // Simplify the control flow graph (deleting unreachable blocks, etc).
1735 OurFPM.add(createCFGSimplificationPass());
1736
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1737 OurFPM.doInitialization();
1738
Reid Kleckner60130f02009-08-26 20:58:25 +0000[diff] [blame]1739 // Set the global so the code gen can use this.
1740 TheFPM = &amp;OurFPM;
1741
1742 // Run the main "interpreter loop" now.
1743 MainLoop();
1744
1745 TheFPM = 0;
1746
1747 // Print out all of the generated code.
1748 TheModule-&gt;dump();
1749
Chris Lattner6093bd52007-10-31 07:29:43 +0000[diff] [blame]1750 return 0;
1751}
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]1752</pre>
1753</div>
1754
Chris Lattner729eb142008-02-10 19:11:04 +0000[diff] [blame]1755<a href="LangImpl6.html">Next: Extending the language: user-defined operators</a>
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]1756</div>
1757
1758<!-- *********************************************************************** -->
1759<hr>
1760<address>
1761 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1762 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1763 <a href="http://validator.w3.org/check/referer"><img
1764 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1765
1766 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
NAKAMURA Takumib9a33632011-04-09 02:13:37 +0000[diff] [blame]1767 <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
Dan Gohman523e3922010-02-03 17:27:31 +0000[diff] [blame]1768 Last modified: $Date$
Chris Lattner602c832c2007-10-31 06:30:21 +0000[diff] [blame]1769</address>
1770</body>
1771</html>