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