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

Control Flow Graphs (CFGs)

Learn how IR instructions are organized into basic blocks connected by edges representing control flow.

Control Flow Graphs (CFGs)

What you'll learn: How compilers organize intermediate representation (IR) instructions into connected blocks that make control flow explicit and analyzable.

The Core Idea

A Control Flow Graph (CFG) is a graphical representation of all possible execution paths through a program. It takes your IR instructions—like Three-Address Code or SSA form—and organizes them into basic blocks connected by edges that show how control can jump from one block to another.

Think of a CFG like a flowchart for your code. Each box (basic block) contains a straight-line sequence of instructions with no jumps in the middle. The arrows (edges) between boxes show where execution can go next: following sequentially, branching on a condition, or jumping to a loop.

Basic Blocks and Edges

A basic block is a maximal sequence of consecutive instructions where:

  • Control enters only at the beginning
  • Control leaves only at the end
  • No internal branching or jumps

For example, these TAC instructions form one basic block:

x = a + b
y = x * 2
z = y - 3

But when you encounter a conditional (if z < 10 goto L1) or a label (L1:), you must start a new block. The CFG connects these blocks with edges representing possible control transfers.

Why CFGs Matter

CFGs make the program's structure explicit for analysis and optimization. Each edge tells you "execution might flow this way." By walking the graph, compilers can perform optimizations like dead code elimination, loop detection, and register allocation—all of which we'll explore later using the CFG structure.

Key Takeaway: Control Flow Graphs organize IR instructions into basic blocks connected by edges, making all possible execution paths explicit and enabling powerful compiler analyses and optimizations.