Lesson 15.5 — Loop nesting forests¶

Techniques: DFS edge classification, natural loops (LLVM's LoopInfo), Tarjan's loop nesting, Havlak's forest for irreducible loops (with Ramalingam's correction), Steensgaard's forest · Pebble implements: DFS (E1), natural loops (E13), Havlak (E14) · Lab: natural loops vs LoopInfo, Havlak vs CycleInfo · Prerequisites: Lesson 15.1 (dominators), Ch 8 (DFS orders) · Time: 5–6 hours

Loop optimizations (Ch 18) need to know which blocks form a loop, where it is entered, which loop is inside which, and how deep each block is nested (register allocation spills in the shallowest blocks). In the running example the answer is easy: B heads an outer loop B…H and E an inner loop E, F, G. Now add one edge, D → F (the function @running_irreducible in tests/ch15/Inputs/running-example.ll). The cycle E → F → G → E can be entered at E and at F. It is still obviously a loop to a human, but neither E nor F dominates the other, so the classical definition refuses to call it one. The five techniques of this lesson differ exactly in what they do with such cycles.

flowchart TD
  A([A]) --> B[B]
  B --> C[C]
  B --> E[E]
  C --> D[D]
  C --> H[H]
  D --> E
  D -.->|irreducible variant only| F
  E --> F[F]
  E --> H
  F --> G[G]
  G --> H
  G --> E
  H --> I[I]
  H --> B

1. Problem and motivation¶

The problem. Given a CFG, produce a loop nesting forest: a set of loops, each with a header (or several), a body, a parent loop and a depth, such that loops are disjoint or nested; and classify every edge relative to a depth-first search. LLVM exposes two such forests: LoopInfo (natural loops only, what every loop pass uses) and CycleInfo (every cycle, reducible or not, used by uniformity analysis and fix-irreducible) [LLVM-LoopInfo, LLVM-Cycle]. Pebble's Ch 18 loop passes consume your E13 forest.

DFS edge classification¶

Depth-first search, as analyzed by Tarjan [Tar72], labels each edge as tree, back (retreating), forward or cross. Every cycle contains a retreating edge (Lemma 15.5.3), so DFS finds candidate loops in linear time; everything else in this lesson builds on it.

Natural loops¶

The first optimizers defined a loop by a back edge \(t \to h\) whose head dominates its tail: the natural loop of the edge is \(h\) plus everything that reaches \(t\) without passing through \(h\) [LM69, All70]. Natural loops are single-entry by construction (\(h\) dominates the whole body, Theorem 15.5.5), which is exactly the property code motion needs. They are what LLVM's LoopInfo reports; irreducible cycles are simply not loops to it.

Tarjan's loop nesting¶

Tarjan showed that on a reducible CFG the loop nesting forest can be built directly from a DFS in almost linear time with a union-find structure, collapsing inner loops into their headers, and that the same algorithm detects irreducibility the moment it meets a second entry [Tar74]. It avoids computing dominators at all.

Havlak's forest¶

Havlak extended Tarjan's algorithm to irreducible CFGs: when a cycle has several entries, the DFS-first entry becomes its header, the cycle is marked irreducible, and the extra entry edges are "carried" up to enclosing loops [Hav97]. Ramalingam showed that Havlak's original bookkeeping can be quadratic and gave a fix that restores the almost-linear bound [Ram99], and later compared all known loop forests [Ram02]. LLVM's CycleInfo computes Havlak's forest [LLVM-CycleTerm].

Steensgaard's forest¶

Steensgaard defined loops as strongly connected components and made every entry of an SCC a header, then recursed inside the component with the back edges to the headers removed [Ste93]. The result does not depend on the DFS, at the price of multiple headers per loop.

2. Definitions and algorithms¶

\(G = (N, E, r)\); a DFS from \(r\) visiting successors in listed order gives \(\mathrm{pre}(\cdot)\), \(\mathrm{post}(\cdot)\) and the DFS tree \(T\) with the ancestor relation \(\preceq_T\) (Definition 15.1.9). A cycle is a closed path; a strongly connected component (SCC) is a maximal set of nodes that all reach each other; it is non-trivial if it has an internal edge.

Definition 15.5.1 (DFS edge kinds)

For a DFS of \(G\), an edge \(u \to v\) between reachable nodes is a tree edge if \(v\) was discovered through it; a retreating (DFS "back") edge if \(v \preceq_T u\) (\(u = v\) included); a forward edge if \(u \prec_T v\) but it is not a tree edge; a cross edge otherwise (then \(\mathrm{pre}(v) < \mathrm{pre}(u)\) and \(v\) finished before \(u\) was discovered).

DFS edge classification¶

Algorithm 15.5.2 (DFS with edge classification)

Input: \(G\).
Output: pre, post, RPO, parent, last (the largest preorder number in each subtree), and the kind of every edge.
Precondition: successors are tried in listed order (this fixes the DFS).
Postcondition: every edge of the reachable graph carries its kind of Definition 15.5.1, and \(a \preceq_T b \iff \mathrm{pre}(a) \le \mathrm{pre}(b) \le \mathrm{last}(a)\).
Invariant: the nodes on the stack are exactly the ancestors of the node being explored, in order (Theorem 15.5.11).

function ClassifyDFS(G = (N, E, r)):
    counterPre ← 0; counterPost ← 0
    onStack ← {}
    Visit(r)
    return pre, post, parent, last, kind

function Visit(u):
    pre[u] ← counterPre; counterPre ← counterPre + 1
    onStack ← onStack ∪ {u}
    for v in succs(u):                    # listed order
        if v has no pre number:
            kind[u → v] ← tree
            parent[v] ← u
            Visit(v)
        else if v ∈ onStack:
            kind[u → v] ← retreating      # v →* u
        else if pre[v] > pre[u]:
            kind[u → v] ← forward         # v is a finished descendant
        else:
            kind[u → v] ← cross
    onStack ← onStack ∖ {u}
    last[u] ← counterPre − 1              # every node numbered since u entered is below u
    post[u] ← counterPost; counterPost ← counterPost + 1

The course's contract (computeDFS, E1) asks for the same result with an explicit stack instead of recursion: the tests run it on a 200 000-node chain.

Lemma 15.5.3 (Every cycle has a retreating edge)

For any DFS, every cycle of reachable nodes contains a retreating edge; in particular a DFS with no retreating edge certifies an acyclic reachable graph.

Proof

