Lesson 14.5 — Elimination methods: intervals, structural analysis, path expressions¶

Techniques: Allen–Cocke interval analysis; Sharir's structural analysis; Tarjan's path expressions · Pebble implements: none (theory and drills; the iterative solvers of Lesson 14.4 are what Pebble uses) · Lab: — · Prerequisites: Lesson 14.2, Lesson 14.4, reducibility (Ch 15, Lesson 15.6) · Time: 4–6 hours

Iterative solvers go around every loop until nothing changes. Elimination methods instead solve each loop once, in closed form: they summarize the loop body as a transfer function \(g\), compute the effect of "any number of trips around the loop" as a closure \(g^{*}\), and substitute it — exactly as Gaussian elimination solves a linear system without iterating. For reaching definitions on the running example, the loop body summarizes to the gen/kill pair \(g = (\{d_4, \dots, d_8\}, \{d_2\})\); its closure is \(g^{*}(x) = x \cup \{d_4, \dots, d_8\}\), and one application to the loop's entry value \(\{d_1, d_2, d_3\}\) gives the header's final value \(\{d_1, \dots, d_8\}\) with no iteration at all.

1. Problem and motivation¶

Iterative algorithms were slow on 1970s machines when loops nested deeply, and their cost depended on the visiting order in ways nobody could bound before Kam and Ullman [KU76]. Elimination methods promised guaranteed, nearly linear cost on the structured (reducible) CFGs that structured languages produce. They need more of the framework than iteration: the transfer functions must form an algebra closed under composition, join and a closure operation, which holds for bit-vector problems. Today production compilers use iteration (Lesson 14.4 explains why: \(d(G) + 2\) passes are enough in practice, and iteration handles any CFG and any monotone framework), but the elimination ideas live on in three places: loop-summarizing analyses such as LLVM's scalar evolution, region-based analysis in the Dragon book and GPU compilers [Dragon2, §9.7], and incremental analysis, where a changed region is re-summarized locally. Pebble does not implement them; this lesson gives the theory, and the drills practice the function algebra they rest on.

Allen–Cocke interval analysis¶

Allen partitioned a CFG into intervals — single-entry regions headed by a loop header [All70] — and Allen and Cocke turned the partition into a data-flow procedure: summarize each interval, collapse it to a node, repeat on the derived graph until one node remains, then propagate values back down [AC76]. A graph for which this sequence ends in a single node is reducible — the definition of reducibility used in Ch 15.

Structural analysis¶

Sharir refined intervals into a grammar of control structures — sequence, if-then, if-then-else, while loop, self loop, natural loop, and a catch-all "proper" or "improper" region — each with its own summary rule [Sha80]. Collapsing structures bottom-up yields a control tree that mirrors the source program, which makes the summaries more precise and easier to update after local transformations. Muchnick's textbook presents it as the region-based method of choice [Muchnick, Ch. 7–8].

Tarjan's path expressions¶

Tarjan observed that every path problem is solved by first computing, for each node \(v\), a regular expression \(P(r, v)\) over the edges that denotes exactly the set of paths from the entry \(r\) to \(v\), and then interpreting that expression in the algebra of the problem — union as join, concatenation as composition, star as closure [Tar81a]. For reducible graphs the path expressions can be computed in \(O(e\,\alpha(e, n))\) time from the dominator tree [Tar81b], the best bound known for elimination.

2. Definitions and algorithms¶

Definition 14.5.1 (Function algebra of a framework)

For an elimination method the framework must supply, on its function space \(\mathcal{F}\): the identity \(\mathrm{id}\); composition \(g \circ f\); join \((f \sqcup g)(x) = f(x) \sqcup g(x)\); and a closure \(f^{*} = \bigsqcup_{i \ge 0} f^{i}\) (so \(f^{*}(x)\) is the join of \(x, f(x), f(f(x)), \dots\)), all computable and inside \(\mathcal{F}\). For gen/kill functions written as pairs \((G, K)\) with \((G, K)(X) = G \cup (X \setminus K)\):

\[ \begin{aligned} (G_2, K_2) \circ (G_1, K_1) &= (G_2 \cup (G_1 \setminus K_2),\ K_1 \cup K_2) \\ (G_1, K_1) \sqcup (G_2, K_2) &= (G_1 \cup G_2,\ K_1 \cap K_2) \\ (G, K)^{*} &= (G, \emptyset) \end{aligned} \]

