docs/tutorial/LangImpl3.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: Implementing code generation to LLVM IR</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: Code generation to LLVM IR</div>
  15
  16 <div class="doc_author">
  17   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
  18 </div>
  19
  20 <!-- *********************************************************************** -->
  21 <div class="doc_section"><a name="intro">Part 3 Introduction</a></div>
  22 <!-- *********************************************************************** -->
  23
  24 <div class="doc_text">
  25
  26 <p>Welcome to part 3 of the "<a href="index.html">Implementing a language with
  27 LLVM</a>" tutorial.  This chapter shows you how to transform the <a
  28 href="LangImpl2.html">Abstract Syntax Tree built in Chapter 2</a> into LLVM IR.
  29 This will teach you a little bit about how LLVM does things, as well as
  30 demonstrate how easy it is to use.  It's much more work to build a lexer and
  31 parser than it is to generate LLVM IR code.
  32 </p>
  33
  34 </div>
  35
  36 <!-- *********************************************************************** -->
  37 <div class="doc_section"><a name="basics">Code Generation setup</a></div>
  38 <!-- *********************************************************************** -->
  39
  40 <div class="doc_text">
  41
  42 <p>
  43 In order to generate LLVM IR, we want some simple setup to get started.  First,
  44 we define virtual codegen methods in each AST class:</p>
  45
  46 <div class="doc_code">
  47 <pre>
  48 /// ExprAST - Base class for all expression nodes.
  49 class ExprAST {
  50 public:
  51   virtual ~ExprAST() {}
  52   virtual Value *Codegen() = 0;
  53 };
  54
  55 /// NumberExprAST - Expression class for numeric literals like "1.0".
  56 class NumberExprAST : public ExprAST {
  57   double Val;
  58 public:
  59   explicit NumberExprAST(double val) : Val(val) {}
  60   virtual Value *Codegen();
  61 };
  62 ...
  63 </pre>
  64 </div>
  65
  66 <p>The Codegen() method says to emit IR for that AST node and all things it
  67 depends on, and they all return an LLVM Value object.
  68 "Value" is the class used to represent a "<a
  69 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single
  70 Assignment (SSA)</a> register" or "SSA value" in LLVM.  The most distinct aspect
  71 of SSA values is that their value is computed as the related instruction
  72 executes, and it does not get a new value until (and if) the instruction
  73 re-executes.  In order words, there is no way to "change" an SSA value.  For
  74 more information, please read up on <a
  75 href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single
  76 Assignment</a> - the concepts are really quite natural once you grok them.</p>
  77
  78 <p>The
  79 second thing we want is an "Error" method like we used for parser, which will
  80 be used to report errors found during code generation (for example, use of an
  81 undeclared parameter):</p>
  82
  83 <div class="doc_code">
  84 <pre>
  85 Value *ErrorV(const char *Str) { Error(Str); return 0; }
  86
  87 static Module *TheModule;
  88 static LLVMBuilder Builder;
  89 static std::map&lt;std::string, Value*&gt; NamedValues;
  90 </pre>
  91 </div>
  92
  93 <p>The static variables will be used during code generation.  <tt>TheModule</tt>
  94 is the LLVM construct that contains all of the functions and global variables in
  95 a chunk of code.  In many ways, it is the top-level structure that the LLVM IR
  96 uses to contain code.</p>
  97
  98 <p>The <tt>Builder</tt> object is a helper object that makes it easy to generate
  99 LLVM instructions.  The <tt>Builder</tt> keeps track of the current place to
 100 insert instructions and has methods to create new instructions.</p>
 101
 102 <p>The <tt>NamedValues</tt> map keeps track of which values are defined in the
 103 current scope and what their LLVM representation is.  In this form of
 104 Kaleidoscope, the only things that can be referenced are function parameters.
 105 As such, function parameters will be in this map when generating code for their
 106 function body.</p>
 107
 108 <p>
 109 With these basics in place, we can start talking about how to generate code for
 110 each expression.  Note that this assumes that the <tt>Builder</tt> has been set
 111 up to generate code <em>into</em> something.  For now, we'll assume that this
 112 has already been done, and we'll just use it to emit code.
 113 </p>
 114
 115 </div>
 116
 117 <!-- *********************************************************************** -->
 118 <div class="doc_section"><a name="exprs">Expression Code Generation</a></div>
 119 <!-- *********************************************************************** -->
 120
 121 <div class="doc_text">
 122
 123 <p>Generating LLVM code for expression nodes is very straight-forward: less
 124 than 45 lines of commented code for all four of our expression nodes.  First,
 125 we'll do numeric literals:</p>
 126
 127 <div class="doc_code">
 128 <pre>
 129 Value *NumberExprAST::Codegen() {
 130   return ConstantFP::get(Type::DoubleTy, APFloat(Val));
 131 }
 132 </pre>
 133 </div>
 134
 135 <p>In the LLVM IR, numeric constants are represented with the
 136 <tt>ConstantFP</tt> class, which holds the numeric value in an <tt>APFloat</tt>
 137 internally (<tt>APFloat</tt> has the capability of holding floating point
 138 constants of <em>A</em>rbitrary <em>P</em>recision).  This code basically just
 139 creates and returns a <tt>ConstantFP</tt>.  Note that in the LLVM IR
 140 that constants are all uniqued together and shared.  For this reason, the API
 141 uses "the foo::get(..)" idiom instead of "new foo(..)" or "foo::create(..).</p>
 142
 143 <div class="doc_code">
 144 <pre>
 145 Value *VariableExprAST::Codegen() {
 146   // Look this variable up in the function.
 147   Value *V = NamedValues[Name];
 148   return V ? V : ErrorV("Unknown variable name");
 149 }
 150 </pre>
 151 </div>
 152
 153 <p>References to variables is also quite simple here.  In the simple version
 154 of Kaleidoscope, we assume that the variable has already been emited somewhere
 155 and its value is available.  In practice, the only values that can be in the
 156 <tt>NamedValues</tt> map are function arguments.  This
 157 code simply checks to see that the specified name is in the map (if not, an
 158 unknown variable is being referenced) and returns the value for it.</p>
 159
 160 <div class="doc_code">
 161 <pre>
 162 Value *BinaryExprAST::Codegen() {
 163   Value *L = LHS-&gt;Codegen();
 164   Value *R = RHS-&gt;Codegen();
 165   if (L == 0 || R == 0) return 0;
 166
 167   switch (Op) {
 168   case '+': return Builder.CreateAdd(L, R, "addtmp");
 169   case '-': return Builder.CreateSub(L, R, "subtmp");
 170   case '*': return Builder.CreateMul(L, R, "multmp");
 171   case '&lt;':
 172     L = Builder.CreateFCmpULT(L, R, "multmp");
 173     // Convert bool 0/1 to double 0.0 or 1.0
 174     return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
 175   default: return ErrorV("invalid binary operator");
 176   }
 177 }
 178 </pre>
 179 </div>
 180
 181 <p>Binary operators start to get more interesting.  The basic idea here is that
 182 we recursively emit code for the left-hand side of the expression, then the
 183 right-hand side, then we compute the result of the binary expression.  In this
 184 code, we do a simple switch on the opcode to create the right LLVM instruction.
 185 </p>
 186
 187 <p>In this example, the LLVM builder class is starting to show its value.
 188 Because it knows where to insert the newly created instruction, you just have to
 189 specificy what instruction to create (e.g. with <tt>CreateAdd</tt>), which
 190 operands to use (<tt>L</tt> and <tt>R</tt> here) and optionally provide a name
 191 for the generated instruction.  One nice thing about LLVM is that the name is
 192 just a hint: if there are multiple additions in a single function, the first
 193 will be named "addtmp" and the second will be "autorenamed" by adding a suffix,
 194 giving it a name like "addtmp42".  Local value names for instructions are purely
 195 optional, but it makes it much easier to read the IR dumps.</p>
 196
 197 <p><a href="../LangRef.html#instref">LLVM instructions</a> are constrained to
 198 have very strict type properties: for example, the Left and Right operators of
 199 an <a href="../LangRef.html#i_add">add instruction</a> have to have the same
 200 type, and that the result of the add matches the operands.  Because all values
 201 in Kaleidoscope are doubles, this makes for very simple code for add, sub and
 202 mul.</p>
 203
 204 <p>On the other hand, LLVM specifies that the <a
 205 href="../LangRef.html#i_fcmp">fcmp instruction</a> always returns an 'i1' value
 206 (a one bit integer).  However, Kaleidoscope wants the value to be a 0.0 or 1.0
 207 value.  In order to get these semantics, we combine the fcmp instruction with
 208 a <a href="../LangRef.html#i_uitofp">uitofp instruction</a>.  This instruction
 209 converts its input integer into a floating point value by treating the input
 210 as an unsigned value.  In contrast, if we used the <a
 211 href="../LangRef.html#i_sitofp">sitofp instruction</a>, the Kaleidoscope '<'
 212 operator would return 0.0 and -1.0, depending on the input value.</p>
 213
 214 <div class="doc_code">
 215 <pre>
 216 Value *CallExprAST::Codegen() {
 217   // Look up the name in the global module table.
 218   Function *CalleeF = TheModule-&gt;getFunction(Callee);
 219   if (CalleeF == 0)
 220     return ErrorV("Unknown function referenced");
 221
 222   // If argument mismatch error.
 223   if (CalleeF-&gt;arg_size() != Args.size())
 224     return ErrorV("Incorrect # arguments passed");
 225
 226   std::vector&lt;Value*&gt; ArgsV;
 227   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 228     ArgsV.push_back(Args[i]-&gt;Codegen());
 229     if (ArgsV.back() == 0) return 0;
 230   }
 231
 232   return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
 233 }
 234 </pre>
 235 </div>
 236
 237 <p>Code generation for function calls is quite straight-forward with LLVM.  The
 238 code above first looks the name of the function up in the LLVM Module's symbol
 239 table.  Recall that the LLVM Module is the container that holds all of the
 240 functions we are JIT'ing.  By giving each function the same name as what the
 241 user specifies, we can use the LLVM symbol table to resolve function names for
 242 us.</p>
 243
 244 <p>Once we have the function to call, we recursively codegen each argument that
 245 is to be passed in, and create an LLVM <a href="../LangRef.html#i_call">call
 246 instruction</a>.  Note that LLVM uses the native C calling conventions by
 247 default, allowing these calls to call into standard library functions like
 248 "sin" and "cos" with no additional effort.</p>
 249
 250 <p>This wraps up our handling of the four basic expressions that we have so far
 251 in Kaleidoscope.  Feel free to go in and add some more.  For example, by
 252 browsing the <a href="../LangRef.html">LLVM language reference</a> you'll find
 253 several other interesting instructions that are really easy to plug into our
 254 basic framework.</p>
 255
 256 </div>
 257
 258 <!-- *********************************************************************** -->
 259 <div class="doc_section"><a name="code">Conclusions and the Full Code</a></div>
 260 <!-- *********************************************************************** -->
 261
 262 <div class="doc_text">
 263
 264 <div class="doc_code">
 265 <pre>
 266 // To build this:
 267 //  g++ -g toy.cpp `llvm-config --cppflags` `llvm-config --ldflags` \
 268 //                `llvm-config --libs core` -I ~/llvm/include/
 269 //  ./a.out
 270 // See example below.
 271
 272 #include "llvm/DerivedTypes.h"
 273 #include "llvm/Module.h"
 274 #include "llvm/Support/LLVMBuilder.h"
 275 #include &lt;cstdio&gt;
 276 #include &lt;string&gt;
 277 #include &lt;map&gt;
 278 #include &lt;vector&gt;
 279 using namespace llvm;
 280
 281 //===----------------------------------------------------------------------===//
 282 // Lexer
 283 //===----------------------------------------------------------------------===//
 284
 285 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
 286 // of these for known things.
 287 enum Token {
 288   tok_eof = -1,
 289
 290   // commands
 291   tok_def = -2, tok_extern = -3,
 292
 293   // primary
 294   tok_identifier = -4, tok_number = -5,
 295 };
 296
 297 static std::string IdentifierStr;  // Filled in if tok_identifier
 298 static double NumVal;              // Filled in if tok_number
 299
 300 /// gettok - Return the next token from standard input.
 301 static int gettok() {
 302   static int LastChar = ' ';
 303
 304   // Skip any whitespace.
 305   while (isspace(LastChar))
 306     LastChar = getchar();
 307
 308   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
 309     IdentifierStr = LastChar;
 310     while (isalnum((LastChar = getchar())))
 311       IdentifierStr += LastChar;
 312
 313     if (IdentifierStr == "def") return tok_def;
 314     if (IdentifierStr == "extern") return tok_extern;
 315     return tok_identifier;
 316   }
 317
 318   if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
 319     std::string NumStr;
 320     do {
 321       NumStr += LastChar;
 322       LastChar = getchar();
 323     } while (isdigit(LastChar) || LastChar == '.');
 324
 325     NumVal = strtod(NumStr.c_str(), 0);
 326     return tok_number;
 327   }
 328
 329   if (LastChar == '#') {
 330     // Comment until end of line.
 331     do LastChar = getchar();
 332     while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp; LastChar != '\r');
 333
 334     if (LastChar != EOF)
 335       return gettok();
 336   }
 337
 338   // Check for end of file.  Don't eat the EOF.
 339   if (LastChar == EOF)
 340     return tok_eof;
 341
 342   // Otherwise, just return the character as its ascii value.
 343   int ThisChar = LastChar;
 344   LastChar = getchar();
 345   return ThisChar;
 346 }
 347
 348 //===----------------------------------------------------------------------===//
 349 // Abstract Syntax Tree (aka Parse Tree)
 350 //===----------------------------------------------------------------------===//
 351
 352 /// ExprAST - Base class for all expression nodes.
 353 class ExprAST {
 354 public:
 355   virtual ~ExprAST() {}
 356   virtual Value *Codegen() = 0;
 357 };
 358
 359 /// NumberExprAST - Expression class for numeric literals like "1.0".
 360 class NumberExprAST : public ExprAST {
 361   double Val;
 362 public:
 363   explicit NumberExprAST(double val) : Val(val) {}
 364   virtual Value *Codegen();
 365 };
 366
 367 /// VariableExprAST - Expression class for referencing a variable, like "a".
 368 class VariableExprAST : public ExprAST {
 369   std::string Name;
 370 public:
 371   explicit VariableExprAST(const std::string &amp;name) : Name(name) {}
 372   virtual Value *Codegen();
 373 };
 374
 375 /// BinaryExprAST - Expression class for a binary operator.
 376 class BinaryExprAST : public ExprAST {
 377   char Op;
 378   ExprAST *LHS, *RHS;
 379 public:
 380   BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
 381     : Op(op), LHS(lhs), RHS(rhs) {}
 382   virtual Value *Codegen();
 383 };
 384
 385 /// CallExprAST - Expression class for function calls.
 386 class CallExprAST : public ExprAST {
 387   std::string Callee;
 388   std::vector&lt;ExprAST*&gt; Args;
 389 public:
 390   CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
 391     : Callee(callee), Args(args) {}
 392   virtual Value *Codegen();
 393 };
 394
 395 /// PrototypeAST - This class represents the "prototype" for a function,
 396 /// which captures its argument names as well as if it is an operator.
 397 class PrototypeAST {
 398   std::string Name;
 399   std::vector&lt;std::string&gt; Args;
 400 public:
 401   PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args)
 402     : Name(name), Args(args) {}
 403
 404   Function *Codegen();
 405 };
 406
 407 /// FunctionAST - This class represents a function definition itself.
 408 class FunctionAST {
 409   PrototypeAST *Proto;
 410   ExprAST *Body;
 411 public:
 412   FunctionAST(PrototypeAST *proto, ExprAST *body)
 413     : Proto(proto), Body(body) {}
 414
 415   Function *Codegen();
 416 };
 417
 418 //===----------------------------------------------------------------------===//
 419 // Parser
 420 //===----------------------------------------------------------------------===//
 421
 422 /// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
 423 /// token the parser it looking at.  getNextToken reads another token from the
 424 /// lexer and updates CurTok with its results.
 425 static int CurTok;
 426 static int getNextToken() {
 427   return CurTok = gettok();
 428 }
 429
 430 /// BinopPrecedence - This holds the precedence for each binary operator that is
 431 /// defined.
 432 static std::map&lt;char, int&gt; BinopPrecedence;
 433
 434 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
 435 static int GetTokPrecedence() {
 436   if (!isascii(CurTok))
 437     return -1;
 438
 439   // Make sure it's a declared binop.
 440   int TokPrec = BinopPrecedence[CurTok];
 441   if (TokPrec &lt;= 0) return -1;
 442   return TokPrec;
 443 }
 444
 445 /// Error* - These are little helper functions for error handling.
 446 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
 447 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
 448 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
 449
 450 static ExprAST *ParseExpression();
 451
 452 /// identifierexpr
 453 ///   ::= identifer
 454 ///   ::= identifer '(' expression* ')'
 455 static ExprAST *ParseIdentifierExpr() {
 456   std::string IdName = IdentifierStr;
 457
 458   getNextToken();  // eat identifer.
 459
 460   if (CurTok != '(') // Simple variable ref.
 461     return new VariableExprAST(IdName);
 462
 463   // Call.
 464   getNextToken();  // eat (
 465   std::vector&lt;ExprAST*&gt; Args;
 466   while (1) {
 467     ExprAST *Arg = ParseExpression();
 468     if (!Arg) return 0;
 469     Args.push_back(Arg);
 470
 471     if (CurTok == ')') break;
 472
 473     if (CurTok != ',')
 474       return Error("Expected ')'");
 475     getNextToken();
 476   }
 477
 478   // Eat the ')'.
 479   getNextToken();
 480
 481   return new CallExprAST(IdName, Args);
 482 }
 483
 484 /// numberexpr ::= number
 485 static ExprAST *ParseNumberExpr() {
 486   ExprAST *Result = new NumberExprAST(NumVal);
 487   getNextToken(); // consume the number
 488   return Result;
 489 }
 490
 491 /// parenexpr ::= '(' expression ')'
 492 static ExprAST *ParseParenExpr() {
 493   getNextToken();  // eat (.
 494   ExprAST *V = ParseExpression();
 495   if (!V) return 0;
 496
 497   if (CurTok != ')')
 498     return Error("expected ')'");
 499   getNextToken();  // eat ).
 500   return V;
 501 }
 502
 503 /// primary
 504 ///   ::= identifierexpr
 505 ///   ::= numberexpr
 506 ///   ::= parenexpr
 507 static ExprAST *ParsePrimary() {
 508   switch (CurTok) {
 509   default: return Error("unknown token when expecting an expression");
 510   case tok_identifier: return ParseIdentifierExpr();
 511   case tok_number:     return ParseNumberExpr();
 512   case '(':            return ParseParenExpr();
 513   }
 514 }
 515
 516 /// binoprhs
 517 ///   ::= ('+' primary)*
 518 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
 519   // If this is a binop, find its precedence.
 520   while (1) {
 521     int TokPrec = GetTokPrecedence();
 522
 523     // If this is a binop that binds at least as tightly as the current binop,
 524     // consume it, otherwise we are done.
 525     if (TokPrec &lt; ExprPrec)
 526       return LHS;
 527
 528     // Okay, we know this is a binop.
 529     int BinOp = CurTok;
 530     getNextToken();  // eat binop
 531
 532     // Parse the primary expression after the binary operator.
 533     ExprAST *RHS = ParsePrimary();
 534     if (!RHS) return 0;
 535
 536     // If BinOp binds less tightly with RHS than the operator after RHS, let
 537     // the pending operator take RHS as its LHS.
 538     int NextPrec = GetTokPrecedence();
 539     if (TokPrec &lt; NextPrec) {
 540       RHS = ParseBinOpRHS(TokPrec+1, RHS);
 541       if (RHS == 0) return 0;
 542     }
 543
 544     // Merge LHS/RHS.
 545     LHS = new BinaryExprAST(BinOp, LHS, RHS);
 546   }
 547 }
 548
 549 /// expression
 550 ///   ::= primary binoprhs
 551 ///
 552 static ExprAST *ParseExpression() {
 553   ExprAST *LHS = ParsePrimary();
 554   if (!LHS) return 0;
 555
 556   return ParseBinOpRHS(0, LHS);
 557 }
 558
 559 /// prototype
 560 ///   ::= id '(' id* ')'
 561 static PrototypeAST *ParsePrototype() {
 562   if (CurTok != tok_identifier)
 563     return ErrorP("Expected function name in prototype");
 564
 565   std::string FnName = IdentifierStr;
 566   getNextToken();
 567
 568   if (CurTok != '(')
 569     return ErrorP("Expected '(' in prototype");
 570
 571   std::vector&lt;std::string&gt; ArgNames;
 572   while (getNextToken() == tok_identifier)
 573     ArgNames.push_back(IdentifierStr);
 574   if (CurTok != ')')
 575     return ErrorP("Expected ')' in prototype");
 576
 577   // success.
 578   getNextToken();  // eat ')'.
 579
 580   return new PrototypeAST(FnName, ArgNames);
 581 }
 582
 583 /// definition ::= 'def' prototype expression
 584 static FunctionAST *ParseDefinition() {
 585   getNextToken();  // eat def.
 586   PrototypeAST *Proto = ParsePrototype();
 587   if (Proto == 0) return 0;
 588
 589   if (ExprAST *E = ParseExpression())
 590     return new FunctionAST(Proto, E);
 591   return 0;
 592 }
 593
 594 /// toplevelexpr ::= expression
 595 static FunctionAST *ParseTopLevelExpr() {
 596   if (ExprAST *E = ParseExpression()) {
 597     // Make an anonymous proto.
 598     PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
 599     return new FunctionAST(Proto, E);
 600   }
 601   return 0;
 602 }
 603
 604 /// external ::= 'extern' prototype
 605 static PrototypeAST *ParseExtern() {
 606   getNextToken();  // eat extern.
 607   return ParsePrototype();
 608 }
 609
 610 //===----------------------------------------------------------------------===//
 611 // Code Generation
 612 //===----------------------------------------------------------------------===//
 613
 614 static Module *TheModule;
 615 static LLVMBuilder Builder;
 616 static std::map&lt;std::string, Value*&gt; NamedValues;
 617
 618 Value *ErrorV(const char *Str) { Error(Str); return 0; }
 619
 620 Value *NumberExprAST::Codegen() {
 621   return ConstantFP::get(Type::DoubleTy, APFloat(Val));
 622 }
 623
 624 Value *VariableExprAST::Codegen() {
 625   // Look this variable up in the function.
 626   Value *V = NamedValues[Name];
 627   return V ? V : ErrorV("Unknown variable name");
 628 }
 629
 630 Value *BinaryExprAST::Codegen() {
 631   Value *L = LHS-&gt;Codegen();
 632   Value *R = RHS-&gt;Codegen();
 633   if (L == 0 || R == 0) return 0;
 634
 635   switch (Op) {
 636   case '+': return Builder.CreateAdd(L, R, "addtmp");
 637   case '-': return Builder.CreateSub(L, R, "subtmp");
 638   case '*': return Builder.CreateMul(L, R, "multmp");
 639   case '&lt;':
 640     L = Builder.CreateFCmpULT(L, R, "multmp");
 641     // Convert bool 0/1 to double 0.0 or 1.0
 642     return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
 643   default: return ErrorV("invalid binary operator");
 644   }
 645 }
 646
 647 Value *CallExprAST::Codegen() {
 648   // Look up the name in the global module table.
 649   Function *CalleeF = TheModule-&gt;getFunction(Callee);
 650   if (CalleeF == 0)
 651     return ErrorV("Unknown function referenced");
 652
 653   // If argument mismatch error.
 654   if (CalleeF-&gt;arg_size() != Args.size())
 655     return ErrorV("Incorrect # arguments passed");
 656
 657   std::vector&lt;Value*&gt; ArgsV;
 658   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 659     ArgsV.push_back(Args[i]-&gt;Codegen());
 660     if (ArgsV.back() == 0) return 0;
 661   }
 662
 663   return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
 664 }
 665
 666 Function *PrototypeAST::Codegen() {
 667   // Make the function type:  double(double,double) etc.
 668   FunctionType *FT =
 669     FunctionType::get(Type::DoubleTy, std::vector&lt;const Type*&gt;(Args.size(),
 670                                                                Type::DoubleTy),
 671                       false);
 672
 673   Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
 674
 675   // If F conflicted, there was already something named 'Name'.  If it has a
 676   // body, don't allow redefinition or reextern.
 677   if (F-&gt;getName() != Name) {
 678     // Delete the one we just made and get the existing one.
 679     F-&gt;eraseFromParent();
 680     F = TheModule-&gt;getFunction(Name);
 681
 682     // If F already has a body, reject this.
 683     if (!F-&gt;empty()) {
 684       ErrorF("redefinition of function");
 685       return 0;
 686     }
 687
 688     // If F took a different number of args, reject.
 689     if (F-&gt;arg_size() != Args.size()) {
 690       ErrorF("redefinition of function with different # args");
 691       return 0;
 692     }
 693   }
 694
 695   // Set names for all arguments.
 696   unsigned Idx = 0;
 697   for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
 698        ++AI, ++Idx) {
 699     AI-&gt;setName(Args[Idx]);
 700
 701     // Add arguments to variable symbol table.
 702     NamedValues[Args[Idx]] = AI;
 703   }
 704
 705   return F;
 706 }
 707
 708 Function *FunctionAST::Codegen() {
 709   NamedValues.clear();
 710
 711   Function *TheFunction = Proto-&gt;Codegen();
 712   if (TheFunction == 0)
 713     return 0;
 714
 715   // Create a new basic block to start insertion into.
 716   Builder.SetInsertPoint(new BasicBlock("entry", TheFunction));
 717
 718   if (Value *RetVal = Body-&gt;Codegen()) {
 719     // Finish off the function.
 720     Builder.CreateRet(RetVal);
 721     return TheFunction;
 722   }
 723
 724   // Error reading body, remove function.
 725   TheFunction-&gt;eraseFromParent();
 726   return 0;
 727 }
 728
 729 //===----------------------------------------------------------------------===//
 730 // Top-Level parsing and JIT Driver
 731 //===----------------------------------------------------------------------===//
 732
 733 static void HandleDefinition() {
 734   if (FunctionAST *F = ParseDefinition()) {
 735     if (Function *LF = F-&gt;Codegen()) {
 736       fprintf(stderr, "Read function definition:");
 737       LF-&gt;dump();
 738     }
 739   } else {
 740     // Skip token for error recovery.
 741     getNextToken();
 742   }
 743 }
 744
 745 static void HandleExtern() {
 746   if (PrototypeAST *P = ParseExtern()) {
 747     if (Function *F = P-&gt;Codegen()) {
 748       fprintf(stderr, "Read extern: ");
 749       F-&gt;dump();
 750     }
 751   } else {
 752     // Skip token for error recovery.
 753     getNextToken();
 754   }
 755 }
 756
 757 static void HandleTopLevelExpression() {
 758   // Evaluate a top level expression into an anonymous function.
 759   if (FunctionAST *F = ParseTopLevelExpr()) {
 760     if (Function *LF = F-&gt;Codegen()) {
 761       fprintf(stderr, "Read top-level expression:");
 762       LF-&gt;dump();
 763     }
 764   } else {
 765     // Skip token for error recovery.
 766     getNextToken();
 767   }
 768 }
 769
 770 /// top ::= definition | external | expression | ';'
 771 static void MainLoop() {
 772   while (1) {
 773     fprintf(stderr, "ready&gt; ");
 774     switch (CurTok) {
 775     case tok_eof:    return;
 776     case ';':        getNextToken(); break;  // ignore top level semicolons.
 777     case tok_def:    HandleDefinition(); break;
 778     case tok_extern: HandleExtern(); break;
 779     default:         HandleTopLevelExpression(); break;
 780     }
 781   }
 782 }
 783
 784
 785
 786 //===----------------------------------------------------------------------===//
 787 // "Library" functions that can be "extern'd" from user code.
 788 //===----------------------------------------------------------------------===//
 789
 790 /// putchard - putchar that takes a double and returns 0.
 791 extern "C"
 792 double putchard(double X) {
 793   putchar((char)X);
 794   return 0;
 795 }
 796
 797 //===----------------------------------------------------------------------===//
 798 // Main driver code.
 799 //===----------------------------------------------------------------------===//
 800
 801 int main() {
 802   TheModule = new Module("my cool jit");
 803
 804   // Install standard binary operators.
 805   // 1 is lowest precedence.
 806   BinopPrecedence['&lt;'] = 10;
 807   BinopPrecedence['+'] = 20;
 808   BinopPrecedence['-'] = 20;
 809   BinopPrecedence['*'] = 40;  // highest.
 810
 811   // Prime the first token.
 812   fprintf(stderr, "ready&gt; ");
 813   getNextToken();
 814
 815   MainLoop();
 816   TheModule-&gt;dump();
 817   return 0;
 818 }
 819
 820 /* Examples:
 821
 822 def fib(x)
 823   if (x &lt; 3) then
 824     1
 825   else
 826     fib(x-1)+fib(x-2);
 827
 828 fib(10);
 829
 830 */
 831 </pre>
 832 </div>
 833 </div>
 834
 835 <!-- *********************************************************************** -->
 836 <hr>
 837 <address>
 838   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 839   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
 840   <a href="http://validator.w3.org/check/referer"><img
 841   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
 842
 843   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
 844   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
 845   Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
 846 </address>
 847 </body>
 848 </html>