| blob | a8d96ac6b7005987775bdcc05a7bfa2c8e0dec4d |
4 <html>
5 <head>
10 </head>
12 <body>
16 <ul>
19 <ol>
26 </ol>
27 </li>
29 Support</li>
30 </ul>
34 </div>
36 <!-- *********************************************************************** -->
38 <!-- *********************************************************************** -->
45 This will teach you a little bit about how LLVM does things, as well as
46 demonstrate how easy it is to use. It's much more work to build a lexer and
47 parser than it is to generate LLVM IR code. :)
48 </p>
51 later. LLVM 2.1 and before will not work with it. Also note that you need
52 to use a version of this tutorial that matches your LLVM release: If you are
53 using an official LLVM release, use the version of the documentation included
57 </div>
59 <!-- *********************************************************************** -->
61 <!-- *********************************************************************** -->
65 <p>
66 In order to generate LLVM IR, we want some simple setup to get started. First
67 we define virtual code generation (codegen) methods in each AST class:</p>
70 <pre>
71 /// ExprAST - Base class for all expression nodes.
72 class ExprAST {
73 public:
74 virtual ~ExprAST() {}
76 };
78 /// NumberExprAST - Expression class for numeric literals like "1.0".
79 class NumberExprAST : public ExprAST {
80 double Val;
81 public:
82 NumberExprAST(double val) : Val(val) {}
84 };
85 ...
86 </pre>
87 </div>
89 <p>The Codegen() method says to emit IR for that AST node along with all the things it
90 depends on, and they all return an LLVM Value object.
94 of SSA values is that their value is computed as the related instruction
95 executes, and it does not get a new value until (and if) the instruction
96 re-executes. In other words, there is no way to "change" an SSA value. For
97 more information, please read up on <a
101 <p>Note that instead of adding virtual methods to the ExprAST class hierarchy,
102 it could also make sense to use a <a
104 other way to model this. Again, this tutorial won't dwell on good software
105 engineering practices: for our purposes, adding a virtual method is
106 simplest.</p>
108 <p>The
109 second thing we want is an "Error" method like we used for the parser, which will
110 be used to report errors found during code generation (for example, use of an
111 undeclared parameter):</p>
114 <pre>
115 Value *ErrorV(const char *Str) { Error(Str); return 0; }
117 static Module *TheModule;
118 static IRBuilder<> Builder(getGlobalContext());
120 </pre>
121 </div>
124 is the LLVM construct that contains all of the functions and global variables in
125 a chunk of code. In many ways, it is the top-level structure that the LLVM IR
126 uses to contain code.</p>
129 LLVM instructions. Instances of the <a
131 class template keep track of the current place to insert instructions and has
132 methods to create new instructions.</p>
135 current scope and what their LLVM representation is. (In other words, it is a
136 symbol table for the code). In this form of Kaleidoscope, the only things that
137 can be referenced are function parameters. As such, function parameters will
138 be in this map when generating code for their function body.</p>
140 <p>
141 With these basics in place, we can start talking about how to generate code for
144 has already been done, and we'll just use it to emit code.
145 </p>
147 </div>
149 <!-- *********************************************************************** -->
151 <!-- *********************************************************************** -->
155 <p>Generating LLVM code for expression nodes is very straightforward: less
156 than 45 lines of commented code for all four of our expression nodes. First
157 we'll do numeric literals:</p>
160 <pre>
161 Value *NumberExprAST::Codegen() {
162 return ConstantFP::get(getGlobalContext(), APFloat(Val));
163 }
164 </pre>
165 </div>
167 <p>In the LLVM IR, numeric constants are represented with the
172 that constants are all uniqued together and shared. For this reason, the API
176 <pre>
177 Value *VariableExprAST::Codegen() {
178 // Look this variable up in the function.
179 Value *V = NamedValues[Name];
180 return V ? V : ErrorV("Unknown variable name");
181 }
182 </pre>
183 </div>
185 <p>References to variables are also quite simple using LLVM. In the simple version
186 of Kaleidoscope, we assume that the variable has already been emitted somewhere
187 and its value is available. In practice, the only values that can be in the
189 code simply checks to see that the specified name is in the map (if not, an
190 unknown variable is being referenced) and returns the value for it. In future
196 <pre>
197 Value *BinaryExprAST::Codegen() {
198 Value *L = LHS->Codegen();
199 Value *R = RHS->Codegen();
202 switch (Op) {
203 case '+': return Builder.CreateFAdd(L, R, "addtmp");
204 case '-': return Builder.CreateFSub(L, R, "subtmp");
205 case '*': return Builder.CreateFMul(L, R, "multmp");
206 case '<':
207 L = Builder.CreateFCmpULT(L, R, "cmptmp");
209 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
210 "booltmp");
211 default: return ErrorV("invalid binary operator");
212 }
213 }
214 </pre>
215 </div>
217 <p>Binary operators start to get more interesting. The basic idea here is that
218 we recursively emit code for the left-hand side of the expression, then the
219 right-hand side, then we compute the result of the binary expression. In this
220 code, we do a simple switch on the opcode to create the right LLVM instruction.
221 </p>
223 <p>In the example above, the LLVM builder class is starting to show its value.
224 IRBuilder knows where to insert the newly created instruction, all you have to
227 for the generated instruction.</p>
229 <p>One nice thing about LLVM is that the name is just a hint. For instance, if
230 the code above emits multiple "addtmp" variables, LLVM will automatically
231 provide each one with an increasing, unique numeric suffix. Local value names
232 for instructions are purely optional, but it makes it much easier to read the
233 IR dumps.</p>
236 strict rules: for example, the Left and Right operators of
238 type, and the result type of the add must match the operand types. Because
239 all values in Kaleidoscope are doubles, this makes for very simple code for add,
240 sub and mul.</p>
244 (a one bit integer). The problem with this is that Kaleidoscope wants the value to be a 0.0 or 1.0 value. In order to get these semantics, we combine the fcmp instruction with
246 converts its input integer into a floating point value by treating the input
247 as an unsigned value. In contrast, if we used the <a
252 <pre>
253 Value *CallExprAST::Codegen() {
254 // Look up the name in the global module table.
255 Function *CalleeF = TheModule->getFunction(Callee);
256 if (CalleeF == 0)
257 return ErrorV("Unknown function referenced");
259 // If argument mismatch error.
260 if (CalleeF->arg_size() != Args.size())
261 return ErrorV("Incorrect # arguments passed");
264 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
265 ArgsV.push_back(Args[i]->Codegen());
267 }
269 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
270 }
271 </pre>
272 </div>
274 <p>Code generation for function calls is quite straightforward with LLVM. The
275 code above initially does a function name lookup in the LLVM Module's symbol
276 table. Recall that the LLVM Module is the container that holds all of the
277 functions we are JIT'ing. By giving each function the same name as what the
278 user specifies, we can use the LLVM symbol table to resolve function names for
279 us.</p>
281 <p>Once we have the function to call, we recursively codegen each argument that
283 instruction</a>. Note that LLVM uses the native C calling conventions by
284 default, allowing these calls to also call into standard library functions like
287 <p>This wraps up our handling of the four basic expressions that we have so far
288 in Kaleidoscope. Feel free to go in and add some more. For example, by
290 several other interesting instructions that are really easy to plug into our
291 basic framework.</p>
293 </div>
295 <!-- *********************************************************************** -->
297 <!-- *********************************************************************** -->
301 <p>Code generation for prototypes and functions must handle a number of
302 details, which make their code less beautiful than expression code
303 generation, but allows us to illustrate some important points. First, lets
304 talk about code generation for prototypes: they are used both for function
305 bodies and external function declarations. The code starts with:</p>
308 <pre>
309 Function *PrototypeAST::Codegen() {
310 // Make the function type: double(double,double) etc.
312 Type::getDoubleTy(getGlobalContext()));
313 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
314 Doubles, false);
316 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
317 </pre>
318 </div>
320 <p>This code packs a lot of power into a few lines. Note first that this
322 really talks about the external interface for a function (not the value computed
323 by an expression), it makes sense for it to return the LLVM Function it
324 corresponds to when codegen'd.</p>
328 function arguments in Kaleidoscope are of type double, the first line creates
330 method to create a function type that takes "N" doubles as arguments, returns
331 one double as a result, and that is not vararg (the false parameter indicates
332 this). Note that Types in LLVM are uniqued just like Constants are, so you
335 <p>The final line above actually creates the function that the prototype will
336 correspond to. This indicates the type, linkage and name to use, as well as which
338 means that the function may be defined outside the current module and/or that it
339 is callable by functions outside the module. The Name passed in is the name the
340 user specified: since "<tt>TheModule</tt>" is specified, this name is registered
341 in "<tt>TheModule</tt>"s symbol table, which is used by the function call code
342 above.</p>
345 <pre>
346 // If F conflicted, there was already something named 'Name'. If it has a
347 // body, don't allow redefinition or reextern.
348 if (F->getName() != Name) {
349 // Delete the one we just made and get the existing one.
350 F->eraseFromParent();
351 F = TheModule->getFunction(Name);
352 </pre>
353 </div>
355 <p>The Module symbol table works just like the Function symbol table when it
356 comes to name conflicts: if a new function is created with a name was previously
357 added to the symbol table, it will get implicitly renamed when added to the
358 Module. The code above exploits this fact to determine if there was a previous
359 definition of this function.</p>
361 <p>In Kaleidoscope, I choose to allow redefinitions of functions in two cases:
362 first, we want to allow 'extern'ing a function more than once, as long as the
363 prototypes for the externs match (since all arguments have the same type, we
364 just have to check that the number of arguments match). Second, we want to
365 allow 'extern'ing a function and then defining a body for it. This is useful
366 when defining mutually recursive functions.</p>
368 <p>In order to implement this, the code above first checks to see if there is
369 a collision on the name of the function. If so, it deletes the function we just
373 unlinks the object from its parent (e.g. a Function from a Module) and returns
377 <pre>
378 // If F already has a body, reject this.
379 if (!F->empty()) {
380 ErrorF("redefinition of function");
381 return 0;
382 }
384 // If F took a different number of args, reject.
385 if (F->arg_size() != Args.size()) {
386 ErrorF("redefinition of function with different # args");
387 return 0;
388 }
389 }
390 </pre>
391 </div>
393 <p>In order to verify the logic above, we first check to see if the pre-existing
394 function is "empty". In this case, empty means that it has no basic blocks in
395 it, which means it has no body. If it has no body, it is a forward
396 declaration. Since we don't allow anything after a full definition of the
397 function, the code rejects this case. If the previous reference to a function
398 was an 'extern', we simply verify that the number of arguments for that
399 definition and this one match up. If not, we emit an error.</p>
402 <pre>
403 // Set names for all arguments.
404 unsigned Idx = 0;
405 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
406 ++AI, ++Idx) {
407 AI->setName(Args[Idx]);
409 // Add arguments to variable symbol table.
410 NamedValues[Args[Idx]] = AI;
411 }
412 return F;
413 }
414 </pre>
415 </div>
417 <p>The last bit of code for prototypes loops over all of the arguments in the
418 function, setting the name of the LLVM Argument objects to match, and registering
421 object to the caller. Note that we don't check for conflicting
422 argument names here (e.g. "extern foo(a b a)"). Doing so would be very
423 straight-forward with the mechanics we have already used above.</p>
426 <pre>
427 Function *FunctionAST::Codegen() {
428 NamedValues.clear();
430 Function *TheFunction = Proto->Codegen();
431 if (TheFunction == 0)
432 return 0;
433 </pre>
434 </div>
436 <p>Code generation for function definitions starts out simply enough: we just
437 codegen the prototype (Proto) and verify that it is ok. We then clear out the
439 last function we compiled. Code generation of the prototype ensures that there
440 is an LLVM Function object that is ready to go for us.</p>
443 <pre>
444 // Create a new basic block to start insertion into.
445 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
446 Builder.SetInsertPoint(BB);
448 if (Value *RetVal = Body->Codegen()) {
449 </pre>
450 </div>
455 second line then tells the builder that new instructions should be inserted into
456 the end of the new basic block. Basic blocks in LLVM are an important part
457 of functions that define the <a
459 Since we don't have any control flow, our functions will only contain one
463 <pre>
464 if (Value *RetVal = Body->Codegen()) {
465 // Finish off the function.
466 Builder.CreateRet(RetVal);
468 // Validate the generated code, checking for consistency.
469 verifyFunction(*TheFunction);
471 return TheFunction;
472 }
473 </pre>
474 </div>
477 the root expression of the function. If no error happens, this emits code to
478 compute the expression into the entry block and returns the value that was
479 computed. Assuming no error, we then create an LLVM <a
482 is provided by LLVM. This function does a variety of consistency checks on the
483 generated code, to determine if our compiler is doing everything right. Using
484 this is important: it can catch a lot of bugs. Once the function is finished
485 and validated, we return it.</p>
488 <pre>
489 // Error reading body, remove function.
490 TheFunction->eraseFromParent();
491 return 0;
492 }
493 </pre>
494 </div>
496 <p>The only piece left here is handling of the error case. For simplicity, we
497 handle this by merely deleting the function we produced with the
499 that they incorrectly typed in before: if we didn't delete it, it would live in
500 the symbol table, with a body, preventing future redefinition.</p>
503 can return a previously defined forward declaration, our code can actually delete
504 a forward declaration. There are a number of ways to fix this bug, see what you
505 can come up with! Here is a testcase:</p>
508 <pre>
509 extern foo(a b); # ok, defines foo.
510 def foo(a b) c; # error, 'c' is invalid.
512 </pre>
513 </div>
515 </div>
517 <!-- *********************************************************************** -->
519 Closing Thoughts</a></div>
520 <!-- *********************************************************************** -->
524 <p>
525 For now, code generation to LLVM doesn't really get us much, except that we can
526 look at the pretty IR calls. The sample code inserts calls to Codegen into the
528 dumps out the LLVM IR. This gives a nice way to look at the LLVM IR for simple
529 functions. For example:
530 </p>
533 <pre>
535 Read top-level expression:
536 define double @""() {
537 entry:
538 ret double 9.000000e+00
539 }
540 </pre>
541 </div>
543 <p>Note how the parser turns the top-level expression into anonymous functions
545 support</a> in the next chapter. Also note that the code is very literally
546 transcribed, no optimizations are being performed except simple constant
547 folding done by IRBuilder. We will
549 the next chapter.</p>
552 <pre>
554 Read function definition:
555 define double @foo(double %a, double %b) {
556 entry:
557 %multmp = fmul double %a, %a
558 %multmp1 = fmul double 2.000000e+00, %a
559 %multmp2 = fmul double %multmp1, %b
560 %addtmp = fadd double %multmp, %multmp2
561 %multmp3 = fmul double %b, %b
562 %addtmp4 = fadd double %addtmp, %multmp3
563 ret double %addtmp4
564 }
565 </pre>
566 </div>
568 <p>This shows some simple arithmetic. Notice the striking similarity to the
569 LLVM builder calls that we use to create the instructions.</p>
572 <pre>
574 Read function definition:
575 define double @bar(double %a) {
576 entry:
577 %calltmp = call double @foo(double %a, double 4.000000e+00)
578 %calltmp1 = call double @bar(double 3.133700e+04)
579 %addtmp = fadd double %calltmp, %calltmp1
580 ret double %addtmp
581 }
582 </pre>
583 </div>
585 <p>This shows some function calls. Note that this function will take a long
586 time to execute if you call it. In the future we'll add conditional control
587 flow to actually make recursion useful :).</p>
590 <pre>
592 Read extern:
593 declare double @cos(double)
596 Read top-level expression:
597 define double @""() {
598 entry:
599 %calltmp = call double @cos(double 1.234000e+00)
600 ret double %calltmp
601 }
602 </pre>
603 </div>
609 <pre>
611 ; ModuleID = 'my cool jit'
613 define double @""() {
614 entry:
616 ret double %addtmp
617 }
619 define double @foo(double %a, double %b) {
620 entry:
621 %multmp = fmul double %a, %a
622 %multmp1 = fmul double 2.000000e+00, %a
623 %multmp2 = fmul double %multmp1, %b
624 %addtmp = fadd double %multmp, %multmp2
625 %multmp3 = fmul double %b, %b
626 %addtmp4 = fadd double %addtmp, %multmp3
627 ret double %addtmp4
628 }
630 define double @bar(double %a) {
631 entry:
632 %calltmp = call double @foo(double %a, double 4.000000e+00)
633 %calltmp1 = call double @bar(double 3.133700e+04)
634 %addtmp = fadd double %calltmp, %calltmp1
635 ret double %addtmp
636 }
638 declare double @cos(double)
640 define double @""() {
641 entry:
642 %calltmp = call double @cos(double 1.234000e+00)
643 ret double %calltmp
644 }
645 </pre>
646 </div>
648 <p>When you quit the current demo, it dumps out the IR for the entire module
649 generated. Here you can see the big picture with all the functions referencing
650 each other.</p>
652 <p>This wraps up the third chapter of the Kaleidoscope tutorial. Up next, we'll
656 </div>
659 <!-- *********************************************************************** -->
661 <!-- *********************************************************************** -->
665 <p>
666 Here is the complete code listing for our running example, enhanced with the
667 LLVM code generator. Because this uses the LLVM libraries, we need to link
668 them in. To do this, we use the <a
670 our makefile/command line about which options to use:</p>
673 <pre>
674 # Compile
675 g++ -g -O3 toy.cpp `llvm-config --cppflags --ldflags --libs core` -o toy
676 # Run
677 ./toy
678 </pre>
679 </div>
684 <pre>
685 // To build this:
686 // See example below.
688 #include "llvm/DerivedTypes.h"
689 #include "llvm/LLVMContext.h"
690 #include "llvm/Module.h"
691 #include "llvm/Analysis/Verifier.h"
692 #include "llvm/Support/IRBuilder.h"
697 using namespace llvm;
699 //===----------------------------------------------------------------------===//
700 // Lexer
701 //===----------------------------------------------------------------------===//
704 // of these for known things.
705 enum Token {
706 tok_eof = -1,
708 // commands
711 // primary
713 };
715 static std::string IdentifierStr; // Filled in if tok_identifier
716 static double NumVal; // Filled in if tok_number
718 /// gettok - Return the next token from standard input.
719 static int gettok() {
720 static int LastChar = ' ';
722 // Skip any whitespace.
723 while (isspace(LastChar))
724 LastChar = getchar();
726 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
727 IdentifierStr = LastChar;
728 while (isalnum((LastChar = getchar())))
729 IdentifierStr += LastChar;
731 if (IdentifierStr == "def") return tok_def;
732 if (IdentifierStr == "extern") return tok_extern;
733 return tok_identifier;
734 }
737 std::string NumStr;
738 do {
739 NumStr += LastChar;
740 LastChar = getchar();
741 } while (isdigit(LastChar) || LastChar == '.');
743 NumVal = strtod(NumStr.c_str(), 0);
744 return tok_number;
745 }
747 if (LastChar == '#') {
748 // Comment until end of line.
749 do LastChar = getchar();
752 if (LastChar != EOF)
753 return gettok();
754 }
756 // Check for end of file. Don't eat the EOF.
757 if (LastChar == EOF)
758 return tok_eof;
760 // Otherwise, just return the character as its ascii value.
761 int ThisChar = LastChar;
762 LastChar = getchar();
763 return ThisChar;
764 }
766 //===----------------------------------------------------------------------===//
767 // Abstract Syntax Tree (aka Parse Tree)
768 //===----------------------------------------------------------------------===//
770 /// ExprAST - Base class for all expression nodes.
771 class ExprAST {
772 public:
773 virtual ~ExprAST() {}
774 virtual Value *Codegen() = 0;
775 };
777 /// NumberExprAST - Expression class for numeric literals like "1.0".
778 class NumberExprAST : public ExprAST {
779 double Val;
780 public:
781 NumberExprAST(double val) : Val(val) {}
782 virtual Value *Codegen();
783 };
785 /// VariableExprAST - Expression class for referencing a variable, like "a".
786 class VariableExprAST : public ExprAST {
787 std::string Name;
788 public:
789 VariableExprAST(const std::string &name) : Name(name) {}
790 virtual Value *Codegen();
791 };
793 /// BinaryExprAST - Expression class for a binary operator.
794 class BinaryExprAST : public ExprAST {
795 char Op;
796 ExprAST *LHS, *RHS;
797 public:
798 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
799 : Op(op), LHS(lhs), RHS(rhs) {}
800 virtual Value *Codegen();
801 };
803 /// CallExprAST - Expression class for function calls.
804 class CallExprAST : public ExprAST {
805 std::string Callee;
807 public:
809 : Callee(callee), Args(args) {}
810 virtual Value *Codegen();
811 };
813 /// PrototypeAST - This class represents the "prototype" for a function,
814 /// which captures its name, and its argument names (thus implicitly the number
815 /// of arguments the function takes).
816 class PrototypeAST {
817 std::string Name;
819 public:
821 : Name(name), Args(args) {}
823 Function *Codegen();
824 };
826 /// FunctionAST - This class represents a function definition itself.
827 class FunctionAST {
828 PrototypeAST *Proto;
829 ExprAST *Body;
830 public:
831 FunctionAST(PrototypeAST *proto, ExprAST *body)
832 : Proto(proto), Body(body) {}
834 Function *Codegen();
835 };
837 //===----------------------------------------------------------------------===//
838 // Parser
839 //===----------------------------------------------------------------------===//
841 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
842 /// token the parser is looking at. getNextToken reads another token from the
843 /// lexer and updates CurTok with its results.
844 static int CurTok;
845 static int getNextToken() {
846 return CurTok = gettok();
847 }
849 /// BinopPrecedence - This holds the precedence for each binary operator that is
850 /// defined.
853 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
854 static int GetTokPrecedence() {
855 if (!isascii(CurTok))
856 return -1;
858 // Make sure it's a declared binop.
859 int TokPrec = BinopPrecedence[CurTok];
861 return TokPrec;
862 }
864 /// Error* - These are little helper functions for error handling.
866 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
867 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
869 static ExprAST *ParseExpression();
871 /// identifierexpr
872 /// ::= identifier
873 /// ::= identifier '(' expression* ')'
874 static ExprAST *ParseIdentifierExpr() {
875 std::string IdName = IdentifierStr;
877 getNextToken(); // eat identifier.
879 if (CurTok != '(') // Simple variable ref.
880 return new VariableExprAST(IdName);
882 // Call.
883 getNextToken(); // eat (
885 if (CurTok != ')') {
886 while (1) {
887 ExprAST *Arg = ParseExpression();
888 if (!Arg) return 0;
889 Args.push_back(Arg);
891 if (CurTok == ')') break;
893 if (CurTok != ',')
894 return Error("Expected ')' or ',' in argument list");
895 getNextToken();
896 }
897 }
899 // Eat the ')'.
900 getNextToken();
902 return new CallExprAST(IdName, Args);
903 }
905 /// numberexpr ::= number
906 static ExprAST *ParseNumberExpr() {
907 ExprAST *Result = new NumberExprAST(NumVal);
908 getNextToken(); // consume the number
909 return Result;
910 }
912 /// parenexpr ::= '(' expression ')'
913 static ExprAST *ParseParenExpr() {
914 getNextToken(); // eat (.
915 ExprAST *V = ParseExpression();
916 if (!V) return 0;
918 if (CurTok != ')')
919 return Error("expected ')'");
920 getNextToken(); // eat ).
921 return V;
922 }
924 /// primary
925 /// ::= identifierexpr
926 /// ::= numberexpr
927 /// ::= parenexpr
928 static ExprAST *ParsePrimary() {
929 switch (CurTok) {
930 default: return Error("unknown token when expecting an expression");
931 case tok_identifier: return ParseIdentifierExpr();
932 case tok_number: return ParseNumberExpr();
933 case '(': return ParseParenExpr();
934 }
935 }
937 /// binoprhs
938 /// ::= ('+' primary)*
939 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
940 // If this is a binop, find its precedence.
941 while (1) {
942 int TokPrec = GetTokPrecedence();
944 // If this is a binop that binds at least as tightly as the current binop,
945 // consume it, otherwise we are done.
946 if (TokPrec < ExprPrec)
947 return LHS;
949 // Okay, we know this is a binop.
950 int BinOp = CurTok;
951 getNextToken(); // eat binop
953 // Parse the primary expression after the binary operator.
954 ExprAST *RHS = ParsePrimary();
955 if (!RHS) return 0;
957 // If BinOp binds less tightly with RHS than the operator after RHS, let
958 // the pending operator take RHS as its LHS.
959 int NextPrec = GetTokPrecedence();
960 if (TokPrec < NextPrec) {
961 RHS = ParseBinOpRHS(TokPrec+1, RHS);
963 }
965 // Merge LHS/RHS.
966 LHS = new BinaryExprAST(BinOp, LHS, RHS);
967 }
968 }
970 /// expression
971 /// ::= primary binoprhs
972 ///
973 static ExprAST *ParseExpression() {
974 ExprAST *LHS = ParsePrimary();
975 if (!LHS) return 0;
977 return ParseBinOpRHS(0, LHS);
978 }
980 /// prototype
981 /// ::= id '(' id* ')'
982 static PrototypeAST *ParsePrototype() {
983 if (CurTok != tok_identifier)
984 return ErrorP("Expected function name in prototype");
986 std::string FnName = IdentifierStr;
987 getNextToken();
989 if (CurTok != '(')
990 return ErrorP("Expected '(' in prototype");
993 while (getNextToken() == tok_identifier)
994 ArgNames.push_back(IdentifierStr);
995 if (CurTok != ')')
996 return ErrorP("Expected ')' in prototype");
998 // success.
999 getNextToken(); // eat ')'.
1001 return new PrototypeAST(FnName, ArgNames);
1002 }
1004 /// definition ::= 'def' prototype expression
1005 static FunctionAST *ParseDefinition() {
1006 getNextToken(); // eat def.
1007 PrototypeAST *Proto = ParsePrototype();
1010 if (ExprAST *E = ParseExpression())
1011 return new FunctionAST(Proto, E);
1012 return 0;
1013 }
1015 /// toplevelexpr ::= expression
1016 static FunctionAST *ParseTopLevelExpr() {
1017 if (ExprAST *E = ParseExpression()) {
1018 // Make an anonymous proto.
1020 return new FunctionAST(Proto, E);
1021 }
1022 return 0;
1023 }
1025 /// external ::= 'extern' prototype
1026 static PrototypeAST *ParseExtern() {
1027 getNextToken(); // eat extern.
1028 return ParsePrototype();
1029 }
1031 //===----------------------------------------------------------------------===//
1032 // Code Generation
1033 //===----------------------------------------------------------------------===//
1035 static Module *TheModule;
1036 static IRBuilder<> Builder(getGlobalContext());
1039 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1041 Value *NumberExprAST::Codegen() {
1042 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1043 }
1045 Value *VariableExprAST::Codegen() {
1046 // Look this variable up in the function.
1047 Value *V = NamedValues[Name];
1048 return V ? V : ErrorV("Unknown variable name");
1049 }
1051 Value *BinaryExprAST::Codegen() {
1052 Value *L = LHS->Codegen();
1053 Value *R = RHS->Codegen();
1056 switch (Op) {
1057 case '+': return Builder.CreateFAdd(L, R, "addtmp");
1058 case '-': return Builder.CreateFSub(L, R, "subtmp");
1059 case '*': return Builder.CreateFMul(L, R, "multmp");
1060 case '<':
1061 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1063 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1064 "booltmp");
1065 default: return ErrorV("invalid binary operator");
1066 }
1067 }
1069 Value *CallExprAST::Codegen() {
1070 // Look up the name in the global module table.
1071 Function *CalleeF = TheModule->getFunction(Callee);
1072 if (CalleeF == 0)
1073 return ErrorV("Unknown function referenced");
1075 // If argument mismatch error.
1076 if (CalleeF->arg_size() != Args.size())
1077 return ErrorV("Incorrect # arguments passed");
1080 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1081 ArgsV.push_back(Args[i]->Codegen());
1083 }
1085 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1086 }
1088 Function *PrototypeAST::Codegen() {
1089 // Make the function type: double(double,double) etc.
1091 Type::getDoubleTy(getGlobalContext()));
1092 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1093 Doubles, false);
1095 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1097 // If F conflicted, there was already something named 'Name'. If it has a
1098 // body, don't allow redefinition or reextern.
1099 if (F->getName() != Name) {
1100 // Delete the one we just made and get the existing one.
1101 F->eraseFromParent();
1102 F = TheModule->getFunction(Name);
1104 // If F already has a body, reject this.
1105 if (!F->empty()) {
1106 ErrorF("redefinition of function");
1107 return 0;
1108 }
1110 // If F took a different number of args, reject.
1111 if (F->arg_size() != Args.size()) {
1112 ErrorF("redefinition of function with different # args");
1113 return 0;
1114 }
1115 }
1117 // Set names for all arguments.
1118 unsigned Idx = 0;
1119 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1120 ++AI, ++Idx) {
1121 AI->setName(Args[Idx]);
1123 // Add arguments to variable symbol table.
1124 NamedValues[Args[Idx]] = AI;
1125 }
1127 return F;
1128 }
1130 Function *FunctionAST::Codegen() {
1131 NamedValues.clear();
1133 Function *TheFunction = Proto->Codegen();
1134 if (TheFunction == 0)
1135 return 0;
1137 // Create a new basic block to start insertion into.
1138 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1139 Builder.SetInsertPoint(BB);
1141 if (Value *RetVal = Body->Codegen()) {
1142 // Finish off the function.
1143 Builder.CreateRet(RetVal);
1145 // Validate the generated code, checking for consistency.
1146 verifyFunction(*TheFunction);
1148 return TheFunction;
1149 }
1151 // Error reading body, remove function.
1152 TheFunction->eraseFromParent();
1153 return 0;
1154 }
1156 //===----------------------------------------------------------------------===//
1157 // Top-Level parsing and JIT Driver
1158 //===----------------------------------------------------------------------===//
1160 static void HandleDefinition() {
1161 if (FunctionAST *F = ParseDefinition()) {
1162 if (Function *LF = F->Codegen()) {
1163 fprintf(stderr, "Read function definition:");
1164 LF->dump();
1165 }
1166 } else {
1167 // Skip token for error recovery.
1168 getNextToken();
1169 }
1170 }
1172 static void HandleExtern() {
1173 if (PrototypeAST *P = ParseExtern()) {
1174 if (Function *F = P->Codegen()) {
1175 fprintf(stderr, "Read extern: ");
1176 F->dump();
1177 }
1178 } else {
1179 // Skip token for error recovery.
1180 getNextToken();
1181 }
1182 }
1184 static void HandleTopLevelExpression() {
1185 // Evaluate a top-level expression into an anonymous function.
1186 if (FunctionAST *F = ParseTopLevelExpr()) {
1187 if (Function *LF = F->Codegen()) {
1188 fprintf(stderr, "Read top-level expression:");
1189 LF->dump();
1190 }
1191 } else {
1192 // Skip token for error recovery.
1193 getNextToken();
1194 }
1195 }
1197 /// top ::= definition | external | expression | ';'
1198 static void MainLoop() {
1199 while (1) {
1200 fprintf(stderr, "ready> ");
1201 switch (CurTok) {
1202 case tok_eof: return;
1203 case ';': getNextToken(); break; // ignore top-level semicolons.
1204 case tok_def: HandleDefinition(); break;
1205 case tok_extern: HandleExtern(); break;
1206 default: HandleTopLevelExpression(); break;
1207 }
1208 }
1209 }
1211 //===----------------------------------------------------------------------===//
1213 //===----------------------------------------------------------------------===//
1215 /// putchard - putchar that takes a double and returns 0.
1216 extern "C"
1217 double putchard(double X) {
1218 putchar((char)X);
1219 return 0;
1220 }
1222 //===----------------------------------------------------------------------===//
1223 // Main driver code.
1224 //===----------------------------------------------------------------------===//
1226 int main() {
1227 LLVMContext &Context = getGlobalContext();
1229 // Install standard binary operators.
1230 // 1 is lowest precedence.
1232 BinopPrecedence['+'] = 20;
1233 BinopPrecedence['-'] = 20;
1234 BinopPrecedence['*'] = 40; // highest.
1236 // Prime the first token.
1237 fprintf(stderr, "ready> ");
1238 getNextToken();
1240 // Make the module, which holds all the code.
1241 TheModule = new Module("my cool jit", Context);
1243 // Run the main "interpreter loop" now.
1244 MainLoop();
1246 // Print out all of the generated code.
1247 TheModule->dump();
1249 return 0;
1250 }
1251 </pre>
1252 </div>
1254 </div>
1256 <!-- *********************************************************************** -->
1257 <hr>
1258 <address>
1266 Last modified: $Date$
1267 </address>
1268 </body>
1269 </html>