CD Notes
Comprehensive introduction to intermediate code generation in compilers covering its purpose, types of intermediate representations, benefits of IR, and the role of intermediate code in the compilation pipeline.
Purpose of Intermediate Code
Intermediate code generation translates the syntax tree or abstract syntax tree from the front end into a lower-level representation that is closer to machine code but still machine-independent. This intermediate representation (IR) serves as the interface between the front end (language-specific) and the back end (machine-specific) of the compiler.
Position in Compiler Pipeline
| Source | Front End → Intermediate Code → Optimizer → Back End → Target |
| │ C ── | ┐ ┌──→ x86 │ |
| │ Java | ├──→ Common IR ──→ ├──→ ARM │ |
| │ Go ── | ┘ └──→ RISC-V │ |
Types of Intermediate Representations
High-level IR (close to source)
- Abstract Syntax Trees (AST)
- Directed Acyclic Graphs (DAG)
- High-level three-address code
Medium-level IR
- Three-address code (TAC)
- Static Single Assignment (SSA)
- Control Flow Graphs with basic blocks
Low-level IR (close to machine)
- Register Transfer Language (RTL)
- Virtual machine bytecode
- Low-level three-address code with machine ops
Level comparison
AST: if (a > b) x = a; else x = b;
TAC: t1 = a > b
if t1 goto L1
x = b
goto L2
L1: x = a
L2:
RTL: CMP r1, r2; BGT L1; MOV r3, r2; JMP L2; L1: MOV r3, r1; L2:
Three-Address Code Overview
The most common intermediate representation. Each instruction has at most three operands (two sources and one destination):
General forms
x = y op z (binary operation)
x = op y (unary operation)
x = y (copy/assignment)
goto L (unconditional jump)
if x relop y goto L (conditional jump)
param x (function parameter)
call f, n (function call, n arguments)
return x (function return)
x = y[i] (indexed access)
x[i] = y (indexed assignment)
x = &y (address-of)
x = *y (pointer dereference)
*x = y (pointer assignment)
Example: a = b * c + d * e
Three-address code
t1 = b * c
t2 = d * e
t3 = t1 + t2
a = t3
Translation Examples
| Source | if (a < b && c > d) x = y + z; |
| L1 | if c > d goto L2 |
| L2 | t1 = y + z |
| Source | while (i < n) { sum = sum + a[i]; i = i + 1; } |
| L1 | if i >= n goto L2 |
| Source | x = a[i][j] (2D array, row-major, element size w) |
Representations of Three-Address Code
| op | arg1 | arg2 | result |
|---|---|---|---|
| * | b | c | t1 |
| * | d | e | t2 |
| + | t1 | t2 | t3 |
| = | t3 | a | |
| # | op | arg1 | arg2 |
| 0 | * | b | c |
| 1 | * | d | e |
| 2 | + | (0) | (1) |
| 3 | = | a | (2) |
Properties of Good IR
Desirable properties
✓ Easy to produce from AST (front-end simplicity)
✓ Easy to translate to target code (back-end simplicity)
✓ Easy to optimize (transformation-friendly)
✓ Compact representation (memory efficiency)
✓ Machine-independent (retargetability)
✓ Explicit operations (no hidden semantics)
✓ Uniform level of abstraction
Real-world IRs
- LLVM IR: SSA-based, typed, well-suited for optimization
- GCC GIMPLE: C-like three-address code in SSA form
- Java Bytecode: stack-based IR for JVM
- .NET CIL: stack-based, supports generics
- WebAssembly: stack-based, portable binary IR
IR Generation from AST
Algorithm: Recursive tree traversal with code emission
function generate(node):
if node is a constant:
return node.value
if node is a variable:
return node.name
if node is binary_op:
left = generate(node.left)
right = generate(node.right)
temp = new_temp()
emit(temp, "=", left, node.op, right)
return temp
if node is assignment:
rhs = generate(node.expression)
emit(node.variable, "=", rhs)
if node is if_statement:
cond = generate(node.condition)
true_label = new_label()
end_label = new_label()
emit("if", cond, "goto", true_label)
generate(node.else_body)
emit("goto", end_label)
emit_label(true_label)
generate(node.then_body)
emit_label(end_label)Interview Questions
- Q: Why not compile directly from source to machine code?
A: Intermediate representation enables: (1) retargetability (one front end, many back ends), (2) machine-independent optimization, (3) modularity (front/back end developed independently), (4) language interoperability (different languages sharing an optimizer/back end). The indirection cost is minimal compared to benefits.
- Q: What is the difference between AST and three-address code as IR?
A: AST preserves source structure (nested expressions, blocks) and is good for source-level analysis. Three-address code linearizes computation into simple statements, making control flow explicit and enabling classical dataflow optimization. AST is higher-level; TAC is lower-level and closer to machine code.
- Q: Why does three-address code use temporary variables?
A: Temporaries hold intermediate results of subexpressions. In a = b + c * d, the multiplication result needs storage before the addition. Temporaries make every operation explicit with at most two source operands, simplifying optimization and code generation.
- Q: What is SSA form and why is it popular as an IR?
A: Static Single Assignment requires each variable to be defined exactly once. Different definitions of the same source variable get different SSA names (x₁, x₂). This makes def-use relationships trivial, simplifies many analyses, and enables efficient algorithms for constant propagation, dead code elimination, and register allocation.
- Q: How does the choice of IR level affect optimization quality?
A: Higher-level IRs preserve more program structure (loops, types) enabling high-level optimizations (loop transformations, devirtualization). Lower-level IRs expose machine-like details enabling low-level optimizations (instruction selection, scheduling). Modern compilers use multiple IR levels to capture both.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Introduction to Intermediate 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, intermediate, code, generation, introduction
Related Compiler Design Topics