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