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

blob: 11a6cc0177f71e653cd791839b693937f55899f6 [file] [log] [blame]

Chris Lattner	c0b42e9	2007-10-23 06:27:55 +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	<link rel="stylesheet" href="../llvm.css" type="text/css">
				10	</head>
				11
				12	<body>
				13
				14	<div class="doc_title">Kaleidoscope: Adding JIT and Optimizer Support</div>
				15
Chris Lattner	128eb86	2007-11-05 19:06:59 +0000	[diff] [blame]	16	<ul>
Chris Lattner	0e555b1	2007-11-05 20:04:56 +0000	[diff] [blame]	17	<li><a href="index.html">Up to Tutorial Index</a></li>
Chris Lattner	128eb86	2007-11-05 19:06:59 +0000	[diff] [blame]	18	<li>Chapter 4
				19	<ol>
				20	<li><a href="#intro">Chapter 4 Introduction</a></li>
				21	<li><a href="#trivialconstfold">Trivial Constant Folding</a></li>
				22	<li><a href="#optimizerpasses">LLVM Optimization Passes</a></li>
				23	<li><a href="#jit">Adding a JIT Compiler</a></li>
				24	<li><a href="#code">Full Code Listing</a></li>
				25	</ol>
				26	</li>
Chris Lattner	0e555b1	2007-11-05 20:04:56 +0000	[diff] [blame]	27	<li><a href="LangImpl5.html">Chapter 5</a>: Extending the Language: Control
				28	Flow</li>
Chris Lattner	128eb86	2007-11-05 19:06:59 +0000	[diff] [blame]	29	</ul>
				30
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	31	<div class="doc_author">
				32	<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
				33	</div>
				34
				35	<!-- *********************************************************************** -->
Chris Lattner	128eb86	2007-11-05 19:06:59 +0000	[diff] [blame]	36	<div class="doc_section"><a name="intro">Chapter 4 Introduction</a></div>
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	37	<!-- *********************************************************************** -->
				38
				39	<div class="doc_text">
				40
Chris Lattner	128eb86	2007-11-05 19:06:59 +0000	[diff] [blame]	41	<p>Welcome to Chapter 4 of the "<a href="index.html">Implementing a language
				42	with LLVM</a>" tutorial. Parts 1-3 described the implementation of a simple
				43	language and included support for generating LLVM IR. This chapter describes
				44	two new techniques: adding optimizer support to your language, and adding JIT
				45	compiler support. This shows how to get nice efficient code for your
				46	language.</p>
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	47
				48	</div>
				49
				50	<!-- *********************************************************************** -->
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	51	<div class="doc_section"><a name="trivialconstfold">Trivial Constant
				52	Folding</a></div>
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	53	<!-- *********************************************************************** -->
				54
				55	<div class="doc_text">
				56
				57	<p>
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	58	Our demonstration for Chapter 3 is elegant and easy to extend. Unfortunately,
				59	it does not produce wonderful code. For example, when compiling simple code,
				60	we don't get obvious optimizations:</p>
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	61
				62	<div class="doc_code">
				63	<pre>
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	64	ready> <b>def test(x) 1+2+x;</b>
				65	Read function definition:
				66	define double @test(double %x) {
				67	entry:
				68	%addtmp = add double 1.000000e+00, 2.000000e+00
				69	%addtmp1 = add double %addtmp, %x
				70	ret double %addtmp1
				71	}
				72	</pre>
				73	</div>
				74
				75	<p>This code is a very very literal transcription of the AST built by parsing
				76	our code, and as such, lacks optimizations like constant folding (we'd like to
				77	get "<tt>add x, 3.0</tt>" in the example above) as well as other more important
				78	optimizations. Constant folding in particular is a very common and very
				79	important optimization: so much so that many language implementors implement
				80	constant folding support in their AST representation.</p>
				81
				82	<p>With LLVM, you don't need to. Since all calls to build LLVM IR go through
				83	the LLVM builder, it would be nice if the builder itself checked to see if there
				84	was a constant folding opportunity when you call it. If so, it could just do
				85	the constant fold and return the constant instead of creating an instruction.
				86	This is exactly what the <tt>LLVMFoldingBuilder</tt> class does. Lets make one
				87	change:
				88
				89	<div class="doc_code">
				90	<pre>
				91	static LLVMFoldingBuilder Builder;
				92	</pre>
				93	</div>
				94
				95	<p>All we did was switch from <tt>LLVMBuilder</tt> to
				96	<tt>LLVMFoldingBuilder</tt>. Though we change no other code, now all of our
				97	instructions are implicitly constant folded without us having to do anything
				98	about it. For example, our example 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
