Dominance and reachability

Read first: Visiting a graph

An edge list says where each statement can go next, not where a branch ends. A branch's arms rejoin at a statement on every path to the exit, and only the first such statement will do: resuming at a later one copies code into both arms. Proving it with a full candidate set per statement makes every visit cost work in proportion to the method's size.

In the diamond below, A's arms rejoin at D. The set method and the pointer method both find it in 12 visits, 6 to settle and 6 to confirm; the pointer method's visits are cheaper, because each statement holds one name rather than up to seven. In the loop graph further down, a backward walk from L2 that stops at T finds the body {T, L1, L2}.

A statement post-dominates another if every path from that one to the exit passes through it.

The example

The same diamond as visiting a graph: A branches, one arm is B1, B2, B3, the other is C, both reach D, and E is the end.

flowchart TD
    A --> B1
    A --> C
    B1 --> B2
    B2 --> B3
    B3 --> D
    C --> D
    D --> E

The question: once A branches, what is the first statement both arms are guaranteed to reach? That is A's immediate post-dominator. The table gives it for every statement in the graph above, and A's row, in amber, is the answer.

Every other row has one way out: B1's only successor is B2, so that is the next statement it must reach, and the same holds for B2, B3, C and D. Only A's row needs both arms compared. The next two sections compute this table two ways and arrive at the same six rows. A second graph, with a loop, comes in Loops.

The slow way: a full set per statement

Give every statement except E a candidate set, start each one as large as possible, and shrink it by the rule in the box, over and over, until nothing shrinks any further. This is Allen and Cocke's iterative formulation,^[1] mirrored to look at successors. Statements are visited in the order D, B3, C, B2, B1, A, each after everything it points to; the fast way uses the same order, for a fair comparison. Diagrams in the walk mark the node a step is working out in amber.

The box's second line does real work in step 6, A, the one visit with two successors: {B1,B2,B3,D,E} ∩ {C,D,E} = {D,E}. The stop line is step 10, where round 2 has changed nothing.

Immediate post-dominator, read off at the end, is the member of each set — other than the statement itself — whose own set is largest: for A, the choice in step 6's set is between D (set size 2) and E (size 1), so D wins, matching the example's table. Six statements, two rounds, twelve visits — though every set was already final after round 1 (steps 1–6), because this graph has no cycles and each statement was visited after everything it points to. Round 2 (steps 7–10), and its whole-collection comparison, only confirms that. The pointer method below needs the same confirming pass on any graph with a loop, so this round is not where the two differ.

The fast way: one pointer per statement

Carry one pointer per statement — its best guess at its immediate post-dominator — instead of a set. This is Cooper, Harvey and Kennedy's algorithm.^[2] At each statement, the new guess is the meeting point of its already-visited successors' pointers, found with two "fingers" by the rule in the box. Like the set version, it repeats passes until one changes nothing.

For post-dominators the postorder is of the reversed graph, walked from the exit, and a lower number means farther from the exit. Steps 1–5 below have one successor each, so the meeting point is that successor. Step 6, A, is where the fingers move: the B1 finger climbs B2, B3, D, then the C finger steps to D.

Same answers as the slow walk's final row, and no statement ever held more than one other statement's name at a time: the chips in step 6 are the whole state. Like the set version, it was settled after one pass only because this graph has no cycles; it still needs a round 2 that changes nothing before it can stop — the same twelve visits. The saving is in what each visit costs.

The two compared

The visits row is identical; the rows above and below it are where the two differ. On six statements the difference is not worth caring about. The per-visit cost is what stops scaling gently: a set of size up to n, compared across all n statements, every round, is n² work per round. A chain-walk is bounded by how far apart two pointers' chains are, which in practice is a handful of hops, not the size of the whole method. Where this is used has the numbers from a method large enough for that difference to be the whole story.

Post-dominators: looking forward

The slow walk's final sets, gathered into one table, are the answer to a question worth naming: which statements is execution guaranteed to reach on the way out, no matter which way it leaves? Each member of a row is a post-dominator of that row's statement.

