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