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()), "iftmp");
477 PN->addIncoming(ThenV, ThenBB);
478 PN->addIncoming(ElseV, ElseBB);
484 <p>The first two lines here are now familiar: the first adds the "merge" block
485 to the Function object (it was previously floating, like the else block above).
486 The second block changes the insertion point so that newly created code will go
487 into the "merge" block. Once that is done, we need to create the PHI node and
488 set up the block/value pairs for the PHI.</p>
490 <p>Finally, the CodeGen function returns the phi node as the value computed by
491 the if/then/else expression. In our example above, this returned value will
492 feed into the code for the top-level function, which will create the return
495 <p>Overall, we now have the ability to execute conditional code in
496 Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
497 that can calculate a wide variety of numeric functions. Next up we'll add
498 another useful expression that is familiar from non-functional languages...</p>
502 <!-- *********************************************************************** -->
503 <div class="doc_section"><a name="for">'for' Loop Expression</a></div>
504 <!-- *********************************************************************** -->
506 <div class="doc_text">
508 <p>Now that we know how to add basic control flow constructs to the language,
509 we have the tools to add more powerful things. Lets add something more
510 aggressive, a 'for' expression:</p>
512 <div class="doc_code">
514 extern putchard(char)
516 for i = 1, i < n, 1.0 in
517 putchard(42); # ascii 42 = '*'
519 # print 100 '*' characters
524 <p>This expression defines a new variable ("i" in this case) which iterates from
525 a starting value, while the condition ("i < n" in this case) is true,
526 incrementing by an optional step value ("1.0" in this case). If the step value
527 is omitted, it defaults to 1.0. While the loop is true, it executes its
528 body expression. Because we don't have anything better to return, we'll just
529 define the loop as always returning 0.0. In the future when we have mutable
530 variables, it will get more useful.</p>
532 <p>As before, lets talk about the changes that we need to Kaleidoscope to
537 <!-- ======================================================================= -->
538 <div class="doc_subsubsection"><a name="forlexer">Lexer Extensions for
539 the 'for' Loop</a></div>
540 <!-- ======================================================================= -->
542 <div class="doc_text">
544 <p>The lexer extensions are the same sort of thing as for if/then/else:</p>
546 <div class="doc_code">
548 ... in enum Token ...
550 tok_if = -6, tok_then = -7, tok_else = -8,
551 <b> tok_for = -9, tok_in = -10</b>
554 if (IdentifierStr == "def") return tok_def;
555 if (IdentifierStr == "extern") return tok_extern;
556 if (IdentifierStr == "if") return tok_if;
557 if (IdentifierStr == "then") return tok_then;
558 if (IdentifierStr == "else") return tok_else;
559 <b>if (IdentifierStr == "for") return tok_for;
560 if (IdentifierStr == "in") return tok_in;</b>
561 return tok_identifier;
567 <!-- ======================================================================= -->
568 <div class="doc_subsubsection"><a name="forast">AST Extensions for
569 the 'for' Loop</a></div>
570 <!-- ======================================================================= -->
572 <div class="doc_text">
574 <p>The AST node is just as simple. It basically boils down to capturing
575 the variable name and the constituent expressions in the node.</p>
577 <div class="doc_code">
579 /// ForExprAST - Expression class for for/in.
580 class ForExprAST : public ExprAST {
582 ExprAST *Start, *End, *Step, *Body;
584 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
585 ExprAST *step, ExprAST *body)
586 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
587 virtual Value *Codegen();
594 <!-- ======================================================================= -->
595 <div class="doc_subsubsection"><a name="forparser">Parser Extensions for
596 the 'for' Loop</a></div>
597 <!-- ======================================================================= -->
599 <div class="doc_text">
601 <p>The parser code is also fairly standard. The only interesting thing here is
602 handling of the optional step value. The parser code handles it by checking to
603 see if the second comma is present. If not, it sets the step value to null in
606 <div class="doc_code">
608 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
609 static ExprAST *ParseForExpr() {
610 getNextToken(); // eat the for.
612 if (CurTok != tok_identifier)
613 return Error("expected identifier after for");
615 std::string IdName = IdentifierStr;
616 getNextToken(); // eat identifier.
619 return Error("expected '=' after for");
620 getNextToken(); // eat '='.
623 ExprAST *Start = ParseExpression();
624 if (Start == 0) return 0;
626 return Error("expected ',' after for start value");
629 ExprAST *End = ParseExpression();
630 if (End == 0) return 0;
632 // The step value is optional.
636 Step = ParseExpression();
637 if (Step == 0) return 0;
640 if (CurTok != tok_in)
641 return Error("expected 'in' after for");
642 getNextToken(); // eat 'in'.
644 ExprAST *Body = ParseExpression();
645 if (Body == 0) return 0;
647 return new ForExprAST(IdName, Start, End, Step, Body);
654 <!-- ======================================================================= -->
655 <div class="doc_subsubsection"><a name="forir">LLVM IR for
656 the 'for' Loop</a></div>
657 <!-- ======================================================================= -->
659 <div class="doc_text">
661 <p>Now we get to the good part: the LLVM IR we want to generate for this thing.
662 With the simple example above, we get this LLVM IR (note that this dump is
663 generated with optimizations disabled for clarity):
666 <div class="doc_code">
668 declare double @putchard(double)
670 define double @printstar(double %n) {
672 ; initial value = 1.0 (inlined into phi)
675 loop: ; preds = %loop, %entry
676 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
678 %calltmp = call double @putchard( double 4.200000e+01 )
680 %nextvar = add double %i, 1.000000e+00
683 %cmptmp = fcmp ult double %i, %n
684 %booltmp = uitofp i1 %cmptmp to double
685 %loopcond = fcmp one double %booltmp, 0.000000e+00
686 br i1 %loopcond, label %loop, label %afterloop
688 afterloop: ; preds = %loop
689 ; loop always returns 0.0
690 ret double 0.000000e+00
695 <p>This loop contains all the same constructs we saw before: a phi node, several
696 expressions, and some basic blocks. Lets see how this fits together.</p>
700 <!-- ======================================================================= -->
701 <div class="doc_subsubsection"><a name="forcodegen">Code Generation for
702 the 'for' Loop</a></div>
703 <!-- ======================================================================= -->
705 <div class="doc_text">
707 <p>The first part of Codegen is very simple: we just output the start expression
708 for the loop value:</p>
710 <div class="doc_code">
712 Value *ForExprAST::Codegen() {
713 // Emit the start code first, without 'variable' in scope.
714 Value *StartVal = Start->Codegen();
715 if (StartVal == 0) return 0;
719 <p>With this out of the way, the next step is to set up the LLVM basic block
720 for the start of the loop body. In the case above, the whole loop body is one
721 block, but remember that the body code itself could consist of multiple blocks
722 (e.g. if it contains an if/then/else or a for/in expression).</p>
724 <div class="doc_code">
726 // Make the new basic block for the loop header, inserting after current
728 Function *TheFunction = Builder.GetInsertBlock()->getParent();
729 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
730 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
732 // Insert an explicit fall through from the current block to the LoopBB.
733 Builder.CreateBr(LoopBB);
737 <p>This code is similar to what we saw for if/then/else. Because we will need
738 it to create the Phi node, we remember the block that falls through into the
739 loop. Once we have that, we create the actual block that starts the loop and
740 create an unconditional branch for the fall-through between the two blocks.</p>
742 <div class="doc_code">
744 // Start insertion in LoopBB.
745 Builder.SetInsertPoint(LoopBB);
747 // Start the PHI node with an entry for Start.
748 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
749 Variable->addIncoming(StartVal, PreheaderBB);
753 <p>Now that the "preheader" for the loop is set up, we switch to emitting code
754 for the loop body. To begin with, we move the insertion point and create the
755 PHI node for the loop induction variable. Since we already know the incoming
756 value for the starting value, we add it to the Phi node. Note that the Phi will
757 eventually get a second value for the backedge, but we can't set it up yet
758 (because it doesn't exist!).</p>
760 <div class="doc_code">
762 // Within the loop, the variable is defined equal to the PHI node. If it
763 // shadows an existing variable, we have to restore it, so save it now.
764 Value *OldVal = NamedValues[VarName];
765 NamedValues[VarName] = Variable;
767 // Emit the body of the loop. This, like any other expr, can change the
768 // current BB. Note that we ignore the value computed by the body, but don't
770 if (Body->Codegen() == 0)
775 <p>Now the code starts to get more interesting. Our 'for' loop introduces a new
776 variable to the symbol table. This means that our symbol table can now contain
777 either function arguments or loop variables. To handle this, before we codegen
778 the body of the loop, we add the loop variable as the current value for its
779 name. Note that it is possible that there is a variable of the same name in the
780 outer scope. It would be easy to make this an error (emit an error and return
781 null if there is already an entry for VarName) but we choose to allow shadowing
782 of variables. In order to handle this correctly, we remember the Value that
783 we are potentially shadowing in <tt>OldVal</tt> (which will be null if there is
784 no shadowed variable).</p>
786 <p>Once the loop variable is set into the symbol table, the code recursively
787 codegen's the body. This allows the body to use the loop variable: any
788 references to it will naturally find it in the symbol table.</p>
790 <div class="doc_code">
792 // Emit the step value.
795 StepVal = Step->Codegen();
796 if (StepVal == 0) return 0;
798 // If not specified, use 1.0.
799 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
802 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
806 <p>Now that the body is emitted, we compute the next value of the iteration
807 variable by adding the step value, or 1.0 if it isn't present. '<tt>NextVar</tt>'
808 will be the value of the loop variable on the next iteration of the loop.</p>
810 <div class="doc_code">
812 // Compute the end condition.
813 Value *EndCond = End->Codegen();
814 if (EndCond == 0) return EndCond;
816 // Convert condition to a bool by comparing equal to 0.0.
817 EndCond = Builder.CreateFCmpONE(EndCond,
818 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
823 <p>Finally, we evaluate the exit value of the loop, to determine whether the
824 loop should exit. This mirrors the condition evaluation for the if/then/else
827 <div class="doc_code">
829 // Create the "after loop" block and insert it.
830 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
831 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
833 // Insert the conditional branch into the end of LoopEndBB.
834 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
836 // Any new code will be inserted in AfterBB.
837 Builder.SetInsertPoint(AfterBB);
841 <p>With the code for the body of the loop complete, we just need to finish up
842 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
843 exit condition, it creates a conditional branch that chooses between executing
844 the loop again and exiting the loop. Any future code is emitted in the
845 "afterloop" block, so it sets the insertion position to it.</p>
847 <div class="doc_code">
849 // Add a new entry to the PHI node for the backedge.
850 Variable->addIncoming(NextVar, LoopEndBB);
852 // Restore the unshadowed variable.
854 NamedValues[VarName] = OldVal;
856 NamedValues.erase(VarName);
858 // for expr always returns 0.0.
859 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
864 <p>The final code handles various cleanups: now that we have the "NextVar"
865 value, we can add the incoming value to the loop PHI node. After that, we
866 remove the loop variable from the symbol table, so that it isn't in scope after
867 the for loop. Finally, code generation of the for loop always returns 0.0, so
868 that is what we return from <tt>ForExprAST::Codegen</tt>.</p>
870 <p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
871 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
872 to know. In the next chapter of our saga, we will get a bit crazier and add
873 <a href="LangImpl6.html">user-defined operators</a> to our poor innocent
878 <!-- *********************************************************************** -->
879 <div class="doc_section"><a name="code">Full Code Listing</a></div>
880 <!-- *********************************************************************** -->
882 <div class="doc_text">
885 Here is the complete code listing for our running example, enhanced with the
886 if/then/else and for expressions.. To build this example, use:
889 <div class="doc_code">
892 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
898 <p>Here is the code:</p>
900 <div class="doc_code">
902 #include "llvm/DerivedTypes.h"
903 #include "llvm/ExecutionEngine/ExecutionEngine.h"
904 #include "llvm/ExecutionEngine/Interpreter.h"
905 #include "llvm/ExecutionEngine/JIT.h"
906 #include "llvm/LLVMContext.h"
907 #include "llvm/Module.h"
908 #include "llvm/ModuleProvider.h"
909 #include "llvm/PassManager.h"
910 #include "llvm/Analysis/Verifier.h"
911 #include "llvm/Target/TargetData.h"
912 #include "llvm/Target/TargetSelect.h"
913 #include "llvm/Transforms/Scalar.h"
914 #include "llvm/Support/IRBuilder.h"
915 #include <cstdio>
916 #include <string>
918 #include <vector>
919 using namespace llvm;
921 //===----------------------------------------------------------------------===//
923 //===----------------------------------------------------------------------===//
925 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
926 // of these for known things.
931 tok_def = -2, tok_extern = -3,
934 tok_identifier = -4, tok_number = -5,
937 tok_if = -6, tok_then = -7, tok_else = -8,
938 tok_for = -9, tok_in = -10
941 static std::string IdentifierStr; // Filled in if tok_identifier
942 static double NumVal; // Filled in if tok_number
944 /// gettok - Return the next token from standard input.
945 static int gettok() {
946 static int LastChar = ' ';
948 // Skip any whitespace.
949 while (isspace(LastChar))
950 LastChar = getchar();
952 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
953 IdentifierStr = LastChar;
954 while (isalnum((LastChar = getchar())))
955 IdentifierStr += LastChar;
957 if (IdentifierStr == "def") return tok_def;
958 if (IdentifierStr == "extern") return tok_extern;
959 if (IdentifierStr == "if") return tok_if;
960 if (IdentifierStr == "then") return tok_then;
961 if (IdentifierStr == "else") return tok_else;
962 if (IdentifierStr == "for") return tok_for;
963 if (IdentifierStr == "in") return tok_in;
964 return tok_identifier;
967 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
971 LastChar = getchar();
972 } while (isdigit(LastChar) || LastChar == '.');
974 NumVal = strtod(NumStr.c_str(), 0);
978 if (LastChar == '#') {
979 // Comment until end of line.
980 do LastChar = getchar();
981 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
987 // Check for end of file. Don't eat the EOF.
991 // Otherwise, just return the character as its ascii value.
992 int ThisChar = LastChar;
993 LastChar = getchar();
997 //===----------------------------------------------------------------------===//
998 // Abstract Syntax Tree (aka Parse Tree)
999 //===----------------------------------------------------------------------===//
1001 /// ExprAST - Base class for all expression nodes.
1004 virtual ~ExprAST() {}
1005 virtual Value *Codegen() = 0;
1008 /// NumberExprAST - Expression class for numeric literals like "1.0".
1009 class NumberExprAST : public ExprAST {
1012 NumberExprAST(double val) : Val(val) {}
1013 virtual Value *Codegen();
1016 /// VariableExprAST - Expression class for referencing a variable, like "a".
1017 class VariableExprAST : public ExprAST {
1020 VariableExprAST(const std::string &name) : Name(name) {}
1021 virtual Value *Codegen();
1024 /// BinaryExprAST - Expression class for a binary operator.
1025 class BinaryExprAST : public ExprAST {
1029 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
1030 : Op(op), LHS(lhs), RHS(rhs) {}
1031 virtual Value *Codegen();
1034 /// CallExprAST - Expression class for function calls.
1035 class CallExprAST : public ExprAST {
1037 std::vector<ExprAST*> Args;
1039 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
1040 : Callee(callee), Args(args) {}
1041 virtual Value *Codegen();
1044 /// IfExprAST - Expression class for if/then/else.
1045 class IfExprAST : public ExprAST {
1046 ExprAST *Cond, *Then, *Else;
1048 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1049 : Cond(cond), Then(then), Else(_else) {}
1050 virtual Value *Codegen();
1053 /// ForExprAST - Expression class for for/in.
1054 class ForExprAST : public ExprAST {
1055 std::string VarName;
1056 ExprAST *Start, *End, *Step, *Body;
1058 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
1059 ExprAST *step, ExprAST *body)
1060 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1061 virtual Value *Codegen();
1064 /// PrototypeAST - This class represents the "prototype" for a function,
1065 /// which captures its argument names as well as if it is an operator.
1066 class PrototypeAST {
1068 std::vector<std::string> Args;
1070 PrototypeAST(const std::string &name, const std::vector<std::string> &args)
1071 : Name(name), Args(args) {}
1073 Function *Codegen();
1076 /// FunctionAST - This class represents a function definition itself.
1078 PrototypeAST *Proto;
1081 FunctionAST(PrototypeAST *proto, ExprAST *body)
1082 : Proto(proto), Body(body) {}
1084 Function *Codegen();
1087 //===----------------------------------------------------------------------===//
1089 //===----------------------------------------------------------------------===//
1091 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1092 /// token the parser it looking at. getNextToken reads another token from the
1093 /// lexer and updates CurTok with its results.
1095 static int getNextToken() {
1096 return CurTok = gettok();
1099 /// BinopPrecedence - This holds the precedence for each binary operator that is
1101 static std::map<char, int> BinopPrecedence;
1103 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1104 static int GetTokPrecedence() {
1105 if (!isascii(CurTok))
1108 // Make sure it's a declared binop.
1109 int TokPrec = BinopPrecedence[CurTok];
1110 if (TokPrec <= 0) return -1;
1114 /// Error* - These are little helper functions for error handling.
1115 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1116 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1117 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1119 static ExprAST *ParseExpression();
1123 /// ::= identifier '(' expression* ')'
1124 static ExprAST *ParseIdentifierExpr() {
1125 std::string IdName = IdentifierStr;
1127 getNextToken(); // eat identifier.
1129 if (CurTok != '(') // Simple variable ref.
1130 return new VariableExprAST(IdName);
1133 getNextToken(); // eat (
1134 std::vector<ExprAST*> Args;
1135 if (CurTok != ')') {
1137 ExprAST *Arg = ParseExpression();
1139 Args.push_back(Arg);
1141 if (CurTok == ')') break;
1144 return Error("Expected ')' or ',' in argument list");
1152 return new CallExprAST(IdName, Args);
1155 /// numberexpr ::= number
1156 static ExprAST *ParseNumberExpr() {
1157 ExprAST *Result = new NumberExprAST(NumVal);
1158 getNextToken(); // consume the number
1162 /// parenexpr ::= '(' expression ')'
1163 static ExprAST *ParseParenExpr() {
1164 getNextToken(); // eat (.
1165 ExprAST *V = ParseExpression();
1169 return Error("expected ')'");
1170 getNextToken(); // eat ).
1174 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1175 static ExprAST *ParseIfExpr() {
1176 getNextToken(); // eat the if.
1179 ExprAST *Cond = ParseExpression();
1180 if (!Cond) return 0;
1182 if (CurTok != tok_then)
1183 return Error("expected then");
1184 getNextToken(); // eat the then
1186 ExprAST *Then = ParseExpression();
1187 if (Then == 0) return 0;
1189 if (CurTok != tok_else)
1190 return Error("expected else");
1194 ExprAST *Else = ParseExpression();
1195 if (!Else) return 0;
1197 return new IfExprAST(Cond, Then, Else);
1200 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1201 static ExprAST *ParseForExpr() {
1202 getNextToken(); // eat the for.
1204 if (CurTok != tok_identifier)
1205 return Error("expected identifier after for");
1207 std::string IdName = IdentifierStr;
1208 getNextToken(); // eat identifier.
1211 return Error("expected '=' after for");
1212 getNextToken(); // eat '='.
1215 ExprAST *Start = ParseExpression();
1216 if (Start == 0) return 0;
1218 return Error("expected ',' after for start value");
1221 ExprAST *End = ParseExpression();
1222 if (End == 0) return 0;
1224 // The step value is optional.
1226 if (CurTok == ',') {
1228 Step = ParseExpression();
1229 if (Step == 0) return 0;
1232 if (CurTok != tok_in)
1233 return Error("expected 'in' after for");
1234 getNextToken(); // eat 'in'.
1236 ExprAST *Body = ParseExpression();
1237 if (Body == 0) return 0;
1239 return new ForExprAST(IdName, Start, End, Step, Body);
1244 /// ::= identifierexpr
1249 static ExprAST *ParsePrimary() {
1251 default: return Error("unknown token when expecting an expression");
1252 case tok_identifier: return ParseIdentifierExpr();
1253 case tok_number: return ParseNumberExpr();
1254 case '(': return ParseParenExpr();
1255 case tok_if: return ParseIfExpr();
1256 case tok_for: return ParseForExpr();
1261 /// ::= ('+' primary)*
1262 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1263 // If this is a binop, find its precedence.
1265 int TokPrec = GetTokPrecedence();
1267 // If this is a binop that binds at least as tightly as the current binop,
1268 // consume it, otherwise we are done.
1269 if (TokPrec < ExprPrec)
1272 // Okay, we know this is a binop.
1274 getNextToken(); // eat binop
1276 // Parse the primary expression after the binary operator.
1277 ExprAST *RHS = ParsePrimary();
1280 // If BinOp binds less tightly with RHS than the operator after RHS, let
1281 // the pending operator take RHS as its LHS.
1282 int NextPrec = GetTokPrecedence();
1283 if (TokPrec < NextPrec) {
1284 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1285 if (RHS == 0) return 0;
1289 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1294 /// ::= primary binoprhs
1296 static ExprAST *ParseExpression() {
1297 ExprAST *LHS = ParsePrimary();
1300 return ParseBinOpRHS(0, LHS);
1304 /// ::= id '(' id* ')'
1305 static PrototypeAST *ParsePrototype() {
1306 if (CurTok != tok_identifier)
1307 return ErrorP("Expected function name in prototype");
1309 std::string FnName = IdentifierStr;
1313 return ErrorP("Expected '(' in prototype");
1315 std::vector<std::string> ArgNames;
1316 while (getNextToken() == tok_identifier)
1317 ArgNames.push_back(IdentifierStr);
1319 return ErrorP("Expected ')' in prototype");
1322 getNextToken(); // eat ')'.
1324 return new PrototypeAST(FnName, ArgNames);
1327 /// definition ::= 'def' prototype expression
1328 static FunctionAST *ParseDefinition() {
1329 getNextToken(); // eat def.
1330 PrototypeAST *Proto = ParsePrototype();
1331 if (Proto == 0) return 0;
1333 if (ExprAST *E = ParseExpression())
1334 return new FunctionAST(Proto, E);
1338 /// toplevelexpr ::= expression
1339 static FunctionAST *ParseTopLevelExpr() {
1340 if (ExprAST *E = ParseExpression()) {
1341 // Make an anonymous proto.
1342 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
1343 return new FunctionAST(Proto, E);
1348 /// external ::= 'extern' prototype
1349 static PrototypeAST *ParseExtern() {
1350 getNextToken(); // eat extern.
1351 return ParsePrototype();
1354 //===----------------------------------------------------------------------===//
1356 //===----------------------------------------------------------------------===//
1358 static Module *TheModule;
1359 static IRBuilder<> Builder(getGlobalContext());
1360 static std::map<std::string, Value*> NamedValues;
1361 static FunctionPassManager *TheFPM;
1363 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1365 Value *NumberExprAST::Codegen() {
1366 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1369 Value *VariableExprAST::Codegen() {
1370 // Look this variable up in the function.
1371 Value *V = NamedValues[Name];
1372 return V ? V : ErrorV("Unknown variable name");
1375 Value *BinaryExprAST::Codegen() {
1376 Value *L = LHS->Codegen();
1377 Value *R = RHS->Codegen();
1378 if (L == 0 || R == 0) return 0;
1381 case '+': return Builder.CreateAdd(L, R, "addtmp");
1382 case '-': return Builder.CreateSub(L, R, "subtmp");
1383 case '*': return Builder.CreateMul(L, R, "multmp");
1385 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1386 // Convert bool 0/1 to double 0.0 or 1.0
1387 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1389 default: return ErrorV("invalid binary operator");
1393 Value *CallExprAST::Codegen() {
1394 // Look up the name in the global module table.
1395 Function *CalleeF = TheModule->getFunction(Callee);
1397 return ErrorV("Unknown function referenced");
1399 // If argument mismatch error.
1400 if (CalleeF->arg_size() != Args.size())
1401 return ErrorV("Incorrect # arguments passed");
1403 std::vector<Value*> ArgsV;
1404 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1405 ArgsV.push_back(Args[i]->Codegen());
1406 if (ArgsV.back() == 0) return 0;
1409 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1412 Value *IfExprAST::Codegen() {
1413 Value *CondV = Cond->Codegen();
1414 if (CondV == 0) return 0;
1416 // Convert condition to a bool by comparing equal to 0.0.
1417 CondV = Builder.CreateFCmpONE(CondV,
1418 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1421 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1423 // Create blocks for the then and else cases. Insert the 'then' block at the
1424 // end of the function.
1425 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1426 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1427 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1429 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1432 Builder.SetInsertPoint(ThenBB);
1434 Value *ThenV = Then->Codegen();
1435 if (ThenV == 0) return 0;
1437 Builder.CreateBr(MergeBB);
1438 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1439 ThenBB = Builder.GetInsertBlock();
1442 TheFunction->getBasicBlockList().push_back(ElseBB);
1443 Builder.SetInsertPoint(ElseBB);
1445 Value *ElseV = Else->Codegen();
1446 if (ElseV == 0) return 0;
1448 Builder.CreateBr(MergeBB);
1449 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1450 ElseBB = Builder.GetInsertBlock();
1452 // Emit merge block.
1453 TheFunction->getBasicBlockList().push_back(MergeBB);
1454 Builder.SetInsertPoint(MergeBB);
1455 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
1458 PN->addIncoming(ThenV, ThenBB);
1459 PN->addIncoming(ElseV, ElseBB);
1463 Value *ForExprAST::Codegen() {
1466 // start = startexpr
1469 // variable = phi [start, loopheader], [nextvariable, loopend]
1475 // nextvariable = variable + step
1476 // endcond = endexpr
1477 // br endcond, loop, endloop
1480 // Emit the start code first, without 'variable' in scope.
1481 Value *StartVal = Start->Codegen();
1482 if (StartVal == 0) return 0;
1484 // Make the new basic block for the loop header, inserting after current
1486 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1487 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1488 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1490 // Insert an explicit fall through from the current block to the LoopBB.
1491 Builder.CreateBr(LoopBB);
1493 // Start insertion in LoopBB.
1494 Builder.SetInsertPoint(LoopBB);
1496 // Start the PHI node with an entry for Start.
1497 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
1498 Variable->addIncoming(StartVal, PreheaderBB);
1500 // Within the loop, the variable is defined equal to the PHI node. If it
1501 // shadows an existing variable, we have to restore it, so save it now.
1502 Value *OldVal = NamedValues[VarName];
1503 NamedValues[VarName] = Variable;
1505 // Emit the body of the loop. This, like any other expr, can change the
1506 // current BB. Note that we ignore the value computed by the body, but don't
1508 if (Body->Codegen() == 0)
1511 // Emit the step value.
1514 StepVal = Step->Codegen();
1515 if (StepVal == 0) return 0;
1517 // If not specified, use 1.0.
1518 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1521 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
1523 // Compute the end condition.
1524 Value *EndCond = End->Codegen();
1525 if (EndCond == 0) return EndCond;
1527 // Convert condition to a bool by comparing equal to 0.0.
1528 EndCond = Builder.CreateFCmpONE(EndCond,
1529 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1532 // Create the "after loop" block and insert it.
1533 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1534 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1536 // Insert the conditional branch into the end of LoopEndBB.
1537 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1539 // Any new code will be inserted in AfterBB.
1540 Builder.SetInsertPoint(AfterBB);
1542 // Add a new entry to the PHI node for the backedge.
1543 Variable->addIncoming(NextVar, LoopEndBB);
1545 // Restore the unshadowed variable.
1547 NamedValues[VarName] = OldVal;
1549 NamedValues.erase(VarName);
1552 // for expr always returns 0.0.
1553 return getGlobalContext().getNullValue(Type::getDoubleTy(getGlobalContext()));
1556 Function *PrototypeAST::Codegen() {
1557 // Make the function type: double(double,double) etc.
1558 std::vector<const Type*> Doubles(Args.size(),
1559 Type::getDoubleTy(getGlobalContext()));
1560 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1563 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1565 // If F conflicted, there was already something named 'Name'. If it has a
1566 // body, don't allow redefinition or reextern.
1567 if (F->getName() != Name) {
1568 // Delete the one we just made and get the existing one.
1569 F->eraseFromParent();
1570 F = TheModule->getFunction(Name);
1572 // If F already has a body, reject this.
1573 if (!F->empty()) {
1574 ErrorF("redefinition of function");
1578 // If F took a different number of args, reject.
1579 if (F->arg_size() != Args.size()) {
1580 ErrorF("redefinition of function with different # args");
1585 // Set names for all arguments.
1587 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1589 AI->setName(Args[Idx]);
1591 // Add arguments to variable symbol table.
1592 NamedValues[Args[Idx]] = AI;
1598 Function *FunctionAST::Codegen() {
1599 NamedValues.clear();
1601 Function *TheFunction = Proto->Codegen();
1602 if (TheFunction == 0)
1605 // Create a new basic block to start insertion into.
1606 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1607 Builder.SetInsertPoint(BB);
1609 if (Value *RetVal = Body->Codegen()) {
1610 // Finish off the function.
1611 Builder.CreateRet(RetVal);
1613 // Validate the generated code, checking for consistency.
1614 verifyFunction(*TheFunction);
1616 // Optimize the function.
1617 TheFPM->run(*TheFunction);
1622 // Error reading body, remove function.
1623 TheFunction->eraseFromParent();
1627 //===----------------------------------------------------------------------===//
1628 // Top-Level parsing and JIT Driver
1629 //===----------------------------------------------------------------------===//
1631 static ExecutionEngine *TheExecutionEngine;
1633 static void HandleDefinition() {
1634 if (FunctionAST *F = ParseDefinition()) {
1635 if (Function *LF = F->Codegen()) {
1636 fprintf(stderr, "Read function definition:");
1640 // Skip token for error recovery.
1645 static void HandleExtern() {
1646 if (PrototypeAST *P = ParseExtern()) {
1647 if (Function *F = P->Codegen()) {
1648 fprintf(stderr, "Read extern: ");
1652 // Skip token for error recovery.
1657 static void HandleTopLevelExpression() {
1658 // Evaluate a top level expression into an anonymous function.
1659 if (FunctionAST *F = ParseTopLevelExpr()) {
1660 if (Function *LF = F->Codegen()) {
1661 // JIT the function, returning a function pointer.
1662 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1664 // Cast it to the right type (takes no arguments, returns a double) so we
1665 // can call it as a native function.
1666 double (*FP)() = (double (*)())(intptr_t)FPtr;
1667 fprintf(stderr, "Evaluated to %f\n", FP());
1670 // Skip token for error recovery.
1675 /// top ::= definition | external | expression | ';'
1676 static void MainLoop() {
1678 fprintf(stderr, "ready> ");
1680 case tok_eof: return;
1681 case ';': getNextToken(); break; // ignore top level semicolons.
1682 case tok_def: HandleDefinition(); break;
1683 case tok_extern: HandleExtern(); break;
1684 default: HandleTopLevelExpression(); break;
1691 //===----------------------------------------------------------------------===//
1692 // "Library" functions that can be "extern'd" from user code.
1693 //===----------------------------------------------------------------------===//
1695 /// putchard - putchar that takes a double and returns 0.
1697 double putchard(double X) {
1702 //===----------------------------------------------------------------------===//
1703 // Main driver code.
1704 //===----------------------------------------------------------------------===//
1707 // Install standard binary operators.
1708 // 1 is lowest precedence.
1709 BinopPrecedence['<'] = 10;
1710 BinopPrecedence['+'] = 20;
1711 BinopPrecedence['-'] = 20;
1712 BinopPrecedence['*'] = 40; // highest.
1714 // Prime the first token.
1715 fprintf(stderr, "ready> ");
1718 // Make the module, which holds all the code.
1719 TheModule = new Module("my cool jit", getGlobalContext());
1721 ExistingModuleProvider *OurModuleProvider =
1722 new ExistingModuleProvider(TheModule);
1724 // Create the JIT. This takes ownership of the module and module provider.
1725 TheExecutionEngine = EngineBuilder(OurModuleProvider).create();
1727 FunctionPassManager OurFPM(OurModuleProvider);
1729 // Set up the optimizer pipeline. Start with registering info about how the
1730 // target lays out data structures.
1731 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1732 // Do simple "peephole" optimizations and bit-twiddling optzns.
1733 OurFPM.add(createInstructionCombiningPass());
1734 // Reassociate expressions.
1735 OurFPM.add(createReassociatePass());
1736 // Eliminate Common SubExpressions.
1737 OurFPM.add(createGVNPass());
1738 // Simplify the control flow graph (deleting unreachable blocks, etc).
1739 OurFPM.add(createCFGSimplificationPass());
1741 OurFPM.doInitialization();
1743 // Set the global so the code gen can use this.
1744 TheFPM = &OurFPM;
1746 // Run the main "interpreter loop" now.
1751 // Print out all of the generated code.
1752 TheModule->dump();
1759 <a href="LangImpl6.html">Next: Extending the language: user-defined operators</a>
1762 <!-- *********************************************************************** -->
1765 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1766 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1767 <a href="http://validator.w3.org/check/referer"><img
1768 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1770 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1771 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1772 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $