Instruction Selection — From IR to Target Machine Code
In this tutorial, you'll learn about Instruction Selection. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Instruction selection is the compiler backend phase that transforms machine-independent Intermediate Representation into target-specific machine instructions, choosing optimal sequences that minimize cost while preserving program semantics.
What You'll Learn & Why It Matters
In this tutorial, you will learn the core instruction selection algorithms — maximal munch, tree pattern matching with Dynamic Programming, and BURG-style bottom-up rewriting. Instruction selection directly determines code quality and is the most target-dependent phase in the compiler backend.
Real-world use: The LLVM backend uses a DAG-based instruction selector with pattern matching to emit optimized ARM, x86, RISC-V, and WebAssembly code. Durga Antivirus Pro uses instruction selection techniques to translate disassembled instructions into a canonical form for cross-architecture malware signature matching.
Prerequisites
You should understand intermediate representations and code generation basics. Familiarity with C and assembly language concepts is assumed.
The Instruction Selection Problem
Given a set of IR operations, select the best sequence of target machine instructions that implements each operation, considering addressing modes, register constraints, and instruction costs.
graph TD
subgraph "Instruction Selection Pipeline"
A[IR Tree / DAG] --> B[Pattern Matching]
B --> C{Candidate Patterns}
C --> D[Cost Evaluation]
D --> E[Optimal Selection]
E --> F[Machine Instructions]
end
subgraph "Target Description"
G[Instruction Patterns]
H[Cost Tables]
I[Register Constraints]
end
G --> B
H --> D
I --> E
style B fill:#2196F3,color:#fff
style D fill:#FF9800,color:#fff
style E fill:#4CAF50,color:#fff
Maximal Munch Algorithm
Maximal munch is the simplest instruction selection strategy: at each step, match the largest (most expensive) instruction pattern that covers the current IR node.
class MaximalMunchSelector:
def __init__(self):
self.patterns = [
(10, 'ADD_REG', self.match_add_reg),
(8, 'ADD_IMM', self.match_add_imm),
(6, 'LOAD_REG', self.match_load_reg),
(5, 'LOAD_IMM', self.match_load_imm),
(4, 'MUL_REG', self.match_mul_reg),
(3, 'STORE', self.match_store),
(2, 'MOVE', self.match_move),
(1, 'NOP', self.match_nop),
]
def select(self, ir_nodes):
selected = []
remaining = list(ir_nodes)
while remaining:
best_cost = -1
best_instr = None
best_match = None
for cost, name, matcher in self.patterns:
for node in remaining:
match = matcher(node)
if match and cost > best_cost:
best_cost = cost
best_instr = name
best_match = match
if best_instr:
selected.append(best_instr)
for consumed in best_match:
if consumed in remaining:
remaining.remove(consumed)
else:
break
return selected
def match_add_reg(self, node):
if node['op'] == 'ADD' and node.get('src2_type') == 'reg':
return [node]
def match_add_imm(self, node):
if node['op'] == 'ADD' and node.get('src2_type') == 'imm':
return [node]
def match_load_reg(self, node):
if node['op'] == 'LOAD' and node.get('src_type') == 'mem':
return [node]
def match_load_imm(self, node):
if node['op'] == 'LOAD' and node.get('src_type') == 'imm':
return [node]
def match_mul_reg(self, node):
if node['op'] == 'MUL':
return [node]
def match_store(self, node):
if node['op'] == 'STORE':
return [node]
def match_move(self, node):
if node['op'] == 'MOVE':
return [node]
def match_nop(self, node):
return False
ir = [
{'op': 'LOAD', 'src_type': 'imm', 'dest': 'r1', 'value': 42},
{'op': 'LOAD', 'src_type': 'mem', 'dest': 'r2', 'value': 'x'},
{'op': 'ADD', 'src2_type': 'reg', 'dest': 'r3', 'src': 'r1', 'src2': 'r2'},
]
selector = MaximalMunchSelector()
result = selector.select(ir)
for instr in result:
print(f"Selected: {instr}")
Expected output:
Selected: LOAD_IMM
Selected: LOAD_REG
Selected: ADD_REG
Tree Pattern Matching with Dynamic Programming
BURG-style instruction selection uses tree grammars and Dynamic Programming to find the optimal covering at each node.
class TreePatternMatcher:
def __init__(self):
self.rules = [
{'pattern': ('+', 'reg', 'reg'), 'cost': 1, 'instr': 'ADD r, a, b'},
{'pattern': ('+', 'reg', 'imm'), 'cost': 1, 'instr': 'ADDI r, a, b'},
{'pattern': ('*', 'reg', 'reg'), 'cost': 4, 'instr': 'MUL r, a, b'},
{'pattern': ('load', 'mem'), 'cost': 3, 'instr': 'LD r, [a]'},
{'pattern': ('load', 'imm'), 'cost': 1, 'instr': 'MOV r, a'},
{'pattern': ('+', ('load', 'imm'), ('load', 'imm')), 'cost': 2, 'instr': 'ADDI r, a, b -> const_folded'},
]
def cost_of(self, node, memo):
if id(node) in memo:
return memo[id(node)]['cost']
best_cost = float('inf')
best_rule = None
for rule in self.rules:
match_result = self.match_pattern(node, rule['pattern'])
if match_result is not None:
total = rule['cost']
for child_match in match_result:
total += self.cost_of(child_match, memo)
if total < best_cost:
best_cost = total
best_rule = rule
if best_rule:
memo[id(node)] = {'cost': best_cost, 'rule': best_rule}
else:
memo[id(node)] = {'cost': 0, 'rule': None}
return memo[id(node)]['cost']
def match_pattern(self, node, pattern):
if isinstance(pattern, tuple):
if not isinstance(node, tuple):
return None
if node[0] != pattern[0]:
return None
children = []
for i in range(1, len(pattern)):
if isinstance(pattern[i], tuple):
child_match = self.match_pattern(node[i], pattern[i])
if child_match is None:
return None
children.extend(child_match)
elif pattern[i] == '_':
pass
else:
if node[i] != pattern[i]:
return None
return children
return []
ir_tree = ('+', ('load', 'imm'), ('load', 'imm'))
matcher = TreePatternMatcher()
cost = matcher.cost_of(ir_tree, {})
print(f"Minimum cost: {cost}")
Expected output:
Minimum cost: 2
Addressing Mode Selection
Complex addressing modes (register+offset, scaled index) combine multiple IR operations into single instructions.
class AddressingModeSelector:
def select_addressing_mode(self, mem_ref):
if 'base' in mem_ref and 'offset' in mem_ref and 'scale' in mem_ref:
return f"[{mem_ref['base']} + {mem_ref['offset']} * {mem_ref['scale']}]"
if 'base' in mem_ref and 'offset' in mem_ref:
if isinstance(mem_ref['offset'], int) and 0 <= mem_ref['offset'] < 4096:
return f"[{mem_ref['base']} + #{mem_ref['offset']}]"
return f"[{mem_ref['base']} + {mem_ref['offset']}]"
if 'base' in mem_ref:
return f"[{mem_ref['base']}]"
if 'label' in mem_ref:
return mem_ref['label']
return "[unknown]"
selector = AddressingModeSelector()
refs = [
{'base': 'rbp', 'offset': -12},
{'base': 'rax', 'offset': 'rbx', 'scale': 4},
{'base': 'rsp'},
{'label': 'global_var'},
]
for ref in refs:
print(f" {ref} -> {selector.select_addressing_mode(ref)}")
Expected output:
{'base': 'rbp', 'offset': -12} -> [rbp + #-12]
{'base': 'rax', 'offset': 'rbx', 'scale': 4} -> [rax + rbx * 4]
{'base': 'rsp'} -> [rsp]
{'label': 'global_var'} -> global_var
Common Errors in Instruction Selection
Error 1: Missing Pattern for an IR Operation
Every IR operation must have at least one matching instruction pattern. Unmatched operations cause the instruction selector to fail or emit invalid code.
Error 2: Incorrect Cost Model
Assigning wrong costs can make the selector choose slower instruction sequences. Profile-guided cost estimation is essential for performance-critical Code Generation.
Error 3: Pattern Ordering in Maximal Munch
If larger patterns are not checked first, maximal munch selects suboptimal smaller patterns. Always sort patterns by decreasing cost before matching.
Error 4: Register Constraint Violation
Selected instructions may have implicit register constraints (fixed input/output registers) that conflict with the register allocator's assignments. Model these constraints in the pattern specification.
Error 5: Chain Rule Explosion
Long chains of rewriting rules can cause exponential blowup in tree pattern matching. Use Dynamic Programming memoization to ensure polynomial-time selection.
Practice Questions
Question 1
What is the maximal munch algorithm for instruction selection?
Show answer
Maximal munch is a Greedy Algorithm that always selects the largest (highest cost) instruction pattern that matches the current set of IR nodes. It consumes the matched nodes and repeats. While simple and fast, it may not find the globally optimal covering.Question 2
How does tree pattern matching with Dynamic Programming improve over maximal munch?
Show answer
Dynamic Programming evaluates all possible pattern coverings at each node and selects the one with minimum total cost. Unlike maximal munch, it finds the globally optimal instruction sequence by considering all combinations, though at higher computational cost.Question 3
Why are complex addressing modes important in instruction selection?
Show answer
Complex addressing modes (like base+offset+scale on x86) combine address calculation and memory access into a single instruction. Folding these operations saves instructions, reduces code size, and improves performance by eliminating separate arithmetic for address computation.Challenge
Implement an instruction selector for a RISC-V backend that translates a simple IR (load, store, add, sub, mul, div, branch) into RISC-V assembly. Handle immediate encodings (12-bit signed immediates), register spilling, and the RISC-V calling convention. Test with a function that computes factorial recursively.
FAQ
graph LR
A[IR Trees/DAGs] --> B[Instruction Selection]
B --> C[Selected Instructions]
C --> D[Instruction Scheduling]
D --> E[Register Allocation]
E --> F[Machine Code Emission]
style B fill:#2196F3,color:#fff,stroke-width:2px
Summary
Instruction selection translates IR operations into target-specific machine instructions, choosing optimal patterns based on cost models. Maximal munch offers fast greedy selection, while tree pattern matching with Dynamic Programming finds globally optimal sequences. Complex addressing modes and proper pattern coverage are critical for generating efficient machine code.
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro