Irreducible Loops

Irreducible loops | MaskRay

H whose head H dominates its tail T defines a loop with the single entry H. This works only for reducible control flow graphs. Opti">

2026-07-12

The dominator tree lets us identify natural loops: a back edge T->H whose head H dominates its tail T defines a loop with the single entry H. This works only for reducible control flow graphs. Optimized machine code and decompiler output routinely contain irreducible loops, which have more than one entry and thus no dominating header, so the dominator-based method cannot see them.

This post builds a loop-nesting forest for an arbitrary CFG with the single-pass depth-first search of 韦韬、毛剑、邹维、陈宇(Tao Wei, Jian Mao, Wei Zou & Yu Chen) A New Algorithm for Identifying Loops in Decompilation, SAS 2007 (The 14th International Static Analysis Symposium).

Reducibility

A depth-first search from the entry classifies every non-tree edge relative to the spanning tree. A retreating edge u->v goes to an ancestor v of u on the DFS path. A cycle is a closed path in the CFG, a graph-theoretic object with no distinguished entry; a loop is the control-flow structure built on top — a set of nodes with a header, nested into a forest. (LLVM draws the same line: LoopInfo represents natural loops, while the GenericCycleInfo used below generalizes them to irreducible control flow.) A CFG is reducible when, in every DFS, each retreating edge is a back edge — its head v dominates its tail u. Then every cycle lies in a natural loop whose header dominates it, so control enters the loop only through that header.

A CFG is irreducible when some cycle has two or more entries: nodes with a predecessor outside the cycle. No single node dominates the cycle, so there is no natural header. The smallest example is the irreducible core:

The irreducible core: 0 enters the 1↔︎2 cycle at both nodes. Double circle = header (1, visited first); dashed = the re-entry edge.

Node 0 branches to both 1 and 2, and 1 -> 2 -> 1 is a cycle entered at 1 (through 0->1) and at 2 (through 0->2). M.S. Hecht and J.D. Ullman proved that a CFG is irreducible if and only if it contains this three-node pattern as a subgraph, allowing each edge to be a path through other nodes.

Because no node dominates an irreducible cycle, its header is not intrinsic — we must pick one of the entries. The standard choice (Havlak, LLVM, and the algorithm below) is the node the DFS reaches first, i.e. the loop member with the smallest preorder number. So the loop-nesting forest of an irreducible CFG depends on the DFS order.

Loop-nesting forest

There is no agreed definition of the loop-nesting forest for irreducible CFGs. Steensgaard, Sreedhar–Gao–Lee, Havlak, and Ramalingam each give a different one; for the CFG in Wei et al.'s Fig. 3 they report two, one, three, and one loops respectively. We adopt Havlak's, the finest, because it gives each loop a single header and the fewest gotos when re-structuring, and it is what LLVM's GenericCycleInfo computes:

The outermost loops are the maximal strongly connected regions (with at least one internal edge).

A loop's header is its minimum-preorder node.

Its inner loops are the loops of the subgraph induced on (loop nodes − header), found recursively.

The forest has a compact encoding. For each node record its innermost loop header iloop_header: the header of the smallest loop containing it, or none. A header's own iloop_header is the header of its parent loop. Following the iloop_header links from a node lists its enclosing loops innermost-first — the "loop header list" of the paper. Which nodes are headers, plus every node's innermost header, determines the whole forest; that is what the program below prints.

Representing and querying the forest

Building the forest is half the job; every consumer then asks two questions repeatedly: is a node inside loop L, and is loop L2 nested in L1? How the forest is stored decides whether these are O(1).

The obvious layout gives each loop the set of all its nodes — its own plus every descendant's. A membership test is one hash probe, but a node nested d loops deep is stored d times, so memory and build cost are O(N * depth). This is what GenericLoopInfo and GenericCycleInfo did: a set per cycle.

An Euler tour of the forest removes the duplication. Lay every node into one shared array so each loop owns a contiguous slice [begin, end) nested inside its parent's. Each node then appears once, memory is O(N), and both queries become interval tests:

is a node inside L: map the node to its innermost loop, then test that loop's index against L's slice;

is L2 nested in L1: L1.begin .

No per-loop set survives — the same trick DominatorTree uses for O(1) dominance (DFSNumIn/DFSNumOut), and the direction GenericCycleInfo took.

The contiguous slices suit a build-once analysis...

Irreducible Loops

Related Articles

(no title)

Scientists reverse brain aging, with a nasal spray

AI has torched the market for junior programmers

Al Vigier: Canada's AI strategy shouldn't include secret Palantir bills

The Anatomy of an AI-Native Org