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

blob: 7e3ed0377372f5d24352ed4f0f6eae684efe81ce [file] [log] [blame]

Chris Lattner	2e90204	2007-10-22 07:01:42 +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: Implementing code generation to LLVM IR</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: Code generation to LLVM IR</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 3 Introduction</a></div>
				22	<!-- *********************************************************************** -->
				23
				24	<div class="doc_text">
				25
				26	<p>Welcome to part 3 of the "<a href="index.html">Implementing a language with
				27	LLVM</a>" tutorial. This chapter shows you how to transform the <a
				28	href="LangImpl2.html">Abstract Syntax Tree built in Chapter 2</a> into LLVM IR.
				29	This will teach you a little bit about how LLVM does things, as well as
				30	demonstrate how easy it is to use. It's much more work to build a lexer and
				31	parser than it is to generate LLVM IR code.
				32	</p>
				33
				34	</div>
				35
				36	<!-- *********************************************************************** -->
				37	<div class="doc_section"><a name="basics">Code Generation setup</a></div>
				38	<!-- *********************************************************************** -->
				39
				40	<div class="doc_text">
				41
				42	<p>
				43	In order to generate LLVM IR, we want some simple setup to get started. First,
				44	we define virtual codegen methods in each AST class:</p>
				45
				46	<div class="doc_code">
				47	<pre>
				48	/// ExprAST - Base class for all expression nodes.
				49	class ExprAST {
				50	public:
				51	virtual ~ExprAST() {}
				52	virtual Value *Codegen() = 0;
				53	};
				54
				55	/// NumberExprAST - Expression class for numeric literals like "1.0".
				56	class NumberExprAST : public ExprAST {
				57	double Val;
				58	public:
Chris Lattner	28571ed	2007-10-23 04:27:44 +0000	[diff] [blame]	59	explicit NumberExprAST(double val) : Val(val) {}
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	60	virtual Value *Codegen();
				61	};
				62	...
				63	</pre>
				64	</div>
				65
Chris Lattner	28571ed	2007-10-23 04:27:44 +0000	[diff] [blame]	66	<p>The Codegen() method says to emit IR for that AST node and all things it
				67	depends on, and they all return an LLVM Value object.
				68	"Value" is the class used to represent a "<a
				69	href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single
				70	Assignment (SSA)</a> register" or "SSA value" in LLVM. The most distinct aspect
				71	of SSA values is that their value is computed as the related instruction
				72	executes, and it does not get a new value until (and if) the instruction
				73	re-executes. In order words, there is no way to "change" an SSA value. For
				74	more information, please read up on <a
				75	href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single
				76	Assignment</a> - the concepts are really quite natural once you grok them.</p>
				77
				78	<p>The
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	79	second thing we want is an "Error" method like we used for parser, which will
				80	be used to report errors found during code generation (for example, use of an
				81	undeclared parameter):</p>
				82
				83	<div class="doc_code">
				84	<pre>
				85	Value ErrorV(const char Str) { Error(Str); return 0; }
				86
				87	static Module *TheModule;
				88	static LLVMBuilder Builder;
				89	static std::map<std::string, Value*> NamedValues;
				90	</pre>
				91	</div>
				92
				93	<p>The static variables will be used during code generation. <tt>TheModule</tt>
				94	is the LLVM construct that contains all of the functions and global variables in
				95	a chunk of code. In many ways, it is the top-level structure that the LLVM IR
				96	uses to contain code.</p>
				97
				98	<p>The <tt>Builder</tt> object is a helper object that makes it easy to generate
				99	LLVM instructions. The <tt>Builder</tt> keeps track of the current place to
				100	insert instructions and has methods to create new instructions.</p>
				101
				102	<p>The <tt>NamedValues</tt> map keeps track of which values are defined in the
				103	current scope and what their LLVM representation is. In this form of
				104	Kaleidoscope, the only things that can be referenced are function parameters.
				105	As such, function parameters will be in this map when generating code for their
				106	function body.</p>
				107
				108	<p>
				109	With these basics in place, we can start talking about how to generate code for
				110	each expression. Note that this assumes that the <tt>Builder</tt> has been set
				111	up to generate code <em>into</em> something. For now, we'll assume that this
				112	has already been done, and we'll just use it to emit code.
				113	</p>
				114
				115	</div>
				116
				117	<!-- *********************************************************************** -->
				118	<div class="doc_section"><a name="exprs">Expression Code Generation</a></div>
				119	<!-- *********************************************************************** -->
				120
				121	<div class="doc_text">
				122
				123	<p>Generating LLVM code for expression nodes is very straight-forward: less
				124	than 45 lines of commented code for all four of our expression nodes. First,
				125	we'll do numeric literals:</p>
				126
				127	<div class="doc_code">
				128	<pre>
				129	Value *NumberExprAST::Codegen() {
				130	return ConstantFP::get(Type::DoubleTy, APFloat(Val));
				131	}
				132	</pre>
				133	</div>
				134
Chris Lattner	d3f0cdd	2007-10-23 04:51:30 +0000	[diff] [blame]	135	<p>In the LLVM IR, numeric constants are represented with the
				136	<tt>ConstantFP</tt> class, which holds the numeric value in an <tt>APFloat</tt>
				137	internally (<tt>APFloat</tt> has the capability of holding floating point
				138	constants of <em>A</em>rbitrary <em>P</em>recision). This code basically just
				139	creates and returns a <tt>ConstantFP</tt>. Note that in the LLVM IR
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	140	that constants are all uniqued together and shared. For this reason, the API
Chris Lattner	d3f0cdd	2007-10-23 04:51:30 +0000	[diff] [blame]	141	uses "the foo::get(..)" idiom instead of "new foo(..)" or "foo::create(..).</p>
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	142
				143	<div class="doc_code">
				144	<pre>
				145	Value *VariableExprAST::Codegen() {
				146	// Look this variable up in the function.
				147	Value *V = NamedValues[Name];
				148	return V ? V : ErrorV("Unknown variable name");
				149	}
				150	</pre>
				151	</div>
				152
