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