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 <center><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
 292 height="315"></center>
 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(Type::DoubleTy, 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 = new BasicBlock("then", TheFunction);
 383   BasicBlock *ElseBB = new BasicBlock("else");
 384   BasicBlock *MergeBB = new BasicBlock("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::DoubleTy, "iftmp");
 476
 477   PN->addIncoming(ThenV, ThenBB);
 478   PN->addIncoming(ElseV, ElseBB);
 479   return PN;
 480 }
 481 </pre>
 482 </div>
 483
 484 <p>The first two lines here are now familiar: the first adds the "merge" block
 485 to the Function object (it was previously floating, like the else block above).
 486 The second block changes the insertion point so that newly created code will go
 487 into the "merge" block.  Once that is done, we need to create the PHI node and
 488 set up the block/value pairs for the PHI.</p>
 489
 490 <p>Finally, the CodeGen function returns the phi node as the value computed by
 491 the if/then/else expression.  In our example above, this returned value will
 492 feed into the code for the top-level function, which will create the return
 493 instruction.</p>
 494
 495 <p>Overall, we now have the ability to execute conditional code in
 496 Kaleidoscope.  With this extension, Kaleidoscope is a fairly complete language
 497 that can calculate a wide variety of numeric functions.  Next up we'll add
 498 another useful expression that is familiar from non-functional languages...</p>
 499
 500 </div>
 501
 502 <!-- *********************************************************************** -->
 503 <div class="doc_section"><a name="for">'for' Loop Expression</a></div>
 504 <!-- *********************************************************************** -->
 505
 506 <div class="doc_text">
 507
 508 <p>Now that we know how to add basic control flow constructs to the language,
 509 we have the tools to add more powerful things.  Lets add something more
 510 aggressive, a 'for' expression:</p>
 511
 512 <div class="doc_code">
 513 <pre>
 514  extern putchard(char)
 515  def printstar(n)
 516    for i = 1, i &lt; n, 1.0 in
 517      putchard(42);  # ascii 42 = '*'
 518
 519  # print 100 '*' characters
 520  printstar(100);
 521 </pre>
 522 </div>
 523
 524 <p>This expression defines a new variable ("i" in this case) which iterates from
 525 a starting value, while the condition ("i &lt; n" in this case) is true,
 526 incrementing by an optional step value ("1.0" in this case).  If the step value
 527 is omitted, it defaults to 1.0.  While the loop is true, it executes its
 528 body expression.  Because we don't have anything better to return, we'll just
 529 define the loop as always returning 0.0.  In the future when we have mutable
 530 variables, it will get more useful.</p>
 531
 532 <p>As before, lets talk about the changes that we need to Kaleidoscope to
 533 support this.</p>
 534
 535 </div>
 536
 537 <!-- ======================================================================= -->
 538 <div class="doc_subsubsection"><a name="forlexer">Lexer Extensions for
 539 the 'for' Loop</a></div>
 540 <!-- ======================================================================= -->
 541
 542 <div class="doc_text">
 543
 544 <p>The lexer extensions are the same sort of thing as for if/then/else:</p>
 545
 546 <div class="doc_code">
 547 <pre>
 548   ... in enum Token ...
 549   // control
 550   tok_if = -6, tok_then = -7, tok_else = -8,
 551 <b>  tok_for = -9, tok_in = -10</b>
 552
 553   ... in gettok ...
 554   if (IdentifierStr == "def") return tok_def;
 555   if (IdentifierStr == "extern") return tok_extern;
 556   if (IdentifierStr == "if") return tok_if;
 557   if (IdentifierStr == "then") return tok_then;
 558   if (IdentifierStr == "else") return tok_else;
 559   <b>if (IdentifierStr == "for") return tok_for;
 560   if (IdentifierStr == "in") return tok_in;</b>
 561   return tok_identifier;
 562 </pre>
 563 </div>
 564
 565 </div>
 566
 567 <!-- ======================================================================= -->
 568 <div class="doc_subsubsection"><a name="forast">AST Extensions for
 569 the 'for' Loop</a></div>
 570 <!-- ======================================================================= -->
 571
 572 <div class="doc_text">
 573
 574 <p>The AST node is just as simple.  It basically boils down to capturing
 575 the variable name and the constituent expressions in the node.</p>
 576
 577 <div class="doc_code">
 578 <pre>
 579 /// ForExprAST - Expression class for for/in.
 580 class ForExprAST : public ExprAST {
 581   std::string VarName;
 582   ExprAST *Start, *End, *Step, *Body;
 583 public:
 584   ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
 585              ExprAST *step, ExprAST *body)
 586     : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
 587   virtual Value *Codegen();
 588 };
 589 </pre>
 590 </div>
 591
 592 </div>
 593
 594 <!-- ======================================================================= -->
 595 <div class="doc_subsubsection"><a name="forparser">Parser Extensions for
 596 the 'for' Loop</a></div>
 597 <!-- ======================================================================= -->
 598
 599 <div class="doc_text">
 600
 601 <p>The parser code is also fairly standard.  The only interesting thing here is
 602 handling of the optional step value.  The parser code handles it by checking to
 603 see if the second comma is present.  If not, it sets the step value to null in
 604 the AST node:</p>
 605
 606 <div class="doc_code">
 607 <pre>
 608 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
 609 static ExprAST *ParseForExpr() {
 610   getNextToken();  // eat the for.
 611
 612   if (CurTok != tok_identifier)
 613     return Error("expected identifier after for");
 614
 615   std::string IdName = IdentifierStr;
 616   getNextToken();  // eat identifier.
 617
 618   if (CurTok != '=')
 619     return Error("expected '=' after for");
 620   getNextToken();  // eat '='.
 621
 622
 623   ExprAST *Start = ParseExpression();
 624   if (Start == 0) return 0;
 625   if (CurTok != ',')
 626     return Error("expected ',' after for start value");
 627   getNextToken();
 628
 629   ExprAST *End = ParseExpression();
 630   if (End == 0) return 0;
 631
 632   // The step value is optional.
 633   ExprAST *Step = 0;
 634   if (CurTok == ',') {
 635     getNextToken();
 636     Step = ParseExpression();
 637     if (Step == 0) return 0;
 638   }
 639
 640   if (CurTok != tok_in)
 641     return Error("expected 'in' after for");
 642   getNextToken();  // eat 'in'.
 643
 644   ExprAST *Body = ParseExpression();
 645   if (Body == 0) return 0;
 646
 647   return new ForExprAST(IdName, Start, End, Step, Body);
 648 }
 649 </pre>
 650 </div>
 651
 652 </div>
 653
 654 <!-- ======================================================================= -->
 655 <div class="doc_subsubsection"><a name="forir">LLVM IR for
 656 the 'for' Loop</a></div>
 657 <!-- ======================================================================= -->
 658
 659 <div class="doc_text">
 660
 661 <p>Now we get to the good part: the LLVM IR we want to generate for this thing.
 662 With the simple example above, we get this LLVM IR (note that this dump is
 663 generated with optimizations disabled for clarity):
 664 </p>
 665
 666 <div class="doc_code">
 667 <pre>
 668 declare double @putchard(double)
 669
 670 define double @printstar(double %n) {
 671 entry:
 672         ; initial value = 1.0 (inlined into phi)
 673         br label %loop
 674
 675 loop:           ; preds = %loop, %entry
 676         %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
 677         ; body
 678         %calltmp = call double @putchard( double 4.200000e+01 )
 679         ; increment
 680         %nextvar = add double %i, 1.000000e+00
 681
 682         ; termination test
 683         %cmptmp = fcmp ult double %i, %n
 684         %booltmp = uitofp i1 %cmptmp to double
 685         %loopcond = fcmp one double %booltmp, 0.000000e+00
 686         br i1 %loopcond, label %loop, label %afterloop
 687
 688 afterloop:              ; preds = %loop
 689         ; loop always returns 0.0
 690         ret double 0.000000e+00
 691 }
 692 </pre>
 693 </div>
 694
 695 <p>This loop contains all the same constructs we saw before: a phi node, several
 696 expressions, and some basic blocks.  Lets see how this fits together.</p>
 697
 698 </div>
 699
 700 <!-- ======================================================================= -->
 701 <div class="doc_subsubsection"><a name="forcodegen">Code Generation for
 702 the 'for' Loop</a></div>
 703 <!-- ======================================================================= -->
 704
 705 <div class="doc_text">
 706
 707 <p>The first part of Codegen is very simple: we just output the start expression
 708 for the loop value:</p>
 709
 710 <div class="doc_code">
 711 <pre>
 712 Value *ForExprAST::Codegen() {
 713   // Emit the start code first, without 'variable' in scope.
 714   Value *StartVal = Start-&gt;Codegen();
 715   if (StartVal == 0) return 0;
 716 </pre>
 717 </div>
 718
 719 <p>With this out of the way, the next step is to set up the LLVM basic block
 720 for the start of the loop body.  In the case above, the whole loop body is one
 721 block, but remember that the body code itself could consist of multiple blocks
 722 (e.g. if it contains an if/then/else or a for/in expression).</p>
 723
 724 <div class="doc_code">
 725 <pre>
 726   // Make the new basic block for the loop header, inserting after current
 727   // block.
 728   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
 729   BasicBlock *PreheaderBB = Builder.GetInsertBlock();
 730   BasicBlock *LoopBB = new BasicBlock("loop", TheFunction);
 731
 732   // Insert an explicit fall through from the current block to the LoopBB.
 733   Builder.CreateBr(LoopBB);
 734 </pre>
 735 </div>
 736
 737 <p>This code is similar to what we saw for if/then/else.  Because we will need
 738 it to create the Phi node, we remember the block that falls through into the
 739 loop.  Once we have that, we create the actual block that starts the loop and
 740 create an unconditional branch for the fall-through between the two blocks.</p>
 741
 742 <div class="doc_code">
 743 <pre>
 744   // Start insertion in LoopBB.
 745   Builder.SetInsertPoint(LoopBB);
 746
 747   // Start the PHI node with an entry for Start.
 748   PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
 749   Variable-&gt;addIncoming(StartVal, PreheaderBB);
 750 </pre>
 751 </div>
 752
 753 <p>Now that the "preheader" for the loop is set up, we switch to emitting code
 754 for the loop body.  To begin with, we move the insertion point and create the
 755 PHI node for the loop induction variable.  Since we already know the incoming
 756 value for the starting value, we add it to the Phi node.  Note that the Phi will
 757 eventually get a second value for the backedge, but we can't set it up yet
 758 (because it doesn't exist!).</p>
 759
 760 <div class="doc_code">
 761 <pre>
 762   // Within the loop, the variable is defined equal to the PHI node.  If it
 763   // shadows an existing variable, we have to restore it, so save it now.
 764   Value *OldVal = NamedValues[VarName];
 765   NamedValues[VarName] = Variable;
 766
 767   // Emit the body of the loop.  This, like any other expr, can change the
 768   // current BB.  Note that we ignore the value computed by the body, but don't
 769   // allow an error.
 770   if (Body-&gt;Codegen() == 0)
 771     return 0;
 772 </pre>
 773 </div>
 774
 775 <p>Now the code starts to get more interesting.  Our 'for' loop introduces a new
 776 variable to the symbol table.  This means that our symbol table can now contain
 777 either function arguments or loop variables.  To handle this, before we codegen
 778 the body of the loop, we add the loop variable as the current value for its
 779 name.  Note that it is possible that there is a variable of the same name in the
 780 outer scope.  It would be easy to make this an error (emit an error and return
 781 null if there is already an entry for VarName) but we choose to allow shadowing
 782 of variables.  In order to handle this correctly, we remember the Value that
 783 we are potentially shadowing in <tt>OldVal</tt> (which will be null if there is
 784 no shadowed variable).</p>
 785
 786 <p>Once the loop variable is set into the symbol table, the code recursively
 787 codegen's the body.  This allows the body to use the loop variable: any
 788 references to it will naturally find it in the symbol table.</p>
 789
 790 <div class="doc_code">
 791 <pre>
 792   // Emit the step value.
 793   Value *StepVal;
 794   if (Step) {
 795     StepVal = Step-&gt;Codegen();
 796     if (StepVal == 0) return 0;
 797   } else {
 798     // If not specified, use 1.0.
 799     StepVal = ConstantFP::get(Type::DoubleTy, APFloat(1.0));
 800   }
 801
 802   Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
 803 </pre>
 804 </div>
 805
 806 <p>Now that the body is emitted, we compute the next value of the iteration
 807 variable by adding the step value, or 1.0 if it isn't present. '<tt>NextVar</tt>'
 808 will be the value of the loop variable on the next iteration of the loop.</p>
 809
 810 <div class="doc_code">
 811 <pre>
 812   // Compute the end condition.
 813   Value *EndCond = End-&gt;Codegen();
 814   if (EndCond == 0) return EndCond;
 815
 816   // Convert condition to a bool by comparing equal to 0.0.
 817   EndCond = Builder.CreateFCmpONE(EndCond,
 818                                   ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
 819                                   "loopcond");
 820 </pre>
 821 </div>
 822
 823 <p>Finally, we evaluate the exit value of the loop, to determine whether the
 824 loop should exit.  This mirrors the condition evaluation for the if/then/else
 825 statement.</p>
 826
 827 <div class="doc_code">
 828 <pre>
 829   // Create the "after loop" block and insert it.
 830   BasicBlock *LoopEndBB = Builder.GetInsertBlock();
 831   BasicBlock *AfterBB = new BasicBlock("afterloop", TheFunction);
 832
 833   // Insert the conditional branch into the end of LoopEndBB.
 834   Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
 835
 836   // Any new code will be inserted in AfterBB.
 837   Builder.SetInsertPoint(AfterBB);
 838 </pre>
 839 </div>
 840
 841 <p>With the code for the body of the loop complete, we just need to finish up
 842 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
 843 exit condition, it creates a conditional branch that chooses between executing
 844 the loop again and exiting the loop.  Any future code is emitted in the
 845 "afterloop" block, so it sets the insertion position to it.</p>
 846
 847 <div class="doc_code">
 848 <pre>
 849   // Add a new entry to the PHI node for the backedge.
 850   Variable-&gt;addIncoming(NextVar, LoopEndBB);
 851
 852   // Restore the unshadowed variable.
 853   if (OldVal)
 854     NamedValues[VarName] = OldVal;
 855   else
 856     NamedValues.erase(VarName);
 857
 858   // for expr always returns 0.0.
 859   return Constant::getNullValue(Type::DoubleTy);
 860 }
 861 </pre>
 862 </div>
 863
 864 <p>The final code handles various cleanups: now that we have the "NextVar"
 865 value, we can add the incoming value to the loop PHI node.  After that, we
 866 remove the loop variable from the symbol table, so that it isn't in scope after
 867 the for loop.  Finally, code generation of the for loop always returns 0.0, so
 868 that is what we return from <tt>ForExprAST::Codegen</tt>.</p>
 869
 870 <p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
 871 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
 872 to know.  In the next chapter of our saga, we will get a bit crazier and add
 873 <a href="LangImpl6.html">user-defined operators</a> to our poor innocent
 874 language.</p>
 875
 876 </div>
 877
 878 <!-- *********************************************************************** -->
 879 <div class="doc_section"><a name="code">Full Code Listing</a></div>
 880 <!-- *********************************************************************** -->
 881
 882 <div class="doc_text">
 883
 884 <p>
 885 Here is the complete code listing for our running example, enhanced with the
 886 if/then/else and for expressions..  To build this example, use:
 887 </p>
 888
 889 <div class="doc_code">
 890 <pre>
 891    # Compile
 892    g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
 893    # Run
 894    ./toy
 895 </pre>
 896 </div>
 897
 898 <p>Here is the code:</p>
 899
 900 <div class="doc_code">
 901 <pre>
 902 #include "llvm/DerivedTypes.h"
 903 #include "llvm/ExecutionEngine/ExecutionEngine.h"
 904 #include "llvm/Module.h"
 905 #include "llvm/ModuleProvider.h"
 906 #include "llvm/PassManager.h"
 907 #include "llvm/Analysis/Verifier.h"
 908 #include "llvm/Target/TargetData.h"
 909 #include "llvm/Transforms/Scalar.h"
 910 #include "llvm/Support/IRBuilder.h"
 911 #include &lt;cstdio&gt;
 912 #include &lt;string&gt;
 913 #include &lt;map&gt;
 914 #include &lt;vector&gt;
 915 using namespace llvm;
 916
 917 //===----------------------------------------------------------------------===//
 918 // Lexer
 919 //===----------------------------------------------------------------------===//
 920
 921 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
 922 // of these for known things.
 923 enum Token {
 924   tok_eof = -1,
 925
 926   // commands
 927   tok_def = -2, tok_extern = -3,
 928
 929   // primary
 930   tok_identifier = -4, tok_number = -5,
 931
 932   // control
 933   tok_if = -6, tok_then = -7, tok_else = -8,
 934   tok_for = -9, tok_in = -10
 935 };
 936
 937 static std::string IdentifierStr;  // Filled in if tok_identifier
 938 static double NumVal;              // Filled in if tok_number
 939
 940 /// gettok - Return the next token from standard input.
 941 static int gettok() {
 942   static int LastChar = ' ';
 943
 944   // Skip any whitespace.
 945   while (isspace(LastChar))
 946     LastChar = getchar();
 947
 948   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
 949     IdentifierStr = LastChar;
 950     while (isalnum((LastChar = getchar())))
 951       IdentifierStr += LastChar;
 952
 953     if (IdentifierStr == "def") return tok_def;
 954     if (IdentifierStr == "extern") return tok_extern;
 955     if (IdentifierStr == "if") return tok_if;
 956     if (IdentifierStr == "then") return tok_then;
 957     if (IdentifierStr == "else") return tok_else;
 958     if (IdentifierStr == "for") return tok_for;
 959     if (IdentifierStr == "in") return tok_in;
 960     return tok_identifier;
 961   }
 962
 963   if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
 964     std::string NumStr;
 965     do {
 966       NumStr += LastChar;
 967       LastChar = getchar();
 968     } while (isdigit(LastChar) || LastChar == '.');
 969
 970     NumVal = strtod(NumStr.c_str(), 0);
 971     return tok_number;
 972   }
 973
 974   if (LastChar == '#') {
 975     // Comment until end of line.
 976     do LastChar = getchar();
 977     while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
 978
 979     if (LastChar != EOF)
 980       return gettok();
 981   }
 982
 983   // Check for end of file.  Don't eat the EOF.
 984   if (LastChar == EOF)
 985     return tok_eof;
 986
 987   // Otherwise, just return the character as its ascii value.
 988   int ThisChar = LastChar;
 989   LastChar = getchar();
 990   return ThisChar;
 991 }
 992
 993 //===----------------------------------------------------------------------===//
 994 // Abstract Syntax Tree (aka Parse Tree)
 995 //===----------------------------------------------------------------------===//
 996
 997 /// ExprAST - Base class for all expression nodes.
 998 class ExprAST {
 999 public:
1000   virtual ~ExprAST() {}
1001   virtual Value *Codegen() = 0;
1002 };
1003
1004 /// NumberExprAST - Expression class for numeric literals like "1.0".
1005 class NumberExprAST : public ExprAST {
1006   double Val;
1007 public:
1008   NumberExprAST(double val) : Val(val) {}
1009   virtual Value *Codegen();
1010 };
1011
1012 /// VariableExprAST - Expression class for referencing a variable, like "a".
1013 class VariableExprAST : public ExprAST {
1014   std::string Name;
1015 public:
1016   VariableExprAST(const std::string &amp;name) : Name(name) {}
1017   virtual Value *Codegen();
1018 };
1019
1020 /// BinaryExprAST - Expression class for a binary operator.
1021 class BinaryExprAST : public ExprAST {
1022   char Op;
1023   ExprAST *LHS, *RHS;
1024 public:
1025   BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
1026     : Op(op), LHS(lhs), RHS(rhs) {}
1027   virtual Value *Codegen();
1028 };
1029
1030 /// CallExprAST - Expression class for function calls.
1031 class CallExprAST : public ExprAST {
1032   std::string Callee;
1033   std::vector&lt;ExprAST*&gt; Args;
1034 public:
1035   CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
1036     : Callee(callee), Args(args) {}
1037   virtual Value *Codegen();
1038 };
1039
1040 /// IfExprAST - Expression class for if/then/else.
1041 class IfExprAST : public ExprAST {
1042   ExprAST *Cond, *Then, *Else;
1043 public:
1044   IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1045   : Cond(cond), Then(then), Else(_else) {}
1046   virtual Value *Codegen();
1047 };
1048
1049 /// ForExprAST - Expression class for for/in.
1050 class ForExprAST : public ExprAST {
1051   std::string VarName;
1052   ExprAST *Start, *End, *Step, *Body;
1053 public:
1054   ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
1055              ExprAST *step, ExprAST *body)
1056     : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1057   virtual Value *Codegen();
1058 };
1059
1060 /// PrototypeAST - This class represents the "prototype" for a function,
1061 /// which captures its argument names as well as if it is an operator.
1062 class PrototypeAST {
1063   std::string Name;
1064   std::vector&lt;std::string&gt; Args;
1065 public:
1066   PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args)
1067     : Name(name), Args(args) {}
1068
1069   Function *Codegen();
1070 };
1071
1072 /// FunctionAST - This class represents a function definition itself.
1073 class FunctionAST {
1074   PrototypeAST *Proto;
1075   ExprAST *Body;
1076 public:
1077   FunctionAST(PrototypeAST *proto, ExprAST *body)
1078     : Proto(proto), Body(body) {}
1079
1080   Function *Codegen();
1081 };
1082
1083 //===----------------------------------------------------------------------===//
1084 // Parser
1085 //===----------------------------------------------------------------------===//
1086
1087 /// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
1088 /// token the parser it looking at.  getNextToken reads another token from the
1089 /// lexer and updates CurTok with its results.
1090 static int CurTok;
1091 static int getNextToken() {
1092   return CurTok = gettok();
1093 }
1094
1095 /// BinopPrecedence - This holds the precedence for each binary operator that is
1096 /// defined.
1097 static std::map&lt;char, int&gt; BinopPrecedence;
1098
1099 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
1100 static int GetTokPrecedence() {
1101   if (!isascii(CurTok))
1102     return -1;
1103
1104   // Make sure it's a declared binop.
1105   int TokPrec = BinopPrecedence[CurTok];
1106   if (TokPrec &lt;= 0) return -1;
1107   return TokPrec;
1108 }
1109
1110 /// Error* - These are little helper functions for error handling.
1111 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1112 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1113 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1114
1115 static ExprAST *ParseExpression();
1116
1117 /// identifierexpr
1118 ///   ::= identifier
1119 ///   ::= identifier '(' expression* ')'
1120 static ExprAST *ParseIdentifierExpr() {
1121   std::string IdName = IdentifierStr;
1122
1123   getNextToken();  // eat identifier.
1124
1125   if (CurTok != '(') // Simple variable ref.
1126     return new VariableExprAST(IdName);
1127
1128   // Call.
1129   getNextToken();  // eat (
1130   std::vector&lt;ExprAST*&gt; Args;
1131   if (CurTok != ')') {
1132     while (1) {
1133       ExprAST *Arg = ParseExpression();
1134       if (!Arg) return 0;
1135       Args.push_back(Arg);
1136
1137       if (CurTok == ')') break;
1138
1139       if (CurTok != ',')
1140         return Error("Expected ')' or ',' in argument list");
1141       getNextToken();
1142     }
1143   }
1144
1145   // Eat the ')'.
1146   getNextToken();
1147
1148   return new CallExprAST(IdName, Args);
1149 }
1150
1151 /// numberexpr ::= number
1152 static ExprAST *ParseNumberExpr() {
1153   ExprAST *Result = new NumberExprAST(NumVal);
1154   getNextToken(); // consume the number
1155   return Result;
1156 }
1157
1158 /// parenexpr ::= '(' expression ')'
1159 static ExprAST *ParseParenExpr() {
1160   getNextToken();  // eat (.
1161   ExprAST *V = ParseExpression();
1162   if (!V) return 0;
1163
1164   if (CurTok != ')')
1165     return Error("expected ')'");
1166   getNextToken();  // eat ).
1167   return V;
1168 }
1169
1170 /// ifexpr ::= 'if' expression 'then' expression 'else' expression
1171 static ExprAST *ParseIfExpr() {
1172   getNextToken();  // eat the if.
1173
1174   // condition.
1175   ExprAST *Cond = ParseExpression();
1176   if (!Cond) return 0;
1177
1178   if (CurTok != tok_then)
1179     return Error("expected then");
1180   getNextToken();  // eat the then
1181
1182   ExprAST *Then = ParseExpression();
1183   if (Then == 0) return 0;
1184
1185   if (CurTok != tok_else)
1186     return Error("expected else");
1187
1188   getNextToken();
1189
1190   ExprAST *Else = ParseExpression();
1191   if (!Else) return 0;
1192
1193   return new IfExprAST(Cond, Then, Else);
1194 }
1195
1196 /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
1197 static ExprAST *ParseForExpr() {
1198   getNextToken();  // eat the for.
1199
1200   if (CurTok != tok_identifier)
1201     return Error("expected identifier after for");
1202
1203   std::string IdName = IdentifierStr;
1204   getNextToken();  // eat identifier.
1205
1206   if (CurTok != '=')
1207     return Error("expected '=' after for");
1208   getNextToken();  // eat '='.
1209
1210
1211   ExprAST *Start = ParseExpression();
1212   if (Start == 0) return 0;
1213   if (CurTok != ',')
1214     return Error("expected ',' after for start value");
1215   getNextToken();
1216
1217   ExprAST *End = ParseExpression();
1218   if (End == 0) return 0;
1219
1220   // The step value is optional.
1221   ExprAST *Step = 0;
1222   if (CurTok == ',') {
1223     getNextToken();
1224     Step = ParseExpression();
1225     if (Step == 0) return 0;
1226   }
1227
1228   if (CurTok != tok_in)
1229     return Error("expected 'in' after for");
1230   getNextToken();  // eat 'in'.
1231
1232   ExprAST *Body = ParseExpression();
1233   if (Body == 0) return 0;
1234
1235   return new ForExprAST(IdName, Start, End, Step, Body);
1236 }
1237
1238
1239 /// primary
1240 ///   ::= identifierexpr
1241 ///   ::= numberexpr
1242 ///   ::= parenexpr
1243 ///   ::= ifexpr
1244 ///   ::= forexpr
1245 static ExprAST *ParsePrimary() {
1246   switch (CurTok) {
1247   default: return Error("unknown token when expecting an expression");
1248   case tok_identifier: return ParseIdentifierExpr();
1249   case tok_number:     return ParseNumberExpr();
1250   case '(':            return ParseParenExpr();
1251   case tok_if:         return ParseIfExpr();
1252   case tok_for:        return ParseForExpr();
1253   }
1254 }
1255
1256 /// binoprhs
1257 ///   ::= ('+' primary)*
1258 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1259   // If this is a binop, find its precedence.
1260   while (1) {
1261     int TokPrec = GetTokPrecedence();
1262
1263     // If this is a binop that binds at least as tightly as the current binop,
1264     // consume it, otherwise we are done.
1265     if (TokPrec &lt; ExprPrec)
1266       return LHS;
1267
1268     // Okay, we know this is a binop.
1269     int BinOp = CurTok;
1270     getNextToken();  // eat binop
1271
1272     // Parse the primary expression after the binary operator.
1273     ExprAST *RHS = ParsePrimary();
1274     if (!RHS) return 0;
1275
1276     // If BinOp binds less tightly with RHS than the operator after RHS, let
1277     // the pending operator take RHS as its LHS.
1278     int NextPrec = GetTokPrecedence();
1279     if (TokPrec &lt; NextPrec) {
1280       RHS = ParseBinOpRHS(TokPrec+1, RHS);
1281       if (RHS == 0) return 0;
1282     }
1283
1284     // Merge LHS/RHS.
1285     LHS = new BinaryExprAST(BinOp, LHS, RHS);
1286   }
1287 }
1288
1289 /// expression
1290 ///   ::= primary binoprhs
1291 ///
1292 static ExprAST *ParseExpression() {
1293   ExprAST *LHS = ParsePrimary();
1294   if (!LHS) return 0;
1295
1296   return ParseBinOpRHS(0, LHS);
1297 }
1298
1299 /// prototype
1300 ///   ::= id '(' id* ')'
1301 static PrototypeAST *ParsePrototype() {
1302   if (CurTok != tok_identifier)
1303     return ErrorP("Expected function name in prototype");
1304
1305   std::string FnName = IdentifierStr;
1306   getNextToken();
1307
1308   if (CurTok != '(')
1309     return ErrorP("Expected '(' in prototype");
1310
1311   std::vector&lt;std::string&gt; ArgNames;
1312   while (getNextToken() == tok_identifier)
1313     ArgNames.push_back(IdentifierStr);
1314   if (CurTok != ')')
1315     return ErrorP("Expected ')' in prototype");
1316
1317   // success.
1318   getNextToken();  // eat ')'.
1319
1320   return new PrototypeAST(FnName, ArgNames);
1321 }
1322
1323 /// definition ::= 'def' prototype expression
1324 static FunctionAST *ParseDefinition() {
1325   getNextToken();  // eat def.
1326   PrototypeAST *Proto = ParsePrototype();
1327   if (Proto == 0) return 0;
1328
1329   if (ExprAST *E = ParseExpression())
1330     return new FunctionAST(Proto, E);
1331   return 0;
1332 }
1333
1334 /// toplevelexpr ::= expression
1335 static FunctionAST *ParseTopLevelExpr() {
1336   if (ExprAST *E = ParseExpression()) {
1337     // Make an anonymous proto.
1338     PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
1339     return new FunctionAST(Proto, E);
1340   }
1341   return 0;
1342 }
1343
1344 /// external ::= 'extern' prototype
1345 static PrototypeAST *ParseExtern() {
1346   getNextToken();  // eat extern.
1347   return ParsePrototype();
1348 }
1349
1350 //===----------------------------------------------------------------------===//
1351 // Code Generation
1352 //===----------------------------------------------------------------------===//
1353
1354 static Module *TheModule;
1355 static IRBuilder Builder;
1356 static std::map&lt;std::string, Value*&gt; NamedValues;
1357 static FunctionPassManager *TheFPM;
1358
1359 Value *ErrorV(const char *Str) { Error(Str); return 0; }
1360
1361 Value *NumberExprAST::Codegen() {
1362   return ConstantFP::get(Type::DoubleTy, APFloat(Val));
1363 }
1364
1365 Value *VariableExprAST::Codegen() {
1366   // Look this variable up in the function.
1367   Value *V = NamedValues[Name];
1368   return V ? V : ErrorV("Unknown variable name");
1369 }
1370
1371 Value *BinaryExprAST::Codegen() {
1372   Value *L = LHS-&gt;Codegen();
1373   Value *R = RHS-&gt;Codegen();
1374   if (L == 0 || R == 0) return 0;
1375
1376   switch (Op) {
1377   case '+': return Builder.CreateAdd(L, R, "addtmp");
1378   case '-': return Builder.CreateSub(L, R, "subtmp");
1379   case '*': return Builder.CreateMul(L, R, "multmp");
1380   case '&lt;':
1381     L = Builder.CreateFCmpULT(L, R, "cmptmp");
1382     // Convert bool 0/1 to double 0.0 or 1.0
1383     return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
1384   default: return ErrorV("invalid binary operator");
1385   }
1386 }
1387
1388 Value *CallExprAST::Codegen() {
1389   // Look up the name in the global module table.
1390   Function *CalleeF = TheModule-&gt;getFunction(Callee);
1391   if (CalleeF == 0)
1392     return ErrorV("Unknown function referenced");
1393
1394   // If argument mismatch error.
1395   if (CalleeF-&gt;arg_size() != Args.size())
1396     return ErrorV("Incorrect # arguments passed");
1397
1398   std::vector&lt;Value*&gt; ArgsV;
1399   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1400     ArgsV.push_back(Args[i]-&gt;Codegen());
1401     if (ArgsV.back() == 0) return 0;
1402   }
1403
1404   return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1405 }
1406
1407 Value *IfExprAST::Codegen() {
1408   Value *CondV = Cond-&gt;Codegen();
1409   if (CondV == 0) return 0;
1410
1411   // Convert condition to a bool by comparing equal to 0.0.
1412   CondV = Builder.CreateFCmpONE(CondV,
1413                                 ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
1414                                 "ifcond");
1415
1416   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1417
1418   // Create blocks for the then and else cases.  Insert the 'then' block at the
1419   // end of the function.
1420   BasicBlock *ThenBB = new BasicBlock("then", TheFunction);
1421   BasicBlock *ElseBB = new BasicBlock("else");
1422   BasicBlock *MergeBB = new BasicBlock("ifcont");
1423
1424   Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1425
1426   // Emit then value.
1427   Builder.SetInsertPoint(ThenBB);
1428
1429   Value *ThenV = Then-&gt;Codegen();
1430   if (ThenV == 0) return 0;
1431
1432   Builder.CreateBr(MergeBB);
1433   // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1434   ThenBB = Builder.GetInsertBlock();
1435
1436   // Emit else block.
1437   TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
1438   Builder.SetInsertPoint(ElseBB);
1439
1440   Value *ElseV = Else-&gt;Codegen();
1441   if (ElseV == 0) return 0;
1442
1443   Builder.CreateBr(MergeBB);
1444   // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1445   ElseBB = Builder.GetInsertBlock();
1446
1447   // Emit merge block.
1448   TheFunction-&gt;getBasicBlockList().push_back(MergeBB);
1449   Builder.SetInsertPoint(MergeBB);
1450   PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
1451
1452   PN-&gt;addIncoming(ThenV, ThenBB);
1453   PN-&gt;addIncoming(ElseV, ElseBB);
1454   return PN;
1455 }
1456
1457 Value *ForExprAST::Codegen() {
1458   // Output this as:
1459   //   ...
1460   //   start = startexpr
1461   //   goto loop
1462   // loop:
1463   //   variable = phi [start, loopheader], [nextvariable, loopend]
1464   //   ...
1465   //   bodyexpr
1466   //   ...
1467   // loopend:
1468   //   step = stepexpr
1469   //   nextvariable = variable + step
1470   //   endcond = endexpr
1471   //   br endcond, loop, endloop
1472   // outloop:
1473
1474   // Emit the start code first, without 'variable' in scope.
1475   Value *StartVal = Start-&gt;Codegen();
1476   if (StartVal == 0) return 0;
1477
1478   // Make the new basic block for the loop header, inserting after current
1479   // block.
1480   Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1481   BasicBlock *PreheaderBB = Builder.GetInsertBlock();
1482   BasicBlock *LoopBB = new BasicBlock("loop", TheFunction);
1483
1484   // Insert an explicit fall through from the current block to the LoopBB.
1485   Builder.CreateBr(LoopBB);
1486
1487   // Start insertion in LoopBB.
1488   Builder.SetInsertPoint(LoopBB);
1489
1490   // Start the PHI node with an entry for Start.
1491   PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
1492   Variable-&gt;addIncoming(StartVal, PreheaderBB);
1493
1494   // Within the loop, the variable is defined equal to the PHI node.  If it
1495   // shadows an existing variable, we have to restore it, so save it now.
1496   Value *OldVal = NamedValues[VarName];
1497   NamedValues[VarName] = Variable;
1498
1499   // Emit the body of the loop.  This, like any other expr, can change the
1500   // current BB.  Note that we ignore the value computed by the body, but don't
1501   // allow an error.
1502   if (Body-&gt;Codegen() == 0)
1503     return 0;
1504
1505   // Emit the step value.
1506   Value *StepVal;
1507   if (Step) {
1508     StepVal = Step-&gt;Codegen();
1509     if (StepVal == 0) return 0;
1510   } else {
1511     // If not specified, use 1.0.
1512     StepVal = ConstantFP::get(Type::DoubleTy, APFloat(1.0));
1513   }
1514
1515   Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
1516
1517   // Compute the end condition.
1518   Value *EndCond = End-&gt;Codegen();
1519   if (EndCond == 0) return EndCond;
1520
1521   // Convert condition to a bool by comparing equal to 0.0.
1522   EndCond = Builder.CreateFCmpONE(EndCond,
1523                                   ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
1524                                   "loopcond");
1525
1526   // Create the "after loop" block and insert it.
1527   BasicBlock *LoopEndBB = Builder.GetInsertBlock();
1528   BasicBlock *AfterBB = new BasicBlock("afterloop", TheFunction);
1529
1530   // Insert the conditional branch into the end of LoopEndBB.
1531   Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1532
1533   // Any new code will be inserted in AfterBB.
1534   Builder.SetInsertPoint(AfterBB);
1535
1536   // Add a new entry to the PHI node for the backedge.
1537   Variable-&gt;addIncoming(NextVar, LoopEndBB);
1538
1539   // Restore the unshadowed variable.
1540   if (OldVal)
1541     NamedValues[VarName] = OldVal;
1542   else
1543     NamedValues.erase(VarName);
1544
1545
1546   // for expr always returns 0.0.
1547   return Constant::getNullValue(Type::DoubleTy);
1548 }
1549
1550 Function *PrototypeAST::Codegen() {
1551   // Make the function type:  double(double,double) etc.
1552   std::vector&lt;const Type*&gt; Doubles(Args.size(), Type::DoubleTy);
1553   FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
1554
1555   Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
1556
1557   // If F conflicted, there was already something named 'Name'.  If it has a
1558   // body, don't allow redefinition or reextern.
1559   if (F-&gt;getName() != Name) {
1560     // Delete the one we just made and get the existing one.
1561     F-&gt;eraseFromParent();
1562     F = TheModule-&gt;getFunction(Name);
1563
1564     // If F already has a body, reject this.
1565     if (!F-&gt;empty()) {
1566       ErrorF("redefinition of function");
1567       return 0;
1568     }
1569
1570     // If F took a different number of args, reject.
1571     if (F-&gt;arg_size() != Args.size()) {
1572       ErrorF("redefinition of function with different # args");
1573       return 0;
1574     }
1575   }
1576
1577   // Set names for all arguments.
1578   unsigned Idx = 0;
1579   for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1580        ++AI, ++Idx) {
1581     AI-&gt;setName(Args[Idx]);
1582
1583     // Add arguments to variable symbol table.
1584     NamedValues[Args[Idx]] = AI;
1585   }
1586
1587   return F;
1588 }
1589
1590 Function *FunctionAST::Codegen() {
1591   NamedValues.clear();
1592
1593   Function *TheFunction = Proto-&gt;Codegen();
1594   if (TheFunction == 0)
1595     return 0;
1596
1597   // Create a new basic block to start insertion into.
1598   BasicBlock *BB = new BasicBlock("entry", TheFunction);
1599   Builder.SetInsertPoint(BB);
1600
1601   if (Value *RetVal = Body-&gt;Codegen()) {
1602     // Finish off the function.
1603     Builder.CreateRet(RetVal);
1604
1605     // Validate the generated code, checking for consistency.
1606     verifyFunction(*TheFunction);
1607
1608     // Optimize the function.
1609     TheFPM-&gt;run(*TheFunction);
1610
1611     return TheFunction;
1612   }
1613
1614   // Error reading body, remove function.
1615   TheFunction-&gt;eraseFromParent();
1616   return 0;
1617 }
1618
1619 //===----------------------------------------------------------------------===//
1620 // Top-Level parsing and JIT Driver
1621 //===----------------------------------------------------------------------===//
1622
1623 static ExecutionEngine *TheExecutionEngine;
1624
1625 static void HandleDefinition() {
1626   if (FunctionAST *F = ParseDefinition()) {
1627     if (Function *LF = F-&gt;Codegen()) {
1628       fprintf(stderr, "Read function definition:");
1629       LF-&gt;dump();
1630     }
1631   } else {
1632     // Skip token for error recovery.
1633     getNextToken();
1634   }
1635 }
1636
1637 static void HandleExtern() {
1638   if (PrototypeAST *P = ParseExtern()) {
1639     if (Function *F = P-&gt;Codegen()) {
1640       fprintf(stderr, "Read extern: ");
1641       F-&gt;dump();
1642     }
1643   } else {
1644     // Skip token for error recovery.
1645     getNextToken();
1646   }
1647 }
1648
1649 static void HandleTopLevelExpression() {
1650   // Evaluate a top level expression into an anonymous function.
1651   if (FunctionAST *F = ParseTopLevelExpr()) {
1652     if (Function *LF = F-&gt;Codegen()) {
1653       // JIT the function, returning a function pointer.
1654       void *FPtr = TheExecutionEngine-&gt;getPointerToFunction(LF);
1655
1656       // Cast it to the right type (takes no arguments, returns a double) so we
1657       // can call it as a native function.
1658       double (*FP)() = (double (*)())FPtr;
1659       fprintf(stderr, "Evaluated to %f\n", FP());
1660     }
1661   } else {
1662     // Skip token for error recovery.
1663     getNextToken();
1664   }
1665 }
1666
1667 /// top ::= definition | external | expression | ';'
1668 static void MainLoop() {
1669   while (1) {
1670     fprintf(stderr, "ready&gt; ");
1671     switch (CurTok) {
1672     case tok_eof:    return;
1673     case ';':        getNextToken(); break;  // ignore top level semicolons.
1674     case tok_def:    HandleDefinition(); break;
1675     case tok_extern: HandleExtern(); break;
1676     default:         HandleTopLevelExpression(); break;
1677     }
1678   }
1679 }
1680
1681
1682
1683 //===----------------------------------------------------------------------===//
1684 // "Library" functions that can be "extern'd" from user code.
1685 //===----------------------------------------------------------------------===//
1686
1687 /// putchard - putchar that takes a double and returns 0.
1688 extern "C"
1689 double putchard(double X) {
1690   putchar((char)X);
1691   return 0;
1692 }
1693
1694 //===----------------------------------------------------------------------===//
1695 // Main driver code.
1696 //===----------------------------------------------------------------------===//
1697
1698 int main() {
1699   // Install standard binary operators.
1700   // 1 is lowest precedence.
1701   BinopPrecedence['&lt;'] = 10;
1702   BinopPrecedence['+'] = 20;
1703   BinopPrecedence['-'] = 20;
1704   BinopPrecedence['*'] = 40;  // highest.
1705
1706   // Prime the first token.
1707   fprintf(stderr, "ready&gt; ");
1708   getNextToken();
1709
1710   // Make the module, which holds all the code.
1711   TheModule = new Module("my cool jit");
1712
1713   // Create the JIT.
1714   TheExecutionEngine = ExecutionEngine::create(TheModule);
1715
1716   {
1717     ExistingModuleProvider OurModuleProvider(TheModule);
1718     FunctionPassManager OurFPM(&amp;OurModuleProvider);
1719
1720     // Set up the optimizer pipeline.  Start with registering info about how the
1721     // target lays out data structures.
1722     OurFPM.add(new TargetData(*TheExecutionEngine-&gt;getTargetData()));
1723     // Do simple "peephole" optimizations and bit-twiddling optzns.
1724     OurFPM.add(createInstructionCombiningPass());
1725     // Reassociate expressions.
1726     OurFPM.add(createReassociatePass());
1727     // Eliminate Common SubExpressions.
1728     OurFPM.add(createGVNPass());
1729     // Simplify the control flow graph (deleting unreachable blocks, etc).
1730     OurFPM.add(createCFGSimplificationPass());
1731     // Set the global so the code gen can use this.
1732     TheFPM = &amp;OurFPM;
1733
1734     // Run the main "interpreter loop" now.
1735     MainLoop();
1736
1737     TheFPM = 0;
1738
1739     // Print out all of the generated code.
1740     TheModule-&gt;dump();
1741   }  // Free module provider (and thus the module) and pass manager.
1742
1743   return 0;
1744 }
1745 </pre>
1746 </div>
1747
1748 <a href="LangImpl6.html">Next: Extending the language: user-defined operators</a>
1749 </div>
1750
1751 <!-- *********************************************************************** -->
1752 <hr>
1753 <address>
1754   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1755   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1756   <a href="http://validator.w3.org/check/referer"><img
1757   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1758
1759   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1760   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1761   Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
1762 </address>
1763 </body>
1764 </html>