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="funcs">Function Code Generation</a></div>
 260 <!-- *********************************************************************** -->
 261
 262 <div class="doc_text">
 263
 264 <p>Code generation for prototypes and functions has to handle a number of
 265 details, which make their code less beautiful and elegant than expression code
 266 generation, but they illustrate some important points.  First, lets talk about
 267 code generation for prototypes: this is used both for function bodies as well
 268 as external function declarations.  The code starts with:</p>
 269
 270 <div class="doc_code">
 271 <pre>
 272 Function *PrototypeAST::Codegen() {
 273   // Make the function type:  double(double,double) etc.
 274   std::vector&lt;const Type*&gt; Doubles(Args.size(), Type::DoubleTy);
 275   FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
 276
 277   Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
 278 </pre>
 279 </div>
 280
 281 <p>This code packs a lot of power into a few lines.  The first step is to create
 282 the <tt>FunctionType</tt> that should be used for a given Prototype.  Since all
 283 function arguments in Kaleidoscope are of type double, the first line creates
 284 a vector of "N" LLVM Double types.  It then uses the <tt>FunctionType::get</tt>
 285 method to create a function type that takes "N" doubles as arguments, returns
 286 one double as a result, and that is not vararg (the false parameter indicates
 287 this).  Note that Types in LLVM are uniqued just like Constants are, so you
 288 don't "new" a type, you "get" it.</p>
 289
 290 <p>The final line above actually creates the function that the prototype will
 291 correspond to.  This indicates which type, linkage, and name to use, and which
 292 module to insert into.  "<a href="LangRef.html#linkage">external linkage</a>"
 293 means that the function may be defined outside the current module and/or that it
 294 is callable by functions outside the module.  The Name passed in is the name the
 295 user specified: since "<tt>TheModule</tt>" is specified, this name is registered
 296 in "<tt>TheModule</tt>"s symbol table, which is used by the function call code
 297 above.</p>
 298
 299 <div class="doc_code">
 300 <pre>
 301   // If F conflicted, there was already something named 'Name'.  If it has a
 302   // body, don't allow redefinition or reextern.
 303   if (F-&gt;getName() != Name) {
 304     // Delete the one we just made and get the existing one.
 305     F-&gt;eraseFromParent();
 306     F = TheModule-&gt;getFunction(Name);
 307 </pre>
 308 </div>
 309
 310 <p>The Module symbol table works just like the Function symbol table when it
 311 comes to name conflicts: if a new function is created with a name was previously
 312 added to the symbol table, it will get implicitly renamed when added to the
 313 Module.  The code above exploits this fact to tell if there was a previous
 314 definition of this function.</p>
 315
 316 <p>In Kaleidoscope, I choose to allow redefinitions of functions in two cases:
 317 first, we want to allow 'extern'ing a function more than once, so long as the
 318 prototypes for the externs match (since all arguments have the same type, we
 319 just have to check that the number of arguments match).  Second, we want to
 320 allow 'extern'ing a function and then definining a body for it.  This is useful
 321 when defining mutually recursive functions.</p>
 322
 323 <p>In order to implement this, the code above first checks to see if there is
 324 a collision on the name of the function.  If so, it deletes the function we just
 325 created (by calling <tt>eraseFromParent</tt>) and then calling
 326 <tt>getFunction</tt> to get the existing function with the specified name.  Note
 327 that many APIs in LLVM have "erase" forms and "remove" forms.  The "remove" form
 328 unlinks the object from its parent (e.g. a Function from a Module) and returns
 329 it.  The "erase" form unlinks the object and then deletes it.</p>
 330
 331 <div class="doc_code">
 332 <pre>
 333     // If F already has a body, reject this.
 334     if (!F-&gt;empty()) {
 335       ErrorF("redefinition of function");
 336       return 0;
 337     }
 338
 339     // If F took a different number of args, reject.
 340     if (F-&gt;arg_size() != Args.size()) {
 341       ErrorF("redefinition of function with different # args");
 342       return 0;
 343     }
 344   }
 345 </pre>
 346 </div>
 347
 348 <p>In order to verify the logic above, we first check to see if the preexisting
 349 function is "empty".  In this case, empty means that it has no basic blocks in
 350 it, which means it has no body.  If it has no body, this means its a forward
 351 declaration.  Since we don't allow anything after a full definition of the
 352 function, the code rejects this case.  If the previous reference to a function
 353 was an 'extern', we simply verify that the number of arguments for that
 354 definition and this one match up.  If not, we emit an error.</p>
 355
 356 <div class="doc_code">
 357 <pre>
 358   // Set names for all arguments.
 359   unsigned Idx = 0;
 360   for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
 361        ++AI, ++Idx) {
 362     AI-&gt;setName(Args[Idx]);
 363
 364     // Add arguments to variable symbol table.
 365     NamedValues[Args[Idx]] = AI;
 366   }
 367   return F;
 368 }
 369 </pre>
 370 </div>
 371
 372 <p>The last bit of code for prototypes loops over all of the arguments in the
 373 function, setting the name of the LLVM Argument objects to match and registering
 374 the arguments in the <tt>NamedValues</tt> map for future use by the
 375 <tt>VariableExprAST</tt> AST node.  Once this is set up, it returns the Function
 376 object to the caller.  Note that we don't check for conflicting
 377 argument names here (e.g. "extern foo(a b a)").  Doing so would be very
 378 straight-forward.</p>
 379
 380 <div class="doc_code">
 381 <pre>
 382 Function *FunctionAST::Codegen() {
 383   NamedValues.clear();
 384
 385   Function *TheFunction = Proto-&gt;Codegen();
 386   if (TheFunction == 0)
 387     return 0;
 388 </pre>
 389 </div>
 390
 391 <p>Code generation for function definitions starts out simply enough: first we
 392 codegen the prototype and verify that it is ok.  We also clear out the
 393 <tt>NamedValues</tt> map to make sure that there isn't anything in it from the
 394 last function we compiled.</p>
 395
 396 <div class="doc_code">
 397 <pre>
 398   // Create a new basic block to start insertion into.
 399   BasicBlock *BB = new BasicBlock("entry", TheFunction);
 400   Builder.SetInsertPoint(BB);
 401
 402   if (Value *RetVal = Body-&gt;Codegen()) {
 403 </pre>
 404 </div>
 405
 406 <p>Now we get to the point where the <tt>Builder</tt> is set up.  The first
 407 line creates a new <a href="http://en.wikipedia.org/wiki/Basic_block">basic
 408 block</a> (named "entry"), which is inserted into <tt>TheFunction</tt>.  The
 409 second line then tells the builder that new instructions should be inserted into
 410 the end of the new basic block.  Basic blocks in LLVM are an important part
 411 of functions that define the <a
 412 href="http://en.wikipedia.org/wiki/Control_flow_graph">Control Flow Graph</a>.
 413 Since we don't have any control flow, our functions will only contain one
 414 block so far.  We'll fix this in a future installment :).</p>
 415
 416 <div class="doc_code">
 417 <pre>
 418   if (Value *RetVal = Body-&gt;Codegen()) {
 419     // Finish off the function.
 420     Builder.CreateRet(RetVal);
 421
 422     // Validate the generated code, checking for consistency.
 423     verifyFunction(*TheFunction);
 424     return TheFunction;
 425   }
 426 </pre>
 427 </div>
 428
 429 <p>Once the insertion point is set up, we call the <tt>CodeGen()</tt> method for
 430 the root expression of the function.  If no error happens, this emits code to
 431 compute the expression into the entry block and returns the value that was
 432 computed.  Assuming no error, we then create an LLVM <a
 433 href="../LangRef.html#i_ret">ret instruction</a>, which completes the function.
 434 Once the function is built, we call the <tt>verifyFunction</tt> function, which
 435 is provided by LLVM.  This function does a variety of consistency checks on the
 436 generated code, to determine if our compiler is doing everything right.  Using
 437 this is important: it can catch a lot of bugs.  Once the function is finished
 438 and validated, we return it.</p>
 439
 440 <div class="doc_code">
 441 <pre>
 442   // Error reading body, remove function.
 443   TheFunction-&gt;eraseFromParent();
 444   return 0;
 445 }
 446 </pre>
 447 </div>
 448
 449 <p>The only piece left here is handling of the error case.  For simplicity, we
 450 simply handle this by deleting the function we produced with the
 451 <tt>eraseFromParent</tt> method.  This allows the user to redefine a function
 452 that they incorrectly typed in before: if we didn't delete it, it would live in
 453 the symbol table, with a body, preventing future redefinition.</p>
 454
 455 <p>This code does have a bug though.  Since the <tt>PrototypeAST::Codegen</tt>
 456 can return a previously defined forward declaration, this can actually delete
 457 a forward declaration.  There are a number of ways to fix this bug, see what you
 458 can come up with!  Here is a testcase:</p>
 459
 460 <div class="doc_code">
 461 <pre>
 462 extern foo(a b);     # ok, defines foo.
 463 def foo(a b) c;      # error, 'c' is invalid.
 464 def bar() foo(1, 2); # error, unknown function "foo"
 465 </pre>
 466 </div>
 467
 468 </div>
 469
 470 <!-- *********************************************************************** -->
 471 <div class="doc_section"><a name="driver">Driver Changes and
 472 Closing Thoughts</a></div>
 473 <!-- *********************************************************************** -->
 474
 475 <div class="doc_text">
 476
 477 <p>
 478 For now, code generation to LLVM doesn't really get us much, except that we can
 479 look at the pretty IR calls.  The sample code inserts calls to Codegen into the
 480 "<tt>HandleDefinition</tt>", "<tt>HandleExtern</tt>" etc functions, and then
 481 dumps out the LLVM IR.  This gives a nice way to look at the LLVM IR for simple
 482 functions.  For example:
 483 </p>
 484
 485 <div class="doc_code">
 486 <pre>
 487 ready> <b>4+5</b>;
 488 ready> Read top-level expression:
 489 define double @""() {
 490 entry:
 491         %addtmp = add double 4.000000e+00, 5.000000e+00
 492         ret double %addtmp
 493 }
 494 </pre>
 495 </div>
 496
 497 <p>Note how the parser turns the top-level expression into anonymous functions
 498 for us.  This will be handy when we add JIT support in the next chapter.  Also
 499 note that the code is very literally transcribed, no optimizations are being
 500 performed.  We will add optimizations explicitly in the next chapter.</p>
 501
 502 <div class="doc_code">
 503 <pre>
 504 ready&gt; <b>def foo(a b) a*a + 2*a*b + b*b;</b>
 505 ready&gt; Read function definition:
 506 define double @foo(double %a, double %b) {
 507 entry:
 508         %multmp = mul double %a, %a
 509         %multmp1 = mul double 2.000000e+00, %a
 510         %multmp2 = mul double %multmp1, %b
 511         %addtmp = add double %multmp, %multmp2
 512         %multmp3 = mul double %b, %b
 513         %addtmp4 = add double %addtmp, %multmp3
 514         ret double %addtmp4
 515 }
 516 </pre>
 517 </div>
 518
 519 <p>This shows some simple arithmetic. Notice the striking similarity to the
 520 LLVM builder calls that we use to create the instructions.</p>
 521
 522 <div class="doc_code">
 523 <pre>
 524 ready&gt; <b>def bar(a) foo(a, 4.0) + bar(31337);</b>
 525 ready&gt; Read function definition:
 526 define double @bar(double %a) {
 527 entry:
 528         %calltmp = call double @foo( double %a, double 4.000000e+00 )
 529         %calltmp1 = call double @bar( double 3.133700e+04 )
 530         %addtmp = add double %calltmp, %calltmp1
 531         ret double %addtmp
 532 }
 533 </pre>
 534 </div>
 535
 536 <p>This shows some function calls.  Note that the runtime of this function might
 537 be fairly high.  In the future we'll add conditional control flow to make
 538 recursion actually be useful :).</p>
 539
 540 <div class="doc_code">
 541 <pre>
 542 ready&gt; <b>extern cos(x);</b>
 543 ready&gt; Read extern:
 544 declare double @cos(double)
 545
 546 ready&gt; <b>cos(1.234);</b>
 547 ready&gt; Read top-level expression:
 548 define double @""() {
 549 entry:
 550         %calltmp = call double @cos( double 1.234000e+00 )
 551         ret double %calltmp
 552 }
 553 </pre>
 554 </div>
 555
 556 <p>This shows an extern for the libm "cos" function, and a call to it.</p>
 557
 558
 559 <div class="doc_code">
 560 <pre>
 561 ready&gt; <b>^D</b>
 562 ; ModuleID = 'my cool jit'
 563
 564 define double @""() {
 565 entry:
 566         %addtmp = add double 4.000000e+00, 5.000000e+00
 567         ret double %addtmp
 568 }
 569
 570 define double @foo(double %a, double %b) {
 571 entry:
 572         %multmp = mul double %a, %a
 573         %multmp1 = mul double 2.000000e+00, %a
 574         %multmp2 = mul double %multmp1, %b
 575         %addtmp = add double %multmp, %multmp2
 576         %multmp3 = mul double %b, %b
 577         %addtmp4 = add double %addtmp, %multmp3
 578         ret double %addtmp4
 579 }
 580
 581 define double @bar(double %a) {
 582 entry:
 583         %calltmp = call double @foo( double %a, double 4.000000e+00 )
 584         %calltmp1 = call double @bar( double 3.133700e+04 )
 585         %addtmp = add double %calltmp, %calltmp1
 586         ret double %addtmp
 587 }
 588
 589 declare double @cos(double)
 590
 591 define double @""() {
 592 entry:
 593         %calltmp = call double @cos( double 1.234000e+00 )
 594         ret double %calltmp
 595 }
 596 </pre>
 597 </div>
 598
 599 <p>When you quit the current demo, it dumps out the IR for the entire module
 600 generated.  Here you can see the big picture with all the functions referencing
 601 each other.</p>
 602
 603 <p>This wraps up this chapter of the Kaleidoscope tutorial.  Up next we'll
 604 describe how to <a href="LangImpl4.html">add JIT codegen and optimizer
 605 support</a> to this so we can actually start running code!</p>
 606
 607 </div>
 608
 609
 610 <!-- *********************************************************************** -->
 611 <div class="doc_section"><a name="code">Full Code Listing</a></div>
 612 <!-- *********************************************************************** -->
 613
 614 <div class="doc_text">
 615
 616 <p>
 617 Here is the complete code listing for our running example, enhanced with the
 618 LLVM code generator.    Because this uses the LLVM libraries, we need to link
 619 them in.  To do this, we use the <a
 620 href="http://llvm.org/cmds/llvm-config.html">llvm-config</a> tool to inform
 621 our makefile/command line about which options to use:</p>
 622
 623 <div class="doc_code">
 624 <pre>
 625    # Compile
 626    g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core` -o toy
 627    # Run
 628    ./toy
 629 </pre>
 630 </div>
 631
 632 <p>Here is the code:</p>
 633
 634 <div class="doc_code">
 635 <pre>
 636 // To build this:
 637 // See example below.
 638
 639 #include "llvm/DerivedTypes.h"
 640 #include "llvm/Module.h"
 641 #include "llvm/Analysis/Verifier.h"
 642 #include "llvm/Support/LLVMBuilder.h"
 643 #include &lt;cstdio&gt;
 644 #include &lt;string&gt;
 645 #include &lt;map&gt;
 646 #include &lt;vector&gt;
 647 using namespace llvm;
 648
 649 //===----------------------------------------------------------------------===//
 650 // Lexer
 651 //===----------------------------------------------------------------------===//
 652
 653 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
 654 // of these for known things.
 655 enum Token {
 656   tok_eof = -1,
 657
 658   // commands
 659   tok_def = -2, tok_extern = -3,
 660
 661   // primary
 662   tok_identifier = -4, tok_number = -5,
 663 };
 664
 665 static std::string IdentifierStr;  // Filled in if tok_identifier
 666 static double NumVal;              // Filled in if tok_number
 667
 668 /// gettok - Return the next token from standard input.
 669 static int gettok() {
 670   static int LastChar = ' ';
 671
 672   // Skip any whitespace.
 673   while (isspace(LastChar))
 674     LastChar = getchar();
 675
 676   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
 677     IdentifierStr = LastChar;
 678     while (isalnum((LastChar = getchar())))
 679       IdentifierStr += LastChar;
 680
 681     if (IdentifierStr == "def") return tok_def;
 682     if (IdentifierStr == "extern") return tok_extern;
 683     return tok_identifier;
 684   }
 685
 686   if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
 687     std::string NumStr;
 688     do {
 689       NumStr += LastChar;
 690       LastChar = getchar();
 691     } while (isdigit(LastChar) || LastChar == '.');
 692
 693     NumVal = strtod(NumStr.c_str(), 0);
 694     return tok_number;
 695   }
 696
 697   if (LastChar == '#') {
 698     // Comment until end of line.
 699     do LastChar = getchar();
 700     while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp; LastChar != '\r');
 701
 702     if (LastChar != EOF)
 703       return gettok();
 704   }
 705
 706   // Check for end of file.  Don't eat the EOF.
 707   if (LastChar == EOF)
 708     return tok_eof;
 709
 710   // Otherwise, just return the character as its ascii value.
 711   int ThisChar = LastChar;
 712   LastChar = getchar();
 713   return ThisChar;
 714 }
 715
 716 //===----------------------------------------------------------------------===//
 717 // Abstract Syntax Tree (aka Parse Tree)
 718 //===----------------------------------------------------------------------===//
 719
 720 /// ExprAST - Base class for all expression nodes.
 721 class ExprAST {
 722 public:
 723   virtual ~ExprAST() {}
 724   virtual Value *Codegen() = 0;
 725 };
 726
 727 /// NumberExprAST - Expression class for numeric literals like "1.0".
 728 class NumberExprAST : public ExprAST {
 729   double Val;
 730 public:
 731   explicit NumberExprAST(double val) : Val(val) {}
 732   virtual Value *Codegen();
 733 };
 734
 735 /// VariableExprAST - Expression class for referencing a variable, like "a".
 736 class VariableExprAST : public ExprAST {
 737   std::string Name;
 738 public:
 739   explicit VariableExprAST(const std::string &amp;name) : Name(name) {}
 740   virtual Value *Codegen();
 741 };
 742
 743 /// BinaryExprAST - Expression class for a binary operator.
 744 class BinaryExprAST : public ExprAST {
 745   char Op;
 746   ExprAST *LHS, *RHS;
 747 public:
 748   BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
 749     : Op(op), LHS(lhs), RHS(rhs) {}
 750   virtual Value *Codegen();
 751 };
 752
 753 /// CallExprAST - Expression class for function calls.
 754 class CallExprAST : public ExprAST {
 755   std::string Callee;
 756   std::vector&lt;ExprAST*&gt; Args;
 757 public:
 758   CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
 759     : Callee(callee), Args(args) {}
 760   virtual Value *Codegen();
 761 };
 762
 763 /// PrototypeAST - This class represents the "prototype" for a function,
 764 /// which captures its argument names as well as if it is an operator.
 765 class PrototypeAST {
 766   std::string Name;
 767   std::vector&lt;std::string&gt; Args;
 768 public:
 769   PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args)
 770     : Name(name), Args(args) {}
 771
 772   Function *Codegen();
 773 };
 774
 775 /// FunctionAST - This class represents a function definition itself.
 776 class FunctionAST {
 777   PrototypeAST *Proto;
 778   ExprAST *Body;
 779 public:
 780   FunctionAST(PrototypeAST *proto, ExprAST *body)
 781     : Proto(proto), Body(body) {}
 782
 783   Function *Codegen();
 784 };
 785
 786 //===----------------------------------------------------------------------===//
 787 // Parser
 788 //===----------------------------------------------------------------------===//
 789
 790 /// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
 791 /// token the parser it looking at.  getNextToken reads another token from the
 792 /// lexer and updates CurTok with its results.
 793 static int CurTok;
 794 static int getNextToken() {
 795   return CurTok = gettok();
 796 }
 797
 798 /// BinopPrecedence - This holds the precedence for each binary operator that is
 799 /// defined.
 800 static std::map&lt;char, int&gt; BinopPrecedence;
 801
 802 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
 803 static int GetTokPrecedence() {
 804   if (!isascii(CurTok))
 805     return -1;
 806
 807   // Make sure it's a declared binop.
 808   int TokPrec = BinopPrecedence[CurTok];
 809   if (TokPrec &lt;= 0) return -1;
 810   return TokPrec;
 811 }
 812
 813 /// Error* - These are little helper functions for error handling.
 814 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
 815 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
 816 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
 817
 818 static ExprAST *ParseExpression();
 819
 820 /// identifierexpr
 821 ///   ::= identifer
 822 ///   ::= identifer '(' expression* ')'
 823 static ExprAST *ParseIdentifierExpr() {
 824   std::string IdName = IdentifierStr;
 825
 826   getNextToken();  // eat identifer.
 827
 828   if (CurTok != '(') // Simple variable ref.
 829     return new VariableExprAST(IdName);
 830
 831   // Call.
 832   getNextToken();  // eat (
 833   std::vector&lt;ExprAST*&gt; Args;
 834   while (1) {
 835     ExprAST *Arg = ParseExpression();
 836     if (!Arg) return 0;
 837     Args.push_back(Arg);
 838
 839     if (CurTok == ')') break;
 840
 841     if (CurTok != ',')
 842       return Error("Expected ')'");
 843     getNextToken();
 844   }
 845
 846   // Eat the ')'.
 847   getNextToken();
 848
 849   return new CallExprAST(IdName, Args);
 850 }
 851
 852 /// numberexpr ::= number
 853 static ExprAST *ParseNumberExpr() {
 854   ExprAST *Result = new NumberExprAST(NumVal);
 855   getNextToken(); // consume the number
 856   return Result;
 857 }
 858
 859 /// parenexpr ::= '(' expression ')'
 860 static ExprAST *ParseParenExpr() {
 861   getNextToken();  // eat (.
 862   ExprAST *V = ParseExpression();
 863   if (!V) return 0;
 864
 865   if (CurTok != ')')
 866     return Error("expected ')'");
 867   getNextToken();  // eat ).
 868   return V;
 869 }
 870
 871 /// primary
 872 ///   ::= identifierexpr
 873 ///   ::= numberexpr
 874 ///   ::= parenexpr
 875 static ExprAST *ParsePrimary() {
 876   switch (CurTok) {
 877   default: return Error("unknown token when expecting an expression");
 878   case tok_identifier: return ParseIdentifierExpr();
 879   case tok_number:     return ParseNumberExpr();
 880   case '(':            return ParseParenExpr();
 881   }
 882 }
 883
 884 /// binoprhs
 885 ///   ::= ('+' primary)*
 886 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
 887   // If this is a binop, find its precedence.
 888   while (1) {
 889     int TokPrec = GetTokPrecedence();
 890
 891     // If this is a binop that binds at least as tightly as the current binop,
 892     // consume it, otherwise we are done.
 893     if (TokPrec &lt; ExprPrec)
 894       return LHS;
 895
 896     // Okay, we know this is a binop.
 897     int BinOp = CurTok;
 898     getNextToken();  // eat binop
 899
 900     // Parse the primary expression after the binary operator.
 901     ExprAST *RHS = ParsePrimary();
 902     if (!RHS) return 0;
 903
 904     // If BinOp binds less tightly with RHS than the operator after RHS, let
 905     // the pending operator take RHS as its LHS.
 906     int NextPrec = GetTokPrecedence();
 907     if (TokPrec &lt; NextPrec) {
 908       RHS = ParseBinOpRHS(TokPrec+1, RHS);
 909       if (RHS == 0) return 0;
 910     }
 911
 912     // Merge LHS/RHS.
 913     LHS = new BinaryExprAST(BinOp, LHS, RHS);
 914   }
 915 }
 916
 917 /// expression
 918 ///   ::= primary binoprhs
 919 ///
 920 static ExprAST *ParseExpression() {
 921   ExprAST *LHS = ParsePrimary();
 922   if (!LHS) return 0;
 923
 924   return ParseBinOpRHS(0, LHS);
 925 }
 926
 927 /// prototype
 928 ///   ::= id '(' id* ')'
 929 static PrototypeAST *ParsePrototype() {
 930   if (CurTok != tok_identifier)
 931     return ErrorP("Expected function name in prototype");
 932
 933   std::string FnName = IdentifierStr;
 934   getNextToken();
 935
 936   if (CurTok != '(')
 937     return ErrorP("Expected '(' in prototype");
 938
 939   std::vector&lt;std::string&gt; ArgNames;
 940   while (getNextToken() == tok_identifier)
 941     ArgNames.push_back(IdentifierStr);
 942   if (CurTok != ')')
 943     return ErrorP("Expected ')' in prototype");
 944
 945   // success.
 946   getNextToken();  // eat ')'.
 947
 948   return new PrototypeAST(FnName, ArgNames);
 949 }
 950
 951 /// definition ::= 'def' prototype expression
 952 static FunctionAST *ParseDefinition() {
 953   getNextToken();  // eat def.
 954   PrototypeAST *Proto = ParsePrototype();
 955   if (Proto == 0) return 0;
 956
 957   if (ExprAST *E = ParseExpression())
 958     return new FunctionAST(Proto, E);
 959   return 0;
 960 }
 961
 962 /// toplevelexpr ::= expression
 963 static FunctionAST *ParseTopLevelExpr() {
 964   if (ExprAST *E = ParseExpression()) {
 965     // Make an anonymous proto.
 966     PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
 967     return new FunctionAST(Proto, E);
 968   }
 969   return 0;
 970 }
 971
 972 /// external ::= 'extern' prototype
 973 static PrototypeAST *ParseExtern() {
 974   getNextToken();  // eat extern.
 975   return ParsePrototype();
 976 }
 977
 978 //===----------------------------------------------------------------------===//
 979 // Code Generation
 980 //===----------------------------------------------------------------------===//
 981
 982 static Module *TheModule;
 983 static LLVMBuilder Builder;
 984 static std::map&lt;std::string, Value*&gt; NamedValues;
 985
 986 Value *ErrorV(const char *Str) { Error(Str); return 0; }
 987
 988 Value *NumberExprAST::Codegen() {
 989   return ConstantFP::get(Type::DoubleTy, APFloat(Val));
 990 }
 991
 992 Value *VariableExprAST::Codegen() {
 993   // Look this variable up in the function.
 994   Value *V = NamedValues[Name];
 995   return V ? V : ErrorV("Unknown variable name");
 996 }
 997
 998 Value *BinaryExprAST::Codegen() {
 999   Value *L = LHS-&gt;Codegen();
1000   Value *R = RHS-&gt;Codegen();
1001   if (L == 0 || R == 0) return 0;
1002
1003   switch (Op) {
1004   case '+': return Builder.CreateAdd(L, R, "addtmp");
1005   case '-': return Builder.CreateSub(L, R, "subtmp");
1006   case '*': return Builder.CreateMul(L, R, "multmp");
1007   case '&lt;':
1008     L = Builder.CreateFCmpULT(L, R, "multmp");
1009     // Convert bool 0/1 to double 0.0 or 1.0
1010     return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
1011   default: return ErrorV("invalid binary operator");
1012   }
1013 }
1014
1015 Value *CallExprAST::Codegen() {
1016   // Look up the name in the global module table.
1017   Function *CalleeF = TheModule-&gt;getFunction(Callee);
1018   if (CalleeF == 0)
1019     return ErrorV("Unknown function referenced");
1020
1021   // If argument mismatch error.
1022   if (CalleeF-&gt;arg_size() != Args.size())
1023     return ErrorV("Incorrect # arguments passed");
1024
1025   std::vector&lt;Value*&gt; ArgsV;
1026   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1027     ArgsV.push_back(Args[i]-&gt;Codegen());
1028     if (ArgsV.back() == 0) return 0;
1029   }
1030
1031   return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1032 }
1033
1034 Function *PrototypeAST::Codegen() {
1035   // Make the function type:  double(double,double) etc.
1036   std::vector&lt;const Type*&gt; Doubles(Args.size(), Type::DoubleTy);
1037   FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
1038
1039   Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
1040
1041   // If F conflicted, there was already something named 'Name'.  If it has a
1042   // body, don't allow redefinition or reextern.
1043   if (F-&gt;getName() != Name) {
1044     // Delete the one we just made and get the existing one.
1045     F-&gt;eraseFromParent();
1046     F = TheModule-&gt;getFunction(Name);
1047
1048     // If F already has a body, reject this.
1049     if (!F-&gt;empty()) {
1050       ErrorF("redefinition of function");
1051       return 0;
1052     }
1053
1054     // If F took a different number of args, reject.
1055     if (F-&gt;arg_size() != Args.size()) {
1056       ErrorF("redefinition of function with different # args");
1057       return 0;
1058     }
1059   }
1060
1061   // Set names for all arguments.
1062   unsigned Idx = 0;
1063   for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1064        ++AI, ++Idx) {
1065     AI-&gt;setName(Args[Idx]);
1066
1067     // Add arguments to variable symbol table.
1068     NamedValues[Args[Idx]] = AI;
1069   }
1070
1071   return F;
1072 }
1073
1074 Function *FunctionAST::Codegen() {
1075   NamedValues.clear();
1076
1077   Function *TheFunction = Proto-&gt;Codegen();
1078   if (TheFunction == 0)
1079     return 0;
1080
1081   // Create a new basic block to start insertion into.
1082   BasicBlock *BB = new BasicBlock("entry", TheFunction);
1083   Builder.SetInsertPoint(BB);
1084
1085   if (Value *RetVal = Body-&gt;Codegen()) {
1086     // Finish off the function.
1087     Builder.CreateRet(RetVal);
1088
1089     // Validate the generated code, checking for consistency.
1090     verifyFunction(*TheFunction);
1091     return TheFunction;
1092   }
1093
1094   // Error reading body, remove function.
1095   TheFunction-&gt;eraseFromParent();
1096   return 0;
1097 }
1098
1099 //===----------------------------------------------------------------------===//
1100 // Top-Level parsing and JIT Driver
1101 //===----------------------------------------------------------------------===//
1102
1103 static void HandleDefinition() {
1104   if (FunctionAST *F = ParseDefinition()) {
1105     if (Function *LF = F-&gt;Codegen()) {
1106       fprintf(stderr, "Read function definition:");
1107       LF-&gt;dump();
1108     }
1109   } else {
1110     // Skip token for error recovery.
1111     getNextToken();
1112   }
1113 }
1114
1115 static void HandleExtern() {
1116   if (PrototypeAST *P = ParseExtern()) {
1117     if (Function *F = P-&gt;Codegen()) {
1118       fprintf(stderr, "Read extern: ");
1119       F-&gt;dump();
1120     }
1121   } else {
1122     // Skip token for error recovery.
1123     getNextToken();
1124   }
1125 }
1126
1127 static void HandleTopLevelExpression() {
1128   // Evaluate a top level expression into an anonymous function.
1129   if (FunctionAST *F = ParseTopLevelExpr()) {
1130     if (Function *LF = F-&gt;Codegen()) {
1131       fprintf(stderr, "Read top-level expression:");
1132       LF-&gt;dump();
1133     }
1134   } else {
1135     // Skip token for error recovery.
1136     getNextToken();
1137   }
1138 }
1139
1140 /// top ::= definition | external | expression | ';'
1141 static void MainLoop() {
1142   while (1) {
1143     fprintf(stderr, "ready&gt; ");
1144     switch (CurTok) {
1145     case tok_eof:    return;
1146     case ';':        getNextToken(); break;  // ignore top level semicolons.
1147     case tok_def:    HandleDefinition(); break;
1148     case tok_extern: HandleExtern(); break;
1149     default:         HandleTopLevelExpression(); break;
1150     }
1151   }
1152 }
1153
1154
1155
1156 //===----------------------------------------------------------------------===//
1157 // "Library" functions that can be "extern'd" from user code.
1158 //===----------------------------------------------------------------------===//
1159
1160 /// putchard - putchar that takes a double and returns 0.
1161 extern "C"
1162 double putchard(double X) {
1163   putchar((char)X);
1164   return 0;
1165 }
1166
1167 //===----------------------------------------------------------------------===//
1168 // Main driver code.
1169 //===----------------------------------------------------------------------===//
1170
1171 int main() {
1172   TheModule = new Module("my cool jit");
1173
1174   // Install standard binary operators.
1175   // 1 is lowest precedence.
1176   BinopPrecedence['&lt;'] = 10;
1177   BinopPrecedence['+'] = 20;
1178   BinopPrecedence['-'] = 20;
1179   BinopPrecedence['*'] = 40;  // highest.
1180
1181   // Prime the first token.
1182   fprintf(stderr, "ready&gt; ");
1183   getNextToken();
1184
1185   MainLoop();
1186   TheModule-&gt;dump();
1187   return 0;
1188 }
1189 </pre>
1190 </div>
1191 </div>
1192
1193 <!-- *********************************************************************** -->
1194 <hr>
1195 <address>
1196   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1197   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1198   <a href="http://validator.w3.org/check/referer"><img
1199   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1200
1201   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1202   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
1203   Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
1204 </address>
1205 </body>
1206 </html>