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

blob: 9826844b004a7a86187d565592646063ee612231 [file] [log] [blame]

Chris Lattner	602c832c	2007-10-31 06:30:21 +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: Extending the Language: Control Flow</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: Extending the Language: Control Flow</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 5
				19	<ol>
				20	<li><a href="#intro">Chapter 5 Introduction</a></li>
				21	<li><a href="#ifthen">If/Then/Else</a>
				22	<ol>
				23	<li><a href="#iflexer">Lexer Extensions</a></li>
				24	<li><a href="#ifast">AST Extensions</a></li>
				25	<li><a href="#ifparser">Parser Extensions</a></li>
				26	<li><a href="#ifir">LLVM IR</a></li>
				27	<li><a href="#ifcodegen">Code Generation</a></li>
				28	</ol>
				29	</li>
				30	<li><a href="#for">'for' Loop Expression</a>
				31	<ol>
				32	<li><a href="#forlexer">Lexer Extensions</a></li>
				33	<li><a href="#forast">AST Extensions</a></li>
				34	<li><a href="#forparser">Parser Extensions</a></li>
				35	<li><a href="#forir">LLVM IR</a></li>
				36	<li><a href="#forcodegen">Code Generation</a></li>
				37	</ol>
				38	</li>
				39	<li><a href="#code">Full Code Listing</a></li>
				40	</ol>
				41	</li>
Chris Lattner	0e555b1	2007-11-05 20:04:56 +0000	[diff] [blame]	42	<li><a href="LangImpl6.html">Chapter 6</a>: Extending the Language:
				43	User-defined Operators</li>
Chris Lattner	128eb86	2007-11-05 19:06:59 +0000	[diff] [blame]	44	</ul>
				45
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	46	<div class="doc_author">
				47	<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
				48	</div>
				49
				50	<!-- *********************************************************************** -->
Chris Lattner	128eb86	2007-11-05 19:06:59 +0000	[diff] [blame]	51	<div class="doc_section"><a name="intro">Chapter 5 Introduction</a></div>
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	52	<!-- *********************************************************************** -->
				53
				54	<div class="doc_text">
				55
Chris Lattner	128eb86	2007-11-05 19:06:59 +0000	[diff] [blame]	56	<p>Welcome to Chapter 5 of the "<a href="index.html">Implementing a language
				57	with LLVM</a>" tutorial. Parts 1-4 described the implementation of the simple
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	58	Kaleidoscope language and included support for generating LLVM IR, followed by
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	59	optimizations and a JIT compiler. Unfortunately, as presented, Kaleidoscope is
				60	mostly useless: it has no control flow other than call and return. This means
				61	that you can't have conditional branches in the code, significantly limiting its
				62	power. In this episode of "build that compiler", we'll extend Kaleidoscope to
Chris Lattner	1092a96	2007-11-07 05:47:48 +0000	[diff] [blame]	63	have an if/then/else expression plus a simple 'for' loop.</p>
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	64
				65	</div>
				66
				67	<!-- *********************************************************************** -->
				68	<div class="doc_section"><a name="ifthen">If/Then/Else</a></div>
				69	<!-- *********************************************************************** -->
				70
				71	<div class="doc_text">
				72
				73	<p>
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	74	Extending Kaleidoscope to support if/then/else is quite straightforward. It
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	75	basically requires adding lexer support for this "new" concept to the lexer,
				76	parser, AST, and LLVM code emitter. This example is nice, because it shows how
				77	easy it is to "grow" a language over time, incrementally extending it as new
				78	ideas are discovered.</p>
				79
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	80	<p>Before we get going on "how" we add this extension, lets talk about "what" we
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	81	want. The basic idea is that we want to be able to write this sort of thing:
				82	</p>
				83
				84	<div class="doc_code">
				85	<pre>
				86	def fib(x)
				87	if x < 3 then
				88	1
				89	else
				90	fib(x-1)+fib(x-2);
				91	</pre>
				92	</div>
				93
				94	<p>In Kaleidoscope, every construct is an expression: there are no statements.
				95	As such, the if/then/else expression needs to return a value like any other.
				96	Since we're using a mostly functional form, we'll have it evaluate its
				97	conditional, then return the 'then' or 'else' value based on how the condition
				98	was resolved. This is very similar to the C "?:" expression.</p>
				99
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	100	<p>The semantics of the if/then/else expression is that it evaluates the
Chris Lattner	1092a96	2007-11-07 05:47:48 +0000	[diff] [blame]	101	condition to a boolean equality value: 0.0 is considered to be false and
				102	everything else is considered to be true.
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	103	If the condition is true, the first subexpression is evaluated and returned, if
				104	the condition is false, the second subexpression is evaluated and returned.
				105	Since Kaleidoscope allows side-effects, this behavior is important to nail down.
				106	</p>
				107
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	108	<p>Now that we know what we "want", lets break this down into its constituent
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	109	pieces.</p>
				110
				111	</div>
				112
				113	<!-- ======================================================================= -->
				114	<div class="doc_subsubsection"><a name="iflexer">Lexer Extensions for
				115	If/Then/Else</a></div>
				116	<!-- ======================================================================= -->
				117
				118
				119	<div class="doc_text">
				120
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	121	<p>The lexer extensions are straightforward. First we add new enum values
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	122	for the relevant tokens:</p>
				123
				124	<div class="doc_code">
				125	<pre>
				126	// control
				127	tok_if = -6, tok_then = -7, tok_else = -8,
				128	</pre>
				129	</div>
				130
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	131	<p>Once we have that, we recognize the new keywords in the lexer. This is pretty simple
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	132	stuff:</p>
				133
				134	<div class="doc_code">
				135	<pre>
				136	...
				137	if (IdentifierStr == "def") return tok_def;
				138	if (IdentifierStr == "extern") return tok_extern;
				139	<b>if (IdentifierStr == "if") return tok_if;
				140	if (IdentifierStr == "then") return tok_then;
				141	if (IdentifierStr == "else") return tok_else;</b>
				142	return tok_identifier;
				143	</pre>
				144	</div>
				145
				146	</div>
				147
				148	<!-- ======================================================================= -->
				149	<div class="doc_subsubsection"><a name="ifast">AST Extensions for
Chris Lattner	128eb86	2007-11-05 19:06:59 +0000	[diff] [blame]	150	If/Then/Else</a></div>
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	151	<!-- ======================================================================= -->
				152
				153	<div class="doc_text">
				154
				155	<p>To represent the new expression we add a new AST node for it:</p>
				156
				157	<div class="doc_code">
				158	<pre>
				159	/// IfExprAST - Expression class for if/then/else.
				160	class IfExprAST : public ExprAST {
				161	ExprAST Cond, Then, *Else;
				162	public:
				163	IfExprAST(ExprAST cond, ExprAST then, ExprAST *_else)
				164	: Cond(cond), Then(then), Else(_else) {}
				165	virtual Value *Codegen();
				166	};
				167	</pre>
				168	</div>
				169
				170	<p>The AST node just has pointers to the various subexpressions.</p>
				171
				172	</div>
				173
				174	<!-- ======================================================================= -->
				175	<div class="doc_subsubsection"><a name="ifparser">Parser Extensions for
Chris Lattner	128eb86	2007-11-05 19:06:59 +0000	[diff] [blame]	176	If/Then/Else</a></div>
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	177	<!-- ======================================================================= -->
				178
				179	<div class="doc_text">
				180
				181	<p>Now that we have the relevant tokens coming from the lexer and we have the
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	182	AST node to build, our parsing logic is relatively straightforward. First we
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	183	define a new parsing function:</p>
				184
				185	<div class="doc_code">
				186	<pre>
				187	/// ifexpr ::= 'if' expression 'then' expression 'else' expression
				188	static ExprAST *ParseIfExpr() {
				189	getNextToken(); // eat the if.
				190
				191	// condition.
				192	ExprAST *Cond = ParseExpression();
				193	if (!Cond) return 0;
				194
				195	if (CurTok != tok_then)
				196	return Error("expected then");
				197	getNextToken(); // eat the then
				198
				199	ExprAST *Then = ParseExpression();
				200	if (Then == 0) return 0;
				201
				202	if (CurTok != tok_else)
				203	return Error("expected else");
				204
				205	getNextToken();
				206
				207	ExprAST *Else = ParseExpression();
				208	if (!Else) return 0;
				209
				210	return new IfExprAST(Cond, Then, Else);
				211	}
				212	</pre>
				213	</div>
				214
				215	<p>Next we hook it up as a primary expression:</p>
				216
				217	<div class="doc_code">
				218	<pre>
				219	static ExprAST *ParsePrimary() {
				220	switch (CurTok) {
				221	default: return Error("unknown token when expecting an expression");
				222	case tok_identifier: return ParseIdentifierExpr();
				223	case tok_number: return ParseNumberExpr();
				224	case '(': return ParseParenExpr();
				225	<b>case tok_if: return ParseIfExpr();</b>
				226	}
				227	}
				228	</pre>
				229	</div>
				230
				231	</div>
				232
				233	<!-- ======================================================================= -->
				234	<div class="doc_subsubsection"><a name="ifir">LLVM IR for If/Then/Else</a></div>
				235	<!-- ======================================================================= -->
				236
				237	<div class="doc_text">
				238
				239	<p>Now that we have it parsing and building the AST, the final piece is adding
				240	LLVM code generation support. This is the most interesting part of the
				241	if/then/else example, because this is where it starts to introduce new concepts.