Owen Anderson	6867aec	2007-10-25 06:50:30 +0000	[diff] [blame]	113	<tt>LLVMFoldingBuilder</tt> when generating code like this. It has no
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	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 the get run, see the <a href="../WritingAnLLVMPass.html">How
				169	to Write a Pass</a> document.</p>
				170
				171	<p>For Kaleidoscope, we are currently generating functions on the fly, one at
				172	a time, as the user types them in. We aren't shooting for the ultimate
				173	optimization experience in this setting, but we also want to catch the easy and
				174	quick stuff where possible. As such, we will choose to run a few per-function
				175	optimizations as the user types the function in. If we wanted to make a "static
				176	Kaleidoscope compiler", we would use exactly the code we have now, except that
				177	we would defer running the optimizer until the entire file has been parsed.</p>
				178
				179	<p>In order to get per-function optimizations going, we need to set up a
				180	<a href="../WritingAnLLVMPass.html#passmanager">FunctionPassManager</a> to hold and
				181	organize the LLVM optimizations that we want to run. Once we have that, we can
				182	add a set of optimizations to run. The code looks like this:</p>
				183
				184	<div class="doc_code">
				185	<pre>
				186	ExistingModuleProvider OurModuleProvider(TheModule);
				187	FunctionPassManager OurFPM(&OurModuleProvider);
				188
				189	// Set up the optimizer pipeline. Start with registering info about how the
				190	// target lays out data structures.
				191	OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
				192	// Do simple "peephole" optimizations and bit-twiddling optzns.
				193	OurFPM.add(createInstructionCombiningPass());
				194	// Reassociate expressions.
				195	OurFPM.add(createReassociatePass());
				196	// Eliminate Common SubExpressions.
				197	OurFPM.add(createGVNPass());
				198	// Simplify the control flow graph (deleting unreachable blocks, etc).
				199	OurFPM.add(createCFGSimplificationPass());
				200
				201	// Set the global so the code gen can use this.
				202	TheFPM = &OurFPM;
				203
				204	// Run the main "interpreter loop" now.
				205	MainLoop();
				206	</pre>
				207	</div>
				208
				209	<p>This code defines two objects, a <tt>ExistingModuleProvider</tt> and a
				210	<tt>FunctionPassManager</tt>. The former is basically a wrapper around our
				211	<tt>Module</tt> that the PassManager requires. It provides certain flexibility
				212	that we're not going to take advantage of here, so I won't dive into what it is
				213	all about.</p>
				214
				215	<p>The meat of the matter is the definition of the "<tt>OurFPM</tt>". It
				216	requires a pointer to the <tt>Module</tt> (through the <tt>ModuleProvider</tt>)
				217	to construct itself. Once it is set up, we use a series of "add" calls to add
				218	a bunch of LLVM passes. The first pass is basically boilerplate, it adds a pass
				219	so that later optimizations know how the data structures in the program are
				220	layed out. The "<tt>TheExecutionEngine</tt>" variable is related to the JIT,
				221	which we will get to in the next section.</p>
				222
				223	<p>In this case, we choose to add 4 optimization passes. The passes we chose
				224	here are a pretty standard set of "cleanup" optimizations that are useful for
				225	a wide variety of code. I won't delve into what they do, but believe that they
				226	are a good starting place.</p>
				227
				228	<p>Once the passmanager, is set up, we need to make use of it. We do this by
				229	running it after our newly created function is constructed (in
				230	<tt>FunctionAST::Codegen</tt>), but before it is returned to the client:</p>
				231
				232	<div class="doc_code">
				233	<pre>
				234	if (Value *RetVal = Body->Codegen()) {
				235	// Finish off the function.
				236	Builder.CreateRet(RetVal);
				237
				238	// Validate the generated code, checking for consistency.
				239	verifyFunction(*TheFunction);
				240
				241	// Optimize the function.
				242	TheFPM->run(*TheFunction);
				243
				244	return TheFunction;
				245	}
				246	</pre>
				247	</div>
				248
				249	<p>As you can see, this is pretty straight-forward. The
				250	<tt>FunctionPassManager</tt> optimizes and updates the LLVM Function* in place,
				251	improving (hopefully) its body. With this in place, we can try our test above
				252	again:</p>
				253
				254	<div class="doc_code">
				255	<pre>
				256	ready> <b>def test(x) (1+2+x)*(x+(1+2));</b>
				257	ready> Read function definition:
				258	define double @test(double %x) {
				259	entry:
				260	%addtmp = add double %x, 3.000000e+00
				261	%multmp = mul double %addtmp, %addtmp
				262	ret double %multmp
				263	}
				264	</pre>
				265	</div>
				266
				267	<p>As expected, we now get our nicely optimized code, saving a floating point
				268	add from the program.</p>
				269
				270	<p>LLVM provides a wide variety of optimizations that can be used in certain
