| blob | a61c82cd4726c45bef68805a485b9daaed944861 |
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::getDoubleTy(getGlobalContext()), "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(getGlobalContext(), "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/LLVMContext.h"
825 #include "llvm/Module.h"
826 #include "llvm/ModuleProvider.h"
827 #include "llvm/PassManager.h"
828 #include "llvm/Analysis/Verifier.h"
829 #include "llvm/Target/TargetData.h"
830 #include "llvm/Transforms/Scalar.h"
831 #include "llvm/Support/IRBuilder.h"
836 using namespace llvm;
838 //===----------------------------------------------------------------------===//
839 // Lexer
840 //===----------------------------------------------------------------------===//
843 // of these for known things.
844 enum Token {
845 tok_eof = -1,
847 // commands
850 // primary
853 // control
857 // operators
859 };
861 static std::string IdentifierStr; // Filled in if tok_identifier
862 static double NumVal; // Filled in if tok_number
864 /// gettok - Return the next token from standard input.
865 static int gettok() {
866 static int LastChar = ' ';
868 // Skip any whitespace.
869 while (isspace(LastChar))
870 LastChar = getchar();
872 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
873 IdentifierStr = LastChar;
874 while (isalnum((LastChar = getchar())))
875 IdentifierStr += LastChar;
877 if (IdentifierStr == "def") return tok_def;
878 if (IdentifierStr == "extern") return tok_extern;
879 if (IdentifierStr == "if") return tok_if;
880 if (IdentifierStr == "then") return tok_then;
881 if (IdentifierStr == "else") return tok_else;
882 if (IdentifierStr == "for") return tok_for;
883 if (IdentifierStr == "in") return tok_in;
884 if (IdentifierStr == "binary") return tok_binary;
885 if (IdentifierStr == "unary") return tok_unary;
886 return tok_identifier;
887 }
890 std::string NumStr;
891 do {
892 NumStr += LastChar;
893 LastChar = getchar();
894 } while (isdigit(LastChar) || LastChar == '.');
896 NumVal = strtod(NumStr.c_str(), 0);
897 return tok_number;
898 }
900 if (LastChar == '#') {
901 // Comment until end of line.
902 do LastChar = getchar();
905 if (LastChar != EOF)
906 return gettok();
907 }
909 // Check for end of file. Don't eat the EOF.
910 if (LastChar == EOF)
911 return tok_eof;
913 // Otherwise, just return the character as its ascii value.
914 int ThisChar = LastChar;
915 LastChar = getchar();
916 return ThisChar;
917 }
919 //===----------------------------------------------------------------------===//
920 // Abstract Syntax Tree (aka Parse Tree)
921 //===----------------------------------------------------------------------===//
923 /// ExprAST - Base class for all expression nodes.
924 class ExprAST {
925 public:
926 virtual ~ExprAST() {}
927 virtual Value *Codegen() = 0;
928 };
930 /// NumberExprAST - Expression class for numeric literals like "1.0".
931 class NumberExprAST : public ExprAST {
932 double Val;
933 public:
934 NumberExprAST(double val) : Val(val) {}
935 virtual Value *Codegen();
936 };
938 /// VariableExprAST - Expression class for referencing a variable, like "a".
939 class VariableExprAST : public ExprAST {
940 std::string Name;
941 public:
942 VariableExprAST(const std::string &name) : Name(name) {}
943 virtual Value *Codegen();
944 };
946 /// UnaryExprAST - Expression class for a unary operator.
947 class UnaryExprAST : public ExprAST {
948 char Opcode;
949 ExprAST *Operand;
950 public:
951 UnaryExprAST(char opcode, ExprAST *operand)
952 : Opcode(opcode), Operand(operand) {}
953 virtual Value *Codegen();
954 };
956 /// BinaryExprAST - Expression class for a binary operator.
957 class BinaryExprAST : public ExprAST {
958 char Op;
959 ExprAST *LHS, *RHS;
960 public:
961 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
962 : Op(op), LHS(lhs), RHS(rhs) {}
963 virtual Value *Codegen();
964 };
966 /// CallExprAST - Expression class for function calls.
967 class CallExprAST : public ExprAST {
968 std::string Callee;
970 public:
972 : Callee(callee), Args(args) {}
973 virtual Value *Codegen();
974 };
976 /// IfExprAST - Expression class for if/then/else.
977 class IfExprAST : public ExprAST {
978 ExprAST *Cond, *Then, *Else;
979 public:
980 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
981 : Cond(cond), Then(then), Else(_else) {}
982 virtual Value *Codegen();
983 };
985 /// ForExprAST - Expression class for for/in.
986 class ForExprAST : public ExprAST {
987 std::string VarName;
988 ExprAST *Start, *End, *Step, *Body;
989 public:
990 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
991 ExprAST *step, ExprAST *body)
992 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
993 virtual Value *Codegen();
994 };
996 /// PrototypeAST - This class represents the "prototype" for a function,
997 /// which captures its argument names as well as if it is an operator.
998 class PrototypeAST {
999 std::string Name;
1001 bool isOperator;
1002 unsigned Precedence; // Precedence if a binary op.
1003 public:
1005 bool isoperator = false, unsigned prec = 0)
1006 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1011 char getOperatorName() const {
1012 assert(isUnaryOp() || isBinaryOp());
1013 return Name[Name.size()-1];
1014 }
1016 unsigned getBinaryPrecedence() const { return Precedence; }
1018 Function *Codegen();
1019 };
1021 /// FunctionAST - This class represents a function definition itself.
1022 class FunctionAST {
1023 PrototypeAST *Proto;
1024 ExprAST *Body;
1025 public:
1026 FunctionAST(PrototypeAST *proto, ExprAST *body)
1027 : Proto(proto), Body(body) {}
1029 Function *Codegen();
1030 };
1032 //===----------------------------------------------------------------------===//
1033 // Parser
1034 //===----------------------------------------------------------------------===//
1036 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1037 /// token the parser it looking at. getNextToken reads another token from the
1038 /// lexer and updates CurTok with its results.
1039 static int CurTok;
1040 static int getNextToken() {
1041 return CurTok = gettok();
1042 }
1044 /// BinopPrecedence - This holds the precedence for each binary operator that is
1045 /// defined.
1048 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1049 static int GetTokPrecedence() {
1050 if (!isascii(CurTok))
1051 return -1;
1053 // Make sure it's a declared binop.
1054 int TokPrec = BinopPrecedence[CurTok];
1056 return TokPrec;
1057 }
1059 /// Error* - These are little helper functions for error handling.
1061 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1062 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1064 static ExprAST *ParseExpression();
1066 /// identifierexpr
1067 /// ::= identifier
1068 /// ::= identifier '(' expression* ')'
1069 static ExprAST *ParseIdentifierExpr() {
1070 std::string IdName = IdentifierStr;
1072 getNextToken(); // eat identifier.
1074 if (CurTok != '(') // Simple variable ref.
1075 return new VariableExprAST(IdName);
1077 // Call.
1078 getNextToken(); // eat (
1080 if (CurTok != ')') {
1081 while (1) {
1082 ExprAST *Arg = ParseExpression();
1083 if (!Arg) return 0;
1084 Args.push_back(Arg);
1086 if (CurTok == ')') break;
1088 if (CurTok != ',')
1089 return Error("Expected ')' or ',' in argument list");
1090 getNextToken();
1091 }
1092 }
1094 // Eat the ')'.
1095 getNextToken();
1097 return new CallExprAST(IdName, Args);
1098 }
1100 /// numberexpr ::= number
1101 static ExprAST *ParseNumberExpr() {
1102 ExprAST *Result = new NumberExprAST(NumVal);
1103 getNextToken(); // consume the number
1104 return Result;
1105 }
1107 /// parenexpr ::= '(' expression ')'
1108 static ExprAST *ParseParenExpr() {
1109 getNextToken(); // eat (.
1110 ExprAST *V = ParseExpression();
1111 if (!V) return 0;
1113 if (CurTok != ')')
1114 return Error("expected ')'");
1115 getNextToken(); // eat ).
1116 return V;
1117 }
1119 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1120 static ExprAST *ParseIfExpr() {
1121 getNextToken(); // eat the if.
1123 // condition.
1124 ExprAST *Cond = ParseExpression();
1125 if (!Cond) return 0;
1127 if (CurTok != tok_then)
1128 return Error("expected then");
1129 getNextToken(); // eat the then
1131 ExprAST *Then = ParseExpression();
1134 if (CurTok != tok_else)
1135 return Error("expected else");
1137 getNextToken();
1139 ExprAST *Else = ParseExpression();
1140 if (!Else) return 0;
1142 return new IfExprAST(Cond, Then, Else);
1143 }
1145 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1146 static ExprAST *ParseForExpr() {
1147 getNextToken(); // eat the for.
1149 if (CurTok != tok_identifier)
1150 return Error("expected identifier after for");
1152 std::string IdName = IdentifierStr;
1153 getNextToken(); // eat identifier.
1155 if (CurTok != '=')
1156 return Error("expected '=' after for");
1157 getNextToken(); // eat '='.
1160 ExprAST *Start = ParseExpression();
1162 if (CurTok != ',')
1163 return Error("expected ',' after for start value");
1164 getNextToken();
1166 ExprAST *End = ParseExpression();
1169 // The step value is optional.
1170 ExprAST *Step = 0;
1171 if (CurTok == ',') {
1172 getNextToken();
1173 Step = ParseExpression();
1175 }
1177 if (CurTok != tok_in)
1178 return Error("expected 'in' after for");
1179 getNextToken(); // eat 'in'.
1181 ExprAST *Body = ParseExpression();
1184 return new ForExprAST(IdName, Start, End, Step, Body);
1185 }
1188 /// primary
1189 /// ::= identifierexpr
1190 /// ::= numberexpr
1191 /// ::= parenexpr
1192 /// ::= ifexpr
1193 /// ::= forexpr
1194 static ExprAST *ParsePrimary() {
1195 switch (CurTok) {
1196 default: return Error("unknown token when expecting an expression");
1197 case tok_identifier: return ParseIdentifierExpr();
1198 case tok_number: return ParseNumberExpr();
1199 case '(': return ParseParenExpr();
1200 case tok_if: return ParseIfExpr();
1201 case tok_for: return ParseForExpr();
1202 }
1203 }
1205 /// unary
1206 /// ::= primary
1207 /// ::= '!' unary
1208 static ExprAST *ParseUnary() {
1209 // If the current token is not an operator, it must be a primary expr.
1210 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1211 return ParsePrimary();
1213 // If this is a unary operator, read it.
1214 int Opc = CurTok;
1215 getNextToken();
1216 if (ExprAST *Operand = ParseUnary())
1217 return new UnaryExprAST(Opc, Operand);
1218 return 0;
1219 }
1221 /// binoprhs
1222 /// ::= ('+' unary)*
1223 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1224 // If this is a binop, find its precedence.
1225 while (1) {
1226 int TokPrec = GetTokPrecedence();
1228 // If this is a binop that binds at least as tightly as the current binop,
1229 // consume it, otherwise we are done.
1230 if (TokPrec < ExprPrec)
1231 return LHS;
1233 // Okay, we know this is a binop.
1234 int BinOp = CurTok;
1235 getNextToken(); // eat binop
1237 // Parse the unary expression after the binary operator.
1238 ExprAST *RHS = ParseUnary();
1239 if (!RHS) return 0;
1241 // If BinOp binds less tightly with RHS than the operator after RHS, let
1242 // the pending operator take RHS as its LHS.
1243 int NextPrec = GetTokPrecedence();
1244 if (TokPrec < NextPrec) {
1245 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1247 }
1249 // Merge LHS/RHS.
1250 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1251 }
1252 }
1254 /// expression
1255 /// ::= unary binoprhs
1256 ///
1257 static ExprAST *ParseExpression() {
1258 ExprAST *LHS = ParseUnary();
1259 if (!LHS) return 0;
1261 return ParseBinOpRHS(0, LHS);
1262 }
1264 /// prototype
1265 /// ::= id '(' id* ')'
1266 /// ::= binary LETTER number? (id, id)
1267 /// ::= unary LETTER (id)
1268 static PrototypeAST *ParsePrototype() {
1269 std::string FnName;
1272 unsigned BinaryPrecedence = 30;
1274 switch (CurTok) {
1275 default:
1276 return ErrorP("Expected function name in prototype");
1277 case tok_identifier:
1278 FnName = IdentifierStr;
1279 Kind = 0;
1280 getNextToken();
1281 break;
1282 case tok_unary:
1283 getNextToken();
1284 if (!isascii(CurTok))
1285 return ErrorP("Expected unary operator");
1286 FnName = "unary";
1287 FnName += (char)CurTok;
1288 Kind = 1;
1289 getNextToken();
1290 break;
1291 case tok_binary:
1292 getNextToken();
1293 if (!isascii(CurTok))
1294 return ErrorP("Expected binary operator");
1295 FnName = "binary";
1296 FnName += (char)CurTok;
1297 Kind = 2;
1298 getNextToken();
1300 // Read the precedence if present.
1301 if (CurTok == tok_number) {
1303 return ErrorP("Invalid precedecnce: must be 1..100");
1304 BinaryPrecedence = (unsigned)NumVal;
1305 getNextToken();
1306 }
1307 break;
1308 }
1310 if (CurTok != '(')
1311 return ErrorP("Expected '(' in prototype");
1314 while (getNextToken() == tok_identifier)
1315 ArgNames.push_back(IdentifierStr);
1316 if (CurTok != ')')
1317 return ErrorP("Expected ')' in prototype");
1319 // success.
1320 getNextToken(); // eat ')'.
1322 // Verify right number of names for operator.
1323 if (Kind && ArgNames.size() != Kind)
1324 return ErrorP("Invalid number of operands for operator");
1326 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1327 }
1329 /// definition ::= 'def' prototype expression
1330 static FunctionAST *ParseDefinition() {
1331 getNextToken(); // eat def.
1332 PrototypeAST *Proto = ParsePrototype();
1335 if (ExprAST *E = ParseExpression())
1336 return new FunctionAST(Proto, E);
1337 return 0;
1338 }
1340 /// toplevelexpr ::= expression
1341 static FunctionAST *ParseTopLevelExpr() {
1342 if (ExprAST *E = ParseExpression()) {
1343 // Make an anonymous proto.
1345 return new FunctionAST(Proto, E);
1346 }
1347 return 0;
1348 }
1350 /// external ::= 'extern' prototype
1351 static PrototypeAST *ParseExtern() {
1352 getNextToken(); // eat extern.
1353 return ParsePrototype();
1354 }
1356 //===----------------------------------------------------------------------===//
1357 // Code Generation
1358 //===----------------------------------------------------------------------===//
1360 static Module *TheModule;
1361 static IRBuilder<> Builder(getGlobalContext());
1363 static FunctionPassManager *TheFPM;
1365 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1367 Value *NumberExprAST::Codegen() {
1368 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1369 }
1371 Value *VariableExprAST::Codegen() {
1372 // Look this variable up in the function.
1373 Value *V = NamedValues[Name];
1374 return V ? V : ErrorV("Unknown variable name");
1375 }
1377 Value *UnaryExprAST::Codegen() {
1378 Value *OperandV = Operand->Codegen();
1382 if (F == 0)
1383 return ErrorV("Unknown unary operator");
1385 return Builder.CreateCall(F, OperandV, "unop");
1386 }
1389 Value *BinaryExprAST::Codegen() {
1390 Value *L = LHS->Codegen();
1391 Value *R = RHS->Codegen();
1394 switch (Op) {
1395 case '+': return Builder.CreateAdd(L, R, "addtmp");
1396 case '-': return Builder.CreateSub(L, R, "subtmp");
1397 case '*': return Builder.CreateMul(L, R, "multmp");
1398 case '<':
1399 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1401 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), "booltmp");
1402 default: break;
1403 }
1405 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1406 // a call to it.
1410 Value *Ops[] = { L, R };
1412 }
1414 Value *CallExprAST::Codegen() {
1415 // Look up the name in the global module table.
1416 Function *CalleeF = TheModule->getFunction(Callee);
1417 if (CalleeF == 0)
1418 return ErrorV("Unknown function referenced");
1420 // If argument mismatch error.
1421 if (CalleeF->arg_size() != Args.size())
1422 return ErrorV("Incorrect # arguments passed");
1425 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1426 ArgsV.push_back(Args[i]->Codegen());
1428 }
1430 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1431 }
1433 Value *IfExprAST::Codegen() {
1434 Value *CondV = Cond->Codegen();
1437 // Convert condition to a bool by comparing equal to 0.0.
1438 CondV = Builder.CreateFCmpONE(CondV,
1439 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1440 "ifcond");
1442 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1444 // Create blocks for the then and else cases. Insert the 'then' block at the
1445 // end of the function.
1446 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1447 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1448 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1450 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1452 // Emit then value.
1453 Builder.SetInsertPoint(ThenBB);
1455 Value *ThenV = Then->Codegen();
1458 Builder.CreateBr(MergeBB);
1459 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1460 ThenBB = Builder.GetInsertBlock();
1462 // Emit else block.
1463 TheFunction->getBasicBlockList().push_back(ElseBB);
1464 Builder.SetInsertPoint(ElseBB);
1466 Value *ElseV = Else->Codegen();
1469 Builder.CreateBr(MergeBB);
1470 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1471 ElseBB = Builder.GetInsertBlock();
1473 // Emit merge block.
1474 TheFunction->getBasicBlockList().push_back(MergeBB);
1475 Builder.SetInsertPoint(MergeBB);
1476 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), "iftmp");
1478 PN->addIncoming(ThenV, ThenBB);
1479 PN->addIncoming(ElseV, ElseBB);
1480 return PN;
1481 }
1483 Value *ForExprAST::Codegen() {
1484 // Output this as:
1485 // ...
1486 // start = startexpr
1487 // goto loop
1488 // loop:
1489 // variable = phi [start, loopheader], [nextvariable, loopend]
1490 // ...
1491 // bodyexpr
1492 // ...
1493 // loopend:
1494 // step = stepexpr
1495 // nextvariable = variable + step
1496 // endcond = endexpr
1497 // br endcond, loop, endloop
1498 // outloop:
1500 // Emit the start code first, without 'variable' in scope.
1501 Value *StartVal = Start->Codegen();
1504 // Make the new basic block for the loop header, inserting after current
1505 // block.
1506 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1507 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1508 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1510 // Insert an explicit fall through from the current block to the LoopBB.
1511 Builder.CreateBr(LoopBB);
1513 // Start insertion in LoopBB.
1514 Builder.SetInsertPoint(LoopBB);
1516 // Start the PHI node with an entry for Start.
1517 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
1518 Variable->addIncoming(StartVal, PreheaderBB);
1520 // Within the loop, the variable is defined equal to the PHI node. If it
1521 // shadows an existing variable, we have to restore it, so save it now.
1522 Value *OldVal = NamedValues[VarName];
1523 NamedValues[VarName] = Variable;
1525 // Emit the body of the loop. This, like any other expr, can change the
1526 // current BB. Note that we ignore the value computed by the body, but don't
1527 // allow an error.
1529 return 0;
1531 // Emit the step value.
1532 Value *StepVal;
1533 if (Step) {
1534 StepVal = Step->Codegen();
1536 } else {
1537 // If not specified, use 1.0.
1538 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1539 }
1541 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
1543 // Compute the end condition.
1544 Value *EndCond = End->Codegen();
1545 if (EndCond == 0) return EndCond;
1547 // Convert condition to a bool by comparing equal to 0.0.
1548 EndCond = Builder.CreateFCmpONE(EndCond,
1549 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1550 "loopcond");
1552 // Create the "after loop" block and insert it.
1553 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1554 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1556 // Insert the conditional branch into the end of LoopEndBB.
1557 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1559 // Any new code will be inserted in AfterBB.
1560 Builder.SetInsertPoint(AfterBB);
1562 // Add a new entry to the PHI node for the backedge.
1563 Variable->addIncoming(NextVar, LoopEndBB);
1565 // Restore the unshadowed variable.
1566 if (OldVal)
1567 NamedValues[VarName] = OldVal;
1568 else
1569 NamedValues.erase(VarName);
1572 // for expr always returns 0.0.
1573 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1574 }
1576 Function *PrototypeAST::Codegen() {
1577 // Make the function type: double(double,double) etc.
1579 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false);
1581 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1583 // If F conflicted, there was already something named 'Name'. If it has a
1584 // body, don't allow redefinition or reextern.
1585 if (F->getName() != Name) {
1586 // Delete the one we just made and get the existing one.
1587 F->eraseFromParent();
1588 F = TheModule->getFunction(Name);
1590 // If F already has a body, reject this.
1591 if (!F->empty()) {
1592 ErrorF("redefinition of function");
1593 return 0;
1594 }
1596 // If F took a different number of args, reject.
1597 if (F->arg_size() != Args.size()) {
1598 ErrorF("redefinition of function with different # args");
1599 return 0;
1600 }
1601 }
1603 // Set names for all arguments.
1604 unsigned Idx = 0;
1605 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1606 ++AI, ++Idx) {
1607 AI->setName(Args[Idx]);
1609 // Add arguments to variable symbol table.
1610 NamedValues[Args[Idx]] = AI;
1611 }
1613 return F;
1614 }
1616 Function *FunctionAST::Codegen() {
1617 NamedValues.clear();
1619 Function *TheFunction = Proto->Codegen();
1620 if (TheFunction == 0)
1621 return 0;
1623 // If this is an operator, install it.
1624 if (Proto->isBinaryOp())
1627 // Create a new basic block to start insertion into.
1628 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1629 Builder.SetInsertPoint(BB);
1631 if (Value *RetVal = Body->Codegen()) {
1632 // Finish off the function.
1633 Builder.CreateRet(RetVal);
1635 // Validate the generated code, checking for consistency.
1636 verifyFunction(*TheFunction);
1638 // Optimize the function.
1639 TheFPM->run(*TheFunction);
1641 return TheFunction;
1642 }
1644 // Error reading body, remove function.
1645 TheFunction->eraseFromParent();
1647 if (Proto->isBinaryOp())
1648 BinopPrecedence.erase(Proto->getOperatorName());
1649 return 0;
1650 }
1652 //===----------------------------------------------------------------------===//
1653 // Top-Level parsing and JIT Driver
1654 //===----------------------------------------------------------------------===//
1656 static ExecutionEngine *TheExecutionEngine;
1658 static void HandleDefinition() {
1659 if (FunctionAST *F = ParseDefinition()) {
1660 if (Function *LF = F->Codegen()) {
1661 fprintf(stderr, "Read function definition:");
1662 LF->dump();
1663 }
1664 } else {
1665 // Skip token for error recovery.
1666 getNextToken();
1667 }
1668 }
1670 static void HandleExtern() {
1671 if (PrototypeAST *P = ParseExtern()) {
1672 if (Function *F = P->Codegen()) {
1673 fprintf(stderr, "Read extern: ");
1674 F->dump();
1675 }
1676 } else {
1677 // Skip token for error recovery.
1678 getNextToken();
1679 }
1680 }
1682 static void HandleTopLevelExpression() {
1683 // Evaluate a top level expression into an anonymous function.
1684 if (FunctionAST *F = ParseTopLevelExpr()) {
1685 if (Function *LF = F->Codegen()) {
1686 // JIT the function, returning a function pointer.
1687 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1689 // Cast it to the right type (takes no arguments, returns a double) so we
1690 // can call it as a native function.
1691 double (*FP)() = (double (*)())FPtr;
1692 fprintf(stderr, "Evaluated to %f\n", FP());
1693 }
1694 } else {
1695 // Skip token for error recovery.
1696 getNextToken();
1697 }
1698 }
1700 /// top ::= definition | external | expression | ';'
1701 static void MainLoop() {
1702 while (1) {
1703 fprintf(stderr, "ready> ");
1704 switch (CurTok) {
1705 case tok_eof: return;
1706 case ';': getNextToken(); break; // ignore top level semicolons.
1707 case tok_def: HandleDefinition(); break;
1708 case tok_extern: HandleExtern(); break;
1709 default: HandleTopLevelExpression(); break;
1710 }
1711 }
1712 }
1716 //===----------------------------------------------------------------------===//
1718 //===----------------------------------------------------------------------===//
1720 /// putchard - putchar that takes a double and returns 0.
1721 extern "C"
1722 double putchard(double X) {
1723 putchar((char)X);
1724 return 0;
1725 }
1728 extern "C"
1729 double printd(double X) {
1730 printf("%f\n", X);
1731 return 0;
1732 }
1734 //===----------------------------------------------------------------------===//
1735 // Main driver code.
1736 //===----------------------------------------------------------------------===//
1738 int main() {
1739 // Install standard binary operators.
1740 // 1 is lowest precedence.
1742 BinopPrecedence['+'] = 20;
1743 BinopPrecedence['-'] = 20;
1744 BinopPrecedence['*'] = 40; // highest.
1746 // Prime the first token.
1747 fprintf(stderr, "ready> ");
1748 getNextToken();
1750 // Make the module, which holds all the code.
1751 TheModule = new Module("my cool jit", getGlobalContext());
1753 ExistingModuleProvider *OurModuleProvider =
1754 new ExistingModuleProvider(TheModule);
1756 // Create the JIT. This takes ownership of the module and module provider.
1757 TheExecutionEngine = EngineBuilder(OurModuleProvider).create();
1759 FunctionPassManager OurFPM(OurModuleProvider);
1761 // Set up the optimizer pipeline. Start with registering info about how the
1762 // target lays out data structures.
1763 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1764 // Do simple "peephole" optimizations and bit-twiddling optzns.
1765 OurFPM.add(createInstructionCombiningPass());
1766 // Reassociate expressions.
1767 OurFPM.add(createReassociatePass());
1768 // Eliminate Common SubExpressions.
1769 OurFPM.add(createGVNPass());
1770 // Simplify the control flow graph (deleting unreachable blocks, etc).
1771 OurFPM.add(createCFGSimplificationPass());
1773 // Set the global so the code gen can use this.
1774 TheFPM = &OurFPM;
1776 // Run the main "interpreter loop" now.
1777 MainLoop();
1779 TheFPM = 0;
1781 // Print out all of the generated code.
1782 TheModule->dump();
1784 return 0;
1785 }
1786 </pre>
1787 </div>
1789 <a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a>
1790 </div>
1792 <!-- *********************************************************************** -->
1793 <hr>
1794 <address>
1803 </address>
1804 </body>
1805 </html>