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