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.
The instruction selection pass is one of the most expensive ones employed in the backend. A study compiling the functions of the ...