well as demonstrate how easy it is to use. It's much more work to build
a lexer and parser than it is to generate LLVM IR code. :)
-**Please note**: the code in this chapter and later require LLVM 2.2 or
-later. LLVM 2.1 and before will not work with it. Also note that you
+**Please note**: the code in this chapter and later require LLVM 3.7 or
+later. LLVM 3.6 and before will not work with it. Also note that you
need to use a version of this tutorial that matches your LLVM release:
If you are using an official LLVM release, use the version of the
documentation included with your release or on the `llvm.org releases
class ExprAST {
public:
virtual ~ExprAST() {}
- virtual Value *Codegen() = 0;
+ virtual Value *codegen() = 0;
};
/// NumberExprAST - Expression class for numeric literals like "1.0".
public:
NumberExprAST(double Val) : Val(Val) {}
- virtual Value *Codegen();
+ virtual Value *codegen();
};
...
-The Codegen() method says to emit IR for that AST node along with all
+The codegen() method says to emit IR for that AST node along with all
the things it depends on, and they all return an LLVM Value object.
"Value" is the class used to represent a "`Static Single Assignment
(SSA) <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_
.. code-block:: c++
+ static std::unique_ptr<Module> *TheModule;
+ static IRBuilder<> Builder(getGlobalContext());
+ static std::map<std::string, Value*> NamedValues;
+
Value *ErrorV(const char *Str) {
Error(Str);
return nullptr;
}
- static Module *TheModule;
- static IRBuilder<> Builder(getGlobalContext());
- static std::map<std::string, Value*> NamedValues;
-
The static variables will be used during code generation. ``TheModule``
-is the LLVM construct that contains all of the functions and global
-variables in a chunk of code. In many ways, it is the top-level
-structure that the LLVM IR uses to contain code.
+is an LLVM construct that contains functions and global variables. In many
+ways, it is the top-level structure that the LLVM IR uses to contain code.
+It will own the memory for all of the IR that we generate, which is why
+the codegen() method returns a raw Value\*, rather than a unique_ptr<Value>.
The ``Builder`` object is a helper object that makes it easy to generate
LLVM instructions. Instances of the
.. code-block:: c++
- Value *NumberExprAST::Codegen() {
+ Value *NumberExprAST::codegen() {
return ConstantFP::get(getGlobalContext(), APFloat(Val));
}
.. code-block:: c++
- Value *VariableExprAST::Codegen() {
+ Value *VariableExprAST::codegen() {
// Look this variable up in the function.
Value *V = NamedValues[Name];
if (!V)
.. code-block:: c++
- Value *BinaryExprAST::Codegen() {
- Value *L = LHS->Codegen();
- Value *R = RHS->Codegen();
+ Value *BinaryExprAST::codegen() {
+ Value *L = LHS->codegen();
+ Value *R = RHS->codegen();
if (!L || !R)
return nullptr;
.. code-block:: c++
- Value *CallExprAST::Codegen() {
+ Value *CallExprAST::codegen() {
// Look up the name in the global module table.
Function *CalleeF = TheModule->getFunction(Callee);
if (!CalleeF)
std::vector<Value *> ArgsV;
for (unsigned i = 0, e = Args.size(); i != e; ++i) {
- ArgsV.push_back(Args[i]->Codegen());
+ ArgsV.push_back(Args[i]->codegen());
if (!ArgsV.back())
return nullptr;
}
return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
}
-Code generation for function calls is quite straightforward with LLVM.
-The code above initially does a function name lookup in the LLVM
-Module's symbol table. Recall that the LLVM Module is the container that
-holds all of the functions we are JIT'ing. By giving each function the
-same name as what the user specifies, we can use the LLVM symbol table
-to resolve function names for us.
+Code generation for function calls is quite straightforward with LLVM. The code
+above initially does a function name lookup in the LLVM Module's symbol table.
+Recall that the LLVM Module is the container that holds the functions we are
+JIT'ing. By giving each function the same name as what the user specifies, we
+can use the LLVM symbol table to resolve function names for us.
Once we have the function to call, we recursively codegen each argument
that is to be passed in, and create an LLVM `call
.. code-block:: c++
- Function *PrototypeAST::Codegen() {
+ Function *PrototypeAST::codegen() {
// Make the function type: double(double,double) etc.
std::vector<Type*> Doubles(Args.size(),
Type::getDoubleTy(getGlobalContext()));
indicates this). Note that Types in LLVM are uniqued just like Constants
are, so you don't "new" a type, you "get" it.
-The final line above actually creates the function that the prototype
-will correspond to. This indicates the type, linkage and name to use, as
+The final line above actually creates the IR Function corresponding to
+the Prototype. This indicates the type, linkage and name to use, as
well as which module to insert into. "`external
linkage <../LangRef.html#linkage>`_" means that the function may be
defined outside the current module and/or that it is callable by
functions outside the module. The Name passed in is the name the user
specified: since "``TheModule``" is specified, this name is registered
-in "``TheModule``"s symbol table, which is used by the function call
-code above.
+in "``TheModule``"s symbol table.
.. code-block:: c++
- // If F conflicted, there was already something named 'Name'. If it has a
- // body, don't allow redefinition or reextern.
- if (F->getName() != Name) {
- // Delete the one we just made and get the existing one.
- F->eraseFromParent();
- F = TheModule->getFunction(Name);
-
-The Module symbol table works just like the Function symbol table when
-it comes to name conflicts: if a new function is created with a name
-that was previously added to the symbol table, the new function will get
-implicitly renamed when added to the Module. The code above exploits
-this fact to determine if there was a previous definition of this
-function.
-
-In Kaleidoscope, I choose to allow redefinitions of functions in two
-cases: first, we want to allow 'extern'ing a function more than once, as
-long as the prototypes for the externs match (since all arguments have
-the same type, we just have to check that the number of arguments
-match). Second, we want to allow 'extern'ing a function and then
-defining a body for it. This is useful when defining mutually recursive
-functions.
-
-In order to implement this, the code above first checks to see if there
-is a collision on the name of the function. If so, it deletes the
-function we just created (by calling ``eraseFromParent``) and then
-calling ``getFunction`` to get the existing function with the specified
-name. Note that many APIs in LLVM have "erase" forms and "remove" forms.
-The "remove" form unlinks the object from its parent (e.g. a Function
-from a Module) and returns it. The "erase" form unlinks the object and
-then deletes it.
+ // Set names for all arguments.
+ unsigned Idx = 0;
+ for (auto &Arg : F->args())
+ Arg.setName(Args[Idx++]);
-.. code-block:: c++
+ return F;
- // If F already has a body, reject this.
- if (!F->empty()) {
- ErrorF("redefinition of function");
- return nullptr;
- }
+Finally, we set the name of each of the function's arguments according to the
+names given in the Prototype. This step isn't strictly necessary, but keeping
+the names consistent makes the IR more readable, and allows subsequent code to
+refer directly to the arguments for their names, rather than having to look up
+them up in the Prototype AST.
- // If F took a different number of args, reject.
- if (F->arg_size() != Args.size()) {
- ErrorF("redefinition of function with different # args");
- return nullptr;
- }
- }
-
-In order to verify the logic above, we first check to see if the
-pre-existing function is "empty". In this case, empty means that it has
-no basic blocks in it, which means it has no body. If it has no body, it
-is a forward declaration. Since we don't allow anything after a full
-definition of the function, the code rejects this case. If the previous
-reference to a function was an 'extern', we simply verify that the
-number of arguments for that definition and this one match up. If not,
-we emit an error.
+At this point we have a function prototype with no body. This is how LLVM IR
+represents function declarations. For extern statements in Kaleidoscope, this
+is as far as we need to go. For function definitions however, we need to
+codegen and attach a function body.
.. code-block:: c++
- // Set names for all arguments.
- unsigned Idx = 0;
- for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size();
- ++AI, ++Idx) {
- AI->setName(Args[Idx]);
-
- // Add arguments to variable symbol table.
- NamedValues[Args[Idx]] = AI;
- }
-
- return F;
- }
+ Function *FunctionAST::codegen() {
+ // First, check for an existing function from a previous 'extern' declaration.
+ Function *TheFunction = TheModule->getFunction(Proto->getName());
-The last bit of code for prototypes loops over all of the arguments in
-the function, setting the name of the LLVM Argument objects to match,
-and registering the arguments in the ``NamedValues`` map for future use
-by the ``VariableExprAST`` AST node. Once this is set up, it returns the
-Function object to the caller. Note that we don't check for conflicting
-argument names here (e.g. "extern foo(a b a)"). Doing so would be very
-straight-forward with the mechanics we have already used above.
+ if (!TheFunction)
+ TheFunction = Proto->codegen();
-.. code-block:: c++
+ if (!TheFunction)
+ return nullptr;
- Function *FunctionAST::Codegen() {
- NamedValues.clear();
+ if (!TheFunction->empty())
+ return (Function*)ErrorV("Function cannot be redefined.");
- Function *TheFunction = Proto->Codegen();
- if (!TheFunction)
- return nullptr;
-Code generation for function definitions starts out simply enough: we
-just codegen the prototype (Proto) and verify that it is ok. We then
-clear out the ``NamedValues`` map to make sure that there isn't anything
-in it from the last function we compiled. Code generation of the
-prototype ensures that there is an LLVM Function object that is ready to
-go for us.
+For function definitions, we start by searching TheModule's symbol table for an
+existing version of this function, in case one has already been created using an
+'extern' statement. If Module::getFunction returns null then no previous version
+exists, so we'll codegen one from the Prototype. In either case, we want to
+assert that the function is empty (i.e. has no body yet) before we start.
.. code-block:: c++
- // Create a new basic block to start insertion into.
- BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
- Builder.SetInsertPoint(BB);
+ // Create a new basic block to start insertion into.
+ BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
+ Builder.SetInsertPoint(BB);
- if (Value *RetVal = Body->Codegen()) {
+ // Record the function arguments in the NamedValues map.
+ NamedValues.clear();
+ for (auto &Arg : TheFunction->args())
+ NamedValues[Arg.getName()] = &Arg;
Now we get to the point where the ``Builder`` is set up. The first line
creates a new `basic block <http://en.wikipedia.org/wiki/Basic_block>`_
don't have any control flow, our functions will only contain one block
at this point. We'll fix this in `Chapter 5 <LangImpl5.html>`_ :).
+Next we add the function arguments to the NamedValues map (after first clearing
+it out) so that they're accessible to ``VariableExprAST`` nodes.
+
.. code-block:: c++
- if (Value *RetVal = Body->Codegen()) {
+ if (Value *RetVal = Body->codegen()) {
// Finish off the function.
Builder.CreateRet(RetVal);
return TheFunction;
}
-Once the insertion point is set up, we call the ``CodeGen()`` method for
-the root expression of the function. If no error happens, this emits
-code to compute the expression into the entry block and returns the
-value that was computed. Assuming no error, we then create an LLVM `ret
-instruction <../LangRef.html#i_ret>`_, which completes the function.
+Once the insertion point has been set up and the NamedValues map populated,
+we call the ``codegen()`` method for the root expression of the function. If no
+error happens, this emits code to compute the expression into the entry block
+and returns the value that was computed. Assuming no error, we then create an
+LLVM `ret instruction <../LangRef.html#i_ret>`_, which completes the function.
Once the function is built, we call ``verifyFunction``, which is
provided by LLVM. This function does a variety of consistency checks on
the generated code, to determine if our compiler is doing everything
that they incorrectly typed in before: if we didn't delete it, it would
live in the symbol table, with a body, preventing future redefinition.
-This code does have a bug, though. Since the ``PrototypeAST::Codegen``
-can return a previously defined forward declaration, our code can
-actually delete a forward declaration. There are a number of ways to fix
-this bug, see what you can come up with! Here is a testcase:
+This code does have a bug, though: If the ``FunctionAST::codegen()`` method
+finds an existing IR Function, it does not validate its signature against the
+definition's own prototype. This means that an earlier 'extern' declaration will
+take precedence over the function definition's signature, which can cause
+codegen to fail, for instance if the function arguments are named differently.
+There are a number of ways to fix this bug, see what you can come up with! Here
+is a testcase:
::
- extern foo(a b); # ok, defines foo.
- def foo(a b) c; # error, 'c' is invalid.
- def bar() foo(1, 2); # error, unknown function "foo"
+ extern foo(a); # ok, defines foo.
+ def foo(b) b; # Error: Unknown variable name. (decl using 'a' takes precedence).
Driver Changes and Closing Thoughts
===================================
For now, code generation to LLVM doesn't really get us much, except that
we can look at the pretty IR calls. The sample code inserts calls to
-Codegen into the "``HandleDefinition``", "``HandleExtern``" etc
+codegen into the "``HandleDefinition``", "``HandleExtern``" etc
functions, and then dumps out the LLVM IR. This gives a nice way to look
at the LLVM IR for simple functions. For example:
projects / oota-llvm.git / blobdiff