Reducibility and loop detection

Read first: Dominance and reachability, Visiting a graph, Strongly connected components

A WHILE loop has one head: control enters at the top and nowhere else. To print a tangle of GO TOs as one, a structuring tool must find, for each cycle, the one statement every path into it passes through. When a cycle can be entered at two statements there is none, and no nesting of IF and WHILE describes it without first rewriting the code.

On this page's three-node counter-example, where Entry branches straight into both A and B of a two-node cycle, three methods all say irreducible: collapsing gets stuck at three statements, the cycle {A, B} is entered at two places, and the dominator test finds a sideways edge closing a cycle. On a five-node one-entry loop, all three say reducible.

Terms are pinned down in Why one way in matters.

The example: one way in, or two

The counter-example, the smallest graph with a loop that has two ways in: 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

Below it, a loop with one entry, reducible by inspection, used to confirm each method says yes. T is the method's entry; the dashed edge goes back to it.

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

The answer, for both graphs, from each of the three methods on this page. Every cell is worked out in the section named in its row:

One way COBOL ends up with the counter-example's shape, in a fragment constructed for this page. Take the paragraphs as the nodes: ENTRY-PARA is Entry, A-PARA is A, B-PARA is B.

ENTRY-PARA.
    IF WS-RESTART = 'Y'
        GO TO B-PARA.
A-PARA.
    ADD 1 TO WS-COUNT.
B-PARA.
    IF WS-COUNT < 10
        GO TO A-PARA.

Falling through gives Entry → A and A → B; GO TO A-PARA gives B → A. The loop A-PARA…B-PARA would have one way in, at A, but GO TO B-PARA jumps into its middle: that is Entry → B. Leave out B-PARA's fall-through out of the loop and these are exactly the four edges of the graph above.

Collapsing the one-entry loop

The first method, due to Hecht and Ullman,^[1] shrinks the graph with two rules, repeated until nothing shrinks any further: T1 deletes an edge from a statement to itself; T2 folds a statement with exactly one predecessor into that predecessor. In the walk, diagrams mark the statement a step just folded into, or the self-loop it just removed, in amber.

Five statements down to one, in the last diagram of the walk. Reducible.

Collapsing the two-entry cycle

Stuck at three statements on the very first round: the red-outlined A and B in step 2 each have two predecessors. Irreducible — and this method says so without having to point at which two nodes are the problem, only that something, somewhere, is.

The collapsing rules: T1 and T2

The two rules the walks above applied, in full:

In the one-entry walk, T2 is steps 1 to 4, each folding one statement, and T1 is step 5, removing the self-loop step 4 made on T. In the two-entry walk, step 1 is T1 and step 2 is T2, and neither changes anything. If the whole graph has shrunk to one statement, as in the first walk, every loop in it had exactly one entry: reducible. If it gets stuck above one statement, as in the second, some region had more than one way in: irreducible.

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 (its own page shows how to find them) — 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. On the two-entry cycle:

Two distinct entry points into one component, the two amber edges in step 1: irreducible, by inspection, with no folding at all. Checked the same way on the good loop, below, the component is {T, L1, L2} (amber) and no edge enters it from outside at all — T is the method's entry, and X1 and X2 are only reached from it — so its one way in is T: reducible.

flowchart TD
    T --> X1
    T --> L1
    X1 --> X2
    L1 --> L2
    L2 -.->|back edge| T
    class T,L1,L2 changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

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?

Both rows of that table apply the second line of this rule:

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. Here it is for the two-entry cycle: solid edges are the dominator tree, dashed ones the two cross-joins from the table.

flowchart TD
    Entry --> A
    Entry --> B
    A -.->|cross-join| B
    B -.->|cross-join| A

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 and visiting A first (Entry → A → B, the amber path below), B → A is found going to a statement still on the current path: a back edge, drawn in red.

flowchart TD
    Entry --> A
    Entry --> B
    A -.->|cross-join| B
    B -.->|"cross-join, DFS back edge"| A
    linkStyle 0 stroke:#f5b041,stroke-width:3px
    linkStyle 2 stroke:#f5b041,stroke-width:3px
    linkStyle 3 stroke:#f87171,stroke-width:3px

(Visit B first and A → B is the one found — the same verdict either way.) It was classified cross-join in the table 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 same test on the good loop. Its dominator tree is T → X1 → X2 and T → L1 → L2, which is every edge but one; that one extra edge is a back-join:

