CD Notes
Understanding target machine architectures for compiler code generation including RISC vs CISC, instruction sets, memory hierarchy, pipelining, and how architecture features influence code generation.
Introduction
The target machine architecture defines the hardware capabilities and constraints that the code generator must work within. Understanding the target architecture is essential for producing efficient code — a naive code generator that ignores architectural features can produce code 10-100x slower than an architecture-aware one.
RISC vs CISC Architectures
| Feature | RISC | CISC |
|---|---|---|
| Instructions | Simple, fixed-size | Complex, variable-size |
| Operands | Register-register only | Register and memory |
| Load/Store | Explicit (separate) | Implicit (in operations) |
| Instruction count | More instructions needed | Fewer instructions needed |
| Registers | Many (16-32+) | Few (6-8 general) |
| Addressing modes | Few (reg, imm, offset) | Many (10+) |
| Encoding | Fixed width (32-bit) | Variable (1-15 bytes) |
| Examples | ARM, MIPS, RISC-V | x86, VAX, 68000 |
Impact on code generation
Memory Hierarchy
Instruction Set Architecture (ISA) Features
Common instruction categories
1. Data Movement:
MOV, LOAD, STORE, PUSH, POP, LEA
2. Arithmetic/Logic:
ADD, SUB, MUL, DIV, AND, OR, XOR, NOT, SHL, SHR
3. Comparison/Branch:
CMP, TEST, JMP, JE, JNE, JL, JG, CALL, RET
4. Floating Point:
FADD, FMUL, FDIV, FSQRT, FLD, FST
5. SIMD/Vector:
ADDPS, MULPD, MOVAPS (process 4-16 values at once)
6. Atomic/Synchronization:
CAS, LOCK prefix, memory barriers
Special instructions relevant to compilers
LEA reg, [base + index*scale + disp] → address computation without memory access
CMOV cond, reg, reg/mem → conditional move (avoid branch)
BSF/BSR → bit scan (find first/last set bit)
POPCNT → population count
Addressing Modes
| a[i] | MOV EAX, [base_a + 4*ECX] (scaled indexed) |
| p->x | MOV EAX, [EBX + offset_x] (based) |
| *p | MOV EAX, [EBX] (indirect) |
Pipelining and Hazards
Classic 5-stage pipeline
IF → ID → EX → MEM → WB
(Fetch, Decode, Execute, Memory, Writeback)
Pipeline hazards that code generators must consider
1. Data Hazard (RAW - Read After Write):
ADD R1, R2, R3 ; R1 written in WB stage (cycle 5)
SUB R4, R1, R5 ; R1 needed in EX stage (cycle 3) ← STALL!
Solution - instruction scheduling
ADD R1, R2, R3
LD R6, [x] ; independent instruction fills gap
SUB R4, R1, R5 ; R1 now ready via forwarding
2. Control Hazard (branches):
BEQ R1, R0, target ; branch outcome known late
ADD R2, R3, R4 ; might be wrong instruction!
Solutions: branch prediction, delay slots, predication
3. Structural Hazard:
Two instructions need same hardware unit simultaneously
Solution: schedule to avoid conflicts
Modern out-of-order CPUs handle most hazards in hardware,
but code scheduling still helps in-order cores (embedded, mobile).
Superscalar and VLIW
| Compiler hint | avoid false dependencies, schedule for resource balance |
| │ Slot 1 | ADD │ Slot 2: MUL │ Slot 3: LD │ (one VLIW word) |
| Compiler responsibility | find independent operations to fill slots |
| Empty slots | NOP (wasted hardware) |
Calling Conventions
| Arguments | RDI, RSI, RDX, RCX, R8, R9 (integers) |
| Return | RAX (integer), XMM0 (float) |
| Caller-saved | RAX, RCX, RDX, RSI, RDI, R8-R11 |
| Callee-saved | RBX, RBP, R12-R15 |
| Stack | 16-byte aligned before CALL |
| Arguments | R0-R3 (first 4 words) |
| Return | R0 (or R0:R1 for 64-bit) |
| Caller-saved | R0-R3, R12 |
| Callee-saved | R4-R11 |
| Stack | 8-byte aligned |
SIMD and Vectorization
| Example | Add arrays (scalar vs vector) |
| Scalar (4 iterations) | Vector (1 iteration for 4 elements): |
| for i in 0..3 | MOVAPS XMM0, [a] ; load 4 floats |
Interview Questions
- Q: How does the memory hierarchy affect code generation?
A: The code generator arranges data access patterns for cache efficiency (spatial/temporal locality), keeps hot variables in registers, uses prefetch instructions for predictable access patterns, and structures loop nests for cache blocking. A cache miss penalty (100+ cycles) dwarfs instruction-level optimizations.
- Q: Why do RISC machines typically have more registers than CISC?
A: RISC load/store architecture requires explicit register-to-register operations, so more registers reduce load/store frequency. CISC can operate directly on memory, needing fewer registers. RISC compensates for simpler instructions with more registers — both approaches aim to minimize memory traffic.
- Q: What is the role of branch prediction in code generation?
A: Branch predictors guess branch outcomes to keep the pipeline full. Code generators can help by: (1) arranging code so the likely path is fall-through, (2) using branch hints where available, (3) replacing branches with conditional moves when profitable, (4) profile-guided optimization to align branch predictions with actual behavior.
- Q: How does a compiler exploit instruction-level parallelism?
A: The compiler schedules independent instructions close together so the CPU's execution units stay busy. It unrolls loops to expose more parallelism, uses SIMD instructions for data-parallel operations, and on VLIW architectures, explicitly packs parallel operations into instruction bundles.
- Q: What is the trade-off between code size and execution speed?
A: Smaller code fits better in instruction cache (fewer cache misses) but may use more instructions per operation. Larger code (loop unrolling, inlining, SIMD) runs faster per iteration but may thrash the I-cache. The optimal balance depends on working set size and cache capacity.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Target Machine Architecture for 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, target, machine
Related Compiler Design Topics