docs/tutorial/LangImpl6.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   2                       "http://www.w3.org/TR/html4/strict.dtd">
   3
   4 <html>
   5 <head>
   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">
  10 </head>
  11
  12 <body>
  13
  14 <h1>Kaleidoscope: Extending the Language: User-defined Operators</h1>
  15
  16 <ul>
  17 <li><a href="index.html">Up to Tutorial Index</a></li>
  18 <li>Chapter 6
  19   <ol>
  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>
  26   </ol>
  27 </li>
  28 <li><a href="LangImpl7.html">Chapter 7</a>: Extending the Language: Mutable
  29 Variables / SSA Construction</li>
  30 </ul>
  31
  32 <div class="doc_author">
  33   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
  34 </div>
  35
  36 <!-- *********************************************************************** -->
  37 <h2><a name="intro">Chapter 6 Introduction</a></h2>
  38 <!-- *********************************************************************** -->
  39
  40 <div>
  41
  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>
  48
  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>
  55
  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>
  59
  60 </div>
  61
  62 <!-- *********************************************************************** -->
  63 <h2><a name="idea">User-defined Operators: the Idea</a></h2>
  64 <!-- *********************************************************************** -->
  65
  66 <div>
  67
  68 <p>
  69 The "operator overloading" that we will add to Kaleidoscope is more general than
  70 languages like C++.  In C++, you are only allowed to redefine existing
  71 operators: you can't programatically change the grammar, introduce new
  72 operators, change precedence levels, etc.  In this chapter, we will add this
  73 capability to Kaleidoscope, which will let the user round out the set of
  74 operators that are supported.</p>
  75
  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
  83 as the JIT runs.</p>
  84
  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>
  88
  89 <div class="doc_code">
  90 <pre>
  91 # Logical unary not.
  92 def unary!(v)
  93   if v then
  94     0
  95   else
  96     1;
  97
  98 # Define &gt; with the same precedence as &lt;.
  99 def binary&gt; 10 (LHS RHS)
 100   RHS &lt; LHS;
 101
 102 # Binary "logical or", (note that it does not "short circuit")
 103 def binary| 5 (LHS RHS)
 104   if LHS then
 105     1
 106   else if RHS then
 107     1
 108   else
 109     0;
 110
 111 # Define = with slightly lower precedence than relationals.
 112 def binary= 9 (LHS RHS)
 113   !(LHS &lt; RHS | LHS &gt; RHS);
 114 </pre>
 115 </div>
 116
 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>
 120
 121 <p>We will break down implementation of these features into two parts:
 122 implementing support for user-defined binary operators and adding unary
 123 operators.</p>
 124
 125 </div>
 126
 127 <!-- *********************************************************************** -->
 128 <h2><a name="binary">User-defined Binary Operators</a></h2>
 129 <!-- *********************************************************************** -->
 130
 131 <div>
 132
 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>
 135
 136 <div class="doc_code">
 137 <pre>
 138 enum Token {
 139   ...
 140   <b>// operators
 141   tok_binary = -11, tok_unary = -12</b>
 142 };
 143 ...
 144 static int gettok() {
 145 ...
 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;
 151 </pre>
 152 </div>
 153
 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>
 159
 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>
 166
 167 <div class="doc_code">
 168 <pre>
 169 /// PrototypeAST - This class represents the "prototype" for a function,
 170 /// which captures its argument names as well as if it is an operator.
 171 class PrototypeAST {
 172   std::string Name;
 173   std::vector&lt;std::string&gt; Args;
 174   <b>bool isOperator;
 175   unsigned Precedence;  // Precedence if a binary op.</b>
 176 public:
 177   PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args,
 178                <b>bool isoperator = false, unsigned prec = 0</b>)
 179   : Name(name), Args(args), <b>isOperator(isoperator), Precedence(prec)</b> {}
 180
 181   <b>bool isUnaryOp() const { return isOperator &amp;&amp; Args.size() == 1; }
 182   bool isBinaryOp() const { return isOperator &amp;&amp; Args.size() == 2; }
 183
 184   char getOperatorName() const {
 185     assert(isUnaryOp() || isBinaryOp());
 186     return Name[Name.size()-1];
 187   }
 188
 189   unsigned getBinaryPrecedence() const { return Precedence; }</b>
 190
 191   Function *Codegen();
 192 };
 193 </pre>
 194 </div>
 195
 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>
 201
 202 <div class="doc_code">
 203 <pre>
 204 /// prototype
 205 ///   ::= id '(' id* ')'
 206 <b>///   ::= binary LETTER number? (id, id)</b>
 207 static PrototypeAST *ParsePrototype() {
 208   std::string FnName;
 209
 210   <b>unsigned Kind = 0;  // 0 = identifier, 1 = unary, 2 = binary.
 211   unsigned BinaryPrecedence = 30;</b>
 212
 213   switch (CurTok) {
 214   default:
 215     return ErrorP("Expected function name in prototype");
 216   case tok_identifier:
 217     FnName = IdentifierStr;
 218     Kind = 0;
 219     getNextToken();
 220     break;
 221   <b>case tok_binary:
 222     getNextToken();
 223     if (!isascii(CurTok))
 224       return ErrorP("Expected binary operator");
 225     FnName = "binary";
 226     FnName += (char)CurTok;
 227     Kind = 2;
 228     getNextToken();
 229
 230     // Read the precedence if present.
 231     if (CurTok == tok_number) {
 232       if (NumVal &lt; 1 || NumVal &gt; 100)
 233         return ErrorP("Invalid precedecnce: must be 1..100");
 234       BinaryPrecedence = (unsigned)NumVal;
 235       getNextToken();
 236     }
 237     break;</b>
 238   }
 239
 240   if (CurTok != '(')
 241     return ErrorP("Expected '(' in prototype");
 242
 243   std::vector&lt;std::string&gt; ArgNames;
 244   while (getNextToken() == tok_identifier)
 245     ArgNames.push_back(IdentifierStr);
 246   if (CurTok != ')')
 247     return ErrorP("Expected ')' in prototype");
 248
 249   // success.
 250   getNextToken();  // eat ')'.
 251
 252   <b>// Verify right number of names for operator.
 253   if (Kind &amp;&amp; ArgNames.size() != Kind)
 254     return ErrorP("Invalid number of operands for operator");
 255
 256   return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);</b>
 257 }
 258 </pre>
 259 </div>
 260
 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>
 267
 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>
 271
 272 <div class="doc_code">
 273 <pre>
 274 Value *BinaryExprAST::Codegen() {
 275   Value *L = LHS-&gt;Codegen();
 276   Value *R = RHS-&gt;Codegen();
 277   if (L == 0 || R == 0) return 0;
 278
 279   switch (Op) {
 280   case '+': return Builder.CreateFAdd(L, R, "addtmp");
 281   case '-': return Builder.CreateFSub(L, R, "subtmp");
 282   case '*': return Builder.CreateFMul(L, R, "multmp");
 283   case '&lt;':
 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()),
 287                                 "booltmp");
 288   <b>default: break;</b>
 289   }
 290
 291   <b>// If it wasn't a builtin binary operator, it must be a user defined one. Emit
 292   // a call to it.
 293   Function *F = TheModule-&gt;getFunction(std::string("binary")+Op);
 294   assert(F &amp;&amp; "binary operator not found!");
 295
 296   Value *Ops[] = { L, R };
 297   return Builder.CreateCall(F, Ops, Ops+2, "binop");</b>
 298 }
 299
 300 </pre>
 301 </div>
 302
 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>
 308
 309 <p>The final piece of code we are missing, is a bit of top-level magic:</p>
 310
 311 <div class="doc_code">
 312 <pre>
 313 Function *FunctionAST::Codegen() {
 314   NamedValues.clear();
 315
 316   Function *TheFunction = Proto->Codegen();
 317   if (TheFunction == 0)
 318     return 0;
 319
 320   <b>// If this is an operator, install it.
 321   if (Proto-&gt;isBinaryOp())
 322     BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();</b>
 323
 324   // Create a new basic block to start insertion into.
 325   BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
 326   Builder.SetInsertPoint(BB);
 327
 328   if (Value *RetVal = Body-&gt;Codegen()) {
 329     ...
 330 </pre>
 331 </div>
 332
 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>
 336
 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>
 341
 342 </div>
 343
 344 <!-- *********************************************************************** -->
 345 <h2><a name="unary">User-defined Unary Operators</a></h2>
 346 <!-- *********************************************************************** -->
 347
 348 <div>
 349
 350 <p>Since we don't currently support unary operators in the Kaleidoscope
 351 language, we'll need to add everything to support them.  Above, we added simple
 352 support for the 'unary' keyword to the lexer.  In addition to that, we need an
 353 AST node:</p>
 354
 355 <div class="doc_code">
 356 <pre>
 357 /// UnaryExprAST - Expression class for a unary operator.
 358 class UnaryExprAST : public ExprAST {
 359   char Opcode;
 360   ExprAST *Operand;
 361 public:
 362   UnaryExprAST(char opcode, ExprAST *operand)
 363     : Opcode(opcode), Operand(operand) {}
 364   virtual Value *Codegen();
 365 };
 366 </pre>
 367 </div>
 368
 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>
 373
 374 <div class="doc_code">
 375 <pre>
 376 /// unary
 377 ///   ::= primary
 378 ///   ::= '!' unary
 379 static ExprAST *ParseUnary() {
 380   // If the current token is not an operator, it must be a primary expr.
 381   if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
 382     return ParsePrimary();
 383
 384   // If this is a unary operator, read it.
 385   int Opc = CurTok;
 386   getNextToken();
 387   if (ExprAST *Operand = ParseUnary())
 388     return new UnaryExprAST(Opc, Operand);
 389   return 0;
 390 }
 391 </pre>
 392 </div>
 393
 394 <p>The grammar we add is pretty straightforward here.  If we see a unary
 395 operator when parsing a primary operator, we eat the operator as a prefix and
 396 parse the remaining piece as another unary operator.  This allows us to handle
 397 multiple unary operators (e.g. "!!x").  Note that unary operators can't have
 398 ambiguous parses like binary operators can, so there is no need for precedence
 399 information.</p>
 400
 401 <p>The problem with this function, is that we need to call ParseUnary from somewhere.
 402 To do this, we change previous callers of ParsePrimary to call ParseUnary
 403 instead:</p>
 404
 405 <div class="doc_code">
 406 <pre>
 407 /// binoprhs
 408 ///   ::= ('+' unary)*
 409 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
 410   ...
 411     <b>// Parse the unary expression after the binary operator.
 412     ExprAST *RHS = ParseUnary();
 413     if (!RHS) return 0;</b>
 414   ...
 415 }
 416 /// expression
 417 ///   ::= unary binoprhs
 418 ///
 419 static ExprAST *ParseExpression() {
 420   <b>ExprAST *LHS = ParseUnary();</b>
 421   if (!LHS) return 0;
 422
 423   return ParseBinOpRHS(0, LHS);
 424 }
 425 </pre>
 426 </div>
 427
 428 <p>With these two simple changes, we are now able to parse unary operators and build the
 429 AST for them.  Next up, we need to add parser support for prototypes, to parse
 430 the unary operator prototype.  We extend the binary operator code above
 431 with:</p>
 432
 433 <div class="doc_code">
 434 <pre>
 435 /// prototype
 436 ///   ::= id '(' id* ')'
 437 ///   ::= binary LETTER number? (id, id)
 438 <b>///   ::= unary LETTER (id)</b>
 439 static PrototypeAST *ParsePrototype() {
 440   std::string FnName;
 441
 442   unsigned Kind = 0;  // 0 = identifier, 1 = unary, 2 = binary.
 443   unsigned BinaryPrecedence = 30;
 444
 445   switch (CurTok) {
 446   default:
 447     return ErrorP("Expected function name in prototype");
 448   case tok_identifier:
 449     FnName = IdentifierStr;
 450     Kind = 0;
 451     getNextToken();
 452     break;
 453   <b>case tok_unary:
 454     getNextToken();
 455     if (!isascii(CurTok))
 456       return ErrorP("Expected unary operator");
 457     FnName = "unary";
 458     FnName += (char)CurTok;
 459     Kind = 1;
 460     getNextToken();
 461     break;</b>
 462   case tok_binary:
 463     ...
 464 </pre>
 465 </div>
 466
 467 <p>As with binary operators, we name unary operators with a name that includes
 468 the operator character.  This assists us at code generation time.  Speaking of,
 469 the final piece we need to add is codegen support for unary operators.  It looks
 470 like this:</p>
 471
 472 <div class="doc_code">
 473 <pre>
 474 Value *UnaryExprAST::Codegen() {
 475   Value *OperandV = Operand->Codegen();
 476   if (OperandV == 0) return 0;
 477
 478   Function *F = TheModule->getFunction(std::string("unary")+Opcode);
 479   if (F == 0)
 480     return ErrorV("Unknown unary operator");
 481
 482   return Builder.CreateCall(F, OperandV, "unop");
 483 }
 484 </pre>
 485 </div>
 486
 487 <p>This code is similar to, but simpler than, the code for binary operators.  It
 488 is simpler primarily because it doesn't need to handle any predefined operators.
 489 </p>
 490
 491 </div>
 492
 493 <!-- *********************************************************************** -->
 494 <h2><a name="example">Kicking the Tires</a></h2>
 495 <!-- *********************************************************************** -->
 496
 497 <div>
 498
 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>
 504
 505 <div class="doc_code">
 506 <pre>
 507 ready&gt; <b>extern printd(x);</b>
 508 Read extern: declare double @printd(double)
 509 ready&gt; <b>def binary : 1 (x y) 0;  # Low-precedence operator that ignores operands.</b>
 510 ..
 511 ready&gt; <b>printd(123) : printd(456) : printd(789);</b>
 512 123.000000
 513 456.000000
 514 789.000000
 515 Evaluated to 0.000000
 516 </pre>
 517 </div>
 518
 519 <p>We can also define a bunch of other "primitive" operations, such as:</p>
 520
 521 <div class="doc_code">
 522 <pre>
 523 # Logical unary not.
 524 def unary!(v)
 525   if v then
 526     0
 527   else
 528     1;
 529
 530 # Unary negate.
 531 def unary-(v)
 532   0-v;
 533
 534 # Define &gt; with the same precedence as &lt;.
 535 def binary&gt; 10 (LHS RHS)
 536   RHS &lt; LHS;
 537
 538 # Binary logical or, which does not short circuit.
 539 def binary| 5 (LHS RHS)
 540   if LHS then
 541     1
 542   else if RHS then
 543     1
 544   else
 545     0;
 546
 547 # Binary logical and, which does not short circuit.
 548 def binary&amp; 6 (LHS RHS)
 549   if !LHS then
 550     0
 551   else
 552     !!RHS;
 553
 554 # Define = with slightly lower precedence than relationals.
 555 def binary = 9 (LHS RHS)
 556   !(LHS &lt; RHS | LHS &gt; RHS);
 557
 558 </pre>
 559 </div>
 560
 561
 562 <p>Given the previous if/then/else support, we can also define interesting
 563 functions for I/O.  For example, the following prints out a character whose
 564 "density" reflects the value passed in: the lower the value, the denser the
 565 character:</p>
 566
 567 <div class="doc_code">
 568 <pre>
 569 ready&gt;
 570 <b>
 571 extern putchard(char)
 572 def printdensity(d)
 573   if d &gt; 8 then
 574     putchard(32)  # ' '
 575   else if d &gt; 4 then
 576     putchard(46)  # '.'
 577   else if d &gt; 2 then
 578     putchard(43)  # '+'
 579   else
 580     putchard(42); # '*'</b>
 581 ...
 582 ready&gt; <b>printdensity(1): printdensity(2): printdensity(3) :
 583           printdensity(4): printdensity(5): printdensity(9): putchard(10);</b>
 584 *++..
 585 Evaluated to 0.000000
 586 </pre>
 587 </div>
 588
 589 <p>Based on these simple primitive operations, we can start to define more
 590 interesting things.  For example, here's a little function that solves for the
 591 number of iterations it takes a function in the complex plane to
 592 converge:</p>
 593
 594 <div class="doc_code">
 595 <pre>
 596 # determine whether the specific location diverges.
 597 # Solve for z = z^2 + c in the complex plane.
 598 def mandleconverger(real imag iters creal cimag)
 599   if iters &gt; 255 | (real*real + imag*imag &gt; 4) then
 600     iters
 601   else
 602     mandleconverger(real*real - imag*imag + creal,
 603                     2*real*imag + cimag,
 604                     iters+1, creal, cimag);
 605
 606 # return the number of iterations required for the iteration to escape
 607 def mandleconverge(real imag)
 608   mandleconverger(real, imag, 0, real, imag);
 609 </pre>
 610 </div>
 611
 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>
 621
 622 <div class="doc_code">
 623 <pre>
 624 # compute and plot the mandlebrot set with the specified 2 dimensional range
 625 # info.
 626 def mandelhelp(xmin xmax xstep   ymin ymax ystep)
 627   for y = ymin, y &lt; ymax, ystep in (
 628     (for x = xmin, x &lt; xmax, xstep in
 629        printdensity(mandleconverge(x,y)))
 630     : putchard(10)
 631   )
 632
 633 # mandel - This is a convenient helper function for ploting the mandelbrot set
 634 # from the specified position with the specified Magnification.
 635 def mandel(realstart imagstart realmag imagmag)
 636   mandelhelp(realstart, realstart+realmag*78, realmag,
 637              imagstart, imagstart+imagmag*40, imagmag);
 638 </pre>
 639 </div>
 640
 641 <p>Given this, we can try plotting out the mandlebrot set!  Lets try it out:</p>
 642
 643 <div class="doc_code">
 644 <pre>
 645 ready&gt; <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&gt; <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 *..........  ...........
 714 *
 715 *..........  ...........
 716 *+++....++++................
 717 *++++++++++++++..............
 718 *++++++++++++++++............ ...
 719 *++++++++++++++++++.................
 720 **+++++++++++++++++++................
 721 **+++++++++++++++++++++..............
 722 ***++++++++++++++++++++++............
 723 ***++++++++++++++++++++++++.........     ......    ...........
 724 ****++++++++++++++++++++++++++......   .........................
 725 *****++++++++++++++++++++++++++++...............................
 726 *****++++++++++++++++++++++++++++++++............................
 727 ******+++++++++++++++++++++++++++++++++++...........................
 728 *******+++++++++++++++++++++++++++++++++++++++.......................
 729 ********+++++++++++++++++++++++++++++++++++++++++++..................
 730 Evaluated to 0.000000
 731 ready&gt; <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 .........                                                           ....+++++++
 766 ........                                                             ...+++++++
 767 .......                                                              ...+++++++
 768                                                                     ....+++++++
 769                                                                    .....+++++++
 770                                                                     ....+++++++
 771                                                                     ....+++++++
 772                                                                     ....+++++++
 773 Evaluated to 0.000000
 774 ready&gt; <b>^D</b>
 775 </pre>
 776 </div>
 777
 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>
 781
 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.
 788 </p>
 789
 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>
 795
 796 </div>
 797
 798 <!-- *********************************************************************** -->
 799 <h2><a name="code">Full Code Listing</a></h2>
 800 <!-- *********************************************************************** -->
 801
 802 <div>
 803
 804 <p>
 805 Here is the complete code listing for our running example, enhanced with the
 806 if/then/else and for expressions..  To build this example, use:
 807 </p>
 808
 809 <div class="doc_code">
 810 <pre>
 811    # Compile
 812    g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
 813    # Run
 814    ./toy
 815 </pre>
 816 </div>
 817
 818 <p>On some platforms, you will need to specify -rdynamic or -Wl,--export-dynamic
 819 when linking.  This ensures that symbols defined in the main executable are
 820 exported to the dynamic linker and so are available for symbol resolution at
 821 run time.  This is not needed if you compile your support code into a shared
 822 library, although doing that will cause problems on Windows.</p>
 823
 824 <p>Here is the code:</p>
 825
 826 <div class="doc_code">
 827 <pre>
 828 #include "llvm/DerivedTypes.h"
 829 #include "llvm/ExecutionEngine/ExecutionEngine.h"
 830 #include "llvm/ExecutionEngine/JIT.h"
 831 #include "llvm/LLVMContext.h"
 832 #include "llvm/Module.h"
 833 #include "llvm/PassManager.h"
 834 #include "llvm/Analysis/Verifier.h"
 835 #include "llvm/Analysis/Passes.h"
 836 #include "llvm/Target/TargetData.h"
 837 #include "llvm/Target/TargetSelect.h"
 838 #include "llvm/Transforms/Scalar.h"
 839 #include "llvm/Support/IRBuilder.h"
 840 #include &lt;cstdio&gt;
 841 #include &lt;string&gt;
 842 #include &lt;map&gt;
 843 #include &lt;vector&gt;
 844 using namespace llvm;
 845
 846 //===----------------------------------------------------------------------===//
 847 // Lexer
 848 //===----------------------------------------------------------------------===//
 849
 850 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
 851 // of these for known things.
 852 enum Token {
 853   tok_eof = -1,
 854
 855   // commands
 856   tok_def = -2, tok_extern = -3,
 857
 858   // primary
 859   tok_identifier = -4, tok_number = -5,
 860
 861   // control
 862   tok_if = -6, tok_then = -7, tok_else = -8,
 863   tok_for = -9, tok_in = -10,
 864
 865   // operators
 866   tok_binary = -11, tok_unary = -12
 867 };
 868
 869 static std::string IdentifierStr;  // Filled in if tok_identifier
 870 static double NumVal;              // Filled in if tok_number
 871
 872 /// gettok - Return the next token from standard input.
 873 static int gettok() {
 874   static int LastChar = ' ';
 875
 876   // Skip any whitespace.
 877   while (isspace(LastChar))
 878     LastChar = getchar();
 879
 880   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
 881     IdentifierStr = LastChar;
 882     while (isalnum((LastChar = getchar())))
 883       IdentifierStr += LastChar;
 884
 885     if (IdentifierStr == "def") return tok_def;
 886     if (IdentifierStr == "extern") return tok_extern;
 887     if (IdentifierStr == "if") return tok_if;
 888     if (IdentifierStr == "then") return tok_then;
 889     if (IdentifierStr == "else") return tok_else;
 890     if (IdentifierStr == "for") return tok_for;
 891     if (IdentifierStr == "in") return tok_in;
 892     if (IdentifierStr == "binary") return tok_binary;
 893     if (IdentifierStr == "unary") return tok_unary;
 894     return tok_identifier;
 895   }
 896
 897   if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
 898     std::string NumStr;
 899     do {
 900       NumStr += LastChar;
 901       LastChar = getchar();
 902     } while (isdigit(LastChar) || LastChar == '.');
 903
 904     NumVal = strtod(NumStr.c_str(), 0);
 905     return tok_number;
 906   }
 907
 908   if (LastChar == '#') {
 909     // Comment until end of line.
 910     do LastChar = getchar();
 911     while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
 912
 913     if (LastChar != EOF)
 914       return gettok();
 915   }
 916
 917   // Check for end of file.  Don't eat the EOF.
 918   if (LastChar == EOF)
 919     return tok_eof;
 920
 921   // Otherwise, just return the character as its ascii value.
 922   int ThisChar = LastChar;
 923   LastChar = getchar();
 924   return ThisChar;
 925 }
 926
 927 //===----------------------------------------------------------------------===//
 928 // Abstract Syntax Tree (aka Parse Tree)
 929 //===----------------------------------------------------------------------===//
 930
 931 /// ExprAST - Base class for all expression nodes.
 932 class ExprAST {
 933 public:
 934   virtual ~ExprAST() {}
 935   virtual Value *Codegen() = 0;
 936 };
 937
 938 /// NumberExprAST - Expression class for numeric literals like "1.0".
 939 class NumberExprAST : public ExprAST {
 940   double Val;
 941 public:
 942   NumberExprAST(double val) : Val(val) {}
 943   virtual Value *Codegen();
 944 };
 945
 946 /// VariableExprAST - Expression class for referencing a variable, like "a".
 947 class VariableExprAST : public ExprAST {
 948   std::string Name;
 949 public:
 950   VariableExprAST(const std::string &amp;name) : Name(name) {}
 951   virtual Value *Codegen();
 952 };
 953
 954 /// UnaryExprAST - Expression class for a unary operator.
 955 class UnaryExprAST : public ExprAST {
 956   char Opcode;
 957   ExprAST *Operand;
 958 public:
 959   UnaryExprAST(char opcode, ExprAST *operand)
 960     : Opcode(opcode), Operand(operand) {}
 961   virtual Value *Codegen();
 962 };
 963
 964 /// BinaryExprAST - Expression class for a binary operator.
 965 class BinaryExprAST : public ExprAST {
 966   char Op;
 967   ExprAST *LHS, *RHS;
 968 public:
 969   BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
 970     : Op(op), LHS(lhs), RHS(rhs) {}
 971   virtual Value *Codegen();
 972 };
 973
 974 /// CallExprAST - Expression class for function calls.
 975 class CallExprAST : public ExprAST {
 976   std::string Callee;
 977   std::vector&lt;ExprAST*&gt; Args;
 978 public:
 979   CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
 980     : Callee(callee), Args(args) {}
 981   virtual Value *Codegen();
 982 };
 983
 984 /// IfExprAST - Expression class for if/then/else.
 985 class IfExprAST : public ExprAST {
 986   ExprAST *Cond, *Then, *Else;
 987 public:
 988   IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
 989   : Cond(cond), Then(then), Else(_else) {}
 990   virtual Value *Codegen();
 991 };
 992
 993 /// ForExprAST - Expression class for for/in.
 994 class ForExprAST : public ExprAST {
 995   std::string VarName;
 996   ExprAST *Start, *End, *Step, *Body;
 997 public:
 998   ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
 999              ExprAST *step, ExprAST *body)
1000     : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1001   virtual Value *Codegen();
1002 };
1003
1004 /// PrototypeAST - This class represents the "prototype" for a function,
1005 /// which captures its name, and its argument names (thus implicitly the number
1006 /// of arguments the function takes), as well as if it is an operator.
1007 class PrototypeAST {
1008   std::string Name;
1009   std::vector&lt;std::string&gt; Args;
1010   bool isOperator;
1011   unsigned Precedence;  // Precedence if a binary op.
1012 public:
1013   PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args,
1014                bool isoperator = false, unsigned prec = 0)
1015   : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1016
1017   bool isUnaryOp() const { return isOperator &amp;&amp; Args.size() == 1; }
1018   bool isBinaryOp() const { return isOperator &amp;&amp; Args.size() == 2; }
1019
1020   char getOperatorName() const {
1021     assert(isUnaryOp() || isBinaryOp());
1022     return Name[Name.size()-1];
1023   }
1024
1025   unsigned getBinaryPrecedence() const { return Precedence; }
1026
1027   Function *Codegen();
1028 };
1029
1030 /// FunctionAST - This class represents a function definition itself.
1031 class FunctionAST {
1032   PrototypeAST *Proto;
1033   ExprAST *Body;
1034 public:
1035   FunctionAST(PrototypeAST *proto, ExprAST *body)
1036     : Proto(proto), Body(body) {}
1037
1038   Function *Codegen();
1039 };
1040
1041 //===----------------------------------------------------------------------===//
1042 // Parser
1043 //===----------------------------------------------------------------------===//
1044
1045 /// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
1046 /// token the parser is looking at.  getNextToken reads another token from the
1047 /// lexer and updates CurTok with its results.
1048 static int CurTok;
1049 static int getNextToken() {
1050   return CurTok = gettok();
1051 }
1052
1053 /// BinopPrecedence - This holds the precedence for each binary operator that is
1054 /// defined.
1055 static std::map&lt;char, int&gt; BinopPrecedence;
1056
1057 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1058 static int GetTokPrecedence() {
1059   if (!isascii(CurTok))
1060     return -1;
1061
1062   // Make sure it's a declared binop.
1063   int TokPrec = BinopPrecedence[CurTok];
1064   if (TokPrec &lt;= 0) return -1;
1065   return TokPrec;
1066 }
1067
1068 /// Error* - These are little helper functions for error handling.
1069 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1070 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1071 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1072
1073 static ExprAST *ParseExpression();
1074
1075 /// identifierexpr
1076 ///   ::= identifier
1077 ///   ::= identifier '(' expression* ')'
1078 static ExprAST *ParseIdentifierExpr() {
1079   std::string IdName = IdentifierStr;
1080
1081   getNextToken();  // eat identifier.
1082
1083   if (CurTok != '(') // Simple variable ref.
1084     return new VariableExprAST(IdName);
1085
1086   // Call.
1087   getNextToken();  // eat (
1088   std::vector&lt;ExprAST*&gt; Args;
1089   if (CurTok != ')') {
1090     while (1) {
1091       ExprAST *Arg = ParseExpression();
1092       if (!Arg) return 0;
1093       Args.push_back(Arg);
1094
1095       if (CurTok == ')') break;
1096
1097       if (CurTok != ',')
1098         return Error("Expected ')' or ',' in argument list");
1099       getNextToken();
1100     }
1101   }
1102
1103   // Eat the ')'.
1104   getNextToken();
1105
1106   return new CallExprAST(IdName, Args);
1107 }
1108
1109 /// numberexpr ::= number
1110 static ExprAST *ParseNumberExpr() {
1111   ExprAST *Result = new NumberExprAST(NumVal);
1112   getNextToken(); // consume the number
1113   return Result;
1114 }
1115
1116 /// parenexpr ::= '(' expression ')'
1117 static ExprAST *ParseParenExpr() {
1118   getNextToken();  // eat (.
1119   ExprAST *V = ParseExpression();
1120   if (!V) return 0;
1121
1122   if (CurTok != ')')
1123     return Error("expected ')'");
1124   getNextToken();  // eat ).
1125   return V;
1126 }
1127
1128 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1129 static ExprAST *ParseIfExpr() {
1130   getNextToken();  // eat the if.
1131
1132   // condition.
1133   ExprAST *Cond = ParseExpression();
1134   if (!Cond) return 0;
1135
1136   if (CurTok != tok_then)
1137     return Error("expected then");
1138   getNextToken();  // eat the then
1139
1140   ExprAST *Then = ParseExpression();
1141   if (Then == 0) return 0;
1142
1143   if (CurTok != tok_else)
1144     return Error("expected else");
1145
1146   getNextToken();
1147
1148   ExprAST *Else = ParseExpression();
1149   if (!Else) return 0;
1150
1151   return new IfExprAST(Cond, Then, Else);
1152 }
1153
1154 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1155 static ExprAST *ParseForExpr() {
1156   getNextToken();  // eat the for.
1157
1158   if (CurTok != tok_identifier)
1159     return Error("expected identifier after for");
1160
1161   std::string IdName = IdentifierStr;
1162   getNextToken();  // eat identifier.
1163
1164   if (CurTok != '=')
1165     return Error("expected '=' after for");
1166   getNextToken();  // eat '='.
1167
1168
1169   ExprAST *Start = ParseExpression();
1170   if (Start == 0) return 0;
1171   if (CurTok != ',')
1172     return Error("expected ',' after for start value");
1173   getNextToken();
1174
1175   ExprAST *End = ParseExpression();
1176   if (End == 0) return 0;
1177
1178   // The step value is optional.
1179   ExprAST *Step = 0;
1180   if (CurTok == ',') {
1181     getNextToken();
1182     Step = ParseExpression();
1183     if (Step == 0) return 0;
1184   }
1185
1186   if (CurTok != tok_in)
1187     return Error("expected 'in' after for");
1188   getNextToken();  // eat 'in'.
1189
1190   ExprAST *Body = ParseExpression();
1191   if (Body == 0) return 0;
1192
1193   return new ForExprAST(IdName, Start, End, Step, Body);
1194 }
1195
1196 /// primary
1197 ///   ::= identifierexpr
1198 ///   ::= numberexpr
1199 ///   ::= parenexpr
1200 ///   ::= ifexpr
1201 ///   ::= forexpr
1202 static ExprAST *ParsePrimary() {
1203   switch (CurTok) {
1204   default: return Error("unknown token when expecting an expression");
1205   case tok_identifier: return ParseIdentifierExpr();
1206   case tok_number:     return ParseNumberExpr();
1207   case '(':            return ParseParenExpr();
1208   case tok_if:         return ParseIfExpr();
1209   case tok_for:        return ParseForExpr();
1210   }
1211 }
1212
1213 /// unary
1214 ///   ::= primary
1215 ///   ::= '!' unary
1216 static ExprAST *ParseUnary() {
1217   // If the current token is not an operator, it must be a primary expr.
1218   if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1219     return ParsePrimary();
1220
1221   // If this is a unary operator, read it.
1222   int Opc = CurTok;
1223   getNextToken();
1224   if (ExprAST *Operand = ParseUnary())
1225     return new UnaryExprAST(Opc, Operand);
1226   return 0;
1227 }
1228
1229 /// binoprhs
1230 ///   ::= ('+' unary)*
1231 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1232   // If this is a binop, find its precedence.
1233   while (1) {
1234     int TokPrec = GetTokPrecedence();
1235
1236     // If this is a binop that binds at least as tightly as the current binop,
1237     // consume it, otherwise we are done.
1238     if (TokPrec &lt; ExprPrec)
1239       return LHS;
1240
1241     // Okay, we know this is a binop.
1242     int BinOp = CurTok;
1243     getNextToken();  // eat binop
1244
1245     // Parse the unary expression after the binary operator.
1246     ExprAST *RHS = ParseUnary();
1247     if (!RHS) return 0;
1248
1249     // If BinOp binds less tightly with RHS than the operator after RHS, let
1250     // the pending operator take RHS as its LHS.
1251     int NextPrec = GetTokPrecedence();
1252     if (TokPrec &lt; NextPrec) {
1253       RHS = ParseBinOpRHS(TokPrec+1, RHS);
1254       if (RHS == 0) return 0;
1255     }
1256
1257     // Merge LHS/RHS.
1258     LHS = new BinaryExprAST(BinOp, LHS, RHS);
1259   }
1260 }
1261
1262 /// expression
1263 ///   ::= unary binoprhs
1264 ///
1265 static ExprAST *ParseExpression() {
1266   ExprAST *LHS = ParseUnary();
1267   if (!LHS) return 0;
1268
1269   return ParseBinOpRHS(0, LHS);
1270 }
1271
1272 /// prototype
1273 ///   ::= id '(' id* ')'
1274 ///   ::= binary LETTER number? (id, id)
1275 ///   ::= unary LETTER (id)
1276 static PrototypeAST *ParsePrototype() {
1277   std::string FnName;
1278
1279   unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
1280   unsigned BinaryPrecedence = 30;
1281
1282   switch (CurTok) {
1283   default:
1284     return ErrorP("Expected function name in prototype");
1285   case tok_identifier:
1286     FnName = IdentifierStr;
1287     Kind = 0;
1288     getNextToken();
1289     break;
1290   case tok_unary:
1291     getNextToken();
1292     if (!isascii(CurTok))
1293       return ErrorP("Expected unary operator");
1294     FnName = "unary";
1295     FnName += (char)CurTok;
1296     Kind = 1;
1297     getNextToken();
1298     break;
1299   case tok_binary:
1300     getNextToken();
1301     if (!isascii(CurTok))
1302       return ErrorP("Expected binary operator");
1303     FnName = "binary";
1304     FnName += (char)CurTok;
1305     Kind = 2;
1306     getNextToken();
1307
1308     // Read the precedence if present.
1309     if (CurTok == tok_number) {
1310       if (NumVal &lt; 1 || NumVal &gt; 100)
1311         return ErrorP("Invalid precedecnce: must be 1..100");
1312       BinaryPrecedence = (unsigned)NumVal;
1313       getNextToken();
1314     }
1315     break;
1316   }
1317
1318   if (CurTok != '(')
1319     return ErrorP("Expected '(' in prototype");
1320
1321   std::vector&lt;std::string&gt; ArgNames;
1322   while (getNextToken() == tok_identifier)
1323     ArgNames.push_back(IdentifierStr);
1324   if (CurTok != ')')
1325     return ErrorP("Expected ')' in prototype");
1326
1327   // success.
1328   getNextToken();  // eat ')'.
1329
1330   // Verify right number of names for operator.
1331   if (Kind &amp;&amp; ArgNames.size() != Kind)
1332     return ErrorP("Invalid number of operands for operator");
1333
1334   return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1335 }
1336
1337 /// definition ::= 'def' prototype expression
1338 static FunctionAST *ParseDefinition() {
1339   getNextToken();  // eat def.
1340   PrototypeAST *Proto = ParsePrototype();
1341   if (Proto == 0) return 0;
1342
1343   if (ExprAST *E = ParseExpression())
1344     return new FunctionAST(Proto, E);
1345   return 0;
1346 }
1347
1348 /// toplevelexpr ::= expression
1349 static FunctionAST *ParseTopLevelExpr() {
1350   if (ExprAST *E = ParseExpression()) {
1351     // Make an anonymous proto.
1352     PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
1353     return new FunctionAST(Proto, E);
1354   }
1355   return 0;
1356 }
1357
1358 /// external ::= 'extern' prototype
1359 static PrototypeAST *ParseExtern() {
1360   getNextToken();  // eat extern.
1361   return ParsePrototype();
1362 }
1363
1364 //===----------------------------------------------------------------------===//
1365 // Code Generation
1366 //===----------------------------------------------------------------------===//
1367
1368 static Module *TheModule;
1369 static IRBuilder&lt;&gt; Builder(getGlobalContext());
1370 static std::map&lt;std::string, Value*&gt; NamedValues;
1371 static FunctionPassManager *TheFPM;
1372
1373 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1374
1375 Value *NumberExprAST::Codegen() {
1376   return ConstantFP::get(getGlobalContext(), APFloat(Val));
1377 }
1378
1379 Value *VariableExprAST::Codegen() {
1380   // Look this variable up in the function.
1381   Value *V = NamedValues[Name];
1382   return V ? V : ErrorV("Unknown variable name");
1383 }
1384
1385 Value *UnaryExprAST::Codegen() {
1386   Value *OperandV = Operand-&gt;Codegen();
1387   if (OperandV == 0) return 0;
1388
1389   Function *F = TheModule-&gt;getFunction(std::string("unary")+Opcode);
1390   if (F == 0)
1391     return ErrorV("Unknown unary operator");
1392
1393   return Builder.CreateCall(F, OperandV, "unop");
1394 }
1395
1396 Value *BinaryExprAST::Codegen() {
1397   Value *L = LHS-&gt;Codegen();
1398   Value *R = RHS-&gt;Codegen();
1399   if (L == 0 || R == 0) return 0;
1400
1401   switch (Op) {
1402   case '+': return Builder.CreateFAdd(L, R, "addtmp");
1403   case '-': return Builder.CreateFSub(L, R, "subtmp");
1404   case '*': return Builder.CreateFMul(L, R, "multmp");
1405   case '&lt;':
1406     L = Builder.CreateFCmpULT(L, R, "cmptmp");
1407     // Convert bool 0/1 to double 0.0 or 1.0
1408     return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1409                                 "booltmp");
1410   default: break;
1411   }
1412
1413   // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1414   // a call to it.
1415   Function *F = TheModule-&gt;getFunction(std::string("binary")+Op);
1416   assert(F &amp;&amp; "binary operator not found!");
1417
1418   Value *Ops[] = { L, R };
1419   return Builder.CreateCall(F, Ops, Ops+2, "binop");
1420 }
1421
1422 Value *CallExprAST::Codegen() {
1423   // Look up the name in the global module table.
1424   Function *CalleeF = TheModule-&gt;getFunction(Callee);
1425   if (CalleeF == 0)
1426     return ErrorV("Unknown function referenced");
1427
1428   // If argument mismatch error.
1429   if (CalleeF-&gt;arg_size() != Args.size())
1430     return ErrorV("Incorrect # arguments passed");
1431
1432   std::vector&lt;Value*&gt; ArgsV;
1433   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1434     ArgsV.push_back(Args[i]-&gt;Codegen());
1435     if (ArgsV.back() == 0) return 0;
1436   }
1437
1438   return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1439 }
1440
1441 Value *IfExprAST::Codegen() {
1442   Value *CondV = Cond-&gt;Codegen();
1443   if (CondV == 0) return 0;
1444
1445   // Convert condition to a bool by comparing equal to 0.0.
1446   CondV = Builder.CreateFCmpONE(CondV,
1447                               ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1448                                 "ifcond");
1449
1450   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1451
1452   // Create blocks for the then and else cases.  Insert the 'then' block at the
1453   // end of the function.
1454   BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1455   BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1456   BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1457
1458   Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1459
1460   // Emit then value.
1461   Builder.SetInsertPoint(ThenBB);
1462
1463   Value *ThenV = Then-&gt;Codegen();
1464   if (ThenV == 0) return 0;
1465
1466   Builder.CreateBr(MergeBB);
1467   // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1468   ThenBB = Builder.GetInsertBlock();
1469
1470   // Emit else block.
1471   TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
1472   Builder.SetInsertPoint(ElseBB);
1473
1474   Value *ElseV = Else-&gt;Codegen();
1475   if (ElseV == 0) return 0;
1476
1477   Builder.CreateBr(MergeBB);
1478   // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1479   ElseBB = Builder.GetInsertBlock();
1480
1481   // Emit merge block.
1482   TheFunction-&gt;getBasicBlockList().push_back(MergeBB);
1483   Builder.SetInsertPoint(MergeBB);
1484   PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
1485                                   "iftmp");
1486
1487   PN-&gt;addIncoming(ThenV, ThenBB);
1488   PN-&gt;addIncoming(ElseV, ElseBB);
1489   return PN;
1490 }
1491
1492 Value *ForExprAST::Codegen() {
1493   // Output this as:
1494   //   ...
1495   //   start = startexpr
1496   //   goto loop
1497   // loop:
1498   //   variable = phi [start, loopheader], [nextvariable, loopend]
1499   //   ...
1500   //   bodyexpr
1501   //   ...
1502   // loopend:
1503   //   step = stepexpr
1504   //   nextvariable = variable + step
1505   //   endcond = endexpr
1506   //   br endcond, loop, endloop
1507   // outloop:
1508
1509   // Emit the start code first, without 'variable' in scope.
1510   Value *StartVal = Start-&gt;Codegen();
1511   if (StartVal == 0) return 0;
1512
1513   // Make the new basic block for the loop header, inserting after current
1514   // block.
1515   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1516   BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1517   BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1518
1519   // Insert an explicit fall through from the current block to the LoopBB.
1520   Builder.CreateBr(LoopBB);
1521
1522   // Start insertion in LoopBB.
1523   Builder.SetInsertPoint(LoopBB);
1524
1525   // Start the PHI node with an entry for Start.
1526   PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
1527   Variable-&gt;addIncoming(StartVal, PreheaderBB);
1528
1529   // Within the loop, the variable is defined equal to the PHI node.  If it
1530   // shadows an existing variable, we have to restore it, so save it now.
1531   Value *OldVal = NamedValues[VarName];
1532   NamedValues[VarName] = Variable;
1533
1534   // Emit the body of the loop.  This, like any other expr, can change the
1535   // current BB.  Note that we ignore the value computed by the body, but don't
1536   // allow an error.
1537   if (Body-&gt;Codegen() == 0)
1538     return 0;
1539
1540   // Emit the step value.
1541   Value *StepVal;
1542   if (Step) {
1543     StepVal = Step-&gt;Codegen();
1544     if (StepVal == 0) return 0;
1545   } else {
1546     // If not specified, use 1.0.
1547     StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1548   }
1549
1550   Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar");
1551
1552   // Compute the end condition.
1553   Value *EndCond = End-&gt;Codegen();
1554   if (EndCond == 0) return EndCond;
1555
1556   // Convert condition to a bool by comparing equal to 0.0.
1557   EndCond = Builder.CreateFCmpONE(EndCond,
1558                               ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1559                                   "loopcond");
1560
1561   // Create the "after loop" block and insert it.
1562   BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1563   BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1564
1565   // Insert the conditional branch into the end of LoopEndBB.
1566   Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1567
1568   // Any new code will be inserted in AfterBB.
1569   Builder.SetInsertPoint(AfterBB);
1570
1571   // Add a new entry to the PHI node for the backedge.
1572   Variable-&gt;addIncoming(NextVar, LoopEndBB);
1573
1574   // Restore the unshadowed variable.
1575   if (OldVal)
1576     NamedValues[VarName] = OldVal;
1577   else
1578     NamedValues.erase(VarName);
1579
1580
1581   // for expr always returns 0.0.
1582   return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1583 }
1584
1585 Function *PrototypeAST::Codegen() {
1586   // Make the function type:  double(double,double) etc.
1587   std::vector&lt;const Type*&gt; Doubles(Args.size(),
1588                                    Type::getDoubleTy(getGlobalContext()));
1589   FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1590                                        Doubles, false);
1591
1592   Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1593
1594   // If F conflicted, there was already something named 'Name'.  If it has a
1595   // body, don't allow redefinition or reextern.
1596   if (F-&gt;getName() != Name) {
1597     // Delete the one we just made and get the existing one.
1598     F-&gt;eraseFromParent();
1599     F = TheModule-&gt;getFunction(Name);
1600
1601     // If F already has a body, reject this.
1602     if (!F-&gt;empty()) {
1603       ErrorF("redefinition of function");
1604       return 0;
1605     }
1606
1607     // If F took a different number of args, reject.
1608     if (F-&gt;arg_size() != Args.size()) {
1609       ErrorF("redefinition of function with different # args");
1610       return 0;
1611     }
1612   }
1613
1614   // Set names for all arguments.
1615   unsigned Idx = 0;
1616   for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1617        ++AI, ++Idx) {
1618     AI-&gt;setName(Args[Idx]);
1619
1620     // Add arguments to variable symbol table.
1621     NamedValues[Args[Idx]] = AI;
1622   }
1623
1624   return F;
1625 }
1626
1627 Function *FunctionAST::Codegen() {
1628   NamedValues.clear();
1629
1630   Function *TheFunction = Proto-&gt;Codegen();
1631   if (TheFunction == 0)
1632     return 0;
1633
1634   // If this is an operator, install it.
1635   if (Proto-&gt;isBinaryOp())
1636     BinopPrecedence[Proto-&gt;getOperatorName()] = Proto-&gt;getBinaryPrecedence();
1637
1638   // Create a new basic block to start insertion into.
1639   BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1640   Builder.SetInsertPoint(BB);
1641
1642   if (Value *RetVal = Body-&gt;Codegen()) {
1643     // Finish off the function.
1644     Builder.CreateRet(RetVal);
1645
1646     // Validate the generated code, checking for consistency.
1647     verifyFunction(*TheFunction);
1648
1649     // Optimize the function.
1650     TheFPM-&gt;run(*TheFunction);
1651
1652     return TheFunction;
1653   }
1654
1655   // Error reading body, remove function.
1656   TheFunction-&gt;eraseFromParent();
1657
1658   if (Proto-&gt;isBinaryOp())
1659     BinopPrecedence.erase(Proto-&gt;getOperatorName());
1660   return 0;
1661 }
1662
1663 //===----------------------------------------------------------------------===//
1664 // Top-Level parsing and JIT Driver
1665 //===----------------------------------------------------------------------===//
1666
1667 static ExecutionEngine *TheExecutionEngine;
1668
1669 static void HandleDefinition() {
1670   if (FunctionAST *F = ParseDefinition()) {
1671     if (Function *LF = F-&gt;Codegen()) {
1672       fprintf(stderr, "Read function definition:");
1673       LF-&gt;dump();
1674     }
1675   } else {
1676     // Skip token for error recovery.
1677     getNextToken();
1678   }
1679 }
1680
1681 static void HandleExtern() {
1682   if (PrototypeAST *P = ParseExtern()) {
1683     if (Function *F = P-&gt;Codegen()) {
1684       fprintf(stderr, "Read extern: ");
1685       F-&gt;dump();
1686     }
1687   } else {
1688     // Skip token for error recovery.
1689     getNextToken();
1690   }
1691 }
1692
1693 static void HandleTopLevelExpression() {
1694   // Evaluate a top-level expression into an anonymous function.
1695   if (FunctionAST *F = ParseTopLevelExpr()) {
1696     if (Function *LF = F-&gt;Codegen()) {
1697       // JIT the function, returning a function pointer.
1698       void *FPtr = TheExecutionEngine-&gt;getPointerToFunction(LF);
1699
1700       // Cast it to the right type (takes no arguments, returns a double) so we
1701       // can call it as a native function.
1702       double (*FP)() = (double (*)())(intptr_t)FPtr;
1703       fprintf(stderr, "Evaluated to %f\n", FP());
1704     }
1705   } else {
1706     // Skip token for error recovery.
1707     getNextToken();
1708   }
1709 }
1710
1711 /// top ::= definition | external | expression | ';'
1712 static void MainLoop() {
1713   while (1) {
1714     fprintf(stderr, "ready&gt; ");
1715     switch (CurTok) {
1716     case tok_eof:    return;
1717     case ';':        getNextToken(); break;  // ignore top-level semicolons.
1718     case tok_def:    HandleDefinition(); break;
1719     case tok_extern: HandleExtern(); break;
1720     default:         HandleTopLevelExpression(); break;
1721     }
1722   }
1723 }
1724
1725 //===----------------------------------------------------------------------===//
1726 // "Library" functions that can be "extern'd" from user code.
1727 //===----------------------------------------------------------------------===//
1728
1729 /// putchard - putchar that takes a double and returns 0.
1730 extern "C"
1731 double putchard(double X) {
1732   putchar((char)X);
1733   return 0;
1734 }
1735
1736 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1737 extern "C"
1738 double printd(double X) {
1739   printf("%f\n", X);
1740   return 0;
1741 }
1742
1743 //===----------------------------------------------------------------------===//
1744 // Main driver code.
1745 //===----------------------------------------------------------------------===//
1746
1747 int main() {
1748   InitializeNativeTarget();
1749   LLVMContext &amp;Context = getGlobalContext();
1750
1751   // Install standard binary operators.
1752   // 1 is lowest precedence.
1753   BinopPrecedence['&lt;'] = 10;
1754   BinopPrecedence['+'] = 20;
1755   BinopPrecedence['-'] = 20;
1756   BinopPrecedence['*'] = 40;  // highest.
1757
1758   // Prime the first token.
1759   fprintf(stderr, "ready&gt; ");
1760   getNextToken();
1761
1762   // Make the module, which holds all the code.
1763   TheModule = new Module("my cool jit", Context);
1764
1765   // Create the JIT.  This takes ownership of the module.
1766   std::string ErrStr;
1767   TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&amp;ErrStr).create();
1768   if (!TheExecutionEngine) {
1769     fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1770     exit(1);
1771   }
1772
1773   FunctionPassManager OurFPM(TheModule);
1774
1775   // Set up the optimizer pipeline.  Start with registering info about how the
1776   // target lays out data structures.
1777   OurFPM.add(new TargetData(*TheExecutionEngine-&gt;getTargetData()));
1778   // Provide basic AliasAnalysis support for GVN.
1779   OurFPM.add(createBasicAliasAnalysisPass());
1780   // Do simple "peephole" optimizations and bit-twiddling optzns.
1781   OurFPM.add(createInstructionCombiningPass());
1782   // Reassociate expressions.
1783   OurFPM.add(createReassociatePass());
1784   // Eliminate Common SubExpressions.
1785   OurFPM.add(createGVNPass());
1786   // Simplify the control flow graph (deleting unreachable blocks, etc).
1787   OurFPM.add(createCFGSimplificationPass());
1788
1789   OurFPM.doInitialization();
1790
1791   // Set the global so the code gen can use this.
1792   TheFPM = &amp;OurFPM;
1793
1794   // Run the main "interpreter loop" now.
1795   MainLoop();
1796
1797   TheFPM = 0;
1798
1799   // Print out all of the generated code.
1800   TheModule-&gt;dump();
1801
1802   return 0;
1803 }
1804 </pre>
1805 </div>
1806
1807 <a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a>
1808 </div>
1809
1810 <!-- *********************************************************************** -->
1811 <hr>
1812 <address>
1813   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1814   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1815   <a href="http://validator.w3.org/check/referer"><img
1816   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1817
1818   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1819   <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
1820   Last modified: $Date$
1821 </address>
1822 </body>
1823 </html>