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

blob: fc1caeb1f2093b9c1e8bf0794f5b2dae6a6b8ec1 [file] [log] [blame]

Erick Tryzelaar	37c076b	2008-03-30 09:57:12 +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: Adding JIT and Optimizer Support</title>
				7	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
				8	<meta name="author" content="Chris Lattner">
				9	<meta name="author" content="Erick Tryzelaar">
				10	<link rel="stylesheet" href="../llvm.css" type="text/css">
				11	</head>
				12
				13	<body>
				14
				15	<div class="doc_title">Kaleidoscope: Adding JIT and Optimizer Support</div>
				16
				17	<ul>
				18	<li><a href="index.html">Up to Tutorial Index</a></li>
				19	<li>Chapter 4
				20	<ol>
				21	<li><a href="#intro">Chapter 4 Introduction</a></li>
				22	<li><a href="#trivialconstfold">Trivial Constant Folding</a></li>
				23	<li><a href="#optimizerpasses">LLVM Optimization Passes</a></li>
				24	<li><a href="#jit">Adding a JIT Compiler</a></li>
				25	<li><a href="#code">Full Code Listing</a></li>
				26	</ol>
				27	</li>
				28	<li><a href="OCamlLangImpl5.html">Chapter 5</a>: Extending the Language: Control
				29	Flow</li>
				30	</ul>
				31
				32	<div class="doc_author">
				33	<p>
				34	Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>
				35	and <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a>
				36	</p>
				37	</div>
				38
				39	<!-- *********************************************************************** -->
				40	<div class="doc_section"><a name="intro">Chapter 4 Introduction</a></div>
				41	<!-- *********************************************************************** -->
				42
				43	<div class="doc_text">
				44
				45	<p>Welcome to Chapter 4 of the "<a href="index.html">Implementing a language
				46	with LLVM</a>" tutorial. Chapters 1-3 described the implementation of a simple
				47	language and added support for generating LLVM IR. This chapter describes
				48	two new techniques: adding optimizer support to your language, and adding JIT
				49	compiler support. These additions will demonstrate how to get nice, efficient code
				50	for the Kaleidoscope language.</p>
				51
				52	</div>
				53
				54	<!-- *********************************************************************** -->
				55	<div class="doc_section"><a name="trivialconstfold">Trivial Constant
				56	Folding</a></div>
				57	<!-- *********************************************************************** -->
				58
				59	<div class="doc_text">
				60
				61	<p><b>Note:</b> the ocaml bindings already use <tt>LLVMFoldingBuilder</tt>.<p>
				62
				63	<p>
				64	Our demonstration for Chapter 3 is elegant and easy to extend. Unfortunately,
				65	it does not produce wonderful code. For example, when compiling simple code,
				66	we don't get obvious optimizations:</p>
				67
				68	<div class="doc_code">
				69	<pre>
				70	ready> <b>def test(x) 1+2+x;</b>
				71	Read function definition:
				72	define double @test(double %x) {
				73	entry:
				74	%addtmp = add double 1.000000e+00, 2.000000e+00
				75	%addtmp1 = add double %addtmp, %x
				76	ret double %addtmp1
				77	}
				78	</pre>
				79	</div>
				80
				81	<p>This code is a very, very literal transcription of the AST built by parsing
				82	the input. As such, this transcription lacks optimizations like constant folding
				83	(we'd like to get "<tt>add x, 3.0</tt>" in the example above) as well as other
				84	more important optimizations. Constant folding, in particular, is a very common
				85	and very important optimization: so much so that many language implementors
				86	implement constant folding support in their AST representation.</p>
				87
				88	<p>With LLVM, you don't need this support in the AST. Since all calls to build
				89	LLVM IR go through the LLVM builder, it would be nice if the builder itself
				90	checked to see if there was a constant folding opportunity when you call it.
				91	If so, it could just do the constant fold and return the constant instead of
				92	creating an instruction. This is exactly what the <tt>LLVMFoldingBuilder</tt>
				93	class does.
				94
				95	<p>All we did was switch from <tt>LLVMBuilder</tt> to
				96	<tt>LLVMFoldingBuilder</tt>. Though we change no other code, we now have all of our
				97	instructions implicitly constant folded without us having to do anything
				98	about it. For example, the input above now compiles to:</p>
				99
				100	<div class="doc_code">
				101	<pre>
				102	ready> <b>def test(x) 1+2+x;</b>
				103	Read function definition:
				104	define double @test(double %x) {
				105	entry:
				106	%addtmp = add double 3.000000e+00, %x
				107	ret double %addtmp
				108	}
				109	</pre>
				110	</div>
				111
				112	<p>Well, that was easy :). In practice, we recommend always using
				113	<tt>LLVMFoldingBuilder</tt> when generating code like this. It has no
				114	"syntactic overhead" for its use (you don't have to uglify your compiler with
				115	constant checks everywhere) and it can dramatically reduce the amount of
				116	LLVM IR that is generated in some cases (particular for languages with a macro
				117	preprocessor or that use a lot of constants).</p>
				118
				119	<p>On the other hand, the <tt>LLVMFoldingBuilder</tt> is limited by the fact
				120	that it does all of its analysis inline with the code as it is built. If you
				121	take a slightly more complex example:</p>
				122
				123	<div class="doc_code">
				124	<pre>
				125	ready> <b>def test(x) (1+2+x)*(x+(1+2));</b>
				126	ready> Read function definition:
				127	define double @test(double %x) {
				128	entry:
				129	%addtmp = add double 3.000000e+00, %x
				130	%addtmp1 = add double %x, 3.000000e+00
				131	%multmp = mul double %addtmp, %addtmp1
				132	ret double %multmp
				133	}
				134	</pre>
				135	</div>
				136
				137	<p>In this case, the LHS and RHS of the multiplication are the same value. We'd
				138	really like to see this generate "<tt>tmp = x+3; result = tmp*tmp;</tt>" instead
				139	of computing "<tt>x*3</tt>" twice.</p>
				140
				141	<p>Unfortunately, no amount of local analysis will be able to detect and correct
				142	this. This requires two transformations: reassociation of expressions (to
				143	make the add's lexically identical) and Common Subexpression Elimination (CSE)
				144	to delete the redundant add instruction. Fortunately, LLVM provides a broad
				145	range of optimizations that you can use, in the form of "passes".</p>
				146
				147	</div>
				148
				149	<!-- *********************************************************************** -->
				150	<div class="doc_section"><a name="optimizerpasses">LLVM Optimization
				151	Passes</a></div>
				152	<!-- *********************************************************************** -->
				153
				154	<div class="doc_text">
				155
				156	<p>LLVM provides many optimization passes, which do many different sorts of
				157	things and have different tradeoffs. Unlike other systems, LLVM doesn't hold
				158	to the mistaken notion that one set of optimizations is right for all languages
				159	and for all situations. LLVM allows a compiler implementor to make complete
				160	decisions about what optimizations to use, in which order, and in what
				161	situation.</p>
				162
				163	<p>As a concrete example, LLVM supports both "whole module" passes, which look
				164	across as large of body of code as they can (often a whole file, but if run
				165	at link time, this can be a substantial portion of the whole program). It also
				166	supports and includes "per-function" passes which just operate on a single
				167	function at a time, without looking at other functions. For more information
				168	on passes and how they are run, see the <a href="../WritingAnLLVMPass.html">How
				169	to Write a Pass</a> document and the <a href="../Passes.html">List of LLVM
				170	Passes</a>.</p>
				171
				172	<p>For Kaleidoscope, we are currently generating functions on the fly, one at
				173	a time, as the user types them in. We aren't shooting for the ultimate
				174	optimization experience in this setting, but we also want to catch the easy and
				175	quick stuff where possible. As such, we will choose to run a few per-function
				176	optimizations as the user types the function in. If we wanted to make a "static
				177	Kaleidoscope compiler", we would use exactly the code we have now, except that
				178	we would defer running the optimizer until the entire file has been parsed.</p>
				179
				180	<p>In order to get per-function optimizations going, we need to set up a
				181	<a href="../WritingAnLLVMPass.html#passmanager">Llvm.PassManager</a> to hold and
				182	organize the LLVM optimizations that we want to run. Once we have that, we can
				183	add a set of optimizations to run. The code looks like this:</p>
				184
				185	<div class="doc_code">
				186	<pre>
				187	(* Create the JIT. *)
				188	let the_module_provider = ModuleProvider.create Codegen.the_module in
				189	let the_execution_engine = ExecutionEngine.create the_module_provider in
				190	let the_fpm = PassManager.create_function the_module_provider in
				191
				192	(* Set up the optimizer pipeline. Start with registering info about how the
				193	* target lays out data structures. *)
				194	TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
				195
				196	(* Do simple "peephole" optimizations and bit-twiddling optzn. *)
				197	add_instruction_combining the_fpm;
				198
				199	(* reassociate expressions. *)
				200	add_reassociation the_fpm;
				201
				202	(* Eliminate Common SubExpressions. *)
				203	add_gvn the_fpm;
				204
				205	(* Simplify the control flow graph (deleting unreachable blocks, etc). *)
				206	add_cfg_simplification the_fpm;
				207
				208	(* Run the main "interpreter loop" now. *)
				209	Toplevel.main_loop the_fpm the_execution_engine stream;
				210	</pre>
				211	</div>
				212
				213	<p>This code defines two values, an <tt>Llvm.llmoduleprovider</tt> and a
				214	<tt>Llvm.PassManager.t</tt>. The former is basically a wrapper around our
				215	<tt>Llvm.llmodule</tt> that the <tt>Llvm.PassManager.t</tt> requires. It
				216	provides certain flexibility that we're not going to take advantage of here,
				217	so I won't dive into any details about it.</p>
				218
				219	<p>The meat of the matter here, is the definition of "<tt>the_fpm</tt>". It
				220	requires a pointer to the <tt>the_module</tt> (through the
				221	<tt>the_module_provider</tt>) to construct itself. Once it is set up, we use a
				222	series of "add" calls to add a bunch of LLVM passes. The first pass is
				223	basically boilerplate, it adds a pass so that later optimizations know how the
				224	data structures in the program are layed out. The
				225	"<tt>the_execution_engine</tt>" variable is related to the JIT, which we will
				226	get to in the next section.</p>
				227
				228	<p>In this case, we choose to add 4 optimization passes. The passes we chose
				229	here are a pretty standard set of "cleanup" optimizations that are useful for
				230	a wide variety of code. I won't delve into what they do but, believe me,
				231	they are a good starting place :).</p>
				232
				233	<p>Once the <tt>Llvm.PassManager.</tt> is set up, we need to make use of it.
				234	We do this by running it after our newly created function is constructed (in
				235	<tt>Codegen.codegen_func</tt>), but before it is returned to the client:</p>
				236
				237	<div class="doc_code">
				238	<pre>
				239	let codegen_func the_fpm = function
				240	...
				241	try
				242	let ret_val = codegen_expr body in
				243
				244	(* Finish off the function. *)
				245	let _ = build_ret ret_val builder in
				246
				247	(* Validate the generated code, checking for consistency. *)
				248	Llvm_analysis.assert_valid_function the_function;
				249
				250	(* Optimize the function. *)
				251	let _ = PassManager.run_function the_function the_fpm in
				252
				253	the_function
				254	</pre>
				255	</div>
				256
				257	<p>As you can see, this is pretty straightforward. The <tt>the_fpm</tt>
				258	optimizes and updates the LLVM Function* in place, improving (hopefully) its
				259	body. With this in place, we can try our test above again:</p>
				260
				261	<div class="doc_code">
				262	<pre>
				263	ready> <b>def test(x) (1+2+x)*(x+(1+2));</b>
				264	ready> Read function definition:
				265	define double @test(double %x) {
				266	entry:
				267	%addtmp = add double %x, 3.000000e+00
				268	%multmp = mul double %addtmp, %addtmp
				269	ret double %multmp
				270	}
				271	</pre>
				272	</div>
				273
				274	<p>As expected, we now get our nicely optimized code, saving a floating point
				275	add instruction from every execution of this function.</p>
				276
				277	<p>LLVM provides a wide variety of optimizations that can be used in certain
				278	circumstances. Some <a href="../Passes.html">documentation about the various
				279	passes</a> is available, but it isn't very complete. Another good source of
				280	ideas can come from looking at the passes that <tt>llvm-gcc</tt> or
				281	<tt>llvm-ld</tt> run to get started. The "<tt>opt</tt>" tool allows you to
				282	experiment with passes from the command line, so you can see if they do
				283	anything.</p>
				284
				285	<p>Now that we have reasonable code coming out of our front-end, lets talk about
				286	executing it!</p>
				287
				288	</div>
				289
				290	<!-- *********************************************************************** -->
				291	<div class="doc_section"><a name="jit">Adding a JIT Compiler</a></div>
				292	<!-- *********************************************************************** -->
				293
				294	<div class="doc_text">
				295
				296	<p>Code that is available in LLVM IR can have a wide variety of tools
				297	applied to it. For example, you can run optimizations on it (as we did above),
				298	you can dump it out in textual or binary forms, you can compile the code to an
				299	assembly file (.s) for some target, or you can JIT compile it. The nice thing
				300	about the LLVM IR representation is that it is the "common currency" between
				301	many different parts of the compiler.
				302	</p>
				303
				304	<p>In this section, we'll add JIT compiler support to our interpreter. The
				305	basic idea that we want for Kaleidoscope is to have the user enter function
				306	bodies as they do now, but immediately evaluate the top-level expressions they
				307	type in. For example, if they type in "1 + 2;", we should evaluate and print
				308	out 3. If they define a function, they should be able to call it from the
				309	command line.</p>
				310
				311	<p>In order to do this, we first declare and initialize the JIT. This is done
				312	by adding a global variable and a call in <tt>main</tt>:</p>
				313
				314	<div class="doc_code">
				315	<pre>
				316	...
				317	let main () =
				318	...
				319	<b>
				320	(* Create the JIT. *)
				321	let the_module_provider = ModuleProvider.create Codegen.the_module in
				322	let the_execution_engine = ExecutionEngine.create the_module_provider in</b>
				323	...
				324	</pre>
				325	</div>
				326
				327	<p>This creates an abstract "Execution Engine" which can be either a JIT
				328	compiler or the LLVM interpreter. LLVM will automatically pick a JIT compiler
				329	for you if one is available for your platform, otherwise it will fall back to
				330	the interpreter.</p>
				331
				332	<p>Once the <tt>Llvm_executionengine.ExecutionEngine.t</tt> is created, the JIT
				333	is ready to be used. There are a variety of APIs that are useful, but the
				334	simplest one is the "<tt>Llvm_executionengine.ExecutionEngine.run_function</tt>"
				335	function. This method JIT compiles the specified LLVM Function and returns a
				336	function pointer to the generated machine code. In our case, this means that we
				337	can change the code that parses a top-level expression to look like this:</p>
				338
				339	<div class="doc_code">
				340	<pre>
				341	(* Evaluate a top-level expression into an anonymous function. *)
				342	let e = Parser.parse_toplevel stream in
				343	print_endline "parsed a top-level expr";
				344	let the_function = Codegen.codegen_func the_fpm e in
				345	dump_value the_function;
				346
				347	(* JIT the function, returning a function pointer. *)
				348	let result = ExecutionEngine.run_function the_function [\|\|]
				349	the_execution_engine in
				350
				351	print_string "Evaluated to ";
				352	print_float (GenericValue.as_float double_type result);
				353	print_newline ();
				354	</pre>
				355	</div>
				356
				357	<p>Recall that we compile top-level expressions into a self-contained LLVM
				358	function that takes no arguments and returns the computed double. Because the
				359	LLVM JIT compiler matches the native platform ABI, this means that you can just
				360	cast the result pointer to a function pointer of that type and call it directly.
				361	This means, there is no difference between JIT compiled code and native machine
				362	code that is statically linked into your application.</p>
				363
				364	<p>With just these two changes, lets see how Kaleidoscope works now!</p>
				365
				366	<div class="doc_code">
				367	<pre>
				368	ready> <b>4+5;</b>
				369	define double @""() {
				370	entry:
				371	ret double 9.000000e+00
				372	}
				373
				374	<em>Evaluated to 9.000000</em>
				375	</pre>
				376	</div>
				377
				378	<p>Well this looks like it is basically working. The dump of the function
				379	shows the "no argument function that always returns double" that we synthesize
				380	for each top level expression that is typed in. This demonstrates very basic
				381	functionality, but can we do more?</p>
				382
				383	<div class="doc_code">
				384	<pre>
				385	ready> <b>def testfunc(x y) x + y*2; </b>
				386	Read function definition:
				387	define double @testfunc(double %x, double %y) {
				388	entry:
				389	%multmp = mul double %y, 2.000000e+00
				390	%addtmp = add double %multmp, %x
				391	ret double %addtmp
				392	}
				393
				394	ready> <b>testfunc(4, 10);</b>
				395	define double @""() {
				396	entry:
				397	%calltmp = call double @testfunc( double 4.000000e+00, double 1.000000e+01 )
				398	ret double %calltmp
				399	}
				400
				401	<em>Evaluated to 24.000000</em>
				402	</pre>
				403	</div>
				404
				405	<p>This illustrates that we can now call user code, but there is something a bit
				406	subtle going on here. Note that we only invoke the JIT on the anonymous
				407	functions that <em>call testfunc</em>, but we never invoked it on <em>testfunc
				408	</em>itself.</p>
				409
				410	<p>What actually happened here is that the anonymous function was JIT'd when
				411	requested. When the Kaleidoscope app calls through the function pointer that is
				412	returned, the anonymous function starts executing. It ends up making the call
				413	to the "testfunc" function, and ends up in a stub that invokes the JIT, lazily,
				414	on testfunc. Once the JIT finishes lazily compiling testfunc,
				415	it returns and the code re-executes the call.</p>
				416
				417	<p>In summary, the JIT will lazily JIT code, on the fly, as it is needed. The
				418	JIT provides a number of other more advanced interfaces for things like freeing
				419	allocated machine code, rejit'ing functions to update them, etc. However, even
				420	with this simple code, we get some surprisingly powerful capabilities - check
				421	this out (I removed the dump of the anonymous functions, you should get the idea
				422	by now :) :</p>
				423
				424	<div class="doc_code">
				425	<pre>
				426	ready> <b>extern sin(x);</b>
				427	Read extern:
				428	declare double @sin(double)
				429
				430	ready> <b>extern cos(x);</b>
				431	Read extern:
				432	declare double @cos(double)
				433
				434	ready> <b>sin(1.0);</b>
				435	<em>Evaluated to 0.841471</em>
				436
				437	ready> <b>def foo(x) sin(x)sin(x) + cos(x)cos(x);</b>
				438	Read function definition:
				439	define double @foo(double %x) {
				440	entry:
				441	%calltmp = call double @sin( double %x )
				442	%multmp = mul double %calltmp, %calltmp
				443	%calltmp2 = call double @cos( double %x )
				444	%multmp4 = mul double %calltmp2, %calltmp2
				445	%addtmp = add double %multmp, %multmp4
				446	ret double %addtmp
				447	}
				448
				449	ready> <b>foo(4.0);</b>
				450	<em>Evaluated to 1.000000</em>
				451	</pre>
				452	</div>
				453
				454	<p>Whoa, how does the JIT know about sin and cos? The answer is surprisingly
				455	simple: in this example, the JIT started execution of a function and got to a
				456	function call. It realized that the function was not yet JIT compiled and
				457	invoked the standard set of routines to resolve the function. In this case,
				458	there is no body defined for the function, so the JIT ended up calling
				459	"<tt>dlsym("sin")</tt>" on the Kaleidoscope process itself. Since
				460	"<tt>sin</tt>" is defined within the JIT's address space, it simply patches up
				461	calls in the module to call the libm version of <tt>sin</tt> directly.</p>
				462
				463	<p>The LLVM JIT provides a number of interfaces (look in the
				464	<tt>llvm_executionengine.mli</tt> file) for controlling how unknown functions
				465	get resolved. It allows you to establish explicit mappings between IR objects
				466	and addresses (useful for LLVM global variables that you want to map to static
				467	tables, for example), allows you to dynamically decide on the fly based on the
				468	function name, and even allows you to have the JIT abort itself if any lazy
				469	compilation is attempted.</p>
				470
				471	<p>One interesting application of this is that we can now extend the language
				472	by writing arbitrary C code to implement operations. For example, if we add:
				473	</p>
				474
				475	<div class="doc_code">
				476	<pre>
				477	/* putchard - putchar that takes a double and returns 0. */
				478	extern "C"
				479	double putchard(double X) {
				480	putchar((char)X);
				481	return 0;
				482	}
				483	</pre>
				484	</div>
				485
				486	<p>Now we can produce simple output to the console by using things like:
				487	"<tt>extern putchard(x); putchard(120);</tt>", which prints a lowercase 'x' on
				488	the console (120 is the ASCII code for 'x'). Similar code could be used to
				489	implement file I/O, console input, and many other capabilities in
				490	Kaleidoscope.</p>
				491
				492	<p>This completes the JIT and optimizer chapter of the Kaleidoscope tutorial. At
				493	this point, we can compile a non-Turing-complete programming language, optimize
				494	and JIT compile it in a user-driven way. Next up we'll look into <a
				495	href="OCamlLangImpl5.html">extending the language with control flow
				496	constructs</a>, tackling some interesting LLVM IR issues along the way.</p>
				497
				498	</div>
				499
				500	<!-- *********************************************************************** -->
				501	<div class="doc_section"><a name="code">Full Code Listing</a></div>
				502	<!-- *********************************************************************** -->
				503
				504	<div class="doc_text">
				505
				506	<p>
				507	Here is the complete code listing for our running example, enhanced with the
				508	LLVM JIT and optimizer. To build this example, use:
				509	</p>
				510
				511	<dl>
				512	<dt>_tags:</dt>
				513	<dd class="doc_code">
				514	<pre>
				515	<{lexer,parser}.ml>: use_camlp4, pp(camlp4of)
				516	<*.{byte,native}>: g++, use_llvm, use_llvm_analysis
				517	<*.{byte,native}>: use_llvm_executionengine, use_llvm_target
				518	<*.{byte,native}>: use_llvm_scalar_opts, use_bindings
				519	</pre>
				520	</dd>
				521
				522	<dt>myocamlbuild.ml:</dt>
				523	<dd class="doc_code">
				524	<pre>
				525	open Ocamlbuild_plugin;;
				526
				527	ocaml_lib ~extern:true "llvm";;
				528	ocaml_lib ~extern:true "llvm_analysis";;
				529	ocaml_lib ~extern:true "llvm_executionengine";;
				530	ocaml_lib ~extern:true "llvm_target";;
				531	ocaml_lib ~extern:true "llvm_scalar_opts";;
				532
				533	flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
				534	dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
				535	</pre>
				536	</dd>
				537
				538	<dt>token.ml:</dt>
				539	<dd class="doc_code">
				540	<pre>
				541	(*===----------------------------------------------------------------------===
				542	* Lexer Tokens
				543	===----------------------------------------------------------------------===)
				544
				545	(* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
				546	* these others for known things. *)
				547	type token =
				548	(* commands *)
				549	\| Def \| Extern
				550
				551	(* primary *)
				552	\| Ident of string \| Number of float
				553
				554	(* unknown *)
				555	\| Kwd of char
				556	</pre>
				557	</dd>
				558
				559	<dt>lexer.ml:</dt>
				560	<dd class="doc_code">
				561	<pre>
				562	(*===----------------------------------------------------------------------===
				563	* Lexer
				564	===----------------------------------------------------------------------===)
				565
				566	let rec lex = parser
				567	(* Skip any whitespace. *)
				568	\| [< ' (' ' \| '\n' \| '\r' \| '\t'); stream >] -> lex stream
				569
				570	(* identifier: [a-zA-Z][a-zA-Z0-9] *)
				571	\| [< ' ('A' .. 'Z' \| 'a' .. 'z' as c); stream >] ->
				572	let buffer = Buffer.create 1 in
				573	Buffer.add_char buffer c;
				574	lex_ident buffer stream
				575
				576	(* number: [0-9.]+ *)
				577	\| [< ' ('0' .. '9' as c); stream >] ->
				578	let buffer = Buffer.create 1 in
				579	Buffer.add_char buffer c;
				580	lex_number buffer stream
				581
				582	(* Comment until end of line. *)
				583	\| [< ' ('#'); stream >] ->
				584	lex_comment stream
				585
				586	(* Otherwise, just return the character as its ascii value. *)
				587	\| [< 'c; stream >] ->
				588	[< 'Token.Kwd c; lex stream >]
				589
				590	(* end of stream. *)
				591	\| [< >] -> [< >]
				592
				593	and lex_number buffer = parser
				594	\| [< ' ('0' .. '9' \| '.' as c); stream >] ->
				595	Buffer.add_char buffer c;
				596	lex_number buffer stream
				597	\| [< stream=lex >] ->
				598	[< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >]
				599
				600	and lex_ident buffer = parser
				601	\| [< ' ('A' .. 'Z' \| 'a' .. 'z' \| '0' .. '9' as c); stream >] ->
				602	Buffer.add_char buffer c;
				603	lex_ident buffer stream
				604	\| [< stream=lex >] ->
				605	match Buffer.contents buffer with
				606	\| "def" -> [< 'Token.Def; stream >]
				607	\| "extern" -> [< 'Token.Extern; stream >]
				608	\| id -> [< 'Token.Ident id; stream >]
				609
				610	and lex_comment = parser
				611	\| [< ' ('\n'); stream=lex >] -> stream
				612	\| [< 'c; e=lex_comment >] -> e
				613	\| [< >] -> [< >]
				614	</pre>
				615	</dd>
				616
				617	<dt>ast.ml:</dt>
				618	<dd class="doc_code">
				619	<pre>
				620	(*===----------------------------------------------------------------------===
				621	* Abstract Syntax Tree (aka Parse Tree)
				622	===----------------------------------------------------------------------===)
				623
				624	(* expr - Base type for all expression nodes. *)
				625	type expr =
				626	(* variant for numeric literals like "1.0". *)
				627	\| Number of float
				628
				629	(* variant for referencing a variable, like "a". *)
				630	\| Variable of string
				631
				632	(* variant for a binary operator. *)
				633	\| Binary of char * expr * expr
				634
				635	(* variant for function calls. *)
				636	\| Call of string * expr array
				637
				638	(* proto - This type represents the "prototype" for a function, which captures
				639	* its name, and its argument names (thus implicitly the number of arguments the
				640	* function takes). *)
				641	type proto = Prototype of string * string array
				642
				643	(* func - This type represents a function definition itself. *)
				644	type func = Function of proto * expr
				645	</pre>
				646	</dd>
				647
				648	<dt>parser.ml:</dt>
				649	<dd class="doc_code">
				650	<pre>
				651	(*===---------------------------------------------------------------------===
				652	* Parser
				653	===---------------------------------------------------------------------===)
				654
				655	(* binop_precedence - This holds the precedence for each binary operator that is
				656	* defined *)
				657	let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
				658
				659	(* precedence - Get the precedence of the pending binary operator token. *)
				660	let precedence c = try Hashtbl.find binop_precedence c with Not_found -> -1
				661
				662	(* primary
				663	* ::= identifier
				664	* ::= numberexpr
				665	* ::= parenexpr *)
				666	let rec parse_primary = parser
				667	(* numberexpr ::= number *)
				668	\| [< 'Token.Number n >] -> Ast.Number n
				669
				670	(* parenexpr ::= '(' expression ')' *)
				671	\| [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
				672
				673	(* identifierexpr
				674	* ::= identifier
				675	* ::= identifier '(' argumentexpr ')' *)
				676	\| [< 'Token.Ident id; stream >] ->
				677	let rec parse_args accumulator = parser
				678	\| [< e=parse_expr; stream >] ->
				679	begin parser
				680	\| [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
				681	\| [< >] -> e :: accumulator
				682	end stream
				683	\| [< >] -> accumulator
				684	in
				685	let rec parse_ident id = parser
				686	(* Call. *)
				687	\| [< 'Token.Kwd '(';
				688	args=parse_args [];
				689	'Token.Kwd ')' ?? "expected ')'">] ->
				690	Ast.Call (id, Array.of_list (List.rev args))
				691
				692	(* Simple variable ref. *)
				693	\| [< >] -> Ast.Variable id
				694	in
				695	parse_ident id stream
				696
				697	\| [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
				698
				699	(* binoprhs
				700	* ::= ('+' primary)* *)
				701	and parse_bin_rhs expr_prec lhs stream =
				702	match Stream.peek stream with
				703	(* If this is a binop, find its precedence. *)
				704	\| Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
				705	let token_prec = precedence c in
				706
				707	(* If this is a binop that binds at least as tightly as the current binop,
				708	* consume it, otherwise we are done. *)
				709	if token_prec < expr_prec then lhs else begin
				710	(* Eat the binop. *)
				711	Stream.junk stream;
				712
				713	(* Parse the primary expression after the binary operator. *)
				714	let rhs = parse_primary stream in
				715
				716	(* Okay, we know this is a binop. *)
				717	let rhs =
				718	match Stream.peek stream with
				719	\| Some (Token.Kwd c2) ->
				720	(* If BinOp binds less tightly with rhs than the operator after
				721	* rhs, let the pending operator take rhs as its lhs. *)
				722	let next_prec = precedence c2 in
				723	if token_prec < next_prec
				724	then parse_bin_rhs (token_prec + 1) rhs stream
				725	else rhs
				726	\| _ -> rhs
				727	in
				728
				729	(* Merge lhs/rhs. *)
				730	let lhs = Ast.Binary (c, lhs, rhs) in
				731	parse_bin_rhs expr_prec lhs stream
				732	end
				733	\| _ -> lhs
				734
				735	(* expression
				736	* ::= primary binoprhs *)
				737	and parse_expr = parser
				738	\| [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream
				739
				740	(* prototype
				741	* ::= id '(' id* ')' *)
				742	let parse_prototype =
				743	let rec parse_args accumulator = parser
				744	\| [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
				745	\| [< >] -> accumulator
				746	in
				747
				748	parser
				749	\| [< 'Token.Ident id;
				750	'Token.Kwd '(' ?? "expected '(' in prototype";
				751	args=parse_args [];
				752	'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
				753	(* success. *)
				754	Ast.Prototype (id, Array.of_list (List.rev args))
				755
				756	\| [< >] ->
				757	raise (Stream.Error "expected function name in prototype")
				758
				759	(* definition ::= 'def' prototype expression *)
				760	let parse_definition = parser
				761	\| [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
				762	Ast.Function (p, e)
				763
				764	(* toplevelexpr ::= expression *)
				765	let parse_toplevel = parser
				766	\| [< e=parse_expr >] ->
				767	(* Make an anonymous proto. *)
				768	Ast.Function (Ast.Prototype ("", [\|\|]), e)
				769
				770	(* external ::= 'extern' prototype *)
				771	let parse_extern = parser
				772	\| [< 'Token.Extern; e=parse_prototype >] -> e
				773	</pre>
				774	</dd>
				775
				776	<dt>codegen.ml:</dt>
				777	<dd class="doc_code">
				778	<pre>
				779	(*===----------------------------------------------------------------------===
				780	* Code Generation
				781	===----------------------------------------------------------------------===)
				782
				783	open Llvm
				784
				785	exception Error of string
				786
				787	let the_module = create_module "my cool jit"
				788	let builder = builder ()
				789	let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
				790
				791	let rec codegen_expr = function
				792	\| Ast.Number n -> const_float double_type n
				793	\| Ast.Variable name ->
				794	(try Hashtbl.find named_values name with
				795	\| Not_found -> raise (Error "unknown variable name"))
				796	\| Ast.Binary (op, lhs, rhs) ->
				797	let lhs_val = codegen_expr lhs in
				798	let rhs_val = codegen_expr rhs in
				799	begin
				800	match op with
				801	\| '+' -> build_add lhs_val rhs_val "addtmp" builder
				802	\| '-' -> build_sub lhs_val rhs_val "subtmp" builder
				803	\| '*' -> build_mul lhs_val rhs_val "multmp" builder
				804	\| '<' ->
				805	(* Convert bool 0/1 to double 0.0 or 1.0 *)
				806	let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
				807	build_uitofp i double_type "booltmp" builder
				808	\| _ -> raise (Error "invalid binary operator")
				809	end
				810	\| Ast.Call (callee, args) ->
				811	(* Look up the name in the module table. *)
				812	let callee =
				813	match lookup_function callee the_module with
				814	\| Some callee -> callee
				815	\| None -> raise (Error "unknown function referenced")
				816	in
				817	let params = params callee in
				818
				819	(* If argument mismatch error. *)
				820	if Array.length params == Array.length args then () else
				821	raise (Error "incorrect # arguments passed");
				822	let args = Array.map codegen_expr args in
				823	build_call callee args "calltmp" builder
				824
				825	let codegen_proto = function
				826	\| Ast.Prototype (name, args) ->
				827	(* Make the function type: double(double,double) etc. *)
				828	let doubles = Array.make (Array.length args) double_type in
				829	let ft = function_type double_type doubles in
				830	let f =
				831	match lookup_function name the_module with
				832	\| None -> declare_function name ft the_module
				833
				834	(* If 'f' conflicted, there was already something named 'name'. If it
				835	* has a body, don't allow redefinition or reextern. *)
				836	\| Some f ->
				837	(* If 'f' already has a body, reject this. *)
				838	if block_begin f <> At_end f then
				839	raise (Error "redefinition of function");
				840
				841	(* If 'f' took a different number of arguments, reject. *)
				842	if element_type (type_of f) <> ft then
				843	raise (Error "redefinition of function with different # args");
				844	f
				845	in
				846
				847	(* Set names for all arguments. *)
				848	Array.iteri (fun i a ->
				849	let n = args.(i) in
				850	set_value_name n a;
				851	Hashtbl.add named_values n a;
				852	) (params f);
				853	f
				854
				855	let codegen_func the_fpm = function
				856	\| Ast.Function (proto, body) ->
				857	Hashtbl.clear named_values;
				858	let the_function = codegen_proto proto in
				859
				860	(* Create a new basic block to start insertion into. *)
				861	let bb = append_block "entry" the_function in
				862	position_at_end bb builder;
				863
				864	try
				865	let ret_val = codegen_expr body in
				866
				867	(* Finish off the function. *)
				868	let _ = build_ret ret_val builder in
				869
				870	(* Validate the generated code, checking for consistency. *)
				871	Llvm_analysis.assert_valid_function the_function;
				872
				873	(* Optimize the function. *)
				874	let _ = PassManager.run_function the_function the_fpm in
				875
				876	the_function
				877	with e ->
				878	delete_function the_function;
				879	raise e
				880	</pre>
				881	</dd>
				882
				883	<dt>toplevel.ml:</dt>
				884	<dd class="doc_code">
				885	<pre>
				886	(*===----------------------------------------------------------------------===
				887	* Top-Level parsing and JIT Driver
				888	===----------------------------------------------------------------------===)
				889
				890	open Llvm
				891	open Llvm_executionengine
				892
				893	(* top ::= definition \| external \| expression \| ';' *)
				894	let rec main_loop the_fpm the_execution_engine stream =
				895	match Stream.peek stream with
				896	\| None -> ()
				897
				898	(* ignore top-level semicolons. *)
				899	\| Some (Token.Kwd ';') ->
				900	Stream.junk stream;
				901	main_loop the_fpm the_execution_engine stream
				902
				903	\| Some token ->
				904	begin
				905	try match token with
				906	\| Token.Def ->
				907	let e = Parser.parse_definition stream in
				908	print_endline "parsed a function definition.";
				909	dump_value (Codegen.codegen_func the_fpm e);
				910	\| Token.Extern ->
				911	let e = Parser.parse_extern stream in
				912	print_endline "parsed an extern.";
				913	dump_value (Codegen.codegen_proto e);
				914	\| _ ->
				915	(* Evaluate a top-level expression into an anonymous function. *)
				916	let e = Parser.parse_toplevel stream in
				917	print_endline "parsed a top-level expr";
				918	let the_function = Codegen.codegen_func the_fpm e in
				919	dump_value the_function;
				920
				921	(* JIT the function, returning a function pointer. *)
				922	let result = ExecutionEngine.run_function the_function [\|\|]
				923	the_execution_engine in
				924
				925	print_string "Evaluated to ";
				926	print_float (GenericValue.as_float double_type result);
				927	print_newline ();
				928	with Stream.Error s \| Codegen.Error s ->
				929	(* Skip token for error recovery. *)
				930	Stream.junk stream;
				931	print_endline s;
				932	end;
				933	print_string "ready> "; flush stdout;
				934	main_loop the_fpm the_execution_engine stream
				935	</pre>
				936	</dd>
				937
				938	<dt>toy.ml:</dt>
				939	<dd class="doc_code">
				940	<pre>
				941	(*===----------------------------------------------------------------------===
				942	* Main driver code.
				943	===----------------------------------------------------------------------===)
				944
				945	open Llvm
				946	open Llvm_executionengine
				947	open Llvm_target
				948	open Llvm_scalar_opts
				949
				950	let main () =
				951	(* Install standard binary operators.
				952	* 1 is the lowest precedence. *)
				953	Hashtbl.add Parser.binop_precedence '<' 10;
				954	Hashtbl.add Parser.binop_precedence '+' 20;
				955	Hashtbl.add Parser.binop_precedence '-' 20;
				956	Hashtbl.add Parser.binop_precedence '' 40; ( highest. *)
				957
				958	(* Prime the first token. *)
				959	print_string "ready> "; flush stdout;
				960	let stream = Lexer.lex (Stream.of_channel stdin) in
				961
				962	(* Create the JIT. *)
				963	let the_module_provider = ModuleProvider.create Codegen.the_module in
				964	let the_execution_engine = ExecutionEngine.create the_module_provider in
				965	let the_fpm = PassManager.create_function the_module_provider in
				966
				967	(* Set up the optimizer pipeline. Start with registering info about how the
				968	* target lays out data structures. *)
				969	TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
				970
				971	(* Do simple "peephole" optimizations and bit-twiddling optzn. *)
				972	add_instruction_combining the_fpm;
				973
				974	(* reassociate expressions. *)
				975	add_reassociation the_fpm;
				976
				977	(* Eliminate Common SubExpressions. *)
				978	add_gvn the_fpm;
				979
				980	(* Simplify the control flow graph (deleting unreachable blocks, etc). *)
				981	add_cfg_simplification the_fpm;
				982
				983	(* Run the main "interpreter loop" now. *)
				984	Toplevel.main_loop the_fpm the_execution_engine stream;
				985
				986	(* Print out all the generated code. *)
				987	dump_module Codegen.the_module
				988	;;
				989
				990	main ()
				991	</pre>
				992	</dd>
				993
				994	<dt>bindings.c</dt>
				995	<dd class="doc_code">
				996	<pre>
				997	#include <stdio.h>
				998
				999	/* putchard - putchar that takes a double and returns 0. */
				1000	extern double putchard(double X) {
				1001	putchar((char)X);
				1002	return 0;
				1003	}
				1004	</pre>
				1005	</dd>
				1006	</dl>
				1007
				1008	<a href="OCamlLangImpl5.html">Next: Extending the language: control flow</a>
				1009	</div>
				1010
				1011	<!-- *********************************************************************** -->
				1012	<hr>
				1013	<address>
				1014	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				1015	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				1016	<a href="http://validator.w3.org/check/referer"><img
				1017	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
				1018
				1019	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1020	<a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br>
				1021	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				1022	Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
				1023	</address>
				1024	</body>
				1025	</html>