| blob | 0163b25a2fd57fff5c2a64e8ad77e0d255ab5e89 |
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 = add 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 = add 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 = add double 3.000000e+00, %x
117 %addtmp1 = add double %x, 3.000000e+00
118 %multmp = mul 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 ExistingModuleProvider *OurModuleProvider =
175 new ExistingModuleProvider(TheModule);
177 FunctionPassManager OurFPM(OurModuleProvider);
179 // Set up the optimizer pipeline. Start with registering info about how the
180 // target lays out data structures.
181 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
182 // Do simple "peephole" optimizations and bit-twiddling optzns.
183 OurFPM.add(createInstructionCombiningPass());
184 // Reassociate expressions.
185 OurFPM.add(createReassociatePass());
186 // Eliminate Common SubExpressions.
187 OurFPM.add(createGVNPass());
188 // Simplify the control flow graph (deleting unreachable blocks, etc).
189 OurFPM.add(createCFGSimplificationPass());
191 // Set the global so the code gen can use this.
192 TheFPM = &OurFPM;
194 // Run the main "interpreter loop" now.
195 MainLoop();
196 </pre>
197 </div>
202 that we're not going to take advantage of here, so I won't dive into any details
203 about it.</p>
207 to construct itself. Once it is set up, we use a series of "add" calls to add
208 a bunch of LLVM passes. The first pass is basically boilerplate, it adds a pass
209 so that later optimizations know how the data structures in the program are
210 layed out. The "<tt>TheExecutionEngine</tt>" variable is related to the JIT,
211 which we will get to in the next section.</p>
214 here are a pretty standard set of "cleanup" optimizations that are useful for
215 a wide variety of code. I won't delve into what they do but, believe me,
216 they are a good starting place :).</p>
218 <p>Once the PassManager is set up, we need to make use of it. We do this by
219 running it after our newly created function is constructed (in
223 <pre>
224 if (Value *RetVal = Body->Codegen()) {
225 // Finish off the function.
226 Builder.CreateRet(RetVal);
228 // Validate the generated code, checking for consistency.
229 verifyFunction(*TheFunction);
231 <b>// Optimize the function.
234 return TheFunction;
235 }
236 </pre>
237 </div>
239 <p>As you can see, this is pretty straightforward. The
241 improving (hopefully) its body. With this in place, we can try our test above
242 again:</p>
245 <pre>
247 ready> Read function definition:
248 define double @test(double %x) {
249 entry:
250 %addtmp = add double %x, 3.000000e+00
251 %multmp = mul double %addtmp, %addtmp
252 ret double %multmp
253 }
254 </pre>
255 </div>
257 <p>As expected, we now get our nicely optimized code, saving a floating point
258 add instruction from every execution of this function.</p>
260 <p>LLVM provides a wide variety of optimizations that can be used in certain
262 passes</a> is available, but it isn't very complete. Another good source of
265 experiment with passes from the command line, so you can see if they do
266 anything.</p>
268 <p>Now that we have reasonable code coming out of our front-end, lets talk about
269 executing it!</p>
271 </div>
273 <!-- *********************************************************************** -->
275 <!-- *********************************************************************** -->
279 <p>Code that is available in LLVM IR can have a wide variety of tools
280 applied to it. For example, you can run optimizations on it (as we did above),
281 you can dump it out in textual or binary forms, you can compile the code to an
282 assembly file (.s) for some target, or you can JIT compile it. The nice thing
283 about the LLVM IR representation is that it is the "common currency" between
284 many different parts of the compiler.
285 </p>
287 <p>In this section, we'll add JIT compiler support to our interpreter. The
288 basic idea that we want for Kaleidoscope is to have the user enter function
289 bodies as they do now, but immediately evaluate the top-level expressions they
290 type in. For example, if they type in "1 + 2;", we should evaluate and print
291 out 3. If they define a function, they should be able to call it from the
292 command line.</p>
294 <p>In order to do this, we first declare and initialize the JIT. This is done
298 <pre>
300 ...
301 int main() {
302 ..
303 <b>// Create the JIT. This takes ownership of the module and module provider.
304 TheExecutionEngine = EngineBuilder(OurModuleProvider).create();</b>
305 ..
306 }
307 </pre>
308 </div>
311 compiler or the LLVM interpreter. LLVM will automatically pick a JIT compiler
312 for you if one is available for your platform, otherwise it will fall back to
313 the interpreter.</p>
316 There are a variety of APIs that are useful, but the simplest one is the
317 "<tt>getPointerToFunction(F)</tt>" method. This method JIT compiles the
318 specified LLVM Function and returns a function pointer to the generated machine
319 code. In our case, this means that we can change the code that parses a
320 top-level expression to look like this:</p>
323 <pre>
324 static void HandleTopLevelExpression() {
325 // Evaluate a top level expression into an anonymous function.
326 if (FunctionAST *F = ParseTopLevelExpr()) {
327 if (Function *LF = F->Codegen()) {
328 LF->dump(); // Dump the function for exposition purposes.
330 <b>// JIT the function, returning a function pointer.
331 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
333 // Cast it to the right type (takes no arguments, returns a double) so we
334 // can call it as a native function.
335 double (*FP)() = (double (*)())FPtr;
337 }
338 </pre>
339 </div>
341 <p>Recall that we compile top-level expressions into a self-contained LLVM
342 function that takes no arguments and returns the computed double. Because the
343 LLVM JIT compiler matches the native platform ABI, this means that you can just
344 cast the result pointer to a function pointer of that type and call it directly.
345 This means, there is no difference between JIT compiled code and native machine
346 code that is statically linked into your application.</p>
351 <pre>
353 define double @""() {
354 entry:
355 ret double 9.000000e+00
356 }
359 </pre>
360 </div>
362 <p>Well this looks like it is basically working. The dump of the function
363 shows the "no argument function that always returns double" that we synthesize
364 for each top level expression that is typed in. This demonstrates very basic
365 functionality, but can we do more?</p>
368 <pre>
370 Read function definition:
371 define double @testfunc(double %x, double %y) {
372 entry:
373 %multmp = mul double %y, 2.000000e+00
374 %addtmp = add double %multmp, %x
375 ret double %addtmp
376 }
379 define double @""() {
380 entry:
382 ret double %calltmp
383 }
386 </pre>
387 </div>
389 <p>This illustrates that we can now call user code, but there is something a bit subtle
390 going on here. Note that we only invoke the JIT on the anonymous functions
394 <p>What actually happened here is that the anonymous function was
395 JIT'd when requested. When the Kaleidoscope app calls through the function
396 pointer that is returned, the anonymous function starts executing. It ends up
397 making the call to the "testfunc" function, and ends up in a stub that invokes
398 the JIT, lazily, on testfunc. Once the JIT finishes lazily compiling testfunc,
399 it returns and the code re-executes the call.</p>
401 <p>In summary, the JIT will lazily JIT code, on the fly, as it is needed. The
402 JIT provides a number of other more advanced interfaces for things like freeing
403 allocated machine code, rejit'ing functions to update them, etc. However, even
404 with this simple code, we get some surprisingly powerful capabilities - check
405 this out (I removed the dump of the anonymous functions, you should get the idea
406 by now :) :</p>
409 <pre>
411 Read extern:
412 declare double @sin(double)
415 Read extern:
416 declare double @cos(double)
422 Read function definition:
423 define double @foo(double %x) {
424 entry:
425 %calltmp = call double @sin( double %x )
426 %multmp = mul double %calltmp, %calltmp
427 %calltmp2 = call double @cos( double %x )
428 %multmp4 = mul double %calltmp2, %calltmp2
429 %addtmp = add double %multmp, %multmp4
430 ret double %addtmp
431 }
435 </pre>
436 </div>
438 <p>Whoa, how does the JIT know about sin and cos? The answer is surprisingly
439 simple: in this
440 example, the JIT started execution of a function and got to a function call. It
441 realized that the function was not yet JIT compiled and invoked the standard set
442 of routines to resolve the function. In this case, there is no body defined
444 Kaleidoscope process itself.
445 Since "<tt>sin</tt>" is defined within the JIT's address space, it simply
447 directly.</p>
449 <p>The LLVM JIT provides a number of interfaces (look in the
451 resolved. It allows you to establish explicit mappings between IR objects and
452 addresses (useful for LLVM global variables that you want to map to static
453 tables, for example), allows you to dynamically decide on the fly based on the
454 function name, and even allows you to have the JIT abort itself if any lazy
455 compilation is attempted.</p>
457 <p>One interesting application of this is that we can now extend the language
458 by writing arbitrary C++ code to implement operations. For example, if we add:
459 </p>
462 <pre>
463 /// putchard - putchar that takes a double and returns 0.
464 extern "C"
465 double putchard(double X) {
466 putchar((char)X);
467 return 0;
468 }
469 </pre>
470 </div>
472 <p>Now we can produce simple output to the console by using things like:
473 "<tt>extern putchard(x); putchard(120);</tt>", which prints a lowercase 'x' on
474 the console (120 is the ASCII code for 'x'). Similar code could be used to
475 implement file I/O, console input, and many other capabilities in
476 Kaleidoscope.</p>
478 <p>This completes the JIT and optimizer chapter of the Kaleidoscope tutorial. At
479 this point, we can compile a non-Turing-complete programming language, optimize
480 and JIT compile it in a user-driven way. Next up we'll look into <a
482 tackling some interesting LLVM IR issues along the way.</p>
484 </div>
486 <!-- *********************************************************************** -->
488 <!-- *********************************************************************** -->
492 <p>
493 Here is the complete code listing for our running example, enhanced with the
494 LLVM JIT and optimizer. To build this example, use:
495 </p>
498 <pre>
499 # Compile
500 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
501 # Run
502 ./toy
503 </pre>
504 </div>
506 <p>
507 If you are compiling this on Linux, make sure to add the "-rdynamic" option
508 as well. This makes sure that the external functions are resolved properly
509 at runtime.</p>
514 <pre>
515 #include "llvm/DerivedTypes.h"
516 #include "llvm/ExecutionEngine/ExecutionEngine.h"
517 #include "llvm/LLVMContext.h"
518 #include "llvm/Module.h"
519 #include "llvm/ModuleProvider.h"
520 #include "llvm/PassManager.h"
521 #include "llvm/Analysis/Verifier.h"
522 #include "llvm/Target/TargetData.h"
523 #include "llvm/Transforms/Scalar.h"
524 #include "llvm/Support/IRBuilder.h"
529 using namespace llvm;
531 //===----------------------------------------------------------------------===//
532 // Lexer
533 //===----------------------------------------------------------------------===//
536 // of these for known things.
537 enum Token {
538 tok_eof = -1,
540 // commands
543 // primary
545 };
547 static std::string IdentifierStr; // Filled in if tok_identifier
548 static double NumVal; // Filled in if tok_number
550 /// gettok - Return the next token from standard input.
551 static int gettok() {
552 static int LastChar = ' ';
554 // Skip any whitespace.
555 while (isspace(LastChar))
556 LastChar = getchar();
558 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
559 IdentifierStr = LastChar;
560 while (isalnum((LastChar = getchar())))
561 IdentifierStr += LastChar;
563 if (IdentifierStr == "def") return tok_def;
564 if (IdentifierStr == "extern") return tok_extern;
565 return tok_identifier;
566 }
569 std::string NumStr;
570 do {
571 NumStr += LastChar;
572 LastChar = getchar();
573 } while (isdigit(LastChar) || LastChar == '.');
575 NumVal = strtod(NumStr.c_str(), 0);
576 return tok_number;
577 }
579 if (LastChar == '#') {
580 // Comment until end of line.
581 do LastChar = getchar();
584 if (LastChar != EOF)
585 return gettok();
586 }
588 // Check for end of file. Don't eat the EOF.
589 if (LastChar == EOF)
590 return tok_eof;
592 // Otherwise, just return the character as its ascii value.
593 int ThisChar = LastChar;
594 LastChar = getchar();
595 return ThisChar;
596 }
598 //===----------------------------------------------------------------------===//
599 // Abstract Syntax Tree (aka Parse Tree)
600 //===----------------------------------------------------------------------===//
602 /// ExprAST - Base class for all expression nodes.
603 class ExprAST {
604 public:
605 virtual ~ExprAST() {}
606 virtual Value *Codegen() = 0;
607 };
609 /// NumberExprAST - Expression class for numeric literals like "1.0".
610 class NumberExprAST : public ExprAST {
611 double Val;
612 public:
613 NumberExprAST(double val) : Val(val) {}
614 virtual Value *Codegen();
615 };
617 /// VariableExprAST - Expression class for referencing a variable, like "a".
618 class VariableExprAST : public ExprAST {
619 std::string Name;
620 public:
621 VariableExprAST(const std::string &name) : Name(name) {}
622 virtual Value *Codegen();
623 };
625 /// BinaryExprAST - Expression class for a binary operator.
626 class BinaryExprAST : public ExprAST {
627 char Op;
628 ExprAST *LHS, *RHS;
629 public:
630 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
631 : Op(op), LHS(lhs), RHS(rhs) {}
632 virtual Value *Codegen();
633 };
635 /// CallExprAST - Expression class for function calls.
636 class CallExprAST : public ExprAST {
637 std::string Callee;
639 public:
641 : Callee(callee), Args(args) {}
642 virtual Value *Codegen();
643 };
645 /// PrototypeAST - This class represents the "prototype" for a function,
646 /// which captures its argument names as well as if it is an operator.
647 class PrototypeAST {
648 std::string Name;
650 public:
652 : Name(name), Args(args) {}
654 Function *Codegen();
655 };
657 /// FunctionAST - This class represents a function definition itself.
658 class FunctionAST {
659 PrototypeAST *Proto;
660 ExprAST *Body;
661 public:
662 FunctionAST(PrototypeAST *proto, ExprAST *body)
663 : Proto(proto), Body(body) {}
665 Function *Codegen();
666 };
668 //===----------------------------------------------------------------------===//
669 // Parser
670 //===----------------------------------------------------------------------===//
672 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
673 /// token the parser it looking at. getNextToken reads another token from the
674 /// lexer and updates CurTok with its results.
675 static int CurTok;
676 static int getNextToken() {
677 return CurTok = gettok();
678 }
680 /// BinopPrecedence - This holds the precedence for each binary operator that is
681 /// defined.
684 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
685 static int GetTokPrecedence() {
686 if (!isascii(CurTok))
687 return -1;
689 // Make sure it's a declared binop.
690 int TokPrec = BinopPrecedence[CurTok];
692 return TokPrec;
693 }
695 /// Error* - These are little helper functions for error handling.
697 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
698 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
700 static ExprAST *ParseExpression();
702 /// identifierexpr
703 /// ::= identifier
704 /// ::= identifier '(' expression* ')'
705 static ExprAST *ParseIdentifierExpr() {
706 std::string IdName = IdentifierStr;
708 getNextToken(); // eat identifier.
710 if (CurTok != '(') // Simple variable ref.
711 return new VariableExprAST(IdName);
713 // Call.
714 getNextToken(); // eat (
716 if (CurTok != ')') {
717 while (1) {
718 ExprAST *Arg = ParseExpression();
719 if (!Arg) return 0;
720 Args.push_back(Arg);
722 if (CurTok == ')') break;
724 if (CurTok != ',')
725 return Error("Expected ')' or ',' in argument list");
726 getNextToken();
727 }
728 }
730 // Eat the ')'.
731 getNextToken();
733 return new CallExprAST(IdName, Args);
734 }
736 /// numberexpr ::= number
737 static ExprAST *ParseNumberExpr() {
738 ExprAST *Result = new NumberExprAST(NumVal);
739 getNextToken(); // consume the number
740 return Result;
741 }
743 /// parenexpr ::= '(' expression ')'
744 static ExprAST *ParseParenExpr() {
745 getNextToken(); // eat (.
746 ExprAST *V = ParseExpression();
747 if (!V) return 0;
749 if (CurTok != ')')
750 return Error("expected ')'");
751 getNextToken(); // eat ).
752 return V;
753 }
755 /// primary
756 /// ::= identifierexpr
757 /// ::= numberexpr
758 /// ::= parenexpr
759 static ExprAST *ParsePrimary() {
760 switch (CurTok) {
761 default: return Error("unknown token when expecting an expression");
762 case tok_identifier: return ParseIdentifierExpr();
763 case tok_number: return ParseNumberExpr();
764 case '(': return ParseParenExpr();
765 }
766 }
768 /// binoprhs
769 /// ::= ('+' primary)*
770 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
771 // If this is a binop, find its precedence.
772 while (1) {
773 int TokPrec = GetTokPrecedence();
775 // If this is a binop that binds at least as tightly as the current binop,
776 // consume it, otherwise we are done.
777 if (TokPrec < ExprPrec)
778 return LHS;
780 // Okay, we know this is a binop.
781 int BinOp = CurTok;
782 getNextToken(); // eat binop
784 // Parse the primary expression after the binary operator.
785 ExprAST *RHS = ParsePrimary();
786 if (!RHS) return 0;
788 // If BinOp binds less tightly with RHS than the operator after RHS, let
789 // the pending operator take RHS as its LHS.
790 int NextPrec = GetTokPrecedence();
791 if (TokPrec < NextPrec) {
792 RHS = ParseBinOpRHS(TokPrec+1, RHS);
794 }
796 // Merge LHS/RHS.
797 LHS = new BinaryExprAST(BinOp, LHS, RHS);
798 }
799 }
801 /// expression
802 /// ::= primary binoprhs
803 ///
804 static ExprAST *ParseExpression() {
805 ExprAST *LHS = ParsePrimary();
806 if (!LHS) return 0;
808 return ParseBinOpRHS(0, LHS);
809 }
811 /// prototype
812 /// ::= id '(' id* ')'
813 static PrototypeAST *ParsePrototype() {
814 if (CurTok != tok_identifier)
815 return ErrorP("Expected function name in prototype");
817 std::string FnName = IdentifierStr;
818 getNextToken();
820 if (CurTok != '(')
821 return ErrorP("Expected '(' in prototype");
824 while (getNextToken() == tok_identifier)
825 ArgNames.push_back(IdentifierStr);
826 if (CurTok != ')')
827 return ErrorP("Expected ')' in prototype");
829 // success.
830 getNextToken(); // eat ')'.
832 return new PrototypeAST(FnName, ArgNames);
833 }
835 /// definition ::= 'def' prototype expression
836 static FunctionAST *ParseDefinition() {
837 getNextToken(); // eat def.
838 PrototypeAST *Proto = ParsePrototype();
841 if (ExprAST *E = ParseExpression())
842 return new FunctionAST(Proto, E);
843 return 0;
844 }
846 /// toplevelexpr ::= expression
847 static FunctionAST *ParseTopLevelExpr() {
848 if (ExprAST *E = ParseExpression()) {
849 // Make an anonymous proto.
851 return new FunctionAST(Proto, E);
852 }
853 return 0;
854 }
856 /// external ::= 'extern' prototype
857 static PrototypeAST *ParseExtern() {
858 getNextToken(); // eat extern.
859 return ParsePrototype();
860 }
862 //===----------------------------------------------------------------------===//
863 // Code Generation
864 //===----------------------------------------------------------------------===//
866 static Module *TheModule;
867 static IRBuilder<> Builder(getGlobalContext());
869 static FunctionPassManager *TheFPM;
871 Value *ErrorV(const char *Str) { Error(Str); return 0; }
873 Value *NumberExprAST::Codegen() {
874 return ConstantFP::get(getGlobalContext(), APFloat(Val));
875 }
877 Value *VariableExprAST::Codegen() {
878 // Look this variable up in the function.
879 Value *V = NamedValues[Name];
880 return V ? V : ErrorV("Unknown variable name");
881 }
883 Value *BinaryExprAST::Codegen() {
884 Value *L = LHS->Codegen();
885 Value *R = RHS->Codegen();
888 switch (Op) {
889 case '+': return Builder.CreateAdd(L, R, "addtmp");
890 case '-': return Builder.CreateSub(L, R, "subtmp");
891 case '*': return Builder.CreateMul(L, R, "multmp");
892 case '<':
893 L = Builder.CreateFCmpULT(L, R, "cmptmp");
895 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), "booltmp");
896 default: return ErrorV("invalid binary operator");
897 }
898 }
900 Value *CallExprAST::Codegen() {
901 // Look up the name in the global module table.
902 Function *CalleeF = TheModule->getFunction(Callee);
903 if (CalleeF == 0)
904 return ErrorV("Unknown function referenced");
906 // If argument mismatch error.
907 if (CalleeF->arg_size() != Args.size())
908 return ErrorV("Incorrect # arguments passed");
911 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
912 ArgsV.push_back(Args[i]->Codegen());
914 }
916 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
917 }
919 Function *PrototypeAST::Codegen() {
920 // Make the function type: double(double,double) etc.
922 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false);
924 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
926 // If F conflicted, there was already something named 'Name'. If it has a
927 // body, don't allow redefinition or reextern.
928 if (F->getName() != Name) {
929 // Delete the one we just made and get the existing one.
930 F->eraseFromParent();
931 F = TheModule->getFunction(Name);
933 // If F already has a body, reject this.
934 if (!F->empty()) {
935 ErrorF("redefinition of function");
936 return 0;
937 }
939 // If F took a different number of args, reject.
940 if (F->arg_size() != Args.size()) {
941 ErrorF("redefinition of function with different # args");
942 return 0;
943 }
944 }
946 // Set names for all arguments.
947 unsigned Idx = 0;
948 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
949 ++AI, ++Idx) {
950 AI->setName(Args[Idx]);
952 // Add arguments to variable symbol table.
953 NamedValues[Args[Idx]] = AI;
954 }
956 return F;
957 }
959 Function *FunctionAST::Codegen() {
960 NamedValues.clear();
962 Function *TheFunction = Proto->Codegen();
963 if (TheFunction == 0)
964 return 0;
966 // Create a new basic block to start insertion into.
967 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
968 Builder.SetInsertPoint(BB);
970 if (Value *RetVal = Body->Codegen()) {
971 // Finish off the function.
972 Builder.CreateRet(RetVal);
974 // Validate the generated code, checking for consistency.
975 verifyFunction(*TheFunction);
977 // Optimize the function.
978 TheFPM->run(*TheFunction);
980 return TheFunction;
981 }
983 // Error reading body, remove function.
984 TheFunction->eraseFromParent();
985 return 0;
986 }
988 //===----------------------------------------------------------------------===//
989 // Top-Level parsing and JIT Driver
990 //===----------------------------------------------------------------------===//
992 static ExecutionEngine *TheExecutionEngine;
994 static void HandleDefinition() {
995 if (FunctionAST *F = ParseDefinition()) {
996 if (Function *LF = F->Codegen()) {
997 fprintf(stderr, "Read function definition:");
998 LF->dump();
999 }
1000 } else {
1001 // Skip token for error recovery.
1002 getNextToken();
1003 }
1004 }
1006 static void HandleExtern() {
1007 if (PrototypeAST *P = ParseExtern()) {
1008 if (Function *F = P->Codegen()) {
1009 fprintf(stderr, "Read extern: ");
1010 F->dump();
1011 }
1012 } else {
1013 // Skip token for error recovery.
1014 getNextToken();
1015 }
1016 }
1018 static void HandleTopLevelExpression() {
1019 // Evaluate a top level expression into an anonymous function.
1020 if (FunctionAST *F = ParseTopLevelExpr()) {
1021 if (Function *LF = F->Codegen()) {
1022 // JIT the function, returning a function pointer.
1023 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1025 // Cast it to the right type (takes no arguments, returns a double) so we
1026 // can call it as a native function.
1027 double (*FP)() = (double (*)())FPtr;
1028 fprintf(stderr, "Evaluated to %f\n", FP());
1029 }
1030 } else {
1031 // Skip token for error recovery.
1032 getNextToken();
1033 }
1034 }
1036 /// top ::= definition | external | expression | ';'
1037 static void MainLoop() {
1038 while (1) {
1039 fprintf(stderr, "ready> ");
1040 switch (CurTok) {
1041 case tok_eof: return;
1042 case ';': getNextToken(); break; // ignore top level semicolons.
1043 case tok_def: HandleDefinition(); break;
1044 case tok_extern: HandleExtern(); break;
1045 default: HandleTopLevelExpression(); break;
1046 }
1047 }
1048 }
1052 //===----------------------------------------------------------------------===//
1054 //===----------------------------------------------------------------------===//
1056 /// putchard - putchar that takes a double and returns 0.
1057 extern "C"
1058 double putchard(double X) {
1059 putchar((char)X);
1060 return 0;
1061 }
1063 //===----------------------------------------------------------------------===//
1064 // Main driver code.
1065 //===----------------------------------------------------------------------===//
1067 int main() {
1068 // Install standard binary operators.
1069 // 1 is lowest precedence.
1071 BinopPrecedence['+'] = 20;
1072 BinopPrecedence['-'] = 20;
1073 BinopPrecedence['*'] = 40; // highest.
1075 // Prime the first token.
1076 fprintf(stderr, "ready> ");
1077 getNextToken();
1079 // Make the module, which holds all the code.
1080 TheModule = new Module("my cool jit", getGlobalContext());
1082 ExistingModuleProvider *OurModuleProvider =
1083 new ExistingModuleProvider(TheModule);
1085 // Create the JIT. This takes ownership of the module and module provider.
1086 TheExecutionEngine = EngineBuilder(OurModuleProvider).create();
1088 FunctionPassManager OurFPM(OurModuleProvider);
1090 // Set up the optimizer pipeline. Start with registering info about how the
1091 // target lays out data structures.
1092 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1093 // Do simple "peephole" optimizations and bit-twiddling optzns.
1094 OurFPM.add(createInstructionCombiningPass());
1095 // Reassociate expressions.
1096 OurFPM.add(createReassociatePass());
1097 // Eliminate Common SubExpressions.
1098 OurFPM.add(createGVNPass());
1099 // Simplify the control flow graph (deleting unreachable blocks, etc).
1100 OurFPM.add(createCFGSimplificationPass());
1102 // Set the global so the code gen can use this.
1103 TheFPM = &OurFPM;
1105 // Run the main "interpreter loop" now.
1106 MainLoop();
1108 TheFPM = 0;
1110 // Print out all of the generated code.
1111 TheModule->dump();
1113 return 0;
1114 }
1115 </pre>
1116 </div>
1119 </div>
1121 <!-- *********************************************************************** -->
1122 <hr>
1123 <address>
1132 </address>
1133 </body>
1134 </html>