Compiler development is a very challenging task. Fortunately, with the advancement of projects like LLVM, addressing this challenge has become significantly easier, enabling even a solo programmer to create a new language that approaches C in terms of performance. Working with LLVM is complicated by the fact that this system is represented by a vast amount of code, accompanied by minimal documentation. To address this shortcoming, the author of the material we are publishing today intends to demonstrate code examples written in Go and show how they are translated first into , and then into LLVM IR using the . The Go SSA and LLVM IR code has been slightly edited to remove elements not relevant to the explanations provided here, making these explanations clearer.
First Example
The first function I will discuss here is a simple mechanism for adding numbers:
func myAdd(a, b int) int{
return a + b
}This function is very simple, and it’s likely that nothing simpler could be conceived. It translates into the following Go SSA code:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0In this representation of the function, type hints are placed on the right, which can often be ignored.
This small example already illustrates the essence of one aspect of SSA. Specifically, when converting code into SSA form, each expression is broken down into its most elementary parts. In our case, the statement return a + b, in fact, represents two operations: adding two numbers and returning the result.
Moreover, here one can see the basic blocks of the program; in this code, there is only one block — the entry block. We will discuss blocks in more detail later.
The Go SSA code easily translates into LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} It can be observed that while other syntactic constructs are used here, the function structure has mostly remained unchanged. LLVM IR code is slightly more complex than Go SSA code and resembles C. Here, in the function declaration, the return type comes first, and the argument type is specified before the argument name. Additionally, for the simplification of IR parsing, a symbol precedes global entities' names, @, while a symbol precedes local names, % (the function is also considered a global entity).
One of the features of this code that should be noted is that the decision regarding the representation of the Go type int, which can be represented by a 32-bit or 64-bit value depending on the compiler and compilation target, is made when creating the LLVM IR code. This is one of many reasons why LLVM IR code is not, as many think, platform-independent. Such code created for one platform cannot simply be taken and compiled for another platform (unless approached with great care ).
Another interesting point to note is that the type i64 is not a signed integer: it is neutral in terms of representing the sign of the number. Depending on the instruction, it can represent both signed and unsigned numbers. In the case of addition, this does not matter, so there is no difference in working with signed or unsigned numbers here. It should be noted that in the C language, an overflow of a signed integer variable leads to undefined behavior, so the Clang frontend adds a flag to the operation nsw (no signed wrap), which tells LLVM that it can assume that overflow never occurs during addition.
This can be important for certain optimizations. For example, adding two i16 values on a 32-bit platform (with 32-bit registers) requires, after performing the addition, a sign extension operation to remain within the range. i16Because of this, performing integer operations considering the machine register sizes is often more efficient.
What happens next with this IR code is not our main concern right now. The code is optimized (but in the case of such a simple example as ours, nothing is optimized anymore), and then it is transformed into machine code.
Second example
The next example we will consider will be a bit more complex. Specifically, it involves a function that sums a slice of integers:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}This code is transformed into the following Go SSA code:
func sum(numbers []int) int:
entry:
jump for.loop
for.loop:
t0 = phi [entry: 0:int, for.body: t6] #n int
t1 = phi [entry: 0:int, for.body: t7] #i int
t2 = len(numbers) int
t3 = t1 < t2 bool
if t3 goto for.body else for.done
for.body:
t4 = &numbers[t1] *int
t5 = *t4 int
t6 = t0 + t5 int
t7 = t1 + 1:int int
jump for.loop
for.done:
return t0Here you can already see more constructs characteristic of code representation in SSA form. Probably the most obvious feature of this code is the fact that there are no structured control flow commands. Control flow is handled here only by conditional and unconditional jumps, and if we consider this command as a control flow command, there is also a return command.
In fact, it is worth noting that the program is not divided into blocks using curly braces (as in C-family languages). It is divided by labels, resembling assembly languages, and presented in the form of basic blocks. In SSA, basic blocks are defined as continuous sequences of code starting with a label and ending with instructions that terminate the basic block, such as — return and jump.
Another interesting detail of this code is presented by the instruction phi. This instruction is quite unusual, and it may take some time to understand it. Remember that — is an abbreviation for Static Single Assignment. This is an intermediate representation of code used by compilers, where each variable is assigned a value only once. This is great for expressing simple functions, like our function myAdd, shown above, but not suitable for more complex functions — such as the one discussed in this section sum. In particular, variables change during the execution of a loop. i and n.
SSA circumvents the limitation of single assignment of variable values using a so-called instruction phi (its name comes from the Greek alphabet). The point is that in order to form SSA code representation for languages like C, one has to resort to some tricks. The result of calling this instruction is the current value of the variable (i or n), and its parameters are a list of basic blocks. For example, consider the following instruction:
t0 = phi [entry: 0:int, for.body: t6] #n Its meaning is as follows: if the previous basic block was the block entry (entry), then t0 is a constant 0, and if the previous basic block was for.body, then you need to take the value t6 from that block. This all may seem quite mysterious, but this mechanism ensures the operation of SSA. From a human perspective, it complicates code understanding, but the fact that each value is assigned only once greatly simplifies many optimizations.
Note that if you are writing your own compiler, you usually do not have to deal with such things. Even Clang does not generate all these instructions phi, it uses the alloca mechanism (it resembles working with regular local variables). Then, during an LLVM optimization pass called , the instructions alloca are transformed into SSA form. TinyGo, however, gets input from Go SSA, which, conveniently, is already transformed into SSA form.
Another innovation in the discussed fragment of intermediate code is that accessing elements of a slice by index is represented as an address calculation operation and a dereference operation of the obtained pointer. Here you can also see direct additions of constants into the IR code (for example — 1:int). In the example with the function myAdd Such a method has not been used. Now, having understood these nuances, let's see how this code will transform into LLVM IR:
define i64 @sum(i64* %ptr, i64 %len, i64 p) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, ref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, ref.next ]
%2 = icmp slt i64 %1, %len
br i1 %2, label %for.body, label %for.done
for.body: ; preds = %for.loop
%3 = getelementptr i64, i64* %ptr, i64 %1
%4 = load i64, i64* %3
%5 = add i64 %0, %4
%6 = add i64 %1, 1
br label %for.loop
for.done: ; preds = %for.loop
ret i64 %0
} Here, as before, we can see the same structure, including other syntactic constructs. For example, in calls, phi the values and labels have been switched. However, there is something here worth noting.
To begin with, we can see a completely different function signature. LLVM does not support slices; as a result, to optimize, the TinyGo compiler that generated this intermediate code split the description of this data structure into parts. It could have represented three slice elements (ptr, len and cap) as a single structure, but representing them as three separate entities allows for certain optimizations. Other compilers might represent slices differently; it depends on the function calling conventions of the target platform.
Another interesting feature of this code is the use of the instruction getelementptr (often abbreviated as GEP).
This instruction works with pointers and is used to obtain a pointer to an element of a slice. For example, let's compare it with the following code written in C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Or with the following equivalent code:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} The most important thing here is that the instruction getelementptr does not perform dereferencing operations. It only calculates a new pointer based on the existing one. It can be perceived similarly to the mul and add instruction at the hardware level. You can read more about the GEP instruction .
Another interesting feature of this intermediate code is the use of the instruction icmpThis is a general-purpose instruction used to implement comparisons of integers. The result of executing this instruction is always a value of type i1 — a boolean value. In this case, comparison is performed using the keyword slt (signed less than), since we are comparing two numbers that were previously represented by the type int. If we were comparing two unsigned integers, we would use icmp, and the keyword used in the comparison would be ult. Another instruction is used for comparing floating-point numbers, fcmp, which works in a similar manner.
Summary
I believe I have covered the most important features of LLVM IR in this material. Of course, there is much more to explore. In particular, intermediate code representation may have many annotations that allow optimization passes to account for certain code characteristics known to the compiler, which cannot be expressed in IR in any other way. For example, this flag inbounds of the GEP instruction, or the flags nsw and nuw, which can be added to the instruction add. The same applies to the keyword private, indicating to the optimizer that the marked function will not be referenced outside of the current compilation unit. This allows many interesting interprocedural optimizations such as the elimination of unused arguments.
You can read more about LLVM in , which you will often refer to while developing your own compiler based on LLVM. Here is , which discusses the development of a compiler for a very simple language. Both of these resources will be useful for you when creating your own compiler.
Dear readers! Are you using LLVM?
Source: habr.com
