DJ graphs and natural loop bodies

Read first: Reducibility and loop detection, Dominance and reachability, Strongly connected components

A back edge names a loop's header, but not where its body stops. Walk backward from it to the header and you collect every statement on the way, including all of any loop nested inside; a strongly-connected-components check puts both loops in one component too.

The example below has a loop at B inside a loop at A. The DJ graph labels each statement with its depth in the dominator tree and handles the deepest header first: B's body {B, B1, B2} is found and collapsed into B, so when A's turn comes its body is {A, B, C, D}, with B standing in for the whole inner loop.

Dominator, back edge and loop header are defined on the two pages above.

The example: a loop inside a loop

An inner loop (B, B1, B2) inside an outer one (A through D). Each statement is immediately dominated by the one above it, so the dominator-tree depths in the labels run d0 to d7.

flowchart TD
    Entry["Entry · d0"] --> A["A · d1"]
    A --> B["B · d2"]
    B --> B1["B1 · d3"]
    B1 --> B2["B2 · d4"]
    B2 -.->|back edge| B
    B2 --> C["C · d5"]
    C --> D["D · d6"]
    D -.->|back edge| A
    D --> Exit["Exit · d7"]

The answer for this graph, which the walk below derives — one body per header, with B in the outer body standing for the whole inner loop:

Every edge in the graph, sorted into the kinds the walk uses. The solid ones are all dominator-tree edges; the two dashed ones close loops, because their target dominates their source:

The pass, in outline, as the walk runs it on the graph above. The second half never fires here; the irreducible section runs it.

for depth = deepest .. 0:
  for each back-join edge s → h,
      h at this depth:
    body = walk back from s,
           stopping at h
    collapse body into h
  if a cross-join edge that is also
     a DFS back edge lands here:
    collapse each strongly connected
      component (2+ members) among
      statements this deep or deeper

Step by step: collapsing the nested loop

The walk visits depths from 7 up to 0, and at each asks one question: does a back-join edge land on a statement at this depth? Steps 1 and 3 are the two yeses: each finds a header, walks backward from the back edge's source to it, and collapses the body into it in the next step. At every other depth the answer is no and the walk moves up.

The backward walks in steps 1 and 3 always stop, and stop at the right place: the header dominates every statement in the body, so every backward path from the body reaches it. It is the same bounded walk as dominance and reachability's loop section. Collapsing then rewires the graph: an edge leaving the body is redirected to start at the header, and an edge entering a body statement other than the header is redirected to end at it. A natural loop has no edges of the second kind, since its header is the only way in; the irreducible walk below does (Entry → B becomes Entry → A). The two collapses above moved these edges:

Why redirecting edges is safe. The header is the only way into the loop, so from the rest of the program the loop's output is indistinguishable from its header's: C in step 2's graph is reached from B, and that is all a shallower level needs. Each redirected edge keeps its original classification (back-join, cross-join, or dominator), as the last column shows, so levels above can still use it.

Why collapsing works. In step 3's graph B is one ordinary statement, so the walk from D back to A passes through it once and never sees B1 or B2. The inner boundary was locked in at step 1, so no statement is walked again by every loop that encloses it.

Step 3's backward walk visits

So the inner loop was collapsed in step 2, before the outer loop's back edge was even inspected in step 3. The kept types matter for exactly this reason: a back-join or cross-join edge that skips past this loop's own header, straight to an outer ancestor, carries that fact up to whichever shallower level needs it next — the same one-level-at-a-time climb eliminating GOTOs uses for a jump nested several scopes deep.

Why inside-out

Run the outer loop first instead, on the original graph, before anything is collapsed. The backward walk from D, stopping at A, goes D, C, B2, B1, B, then A: it picks up the inner loop's statements on the way.

flowchart TD
    Entry["Entry · d0"] --> A["A · d1"]
    A --> B["B · d2"]
    B --> B1["B1 · d3"]
    B1 --> B2["B2 · d4"]
    B2 -.->|back edge| B
    B2 --> C["C · d5"]
    C --> D["D · d6"]
    D -.->|back edge| A
    D --> Exit["Exit · d7"]
    class A,B,B1,B2,C member
    class D changed
    classDef member stroke:#4ade80,stroke-width:3px,fill:transparent
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000
    linkStyle 7 stroke:#f5b041,stroke-width:3px