Lemma 14.5.2 (Gen/kill algebra)

The three equations of Definition 14.5.1 hold, and gen/kill functions are idempotent: \(f \circ f = f\).

Proof

Composition: \(G_2 \cup ((G_1 \cup (X \setminus K_1)) \setminus K_2) = G_2 \cup (G_1 \setminus K_2) \cup (X \setminus (K_1 \cup K_2))\). Join: \((G_1 \cup (X \setminus K_1)) \cup (G_2 \cup (X \setminus K_2)) = (G_1 \cup G_2) \cup (X \setminus (K_1 \cap K_2))\). Idempotence: by the composition rule \(f \circ f = (G \cup (G \setminus K), K \cup K) = (G, K)\). Closure: by idempotence \(f^{i} = f\) for \(i \ge 1\), so \(f^{*} = \mathrm{id} \sqcup f\) and \(X \cup G \cup (X \setminus K) = G \cup X\), the pair \((G, \emptyset)\). \(\square\)

Allen–Cocke interval analysis¶

Definition 14.5.3 (Interval, derived graph)

For a node \(h\) of a flowgraph \(G\), the interval \(I(h)\) is the largest set of nodes such that \(h \in I(h)\), and every \(v \in I(h) \setminus \{h\}\) has all its predecessors in \(I(h)\) and is not the target of an edge from outside that enters any cycle avoiding \(h\) — equivalently, the set built by Algorithm 14.5.4. Intervals partition \(N\). The derived graph \(G'\) has one node per interval and an edge \(I \to J\) when some edge leads from a node of \(I\) to the header of \(J\). \(G\) is reducible if the derived sequence \(G, G', G'', \dots\) ends in a single node.

Algorithm 14.5.4 (Interval partition, Allen–Cocke)

Input: a flowgraph \(G = (N, E, r)\), every node reachable.
Output: the intervals of \(G\) and their headers, each interval's nodes in an order where every node comes after its in-interval predecessors (except for edges back to the header).
Precondition: every node is reachable from \(r\).
Postcondition: the intervals partition \(N\); each is single-entry (only its header has predecessors outside it) (Lemma 14.5.5).
Invariant: every node in H is not in any interval yet and has a predecessor in some interval.

function Intervals(G = (N, E, r)):
    H ← [r]                                       # candidate headers
    assigned ← ∅;  result ← []
    while H ≠ []:
        h ← pop front of H
        if h ∈ assigned: continue
        I ← [h];  assigned ← assigned ∪ {h}
        repeat
            grew ← false
            for v in N ∖ assigned:
                if preds(v) ≠ ∅ and preds(v) ⊆ I:      # every predecessor already inside
                    append v to I;  assigned ← assigned ∪ {v};  grew ← true
        until not grew
        for v in N ∖ assigned:
            if some predecessor of v is in I and v ∉ H: append v to H
        append (h, I) to result
    return result

Lemma 14.5.5 (Intervals are single-entry and partition \(N\))

Algorithm 14.5.4 assigns every node to exactly one interval, and every edge entering an interval from outside targets its header.

Proof

Partition: a node is added to an interval at most once (assigned); every node is reachable from \(r\), so by induction on the distance from \(r\) it eventually has a predecessor in some interval and is either absorbed or becomes a header candidate, and candidates are processed until \(H\) is empty. Single entry: a non-header \(v\) is added to \(I\) only when all its predecessors are already in \(I\), so no edge from outside \(I\) reaches \(v\); later intervals cannot add predecessors to \(v\) (edges are fixed). \(\square\)

Algorithm 14.5.6 (Interval elimination for a forward gen/kill problem)

Input: a reducible flowgraph; gen/kill pairs \(f_v\) per node; the entry value \(\iota\).
Output: \(\mathrm{IN}[v]\) for every node.
Precondition: \(G\) reducible; the framework's functions form the algebra of Definition 14.5.1 (gen/kill).
Postcondition: \(\mathrm{IN} = \mathrm{MFP} = \mathrm{MOP}\) (Theorem 14.5.7).
Invariant: after the summary phase at level \(k\), every node of \(G^{(k)}\) carries the function from its header's entry to its own entry, and every derived node carries the function from its header's entry to each of its exits.

