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