docs/tutorial/LangImpl6.rst

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