Introduction

Imagine a city with a single bridge over a river. No matter which road you take into the eastern half, you must cross that bridge. The bridge dominates every destination on the far side.

The same idea appears at the heart of every compiler, every program analyzer, and every security tool that traces how data moves through code. Given a directed graph with a distinguished entry node, we say that node A dominates node B if every path from the entry to B passes through A. By definition the entry dominates itself and everything else; a node can have many dominators. The one closest to B in the domination order — the node that dominates B but is dominated by everything else that also dominates B — is called B's immediate dominator.

The collection of all immediate-dominator relationships forms a tree rooted at the entry. That tree is the dominator tree, and it encodes a remarkable amount of structure: loops, irreducible regions, and safe spots for code motion all become visible the moment you have it in hand.

Computing dominators naively would require checking every possible path — exponentially many in the worst case. The elegant insight of Thomas Lengauer and Robert Tarjan (1979) is that a single depth-first traversal plus a clever link-cut structure is almost enough: their algorithm runs in O(mα(m,n))O(m \alpha(m, n)) time on a graph with mm edges and nn nodes, where α\alpha is the inverse Ackermann function — for all practical purposes, linear time.

Try It: Control-Flow Dominators

The demo below shows a small control-flow graph. Each node is a program block (entry at the top). Click any node to highlight its dominators — the set of nodes that every path from entry must pass through to reach it.

<p class="hint">A control-flow graph with 7 nodes (entry = <b>0</b>). Click any node to see which nodes <b>dominate</b> it — every path from entry must pass through each highlighted dominator.</p>
<div id="canvas-wrap"><canvas id="cfg" width="480" height="340"></canvas></div>
<div class="status" id="status">Click a node to highlight its dominators.</div>
<div class="btns">
  <button id="reset-btn" type="button" class="ghost">Clear selection</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#canvas-wrap { display: flex; justify-content: center; }