Let \(c\) be the node of the cycle with the smallest preorder number and \(p\) its predecessor on the cycle. When \(c\) is discovered, every other node of the cycle is undiscovered (larger preorder number) and reachable from \(c\) along the cycle through undiscovered nodes. By the white-path theorem of depth-first search [Tar72] they all become descendants of \(c\); so \(c \preceq_T p\) and \(p \to c\) is retreating.

Definition 15.5.4 (Back edge, natural loop)

A back edge (in the dominance sense) is an edge \(t \to h\) with \(h \mathrel{\mathrm{dom}} t\); \(t\) is a latch of the header \(h\). The natural loop of \(h\) is

\[ \mathrm{body}(h) \triangleq \{h\} \cup \{\, x \in N_r \mid \exists\ t \to h \text{ back edge and a path } x \leadsto t \text{ avoiding } h \,\}, \]

so all back edges into one header give one loop (as in LLVM and GCC). \(\mathrm{loop}(t \to h)\) is the same set built from one back edge.

Theorem 15.5.5 (Natural loops are single-entry and nest)

(a) \(h\) dominates every node of \(\mathrm{body}(h)\), so every edge entering \(\mathrm{body}(h)\) from outside enters at \(h\). (b) For headers \(h_1 \neq h_2\), \(\mathrm{body}(h_1)\) and \(\mathrm{body}(h_2)\) are disjoint or one contains the other.

Proof

