1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
6 <title>Kaleidoscope: Implementing code generation to LLVM IR</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: Code generation to LLVM IR</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 3 Introduction</a></div>
22 <!-- *********************************************************************** -->
24 <div class="doc_text">
26 <p>Welcome to part 3 of the "<a href="index.html">Implementing a language with
27 LLVM</a>" tutorial. This chapter shows you how to transform the <a
28 href="LangImpl2.html">Abstract Syntax Tree built in Chapter 2</a> into LLVM IR.
29 This will teach you a little bit about how LLVM does things, as well as
30 demonstrate how easy it is to use. It's much more work to build a lexer and
31 parser than it is to generate LLVM IR code.
36 <!-- *********************************************************************** -->
37 <div class="doc_section"><a name="basics">Code Generation setup</a></div>
38 <!-- *********************************************************************** -->
40 <div class="doc_text">
43 In order to generate LLVM IR, we want some simple setup to get started. First,
44 we define virtual codegen methods in each AST class:</p>
46 <div class="doc_code">
48 /// ExprAST - Base class for all expression nodes.
52 virtual Value *Codegen() = 0;
55 /// NumberExprAST - Expression class for numeric literals like "1.0".
56 class NumberExprAST : public ExprAST {
59 explicit NumberExprAST(double val) : Val(val) {}
60 virtual Value *Codegen();
66 <p>The Codegen() method says to emit IR for that AST node and all things it
67 depends on, and they all return an LLVM Value object.
68 "Value" is the class used to represent a "<a
69 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single
70 Assignment (SSA)</a> register" or "SSA value" in LLVM. The most distinct aspect
71 of SSA values is that their value is computed as the related instruction
72 executes, and it does not get a new value until (and if) the instruction
73 re-executes. In order words, there is no way to "change" an SSA value. For
74 more information, please read up on <a
75 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single
76 Assignment</a> - the concepts are really quite natural once you grok them.</p>
79 second thing we want is an "Error" method like we used for parser, which will
80 be used to report errors found during code generation (for example, use of an
81 undeclared parameter):</p>
83 <div class="doc_code">
85 Value *ErrorV(const char *Str) { Error(Str); return 0; }
87 static Module *TheModule;
88 static LLVMBuilder Builder;
89 static std::map<std::string, Value*> NamedValues;
93 <p>The static variables will be used during code generation. <tt>TheModule</tt>
94 is the LLVM construct that contains all of the functions and global variables in
95 a chunk of code. In many ways, it is the top-level structure that the LLVM IR
96 uses to contain code.</p>
98 <p>The <tt>Builder</tt> object is a helper object that makes it easy to generate
99 LLVM instructions. The <tt>Builder</tt> keeps track of the current place to
100 insert instructions and has methods to create new instructions.</p>
102 <p>The <tt>NamedValues</tt> map keeps track of which values are defined in the
103 current scope and what their LLVM representation is. In this form of
104 Kaleidoscope, the only things that can be referenced are function parameters.
105 As such, function parameters will be in this map when generating code for their
109 With these basics in place, we can start talking about how to generate code for
110 each expression. Note that this assumes that the <tt>Builder</tt> has been set
111 up to generate code <em>into</em> something. For now, we'll assume that this
112 has already been done, and we'll just use it to emit code.
117 <!-- *********************************************************************** -->
118 <div class="doc_section"><a name="exprs">Expression Code Generation</a></div>
119 <!-- *********************************************************************** -->
121 <div class="doc_text">
123 <p>Generating LLVM code for expression nodes is very straight-forward: less
124 than 45 lines of commented code for all four of our expression nodes. First,
125 we'll do numeric literals:</p>
127 <div class="doc_code">
129 Value *NumberExprAST::Codegen() {
130 return ConstantFP::get(Type::DoubleTy, APFloat(Val));
135 <p>In the LLVM IR, numeric constants are represented with the
136 <tt>ConstantFP</tt> class, which holds the numeric value in an <tt>APFloat</tt>
137 internally (<tt>APFloat</tt> has the capability of holding floating point
138 constants of <em>A</em>rbitrary <em>P</em>recision). This code basically just
139 creates and returns a <tt>ConstantFP</tt>. Note that in the LLVM IR
140 that constants are all uniqued together and shared. For this reason, the API
141 uses "the foo::get(..)" idiom instead of "new foo(..)" or "foo::create(..).</p>
143 <div class="doc_code">
145 Value *VariableExprAST::Codegen() {
146 // Look this variable up in the function.
147 Value *V = NamedValues[Name];
148 return V ? V : ErrorV("Unknown variable name");
153 <p>References to variables is also quite simple here. In the simple version
154 of Kaleidoscope, we assume that the variable has already been emited somewhere
155 and its value is available. In practice, the only values that can be in the
156 <tt>NamedValues</tt> map are function arguments. This
157 code simply checks to see that the specified name is in the map (if not, an
158 unknown variable is being referenced) and returns the value for it.</p>
160 <div class="doc_code">
162 Value *BinaryExprAST::Codegen() {
163 Value *L = LHS->Codegen();
164 Value *R = RHS->Codegen();
165 if (L == 0 || R == 0) return 0;
168 case '+': return Builder.CreateAdd(L, R, "addtmp");
169 case '-': return Builder.CreateSub(L, R, "subtmp");
170 case '*': return Builder.CreateMul(L, R, "multmp");
172 L = Builder.CreateFCmpULT(L, R, "multmp");
173 // Convert bool 0/1 to double 0.0 or 1.0
174 return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
175 default: return ErrorV("invalid binary operator");
181 <p>Binary operators start to get more interesting. The basic idea here is that
182 we recursively emit code for the left-hand side of the expression, then the
183 right-hand side, then we compute the result of the binary expression. In this
184 code, we do a simple switch on the opcode to create the right LLVM instruction.
187 <p>In this example, the LLVM builder class is starting to show its value.
188 Because it knows where to insert the newly created instruction, you just have to
189 specificy what instruction to create (e.g. with <tt>CreateAdd</tt>), which
190 operands to use (<tt>L</tt> and <tt>R</tt> here) and optionally provide a name
191 for the generated instruction. One nice thing about LLVM is that the name is
192 just a hint: if there are multiple additions in a single function, the first
193 will be named "addtmp" and the second will be "autorenamed" by adding a suffix,
194 giving it a name like "addtmp42". Local value names for instructions are purely
195 optional, but it makes it much easier to read the IR dumps.</p>
197 <p><a href="../LangRef.html#instref">LLVM instructions</a> are constrained to
198 have very strict type properties: for example, the Left and Right operators of
199 an <a href="../LangRef.html#i_add">add instruction</a> have to have the same
200 type, and that the result of the add matches the operands. Because all values
201 in Kaleidoscope are doubles, this makes for very simple code for add, sub and
204 <p>On the other hand, LLVM specifies that the <a
205 href="../LangRef.html#i_fcmp">fcmp instruction</a> always returns an 'i1' value
206 (a one bit integer). However, Kaleidoscope wants the value to be a 0.0 or 1.0
207 value. In order to get these semantics, we combine the fcmp instruction with
208 a <a href="../LangRef.html#i_uitofp">uitofp instruction</a>. This instruction
209 converts its input integer into a floating point value by treating the input
210 as an unsigned value. In contrast, if we used the <a
211 href="../LangRef.html#i_sitofp">sitofp instruction</a>, the Kaleidoscope '<'
212 operator would return 0.0 and -1.0, depending on the input value.</p>
214 <div class="doc_code">
216 Value *CallExprAST::Codegen() {
217 // Look up the name in the global module table.
218 Function *CalleeF = TheModule->getFunction(Callee);
220 return ErrorV("Unknown function referenced");
222 // If argument mismatch error.
223 if (CalleeF->arg_size() != Args.size())
224 return ErrorV("Incorrect # arguments passed");
226 std::vector<Value*> ArgsV;
227 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
228 ArgsV.push_back(Args[i]->Codegen());
229 if (ArgsV.back() == 0) return 0;
232 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
237 <p>Code generation for function calls is quite straight-forward with LLVM. The
238 code above first looks the name of the function up in the LLVM Module's symbol
239 table. Recall that the LLVM Module is the container that holds all of the
240 functions we are JIT'ing. By giving each function the same name as what the
241 user specifies, we can use the LLVM symbol table to resolve function names for
244 <p>Once we have the function to call, we recursively codegen each argument that
245 is to be passed in, and create an LLVM <a href="../LangRef.html#i_call">call
246 instruction</a>. Note that LLVM uses the native C calling conventions by
247 default, allowing these calls to call into standard library functions like
248 "sin" and "cos" with no additional effort.</p>
250 <p>This wraps up our handling of the four basic expressions that we have so far
251 in Kaleidoscope. Feel free to go in and add some more. For example, by
252 browsing the <a href="../LangRef.html">LLVM language reference</a> you'll find
253 several other interesting instructions that are really easy to plug into our
258 <!-- *********************************************************************** -->
259 <div class="doc_section"><a name="funcs">Function Code Generation</a></div>
260 <!-- *********************************************************************** -->
262 <div class="doc_text">
264 <p>Code generation for prototypes and functions has to handle a number of
265 details, which make their code less beautiful and elegant than expression code
266 generation, but they illustrate some important points. First, lets talk about
267 code generation for prototypes: this is used both for function bodies as well
268 as external function declarations. The code starts with:</p>
270 <div class="doc_code">
272 Function *PrototypeAST::Codegen() {
273 // Make the function type: double(double,double) etc.
274 std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
275 FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
277 Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
281 <p>This code packs a lot of power into a few lines. The first step is to create
282 the <tt>FunctionType</tt> that should be used for a given Prototype. Since all
283 function arguments in Kaleidoscope are of type double, the first line creates
284 a vector of "N" LLVM Double types. It then uses the <tt>FunctionType::get</tt>
285 method to create a function type that takes "N" doubles as arguments, returns
286 one double as a result, and that is not vararg (the false parameter indicates
287 this). Note that Types in LLVM are uniqued just like Constants are, so you
288 don't "new" a type, you "get" it.</p>
290 <p>The final line above actually creates the function that the prototype will
291 correspond to. This indicates which type, linkage, and name to use, and which
292 module to insert into. "<a href="LangRef.html#linkage">external linkage</a>"
293 means that the function may be defined outside the current module and/or that it
294 is callable by functions outside the module. The Name passed in is the name the
295 user specified: since "<tt>TheModule</tt>" is specified, this name is registered
296 in "<tt>TheModule</tt>"s symbol table, which is used by the function call code
299 <div class="doc_code">
301 // If F conflicted, there was already something named 'Name'. If it has a
302 // body, don't allow redefinition or reextern.
303 if (F->getName() != Name) {
304 // Delete the one we just made and get the existing one.
305 F->eraseFromParent();
306 F = TheModule->getFunction(Name);
310 <p>The Module symbol table works just like the Function symbol table when it
311 comes to name conflicts: if a new function is created with a name was previously
312 added to the symbol table, it will get implicitly renamed when added to the
313 Module. The code above exploits this fact to tell if there was a previous
314 definition of this function.</p>
316 <p>In Kaleidoscope, I choose to allow redefinitions of functions in two cases:
317 first, we want to allow 'extern'ing a function more than once, so long as the
318 prototypes for the externs match (since all arguments have the same type, we
319 just have to check that the number of arguments match). Second, we want to
320 allow 'extern'ing a function and then definining a body for it. This is useful
321 when defining mutually recursive functions.</p>
323 <p>In order to implement this, the code above first checks to see if there is
324 a collision on the name of the function. If so, it deletes the function we just
325 created (by calling <tt>eraseFromParent</tt>) and then calling
326 <tt>getFunction</tt> to get the existing function with the specified name. Note
327 that many APIs in LLVM have "erase" forms and "remove" forms. The "remove" form
328 unlinks the object from its parent (e.g. a Function from a Module) and returns
329 it. The "erase" form unlinks the object and then deletes it.</p>
331 <div class="doc_code">
333 // If F already has a body, reject this.
334 if (!F->empty()) {
335 ErrorF("redefinition of function");
339 // If F took a different number of args, reject.
340 if (F->arg_size() != Args.size()) {
341 ErrorF("redefinition of function with different # args");
348 <p>In order to verify the logic above, we first check to see if the preexisting
349 function is "empty". In this case, empty means that it has no basic blocks in
350 it, which means it has no body. If it has no body, this means its a forward
351 declaration. Since we don't allow anything after a full definition of the
352 function, the code rejects this case. If the previous reference to a function
353 was an 'extern', we simply verify that the number of arguments for that
354 definition and this one match up. If not, we emit an error.</p>
356 <div class="doc_code">
358 // Set names for all arguments.
360 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
362 AI->setName(Args[Idx]);
364 // Add arguments to variable symbol table.
365 NamedValues[Args[Idx]] = AI;
372 <p>The last bit of code for prototypes loops over all of the arguments in the
373 function, setting the name of the LLVM Argument objects to match and registering
374 the arguments in the <tt>NamedValues</tt> map for future use by the
375 <tt>VariableExprAST</tt> AST node. Once this is set up, it returns the Function
376 object to the caller. Note that we don't check for conflicting
377 argument names here (e.g. "extern foo(a b a)"). Doing so would be very
378 straight-forward.</p>
380 <div class="doc_code">
382 Function *FunctionAST::Codegen() {
385 Function *TheFunction = Proto->Codegen();
386 if (TheFunction == 0)
391 <p>Code generation for function definitions starts out simply enough: first we
392 codegen the prototype and verify that it is ok. We also clear out the
393 <tt>NamedValues</tt> map to make sure that there isn't anything in it from the
394 last function we compiled.</p>
396 <div class="doc_code">
398 // Create a new basic block to start insertion into.
399 BasicBlock *BB = new BasicBlock("entry", TheFunction);
400 Builder.SetInsertPoint(BB);
402 if (Value *RetVal = Body->Codegen()) {
403 // Finish off the function.
404 Builder.CreateRet(RetVal);
410 <p>Now we get to the point where the <tt>Builder</tt> is set up. The first
411 line creates a new <a href="http://en.wikipedia.org/wiki/Basic_block">basic
412 block</a> (named "entry"), which is inserted into <tt>TheFunction</tt>. The
413 second line then tells the builder that new instructions should be inserted into
414 the end of the new basic block. Basic blocks in LLVM are an important part
415 of functions that define the <a
416 href="http://en.wikipedia.org/wiki/Control_flow_graph">Control Flow Graph</a>.
417 Since we don't have any control flow, our functions will only contain one
418 block so far. We'll fix this in a future installment :).</p>
420 <p>Once the insertion point is set up, we call the <tt>CodeGen()</tt> method for
421 the root expression of the function. If no error happens, this emits code to
422 compute the expression into the entry block and returns the value that was
423 computed. Assuming no error, we then create an LLVM <a
424 href="../LangRef.html#i_ret">ret instruction</a>. This completes the function,
425 which is then returned.</p>
427 <div class="doc_code">
429 // Error reading body, remove function.
430 TheFunction->eraseFromParent();
436 <p>The only piece left here is handling of the error case. For simplicity, we
437 simply handle this by deleting the function we produced with the
438 <tt>eraseFromParent</tt> method. This allows the user to redefine a function
439 that they incorrectly typed in before: if we didn't delete it, it would live in
440 the symbol table, with a body, preventing future redefinition.</p>
442 <p>This code does have a bug though. Since the <tt>PrototypeAST::Codegen</tt>
443 can return a previously defined forward declaration, this can actually delete
444 a forward declaration. There are a number of ways to fix this bug, see what you
445 can come up with! Here is a testcase:</p>
447 <div class="doc_code">
449 extern foo(a b); # ok, defines foo.
450 def foo(a b) c; # error, 'c' is invalid.
451 def bar() foo(1, 2); # error, unknown function "foo"
457 <!-- *********************************************************************** -->
458 <div class="doc_section"><a name="driver">Driver Changes and
459 Closing Thoughts</a></div>
460 <!-- *********************************************************************** -->
462 <div class="doc_text">
465 For now, code generation to LLVM doesn't really get us much, except that we can
466 look at the pretty IR calls. The sample code inserts calls to Codegen into the
467 "<tt>HandleDefinition</tt>", "<tt>HandleExtern</tt>" etc functions, and then
468 dumps out the LLVM IR. This gives a nice way to look at the LLVM IR for simple
469 functions. For example:
472 <div class="doc_code">
475 ready> Read top-level expression:
476 define double @""() {
478 %addtmp = add double 4.000000e+00, 5.000000e+00
484 <p>Note how the parser turns the top-level expression into anonymous functions
485 for us. This will be handy when we add JIT support in the next chapter. Also
486 note that the code is very literally transcribed, no optimizations are being
487 performed. We will add optimizations explicitly in the next chapter.</p>
489 <div class="doc_code">
491 ready> <b>def foo(a b) a*a + 2*a*b + b*b;</b>
492 ready> Read function definition:
493 define double @foo(double %a, double %b) {
495 %multmp = mul double %a, %a
496 %multmp1 = mul double 2.000000e+00, %a
497 %multmp2 = mul double %multmp1, %b
498 %addtmp = add double %multmp, %multmp2
499 %multmp3 = mul double %b, %b
500 %addtmp4 = add double %addtmp, %multmp3
506 <p>This shows some simple arithmetic. Notice the striking similarity to the
507 LLVM builder calls that we use to create the instructions.</p>
509 <div class="doc_code">
511 ready> <b>def bar(a) foo(a, 4.0) + bar(31337);</b>
512 ready> Read function definition:
513 define double @bar(double %a) {
515 %calltmp = call double @foo( double %a, double 4.000000e+00 )
516 %calltmp1 = call double @bar( double 3.133700e+04 )
517 %addtmp = add double %calltmp, %calltmp1
523 <p>This shows some function calls. Note that the runtime of this function might
524 be fairly high. In the future we'll add conditional control flow to make
525 recursion actually be useful :).</p>
527 <div class="doc_code">
529 ready> <b>extern cos(x);</b>
530 ready> Read extern:
531 declare double @cos(double)
533 ready> <b>cos(1.234);</b>
534 ready> Read top-level expression:
535 define double @""() {
537 %calltmp = call double @cos( double 1.234000e+00 )
543 <p>This shows an extern for the libm "cos" function, and a call to it.</p>
546 <div class="doc_code">
549 ; ModuleID = 'my cool jit'
551 define double @""() {
553 %addtmp = add double 4.000000e+00, 5.000000e+00
557 define double @foo(double %a, double %b) {
559 %multmp = mul double %a, %a
560 %multmp1 = mul double 2.000000e+00, %a
561 %multmp2 = mul double %multmp1, %b
562 %addtmp = add double %multmp, %multmp2
563 %multmp3 = mul double %b, %b
564 %addtmp4 = add double %addtmp, %multmp3
568 define double @bar(double %a) {
570 %calltmp = call double @foo( double %a, double 4.000000e+00 )
571 %calltmp1 = call double @bar( double 3.133700e+04 )
572 %addtmp = add double %calltmp, %calltmp1
576 declare double @cos(double)
578 define double @""() {
580 %calltmp = call double @cos( double 1.234000e+00 )
586 <p>When you quit the current demo, it dumps out the IR for the entire module
587 generated. Here you can see the big picture with all the functions referencing
590 <p>This wraps up this chapter of the Kaleidoscope tutorial. Up next we'll
591 describe how to <a href="LangImpl4.html">add JIT codegen and optimizer
592 support</a> to this so we can actually start running code!</p>
597 <!-- *********************************************************************** -->
598 <div class="doc_section"><a name="code">Full Code Listing</a></div>
599 <!-- *********************************************************************** -->
601 <div class="doc_text">
604 Here is the complete code listing for our running example, enhanced with the
605 LLVM code generator. Because this uses the LLVM libraries, we need to link
606 them in. To do this, we use the <a
607 href="http://llvm.org/cmds/llvm-config.html">llvm-config</a> tool to inform
608 our makefile/command line about which options to use:</p>
610 <div class="doc_code">
613 g++ -g toy.cpp `llvm-config --cppflags` `llvm-config --ldflags` \
614 `llvm-config --libs core` -o toy
620 <p>Here is the code:</p>
622 <div class="doc_code">
625 // See example below.
627 #include "llvm/DerivedTypes.h"
628 #include "llvm/Module.h"
629 #include "llvm/Support/LLVMBuilder.h"
630 #include <cstdio>
631 #include <string>
633 #include <vector>
634 using namespace llvm;
636 //===----------------------------------------------------------------------===//
638 //===----------------------------------------------------------------------===//
640 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
641 // of these for known things.
646 tok_def = -2, tok_extern = -3,
649 tok_identifier = -4, tok_number = -5,
652 static std::string IdentifierStr; // Filled in if tok_identifier
653 static double NumVal; // Filled in if tok_number
655 /// gettok - Return the next token from standard input.
656 static int gettok() {
657 static int LastChar = ' ';
659 // Skip any whitespace.
660 while (isspace(LastChar))
661 LastChar = getchar();
663 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
664 IdentifierStr = LastChar;
665 while (isalnum((LastChar = getchar())))
666 IdentifierStr += LastChar;
668 if (IdentifierStr == "def") return tok_def;
669 if (IdentifierStr == "extern") return tok_extern;
670 return tok_identifier;
673 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
677 LastChar = getchar();
678 } while (isdigit(LastChar) || LastChar == '.');
680 NumVal = strtod(NumStr.c_str(), 0);
684 if (LastChar == '#') {
685 // Comment until end of line.
686 do LastChar = getchar();
687 while (LastChar != EOF && LastChar != '\n' & LastChar != '\r');
693 // Check for end of file. Don't eat the EOF.
697 // Otherwise, just return the character as its ascii value.
698 int ThisChar = LastChar;
699 LastChar = getchar();
703 //===----------------------------------------------------------------------===//
704 // Abstract Syntax Tree (aka Parse Tree)
705 //===----------------------------------------------------------------------===//
707 /// ExprAST - Base class for all expression nodes.
710 virtual ~ExprAST() {}
711 virtual Value *Codegen() = 0;
714 /// NumberExprAST - Expression class for numeric literals like "1.0".
715 class NumberExprAST : public ExprAST {
718 explicit NumberExprAST(double val) : Val(val) {}
719 virtual Value *Codegen();
722 /// VariableExprAST - Expression class for referencing a variable, like "a".
723 class VariableExprAST : public ExprAST {
726 explicit VariableExprAST(const std::string &name) : Name(name) {}
727 virtual Value *Codegen();
730 /// BinaryExprAST - Expression class for a binary operator.
731 class BinaryExprAST : public ExprAST {
735 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
736 : Op(op), LHS(lhs), RHS(rhs) {}
737 virtual Value *Codegen();
740 /// CallExprAST - Expression class for function calls.
741 class CallExprAST : public ExprAST {
743 std::vector<ExprAST*> Args;
745 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
746 : Callee(callee), Args(args) {}
747 virtual Value *Codegen();
750 /// PrototypeAST - This class represents the "prototype" for a function,
751 /// which captures its argument names as well as if it is an operator.
754 std::vector<std::string> Args;
756 PrototypeAST(const std::string &name, const std::vector<std::string> &args)
757 : Name(name), Args(args) {}
762 /// FunctionAST - This class represents a function definition itself.
767 FunctionAST(PrototypeAST *proto, ExprAST *body)
768 : Proto(proto), Body(body) {}
773 //===----------------------------------------------------------------------===//
775 //===----------------------------------------------------------------------===//
777 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
778 /// token the parser it looking at. getNextToken reads another token from the
779 /// lexer and updates CurTok with its results.
781 static int getNextToken() {
782 return CurTok = gettok();
785 /// BinopPrecedence - This holds the precedence for each binary operator that is
787 static std::map<char, int> BinopPrecedence;
789 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
790 static int GetTokPrecedence() {
791 if (!isascii(CurTok))
794 // Make sure it's a declared binop.
795 int TokPrec = BinopPrecedence[CurTok];
796 if (TokPrec <= 0) return -1;
800 /// Error* - These are little helper functions for error handling.
801 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
802 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
803 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
805 static ExprAST *ParseExpression();
809 /// ::= identifer '(' expression* ')'
810 static ExprAST *ParseIdentifierExpr() {
811 std::string IdName = IdentifierStr;
813 getNextToken(); // eat identifer.
815 if (CurTok != '(') // Simple variable ref.
816 return new VariableExprAST(IdName);
819 getNextToken(); // eat (
820 std::vector<ExprAST*> Args;
822 ExprAST *Arg = ParseExpression();
826 if (CurTok == ')') break;
829 return Error("Expected ')'");
836 return new CallExprAST(IdName, Args);
839 /// numberexpr ::= number
840 static ExprAST *ParseNumberExpr() {
841 ExprAST *Result = new NumberExprAST(NumVal);
842 getNextToken(); // consume the number
846 /// parenexpr ::= '(' expression ')'
847 static ExprAST *ParseParenExpr() {
848 getNextToken(); // eat (.
849 ExprAST *V = ParseExpression();
853 return Error("expected ')'");
854 getNextToken(); // eat ).
859 /// ::= identifierexpr
862 static ExprAST *ParsePrimary() {
864 default: return Error("unknown token when expecting an expression");
865 case tok_identifier: return ParseIdentifierExpr();
866 case tok_number: return ParseNumberExpr();
867 case '(': return ParseParenExpr();
872 /// ::= ('+' primary)*
873 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
874 // If this is a binop, find its precedence.
876 int TokPrec = GetTokPrecedence();
878 // If this is a binop that binds at least as tightly as the current binop,
879 // consume it, otherwise we are done.
880 if (TokPrec < ExprPrec)
883 // Okay, we know this is a binop.
885 getNextToken(); // eat binop
887 // Parse the primary expression after the binary operator.
888 ExprAST *RHS = ParsePrimary();
891 // If BinOp binds less tightly with RHS than the operator after RHS, let
892 // the pending operator take RHS as its LHS.
893 int NextPrec = GetTokPrecedence();
894 if (TokPrec < NextPrec) {
895 RHS = ParseBinOpRHS(TokPrec+1, RHS);
896 if (RHS == 0) return 0;
900 LHS = new BinaryExprAST(BinOp, LHS, RHS);
905 /// ::= primary binoprhs
907 static ExprAST *ParseExpression() {
908 ExprAST *LHS = ParsePrimary();
911 return ParseBinOpRHS(0, LHS);
915 /// ::= id '(' id* ')'
916 static PrototypeAST *ParsePrototype() {
917 if (CurTok != tok_identifier)
918 return ErrorP("Expected function name in prototype");
920 std::string FnName = IdentifierStr;
924 return ErrorP("Expected '(' in prototype");
926 std::vector<std::string> ArgNames;
927 while (getNextToken() == tok_identifier)
928 ArgNames.push_back(IdentifierStr);
930 return ErrorP("Expected ')' in prototype");
933 getNextToken(); // eat ')'.
935 return new PrototypeAST(FnName, ArgNames);
938 /// definition ::= 'def' prototype expression
939 static FunctionAST *ParseDefinition() {
940 getNextToken(); // eat def.
941 PrototypeAST *Proto = ParsePrototype();
942 if (Proto == 0) return 0;
944 if (ExprAST *E = ParseExpression())
945 return new FunctionAST(Proto, E);
949 /// toplevelexpr ::= expression
950 static FunctionAST *ParseTopLevelExpr() {
951 if (ExprAST *E = ParseExpression()) {
952 // Make an anonymous proto.
953 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
954 return new FunctionAST(Proto, E);
959 /// external ::= 'extern' prototype
960 static PrototypeAST *ParseExtern() {
961 getNextToken(); // eat extern.
962 return ParsePrototype();
965 //===----------------------------------------------------------------------===//
967 //===----------------------------------------------------------------------===//
969 static Module *TheModule;
970 static LLVMBuilder Builder;
971 static std::map<std::string, Value*> NamedValues;
973 Value *ErrorV(const char *Str) { Error(Str); return 0; }
975 Value *NumberExprAST::Codegen() {
976 return ConstantFP::get(Type::DoubleTy, APFloat(Val));
979 Value *VariableExprAST::Codegen() {
980 // Look this variable up in the function.
981 Value *V = NamedValues[Name];
982 return V ? V : ErrorV("Unknown variable name");
985 Value *BinaryExprAST::Codegen() {
986 Value *L = LHS->Codegen();
987 Value *R = RHS->Codegen();
988 if (L == 0 || R == 0) return 0;
991 case '+': return Builder.CreateAdd(L, R, "addtmp");
992 case '-': return Builder.CreateSub(L, R, "subtmp");
993 case '*': return Builder.CreateMul(L, R, "multmp");
995 L = Builder.CreateFCmpULT(L, R, "multmp");
996 // Convert bool 0/1 to double 0.0 or 1.0
997 return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
998 default: return ErrorV("invalid binary operator");
1002 Value *CallExprAST::Codegen() {
1003 // Look up the name in the global module table.
1004 Function *CalleeF = TheModule->getFunction(Callee);
1006 return ErrorV("Unknown function referenced");
1008 // If argument mismatch error.
1009 if (CalleeF->arg_size() != Args.size())
1010 return ErrorV("Incorrect # arguments passed");
1012 std::vector<Value*> ArgsV;
1013 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1014 ArgsV.push_back(Args[i]->Codegen());
1015 if (ArgsV.back() == 0) return 0;
1018 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1021 Function *PrototypeAST::Codegen() {
1022 // Make the function type: double(double,double) etc.
1023 std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
1024 FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
1026 Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
1028 // If F conflicted, there was already something named 'Name'. If it has a
1029 // body, don't allow redefinition or reextern.
1030 if (F->getName() != Name) {
1031 // Delete the one we just made and get the existing one.
1032 F->eraseFromParent();
1033 F = TheModule->getFunction(Name);
1035 // If F already has a body, reject this.
1036 if (!F->empty()) {
1037 ErrorF("redefinition of function");
1041 // If F took a different number of args, reject.
1042 if (F->arg_size() != Args.size()) {
1043 ErrorF("redefinition of function with different # args");
1048 // Set names for all arguments.
1050 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1052 AI->setName(Args[Idx]);
1054 // Add arguments to variable symbol table.
1055 NamedValues[Args[Idx]] = AI;
1061 Function *FunctionAST::Codegen() {
1062 NamedValues.clear();
1064 Function *TheFunction = Proto->Codegen();
1065 if (TheFunction == 0)
1068 // Create a new basic block to start insertion into.
1069 BasicBlock *BB = new BasicBlock("entry", TheFunction);
1070 Builder.SetInsertPoint(BB);
1072 if (Value *RetVal = Body->Codegen()) {
1073 // Finish off the function.
1074 Builder.CreateRet(RetVal);
1078 // Error reading body, remove function.
1079 TheFunction->eraseFromParent();
1083 //===----------------------------------------------------------------------===//
1084 // Top-Level parsing and JIT Driver
1085 //===----------------------------------------------------------------------===//
1087 static void HandleDefinition() {
1088 if (FunctionAST *F = ParseDefinition()) {
1089 if (Function *LF = F->Codegen()) {
1090 fprintf(stderr, "Read function definition:");
1094 // Skip token for error recovery.
1099 static void HandleExtern() {
1100 if (PrototypeAST *P = ParseExtern()) {
1101 if (Function *F = P->Codegen()) {
1102 fprintf(stderr, "Read extern: ");
1106 // Skip token for error recovery.
1111 static void HandleTopLevelExpression() {
1112 // Evaluate a top level expression into an anonymous function.
1113 if (FunctionAST *F = ParseTopLevelExpr()) {
1114 if (Function *LF = F->Codegen()) {
1115 fprintf(stderr, "Read top-level expression:");
1119 // Skip token for error recovery.
1124 /// top ::= definition | external | expression | ';'
1125 static void MainLoop() {
1127 fprintf(stderr, "ready> ");
1129 case tok_eof: return;
1130 case ';': getNextToken(); break; // ignore top level semicolons.
1131 case tok_def: HandleDefinition(); break;
1132 case tok_extern: HandleExtern(); break;
1133 default: HandleTopLevelExpression(); break;
1140 //===----------------------------------------------------------------------===//
1141 // "Library" functions that can be "extern'd" from user code.
1142 //===----------------------------------------------------------------------===//
1144 /// putchard - putchar that takes a double and returns 0.
1146 double putchard(double X) {
1151 //===----------------------------------------------------------------------===//
1152 // Main driver code.
1153 //===----------------------------------------------------------------------===//
1156 TheModule = new Module("my cool jit");
1158 // Install standard binary operators.
1159 // 1 is lowest precedence.
1160 BinopPrecedence['<'] = 10;
1161 BinopPrecedence['+'] = 20;
1162 BinopPrecedence['-'] = 20;
1163 BinopPrecedence['*'] = 40; // highest.
1165 // Prime the first token.
1166 fprintf(stderr, "ready> ");
1170 TheModule->dump();
1177 <!-- *********************************************************************** -->
1180 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1181 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1182 <a href="http://validator.w3.org/check/referer"><img
1183 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1185 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1186 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1187 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $