Backend

Library Usage

The goal in designing the FU-compiler's backend was to target LLVM IR. This can be done in one of two ways:

1. Use either the C++ API or the C API provided by LLVM to generate LLVM IR code.

• Pros: API is simple to use; LLVM IR changes will not break your code;
• Cons: Documentation for the API is not always up-to-date, or even correct; dependency on LLVM libraries;

2. Generate LLVM IR code manually.

• Pros: No third-party dependencies; leads to greater understanding of how LLVM IR works;
• Cons: Work necessary when the LLVM IR specification changes; reinvents the wheel as usable code doing the same thing under an open source license already exists;

The decision was made for us implicitly as one of the requirements was to not have any third-party dependencies, resulting in option 2.

Overall Structure

This, however, lead us to the next problem: Should we recreate the parts of the LLVM API we needed - with its extensive Value hierarchy - or use a different approach? We judged the amount of work for the first option to be - in our case - significantly larger than that of the second option, as we needed only a small portion of the API, but would still have to create many classes to properly implement something akin to the Value hierarchy.

With that decision in mind our target code generation consists of two main classes:

• Module: Corresponds to one LLVM IR module (.ll file)
• Function: Corresponds to one LLVM IR function and describes what LLVM IR instructions we can add to such a function in an abstract fashion
• LLVMBackend: Implements the interface and calls the appropriate method in Module for each TAC-Quadruple

In addition to that we have the utility class LLVMExecutor, which allows us to test our generated LLVM IR code from Java at runtime by calling LLVM's jit-compiler (and interpreter, in case jit-compiling is not available) lli.

Static Single Assignment and LLVM

Another important design decision concerns to which extend SSA is generated. To understand the issue, one should have a look at the LLVM machine model and LLVM IR's language description: LLVM, at it's core, is a register machine with an unlimited number of named registers. These registers can be used as arguments to instructions - which never modify registers themselves. The result of instructions, however, can be assigned to registers (and only registers).

%z = add %i64 %x, %y <- adds the two longs in registers %x and %y and stores the result to %z

The quirk with LLVM is, that you cannot assign a register more than once in a namespace. In other words, you cannot reassign a register. This is an issue when using conditionals or loops, where you assign the same register with different values in different branches. LLVM (and SSA in general) employs so called phi nodes (see SSA article above) to allow to assign different value to a single register, based on where the control flow came from.

While phi nodes allow us to, rather easily, write loops and conditionals, implementing mutable variables in LLVM SSA is something else entirely: Mutable variables in the TAC can be the target of assignments multiple times. SSA strictly prohibits this notion. The only way to deal with it is to allocate a new register every time an assignment is made:

%z.0 = add i64 %x, %y %z.1 = add i64 %z, %i %z.2 = add i64 %z, %j ...

This approach works for simple programs, but quickly becomes unwieldy when combined with functions, global variables and/or loops.

With Mutable memory LLVM IR provides an alternative way to deal with SSA. Let us have a look at the instructions to use mutable memory. The LLVM machine model has a traditional stack for functions to manipulate memory. The instruction alloca allocates memory for a variable on this stack and returns a pointer to it. store <from> <to> writes the value of a register into the memory area refered to by the pointer in the register . The last instruction load <from> loads the value at the memory location, which is pointed at by register and returns the value.

1. Declarations in TAC are converted to alloca instructions with the corresponding LLVM type.
2. Assignments in TAC are converted to store instructions
3. Read-Access to Variables (i.e. using them anywhere except as results in assignments) in TAC yields load instructions in the generated LLVM IR. Note that for every read, a new load instruction is generated, because the value of the variable might have changed in the meantime.

While it is possible to implement the source language only using registers and phi instructions, the recommended approach to generate code for mutable variables is to employ mutable memory, as suggested by the official LLVM language guide:

The short (and happy) summary of this chapter is that there is no need for your front-end to build SSA form: LLVM provides highly tuned and well tested support for this, though the way it works is a bit unexpected for some.

(written by Chris Lattner, the primary implementor of LLVM, commit here).

Mutable memory is not required to be SSA form and thus lets us generate code for mutable variables more easily. The great SSA support the language guide mentions lies in the LLVM tools and libraries, which can convert the store, alloca and load instructions to basic SSA again. Note that this is not always possible (function arguments cannot, in general, be converted to SSA), but in the case of our TAC, all memory accessing instructions are converted (i.e. optimized away).

We decided to use the latter (recommended) approach, because it better leverages the power of LLVM IR and the LLVM tools and lets us write better understandable LLVM IR Code more easily.

You can run the LLVM optimizer tool yourself to examine the resulting LLVM code by calling: opt -mem2reg <input.ll>