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

blob: f54effcd859c4031aa4e33e97e3181d1cefcfbc6 [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
				16	<div class="doc_author">
				17	<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
				18	</div>
				19
				20	<!-- *********************************************************************** -->
				21	<div class="doc_section"><a name="intro">Part 5 Introduction</a></div>
				22	<!-- *********************************************************************** -->
				23
				24	<div class="doc_text">
				25
				26	<p>Welcome to Part 5 of the "<a href="index.html">Implementing a language with
				27	LLVM</a>" tutorial. Parts 1-4 described the implementation of the simple
				28	Kaleidoscope language and included support for generating LLVM IR, following by
				29	optimizations and a JIT compiler. Unfortunately, as presented, Kaleidoscope is
				30	mostly useless: it has no control flow other than call and return. This means
				31	that you can't have conditional branches in the code, significantly limiting its
				32	power. In this episode of "build that compiler", we'll extend Kaleidoscope to
				33	have an if/then/else expression plus a simple looping construct.</p>
				34
				35	</div>
				36
				37	<!-- *********************************************************************** -->
				38	<div class="doc_section"><a name="ifthen">If/Then/Else</a></div>
				39	<!-- *********************************************************************** -->
				40
				41	<div class="doc_text">
				42
				43	<p>
				44	Extending Kaleidoscope to support if/then/else is quite straight-forward. It
				45	basically requires adding lexer support for this "new" concept to the lexer,
				46	parser, AST, and LLVM code emitter. This example is nice, because it shows how
				47	easy it is to "grow" a language over time, incrementally extending it as new
				48	ideas are discovered.</p>
				49
				50	<p>Before we get going on "how" we do this extension, lets talk about what we
				51	want. The basic idea is that we want to be able to write this sort of thing:
				52	</p>
				53
				54	<div class="doc_code">
				55	<pre>
				56	def fib(x)
				57	if x < 3 then
				58	1
				59	else
				60	fib(x-1)+fib(x-2);
				61	</pre>
				62	</div>
				63
				64	<p>In Kaleidoscope, every construct is an expression: there are no statements.
				65	As such, the if/then/else expression needs to return a value like any other.
				66	Since we're using a mostly functional form, we'll have it evaluate its
				67	conditional, then return the 'then' or 'else' value based on how the condition
				68	was resolved. This is very similar to the C "?:" expression.</p>
				69
				70	<p>The semantics of the if/then/else expression is that it first evaluates the
				71	condition to a boolean equality value: 0.0 is false and everything else is true.
				72	If the condition is true, the first subexpression is evaluated and returned, if
				73	the condition is false, the second subexpression is evaluated and returned.
				74	Since Kaleidoscope allows side-effects, this behavior is important to nail down.
				75	</p>
				76
				77	<p>Now that we know what we want, lets break this down into its constituent
				78	pieces.</p>
				79
				80	</div>
				81
				82	<!-- ======================================================================= -->
				83	<div class="doc_subsubsection"><a name="iflexer">Lexer Extensions for
				84	If/Then/Else</a></div>
				85	<!-- ======================================================================= -->
				86
				87
				88	<div class="doc_text">
				89
				90	<p>The lexer extensions are straight-forward. First we add new enum values
				91	for the relevant tokens:</p>
				92
				93	<div class="doc_code">
				94	<pre>
				95	// control
				96	tok_if = -6, tok_then = -7, tok_else = -8,
				97	</pre>
				98	</div>
				99
				100	<p>Once we have that, we recognize the new keywords in the lexer, pretty simple
				101	stuff:</p>
				102
				103	<div class="doc_code">
				104	<pre>
				105	...
				106	if (IdentifierStr == "def") return tok_def;
				107	if (IdentifierStr == "extern") return tok_extern;
				108	<b>if (IdentifierStr == "if") return tok_if;
				109	if (IdentifierStr == "then") return tok_then;
				110	if (IdentifierStr == "else") return tok_else;</b>
				111	return tok_identifier;
				112	</pre>
				113	</div>
				114
				115	</div>
				116
				117	<!-- ======================================================================= -->
				118	<div class="doc_subsubsection"><a name="ifast">AST Extensions for
				119	If/Then/Else </a></div>
				120	<!-- ======================================================================= -->
				121
				122	<div class="doc_text">
				123
				124	<p>To represent the new expression we add a new AST node for it:</p>
				125
				126	<div class="doc_code">
				127	<pre>
				128	/// IfExprAST - Expression class for if/then/else.
				129	class IfExprAST : public ExprAST {
				130	ExprAST Cond, Then, *Else;
				131	public:
				132	IfExprAST(ExprAST cond, ExprAST then, ExprAST *_else)
				133	: Cond(cond), Then(then), Else(_else) {}
				134	virtual Value *Codegen();
				135	};
				136	</pre>
				137	</div>
				138
				139	<p>The AST node just has pointers to the various subexpressions.</p>
				140
				141	</div>
				142
				143	<!-- ======================================================================= -->
				144	<div class="doc_subsubsection"><a name="ifparser">Parser Extensions for
				145	If/Then/Else </a></div>
				146	<!-- ======================================================================= -->
				147
				148	<div class="doc_text">
				149
				150	<p>Now that we have the relevant tokens coming from the lexer and we have the
				151	AST node to build, our parsing logic is relatively straight-forward. First we
				152	define a new parsing function:</p>
				153
				154	<div class="doc_code">
				155	<pre>
				156	/// ifexpr ::= 'if' expression 'then' expression 'else' expression
				157	static ExprAST *ParseIfExpr() {
				158	getNextToken(); // eat the if.
				159
				160	// condition.
				161	ExprAST *Cond = ParseExpression();
				162	if (!Cond) return 0;
				163
				164	if (CurTok != tok_then)
				165	return Error("expected then");
				166	getNextToken(); // eat the then
				167
				168	ExprAST *Then = ParseExpression();
				169	if (Then == 0) return 0;
				170
				171	if (CurTok != tok_else)
				172	return Error("expected else");
				173
				174	getNextToken();
				175
				176	ExprAST *Else = ParseExpression();
				177	if (!Else) return 0;
				178
				179	return new IfExprAST(Cond, Then, Else);
				180	}
				181	</pre>
				182	</div>
				183
				184	<p>Next we hook it up as a primary expression:</p>
				185
				186	<div class="doc_code">
				187	<pre>
				188	static ExprAST *ParsePrimary() {
				189	switch (CurTok) {
				190	default: return Error("unknown token when expecting an expression");
				191	case tok_identifier: return ParseIdentifierExpr();
				192	case tok_number: return ParseNumberExpr();
				193	case '(': return ParseParenExpr();
				194	<b>case tok_if: return ParseIfExpr();</b>
				195	}
				196	}
				197	</pre>
				198	</div>
				199
				200	</div>
				201
				202	<!-- ======================================================================= -->
				203	<div class="doc_subsubsection"><a name="ifir">LLVM IR for If/Then/Else</a></div>
				204	<!-- ======================================================================= -->
				205
				206	<div class="doc_text">
				207
				208	<p>Now that we have it parsing and building the AST, the final piece is adding
				209	LLVM code generation support. This is the most interesting part of the
				210	if/then/else example, because this is where it starts to introduce new concepts.
				211	All of the code above has been described in previous chapters fairly thoroughly.
				212	</p>
				213
				214	<p>To motivate the code we want to produce, lets take a look at a simple
				215	example. Consider:</p>
				216
				217	<div class="doc_code">
				218	<pre>
				219	extern foo();
				220	extern bar();
				221	def baz(x) if x then foo() else bar();
				222	</pre>
				223	</div>
				224
				225	<p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
				226	looks like this:</p>
				227
				228	<div class="doc_code">
				229	<pre>
				230	declare double @foo()
				231
				232	declare double @bar()
				233
				234	define double @baz(double %x) {
				235	entry:
				236	%ifcond = fcmp one double %x, 0.000000e+00
				237	br i1 %ifcond, label %then, label %else
				238
				239	then: ; preds = %entry
				240	%calltmp = call double @foo()
				241	br label %ifcont
				242
				243	else: ; preds = %entry
				244	%calltmp1 = call double @bar()
				245	br label %ifcont
				246
				247	ifcont: ; preds = %else, %then
				248	%iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
				249	ret double %iftmp
				250	}
				251	</pre>
				252	</div>
				253
				254	<p>To visualize the control flow graph, you can use a nifty feature of the LLVM
				255	'<a href="http://llvm.org/cmds/opt.html">opt</a>' tool. If you put this LLVM IR
				256	into "t.ll" and run "<tt>llvm-as < t.ll \| opt -analyze -view-cfg</tt>", <a
				257	href="../ProgrammersManual.html#ViewGraph">a window will pop up</a> and you'll
				258	see this graph:</p>
				259
				260	<center><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
				261	height="315"></center>
				262
				263	<p>Another way to get this is to call "<tt>F->viewCFG()</tt>" or
				264	"<tt>F->viewCFGOnly()</tt>" (where F is a "<tt>Function*</tt>") either by
				265	inserting actual calls into the code and recompiling or by calling these in the
				266	debugger. LLVM has many nice features for visualizing various graphs.</p>
				267
				268	<p>Coming back to the generated code, it is fairly simple: the entry block
				269	evaluates the conditional expression ("x" in our case here) and compares the
				270	result to 0.0 with the "<tt><a href="../LangRef.html#i_fcmp">fcmp</a> one</tt>"
				271	instruction ('one' is "ordered and not equal"). Based on the result of this
				272	expression, the code jumps to either the "then" or "else" blocks, which contain
				273	the expressions for the true/false case.</p>
				274
				275	<p>Once the then/else blocks is finished executing, they both branch back to the
				276	else block to execute the code that happens after the if/then/else. In this
				277	case the only thing left to do is to return to the caller of the function. The
				278	question then becomes: how does the code know which expression to return?</p>
				279
				280	<p>The answer to this question involves an important SSA operation: the
				281	<a href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Phi
				282	operation</a>. If you're not familiar with SSA, <a
				283	href="http://en.wikipedia.org/wiki/Static_single_assignment_form">the wikipedia
				284	article</a> is a good introduction and there are various other introductions to
				285	it available on your favorite search engine. The short version is that
				286	"execution" of the Phi operation requires "remembering" which block control came
				287	from. The Phi operation takes on the value corresponding to the input control
				288	block. In this case, if control comes in from the "then" block, it gets the
				289	value of "calltmp". If control comes from the "else" block, it gets the value
				290	of "calltmp1".</p>
				291
				292	<p>At this point, you are probably starting to think "on no! this means my
				293	simple and elegant front-end will have to start generating SSA form in order to
				294	use LLVM!". Fortunately, this is not the case, and we strongly advise
				295	<em>not</em> implementing an SSA construction algorithm in your front-end
				296	unless there is an amazingly good reason to do so. In practice, there are two
				297	sorts of values that float around in code written in your average imperative
				298	programming language that might need Phi nodes:</p>
				299
				300	<ol>
				301	<li>Code that involves user variables: <tt>x = 1; x = x + 1; </tt></li>
				302	<li>Values that are implicit in the structure of your AST, such as the phi node
				303	in this case.</li>
				304	</ol>
				305
				306	<p>At a future point in this tutorial ("mutable variables"), we'll talk about #1
				307	in depth. For now, just believe me that you don't need SSA construction to
				308	handle them. For #2, you have the choice of using the techniques that we will
				309	describe for #1, or you can insert Phi nodes directly if convenient. In this
				310	case, it is really really easy to generate the Phi node, so we choose to do it
				311	directly.</p>
				312
				313	<p>Okay, enough of the motivation and overview, lets generate code!</p>
				314
				315	</div>
				316
				317	<!-- ======================================================================= -->
				318	<div class="doc_subsubsection"><a name="ifcodegen">Code Generation for
				319	If/Then/Else</a></div>
				320	<!-- ======================================================================= -->
				321
				322	<div class="doc_text">
				323
				324	<p>In order to generate code for this, we implement the <tt>Codegen</tt> method
				325	for <tt>IfExprAST</tt>:</p>
				326
				327	<div class="doc_code">
				328	<pre>
				329	Value *IfExprAST::Codegen() {
				330	Value *CondV = Cond->Codegen();
				331	if (CondV == 0) return 0;
				332
				333	// Convert condition to a bool by comparing equal to 0.0.
				334	CondV = Builder.CreateFCmpONE(CondV,
				335	ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
				336	"ifcond");
				337	</pre>
				338	</div>
				339
				340	<p>This code is straight-forward and similar to what we saw before. We emit the
				341	expression for the condition, then compare that value to zero to get a truth
				342	value as a 1-bit (bool) value.</p>
				343
				344	<div class="doc_code">
				345	<pre>
				346	Function *TheFunction = Builder.GetInsertBlock()->getParent();
				347
				348	// Create blocks for the then and else cases. Insert the 'then' block at the
				349	// end of the function.
				350	BasicBlock *ThenBB = new BasicBlock("then", TheFunction);
				351	BasicBlock *ElseBB = new BasicBlock("else");
				352	BasicBlock *MergeBB = new BasicBlock("ifcont");
				353
				354	Builder.CreateCondBr(CondV, ThenBB, ElseBB);
				355	</pre>
				356	</div>
				357
				358	<p>This code creates the basic blocks that are related to the if/then/else
				359	statement, and correspond directly to the blocks in the example above. The
				360	first line of this gets the current Function object that is being built. It
				361	gets this by asking the builder for the current BasicBlock, and asking that
				362	block for its "parent" (the function it is currently embedded into).</p>
				363
				364	<p>Once it has that, it creates three blocks. Note that it passes "TheFunction"
				365	into the constructor for the "then" block. This causes the constructor to
				366	automatically insert the new block onto the end of the specified function. The
				367	other two blocks are created, but aren't yet inserted into the function.</p>
				368
				369	<p>Once the blocks are created, we can emit the conditional branch that chooses
				370	between them. Note that creating new blocks does not implicitly affect the
				371	LLVMBuilder, so it is still inserting into the block that the condition
				372	went into. Also note that it is creating a branch to the "then" block and the
				373	"else" block, even though the "else" block isn't inserted into the function yet.
				374	This is all ok: it is the standard way that LLVM supports forward
				375	references.</p>
				376
				377	<div class="doc_code">
				378	<pre>
				379	// Emit then value.
				380	Builder.SetInsertPoint(ThenBB);
				381
				382	Value *ThenV = Then->Codegen();
				383	if (ThenV == 0) return 0;
				384
				385	Builder.CreateBr(MergeBB);
				386	// Codegen of 'Then' can change the current block, update ThenBB for the PHI.
				387	ThenBB = Builder.GetInsertBlock();
				388	</pre>
				389	</div>
				390
				391	<p>After the conditional branch is inserted, we move the builder to start
				392	inserting into the "then" block. Strictly speaking, this call moves the
				393	insertion point to be at the end of the specified block. However, since the
				394	"then" block is empty, it also starts out by inserting at the beginning of the
				395	block. :)</p>
				396
				397	<p>Once the insertion point is set, we recursively codegen the "then" expression
				398	from the AST. To finish off the then block, we create an unconditional branch
				399	to the merge block. One interesting (and very important) aspect of the LLVM IR
				400	is that it <a href="../LangRef.html#functionstructure">requires all basic blocks
				401	to be "terminated"</a> with a <a href="../LangRef.html#terminators">control flow
				402	instruction</a> such as return or branch. This means that all control flow,
				403	<em>including fall throughs</em> must be made explicit in the LLVM IR. If you
				404	violate this rule, the verifier will emit an error.</p>
				405
				406	<p>The final line here is quite subtle, but is very important. The basic issue
				407	is that when we create the Phi node in the merge block, we need to set up the
				408	block/value pairs that indicate how the Phi will work. Importantly, the Phi
				409	node expects to have an extry for each predecessor of the block in the CFG. Why
				410	then are we getting the current block when we just set it to ThenBB 5 lines
				411	above? The problem is that the "Then" expression may actually itself change the
				412	block that the Builder is emitting into if, for example, it contains a nested
				413	"if/then/else" expression. Because calling Codegen recursively could
				414	arbitrarily change the notion of the current block, we are required to get an
				415	up-to-date value for code that will set up the Phi node.</p>
				416
				417	<div class="doc_code">
				418	<pre>
				419	// Emit else block.
				420	TheFunction->getBasicBlockList().push_back(ElseBB);
				421	Builder.SetInsertPoint(ElseBB);
				422
				423	Value *ElseV = Else->Codegen();
				424	if (ElseV == 0) return 0;
				425
				426	Builder.CreateBr(MergeBB);
				427	// Codegen of 'Else' can change the current block, update ElseBB for the PHI.
				428	ElseBB = Builder.GetInsertBlock();
				429	</pre>
				430	</div>
				431
				432	<p>Code generation for the 'else' block is basically identical to codegen for
				433	the 'then' block. The only significant difference is the first line, which adds
				434	the 'else' block to the function. Recall previously that the 'else' block was
				435	created, but not added to the function. Now that the 'then' and 'else' blocks
				436	are emitted, we can finish up with the merge code:</p>
				437
				438	<div class="doc_code">
				439	<pre>
				440	// Emit merge block.
				441	TheFunction->getBasicBlockList().push_back(MergeBB);
				442	Builder.SetInsertPoint(MergeBB);
				443	PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
				444
				445	PN->addIncoming(ThenV, ThenBB);
				446	PN->addIncoming(ElseV, ElseBB);
				447	return PN;
				448	}
				449	</pre>
				450	</div>
				451
				452	<p>The first two lines here are now familiar: the first adds the "merge" block
				453	to the Function object (it was previously floating, like the else block above).
				454	The second block changes the insertion point so that newly created code will go
				455	into the "merge" block. Once that is done, we need to create the PHI node and
				456	set up the block/value pairs for the PHI.</p>
				457
				458	<p>Finally, the CodeGen function returns the phi node as the value computed by
				459	the if/then/else expression. In our example above, this returned value will
				460	feed into the code for the top-level function, which will create the return
				461	instruction.</p>
				462
				463	<p>Overall, we now have the ability to execution conditional code in
				464	Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
				465	that can calculate a wide variety of numeric functions. Next up we'll add
				466	another useful expression that is familiar from non-functional languages...</p>
				467
				468	</div>
				469
				470	<!-- *********************************************************************** -->
				471	<div class="doc_section"><a name="for">'for' Loop Expression</a></div>
				472	<!-- *********************************************************************** -->
				473
				474	<div class="doc_text">
				475
