1 ========================================
2 Kaleidoscope: Code generation to LLVM IR
3 ========================================
11 Welcome to Chapter 3 of the "`Implementing a language with
12 LLVM <index.html>`_" tutorial. This chapter shows you how to transform
13 the `Abstract Syntax Tree <LangImpl2.html>`_, built in Chapter 2, into
14 LLVM IR. This will teach you a little bit about how LLVM does things, as
15 well as demonstrate how easy it is to use. It's much more work to build
16 a lexer and parser than it is to generate LLVM IR code. :)
18 **Please note**: the code in this chapter and later require LLVM 2.2 or
19 later. LLVM 2.1 and before will not work with it. Also note that you
20 need to use a version of this tutorial that matches your LLVM release:
21 If you are using an official LLVM release, use the version of the
22 documentation included with your release or on the `llvm.org releases
23 page <http://llvm.org/releases/>`_.
28 In order to generate LLVM IR, we want some simple setup to get started.
29 First we define virtual code generation (codegen) methods in each AST
34 /// ExprAST - Base class for all expression nodes.
38 virtual Value *Codegen() = 0;
41 /// NumberExprAST - Expression class for numeric literals like "1.0".
42 class NumberExprAST : public ExprAST {
46 NumberExprAST(double Val) : Val(Val) {}
47 virtual Value *Codegen();
51 The Codegen() method says to emit IR for that AST node along with all
52 the things it depends on, and they all return an LLVM Value object.
53 "Value" is the class used to represent a "`Static Single Assignment
54 (SSA) <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_
55 register" or "SSA value" in LLVM. The most distinct aspect of SSA values
56 is that their value is computed as the related instruction executes, and
57 it does not get a new value until (and if) the instruction re-executes.
58 In other words, there is no way to "change" an SSA value. For more
59 information, please read up on `Static Single
60 Assignment <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_
61 - the concepts are really quite natural once you grok them.
63 Note that instead of adding virtual methods to the ExprAST class
64 hierarchy, it could also make sense to use a `visitor
65 pattern <http://en.wikipedia.org/wiki/Visitor_pattern>`_ or some other
66 way to model this. Again, this tutorial won't dwell on good software
67 engineering practices: for our purposes, adding a virtual method is
70 The second thing we want is an "Error" method like we used for the
71 parser, which will be used to report errors found during code generation
72 (for example, use of an undeclared parameter):
76 Value *ErrorV(const char *Str) {
81 static Module *TheModule;
82 static IRBuilder<> Builder(getGlobalContext());
83 static std::map<std::string, Value*> NamedValues;
85 The static variables will be used during code generation. ``TheModule``
86 is the LLVM construct that contains all of the functions and global
87 variables in a chunk of code. In many ways, it is the top-level
88 structure that the LLVM IR uses to contain code.
90 The ``Builder`` object is a helper object that makes it easy to generate
91 LLVM instructions. Instances of the
92 `IRBuilder <http://llvm.org/doxygen/IRBuilder_8h-source.html>`_
93 class template keep track of the current place to insert instructions
94 and has methods to create new instructions.
96 The ``NamedValues`` map keeps track of which values are defined in the
97 current scope and what their LLVM representation is. (In other words, it
98 is a symbol table for the code). In this form of Kaleidoscope, the only
99 things that can be referenced are function parameters. As such, function
100 parameters will be in this map when generating code for their function
103 With these basics in place, we can start talking about how to generate
104 code for each expression. Note that this assumes that the ``Builder``
105 has been set up to generate code *into* something. For now, we'll assume
106 that this has already been done, and we'll just use it to emit code.
108 Expression Code Generation
109 ==========================
111 Generating LLVM code for expression nodes is very straightforward: less
112 than 45 lines of commented code for all four of our expression nodes.
113 First we'll do numeric literals:
117 Value *NumberExprAST::Codegen() {
118 return ConstantFP::get(getGlobalContext(), APFloat(Val));
121 In the LLVM IR, numeric constants are represented with the
122 ``ConstantFP`` class, which holds the numeric value in an ``APFloat``
123 internally (``APFloat`` has the capability of holding floating point
124 constants of Arbitrary Precision). This code basically just creates
125 and returns a ``ConstantFP``. Note that in the LLVM IR that constants
126 are all uniqued together and shared. For this reason, the API uses the
127 "foo::get(...)" idiom instead of "new foo(..)" or "foo::Create(..)".
131 Value *VariableExprAST::Codegen() {
132 // Look this variable up in the function.
133 Value *V = NamedValues[Name];
134 return V ? V : ErrorV("Unknown variable name");
137 References to variables are also quite simple using LLVM. In the simple
138 version of Kaleidoscope, we assume that the variable has already been
139 emitted somewhere and its value is available. In practice, the only
140 values that can be in the ``NamedValues`` map are function arguments.
141 This code simply checks to see that the specified name is in the map (if
142 not, an unknown variable is being referenced) and returns the value for
143 it. In future chapters, we'll add support for `loop induction
144 variables <LangImpl5.html#for>`_ in the symbol table, and for `local
145 variables <LangImpl7.html#localvars>`_.
149 Value *BinaryExprAST::Codegen() {
150 Value *L = LHS->Codegen();
151 Value *R = RHS->Codegen();
157 return Builder.CreateFAdd(L, R, "addtmp");
159 return Builder.CreateFSub(L, R, "subtmp");
161 return Builder.CreateFMul(L, R, "multmp");
163 L = Builder.CreateFCmpULT(L, R, "cmptmp");
164 // Convert bool 0/1 to double 0.0 or 1.0
165 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()),
168 return ErrorV("invalid binary operator");
172 Binary operators start to get more interesting. The basic idea here is
173 that we recursively emit code for the left-hand side of the expression,
174 then the right-hand side, then we compute the result of the binary
175 expression. In this code, we do a simple switch on the opcode to create
176 the right LLVM instruction.
178 In the example above, the LLVM builder class is starting to show its
179 value. IRBuilder knows where to insert the newly created instruction,
180 all you have to do is specify what instruction to create (e.g. with
181 ``CreateFAdd``), which operands to use (``L`` and ``R`` here) and
182 optionally provide a name for the generated instruction.
184 One nice thing about LLVM is that the name is just a hint. For instance,
185 if the code above emits multiple "addtmp" variables, LLVM will
186 automatically provide each one with an increasing, unique numeric
187 suffix. Local value names for instructions are purely optional, but it
188 makes it much easier to read the IR dumps.
190 `LLVM instructions <../LangRef.html#instref>`_ are constrained by strict
191 rules: for example, the Left and Right operators of an `add
192 instruction <../LangRef.html#i_add>`_ must have the same type, and the
193 result type of the add must match the operand types. Because all values
194 in Kaleidoscope are doubles, this makes for very simple code for add,
197 On the other hand, LLVM specifies that the `fcmp
198 instruction <../LangRef.html#i_fcmp>`_ always returns an 'i1' value (a
199 one bit integer). The problem with this is that Kaleidoscope wants the
200 value to be a 0.0 or 1.0 value. In order to get these semantics, we
201 combine the fcmp instruction with a `uitofp
202 instruction <../LangRef.html#i_uitofp>`_. This instruction converts its
203 input integer into a floating point value by treating the input as an
204 unsigned value. In contrast, if we used the `sitofp
205 instruction <../LangRef.html#i_sitofp>`_, the Kaleidoscope '<' operator
206 would return 0.0 and -1.0, depending on the input value.
210 Value *CallExprAST::Codegen() {
211 // Look up the name in the global module table.
212 Function *CalleeF = TheModule->getFunction(Callee);
214 return ErrorV("Unknown function referenced");
216 // If argument mismatch error.
217 if (CalleeF->arg_size() != Args.size())
218 return ErrorV("Incorrect # arguments passed");
220 std::vector<Value *> ArgsV;
221 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
222 ArgsV.push_back(Args[i]->Codegen());
227 return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
230 Code generation for function calls is quite straightforward with LLVM.
231 The code above initially does a function name lookup in the LLVM
232 Module's symbol table. Recall that the LLVM Module is the container that
233 holds all of the functions we are JIT'ing. By giving each function the
234 same name as what the user specifies, we can use the LLVM symbol table
235 to resolve function names for us.
237 Once we have the function to call, we recursively codegen each argument
238 that is to be passed in, and create an LLVM `call
239 instruction <../LangRef.html#i_call>`_. Note that LLVM uses the native C
240 calling conventions by default, allowing these calls to also call into
241 standard library functions like "sin" and "cos", with no additional
244 This wraps up our handling of the four basic expressions that we have so
245 far in Kaleidoscope. Feel free to go in and add some more. For example,
246 by browsing the `LLVM language reference <../LangRef.html>`_ you'll find
247 several other interesting instructions that are really easy to plug into
250 Function Code Generation
251 ========================
253 Code generation for prototypes and functions must handle a number of
254 details, which make their code less beautiful than expression code
255 generation, but allows us to illustrate some important points. First,
256 lets talk about code generation for prototypes: they are used both for
257 function bodies and external function declarations. The code starts
262 Function *PrototypeAST::Codegen() {
263 // Make the function type: double(double,double) etc.
264 std::vector<Type*> Doubles(Args.size(),
265 Type::getDoubleTy(getGlobalContext()));
267 FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false);
270 Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
272 This code packs a lot of power into a few lines. Note first that this
273 function returns a "Function\*" instead of a "Value\*". Because a
274 "prototype" really talks about the external interface for a function
275 (not the value computed by an expression), it makes sense for it to
276 return the LLVM Function it corresponds to when codegen'd.
278 The call to ``FunctionType::get`` creates the ``FunctionType`` that
279 should be used for a given Prototype. Since all function arguments in
280 Kaleidoscope are of type double, the first line creates a vector of "N"
281 LLVM double types. It then uses the ``Functiontype::get`` method to
282 create a function type that takes "N" doubles as arguments, returns one
283 double as a result, and that is not vararg (the false parameter
284 indicates this). Note that Types in LLVM are uniqued just like Constants
285 are, so you don't "new" a type, you "get" it.
287 The final line above actually creates the function that the prototype
288 will correspond to. This indicates the type, linkage and name to use, as
289 well as which module to insert into. "`external
290 linkage <../LangRef.html#linkage>`_" means that the function may be
291 defined outside the current module and/or that it is callable by
292 functions outside the module. The Name passed in is the name the user
293 specified: since "``TheModule``" is specified, this name is registered
294 in "``TheModule``"s symbol table, which is used by the function call
299 // If F conflicted, there was already something named 'Name'. If it has a
300 // body, don't allow redefinition or reextern.
301 if (F->getName() != Name) {
302 // Delete the one we just made and get the existing one.
303 F->eraseFromParent();
304 F = TheModule->getFunction(Name);
306 The Module symbol table works just like the Function symbol table when
307 it comes to name conflicts: if a new function is created with a name
308 that was previously added to the symbol table, the new function will get
309 implicitly renamed when added to the Module. The code above exploits
310 this fact to determine if there was a previous definition of this
313 In Kaleidoscope, I choose to allow redefinitions of functions in two
314 cases: first, we want to allow 'extern'ing a function more than once, as
315 long as the prototypes for the externs match (since all arguments have
316 the same type, we just have to check that the number of arguments
317 match). Second, we want to allow 'extern'ing a function and then
318 defining a body for it. This is useful when defining mutually recursive
321 In order to implement this, the code above first checks to see if there
322 is a collision on the name of the function. If so, it deletes the
323 function we just created (by calling ``eraseFromParent``) and then
324 calling ``getFunction`` to get the existing function with the specified
325 name. Note that many APIs in LLVM have "erase" forms and "remove" forms.
326 The "remove" form unlinks the object from its parent (e.g. a Function
327 from a Module) and returns it. The "erase" form unlinks the object and
332 // If F already has a body, reject this.
334 ErrorF("redefinition of function");
338 // If F took a different number of args, reject.
339 if (F->arg_size() != Args.size()) {
340 ErrorF("redefinition of function with different # args");
345 In order to verify the logic above, we first check to see if the
346 pre-existing function is "empty". In this case, empty means that it has
347 no basic blocks in it, which means it has no body. If it has no body, it
348 is a forward declaration. Since we don't allow anything after a full
349 definition of the function, the code rejects this case. If the previous
350 reference to a function was an 'extern', we simply verify that the
351 number of arguments for that definition and this one match up. If not,
356 // Set names for all arguments.
358 for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
360 AI->setName(Args[Idx]);
362 // Add arguments to variable symbol table.
363 NamedValues[Args[Idx]] = AI;
369 The last bit of code for prototypes loops over all of the arguments in
370 the function, setting the name of the LLVM Argument objects to match,
371 and registering the arguments in the ``NamedValues`` map for future use
372 by the ``VariableExprAST`` AST node. Once this is set up, it returns the
373 Function object to the caller. Note that we don't check for conflicting
374 argument names here (e.g. "extern foo(a b a)"). Doing so would be very
375 straight-forward with the mechanics we have already used above.
379 Function *FunctionAST::Codegen() {
382 Function *TheFunction = Proto->Codegen();
386 Code generation for function definitions starts out simply enough: we
387 just codegen the prototype (Proto) and verify that it is ok. We then
388 clear out the ``NamedValues`` map to make sure that there isn't anything
389 in it from the last function we compiled. Code generation of the
390 prototype ensures that there is an LLVM Function object that is ready to
395 // Create a new basic block to start insertion into.
396 BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
397 Builder.SetInsertPoint(BB);
399 if (Value *RetVal = Body->Codegen()) {
401 Now we get to the point where the ``Builder`` is set up. The first line
402 creates a new `basic block <http://en.wikipedia.org/wiki/Basic_block>`_
403 (named "entry"), which is inserted into ``TheFunction``. The second line
404 then tells the builder that new instructions should be inserted into the
405 end of the new basic block. Basic blocks in LLVM are an important part
406 of functions that define the `Control Flow
407 Graph <http://en.wikipedia.org/wiki/Control_flow_graph>`_. Since we
408 don't have any control flow, our functions will only contain one block
409 at this point. We'll fix this in `Chapter 5 <LangImpl5.html>`_ :).
413 if (Value *RetVal = Body->Codegen()) {
414 // Finish off the function.
415 Builder.CreateRet(RetVal);
417 // Validate the generated code, checking for consistency.
418 verifyFunction(*TheFunction);
423 Once the insertion point is set up, we call the ``CodeGen()`` method for
424 the root expression of the function. If no error happens, this emits
425 code to compute the expression into the entry block and returns the
426 value that was computed. Assuming no error, we then create an LLVM `ret
427 instruction <../LangRef.html#i_ret>`_, which completes the function.
428 Once the function is built, we call ``verifyFunction``, which is
429 provided by LLVM. This function does a variety of consistency checks on
430 the generated code, to determine if our compiler is doing everything
431 right. Using this is important: it can catch a lot of bugs. Once the
432 function is finished and validated, we return it.
436 // Error reading body, remove function.
437 TheFunction->eraseFromParent();
441 The only piece left here is handling of the error case. For simplicity,
442 we handle this by merely deleting the function we produced with the
443 ``eraseFromParent`` method. This allows the user to redefine a function
444 that they incorrectly typed in before: if we didn't delete it, it would
445 live in the symbol table, with a body, preventing future redefinition.
447 This code does have a bug, though. Since the ``PrototypeAST::Codegen``
448 can return a previously defined forward declaration, our code can
449 actually delete a forward declaration. There are a number of ways to fix
450 this bug, see what you can come up with! Here is a testcase:
454 extern foo(a b); # ok, defines foo.
455 def foo(a b) c; # error, 'c' is invalid.
456 def bar() foo(1, 2); # error, unknown function "foo"
458 Driver Changes and Closing Thoughts
459 ===================================
461 For now, code generation to LLVM doesn't really get us much, except that
462 we can look at the pretty IR calls. The sample code inserts calls to
463 Codegen into the "``HandleDefinition``", "``HandleExtern``" etc
464 functions, and then dumps out the LLVM IR. This gives a nice way to look
465 at the LLVM IR for simple functions. For example:
470 Read top-level expression:
473 ret double 9.000000e+00
476 Note how the parser turns the top-level expression into anonymous
477 functions for us. This will be handy when we add `JIT
478 support <LangImpl4.html#jit>`_ in the next chapter. Also note that the
479 code is very literally transcribed, no optimizations are being performed
480 except simple constant folding done by IRBuilder. We will `add
481 optimizations <LangImpl4.html#trivialconstfold>`_ explicitly in the next
486 ready> def foo(a b) a*a + 2*a*b + b*b;
487 Read function definition:
488 define double @foo(double %a, double %b) {
490 %multmp = fmul double %a, %a
491 %multmp1 = fmul double 2.000000e+00, %a
492 %multmp2 = fmul double %multmp1, %b
493 %addtmp = fadd double %multmp, %multmp2
494 %multmp3 = fmul double %b, %b
495 %addtmp4 = fadd double %addtmp, %multmp3
499 This shows some simple arithmetic. Notice the striking similarity to the
500 LLVM builder calls that we use to create the instructions.
504 ready> def bar(a) foo(a, 4.0) + bar(31337);
505 Read function definition:
506 define double @bar(double %a) {
508 %calltmp = call double @foo(double %a, double 4.000000e+00)
509 %calltmp1 = call double @bar(double 3.133700e+04)
510 %addtmp = fadd double %calltmp, %calltmp1
514 This shows some function calls. Note that this function will take a long
515 time to execute if you call it. In the future we'll add conditional
516 control flow to actually make recursion useful :).
520 ready> extern cos(x);
522 declare double @cos(double)
525 Read top-level expression:
528 %calltmp = call double @cos(double 1.234000e+00)
532 This shows an extern for the libm "cos" function, and a call to it.
534 .. TODO:: Abandon Pygments' horrible `llvm` lexer. It just totally gives up
535 on highlighting this due to the first line.
540 ; ModuleID = 'my cool jit'
544 %addtmp = fadd double 4.000000e+00, 5.000000e+00
548 define double @foo(double %a, double %b) {
550 %multmp = fmul double %a, %a
551 %multmp1 = fmul double 2.000000e+00, %a
552 %multmp2 = fmul double %multmp1, %b
553 %addtmp = fadd double %multmp, %multmp2
554 %multmp3 = fmul double %b, %b
555 %addtmp4 = fadd double %addtmp, %multmp3
559 define double @bar(double %a) {
561 %calltmp = call double @foo(double %a, double 4.000000e+00)
562 %calltmp1 = call double @bar(double 3.133700e+04)
563 %addtmp = fadd double %calltmp, %calltmp1
567 declare double @cos(double)
571 %calltmp = call double @cos(double 1.234000e+00)
575 When you quit the current demo, it dumps out the IR for the entire
576 module generated. Here you can see the big picture with all the
577 functions referencing each other.
579 This wraps up the third chapter of the Kaleidoscope tutorial. Up next,
580 we'll describe how to `add JIT codegen and optimizer
581 support <LangImpl4.html>`_ to this so we can actually start running
587 Here is the complete code listing for our running example, enhanced with
588 the LLVM code generator. Because this uses the LLVM libraries, we need
589 to link them in. To do this, we use the
590 `llvm-config <http://llvm.org/cmds/llvm-config.html>`_ tool to inform
591 our makefile/command line about which options to use:
596 clang++ -g -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -o toy
602 .. literalinclude:: ../../examples/Kaleidoscope/Chapter3/toy.cpp
605 `Next: Adding JIT and Optimizer Support <LangImpl4.html>`_