function IntervalElimination(G, f, ι):
    # Phase 1 (bottom-up): summarize intervals, level by level
    level ← G
    while level has more than one node:
        for each interval (h, I) of level (Algorithm 14.5.4), nodes in its order:
            F[h] ← id                                    # from h's entry to h's entry
            for v in I ∖ {h}:  F[v] ← ⊔ { f_p ∘ F[p] : p ∈ preds(v) }      # acyclic inside I
            back ← ⊔ { f_p ∘ F[p] : p ∈ I, p → h is an edge }             # around the loop
            loop[h] ← back*                             # Definition 14.5.1 closure
            for v in I:  F[v] ← F[v] ∘ loop[h]           # entry of h, any trips, then to v
            the derived node for I gets, for each exit edge v → w, the function f_v ∘ F[v]
        level ← derived graph of level
    # Phase 2 (top-down): turn summaries into values
    IN[entry of the last node] ← ι
    for each level from the last back to G:
        for each interval (h, I):  for v in I:  IN[v] ← F[v](IN[h])
                                 # IN[h] = join over edges entering I of (edge function)(IN of source)
    return IN

Theorem 14.5.7 (Correctness of interval elimination)

For a reducible flowgraph and a gen/kill framework, Algorithm 14.5.6 computes the MOP solution, which equals MFP.

Proof sketch (full proof: [AC76]; the algebraic view: [Tar81a])

Within an interval without its back edges the graph is acyclic and single-entry, so the join over the finitely many header-to-\(v\) paths of the composed functions is computed exactly by the topological-order pass (distributivity lets composition distribute over the joins, Lemma 14.1.10). Every path from the header back to itself decomposes uniquely into trips around back edges, so the set of all header-to-\(v\) paths is (trips)\(^{*}\) followed by one acyclic path: its join is \(F[v] \circ \mathrm{back}^{*}\). Collapsing an interval preserves the path structure between headers, so induction on the derived sequence (which ends in one node exactly when \(G\) is reducible) yields the join over all entry-to-\(v\) paths: MOP. Distributivity gives MOP = MFP (Theorem 14.2.13).

Structural analysis¶

Definition 14.5.8 (Region schemas and control tree)

A region is a set of nodes with a single entry node, matched by one of the schemas: block (a chain \(v_1 \to \cdots \to v_k\), each with one successor and one predecessor), if-then, if-then-else, self loop (\(v \to v\)), while loop (a header with a body chain back to it and one exit), natural loop (a single-entry cyclic region), proper region (single-entry acyclic, not matched above) and improper region (single-entry, cyclic, irreducible). Reducing a region replaces it by one abstract node; the control tree records the nesting of reductions.

Algorithm 14.5.9 (Structural analysis, Sharir)

Input: a flowgraph and a framework with the algebra of Definition 14.5.1.
Output: the control tree; a transfer function per region; the values at every node.
Precondition: functions closed under \(\circ\), \(\sqcup\), \(^{*}\); for improper regions, an iterative fallback.
Postcondition: the values equal MFP (for distributive frameworks: MOP).
Invariant: every abstract node's function maps its entry value to its exit value(s) exactly as the collapsed subgraph does.

