1 ==================================================
2 Kaleidoscope: Extending the Language: Control Flow
3 ==================================================
8 Written by `Chris Lattner <mailto:sabre@nondot.org>`_
10 Chapter 5 Introduction
11 ======================
13 Welcome to Chapter 5 of the "`Implementing a language with
14 LLVM <index.html>`_" tutorial. Parts 1-4 described the implementation of
15 the simple Kaleidoscope language and included support for generating
16 LLVM IR, followed by optimizations and a JIT compiler. Unfortunately, as
17 presented, Kaleidoscope is mostly useless: it has no control flow other
18 than call and return. This means that you can't have conditional
19 branches in the code, significantly limiting its power. In this episode
20 of "build that compiler", we'll extend Kaleidoscope to have an
21 if/then/else expression plus a simple 'for' loop.
26 Extending Kaleidoscope to support if/then/else is quite straightforward.
27 It basically requires adding support for this "new" concept to the
28 lexer, parser, AST, and LLVM code emitter. This example is nice, because
29 it shows how easy it is to "grow" a language over time, incrementally
30 extending it as new ideas are discovered.
32 Before we get going on "how" we add this extension, lets talk about
33 "what" we want. The basic idea is that we want to be able to write this
44 In Kaleidoscope, every construct is an expression: there are no
45 statements. As such, the if/then/else expression needs to return a value
46 like any other. Since we're using a mostly functional form, we'll have
47 it evaluate its conditional, then return the 'then' or 'else' value
48 based on how the condition was resolved. This is very similar to the C
51 The semantics of the if/then/else expression is that it evaluates the
52 condition to a boolean equality value: 0.0 is considered to be false and
53 everything else is considered to be true. If the condition is true, the
54 first subexpression is evaluated and returned, if the condition is
55 false, the second subexpression is evaluated and returned. Since
56 Kaleidoscope allows side-effects, this behavior is important to nail
59 Now that we know what we "want", lets break this down into its
62 Lexer Extensions for If/Then/Else
63 ---------------------------------
65 The lexer extensions are straightforward. First we add new enum values
66 for the relevant tokens:
71 tok_if = -6, tok_then = -7, tok_else = -8,
73 Once we have that, we recognize the new keywords in the lexer. This is
79 if (IdentifierStr == "def") return tok_def;
80 if (IdentifierStr == "extern") return tok_extern;
81 if (IdentifierStr == "if") return tok_if;
82 if (IdentifierStr == "then") return tok_then;
83 if (IdentifierStr == "else") return tok_else;
84 return tok_identifier;
86 AST Extensions for If/Then/Else
87 -------------------------------
89 To represent the new expression we add a new AST node for it:
93 /// IfExprAST - Expression class for if/then/else.
94 class IfExprAST : public ExprAST {
95 ExprAST *Cond, *Then, *Else;
97 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
98 : Cond(cond), Then(then), Else(_else) {}
99 virtual Value *Codegen();
102 The AST node just has pointers to the various subexpressions.
104 Parser Extensions for If/Then/Else
105 ----------------------------------
107 Now that we have the relevant tokens coming from the lexer and we have
108 the AST node to build, our parsing logic is relatively straightforward.
109 First we define a new parsing function:
113 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
114 static ExprAST *ParseIfExpr() {
115 getNextToken(); // eat the if.
118 ExprAST *Cond = ParseExpression();
121 if (CurTok != tok_then)
122 return Error("expected then");
123 getNextToken(); // eat the then
125 ExprAST *Then = ParseExpression();
126 if (Then == 0) return 0;
128 if (CurTok != tok_else)
129 return Error("expected else");
133 ExprAST *Else = ParseExpression();
136 return new IfExprAST(Cond, Then, Else);
139 Next we hook it up as a primary expression:
143 static ExprAST *ParsePrimary() {
145 default: return Error("unknown token when expecting an expression");
146 case tok_identifier: return ParseIdentifierExpr();
147 case tok_number: return ParseNumberExpr();
148 case '(': return ParseParenExpr();
149 case tok_if: return ParseIfExpr();
153 LLVM IR for If/Then/Else
154 ------------------------
156 Now that we have it parsing and building the AST, the final piece is
157 adding LLVM code generation support. This is the most interesting part
158 of the if/then/else example, because this is where it starts to
159 introduce new concepts. All of the code above has been thoroughly
160 described in previous chapters.
162 To motivate the code we want to produce, lets take a look at a simple
169 def baz(x) if x then foo() else bar();
171 If you disable optimizations, the code you'll (soon) get from
172 Kaleidoscope looks like this:
176 declare double @foo()
178 declare double @bar()
180 define double @baz(double %x) {
182 %ifcond = fcmp one double %x, 0.000000e+00
183 br i1 %ifcond, label %then, label %else
185 then: ; preds = %entry
186 %calltmp = call double @foo()
189 else: ; preds = %entry
190 %calltmp1 = call double @bar()
193 ifcont: ; preds = %else, %then
194 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
198 To visualize the control flow graph, you can use a nifty feature of the
199 LLVM '`opt <http://llvm.org/cmds/opt.html>`_' tool. If you put this LLVM
200 IR into "t.ll" and run "``llvm-as < t.ll | opt -analyze -view-cfg``", `a
201 window will pop up <../ProgrammersManual.html#ViewGraph>`_ and you'll
204 .. figure:: LangImpl5-cfg.png
210 Another way to get this is to call "``F->viewCFG()``" or
211 "``F->viewCFGOnly()``" (where F is a "``Function*``") either by
212 inserting actual calls into the code and recompiling or by calling these
213 in the debugger. LLVM has many nice features for visualizing various
216 Getting back to the generated code, it is fairly simple: the entry block
217 evaluates the conditional expression ("x" in our case here) and compares
218 the result to 0.0 with the "``fcmp one``" instruction ('one' is "Ordered
219 and Not Equal"). Based on the result of this expression, the code jumps
220 to either the "then" or "else" blocks, which contain the expressions for
221 the true/false cases.
223 Once the then/else blocks are finished executing, they both branch back
224 to the 'ifcont' block to execute the code that happens after the
225 if/then/else. In this case the only thing left to do is to return to the
226 caller of the function. The question then becomes: how does the code
227 know which expression to return?
229 The answer to this question involves an important SSA operation: the
231 operation <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_.
232 If you're not familiar with SSA, `the wikipedia
233 article <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_
234 is a good introduction and there are various other introductions to it
235 available on your favorite search engine. The short version is that
236 "execution" of the Phi operation requires "remembering" which block
237 control came from. The Phi operation takes on the value corresponding to
238 the input control block. In this case, if control comes in from the
239 "then" block, it gets the value of "calltmp". If control comes from the
240 "else" block, it gets the value of "calltmp1".
242 At this point, you are probably starting to think "Oh no! This means my
243 simple and elegant front-end will have to start generating SSA form in
244 order to use LLVM!". Fortunately, this is not the case, and we strongly
245 advise *not* implementing an SSA construction algorithm in your
246 front-end unless there is an amazingly good reason to do so. In
247 practice, there are two sorts of values that float around in code
248 written for your average imperative programming language that might need
251 #. Code that involves user variables: ``x = 1; x = x + 1;``
252 #. Values that are implicit in the structure of your AST, such as the
253 Phi node in this case.
255 In `Chapter 7 <LangImpl7.html>`_ of this tutorial ("mutable variables"),
256 we'll talk about #1 in depth. For now, just believe me that you don't
257 need SSA construction to handle this case. For #2, you have the choice
258 of using the techniques that we will describe for #1, or you can insert
259 Phi nodes directly, if convenient. In this case, it is really really
260 easy to generate the Phi node, so we choose to do it directly.
262 Okay, enough of the motivation and overview, lets generate code!
264 Code Generation for If/Then/Else
265 --------------------------------
267 In order to generate code for this, we implement the ``Codegen`` method
272 Value *IfExprAST::Codegen() {
273 Value *CondV = Cond->Codegen();
274 if (CondV == 0) return 0;
276 // Convert condition to a bool by comparing equal to 0.0.
277 CondV = Builder.CreateFCmpONE(CondV,
278 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
281 This code is straightforward and similar to what we saw before. We emit
282 the expression for the condition, then compare that value to zero to get
283 a truth value as a 1-bit (bool) value.
287 Function *TheFunction = Builder.GetInsertBlock()->getParent();
289 // Create blocks for the then and else cases. Insert the 'then' block at the
290 // end of the function.
291 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
292 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
293 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
295 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
297 This code creates the basic blocks that are related to the if/then/else
298 statement, and correspond directly to the blocks in the example above.
299 The first line gets the current Function object that is being built. It
300 gets this by asking the builder for the current BasicBlock, and asking
301 that block for its "parent" (the function it is currently embedded
304 Once it has that, it creates three blocks. Note that it passes
305 "TheFunction" into the constructor for the "then" block. This causes the
306 constructor to automatically insert the new block into the end of the
307 specified function. The other two blocks are created, but aren't yet
308 inserted into the function.
310 Once the blocks are created, we can emit the conditional branch that
311 chooses between them. Note that creating new blocks does not implicitly
312 affect the IRBuilder, so it is still inserting into the block that the
313 condition went into. Also note that it is creating a branch to the
314 "then" block and the "else" block, even though the "else" block isn't
315 inserted into the function yet. This is all ok: it is the standard way
316 that LLVM supports forward references.
321 Builder.SetInsertPoint(ThenBB);
323 Value *ThenV = Then->Codegen();
324 if (ThenV == 0) return 0;
326 Builder.CreateBr(MergeBB);
327 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
328 ThenBB = Builder.GetInsertBlock();
330 After the conditional branch is inserted, we move the builder to start
331 inserting into the "then" block. Strictly speaking, this call moves the
332 insertion point to be at the end of the specified block. However, since
333 the "then" block is empty, it also starts out by inserting at the
334 beginning of the block. :)
336 Once the insertion point is set, we recursively codegen the "then"
337 expression from the AST. To finish off the "then" block, we create an
338 unconditional branch to the merge block. One interesting (and very
339 important) aspect of the LLVM IR is that it `requires all basic blocks
340 to be "terminated" <../LangRef.html#functionstructure>`_ with a `control
341 flow instruction <../LangRef.html#terminators>`_ such as return or
342 branch. This means that all control flow, *including fall throughs* must
343 be made explicit in the LLVM IR. If you violate this rule, the verifier
346 The final line here is quite subtle, but is very important. The basic
347 issue is that when we create the Phi node in the merge block, we need to
348 set up the block/value pairs that indicate how the Phi will work.
349 Importantly, the Phi node expects to have an entry for each predecessor
350 of the block in the CFG. Why then, are we getting the current block when
351 we just set it to ThenBB 5 lines above? The problem is that the "Then"
352 expression may actually itself change the block that the Builder is
353 emitting into if, for example, it contains a nested "if/then/else"
354 expression. Because calling Codegen recursively could arbitrarily change
355 the notion of the current block, we are required to get an up-to-date
356 value for code that will set up the Phi node.
361 TheFunction->getBasicBlockList().push_back(ElseBB);
362 Builder.SetInsertPoint(ElseBB);
364 Value *ElseV = Else->Codegen();
365 if (ElseV == 0) return 0;
367 Builder.CreateBr(MergeBB);
368 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
369 ElseBB = Builder.GetInsertBlock();
371 Code generation for the 'else' block is basically identical to codegen
372 for the 'then' block. The only significant difference is the first line,
373 which adds the 'else' block to the function. Recall previously that the
374 'else' block was created, but not added to the function. Now that the
375 'then' and 'else' blocks are emitted, we can finish up with the merge
381 TheFunction->getBasicBlockList().push_back(MergeBB);
382 Builder.SetInsertPoint(MergeBB);
383 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
386 PN->addIncoming(ThenV, ThenBB);
387 PN->addIncoming(ElseV, ElseBB);
391 The first two lines here are now familiar: the first adds the "merge"
392 block to the Function object (it was previously floating, like the else
393 block above). The second block changes the insertion point so that newly
394 created code will go into the "merge" block. Once that is done, we need
395 to create the PHI node and set up the block/value pairs for the PHI.
397 Finally, the CodeGen function returns the phi node as the value computed
398 by the if/then/else expression. In our example above, this returned
399 value will feed into the code for the top-level function, which will
400 create the return instruction.
402 Overall, we now have the ability to execute conditional code in
403 Kaleidoscope. With this extension, Kaleidoscope is a fairly complete
404 language that can calculate a wide variety of numeric functions. Next up
405 we'll add another useful expression that is familiar from non-functional
408 'for' Loop Expression
409 =====================
411 Now that we know how to add basic control flow constructs to the
412 language, we have the tools to add more powerful things. Lets add
413 something more aggressive, a 'for' expression:
417 extern putchard(char)
419 for i = 1, i < n, 1.0 in
420 putchard(42); # ascii 42 = '*'
422 # print 100 '*' characters
425 This expression defines a new variable ("i" in this case) which iterates
426 from a starting value, while the condition ("i < n" in this case) is
427 true, incrementing by an optional step value ("1.0" in this case). If
428 the step value is omitted, it defaults to 1.0. While the loop is true,
429 it executes its body expression. Because we don't have anything better
430 to return, we'll just define the loop as always returning 0.0. In the
431 future when we have mutable variables, it will get more useful.
433 As before, lets talk about the changes that we need to Kaleidoscope to
436 Lexer Extensions for the 'for' Loop
437 -----------------------------------
439 The lexer extensions are the same sort of thing as for if/then/else:
443 ... in enum Token ...
445 tok_if = -6, tok_then = -7, tok_else = -8,
446 tok_for = -9, tok_in = -10
449 if (IdentifierStr == "def") return tok_def;
450 if (IdentifierStr == "extern") return tok_extern;
451 if (IdentifierStr == "if") return tok_if;
452 if (IdentifierStr == "then") return tok_then;
453 if (IdentifierStr == "else") return tok_else;
454 if (IdentifierStr == "for") return tok_for;
455 if (IdentifierStr == "in") return tok_in;
456 return tok_identifier;
458 AST Extensions for the 'for' Loop
459 ---------------------------------
461 The AST node is just as simple. It basically boils down to capturing the
462 variable name and the constituent expressions in the node.
466 /// ForExprAST - Expression class for for/in.
467 class ForExprAST : public ExprAST {
469 ExprAST *Start, *End, *Step, *Body;
471 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
472 ExprAST *step, ExprAST *body)
473 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
474 virtual Value *Codegen();
477 Parser Extensions for the 'for' Loop
478 ------------------------------------
480 The parser code is also fairly standard. The only interesting thing here
481 is handling of the optional step value. The parser code handles it by
482 checking to see if the second comma is present. If not, it sets the step
483 value to null in the AST node:
487 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
488 static ExprAST *ParseForExpr() {
489 getNextToken(); // eat the for.
491 if (CurTok != tok_identifier)
492 return Error("expected identifier after for");
494 std::string IdName = IdentifierStr;
495 getNextToken(); // eat identifier.
498 return Error("expected '=' after for");
499 getNextToken(); // eat '='.
502 ExprAST *Start = ParseExpression();
503 if (Start == 0) return 0;
505 return Error("expected ',' after for start value");
508 ExprAST *End = ParseExpression();
509 if (End == 0) return 0;
511 // The step value is optional.
515 Step = ParseExpression();
516 if (Step == 0) return 0;
519 if (CurTok != tok_in)
520 return Error("expected 'in' after for");
521 getNextToken(); // eat 'in'.
523 ExprAST *Body = ParseExpression();
524 if (Body == 0) return 0;
526 return new ForExprAST(IdName, Start, End, Step, Body);
529 LLVM IR for the 'for' Loop
530 --------------------------
532 Now we get to the good part: the LLVM IR we want to generate for this
533 thing. With the simple example above, we get this LLVM IR (note that
534 this dump is generated with optimizations disabled for clarity):
538 declare double @putchard(double)
540 define double @printstar(double %n) {
542 ; initial value = 1.0 (inlined into phi)
545 loop: ; preds = %loop, %entry
546 %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
548 %calltmp = call double @putchard(double 4.200000e+01)
550 %nextvar = fadd double %i, 1.000000e+00
553 %cmptmp = fcmp ult double %i, %n
554 %booltmp = uitofp i1 %cmptmp to double
555 %loopcond = fcmp one double %booltmp, 0.000000e+00
556 br i1 %loopcond, label %loop, label %afterloop
558 afterloop: ; preds = %loop
559 ; loop always returns 0.0
560 ret double 0.000000e+00
563 This loop contains all the same constructs we saw before: a phi node,
564 several expressions, and some basic blocks. Lets see how this fits
567 Code Generation for the 'for' Loop
568 ----------------------------------
570 The first part of Codegen is very simple: we just output the start
571 expression for the loop value:
575 Value *ForExprAST::Codegen() {
576 // Emit the start code first, without 'variable' in scope.
577 Value *StartVal = Start->Codegen();
578 if (StartVal == 0) return 0;
580 With this out of the way, the next step is to set up the LLVM basic
581 block for the start of the loop body. In the case above, the whole loop
582 body is one block, but remember that the body code itself could consist
583 of multiple blocks (e.g. if it contains an if/then/else or a for/in
588 // Make the new basic block for the loop header, inserting after current
590 Function *TheFunction = Builder.GetInsertBlock()->getParent();
591 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
592 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
594 // Insert an explicit fall through from the current block to the LoopBB.
595 Builder.CreateBr(LoopBB);
597 This code is similar to what we saw for if/then/else. Because we will
598 need it to create the Phi node, we remember the block that falls through
599 into the loop. Once we have that, we create the actual block that starts
600 the loop and create an unconditional branch for the fall-through between
605 // Start insertion in LoopBB.
606 Builder.SetInsertPoint(LoopBB);
608 // Start the PHI node with an entry for Start.
609 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
610 Variable->addIncoming(StartVal, PreheaderBB);
612 Now that the "preheader" for the loop is set up, we switch to emitting
613 code for the loop body. To begin with, we move the insertion point and
614 create the PHI node for the loop induction variable. Since we already
615 know the incoming value for the starting value, we add it to the Phi
616 node. Note that the Phi will eventually get a second value for the
617 backedge, but we can't set it up yet (because it doesn't exist!).
621 // Within the loop, the variable is defined equal to the PHI node. If it
622 // shadows an existing variable, we have to restore it, so save it now.
623 Value *OldVal = NamedValues[VarName];
624 NamedValues[VarName] = Variable;
626 // Emit the body of the loop. This, like any other expr, can change the
627 // current BB. Note that we ignore the value computed by the body, but don't
629 if (Body->Codegen() == 0)
632 Now the code starts to get more interesting. Our 'for' loop introduces a
633 new variable to the symbol table. This means that our symbol table can
634 now contain either function arguments or loop variables. To handle this,
635 before we codegen the body of the loop, we add the loop variable as the
636 current value for its name. Note that it is possible that there is a
637 variable of the same name in the outer scope. It would be easy to make
638 this an error (emit an error and return null if there is already an
639 entry for VarName) but we choose to allow shadowing of variables. In
640 order to handle this correctly, we remember the Value that we are
641 potentially shadowing in ``OldVal`` (which will be null if there is no
644 Once the loop variable is set into the symbol table, the code
645 recursively codegen's the body. This allows the body to use the loop
646 variable: any references to it will naturally find it in the symbol
651 // Emit the step value.
654 StepVal = Step->Codegen();
655 if (StepVal == 0) return 0;
657 // If not specified, use 1.0.
658 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
661 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
663 Now that the body is emitted, we compute the next value of the iteration
664 variable by adding the step value, or 1.0 if it isn't present.
665 '``NextVar``' will be the value of the loop variable on the next
666 iteration of the loop.
670 // Compute the end condition.
671 Value *EndCond = End->Codegen();
672 if (EndCond == 0) return EndCond;
674 // Convert condition to a bool by comparing equal to 0.0.
675 EndCond = Builder.CreateFCmpONE(EndCond,
676 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
679 Finally, we evaluate the exit value of the loop, to determine whether
680 the loop should exit. This mirrors the condition evaluation for the
681 if/then/else statement.
685 // Create the "after loop" block and insert it.
686 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
687 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
689 // Insert the conditional branch into the end of LoopEndBB.
690 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
692 // Any new code will be inserted in AfterBB.
693 Builder.SetInsertPoint(AfterBB);
695 With the code for the body of the loop complete, we just need to finish
696 up the control flow for it. This code remembers the end block (for the
697 phi node), then creates the block for the loop exit ("afterloop"). Based
698 on the value of the exit condition, it creates a conditional branch that
699 chooses between executing the loop again and exiting the loop. Any
700 future code is emitted in the "afterloop" block, so it sets the
701 insertion position to it.
705 // Add a new entry to the PHI node for the backedge.
706 Variable->addIncoming(NextVar, LoopEndBB);
708 // Restore the unshadowed variable.
710 NamedValues[VarName] = OldVal;
712 NamedValues.erase(VarName);
714 // for expr always returns 0.0.
715 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
718 The final code handles various cleanups: now that we have the "NextVar"
719 value, we can add the incoming value to the loop PHI node. After that,
720 we remove the loop variable from the symbol table, so that it isn't in
721 scope after the for loop. Finally, code generation of the for loop
722 always returns 0.0, so that is what we return from
723 ``ForExprAST::Codegen``.
725 With this, we conclude the "adding control flow to Kaleidoscope" chapter
726 of the tutorial. In this chapter we added two control flow constructs,
727 and used them to motivate a couple of aspects of the LLVM IR that are
728 important for front-end implementors to know. In the next chapter of our
729 saga, we will get a bit crazier and add `user-defined
730 operators <LangImpl6.html>`_ to our poor innocent language.
735 Here is the complete code listing for our running example, enhanced with
736 the if/then/else and for expressions.. To build this example, use:
741 clang++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
749 #include "llvm/DerivedTypes.h"
750 #include "llvm/ExecutionEngine/ExecutionEngine.h"
751 #include "llvm/ExecutionEngine/JIT.h"
752 #include "llvm/IRBuilder.h"
753 #include "llvm/LLVMContext.h"
754 #include "llvm/Module.h"
755 #include "llvm/PassManager.h"
756 #include "llvm/Analysis/Verifier.h"
757 #include "llvm/Analysis/Passes.h"
758 #include "llvm/DataLayout.h"
759 #include "llvm/Transforms/Scalar.h"
760 #include "llvm/Support/TargetSelect.h"
765 using namespace llvm;
767 //===----------------------------------------------------------------------===//
769 //===----------------------------------------------------------------------===//
771 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
772 // of these for known things.
777 tok_def = -2, tok_extern = -3,
780 tok_identifier = -4, tok_number = -5,
783 tok_if = -6, tok_then = -7, tok_else = -8,
784 tok_for = -9, tok_in = -10
787 static std::string IdentifierStr; // Filled in if tok_identifier
788 static double NumVal; // Filled in if tok_number
790 /// gettok - Return the next token from standard input.
791 static int gettok() {
792 static int LastChar = ' ';
794 // Skip any whitespace.
795 while (isspace(LastChar))
796 LastChar = getchar();
798 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
799 IdentifierStr = LastChar;
800 while (isalnum((LastChar = getchar())))
801 IdentifierStr += LastChar;
803 if (IdentifierStr == "def") return tok_def;
804 if (IdentifierStr == "extern") return tok_extern;
805 if (IdentifierStr == "if") return tok_if;
806 if (IdentifierStr == "then") return tok_then;
807 if (IdentifierStr == "else") return tok_else;
808 if (IdentifierStr == "for") return tok_for;
809 if (IdentifierStr == "in") return tok_in;
810 return tok_identifier;
813 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
817 LastChar = getchar();
818 } while (isdigit(LastChar) || LastChar == '.');
820 NumVal = strtod(NumStr.c_str(), 0);
824 if (LastChar == '#') {
825 // Comment until end of line.
826 do LastChar = getchar();
827 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
833 // Check for end of file. Don't eat the EOF.
837 // Otherwise, just return the character as its ascii value.
838 int ThisChar = LastChar;
839 LastChar = getchar();
843 //===----------------------------------------------------------------------===//
844 // Abstract Syntax Tree (aka Parse Tree)
845 //===----------------------------------------------------------------------===//
847 /// ExprAST - Base class for all expression nodes.
850 virtual ~ExprAST() {}
851 virtual Value *Codegen() = 0;
854 /// NumberExprAST - Expression class for numeric literals like "1.0".
855 class NumberExprAST : public ExprAST {
858 NumberExprAST(double val) : Val(val) {}
859 virtual Value *Codegen();
862 /// VariableExprAST - Expression class for referencing a variable, like "a".
863 class VariableExprAST : public ExprAST {
866 VariableExprAST(const std::string &name) : Name(name) {}
867 virtual Value *Codegen();
870 /// BinaryExprAST - Expression class for a binary operator.
871 class BinaryExprAST : public ExprAST {
875 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
876 : Op(op), LHS(lhs), RHS(rhs) {}
877 virtual Value *Codegen();
880 /// CallExprAST - Expression class for function calls.
881 class CallExprAST : public ExprAST {
883 std::vector<ExprAST*> Args;
885 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
886 : Callee(callee), Args(args) {}
887 virtual Value *Codegen();
890 /// IfExprAST - Expression class for if/then/else.
891 class IfExprAST : public ExprAST {
892 ExprAST *Cond, *Then, *Else;
894 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
895 : Cond(cond), Then(then), Else(_else) {}
896 virtual Value *Codegen();
899 /// ForExprAST - Expression class for for/in.
900 class ForExprAST : public ExprAST {
902 ExprAST *Start, *End, *Step, *Body;
904 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
905 ExprAST *step, ExprAST *body)
906 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
907 virtual Value *Codegen();
910 /// PrototypeAST - This class represents the "prototype" for a function,
911 /// which captures its name, and its argument names (thus implicitly the number
912 /// of arguments the function takes).
915 std::vector<std::string> Args;
917 PrototypeAST(const std::string &name, const std::vector<std::string> &args)
918 : Name(name), Args(args) {}
923 /// FunctionAST - This class represents a function definition itself.
928 FunctionAST(PrototypeAST *proto, ExprAST *body)
929 : Proto(proto), Body(body) {}
934 //===----------------------------------------------------------------------===//
936 //===----------------------------------------------------------------------===//
938 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
939 /// token the parser is looking at. getNextToken reads another token from the
940 /// lexer and updates CurTok with its results.
942 static int getNextToken() {
943 return CurTok = gettok();
946 /// BinopPrecedence - This holds the precedence for each binary operator that is
948 static std::map<char, int> BinopPrecedence;
950 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
951 static int GetTokPrecedence() {
952 if (!isascii(CurTok))
955 // Make sure it's a declared binop.
956 int TokPrec = BinopPrecedence[CurTok];
957 if (TokPrec <= 0) return -1;
961 /// Error* - These are little helper functions for error handling.
962 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
963 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
964 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
966 static ExprAST *ParseExpression();
970 /// ::= identifier '(' expression* ')'
971 static ExprAST *ParseIdentifierExpr() {
972 std::string IdName = IdentifierStr;
974 getNextToken(); // eat identifier.
976 if (CurTok != '(') // Simple variable ref.
977 return new VariableExprAST(IdName);
980 getNextToken(); // eat (
981 std::vector<ExprAST*> Args;
984 ExprAST *Arg = ParseExpression();
988 if (CurTok == ')') break;
991 return Error("Expected ')' or ',' in argument list");
999 return new CallExprAST(IdName, Args);
1002 /// numberexpr ::= number
1003 static ExprAST *ParseNumberExpr() {
1004 ExprAST *Result = new NumberExprAST(NumVal);
1005 getNextToken(); // consume the number
1009 /// parenexpr ::= '(' expression ')'
1010 static ExprAST *ParseParenExpr() {
1011 getNextToken(); // eat (.
1012 ExprAST *V = ParseExpression();
1016 return Error("expected ')'");
1017 getNextToken(); // eat ).
1021 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1022 static ExprAST *ParseIfExpr() {
1023 getNextToken(); // eat the if.
1026 ExprAST *Cond = ParseExpression();
1027 if (!Cond) return 0;
1029 if (CurTok != tok_then)
1030 return Error("expected then");
1031 getNextToken(); // eat the then
1033 ExprAST *Then = ParseExpression();
1034 if (Then == 0) return 0;
1036 if (CurTok != tok_else)
1037 return Error("expected else");
1041 ExprAST *Else = ParseExpression();
1042 if (!Else) return 0;
1044 return new IfExprAST(Cond, Then, Else);
1047 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1048 static ExprAST *ParseForExpr() {
1049 getNextToken(); // eat the for.
1051 if (CurTok != tok_identifier)
1052 return Error("expected identifier after for");
1054 std::string IdName = IdentifierStr;
1055 getNextToken(); // eat identifier.
1058 return Error("expected '=' after for");
1059 getNextToken(); // eat '='.
1062 ExprAST *Start = ParseExpression();
1063 if (Start == 0) return 0;
1065 return Error("expected ',' after for start value");
1068 ExprAST *End = ParseExpression();
1069 if (End == 0) return 0;
1071 // The step value is optional.
1073 if (CurTok == ',') {
1075 Step = ParseExpression();
1076 if (Step == 0) return 0;
1079 if (CurTok != tok_in)
1080 return Error("expected 'in' after for");
1081 getNextToken(); // eat 'in'.
1083 ExprAST *Body = ParseExpression();
1084 if (Body == 0) return 0;
1086 return new ForExprAST(IdName, Start, End, Step, Body);
1090 /// ::= identifierexpr
1095 static ExprAST *ParsePrimary() {
1097 default: return Error("unknown token when expecting an expression");
1098 case tok_identifier: return ParseIdentifierExpr();
1099 case tok_number: return ParseNumberExpr();
1100 case '(': return ParseParenExpr();
1101 case tok_if: return ParseIfExpr();
1102 case tok_for: return ParseForExpr();
1107 /// ::= ('+' primary)*
1108 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1109 // If this is a binop, find its precedence.
1111 int TokPrec = GetTokPrecedence();
1113 // If this is a binop that binds at least as tightly as the current binop,
1114 // consume it, otherwise we are done.
1115 if (TokPrec < ExprPrec)
1118 // Okay, we know this is a binop.
1120 getNextToken(); // eat binop
1122 // Parse the primary expression after the binary operator.
1123 ExprAST *RHS = ParsePrimary();
1126 // If BinOp binds less tightly with RHS than the operator after RHS, let
1127 // the pending operator take RHS as its LHS.
1128 int NextPrec = GetTokPrecedence();
1129 if (TokPrec < NextPrec) {
1130 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1131 if (RHS == 0) return 0;
1135 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1140 /// ::= primary binoprhs
1142 static ExprAST *ParseExpression() {
1143 ExprAST *LHS = ParsePrimary();
1146 return ParseBinOpRHS(0, LHS);
1150 /// ::= id '(' id* ')'
1151 static PrototypeAST *ParsePrototype() {
1152 if (CurTok != tok_identifier)
1153 return ErrorP("Expected function name in prototype");
1155 std::string FnName = IdentifierStr;
1159 return ErrorP("Expected '(' in prototype");
1161 std::vector<std::string> ArgNames;
1162 while (getNextToken() == tok_identifier)
1163 ArgNames.push_back(IdentifierStr);
1165 return ErrorP("Expected ')' in prototype");
1168 getNextToken(); // eat ')'.
1170 return new PrototypeAST(FnName, ArgNames);
1173 /// definition ::= 'def' prototype expression
1174 static FunctionAST *ParseDefinition() {
1175 getNextToken(); // eat def.
1176 PrototypeAST *Proto = ParsePrototype();
1177 if (Proto == 0) return 0;
1179 if (ExprAST *E = ParseExpression())
1180 return new FunctionAST(Proto, E);
1184 /// toplevelexpr ::= expression
1185 static FunctionAST *ParseTopLevelExpr() {
1186 if (ExprAST *E = ParseExpression()) {
1187 // Make an anonymous proto.
1188 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
1189 return new FunctionAST(Proto, E);
1194 /// external ::= 'extern' prototype
1195 static PrototypeAST *ParseExtern() {
1196 getNextToken(); // eat extern.
1197 return ParsePrototype();
1200 //===----------------------------------------------------------------------===//
1202 //===----------------------------------------------------------------------===//
1204 static Module *TheModule;
1205 static IRBuilder<> Builder(getGlobalContext());
1206 static std::map<std::string, Value*> NamedValues;
1207 static FunctionPassManager *TheFPM;
1209 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1211 Value *NumberExprAST::Codegen() {
1212 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1215 Value *VariableExprAST::Codegen() {
1216 // Look this variable up in the function.
1217 Value *V = NamedValues[Name];
1218 return V ? V : ErrorV("Unknown variable name");
1221 Value *BinaryExprAST::Codegen() {
1222 Value *L = LHS->Codegen();
1223 Value *R = RHS->Codegen();
1224 if (L == 0 || R == 0) return 0;
1227 case '+': return Builder.CreateFAdd(L, R, "addtmp");
1228 case '-': return Builder.CreateFSub(L, R, "subtmp");
1229 case '*': return Builder.CreateFMul(L, R, "multmp");
1231 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1232 // Convert bool 0/1 to double 0.0 or 1.0
1233 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1235 default: return ErrorV("invalid binary operator");
1239 Value *CallExprAST::Codegen() {
1240 // Look up the name in the global module table.
1241 Function *CalleeF = TheModule->getFunction(Callee);
1243 return ErrorV("Unknown function referenced");
1245 // If argument mismatch error.
1246 if (CalleeF->arg_size() != Args.size())
1247 return ErrorV("Incorrect # arguments passed");
1249 std::vector<Value*> ArgsV;
1250 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1251 ArgsV.push_back(Args[i]->Codegen());
1252 if (ArgsV.back() == 0) return 0;
1255 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
1258 Value *IfExprAST::Codegen() {
1259 Value *CondV = Cond->Codegen();
1260 if (CondV == 0) return 0;
1262 // Convert condition to a bool by comparing equal to 0.0.
1263 CondV = Builder.CreateFCmpONE(CondV,
1264 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1267 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1269 // Create blocks for the then and else cases. Insert the 'then' block at the
1270 // end of the function.
1271 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1272 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1273 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1275 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1278 Builder.SetInsertPoint(ThenBB);
1280 Value *ThenV = Then->Codegen();
1281 if (ThenV == 0) return 0;
1283 Builder.CreateBr(MergeBB);
1284 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1285 ThenBB = Builder.GetInsertBlock();
1288 TheFunction->getBasicBlockList().push_back(ElseBB);
1289 Builder.SetInsertPoint(ElseBB);
1291 Value *ElseV = Else->Codegen();
1292 if (ElseV == 0) return 0;
1294 Builder.CreateBr(MergeBB);
1295 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1296 ElseBB = Builder.GetInsertBlock();
1298 // Emit merge block.
1299 TheFunction->getBasicBlockList().push_back(MergeBB);
1300 Builder.SetInsertPoint(MergeBB);
1301 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
1304 PN->addIncoming(ThenV, ThenBB);
1305 PN->addIncoming(ElseV, ElseBB);
1309 Value *ForExprAST::Codegen() {
1312 // start = startexpr
1315 // variable = phi [start, loopheader], [nextvariable, loopend]
1321 // nextvariable = variable + step
1322 // endcond = endexpr
1323 // br endcond, loop, endloop
1326 // Emit the start code first, without 'variable' in scope.
1327 Value *StartVal = Start->Codegen();
1328 if (StartVal == 0) return 0;
1330 // Make the new basic block for the loop header, inserting after current
1332 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1333 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1334 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1336 // Insert an explicit fall through from the current block to the LoopBB.
1337 Builder.CreateBr(LoopBB);
1339 // Start insertion in LoopBB.
1340 Builder.SetInsertPoint(LoopBB);
1342 // Start the PHI node with an entry for Start.
1343 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
1344 Variable->addIncoming(StartVal, PreheaderBB);
1346 // Within the loop, the variable is defined equal to the PHI node. If it
1347 // shadows an existing variable, we have to restore it, so save it now.
1348 Value *OldVal = NamedValues[VarName];
1349 NamedValues[VarName] = Variable;
1351 // Emit the body of the loop. This, like any other expr, can change the
1352 // current BB. Note that we ignore the value computed by the body, but don't
1354 if (Body->Codegen() == 0)
1357 // Emit the step value.
1360 StepVal = Step->Codegen();
1361 if (StepVal == 0) return 0;
1363 // If not specified, use 1.0.
1364 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1367 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
1369 // Compute the end condition.
1370 Value *EndCond = End->Codegen();
1371 if (EndCond == 0) return EndCond;
1373 // Convert condition to a bool by comparing equal to 0.0.
1374 EndCond = Builder.CreateFCmpONE(EndCond,
1375 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1378 // Create the "after loop" block and insert it.
1379 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1380 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1382 // Insert the conditional branch into the end of LoopEndBB.
1383 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1385 // Any new code will be inserted in AfterBB.
1386 Builder.SetInsertPoint(AfterBB);
1388 // Add a new entry to the PHI node for the backedge.
1389 Variable->addIncoming(NextVar, LoopEndBB);
1391 // Restore the unshadowed variable.
1393 NamedValues[VarName] = OldVal;
1395 NamedValues.erase(VarName);
1398 // for expr always returns 0.0.
1399 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1402 Function *PrototypeAST::Codegen() {
1403 // Make the function type: double(double,double) etc.
1404 std::vector<Type*> Doubles(Args.size(),
1405 Type::getDoubleTy(getGlobalContext()));
1406 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1409 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1411 // If F conflicted, there was already something named 'Name'. If it has a
1412 // body, don't allow redefinition or reextern.
1413 if (F->getName() != Name) {
1414 // Delete the one we just made and get the existing one.
1415 F->eraseFromParent();
1416 F = TheModule->getFunction(Name);
1418 // If F already has a body, reject this.
1420 ErrorF("redefinition of function");
1424 // If F took a different number of args, reject.
1425 if (F->arg_size() != Args.size()) {
1426 ErrorF("redefinition of function with different # args");
1431 // Set names for all arguments.
1433 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1435 AI->setName(Args[Idx]);
1437 // Add arguments to variable symbol table.
1438 NamedValues[Args[Idx]] = AI;
1444 Function *FunctionAST::Codegen() {
1445 NamedValues.clear();
1447 Function *TheFunction = Proto->Codegen();
1448 if (TheFunction == 0)
1451 // Create a new basic block to start insertion into.
1452 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1453 Builder.SetInsertPoint(BB);
1455 if (Value *RetVal = Body->Codegen()) {
1456 // Finish off the function.
1457 Builder.CreateRet(RetVal);
1459 // Validate the generated code, checking for consistency.
1460 verifyFunction(*TheFunction);
1462 // Optimize the function.
1463 TheFPM->run(*TheFunction);
1468 // Error reading body, remove function.
1469 TheFunction->eraseFromParent();
1473 //===----------------------------------------------------------------------===//
1474 // Top-Level parsing and JIT Driver
1475 //===----------------------------------------------------------------------===//
1477 static ExecutionEngine *TheExecutionEngine;
1479 static void HandleDefinition() {
1480 if (FunctionAST *F = ParseDefinition()) {
1481 if (Function *LF = F->Codegen()) {
1482 fprintf(stderr, "Read function definition:");
1486 // Skip token for error recovery.
1491 static void HandleExtern() {
1492 if (PrototypeAST *P = ParseExtern()) {
1493 if (Function *F = P->Codegen()) {
1494 fprintf(stderr, "Read extern: ");
1498 // Skip token for error recovery.
1503 static void HandleTopLevelExpression() {
1504 // Evaluate a top-level expression into an anonymous function.
1505 if (FunctionAST *F = ParseTopLevelExpr()) {
1506 if (Function *LF = F->Codegen()) {
1507 // JIT the function, returning a function pointer.
1508 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1510 // Cast it to the right type (takes no arguments, returns a double) so we
1511 // can call it as a native function.
1512 double (*FP)() = (double (*)())(intptr_t)FPtr;
1513 fprintf(stderr, "Evaluated to %f\n", FP());
1516 // Skip token for error recovery.
1521 /// top ::= definition | external | expression | ';'
1522 static void MainLoop() {
1524 fprintf(stderr, "ready> ");
1526 case tok_eof: return;
1527 case ';': getNextToken(); break; // ignore top-level semicolons.
1528 case tok_def: HandleDefinition(); break;
1529 case tok_extern: HandleExtern(); break;
1530 default: HandleTopLevelExpression(); break;
1535 //===----------------------------------------------------------------------===//
1536 // "Library" functions that can be "extern'd" from user code.
1537 //===----------------------------------------------------------------------===//
1539 /// putchard - putchar that takes a double and returns 0.
1541 double putchard(double X) {
1546 //===----------------------------------------------------------------------===//
1547 // Main driver code.
1548 //===----------------------------------------------------------------------===//
1551 InitializeNativeTarget();
1552 LLVMContext &Context = getGlobalContext();
1554 // Install standard binary operators.
1555 // 1 is lowest precedence.
1556 BinopPrecedence['<'] = 10;
1557 BinopPrecedence['+'] = 20;
1558 BinopPrecedence['-'] = 20;
1559 BinopPrecedence['*'] = 40; // highest.
1561 // Prime the first token.
1562 fprintf(stderr, "ready> ");
1565 // Make the module, which holds all the code.
1566 TheModule = new Module("my cool jit", Context);
1568 // Create the JIT. This takes ownership of the module.
1570 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
1571 if (!TheExecutionEngine) {
1572 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1576 FunctionPassManager OurFPM(TheModule);
1578 // Set up the optimizer pipeline. Start with registering info about how the
1579 // target lays out data structures.
1580 OurFPM.add(new DataLayout(*TheExecutionEngine->getDataLayout()));
1581 // Provide basic AliasAnalysis support for GVN.
1582 OurFPM.add(createBasicAliasAnalysisPass());
1583 // Do simple "peephole" optimizations and bit-twiddling optzns.
1584 OurFPM.add(createInstructionCombiningPass());
1585 // Reassociate expressions.
1586 OurFPM.add(createReassociatePass());
1587 // Eliminate Common SubExpressions.
1588 OurFPM.add(createGVNPass());
1589 // Simplify the control flow graph (deleting unreachable blocks, etc).
1590 OurFPM.add(createCFGSimplificationPass());
1592 OurFPM.doInitialization();
1594 // Set the global so the code gen can use this.
1597 // Run the main "interpreter loop" now.
1602 // Print out all of the generated code.
1608 `Next: Extending the language: user-defined operators <LangImpl6.html>`_