Linear IR vs Graph-Based IR
What you'll learn: You'll understand the difference between representing program instructions as a flat list versus an explicit graph structure.
When a compiler translates your source code into an intermediate representation (IR), it must choose how to organize that information. Two fundamental approaches exist: linear IR and graph-based IR.
Linear IR: Sequential Instruction Lists
Linear IR represents programs as a straightforward sequence of instructions, much like reading lines in a text file. Three-address code (TAC) is a classic example:
t1 = x + y
t2 = t1 * z
return t2
Each instruction follows the previous one. Control flow (jumps, branches) is handled with explicit labels and jump instructions. It's simple, compact, and easy to emit during compilation.
Analogy: Think of linear IR like turn-by-turn driving directions written on paper—you follow them line by line.
Graph-Based IR: Explicit Structure
Graph-based IR organizes instructions as nodes in a graph, with edges explicitly showing relationships. Control flow graphs (CFGs) show how basic blocks connect. SSA form uses a data-flow graph where edges show which instruction produces the value another consumes.
In a graph representation, dependencies are visible—you can see that instruction B uses the result of instruction A because there's an edge connecting them.
Analogy: This is like a visual flowchart where boxes and arrows show exactly how each step depends on others.
The Key Difference
Linear IR requires you to infer relationships by analyzing the sequence. Graph-based IR makes those relationships explicit in its structure. Graph-based IR excels at optimization because dependencies are immediately apparent—you don't need to reconstruct control flow or trace variable uses. Linear IR is simpler to generate and more space-efficient.
Key Takeaway: Linear IR stores instructions sequentially (analyze to find dependencies), while graph-based IR explicitly encodes control and data relationships as edges (dependencies visible by inspection).