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

blob: 7b02faa6141d43ef31061fcbda1042d6dceb9ed8 [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;
				718	while (1) {
				719	ExprAST *Arg = ParseExpression();
				720	if (!Arg) return 0;
				721	Args.push_back(Arg);
				722
				723	if (CurTok == ')') break;
				724
				725	if (CurTok != ',')
				726	return Error("Expected ')'");
				727	getNextToken();
				728	}
				729
				730	// Eat the ')'.
				731	getNextToken();
				732
				733	return new CallExprAST(IdName, Args);
				734	}
				735
				736	/// numberexpr ::= number
				737	static ExprAST *ParseNumberExpr() {
				738	ExprAST *Result = new NumberExprAST(NumVal);
				739	getNextToken(); // consume the number
				740	return Result;
				741	}
				742
				743	/// parenexpr ::= '(' expression ')'
				744	static ExprAST *ParseParenExpr() {
				745	getNextToken(); // eat (.
				746	ExprAST *V = ParseExpression();
				747	if (!V) return 0;
				748
				749	if (CurTok != ')')
				750	return Error("expected ')'");
				751	getNextToken(); // eat ).
				752	return V;
				753	}
				754
				755	/// primary
				756	/// ::= identifierexpr
				757	/// ::= numberexpr
				758	/// ::= parenexpr
				759	static ExprAST *ParsePrimary() {
				760	switch (CurTok) {
				761	default: return Error("unknown token when expecting an expression");
				762	case tok_identifier: return ParseIdentifierExpr();
				763	case tok_number: return ParseNumberExpr();
				764	case '(': return ParseParenExpr();
				765	}
				766	}
				767
				768	/// binoprhs
				769	/// ::= ('+' primary)*
				770	static ExprAST ParseBinOpRHS(int ExprPrec, ExprAST LHS) {
				771	// If this is a binop, find its precedence.
				772	while (1) {
				773	int TokPrec = GetTokPrecedence();
				774
				775	// If this is a binop that binds at least as tightly as the current binop,
				776	// consume it, otherwise we are done.
				777	if (TokPrec < ExprPrec)
				778	return LHS;
				779
				780	// Okay, we know this is a binop.
				781	int BinOp = CurTok;
				782	getNextToken(); // eat binop
				783
				784	// Parse the primary expression after the binary operator.
				785	ExprAST *RHS = ParsePrimary();
				786	if (!RHS) return 0;
				787
				788	// If BinOp binds less tightly with RHS than the operator after RHS, let
				789	// the pending operator take RHS as its LHS.
				790	int NextPrec = GetTokPrecedence();
				791	if (TokPrec < NextPrec) {
				792	RHS = ParseBinOpRHS(TokPrec+1, RHS);
				793	if (RHS == 0) return 0;
				794	}
				795
				796	// Merge LHS/RHS.
				797	LHS = new BinaryExprAST(BinOp, LHS, RHS);
				798	}
				799	}
				800
				801	/// expression
				802	/// ::= primary binoprhs
				803	///
				804	static ExprAST *ParseExpression() {
				805	ExprAST *LHS = ParsePrimary();
				806	if (!LHS) return 0;
				807
				808	return ParseBinOpRHS(0, LHS);
				809	}
				810
				811	/// prototype
				812	/// ::= id '(' id* ')'
				813	static PrototypeAST *ParsePrototype() {
				814	if (CurTok != tok_identifier)
				815	return ErrorP("Expected function name in prototype");
				816
				817	std::string FnName = IdentifierStr;
				818	getNextToken();
				819
				820	if (CurTok != '(')
				821	return ErrorP("Expected '(' in prototype");
				822
				823	std::vector<std::string> ArgNames;
				824	while (getNextToken() == tok_identifier)
				825	ArgNames.push_back(IdentifierStr);
				826	if (CurTok != ')')
				827	return ErrorP("Expected ')' in prototype");
				828
				829	// success.
				830	getNextToken(); // eat ')'.
				831
				832	return new PrototypeAST(FnName, ArgNames);
				833	}
				834
				835	/// definition ::= 'def' prototype expression
				836	static FunctionAST *ParseDefinition() {
				837	getNextToken(); // eat def.
				838	PrototypeAST *Proto = ParsePrototype();
				839	if (Proto == 0) return 0;
				840
				841	if (ExprAST *E = ParseExpression())
				842	return new FunctionAST(Proto, E);
				843	return 0;
				844	}
				845
				846	/// toplevelexpr ::= expression
				847	static FunctionAST *ParseTopLevelExpr() {
				848	if (ExprAST *E = ParseExpression()) {
				849	// Make an anonymous proto.
				850	PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
				851	return new FunctionAST(Proto, E);
				852	}
				853	return 0;
				854	}
				855
				856	/// external ::= 'extern' prototype
				857	static PrototypeAST *ParseExtern() {
				858	getNextToken(); // eat extern.
				859	return ParsePrototype();
				860	}
				861
				862	//===----------------------------------------------------------------------===//
				863	// Code Generation
				864	//===----------------------------------------------------------------------===//
				865
				866	static Module *TheModule;
				867	static LLVMFoldingBuilder Builder;
				868	static std::map<std::string, Value*> NamedValues;
				869	static FunctionPassManager *TheFPM;
				870
				871	Value ErrorV(const char Str) { Error(Str); return 0; }
				872
				873	Value *NumberExprAST::Codegen() {
				874	return ConstantFP::get(Type::DoubleTy, APFloat(Val));
				875	}
				876
				877	Value *VariableExprAST::Codegen() {
				878	// Look this variable up in the function.
				879	Value *V = NamedValues[Name];
				880	return V ? V : ErrorV("Unknown variable name");
				881	}
				882
				883	Value *BinaryExprAST::Codegen() {
				884	Value *L = LHS->Codegen();
				885	Value *R = RHS->Codegen();
				886	if (L == 0 \|\| R == 0) return 0;
				887
				888	switch (Op) {
				889	case '+': return Builder.CreateAdd(L, R, "addtmp");
				890	case '-': return Builder.CreateSub(L, R, "subtmp");
				891	case '*': return Builder.CreateMul(L, R, "multmp");
				892	case '<':
				893	L = Builder.CreateFCmpULT(L, R, "multmp");
				894	// Convert bool 0/1 to double 0.0 or 1.0
				895	return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
				896	default: return ErrorV("invalid binary operator");
				897	}
				898	}
				899
				900	Value *CallExprAST::Codegen() {
				901	// Look up the name in the global module table.
				902	Function *CalleeF = TheModule->getFunction(Callee);
				903	if (CalleeF == 0)
				904	return ErrorV("Unknown function referenced");
				905
				906	// If argument mismatch error.
				907	if (CalleeF->arg_size() != Args.size())
				908	return ErrorV("Incorrect # arguments passed");
				909
				910	std::vector<Value*> ArgsV;
				911	for (unsigned i = 0, e = Args.size(); i != e; ++i) {
				912	ArgsV.push_back(Args[i]->Codegen());
				913	if (ArgsV.back() == 0) return 0;
				914	}
				915
				916	return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
				917	}
				918
				919	Function *PrototypeAST::Codegen() {
				920	// Make the function type: double(double,double) etc.
				921	std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
				922	FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
				923
				924	Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
				925
				926	// If F conflicted, there was already something named 'Name'. If it has a
				927	// body, don't allow redefinition or reextern.
				928	if (F->getName() != Name) {
				929	// Delete the one we just made and get the existing one.
				930	F->eraseFromParent();
				931	F = TheModule->getFunction(Name);
				932
				933	// If F already has a body, reject this.
				934	if (!F->empty()) {
				935	ErrorF("redefinition of function");
				936	return 0;
				937	}
				938
				939	// If F took a different number of args, reject.
				940	if (F->arg_size() != Args.size()) {
				941	ErrorF("redefinition of function with different # args");
				942	return 0;
				943	}
				944	}
				945
				946	// Set names for all arguments.
				947	unsigned Idx = 0;
				948	for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
				949	++AI, ++Idx) {
				950	AI->setName(Args[Idx]);
				951
				952	// Add arguments to variable symbol table.
				953	NamedValues[Args[Idx]] = AI;
				954	}
				955
				956	return F;
				957	}
				958
				959	Function *FunctionAST::Codegen() {
				960	NamedValues.clear();
				961
				962	Function *TheFunction = Proto->Codegen();
				963	if (TheFunction == 0)
				964	return 0;
				965
				966	// Create a new basic block to start insertion into.
				967	BasicBlock *BB = new BasicBlock("entry", TheFunction);
				968	Builder.SetInsertPoint(BB);
				969
				970	if (Value *RetVal = Body->Codegen()) {
				971	// Finish off the function.
				972	Builder.CreateRet(RetVal);
				973
				974	// Validate the generated code, checking for consistency.
				975	verifyFunction(*TheFunction);
				976
				977	// Optimize the function.
				978	TheFPM->run(*TheFunction);
				979
				980	return TheFunction;
				981	}
				982
				983	// Error reading body, remove function.
				984	TheFunction->eraseFromParent();
				985	return 0;
				986	}
				987
				988	//===----------------------------------------------------------------------===//
				989	// Top-Level parsing and JIT Driver
				990	//===----------------------------------------------------------------------===//
				991
				992	static ExecutionEngine *TheExecutionEngine;
				993
				994	static void HandleDefinition() {
				995	if (FunctionAST *F = ParseDefinition()) {
				996	if (Function *LF = F->Codegen()) {
				997	fprintf(stderr, "Read function definition:");
				998	LF->dump();
				999	}
				1000	} else {
				1001	// Skip token for error recovery.
				1002	getNextToken();
				1003	}
				1004	}
				1005
				1006	static void HandleExtern() {
				1007	if (PrototypeAST *P = ParseExtern()) {
				1008	if (Function *F = P->Codegen()) {
				1009	fprintf(stderr, "Read extern: ");
				1010	F->dump();
				1011	}
				1012	} else {
				1013	// Skip token for error recovery.
				1014	getNextToken();
				1015	}
				1016	}
				1017
				1018	static void HandleTopLevelExpression() {
				1019	// Evaluate a top level expression into an anonymous function.
				1020	if (FunctionAST *F = ParseTopLevelExpr()) {
				1021	if (Function *LF = F->Codegen()) {
				1022	// JIT the function, returning a function pointer.
				1023	void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
				1024
				1025	// Cast it to the right type (takes no arguments, returns a double) so we
				1026	// can call it as a native function.
				1027	double (FP)() = (double ()())FPtr;
				1028	fprintf(stderr, "Evaluated to %f\n", FP());
				1029	}
				1030	} else {
				1031	// Skip token for error recovery.
				1032	getNextToken();
				1033	}
				1034	}
				1035
				1036	/// top ::= definition \| external \| expression \| ';'
				1037	static void MainLoop() {
				1038	while (1) {
				1039	fprintf(stderr, "ready> ");
				1040	switch (CurTok) {
				1041	case tok_eof: return;
				1042	case ';': getNextToken(); break; // ignore top level semicolons.
				1043	case tok_def: HandleDefinition(); break;
				1044	case tok_extern: HandleExtern(); break;
				1045	default: HandleTopLevelExpression(); break;
				1046	}
				1047	}
				1048	}
				1049
				1050
				1051
				1052	//===----------------------------------------------------------------------===//
				1053	// "Library" functions that can be "extern'd" from user code.
				1054	//===----------------------------------------------------------------------===//
				1055
				1056	/// putchard - putchar that takes a double and returns 0.
				1057	extern "C"
				1058	double putchard(double X) {
				1059	putchar((char)X);
				1060	return 0;
				1061	}
				1062
				1063	//===----------------------------------------------------------------------===//
				1064	// Main driver code.
				1065	//===----------------------------------------------------------------------===//
				1066
				1067	int main() {
				1068	// Install standard binary operators.
				1069	// 1 is lowest precedence.
				1070	BinopPrecedence['<'] = 10;
				1071	BinopPrecedence['+'] = 20;
				1072	BinopPrecedence['-'] = 20;
				1073	BinopPrecedence['*'] = 40; // highest.
				1074
				1075	// Prime the first token.
				1076	fprintf(stderr, "ready> ");
				1077	getNextToken();
				1078
				1079	// Make the module, which holds all the code.
				1080	TheModule = new Module("my cool jit");
				1081
				1082	// Create the JIT.
				1083	TheExecutionEngine = ExecutionEngine::create(TheModule);
				1084
				1085	{
				1086	ExistingModuleProvider OurModuleProvider(TheModule);
				1087	FunctionPassManager OurFPM(&OurModuleProvider);
				1088
				1089	// Set up the optimizer pipeline. Start with registering info about how the
				1090	// target lays out data structures.
				1091	OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
				1092	// Do simple "peephole" optimizations and bit-twiddling optzns.
				1093	OurFPM.add(createInstructionCombiningPass());
				1094	// Reassociate expressions.
				1095	OurFPM.add(createReassociatePass());
				1096	// Eliminate Common SubExpressions.
				1097	OurFPM.add(createGVNPass());
				1098	// Simplify the control flow graph (deleting unreachable blocks, etc).
				1099	OurFPM.add(createCFGSimplificationPass());
				1100
				1101	// Set the global so the code gen can use this.
				1102	TheFPM = &OurFPM;
				1103
				1104	// Run the main "interpreter loop" now.
				1105	MainLoop();
				1106
				1107	TheFPM = 0;
				1108	} // Free module provider and pass manager.
				1109
				1110
				1111	// Print out all of the generated code.
				1112	TheModule->dump();
				1113	return 0;
				1114	}
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	1115	</pre>
				1116	</div>
				1117
Chris Lattner	c0b42e9	2007-10-23 06:27:55 +0000	[diff] [blame]	1118	</div>
				1119
				1120	<!-- *********************************************************************** -->
				1121	<hr>
				1122	<address>
				1123	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				1124	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				1125	<a href="http://validator.w3.org/check/referer"><img
Chris Lattner	8eef4b2	2007-10-23 06:30:50 +0000	[diff] [blame]	1126	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]	1127
				1128	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1129	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				1130	Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
				1131	</address>
				1132	</body>
				1133	</html>