Creating machine instructions from the IR is a very important task in the backend. One common way to implement it is to utilize a DAG:
- First, we must create a DAG from the IR. A node of the DAG represents an operation and the edges model control and data flow dependencies.
- Next, we must loop over the DAG and legalize the types and operations. Legalization means that we only use types and operations that are supported by the hardware. This requires us to create a configuration that tells the framework how to deal with non-legal types and operations. For instance, a 64-bit value could be split into two 32-bit values, the multiplication of two 64-bit values could be changed to a library call, and a complex operation such as count population could be expanded into a sequence of simpler operations for calculating this value.
- After, pattern matching is utilized to match nodes in the DAG and replace them with machine instructions. We encountered such a pattern in the previous chapter.
- Finally, an instruction scheduler reorders the machine instructions into a more performant order.
This is just a high-level description of the instruction selection process via the selection DAG. If you are interested in more details, you can find it in the The LLVM Target-Independent Code Generator user guide at https://llvm.org/docs/CodeGenerator.htmlselectiondag-instruction-selection-process.
Furthermore, all backends in LLVM implement the selection DAG. The main advantage is that it generates performant code. However, this comes at a cost: creating the DAG is expensive, and it slows down compilation speed. Therefore, this has prompted LLVM developers to look for alternative and more desirable approaches. Some targets implement instruction selection via FastISel, which is only used for non-optimized code. It can quickly generate code, but the generated code is inferior to the one generated by the selection DAG method. In addition, it adds a whole new instruction selection method, which doubles the testing effort. Another method is also used for instruction selection called global instruction selection, which we’ll examine later in the Global instruction selection section.
In this chapter, we aim to implement enough of the backend to lower a simple IR function, like this:
define i32 @f1(i32 %a, i32 %b) {
%res = and i32 %a, %b
ret i32 %res
}
Moreover, for a real backend, much more code is needed, and we must point out what needs to be added for greater functionality.
To implement instruction selection via the selection DAG, we need to create two new classes: M88kISelLowering and M88kDAGToDAGISel. The former class is used to customize the DAG, for example, by defining which types are legal. It also contains the code to support the lowering of functions and function calls. The latter class performs DAG transformations, and the implementation is mostly generated from the target description.
There are several classes within the backend that we will be adding implementation to, and Figure 12.1 depicts the high-level relationship between the primary classes that we will be developing further:
Figure 12.1 – Relationship between the main classes