Outer loop first

That set has no way to say that B1 and B2 repeat on their own, inside each pass of A's loop: they look like the outer loop's statements, which is exactly the mix-up in the TL;DR. Untangling it would mean re-analysing the inner loop's boundary while looking at the outer one. Inside-out avoids that: by step 3 of the walk, B already stands for the inner loop, so the same walk from D gives {A, B, C, D}.

What reducibility alone gives you

Reducibility and loop detection settles whether a flowgraph is well-behaved at all, and its strongly-connected-components method points at roughly where the trouble is. On the example, neither hands back the two bodies:

The structure that gets the last row, the DJ graph, was introduced by Sreedhar and Gao for a different problem — placing φ-nodes in static single assignment form.^[1] Sreedhar, Gao and Lee then reused it for this one: identifying every loop's exact body, nested ones included, in one bottom-up pass.^[2] The dominator-tree reducibility test on the reducibility page is a piece of that second paper too. The rest of it is what the walk above did: process a method's dominator tree from its deepest level up, and at every level, either collapse a loop that was just found into a single stand-in statement, or discover that no single statement can be called that level's loop header at all.

The three edge kinds

A DJ graph splits a method's control-flow edges into three kinds. The example's edge table used the first two:

Cross-join edges are mostly harmless — every if/else merge makes them. In dominance and reachability's diamond, below, D dominates neither B3 nor C, so both edges into it are cross-join, and that graph is perfectly reducible:

flowchart TD
    A --> B1
    A --> C
    B1 --> B2
    B2 --> B3
    B3 -.->|cross-join| D
    C -.->|cross-join| D
    D --> E

A cross-join edge signals an irreducible region only when it is also a DFS back edge — when it closes a cycle without its target dominating its source. The diamond has no cycle, so neither of its cross-join edges is one. "Back edge" therefore has two senses here. In the DFS sense, it is an edge a depth-first walk finds going to a statement still on its current path. In the dominator sense, it is an edge whose target dominates its source — a back-join edge. The table puts edges from this page's graphs through both tests (the last row is the two-entry cycle from the irreducible section, visited A first):

On a reducible graph the two senses pick out exactly the same edges, as in the first two rows; a DFS back edge that is cross-join instead, as in the last row, is precisely where they disagree, and precisely an irreducible region. The rule is reducibility and loop detection's third method; what is new is keeping each statement's depth, so a bottom-up pass knows which level to process next.

Why depth matters. A loop can only be nested inside loops whose headers are ancestors of its own header in the dominator tree, so an enclosing loop's header is always shallower than the loops it contains: in the example, A at d1 is an ancestor of B at d2. (Two headers on different branches of the tree are unrelated, whatever their depths.) Processing from deepest to shallowest therefore resolves the innermost loops first, as the walk resolved B before A.

When a level is irreducible instead

The two-entry cycle from the reducibility page, the smallest irreducible shape there is:

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

The first walk relied on a back-join edge to name each header. This cycle closes through a cross-join edge instead — B → A, which is also a DFS back edge when the DFS visits A first, landing on A at depth 1 — the hallmark of an irreducible region: a cycle with more than one entry point (Entry → A and Entry → B above), so no single statement dominates the rest, and there is no header for a backward walk to stop at. A level can hold both kinds: its natural loops are collapsed first, then whatever irreducible region remains is handled as below.

A DFS over this DJ graph from Entry, visiting A before B, finds exactly one back edge: B → A, already classified cross-join. A → B is cross-join too, but the DFS took it as an ordinary forward step, so on its own it would mean nothing; B → A being both cross-join and a DFS back edge is the signal to try the quicker check.

Step 1 is the fallback: take every statement at this dominator depth or deeper that is still in the graph, and run a strongly connected components analysis over them. Any component with more than one member is an irreducible region. Step 2 collapses it the same way a natural loop is collapsed — merged into a single stand-in statement — so that levels above can continue without knowing there was anything unusual.

Compare step 2 here with step 2 of the first walk: a reducible loop's body and an irreducible region's component both disappear into one statement before the level above ever sees them. What differs is how the body was found: a bounded backward walk from one edge for a reducible loop, a full strongly-connected-components pass for an irreducible region, because an irreducible region has no single back edge whose header could have been walked back from in the first place.

What goes wrong