Chris Lattner	d3f0cdd	2007-10-23 04:51:30 +0000	[diff] [blame]	153	<p>References to variables is also quite simple here. In the simple version
				154	of Kaleidoscope, we assume that the variable has already been emited somewhere
				155	and its value is available. In practice, the only values that can be in the
				156	<tt>NamedValues</tt> map are function arguments. This
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	157	code simply checks to see that the specified name is in the map (if not, an
				158	unknown variable is being referenced) and returns the value for it.</p>
				159
				160	<div class="doc_code">
				161	<pre>
				162	Value *BinaryExprAST::Codegen() {
				163	Value *L = LHS->Codegen();
				164	Value *R = RHS->Codegen();
				165	if (L == 0 \|\| R == 0) return 0;
				166
				167	switch (Op) {
				168	case '+': return Builder.CreateAdd(L, R, "addtmp");
				169	case '-': return Builder.CreateSub(L, R, "subtmp");
				170	case '*': return Builder.CreateMul(L, R, "multmp");
				171	case '<':
				172	L = Builder.CreateFCmpULT(L, R, "multmp");
				173	// Convert bool 0/1 to double 0.0 or 1.0
				174	return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
				175	default: return ErrorV("invalid binary operator");
				176	}
				177	}
				178	</pre>
				179	</div>
				180
Chris Lattner	d3f0cdd	2007-10-23 04:51:30 +0000	[diff] [blame]	181	<p>Binary operators start to get more interesting. The basic idea here is that
				182	we recursively emit code for the left-hand side of the expression, then the
				183	right-hand side, then we compute the result of the binary expression. In this
				184	code, we do a simple switch on the opcode to create the right LLVM instruction.
				185	</p>
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	186
Chris Lattner	d3f0cdd	2007-10-23 04:51:30 +0000	[diff] [blame]	187	<p>In this example, the LLVM builder class is starting to show its value.
				188	Because it knows where to insert the newly created instruction, you just have to
				189	specificy what instruction to create (e.g. with <tt>CreateAdd</tt>), which
				190	operands to use (<tt>L</tt> and <tt>R</tt> here) and optionally provide a name
				191	for the generated instruction. One nice thing about LLVM is that the name is
				192	just a hint: if there are multiple additions in a single function, the first
				193	will be named "addtmp" and the second will be "autorenamed" by adding a suffix,
				194	giving it a name like "addtmp42". Local value names for instructions are purely
				195	optional, but it makes it much easier to read the IR dumps.</p>
				196
				197	<p><a href="../LangRef.html#instref">LLVM instructions</a> are constrained to
				198	have very strict type properties: for example, the Left and Right operators of
				199	an <a href="../LangRef.html#i_add">add instruction</a> have to have the same
				200	type, and that the result of the add matches the operands. Because all values
				201	in Kaleidoscope are doubles, this makes for very simple code for add, sub and
				202	mul.</p>
				203
				204	<p>On the other hand, LLVM specifies that the <a
				205	href="../LangRef.html#i_fcmp">fcmp instruction</a> always returns an 'i1' value
				206	(a one bit integer). However, Kaleidoscope wants the value to be a 0.0 or 1.0
				207	value. In order to get these semantics, we combine the fcmp instruction with
				208	a <a href="../LangRef.html#i_uitofp">uitofp instruction</a>. This instruction
				209	converts its input integer into a floating point value by treating the input
				210	as an unsigned value. In contrast, if we used the <a
				211	href="../LangRef.html#i_sitofp">sitofp instruction</a>, the Kaleidoscope '<'
				212	operator would return 0.0 and -1.0, depending on the input value.</p>
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	213
				214	<div class="doc_code">
				215	<pre>
				216	Value *CallExprAST::Codegen() {
				217	// Look up the name in the global module table.
				218	Function *CalleeF = TheModule->getFunction(Callee);
				219	if (CalleeF == 0)
				220	return ErrorV("Unknown function referenced");
				221
				222	// If argument mismatch error.
				223	if (CalleeF->arg_size() != Args.size())
				224	return ErrorV("Incorrect # arguments passed");
				225
				226	std::vector<Value*> ArgsV;
				227	for (unsigned i = 0, e = Args.size(); i != e; ++i) {
				228	ArgsV.push_back(Args[i]->Codegen());
				229	if (ArgsV.back() == 0) return 0;
				230	}
				231
				232	return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
				233	}
				234	</pre>
				235	</div>
				236
Chris Lattner	d3f0cdd	2007-10-23 04:51:30 +0000	[diff] [blame]	237	<p>Code generation for function calls is quite straight-forward with LLVM. The
				238	code above first looks the name of the function up in the LLVM Module's symbol
				239	table. Recall that the LLVM Module is the container that holds all of the
				240	functions we are JIT'ing. By giving each function the same name as what the
				241	user specifies, we can use the LLVM symbol table to resolve function names for
				242	us.</p>
				243
				244	<p>Once we have the function to call, we recursively codegen each argument that
				245	is to be passed in, and create an LLVM <a href="../LangRef.html#i_call">call
				246	instruction</a>. Note that LLVM uses the native C calling conventions by
				247	default, allowing these calls to call into standard library functions like
				248	"sin" and "cos" with no additional effort.</p>
				249
				250	<p>This wraps up our handling of the four basic expressions that we have so far
				251	in Kaleidoscope. Feel free to go in and add some more. For example, by
				252	browsing the <a href="../LangRef.html">LLVM language reference</a> you'll find
				253	several other interesting instructions that are really easy to plug into our
				254	basic framework.</p>
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	255
				256	</div>
				257
				258	<!-- *********************************************************************** -->
