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

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