Lesson 15.6 — Reducibility¶
Techniques: T1/T2 reduction, interval derived sequences, the DFS back-edge test, node splitting · Pebble implements: T1/T2 (E15); the DFS test is
llvm::containsIrreducibleCFG, which the tests compare with; intervals and node splitting are Python oracles and drills · Lab: your T1/T2 verdict vscontainsIrreducibleCFGand vs Havlak's irreducible loops · Prerequisites: Lesson 15.1, Lesson 15.5, Ch 14 (interval analysis mentioned there) · Time: 3–4 hours
A CFG is reducible when every loop has a single entry. Structured programs produce only reducible CFGs, and a remarkable number of algorithms depend on it: natural loops capture every cycle, iterative dataflow in RPO converges in \(d + 2\) passes with small \(d\), dominance back edges and DFS back edges coincide, and elimination-style dataflow (Ch 14) works at all. The running example is reducible; @running_irreducible (the same CFG plus D → F) is not. This lesson gives four ways to tell them apart, and one way to repair the second.
flowchart TD
A([A]) --> B[B]
B --> C[C]
B --> E[E]
C --> D[D]
C --> H[H]
D --> E
D --> F
E --> F[F]
E --> H
F --> G[G]
G --> H
G --> E
H --> I[I]
H --> B
classDef hl fill:#fde68a,stroke:#b45309;
class E,F hl;(The irreducible variant: the cycle E → F → G → E has two entries, E and F, highlighted.)
1. Problem and motivation¶
The problem. Decide whether a CFG is reducible; if it is not, identify the irreducible part and, optionally, transform the CFG into an equivalent reducible one. LLVM asks this before transformations that assume single-entry loops (MustExecute's loop analysis, StructurizeCFG for GPUs) and repairs irreducible cycles with fix-irreducible; pebblec never creates irreducible CFGs from Pebble source (it has no goto), but C code compiled with clang can contain them (Duff's device, tests/ch15/Inputs/c-duff.ll).
Why structured languages give reducible CFGs. Each structured construct (sequence, if, while, for, break/continue to an enclosing loop, return) produces a region with one entry, and the only way to create a cycle is a loop construct, whose condition block is the single entry of every cycle through the body. Composition preserves this, so every cycle has a unique entry that dominates it. Irreducibility needs a jump into a loop body: goto (the two C functions in tests/ch15/Inputs/c-goto.ll), a switch whose cases land inside a loop (Duff's device, whose do-while gets 8 entries), hand-written state machines, and some transformations such as careless jump threading (LLVM's JumpThreadingPass::findLoopHeaders exists to avoid "turn[ing] proper loop structures into irreducible loops").
T1/T2 reduction¶
Hecht and Ullman defined reducibility by two graph transformations: delete a self loop (T1), and merge a node into its unique predecessor (T2) [HU72]. A graph is reducible iff repeated application shrinks it to a single node; they proved the result does not depend on the order of application (Theorem 15.6.3). It is the textbook definition and a perfect test oracle.
Interval derived sequences¶
Allen introduced intervals: maximal single-entry regions grown from a header by adding nodes all of whose predecessors are already inside [All70]. Collapsing every interval to a node gives the derived graph; repeating gives the derived sequence, which ends in a single node iff the CFG is reducible. Allen and Cocke built the first elimination-based dataflow algorithm on it [AC76] (Ch 14).
The DFS back-edge test¶
Hecht and Ullman later characterized reducibility through DFS: a CFG is reducible iff, for some (equivalently every) DFS, every retreating edge \(u \to v\) has \(v \mathrel{\mathrm{dom}} u\) [HU74] (Theorem 15.6.4). With dominators already computed, this is a linear check; Tarjan's loop-nesting algorithm tests the same property without dominators [Tar74]. LLVM's containsIrreducibleCFG implements it with LoopInfo [LLVM-CFG].
Node splitting¶
An irreducible cycle can be made reducible by giving each extra entry its own copy of the code it enters: node splitting, attributed to Cocke and Miller [CM69] and systematized by Hecht [Hec77]. The copies can grow exponentially [CFT03]; Janssen and Corporaal gave a controlled version that splits as little as possible [JC97]. Production compilers prefer to add a dispatch block instead (LLVM's fix-irreducible), which needs no duplication.
2. Definitions and algorithms¶
\(G = (N, E, r)\), all nodes reachable (unreachable nodes are dropped first).
Definition 15.6.1 (T1, T2, limit graph, region)
T1 removes a self loop \(n \to n\). T2 applies to \(n \neq r\) with exactly one predecessor \(m\): it replaces \(m\) and \(n\) by one node with \(m\)'s predecessors and the union of their successors (minus the edge \(m \to n\)). The limit graph is what remains when neither rule applies. Each limit node stands for the set of original nodes merged into it, its region.
Definition 15.6.2 (Reducible flowgraph)
\(G\) is reducible if its limit graph has a single node [HU72].
Theorem 15.6.3 (T1/T2 is confluent)
Every maximal sequence of T1/T2 applications ends in the same limit graph, up to the names of the merged nodes.
Proof sketch (full proof: [HU72, §3])
T1 and T2 terminate (T1 removes an edge, T2 a node), so by Newman's lemma it suffices to show local confluence: if two rule applications are possible, applying either one leaves the other applicable (or already achieved) up to renaming. Two T1s on different nodes commute. A T1 on \(n\) does not change the number of predecessors of any other node, so a pending T2 stays applicable. Two T2s merging \(n_1\) into \(m_1\) and \(n_2\) into \(m_2\) with \(n_1 \neq n_2\): if \(m_2 = n_1\), merging \(n_1\) into \(m_1\) first makes \(n_2\)'s unique predecessor the merged node, where T2 still applies, and the result is the same set of regions. The other cases do not interact.
Theorem 15.6.4 (Characterizations of reducibility)
The following are equivalent: (a) \(G\) is reducible (Definition 15.6.2); (b) for some DFS of \(G\), every retreating edge \(u \to v\) is a dominance back edge (\(v \mathrel{\mathrm{dom}} u\)); (b′) the same holds for every DFS; (c) removing all dominance back edges leaves an acyclic graph; (d) every cycle contains a node that dominates all nodes of the cycle; (e) \(G\) has no subgraph "(*)": nodes \(c, a, b\) with \(a \neq b\) and \(a, b \neq c\), and paths \(r \leadsto c\), \(c \leadsto a\), \(c \leadsto b\), \(a \leadsto b\), \(b \leadsto a\) that pairwise share only their endpoints (\(c = r\) allowed).
Proof ((b)–(d) in full; (a) and (e): proof sketch, full proof: [HU74, Theorems 1–3])
Let \(B\) be the set of dominance back edges and \(\mathrm{Ret}\) the retreating edges of a DFS. Every dominance back edge \(t \to h\) is retreating: \(h \mathrel{\mathrm{dom}} t\) gives \(h \preceq_T t\) (Lemma 15.1.10). So \(B \subseteq \mathrm{Ret}\) always, and (b) says \(\mathrm{Ret} = B\). No tree edge is in \(B\): a tree edge \(t \to h\) has \(t = \mathrm{parent}(h)\), a proper \(T\)-ancestor of \(h\), while \(h \mathrel{\mathrm{dom}} t\) would make \(h\) an ancestor of \(t\). (b) ⇒ (c). Removing \(B = \mathrm{Ret}\) keeps the DFS tree and the kinds of all other edges, so the remaining graph has a DFS without retreating edges and is acyclic by Lemma 15.5.3. (c) ⇒ (b′). Take any DFS and a retreating edge \(u \to v\). The tree path \(v \leadsto u\) plus \(u \to v\) is a cycle; by (c) it contains an edge of \(B\); its tree edges are not in \(B\), so \(u \to v \in B\). (b′) ⇒ (b) is trivial. (b) ⇒ (d). Let \(c\) be the node of the cycle with the smallest preorder number and \(p\) its predecessor on the cycle. By the proof of Lemma 15.5.3, \(p \to c\) is retreating, so \(c \mathrel{\mathrm{dom}} p\) by (b). If some path \(r \leadsto x\) to a cycle node \(x\) avoided \(c\), continuing along the cycle from \(x\) to \(p\) (which does not pass \(c\), as \(c\) occurs once on the cycle, right after \(p\)) would reach \(p\) avoiding \(c\). So \(c\) dominates the whole cycle. (d) ⇒ (b). Let \(u \to v\) be retreating; the tree path \(v \leadsto u\) plus the edge is a cycle, and by (d) one of its nodes \(d\) dominates all of them, in particular \(v\). Then \(d \preceq_T v\) (Lemma 15.1.10), and \(d\) lies on the tree path below \(v\), so \(d = v\): \(v \mathrel{\mathrm{dom}} u\). (a) ⟺ (b), (e): T2 merges a node into its unique predecessor, which dominates it, and T1 removes a back edge of a region; by induction on the rule applications a graph satisfying (c) reduces completely, and a () subgraph can never be reduced because neither \(a\) nor \(b\) ever gets a unique predecessor while the other is separate. Conversely, if (b) fails, the retreating edge \(u \to v\) with \(v \not\mathrel{\mathrm{dom}} u\) gives a () subgraph with \(a = v\), \(b\) the first node where a path \(r \leadsto u\) avoiding \(v\) meets the tree path \(v \leadsto u\), and \(c\) the last node that path shares with the tree path \(r \leadsto v\). The details are in [HU74].
Reducibility on the running example
In the running example the retreating edges H → B and G → E are dominance back edges, so (b) holds: reducible. In @running_irreducible the retreating edge G → E is not one (the path A B C D F G avoids E), and the cycle E → F → G → E has no node dominating it: (d) fails; \(c = B\), \(a = E\), \(b = F\) with the paths A → B, B → E, B → C → D → F, E → F and F → G → E form the (*) subgraph.
Definition 15.6.5 (Interval, derived graph, derived sequence)
An interval \(I(h)\) with header \(h\) is the maximal set containing \(h\) such that every node of \(I(h)\) other than \(h\) has all its predecessors in \(I(h)\), and every cycle within \(I(h)\) passes through \(h\). The derived graph \(I(G)\) has one node per interval and an edge \(I \to J\) when some edge of \(G\) leaves \(I\) and enters \(J\)'s header. The derived sequence is \(G, I(G), I(I(G)), \dots\) until the graph stops changing (the limit). An edge inside one interval, in particular a self loop, is not an edge of \(I(G)\); a self loop does keep its node out of its predecessor's interval, which is why \(I(G)\) can have as many nodes as \(G\) and still differ from it.
T1/T2 reduction¶
Algorithm 15.6.6 (T1/T2 reduction)
- Input: \(G\).
- Output: reducible?, the limit graph and each limit node's region.
- Precondition: none; unreachable nodes are dropped first.
- Postcondition: the returned graph is the limit graph of Theorem 15.6.3, and reducible iff it has one node.
- Invariant: every node of the current graph stands for a single-entry region of the original whose entry is its representative (Lemma 15.6.10); every node whose predecessor set changed is on the worklist.
function T1T2(G = (N, E, r)):
drop unreachable nodes
members[n] ← {n} for every n
worklist ← all nodes
while worklist not empty:
n ← pop worklist
if n no longer exists: continue
if n → n ∈ E: # T1
remove n → n; push n
continue
if n ≠ r and |preds(n)| = 1: # T2
m ← the predecessor of n
remove m → n
for s in succs(n):
replace n → s by m → s (merging duplicates); push s
members[m] ← members[m] ∪ members[n]
delete n; push m
return (number of nodes = 1, graph, members)
You implement it as isReducibleT1T2(G, &LimitSize) (E15).
Interval derived sequences¶
Algorithm 15.6.7 (Intervals and the derived sequence)
- Input: \(G\).
- Output: the intervals of \(G\), and the derived sequence.
- Precondition: all nodes reachable.
- Postcondition: the intervals partition \(N\) (Definition 15.6.5); the last graph of the sequence has one node iff \(G\) is reducible.
- Invariant: each interval under construction is single-entry: every node added after its header has all its predecessors already inside (Theorem 15.6.12).
function Intervals(G):
headers ← queue [r]; seenHeader ← {r}; assigned ← {}
result ← []
while headers not empty:
h ← pop front of headers
I ← [h]; assigned ← assigned ∪ {h}
repeat
for n in N, n ≠ r, n ∉ assigned:
if every predecessor of n is in I: append n to I; assigned ← assigned ∪ {n}
until no node was added in the last scan
for n in N, n ∉ assigned, n ∉ seenHeader:
if some predecessor of n is in I: enqueue n in headers; seenHeader ← seenHeader ∪ {n}
append (h, I) to result
return result
function DerivedSequence(G):
sequence ← [G]
loop
ivs ← Intervals(G)
G′ ← one node per interval (named by its header); an edge h₁ → h₂ whenever an edge of G
goes from interval h₁ to the header h₂ of another interval
if G′ = G (same nodes and edges): return sequence # the limit
# (compare edges too: a first step can keep every node and only drop self loops)
append G′ to sequence; G ← G′
The Python oracles are intervals and derived_sequence in tools/course/lib/cfa.py.
The DFS back-edge test¶
Algorithm 15.6.8 (DFS back-edge test)
- Input: \(G\), a DFS (edge kinds), the dominator tree \(\mathcal{D}\) — or, in LLVM's variant, an RPO traversal and
LoopInfo. - Output: reducible?, and the offending retreating edges.
- Precondition: \(\mathcal{D}\) (or
LoopInfo) is correct for \(G\). - Postcondition: reducible iff no offending edge (Theorem 15.6.4(b)).
- Invariant:
badholds exactly the retreating edges examined so far whose head does not dominate their tail.
function DFSReducible(G, dfs, D):
bad ← []
for each edge u → v with kind[u → v] = retreating:
if not D.dominates(v, u): append u → v to bad
return (bad is empty, bad)
function LLVMContainsIrreducibleCFG(RPO, LoopInfo): # llvm/include/llvm/Analysis/CFG.h
visited ← {}
for n in RPO:
visited ← visited ∪ {n}
for s in succs(n):
if s ∈ visited: # an edge to an earlier RPO node
if no loop containing n (walking out from LoopInfo.getLoopFor(n))
has header s:
return true # a retreating edge that is not a loop back edge
return false
The course's Python oracle is_reducible in tools/course/lib/cfg.py uses characterization (c).
Node splitting¶
Algorithm 15.6.9 (Node splitting)
- Input: \(G\).
- Output: an equivalent reducible \(G'\) (the same executable paths, with some nodes copied).
- Precondition: the entry region is never split.
- Postcondition: \(G'\) is reducible and every path of \(G\) corresponds to exactly one path of \(G'\) with the same sequence of original blocks (Theorem 15.6.14).
- Invariant: each round preserves the paths up to renaming copies and strictly reduces the number of nodes of the limit graph (Theorem 15.6.14).
function NodeSplitting(G):
loop
(reducible, L, members) ← T1T2(G)
if reducible: return G
R ← a non-entry node of L with ≥ 2 predecessors,
choosing the one whose region members[R] has the fewest original nodes
for each predecessor P of R in L except the first:
copy every original node of members[R], with its internal edges,
and edges from the copy to the same successors outside the region
redirect every edge from P's region into the region to the copy
Each round removes one multi-entry situation of the limit graph; the copies are fresh nodes (named E′, E″, … in the traces). The Python oracle is node_splitting.
3. Worked examples¶
T1/T2 on both CFGs¶
Running example (reducible). One row per rule application; the graph after the step (nodes named by the representative that absorbed the others):
| step | rule | applied to | graph after the step |
|---|---|---|---|
| 1 | T2 | C into B | A → B; B → E, D, H; E → F, H; D → E; H → I, B; F → G; G → H, E; I |
| 2 | T2 | D into B | A → B; B → E, H; E → F, H; H → I, B; F → G; G → H, E; I |
| 3 | T2 | F into E | A → B; B → E, H; E → H, G; H → I, B; G → H, E; I |
| 4 | T2 | G into E | A → B; B → E, H; E → H, E; H → I, B; I |
| 5 | T1 | E (self loop from step 4) | A → B; B → E, H; E → H; H → I, B; I |
| 6 | T2 | E into B | A → B; B → H; H → I, B; I |
| 7 | T2 | H into B | A → B; B → I, B; I |
| 8 | T1 | B | A → B; B → I; I |
| 9 | T2 | B into A | A → I; I |
| 10 | T2 | I into A | A |
One node: reducible. Each T1 marks where a loop collapsed onto its header (E at step 5, B at step 8).
Irreducible variant (with D → F):
| step | rule | applied to | graph after the step |
|---|---|---|---|
| 1 | T2 | C into B | A → B; B → E, D, H; E → F, H; D → E, F; H → I, B; F → G; G → H, E; I |
| 2 | T2 | D into B | A → B; B → E, H, F; E → F, H; H → I, B; F → G; G → H, E; I |
| 3 | T2 | G into F | A → B; B → E, H, F; E → F, H; H → I, B; F → H, E; I |
| 4 | T2 | I into H | A → B; B → E, H, F; E → F, H; H → B; F → H, E |
Now E has predecessors B and F, F has B and E, H has B, E and F, and B has A and H: no rule applies. The limit graph has 5 nodes, regions A = {A}, B = {B, C, D}, E = {E}, F = {F, G}, H = {H, I}: irreducible. The two-entry cycle E ⇄ F is the core, and it also blocks the outer loop from collapsing.
Try it
./course drill natural-loops --seed 5 --difficulty hard --solution shows the T1/T2 table and the derived-sequence sizes for a random, possibly irreducible, CFG.
Interval derived sequences on both CFGs¶
| CFG | intervals of G (header: members in order added) | I(G) | I(I(G)) | I³(G) | verdict |
|---|---|---|---|---|---|
| running example | A: A; B: B C D; E: E F G; H: H I | A → B; B → E, H; E → H; H → B | A → B (B's back edge is now internal) | A | reducible (9 → 4 → 2 → 1) |
| irreducible variant | A: A; B: B C D; E: E; H: H I; F: F G | A → B; B → E, H, F; E → F, H; H → B; F → H, E | the same 5 nodes: no interval grows | — | irreducible (9 → 5, limit 5) |
In the irreducible variant, E cannot join B's interval (its predecessor G is outside) and neither can F (its predecessor E is outside): each becomes its own header, and in the derived graph they remain two headers that enter each other.
The DFS back-edge test on both CFGs¶
| CFG | retreating edges (course DFS) | head dominates tail? | verdict |
|---|---|---|---|
| running example | H → B, G → E | B dom H: yes; E dom G: yes | reducible |
| irreducible variant | H → B, G → E | B dom H: yes; E dom G: no (A B C D F G avoids E) | irreducible; offending edge G → E |
containsIrreducibleCFG reaches the same conclusion: in RPO A B C D E F G H I, the edges to earlier nodes are G → E and H → B; LoopInfo has a loop with header B containing H, but no loop with header E (E is not a natural-loop header in the variant).
Node splitting on the irreducible variant¶
| round | limit graph (from T1/T2) | node split | predecessor regions | copies made | result |
|---|---|---|---|---|---|
| 1 | 5 nodes (above) | E (region {E}, the smallest with ≥ 2 predecessors) | B = {B, C, D} keeps E; F = {F, G} gets a copy | E′ with E′ → F, H | G → E′ instead of G → E |
| 2 | T1/T2 now reduces to one node | — | — | — | reducible |
The split CFG: A → B; B → C, E; C → D, H; D → E, F; E → F, H; F → G; G → H, E′; E′ → F, H; H → I, B; I. The cycle is now F → G → E′ → F, entered only at F: a natural loop with header F. The price is one duplicated block.
4. Invariants and correctness¶
T1/T2 reduction¶
Lemma 15.6.10 (T1/T2 keeps single-entry regions)
At every point of Algorithm 15.6.6, each node \(x\) of the current graph stands for a region whose only entry (Definition 15.5.6) is \(x\)'s representative, and every edge between current nodes corresponds to an edge of \(G\) from the source region into the target's representative.
Proof
By induction on the rule applications. Initially every region is a single node. T1 removes an edge from a region's representative to itself: it only drops a cycle that lies inside one region, entered at its representative. T2 merges \(n\) into its unique predecessor \(m\): every edge into \(n\)'s region came from \(m\)'s region, so the union is entered only through \(m\)'s representative, and the edges out of the union are those out of the two regions.
Theorem 15.6.11 (Correctness of Algorithm 15.6.6)
Algorithm 15.6.6 terminates, returns the limit graph of Theorem 15.6.3, and reports reducible iff \(G\) is reducible.
Proof sketch (full proof: [HU72, §3])
Termination: T1 removes an edge, T2 removes a node. Limit: the worklist holds every node whose predecessor set or self-loop status changed, so when it is empty no rule applies anywhere; by Theorem 15.6.3 the order of applications is irrelevant. Verdict: this is Definition 15.6.2 applied to that limit; Theorem 15.6.4 connects it to the dominance characterizations (b)–(d).
When it breaks: forgetting to drop unreachable nodes (they block T2 on their successors); treating the entry as T2-mergeable.
Interval derived sequences¶
Theorem 15.6.12 (Intervals decide reducibility)
Each interval is a single-entry region whose cycles pass through its header, the derived sequence terminates, and its limit has one node iff \(G\) is reducible.
Proof sketch (full proof: [All70]; [HU74, §3])
Single entry: a node is added only when all its predecessors are inside, so edges from outside enter only at the header. Termination: each step either removes a node or, at most once (derived graphs have no self loops), keeps the nodes and drops self loops. Verdict: collapsing an interval (a single-entry region whose cycles all pass through its header) neither creates nor removes a cycle without a dominating node, so characterization (d) of Theorem 15.6.4 is invariant along the sequence [HU74, §3]. A one-node limit is reducible. In a limit with more than one node every interval is a single node, so no non-entry node has all its predecessors in one other node's interval, i.e. no T2 applies, and after removing self loops (T1) the limit is also a T1/T2 limit with more than one node: irreducible by Definition 15.6.2 and Theorem 15.6.3.
When it breaks: intervals are not loops: an interval also contains the acyclic tail after a loop (B's interval includes C and D above).
The DFS back-edge test¶
Theorem 15.6.13 (Correctness of Algorithm 15.6.8)
DFSReducible returns true iff \(G\) is reducible, and every edge it reports is a retreating edge that is not a dominance back edge; LLVMContainsIrreducibleCFG returns true iff \(G\) is irreducible.
Proof
The first function checks characterization (b) of Theorem 15.6.4 edge by edge. For LLVM's variant: an edge to an earlier RPO node is exactly a retreating edge of the DFS that produced the RPO; it is a dominance back edge iff its target is the header of a natural loop containing its source (Definition 15.5.4 and Theorem 15.5.5), which is what the walk over getLoopFor(n) and its parents checks. So it returns true iff (b) fails. Termination: one scan of the edges.
Node splitting¶
Theorem 15.6.14 (Correctness of node splitting)
Algorithm 15.6.9 terminates with a reducible graph whose paths correspond one-to-one to those of \(G\).
Proof sketch (full proof: [Hec77]; controlled variant: [JC97])
Paths: a copy of a region receives exactly the edges from one predecessor region and has the same outgoing edges, so every path of the old graph maps to exactly one path of the new graph, and back, by renaming copies to originals. Progress: let \(L\) be the limit graph before the round. By Lemma 15.6.10, edges between regions enter only representatives, which the old reduction never merged, and the copies add edges only into representatives; so the old sequence of T1/T2 applications still applies inside every region and inside every copy. It leaves \(L\) with \(R\) replaced by \(R\) and its copies, each of which now has a single predecessor node (its \(P\)), no self loop and is not the entry: one more T2 each absorbs them. So the new limit graph has at most \(\lvert L \rvert - 1\) nodes, and the procedure stops after at most \(\lvert L \rvert - 1\) rounds, though the copies can make the graph exponentially large (Proposition 15.6.15).
When it breaks: splitting a region that contains the entry; splitting when phi nodes exist without updating them (the copies' phis must drop the incoming values from the other predecessors).
5. Complexity¶
\(n\) = nodes, \(m\) = edges, \(k\) = loop nesting depth.
| Technique | Time (worst) | Time (typical) | Space | Notes |
|---|---|---|---|---|
| T1/T2 (worklist, E15) | \(O(n \cdot m)\) with sorted sets, near-linear with union-find [Tar74] | linear | \(O(n + m)\) | limit graph shows the irreducible core |
| Interval derived sequence | \(O(k \cdot (n + m))\) | linear per round, few rounds | \(O(n + m)\) | rounds ≈ loop depth + 1 |
| DFS back-edge test | \(O(n + m)\) given \(O(1)\) dominance queries | linear | \(O(n)\) | LLVM's version walks loop parents: \(O(m \cdot k)\) |
| Node splitting | exponential in \(n\) worst case [CFT03] | a few copies | output size | controlled splitting minimizes copies [JC97] |
Proposition 15.6.15 (Costs, and the exponential blow-up of splitting)
(a) Algorithm 15.6.6 performs at most \(n\) T2s and \(m\) T1s; with std::set adjacency each T2 costs \(O(m \log n)\) in the worst case, \(O(n \cdot m \log n)\) overall. (b) Algorithm 15.6.8 costs \(O(n + m)\) given \(O(1)\) dominance queries (Corollary 15.1.7). (c) There are irreducible CFGs with \(k\) nodes whose every reducible equivalent obtained by splitting has \(\Omega(2^{k})\) nodes.
Proof ((a), (b) in full; (c): proof sketch, full proof: [CFT03])
(a) T2 deletes a node and T1 an edge, and neither rule creates nodes or edges beyond moving \(n\)'s successor edges to \(m\) (merging duplicates); moving at most \(m\) edges with ordered-set insertions costs \(O(m \log n)\) per T2. (b) One scan of the edges with an \(O(1)\) query each. (c) Take the complete graph on \(k\) mutually reachable nodes, each also reachable directly from the entry: every node is an entry of the cycle. A reducible equivalent must, for each order in which the \(k\) nodes can be first visited, keep a separate copy of the code reached after that prefix, and Carter, Ferrante and Thomborson show that \(\Omega(2^{k})\) distinct nodes are needed.
Pathological input: for T1/T2 without a worklist (rescan all nodes after every change), a chain of \(n\) nodes costs \(\Theta(n^2)\) rescans; the worklist version in E15 visits each node a constant number of times per change of its predecessors. For node splitting, the family of (c).
At scale: irreducible CFGs are rare in ordinary code. On the course's reference container, compiling every C file that builds stand-alone (194 files: Go's cgo runtime, bison's skeletons, mypyc's runtime, X11 transport code, and this chapter's tests) with clang -O0 -Xclang -disable-O0-optnone and running print<pebble-reducibility> gives 400 functions, of which exactly 4 are irreducible, and all 4 are the ones written deliberately for tests/ch15 (Duff's device, two gotos into loops, a goto state machine). The measurement takes a minute to repeat with the commands in labs/ch15-dominance/SPEC.md.
6. Variants and refinements¶
T1/T2 reduction¶
- Ullman's fast reducibility check / Tarjan's union-find test [Tar74] — trade-off: almost-linear time, but gives only the verdict, not the limit graph.
- Structural analysis (Sharir; [Muchnick §7.7]) generalizes T1/T2 to a catalogue of region shapes (if-then, if-then-else, while, proper, improper) — trade-off: richer structure for elimination dataflow and decompilation, more rules.
Interval derived sequences¶
- Allen–Cocke interval dataflow [AC76] — trade-off: solves dataflow problems by elimination over the derived sequence, fails on irreducible graphs.
- Graham–Wegman "T1/T2 dataflow" — trade-off: same elimination idea on T1/T2 regions instead of intervals.
The DFS back-edge test¶
- Dominance-based (the course oracle
is_reducible) vsLoopInfo-based (LLVM) — trade-off: the first needs dominators only; the second reuses LoopInfo when it exists. - Tarjan's test without dominators [Tar74] (Lesson 15.5) — trade-off: no dominators needed, returns the loop forest as a bonus.
Node splitting¶
- Controlled node splitting [JC97]: choose split nodes to minimize the number of copies — trade-off: search cost at compile time for smaller code.
- Dispatch (guard) blocks instead of copies: LLVM's
FixIrreducibleroutes all entries through a new header that branches on which entry was meant; the WebAssembly back end does the same with a label variable ("we … do not duplicate code") — trade-off: no code growth, but an extra branch and a helper variable on every entry. - DJ-graph-based handling [UM02 compares]: analyze irreducible loops directly instead of transforming them — trade-off: no transformation at all, but every client analysis must understand irreducible loops.
7. In real compilers¶
T1/T2 reduction¶
- No production compiler runs T1/T2 as a pass; it is the verification oracle in this course (your
isReducibleT1T2,print<pebble-reducibility>) and a textbook definition. Compilers use the DFS test or loop analyses instead because they already have dominators or loops. The box below therefore runs the course's reference implementation next to LLVM's CycleInfo.
T1/T2 limit graphs next to LLVM's cycles
Reproduce (clang 23.1.2, opt 23.1.2, and the course's PebblePasses plugin built from the reference solution by ./course test 15 --solution; run from the repository root):
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
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 goto.c -o goto.ll
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm running.c -o running.ll
# Built by ./course test 15 --solution. The preset is ci-solutions-macos on macOS
# (the plugin is then PebblePasses.dylib).
P=$(ls build/ci-solutions-*/lib/PebblePasses.{so,dylib} 2>/dev/null | head -1)
for f in goto running; do
opt -load-pass-plugin=$P -passes='sroa,simplifycfg,print<pebble-reducibility>,print<cycles>' \
-disable-output $f.ll
done
Output (complete):
Pebble reducibility for function 'g': irreducible (T1/T2 limit graph has 3 nodes)
CycleInfo for function: g
depth=1: entries(while.cond inside) while.body
Pebble reducibility for function 'running': reducible (T1/T2 limit graph has 1 node)
CycleInfo for function: running
depth=1: entries(B) H C E F D
depth=2: entries(E) F
What to notice: on goto.c T1/T2 gets stuck at 3 nodes (Theorem 15.6.11): the entry region, and the two entries of the irreducible cycle, which CycleInfo lists as entries(while.cond inside); while.body has a unique predecessor and was merged by T2. On the running example everything collapses to 1 node and CycleInfo's cycles all have a single entry: Theorem 15.6.4, (a) and (d), seen from two independent implementations.
Interval derived sequences¶
- Historical: the IBM FORTRAN compilers and PL/I optimizer of the 1970s used interval analysis [AC76]. Modern LLVM and GCC solve dataflow iteratively (Ch 14) and do not build intervals; interval-like single-entry regions survive in LLVM's
RegionInfo(llvm/lib/Analysis/RegionInfo.cpp, SESE regions for Polly) [LLVM-RegionInfo].
Nested single-entry regions: RegionInfo
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
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
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm scale.c -o scale.ll
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm goto.c -o goto.ll
for f in scale goto; do opt -passes='sroa,print<regions>' -disable-output $f.ll; done
Output (complete):
Region Tree for function: scale
Region tree:
[0] entry => <Function Return>
[1] for.cond => for.end7
[2] for.cond1 => for.end
End region tree
Region Tree for function: g
Region tree:
[0] entry => <Function Return>
[1] entry => while.end
End region tree
What to notice: on the reducible loop nest, RegionInfo finds nested single-entry single-exit regions for the outer loop (for.cond => for.end7) and the inner one (for.cond1 => for.end): the nested structure the derived sequence collapses step by step (Definition 15.6.5; SESE regions also require a single exit, which intervals do not). On goto.c no region isolates the loop: its two entries mean the smallest single-entry region around the cycle starts at entry itself, just as the derived sequence of an irreducible graph gets stuck.
The DFS back-edge test¶
LLVM
llvm/include/llvm/Analysis/CFG.h — containsIrreducibleCFG<NodeT>(RPOTraversal, LoopInfo): walks blocks in RPO and returns true on the first edge to an already visited block that is not a back edge of a loop containing the source (the isProperBackedge lambda). Used by llvm/lib/Analysis/MustExecute.cpp (LLVM 23.1.2) [LLVM-CFG].
- Go 1.25
likelyadjust.go—loopnestforsetssawIrredwhen a retreating edge's target does not dominate its source, and branch-likelihood heuristics then back off [Go-Loopnest]. - Pebble
pebble-verify-cfacompares your T1/T2 verdict withcontainsIrreducibleCFGon every function it sees.
A retreating edge whose head does not dominate its tail
Reproduce (clang 23.1.2, opt 23.1.2; running_irr.c is the running example plus D → F, from Lesson 15.5, section 7):
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<domtree>,print<loops>' -disable-output running_irr.ll
Output (complete):
DominatorTree for function: running_irr
=============================--------------------------------
Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries.
[1] %entry {4294967295,4294967295} [0]
[2] %B {4294967295,4294967295} [1]
[3] %C {4294967295,4294967295} [2]
[4] %D {4294967295,4294967295} [3]
[3] %E {4294967295,4294967295} [2]
[3] %F {4294967295,4294967295} [2]
[3] %H {4294967295,4294967295} [2]
[4] %I {4294967295,4294967295} [3]
Roots: %entry
Loop info for function 'running_irr':
Loop at depth 1 containing: %B<header>,%C,%D,%E,%F,%H<latch><exiting>
What to notice: a DFS from entry that follows successors in order visits B, C, D, E, F, so F → E is a retreating edge. But the tree shows \(\mathrm{idom}(F) = B\): E does not dominate F (the path through D → F avoids E). Characterization (b) of Theorem 15.6.4 fails, so the CFG is irreducible, and LoopInfo — which only accepts dominance back edges — reports the B loop alone. containsIrreducibleCFG reaches the same verdict from exactly these two facts: an RPO edge F → E whose target heads no loop containing F.
Node splitting¶
LLVM
llvm/lib/Transforms/Utils/FixIrreducible.cpp — fixIrreducible(Cycle &C, CycleInfo &CI, …): turns each irreducible CycleInfo cycle into a natural loop with a new header, using ControlFlowHub guard blocks rather than duplication [LLVM-FixIrr]; llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp adds a dispatch block with a label helper variable (LLVM 23.1.2).
- Research and GPU structurizers use node splitting when a structured output is mandatory and code growth is acceptable; Unger and Mueller compare optimized node splitting with DJ-graph-based approaches [UM02].
fix-irreducible: a guard block instead of copies
Reproduce (clang 23.1.2, opt 23.1.2):
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
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm goto.c -o goto.ll
opt -passes='sroa,fix-irreducible,print<cycles>,print<loops>' -disable-output goto.ll
opt -passes='sroa,fix-irreducible' -S goto.ll | grep -E '^[a-z.]+:|^ br|Guard'
Output (complete, the IR filtered by the grep):
CycleInfo for function: g
depth=1: entries(irr.guard) while.cond inside while.body
Loop info for function 'g':
Parallel Loop at depth 1 containing: %irr.guard<header>,%while.cond<exiting>,%while.body,%inside<latch>
entry:
br i1 %tobool, label %if.then, label %if.end
if.then: ; preds = %entry
br label %irr.guard
if.end: ; preds = %entry
br label %irr.guard
while.cond: ; preds = %irr.guard
br i1 %cmp, label %while.body, label %while.end
while.body: ; preds = %while.cond
br label %inside
inside: ; preds = %irr.guard, %while.body
br label %irr.guard, !llvm.loop !5
while.end: ; preds = %while.cond
irr.guard: ; preds = %if.then, %if.end, %inside
%Guard.while.cond = phi i1 [ true, %inside ], [ true, %if.end ], [ false, %if.then ]
br i1 %Guard.while.cond, label %while.cond, label %inside
What to notice: both entries of the cycle (from if.end into while.cond, from if.then into inside) now go to a new block irr.guard, which branches on the phi %Guard.while.cond recording which entry was meant. The cycle has one entry, irr.guard dominates it, and LoopInfo now reports a natural loop with that header. Node splitting (Algorithm 15.6.9) would instead have copied inside (or while.cond) for one of the entries: no extra branch, but duplicated code — and exponentially much in the worst case (Proposition 15.6.15).
Find where LLVM does it. Open llvm/include/llvm/Analysis/CFG.h (LLVM 23.1.2) and read containsIrreducibleCFG. Question: which LLVM analysis result does it take besides the RPO traversal? (Quiz reducibility-facts, statement (e), checks the answer; the flashcards tagged reducibility-dfs ask it directly.)
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| T1/T2 | exact verdict | O(n·m) naive, near-linear with care | limit graph shows the irreducible core | ~40 lines | textbooks, verification |
| Interval derived sequence | exact verdict + intervals | O(n·m) | nested intervals (Allen–Cocke analysis) | ~60 lines | interval dataflow analysis (Ch 14) |
| DFS back-edge test | exact verdict | O(n + m) after dominators | the offending retreating edges | ~10 lines | LLVM containsIrreducibleCFG |
| Node splitting | makes any CFG reducible | exponential code growth worst case | an equivalent reducible CFG | ~80 lines | GPU back ends, structurizers; LLVM uses guard blocks instead (fix-irreducible) |
Choose T1/T2 when you want a definition-level oracle or the irreducible core (the limit graph) for diagnostics. Choose intervals when you run elimination-based dataflow or need the nested single-entry regions themselves. Choose the DFS test when dominators or loops are already available: it is the cheapest and names the offending edges. Choose node splitting when a consumer requires reducible input and code growth is acceptable; otherwise prefer a dispatch block.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch15.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| T1/T2 | t1t2-limit, reducibility-facts |
./course drill natural-loops --difficulty hard --solution |
t1-t2 |
E15 |
| Intervals | derived-sequence, reducibility-facts |
./course drill natural-loops --difficulty hard --solution (derived-sequence sizes) |
intervals |
— (oracle only) |
| DFS back-edge test | dfs-edge-kinds, reducibility-facts |
./course drill natural-loops --difficulty hard (the reducible: line) |
reducibility-dfs |
— (compared with LLVM in E15's tests) |
| Node splitting | node-splitting-copies, reducibility-facts |
./course drill natural-loops --difficulty hard --solution shows the Havlak/Steensgaard view; splitting is traced in this lesson |
node-splitting |
— (oracle only) |
Irreducible means a cycle with two entries
"Irreducible" does not mean "has a loop LoopInfo does not report" in a vague sense: it means some cycle has two entries. A CFG full of gotos can still be reducible, and a single goto into a loop body is enough to make it irreducible.
References¶
See the chapter references.