Reaching definitions analysis in Compiler Design - Time & Space Complexity

Time Complexity: Reaching definitions analysis

O(n * e)

Understanding Time Complexity

Analyzing time complexity helps us understand how the cost of reaching definitions analysis grows as the program size increases.

We want to know how the number of operations changes when the number of program statements grows.

Scenario Under Consideration

Analyze the time complexity of the following reaching definitions analysis algorithm.

for each block in program:
  in[block] = empty set
  out[block] = empty set

repeat
  for each block in program:
    in[block] = union of out[pred] for all predecessors pred
    out[block] = gen[block] union (in[block] - kill[block])
until in and out sets do not change
    

This code computes which variable definitions can reach each block by repeatedly updating sets until they stabilize.

Identify Repeating Operations

Identify the loops and repeated set operations.

• Primary operation: Iterating over all blocks repeatedly to update in and out sets.
• How many times: The outer loop repeats until no changes occur, which depends on program size and control flow.

How Execution Grows With Input

As the number of blocks (n) increases, the number of updates grows roughly with n times the number of iterations needed for sets to stabilize.

Input Size (n)	Approx. Operations
10	About 100 to 200 updates
100	Thousands of updates
1000	Hundreds of thousands of updates

Pattern observation: The work grows more than linearly because each iteration updates all blocks and repeats until stable.

Final Time Complexity

Time Complexity: O(n * e)

This means the time grows with the number of blocks times the number of edges in the control flow graph, reflecting repeated updates until stability.

Common Mistake

[X] Wrong: "The analysis finishes in just one pass over the blocks."

[OK] Correct: The sets depend on predecessors and need multiple passes to stabilize, so one pass is not enough.

Interview Connect

Understanding how data flows through a program and how analysis scales is a valuable skill for compiler design and optimization tasks.

Self-Check

"What if we used a worklist algorithm that only updates blocks when their inputs change? How would the time complexity change?"