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