Chris Lattner	1092a96	2007-11-07 05:47:48 +0000	[diff] [blame]	242	All of the code above has been thoroughly described in previous chapters.
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	243	</p>
				244
				245	<p>To motivate the code we want to produce, lets take a look at a simple
				246	example. Consider:</p>
				247
				248	<div class="doc_code">
				249	<pre>
				250	extern foo();
				251	extern bar();
				252	def baz(x) if x then foo() else bar();
				253	</pre>
				254	</div>
				255
				256	<p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
				257	looks like this:</p>
				258
				259	<div class="doc_code">
				260	<pre>
				261	declare double @foo()
				262
				263	declare double @bar()
				264
				265	define double @baz(double %x) {
				266	entry:
				267	%ifcond = fcmp one double %x, 0.000000e+00
				268	br i1 %ifcond, label %then, label %else
				269
				270	then: ; preds = %entry
				271	%calltmp = call double @foo()
				272	br label %ifcont
				273
				274	else: ; preds = %entry
				275	%calltmp1 = call double @bar()
				276	br label %ifcont
				277
				278	ifcont: ; preds = %else, %then
				279	%iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
				280	ret double %iftmp
				281	}
				282	</pre>
				283	</div>
				284
				285	<p>To visualize the control flow graph, you can use a nifty feature of the LLVM
				286	'<a href="http://llvm.org/cmds/opt.html">opt</a>' tool. If you put this LLVM IR
				287	into "t.ll" and run "<tt>llvm-as < t.ll \| opt -analyze -view-cfg</tt>", <a
				288	href="../ProgrammersManual.html#ViewGraph">a window will pop up</a> and you'll
				289	see this graph:</p>
				290
				291	<center><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
				292	height="315"></center>
				293
				294	<p>Another way to get this is to call "<tt>F->viewCFG()</tt>" or
				295	"<tt>F->viewCFGOnly()</tt>" (where F is a "<tt>Function*</tt>") either by
				296	inserting actual calls into the code and recompiling or by calling these in the
				297	debugger. LLVM has many nice features for visualizing various graphs.</p>
				298
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	299	<p>Getting back to the generated code, it is fairly simple: the entry block
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	300	evaluates the conditional expression ("x" in our case here) and compares the
				301	result to 0.0 with the "<tt><a href="../LangRef.html#i_fcmp">fcmp</a> one</tt>"
Chris Lattner	1092a96	2007-11-07 05:47:48 +0000	[diff] [blame]	302	instruction ('one' is "Ordered and Not Equal"). Based on the result of this
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	303	expression, the code jumps to either the "then" or "else" blocks, which contain
Chris Lattner	1092a96	2007-11-07 05:47:48 +0000	[diff] [blame]	304	the expressions for the true/false cases.</p>
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	305
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	306	<p>Once the then/else blocks are finished executing, they both branch back to the
Chris Lattner	1092a96	2007-11-07 05:47:48 +0000	[diff] [blame]	307	'ifcont' block to execute the code that happens after the if/then/else. In this
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	308	case the only thing left to do is to return to the caller of the function. The
				309	question then becomes: how does the code know which expression to return?</p>
				310
				311	<p>The answer to this question involves an important SSA operation: the
				312	<a href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Phi
				313	operation</a>. If you're not familiar with SSA, <a
				314	href="http://en.wikipedia.org/wiki/Static_single_assignment_form">the wikipedia
				315	article</a> is a good introduction and there are various other introductions to
				316	it available on your favorite search engine. The short version is that
				317	"execution" of the Phi operation requires "remembering" which block control came
				318	from. The Phi operation takes on the value corresponding to the input control
				319	block. In this case, if control comes in from the "then" block, it gets the
				320	value of "calltmp". If control comes from the "else" block, it gets the value
				321	of "calltmp1".</p>
				322
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	323	<p>At this point, you are probably starting to think "Oh no! This means my
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	324	simple and elegant front-end will have to start generating SSA form in order to
				325	use LLVM!". Fortunately, this is not the case, and we strongly advise
				326	<em>not</em> implementing an SSA construction algorithm in your front-end
				327	unless there is an amazingly good reason to do so. In practice, there are two
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	328	sorts of values that float around in code written for your average imperative
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	329	programming language that might need Phi nodes:</p>
				330
				331	<ol>
				332	<li>Code that involves user variables: <tt>x = 1; x = x + 1; </tt></li>
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	333	<li>Values that are implicit in the structure of your AST, such as the Phi node
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	334	in this case.</li>
				335	</ol>
				336
Chris Lattner	b0f0deb	2007-11-05 07:02:49 +0000	[diff] [blame]	337	<p>In <a href="LangImpl7.html">Chapter 7</a> of this tutorial ("mutable
				338	variables"), we'll talk about #1
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	339	in depth. For now, just believe me that you don't need SSA construction to
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	340	handle this case. For #2, you have the choice of using the techniques that we will
				341	describe for #1, or you can insert Phi nodes directly, if convenient. In this
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	342	case, it is really really easy to generate the Phi node, so we choose to do it
				343	directly.</p>
				344
				345	<p>Okay, enough of the motivation and overview, lets generate code!</p>
				346
				347	</div>
				348
				349	<!-- ======================================================================= -->
				350	<div class="doc_subsubsection"><a name="ifcodegen">Code Generation for
				351	If/Then/Else</a></div>
				352	<!-- ======================================================================= -->
				353
				354	<div class="doc_text">
				355
				356	<p>In order to generate code for this, we implement the <tt>Codegen</tt> method
				357	for <tt>IfExprAST</tt>:</p>
				358
				359	<div class="doc_code">
				360	<pre>
				361	Value *IfExprAST::Codegen() {
				362	Value *CondV = Cond->Codegen();
				363	if (CondV == 0) return 0;
				364
				365	// Convert condition to a bool by comparing equal to 0.0.
				366	CondV = Builder.CreateFCmpONE(CondV,
				367	ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
				368	"ifcond");
				369	</pre>
				370	</div>
				371
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	372	<p>This code is straightforward and similar to what we saw before. We emit the
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	373	expression for the condition, then compare that value to zero to get a truth
				374	value as a 1-bit (bool) value.</p>
				375
				376	<div class="doc_code">
				377	<pre>
				378	Function *TheFunction = Builder.GetInsertBlock()->getParent();
				379
				380	// Create blocks for the then and else cases. Insert the 'then' block at the
				381	// end of the function.
				382	BasicBlock *ThenBB = new BasicBlock("then", TheFunction);
				383	BasicBlock *ElseBB = new BasicBlock("else");
				384	BasicBlock *MergeBB = new BasicBlock("ifcont");
				385
				386	Builder.CreateCondBr(CondV, ThenBB, ElseBB);
				387	</pre>
				388	</div>
				389
				390	<p>This code creates the basic blocks that are related to the if/then/else
				391	statement, and correspond directly to the blocks in the example above. The
Chris Lattner	1092a96	2007-11-07 05:47:48 +0000	[diff] [blame]	392	first line gets the current Function object that is being built. It
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	393	gets this by asking the builder for the current BasicBlock, and asking that
				394	block for its "parent" (the function it is currently embedded into).</p>
				395
				396	<p>Once it has that, it creates three blocks. Note that it passes "TheFunction"
				397	into the constructor for the "then" block. This causes the constructor to
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	398	automatically insert the new block into the end of the specified function. The
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	399	other two blocks are created, but aren't yet inserted into the function.</p>
				400
				401	<p>Once the blocks are created, we can emit the conditional branch that chooses
				402	between them. Note that creating new blocks does not implicitly affect the
				403	LLVMBuilder, so it is still inserting into the block that the condition
				404	went into. Also note that it is creating a branch to the "then" block and the
				405	"else" block, even though the "else" block isn't inserted into the function yet.
				406	This is all ok: it is the standard way that LLVM supports forward
				407	references.</p>
				408
				409	<div class="doc_code">
				410	<pre>
				411	// Emit then value.
				412	Builder.SetInsertPoint(ThenBB);
				413
				414	Value *ThenV = Then->Codegen();
				415	if (ThenV == 0) return 0;
				416
				417	Builder.CreateBr(MergeBB);
				418	// Codegen of 'Then' can change the current block, update ThenBB for the PHI.
				419	ThenBB = Builder.GetInsertBlock();
				420	</pre>
				421	</div>
				422
				423	<p>After the conditional branch is inserted, we move the builder to start
				424	inserting into the "then" block. Strictly speaking, this call moves the
				425	insertion point to be at the end of the specified block. However, since the
				426	"then" block is empty, it also starts out by inserting at the beginning of the
				427	block. :)</p>
				428
				429	<p>Once the insertion point is set, we recursively codegen the "then" expression
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	430	from the AST. To finish off the "then" block, we create an unconditional branch
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	431	to the merge block. One interesting (and very important) aspect of the LLVM IR
				432	is that it <a href="../LangRef.html#functionstructure">requires all basic blocks
				433	to be "terminated"</a> with a <a href="../LangRef.html#terminators">control flow
				434	instruction</a> such as return or branch. This means that all control flow,
				435	<em>including fall throughs</em> must be made explicit in the LLVM IR. If you
				436	violate this rule, the verifier will emit an error.</p>
				437
				438	<p>The final line here is quite subtle, but is very important. The basic issue
				439	is that when we create the Phi node in the merge block, we need to set up the
				440	block/value pairs that indicate how the Phi will work. Importantly, the Phi
Chris Lattner	b501964	2007-11-05 17:52:04 +0000	[diff] [blame]	441	node expects to have an entry for each predecessor of the block in the CFG. Why
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	442	then, are we getting the current block when we just set it to ThenBB 5 lines
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	443	above? The problem is that the "Then" expression may actually itself change the
				444	block that the Builder is emitting into if, for example, it contains a nested
				445	"if/then/else" expression. Because calling Codegen recursively could
				446	arbitrarily change the notion of the current block, we are required to get an
				447	up-to-date value for code that will set up the Phi node.</p>
				448
				449	<div class="doc_code">
				450	<pre>
				451	// Emit else block.
				452	TheFunction->getBasicBlockList().push_back(ElseBB);
				453	Builder.SetInsertPoint(ElseBB);
				454
				455	Value *ElseV = Else->Codegen();
				456	if (ElseV == 0) return 0;
				457
				458	Builder.CreateBr(MergeBB);
				459	// Codegen of 'Else' can change the current block, update ElseBB for the PHI.
				460	ElseBB = Builder.GetInsertBlock();
				461	</pre>
				462	</div>
				463
				464	<p>Code generation for the 'else' block is basically identical to codegen for
				465	the 'then' block. The only significant difference is the first line, which adds
				466	the 'else' block to the function. Recall previously that the 'else' block was
				467	created, but not added to the function. Now that the 'then' and 'else' blocks
				468	are emitted, we can finish up with the merge code:</p>
				469
				470	<div class="doc_code">
				471	<pre>
				472	// Emit merge block.
				473	TheFunction->getBasicBlockList().push_back(MergeBB);
				474	Builder.SetInsertPoint(MergeBB);
				475	PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
				476
				477	PN->addIncoming(ThenV, ThenBB);
				478	PN->addIncoming(ElseV, ElseBB);
				479	return PN;
				480	}
				481	</pre>
				482	</div>
				483
				484	<p>The first two lines here are now familiar: the first adds the "merge" block
				485	to the Function object (it was previously floating, like the else block above).
				486	The second block changes the insertion point so that newly created code will go
				487	into the "merge" block. Once that is done, we need to create the PHI node and
				488	set up the block/value pairs for the PHI.</p>
				489
				490	<p>Finally, the CodeGen function returns the phi node as the value computed by
				491	the if/then/else expression. In our example above, this returned value will
				492	feed into the code for the top-level function, which will create the return
				493	instruction.</p>
				494
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	495	<p>Overall, we now have the ability to execute conditional code in
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	496	Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
				497	that can calculate a wide variety of numeric functions. Next up we'll add
				498	another useful expression that is familiar from non-functional languages...</p>
				499
				500	</div>
				501
				502	<!-- *********************************************************************** -->
				503	<div class="doc_section"><a name="for">'for' Loop Expression</a></div>
				504	<!-- *********************************************************************** -->
				505
				506	<div class="doc_text">
				507
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	508	<p>Now that we know how to add basic control flow constructs to the language,
				509	we have the tools to add more powerful things. Lets add something more
				510	aggressive, a 'for' expression:</p>
				511
				512	<div class="doc_code">
				513	<pre>
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	514	extern putchard(char)
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	515	def printstar(n)
				516	for i = 1, i < n, 1.0 in
				517	putchard(42); # ascii 42 = '*'
				518
				519	# print 100 '*' characters
				520	printstar(100);
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	521	</pre>
				522	</div>
				523
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	524	<p>This expression defines a new variable ("i" in this case) which iterates from
				525	a starting value, while the condition ("i < n" in this case) is true,
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	526	incrementing by an optional step value ("1.0" in this case). If the step value
				527	is omitted, it defaults to 1.0. While the loop is true, it executes its
				528	body expression. Because we don't have anything better to return, we'll just
				529	define the loop as always returning 0.0. In the future when we have mutable
				530	variables, it will get more useful.</p>
				531
				532	<p>As before, lets talk about the changes that we need to Kaleidoscope to
				533	support this.</p>
				534
				535	</div>
				536
				537	<!-- ======================================================================= -->
				538	<div class="doc_subsubsection"><a name="forlexer">Lexer Extensions for
				539	the 'for' Loop</a></div>
				540	<!-- ======================================================================= -->
				541
				542	<div class="doc_text">
				543
				544	<p>The lexer extensions are the same sort of thing as for if/then/else:</p>
				545
				546	<div class="doc_code">
				547	<pre>
				548	... in enum Token ...
				549	// control
				550	tok_if = -6, tok_then = -7, tok_else = -8,
				551	<b> tok_for = -9, tok_in = -10</b>
				552
				553	... in gettok ...
				554	if (IdentifierStr == "def") return tok_def;
				555	if (IdentifierStr == "extern") return tok_extern;
				556	if (IdentifierStr == "if") return tok_if;
				557	if (IdentifierStr == "then") return tok_then;
				558	if (IdentifierStr == "else") return tok_else;
				559	<b>if (IdentifierStr == "for") return tok_for;
				560	if (IdentifierStr == "in") return tok_in;</b>
				561	return tok_identifier;
				562	</pre>
				563	</div>
				564
				565	</div>
				566
				567	<!-- ======================================================================= -->
				568	<div class="doc_subsubsection"><a name="forast">AST Extensions for
				569	the 'for' Loop</a></div>
				570	<!-- ======================================================================= -->
				571
				572	<div class="doc_text">
				573
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	574	<p>The AST node is just as simple. It basically boils down to capturing
Chris Lattner	1092a96	2007-11-07 05:47:48 +0000	[diff] [blame]	575	the variable name and the constituent expressions in the node.</p>
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	576
				577	<div class="doc_code">
				578	<pre>
				579	/// ForExprAST - Expression class for for/in.
				580	class ForExprAST : public ExprAST {
				581	std::string VarName;
				582	ExprAST Start, End, Step, Body;
				583	public:
				584	ForExprAST(const std::string &varname, ExprAST start, ExprAST end,
				585	ExprAST step, ExprAST body)
				586	: VarName(varname), Start(start), End(end), Step(step), Body(body) {}
				587	virtual Value *Codegen();
				588	};
				589	</pre>
				590	</div>
				591
				592	</div>
				593
				594	<!-- ======================================================================= -->
				595	<div class="doc_subsubsection"><a name="forparser">Parser Extensions for
				596	the 'for' Loop</a></div>
				597	<!-- ======================================================================= -->
				598
				599	<div class="doc_text">
				600
				601	<p>The parser code is also fairly standard. The only interesting thing here is
				602	handling of the optional step value. The parser code handles it by checking to
				603	see if the second comma is present. If not, it sets the step value to null in
				604	the AST node:</p>
				605
				606	<div class="doc_code">
				607	<pre>
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	608	/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	609	static ExprAST *ParseForExpr() {
				610	getNextToken(); // eat the for.
				611
				612	if (CurTok != tok_identifier)
				613	return Error("expected identifier after for");
				614
				615	std::string IdName = IdentifierStr;
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	616	getNextToken(); // eat identifier.
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	617
				618	if (CurTok != '=')
				619	return Error("expected '=' after for");
				620	getNextToken(); // eat '='.
				621
				622
				623	ExprAST *Start = ParseExpression();
				624	if (Start == 0) return 0;
				625	if (CurTok != ',')
				626	return Error("expected ',' after for start value");
				627	getNextToken();
				628
				629	ExprAST *End = ParseExpression();
				630	if (End == 0) return 0;
				631
				632	// The step value is optional.
				633	ExprAST *Step = 0;
				634	if (CurTok == ',') {
				635	getNextToken();
				636	Step = ParseExpression();
				637	if (Step == 0) return 0;
				638	}
				639
				640	if (CurTok != tok_in)
				641	return Error("expected 'in' after for");
				642	getNextToken(); // eat 'in'.
				643
				644	ExprAST *Body = ParseExpression();
				645	if (Body == 0) return 0;
				646
				647	return new ForExprAST(IdName, Start, End, Step, Body);
				648	}
				649	</pre>
				650	</div>
				651
				652	</div>
				653
				654	<!-- ======================================================================= -->
				655	<div class="doc_subsubsection"><a name="forir">LLVM IR for
				656	the 'for' Loop</a></div>
				657	<!-- ======================================================================= -->
				658
				659	<div class="doc_text">
				660
				661	<p>Now we get to the good part: the LLVM IR we want to generate for this thing.