The closest member of each set, excluding the statement itself, is its immediate post-dominator, the example's table. Notice A's row has two post-dominators besides itself, D and E — both arms are forced through each of them. D is the immediate one because it comes first: every path from A to E passes through D, so D is closer, and "closest" is the question being asked. Keep that row in mind for what goes wrong.

Dominators: looking backward

The mirror question: pick a statement and ask which earlier statements execution is guaranteed to have already passed through to get there, no matter which way it arrived. To reach B3 in the diamond: always through B2, always through B1, always through A — no other way in. Each of those dominates B3, as B3's row below says. C does not — the other arm reaches B3 without it.

Of everything dominating B3, the closest — B2 — is its immediate dominator. Chaining immediate dominators (A → B1 → B2 → B3) is the one unavoidable route in. The loop section below needs this direction: a back edge is recognised by its target dominating its source.

Loops: reachability with a stopping point

A different question needs no sets or pointers at all: which statements belong to a loop — the backward walk below, bounded at the header, is Aho, Sethi and Ullman's.^[3] Take the loop from visiting a graph. Below, amber marks the statement a step is currently taking off the worklist; a bordered node marks a statement already confirmed as part of the loop body.

flowchart TD
    T --> X1
    T --> L1
    X1 --> X2
    L1 --> L2
    L2 -.->|back edge| T

L2 → T is the back edge, in both of the senses the word gets used: it is the arrow DFS found going to a statement still on its own path, and its target, T, dominates its source, L2 — every path to L2 goes through T. On a reducible graph the two senses always coincide; where they do not, the graph has a loop with more than one entry (see reducibility). A natural loop needs the second sense, and T is this loop's header. The loop's body is everything reachable walking backward from L2, with one rule: stop expanding the moment the walk reaches T, rather than following whatever leads into T from outside the loop.

The box's "stop there" line is step 1, where T comes off the list and its predecessors are left alone. The last line is step 2, which adds L1, and step 3, where L1's predecessor T is already in the body.

Loop body: {T, L1, L2}, the last step's chips. X1 and X2 are never reached by this walk at all — the other arm out of T, outside the loop — and nothing about them had to be inspected to know that, which is why they never once appear bordered in the diagrams above. The same bounded backward walk, with no stopping point, also answers "what can reach the end" (which decides which statements have a post-dominator at all — see what goes wrong) and, run forward instead of backward, "what is reachable from the start."

Where this shows up in reverse engineering

Dominance and reachability are the first things a tool needs once it has a control-flow graph and wants to say something about it in English, or in another language's syntax, rather than just a list of edges. Each use below rests on one of this page's answers, gathered here:

• Narrating an unfamiliar method or paragraph before a human — or a model — tries to explain what it does: finding where a branch's two arms reunite (D, the first chip), and exactly which statements belong to a loop (T, L1, L2, and not X1, X2), is the structural skeleton any such narration is built on top of. Get the loop body wrong and the narration describes the wrong statements as repeating.
• Reconstructing structured source from a control-flow graph — the core move inside any decompiler or legacy transpiler — needs a branch's immediate post-dominator before it can emit a single if/else: that is the one statement guaranteed to run after either arm, the natural point to resume straight-line code.
  if at Aarms: B1, B2, B3 | Cresume at D
  The first fragment under what goes wrong is the diamond emitted that way.
• A prerequisite, not a substitute, for reducibility: dominance alone describes a region cleanly only once that region is known to have a single entry per loop, as the loop graph's T is. An irreducible region needs restructuring first — this page's techniques are what the pages after it build on, not a way around them.

What goes wrong

• Taking any post-dominator for the immediate one. A's strict post-dominators are D and E, and both arms are forced through each. But E is not the closest: every path from A to E passes through D first, so D is the immediate one. A structuring tool that resumed straight-line code at E would put D inside both arms of the if/else. The diamond, resumed at D and then at E:

  if A            -- resume at D
      B1; B2; B3
  else
      C
  end
  D
  E

  if A            -- resume at E
      B1; B2; B3; D
  else
      C; D
  end
  E

  The second fragment runs the same statements, but D is written twice and now reads as part of each arm.

