Instruction selection

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, instruction selection is the stage of a <a href="/facts/Compiler/WNfCDFJe">compiler</a> backend that transforms its middle-level <a href="/facts/Intermediate_representation/s0qRrbfh">intermediate representation</a> (IR) into a low-level IR. In a typical compiler, instruction selection precedes both <a href="/facts/Instruction_scheduling/5GuldkLY">instruction scheduling</a> and <a href="/facts/Register_allocation/rB1vkhxU">register allocation</a>; hence its output IR has an infinite set of pseudo-registers (often known as temporaries) and may still be – and typically is – subject to <a href="/facts/Peephole_optimization/B2XLWj3K">peephole optimization</a>. Otherwise, it closely resembles the target <a href="/facts/Machine_code/bgdQ1Fxf">machine code</a>, <a href="/facts/Bytecode/EPkMFR7M">bytecode</a>, or <a href="/facts/Assembly_language/7XuV0cla">assembly language</a>.
For example, for the following sequence of middle-level IR code

t1 = a
t2 = b
t3 = t1 + t2
a = t3
b = t1

a good instruction sequence for the <a href="/facts/X86/Kypq5fgu">x86 architecture</a> is

MOV EAX, a
XCHG EAX, b
ADD a, EAX

For a comprehensive survey on instruction selection, see.

Instruction selection open-in-new

Instruction selection