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