canvas { border-radius: 10px; background: #f4f6f8; cursor: pointer; max-width: 100%; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Dominator Tree demo using the simple iterative algorithm.
// Graph: 7 nodes (0 = entry), edges define a small CFG with branches and a loop.
// Dominator definition: A dom B iff every path from entry to B passes through A.
// The immediate dominator tree is computed with the classic iterative bit-set approach.

const N = 7; // nodes 0..6
// Adjacency list (directed edges)
const ADJ = [
  [1, 2],    // 0 -> 1, 2
  [3],       // 1 -> 3
  [3, 4],    // 2 -> 3, 4
  [3],       // 3 -> 5
  [5],       // 4 -> 5
  [6, 1],    // 5 -> 6, 1  (back-edge 5->1 creates a loop)
  []         // 6 (exit)
];
// Reverse adjacency
const RADJ = Array.from({length: N}, () => []);
for (let u = 0; u < N; u++) for (const v of ADJ[u]) RADJ[v].push(u);

// --- Iterative dominator computation (bit-set) ---
function computeDoms() {
  // dom[v] = set of nodes that dominate v (as bitmask)
  const ALL = (1 << N) - 1;
  const dom = new Array(N).fill(ALL);
  dom[0] = 1; // entry only dominated by itself
  let changed = true;
  while (changed) {
    changed = false;
    for (let v = 1; v < N; v++) {
      let newDom = ALL;
      for (const p of RADJ[v]) newDom &= dom[p];
      newDom |= (1 << v);
      if (newDom !== dom[v]) { dom[v] = newDom; changed = true; }
    }
  }
  return dom;
}

// --- Immediate dominator: closest dominator (not the node itself) ---
function computeIdom(dom) {
  const idom = new Array(N).fill(-1);
  for (let v = 1; v < N; v++) {
    const doms = [];
    for (let u = 0; u < N; u++) if (u !== v && (dom[v] >> u & 1)) doms.push(u);
    // idom is the dominator dominated by all other dominators of v
    // = the one with the most bits set in dom that is still in doms
    let best = -1, bestCount = -1;
    for (const u of doms) {
      const cnt = doms.filter(w => dom[u] >> w & 1).length;
      if (cnt > bestCount) { bestCount = cnt; best = u; }
    }
    idom[v] = best;
  }
  return idom;
}

const DOM = computeDoms();
const IDOM = computeIdom(DOM);

// Dominators of node v = bits set in DOM[v]
function domsOf(v) {
  const result = [];
  for (let u = 0; u < N; u++) if (DOM[v] >> u & 1) result.push(u);
  return result;
}

// --- Layout: assign (x, y) positions for each node ---
// Layered by BFS depth
const DEPTH = new Array(N).fill(-1);
DEPTH[0] = 0;
const bfsQueue = [0];
while (bfsQueue.length) {
  const u = bfsQueue.shift();
  for (const v of ADJ[u]) {
    if (DEPTH[v] < 0) { DEPTH[v] = DEPTH[u] + 1; bfsQueue.push(v); }
  }
}
// Positions (canvas 480x340, padding 40)
const POS = [
  [240, 40],   // 0 entry
  [140, 120],  // 1
  [340, 120],  // 2
  [240, 200],  // 3
  [380, 200],  // 4
  [240, 280],  // 5
  [380, 280],  // 6
];
const R = 22; // node radius

// --- Drawing ---
const canvas = document.getElementById('cfg');
const ctx = canvas.getContext('2d');
let selected = -1;

function drawArrow(x1, y1, x2, y2, color) {
  // Shorten to node boundary
  const dx = x2 - x1, dy = y2 - y1;
  const len = Math.sqrt(dx*dx + dy*dy);
  const ux = dx/len, uy = dy/len;
  const sx = x1 + ux*R, sy = y1 + uy*R;
  const ex = x2 - ux*(R+2), ey = y2 - uy*(R+2);
  ctx.beginPath(); ctx.moveTo(sx, sy); ctx.lineTo(ex, ey);
  ctx.strokeStyle = color; ctx.lineWidth = 2; ctx.stroke();
  // Arrowhead
  const angle = Math.atan2(ey-sy, ex-sx);
  ctx.beginPath();
  ctx.moveTo(ex, ey);
  ctx.lineTo(ex - 10*Math.cos(angle-0.4), ey - 10*Math.sin(angle-0.4));
  ctx.lineTo(ex - 10*Math.cos(angle+0.4), ey - 10*Math.sin(angle+0.4));
  ctx.closePath(); ctx.fillStyle = color; ctx.fill();
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  const domSet = selected >= 0 ? new Set(domsOf(selected)) : new Set();

  // Draw edges
  for (let u = 0; u < N; u++) {
    for (const v of ADJ[u]) {
      const [x1,y1] = POS[u], [x2,y2] = POS[v];
      const isBackEdge = DEPTH[v] <= DEPTH[u];
      const color = isBackEdge ? '#e67700' : '#aaa';
      drawArrow(x1, y1, x2, y2, color);
    }
  }

  // Draw dominator-tree edges (dashed, blue) only if a node is selected
  if (selected >= 0) {
    for (let v = 1; v < N; v++) {
      if (IDOM[v] < 0) continue;
      const u = IDOM[v];
      const [x1,y1] = POS[u], [x2,y2] = POS[v];
      ctx.save();
      ctx.setLineDash([4,4]);
      ctx.strokeStyle = '#1d3557';
      ctx.lineWidth = 1.5;
      ctx.globalAlpha = 0.35;
      ctx.beginPath(); ctx.moveTo(x1, y1); ctx.lineTo(x2, y2); ctx.stroke();
      ctx.restore();
    }
  }

  // Draw nodes
  for (let v = 0; v < N; v++) {
    const [x, y] = POS[v];
    const isDom = domSet.has(v);
    const isSel = v === selected;
    ctx.beginPath(); ctx.arc(x, y, R, 0, 2*Math.PI);
    if (isSel) {
      ctx.fillStyle = '#e63946'; ctx.fill();
      ctx.strokeStyle = '#b02030'; ctx.lineWidth = 2.5; ctx.stroke();
    } else if (isDom) {
      ctx.fillStyle = '#1d9e6e'; ctx.fill();
      ctx.strokeStyle = '#0f6b49'; ctx.lineWidth = 2.5; ctx.stroke();
    } else {
      ctx.fillStyle = '#e8eef3'; ctx.fill();
      ctx.strokeStyle = '#8099b0'; ctx.lineWidth = 1.5; ctx.stroke();
    }
    ctx.fillStyle = isSel || isDom ? '#fff' : '#1d3557';
    ctx.font = 'bold 14px ui-monospace,monospace';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(v === 0 ? 'entry' : v.toString(), x, y);
  }
}

function nodeAt(mx, my) {
  for (let v = 0; v < N; v++) {
    const [x, y] = POS[v];
    if ((mx-x)**2 + (my-y)**2 <= R*R) return v;
  }
  return -1;
}

canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width / rect.width;
  const scaleY = canvas.height / rect.height;
  const mx = (e.clientX - rect.left) * scaleX;
  const my = (e.clientY - rect.top) * scaleY;
  const v = nodeAt(mx, my);
  if (v < 0) return;
  selected = (selected === v) ? -1 : v;
  if (selected >= 0) {
    const doms = domsOf(selected).filter(u => u !== selected);
    const domNames = doms.map(u => u === 0 ? 'entry' : u.toString());
    const idomLabel = IDOM[selected] >= 0 ? (IDOM[selected] === 0 ? 'entry' : IDOM[selected].toString()) : 'none';
    document.getElementById('status').textContent =
      selected === 0
        ? 'entry dominates itself (and everything else).'
        : fmt('Node %selected% is dominated by: %domNames% + itself. Immediate dominator: %idomLabel%.', { selected: selected, domNames: domNames.join(', '), idomLabel: idomLabel });
  } else {
    document.getElementById('status').textContent = 'Click a node to highlight its dominators.';
  }
  draw();
  // Log dominator info to console for verification
  console.log('DOM bitmasks:', DOM.map((d,i)=>`node${i}:${d.toString(2).padStart(N,'0')}`).join(' '));
  console.log('IDOM:', IDOM);
});

