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