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>
16 <div class="doc_author">
17 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
20 <!-- *********************************************************************** -->
21 <div class="doc_section"><a name="intro">Part 5 Introduction</a></div>
22 <!-- *********************************************************************** -->
24 <div class="doc_text">
26 <p>Welcome to Part 5 of the "<a href="index.html">Implementing a language with
27 LLVM</a>" tutorial. Parts 1-4 described the implementation of the simple
28 Kaleidoscope language and included support for generating LLVM IR, following by
29 optimizations and a JIT compiler. Unfortunately, as presented, Kaleidoscope is
30 mostly useless: it has no control flow other than call and return. This means
31 that you can't have conditional branches in the code, significantly limiting its
32 power. In this episode of "build that compiler", we'll extend Kaleidoscope to
33 have an if/then/else expression plus a simple looping construct.</p>
37 <!-- *********************************************************************** -->
38 <div class="doc_section"><a name="ifthen">If/Then/Else</a></div>
39 <!-- *********************************************************************** -->
41 <div class="doc_text">
44 Extending Kaleidoscope to support if/then/else is quite straight-forward. It
45 basically requires adding lexer support for this "new" concept to the lexer,
46 parser, AST, and LLVM code emitter. This example is nice, because it shows how
47 easy it is to "grow" a language over time, incrementally extending it as new
48 ideas are discovered.</p>
50 <p>Before we get going on "how" we do this extension, lets talk about what we
51 want. The basic idea is that we want to be able to write this sort of thing:
54 <div class="doc_code">
64 <p>In Kaleidoscope, every construct is an expression: there are no statements.
65 As such, the if/then/else expression needs to return a value like any other.
66 Since we're using a mostly functional form, we'll have it evaluate its
67 conditional, then return the 'then' or 'else' value based on how the condition
68 was resolved. This is very similar to the C "?:" expression.</p>
70 <p>The semantics of the if/then/else expression is that it first evaluates the
71 condition to a boolean equality value: 0.0 is false and everything else is true.
72 If the condition is true, the first subexpression is evaluated and returned, if
73 the condition is false, the second subexpression is evaluated and returned.
74 Since Kaleidoscope allows side-effects, this behavior is important to nail down.
77 <p>Now that we know what we want, lets break this down into its constituent
82 <!-- ======================================================================= -->
83 <div class="doc_subsubsection"><a name="iflexer">Lexer Extensions for
84 If/Then/Else</a></div>
85 <!-- ======================================================================= -->
88 <div class="doc_text">
90 <p>The lexer extensions are straight-forward. First we add new enum values
91 for the relevant tokens:</p>
93 <div class="doc_code">
96 tok_if = -6, tok_then = -7, tok_else = -8,
100 <p>Once we have that, we recognize the new keywords in the lexer, pretty simple
103 <div class="doc_code">
106 if (IdentifierStr == "def") return tok_def;
107 if (IdentifierStr == "extern") return tok_extern;
108 <b>if (IdentifierStr == "if") return tok_if;
109 if (IdentifierStr == "then") return tok_then;
110 if (IdentifierStr == "else") return tok_else;</b>
111 return tok_identifier;
117 <!-- ======================================================================= -->
118 <div class="doc_subsubsection"><a name="ifast">AST Extensions for
119 If/Then/Else </a></div>
120 <!-- ======================================================================= -->
122 <div class="doc_text">
124 <p>To represent the new expression we add a new AST node for it:</p>
126 <div class="doc_code">
128 /// IfExprAST - Expression class for if/then/else.
129 class IfExprAST : public ExprAST {
130 ExprAST *Cond, *Then, *Else;
132 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
133 : Cond(cond), Then(then), Else(_else) {}
134 virtual Value *Codegen();
139 <p>The AST node just has pointers to the various subexpressions.</p>
143 <!-- ======================================================================= -->
144 <div class="doc_subsubsection"><a name="ifparser">Parser Extensions for
145 If/Then/Else </a></div>
146 <!-- ======================================================================= -->
148 <div class="doc_text">
150 <p>Now that we have the relevant tokens coming from the lexer and we have the
151 AST node to build, our parsing logic is relatively straight-forward. First we
152 define a new parsing function:</p>
154 <div class="doc_code">
156 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
157 static ExprAST *ParseIfExpr() {
158 getNextToken(); // eat the if.
161 ExprAST *Cond = ParseExpression();
164 if (CurTok != tok_then)
165 return Error("expected then");
166 getNextToken(); // eat the then
168 ExprAST *Then = ParseExpression();
169 if (Then == 0) return 0;
171 if (CurTok != tok_else)
172 return Error("expected else");
176 ExprAST *Else = ParseExpression();
179 return new IfExprAST(Cond, Then, Else);
184 <p>Next we hook it up as a primary expression:</p>
186 <div class="doc_code">
188 static ExprAST *ParsePrimary() {
190 default: return Error("unknown token when expecting an expression");
191 case tok_identifier: return ParseIdentifierExpr();
192 case tok_number: return ParseNumberExpr();
193 case '(': return ParseParenExpr();
194 <b>case tok_if: return ParseIfExpr();</b>
202 <!-- ======================================================================= -->
203 <div class="doc_subsubsection"><a name="ifir">LLVM IR for If/Then/Else</a></div>
204 <!-- ======================================================================= -->
206 <div class="doc_text">
208 <p>Now that we have it parsing and building the AST, the final piece is adding
209 LLVM code generation support. This is the most interesting part of the
210 if/then/else example, because this is where it starts to introduce new concepts.
211 All of the code above has been described in previous chapters fairly thoroughly.
214 <p>To motivate the code we want to produce, lets take a look at a simple
215 example. Consider:</p>
217 <div class="doc_code">
221 def baz(x) if x then foo() else bar();
225 <p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
228 <div class="doc_code">
230 declare double @foo()
232 declare double @bar()
234 define double @baz(double %x) {
236 %ifcond = fcmp one double %x, 0.000000e+00
237 br i1 %ifcond, label %then, label %else
239 then: ; preds = %entry
240 %calltmp = call double @foo()
243 else: ; preds = %entry
244 %calltmp1 = call double @bar()
247 ifcont: ; preds = %else, %then
248 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
254 <p>To visualize the control flow graph, you can use a nifty feature of the LLVM
255 '<a href="http://llvm.org/cmds/opt.html">opt</a>' tool. If you put this LLVM IR
256 into "t.ll" and run "<tt>llvm-as < t.ll | opt -analyze -view-cfg</tt>", <a
257 href="../ProgrammersManual.html#ViewGraph">a window will pop up</a> and you'll
260 <center><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
261 height="315"></center>
263 <p>Another way to get this is to call "<tt>F->viewCFG()</tt>" or
264 "<tt>F->viewCFGOnly()</tt>" (where F is a "<tt>Function*</tt>") either by
265 inserting actual calls into the code and recompiling or by calling these in the
266 debugger. LLVM has many nice features for visualizing various graphs.</p>
268 <p>Coming back to the generated code, it is fairly simple: the entry block
269 evaluates the conditional expression ("x" in our case here) and compares the
270 result to 0.0 with the "<tt><a href="../LangRef.html#i_fcmp">fcmp</a> one</tt>"
271 instruction ('one' is "ordered and not equal"). Based on the result of this
272 expression, the code jumps to either the "then" or "else" blocks, which contain
273 the expressions for the true/false case.</p>
275 <p>Once the then/else blocks is finished executing, they both branch back to the
276 else block to execute the code that happens after the if/then/else. In this
277 case the only thing left to do is to return to the caller of the function. The
278 question then becomes: how does the code know which expression to return?</p>
280 <p>The answer to this question involves an important SSA operation: the
281 <a href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Phi
282 operation</a>. If you're not familiar with SSA, <a
283 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">the wikipedia
284 article</a> is a good introduction and there are various other introductions to
285 it available on your favorite search engine. The short version is that
286 "execution" of the Phi operation requires "remembering" which block control came
287 from. The Phi operation takes on the value corresponding to the input control
288 block. In this case, if control comes in from the "then" block, it gets the
289 value of "calltmp". If control comes from the "else" block, it gets the value
292 <p>At this point, you are probably starting to think "on no! this means my
293 simple and elegant front-end will have to start generating SSA form in order to
294 use LLVM!". Fortunately, this is not the case, and we strongly advise
295 <em>not</em> implementing an SSA construction algorithm in your front-end
296 unless there is an amazingly good reason to do so. In practice, there are two
297 sorts of values that float around in code written in your average imperative
298 programming language that might need Phi nodes:</p>
301 <li>Code that involves user variables: <tt>x = 1; x = x + 1; </tt></li>
302 <li>Values that are implicit in the structure of your AST, such as the phi node
306 <p>In <a href="LangImpl7.html">Chapter 7</a> of this tutorial ("mutable
307 variables"), we'll talk about #1
308 in depth. For now, just believe me that you don't need SSA construction to
309 handle them. For #2, you have the choice of using the techniques that we will
310 describe for #1, or you can insert Phi nodes directly if convenient. In this
311 case, it is really really easy to generate the Phi node, so we choose to do it
314 <p>Okay, enough of the motivation and overview, lets generate code!</p>
318 <!-- ======================================================================= -->
319 <div class="doc_subsubsection"><a name="ifcodegen">Code Generation for
320 If/Then/Else</a></div>
321 <!-- ======================================================================= -->
323 <div class="doc_text">
325 <p>In order to generate code for this, we implement the <tt>Codegen</tt> method
326 for <tt>IfExprAST</tt>:</p>
328 <div class="doc_code">
330 Value *IfExprAST::Codegen() {
331 Value *CondV = Cond->Codegen();
332 if (CondV == 0) return 0;
334 // Convert condition to a bool by comparing equal to 0.0.
335 CondV = Builder.CreateFCmpONE(CondV,
336 ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
341 <p>This code is straight-forward and similar to what we saw before. We emit the
342 expression for the condition, then compare that value to zero to get a truth
343 value as a 1-bit (bool) value.</p>
345 <div class="doc_code">
347 Function *TheFunction = Builder.GetInsertBlock()->getParent();
349 // Create blocks for the then and else cases. Insert the 'then' block at the
350 // end of the function.
351 BasicBlock *ThenBB = new BasicBlock("then", TheFunction);
352 BasicBlock *ElseBB = new BasicBlock("else");
353 BasicBlock *MergeBB = new BasicBlock("ifcont");
355 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
359 <p>This code creates the basic blocks that are related to the if/then/else
360 statement, and correspond directly to the blocks in the example above. The
361 first line of this gets the current Function object that is being built. It
362 gets this by asking the builder for the current BasicBlock, and asking that
363 block for its "parent" (the function it is currently embedded into).</p>
365 <p>Once it has that, it creates three blocks. Note that it passes "TheFunction"
366 into the constructor for the "then" block. This causes the constructor to
367 automatically insert the new block onto the end of the specified function. The
368 other two blocks are created, but aren't yet inserted into the function.</p>
370 <p>Once the blocks are created, we can emit the conditional branch that chooses
371 between them. Note that creating new blocks does not implicitly affect the
372 LLVMBuilder, so it is still inserting into the block that the condition
373 went into. Also note that it is creating a branch to the "then" block and the
374 "else" block, even though the "else" block isn't inserted into the function yet.
375 This is all ok: it is the standard way that LLVM supports forward
378 <div class="doc_code">
381 Builder.SetInsertPoint(ThenBB);
383 Value *ThenV = Then->Codegen();
384 if (ThenV == 0) return 0;
386 Builder.CreateBr(MergeBB);
387 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
388 ThenBB = Builder.GetInsertBlock();
392 <p>After the conditional branch is inserted, we move the builder to start
393 inserting into the "then" block. Strictly speaking, this call moves the
394 insertion point to be at the end of the specified block. However, since the
395 "then" block is empty, it also starts out by inserting at the beginning of the
398 <p>Once the insertion point is set, we recursively codegen the "then" expression
399 from the AST. To finish off the then block, we create an unconditional branch
400 to the merge block. One interesting (and very important) aspect of the LLVM IR
401 is that it <a href="../LangRef.html#functionstructure">requires all basic blocks
402 to be "terminated"</a> with a <a href="../LangRef.html#terminators">control flow
403 instruction</a> such as return or branch. This means that all control flow,
404 <em>including fall throughs</em> must be made explicit in the LLVM IR. If you
405 violate this rule, the verifier will emit an error.</p>
407 <p>The final line here is quite subtle, but is very important. The basic issue
408 is that when we create the Phi node in the merge block, we need to set up the
409 block/value pairs that indicate how the Phi will work. Importantly, the Phi
410 node expects to have an entry for each predecessor of the block in the CFG. Why
411 then are we getting the current block when we just set it to ThenBB 5 lines
412 above? The problem is that the "Then" expression may actually itself change the
413 block that the Builder is emitting into if, for example, it contains a nested
414 "if/then/else" expression. Because calling Codegen recursively could
415 arbitrarily change the notion of the current block, we are required to get an
416 up-to-date value for code that will set up the Phi node.</p>
418 <div class="doc_code">
421 TheFunction->getBasicBlockList().push_back(ElseBB);
422 Builder.SetInsertPoint(ElseBB);
424 Value *ElseV = Else->Codegen();
425 if (ElseV == 0) return 0;
427 Builder.CreateBr(MergeBB);
428 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
429 ElseBB = Builder.GetInsertBlock();
433 <p>Code generation for the 'else' block is basically identical to codegen for
434 the 'then' block. The only significant difference is the first line, which adds
435 the 'else' block to the function. Recall previously that the 'else' block was
436 created, but not added to the function. Now that the 'then' and 'else' blocks
437 are emitted, we can finish up with the merge code:</p>
439 <div class="doc_code">
442 TheFunction->getBasicBlockList().push_back(MergeBB);
443 Builder.SetInsertPoint(MergeBB);
444 PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
446 PN->addIncoming(ThenV, ThenBB);
447 PN->addIncoming(ElseV, ElseBB);
453 <p>The first two lines here are now familiar: the first adds the "merge" block
454 to the Function object (it was previously floating, like the else block above).
455 The second block changes the insertion point so that newly created code will go
456 into the "merge" block. Once that is done, we need to create the PHI node and
457 set up the block/value pairs for the PHI.</p>
459 <p>Finally, the CodeGen function returns the phi node as the value computed by
460 the if/then/else expression. In our example above, this returned value will
461 feed into the code for the top-level function, which will create the return
464 <p>Overall, we now have the ability to execution conditional code in
465 Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
466 that can calculate a wide variety of numeric functions. Next up we'll add
467 another useful expression that is familiar from non-functional languages...</p>
471 <!-- *********************************************************************** -->
472 <div class="doc_section"><a name="for">'for' Loop Expression</a></div>
473 <!-- *********************************************************************** -->
475 <div class="doc_text">
477 <p>Now that we know how to add basic control flow constructs to the language,
478 we have the tools to add more powerful things. Lets add something more
479 aggressive, a 'for' expression:</p>
481 <div class="doc_code">
483 extern putchard(char)
485 for i = 1, i < n, 1.0 in
486 putchard(42); # ascii 42 = '*'
488 # print 100 '*' characters
493 <p>This expression defines a new variable ("i" in this case) which iterates from
494 a starting value, while the condition ("i < n" in this case) is true,
495 incrementing by an optional step value ("1.0" in this case). If the step value
496 is omitted, it defaults to 1.0. While the loop is true, it executes its
497 body expression. Because we don't have anything better to return, we'll just
498 define the loop as always returning 0.0. In the future when we have mutable
499 variables, it will get more useful.</p>
501 <p>As before, lets talk about the changes that we need to Kaleidoscope to
506 <!-- ======================================================================= -->
507 <div class="doc_subsubsection"><a name="forlexer">Lexer Extensions for
508 the 'for' Loop</a></div>
509 <!-- ======================================================================= -->
511 <div class="doc_text">
513 <p>The lexer extensions are the same sort of thing as for if/then/else:</p>
515 <div class="doc_code">
517 ... in enum Token ...
519 tok_if = -6, tok_then = -7, tok_else = -8,
520 <b> tok_for = -9, tok_in = -10</b>
523 if (IdentifierStr == "def") return tok_def;
524 if (IdentifierStr == "extern") return tok_extern;
525 if (IdentifierStr == "if") return tok_if;
526 if (IdentifierStr == "then") return tok_then;
527 if (IdentifierStr == "else") return tok_else;
528 <b>if (IdentifierStr == "for") return tok_for;
529 if (IdentifierStr == "in") return tok_in;</b>
530 return tok_identifier;
536 <!-- ======================================================================= -->
537 <div class="doc_subsubsection"><a name="forast">AST Extensions for
538 the 'for' Loop</a></div>
539 <!-- ======================================================================= -->
541 <div class="doc_text">
543 <p>The AST node is similarly simple. It basically boils down to capturing
544 the variable name and the consituent expressions in the node.</p>
546 <div class="doc_code">
548 /// ForExprAST - Expression class for for/in.
549 class ForExprAST : public ExprAST {
551 ExprAST *Start, *End, *Step, *Body;
553 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
554 ExprAST *step, ExprAST *body)
555 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
556 virtual Value *Codegen();
563 <!-- ======================================================================= -->
564 <div class="doc_subsubsection"><a name="forparser">Parser Extensions for
565 the 'for' Loop</a></div>
566 <!-- ======================================================================= -->
568 <div class="doc_text">
570 <p>The parser code is also fairly standard. The only interesting thing here is
571 handling of the optional step value. The parser code handles it by checking to
572 see if the second comma is present. If not, it sets the step value to null in
575 <div class="doc_code">
577 /// forexpr ::= 'for' identifer '=' expr ',' expr (',' expr)? 'in' expression
578 static ExprAST *ParseForExpr() {
579 getNextToken(); // eat the for.
581 if (CurTok != tok_identifier)
582 return Error("expected identifier after for");
584 std::string IdName = IdentifierStr;
585 getNextToken(); // eat identifer.
588 return Error("expected '=' after for");
589 getNextToken(); // eat '='.
592 ExprAST *Start = ParseExpression();
593 if (Start == 0) return 0;
595 return Error("expected ',' after for start value");
598 ExprAST *End = ParseExpression();
599 if (End == 0) return 0;
601 // The step value is optional.
605 Step = ParseExpression();
606 if (Step == 0) return 0;
609 if (CurTok != tok_in)
610 return Error("expected 'in' after for");
611 getNextToken(); // eat 'in'.
613 ExprAST *Body = ParseExpression();
614 if (Body == 0) return 0;
616 return new ForExprAST(IdName, Start, End, Step, Body);
623 <!-- ======================================================================= -->
624 <div class="doc_subsubsection"><a name="forir">LLVM IR for
625 the 'for' Loop</a></div>
626 <!-- ======================================================================= -->
628 <div class="doc_text">
630 <p>Now we get to the good part: the LLVM IR we want to generate for this thing.
631 With the simple example above, we get this LLVM IR (note that this dump is
632 generated with optimizations disabled):
635 <div class="doc_code">
637 declare double @putchard(double)
639 define double @printstar(double %n) {
641 ; initial value = 1.0 (inlined into phi)
644 loop: ; preds = %loop, %entry
645 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
647 %calltmp = call double @putchard( double 4.200000e+01 )
649 %nextvar = add double %i, 1.000000e+00
652 %multmp = fcmp ult double %i, %n
653 %booltmp = uitofp i1 %multmp to double
654 %loopcond = fcmp one double %booltmp, 0.000000e+00
655 br i1 %loopcond, label %loop, label %afterloop
657 afterloop: ; preds = %loop
658 ; loop always returns 0.0
659 ret double 0.000000e+00
664 <p>This loop contains all the same constructs we saw before: a phi node, several
665 expressions, and some basic blocks. Lets see how this fits together.</p>
669 <!-- ======================================================================= -->
670 <div class="doc_subsubsection"><a name="forcodegen">Code Generation for
671 the 'for' Loop</a></div>
672 <!-- ======================================================================= -->
674 <div class="doc_text">
676 <p>The first part of codegen is very simple: we just output the start expression
677 for the loop value:</p>
679 <div class="doc_code">
681 Value *ForExprAST::Codegen() {
682 // Emit the start code first, without 'variable' in scope.
683 Value *StartVal = Start->Codegen();
684 if (StartVal == 0) return 0;
688 <p>With this out of the way, the next step is to set up the LLVM basic block
689 for the start of the loop body. In the case above, the whole loop body is one
690 block, but remember that the body code itself could consist of multiple blocks
691 (e.g. if it is a if/then/else expression).</p>
693 <div class="doc_code">
695 // Make the new basic block for the loop header, inserting after current
697 Function *TheFunction = Builder.GetInsertBlock()->getParent();
698 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
699 BasicBlock *LoopBB = new BasicBlock("loop", TheFunction);
701 // Insert an explicit fall through from the current block to the LoopBB.
702 Builder.CreateBr(LoopBB);
706 <p>This code is similar to what we saw for if/then/else. Because we will need
707 it to create the Phi node, we remember the block that falls through into the
708 loop. Once we have that, we create the actual block that starts the loop and
709 create an unconditional branch for the fall-through between the two blocks.</p>
711 <div class="doc_code">
713 // Start insertion in LoopBB.
714 Builder.SetInsertPoint(LoopBB);
716 // Start the PHI node with an entry for Start.
717 PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
718 Variable->addIncoming(StartVal, PreheaderBB);
722 <p>Now that the "preheader" for the loop is set up, we switch to emitting code
723 for the loop body. To begin with, we move the insertion point and create the
724 PHI node for the loop induction variable. SInce we already know the incoming
725 value for the starting value, we add it to the Phi node. Note that the Phi will
726 eventually get a second value for the backedge, but we can't set it up yet
727 (because it doesn't exist!).</p>
729 <div class="doc_code">
731 // Within the loop, the variable is defined equal to the PHI node. If it
732 // shadows an existing variable, we have to restore it, so save it now.
733 Value *OldVal = NamedValues[VarName];
734 NamedValues[VarName] = Variable;
736 // Emit the body of the loop. This, like any other expr, can change the
737 // current BB. Note that we ignore the value computed by the body, but don't
739 if (Body->Codegen() == 0)
744 <p>Now the code starts to get more interesting. Our 'for' loop introduces a new
745 variable to the symbol table. This means that our symbol table can now contain
746 either function arguments or loop variables. To handle this, before we codegen
747 the body of the loop, we add the loop variable as the current value for its
748 name. Note that it is possible that there is a variable of the same name in the
749 outer scope. It would be easy to make this an error (emit an error and return
750 null if there is already an entry for VarName) but we choose to allow shadowing
751 of variables. In order to handle this correctly, we remember the Value that
752 we are potentially shadowing in <tt>OldVal</tt> (which will be null if there is
753 no shadowed variable).</p>
755 <p>Once the loop variable is set into the symbol table, the code recursively
756 codegen's the body. This allows the body to use the loop variable: any
757 references to it will naturally find it in the symbol table.</p>
759 <div class="doc_code">
761 // Emit the step value.
764 StepVal = Step->Codegen();
765 if (StepVal == 0) return 0;
767 // If not specified, use 1.0.
768 StepVal = ConstantFP::get(Type::DoubleTy, APFloat(1.0));
771 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
775 <p>Now that the body is emitted, we compute the next value of the iteration
776 variable by adding the step value or 1.0 if it isn't present. '<tt>NextVar</tt>'
777 will be the value of the loop variable on the next iteration of the loop.</p>
779 <div class="doc_code">
781 // Compute the end condition.
782 Value *EndCond = End->Codegen();
783 if (EndCond == 0) return EndCond;
785 // Convert condition to a bool by comparing equal to 0.0.
786 EndCond = Builder.CreateFCmpONE(EndCond,
787 ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
792 <p>Finally, we evaluate the exit value of the loop, to determine whether the
793 loop should exit. This mirrors the condition evaluation for the if/then/else
796 <div class="doc_code">
798 // Create the "after loop" block and insert it.
799 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
800 BasicBlock *AfterBB = new BasicBlock("afterloop", TheFunction);
802 // Insert the conditional branch into the end of LoopEndBB.
803 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
805 // Any new code will be inserted in AfterBB.
806 Builder.SetInsertPoint(AfterBB);
810 <p>With the code for the body of the loop complete, we just need to finish up
811 the control flow for it. This remembers the end block (for the phi node), then
812 creates the block for the loop exit ("afterloop"). Based on the value of the
813 exit condition, it creates a conditional branch that chooses between executing
814 the loop again and exiting the loop. Any future code is emitted in the
815 "afterloop" block, so it sets the insertion position to it.</p>
817 <div class="doc_code">
819 // Add a new entry to the PHI node for the backedge.
820 Variable->addIncoming(NextVar, LoopEndBB);
822 // Restore the unshadowed variable.
824 NamedValues[VarName] = OldVal;
826 NamedValues.erase(VarName);
828 // for expr always returns 0.0.
829 return Constant::getNullValue(Type::DoubleTy);
834 <p>The final code handles various cleanups: now that we have the "NextVar"
835 value, we can add the incoming value to the loop PHI node. After that, we
836 remove the loop variable from the symbol table, so that it isn't in scope after
837 the for loop. Finally, code generation of the for loop always returns 0.0, so
838 that is what we return from <tt>ForExprAST::Codegen</tt>.</p>
840 <p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
841 the tutorial. We added two control flow constructs, and used them to motivate
842 a couple of aspects of the LLVM IR that are important for front-end implementors
843 to know. In the next chapter of our saga, we will get a bit crazier and add
844 operator overloading to our poor innocent language.</p>
848 <!-- *********************************************************************** -->
849 <div class="doc_section"><a name="code">Full Code Listing</a></div>
850 <!-- *********************************************************************** -->
852 <div class="doc_text">
855 Here is the complete code listing for our running example, enhanced with the
856 if/then/else and for expressions.. To build this example, use:
859 <div class="doc_code">
862 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
868 <p>Here is the code:</p>
870 <div class="doc_code">
872 #include "llvm/DerivedTypes.h"
873 #include "llvm/ExecutionEngine/ExecutionEngine.h"
874 #include "llvm/Module.h"
875 #include "llvm/ModuleProvider.h"
876 #include "llvm/PassManager.h"
877 #include "llvm/Analysis/Verifier.h"
878 #include "llvm/Target/TargetData.h"
879 #include "llvm/Transforms/Scalar.h"
880 #include "llvm/Support/LLVMBuilder.h"
881 #include <cstdio>
882 #include <string>
884 #include <vector>
885 using namespace llvm;
887 //===----------------------------------------------------------------------===//
889 //===----------------------------------------------------------------------===//
891 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
892 // of these for known things.
897 tok_def = -2, tok_extern = -3,
900 tok_identifier = -4, tok_number = -5,
903 tok_if = -6, tok_then = -7, tok_else = -8,
904 tok_for = -9, tok_in = -10
907 static std::string IdentifierStr; // Filled in if tok_identifier
908 static double NumVal; // Filled in if tok_number
910 /// gettok - Return the next token from standard input.
911 static int gettok() {
912 static int LastChar = ' ';
914 // Skip any whitespace.
915 while (isspace(LastChar))
916 LastChar = getchar();
918 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
919 IdentifierStr = LastChar;
920 while (isalnum((LastChar = getchar())))
921 IdentifierStr += LastChar;
923 if (IdentifierStr == "def") return tok_def;
924 if (IdentifierStr == "extern") return tok_extern;
925 if (IdentifierStr == "if") return tok_if;
926 if (IdentifierStr == "then") return tok_then;
927 if (IdentifierStr == "else") return tok_else;
928 if (IdentifierStr == "for") return tok_for;
929 if (IdentifierStr == "in") return tok_in;
930 return tok_identifier;
933 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
937 LastChar = getchar();
938 } while (isdigit(LastChar) || LastChar == '.');
940 NumVal = strtod(NumStr.c_str(), 0);
944 if (LastChar == '#') {
945 // Comment until end of line.
946 do LastChar = getchar();
947 while (LastChar != EOF && LastChar != '\n' & LastChar != '\r');
953 // Check for end of file. Don't eat the EOF.
957 // Otherwise, just return the character as its ascii value.
958 int ThisChar = LastChar;
959 LastChar = getchar();
963 //===----------------------------------------------------------------------===//
964 // Abstract Syntax Tree (aka Parse Tree)
965 //===----------------------------------------------------------------------===//
967 /// ExprAST - Base class for all expression nodes.
970 virtual ~ExprAST() {}
971 virtual Value *Codegen() = 0;
974 /// NumberExprAST - Expression class for numeric literals like "1.0".
975 class NumberExprAST : public ExprAST {
978 NumberExprAST(double val) : Val(val) {}
979 virtual Value *Codegen();
982 /// VariableExprAST - Expression class for referencing a variable, like "a".
983 class VariableExprAST : public ExprAST {
986 VariableExprAST(const std::string &name) : Name(name) {}
987 virtual Value *Codegen();
990 /// BinaryExprAST - Expression class for a binary operator.
991 class BinaryExprAST : public ExprAST {
995 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
996 : Op(op), LHS(lhs), RHS(rhs) {}
997 virtual Value *Codegen();
1000 /// CallExprAST - Expression class for function calls.
1001 class CallExprAST : public ExprAST {
1003 std::vector<ExprAST*> Args;
1005 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
1006 : Callee(callee), Args(args) {}
1007 virtual Value *Codegen();
1010 /// IfExprAST - Expression class for if/then/else.
1011 class IfExprAST : public ExprAST {
1012 ExprAST *Cond, *Then, *Else;
1014 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1015 : Cond(cond), Then(then), Else(_else) {}
1016 virtual Value *Codegen();
1019 /// ForExprAST - Expression class for for/in.
1020 class ForExprAST : public ExprAST {
1021 std::string VarName;
1022 ExprAST *Start, *End, *Step, *Body;
1024 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
1025 ExprAST *step, ExprAST *body)
1026 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1027 virtual Value *Codegen();
1030 /// PrototypeAST - This class represents the "prototype" for a function,
1031 /// which captures its argument names as well as if it is an operator.
1032 class PrototypeAST {
1034 std::vector<std::string> Args;
1036 PrototypeAST(const std::string &name, const std::vector<std::string> &args)
1037 : Name(name), Args(args) {}
1039 Function *Codegen();
1042 /// FunctionAST - This class represents a function definition itself.
1044 PrototypeAST *Proto;
1047 FunctionAST(PrototypeAST *proto, ExprAST *body)
1048 : Proto(proto), Body(body) {}
1050 Function *Codegen();
1053 //===----------------------------------------------------------------------===//
1055 //===----------------------------------------------------------------------===//
1057 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1058 /// token the parser it looking at. getNextToken reads another token from the
1059 /// lexer and updates CurTok with its results.
1061 static int getNextToken() {
1062 return CurTok = gettok();
1065 /// BinopPrecedence - This holds the precedence for each binary operator that is
1067 static std::map<char, int> BinopPrecedence;
1069 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1070 static int GetTokPrecedence() {
1071 if (!isascii(CurTok))
1074 // Make sure it's a declared binop.
1075 int TokPrec = BinopPrecedence[CurTok];
1076 if (TokPrec <= 0) return -1;
1080 /// Error* - These are little helper functions for error handling.
1081 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1082 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1083 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1085 static ExprAST *ParseExpression();
1089 /// ::= identifer '(' expression* ')'
1090 static ExprAST *ParseIdentifierExpr() {
1091 std::string IdName = IdentifierStr;
1093 getNextToken(); // eat identifer.
1095 if (CurTok != '(') // Simple variable ref.
1096 return new VariableExprAST(IdName);
1099 getNextToken(); // eat (
1100 std::vector<ExprAST*> Args;
1101 if (CurTok != ')') {
1103 ExprAST *Arg = ParseExpression();
1105 Args.push_back(Arg);
1107 if (CurTok == ')') break;
1110 return Error("Expected ')'");
1118 return new CallExprAST(IdName, Args);
1121 /// numberexpr ::= number
1122 static ExprAST *ParseNumberExpr() {
1123 ExprAST *Result = new NumberExprAST(NumVal);
1124 getNextToken(); // consume the number
1128 /// parenexpr ::= '(' expression ')'
1129 static ExprAST *ParseParenExpr() {
1130 getNextToken(); // eat (.
1131 ExprAST *V = ParseExpression();
1135 return Error("expected ')'");
1136 getNextToken(); // eat ).
1140 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1141 static ExprAST *ParseIfExpr() {
1142 getNextToken(); // eat the if.
1145 ExprAST *Cond = ParseExpression();
1146 if (!Cond) return 0;
1148 if (CurTok != tok_then)
1149 return Error("expected then");
1150 getNextToken(); // eat the then
1152 ExprAST *Then = ParseExpression();
1153 if (Then == 0) return 0;
1155 if (CurTok != tok_else)
1156 return Error("expected else");
1160 ExprAST *Else = ParseExpression();
1161 if (!Else) return 0;
1163 return new IfExprAST(Cond, Then, Else);
1166 /// forexpr ::= 'for' identifer '=' expr ',' expr (',' expr)? 'in' expression
1167 static ExprAST *ParseForExpr() {
1168 getNextToken(); // eat the for.
1170 if (CurTok != tok_identifier)
1171 return Error("expected identifier after for");
1173 std::string IdName = IdentifierStr;
1174 getNextToken(); // eat identifer.
1177 return Error("expected '=' after for");
1178 getNextToken(); // eat '='.
1181 ExprAST *Start = ParseExpression();
1182 if (Start == 0) return 0;
1184 return Error("expected ',' after for start value");
1187 ExprAST *End = ParseExpression();
1188 if (End == 0) return 0;
1190 // The step value is optional.
1192 if (CurTok == ',') {
1194 Step = ParseExpression();
1195 if (Step == 0) return 0;
1198 if (CurTok != tok_in)
1199 return Error("expected 'in' after for");
1200 getNextToken(); // eat 'in'.
1202 ExprAST *Body = ParseExpression();
1203 if (Body == 0) return 0;
1205 return new ForExprAST(IdName, Start, End, Step, Body);
1210 /// ::= identifierexpr
1215 static ExprAST *ParsePrimary() {
1217 default: return Error("unknown token when expecting an expression");
1218 case tok_identifier: return ParseIdentifierExpr();
1219 case tok_number: return ParseNumberExpr();
1220 case '(': return ParseParenExpr();
1221 case tok_if: return ParseIfExpr();
1222 case tok_for: return ParseForExpr();
1227 /// ::= ('+' primary)*
1228 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1229 // If this is a binop, find its precedence.
1231 int TokPrec = GetTokPrecedence();
1233 // If this is a binop that binds at least as tightly as the current binop,
1234 // consume it, otherwise we are done.
1235 if (TokPrec < ExprPrec)
1238 // Okay, we know this is a binop.
1240 getNextToken(); // eat binop
1242 // Parse the primary expression after the binary operator.
1243 ExprAST *RHS = ParsePrimary();
1246 // If BinOp binds less tightly with RHS than the operator after RHS, let
1247 // the pending operator take RHS as its LHS.
1248 int NextPrec = GetTokPrecedence();
1249 if (TokPrec < NextPrec) {
1250 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1251 if (RHS == 0) return 0;
1255 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1260 /// ::= primary binoprhs
1262 static ExprAST *ParseExpression() {
1263 ExprAST *LHS = ParsePrimary();
1266 return ParseBinOpRHS(0, LHS);
1270 /// ::= id '(' id* ')'
1271 static PrototypeAST *ParsePrototype() {
1272 if (CurTok != tok_identifier)
1273 return ErrorP("Expected function name in prototype");
1275 std::string FnName = IdentifierStr;
1279 return ErrorP("Expected '(' in prototype");
1281 std::vector<std::string> ArgNames;
1282 while (getNextToken() == tok_identifier)
1283 ArgNames.push_back(IdentifierStr);
1285 return ErrorP("Expected ')' in prototype");
1288 getNextToken(); // eat ')'.
1290 return new PrototypeAST(FnName, ArgNames);
1293 /// definition ::= 'def' prototype expression
1294 static FunctionAST *ParseDefinition() {
1295 getNextToken(); // eat def.
1296 PrototypeAST *Proto = ParsePrototype();
1297 if (Proto == 0) return 0;
1299 if (ExprAST *E = ParseExpression())
1300 return new FunctionAST(Proto, E);
1304 /// toplevelexpr ::= expression
1305 static FunctionAST *ParseTopLevelExpr() {
1306 if (ExprAST *E = ParseExpression()) {
1307 // Make an anonymous proto.
1308 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
1309 return new FunctionAST(Proto, E);
1314 /// external ::= 'extern' prototype
1315 static PrototypeAST *ParseExtern() {
1316 getNextToken(); // eat extern.
1317 return ParsePrototype();
1320 //===----------------------------------------------------------------------===//
1322 //===----------------------------------------------------------------------===//
1324 static Module *TheModule;
1325 static LLVMFoldingBuilder Builder;
1326 static std::map<std::string, Value*> NamedValues;
1327 static FunctionPassManager *TheFPM;
1329 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1331 Value *NumberExprAST::Codegen() {
1332 return ConstantFP::get(Type::DoubleTy, APFloat(Val));
1335 Value *VariableExprAST::Codegen() {
1336 // Look this variable up in the function.
1337 Value *V = NamedValues[Name];
1338 return V ? V : ErrorV("Unknown variable name");
1341 Value *BinaryExprAST::Codegen() {
1342 Value *L = LHS->Codegen();
1343 Value *R = RHS->Codegen();
1344 if (L == 0 || R == 0) return 0;
1347 case '+': return Builder.CreateAdd(L, R, "addtmp");
1348 case '-': return Builder.CreateSub(L, R, "subtmp");
1349 case '*': return Builder.CreateMul(L, R, "multmp");
1351 L = Builder.CreateFCmpULT(L, R, "multmp");
1352 // Convert bool 0/1 to double 0.0 or 1.0
1353 return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
1354 default: return ErrorV("invalid binary operator");
1358 Value *CallExprAST::Codegen() {
1359 // Look up the name in the global module table.
1360 Function *CalleeF = TheModule->getFunction(Callee);
1362 return ErrorV("Unknown function referenced");
1364 // If argument mismatch error.
1365 if (CalleeF->arg_size() != Args.size())
1366 return ErrorV("Incorrect # arguments passed");
1368 std::vector<Value*> ArgsV;
1369 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1370 ArgsV.push_back(Args[i]->Codegen());
1371 if (ArgsV.back() == 0) return 0;
1374 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1377 Value *IfExprAST::Codegen() {
1378 Value *CondV = Cond->Codegen();
1379 if (CondV == 0) return 0;
1381 // Convert condition to a bool by comparing equal to 0.0.
1382 CondV = Builder.CreateFCmpONE(CondV,
1383 ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
1386 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1388 // Create blocks for the then and else cases. Insert the 'then' block at the
1389 // end of the function.
1390 BasicBlock *ThenBB = new BasicBlock("then", TheFunction);
1391 BasicBlock *ElseBB = new BasicBlock("else");
1392 BasicBlock *MergeBB = new BasicBlock("ifcont");
1394 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1397 Builder.SetInsertPoint(ThenBB);
1399 Value *ThenV = Then->Codegen();
1400 if (ThenV == 0) return 0;
1402 Builder.CreateBr(MergeBB);
1403 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1404 ThenBB = Builder.GetInsertBlock();
1407 TheFunction->getBasicBlockList().push_back(ElseBB);
1408 Builder.SetInsertPoint(ElseBB);
1410 Value *ElseV = Else->Codegen();
1411 if (ElseV == 0) return 0;
1413 Builder.CreateBr(MergeBB);
1414 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1415 ElseBB = Builder.GetInsertBlock();
1417 // Emit merge block.
1418 TheFunction->getBasicBlockList().push_back(MergeBB);
1419 Builder.SetInsertPoint(MergeBB);
1420 PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
1422 PN->addIncoming(ThenV, ThenBB);
1423 PN->addIncoming(ElseV, ElseBB);
1427 Value *ForExprAST::Codegen() {
1430 // start = startexpr
1433 // variable = phi [start, loopheader], [nextvariable, loopend]
1439 // nextvariable = variable + step
1440 // endcond = endexpr
1441 // br endcond, loop, endloop
1444 // Emit the start code first, without 'variable' in scope.
1445 Value *StartVal = Start->Codegen();
1446 if (StartVal == 0) return 0;
1448 // Make the new basic block for the loop header, inserting after current
1450 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1451 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1452 BasicBlock *LoopBB = new BasicBlock("loop", TheFunction);
1454 // Insert an explicit fall through from the current block to the LoopBB.
1455 Builder.CreateBr(LoopBB);
1457 // Start insertion in LoopBB.
1458 Builder.SetInsertPoint(LoopBB);
1460 // Start the PHI node with an entry for Start.
1461 PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
1462 Variable->addIncoming(StartVal, PreheaderBB);
1464 // Within the loop, the variable is defined equal to the PHI node. If it
1465 // shadows an existing variable, we have to restore it, so save it now.
1466 Value *OldVal = NamedValues[VarName];
1467 NamedValues[VarName] = Variable;
1469 // Emit the body of the loop. This, like any other expr, can change the
1470 // current BB. Note that we ignore the value computed by the body, but don't
1472 if (Body->Codegen() == 0)
1475 // Emit the step value.
1478 StepVal = Step->Codegen();
1479 if (StepVal == 0) return 0;
1481 // If not specified, use 1.0.
1482 StepVal = ConstantFP::get(Type::DoubleTy, APFloat(1.0));
1485 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
1487 // Compute the end condition.
1488 Value *EndCond = End->Codegen();
1489 if (EndCond == 0) return EndCond;
1491 // Convert condition to a bool by comparing equal to 0.0.
1492 EndCond = Builder.CreateFCmpONE(EndCond,
1493 ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
1496 // Create the "after loop" block and insert it.
1497 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1498 BasicBlock *AfterBB = new BasicBlock("afterloop", TheFunction);
1500 // Insert the conditional branch into the end of LoopEndBB.
1501 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1503 // Any new code will be inserted in AfterBB.
1504 Builder.SetInsertPoint(AfterBB);
1506 // Add a new entry to the PHI node for the backedge.
1507 Variable->addIncoming(NextVar, LoopEndBB);
1509 // Restore the unshadowed variable.
1511 NamedValues[VarName] = OldVal;
1513 NamedValues.erase(VarName);
1516 // for expr always returns 0.0.
1517 return Constant::getNullValue(Type::DoubleTy);
1520 Function *PrototypeAST::Codegen() {
1521 // Make the function type: double(double,double) etc.
1522 std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
1523 FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
1525 Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
1527 // If F conflicted, there was already something named 'Name'. If it has a
1528 // body, don't allow redefinition or reextern.
1529 if (F->getName() != Name) {
1530 // Delete the one we just made and get the existing one.
1531 F->eraseFromParent();
1532 F = TheModule->getFunction(Name);
1534 // If F already has a body, reject this.
1535 if (!F->empty()) {
1536 ErrorF("redefinition of function");
1540 // If F took a different number of args, reject.
1541 if (F->arg_size() != Args.size()) {
1542 ErrorF("redefinition of function with different # args");
1547 // Set names for all arguments.
1549 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1551 AI->setName(Args[Idx]);
1553 // Add arguments to variable symbol table.
1554 NamedValues[Args[Idx]] = AI;
1560 Function *FunctionAST::Codegen() {
1561 NamedValues.clear();
1563 Function *TheFunction = Proto->Codegen();
1564 if (TheFunction == 0)
1567 // Create a new basic block to start insertion into.
1568 BasicBlock *BB = new BasicBlock("entry", TheFunction);
1569 Builder.SetInsertPoint(BB);
1571 if (Value *RetVal = Body->Codegen()) {
1572 // Finish off the function.
1573 Builder.CreateRet(RetVal);
1575 // Validate the generated code, checking for consistency.
1576 verifyFunction(*TheFunction);
1578 // Optimize the function.
1579 TheFPM->run(*TheFunction);
1584 // Error reading body, remove function.
1585 TheFunction->eraseFromParent();
1589 //===----------------------------------------------------------------------===//
1590 // Top-Level parsing and JIT Driver
1591 //===----------------------------------------------------------------------===//
1593 static ExecutionEngine *TheExecutionEngine;
1595 static void HandleDefinition() {
1596 if (FunctionAST *F = ParseDefinition()) {
1597 if (Function *LF = F->Codegen()) {
1598 fprintf(stderr, "Read function definition:");
1602 // Skip token for error recovery.
1607 static void HandleExtern() {
1608 if (PrototypeAST *P = ParseExtern()) {
1609 if (Function *F = P->Codegen()) {
1610 fprintf(stderr, "Read extern: ");
1614 // Skip token for error recovery.
1619 static void HandleTopLevelExpression() {
1620 // Evaluate a top level expression into an anonymous function.
1621 if (FunctionAST *F = ParseTopLevelExpr()) {
1622 if (Function *LF = F->Codegen()) {
1623 // JIT the function, returning a function pointer.
1624 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1626 // Cast it to the right type (takes no arguments, returns a double) so we
1627 // can call it as a native function.
1628 double (*FP)() = (double (*)())FPtr;
1629 fprintf(stderr, "Evaluated to %f\n", FP());
1632 // Skip token for error recovery.
1637 /// top ::= definition | external | expression | ';'
1638 static void MainLoop() {
1640 fprintf(stderr, "ready> ");
1642 case tok_eof: return;
1643 case ';': getNextToken(); break; // ignore top level semicolons.
1644 case tok_def: HandleDefinition(); break;
1645 case tok_extern: HandleExtern(); break;
1646 default: HandleTopLevelExpression(); break;
1653 //===----------------------------------------------------------------------===//
1654 // "Library" functions that can be "extern'd" from user code.
1655 //===----------------------------------------------------------------------===//
1657 /// putchard - putchar that takes a double and returns 0.
1659 double putchard(double X) {
1664 //===----------------------------------------------------------------------===//
1665 // Main driver code.
1666 //===----------------------------------------------------------------------===//
1669 // Install standard binary operators.
1670 // 1 is lowest precedence.
1671 BinopPrecedence['<'] = 10;
1672 BinopPrecedence['+'] = 20;
1673 BinopPrecedence['-'] = 20;
1674 BinopPrecedence['*'] = 40; // highest.
1676 // Prime the first token.
1677 fprintf(stderr, "ready> ");
1680 // Make the module, which holds all the code.
1681 TheModule = new Module("my cool jit");
1684 TheExecutionEngine = ExecutionEngine::create(TheModule);
1687 ExistingModuleProvider OurModuleProvider(TheModule);
1688 FunctionPassManager OurFPM(&OurModuleProvider);
1690 // Set up the optimizer pipeline. Start with registering info about how the
1691 // target lays out data structures.
1692 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1693 // Do simple "peephole" optimizations and bit-twiddling optzns.
1694 OurFPM.add(createInstructionCombiningPass());
1695 // Reassociate expressions.
1696 OurFPM.add(createReassociatePass());
1697 // Eliminate Common SubExpressions.
1698 OurFPM.add(createGVNPass());
1699 // Simplify the control flow graph (deleting unreachable blocks, etc).
1700 OurFPM.add(createCFGSimplificationPass());
1701 // Set the global so the code gen can use this.
1702 TheFPM = &OurFPM;
1704 // Run the main "interpreter loop" now.
1708 } // Free module provider and pass manager.
1711 // Print out all of the generated code.
1712 TheModule->dump();
1720 <!-- *********************************************************************** -->
1723 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1724 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1725 <a href="http://validator.w3.org/check/referer"><img
1726 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1728 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1729 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1730 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $