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