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

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