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

blob: 38ed25d89f5bbce04a5628fa76d8795a893e2ca1 [file] [log] [blame]

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