Understanding the instruction selection phase

Instruction selection is the process of transforming the LLVM IR into the SelectionDAG nodes (SDNode) representing target instructions. The first step is to build the DAG out of LLVM IR instructions, creating a SelectionDAG object whose nodes carry IR operations. Next, these nodes go through the lowering, DAG combiner, and legalization phases, making it easier to match against target instructions. The instruction selection then performs a DAG-to-DAG conversion using node pattern matching and transforms the SelectionDAG nodes into nodes representing target instructions.

Note

The instruction selection pass is one of the most expensive ones employed in the backend. A study compiling the functions of the SPEC CPU2006 benchmark reveals that, on average, the instruction selection pass alone uses almost half of the time spent in the llc tool with –O2, generating x86 code, in LLVM 3.0. If you are interested in knowing the average time spent in all –O2...