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

blob: 837815a77ddc823d2eb558d1e9aa7121d1425b80 [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	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	58	Kaleidoscope language and included support for generating LLVM IR, following by
				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>
				74	Extending Kaleidoscope to support if/then/else is quite straight-forward. It
				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
				80	<p>Before we get going on "how" we do this extension, lets talk about what we
				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
				100	<p>The semantics of the if/then/else expression is that it first 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
				108	<p>Now that we know what we want, lets break this down into its constituent
				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
				121	<p>The lexer extensions are straight-forward. First we add new enum values
				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
				131	<p>Once we have that, we recognize the new keywords in the lexer, pretty simple
				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
				182	AST node to build, our parsing logic is relatively straight-forward. First we
				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
				299	<p>Coming back to the generated code, it is fairly simple: the entry block
				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
				306	<p>Once the then/else blocks is 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	7115521	2007-11-06 01:39:12 +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
				328	sorts of values that float around in code written in your average imperative
				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>
				333	<li>Values that are implicit in the structure of your AST, such as the phi node
				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
				340	handle them. 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
				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
				372	<p>This code is straight-forward and similar to what we saw before. We emit the
				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
				398	automatically insert the new block onto the end of the specified function. The
				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
				430	from the AST. To finish off the then block, we create an unconditional branch
				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	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	442	then are we getting the current block when we just set it to ThenBB 5 lines
				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
				495	<p>Overall, we now have the ability to execution conditional code in
				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
				574	<p>The AST node is similarly 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	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	707	<p>The first part of codegen is very simple: we just output the start expression
				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
				807	variable by adding the step value or 1.0 if it isn't present. '<tt>NextVar</tt>'
				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
				842	the control flow for it. This remembers the end block (for the phi node), then
				843	creates the block for the loop exit ("afterloop"). Based on the value of the
				844	exit condition, it creates a conditional branch that chooses between executing
				845	the loop again and exiting the loop. Any future code is emitted in the
				846	"afterloop" block, so it sets the insertion position to it.</p>
				847
				848	<div class="doc_code">
				849	<pre>
				850	// Add a new entry to the PHI node for the backedge.
				851	Variable->addIncoming(NextVar, LoopEndBB);
				852
				853	// Restore the unshadowed variable.
				854	if (OldVal)
				855	NamedValues[VarName] = OldVal;
				856	else
				857	NamedValues.erase(VarName);
				858
				859	// for expr always returns 0.0.
				860	return Constant::getNullValue(Type::DoubleTy);
				861	}
				862	</pre>
				863	</div>
				864
				865	<p>The final code handles various cleanups: now that we have the "NextVar"
				866	value, we can add the incoming value to the loop PHI node. After that, we
				867	remove the loop variable from the symbol table, so that it isn't in scope after
				868	the for loop. Finally, code generation of the for loop always returns 0.0, so
				869	that is what we return from <tt>ForExprAST::Codegen</tt>.</p>
				870
				871	<p>With this, we conclude the "adding control flow to Kaleidoscope" chapter of
				872	the tutorial. We added two control flow constructs, and used them to motivate
				873	a couple of aspects of the LLVM IR that are important for front-end implementors
				874	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]	875	<a href="LangImpl6.html">user-defined operators</a> to our poor innocent
				876	language.</p>
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	877
				878	</div>
				879
				880	<!-- *********************************************************************** -->
				881	<div class="doc_section"><a name="code">Full Code Listing</a></div>
				882	<!-- *********************************************************************** -->
				883
				884	<div class="doc_text">
				885
				886	<p>
				887	Here is the complete code listing for our running example, enhanced with the
				888	if/then/else and for expressions.. To build this example, use:
				889	</p>
				890
				891	<div class="doc_code">
				892	<pre>
				893	# Compile
				894	g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
				895	# Run
				896	./toy
				897	</pre>
				898	</div>
				899
				900	<p>Here is the code:</p>
				901
				902	<div class="doc_code">
				903	<pre>
				904	#include "llvm/DerivedTypes.h"
				905	#include "llvm/ExecutionEngine/ExecutionEngine.h"
				906	#include "llvm/Module.h"
				907	#include "llvm/ModuleProvider.h"
				908	#include "llvm/PassManager.h"
				909	#include "llvm/Analysis/Verifier.h"
				910	#include "llvm/Target/TargetData.h"
				911	#include "llvm/Transforms/Scalar.h"
				912	#include "llvm/Support/LLVMBuilder.h"
				913	#include <cstdio>
				914	#include <string>
				915	#include <map>
				916	#include <vector>
				917	using namespace llvm;
				918
				919	//===----------------------------------------------------------------------===//
				920	// Lexer
				921	//===----------------------------------------------------------------------===//
				922
				923	// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
				924	// of these for known things.
				925	enum Token {
				926	tok_eof = -1,
				927
				928	// commands
				929	tok_def = -2, tok_extern = -3,
				930
				931	// primary
				932	tok_identifier = -4, tok_number = -5,
				933
				934	// control
				935	tok_if = -6, tok_then = -7, tok_else = -8,
				936	tok_for = -9, tok_in = -10
				937	};
				938
				939	static std::string IdentifierStr; // Filled in if tok_identifier
				940	static double NumVal; // Filled in if tok_number
				941
				942	/// gettok - Return the next token from standard input.
				943	static int gettok() {
				944	static int LastChar = ' ';
				945
				946	// Skip any whitespace.
				947	while (isspace(LastChar))
				948	LastChar = getchar();
				949
				950	if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
				951	IdentifierStr = LastChar;
				952	while (isalnum((LastChar = getchar())))
				953	IdentifierStr += LastChar;
				954
				955	if (IdentifierStr == "def") return tok_def;
				956	if (IdentifierStr == "extern") return tok_extern;
				957	if (IdentifierStr == "if") return tok_if;
				958	if (IdentifierStr == "then") return tok_then;
				959	if (IdentifierStr == "else") return tok_else;
				960	if (IdentifierStr == "for") return tok_for;
				961	if (IdentifierStr == "in") return tok_in;
				962	return tok_identifier;
				963	}
				964
				965	if (isdigit(LastChar) \|\| LastChar == '.') { // Number: [0-9.]+
				966	std::string NumStr;
				967	do {
				968	NumStr += LastChar;
				969	LastChar = getchar();
				970	} while (isdigit(LastChar) \|\| LastChar == '.');
				971
				972	NumVal = strtod(NumStr.c_str(), 0);
				973	return tok_number;
				974	}
				975
				976	if (LastChar == '#') {
				977	// Comment until end of line.
				978	do LastChar = getchar();
				979	while (LastChar != EOF && LastChar != '\n' & LastChar != '\r');
				980
				981	if (LastChar != EOF)
				982	return gettok();
				983	}
				984
				985	// Check for end of file. Don't eat the EOF.
				986	if (LastChar == EOF)
				987	return tok_eof;
				988
				989	// Otherwise, just return the character as its ascii value.
				990	int ThisChar = LastChar;
				991	LastChar = getchar();
				992	return ThisChar;
				993	}
				994
				995	//===----------------------------------------------------------------------===//
				996	// Abstract Syntax Tree (aka Parse Tree)
				997	//===----------------------------------------------------------------------===//
				998
				999	/// ExprAST - Base class for all expression nodes.
				1000	class ExprAST {
				1001	public:
				1002	virtual ~ExprAST() {}
				1003	virtual Value *Codegen() = 0;
				1004	};
				1005
				1006	/// NumberExprAST - Expression class for numeric literals like "1.0".
				1007	class NumberExprAST : public ExprAST {
				1008	double Val;
				1009	public:
				1010	NumberExprAST(double val) : Val(val) {}
				1011	virtual Value *Codegen();
				1012	};
				1013
				1014	/// VariableExprAST - Expression class for referencing a variable, like "a".
				1015	class VariableExprAST : public ExprAST {
				1016	std::string Name;
				1017	public:
				1018	VariableExprAST(const std::string &name) : Name(name) {}
				1019	virtual Value *Codegen();
				1020	};
				1021
				1022	/// BinaryExprAST - Expression class for a binary operator.
				1023	class BinaryExprAST : public ExprAST {
				1024	char Op;
				1025	ExprAST LHS, RHS;
				1026	public:
				1027	BinaryExprAST(char op, ExprAST lhs, ExprAST rhs)
				1028	: Op(op), LHS(lhs), RHS(rhs) {}
				1029	virtual Value *Codegen();
				1030	};
				1031
				1032	/// CallExprAST - Expression class for function calls.
				1033	class CallExprAST : public ExprAST {
				1034	std::string Callee;
				1035	std::vector<ExprAST*> Args;
				1036	public:
				1037	CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
				1038	: Callee(callee), Args(args) {}
				1039	virtual Value *Codegen();
				1040	};
				1041
				1042	/// IfExprAST - Expression class for if/then/else.
				1043	class IfExprAST : public ExprAST {
				1044	ExprAST Cond, Then, *Else;
				1045	public:
				1046	IfExprAST(ExprAST cond, ExprAST then, ExprAST *_else)
				1047	: Cond(cond), Then(then), Else(_else) {}
				1048	virtual Value *Codegen();
				1049	};
				1050
				1051	/// ForExprAST - Expression class for for/in.
				1052	class ForExprAST : public ExprAST {
				1053	std::string VarName;
				1054	ExprAST Start, End, Step, Body;
				1055	public:
				1056	ForExprAST(const std::string &varname, ExprAST start, ExprAST end,
				1057	ExprAST step, ExprAST body)
				1058	: VarName(varname), Start(start), End(end), Step(step), Body(body) {}
				1059	virtual Value *Codegen();
				1060	};
				1061
				1062	/// PrototypeAST - This class represents the "prototype" for a function,
				1063	/// which captures its argument names as well as if it is an operator.
				1064	class PrototypeAST {
				1065	std::string Name;
				1066	std::vector<std::string> Args;
				1067	public:
				1068	PrototypeAST(const std::string &name, const std::vector<std::string> &args)
				1069	: Name(name), Args(args) {}
				1070
				1071	Function *Codegen();
				1072	};
				1073
				1074	/// FunctionAST - This class represents a function definition itself.
				1075	class FunctionAST {
				1076	PrototypeAST *Proto;
				1077	ExprAST *Body;
				1078	public:
				1079	FunctionAST(PrototypeAST proto, ExprAST body)
				1080	: Proto(proto), Body(body) {}
				1081
				1082	Function *Codegen();
				1083	};
				1084
				1085	//===----------------------------------------------------------------------===//
				1086	// Parser
				1087	//===----------------------------------------------------------------------===//
				1088
				1089	/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
				1090	/// token the parser it looking at. getNextToken reads another token from the
				1091	/// lexer and updates CurTok with its results.
				1092	static int CurTok;
				1093	static int getNextToken() {
				1094	return CurTok = gettok();
				1095	}
				1096
				1097	/// BinopPrecedence - This holds the precedence for each binary operator that is
				1098	/// defined.
				1099	static std::map<char, int> BinopPrecedence;
				1100
				1101	/// GetTokPrecedence - Get the precedence of the pending binary operator token.
				1102	static int GetTokPrecedence() {
				1103	if (!isascii(CurTok))
				1104	return -1;
				1105
				1106	// Make sure it's a declared binop.
				1107	int TokPrec = BinopPrecedence[CurTok];
				1108	if (TokPrec <= 0) return -1;
				1109	return TokPrec;
				1110	}
				1111
				1112	/// Error* - These are little helper functions for error handling.
				1113	ExprAST Error(const char Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
				1114	PrototypeAST ErrorP(const char Str) { Error(Str); return 0; }
				1115	FunctionAST ErrorF(const char Str) { Error(Str); return 0; }
				1116
				1117	static ExprAST *ParseExpression();
				1118
				1119	/// identifierexpr
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	1120	/// ::= identifier
				1121	/// ::= identifier '(' expression* ')'
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1122	static ExprAST *ParseIdentifierExpr() {
				1123	std::string IdName = IdentifierStr;
				1124
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	1125	getNextToken(); // eat identifier.
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1126
				1127	if (CurTok != '(') // Simple variable ref.
				1128	return new VariableExprAST(IdName);
				1129
				1130	// Call.
				1131	getNextToken(); // eat (
				1132	std::vector<ExprAST*> Args;
				1133	if (CurTok != ')') {
				1134	while (1) {
				1135	ExprAST *Arg = ParseExpression();
				1136	if (!Arg) return 0;
				1137	Args.push_back(Arg);
				1138
				1139	if (CurTok == ')') break;
				1140
				1141	if (CurTok != ',')
				1142	return Error("Expected ')'");
				1143	getNextToken();
				1144	}
				1145	}
				1146
				1147	// Eat the ')'.
				1148	getNextToken();
				1149
				1150	return new CallExprAST(IdName, Args);
				1151	}
				1152
				1153	/// numberexpr ::= number
				1154	static ExprAST *ParseNumberExpr() {
				1155	ExprAST *Result = new NumberExprAST(NumVal);
				1156	getNextToken(); // consume the number
				1157	return Result;
				1158	}
				1159
				1160	/// parenexpr ::= '(' expression ')'
				1161	static ExprAST *ParseParenExpr() {
				1162	getNextToken(); // eat (.
				1163	ExprAST *V = ParseExpression();
				1164	if (!V) return 0;
				1165
				1166	if (CurTok != ')')
				1167	return Error("expected ')'");
				1168	getNextToken(); // eat ).
				1169	return V;
				1170	}
				1171
				1172	/// ifexpr ::= 'if' expression 'then' expression 'else' expression
				1173	static ExprAST *ParseIfExpr() {
				1174	getNextToken(); // eat the if.
				1175
				1176	// condition.
				1177	ExprAST *Cond = ParseExpression();
				1178	if (!Cond) return 0;
				1179
				1180	if (CurTok != tok_then)
				1181	return Error("expected then");
				1182	getNextToken(); // eat the then
				1183
				1184	ExprAST *Then = ParseExpression();
				1185	if (Then == 0) return 0;
				1186
				1187	if (CurTok != tok_else)
				1188	return Error("expected else");
				1189
				1190	getNextToken();
				1191
				1192	ExprAST *Else = ParseExpression();
				1193	if (!Else) return 0;
				1194
				1195	return new IfExprAST(Cond, Then, Else);
				1196	}
				1197
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	1198	/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1199	static ExprAST *ParseForExpr() {
				1200	getNextToken(); // eat the for.
				1201
				1202	if (CurTok != tok_identifier)
				1203	return Error("expected identifier after for");
				1204
				1205	std::string IdName = IdentifierStr;
Chris Lattner	20a0c80	2007-11-05 17:54:34 +0000	[diff] [blame]	1206	getNextToken(); // eat identifier.
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1207
				1208	if (CurTok != '=')
				1209	return Error("expected '=' after for");
				1210	getNextToken(); // eat '='.
				1211
				1212
				1213	ExprAST *Start = ParseExpression();
				1214	if (Start == 0) return 0;
				1215	if (CurTok != ',')
				1216	return Error("expected ',' after for start value");
				1217	getNextToken();
				1218
				1219	ExprAST *End = ParseExpression();
				1220	if (End == 0) return 0;
				1221
				1222	// The step value is optional.
				1223	ExprAST *Step = 0;
				1224	if (CurTok == ',') {
				1225	getNextToken();
				1226	Step = ParseExpression();
				1227	if (Step == 0) return 0;
				1228	}
				1229
				1230	if (CurTok != tok_in)
				1231	return Error("expected 'in' after for");
				1232	getNextToken(); // eat 'in'.
				1233
				1234	ExprAST *Body = ParseExpression();
				1235	if (Body == 0) return 0;
				1236
				1237	return new ForExprAST(IdName, Start, End, Step, Body);
				1238	}
				1239
				1240
				1241	/// primary
				1242	/// ::= identifierexpr
				1243	/// ::= numberexpr
				1244	/// ::= parenexpr
				1245	/// ::= ifexpr
				1246	/// ::= forexpr
				1247	static ExprAST *ParsePrimary() {
				1248	switch (CurTok) {
				1249	default: return Error("unknown token when expecting an expression");
				1250	case tok_identifier: return ParseIdentifierExpr();
				1251	case tok_number: return ParseNumberExpr();
				1252	case '(': return ParseParenExpr();
				1253	case tok_if: return ParseIfExpr();
				1254	case tok_for: return ParseForExpr();
				1255	}
				1256	}
				1257
				1258	/// binoprhs
				1259	/// ::= ('+' primary)*
				1260	static ExprAST ParseBinOpRHS(int ExprPrec, ExprAST LHS) {
				1261	// If this is a binop, find its precedence.
				1262	while (1) {
				1263	int TokPrec = GetTokPrecedence();
				1264
				1265	// If this is a binop that binds at least as tightly as the current binop,
				1266	// consume it, otherwise we are done.
				1267	if (TokPrec < ExprPrec)
				1268	return LHS;
				1269
				1270	// Okay, we know this is a binop.
				1271	int BinOp = CurTok;
				1272	getNextToken(); // eat binop
				1273
				1274	// Parse the primary expression after the binary operator.
				1275	ExprAST *RHS = ParsePrimary();
				1276	if (!RHS) return 0;
				1277
				1278	// If BinOp binds less tightly with RHS than the operator after RHS, let
				1279	// the pending operator take RHS as its LHS.
				1280	int NextPrec = GetTokPrecedence();
				1281	if (TokPrec < NextPrec) {
				1282	RHS = ParseBinOpRHS(TokPrec+1, RHS);
				1283	if (RHS == 0) return 0;
				1284	}
				1285
				1286	// Merge LHS/RHS.
				1287	LHS = new BinaryExprAST(BinOp, LHS, RHS);
				1288	}
				1289	}
				1290
				1291	/// expression
				1292	/// ::= primary binoprhs
				1293	///
				1294	static ExprAST *ParseExpression() {
				1295	ExprAST *LHS = ParsePrimary();
				1296	if (!LHS) return 0;
				1297
				1298	return ParseBinOpRHS(0, LHS);
				1299	}
				1300
				1301	/// prototype
				1302	/// ::= id '(' id* ')'
				1303	static PrototypeAST *ParsePrototype() {
				1304	if (CurTok != tok_identifier)
				1305	return ErrorP("Expected function name in prototype");
				1306
				1307	std::string FnName = IdentifierStr;
				1308	getNextToken();
				1309
				1310	if (CurTok != '(')
				1311	return ErrorP("Expected '(' in prototype");
				1312
				1313	std::vector<std::string> ArgNames;
				1314	while (getNextToken() == tok_identifier)
				1315	ArgNames.push_back(IdentifierStr);
				1316	if (CurTok != ')')
				1317	return ErrorP("Expected ')' in prototype");
				1318
				1319	// success.
				1320	getNextToken(); // eat ')'.
				1321
				1322	return new PrototypeAST(FnName, ArgNames);
				1323	}
				1324
				1325	/// definition ::= 'def' prototype expression
				1326	static FunctionAST *ParseDefinition() {
				1327	getNextToken(); // eat def.
				1328	PrototypeAST *Proto = ParsePrototype();
				1329	if (Proto == 0) return 0;
				1330
				1331	if (ExprAST *E = ParseExpression())
				1332	return new FunctionAST(Proto, E);
				1333	return 0;
				1334	}
				1335
				1336	/// toplevelexpr ::= expression
				1337	static FunctionAST *ParseTopLevelExpr() {
				1338	if (ExprAST *E = ParseExpression()) {
				1339	// Make an anonymous proto.
				1340	PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
				1341	return new FunctionAST(Proto, E);
				1342	}
				1343	return 0;
				1344	}
				1345
				1346	/// external ::= 'extern' prototype
				1347	static PrototypeAST *ParseExtern() {
				1348	getNextToken(); // eat extern.
				1349	return ParsePrototype();
				1350	}
				1351
				1352	//===----------------------------------------------------------------------===//
				1353	// Code Generation
				1354	//===----------------------------------------------------------------------===//
				1355
				1356	static Module *TheModule;
				1357	static LLVMFoldingBuilder Builder;
				1358	static std::map<std::string, Value*> NamedValues;
				1359	static FunctionPassManager *TheFPM;
				1360
				1361	Value ErrorV(const char Str) { Error(Str); return 0; }
				1362
				1363	Value *NumberExprAST::Codegen() {
				1364	return ConstantFP::get(Type::DoubleTy, APFloat(Val));
				1365	}
				1366
				1367	Value *VariableExprAST::Codegen() {
				1368	// Look this variable up in the function.
				1369	Value *V = NamedValues[Name];
				1370	return V ? V : ErrorV("Unknown variable name");
				1371	}
				1372
				1373	Value *BinaryExprAST::Codegen() {
				1374	Value *L = LHS->Codegen();
				1375	Value *R = RHS->Codegen();
				1376	if (L == 0 \|\| R == 0) return 0;
				1377
				1378	switch (Op) {
				1379	case '+': return Builder.CreateAdd(L, R, "addtmp");
				1380	case '-': return Builder.CreateSub(L, R, "subtmp");
				1381	case '*': return Builder.CreateMul(L, R, "multmp");
				1382	case '<':
Chris Lattner	7115521	2007-11-06 01:39:12 +0000	[diff] [blame]	1383	L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1384	// Convert bool 0/1 to double 0.0 or 1.0
				1385	return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
				1386	default: return ErrorV("invalid binary operator");
				1387	}
				1388	}
				1389
				1390	Value *CallExprAST::Codegen() {
				1391	// Look up the name in the global module table.
				1392	Function *CalleeF = TheModule->getFunction(Callee);
				1393	if (CalleeF == 0)
				1394	return ErrorV("Unknown function referenced");
				1395
				1396	// If argument mismatch error.
				1397	if (CalleeF->arg_size() != Args.size())
				1398	return ErrorV("Incorrect # arguments passed");
				1399
				1400	std::vector<Value*> ArgsV;
				1401	for (unsigned i = 0, e = Args.size(); i != e; ++i) {
				1402	ArgsV.push_back(Args[i]->Codegen());
				1403	if (ArgsV.back() == 0) return 0;
				1404	}
				1405
				1406	return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
				1407	}
				1408
				1409	Value *IfExprAST::Codegen() {
				1410	Value *CondV = Cond->Codegen();
				1411	if (CondV == 0) return 0;
				1412
				1413	// Convert condition to a bool by comparing equal to 0.0.
				1414	CondV = Builder.CreateFCmpONE(CondV,
				1415	ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
				1416	"ifcond");
				1417
				1418	Function *TheFunction = Builder.GetInsertBlock()->getParent();
				1419
				1420	// Create blocks for the then and else cases. Insert the 'then' block at the
				1421	// end of the function.
				1422	BasicBlock *ThenBB = new BasicBlock("then", TheFunction);
				1423	BasicBlock *ElseBB = new BasicBlock("else");
				1424	BasicBlock *MergeBB = new BasicBlock("ifcont");
				1425
				1426	Builder.CreateCondBr(CondV, ThenBB, ElseBB);
				1427
				1428	// Emit then value.
				1429	Builder.SetInsertPoint(ThenBB);
				1430
				1431	Value *ThenV = Then->Codegen();
				1432	if (ThenV == 0) return 0;
				1433
				1434	Builder.CreateBr(MergeBB);
				1435	// Codegen of 'Then' can change the current block, update ThenBB for the PHI.
				1436	ThenBB = Builder.GetInsertBlock();
				1437
				1438	// Emit else block.
				1439	TheFunction->getBasicBlockList().push_back(ElseBB);
				1440	Builder.SetInsertPoint(ElseBB);
				1441
				1442	Value *ElseV = Else->Codegen();
				1443	if (ElseV == 0) return 0;
				1444
				1445	Builder.CreateBr(MergeBB);
				1446	// Codegen of 'Else' can change the current block, update ElseBB for the PHI.
				1447	ElseBB = Builder.GetInsertBlock();
				1448
				1449	// Emit merge block.
				1450	TheFunction->getBasicBlockList().push_back(MergeBB);
				1451	Builder.SetInsertPoint(MergeBB);
				1452	PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
				1453
				1454	PN->addIncoming(ThenV, ThenBB);
				1455	PN->addIncoming(ElseV, ElseBB);
				1456	return PN;
				1457	}
				1458
				1459	Value *ForExprAST::Codegen() {
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	1460	// Output this as:
				1461	// ...
				1462	// start = startexpr
				1463	// goto loop
				1464	// loop:
				1465	// variable = phi [start, loopheader], [nextvariable, loopend]
				1466	// ...
				1467	// bodyexpr
				1468	// ...
				1469	// loopend:
				1470	// step = stepexpr
				1471	// nextvariable = variable + step
				1472	// endcond = endexpr
				1473	// br endcond, loop, endloop
				1474	// outloop:
				1475
				1476	// Emit the start code first, without 'variable' in scope.
				1477	Value *StartVal = Start->Codegen();
				1478	if (StartVal == 0) return 0;
				1479
				1480	// Make the new basic block for the loop header, inserting after current
				1481	// block.
				1482	Function *TheFunction = Builder.GetInsertBlock()->getParent();
				1483	BasicBlock *PreheaderBB = Builder.GetInsertBlock();
				1484	BasicBlock *LoopBB = new BasicBlock("loop", TheFunction);
				1485
				1486	// Insert an explicit fall through from the current block to the LoopBB.
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	1487	Builder.CreateBr(LoopBB);
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1488
				1489	// Start insertion in LoopBB.
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	1490	Builder.SetInsertPoint(LoopBB);
				1491
				1492	// Start the PHI node with an entry for Start.
				1493	PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
				1494	Variable->addIncoming(StartVal, PreheaderBB);
				1495
				1496	// Within the loop, the variable is defined equal to the PHI node. If it
				1497	// shadows an existing variable, we have to restore it, so save it now.
				1498	Value *OldVal = NamedValues[VarName];
				1499	NamedValues[VarName] = Variable;
				1500
				1501	// Emit the body of the loop. This, like any other expr, can change the
				1502	// current BB. Note that we ignore the value computed by the body, but don't
				1503	// allow an error.
				1504	if (Body->Codegen() == 0)
				1505	return 0;
				1506
				1507	// Emit the step value.
				1508	Value *StepVal;
				1509	if (Step) {
				1510	StepVal = Step->Codegen();
				1511	if (StepVal == 0) return 0;
				1512	} else {
				1513	// If not specified, use 1.0.
				1514	StepVal = ConstantFP::get(Type::DoubleTy, APFloat(1.0));
				1515	}
				1516
				1517	Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
				1518
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	1519	// Compute the end condition.
				1520	Value *EndCond = End->Codegen();
				1521	if (EndCond == 0) return EndCond;
				1522
				1523	// Convert condition to a bool by comparing equal to 0.0.
				1524	EndCond = Builder.CreateFCmpONE(EndCond,
				1525	ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
				1526	"loopcond");
				1527
				1528	// Create the "after loop" block and insert it.
				1529	BasicBlock *LoopEndBB = Builder.GetInsertBlock();
				1530	BasicBlock *AfterBB = new BasicBlock("afterloop", TheFunction);
				1531
				1532	// Insert the conditional branch into the end of LoopEndBB.
				1533	Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
				1534
				1535	// Any new code will be inserted in AfterBB.
				1536	Builder.SetInsertPoint(AfterBB);
				1537
				1538	// Add a new entry to the PHI node for the backedge.
				1539	Variable->addIncoming(NextVar, LoopEndBB);
				1540
				1541	// Restore the unshadowed variable.
				1542	if (OldVal)
				1543	NamedValues[VarName] = OldVal;
				1544	else
				1545	NamedValues.erase(VarName);
				1546
				1547
				1548	// for expr always returns 0.0.
				1549	return Constant::getNullValue(Type::DoubleTy);
				1550	}
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1551
				1552	Function *PrototypeAST::Codegen() {
				1553	// Make the function type: double(double,double) etc.
				1554	std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
				1555	FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
				1556
				1557	Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
				1558
				1559	// If F conflicted, there was already something named 'Name'. If it has a
				1560	// body, don't allow redefinition or reextern.
				1561	if (F->getName() != Name) {
				1562	// Delete the one we just made and get the existing one.
				1563	F->eraseFromParent();
				1564	F = TheModule->getFunction(Name);
				1565
				1566	// If F already has a body, reject this.
				1567	if (!F->empty()) {
				1568	ErrorF("redefinition of function");
				1569	return 0;
				1570	}
				1571
				1572	// If F took a different number of args, reject.
				1573	if (F->arg_size() != Args.size()) {
				1574	ErrorF("redefinition of function with different # args");
				1575	return 0;
				1576	}
				1577	}
				1578
				1579	// Set names for all arguments.
				1580	unsigned Idx = 0;
				1581	for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
				1582	++AI, ++Idx) {
				1583	AI->setName(Args[Idx]);
				1584
				1585	// Add arguments to variable symbol table.
				1586	NamedValues[Args[Idx]] = AI;
				1587	}
				1588
				1589	return F;
				1590	}
				1591
				1592	Function *FunctionAST::Codegen() {
				1593	NamedValues.clear();
				1594
				1595	Function *TheFunction = Proto->Codegen();
				1596	if (TheFunction == 0)
				1597	return 0;
				1598
				1599	// Create a new basic block to start insertion into.
				1600	BasicBlock *BB = new BasicBlock("entry", TheFunction);
				1601	Builder.SetInsertPoint(BB);
				1602
				1603	if (Value *RetVal = Body->Codegen()) {
				1604	// Finish off the function.
				1605	Builder.CreateRet(RetVal);
				1606
				1607	// Validate the generated code, checking for consistency.
				1608	verifyFunction(*TheFunction);
				1609
				1610	// Optimize the function.
				1611	TheFPM->run(*TheFunction);
				1612
				1613	return TheFunction;
				1614	}
				1615
				1616	// Error reading body, remove function.
				1617	TheFunction->eraseFromParent();
				1618	return 0;
				1619	}
				1620
				1621	//===----------------------------------------------------------------------===//
				1622	// Top-Level parsing and JIT Driver
				1623	//===----------------------------------------------------------------------===//
				1624
				1625	static ExecutionEngine *TheExecutionEngine;
				1626
				1627	static void HandleDefinition() {
				1628	if (FunctionAST *F = ParseDefinition()) {
				1629	if (Function *LF = F->Codegen()) {
				1630	fprintf(stderr, "Read function definition:");
				1631	LF->dump();
				1632	}
				1633	} else {
				1634	// Skip token for error recovery.
				1635	getNextToken();
				1636	}
				1637	}
				1638
				1639	static void HandleExtern() {
				1640	if (PrototypeAST *P = ParseExtern()) {
				1641	if (Function *F = P->Codegen()) {
				1642	fprintf(stderr, "Read extern: ");
				1643	F->dump();
				1644	}
				1645	} else {
				1646	// Skip token for error recovery.
				1647	getNextToken();
				1648	}
				1649	}
				1650
				1651	static void HandleTopLevelExpression() {
				1652	// Evaluate a top level expression into an anonymous function.
				1653	if (FunctionAST *F = ParseTopLevelExpr()) {
				1654	if (Function *LF = F->Codegen()) {
				1655	// JIT the function, returning a function pointer.
				1656	void *FPtr = TheExecutionEngine->getPointerToFunction(LF);
				1657
				1658	// Cast it to the right type (takes no arguments, returns a double) so we
				1659	// can call it as a native function.
				1660	double (FP)() = (double ()())FPtr;
				1661	fprintf(stderr, "Evaluated to %f\n", FP());
				1662	}
				1663	} else {
				1664	// Skip token for error recovery.
				1665	getNextToken();
				1666	}
				1667	}
				1668
				1669	/// top ::= definition \| external \| expression \| ';'
				1670	static void MainLoop() {
				1671	while (1) {
				1672	fprintf(stderr, "ready> ");
				1673	switch (CurTok) {
				1674	case tok_eof: return;
				1675	case ';': getNextToken(); break; // ignore top level semicolons.
				1676	case tok_def: HandleDefinition(); break;
				1677	case tok_extern: HandleExtern(); break;
				1678	default: HandleTopLevelExpression(); break;
				1679	}
				1680	}
				1681	}
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame]	1682
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1683
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1684
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1685	//===----------------------------------------------------------------------===//
				1686	// "Library" functions that can be "extern'd" from user code.
				1687	//===----------------------------------------------------------------------===//
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1688
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1689	/// putchard - putchar that takes a double and returns 0.
				1690	extern "C"
				1691	double putchard(double X) {
				1692	putchar((char)X);
				1693	return 0;
				1694	}
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1695
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1696	//===----------------------------------------------------------------------===//
				1697	// Main driver code.
				1698	//===----------------------------------------------------------------------===//
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1699
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1700	int main() {
				1701	// Install standard binary operators.
				1702	// 1 is lowest precedence.
				1703	BinopPrecedence['<'] = 10;
				1704	BinopPrecedence['+'] = 20;
				1705	BinopPrecedence['-'] = 20;
				1706	BinopPrecedence['*'] = 40; // highest.
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1707
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1708	// Prime the first token.
				1709	fprintf(stderr, "ready> ");
				1710	getNextToken();
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1711
Chris Lattner	6093bd5	2007-10-31 07:29:43 +0000	[diff] [blame]	1712	// Make the module, which holds all the code.
				1713	TheModule = new Module("my cool jit");
				1714
				1715	// Create the JIT.
				1716	TheExecutionEngine = ExecutionEngine::create(TheModule);
				1717
				1718	{
				1719	ExistingModuleProvider OurModuleProvider(TheModule);
				1720	FunctionPassManager OurFPM(&OurModuleProvider);
				1721
				1722	// Set up the optimizer pipeline. Start with registering info about how the
				1723	// target lays out data structures.
				1724	OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
				1725	// Do simple "peephole" optimizations and bit-twiddling optzns.
				1726	OurFPM.add(createInstructionCombiningPass());
				1727	// Reassociate expressions.
				1728	OurFPM.add(createReassociatePass());
				1729	// Eliminate Common SubExpressions.
				1730	OurFPM.add(createGVNPass());
				1731	// Simplify the control flow graph (deleting unreachable blocks, etc).
				1732	OurFPM.add(createCFGSimplificationPass());
				1733	// Set the global so the code gen can use this.
				1734	TheFPM = &OurFPM;
				1735
				1736	// Run the main "interpreter loop" now.
				1737	MainLoop();
				1738
				1739	TheFPM = 0;
				1740	} // Free module provider and pass manager.
				1741
				1742
				1743	// Print out all of the generated code.
				1744	TheModule->dump();
				1745	return 0;
				1746	}
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	1747	</pre>
				1748	</div>
				1749
				1750	</div>
				1751
				1752	<!-- *********************************************************************** -->
				1753	<hr>
				1754	<address>
				1755	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				1756	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				1757	<a href="http://validator.w3.org/check/referer"><img
				1758	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
				1759
				1760	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1761	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				1762	Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
				1763	</address>
				1764	</body>
				1765	</html>