document.getElementById('reset-btn').addEventListener('click', () => {
  selected = -1;
  document.getElementById('status').textContent = 'Click a node to highlight its dominators.';
  draw();
});

draw();
// Log initial state for verification
console.log('Dominator tree ready. DOM bitmasks (LSB=node0):');
for (let v = 0; v < N; v++) console.log("  " + fmt('node %v%: dominated by', { v: v }), domsOf(v));
console.log('Immediate dominators:', IDOM);
Result
Console

Notice that the dominator relationship is asymmetric: if A dominates B it does not mean B dominates A. Also note that removing a dominator from the graph would disconnect the entry from everything it dominated — dominators are the true bottlenecks of control flow, and identifying them is the first step in every loop-optimization pass a compiler ever runs.

The Real Complexity

Dominators are a solved problem — but the path to an efficient algorithm was long.

  • Naive approach: to check whether A dominates B, remove A from the graph and see if B is still reachable from entry. Repeat for every (A, B) pair: O(n⋅(n+m))O(n \cdot (n + m)) time.
  • Iterative data-flow: treat domination as a lattice and propagate a bit-set for each node, iterating to a fixed point. Still O(n2)O(n^2) in the worst case but simple to implement; used in many teaching compilers.
  • Lengauer-Tarjan (1979): Thomas Lengauer and Robert Endre Tarjan published a landmark algorithm using depth-first spanning trees and a path-compression structure to compute the entire dominator tree in O(mα(m,n))O(m \alpha(m, n)) time — essentially linear for any real program. This is the algorithm used in GCC, LLVM, and virtually every production compiler.
  • Simple linear-time algorithm (Cooper et al., 2001): Keith Cooper, Timothy Harvey, and Ken Kennedy showed a simpler algorithm that is linear in practice (though not in the worst case) and is often faster on real CFGs due to cache behavior.

The dominator tree is not NP-hard, not undecidable, not even a Millennium problem — it is a clean algorithmic success story: a question that appears to need exponential search, tamed to near-linear time by one of the great insights of graph theory. Compare this with the halting problem where no algorithm can ever win, or P vs NP where we still do not know if winning is even possible.

Where It Matters

Dominator trees are the silent engine behind an enormous range of software tools:

  • Loop detection: a back edge in the depth-first tree (an edge from a node to one of its dominators) is precisely the definition of a loop header. Every loop-unrolling and vectorization pass starts here.
  • Static Single Assignment (SSA) form: placing φ-nodes at the right places in a CFG requires the dominance frontier — the set of nodes just outside each dominator's reach. SSA is the internal representation of GCC, LLVM, V8, and most modern compilers.
  • Code motion and hoisting: an expression can be moved to an earlier block only if that block dominates all uses of the expression. Without the dominator tree, this optimization is unsafe.
  • Security and taint analysis: to prove that a secret value cannot leak to an output, analysts check whether all paths to the output pass through a sanitizing node — a domination query.
  • Web critical-path rendering: browser engines model the render pipeline as a graph and use domination-style reasoning to decide which resources block the first paint.

Every time your compiler auto-vectorizes a loop, every time V8 hoists a constant out of a hot inner loop, the dominator tree was consulted first.

Conclusion

The dominator tree is a beautiful example of a problem that looks hard — "check every path from entry to target" — but yields to the right structural insight. Lengauer and Tarjan's 1979 algorithm showed that the entire tree can be built in barely more than linear time, turning what seemed like an exponential search into a routine preprocessing step.

Today the dominator tree is woven so deeply into the infrastructure of software that it is nearly invisible: it runs before every optimization pass in every production compiler, before every SSA construction, before every loop the CPU will eventually vectorize. The bridge analogy holds: you cannot understand where a program goes without first knowing which nodes it must pass through. That is the dominator tree's gift — and it is computed for free.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/dominator-tree/Content licensed under CC BY-NC 4.0.