| blob | 35dcdf4914e39b6cb968840415f80c0230cd5dd8 |
4 <html>
5 <head>
10 </head>
12 <body>
16 <ul>
19 <ol>
25 </ol>
26 </li>
28 Flow</li>
29 </ul>
33 </div>
35 <!-- *********************************************************************** -->
37 <!-- *********************************************************************** -->
43 language and added support for generating LLVM IR. This chapter describes
44 two new techniques: adding optimizer support to your language, and adding JIT
45 compiler support. These additions will demonstrate how to get nice, efficient code
46 for the Kaleidoscope language.</p>
48 </div>
50 <!-- *********************************************************************** -->
52 Folding</a></div>
53 <!-- *********************************************************************** -->
57 <p>
58 Our demonstration for Chapter 3 is elegant and easy to extend. Unfortunately,
59 it does not produce wonderful code. The IRBuilder, however, does give us
60 obvious optimizations when compiling simple code:</p>
63 <pre>
65 Read function definition:
66 define double @test(double %x) {
67 entry:
68 %addtmp = fadd double 3.000000e+00, %x
69 ret double %addtmp
70 }
71 </pre>
72 </div>
74 <p>This code is not a literal transcription of the AST built by parsing the
75 input. That would be:
78 <pre>
80 Read function definition:
81 define double @test(double %x) {
82 entry:
84 %addtmp1 = fadd double %addtmp, %x
85 ret double %addtmp1
86 }
87 </pre>
88 </div>
90 <p>Constant folding, as seen above, in particular, is a very common and very
91 important optimization: so much so that many language implementors implement
92 constant folding support in their AST representation.</p>
94 <p>With LLVM, you don't need this support in the AST. Since all calls to build
95 LLVM IR go through the LLVM IR builder, the builder itself checked to see if
96 there was a constant folding opportunity when you call it. If so, it just does
97 the constant fold and return the constant instead of creating an instruction.
99 <p>Well, that was easy :). In practice, we recommend always using
101 "syntactic overhead" for its use (you don't have to uglify your compiler with
102 constant checks everywhere) and it can dramatically reduce the amount of
103 LLVM IR that is generated in some cases (particular for languages with a macro
104 preprocessor or that use a lot of constants).</p>
107 that it does all of its analysis inline with the code as it is built. If you
108 take a slightly more complex example:</p>
111 <pre>
113 ready> Read function definition:
114 define double @test(double %x) {
115 entry:
116 %addtmp = fadd double 3.000000e+00, %x
117 %addtmp1 = fadd double %x, 3.000000e+00
118 %multmp = fmul double %addtmp, %addtmp1
119 ret double %multmp
120 }
121 </pre>
122 </div>
124 <p>In this case, the LHS and RHS of the multiplication are the same value. We'd
125 really like to see this generate "<tt>tmp = x+3; result = tmp*tmp;</tt>" instead
128 <p>Unfortunately, no amount of local analysis will be able to detect and correct
129 this. This requires two transformations: reassociation of expressions (to
130 make the add's lexically identical) and Common Subexpression Elimination (CSE)
131 to delete the redundant add instruction. Fortunately, LLVM provides a broad
134 </div>
136 <!-- *********************************************************************** -->
138 Passes</a></div>
139 <!-- *********************************************************************** -->
143 <p>LLVM provides many optimization passes, which do many different sorts of
144 things and have different tradeoffs. Unlike other systems, LLVM doesn't hold
145 to the mistaken notion that one set of optimizations is right for all languages
146 and for all situations. LLVM allows a compiler implementor to make complete
147 decisions about what optimizations to use, in which order, and in what
148 situation.</p>
151 across as large of body of code as they can (often a whole file, but if run
152 at link time, this can be a substantial portion of the whole program). It also
153 supports and includes "per-function" passes which just operate on a single
154 function at a time, without looking at other functions. For more information
159 <p>For Kaleidoscope, we are currently generating functions on the fly, one at
160 a time, as the user types them in. We aren't shooting for the ultimate
161 optimization experience in this setting, but we also want to catch the easy and
162 quick stuff where possible. As such, we will choose to run a few per-function
163 optimizations as the user types the function in. If we wanted to make a "static
164 Kaleidoscope compiler", we would use exactly the code we have now, except that
165 we would defer running the optimizer until the entire file has been parsed.</p>
167 <p>In order to get per-function optimizations going, we need to set up a
169 organize the LLVM optimizations that we want to run. Once we have that, we can
170 add a set of optimizations to run. The code looks like this:</p>
173 <pre>
174 FunctionPassManager OurFPM(TheModule);
176 // Set up the optimizer pipeline. Start with registering info about how the
177 // target lays out data structures.
178 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
179 // Do simple "peephole" optimizations and bit-twiddling optzns.
180 OurFPM.add(createInstructionCombiningPass());
181 // Reassociate expressions.
182 OurFPM.add(createReassociatePass());
183 // Eliminate Common SubExpressions.
184 OurFPM.add(createGVNPass());
185 // Simplify the control flow graph (deleting unreachable blocks, etc).
186 OurFPM.add(createCFGSimplificationPass());
188 OurFPM.doInitialization();
190 // Set the global so the code gen can use this.
191 TheFPM = &OurFPM;
193 // Run the main "interpreter loop" now.
194 MainLoop();
195 </pre>
196 </div>
200 up, we use a series of "add" calls to add a bunch of LLVM passes. The first
201 pass is basically boilerplate, it adds a pass so that later optimizations know
202 how the data structures in the program are laid out. The
203 "<tt>TheExecutionEngine</tt>" variable is related to the JIT, which we will get
204 to in the next section.</p>
207 here are a pretty standard set of "cleanup" optimizations that are useful for
208 a wide variety of code. I won't delve into what they do but, believe me,
209 they are a good starting place :).</p>
211 <p>Once the PassManager is set up, we need to make use of it. We do this by
212 running it after our newly created function is constructed (in
216 <pre>
217 if (Value *RetVal = Body->Codegen()) {
218 // Finish off the function.
219 Builder.CreateRet(RetVal);
221 // Validate the generated code, checking for consistency.
222 verifyFunction(*TheFunction);
224 <b>// Optimize the function.
227 return TheFunction;
228 }
229 </pre>
230 </div>
232 <p>As you can see, this is pretty straightforward. The
234 improving (hopefully) its body. With this in place, we can try our test above
235 again:</p>
238 <pre>
240 ready> Read function definition:
241 define double @test(double %x) {
242 entry:
243 %addtmp = fadd double %x, 3.000000e+00
244 %multmp = fmul double %addtmp, %addtmp
245 ret double %multmp
246 }
247 </pre>
248 </div>
250 <p>As expected, we now get our nicely optimized code, saving a floating point
251 add instruction from every execution of this function.</p>
253 <p>LLVM provides a wide variety of optimizations that can be used in certain
255 passes</a> is available, but it isn't very complete. Another good source of
258 experiment with passes from the command line, so you can see if they do
259 anything.</p>
261 <p>Now that we have reasonable code coming out of our front-end, lets talk about
262 executing it!</p>
264 </div>
266 <!-- *********************************************************************** -->
268 <!-- *********************************************************************** -->
272 <p>Code that is available in LLVM IR can have a wide variety of tools
273 applied to it. For example, you can run optimizations on it (as we did above),
274 you can dump it out in textual or binary forms, you can compile the code to an
275 assembly file (.s) for some target, or you can JIT compile it. The nice thing
276 about the LLVM IR representation is that it is the "common currency" between
277 many different parts of the compiler.
278 </p>
280 <p>In this section, we'll add JIT compiler support to our interpreter. The
281 basic idea that we want for Kaleidoscope is to have the user enter function
282 bodies as they do now, but immediately evaluate the top-level expressions they
283 type in. For example, if they type in "1 + 2;", we should evaluate and print
284 out 3. If they define a function, they should be able to call it from the
285 command line.</p>
287 <p>In order to do this, we first declare and initialize the JIT. This is done
291 <pre>
293 ...
294 int main() {
295 ..
296 <b>// Create the JIT. This takes ownership of the module.
297 TheExecutionEngine = EngineBuilder(TheModule).create();</b>
298 ..
299 }
300 </pre>
301 </div>
304 compiler or the LLVM interpreter. LLVM will automatically pick a JIT compiler
305 for you if one is available for your platform, otherwise it will fall back to
306 the interpreter.</p>
309 There are a variety of APIs that are useful, but the simplest one is the
310 "<tt>getPointerToFunction(F)</tt>" method. This method JIT compiles the
311 specified LLVM Function and returns a function pointer to the generated machine
312 code. In our case, this means that we can change the code that parses a
313 top-level expression to look like this:</p>
316 <pre>
317 static void HandleTopLevelExpression() {
318 // Evaluate a top-level expression into an anonymous function.
319 if (FunctionAST *F = ParseTopLevelExpr()) {
320 if (Function *LF = F->Codegen()) {
321 LF->dump(); // Dump the function for exposition purposes.
323 <b>// JIT the function, returning a function pointer.
324 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
326 // Cast it to the right type (takes no arguments, returns a double) so we
327 // can call it as a native function.
328 double (*FP)() = (double (*)())(intptr_t)FPtr;
330 }
331 </pre>
332 </div>
334 <p>Recall that we compile top-level expressions into a self-contained LLVM
335 function that takes no arguments and returns the computed double. Because the
336 LLVM JIT compiler matches the native platform ABI, this means that you can just
337 cast the result pointer to a function pointer of that type and call it directly.
338 This means, there is no difference between JIT compiled code and native machine
339 code that is statically linked into your application.</p>
344 <pre>
346 define double @""() {
347 entry:
348 ret double 9.000000e+00
349 }
352 </pre>
353 </div>
355 <p>Well this looks like it is basically working. The dump of the function
356 shows the "no argument function that always returns double" that we synthesize
357 for each top-level expression that is typed in. This demonstrates very basic
358 functionality, but can we do more?</p>
361 <pre>
363 Read function definition:
364 define double @testfunc(double %x, double %y) {
365 entry:
366 %multmp = fmul double %y, 2.000000e+00
367 %addtmp = fadd double %multmp, %x
368 ret double %addtmp
369 }
372 define double @""() {
373 entry:
375 ret double %calltmp
376 }
379 </pre>
380 </div>
382 <p>This illustrates that we can now call user code, but there is something a bit
383 subtle going on here. Note that we only invoke the JIT on the anonymous
386 scanned for all non-JIT'd functions transitively called from the anonymous
387 function and compiled all of them before returning
390 <p>The JIT provides a number of other more advanced interfaces for things like
391 freeing allocated machine code, rejit'ing functions to update them, etc.
392 However, even with this simple code, we get some surprisingly powerful
393 capabilities - check this out (I removed the dump of the anonymous functions,
394 you should get the idea by now :) :</p>
397 <pre>
399 Read extern:
400 declare double @sin(double)
403 Read extern:
404 declare double @cos(double)
410 Read function definition:
411 define double @foo(double %x) {
412 entry:
413 %calltmp = call double @sin(double %x)
414 %multmp = fmul double %calltmp, %calltmp
415 %calltmp2 = call double @cos(double %x)
416 %multmp4 = fmul double %calltmp2, %calltmp2
417 %addtmp = fadd double %multmp, %multmp4
418 ret double %addtmp
419 }
423 </pre>
424 </div>
426 <p>Whoa, how does the JIT know about sin and cos? The answer is surprisingly
427 simple: in this
428 example, the JIT started execution of a function and got to a function call. It
429 realized that the function was not yet JIT compiled and invoked the standard set
430 of routines to resolve the function. In this case, there is no body defined
432 Kaleidoscope process itself.
433 Since "<tt>sin</tt>" is defined within the JIT's address space, it simply
435 directly.</p>
437 <p>The LLVM JIT provides a number of interfaces (look in the
439 resolved. It allows you to establish explicit mappings between IR objects and
440 addresses (useful for LLVM global variables that you want to map to static
441 tables, for example), allows you to dynamically decide on the fly based on the
442 function name, and even allows you to have the JIT compile functions lazily the
443 first time they're called.</p>
445 <p>One interesting application of this is that we can now extend the language
446 by writing arbitrary C++ code to implement operations. For example, if we add:
447 </p>
450 <pre>
451 /// putchard - putchar that takes a double and returns 0.
452 extern "C"
453 double putchard(double X) {
454 putchar((char)X);
455 return 0;
456 }
457 </pre>
458 </div>
460 <p>Now we can produce simple output to the console by using things like:
461 "<tt>extern putchard(x); putchard(120);</tt>", which prints a lowercase 'x' on
462 the console (120 is the ASCII code for 'x'). Similar code could be used to
463 implement file I/O, console input, and many other capabilities in
464 Kaleidoscope.</p>
466 <p>This completes the JIT and optimizer chapter of the Kaleidoscope tutorial. At
467 this point, we can compile a non-Turing-complete programming language, optimize
468 and JIT compile it in a user-driven way. Next up we'll look into <a
470 tackling some interesting LLVM IR issues along the way.</p>
472 </div>
474 <!-- *********************************************************************** -->
476 <!-- *********************************************************************** -->
480 <p>
481 Here is the complete code listing for our running example, enhanced with the
482 LLVM JIT and optimizer. To build this example, use:
483 </p>
486 <pre>
487 # Compile
488 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
489 # Run
490 ./toy
491 </pre>
492 </div>
494 <p>
495 If you are compiling this on Linux, make sure to add the "-rdynamic" option
496 as well. This makes sure that the external functions are resolved properly
497 at runtime.</p>
502 <pre>
503 #include "llvm/DerivedTypes.h"
504 #include "llvm/ExecutionEngine/ExecutionEngine.h"
505 #include "llvm/ExecutionEngine/JIT.h"
506 #include "llvm/LLVMContext.h"
507 #include "llvm/Module.h"
508 #include "llvm/PassManager.h"
509 #include "llvm/Analysis/Verifier.h"
510 #include "llvm/Target/TargetData.h"
511 #include "llvm/Target/TargetSelect.h"
512 #include "llvm/Transforms/Scalar.h"
513 #include "llvm/Support/IRBuilder.h"
518 using namespace llvm;
520 //===----------------------------------------------------------------------===//
521 // Lexer
522 //===----------------------------------------------------------------------===//
525 // of these for known things.
526 enum Token {
527 tok_eof = -1,
529 // commands
532 // primary
534 };
536 static std::string IdentifierStr; // Filled in if tok_identifier
537 static double NumVal; // Filled in if tok_number
539 /// gettok - Return the next token from standard input.
540 static int gettok() {
541 static int LastChar = ' ';
543 // Skip any whitespace.
544 while (isspace(LastChar))
545 LastChar = getchar();
547 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
548 IdentifierStr = LastChar;
549 while (isalnum((LastChar = getchar())))
550 IdentifierStr += LastChar;
552 if (IdentifierStr == "def") return tok_def;
553 if (IdentifierStr == "extern") return tok_extern;
554 return tok_identifier;
555 }
558 std::string NumStr;
559 do {
560 NumStr += LastChar;
561 LastChar = getchar();
562 } while (isdigit(LastChar) || LastChar == '.');
564 NumVal = strtod(NumStr.c_str(), 0);
565 return tok_number;
566 }
568 if (LastChar == '#') {
569 // Comment until end of line.
570 do LastChar = getchar();
573 if (LastChar != EOF)
574 return gettok();
575 }
577 // Check for end of file. Don't eat the EOF.
578 if (LastChar == EOF)
579 return tok_eof;
581 // Otherwise, just return the character as its ascii value.
582 int ThisChar = LastChar;
583 LastChar = getchar();
584 return ThisChar;
585 }
587 //===----------------------------------------------------------------------===//
588 // Abstract Syntax Tree (aka Parse Tree)
589 //===----------------------------------------------------------------------===//
591 /// ExprAST - Base class for all expression nodes.
592 class ExprAST {
593 public:
594 virtual ~ExprAST() {}
595 virtual Value *Codegen() = 0;
596 };
598 /// NumberExprAST - Expression class for numeric literals like "1.0".
599 class NumberExprAST : public ExprAST {
600 double Val;
601 public:
602 NumberExprAST(double val) : Val(val) {}
603 virtual Value *Codegen();
604 };
606 /// VariableExprAST - Expression class for referencing a variable, like "a".
607 class VariableExprAST : public ExprAST {
608 std::string Name;
609 public:
610 VariableExprAST(const std::string &name) : Name(name) {}
611 virtual Value *Codegen();
612 };
614 /// BinaryExprAST - Expression class for a binary operator.
615 class BinaryExprAST : public ExprAST {
616 char Op;
617 ExprAST *LHS, *RHS;
618 public:
619 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
620 : Op(op), LHS(lhs), RHS(rhs) {}
621 virtual Value *Codegen();
622 };
624 /// CallExprAST - Expression class for function calls.
625 class CallExprAST : public ExprAST {
626 std::string Callee;
628 public:
630 : Callee(callee), Args(args) {}
631 virtual Value *Codegen();
632 };
634 /// PrototypeAST - This class represents the "prototype" for a function,
635 /// which captures its name, and its argument names (thus implicitly the number
636 /// of arguments the function takes).
637 class PrototypeAST {
638 std::string Name;
640 public:
642 : Name(name), Args(args) {}
644 Function *Codegen();
645 };
647 /// FunctionAST - This class represents a function definition itself.
648 class FunctionAST {
649 PrototypeAST *Proto;
650 ExprAST *Body;
651 public:
652 FunctionAST(PrototypeAST *proto, ExprAST *body)
653 : Proto(proto), Body(body) {}
655 Function *Codegen();
656 };
658 //===----------------------------------------------------------------------===//
659 // Parser
660 //===----------------------------------------------------------------------===//
662 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
663 /// token the parser is looking at. getNextToken reads another token from the
664 /// lexer and updates CurTok with its results.
665 static int CurTok;
666 static int getNextToken() {
667 return CurTok = gettok();
668 }
670 /// BinopPrecedence - This holds the precedence for each binary operator that is
671 /// defined.
674 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
675 static int GetTokPrecedence() {
676 if (!isascii(CurTok))
677 return -1;
679 // Make sure it's a declared binop.
680 int TokPrec = BinopPrecedence[CurTok];
682 return TokPrec;
683 }
685 /// Error* - These are little helper functions for error handling.
687 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
688 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
690 static ExprAST *ParseExpression();
692 /// identifierexpr
693 /// ::= identifier
694 /// ::= identifier '(' expression* ')'
695 static ExprAST *ParseIdentifierExpr() {
696 std::string IdName = IdentifierStr;
698 getNextToken(); // eat identifier.
700 if (CurTok != '(') // Simple variable ref.
701 return new VariableExprAST(IdName);
703 // Call.
704 getNextToken(); // eat (
706 if (CurTok != ')') {
707 while (1) {
708 ExprAST *Arg = ParseExpression();
709 if (!Arg) return 0;
710 Args.push_back(Arg);
712 if (CurTok == ')') break;
714 if (CurTok != ',')
715 return Error("Expected ')' or ',' in argument list");
716 getNextToken();
717 }
718 }
720 // Eat the ')'.
721 getNextToken();
723 return new CallExprAST(IdName, Args);
724 }
726 /// numberexpr ::= number
727 static ExprAST *ParseNumberExpr() {
728 ExprAST *Result = new NumberExprAST(NumVal);
729 getNextToken(); // consume the number
730 return Result;
731 }
733 /// parenexpr ::= '(' expression ')'
734 static ExprAST *ParseParenExpr() {
735 getNextToken(); // eat (.
736 ExprAST *V = ParseExpression();
737 if (!V) return 0;
739 if (CurTok != ')')
740 return Error("expected ')'");
741 getNextToken(); // eat ).
742 return V;
743 }
745 /// primary
746 /// ::= identifierexpr
747 /// ::= numberexpr
748 /// ::= parenexpr
749 static ExprAST *ParsePrimary() {
750 switch (CurTok) {
751 default: return Error("unknown token when expecting an expression");
752 case tok_identifier: return ParseIdentifierExpr();
753 case tok_number: return ParseNumberExpr();
754 case '(': return ParseParenExpr();
755 }
756 }
758 /// binoprhs
759 /// ::= ('+' primary)*
760 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
761 // If this is a binop, find its precedence.
762 while (1) {
763 int TokPrec = GetTokPrecedence();
765 // If this is a binop that binds at least as tightly as the current binop,
766 // consume it, otherwise we are done.
767 if (TokPrec < ExprPrec)
768 return LHS;
770 // Okay, we know this is a binop.
771 int BinOp = CurTok;
772 getNextToken(); // eat binop
774 // Parse the primary expression after the binary operator.
775 ExprAST *RHS = ParsePrimary();
776 if (!RHS) return 0;
778 // If BinOp binds less tightly with RHS than the operator after RHS, let
779 // the pending operator take RHS as its LHS.
780 int NextPrec = GetTokPrecedence();
781 if (TokPrec < NextPrec) {
782 RHS = ParseBinOpRHS(TokPrec+1, RHS);
784 }
786 // Merge LHS/RHS.
787 LHS = new BinaryExprAST(BinOp, LHS, RHS);
788 }
789 }
791 /// expression
792 /// ::= primary binoprhs
793 ///
794 static ExprAST *ParseExpression() {
795 ExprAST *LHS = ParsePrimary();
796 if (!LHS) return 0;
798 return ParseBinOpRHS(0, LHS);
799 }
801 /// prototype
802 /// ::= id '(' id* ')'
803 static PrototypeAST *ParsePrototype() {
804 if (CurTok != tok_identifier)
805 return ErrorP("Expected function name in prototype");
807 std::string FnName = IdentifierStr;
808 getNextToken();
810 if (CurTok != '(')
811 return ErrorP("Expected '(' in prototype");
814 while (getNextToken() == tok_identifier)
815 ArgNames.push_back(IdentifierStr);
816 if (CurTok != ')')
817 return ErrorP("Expected ')' in prototype");
819 // success.
820 getNextToken(); // eat ')'.
822 return new PrototypeAST(FnName, ArgNames);
823 }
825 /// definition ::= 'def' prototype expression
826 static FunctionAST *ParseDefinition() {
827 getNextToken(); // eat def.
828 PrototypeAST *Proto = ParsePrototype();
831 if (ExprAST *E = ParseExpression())
832 return new FunctionAST(Proto, E);
833 return 0;
834 }
836 /// toplevelexpr ::= expression
837 static FunctionAST *ParseTopLevelExpr() {
838 if (ExprAST *E = ParseExpression()) {
839 // Make an anonymous proto.
841 return new FunctionAST(Proto, E);
842 }
843 return 0;
844 }
846 /// external ::= 'extern' prototype
847 static PrototypeAST *ParseExtern() {
848 getNextToken(); // eat extern.
849 return ParsePrototype();
850 }
852 //===----------------------------------------------------------------------===//
853 // Code Generation
854 //===----------------------------------------------------------------------===//
856 static Module *TheModule;
857 static IRBuilder<> Builder(getGlobalContext());
859 static FunctionPassManager *TheFPM;
861 Value *ErrorV(const char *Str) { Error(Str); return 0; }
863 Value *NumberExprAST::Codegen() {
864 return ConstantFP::get(getGlobalContext(), APFloat(Val));
865 }
867 Value *VariableExprAST::Codegen() {
868 // Look this variable up in the function.
869 Value *V = NamedValues[Name];
870 return V ? V : ErrorV("Unknown variable name");
871 }
873 Value *BinaryExprAST::Codegen() {
874 Value *L = LHS->Codegen();
875 Value *R = RHS->Codegen();
878 switch (Op) {
879 case '+': return Builder.CreateFAdd(L, R, "addtmp");
880 case '-': return Builder.CreateFSub(L, R, "subtmp");
881 case '*': return Builder.CreateFMul(L, R, "multmp");
882 case '<':
883 L = Builder.CreateFCmpULT(L, R, "cmptmp");
885 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
886 "booltmp");
887 default: return ErrorV("invalid binary operator");
888 }
889 }
891 Value *CallExprAST::Codegen() {
892 // Look up the name in the global module table.
893 Function *CalleeF = TheModule->getFunction(Callee);
894 if (CalleeF == 0)
895 return ErrorV("Unknown function referenced");
897 // If argument mismatch error.
898 if (CalleeF->arg_size() != Args.size())
899 return ErrorV("Incorrect # arguments passed");
902 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
903 ArgsV.push_back(Args[i]->Codegen());
905 }
907 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
908 }
910 Function *PrototypeAST::Codegen() {
911 // Make the function type: double(double,double) etc.
913 Type::getDoubleTy(getGlobalContext()));
914 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
915 Doubles, false);
917 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
919 // If F conflicted, there was already something named 'Name'. If it has a
920 // body, don't allow redefinition or reextern.
921 if (F->getName() != Name) {
922 // Delete the one we just made and get the existing one.
923 F->eraseFromParent();
924 F = TheModule->getFunction(Name);
926 // If F already has a body, reject this.
927 if (!F->empty()) {
928 ErrorF("redefinition of function");
929 return 0;
930 }
932 // If F took a different number of args, reject.
933 if (F->arg_size() != Args.size()) {
934 ErrorF("redefinition of function with different # args");
935 return 0;
936 }
937 }
939 // Set names for all arguments.
940 unsigned Idx = 0;
941 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
942 ++AI, ++Idx) {
943 AI->setName(Args[Idx]);
945 // Add arguments to variable symbol table.
946 NamedValues[Args[Idx]] = AI;
947 }
949 return F;
950 }
952 Function *FunctionAST::Codegen() {
953 NamedValues.clear();
955 Function *TheFunction = Proto->Codegen();
956 if (TheFunction == 0)
957 return 0;
959 // Create a new basic block to start insertion into.
960 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
961 Builder.SetInsertPoint(BB);
963 if (Value *RetVal = Body->Codegen()) {
964 // Finish off the function.
965 Builder.CreateRet(RetVal);
967 // Validate the generated code, checking for consistency.
968 verifyFunction(*TheFunction);
970 // Optimize the function.
971 TheFPM->run(*TheFunction);
973 return TheFunction;
974 }
976 // Error reading body, remove function.
977 TheFunction->eraseFromParent();
978 return 0;
979 }
981 //===----------------------------------------------------------------------===//
982 // Top-Level parsing and JIT Driver
983 //===----------------------------------------------------------------------===//
985 static ExecutionEngine *TheExecutionEngine;
987 static void HandleDefinition() {
988 if (FunctionAST *F = ParseDefinition()) {
989 if (Function *LF = F->Codegen()) {
990 fprintf(stderr, "Read function definition:");
991 LF->dump();
992 }
993 } else {
994 // Skip token for error recovery.
995 getNextToken();
996 }
997 }
999 static void HandleExtern() {
1000 if (PrototypeAST *P = ParseExtern()) {
1001 if (Function *F = P->Codegen()) {
1002 fprintf(stderr, "Read extern: ");
1003 F->dump();
1004 }
1005 } else {
1006 // Skip token for error recovery.
1007 getNextToken();
1008 }
1009 }
1011 static void HandleTopLevelExpression() {
1012 // Evaluate a top-level expression into an anonymous function.
1013 if (FunctionAST *F = ParseTopLevelExpr()) {
1014 if (Function *LF = F->Codegen()) {
1015 // JIT the function, returning a function pointer.
1016 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1018 // Cast it to the right type (takes no arguments, returns a double) so we
1019 // can call it as a native function.
1020 double (*FP)() = (double (*)())(intptr_t)FPtr;
1021 fprintf(stderr, "Evaluated to %f\n", FP());
1022 }
1023 } else {
1024 // Skip token for error recovery.
1025 getNextToken();
1026 }
1027 }
1029 /// top ::= definition | external | expression | ';'
1030 static void MainLoop() {
1031 while (1) {
1032 fprintf(stderr, "ready> ");
1033 switch (CurTok) {
1034 case tok_eof: return;
1035 case ';': getNextToken(); break; // ignore top-level semicolons.
1036 case tok_def: HandleDefinition(); break;
1037 case tok_extern: HandleExtern(); break;
1038 default: HandleTopLevelExpression(); break;
1039 }
1040 }
1041 }
1043 //===----------------------------------------------------------------------===//
1045 //===----------------------------------------------------------------------===//
1047 /// putchard - putchar that takes a double and returns 0.
1048 extern "C"
1049 double putchard(double X) {
1050 putchar((char)X);
1051 return 0;
1052 }
1054 //===----------------------------------------------------------------------===//
1055 // Main driver code.
1056 //===----------------------------------------------------------------------===//
1058 int main() {
1059 InitializeNativeTarget();
1060 LLVMContext &Context = getGlobalContext();
1062 // Install standard binary operators.
1063 // 1 is lowest precedence.
1065 BinopPrecedence['+'] = 20;
1066 BinopPrecedence['-'] = 20;
1067 BinopPrecedence['*'] = 40; // highest.
1069 // Prime the first token.
1070 fprintf(stderr, "ready> ");
1071 getNextToken();
1073 // Make the module, which holds all the code.
1074 TheModule = new Module("my cool jit", Context);
1076 // Create the JIT. This takes ownership of the module.
1077 std::string ErrStr;
1078 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
1079 if (!TheExecutionEngine) {
1080 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1081 exit(1);
1082 }
1084 FunctionPassManager OurFPM(TheModule);
1086 // Set up the optimizer pipeline. Start with registering info about how the
1087 // target lays out data structures.
1088 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1089 // Do simple "peephole" optimizations and bit-twiddling optzns.
1090 OurFPM.add(createInstructionCombiningPass());
1091 // Reassociate expressions.
1092 OurFPM.add(createReassociatePass());
1093 // Eliminate Common SubExpressions.
1094 OurFPM.add(createGVNPass());
1095 // Simplify the control flow graph (deleting unreachable blocks, etc).
1096 OurFPM.add(createCFGSimplificationPass());
1098 OurFPM.doInitialization();
1100 // Set the global so the code gen can use this.
1101 TheFPM = &OurFPM;
1103 // Run the main "interpreter loop" now.
1104 MainLoop();
1106 TheFPM = 0;
1108 // Print out all of the generated code.
1109 TheModule->dump();
1111 return 0;
1112 }
1113 </pre>
1114 </div>
1117 </div>
1119 <!-- *********************************************************************** -->
1120 <hr>
1121 <address>
1129 Last modified: $Date$
1130 </address>
1131 </body>
1132 </html>