An esoteric exploration on the target independence of compiler IRs.
The main reason to have a target-independent IR is that there are many optimizations who are independent of the target. The idea, then, is to implement these optimizations once, on a target-independent IR, and not for every source-target combination.
This idea works great when we are dealing with optimizations which are actually target-independent. A canonical example is dead-code elimination. The characteristics of the target don't matter when deleting code. You just delete as much as you can and it will always be beneficial no matter what.
Things get more complicated when we have transformations which are target-independent but the decision-making involved is not. This requires a little analysis. When talking about a compiler optimization, it makes sense to think of it as having at least three components: the transformation, the legality constraints and the profitability analysis (shameless plug of my thesis because it talks about this distinction extensively). The transformation is the kind of changes we perform to the code, like moving, inserting or deleting code. For example, in dead-code elimination, we literally delete statements. In loop tiling, we strip-mine loops by certain factors and interchange them. Legality is concerned with when it is legal to perform the transformation, and profitability analysis is concerned with when it is profitable to do it, and with what parameters.
For many optimizations, the transformation is target-independent but the profitability analysis is not. For example, you don't need to know anything about the target to perform loop-tiling. This implies that the language/IR does not need to capture target details. For example, you can perform loop tiling in e.g., Rust. However, to do loop-tiling effectively, you do need to know about the target, for example, you should at least know the size of the caches.
This gave rise to a popular direction in optimizing compilers where the IR, on which transformations are performed, is target-independent, but there is also target-specific information flowing around so that passes can perform the transformations effectively. In that way, we have a nice trade-off where we still have one IR, but we perform optimizations specialized per target.
That's at least the narrative I had in my mind until recently...
Let's now take the most popular compiler IR ever, the LLVM IR, and examine its target (and later, source) independence. But first, we should think a bit harder about the definition of target independence.
The simple, and conventional, definition is that the IR does not have entities that are tied to a particular target. In that sense, the LLVM IR is mostly target-independent. For example, its core operations like add are not tied to a particular target.
In practice, the LLVM IR does not fully abide to this definition. For example, the inreg is target-specific and the same is true for a ton of intrinsics. But I would say these are not big problems, or at least, they are not that intellectually intriguing.
The more interesting problem is that the definition above is too simplistic to capture some adverse effects of target dependence that an independent IR is supposed to avoid. In particular, for an IR to be independent, we better add the constraint that whatever front-end lowers to it, does not need to know the resulting target. This is due to one of the main goals of target-independent IRs which is to reduce the explosion of source-target combinations.
In that sense, the LLVM IR is not target-independent, but the reasons are subtler. Consider this example. We have some simple C code translated, by Clang, to LLVM IR, for 3 different targets. Theoretically, the IR should have been the same for all three. The simplistic reason they are different is the Application Binary Interface (ABI). For example, with the x86-64 ABI (section 3.2.3), it's ok to treat the struct as a single integer, both for passing it and returning it 1. On the other hand, the MIPS ABI ("Argument Passing") e.g., tells us that if the function returns a struct, then the first argument should be a pointer to which the result will be stored.
But the question is: Why does the front-end have to deal with
it? Notice that in LLVM IR we could both pass, and return, a
struct by value. So, we would expect Clang to emit this
IR for all targets and let each different back-end translate
it to the target-specific form. To understand the discrepancy, we need
to look deeper into what ABIs define.
Notice that the need for an ABI, for a target, arises only when we are dealing with concepts that are higher-level than, or anyway not existent, in the assembly language (of that same target). For example, the reason we need calling conventions is that the concept of an argument does not exist e.g., in x86 assembly. It is a higher-level concept, which can however be implemented using this assembly. The problem is that it can be implemented in many different ways and so to have programs that function correctly, all compilers need to agree to implement it in the same way.
The problem of dependence in the IR arises when the concept is higher-level, or non-existent, in the IR too! For example, the LLVM IR does not have classes (but one of course can implement them in many ways). To see why this is a problem, suppose the ABI defines calling conventions specific to classes. This is e.g., a reality in the x86-64 ABI. It states: "If a C++ object has either a non-trivial copy constructor or a non-trivial destructor, it is passed by invisible reference ...".
The front-end can't implement classes arbitrarily, and then expect the back-end to apply the calling convention, because the concept of a class is lost in the translation! In other words, it will now be very hard for a back-end to, essentially, reverse-engineer, that certain sequences of instructions implement the concept of a class.
A subtler but similar example is something like the int
type in C, whose bit-width depends on the target. The LLVM IR does not
have such a type. It only has integers of a clearly specified width. A
front-end, then, needs to know the target, so that it knows what
bit-width to use for an int.
Given this problem, there are two solutions. The first is to translate such concepts using predictable (by the back-end) patterns, such that the back-end can recognize them. But this solution is unreliable and we need to be sure that the ABI will be applied perfectly. If, for example, the back-end fails to identify a class and apply a calling convention, the program can literally crash. The other solution is basically what LLVM employs, which is to have every front-end deal with the ABI.
Now, let's consider the drawbacks of the situation we are facing. The first and obvious one is that of the engineering effort and code duplication involved in all these front-ends replicating similar code just to deal with the ABI. This gave rise to libraries like llvm-abi.
Second, because the back-end is not responsible for the calling conventions, it actually is agnostic. This means that it will translate anything given to it, no matter if it agrees with the conventions. Since it is not the back-end that is responsible, it has to assume that whoever is, did the job correctly.
Finally, to return to our original problem, because we need different calling conventions based on the architecture, it means that LLVM IR is not really target-independent. You cannot generate IR without knowing the target. Furthermore, can you ship your LLVM IR to a different target than the one the front-end translated to? No. Can you combine two IR files generated for different targets? No.
But at least the IR is source-independent right? Right? Not necessarily. Similarly to our definition of target independence, I would say that an IR is source independent if it can express any source and if IR files for different sources can be combined. Given our discussion above, we can already see that the latter is not necessarily true. For example, can you combine IRs generated for the same target but originating from different source languages? Not necessarily. For example, if there was an ABI based on Rust, then even if we were compiling to the same target, it wouldn't necessarily match with the IR from C.
The former is not a given either. For example, apparently Rust had a hard time translating to LLVM IR. One example is that infinite loops are fine in Rust in cases where they are not fine in C++. Because the LLVM IR uses the C++ memory model, Rust simply could not translate to it.