Chris Lattner	35abbf5	2007-10-23 06:23:57 +0000	[diff] [blame]	259	<div class="doc_section"><a name="funcs">Function Code Generation</a></div>
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	260	<!-- *********************************************************************** -->
				261
				262	<div class="doc_text">
				263
Chris Lattner	35abbf5	2007-10-23 06:23:57 +0000	[diff] [blame]	264	<p>Code generation for prototypes and functions has to handle a number of
				265	details, which make their code less beautiful and elegant than expression code
				266	generation, but they illustrate some important points. First, lets talk about
				267	code generation for prototypes: this is used both for function bodies as well
				268	as external function declarations. The code starts with:</p>
				269
				270	<div class="doc_code">
				271	<pre>
				272	Function *PrototypeAST::Codegen() {
				273	// Make the function type: double(double,double) etc.
				274	std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
				275	FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
				276
				277	Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
				278	</pre>
				279	</div>
				280
				281	<p>This code packs a lot of power into a few lines. The first step is to create
				282	the <tt>FunctionType</tt> that should be used for a given Prototype. Since all
				283	function arguments in Kaleidoscope are of type double, the first line creates
				284	a vector of "N" LLVM Double types. It then uses the <tt>FunctionType::get</tt>
				285	method to create a function type that takes "N" doubles as arguments, returns
				286	one double as a result, and that is not vararg (the false parameter indicates
				287	this). Note that Types in LLVM are uniqued just like Constants are, so you
				288	don't "new" a type, you "get" it.</p>
				289
				290	<p>The final line above actually creates the function that the prototype will
				291	correspond to. This indicates which type, linkage, and name to use, and which
				292	module to insert into. "<a href="LangRef.html#linkage">external linkage</a>"
				293	means that the function may be defined outside the current module and/or that it
				294	is callable by functions outside the module. The Name passed in is the name the
				295	user specified: since "<tt>TheModule</tt>" is specified, this name is registered
				296	in "<tt>TheModule</tt>"s symbol table, which is used by the function call code
				297	above.</p>
				298
				299	<div class="doc_code">
				300	<pre>
				301	// If F conflicted, there was already something named 'Name'. If it has a
				302	// body, don't allow redefinition or reextern.
				303	if (F->getName() != Name) {
				304	// Delete the one we just made and get the existing one.
				305	F->eraseFromParent();
				306	F = TheModule->getFunction(Name);
				307	</pre>
				308	</div>
				309
				310	<p>The Module symbol table works just like the Function symbol table when it
				311	comes to name conflicts: if a new function is created with a name was previously
				312	added to the symbol table, it will get implicitly renamed when added to the
				313	Module. The code above exploits this fact to tell if there was a previous
				314	definition of this function.</p>
				315
				316	<p>In Kaleidoscope, I choose to allow redefinitions of functions in two cases:
				317	first, we want to allow 'extern'ing a function more than once, so long as the
				318	prototypes for the externs match (since all arguments have the same type, we
				319	just have to check that the number of arguments match). Second, we want to
				320	allow 'extern'ing a function and then definining a body for it. This is useful
				321	when defining mutually recursive functions.</p>
				322
				323	<p>In order to implement this, the code above first checks to see if there is
				324	a collision on the name of the function. If so, it deletes the function we just
				325	created (by calling <tt>eraseFromParent</tt>) and then calling
				326	<tt>getFunction</tt> to get the existing function with the specified name. Note
				327	that many APIs in LLVM have "erase" forms and "remove" forms. The "remove" form
				328	unlinks the object from its parent (e.g. a Function from a Module) and returns
				329	it. The "erase" form unlinks the object and then deletes it.</p>
				330
				331	<div class="doc_code">
				332	<pre>
				333	// If F already has a body, reject this.
				334	if (!F->empty()) {
				335	ErrorF("redefinition of function");
				336	return 0;
				337	}
				338
				339	// If F took a different number of args, reject.
				340	if (F->arg_size() != Args.size()) {
				341	ErrorF("redefinition of function with different # args");
				342	return 0;
				343	}
				344	}
				345	</pre>
				346	</div>
				347
				348	<p>In order to verify the logic above, we first check to see if the preexisting
				349	function is "empty". In this case, empty means that it has no basic blocks in
				350	it, which means it has no body. If it has no body, this means its a forward
				351	declaration. Since we don't allow anything after a full definition of the
				352	function, the code rejects this case. If the previous reference to a function
				353	was an 'extern', we simply verify that the number of arguments for that
				354	definition and this one match up. If not, we emit an error.</p>
				355
				356	<div class="doc_code">
				357	<pre>
				358	// Set names for all arguments.
				359	unsigned Idx = 0;
				360	for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
				361	++AI, ++Idx) {
				362	AI->setName(Args[Idx]);
				363
				364	// Add arguments to variable symbol table.
				365	NamedValues[Args[Idx]] = AI;
				366	}
				367	return F;
				368	}
				369	</pre>
				370	</div>
				371
				372	<p>The last bit of code for prototypes loops over all of the arguments in the
				373	function, setting the name of the LLVM Argument objects to match and registering
				374	the arguments in the <tt>NamedValues</tt> map for future use by the
				375	<tt>VariableExprAST</tt> AST node. Once this is set up, it returns the Function
				376	object to the caller. Note that we don't check for conflicting
				377	argument names here (e.g. "extern foo(a b a)"). Doing so would be very
				378	straight-forward.</p>
				379
				380	<div class="doc_code">
				381	<pre>
				382	Function *FunctionAST::Codegen() {
				383	NamedValues.clear();
				384
				385	Function *TheFunction = Proto->Codegen();
				386	if (TheFunction == 0)
				387	return 0;
				388	</pre>
				389	</div>
				390
				391	<p>Code generation for function definitions starts out simply enough: first we
				392	codegen the prototype and verify that it is ok. We also clear out the
				393	<tt>NamedValues</tt> map to make sure that there isn't anything in it from the
				394	last function we compiled.</p>
				395
				396	<div class="doc_code">
				397	<pre>
				398	// Create a new basic block to start insertion into.
				399	BasicBlock *BB = new BasicBlock("entry", TheFunction);
				400	Builder.SetInsertPoint(BB);
				401
				402	if (Value *RetVal = Body->Codegen()) {
				403	// Finish off the function.
				404	Builder.CreateRet(RetVal);
				405	return TheFunction;
				406	}
				407	</pre>
				408	</div>
				409
				410	<p>Now we get to the point where the <tt>Builder</tt> is set up. The first
				411	line creates a new <a href="http://en.wikipedia.org/wiki/Basic_block">basic
				412	block</a> (named "entry"), which is inserted into <tt>TheFunction</tt>. The
				413	second line then tells the builder that new instructions should be inserted into
				414	the end of the new basic block. Basic blocks in LLVM are an important part
				415	of functions that define the <a
				416	href="http://en.wikipedia.org/wiki/Control_flow_graph">Control Flow Graph</a>.
				417	Since we don't have any control flow, our functions will only contain one
				418	block so far. We'll fix this in a future installment :).</p>
				419
				420	<p>Once the insertion point is set up, we call the <tt>CodeGen()</tt> method for
				421	the root expression of the function. If no error happens, this emits code to
				422	compute the expression into the entry block and returns the value that was
				423	computed. Assuming no error, we then create an LLVM <a
				424	href="../LangRef.html#i_ret">ret instruction</a>. This completes the function,
				425	which is then returned.</p>
				426
				427	<div class="doc_code">
				428	<pre>
				429	// Error reading body, remove function.
				430	TheFunction->eraseFromParent();
				431	return 0;
				432	}
				433	</pre>
				434	</div>
				435
				436	<p>The only piece left here is handling of the error case. For simplicity, we
				437	simply handle this by deleting the function we produced with the
				438	<tt>eraseFromParent</tt> method. This allows the user to redefine a function
				439	that they incorrectly typed in before: if we didn't delete it, it would live in
				440	the symbol table, with a body, preventing future redefinition.</p>
				441
				442	<p>This code does have a bug though. Since the <tt>PrototypeAST::Codegen</tt>
				443	can return a previously defined forward declaration, this can actually delete
				444	a forward declaration. There are a number of ways to fix this bug, see what you
				445	can come up with! Here is a testcase:</p>
				446
				447	<div class="doc_code">
				448	<pre>
				449	extern foo(a b); # ok, defines foo.
				450	def foo(a b) c; # error, 'c' is invalid.
				451	def bar() foo(1, 2); # error, unknown function "foo"
				452	</pre>
				453	</div>
				454
				455	</div>
				456
				457	<!-- *********************************************************************** -->
				458	<div class="doc_section"><a name="driver">Driver Changes and
				459	Closing Thoughts</a></div>
				460	<!-- *********************************************************************** -->
				461
				462	<div class="doc_text">
				463
				464	<p>
				465	For now, code generation to LLVM doesn't really get us much, except that we can
				466	look at the pretty IR calls. The sample code inserts calls to Codegen into the
				467	"<tt>HandleDefinition</tt>", "<tt>HandleExtern</tt>" etc functions, and then
				468	dumps out the LLVM IR. This gives a nice way to look at the LLVM IR for simple
				469	functions. For example:
				470	</p>
				471
				472	<div class="doc_code">
				473	<pre>
				474	ready> <b>4+5</b>;
				475	ready> Read top-level expression:
				476	define double @""() {
				477	entry:
				478	%addtmp = add double 4.000000e+00, 5.000000e+00
				479	ret double %addtmp
				480	}
				481	</pre>
				482	</div>
				483
				484	<p>Note how the parser turns the top-level expression into anonymous functions
				485	for us. This will be handy when we add JIT support in the next chapter. Also
				486	note that the code is very literally transcribed, no optimizations are being
				487	performed. We will add optimizations explicitly in the next chapter.</p>
				488
				489	<div class="doc_code">
				490	<pre>
				491	ready> <b>def foo(a b) aa + 2ab + bb;</b>
				492	ready> Read function definition:
				493	define double @foo(double %a, double %b) {
				494	entry:
				495	%multmp = mul double %a, %a
				496	%multmp1 = mul double 2.000000e+00, %a
				497	%multmp2 = mul double %multmp1, %b
				498	%addtmp = add double %multmp, %multmp2
				499	%multmp3 = mul double %b, %b
				500	%addtmp4 = add double %addtmp, %multmp3
				501	ret double %addtmp4
				502	}
				503	</pre>
				504	</div>
				505
				506	<p>This shows some simple arithmetic. Notice the striking similarity to the
				507	LLVM builder calls that we use to create the instructions.</p>
				508
				509	<div class="doc_code">
				510	<pre>
				511	ready> <b>def bar(a) foo(a, 4.0) + bar(31337);</b>
				512	ready> Read function definition:
				513	define double @bar(double %a) {
				514	entry:
				515	%calltmp = call double @foo( double %a, double 4.000000e+00 )
				516	%calltmp1 = call double @bar( double 3.133700e+04 )
				517	%addtmp = add double %calltmp, %calltmp1
				518	ret double %addtmp
				519	}
				520	</pre>
				521	</div>
				522
				523	<p>This shows some function calls. Note that the runtime of this function might
				524	be fairly high. In the future we'll add conditional control flow to make
				525	recursion actually be useful :).</p>
				526
				527	<div class="doc_code">
				528	<pre>
				529	ready> <b>extern cos(x);</b>
				530	ready> Read extern:
				531	declare double @cos(double)
				532
				533	ready> <b>cos(1.234);</b>
				534	ready> Read top-level expression:
				535	define double @""() {
				536	entry:
Chris Lattner	8eef4b2	2007-10-23 06:30:50 +0000	[diff] [blame]	537	%calltmp = call double @cos( double 1.234000e+00 )
Chris Lattner	35abbf5	2007-10-23 06:23:57 +0000	[diff] [blame]	538	ret double %calltmp
				539	}
				540	</pre>
				541	</div>
				542
				543	<p>This shows an extern for the libm "cos" function, and a call to it.</p>
				544
				545
				546	<div class="doc_code">
				547	<pre>
				548	ready> <b>^D</b>
				549	; ModuleID = 'my cool jit'
				550
				551	define double @""() {
				552	entry:
				553	%addtmp = add double 4.000000e+00, 5.000000e+00
				554	ret double %addtmp
				555	}
				556
				557	define double @foo(double %a, double %b) {
				558	entry:
				559	%multmp = mul double %a, %a
				560	%multmp1 = mul double 2.000000e+00, %a
				561	%multmp2 = mul double %multmp1, %b
				562	%addtmp = add double %multmp, %multmp2
				563	%multmp3 = mul double %b, %b
				564	%addtmp4 = add double %addtmp, %multmp3
				565	ret double %addtmp4
				566	}
				567
				568	define double @bar(double %a) {
				569	entry:
				570	%calltmp = call double @foo( double %a, double 4.000000e+00 )
				571	%calltmp1 = call double @bar( double 3.133700e+04 )
				572	%addtmp = add double %calltmp, %calltmp1
				573	ret double %addtmp
				574	}
				575
				576	declare double @cos(double)
				577
				578	define double @""() {
				579	entry:
				580	%calltmp = call double @cos( double 1.234000e+00 )
				581	ret double %calltmp
				582	}
				583	</pre>
				584	</div>
				585
				586	<p>When you quit the current demo, it dumps out the IR for the entire module
				587	generated. Here you can see the big picture with all the functions referencing
				588	each other.</p>
				589
				590	<p>This wraps up this chapter of the Kaleidoscope tutorial. Up next we'll
				591	describe how to <a href="LangImpl4.html">add JIT codegen and optimizer
				592	support</a> to this so we can actually start running code!</p>
				593
				594	</div>
				595
				596
				597	<!-- *********************************************************************** -->
				598	<div class="doc_section"><a name="code">Full Code Listing</a></div>
				599	<!-- *********************************************************************** -->
				600
				601	<div class="doc_text">
				602
				603	<p>
				604	Here is the complete code listing for our running example, enhanced with the
				605	LLVM code generator. Because this uses the LLVM libraries, we need to link
				606	them in. To do this, we use the <a
				607	href="http://llvm.org/cmds/llvm-config.html">llvm-config</a> tool to inform
				608	our makefile/command line about which options to use:</p>
				609
				610	<div class="doc_code">
				611	<pre>
				612	# Compile
