| blob | 510d9dde09a97ee86512f0be053bbb888bdd15c7 |
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.CreateFAdd(L, R, "addtmp");
281 case '-': return Builder.CreateFSub(L, R, "subtmp");
282 case '*': return Builder.CreateFMul(L, R, "multmp");
283 case '<':
284 L = Builder.CreateFCmpULT(L, R, "cmptmp");
286 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
287 "booltmp");
289 }
291 <b>// If it wasn't a builtin binary operator, it must be a user defined one. Emit
292 // a call to it.
296 Value *Ops[] = { L, R };
298 }
300 </pre>
301 </div>
303 <p>As you can see above, the new code is actually really simple. It just does
304 a lookup for the appropriate operator in the symbol table and generates a
305 function call to it. Since user-defined operators are just built as normal
306 functions (because the "prototype" boils down to a function with the right
307 name) everything falls into place.</p>
312 <pre>
313 Function *FunctionAST::Codegen() {
314 NamedValues.clear();
316 Function *TheFunction = Proto->Codegen();
317 if (TheFunction == 0)
318 return 0;
320 <b>// If this is an operator, install it.
321 if (Proto->isBinaryOp())
324 // Create a new basic block to start insertion into.
325 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
326 Builder.SetInsertPoint(BB);
328 if (Value *RetVal = Body->Codegen()) {
329 ...
330 </pre>
331 </div>
333 <p>Basically, before codegening a function, if it is a user-defined operator, we
334 register it in the precedence table. This allows the binary operator parsing
335 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>
337 <p>Now we have useful user-defined binary operators. This builds a lot
338 on the previous framework we built for other operators. Adding unary operators
339 is a bit more challenging, because we don't have any framework for it yet - lets
340 see what it takes.</p>
342 </div>
344 <!-- *********************************************************************** -->
346 <!-- *********************************************************************** -->
350 <p>Since we don't currently support unary operators in the Kaleidoscope
351 language, we'll need to add everything to support them. Above, we added simple
352 support for the 'unary' keyword to the lexer. In addition to that, we need an
353 AST node:</p>
356 <pre>
357 /// UnaryExprAST - Expression class for a unary operator.
358 class UnaryExprAST : public ExprAST {
359 char Opcode;
360 ExprAST *Operand;
361 public:
362 UnaryExprAST(char opcode, ExprAST *operand)
363 : Opcode(opcode), Operand(operand) {}
364 virtual Value *Codegen();
365 };
366 </pre>
367 </div>
369 <p>This AST node is very simple and obvious by now. It directly mirrors the
370 binary operator AST node, except that it only has one child. With this, we
371 need to add the parsing logic. Parsing a unary operator is pretty simple: we'll
372 add a new function to do it:</p>
375 <pre>
376 /// unary
377 /// ::= primary
378 /// ::= '!' unary
379 static ExprAST *ParseUnary() {
380 // If the current token is not an operator, it must be a primary expr.
381 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
382 return ParsePrimary();
384 // If this is a unary operator, read it.
385 int Opc = CurTok;
386 getNextToken();
387 if (ExprAST *Operand = ParseUnary())
388 return new UnaryExprAST(Opc, Operand);
389 return 0;
390 }
391 </pre>
392 </div>
394 <p>The grammar we add is pretty straightforward here. If we see a unary
395 operator when parsing a primary operator, we eat the operator as a prefix and
396 parse the remaining piece as another unary operator. This allows us to handle
397 multiple unary operators (e.g. "!!x"). Note that unary operators can't have
398 ambiguous parses like binary operators can, so there is no need for precedence
399 information.</p>
401 <p>The problem with this function, is that we need to call ParseUnary from somewhere.
402 To do this, we change previous callers of ParsePrimary to call ParseUnary
403 instead:</p>
406 <pre>
407 /// binoprhs
408 /// ::= ('+' unary)*
409 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
410 ...
411 <b>// Parse the unary expression after the binary operator.
412 ExprAST *RHS = ParseUnary();
414 ...
415 }
416 /// expression
417 /// ::= unary binoprhs
418 ///
419 static ExprAST *ParseExpression() {
421 if (!LHS) return 0;
423 return ParseBinOpRHS(0, LHS);
424 }
425 </pre>
426 </div>
428 <p>With these two simple changes, we are now able to parse unary operators and build the
429 AST for them. Next up, we need to add parser support for prototypes, to parse
430 the unary operator prototype. We extend the binary operator code above
431 with:</p>
434 <pre>
435 /// prototype
436 /// ::= id '(' id* ')'
437 /// ::= binary LETTER number? (id, id)
439 static PrototypeAST *ParsePrototype() {
440 std::string FnName;
443 unsigned BinaryPrecedence = 30;
445 switch (CurTok) {
446 default:
447 return ErrorP("Expected function name in prototype");
448 case tok_identifier:
449 FnName = IdentifierStr;
450 Kind = 0;
451 getNextToken();
452 break;
453 <b>case tok_unary:
454 getNextToken();
455 if (!isascii(CurTok))
456 return ErrorP("Expected unary operator");
457 FnName = "unary";
458 FnName += (char)CurTok;
459 Kind = 1;
460 getNextToken();
461 break;</b>
462 case tok_binary:
463 ...
464 </pre>
465 </div>
467 <p>As with binary operators, we name unary operators with a name that includes
468 the operator character. This assists us at code generation time. Speaking of,
469 the final piece we need to add is codegen support for unary operators. It looks
470 like this:</p>
473 <pre>
474 Value *UnaryExprAST::Codegen() {
475 Value *OperandV = Operand->Codegen();
479 if (F == 0)
480 return ErrorV("Unknown unary operator");
482 return Builder.CreateCall(F, OperandV, "unop");
483 }
484 </pre>
485 </div>
487 <p>This code is similar to, but simpler than, the code for binary operators. It
488 is simpler primarily because it doesn't need to handle any predefined operators.
489 </p>
491 </div>
493 <!-- *********************************************************************** -->
495 <!-- *********************************************************************** -->
499 <p>It is somewhat hard to believe, but with a few simple extensions we've
500 covered in the last chapters, we have grown a real-ish language. With this, we
501 can do a lot of interesting things, including I/O, math, and a bunch of other
502 things. For example, we can now add a nice sequencing operator (printd is
503 defined to print out the specified value and a newline):</p>
506 <pre>
508 Read extern: declare double @printd(double)
510 ..
512 123.000000
513 456.000000
514 789.000000
515 Evaluated to 0.000000
516 </pre>
517 </div>
522 <pre>
523 # Logical unary not.
524 def unary!(v)
525 if v then
526 0
527 else
528 1;
530 # Unary negate.
531 def unary-(v)
532 0-v;
536 RHS < LHS;
538 # Binary logical or, which does not short circuit.
539 def binary| 5 (LHS RHS)
540 if LHS then
541 1
542 else if RHS then
543 1
544 else
545 0;
547 # Binary logical and, which does not short circuit.
549 if !LHS then
550 0
551 else
552 !!RHS;
554 # Define = with slightly lower precedence than relationals.
555 def binary = 9 (LHS RHS)
558 </pre>
559 </div>
562 <p>Given the previous if/then/else support, we can also define interesting
563 functions for I/O. For example, the following prints out a character whose
564 "density" reflects the value passed in: the lower the value, the denser the
565 character:</p>
568 <pre>
569 ready>
570 <b>
571 extern putchard(char)
572 def printdensity(d)
574 putchard(32) # ' '
576 putchard(46) # '.'
578 putchard(43) # '+'
579 else
581 ...
584 *++..
585 Evaluated to 0.000000
586 </pre>
587 </div>
589 <p>Based on these simple primitive operations, we can start to define more
590 interesting things. For example, here's a little function that solves for the
591 number of iterations it takes a function in the complex plane to
592 converge:</p>
595 <pre>
596 # determine whether the specific location diverges.
597 # Solve for z = z^2 + c in the complex plane.
598 def mandleconverger(real imag iters creal cimag)
600 iters
601 else
602 mandleconverger(real*real - imag*imag + creal,
603 2*real*imag + cimag,
604 iters+1, creal, cimag);
606 # return the number of iterations required for the iteration to escape
607 def mandleconverge(real imag)
608 mandleconverger(real, imag, 0, real, imag);
609 </pre>
610 </div>
613 for computation of the <a
616 for a complex orbit to escape, saturating to 255. This is not a very useful
617 function by itself, but if you plot its value over a two-dimensional plane,
618 you can see the Mandelbrot set. Given that we are limited to using putchard
619 here, our amazing graphical output is limited, but we can whip together
620 something using the density plotter above:</p>
623 <pre>
624 # compute and plot the mandlebrot set with the specified 2 dimensional range
625 # info.
626 def mandelhelp(xmin xmax xstep ymin ymax ystep)
627 for y = ymin, y < ymax, ystep in (
628 (for x = xmin, x < xmax, xstep in
629 printdensity(mandleconverge(x,y)))
630 : putchard(10)
631 )
633 # mandel - This is a convenient helper function for ploting the mandelbrot set
634 # from the specified position with the specified Magnification.
635 def mandel(realstart imagstart realmag imagmag)
636 mandelhelp(realstart, realstart+realmag*78, realmag,
637 imagstart, imagstart+imagmag*40, imagmag);
638 </pre>
639 </div>
644 <pre>
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 *******************************************************************************
687 Evaluated to 0.000000
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 ********+++++++++++++++++++++++++++++++++++++++++++..................
730 Evaluated to 0.000000
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 ....+++++++
773 Evaluated to 0.000000
775 </pre>
776 </div>
778 <p>At this point, you may be starting to realize that Kaleidoscope is a real
779 and powerful language. It may not be self-similar :), but it can be used to
780 plot things that are!</p>
783 tutorial. We have successfully augmented our language, adding the ability to extend the
784 language in the library, and we have shown how this can be used to build a simple but
785 interesting end-user application in Kaleidoscope. At this point, Kaleidoscope
786 can build a variety of applications that are functional and can call functions
787 with side-effects, but it can't actually define and mutate a variable itself.
788 </p>
790 <p>Strikingly, variable mutation is an important feature of some
793 phase to your front-end. In the next chapter, we will describe how you can
794 add variable mutation without building SSA in your front-end.</p>
796 </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/ExecutionEngine/JIT.h"
825 #include "llvm/LLVMContext.h"
826 #include "llvm/Module.h"
827 #include "llvm/PassManager.h"
828 #include "llvm/Analysis/Verifier.h"
829 #include "llvm/Analysis/Passes.h"
830 #include "llvm/Target/TargetData.h"
831 #include "llvm/Target/TargetSelect.h"
832 #include "llvm/Transforms/Scalar.h"
833 #include "llvm/Support/IRBuilder.h"
838 using namespace llvm;
840 //===----------------------------------------------------------------------===//
841 // Lexer
842 //===----------------------------------------------------------------------===//
845 // of these for known things.
846 enum Token {
847 tok_eof = -1,
849 // commands
852 // primary
855 // control
859 // operators
861 };
863 static std::string IdentifierStr; // Filled in if tok_identifier
864 static double NumVal; // Filled in if tok_number
866 /// gettok - Return the next token from standard input.
867 static int gettok() {
868 static int LastChar = ' ';
870 // Skip any whitespace.
871 while (isspace(LastChar))
872 LastChar = getchar();
874 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
875 IdentifierStr = LastChar;
876 while (isalnum((LastChar = getchar())))
877 IdentifierStr += LastChar;
879 if (IdentifierStr == "def") return tok_def;
880 if (IdentifierStr == "extern") return tok_extern;
881 if (IdentifierStr == "if") return tok_if;
882 if (IdentifierStr == "then") return tok_then;
883 if (IdentifierStr == "else") return tok_else;
884 if (IdentifierStr == "for") return tok_for;
885 if (IdentifierStr == "in") return tok_in;
886 if (IdentifierStr == "binary") return tok_binary;
887 if (IdentifierStr == "unary") return tok_unary;
888 return tok_identifier;
889 }
892 std::string NumStr;
893 do {
894 NumStr += LastChar;
895 LastChar = getchar();
896 } while (isdigit(LastChar) || LastChar == '.');
898 NumVal = strtod(NumStr.c_str(), 0);
899 return tok_number;
900 }
902 if (LastChar == '#') {
903 // Comment until end of line.
904 do LastChar = getchar();
907 if (LastChar != EOF)
908 return gettok();
909 }
911 // Check for end of file. Don't eat the EOF.
912 if (LastChar == EOF)
913 return tok_eof;
915 // Otherwise, just return the character as its ascii value.
916 int ThisChar = LastChar;
917 LastChar = getchar();
918 return ThisChar;
919 }
921 //===----------------------------------------------------------------------===//
922 // Abstract Syntax Tree (aka Parse Tree)
923 //===----------------------------------------------------------------------===//
925 /// ExprAST - Base class for all expression nodes.
926 class ExprAST {
927 public:
928 virtual ~ExprAST() {}
929 virtual Value *Codegen() = 0;
930 };
932 /// NumberExprAST - Expression class for numeric literals like "1.0".
933 class NumberExprAST : public ExprAST {
934 double Val;
935 public:
936 NumberExprAST(double val) : Val(val) {}
937 virtual Value *Codegen();
938 };
940 /// VariableExprAST - Expression class for referencing a variable, like "a".
941 class VariableExprAST : public ExprAST {
942 std::string Name;
943 public:
944 VariableExprAST(const std::string &name) : Name(name) {}
945 virtual Value *Codegen();
946 };
948 /// UnaryExprAST - Expression class for a unary operator.
949 class UnaryExprAST : public ExprAST {
950 char Opcode;
951 ExprAST *Operand;
952 public:
953 UnaryExprAST(char opcode, ExprAST *operand)
954 : Opcode(opcode), Operand(operand) {}
955 virtual Value *Codegen();
956 };
958 /// BinaryExprAST - Expression class for a binary operator.
959 class BinaryExprAST : public ExprAST {
960 char Op;
961 ExprAST *LHS, *RHS;
962 public:
963 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
964 : Op(op), LHS(lhs), RHS(rhs) {}
965 virtual Value *Codegen();
966 };
968 /// CallExprAST - Expression class for function calls.
969 class CallExprAST : public ExprAST {
970 std::string Callee;
972 public:
974 : Callee(callee), Args(args) {}
975 virtual Value *Codegen();
976 };
978 /// IfExprAST - Expression class for if/then/else.
979 class IfExprAST : public ExprAST {
980 ExprAST *Cond, *Then, *Else;
981 public:
982 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
983 : Cond(cond), Then(then), Else(_else) {}
984 virtual Value *Codegen();
985 };
987 /// ForExprAST - Expression class for for/in.
988 class ForExprAST : public ExprAST {
989 std::string VarName;
990 ExprAST *Start, *End, *Step, *Body;
991 public:
992 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
993 ExprAST *step, ExprAST *body)
994 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
995 virtual Value *Codegen();
996 };
998 /// PrototypeAST - This class represents the "prototype" for a function,
999 /// which captures its name, and its argument names (thus implicitly the number
1000 /// of arguments the function takes), as well as if it is an operator.
1001 class PrototypeAST {
1002 std::string Name;
1004 bool isOperator;
1005 unsigned Precedence; // Precedence if a binary op.
1006 public:
1008 bool isoperator = false, unsigned prec = 0)
1009 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1014 char getOperatorName() const {
1015 assert(isUnaryOp() || isBinaryOp());
1016 return Name[Name.size()-1];
1017 }
1019 unsigned getBinaryPrecedence() const { return Precedence; }
1021 Function *Codegen();
1022 };
1024 /// FunctionAST - This class represents a function definition itself.
1025 class FunctionAST {
1026 PrototypeAST *Proto;
1027 ExprAST *Body;
1028 public:
1029 FunctionAST(PrototypeAST *proto, ExprAST *body)
1030 : Proto(proto), Body(body) {}
1032 Function *Codegen();
1033 };
1035 //===----------------------------------------------------------------------===//
1036 // Parser
1037 //===----------------------------------------------------------------------===//
1039 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1040 /// token the parser is looking at. getNextToken reads another token from the
1041 /// lexer and updates CurTok with its results.
1042 static int CurTok;
1043 static int getNextToken() {
1044 return CurTok = gettok();
1045 }
1047 /// BinopPrecedence - This holds the precedence for each binary operator that is
1048 /// defined.
1051 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1052 static int GetTokPrecedence() {
1053 if (!isascii(CurTok))
1054 return -1;
1056 // Make sure it's a declared binop.
1057 int TokPrec = BinopPrecedence[CurTok];
1059 return TokPrec;
1060 }
1062 /// Error* - These are little helper functions for error handling.
1064 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1065 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1067 static ExprAST *ParseExpression();
1069 /// identifierexpr
1070 /// ::= identifier
1071 /// ::= identifier '(' expression* ')'
1072 static ExprAST *ParseIdentifierExpr() {
1073 std::string IdName = IdentifierStr;
1075 getNextToken(); // eat identifier.
1077 if (CurTok != '(') // Simple variable ref.
1078 return new VariableExprAST(IdName);
1080 // Call.
1081 getNextToken(); // eat (
1083 if (CurTok != ')') {
1084 while (1) {
1085 ExprAST *Arg = ParseExpression();
1086 if (!Arg) return 0;
1087 Args.push_back(Arg);
1089 if (CurTok == ')') break;
1091 if (CurTok != ',')
1092 return Error("Expected ')' or ',' in argument list");
1093 getNextToken();
1094 }
1095 }
1097 // Eat the ')'.
1098 getNextToken();
1100 return new CallExprAST(IdName, Args);
1101 }
1103 /// numberexpr ::= number
1104 static ExprAST *ParseNumberExpr() {
1105 ExprAST *Result = new NumberExprAST(NumVal);
1106 getNextToken(); // consume the number
1107 return Result;
1108 }
1110 /// parenexpr ::= '(' expression ')'
1111 static ExprAST *ParseParenExpr() {
1112 getNextToken(); // eat (.
1113 ExprAST *V = ParseExpression();
1114 if (!V) return 0;
1116 if (CurTok != ')')
1117 return Error("expected ')'");
1118 getNextToken(); // eat ).
1119 return V;
1120 }
1122 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1123 static ExprAST *ParseIfExpr() {
1124 getNextToken(); // eat the if.
1126 // condition.
1127 ExprAST *Cond = ParseExpression();
1128 if (!Cond) return 0;
1130 if (CurTok != tok_then)
1131 return Error("expected then");
1132 getNextToken(); // eat the then
1134 ExprAST *Then = ParseExpression();
1137 if (CurTok != tok_else)
1138 return Error("expected else");
1140 getNextToken();
1142 ExprAST *Else = ParseExpression();
1143 if (!Else) return 0;
1145 return new IfExprAST(Cond, Then, Else);
1146 }
1148 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1149 static ExprAST *ParseForExpr() {
1150 getNextToken(); // eat the for.
1152 if (CurTok != tok_identifier)
1153 return Error("expected identifier after for");
1155 std::string IdName = IdentifierStr;
1156 getNextToken(); // eat identifier.
1158 if (CurTok != '=')
1159 return Error("expected '=' after for");
1160 getNextToken(); // eat '='.
1163 ExprAST *Start = ParseExpression();
1165 if (CurTok != ',')
1166 return Error("expected ',' after for start value");
1167 getNextToken();
1169 ExprAST *End = ParseExpression();
1172 // The step value is optional.
1173 ExprAST *Step = 0;
1174 if (CurTok == ',') {
1175 getNextToken();
1176 Step = ParseExpression();
1178 }
1180 if (CurTok != tok_in)
1181 return Error("expected 'in' after for");
1182 getNextToken(); // eat 'in'.
1184 ExprAST *Body = ParseExpression();
1187 return new ForExprAST(IdName, Start, End, Step, Body);
1188 }
1190 /// primary
1191 /// ::= identifierexpr
1192 /// ::= numberexpr
1193 /// ::= parenexpr
1194 /// ::= ifexpr
1195 /// ::= forexpr
1196 static ExprAST *ParsePrimary() {
1197 switch (CurTok) {
1198 default: return Error("unknown token when expecting an expression");
1199 case tok_identifier: return ParseIdentifierExpr();
1200 case tok_number: return ParseNumberExpr();
1201 case '(': return ParseParenExpr();
1202 case tok_if: return ParseIfExpr();
1203 case tok_for: return ParseForExpr();
1204 }
1205 }
1207 /// unary
1208 /// ::= primary
1209 /// ::= '!' unary
1210 static ExprAST *ParseUnary() {
1211 // If the current token is not an operator, it must be a primary expr.
1212 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1213 return ParsePrimary();
1215 // If this is a unary operator, read it.
1216 int Opc = CurTok;
1217 getNextToken();
1218 if (ExprAST *Operand = ParseUnary())
1219 return new UnaryExprAST(Opc, Operand);
1220 return 0;
1221 }
1223 /// binoprhs
1224 /// ::= ('+' unary)*
1225 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1226 // If this is a binop, find its precedence.
1227 while (1) {
1228 int TokPrec = GetTokPrecedence();
1230 // If this is a binop that binds at least as tightly as the current binop,
1231 // consume it, otherwise we are done.
1232 if (TokPrec < ExprPrec)
1233 return LHS;
1235 // Okay, we know this is a binop.
1236 int BinOp = CurTok;
1237 getNextToken(); // eat binop
1239 // Parse the unary expression after the binary operator.
1240 ExprAST *RHS = ParseUnary();
1241 if (!RHS) return 0;
1243 // If BinOp binds less tightly with RHS than the operator after RHS, let
1244 // the pending operator take RHS as its LHS.
1245 int NextPrec = GetTokPrecedence();
1246 if (TokPrec < NextPrec) {
1247 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1249 }
1251 // Merge LHS/RHS.
1252 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1253 }
1254 }
1256 /// expression
1257 /// ::= unary binoprhs
1258 ///
1259 static ExprAST *ParseExpression() {
1260 ExprAST *LHS = ParseUnary();
1261 if (!LHS) return 0;
1263 return ParseBinOpRHS(0, LHS);
1264 }
1266 /// prototype
1267 /// ::= id '(' id* ')'
1268 /// ::= binary LETTER number? (id, id)
1269 /// ::= unary LETTER (id)
1270 static PrototypeAST *ParsePrototype() {
1271 std::string FnName;
1274 unsigned BinaryPrecedence = 30;
1276 switch (CurTok) {
1277 default:
1278 return ErrorP("Expected function name in prototype");
1279 case tok_identifier:
1280 FnName = IdentifierStr;
1281 Kind = 0;
1282 getNextToken();
1283 break;
1284 case tok_unary:
1285 getNextToken();
1286 if (!isascii(CurTok))
1287 return ErrorP("Expected unary operator");
1288 FnName = "unary";
1289 FnName += (char)CurTok;
1290 Kind = 1;
1291 getNextToken();
1292 break;
1293 case tok_binary:
1294 getNextToken();
1295 if (!isascii(CurTok))
1296 return ErrorP("Expected binary operator");
1297 FnName = "binary";
1298 FnName += (char)CurTok;
1299 Kind = 2;
1300 getNextToken();
1302 // Read the precedence if present.
1303 if (CurTok == tok_number) {
1305 return ErrorP("Invalid precedecnce: must be 1..100");
1306 BinaryPrecedence = (unsigned)NumVal;
1307 getNextToken();
1308 }
1309 break;
1310 }
1312 if (CurTok != '(')
1313 return ErrorP("Expected '(' in prototype");
1316 while (getNextToken() == tok_identifier)
1317 ArgNames.push_back(IdentifierStr);
1318 if (CurTok != ')')
1319 return ErrorP("Expected ')' in prototype");
1321 // success.
1322 getNextToken(); // eat ')'.
1324 // Verify right number of names for operator.
1325 if (Kind && ArgNames.size() != Kind)
1326 return ErrorP("Invalid number of operands for operator");
1328 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1329 }
1331 /// definition ::= 'def' prototype expression
1332 static FunctionAST *ParseDefinition() {
1333 getNextToken(); // eat def.
1334 PrototypeAST *Proto = ParsePrototype();
1337 if (ExprAST *E = ParseExpression())
1338 return new FunctionAST(Proto, E);
1339 return 0;
1340 }
1342 /// toplevelexpr ::= expression
1343 static FunctionAST *ParseTopLevelExpr() {
1344 if (ExprAST *E = ParseExpression()) {
1345 // Make an anonymous proto.
1347 return new FunctionAST(Proto, E);
1348 }
1349 return 0;
1350 }
1352 /// external ::= 'extern' prototype
1353 static PrototypeAST *ParseExtern() {
1354 getNextToken(); // eat extern.
1355 return ParsePrototype();
1356 }
1358 //===----------------------------------------------------------------------===//
1359 // Code Generation
1360 //===----------------------------------------------------------------------===//
1362 static Module *TheModule;
1363 static IRBuilder<> Builder(getGlobalContext());
1365 static FunctionPassManager *TheFPM;
1367 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1369 Value *NumberExprAST::Codegen() {
1370 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1371 }
1373 Value *VariableExprAST::Codegen() {
1374 // Look this variable up in the function.
1375 Value *V = NamedValues[Name];
1376 return V ? V : ErrorV("Unknown variable name");
1377 }
1379 Value *UnaryExprAST::Codegen() {
1380 Value *OperandV = Operand->Codegen();
1384 if (F == 0)
1385 return ErrorV("Unknown unary operator");
1387 return Builder.CreateCall(F, OperandV, "unop");
1388 }
1390 Value *BinaryExprAST::Codegen() {
1391 Value *L = LHS->Codegen();
1392 Value *R = RHS->Codegen();
1395 switch (Op) {
1396 case '+': return Builder.CreateFAdd(L, R, "addtmp");
1397 case '-': return Builder.CreateFSub(L, R, "subtmp");
1398 case '*': return Builder.CreateFMul(L, R, "multmp");
1399 case '<':
1400 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1402 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1403 "booltmp");
1404 default: break;
1405 }
1407 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1408 // a call to it.
1412 Value *Ops[] = { L, R };
1414 }
1416 Value *CallExprAST::Codegen() {
1417 // Look up the name in the global module table.
1418 Function *CalleeF = TheModule->getFunction(Callee);
1419 if (CalleeF == 0)
1420 return ErrorV("Unknown function referenced");
1422 // If argument mismatch error.
1423 if (CalleeF->arg_size() != Args.size())
1424 return ErrorV("Incorrect # arguments passed");
1427 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1428 ArgsV.push_back(Args[i]->Codegen());
1430 }
1432 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1433 }
1435 Value *IfExprAST::Codegen() {
1436 Value *CondV = Cond->Codegen();
1439 // Convert condition to a bool by comparing equal to 0.0.
1440 CondV = Builder.CreateFCmpONE(CondV,
1441 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1442 "ifcond");
1444 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1446 // Create blocks for the then and else cases. Insert the 'then' block at the
1447 // end of the function.
1448 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1449 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1450 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1452 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1454 // Emit then value.
1455 Builder.SetInsertPoint(ThenBB);
1457 Value *ThenV = Then->Codegen();
1460 Builder.CreateBr(MergeBB);
1461 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1462 ThenBB = Builder.GetInsertBlock();
1464 // Emit else block.
1465 TheFunction->getBasicBlockList().push_back(ElseBB);
1466 Builder.SetInsertPoint(ElseBB);
1468 Value *ElseV = Else->Codegen();
1471 Builder.CreateBr(MergeBB);
1472 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1473 ElseBB = Builder.GetInsertBlock();
1475 // Emit merge block.
1476 TheFunction->getBasicBlockList().push_back(MergeBB);
1477 Builder.SetInsertPoint(MergeBB);
1478 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
1479 "iftmp");
1481 PN->addIncoming(ThenV, ThenBB);
1482 PN->addIncoming(ElseV, ElseBB);
1483 return PN;
1484 }
1486 Value *ForExprAST::Codegen() {
1487 // Output this as:
1488 // ...
1489 // start = startexpr
1490 // goto loop
1491 // loop:
1492 // variable = phi [start, loopheader], [nextvariable, loopend]
1493 // ...
1494 // bodyexpr
1495 // ...
1496 // loopend:
1497 // step = stepexpr
1498 // nextvariable = variable + step
1499 // endcond = endexpr
1500 // br endcond, loop, endloop
1501 // outloop:
1503 // Emit the start code first, without 'variable' in scope.
1504 Value *StartVal = Start->Codegen();
1507 // Make the new basic block for the loop header, inserting after current
1508 // block.
1509 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1510 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1511 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1513 // Insert an explicit fall through from the current block to the LoopBB.
1514 Builder.CreateBr(LoopBB);
1516 // Start insertion in LoopBB.
1517 Builder.SetInsertPoint(LoopBB);
1519 // Start the PHI node with an entry for Start.
1520 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
1521 Variable->addIncoming(StartVal, PreheaderBB);
1523 // Within the loop, the variable is defined equal to the PHI node. If it
1524 // shadows an existing variable, we have to restore it, so save it now.
1525 Value *OldVal = NamedValues[VarName];
1526 NamedValues[VarName] = Variable;
1528 // Emit the body of the loop. This, like any other expr, can change the
1529 // current BB. Note that we ignore the value computed by the body, but don't
1530 // allow an error.
1532 return 0;
1534 // Emit the step value.
1535 Value *StepVal;
1536 if (Step) {
1537 StepVal = Step->Codegen();
1539 } else {
1540 // If not specified, use 1.0.
1541 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1542 }
1544 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
1546 // Compute the end condition.
1547 Value *EndCond = End->Codegen();
1548 if (EndCond == 0) return EndCond;
1550 // Convert condition to a bool by comparing equal to 0.0.
1551 EndCond = Builder.CreateFCmpONE(EndCond,
1552 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1553 "loopcond");
1555 // Create the "after loop" block and insert it.
1556 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1557 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1559 // Insert the conditional branch into the end of LoopEndBB.
1560 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1562 // Any new code will be inserted in AfterBB.
1563 Builder.SetInsertPoint(AfterBB);
1565 // Add a new entry to the PHI node for the backedge.
1566 Variable->addIncoming(NextVar, LoopEndBB);
1568 // Restore the unshadowed variable.
1569 if (OldVal)
1570 NamedValues[VarName] = OldVal;
1571 else
1572 NamedValues.erase(VarName);
1575 // for expr always returns 0.0.
1576 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1577 }
1579 Function *PrototypeAST::Codegen() {
1580 // Make the function type: double(double,double) etc.
1582 Type::getDoubleTy(getGlobalContext()));
1583 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1584 Doubles, false);
1586 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1588 // If F conflicted, there was already something named 'Name'. If it has a
1589 // body, don't allow redefinition or reextern.
1590 if (F->getName() != Name) {
1591 // Delete the one we just made and get the existing one.
1592 F->eraseFromParent();
1593 F = TheModule->getFunction(Name);
1595 // If F already has a body, reject this.
1596 if (!F->empty()) {
1597 ErrorF("redefinition of function");
1598 return 0;
1599 }
1601 // If F took a different number of args, reject.
1602 if (F->arg_size() != Args.size()) {
1603 ErrorF("redefinition of function with different # args");
1604 return 0;
1605 }
1606 }
1608 // Set names for all arguments.
1609 unsigned Idx = 0;
1610 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1611 ++AI, ++Idx) {
1612 AI->setName(Args[Idx]);
1614 // Add arguments to variable symbol table.
1615 NamedValues[Args[Idx]] = AI;
1616 }
1618 return F;
1619 }
1621 Function *FunctionAST::Codegen() {
1622 NamedValues.clear();
1624 Function *TheFunction = Proto->Codegen();
1625 if (TheFunction == 0)
1626 return 0;
1628 // If this is an operator, install it.
1629 if (Proto->isBinaryOp())
1632 // Create a new basic block to start insertion into.
1633 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1634 Builder.SetInsertPoint(BB);
1636 if (Value *RetVal = Body->Codegen()) {
1637 // Finish off the function.
1638 Builder.CreateRet(RetVal);
1640 // Validate the generated code, checking for consistency.
1641 verifyFunction(*TheFunction);
1643 // Optimize the function.
1644 TheFPM->run(*TheFunction);
1646 return TheFunction;
1647 }
1649 // Error reading body, remove function.
1650 TheFunction->eraseFromParent();
1652 if (Proto->isBinaryOp())
1653 BinopPrecedence.erase(Proto->getOperatorName());
1654 return 0;
1655 }
1657 //===----------------------------------------------------------------------===//
1658 // Top-Level parsing and JIT Driver
1659 //===----------------------------------------------------------------------===//
1661 static ExecutionEngine *TheExecutionEngine;
1663 static void HandleDefinition() {
1664 if (FunctionAST *F = ParseDefinition()) {
1665 if (Function *LF = F->Codegen()) {
1666 fprintf(stderr, "Read function definition:");
1667 LF->dump();
1668 }
1669 } else {
1670 // Skip token for error recovery.
1671 getNextToken();
1672 }
1673 }
1675 static void HandleExtern() {
1676 if (PrototypeAST *P = ParseExtern()) {
1677 if (Function *F = P->Codegen()) {
1678 fprintf(stderr, "Read extern: ");
1679 F->dump();
1680 }
1681 } else {
1682 // Skip token for error recovery.
1683 getNextToken();
1684 }
1685 }
1687 static void HandleTopLevelExpression() {
1688 // Evaluate a top-level expression into an anonymous function.
1689 if (FunctionAST *F = ParseTopLevelExpr()) {
1690 if (Function *LF = F->Codegen()) {
1691 // JIT the function, returning a function pointer.
1692 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1694 // Cast it to the right type (takes no arguments, returns a double) so we
1695 // can call it as a native function.
1696 double (*FP)() = (double (*)())(intptr_t)FPtr;
1697 fprintf(stderr, "Evaluated to %f\n", FP());
1698 }
1699 } else {
1700 // Skip token for error recovery.
1701 getNextToken();
1702 }
1703 }
1705 /// top ::= definition | external | expression | ';'
1706 static void MainLoop() {
1707 while (1) {
1708 fprintf(stderr, "ready> ");
1709 switch (CurTok) {
1710 case tok_eof: return;
1711 case ';': getNextToken(); break; // ignore top-level semicolons.
1712 case tok_def: HandleDefinition(); break;
1713 case tok_extern: HandleExtern(); break;
1714 default: HandleTopLevelExpression(); break;
1715 }
1716 }
1717 }
1719 //===----------------------------------------------------------------------===//
1721 //===----------------------------------------------------------------------===//
1723 /// putchard - putchar that takes a double and returns 0.
1724 extern "C"
1725 double putchard(double X) {
1726 putchar((char)X);
1727 return 0;
1728 }
1731 extern "C"
1732 double printd(double X) {
1733 printf("%f\n", X);
1734 return 0;
1735 }
1737 //===----------------------------------------------------------------------===//
1738 // Main driver code.
1739 //===----------------------------------------------------------------------===//
1741 int main() {
1742 InitializeNativeTarget();
1743 LLVMContext &Context = getGlobalContext();
1745 // Install standard binary operators.
1746 // 1 is lowest precedence.
1748 BinopPrecedence['+'] = 20;
1749 BinopPrecedence['-'] = 20;
1750 BinopPrecedence['*'] = 40; // highest.
1752 // Prime the first token.
1753 fprintf(stderr, "ready> ");
1754 getNextToken();
1756 // Make the module, which holds all the code.
1757 TheModule = new Module("my cool jit", Context);
1759 // Create the JIT. This takes ownership of the module.
1760 std::string ErrStr;
1761 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
1762 if (!TheExecutionEngine) {
1763 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1764 exit(1);
1765 }
1767 FunctionPassManager OurFPM(TheModule);
1769 // Set up the optimizer pipeline. Start with registering info about how the
1770 // target lays out data structures.
1771 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1772 // Provide basic AliasAnalysis support for GVN.
1773 OurFPM.add(createBasicAliasAnalysisPass());
1774 // Do simple "peephole" optimizations and bit-twiddling optzns.
1775 OurFPM.add(createInstructionCombiningPass());
1776 // Reassociate expressions.
1777 OurFPM.add(createReassociatePass());
1778 // Eliminate Common SubExpressions.
1779 OurFPM.add(createGVNPass());
1780 // Simplify the control flow graph (deleting unreachable blocks, etc).
1781 OurFPM.add(createCFGSimplificationPass());
1783 OurFPM.doInitialization();
1785 // Set the global so the code gen can use this.
1786 TheFPM = &OurFPM;
1788 // Run the main "interpreter loop" now.
1789 MainLoop();
1791 TheFPM = 0;
1793 // Print out all of the generated code.
1794 TheModule->dump();
1796 return 0;
1797 }
1798 </pre>
1799 </div>
1801 <a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a>
1802 </div>
1804 <!-- *********************************************************************** -->
1805 <hr>
1806 <address>
1814 Last modified: $Date$
1815 </address>
1816 </body>
1817 </html>