Dominance and reachability

Where a branch's two arms come back together, and exactly which statements are inside a loop — worked both the slow way and the fast way, on the same small graph, so the difference is visible rather than asserted.

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.

• 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, and exactly which statements belong to a loop, 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.
• 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. An irreducible region needs restructuring first — this page's techniques are what the pages after it build on, not a way around them.

The example

The same diamond as visiting a graph: a branch, two arms of different lengths, a statement both arms reach, then the end. Diagrams below mark the node a step is currently working out in amber.

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

Two questions about it, both answered on this page: once A branches, what is the statement both arms are guaranteed to reach? And separately — on a different graph, below — exactly which statements belong to a loop?

Dominators: looking backward

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 — the iterative dataflow formulation below is Allen and Cocke's.^[1] To reach B3: always through B2, always through B1, always through A — no other way in. Each of those dominates B3. 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.

Post-dominators: looking forward

Same question, mirrored: which statements is execution guaranteed to reach on the way out, no matter which way it leaves? That is a post-dominator, and it is the answer to the branch question — the statement both of A's arms are forced through is A's post-dominator.

The closest member of each set, excluding the statement itself, is its immediate post-dominator — the number this page spends the rest of its time computing, two different ways.

Notice B1's answer is B2, not D — D is where the branch's arms visibly rejoin, but B2 is closer, and "closest" is the question being asked. Keep that row in mind for what goes wrong.

The slow way: a full set per statement

Give every statement a candidate set, start each one as large as possible, and shrink it to {self} ∪ (intersection of every successor's set), over and over, until nothing shrinks any further. Visited in the same order both times for a fair comparison — D, B3, C, B2, B1, A, each after everything it points to.

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 is between D (set size 2) and E (size 1), so D wins, matching the table above. Six statements, two rounds, twelve visits, and a whole-collection comparison just to confirm round 2 changed nothing. That confirming round is pure overhead — on this graph, cheap; it is not what makes this approach slow in general.

The fast way: one pointer per statement

Carry one pointer per statement — its best guess at its immediate post-dominator — instead of a set. At each statement, the new guess is the meeting point of its already-visited successors' pointers: walk each successor's pointer-chain forward until two chains land on the same statement.

Same answers as the slow walk's final row, reached in one pass, no confirming round, and no statement ever held more than one other statement's name at a time.

The two compared

On six statements the difference is a handful of extra visits — 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.

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.^[2] 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 — the arrow DFS found going to a statement still on its own path. T is the 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.

Loop body: {T, L1, L2}. 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" (used above to decide which statements have a post-dominator at all) and, run forward instead of backward, "what is reachable from the start."

What goes wrong

• Mistaking "immediate" for "the nearest place things visibly merge." B1's immediate post-dominator is B2, not D, even though D is the more obviously interesting spot where the branch's arms rejoin. D does post-dominate B1 — it is simply not the closest one.
• 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.
• Assuming every statement is reachable. Dead code — a statement nothing can reach from the start — has no path to the exit either, so it 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.

Where this is used

A 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.

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. One real method's control-flow graph, though, 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. A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986, p. 604 (Algorithm 10.1), reprinted 2nd ed. 2006, p. 665 (Algorithm 9.46). Constructing the natural loop of a back edge.