Course contentsShow
← Computer Science
Lesson 2053 of 2,87246. Compilation and InterpretationFree lesson

Instruction Selection

Choosing optimal machine instructions for IR operations balances code size, speed, and register usage.

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 directly
  • LEA reg, [reg + 4] — preserves original, useful for address calculations
  • INC four 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.