Two limitations to be aware of, both consequences of the design rather than bugs, each shown on one of this page's two walks:

• An irreducible region's recorded "header" is an artifact of visitation order, not a property of the region. A natural loop has a true header — the one statement that dominates every node in its body. An irreducible region, by definition, has no such statement. The tool described here still picks one statement to serve as the stand-in after collapsing — its own convention, not the paper's — and uses whichever statement the DFS happened to identify as the target of its back edge: A in step 2 of the irreducible walk. Run the DFS over the same two-entry cycle visiting B before A instead, and the back edge found is A → B, not B → A — the identical region collapses to a different stand-in statement:

  Entry's children visited	DFS back edge found	recorded header
  A, then B	B → A	A
  B, then A	A → B	B

  That is not a bug so much as an honest consequence of the question itself: an irreducible region has no single header, so any one statement named as "the" header for it is already a necessary approximation — just not a stable one across runs.
• A collapsed body is reported in terms of whatever was already collapsed underneath it, not fully expanded back out. By the time an outer loop is processed, its inner loops are already single stand-in statements, and the outer loop's reported body lists those stand-ins. That is what keeps an outer loop from re-walking its inner loops' statements, but if you need the full list of original statements you must expand each stand-in from what it absorbed. Step 3 of the first walk records {A, B, C, D}, where B means the stand-in, not the three statements it absorbed:

  header	reported body	original statements, fully expanded
  B	{B, B1, B2}	{B, B1, B2} — not nested, nothing to expand
  A	{A, B, C, D}	{A, B, B1, B2, C, D} once B's own body is substituted back in

  Reading a reported body as the complete statement list, for a loop with another one nested inside it, misses the inner loop's statements other than its header: here B1 and B2, four statements listed where there are six.

The whole pass

The full algorithm, as one box:

Each line of the box has already run on this page:

On top of building the dominator tree and walking every edge to classify it, the pass visits each level once, does one backward walk per loop found, and one strongly connected component search per irreducible level. For this page's two walks:

For reducible graphs, Sreedhar, Gao and Lee bound the whole thing at near-linear time by doing the collapsing with a union-find structure.^[2] Irreducible levels cost more: each search covers every statement at that depth or deeper, so the same statements can be searched again at several levels. On a typical COBOL program — where irreducible regions are rare and loops rarely nest more than two or three deep — this finishes almost instantly.

Where this shows up in reverse engineering

Knowing a method is reducible is not the same as knowing which statements belong to which loop — the first table under what reducibility alone gives you — and once there is more than one loop, that distinction is exactly what the next tool in the pipeline needs. On the example:

• Automatic narration of an unfamiliar program needs the exact loop body before it can say more than "there is a loop somewhere in here". Handed the first row (the set from why inside-out), it would describe B1 and B2 as the outer loop's statements.
• A decompiler nesting loops correctly in its emitted source has the identical requirement: get the body boundary wrong by one statement and the generated code either runs an extra statement inside the wrong loop or runs one outside a loop it should be inside.
• Why bottom-up, specifically: as in the first walk, resolving the innermost loop first and collapsing it keeps the outer loop's own analysis from ever needing the inner loop's statements — the only way this scales to a method with several loops at several nesting depths without re-deriving the same boundary at every level.

Where the edge kinds are used next

The three edge kinds — dominator, back-join, cross-join — are not thrown away once reducibility and loop bodies are known. A transpiler, the first use below, maps them like this on this page's graphs:

• A transpiler emitting structured code switches on exactly these three edge classes when deciding how to represent each edge: a back-join edge becomes a loop, a forward dominator edge becomes straight-line code or an IF, and a cross-join edge that is also a DFS back edge (if any) marks the irreducible region that needs the more expensive restructuring from eliminating GOTOs. The classification done here survives into code generation, not just into an analysis report.
• A narration or documentation tool uses the loop bodies to scope its descriptions: "this loop iterates over records" is only meaningful if the tool knows exactly which statements are inside the loop and which are after it. Without the DJ graph's output, the best it can do is "there is a loop somewhere near these statements."

References

1. V. C. Sreedhar and G. R. Gao. "A Linear Time Algorithm for Placing φ-Nodes." Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '95), 1995, pp. 62–73. Introduces the DJ graph.
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 bottom-up collapsing algorithm this page walks through.