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