1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
6 <title>Kaleidoscope: Extending the Language: User-defined Operators</title>
7 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
8 <meta name="author" content="Chris Lattner">
9 <link rel="stylesheet" href="../_static/llvm.css" type="text/css">
14 <h1>Kaleidoscope: Extending the Language: User-defined Operators</h1>
17 <li><a href="index.html">Up to Tutorial Index</a></li>
20 <li><a href="#intro">Chapter 6 Introduction</a></li>
21 <li><a href="#idea">User-defined Operators: the Idea</a></li>
22 <li><a href="#binary">User-defined Binary Operators</a></li>
23 <li><a href="#unary">User-defined Unary Operators</a></li>
24 <li><a href="#example">Kicking the Tires</a></li>
25 <li><a href="#code">Full Code Listing</a></li>
28 <li><a href="LangImpl7.html">Chapter 7</a>: Extending the Language: Mutable
29 Variables / SSA Construction</li>
32 <div class="doc_author">
33 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
36 <!-- *********************************************************************** -->
37 <h2><a name="intro">Chapter 6 Introduction</a></h2>
38 <!-- *********************************************************************** -->
42 <p>Welcome to Chapter 6 of the "<a href="index.html">Implementing a language
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
57 application that <a href="#example">renders the Mandelbrot set</a>. This gives
58 an example of what you can build with Kaleidoscope and its feature set.</p>
62 <!-- *********************************************************************** -->
63 <h2><a name="idea">User-defined Operators: the Idea</a></h2>
64 <!-- *********************************************************************** -->
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
80 href="LangImpl2.html">Chapter 2</a> for details. Without using operator
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
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>
89 <div class="doc_code">
98 # Define > with the same precedence as <.
99 def binary> 10 (LHS RHS)
102 # Binary "logical or", (note that it does not "short circuit")
103 def binary| 5 (LHS RHS)
111 # Define = with slightly lower precedence than relationals.
112 def binary= 9 (LHS RHS)
113 !(LHS < RHS | LHS > RHS);
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
127 <!-- *********************************************************************** -->
128 <h2><a name="binary">User-defined Binary Operators</a></h2>
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>
136 <div class="doc_code">
141 tok_binary = -11, tok_unary = -12</b>
144 static int gettok() {
146 if (IdentifierStr == "for") return tok_for;
147 if (IdentifierStr == "in") return tok_in;
148 <b>if (IdentifierStr == "binary") return tok_binary;
149 if (IdentifierStr == "unary") return tok_unary;</b>
150 return tok_identifier;
154 <p>This just adds lexer support for the unary and binary keywords, like we
155 did in <a href="LangImpl5.html#iflexer">previous chapters</a>. One nice thing
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
163 "prototype" production and into the <tt>PrototypeAST</tt> AST node. To
164 represent our new user-defined operators as prototypes, we have to extend
165 the <tt>PrototypeAST</tt> AST node like this:</p>
167 <div class="doc_code">
169 /// PrototypeAST - This class represents the "prototype" for a function,
170 /// which captures its argument names as well as if it is an operator.
173 std::vector<std::string> Args;
175 unsigned Precedence; // Precedence if a binary op.</b>
177 PrototypeAST(const std::string &name, const std::vector<std::string> &args,
178 <b>bool isoperator = false, unsigned prec = 0</b>)
179 : Name(name), Args(args), <b>isOperator(isoperator), Precedence(prec)</b> {}
181 <b>bool isUnaryOp() const { return isOperator && Args.size() == 1; }
182 bool isBinaryOp() const { return isOperator && Args.size() == 2; }
184 char getOperatorName() const {
185 assert(isUnaryOp() || isBinaryOp());
186 return Name[Name.size()-1];
189 unsigned getBinaryPrecedence() const { return Precedence; }</b>
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>
202 <div class="doc_code">
205 /// ::= id '(' id* ')'
206 <b>/// ::= binary LETTER number? (id, id)</b>
207 static PrototypeAST *ParsePrototype() {
210 <b>unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
211 unsigned BinaryPrecedence = 30;</b>
215 return ErrorP("Expected function name in prototype");
217 FnName = IdentifierStr;
223 if (!isascii(CurTok))
224 return ErrorP("Expected binary operator");
226 FnName += (char)CurTok;
230 // Read the precedence if present.
231 if (CurTok == tok_number) {
232 if (NumVal < 1 || NumVal > 100)
233 return ErrorP("Invalid precedecnce: must be 1..100");
234 BinaryPrecedence = (unsigned)NumVal;
241 return ErrorP("Expected '(' in prototype");
243 std::vector<std::string> ArgNames;
244 while (getNextToken() == tok_identifier)
245 ArgNames.push_back(IdentifierStr);
247 return ErrorP("Expected ')' in prototype");
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");
256 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);</b>
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
263 the couple lines that set up <tt>FnName</tt> for binary operators. This builds names
264 like "binary@" for a newly defined "@" operator. This then takes advantage of the
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>
272 <div class="doc_code">
274 Value *BinaryExprAST::Codegen() {
275 Value *L = LHS->Codegen();
276 Value *R = RHS->Codegen();
277 if (L == 0 || R == 0) return 0;
280 case '+': return Builder.CreateFAdd(L, R, "addtmp");
281 case '-': return Builder.CreateFSub(L, R, "subtmp");
282 case '*': return Builder.CreateFMul(L, R, "multmp");
284 L = Builder.CreateFCmpULT(L, R, "cmptmp");
285 // Convert bool 0/1 to double 0.0 or 1.0
286 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
288 <b>default: break;</b>
291 <b>// If it wasn't a builtin binary operator, it must be a user defined one. Emit
293 Function *F = TheModule->getFunction(std::string("binary")+Op);
294 assert(F && "binary operator not found!");
296 Value *Ops[2] = { L, R };
297 return Builder.CreateCall(F, Ops, "binop");</b>
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>
309 <p>The final piece of code we are missing, is a bit of top-level magic:</p>
311 <div class="doc_code">
313 Function *FunctionAST::Codegen() {
316 Function *TheFunction = Proto->Codegen();
317 if (TheFunction == 0)
320 <b>// If this is an operator, install it.
321 if (Proto->isBinaryOp())
322 BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();</b>
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()) {
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>
344 <!-- *********************************************************************** -->
345 <h2><a name="unary">User-defined Unary Operators</a></h2>
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
355 <div class="doc_code">
357 /// UnaryExprAST - Expression class for a unary operator.
358 class UnaryExprAST : public ExprAST {
362 UnaryExprAST(char opcode, ExprAST *operand)
363 : Opcode(opcode), Operand(operand) {}
364 virtual Value *Codegen();
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>
374 <div class="doc_code">
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.
387 if (ExprAST *Operand = ParseUnary())
388 return new UnaryExprAST(Opc, Operand);
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
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
405 <div class="doc_code">
409 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
411 <b>// Parse the unary expression after the binary operator.
412 ExprAST *RHS = ParseUnary();
413 if (!RHS) return 0;</b>
417 /// ::= unary binoprhs
419 static ExprAST *ParseExpression() {
420 <b>ExprAST *LHS = ParseUnary();</b>
423 return ParseBinOpRHS(0, LHS);
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
433 <div class="doc_code">
436 /// ::= id '(' id* ')'
437 /// ::= binary LETTER number? (id, id)
438 <b>/// ::= unary LETTER (id)</b>
439 static PrototypeAST *ParsePrototype() {
442 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
443 unsigned BinaryPrecedence = 30;
447 return ErrorP("Expected function name in prototype");
449 FnName = IdentifierStr;
455 if (!isascii(CurTok))
456 return ErrorP("Expected unary operator");
458 FnName += (char)CurTok;
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
472 <div class="doc_code">
474 Value *UnaryExprAST::Codegen() {
475 Value *OperandV = Operand->Codegen();
476 if (OperandV == 0) return 0;
478 Function *F = TheModule->getFunction(std::string("unary")+Opcode);
480 return ErrorV("Unknown unary operator");
482 return Builder.CreateCall(F, OperandV, "unop");
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.
493 <!-- *********************************************************************** -->
494 <h2><a name="example">Kicking the Tires</a></h2>
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>
505 <div class="doc_code">
507 ready> <b>extern printd(x);</b>
509 declare double @printd(double)
511 ready> <b>def binary : 1 (x y) 0; # Low-precedence operator that ignores operands.</b>
513 ready> <b>printd(123) : printd(456) : printd(789);</b>
517 Evaluated to 0.000000
521 <p>We can also define a bunch of other "primitive" operations, such as:</p>
523 <div class="doc_code">
536 # Define > with the same precedence as <.
537 def binary> 10 (LHS RHS)
540 # Binary logical or, which does not short circuit.
541 def binary| 5 (LHS RHS)
549 # Binary logical and, which does not short circuit.
550 def binary& 6 (LHS RHS)
556 # Define = with slightly lower precedence than relationals.
557 def binary = 9 (LHS RHS)
558 !(LHS < RHS | LHS > RHS);
560 # Define ':' for sequencing: as a low-precedence operator that ignores operands
561 # and just returns the RHS.
562 def binary : 1 (x y) y;
567 <p>Given the previous if/then/else support, we can also define interesting
568 functions for I/O. For example, the following prints out a character whose
569 "density" reflects the value passed in: the lower the value, the denser the
572 <div class="doc_code">
576 extern putchard(char)
580 else if d > 4 then
582 else if d > 2 then
585 putchard(42); # '*'</b>
587 ready> <b>printdensity(1): printdensity(2): printdensity(3):
588 printdensity(4): printdensity(5): printdensity(9):
591 Evaluated to 0.000000
595 <p>Based on these simple primitive operations, we can start to define more
596 interesting things. For example, here's a little function that solves for the
597 number of iterations it takes a function in the complex plane to
600 <div class="doc_code">
602 # Determine whether the specific location diverges.
603 # Solve for z = z^2 + c in the complex plane.
604 def mandleconverger(real imag iters creal cimag)
605 if iters > 255 | (real*real + imag*imag > 4) then
608 mandleconverger(real*real - imag*imag + creal,
610 iters+1, creal, cimag);
612 # Return the number of iterations required for the iteration to escape
613 def mandleconverge(real imag)
614 mandleconverger(real, imag, 0, real, imag);
618 <p>This "<code>z = z<sup>2</sup> + c</code>" function is a beautiful little
619 creature that is the basis for computation of
620 the <a href="http://en.wikipedia.org/wiki/Mandelbrot_set">Mandelbrot Set</a>.
621 Our <tt>mandelconverge</tt> function returns the number of iterations that it
622 takes for a complex orbit to escape, saturating to 255. This is not a very
623 useful function by itself, but if you plot its value over a two-dimensional
624 plane, you can see the Mandelbrot set. Given that we are limited to using
625 putchard here, our amazing graphical output is limited, but we can whip together
626 something using the density plotter above:</p>
628 <div class="doc_code">
630 # Compute and plot the mandlebrot set with the specified 2 dimensional range
632 def mandelhelp(xmin xmax xstep ymin ymax ystep)
633 for y = ymin, y < ymax, ystep in (
634 (for x = xmin, x < xmax, xstep in
635 printdensity(mandleconverge(x,y)))
639 # mandel - This is a convenient helper function for plotting the mandelbrot set
640 # from the specified position with the specified Magnification.
641 def mandel(realstart imagstart realmag imagmag)
642 mandelhelp(realstart, realstart+realmag*78, realmag,
643 imagstart, imagstart+imagmag*40, imagmag);
647 <p>Given this, we can try plotting out the mandlebrot set! Lets try it out:</p>
649 <div class="doc_code">
651 ready> <b>mandel(-2.3, -1.3, 0.05, 0.07);</b>
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 *********************++++++++++++++++++++++.++++++++***************************
688 *************************+++++++++++++++++++++++*******************************
689 ******************************+++++++++++++************************************
690 *******************************************************************************
691 *******************************************************************************
692 *******************************************************************************
693 Evaluated to 0.000000
694 ready> <b>mandel(-2, -1, 0.02, 0.04);</b>
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 *.......... ...........
721 *.......... ...........
722 *+++....++++................
723 *++++++++++++++..............
724 *++++++++++++++++............ ...
725 *++++++++++++++++++.................
726 **+++++++++++++++++++................
727 **+++++++++++++++++++++..............
728 ***++++++++++++++++++++++............
729 ***++++++++++++++++++++++++......... ...... ...........
730 ****++++++++++++++++++++++++++...... .........................
731 *****++++++++++++++++++++++++++++...............................
732 *****++++++++++++++++++++++++++++++++............................
733 ******+++++++++++++++++++++++++++++++++++...........................
734 *******+++++++++++++++++++++++++++++++++++++++.......................
735 ********+++++++++++++++++++++++++++++++++++++++++++..................
736 Evaluated to 0.000000
737 ready> <b>mandel(-0.9, -1.4, 0.02, 0.03);</b>
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 ......... ....+++++++
779 Evaluated to 0.000000
784 <p>At this point, you may be starting to realize that Kaleidoscope is a real
785 and powerful language. It may not be self-similar :), but it can be used to
786 plot things that are!</p>
788 <p>With this, we conclude the "adding user-defined operators" chapter of the
789 tutorial. We have successfully augmented our language, adding the ability to extend the
790 language in the library, and we have shown how this can be used to build a simple but
791 interesting end-user application in Kaleidoscope. At this point, Kaleidoscope
792 can build a variety of applications that are functional and can call functions
793 with side-effects, but it can't actually define and mutate a variable itself.
796 <p>Strikingly, variable mutation is an important feature of some
797 languages, and it is not at all obvious how to <a href="LangImpl7.html">add
798 support for mutable variables</a> without having to add an "SSA construction"
799 phase to your front-end. In the next chapter, we will describe how you can
800 add variable mutation without building SSA in your front-end.</p>
804 <!-- *********************************************************************** -->
805 <h2><a name="code">Full Code Listing</a></h2>
806 <!-- *********************************************************************** -->
811 Here is the complete code listing for our running example, enhanced with the
812 if/then/else and for expressions.. To build this example, use:
815 <div class="doc_code">
818 clang++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
824 <p>On some platforms, you will need to specify -rdynamic or -Wl,--export-dynamic
825 when linking. This ensures that symbols defined in the main executable are
826 exported to the dynamic linker and so are available for symbol resolution at
827 run time. This is not needed if you compile your support code into a shared
828 library, although doing that will cause problems on Windows.</p>
830 <p>Here is the code:</p>
832 <div class="doc_code">
834 #include "llvm/DerivedTypes.h"
835 #include "llvm/ExecutionEngine/ExecutionEngine.h"
836 #include "llvm/ExecutionEngine/JIT.h"
837 #include "llvm/IRBuilder.h"
838 #include "llvm/LLVMContext.h"
839 #include "llvm/Module.h"
840 #include "llvm/PassManager.h"
841 #include "llvm/Analysis/Verifier.h"
842 #include "llvm/Analysis/Passes.h"
843 #include "llvm/DataLayout.h"
844 #include "llvm/Transforms/Scalar.h"
845 #include "llvm/Support/TargetSelect.h"
846 #include <cstdio>
847 #include <string>
849 #include <vector>
850 using namespace llvm;
852 //===----------------------------------------------------------------------===//
854 //===----------------------------------------------------------------------===//
856 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
857 // of these for known things.
862 tok_def = -2, tok_extern = -3,
865 tok_identifier = -4, tok_number = -5,
868 tok_if = -6, tok_then = -7, tok_else = -8,
869 tok_for = -9, tok_in = -10,
872 tok_binary = -11, tok_unary = -12
875 static std::string IdentifierStr; // Filled in if tok_identifier
876 static double NumVal; // Filled in if tok_number
878 /// gettok - Return the next token from standard input.
879 static int gettok() {
880 static int LastChar = ' ';
882 // Skip any whitespace.
883 while (isspace(LastChar))
884 LastChar = getchar();
886 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
887 IdentifierStr = LastChar;
888 while (isalnum((LastChar = getchar())))
889 IdentifierStr += LastChar;
891 if (IdentifierStr == "def") return tok_def;
892 if (IdentifierStr == "extern") return tok_extern;
893 if (IdentifierStr == "if") return tok_if;
894 if (IdentifierStr == "then") return tok_then;
895 if (IdentifierStr == "else") return tok_else;
896 if (IdentifierStr == "for") return tok_for;
897 if (IdentifierStr == "in") return tok_in;
898 if (IdentifierStr == "binary") return tok_binary;
899 if (IdentifierStr == "unary") return tok_unary;
900 return tok_identifier;
903 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
907 LastChar = getchar();
908 } while (isdigit(LastChar) || LastChar == '.');
910 NumVal = strtod(NumStr.c_str(), 0);
914 if (LastChar == '#') {
915 // Comment until end of line.
916 do LastChar = getchar();
917 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
923 // Check for end of file. Don't eat the EOF.
927 // Otherwise, just return the character as its ascii value.
928 int ThisChar = LastChar;
929 LastChar = getchar();
933 //===----------------------------------------------------------------------===//
934 // Abstract Syntax Tree (aka Parse Tree)
935 //===----------------------------------------------------------------------===//
937 /// ExprAST - Base class for all expression nodes.
940 virtual ~ExprAST() {}
941 virtual Value *Codegen() = 0;
944 /// NumberExprAST - Expression class for numeric literals like "1.0".
945 class NumberExprAST : public ExprAST {
948 NumberExprAST(double val) : Val(val) {}
949 virtual Value *Codegen();
952 /// VariableExprAST - Expression class for referencing a variable, like "a".
953 class VariableExprAST : public ExprAST {
956 VariableExprAST(const std::string &name) : Name(name) {}
957 virtual Value *Codegen();
960 /// UnaryExprAST - Expression class for a unary operator.
961 class UnaryExprAST : public ExprAST {
965 UnaryExprAST(char opcode, ExprAST *operand)
966 : Opcode(opcode), Operand(operand) {}
967 virtual Value *Codegen();
970 /// BinaryExprAST - Expression class for a binary operator.
971 class BinaryExprAST : public ExprAST {
975 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
976 : Op(op), LHS(lhs), RHS(rhs) {}
977 virtual Value *Codegen();
980 /// CallExprAST - Expression class for function calls.
981 class CallExprAST : public ExprAST {
983 std::vector<ExprAST*> Args;
985 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
986 : Callee(callee), Args(args) {}
987 virtual Value *Codegen();
990 /// IfExprAST - Expression class for if/then/else.
991 class IfExprAST : public ExprAST {
992 ExprAST *Cond, *Then, *Else;
994 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
995 : Cond(cond), Then(then), Else(_else) {}
996 virtual Value *Codegen();
999 /// ForExprAST - Expression class for for/in.
1000 class ForExprAST : public ExprAST {
1001 std::string VarName;
1002 ExprAST *Start, *End, *Step, *Body;
1004 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
1005 ExprAST *step, ExprAST *body)
1006 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1007 virtual Value *Codegen();
1010 /// PrototypeAST - This class represents the "prototype" for a function,
1011 /// which captures its name, and its argument names (thus implicitly the number
1012 /// of arguments the function takes), as well as if it is an operator.
1013 class PrototypeAST {
1015 std::vector<std::string> Args;
1017 unsigned Precedence; // Precedence if a binary op.
1019 PrototypeAST(const std::string &name, const std::vector<std::string> &args,
1020 bool isoperator = false, unsigned prec = 0)
1021 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1023 bool isUnaryOp() const { return isOperator && Args.size() == 1; }
1024 bool isBinaryOp() const { return isOperator && Args.size() == 2; }
1026 char getOperatorName() const {
1027 assert(isUnaryOp() || isBinaryOp());
1028 return Name[Name.size()-1];
1031 unsigned getBinaryPrecedence() const { return Precedence; }
1033 Function *Codegen();
1036 /// FunctionAST - This class represents a function definition itself.
1038 PrototypeAST *Proto;
1041 FunctionAST(PrototypeAST *proto, ExprAST *body)
1042 : Proto(proto), Body(body) {}
1044 Function *Codegen();
1047 //===----------------------------------------------------------------------===//
1049 //===----------------------------------------------------------------------===//
1051 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1052 /// token the parser is looking at. getNextToken reads another token from the
1053 /// lexer and updates CurTok with its results.
1055 static int getNextToken() {
1056 return CurTok = gettok();
1059 /// BinopPrecedence - This holds the precedence for each binary operator that is
1061 static std::map<char, int> BinopPrecedence;
1063 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1064 static int GetTokPrecedence() {
1065 if (!isascii(CurTok))
1068 // Make sure it's a declared binop.
1069 int TokPrec = BinopPrecedence[CurTok];
1070 if (TokPrec <= 0) return -1;
1074 /// Error* - These are little helper functions for error handling.
1075 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1076 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1077 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1079 static ExprAST *ParseExpression();
1083 /// ::= identifier '(' expression* ')'
1084 static ExprAST *ParseIdentifierExpr() {
1085 std::string IdName = IdentifierStr;
1087 getNextToken(); // eat identifier.
1089 if (CurTok != '(') // Simple variable ref.
1090 return new VariableExprAST(IdName);
1093 getNextToken(); // eat (
1094 std::vector<ExprAST*> Args;
1095 if (CurTok != ')') {
1097 ExprAST *Arg = ParseExpression();
1099 Args.push_back(Arg);
1101 if (CurTok == ')') break;
1104 return Error("Expected ')' or ',' in argument list");
1112 return new CallExprAST(IdName, Args);
1115 /// numberexpr ::= number
1116 static ExprAST *ParseNumberExpr() {
1117 ExprAST *Result = new NumberExprAST(NumVal);
1118 getNextToken(); // consume the number
1122 /// parenexpr ::= '(' expression ')'
1123 static ExprAST *ParseParenExpr() {
1124 getNextToken(); // eat (.
1125 ExprAST *V = ParseExpression();
1129 return Error("expected ')'");
1130 getNextToken(); // eat ).
1134 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1135 static ExprAST *ParseIfExpr() {
1136 getNextToken(); // eat the if.
1139 ExprAST *Cond = ParseExpression();
1140 if (!Cond) return 0;
1142 if (CurTok != tok_then)
1143 return Error("expected then");
1144 getNextToken(); // eat the then
1146 ExprAST *Then = ParseExpression();
1147 if (Then == 0) return 0;
1149 if (CurTok != tok_else)
1150 return Error("expected else");
1154 ExprAST *Else = ParseExpression();
1155 if (!Else) return 0;
1157 return new IfExprAST(Cond, Then, Else);
1160 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1161 static ExprAST *ParseForExpr() {
1162 getNextToken(); // eat the for.
1164 if (CurTok != tok_identifier)
1165 return Error("expected identifier after for");
1167 std::string IdName = IdentifierStr;
1168 getNextToken(); // eat identifier.
1171 return Error("expected '=' after for");
1172 getNextToken(); // eat '='.
1175 ExprAST *Start = ParseExpression();
1176 if (Start == 0) return 0;
1178 return Error("expected ',' after for start value");
1181 ExprAST *End = ParseExpression();
1182 if (End == 0) return 0;
1184 // The step value is optional.
1186 if (CurTok == ',') {
1188 Step = ParseExpression();
1189 if (Step == 0) return 0;
1192 if (CurTok != tok_in)
1193 return Error("expected 'in' after for");
1194 getNextToken(); // eat 'in'.
1196 ExprAST *Body = ParseExpression();
1197 if (Body == 0) return 0;
1199 return new ForExprAST(IdName, Start, End, Step, Body);
1203 /// ::= identifierexpr
1208 static ExprAST *ParsePrimary() {
1210 default: return Error("unknown token when expecting an expression");
1211 case tok_identifier: return ParseIdentifierExpr();
1212 case tok_number: return ParseNumberExpr();
1213 case '(': return ParseParenExpr();
1214 case tok_if: return ParseIfExpr();
1215 case tok_for: return ParseForExpr();
1222 static ExprAST *ParseUnary() {
1223 // If the current token is not an operator, it must be a primary expr.
1224 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1225 return ParsePrimary();
1227 // If this is a unary operator, read it.
1230 if (ExprAST *Operand = ParseUnary())
1231 return new UnaryExprAST(Opc, Operand);
1236 /// ::= ('+' unary)*
1237 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1238 // If this is a binop, find its precedence.
1240 int TokPrec = GetTokPrecedence();
1242 // If this is a binop that binds at least as tightly as the current binop,
1243 // consume it, otherwise we are done.
1244 if (TokPrec < ExprPrec)
1247 // Okay, we know this is a binop.
1249 getNextToken(); // eat binop
1251 // Parse the unary expression after the binary operator.
1252 ExprAST *RHS = ParseUnary();
1255 // If BinOp binds less tightly with RHS than the operator after RHS, let
1256 // the pending operator take RHS as its LHS.
1257 int NextPrec = GetTokPrecedence();
1258 if (TokPrec < NextPrec) {
1259 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1260 if (RHS == 0) return 0;
1264 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1269 /// ::= unary binoprhs
1271 static ExprAST *ParseExpression() {
1272 ExprAST *LHS = ParseUnary();
1275 return ParseBinOpRHS(0, LHS);
1279 /// ::= id '(' id* ')'
1280 /// ::= binary LETTER number? (id, id)
1281 /// ::= unary LETTER (id)
1282 static PrototypeAST *ParsePrototype() {
1285 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
1286 unsigned BinaryPrecedence = 30;
1290 return ErrorP("Expected function name in prototype");
1291 case tok_identifier:
1292 FnName = IdentifierStr;
1298 if (!isascii(CurTok))
1299 return ErrorP("Expected unary operator");
1301 FnName += (char)CurTok;
1307 if (!isascii(CurTok))
1308 return ErrorP("Expected binary operator");
1310 FnName += (char)CurTok;
1314 // Read the precedence if present.
1315 if (CurTok == tok_number) {
1316 if (NumVal < 1 || NumVal > 100)
1317 return ErrorP("Invalid precedecnce: must be 1..100");
1318 BinaryPrecedence = (unsigned)NumVal;
1325 return ErrorP("Expected '(' in prototype");
1327 std::vector<std::string> ArgNames;
1328 while (getNextToken() == tok_identifier)
1329 ArgNames.push_back(IdentifierStr);
1331 return ErrorP("Expected ')' in prototype");
1334 getNextToken(); // eat ')'.
1336 // Verify right number of names for operator.
1337 if (Kind && ArgNames.size() != Kind)
1338 return ErrorP("Invalid number of operands for operator");
1340 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1343 /// definition ::= 'def' prototype expression
1344 static FunctionAST *ParseDefinition() {
1345 getNextToken(); // eat def.
1346 PrototypeAST *Proto = ParsePrototype();
1347 if (Proto == 0) return 0;
1349 if (ExprAST *E = ParseExpression())
1350 return new FunctionAST(Proto, E);
1354 /// toplevelexpr ::= expression
1355 static FunctionAST *ParseTopLevelExpr() {
1356 if (ExprAST *E = ParseExpression()) {
1357 // Make an anonymous proto.
1358 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
1359 return new FunctionAST(Proto, E);
1364 /// external ::= 'extern' prototype
1365 static PrototypeAST *ParseExtern() {
1366 getNextToken(); // eat extern.
1367 return ParsePrototype();
1370 //===----------------------------------------------------------------------===//
1372 //===----------------------------------------------------------------------===//
1374 static Module *TheModule;
1375 static IRBuilder<> Builder(getGlobalContext());
1376 static std::map<std::string, Value*> NamedValues;
1377 static FunctionPassManager *TheFPM;
1379 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1381 Value *NumberExprAST::Codegen() {
1382 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1385 Value *VariableExprAST::Codegen() {
1386 // Look this variable up in the function.
1387 Value *V = NamedValues[Name];
1388 return V ? V : ErrorV("Unknown variable name");
1391 Value *UnaryExprAST::Codegen() {
1392 Value *OperandV = Operand->Codegen();
1393 if (OperandV == 0) return 0;
1395 Function *F = TheModule->getFunction(std::string("unary")+Opcode);
1397 return ErrorV("Unknown unary operator");
1399 return Builder.CreateCall(F, OperandV, "unop");
1402 Value *BinaryExprAST::Codegen() {
1403 Value *L = LHS->Codegen();
1404 Value *R = RHS->Codegen();
1405 if (L == 0 || R == 0) return 0;
1408 case '+': return Builder.CreateFAdd(L, R, "addtmp");
1409 case '-': return Builder.CreateFSub(L, R, "subtmp");
1410 case '*': return Builder.CreateFMul(L, R, "multmp");
1412 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1413 // Convert bool 0/1 to double 0.0 or 1.0
1414 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1419 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1421 Function *F = TheModule->getFunction(std::string("binary")+Op);
1422 assert(F && "binary operator not found!");
1424 Value *Ops[2] = { L, R };
1425 return Builder.CreateCall(F, Ops, "binop");
1428 Value *CallExprAST::Codegen() {
1429 // Look up the name in the global module table.
1430 Function *CalleeF = TheModule->getFunction(Callee);
1432 return ErrorV("Unknown function referenced");
1434 // If argument mismatch error.
1435 if (CalleeF->arg_size() != Args.size())
1436 return ErrorV("Incorrect # arguments passed");
1438 std::vector<Value*> ArgsV;
1439 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1440 ArgsV.push_back(Args[i]->Codegen());
1441 if (ArgsV.back() == 0) return 0;
1444 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
1447 Value *IfExprAST::Codegen() {
1448 Value *CondV = Cond->Codegen();
1449 if (CondV == 0) return 0;
1451 // Convert condition to a bool by comparing equal to 0.0.
1452 CondV = Builder.CreateFCmpONE(CondV,
1453 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1456 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1458 // Create blocks for the then and else cases. Insert the 'then' block at the
1459 // end of the function.
1460 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1461 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1462 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1464 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1467 Builder.SetInsertPoint(ThenBB);
1469 Value *ThenV = Then->Codegen();
1470 if (ThenV == 0) return 0;
1472 Builder.CreateBr(MergeBB);
1473 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1474 ThenBB = Builder.GetInsertBlock();
1477 TheFunction->getBasicBlockList().push_back(ElseBB);
1478 Builder.SetInsertPoint(ElseBB);
1480 Value *ElseV = Else->Codegen();
1481 if (ElseV == 0) return 0;
1483 Builder.CreateBr(MergeBB);
1484 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1485 ElseBB = Builder.GetInsertBlock();
1487 // Emit merge block.
1488 TheFunction->getBasicBlockList().push_back(MergeBB);
1489 Builder.SetInsertPoint(MergeBB);
1490 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
1493 PN->addIncoming(ThenV, ThenBB);
1494 PN->addIncoming(ElseV, ElseBB);
1498 Value *ForExprAST::Codegen() {
1501 // start = startexpr
1504 // variable = phi [start, loopheader], [nextvariable, loopend]
1510 // nextvariable = variable + step
1511 // endcond = endexpr
1512 // br endcond, loop, endloop
1515 // Emit the start code first, without 'variable' in scope.
1516 Value *StartVal = Start->Codegen();
1517 if (StartVal == 0) return 0;
1519 // Make the new basic block for the loop header, inserting after current
1521 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1522 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1523 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1525 // Insert an explicit fall through from the current block to the LoopBB.
1526 Builder.CreateBr(LoopBB);
1528 // Start insertion in LoopBB.
1529 Builder.SetInsertPoint(LoopBB);
1531 // Start the PHI node with an entry for Start.
1532 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
1533 Variable->addIncoming(StartVal, PreheaderBB);
1535 // Within the loop, the variable is defined equal to the PHI node. If it
1536 // shadows an existing variable, we have to restore it, so save it now.
1537 Value *OldVal = NamedValues[VarName];
1538 NamedValues[VarName] = Variable;
1540 // Emit the body of the loop. This, like any other expr, can change the
1541 // current BB. Note that we ignore the value computed by the body, but don't
1543 if (Body->Codegen() == 0)
1546 // Emit the step value.
1549 StepVal = Step->Codegen();
1550 if (StepVal == 0) return 0;
1552 // If not specified, use 1.0.
1553 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1556 Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
1558 // Compute the end condition.
1559 Value *EndCond = End->Codegen();
1560 if (EndCond == 0) return EndCond;
1562 // Convert condition to a bool by comparing equal to 0.0.
1563 EndCond = Builder.CreateFCmpONE(EndCond,
1564 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1567 // Create the "after loop" block and insert it.
1568 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1569 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1571 // Insert the conditional branch into the end of LoopEndBB.
1572 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1574 // Any new code will be inserted in AfterBB.
1575 Builder.SetInsertPoint(AfterBB);
1577 // Add a new entry to the PHI node for the backedge.
1578 Variable->addIncoming(NextVar, LoopEndBB);
1580 // Restore the unshadowed variable.
1582 NamedValues[VarName] = OldVal;
1584 NamedValues.erase(VarName);
1587 // for expr always returns 0.0.
1588 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1591 Function *PrototypeAST::Codegen() {
1592 // Make the function type: double(double,double) etc.
1593 std::vector<Type*> Doubles(Args.size(),
1594 Type::getDoubleTy(getGlobalContext()));
1595 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1598 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1600 // If F conflicted, there was already something named 'Name'. If it has a
1601 // body, don't allow redefinition or reextern.
1602 if (F->getName() != Name) {
1603 // Delete the one we just made and get the existing one.
1604 F->eraseFromParent();
1605 F = TheModule->getFunction(Name);
1607 // If F already has a body, reject this.
1608 if (!F->empty()) {
1609 ErrorF("redefinition of function");
1613 // If F took a different number of args, reject.
1614 if (F->arg_size() != Args.size()) {
1615 ErrorF("redefinition of function with different # args");
1620 // Set names for all arguments.
1622 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1624 AI->setName(Args[Idx]);
1626 // Add arguments to variable symbol table.
1627 NamedValues[Args[Idx]] = AI;
1633 Function *FunctionAST::Codegen() {
1634 NamedValues.clear();
1636 Function *TheFunction = Proto->Codegen();
1637 if (TheFunction == 0)
1640 // If this is an operator, install it.
1641 if (Proto->isBinaryOp())
1642 BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
1644 // Create a new basic block to start insertion into.
1645 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1646 Builder.SetInsertPoint(BB);
1648 if (Value *RetVal = Body->Codegen()) {
1649 // Finish off the function.
1650 Builder.CreateRet(RetVal);
1652 // Validate the generated code, checking for consistency.
1653 verifyFunction(*TheFunction);
1655 // Optimize the function.
1656 TheFPM->run(*TheFunction);
1661 // Error reading body, remove function.
1662 TheFunction->eraseFromParent();
1664 if (Proto->isBinaryOp())
1665 BinopPrecedence.erase(Proto->getOperatorName());
1669 //===----------------------------------------------------------------------===//
1670 // Top-Level parsing and JIT Driver
1671 //===----------------------------------------------------------------------===//
1673 static ExecutionEngine *TheExecutionEngine;
1675 static void HandleDefinition() {
1676 if (FunctionAST *F = ParseDefinition()) {
1677 if (Function *LF = F->Codegen()) {
1678 fprintf(stderr, "Read function definition:");
1682 // Skip token for error recovery.
1687 static void HandleExtern() {
1688 if (PrototypeAST *P = ParseExtern()) {
1689 if (Function *F = P->Codegen()) {
1690 fprintf(stderr, "Read extern: ");
1694 // Skip token for error recovery.
1699 static void HandleTopLevelExpression() {
1700 // Evaluate a top-level expression into an anonymous function.
1701 if (FunctionAST *F = ParseTopLevelExpr()) {
1702 if (Function *LF = F->Codegen()) {
1703 // JIT the function, returning a function pointer.
1704 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1706 // Cast it to the right type (takes no arguments, returns a double) so we
1707 // can call it as a native function.
1708 double (*FP)() = (double (*)())(intptr_t)FPtr;
1709 fprintf(stderr, "Evaluated to %f\n", FP());
1712 // Skip token for error recovery.
1717 /// top ::= definition | external | expression | ';'
1718 static void MainLoop() {
1720 fprintf(stderr, "ready> ");
1722 case tok_eof: return;
1723 case ';': getNextToken(); break; // ignore top-level semicolons.
1724 case tok_def: HandleDefinition(); break;
1725 case tok_extern: HandleExtern(); break;
1726 default: HandleTopLevelExpression(); break;
1731 //===----------------------------------------------------------------------===//
1732 // "Library" functions that can be "extern'd" from user code.
1733 //===----------------------------------------------------------------------===//
1735 /// putchard - putchar that takes a double and returns 0.
1737 double putchard(double X) {
1742 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1744 double printd(double X) {
1749 //===----------------------------------------------------------------------===//
1750 // Main driver code.
1751 //===----------------------------------------------------------------------===//
1754 InitializeNativeTarget();
1755 LLVMContext &Context = getGlobalContext();
1757 // Install standard binary operators.
1758 // 1 is lowest precedence.
1759 BinopPrecedence['<'] = 10;
1760 BinopPrecedence['+'] = 20;
1761 BinopPrecedence['-'] = 20;
1762 BinopPrecedence['*'] = 40; // highest.
1764 // Prime the first token.
1765 fprintf(stderr, "ready> ");
1768 // Make the module, which holds all the code.
1769 TheModule = new Module("my cool jit", Context);
1771 // Create the JIT. This takes ownership of the module.
1773 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
1774 if (!TheExecutionEngine) {
1775 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1779 FunctionPassManager OurFPM(TheModule);
1781 // Set up the optimizer pipeline. Start with registering info about how the
1782 // target lays out data structures.
1783 OurFPM.add(new DataLayout(*TheExecutionEngine->getDataLayout()));
1784 // Provide basic AliasAnalysis support for GVN.
1785 OurFPM.add(createBasicAliasAnalysisPass());
1786 // Do simple "peephole" optimizations and bit-twiddling optzns.
1787 OurFPM.add(createInstructionCombiningPass());
1788 // Reassociate expressions.
1789 OurFPM.add(createReassociatePass());
1790 // Eliminate Common SubExpressions.
1791 OurFPM.add(createGVNPass());
1792 // Simplify the control flow graph (deleting unreachable blocks, etc).
1793 OurFPM.add(createCFGSimplificationPass());
1795 OurFPM.doInitialization();
1797 // Set the global so the code gen can use this.
1798 TheFPM = &OurFPM;
1800 // Run the main "interpreter loop" now.
1805 // Print out all of the generated code.
1806 TheModule->dump();
1813 <a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a>
1816 <!-- *********************************************************************** -->
1819 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1820 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1821 <a href="http://validator.w3.org/check/referer"><img
1822 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1824 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1825 <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
1826 Last modified: $Date$