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

blob: ec3c20bc6bfac6d08671ce25ffe8751dfcead110 [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
				209	(* Run the main "interpreter loop" now. *)
				210	Toplevel.main_loop the_fpm the_execution_engine stream;
				211	</pre>
				212	</div>
				213
				214	<p>This code defines two values, an <tt>Llvm.llmoduleprovider</tt> and a
				215	<tt>Llvm.PassManager.t</tt>. The former is basically a wrapper around our
				216	<tt>Llvm.llmodule</tt> that the <tt>Llvm.PassManager.t</tt> requires. It
				217	provides certain flexibility that we're not going to take advantage of here,
				218	so I won't dive into any details about it.</p>
				219
				220	<p>The meat of the matter here, is the definition of "<tt>the_fpm</tt>". It
				221	requires a pointer to the <tt>the_module</tt> (through the
				222	<tt>the_module_provider</tt>) to construct itself. Once it is set up, we use a
				223	series of "add" calls to add a bunch of LLVM passes. The first pass is
				224	basically boilerplate, it adds a pass so that later optimizations know how the
				225	data structures in the program are layed out. The
				226	"<tt>the_execution_engine</tt>" variable is related to the JIT, which we will
				227	get to in the next section.</p>
				228
				229	<p>In this case, we choose to add 4 optimization passes. The passes we chose
				230	here are a pretty standard set of "cleanup" optimizations that are useful for
				231	a wide variety of code. I won't delve into what they do but, believe me,
				232	they are a good starting place :).</p>
				233
				234	<p>Once the <tt>Llvm.PassManager.</tt> is set up, we need to make use of it.
				235	We do this by running it after our newly created function is constructed (in
				236	<tt>Codegen.codegen_func</tt>), but before it is returned to the client:</p>
				237
				238	<div class="doc_code">
				239	<pre>
				240	let codegen_func the_fpm = function
Erick Tryzelaar	35295ff	2008-03-31 08:44:50 +0000	[diff] [blame]	241	...
Erick Tryzelaar	37c076b	2008-03-30 09:57:12 +0000	[diff] [blame]	242	try
				243	let ret_val = codegen_expr body in
				244
				245	(* Finish off the function. *)
				246	let _ = build_ret ret_val builder in
				247
				248	(* Validate the generated code, checking for consistency. *)
				249	Llvm_analysis.assert_valid_function the_function;
				250
				251	(* Optimize the function. *)
				252	let _ = PassManager.run_function the_function the_fpm in
				253
				254	the_function
				255	</pre>
				256	</div>
				257
				258	<p>As you can see, this is pretty straightforward. The <tt>the_fpm</tt>
				259	optimizes and updates the LLVM Function* in place, improving (hopefully) its
				260	body. With this in place, we can try our test above again:</p>
				261
				262	<div class="doc_code">
				263	<pre>
				264	ready> <b>def test(x) (1+2+x)*(x+(1+2));</b>
				265	ready> Read function definition:
				266	define double @test(double %x) {
				267	entry:
				268	%addtmp = add double %x, 3.000000e+00
				269	%multmp = mul double %addtmp, %addtmp
				270	ret double %multmp
				271	}
				272	</pre>
				273	</div>
				274
				275	<p>As expected, we now get our nicely optimized code, saving a floating point
				276	add instruction from every execution of this function.</p>
				277
				278	<p>LLVM provides a wide variety of optimizations that can be used in certain
				279	circumstances. Some <a href="../Passes.html">documentation about the various
				280	passes</a> is available, but it isn't very complete. Another good source of
				281	ideas can come from looking at the passes that <tt>llvm-gcc</tt> or
				282	<tt>llvm-ld</tt> run to get started. The "<tt>opt</tt>" tool allows you to
				283	experiment with passes from the command line, so you can see if they do
				284	anything.</p>
				285
				286	<p>Now that we have reasonable code coming out of our front-end, lets talk about
				287	executing it!</p>
				288
				289	</div>
				290
				291	<!-- *********************************************************************** -->
				292	<div class="doc_section"><a name="jit">Adding a JIT Compiler</a></div>
				293	<!-- *********************************************************************** -->
				294
				295	<div class="doc_text">
				296
				297	<p>Code that is available in LLVM IR can have a wide variety of tools
				298	applied to it. For example, you can run optimizations on it (as we did above),
				299	you can dump it out in textual or binary forms, you can compile the code to an
				300	assembly file (.s) for some target, or you can JIT compile it. The nice thing
				301	about the LLVM IR representation is that it is the "common currency" between
				302	many different parts of the compiler.
				303	</p>
				304
				305	<p>In this section, we'll add JIT compiler support to our interpreter. The
				306	basic idea that we want for Kaleidoscope is to have the user enter function
				307	bodies as they do now, but immediately evaluate the top-level expressions they
				308	type in. For example, if they type in "1 + 2;", we should evaluate and print
				309	out 3. If they define a function, they should be able to call it from the
				310	command line.</p>
				311
				312	<p>In order to do this, we first declare and initialize the JIT. This is done
				313	by adding a global variable and a call in <tt>main</tt>:</p>
				314
				315	<div class="doc_code">
				316	<pre>
				317	...
				318	let main () =
				319	...