• Keeping the whole candidate set instead of a chain of pointers. It is the natural first way to write this down, it gives the right answer, and on a method of a few hundred statements nobody will ever notice it is doing more work than it needs to. The cost only shows up on the methods large enough to matter, which is exactly when nobody is watching closely enough to catch it by inspection — see below. Even on the diamond, counting the names each method holds in its two walks:

  statement	set, before round 1	set, after round 1	pointer
  D	7	2	1
  B3	7	3	1
  C	7	3	1
  B2	7	4	1
  B1	7	5	1
  A	7	3	1
  total	42	20	6

• Assuming every statement reaches the exit. Post-dominators are defined by paths to the exit, so a statement that can never reach it — one caught in an infinite loop, say — has no post-dominator at all, and must be left out of the answer rather than defaulted to something. A computation that silently assigns it one anyway will look fine until something tries to walk the resulting structure and finds a cycle or a dangling reference that was never really there. Code unreachable from the start is the mirror problem, for dominators: it has none, though it may still fall through to the exit and so have post-dominators. Below, the diamond with C → D replaced by a loop of C onto itself, so C (amber) never reaches E:

  flowchart TD
      A --> B1
      A --> C
      B1 --> B2
      B2 --> B3
      B3 --> D
      D --> E
      C --> C
      class C changed
      classDef changed fill:#f5b041,stroke:#f5b041,color:#000
  

  Run the slow walk on it unchanged. C's only successor is C, so its set is intersected with itself and never shrinks: it holds all seven names after round 1, and round 2 changes nothing; the read-off rule then names A, whose set {A, B1, B2, B3, D, E} is the largest, as the statement C must reach next, though A runs before C:

  statement	set after the walk	read off	right answer
  C	{A, B1, B2, B3, C, D, E}	A	none: left out

Where this is used

cobol-rekt computes forward dominators the whole-candidate-set way, following Allen and Cocke,^[1] and picks each statement's immediate dominator by eliminating the candidates that dominate another candidate. Those dominators are what its DJ graph, loop-body detection and reducibility test are built on. It computes no post-dominators. The elimination, applied to B3's row of the dominator table above:

The post-dominator half of this page comes from a separate Java tool that turns one method's control-flow graph into a nested tree of regions — decisions with two arms and a known end, loops with a known body, everything else a plain sequence — for narrating what the method does, in order. Every decision needs its immediate post-dominator; every loop needs its backward-reachable body. On this page's graphs those are the example table's D and the loop walk's {T, L1, L2}.

Most methods in a normal corpus are small enough that either approach — whole candidate sets or a chain of pointers — finishes before anyone would notice the difference. The table's right-hand column is the exception: one real method's control-flow graph had on the order of seven thousand statements and eighteen thousand edges — an unusually large single method, the kind a long hand-written dispatcher or a heavily generated chain of conditions produces, but not actually rare in enterprise code once a corpus is big enough. Built the whole-candidate-set way, settling that method's post-dominators alone was doing tens of millions of set comparisons per round, for however many rounds a graph that shape needed — long enough that it looked indistinguishable from a tool that had hung, rather than one that was simply still working. Rebuilt the pointer-chasing way described above, the same method's region tree finished in about a second. Nothing about the fast way is specific to a large method — it is the same six-step walk run on this page, just run on a graph with a thousand times more statements in it.

References

1. F. E. Allen and J. Cocke. "Graph-Theoretic Constructs for Program Control Flow Analysis." IBM Research Report RC 3923, 1972. The iterative dataflow algorithm for computing dominators.
2. K. D. Cooper, T. J. Harvey, and K. Kennedy. "A Simple, Fast Dominance Algorithm." Software Practice & Experience, 4, 2001. The pointer-per-statement method and its two-finger intersect.
3. A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986, p. 604 (Algorithm 10.1); new 2nd edition by A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, 2006, p. 665 (Algorithm 9.46). Constructing the natural loop of a back edge.