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 <div class="doc_title">Kaleidoscope: Extending the Language: User-defined Operators</div>
  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 <div class="doc_section"><a name="intro">Chapter 6 Introduction</a></div>
  38 <!-- *********************************************************************** -->
  39
  40 <div class="doc_text">
  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 <div class="doc_section"><a name="idea">User-defined Operators: the Idea</a></div>
  64 <!-- *********************************************************************** -->
  65
  66 <div class="doc_text">
  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 <div class="doc_section"><a name="binary">User-defined Binary Operators</a></div>
 129 <!-- *********************************************************************** -->
 130
 131 <div class="doc_text">
 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 <div class="doc_section"><a name="unary">User-defined Unary Operators</a></div>
 346 <!-- *********************************************************************** -->
 347
 348 <div class="doc_text">
 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 <div class="doc_section"><a name="example">Kicking the Tires</a></div>
 495 <!-- *********************************************************************** -->
 496
 497 <div class="doc_text">
 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 &gt;.
 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 <div class="doc_section"><a name="code">Full Code Listing</a></div>
 800 <!-- *********************************************************************** -->
 801
 802 <div class="doc_text">
 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>Here is the code:</p>
 819
 820 <div class="doc_code">
 821 <pre>
 822 #include "llvm/DerivedTypes.h"
 823 #include "llvm/ExecutionEngine/ExecutionEngine.h"
 824 #include "llvm/ExecutionEngine/JIT.h"
 825 #include "llvm/LLVMContext.h"
 826 #include "llvm/Module.h"
 827 #include "llvm/PassManager.h"
 828 #include "llvm/Analysis/Verifier.h"
 829 #include "llvm/Target/TargetData.h"
 830 #include "llvm/Target/TargetSelect.h"
 831 #include "llvm/Transforms/Scalar.h"
 832 #include "llvm/Support/IRBuilder.h"
 833 #include &lt;cstdio&gt;
 834 #include &lt;string&gt;
 835 #include &lt;map&gt;
 836 #include &lt;vector&gt;
 837 using namespace llvm;
 838
 839 //===----------------------------------------------------------------------===//
 840 // Lexer
 841 //===----------------------------------------------------------------------===//
 842
 843 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
 844 // of these for known things.
 845 enum Token {
 846   tok_eof = -1,
 847
 848   // commands
 849   tok_def = -2, tok_extern = -3,
 850
 851   // primary
 852   tok_identifier = -4, tok_number = -5,
 853
 854   // control
 855   tok_if = -6, tok_then = -7, tok_else = -8,
 856   tok_for = -9, tok_in = -10,
 857
 858   // operators
 859   tok_binary = -11, tok_unary = -12
 860 };
 861
 862 static std::string IdentifierStr;  // Filled in if tok_identifier
 863 static double NumVal;              // Filled in if tok_number
 864
 865 /// gettok - Return the next token from standard input.
 866 static int gettok() {
 867   static int LastChar = ' ';
 868
 869   // Skip any whitespace.
 870   while (isspace(LastChar))
 871     LastChar = getchar();
 872
 873   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
 874     IdentifierStr = LastChar;
 875     while (isalnum((LastChar = getchar())))
 876       IdentifierStr += LastChar;
 877
 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;
 888   }
 889
 890   if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
 891     std::string NumStr;
 892     do {
 893       NumStr += LastChar;
 894       LastChar = getchar();
 895     } while (isdigit(LastChar) || LastChar == '.');
 896
 897     NumVal = strtod(NumStr.c_str(), 0);
 898     return tok_number;
 899   }
 900
 901   if (LastChar == '#') {
 902     // Comment until end of line.
 903     do LastChar = getchar();
 904     while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
 905
 906     if (LastChar != EOF)
 907       return gettok();
 908   }
 909
 910   // Check for end of file.  Don't eat the EOF.
 911   if (LastChar == EOF)
 912     return tok_eof;
 913
 914   // Otherwise, just return the character as its ascii value.
 915   int ThisChar = LastChar;
 916   LastChar = getchar();
 917   return ThisChar;
 918 }
 919
 920 //===----------------------------------------------------------------------===//
 921 // Abstract Syntax Tree (aka Parse Tree)
 922 //===----------------------------------------------------------------------===//
 923
 924 /// ExprAST - Base class for all expression nodes.
 925 class ExprAST {
 926 public:
 927   virtual ~ExprAST() {}
 928   virtual Value *Codegen() = 0;
 929 };
 930
 931 /// NumberExprAST - Expression class for numeric literals like "1.0".
 932 class NumberExprAST : public ExprAST {
 933   double Val;
 934 public:
 935   NumberExprAST(double val) : Val(val) {}
 936   virtual Value *Codegen();
 937 };
 938
 939 /// VariableExprAST - Expression class for referencing a variable, like "a".
 940 class VariableExprAST : public ExprAST {
 941   std::string Name;
 942 public:
 943   VariableExprAST(const std::string &amp;name) : Name(name) {}
 944   virtual Value *Codegen();
 945 };
 946
 947 /// UnaryExprAST - Expression class for a unary operator.
 948 class UnaryExprAST : public ExprAST {
 949   char Opcode;
 950   ExprAST *Operand;
 951 public:
 952   UnaryExprAST(char opcode, ExprAST *operand)
 953     : Opcode(opcode), Operand(operand) {}
 954   virtual Value *Codegen();
 955 };
 956
 957 /// BinaryExprAST - Expression class for a binary operator.
 958 class BinaryExprAST : public ExprAST {
 959   char Op;
 960   ExprAST *LHS, *RHS;
 961 public:
 962   BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
 963     : Op(op), LHS(lhs), RHS(rhs) {}
 964   virtual Value *Codegen();
 965 };
 966
 967 /// CallExprAST - Expression class for function calls.
 968 class CallExprAST : public ExprAST {
 969   std::string Callee;
 970   std::vector&lt;ExprAST*&gt; Args;
 971 public:
 972   CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
 973     : Callee(callee), Args(args) {}
 974   virtual Value *Codegen();
 975 };
 976
 977 /// IfExprAST - Expression class for if/then/else.
 978 class IfExprAST : public ExprAST {
 979   ExprAST *Cond, *Then, *Else;
 980 public:
 981   IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
 982   : Cond(cond), Then(then), Else(_else) {}
 983   virtual Value *Codegen();
 984 };
 985
 986 /// ForExprAST - Expression class for for/in.
 987 class ForExprAST : public ExprAST {
 988   std::string VarName;
 989   ExprAST *Start, *End, *Step, *Body;
 990 public:
 991   ForExprAST(const std::string &amp;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();
 995 };
 996
 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 {
1001   std::string Name;
1002   std::vector&lt;std::string&gt; Args;
1003   bool isOperator;
1004   unsigned Precedence;  // Precedence if a binary op.
1005 public:
1006   PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args,
1007                bool isoperator = false, unsigned prec = 0)
1008   : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1009
1010   bool isUnaryOp() const { return isOperator &amp;&amp; Args.size() == 1; }
1011   bool isBinaryOp() const { return isOperator &amp;&amp; Args.size() == 2; }
1012
1013   char getOperatorName() const {
1014     assert(isUnaryOp() || isBinaryOp());
1015     return Name[Name.size()-1];
1016   }
1017
1018   unsigned getBinaryPrecedence() const { return Precedence; }
1019
1020   Function *Codegen();
1021 };
1022
1023 /// FunctionAST - This class represents a function definition itself.
1024 class FunctionAST {
1025   PrototypeAST *Proto;
1026   ExprAST *Body;
1027 public:
1028   FunctionAST(PrototypeAST *proto, ExprAST *body)
1029     : Proto(proto), Body(body) {}
1030
1031   Function *Codegen();
1032 };
1033
1034 //===----------------------------------------------------------------------===//
1035 // Parser
1036 //===----------------------------------------------------------------------===//
1037
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.
1041 static int CurTok;
1042 static int getNextToken() {
1043   return CurTok = gettok();
1044 }
1045
1046 /// BinopPrecedence - This holds the precedence for each binary operator that is
1047 /// defined.
1048 static std::map&lt;char, int&gt; BinopPrecedence;
1049
1050 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1051 static int GetTokPrecedence() {
1052   if (!isascii(CurTok))
1053     return -1;
1054
1055   // Make sure it's a declared binop.
1056   int TokPrec = BinopPrecedence[CurTok];
1057   if (TokPrec &lt;= 0) return -1;
1058   return TokPrec;
1059 }
1060
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; }
1065
1066 static ExprAST *ParseExpression();
1067
1068 /// identifierexpr
1069 ///   ::= identifier
1070 ///   ::= identifier '(' expression* ')'
1071 static ExprAST *ParseIdentifierExpr() {
1072   std::string IdName = IdentifierStr;
1073
1074   getNextToken();  // eat identifier.
1075
1076   if (CurTok != '(') // Simple variable ref.
1077     return new VariableExprAST(IdName);
1078
1079   // Call.
1080   getNextToken();  // eat (
1081   std::vector&lt;ExprAST*&gt; Args;
1082   if (CurTok != ')') {
1083     while (1) {
1084       ExprAST *Arg = ParseExpression();
1085       if (!Arg) return 0;
1086       Args.push_back(Arg);
1087
1088       if (CurTok == ')') break;
1089
1090       if (CurTok != ',')
1091         return Error("Expected ')' or ',' in argument list");
1092       getNextToken();
1093     }
1094   }
1095
1096   // Eat the ')'.
1097   getNextToken();
1098
1099   return new CallExprAST(IdName, Args);
1100 }
1101
1102 /// numberexpr ::= number
1103 static ExprAST *ParseNumberExpr() {
1104   ExprAST *Result = new NumberExprAST(NumVal);
1105   getNextToken(); // consume the number
1106   return Result;
1107 }
1108
1109 /// parenexpr ::= '(' expression ')'
1110 static ExprAST *ParseParenExpr() {
1111   getNextToken();  // eat (.
1112   ExprAST *V = ParseExpression();
1113   if (!V) return 0;
1114
1115   if (CurTok != ')')
1116     return Error("expected ')'");
1117   getNextToken();  // eat ).
1118   return V;
1119 }
1120
1121 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1122 static ExprAST *ParseIfExpr() {
1123   getNextToken();  // eat the if.
1124
1125   // condition.
1126   ExprAST *Cond = ParseExpression();
1127   if (!Cond) return 0;
1128
1129   if (CurTok != tok_then)
1130     return Error("expected then");
1131   getNextToken();  // eat the then
1132
1133   ExprAST *Then = ParseExpression();
1134   if (Then == 0) return 0;
1135
1136   if (CurTok != tok_else)
1137     return Error("expected else");
1138
1139   getNextToken();
1140
1141   ExprAST *Else = ParseExpression();
1142   if (!Else) return 0;
1143
1144   return new IfExprAST(Cond, Then, Else);
1145 }
1146
1147 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1148 static ExprAST *ParseForExpr() {
1149   getNextToken();  // eat the for.
1150
1151   if (CurTok != tok_identifier)
1152     return Error("expected identifier after for");
1153
1154   std::string IdName = IdentifierStr;
1155   getNextToken();  // eat identifier.
1156
1157   if (CurTok != '=')
1158     return Error("expected '=' after for");
1159   getNextToken();  // eat '='.
1160
1161
1162   ExprAST *Start = ParseExpression();
1163   if (Start == 0) return 0;
1164   if (CurTok != ',')
1165     return Error("expected ',' after for start value");
1166   getNextToken();
1167
1168   ExprAST *End = ParseExpression();
1169   if (End == 0) return 0;
1170
1171   // The step value is optional.
1172   ExprAST *Step = 0;
1173   if (CurTok == ',') {
1174     getNextToken();
1175     Step = ParseExpression();
1176     if (Step == 0) return 0;
1177   }
1178
1179   if (CurTok != tok_in)
1180     return Error("expected 'in' after for");
1181   getNextToken();  // eat 'in'.
1182
1183   ExprAST *Body = ParseExpression();
1184   if (Body == 0) return 0;
1185
1186   return new ForExprAST(IdName, Start, End, Step, Body);
1187 }
1188
1189 /// primary
1190 ///   ::= identifierexpr
1191 ///   ::= numberexpr
1192 ///   ::= parenexpr
1193 ///   ::= ifexpr
1194 ///   ::= forexpr
1195 static ExprAST *ParsePrimary() {
1196   switch (CurTok) {
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();
1203   }
1204 }
1205
1206 /// unary
1207 ///   ::= primary
1208 ///   ::= '!' unary
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();
1213
1214   // If this is a unary operator, read it.
1215   int Opc = CurTok;
1216   getNextToken();
1217   if (ExprAST *Operand = ParseUnary())
1218     return new UnaryExprAST(Opc, Operand);
1219   return 0;
1220 }
1221
1222 /// binoprhs
1223 ///   ::= ('+' unary)*
1224 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1225   // If this is a binop, find its precedence.
1226   while (1) {
1227     int TokPrec = GetTokPrecedence();
1228
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 &lt; ExprPrec)
1232       return LHS;
1233
1234     // Okay, we know this is a binop.
1235     int BinOp = CurTok;
1236     getNextToken();  // eat binop
1237
1238     // Parse the unary expression after the binary operator.
1239     ExprAST *RHS = ParseUnary();
1240     if (!RHS) return 0;
1241
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 &lt; NextPrec) {
1246       RHS = ParseBinOpRHS(TokPrec+1, RHS);
1247       if (RHS == 0) return 0;
1248     }
1249
1250     // Merge LHS/RHS.
1251     LHS = new BinaryExprAST(BinOp, LHS, RHS);
1252   }
1253 }
1254
1255 /// expression
1256 ///   ::= unary binoprhs
1257 ///
1258 static ExprAST *ParseExpression() {
1259   ExprAST *LHS = ParseUnary();
1260   if (!LHS) return 0;
1261
1262   return ParseBinOpRHS(0, LHS);
1263 }
1264
1265 /// prototype
1266 ///   ::= id '(' id* ')'
1267 ///   ::= binary LETTER number? (id, id)
1268 ///   ::= unary LETTER (id)
1269 static PrototypeAST *ParsePrototype() {
1270   std::string FnName;
1271
1272   unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
1273   unsigned BinaryPrecedence = 30;
1274
1275   switch (CurTok) {
1276   default:
1277     return ErrorP("Expected function name in prototype");
1278   case tok_identifier:
1279     FnName = IdentifierStr;
1280     Kind = 0;
1281     getNextToken();
1282     break;
1283   case tok_unary:
1284     getNextToken();
1285     if (!isascii(CurTok))
1286       return ErrorP("Expected unary operator");
1287     FnName = "unary";
1288     FnName += (char)CurTok;
1289     Kind = 1;
1290     getNextToken();
1291     break;
1292   case tok_binary:
1293     getNextToken();
1294     if (!isascii(CurTok))
1295       return ErrorP("Expected binary operator");
1296     FnName = "binary";
1297     FnName += (char)CurTok;
1298     Kind = 2;
1299     getNextToken();
1300
1301     // Read the precedence if present.
1302     if (CurTok == tok_number) {
1303       if (NumVal &lt; 1 || NumVal &gt; 100)
1304         return ErrorP("Invalid precedecnce: must be 1..100");
1305       BinaryPrecedence = (unsigned)NumVal;
1306       getNextToken();
1307     }
1308     break;
1309   }
1310
1311   if (CurTok != '(')
1312     return ErrorP("Expected '(' in prototype");
1313
1314   std::vector&lt;std::string&gt; ArgNames;
1315   while (getNextToken() == tok_identifier)
1316     ArgNames.push_back(IdentifierStr);
1317   if (CurTok != ')')
1318     return ErrorP("Expected ')' in prototype");
1319
1320   // success.
1321   getNextToken();  // eat ')'.
1322
1323   // Verify right number of names for operator.
1324   if (Kind &amp;&amp; ArgNames.size() != Kind)
1325     return ErrorP("Invalid number of operands for operator");
1326
1327   return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1328 }
1329
1330 /// definition ::= 'def' prototype expression
1331 static FunctionAST *ParseDefinition() {
1332   getNextToken();  // eat def.
1333   PrototypeAST *Proto = ParsePrototype();
1334   if (Proto == 0) return 0;
1335
1336   if (ExprAST *E = ParseExpression())
1337     return new FunctionAST(Proto, E);
1338   return 0;
1339 }
1340
1341 /// toplevelexpr ::= expression
1342 static FunctionAST *ParseTopLevelExpr() {
1343   if (ExprAST *E = ParseExpression()) {
1344     // Make an anonymous proto.
1345     PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
1346     return new FunctionAST(Proto, E);
1347   }
1348   return 0;
1349 }
1350
1351 /// external ::= 'extern' prototype
1352 static PrototypeAST *ParseExtern() {
1353   getNextToken();  // eat extern.
1354   return ParsePrototype();
1355 }
1356
1357 //===----------------------------------------------------------------------===//
1358 // Code Generation
1359 //===----------------------------------------------------------------------===//
1360
1361 static Module *TheModule;
1362 static IRBuilder&lt;&gt; Builder(getGlobalContext());
1363 static std::map&lt;std::string, Value*&gt; NamedValues;
1364 static FunctionPassManager *TheFPM;
1365
1366 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1367
1368 Value *NumberExprAST::Codegen() {
1369   return ConstantFP::get(getGlobalContext(), APFloat(Val));
1370 }
1371
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");
1376 }
1377
1378 Value *UnaryExprAST::Codegen() {
1379   Value *OperandV = Operand-&gt;Codegen();
1380   if (OperandV == 0) return 0;
1381
1382   Function *F = TheModule-&gt;getFunction(std::string("unary")+Opcode);
1383   if (F == 0)
1384     return ErrorV("Unknown unary operator");
1385
1386   return Builder.CreateCall(F, OperandV, "unop");
1387 }
1388
1389 Value *BinaryExprAST::Codegen() {
1390   Value *L = LHS-&gt;Codegen();
1391   Value *R = RHS-&gt;Codegen();
1392   if (L == 0 || R == 0) return 0;
1393
1394   switch (Op) {
1395   case '+': return Builder.CreateFAdd(L, R, "addtmp");
1396   case '-': return Builder.CreateFSub(L, R, "subtmp");
1397   case '*': return Builder.CreateFMul(L, R, "multmp");
1398   case '&lt;':
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()),
1402                                 "booltmp");
1403   default: break;
1404   }
1405
1406   // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1407   // a call to it.
1408   Function *F = TheModule-&gt;getFunction(std::string("binary")+Op);
1409   assert(F &amp;&amp; "binary operator not found!");
1410
1411   Value *Ops[] = { L, R };
1412   return Builder.CreateCall(F, Ops, Ops+2, "binop");
1413 }
1414
1415 Value *CallExprAST::Codegen() {
1416   // Look up the name in the global module table.
1417   Function *CalleeF = TheModule-&gt;getFunction(Callee);
1418   if (CalleeF == 0)
1419     return ErrorV("Unknown function referenced");
1420
1421   // If argument mismatch error.
1422   if (CalleeF-&gt;arg_size() != Args.size())
1423     return ErrorV("Incorrect # arguments passed");
1424
1425   std::vector&lt;Value*&gt; ArgsV;
1426   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1427     ArgsV.push_back(Args[i]-&gt;Codegen());
1428     if (ArgsV.back() == 0) return 0;
1429   }
1430
1431   return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1432 }
1433
1434 Value *IfExprAST::Codegen() {
1435   Value *CondV = Cond-&gt;Codegen();
1436   if (CondV == 0) return 0;
1437
1438   // Convert condition to a bool by comparing equal to 0.0.
1439   CondV = Builder.CreateFCmpONE(CondV,
1440                               ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1441                                 "ifcond");
1442
1443   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1444
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");
1450
1451   Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1452
1453   // Emit then value.
1454   Builder.SetInsertPoint(ThenBB);
1455
1456   Value *ThenV = Then-&gt;Codegen();
1457   if (ThenV == 0) return 0;
1458
1459   Builder.CreateBr(MergeBB);
1460   // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1461   ThenBB = Builder.GetInsertBlock();
1462
1463   // Emit else block.
1464   TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
1465   Builder.SetInsertPoint(ElseBB);
1466
1467   Value *ElseV = Else-&gt;Codegen();
1468   if (ElseV == 0) return 0;
1469
1470   Builder.CreateBr(MergeBB);
1471   // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1472   ElseBB = Builder.GetInsertBlock();
1473
1474   // Emit merge block.
1475   TheFunction-&gt;getBasicBlockList().push_back(MergeBB);
1476   Builder.SetInsertPoint(MergeBB);
1477   PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
1478                                   "iftmp");
1479
1480   PN-&gt;addIncoming(ThenV, ThenBB);
1481   PN-&gt;addIncoming(ElseV, ElseBB);
1482   return PN;
1483 }
1484
1485 Value *ForExprAST::Codegen() {
1486   // Output this as:
1487   //   ...
1488   //   start = startexpr
1489   //   goto loop
1490   // loop:
1491   //   variable = phi [start, loopheader], [nextvariable, loopend]
1492   //   ...
1493   //   bodyexpr
1494   //   ...
1495   // loopend:
1496   //   step = stepexpr
1497   //   nextvariable = variable + step
1498   //   endcond = endexpr
1499   //   br endcond, loop, endloop
1500   // outloop:
1501
1502   // Emit the start code first, without 'variable' in scope.
1503   Value *StartVal = Start-&gt;Codegen();
1504   if (StartVal == 0) return 0;
1505
1506   // Make the new basic block for the loop header, inserting after current
1507   // block.
1508   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1509   BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1510   BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1511
1512   // Insert an explicit fall through from the current block to the LoopBB.
1513   Builder.CreateBr(LoopBB);
1514
1515   // Start insertion in LoopBB.
1516   Builder.SetInsertPoint(LoopBB);
1517
1518   // Start the PHI node with an entry for Start.
1519   PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
1520   Variable-&gt;addIncoming(StartVal, PreheaderBB);
1521
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;
1526
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
1529   // allow an error.
1530   if (Body-&gt;Codegen() == 0)
1531     return 0;
1532
1533   // Emit the step value.
1534   Value *StepVal;
1535   if (Step) {
1536     StepVal = Step-&gt;Codegen();
1537     if (StepVal == 0) return 0;
1538   } else {
1539     // If not specified, use 1.0.
1540     StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1541   }
1542
1543   Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
1544
1545   // Compute the end condition.
1546   Value *EndCond = End-&gt;Codegen();
1547   if (EndCond == 0) return EndCond;
1548
1549   // Convert condition to a bool by comparing equal to 0.0.
1550   EndCond = Builder.CreateFCmpONE(EndCond,
1551                               ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1552                                   "loopcond");
1553
1554   // Create the "after loop" block and insert it.
1555   BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1556   BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1557
1558   // Insert the conditional branch into the end of LoopEndBB.
1559   Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1560
1561   // Any new code will be inserted in AfterBB.
1562   Builder.SetInsertPoint(AfterBB);
1563
1564   // Add a new entry to the PHI node for the backedge.
1565   Variable-&gt;addIncoming(NextVar, LoopEndBB);
1566
1567   // Restore the unshadowed variable.
1568   if (OldVal)
1569     NamedValues[VarName] = OldVal;
1570   else
1571     NamedValues.erase(VarName);
1572
1573
1574   // for expr always returns 0.0.
1575   return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1576 }
1577
1578 Function *PrototypeAST::Codegen() {
1579   // Make the function type:  double(double,double) etc.
1580   std::vector&lt;const Type*&gt; Doubles(Args.size(),
1581                                    Type::getDoubleTy(getGlobalContext()));
1582   FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1583                                        Doubles, false);
1584
1585   Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1586
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-&gt;getName() != Name) {
1590     // Delete the one we just made and get the existing one.
1591     F-&gt;eraseFromParent();
1592     F = TheModule-&gt;getFunction(Name);
1593
1594     // If F already has a body, reject this.
1595     if (!F-&gt;empty()) {
1596       ErrorF("redefinition of function");
1597       return 0;
1598     }
1599
1600     // If F took a different number of args, reject.
1601     if (F-&gt;arg_size() != Args.size()) {
1602       ErrorF("redefinition of function with different # args");
1603       return 0;
1604     }
1605   }
1606
1607   // Set names for all arguments.
1608   unsigned Idx = 0;
1609   for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1610        ++AI, ++Idx) {
1611     AI-&gt;setName(Args[Idx]);
1612
1613     // Add arguments to variable symbol table.
1614     NamedValues[Args[Idx]] = AI;
1615   }
1616
1617   return F;
1618 }
1619
1620 Function *FunctionAST::Codegen() {
1621   NamedValues.clear();
1622
1623   Function *TheFunction = Proto-&gt;Codegen();
1624   if (TheFunction == 0)
1625     return 0;
1626
1627   // If this is an operator, install it.
1628   if (Proto-&gt;isBinaryOp())
1629     BinopPrecedence[Proto-&gt;getOperatorName()] = Proto-&gt;getBinaryPrecedence();
1630
1631   // Create a new basic block to start insertion into.
1632   BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1633   Builder.SetInsertPoint(BB);
1634
1635   if (Value *RetVal = Body-&gt;Codegen()) {
1636     // Finish off the function.
1637     Builder.CreateRet(RetVal);
1638
1639     // Validate the generated code, checking for consistency.
1640     verifyFunction(*TheFunction);
1641
1642     // Optimize the function.
1643     TheFPM-&gt;run(*TheFunction);
1644
1645     return TheFunction;
1646   }
1647
1648   // Error reading body, remove function.
1649   TheFunction-&gt;eraseFromParent();
1650
1651   if (Proto-&gt;isBinaryOp())
1652     BinopPrecedence.erase(Proto-&gt;getOperatorName());
1653   return 0;
1654 }
1655
1656 //===----------------------------------------------------------------------===//
1657 // Top-Level parsing and JIT Driver
1658 //===----------------------------------------------------------------------===//
1659
1660 static ExecutionEngine *TheExecutionEngine;
1661
1662 static void HandleDefinition() {
1663   if (FunctionAST *F = ParseDefinition()) {
1664     if (Function *LF = F-&gt;Codegen()) {
1665       fprintf(stderr, "Read function definition:");
1666       LF-&gt;dump();
1667     }
1668   } else {
1669     // Skip token for error recovery.
1670     getNextToken();
1671   }
1672 }
1673
1674 static void HandleExtern() {
1675   if (PrototypeAST *P = ParseExtern()) {
1676     if (Function *F = P-&gt;Codegen()) {
1677       fprintf(stderr, "Read extern: ");
1678       F-&gt;dump();
1679     }
1680   } else {
1681     // Skip token for error recovery.
1682     getNextToken();
1683   }
1684 }
1685
1686 static void HandleTopLevelExpression() {
1687   // Evaluate a top-level expression into an anonymous function.
1688   if (FunctionAST *F = ParseTopLevelExpr()) {
1689     if (Function *LF = F-&gt;Codegen()) {
1690       // JIT the function, returning a function pointer.
1691       void *FPtr = TheExecutionEngine-&gt;getPointerToFunction(LF);
1692
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());
1697     }
1698   } else {
1699     // Skip token for error recovery.
1700     getNextToken();
1701   }
1702 }
1703
1704 /// top ::= definition | external | expression | ';'
1705 static void MainLoop() {
1706   while (1) {
1707     fprintf(stderr, "ready&gt; ");
1708     switch (CurTok) {
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;
1714     }
1715   }
1716 }
1717
1718 //===----------------------------------------------------------------------===//
1719 // "Library" functions that can be "extern'd" from user code.
1720 //===----------------------------------------------------------------------===//
1721
1722 /// putchard - putchar that takes a double and returns 0.
1723 extern "C"
1724 double putchard(double X) {
1725   putchar((char)X);
1726   return 0;
1727 }
1728
1729 /// printd - printf that takes a double prints it as "%f\n", returning 0.
1730 extern "C"
1731 double printd(double X) {
1732   printf("%f\n", X);
1733   return 0;
1734 }
1735
1736 //===----------------------------------------------------------------------===//
1737 // Main driver code.
1738 //===----------------------------------------------------------------------===//
1739
1740 int main() {
1741   InitializeNativeTarget();
1742   LLVMContext &amp;Context = getGlobalContext();
1743
1744   // Install standard binary operators.
1745   // 1 is lowest precedence.
1746   BinopPrecedence['&lt;'] = 10;
1747   BinopPrecedence['+'] = 20;
1748   BinopPrecedence['-'] = 20;
1749   BinopPrecedence['*'] = 40;  // highest.
1750
1751   // Prime the first token.
1752   fprintf(stderr, "ready&gt; ");
1753   getNextToken();
1754
1755   // Make the module, which holds all the code.
1756   TheModule = new Module("my cool jit", Context);
1757
1758   // Create the JIT.  This takes ownership of the module.
1759   std::string ErrStr;
1760   TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
1761   if (!TheExecutionEngine) {
1762     fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
1763     exit(1);
1764   }
1765
1766   FunctionPassManager OurFPM(TheModule);
1767
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-&gt;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());
1779
1780   OurFPM.doInitialization();
1781
1782   // Set the global so the code gen can use this.
1783   TheFPM = &amp;OurFPM;
1784
1785   // Run the main "interpreter loop" now.
1786   MainLoop();
1787
1788   TheFPM = 0;
1789
1790   // Print out all of the generated code.
1791   TheModule-&gt;dump();
1792
1793   return 0;
1794 }
1795 </pre>
1796 </div>
1797
1798 <a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a>
1799 </div>
1800
1801 <!-- *********************************************************************** -->
1802 <hr>
1803 <address>
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>
1808
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$
1812 </address>
1813 </body>
1814 </html>