DJ graphs and natural loop bodies

Reducibility answers yes or no, and roughly where. It does not say which statements belong to which loop when there is more than one, nested or side by side. One structure — the DJ graph — answers that, by processing a method's loops from the inside out, one dominator level at a time.

Where this shows up in reverse engineering

Knowing a method is reducible is not the same as knowing which statements belong to which loop — and once there is more than one loop, nested or side by side, that distinction is exactly what the next tool in the pipeline needs.

• Automatic narration of an unfamiliar program needs the exact loop body before it can say anything more specific than "there is a loop somewhere in here": telling an outer loop's statements apart from an inner one's is what lets a narration describe each one correctly instead of describing the inner loop's statements as if they belonged to the outer one, or vice versa.
• 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: resolving the innermost loop first and collapsing it before asking about the loop around it is what keeps the outer loop's own analysis from ever needing to know the inner loop's statements existed — the only way this scales to a method with several loops at several nesting depths without re-deriving the same boundary information at every level.

The problem

Reducibility and loop detection settles whether a flowgraph is well-behaved at all, and the strongly-connected-components method there points at roughly where the trouble is. Neither one hands back the thing a structuring tool actually needs: for this specific loop, the exact set of statements inside it — and when one loop sits inside another, the inner one's statements need to be told apart from the outer one's before either body means anything.

The structure below, 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, covered here: 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 DJ graph

A DJ graph is two kinds of edge sharing one graph: every dominator-tree edge (a "D-edge," unchanged from the dominator tree itself), plus every edge from the original flowgraph that is not a dominator-tree edge, reclassified exactly as reducibility and loop detection's third method already does: a back-join edge if its target dominates its source, a cross-join edge otherwise. Nothing new in the classification rule — what is new is doing it once, over the whole method, and keeping each statement's dominator-tree depth alongside it, so a bottom-up pass has an order to follow.

A small nested example — an inner loop (B, B1, B2) sitting inside an outer one (A through D):

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"]

Every solid edge above is already a dominator-tree edge — this particular shape happens to be a straight chain of immediate dominators, same as the single-loop graph on the reducibility page, just longer. Classifying the two dashed edges the usual way: does B dominate B2? Yes — back-join. Does A dominate D? Yes — back-join. Both land inside the loop they belong to, not sideways into one; this graph has no cross-join edges at all, which is exactly what "fully reducible, nested two deep" looks like on a DJ graph.

Collapsing the nested loop, bottom-up

Walk the dominator tree's levels from deepest to shallowest. At each level, look for a back-join edge landing on a statement at that level; if one exists, that statement is a loop header, and its body is found exactly the way dominance and reachability's loop section already finds a single loop's body: walk backward from the back edge's source, stopping at the header. Collapse the whole body into the header — one statement standing in for all of them — and continue up a level, with that collapse already done.

Two natural loops, correctly told apart, in one bottom-up pass — the inner one collapsed before the outer one's own back edge was even inspected, so the outer loop's walk never had to know B1 or B2 existed. The redirected edges keep their original type for exactly this reason: a back-join or cross-join edge that happens to skip 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.

When a level is irreducible instead

Not every level finds a back-join edge. Back on 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

A DFS over this DJ graph from Entry, visiting A before B, finds exactly one back edge: B → A, already classified cross-join. No back-join edge landed on this level at all — the signal to try the quicker check instead.

Same collapse step either way — a reducible loop's body or 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

• An irreducible region's recorded "header" is an artifact of visitation order, not a property of the region. 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 depending on which child of Entry happened to be visited first:

  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, by definition, has no single header, so any one statement the algorithm names 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. The outer loop above is recorded as {A, B, C, D} — B there means the single stand-in statement, not the three original 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 that turns out to have another one nested inside it, undercounts by exactly the inner loop's size.

Where this is used

The three edge types this page builds — dominator, back-join, cross-join — are not thrown away once reducibility and loop bodies are known. The transpiler's own tree-cloning step still switches on exactly these three classes when copying an edge into its output graph, alongside the same plain and annotated edge types eliminating GOTOs rewrites: the classification done here survives into code generation, not just into an analysis report.

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.