Global instruction selection – Instruction Selection

Instruction selection via the selection DAG produces fast code, but it takes time to do so. The speed of the compiler is often critical for developers, who want to quickly try out the changes they’ve made. Usually, the compiler should be very fast at optimization level 0, but it can take more time with increased optimization levels. However, constructing the selection DAG costs so much time that this approach does not scale as required. The first solution was to create another instruction selection algorithm called FastISel, which is fast but does not generate good code. It also does not share code with the selection DAG implementation, which is an obvious problem. Because of this, not all targets support FastISel.

The selection DAG approach does not scale because it is a large, monolithic algorithm. If we can avoid creating a new data structure such as the selection DAG, then we should be able to perform the instruction selection using small components. The backend already has a pass pipeline, so using passes is a natural choice. Based on these thoughts, GlobalISel performs the following steps:

1. First, the LLVM IR is lowered into generic machine instructions. Generic machine instructions represent the most common operation found in real hardware. Note that this translation uses the machine functions and machine basic blocks, which means it directly translates into the data structures used by the other parts of the backend.
2. The generic machine instructions are then legalized.
3. After, the operands of generic machine instructions are mapped to register banks.
4. Finally, the generic instructions are replaced with real machine instructions, using the patterns defined in the target description.

Since these are all passes, we can insert as many passes as we want in between. For example, a combiner pass could be used to replace a sequence of generic machine instructions with another generic machine instruction, or with a real machine instruction. Turning these additional passes off increases the compilation speed while turning them on improves the quality of the generated code. Hence, we can scale as we need.

There is another advantage in this approach. The selection DAG translates basic block by basic block, but a machine pass works on a machine function, which enables us to consider all basic blocks of a function during instruction selections. Therefore, this instruction selection method is called global instruction selection (GlobalISel). Let’s have a look at how this approach works, starting with the transformation of calls.