Intermediate Code Generation

After semantic analysis, the compiler translates the AST into an Intermediate Representation (IR) — a form that is:
- Lower-level than the source language (closer to machine code)
- Higher-level than actual assembly (still machine-independent)
- Easy to optimize
- Easy to translate to different target architectures

Why have an IR at all? The two-phase benefit:
- N source languages × M target architectures = N×M compilers without IR
- With IR: N front-ends + M back-ends = N+M components
- LLVM is the prime example: Clang (C front-end) + Rust + Swift all compile to LLVM IR, which then targets x86, ARM, RISC-V, WebAssembly

Three-Address Code (TAC):
The most common IR form. Each instruction has at most ONE operator and THREE addresses (operands). Every complex expression is broken into a sequence of simple assignments.

Forms:
- x = y op z (binary operation)
- x = op y (unary operation)
- x = y (copy)
- goto L (unconditional jump)
- if x goto L (conditional jump)
- x = y[i] (array access)
- x[i] = y (array assignment)
- x = call f, n (function call with n args)
- param x (push argument)
- return x

Temporaries: TAC introduces temporary variables (t1, t2, t3...) to hold intermediate values. These map to registers during code generation.

SSA (Static Single Assignment) form:
Modern compilers (LLVM, GCC) use SSA — every variable is assigned exactly once. Φ (phi) functions merge values from different control flow paths.
- Makes dataflow analysis much simpler
- Makes most optimizations easier to implement
- Every LLVM IR instruction is in SSA form

Basic Blocks and Control Flow Graph (CFG):
- Basic block: maximal sequence of instructions with no branches in or out (except at start/end)
- CFG: directed graph where nodes = basic blocks, edges = possible control flow
- Optimizations work on the CFG — dead code = unreachable blocks

LLVM IR — the real-world IR:
LLVM IR is typed, in SSA form, and explicitly manages memory via alloca/load/store. Clang, Rust, Swift, Kotlin/Native all compile to LLVM IR. You can inspect it with "clang -emit-llvm -S file.c".

1from dataclasses import dataclass, field
2from typing import Union, Optional
3
4# ── TAC Instructions ───────────────────────────────────
5@dataclass
6class TACBinOp:
7    result: str
8    left:   str
9    op:     str
10    right:  str
11    def __str__(self): return f"    {self.result} = {self.left} {self.op} {self.right}"
12
13@dataclass
14class TACCopy:
15    result: str
16    value:  str
17    def __str__(self): return f"    {self.result} = {self.value}"
18
19@dataclass
20class TACJump:
21    label: str
22    def __str__(self): return f"    goto {self.label}"
23
24@dataclass
25class TACCondJump:
26    condition: str
27    true_label:  str
28    false_label: str
29    def __str__(self): return f"    if {self.condition} goto {self.true_label} else {self.false_label}"
30
31@dataclass
32class TACLabel:
33    name: str
34    def __str__(self): return f"{self.name}:"
35
36@dataclass
37class TACReturn:
38    value: str
39    def __str__(self): return f"    return {self.value}"
40
41@dataclass
42class TACParam:
43    value: str
44    def __str__(self): return f"    param {self.value}"
45
46@dataclass
47class TACCall:
48    result: str
49    func:   str
50    nargs:  int
51    def __str__(self): return f"    {self.result} = call {self.func}, {self.nargs}"
52
53# ── TAC Generator ──────────────────────────────────────
54class TACGenerator:
55    def __init__(self):
56        self.instructions = []
57        self.temp_count   = 0
58        self.label_count  = 0
59
60    def new_temp(self) -> str:
61        self.temp_count += 1
62        return f"t{self.temp_count}"
63
64    def new_label(self) -> str:
65        self.label_count += 1
66        return f"L{self.label_count}"
67
68    def emit(self, instr):
69        self.instructions.append(instr)
70
71    def gen_expr(self, node) -> str:
72        if isinstance(node, Num):
73            return str(node.value)
74        if isinstance(node, Var):
75            return node.name
76        if isinstance(node, BinOp):
77            left  = self.gen_expr(node.left)
78            right = self.gen_expr(node.right)
79            temp  = self.new_temp()
80            self.emit(TACBinOp(temp, left, node.op, right))
81            return temp
82        if isinstance(node, UnaryOp):
83            operand = self.gen_expr(node.operand)
84            temp    = self.new_temp()
85            self.emit(TACBinOp(temp, "0", "-", operand))
86            return temp
87        raise ValueError(f"Unknown expr: {node}")
88
89    def gen_stmt(self, node):
90        if isinstance(node, Assign):
91            val = self.gen_expr(node.value)
92            self.emit(TACCopy(node.name, val))
93
94        elif isinstance(node, If):
95            cond = self.gen_expr(node.condition)
96            true_lbl  = self.new_label()
97            false_lbl = self.new_label()
98            end_lbl   = self.new_label()
99
100            self.emit(TACCondJump(cond, true_lbl, false_lbl))
101            self.emit(TACLabel(true_lbl))
102            for s in node.then_body:
103                self.gen_stmt(s)
104            self.emit(TACJump(end_lbl))
105            self.emit(TACLabel(false_lbl))
106            for s in node.else_body:
107                self.gen_stmt(s)
108            self.emit(TACLabel(end_lbl))
109
110        elif isinstance(node, Return):
111            val = self.gen_expr(node.value)
112            self.emit(TACReturn(val))
113
114    def generate(self, program):
115        for stmt in program:
116            self.gen_stmt(stmt)
117        return self.instructions
118
119# ── Test IR generation ─────────────────────────────────
120program = [
121    Assign("x", Num(10)),
122    Assign("y", BinOp(Num(2), "+", BinOp(Num(3), "*", Var("x")))),
123    If(
124        condition=BinOp(Var("x"), ">", Num(5)),
125        then_body=[Assign("result", BinOp(Var("y"), "-", Num(1)))],
126        else_body=[Assign("result", Num(0))],
127    ),
128    Return(Var("result")),
129]
130
131gen  = TACGenerator()
132code = gen.generate(program)
133
134print("Three-Address Code (TAC):")
135for instr in code:
136    print(instr)
137
138# ── Real LLVM IR (if clang available) ─────────────────
139print("
140Real LLVM IR from clang:")
141llvm_ir_example = """
142; clang -emit-llvm -S -O0 hello.c -o hello.ll
143; int add(int a, int b) { return a + b; }
144
145define i32 @add(i32 %a, i32 %b) {
146entry:
147  %a.addr = alloca i32          ; allocate stack slot for a
148  %b.addr = alloca i32          ; allocate stack slot for b
149  store i32 %a, i32* %a.addr   ; store arg into stack
150  store i32 %b, i32* %b.addr
151  %0 = load i32, i32* %a.addr  ; load a
152  %1 = load i32, i32* %b.addr  ; load b
153  %add = add nsw i32 %0, %1    ; add (no signed wrap)
154  ret i32 %add                  ; return result
155}
156; Every variable assigned exactly once → SSA form
157"""
158print(llvm_ir_example)