Dominator Tree Construction

Problem definition

A dominator of a basic block n in a CFG is any block that appears on every path from the entry to n. Finding dominators is a fundamental, decidable analysis used for optimizations like code motion, SSA construction, and control dependence.

The dominator sets satisfy:

The entry block n₀ dominates only itself.
Every other block n is dominated by itself plus the common dominators of its immediate predecessors.

Plain text algorithm

We compute dominators by repeating these steps until nothing changes:

Initialization:
- Set Dom(n₀) = {n₀}.
- For every other block n, set Dom(n) = B (the set of all blocks).
Update:
- For each non‑entry block n:
  1. Gather the dominator sets of all predecessors p ∈ preds(n).
  2. Intersect them to get the common dominators.
  3. Union the result with {n} (each block dominates itself).
  4. Set this as the new Dom(n).
Fixed‑point check:
- If any Dom(n) changed in this pass, repeat the Update step.
- Otherwise, stop—every dominator set is now correct.

Pseudo‑code

let B = set of all basic blocks
let ENTRY = entry block n₀

// Initialization
Dom[ENTRY] = { ENTRY }
for each n in B \ {ENTRY}:
  Dom[n] = B

// Fixed-point iteration
changed = true
while changed:
  changed = false
  for each n in B \ {ENTRY}:
    newSet = { n }
    intersect = B
    for each p in preds(n):
      intersect = intersect ∩ Dom[p]
    newSet = newSet ∪ intersect
    if newSet ≠ Dom[n]:
      Dom[n] = newSet
      changed = true

Mathematical Formulation

$$\mathrm{Dom}(n) = \begin{cases} \{n\} & \text{if }n = n_{0},\\[6pt] \{n\}\;\cup\;\displaystyle\bigcap_{p\in\mathrm{preds}(n)}\mathrm{Dom}(p) & \text{otherwise.} \end{cases}$$

Notation:

B — set of all basic blocks
n₀ — the entry block
Dom(n) — dominator set of block n
preds(n) — set of immediate predecessors of n
∩ — set intersection (“common to all”)
∪ — set union (“combine elements”)

Postdominator Analysis

A postdominator of a basic block n in a CFG is any block that appears on every path from n to the exit. This analysis is decidable and underpins control‑dependence, slicing, and safe cleanup insertions.

The postdominator sets satisfy:

The exit block e₀ postdominates only itself.
Every other block n is postdominated by itself plus the common postdominators of its immediate successors.

Plain text algorithm

We compute postdominators by repeating until convergence:

Initialization:
- Set pDom(e₀) = {e₀}, where e₀ is the exit block.
- For every other block n, set pDom(n) = B (all blocks).
Update:
- For each non‑exit block n:
  1. Collect each successor’s postdominator set pDom(s) for all s ∈ succs(n).
  2. Intersect them to find common postdominators.
  3. Union that with {n} (every block postdominates itself).
  4. Assign the result to pDom(n).
Fixed‑point check:
- If any pDom(n) changed, repeat Update.
- Else, stop—postdominators are stable.

Pseudo‑code

let B = set of all basic blocks
let EXIT = exit block e₀

// Initialization
pDom[EXIT] = { EXIT }
for each n in B \ {EXIT}:
  pDom[n] = B

// Fixed-point iteration
changed = true
while changed:
  changed = false
  for each n in B \ {EXIT}:
    newSet = { n }
    intersect = B
    for each s in succs(n):
      intersect = intersect ∩ pDom[s]
    newSet = newSet ∪ intersect
    if newSet ≠ pDom[n]:
      pDom[n] = newSet
      changed = true

Mathematical Formulation

$$\mathrm{pDom}(n) = \begin{cases} \{n\} & \text{if }n = e_{0},\\[6pt] \{n\}\;\cup\;\displaystyle\bigcap_{s\in\mathrm{succs}(n)}\mathrm{pDom}(s) & \text{otherwise.} \end{cases}$$

Notation:

B — set of all basic blocks
e₀ — the exit block
pDom(n) — postdominator set of block n
succs(n) — set of immediate successors of n
∩ — intersection (common to all)
∪ — union (combine elements)