Global 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...