| blob | 44ad15b009655fcf9bd95ecbf0a9cad5097996c1 |
4 <html>
5 <head>
10 </head>
12 <body>
16 <ul>
19 <ol>
26 </ol>
27 </li>
29 Variables / SSA Construction</li>
30 </ul>
34 </div>
36 <!-- *********************************************************************** -->
38 <!-- *********************************************************************** -->
43 with LLVM</a>" tutorial. At this point in our tutorial, we now have a fully
44 functional language that is fairly minimal, but also useful. There
45 is still one big problem with it, however. Our language doesn't have many
46 useful operators (like division, logical negation, or even any comparisons
47 besides less-than).</p>
49 <p>This chapter of the tutorial takes a wild digression into adding user-defined
50 operators to the simple and beautiful Kaleidoscope language. This digression now gives
51 us a simple and ugly language in some ways, but also a powerful one at the same time.
52 One of the great things about creating your own language is that you get to
53 decide what is good or bad. In this tutorial we'll assume that it is okay to
54 use this as a way to show some interesting parsing techniques.</p>
56 <p>At the end of this tutorial, we'll run through an example Kaleidoscope
58 an example of what you can build with Kaleidoscope and its feature set.</p>
60 </div>
62 <!-- *********************************************************************** -->
64 <!-- *********************************************************************** -->
68 <p>
69 The "operator overloading" that we will add to Kaleidoscope is more general than
70 languages like C++. In C++, you are only allowed to redefine existing
71 operators: you can't programatically change the grammar, introduce new
72 operators, change precedence levels, etc. In this chapter, we will add this
73 capability to Kaleidoscope, which will let the user round out the set of
74 operators that are supported.</p>
76 <p>The point of going into user-defined operators in a tutorial like this is to
77 show the power and flexibility of using a hand-written parser. Thus far, the parser
78 we have been implementing uses recursive descent for most parts of the grammar and
79 operator precedence parsing for the expressions. See <a
81 precedence parsing, it would be very difficult to allow the programmer to
82 introduce new operators into the grammar: the grammar is dynamically extensible
83 as the JIT runs.</p>
85 <p>The two specific features we'll add are programmable unary operators (right
86 now, Kaleidoscope has no unary operators at all) as well as binary operators.
87 An example of this is:</p>
90 <pre>
91 # Logical unary not.
92 def unary!(v)
93 if v then
94 0
95 else
96 1;
100 RHS < LHS;
103 def binary| 5 (LHS RHS)
104 if LHS then
105 1
106 else if RHS then
107 1
108 else
109 0;
111 # Define = with slightly lower precedence than relationals.
112 def binary= 9 (LHS RHS)
114 </pre>
115 </div>
117 <p>Many languages aspire to being able to implement their standard runtime
118 library in the language itself. In Kaleidoscope, we can implement significant
119 parts of the language in the library!</p>
121 <p>We will break down implementation of these features into two parts:
122 implementing support for user-defined binary operators and adding unary
123 operators.</p>
125 </div>
127 <!-- *********************************************************************** -->
129 <!-- *********************************************************************** -->
133 <p>Adding support for user-defined binary operators is pretty simple with our
134 current framework. We'll first add support for the unary/binary keywords:</p>
137 <pre>
138 enum Token {
139 ...
140 <b>// operators
142 };
143 ...
144 static int gettok() {
145 ...
146 if (IdentifierStr == "for") return tok_for;
147 if (IdentifierStr == "in") return tok_in;
150 return tok_identifier;
151 </pre>
152 </div>
154 <p>This just adds lexer support for the unary and binary keywords, like we
156 about our current AST, is that we represent binary operators with full generalisation
157 by using their ASCII code as the opcode. For our extended operators, we'll use this
158 same representation, so we don't need any new AST or parser support.</p>
160 <p>On the other hand, we have to be able to represent the definitions of these
161 new operators, in the "def binary| 5" part of the function definition. In our
162 grammar so far, the "name" for the function definition is parsed as the
164 represent our new user-defined operators as prototypes, we have to extend
168 <pre>
169 /// PrototypeAST - This class represents the "prototype" for a function,
170 /// which captures its argument names as well as if it is an operator.
171 class PrototypeAST {
172 std::string Name;
174 <b>bool isOperator;
175 unsigned Precedence; // Precedence if a binary op.</b>
176 public:
184 char getOperatorName() const {
185 assert(isUnaryOp() || isBinaryOp());
186 return Name[Name.size()-1];
187 }
189 unsigned getBinaryPrecedence() const { return Precedence; }</b>
191 Function *Codegen();
192 };
193 </pre>
194 </div>
196 <p>Basically, in addition to knowing a name for the prototype, we now keep track
197 of whether it was an operator, and if it was, what precedence level the operator
198 is at. The precedence is only used for binary operators (as you'll see below,
199 it just doesn't apply for unary operators). Now that we have a way to represent
200 the prototype for a user-defined operator, we need to parse it:</p>
203 <pre>
204 /// prototype
205 /// ::= id '(' id* ')'
207 static PrototypeAST *ParsePrototype() {
208 std::string FnName;
213 switch (CurTok) {
214 default:
215 return ErrorP("Expected function name in prototype");
216 case tok_identifier:
217 FnName = IdentifierStr;
218 Kind = 0;
219 getNextToken();
220 break;
221 <b>case tok_binary:
222 getNextToken();
223 if (!isascii(CurTok))
224 return ErrorP("Expected binary operator");
225 FnName = "binary";
226 FnName += (char)CurTok;
227 Kind = 2;
228 getNextToken();
230 // Read the precedence if present.
231 if (CurTok == tok_number) {
233 return ErrorP("Invalid precedecnce: must be 1..100");
234 BinaryPrecedence = (unsigned)NumVal;
235 getNextToken();
236 }
237 break;</b>
238 }
240 if (CurTok != '(')
241 return ErrorP("Expected '(' in prototype");
244 while (getNextToken() == tok_identifier)
245 ArgNames.push_back(IdentifierStr);
246 if (CurTok != ')')
247 return ErrorP("Expected ')' in prototype");
249 // success.
250 getNextToken(); // eat ')'.
252 <b>// Verify right number of names for operator.
253 if (Kind && ArgNames.size() != Kind)
254 return ErrorP("Invalid number of operands for operator");
257 }
258 </pre>
259 </div>
261 <p>This is all fairly straightforward parsing code, and we have already seen
262 a lot of similar code in the past. One interesting part about the code above is
265 fact that symbol names in the LLVM symbol table are allowed to have any character in
266 them, including embedded nul characters.</p>
268 <p>The next interesting thing to add, is codegen support for these binary operators.
269 Given our current structure, this is a simple addition of a default case for our
270 existing binary operator node:</p>
273 <pre>
274 Value *BinaryExprAST::Codegen() {
275 Value *L = LHS->Codegen();
276 Value *R = RHS->Codegen();
279 switch (Op) {
280 case '+': return Builder.CreateAdd(L, R, "addtmp");
281 case '-': return Builder.CreateSub(L, R, "subtmp");
282 case '*': return Builder.CreateMul(L, R, "multmp");
283 case '<':
284 L = Builder.CreateFCmpULT(L, R, "cmptmp");
286 return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
288 }
290 <b>// If it wasn't a builtin binary operator, it must be a user defined one. Emit
291 // a call to it.
295 Value *Ops[] = { L, R };
297 }
299 </pre>
300 </div>
302 <p>As you can see above, the new code is actually really simple. It just does
303 a lookup for the appropriate operator in the symbol table and generates a
304 function call to it. Since user-defined operators are just built as normal
305 functions (because the "prototype" boils down to a function with the right
306 name) everything falls into place.</p>
311 <pre>
312 Function *FunctionAST::Codegen() {
313 NamedValues.clear();
315 Function *TheFunction = Proto->Codegen();
316 if (TheFunction == 0)
317 return 0;
319 <b>// If this is an operator, install it.
320 if (Proto->isBinaryOp())
323 // Create a new basic block to start insertion into.
324 BasicBlock *BB = BasicBlock::Create("entry", TheFunction);
325 Builder.SetInsertPoint(BB);
327 if (Value *RetVal = Body->Codegen()) {
328 ...
329 </pre>
330 </div>
332 <p>Basically, before codegening a function, if it is a user-defined operator, we
333 register it in the precedence table. This allows the binary operator parsing
334 logic we already have in place to handle it. Since we are working on a fully-general operator precedence parser, this is all we need to do to "extend the grammar".</p>
336 <p>Now we have useful user-defined binary operators. This builds a lot
337 on the previous framework we built for other operators. Adding unary operators
338 is a bit more challenging, because we don't have any framework for it yet - lets
339 see what it takes.</p>
341 </div>
343 <!-- *********************************************************************** -->
345 <!-- *********************************************************************** -->
349 <p>Since we don't currently support unary operators in the Kaleidoscope
350 language, we'll need to add everything to support them. Above, we added simple
351 support for the 'unary' keyword to the lexer. In addition to that, we need an
352 AST node:</p>
355 <pre>
356 /// UnaryExprAST - Expression class for a unary operator.
357 class UnaryExprAST : public ExprAST {
358 char Opcode;
359 ExprAST *Operand;
360 public:
361 UnaryExprAST(char opcode, ExprAST *operand)
362 : Opcode(opcode), Operand(operand) {}
363 virtual Value *Codegen();
364 };
365 </pre>
366 </div>
368 <p>This AST node is very simple and obvious by now. It directly mirrors the
369 binary operator AST node, except that it only has one child. With this, we
370 need to add the parsing logic. Parsing a unary operator is pretty simple: we'll
371 add a new function to do it:</p>
374 <pre>
375 /// unary
376 /// ::= primary
377 /// ::= '!' unary
378 static ExprAST *ParseUnary() {
379 // If the current token is not an operator, it must be a primary expr.
380 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
381 return ParsePrimary();
383 // If this is a unary operator, read it.
384 int Opc = CurTok;
385 getNextToken();
386 if (ExprAST *Operand = ParseUnary())
387 return new UnaryExprAST(Opc, Operand);
388 return 0;
389 }
390 </pre>
391 </div>
393 <p>The grammar we add is pretty straightforward here. If we see a unary
394 operator when parsing a primary operator, we eat the operator as a prefix and
395 parse the remaining piece as another unary operator. This allows us to handle
396 multiple unary operators (e.g. "!!x"). Note that unary operators can't have
397 ambiguous parses like binary operators can, so there is no need for precedence
398 information.</p>
400 <p>The problem with this function, is that we need to call ParseUnary from somewhere.
401 To do this, we change previous callers of ParsePrimary to call ParseUnary
402 instead:</p>
405 <pre>
406 /// binoprhs
407 /// ::= ('+' unary)*
408 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
409 ...
410 <b>// Parse the unary expression after the binary operator.
411 ExprAST *RHS = ParseUnary();
413 ...
414 }
415 /// expression
416 /// ::= unary binoprhs
417 ///
418 static ExprAST *ParseExpression() {
420 if (!LHS) return 0;
422 return ParseBinOpRHS(0, LHS);
423 }
424 </pre>
425 </div>
427 <p>With these two simple changes, we are now able to parse unary operators and build the
428 AST for them. Next up, we need to add parser support for prototypes, to parse
429 the unary operator prototype. We extend the binary operator code above
430 with:</p>
433 <pre>
434 /// prototype
435 /// ::= id '(' id* ')'
436 /// ::= binary LETTER number? (id, id)
438 static PrototypeAST *ParsePrototype() {
439 std::string FnName;
442 unsigned BinaryPrecedence = 30;
444 switch (CurTok) {
445 default:
446 return ErrorP("Expected function name in prototype");
447 case tok_identifier:
448 FnName = IdentifierStr;
449 Kind = 0;
450 getNextToken();
451 break;
452 <b>case tok_unary:
453 getNextToken();
454 if (!isascii(CurTok))
455 return ErrorP("Expected unary operator");
456 FnName = "unary";
457 FnName += (char)CurTok;
458 Kind = 1;
459 getNextToken();
460 break;</b>
461 case tok_binary:
462 ...
463 </pre>
464 </div>
466 <p>As with binary operators, we name unary operators with a name that includes
467 the operator character. This assists us at code generation time. Speaking of,
468 the final piece we need to add is codegen support for unary operators. It looks
469 like this:</p>
472 <pre>
473 Value *UnaryExprAST::Codegen() {
474 Value *OperandV = Operand->Codegen();
478 if (F == 0)
479 return ErrorV("Unknown unary operator");
481 return Builder.CreateCall(F, OperandV, "unop");
482 }
483 </pre>
484 </div>
486 <p>This code is similar to, but simpler than, the code for binary operators. It
487 is simpler primarily because it doesn't need to handle any predefined operators.
488 </p>
490 </div>
492 <!-- *********************************************************************** -->
494 <!-- *********************************************************************** -->
498 <p>It is somewhat hard to believe, but with a few simple extensions we've
499 covered in the last chapters, we have grown a real-ish language. With this, we
500 can do a lot of interesting things, including I/O, math, and a bunch of other
501 things. For example, we can now add a nice sequencing operator (printd is
502 defined to print out the specified value and a newline):</p>
505 <pre>
507 Read extern: declare double @printd(double)
509 ..
511 123.000000
512 456.000000
513 789.000000
514 Evaluated to 0.000000
515 </pre>
516 </div>
521 <pre>
522 # Logical unary not.
523 def unary!(v)
524 if v then
525 0
526 else
527 1;
529 # Unary negate.
530 def unary-(v)
531 0-v;
535 RHS < LHS;
537 # Binary logical or, which does not short circuit.
538 def binary| 5 (LHS RHS)
539 if LHS then
540 1
541 else if RHS then
542 1
543 else
544 0;
546 # Binary logical and, which does not short circuit.
548 if !LHS then
549 0
550 else
551 !!RHS;
553 # Define = with slightly lower precedence than relationals.
554 def binary = 9 (LHS RHS)
557 </pre>
558 </div>
561 <p>Given the previous if/then/else support, we can also define interesting
562 functions for I/O. For example, the following prints out a character whose
563 "density" reflects the value passed in: the lower the value, the denser the
564 character:</p>
567 <pre>
568 ready>
569 <b>
570 extern putchard(char)
571 def printdensity(d)
573 putchard(32) # ' '
575 putchard(46) # '.'
577 putchard(43) # '+'
578 else
580 ...
583 *++..
584 Evaluated to 0.000000
585 </pre>
586 </div>
588 <p>Based on these simple primitive operations, we can start to define more
589 interesting things. For example, here's a little function that solves for the
590 number of iterations it takes a function in the complex plane to
591 converge:</p>
594 <pre>
595 # determine whether the specific location diverges.
596 # Solve for z = z^2 + c in the complex plane.
597 def mandleconverger(real imag iters creal cimag)
599 iters
600 else
601 mandleconverger(real*real - imag*imag + creal,
602 2*real*imag + cimag,
603 iters+1, creal, cimag);
605 # return the number of iterations required for the iteration to escape
606 def mandleconverge(real imag)
607 mandleconverger(real, imag, 0, real, imag);
608 </pre>
609 </div>
612 for computation of the <a
615 for a complex orbit to escape, saturating to 255. This is not a very useful
616 function by itself, but if you plot its value over a two-dimensional plane,
617 you can see the Mandelbrot set. Given that we are limited to using putchard
618 here, our amazing graphical output is limited, but we can whip together
619 something using the density plotter above:</p>
622 <pre>
623 # compute and plot the mandlebrot set with the specified 2 dimensional range
624 # info.
625 def mandelhelp(xmin xmax xstep ymin ymax ystep)
626 for y = ymin, y < ymax, ystep in (
627 (for x = xmin, x < xmax, xstep in
628 printdensity(mandleconverge(x,y)))
629 : putchard(10)
630 )
632 # mandel - This is a convenient helper function for ploting the mandelbrot set
633 # from the specified position with the specified Magnification.
634 def mandel(realstart imagstart realmag imagmag)
635 mandelhelp(realstart, realstart+realmag*78, realmag,
636 imagstart, imagstart+imagmag*40, imagmag);
637 </pre>
638 </div>
643 <pre>
645 *******************************+++++++++++*************************************
646 *************************+++++++++++++++++++++++*******************************
647 **********************+++++++++++++++++++++++++++++****************************
648 *******************+++++++++++++++++++++.. ...++++++++*************************
649 *****************++++++++++++++++++++++.... ...+++++++++***********************
650 ***************+++++++++++++++++++++++..... ...+++++++++*********************
651 **************+++++++++++++++++++++++.... ....+++++++++********************
652 *************++++++++++++++++++++++...... .....++++++++*******************
653 ************+++++++++++++++++++++....... .......+++++++******************
654 ***********+++++++++++++++++++.... ... .+++++++*****************
655 **********+++++++++++++++++....... .+++++++****************
656 *********++++++++++++++........... ...+++++++***************
657 ********++++++++++++............ ...++++++++**************
658 ********++++++++++... .......... .++++++++**************
659 *******+++++++++..... .+++++++++*************
660 *******++++++++...... ..+++++++++*************
661 *******++++++....... ..+++++++++*************
662 *******+++++...... ..+++++++++*************
663 *******.... .... ...+++++++++*************
664 *******.... . ...+++++++++*************
665 *******+++++...... ...+++++++++*************
666 *******++++++....... ..+++++++++*************
667 *******++++++++...... .+++++++++*************
668 *******+++++++++..... ..+++++++++*************
669 ********++++++++++... .......... .++++++++**************
670 ********++++++++++++............ ...++++++++**************
671 *********++++++++++++++.......... ...+++++++***************
672 **********++++++++++++++++........ .+++++++****************
673 **********++++++++++++++++++++.... ... ..+++++++****************
674 ***********++++++++++++++++++++++....... .......++++++++*****************
675 ************+++++++++++++++++++++++...... ......++++++++******************
676 **************+++++++++++++++++++++++.... ....++++++++********************
677 ***************+++++++++++++++++++++++..... ...+++++++++*********************
678 *****************++++++++++++++++++++++.... ...++++++++***********************
679 *******************+++++++++++++++++++++......++++++++*************************
680 *********************++++++++++++++++++++++.++++++++***************************
681 *************************+++++++++++++++++++++++*******************************
682 ******************************+++++++++++++************************************
683 *******************************************************************************
684 *******************************************************************************
685 *******************************************************************************
686 Evaluated to 0.000000
688 **************************+++++++++++++++++++++++++++++++++++++++++++++++++++++
689 ***********************++++++++++++++++++++++++++++++++++++++++++++++++++++++++
690 *********************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
691 *******************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
692 *****************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++.....
693 ***************++++++++++++++++++++++++++++++++++++++++++++++++++++++++........
694 **************++++++++++++++++++++++++++++++++++++++++++++++++++++++...........
695 ************+++++++++++++++++++++++++++++++++++++++++++++++++++++..............
696 ***********++++++++++++++++++++++++++++++++++++++++++++++++++........ .
697 **********++++++++++++++++++++++++++++++++++++++++++++++.............
698 ********+++++++++++++++++++++++++++++++++++++++++++..................
699 *******+++++++++++++++++++++++++++++++++++++++.......................
700 ******+++++++++++++++++++++++++++++++++++...........................
701 *****++++++++++++++++++++++++++++++++............................
702 *****++++++++++++++++++++++++++++...............................
703 ****++++++++++++++++++++++++++...... .........................
704 ***++++++++++++++++++++++++......... ...... ...........
705 ***++++++++++++++++++++++............
706 **+++++++++++++++++++++..............
707 **+++++++++++++++++++................
708 *++++++++++++++++++.................
709 *++++++++++++++++............ ...
710 *++++++++++++++..............
711 *+++....++++................
712 *.......... ...........
713 *
714 *.......... ...........
715 *+++....++++................
716 *++++++++++++++..............
717 *++++++++++++++++............ ...
718 *++++++++++++++++++.................
719 **+++++++++++++++++++................
720 **+++++++++++++++++++++..............
721 ***++++++++++++++++++++++............
722 ***++++++++++++++++++++++++......... ...... ...........
723 ****++++++++++++++++++++++++++...... .........................
724 *****++++++++++++++++++++++++++++...............................
725 *****++++++++++++++++++++++++++++++++............................
726 ******+++++++++++++++++++++++++++++++++++...........................
727 *******+++++++++++++++++++++++++++++++++++++++.......................
728 ********+++++++++++++++++++++++++++++++++++++++++++..................
729 Evaluated to 0.000000
731 *******************************************************************************
732 *******************************************************************************
733 *******************************************************************************
734 **********+++++++++++++++++++++************************************************
735 *+++++++++++++++++++++++++++++++++++++++***************************************
736 +++++++++++++++++++++++++++++++++++++++++++++**********************************
737 ++++++++++++++++++++++++++++++++++++++++++++++++++*****************************
738 ++++++++++++++++++++++++++++++++++++++++++++++++++++++*************************
739 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++**********************
740 +++++++++++++++++++++++++++++++++.........++++++++++++++++++*******************
741 +++++++++++++++++++++++++++++++.... ......+++++++++++++++++++****************
742 +++++++++++++++++++++++++++++....... ........+++++++++++++++++++**************
743 ++++++++++++++++++++++++++++........ ........++++++++++++++++++++************
744 +++++++++++++++++++++++++++......... .. ...+++++++++++++++++++++**********
745 ++++++++++++++++++++++++++........... ....++++++++++++++++++++++********
746 ++++++++++++++++++++++++............. .......++++++++++++++++++++++******
747 +++++++++++++++++++++++............. ........+++++++++++++++++++++++****
748 ++++++++++++++++++++++........... ..........++++++++++++++++++++++***
749 ++++++++++++++++++++........... .........++++++++++++++++++++++*
750 ++++++++++++++++++............ ...........++++++++++++++++++++
751 ++++++++++++++++............... .............++++++++++++++++++
752 ++++++++++++++................. ...............++++++++++++++++
753 ++++++++++++.................. .................++++++++++++++
754 +++++++++.................. .................+++++++++++++
755 ++++++........ . ......... ..++++++++++++
756 ++............ ...... ....++++++++++
757 .............. ...++++++++++
758 .............. ....+++++++++
759 .............. .....++++++++
760 ............. ......++++++++
761 ........... .......++++++++
762 ......... ........+++++++
763 ......... ........+++++++
764 ......... ....+++++++
765 ........ ...+++++++
766 ....... ...+++++++
767 ....+++++++
768 .....+++++++
769 ....+++++++
770 ....+++++++
771 ....+++++++
772 Evaluated to 0.000000
774 </pre>
775 </div>
777 <p>At this point, you may be starting to realize that Kaleidoscope is a real
778 and powerful language. It may not be self-similar :), but it can be used to
779 plot things that are!</p>
782 tutorial. We have successfully augmented our language, adding the ability to extend the
783 language in the library, and we have shown how this can be used to build a simple but
784 interesting end-user application in Kaleidoscope. At this point, Kaleidoscope
785 can build a variety of applications that are functional and can call functions
786 with side-effects, but it can't actually define and mutate a variable itself.
787 </p>
789 <p>Strikingly, variable mutation is an important feature of some
792 phase to your front-end. In the next chapter, we will describe how you can
793 add variable mutation without building SSA in your front-end.</p>
795 </div>
798 <!-- *********************************************************************** -->
800 <!-- *********************************************************************** -->
804 <p>
805 Here is the complete code listing for our running example, enhanced with the
806 if/then/else and for expressions.. To build this example, use:
807 </p>
810 <pre>
811 # Compile
812 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
813 # Run
814 ./toy
815 </pre>
816 </div>
821 <pre>
822 #include "llvm/DerivedTypes.h"
823 #include "llvm/ExecutionEngine/ExecutionEngine.h"
824 #include "llvm/Module.h"
825 #include "llvm/ModuleProvider.h"
826 #include "llvm/PassManager.h"
827 #include "llvm/Analysis/Verifier.h"
828 #include "llvm/Target/TargetData.h"
829 #include "llvm/Transforms/Scalar.h"
830 #include "llvm/Support/IRBuilder.h"
835 using namespace llvm;
837 //===----------------------------------------------------------------------===//
838 // Lexer
839 //===----------------------------------------------------------------------===//
842 // of these for known things.
843 enum Token {
844 tok_eof = -1,
846 // commands
849 // primary
852 // control
856 // operators
858 };
860 static std::string IdentifierStr; // Filled in if tok_identifier
861 static double NumVal; // Filled in if tok_number
863 /// gettok - Return the next token from standard input.
864 static int gettok() {
865 static int LastChar = ' ';
867 // Skip any whitespace.
868 while (isspace(LastChar))
869 LastChar = getchar();
871 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
872 IdentifierStr = LastChar;
873 while (isalnum((LastChar = getchar())))
874 IdentifierStr += LastChar;
876 if (IdentifierStr == "def") return tok_def;
877 if (IdentifierStr == "extern") return tok_extern;
878 if (IdentifierStr == "if") return tok_if;
879 if (IdentifierStr == "then") return tok_then;
880 if (IdentifierStr == "else") return tok_else;
881 if (IdentifierStr == "for") return tok_for;
882 if (IdentifierStr == "in") return tok_in;
883 if (IdentifierStr == "binary") return tok_binary;
884 if (IdentifierStr == "unary") return tok_unary;
885 return tok_identifier;
886 }
889 std::string NumStr;
890 do {
891 NumStr += LastChar;
892 LastChar = getchar();
893 } while (isdigit(LastChar) || LastChar == '.');
895 NumVal = strtod(NumStr.c_str(), 0);
896 return tok_number;
897 }
899 if (LastChar == '#') {
900 // Comment until end of line.
901 do LastChar = getchar();
904 if (LastChar != EOF)
905 return gettok();
906 }
908 // Check for end of file. Don't eat the EOF.
909 if (LastChar == EOF)
910 return tok_eof;
912 // Otherwise, just return the character as its ascii value.
913 int ThisChar = LastChar;
914 LastChar = getchar();
915 return ThisChar;
916 }
918 //===----------------------------------------------------------------------===//
919 // Abstract Syntax Tree (aka Parse Tree)
920 //===----------------------------------------------------------------------===//
922 /// ExprAST - Base class for all expression nodes.
923 class ExprAST {
924 public:
925 virtual ~ExprAST() {}
926 virtual Value *Codegen() = 0;
927 };
929 /// NumberExprAST - Expression class for numeric literals like "1.0".
930 class NumberExprAST : public ExprAST {
931 double Val;
932 public:
933 NumberExprAST(double val) : Val(val) {}
934 virtual Value *Codegen();
935 };
937 /// VariableExprAST - Expression class for referencing a variable, like "a".
938 class VariableExprAST : public ExprAST {
939 std::string Name;
940 public:
941 VariableExprAST(const std::string &name) : Name(name) {}
942 virtual Value *Codegen();
943 };
945 /// UnaryExprAST - Expression class for a unary operator.
946 class UnaryExprAST : public ExprAST {
947 char Opcode;
948 ExprAST *Operand;
949 public:
950 UnaryExprAST(char opcode, ExprAST *operand)
951 : Opcode(opcode), Operand(operand) {}
952 virtual Value *Codegen();
953 };
955 /// BinaryExprAST - Expression class for a binary operator.
956 class BinaryExprAST : public ExprAST {
957 char Op;
958 ExprAST *LHS, *RHS;
959 public:
960 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
961 : Op(op), LHS(lhs), RHS(rhs) {}
962 virtual Value *Codegen();
963 };
965 /// CallExprAST - Expression class for function calls.
966 class CallExprAST : public ExprAST {
967 std::string Callee;
969 public:
971 : Callee(callee), Args(args) {}
972 virtual Value *Codegen();
973 };
975 /// IfExprAST - Expression class for if/then/else.
976 class IfExprAST : public ExprAST {
977 ExprAST *Cond, *Then, *Else;
978 public:
979 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
980 : Cond(cond), Then(then), Else(_else) {}
981 virtual Value *Codegen();
982 };
984 /// ForExprAST - Expression class for for/in.
985 class ForExprAST : public ExprAST {
986 std::string VarName;
987 ExprAST *Start, *End, *Step, *Body;
988 public:
989 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
990 ExprAST *step, ExprAST *body)
991 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
992 virtual Value *Codegen();
993 };
995 /// PrototypeAST - This class represents the "prototype" for a function,
996 /// which captures its argument names as well as if it is an operator.
997 class PrototypeAST {
998 std::string Name;
1000 bool isOperator;
1001 unsigned Precedence; // Precedence if a binary op.
1002 public:
1004 bool isoperator = false, unsigned prec = 0)
1005 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1010 char getOperatorName() const {
1011 assert(isUnaryOp() || isBinaryOp());
1012 return Name[Name.size()-1];
1013 }
1015 unsigned getBinaryPrecedence() const { return Precedence; }
1017 Function *Codegen();
1018 };
1020 /// FunctionAST - This class represents a function definition itself.
1021 class FunctionAST {
1022 PrototypeAST *Proto;
1023 ExprAST *Body;
1024 public:
1025 FunctionAST(PrototypeAST *proto, ExprAST *body)
1026 : Proto(proto), Body(body) {}
1028 Function *Codegen();
1029 };
1031 //===----------------------------------------------------------------------===//
1032 // Parser
1033 //===----------------------------------------------------------------------===//
1035 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1036 /// token the parser it looking at. getNextToken reads another token from the
1037 /// lexer and updates CurTok with its results.
1038 static int CurTok;
1039 static int getNextToken() {
1040 return CurTok = gettok();
1041 }
1043 /// BinopPrecedence - This holds the precedence for each binary operator that is
1044 /// defined.
1047 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1048 static int GetTokPrecedence() {
1049 if (!isascii(CurTok))
1050 return -1;
1052 // Make sure it's a declared binop.
1053 int TokPrec = BinopPrecedence[CurTok];
1055 return TokPrec;
1056 }
1058 /// Error* - These are little helper functions for error handling.
1060 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1061 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1063 static ExprAST *ParseExpression();
1065 /// identifierexpr
1066 /// ::= identifier
1067 /// ::= identifier '(' expression* ')'
1068 static ExprAST *ParseIdentifierExpr() {
1069 std::string IdName = IdentifierStr;
1071 getNextToken(); // eat identifier.
1073 if (CurTok != '(') // Simple variable ref.
1074 return new VariableExprAST(IdName);
1076 // Call.
1077 getNextToken(); // eat (
1079 if (CurTok != ')') {
1080 while (1) {
1081 ExprAST *Arg = ParseExpression();
1082 if (!Arg) return 0;
1083 Args.push_back(Arg);
1085 if (CurTok == ')') break;
1087 if (CurTok != ',')
1088 return Error("Expected ')' or ',' in argument list");
1089 getNextToken();
1090 }
1091 }
1093 // Eat the ')'.
1094 getNextToken();
1096 return new CallExprAST(IdName, Args);
1097 }
1099 /// numberexpr ::= number
1100 static ExprAST *ParseNumberExpr() {
1101 ExprAST *Result = new NumberExprAST(NumVal);
1102 getNextToken(); // consume the number
1103 return Result;
1104 }
1106 /// parenexpr ::= '(' expression ')'
1107 static ExprAST *ParseParenExpr() {
1108 getNextToken(); // eat (.
1109 ExprAST *V = ParseExpression();
1110 if (!V) return 0;
1112 if (CurTok != ')')
1113 return Error("expected ')'");
1114 getNextToken(); // eat ).
1115 return V;
1116 }
1118 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1119 static ExprAST *ParseIfExpr() {
1120 getNextToken(); // eat the if.
1122 // condition.
1123 ExprAST *Cond = ParseExpression();
1124 if (!Cond) return 0;
1126 if (CurTok != tok_then)
1127 return Error("expected then");
1128 getNextToken(); // eat the then
1130 ExprAST *Then = ParseExpression();
1133 if (CurTok != tok_else)
1134 return Error("expected else");
1136 getNextToken();
1138 ExprAST *Else = ParseExpression();
1139 if (!Else) return 0;
1141 return new IfExprAST(Cond, Then, Else);
1142 }
1144 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1145 static ExprAST *ParseForExpr() {
1146 getNextToken(); // eat the for.
1148 if (CurTok != tok_identifier)
1149 return Error("expected identifier after for");
1151 std::string IdName = IdentifierStr;
1152 getNextToken(); // eat identifier.
1154 if (CurTok != '=')
1155 return Error("expected '=' after for");
1156 getNextToken(); // eat '='.
1159 ExprAST *Start = ParseExpression();
1161 if (CurTok != ',')
1162 return Error("expected ',' after for start value");
1163 getNextToken();
1165 ExprAST *End = ParseExpression();
1168 // The step value is optional.
1169 ExprAST *Step = 0;
1170 if (CurTok == ',') {
1171 getNextToken();
1172 Step = ParseExpression();
1174 }
1176 if (CurTok != tok_in)
1177 return Error("expected 'in' after for");
1178 getNextToken(); // eat 'in'.
1180 ExprAST *Body = ParseExpression();
1183 return new ForExprAST(IdName, Start, End, Step, Body);
1184 }
1187 /// primary
1188 /// ::= identifierexpr
1189 /// ::= numberexpr
1190 /// ::= parenexpr
1191 /// ::= ifexpr
1192 /// ::= forexpr
1193 static ExprAST *ParsePrimary() {
1194 switch (CurTok) {
1195 default: return Error("unknown token when expecting an expression");
1196 case tok_identifier: return ParseIdentifierExpr();
1197 case tok_number: return ParseNumberExpr();
1198 case '(': return ParseParenExpr();
1199 case tok_if: return ParseIfExpr();
1200 case tok_for: return ParseForExpr();
1201 }
1202 }
1204 /// unary
1205 /// ::= primary
1206 /// ::= '!' unary
1207 static ExprAST *ParseUnary() {
1208 // If the current token is not an operator, it must be a primary expr.
1209 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1210 return ParsePrimary();
1212 // If this is a unary operator, read it.
1213 int Opc = CurTok;
1214 getNextToken();
1215 if (ExprAST *Operand = ParseUnary())
1216 return new UnaryExprAST(Opc, Operand);
1217 return 0;
1218 }
1220 /// binoprhs
1221 /// ::= ('+' unary)*
1222 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1223 // If this is a binop, find its precedence.
1224 while (1) {
1225 int TokPrec = GetTokPrecedence();
1227 // If this is a binop that binds at least as tightly as the current binop,
1228 // consume it, otherwise we are done.
1229 if (TokPrec < ExprPrec)
1230 return LHS;
1232 // Okay, we know this is a binop.
1233 int BinOp = CurTok;
1234 getNextToken(); // eat binop
1236 // Parse the unary expression after the binary operator.
1237 ExprAST *RHS = ParseUnary();
1238 if (!RHS) return 0;
1240 // If BinOp binds less tightly with RHS than the operator after RHS, let
1241 // the pending operator take RHS as its LHS.
1242 int NextPrec = GetTokPrecedence();
1243 if (TokPrec < NextPrec) {
1244 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1246 }
1248 // Merge LHS/RHS.
1249 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1250 }
1251 }
1253 /// expression
1254 /// ::= unary binoprhs
1255 ///
1256 static ExprAST *ParseExpression() {
1257 ExprAST *LHS = ParseUnary();
1258 if (!LHS) return 0;
1260 return ParseBinOpRHS(0, LHS);
1261 }
1263 /// prototype
1264 /// ::= id '(' id* ')'
1265 /// ::= binary LETTER number? (id, id)
1266 /// ::= unary LETTER (id)
1267 static PrototypeAST *ParsePrototype() {
1268 std::string FnName;
1271 unsigned BinaryPrecedence = 30;
1273 switch (CurTok) {
1274 default:
1275 return ErrorP("Expected function name in prototype");
1276 case tok_identifier:
1277 FnName = IdentifierStr;
1278 Kind = 0;
1279 getNextToken();
1280 break;
1281 case tok_unary:
1282 getNextToken();
1283 if (!isascii(CurTok))
1284 return ErrorP("Expected unary operator");
1285 FnName = "unary";
1286 FnName += (char)CurTok;
1287 Kind = 1;
1288 getNextToken();
1289 break;
1290 case tok_binary:
1291 getNextToken();
1292 if (!isascii(CurTok))
1293 return ErrorP("Expected binary operator");
1294 FnName = "binary";
1295 FnName += (char)CurTok;
1296 Kind = 2;
1297 getNextToken();
1299 // Read the precedence if present.
1300 if (CurTok == tok_number) {
1302 return ErrorP("Invalid precedecnce: must be 1..100");
1303 BinaryPrecedence = (unsigned)NumVal;
1304 getNextToken();
1305 }
1306 break;
1307 }
1309 if (CurTok != '(')
1310 return ErrorP("Expected '(' in prototype");
1313 while (getNextToken() == tok_identifier)
1314 ArgNames.push_back(IdentifierStr);
1315 if (CurTok != ')')
1316 return ErrorP("Expected ')' in prototype");
1318 // success.
1319 getNextToken(); // eat ')'.
1321 // Verify right number of names for operator.
1322 if (Kind && ArgNames.size() != Kind)
1323 return ErrorP("Invalid number of operands for operator");
1325 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1326 }
1328 /// definition ::= 'def' prototype expression
1329 static FunctionAST *ParseDefinition() {
1330 getNextToken(); // eat def.
1331 PrototypeAST *Proto = ParsePrototype();
1334 if (ExprAST *E = ParseExpression())
1335 return new FunctionAST(Proto, E);
1336 return 0;
1337 }
1339 /// toplevelexpr ::= expression
1340 static FunctionAST *ParseTopLevelExpr() {
1341 if (ExprAST *E = ParseExpression()) {
1342 // Make an anonymous proto.
1344 return new FunctionAST(Proto, E);
1345 }
1346 return 0;
1347 }
1349 /// external ::= 'extern' prototype
1350 static PrototypeAST *ParseExtern() {
1351 getNextToken(); // eat extern.
1352 return ParsePrototype();
1353 }
1355 //===----------------------------------------------------------------------===//
1356 // Code Generation
1357 //===----------------------------------------------------------------------===//
1359 static Module *TheModule;
1360 static IRBuilder<> Builder;
1362 static FunctionPassManager *TheFPM;
1364 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1366 Value *NumberExprAST::Codegen() {
1367 return ConstantFP::get(APFloat(Val));
1368 }
1370 Value *VariableExprAST::Codegen() {
1371 // Look this variable up in the function.
1372 Value *V = NamedValues[Name];
1373 return V ? V : ErrorV("Unknown variable name");
1374 }
1376 Value *UnaryExprAST::Codegen() {
1377 Value *OperandV = Operand->Codegen();
1381 if (F == 0)
1382 return ErrorV("Unknown unary operator");
1384 return Builder.CreateCall(F, OperandV, "unop");
1385 }
1388 Value *BinaryExprAST::Codegen() {
1389 Value *L = LHS->Codegen();
1390 Value *R = RHS->Codegen();
1393 switch (Op) {
1394 case '+': return Builder.CreateAdd(L, R, "addtmp");
1395 case '-': return Builder.CreateSub(L, R, "subtmp");
1396 case '*': return Builder.CreateMul(L, R, "multmp");
1397 case '<':
1398 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1400 return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
1401 default: break;
1402 }
1404 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1405 // a call to it.
1409 Value *Ops[] = { L, R };
1411 }
1413 Value *CallExprAST::Codegen() {
1414 // Look up the name in the global module table.
1415 Function *CalleeF = TheModule->getFunction(Callee);
1416 if (CalleeF == 0)
1417 return ErrorV("Unknown function referenced");
1419 // If argument mismatch error.
1420 if (CalleeF->arg_size() != Args.size())
1421 return ErrorV("Incorrect # arguments passed");
1424 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1425 ArgsV.push_back(Args[i]->Codegen());
1427 }
1429 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1430 }
1432 Value *IfExprAST::Codegen() {
1433 Value *CondV = Cond->Codegen();
1436 // Convert condition to a bool by comparing equal to 0.0.
1437 CondV = Builder.CreateFCmpONE(CondV,
1438 ConstantFP::get(APFloat(0.0)),
1439 "ifcond");
1441 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1443 // Create blocks for the then and else cases. Insert the 'then' block at the
1444 // end of the function.
1445 BasicBlock *ThenBB = BasicBlock::Create("then", TheFunction);
1446 BasicBlock *ElseBB = BasicBlock::Create("else");
1447 BasicBlock *MergeBB = BasicBlock::Create("ifcont");
1449 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1451 // Emit then value.
1452 Builder.SetInsertPoint(ThenBB);
1454 Value *ThenV = Then->Codegen();
1457 Builder.CreateBr(MergeBB);
1458 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1459 ThenBB = Builder.GetInsertBlock();
1461 // Emit else block.
1462 TheFunction->getBasicBlockList().push_back(ElseBB);
1463 Builder.SetInsertPoint(ElseBB);
1465 Value *ElseV = Else->Codegen();
1468 Builder.CreateBr(MergeBB);
1469 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1470 ElseBB = Builder.GetInsertBlock();
1472 // Emit merge block.
1473 TheFunction->getBasicBlockList().push_back(MergeBB);
1474 Builder.SetInsertPoint(MergeBB);
1475 PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
1477 PN->addIncoming(ThenV, ThenBB);
1478 PN->addIncoming(ElseV, ElseBB);
1479 return PN;
1480 }
1482 Value *ForExprAST::Codegen() {
1483 // Output this as:
1484 // ...
1485 // start = startexpr
1486 // goto loop
1487 // loop:
1488 // variable = phi [start, loopheader], [nextvariable, loopend]
1489 // ...
1490 // bodyexpr
1491 // ...
1492 // loopend:
1493 // step = stepexpr
1494 // nextvariable = variable + step
1495 // endcond = endexpr
1496 // br endcond, loop, endloop
1497 // outloop:
1499 // Emit the start code first, without 'variable' in scope.
1500 Value *StartVal = Start->Codegen();
1503 // Make the new basic block for the loop header, inserting after current
1504 // block.
1505 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1506 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1507 BasicBlock *LoopBB = BasicBlock::Create("loop", TheFunction);
1509 // Insert an explicit fall through from the current block to the LoopBB.
1510 Builder.CreateBr(LoopBB);
1512 // Start insertion in LoopBB.
1513 Builder.SetInsertPoint(LoopBB);
1515 // Start the PHI node with an entry for Start.
1516 PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
1517 Variable->addIncoming(StartVal, PreheaderBB);
1519 // Within the loop, the variable is defined equal to the PHI node. If it
1520 // shadows an existing variable, we have to restore it, so save it now.
1521 Value *OldVal = NamedValues[VarName];
1522 NamedValues[VarName] = Variable;
1524 // Emit the body of the loop. This, like any other expr, can change the
1525 // current BB. Note that we ignore the value computed by the body, but don't
1526 // allow an error.
1528 return 0;
1530 // Emit the step value.
1531 Value *StepVal;
1532 if (Step) {
1533 StepVal = Step->Codegen();
1535 } else {
1536 // If not specified, use 1.0.
1537 StepVal = ConstantFP::get(APFloat(1.0));
1538 }
1540 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
1542 // Compute the end condition.
1543 Value *EndCond = End->Codegen();
1544 if (EndCond == 0) return EndCond;
1546 // Convert condition to a bool by comparing equal to 0.0.
1547 EndCond = Builder.CreateFCmpONE(EndCond,
1548 ConstantFP::get(APFloat(0.0)),
1549 "loopcond");
1551 // Create the "after loop" block and insert it.
1552 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1553 BasicBlock *AfterBB = BasicBlock::Create("afterloop", TheFunction);
1555 // Insert the conditional branch into the end of LoopEndBB.
1556 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1558 // Any new code will be inserted in AfterBB.
1559 Builder.SetInsertPoint(AfterBB);
1561 // Add a new entry to the PHI node for the backedge.
1562 Variable->addIncoming(NextVar, LoopEndBB);
1564 // Restore the unshadowed variable.
1565 if (OldVal)
1566 NamedValues[VarName] = OldVal;
1567 else
1568 NamedValues.erase(VarName);
1571 // for expr always returns 0.0.
1572 return Constant::getNullValue(Type::DoubleTy);
1573 }
1575 Function *PrototypeAST::Codegen() {
1576 // Make the function type: double(double,double) etc.
1578 FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
1580 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1582 // If F conflicted, there was already something named 'Name'. If it has a
1583 // body, don't allow redefinition or reextern.
1584 if (F->getName() != Name) {
1585 // Delete the one we just made and get the existing one.
1586 F->eraseFromParent();
1587 F = TheModule->getFunction(Name);
1589 // If F already has a body, reject this.
1590 if (!F->empty()) {
1591 ErrorF("redefinition of function");
1592 return 0;
1593 }
1595 // If F took a different number of args, reject.
1596 if (F->arg_size() != Args.size()) {
1597 ErrorF("redefinition of function with different # args");
1598 return 0;
1599 }
1600 }
1602 // Set names for all arguments.
1603 unsigned Idx = 0;
1604 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1605 ++AI, ++Idx) {
1606 AI->setName(Args[Idx]);
1608 // Add arguments to variable symbol table.
1609 NamedValues[Args[Idx]] = AI;
1610 }
1612 return F;
1613 }
1615 Function *FunctionAST::Codegen() {
1616 NamedValues.clear();
1618 Function *TheFunction = Proto->Codegen();
1619 if (TheFunction == 0)
1620 return 0;
1622 // If this is an operator, install it.
1623 if (Proto->isBinaryOp())
1626 // Create a new basic block to start insertion into.
1627 BasicBlock *BB = BasicBlock::Create("entry", TheFunction);
1628 Builder.SetInsertPoint(BB);
1630 if (Value *RetVal = Body->Codegen()) {
1631 // Finish off the function.
1632 Builder.CreateRet(RetVal);
1634 // Validate the generated code, checking for consistency.
1635 verifyFunction(*TheFunction);
1637 // Optimize the function.
1638 TheFPM->run(*TheFunction);
1640 return TheFunction;
1641 }
1643 // Error reading body, remove function.
1644 TheFunction->eraseFromParent();
1646 if (Proto->isBinaryOp())
1647 BinopPrecedence.erase(Proto->getOperatorName());
1648 return 0;
1649 }
1651 //===----------------------------------------------------------------------===//
1652 // Top-Level parsing and JIT Driver
1653 //===----------------------------------------------------------------------===//
1655 static ExecutionEngine *TheExecutionEngine;
1657 static void HandleDefinition() {
1658 if (FunctionAST *F = ParseDefinition()) {
1659 if (Function *LF = F->Codegen()) {
1660 fprintf(stderr, "Read function definition:");
1661 LF->dump();
1662 }
1663 } else {
1664 // Skip token for error recovery.
1665 getNextToken();
1666 }
1667 }
1669 static void HandleExtern() {
1670 if (PrototypeAST *P = ParseExtern()) {
1671 if (Function *F = P->Codegen()) {
1672 fprintf(stderr, "Read extern: ");
1673 F->dump();
1674 }
1675 } else {
1676 // Skip token for error recovery.
1677 getNextToken();
1678 }
1679 }
1681 static void HandleTopLevelExpression() {
1682 // Evaluate a top level expression into an anonymous function.
1683 if (FunctionAST *F = ParseTopLevelExpr()) {
1684 if (Function *LF = F->Codegen()) {
1685 // JIT the function, returning a function pointer.
1686 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1688 // Cast it to the right type (takes no arguments, returns a double) so we
1689 // can call it as a native function.
1690 double (*FP)() = (double (*)())FPtr;
1691 fprintf(stderr, "Evaluated to %f\n", FP());
1692 }
1693 } else {
1694 // Skip token for error recovery.
1695 getNextToken();
1696 }
1697 }
1699 /// top ::= definition | external | expression | ';'
1700 static void MainLoop() {
1701 while (1) {
1702 fprintf(stderr, "ready> ");
1703 switch (CurTok) {
1704 case tok_eof: return;
1705 case ';': getNextToken(); break; // ignore top level semicolons.
1706 case tok_def: HandleDefinition(); break;
1707 case tok_extern: HandleExtern(); break;
1708 default: HandleTopLevelExpression(); break;
1709 }
1710 }
1711 }
1715 //===----------------------------------------------------------------------===//
1717 //===----------------------------------------------------------------------===//
1719 /// putchard - putchar that takes a double and returns 0.
1720 extern "C"
1721 double putchard(double X) {
1722 putchar((char)X);
1723 return 0;
1724 }
1727 extern "C"
1728 double printd(double X) {
1729 printf("%f\n", X);
1730 return 0;
1731 }
1733 //===----------------------------------------------------------------------===//
1734 // Main driver code.
1735 //===----------------------------------------------------------------------===//
1737 int main() {
1738 // Install standard binary operators.
1739 // 1 is lowest precedence.
1741 BinopPrecedence['+'] = 20;
1742 BinopPrecedence['-'] = 20;
1743 BinopPrecedence['*'] = 40; // highest.
1745 // Prime the first token.
1746 fprintf(stderr, "ready> ");
1747 getNextToken();
1749 // Make the module, which holds all the code.
1750 TheModule = new Module("my cool jit");
1752 // Create the JIT.
1753 TheExecutionEngine = ExecutionEngine::create(TheModule);
1755 {
1756 ExistingModuleProvider OurModuleProvider(TheModule);
1757 FunctionPassManager OurFPM(&OurModuleProvider);
1759 // Set up the optimizer pipeline. Start with registering info about how the
1760 // target lays out data structures.
1761 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1762 // Do simple "peephole" optimizations and bit-twiddling optzns.
1763 OurFPM.add(createInstructionCombiningPass());
1764 // Reassociate expressions.
1765 OurFPM.add(createReassociatePass());
1766 // Eliminate Common SubExpressions.
1767 OurFPM.add(createGVNPass());
1768 // Simplify the control flow graph (deleting unreachable blocks, etc).
1769 OurFPM.add(createCFGSimplificationPass());
1770 // Set the global so the code gen can use this.
1771 TheFPM = &OurFPM;
1773 // Run the main "interpreter loop" now.
1774 MainLoop();
1776 TheFPM = 0;
1778 // Print out all of the generated code.
1779 TheModule->dump();
1780 } // Free module provider (and thus the module) and pass manager.
1782 return 0;
1783 }
1784 </pre>
1785 </div>
1787 <a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a>
1788 </div>
1790 <!-- *********************************************************************** -->
1791 <hr>
1792 <address>
1801 </address>
1802 </body>
1803 </html>