| blob | 5a41f51fd6c15bccaf6ab8b0cbebeb5302bd861c |
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. For example, when compiling simple code,
60 we don't get obvious optimizations:</p>
63 <pre>
65 Read function definition:
66 define double @test(double %x) {
67 entry:
69 %addtmp1 = add double %addtmp, %x
70 ret double %addtmp1
71 }
72 </pre>
73 </div>
75 <p>This code is a very, very literal transcription of the AST built by parsing
76 the input. As such, this transcription lacks optimizations like constant folding (we'd like to get "<tt>add x, 3.0</tt>" in the example above) as well as other more important
77 optimizations. Constant folding, in particular, is a very common and very
78 important optimization: so much so that many language implementors implement
79 constant folding support in their AST representation.</p>
81 <p>With LLVM, you don't need this support in the AST. Since all calls to build LLVM IR go through
82 the LLVM builder, it would be nice if the builder itself checked to see if there
83 was a constant folding opportunity when you call it. If so, it could just do
84 the constant fold and return the constant instead of creating an instruction.
86 change:
89 <pre>
90 static LLVMFoldingBuilder Builder;
91 </pre>
92 </div>
96 instructions implicitly constant folded without us having to do anything
97 about it. For example, the input above now compiles to:</p>
100 <pre>
102 Read function definition:
103 define double @test(double %x) {
104 entry:
105 %addtmp = add double 3.000000e+00, %x
106 ret double %addtmp
107 }
108 </pre>
109 </div>
111 <p>Well, that was easy :). In practice, we recommend always using
113 "syntactic overhead" for its use (you don't have to uglify your compiler with
114 constant checks everywhere) and it can dramatically reduce the amount of
115 LLVM IR that is generated in some cases (particular for languages with a macro
116 preprocessor or that use a lot of constants).</p>
119 that it does all of its analysis inline with the code as it is built. If you
120 take a slightly more complex example:</p>
123 <pre>
125 ready> Read function definition:
126 define double @test(double %x) {
127 entry:
128 %addtmp = add double 3.000000e+00, %x
129 %addtmp1 = add double %x, 3.000000e+00
130 %multmp = mul double %addtmp, %addtmp1
131 ret double %multmp
132 }
133 </pre>
134 </div>
136 <p>In this case, the LHS and RHS of the multiplication are the same value. We'd
137 really like to see this generate "<tt>tmp = x+3; result = tmp*tmp;</tt>" instead
140 <p>Unfortunately, no amount of local analysis will be able to detect and correct
141 this. This requires two transformations: reassociation of expressions (to
142 make the add's lexically identical) and Common Subexpression Elimination (CSE)
143 to delete the redundant add instruction. Fortunately, LLVM provides a broad
146 </div>
148 <!-- *********************************************************************** -->
150 Passes</a></div>
151 <!-- *********************************************************************** -->
155 <p>LLVM provides many optimization passes, which do many different sorts of
156 things and have different tradeoffs. Unlike other systems, LLVM doesn't hold
157 to the mistaken notion that one set of optimizations is right for all languages
158 and for all situations. LLVM allows a compiler implementor to make complete
159 decisions about what optimizations to use, in which order, and in what
160 situation.</p>
163 across as large of body of code as they can (often a whole file, but if run
164 at link time, this can be a substantial portion of the whole program). It also
165 supports and includes "per-function" passes which just operate on a single
166 function at a time, without looking at other functions. For more information
171 <p>For Kaleidoscope, we are currently generating functions on the fly, one at
172 a time, as the user types them in. We aren't shooting for the ultimate
173 optimization experience in this setting, but we also want to catch the easy and
174 quick stuff where possible. As such, we will choose to run a few per-function
175 optimizations as the user types the function in. If we wanted to make a "static
176 Kaleidoscope compiler", we would use exactly the code we have now, except that
177 we would defer running the optimizer until the entire file has been parsed.</p>
179 <p>In order to get per-function optimizations going, we need to set up a
181 organize the LLVM optimizations that we want to run. Once we have that, we can
182 add a set of optimizations to run. The code looks like this:</p>
185 <pre>
186 ExistingModuleProvider OurModuleProvider(TheModule);
187 FunctionPassManager OurFPM(&OurModuleProvider);
189 // Set up the optimizer pipeline. Start with registering info about how the
190 // target lays out data structures.
191 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
192 // Do simple "peephole" optimizations and bit-twiddling optzns.
193 OurFPM.add(createInstructionCombiningPass());
194 // Reassociate expressions.
195 OurFPM.add(createReassociatePass());
196 // Eliminate Common SubExpressions.
197 OurFPM.add(createGVNPass());
198 // Simplify the control flow graph (deleting unreachable blocks, etc).
199 OurFPM.add(createCFGSimplificationPass());
201 // Set the global so the code gen can use this.
202 TheFPM = &OurFPM;
204 // Run the main "interpreter loop" now.
205 MainLoop();
206 </pre>
207 </div>
212 that we're not going to take advantage of here, so I won't dive into any details
213 about it.</p>
217 to construct itself. Once it is set up, we use a series of "add" calls to add
218 a bunch of LLVM passes. The first pass is basically boilerplate, it adds a pass
219 so that later optimizations know how the data structures in the program are
220 layed out. The "<tt>TheExecutionEngine</tt>" variable is related to the JIT,
221 which we will get to in the next section.</p>
224 here are a pretty standard set of "cleanup" optimizations that are useful for
225 a wide variety of code. I won't delve into what they do but, believe me,
226 they are a good starting place :).</p>
228 <p>Once the PassManager is set up, we need to make use of it. We do this by
229 running it after our newly created function is constructed (in
233 <pre>
234 if (Value *RetVal = Body->Codegen()) {
235 // Finish off the function.
236 Builder.CreateRet(RetVal);
238 // Validate the generated code, checking for consistency.
239 verifyFunction(*TheFunction);
241 <b>// Optimize the function.
244 return TheFunction;
245 }
246 </pre>
247 </div>
249 <p>As you can see, this is pretty straightforward. The
251 improving (hopefully) its body. With this in place, we can try our test above
252 again:</p>
255 <pre>
257 ready> Read function definition:
258 define double @test(double %x) {
259 entry:
260 %addtmp = add double %x, 3.000000e+00
261 %multmp = mul double %addtmp, %addtmp
262 ret double %multmp
263 }
264 </pre>
265 </div>
267 <p>As expected, we now get our nicely optimized code, saving a floating point
268 add instruction from every execution of this function.</p>
270 <p>LLVM provides a wide variety of optimizations that can be used in certain
272 passes</a> is available, but it isn't very complete. Another good source of
275 experiment with passes from the command line, so you can see if they do
276 anything.</p>
278 <p>Now that we have reasonable code coming out of our front-end, lets talk about
279 executing it!</p>
281 </div>
283 <!-- *********************************************************************** -->
285 <!-- *********************************************************************** -->
289 <p>Code that is available in LLVM IR can have a wide variety of tools
290 applied to it. For example, you can run optimizations on it (as we did above),
291 you can dump it out in textual or binary forms, you can compile the code to an
292 assembly file (.s) for some target, or you can JIT compile it. The nice thing
293 about the LLVM IR representation is that it is the "common currency" between
294 many different parts of the compiler.
295 </p>
297 <p>In this section, we'll add JIT compiler support to our interpreter. The
298 basic idea that we want for Kaleidoscope is to have the user enter function
299 bodies as they do now, but immediately evaluate the top-level expressions they
300 type in. For example, if they type in "1 + 2;", we should evaluate and print
301 out 3. If they define a function, they should be able to call it from the
302 command line.</p>
304 <p>In order to do this, we first declare and initialize the JIT. This is done
308 <pre>
310 ...
311 int main() {
312 ..
313 <b>// Create the JIT.
314 TheExecutionEngine = ExecutionEngine::create(TheModule);</b>
315 ..
316 }
317 </pre>
318 </div>
321 compiler or the LLVM interpreter. LLVM will automatically pick a JIT compiler
322 for you if one is available for your platform, otherwise it will fall back to
323 the interpreter.</p>
326 There are a variety of APIs that are useful, but the simplest one is the
327 "<tt>getPointerToFunction(F)</tt>" method. This method JIT compiles the
328 specified LLVM Function and returns a function pointer to the generated machine
329 code. In our case, this means that we can change the code that parses a
330 top-level expression to look like this:</p>
333 <pre>
334 static void HandleTopLevelExpression() {
335 // Evaluate a top level expression into an anonymous function.
336 if (FunctionAST *F = ParseTopLevelExpr()) {
337 if (Function *LF = F->Codegen()) {
338 LF->dump(); // Dump the function for exposition purposes.
340 <b>// JIT the function, returning a function pointer.
341 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
343 // Cast it to the right type (takes no arguments, returns a double) so we
344 // can call it as a native function.
345 double (*FP)() = (double (*)())FPtr;
347 }
348 </pre>
349 </div>
351 <p>Recall that we compile top-level expressions into a self-contained LLVM
352 function that takes no arguments and returns the computed double. Because the
353 LLVM JIT compiler matches the native platform ABI, this means that you can just
354 cast the result pointer to a function pointer of that type and call it directly.
355 This means, there is no difference between JIT compiled code and native machine
356 code that is statically linked into your application.</p>
361 <pre>
363 define double @""() {
364 entry:
365 ret double 9.000000e+00
366 }
369 </pre>
370 </div>
372 <p>Well this looks like it is basically working. The dump of the function
373 shows the "no argument function that always returns double" that we synthesize
374 for each top level expression that is typed in. This demonstrates very basic
375 functionality, but can we do more?</p>
378 <pre>
380 Read function definition:
381 define double @testfunc(double %x, double %y) {
382 entry:
383 %multmp = mul double %y, 2.000000e+00
384 %addtmp = add double %multmp, %x
385 ret double %addtmp
386 }
389 define double @""() {
390 entry:
392 ret double %calltmp
393 }
396 </pre>
397 </div>
399 <p>This illustrates that we can now call user code, but there is something a bit subtle
400 going on here. Note that we only invoke the JIT on the anonymous functions
404 <p>What actually happened here is that the anonymous function was
405 JIT'd when requested. When the Kaleidoscope app calls through the function
406 pointer that is returned, the anonymous function starts executing. It ends up
407 making the call to the "testfunc" function, and ends up in a stub that invokes
408 the JIT, lazily, on testfunc. Once the JIT finishes lazily compiling testfunc,
409 it returns and the code re-executes the call.</p>
411 <p>In summary, the JIT will lazily JIT code, on the fly, as it is needed. The
412 JIT provides a number of other more advanced interfaces for things like freeing
413 allocated machine code, rejit'ing functions to update them, etc. However, even
414 with this simple code, we get some surprisingly powerful capabilities - check
415 this out (I removed the dump of the anonymous functions, you should get the idea
416 by now :) :</p>
419 <pre>
421 Read extern:
422 declare double @sin(double)
425 Read extern:
426 declare double @cos(double)
432 Read function definition:
433 define double @foo(double %x) {
434 entry:
435 %calltmp = call double @sin( double %x )
436 %multmp = mul double %calltmp, %calltmp
437 %calltmp2 = call double @cos( double %x )
438 %multmp4 = mul double %calltmp2, %calltmp2
439 %addtmp = add double %multmp, %multmp4
440 ret double %addtmp
441 }
445 </pre>
446 </div>
448 <p>Whoa, how does the JIT know about sin and cos? The answer is surprisingly
449 simple: in this
450 example, the JIT started execution of a function and got to a function call. It
451 realized that the function was not yet JIT compiled and invoked the standard set
452 of routines to resolve the function. In this case, there is no body defined
454 Kaleidoscope process itself.
455 Since "<tt>sin</tt>" is defined within the JIT's address space, it simply
457 directly.</p>
459 <p>The LLVM JIT provides a number of interfaces (look in the
461 resolved. It allows you to establish explicit mappings between IR objects and
462 addresses (useful for LLVM global variables that you want to map to static
463 tables, for example), allows you to dynamically decide on the fly based on the
464 function name, and even allows you to have the JIT abort itself if any lazy
465 compilation is attempted.</p>
467 <p>One interesting application of this is that we can now extend the language
468 by writing arbitrary C++ code to implement operations. For example, if we add:
469 </p>
472 <pre>
473 /// putchard - putchar that takes a double and returns 0.
474 extern "C"
475 double putchard(double X) {
476 putchar((char)X);
477 return 0;
478 }
479 </pre>
480 </div>
482 <p>Now we can produce simple output to the console by using things like:
483 "<tt>extern putchard(x); putchard(120);</tt>", which prints a lowercase 'x' on
484 the console (120 is the ASCII code for 'x'). Similar code could be used to
485 implement file I/O, console input, and many other capabilities in
486 Kaleidoscope.</p>
488 <p>This completes the JIT and optimizer chapter of the Kaleidoscope tutorial. At
489 this point, we can compile a non-Turing-complete programming language, optimize
490 and JIT compile it in a user-driven way. Next up we'll look into <a
492 tackling some interesting LLVM IR issues along the way.</p>
494 </div>
496 <!-- *********************************************************************** -->
498 <!-- *********************************************************************** -->
502 <p>
503 Here is the complete code listing for our running example, enhanced with the
504 LLVM JIT and optimizer. To build this example, use:
505 </p>
508 <pre>
509 # Compile
510 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
511 # Run
512 ./toy
513 </pre>
514 </div>
519 <pre>
520 #include "llvm/DerivedTypes.h"
521 #include "llvm/ExecutionEngine/ExecutionEngine.h"
522 #include "llvm/Module.h"
523 #include "llvm/ModuleProvider.h"
524 #include "llvm/PassManager.h"
525 #include "llvm/Analysis/Verifier.h"
526 #include "llvm/Target/TargetData.h"
527 #include "llvm/Transforms/Scalar.h"
528 #include "llvm/Support/LLVMBuilder.h"
533 using namespace llvm;
535 //===----------------------------------------------------------------------===//
536 // Lexer
537 //===----------------------------------------------------------------------===//
540 // of these for known things.
541 enum Token {
542 tok_eof = -1,
544 // commands
547 // primary
549 };
551 static std::string IdentifierStr; // Filled in if tok_identifier
552 static double NumVal; // Filled in if tok_number
554 /// gettok - Return the next token from standard input.
555 static int gettok() {
556 static int LastChar = ' ';
558 // Skip any whitespace.
559 while (isspace(LastChar))
560 LastChar = getchar();
562 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
563 IdentifierStr = LastChar;
564 while (isalnum((LastChar = getchar())))
565 IdentifierStr += LastChar;
567 if (IdentifierStr == "def") return tok_def;
568 if (IdentifierStr == "extern") return tok_extern;
569 return tok_identifier;
570 }
573 std::string NumStr;
574 do {
575 NumStr += LastChar;
576 LastChar = getchar();
577 } while (isdigit(LastChar) || LastChar == '.');
579 NumVal = strtod(NumStr.c_str(), 0);
580 return tok_number;
581 }
583 if (LastChar == '#') {
584 // Comment until end of line.
585 do LastChar = getchar();
588 if (LastChar != EOF)
589 return gettok();
590 }
592 // Check for end of file. Don't eat the EOF.
593 if (LastChar == EOF)
594 return tok_eof;
596 // Otherwise, just return the character as its ascii value.
597 int ThisChar = LastChar;
598 LastChar = getchar();
599 return ThisChar;
600 }
602 //===----------------------------------------------------------------------===//
603 // Abstract Syntax Tree (aka Parse Tree)
604 //===----------------------------------------------------------------------===//
606 /// ExprAST - Base class for all expression nodes.
607 class ExprAST {
608 public:
609 virtual ~ExprAST() {}
610 virtual Value *Codegen() = 0;
611 };
613 /// NumberExprAST - Expression class for numeric literals like "1.0".
614 class NumberExprAST : public ExprAST {
615 double Val;
616 public:
617 NumberExprAST(double val) : Val(val) {}
618 virtual Value *Codegen();
619 };
621 /// VariableExprAST - Expression class for referencing a variable, like "a".
622 class VariableExprAST : public ExprAST {
623 std::string Name;
624 public:
625 VariableExprAST(const std::string &name) : Name(name) {}
626 virtual Value *Codegen();
627 };
629 /// BinaryExprAST - Expression class for a binary operator.
630 class BinaryExprAST : public ExprAST {
631 char Op;
632 ExprAST *LHS, *RHS;
633 public:
634 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
635 : Op(op), LHS(lhs), RHS(rhs) {}
636 virtual Value *Codegen();
637 };
639 /// CallExprAST - Expression class for function calls.
640 class CallExprAST : public ExprAST {
641 std::string Callee;
643 public:
645 : Callee(callee), Args(args) {}
646 virtual Value *Codegen();
647 };
649 /// PrototypeAST - This class represents the "prototype" for a function,
650 /// which captures its argument names as well as if it is an operator.
651 class PrototypeAST {
652 std::string Name;
654 public:
656 : Name(name), Args(args) {}
658 Function *Codegen();
659 };
661 /// FunctionAST - This class represents a function definition itself.
662 class FunctionAST {
663 PrototypeAST *Proto;
664 ExprAST *Body;
665 public:
666 FunctionAST(PrototypeAST *proto, ExprAST *body)
667 : Proto(proto), Body(body) {}
669 Function *Codegen();
670 };
672 //===----------------------------------------------------------------------===//
673 // Parser
674 //===----------------------------------------------------------------------===//
676 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
677 /// token the parser it looking at. getNextToken reads another token from the
678 /// lexer and updates CurTok with its results.
679 static int CurTok;
680 static int getNextToken() {
681 return CurTok = gettok();
682 }
684 /// BinopPrecedence - This holds the precedence for each binary operator that is
685 /// defined.
688 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
689 static int GetTokPrecedence() {
690 if (!isascii(CurTok))
691 return -1;
693 // Make sure it's a declared binop.
694 int TokPrec = BinopPrecedence[CurTok];
696 return TokPrec;
697 }
699 /// Error* - These are little helper functions for error handling.
701 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
702 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
704 static ExprAST *ParseExpression();
706 /// identifierexpr
707 /// ::= identifier
708 /// ::= identifier '(' expression* ')'
709 static ExprAST *ParseIdentifierExpr() {
710 std::string IdName = IdentifierStr;
712 getNextToken(); // eat identifier.
714 if (CurTok != '(') // Simple variable ref.
715 return new VariableExprAST(IdName);
717 // Call.
718 getNextToken(); // eat (
720 if (CurTok != ')') {
721 while (1) {
722 ExprAST *Arg = ParseExpression();
723 if (!Arg) return 0;
724 Args.push_back(Arg);
726 if (CurTok == ')') break;
728 if (CurTok != ',')
729 return Error("Expected ')'");
730 getNextToken();
731 }
732 }
734 // Eat the ')'.
735 getNextToken();
737 return new CallExprAST(IdName, Args);
738 }
740 /// numberexpr ::= number
741 static ExprAST *ParseNumberExpr() {
742 ExprAST *Result = new NumberExprAST(NumVal);
743 getNextToken(); // consume the number
744 return Result;
745 }
747 /// parenexpr ::= '(' expression ')'
748 static ExprAST *ParseParenExpr() {
749 getNextToken(); // eat (.
750 ExprAST *V = ParseExpression();
751 if (!V) return 0;
753 if (CurTok != ')')
754 return Error("expected ')'");
755 getNextToken(); // eat ).
756 return V;
757 }
759 /// primary
760 /// ::= identifierexpr
761 /// ::= numberexpr
762 /// ::= parenexpr
763 static ExprAST *ParsePrimary() {
764 switch (CurTok) {
765 default: return Error("unknown token when expecting an expression");
766 case tok_identifier: return ParseIdentifierExpr();
767 case tok_number: return ParseNumberExpr();
768 case '(': return ParseParenExpr();
769 }
770 }
772 /// binoprhs
773 /// ::= ('+' primary)*
774 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
775 // If this is a binop, find its precedence.
776 while (1) {
777 int TokPrec = GetTokPrecedence();
779 // If this is a binop that binds at least as tightly as the current binop,
780 // consume it, otherwise we are done.
781 if (TokPrec < ExprPrec)
782 return LHS;
784 // Okay, we know this is a binop.
785 int BinOp = CurTok;
786 getNextToken(); // eat binop
788 // Parse the primary expression after the binary operator.
789 ExprAST *RHS = ParsePrimary();
790 if (!RHS) return 0;
792 // If BinOp binds less tightly with RHS than the operator after RHS, let
793 // the pending operator take RHS as its LHS.
794 int NextPrec = GetTokPrecedence();
795 if (TokPrec < NextPrec) {
796 RHS = ParseBinOpRHS(TokPrec+1, RHS);
798 }
800 // Merge LHS/RHS.
801 LHS = new BinaryExprAST(BinOp, LHS, RHS);
802 }
803 }
805 /// expression
806 /// ::= primary binoprhs
807 ///
808 static ExprAST *ParseExpression() {
809 ExprAST *LHS = ParsePrimary();
810 if (!LHS) return 0;
812 return ParseBinOpRHS(0, LHS);
813 }
815 /// prototype
816 /// ::= id '(' id* ')'
817 static PrototypeAST *ParsePrototype() {
818 if (CurTok != tok_identifier)
819 return ErrorP("Expected function name in prototype");
821 std::string FnName = IdentifierStr;
822 getNextToken();
824 if (CurTok != '(')
825 return ErrorP("Expected '(' in prototype");
828 while (getNextToken() == tok_identifier)
829 ArgNames.push_back(IdentifierStr);
830 if (CurTok != ')')
831 return ErrorP("Expected ')' in prototype");
833 // success.
834 getNextToken(); // eat ')'.
836 return new PrototypeAST(FnName, ArgNames);
837 }
839 /// definition ::= 'def' prototype expression
840 static FunctionAST *ParseDefinition() {
841 getNextToken(); // eat def.
842 PrototypeAST *Proto = ParsePrototype();
845 if (ExprAST *E = ParseExpression())
846 return new FunctionAST(Proto, E);
847 return 0;
848 }
850 /// toplevelexpr ::= expression
851 static FunctionAST *ParseTopLevelExpr() {
852 if (ExprAST *E = ParseExpression()) {
853 // Make an anonymous proto.
855 return new FunctionAST(Proto, E);
856 }
857 return 0;
858 }
860 /// external ::= 'extern' prototype
861 static PrototypeAST *ParseExtern() {
862 getNextToken(); // eat extern.
863 return ParsePrototype();
864 }
866 //===----------------------------------------------------------------------===//
867 // Code Generation
868 //===----------------------------------------------------------------------===//
870 static Module *TheModule;
871 static LLVMFoldingBuilder Builder;
873 static FunctionPassManager *TheFPM;
875 Value *ErrorV(const char *Str) { Error(Str); return 0; }
877 Value *NumberExprAST::Codegen() {
878 return ConstantFP::get(Type::DoubleTy, APFloat(Val));
879 }
881 Value *VariableExprAST::Codegen() {
882 // Look this variable up in the function.
883 Value *V = NamedValues[Name];
884 return V ? V : ErrorV("Unknown variable name");
885 }
887 Value *BinaryExprAST::Codegen() {
888 Value *L = LHS->Codegen();
889 Value *R = RHS->Codegen();
892 switch (Op) {
893 case '+': return Builder.CreateAdd(L, R, "addtmp");
894 case '-': return Builder.CreateSub(L, R, "subtmp");
895 case '*': return Builder.CreateMul(L, R, "multmp");
896 case '<':
897 L = Builder.CreateFCmpULT(L, R, "cmptmp");
899 return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
900 default: return ErrorV("invalid binary operator");
901 }
902 }
904 Value *CallExprAST::Codegen() {
905 // Look up the name in the global module table.
906 Function *CalleeF = TheModule->getFunction(Callee);
907 if (CalleeF == 0)
908 return ErrorV("Unknown function referenced");
910 // If argument mismatch error.
911 if (CalleeF->arg_size() != Args.size())
912 return ErrorV("Incorrect # arguments passed");
915 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
916 ArgsV.push_back(Args[i]->Codegen());
918 }
920 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
921 }
923 Function *PrototypeAST::Codegen() {
924 // Make the function type: double(double,double) etc.
926 FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
928 Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
930 // If F conflicted, there was already something named 'Name'. If it has a
931 // body, don't allow redefinition or reextern.
932 if (F->getName() != Name) {
933 // Delete the one we just made and get the existing one.
934 F->eraseFromParent();
935 F = TheModule->getFunction(Name);
937 // If F already has a body, reject this.
938 if (!F->empty()) {
939 ErrorF("redefinition of function");
940 return 0;
941 }
943 // If F took a different number of args, reject.
944 if (F->arg_size() != Args.size()) {
945 ErrorF("redefinition of function with different # args");
946 return 0;
947 }
948 }
950 // Set names for all arguments.
951 unsigned Idx = 0;
952 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
953 ++AI, ++Idx) {
954 AI->setName(Args[Idx]);
956 // Add arguments to variable symbol table.
957 NamedValues[Args[Idx]] = AI;
958 }
960 return F;
961 }
963 Function *FunctionAST::Codegen() {
964 NamedValues.clear();
966 Function *TheFunction = Proto->Codegen();
967 if (TheFunction == 0)
968 return 0;
970 // Create a new basic block to start insertion into.
971 BasicBlock *BB = new BasicBlock("entry", TheFunction);
972 Builder.SetInsertPoint(BB);
974 if (Value *RetVal = Body->Codegen()) {
975 // Finish off the function.
976 Builder.CreateRet(RetVal);
978 // Validate the generated code, checking for consistency.
979 verifyFunction(*TheFunction);
981 // Optimize the function.
982 TheFPM->run(*TheFunction);
984 return TheFunction;
985 }
987 // Error reading body, remove function.
988 TheFunction->eraseFromParent();
989 return 0;
990 }
992 //===----------------------------------------------------------------------===//
993 // Top-Level parsing and JIT Driver
994 //===----------------------------------------------------------------------===//
996 static ExecutionEngine *TheExecutionEngine;
998 static void HandleDefinition() {
999 if (FunctionAST *F = ParseDefinition()) {
1000 if (Function *LF = F->Codegen()) {
1001 fprintf(stderr, "Read function definition:");
1002 LF->dump();
1003 }
1004 } else {
1005 // Skip token for error recovery.
1006 getNextToken();
1007 }
1008 }
1010 static void HandleExtern() {
1011 if (PrototypeAST *P = ParseExtern()) {
1012 if (Function *F = P->Codegen()) {
1013 fprintf(stderr, "Read extern: ");
1014 F->dump();
1015 }
1016 } else {
1017 // Skip token for error recovery.
1018 getNextToken();
1019 }
1020 }
1022 static void HandleTopLevelExpression() {
1023 // Evaluate a top level expression into an anonymous function.
1024 if (FunctionAST *F = ParseTopLevelExpr()) {
1025 if (Function *LF = F->Codegen()) {
1026 // JIT the function, returning a function pointer.
1027 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1029 // Cast it to the right type (takes no arguments, returns a double) so we
1030 // can call it as a native function.
1031 double (*FP)() = (double (*)())FPtr;
1032 fprintf(stderr, "Evaluated to %f\n", FP());
1033 }
1034 } else {
1035 // Skip token for error recovery.
1036 getNextToken();
1037 }
1038 }
1040 /// top ::= definition | external | expression | ';'
1041 static void MainLoop() {
1042 while (1) {
1043 fprintf(stderr, "ready> ");
1044 switch (CurTok) {
1045 case tok_eof: return;
1046 case ';': getNextToken(); break; // ignore top level semicolons.
1047 case tok_def: HandleDefinition(); break;
1048 case tok_extern: HandleExtern(); break;
1049 default: HandleTopLevelExpression(); break;
1050 }
1051 }
1052 }
1056 //===----------------------------------------------------------------------===//
1058 //===----------------------------------------------------------------------===//
1060 /// putchard - putchar that takes a double and returns 0.
1061 extern "C"
1062 double putchard(double X) {
1063 putchar((char)X);
1064 return 0;
1065 }
1067 //===----------------------------------------------------------------------===//
1068 // Main driver code.
1069 //===----------------------------------------------------------------------===//
1071 int main() {
1072 // Install standard binary operators.
1073 // 1 is lowest precedence.
1075 BinopPrecedence['+'] = 20;
1076 BinopPrecedence['-'] = 20;
1077 BinopPrecedence['*'] = 40; // highest.
1079 // Prime the first token.
1080 fprintf(stderr, "ready> ");
1081 getNextToken();
1083 // Make the module, which holds all the code.
1084 TheModule = new Module("my cool jit");
1086 // Create the JIT.
1087 TheExecutionEngine = ExecutionEngine::create(TheModule);
1089 {
1090 ExistingModuleProvider OurModuleProvider(TheModule);
1091 FunctionPassManager OurFPM(&OurModuleProvider);
1093 // Set up the optimizer pipeline. Start with registering info about how the
1094 // target lays out data structures.
1095 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1096 // Do simple "peephole" optimizations and bit-twiddling optzns.
1097 OurFPM.add(createInstructionCombiningPass());
1098 // Reassociate expressions.
1099 OurFPM.add(createReassociatePass());
1100 // Eliminate Common SubExpressions.
1101 OurFPM.add(createGVNPass());
1102 // Simplify the control flow graph (deleting unreachable blocks, etc).
1103 OurFPM.add(createCFGSimplificationPass());
1105 // Set the global so the code gen can use this.
1106 TheFPM = &OurFPM;
1108 // Run the main "interpreter loop" now.
1109 MainLoop();
1111 TheFPM = 0;
1112 } // Free module provider and pass manager.
1115 // Print out all of the generated code.
1116 TheModule->dump();
1117 return 0;
1118 }
1119 </pre>
1120 </div>
1122 </div>
1124 <!-- *********************************************************************** -->
1125 <hr>
1126 <address>
1135 </address>
1136 </body>
1137 </html>