CD Notes
Detailed exploration of code generator design principles including target machine models, instruction costs, addressing modes, and the systematic approach to building effective code generators.
Design Goals
A well-designed code generator must balance multiple competing objectives: producing correct code that faithfully implements the source program semantics, generating efficient target code that runs fast and uses memory wisely, and keeping the code generator itself maintainable and retargetable to different architectures.
Target Machine Model
The code generator works against an abstract model of the target machine:
Generic RISC Machine Model
┌─────────────────────────────────────────┐
│ Registers: R0, R1, ..., Rn-1 │
│ (general purpose, fast access) │
│ │
│ Memory: M[0], M[1], ..., M[max] │
│ (large, slow access) │
│ │
│ Instructions: │
│ LD Ri, M[addr] (load) │
│ ST M[addr], Ri (store) │
│ OP Ri, Rj, Rk (arithmetic) │
│ BR label (unconditional) │
│ CBR Ri, label (conditional) │
└─────────────────────────────────────────┘
Generic CISC Machine Model (x86-like)
┌─────────────────────────────────────────┐
│ Registers: EAX, EBX, ECX, EDX, ... │
│ Special: ESP (stack), EBP (frame) │
│ │
│ Addressing Modes: │
│ Direct: MOV EAX, [1000] │
│ Register: MOV EAX, EBX │
│ Indirect: MOV EAX, [EBX] │
│ Indexed: MOV EAX, [EBX+ECX*4] │
│ Immediate: MOV EAX, 42 │
│ │
│ Variable-length instructions │
│ Memory operands in most instructions │
└─────────────────────────────────────────┘
Instruction Costs
Cost model (simplified)
Register operation: 1 cycle
Memory load/store: 4-100 cycles (cache dependent)
Branch (predicted): 1 cycle
Branch (mispredicted): 15-20 cycles
Function call: 5-10 cycles
Division: 20-40 cycles
Cost-based instruction selection
x = y + 1
Option A (3 instructions, 2 memory accesses):
LD R0, y cost: 4
ADDI R0, R0, 1 cost: 1
ST x, R0 cost: 4
Total: 9 cycles
Option B (if y already in R1)
ADDI R1, R1, 1 cost: 1
(keep result in register for later use)
Total: 1 cycle
Speedup: 9x by keeping values in registers!
Addressing Modes and Code Quality
Register Allocation Strategy
Approaches to register allocation
1. Local (within basic block):
- Simple, fast
- Treats block boundaries as barriers
- Loads/stores at block entry/exit
2. Global (across basic blocks):
- Better performance
- More complex analysis
- Graph coloring approach
3. Interprocedural:
- Across function boundaries
- Respects calling conventions
- Maximum optimization potential
Register allocation pipeline
IR → Liveness Analysis → Interference Graph → Graph Coloring → Allocation
↓ (if fails)
Spilling
↓
Retry coloring
getReg() Function Design
The getReg function decides where to store the result of each computation:
| Algorithm getReg(instruction I | x = y op z): |
| Registers | R0, R1 (only 2 available) |
| Code | t1 = a + b; t2 = c + d; t3 = t1 * t2 |
| t1 = a + b: R0 empty | use R0. Result: R0=t1 |
| t2 = c + d: R1 empty | use R1. Result: R0=t1, R1=t2 |
| t3 = t1*t2 | t1 in R0, t2 in R1, both used here for last time |
Instruction Selection Using Tree Matching
| Pattern 1 | r ← MEM[const] matches leaf load |
| Pattern 2 | r ← r + r matches add node |
| Pattern 3 | r ← r * r matches mul node |
| Pattern 4 | r ← MEM[r + const] matches add+load combined |
| Tile 1 | R1 ← MEM[b] (load b) |
| Tile 2 | R2 ← MEM[c] (load c) |
| Tile 3 | R1 ← R1 * R2 (multiply) |
| Tile 4 | R2 ← MEM[a] (load a) |
| Tile 5 | R1 ← R2 + R1 (add) |
| Tile 6 | MEM[x] ← R1 (store) |
Handling Control Flow
| Three-address code | Generated code: |
| L1 | x = y + z BR L2 |
| goto L3 L1 | ADD R2, R3, R4 |
| L2 | x = y - z BR L3 |
| L3 | ... L2: SUB R2, R3, R4 |
| L3 | ... |
Code Generator Generator (CGG)
| │ pattern | reg ← reg + reg │ |
| │ asm | "ADD %0, %1, %2" │ |
| │ cost | 1 │ |
| │ pattern | reg ← MEM[reg + reg] │ |
| │ asm | "LDR %0, [%1, %2]" │ |
| │ cost | 4 │ |
| CGG reads description | produces code generator |
| Examples | BURG, BURS, iburg, LLVM TableGen |
Handling Data Types
| Integer addition | x = a + b |
| Floating-point addition | x = a + b |
| String concatenation | s = s1 + s2 |
| Array access | x = a[i] |
Interview Questions
- Q: How does a retargetable compiler handle different architectures?
A: It separates the code generator into a machine-independent algorithm and a machine description. The description specifies available instructions, registers, addressing modes, and costs. The algorithm (tree matching, graph coloring) works against this abstract description. Changing targets requires only a new description file — LLVM's approach with TableGen is a prime example.
- Q: What is the trade-off between compilation speed and code quality in code generation?
A: Fast code generation (O(n) algorithms) produces reasonable but suboptimal code — suitable for debug builds. High-quality generation (graph coloring, optimal instruction selection) takes O(n²) or more — suitable for release builds. Most compilers offer optimization levels (-O0 through -O3) to let users choose this trade-off.
- Q: How do RISC and CISC architectures affect code generator design?
A: RISC generators deal with more instructions (explicit loads/stores) but simpler instruction selection. CISC generators have complex addressing modes that can fold multiple operations into one instruction but require sophisticated pattern matching. RISC is easier to generate for; CISC can produce fewer instructions.
- Q: What role does the calling convention play in code generation?
A: The calling convention dictates how functions communicate: which registers pass arguments, which are caller/callee-saved, where the return value goes, and stack frame layout. The code generator must follow these rules at every call site and function entry/exit to ensure correct interaction between separately compiled modules.
- Q: Why is instruction scheduling important for modern processors?
A: Modern CPUs have deep pipelines (10-20 stages) and multiple execution units. Without scheduling, dependencies between consecutive instructions cause pipeline stalls. The code generator reorders independent instructions to fill latency gaps, potentially doubling throughput on superscalar processors.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Code Generator Design in Compiler Construction.
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, generator, code generator design in compiler construction
Related Compiler Design Topics