1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
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">
14 <div class="doc_title">Kaleidoscope: Extending the Language: Control Flow</div>
17 <li><a href="index.html">Up to Tutorial Index</a></li>
20 <li><a href="#intro">Chapter 5 Introduction</a></li>
21 <li><a href="#ifthen">If/Then/Else</a>
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>
30 <li><a href="#for">'for' Loop Expression</a>
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>
39 <li><a href="#code">Full Code Listing</a></li>
42 <li><a href="LangImpl6.html">Chapter 6</a>: Extending the Language:
43 User-defined Operators</li>
46 <div class="doc_author">
47 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
50 <!-- *********************************************************************** -->
51 <div class="doc_section"><a name="intro">Chapter 5 Introduction</a></div>
52 <!-- *********************************************************************** -->
54 <div class="doc_text">
56 <p>Welcome to Chapter 5 of the "<a href="index.html">Implementing a language
57 with LLVM</a>" tutorial. Parts 1-4 described the implementation of the simple
58 Kaleidoscope language and included support for generating LLVM IR, followed by
59 optimizations and a JIT compiler. Unfortunately, as presented, Kaleidoscope is
60 mostly useless: it has no control flow other than call and return. This means
61 that you can't have conditional branches in the code, significantly limiting its
62 power. In this episode of "build that compiler", we'll extend Kaleidoscope to
63 have an if/then/else expression plus a simple 'for' loop.</p>
67 <!-- *********************************************************************** -->
68 <div class="doc_section"><a name="ifthen">If/Then/Else</a></div>
69 <!-- *********************************************************************** -->
71 <div class="doc_text">
74 Extending Kaleidoscope to support if/then/else is quite straightforward. It
75 basically requires adding lexer support for this "new" concept to the lexer,
76 parser, AST, and LLVM code emitter. This example is nice, because it shows how
77 easy it is to "grow" a language over time, incrementally extending it as new
78 ideas are discovered.</p>
80 <p>Before we get going on "how" we add this extension, lets talk about "what" we
81 want. The basic idea is that we want to be able to write this sort of thing:
84 <div class="doc_code">
94 <p>In Kaleidoscope, every construct is an expression: there are no statements.
95 As such, the if/then/else expression needs to return a value like any other.
96 Since we're using a mostly functional form, we'll have it evaluate its
97 conditional, then return the 'then' or 'else' value based on how the condition
98 was resolved. This is very similar to the C "?:" expression.</p>
100 <p>The semantics of the if/then/else expression is that it evaluates the
101 condition to a boolean equality value: 0.0 is considered to be false and
102 everything else is considered to be true.
103 If the condition is true, the first subexpression is evaluated and returned, if
104 the condition is false, the second subexpression is evaluated and returned.
105 Since Kaleidoscope allows side-effects, this behavior is important to nail down.
108 <p>Now that we know what we "want", lets break this down into its constituent
113 <!-- ======================================================================= -->
114 <div class="doc_subsubsection"><a name="iflexer">Lexer Extensions for
115 If/Then/Else</a></div>
116 <!-- ======================================================================= -->
119 <div class="doc_text">
121 <p>The lexer extensions are straightforward. First we add new enum values
122 for the relevant tokens:</p>
124 <div class="doc_code">
127 tok_if = -6, tok_then = -7, tok_else = -8,
131 <p>Once we have that, we recognize the new keywords in the lexer. This is pretty simple
134 <div class="doc_code">
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;
148 <!-- ======================================================================= -->
149 <div class="doc_subsubsection"><a name="ifast">AST Extensions for
150 If/Then/Else</a></div>
151 <!-- ======================================================================= -->
153 <div class="doc_text">
155 <p>To represent the new expression we add a new AST node for it:</p>
157 <div class="doc_code">
159 /// IfExprAST - Expression class for if/then/else.
160 class IfExprAST : public ExprAST {
161 ExprAST *Cond, *Then, *Else;
163 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
164 : Cond(cond), Then(then), Else(_else) {}
165 virtual Value *Codegen();
170 <p>The AST node just has pointers to the various subexpressions.</p>
174 <!-- ======================================================================= -->
175 <div class="doc_subsubsection"><a name="ifparser">Parser Extensions for
176 If/Then/Else</a></div>
177 <!-- ======================================================================= -->
179 <div class="doc_text">
181 <p>Now that we have the relevant tokens coming from the lexer and we have the
182 AST node to build, our parsing logic is relatively straightforward. First we
183 define a new parsing function:</p>
185 <div class="doc_code">
187 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
188 static ExprAST *ParseIfExpr() {
189 getNextToken(); // eat the if.
192 ExprAST *Cond = ParseExpression();
195 if (CurTok != tok_then)
196 return Error("expected then");
197 getNextToken(); // eat the then
199 ExprAST *Then = ParseExpression();
200 if (Then == 0) return 0;
202 if (CurTok != tok_else)
203 return Error("expected else");
207 ExprAST *Else = ParseExpression();
210 return new IfExprAST(Cond, Then, Else);
215 <p>Next we hook it up as a primary expression:</p>
217 <div class="doc_code">
219 static ExprAST *ParsePrimary() {
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>
233 <!-- ======================================================================= -->
234 <div class="doc_subsubsection"><a name="ifir">LLVM IR for If/Then/Else</a></div>
235 <!-- ======================================================================= -->
237 <div class="doc_text">
239 <p>Now that we have it parsing and building the AST, the final piece is adding
240 LLVM code generation support. This is the most interesting part of the
241 if/then/else example, because this is where it starts to introduce new concepts.
242 All of the code above has been thoroughly described in previous chapters.
245 <p>To motivate the code we want to produce, lets take a look at a simple
246 example. Consider:</p>
248 <div class="doc_code">
252 def baz(x) if x then foo() else bar();
256 <p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
259 <div class="doc_code">
261 declare double @foo()
263 declare double @bar()
265 define double @baz(double %x) {
267 %ifcond = fcmp one double %x, 0.000000e+00
268 br i1 %ifcond, label %then, label %else
270 then: ; preds = %entry
271 %calltmp = call double @foo()
274 else: ; preds = %entry
275 %calltmp1 = call double @bar()
278 ifcont: ; preds = %else, %then
279 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
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
287 into "t.ll" and run "<tt>llvm-as < t.ll | opt -analyze -view-cfg</tt>", <a
288 href="../ProgrammersManual.html#ViewGraph">a window will pop up</a> and you'll
291 <div style="text-align: center"><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
294 <p>Another way to get this is to call "<tt>F->viewCFG()</tt>" or
295 "<tt>F->viewCFGOnly()</tt>" (where F is a "<tt>Function*</tt>") either by
296 inserting actual calls into the code and recompiling or by calling these in the
297 debugger. LLVM has many nice features for visualizing various graphs.</p>
299 <p>Getting back to the generated code, it is fairly simple: the entry block
300 evaluates the conditional expression ("x" in our case here) and compares the
301 result to 0.0 with the "<tt><a href="../LangRef.html#i_fcmp">fcmp</a> one</tt>"
302 instruction ('one' is "Ordered and Not Equal"). Based on the result of this
303 expression, the code jumps to either the "then" or "else" blocks, which contain
304 the expressions for the true/false cases.</p>
306 <p>Once the then/else blocks are finished executing, they both branch back to the
307 'ifcont' block to execute the code that happens after the if/then/else. In this
308 case the only thing left to do is to return to the caller of the function. The
309 question then becomes: how does the code know which expression to return?</p>
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
313 operation</a>. If you're not familiar with SSA, <a
314 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">the wikipedia
315 article</a> is a good introduction and there are various other introductions to
316 it available on your favorite search engine. The short version is that
317 "execution" of the Phi operation requires "remembering" which block control came
318 from. The Phi operation takes on the value corresponding to the input control
319 block. In this case, if control comes in from the "then" block, it gets the
320 value of "calltmp". If control comes from the "else" block, it gets the value
323 <p>At this point, you are probably starting to think "Oh no! This means my
324 simple and elegant front-end will have to start generating SSA form in order to
325 use LLVM!". Fortunately, this is not the case, and we strongly advise
326 <em>not</em> implementing an SSA construction algorithm in your front-end
327 unless there is an amazingly good reason to do so. In practice, there are two
328 sorts of values that float around in code written for your average imperative
329 programming language that might need Phi nodes:</p>
332 <li>Code that involves user variables: <tt>x = 1; x = x + 1; </tt></li>
333 <li>Values that are implicit in the structure of your AST, such as the Phi node
337 <p>In <a href="LangImpl7.html">Chapter 7</a> of this tutorial ("mutable
338 variables"), we'll talk about #1
339 in depth. For now, just believe me that you don't need SSA construction to
340 handle this case. For #2, you have the choice of using the techniques that we will
341 describe for #1, or you can insert Phi nodes directly, if convenient. In this
342 case, it is really really easy to generate the Phi node, so we choose to do it
345 <p>Okay, enough of the motivation and overview, lets generate code!</p>
349 <!-- ======================================================================= -->
350 <div class="doc_subsubsection"><a name="ifcodegen">Code Generation for
351 If/Then/Else</a></div>
352 <!-- ======================================================================= -->
354 <div class="doc_text">
356 <p>In order to generate code for this, we implement the <tt>Codegen</tt> method
357 for <tt>IfExprAST</tt>:</p>
359 <div class="doc_code">
361 Value *IfExprAST::Codegen() {
362 Value *CondV = Cond->Codegen();
363 if (CondV == 0) return 0;
365 // Convert condition to a bool by comparing equal to 0.0.
366 CondV = Builder.CreateFCmpONE(CondV,
367 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
372 <p>This code is straightforward and similar to what we saw before. We emit the
373 expression for the condition, then compare that value to zero to get a truth
374 value as a 1-bit (bool) value.</p>
376 <div class="doc_code">
378 Function *TheFunction = Builder.GetInsertBlock()->getParent();
380 // Create blocks for the then and else cases. Insert the 'then' block at the
381 // end of the function.
382 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
383 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
384 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
386 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
390 <p>This code creates the basic blocks that are related to the if/then/else
391 statement, and correspond directly to the blocks in the example above. The
392 first line gets the current Function object that is being built. It
393 gets this by asking the builder for the current BasicBlock, and asking that
394 block for its "parent" (the function it is currently embedded into).</p>
396 <p>Once it has that, it creates three blocks. Note that it passes "TheFunction"
397 into the constructor for the "then" block. This causes the constructor to
398 automatically insert the new block into the end of the specified function. The
399 other two blocks are created, but aren't yet inserted into the function.</p>
401 <p>Once the blocks are created, we can emit the conditional branch that chooses
402 between them. Note that creating new blocks does not implicitly affect the
403 IRBuilder, so it is still inserting into the block that the condition
404 went 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.
406 This is all ok: it is the standard way that LLVM supports forward
409 <div class="doc_code">
412 Builder.SetInsertPoint(ThenBB);
414 Value *ThenV = Then->Codegen();
415 if (ThenV == 0) return 0;
417 Builder.CreateBr(MergeBB);
418 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
419 ThenBB = Builder.GetInsertBlock();
423 <p>After the conditional branch is inserted, we move the builder to start
424 inserting into the "then" block. Strictly speaking, this call moves the
425 insertion 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
429 <p>Once the insertion point is set, we recursively codegen the "then" expression
430 from the AST. To finish off the "then" block, we create an unconditional branch
431 to the merge block. One interesting (and very important) aspect of the LLVM IR
432 is that it <a href="../LangRef.html#functionstructure">requires all basic blocks
433 to be "terminated"</a> with a <a href="../LangRef.html#terminators">control flow
434 instruction</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
436 violate this rule, the verifier will emit an error.</p>
438 <p>The final line here is quite subtle, but is very important. The basic issue
439 is that when we create the Phi node in the merge block, we need to set up the
440 block/value pairs that indicate how the Phi will work. Importantly, the Phi
441 node expects to have an entry for each predecessor of the block in the CFG. Why
442 then, are we getting the current block when we just set it to ThenBB 5 lines
443 above? The problem is that the "Then" expression may actually itself change the
444 block that the Builder is emitting into if, for example, it contains a nested
445 "if/then/else" expression. Because calling Codegen recursively could
446 arbitrarily change the notion of the current block, we are required to get an
447 up-to-date value for code that will set up the Phi node.</p>
449 <div class="doc_code">
452 TheFunction->getBasicBlockList().push_back(ElseBB);
453 Builder.SetInsertPoint(ElseBB);
455 Value *ElseV = Else->Codegen();
456 if (ElseV == 0) return 0;
458 Builder.CreateBr(MergeBB);
459 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
460 ElseBB = Builder.GetInsertBlock();
464 <p>Code generation for the 'else' block is basically identical to codegen for
465 the 'then' block. The only significant difference is the first line, which adds
466 the 'else' block to the function. Recall previously that the 'else' block was
467 created, but not added to the function. Now that the 'then' and 'else' blocks
468 are emitted, we can finish up with the merge code:</p>
470 <div class="doc_code">
473 TheFunction->getBasicBlockList().push_back(MergeBB);
474 Builder.SetInsertPoint(MergeBB);
475 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
478 PN->addIncoming(ThenV, ThenBB);
479 PN->addIncoming(ElseV, ElseBB);
485 <p>The first two lines here are now familiar: the first adds the "merge" block
486 to the Function object (it was previously floating, like the else block above).
487 The second block changes the insertion point so that newly created code will go
488 into the "merge" block. Once that is done, we need to create the PHI node and
489 set up the block/value pairs for the PHI.</p>
491 <p>Finally, the CodeGen function returns the phi node as the value computed by
492 the if/then/else expression. In our example above, this returned value will
493 feed into the code for the top-level function, which will create the return
496 <p>Overall, we now have the ability to execute conditional code in
497 Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
498 that can calculate a wide variety of numeric functions. Next up we'll add
499 another useful expression that is familiar from non-functional languages...</p>
503 <!-- *********************************************************************** -->
504 <div class="doc_section"><a name="for">'for' Loop Expression</a></div>
505 <!-- *********************************************************************** -->
507 <div class="doc_text">
509 <p>Now that we know how to add basic control flow constructs to the language,
510 we have the tools to add more powerful things. Lets add something more
511 aggressive, a 'for' expression:</p>
513 <div class="doc_code">
515 extern putchard(char)
517 for i = 1, i < n, 1.0 in
518 putchard(42); # ascii 42 = '*'
520 # print 100 '*' characters
525 <p>This expression defines a new variable ("i" in this case) which iterates from
526 a starting value, while the condition ("i < n" in this case) is true,
527 incrementing by an optional step value ("1.0" in this case). If the step value
528 is omitted, it defaults to 1.0. While the loop is true, it executes its
529 body expression. Because we don't have anything better to return, we'll just
530 define the loop as always returning 0.0. In the future when we have mutable
531 variables, it will get more useful.</p>
533 <p>As before, lets talk about the changes that we need to Kaleidoscope to
538 <!-- ======================================================================= -->
539 <div class="doc_subsubsection"><a name="forlexer">Lexer Extensions for
540 the 'for' Loop</a></div>
541 <!-- ======================================================================= -->
543 <div class="doc_text">
545 <p>The lexer extensions are the same sort of thing as for if/then/else:</p>
547 <div class="doc_code">
549 ... in enum Token ...
551 tok_if = -6, tok_then = -7, tok_else = -8,
552 <b> tok_for = -9, tok_in = -10</b>
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;
568 <!-- ======================================================================= -->
569 <div class="doc_subsubsection"><a name="forast">AST Extensions for
570 the 'for' Loop</a></div>
571 <!-- ======================================================================= -->
573 <div class="doc_text">
575 <p>The AST node is just as simple. It basically boils down to capturing
576 the variable name and the constituent expressions in the node.</p>
578 <div class="doc_code">
580 /// ForExprAST - Expression class for for/in.
581 class ForExprAST : public ExprAST {
583 ExprAST *Start, *End, *Step, *Body;
585 ForExprAST(const std::string &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();
595 <!-- ======================================================================= -->
596 <div class="doc_subsubsection"><a name="forparser">Parser Extensions for
597 the 'for' Loop</a></div>
598 <!-- ======================================================================= -->
600 <div class="doc_text">
602 <p>The parser code is also fairly standard. The only interesting thing here is
603 handling of the optional step value. The parser code handles it by checking to
604 see if the second comma is present. If not, it sets the step value to null in
607 <div class="doc_code">
609 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
610 static ExprAST *ParseForExpr() {
611 getNextToken(); // eat the for.
613 if (CurTok != tok_identifier)
614 return Error("expected identifier after for");
616 std::string IdName = IdentifierStr;
617 getNextToken(); // eat identifier.
620 return Error("expected '=' after for");
621 getNextToken(); // eat '='.
624 ExprAST *Start = ParseExpression();
625 if (Start == 0) return 0;
627 return Error("expected ',' after for start value");
630 ExprAST *End = ParseExpression();
631 if (End == 0) return 0;
633 // The step value is optional.
637 Step = ParseExpression();
638 if (Step == 0) return 0;
641 if (CurTok != tok_in)
642 return Error("expected 'in' after for");
643 getNextToken(); // eat 'in'.
645 ExprAST *Body = ParseExpression();
646 if (Body == 0) return 0;
648 return new ForExprAST(IdName, Start, End, Step, Body);
655 <!-- ======================================================================= -->
656 <div class="doc_subsubsection"><a name="forir">LLVM IR for
657 the 'for' Loop</a></div>
658 <!-- ======================================================================= -->
660 <div class="doc_text">
662 <p>Now we get to the good part: the LLVM IR we want to generate for this thing.
663 With the simple example above, we get this LLVM IR (note that this dump is
664 generated with optimizations disabled for clarity):
667 <div class="doc_code">
669 declare double @putchard(double)
671 define double @printstar(double %n) {
673 ; initial value = 1.0 (inlined into phi)
676 loop: ; preds = %loop, %entry
677 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
679 %calltmp = call double @putchard( double 4.200000e+01 )
681 %nextvar = add double %i, 1.000000e+00
684 %cmptmp = fcmp ult double %i, %n
685 %booltmp = uitofp i1 %cmptmp to double
686 %loopcond = fcmp one double %booltmp, 0.000000e+00
687 br i1 %loopcond, label %loop, label %afterloop
689 afterloop: ; preds = %loop
690 ; loop always returns 0.0
691 ret double 0.000000e+00
696 <p>This loop contains all the same constructs we saw before: a phi node, several
697 expressions, and some basic blocks. Lets see how this fits together.</p>
701 <!-- ======================================================================= -->
702 <div class="doc_subsubsection"><a name="forcodegen">Code Generation for
703 the 'for' Loop</a></div>
704 <!-- ======================================================================= -->
706 <div class="doc_text">
708 <p>The first part of Codegen is very simple: we just output the start expression
709 for the loop value:</p>
711 <div class="doc_code">
713 Value *ForExprAST::Codegen() {
714 // Emit the start code first, without 'variable' in scope.
715 Value *StartVal = Start->Codegen();
716 if (StartVal == 0) return 0;
720 <p>With this out of the way, the next step is to set up the LLVM basic block
721 for the start of the loop body. In the case above, the whole loop body is one
722 block, but remember that the body code itself could consist of multiple blocks
723 (e.g. if it contains an if/then/else or a for/in expression).</p>
725 <div class="doc_code">
727 // Make the new basic block for the loop header, inserting after current
729 Function *TheFunction = Builder.GetInsertBlock()->getParent();
730 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
731 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
733 // Insert an explicit fall through from the current block to the LoopBB.
734 Builder.CreateBr(LoopBB);
738 <p>This code is similar to what we saw for if/then/else. Because we will need
739 it to create the Phi node, we remember the block that falls through into the
740 loop. Once we have that, we create the actual block that starts the loop and
741 create an unconditional branch for the fall-through between the two blocks.</p>
743 <div class="doc_code">
745 // Start insertion in LoopBB.
746 Builder.SetInsertPoint(LoopBB);
748 // Start the PHI node with an entry for Start.
749 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
750 Variable->addIncoming(StartVal, PreheaderBB);
754 <p>Now that the "preheader" for the loop is set up, we switch to emitting code
755 for the loop body. To begin with, we move the insertion point and create the
756 PHI node for the loop induction variable. Since we already know the incoming
757 value for the starting value, we add it to the Phi node. Note that the Phi will
758 eventually get a second value for the backedge, but we can't set it up yet
759 (because it doesn't exist!).</p>
761 <div class="doc_code">
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;
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
771 if (Body->Codegen() == 0)
776 <p>Now the code starts to get more interesting. Our 'for' loop introduces a new
777 variable to the symbol table. This means that our symbol table can now contain
778 either function arguments or loop variables. To handle this, before we codegen
779 the body of the loop, we add the loop variable as the current value for its
780 name. Note that it is possible that there is a variable of the same name in the
781 outer scope. It would be easy to make this an error (emit an error and return
782 null if there is already an entry for VarName) but we choose to allow shadowing
783 of variables. In order to handle this correctly, we remember the Value that
784 we are potentially shadowing in <tt>OldVal</tt> (which will be null if there is
785 no shadowed variable).</p>
787 <p>Once the loop variable is set into the symbol table, the code recursively
788 codegen's the body. This allows the body to use the loop variable: any
789 references to it will naturally find it in the symbol table.</p>
791 <div class="doc_code">
793 // Emit the step value.
796 StepVal = Step->Codegen();
797 if (StepVal == 0) return 0;
799 // If not specified, use 1.0.
800 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
803 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
807 <p>Now that the body is emitted, we compute the next value of the iteration
808 variable by adding the step value, or 1.0 if it isn't present. '<tt>NextVar</tt>'
809 will be the value of the loop variable on the next iteration of the loop.</p>
811 <div class="doc_code">
813 // Compute the end condition.
814 Value *EndCond = End->Codegen();
815 if (EndCond == 0) return EndCond;
817 // Convert condition to a bool by comparing equal to 0.0.
818 EndCond = Builder.CreateFCmpONE(EndCond,
819 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
824 <p>Finally, we evaluate the exit value of the loop, to determine whether the
825 loop should exit. This mirrors the condition evaluation for the if/then/else
828 <div class="doc_code">
830 // Create the "after loop" block and insert it.
831 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
832 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
834 // Insert the conditional branch into the end of LoopEndBB.
835 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
837 // Any new code will be inserted in AfterBB.
838 Builder.SetInsertPoint(AfterBB);
842 <p>With the code for the body of the loop complete, we just need to finish up
843 the 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
844 exit condition, it creates a conditional branch that chooses between executing
845 the 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>
848 <div class="doc_code">
850 // Add a new entry to the PHI node for the backedge.
851 Variable->addIncoming(NextVar, LoopEndBB);
853 // Restore the unshadowed variable.
855 NamedValues[VarName] = OldVal;
857 NamedValues.erase(VarName);
859 // for expr always returns 0.0.
860 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
865 <p>The final code handles various cleanups: now that we have the "NextVar"
866 value, we can add the incoming value to the loop PHI node. After that, we
867 remove the loop variable from the symbol table, so that it isn't in scope after
868 the for loop. Finally, code generation of the for loop always returns 0.0, so
869 that is what we return from <tt>ForExprAST::Codegen</tt>.</p>
871 <p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
872 the 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
873 to know. In the next chapter of our saga, we will get a bit crazier and add
874 <a href="LangImpl6.html">user-defined operators</a> to our poor innocent
879 <!-- *********************************************************************** -->
880 <div class="doc_section"><a name="code">Full Code Listing</a></div>
881 <!-- *********************************************************************** -->
883 <div class="doc_text">
886 Here is the complete code listing for our running example, enhanced with the
887 if/then/else and for expressions.. To build this example, use:
890 <div class="doc_code">
893 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
899 <p>Here is the code:</p>
901 <div class="doc_code">
903 #include "llvm/DerivedTypes.h"
904 #include "llvm/ExecutionEngine/ExecutionEngine.h"
905 #include "llvm/ExecutionEngine/Interpreter.h"
906 #include "llvm/ExecutionEngine/JIT.h"
907 #include "llvm/LLVMContext.h"
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"
913 #include "llvm/Target/TargetSelect.h"
914 #include "llvm/Transforms/Scalar.h"
915 #include "llvm/Support/IRBuilder.h"
916 #include <cstdio>
917 #include <string>
919 #include <vector>
920 using namespace llvm;
922 //===----------------------------------------------------------------------===//
924 //===----------------------------------------------------------------------===//
926 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
927 // of these for known things.
932 tok_def = -2, tok_extern = -3,
935 tok_identifier = -4, tok_number = -5,
938 tok_if = -6, tok_then = -7, tok_else = -8,
939 tok_for = -9, tok_in = -10
942 static std::string IdentifierStr; // Filled in if tok_identifier
943 static double NumVal; // Filled in if tok_number
945 /// gettok - Return the next token from standard input.
946 static int gettok() {
947 static int LastChar = ' ';
949 // Skip any whitespace.
950 while (isspace(LastChar))
951 LastChar = getchar();
953 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
954 IdentifierStr = LastChar;
955 while (isalnum((LastChar = getchar())))
956 IdentifierStr += LastChar;
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;
968 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
972 LastChar = getchar();
973 } while (isdigit(LastChar) || LastChar == '.');
975 NumVal = strtod(NumStr.c_str(), 0);
979 if (LastChar == '#') {
980 // Comment until end of line.
981 do LastChar = getchar();
982 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
988 // Check for end of file. Don't eat the EOF.
992 // Otherwise, just return the character as its ascii value.
993 int ThisChar = LastChar;
994 LastChar = getchar();
998 //===----------------------------------------------------------------------===//
999 // Abstract Syntax Tree (aka Parse Tree)
1000 //===----------------------------------------------------------------------===//
1002 /// ExprAST - Base class for all expression nodes.
1005 virtual ~ExprAST() {}
1006 virtual Value *Codegen() = 0;
1009 /// NumberExprAST - Expression class for numeric literals like "1.0".
1010 class NumberExprAST : public ExprAST {
1013 NumberExprAST(double val) : Val(val) {}
1014 virtual Value *Codegen();
1017 /// VariableExprAST - Expression class for referencing a variable, like "a".
1018 class VariableExprAST : public ExprAST {
1021 VariableExprAST(const std::string &name) : Name(name) {}
1022 virtual Value *Codegen();
1025 /// BinaryExprAST - Expression class for a binary operator.
1026 class BinaryExprAST : public ExprAST {
1030 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
1031 : Op(op), LHS(lhs), RHS(rhs) {}
1032 virtual Value *Codegen();
1035 /// CallExprAST - Expression class for function calls.
1036 class CallExprAST : public ExprAST {
1038 std::vector<ExprAST*> Args;
1040 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
1041 : Callee(callee), Args(args) {}
1042 virtual Value *Codegen();
1045 /// IfExprAST - Expression class for if/then/else.
1046 class IfExprAST : public ExprAST {
1047 ExprAST *Cond, *Then, *Else;
1049 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1050 : Cond(cond), Then(then), Else(_else) {}
1051 virtual Value *Codegen();
1054 /// ForExprAST - Expression class for for/in.
1055 class ForExprAST : public ExprAST {
1056 std::string VarName;
1057 ExprAST *Start, *End, *Step, *Body;
1059 ForExprAST(const std::string &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();
1065 /// PrototypeAST - This class represents the "prototype" for a function,
1066 /// which captures its name, and its argument names (thus implicitly the number
1067 /// of arguments the function takes).
1068 class PrototypeAST {
1070 std::vector<std::string> Args;
1072 PrototypeAST(const std::string &name, const std::vector<std::string> &args)
1073 : Name(name), Args(args) {}
1075 Function *Codegen();
1078 /// FunctionAST - This class represents a function definition itself.
1080 PrototypeAST *Proto;
1083 FunctionAST(PrototypeAST *proto, ExprAST *body)
1084 : Proto(proto), Body(body) {}
1086 Function *Codegen();
1089 //===----------------------------------------------------------------------===//
1091 //===----------------------------------------------------------------------===//
1093 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1094 /// token the parser is looking at. getNextToken reads another token from the
1095 /// lexer and updates CurTok with its results.
1097 static int getNextToken() {
1098 return CurTok = gettok();
1101 /// BinopPrecedence - This holds the precedence for each binary operator that is
1103 static std::map<char, int> BinopPrecedence;
1105 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1106 static int GetTokPrecedence() {
1107 if (!isascii(CurTok))
1110 // Make sure it's a declared binop.
1111 int TokPrec = BinopPrecedence[CurTok];
1112 if (TokPrec <= 0) return -1;
1116 /// Error* - These are little helper functions for error handling.
1117 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1118 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1119 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1121 static ExprAST *ParseExpression();
1125 /// ::= identifier '(' expression* ')'
1126 static ExprAST *ParseIdentifierExpr() {
1127 std::string IdName = IdentifierStr;
1129 getNextToken(); // eat identifier.
1131 if (CurTok != '(') // Simple variable ref.
1132 return new VariableExprAST(IdName);
1135 getNextToken(); // eat (
1136 std::vector<ExprAST*> Args;
1137 if (CurTok != ')') {
1139 ExprAST *Arg = ParseExpression();
1141 Args.push_back(Arg);
1143 if (CurTok == ')') break;
1146 return Error("Expected ')' or ',' in argument list");
1154 return new CallExprAST(IdName, Args);
1157 /// numberexpr ::= number
1158 static ExprAST *ParseNumberExpr() {
1159 ExprAST *Result = new NumberExprAST(NumVal);
1160 getNextToken(); // consume the number
1164 /// parenexpr ::= '(' expression ')'
1165 static ExprAST *ParseParenExpr() {
1166 getNextToken(); // eat (.
1167 ExprAST *V = ParseExpression();
1171 return Error("expected ')'");
1172 getNextToken(); // eat ).
1176 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1177 static ExprAST *ParseIfExpr() {
1178 getNextToken(); // eat the if.
1181 ExprAST *Cond = ParseExpression();
1182 if (!Cond) return 0;
1184 if (CurTok != tok_then)
1185 return Error("expected then");
1186 getNextToken(); // eat the then
1188 ExprAST *Then = ParseExpression();
1189 if (Then == 0) return 0;
1191 if (CurTok != tok_else)
1192 return Error("expected else");
1196 ExprAST *Else = ParseExpression();
1197 if (!Else) return 0;
1199 return new IfExprAST(Cond, Then, Else);
1202 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1203 static ExprAST *ParseForExpr() {
1204 getNextToken(); // eat the for.
1206 if (CurTok != tok_identifier)
1207 return Error("expected identifier after for");
1209 std::string IdName = IdentifierStr;
1210 getNextToken(); // eat identifier.
1213 return Error("expected '=' after for");
1214 getNextToken(); // eat '='.
1217 ExprAST *Start = ParseExpression();
1218 if (Start == 0) return 0;
1220 return Error("expected ',' after for start value");
1223 ExprAST *End = ParseExpression();
1224 if (End == 0) return 0;
1226 // The step value is optional.
1228 if (CurTok == ',') {
1230 Step = ParseExpression();
1231 if (Step == 0) return 0;
1234 if (CurTok != tok_in)
1235 return Error("expected 'in' after for");
1236 getNextToken(); // eat 'in'.
1238 ExprAST *Body = ParseExpression();
1239 if (Body == 0) return 0;
1241 return new ForExprAST(IdName, Start, End, Step, Body);
1245 /// ::= identifierexpr
1250 static ExprAST *ParsePrimary() {
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();
1262 /// ::= ('+' primary)*
1263 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1264 // If this is a binop, find its precedence.
1266 int TokPrec = GetTokPrecedence();
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 < ExprPrec)
1273 // Okay, we know this is a binop.
1275 getNextToken(); // eat binop
1277 // Parse the primary expression after the binary operator.
1278 ExprAST *RHS = ParsePrimary();
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 < NextPrec) {
1285 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1286 if (RHS == 0) return 0;
1290 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1295 /// ::= primary binoprhs
1297 static ExprAST *ParseExpression() {
1298 ExprAST *LHS = ParsePrimary();
1301 return ParseBinOpRHS(0, LHS);
1305 /// ::= id '(' id* ')'
1306 static PrototypeAST *ParsePrototype() {
1307 if (CurTok != tok_identifier)
1308 return ErrorP("Expected function name in prototype");
1310 std::string FnName = IdentifierStr;
1314 return ErrorP("Expected '(' in prototype");
1316 std::vector<std::string> ArgNames;
1317 while (getNextToken() == tok_identifier)
1318 ArgNames.push_back(IdentifierStr);
1320 return ErrorP("Expected ')' in prototype");
1323 getNextToken(); // eat ')'.
1325 return new PrototypeAST(FnName, ArgNames);
1328 /// definition ::= 'def' prototype expression
1329 static FunctionAST *ParseDefinition() {
1330 getNextToken(); // eat def.
1331 PrototypeAST *Proto = ParsePrototype();
1332 if (Proto == 0) return 0;
1334 if (ExprAST *E = ParseExpression())
1335 return new FunctionAST(Proto, E);
1339 /// toplevelexpr ::= expression
1340 static FunctionAST *ParseTopLevelExpr() {
1341 if (ExprAST *E = ParseExpression()) {
1342 // Make an anonymous proto.
1343 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
1344 return new FunctionAST(Proto, E);
1349 /// external ::= 'extern' prototype
1350 static PrototypeAST *ParseExtern() {
1351 getNextToken(); // eat extern.
1352 return ParsePrototype();
1355 //===----------------------------------------------------------------------===//
1357 //===----------------------------------------------------------------------===//
1359 static Module *TheModule;
1360 static IRBuilder<> Builder(getGlobalContext());
1361 static std::map<std::string, Value*> NamedValues;
1362 static FunctionPassManager *TheFPM;
1364 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1366 Value *NumberExprAST::Codegen() {
1367 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1370 Value *VariableExprAST::Codegen() {
1371 // Look this variable up in the function.
1372 Value *V = NamedValues[Name];
1373 return V ? V : ErrorV("Unknown variable name");
1376 Value *BinaryExprAST::Codegen() {
1377 Value *L = LHS->Codegen();
1378 Value *R = RHS->Codegen();
1379 if (L == 0 || R == 0) return 0;
1382 case '+': return Builder.CreateAdd(L, R, "addtmp");
1383 case '-': return Builder.CreateSub(L, R, "subtmp");
1384 case '*': return Builder.CreateMul(L, R, "multmp");
1386 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1387 // Convert bool 0/1 to double 0.0 or 1.0
1388 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1390 default: return ErrorV("invalid binary operator");
1394 Value *CallExprAST::Codegen() {
1395 // Look up the name in the global module table.
1396 Function *CalleeF = TheModule->getFunction(Callee);
1398 return ErrorV("Unknown function referenced");
1400 // If argument mismatch error.
1401 if (CalleeF->arg_size() != Args.size())
1402 return ErrorV("Incorrect # arguments passed");
1404 std::vector<Value*> ArgsV;
1405 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1406 ArgsV.push_back(Args[i]->Codegen());
1407 if (ArgsV.back() == 0) return 0;
1410 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1413 Value *IfExprAST::Codegen() {
1414 Value *CondV = Cond->Codegen();
1415 if (CondV == 0) return 0;
1417 // Convert condition to a bool by comparing equal to 0.0.
1418 CondV = Builder.CreateFCmpONE(CondV,
1419 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1422 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1424 // Create blocks for the then and else cases. Insert the 'then' block at the
1425 // end of the function.
1426 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1427 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1428 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1430 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1433 Builder.SetInsertPoint(ThenBB);
1435 Value *ThenV = Then->Codegen();
1436 if (ThenV == 0) return 0;
1438 Builder.CreateBr(MergeBB);
1439 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1440 ThenBB = Builder.GetInsertBlock();
1443 TheFunction->getBasicBlockList().push_back(ElseBB);
1444 Builder.SetInsertPoint(ElseBB);
1446 Value *ElseV = Else->Codegen();
1447 if (ElseV == 0) return 0;
1449 Builder.CreateBr(MergeBB);
1450 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1451 ElseBB = Builder.GetInsertBlock();
1453 // Emit merge block.
1454 TheFunction->getBasicBlockList().push_back(MergeBB);
1455 Builder.SetInsertPoint(MergeBB);
1456 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
1459 PN->addIncoming(ThenV, ThenBB);
1460 PN->addIncoming(ElseV, ElseBB);
1464 Value *ForExprAST::Codegen() {
1467 // start = startexpr
1470 // variable = phi [start, loopheader], [nextvariable, loopend]
1476 // nextvariable = variable + step
1477 // endcond = endexpr
1478 // br endcond, loop, endloop
1481 // Emit the start code first, without 'variable' in scope.
1482 Value *StartVal = Start->Codegen();
1483 if (StartVal == 0) return 0;
1485 // Make the new basic block for the loop header, inserting after current
1487 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1488 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1489 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1491 // Insert an explicit fall through from the current block to the LoopBB.
1492 Builder.CreateBr(LoopBB);
1494 // Start insertion in LoopBB.
1495 Builder.SetInsertPoint(LoopBB);
1497 // Start the PHI node with an entry for Start.
1498 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
1499 Variable->addIncoming(StartVal, PreheaderBB);
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;
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
1509 if (Body->Codegen() == 0)
1512 // Emit the step value.
1515 StepVal = Step->Codegen();
1516 if (StepVal == 0) return 0;
1518 // If not specified, use 1.0.
1519 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1522 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
1524 // Compute the end condition.
1525 Value *EndCond = End->Codegen();
1526 if (EndCond == 0) return EndCond;
1528 // Convert condition to a bool by comparing equal to 0.0.
1529 EndCond = Builder.CreateFCmpONE(EndCond,
1530 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1533 // Create the "after loop" block and insert it.
1534 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1535 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1537 // Insert the conditional branch into the end of LoopEndBB.
1538 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1540 // Any new code will be inserted in AfterBB.
1541 Builder.SetInsertPoint(AfterBB);
1543 // Add a new entry to the PHI node for the backedge.
1544 Variable->addIncoming(NextVar, LoopEndBB);
1546 // Restore the unshadowed variable.
1548 NamedValues[VarName] = OldVal;
1550 NamedValues.erase(VarName);
1553 // for expr always returns 0.0.
1554 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1557 Function *PrototypeAST::Codegen() {
1558 // Make the function type: double(double,double) etc.
1559 std::vector<const Type*> Doubles(Args.size(),
1560 Type::getDoubleTy(getGlobalContext()));
1561 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1564 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
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->getName() != Name) {
1569 // Delete the one we just made and get the existing one.
1570 F->eraseFromParent();
1571 F = TheModule->getFunction(Name);
1573 // If F already has a body, reject this.
1574 if (!F->empty()) {
1575 ErrorF("redefinition of function");
1579 // If F took a different number of args, reject.
1580 if (F->arg_size() != Args.size()) {
1581 ErrorF("redefinition of function with different # args");
1586 // Set names for all arguments.
1588 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1590 AI->setName(Args[Idx]);
1592 // Add arguments to variable symbol table.
1593 NamedValues[Args[Idx]] = AI;
1599 Function *FunctionAST::Codegen() {
1600 NamedValues.clear();
1602 Function *TheFunction = Proto->Codegen();
1603 if (TheFunction == 0)
1606 // Create a new basic block to start insertion into.
1607 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1608 Builder.SetInsertPoint(BB);
1610 if (Value *RetVal = Body->Codegen()) {
1611 // Finish off the function.
1612 Builder.CreateRet(RetVal);
1614 // Validate the generated code, checking for consistency.
1615 verifyFunction(*TheFunction);
1617 // Optimize the function.
1618 TheFPM->run(*TheFunction);
1623 // Error reading body, remove function.
1624 TheFunction->eraseFromParent();
1628 //===----------------------------------------------------------------------===//
1629 // Top-Level parsing and JIT Driver
1630 //===----------------------------------------------------------------------===//
1632 static ExecutionEngine *TheExecutionEngine;
1634 static void HandleDefinition() {
1635 if (FunctionAST *F = ParseDefinition()) {
1636 if (Function *LF = F->Codegen()) {
1637 fprintf(stderr, "Read function definition:");
1641 // Skip token for error recovery.
1646 static void HandleExtern() {
1647 if (PrototypeAST *P = ParseExtern()) {
1648 if (Function *F = P->Codegen()) {
1649 fprintf(stderr, "Read extern: ");
1653 // Skip token for error recovery.
1658 static void HandleTopLevelExpression() {
1659 // Evaluate a top-level expression into an anonymous function.
1660 if (FunctionAST *F = ParseTopLevelExpr()) {
1661 if (Function *LF = F->Codegen()) {
1662 // JIT the function, returning a function pointer.
1663 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1665 // Cast it to the right type (takes no arguments, returns a double) so we
1666 // can call it as a native function.
1667 double (*FP)() = (double (*)())(intptr_t)FPtr;
1668 fprintf(stderr, "Evaluated to %f\n", FP());
1671 // Skip token for error recovery.
1676 /// top ::= definition | external | expression | ';'
1677 static void MainLoop() {
1679 fprintf(stderr, "ready> ");
1681 case tok_eof: return;
1682 case ';': getNextToken(); break; // ignore top-level semicolons.
1683 case tok_def: HandleDefinition(); break;
1684 case tok_extern: HandleExtern(); break;
1685 default: HandleTopLevelExpression(); break;
1690 //===----------------------------------------------------------------------===//
1691 // "Library" functions that can be "extern'd" from user code.
1692 //===----------------------------------------------------------------------===//
1694 /// putchard - putchar that takes a double and returns 0.
1696 double putchard(double X) {
1701 //===----------------------------------------------------------------------===//
1702 // Main driver code.
1703 //===----------------------------------------------------------------------===//
1706 InitializeNativeTarget();
1707 LLVMContext &Context = getGlobalContext();
1709 // Install standard binary operators.
1710 // 1 is lowest precedence.
1711 BinopPrecedence['<'] = 10;
1712 BinopPrecedence['+'] = 20;
1713 BinopPrecedence['-'] = 20;
1714 BinopPrecedence['*'] = 40; // highest.
1716 // Prime the first token.
1717 fprintf(stderr, "ready> ");
1720 // Make the module, which holds all the code.
1721 TheModule = new Module("my cool jit", Context);
1723 ExistingModuleProvider *OurModuleProvider =
1724 new ExistingModuleProvider(TheModule);
1726 // Create the JIT. This takes ownership of the module and module provider.
1727 TheExecutionEngine = EngineBuilder(OurModuleProvider).create();
1729 FunctionPassManager OurFPM(OurModuleProvider);
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->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());
1743 OurFPM.doInitialization();
1745 // Set the global so the code gen can use this.
1746 TheFPM = &OurFPM;
1748 // Run the main "interpreter loop" now.
1753 // Print out all of the generated code.
1754 TheModule->dump();
1761 <a href="LangImpl6.html">Next: Extending the language: user-defined operators</a>
1764 <!-- *********************************************************************** -->
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>
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) $