Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / 422094c38dfe6878de40f4ad443dcd77542fac22 / . / docs / tutorial / LangImpl3.html
blob: 056e2134fb560b4e296951767276079faf2c66a5 [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
14<div class="doc_title">Kaleidoscope: Code generation to LLVM IR</div>
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<!-- *********************************************************************** -->
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]37<div class="doc_section"><a name="intro">Chapter 3 Introduction</a></div>
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<!-- *********************************************************************** -->
Chris Lattner7badb2d2007-11-06 07:26:32 +0000[diff] [blame]60<div class="doc_section"><a name="basics">Code Generation Setup</a></div>
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:
Chris Lattner28571ed2007-10-23 04:27:44 +0000[diff] [blame]82 explicit 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<!-- *********************************************************************** -->
150<div class="doc_section"><a name="exprs">Expression Code Generation</a></div>
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
Owen Anderson914e50c2009-07-16 19:05:41 +0000[diff] [blame]173uses "the Context.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
Chris Lattnerd3f0cdd2007-10-23 04:51:30 +0000[diff] [blame]186of Kaleidoscope, we assume that the variable has already been emited somewhere
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) {
203 case '+': return Builder.CreateAdd(L, R, "addtmp");
204 case '-': return Builder.CreateSub(L, R, "subtmp");
205 case '*': return Builder.CreateMul(L, R, "multmp");
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 Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]225do is specify what instruction to create (e.g. with <tt>CreateAdd</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<!-- *********************************************************************** -->
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]296<div class="doc_section"><a name="funcs">Function Code Generation</a></div>
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
Owen Anderson914e50c2009-07-16 19:05:41 +0000[diff] [blame]326<p>The call to <tt>Context.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
Owen Anderson914e50c2009-07-16 19:05:41 +0000[diff] [blame]329a vector of "N" LLVM double types. It then uses the <tt>Context.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
356comes to name conflicts: if a new function is created with a name was previously
357added to the symbol table, it 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
365allow 'extern'ing a function and then definining a body for it. This is useful
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);
467
468 // Validate the generated code, checking for consistency.
469 verifyFunction(*TheFunction);
470 return TheFunction;
471 }
472</pre>
473</div>
474
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]475<p>Once the insertion point is set up, we call the <tt>CodeGen()</tt> method for
476the root expression of the function. If no error happens, this emits code to
477compute the expression into the entry block and returns the value that was
478computed. Assuming no error, we then create an LLVM <a
Chris Lattnerd9b86162007-10-25 04:30:35 +0000[diff] [blame]479href="../LangRef.html#i_ret">ret instruction</a>, which completes the function.
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]480Once the function is built, we call <tt>verifyFunction</tt>, which
Chris Lattnerd9b86162007-10-25 04:30:35 +0000[diff] [blame]481is provided by LLVM. This function does a variety of consistency checks on the
482generated code, to determine if our compiler is doing everything right. Using
483this is important: it can catch a lot of bugs. Once the function is finished
484and validated, we return it.</p>
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]485
486<div class="doc_code">
487<pre>
488 // Error reading body, remove function.
489 TheFunction-&gt;eraseFromParent();
490 return 0;
491}
492</pre>
493</div>
494
495<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]496handle this by merely deleting the function we produced with the
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]497<tt>eraseFromParent</tt> method. This allows the user to redefine a function
498that they incorrectly typed in before: if we didn't delete it, it would live in
499the symbol table, with a body, preventing future redefinition.</p>
500
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]501<p>This code does have a bug, though. Since the <tt>PrototypeAST::Codegen</tt>
502can return a previously defined forward declaration, our code can actually delete
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]503a forward declaration. There are a number of ways to fix this bug, see what you
504can come up with! Here is a testcase:</p>
505
506<div class="doc_code">
507<pre>
508extern foo(a b); # ok, defines foo.
509def foo(a b) c; # error, 'c' is invalid.
510def bar() foo(1, 2); # error, unknown function "foo"
511</pre>
512</div>
513
514</div>
515
516<!-- *********************************************************************** -->
517<div class="doc_section"><a name="driver">Driver Changes and
518Closing Thoughts</a></div>
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:
537 %addtmp = add double 4.000000e+00, 5.000000e+00
538 ret double %addtmp
539}
540</pre>
541</div>
542
543<p>Note how the parser turns the top-level expression into anonymous functions
Chris Lattnerd96b1592007-11-07 05:07:10 +0000[diff] [blame]544for us. This will be handy when we add <a href="LangImpl4.html#jit">JIT
545support</a> in the next chapter. Also note that the code is very literally
546transcribed, no optimizations are being performed. We will
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:
556 %multmp = mul double %a, %a
557 %multmp1 = mul double 2.000000e+00, %a
558 %multmp2 = mul double %multmp1, %b
559 %addtmp = add double %multmp, %multmp2
560 %multmp3 = mul double %b, %b
561 %addtmp4 = add double %addtmp, %multmp3
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:
576 %calltmp = call double @foo( double %a, double 4.000000e+00 )
577 %calltmp1 = call double @bar( double 3.133700e+04 )
578 %addtmp = add double %calltmp, %calltmp1
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:
Chris Lattner8eef4b22007-10-23 06:30:50 +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:
614 %addtmp = add double 4.000000e+00, 5.000000e+00
615 ret double %addtmp
616}
617
618define double @foo(double %a, double %b) {
619entry:
620 %multmp = mul double %a, %a
621 %multmp1 = mul double 2.000000e+00, %a
622 %multmp2 = mul double %multmp1, %b
623 %addtmp = add double %multmp, %multmp2
624 %multmp3 = mul double %b, %b
625 %addtmp4 = add double %addtmp, %multmp3
626 ret double %addtmp4
627}
628
629define double @bar(double %a) {
630entry:
631 %calltmp = call double @foo( double %a, double 4.000000e+00 )
632 %calltmp1 = call double @bar( double 3.133700e+04 )
633 %addtmp = add double %calltmp, %calltmp1
634 ret double %addtmp
635}
636
637declare double @cos(double)
638
639define double @""() {
640entry:
641 %calltmp = call double @cos( double 1.234000e+00 )
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<!-- *********************************************************************** -->
659<div class="doc_section"><a name="code">Full Code Listing</a></div>
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
711 tok_identifier = -4, tok_number = -5,
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:
Chris Lattner28571ed2007-10-23 04:27:44 +0000[diff] [blame]780 explicit 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:
Chris Lattner28571ed2007-10-23 04:27:44 +0000[diff] [blame]788 explicit 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,
813/// which captures its argument names as well as if it is an operator.
814class PrototypeAST {
815 std::string Name;
816 std::vector&lt;std::string&gt; Args;
817public:
818 PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args)
819 : Name(name), Args(args) {}
820
821 Function *Codegen();
822};
823
824/// FunctionAST - This class represents a function definition itself.
825class FunctionAST {
826 PrototypeAST *Proto;
827 ExprAST *Body;
828public:
829 FunctionAST(PrototypeAST *proto, ExprAST *body)
830 : Proto(proto), Body(body) {}
831
832 Function *Codegen();
833};
834
835//===----------------------------------------------------------------------===//
836// Parser
837//===----------------------------------------------------------------------===//
838
839/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
840/// token the parser it looking at. getNextToken reads another token from the
841/// lexer and updates CurTok with its results.
842static int CurTok;
843static int getNextToken() {
844 return CurTok = gettok();
845}
846
847/// BinopPrecedence - This holds the precedence for each binary operator that is
848/// defined.
849static std::map&lt;char, int&gt; BinopPrecedence;
850
851/// GetTokPrecedence - Get the precedence of the pending binary operator token.
852static int GetTokPrecedence() {
853 if (!isascii(CurTok))
854 return -1;
855
856 // Make sure it's a declared binop.
857 int TokPrec = BinopPrecedence[CurTok];
858 if (TokPrec &lt;= 0) return -1;
859 return TokPrec;
860}
861
862/// Error* - These are little helper functions for error handling.
863ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
864PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
865FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
866
867static ExprAST *ParseExpression();
868
869/// identifierexpr
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]870/// ::= identifier
871/// ::= identifier '(' expression* ')'
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]872static ExprAST *ParseIdentifierExpr() {
873 std::string IdName = IdentifierStr;
874
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]875 getNextToken(); // eat identifier.
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]876
877 if (CurTok != '(') // Simple variable ref.
878 return new VariableExprAST(IdName);
879
880 // Call.
881 getNextToken(); // eat (
882 std::vector&lt;ExprAST*&gt; Args;
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]883 if (CurTok != ')') {
884 while (1) {
885 ExprAST *Arg = ParseExpression();
886 if (!Arg) return 0;
887 Args.push_back(Arg);
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]888
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]889 if (CurTok == ')') break;
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]890
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]891 if (CurTok != ',')
Chris Lattner6c4be9c2008-04-14 16:44:41 +0000[diff] [blame]892 return Error("Expected ')' or ',' in argument list");
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]893 getNextToken();
894 }
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]895 }
896
897 // Eat the ')'.
898 getNextToken();
899
900 return new CallExprAST(IdName, Args);
901}
902
903/// numberexpr ::= number
904static ExprAST *ParseNumberExpr() {
905 ExprAST *Result = new NumberExprAST(NumVal);
906 getNextToken(); // consume the number
907 return Result;
908}
909
910/// parenexpr ::= '(' expression ')'
911static ExprAST *ParseParenExpr() {
912 getNextToken(); // eat (.
913 ExprAST *V = ParseExpression();
914 if (!V) return 0;
915
916 if (CurTok != ')')
917 return Error("expected ')'");
918 getNextToken(); // eat ).
919 return V;
920}
921
922/// primary
923/// ::= identifierexpr
924/// ::= numberexpr
925/// ::= parenexpr
926static ExprAST *ParsePrimary() {
927 switch (CurTok) {
928 default: return Error("unknown token when expecting an expression");
929 case tok_identifier: return ParseIdentifierExpr();
930 case tok_number: return ParseNumberExpr();
931 case '(': return ParseParenExpr();
932 }
933}
934
935/// binoprhs
936/// ::= ('+' primary)*
937static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
938 // If this is a binop, find its precedence.
939 while (1) {
940 int TokPrec = GetTokPrecedence();
941
942 // If this is a binop that binds at least as tightly as the current binop,
943 // consume it, otherwise we are done.
944 if (TokPrec &lt; ExprPrec)
945 return LHS;
946
947 // Okay, we know this is a binop.
948 int BinOp = CurTok;
949 getNextToken(); // eat binop
950
951 // Parse the primary expression after the binary operator.
952 ExprAST *RHS = ParsePrimary();
953 if (!RHS) return 0;
954
955 // If BinOp binds less tightly with RHS than the operator after RHS, let
956 // the pending operator take RHS as its LHS.
957 int NextPrec = GetTokPrecedence();
958 if (TokPrec &lt; NextPrec) {
959 RHS = ParseBinOpRHS(TokPrec+1, RHS);
960 if (RHS == 0) return 0;
961 }
962
963 // Merge LHS/RHS.
964 LHS = new BinaryExprAST(BinOp, LHS, RHS);
965 }
966}
967
968/// expression
969/// ::= primary binoprhs
970///
971static ExprAST *ParseExpression() {
972 ExprAST *LHS = ParsePrimary();
973 if (!LHS) return 0;
974
975 return ParseBinOpRHS(0, LHS);
976}
977
978/// prototype
979/// ::= id '(' id* ')'
980static PrototypeAST *ParsePrototype() {
981 if (CurTok != tok_identifier)
982 return ErrorP("Expected function name in prototype");
983
984 std::string FnName = IdentifierStr;
985 getNextToken();
986
987 if (CurTok != '(')
988 return ErrorP("Expected '(' in prototype");
989
990 std::vector&lt;std::string&gt; ArgNames;
991 while (getNextToken() == tok_identifier)
992 ArgNames.push_back(IdentifierStr);
993 if (CurTok != ')')
994 return ErrorP("Expected ')' in prototype");
995
996 // success.
997 getNextToken(); // eat ')'.
998
999 return new PrototypeAST(FnName, ArgNames);
1000}
1001
1002/// definition ::= 'def' prototype expression
1003static FunctionAST *ParseDefinition() {
1004 getNextToken(); // eat def.
1005 PrototypeAST *Proto = ParsePrototype();
1006 if (Proto == 0) return 0;
1007
1008 if (ExprAST *E = ParseExpression())
1009 return new FunctionAST(Proto, E);
1010 return 0;
1011}
1012
1013/// toplevelexpr ::= expression
1014static FunctionAST *ParseTopLevelExpr() {
1015 if (ExprAST *E = ParseExpression()) {
1016 // Make an anonymous proto.
1017 PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
1018 return new FunctionAST(Proto, E);
1019 }
1020 return 0;
1021}
1022
1023/// external ::= 'extern' prototype
1024static PrototypeAST *ParseExtern() {
1025 getNextToken(); // eat extern.
1026 return ParsePrototype();
1027}
1028
1029//===----------------------------------------------------------------------===//
1030// Code Generation
1031//===----------------------------------------------------------------------===//
1032
1033static Module *TheModule;
Chris Lattner3e7b5ca2009-07-21 22:47:03 +0000[diff] [blame]1034static IRBuilder&lt;&gt; Builder(getGlobalContext());
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1035static std::map&lt;std::string, Value*&gt; NamedValues;
1036
1037Value *ErrorV(const char *Str) { Error(Str); return 0; }
1038
1039Value *NumberExprAST::Codegen() {
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1040 return ConstantFP::get(getGlobalContext(), APFloat(Val));
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1041}
1042
1043Value *VariableExprAST::Codegen() {
1044 // Look this variable up in the function.
1045 Value *V = NamedValues[Name];
1046 return V ? V : ErrorV("Unknown variable name");
1047}
1048
1049Value *BinaryExprAST::Codegen() {
1050 Value *L = LHS-&gt;Codegen();
1051 Value *R = RHS-&gt;Codegen();
1052 if (L == 0 || R == 0) return 0;
1053
1054 switch (Op) {
1055 case '+': return Builder.CreateAdd(L, R, "addtmp");
1056 case '-': return Builder.CreateSub(L, R, "subtmp");
1057 case '*': return Builder.CreateMul(L, R, "multmp");
1058 case '&lt;':
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]1059 L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1060 // Convert bool 0/1 to double 0.0 or 1.0
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1061 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), "booltmp");
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1062 default: return ErrorV("invalid binary operator");
1063 }
1064}
1065
1066Value *CallExprAST::Codegen() {
1067 // Look up the name in the global module table.
1068 Function *CalleeF = TheModule-&gt;getFunction(Callee);
1069 if (CalleeF == 0)
1070 return ErrorV("Unknown function referenced");
1071
1072 // If argument mismatch error.
1073 if (CalleeF-&gt;arg_size() != Args.size())
1074 return ErrorV("Incorrect # arguments passed");
1075
1076 std::vector&lt;Value*&gt; ArgsV;
1077 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1078 ArgsV.push_back(Args[i]-&gt;Codegen());
1079 if (ArgsV.back() == 0) return 0;
1080 }
1081
1082 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1083}
1084
1085Function *PrototypeAST::Codegen() {
1086 // Make the function type: double(double,double) etc.
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame^]1087 std::vector&lt;const Type*&gt; Doubles(Args.size(),
1088 Type::getDoubleTy(getGlobalContext()));
1089 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1090 Doubles, false);
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1091
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]1092 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1093
1094 // If F conflicted, there was already something named 'Name'. If it has a
1095 // body, don't allow redefinition or reextern.
1096 if (F-&gt;getName() != Name) {
1097 // Delete the one we just made and get the existing one.
1098 F-&gt;eraseFromParent();
1099 F = TheModule-&gt;getFunction(Name);
1100
1101 // If F already has a body, reject this.
1102 if (!F-&gt;empty()) {
1103 ErrorF("redefinition of function");
1104 return 0;
1105 }
1106
1107 // If F took a different number of args, reject.
1108 if (F-&gt;arg_size() != Args.size()) {
1109 ErrorF("redefinition of function with different # args");
1110 return 0;
1111 }
1112 }
1113
1114 // Set names for all arguments.
1115 unsigned Idx = 0;
1116 for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1117 ++AI, ++Idx) {
1118 AI-&gt;setName(Args[Idx]);
1119
1120 // Add arguments to variable symbol table.
1121 NamedValues[Args[Idx]] = AI;
1122 }
1123
1124 return F;
1125}
1126
1127Function *FunctionAST::Codegen() {
1128 NamedValues.clear();
1129
1130 Function *TheFunction = Proto-&gt;Codegen();
1131 if (TheFunction == 0)
1132 return 0;
1133
1134 // Create a new basic block to start insertion into.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1135 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]1136 Builder.SetInsertPoint(BB);
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1137
1138 if (Value *RetVal = Body-&gt;Codegen()) {
1139 // Finish off the function.
1140 Builder.CreateRet(RetVal);
Chris Lattnerd9b86162007-10-25 04:30:35 +0000[diff] [blame]1141
1142 // Validate the generated code, checking for consistency.
1143 verifyFunction(*TheFunction);
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1144 return TheFunction;
1145 }
1146
1147 // Error reading body, remove function.
1148 TheFunction-&gt;eraseFromParent();
1149 return 0;
1150}
1151
1152//===----------------------------------------------------------------------===//
1153// Top-Level parsing and JIT Driver
1154//===----------------------------------------------------------------------===//
1155
1156static void HandleDefinition() {
1157 if (FunctionAST *F = ParseDefinition()) {
1158 if (Function *LF = F-&gt;Codegen()) {
1159 fprintf(stderr, "Read function definition:");
1160 LF-&gt;dump();
1161 }
1162 } else {
1163 // Skip token for error recovery.
1164 getNextToken();
1165 }
1166}
1167
1168static void HandleExtern() {
1169 if (PrototypeAST *P = ParseExtern()) {
1170 if (Function *F = P-&gt;Codegen()) {
1171 fprintf(stderr, "Read extern: ");
1172 F-&gt;dump();
1173 }
1174 } else {
1175 // Skip token for error recovery.
1176 getNextToken();
1177 }
1178}
1179
1180static void HandleTopLevelExpression() {
1181 // Evaluate a top level expression into an anonymous function.
1182 if (FunctionAST *F = ParseTopLevelExpr()) {
1183 if (Function *LF = F-&gt;Codegen()) {
1184 fprintf(stderr, "Read top-level expression:");
1185 LF-&gt;dump();
1186 }
1187 } else {
1188 // Skip token for error recovery.
1189 getNextToken();
1190 }
1191}
1192
1193/// top ::= definition | external | expression | ';'
1194static void MainLoop() {
1195 while (1) {
1196 fprintf(stderr, "ready&gt; ");
1197 switch (CurTok) {
1198 case tok_eof: return;
1199 case ';': getNextToken(); break; // ignore top level semicolons.
1200 case tok_def: HandleDefinition(); break;
1201 case tok_extern: HandleExtern(); break;
1202 default: HandleTopLevelExpression(); break;
1203 }
1204 }
1205}
1206
1207
1208
1209//===----------------------------------------------------------------------===//
1210// "Library" functions that can be "extern'd" from user code.
1211//===----------------------------------------------------------------------===//
1212
1213/// putchard - putchar that takes a double and returns 0.
1214extern "C"
1215double putchard(double X) {
1216 putchar((char)X);
1217 return 0;
1218}
1219
1220//===----------------------------------------------------------------------===//
1221// Main driver code.
1222//===----------------------------------------------------------------------===//
1223
1224int main() {
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]1225 TheModule = new Module("my cool jit", getGlobalContext());
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1226
1227 // Install standard binary operators.
1228 // 1 is lowest precedence.
1229 BinopPrecedence['&lt;'] = 10;
1230 BinopPrecedence['+'] = 20;
1231 BinopPrecedence['-'] = 20;
1232 BinopPrecedence['*'] = 40; // highest.
1233
1234 // Prime the first token.
1235 fprintf(stderr, "ready&gt; ");
1236 getNextToken();
1237
1238 MainLoop();
1239 TheModule-&gt;dump();
1240 return 0;
1241}
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1242</pre>
1243</div>
Chris Lattner729eb142008-02-10 19:11:04 +0000[diff] [blame]1244<a href="LangImpl4.html">Next: Adding JIT and Optimizer Support</a>
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1245</div>
1246
1247<!-- *********************************************************************** -->
1248<hr>
1249<address>
1250 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1251 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1252 <a href="http://validator.w3.org/check/referer"><img
Chris Lattner8eef4b22007-10-23 06:30:50 +0000[diff] [blame]1253 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1254
1255 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1256 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
Chris Lattner3e7b5ca2009-07-21 22:47:03 +0000[diff] [blame]1257 Last modified: $Date: 2009-07-21 11:05:13 -0700 (Tue, 21 Jul 2009) $
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1258</address>
1259</body>
1260</html>