1 ========================================
2 Kaleidoscope: Code generation to LLVM IR
3 ========================================
11 Welcome to Chapter 3 of the "`Implementing a language with
12 LLVM <index.html>`_" tutorial. This chapter shows you how to transform
13 the `Abstract Syntax Tree <LangImpl2.html>`_, built in Chapter 2, into
14 LLVM IR. This will teach you a little bit about how LLVM does things, as
15 well as demonstrate how easy it is to use. It's much more work to build
16 a lexer and parser than it is to generate LLVM IR code. :)
18 **Please note**: the code in this chapter and later require LLVM 2.2 or
19 later. LLVM 2.1 and before will not work with it. Also note that you
20 need to use a version of this tutorial that matches your LLVM release:
21 If you are using an official LLVM release, use the version of the
22 documentation included with your release or on the `llvm.org releases
23 page <http://llvm.org/releases/>`_.
28 In order to generate LLVM IR, we want some simple setup to get started.
29 First we define virtual code generation (codegen) methods in each AST
34 /// ExprAST - Base class for all expression nodes.
38 virtual Value *Codegen() = 0;
41 /// NumberExprAST - Expression class for numeric literals like "1.0".
42 class NumberExprAST : public ExprAST {
45 NumberExprAST(double val) : Val(val) {}
46 virtual Value *Codegen();
50 The Codegen() method says to emit IR for that AST node along with all
51 the things it depends on, and they all return an LLVM Value object.
52 "Value" is the class used to represent a "`Static Single Assignment
53 (SSA) <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_
54 register" or "SSA value" in LLVM. The most distinct aspect of SSA values
55 is that their value is computed as the related instruction executes, and
56 it does not get a new value until (and if) the instruction re-executes.
57 In other words, there is no way to "change" an SSA value. For more
58 information, please read up on `Static Single
59 Assignment <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_
60 - the concepts are really quite natural once you grok them.
62 Note that instead of adding virtual methods to the ExprAST class
63 hierarchy, it could also make sense to use a `visitor
64 pattern <http://en.wikipedia.org/wiki/Visitor_pattern>`_ or some other
65 way to model this. Again, this tutorial won't dwell on good software
66 engineering practices: for our purposes, adding a virtual method is
69 The second thing we want is an "Error" method like we used for the
70 parser, which will be used to report errors found during code generation
71 (for example, use of an undeclared parameter):
75 Value *ErrorV(const char *Str) { Error(Str); return 0; }
77 static Module *TheModule;
78 static IRBuilder<> Builder(getGlobalContext());
79 static std::map<std::string, Value*> NamedValues;
81 The static variables will be used during code generation. ``TheModule``
82 is the LLVM construct that contains all of the functions and global
83 variables in a chunk of code. In many ways, it is the top-level
84 structure that the LLVM IR uses to contain code.
86 The ``Builder`` object is a helper object that makes it easy to generate
87 LLVM instructions. Instances of the
88 ```IRBuilder`` <http://llvm.org/doxygen/IRBuilder_8h-source.html>`_
89 class template keep track of the current place to insert instructions
90 and has methods to create new instructions.
92 The ``NamedValues`` map keeps track of which values are defined in the
93 current scope and what their LLVM representation is. (In other words, it
94 is a symbol table for the code). In this form of Kaleidoscope, the only
95 things that can be referenced are function parameters. As such, function
96 parameters will be in this map when generating code for their function
99 With these basics in place, we can start talking about how to generate
100 code for each expression. Note that this assumes that the ``Builder``
101 has been set up to generate code *into* something. For now, we'll assume
102 that this has already been done, and we'll just use it to emit code.
104 Expression Code Generation
105 ==========================
107 Generating LLVM code for expression nodes is very straightforward: less
108 than 45 lines of commented code for all four of our expression nodes.
109 First we'll do numeric literals:
113 Value *NumberExprAST::Codegen() {
114 return ConstantFP::get(getGlobalContext(), APFloat(Val));
117 In the LLVM IR, numeric constants are represented with the
118 ``ConstantFP`` class, which holds the numeric value in an ``APFloat``
119 internally (``APFloat`` has the capability of holding floating point
120 constants of Arbitrary Precision). This code basically just creates
121 and returns a ``ConstantFP``. Note that in the LLVM IR that constants
122 are all uniqued together and shared. For this reason, the API uses the
123 "foo::get(...)" idiom instead of "new foo(..)" or "foo::Create(..)".
127 Value *VariableExprAST::Codegen() {
128 // Look this variable up in the function.
129 Value *V = NamedValues[Name];
130 return V ? V : ErrorV("Unknown variable name");
133 References to variables are also quite simple using LLVM. In the simple
134 version of Kaleidoscope, we assume that the variable has already been
135 emitted somewhere and its value is available. In practice, the only
136 values that can be in the ``NamedValues`` map are function arguments.
137 This code simply checks to see that the specified name is in the map (if
138 not, an unknown variable is being referenced) and returns the value for
139 it. In future chapters, we'll add support for `loop induction
140 variables <LangImpl5.html#for>`_ in the symbol table, and for `local
141 variables <LangImpl7.html#localvars>`_.
145 Value *BinaryExprAST::Codegen() {
146 Value *L = LHS->Codegen();
147 Value *R = RHS->Codegen();
148 if (L == 0 || R == 0) return 0;
151 case '+': return Builder.CreateFAdd(L, R, "addtmp");
152 case '-': return Builder.CreateFSub(L, R, "subtmp");
153 case '*': return Builder.CreateFMul(L, R, "multmp");
155 L = Builder.CreateFCmpULT(L, R, "cmptmp");
156 // Convert bool 0/1 to double 0.0 or 1.0
157 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
159 default: return ErrorV("invalid binary operator");
163 Binary operators start to get more interesting. The basic idea here is
164 that we recursively emit code for the left-hand side of the expression,
165 then the right-hand side, then we compute the result of the binary
166 expression. In this code, we do a simple switch on the opcode to create
167 the right LLVM instruction.
169 In the example above, the LLVM builder class is starting to show its
170 value. IRBuilder knows where to insert the newly created instruction,
171 all you have to do is specify what instruction to create (e.g. with
172 ``CreateFAdd``), which operands to use (``L`` and ``R`` here) and
173 optionally provide a name for the generated instruction.
175 One nice thing about LLVM is that the name is just a hint. For instance,
176 if the code above emits multiple "addtmp" variables, LLVM will
177 automatically provide each one with an increasing, unique numeric
178 suffix. Local value names for instructions are purely optional, but it
179 makes it much easier to read the IR dumps.
181 `LLVM instructions <../LangRef.html#instref>`_ are constrained by strict
182 rules: for example, the Left and Right operators of an `add
183 instruction <../LangRef.html#i_add>`_ must have the same type, and the
184 result type of the add must match the operand types. Because all values
185 in Kaleidoscope are doubles, this makes for very simple code for add,
188 On the other hand, LLVM specifies that the `fcmp
189 instruction <../LangRef.html#i_fcmp>`_ always returns an 'i1' value (a
190 one bit integer). The problem with this is that Kaleidoscope wants the
191 value to be a 0.0 or 1.0 value. In order to get these semantics, we
192 combine the fcmp instruction with a `uitofp
193 instruction <../LangRef.html#i_uitofp>`_. This instruction converts its
194 input integer into a floating point value by treating the input as an
195 unsigned value. In contrast, if we used the `sitofp
196 instruction <../LangRef.html#i_sitofp>`_, the Kaleidoscope '<' operator
197 would return 0.0 and -1.0, depending on the input value.
201 Value *CallExprAST::Codegen() {
202 // Look up the name in the global module table.
203 Function *CalleeF = TheModule->getFunction(Callee);
205 return ErrorV("Unknown function referenced");
207 // If argument mismatch error.
208 if (CalleeF->arg_size() != Args.size())
209 return ErrorV("Incorrect # arguments passed");
211 std::vector<Value*> ArgsV;
212 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
213 ArgsV.push_back(Args[i]->Codegen());
214 if (ArgsV.back() == 0) return 0;
217 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
220 Code generation for function calls is quite straightforward with LLVM.
221 The code above initially does a function name lookup in the LLVM
222 Module's symbol table. Recall that the LLVM Module is the container that
223 holds all of the functions we are JIT'ing. By giving each function the
224 same name as what the user specifies, we can use the LLVM symbol table
225 to resolve function names for us.
227 Once we have the function to call, we recursively codegen each argument
228 that is to be passed in, and create an LLVM `call
229 instruction <../LangRef.html#i_call>`_. Note that LLVM uses the native C
230 calling conventions by default, allowing these calls to also call into
231 standard library functions like "sin" and "cos", with no additional
234 This wraps up our handling of the four basic expressions that we have so
235 far in Kaleidoscope. Feel free to go in and add some more. For example,
236 by browsing the `LLVM language reference <../LangRef.html>`_ you'll find
237 several other interesting instructions that are really easy to plug into
240 Function Code Generation
241 ========================
243 Code generation for prototypes and functions must handle a number of
244 details, which make their code less beautiful than expression code
245 generation, but allows us to illustrate some important points. First,
246 lets talk about code generation for prototypes: they are used both for
247 function bodies and external function declarations. The code starts
252 Function *PrototypeAST::Codegen() {
253 // Make the function type: double(double,double) etc.
254 std::vector<Type*> Doubles(Args.size(),
255 Type::getDoubleTy(getGlobalContext()));
256 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
259 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
261 This code packs a lot of power into a few lines. Note first that this
262 function returns a "Function\*" instead of a "Value\*". Because a
263 "prototype" really talks about the external interface for a function
264 (not the value computed by an expression), it makes sense for it to
265 return the LLVM Function it corresponds to when codegen'd.
267 The call to ``FunctionType::get`` creates the ``FunctionType`` that
268 should be used for a given Prototype. Since all function arguments in
269 Kaleidoscope are of type double, the first line creates a vector of "N"
270 LLVM double types. It then uses the ``Functiontype::get`` method to
271 create a function type that takes "N" doubles as arguments, returns one
272 double as a result, and that is not vararg (the false parameter
273 indicates this). Note that Types in LLVM are uniqued just like Constants
274 are, so you don't "new" a type, you "get" it.
276 The final line above actually creates the function that the prototype
277 will correspond to. This indicates the type, linkage and name to use, as
278 well as which module to insert into. "`external
279 linkage <../LangRef.html#linkage>`_" means that the function may be
280 defined outside the current module and/or that it is callable by
281 functions outside the module. The Name passed in is the name the user
282 specified: since "``TheModule``" is specified, this name is registered
283 in "``TheModule``"s symbol table, which is used by the function call
288 // If F conflicted, there was already something named 'Name'. If it has a
289 // body, don't allow redefinition or reextern.
290 if (F->getName() != Name) {
291 // Delete the one we just made and get the existing one.
292 F->eraseFromParent();
293 F = TheModule->getFunction(Name);
295 The Module symbol table works just like the Function symbol table when
296 it comes to name conflicts: if a new function is created with a name
297 that was previously added to the symbol table, the new function will get
298 implicitly renamed when added to the Module. The code above exploits
299 this fact to determine if there was a previous definition of this
302 In Kaleidoscope, I choose to allow redefinitions of functions in two
303 cases: first, we want to allow 'extern'ing a function more than once, as
304 long as the prototypes for the externs match (since all arguments have
305 the same type, we just have to check that the number of arguments
306 match). Second, we want to allow 'extern'ing a function and then
307 defining a body for it. This is useful when defining mutually recursive
310 In order to implement this, the code above first checks to see if there
311 is a collision on the name of the function. If so, it deletes the
312 function we just created (by calling ``eraseFromParent``) and then
313 calling ``getFunction`` to get the existing function with the specified
314 name. Note that many APIs in LLVM have "erase" forms and "remove" forms.
315 The "remove" form unlinks the object from its parent (e.g. a Function
316 from a Module) and returns it. The "erase" form unlinks the object and
321 // If F already has a body, reject this.
323 ErrorF("redefinition of function");
327 // If F took a different number of args, reject.
328 if (F->arg_size() != Args.size()) {
329 ErrorF("redefinition of function with different # args");
334 In order to verify the logic above, we first check to see if the
335 pre-existing function is "empty". In this case, empty means that it has
336 no basic blocks in it, which means it has no body. If it has no body, it
337 is a forward declaration. Since we don't allow anything after a full
338 definition of the function, the code rejects this case. If the previous
339 reference to a function was an 'extern', we simply verify that the
340 number of arguments for that definition and this one match up. If not,
345 // Set names for all arguments.
347 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
349 AI->setName(Args[Idx]);
351 // Add arguments to variable symbol table.
352 NamedValues[Args[Idx]] = AI;
357 The last bit of code for prototypes loops over all of the arguments in
358 the function, setting the name of the LLVM Argument objects to match,
359 and registering the arguments in the ``NamedValues`` map for future use
360 by the ``VariableExprAST`` AST node. Once this is set up, it returns the
361 Function object to the caller. Note that we don't check for conflicting
362 argument names here (e.g. "extern foo(a b a)"). Doing so would be very
363 straight-forward with the mechanics we have already used above.
367 Function *FunctionAST::Codegen() {
370 Function *TheFunction = Proto->Codegen();
371 if (TheFunction == 0)
374 Code generation for function definitions starts out simply enough: we
375 just codegen the prototype (Proto) and verify that it is ok. We then
376 clear out the ``NamedValues`` map to make sure that there isn't anything
377 in it from the last function we compiled. Code generation of the
378 prototype ensures that there is an LLVM Function object that is ready to
383 // Create a new basic block to start insertion into.
384 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
385 Builder.SetInsertPoint(BB);
387 if (Value *RetVal = Body->Codegen()) {
389 Now we get to the point where the ``Builder`` is set up. The first line
390 creates a new `basic block <http://en.wikipedia.org/wiki/Basic_block>`_
391 (named "entry"), which is inserted into ``TheFunction``. The second line
392 then tells the builder that new instructions should be inserted into the
393 end of the new basic block. Basic blocks in LLVM are an important part
394 of functions that define the `Control Flow
395 Graph <http://en.wikipedia.org/wiki/Control_flow_graph>`_. Since we
396 don't have any control flow, our functions will only contain one block
397 at this point. We'll fix this in `Chapter 5 <LangImpl5.html>`_ :).
401 if (Value *RetVal = Body->Codegen()) {
402 // Finish off the function.
403 Builder.CreateRet(RetVal);
405 // Validate the generated code, checking for consistency.
406 verifyFunction(*TheFunction);
411 Once the insertion point is set up, we call the ``CodeGen()`` method for
412 the root expression of the function. If no error happens, this emits
413 code to compute the expression into the entry block and returns the
414 value that was computed. Assuming no error, we then create an LLVM `ret
415 instruction <../LangRef.html#i_ret>`_, which completes the function.
416 Once the function is built, we call ``verifyFunction``, which is
417 provided by LLVM. This function does a variety of consistency checks on
418 the generated code, to determine if our compiler is doing everything
419 right. Using this is important: it can catch a lot of bugs. Once the
420 function is finished and validated, we return it.
424 // Error reading body, remove function.
425 TheFunction->eraseFromParent();
429 The only piece left here is handling of the error case. For simplicity,
430 we handle this by merely deleting the function we produced with the
431 ``eraseFromParent`` method. This allows the user to redefine a function
432 that they incorrectly typed in before: if we didn't delete it, it would
433 live in the symbol table, with a body, preventing future redefinition.
435 This code does have a bug, though. Since the ``PrototypeAST::Codegen``
436 can return a previously defined forward declaration, our code can
437 actually delete a forward declaration. There are a number of ways to fix
438 this bug, see what you can come up with! Here is a testcase:
442 extern foo(a b); # ok, defines foo.
443 def foo(a b) c; # error, 'c' is invalid.
444 def bar() foo(1, 2); # error, unknown function "foo"
446 Driver Changes and Closing Thoughts
447 ===================================
449 For now, code generation to LLVM doesn't really get us much, except that
450 we can look at the pretty IR calls. The sample code inserts calls to
451 Codegen into the "``HandleDefinition``", "``HandleExtern``" etc
452 functions, and then dumps out the LLVM IR. This gives a nice way to look
453 at the LLVM IR for simple functions. For example:
458 Read top-level expression:
461 ret double 9.000000e+00
464 Note how the parser turns the top-level expression into anonymous
465 functions for us. This will be handy when we add `JIT
466 support <LangImpl4.html#jit>`_ in the next chapter. Also note that the
467 code is very literally transcribed, no optimizations are being performed
468 except simple constant folding done by IRBuilder. We will `add
469 optimizations <LangImpl4.html#trivialconstfold>`_ explicitly in the next
474 ready> def foo(a b) a*a + 2*a*b + b*b;
475 Read function definition:
476 define double @foo(double %a, double %b) {
478 %multmp = fmul double %a, %a
479 %multmp1 = fmul double 2.000000e+00, %a
480 %multmp2 = fmul double %multmp1, %b
481 %addtmp = fadd double %multmp, %multmp2
482 %multmp3 = fmul double %b, %b
483 %addtmp4 = fadd double %addtmp, %multmp3
487 This shows some simple arithmetic. Notice the striking similarity to the
488 LLVM builder calls that we use to create the instructions.
492 ready> def bar(a) foo(a, 4.0) + bar(31337);
493 Read function definition:
494 define double @bar(double %a) {
496 %calltmp = call double @foo(double %a, double 4.000000e+00)
497 %calltmp1 = call double @bar(double 3.133700e+04)
498 %addtmp = fadd double %calltmp, %calltmp1
502 This shows some function calls. Note that this function will take a long
503 time to execute if you call it. In the future we'll add conditional
504 control flow to actually make recursion useful :).
508 ready> extern cos(x);
510 declare double @cos(double)
513 Read top-level expression:
516 %calltmp = call double @cos(double 1.234000e+00)
520 This shows an extern for the libm "cos" function, and a call to it.
522 .. TODO:: Abandon Pygments' horrible `llvm` lexer. It just totally gives up
523 on highlighting this due to the first line.
528 ; ModuleID = 'my cool jit'
532 %addtmp = fadd double 4.000000e+00, 5.000000e+00
536 define double @foo(double %a, double %b) {
538 %multmp = fmul double %a, %a
539 %multmp1 = fmul double 2.000000e+00, %a
540 %multmp2 = fmul double %multmp1, %b
541 %addtmp = fadd double %multmp, %multmp2
542 %multmp3 = fmul double %b, %b
543 %addtmp4 = fadd double %addtmp, %multmp3
547 define double @bar(double %a) {
549 %calltmp = call double @foo(double %a, double 4.000000e+00)
550 %calltmp1 = call double @bar(double 3.133700e+04)
551 %addtmp = fadd double %calltmp, %calltmp1
555 declare double @cos(double)
559 %calltmp = call double @cos(double 1.234000e+00)
563 When you quit the current demo, it dumps out the IR for the entire
564 module generated. Here you can see the big picture with all the
565 functions referencing each other.
567 This wraps up the third chapter of the Kaleidoscope tutorial. Up next,
568 we'll describe how to `add JIT codegen and optimizer
569 support <LangImpl4.html>`_ to this so we can actually start running
575 Here is the complete code listing for our running example, enhanced with
576 the LLVM code generator. Because this uses the LLVM libraries, we need
577 to link them in. To do this, we use the
578 `llvm-config <http://llvm.org/cmds/llvm-config.html>`_ tool to inform
579 our makefile/command line about which options to use:
584 clang++ -g -O3 toy.cpp `llvm-config --cppflags --ldflags --libs core` -o toy
593 // See example below.
595 #include "llvm/DerivedTypes.h"
596 #include "llvm/IRBuilder.h"
597 #include "llvm/LLVMContext.h"
598 #include "llvm/Module.h"
599 #include "llvm/Analysis/Verifier.h"
604 using namespace llvm;
606 //===----------------------------------------------------------------------===//
608 //===----------------------------------------------------------------------===//
610 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
611 // of these for known things.
616 tok_def = -2, tok_extern = -3,
619 tok_identifier = -4, tok_number = -5
622 static std::string IdentifierStr; // Filled in if tok_identifier
623 static double NumVal; // Filled in if tok_number
625 /// gettok - Return the next token from standard input.
626 static int gettok() {
627 static int LastChar = ' ';
629 // Skip any whitespace.
630 while (isspace(LastChar))
631 LastChar = getchar();
633 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
634 IdentifierStr = LastChar;
635 while (isalnum((LastChar = getchar())))
636 IdentifierStr += LastChar;
638 if (IdentifierStr == "def") return tok_def;
639 if (IdentifierStr == "extern") return tok_extern;
640 return tok_identifier;
643 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
647 LastChar = getchar();
648 } while (isdigit(LastChar) || LastChar == '.');
650 NumVal = strtod(NumStr.c_str(), 0);
654 if (LastChar == '#') {
655 // Comment until end of line.
656 do LastChar = getchar();
657 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
663 // Check for end of file. Don't eat the EOF.
667 // Otherwise, just return the character as its ascii value.
668 int ThisChar = LastChar;
669 LastChar = getchar();
673 //===----------------------------------------------------------------------===//
674 // Abstract Syntax Tree (aka Parse Tree)
675 //===----------------------------------------------------------------------===//
677 /// ExprAST - Base class for all expression nodes.
680 virtual ~ExprAST() {}
681 virtual Value *Codegen() = 0;
684 /// NumberExprAST - Expression class for numeric literals like "1.0".
685 class NumberExprAST : public ExprAST {
688 NumberExprAST(double val) : Val(val) {}
689 virtual Value *Codegen();
692 /// VariableExprAST - Expression class for referencing a variable, like "a".
693 class VariableExprAST : public ExprAST {
696 VariableExprAST(const std::string &name) : Name(name) {}
697 virtual Value *Codegen();
700 /// BinaryExprAST - Expression class for a binary operator.
701 class BinaryExprAST : public ExprAST {
705 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
706 : Op(op), LHS(lhs), RHS(rhs) {}
707 virtual Value *Codegen();
710 /// CallExprAST - Expression class for function calls.
711 class CallExprAST : public ExprAST {
713 std::vector<ExprAST*> Args;
715 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
716 : Callee(callee), Args(args) {}
717 virtual Value *Codegen();
720 /// PrototypeAST - This class represents the "prototype" for a function,
721 /// which captures its name, and its argument names (thus implicitly the number
722 /// of arguments the function takes).
725 std::vector<std::string> Args;
727 PrototypeAST(const std::string &name, const std::vector<std::string> &args)
728 : Name(name), Args(args) {}
733 /// FunctionAST - This class represents a function definition itself.
738 FunctionAST(PrototypeAST *proto, ExprAST *body)
739 : Proto(proto), Body(body) {}
744 //===----------------------------------------------------------------------===//
746 //===----------------------------------------------------------------------===//
748 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
749 /// token the parser is looking at. getNextToken reads another token from the
750 /// lexer and updates CurTok with its results.
752 static int getNextToken() {
753 return CurTok = gettok();
756 /// BinopPrecedence - This holds the precedence for each binary operator that is
758 static std::map<char, int> BinopPrecedence;
760 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
761 static int GetTokPrecedence() {
762 if (!isascii(CurTok))
765 // Make sure it's a declared binop.
766 int TokPrec = BinopPrecedence[CurTok];
767 if (TokPrec <= 0) return -1;
771 /// Error* - These are little helper functions for error handling.
772 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
773 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
774 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
776 static ExprAST *ParseExpression();
780 /// ::= identifier '(' expression* ')'
781 static ExprAST *ParseIdentifierExpr() {
782 std::string IdName = IdentifierStr;
784 getNextToken(); // eat identifier.
786 if (CurTok != '(') // Simple variable ref.
787 return new VariableExprAST(IdName);
790 getNextToken(); // eat (
791 std::vector<ExprAST*> Args;
794 ExprAST *Arg = ParseExpression();
798 if (CurTok == ')') break;
801 return Error("Expected ')' or ',' in argument list");
809 return new CallExprAST(IdName, Args);
812 /// numberexpr ::= number
813 static ExprAST *ParseNumberExpr() {
814 ExprAST *Result = new NumberExprAST(NumVal);
815 getNextToken(); // consume the number
819 /// parenexpr ::= '(' expression ')'
820 static ExprAST *ParseParenExpr() {
821 getNextToken(); // eat (.
822 ExprAST *V = ParseExpression();
826 return Error("expected ')'");
827 getNextToken(); // eat ).
832 /// ::= identifierexpr
835 static ExprAST *ParsePrimary() {
837 default: return Error("unknown token when expecting an expression");
838 case tok_identifier: return ParseIdentifierExpr();
839 case tok_number: return ParseNumberExpr();
840 case '(': return ParseParenExpr();
845 /// ::= ('+' primary)*
846 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
847 // If this is a binop, find its precedence.
849 int TokPrec = GetTokPrecedence();
851 // If this is a binop that binds at least as tightly as the current binop,
852 // consume it, otherwise we are done.
853 if (TokPrec < ExprPrec)
856 // Okay, we know this is a binop.
858 getNextToken(); // eat binop
860 // Parse the primary expression after the binary operator.
861 ExprAST *RHS = ParsePrimary();
864 // If BinOp binds less tightly with RHS than the operator after RHS, let
865 // the pending operator take RHS as its LHS.
866 int NextPrec = GetTokPrecedence();
867 if (TokPrec < NextPrec) {
868 RHS = ParseBinOpRHS(TokPrec+1, RHS);
869 if (RHS == 0) return 0;
873 LHS = new BinaryExprAST(BinOp, LHS, RHS);
878 /// ::= primary binoprhs
880 static ExprAST *ParseExpression() {
881 ExprAST *LHS = ParsePrimary();
884 return ParseBinOpRHS(0, LHS);
888 /// ::= id '(' id* ')'
889 static PrototypeAST *ParsePrototype() {
890 if (CurTok != tok_identifier)
891 return ErrorP("Expected function name in prototype");
893 std::string FnName = IdentifierStr;
897 return ErrorP("Expected '(' in prototype");
899 std::vector<std::string> ArgNames;
900 while (getNextToken() == tok_identifier)
901 ArgNames.push_back(IdentifierStr);
903 return ErrorP("Expected ')' in prototype");
906 getNextToken(); // eat ')'.
908 return new PrototypeAST(FnName, ArgNames);
911 /// definition ::= 'def' prototype expression
912 static FunctionAST *ParseDefinition() {
913 getNextToken(); // eat def.
914 PrototypeAST *Proto = ParsePrototype();
915 if (Proto == 0) return 0;
917 if (ExprAST *E = ParseExpression())
918 return new FunctionAST(Proto, E);
922 /// toplevelexpr ::= expression
923 static FunctionAST *ParseTopLevelExpr() {
924 if (ExprAST *E = ParseExpression()) {
925 // Make an anonymous proto.
926 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
927 return new FunctionAST(Proto, E);
932 /// external ::= 'extern' prototype
933 static PrototypeAST *ParseExtern() {
934 getNextToken(); // eat extern.
935 return ParsePrototype();
938 //===----------------------------------------------------------------------===//
940 //===----------------------------------------------------------------------===//
942 static Module *TheModule;
943 static IRBuilder<> Builder(getGlobalContext());
944 static std::map<std::string, Value*> NamedValues;
946 Value *ErrorV(const char *Str) { Error(Str); return 0; }
948 Value *NumberExprAST::Codegen() {
949 return ConstantFP::get(getGlobalContext(), APFloat(Val));
952 Value *VariableExprAST::Codegen() {
953 // Look this variable up in the function.
954 Value *V = NamedValues[Name];
955 return V ? V : ErrorV("Unknown variable name");
958 Value *BinaryExprAST::Codegen() {
959 Value *L = LHS->Codegen();
960 Value *R = RHS->Codegen();
961 if (L == 0 || R == 0) return 0;
964 case '+': return Builder.CreateFAdd(L, R, "addtmp");
965 case '-': return Builder.CreateFSub(L, R, "subtmp");
966 case '*': return Builder.CreateFMul(L, R, "multmp");
968 L = Builder.CreateFCmpULT(L, R, "cmptmp");
969 // Convert bool 0/1 to double 0.0 or 1.0
970 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
972 default: return ErrorV("invalid binary operator");
976 Value *CallExprAST::Codegen() {
977 // Look up the name in the global module table.
978 Function *CalleeF = TheModule->getFunction(Callee);
980 return ErrorV("Unknown function referenced");
982 // If argument mismatch error.
983 if (CalleeF->arg_size() != Args.size())
984 return ErrorV("Incorrect # arguments passed");
986 std::vector<Value*> ArgsV;
987 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
988 ArgsV.push_back(Args[i]->Codegen());
989 if (ArgsV.back() == 0) return 0;
992 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
995 Function *PrototypeAST::Codegen() {
996 // Make the function type: double(double,double) etc.
997 std::vector<Type*> Doubles(Args.size(),
998 Type::getDoubleTy(getGlobalContext()));
999 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1002 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1004 // If F conflicted, there was already something named 'Name'. If it has a
1005 // body, don't allow redefinition or reextern.
1006 if (F->getName() != Name) {
1007 // Delete the one we just made and get the existing one.
1008 F->eraseFromParent();
1009 F = TheModule->getFunction(Name);
1011 // If F already has a body, reject this.
1013 ErrorF("redefinition of function");
1017 // If F took a different number of args, reject.
1018 if (F->arg_size() != Args.size()) {
1019 ErrorF("redefinition of function with different # args");
1024 // Set names for all arguments.
1026 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1028 AI->setName(Args[Idx]);
1030 // Add arguments to variable symbol table.
1031 NamedValues[Args[Idx]] = AI;
1037 Function *FunctionAST::Codegen() {
1038 NamedValues.clear();
1040 Function *TheFunction = Proto->Codegen();
1041 if (TheFunction == 0)
1044 // Create a new basic block to start insertion into.
1045 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1046 Builder.SetInsertPoint(BB);
1048 if (Value *RetVal = Body->Codegen()) {
1049 // Finish off the function.
1050 Builder.CreateRet(RetVal);
1052 // Validate the generated code, checking for consistency.
1053 verifyFunction(*TheFunction);
1058 // Error reading body, remove function.
1059 TheFunction->eraseFromParent();
1063 //===----------------------------------------------------------------------===//
1064 // Top-Level parsing and JIT Driver
1065 //===----------------------------------------------------------------------===//
1067 static void HandleDefinition() {
1068 if (FunctionAST *F = ParseDefinition()) {
1069 if (Function *LF = F->Codegen()) {
1070 fprintf(stderr, "Read function definition:");
1074 // Skip token for error recovery.
1079 static void HandleExtern() {
1080 if (PrototypeAST *P = ParseExtern()) {
1081 if (Function *F = P->Codegen()) {
1082 fprintf(stderr, "Read extern: ");
1086 // Skip token for error recovery.
1091 static void HandleTopLevelExpression() {
1092 // Evaluate a top-level expression into an anonymous function.
1093 if (FunctionAST *F = ParseTopLevelExpr()) {
1094 if (Function *LF = F->Codegen()) {
1095 fprintf(stderr, "Read top-level expression:");
1099 // Skip token for error recovery.
1104 /// top ::= definition | external | expression | ';'
1105 static void MainLoop() {
1107 fprintf(stderr, "ready> ");
1109 case tok_eof: return;
1110 case ';': getNextToken(); break; // ignore top-level semicolons.
1111 case tok_def: HandleDefinition(); break;
1112 case tok_extern: HandleExtern(); break;
1113 default: HandleTopLevelExpression(); break;
1118 //===----------------------------------------------------------------------===//
1119 // "Library" functions that can be "extern'd" from user code.
1120 //===----------------------------------------------------------------------===//
1122 /// putchard - putchar that takes a double and returns 0.
1124 double putchard(double X) {
1129 //===----------------------------------------------------------------------===//
1130 // Main driver code.
1131 //===----------------------------------------------------------------------===//
1134 LLVMContext &Context = getGlobalContext();
1136 // Install standard binary operators.
1137 // 1 is lowest precedence.
1138 BinopPrecedence['<'] = 10;
1139 BinopPrecedence['+'] = 20;
1140 BinopPrecedence['-'] = 20;
1141 BinopPrecedence['*'] = 40; // highest.
1143 // Prime the first token.
1144 fprintf(stderr, "ready> ");
1147 // Make the module, which holds all the code.
1148 TheModule = new Module("my cool jit", Context);
1150 // Run the main "interpreter loop" now.
1153 // Print out all of the generated code.
1159 `Next: Adding JIT and Optimizer Support <LangImpl4.html>`_