Data Flow Analysis in Compilers - Intuition, Equations, and Real Examples

Modern compilers don’t optimize code by guesswork.
They optimize by proving facts about programs.

Those facts are computed using Data Flow Analysis (DFA), the backbone of almost every serious compiler optimization.

In this article, we’ll build data flow analysis from first principles:

• what it means,

• how it works,

• and why every optimization pipeline depends on it.

Why Data Flow Analysis Exists?

Consider this code:

x = 5;
y = x + 1;
z = x + 1;

A human immediately sees:

• x + 1 is computed twice

• The second computation is redundant

A compiler can’t “see” that unless it can prove:

1. x still equals 5

2. x + 1 was already computed earlier

3. Nothing in between invalidated it

Data Flow Analysis computes exactly these kinds of facts.

Definition (informal):
Data flow analysis determines what is true about program variables at each point in the program.

Control Flow Graph (CFG): Where DFA Lives

Before analyzing data flow, we need structure.

Compilers convert code into a Control Flow Graph (CFG):

• Nodes → basic blocks (straight-line code)

• Edges → possible flow of execution

Every data flow analysis runs on the CFG, not directly on source code.

What Is a Data-Flow Fact?

A data-flow fact is information the compiler wants to know at some program point.

Examples:

Different analyses → different facts
Same framework → different meanings

Forward vs Backward Analysis

The direction of analysis depends on where the information flows from.

Forward Analysis

Information flows with execution (entry → exit).

Examples:

• Reaching Definitions

• Constant Propagation

• Available Expressions

Backward Analysis

Information flows against execution (exit → entry).

Examples:

• Live Variable Analysis

• Very Busy Expressions

Rule of thumb:
If a fact depends on the past → forward
If it depends on the future → backward

With this framework in place, we can look at some of the most common data flow analyses used in real compilers. Each of the following analyses uses the same DFA machinery - only the meaning of the facts changes.

1) Reaching Definitions (RD)

Question it answers:

Which assignments might have produced the current value of a variable?

Data-flow fact:

• A definition (assignment to a variable)

Direction:

• Forward

Meet operator:

• Union (⋃)

Sets:

• GEN(b) – definitions created in block b

• KILL(b) – other definitions of the same variable

• IN(b) – definitions that may reach the start of b

• OUT(b) – definitions that may reach after b

Why it matters:

• Enables constant propagation

• Enables copy propagation

• Explains where values come from

2) Live Variable Analysis (LVA)

Question it answers:

Will this variable be used again in the future?

Data-flow fact:

• A variable

Direction:

• Backward

Meet operator:

• Union (⋃)

Sets:

• GEN(b) – variables used before being defined in b

• KILL(b) – variables defined in b

• IN(b) – variables live at block entry

• OUT(b) – variables live at block exit

Why it matters:

• Dead code elimination

• Register allocation

3) Available Expressions (AE)

Question it answers:

Has this expression already been computed and not invalidated?

Data-flow fact:

• An expression (e.g., a + b)

Direction:

• Forward

Meet operator:

• Intersection (⋂)

Sets:

• GEN(b) – expressions computed in b that survive

• KILL(b) – expressions invalidated by assignments in b

• IN(b) – expressions available at block entry

• OUT(b) – expressions available at block exit

Why it matters:

• Common subexpression elimination

• Global redundancy elimination

4) Constant Propagation

Question it answers:

Does this variable have a known constant value here?

Data-flow fact:

• (variable → constant) mapping

Direction:

• Forward

Meet operator:

• Lattice meet (⊓), not simple set union/intersection

• Unlike the previous analyses, constant propagation uses a lattice rather than simple set operations, because information can be partially known (for example, unknown vs constant vs conflicting).

Sets (conceptual):

• GEN(b) – constant assignments in b

• KILL(b) – assignments that overwrite constants

• IN(b) – constants known at entry

• OUT(b) – constants known at exit

Why it matters:

• Eliminates computations

• Enables branch simplification

• Enables dead code elimination

Seeing these analyses side by side makes the underlying structure of data flow analysis explicit.

A unifying table (this is GOLD)

Although Reaching Definitions, Live Variables, Available Expressions, and Constant Propagation look different on the surface, they are all instances of the same underlying idea: compute facts, propagate them through control flow, and transform code based on what is proven to be true.

Once this pattern clicks, compiler optimization stops feeling magical and starts feeling systematic.