docs/tutorial/LangImpl5.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: Control Flow</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: Control Flow</div>
  15
  16 <ul>
  17 <li><a href="index.html">Up to Tutorial Index</a></li>
  18 <li>Chapter 5
  19   <ol>
  20     <li><a href="#intro">Chapter 5 Introduction</a></li>
  21     <li><a href="#ifthen">If/Then/Else</a>
  22     <ol>
  23       <li><a href="#iflexer">Lexer Extensions</a></li>
  24       <li><a href="#ifast">AST Extensions</a></li>
  25       <li><a href="#ifparser">Parser Extensions</a></li>
  26       <li><a href="#ifir">LLVM IR</a></li>
  27       <li><a href="#ifcodegen">Code Generation</a></li>
  28     </ol>
  29     </li>
  30     <li><a href="#for">'for' Loop Expression</a>
  31     <ol>
  32       <li><a href="#forlexer">Lexer Extensions</a></li>
  33       <li><a href="#forast">AST Extensions</a></li>
  34       <li><a href="#forparser">Parser Extensions</a></li>
  35       <li><a href="#forir">LLVM IR</a></li>
  36       <li><a href="#forcodegen">Code Generation</a></li>
  37     </ol>
  38     </li>
  39     <li><a href="#code">Full Code Listing</a></li>
  40   </ol>
  41 </li>
  42 <li><a href="LangImpl6.html">Chapter 6</a>: Extending the Language:
  43 User-defined Operators</li>
  44 </ul>
  45
  46 <div class="doc_author">
  47   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
  48 </div>
  49
  50 <!-- *********************************************************************** -->
  51 <div class="doc_section"><a name="intro">Chapter 5 Introduction</a></div>
  52 <!-- *********************************************************************** -->
  53
  54 <div class="doc_text">
  55
  56 <p>Welcome to Chapter 5 of the "<a href="index.html">Implementing a language
  57 with LLVM</a>" tutorial.  Parts 1-4 described the implementation of the simple
  58 Kaleidoscope language and included support for generating LLVM IR, followed by
  59 optimizations and a JIT compiler.  Unfortunately, as presented, Kaleidoscope is
  60 mostly useless: it has no control flow other than call and return.  This means
  61 that you can't have conditional branches in the code, significantly limiting its
  62 power.  In this episode of "build that compiler", we'll extend Kaleidoscope to
  63 have an if/then/else expression plus a simple 'for' loop.</p>
  64
  65 </div>
  66
  67 <!-- *********************************************************************** -->
  68 <div class="doc_section"><a name="ifthen">If/Then/Else</a></div>
  69 <!-- *********************************************************************** -->
  70
  71 <div class="doc_text">
  72
  73 <p>
  74 Extending Kaleidoscope to support if/then/else is quite straightforward.  It
  75 basically requires adding lexer support for this "new" concept to the lexer,
  76 parser, AST, and LLVM code emitter.  This example is nice, because it shows how
  77 easy it is to "grow" a language over time, incrementally extending it as new
  78 ideas are discovered.</p>
  79
  80 <p>Before we get going on "how" we add this extension, lets talk about "what" we
  81 want.  The basic idea is that we want to be able to write this sort of thing:
  82 </p>
  83
  84 <div class="doc_code">
  85 <pre>
  86 def fib(x)
  87   if x &lt; 3 then
  88     1
  89   else
  90     fib(x-1)+fib(x-2);
  91 </pre>
  92 </div>
  93
  94 <p>In Kaleidoscope, every construct is an expression: there are no statements.
  95 As such, the if/then/else expression needs to return a value like any other.
  96 Since we're using a mostly functional form, we'll have it evaluate its
  97 conditional, then return the 'then' or 'else' value based on how the condition
  98 was resolved.  This is very similar to the C "?:" expression.</p>
  99
 100 <p>The semantics of the if/then/else expression is that it evaluates the
 101 condition to a boolean equality value: 0.0 is considered to be false and
 102 everything else is considered to be true.
 103 If the condition is true, the first subexpression is evaluated and returned, if
 104 the condition is false, the second subexpression is evaluated and returned.
 105 Since Kaleidoscope allows side-effects, this behavior is important to nail down.
 106 </p>
 107
 108 <p>Now that we know what we "want", lets break this down into its constituent
 109 pieces.</p>
 110
 111 </div>
 112
 113 <!-- ======================================================================= -->
 114 <div class="doc_subsubsection"><a name="iflexer">Lexer Extensions for
 115 If/Then/Else</a></div>
 116 <!-- ======================================================================= -->
 117
 118
 119 <div class="doc_text">
 120
 121 <p>The lexer extensions are straightforward.  First we add new enum values
 122 for the relevant tokens:</p>
 123
 124 <div class="doc_code">
 125 <pre>
 126   // control
 127   tok_if = -6, tok_then = -7, tok_else = -8,
 128 </pre>
 129 </div>
 130
 131 <p>Once we have that, we recognize the new keywords in the lexer. This is pretty simple
 132 stuff:</p>
 133
 134 <div class="doc_code">
 135 <pre>
 136     ...
 137     if (IdentifierStr == "def") return tok_def;
 138     if (IdentifierStr == "extern") return tok_extern;
 139     <b>if (IdentifierStr == "if") return tok_if;
 140     if (IdentifierStr == "then") return tok_then;
 141     if (IdentifierStr == "else") return tok_else;</b>
 142     return tok_identifier;
 143 </pre>
 144 </div>
 145
 146 </div>
 147
 148 <!-- ======================================================================= -->
 149 <div class="doc_subsubsection"><a name="ifast">AST Extensions for
 150  If/Then/Else</a></div>
 151 <!-- ======================================================================= -->
 152
 153 <div class="doc_text">
 154
 155 <p>To represent the new expression we add a new AST node for it:</p>
 156
 157 <div class="doc_code">
 158 <pre>
 159 /// IfExprAST - Expression class for if/then/else.
 160 class IfExprAST : public ExprAST {
 161   ExprAST *Cond, *Then, *Else;
 162 public:
 163   IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
 164     : Cond(cond), Then(then), Else(_else) {}
 165   virtual Value *Codegen();
 166 };
 167 </pre>
 168 </div>
 169
 170 <p>The AST node just has pointers to the various subexpressions.</p>
 171
 172 </div>
 173
 174 <!-- ======================================================================= -->
 175 <div class="doc_subsubsection"><a name="ifparser">Parser Extensions for
 176 If/Then/Else</a></div>
 177 <!-- ======================================================================= -->
 178
 179 <div class="doc_text">
 180
 181 <p>Now that we have the relevant tokens coming from the lexer and we have the
 182 AST node to build, our parsing logic is relatively straightforward.  First we
 183 define a new parsing function:</p>
 184
 185 <div class="doc_code">
 186 <pre>
 187 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
 188 static ExprAST *ParseIfExpr() {
 189   getNextToken();  // eat the if.
 190
 191   // condition.
 192   ExprAST *Cond = ParseExpression();
 193   if (!Cond) return 0;
 194
 195   if (CurTok != tok_then)
 196     return Error("expected then");
 197   getNextToken();  // eat the then
 198
 199   ExprAST *Then = ParseExpression();
 200   if (Then == 0) return 0;
 201
 202   if (CurTok != tok_else)
 203     return Error("expected else");
 204
 205   getNextToken();
 206
 207   ExprAST *Else = ParseExpression();
 208   if (!Else) return 0;
 209
 210   return new IfExprAST(Cond, Then, Else);
 211 }
 212 </pre>
 213 </div>
 214
 215 <p>Next we hook it up as a primary expression:</p>
 216
 217 <div class="doc_code">
 218 <pre>
 219 static ExprAST *ParsePrimary() {
 220   switch (CurTok) {
 221   default: return Error("unknown token when expecting an expression");
 222   case tok_identifier: return ParseIdentifierExpr();
 223   case tok_number:     return ParseNumberExpr();
 224   case '(':            return ParseParenExpr();
 225   <b>case tok_if:         return ParseIfExpr();</b>
 226   }
 227 }
 228 </pre>
 229 </div>
 230
 231 </div>
 232
 233 <!-- ======================================================================= -->
 234 <div class="doc_subsubsection"><a name="ifir">LLVM IR for If/Then/Else</a></div>
 235 <!-- ======================================================================= -->
 236
 237 <div class="doc_text">
 238
 239 <p>Now that we have it parsing and building the AST, the final piece is adding
 240 LLVM code generation support.  This is the most interesting part of the
 241 if/then/else example, because this is where it starts to introduce new concepts.
 242 All of the code above has been thoroughly described in previous chapters.
 243 </p>
 244
 245 <p>To motivate the code we want to produce, lets take a look at a simple
 246 example.  Consider:</p>
 247
 248 <div class="doc_code">
 249 <pre>
 250 extern foo();
 251 extern bar();
 252 def baz(x) if x then foo() else bar();
 253 </pre>
 254 </div>
 255
 256 <p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
 257 looks like this:</p>
 258
 259 <div class="doc_code">
 260 <pre>
 261 declare double @foo()
 262
 263 declare double @bar()
 264
 265 define double @baz(double %x) {
 266 entry:
 267         %ifcond = fcmp one double %x, 0.000000e+00
 268         br i1 %ifcond, label %then, label %else
 269
 270 then:           ; preds = %entry
 271         %calltmp = call double @foo()
 272         br label %ifcont
 273
 274 else:           ; preds = %entry
 275         %calltmp1 = call double @bar()
 276         br label %ifcont
 277
 278 ifcont:         ; preds = %else, %then
 279         %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
 280         ret double %iftmp
 281 }
 282 </pre>
 283 </div>
 284
 285 <p>To visualize the control flow graph, you can use a nifty feature of the LLVM
 286 '<a href="http://llvm.org/cmds/opt.html">opt</a>' tool.  If you put this LLVM IR
 287 into "t.ll" and run "<tt>llvm-as &lt; t.ll | opt -analyze -view-cfg</tt>", <a
 288 href="../ProgrammersManual.html#ViewGraph">a window will pop up</a> and you'll
 289 see this graph:</p>
 290
 291 <div style="text-align: center"><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
 292 height="315"></div>
 293
 294 <p>Another way to get this is to call "<tt>F-&gt;viewCFG()</tt>" or
 295 "<tt>F-&gt;viewCFGOnly()</tt>" (where F is a "<tt>Function*</tt>") either by
 296 inserting actual calls into the code and recompiling or by calling these in the
 297 debugger.  LLVM has many nice features for visualizing various graphs.</p>
 298
 299 <p>Getting back to the generated code, it is fairly simple: the entry block
 300 evaluates the conditional expression ("x" in our case here) and compares the
 301 result to 0.0 with the "<tt><a href="../LangRef.html#i_fcmp">fcmp</a> one</tt>"
 302 instruction ('one' is "Ordered and Not Equal").  Based on the result of this
 303 expression, the code jumps to either the "then" or "else" blocks, which contain
 304 the expressions for the true/false cases.</p>
 305
 306 <p>Once the then/else blocks are finished executing, they both branch back to the
 307 'ifcont' block to execute the code that happens after the if/then/else.  In this
 308 case the only thing left to do is to return to the caller of the function.  The
 309 question then becomes: how does the code know which expression to return?</p>
 310
 311 <p>The answer to this question involves an important SSA operation: the
 312 <a href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Phi
 313 operation</a>.  If you're not familiar with SSA, <a
 314 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">the wikipedia
 315 article</a> is a good introduction and there are various other introductions to
 316 it available on your favorite search engine.  The short version is that
 317 "execution" of the Phi operation requires "remembering" which block control came
 318 from.  The Phi operation takes on the value corresponding to the input control
 319 block.  In this case, if control comes in from the "then" block, it gets the
 320 value of "calltmp".  If control comes from the "else" block, it gets the value
 321 of "calltmp1".</p>
 322
 323 <p>At this point, you are probably starting to think "Oh no! This means my
 324 simple and elegant front-end will have to start generating SSA form in order to
 325 use LLVM!".  Fortunately, this is not the case, and we strongly advise
 326 <em>not</em> implementing an SSA construction algorithm in your front-end
 327 unless there is an amazingly good reason to do so.  In practice, there are two
 328 sorts of values that float around in code written for your average imperative
 329 programming language that might need Phi nodes:</p>
 330
 331 <ol>
 332 <li>Code that involves user variables: <tt>x = 1; x = x + 1; </tt></li>
 333 <li>Values that are implicit in the structure of your AST, such as the Phi node
 334 in this case.</li>
 335 </ol>
 336
 337 <p>In <a href="LangImpl7.html">Chapter 7</a> of this tutorial ("mutable
 338 variables"), we'll talk about #1
 339 in depth.  For now, just believe me that you don't need SSA construction to
 340 handle this case.  For #2, you have the choice of using the techniques that we will
 341 describe for #1, or you can insert Phi nodes directly, if convenient.  In this
 342 case, it is really really easy to generate the Phi node, so we choose to do it
 343 directly.</p>
 344
 345 <p>Okay, enough of the motivation and overview, lets generate code!</p>
 346
 347 </div>
 348
 349 <!-- ======================================================================= -->
 350 <div class="doc_subsubsection"><a name="ifcodegen">Code Generation for
 351 If/Then/Else</a></div>
 352 <!-- ======================================================================= -->
 353
 354 <div class="doc_text">
 355
 356 <p>In order to generate code for this, we implement the <tt>Codegen</tt> method
 357 for <tt>IfExprAST</tt>:</p>
 358
 359 <div class="doc_code">
 360 <pre>
 361 Value *IfExprAST::Codegen() {
 362   Value *CondV = Cond-&gt;Codegen();
 363   if (CondV == 0) return 0;
 364
 365   // Convert condition to a bool by comparing equal to 0.0.
 366   CondV = Builder.CreateFCmpONE(CondV,
 367                               ConstantFP::get(getGlobalContext(), APFloat(0.0)),
 368                                 "ifcond");
 369 </pre>
 370 </div>
 371
 372 <p>This code is straightforward and similar to what we saw before.  We emit the
 373 expression for the condition, then compare that value to zero to get a truth
 374 value as a 1-bit (bool) value.</p>
 375
 376 <div class="doc_code">
 377 <pre>
 378   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
 379
 380   // Create blocks for the then and else cases.  Insert the 'then' block at the
 381   // end of the function.
 382   BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
 383   BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
 384   BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
 385
 386   Builder.CreateCondBr(CondV, ThenBB, ElseBB);
 387 </pre>
 388 </div>
 389
 390 <p>This code creates the basic blocks that are related to the if/then/else
 391 statement, and correspond directly to the blocks in the example above.  The
 392 first line gets the current Function object that is being built.  It
 393 gets this by asking the builder for the current BasicBlock, and asking that
 394 block for its "parent" (the function it is currently embedded into).</p>
 395
 396 <p>Once it has that, it creates three blocks.  Note that it passes "TheFunction"
 397 into the constructor for the "then" block.  This causes the constructor to
 398 automatically insert the new block into the end of the specified function.  The
 399 other two blocks are created, but aren't yet inserted into the function.</p>
 400
 401 <p>Once the blocks are created, we can emit the conditional branch that chooses
 402 between them.  Note that creating new blocks does not implicitly affect the
 403 IRBuilder, so it is still inserting into the block that the condition
 404 went into.  Also note that it is creating a branch to the "then" block and the
 405 "else" block, even though the "else" block isn't inserted into the function yet.
 406 This is all ok: it is the standard way that LLVM supports forward
 407 references.</p>
 408
 409 <div class="doc_code">
 410 <pre>
 411   // Emit then value.
 412   Builder.SetInsertPoint(ThenBB);
 413
 414   Value *ThenV = Then-&gt;Codegen();
 415   if (ThenV == 0) return 0;
 416
 417   Builder.CreateBr(MergeBB);
 418   // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
 419   ThenBB = Builder.GetInsertBlock();
 420 </pre>
 421 </div>
 422
 423 <p>After the conditional branch is inserted, we move the builder to start
 424 inserting into the "then" block.  Strictly speaking, this call moves the
 425 insertion point to be at the end of the specified block.  However, since the
 426 "then" block is empty, it also starts out by inserting at the beginning of the
 427 block.  :)</p>
 428
 429 <p>Once the insertion point is set, we recursively codegen the "then" expression
 430 from the AST.  To finish off the "then" block, we create an unconditional branch
 431 to the merge block.  One interesting (and very important) aspect of the LLVM IR
 432 is that it <a href="../LangRef.html#functionstructure">requires all basic blocks
 433 to be "terminated"</a> with a <a href="../LangRef.html#terminators">control flow
 434 instruction</a> such as return or branch.  This means that all control flow,
 435 <em>including fall throughs</em> must be made explicit in the LLVM IR.  If you
 436 violate this rule, the verifier will emit an error.</p>
 437
 438 <p>The final line here is quite subtle, but is very important.  The basic issue
 439 is that when we create the Phi node in the merge block, we need to set up the
 440 block/value pairs that indicate how the Phi will work.  Importantly, the Phi
 441 node expects to have an entry for each predecessor of the block in the CFG.  Why
 442 then, are we getting the current block when we just set it to ThenBB 5 lines
 443 above?  The problem is that the "Then" expression may actually itself change the
 444 block that the Builder is emitting into if, for example, it contains a nested
 445 "if/then/else" expression.  Because calling Codegen recursively could
 446 arbitrarily change the notion of the current block, we are required to get an
 447 up-to-date value for code that will set up the Phi node.</p>
 448
 449 <div class="doc_code">
 450 <pre>
 451   // Emit else block.
 452   TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
 453   Builder.SetInsertPoint(ElseBB);
 454
 455   Value *ElseV = Else-&gt;Codegen();
 456   if (ElseV == 0) return 0;
 457
 458   Builder.CreateBr(MergeBB);
 459   // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
 460   ElseBB = Builder.GetInsertBlock();
 461 </pre>
 462 </div>
 463
 464 <p>Code generation for the 'else' block is basically identical to codegen for
 465 the 'then' block.  The only significant difference is the first line, which adds
 466 the 'else' block to the function.  Recall previously that the 'else' block was
 467 created, but not added to the function.  Now that the 'then' and 'else' blocks
 468 are emitted, we can finish up with the merge code:</p>
 469
 470 <div class="doc_code">
 471 <pre>
 472   // Emit merge block.
 473   TheFunction->getBasicBlockList().push_back(MergeBB);
 474   Builder.SetInsertPoint(MergeBB);
 475   PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
 476                                   "iftmp");
 477
 478   PN->addIncoming(ThenV, ThenBB);
 479   PN->addIncoming(ElseV, ElseBB);
 480   return PN;
 481 }
 482 </pre>
 483 </div>
 484
 485 <p>The first two lines here are now familiar: the first adds the "merge" block
 486 to the Function object (it was previously floating, like the else block above).
 487 The second block changes the insertion point so that newly created code will go
 488 into the "merge" block.  Once that is done, we need to create the PHI node and
 489 set up the block/value pairs for the PHI.</p>
 490
 491 <p>Finally, the CodeGen function returns the phi node as the value computed by
 492 the if/then/else expression.  In our example above, this returned value will
 493 feed into the code for the top-level function, which will create the return
 494 instruction.</p>
 495
 496 <p>Overall, we now have the ability to execute conditional code in
 497 Kaleidoscope.  With this extension, Kaleidoscope is a fairly complete language
 498 that can calculate a wide variety of numeric functions.  Next up we'll add
 499 another useful expression that is familiar from non-functional languages...</p>
 500
 501 </div>
 502
 503 <!-- *********************************************************************** -->
 504 <div class="doc_section"><a name="for">'for' Loop Expression</a></div>
 505 <!-- *********************************************************************** -->
 506
 507 <div class="doc_text">
 508
 509 <p>Now that we know how to add basic control flow constructs to the language,
 510 we have the tools to add more powerful things.  Lets add something more
 511 aggressive, a 'for' expression:</p>
 512
 513 <div class="doc_code">
 514 <pre>
 515  extern putchard(char)
 516  def printstar(n)
 517    for i = 1, i &lt; n, 1.0 in
 518      putchard(42);  # ascii 42 = '*'
 519
 520  # print 100 '*' characters
 521  printstar(100);
 522 </pre>
 523 </div>
 524
 525 <p>This expression defines a new variable ("i" in this case) which iterates from
 526 a starting value, while the condition ("i &lt; n" in this case) is true,
 527 incrementing by an optional step value ("1.0" in this case).  If the step value
 528 is omitted, it defaults to 1.0.  While the loop is true, it executes its
 529 body expression.  Because we don't have anything better to return, we'll just
 530 define the loop as always returning 0.0.  In the future when we have mutable
 531 variables, it will get more useful.</p>
 532
 533 <p>As before, lets talk about the changes that we need to Kaleidoscope to
 534 support this.</p>
 535
 536 </div>
 537
 538 <!-- ======================================================================= -->
 539 <div class="doc_subsubsection"><a name="forlexer">Lexer Extensions for
 540 the 'for' Loop</a></div>
 541 <!-- ======================================================================= -->
 542
 543 <div class="doc_text">
 544
 545 <p>The lexer extensions are the same sort of thing as for if/then/else:</p>
 546
 547 <div class="doc_code">
 548 <pre>
 549   ... in enum Token ...
 550   // control
 551   tok_if = -6, tok_then = -7, tok_else = -8,
 552 <b>  tok_for = -9, tok_in = -10</b>
 553
 554   ... in gettok ...
 555   if (IdentifierStr == "def") return tok_def;
 556   if (IdentifierStr == "extern") return tok_extern;
 557   if (IdentifierStr == "if") return tok_if;
 558   if (IdentifierStr == "then") return tok_then;
 559   if (IdentifierStr == "else") return tok_else;
 560   <b>if (IdentifierStr == "for") return tok_for;
 561   if (IdentifierStr == "in") return tok_in;</b>
 562   return tok_identifier;
 563 </pre>
 564 </div>
 565
 566 </div>
 567
 568 <!-- ======================================================================= -->
 569 <div class="doc_subsubsection"><a name="forast">AST Extensions for
 570 the 'for' Loop</a></div>
 571 <!-- ======================================================================= -->
 572
 573 <div class="doc_text">
 574
 575 <p>The AST node is just as simple.  It basically boils down to capturing
 576 the variable name and the constituent expressions in the node.</p>
 577
 578 <div class="doc_code">
 579 <pre>
 580 /// ForExprAST - Expression class for for/in.
 581 class ForExprAST : public ExprAST {
 582   std::string VarName;
 583   ExprAST *Start, *End, *Step, *Body;
 584 public:
 585   ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
 586              ExprAST *step, ExprAST *body)
 587     : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
 588   virtual Value *Codegen();
 589 };
 590 </pre>
 591 </div>
 592
 593 </div>
 594
 595 <!-- ======================================================================= -->
 596 <div class="doc_subsubsection"><a name="forparser">Parser Extensions for
 597 the 'for' Loop</a></div>
 598 <!-- ======================================================================= -->
 599
 600 <div class="doc_text">
 601
 602 <p>The parser code is also fairly standard.  The only interesting thing here is
 603 handling of the optional step value.  The parser code handles it by checking to
 604 see if the second comma is present.  If not, it sets the step value to null in
 605 the AST node:</p>
 606
 607 <div class="doc_code">
 608 <pre>
 609 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
 610 static ExprAST *ParseForExpr() {
 611   getNextToken();  // eat the for.
 612
 613   if (CurTok != tok_identifier)
 614     return Error("expected identifier after for");
 615
 616   std::string IdName = IdentifierStr;
 617   getNextToken();  // eat identifier.
 618
 619   if (CurTok != '=')
 620     return Error("expected '=' after for");
 621   getNextToken();  // eat '='.
 622
 623
 624   ExprAST *Start = ParseExpression();
 625   if (Start == 0) return 0;
 626   if (CurTok != ',')
 627     return Error("expected ',' after for start value");
 628   getNextToken();
 629
 630   ExprAST *End = ParseExpression();
 631   if (End == 0) return 0;
 632
 633   // The step value is optional.
 634   ExprAST *Step = 0;
 635   if (CurTok == ',') {
 636     getNextToken();
 637     Step = ParseExpression();
 638     if (Step == 0) return 0;
 639   }
 640
 641   if (CurTok != tok_in)
 642     return Error("expected 'in' after for");
 643   getNextToken();  // eat 'in'.
 644
 645   ExprAST *Body = ParseExpression();
 646   if (Body == 0) return 0;
 647
 648   return new ForExprAST(IdName, Start, End, Step, Body);
 649 }
 650 </pre>
 651 </div>
 652
 653 </div>
 654
 655 <!-- ======================================================================= -->
 656 <div class="doc_subsubsection"><a name="forir">LLVM IR for
 657 the 'for' Loop</a></div>
 658 <!-- ======================================================================= -->
 659
 660 <div class="doc_text">
 661
 662 <p>Now we get to the good part: the LLVM IR we want to generate for this thing.
 663 With the simple example above, we get this LLVM IR (note that this dump is
 664 generated with optimizations disabled for clarity):
 665 </p>
 666
 667 <div class="doc_code">
 668 <pre>
 669 declare double @putchard(double)
 670
 671 define double @printstar(double %n) {
 672 entry:
 673         ; initial value = 1.0 (inlined into phi)
 674         br label %loop
 675
 676 loop:           ; preds = %loop, %entry
 677         %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
 678         ; body
 679         %calltmp = call double @putchard( double 4.200000e+01 )
 680         ; increment
 681         %nextvar = add double %i, 1.000000e+00
 682
 683         ; termination test
 684         %cmptmp = fcmp ult double %i, %n
 685         %booltmp = uitofp i1 %cmptmp to double
 686         %loopcond = fcmp one double %booltmp, 0.000000e+00
 687         br i1 %loopcond, label %loop, label %afterloop
 688
 689 afterloop:              ; preds = %loop
 690         ; loop always returns 0.0
 691         ret double 0.000000e+00
 692 }
 693 </pre>
 694 </div>
 695
 696 <p>This loop contains all the same constructs we saw before: a phi node, several
 697 expressions, and some basic blocks.  Lets see how this fits together.</p>
 698
 699 </div>
 700
 701 <!-- ======================================================================= -->
 702 <div class="doc_subsubsection"><a name="forcodegen">Code Generation for
 703 the 'for' Loop</a></div>
 704 <!-- ======================================================================= -->
 705
 706 <div class="doc_text">
 707
 708 <p>The first part of Codegen is very simple: we just output the start expression
 709 for the loop value:</p>
 710
 711 <div class="doc_code">
 712 <pre>
 713 Value *ForExprAST::Codegen() {
 714   // Emit the start code first, without 'variable' in scope.
 715   Value *StartVal = Start-&gt;Codegen();
 716   if (StartVal == 0) return 0;
 717 </pre>
 718 </div>
 719
 720 <p>With this out of the way, the next step is to set up the LLVM basic block
 721 for the start of the loop body.  In the case above, the whole loop body is one
 722 block, but remember that the body code itself could consist of multiple blocks
 723 (e.g. if it contains an if/then/else or a for/in expression).</p>
 724
 725 <div class="doc_code">
 726 <pre>
 727   // Make the new basic block for the loop header, inserting after current
 728   // block.
 729   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
 730   BasicBlock *PreheaderBB = Builder.GetInsertBlock();
 731   BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
 732
 733   // Insert an explicit fall through from the current block to the LoopBB.
 734   Builder.CreateBr(LoopBB);
 735 </pre>
 736 </div>
 737
 738 <p>This code is similar to what we saw for if/then/else.  Because we will need
 739 it to create the Phi node, we remember the block that falls through into the
 740 loop.  Once we have that, we create the actual block that starts the loop and
 741 create an unconditional branch for the fall-through between the two blocks.</p>
 742
 743 <div class="doc_code">
 744 <pre>
 745   // Start insertion in LoopBB.
 746   Builder.SetInsertPoint(LoopBB);
 747
 748   // Start the PHI node with an entry for Start.
 749   PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
 750   Variable-&gt;addIncoming(StartVal, PreheaderBB);
 751 </pre>
 752 </div>
 753
 754 <p>Now that the "preheader" for the loop is set up, we switch to emitting code
 755 for the loop body.  To begin with, we move the insertion point and create the
 756 PHI node for the loop induction variable.  Since we already know the incoming
 757 value for the starting value, we add it to the Phi node.  Note that the Phi will
 758 eventually get a second value for the backedge, but we can't set it up yet
 759 (because it doesn't exist!).</p>
 760
 761 <div class="doc_code">
 762 <pre>
 763   // Within the loop, the variable is defined equal to the PHI node.  If it
 764   // shadows an existing variable, we have to restore it, so save it now.
 765   Value *OldVal = NamedValues[VarName];
 766   NamedValues[VarName] = Variable;
 767
 768   // Emit the body of the loop.  This, like any other expr, can change the
 769   // current BB.  Note that we ignore the value computed by the body, but don't
 770   // allow an error.
 771   if (Body-&gt;Codegen() == 0)
 772     return 0;
 773 </pre>
 774 </div>
 775
 776 <p>Now the code starts to get more interesting.  Our 'for' loop introduces a new
 777 variable to the symbol table.  This means that our symbol table can now contain
 778 either function arguments or loop variables.  To handle this, before we codegen
 779 the body of the loop, we add the loop variable as the current value for its
 780 name.  Note that it is possible that there is a variable of the same name in the
 781 outer scope.  It would be easy to make this an error (emit an error and return
 782 null if there is already an entry for VarName) but we choose to allow shadowing
 783 of variables.  In order to handle this correctly, we remember the Value that
 784 we are potentially shadowing in <tt>OldVal</tt> (which will be null if there is
 785 no shadowed variable).</p>
 786
 787 <p>Once the loop variable is set into the symbol table, the code recursively
 788 codegen's the body.  This allows the body to use the loop variable: any
 789 references to it will naturally find it in the symbol table.</p>
 790
 791 <div class="doc_code">
 792 <pre>
 793   // Emit the step value.
 794   Value *StepVal;
 795   if (Step) {
 796     StepVal = Step-&gt;Codegen();
 797     if (StepVal == 0) return 0;
 798   } else {
 799     // If not specified, use 1.0.
 800     StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
 801   }
 802
 803   Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
 804 </pre>
 805 </div>
 806
 807 <p>Now that the body is emitted, we compute the next value of the iteration
 808 variable by adding the step value, or 1.0 if it isn't present. '<tt>NextVar</tt>'
 809 will be the value of the loop variable on the next iteration of the loop.</p>
 810
 811 <div class="doc_code">
 812 <pre>
 813   // Compute the end condition.
 814   Value *EndCond = End-&gt;Codegen();
 815   if (EndCond == 0) return EndCond;
 816
 817   // Convert condition to a bool by comparing equal to 0.0.
 818   EndCond = Builder.CreateFCmpONE(EndCond,
 819                               ConstantFP::get(getGlobalContext(), APFloat(0.0)),
 820                                   "loopcond");
 821 </pre>
 822 </div>
 823
 824 <p>Finally, we evaluate the exit value of the loop, to determine whether the
 825 loop should exit.  This mirrors the condition evaluation for the if/then/else
 826 statement.</p>
 827
 828 <div class="doc_code">
 829 <pre>
 830   // Create the "after loop" block and insert it.
 831   BasicBlock *LoopEndBB = Builder.GetInsertBlock();
 832   BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
 833
 834   // Insert the conditional branch into the end of LoopEndBB.
 835   Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
 836
 837   // Any new code will be inserted in AfterBB.
 838   Builder.SetInsertPoint(AfterBB);
 839 </pre>
 840 </div>
 841
 842 <p>With the code for the body of the loop complete, we just need to finish up
 843 the control flow for it.  This code remembers the end block (for the phi node), then creates the block for the loop exit ("afterloop").  Based on the value of the
 844 exit condition, it creates a conditional branch that chooses between executing
 845 the loop again and exiting the loop.  Any future code is emitted in the
 846 "afterloop" block, so it sets the insertion position to it.</p>
 847
 848 <div class="doc_code">
 849 <pre>
 850   // Add a new entry to the PHI node for the backedge.
 851   Variable-&gt;addIncoming(NextVar, LoopEndBB);
 852
 853   // Restore the unshadowed variable.
 854   if (OldVal)
 855     NamedValues[VarName] = OldVal;
 856   else
 857     NamedValues.erase(VarName);
 858
 859   // for expr always returns 0.0.
 860   return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
 861 }
 862 </pre>
 863 </div>
 864
 865 <p>The final code handles various cleanups: now that we have the "NextVar"
 866 value, we can add the incoming value to the loop PHI node.  After that, we
 867 remove the loop variable from the symbol table, so that it isn't in scope after
 868 the for loop.  Finally, code generation of the for loop always returns 0.0, so
 869 that is what we return from <tt>ForExprAST::Codegen</tt>.</p>
 870
 871 <p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
 872 the tutorial.  In this chapter we added two control flow constructs, and used them to motivate a couple of aspects of the LLVM IR that are important for front-end implementors
 873 to know.  In the next chapter of our saga, we will get a bit crazier and add
 874 <a href="LangImpl6.html">user-defined operators</a> to our poor innocent
 875 language.</p>
 876
 877 </div>
 878
 879 <!-- *********************************************************************** -->
 880 <div class="doc_section"><a name="code">Full Code Listing</a></div>
 881 <!-- *********************************************************************** -->
 882
 883 <div class="doc_text">
 884
 885 <p>
 886 Here is the complete code listing for our running example, enhanced with the
 887 if/then/else and for expressions..  To build this example, use:
 888 </p>
 889
 890 <div class="doc_code">
 891 <pre>
 892    # Compile
 893    g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
 894    # Run
 895    ./toy
 896 </pre>
 897 </div>
 898
 899 <p>Here is the code:</p>
 900
 901 <div class="doc_code">
 902 <pre>
 903 #include "llvm/DerivedTypes.h"
 904 #include "llvm/ExecutionEngine/ExecutionEngine.h"
 905 #include "llvm/ExecutionEngine/Interpreter.h"
 906 #include "llvm/ExecutionEngine/JIT.h"
 907 #include "llvm/LLVMContext.h"
 908 #include "llvm/Module.h"
 909 #include "llvm/ModuleProvider.h"
 910 #include "llvm/PassManager.h"
 911 #include "llvm/Analysis/Verifier.h"
 912 #include "llvm/Target/TargetData.h"
 913 #include "llvm/Target/TargetSelect.h"
 914 #include "llvm/Transforms/Scalar.h"
 915 #include "llvm/Support/IRBuilder.h"
 916 #include &lt;cstdio&gt;
 917 #include &lt;string&gt;
 918 #include &lt;map&gt;
 919 #include &lt;vector&gt;
 920 using namespace llvm;
 921
 922 //===----------------------------------------------------------------------===//
 923 // Lexer
 924 //===----------------------------------------------------------------------===//
 925
 926 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
 927 // of these for known things.
 928 enum Token {
 929   tok_eof = -1,
 930
 931   // commands
 932   tok_def = -2, tok_extern = -3,
 933
 934   // primary
 935   tok_identifier = -4, tok_number = -5,
 936
 937   // control
 938   tok_if = -6, tok_then = -7, tok_else = -8,
 939   tok_for = -9, tok_in = -10
 940 };
 941
 942 static std::string IdentifierStr;  // Filled in if tok_identifier
 943 static double NumVal;              // Filled in if tok_number
 944
 945 /// gettok - Return the next token from standard input.
 946 static int gettok() {
 947   static int LastChar = ' ';
 948
 949   // Skip any whitespace.
 950   while (isspace(LastChar))
 951     LastChar = getchar();
 952
 953   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
 954     IdentifierStr = LastChar;
 955     while (isalnum((LastChar = getchar())))
 956       IdentifierStr += LastChar;
 957
 958     if (IdentifierStr == "def") return tok_def;
 959     if (IdentifierStr == "extern") return tok_extern;
 960     if (IdentifierStr == "if") return tok_if;
 961     if (IdentifierStr == "then") return tok_then;
 962     if (IdentifierStr == "else") return tok_else;
 963     if (IdentifierStr == "for") return tok_for;
 964     if (IdentifierStr == "in") return tok_in;
 965     return tok_identifier;
 966   }
 967
 968   if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
 969     std::string NumStr;
 970     do {
 971       NumStr += LastChar;
 972       LastChar = getchar();
 973     } while (isdigit(LastChar) || LastChar == '.');
 974
 975     NumVal = strtod(NumStr.c_str(), 0);
 976     return tok_number;
 977   }
 978
 979   if (LastChar == '#') {
 980     // Comment until end of line.
 981     do LastChar = getchar();
 982     while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
 983
 984     if (LastChar != EOF)
 985       return gettok();
 986   }
 987
 988   // Check for end of file.  Don't eat the EOF.
 989   if (LastChar == EOF)
 990     return tok_eof;
 991
 992   // Otherwise, just return the character as its ascii value.
 993   int ThisChar = LastChar;
 994   LastChar = getchar();
 995   return ThisChar;
 996 }
 997
 998 //===----------------------------------------------------------------------===//
 999 // Abstract Syntax Tree (aka Parse Tree)
