Instruction Selection
What you'll learn: You'll learn how compilers choose the best machine instructions to implement each intermediate-representation operation.
The Translation Challenge
After generating intermediate representation (IR) like three-address code or SSA form, the compiler must convert each IR operation into actual machine instructions that the target CPU understands. This is instruction selection—mapping abstract operations to concrete hardware commands.
Balancing Multiple Goals
Here's where it gets interesting: there's rarely one "correct" instruction for an IR operation. Modern CPUs offer multiple ways to accomplish the same task, and the compiler must balance competing priorities:
- Code size: Fewer, compact instructions reduce memory footprint
- Execution speed: Some instructions execute faster than others
- Register usage: Complex instructions might require more registers, complicating register allocation
The Grocery Shopping Analogy
Think of instruction selection like choosing how to buy ingredients. For "get 12 eggs," you could:
- Buy one dozen carton (compact, efficient)
- Buy two 6-egg cartons (flexible, uses more space)
- Buy 12 individual eggs (maximum control, very inefficient)
All accomplish the goal, but the best choice depends on your constraints: storage space, cost, and how you'll use them.
Real-World Example
Consider the IR operation a = b + 4. On x86, you might select:
ADD reg, 4— fast, modifies register directlyLEA reg, [reg + 4]— preserves original, useful for address calculationsINCfour times — smallest code size but slowest
Different contexts demand different selections. A space-constrained embedded system favors compact code; a performance-critical loop wants the fastest option.
Key Takeaway: Instruction selection translates IR operations into machine code by choosing instructions that optimize for code size, execution speed, and register pressure based on the target architecture and context.