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