569 lines · plain
1========================================2Kaleidoscope: Code generation to LLVM IR3========================================4 5.. contents::6 :local:7 8Chapter 3 Introduction9======================10 11Welcome to Chapter 3 of the "`Implementing a language with12LLVM <index.html>`_" tutorial. This chapter shows you how to transform13the `Abstract Syntax Tree <LangImpl02.html>`_, built in Chapter 2, into14LLVM IR. This will teach you a little bit about how LLVM does things, as15well as demonstrate how easy it is to use. It's much more work to build16a lexer and parser than it is to generate LLVM IR code. :)17 18**Please note**: the code in this chapter and later require LLVM 3.7 or19later. LLVM 3.6 and before will not work with it. Also note that you20need to use a version of this tutorial that matches your LLVM release:21If you are using an official LLVM release, use the version of the22documentation included with your release or on the `llvm.org releases23page <https://llvm.org/releases/>`_.24 25Code Generation Setup26=====================27 28In order to generate LLVM IR, we want some simple setup to get started.29First we define virtual code generation (codegen) methods in each AST30class:31 32.. code-block:: c++33 34 /// ExprAST - Base class for all expression nodes.35 class ExprAST {36 public:37 virtual ~ExprAST() = default;38 virtual Value *codegen() = 0;39 };40 41 /// NumberExprAST - Expression class for numeric literals like "1.0".42 class NumberExprAST : public ExprAST {43 double Val;44 45 public:46 NumberExprAST(double Val) : Val(Val) {}47 Value *codegen() override;48 };49 ...50 51The codegen() method says to emit IR for that AST node along with all52the things it depends on, and they all return an LLVM Value object.53"Value" is the class used to represent a "`Static Single Assignment54(SSA) <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_55register" or "SSA value" in LLVM. The most distinct aspect of SSA values56is that their value is computed as the related instruction executes, and57it does not get a new value until (and if) the instruction re-executes.58In other words, there is no way to "change" an SSA value. For more59information, please read up on `Static Single60Assignment <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_61- the concepts are really quite natural once you grok them.62 63Note that instead of adding virtual methods to the ExprAST class64hierarchy, it could also make sense to use a `visitor65pattern <http://en.wikipedia.org/wiki/Visitor_pattern>`_ or some other66way to model this. Again, this tutorial won't dwell on good software67engineering practices: for our purposes, adding a virtual method is68simplest.69 70The second thing we want is a "LogError" method like we used for the71parser, which will be used to report errors found during code generation72(for example, use of an undeclared parameter):73 74.. code-block:: c++75 76 static std::unique_ptr<LLVMContext> TheContext;77 static std::unique_ptr<IRBuilder<>> Builder;78 static std::unique_ptr<Module> TheModule;79 static std::map<std::string, Value *> NamedValues;80 81 Value *LogErrorV(const char *Str) {82 LogError(Str);83 return nullptr;84 }85 86The static variables will be used during code generation. ``TheContext``87is an opaque object that owns a lot of core LLVM data structures, such as88the type and constant value tables. We don't need to understand it in89detail, we just need a single instance to pass into APIs that require it.90 91The ``Builder`` object is a helper object that makes it easy to generate92LLVM instructions. Instances of the93`IRBuilder <https://llvm.org/doxygen/IRBuilder_8h_source.html>`_94class template keep track of the current place to insert instructions95and has methods to create new instructions.96 97``TheModule`` is an LLVM construct that contains functions and global98variables. In many ways, it is the top-level structure that the LLVM IR99uses to contain code. It will own the memory for all of the IR that we100generate, which is why the codegen() method returns a raw Value\*,101rather than a unique_ptr<Value>.102 103The ``NamedValues`` map keeps track of which values are defined in the104current scope and what their LLVM representation is. (In other words, it105is a symbol table for the code). In this form of Kaleidoscope, the only106things that can be referenced are function parameters. As such, function107parameters will be in this map when generating code for their function108body.109 110With these basics in place, we can start talking about how to generate111code for each expression. Note that this assumes that the ``Builder``112has been set up to generate code *into* something. For now, we'll assume113that this has already been done, and we'll just use it to emit code.114 115Expression Code Generation116==========================117 118Generating LLVM code for expression nodes is very straightforward: less119than 45 lines of commented code for all four of our expression nodes.120First we'll do numeric literals:121 122.. code-block:: c++123 124 Value *NumberExprAST::codegen() {125 return ConstantFP::get(*TheContext, APFloat(Val));126 }127 128In the LLVM IR, numeric constants are represented with the129``ConstantFP`` class, which holds the numeric value in an ``APFloat``130internally (``APFloat`` has the capability of holding floating point131constants of Arbitrary Precision). This code basically just creates132and returns a ``ConstantFP``. Note that in the LLVM IR that constants133are all uniqued together and shared. For this reason, the API uses the134"foo::get(...)" idiom instead of "new foo(..)" or "foo::Create(..)".135 136.. code-block:: c++137 138 Value *VariableExprAST::codegen() {139 // Look this variable up in the function.140 Value *V = NamedValues[Name];141 if (!V)142 LogErrorV("Unknown variable name");143 return V;144 }145 146References to variables are also quite simple using LLVM. In the simple147version of Kaleidoscope, we assume that the variable has already been148emitted somewhere and its value is available. In practice, the only149values that can be in the ``NamedValues`` map are function arguments.150This code simply checks to see that the specified name is in the map (if151not, an unknown variable is being referenced) and returns the value for152it. In future chapters, we'll add support for `loop induction153variables <LangImpl05.html#for-loop-expression>`_ in the symbol table, and for `local154variables <LangImpl07.html#user-defined-local-variables>`_.155 156.. code-block:: c++157 158 Value *BinaryExprAST::codegen() {159 Value *L = LHS->codegen();160 Value *R = RHS->codegen();161 if (!L || !R)162 return nullptr;163 164 switch (Op) {165 case '+':166 return Builder->CreateFAdd(L, R, "addtmp");167 case '-':168 return Builder->CreateFSub(L, R, "subtmp");169 case '*':170 return Builder->CreateFMul(L, R, "multmp");171 case '<':172 L = Builder->CreateFCmpULT(L, R, "cmptmp");173 // Convert bool 0/1 to double 0.0 or 1.0174 return Builder->CreateUIToFP(L, Type::getDoubleTy(*TheContext),175 "booltmp");176 default:177 return LogErrorV("invalid binary operator");178 }179 }180 181Binary operators start to get more interesting. The basic idea here is182that we recursively emit code for the left-hand side of the expression,183then the right-hand side, then we compute the result of the binary184expression. In this code, we do a simple switch on the opcode to create185the right LLVM instruction.186 187In the example above, the LLVM builder class is starting to show its188value. IRBuilder knows where to insert the newly created instruction,189all you have to do is specify what instruction to create (e.g. with190``CreateFAdd``), which operands to use (``L`` and ``R`` here) and191optionally provide a name for the generated instruction.192 193One nice thing about LLVM is that the name is just a hint. For instance,194if the code above emits multiple "addtmp" variables, LLVM will195automatically provide each one with an increasing, unique numeric196suffix. Local value names for instructions are purely optional, but it197makes it much easier to read the IR dumps.198 199`LLVM instructions <../../LangRef.html#instruction-reference>`_ are constrained by strict200rules: for example, the Left and Right operands of an `add201instruction <../../LangRef.html#add-instruction>`_ must have the same type, and the202result type of the add must match the operand types. Because all values203in Kaleidoscope are doubles, this makes for very simple code for add,204sub and mul.205 206On the other hand, LLVM specifies that the `fcmp207instruction <../../LangRef.html#fcmp-instruction>`_ always returns an 'i1' value (a208one bit integer). The problem with this is that Kaleidoscope wants the209value to be a 0.0 or 1.0 value. In order to get these semantics, we210combine the fcmp instruction with a `uitofp211instruction <../../LangRef.html#uitofp-to-instruction>`_. This instruction converts its212input integer into a floating point value by treating the input as an213unsigned value. In contrast, if we used the `sitofp214instruction <../../LangRef.html#sitofp-to-instruction>`_, the Kaleidoscope '<' operator215would return 0.0 and -1.0, depending on the input value.216 217.. code-block:: c++218 219 Value *CallExprAST::codegen() {220 // Look up the name in the global module table.221 Function *CalleeF = TheModule->getFunction(Callee);222 if (!CalleeF)223 return LogErrorV("Unknown function referenced");224 225 // If argument mismatch error.226 if (CalleeF->arg_size() != Args.size())227 return LogErrorV("Incorrect # arguments passed");228 229 std::vector<Value *> ArgsV;230 for (unsigned i = 0, e = Args.size(); i != e; ++i) {231 ArgsV.push_back(Args[i]->codegen());232 if (!ArgsV.back())233 return nullptr;234 }235 236 return Builder->CreateCall(CalleeF, ArgsV, "calltmp");237 }238 239Code generation for function calls is quite straightforward with LLVM. The code240above initially does a function name lookup in the LLVM Module's symbol table.241Recall that the LLVM Module is the container that holds the functions we are242JIT'ing. By giving each function the same name as what the user specifies, we243can use the LLVM symbol table to resolve function names for us.244 245Once we have the function to call, we recursively codegen each argument246that is to be passed in, and create an LLVM `call247instruction <../../LangRef.html#call-instruction>`_. Note that LLVM uses the native C248calling conventions by default, allowing these calls to also call into249standard library functions like "sin" and "cos", with no additional250effort.251 252This wraps up our handling of the four basic expressions that we have so253far in Kaleidoscope. Feel free to go in and add some more. For example,254by browsing the `LLVM language reference <../../LangRef.html>`_ you'll find255several other interesting instructions that are really easy to plug into256our basic framework.257 258Function Code Generation259========================260 261Code generation for prototypes and functions must handle a number of262details, which make their code less beautiful than expression code263generation, but allows us to illustrate some important points. First,264let's talk about code generation for prototypes: they are used both for265function bodies and external function declarations. The code starts266with:267 268.. code-block:: c++269 270 Function *PrototypeAST::codegen() {271 // Make the function type: double(double,double) etc.272 std::vector<Type*> Doubles(Args.size(),273 Type::getDoubleTy(*TheContext));274 FunctionType *FT =275 FunctionType::get(Type::getDoubleTy(*TheContext), Doubles, false);276 277 Function *F =278 Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());279 280This code packs a lot of power into a few lines. Note first that this281function returns a "Function\*" instead of a "Value\*". Because a282"prototype" really talks about the external interface for a function283(not the value computed by an expression), it makes sense for it to284return the LLVM Function it corresponds to when codegen'd.285 286The call to ``FunctionType::get`` creates the ``FunctionType`` that287should be used for a given Prototype. Since all function arguments in288Kaleidoscope are of type double, the first line creates a vector of "N"289LLVM double types. It then uses the ``Functiontype::get`` method to290create a function type that takes "N" doubles as arguments, returns one291double as a result, and that is not vararg (the false parameter292indicates this). Note that Types in LLVM are uniqued just like Constants293are, so you don't "new" a type, you "get" it.294 295The final line above actually creates the IR Function corresponding to296the Prototype. This indicates the type, linkage and name to use, as297well as which module to insert into. "`external298linkage <../../LangRef.html#linkage>`_" means that the function may be299defined outside the current module and/or that it is callable by300functions outside the module. The Name passed in is the name the user301specified: since "``TheModule``" is specified, this name is registered302in "``TheModule``"s symbol table.303 304.. code-block:: c++305 306 // Set names for all arguments.307 unsigned Idx = 0;308 for (auto &Arg : F->args())309 Arg.setName(Args[Idx++]);310 311 return F;312 313Finally, we set the name of each of the function's arguments according to the314names given in the Prototype. This step isn't strictly necessary, but keeping315the names consistent makes the IR more readable, and allows subsequent code to316refer directly to the arguments for their names, rather than having to look317them up in the Prototype AST.318 319At this point we have a function prototype with no body. This is how LLVM IR320represents function declarations. For extern statements in Kaleidoscope, this321is as far as we need to go. For function definitions however, we need to322codegen and attach a function body.323 324.. code-block:: c++325 326 Function *FunctionAST::codegen() {327 // First, check for an existing function from a previous 'extern' declaration.328 Function *TheFunction = TheModule->getFunction(Proto->getName());329 330 if (!TheFunction)331 TheFunction = Proto->codegen();332 333 if (!TheFunction)334 return nullptr;335 336 if (!TheFunction->empty())337 return (Function*)LogErrorV("Function cannot be redefined.");338 339 340For function definitions, we start by searching TheModule's symbol table for an341existing version of this function, in case one has already been created using an342'extern' statement. If Module::getFunction returns null then no previous version343exists, so we'll codegen one from the Prototype. In either case, we want to344assert that the function is empty (i.e. has no body yet) before we start.345 346.. code-block:: c++347 348 // Create a new basic block to start insertion into.349 BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);350 Builder->SetInsertPoint(BB);351 352 // Record the function arguments in the NamedValues map.353 NamedValues.clear();354 for (auto &Arg : TheFunction->args())355 NamedValues[std::string(Arg.getName())] = &Arg;356 357Now we get to the point where the ``Builder`` is set up. The first line358creates a new `basic block <http://en.wikipedia.org/wiki/Basic_block>`_359(named "entry"), which is inserted into ``TheFunction``. The second line360then tells the builder that new instructions should be inserted into the361end of the new basic block. Basic blocks in LLVM are an important part362of functions that define the `Control Flow363Graph <http://en.wikipedia.org/wiki/Control_flow_graph>`_. Since we364don't have any control flow, our functions will only contain one block365at this point. We'll fix this in `Chapter 5 <LangImpl05.html>`_ :).366 367Next we add the function arguments to the NamedValues map (after first clearing368it out) so that they're accessible to ``VariableExprAST`` nodes.369 370.. code-block:: c++371 372 if (Value *RetVal = Body->codegen()) {373 // Finish off the function.374 Builder->CreateRet(RetVal);375 376 // Validate the generated code, checking for consistency.377 verifyFunction(*TheFunction);378 379 return TheFunction;380 }381 382Once the insertion point has been set up and the NamedValues map populated,383we call the ``codegen()`` method for the root expression of the function. If no384error happens, this emits code to compute the expression into the entry block385and returns the value that was computed. Assuming no error, we then create an386LLVM `ret instruction <../../LangRef.html#ret-instruction>`_, which completes the function.387Once the function is built, we call ``verifyFunction``, which is388provided by LLVM. This function does a variety of consistency checks on389the generated code, to determine if our compiler is doing everything390right. Using this is important: it can catch a lot of bugs. Once the391function is finished and validated, we return it.392 393.. code-block:: c++394 395 // Error reading body, remove function.396 TheFunction->eraseFromParent();397 return nullptr;398 }399 400The only piece left here is handling of the error case. For simplicity,401we handle this by merely deleting the function we produced with the402``eraseFromParent`` method. This allows the user to redefine a function403that they incorrectly typed in before: if we didn't delete it, it would404live in the symbol table, with a body, preventing future redefinition.405 406This code does have a bug, though: If the ``FunctionAST::codegen()`` method407finds an existing IR Function, it does not validate its signature against the408definition's own prototype. This means that an earlier 'extern' declaration will409take precedence over the function definition's signature, which can cause410codegen to fail, for instance if the function arguments are named differently.411There are a number of ways to fix this bug, see what you can come up with! Here412is a testcase:413 414::415 416 extern foo(a); # ok, defines foo.417 def foo(b) b; # Error: Unknown variable name. (decl using 'a' takes precedence).418 419Driver Changes and Closing Thoughts420===================================421 422For now, code generation to LLVM doesn't really get us much, except that423we can look at the pretty IR calls. The sample code inserts calls to424codegen into the "``HandleDefinition``", "``HandleExtern``" etc425functions, and then dumps out the LLVM IR. This gives a nice way to look426at the LLVM IR for simple functions. For example:427 428::429 430 ready> 4+5;431 Read top-level expression:432 define double @0() {433 entry:434 ret double 9.000000e+00435 }436 437Note how the parser turns the top-level expression into anonymous438functions for us. This will be handy when we add `JIT439support <LangImpl04.html#adding-a-jit-compiler>`_ in the next chapter. Also note that the440code is very literally transcribed, no optimizations are being performed441except simple constant folding done by IRBuilder. We will `add442optimizations <LangImpl04.html#trivial-constant-folding>`_ explicitly in the next443chapter.444 445::446 447 ready> def foo(a b) a*a + 2*a*b + b*b;448 Read function definition:449 define double @foo(double %a, double %b) {450 entry:451 %multmp = fmul double %a, %a452 %multmp1 = fmul double 2.000000e+00, %a453 %multmp2 = fmul double %multmp1, %b454 %addtmp = fadd double %multmp, %multmp2455 %multmp3 = fmul double %b, %b456 %addtmp4 = fadd double %addtmp, %multmp3457 ret double %addtmp4458 }459 460This shows some simple arithmetic. Notice the striking similarity to the461LLVM builder calls that we use to create the instructions.462 463::464 465 ready> def bar(a) foo(a, 4.0) + bar(31337);466 Read function definition:467 define double @bar(double %a) {468 entry:469 %calltmp = call double @foo(double %a, double 4.000000e+00)470 %calltmp1 = call double @bar(double 3.133700e+04)471 %addtmp = fadd double %calltmp, %calltmp1472 ret double %addtmp473 }474 475This shows some function calls. Note that this function will take a long476time to execute if you call it. In the future we'll add conditional477control flow to actually make recursion useful :).478 479::480 481 ready> extern cos(x);482 Read extern:483 declare double @cos(double)484 485 ready> cos(1.234);486 Read top-level expression:487 define double @1() {488 entry:489 %calltmp = call double @cos(double 1.234000e+00)490 ret double %calltmp491 }492 493This shows an extern for the libm "cos" function, and a call to it.494 495.. TODO:: Abandon Pygments' horrible `llvm` lexer. It just totally gives up496 on highlighting this due to the first line.497 498::499 500 ready> ^D501 ; ModuleID = 'my cool jit'502 503 define double @0() {504 entry:505 %addtmp = fadd double 4.000000e+00, 5.000000e+00506 ret double %addtmp507 }508 509 define double @foo(double %a, double %b) {510 entry:511 %multmp = fmul double %a, %a512 %multmp1 = fmul double 2.000000e+00, %a513 %multmp2 = fmul double %multmp1, %b514 %addtmp = fadd double %multmp, %multmp2515 %multmp3 = fmul double %b, %b516 %addtmp4 = fadd double %addtmp, %multmp3517 ret double %addtmp4518 }519 520 define double @bar(double %a) {521 entry:522 %calltmp = call double @foo(double %a, double 4.000000e+00)523 %calltmp1 = call double @bar(double 3.133700e+04)524 %addtmp = fadd double %calltmp, %calltmp1525 ret double %addtmp526 }527 528 declare double @cos(double)529 530 define double @1() {531 entry:532 %calltmp = call double @cos(double 1.234000e+00)533 ret double %calltmp534 }535 536When you quit the current demo (by sending an EOF via CTRL+D on Linux537or CTRL+Z and ENTER on Windows), it dumps out the IR for the entire538module generated. Here you can see the big picture with all the539functions referencing each other.540 541This wraps up the third chapter of the Kaleidoscope tutorial. Up next,542we'll describe how to `add JIT codegen and optimizer543support <LangImpl04.html>`_ to this so we can actually start running544code!545 546Full Code Listing547=================548 549Here is the complete code listing for our running example, enhanced with550the LLVM code generator. Because this uses the LLVM libraries, we need551to link them in. To do this, we use the552`llvm-config <https://llvm.org/cmds/llvm-config.html>`_ tool to inform553our makefile/command line about which options to use:554 555.. code-block:: bash556 557 # Compile558 clang++ -g -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -o toy559 # Run560 ./toy561 562Here is the code:563 564.. literalinclude:: ../../../examples/Kaleidoscope/Chapter3/toy.cpp565 :language: c++566 567`Next: Adding JIT and Optimizer Support <LangImpl04.html>`_568 569