CD Notes
Detailed guide to instruction selection techniques including tree pattern matching, dynamic programming, BURS, and practical approaches to choosing optimal machine instructions for intermediate code.
Overview
Instruction selection is the process of mapping intermediate representation operations to target machine instructions. The challenge lies in the many-to-many relationship: one IR operation may be implementable by several instruction sequences, and one machine instruction may implement multiple IR operations.
The Problem
Macro Expansion (Simple Approach)
Advantages
- Strategy: Replace each IR instruction with a fixed template.
- Templates:
- x = y + z
- x = y - z
- x = y
- if x goto L →
- Advantages: Simple to implement, fast compilation
- Example:
- t1 = a + b
- t2 = t1 + c
- ↑ Redundant! t1 was just stored to memory
- Better: Keep t1 in register, skip store and reload.
Disadvantages
- →
- →
- →
- LD R0, x; BNZ R0, L
- →
- →
Tree Pattern Matching
The most effective instruction selection technique represents IR as expression trees and machine instructions as tree patterns (tiles):
| IR Tree for | a[i] = b + 1 |
| │ Tile 1 | reg ← CONST c │ |
| │ MOVI Rd, #c cost | 1 │ |
| │ Tile 2 | reg ← MEM[addr] │ |
| │ LD Rd, [addr] cost | 4 │ |
| │ Tile 3 | reg ← reg + reg │ |
| │ ADD Rd, Rs1, Rs2 cost | 1 │ |
| │ Tile 4 | reg ← reg * reg │ |
| │ MUL Rd, Rs1, Rs2 cost | 3 │ |
| │ Tile 5 | reg ← MEM[reg + reg] │ |
| │ LD Rd, [Rs1, Rs2] cost | 4 │ |
| │ Tile 6 | MEM[reg] ← reg │ |
| │ ST [Rd], Rs cost | 4 │ |
| │ Tile 7 | reg ← reg + CONST c │ |
| │ ADDI Rd, Rs, #c cost | 1 │ |
| │ Tile 8 | MEM[reg + reg] ← reg │ |
| │ ST [Rd, Ri], Rs cost | 4 │ |
| │ Tile 9 | reg ← reg << CONST c │ |
| │ SHL Rd, Rs, #c cost | 1 │ |
| │ Tile 10 | reg ← MEM[reg + reg*CONST] │ |
| │ LD Rd, [Rs1, Rs2, #scale] cost | 4 │ |
Dynamic Programming Approach
| Algorithm | Optimal tiling using bottom-up dynamic programming |
| Example | Minimize cost for x = a + b*c |
| Tree | [=] |
| Node [b] | LD R, [b] cost = 4 |
| Node [c] | LD R, [c] cost = 4 |
| Node [*] | MUL R, Rb, Rc cost = 3 + 4 + 4 = 11 |
| Or | (if MAC available) keep for combined |
| Node [a] | LD R, [a] cost = 4 |
| Node [+] | ADD R, Ra, Rmul cost = 1 + 4 + 11 = 16 |
| Or | (if ADD-MEM available) cost might differ |
| Node [=] | ST [x], R cost = 4 + 16 = 20 |
BURS (Bottom-Up Rewrite System)
| reg | PLUS(reg, reg) { ADD Rd, Rs1, Rs2 } cost 1 |
| reg | PLUS(reg, CONST) { ADDI Rd, Rs, #c } cost 1 |
| reg | MEM(reg) { LD Rd, [Rs] } cost 4 |
| reg | MEM(PLUS(reg, CONST)) { LD Rd, [Rs+#c] } cost 4 |
| reg | MEM(PLUS(reg, reg)) { LD Rd, [Rs1+Rs2] } cost 4 |
| Tools | iburg, BURG, LLVM SelectionDAG |
Handling Special Cases
| x = x + 1 | INC [x] (instead of load-add-store) |
| x = y * 8 | SHL R, Ry, 3 |
| x = y / 4 | SHR R, Ry, 2 |
| x = y % 8 | AND R, Ry, 7 |
| x = (a>b) ? c : d | CMP a,b; CMOVG R,c; CMOVLE R,d |
| x = a + b*c | MAC R, Ra, Rb, Rc (single instruction on DSPs) |
Peephole Optimization in Instruction Selection
| Pattern | Redundant load after store |
| LD R1, [x] | MOV R1, R0 (value is in R0!) |
| Pattern | Redundant comparison |
| CMP R0, 0 | (eliminate, SUB already set zero flag) |
| Pattern | Strength reduction |
| MUL R0, R1, 3 | LEA R0, [R1 + R1*2] (x86 LEA trick) |
| Pattern | Combine operations |
| ADD R0, R0, R2 | LEA R0, [R2 + R1*4] |
LLVM's Approach: SelectionDAG
LLVM Instruction Selection Pipeline
LLVM IR → SelectionDAG → Legalized DAG → Selected DAG → Machine Instrs
1. Build DAG from IR (operations as nodes)
2. Legalize: replace unsupported ops with supported sequences
- i64 add on 32-bit machine → two i32 adds with carry
3. Combine: pattern-match complex instructions
- ADD + SHL → fused shift-add
4. Select: map DAG nodes to machine instructions using TableGen patterns
5. Schedule: order instructions for pipeline efficiency
TableGen pattern example
def : Pat<(add GR32:$src1, GR32:$src2),
(ADD32rr GR32:$src1, GR32:$src2)>;
def : Pat<(add GR32:$src, (load addr:$mem)),
(ADD32rm GR32:$src, addr:$mem)>;
Interview Questions
- Q: Why is optimal instruction selection NP-complete in general?
A: For DAG-shaped IR (with shared subexpressions), finding the minimum-cost covering is equivalent to solving an integer linear program. However, for tree-shaped IR, dynamic programming gives an optimal solution in linear time. Most practical systems use tree decomposition of DAGs.
- Q: How does instruction selection differ between RISC and CISC?
A: RISC has few, simple patterns (most operations need explicit load/store), making selection straightforward but producing more instructions. CISC has complex patterns (memory operands, combined addressing modes) offering more optimization opportunities but requiring more sophisticated pattern matching.
- Q: What is the role of legalization in LLVM's instruction selection?
A: Legalization ensures all IR operations are implementable on the target. It replaces unsupported types (i128 on 32-bit) with sequences of supported operations, and replaces unsupported operations (e.g., no hardware divide) with library calls or alternative instruction sequences.
- Q: How does instruction selection handle register pressure?
A: Instruction selection typically ignores register constraints (assumes infinite registers). However, some heuristics prefer tiles that minimize simultaneously live values. Register allocation happens as a separate phase and may require re-selection if spilling changes the optimal tiling.
- Q: What is the advantage of tree pattern matching over macro expansion?
A: Tree pattern matching considers larger context — it can match a subtree of multiple IR nodes to a single complex instruction. Macro expansion only sees one IR instruction at a time. The improvement can be 2-3x fewer instructions generated, especially on CISC machines with rich addressing modes.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Instruction Selection in Code Generation.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, code, generation, instruction, selection
Related Compiler Design Topics