Blame - docs/tutorial/OCamlLangImpl7.html - fp2-dev/platform/external/llvm

blob: abda44011cab14a629855bd4f463d8b3a515c1ba [file] [log] [blame]

Erick Tryzelaar	35295ff	2008-03-31 08:44:50 +0000	[diff] [blame]	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: Extending the Language: Mutable Variables / SSA
				7	construction</title>
				8	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
				9	<meta name="author" content="Chris Lattner">
				10	<meta name="author" content="Erick Tryzelaar">
				11	<link rel="stylesheet" href="../llvm.css" type="text/css">
				12	</head>
				13
				14	<body>
				15
				16	<div class="doc_title">Kaleidoscope: Extending the Language: Mutable Variables</div>
				17
				18	<ul>
				19	<li><a href="index.html">Up to Tutorial Index</a></li>
				20	<li>Chapter 7
				21	<ol>
				22	<li><a href="#intro">Chapter 7 Introduction</a></li>
				23	<li><a href="#why">Why is this a hard problem?</a></li>
				24	<li><a href="#memory">Memory in LLVM</a></li>
				25	<li><a href="#kalvars">Mutable Variables in Kaleidoscope</a></li>
				26	<li><a href="#adjustments">Adjusting Existing Variables for
				27	Mutation</a></li>
				28	<li><a href="#assignment">New Assignment Operator</a></li>
				29	<li><a href="#localvars">User-defined Local Variables</a></li>
				30	<li><a href="#code">Full Code Listing</a></li>
				31	</ol>
				32	</li>
				33	<li><a href="LangImpl8.html">Chapter 8</a>: Conclusion and other useful LLVM
				34	tidbits</li>
				35	</ul>
				36
				37	<div class="doc_author">
				38	<p>
				39	Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>
				40	and <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a>
				41	</p>
				42	</div>
				43
				44	<!-- *********************************************************************** -->
				45	<div class="doc_section"><a name="intro">Chapter 7 Introduction</a></div>
				46	<!-- *********************************************************************** -->
				47
				48	<div class="doc_text">
				49
				50	<p>Welcome to Chapter 7 of the "<a href="index.html">Implementing a language
				51	with LLVM</a>" tutorial. In chapters 1 through 6, we've built a very
				52	respectable, albeit simple, <a
				53	href="http://en.wikipedia.org/wiki/Functional_programming">functional
				54	programming language</a>. In our journey, we learned some parsing techniques,
				55	how to build and represent an AST, how to build LLVM IR, and how to optimize
				56	the resultant code as well as JIT compile it.</p>
				57
				58	<p>While Kaleidoscope is interesting as a functional language, the fact that it
				59	is functional makes it "too easy" to generate LLVM IR for it. In particular, a
				60	functional language makes it very easy to build LLVM IR directly in <a
				61	href="http://en.wikipedia.org/wiki/Static_single_assignment_form">SSA form</a>.
				62	Since LLVM requires that the input code be in SSA form, this is a very nice
				63	property and it is often unclear to newcomers how to generate code for an
				64	imperative language with mutable variables.</p>
				65
				66	<p>The short (and happy) summary of this chapter is that there is no need for
				67	your front-end to build SSA form: LLVM provides highly tuned and well tested
				68	support for this, though the way it works is a bit unexpected for some.</p>
				69
				70	</div>
				71
				72	<!-- *********************************************************************** -->
				73	<div class="doc_section"><a name="why">Why is this a hard problem?</a></div>
				74	<!-- *********************************************************************** -->
				75
				76	<div class="doc_text">
				77
				78	<p>
				79	To understand why mutable variables cause complexities in SSA construction,
				80	consider this extremely simple C example:
				81	</p>
				82
				83	<div class="doc_code">
				84	<pre>
				85	int G, H;
				86	int test(_Bool Condition) {
				87	int X;
				88	if (Condition)
				89	X = G;
				90	else
				91	X = H;
				92	return X;
				93	}
				94	</pre>
				95	</div>
				96
				97	<p>In this case, we have the variable "X", whose value depends on the path
				98	executed in the program. Because there are two different possible values for X
				99	before the return instruction, a PHI node is inserted to merge the two values.
				100	The LLVM IR that we want for this example looks like this:</p>
				101
				102	<div class="doc_code">
				103	<pre>
				104	@G = weak global i32 0 ; type of @G is i32*
				105	@H = weak global i32 0 ; type of @H is i32*
				106
				107	define i32 @test(i1 %Condition) {
				108	entry:
				109	br i1 %Condition, label %cond_true, label %cond_false
				110
				111	cond_true:
				112	%X.0 = load i32* @G
				113	br label %cond_next
				114
				115	cond_false:
				116	%X.1 = load i32* @H
				117	br label %cond_next
				118
				119	cond_next:
				120	%X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
				121	ret i32 %X.2
				122	}
				123	</pre>
				124	</div>
				125
				126	<p>In this example, the loads from the G and H global variables are explicit in
				127	the LLVM IR, and they live in the then/else branches of the if statement
				128	(cond_true/cond_false). In order to merge the incoming values, the X.2 phi node
				129	in the cond_next block selects the right value to use based on where control
				130	flow is coming from: if control flow comes from the cond_false block, X.2 gets
				131	the value of X.1. Alternatively, if control flow comes from cond_true, it gets
				132	the value of X.0. The intent of this chapter is not to explain the details of
				133	SSA form. For more information, see one of the many <a
				134	href="http://en.wikipedia.org/wiki/Static_single_assignment_form">online
				135	references</a>.</p>
				136
				137	<p>The question for this article is "who places the phi nodes when lowering
				138	assignments to mutable variables?". The issue here is that LLVM
				139	<em>requires</em> that its IR be in SSA form: there is no "non-ssa" mode for it.
				140	However, SSA construction requires non-trivial algorithms and data structures,
				141	so it is inconvenient and wasteful for every front-end to have to reproduce this
				142	logic.</p>
				143
				144	</div>
				145
				146	<!-- *********************************************************************** -->
				147	<div class="doc_section"><a name="memory">Memory in LLVM</a></div>
				148	<!-- *********************************************************************** -->
				149
				150	<div class="doc_text">
				151
				152	<p>The 'trick' here is that while LLVM does require all register values to be
				153	in SSA form, it does not require (or permit) memory objects to be in SSA form.
				154	In the example above, note that the loads from G and H are direct accesses to
				155	G and H: they are not renamed or versioned. This differs from some other
				156	compiler systems, which do try to version memory objects. In LLVM, instead of
				157	encoding dataflow analysis of memory into the LLVM IR, it is handled with <a
				158	href="../WritingAnLLVMPass.html">Analysis Passes</a> which are computed on
				159	demand.</p>
				160
				161	<p>
				162	With this in mind, the high-level idea is that we want to make a stack variable
				163	(which lives in memory, because it is on the stack) for each mutable object in
				164	a function. To take advantage of this trick, we need to talk about how LLVM
				165	represents stack variables.
				166	</p>
				167
				168	<p>In LLVM, all memory accesses are explicit with load/store instructions, and
				169	it is carefully designed not to have (or need) an "address-of" operator. Notice
				170	how the type of the @G/@H global variables is actually "i32*" even though the
				171	variable is defined as "i32". What this means is that @G defines <em>space</em>
				172	for an i32 in the global data area, but its <em>name</em> actually refers to the
				173	address for that space. Stack variables work the same way, except that instead of
				174	being declared with global variable definitions, they are declared with the
				175	<a href="../LangRef.html#i_alloca">LLVM alloca instruction</a>:</p>
				176
				177	<div class="doc_code">
				178	<pre>
				179	define i32 @example() {
				180	entry:
				181	%X = alloca i32 ; type of %X is i32*.
				182	...
				183	%tmp = load i32* %X ; load the stack value %X from the stack.
				184	%tmp2 = add i32 %tmp, 1 ; increment it
				185	store i32 %tmp2, i32* %X ; store it back
				186	...
				187	</pre>
				188	</div>
				189
				190	<p>This code shows an example of how you can declare and manipulate a stack
				191	variable in the LLVM IR. Stack memory allocated with the alloca instruction is
				192	fully general: you can pass the address of the stack slot to functions, you can
				193	store it in other variables, etc. In our example above, we could rewrite the
				194	example to use the alloca technique to avoid using a PHI node:</p>
				195
				196	<div class="doc_code">
				197	<pre>
				198	@G = weak global i32 0 ; type of @G is i32*
				199	@H = weak global i32 0 ; type of @H is i32*
				200
				201	define i32 @test(i1 %Condition) {
				202	entry:
				203	%X = alloca i32 ; type of %X is i32*.
				204	br i1 %Condition, label %cond_true, label %cond_false
				205
				206	cond_true:
				207	%X.0 = load i32* @G
				208	store i32 %X.0, i32* %X ; Update X
				209	br label %cond_next
				210
				211	cond_false:
				212	%X.1 = load i32* @H
				213	store i32 %X.1, i32* %X ; Update X
				214	br label %cond_next
				215
				216	cond_next:
				217	%X.2 = load i32* %X ; Read X
				218	ret i32 %X.2
				219	}
				220	</pre>
				221	</div>
				222
				223	<p>With this, we have discovered a way to handle arbitrary mutable variables
				224	without the need to create Phi nodes at all:</p>
				225
				226	<ol>
				227	<li>Each mutable variable becomes a stack allocation.</li>
				228	<li>Each read of the variable becomes a load from the stack.</li>
				229	<li>Each update of the variable becomes a store to the stack.</li>
				230	<li>Taking the address of a variable just uses the stack address directly.</li>
				231	</ol>
				232
				233	<p>While this solution has solved our immediate problem, it introduced another
				234	one: we have now apparently introduced a lot of stack traffic for very simple
				235	and common operations, a major performance problem. Fortunately for us, the
				236	LLVM optimizer has a highly-tuned optimization pass named "mem2reg" that handles
				237	this case, promoting allocas like this into SSA registers, inserting Phi nodes
				238	as appropriate. If you run this example through the pass, for example, you'll
				239	get:</p>
				240
				241	<div class="doc_code">
				242	<pre>
				243	$ <b>llvm-as < example.ll \| opt -mem2reg \| llvm-dis</b>
				244	@G = weak global i32 0
				245	@H = weak global i32 0
				246
				247	define i32 @test(i1 %Condition) {
				248	entry:
				249	br i1 %Condition, label %cond_true, label %cond_false
				250
				251	cond_true:
				252	%X.0 = load i32* @G
				253	br label %cond_next
				254
				255	cond_false:
				256	%X.1 = load i32* @H
				257	br label %cond_next
				258
				259	cond_next:
				260	%X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
				261	ret i32 %X.01
				262	}
				263	</pre>
				264	</div>
				265
				266	<p>The mem2reg pass implements the standard "iterated dominance frontier"
				267	algorithm for constructing SSA form and has a number of optimizations that speed
				268	up (very common) degenerate cases. The mem2reg optimization pass is the answer
				269	to dealing with mutable variables, and we highly recommend that you depend on
				270	it. Note that mem2reg only works on variables in certain circumstances:</p>
				271
				272	<ol>
				273	<li>mem2reg is alloca-driven: it looks for allocas and if it can handle them, it
				274	promotes them. It does not apply to global variables or heap allocations.</li>
				275
				276	<li>mem2reg only looks for alloca instructions in the entry block of the
				277	function. Being in the entry block guarantees that the alloca is only executed
				278	once, which makes analysis simpler.</li>
				279
				280	<li>mem2reg only promotes allocas whose uses are direct loads and stores. If
				281	the address of the stack object is passed to a function, or if any funny pointer
				282	arithmetic is involved, the alloca will not be promoted.</li>
				283
				284	<li>mem2reg only works on allocas of <a
				285	href="../LangRef.html#t_classifications">first class</a>
				286	values (such as pointers, scalars and vectors), and only if the array size
				287	of the allocation is 1 (or missing in the .ll file). mem2reg is not capable of
				288	promoting structs or arrays to registers. Note that the "scalarrepl" pass is
				289	more powerful and can promote structs, "unions", and arrays in many cases.</li>
				290
				291	</ol>
				292
				293	<p>
				294	All of these properties are easy to satisfy for most imperative languages, and
				295	we'll illustrate it below with Kaleidoscope. The final question you may be
				296	asking is: should I bother with this nonsense for my front-end? Wouldn't it be
				297	better if I just did SSA construction directly, avoiding use of the mem2reg
				298	optimization pass? In short, we strongly recommend that you use this technique
				299	for building SSA form, unless there is an extremely good reason not to. Using
				300	this technique is:</p>
				301
				302	<ul>
				303	<li>Proven and well tested: llvm-gcc and clang both use this technique for local
				304	mutable variables. As such, the most common clients of LLVM are using this to
				305	handle a bulk of their variables. You can be sure that bugs are found fast and
				306	fixed early.</li>
				307
				308	<li>Extremely Fast: mem2reg has a number of special cases that make it fast in
				309	common cases as well as fully general. For example, it has fast-paths for
				310	variables that are only used in a single block, variables that only have one
				311	assignment point, good heuristics to avoid insertion of unneeded phi nodes, etc.
				312	</li>
				313
				314	<li>Needed for debug info generation: <a href="../SourceLevelDebugging.html">
				315	Debug information in LLVM</a> relies on having the address of the variable
				316	exposed so that debug info can be attached to it. This technique dovetails
				317	very naturally with this style of debug info.</li>
				318	</ul>
				319
				320	<p>If nothing else, this makes it much easier to get your front-end up and
				321	running, and is very simple to implement. Lets extend Kaleidoscope with mutable
				322	variables now!
				323	</p>
				324
				325	</div>
				326
				327	<!-- *********************************************************************** -->
				328	<div class="doc_section"><a name="kalvars">Mutable Variables in
				329	Kaleidoscope</a></div>
				330	<!-- *********************************************************************** -->
				331
				332	<div class="doc_text">
				333
				334	<p>Now that we know the sort of problem we want to tackle, lets see what this
				335	looks like in the context of our little Kaleidoscope language. We're going to
				336	add two features:</p>
				337
				338	<ol>
				339	<li>The ability to mutate variables with the '=' operator.</li>
				340	<li>The ability to define new variables.</li>
				341	</ol>
				342
				343	<p>While the first item is really what this is about, we only have variables
				344	for incoming arguments as well as for induction variables, and redefining those only
				345	goes so far :). Also, the ability to define new variables is a
				346	useful thing regardless of whether you will be mutating them. Here's a
				347	motivating example that shows how we could use these:</p>
				348
				349	<div class="doc_code">
				350	<pre>
				351	# Define ':' for sequencing: as a low-precedence operator that ignores operands
				352	# and just returns the RHS.
				353	def binary : 1 (x y) y;
				354
				355	# Recursive fib, we could do this before.
				356	def fib(x)
				357	if (x < 3) then
				358	1
				359	else
				360	fib(x-1)+fib(x-2);
				361
				362	# Iterative fib.
				363	def fibi(x)
				364	<b>var a = 1, b = 1, c in</b>
				365	(for i = 3, i < x in
				366	<b>c = a + b</b> :
				367	<b>a = b</b> :
				368	<b>b = c</b>) :
				369	b;
				370
				371	# Call it.
				372	fibi(10);
				373	</pre>
				374	</div>
				375
				376	<p>
				377	In order to mutate variables, we have to change our existing variables to use
				378	the "alloca trick". Once we have that, we'll add our new operator, then extend
				379	Kaleidoscope to support new variable definitions.
				380	</p>
				381
				382	</div>
				383
				384	<!-- *********************************************************************** -->
				385	<div class="doc_section"><a name="adjustments">Adjusting Existing Variables for
				386	Mutation</a></div>
				387	<!-- *********************************************************************** -->
				388
				389	<div class="doc_text">
				390
				391	<p>
				392	The symbol table in Kaleidoscope is managed at code generation time by the
				393	'<tt>named_values</tt>' map. This map currently keeps track of the LLVM
				394	"Value*" that holds the double value for the named variable. In order to
				395	support mutation, we need to change this slightly, so that it
				396	<tt>named_values</tt> holds the <em>memory location</em> of the variable in
				397	question. Note that this change is a refactoring: it changes the structure of
				398	the code, but does not (by itself) change the behavior of the compiler. All of
				399	these changes are isolated in the Kaleidoscope code generator.</p>
				400
				401	<p>
				402	At this point in Kaleidoscope's development, it only supports variables for two
				403	things: incoming arguments to functions and the induction variable of 'for'
				404	loops. For consistency, we'll allow mutation of these variables in addition to
				405	other user-defined variables. This means that these will both need memory
				406	locations.
				407	</p>
				408
				409	<p>To start our transformation of Kaleidoscope, we'll change the
				410	<tt>named_values</tt> map so that it maps to AllocaInst* instead of Value*.
				411	Once we do this, the C++ compiler will tell us what parts of the code we need to
				412	update:</p>
				413
				414	<p><b>Note:</b> the ocaml bindings currently model both <tt>Value*</tt>s and
				415	<tt>AllocInst*</tt>s as <tt>Llvm.llvalue</tt>s, but this may change in the
				416	future to be more type safe.</p>
				417
				418	<div class="doc_code">
				419	<pre>
				420	let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
				421	</pre>
				422	</div>
				423
				424	<p>Also, since we will need to create these alloca's, we'll use a helper
				425	function that ensures that the allocas are created in the entry block of the
				426	function:</p>
				427
				428	<div class="doc_code">
				429	<pre>
				430	(* Create an alloca instruction in the entry block of the function. This
				431	* is used for mutable variables etc. *)
				432	let create_entry_block_alloca the_function var_name =
				433	let builder = builder_at (instr_begin (entry_block the_function)) in
				434	build_alloca double_type var_name builder
				435	</pre>
				436	</div>
				437
				438	<p>This funny looking code creates an <tt>Llvm.llbuilder</tt> object that is
				439	pointing at the first instruction of the entry block. It then creates an alloca
				440	with the expected name and returns it. Because all values in Kaleidoscope are
				441	doubles, there is no need to pass in a type to use.</p>
				442
				443	<p>With this in place, the first functionality change we want to make is to
				444	variable references. In our new scheme, variables live on the stack, so code
				445	generating a reference to them actually needs to produce a load from the stack
				446	slot:</p>
				447
				448	<div class="doc_code">
				449	<pre>
				450	let rec codegen_expr = function
				451	...
				452	\| Ast.Variable name ->
				453	let v = try Hashtbl.find named_values name with
				454	\| Not_found -> raise (Error "unknown variable name")
				455	in
				456	<b>(* Load the value. *)
				457	build_load v name builder</b>
				458	</pre>
				459	</div>
				460
				461	<p>As you can see, this is pretty straightforward. Now we need to update the
				462	things that define the variables to set up the alloca. We'll start with
				463	<tt>codegen_expr Ast.For ...</tt> (see the <a href="#code">full code listing</a>
				464	for the unabridged code):</p>
				465
				466	<div class="doc_code">
				467	<pre>
				468	\| Ast.For (var_name, start, end_, step, body) ->
				469	let the_function = block_parent (insertion_block builder) in
				470
				471	(* Create an alloca for the variable in the entry block. *)
				472	<b>let alloca = create_entry_block_alloca the_function var_name in</b>
				473
				474	(* Emit the start code first, without 'variable' in scope. *)
				475	let start_val = codegen_expr start in
				476
				477	<b>(* Store the value into the alloca. *)
				478	ignore(build_store start_val alloca builder);</b>
				479
				480	...
				481
				482	(* Within the loop, the variable is defined equal to the PHI node. If it
				483	* shadows an existing variable, we have to restore it, so save it
				484	* now. *)
				485	let old_val =
				486	try Some (Hashtbl.find named_values var_name) with Not_found -> None
				487	in
				488	<b>Hashtbl.add named_values var_name alloca;</b>
				489
				490	...
				491
				492	(* Compute the end condition. *)
				493	let end_cond = codegen_expr end_ in
				494
				495	<b>(* Reload, increment, and restore the alloca. This handles the case where
				496	* the body of the loop mutates the variable. *)
				497	let cur_var = build_load alloca var_name builder in
				498	let next_var = build_add cur_var step_val "nextvar" builder in
				499	ignore(build_store next_var alloca builder);</b>
				500	...
				501	</pre>
				502	</div>
				503
				504	<p>This code is virtually identical to the code <a
				505	href="OCamlLangImpl5.html#forcodegen">before we allowed mutable variables</a>.
				506	The big difference is that we no longer have to construct a PHI node, and we use
				507	load/store to access the variable as needed.</p>
				508
				509	<p>To support mutable argument variables, we need to also make allocas for them.
				510	The code for this is also pretty simple:</p>
				511
				512	<div class="doc_code">
				513	<pre>
				514	(* Create an alloca for each argument and register the argument in the symbol
				515	* table so that references to it will succeed. *)
				516	let create_argument_allocas the_function proto =
				517	let args = match proto with
				518	\| Ast.Prototype (_, args) \| Ast.BinOpPrototype (_, args, _) -> args
				519	in
				520	Array.iteri (fun i ai ->
				521	let var_name = args.(i) in
				522	(* Create an alloca for this variable. *)
				523	let alloca = create_entry_block_alloca the_function var_name in
				524
				525	(* Store the initial value into the alloca. *)
				526	ignore(build_store ai alloca builder);
				527
				528	(* Add arguments to variable symbol table. *)
				529	Hashtbl.add named_values var_name alloca;
				530	) (params the_function)
				531	</pre>
				532	</div>
				533
				534	<p>For each argument, we make an alloca, store the input value to the function
				535	into the alloca, and register the alloca as the memory location for the
				536	argument. This method gets invoked by <tt>Codegen.codegen_func</tt> right after
				537	it sets up the entry block for the function.</p>
				538
				539	<p>The final missing piece is adding the mem2reg pass, which allows us to get
				540	good codegen once again:</p>
				541
				542	<div class="doc_code">
				543	<pre>
				544	let main () =
				545	...
				546	let the_fpm = PassManager.create_function the_module_provider in
				547
				548	(* Set up the optimizer pipeline. Start with registering info about how the
				549	* target lays out data structures. *)
				550	TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
				551
				552	<b>(* Promote allocas to registers. *)
				553	add_memory_to_register_promotion the_fpm;</b>
				554
				555	(* Do simple "peephole" optimizations and bit-twiddling optzn. *)
				556	add_instruction_combining the_fpm;
				557
				558	(* reassociate expressions. *)
				559	add_reassociation the_fpm;
				560	</pre>
				561	</div>
				562
				563	<p>It is interesting to see what the code looks like before and after the
				564	mem2reg optimization runs. For example, this is the before/after code for our
				565	recursive fib function. Before the optimization:</p>
				566
				567	<div class="doc_code">
				568	<pre>
				569	define double @fib(double %x) {
				570	entry:
				571	<b>%x1 = alloca double
				572	store double %x, double* %x1
				573	%x2 = load double* %x1</b>
				574	%cmptmp = fcmp ult double %x2, 3.000000e+00
				575	%booltmp = uitofp i1 %cmptmp to double
				576	%ifcond = fcmp one double %booltmp, 0.000000e+00
				577	br i1 %ifcond, label %then, label %else
				578
				579	then: ; preds = %entry
				580	br label %ifcont
				581
				582	else: ; preds = %entry
				583	<b>%x3 = load double* %x1</b>
				584	%subtmp = sub double %x3, 1.000000e+00
				585	%calltmp = call double @fib( double %subtmp )
				586	<b>%x4 = load double* %x1</b>
				587	%subtmp5 = sub double %x4, 2.000000e+00
				588	%calltmp6 = call double @fib( double %subtmp5 )
				589	%addtmp = add double %calltmp, %calltmp6
				590	br label %ifcont
				591
				592	ifcont: ; preds = %else, %then
				593	%iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
				594	ret double %iftmp
				595	}
				596	</pre>
				597	</div>
				598
				599	<p>Here there is only one variable (x, the input argument) but you can still
				600	see the extremely simple-minded code generation strategy we are using. In the
				601	entry block, an alloca is created, and the initial input value is stored into
				602	it. Each reference to the variable does a reload from the stack. Also, note
				603	that we didn't modify the if/then/else expression, so it still inserts a PHI
				604	node. While we could make an alloca for it, it is actually easier to create a
				605	PHI node for it, so we still just make the PHI.</p>
				606
				607	<p>Here is the code after the mem2reg pass runs:</p>
				608
				609	<div class="doc_code">
				610	<pre>
				611	define double @fib(double %x) {
				612	entry:
				613	%cmptmp = fcmp ult double <b>%x</b>, 3.000000e+00
				614	%booltmp = uitofp i1 %cmptmp to double
				615	%ifcond = fcmp one double %booltmp, 0.000000e+00
				616	br i1 %ifcond, label %then, label %else
				617
				618	then:
				619	br label %ifcont
				620
				621	else:
				622	%subtmp = sub double <b>%x</b>, 1.000000e+00
				623	%calltmp = call double @fib( double %subtmp )
				624	%subtmp5 = sub double <b>%x</b>, 2.000000e+00
				625	%calltmp6 = call double @fib( double %subtmp5 )
				626	%addtmp = add double %calltmp, %calltmp6
				627	br label %ifcont
				628
				629	ifcont: ; preds = %else, %then
				630	%iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
				631	ret double %iftmp
				632	}
				633	</pre>
				634	</div>
				635
				636	<p>This is a trivial case for mem2reg, since there are no redefinitions of the
				637	variable. The point of showing this is to calm your tension about inserting
				638	such blatent inefficiencies :).</p>
				639
				640	<p>After the rest of the optimizers run, we get:</p>
				641
				642	<div class="doc_code">
				643	<pre>
				644	define double @fib(double %x) {
				645	entry:
				646	%cmptmp = fcmp ult double %x, 3.000000e+00
				647	%booltmp = uitofp i1 %cmptmp to double
				648	%ifcond = fcmp ueq double %booltmp, 0.000000e+00
				649	br i1 %ifcond, label %else, label %ifcont
				650
				651	else:
				652	%subtmp = sub double %x, 1.000000e+00
				653	%calltmp = call double @fib( double %subtmp )
				654	%subtmp5 = sub double %x, 2.000000e+00
				655	%calltmp6 = call double @fib( double %subtmp5 )
				656	%addtmp = add double %calltmp, %calltmp6
				657	ret double %addtmp
				658
				659	ifcont:
				660	ret double 1.000000e+00
				661	}
				662	</pre>
				663	</div>
				664
				665	<p>Here we see that the simplifycfg pass decided to clone the return instruction
				666	into the end of the 'else' block. This allowed it to eliminate some branches
				667	and the PHI node.</p>
				668
				669	<p>Now that all symbol table references are updated to use stack variables,
				670	we'll add the assignment operator.</p>
				671
				672	</div>
				673
				674	<!-- *********************************************************************** -->
				675	<div class="doc_section"><a name="assignment">New Assignment Operator</a></div>
				676	<!-- *********************************************************************** -->
				677
				678	<div class="doc_text">
				679
				680	<p>With our current framework, adding a new assignment operator is really
				681	simple. We will parse it just like any other binary operator, but handle it
				682	internally (instead of allowing the user to define it). The first step is to
				683	set a precedence:</p>
				684
				685	<div class="doc_code">
				686	<pre>
				687	let main () =
				688	(* Install standard binary operators.
				689	* 1 is the lowest precedence. *)
				690	<b>Hashtbl.add Parser.binop_precedence '=' 2;</b>
				691	Hashtbl.add Parser.binop_precedence '<' 10;
				692	Hashtbl.add Parser.binop_precedence '+' 20;
				693	Hashtbl.add Parser.binop_precedence '-' 20;
				694	...
				695	</pre>
				696	</div>
				697
				698	<p>Now that the parser knows the precedence of the binary operator, it takes
				699	care of all the parsing and AST generation. We just need to implement codegen
				700	for the assignment operator. This looks like:</p>
				701
				702	<div class="doc_code">
				703	<pre>
				704	let rec codegen_expr = function
				705	begin match op with
				706	\| '=' ->
				707	(* Special case '=' because we don't want to emit the LHS as an
				708	* expression. *)
				709	let name =
				710	match lhs with
				711	\| Ast.Variable name -> name
				712	\| _ -> raise (Error "destination of '=' must be a variable")
				713	in
				714	</pre>
				715	</div>
				716
				717	<p>Unlike the rest of the binary operators, our assignment operator doesn't
				718	follow the "emit LHS, emit RHS, do computation" model. As such, it is handled
				719	as a special case before the other binary operators are handled. The other
				720	strange thing is that it requires the LHS to be a variable. It is invalid to
				721	have "(x+1) = expr" - only things like "x = expr" are allowed.
				722	</p>
				723
				724
				725	<div class="doc_code">
				726	<pre>
				727	(* Codegen the rhs. *)
				728	let val_ = codegen_expr rhs in
				729
				730	(* Lookup the name. *)
				731	let variable = try Hashtbl.find named_values name with
				732	\| Not_found -> raise (Error "unknown variable name")
				733	in
				734	ignore(build_store val_ variable builder);
				735	val_
				736	\| _ ->
				737	...
				738	</pre>
				739	</div>
				740
				741	<p>Once we have the variable, codegen'ing the assignment is straightforward:
				742	we emit the RHS of the assignment, create a store, and return the computed
				743	value. Returning a value allows for chained assignments like "X = (Y = Z)".</p>
				744
				745	<p>Now that we have an assignment operator, we can mutate loop variables and
				746	arguments. For example, we can now run code like this:</p>
				747
				748	<div class="doc_code">
				749	<pre>
				750	# Function to print a double.
				751	extern printd(x);
				752
				753	# Define ':' for sequencing: as a low-precedence operator that ignores operands
				754	# and just returns the RHS.
				755	def binary : 1 (x y) y;
				756
				757	def test(x)
				758	printd(x) :
				759	x = 4 :
				760	printd(x);
				761
				762	test(123);
				763	</pre>
				764	</div>
				765
				766	<p>When run, this example prints "123" and then "4", showing that we did
				767	actually mutate the value! Okay, we have now officially implemented our goal:
				768	getting this to work requires SSA construction in the general case. However,
				769	to be really useful, we want the ability to define our own local variables, lets
				770	add this next!
				771	</p>
				772
				773	</div>
				774
				775	<!-- *********************************************************************** -->
				776	<div class="doc_section"><a name="localvars">User-defined Local
				777	Variables</a></div>
				778	<!-- *********************************************************************** -->
				779
				780	<div class="doc_text">
				781
				782	<p>Adding var/in is just like any other other extensions we made to
				783	Kaleidoscope: we extend the lexer, the parser, the AST and the code generator.
				784	The first step for adding our new 'var/in' construct is to extend the lexer.
				785	As before, this is pretty trivial, the code looks like this:</p>
				786
				787	<div class="doc_code">
				788	<pre>
				789	type token =
				790	...
				791	<b>(* var definition *)
				792	\| Var</b>
				793
				794	...
				795
				796	and lex_ident buffer = parser
				797	...
				798	\| "in" -> [< 'Token.In; stream >]
				799	\| "binary" -> [< 'Token.Binary; stream >]
				800	\| "unary" -> [< 'Token.Unary; stream >]
				801	<b>\| "var" -> [< 'Token.Var; stream >]</b>
				802	...
				803	</pre>
				804	</div>
				805
				806	<p>The next step is to define the AST node that we will construct. For var/in,
				807	it looks like this:</p>
				808
				809	<div class="doc_code">
				810	<pre>
				811	type expr =
				812	...
				813	(* variant for var/in. *)
				814	\| Var of (string * expr option) array * expr
				815	...
				816	</pre>
				817	</div>
				818
				819	<p>var/in allows a list of names to be defined all at once, and each name can
				820	optionally have an initializer value. As such, we capture this information in
				821	the VarNames vector. Also, var/in has a body, this body is allowed to access
				822	the variables defined by the var/in.</p>
				823
				824	<p>With this in place, we can define the parser pieces. The first thing we do
				825	is add it as a primary expression:</p>
				826
				827	<div class="doc_code">
				828	<pre>
				829	(* primary
				830	* ::= identifier
				831	* ::= numberexpr
				832	* ::= parenexpr
				833	* ::= ifexpr
				834	* ::= forexpr
				835	<b>* ::= varexpr</b> *)
				836	let rec parse_primary = parser
				837	...
				838	<b>(* varexpr
				839	* ::= 'var' identifier ('=' expression?
				840	* (',' identifier ('=' expression)?)* 'in' expression *)
				841	\| [< 'Token.Var;
				842	(* At least one variable name is required. *)
				843	'Token.Ident id ?? "expected identifier after var";
				844	init=parse_var_init;
				845	var_names=parse_var_names [(id, init)];
				846	(* At this point, we have to have 'in'. *)
				847	'Token.In ?? "expected 'in' keyword after 'var'";
				848	body=parse_expr >] ->
				849	Ast.Var (Array.of_list (List.rev var_names), body)</b>
				850
				851	...
				852
				853	and parse_var_init = parser
				854	(* read in the optional initializer. *)
				855	\| [< 'Token.Kwd '='; e=parse_expr >] -> Some e
				856	\| [< >] -> None
				857
				858	and parse_var_names accumulator = parser
				859	\| [< 'Token.Kwd ',';
				860	'Token.Ident id ?? "expected identifier list after var";
				861	init=parse_var_init;
				862	e=parse_var_names ((id, init) :: accumulator) >] -> e
				863	\| [< >] -> accumulator
				864	</pre>
				865	</div>
				866
				867	<p>Now that we can parse and represent the code, we need to support emission of
				868	LLVM IR for it. This code starts out with:</p>
				869
				870	<div class="doc_code">
				871	<pre>
				872	let rec codegen_expr = function
				873	...
				874	\| Ast.Var (var_names, body)
				875	let old_bindings = ref [] in
				876
				877	let the_function = block_parent (insertion_block builder) in
				878
				879	(* Register all variables and emit their initializer. *)
				880	Array.iter (fun (var_name, init) ->
				881	</pre>
				882	</div>
				883
				884	<p>Basically it loops over all the variables, installing them one at a time.
				885	For each variable we put into the symbol table, we remember the previous value
				886	that we replace in OldBindings.</p>
				887
				888	<div class="doc_code">
				889	<pre>
				890	(* Emit the initializer before adding the variable to scope, this
				891	* prevents the initializer from referencing the variable itself, and
				892	* permits stuff like this:
				893	* var a = 1 in
				894	* var a = a in ... # refers to outer 'a'. *)
				895	let init_val =
				896	match init with
				897	\| Some init -> codegen_expr init
				898	(* If not specified, use 0.0. *)
				899	\| None -> const_float double_type 0.0
				900	in
				901
				902	let alloca = create_entry_block_alloca the_function var_name in
				903	ignore(build_store init_val alloca builder);
				904
				905	(* Remember the old variable binding so that we can restore the binding
				906	* when we unrecurse. *)
				907
				908	begin
				909	try
				910	let old_value = Hashtbl.find named_values var_name in
				911	old_bindings := (var_name, old_value) :: !old_bindings;
				912	with Not_found > ()
				913	end;
				914
				915	(* Remember this binding. *)
				916	Hashtbl.add named_values var_name alloca;
				917	) var_names;
				918	</pre>
				919	</div>
				920
				921	<p>There are more comments here than code. The basic idea is that we emit the
				922	initializer, create the alloca, then update the symbol table to point to it.
				923	Once all the variables are installed in the symbol table, we evaluate the body
				924	of the var/in expression:</p>
				925
				926	<div class="doc_code">
				927	<pre>
				928	(* Codegen the body, now that all vars are in scope. *)
				929	let body_val = codegen_expr body in
				930	</pre>
				931	</div>
				932
				933	<p>Finally, before returning, we restore the previous variable bindings:</p>
				934
				935	<div class="doc_code">
				936	<pre>
				937	(* Pop all our variables from scope. *)
				938	List.iter (fun (var_name, old_value) ->
				939	Hashtbl.add named_values var_name old_value
				940	) !old_bindings;
				941
				942	(* Return the body computation. *)
				943	body_val
				944	</pre>
				945	</div>
				946
				947	<p>The end result of all of this is that we get properly scoped variable
				948	definitions, and we even (trivially) allow mutation of them :).</p>
				949
				950	<p>With this, we completed what we set out to do. Our nice iterative fib
				951	example from the intro compiles and runs just fine. The mem2reg pass optimizes
				952	all of our stack variables into SSA registers, inserting PHI nodes where needed,
				953	and our front-end remains simple: no "iterated dominance frontier" computation
				954	anywhere in sight.</p>
				955
				956	</div>
				957
				958	<!-- *********************************************************************** -->
				959	<div class="doc_section"><a name="code">Full Code Listing</a></div>
				960	<!-- *********************************************************************** -->
				961
				962	<div class="doc_text">
				963
				964	<p>
				965	Here is the complete code listing for our running example, enhanced with mutable
				966	variables and var/in support. To build this example, use:
				967	</p>
				968
				969	<div class="doc_code">
				970	<pre>
				971	# Compile
				972	ocamlbuild toy.byte
				973	# Run
				974	./toy.byte
				975	</pre>
				976	</div>
				977
				978	<p>Here is the code:</p>
				979
				980	<dl>
				981	<dt>_tags:</dt>
				982	<dd class="doc_code">
				983	<pre>
				984	<{lexer,parser}.ml>: use_camlp4, pp(camlp4of)
				985	<*.{byte,native}>: g++, use_llvm, use_llvm_analysis
				986	<*.{byte,native}>: use_llvm_executionengine, use_llvm_target
				987	<*.{byte,native}>: use_llvm_scalar_opts, use_bindings
				988	</pre>
				989	</dd>
				990
				991	<dt>myocamlbuild.ml:</dt>
				992	<dd class="doc_code">
				993	<pre>
				994	open Ocamlbuild_plugin;;
				995
				996	ocaml_lib ~extern:true "llvm";;
				997	ocaml_lib ~extern:true "llvm_analysis";;
				998	ocaml_lib ~extern:true "llvm_executionengine";;
				999	ocaml_lib ~extern:true "llvm_target";;
				1000	ocaml_lib ~extern:true "llvm_scalar_opts";;
				1001
				1002	flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
				1003	dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
				1004	</pre>
				1005	</dd>
				1006
				1007	<dt>token.ml:</dt>
				1008	<dd class="doc_code">
				1009	<pre>
				1010	(*===----------------------------------------------------------------------===
				1011	* Lexer Tokens
				1012	===----------------------------------------------------------------------===)
				1013
				1014	(* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
				1015	* these others for known things. *)
				1016	type token =
				1017	(* commands *)
				1018	\| Def \| Extern
				1019
				1020	(* primary *)
				1021	\| Ident of string \| Number of float
				1022
				1023	(* unknown *)
				1024	\| Kwd of char
				1025
				1026	(* control *)
				1027	\| If \| Then \| Else
				1028	\| For \| In
				1029
				1030	(* operators *)
				1031	\| Binary \| Unary
				1032
				1033	(* var definition *)
				1034	\| Var
				1035	</pre>
				1036	</dd>
				1037
				1038	<dt>lexer.ml:</dt>
				1039	<dd class="doc_code">
				1040	<pre>
				1041	(*===----------------------------------------------------------------------===
				1042	* Lexer
				1043	===----------------------------------------------------------------------===)
				1044
				1045	let rec lex = parser
				1046	(* Skip any whitespace. *)
				1047	\| [< ' (' ' \| '\n' \| '\r' \| '\t'); stream >] -> lex stream
				1048
				1049	(* identifier: [a-zA-Z][a-zA-Z0-9] *)
				1050	\| [< ' ('A' .. 'Z' \| 'a' .. 'z' as c); stream >] ->
				1051	let buffer = Buffer.create 1 in
				1052	Buffer.add_char buffer c;
				1053	lex_ident buffer stream
				1054
				1055	(* number: [0-9.]+ *)
				1056	\| [< ' ('0' .. '9' as c); stream >] ->
				1057	let buffer = Buffer.create 1 in
				1058	Buffer.add_char buffer c;
				1059	lex_number buffer stream
				1060
				1061	(* Comment until end of line. *)
				1062	\| [< ' ('#'); stream >] ->
				1063	lex_comment stream
				1064
				1065	(* Otherwise, just return the character as its ascii value. *)
				1066	\| [< 'c; stream >] ->
				1067	[< 'Token.Kwd c; lex stream >]
				1068
				1069	(* end of stream. *)
				1070	\| [< >] -> [< >]
				1071
				1072	and lex_number buffer = parser
				1073	\| [< ' ('0' .. '9' \| '.' as c); stream >] ->
				1074	Buffer.add_char buffer c;
				1075	lex_number buffer stream
				1076	\| [< stream=lex >] ->
				1077	[< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >]
				1078
				1079	and lex_ident buffer = parser
				1080	\| [< ' ('A' .. 'Z' \| 'a' .. 'z' \| '0' .. '9' as c); stream >] ->
				1081	Buffer.add_char buffer c;
				1082	lex_ident buffer stream
				1083	\| [< stream=lex >] ->
				1084	match Buffer.contents buffer with
				1085	\| "def" -> [< 'Token.Def; stream >]
				1086	\| "extern" -> [< 'Token.Extern; stream >]
				1087	\| "if" -> [< 'Token.If; stream >]
				1088	\| "then" -> [< 'Token.Then; stream >]
				1089	\| "else" -> [< 'Token.Else; stream >]
				1090	\| "for" -> [< 'Token.For; stream >]
				1091	\| "in" -> [< 'Token.In; stream >]
				1092	\| "binary" -> [< 'Token.Binary; stream >]
				1093	\| "unary" -> [< 'Token.Unary; stream >]
				1094	\| "var" -> [< 'Token.Var; stream >]
				1095	\| id -> [< 'Token.Ident id; stream >]
				1096
				1097	and lex_comment = parser
				1098	\| [< ' ('\n'); stream=lex >] -> stream
				1099	\| [< 'c; e=lex_comment >] -> e
				1100	\| [< >] -> [< >]
				1101	</pre>
				1102	</dd>
				1103
				1104	<dt>ast.ml:</dt>
				1105	<dd class="doc_code">
				1106	<pre>
				1107	(*===----------------------------------------------------------------------===
				1108	* Abstract Syntax Tree (aka Parse Tree)
				1109	===----------------------------------------------------------------------===)
				1110
				1111	(* expr - Base type for all expression nodes. *)
				1112	type expr =
				1113	(* variant for numeric literals like "1.0". *)
				1114	\| Number of float
				1115
				1116	(* variant for referencing a variable, like "a". *)
				1117	\| Variable of string
				1118
				1119	(* variant for a unary operator. *)
				1120	\| Unary of char * expr
				1121
				1122	(* variant for a binary operator. *)
				1123	\| Binary of char * expr * expr
				1124
				1125	(* variant for function calls. *)
				1126	\| Call of string * expr array
				1127
				1128	(* variant for if/then/else. *)
				1129	\| If of expr * expr * expr
				1130
				1131	(* variant for for/in. *)
				1132	\| For of string * expr * expr * expr option * expr
				1133
				1134	(* variant for var/in. *)
				1135	\| Var of (string * expr option) array * expr
				1136
				1137	(* proto - This type represents the "prototype" for a function, which captures
				1138	* its name, and its argument names (thus implicitly the number of arguments the
				1139	* function takes). *)
				1140	type proto =
				1141	\| Prototype of string * string array
				1142	\| BinOpPrototype of string * string array * int
				1143
				1144	(* func - This type represents a function definition itself. *)
				1145	type func = Function of proto * expr
				1146	</pre>
				1147	</dd>
				1148
				1149	<dt>parser.ml:</dt>
				1150	<dd class="doc_code">
				1151	<pre>
				1152	(*===---------------------------------------------------------------------===
				1153	* Parser
				1154	===---------------------------------------------------------------------===)
				1155
				1156	(* binop_precedence - This holds the precedence for each binary operator that is
				1157	* defined *)
				1158	let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
				1159
				1160	(* precedence - Get the precedence of the pending binary operator token. *)
				1161	let precedence c = try Hashtbl.find binop_precedence c with Not_found -> -1
				1162
				1163	(* primary
				1164	* ::= identifier
				1165	* ::= numberexpr
				1166	* ::= parenexpr
				1167	* ::= ifexpr
				1168	* ::= forexpr
				1169	* ::= varexpr *)
				1170	let rec parse_primary = parser
				1171	(* numberexpr ::= number *)
				1172	\| [< 'Token.Number n >] -> Ast.Number n
				1173
				1174	(* parenexpr ::= '(' expression ')' *)
				1175	\| [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
				1176
				1177	(* identifierexpr
				1178	* ::= identifier
				1179	* ::= identifier '(' argumentexpr ')' *)
				1180	\| [< 'Token.Ident id; stream >] ->
				1181	let rec parse_args accumulator = parser
				1182	\| [< e=parse_expr; stream >] ->
				1183	begin parser
				1184	\| [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
				1185	\| [< >] -> e :: accumulator
				1186	end stream
				1187	\| [< >] -> accumulator
				1188	in
				1189	let rec parse_ident id = parser
				1190	(* Call. *)
				1191	\| [< 'Token.Kwd '(';
				1192	args=parse_args [];
				1193	'Token.Kwd ')' ?? "expected ')'">] ->
				1194	Ast.Call (id, Array.of_list (List.rev args))
				1195
				1196	(* Simple variable ref. *)
				1197	\| [< >] -> Ast.Variable id
				1198	in
				1199	parse_ident id stream
				1200
				1201	(* ifexpr ::= 'if' expr 'then' expr 'else' expr *)
				1202	\| [< 'Token.If; c=parse_expr;
				1203	'Token.Then ?? "expected 'then'"; t=parse_expr;
				1204	'Token.Else ?? "expected 'else'"; e=parse_expr >] ->
				1205	Ast.If (c, t, e)
				1206
				1207	(* forexpr
				1208	::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression *)
				1209	\| [< 'Token.For;
				1210	'Token.Ident id ?? "expected identifier after for";
				1211	'Token.Kwd '=' ?? "expected '=' after for";
				1212	stream >] ->
				1213	begin parser
				1214	\| [<
				1215	start=parse_expr;
				1216	'Token.Kwd ',' ?? "expected ',' after for";
				1217	end_=parse_expr;
				1218	stream >] ->
				1219	let step =
				1220	begin parser
				1221	\| [< 'Token.Kwd ','; step=parse_expr >] -> Some step
				1222	\| [< >] -> None
				1223	end stream
				1224	in
				1225	begin parser
				1226	\| [< 'Token.In; body=parse_expr >] ->
				1227	Ast.For (id, start, end_, step, body)
				1228	\| [< >] ->
				1229	raise (Stream.Error "expected 'in' after for")
				1230	end stream
				1231	\| [< >] ->
				1232	raise (Stream.Error "expected '=' after for")
				1233	end stream
				1234
				1235	(* varexpr
				1236	* ::= 'var' identifier ('=' expression?
				1237	* (',' identifier ('=' expression)?)* 'in' expression *)
				1238	\| [< 'Token.Var;
				1239	(* At least one variable name is required. *)
				1240	'Token.Ident id ?? "expected identifier after var";
				1241	init=parse_var_init;
				1242	var_names=parse_var_names [(id, init)];
				1243	(* At this point, we have to have 'in'. *)
				1244	'Token.In ?? "expected 'in' keyword after 'var'";
				1245	body=parse_expr >] ->
				1246	Ast.Var (Array.of_list (List.rev var_names), body)
				1247
				1248	\| [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
				1249
				1250	(* unary
				1251	* ::= primary
				1252	* ::= '!' unary *)
				1253	and parse_unary = parser
				1254	(* If this is a unary operator, read it. *)
				1255	\| [< 'Token.Kwd op when op != '(' && op != ')'; operand=parse_expr >] ->
				1256	Ast.Unary (op, operand)
				1257
				1258	(* If the current token is not an operator, it must be a primary expr. *)
				1259	\| [< stream >] -> parse_primary stream
				1260
				1261	(* binoprhs
				1262	* ::= ('+' primary)* *)
				1263	and parse_bin_rhs expr_prec lhs stream =
				1264	match Stream.peek stream with
				1265	(* If this is a binop, find its precedence. *)
				1266	\| Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
				1267	let token_prec = precedence c in
				1268
				1269	(* If this is a binop that binds at least as tightly as the current binop,
				1270	* consume it, otherwise we are done. *)
				1271	if token_prec < expr_prec then lhs else begin
				1272	(* Eat the binop. *)
				1273	Stream.junk stream;
				1274
				1275	(* Parse the primary expression after the binary operator. *)
				1276	let rhs = parse_unary stream in
				1277
				1278	(* Okay, we know this is a binop. *)
				1279	let rhs =
				1280	match Stream.peek stream with
				1281	\| Some (Token.Kwd c2) ->
				1282	(* If BinOp binds less tightly with rhs than the operator after
				1283	* rhs, let the pending operator take rhs as its lhs. *)
				1284	let next_prec = precedence c2 in
				1285	if token_prec < next_prec
				1286	then parse_bin_rhs (token_prec + 1) rhs stream
				1287	else rhs
				1288	\| _ -> rhs
				1289	in
				1290
				1291	(* Merge lhs/rhs. *)
				1292	let lhs = Ast.Binary (c, lhs, rhs) in
				1293	parse_bin_rhs expr_prec lhs stream
				1294	end
				1295	\| _ -> lhs
				1296
				1297	and parse_var_init = parser
				1298	(* read in the optional initializer. *)
				1299	\| [< 'Token.Kwd '='; e=parse_expr >] -> Some e
				1300	\| [< >] -> None
				1301
				1302	and parse_var_names accumulator = parser
				1303	\| [< 'Token.Kwd ',';
				1304	'Token.Ident id ?? "expected identifier list after var";
				1305	init=parse_var_init;
				1306	e=parse_var_names ((id, init) :: accumulator) >] -> e
				1307	\| [< >] -> accumulator
				1308
				1309	(* expression
				1310	* ::= primary binoprhs *)
				1311	and parse_expr = parser
				1312	\| [< lhs=parse_unary; stream >] -> parse_bin_rhs 0 lhs stream
				1313
				1314	(* prototype
				1315	* ::= id '(' id* ')'
				1316	* ::= binary LETTER number? (id, id)
				1317	* ::= unary LETTER number? (id) *)
				1318	let parse_prototype =
				1319	let rec parse_args accumulator = parser
				1320	\| [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
				1321	\| [< >] -> accumulator
				1322	in
				1323	let parse_operator = parser
				1324	\| [< 'Token.Unary >] -> "unary", 1
				1325	\| [< 'Token.Binary >] -> "binary", 2
				1326	in
				1327	let parse_binary_precedence = parser
				1328	\| [< 'Token.Number n >] -> int_of_float n
				1329	\| [< >] -> 30
				1330	in
				1331	parser
				1332	\| [< 'Token.Ident id;
				1333	'Token.Kwd '(' ?? "expected '(' in prototype";
				1334	args=parse_args [];
				1335	'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
				1336	(* success. *)
				1337	Ast.Prototype (id, Array.of_list (List.rev args))
				1338	\| [< (prefix, kind)=parse_operator;
				1339	'Token.Kwd op ?? "expected an operator";
				1340	(* Read the precedence if present. *)
				1341	binary_precedence=parse_binary_precedence;
				1342	'Token.Kwd '(' ?? "expected '(' in prototype";
				1343	args=parse_args [];
				1344	'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
				1345	let name = prefix ^ (String.make 1 op) in
				1346	let args = Array.of_list (List.rev args) in
				1347
				1348	(* Verify right number of arguments for operator. *)
				1349	if Array.length args != kind
				1350	then raise (Stream.Error "invalid number of operands for operator")
				1351	else
				1352	if kind == 1 then
				1353	Ast.Prototype (name, args)
				1354	else
				1355	Ast.BinOpPrototype (name, args, binary_precedence)
				1356	\| [< >] ->
				1357	raise (Stream.Error "expected function name in prototype")
				1358
				1359	(* definition ::= 'def' prototype expression *)
				1360	let parse_definition = parser
				1361	\| [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
				1362	Ast.Function (p, e)
				1363
				1364	(* toplevelexpr ::= expression *)
				1365	let parse_toplevel = parser
				1366	\| [< e=parse_expr >] ->
				1367	(* Make an anonymous proto. *)
				1368	Ast.Function (Ast.Prototype ("", [\|\|]), e)
				1369
				1370	(* external ::= 'extern' prototype *)
				1371	let parse_extern = parser
				1372	\| [< 'Token.Extern; e=parse_prototype >] -> e
				1373	</pre>
				1374	</dd>
				1375
				1376	<dt>codegen.ml:</dt>
				1377	<dd class="doc_code">
				1378	<pre>
				1379	(*===----------------------------------------------------------------------===
				1380	* Code Generation
				1381	===----------------------------------------------------------------------===)
				1382
				1383	open Llvm
				1384
				1385	exception Error of string
				1386
				1387	let the_module = create_module "my cool jit"
				1388	let builder = builder ()
				1389	let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
				1390
				1391	(* Create an alloca instruction in the entry block of the function. This
				1392	* is used for mutable variables etc. *)
				1393	let create_entry_block_alloca the_function var_name =
				1394	let builder = builder_at (instr_begin (entry_block the_function)) in
				1395	build_alloca double_type var_name builder
				1396
				1397	let rec codegen_expr = function
				1398	\| Ast.Number n -> const_float double_type n
				1399	\| Ast.Variable name ->
				1400	let v = try Hashtbl.find named_values name with
				1401	\| Not_found -> raise (Error "unknown variable name")
				1402	in
				1403	(* Load the value. *)
				1404	build_load v name builder
				1405	\| Ast.Unary (op, operand) ->
				1406	let operand = codegen_expr operand in
				1407	let callee = "unary" ^ (String.make 1 op) in
				1408	let callee =
				1409	match lookup_function callee the_module with
				1410	\| Some callee -> callee
				1411	\| None -> raise (Error "unknown unary operator")
				1412	in
				1413	build_call callee [\|operand\|] "unop" builder
				1414	\| Ast.Binary (op, lhs, rhs) ->
				1415	begin match op with
				1416	\| '=' ->
				1417	(* Special case '=' because we don't want to emit the LHS as an
				1418	* expression. *)
				1419	let name =
				1420	match lhs with
				1421	\| Ast.Variable name -> name
				1422	\| _ -> raise (Error "destination of '=' must be a variable")
				1423	in
				1424
				1425	(* Codegen the rhs. *)
				1426	let val_ = codegen_expr rhs in
				1427
				1428	(* Lookup the name. *)
				1429	let variable = try Hashtbl.find named_values name with
				1430	\| Not_found -> raise (Error "unknown variable name")
				1431	in
				1432	ignore(build_store val_ variable builder);
				1433	val_
				1434	\| _ ->
				1435	let lhs_val = codegen_expr lhs in
				1436	let rhs_val = codegen_expr rhs in
				1437	begin
				1438	match op with
				1439	\| '+' -> build_add lhs_val rhs_val "addtmp" builder
				1440	\| '-' -> build_sub lhs_val rhs_val "subtmp" builder
				1441	\| '*' -> build_mul lhs_val rhs_val "multmp" builder
				1442	\| '<' ->
				1443	(* Convert bool 0/1 to double 0.0 or 1.0 *)
				1444	let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
				1445	build_uitofp i double_type "booltmp" builder
				1446	\| _ ->
				1447	(* If it wasn't a builtin binary operator, it must be a user defined
				1448	* one. Emit a call to it. *)
				1449	let callee = "binary" ^ (String.make 1 op) in
				1450	let callee =
				1451	match lookup_function callee the_module with
				1452	\| Some callee -> callee
				1453	\| None -> raise (Error "binary operator not found!")
				1454	in
				1455	build_call callee [\|lhs_val; rhs_val\|] "binop" builder
				1456	end
				1457	end
				1458	\| Ast.Call (callee, args) ->
				1459	(* Look up the name in the module table. *)
				1460	let callee =
				1461	match lookup_function callee the_module with
				1462	\| Some callee -> callee
				1463	\| None -> raise (Error "unknown function referenced")
				1464	in
				1465	let params = params callee in
				1466
				1467	(* If argument mismatch error. *)
				1468	if Array.length params == Array.length args then () else
				1469	raise (Error "incorrect # arguments passed");
				1470	let args = Array.map codegen_expr args in
				1471	build_call callee args "calltmp" builder
				1472	\| Ast.If (cond, then_, else_) ->
				1473	let cond = codegen_expr cond in
				1474
				1475	(* Convert condition to a bool by comparing equal to 0.0 *)
				1476	let zero = const_float double_type 0.0 in
				1477	let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
				1478
				1479	(* Grab the first block so that we might later add the conditional branch
				1480	* to it at the end of the function. *)
				1481	let start_bb = insertion_block builder in
				1482	let the_function = block_parent start_bb in
				1483
				1484	let then_bb = append_block "then" the_function in
				1485
				1486	(* Emit 'then' value. *)
				1487	position_at_end then_bb builder;
				1488	let then_val = codegen_expr then_ in
				1489
				1490	(* Codegen of 'then' can change the current block, update then_bb for the
				1491	* phi. We create a new name because one is used for the phi node, and the
				1492	* other is used for the conditional branch. *)
				1493	let new_then_bb = insertion_block builder in
				1494
				1495	(* Emit 'else' value. *)
				1496	let else_bb = append_block "else" the_function in
				1497	position_at_end else_bb builder;
				1498	let else_val = codegen_expr else_ in
				1499
				1500	(* Codegen of 'else' can change the current block, update else_bb for the
				1501	* phi. *)
				1502	let new_else_bb = insertion_block builder in
				1503
				1504	(* Emit merge block. *)
				1505	let merge_bb = append_block "ifcont" the_function in
				1506	position_at_end merge_bb builder;
				1507	let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
				1508	let phi = build_phi incoming "iftmp" builder in
				1509
				1510	(* Return to the start block to add the conditional branch. *)
				1511	position_at_end start_bb builder;
				1512	ignore (build_cond_br cond_val then_bb else_bb builder);
				1513
				1514	(* Set a unconditional branch at the end of the 'then' block and the
				1515	* 'else' block to the 'merge' block. *)
				1516	position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
				1517	position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
				1518
				1519	(* Finally, set the builder to the end of the merge block. *)
				1520	position_at_end merge_bb builder;
				1521
				1522	phi
				1523	\| Ast.For (var_name, start, end_, step, body) ->
				1524	(* Output this as:
				1525	* var = alloca double
				1526	* ...
				1527	* start = startexpr
				1528	* store start -> var
				1529	* goto loop
				1530	* loop:
				1531	* ...
				1532	* bodyexpr
				1533	* ...
				1534	* loopend:
				1535	* step = stepexpr
				1536	* endcond = endexpr
				1537	*
				1538	* curvar = load var
				1539	* nextvar = curvar + step
				1540	* store nextvar -> var
				1541	* br endcond, loop, endloop
				1542	* outloop: *)
				1543
				1544	let the_function = block_parent (insertion_block builder) in
				1545
				1546	(* Create an alloca for the variable in the entry block. *)
				1547	let alloca = create_entry_block_alloca the_function var_name in
				1548
				1549	(* Emit the start code first, without 'variable' in scope. *)
				1550	let start_val = codegen_expr start in
				1551
				1552	(* Store the value into the alloca. *)
				1553	ignore(build_store start_val alloca builder);
				1554
				1555	(* Make the new basic block for the loop header, inserting after current
				1556	* block. *)
				1557	let loop_bb = append_block "loop" the_function in
				1558
				1559	(* Insert an explicit fall through from the current block to the
				1560	* loop_bb. *)
				1561	ignore (build_br loop_bb builder);
				1562
				1563	(* Start insertion in loop_bb. *)
				1564	position_at_end loop_bb builder;
				1565
				1566	(* Within the loop, the variable is defined equal to the PHI node. If it
				1567	* shadows an existing variable, we have to restore it, so save it
				1568	* now. *)
				1569	let old_val =
				1570	try Some (Hashtbl.find named_values var_name) with Not_found -> None
				1571	in
				1572	Hashtbl.add named_values var_name alloca;
				1573
				1574	(* Emit the body of the loop. This, like any other expr, can change the
				1575	* current BB. Note that we ignore the value computed by the body, but
				1576	* don't allow an error *)
				1577	ignore (codegen_expr body);
				1578
				1579	(* Emit the step value. *)
				1580	let step_val =
				1581	match step with
				1582	\| Some step -> codegen_expr step
				1583	(* If not specified, use 1.0. *)
				1584	\| None -> const_float double_type 1.0
				1585	in
				1586
				1587	(* Compute the end condition. *)
				1588	let end_cond = codegen_expr end_ in
				1589
				1590	(* Reload, increment, and restore the alloca. This handles the case where
				1591	* the body of the loop mutates the variable. *)
				1592	let cur_var = build_load alloca var_name builder in
				1593	let next_var = build_add cur_var step_val "nextvar" builder in
				1594	ignore(build_store next_var alloca builder);
				1595
				1596	(* Convert condition to a bool by comparing equal to 0.0. *)
				1597	let zero = const_float double_type 0.0 in
				1598	let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
				1599
				1600	(* Create the "after loop" block and insert it. *)
				1601	let after_bb = append_block "afterloop" the_function in
				1602
				1603	(* Insert the conditional branch into the end of loop_end_bb. *)
				1604	ignore (build_cond_br end_cond loop_bb after_bb builder);
				1605
				1606	(* Any new code will be inserted in after_bb. *)
				1607	position_at_end after_bb builder;
				1608
				1609	(* Restore the unshadowed variable. *)
				1610	begin match old_val with
				1611	\| Some old_val -> Hashtbl.add named_values var_name old_val
				1612	\| None -> ()
				1613	end;
				1614
				1615	(* for expr always returns 0.0. *)
				1616	const_null double_type
				1617	\| Ast.Var (var_names, body) ->
				1618	let old_bindings = ref [] in
				1619
				1620	let the_function = block_parent (insertion_block builder) in
				1621
				1622	(* Register all variables and emit their initializer. *)
				1623	Array.iter (fun (var_name, init) ->
				1624	(* Emit the initializer before adding the variable to scope, this
				1625	* prevents the initializer from referencing the variable itself, and
				1626	* permits stuff like this:
				1627	* var a = 1 in
				1628	* var a = a in ... # refers to outer 'a'. *)
				1629	let init_val =
				1630	match init with
				1631	\| Some init -> codegen_expr init
				1632	(* If not specified, use 0.0. *)
				1633	\| None -> const_float double_type 0.0
				1634	in
				1635
				1636	let alloca = create_entry_block_alloca the_function var_name in
				1637	ignore(build_store init_val alloca builder);
				1638
				1639	(* Remember the old variable binding so that we can restore the binding
				1640	* when we unrecurse. *)
				1641	begin
				1642	try
				1643	let old_value = Hashtbl.find named_values var_name in
				1644	old_bindings := (var_name, old_value) :: !old_bindings;
				1645	with Not_found -> ()
				1646	end;
				1647
				1648	(* Remember this binding. *)
				1649	Hashtbl.add named_values var_name alloca;
				1650	) var_names;
				1651
				1652	(* Codegen the body, now that all vars are in scope. *)
				1653	let body_val = codegen_expr body in
				1654
				1655	(* Pop all our variables from scope. *)
				1656	List.iter (fun (var_name, old_value) ->
				1657	Hashtbl.add named_values var_name old_value
				1658	) !old_bindings;
				1659
				1660	(* Return the body computation. *)
				1661	body_val
				1662
				1663	let codegen_proto = function
				1664	\| Ast.Prototype (name, args) \| Ast.BinOpPrototype (name, args, _) ->
				1665	(* Make the function type: double(double,double) etc. *)
				1666	let doubles = Array.make (Array.length args) double_type in
				1667	let ft = function_type double_type doubles in
				1668	let f =
				1669	match lookup_function name the_module with
				1670	\| None -> declare_function name ft the_module
				1671
				1672	(* If 'f' conflicted, there was already something named 'name'. If it
				1673	* has a body, don't allow redefinition or reextern. *)
				1674	\| Some f ->
				1675	(* If 'f' already has a body, reject this. *)
				1676	if block_begin f <> At_end f then
				1677	raise (Error "redefinition of function");
				1678
				1679	(* If 'f' took a different number of arguments, reject. *)
				1680	if element_type (type_of f) <> ft then
				1681	raise (Error "redefinition of function with different # args");
				1682	f
				1683	in
				1684
				1685	(* Set names for all arguments. *)
				1686	Array.iteri (fun i a ->
				1687	let n = args.(i) in
				1688	set_value_name n a;
				1689	Hashtbl.add named_values n a;
				1690	) (params f);
				1691	f
				1692
				1693	(* Create an alloca for each argument and register the argument in the symbol
				1694	* table so that references to it will succeed. *)
				1695	let create_argument_allocas the_function proto =
				1696	let args = match proto with
				1697	\| Ast.Prototype (_, args) \| Ast.BinOpPrototype (_, args, _) -> args
				1698	in
				1699	Array.iteri (fun i ai ->
				1700	let var_name = args.(i) in
				1701	(* Create an alloca for this variable. *)
				1702	let alloca = create_entry_block_alloca the_function var_name in
				1703
				1704	(* Store the initial value into the alloca. *)
				1705	ignore(build_store ai alloca builder);
				1706
				1707	(* Add arguments to variable symbol table. *)
				1708	Hashtbl.add named_values var_name alloca;
				1709	) (params the_function)
				1710
				1711	let codegen_func the_fpm = function
				1712	\| Ast.Function (proto, body) ->
				1713	Hashtbl.clear named_values;
				1714	let the_function = codegen_proto proto in
				1715
				1716	(* If this is an operator, install it. *)
				1717	begin match proto with
				1718	\| Ast.BinOpPrototype (name, args, prec) ->
				1719	let op = name.[String.length name - 1] in
				1720	Hashtbl.add Parser.binop_precedence op prec;
				1721	\| _ -> ()
				1722	end;
				1723
				1724	(* Create a new basic block to start insertion into. *)
				1725	let bb = append_block "entry" the_function in
				1726	position_at_end bb builder;
				1727
				1728	try
				1729	(* Add all arguments to the symbol table and create their allocas. *)
				1730	create_argument_allocas the_function proto;
				1731
				1732	let ret_val = codegen_expr body in
				1733
				1734	(* Finish off the function. *)
				1735	let _ = build_ret ret_val builder in
				1736
				1737	(* Validate the generated code, checking for consistency. *)
				1738	Llvm_analysis.assert_valid_function the_function;
				1739
				1740	(* Optimize the function. *)
				1741	let _ = PassManager.run_function the_function the_fpm in
				1742
				1743	the_function
				1744	with e ->
				1745	delete_function the_function;
				1746	raise e
				1747	</pre>
				1748	</dd>
				1749
				1750	<dt>toplevel.ml:</dt>
				1751	<dd class="doc_code">
				1752	<pre>
				1753	(*===----------------------------------------------------------------------===
				1754	* Top-Level parsing and JIT Driver
				1755	===----------------------------------------------------------------------===)
				1756
				1757	open Llvm
				1758	open Llvm_executionengine
				1759
				1760	(* top ::= definition \| external \| expression \| ';' *)
				1761	let rec main_loop the_fpm the_execution_engine stream =
				1762	match Stream.peek stream with
				1763	\| None -> ()
				1764
				1765	(* ignore top-level semicolons. *)
				1766	\| Some (Token.Kwd ';') ->
				1767	Stream.junk stream;
				1768	main_loop the_fpm the_execution_engine stream
				1769
				1770	\| Some token ->
				1771	begin
				1772	try match token with
				1773	\| Token.Def ->
				1774	let e = Parser.parse_definition stream in
				1775	print_endline "parsed a function definition.";
				1776	dump_value (Codegen.codegen_func the_fpm e);
				1777	\| Token.Extern ->
				1778	let e = Parser.parse_extern stream in
				1779	print_endline "parsed an extern.";
				1780	dump_value (Codegen.codegen_proto e);
				1781	\| _ ->
				1782	(* Evaluate a top-level expression into an anonymous function. *)
				1783	let e = Parser.parse_toplevel stream in
				1784	print_endline "parsed a top-level expr";
				1785	let the_function = Codegen.codegen_func the_fpm e in
				1786	dump_value the_function;
				1787
				1788	(* JIT the function, returning a function pointer. *)
				1789	let result = ExecutionEngine.run_function the_function [\|\|]
				1790	the_execution_engine in
				1791
				1792	print_string "Evaluated to ";
				1793	print_float (GenericValue.as_float double_type result);
				1794	print_newline ();
				1795	with Stream.Error s \| Codegen.Error s ->
				1796	(* Skip token for error recovery. *)
				1797	Stream.junk stream;
				1798	print_endline s;
				1799	end;
				1800	print_string "ready> "; flush stdout;
				1801	main_loop the_fpm the_execution_engine stream
				1802	</pre>
				1803	</dd>
				1804
				1805	<dt>toy.ml:</dt>
				1806	<dd class="doc_code">
				1807	<pre>
				1808	(*===----------------------------------------------------------------------===
				1809	* Main driver code.
				1810	===----------------------------------------------------------------------===)
				1811
				1812	open Llvm
				1813	open Llvm_executionengine
				1814	open Llvm_target
				1815	open Llvm_scalar_opts
				1816
				1817	let main () =
				1818	(* Install standard binary operators.
				1819	* 1 is the lowest precedence. *)
				1820	Hashtbl.add Parser.binop_precedence '=' 2;
				1821	Hashtbl.add Parser.binop_precedence '<' 10;
				1822	Hashtbl.add Parser.binop_precedence '+' 20;
				1823	Hashtbl.add Parser.binop_precedence '-' 20;
				1824	Hashtbl.add Parser.binop_precedence '' 40; ( highest. *)
				1825
				1826	(* Prime the first token. *)
				1827	print_string "ready> "; flush stdout;
				1828	let stream = Lexer.lex (Stream.of_channel stdin) in
				1829
				1830	(* Create the JIT. *)
				1831	let the_module_provider = ModuleProvider.create Codegen.the_module in
				1832	let the_execution_engine = ExecutionEngine.create the_module_provider in
				1833	let the_fpm = PassManager.create_function the_module_provider in
				1834
				1835	(* Set up the optimizer pipeline. Start with registering info about how the
				1836	* target lays out data structures. *)
				1837	TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
				1838
				1839	(* Promote allocas to registers. *)
				1840	add_memory_to_register_promotion the_fpm;
				1841
				1842	(* Do simple "peephole" optimizations and bit-twiddling optzn. *)
				1843	add_instruction_combining the_fpm;
				1844
				1845	(* reassociate expressions. *)
				1846	add_reassociation the_fpm;
				1847
				1848	(* Eliminate Common SubExpressions. *)
				1849	add_gvn the_fpm;
				1850
				1851	(* Simplify the control flow graph (deleting unreachable blocks, etc). *)
				1852	add_cfg_simplification the_fpm;
				1853
				1854	(* Run the main "interpreter loop" now. *)
				1855	Toplevel.main_loop the_fpm the_execution_engine stream;
				1856
				1857	(* Print out all the generated code. *)
				1858	dump_module Codegen.the_module
				1859	;;
				1860
				1861	main ()
				1862	</pre>
				1863	</dd>
				1864
				1865	<dt>bindings.c</dt>
				1866	<dd class="doc_code">
				1867	<pre>
				1868	#include <stdio.h>
				1869
				1870	/* putchard - putchar that takes a double and returns 0. */
				1871	extern double putchard(double X) {
				1872	putchar((char)X);
				1873	return 0;
				1874	}
				1875
				1876	/* printd - printf that takes a double prints it as "%f\n", returning 0. */
				1877	extern double printd(double X) {
				1878	printf("%f\n", X);
				1879	return 0;
				1880	}
				1881	</pre>
				1882	</dd>
				1883	</dl>
				1884
				1885	<a href="LangImpl8.html">Next: Conclusion and other useful LLVM tidbits</a>
				1886	</div>
				1887
				1888	<!-- *********************************************************************** -->
				1889	<hr>
				1890	<address>
				1891	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				1892	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				1893	<a href="http://validator.w3.org/check/referer"><img
				1894	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
				1895
				1896	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1897	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				1898	<a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br>
				1899	Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
				1900	</address>
				1901	</body>
				1902	</html>