Chris Lattner	7271423	2007-10-25 17:52:39 +0000	[diff] [blame]	271	circumstances. Some <a href="../Passes.html">documentation about the various
				272	passes</a> is available, but it isn't very complete. Another good source of
				273	ideas is to look at the passes that <tt>llvm-gcc</tt> or
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	274	<tt>llvm-ld</tt> run to get started. The "<tt>opt</tt>" tool allows you to
				275	experiment with passes from the command line, so you can see if they do
				276	anything.</p>
				277
				278	<p>Now that we have reasonable code coming out of our front-end, lets talk about
				279	executing it!</p>
				280
				281	</div>
				282
				283	<!-- *********************************************************************** -->
				284	<div class="doc_section"><a name="jit">Adding a JIT Compiler</a></div>
				285	<!-- *********************************************************************** -->
				286
				287	<div class="doc_text">
				288
				289	<p>Once the code is available in LLVM IR form a wide variety of tools can be
				290	applied to it. For example, you can run optimizations on it (as we did above),
				291	you can dump it out in textual or binary forms, you can compile the code to an
				292	assembly file (.s) for some target, or you can JIT compile it. The nice thing
				293	about the LLVM IR representation is that it is the common currency between many
				294	different parts of the compiler.
				295	</p>
				296
				297	<p>In this chapter, we'll add JIT compiler support to our interpreter. The
				298	basic idea that we want for Kaleidoscope is to have the user enter function
				299	bodies as they do now, but immediately evaluate the top-level expressions they
				300	type in. For example, if they type in "1 + 2;", we should evaluate and print
				301	out 3. If they define a function, they should be able to call it from the
				302	command line.</p>
				303
				304	<p>In order to do this, we first declare and initialize the JIT. This is done
				305	by adding a global variable and a call in <tt>main</tt>:</p>
				306
				307	<div class="doc_code">
				308	<pre>
				309	static ExecutionEngine *TheExecutionEngine;
				310	...
				311	int main() {
				312	..
				313	// Create the JIT.
				314	TheExecutionEngine = ExecutionEngine::create(TheModule);
				315	..
				316	}
				317	</pre>
				318	</div>
				319
				320	<p>This creates an abstract "Execution Engine" which can be either a JIT
				321	compiler or the LLVM interpreter. LLVM will automatically pick a JIT compiler
				322	for you if one is available for your platform, otherwise it will fall back to
				323	the interpreter.</p>
				324
				325	<p>Once the <tt>ExecutionEngine</tt> is created, the JIT is ready to be used.
				326	There are a variety of APIs that are useful, but the most simple one is the
				327	"<tt>getPointerToFunction(F)</tt>" method. This method JIT compiles the
				328	specified LLVM Function and returns a function pointer to the generated machine
				329	code. In our case, this means that we can change the code that parses a
				330	top-level expression to look like this:</p>
				331
				332	<div class="doc_code">
				333	<pre>
				334	static void HandleTopLevelExpression() {
				335	// Evaluate a top level expression into an anonymous function.
				336	if (FunctionAST *F = ParseTopLevelExpr()) {
				337	if (Function *LF = F->Codegen()) {
				338	LF->dump(); // Dump the function for exposition purposes.
				339
				340	// JIT the function, returning a function pointer.
				341	void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
				342
				343	// Cast it to the right type (takes no arguments, returns a double) so we
				344	// can call it as a native function.
				345	double (FP)() = (double ()())FPtr;
				346	fprintf(stderr, "Evaluated to %f\n", FP());
				347	}
				348	</pre>
				349	</div>
				350
				351	<p>Recall that we compile top-level expressions into a self-contained LLVM
				352	function that takes no arguments and returns the computed double. Because the
				353	LLVM JIT compiler matches the native platform ABI, this means that you can just
				354	cast the result pointer to a function pointer of that type and call it directly.
				355	As such, there is no difference between JIT compiled code and native machine
				356	code that is statically linked into your application.</p>
				357
				358	<p>With just these two changes, lets see how Kaleidoscope works now!</p>
				359
				360	<div class="doc_code">
				361	<pre>
				362	ready> <b>4+5;</b>
				363	define double @""() {
				364	entry:
				365	ret double 9.000000e+00
				366	}
				367
				368	<em>Evaluated to 9.000000</em>
				369	</pre>
				370	</div>
				371
				372	<p>Well this looks like it is basically working. The dump of the function
				373	shows the "no argument function that always returns double" that we synthesize
				374	for each top level expression that is typed it. This demonstrates very basic
				375	functionality, but can we do more?</p>
				376
				377	<div class="doc_code">
				378	<pre>
Chris Lattner	2e89f3a	2007-10-31 07:30:39 +0000	[diff] [blame]	379	ready> <b>def testfunc(x y) x + y*2; </b>
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	380	Read function definition:
				381	define double @testfunc(double %x, double %y) {
				382	entry:
				383	%multmp = mul double %y, 2.000000e+00
				384	%addtmp = add double %multmp, %x
				385	ret double %addtmp
				386	}
				387
				388	ready> <b>testfunc(4, 10);</b>
				389	define double @""() {
				390	entry:
				391	%calltmp = call double @testfunc( double 4.000000e+00, double 1.000000e+01 )
				392	ret double %calltmp
				393	}
				394
				395	<em>Evaluated to 24.000000</em>
				396	</pre>
				397	</div>
				398
				399	<p>This illustrates that we can now call user code, but it is a bit subtle what
				400	is going on here. Note that we only invoke the JIT on the anonymous functions
				401	that <em>calls testfunc</em>, but we never invoked it on <em>testfunc
				402	itself</em>.</p>
				403
				404	<p>What actually happened here is that the anonymous function is
				405	JIT'd when requested. When the Kaleidoscope app calls through the function
				406	pointer that is returned, the anonymous function starts executing. It ends up
				407	making the call for the "testfunc" function, and ends up in a stub that invokes
				408	the JIT, lazily, on testfunc. Once the JIT finishes lazily compiling testfunc,
				409	it returns and the code reexecutes the call.</p>
				410
				411	<p>In summary, the JIT will lazily JIT code on the fly as it is needed. The
				412	JIT provides a number of other more advanced interfaces for things like freeing
				413	allocated machine code, rejit'ing functions to update them, etc. However, even
				414	with this simple code, we get some surprisingly powerful capabilities - check
				415	this out (I removed the dump of the anonymous functions, you should get the idea
				416	by now :) :</p>
				417
				418	<div class="doc_code">
				419	<pre>
				420	ready> <b>extern sin(x);</b>
				421	Read extern:
				422	declare double @sin(double)
				423
				424	ready> <b>extern cos(x);</b>
				425	Read extern:
				426	declare double @cos(double)
				427
				428	ready> <b>sin(1.0);</b>
				429	<em>Evaluated to 0.841471</em>
Chris Lattner	7271423	2007-10-25 17:52:39 +0000	[diff] [blame]	430
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	431	ready> <b>def foo(x) sin(x)sin(x) + cos(x)cos(x);</b>
				432	Read function definition:
				433	define double @foo(double %x) {
				434	entry:
				435	%calltmp = call double @sin( double %x )
				436	%multmp = mul double %calltmp, %calltmp
				437	%calltmp2 = call double @cos( double %x )
				438	%multmp4 = mul double %calltmp2, %calltmp2
				439	%addtmp = add double %multmp, %multmp4
				440	ret double %addtmp
				441	}
				442
				443	ready> <b>foo(4.0);</b>
				444	<em>Evaluated to 1.000000</em>
				445	</pre>
				446	</div>
				447
				448	<p>Whoa, how does the JIT know about sin and cos? The answer is simple: in this
				449	example, the JIT started execution of a function and got to a function call. It
				450	realized that the function was not yet JIT compiled and invoked the standard set
				451	of routines to resolve the function. In this case, there is no body defined
				452	for the function, so the JIT ended up calling "<tt>dlsym("sin")</tt>" on itself.
				453	Since "<tt>sin</tt>" is defined within the JIT's address space, it simply
				454	patches up calls in the module to call the libm version of <tt>sin</tt>
				455	directly.</p>
				456
				457	<p>The LLVM JIT provides a number of interfaces (look in the
				458	<tt>ExecutionEngine.h</tt> file) for controlling how unknown functions get
				459	resolved. It allows you to establish explicit mappings between IR objects and
				460	addresses (useful for LLVM global variables that you want to map to static
				461	tables, for example), allows you to dynamically decide on the fly based on the
				462	function name, and even allows you to have the JIT abort itself if any lazy
				463	compilation is attempted.</p>
				464
Chris Lattner	7271423	2007-10-25 17:52:39 +0000	[diff] [blame]	465	<p>One interesting application of this is that we can now extend the language
				466	by writing arbitrary C++ code to implement operations. For example, if we add:
				467	</p>
				468
				469	<div class="doc_code">
				470	<pre>
				471	/// putchard - putchar that takes a double and returns 0.
				472	extern "C"
				473	double putchard(double X) {
				474	putchar((char)X);
				475	return 0;
				476	}
				477	</pre>
				478	</div>
				479
				480	<p>Now we can produce simple output to the console by using things like:
				481	"<tt>extern putchard(x); putchard(120);</tt>", which prints a lowercase 'x' on
				482	the console (120 is the ascii code for 'x'). Similar code could be used to
				483	implement file I/O, console input, and many other capabilities in
				484	Kaleidoscope.</p>
				485
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	486	<p>This completes the JIT and optimizer chapter of the Kaleidoscope tutorial. At
				487	this point, we can compile a non-Turing-complete programming language, optimize
				488	and JIT compile it in a user-driven way. Next up we'll look into <a
				489	href="LangImpl5.html">extending the language with control flow constructs</a>,
				490	tackling some interesting LLVM IR issues along the way.</p>
				491
				492	</div>
				493
				494	<!-- *********************************************************************** -->
				495	<div class="doc_section"><a name="code">Full Code Listing</a></div>
				496	<!-- *********************************************************************** -->
				497
				498	<div class="doc_text">
				499
				500	<p>
				501	Here is the complete code listing for our running example, enhanced with the
				502	LLVM JIT and optimizer. To build this example, use:
				503	</p>
				504
				505	<div class="doc_code">
				506	<pre>
				507	# Compile
				508	g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
				509	# Run
				510	./toy
				511	</pre>
				512	</div>
				513
				514	<p>Here is the code:</p>
				515
				516	<div class="doc_code">
				517	<pre>
				518	#include "llvm/DerivedTypes.h"
				519	#include "llvm/ExecutionEngine/ExecutionEngine.h"
				520	#include "llvm/Module.h"
				521	#include "llvm/ModuleProvider.h"
				522	#include "llvm/PassManager.h"
				523	#include "llvm/Analysis/Verifier.h"
				524	#include "llvm/Target/TargetData.h"
				525	#include "llvm/Transforms/Scalar.h"
				526	#include "llvm/Support/LLVMBuilder.h"
				527	#include <cstdio>
				528	#include <string>
				529	#include <map>
				530	#include <vector>
				531	using namespace llvm;
				532
				533	//===----------------------------------------------------------------------===//
				534	// Lexer
				535	//===----------------------------------------------------------------------===//
				536
				537	// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
				538	// of these for known things.
				539	enum Token {
				540	tok_eof = -1,
				541
				542	// commands
				543	tok_def = -2, tok_extern = -3,
				544
				545	// primary
				546	tok_identifier = -4, tok_number = -5,
				547	};
				548
				549	static std::string IdentifierStr; // Filled in if tok_identifier
				550	static double NumVal; // Filled in if tok_number
				551
				552	/// gettok - Return the next token from standard input.
				553	static int gettok() {
				554	static int LastChar = ' ';
				555
				556	// Skip any whitespace.
				557	while (isspace(LastChar))
				558	LastChar = getchar();
				559
				560	if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
				561	IdentifierStr = LastChar;
				562	while (isalnum((LastChar = getchar())))
				563	IdentifierStr += LastChar;
				564
				565	if (IdentifierStr == "def") return tok_def;
				566	if (IdentifierStr == "extern") return tok_extern;
				567	return tok_identifier;
				568	}
				569
				570	if (isdigit(LastChar) \|\| LastChar == '.') { // Number: [0-9.]+
				571	std::string NumStr;
				572	do {
				573	NumStr += LastChar;
				574	LastChar = getchar();
				575	} while (isdigit(LastChar) \|\| LastChar == '.');
				576
				577	NumVal = strtod(NumStr.c_str(), 0);
				578	return tok_number;
				579	}
				580
				581	if (LastChar == '#') {
				582	// Comment until end of line.
				583	do LastChar = getchar();
				584	while (LastChar != EOF && LastChar != '\n' & LastChar != '\r');
				585
				586	if (LastChar != EOF)
				587	return gettok();
				588	}
				589
				590	// Check for end of file. Don't eat the EOF.
				591	if (LastChar == EOF)
				592	return tok_eof;
				593
				594	// Otherwise, just return the character as its ascii value.
				595	int ThisChar = LastChar;
				596	LastChar = getchar();
				597	return ThisChar;
				598	}
				599
				600	//===----------------------------------------------------------------------===//
				601	// Abstract Syntax Tree (aka Parse Tree)
				602	//===----------------------------------------------------------------------===//
				603
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	604	/// ExprAST - Base class for all expression nodes.
				605	class ExprAST {
				606	public:
				607	virtual ~ExprAST() {}
				608	virtual Value *Codegen() = 0;
				609	};
				610
				611	/// NumberExprAST - Expression class for numeric literals like "1.0".
				612	class NumberExprAST : public ExprAST {
				613	double Val;
				614	public:
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	615	NumberExprAST(double val) : Val(val) {}
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	616	virtual Value *Codegen();
				617	};
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	618
				619	/// VariableExprAST - Expression class for referencing a variable, like "a".
				620	class VariableExprAST : public ExprAST {
				621	std::string Name;
				622	public:
				623	VariableExprAST(const std::string &name) : Name(name) {}
				624	virtual Value *Codegen();
				625	};
				626
				627	/// BinaryExprAST - Expression class for a binary operator.
				628	class BinaryExprAST : public ExprAST {
				629	char Op;
				630	ExprAST LHS, RHS;
				631	public:
				632	BinaryExprAST(char op, ExprAST lhs, ExprAST rhs)
				633	: Op(op), LHS(lhs), RHS(rhs) {}
				634	virtual Value *Codegen();
				635	};
				636
				637	/// CallExprAST - Expression class for function calls.
				638	class CallExprAST : public ExprAST {
				639	std::string Callee;
				640	std::vector<ExprAST*> Args;
				641	public:
				642	CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
				643	: Callee(callee), Args(args) {}
				644	virtual Value *Codegen();
				645	};
				646
				647	/// PrototypeAST - This class represents the "prototype" for a function,
				648	/// which captures its argument names as well as if it is an operator.
				649	class PrototypeAST {
				650	std::string Name;
				651	std::vector<std::string> Args;
				652	public:
				653	PrototypeAST(const std::string &name, const std::vector<std::string> &args)
				654	: Name(name), Args(args) {}
				655
				656	Function *Codegen();
				657	};
				658
				659	/// FunctionAST - This class represents a function definition itself.
				660	class FunctionAST {
				661	PrototypeAST *Proto;
				662	ExprAST *Body;
				663	public:
				664	FunctionAST(PrototypeAST proto, ExprAST body)
				665	: Proto(proto), Body(body) {}
				666
				667	Function *Codegen();
				668	};
				669
				670	//===----------------------------------------------------------------------===//
				671	// Parser
				672	//===----------------------------------------------------------------------===//
				673
				674	/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
				675	/// token the parser it looking at. getNextToken reads another token from the
				676	/// lexer and updates CurTok with its results.
				677	static int CurTok;
				678	static int getNextToken() {
				679	return CurTok = gettok();
				680	}
				681
				682	/// BinopPrecedence - This holds the precedence for each binary operator that is
				683	/// defined.
				684	static std::map<char, int> BinopPrecedence;
				685
				686	/// GetTokPrecedence - Get the precedence of the pending binary operator token.
				687	static int GetTokPrecedence() {
				688	if (!isascii(CurTok))
				689	return -1;
				690
				691	// Make sure it's a declared binop.
				692	int TokPrec = BinopPrecedence[CurTok];
				693	if (TokPrec <= 0) return -1;
				694	return TokPrec;
				695	}
				696
				697	/// Error* - These are little helper functions for error handling.
				698	ExprAST Error(const char Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
				699	PrototypeAST ErrorP(const char Str) { Error(Str); return 0; }
				700	FunctionAST ErrorF(const char Str) { Error(Str); return 0; }
				701
				702	static ExprAST *ParseExpression();
				703
				704	/// identifierexpr
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	705	/// ::= identifier
				706	/// ::= identifier '(' expression* ')'
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	707	static ExprAST *ParseIdentifierExpr() {
				708	std::string IdName = IdentifierStr;
				709
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	710	getNextToken(); // eat identifier.
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	711
				712	if (CurTok != '(') // Simple variable ref.
				713	return new VariableExprAST(IdName);
				714
				715	// Call.
				716	getNextToken(); // eat (
				717	std::vector<ExprAST*> Args;
Chris Lattner	7115521	2007-11-06 01:39:12 +0000	[diff] [blame]	718	if (CurTok != ')') {
				719	while (1) {
				720	ExprAST *Arg = ParseExpression();
				721	if (!Arg) return 0;
				722	Args.push_back(Arg);
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	723
Chris Lattner	7115521	2007-11-06 01:39:12 +0000	[diff] [blame]	724	if (CurTok == ')') break;
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	725
Chris Lattner	7115521	2007-11-06 01:39:12 +0000	[diff] [blame]	726	if (CurTok != ',')
				727	return Error("Expected ')'");
				728	getNextToken();
				729	}
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	730	}
				731
				732	// Eat the ')'.
				733	getNextToken();
				734
				735	return new CallExprAST(IdName, Args);
				736	}
				737
				738	/// numberexpr ::= number
				739	static ExprAST *ParseNumberExpr() {
				740	ExprAST *Result = new NumberExprAST(NumVal);
				741	getNextToken(); // consume the number
				742	return Result;
				743	}
				744
				745	/// parenexpr ::= '(' expression ')'
				746	static ExprAST *ParseParenExpr() {
				747	getNextToken(); // eat (.
				748	ExprAST *V = ParseExpression();
				749	if (!V) return 0;
				750
				751	if (CurTok != ')')
				752	return Error("expected ')'");
				753	getNextToken(); // eat ).
				754	return V;
				755	}
				756
				757	/// primary
				758	/// ::= identifierexpr
				759	/// ::= numberexpr
				760	/// ::= parenexpr
				761	static ExprAST *ParsePrimary() {
				762	switch (CurTok) {
				763	default: return Error("unknown token when expecting an expression");
				764	case tok_identifier: return ParseIdentifierExpr();
				765	case tok_number: return ParseNumberExpr();
				766	case '(': return ParseParenExpr();
				767	}
				768	}
				769
				770	/// binoprhs
				771	/// ::= ('+' primary)*
				772	static ExprAST ParseBinOpRHS(int ExprPrec, ExprAST LHS) {
				773	// If this is a binop, find its precedence.
				774	while (1) {
				775	int TokPrec = GetTokPrecedence();
				776
				777	// If this is a binop that binds at least as tightly as the current binop,
				778	// consume it, otherwise we are done.
				779	if (TokPrec < ExprPrec)
				780	return LHS;
				781
				782	// Okay, we know this is a binop.
				783	int BinOp = CurTok;
				784	getNextToken(); // eat binop
				785
				786	// Parse the primary expression after the binary operator.
				787	ExprAST *RHS = ParsePrimary();
				788	if (!RHS) return 0;
				789
				790	// If BinOp binds less tightly with RHS than the operator after RHS, let
				791	// the pending operator take RHS as its LHS.
				792	int NextPrec = GetTokPrecedence();
				793	if (TokPrec < NextPrec) {
				794	RHS = ParseBinOpRHS(TokPrec+1, RHS);
				795	if (RHS == 0) return 0;
				796	}
				797
				798	// Merge LHS/RHS.
				799	LHS = new BinaryExprAST(BinOp, LHS, RHS);
				800	}
				801	}
				802
				803	/// expression
				804	/// ::= primary binoprhs
				805	///
				806	static ExprAST *ParseExpression() {
				807	ExprAST *LHS = ParsePrimary();
				808	if (!LHS) return 0;
				809
				810	return ParseBinOpRHS(0, LHS);
				811	}
				812
				813	/// prototype
				814	/// ::= id '(' id* ')'
				815	static PrototypeAST *ParsePrototype() {
				816	if (CurTok != tok_identifier)
				817	return ErrorP("Expected function name in prototype");
				818
				819	std::string FnName = IdentifierStr;
				820	getNextToken();
				821
				822	if (CurTok != '(')
				823	return ErrorP("Expected '(' in prototype");
				824
				825	std::vector<std::string> ArgNames;
				826	while (getNextToken() == tok_identifier)
				827	ArgNames.push_back(IdentifierStr);
				828	if (CurTok != ')')
				829	return ErrorP("Expected ')' in prototype");
				830
				831	// success.
				832	getNextToken(); // eat ')'.
				833
				834	return new PrototypeAST(FnName, ArgNames);
				835	}
				836
				837	/// definition ::= 'def' prototype expression
				838	static FunctionAST *ParseDefinition() {
				839	getNextToken(); // eat def.
				840	PrototypeAST *Proto = ParsePrototype();
				841	if (Proto == 0) return 0;
				842
				843	if (ExprAST *E = ParseExpression())
				844	return new FunctionAST(Proto, E);
				845	return 0;
				846	}
				847
				848	/// toplevelexpr ::= expression
				849	static FunctionAST *ParseTopLevelExpr() {
				850	if (ExprAST *E = ParseExpression()) {
				851	// Make an anonymous proto.
				852	PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
				853	return new FunctionAST(Proto, E);
				854	}
				855	return 0;
				856	}
				857
				858	/// external ::= 'extern' prototype
				859	static PrototypeAST *ParseExtern() {
				860	getNextToken(); // eat extern.
				861	return ParsePrototype();
				862	}
				863
				864	//===----------------------------------------------------------------------===//
				865	// Code Generation
				866	//===----------------------------------------------------------------------===//
				867
				868	static Module *TheModule;
				869	static LLVMFoldingBuilder Builder;
				870	static std::map<std::string, Value*> NamedValues;
				871	static FunctionPassManager *TheFPM;
				872
				873	Value ErrorV(const char Str) { Error(Str); return 0; }
				874
				875	Value *NumberExprAST::Codegen() {
				876	return ConstantFP::get(Type::DoubleTy, APFloat(Val));
				877	}
				878
				879	Value *VariableExprAST::Codegen() {
				880	// Look this variable up in the function.
				881	Value *V = NamedValues[Name];
				882	return V ? V : ErrorV("Unknown variable name");
				883	}
				884
				885	Value *BinaryExprAST::Codegen() {
				886	Value *L = LHS->Codegen();
				887	Value *R = RHS->Codegen();
				888	if (L == 0 \|\| R == 0) return 0;
				889
				890	switch (Op) {
				891	case '+': return Builder.CreateAdd(L, R, "addtmp");
				892	case '-': return Builder.CreateSub(L, R, "subtmp");
				893	case '*': return Builder.CreateMul(L, R, "multmp");
				894	case '<':
Chris Lattner	7115521	2007-11-06 01:39:12 +0000	[diff] [blame]	895	L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner	118749e	2007-10-25 06:23:36 +0000	[diff] [blame]	896	// Convert bool 0/1 to double 0.0 or 1.0
				897	return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
				898	default: return ErrorV("invalid binary operator");
				899	}
				900	}
				901
				902	Value *CallExprAST::Codegen() {
				903	// Look up the name in the global module table.
				904	Function *CalleeF = TheModule->getFunction(Callee);
				905	if (CalleeF == 0)
				906	return ErrorV("Unknown function referenced");
				907
				908	// If argument mismatch error.
				909	if (CalleeF->arg_size() != Args.size())
				910	return ErrorV("Incorrect # arguments passed");
				911
				912	std::vector<Value*> ArgsV;
				913	for (unsigned i = 0, e = Args.size(); i != e; ++i) {
				914	ArgsV.push_back(Args[i]->Codegen());
				915	if (ArgsV.back() == 0) return 0;
				916	}
				917
				918	return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
				919	}
				920
				921	Function *PrototypeAST::Codegen() {
				922	// Make the function type: double(double,double) etc.
				923	std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
				924	FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
				925
				926	Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
				927
				928	// If F conflicted, there was already something named 'Name'. If it has a
				929	// body, don't allow redefinition or reextern.
				930	if (F->getName() != Name) {
				931	// Delete the one we just made and get the existing one.
				932	F->eraseFromParent();
				933	F = TheModule->getFunction(Name);
				934
				935	// If F already has a body, reject this.
				936	if (!F->empty()) {
				937	ErrorF("redefinition of function");
				938	return 0;
				939	}
				940
				941	// If F took a different number of args, reject.
				942	if (F->arg_size() != Args.size()) {
				943	ErrorF("redefinition of function with different # args");
				944	return 0;
				945	}
				946	}
				947
				948	// Set names for all arguments.
				949	unsigned Idx = 0;
				950	for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
				951	++AI, ++Idx) {
				952	AI->setName(Args[Idx]);
				953
				954	// Add arguments to variable symbol table.
				955	NamedValues[Args[Idx]] = AI;
				956	}
				957
				958	return F;
				959	}
				960
				961	Function *FunctionAST::Codegen() {
				962	NamedValues.clear();
				963
				964	Function *TheFunction = Proto->Codegen();
				965	if (TheFunction == 0)
				966	return 0;
				967
				968	// Create a new basic block to start insertion into.
				969	BasicBlock *BB = new BasicBlock("entry", TheFunction);
				970	Builder.SetInsertPoint(BB);
				971
				972	if (Value *RetVal = Body->Codegen()) {
				973	// Finish off the function.
				974	Builder.CreateRet(RetVal);
				975
				976	// Validate the generated code, checking for consistency.
				977	verifyFunction(*TheFunction);
				978
				979	// Optimize the function.
				980	TheFPM->run(*TheFunction);
				981
				982	return TheFunction;
				983	}
				984
				985	// Error reading body, remove function.
				986	TheFunction->eraseFromParent();
				987	return 0;
				988	}
				989
				990	//===----------------------------------------------------------------------===//
				991	// Top-Level parsing and JIT Driver
				992	//===----------------------------------------------------------------------===//
				993
				994	static ExecutionEngine *TheExecutionEngine;
				995
				996	static void HandleDefinition() {
				997	if (FunctionAST *F = ParseDefinition()) {
				998	if (Function *LF = F->Codegen()) {
				999	fprintf(stderr, "Read function definition:");
				1000	LF->dump();
				1001	}
				1002	} else {
				1003	// Skip token for error recovery.
				1004	getNextToken();
				1005	}
				1006	}
				1007
				1008	static void HandleExtern() {
				1009	if (PrototypeAST *P = ParseExtern()) {
				1010	if (Function *F = P->Codegen()) {
				1011	fprintf(stderr, "Read extern: ");
				1012	F->dump();
				1013	}
				1014	} else {
				1015	// Skip token for error recovery.
				1016	getNextToken();
				1017	}
				1018	}
				1019
				1020	static void HandleTopLevelExpression() {
				1021	// Evaluate a top level expression into an anonymous function.
				1022	if (FunctionAST *F = ParseTopLevelExpr()) {
				1023	if (Function *LF = F->Codegen()) {
				1024	// JIT the function, returning a function pointer.
				1025	void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
				1026
				1027	// Cast it to the right type (takes no arguments, returns a double) so we
				1028	// can call it as a native function.
				1029	double (FP)() = (double ()())FPtr;
				1030	fprintf(stderr, "Evaluated to %f\n", FP());
				1031	}
				1032	} else {
				1033	// Skip token for error recovery.
				1034	getNextToken();
				1035	}
				1036	}
				1037
				1038	/// top ::= definition \| external \| expression \| ';'
				1039	static void MainLoop() {
				1040	while (1) {
				1041	fprintf(stderr, "ready> ");
				1042	switch (CurTok) {
				1043	case tok_eof: return;
				1044	case ';': getNextToken(); break; // ignore top level semicolons.
				1045	case tok_def: HandleDefinition(); break;
				1046	case tok_extern: HandleExtern(); break;
				1047	default: HandleTopLevelExpression(); break;
				1048	}
				1049	}
				1050	}
				1051
				1052
				1053
				1054	//===----------------------------------------------------------------------===//
				1055	// "Library" functions that can be "extern'd" from user code.
				1056	//===----------------------------------------------------------------------===//
				1057
				1058	/// putchard - putchar that takes a double and returns 0.
				1059	extern "C"
				1060	double putchard(double X) {
				1061	putchar((char)X);
				1062	return 0;
				1063	}
				1064
				1065	//===----------------------------------------------------------------------===//
				1066	// Main driver code.
				1067	//===----------------------------------------------------------------------===//
				1068
				1069	int main() {
				1070	// Install standard binary operators.
				1071	// 1 is lowest precedence.
				1072	BinopPrecedence['<'] = 10;
				1073	BinopPrecedence['+'] = 20;
				1074	BinopPrecedence['-'] = 20;
				1075	BinopPrecedence['*'] = 40; // highest.
				1076
				1077	// Prime the first token.
				1078	fprintf(stderr, "ready> ");
				1079	getNextToken();
				1080
				1081	// Make the module, which holds all the code.
				1082	TheModule = new Module("my cool jit");
				1083
				1084	// Create the JIT.
				1085	TheExecutionEngine = ExecutionEngine::create(TheModule);
				1086
				1087	{
				1088	ExistingModuleProvider OurModuleProvider(TheModule);
				1089	FunctionPassManager OurFPM(&OurModuleProvider);
				1090
				1091	// Set up the optimizer pipeline. Start with registering info about how the
				1092	// target lays out data structures.
				1093	OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
				1094	// Do simple "peephole" optimizations and bit-twiddling optzns.
				1095	OurFPM.add(createInstructionCombiningPass());
				1096	// Reassociate expressions.
				1097	OurFPM.add(createReassociatePass());
				1098	// Eliminate Common SubExpressions.
				1099	OurFPM.add(createGVNPass());
				1100	// Simplify the control flow graph (deleting unreachable blocks, etc).
				1101	OurFPM.add(createCFGSimplificationPass());
				1102
				1103	// Set the global so the code gen can use this.
				1104	TheFPM = &OurFPM;
				1105
				1106	// Run the main "interpreter loop" now.
				1107	MainLoop();
				1108
				1109	TheFPM = 0;
				1110	} // Free module provider and pass manager.
				1111
				1112
				1113	// Print out all of the generated code.
				1114	TheModule->dump();
				1115	return 0;
				1116	}
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	1117	</pre>
				1118	</div>
				1119
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	1120	</div>
				1121
				1122	<!-- *********************************************************************** -->
				1123	<hr>
				1124	<address>
				1125	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				1126	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				1127	<a href="http://validator.w3.org/check/referer"><img
Chris Lattner	8eef4b2	2007-10-23 06:30:50 +0000	[diff] [blame]	1128	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	1129
				1130	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1131	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				1132	Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
				1133	</address>
				1134	</body>
				1135	</html>