(a) Let \(x \in \mathrm{body}(h)\), \(x \neq h\), with a path \(x \leadsto t\) avoiding \(h\) to a latch \(t\). A path \(r \leadsto x\) avoiding \(h\), followed by it, would reach \(t\) avoiding \(h\), contradicting \(h \mathrel{\mathrm{dom}} t\). An edge \(y \to x\) from a reachable \(y \notin \mathrm{body}(h)\) with \(x \neq h\) would put \(y\) in the body (prepend it to \(x\)'s path; \(y \neq h\)), so outside edges from reachable blocks enter only at \(h\). (b) Suppose \(x \in \mathrm{body}(h_1) \cap \mathrm{body}(h_2)\). By (a) \(h_1\) and \(h_2\) both dominate \(x\), so they are comparable (Theorem 15.1.6); say \(h_1 \mathrel{\mathrm{sdom}} h_2\). We show \(\mathrm{body}(h_2) \subseteq \mathrm{body}(h_1)\). First, \(h_1 \notin \mathrm{body}(h_2)\): otherwise \(h_2 \mathrel{\mathrm{dom}} h_1\) by (a), contradicting antisymmetry. Take a simple path \(P : r \leadsto x\); it contains \(h_1\) before \(h_2\) (as \(h_1 \mathrel{\mathrm{dom}} h_2\)) and each once, so its suffix after \(h_2\) is a path \(h_2 \leadsto x\) avoiding \(h_1\). Now let \(y \in \mathrm{body}(h_2)\), \(y \neq h_2\), with a path \(y \leadsto t_2\) avoiding \(h_2\); every node on it is in \(\mathrm{body}(h_2)\), hence not \(h_1\). Since \(x \in \mathrm{body}(h_1)\) and \(x \neq h_1\) (because \(h_1 \notin \mathrm{body}(h_2)\)), \(x\) has a (possibly empty) path to a latch of \(h_1\) avoiding \(h_1\). The path \(y \leadsto t_2 \to h_2 \leadsto x \leadsto t_1\) avoids \(h_1\): so \(y \in \mathrm{body}(h_1)\), and its suffix from \(h_2\) shows \(h_2 \in \mathrm{body}(h_1)\).

Definition 15.5.6 (Entries, reducible cycle, loop nesting forest)

An entry of a node set \(L\) is a node of \(L\) with a predecessor outside \(L\) (or \(r \in L\)). An SCC, or a loop of a forest, is reducible if it has exactly one entry. (For an arbitrary cycle this would be the wrong test: in \(r \to d\), \(d \to x\), \(d \to z\), \(z \to x\), \(x \to y\), \(y \to d\) the cycle \(d \to x \to y \to d\) is also entered at \(x\), from \(z\), yet the graph is reducible; its SCC \(\{d, x, y, z\}\) has the single entry \(d\).) A loop nesting forest is a family of node sets (loops), each with a non-empty set of headers, such that any two loops are disjoint or nested, and inside each loop, removing the edges into its header(s) leaves its child loops as the maximal cycles [Ram02]. Forests differ in how they choose headers: all entries (Steensgaard), the DFS-first entry (Havlak), or only dominating headers (natural loops).

Natural loops¶

Algorithm 15.5.7 (Natural loops)

Input: \(G\) and its dominator tree \(\mathcal{D}\).
Output: the natural loop forest: per header, latches, body, parent, depth; per node, the innermost loop.
Precondition: \(\mathcal{D}\) is correct; unreachable predecessors are ignored.
Postcondition: the loops are the sets \(\mathrm{body}(h)\) of Definition 15.5.4, nested by containment (the loops LoopInfo reports).
Invariant: every node added to a body reaches a latch without passing through \(h\) (and is therefore dominated by \(h\), Theorem 15.5.5).

function NaturalLoops(G, D):
    latches ← map from header to list
    for each edge t → h with t reachable:
        if D.dominates(h, t): append t to latches[h]
    loops ← []
    for each header h in latches:
        body ← {h}
        work ← []
        for t in latches[h]:
            if t ∉ body: body ← body ∪ {t}; push t on work
        while work not empty:
            x ← pop work
            for p in preds(x):
                if p reachable and p ∉ body:
                    body ← body ∪ {p}; push p on work
        append (h, latches[h], body) to loops
    for each loop L:                                 # nesting
        parent(L) ← the smallest other loop whose body contains header(L)
        depth(L) ← 1 + number of ancestors of L
    innermost(x) ← the deepest loop containing x
    return loops

You implement it as computeNaturalLoops(G, DT) (E13).

Tarjan's loop nesting¶

Algorithm 15.5.8 (Tarjan's loop nesting and reducibility test)

Input: \(G\) and a DFS (pre, last).
Output: the loop forest of a reducible \(G\), or IRREDUCIBLE.
Precondition: none; the answer IRREDUCIBLE is exact.
Postcondition: if \(G\) is reducible, each header \(w\)'s loop is \(\mathrm{body}(w)\) and header[x] is the innermost enclosing header of \(x\).
Invariant: when \(w\) is processed (in decreasing preorder), every loop whose header is later in preorder has been collapsed into its header, and \(\mathrm{Find}(x)\) is the header of the outermost collapsed loop containing \(x\) (Theorem 15.5.13).

function TarjanLoops(G, dfs):
    for w in N (reachable):
        backPreds[w] ← { v ∈ preds(w) : IsAncestor(w, v) }           # includes w → w
        nonBackPreds[w] ← the other reachable predecessors
        UF.makeSet(w); header[w] ← none
    for w in reachable nodes in decreasing preorder:
        P ← { UF.find(v) : v ∈ backPreds[w], v ≠ w }
        worklist ← P
        while worklist not empty:
            x ← pop worklist
            for y in nonBackPreds[x]:
                y′ ← UF.find(y)
                if not IsAncestor(w, y′):          # an entry from outside w's DFS subtree
                    return IRREDUCIBLE
                if y′ ∉ P and y′ ≠ w:
                    P ← P ∪ {y′}; push y′ on worklist
        for x in P:
            header[x] ← w
            UF.union(x, w)                          # x's whole collapsed loop joins w
    return header

function IsAncestor(a, b):
    return pre[a] ≤ pre[b] ≤ last[a]

UF.find(x) returns the representative of \(x\)'s set, the header of the outermost loop collapsed so far that contains \(x\). The course oracle is tarjan_loop_nesting in tools/course/lib/cfa.py.

Havlak's forest¶

Algorithm 15.5.9 (Havlak's loop nesting forest)

Input: \(G\) and a DFS (pre, last).
Output: one loop per header, with its kind (self, reducible, irreducible), members, parent and depth.
Precondition: none (irreducible CFGs allowed).
Postcondition: on the same DFS, the forest is CycleInfo's; on reducible CFGs it is the natural loop forest; a loop is marked irreducible iff it has an entry other than its header.
Invariant: as for Algorithm 15.5.8, plus: nonBackPreds[w] contains every edge from outside \(w\)'s DFS subtree into \(w\)'s collapsed loop, so an enclosing header sees the entries of its inner irreducible loops (Theorem 15.5.14).

function Havlak(G, dfs):
    for w in N (reachable):
        backPreds[w] ← { v ∈ preds(w) : IsAncestor(w, v) }           # includes w → w
        nonBackPreds[w] ← the other reachable predecessors
        UF.makeSet(w); header[w] ← none
    for w in reachable nodes in decreasing preorder:
        P ← {}
        for v in backPreds[w]:
            if v ≠ w: P ← P ∪ {UF.find(v)}
            else: type[w] ← self
        if P ≠ {}: type[w] ← reducible
        worklist ← P
        while worklist not empty:
            x ← pop worklist
            for y in nonBackPreds[x]:
                y′ ← UF.find(y)
                if not IsAncestor(w, y′):          # an entry from outside w's DFS subtree
                    type[w] ← irreducible
                    nonBackPreds[w] ← nonBackPreds[w] ∪ {y}   # carried up to w
                else if y′ ∉ P and y′ ≠ w:
                    P ← P ∪ {y′}; push y′ on worklist
        for x in P:
            header[x] ← w
            UF.union(x, w)                          # x's whole collapsed loop joins w
    loops ← one per w with type[w] defined; parent(loop of w) = loop of header[w]
    return loops

This is [Hav97, Figure 3]; it needs no dominators. You implement it as computeHavlakLoops(G, D) (E14).

Steensgaard's forest¶

Algorithm 15.5.10 (Steensgaard's loop nesting forest)

Input: \(G\).
Output: loops as SCCs, each with its set of headers.
Precondition: none.
Postcondition: the top-level loops are the non-trivial SCCs of \(G\); inside a loop \(C\) with headers \(H_C\), the child loops are the non-trivial SCCs of \(C\) without the edges into \(H_C\).
Invariant: every recursive call receives a node set \(C\) and an edge set strictly smaller than its parent's (Theorem 15.5.15).

function Steensgaard(G):
    return Forest(reachable nodes of G, edges of G, parent = none, depth = 1)

function Forest(nodes, edges, parent, depth):
    loops ← []
    for C in SCCs(nodes, edges):                    # Tarjan's SCC algorithm [Tar72]
        if C has no internal edge: continue         # a single node without self loop
        headers ← { x ∈ C : x has a predecessor outside C, or x = r }
        append (headers, C, parent, depth) to loops
        inner ← { u → v ∈ edges : u, v ∈ C and v ∉ headers }     # drop edges into headers
        loops ← loops ++ Forest(C, inner, headers, depth + 1)
    return loops

The course has it only as the Python oracle steensgaard_loops.

3. Worked example¶

DFS edge classification on the running example¶

Successors in listed order; one row per event (tree edges are shown by the visit they cause):

#	event	DFS stack (bottom→top)	preorder so far	postorder so far
1	visit A (pre 1)	A	A
2	visit B (pre 2)	A B	A B
3	visit C (pre 3)	A B C	A B C
4	visit D (pre 4)	A B C D	A B C D
5	visit E (pre 5)	A B C D E	A B C D E
6	visit F (pre 6)	A B C D E F	A B C D E F
7	visit G (pre 7)	A B C D E F G	A B C D E F G
8	visit H (pre 8)	A B C D E F G H	A B C D E F G H
9	visit I (pre 9)	A B C D E F G H I	A B C D E F G H I
10	finish I (post 1)	A B C D E F G H	A B C D E F G H I	I
11	edge H→B: B is on the stack → retreating	A B C D E F G H	A B C D E F G H I	I
12	finish H (post 2)	A B C D E F G	A B C D E F G H I	I H
13	edge G→E: E is on the stack → retreating	A B C D E F G	A B C D E F G H I	I H
14	finish G (post 3)	A B C D E F	A B C D E F G H I	I H G
15	finish F (post 4)	A B C D E	A B C D E F G H I	I H G F
16	edge E→H: H finished, pre(H) = 8 > pre(E) = 5 → forward	A B C D E	A B C D E F G H I	I H G F
17	finish E (post 5)	A B C D	A B C D E F G H I	I H G F E
18	finish D (post 6)	A B C	A B C D E F G H I	I H G F E D
19	edge C→H: H finished, pre(H) = 8 > pre(C) = 3 → forward	A B C	A B C D E F G H I	I H G F E D
20	finish C (post 7)	A B	A B C D E F G H I	I H G F E D C
21	edge B→E: E finished, pre(E) = 5 > pre(B) = 2 → forward	A B	A B C D E F G H I	I H G F E D C
22	finish B (post 8)	A	A B C D E F G H I	I H G F E D C B
23	finish A (post 9)	(empty)	A B C D E F G H I	I H G F E D C B A

Retreating edges: H→B and G→E. There are no cross edges here; in @chk_irreducible (Lesson 15.1) B→C and B→D are cross edges.

Try it

./course drill rpo --seed 8 --difficulty hard --solution classifies every edge of a random, possibly irreducible, CFG.

Natural loops on the running example¶

Back edges (head dominates tail): H → B (B dom H) and G → E (E dom G); they are exactly the retreating edges, as they must be in a reducible CFG (Theorem 15.6.4).

header	step	work (stack)	action	body
E	0	G	latch G	{E, G}
E	1	F	pop G: pred F added	{E, F, G}
E	2	(empty)	pop F: pred E is the header	{E, F, G}
B	0	H	latch H	{B, H}
B	1	C E G	pop H: preds C, E, G added	{B, C, E, G, H}
B	2	C E F	pop G: pred F added	{B, C, E, F, G, H}
B	3	C E	pop F: pred E already in	same
B	4	C D	pop E: preds B (in), D added, G (in)	{B, C, D, E, F, G, H}
B	5	C	pop D: pred C already in	same
B	6	(empty)	pop C: pred B is the header	same

Nesting: E's header lies in B's body, so parent(E-loop) = B-loop (Theorem 15.5.5(b)); depths: A 0, B 1, C 1, D 1, E 2, F 2, G 2, H 1, I 0.

On @running_irreducible, G → E is still a retreating edge of the same DFS, but E no longer dominates G: the path A B C D F G avoids E. So only H → B is a back edge, LoopInfo reports just the B loop, and E, F and G sit at depth 1.

Tarjan's loop nesting on the running example¶

Reverse preorder I H G F E D C B A. backPreds: B ← {H}, E ← {G}; all other predecessors are non-back.

w	P from backPreds	worklist steps (y ∈ nonBackPreds, find(y), in w's subtree?)	collapse (UF)
I, H, G, F	—	—	—
E	{G}	pop G: F → F, yes → add F; pop F: E = w, skip	F, G into E
D, C	—	—	—
B	{H}	pop H: C → C yes add; E → E yes add; G → E (collapsed), already in; pop E: B = w; D → D yes add; pop D: C in P; pop C: B = w	C, D, E, H into B
A	—	—	—

The forest equals the natural loops, and no entry from outside a subtree was met: the CFG is reducible.

Havlak's forest on the irreducible variant¶

@running_irreducible has the same DFS (D → F becomes a forward edge). nonBackPreds(F) = {E, D}.

w	P	worklist steps	carried to w	type	collapse
E	{G}	pop G: F → F in E's subtree (pre 6 ∈ [5, 9]; E's DFS subtree is E F G H I) → add; pop F: E = w; D → D, pre 4 ∉ [5, 9] → irreducible	D → nonBackPreds(E)	irreducible	F, G into E
B	{H}	pop H: C, E (G → E) added; pop E: B = w, D (original) and D (carried) → add D; pop D: C in P; pop C: B = w	—	reducible	C, D, E, H into B

Havlak's forest: B (reducible, depth 1) containing E (irreducible, depth 2, body {E, F, G}). Tarjan's algorithm stops at w = E with "irreducible". This is what print<cycles> prints (entries(E F) G at depth 2): CycleInfo lists both entries and picks E, the first one the DFS reached, as header.

Steensgaard's forest on the irreducible variant¶

level	component	entries → headers	edges removed before recursing
1	{B, C, D, E, F, G, H}	B (pred A)	H → B
2	{E, F, G} (inside, after removing H → B)	E (preds B, D), F (pred D)	G → E, E → F
3	inside {E, F, G} without those edges: no cycle	—	—

Steensgaard gives the inner loop two headers, E and F, independent of the DFS; Havlak gives it one header, E, because the DFS reached E first. On the reducible running example both give B ⊃ E with single headers, the same as natural loops.

Try it

./course drill natural-loops --seed 2 --difficulty hard --solution shows back edges, bodies, T1/T2, and the Havlak and Steensgaard forests of an irreducible CFG.

4. Invariants and correctness¶

DFS edge classification¶

Theorem 15.5.11 (Correctness of Algorithm 15.5.2)

Algorithm 15.5.2 visits every reachable node once, classifies every edge by Definition 15.5.1, and \(a \preceq_T b \iff \mathrm{pre}(a) \le \mathrm{pre}(b) \le \mathrm{last}(a)\).

Proof

Stack invariant: Visit(v) is called from Visit(parent(v)), so the active calls (the stack) are the tree path from \(r\) to the current node, i.e. its ancestors. Classification: when \(u\) examines \(u \to v\): an undiscovered \(v\) is discovered through this edge (tree); a \(v\) on the stack is an ancestor of \(u\) (retreating); a finished \(v\) with \(\mathrm{pre}(v) > \mathrm{pre}(u)\) was discovered while \(u\) was active, hence in \(u\)'s subtree (forward); a finished \(v\) with a smaller number finished before \(u\) was discovered — had it been an ancestor, it would still be active — so it is in an earlier, disjoint subtree (cross). Intervals: the nodes numbered while \(u\) is active are exactly its descendants, so they occupy \([\mathrm{pre}(u), \mathrm{last}(u)]\). Termination: each node is visited once; each edge examined once.

When it breaks: which edges are retreating depends on the successor order; only in reducible CFGs is the set independent of the DFS (Hecht–Ullman, Theorem 15.6.4 in Lesson 15.6).

Natural loops¶

Theorem 15.5.12 (Correctness of Algorithm 15.5.7)

Algorithm 15.5.7 computes \(\mathrm{body}(h)\) for every header, and its nesting by containment is a tree.

Proof

Bodies: the reverse walk starts at the latches and follows predecessors, never expanding \(h\) (it is in body from the start); a node is added iff it reaches a latch by a path avoiding \(h\), which is Definition 15.5.4. Unreachable predecessors are skipped because they are in no path from \(r\) and are not dominated by \(h\). Nesting: by Theorem 15.5.5(b), the loops containing a given header form a chain under \(\subseteq\), so "the smallest other loop containing header(L)" is well defined and the parent relation is a forest. Termination: each node enters each body once.

When it breaks: counting unreachable predecessors (they are not dominated by \(h\), and LLVM ignores them: unreachable.ll's @dead_into_loop); expecting irreducible cycles to appear.

Tarjan's loop nesting¶

Theorem 15.5.13 (Correctness of Tarjan's algorithm)

Algorithm 15.5.8 returns IRREDUCIBLE iff \(G\) is irreducible; otherwise header describes the natural loop forest.

Proof sketch (full proof: [Tar74, §2–3])

Process \(w\) in decreasing preorder. By induction, all loops with headers after \(w\) are collapsed, so \(\mathrm{Find}\) maps each node to the outermost such header. \(P\) starts with the (collapsed) sources of retreating edges into \(w\), which are in \(w\)'s DFS subtree, and grows backwards through non-retreating predecessors. If every such predecessor stays in \(w\)'s subtree, \(P\) is exactly the set of subtree nodes that reach a retreating-edge source of \(w\) without passing \(w\): the natural loop of \(w\) (\(w\) dominates it, since the only way into the subtree from outside is through \(w\) — any other entry would be found). If some predecessor lies outside the subtree, a path enters the cycle through \(w\) other than via \(w\): the cycle has two entries and \(G\) is irreducible (Theorem 15.6.4). Termination: each node joins \(P\) at most once per \(w\) and is collapsed once.

Havlak's forest¶

Theorem 15.5.14 (Correctness of Havlak's algorithm)

For a fixed DFS, Algorithm 15.5.9 returns a loop nesting forest whose loop with header \(w\) is the largest cycle-closed set inside \(w\)'s DFS subtree that reaches a retreating-edge source of \(w\); it is marked irreducible iff it has an entry other than \(w\). On reducible CFGs it coincides with the natural loop forest.

Proof sketch (full proof: [Hav97, §3]; complexity: [Ram99])

As in Theorem 15.5.13, \(P\) collects the subtree nodes that reach a retreating-edge source of \(w\) after collapsing. A predecessor outside the subtree is an extra entry: instead of stopping, the algorithm marks \(w\)'s loop irreducible and carries the edge up (nonBackPreds[w]), so the enclosing header examines it later, where it may be internal. The loop stays inside \(w\)'s subtree, so \(w\) is its unique header — the DFS-first entry. This is the cycle of LLVM's CycleTerminology.md for the same DFS [LLVM-CycleTerm]: the tests ch15.Havlak.* compare your forest with CycleInfo on 1 650 CFGs after reversing successor lists (CycleInfo's DFS pops the last successor first). On a reducible CFG no carried edge exists and the algorithm is Tarjan's.

When it breaks: re-examining carried edges at every level: Ramalingam's quadratic case (section 5).

Steensgaard's forest¶

Theorem 15.5.15 (Correctness of Steensgaard's construction)

Algorithm 15.5.10 terminates, and its output is a loop nesting forest (Definition 15.5.6) whose loops are SCCs and whose headers are all entries.

Proof

Termination: in a non-trivial SCC \(C\) every node has a predecessor inside \(C\) (a self loop, or a node of \(C\) reaching it), so in particular each header has an internal incoming edge, and inner has strictly fewer edges than the edges of \(C\). Forest: SCCs of one graph are disjoint, and the recursion only looks inside \(C\), so loops are disjoint or nested. Maximality: each returned set is an SCC, a maximal set of mutually reachable nodes, of its parent loop's graph with the edges into the parent's headers removed; removing those edges breaks every cycle through a header, so the child loops are exactly the maximal cycles avoiding the headers, as Definition 15.5.6 requires [Ste93].

5. Complexity¶

\(n\) = nodes, \(m\) = edges, \(k\) = maximum loop nesting depth, \(\alpha\) = inverse Ackermann.

Technique	Time (worst)	Time (typical)	Space	Notes
DFS edge classification	\(O(n + m)\)	linear	\(O(n)\)	iterative to avoid stack overflow
Natural loops (per-header walks, E13)	\(O(k \cdot (n + m))\)	near-linear	\(O(n \cdot k)\) for explicit bodies	LLVM's subloop skipping makes discovery \(O(n + m)\)
Tarjan's loop nesting	\(O(m\,\alpha(m, n))\)	linear	\(O(n + m)\)	stops at the first irreducible header
Havlak	\(O(n \cdot m)\) as published; \(O(m\,\alpha(m, n))\) with [Ram99]	near-linear	\(O(n + m)\)	carried edges are the risk
Steensgaard	\(O(k \cdot (n + m)) \subseteq O(n \cdot m)\)	near-linear	\(O(n + m)\)	one SCC pass per nesting level

Proposition 15.5.16 (Cost of the loop forests)

Algorithm 15.5.7 runs in \(O(k \cdot (n + m))\); Algorithm 15.5.10 in \(O(k \cdot (n + m))\); Algorithms 15.5.8 and 15.5.9 perform \(O(m)\) union-find operations, plus, for Havlak as published, re-examinations of carried edges.

Proof

A node lies in at most \(k\) natural loops and is walked once per loop, scanning its predecessors each time: \(O(k(n + m))\). Steensgaard's recursion depth is the nesting depth and each level runs a linear-time SCC algorithm on disjoint components. In Tarjan's and Havlak's algorithms each predecessor edge is examined when its target joins some \(P\), which happens once per enclosing header in the worst case unless collapsed nodes are skipped — the union-find does exactly that, giving \(O(m)\) Finds and \(O(n)\) Unions, i.e. \(O(m\,\alpha(m, n))\) [Tar74]. The carried edges are the exception, as the family below shows.

Pathological input: \(k\) irreducible loops nested inside each other, each with a second entry edge from the function entry into its body: when Havlak processes the \(i\)-th header from the inside, it re-examines the \(i - 1\) entry edges carried up from the inner loops, \(\Theta(k^2)\) examinations for a graph of size \(\Theta(k)\). Ramalingam's fix links carried edges so each is examined a constant number of times [Ram99]. For natural loops, \(k\) perfectly nested loops make the per-header walk (E13) visit \(\Theta(k^2)\) nodes; LLVM's discoverAndMapSubloop jumps over already discovered subloops [LLVM-LoopInfo].

At scale: LLVM computes LoopInfo for every function in every optimization pipeline; its comment in LoopInfoBase::analyze states the discovery is linear in the number of CFG edges, and populating the explicit block lists costs "loop-depth number of insertions per block".

DFS edge classification¶

Stack-of-successor-iterators DFS (LLVM's po_iterator, the course solution) vs pop-time marking (LLVM's CycleInfo DFS, SemiNCAInfo::runDFS) — trade-off: the second is simpler but, if successors are pushed in order, explores the last successor first; reverse them first to get the same DFS.
Loop-aware RPO (V8's SpecialRPONumberer) [V8-Scheduler] — trade-off: extra work to keep every loop's blocks contiguous in the order, which schedulers want.

Natural loops¶

Subloop skipping (LLVM discoverAndMapSubloop) — trade-off: linear discovery, slightly more complex code.
Merging back edges per header vs one loop per back edge — trade-off: LLVM and GCC merge (one loop, several latches); some textbooks keep one loop per edge, which gives nested loops with the same header.
Loops from the DJ graph [SGL96] — trade-off: finds reducible and irreducible loops in one framework, needs the DJ graph.

Tarjan's loop nesting¶

Interval-based nesting (Allen–Cocke, Lesson 15.6) — trade-off: intervals are not exactly loops (an interval contains acyclic tails).
Reducibility test only (drop the forest) — trade-off: the cheapest exact reducibility check without dominators.

Havlak's forest¶

Ramalingam's correction [Ram99] — trade-off: almost-linear time, more bookkeeping for carried edges.
CycleInfo's variant (LLVM): builds the same forest with a top-level-parent map instead of union-find, and records all entries of each cycle — trade-off: entries are available (for fix-irreducible), union-find is not needed because cycles are moved under their parent explicitly.
Wei–Mao–Zou–Chen loop identification [WMZC07], designed for decompilers — trade-off: one DFS pass that finds headers and nesting together, harder to follow than Havlak's two-phase formulation.

Steensgaard's forest¶

Sreedhar–Gao–Lee forest on DJ graphs [SGL96] — trade-off: headers are the entries of the outermost SCC like Steensgaard, but inner loops are found by level.
GCC's irreducible marking (below) — trade-off: only marks irreducible regions (blocks and edges) via SCCs after removing latch edges; it does not build a second forest.

7. In real compilers¶

DFS edge classification¶

LLVM llvm/lib/Analysis/CFG.cpp — llvm::FindFunctionBackedges: a DFS with an explicit stack of successor iterators that reports retreating edges (called "backedges") [LLVM-CFGcpp]; llvm/include/llvm/ADT/GenericCycleImpl.h — GenericCycleInfoCompute::dfs computes preorder and subtree ranges (LLVM 23.1.2) [LLVM-Cycle].
GCC 15 gcc/cfganal.cc — mark_dfs_back_edges: flags EDGE_DFS_BACK on retreating edges [GCC-Cfganal].
V8 src/compiler/scheduler.cc — SpecialRPONumberer::ComputeSpecialRPO: a DFS that identifies loops by their back edges and keeps them contiguous (V8 13.8) [V8-Scheduler].

GCC marks retreating edges DFS_BACK

Reproduce (gcc-14 = GCC 14.2.0, Ubuntu build 14.2.0-4ubuntu2~24.04.1; the sed only removes profile counts):

cat > scale.c <<'EOF'
void scale(int n, int m, int *a) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      a[i * m + j] *= 2;
}
EOF
gcc-14 -O1 -fdump-tree-profile_estimate-blocks-details=scale.pe -c scale.c -o /dev/null
grep -E '^;; basic block|^;;  succ|^;;              [0-9E]' scale.pe | sed -E 's/,? +count:? ?[0-9]+ \([^)]*\)//'

Output (complete, filtered):

;; basic block 2, loop depth 0, maybe hot
;;  succ:       6 [always] (FALLTHRU,EXECUTABLE) scale.c:2:3
;; basic block 3, loop depth 2, maybe hot
;;  succ:       4 [always] (FALLTHRU,DFS_BACK,EXECUTABLE)
;; basic block 4, loop depth 2, maybe hot
;;              3 [always] (FALLTHRU,DFS_BACK,EXECUTABLE)
;;  succ:       3 [89.0% (guessed)] (TRUE_VALUE,EXECUTABLE)
;;              5 [11.0% (guessed)] (FALSE_VALUE,EXECUTABLE)
;; basic block 5, loop depth 1, maybe hot
;;  succ:       6 [always] (FALLTHRU,DFS_BACK,EXECUTABLE)
;; basic block 6, loop depth 1, maybe hot
;;              5 [always] (FALLTHRU,DFS_BACK,EXECUTABLE)
;;  succ:       8 [89.0% (guessed)] (TRUE_VALUE,EXECUTABLE)
;;              7 [11.0% (guessed)] (FALSE_VALUE,EXECUTABLE)
;; basic block 8, loop depth 1, maybe hot
;;  succ:       4 [always] (FALLTHRU)
;; basic block 7, loop depth 0, maybe hot
;;  succ:       EXIT [always] (EXECUTABLE) scale.c:5:1

What to notice: GCC's mark_dfs_back_edges flags exactly two edges DFS_BACK: 3 → 4 (the inner loop's latch to its header) and 5 → 6 (the outer latch to the outer header); every other edge is a tree, forward or cross edge (Definition 15.5.1). Each retreating edge's target has the loop depth of a loop header, and on this reducible CFG the retreating edges are the dominance back edges (Theorem 15.6.4). Block 8, which leads from the outer header into the inner loop, is a preheader that GCC's loop code inserted (compare Lesson 15.7).

Natural loops¶

LLVM

llvm/include/llvm/Support/GenericLoopInfoImpl.h — LoopInfoBase::analyze visits dominator-tree nodes in reverse preorder, collects predecessors the node dominates (the back edges), and calls discoverAndMapSubloop (reverse walk that skips inner subloops); PopulateLoopsDFS fills the block lists [LLVM-LoopInfo]. llvm/lib/Analysis/LoopInfo.cpp instantiates it and implements Loop::isLoopSimplifyForm, Loop::isLCSSAForm (Lesson 15.7) (LLVM 23.1.2) [LLVM-LoopInfoCpp].

GCC 15 gcc/cfgloop.cc — flow_loops_find: natural loops from back edges whose destination dominates their source, loops with the same header merged, stored in loop_father.
Cranelift (Wasmtime 36) cranelift/codegen/src/loop_analysis.rs — LoopAnalysis::compute: find_loop_headers ("a block is a loop header if it dominates any of its predecessors") and discover_loop_blocks [Cranelift-Loops].
Go 1.25 src/cmd/compile/internal/ssa/likelyadjust.go — loopnestfor: headers from dominated predecessors, with a hasIrreducible flag when that fails [Go-Loopnest].

LoopInfo on a loop nest

Reproduce (clang 23.1.2, opt 23.1.2):

cat > scale.c <<'EOF'
void scale(int n, int m, int *a) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      a[i * m + j] *= 2;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm scale.c -o scale.ll
opt -passes='sroa,print<loops>' -disable-output scale.ll

Output (complete):

Loop info for function 'scale':
Loop at depth 1 containing: %for.cond<header><exiting>,%for.body,%for.cond1,%for.end,%for.inc5<latch>,%for.body3,%for.inc
    Loop at depth 2 containing: %for.cond1<header><exiting>,%for.body3,%for.inc<latch>

What to notice: each loop is \(\mathrm{body}(h)\) of Definition 15.5.4: header for.cond with the latch for.inc5, and the inner header for.cond1 with latch for.inc. The inner body is contained in the outer one (Theorem 15.5.5(b)) and printed indented at depth 2. <exiting> marks blocks with a successor outside the loop; Lesson 15.7 uses the same vocabulary [LLVM-LoopTerm].

Tarjan's loop nesting¶

HotSpot C2 (JDK 25) src/hotspot/share/opto/loopnode.cpp — PhaseIdealLoop::build_loop_tree ("I use a modified Vick/Tarjan algorithm"): a pre/post-order DFS that builds IdealLoopTrees and flags _irreducible loops instead of stopping [HotSpot-Loops].
LLVM has no Tarjan-style forest; reducibility is tested with containsIrreducibleCFG (Lesson 15.6).

On a reducible CFG every forest agrees

Reproduce (clang 23.1.2, opt 23.1.2; running.c is the running example of Lesson 15.1, section 7, with G fused into F):

cat > running.c <<'EOF'
void work(int);
void running(int *c) {
B:  if (c[0]) goto C; goto E;
C:  if (c[1]) goto D; goto H;
D:  work(4); goto E;
E:  if (c[2]) goto F; goto H;
F:  work(6); goto G;
G:  if (c[3]) goto H; goto E;
H:  if (c[4]) goto I; goto B;
I:  return;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm running.c -o running.ll
opt -passes='simplifycfg,print<loops>,print<cycles>' -disable-output running.ll

Output (complete):

Loop info for function 'running':
Loop at depth 1 containing: %B<header>,%C,%D,%E,%F,%H<latch><exiting>
    Loop at depth 2 containing: %E<header><exiting>,%F<latch><exiting>
CycleInfo for function: running
    depth=1: entries(B) H C E F D
        depth=2: entries(E) F

What to notice: LoopInfo (natural loops, from dominators) and CycleInfo (Havlak's forest, from a DFS) report the same two loops, B ⊃ E, with single entries. That is the forest Tarjan's algorithm builds without dominators on a reducible CFG (Theorem 15.5.13), and what HotSpot's modified Vick/Tarjan loop tree computes for Java bytecode, which is almost always reducible.

Havlak's forest¶

LLVM

llvm/include/llvm/ADT/GenericCycleImpl.h — GenericCycleInfoCompute::run: header candidates in reverse preorder, predecessors that are DFS descendants seed a worklist, non-descendant predecessors make a block an extra entry (appendEntry), and already discovered cycles are moved under the new one (moveTopLevelCycleToNewParent) [LLVM-Cycle]. llvm/lib/Analysis/CycleAnalysis.cpp exposes CycleAnalysis and print<cycles>; llvm/docs/CycleTerminology.md cites Havlak for the definition (LLVM 23.1.2) [LLVM-CycleTerm].

LLVM users: UniformityAnalysis (GPU divergence) and FixIrreducible (llvm/lib/Transforms/Utils/FixIrreducible.cpp, fixIrreducible(Cycle &C, …)) consume CycleInfo [LLVM-FixIrr].
Pebble your computeHavlakLoops (E14), print<pebble-loops;havlak>.

An irreducible inner cycle: LoopInfo drops it, CycleInfo keeps it

Reproduce (clang 23.1.2, opt 23.1.2; running_irr.c is running.c plus the edge D → F):

cat > running_irr.c <<'EOF'
void work(int);
void running_irr(int *c) {
B:  if (c[0]) goto C; goto E;
C:  if (c[1]) goto D; goto H;
D:  work(4); if (c[5]) goto E; goto F;
E:  if (c[2]) goto F; goto H;
F:  work(6); goto G;
G:  if (c[3]) goto H; goto E;
H:  if (c[4]) goto I; goto B;
I:  return;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm running_irr.c -o running_irr.ll
opt -passes='simplifycfg,print<loops>,print<cycles>' -disable-output running_irr.ll

Output (complete):

Loop info for function 'running_irr':
Loop at depth 1 containing: %B<header>,%C,%D,%E,%F,%H<latch><exiting>
CycleInfo for function: running_irr
    depth=1: entries(B) H C E F D
        depth=2: entries(E F)

What to notice: with D → F, E no longer dominates F, so the only back edge is H → B and LoopInfo reports one loop with E and F at depth 1. CycleInfo reports Havlak's forest: the outer cycle B and, nested inside, the cycle {E, F} with two entries, entries(E F) — an irreducible cycle (Theorem 15.5.14). Its header is the first entry printed, the one CycleInfo's DFS reached first; Havlak's Irreducible flag corresponds to "more than one entry". This is the lesson's @running_irreducible with G fused into F.

Steensgaard's forest¶

GCC 15 gcc/cfgloopanal.cc — mark_irreducible_loops: "we throw away all latch edges and mark blocks inside any remaining cycle", computed with SCCs (graphds_scc), Steensgaard-style but only to flag BB_IRREDUCIBLE_LOOP and EDGE_IRREDUCIBLE_LOOP [GCC-Loops].
Production compilers do not build Steensgaard's full forest; it is used in research (program dependence graphs of irreducible programs [Ste93]) and in Ramalingam's comparisons [Ram02]. The course implements it only as a Python oracle.

GCC marks the SCC of an irreducible loop

Reproduce (gcc-14 = GCC 14.2.0, Ubuntu build 14.2.0-4ubuntu2~24.04.1):

cat > goto.c <<'EOF'
int g(int n, int k) {
  int s = 0, i = 0;
  if (k) goto inside;
  while (i < n) {
    s += i;
  inside:
    s += 2;
    i++;
  }
  return s;
}
EOF
gcc-14 -O1 -fdump-tree-profile_estimate-blocks-details=goto.pe -c goto.c -o /dev/null
grep -E '^;; basic block|^;;  (prev|succ)|^;;              [0-9E]' goto.pe | sed -E 's/,? +count:? ?[0-9]+ \([^)]*\)//'

Output (complete, filtered):

;; basic block 2, loop depth 0, maybe hot
;;  prev block 0, next block 3, flags: (NEW, VISITED)
;;  succ:       3 [34.0% (guessed)] (TRUE_VALUE,EXECUTABLE)
;;              6 [66.0% (guessed)] (FALSE_VALUE,EXECUTABLE)
;; basic block 3, loop depth 0, maybe hot
;;  prev block 2, next block 4, flags: (NEW, VISITED)
;;  succ:       5 [always] (FALLTHRU,EXECUTABLE) goto.c:3:10
;; basic block 4, loop depth 0, maybe hot
;;  prev block 3, next block 5, flags: (NEW, IRREDUCIBLE_LOOP, VISITED)
;;  succ:       5 [always] (FALLTHRU,DFS_BACK,IRREDUCIBLE_LOOP,EXECUTABLE)
;; basic block 5, loop depth 0, maybe hot
;;  prev block 4, next block 6, flags: (NEW, IRREDUCIBLE_LOOP, VISITED)
;;              4 [always] (FALLTHRU,DFS_BACK,IRREDUCIBLE_LOOP,EXECUTABLE)
;;  succ:       6 [always] (FALLTHRU,IRREDUCIBLE_LOOP,EXECUTABLE)
;; basic block 6, loop depth 0, maybe hot
;;  prev block 5, next block 7, flags: (NEW, IRREDUCIBLE_LOOP, VISITED)
;;              5 [always] (FALLTHRU,IRREDUCIBLE_LOOP,EXECUTABLE)
;;  succ:       4 [50.0% (guessed)] (IRREDUCIBLE_LOOP,TRUE_VALUE,EXECUTABLE)
;;              7 [50.0% (guessed)] (FALSE_VALUE,EXECUTABLE)
;; basic block 7, loop depth 0, maybe hot
;;  prev block 6, next block 1, flags: (NEW, VISITED)
;;  succ:       EXIT [always] (EXECUTABLE) goto.c:10:10

What to notice: goto.c jumps into the middle of the while loop (block 3 → 5), so the cycle {4, 5, 6} has two entries, 5 and 6, and GCC finds no natural loop (every block has loop depth 0). mark_irreducible_loops removes the latch edges and marks every block and edge of the remaining SCC IRREDUCIBLE_LOOP — the SCC that Steensgaard's forest would return, with both entries (5 and 6) as headers (Algorithm 15.5.10). The DFS entered the cycle at 5 (through 3), so it classified 4 → 5 as DFS_BACK: a retreating edge that is not a dominance back edge.

Find where LLVM does it. Open llvm/include/llvm/Support/GenericLoopInfoImpl.h (LLVM 23.1.2) and find the function that LoopInfoBase::analyze calls to perform the backward traversal for one header. Question: what is its name? (Quiz llvm-where-loops.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use	Irreducible CFGs
DFS edge classification	classifies every edge	O(n + m)	tree/back/forward/cross per edge; back edges depend on the DFS	~40 lines	every loop and SCC algorithm	back edges ≠ loops
Natural loops (`LoopInfo`)	reducible loops only	O(n + m) after dominators	header, latches, body, nesting	~60 lines	LLVM, GCC, Cranelift loop optimizers	ignored
Tarjan loop nesting	reducible graphs; stops on irreducible	O(m α(m,n))	forest + reducibility verdict	~70 lines	reducibility test, structural analysis	detected, not handled
Havlak	all cycles; header = first DFS entry	O(m α(m,n)) with Ramalingam's fix	forest with irreducible flags and entries	~90 lines	LLVM `CycleInfo`, GPU divergence analysis	yes
Steensgaard	all cycles; all entries are headers	O(n·m) worst (nested SCCs)	forest with header sets	~50 lines with an SCC routine	GCC irreducible marking (SCC-based)	yes

Choose DFS classification when you need retreating edges or a topological order quickly; never treat its back edges as loops in an irreducible CFG. Choose natural loops when you optimize loops (LICM, unrolling, vectorization need a single header that dominates the body). Choose Tarjan's nesting when you need a fast reducibility test or a forest without dominators on code you know is structured. Choose Havlak when irreducible cycles matter (divergence, structurization, fix-irreducible) and a DFS-dependent header is acceptable. Choose Steensgaard when you need a DFS-independent description of irreducible regions, for example to report them to a user.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch15.yaml`)	Drill	Flashcard tag	Exercises
DFS edge classification	`dfs-edge-kinds`, `reducibility-facts`	`./course drill rpo --difficulty hard`	`dfs-edges`	E1
Natural loops	`natural-loop-body`, `llvm-where-loops`	`./course drill natural-loops`	`natural-loops`	E13
Tarjan's loop nesting	`havlak-irreducible`, `reducibility-facts`	`./course drill natural-loops --difficulty hard --solution`	`tarjan-loops`	— (oracle only)
Havlak	`havlak-irreducible`, `steensgaard-vs-havlak`	`./course drill natural-loops --difficulty hard --solution`	`havlak`	E14
Steensgaard	`steensgaard-vs-havlak`, `reducibility-facts`	`./course drill natural-loops --difficulty hard --solution`	`steensgaard`	— (oracle only)

A DFS back edge is not a natural-loop back edge

A retreating edge is not the same thing as a dominance back edge. G → E in @running_irreducible is retreating for the course's DFS, but E does not dominate G, so there is no natural loop and LoopInfo does not report one. llvm::FindFunctionBackedges returns retreating edges; Loop::getLoopLatch talks about dominance back edges.

References¶

See the chapter references.

Lesson 15.5 — Loop nesting forests¶

1. Problem and motivation¶

DFS edge classification¶

Natural loops¶

Tarjan's loop nesting¶

Havlak's forest¶

Steensgaard's forest¶

2. Definitions and algorithms¶

DFS edge classification¶

Natural loops¶

Tarjan's loop nesting¶

Havlak's forest¶

Steensgaard's forest¶

3. Worked example¶

DFS edge classification on the running example¶

Natural loops on the running example¶

Tarjan's loop nesting on the running example¶

Havlak's forest on the irreducible variant¶

Steensgaard's forest on the irreducible variant¶

4. Invariants and correctness¶

DFS edge classification¶

Natural loops¶

Tarjan's loop nesting¶

Havlak's forest¶

Steensgaard's forest¶

5. Complexity¶

6. Variants and refinements¶

DFS edge classification¶

Natural loops¶

Tarjan's loop nesting¶

Havlak's forest¶

Steensgaard's forest¶

7. In real compilers¶

DFS edge classification¶

Natural loops¶

Tarjan's loop nesting¶

Havlak's forest¶

Steensgaard's forest¶

8. Comparison¶

9. Assessment¶

References¶