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 <h1>Kaleidoscope: Extending the Language: Control Flow</h1>
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 <h2><a name="intro">Chapter 5 Introduction</a></h2>
52 <!-- *********************************************************************** -->
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 <h2><a name="ifthen">If/Then/Else</a></h2>
69 <!-- *********************************************************************** -->
74 Extending Kaleidoscope to support if/then/else is quite straightforward. It
75 basically requires adding 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
111 <!-- ======================================================================= -->
112 <h4><a name="iflexer">Lexer Extensions for If/Then/Else</a></h4>
113 <!-- ======================================================================= -->
118 <p>The lexer extensions are straightforward. First we add new enum values
119 for the relevant tokens:</p>
121 <div class="doc_code">
124 tok_if = -6, tok_then = -7, tok_else = -8,
128 <p>Once we have that, we recognize the new keywords in the lexer. This is pretty simple
131 <div class="doc_code">
134 if (IdentifierStr == "def") return tok_def;
135 if (IdentifierStr == "extern") return tok_extern;
136 <b>if (IdentifierStr == "if") return tok_if;
137 if (IdentifierStr == "then") return tok_then;
138 if (IdentifierStr == "else") return tok_else;</b>
139 return tok_identifier;
145 <!-- ======================================================================= -->
146 <h4><a name="ifast">AST Extensions for If/Then/Else</a></h4>
147 <!-- ======================================================================= -->
151 <p>To represent the new expression we add a new AST node for it:</p>
153 <div class="doc_code">
155 /// IfExprAST - Expression class for if/then/else.
156 class IfExprAST : public ExprAST {
157 ExprAST *Cond, *Then, *Else;
159 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
160 : Cond(cond), Then(then), Else(_else) {}
161 virtual Value *Codegen();
166 <p>The AST node just has pointers to the various subexpressions.</p>
170 <!-- ======================================================================= -->
171 <h4><a name="ifparser">Parser Extensions for If/Then/Else</a></h4>
172 <!-- ======================================================================= -->
176 <p>Now that we have the relevant tokens coming from the lexer and we have the
177 AST node to build, our parsing logic is relatively straightforward. First we
178 define a new parsing function:</p>
180 <div class="doc_code">
182 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
183 static ExprAST *ParseIfExpr() {
184 getNextToken(); // eat the if.
187 ExprAST *Cond = ParseExpression();
190 if (CurTok != tok_then)
191 return Error("expected then");
192 getNextToken(); // eat the then
194 ExprAST *Then = ParseExpression();
195 if (Then == 0) return 0;
197 if (CurTok != tok_else)
198 return Error("expected else");
202 ExprAST *Else = ParseExpression();
205 return new IfExprAST(Cond, Then, Else);
210 <p>Next we hook it up as a primary expression:</p>
212 <div class="doc_code">
214 static ExprAST *ParsePrimary() {
216 default: return Error("unknown token when expecting an expression");
217 case tok_identifier: return ParseIdentifierExpr();
218 case tok_number: return ParseNumberExpr();
219 case '(': return ParseParenExpr();
220 <b>case tok_if: return ParseIfExpr();</b>
228 <!-- ======================================================================= -->
229 <h4><a name="ifir">LLVM IR for If/Then/Else</a></h4>
230 <!-- ======================================================================= -->
234 <p>Now that we have it parsing and building the AST, the final piece is adding
235 LLVM code generation support. This is the most interesting part of the
236 if/then/else example, because this is where it starts to introduce new concepts.
237 All of the code above has been thoroughly described in previous chapters.
240 <p>To motivate the code we want to produce, lets take a look at a simple
241 example. Consider:</p>
243 <div class="doc_code">
247 def baz(x) if x then foo() else bar();
251 <p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
254 <div class="doc_code">
256 declare double @foo()
258 declare double @bar()
260 define double @baz(double %x) {
262 %ifcond = fcmp one double %x, 0.000000e+00
263 br i1 %ifcond, label %then, label %else
265 then: ; preds = %entry
266 %calltmp = call double @foo()
269 else: ; preds = %entry
270 %calltmp1 = call double @bar()
273 ifcont: ; preds = %else, %then
274 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
280 <p>To visualize the control flow graph, you can use a nifty feature of the LLVM
281 '<a href="http://llvm.org/cmds/opt.html">opt</a>' tool. If you put this LLVM IR
282 into "t.ll" and run "<tt>llvm-as < t.ll | opt -analyze -view-cfg</tt>", <a
283 href="../ProgrammersManual.html#ViewGraph">a window will pop up</a> and you'll
286 <div style="text-align: center"><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
289 <p>Another way to get this is to call "<tt>F->viewCFG()</tt>" or
290 "<tt>F->viewCFGOnly()</tt>" (where F is a "<tt>Function*</tt>") either by
291 inserting actual calls into the code and recompiling or by calling these in the
292 debugger. LLVM has many nice features for visualizing various graphs.</p>
294 <p>Getting back to the generated code, it is fairly simple: the entry block
295 evaluates the conditional expression ("x" in our case here) and compares the
296 result to 0.0 with the "<tt><a href="../LangRef.html#i_fcmp">fcmp</a> one</tt>"
297 instruction ('one' is "Ordered and Not Equal"). Based on the result of this
298 expression, the code jumps to either the "then" or "else" blocks, which contain
299 the expressions for the true/false cases.</p>
301 <p>Once the then/else blocks are finished executing, they both branch back to the
302 'ifcont' block to execute the code that happens after the if/then/else. In this
303 case the only thing left to do is to return to the caller of the function. The
304 question then becomes: how does the code know which expression to return?</p>
306 <p>The answer to this question involves an important SSA operation: the
307 <a href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Phi
308 operation</a>. If you're not familiar with SSA, <a
309 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">the wikipedia
310 article</a> is a good introduction and there are various other introductions to
311 it available on your favorite search engine. The short version is that
312 "execution" of the Phi operation requires "remembering" which block control came
313 from. The Phi operation takes on the value corresponding to the input control
314 block. In this case, if control comes in from the "then" block, it gets the
315 value of "calltmp". If control comes from the "else" block, it gets the value
318 <p>At this point, you are probably starting to think "Oh no! This means my
319 simple and elegant front-end will have to start generating SSA form in order to
320 use LLVM!". Fortunately, this is not the case, and we strongly advise
321 <em>not</em> implementing an SSA construction algorithm in your front-end
322 unless there is an amazingly good reason to do so. In practice, there are two
323 sorts of values that float around in code written for your average imperative
324 programming language that might need Phi nodes:</p>
327 <li>Code that involves user variables: <tt>x = 1; x = x + 1; </tt></li>
328 <li>Values that are implicit in the structure of your AST, such as the Phi node
332 <p>In <a href="LangImpl7.html">Chapter 7</a> of this tutorial ("mutable
333 variables"), we'll talk about #1
334 in depth. For now, just believe me that you don't need SSA construction to
335 handle this case. For #2, you have the choice of using the techniques that we will
336 describe for #1, or you can insert Phi nodes directly, if convenient. In this
337 case, it is really really easy to generate the Phi node, so we choose to do it
340 <p>Okay, enough of the motivation and overview, lets generate code!</p>
344 <!-- ======================================================================= -->
345 <h4><a name="ifcodegen">Code Generation for If/Then/Else</a></h4>
346 <!-- ======================================================================= -->
350 <p>In order to generate code for this, we implement the <tt>Codegen</tt> method
351 for <tt>IfExprAST</tt>:</p>
353 <div class="doc_code">
355 Value *IfExprAST::Codegen() {
356 Value *CondV = Cond->Codegen();
357 if (CondV == 0) return 0;
359 // Convert condition to a bool by comparing equal to 0.0.
360 CondV = Builder.CreateFCmpONE(CondV,
361 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
366 <p>This code is straightforward and similar to what we saw before. We emit the
367 expression for the condition, then compare that value to zero to get a truth
368 value as a 1-bit (bool) value.</p>
370 <div class="doc_code">
372 Function *TheFunction = Builder.GetInsertBlock()->getParent();
374 // Create blocks for the then and else cases. Insert the 'then' block at the
375 // end of the function.
376 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
377 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
378 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
380 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
384 <p>This code creates the basic blocks that are related to the if/then/else
385 statement, and correspond directly to the blocks in the example above. The
386 first line gets the current Function object that is being built. It
387 gets this by asking the builder for the current BasicBlock, and asking that
388 block for its "parent" (the function it is currently embedded into).</p>
390 <p>Once it has that, it creates three blocks. Note that it passes "TheFunction"
391 into the constructor for the "then" block. This causes the constructor to
392 automatically insert the new block into the end of the specified function. The
393 other two blocks are created, but aren't yet inserted into the function.</p>
395 <p>Once the blocks are created, we can emit the conditional branch that chooses
396 between them. Note that creating new blocks does not implicitly affect the
397 IRBuilder, so it is still inserting into the block that the condition
398 went into. Also note that it is creating a branch to the "then" block and the
399 "else" block, even though the "else" block isn't inserted into the function yet.
400 This is all ok: it is the standard way that LLVM supports forward
403 <div class="doc_code">
406 Builder.SetInsertPoint(ThenBB);
408 Value *ThenV = Then->Codegen();
409 if (ThenV == 0) return 0;
411 Builder.CreateBr(MergeBB);
412 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
413 ThenBB = Builder.GetInsertBlock();
417 <p>After the conditional branch is inserted, we move the builder to start
418 inserting into the "then" block. Strictly speaking, this call moves the
419 insertion point to be at the end of the specified block. However, since the
420 "then" block is empty, it also starts out by inserting at the beginning of the
423 <p>Once the insertion point is set, we recursively codegen the "then" expression
424 from the AST. To finish off the "then" block, we create an unconditional branch
425 to the merge block. One interesting (and very important) aspect of the LLVM IR
426 is that it <a href="../LangRef.html#functionstructure">requires all basic blocks
427 to be "terminated"</a> with a <a href="../LangRef.html#terminators">control flow
428 instruction</a> such as return or branch. This means that all control flow,
429 <em>including fall throughs</em> must be made explicit in the LLVM IR. If you
430 violate this rule, the verifier will emit an error.</p>
432 <p>The final line here is quite subtle, but is very important. The basic issue
433 is that when we create the Phi node in the merge block, we need to set up the
434 block/value pairs that indicate how the Phi will work. Importantly, the Phi
435 node expects to have an entry for each predecessor of the block in the CFG. Why
436 then, are we getting the current block when we just set it to ThenBB 5 lines
437 above? The problem is that the "Then" expression may actually itself change the
438 block that the Builder is emitting into if, for example, it contains a nested
439 "if/then/else" expression. Because calling Codegen recursively could
440 arbitrarily change the notion of the current block, we are required to get an
441 up-to-date value for code that will set up the Phi node.</p>
443 <div class="doc_code">
446 TheFunction->getBasicBlockList().push_back(ElseBB);
447 Builder.SetInsertPoint(ElseBB);
449 Value *ElseV = Else->Codegen();
450 if (ElseV == 0) return 0;
452 Builder.CreateBr(MergeBB);
453 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
454 ElseBB = Builder.GetInsertBlock();
458 <p>Code generation for the 'else' block is basically identical to codegen for
459 the 'then' block. The only significant difference is the first line, which adds
460 the 'else' block to the function. Recall previously that the 'else' block was
461 created, but not added to the function. Now that the 'then' and 'else' blocks
462 are emitted, we can finish up with the merge code:</p>
464 <div class="doc_code">
467 TheFunction->getBasicBlockList().push_back(MergeBB);
468 Builder.SetInsertPoint(MergeBB);
469 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
472 PN->addIncoming(ThenV, ThenBB);
473 PN->addIncoming(ElseV, ElseBB);
479 <p>The first two lines here are now familiar: the first adds the "merge" block
480 to the Function object (it was previously floating, like the else block above).
481 The second block changes the insertion point so that newly created code will go
482 into the "merge" block. Once that is done, we need to create the PHI node and
483 set up the block/value pairs for the PHI.</p>
485 <p>Finally, the CodeGen function returns the phi node as the value computed by
486 the if/then/else expression. In our example above, this returned value will
487 feed into the code for the top-level function, which will create the return
490 <p>Overall, we now have the ability to execute conditional code in
491 Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
492 that can calculate a wide variety of numeric functions. Next up we'll add
493 another useful expression that is familiar from non-functional languages...</p>
499 <!-- *********************************************************************** -->
500 <h2><a name="for">'for' Loop Expression</a></h2>
501 <!-- *********************************************************************** -->
505 <p>Now that we know how to add basic control flow constructs to the language,
506 we have the tools to add more powerful things. Lets add something more
507 aggressive, a 'for' expression:</p>
509 <div class="doc_code">
511 extern putchard(char)
513 for i = 1, i < n, 1.0 in
514 putchard(42); # ascii 42 = '*'
516 # print 100 '*' characters
521 <p>This expression defines a new variable ("i" in this case) which iterates from
522 a starting value, while the condition ("i < n" in this case) is true,
523 incrementing by an optional step value ("1.0" in this case). If the step value
524 is omitted, it defaults to 1.0. While the loop is true, it executes its
525 body expression. Because we don't have anything better to return, we'll just
526 define the loop as always returning 0.0. In the future when we have mutable
527 variables, it will get more useful.</p>
529 <p>As before, lets talk about the changes that we need to Kaleidoscope to
532 <!-- ======================================================================= -->
533 <h4><a name="forlexer">Lexer Extensions for the 'for' Loop</a></h4>
534 <!-- ======================================================================= -->
538 <p>The lexer extensions are the same sort of thing as for if/then/else:</p>
540 <div class="doc_code">
542 ... in enum Token ...
544 tok_if = -6, tok_then = -7, tok_else = -8,
545 <b> tok_for = -9, tok_in = -10</b>
548 if (IdentifierStr == "def") return tok_def;
549 if (IdentifierStr == "extern") return tok_extern;
550 if (IdentifierStr == "if") return tok_if;
551 if (IdentifierStr == "then") return tok_then;
552 if (IdentifierStr == "else") return tok_else;
553 <b>if (IdentifierStr == "for") return tok_for;
554 if (IdentifierStr == "in") return tok_in;</b>
555 return tok_identifier;
561 <!-- ======================================================================= -->
562 <h4><a name="forast">AST Extensions for the 'for' Loop</a></h4>
563 <!-- ======================================================================= -->
567 <p>The AST node is just as simple. It basically boils down to capturing
568 the variable name and the constituent expressions in the node.</p>
570 <div class="doc_code">
572 /// ForExprAST - Expression class for for/in.
573 class ForExprAST : public ExprAST {
575 ExprAST *Start, *End, *Step, *Body;
577 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
578 ExprAST *step, ExprAST *body)
579 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
580 virtual Value *Codegen();
587 <!-- ======================================================================= -->
588 <h4><a name="forparser">Parser Extensions for the 'for' Loop</a></h4>
589 <!-- ======================================================================= -->
593 <p>The parser code is also fairly standard. The only interesting thing here is
594 handling of the optional step value. The parser code handles it by checking to
595 see if the second comma is present. If not, it sets the step value to null in
598 <div class="doc_code">
600 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
601 static ExprAST *ParseForExpr() {
602 getNextToken(); // eat the for.
604 if (CurTok != tok_identifier)
605 return Error("expected identifier after for");
607 std::string IdName = IdentifierStr;
608 getNextToken(); // eat identifier.
611 return Error("expected '=' after for");
612 getNextToken(); // eat '='.
615 ExprAST *Start = ParseExpression();
616 if (Start == 0) return 0;
618 return Error("expected ',' after for start value");
621 ExprAST *End = ParseExpression();
622 if (End == 0) return 0;
624 // The step value is optional.
628 Step = ParseExpression();
629 if (Step == 0) return 0;
632 if (CurTok != tok_in)
633 return Error("expected 'in' after for");
634 getNextToken(); // eat 'in'.
636 ExprAST *Body = ParseExpression();
637 if (Body == 0) return 0;
639 return new ForExprAST(IdName, Start, End, Step, Body);
646 <!-- ======================================================================= -->
647 <h4><a name="forir">LLVM IR for the 'for' Loop</a></h4>
648 <!-- ======================================================================= -->
652 <p>Now we get to the good part: the LLVM IR we want to generate for this thing.
653 With the simple example above, we get this LLVM IR (note that this dump is
654 generated with optimizations disabled for clarity):
657 <div class="doc_code">
659 declare double @putchard(double)
661 define double @printstar(double %n) {
663 ; initial value = 1.0 (inlined into phi)
666 loop: ; preds = %loop, %entry
667 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
669 %calltmp = call double @putchard(double 4.200000e+01)
671 %nextvar = fadd double %i, 1.000000e+00
674 %cmptmp = fcmp ult double %i, %n
675 %booltmp = uitofp i1 %cmptmp to double
676 %loopcond = fcmp one double %booltmp, 0.000000e+00
677 br i1 %loopcond, label %loop, label %afterloop
679 afterloop: ; preds = %loop
680 ; loop always returns 0.0
681 ret double 0.000000e+00
686 <p>This loop contains all the same constructs we saw before: a phi node, several
687 expressions, and some basic blocks. Lets see how this fits together.</p>
691 <!-- ======================================================================= -->
692 <h4><a name="forcodegen">Code Generation for the 'for' Loop</a></h4>
693 <!-- ======================================================================= -->
697 <p>The first part of Codegen is very simple: we just output the start expression
698 for the loop value:</p>
700 <div class="doc_code">
702 Value *ForExprAST::Codegen() {
703 // Emit the start code first, without 'variable' in scope.
704 Value *StartVal = Start->Codegen();
705 if (StartVal == 0) return 0;
709 <p>With this out of the way, the next step is to set up the LLVM basic block
710 for the start of the loop body. In the case above, the whole loop body is one
711 block, but remember that the body code itself could consist of multiple blocks
712 (e.g. if it contains an if/then/else or a for/in expression).</p>
714 <div class="doc_code">
716 // Make the new basic block for the loop header, inserting after current
718 Function *TheFunction = Builder.GetInsertBlock()->getParent();
719 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
720 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
722 // Insert an explicit fall through from the current block to the LoopBB.
723 Builder.CreateBr(LoopBB);
727 <p>This code is similar to what we saw for if/then/else. Because we will need
728 it to create the Phi node, we remember the block that falls through into the
729 loop. Once we have that, we create the actual block that starts the loop and
730 create an unconditional branch for the fall-through between the two blocks.</p>
732 <div class="doc_code">
734 // Start insertion in LoopBB.
735 Builder.SetInsertPoint(LoopBB);
737 // Start the PHI node with an entry for Start.
738 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
739 Variable->addIncoming(StartVal, PreheaderBB);
743 <p>Now that the "preheader" for the loop is set up, we switch to emitting code
744 for the loop body. To begin with, we move the insertion point and create the
745 PHI node for the loop induction variable. Since we already know the incoming
746 value for the starting value, we add it to the Phi node. Note that the Phi will
747 eventually get a second value for the backedge, but we can't set it up yet
748 (because it doesn't exist!).</p>
750 <div class="doc_code">
752 // Within the loop, the variable is defined equal to the PHI node. If it
753 // shadows an existing variable, we have to restore it, so save it now.
754 Value *OldVal = NamedValues[VarName];
755 NamedValues[VarName] = Variable;
757 // Emit the body of the loop. This, like any other expr, can change the
758 // current BB. Note that we ignore the value computed by the body, but don't
760 if (Body->Codegen() == 0)
765 <p>Now the code starts to get more interesting. Our 'for' loop introduces a new
766 variable to the symbol table. This means that our symbol table can now contain
767 either function arguments or loop variables. To handle this, before we codegen
768 the body of the loop, we add the loop variable as the current value for its
769 name. Note that it is possible that there is a variable of the same name in the
770 outer scope. It would be easy to make this an error (emit an error and return
771 null if there is already an entry for VarName) but we choose to allow shadowing
772 of variables. In order to handle this correctly, we remember the Value that
773 we are potentially shadowing in <tt>OldVal</tt> (which will be null if there is
774 no shadowed variable).</p>
776 <p>Once the loop variable is set into the symbol table, the code recursively
777 codegen's the body. This allows the body to use the loop variable: any
778 references to it will naturally find it in the symbol table.</p>
780 <div class="doc_code">
782 // Emit the step value.
785 StepVal = Step->Codegen();
786 if (StepVal == 0) return 0;
788 // If not specified, use 1.0.
789 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
792 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
796 <p>Now that the body is emitted, we compute the next value of the iteration
797 variable by adding the step value, or 1.0 if it isn't present. '<tt>NextVar</tt>'
798 will be the value of the loop variable on the next iteration of the loop.</p>
800 <div class="doc_code">
802 // Compute the end condition.
803 Value *EndCond = End->Codegen();
804 if (EndCond == 0) return EndCond;
806 // Convert condition to a bool by comparing equal to 0.0.
807 EndCond = Builder.CreateFCmpONE(EndCond,
808 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
813 <p>Finally, we evaluate the exit value of the loop, to determine whether the
814 loop should exit. This mirrors the condition evaluation for the if/then/else
817 <div class="doc_code">
819 // Create the "after loop" block and insert it.
820 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
821 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
823 // Insert the conditional branch into the end of LoopEndBB.
824 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
826 // Any new code will be inserted in AfterBB.
827 Builder.SetInsertPoint(AfterBB);
831 <p>With the code for the body of the loop complete, we just need to finish up
832 the control flow for it. This code remembers the end block (for the phi node),
833 then creates the block for the loop exit ("afterloop"). Based on the value of
834 the exit condition, it creates a conditional branch that chooses between
835 executing the loop again and exiting the loop. Any future code is emitted in
836 the "afterloop" block, so it sets the insertion position to it.</p>
838 <div class="doc_code">
840 // Add a new entry to the PHI node for the backedge.
841 Variable->addIncoming(NextVar, LoopEndBB);
843 // Restore the unshadowed variable.
845 NamedValues[VarName] = OldVal;
847 NamedValues.erase(VarName);
849 // for expr always returns 0.0.
850 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
855 <p>The final code handles various cleanups: now that we have the "NextVar"
856 value, we can add the incoming value to the loop PHI node. After that, we
857 remove the loop variable from the symbol table, so that it isn't in scope after
858 the for loop. Finally, code generation of the for loop always returns 0.0, so
859 that is what we return from <tt>ForExprAST::Codegen</tt>.</p>
861 <p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
862 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
863 to know. In the next chapter of our saga, we will get a bit crazier and add
864 <a href="LangImpl6.html">user-defined operators</a> to our poor innocent
871 <!-- *********************************************************************** -->
872 <h2><a name="code">Full Code Listing</a></h2>
873 <!-- *********************************************************************** -->
878 Here is the complete code listing for our running example, enhanced with the
879 if/then/else and for expressions.. To build this example, use:
882 <div class="doc_code">
885 clang++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
891 <p>Here is the code:</p>
893 <div class="doc_code">
895 #include "llvm/DerivedTypes.h"
896 #include "llvm/ExecutionEngine/ExecutionEngine.h"
897 #include "llvm/ExecutionEngine/JIT.h"
898 #include "llvm/LLVMContext.h"
899 #include "llvm/Module.h"
900 #include "llvm/PassManager.h"
901 #include "llvm/Analysis/Verifier.h"
902 #include "llvm/Analysis/Passes.h"
903 #include "llvm/Target/TargetData.h"
904 #include "llvm/Transforms/Scalar.h"
905 #include "llvm/Support/IRBuilder.h"
906 #include "llvm/Support/TargetSelect.h"
907 #include <cstdio>
908 #include <string>
910 #include <vector>
911 using namespace llvm;
913 //===----------------------------------------------------------------------===//
915 //===----------------------------------------------------------------------===//
917 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
918 // of these for known things.
923 tok_def = -2, tok_extern = -3,
926 tok_identifier = -4, tok_number = -5,
929 tok_if = -6, tok_then = -7, tok_else = -8,
930 tok_for = -9, tok_in = -10
933 static std::string IdentifierStr; // Filled in if tok_identifier
934 static double NumVal; // Filled in if tok_number
936 /// gettok - Return the next token from standard input.
937 static int gettok() {
938 static int LastChar = ' ';
940 // Skip any whitespace.
941 while (isspace(LastChar))
942 LastChar = getchar();
944 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
945 IdentifierStr = LastChar;
946 while (isalnum((LastChar = getchar())))
947 IdentifierStr += LastChar;
949 if (IdentifierStr == "def") return tok_def;
950 if (IdentifierStr == "extern") return tok_extern;
951 if (IdentifierStr == "if") return tok_if;
952 if (IdentifierStr == "then") return tok_then;
953 if (IdentifierStr == "else") return tok_else;
954 if (IdentifierStr == "for") return tok_for;
955 if (IdentifierStr == "in") return tok_in;
956 return tok_identifier;
959 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
963 LastChar = getchar();
964 } while (isdigit(LastChar) || LastChar == '.');
966 NumVal = strtod(NumStr.c_str(), 0);
970 if (LastChar == '#') {
971 // Comment until end of line.
972 do LastChar = getchar();
973 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
979 // Check for end of file. Don't eat the EOF.
983 // Otherwise, just return the character as its ascii value.
984 int ThisChar = LastChar;
985 LastChar = getchar();
989 //===----------------------------------------------------------------------===//
990 // Abstract Syntax Tree (aka Parse Tree)
991 //===----------------------------------------------------------------------===//
993 /// ExprAST - Base class for all expression nodes.
996 virtual ~ExprAST() {}
997 virtual Value *Codegen() = 0;
1000 /// NumberExprAST - Expression class for numeric literals like "1.0".
1001 class NumberExprAST : public ExprAST {
1004 NumberExprAST(double val) : Val(val) {}
1005 virtual Value *Codegen();
1008 /// VariableExprAST - Expression class for referencing a variable, like "a".
1009 class VariableExprAST : public ExprAST {
1012 VariableExprAST(const std::string &name) : Name(name) {}
1013 virtual Value *Codegen();
1016 /// BinaryExprAST - Expression class for a binary operator.
1017 class BinaryExprAST : public ExprAST {
1021 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
1022 : Op(op), LHS(lhs), RHS(rhs) {}
1023 virtual Value *Codegen();
1026 /// CallExprAST - Expression class for function calls.
1027 class CallExprAST : public ExprAST {
1029 std::vector<ExprAST*> Args;
1031 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
1032 : Callee(callee), Args(args) {}
1033 virtual Value *Codegen();
1036 /// IfExprAST - Expression class for if/then/else.
1037 class IfExprAST : public ExprAST {
1038 ExprAST *Cond, *Then, *Else;
1040 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1041 : Cond(cond), Then(then), Else(_else) {}
1042 virtual Value *Codegen();
1045 /// ForExprAST - Expression class for for/in.
1046 class ForExprAST : public ExprAST {
1047 std::string VarName;
1048 ExprAST *Start, *End, *Step, *Body;
1050 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
1051 ExprAST *step, ExprAST *body)
1052 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1053 virtual Value *Codegen();
1056 /// PrototypeAST - This class represents the "prototype" for a function,
1057 /// which captures its name, and its argument names (thus implicitly the number
1058 /// of arguments the function takes).
1059 class PrototypeAST {
1061 std::vector<std::string> Args;
1063 PrototypeAST(const std::string &name, const std::vector<std::string> &args)
1064 : Name(name), Args(args) {}
1066 Function *Codegen();
1069 /// FunctionAST - This class represents a function definition itself.
1071 PrototypeAST *Proto;
1074 FunctionAST(PrototypeAST *proto, ExprAST *body)
1075 : Proto(proto), Body(body) {}
1077 Function *Codegen();
1080 //===----------------------------------------------------------------------===//
1082 //===----------------------------------------------------------------------===//
1084 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1085 /// token the parser is looking at. getNextToken reads another token from the
1086 /// lexer and updates CurTok with its results.
1088 static int getNextToken() {
1089 return CurTok = gettok();
1092 /// BinopPrecedence - This holds the precedence for each binary operator that is
1094 static std::map<char, int> BinopPrecedence;
1096 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1097 static int GetTokPrecedence() {
1098 if (!isascii(CurTok))
1101 // Make sure it's a declared binop.
1102 int TokPrec = BinopPrecedence[CurTok];
1103 if (TokPrec <= 0) return -1;
1107 /// Error* - These are little helper functions for error handling.
1108 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1109 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1110 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1112 static ExprAST *ParseExpression();
1116 /// ::= identifier '(' expression* ')'
1117 static ExprAST *ParseIdentifierExpr() {
1118 std::string IdName = IdentifierStr;
1120 getNextToken(); // eat identifier.
1122 if (CurTok != '(') // Simple variable ref.
1123 return new VariableExprAST(IdName);
1126 getNextToken(); // eat (
1127 std::vector<ExprAST*> Args;
1128 if (CurTok != ')') {
1130 ExprAST *Arg = ParseExpression();
1132 Args.push_back(Arg);
1134 if (CurTok == ')') break;
1137 return Error("Expected ')' or ',' in argument list");
1145 return new CallExprAST(IdName, Args);
1148 /// numberexpr ::= number
1149 static ExprAST *ParseNumberExpr() {
1150 ExprAST *Result = new NumberExprAST(NumVal);
1151 getNextToken(); // consume the number
1155 /// parenexpr ::= '(' expression ')'
1156 static ExprAST *ParseParenExpr() {
1157 getNextToken(); // eat (.
1158 ExprAST *V = ParseExpression();
1162 return Error("expected ')'");
1163 getNextToken(); // eat ).
1167 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1168 static ExprAST *ParseIfExpr() {
1169 getNextToken(); // eat the if.
1172 ExprAST *Cond = ParseExpression();
1173 if (!Cond) return 0;
1175 if (CurTok != tok_then)
1176 return Error("expected then");
1177 getNextToken(); // eat the then
1179 ExprAST *Then = ParseExpression();
1180 if (Then == 0) return 0;
1182 if (CurTok != tok_else)
1183 return Error("expected else");
1187 ExprAST *Else = ParseExpression();
1188 if (!Else) return 0;
1190 return new IfExprAST(Cond, Then, Else);
1193 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1194 static ExprAST *ParseForExpr() {
1195 getNextToken(); // eat the for.
1197 if (CurTok != tok_identifier)
1198 return Error("expected identifier after for");
1200 std::string IdName = IdentifierStr;
1201 getNextToken(); // eat identifier.
1204 return Error("expected '=' after for");
1205 getNextToken(); // eat '='.
1208 ExprAST *Start = ParseExpression();
1209 if (Start == 0) return 0;
1211 return Error("expected ',' after for start value");
1214 ExprAST *End = ParseExpression();
1215 if (End == 0) return 0;
1217 // The step value is optional.
1219 if (CurTok == ',') {
1221 Step = ParseExpression();
1222 if (Step == 0) return 0;
1225 if (CurTok != tok_in)
1226 return Error("expected 'in' after for");
1227 getNextToken(); // eat 'in'.
1229 ExprAST *Body = ParseExpression();
1230 if (Body == 0) return 0;
1232 return new ForExprAST(IdName, Start, End, Step, Body);
1236 /// ::= identifierexpr
1241 static ExprAST *ParsePrimary() {
1243 default: return Error("unknown token when expecting an expression");
1244 case tok_identifier: return ParseIdentifierExpr();
1245 case tok_number: return ParseNumberExpr();
1246 case '(': return ParseParenExpr();
1247 case tok_if: return ParseIfExpr();
1248 case tok_for: return ParseForExpr();
1253 /// ::= ('+' primary)*
1254 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1255 // If this is a binop, find its precedence.
1257 int TokPrec = GetTokPrecedence();
1259 // If this is a binop that binds at least as tightly as the current binop,
1260 // consume it, otherwise we are done.
1261 if (TokPrec < ExprPrec)
1264 // Okay, we know this is a binop.
1266 getNextToken(); // eat binop
1268 // Parse the primary expression after the binary operator.
1269 ExprAST *RHS = ParsePrimary();
1272 // If BinOp binds less tightly with RHS than the operator after RHS, let
1273 // the pending operator take RHS as its LHS.
1274 int NextPrec = GetTokPrecedence();
1275 if (TokPrec < NextPrec) {
1276 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1277 if (RHS == 0) return 0;
1281 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1286 /// ::= primary binoprhs
1288 static ExprAST *ParseExpression() {
1289 ExprAST *LHS = ParsePrimary();
1292 return ParseBinOpRHS(0, LHS);
1296 /// ::= id '(' id* ')'
1297 static PrototypeAST *ParsePrototype() {
1298 if (CurTok != tok_identifier)
1299 return ErrorP("Expected function name in prototype");
1301 std::string FnName = IdentifierStr;
1305 return ErrorP("Expected '(' in prototype");
1307 std::vector<std::string> ArgNames;
1308 while (getNextToken() == tok_identifier)
1309 ArgNames.push_back(IdentifierStr);
1311 return ErrorP("Expected ')' in prototype");
1314 getNextToken(); // eat ')'.
1316 return new PrototypeAST(FnName, ArgNames);
1319 /// definition ::= 'def' prototype expression
1320 static FunctionAST *ParseDefinition() {
1321 getNextToken(); // eat def.
1322 PrototypeAST *Proto = ParsePrototype();
1323 if (Proto == 0) return 0;
1325 if (ExprAST *E = ParseExpression())
1326 return new FunctionAST(Proto, E);
1330 /// toplevelexpr ::= expression
1331 static FunctionAST *ParseTopLevelExpr() {
1332 if (ExprAST *E = ParseExpression()) {
1333 // Make an anonymous proto.
1334 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
1335 return new FunctionAST(Proto, E);
1340 /// external ::= 'extern' prototype
1341 static PrototypeAST *ParseExtern() {
1342 getNextToken(); // eat extern.
1343 return ParsePrototype();
1346 //===----------------------------------------------------------------------===//
1348 //===----------------------------------------------------------------------===//
1350 static Module *TheModule;
1351 static IRBuilder<> Builder(getGlobalContext());
1352 static std::map<std::string, Value*> NamedValues;
1353 static FunctionPassManager *TheFPM;
1355 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1357 Value *NumberExprAST::Codegen() {
1358 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1361 Value *VariableExprAST::Codegen() {
1362 // Look this variable up in the function.
1363 Value *V = NamedValues[Name];
1364 return V ? V : ErrorV("Unknown variable name");
1367 Value *BinaryExprAST::Codegen() {
1368 Value *L = LHS->Codegen();
1369 Value *R = RHS->Codegen();
1370 if (L == 0 || R == 0) return 0;
1373 case '+': return Builder.CreateFAdd(L, R, "addtmp");
1374 case '-': return Builder.CreateFSub(L, R, "subtmp");
1375 case '*': return Builder.CreateFMul(L, R, "multmp");
1377 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1378 // Convert bool 0/1 to double 0.0 or 1.0
1379 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1381 default: return ErrorV("invalid binary operator");
1385 Value *CallExprAST::Codegen() {
1386 // Look up the name in the global module table.
1387 Function *CalleeF = TheModule->getFunction(Callee);
1389 return ErrorV("Unknown function referenced");
1391 // If argument mismatch error.
1392 if (CalleeF->arg_size() != Args.size())
1393 return ErrorV("Incorrect # arguments passed");
1395 std::vector<Value*> ArgsV;
1396 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1397 ArgsV.push_back(Args[i]->Codegen());
1398 if (ArgsV.back() == 0) return 0;
1401 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
1404 Value *IfExprAST::Codegen() {
1405 Value *CondV = Cond->Codegen();
1406 if (CondV == 0) return 0;
1408 // Convert condition to a bool by comparing equal to 0.0.
1409 CondV = Builder.CreateFCmpONE(CondV,
1410 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1413 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1415 // Create blocks for the then and else cases. Insert the 'then' block at the
1416 // end of the function.
1417 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1418 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1419 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1421 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1424 Builder.SetInsertPoint(ThenBB);
1426 Value *ThenV = Then->Codegen();
1427 if (ThenV == 0) return 0;
1429 Builder.CreateBr(MergeBB);
1430 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1431 ThenBB = Builder.GetInsertBlock();
1434 TheFunction->getBasicBlockList().push_back(ElseBB);
1435 Builder.SetInsertPoint(ElseBB);
1437 Value *ElseV = Else->Codegen();
1438 if (ElseV == 0) return 0;
1440 Builder.CreateBr(MergeBB);
1441 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1442 ElseBB = Builder.GetInsertBlock();
1444 // Emit merge block.
1445 TheFunction->getBasicBlockList().push_back(MergeBB);
1446 Builder.SetInsertPoint(MergeBB);
1447 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
1450 PN->addIncoming(ThenV, ThenBB);
1451 PN->addIncoming(ElseV, ElseBB);
1455 Value *ForExprAST::Codegen() {
1458 // start = startexpr
1461 // variable = phi [start, loopheader], [nextvariable, loopend]
1467 // nextvariable = variable + step
1468 // endcond = endexpr
1469 // br endcond, loop, endloop
1472 // Emit the start code first, without 'variable' in scope.
1473 Value *StartVal = Start->Codegen();
1474 if (StartVal == 0) return 0;
1476 // Make the new basic block for the loop header, inserting after current
1478 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1479 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1480 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1482 // Insert an explicit fall through from the current block to the LoopBB.
1483 Builder.CreateBr(LoopBB);
1485 // Start insertion in LoopBB.
1486 Builder.SetInsertPoint(LoopBB);
1488 // Start the PHI node with an entry for Start.
1489 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
1490 Variable->addIncoming(StartVal, PreheaderBB);
1492 // Within the loop, the variable is defined equal to the PHI node. If it
1493 // shadows an existing variable, we have to restore it, so save it now.
1494 Value *OldVal = NamedValues[VarName];
1495 NamedValues[VarName] = Variable;
1497 // Emit the body of the loop. This, like any other expr, can change the
1498 // current BB. Note that we ignore the value computed by the body, but don't
1500 if (Body->Codegen() == 0)
1503 // Emit the step value.
1506 StepVal = Step->Codegen();
1507 if (StepVal == 0) return 0;
1509 // If not specified, use 1.0.
1510 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1513 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
1515 // Compute the end condition.
1516 Value *EndCond = End->Codegen();
1517 if (EndCond == 0) return EndCond;
1519 // Convert condition to a bool by comparing equal to 0.0.
1520 EndCond = Builder.CreateFCmpONE(EndCond,
1521 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1524 // Create the "after loop" block and insert it.
1525 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1526 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1528 // Insert the conditional branch into the end of LoopEndBB.
1529 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1531 // Any new code will be inserted in AfterBB.
1532 Builder.SetInsertPoint(AfterBB);
1534 // Add a new entry to the PHI node for the backedge.
1535 Variable->addIncoming(NextVar, LoopEndBB);
1537 // Restore the unshadowed variable.
1539 NamedValues[VarName] = OldVal;
1541 NamedValues.erase(VarName);
1544 // for expr always returns 0.0.
1545 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1548 Function *PrototypeAST::Codegen() {
1549 // Make the function type: double(double,double) etc.
1550 std::vector<Type*> Doubles(Args.size(),
1551 Type::getDoubleTy(getGlobalContext()));
1552 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1555 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1557 // If F conflicted, there was already something named 'Name'. If it has a
1558 // body, don't allow redefinition or reextern.
1559 if (F->getName() != Name) {
1560 // Delete the one we just made and get the existing one.
1561 F->eraseFromParent();
1562 F = TheModule->getFunction(Name);
1564 // If F already has a body, reject this.
1565 if (!F->empty()) {
1566 ErrorF("redefinition of function");
1570 // If F took a different number of args, reject.
1571 if (F->arg_size() != Args.size()) {
1572 ErrorF("redefinition of function with different # args");
1577 // Set names for all arguments.
1579 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1581 AI->setName(Args[Idx]);
1583 // Add arguments to variable symbol table.
1584 NamedValues[Args[Idx]] = AI;
1590 Function *FunctionAST::Codegen() {
1591 NamedValues.clear();
1593 Function *TheFunction = Proto->Codegen();
1594 if (TheFunction == 0)
1597 // Create a new basic block to start insertion into.
1598 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1599 Builder.SetInsertPoint(BB);
1601 if (Value *RetVal = Body->Codegen()) {
1602 // Finish off the function.
1603 Builder.CreateRet(RetVal);
1605 // Validate the generated code, checking for consistency.
1606 verifyFunction(*TheFunction);
1608 // Optimize the function.
1609 TheFPM->run(*TheFunction);
1614 // Error reading body, remove function.
1615 TheFunction->eraseFromParent();
1619 //===----------------------------------------------------------------------===//
1620 // Top-Level parsing and JIT Driver
1621 //===----------------------------------------------------------------------===//
1623 static ExecutionEngine *TheExecutionEngine;
1625 static void HandleDefinition() {
1626 if (FunctionAST *F = ParseDefinition()) {
1627 if (Function *LF = F->Codegen()) {
1628 fprintf(stderr, "Read function definition:");
1632 // Skip token for error recovery.
1637 static void HandleExtern() {
1638 if (PrototypeAST *P = ParseExtern()) {
1639 if (Function *F = P->Codegen()) {
1640 fprintf(stderr, "Read extern: ");
1644 // Skip token for error recovery.
1649 static void HandleTopLevelExpression() {
1650 // Evaluate a top-level expression into an anonymous function.
1651 if (FunctionAST *F = ParseTopLevelExpr()) {
1652 if (Function *LF = F->Codegen()) {
1653 // JIT the function, returning a function pointer.
1654 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1656 // Cast it to the right type (takes no arguments, returns a double) so we
1657 // can call it as a native function.
1658 double (*FP)() = (double (*)())(intptr_t)FPtr;
1659 fprintf(stderr, "Evaluated to %f\n", FP());
1662 // Skip token for error recovery.
1667 /// top ::= definition | external | expression | ';'
1668 static void MainLoop() {
1670 fprintf(stderr, "ready> ");
1672 case tok_eof: return;
1673 case ';': getNextToken(); break; // ignore top-level semicolons.
1674 case tok_def: HandleDefinition(); break;
1675 case tok_extern: HandleExtern(); break;
1676 default: HandleTopLevelExpression(); break;
1681 //===----------------------------------------------------------------------===//
1682 // "Library" functions that can be "extern'd" from user code.
1683 //===----------------------------------------------------------------------===//
1685 /// putchard - putchar that takes a double and returns 0.
1687 double putchard(double X) {
1692 //===----------------------------------------------------------------------===//
1693 // Main driver code.
1694 //===----------------------------------------------------------------------===//
1697 InitializeNativeTarget();
1698 LLVMContext &Context = getGlobalContext();
1700 // Install standard binary operators.
1701 // 1 is lowest precedence.
1702 BinopPrecedence['<'] = 10;
1703 BinopPrecedence['+'] = 20;
1704 BinopPrecedence['-'] = 20;
1705 BinopPrecedence['*'] = 40; // highest.
1707 // Prime the first token.
1708 fprintf(stderr, "ready> ");
1711 // Make the module, which holds all the code.
1712 TheModule = new Module("my cool jit", Context);
1714 // Create the JIT. This takes ownership of the module.
1716 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
1717 if (!TheExecutionEngine) {
1718 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1722 FunctionPassManager OurFPM(TheModule);
1724 // Set up the optimizer pipeline. Start with registering info about how the
1725 // target lays out data structures.
1726 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1727 // Provide basic AliasAnalysis support for GVN.
1728 OurFPM.add(createBasicAliasAnalysisPass());
1729 // Do simple "peephole" optimizations and bit-twiddling optzns.
1730 OurFPM.add(createInstructionCombiningPass());
1731 // Reassociate expressions.
1732 OurFPM.add(createReassociatePass());
1733 // Eliminate Common SubExpressions.
1734 OurFPM.add(createGVNPass());
1735 // Simplify the control flow graph (deleting unreachable blocks, etc).
1736 OurFPM.add(createCFGSimplificationPass());
1738 OurFPM.doInitialization();
1740 // Set the global so the code gen can use this.
1741 TheFPM = &OurFPM;
1743 // Run the main "interpreter loop" now.
1748 // Print out all of the generated code.
1749 TheModule->dump();
1756 <a href="LangImpl6.html">Next: Extending the language: user-defined operators</a>
1759 <!-- *********************************************************************** -->
1762 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1763 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1764 <a href="http://validator.w3.org/check/referer"><img
1765 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1767 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1768 <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
1769 Last modified: $Date$