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

blob: dab3059c89a478a84b72f0181ee5bfd497749c1f [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
Erick Tryzelaar	1f3d276	2009-08-19 17:32:38 +0000	[diff] [blame]	1387	let context = global_context ()
				1388	let the_module = create_module context "my cool jit"
				1389	let builder = builder context
Erick Tryzelaar	35295ff	2008-03-31 08:44:50 +0000	[diff] [blame]	1390	let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
				1391
				1392	(* Create an alloca instruction in the entry block of the function. This
				1393	* is used for mutable variables etc. *)
				1394	let create_entry_block_alloca the_function var_name =
Erick Tryzelaar	1f3d276	2009-08-19 17:32:38 +0000	[diff] [blame]	1395	let builder = builder_at context (instr_begin (entry_block the_function)) in
Erick Tryzelaar	35295ff	2008-03-31 08:44:50 +0000	[diff] [blame]	1396	build_alloca double_type var_name builder
				1397
				1398	let rec codegen_expr = function
				1399	\| Ast.Number n -> const_float double_type n
				1400	\| Ast.Variable name ->
				1401	let v = try Hashtbl.find named_values name with
				1402	\| Not_found -> raise (Error "unknown variable name")
				1403	in
				1404	(* Load the value. *)
				1405	build_load v name builder
				1406	\| Ast.Unary (op, operand) ->
				1407	let operand = codegen_expr operand in
				1408	let callee = "unary" ^ (String.make 1 op) in
				1409	let callee =
				1410	match lookup_function callee the_module with
				1411	\| Some callee -> callee
				1412	\| None -> raise (Error "unknown unary operator")
				1413	in
				1414	build_call callee [\|operand\|] "unop" builder
				1415	\| Ast.Binary (op, lhs, rhs) ->
				1416	begin match op with
				1417	\| '=' ->
				1418	(* Special case '=' because we don't want to emit the LHS as an
				1419	* expression. *)
				1420	let name =
				1421	match lhs with
				1422	\| Ast.Variable name -> name
				1423	\| _ -> raise (Error "destination of '=' must be a variable")
				1424	in
				1425
				1426	(* Codegen the rhs. *)
				1427	let val_ = codegen_expr rhs in
				1428
				1429	(* Lookup the name. *)
				1430	let variable = try Hashtbl.find named_values name with
				1431	\| Not_found -> raise (Error "unknown variable name")
				1432	in
				1433	ignore(build_store val_ variable builder);
				1434	val_
				1435	\| _ ->
				1436	let lhs_val = codegen_expr lhs in
				1437	let rhs_val = codegen_expr rhs in
				1438	begin
				1439	match op with
				1440	\| '+' -> build_add lhs_val rhs_val "addtmp" builder
				1441	\| '-' -> build_sub lhs_val rhs_val "subtmp" builder
				1442	\| '*' -> build_mul lhs_val rhs_val "multmp" builder
				1443	\| '<' ->
				1444	(* Convert bool 0/1 to double 0.0 or 1.0 *)
				1445	let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
				1446	build_uitofp i double_type "booltmp" builder
				1447	\| _ ->
				1448	(* If it wasn't a builtin binary operator, it must be a user defined
				1449	* one. Emit a call to it. *)
				1450	let callee = "binary" ^ (String.make 1 op) in
				1451	let callee =
				1452	match lookup_function callee the_module with
				1453	\| Some callee -> callee
				1454	\| None -> raise (Error "binary operator not found!")
				1455	in
				1456	build_call callee [\|lhs_val; rhs_val\|] "binop" builder
				1457	end
				1458	end
				1459	\| Ast.Call (callee, args) ->
				1460	(* Look up the name in the module table. *)
				1461	let callee =
				1462	match lookup_function callee the_module with
				1463	\| Some callee -> callee
				1464	\| None -> raise (Error "unknown function referenced")
				1465	in
				1466	let params = params callee in
				1467
				1468	(* If argument mismatch error. *)
				1469	if Array.length params == Array.length args then () else
				1470	raise (Error "incorrect # arguments passed");
				1471	let args = Array.map codegen_expr args in
				1472	build_call callee args "calltmp" builder
				1473	\| Ast.If (cond, then_, else_) ->
				1474	let cond = codegen_expr cond in
				1475
				1476	(* Convert condition to a bool by comparing equal to 0.0 *)
				1477	let zero = const_float double_type 0.0 in
				1478	let cond_val = build_fcmp Fcmp.One cond zero "ifcond" builder in
				1479
				1480	(* Grab the first block so that we might later add the conditional branch
				1481	* to it at the end of the function. *)
				1482	let start_bb = insertion_block builder in
				1483	let the_function = block_parent start_bb in
				1484
				1485	let then_bb = append_block "then" the_function in
				1486
				1487	(* Emit 'then' value. *)
				1488	position_at_end then_bb builder;
				1489	let then_val = codegen_expr then_ in
				1490
				1491	(* Codegen of 'then' can change the current block, update then_bb for the
				1492	* phi. We create a new name because one is used for the phi node, and the
				1493	* other is used for the conditional branch. *)
				1494	let new_then_bb = insertion_block builder in
				1495
				1496	(* Emit 'else' value. *)
				1497	let else_bb = append_block "else" the_function in
				1498	position_at_end else_bb builder;
				1499	let else_val = codegen_expr else_ in
				1500
				1501	(* Codegen of 'else' can change the current block, update else_bb for the
				1502	* phi. *)
				1503	let new_else_bb = insertion_block builder in
				1504
				1505	(* Emit merge block. *)
				1506	let merge_bb = append_block "ifcont" the_function in
				1507	position_at_end merge_bb builder;
				1508	let incoming = [(then_val, new_then_bb); (else_val, new_else_bb)] in
				1509	let phi = build_phi incoming "iftmp" builder in
				1510
				1511	(* Return to the start block to add the conditional branch. *)
				1512	position_at_end start_bb builder;
				1513	ignore (build_cond_br cond_val then_bb else_bb builder);
				1514
				1515	(* Set a unconditional branch at the end of the 'then' block and the
				1516	* 'else' block to the 'merge' block. *)
				1517	position_at_end new_then_bb builder; ignore (build_br merge_bb builder);
				1518	position_at_end new_else_bb builder; ignore (build_br merge_bb builder);
				1519
				1520	(* Finally, set the builder to the end of the merge block. *)
				1521	position_at_end merge_bb builder;
				1522
				1523	phi
				1524	\| Ast.For (var_name, start, end_, step, body) ->
				1525	(* Output this as:
				1526	* var = alloca double
				1527	* ...
				1528	* start = startexpr
				1529	* store start -> var
				1530	* goto loop
				1531	* loop:
				1532	* ...
				1533	* bodyexpr
				1534	* ...
				1535	* loopend:
				1536	* step = stepexpr
				1537	* endcond = endexpr
				1538	*
				1539	* curvar = load var
				1540	* nextvar = curvar + step
				1541	* store nextvar -> var
				1542	* br endcond, loop, endloop
				1543	* outloop: *)
				1544
				1545	let the_function = block_parent (insertion_block builder) in
				1546
				1547	(* Create an alloca for the variable in the entry block. *)
				1548	let alloca = create_entry_block_alloca the_function var_name in
				1549
				1550	(* Emit the start code first, without 'variable' in scope. *)
				1551	let start_val = codegen_expr start in
				1552
				1553	(* Store the value into the alloca. *)
				1554	ignore(build_store start_val alloca builder);
				1555
				1556	(* Make the new basic block for the loop header, inserting after current
				1557	* block. *)
				1558	let loop_bb = append_block "loop" the_function in
				1559
				1560	(* Insert an explicit fall through from the current block to the
				1561	* loop_bb. *)
				1562	ignore (build_br loop_bb builder);
				1563
				1564	(* Start insertion in loop_bb. *)
				1565	position_at_end loop_bb builder;
				1566
				1567	(* Within the loop, the variable is defined equal to the PHI node. If it
				1568	* shadows an existing variable, we have to restore it, so save it
				1569	* now. *)
				1570	let old_val =
				1571	try Some (Hashtbl.find named_values var_name) with Not_found -> None
				1572	in
				1573	Hashtbl.add named_values var_name alloca;
				1574
				1575	(* Emit the body of the loop. This, like any other expr, can change the
				1576	* current BB. Note that we ignore the value computed by the body, but
				1577	* don't allow an error *)
				1578	ignore (codegen_expr body);
				1579
				1580	(* Emit the step value. *)
				1581	let step_val =
				1582	match step with
				1583	\| Some step -> codegen_expr step
				1584	(* If not specified, use 1.0. *)
				1585	\| None -> const_float double_type 1.0
				1586	in
				1587
				1588	(* Compute the end condition. *)
				1589	let end_cond = codegen_expr end_ in
				1590
				1591	(* Reload, increment, and restore the alloca. This handles the case where
				1592	* the body of the loop mutates the variable. *)
				1593	let cur_var = build_load alloca var_name builder in
				1594	let next_var = build_add cur_var step_val "nextvar" builder in
				1595	ignore(build_store next_var alloca builder);
				1596
				1597	(* Convert condition to a bool by comparing equal to 0.0. *)
				1598	let zero = const_float double_type 0.0 in
				1599	let end_cond = build_fcmp Fcmp.One end_cond zero "loopcond" builder in
				1600
				1601	(* Create the "after loop" block and insert it. *)
				1602	let after_bb = append_block "afterloop" the_function in
				1603
				1604	(* Insert the conditional branch into the end of loop_end_bb. *)
				1605	ignore (build_cond_br end_cond loop_bb after_bb builder);
				1606
				1607	(* Any new code will be inserted in after_bb. *)
				1608	position_at_end after_bb builder;
				1609
				1610	(* Restore the unshadowed variable. *)
				1611	begin match old_val with
				1612	\| Some old_val -> Hashtbl.add named_values var_name old_val
				1613	\| None -> ()
				1614	end;
				1615
				1616	(* for expr always returns 0.0. *)
				1617	const_null double_type
				1618	\| Ast.Var (var_names, body) ->
				1619	let old_bindings = ref [] in
				1620
				1621	let the_function = block_parent (insertion_block builder) in
				1622
				1623	(* Register all variables and emit their initializer. *)
				1624	Array.iter (fun (var_name, init) ->
				1625	(* Emit the initializer before adding the variable to scope, this
				1626	* prevents the initializer from referencing the variable itself, and
				1627	* permits stuff like this:
				1628	* var a = 1 in
				1629	* var a = a in ... # refers to outer 'a'. *)
				1630	let init_val =
				1631	match init with
				1632	\| Some init -> codegen_expr init
				1633	(* If not specified, use 0.0. *)
				1634	\| None -> const_float double_type 0.0
				1635	in
				1636
				1637	let alloca = create_entry_block_alloca the_function var_name in
				1638	ignore(build_store init_val alloca builder);
				1639
				1640	(* Remember the old variable binding so that we can restore the binding
				1641	* when we unrecurse. *)
				1642	begin
				1643	try
				1644	let old_value = Hashtbl.find named_values var_name in
				1645	old_bindings := (var_name, old_value) :: !old_bindings;
				1646	with Not_found -> ()
				1647	end;
				1648
				1649	(* Remember this binding. *)
				1650	Hashtbl.add named_values var_name alloca;
				1651	) var_names;
				1652
				1653	(* Codegen the body, now that all vars are in scope. *)
				1654	let body_val = codegen_expr body in
				1655
				1656	(* Pop all our variables from scope. *)
				1657	List.iter (fun (var_name, old_value) ->
				1658	Hashtbl.add named_values var_name old_value
				1659	) !old_bindings;
				1660
				1661	(* Return the body computation. *)
				1662	body_val
				1663
				1664	let codegen_proto = function
				1665	\| Ast.Prototype (name, args) \| Ast.BinOpPrototype (name, args, _) ->
				1666	(* Make the function type: double(double,double) etc. *)
				1667	let doubles = Array.make (Array.length args) double_type in
				1668	let ft = function_type double_type doubles in
				1669	let f =
				1670	match lookup_function name the_module with
				1671	\| None -> declare_function name ft the_module
				1672
				1673	(* If 'f' conflicted, there was already something named 'name'. If it
				1674	* has a body, don't allow redefinition or reextern. *)
				1675	\| Some f ->
				1676	(* If 'f' already has a body, reject this. *)
				1677	if block_begin f <> At_end f then
				1678	raise (Error "redefinition of function");
				1679
				1680	(* If 'f' took a different number of arguments, reject. *)
				1681	if element_type (type_of f) <> ft then
				1682	raise (Error "redefinition of function with different # args");
				1683	f
				1684	in
				1685
				1686	(* Set names for all arguments. *)
				1687	Array.iteri (fun i a ->
				1688	let n = args.(i) in
				1689	set_value_name n a;
				1690	Hashtbl.add named_values n a;
				1691	) (params f);
				1692	f
				1693
				1694	(* Create an alloca for each argument and register the argument in the symbol
				1695	* table so that references to it will succeed. *)
				1696	let create_argument_allocas the_function proto =
				1697	let args = match proto with
				1698	\| Ast.Prototype (_, args) \| Ast.BinOpPrototype (_, args, _) -> args
				1699	in
				1700	Array.iteri (fun i ai ->
				1701	let var_name = args.(i) in
				1702	(* Create an alloca for this variable. *)
				1703	let alloca = create_entry_block_alloca the_function var_name in
				1704
				1705	(* Store the initial value into the alloca. *)
				1706	ignore(build_store ai alloca builder);
				1707
				1708	(* Add arguments to variable symbol table. *)
				1709	Hashtbl.add named_values var_name alloca;
				1710	) (params the_function)
				1711
				1712	let codegen_func the_fpm = function
				1713	\| Ast.Function (proto, body) ->
				1714	Hashtbl.clear named_values;
				1715	let the_function = codegen_proto proto in
				1716
				1717	(* If this is an operator, install it. *)
				1718	begin match proto with
				1719	\| Ast.BinOpPrototype (name, args, prec) ->
				1720	let op = name.[String.length name - 1] in
				1721	Hashtbl.add Parser.binop_precedence op prec;
				1722	\| _ -> ()
				1723	end;
				1724
				1725	(* Create a new basic block to start insertion into. *)
				1726	let bb = append_block "entry" the_function in
				1727	position_at_end bb builder;
				1728
				1729	try
				1730	(* Add all arguments to the symbol table and create their allocas. *)
				1731	create_argument_allocas the_function proto;
				1732
				1733	let ret_val = codegen_expr body in
				1734
				1735	(* Finish off the function. *)
				1736	let _ = build_ret ret_val builder in
				1737
				1738	(* Validate the generated code, checking for consistency. *)
				1739	Llvm_analysis.assert_valid_function the_function;
				1740
				1741	(* Optimize the function. *)
				1742	let _ = PassManager.run_function the_function the_fpm in
				1743
				1744	the_function
				1745	with e ->
				1746	delete_function the_function;
				1747	raise e
				1748	</pre>
				1749	</dd>
				1750
				1751	<dt>toplevel.ml:</dt>
				1752	<dd class="doc_code">
				1753	<pre>
				1754	(*===----------------------------------------------------------------------===
				1755	* Top-Level parsing and JIT Driver
				1756	===----------------------------------------------------------------------===)
				1757
				1758	open Llvm
				1759	open Llvm_executionengine
				1760
				1761	(* top ::= definition \| external \| expression \| ';' *)
				1762	let rec main_loop the_fpm the_execution_engine stream =
				1763	match Stream.peek stream with
				1764	\| None -> ()
				1765
				1766	(* ignore top-level semicolons. *)
				1767	\| Some (Token.Kwd ';') ->
				1768	Stream.junk stream;
				1769	main_loop the_fpm the_execution_engine stream
				1770
				1771	\| Some token ->
				1772	begin
				1773	try match token with
				1774	\| Token.Def ->
				1775	let e = Parser.parse_definition stream in
				1776	print_endline "parsed a function definition.";
				1777	dump_value (Codegen.codegen_func the_fpm e);
				1778	\| Token.Extern ->
				1779	let e = Parser.parse_extern stream in
				1780	print_endline "parsed an extern.";
				1781	dump_value (Codegen.codegen_proto e);
				1782	\| _ ->
				1783	(* Evaluate a top-level expression into an anonymous function. *)
				1784	let e = Parser.parse_toplevel stream in
				1785	print_endline "parsed a top-level expr";
				1786	let the_function = Codegen.codegen_func the_fpm e in
				1787	dump_value the_function;
				1788
				1789	(* JIT the function, returning a function pointer. *)
				1790	let result = ExecutionEngine.run_function the_function [\|\|]
				1791	the_execution_engine in
				1792
				1793	print_string "Evaluated to ";
				1794	print_float (GenericValue.as_float double_type result);
				1795	print_newline ();
				1796	with Stream.Error s \| Codegen.Error s ->
				1797	(* Skip token for error recovery. *)
				1798	Stream.junk stream;
				1799	print_endline s;
				1800	end;
				1801	print_string "ready> "; flush stdout;
				1802	main_loop the_fpm the_execution_engine stream
				1803	</pre>
				1804	</dd>
				1805
				1806	<dt>toy.ml:</dt>
				1807	<dd class="doc_code">
				1808	<pre>
				1809	(*===----------------------------------------------------------------------===
				1810	* Main driver code.
				1811	===----------------------------------------------------------------------===)
				1812
				1813	open Llvm
				1814	open Llvm_executionengine
				1815	open Llvm_target
				1816	open Llvm_scalar_opts
				1817
				1818	let main () =
				1819	(* Install standard binary operators.
				1820	* 1 is the lowest precedence. *)
				1821	Hashtbl.add Parser.binop_precedence '=' 2;
				1822	Hashtbl.add Parser.binop_precedence '<' 10;
				1823	Hashtbl.add Parser.binop_precedence '+' 20;
				1824	Hashtbl.add Parser.binop_precedence '-' 20;
				1825	Hashtbl.add Parser.binop_precedence '' 40; ( highest. *)
				1826
				1827	(* Prime the first token. *)
				1828	print_string "ready> "; flush stdout;
				1829	let stream = Lexer.lex (Stream.of_channel stdin) in
				1830
				1831	(* Create the JIT. *)
				1832	let the_module_provider = ModuleProvider.create Codegen.the_module in
				1833	let the_execution_engine = ExecutionEngine.create the_module_provider in
				1834	let the_fpm = PassManager.create_function the_module_provider in
				1835
				1836	(* Set up the optimizer pipeline. Start with registering info about how the
				1837	* target lays out data structures. *)
				1838	TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
				1839
				1840	(* Promote allocas to registers. *)
				1841	add_memory_to_register_promotion the_fpm;
				1842
				1843	(* Do simple "peephole" optimizations and bit-twiddling optzn. *)
				1844	add_instruction_combining the_fpm;
				1845
				1846	(* reassociate expressions. *)
				1847	add_reassociation the_fpm;
				1848
				1849	(* Eliminate Common SubExpressions. *)
				1850	add_gvn the_fpm;
				1851
				1852	(* Simplify the control flow graph (deleting unreachable blocks, etc). *)
				1853	add_cfg_simplification the_fpm;
				1854
				1855	(* Run the main "interpreter loop" now. *)
				1856	Toplevel.main_loop the_fpm the_execution_engine stream;
				1857
				1858	(* Print out all the generated code. *)
				1859	dump_module Codegen.the_module
				1860	;;
				1861
				1862	main ()
				1863	</pre>
				1864	</dd>
				1865
				1866	<dt>bindings.c</dt>
				1867	<dd class="doc_code">
				1868	<pre>
				1869	#include <stdio.h>
				1870
				1871	/* putchard - putchar that takes a double and returns 0. */
				1872	extern double putchard(double X) {
				1873	putchar((char)X);
				1874	return 0;
				1875	}
				1876
				1877	/* printd - printf that takes a double prints it as "%f\n", returning 0. */
				1878	extern double printd(double X) {
				1879	printf("%f\n", X);
				1880	return 0;
				1881	}
				1882	</pre>
				1883	</dd>
				1884	</dl>
				1885
				1886	<a href="LangImpl8.html">Next: Conclusion and other useful LLVM tidbits</a>
				1887	</div>
				1888
				1889	<!-- *********************************************************************** -->
				1890	<hr>
				1891	<address>
				1892	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				1893	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				1894	<a href="http://validator.w3.org/check/referer"><img
				1895	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
				1896
				1897	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1898	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				1899	<a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br>
				1900	Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
				1901	</address>
				1902	</body>
				1903	</html>