That last row is where the two senses of back edge meet. In the DFS sense, a back edge is one a depth-first walk finds going to a statement still on its current path; in the dominator sense, it is one whose target dominates its source — a back-join edge. L2 → T is both. On a reducible graph the two pick out exactly the same edges; on the two-entry cycle, B → A is a DFS back edge but not a back-join.

A cross-join edge that is not a DFS back edge closes no cycle and says nothing about reducibility. Either arm of an if/else landing on the statement where they merge is one. Below, M's dominators are {C, M}, so neither edge into M is a dominator-tree edge; and M dominates neither Then (dominated by {C, Then}) nor Else ({C, Else}), so both are cross-joins. A depth-first walk C → Then → M finishes M before it visits Else, so Else → M goes to a finished statement, not one on the path: no back edges at all.

flowchart TD
    C --> Then
    C --> Else
    Then -.->|cross-join| M
    Else -.->|cross-join| M

This page only asks the DJ graph 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.

Why one way in matters

A loop with one entry — one statement execution always passes through to get into it — is a natural loop: its header dominates every node in its body, meaning every path into the loop must pass through that one entry point. The two dominator tables above show the difference. Intersect the dominator sets of each loop's statements:

This is the kind of loop dominance and reachability already finds the body of. In the second row, nothing inside the cycle dominates both A and B; only Entry, outside it, does. 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, the T in the first row. The second row has none to name, so that cycle cannot be described this way without first rewriting it, a much bigger job than detecting it.

What goes wrong

• Running T2 without T1. A self-loop counts as a predecessor. A statement with one edge in from elsewhere and one edge to itself has two predecessors — the other statement and itself — so T2 never fires on it, and without T1 to remove the self-edge first, the graph gets stuck above one statement: a perfectly reducible graph reported as irreducible. Here Retry is that statement:

  flowchart TD
      Entry --> Retry
      Retry -.->|self-loop| Retry
      class Retry stuck
      classDef stuck stroke:#f87171,stroke-width:3px,fill:transparent
  

  	predecessors of Retry	result
  T2 only	{Entry, Retry}	stuck at 2 statements: "irreducible"
  T1 then T2	{Entry}, once T1 removes the self-loop	folds into Entry: 1 statement, reducible

  The good loop would not catch the omission — its self-loop only appears on T, the root, in step 4 of its walk, once everything else has folded away and only one statement is left.
• Trusting one strongly connected component with one visible entry. It is necessary, not sufficient: a strongly connected component can contain a smaller, irreducible one nested inside it, invisible until that inner piece is checked on its own: remove the outer component's header and recompute strongly connected components among the statements left inside it, then check each of those the same way. Below, the outer component {H, A, B} is entered only at H. Remove H and {A, B} is still a component, entered from H at both A and B (amber):

  flowchart TD
      Start --> H
      H --> A
      H --> B
      A --> B
      B --> A
      B --> H
      class A,B stuck
      classDef stuck stroke:#f87171,stroke-width:3px,fill:transparent
      linkStyle 1 stroke:#f5b041,stroke-width:3px
      linkStyle 2 stroke:#f5b041,stroke-width:3px
  

  outer {H, A, B}: entered at H onlyinner {A, B}: entered at A and at B
  A clean look at the outer boundary is not a clean bill of health for everything inside it. (T1/T2 agree: H, A and B each have two predecessors, and nothing folds.)
• 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 never fires either rule, from the very first round; this is its state after step 2 of its walk:

  statement	self-loop?	predecessors
  Entry	no	{} (root)
  A	no	{Entry, B}
  B	no	{Entry, A}

  Nothing for either rule, and three statements left: irreducible, not done.

Where this shows up in reverse engineering

• Decades of hand-patched GO TOs in a legacy COBOL program are the realistic place a multi-entry loop actually shows up. Read the example's GO TO B-PARA as that patch: a fix bolted on years after the original A-PARA…B-PARA loop, jumping into its middle, is exactly how a second, overlapping entry gets created without anyone intending to write an irreducible region. Without the amber edge, the patch, the loop has one way in, at A:

  flowchart TD
      Entry --> A
      A --> B
      B --> A
      Entry -->|"GO TO B-PARA"| B
      linkStyle 3 stroke:#f5b041,stroke-width:3px
  

• 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: the strongly-connected-component check's chips, Entry → A and Entry → B, already say this region is not reducible, which turns "the decompiled output looks wrong and I don't know why" into a specific, checkable claim about one part of one method.

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, as the example's answer table shows. 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.