function StructuralAnalysis(G):
    while G has more than one node:
        for v in postorder of a DFS of G:                    # innermost structures first
            R ← the smallest region with entry v matching a schema (acyclic schemas first)
            if R exists:
                f_R ← Summary(schema(R), functions of R's nodes)
                replace R by one node with function f_R;  record R in the control tree
                restart the traversal
    values: walk the control tree top-down, applying each region's internal functions to its entry value

function Summary(schema, fs):
    block v1..vk         : f_vk ∘ ... ∘ f_v1
    if-then (c; t)        : (f_t ∘ f_c) ⊔ f_c                       # exit after then, or after the test
    if-then-else (c; t; e): (f_t ∘ f_c) ⊔ (f_e ∘ f_c)
    self loop v           : f_v ∘ f_v*                            # any number of trips, then the exit
    while (h; body b)     : f_h ∘ (f_b ∘ f_h)*                      # test, (body, test)*, exit on the test
    natural / proper      : join over the region's acyclic paths, with the closure of its back edges
    improper region       : iterate (Lesson 14.4) inside the region

Tarjan's path expressions¶

Definition 14.5.10 (Path expression)

Treat the edges \(E\) as an alphabet. A path expression for \((u, v)\) is a regular expression \(P(u, v)\) over \(E\) whose language is exactly the set of paths (as edge sequences) from \(u\) to \(v\). An interpretation maps each edge \(a = x \to y\) to \(f_x\) (the transfer function of its source) and extends homomorphically: \(\llbracket \emptyset \rrbracket = \bot\), \(\llbracket \varepsilon \rrbracket = \mathrm{id}\), \(\llbracket P \cup Q \rrbracket = \llbracket P \rrbracket \sqcup \llbracket Q \rrbracket\), \(\llbracket P \cdot Q \rrbracket = \llbracket Q \rrbracket \circ \llbracket P \rrbracket\), \(\llbracket P^{*} \rrbracket = \llbracket P \rrbracket^{*}\).

Algorithm 14.5.11 (Single-source path expressions by state elimination)

Input: a flowgraph \(G = (N, E, r)\).
Output: \(P(r, v)\) for every node \(v\).
Precondition: none (any graph; Tarjan's \(O(e\,\alpha(e,n))\) refinement needs reducibility).
Postcondition: \(L(P(r, v))\) = the set of paths from \(r\) to \(v\).
Invariant: after eliminating nodes \(w_1, \dots, w_j\), the label \(R[x, y]\) denotes exactly the paths from \(x\) to \(y\) whose inner nodes are all among \(w_1, \dots, w_j\).

function PathExpressions(G = (N, E, r)):
    for x, y in N: R[x, y] ← ∅
    for a = (x → y) in E: R[x, y] ← R[x, y] ∪ a
    for w in N (any order):                          # eliminate w as an inner node
        loop ← R[w, w]*
        for x in N, y in N with R[x, w] ≠ ∅ and R[w, y] ≠ ∅:
            R[x, y] ← R[x, y] ∪ R[x, w] · loop · R[w, y]
    for v in N:
        P(r, v) ← (ε if v = r else ∅) ∪ R[r, v]         # R[r, r] already contains the cycles through r
    return P

Theorem 14.5.12 (Path expressions solve distributive problems)

If the framework is distributive and has the closure of Definition 14.5.1, then \(\llbracket P(r, v) \rrbracket(\iota) = \mathrm{MOP}(v)\) for every \(v\); for gen/kill problems this equals MFP.

Proof sketch (full proof: [Tar81a])

By induction on the structure of the expression, \(\llbracket P \rrbracket = \bigsqcup_{p \in L(P)} f_p\): union and concatenation by distributivity (composition distributes over joins of functions), star by the definition of closure as the join of all powers. With \(L(P(r, v)) = \mathrm{Paths}(v)\) (the postcondition of Algorithm 14.5.11, by induction on the number of eliminated nodes using the invariant) this is the definition of MOP; Theorem 14.2.13 gives MFP.

3. Worked example¶

The running example (reaching definitions; gen/kill pairs from Lesson 14.3: \(f_A = (\{d_1,d_2,d_3\}, \{d_5,d_8\})\), \(f_B = f_F = (\emptyset, \emptyset)\), \(f_C = (\{d_4\}, \emptyset)\), \(f_D = (\{d_5,d_6\}, \{d_3\})\), \(f_E = (\{d_7,d_8\}, \{d_2\})\); edges \(a_1{:}\,A{\to}B\), \(a_2{:}\,B{\to}C\), \(a_3{:}\,B{\to}F\), \(a_4{:}\,C{\to}D\), \(a_5{:}\,C{\to}E\), \(a_6{:}\,D{\to}E\), \(a_7{:}\,E{\to}B\)).

flowchart TD
  A([A]) -->|a1| B[B]
  B -->|a2| C[C]
  B -->|a3| F[F]
  C -->|a4| D[D]
  C -->|a5| E[E]
  D -->|a6| E
  E -->|a7| B

Allen–Cocke interval analysis on the running example¶

Algorithm 14.5.4:

step	header	absorbed (all preds inside)	new header candidates	\(H\) after
1	A	— (B has predecessor E outside)	B	[B]
2	B	C (pred B), F (pred B), D (pred C), E (preds C, D)	—	[]

Intervals \(I(A) = \{A\}\), \(I(B) = \{B, C, F, D, E\}\). Derived graph \(G'\): \(I(A) \to I(B)\), two nodes; its only interval is \(\{I(A), I(B)\}\), so \(G''\) has one node: reducible, derived sequence of length 2.

Phase 1 inside \(I(B)\), functions from B's entry (with \(\mathrm{id} = (\emptyset, \emptyset)\)), using Lemma 14.5.2:

node	\(F[v]\) (acyclic)	computation
B	\((\emptyset, \emptyset)\)	identity
C	\((\emptyset, \emptyset)\)	\(f_B \circ F[B]\)
F	\((\emptyset, \emptyset)\)	\(f_B \circ F[B]\)
D	\((\{d_4\}, \emptyset)\)	\(f_C \circ F[C]\)
E	\((\{d_4,d_5,d_6\}, \emptyset)\)	\((f_C \circ F[C]) \sqcup (f_D \circ F[D]) = (\{d_4\}, \emptyset) \sqcup (\{d_5, d_6\} \cup (\{d_4\} \setminus \{d_3\}), \{d_3\})\)

Back edge: \(\mathrm{back} = f_E \circ F[E] = (\{d_7,d_8\} \cup (\{d_4,d_5,d_6\} \setminus \{d_2\}), \{d_2\}) = (\{d_4, \dots, d_8\}, \{d_2\})\); closure \(\mathrm{loop}[B] = (\{d_4, \dots, d_8\}, \emptyset)\). Each \(F[v]\) is composed with \(\mathrm{loop}[B]\); e.g. \(F[D] \circ \mathrm{loop}[B] = (\{d_4\} \cup \{d_4..d_8\}, \emptyset)\).

Phase 2: \(\mathrm{IN}[A] = \emptyset\), \(\mathrm{OUT}[A] = f_A(\emptyset) = \{d_1, d_2, d_3\}\), so B's entry value is \(\{d_1, d_2, d_3\}\) and \(\mathrm{IN}[B] = \mathrm{loop}[B](\{d_1,d_2,d_3\}) = \{d_1, \dots, d_8\}\); then \(\mathrm{IN}[v] = F[v](\mathrm{IN}[B]) = \{d_1, \dots, d_8\}\) for C, D, E, F — the values of Lesson 14.3's table, with no iteration: every function was evaluated once.

Structural analysis on the running example¶

Postorder of a DFS: E, D, C, F, B, A (successors in listed order: from B first C then F).

step	region found	schema	summary function
1	\(\{C, D, E\}\) with entry C	if-then (test C, then D, join at E) followed by E: a proper acyclic region	\(f_{CDE} = f_E \circ ((f_D \circ f_C) \sqcup f_C) = (\{d_4..d_8\}, \{d_2\})\)
2	\(\{B, CDE\}\)	while loop (header B, body CDE, exit to F)	\(f_W = f_B \circ (f_{CDE} \circ f_B)^{*} = (\{d_4..d_8\}, \emptyset)\)
3	\(\{A, W, F\}\)	block	\(f_F \circ f_W \circ f_A = (\{d_4..d_8\} \cup \{d_1, d_2, d_3\},\ \{d_5, d_8\}) = (\{d_1, \dots, d_8\}, \{d_5, d_8\})\)

The control tree is block(A, while(B, proper(C, D, E)), F) — the shape of the C source. Walking it top-down gives the same values as interval analysis.

Tarjan's path expressions on the running example¶

Algorithm 14.5.11 eliminating D, C, E, F (inner nodes), then B:

Eliminate D: \(R[C, E] \gets a_5 \cup a_4 a_6\).
Eliminate C: \(R[B, E] \gets a_2 (a_5 \cup a_4 a_6)\); \(R[B, D] \gets a_2 a_4\).
Eliminate E: \(R[B, B] \gets a_2 (a_5 \cup a_4 a_6) a_7\); also \(R[C, B], R[D, B]\).
Eliminate B: \(R[A, B] \gets a_1 (a_2 (a_5 \cup a_4 a_6) a_7)^{*}\), and \(R[A, F] \gets a_1 (a_2 (a_5 \cup a_4 a_6) a_7)^{*} a_3\).

Interpreting \(P(A, B) = a_1 \cdot (a_2 (a_5 \cup a_4 a_6) a_7)^{*}\): the star's body is \(f_E \circ ((f_C) \sqcup (f_D \circ f_C)) \circ f_B = (\{d_4..d_8\}, \{d_2\})\), its closure \((\{d_4..d_8\}, \emptyset)\), and after \(a_1\) (\(f_A\)): \(\llbracket P(A, B) \rrbracket(\emptyset) = \{d_4..d_8\} \cup \{d_1, d_2, d_3\} = \{d_1, \dots, d_8\}\) — the same answer a third way.

Try it

Elimination methods rest on the gen/kill algebra: ./course drill dataflow-table --seed 11 --difficulty hard --solution prints gen/kill sets; compose them by hand around each loop and check the IN of the loop head against the drill's answer. ./course drill lattice-props practices distributivity, the property every step above uses.

4. Invariants and correctness¶

Allen–Cocke interval analysis¶

Lemma 14.5.5 (single entry) and Theorem 14.5.7. When it breaks: on an irreducible graph the derived sequence stops at a graph with more than one node in which no interval absorbs anything (the smallest example: \(r \to a\), \(r \to b\), \(a \leftrightarrow b\)); the algorithm then needs node splitting (exponential in the worst case) or a fallback to iteration.

Structural analysis¶

The invariant of Algorithm 14.5.9 — each abstract node's function equals its subgraph's path join — is maintained schema by schema, by the same path-decomposition argument as Theorem 14.5.7. When it breaks: improper regions have no closed-form summary; Sharir's method iterates inside them, and a non-distributive framework makes the schema summaries (which join before composing) less precise than MFP on the original graph would be — for example constant propagation through an if-then-else summary loses the per-branch constants.

Tarjan's path expressions¶

Theorem 14.5.12; the invariant of Algorithm 14.5.11 is the Kleene/McNaughton–Yamada invariant for regular expressions of automata (induction on eliminated nodes). When it breaks: the closure must exist and be computable — for constant propagation \(f^{*}\) is a join of infinitely many functions and has no finite representation in general, and for the interval domain the closure of \(x \mapsto x + 1\) is exactly the widening problem of Lesson 14.7.

5. Complexity¶

Let \(n\) = nodes, \(e\) = edges, \(\ell\) = length of the derived sequence (≈ loop nesting depth + 1 on structured code), \(c\) = cost of one operation in the function algebra (\(O(k / w)\) for gen/kill pairs of \(k\) facts).

Technique	Time (worst)	Time (typical)	Space	Variables
Allen–Cocke intervals	\(O(\ell \cdot (n + e) \cdot c)\), \(\ell \le n\)	\(\ell \le 4\): near-linear	\(O(n + e)\) functions	\(n, e, \ell, c\)
Structural analysis	\(O(n \cdot e \cdot c)\) with restart-after-reduction; improper regions iterate	near-linear on structured code	control tree \(O(n)\)	\(n, e, c\)
Path expressions (state elimination, Algorithm 14.5.11)	\(O(n^3)\) expression operations	—	\(O(n^2)\) expressions	\(n\)
Path expressions (Tarjan, reducible)	\(O(e\,\alpha(e, n) \cdot c)\) [Tar81b]	—	\(O(e)\)	\(e, n\), \(\alpha\) = inverse Ackermann

Proposition 14.5.13 (Cost of interval elimination)

Algorithm 14.5.6 performs \(O(\ell \cdot (n + e))\) function-algebra operations.

Proof

Each level of the derived sequence partitions its nodes into intervals (Algorithm 14.5.4 with a predecessor counter per node instead of the repeat scan touches each node and edge a constant number of times) and computes one composition and one join per edge plus one closure and one composition per node; levels shrink, so each has at most \(n\) nodes and \(e\) edges. Phase 2 applies each stored function once per level. With \(\ell\) levels the total is \(O(\ell (n + e))\). \(\square\)

Pathological input. \(k\) perfectly nested while loops, each loop body being the next loop: the derived sequence has length \(\ell = k + 1\) (each level peels one loop), so interval analysis costs \(\Theta(k \cdot (n + e))\) — the same order as round-robin's \(d + 2 = k + 2\) passes, because \(d = k\) on this family. State elimination on the complete graph \(K_n\) builds expressions of size exponential in \(n\) unless shared as DAGs; Tarjan's algorithm avoids this on reducible graphs.

At scale: Cooper, Harvey and Kennedy measured the iterative algorithm's variants on real programs and found that a well-implemented worklist solver converges in a few visits per node on reducible and irreducible graphs alike [CHK04]; with iteration that cheap and that general, the asymptotic advantage of elimination rarely pays for its implementation effort — the reason production compilers iterate. (Their report measures iterative solvers only; it does not benchmark an elimination method.)

Allen–Cocke interval analysis¶

Graham–Wegman [GW76]: an \(O(e \log e)\) elimination algorithm for a broad class of frameworks on reducible graphs — trade-off: better bound, more complex reductions.
Node splitting [RP86]: duplicate nodes to make an irreducible graph reducible — trade-off: exponential code growth in the worst case (Ch 15, Lesson 15.6).

Structural analysis¶

Region-based analysis on natural loops [Dragon2, §9.7]: only two region kinds (body and loop) derived from the loop nesting forest — trade-off: simpler, works on any reducible CFG, fewer precise schemas.
Incremental re-analysis [Muchnick, Ch. 8]: after a local transformation re-summarize only the enclosing region and re-propagate — trade-off: requires keeping the control tree up to date.

Tarjan's path expressions¶

Kleene algebra with tests / algebraic program analysis [Tar81a]: any problem with a semiring of functions (shortest paths, reachability, dataflow) is one interpretation of the same path expressions — trade-off: generality versus the need for a closure operation.
Newtonian program analysis [EKL10] generalizes Kleene iteration to Newton's method on semirings for interprocedural problems — trade-off: faster convergence, heavier algebra.

7. In real compilers¶

Allen–Cocke interval analysis¶

LLVM

No LLVM or GCC pass solves dataflow by interval elimination today. The interval structure survives as the loop nesting forest: llvm/include/llvm/Analysis/LoopInfo.h (natural loops) and llvm/include/llvm/Analysis/CycleAnalysis.h (cycles, including irreducible ones) (LLVM 23.1.2) [LLVM-LI].

The interval of the running example's loop head in LLVM's loop and cycle analyses

Reproduce (clang 23.1.2, opt 23.1.2; running.c is tests/ch14/Inputs/c/running.c):

cat > running.c <<'EOF'
int running(int a, int b, int n) {
  int x = a * b;
  int i = 0;
  int s = 0;
  while (i < n) {
    int t = a * b;
    if (t < s) {
      s = s + t;
      a = t - 1;
    }
    int u = a * b;
    i = i + 1;
  }
  return s;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm running.c -o - \
  | opt -passes=mem2reg -S -o running.ll
opt -passes='print<loops>,print<cycles>' -disable-output running.ll

Output:

Loop info for function 'running':
Parallel Loop at depth 1 containing: %while.cond<header><exiting>,%while.body,%if.then,%if.end<latch>
CycleInfo for function: running
    depth=1: entries(while.cond) if.end while.body if.then

What to notice: the interval \(I(B)\) of the worked example is headed by %while.cond (B) and contains the loop blocks %while.body (C), %if.then (D), %if.end (E) plus the exit %while.end (F), which interval analysis absorbs because its only predecessor is inside. LoopInfo reports the cyclic part only; CycleInfo reports the same single-entry cycle. On an irreducible CFG, CycleInfo lists several entries(...) — exactly where the derived sequence of Definition 14.5.3 gets stuck.

Structural analysis¶

LLVM

llvm/lib/Analysis/RegionInfo.cpp — single-entry single-exit (SESE) regions, the region structure used by Polly and by structurizing GPU back ends (llvm/lib/Transforms/Scalar/StructurizeCFG.cpp) (LLVM 23.1.2) [LLVM-RI].

SESE regions of the running example: LLVM's RegionInfo

Reproduce (clang 23.1.2, opt 23.1.2; running.ll from the previous box):

cat > running.c <<'EOF'
int running(int a, int b, int n) {
  int x = a * b;
  int i = 0;
  int s = 0;
  while (i < n) {
    int t = a * b;
    if (t < s) {
      s = s + t;
      a = t - 1;
    }
    int u = a * b;
    i = i + 1;
  }
  return s;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm running.c -o - \
  | opt -passes=mem2reg -S -o running.ll
opt -passes='print<regions>' -disable-output running.ll

Output:

Region Tree for function: running
Region tree:
[0] entry => <Function Return>
  [1] while.cond => while.end
    [2] while.body => if.end
End region tree

What to notice: the region tree is the control tree of the worked example: the whole function (block), the while loop from %while.cond to its exit, and inside it the if region from %while.body to the join %if.end. Structural analysis would attach one summary function to each of these nodes (Algorithm 14.5.9).

Tarjan's path expressions¶

LLVM

llvm/lib/Analysis/ScalarEvolution.cpp — ScalarEvolution::createAddRecFromPHI recognizes a loop's recurrence and replaces "any number of trips" by a closed form (an add-recurrence {start,+,step} and its exit value): the closure step of an elimination method, for the lattice of symbolic expressions (LLVM 23.1.2) [LLVM-SCEV].

Solving a loop in closed form: scalar evolution

Reproduce (clang 23.1.2, opt 23.1.2):

cat > tri.c <<'EOF'
int tri(int n) {
  int s = 0;
  for (int i = 0; i < n; i++)
    s = s + i;
  return s;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm tri.c -o - \
  | opt -passes=mem2reg -S -o tri.ll
opt -passes='print<scalar-evolution>' -disable-output tri.ll 2>&1 | grep -A1 -E '%(s|i).0 = phi'

Output:

  %s.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
  -->  {0,+,0,+,1}<%for.cond> U: full-set S: full-set       Exits: (trunc i33 (((zext i32 (-1 + (0 smax %n))<nsw> to i33) * (zext i32 (0 smax %n) to i33)) /u 2) to i32)        LoopDispositions: { %for.cond: Computable }
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  -->  {0,+,1}<nuw><nsw><%for.cond> U: [0,-2147483648) S: [0,-2147483648)       Exits: (0 smax %n)      LoopDispositions: { %for.cond: Computable }

What to notice: instead of iterating \(s \mapsto s + i\), SCEV writes the value after any number of trips as the chain of recurrences {0,+,0,+,1} and the exit value as \(n(n-1)/2\) (in 33-bit arithmetic): the "star" of the loop computed symbolically, which is what \(\llbracket P^{*} \rrbracket\) does in Theorem 14.5.12. SCEV is not a path-expression solver, but it is the production descendant of the idea of summarizing loops in closed form.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Allen–Cocke interval analysis	MOP for distributive frameworks with closure; reducible CFGs only (or node splitting)	\(O(\ell (n + e))\) algebra operations	Loop summaries reusable after edits	Medium: interval partition + function algebra	Historical (IBM compilers); the definition of reducibility
Structural analysis	Same, plus precise schemas; improper regions iterate	near-linear on structured code	A control tree mirroring the source	High: many schemas	Region-based optimization, decompilers, GPU structurizers
Tarjan's path expressions	MOP for any problem with a closed semiring of functions	\(O(e\,\alpha(e,n))\) on reducible CFGs	Symbolic path summaries, reusable across problems	High	Algebraic program analysis; theory; closed-form loop summaries (SCEV)

Choose an elimination method when you need summaries of loops or regions for reuse (incremental analysis, loop transformations) and your framework has a closure. Choose structural analysis when you want results attached to source-like structures. Choose path expressions when you solve many different problems over the same graph (compute the expressions once, interpret many times). Otherwise iterate (Lesson 14.4): simpler, handles every CFG and every monotone framework, and cheap in practice (a few visits per node [CHK04]).

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Allen–Cocke interval analysis	`intervals-running`, `genkill-closure`	— (theory; see below)	`intervals`	—
Structural analysis	`structural-schemas`, `elimination-irreducible`	—	`structural`	—
Tarjan's path expressions	`path-expression-interpret`, `genkill-compose`	—	`path-expressions`	—

No drill generates elimination problems: their only computational content beyond Lesson 14.4 is the gen/kill algebra of Definition 14.5.1, which the quiz questions genkill-compose and genkill-closure test on concrete pairs, and the reducibility test, drilled by Chapter 15's ./course drill loop-forms and natural-loops.

Pitfall

"Elimination is faster than iteration." Asymptotically on reducible graphs, yes; in practice RPO iteration converges in a handful of passes on real code (\(d(G)\) is small [Dragon2, §9.6]; see the measurements of [CHK04]) and is far simpler. Elimination pays off when you need the summaries themselves, not just the fixed point.

References¶

See the chapter references.

Lesson 14.5 — Elimination methods: intervals, structural analysis, path expressions¶

1. Problem and motivation¶

Allen–Cocke interval analysis¶

Structural analysis¶

Tarjan's path expressions¶

2. Definitions and algorithms¶

Allen–Cocke interval analysis¶

Structural analysis¶

Tarjan's path expressions¶

3. Worked example¶

Allen–Cocke interval analysis on the running example¶

Structural analysis on the running example¶

Tarjan's path expressions on the running example¶

4. Invariants and correctness¶

Allen–Cocke interval analysis¶

Structural analysis¶

Tarjan's path expressions¶

5. Complexity¶

6. Variants and refinements¶

Allen–Cocke interval analysis¶

Structural analysis¶

Tarjan's path expressions¶

7. In real compilers¶

Allen–Cocke interval analysis¶

Structural analysis¶

Tarjan's path expressions¶

8. Comparison¶

9. Assessment¶

References¶