Chris Lattner	9ac0ca0	2007-10-24 05:09:48 +0000	[diff] [blame^]	613	g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core` -o toy
Chris Lattner	35abbf5	2007-10-23 06:23:57 +0000	[diff] [blame]	614	# Run
				615	./toy
				616	</pre>
				617	</div>
				618
				619	<p>Here is the code:</p>
				620
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	621	<div class="doc_code">
				622	<pre>
				623	// To build this:
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	624	// See example below.
				625
				626	#include "llvm/DerivedTypes.h"
				627	#include "llvm/Module.h"
				628	#include "llvm/Support/LLVMBuilder.h"
				629	#include <cstdio>
				630	#include <string>
				631	#include <map>
				632	#include <vector>
				633	using namespace llvm;
				634
				635	//===----------------------------------------------------------------------===//
				636	// Lexer
				637	//===----------------------------------------------------------------------===//
				638
				639	// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
				640	// of these for known things.
				641	enum Token {
				642	tok_eof = -1,
				643
				644	// commands
				645	tok_def = -2, tok_extern = -3,
				646
				647	// primary
				648	tok_identifier = -4, tok_number = -5,
				649	};
				650
				651	static std::string IdentifierStr; // Filled in if tok_identifier
				652	static double NumVal; // Filled in if tok_number
				653
				654	/// gettok - Return the next token from standard input.
				655	static int gettok() {
				656	static int LastChar = ' ';
				657
				658	// Skip any whitespace.
				659	while (isspace(LastChar))
				660	LastChar = getchar();
				661
				662	if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
				663	IdentifierStr = LastChar;
				664	while (isalnum((LastChar = getchar())))
				665	IdentifierStr += LastChar;
				666
				667	if (IdentifierStr == "def") return tok_def;
				668	if (IdentifierStr == "extern") return tok_extern;
				669	return tok_identifier;
				670	}
				671
				672	if (isdigit(LastChar) \|\| LastChar == '.') { // Number: [0-9.]+
				673	std::string NumStr;
				674	do {
				675	NumStr += LastChar;
				676	LastChar = getchar();
				677	} while (isdigit(LastChar) \|\| LastChar == '.');
				678
				679	NumVal = strtod(NumStr.c_str(), 0);
				680	return tok_number;
				681	}
				682
				683	if (LastChar == '#') {
				684	// Comment until end of line.
				685	do LastChar = getchar();
				686	while (LastChar != EOF && LastChar != '\n' & LastChar != '\r');
				687
				688	if (LastChar != EOF)
				689	return gettok();
				690	}
				691
				692	// Check for end of file. Don't eat the EOF.
				693	if (LastChar == EOF)
				694	return tok_eof;
				695
				696	// Otherwise, just return the character as its ascii value.
				697	int ThisChar = LastChar;
				698	LastChar = getchar();
				699	return ThisChar;
				700	}
				701
				702	//===----------------------------------------------------------------------===//
				703	// Abstract Syntax Tree (aka Parse Tree)
				704	//===----------------------------------------------------------------------===//
				705
				706	/// ExprAST - Base class for all expression nodes.
				707	class ExprAST {
				708	public:
				709	virtual ~ExprAST() {}
				710	virtual Value *Codegen() = 0;
				711	};
				712
				713	/// NumberExprAST - Expression class for numeric literals like "1.0".
				714	class NumberExprAST : public ExprAST {
				715	double Val;
				716	public:
Chris Lattner	28571ed	2007-10-23 04:27:44 +0000	[diff] [blame]	717	explicit NumberExprAST(double val) : Val(val) {}
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	718	virtual Value *Codegen();
				719	};
				720
				721	/// VariableExprAST - Expression class for referencing a variable, like "a".
				722	class VariableExprAST : public ExprAST {
				723	std::string Name;
				724	public:
Chris Lattner	28571ed	2007-10-23 04:27:44 +0000	[diff] [blame]	725	explicit VariableExprAST(const std::string &name) : Name(name) {}
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	726	virtual Value *Codegen();
				727	};
				728
				729	/// BinaryExprAST - Expression class for a binary operator.
				730	class BinaryExprAST : public ExprAST {
				731	char Op;
				732	ExprAST LHS, RHS;
				733	public:
				734	BinaryExprAST(char op, ExprAST lhs, ExprAST rhs)
				735	: Op(op), LHS(lhs), RHS(rhs) {}
				736	virtual Value *Codegen();
				737	};
				738
				739	/// CallExprAST - Expression class for function calls.
				740	class CallExprAST : public ExprAST {
				741	std::string Callee;
				742	std::vector<ExprAST*> Args;
				743	public:
				744	CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
				745	: Callee(callee), Args(args) {}
				746	virtual Value *Codegen();
				747	};
				748
				749	/// PrototypeAST - This class represents the "prototype" for a function,
				750	/// which captures its argument names as well as if it is an operator.
				751	class PrototypeAST {
				752	std::string Name;
				753	std::vector<std::string> Args;
				754	public:
				755	PrototypeAST(const std::string &name, const std::vector<std::string> &args)
				756	: Name(name), Args(args) {}
				757
				758	Function *Codegen();
				759	};
				760
				761	/// FunctionAST - This class represents a function definition itself.
				762	class FunctionAST {
				763	PrototypeAST *Proto;
				764	ExprAST *Body;
				765	public:
				766	FunctionAST(PrototypeAST proto, ExprAST body)
				767	: Proto(proto), Body(body) {}
				768
				769	Function *Codegen();
				770	};
				771
				772	//===----------------------------------------------------------------------===//
				773	// Parser
				774	//===----------------------------------------------------------------------===//
				775
				776	/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
				777	/// token the parser it looking at. getNextToken reads another token from the
				778	/// lexer and updates CurTok with its results.
				779	static int CurTok;
				780	static int getNextToken() {
				781	return CurTok = gettok();
				782	}
				783
				784	/// BinopPrecedence - This holds the precedence for each binary operator that is
				785	/// defined.
				786	static std::map<char, int> BinopPrecedence;
				787
				788	/// GetTokPrecedence - Get the precedence of the pending binary operator token.
				789	static int GetTokPrecedence() {
				790	if (!isascii(CurTok))
				791	return -1;
				792
				793	// Make sure it's a declared binop.
				794	int TokPrec = BinopPrecedence[CurTok];
				795	if (TokPrec <= 0) return -1;
				796	return TokPrec;
				797	}
				798
				799	/// Error* - These are little helper functions for error handling.
				800	ExprAST Error(const char Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
				801	PrototypeAST ErrorP(const char Str) { Error(Str); return 0; }
				802	FunctionAST ErrorF(const char Str) { Error(Str); return 0; }
				803
				804	static ExprAST *ParseExpression();
				805
				806	/// identifierexpr
				807	/// ::= identifer
				808	/// ::= identifer '(' expression* ')'
				809	static ExprAST *ParseIdentifierExpr() {
				810	std::string IdName = IdentifierStr;
				811
				812	getNextToken(); // eat identifer.
				813
				814	if (CurTok != '(') // Simple variable ref.
				815	return new VariableExprAST(IdName);
				816
				817	// Call.
				818	getNextToken(); // eat (
				819	std::vector<ExprAST*> Args;
				820	while (1) {
				821	ExprAST *Arg = ParseExpression();
				822	if (!Arg) return 0;
				823	Args.push_back(Arg);
				824
				825	if (CurTok == ')') break;
				826
				827	if (CurTok != ',')
				828	return Error("Expected ')'");
				829	getNextToken();
				830	}
				831
				832	// Eat the ')'.
				833	getNextToken();
				834
				835	return new CallExprAST(IdName, Args);
				836	}
				837
				838	/// numberexpr ::= number
				839	static ExprAST *ParseNumberExpr() {
				840	ExprAST *Result = new NumberExprAST(NumVal);
				841	getNextToken(); // consume the number
				842	return Result;
				843	}
				844
				845	/// parenexpr ::= '(' expression ')'
				846	static ExprAST *ParseParenExpr() {
				847	getNextToken(); // eat (.
				848	ExprAST *V = ParseExpression();
				849	if (!V) return 0;
				850
				851	if (CurTok != ')')
				852	return Error("expected ')'");
				853	getNextToken(); // eat ).
				854	return V;
				855	}
				856
				857	/// primary
				858	/// ::= identifierexpr
				859	/// ::= numberexpr
				860	/// ::= parenexpr
				861	static ExprAST *ParsePrimary() {
				862	switch (CurTok) {
				863	default: return Error("unknown token when expecting an expression");
				864	case tok_identifier: return ParseIdentifierExpr();
				865	case tok_number: return ParseNumberExpr();
				866	case '(': return ParseParenExpr();
				867	}
				868	}
				869
				870	/// binoprhs
				871	/// ::= ('+' primary)*
				872	static ExprAST ParseBinOpRHS(int ExprPrec, ExprAST LHS) {
				873	// If this is a binop, find its precedence.
				874	while (1) {
				875	int TokPrec = GetTokPrecedence();
				876
				877	// If this is a binop that binds at least as tightly as the current binop,
				878	// consume it, otherwise we are done.
				879	if (TokPrec < ExprPrec)
				880	return LHS;
				881
				882	// Okay, we know this is a binop.
				883	int BinOp = CurTok;
				884	getNextToken(); // eat binop
				885
				886	// Parse the primary expression after the binary operator.
				887	ExprAST *RHS = ParsePrimary();
				888	if (!RHS) return 0;
				889
				890	// If BinOp binds less tightly with RHS than the operator after RHS, let
				891	// the pending operator take RHS as its LHS.
				892	int NextPrec = GetTokPrecedence();
				893	if (TokPrec < NextPrec) {
				894	RHS = ParseBinOpRHS(TokPrec+1, RHS);
				895	if (RHS == 0) return 0;
				896	}
				897
				898	// Merge LHS/RHS.
				899	LHS = new BinaryExprAST(BinOp, LHS, RHS);
				900	}
				901	}
				902
				903	/// expression
				904	/// ::= primary binoprhs
				905	///
				906	static ExprAST *ParseExpression() {
				907	ExprAST *LHS = ParsePrimary();
				908	if (!LHS) return 0;
				909
				910	return ParseBinOpRHS(0, LHS);
				911	}
				912
				913	/// prototype
				914	/// ::= id '(' id* ')'
				915	static PrototypeAST *ParsePrototype() {
				916	if (CurTok != tok_identifier)
				917	return ErrorP("Expected function name in prototype");
				918
				919	std::string FnName = IdentifierStr;
				920	getNextToken();
				921
				922	if (CurTok != '(')
				923	return ErrorP("Expected '(' in prototype");
				924
				925	std::vector<std::string> ArgNames;
				926	while (getNextToken() == tok_identifier)
				927	ArgNames.push_back(IdentifierStr);
				928	if (CurTok != ')')
				929	return ErrorP("Expected ')' in prototype");
				930
				931	// success.
				932	getNextToken(); // eat ')'.
				933
				934	return new PrototypeAST(FnName, ArgNames);
				935	}
				936
				937	/// definition ::= 'def' prototype expression
				938	static FunctionAST *ParseDefinition() {
				939	getNextToken(); // eat def.
				940	PrototypeAST *Proto = ParsePrototype();
				941	if (Proto == 0) return 0;
				942
				943	if (ExprAST *E = ParseExpression())
				944	return new FunctionAST(Proto, E);
				945	return 0;
				946	}
				947
				948	/// toplevelexpr ::= expression
				949	static FunctionAST *ParseTopLevelExpr() {
				950	if (ExprAST *E = ParseExpression()) {
				951	// Make an anonymous proto.
				952	PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
				953	return new FunctionAST(Proto, E);
				954	}
				955	return 0;
				956	}
				957
				958	/// external ::= 'extern' prototype
				959	static PrototypeAST *ParseExtern() {
				960	getNextToken(); // eat extern.
				961	return ParsePrototype();
				962	}
				963
				964	//===----------------------------------------------------------------------===//
				965	// Code Generation
				966	//===----------------------------------------------------------------------===//
				967
				968	static Module *TheModule;
				969	static LLVMBuilder Builder;
				970	static std::map<std::string, Value*> NamedValues;
				971
				972	Value ErrorV(const char Str) { Error(Str); return 0; }
				973
				974	Value *NumberExprAST::Codegen() {
				975	return ConstantFP::get(Type::DoubleTy, APFloat(Val));
				976	}
				977
				978	Value *VariableExprAST::Codegen() {
				979	// Look this variable up in the function.
				980	Value *V = NamedValues[Name];
				981	return V ? V : ErrorV("Unknown variable name");
				982	}
				983
				984	Value *BinaryExprAST::Codegen() {
				985	Value *L = LHS->Codegen();
				986	Value *R = RHS->Codegen();
				987	if (L == 0 \|\| R == 0) return 0;
				988
				989	switch (Op) {
				990	case '+': return Builder.CreateAdd(L, R, "addtmp");
				991	case '-': return Builder.CreateSub(L, R, "subtmp");
				992	case '*': return Builder.CreateMul(L, R, "multmp");
				993	case '<':
				994	L = Builder.CreateFCmpULT(L, R, "multmp");
				995	// Convert bool 0/1 to double 0.0 or 1.0
				996	return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
				997	default: return ErrorV("invalid binary operator");
				998	}
				999	}
				1000
				1001	Value *CallExprAST::Codegen() {
				1002	// Look up the name in the global module table.
				1003	Function *CalleeF = TheModule->getFunction(Callee);
				1004	if (CalleeF == 0)
				1005	return ErrorV("Unknown function referenced");
				1006
				1007	// If argument mismatch error.
				1008	if (CalleeF->arg_size() != Args.size())
				1009	return ErrorV("Incorrect # arguments passed");
				1010
				1011	std::vector<Value*> ArgsV;
				1012	for (unsigned i = 0, e = Args.size(); i != e; ++i) {
				1013	ArgsV.push_back(Args[i]->Codegen());
				1014	if (ArgsV.back() == 0) return 0;
				1015	}
				1016
				1017	return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
				1018	}
				1019
				1020	Function *PrototypeAST::Codegen() {
				1021	// Make the function type: double(double,double) etc.
Chris Lattner	35abbf5	2007-10-23 06:23:57 +0000	[diff] [blame]	1022	std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy);
				1023	FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	1024
				1025	Function *F = new Function(FT, Function::ExternalLinkage, Name, TheModule);
				1026
				1027	// If F conflicted, there was already something named 'Name'. If it has a
				1028	// body, don't allow redefinition or reextern.
				1029	if (F->getName() != Name) {
				1030	// Delete the one we just made and get the existing one.
				1031	F->eraseFromParent();
				1032	F = TheModule->getFunction(Name);
				1033
				1034	// If F already has a body, reject this.
				1035	if (!F->empty()) {
				1036	ErrorF("redefinition of function");
				1037	return 0;
				1038	}
				1039
				1040	// If F took a different number of args, reject.
				1041	if (F->arg_size() != Args.size()) {
				1042	ErrorF("redefinition of function with different # args");
				1043	return 0;
				1044	}
				1045	}
				1046
				1047	// Set names for all arguments.
				1048	unsigned Idx = 0;
				1049	for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
				1050	++AI, ++Idx) {
				1051	AI->setName(Args[Idx]);
				1052
				1053	// Add arguments to variable symbol table.
				1054	NamedValues[Args[Idx]] = AI;
				1055	}
				1056
				1057	return F;
				1058	}
				1059
				1060	Function *FunctionAST::Codegen() {
				1061	NamedValues.clear();
				1062
				1063	Function *TheFunction = Proto->Codegen();
				1064	if (TheFunction == 0)
				1065	return 0;
				1066
				1067	// Create a new basic block to start insertion into.
Chris Lattner	35abbf5	2007-10-23 06:23:57 +0000	[diff] [blame]	1068	BasicBlock *BB = new BasicBlock("entry", TheFunction);
				1069	Builder.SetInsertPoint(BB);
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	1070
				1071	if (Value *RetVal = Body->Codegen()) {
				1072	// Finish off the function.
				1073	Builder.CreateRet(RetVal);
				1074	return TheFunction;
				1075	}
				1076
				1077	// Error reading body, remove function.
				1078	TheFunction->eraseFromParent();
				1079	return 0;
				1080	}
				1081
				1082	//===----------------------------------------------------------------------===//
				1083	// Top-Level parsing and JIT Driver
				1084	//===----------------------------------------------------------------------===//
				1085
				1086	static void HandleDefinition() {
				1087	if (FunctionAST *F = ParseDefinition()) {
				1088	if (Function *LF = F->Codegen()) {
				1089	fprintf(stderr, "Read function definition:");
				1090	LF->dump();
				1091	}
				1092	} else {
				1093	// Skip token for error recovery.
				1094	getNextToken();
				1095	}
				1096	}
				1097
				1098	static void HandleExtern() {
				1099	if (PrototypeAST *P = ParseExtern()) {
				1100	if (Function *F = P->Codegen()) {
				1101	fprintf(stderr, "Read extern: ");
				1102	F->dump();
				1103	}
				1104	} else {
				1105	// Skip token for error recovery.
				1106	getNextToken();
				1107	}
				1108	}
				1109
				1110	static void HandleTopLevelExpression() {
				1111	// Evaluate a top level expression into an anonymous function.
				1112	if (FunctionAST *F = ParseTopLevelExpr()) {
				1113	if (Function *LF = F->Codegen()) {
				1114	fprintf(stderr, "Read top-level expression:");
				1115	LF->dump();
				1116	}
				1117	} else {
				1118	// Skip token for error recovery.
				1119	getNextToken();
				1120	}
				1121	}
				1122
				1123	/// top ::= definition \| external \| expression \| ';'
				1124	static void MainLoop() {
				1125	while (1) {
				1126	fprintf(stderr, "ready> ");
				1127	switch (CurTok) {
				1128	case tok_eof: return;
				1129	case ';': getNextToken(); break; // ignore top level semicolons.
				1130	case tok_def: HandleDefinition(); break;
				1131	case tok_extern: HandleExtern(); break;
				1132	default: HandleTopLevelExpression(); break;
				1133	}
				1134	}
				1135	}
				1136
				1137
				1138
				1139	//===----------------------------------------------------------------------===//
				1140	// "Library" functions that can be "extern'd" from user code.
				1141	//===----------------------------------------------------------------------===//
				1142
				1143	/// putchard - putchar that takes a double and returns 0.
				1144	extern "C"
				1145	double putchard(double X) {
				1146	putchar((char)X);
				1147	return 0;
				1148	}
				1149
				1150	//===----------------------------------------------------------------------===//
				1151	// Main driver code.
				1152	//===----------------------------------------------------------------------===//
				1153
				1154	int main() {
				1155	TheModule = new Module("my cool jit");
				1156
				1157	// Install standard binary operators.
				1158	// 1 is lowest precedence.
				1159	BinopPrecedence['<'] = 10;
				1160	BinopPrecedence['+'] = 20;
				1161	BinopPrecedence['-'] = 20;
				1162	BinopPrecedence['*'] = 40; // highest.
				1163
				1164	// Prime the first token.
				1165	fprintf(stderr, "ready> ");
				1166	getNextToken();
				1167
				1168	MainLoop();
				1169	TheModule->dump();
				1170	return 0;
				1171	}
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	1172	</pre>
				1173	</div>
				1174	</div>
				1175
				1176	<!-- *********************************************************************** -->
				1177	<hr>
				1178	<address>
				1179	<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
				1180	src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
				1181	<a href="http://validator.w3.org/check/referer"><img
Chris Lattner	8eef4b2	2007-10-23 06:30:50 +0000	[diff] [blame]	1182	src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
Chris Lattner	2e90204	2007-10-22 07:01:42 +0000	[diff] [blame]	1183
				1184	<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
				1185	<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
				1186	Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
				1187	</address>
				1188	</body>
				1189	</html>