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