Erick Tryzelaar	35295ff	2008-03-31 08:44:50 +0000	[diff] [blame]	320	<b>(* Create the JIT. *)
Erick Tryzelaar	37c076b	2008-03-30 09:57:12 +0000	[diff] [blame]	321	let the_module_provider = ModuleProvider.create Codegen.the_module in
Erick Tryzelaar	35295ff	2008-03-31 08:44:50 +0000	[diff] [blame]	322	let the_execution_engine = ExecutionEngine.create the_module_provider in</b>
Erick Tryzelaar	37c076b	2008-03-30 09:57:12 +0000	[diff] [blame]	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
Erick Tryzelaar	35295ff	2008-03-31 08:44:50 +0000	[diff] [blame]	511	<div class="doc_code">
				512	<pre>
				513	# Compile
				514	ocamlbuild toy.byte
				515	# Run
				516	./toy.byte
				517	</pre>
				518	</div>
				519
				520	<p>Here is the code:</p>
				521
Erick Tryzelaar	37c076b	2008-03-30 09:57:12 +0000	[diff] [blame]	522	<dl>
				523	<dt>_tags:</dt>
				524	<dd class="doc_code">
				525	<pre>
				526	<{lexer,parser}.ml>: use_camlp4, pp(camlp4of)
				527	<*.{byte,native}>: g++, use_llvm, use_llvm_analysis
				528	<*.{byte,native}>: use_llvm_executionengine, use_llvm_target
				529	<*.{byte,native}>: use_llvm_scalar_opts, use_bindings
				530	</pre>
				531	</dd>
				532
				533	<dt>myocamlbuild.ml:</dt>
				534	<dd class="doc_code">
				535	<pre>
				536	open Ocamlbuild_plugin;;
				537
				538	ocaml_lib ~extern:true "llvm";;
				539	ocaml_lib ~extern:true "llvm_analysis";;
				540	ocaml_lib ~extern:true "llvm_executionengine";;
				541	ocaml_lib ~extern:true "llvm_target";;
				542	ocaml_lib ~extern:true "llvm_scalar_opts";;
				543
				544	flag ["link"; "ocaml"; "g++"] (S[A"-cc"; A"g++"]);;
				545	dep ["link"; "ocaml"; "use_bindings"] ["bindings.o"];;
				546	</pre>
				547	</dd>
				548
				549	<dt>token.ml:</dt>
				550	<dd class="doc_code">
				551	<pre>
				552	(*===----------------------------------------------------------------------===
				553	* Lexer Tokens
				554	===----------------------------------------------------------------------===)
				555
				556	(* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of
				557	* these others for known things. *)
				558	type token =
				559	(* commands *)
				560	\| Def \| Extern
				561
				562	(* primary *)
				563	\| Ident of string \| Number of float
				564
				565	(* unknown *)
				566	\| Kwd of char
				567	</pre>
				568	</dd>
				569
				570	<dt>lexer.ml:</dt>
				571	<dd class="doc_code">
				572	<pre>
				573	(*===----------------------------------------------------------------------===
				574	* Lexer
				575	===----------------------------------------------------------------------===)
				576
				577	let rec lex = parser
				578	(* Skip any whitespace. *)
				579	\| [< ' (' ' \| '\n' \| '\r' \| '\t'); stream >] -> lex stream
				580
				581	(* identifier: [a-zA-Z][a-zA-Z0-9] *)
				582	\| [< ' ('A' .. 'Z' \| 'a' .. 'z' as c); stream >] ->
				583	let buffer = Buffer.create 1 in
				584	Buffer.add_char buffer c;
				585	lex_ident buffer stream
				586
				587	(* number: [0-9.]+ *)
				588	\| [< ' ('0' .. '9' as c); stream >] ->
				589	let buffer = Buffer.create 1 in
				590	Buffer.add_char buffer c;
				591	lex_number buffer stream
				592
				593	(* Comment until end of line. *)
				594	\| [< ' ('#'); stream >] ->
				595	lex_comment stream
				596
				597	(* Otherwise, just return the character as its ascii value. *)
				598	\| [< 'c; stream >] ->
				599	[< 'Token.Kwd c; lex stream >]
				600
				601	(* end of stream. *)
				602	\| [< >] -> [< >]
				603
				604	and lex_number buffer = parser
				605	\| [< ' ('0' .. '9' \| '.' as c); stream >] ->
				606	Buffer.add_char buffer c;
				607	lex_number buffer stream
				608	\| [< stream=lex >] ->
				609	[< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >]
				610
				611	and lex_ident buffer = parser
				612	\| [< ' ('A' .. 'Z' \| 'a' .. 'z' \| '0' .. '9' as c); stream >] ->
				613	Buffer.add_char buffer c;
				614	lex_ident buffer stream
				615	\| [< stream=lex >] ->
				616	match Buffer.contents buffer with
				617	\| "def" -> [< 'Token.Def; stream >]
				618	\| "extern" -> [< 'Token.Extern; stream >]
				619	\| id -> [< 'Token.Ident id; stream >]
				620
				621	and lex_comment = parser
				622	\| [< ' ('\n'); stream=lex >] -> stream
				623	\| [< 'c; e=lex_comment >] -> e
				624	\| [< >] -> [< >]
				625	</pre>
				626	</dd>
				627
				628	<dt>ast.ml:</dt>
				629	<dd class="doc_code">
				630	<pre>
				631	(*===----------------------------------------------------------------------===
				632	* Abstract Syntax Tree (aka Parse Tree)
				633	===----------------------------------------------------------------------===)
				634
				635	(* expr - Base type for all expression nodes. *)
				636	type expr =
				637	(* variant for numeric literals like "1.0". *)
				638	\| Number of float
				639
				640	(* variant for referencing a variable, like "a". *)
				641	\| Variable of string
				642
				643	(* variant for a binary operator. *)
				644	\| Binary of char * expr * expr
				645
				646	(* variant for function calls. *)
				647	\| Call of string * expr array
				648
				649	(* proto - This type represents the "prototype" for a function, which captures
				650	* its name, and its argument names (thus implicitly the number of arguments the
				651	* function takes). *)
				652	type proto = Prototype of string * string array
				653
				654	(* func - This type represents a function definition itself. *)
				655	type func = Function of proto * expr
				656	</pre>
				657	</dd>
				658
				659	<dt>parser.ml:</dt>
				660	<dd class="doc_code">
				661	<pre>
				662	(*===---------------------------------------------------------------------===
				663	* Parser
				664	===---------------------------------------------------------------------===)
				665
				666	(* binop_precedence - This holds the precedence for each binary operator that is
				667	* defined *)
				668	let binop_precedence:(char, int) Hashtbl.t = Hashtbl.create 10
				669
				670	(* precedence - Get the precedence of the pending binary operator token. *)
				671	let precedence c = try Hashtbl.find binop_precedence c with Not_found -> -1
				672
				673	(* primary
				674	* ::= identifier
				675	* ::= numberexpr
				676	* ::= parenexpr *)
				677	let rec parse_primary = parser
				678	(* numberexpr ::= number *)
				679	\| [< 'Token.Number n >] -> Ast.Number n
				680
				681	(* parenexpr ::= '(' expression ')' *)
				682	\| [< 'Token.Kwd '('; e=parse_expr; 'Token.Kwd ')' ?? "expected ')'" >] -> e
				683
				684	(* identifierexpr
				685	* ::= identifier
				686	* ::= identifier '(' argumentexpr ')' *)
				687	\| [< 'Token.Ident id; stream >] ->
				688	let rec parse_args accumulator = parser
				689	\| [< e=parse_expr; stream >] ->
				690	begin parser
				691	\| [< 'Token.Kwd ','; e=parse_args (e :: accumulator) >] -> e
				692	\| [< >] -> e :: accumulator
				693	end stream
				694	\| [< >] -> accumulator
				695	in
				696	let rec parse_ident id = parser
				697	(* Call. *)
				698	\| [< 'Token.Kwd '(';
				699	args=parse_args [];
				700	'Token.Kwd ')' ?? "expected ')'">] ->
				701	Ast.Call (id, Array.of_list (List.rev args))
				702
				703	(* Simple variable ref. *)
				704	\| [< >] -> Ast.Variable id
				705	in
				706	parse_ident id stream
				707
				708	\| [< >] -> raise (Stream.Error "unknown token when expecting an expression.")
				709
				710	(* binoprhs
				711	* ::= ('+' primary)* *)
				712	and parse_bin_rhs expr_prec lhs stream =
				713	match Stream.peek stream with
				714	(* If this is a binop, find its precedence. *)
				715	\| Some (Token.Kwd c) when Hashtbl.mem binop_precedence c ->
				716	let token_prec = precedence c in
				717
				718	(* If this is a binop that binds at least as tightly as the current binop,
				719	* consume it, otherwise we are done. *)
				720	if token_prec < expr_prec then lhs else begin
				721	(* Eat the binop. *)
				722	Stream.junk stream;
				723
				724	(* Parse the primary expression after the binary operator. *)
				725	let rhs = parse_primary stream in
				726
				727	(* Okay, we know this is a binop. *)
				728	let rhs =
				729	match Stream.peek stream with
				730	\| Some (Token.Kwd c2) ->
				731	(* If BinOp binds less tightly with rhs than the operator after
				732	* rhs, let the pending operator take rhs as its lhs. *)
				733	let next_prec = precedence c2 in
				734	if token_prec < next_prec
				735	then parse_bin_rhs (token_prec + 1) rhs stream
				736	else rhs
				737	\| _ -> rhs
				738	in
				739
				740	(* Merge lhs/rhs. *)
				741	let lhs = Ast.Binary (c, lhs, rhs) in
				742	parse_bin_rhs expr_prec lhs stream
				743	end
				744	\| _ -> lhs
				745
				746	(* expression
				747	* ::= primary binoprhs *)
				748	and parse_expr = parser
				749	\| [< lhs=parse_primary; stream >] -> parse_bin_rhs 0 lhs stream
				750
				751	(* prototype
				752	* ::= id '(' id* ')' *)
				753	let parse_prototype =
				754	let rec parse_args accumulator = parser
				755	\| [< 'Token.Ident id; e=parse_args (id::accumulator) >] -> e
				756	\| [< >] -> accumulator
				757	in
				758
				759	parser
				760	\| [< 'Token.Ident id;
				761	'Token.Kwd '(' ?? "expected '(' in prototype";
				762	args=parse_args [];
				763	'Token.Kwd ')' ?? "expected ')' in prototype" >] ->
				764	(* success. *)
				765	Ast.Prototype (id, Array.of_list (List.rev args))
				766
				767	\| [< >] ->
				768	raise (Stream.Error "expected function name in prototype")
				769
				770	(* definition ::= 'def' prototype expression *)
				771	let parse_definition = parser
				772	\| [< 'Token.Def; p=parse_prototype; e=parse_expr >] ->
				773	Ast.Function (p, e)
				774
				775	(* toplevelexpr ::= expression *)
				776	let parse_toplevel = parser
				777	\| [< e=parse_expr >] ->
				778	(* Make an anonymous proto. *)
				779	Ast.Function (Ast.Prototype ("", [\|\|]), e)
				780
				781	(* external ::= 'extern' prototype *)
				782	let parse_extern = parser
				783	\| [< 'Token.Extern; e=parse_prototype >] -> e
				784	</pre>
				785	</dd>
				786
				787	<dt>codegen.ml:</dt>
				788	<dd class="doc_code">
				789	<pre>
				790	(*===----------------------------------------------------------------------===
				791	* Code Generation
				792	===----------------------------------------------------------------------===)
				793
				794	open Llvm
				795
				796	exception Error of string
				797
Erick Tryzelaar	1f3d276	2009-08-19 17:32:38 +0000	[diff] [blame]	798	let context = global_context ()
				799	let the_module = create_module context "my cool jit"
				800	let builder = builder context
Erick Tryzelaar	37c076b	2008-03-30 09:57:12 +0000	[diff] [blame]	801	let named_values:(string, llvalue) Hashtbl.t = Hashtbl.create 10
				802
				803	let rec codegen_expr = function
				804	\| Ast.Number n -> const_float double_type n
				805	\| Ast.Variable name ->
				806	(try Hashtbl.find named_values name with
				807	\| Not_found -> raise (Error "unknown variable name"))
				808	\| Ast.Binary (op, lhs, rhs) ->
				809	let lhs_val = codegen_expr lhs in
				810	let rhs_val = codegen_expr rhs in
				811	begin
				812	match op with
				813	\| '+' -> build_add lhs_val rhs_val "addtmp" builder
				814	\| '-' -> build_sub lhs_val rhs_val "subtmp" builder
				815	\| '*' -> build_mul lhs_val rhs_val "multmp" builder
				816	\| '<' ->
				817	(* Convert bool 0/1 to double 0.0 or 1.0 *)
				818	let i = build_fcmp Fcmp.Ult lhs_val rhs_val "cmptmp" builder in
				819	build_uitofp i double_type "booltmp" builder
				820	\| _ -> raise (Error "invalid binary operator")
				821	end
				822	\| Ast.Call (callee, args) ->
				823	(* Look up the name in the module table. *)
				824	let callee =
				825	match lookup_function callee the_module with
				826	\| Some callee -> callee
				827	\| None -> raise (Error "unknown function referenced")
				828	in
				829	let params = params callee in
				830
				831	(* If argument mismatch error. *)
				832	if Array.length params == Array.length args then () else
				833	raise (Error "incorrect # arguments passed");
				834	let args = Array.map codegen_expr args in
				835	build_call callee args "calltmp" builder
				836
				837	let codegen_proto = function
				838	\| Ast.Prototype (name, args) ->
				839	(* Make the function type: double(double,double) etc. *)
				840	let doubles = Array.make (Array.length args) double_type in
				841	let ft = function_type double_type doubles in
				842	let f =
				843	match lookup_function name the_module with
				844	\| None -> declare_function name ft the_module
				845
				846	(* If 'f' conflicted, there was already something named 'name'. If it
				847	* has a body, don't allow redefinition or reextern. *)
				848	\| Some f ->
				849	(* If 'f' already has a body, reject this. *)
				850	if block_begin f <> At_end f then
				851	raise (Error "redefinition of function");
				852
				853	(* If 'f' took a different number of arguments, reject. *)
				854	if element_type (type_of f) <> ft then
				855	raise (Error "redefinition of function with different # args");
				856	f
				857	in
				858
				859	(* Set names for all arguments. *)
				860	Array.iteri (fun i a ->
				861	let n = args.(i) in
				862	set_value_name n a;
				863	Hashtbl.add named_values n a;
				864	) (params f);
				865	f
				866
				867	let codegen_func the_fpm = function
				868	\| Ast.Function (proto, body) ->
				869	Hashtbl.clear named_values;
				870	let the_function = codegen_proto proto in
				871
				872	(* Create a new basic block to start insertion into. *)
				873	let bb = append_block "entry" the_function in
				874	position_at_end bb builder;
				875
				876	try
				877	let ret_val = codegen_expr body in
				878
				879	(* Finish off the function. *)
				880	let _ = build_ret ret_val builder in
				881
				882	(* Validate the generated code, checking for consistency. *)
				883	Llvm_analysis.assert_valid_function the_function;
				884
				885	(* Optimize the function. *)
				886	let _ = PassManager.run_function the_function the_fpm in
				887
				888	the_function
				889	with e ->
				890	delete_function the_function;
				891	raise e
				892	</pre>
				893	</dd>
				894
				895	<dt>toplevel.ml:</dt>
				896	<dd class="doc_code">
				897	<pre>
				898	(*===----------------------------------------------------------------------===
				899	* Top-Level parsing and JIT Driver
				900	===----------------------------------------------------------------------===)
				901
				902	open Llvm
				903	open Llvm_executionengine
				904
				905	(* top ::= definition \| external \| expression \| ';' *)
				906	let rec main_loop the_fpm the_execution_engine stream =
				907	match Stream.peek stream with
				908	\| None -> ()
				909
				910	(* ignore top-level semicolons. *)
				911	\| Some (Token.Kwd ';') ->
				912	Stream.junk stream;
				913	main_loop the_fpm the_execution_engine stream
				914
				915	\| Some token ->
				916	begin
				917	try match token with
				918	\| Token.Def ->
				919	let e = Parser.parse_definition stream in
				920	print_endline "parsed a function definition.";
				921	dump_value (Codegen.codegen_func the_fpm e);
				922	\| Token.Extern ->
				923	let e = Parser.parse_extern stream in
				924	print_endline "parsed an extern.";
				925	dump_value (Codegen.codegen_proto e);
				926	\| _ ->
				927	(* Evaluate a top-level expression into an anonymous function. *)
				928	let e = Parser.parse_toplevel stream in
				929	print_endline "parsed a top-level expr";
				930	let the_function = Codegen.codegen_func the_fpm e in
				931	dump_value the_function;
				932
				933	(* JIT the function, returning a function pointer. *)
				934	let result = ExecutionEngine.run_function the_function [\|\|]
				935	the_execution_engine in
				936
				937	print_string "Evaluated to ";
				938	print_float (GenericValue.as_float double_type result);
				939	print_newline ();
				940	with Stream.Error s \| Codegen.Error s ->
				941	(* Skip token for error recovery. *)
				942	Stream.junk stream;
				943	print_endline s;
				944	end;
				945	print_string "ready> "; flush stdout;
				946	main_loop the_fpm the_execution_engine stream
				947	</pre>
				948	</dd>
				949
				950	<dt>toy.ml:</dt>
				951	<dd class="doc_code">
				952	<pre>
				953	(*===----------------------------------------------------------------------===
				954	* Main driver code.
				955	===----------------------------------------------------------------------===)
				956
				957	open Llvm
				958	open Llvm_executionengine
				959	open Llvm_target
				960	open Llvm_scalar_opts
				961
				962	let main () =
				963	(* Install standard binary operators.
				964	* 1 is the lowest precedence. *)
				965	Hashtbl.add Parser.binop_precedence '<' 10;
				966	Hashtbl.add Parser.binop_precedence '+' 20;
				967	Hashtbl.add Parser.binop_precedence '-' 20;
				968	Hashtbl.add Parser.binop_precedence '' 40; ( highest. *)
				969
				970	(* Prime the first token. *)
				971	print_string "ready> "; flush stdout;
				972	let stream = Lexer.lex (Stream.of_channel stdin) in
				973
				974	(* Create the JIT. *)
				975	let the_module_provider = ModuleProvider.create Codegen.the_module in
				976	let the_execution_engine = ExecutionEngine.create the_module_provider in
				977	let the_fpm = PassManager.create_function the_module_provider in
				978
				979	(* Set up the optimizer pipeline. Start with registering info about how the
				980	* target lays out data structures. *)
				981	TargetData.add (ExecutionEngine.target_data the_execution_engine) the_fpm;
				982
				983	(* Do simple "peephole" optimizations and bit-twiddling optzn. *)
				984	add_instruction_combining the_fpm;
				985
				986	(* reassociate expressions. *)
				987	add_reassociation the_fpm;
				988
				989	(* Eliminate Common SubExpressions. *)
				990	add_gvn the_fpm;
				991
				992	(* Simplify the control flow graph (deleting unreachable blocks, etc). *)
				993	add_cfg_simplification the_fpm;
				994
				995	(* Run the main "interpreter loop" now. *)
				996	Toplevel.main_loop the_fpm the_execution_engine stream;
				997
				998	(* Print out all the generated code. *)
				999	dump_module Codegen.the_module
				1000	;;
				1001
				1002	main ()
				1003	</pre>
				1004	</dd>
				1005
				1006	<dt>bindings.c</dt>
				1007	<dd class="doc_code">
				1008	<pre>
				1009	#include <stdio.h>
				1010
				1011	/* putchard - putchar that takes a double and returns 0. */
				1012	extern double putchard(double X) {
				1013	putchar((char)X);
				1014	return 0;
				1015	}
				1016	</pre>
				1017	</dd>
				1018	</dl>
				1019
				1020	<a href="OCamlLangImpl5.html">Next: Extending the language: control flow</a>
				1021	</div>
				1022
				1023	<!-- *********************************************************************** -->
				1024	<hr>
				1025	<address>
				1026	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				1027	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				1028	<a href="http://validator.w3.org/check/referer"><img
				1029	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
				1030
				1031	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1032	<a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br>
				1033	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				1034	Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
				1035	</address>
				1036	</body>
				1037	</html>