Reducibility and loop detection

A loop with exactly one way in is easy to reason about. A loop with two is not — and three different ways to tell them apart, two of which agree on a tiny two-node counter-example used throughout.

Where this shows up in reverse engineering

Before trusting any tool's promise to turn an arbitrary control-flow graph into clean nested IF/WHILE blocks, it is worth knowing whether the method or paragraph in front of it is even reducible at all.

• Decades of hand-patched GOTOs in a legacy COBOL program are the realistic place a multi-entry loop actually shows up: a fix bolted on years after the original logic, jumping into the middle of an existing loop from somewhere else, is exactly how a second, overlapping entry gets created without anyone intending to write an irreducible region.
• Obfuscated or heavily optimized bytecode is the Java-side equivalent: a control-flow-flattening obfuscator, or a compiler's own loop transformations, can produce a region a straightforward decompiler either duplicates code around or refuses to render as structured source at all.
• Why "roughly where" is still useful even before the exact statement set is known: a tool that can at least say this region, somewhere in here, is not reducible has already turned "the decompiled output looks wrong and I don't know why" into a specific, checkable claim about one part of one method.

The problem

A loop with one entry — one statement execution always passes through to get into it — is a natural loop, the kind dominance and reachability already finds the body of. A loop with two or more separate entries, reachable without going through each other first, has no single header to call "the start of the loop" — nothing dominates the whole thing. A flowgraph built entirely out of natural loops, nested or side by side, is reducible. One with a multi-entry loop anywhere inside it is irreducible.

Reducibility matters because most of what a structuring tool wants to say — "this is a loop, here is its body, here is what comes after it" — assumes a single entry. An irreducible region cannot be described that way at all without first rewriting it, which is a much bigger job than detecting it.

Two examples

Two small graphs, reused across every method on this page. First, a loop with one entry — reducible by inspection, used to confirm each method says yes:

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

Second, the smallest graph that has two: a branch straight into both nodes of a two-node cycle, so neither node is reachable only through the other.

flowchart TD
    Entry --> A
    Entry --> B
    A --> B
    B --> A

Nothing dominates both A and B except Entry itself — there is no single header inside the cycle, because either one can be reached first.

Collapsing the graph: T1 and T2

One way to test reducibility, due to Hecht and Ullman:^[1] shrink the graph by two rules, repeated until nothing shrinks any further.

If the whole graph has shrunk to one statement, every loop in it had exactly one entry: reducible. If it gets stuck above one statement, some region had more than one way in: irreducible.

Running it on the good loop

Diagrams below mark the statement a step just folded into, or the self-loop it just removed, in amber.

Five statements down to one. Reducible.

Running it on the bad one

Stuck at three statements on the very first round. Irreducible — and this method says so without having to point at which two nodes are the problem, only that something, somewhere, is.

A quicker check for where: strongly connected components

A cheaper question, answerable without folding anything: find every maximal set of statements that can all reach each other — a strongly connected component — and look at how it is entered from outside. A loop with one entry has every outside edge landing on the same statement. A loop with two or more has outside edges landing on different statements inside the same component.

Two distinct entry points into one component: improper, by inspection, with no folding at all. Checked the same way on the good loop, the component is {T, L1, L2} and its only outside edge is the one edge T already has coming from wherever calls into the method — one entry, proper.

A third way: reusing dominance

A third method, from Sreedhar, Gao and Lee's paper on identifying loops with DJ graphs,^[2] answers the same question using the machinery dominance and reachability already built, rather than folding the graph or hunting components. Compute dominators for the two-entry cycle:

The dominator tree is just Entry → A and Entry → B — two children, nothing nested. Every edge in the original graph that is not a dominator-tree edge gets classified by one question: does the edge's target dominate its source?

A graph is reducible exactly when none of its back-edges — found by a fresh depth-first walk over this reclassified graph, not the original — turn out to be cross-join edges. Walking from Entry here, B → A is found going to a statement still on the current path: a back edge. It was classified cross-join above. One cross-join back edge is enough: irreducible, the same answer as the other two methods, from a different question — "does this edge ever reach into a region sideways, rather than climbing to something that was shown to dominate it" — asked once per edge instead of once per fold or once per component.

The dominator-tree edges plus this reclassified set, together, are called a DJ graph — the "D" for dominator, the "J" for the join edges just classified. This page only asks it yes-or-no questions; DJ graphs and natural loop bodies uses the same graph to find the exact statement set of every loop's body, nested ones included.

What goes wrong

• Running T2 without T1. Folding the good loop's last node produces a self-loop (T → T) before the graph is down to one statement — without T1 to clear it, the fold-count stays positive forever and the loop never terminates on an otherwise perfectly reducible graph.
• Trusting one strongly connected component with one visible entry. It is necessary, not sufficient: a strongly connected component can contain a smaller, improper one nested inside it, invisible until that inner piece is checked on its own. A clean look at the outer boundary is not a clean bill of health for everything inside it.
• Reading "no self-loops, no single-predecessor nodes left" as success. It is the opposite — T1 and T2 both finding nothing to do, on a graph still above one statement, is exactly what a stuck, irreducible region looks like. The two-entry cycle above never fires either rule, from the very first round.

Where this is used

Before translating a flowgraph with arbitrary jumps into structured code, it has to be known which parts, if any, do not reduce — those are the parts a straight translation into IF/WHILE cannot express without first restructuring them. The three methods above answer "is it reducible at all" and "roughly where" cheaply. Turning that into the exact statement set of every loop body, including loops nested inside other loops, is the DJ graph's other job — see DJ graphs and natural loop bodies.

References

1. M. S. Hecht and J. D. Ullman. "Flow Graph Reducibility." SIAM Journal on Computing, 1(2), 1972, pp. 188–202. The T1/T2 collapsing rules.
2. V. C. Sreedhar, G. R. Gao, and Y.-F. Lee. "Identifying Loops Using DJ Graphs." ACM Transactions on Programming Languages and Systems, 18(6), November 1996, pp. 649–658. The dominator/back-join/cross-join reducibility test; see also DJ graphs and natural loop bodies.