Course contentsShow
← Computer Science
Lesson 2044 of 2,87246. Compilation and InterpretationFree lesson

Linear IR vs Graph-Based IR

Compare sequential instruction lists with graph structures that explicitly represent control and data dependencies.

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).