Gordon Henriksen	bb310f1	2007-11-12 13:46:21 +0000	[diff] [blame]	662	With the simple example above, we get this LLVM IR (note that this dump is
				663	generated with optimizations disabled for clarity):
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	664	</p>
				665
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	666	<div class="doc_code">
				667	<pre>
				668	declare double @putchard(double)
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	669
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	670	define double @printstar(double %n) {
				671	entry:
				672	; initial value = 1.0 (inlined into phi)
				673	br label %loop
				674
				675	loop: ; preds = %loop, %entry
				676	%i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
				677	; body
				678	%calltmp = call double @putchard( double 4.200000e+01 )
				679	; increment
				680	%nextvar = add double %i, 1.000000e+00
				681
				682	; termination test
Chris Lattner	7115521	2007-11-06 01:39:12 +0000	[diff] [blame]	683	%cmptmp = fcmp ult double %i, %n
				684	%booltmp = uitofp i1 %cmptmp to double
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	685	%loopcond = fcmp one double %booltmp, 0.000000e+00
				686	br i1 %loopcond, label %loop, label %afterloop
				687
				688	afterloop: ; preds = %loop
				689	; loop always returns 0.0
				690	ret double 0.000000e+00
				691	}
				692	</pre>
				693	</div>
				694
				695	<p>This loop contains all the same constructs we saw before: a phi node, several
				696	expressions, and some basic blocks. Lets see how this fits together.</p>
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	697
				698	</div>
				699
				700	<!-- ======================================================================= -->
				701	<div class="doc_subsubsection"><a name="forcodegen">Code Generation for
				702	the 'for' Loop</a></div>
				703	<!-- ======================================================================= -->
				704
				705	<div class="doc_text">
				706
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	707	<p>The first part of Codegen is very simple: we just output the start expression
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	708	for the loop value:</p>
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	709
				710	<div class="doc_code">
				711	<pre>
				712	Value *ForExprAST::Codegen() {
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	713	// Emit the start code first, without 'variable' in scope.
				714	Value *StartVal = Start->Codegen();
				715	if (StartVal == 0) return 0;
				716	</pre>
				717	</div>
				718
				719	<p>With this out of the way, the next step is to set up the LLVM basic block
				720	for the start of the loop body. In the case above, the whole loop body is one
				721	block, but remember that the body code itself could consist of multiple blocks
Chris Lattner	1092a96	2007-11-07 05:47:48 +0000	[diff] [blame]	722	(e.g. if it contains an if/then/else or a for/in expression).</p>
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	723
				724	<div class="doc_code">
				725	<pre>
				726	// Make the new basic block for the loop header, inserting after current
				727	// block.
				728	Function *TheFunction = Builder.GetInsertBlock()->getParent();
				729	BasicBlock *PreheaderBB = Builder.GetInsertBlock();
				730	BasicBlock *LoopBB = new BasicBlock("loop", TheFunction);
				731
				732	// Insert an explicit fall through from the current block to the LoopBB.
				733	Builder.CreateBr(LoopBB);
				734	</pre>
				735	</div>
				736
				737	<p>This code is similar to what we saw for if/then/else. Because we will need
				738	it to create the Phi node, we remember the block that falls through into the
				739	loop. Once we have that, we create the actual block that starts the loop and
				740	create an unconditional branch for the fall-through between the two blocks.</p>
				741
				742	<div class="doc_code">
				743	<pre>
				744	// Start insertion in LoopBB.
				745	Builder.SetInsertPoint(LoopBB);
				746
				747	// Start the PHI node with an entry for Start.
				748	PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
				749	Variable->addIncoming(StartVal, PreheaderBB);
				750	</pre>
				751	</div>
				752
				753	<p>Now that the "preheader" for the loop is set up, we switch to emitting code
				754	for the loop body. To begin with, we move the insertion point and create the
Chris Lattner	1092a96	2007-11-07 05:47:48 +0000	[diff] [blame]	755	PHI node for the loop induction variable. Since we already know the incoming
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	756	value for the starting value, we add it to the Phi node. Note that the Phi will
				757	eventually get a second value for the backedge, but we can't set it up yet
				758	(because it doesn't exist!).</p>
				759
				760	<div class="doc_code">
				761	<pre>
				762	// Within the loop, the variable is defined equal to the PHI node. If it
				763	// shadows an existing variable, we have to restore it, so save it now.
				764	Value *OldVal = NamedValues[VarName];
				765	NamedValues[VarName] = Variable;
				766
				767	// Emit the body of the loop. This, like any other expr, can change the
				768	// current BB. Note that we ignore the value computed by the body, but don't
				769	// allow an error.
				770	if (Body->Codegen() == 0)
				771	return 0;
				772	</pre>
				773	</div>
				774
				775	<p>Now the code starts to get more interesting. Our 'for' loop introduces a new
				776	variable to the symbol table. This means that our symbol table can now contain
				777	either function arguments or loop variables. To handle this, before we codegen
				778	the body of the loop, we add the loop variable as the current value for its
				779	name. Note that it is possible that there is a variable of the same name in the
				780	outer scope. It would be easy to make this an error (emit an error and return
				781	null if there is already an entry for VarName) but we choose to allow shadowing
				782	of variables. In order to handle this correctly, we remember the Value that
				783	we are potentially shadowing in <tt>OldVal</tt> (which will be null if there is
				784	no shadowed variable).</p>
				785
				786	<p>Once the loop variable is set into the symbol table, the code recursively
				787	codegen's the body. This allows the body to use the loop variable: any
				788	references to it will naturally find it in the symbol table.</p>
				789
				790	<div class="doc_code">
				791	<pre>
				792	// Emit the step value.
				793	Value *StepVal;
				794	if (Step) {
				795	StepVal = Step->Codegen();
				796	if (StepVal == 0) return 0;
				797	} else {
				798	// If not specified, use 1.0.
				799	StepVal = ConstantFP::get(Type::DoubleTy, APFloat(1.0));
				800	}
				801
				802	Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
				803	</pre>
				804	</div>
				805
				806	<p>Now that the body is emitted, we compute the next value of the iteration
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	807	variable by adding the step value, or 1.0 if it isn't present. '<tt>NextVar</tt>'
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	808	will be the value of the loop variable on the next iteration of the loop.</p>
				809
				810	<div class="doc_code">
				811	<pre>
				812	// Compute the end condition.
				813	Value *EndCond = End->Codegen();
				814	if (EndCond == 0) return EndCond;
				815
				816	// Convert condition to a bool by comparing equal to 0.0.
				817	EndCond = Builder.CreateFCmpONE(EndCond,
				818	ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
				819	"loopcond");
				820	</pre>
				821	</div>
				822
				823	<p>Finally, we evaluate the exit value of the loop, to determine whether the
				824	loop should exit. This mirrors the condition evaluation for the if/then/else
				825	statement.</p>
				826
				827	<div class="doc_code">
				828	<pre>
				829	// Create the "after loop" block and insert it.
				830	BasicBlock *LoopEndBB = Builder.GetInsertBlock();
				831	BasicBlock *AfterBB = new BasicBlock("afterloop", TheFunction);
				832
				833	// Insert the conditional branch into the end of LoopEndBB.
				834	Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
				835
				836	// Any new code will be inserted in AfterBB.
				837	Builder.SetInsertPoint(AfterBB);
				838	</pre>
				839	</div>
				840
				841	<p>With the code for the body of the loop complete, we just need to finish up
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	842	the control flow for it. This code remembers the end block (for the phi node), then creates the block for the loop exit ("afterloop"). Based on the value of the
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	843	exit condition, it creates a conditional branch that chooses between executing
				844	the loop again and exiting the loop. Any future code is emitted in the
				845	"afterloop" block, so it sets the insertion position to it.</p>
				846
				847	<div class="doc_code">
				848	<pre>
				849	// Add a new entry to the PHI node for the backedge.
				850	Variable->addIncoming(NextVar, LoopEndBB);
				851
				852	// Restore the unshadowed variable.
				853	if (OldVal)
				854	NamedValues[VarName] = OldVal;
				855	else
				856	NamedValues.erase(VarName);
				857
				858	// for expr always returns 0.0.
				859	return Constant::getNullValue(Type::DoubleTy);
				860	}
				861	</pre>
				862	</div>
				863
				864	<p>The final code handles various cleanups: now that we have the "NextVar"
				865	value, we can add the incoming value to the loop PHI node. After that, we
				866	remove the loop variable from the symbol table, so that it isn't in scope after
				867	the for loop. Finally, code generation of the for loop always returns 0.0, so
				868	that is what we return from <tt>ForExprAST::Codegen</tt>.</p>
				869
				870	<p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
Chris Lattner	41fcea3	2007-11-13 07:06:30 +0000	[diff] [blame]	871	the tutorial. In this chapter we added two control flow constructs, and used them to motivate a couple of aspects of the LLVM IR that are important for front-end implementors
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	872	to know. In the next chapter of our saga, we will get a bit crazier and add
Chris Lattner	7115521	2007-11-06 01:39:12 +0000	[diff] [blame]	873	<a href="LangImpl6.html">user-defined operators</a> to our poor innocent
				874	language.</p>
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	875
				876	</div>
				877
				878	<!-- *********************************************************************** -->
				879	<div class="doc_section"><a name="code">Full Code Listing</a></div>
				880	<!-- *********************************************************************** -->
				881
				882	<div class="doc_text">
				883
				884	<p>
				885	Here is the complete code listing for our running example, enhanced with the
				886	if/then/else and for expressions.. To build this example, use:
				887	</p>
				888
				889	<div class="doc_code">
				890	<pre>
				891	# Compile
				892	g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
				893	# Run
				894	./toy
				895	</pre>
				896	</div>
				897
				898	<p>Here is the code:</p>
				899
				900	<div class="doc_code">
				901	<pre>
				902	#include "llvm/DerivedTypes.h"
				903	#include "llvm/ExecutionEngine/ExecutionEngine.h"
				904	#include "llvm/Module.h"
				905	#include "llvm/ModuleProvider.h"
				906	#include "llvm/PassManager.h"
				907	#include "llvm/Analysis/Verifier.h"
				908	#include "llvm/Target/TargetData.h"
				909	#include "llvm/Transforms/Scalar.h"
				910	#include "llvm/Support/LLVMBuilder.h"
				911	#include <cstdio>
				912	#include <string>
				913	#include <map>
				914	#include <vector>
				915	using namespace llvm;
				916
				917	//===----------------------------------------------------------------------===//
				918	// Lexer
				919	//===----------------------------------------------------------------------===//
				920
				921	// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
				922	// of these for known things.
				923	enum Token {
				924	tok_eof = -1,
				925
				926	// commands
				927	tok_def = -2, tok_extern = -3,
				928
				929	// primary
				930	tok_identifier = -4, tok_number = -5,
				931
				932	// control
				933	tok_if = -6, tok_then = -7, tok_else = -8,
				934	tok_for = -9, tok_in = -10
				935	};
				936
				937	static std::string IdentifierStr; // Filled in if tok_identifier
				938	static double NumVal; // Filled in if tok_number
				939
				940	/// gettok - Return the next token from standard input.
				941	static int gettok() {
				942	static int LastChar = ' ';
				943
				944	// Skip any whitespace.
				945	while (isspace(LastChar))
				946	LastChar = getchar();
				947
				948	if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
				949	IdentifierStr = LastChar;
				950	while (isalnum((LastChar = getchar())))
				951	IdentifierStr += LastChar;
				952
				953	if (IdentifierStr == "def") return tok_def;
				954	if (IdentifierStr == "extern") return tok_extern;
				955	if (IdentifierStr == "if") return tok_if;
				956	if (IdentifierStr == "then") return tok_then;
				957	if (IdentifierStr == "else") return tok_else;
				958	if (IdentifierStr == "for") return tok_for;
				959	if (IdentifierStr == "in") return tok_in;
				960	return tok_identifier;
				961	}
				962
				963	if (isdigit(LastChar) \|\| LastChar == '.') { // Number: [0-9.]+
				964	std::string NumStr;
				965	do {
				966	NumStr += LastChar;
				967	LastChar = getchar();
				968	} while (isdigit(LastChar) \|\| LastChar == '.');
				969
				970	NumVal = strtod(NumStr.c_str(), 0);
				971	return tok_number;
				972	}
				973
				974	if (LastChar == '#') {
				975	// Comment until end of line.
				976	do LastChar = getchar();
				977	while (LastChar != EOF && LastChar != '\n' & LastChar != '\r');
				978
				979	if (LastChar != EOF)
				980	return gettok();
				981	}
				982
				983	// Check for end of file. Don't eat the EOF.
				984	if (LastChar == EOF)
				985	return tok_eof;
				986
				987	// Otherwise, just return the character as its ascii value.
				988	int ThisChar = LastChar;
				989	LastChar = getchar();
				990	return ThisChar;
				991	}
				992
				993	//===----------------------------------------------------------------------===//
				994	// Abstract Syntax Tree (aka Parse Tree)
				995	//===----------------------------------------------------------------------===//
				996
				997	/// ExprAST - Base class for all expression nodes.
				998	class ExprAST {
				999	public:
				1000	virtual ~ExprAST() {}
				1001	virtual Value *Codegen() = 0;
				1002	};
				1003
				1004	/// NumberExprAST - Expression class for numeric literals like "1.0".
				1005	class NumberExprAST : public ExprAST {
				1006	double Val;
				1007	public:
				1008	NumberExprAST(double val) : Val(val) {}
				1009	virtual Value *Codegen();
				1010	};
				1011
				1012	/// VariableExprAST - Expression class for referencing a variable, like "a".
				1013	class VariableExprAST : public ExprAST {
				1014	std::string Name;
				1015	public:
				1016	VariableExprAST(const std::string &name) : Name(name) {}
				1017	virtual Value *Codegen();
				1018	};
				1019
				1020	/// BinaryExprAST - Expression class for a binary operator.
				1021	class BinaryExprAST : public ExprAST {
				1022	char Op;
				1023	ExprAST LHS, RHS;
				1024	public:
				1025	BinaryExprAST(char op, ExprAST lhs, ExprAST rhs)
				1026	: Op(op), LHS(lhs), RHS(rhs) {}
				1027	virtual Value *Codegen();
				1028	};
				1029
				1030	/// CallExprAST - Expression class for function calls.
				1031	class CallExprAST : public ExprAST {
				1032	std::string Callee;
				1033	std::vector<ExprAST*> Args;
				1034	public:
				1035	CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
				1036	: Callee(callee), Args(args) {}
				1037	virtual Value *Codegen();
				1038	};
				1039
				1040	/// IfExprAST - Expression class for if/then/else.
				1041	class IfExprAST : public ExprAST {
				1042	ExprAST Cond, Then, *Else;
				1043	public:
				1044	IfExprAST(ExprAST cond, ExprAST then, ExprAST *_else)
				1045	: Cond(cond), Then(then), Else(_else) {}
				1046	virtual Value *Codegen();
				1047	};
				1048
				1049	/// ForExprAST - Expression class for for/in.
				1050	class ForExprAST : public ExprAST {
				1051	std::string VarName;
				1052	ExprAST Start, End, Step, Body;
				1053	public:
				1054	ForExprAST(const std::string &varname, ExprAST start, ExprAST end,
				1055	ExprAST step, ExprAST body)
				1056	: VarName(varname), Start(start), End(end), Step(step), Body(body) {}
				1057	virtual Value *Codegen();
				1058	};
				1059
				1060	/// PrototypeAST - This class represents the "prototype" for a function,
				1061	/// which captures its argument names as well as if it is an operator.
				1062	class PrototypeAST {
				1063	std::string Name;
				1064	std::vector<std::string> Args;
				1065	public:
				1066	PrototypeAST(const std::string &name, const std::vector<std::string> &args)
				1067	: Name(name), Args(args) {}
				1068
				1069	Function *Codegen();
				1070	};
				1071
				1072	/// FunctionAST - This class represents a function definition itself.
				1073	class FunctionAST {
				1074	PrototypeAST *Proto;
				1075	ExprAST *Body;
				1076	public:
				1077	FunctionAST(PrototypeAST proto, ExprAST body)
				1078	: Proto(proto), Body(body) {}
				1079
				1080	Function *Codegen();
				1081	};
				1082
				1083	//===----------------------------------------------------------------------===//
				1084	// Parser
				1085	//===----------------------------------------------------------------------===//
				1086
				1087	/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
				1088	/// token the parser it looking at. getNextToken reads another token from the
				1089	/// lexer and updates CurTok with its results.
				1090	static int CurTok;
				1091	static int getNextToken() {
				1092	return CurTok = gettok();
				1093	}
				1094
				1095	/// BinopPrecedence - This holds the precedence for each binary operator that is
				1096	/// defined.
				1097	static std::map<char, int> BinopPrecedence;
				1098
				1099	/// GetTokPrecedence - Get the precedence of the pending binary operator token.
				1100	static int GetTokPrecedence() {
				1101	if (!isascii(CurTok))
				1102	return -1;
				1103
				1104	// Make sure it's a declared binop.
				1105	int TokPrec = BinopPrecedence[CurTok];
				1106	if (TokPrec <= 0) return -1;
				1107	return TokPrec;
				1108	}
				1109
				1110	/// Error* - These are little helper functions for error handling.
				1111	ExprAST Error(const char Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
				1112	PrototypeAST ErrorP(const char Str) { Error(Str); return 0; }
				1113	FunctionAST ErrorF(const char Str) { Error(Str); return 0; }
				1114
				1115	static ExprAST *ParseExpression();
				1116
				1117	/// identifierexpr
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	1118	/// ::= identifier
				1119	/// ::= identifier '(' expression* ')'
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1120	static ExprAST *ParseIdentifierExpr() {
				1121	std::string IdName = IdentifierStr;
				1122
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	1123	getNextToken(); // eat identifier.
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1124
				1125	if (CurTok != '(') // Simple variable ref.
				1126	return new VariableExprAST(IdName);
				1127
				1128	// Call.
				1129	getNextToken(); // eat (
				1130	std::vector<ExprAST*> Args;
				1131	if (CurTok != ')') {
				1132	while (1) {
				1133	ExprAST *Arg = ParseExpression();
				1134	if (!Arg) return 0;
				1135	Args.push_back(Arg);
				1136
				1137	if (CurTok == ')') break;
				1138
				1139	if (CurTok != ',')
				1140	return Error("Expected ')'");
				1141	getNextToken();
				1142	}
				1143	}
				1144
				1145	// Eat the ')'.
				1146	getNextToken();
				1147
				1148	return new CallExprAST(IdName, Args);
				1149	}
				1150
				1151	/// numberexpr ::= number
				1152	static ExprAST *ParseNumberExpr() {
				1153	ExprAST *Result = new NumberExprAST(NumVal);
				1154	getNextToken(); // consume the number
				1155	return Result;
				1156	}
				1157
				1158	/// parenexpr ::= '(' expression ')'
				1159	static ExprAST *ParseParenExpr() {
				1160	getNextToken(); // eat (.
				1161	ExprAST *V = ParseExpression();
				1162	if (!V) return 0;
				1163
				1164	if (CurTok != ')')
				1165	return Error("expected ')'");
				1166	getNextToken(); // eat ).
				1167	return V;
				1168	}
				1169
				1170	/// ifexpr ::= 'if' expression 'then' expression 'else' expression
				1171	static ExprAST *ParseIfExpr() {
				1172	getNextToken(); // eat the if.
				1173
				1174	// condition.
				1175	ExprAST *Cond = ParseExpression();
				1176	if (!Cond) return 0;
				1177
				1178	if (CurTok != tok_then)
				1179	return Error("expected then");
				1180	getNextToken(); // eat the then
				1181
				1182	ExprAST *Then = ParseExpression();
				1183	if (Then == 0) return 0;
				1184
				1185	if (CurTok != tok_else)
				1186	return Error("expected else");
				1187
				1188	getNextToken();
				1189
				1190	ExprAST *Else = ParseExpression();
				1191	if (!Else) return 0;
				1192
				1193	return new IfExprAST(Cond, Then, Else);
				1194	}
				1195
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	1196	/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1197	static ExprAST *ParseForExpr() {
				1198	getNextToken(); // eat the for.
				1199
				1200	if (CurTok != tok_identifier)
				1201	return Error("expected identifier after for");
				1202
				1203	std::string IdName = IdentifierStr;
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	1204	getNextToken(); // eat identifier.
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1205
				1206	if (CurTok != '=')
				1207	return Error("expected '=' after for");
				1208	getNextToken(); // eat '='.
				1209
				1210
				1211	ExprAST *Start = ParseExpression();
				1212	if (Start == 0) return 0;
				1213	if (CurTok != ',')
				1214	return Error("expected ',' after for start value");
				1215	getNextToken();
				1216
				1217	ExprAST *End = ParseExpression();
				1218	if (End == 0) return 0;
				1219
				1220	// The step value is optional.
				1221	ExprAST *Step = 0;
				1222	if (CurTok == ',') {
				1223	getNextToken();
				1224	Step = ParseExpression();
				1225	if (Step == 0) return 0;
				1226	}
				1227
				1228	if (CurTok != tok_in)
				1229	return Error("expected 'in' after for");
				1230	getNextToken(); // eat 'in'.
				1231
				1232	ExprAST *Body = ParseExpression();
				1233	if (Body == 0) return 0;
				1234
				1235	return new ForExprAST(IdName, Start, End, Step, Body);
				1236	}
				1237
				1238
				1239	/// primary
				1240	/// ::= identifierexpr
				1241	/// ::= numberexpr
				1242	/// ::= parenexpr
				1243	/// ::= ifexpr
				1244	/// ::= forexpr
				1245	static ExprAST *ParsePrimary() {
				1246	switch (CurTok) {
				1247	default: return Error("unknown token when expecting an expression");
				1248	case tok_identifier: return ParseIdentifierExpr();
				1249	case tok_number: return ParseNumberExpr();
				1250	case '(': return ParseParenExpr();
				1251	case tok_if: return ParseIfExpr();
				1252	case tok_for: return ParseForExpr();
				1253	}
				1254	}
				1255
				1256	/// binoprhs
				1257	/// ::= ('+' primary)*
				1258	static ExprAST ParseBinOpRHS(int ExprPrec, ExprAST LHS) {
				1259	// If this is a binop, find its precedence.
				1260	while (1) {
				1261	int TokPrec = GetTokPrecedence();
				1262
				1263	// If this is a binop that binds at least as tightly as the current binop,
				1264	// consume it, otherwise we are done.
				1265	if (TokPrec < ExprPrec)
				1266	return LHS;
				1267
				1268	// Okay, we know this is a binop.
				1269	int BinOp = CurTok;
				1270	getNextToken(); // eat binop
				1271
				1272	// Parse the primary expression after the binary operator.
				1273	ExprAST *RHS = ParsePrimary();
				1274	if (!RHS) return 0;
				1275
				1276	// If BinOp binds less tightly with RHS than the operator after RHS, let
				1277	// the pending operator take RHS as its LHS.
				1278	int NextPrec = GetTokPrecedence();
				1279	if (TokPrec < NextPrec) {
				1280	RHS = ParseBinOpRHS(TokPrec+1, RHS);
				1281	if (RHS == 0) return 0;
				1282	}
				1283
				1284	// Merge LHS/RHS.
				1285	LHS = new BinaryExprAST(BinOp, LHS, RHS);
				1286	}
				1287	}
				1288
				1289	/// expression
				1290	/// ::= primary binoprhs
				1291	///
				1292	static ExprAST *ParseExpression() {
				1293	ExprAST *LHS = ParsePrimary();
				1294	if (!LHS) return 0;
				1295
				1296	return ParseBinOpRHS(0, LHS);
				1297	}
				1298
				1299	/// prototype
				1300	/// ::= id '(' id* ')'
				1301	static PrototypeAST *ParsePrototype() {
				1302	if (CurTok != tok_identifier)
				1303	return ErrorP("Expected function name in prototype");
				1304
				1305	std::string FnName = IdentifierStr;
				1306	getNextToken();
				1307
				1308	if (CurTok != '(')
				1309	return ErrorP("Expected '(' in prototype");
				1310
				1311	std::vector<std::string> ArgNames;
				1312	while (getNextToken() == tok_identifier)
				1313	ArgNames.push_back(IdentifierStr);
				1314	if (CurTok != ')')
				1315	return ErrorP("Expected ')' in prototype");
				1316
				1317	// success.
				1318	getNextToken(); // eat ')'.
				1319
				1320	return new PrototypeAST(FnName, ArgNames);
				1321	}
				1322
				1323	/// definition ::= 'def' prototype expression
				1324	static FunctionAST *ParseDefinition() {
				1325	getNextToken(); // eat def.
				1326	PrototypeAST *Proto = ParsePrototype();
				1327	if (Proto == 0) return 0;
				1328
				1329	if (ExprAST *E = ParseExpression())
				1330	return new FunctionAST(Proto, E);
				1331	return 0;
				1332	}
				1333
				1334	/// toplevelexpr ::= expression
				1335	static FunctionAST *ParseTopLevelExpr() {
				1336	if (ExprAST *E = ParseExpression()) {
				1337	// Make an anonymous proto.
				1338	PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
				1339	return new FunctionAST(Proto, E);
				1340	}
				1341	return 0;
				1342	}
				1343
				1344	/// external ::= 'extern' prototype
				1345	static PrototypeAST *ParseExtern() {
				1346	getNextToken(); // eat extern.
				1347	return ParsePrototype();
				1348	}
				1349
				1350	//===----------------------------------------------------------------------===//
				1351	// Code Generation
				1352	//===----------------------------------------------------------------------===//
				1353
				1354	static Module *TheModule;
				1355	static LLVMFoldingBuilder Builder;
				1356	static std::map<std::string, Value*> NamedValues;
				1357	static FunctionPassManager *TheFPM;
				1358
				1359	Value ErrorV(const char Str) { Error(Str); return 0; }
				1360
				1361	Value *NumberExprAST::Codegen() {
				1362	return ConstantFP::get(Type::DoubleTy, APFloat(Val));
				1363	}
				1364
				1365	Value *VariableExprAST::Codegen() {
				1366	// Look this variable up in the function.
				1367	Value *V = NamedValues[Name];
				1368	return V ? V : ErrorV("Unknown variable name");
				1369	}
				1370
				1371	Value *BinaryExprAST::Codegen() {
				1372	Value *L = LHS->Codegen();
				1373	Value *R = RHS->Codegen();
				1374	if (L == 0 \|\| R == 0) return 0;
				1375
				1376	switch (Op) {
				1377	case '+': return Builder.CreateAdd(L, R, "addtmp");
				1378	case '-': return Builder.CreateSub(L, R, "subtmp");
				1379	case '*': return Builder.CreateMul(L, R, "multmp");
				1380	case '<':
Chris Lattner	7115521	2007-11-06 01:39:12 +0000	[diff] [blame]	1381	L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1382	// Convert bool 0/1 to double 0.0 or 1.0
				1383	return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
				1384	default: return ErrorV("invalid binary operator");
				1385	}
				1386	}
				1387
				1388	Value *CallExprAST::Codegen() {
				1389	// Look up the name in the global module table.
				1390	Function *CalleeF = TheModule->getFunction(Callee);
				1391	if (CalleeF == 0)
				1392	return ErrorV("Unknown function referenced");
				1393
				1394	// If argument mismatch error.
				1395	if (CalleeF->arg_size() != Args.size())
				1396	return ErrorV("Incorrect # arguments passed");
				1397
				1398	std::vector<Value*> ArgsV;
				1399	for (unsigned i = 0, e = Args.size(); i != e; ++i) {
				1400	ArgsV.push_back(Args[i]->Codegen());
				1401	if (ArgsV.back() == 0) return 0;
				1402	}
				1403
				1404	return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
				1405	}
				1406
				1407	Value *IfExprAST::Codegen() {
				1408	Value *CondV = Cond->Codegen();
				1409	if (CondV == 0) return 0;
				1410
				1411	// Convert condition to a bool by comparing equal to 0.0.
				1412	CondV = Builder.CreateFCmpONE(CondV,
				1413	ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
				1414	"ifcond");
				1415
				1416	Function *TheFunction = Builder.GetInsertBlock()->getParent();
				1417
				1418	// Create blocks for the then and else cases. Insert the 'then' block at the
				1419	// end of the function.
				1420	BasicBlock *ThenBB = new BasicBlock("then", TheFunction);
				1421	BasicBlock *ElseBB = new BasicBlock("else");
				1422	BasicBlock *MergeBB = new BasicBlock("ifcont");
				1423
				1424	Builder.CreateCondBr(CondV, ThenBB, ElseBB);
				1425
				1426	// Emit then value.
				1427	Builder.SetInsertPoint(ThenBB);
				1428
				1429	Value *ThenV = Then->Codegen();
				1430	if (ThenV == 0) return 0;
				1431
				1432	Builder.CreateBr(MergeBB);
				1433	// Codegen of 'Then' can change the current block, update ThenBB for the PHI.
				1434	ThenBB = Builder.GetInsertBlock();
				1435
				1436	// Emit else block.
				1437	TheFunction->getBasicBlockList().push_back(ElseBB);
				1438	Builder.SetInsertPoint(ElseBB);
				1439
				1440	Value *ElseV = Else->Codegen();
				1441	if (ElseV == 0) return 0;
				1442
				1443	Builder.CreateBr(MergeBB);
				1444	// Codegen of 'Else' can change the current block, update ElseBB for the PHI.
				1445	ElseBB = Builder.GetInsertBlock();
				1446
				1447	// Emit merge block.
				1448	TheFunction->getBasicBlockList().push_back(MergeBB);
				1449	Builder.SetInsertPoint(MergeBB);
				1450	PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
				1451
				1452	PN->addIncoming(ThenV, ThenBB);
				1453	PN->addIncoming(ElseV, ElseBB);
				1454	return PN;
				1455	}
				1456
				1457	Value *ForExprAST::Codegen() {
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	1458	// Output this as:
				1459	// ...
				1460	// start = startexpr
				1461	// goto loop
				1462	// loop:
				1463	// variable = phi [start, loopheader], [nextvariable, loopend]
				1464	// ...
				1465	// bodyexpr
				1466	// ...
				1467	// loopend:
				1468	// step = stepexpr
				1469	// nextvariable = variable + step
				1470	// endcond = endexpr
				1471	// br endcond, loop, endloop
				1472	// outloop:
				1473
				1474	// Emit the start code first, without 'variable' in scope.
				1475	Value *StartVal = Start->Codegen();
				1476	if (StartVal == 0) return 0;
				1477
				1478	// Make the new basic block for the loop header, inserting after current
				1479	// block.
				1480	Function *TheFunction = Builder.GetInsertBlock()->getParent();
				1481	BasicBlock *PreheaderBB = Builder.GetInsertBlock();
				1482	BasicBlock *LoopBB = new BasicBlock("loop", TheFunction);
				1483
				1484	// Insert an explicit fall through from the current block to the LoopBB.
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	1485	Builder.CreateBr(LoopBB);
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1486
				1487	// Start insertion in LoopBB.
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	1488	Builder.SetInsertPoint(LoopBB);
				1489
				1490	// Start the PHI node with an entry for Start.
				1491	PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
				1492	Variable->addIncoming(StartVal, PreheaderBB);
				1493
				1494	// Within the loop, the variable is defined equal to the PHI node. If it
				1495	// shadows an existing variable, we have to restore it, so save it now.
				1496	Value *OldVal = NamedValues[VarName];
				1497	NamedValues[VarName] = Variable;
				1498
				1499	// Emit the body of the loop. This, like any other expr, can change the
				1500	// current BB. Note that we ignore the value computed by the body, but don't
				1501	// allow an error.
				1502	if (Body->Codegen() == 0)
				1503	return 0;
				1504
				1505	// Emit the step value.
				1506	Value *StepVal;
				1507	if (Step) {
				1508	StepVal = Step->Codegen();
				1509	if (StepVal == 0) return 0;
				1510	} else {
				1511	// If not specified, use 1.0.
				1512	StepVal = ConstantFP::get(Type::DoubleTy, APFloat(1.0));
				1513	}
				1514
				1515	Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
				1516
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	1517	// Compute the end condition.
				1518	Value *EndCond = End->Codegen();
				1519	if (EndCond == 0) return EndCond;
				1520
				1521	// Convert condition to a bool by comparing equal to 0.0.
				1522	EndCond = Builder.CreateFCmpONE(EndCond,
				1523	ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
				1524	"loopcond");
				1525
				1526	// Create the "after loop" block and insert it.
				1527	BasicBlock *LoopEndBB = Builder.GetInsertBlock();
				1528	BasicBlock *AfterBB = new BasicBlock("afterloop", TheFunction);
				1529
				1530	// Insert the conditional branch into the end of LoopEndBB.
				1531	Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
				1532
				1533	// Any new code will be inserted in AfterBB.
				1534	Builder.SetInsertPoint(AfterBB);
				1535
				1536	// Add a new entry to the PHI node for the backedge.
				1537	Variable->addIncoming(NextVar, LoopEndBB);
				1538
				1539	// Restore the unshadowed variable.
				1540	if (OldVal)
				1541	NamedValues[VarName] = OldVal;
				1542	else
				1543	NamedValues.erase(VarName);
				1544
				1545
				1546	// for expr always returns 0.0.
				1547	return Constant::getNullValue(Type::DoubleTy);
				1548	}
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1549
				1550	Function *PrototypeAST::Codegen() {
				1551	// Make the function type: double(double,double) etc.
				1552	std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
				1553	FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
				1554
				1555	Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
				1556
				1557	// If F conflicted, there was already something named 'Name'. If it has a
				1558	// body, don't allow redefinition or reextern.
				1559	if (F->getName() != Name) {
				1560	// Delete the one we just made and get the existing one.
				1561	F->eraseFromParent();
				1562	F = TheModule->getFunction(Name);
				1563
				1564	// If F already has a body, reject this.
				1565	if (!F->empty()) {
				1566	ErrorF("redefinition of function");
				1567	return 0;
				1568	}
				1569
				1570	// If F took a different number of args, reject.
				1571	if (F->arg_size() != Args.size()) {
				1572	ErrorF("redefinition of function with different # args");
				1573	return 0;
				1574	}
				1575	}
				1576
				1577	// Set names for all arguments.
				1578	unsigned Idx = 0;
				1579	for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
				1580	++AI, ++Idx) {
				1581	AI->setName(Args[Idx]);
				1582
				1583	// Add arguments to variable symbol table.
				1584	NamedValues[Args[Idx]] = AI;
				1585	}
				1586
				1587	return F;
				1588	}
				1589
				1590	Function *FunctionAST::Codegen() {
				1591	NamedValues.clear();
				1592
				1593	Function *TheFunction = Proto->Codegen();
				1594	if (TheFunction == 0)
				1595	return 0;
				1596
				1597	// Create a new basic block to start insertion into.
				1598	BasicBlock *BB = new BasicBlock("entry", TheFunction);
				1599	Builder.SetInsertPoint(BB);
				1600
				1601	if (Value *RetVal = Body->Codegen()) {
				1602	// Finish off the function.
				1603	Builder.CreateRet(RetVal);
				1604
				1605	// Validate the generated code, checking for consistency.
				1606	verifyFunction(*TheFunction);
				1607
				1608	// Optimize the function.
				1609	TheFPM->run(*TheFunction);
				1610
				1611	return TheFunction;
				1612	}
				1613
				1614	// Error reading body, remove function.
				1615	TheFunction->eraseFromParent();
				1616	return 0;
				1617	}
				1618
				1619	//===----------------------------------------------------------------------===//
				1620	// Top-Level parsing and JIT Driver
				1621	//===----------------------------------------------------------------------===//
				1622
				1623	static ExecutionEngine *TheExecutionEngine;
				1624
				1625	static void HandleDefinition() {
				1626	if (FunctionAST *F = ParseDefinition()) {
				1627	if (Function *LF = F->Codegen()) {
				1628	fprintf(stderr, "Read function definition:");
				1629	LF->dump();
				1630	}
				1631	} else {
				1632	// Skip token for error recovery.
				1633	getNextToken();
				1634	}
				1635	}
				1636
				1637	static void HandleExtern() {
				1638	if (PrototypeAST *P = ParseExtern()) {
				1639	if (Function *F = P->Codegen()) {
				1640	fprintf(stderr, "Read extern: ");
				1641	F->dump();
				1642	}
				1643	} else {
				1644	// Skip token for error recovery.
				1645	getNextToken();
				1646	}
				1647	}
				1648
				1649	static void HandleTopLevelExpression() {
				1650	// Evaluate a top level expression into an anonymous function.
				1651	if (FunctionAST *F = ParseTopLevelExpr()) {
				1652	if (Function *LF = F->Codegen()) {
				1653	// JIT the function, returning a function pointer.
				1654	void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
				1655
				1656	// Cast it to the right type (takes no arguments, returns a double) so we
				1657	// can call it as a native function.
				1658	double (FP)() = (double ()())FPtr;
				1659	fprintf(stderr, "Evaluated to %f\n", FP());
				1660	}
				1661	} else {
				1662	// Skip token for error recovery.
				1663	getNextToken();
				1664	}
				1665	}
				1666
				1667	/// top ::= definition \| external \| expression \| ';'
				1668	static void MainLoop() {
				1669	while (1) {
				1670	fprintf(stderr, "ready> ");
				1671	switch (CurTok) {
				1672	case tok_eof: return;
				1673	case ';': getNextToken(); break; // ignore top level semicolons.
				1674	case tok_def: HandleDefinition(); break;
				1675	case tok_extern: HandleExtern(); break;
				1676	default: HandleTopLevelExpression(); break;
				1677	}
				1678	}
				1679	}
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	1680
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1681
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1682
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1683	//===----------------------------------------------------------------------===//
				1684	// "Library" functions that can be "extern'd" from user code.
				1685	//===----------------------------------------------------------------------===//
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1686
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1687	/// putchard - putchar that takes a double and returns 0.
				1688	extern "C"
				1689	double putchard(double X) {
				1690	putchar((char)X);
				1691	return 0;
				1692	}
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1693
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1694	//===----------------------------------------------------------------------===//
				1695	// Main driver code.
				1696	//===----------------------------------------------------------------------===//
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1697
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1698	int main() {
				1699	// Install standard binary operators.
				1700	// 1 is lowest precedence.
				1701	BinopPrecedence['<'] = 10;
				1702	BinopPrecedence['+'] = 20;
				1703	BinopPrecedence['-'] = 20;
				1704	BinopPrecedence['*'] = 40; // highest.
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1705
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1706	// Prime the first token.
				1707	fprintf(stderr, "ready> ");
				1708	getNextToken();
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1709
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1710	// Make the module, which holds all the code.
				1711	TheModule = new Module("my cool jit");
				1712
				1713	// Create the JIT.
				1714	TheExecutionEngine = ExecutionEngine::create(TheModule);
				1715
				1716	{
				1717	ExistingModuleProvider OurModuleProvider(TheModule);
				1718	FunctionPassManager OurFPM(&OurModuleProvider);
				1719
				1720	// Set up the optimizer pipeline. Start with registering info about how the
				1721	// target lays out data structures.
				1722	OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
				1723	// Do simple "peephole" optimizations and bit-twiddling optzns.
				1724	OurFPM.add(createInstructionCombiningPass());
				1725	// Reassociate expressions.
				1726	OurFPM.add(createReassociatePass());
				1727	// Eliminate Common SubExpressions.
				1728	OurFPM.add(createGVNPass());
				1729	// Simplify the control flow graph (deleting unreachable blocks, etc).
				1730	OurFPM.add(createCFGSimplificationPass());
				1731	// Set the global so the code gen can use this.
				1732	TheFPM = &OurFPM;
				1733
				1734	// Run the main "interpreter loop" now.
				1735	MainLoop();
				1736
				1737	TheFPM = 0;
				1738	} // Free module provider and pass manager.
				1739
				1740
				1741	// Print out all of the generated code.
				1742	TheModule->dump();
				1743	return 0;
				1744	}
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1745	</pre>
				1746	</div>
				1747
				1748	</div>
				1749
				1750	<!-- *********************************************************************** -->
				1751	<hr>
				1752	<address>
				1753	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				1754	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				1755	<a href="http://validator.w3.org/check/referer"><img
				1756	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
				1757
				1758	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1759	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				1760	Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
				1761	</address>
				1762	</body>
				1763	</html>