Intermediate Representation

The AST is a tree of source structure. The IR is a flatter, language-agnostic representation suitable for optimization + codegen.

Three-Address Code (TAC):

t1 = b + c
t2 = a * t1
result = t2

Each instruction has at most 3 operands. Easy to generate from AST. Easy to emit assembly from.

AST:
Assign(result,
       Mul(Var(a),
           Add(Var(b), Var(c))))

TAC:
LOAD t1, b
LOAD t2, c
ADD  t3, t1, t2
LOAD t4, a
MUL  t5, t4, t3
STORE result, t5

SSA (Static Single Assignment):

• Each variable assigned exactly once.
• Phi functions at merge points to combine paths:

   if x > 0:
       y1 = 1
   else:
       y2 = -1
   y3 = phi(y1, y2)   # SSA merge

LLVM IR is SSA. Enables many optimizations cheaply (def-use chains trivial).

Control Flow Graph (CFG):

• Function decomposed into basic blocks (straight-line code).
• Edges between blocks for branches.
• IR opts work on CFG.

Basic block invariant: only entry is the first instruction; only exit is a branch/return at the end.

Real LLVM IR:

define i32 @add(i32 %a, i32 %b) {
  %tmp = add i32 %a, %b
  ret i32 %tmp
}

Typed, structured, designed for analysis.