1000 //===----------------------------------------------------------------------===//
1001
1002 /// ExprAST - Base class for all expression nodes.
1003 class ExprAST {
1004 public:
1005   virtual ~ExprAST() {}
1006   virtual Value *Codegen() = 0;
1007 };
1008
1009 /// NumberExprAST - Expression class for numeric literals like "1.0".
1010 class NumberExprAST : public ExprAST {
1011   double Val;
1012 public:
1013   NumberExprAST(double val) : Val(val) {}
1014   virtual Value *Codegen();
1015 };
1016
1017 /// VariableExprAST - Expression class for referencing a variable, like "a".
1018 class VariableExprAST : public ExprAST {
1019   std::string Name;
1020 public:
1021   VariableExprAST(const std::string &amp;name) : Name(name) {}
1022   virtual Value *Codegen();
1023 };
1024
1025 /// BinaryExprAST - Expression class for a binary operator.
1026 class BinaryExprAST : public ExprAST {
1027   char Op;
1028   ExprAST *LHS, *RHS;
1029 public:
1030   BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
1031     : Op(op), LHS(lhs), RHS(rhs) {}
1032   virtual Value *Codegen();
1033 };
1034
1035 /// CallExprAST - Expression class for function calls.
1036 class CallExprAST : public ExprAST {
1037   std::string Callee;
1038   std::vector&lt;ExprAST*&gt; Args;
1039 public:
1040   CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
1041     : Callee(callee), Args(args) {}
1042   virtual Value *Codegen();
1043 };
1044
1045 /// IfExprAST - Expression class for if/then/else.
1046 class IfExprAST : public ExprAST {
1047   ExprAST *Cond, *Then, *Else;
1048 public:
1049   IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1050   : Cond(cond), Then(then), Else(_else) {}
1051   virtual Value *Codegen();
1052 };
1053
1054 /// ForExprAST - Expression class for for/in.
1055 class ForExprAST : public ExprAST {
1056   std::string VarName;
1057   ExprAST *Start, *End, *Step, *Body;
1058 public:
1059   ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
1060              ExprAST *step, ExprAST *body)
1061     : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1062   virtual Value *Codegen();
1063 };
1064
1065 /// PrototypeAST - This class represents the "prototype" for a function,
1066 /// which captures its name, and its argument names (thus implicitly the number
1067 /// of arguments the function takes).
1068 class PrototypeAST {
1069   std::string Name;
1070   std::vector&lt;std::string&gt; Args;
1071 public:
1072   PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args)
1073     : Name(name), Args(args) {}
1074
1075   Function *Codegen();
1076 };
1077
1078 /// FunctionAST - This class represents a function definition itself.
1079 class FunctionAST {
1080   PrototypeAST *Proto;
1081   ExprAST *Body;
1082 public:
1083   FunctionAST(PrototypeAST *proto, ExprAST *body)
1084     : Proto(proto), Body(body) {}
1085
1086   Function *Codegen();
1087 };
1088
1089 //===----------------------------------------------------------------------===//
1090 // Parser
1091 //===----------------------------------------------------------------------===//
1092
1093 /// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
1094 /// token the parser is looking at.  getNextToken reads another token from the
1095 /// lexer and updates CurTok with its results.
1096 static int CurTok;
1097 static int getNextToken() {
1098   return CurTok = gettok();
1099 }
1100
1101 /// BinopPrecedence - This holds the precedence for each binary operator that is
1102 /// defined.
1103 static std::map&lt;char, int&gt; BinopPrecedence;
1104
1105 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1106 static int GetTokPrecedence() {
1107   if (!isascii(CurTok))
1108     return -1;
1109
1110   // Make sure it's a declared binop.
1111   int TokPrec = BinopPrecedence[CurTok];
1112   if (TokPrec &lt;= 0) return -1;
1113   return TokPrec;
1114 }
1115
1116 /// Error* - These are little helper functions for error handling.
1117 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1118 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1119 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1120
1121 static ExprAST *ParseExpression();
1122
1123 /// identifierexpr
1124 ///   ::= identifier
1125 ///   ::= identifier '(' expression* ')'
1126 static ExprAST *ParseIdentifierExpr() {
1127   std::string IdName = IdentifierStr;
1128
1129   getNextToken();  // eat identifier.
1130
1131   if (CurTok != '(') // Simple variable ref.
1132     return new VariableExprAST(IdName);
1133
1134   // Call.
1135   getNextToken();  // eat (
1136   std::vector&lt;ExprAST*&gt; Args;
1137   if (CurTok != ')') {
1138     while (1) {
1139       ExprAST *Arg = ParseExpression();
1140       if (!Arg) return 0;
1141       Args.push_back(Arg);
1142
1143       if (CurTok == ')') break;
1144
1145       if (CurTok != ',')
1146         return Error("Expected ')' or ',' in argument list");
1147       getNextToken();
1148     }
1149   }
1150
1151   // Eat the ')'.
1152   getNextToken();
1153
1154   return new CallExprAST(IdName, Args);
1155 }
1156
1157 /// numberexpr ::= number
1158 static ExprAST *ParseNumberExpr() {
1159   ExprAST *Result = new NumberExprAST(NumVal);
1160   getNextToken(); // consume the number
1161   return Result;
1162 }
1163
1164 /// parenexpr ::= '(' expression ')'
1165 static ExprAST *ParseParenExpr() {
1166   getNextToken();  // eat (.
1167   ExprAST *V = ParseExpression();
1168   if (!V) return 0;
1169
1170   if (CurTok != ')')
1171     return Error("expected ')'");
1172   getNextToken();  // eat ).
1173   return V;
1174 }
1175
1176 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1177 static ExprAST *ParseIfExpr() {
1178   getNextToken();  // eat the if.
1179
1180   // condition.
1181   ExprAST *Cond = ParseExpression();
1182   if (!Cond) return 0;
1183
1184   if (CurTok != tok_then)
1185     return Error("expected then");
1186   getNextToken();  // eat the then
1187
1188   ExprAST *Then = ParseExpression();
1189   if (Then == 0) return 0;
1190
1191   if (CurTok != tok_else)
1192     return Error("expected else");
1193
1194   getNextToken();
1195
1196   ExprAST *Else = ParseExpression();
1197   if (!Else) return 0;
1198
1199   return new IfExprAST(Cond, Then, Else);
1200 }
1201
1202 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1203 static ExprAST *ParseForExpr() {
1204   getNextToken();  // eat the for.
1205
1206   if (CurTok != tok_identifier)
1207     return Error("expected identifier after for");
1208
1209   std::string IdName = IdentifierStr;
1210   getNextToken();  // eat identifier.
1211
1212   if (CurTok != '=')
1213     return Error("expected '=' after for");
1214   getNextToken();  // eat '='.
1215
1216
1217   ExprAST *Start = ParseExpression();
1218   if (Start == 0) return 0;
1219   if (CurTok != ',')
1220     return Error("expected ',' after for start value");
1221   getNextToken();
1222
1223   ExprAST *End = ParseExpression();
1224   if (End == 0) return 0;
1225
1226   // The step value is optional.
1227   ExprAST *Step = 0;
1228   if (CurTok == ',') {
1229     getNextToken();
1230     Step = ParseExpression();
1231     if (Step == 0) return 0;
1232   }
1233
1234   if (CurTok != tok_in)
1235     return Error("expected 'in' after for");
1236   getNextToken();  // eat 'in'.
1237
1238   ExprAST *Body = ParseExpression();
1239   if (Body == 0) return 0;
1240
1241   return new ForExprAST(IdName, Start, End, Step, Body);
1242 }
1243
1244 /// primary
1245 ///   ::= identifierexpr
1246 ///   ::= numberexpr
1247 ///   ::= parenexpr
1248 ///   ::= ifexpr
1249 ///   ::= forexpr
1250 static ExprAST *ParsePrimary() {
1251   switch (CurTok) {
1252   default: return Error("unknown token when expecting an expression");
1253   case tok_identifier: return ParseIdentifierExpr();
1254   case tok_number:     return ParseNumberExpr();
1255   case '(':            return ParseParenExpr();
1256   case tok_if:         return ParseIfExpr();
1257   case tok_for:        return ParseForExpr();
1258   }
1259 }
1260
1261 /// binoprhs
1262 ///   ::= ('+' primary)*
1263 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1264   // If this is a binop, find its precedence.
1265   while (1) {
1266     int TokPrec = GetTokPrecedence();
1267
1268     // If this is a binop that binds at least as tightly as the current binop,
1269     // consume it, otherwise we are done.
1270     if (TokPrec &lt; ExprPrec)
1271       return LHS;
1272
1273     // Okay, we know this is a binop.
1274     int BinOp = CurTok;
1275     getNextToken();  // eat binop
1276
1277     // Parse the primary expression after the binary operator.
1278     ExprAST *RHS = ParsePrimary();
1279     if (!RHS) return 0;
1280
1281     // If BinOp binds less tightly with RHS than the operator after RHS, let
1282     // the pending operator take RHS as its LHS.
1283     int NextPrec = GetTokPrecedence();
1284     if (TokPrec &lt; NextPrec) {
1285       RHS = ParseBinOpRHS(TokPrec+1, RHS);
1286       if (RHS == 0) return 0;
1287     }
1288
1289     // Merge LHS/RHS.
1290     LHS = new BinaryExprAST(BinOp, LHS, RHS);
1291   }
1292 }
1293
1294 /// expression
1295 ///   ::= primary binoprhs
1296 ///
1297 static ExprAST *ParseExpression() {
1298   ExprAST *LHS = ParsePrimary();
1299   if (!LHS) return 0;
1300
1301   return ParseBinOpRHS(0, LHS);
1302 }
1303
1304 /// prototype
1305 ///   ::= id '(' id* ')'
1306 static PrototypeAST *ParsePrototype() {
1307   if (CurTok != tok_identifier)
1308     return ErrorP("Expected function name in prototype");
1309
1310   std::string FnName = IdentifierStr;
1311   getNextToken();
1312
1313   if (CurTok != '(')
1314     return ErrorP("Expected '(' in prototype");
1315
1316   std::vector&lt;std::string&gt; ArgNames;
1317   while (getNextToken() == tok_identifier)
1318     ArgNames.push_back(IdentifierStr);
1319   if (CurTok != ')')
1320     return ErrorP("Expected ')' in prototype");
1321
1322   // success.
1323   getNextToken();  // eat ')'.
1324
1325   return new PrototypeAST(FnName, ArgNames);
1326 }
1327
1328 /// definition ::= 'def' prototype expression
1329 static FunctionAST *ParseDefinition() {
1330   getNextToken();  // eat def.
1331   PrototypeAST *Proto = ParsePrototype();
1332   if (Proto == 0) return 0;
1333
1334   if (ExprAST *E = ParseExpression())
1335     return new FunctionAST(Proto, E);
1336   return 0;
1337 }
1338
1339 /// toplevelexpr ::= expression
1340 static FunctionAST *ParseTopLevelExpr() {
1341   if (ExprAST *E = ParseExpression()) {
1342     // Make an anonymous proto.
1343     PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
1344     return new FunctionAST(Proto, E);
1345   }
1346   return 0;
1347 }
1348
1349 /// external ::= 'extern' prototype
1350 static PrototypeAST *ParseExtern() {
1351   getNextToken();  // eat extern.
1352   return ParsePrototype();
1353 }
1354
1355 //===----------------------------------------------------------------------===//
1356 // Code Generation
1357 //===----------------------------------------------------------------------===//
1358
1359 static Module *TheModule;
1360 static IRBuilder&lt;&gt; Builder(getGlobalContext());
1361 static std::map&lt;std::string, Value*&gt; NamedValues;
1362 static FunctionPassManager *TheFPM;
1363
1364 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1365
1366 Value *NumberExprAST::Codegen() {
1367   return ConstantFP::get(getGlobalContext(), APFloat(Val));
1368 }
1369
1370 Value *VariableExprAST::Codegen() {
1371   // Look this variable up in the function.
1372   Value *V = NamedValues[Name];
1373   return V ? V : ErrorV("Unknown variable name");
1374 }
1375
1376 Value *BinaryExprAST::Codegen() {
1377   Value *L = LHS-&gt;Codegen();
1378   Value *R = RHS-&gt;Codegen();
1379   if (L == 0 || R == 0) return 0;
1380
1381   switch (Op) {
1382   case '+': return Builder.CreateAdd(L, R, "addtmp");
1383   case '-': return Builder.CreateSub(L, R, "subtmp");
1384   case '*': return Builder.CreateMul(L, R, "multmp");
1385   case '&lt;':
1386     L = Builder.CreateFCmpULT(L, R, "cmptmp");
1387     // Convert bool 0/1 to double 0.0 or 1.0
1388     return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1389                                 "booltmp");
1390   default: return ErrorV("invalid binary operator");
1391   }
1392 }
1393
1394 Value *CallExprAST::Codegen() {
1395   // Look up the name in the global module table.
1396   Function *CalleeF = TheModule-&gt;getFunction(Callee);
1397   if (CalleeF == 0)
1398     return ErrorV("Unknown function referenced");
1399
1400   // If argument mismatch error.
1401   if (CalleeF-&gt;arg_size() != Args.size())
1402     return ErrorV("Incorrect # arguments passed");
1403
1404   std::vector&lt;Value*&gt; ArgsV;
1405   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1406     ArgsV.push_back(Args[i]-&gt;Codegen());
1407     if (ArgsV.back() == 0) return 0;
1408   }
1409
1410   return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1411 }
1412
1413 Value *IfExprAST::Codegen() {
1414   Value *CondV = Cond-&gt;Codegen();
1415   if (CondV == 0) return 0;
1416
1417   // Convert condition to a bool by comparing equal to 0.0.
1418   CondV = Builder.CreateFCmpONE(CondV,
1419                               ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1420                                 "ifcond");
1421
1422   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1423
1424   // Create blocks for the then and else cases.  Insert the 'then' block at the
1425   // end of the function.
1426   BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
1427   BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
1428   BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");
1429
1430   Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1431
1432   // Emit then value.
1433   Builder.SetInsertPoint(ThenBB);
1434
1435   Value *ThenV = Then-&gt;Codegen();
1436   if (ThenV == 0) return 0;
1437
1438   Builder.CreateBr(MergeBB);
1439   // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1440   ThenBB = Builder.GetInsertBlock();
1441
1442   // Emit else block.
1443   TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
1444   Builder.SetInsertPoint(ElseBB);
1445
1446   Value *ElseV = Else-&gt;Codegen();
1447   if (ElseV == 0) return 0;
1448
1449   Builder.CreateBr(MergeBB);
1450   // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1451   ElseBB = Builder.GetInsertBlock();
1452
1453   // Emit merge block.
1454   TheFunction-&gt;getBasicBlockList().push_back(MergeBB);
1455   Builder.SetInsertPoint(MergeBB);
1456   PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
1457                                   "iftmp");
1458
1459   PN-&gt;addIncoming(ThenV, ThenBB);
1460   PN-&gt;addIncoming(ElseV, ElseBB);
1461   return PN;
1462 }
1463
1464 Value *ForExprAST::Codegen() {
1465   // Output this as:
1466   //   ...
1467   //   start = startexpr
1468   //   goto loop
1469   // loop:
1470   //   variable = phi [start, loopheader], [nextvariable, loopend]
1471   //   ...
1472   //   bodyexpr
1473   //   ...
1474   // loopend:
1475   //   step = stepexpr
1476   //   nextvariable = variable + step
1477   //   endcond = endexpr
1478   //   br endcond, loop, endloop
1479   // outloop:
1480
1481   // Emit the start code first, without 'variable' in scope.
1482   Value *StartVal = Start-&gt;Codegen();
1483   if (StartVal == 0) return 0;
1484
1485   // Make the new basic block for the loop header, inserting after current
1486   // block.
1487   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1488   BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1489   BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction);
1490
1491   // Insert an explicit fall through from the current block to the LoopBB.
1492   Builder.CreateBr(LoopBB);
1493
1494   // Start insertion in LoopBB.
1495   Builder.SetInsertPoint(LoopBB);
1496
1497   // Start the PHI node with an entry for Start.
1498   PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
1499   Variable-&gt;addIncoming(StartVal, PreheaderBB);
1500
1501   // Within the loop, the variable is defined equal to the PHI node.  If it
1502   // shadows an existing variable, we have to restore it, so save it now.
1503   Value *OldVal = NamedValues[VarName];
1504   NamedValues[VarName] = Variable;
1505
1506   // Emit the body of the loop.  This, like any other expr, can change the
1507   // current BB.  Note that we ignore the value computed by the body, but don't
1508   // allow an error.
1509   if (Body-&gt;Codegen() == 0)
1510     return 0;
1511
1512   // Emit the step value.
1513   Value *StepVal;
1514   if (Step) {
1515     StepVal = Step-&gt;Codegen();
1516     if (StepVal == 0) return 0;
1517   } else {
1518     // If not specified, use 1.0.
1519     StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0));
1520   }
1521
1522   Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
1523
1524   // Compute the end condition.
1525   Value *EndCond = End-&gt;Codegen();
1526   if (EndCond == 0) return EndCond;
1527
1528   // Convert condition to a bool by comparing equal to 0.0.
1529   EndCond = Builder.CreateFCmpONE(EndCond,
1530                               ConstantFP::get(getGlobalContext(), APFloat(0.0)),
1531                                   "loopcond");
1532
1533   // Create the "after loop" block and insert it.
1534   BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1535   BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction);
1536
1537   // Insert the conditional branch into the end of LoopEndBB.
1538   Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1539
1540   // Any new code will be inserted in AfterBB.
1541   Builder.SetInsertPoint(AfterBB);
1542
1543   // Add a new entry to the PHI node for the backedge.
1544   Variable-&gt;addIncoming(NextVar, LoopEndBB);
1545
1546   // Restore the unshadowed variable.
1547   if (OldVal)
1548     NamedValues[VarName] = OldVal;
1549   else
1550     NamedValues.erase(VarName);
1551
1552
1553   // for expr always returns 0.0.
1554   return Constant::getNullValue(Type::getDoubleTy(getGlobalContext()));
1555 }
1556
1557 Function *PrototypeAST::Codegen() {
1558   // Make the function type:  double(double,double) etc.
1559   std::vector&lt;const Type*&gt; Doubles(Args.size(),
1560                                    Type::getDoubleTy(getGlobalContext()));
1561   FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1562                                        Doubles, false);
1563
1564   Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
1565
1566   // If F conflicted, there was already something named 'Name'.  If it has a
1567   // body, don't allow redefinition or reextern.
1568   if (F-&gt;getName() != Name) {
1569     // Delete the one we just made and get the existing one.
1570     F-&gt;eraseFromParent();
1571     F = TheModule-&gt;getFunction(Name);
1572
1573     // If F already has a body, reject this.
1574     if (!F-&gt;empty()) {
1575       ErrorF("redefinition of function");
1576       return 0;
1577     }
1578
1579     // If F took a different number of args, reject.
1580     if (F-&gt;arg_size() != Args.size()) {
1581       ErrorF("redefinition of function with different # args");
1582       return 0;
1583     }
1584   }
1585
1586   // Set names for all arguments.
1587   unsigned Idx = 0;
1588   for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1589        ++AI, ++Idx) {
1590     AI-&gt;setName(Args[Idx]);
1591
1592     // Add arguments to variable symbol table.
1593     NamedValues[Args[Idx]] = AI;
1594   }
1595
1596   return F;
1597 }
1598
1599 Function *FunctionAST::Codegen() {
1600   NamedValues.clear();
1601
1602   Function *TheFunction = Proto-&gt;Codegen();
1603   if (TheFunction == 0)
1604     return 0;
1605
1606   // Create a new basic block to start insertion into.
1607   BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
1608   Builder.SetInsertPoint(BB);
1609
1610   if (Value *RetVal = Body-&gt;Codegen()) {
1611     // Finish off the function.
1612     Builder.CreateRet(RetVal);
1613
1614     // Validate the generated code, checking for consistency.
1615     verifyFunction(*TheFunction);
1616
1617     // Optimize the function.
1618     TheFPM-&gt;run(*TheFunction);
1619
1620     return TheFunction;
1621   }
1622
1623   // Error reading body, remove function.
1624   TheFunction-&gt;eraseFromParent();
1625   return 0;
1626 }
1627
1628 //===----------------------------------------------------------------------===//
1629 // Top-Level parsing and JIT Driver
1630 //===----------------------------------------------------------------------===//
1631
1632 static ExecutionEngine *TheExecutionEngine;
1633
1634 static void HandleDefinition() {
1635   if (FunctionAST *F = ParseDefinition()) {
1636     if (Function *LF = F-&gt;Codegen()) {
1637       fprintf(stderr, "Read function definition:");
1638       LF-&gt;dump();
1639     }
1640   } else {
1641     // Skip token for error recovery.
1642     getNextToken();
1643   }
1644 }
1645
1646 static void HandleExtern() {
1647   if (PrototypeAST *P = ParseExtern()) {
1648     if (Function *F = P-&gt;Codegen()) {
1649       fprintf(stderr, "Read extern: ");
1650       F-&gt;dump();
1651     }
1652   } else {
1653     // Skip token for error recovery.
1654     getNextToken();
1655   }
1656 }
1657
1658 static void HandleTopLevelExpression() {
1659   // Evaluate a top-level expression into an anonymous function.
1660   if (FunctionAST *F = ParseTopLevelExpr()) {
1661     if (Function *LF = F-&gt;Codegen()) {
1662       // JIT the function, returning a function pointer.
1663       void *FPtr = TheExecutionEngine-&gt;getPointerToFunction(LF);
1664
1665       // Cast it to the right type (takes no arguments, returns a double) so we
1666       // can call it as a native function.
1667       double (*FP)() = (double (*)())(intptr_t)FPtr;
1668       fprintf(stderr, "Evaluated to %f\n", FP());
1669     }
1670   } else {
1671     // Skip token for error recovery.
1672     getNextToken();
1673   }
1674 }
1675
1676 /// top ::= definition | external | expression | ';'
1677 static void MainLoop() {
1678   while (1) {
1679     fprintf(stderr, "ready&gt; ");
1680     switch (CurTok) {
1681     case tok_eof:    return;
1682     case ';':        getNextToken(); break;  // ignore top-level semicolons.
1683     case tok_def:    HandleDefinition(); break;
1684     case tok_extern: HandleExtern(); break;
1685     default:         HandleTopLevelExpression(); break;
1686     }
1687   }
1688 }
1689
1690 //===----------------------------------------------------------------------===//
1691 // "Library" functions that can be "extern'd" from user code.
1692 //===----------------------------------------------------------------------===//
1693
1694 /// putchard - putchar that takes a double and returns 0.
1695 extern "C"
1696 double putchard(double X) {
1697   putchar((char)X);
1698   return 0;
1699 }
1700
1701 //===----------------------------------------------------------------------===//
1702 // Main driver code.
1703 //===----------------------------------------------------------------------===//
1704
1705 int main() {
1706   InitializeNativeTarget();
1707   LLVMContext &amp;Context = getGlobalContext();
1708
1709   // Install standard binary operators.
1710   // 1 is lowest precedence.
1711   BinopPrecedence['&lt;'] = 10;
1712   BinopPrecedence['+'] = 20;
1713   BinopPrecedence['-'] = 20;
1714   BinopPrecedence['*'] = 40;  // highest.
1715
1716   // Prime the first token.
1717   fprintf(stderr, "ready&gt; ");
1718   getNextToken();
1719
1720   // Make the module, which holds all the code.
1721   TheModule = new Module("my cool jit", Context);
1722
1723   ExistingModuleProvider *OurModuleProvider =
1724       new ExistingModuleProvider(TheModule);
1725
1726   // Create the JIT.  This takes ownership of the module and module provider.
1727   TheExecutionEngine = EngineBuilder(OurModuleProvider).create();
1728
1729   FunctionPassManager OurFPM(OurModuleProvider);
1730
1731   // Set up the optimizer pipeline.  Start with registering info about how the
1732   // target lays out data structures.
1733   OurFPM.add(new TargetData(*TheExecutionEngine-&gt;getTargetData()));
1734   // Do simple "peephole" optimizations and bit-twiddling optzns.
1735   OurFPM.add(createInstructionCombiningPass());
1736   // Reassociate expressions.
1737   OurFPM.add(createReassociatePass());
1738   // Eliminate Common SubExpressions.
1739   OurFPM.add(createGVNPass());
1740   // Simplify the control flow graph (deleting unreachable blocks, etc).
1741   OurFPM.add(createCFGSimplificationPass());
1742
1743   OurFPM.doInitialization();
1744
1745   // Set the global so the code gen can use this.
1746   TheFPM = &amp;OurFPM;
1747
1748   // Run the main "interpreter loop" now.
1749   MainLoop();
1750
1751   TheFPM = 0;
1752
1753   // Print out all of the generated code.
1754   TheModule-&gt;dump();
1755
1756   return 0;
1757 }
1758 </pre>
1759 </div>
1760
1761 <a href="LangImpl6.html">Next: Extending the language: user-defined operators</a>
1762 </div>
1763
1764 <!-- *********************************************************************** -->
1765 <hr>
1766 <address>
1767   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1768   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1769   <a href="http://validator.w3.org/check/referer"><img
1770   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1771
1772   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1773   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1774   Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
1775 </address>
1776 </body>
1777 </html>