Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / 8040cd3cfd7b87661c08ca916daf355593dd8ffa / . / docs / tutorial / LangImpl3.html
blob: e3d2117c4e6867165b9a3b460b529c36fa1a453f [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:
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<!-- *********************************************************************** -->
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
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) {
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
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<!-- *********************************************************************** -->
518<div class="doc_section"><a name="driver">Driver Changes and
519Closing Thoughts</a></div>
520<!-- *********************************************************************** -->
521
522<div class="doc_text">
523
524<p>
525For now, code generation to LLVM doesn't really get us much, except that we can
526look at the pretty IR calls. The sample code inserts calls to Codegen into the
527"<tt>HandleDefinition</tt>", "<tt>HandleExtern</tt>" etc functions, and then
528dumps out the LLVM IR. This gives a nice way to look at the LLVM IR for simple
529functions. For example:
530</p>
531
532<div class="doc_code">
533<pre>
534ready> <b>4+5</b>;
Chris Lattnerd96b1592007-11-07 05:07:10 +0000[diff] [blame]535Read top-level expression:
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]536define double @""() {
537entry:
538 %addtmp = add double 4.000000e+00, 5.000000e+00
539 ret double %addtmp
540}
541</pre>
542</div>
543
544<p>Note how the parser turns the top-level expression into anonymous functions
Chris Lattnerd96b1592007-11-07 05:07:10 +0000[diff] [blame]545for us. This will be handy when we add <a href="LangImpl4.html#jit">JIT
546support</a> in the next chapter. Also note that the code is very literally
547transcribed, no optimizations are being performed. We will
548<a href="LangImpl4.html#trivialconstfold">add optimizations</a> explicitly in
549the next chapter.</p>
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]550
551<div class="doc_code">
552<pre>
553ready&gt; <b>def foo(a b) a*a + 2*a*b + b*b;</b>
Chris Lattnerd96b1592007-11-07 05:07:10 +0000[diff] [blame]554Read function definition:
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]555define double @foo(double %a, double %b) {
556entry:
557 %multmp = mul double %a, %a
558 %multmp1 = mul double 2.000000e+00, %a
559 %multmp2 = mul double %multmp1, %b
560 %addtmp = add double %multmp, %multmp2
561 %multmp3 = mul double %b, %b
562 %addtmp4 = add double %addtmp, %multmp3
563 ret double %addtmp4
564}
565</pre>
566</div>
567
568<p>This shows some simple arithmetic. Notice the striking similarity to the
569LLVM builder calls that we use to create the instructions.</p>
570
571<div class="doc_code">
572<pre>
573ready&gt; <b>def bar(a) foo(a, 4.0) + bar(31337);</b>
Chris Lattnerd96b1592007-11-07 05:07:10 +0000[diff] [blame]574Read function definition:
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]575define double @bar(double %a) {
576entry:
577 %calltmp = call double @foo( double %a, double 4.000000e+00 )
578 %calltmp1 = call double @bar( double 3.133700e+04 )
579 %addtmp = add double %calltmp, %calltmp1
580 ret double %addtmp
581}
582</pre>
583</div>
584
Chris Lattnerfc60ab02007-11-05 17:39:26 +0000[diff] [blame]585<p>This shows some function calls. Note that this function will take a long
586time to execute if you call it. In the future we'll add conditional control
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]587flow to actually make recursion useful :).</p>
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]588
589<div class="doc_code">
590<pre>
591ready&gt; <b>extern cos(x);</b>
Chris Lattnerd96b1592007-11-07 05:07:10 +0000[diff] [blame]592Read extern:
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]593declare double @cos(double)
594
595ready&gt; <b>cos(1.234);</b>
Chris Lattnerd96b1592007-11-07 05:07:10 +0000[diff] [blame]596Read top-level expression:
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]597define double @""() {
598entry:
Chris Lattner8eef4b22007-10-23 06:30:50 +0000[diff] [blame]599 %calltmp = call double @cos( double 1.234000e+00 )
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]600 ret double %calltmp
601}
602</pre>
603</div>
604
605<p>This shows an extern for the libm "cos" function, and a call to it.</p>
606
607
608<div class="doc_code">
609<pre>
610ready&gt; <b>^D</b>
611; ModuleID = 'my cool jit'
612
613define double @""() {
614entry:
615 %addtmp = add double 4.000000e+00, 5.000000e+00
616 ret double %addtmp
617}
618
619define double @foo(double %a, double %b) {
620entry:
621 %multmp = mul double %a, %a
622 %multmp1 = mul double 2.000000e+00, %a
623 %multmp2 = mul double %multmp1, %b
624 %addtmp = add double %multmp, %multmp2
625 %multmp3 = mul double %b, %b
626 %addtmp4 = add double %addtmp, %multmp3
627 ret double %addtmp4
628}
629
630define double @bar(double %a) {
631entry:
632 %calltmp = call double @foo( double %a, double 4.000000e+00 )
633 %calltmp1 = call double @bar( double 3.133700e+04 )
634 %addtmp = add double %calltmp, %calltmp1
635 ret double %addtmp
636}
637
638declare double @cos(double)
639
640define double @""() {
641entry:
642 %calltmp = call double @cos( double 1.234000e+00 )
643 ret double %calltmp
644}
645</pre>
646</div>
647
648<p>When you quit the current demo, it dumps out the IR for the entire module
649generated. Here you can see the big picture with all the functions referencing
650each other.</p>
651
Chris Lattner41fcea32007-11-13 07:06:30 +0000[diff] [blame]652<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]653describe how to <a href="LangImpl4.html">add JIT codegen and optimizer
654support</a> to this so we can actually start running code!</p>
655
656</div>
657
658
659<!-- *********************************************************************** -->
660<div class="doc_section"><a name="code">Full Code Listing</a></div>
661<!-- *********************************************************************** -->
662
663<div class="doc_text">
664
665<p>
666Here is the complete code listing for our running example, enhanced with the
667LLVM code generator. Because this uses the LLVM libraries, we need to link
668them in. To do this, we use the <a
669href="http://llvm.org/cmds/llvm-config.html">llvm-config</a> tool to inform
670our makefile/command line about which options to use:</p>
671
672<div class="doc_code">
673<pre>
674 # Compile
Chris Lattnerd96b1592007-11-07 05:07:10 +0000[diff] [blame]675 g++ -g -O3 toy.cpp `llvm-config --cppflags --ldflags --libs core` -o toy
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]676 # Run
677 ./toy
678</pre>
679</div>
680
681<p>Here is the code:</p>
682
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]683<div class="doc_code">
684<pre>
685// To build this:
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]686// See example below.
687
688#include "llvm/DerivedTypes.h"
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame]689#include "llvm/LLVMContext.h"
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]690#include "llvm/Module.h"
Chris Lattnerd9b86162007-10-25 04:30:35 +0000[diff] [blame]691#include "llvm/Analysis/Verifier.h"
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]692#include "llvm/Support/IRBuilder.h"
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]693#include &lt;cstdio&gt;
694#include &lt;string&gt;
695#include &lt;map&gt;
696#include &lt;vector&gt;
697using namespace llvm;
698
699//===----------------------------------------------------------------------===//
700// Lexer
701//===----------------------------------------------------------------------===//
702
703// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
704// of these for known things.
705enum Token {
706 tok_eof = -1,
707
708 // commands
709 tok_def = -2, tok_extern = -3,
710
711 // primary
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]712 tok_identifier = -4, tok_number = -5
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]713};
714
715static std::string IdentifierStr; // Filled in if tok_identifier
716static double NumVal; // Filled in if tok_number
717
718/// gettok - Return the next token from standard input.
719static int gettok() {
720 static int LastChar = ' ';
721
722 // Skip any whitespace.
723 while (isspace(LastChar))
724 LastChar = getchar();
725
726 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
727 IdentifierStr = LastChar;
728 while (isalnum((LastChar = getchar())))
729 IdentifierStr += LastChar;
730
731 if (IdentifierStr == "def") return tok_def;
732 if (IdentifierStr == "extern") return tok_extern;
733 return tok_identifier;
734 }
735
736 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
737 std::string NumStr;
738 do {
739 NumStr += LastChar;
740 LastChar = getchar();
741 } while (isdigit(LastChar) || LastChar == '.');
742
743 NumVal = strtod(NumStr.c_str(), 0);
744 return tok_number;
745 }
746
747 if (LastChar == '#') {
748 // Comment until end of line.
749 do LastChar = getchar();
Chris Lattnerc80c23f2007-12-02 22:46:01 +0000[diff] [blame]750 while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]751
752 if (LastChar != EOF)
753 return gettok();
754 }
755
756 // Check for end of file. Don't eat the EOF.
757 if (LastChar == EOF)
758 return tok_eof;
759
760 // Otherwise, just return the character as its ascii value.
761 int ThisChar = LastChar;
762 LastChar = getchar();
763 return ThisChar;
764}
765
766//===----------------------------------------------------------------------===//
767// Abstract Syntax Tree (aka Parse Tree)
768//===----------------------------------------------------------------------===//
769
770/// ExprAST - Base class for all expression nodes.
771class ExprAST {
772public:
773 virtual ~ExprAST() {}
774 virtual Value *Codegen() = 0;
775};
776
777/// NumberExprAST - Expression class for numeric literals like "1.0".
778class NumberExprAST : public ExprAST {
779 double Val;
780public:
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]781 NumberExprAST(double val) : Val(val) {}
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]782 virtual Value *Codegen();
783};
784
785/// VariableExprAST - Expression class for referencing a variable, like "a".
786class VariableExprAST : public ExprAST {
787 std::string Name;
788public:
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]789 VariableExprAST(const std::string &amp;name) : Name(name) {}
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]790 virtual Value *Codegen();
791};
792
793/// BinaryExprAST - Expression class for a binary operator.
794class BinaryExprAST : public ExprAST {
795 char Op;
796 ExprAST *LHS, *RHS;
797public:
798 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
799 : Op(op), LHS(lhs), RHS(rhs) {}
800 virtual Value *Codegen();
801};
802
803/// CallExprAST - Expression class for function calls.
804class CallExprAST : public ExprAST {
805 std::string Callee;
806 std::vector&lt;ExprAST*&gt; Args;
807public:
808 CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
809 : Callee(callee), Args(args) {}
810 virtual Value *Codegen();
811};
812
813/// PrototypeAST - This class represents the "prototype" for a function,
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]814/// which captures its name, and its argument names (thus implicitly the number
815/// of arguments the function takes).
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]816class PrototypeAST {
817 std::string Name;
818 std::vector&lt;std::string&gt; Args;
819public:
820 PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args)
821 : Name(name), Args(args) {}
822
823 Function *Codegen();
824};
825
826/// FunctionAST - This class represents a function definition itself.
827class FunctionAST {
828 PrototypeAST *Proto;
829 ExprAST *Body;
830public:
831 FunctionAST(PrototypeAST *proto, ExprAST *body)
832 : Proto(proto), Body(body) {}
833
834 Function *Codegen();
835};
836
837//===----------------------------------------------------------------------===//
838// Parser
839//===----------------------------------------------------------------------===//
840
841/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]842/// token the parser is looking at. getNextToken reads another token from the
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]843/// lexer and updates CurTok with its results.
844static int CurTok;
845static int getNextToken() {
846 return CurTok = gettok();
847}
848
849/// BinopPrecedence - This holds the precedence for each binary operator that is
850/// defined.
851static std::map&lt;char, int&gt; BinopPrecedence;
852
853/// GetTokPrecedence - Get the precedence of the pending binary operator token.
854static int GetTokPrecedence() {
855 if (!isascii(CurTok))
856 return -1;
857
858 // Make sure it's a declared binop.
859 int TokPrec = BinopPrecedence[CurTok];
860 if (TokPrec &lt;= 0) return -1;
861 return TokPrec;
862}
863
864/// Error* - These are little helper functions for error handling.
865ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
866PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
867FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
868
869static ExprAST *ParseExpression();
870
871/// identifierexpr
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]872/// ::= identifier
873/// ::= identifier '(' expression* ')'
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]874static ExprAST *ParseIdentifierExpr() {
875 std::string IdName = IdentifierStr;
876
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]877 getNextToken(); // eat identifier.
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]878
879 if (CurTok != '(') // Simple variable ref.
880 return new VariableExprAST(IdName);
881
882 // Call.
883 getNextToken(); // eat (
884 std::vector&lt;ExprAST*&gt; Args;
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]885 if (CurTok != ')') {
886 while (1) {
887 ExprAST *Arg = ParseExpression();
888 if (!Arg) return 0;
889 Args.push_back(Arg);
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]890
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]891 if (CurTok == ')') break;
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]892
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]893 if (CurTok != ',')
Chris Lattner6c4be9c2008-04-14 16:44:41 +0000[diff] [blame]894 return Error("Expected ')' or ',' in argument list");
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]895 getNextToken();
896 }
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]897 }
898
899 // Eat the ')'.
900 getNextToken();
901
902 return new CallExprAST(IdName, Args);
903}
904
905/// numberexpr ::= number
906static ExprAST *ParseNumberExpr() {
907 ExprAST *Result = new NumberExprAST(NumVal);
908 getNextToken(); // consume the number
909 return Result;
910}
911
912/// parenexpr ::= '(' expression ')'
913static ExprAST *ParseParenExpr() {
914 getNextToken(); // eat (.
915 ExprAST *V = ParseExpression();
916 if (!V) return 0;
917
918 if (CurTok != ')')
919 return Error("expected ')'");
920 getNextToken(); // eat ).
921 return V;
922}
923
924/// primary
925/// ::= identifierexpr
926/// ::= numberexpr
927/// ::= parenexpr
928static ExprAST *ParsePrimary() {
929 switch (CurTok) {
930 default: return Error("unknown token when expecting an expression");
931 case tok_identifier: return ParseIdentifierExpr();
932 case tok_number: return ParseNumberExpr();
933 case '(': return ParseParenExpr();
934 }
935}
936
937/// binoprhs
938/// ::= ('+' primary)*
939static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
940 // If this is a binop, find its precedence.
941 while (1) {
942 int TokPrec = GetTokPrecedence();
943
944 // If this is a binop that binds at least as tightly as the current binop,
945 // consume it, otherwise we are done.
946 if (TokPrec &lt; ExprPrec)
947 return LHS;
948
949 // Okay, we know this is a binop.
950 int BinOp = CurTok;
951 getNextToken(); // eat binop
952
953 // Parse the primary expression after the binary operator.
954 ExprAST *RHS = ParsePrimary();
955 if (!RHS) return 0;
956
957 // If BinOp binds less tightly with RHS than the operator after RHS, let
958 // the pending operator take RHS as its LHS.
959 int NextPrec = GetTokPrecedence();
960 if (TokPrec &lt; NextPrec) {
961 RHS = ParseBinOpRHS(TokPrec+1, RHS);
962 if (RHS == 0) return 0;
963 }
964
965 // Merge LHS/RHS.
966 LHS = new BinaryExprAST(BinOp, LHS, RHS);
967 }
968}
969
970/// expression
971/// ::= primary binoprhs
972///
973static ExprAST *ParseExpression() {
974 ExprAST *LHS = ParsePrimary();
975 if (!LHS) return 0;
976
977 return ParseBinOpRHS(0, LHS);
978}
979
980/// prototype
981/// ::= id '(' id* ')'
982static PrototypeAST *ParsePrototype() {
983 if (CurTok != tok_identifier)
984 return ErrorP("Expected function name in prototype");
985
986 std::string FnName = IdentifierStr;
987 getNextToken();
988
989 if (CurTok != '(')
990 return ErrorP("Expected '(' in prototype");
991
992 std::vector&lt;std::string&gt; ArgNames;
993 while (getNextToken() == tok_identifier)
994 ArgNames.push_back(IdentifierStr);
995 if (CurTok != ')')
996 return ErrorP("Expected ')' in prototype");
997
998 // success.
999 getNextToken(); // eat ')'.
1000
1001 return new PrototypeAST(FnName, ArgNames);
1002}
1003
1004/// definition ::= 'def' prototype expression
1005static FunctionAST *ParseDefinition() {
1006 getNextToken(); // eat def.
1007 PrototypeAST *Proto = ParsePrototype();
1008 if (Proto == 0) return 0;
1009
1010 if (ExprAST *E = ParseExpression())
1011 return new FunctionAST(Proto, E);
1012 return 0;
1013}
1014
1015/// toplevelexpr ::= expression
1016static FunctionAST *ParseTopLevelExpr() {
1017 if (ExprAST *E = ParseExpression()) {
1018 // Make an anonymous proto.
1019 PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
1020 return new FunctionAST(Proto, E);
1021 }
1022 return 0;
1023}
1024
1025/// external ::= 'extern' prototype
1026static PrototypeAST *ParseExtern() {
1027 getNextToken(); // eat extern.
1028 return ParsePrototype();
1029}
1030
1031//===----------------------------------------------------------------------===//
1032// Code Generation
1033//===----------------------------------------------------------------------===//
1034
1035static Module *TheModule;
Chris Lattner3e7b5ca2009-07-21 22:47:03 +0000[diff] [blame]1036static IRBuilder&lt;&gt; Builder(getGlobalContext());
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1037static std::map&lt;std::string, Value*&gt; NamedValues;
1038
1039Value *ErrorV(const char *Str) { Error(Str); return 0; }
1040
1041Value *NumberExprAST::Codegen() {
Owen Anderson6f83c9c2009-07-27 20:59:43 +0000[diff] [blame]1042 return ConstantFP::get(getGlobalContext(), APFloat(Val));
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1043}
1044
1045Value *VariableExprAST::Codegen() {
1046 // Look this variable up in the function.
1047 Value *V = NamedValues[Name];
1048 return V ? V : ErrorV("Unknown variable name");
1049}
1050
1051Value *BinaryExprAST::Codegen() {
1052 Value *L = LHS-&gt;Codegen();
1053 Value *R = RHS-&gt;Codegen();
1054 if (L == 0 || R == 0) return 0;
1055
1056 switch (Op) {
1057 case '+': return Builder.CreateAdd(L, R, "addtmp");
1058 case '-': return Builder.CreateSub(L, R, "subtmp");
1059 case '*': return Builder.CreateMul(L, R, "multmp");
1060 case '&lt;':
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]1061 L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1062 // Convert bool 0/1 to double 0.0 or 1.0
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1063 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
1064 "booltmp");
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1065 default: return ErrorV("invalid binary operator");
1066 }
1067}
1068
1069Value *CallExprAST::Codegen() {
1070 // Look up the name in the global module table.
1071 Function *CalleeF = TheModule-&gt;getFunction(Callee);
1072 if (CalleeF == 0)
1073 return ErrorV("Unknown function referenced");
1074
1075 // If argument mismatch error.
1076 if (CalleeF-&gt;arg_size() != Args.size())
1077 return ErrorV("Incorrect # arguments passed");
1078
1079 std::vector&lt;Value*&gt; ArgsV;
1080 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1081 ArgsV.push_back(Args[i]-&gt;Codegen());
1082 if (ArgsV.back() == 0) return 0;
1083 }
1084
1085 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1086}
1087
1088Function *PrototypeAST::Codegen() {
1089 // Make the function type: double(double,double) etc.
Nick Lewycky422094c2009-09-13 21:38:54 +0000[diff] [blame]1090 std::vector&lt;const Type*&gt; Doubles(Args.size(),
1091 Type::getDoubleTy(getGlobalContext()));
1092 FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
1093 Doubles, false);
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1094
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]1095 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1096
1097 // If F conflicted, there was already something named 'Name'. If it has a
1098 // body, don't allow redefinition or reextern.
1099 if (F-&gt;getName() != Name) {
1100 // Delete the one we just made and get the existing one.
1101 F-&gt;eraseFromParent();
1102 F = TheModule-&gt;getFunction(Name);
1103
1104 // If F already has a body, reject this.
1105 if (!F-&gt;empty()) {
1106 ErrorF("redefinition of function");
1107 return 0;
1108 }
1109
1110 // If F took a different number of args, reject.
1111 if (F-&gt;arg_size() != Args.size()) {
1112 ErrorF("redefinition of function with different # args");
1113 return 0;
1114 }
1115 }
1116
1117 // Set names for all arguments.
1118 unsigned Idx = 0;
1119 for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1120 ++AI, ++Idx) {
1121 AI-&gt;setName(Args[Idx]);
1122
1123 // Add arguments to variable symbol table.
1124 NamedValues[Args[Idx]] = AI;
1125 }
1126
1127 return F;
1128}
1129
1130Function *FunctionAST::Codegen() {
1131 NamedValues.clear();
1132
1133 Function *TheFunction = Proto-&gt;Codegen();
1134 if (TheFunction == 0)
1135 return 0;
1136
1137 // Create a new basic block to start insertion into.
Owen Anderson1d0be152009-08-13 21:58:54 +0000[diff] [blame]1138 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
Chris Lattner35abbf52007-10-23 06:23:57 +0000[diff] [blame]1139 Builder.SetInsertPoint(BB);
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1140
1141 if (Value *RetVal = Body-&gt;Codegen()) {
1142 // Finish off the function.
1143 Builder.CreateRet(RetVal);
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1144
Chris Lattnerd9b86162007-10-25 04:30:35 +0000[diff] [blame]1145 // Validate the generated code, checking for consistency.
1146 verifyFunction(*TheFunction);
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1147
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1148 return TheFunction;
1149 }
1150
1151 // Error reading body, remove function.
1152 TheFunction-&gt;eraseFromParent();
1153 return 0;
1154}
1155
1156//===----------------------------------------------------------------------===//
1157// Top-Level parsing and JIT Driver
1158//===----------------------------------------------------------------------===//
1159
1160static void HandleDefinition() {
1161 if (FunctionAST *F = ParseDefinition()) {
1162 if (Function *LF = F-&gt;Codegen()) {
1163 fprintf(stderr, "Read function definition:");
1164 LF-&gt;dump();
1165 }
1166 } else {
1167 // Skip token for error recovery.
1168 getNextToken();
1169 }
1170}
1171
1172static void HandleExtern() {
1173 if (PrototypeAST *P = ParseExtern()) {
1174 if (Function *F = P-&gt;Codegen()) {
1175 fprintf(stderr, "Read extern: ");
1176 F-&gt;dump();
1177 }
1178 } else {
1179 // Skip token for error recovery.
1180 getNextToken();
1181 }
1182}
1183
1184static void HandleTopLevelExpression() {
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1185 // Evaluate a top-level expression into an anonymous function.
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1186 if (FunctionAST *F = ParseTopLevelExpr()) {
1187 if (Function *LF = F-&gt;Codegen()) {
1188 fprintf(stderr, "Read top-level expression:");
1189 LF-&gt;dump();
1190 }
1191 } else {
1192 // Skip token for error recovery.
1193 getNextToken();
1194 }
1195}
1196
1197/// top ::= definition | external | expression | ';'
1198static void MainLoop() {
1199 while (1) {
1200 fprintf(stderr, "ready&gt; ");
1201 switch (CurTok) {
1202 case tok_eof: return;
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1203 case ';': getNextToken(); break; // ignore top-level semicolons.
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1204 case tok_def: HandleDefinition(); break;
1205 case tok_extern: HandleExtern(); break;
1206 default: HandleTopLevelExpression(); break;
1207 }
1208 }
1209}
1210
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1211//===----------------------------------------------------------------------===//
1212// "Library" functions that can be "extern'd" from user code.
1213//===----------------------------------------------------------------------===//
1214
1215/// putchard - putchar that takes a double and returns 0.
1216extern "C"
1217double putchard(double X) {
1218 putchar((char)X);
1219 return 0;
1220}
1221
1222//===----------------------------------------------------------------------===//
1223// Main driver code.
1224//===----------------------------------------------------------------------===//
1225
1226int main() {
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1227 LLVMContext &amp;Context = getGlobalContext();
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1228
1229 // Install standard binary operators.
1230 // 1 is lowest precedence.
1231 BinopPrecedence['&lt;'] = 10;
1232 BinopPrecedence['+'] = 20;
1233 BinopPrecedence['-'] = 20;
1234 BinopPrecedence['*'] = 40; // highest.
1235
1236 // Prime the first token.
1237 fprintf(stderr, "ready&gt; ");
1238 getNextToken();
1239
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1240 // Make the module, which holds all the code.
1241 TheModule = new Module("my cool jit", Context);
1242
1243 // Run the main "interpreter loop" now.
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1244 MainLoop();
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1245
1246 // Print out all of the generated code.
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1247 TheModule-&gt;dump();
Erick Tryzelaarfd1ec5e2009-09-22 21:14:49 +0000[diff] [blame]1248
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1249 return 0;
1250}
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1251</pre>
1252</div>
Chris Lattner729eb142008-02-10 19:11:04 +0000[diff] [blame]1253<a href="LangImpl4.html">Next: Adding JIT and Optimizer Support</a>
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1254</div>
1255
1256<!-- *********************************************************************** -->
1257<hr>
1258<address>
1259 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1260 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1261 <a href="http://validator.w3.org/check/referer"><img
Chris Lattner8eef4b22007-10-23 06:30:50 +0000[diff] [blame]1262 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1263
1264 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1265 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
Chris Lattner3e7b5ca2009-07-21 22:47:03 +0000[diff] [blame]1266 Last modified: $Date: 2009-07-21 11:05:13 -0700 (Tue, 21 Jul 2009) $
Chris Lattner2e902042007-10-22 07:01:42 +0000[diff] [blame]1267</address>
1268</body>
1269</html>