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="../llvm.css" type="text/css">
14 <div class="doc_title">Kaleidoscope: Extending the Language: User-defined Operators</div>
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 <div class="doc_section"><a name="intro">Chapter 6 Introduction</a></div>
38 <!-- *********************************************************************** -->
40 <div class="doc_text">
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 <div class="doc_section"><a name="idea">User-defined Operators: the Idea</a></div>
64 <!-- *********************************************************************** -->
66 <div class="doc_text">
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 <div class="doc_section"><a name="binary">User-defined Binary Operators</a></div>
129 <!-- *********************************************************************** -->
131 <div class="doc_text">
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[] = { L, R };
297 return Builder.CreateCall(F, Ops, Ops+2, "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 <div class="doc_section"><a name="unary">User-defined Unary Operators</a></div>
346 <!-- *********************************************************************** -->
348 <div class="doc_text">
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 <div class="doc_section"><a name="example">Kicking the Tires</a></div>
495 <!-- *********************************************************************** -->
497 <div class="doc_text">
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>
508 Read extern: declare double @printd(double)
509 ready> <b>def binary : 1 (x y) 0; # Low-precedence operator that ignores operands.</b>
511 ready> <b>printd(123) : printd(456) : printd(789);</b>
515 Evaluated to 0.000000
519 <p>We can also define a bunch of other "primitive" operations, such as:</p>
521 <div class="doc_code">
534 # Define > with the same precedence as <.
535 def binary> 10 (LHS RHS)
538 # Binary logical or, which does not short circuit.
539 def binary| 5 (LHS RHS)
547 # Binary logical and, which does not short circuit.
548 def binary& 6 (LHS RHS)
554 # Define = with slightly lower precedence than relationals.
555 def binary = 9 (LHS RHS)
556 !(LHS < RHS | LHS > RHS);
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
567 <div class="doc_code">
571 extern putchard(char)
575 else if d > 4 then
577 else if d > 2 then
580 putchard(42); # '*'</b>
582 ready> <b>printdensity(1): printdensity(2): printdensity(3) :
583 printdensity(4): printdensity(5): printdensity(9): putchard(10);</b>
585 Evaluated to 0.000000
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
594 <div class="doc_code">
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)
599 if iters > 255 | (real*real + imag*imag > 4) then
602 mandleconverger(real*real - imag*imag + creal,
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);
612 <p>This "z = z<sup>2</sup> + c" function is a beautiful little creature that is the basis
613 for computation of the <a
614 href="http://en.wikipedia.org/wiki/Mandelbrot_set">Mandelbrot Set</a>. Our
615 <tt>mandelconverge</tt> function returns the number of iterations that it takes
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>
622 <div class="doc_code">
624 # compute and plot the mandlebrot set with the specified 2 dimensional range
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)))
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);
641 <p>Given this, we can try plotting out the mandlebrot set! Lets try it out:</p>
643 <div class="doc_code">
645 ready> <b>mandel(-2.3, -1.3, 0.05, 0.07);</b>
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
688 ready> <b>mandel(-2, -1, 0.02, 0.04);</b>
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 *.......... ...........
715 *.......... ...........
716 *+++....++++................
717 *++++++++++++++..............
718 *++++++++++++++++............ ...
719 *++++++++++++++++++.................
720 **+++++++++++++++++++................
721 **+++++++++++++++++++++..............
722 ***++++++++++++++++++++++............
723 ***++++++++++++++++++++++++......... ...... ...........
724 ****++++++++++++++++++++++++++...... .........................
725 *****++++++++++++++++++++++++++++...............................
726 *****++++++++++++++++++++++++++++++++............................
727 ******+++++++++++++++++++++++++++++++++++...........................
728 *******+++++++++++++++++++++++++++++++++++++++.......................
729 ********+++++++++++++++++++++++++++++++++++++++++++..................
730 Evaluated to 0.000000
731 ready> <b>mandel(-0.9, -1.4, 0.02, 0.03);</b>
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 ......... ....+++++++
773 Evaluated to 0.000000
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>
782 <p>With this, we conclude the "adding user-defined operators" chapter of the
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.
790 <p>Strikingly, variable mutation is an important feature of some
791 languages, and it is not at all obvious how to <a href="LangImpl7.html">add
792 support for mutable variables</a> without having to add an "SSA construction"
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>
798 <!-- *********************************************************************** -->
799 <div class="doc_section"><a name="code">Full Code Listing</a></div>
800 <!-- *********************************************************************** -->
802 <div class="doc_text">
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:
809 <div class="doc_code">
812 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
818 <p>Here is the code:</p>
820 <div class="doc_code">
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/Target/TargetData.h"
830 #include "llvm/Target/TargetSelect.h"
831 #include "llvm/Transforms/Scalar.h"
832 #include "llvm/Support/IRBuilder.h"
833 #include <cstdio>
834 #include <string>
836 #include <vector>
837 using namespace llvm;
839 //===----------------------------------------------------------------------===//
841 //===----------------------------------------------------------------------===//
843 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
844 // of these for known things.
849 tok_def = -2, tok_extern = -3,
852 tok_identifier = -4, tok_number = -5,
855 tok_if = -6, tok_then = -7, tok_else = -8,
856 tok_for = -9, tok_in = -10,
859 tok_binary = -11, tok_unary = -12
862 static std::string IdentifierStr; // Filled in if tok_identifier
863 static double NumVal; // Filled in if tok_number
865 /// gettok - Return the next token from standard input.
866 static int gettok() {
867 static int LastChar = ' ';
869 // Skip any whitespace.
870 while (isspace(LastChar))
871 LastChar = getchar();
873 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
874 IdentifierStr = LastChar;
875 while (isalnum((LastChar = getchar())))
876 IdentifierStr += LastChar;
878 if (IdentifierStr == "def") return tok_def;
879 if (IdentifierStr == "extern") return tok_extern;
880 if (IdentifierStr == "if") return tok_if;
881 if (IdentifierStr == "then") return tok_then;
882 if (IdentifierStr == "else") return tok_else;
883 if (IdentifierStr == "for") return tok_for;
884 if (IdentifierStr == "in") return tok_in;
885 if (IdentifierStr == "binary") return tok_binary;
886 if (IdentifierStr == "unary") return tok_unary;
887 return tok_identifier;
890 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
894 LastChar = getchar();
895 } while (isdigit(LastChar) || LastChar == '.');
897 NumVal = strtod(NumStr.c_str(), 0);
901 if (LastChar == '#') {
902 // Comment until end of line.
903 do LastChar = getchar();
904 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
910 // Check for end of file. Don't eat the EOF.
914 // Otherwise, just return the character as its ascii value.
915 int ThisChar = LastChar;
916 LastChar = getchar();
920 //===----------------------------------------------------------------------===//
921 // Abstract Syntax Tree (aka Parse Tree)
922 //===----------------------------------------------------------------------===//
924 /// ExprAST - Base class for all expression nodes.
927 virtual ~ExprAST() {}
928 virtual Value *Codegen() = 0;
931 /// NumberExprAST - Expression class for numeric literals like "1.0".
932 class NumberExprAST : public ExprAST {
935 NumberExprAST(double val) : Val(val) {}
936 virtual Value *Codegen();
939 /// VariableExprAST - Expression class for referencing a variable, like "a".
940 class VariableExprAST : public ExprAST {
943 VariableExprAST(const std::string &name) : Name(name) {}
944 virtual Value *Codegen();
947 /// UnaryExprAST - Expression class for a unary operator.
948 class UnaryExprAST : public ExprAST {
952 UnaryExprAST(char opcode, ExprAST *operand)
953 : Opcode(opcode), Operand(operand) {}
954 virtual Value *Codegen();
957 /// BinaryExprAST - Expression class for a binary operator.
958 class BinaryExprAST : public ExprAST {
962 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
963 : Op(op), LHS(lhs), RHS(rhs) {}
964 virtual Value *Codegen();
967 /// CallExprAST - Expression class for function calls.
968 class CallExprAST : public ExprAST {
970 std::vector<ExprAST*> Args;
972 CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
973 : Callee(callee), Args(args) {}
974 virtual Value *Codegen();
977 /// IfExprAST - Expression class for if/then/else.
978 class IfExprAST : public ExprAST {
979 ExprAST *Cond, *Then, *Else;
981 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
982 : Cond(cond), Then(then), Else(_else) {}
983 virtual Value *Codegen();
986 /// ForExprAST - Expression class for for/in.
987 class ForExprAST : public ExprAST {
989 ExprAST *Start, *End, *Step, *Body;
991 ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end,
992 ExprAST *step, ExprAST *body)
993 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
994 virtual Value *Codegen();
997 /// PrototypeAST - This class represents the "prototype" for a function,
998 /// which captures its name, and its argument names (thus implicitly the number
999 /// of arguments the function takes), as well as if it is an operator.
1000 class PrototypeAST {
1002 std::vector<std::string> Args;
1004 unsigned Precedence; // Precedence if a binary op.
1006 PrototypeAST(const std::string &name, const std::vector<std::string> &args,
1007 bool isoperator = false, unsigned prec = 0)
1008 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1010 bool isUnaryOp() const { return isOperator && Args.size() == 1; }
1011 bool isBinaryOp() const { return isOperator && Args.size() == 2; }
1013 char getOperatorName() const {
1014 assert(isUnaryOp() || isBinaryOp());
1015 return Name[Name.size()-1];
1018 unsigned getBinaryPrecedence() const { return Precedence; }
1020 Function *Codegen();
1023 /// FunctionAST - This class represents a function definition itself.
1025 PrototypeAST *Proto;
1028 FunctionAST(PrototypeAST *proto, ExprAST *body)
1029 : Proto(proto), Body(body) {}
1031 Function *Codegen();
1034 //===----------------------------------------------------------------------===//
1036 //===----------------------------------------------------------------------===//
1038 /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1039 /// token the parser is looking at. getNextToken reads another token from the
1040 /// lexer and updates CurTok with its results.
1042 static int getNextToken() {
1043 return CurTok = gettok();
1046 /// BinopPrecedence - This holds the precedence for each binary operator that is
1048 static std::map<char, int> BinopPrecedence;
1050 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1051 static int GetTokPrecedence() {
1052 if (!isascii(CurTok))
1055 // Make sure it's a declared binop.
1056 int TokPrec = BinopPrecedence[CurTok];
1057 if (TokPrec <= 0) return -1;
1061 /// Error* - These are little helper functions for error handling.
1062 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1063 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1064 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1066 static ExprAST *ParseExpression();
1070 /// ::= identifier '(' expression* ')'
1071 static ExprAST *ParseIdentifierExpr() {
1072 std::string IdName = IdentifierStr;
1074 getNextToken(); // eat identifier.
1076 if (CurTok != '(') // Simple variable ref.
1077 return new VariableExprAST(IdName);
1080 getNextToken(); // eat (
1081 std::vector<ExprAST*> Args;
1082 if (CurTok != ')') {
1084 ExprAST *Arg = ParseExpression();
1086 Args.push_back(Arg);
1088 if (CurTok == ')') break;
1091 return Error("Expected ')' or ',' in argument list");
1099 return new CallExprAST(IdName, Args);
1102 /// numberexpr ::= number
1103 static ExprAST *ParseNumberExpr() {
1104 ExprAST *Result = new NumberExprAST(NumVal);
1105 getNextToken(); // consume the number
1109 /// parenexpr ::= '(' expression ')'
1110 static ExprAST *ParseParenExpr() {
1111 getNextToken(); // eat (.
1112 ExprAST *V = ParseExpression();
1116 return Error("expected ')'");
1117 getNextToken(); // eat ).
1121 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1122 static ExprAST *ParseIfExpr() {
1123 getNextToken(); // eat the if.
1126 ExprAST *Cond = ParseExpression();
1127 if (!Cond) return 0;
1129 if (CurTok != tok_then)
1130 return Error("expected then");
1131 getNextToken(); // eat the then
1133 ExprAST *Then = ParseExpression();
1134 if (Then == 0) return 0;
1136 if (CurTok != tok_else)
1137 return Error("expected else");
1141 ExprAST *Else = ParseExpression();
1142 if (!Else) return 0;
1144 return new IfExprAST(Cond, Then, Else);
1147 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1148 static ExprAST *ParseForExpr() {
1149 getNextToken(); // eat the for.
1151 if (CurTok != tok_identifier)
1152 return Error("expected identifier after for");
1154 std::string IdName = IdentifierStr;
1155 getNextToken(); // eat identifier.
1158 return Error("expected '=' after for");
1159 getNextToken(); // eat '='.
1162 ExprAST *Start = ParseExpression();
1163 if (Start == 0) return 0;
1165 return Error("expected ',' after for start value");
1168 ExprAST *End = ParseExpression();
1169 if (End == 0) return 0;
1171 // The step value is optional.
1173 if (CurTok == ',') {
1175 Step = ParseExpression();
1176 if (Step == 0) return 0;
1179 if (CurTok != tok_in)
1180 return Error("expected 'in' after for");
1181 getNextToken(); // eat 'in'.
1183 ExprAST *Body = ParseExpression();
1184 if (Body == 0) return 0;
1186 return new ForExprAST(IdName, Start, End, Step, Body);
1190 /// ::= identifierexpr
1195 static ExprAST *ParsePrimary() {
1197 default: return Error("unknown token when expecting an expression");
1198 case tok_identifier: return ParseIdentifierExpr();
1199 case tok_number: return ParseNumberExpr();
1200 case '(': return ParseParenExpr();
1201 case tok_if: return ParseIfExpr();
1202 case tok_for: return ParseForExpr();
1209 static ExprAST *ParseUnary() {
1210 // If the current token is not an operator, it must be a primary expr.
1211 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1212 return ParsePrimary();
1214 // If this is a unary operator, read it.
1217 if (ExprAST *Operand = ParseUnary())
1218 return new UnaryExprAST(Opc, Operand);
1223 /// ::= ('+' unary)*
1224 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1225 // If this is a binop, find its precedence.
1227 int TokPrec = GetTokPrecedence();
1229 // If this is a binop that binds at least as tightly as the current binop,
1230 // consume it, otherwise we are done.
1231 if (TokPrec < ExprPrec)
1234 // Okay, we know this is a binop.
1236 getNextToken(); // eat binop
1238 // Parse the unary expression after the binary operator.
1239 ExprAST *RHS = ParseUnary();
1242 // If BinOp binds less tightly with RHS than the operator after RHS, let
1243 // the pending operator take RHS as its LHS.
1244 int NextPrec = GetTokPrecedence();
1245 if (TokPrec < NextPrec) {
1246 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1247 if (RHS == 0) return 0;
1251 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1256 /// ::= unary binoprhs
1258 static ExprAST *ParseExpression() {
1259 ExprAST *LHS = ParseUnary();
1262 return ParseBinOpRHS(0, LHS);
1266 /// ::= id '(' id* ')'
1267 /// ::= binary LETTER number? (id, id)
1268 /// ::= unary LETTER (id)
1269 static PrototypeAST *ParsePrototype() {
1272 unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
1273 unsigned BinaryPrecedence = 30;
1277 return ErrorP("Expected function name in prototype");
1278 case tok_identifier:
1279 FnName = IdentifierStr;
1285 if (!isascii(CurTok))
1286 return ErrorP("Expected unary operator");
1288 FnName += (char)CurTok;
1294 if (!isascii(CurTok))
1295 return ErrorP("Expected binary operator");
1297 FnName += (char)CurTok;
1301 // Read the precedence if present.
1302 if (CurTok == tok_number) {
1303 if (NumVal < 1 || NumVal > 100)
1304 return ErrorP("Invalid precedecnce: must be 1..100");
1305 BinaryPrecedence = (unsigned)NumVal;
1312 return ErrorP("Expected '(' in prototype");
1314 std::vector<std::string> ArgNames;
1315 while (getNextToken() == tok_identifier)
1316 ArgNames.push_back(IdentifierStr);
1318 return ErrorP("Expected ')' in prototype");
1321 getNextToken(); // eat ')'.
1323 // Verify right number of names for operator.
1324 if (Kind && ArgNames.size() != Kind)
1325 return ErrorP("Invalid number of operands for operator");
1327 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1330 /// definition ::= 'def' prototype expression
1331 static FunctionAST *ParseDefinition() {
1332 getNextToken(); // eat def.
1333 PrototypeAST *Proto = ParsePrototype();
1334 if (Proto == 0) return 0;
1336 if (ExprAST *E = ParseExpression())
1337 return new FunctionAST(Proto, E);
1341 /// toplevelexpr ::= expression
1342 static FunctionAST *ParseTopLevelExpr() {
1343 if (ExprAST *E = ParseExpression()) {
1344 // Make an anonymous proto.
1345 PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
1346 return new FunctionAST(Proto, E);
1351 /// external ::= 'extern' prototype
1352 static PrototypeAST *ParseExtern() {
1353 getNextToken(); // eat extern.
1354 return ParsePrototype();
1357 //===----------------------------------------------------------------------===//
1359 //===----------------------------------------------------------------------===//
1361 static Module *TheModule;
1362 static IRBuilder<> Builder(getGlobalContext());
1363 static std::map<std::string, Value*> NamedValues;
1364 static FunctionPassManager *TheFPM;
1366 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1368 Value *NumberExprAST::Codegen() {
1369 return ConstantFP::get(getGlobalContext(), APFloat(Val));
1372 Value *VariableExprAST::Codegen() {
1373 // Look this variable up in the function.
1374 Value *V = NamedValues[Name];
1375 return V ? V : ErrorV("Unknown variable name");
1378 Value *UnaryExprAST::Codegen() {
1379 Value *OperandV = Operand->Codegen();
1380 if (OperandV == 0) return 0;
1382 Function *F = TheModule->getFunction(std::string("unary")+Opcode);
1384 return ErrorV("Unknown unary operator");
1386 return Builder.CreateCall(F, OperandV, "unop");
1389 Value *BinaryExprAST::Codegen() {
1390 Value *L = LHS->Codegen();
1391 Value *R = RHS->Codegen();
1392 if (L == 0 || R == 0) return 0;
1395 case '+': return Builder.CreateFAdd(L, R, "addtmp");
1396 case '-': return Builder.CreateFSub(L, R, "subtmp");
1397 case '*': return Builder.CreateFMul(L, R, "multmp");
1399 L = Builder.CreateFCmpULT(L, R, "cmptmp");
1400 // Convert bool 0/1 to double 0.0 or 1.0
1401 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1406 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1408 Function *F = TheModule->getFunction(std::string("binary")+Op);
1409 assert(F && "binary operator not found!");
1411 Value *Ops[] = { L, R };
1412 return Builder.CreateCall(F, Ops, Ops+2, "binop");
1415 Value *CallExprAST::Codegen() {
1416 // Look up the name in the global module table.
1417 Function *CalleeF = TheModule->getFunction(Callee);
1419 return ErrorV("Unknown function referenced");
1421 // If argument mismatch error.
1422 if (CalleeF->arg_size() != Args.size())
1423 return ErrorV("Incorrect # arguments passed");
1425 std::vector<Value*> ArgsV;
1426 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1427 ArgsV.push_back(Args[i]->Codegen());
1428 if (ArgsV.back() == 0) return 0;
1431 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1434 Value *IfExprAST::Codegen() {
1435 Value *CondV = Cond->Codegen();
1436 if (CondV == 0) return 0;
1438 // Convert condition to a bool by comparing equal to 0.0.
1439 CondV = Builder.CreateFCmpONE(CondV,
1440 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1443 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1445 // Create blocks for the then and else cases. Insert the 'then' block at the
1446 // end of the function.
1447 BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1448 BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1449 BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1451 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1454 Builder.SetInsertPoint(ThenBB);
1456 Value *ThenV = Then->Codegen();
1457 if (ThenV == 0) return 0;
1459 Builder.CreateBr(MergeBB);
1460 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1461 ThenBB = Builder.GetInsertBlock();
1464 TheFunction->getBasicBlockList().push_back(ElseBB);
1465 Builder.SetInsertPoint(ElseBB);
1467 Value *ElseV = Else->Codegen();
1468 if (ElseV == 0) return 0;
1470 Builder.CreateBr(MergeBB);
1471 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1472 ElseBB = Builder.GetInsertBlock();
1474 // Emit merge block.
1475 TheFunction->getBasicBlockList().push_back(MergeBB);
1476 Builder.SetInsertPoint(MergeBB);
1477 PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
1480 PN->addIncoming(ThenV, ThenBB);
1481 PN->addIncoming(ElseV, ElseBB);
1485 Value *ForExprAST::Codegen() {
1488 // start = startexpr
1491 // variable = phi [start, loopheader], [nextvariable, loopend]
1497 // nextvariable = variable + step
1498 // endcond = endexpr
1499 // br endcond, loop, endloop
1502 // Emit the start code first, without 'variable' in scope.
1503 Value *StartVal = Start->Codegen();
1504 if (StartVal == 0) return 0;
1506 // Make the new basic block for the loop header, inserting after current
1508 Function *TheFunction = Builder.GetInsertBlock()->getParent();
1509 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1510 BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1512 // Insert an explicit fall through from the current block to the LoopBB.
1513 Builder.CreateBr(LoopBB);
1515 // Start insertion in LoopBB.
1516 Builder.SetInsertPoint(LoopBB);
1518 // Start the PHI node with an entry for Start.
1519 PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
1520 Variable->addIncoming(StartVal, PreheaderBB);
1522 // Within the loop, the variable is defined equal to the PHI node. If it
1523 // shadows an existing variable, we have to restore it, so save it now.
1524 Value *OldVal = NamedValues[VarName];
1525 NamedValues[VarName] = Variable;
1527 // Emit the body of the loop. This, like any other expr, can change the
1528 // current BB. Note that we ignore the value computed by the body, but don't
1530 if (Body->Codegen() == 0)
1533 // Emit the step value.
1536 StepVal = Step->Codegen();
1537 if (StepVal == 0) return 0;
1539 // If not specified, use 1.0.
1540 StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1543 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
1545 // Compute the end condition.
1546 Value *EndCond = End->Codegen();
1547 if (EndCond == 0) return EndCond;
1549 // Convert condition to a bool by comparing equal to 0.0.
1550 EndCond = Builder.CreateFCmpONE(EndCond,
1551 ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1554 // Create the "after loop" block and insert it.
1555 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1556 BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1558 // Insert the conditional branch into the end of LoopEndBB.
1559 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1561 // Any new code will be inserted in AfterBB.
1562 Builder.SetInsertPoint(AfterBB);
1564 // Add a new entry to the PHI node for the backedge.
1565 Variable->addIncoming(NextVar, LoopEndBB);
1567 // Restore the unshadowed variable.
1569 NamedValues[VarName] = OldVal;
1571 NamedValues.erase(VarName);
1574 // for expr always returns 0.0.
1575 return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1578 Function *PrototypeAST::Codegen() {
1579 // Make the function type: double(double,double) etc.
1580 std::vector<const Type*> Doubles(Args.size(),
1581 Type::getDoubleTy(getGlobalContext()));
1582 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1585 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1587 // If F conflicted, there was already something named 'Name'. If it has a
1588 // body, don't allow redefinition or reextern.
1589 if (F->getName() != Name) {
1590 // Delete the one we just made and get the existing one.
1591 F->eraseFromParent();
1592 F = TheModule->getFunction(Name);
1594 // If F already has a body, reject this.
1595 if (!F->empty()) {
1596 ErrorF("redefinition of function");
1600 // If F took a different number of args, reject.
1601 if (F->arg_size() != Args.size()) {
1602 ErrorF("redefinition of function with different # args");
1607 // Set names for all arguments.
1609 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
1611 AI->setName(Args[Idx]);
1613 // Add arguments to variable symbol table.
1614 NamedValues[Args[Idx]] = AI;
1620 Function *FunctionAST::Codegen() {
1621 NamedValues.clear();
1623 Function *TheFunction = Proto->Codegen();
1624 if (TheFunction == 0)
1627 // If this is an operator, install it.
1628 if (Proto->isBinaryOp())
1629 BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();
1631 // Create a new basic block to start insertion into.
1632 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1633 Builder.SetInsertPoint(BB);
1635 if (Value *RetVal = Body->Codegen()) {
1636 // Finish off the function.
1637 Builder.CreateRet(RetVal);
1639 // Validate the generated code, checking for consistency.
1640 verifyFunction(*TheFunction);
1642 // Optimize the function.
1643 TheFPM->run(*TheFunction);
1648 // Error reading body, remove function.
1649 TheFunction->eraseFromParent();
1651 if (Proto->isBinaryOp())
1652 BinopPrecedence.erase(Proto->getOperatorName());
1656 //===----------------------------------------------------------------------===//
1657 // Top-Level parsing and JIT Driver
1658 //===----------------------------------------------------------------------===//
1660 static ExecutionEngine *TheExecutionEngine;
1662 static void HandleDefinition() {
1663 if (FunctionAST *F = ParseDefinition()) {
1664 if (Function *LF = F->Codegen()) {
1665 fprintf(stderr, "Read function definition:");
1669 // Skip token for error recovery.
1674 static void HandleExtern() {
1675 if (PrototypeAST *P = ParseExtern()) {
1676 if (Function *F = P->Codegen()) {
1677 fprintf(stderr, "Read extern: ");
1681 // Skip token for error recovery.
1686 static void HandleTopLevelExpression() {
1687 // Evaluate a top-level expression into an anonymous function.
1688 if (FunctionAST *F = ParseTopLevelExpr()) {
1689 if (Function *LF = F->Codegen()) {
1690 // JIT the function, returning a function pointer.
1691 void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
1693 // Cast it to the right type (takes no arguments, returns a double) so we
1694 // can call it as a native function.
1695 double (*FP)() = (double (*)())(intptr_t)FPtr;
1696 fprintf(stderr, "Evaluated to %f\n", FP());
1699 // Skip token for error recovery.
1704 /// top ::= definition | external | expression | ';'
1705 static void MainLoop() {
1707 fprintf(stderr, "ready> ");
1709 case tok_eof: return;
1710 case ';': getNextToken(); break; // ignore top-level semicolons.
1711 case tok_def: HandleDefinition(); break;
1712 case tok_extern: HandleExtern(); break;
1713 default: HandleTopLevelExpression(); break;
1718 //===----------------------------------------------------------------------===//
1719 // "Library" functions that can be "extern'd" from user code.
1720 //===----------------------------------------------------------------------===//
1722 /// putchard - putchar that takes a double and returns 0.
1724 double putchard(double X) {
1729 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1731 double printd(double X) {
1736 //===----------------------------------------------------------------------===//
1737 // Main driver code.
1738 //===----------------------------------------------------------------------===//
1741 InitializeNativeTarget();
1742 LLVMContext &Context = getGlobalContext();
1744 // Install standard binary operators.
1745 // 1 is lowest precedence.
1746 BinopPrecedence['<'] = 10;
1747 BinopPrecedence['+'] = 20;
1748 BinopPrecedence['-'] = 20;
1749 BinopPrecedence['*'] = 40; // highest.
1751 // Prime the first token.
1752 fprintf(stderr, "ready> ");
1755 // Make the module, which holds all the code.
1756 TheModule = new Module("my cool jit", Context);
1758 // Create the JIT. This takes ownership of the module.
1760 TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
1761 if (!TheExecutionEngine) {
1762 fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1766 FunctionPassManager OurFPM(TheModule);
1768 // Set up the optimizer pipeline. Start with registering info about how the
1769 // target lays out data structures.
1770 OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
1771 // Do simple "peephole" optimizations and bit-twiddling optzns.
1772 OurFPM.add(createInstructionCombiningPass());
1773 // Reassociate expressions.
1774 OurFPM.add(createReassociatePass());
1775 // Eliminate Common SubExpressions.
1776 OurFPM.add(createGVNPass());
1777 // Simplify the control flow graph (deleting unreachable blocks, etc).
1778 OurFPM.add(createCFGSimplificationPass());
1780 OurFPM.doInitialization();
1782 // Set the global so the code gen can use this.
1783 TheFPM = &OurFPM;
1785 // Run the main "interpreter loop" now.
1790 // Print out all of the generated code.
1791 TheModule->dump();
1798 <a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a>
1801 <!-- *********************************************************************** -->
1804 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1805 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1806 <a href="http://validator.w3.org/check/referer"><img
1807 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1809 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1810 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1811 Last modified: $Date$