Chris Lattner	f523480	2007-10-31 06:47:39 +0000	[diff] [blame^]	476	<p>Now that we know how to add basic control flow constructs to the language,
				477	we have the tools to add more powerful things. Lets add something more
				478	aggressive, a 'for' expression:</p>
				479
				480	<div class="doc_code">
				481	<pre>
				482	# print 100 '*' (ascii 42) characters
				483	extern putchard(char)
				484	for x = 1, x < 100, 1.0 in putchard(42);
				485	</pre>
				486	</div>
				487
				488	<p>This expression defines a new variable ("x" in this case) which iterates from
				489	a starting value, while the condition ("x < 100" in this case) is true,
				490	incrementing by an optional step value ("1.0" in this case). If the step value
				491	is omitted, it defaults to 1.0. While the loop is true, it executes its
				492	body expression. Because we don't have anything better to return, we'll just
				493	define the loop as always returning 0.0. In the future when we have mutable
				494	variables, it will get more useful.</p>
				495
				496	<p>As before, lets talk about the changes that we need to Kaleidoscope to
				497	support this.</p>
				498
				499	</div>
				500
				501	<!-- ======================================================================= -->
				502	<div class="doc_subsubsection"><a name="forlexer">Lexer Extensions for
				503	the 'for' Loop</a></div>
				504	<!-- ======================================================================= -->
				505
				506	<div class="doc_text">
				507
				508	<p>The lexer extensions are the same sort of thing as for if/then/else:</p>
				509
				510	<div class="doc_code">
				511	<pre>
				512	... in enum Token ...
				513	// control
				514	tok_if = -6, tok_then = -7, tok_else = -8,
				515	<b> tok_for = -9, tok_in = -10</b>
				516
				517	... in gettok ...
				518	if (IdentifierStr == "def") return tok_def;
				519	if (IdentifierStr == "extern") return tok_extern;
				520	if (IdentifierStr == "if") return tok_if;
				521	if (IdentifierStr == "then") return tok_then;
				522	if (IdentifierStr == "else") return tok_else;
				523	<b>if (IdentifierStr == "for") return tok_for;
				524	if (IdentifierStr == "in") return tok_in;</b>
				525	return tok_identifier;
				526	</pre>
				527	</div>
				528
				529	</div>
				530
				531	<!-- ======================================================================= -->
				532	<div class="doc_subsubsection"><a name="forast">AST Extensions for
				533	the 'for' Loop</a></div>
				534	<!-- ======================================================================= -->
				535
				536	<div class="doc_text">
				537
				538	<p>The AST node is similarly simple. It basically boils down to capturing
				539	the variable name and the consituent expressions in the node.</p>
				540
				541	<div class="doc_code">
				542	<pre>
				543	/// ForExprAST - Expression class for for/in.
				544	class ForExprAST : public ExprAST {
				545	std::string VarName;
				546	ExprAST Start, End, Step, Body;
				547	public:
				548	ForExprAST(const std::string &varname, ExprAST start, ExprAST end,
				549	ExprAST step, ExprAST body)
				550	: VarName(varname), Start(start), End(end), Step(step), Body(body) {}
				551	virtual Value *Codegen();
				552	};
				553	</pre>
				554	</div>
				555
				556	</div>
				557
				558	<!-- ======================================================================= -->
				559	<div class="doc_subsubsection"><a name="forparser">Parser Extensions for
				560	the 'for' Loop</a></div>
				561	<!-- ======================================================================= -->
				562
				563	<div class="doc_text">
				564
				565	<p>The parser code is also fairly standard. The only interesting thing here is
				566	handling of the optional step value. The parser code handles it by checking to
				567	see if the second comma is present. If not, it sets the step value to null in
				568	the AST node:</p>
				569
				570	<div class="doc_code">
				571	<pre>
				572	/// forexpr ::= 'for' identifer '=' expr ',' expr (',' expr)? 'in' expression
				573	static ExprAST *ParseForExpr() {
				574	getNextToken(); // eat the for.
				575
				576	if (CurTok != tok_identifier)
				577	return Error("expected identifier after for");
				578
				579	std::string IdName = IdentifierStr;
				580	getNextToken(); // eat identifer.
				581
				582	if (CurTok != '=')
				583	return Error("expected '=' after for");
				584	getNextToken(); // eat '='.
				585
				586
				587	ExprAST *Start = ParseExpression();
				588	if (Start == 0) return 0;
				589	if (CurTok != ',')
				590	return Error("expected ',' after for start value");
				591	getNextToken();
				592
				593	ExprAST *End = ParseExpression();
				594	if (End == 0) return 0;
				595
				596	// The step value is optional.
				597	ExprAST *Step = 0;
				598	if (CurTok == ',') {
				599	getNextToken();
				600	Step = ParseExpression();
				601	if (Step == 0) return 0;
				602	}
				603
				604	if (CurTok != tok_in)
				605	return Error("expected 'in' after for");
				606	getNextToken(); // eat 'in'.
				607
				608	ExprAST *Body = ParseExpression();
				609	if (Body == 0) return 0;
				610
				611	return new ForExprAST(IdName, Start, End, Step, Body);
				612	}
				613	</pre>
				614	</div>
				615
				616	</div>
				617
				618	<!-- ======================================================================= -->
				619	<div class="doc_subsubsection"><a name="forir">LLVM IR for
				620	the 'for' Loop</a></div>
				621	<!-- ======================================================================= -->
				622
				623	<div class="doc_text">
				624
				625	<p>Now we get to the good part: the LLVM IR we want to generate for this thing.
				626	</p>
				627
				628
				629
				630	</div>
				631
				632	<!-- ======================================================================= -->
				633	<div class="doc_subsubsection"><a name="forcodegen">Code Generation for
				634	the 'for' Loop</a></div>
				635	<!-- ======================================================================= -->
				636
				637	<div class="doc_text">
				638
				639
				640	<div class="doc_code">
				641	<pre>
				642	Value *ForExprAST::Codegen() {
				643	// Output this as:
				644	// ...
				645	// start = startexpr
				646	// goto loop
				647	// loop:
				648	// variable = phi [start, loopheader], [nextvariable, loopend]
				649	// ...
				650	// bodyexpr
				651	// ...
				652	// loopend:
				653	// step = stepexpr
				654	// nextvariable = variable + step
				655	// endcond = endexpr
				656	// br endcond, loop, endloop
				657	// outloop:
				658
				659	// Emit the start code first, without 'variable' in scope.
				660	Value *StartVal = Start->Codegen();
				661	if (StartVal == 0) return 0;
				662
				663	// Make the new basic block for the loop header, inserting after current
				664	// block.
				665	Function *TheFunction = Builder.GetInsertBlock()->getParent();
				666	BasicBlock *PreheaderBB = Builder.GetInsertBlock();
				667	BasicBlock *LoopBB = new BasicBlock("loop", TheFunction);
				668
				669	// Insert an explicit fall through from the current block to the LoopBB.
				670	// Start insertion in LoopBB.
				671	Builder.CreateBr(LoopBB);
				672	Builder.SetInsertPoint(LoopBB);
				673
				674	// Start the PHI node with an entry for Start.
				675	PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
				676	Variable->addIncoming(StartVal, PreheaderBB);
				677
				678	// Within the loop, the variable is defined equal to the PHI node. If it
				679	// shadows an existing variable, we have to restore it, so save it now.
				680	Value *OldVal = NamedValues[VarName];
				681	NamedValues[VarName] = Variable;
				682
				683	// Emit the body of the loop. This, like any other expr, can change the
				684	// current BB. Note that we ignore the value computed by the body, but don't
				685	// allow an error.
				686	if (Body->Codegen() == 0)
				687	return 0;
				688
				689	// Emit the step value.
				690	Value *StepVal;
				691	if (Step) {
				692	StepVal = Step->Codegen();
				693	if (StepVal == 0) return 0;
				694	} else {
				695	// If not specified, use 1.0.
				696	StepVal = ConstantFP::get(Type::DoubleTy, APFloat(1.0));
				697	}
				698
				699	Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
				700
				701	// When evaluating the end condition, the value of the variable is the
				702	// incremented value.
				703	NamedValues[VarName] = Variable;
				704
				705
				706	// Compute the end condition.
				707	Value *EndCond = End->Codegen();
				708	if (EndCond == 0) return EndCond;
				709
				710	// Convert condition to a bool by comparing equal to 0.0.
				711	EndCond = Builder.CreateFCmpONE(EndCond,
				712	ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
				713	"loopcond");
				714
				715	// Create the "after loop" block and insert it.
				716	BasicBlock *LoopEndBB = Builder.GetInsertBlock();
				717	BasicBlock *AfterBB = new BasicBlock("afterloop", TheFunction);
				718
				719	// Insert the conditional branch into the end of LoopEndBB.
				720	Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
				721
				722	// Any new code will be inserted in AfterBB.
				723	Builder.SetInsertPoint(AfterBB);
				724
				725	// Add a new entry to the PHI node for the backedge.
				726	Variable->addIncoming(NextVar, LoopEndBB);
				727
				728	// Restore the unshadowed variable.
				729	if (OldVal)
				730	NamedValues[VarName] = OldVal;
				731	else
				732	NamedValues.erase(VarName);
				733
				734
				735	// for expr always returns 0.0.
				736	return Constant::getNullValue(Type::DoubleTy);
				737	}
				738	</pre>
				739	</div>
				740
Chris Lattner	602c832c	2007-10-31 06:30:21 +0000	[diff] [blame]	741
				742	</div>
				743
				744	<!-- *********************************************************************** -->
				745	<div class="doc_section"><a name="code">Full Code Listing</a></div>
				746	<!-- *********************************************************************** -->
				747
				748	<div class="doc_text">
				749
				750	<p>
				751	Here is the complete code listing for our running example, enhanced with the
				752	if/then/else and for expressions.. To build this example, use:
				753	</p>
				754
				755	<div class="doc_code">
				756	<pre>
				757	# Compile
				758	g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
				759	# Run
				760	./toy
				761	</pre>
				762	</div>
				763
				764	<p>Here is the code:</p>
				765
				766	<div class="doc_code">
				767	<pre>
				768	...
				769	</pre>
				770	</div>
				771
				772	</div>
				773
				774	<!-- *********************************************************************** -->
				775	<hr>
				776	<address>
				777	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				778	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				779	<a href="http://validator.w3.org/check/referer"><img
				780	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
				781
				782	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				783	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				784	Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
				785	</address>
				786	</body>
				787	</html>