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