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