Lesson 14.6 — Sparse analysis: def-use chains, SSA and sparse evaluation graphs¶

Techniques: propagation along def-use chains; SSA-based sparse propagation (sparse constant propagation, Wegman–Zadeck SCCP, sparse SSA liveness); Choi–Cytron–Ferrante sparse evaluation graphs · Pebble implements: sparse liveness in the comparison lab (labs/ch14-dataflow, requirement L1) · Lab: dense vs sparse liveness (ch14-solverbench Part 3) · Prerequisites: Lesson 14.3, Lesson 14.4, dominance frontiers (Ch 15, Lesson 15.3) · Time: 5–7 hours

A dense analysis keeps a fact per variable per program point and pushes all of them through every block, even through blocks that never touch the variable. For constant propagation of k in

int k = 3;                 /* ... 200 blocks that never mention k ... */
return r * k;

a dense solver copies "\(k = 3\)" through 200 transfer functions. A sparse analysis attaches the fact to the definition of k and sends it directly to the uses of k, along def-use chains. In SSA form every use has exactly one definition, so the chains are the SSA edges themselves; that is why SCCP, LLVM's SparseSolver, GCC's CCP and MLIR's sparse analyses all run on SSA. The comparison lab measures the difference for liveness: on a 5 000-block random function, dense bit-vector liveness takes 228 ms and the sparse per-value walk 15 ms (ch14-solverbench Part 3, this container).

1. Problem and motivation¶

Dense analyses cost \(O(\text{blocks} \times \text{facts})\) per pass even when each fact is relevant in a few blocks. Sparse analyses aim for cost proportional to the size of the def-use structure. The idea appeared as soon as use-def chains did [Ull73, Ken81], but became systematic with SSA [CFRWZ91] and with Choi, Cytron and Ferrante's sparse evaluation graphs [CCF91], which construct, for any monotone problem, the smallest graph on which the problem can be solved exactly.

Def-use chains¶

A def-use chain links a definition of \(v\) to every use it reaches — the inverse of reaching definitions (Lesson 14.3). Propagating along them skips every block in between [Ken81]. Without SSA the chains can be quadratic (every definition reaching every use through a join); SSA's phis factor them into linear size.

SSA-based sparse propagation¶

In SSA the chains are the operands of instructions. Sparse constant propagation evaluates each instruction when an operand's lattice value changes; Wegman and Zadeck's sparse conditional constant propagation (SCCP) also tracks which CFG edges are executable, so that a constant branch condition makes the other successor — and every phi operand coming from it — irrelevant [WZ91]. The same per-value view gives sparse liveness: walk backwards from each use to the definition, marking blocks live on the way [BBD+11, SSAB, Ch. 9]; LLVM's LiveVariables does exactly this for virtual registers. Pebble's lab implements it (L1) and checks it against the dense solver of E2.

Sparse evaluation graphs¶

SSA is a sparse representation for one problem family (values of variables). Choi, Cytron and Ferrante generalized the construction: for a given problem, the nodes whose transfer function is not the identity are the "interesting" ones; the places where their facts must be merged are their iterated dominance frontiers; connecting each node to its nearest interesting dominator gives the sparse evaluation graph (SEG), on which the problem has the same solution [CCF91]. MemorySSA in LLVM is an SEG for memory-state reaching definitions.

2. Definitions and algorithms¶

Def-use chains¶

Definition 14.6.1 (Def-use chains; SSA edges)

For a definition \(d\) of \(v\) and a use \(u\) of \(v\), \((d, u)\) is a def-use chain if \(d\) reaches \(u\) (Definition 14.3.2). In SSA form each use has exactly one reaching definition, its operand, so the def-use chains are the pairs (defining instruction, using instruction) — the SSA edges; a phi operand is a use located at the end of the corresponding predecessor (Definition 14.3.9).

Algorithm 14.6.2 (Sparse forward propagation over SSA edges)

Input: an SSA function; a lattice \(L\) per value; for each instruction \(I\) an abstract evaluation \(\hat{I} : L^{\mathrm{operands}} \to L\) (a phi joins its operands).
Output: \(V(x) \in L\) for every SSA value \(x\).
Precondition: each \(\hat{I}\) is monotone; \(L\) satisfies ACC.
Postcondition: \(V\) is the least fixed point of \(V(x) = \widehat{\mathrm{def}(x)}(V(\mathrm{operands}))\), the same values a dense analysis finds at each value's definition when all blocks are considered executable (Theorem 14.6.3).
Invariant: \(V \sqsubseteq\) the least fixed point; every instruction whose operands changed since its last evaluation is on \(W\).

function SparsePropagate(F):
    for every SSA value x: V[x] ← ⊥
    for every argument a: V[a] ← ⊤ (unknown input)
    W ← all instructions of F
    while W ≠ ∅:
        I ← remove any element of W
        new ← Î(V[operands of I])            # phis: ⊔ of V over all operands
        if new ≠ V[I]:
            V[I] ← new
            for every user U of I: add U to W  # follow the def-use (SSA) edges
    return V

Theorem 14.6.3 (Sparse = dense for SSA value problems)

For a problem whose facts are per SSA value and whose transfer functions only change the fact of the value an instruction defines, Algorithm 14.6.2 computes the same fixed point as the dense framework of Lesson 14.2 over \(\mathit{Values} \to L\), and every instruction is evaluated at most \(1 + h(L) \cdot \lvert \mathrm{operands} \rvert\) times.

Proof

In the dense framework the fact of \(x\) at any point dominated by \(\mathrm{def}(x)\) equals \(V(x)\): no other instruction changes it (each transfer function only writes its own value), and SSA guarantees that all uses are dominated by the definition. So the dense equations restricted to the definition points are exactly \(V(x) = \widehat{\mathrm{def}(x)}(V(\mathrm{operands}))\), a system over \(\mathit{Values} \to L\) whose least fixed point Algorithm 14.6.2 computes by the worklist argument of Theorem 14.4.4 (Lemma 14.4.3 with "dependents" = users). An instruction is re-added only when one of its operands strictly grows, which happens at most \(h(L)\) times per operand. \(\square\)

Walking def-use chains backwards: LLVM's DemandedBits

Reproduce (opt 23.1.2):

cat > db.ll <<'EOF'
define i8 @g(i32 %x, i32 %y) {
  %a = add i32 %x, %y
  %s = shl i32 %a, 4
  %t = trunc i32 %s to i8
  ret i8 %t
}
EOF
opt -passes='print<demanded-bits>' -disable-output db.ll 2>&1 | sort   # the printer's order varies

Output:

DemandedBits: 0xf for   %a = add i32 %x, %y
DemandedBits: 0xf for %a in   %s = shl i32 %a, 4
DemandedBits: 0xf for %x in   %a = add i32 %x, %y
DemandedBits: 0xf for %y in   %a = add i32 %x, %y
DemandedBits: 0xff for   %s = shl i32 %a, 4
DemandedBits: 0xff for   %t = trunc i32 %s to i8
DemandedBits: 0xff for %s in   %t = trunc i32 %s to i8
DemandedBits: 0xffffffff for 4 in   %s = shl i32 %a, 4
Printing analysis 'Demanded Bits Analysis' for function 'g':

What to notice: DemandedBits is liveness at bit granularity: which bits of a value may be read later. It starts from the "roots" (here ret), and for each instruction propagates demanded bits to its operands along use-def chains (DemandedBits::performAnalysis, a worklist over instructions) [LLVM-DB] — Algorithm 14.6.2 run backwards. trunc to i8 demands only the low 8 bits of %s; shl ... 4 shifts that demand down to the low 4 bits of %a; so only 4 bits of %x and %y matter. No block-level IN/OUT sets exist anywhere.

SSA-based sparse propagation¶

Algorithm 14.6.4 (Sparse SSA liveness by path exploration)

Input: an SSA function (Definition 14.3.9's conventions).
Output: live-in and live-out sets of every block.
Precondition: SSA form (single definition per value).
Postcondition: the sets equal the least solution of Definition 14.3.9's equations (Theorem 14.6.5); each (value, block) live-in pair is discovered once.
Invariant: every block marked live-in for \(v\) has all its predecessors marked live-out for \(v\) and either scheduled or already processed.

function SparseLiveness(F):
    for every value v (arguments and value-producing instructions):
        for every use of v in instruction U:
            if U is a phi of block B reading v from predecessor P:
                LiveOut[P] ← LiveOut[P] ∪ {v};  UpAndMark(v, P)
            else if U's block defines v before U:  continue   # not upward exposed
            else: UpAndMark(v, block(U))

function UpAndMark(v, B):
    stack ← [B]
    while stack ≠ []:
        X ← pop(stack)
        if X = defblock(v): continue                 # v is defined here: not live-in
        if v ∈ LiveIn[X]: continue                   # already explored from here
        LiveIn[X] ← LiveIn[X] ∪ {v}
        for P in preds(X):
            LiveOut[P] ← LiveOut[P] ∪ {v}
            push P onto stack

(defblock of an argument is none: arguments are live-in to the entry. A phi of \(B\) is defined at the start of \(B\), so defblock stops the walk there too.) This is the lab's contract lab14::computeLivenessSparse (labs/ch14-dataflow/include/lab14/SparseLiveness.h); SparseStats::Marks counts the executions of LiveIn[X] ← LiveIn[X] ∪ {v}.

Theorem 14.6.5 (Correctness of Algorithm 14.6.4)

Algorithm 14.6.4 computes the sets of Definition 14.3.9. It performs exactly \(\sum_{B} \lvert \mathrm{LiveIn}(B) \rvert\) marks and \(O\big(\sum_{v} \sum_{B : v \in \mathrm{LiveIn}(B)} (1 + \lvert \mathrm{preds}(B) \rvert)\big)\) steps.

Proof

Soundness (\(\subseteq\) of the least solution): a block is marked live-in for \(v\) only when there is a path from it to a use of \(v\) that avoids \(\mathrm{defblock}(v)\) (the path the walk followed backwards), and live-out only on predecessors of such blocks or of phi uses — both are forced by the equations of Definition 14.3.9, so every mark is in the least solution. Completeness (\(\supseteq\)): if \(v \in \mathrm{LiveIn}(X)\) in the least solution, there is a path \(X \leadsto\) (a use of \(v\)) that does not pass \(\mathrm{defblock}(v)\) except possibly at its start... (for \(X \neq \mathrm{defblock}(v)\), none at all); the walk started from that use visits the path's blocks backwards, and no block on it is \(\mathrm{defblock}(v)\), so it reaches and marks \(X\) — unless it stops earlier at a block already marked, whose own exploration (by induction on the order of marking) reached everything above it. Live-out sets are the predecessors' marks plus phi uses, exactly the first equation. Cost: the check v ∈ LiveIn[X] stops every revisit, so each (value, block) pair is marked once and pushes its predecessors once. The course test ch14.SparseLiveness.* checks both the sets (against a path-search oracle) and Marks \(= \sum_B \lvert \mathrm{LiveIn}(B) \rvert\). \(\square\)

Algorithm 14.6.6 (Sparse conditional constant propagation, Wegman–Zadeck)

Input: an SSA function; the constant lattice \(\mathbb{Z}_\bot^\top\) per value.
Output: \(V(x)\) for each value; the set of executable blocks and edges.
Precondition: SSA form.
Postcondition: the least fixed point of the combined system in which an edge is executable only if its source block is executable and the branch condition's value allows it, and a phi joins only operands on executable edges (Theorem 14.6.7).
Invariant: every executable edge whose destination has not been processed for it is in FlowWL; every instruction in an executable block whose operand value changed is in SSAWL.

function SCCP(F):
    V[x] ← ⊥ for every value;  V[arg] ← ⊤
    ExecEdge ← ∅;  ExecBlock ← ∅
    FlowWL ← [(∗, entry)];  SSAWL ← []
    while FlowWL ≠ [] or SSAWL ≠ []:
        if FlowWL ≠ []:
            (P, B) ← pop FlowWL
            if (P, B) ∈ ExecEdge: continue
            ExecEdge ← ExecEdge ∪ {(P, B)}
            for each phi of B: VisitPhi(phi)
            if B ∉ ExecBlock:
                ExecBlock ← ExecBlock ∪ {B}
                for each non-phi I of B: VisitInst(I)
        else:
            I ← pop SSAWL
            if block(I) ∈ ExecBlock:
                if I is a phi: VisitPhi(I) else: VisitInst(I)

    function VisitPhi(φ in B):   Update(φ, ⊔ { V[op_P] : (P, B) ∈ ExecEdge })
    function VisitInst(I):
        if I is a conditional branch on c:
            if V[c] = true:  push (block(I), then-successor) on FlowWL
            if V[c] = false: push (block(I), else-successor) on FlowWL
            if V[c] = ⊤:     push both
        else if I is an unconditional branch: push its edge
        else: Update(I, Î(V[operands]))
    function Update(x, new):
        if new ≠ V[x]: V[x] ← new; push every user of x on SSAWL

Theorem 14.6.7 (SCCP)

SCCP terminates after \(O(\lvert \text{SSA edges} \rvert + \lvert E \rvert)\) visits and computes a solution at least as precise as sparse constant propagation followed by unreachable-code elimination, iterated to a fixed point; it finds every constant that either of them finds, and some that neither finds.

Proof sketch (full proof: [WZ91, §4])

Termination: each value's lattice element rises at most twice (\(\bot \to c \to \top\)), each edge becomes executable once; each rise pushes the value's users, each executable edge its target. Precision: SCCP's system is the product of the value lattice and the "executable" lattice \(\{\text{no}, \text{yes}\}\) per edge, solved together; its least fixed point is below the fixed point of alternating the two separate analyses, because each of those computes a fixed point of a system with fewer constraints assumed away (an edge assumed executable contributes its phi operands). The example x = 1; loop { if (x != 1) x = 2; } of Lesson 14.1 is found by SCCP but by neither separate analysis: constant propagation alone sees \(x \in \{1, 2\}\), and unreachable-code elimination alone does not know that \(x = 1\).

SCCP in GCC: lattice transitions and executable edges

Reproduce (gcc 14.2.0):

cat > cp.c <<'EOF'
int h(int n) {
  int k = 3;
  int r;
  if (k > 2)
    r = n + k;
  else
    r = n - k;
  return r * k;
}
EOF
gcc-14 -O1 -fdump-tree-ccp1-details -S cp.c -o /dev/null
sed -n '/^Simulating block 2/,/^Substituting/p' cp.c.*t.ccp1 | grep -v '^$'

Output:

Simulating block 2
Visiting statement:
k_2 = 3;
which is likely CONSTANT
Lattice value changed to CONSTANT 3.  Adding SSA edges to worklist.
marking stmt to be not simulated again
Visiting statement:
if (k_2 > 2)
which is likely CONSTANT
Match-and-simplified k_2 > 2 to 1
Adding destination of edge (2 -> 3) to worklist
marking stmt to be not simulated again
Simulating block 3
Visiting statement:
r_5 = n_3(D) + k_2;
which is likely CONSTANT
Lattice value changed to VARYING.  Adding SSA edges to worklist.
Adding destination of edge (3 -> 5) to worklist
Simulating block 5
Visiting PHI node: r_1 = PHI <r_5(3), r_4(4)>
    Argument #0 (3 -> 5 executable)
    r_5 Value: CONSTANT r_5
    Argument #1 (4 -> 5 not executable)
    PHI node value: VARYING
Lattice value changed to VARYING.  Adding SSA edges to worklist.
Visiting statement:
_6 = r_1 * k_2;
which is likely CONSTANT
Lattice value changed to VARYING.  Adding SSA edges to worklist.
Visiting statement:
return _6;
No interesting values produced.  Marked VARYING.
Substituting values and folding statements

What to notice: GCC's CCP (gcc/tree-ssa-ccp.cc, "based on the SSA propagation engine") [GCC-CCP] is Algorithm 14.6.6. k_2 = 3 rises from UNDEFINED to CONSTANT 3; the condition folds to true, so only the edge 2 -> 3 is added to the flow worklist and block 4 (the else) is never simulated. At the phi r_1 = PHI <r_5(3), r_4(4)> argument #1 comes from the non-executable edge 4 -> 5 and is ignored — the "conditional" in SCCP. r_5 depends on the parameter n, so r_1 is VARYING (\(\top\)).

Sparse liveness in LLVM's code generator: LiveVariables

Reproduce (llc 23.1.2, x86-64):

cat > lv.ll <<'EOF'
define i32 @sum(i32 %n) {
entry:
  br label %head
head:
  %i = phi i32 [ 0, %entry ], [ %i1, %body ]
  %s = phi i32 [ 0, %entry ], [ %s1, %body ]
  %c = icmp slt i32 %i, %n
  br i1 %c, label %body, label %exit
body:
  %s1 = add i32 %s, %i
  %i1 = add i32 %i, 1
  br label %head
exit:
  ret i32 %s
}
EOF
llc -O2 -mtriple=x86_64-unknown-linux-gnu -print-after=livevars lv.ll -o /dev/null 2>&1 | sed -n '/^bb.1/,$p'

Output:

bb.1.head:
; predecessors: %bb.0, %bb.2
  successors: %bb.2(0x7c000000), %bb.3(0x04000000); %bb.2(96.88%), %bb.3(3.12%)

  %0:gr32 = PHI %5:gr32, %bb.0, %3:gr32, %bb.2
  %1:gr32 = PHI %5:gr32, %bb.0, %2:gr32, %bb.2
  CMP32rr %0:gr32, %4:gr32, implicit-def $eflags
  JCC_1 %bb.3, 13, implicit killed $eflags
  JMP_1 %bb.2

bb.2.body:
; predecessors: %bb.1
  successors: %bb.1(0x80000000); %bb.1(100.00%)

  %2:gr32 = ADD32rr killed %1:gr32(tied-def 0), %0:gr32, implicit-def dead $eflags
  %3:gr32 = INC32r killed %0:gr32(tied-def 0), implicit-def dead $eflags
  JMP_1 %bb.1

bb.3.exit:
; predecessors: %bb.1

  $eax = COPY killed %1:gr32
  RET 0, killed $eax

# End machine code for function sum.

What to notice: killed marks the last use of a virtual register on its live range — the information register allocation needs. LiveVariables computes it per virtual register (LiveVariables::HandleVirtRegUse and MarkVirtRegAliveInBlock, llvm/lib/CodeGen/LiveVariables.cpp) [LLVM-LV]: from each use it walks predecessor blocks up to the definition, exactly Algorithm 14.6.4. %0 (the phi for i) is killed in bb.2 by the INC that defines its successor value; %1 (s) is killed in bb.2 and in bb.3 — on each path its last use.

Sparse evaluation graphs¶

Definition 14.6.8 (Sparse evaluation graph)

Fix a forward monotone problem on \(G = (N, E, r)\) with transfer functions \(f_n\). A node is interesting if \(f_n \neq \mathrm{id}\); let \(S\) be the interesting nodes plus \(r\). The meet nodes are \(\mathrm{DF}^{+}(S)\) (iterated dominance frontier, Ch 15). The sparse evaluation graph has node set \(S \cup \mathrm{DF}^{+}(S)\) and an edge \(m \to n\) for every SEG node \(n\) and every CFG predecessor \(p\) of \(n\) (or \(n\) itself if \(n \in S \setminus \mathrm{DF}^{+}(S)\)) where \(m\) is the nearest SEG node dominating \(p\) (inclusive). Every non-SEG CFG node \(x\) is mapped to the nearest SEG node dominating it; its value is that node's output.

Algorithm 14.6.9 (SEG construction and solution, Choi–Cytron–Ferrante)

Input: a forward problem (transfer functions, lattice); the dominator tree and dominance frontiers of \(G\).
Output: the SEG, its solution, and the values of all CFG nodes.
Precondition: every node reachable; transfer functions monotone.
Postcondition: the SEG solution, mapped back, equals the MFP solution on \(G\) (Theorem 14.6.10).
Invariant: during the dominator-tree walk, top is the nearest SEG node dominating the current node.

function BuildSEG(G, f, DT, DF):
    S ← { n : f_n ≠ id } ∪ {r}
    M ← DF⁺(S)                                  # meet nodes (Cytron et al.'s phi placement)
    SEG ← S ∪ M
    Walk(r, top = r)                             # preorder walk of the dominator tree
    solve the problem on SEG (Lesson 14.4) with f_n for n ∈ S, id for n ∈ M ∖ S, join at M
    for x in N ∖ SEG: value(x) ← OUT[map(x)]

function Walk(x, top):
    if x ∈ SEG:
        if x ∉ M and x ≠ r: add SEG edge top → x        # top = nearest strict SEG dominator
        top ← x
    map(x) ← top
    for s in succs(x) with s ∈ M:                # an edge into a meet node
        add SEG edge top → s                     # top = nearest SEG node dominating x
    for c in children of x in DT: Walk(c, top)

Theorem 14.6.10 (SEG correctness)

The SEG solution, mapped back through map, equals the MFP solution of the problem on \(G\).

Proof sketch (full proof: [CCF91, §3])

Between an SEG node \(m\) and a CFG node \(x\) it dominates with no SEG node in between on the dominator path, every CFG path from \(m\) to \(x\) that stays below \(m\) passes only identity nodes and no merge that could bring in a different value — any such merge point would be in \(\mathrm{DF}^{+}(S)\) and hence an SEG node. So the dense value at \(x\) equals \(m\)'s output, and at a meet node the dense join over CFG predecessors equals the join over the SEG predecessors mapped from them. The SEG equations are therefore the dense equations with identity chains contracted, and have the same least fixed point.

An SEG for memory: LLVM's MemorySSA

Reproduce (opt 23.1.2):

cat > mssa.ll <<'EOF'
define i32 @m(ptr noalias %p, ptr noalias %q, i1 %c) {
entry:
  store i32 1, ptr %p
  br i1 %c, label %then, label %join
then:
  store i32 2, ptr %q
  br label %join
join:
  %v = load i32, ptr %p
  ret i32 %v
}
EOF
opt -passes='print<memoryssa>' -disable-output mssa.ll

Output:

MemorySSA for function: m
define i32 @m(ptr noalias %p, ptr noalias %q, i1 %c) {
entry:
; 1 = MemoryDef(liveOnEntry)
  store i32 1, ptr %p, align 4
  br i1 %c, label %then, label %join

then:                                             ; preds = %entry
; 2 = MemoryDef(1)
  store i32 2, ptr %q, align 4
  br label %join

join:                                             ; preds = %then, %entry
; 3 = MemoryPhi({entry,1},{then,2})
; MemoryUse(1)
  %v = load i32, ptr %p, align 4
  ret i32 %v
}

What to notice: the interesting nodes of "which store last wrote memory" are the stores (MemoryDefs 1 and 2); the meet node 3 = MemoryPhi sits at %join, the dominance frontier of the store in %then (Definition 14.6.8). Every other instruction maps to the nearest dominating MemoryDef — the SEG edges. The load's MemoryUse(1) goes further than a plain SEG: MemorySSA uses alias analysis (%p and %q are noalias) to skip def 2 and the phi and link the load directly to def 1 (llvm/lib/Analysis/MemorySSA.cpp) [LLVM-MSSA].

3. Worked example¶

Running example in SSA form (tests/ch14/Inputs/running.ssa.ll, the C version of Lesson 14.3's program after mem2reg). Block names: entry (A), while.cond (B), while.body (C), if.then (D), if.end (E), while.end (F).

flowchart TD
  entry(["entry: %mul = %a * %b"]) --> while.cond["while.cond: %i.0 = phi(0, %add4)<br/>%s.0 = phi(0, %s.1)<br/>%a.addr.0 = phi(%a, %a.addr.1)<br/>%cmp = %i.0 < %n"]
  while.cond --> while.body["while.body: %mul1 = %a.addr.0 * %b<br/>%cmp2 = %mul1 < %s.0"]
  while.cond --> while.end["while.end: ret %s.0"]
  while.body --> if.then["if.then: %add = %s.0 + %mul1<br/>%sub = %mul1 - 1"]
  while.body --> if.end["if.end: %s.1 = phi(%add, %s.0)<br/>%a.addr.1 = phi(%sub, %a.addr.0)<br/>%mul3 = %a.addr.1 * %b<br/>%add4 = %i.0 + 1"]
  if.then --> if.end
  if.end --> while.cond

Def-use chains on the running example¶

The SSA edges of %s.0 (defined by a phi in while.cond): uses in while.body (%cmp2), if.then (%add), if.end (phi %s.1, operand from while.body) and while.end (ret). A dense liveness solver pushes the fact "\(s.0\)" through all six blocks for every pass; sparse propagation of a lattice value for %s.0 touches exactly these four uses. The whole function has 16 values and 25 SSA edges (operands that are values), against 6 blocks × 16 values = 96 dense (block, value) facts per pass.

SSA-based sparse propagation on the running example¶

Algorithm 14.6.4 for %s.0 (defblock while.cond):

step	action	stack after	LiveIn / LiveOut changes
1	use in `%cmp2` (block `while.body`, not defined there): UpAndMark(`while.body`)	[while.body]	—
2	pop `while.body`: mark live-in; preds `while.cond`	[while.cond]	LiveIn(while.body), LiveOut(while.cond)
3	pop `while.cond` = defblock: stop	[]	—
4	use in `%add` (block `if.then`): UpAndMark(`if.then`)	[if.then]	—
5	pop `if.then`: mark; pred `while.body`	[while.body]	LiveIn(if.then), LiveOut(while.body)
6	pop `while.body`: already live-in: stop	[]	—
7	phi `%s.1` reads `%s.0` from `while.body`: LiveOut(`while.body`) (already); UpAndMark(`while.body`)	[while.body]	—
8	pop `while.body`: already live-in: stop	[]	—
9	use in `ret` (block `while.end`): UpAndMark(`while.end`)	[while.end]	—
10	pop `while.end`: mark; pred `while.cond`	[while.cond]	LiveIn(while.end) (LiveOut(while.cond) already)
11	pop `while.cond` = defblock: stop	[]	—

Result: %s.0 is live-in to while.body, if.then, while.end (3 marks) and live-out of while.cond, while.body — the same as print<pebble-liveness> (Lesson 14.3). Over all 16 values the walk makes 19 marks: \(3 + 2 + 5 + 5 + 3 + 1\), the total size of the live-in sets.

SCCP (Algorithm 14.6.6) on the loop of Lesson 14.1 (x = 1; for (i...) if (x != 1) x = 2;, SSA values %x.0 = phi(1, %x.1) at the head, %cmp1 = %x.0 != 1, %x.1 = phi(2 from if.then, %x.0 from for.body)):

step	event	lattice / executable changes
1	edge (∗, entry)	entry executable; `br` pushes (entry, for.cond)
2	edge (entry, for.cond)	for.cond executable; `%x.0 = phi(1)` → 1; `%i.0` → 0; `%cmp` = `0 < %n` → ⊤; both successors pushed
3	edge (for.cond, for.body)	`%cmp1 = (1 != 1)` → false; only (for.body, if.end) pushed
4	edge (for.cond, for.end)	`ret %x.0`
5	edge (for.body, if.end)	`%x.1 = phi(—, %x.0)`: only the for.body operand is on an executable edge → 1
6	edge (if.end, for.inc), then (for.inc, for.cond)	`%inc` → ⊤; `%i.0` → ⊤; `%x.0 = 1 ⊔ 1 = 1` (no change)
7	SSA worklist drains	`%x.0 = 1`, `%x.1 = 1`; `if.then` never executable

The edge if.then → if.end never becomes executable, so the operand 2 of %x.1 is never joined: %x.0 stays 1, which is why opt -passes=sccp returned ret i32 1 in Lesson 14.1.

Sparse evaluation graphs on the running example¶

Reaching definitions of variable s in the non-SSA running example: interesting nodes \(S = \{A, D\}\) (they assign s) plus the entry \(A\). \(\mathrm{DF}(A) = \emptyset\), \(\mathrm{DF}(D) = \{E\}\), \(\mathrm{DF}(E) = \{B\}\), \(\mathrm{DF}(B) = \{B\}\): \(\mathrm{DF}^{+}(S) = \{B, E\}\) — exactly where SSA places phis for s (%s.0 in B, %s.1 in E). SEG nodes \(\{A, B, D, E\}\); edges: \(A \to B\) (A is the nearest SEG dominator of B's predecessor A), \(E \to B\) (predecessor E is itself in the SEG), \(D \to E\), \(B \to E\) (E's predecessor C maps to B), and \(B \to D\) (D's predecessor C maps to B). Blocks C and F map to B. Solving reaching definitions of s on this 4-node graph gives \(\mathrm{IN}(B) = \{d_3, d_5\}\), which C and F inherit — the \(s\)-part of Lesson 14.3's table.

Try it

Implement L1 and run build/<preset>/bin/ch14-solverbench: Part 3 prints dense vs sparse times and the number of sparse marks. ./course drill dataflow-table --seed 3 --difficulty medium (liveness instances) gives dense tables you can re-derive sparsely, one variable at a time.

4. Invariants and correctness¶

Def-use chains¶

Theorem 14.6.3. When it breaks: the reduction to per-value facts needs transfer functions that write only their own value. Facts about memory (a store changes what a load of another pointer returns) or about relations between values (octagons) are not per-value; they need MemorySSA-style SEGs or dense analysis. And without SSA, def-use chains can be quadratic: \(m\) definitions of \(x\) on the arms of a switch and \(m\) uses after it give \(m^2\) chains; the phi of SSA makes it \(2m\).

SSA-based sparse propagation¶

Theorems 14.6.5 and 14.6.7. When it breaks: Algorithm 14.6.4 relies on "defined in \(B\)" meaning "defined before every use in \(B\)", which SSA's dominance property guarantees for reachable code; in unreachable blocks LLVM allows a use before its definition, and the walk must then treat the use as upward exposed (the lab's solution handles this case explicitly). SCCP's optimism is only sound because it computes a fixed point: stopping early — for example after a timeout — may leave a block wrongly marked non-executable.

Sparse evaluation graphs¶

Theorem 14.6.10. When it breaks: the SEG is built per problem instance (it depends on which nodes are interesting), so a pass that solves many problems (one per variable) pays for many SEGs; Cytron's DF+ can be quadratic per problem. Backward problems need the reverse graph's (post-)dominance frontiers.

5. Complexity¶

Let \(n\) = blocks, \(e\) = CFG edges, \(V\) = SSA values, \(U\) = SSA edges (operands that are values), \(h\) = lattice height, \(\lvert \mathrm{live} \rvert = \sum_B \lvert \mathrm{LiveIn}(B) \rvert\).

Technique	Time (worst)	Time (typical)	Space	Variables
Def-use chains (Algorithm 14.6.2)	\(O(h \cdot U)\) evaluations	1–2 evaluations per instruction	\(O(V + U)\)	\(V, U, h\)
Sparse liveness (Algorithm 14.6.4)	\(O(\lvert \mathrm{live} \rvert + \sum \lvert \mathrm{preds} \rvert \text{ over marks}) \le O(V \cdot e)\)	proportional to live-range sizes	\(O(\lvert \mathrm{live} \rvert)\)	\(V, e\)
SCCP (Algorithm 14.6.6)	\(O(U + e)\) visits (\(h = 2\))	linear	\(O(V + e)\)	\(U, e\)
Dense liveness, for comparison	\(O((d+2) \cdot e \cdot V / w)\)	3–6 passes	\(O(n V / w)\)	\(n, e, V, w, d\)
SEG construction + solution	\(O(n^2)\) per problem with Cytron DF+; \(O(n + e)\) with linear DF+	near-linear	\(O(\lvert \mathrm{SEG} \rvert)\)	\(n, e\)

Proposition 14.6.11 (Sparse beats dense when live ranges are short)

For liveness on a function where each value is live-in to at most \(c\) blocks and every block has at most \(\Delta\) predecessors, Algorithm 14.6.4 costs \(O(U + c\,V (1 + \Delta))\) steps, while one dense pass alone costs \(\Theta(n \cdot V / w)\) word operations.

Proof

Scanning the uses costs \(O(U)\). Theorem 14.6.5's walk cost is \(\sum_v \sum_{B : v \in \mathrm{LiveIn}(B)} (1 + \lvert \mathrm{preds}(B) \rvert) \le \sum_v c\,(1 + \Delta)\). A dense pass touches every block's \(\lceil V / w \rceil\)-word vectors: \(\Theta(n V / w)\). For constant \(c\) and \(\Delta\) (short live ranges, CFGs of bounded in-degree) the sparse cost is linear in the size of the function, the dense cost quadratic. \(\square\)

Pathological input. For sparse liveness, a value used at the bottom of a chain of \(n\) blocks and defined at the top is live in all \(n\) blocks: \(n\) marks. With \(V = n\) such values (each defined at the top), sparse liveness does \(\Theta(n^2)\) marks — the same order as the size of the answer, which is also what dense liveness stores.

At scale: ch14-solverbench Part 3 (this container): 5 000 blocks, 15 019 values — dense 228 ms, sparse 14.6 ms with 20 656 marks; 500 blocks — dense 2.4 ms, sparse 0.7 ms. SCCP is linear and runs several times in LLVM's -O2 pipeline (sccp, ipsccp).

Def-use chains¶

Static single information (SSI) / e-SSA [Ana99]: add σ-functions at branches so that branch-refined facts (like x < 10 on one edge) also become per-value — trade-off: more nodes, but interval and nullness analyses become sparse. LLVM's PredicateInfo (ssa.copy intrinsics) serves the same purpose for SCCP.
Factored use-def chains (FUD chains, Wolfe) [SSAB, Ch. 8] — SSA-like factoring without renaming — trade-off: sparse chains without rewriting the program.

SSA-based sparse propagation¶

Liveness checking [BHG+08]: answer "is \(v\) live at \(p\)?" by querying the dominator tree and a precomputed loop structure, no sets at all — trade-off: fast per query, useful when few queries are needed (SSA destruction).
MLIR's sparse framework [MLIR-DF]: SparseForwardDataFlowAnalysis runs Algorithm 14.6.2 with dead-code analysis in the same solver — SCCP generalized to any lattice.

Sparse evaluation graphs¶

MemorySSA [LLVM-MSSA]: an SEG for memory with alias-analysis-based "optimized uses" — trade-off: cheap updates, approximate.
Quick propagation graphs (Johnson–Pingali dependence flow graphs) and sparse value-flow graphs in pointer analysis (SVF) — trade-off: more precision per problem, more construction cost.

7. In real compilers¶

Def-use chains¶

LLVM

Every llvm::Value keeps its use list (Value::uses()), so def-use chains are free; llvm/lib/Analysis/DemandedBits.cpp — DemandedBits::performAnalysis (LLVM 23.1.2) [LLVM-DB]. llvm/include/llvm/Analysis/SparsePropagation.h — SparseSolver propagates along them [LLVM-SPARSE].

GCC gcc/tree-ssa-propagate.cc — the SSA propagation engine behind CCP and copy propagation (GCC 15) [GCC-CCP].

SSA-based sparse propagation¶

LLVM

llvm/lib/Transforms/Utils/SCCPSolver.cpp — SCCPInstVisitor::solve, markEdgeExecutable, visitPHINode (LLVM 23.1.2) [LLVM-SCCP]; llvm/lib/CodeGen/LiveVariables.cpp — MarkVirtRegAliveInBlock, the sparse liveness walk [LLVM-LV].

GCC gcc/tree-ssa-ccp.cc — Wegman–Zadeck CCP; the file cites "Wegman and Zadeck, ACM TOPLAS 13(2):181-210" (GCC 15) [GCC-CCP].
MLIR mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h — AbstractSparseForwardDataFlowAnalysis; DeadCodeAnalysis.h tracks executable blocks (LLVM 23.1.2) [MLIR-DF].

Find where LLVM does it. Open llvm/lib/Transforms/Utils/SCCPSolver.cpp and find SCCPInstVisitor::markEdgeExecutable. Question: after an edge becomes executable into an already-executable block, which instructions of the destination are revisited? (Quiz llvm-where-sccp-edge.)

Sparse evaluation graphs¶

LLVM

llvm/lib/Analysis/MemorySSA.cpp — MemorySSA::buildMemorySSA calls placePHINodes, which places MemoryPhis with a ForwardIDFCalculator (iterated dominance frontiers), then links uses to their nearest dominating definitions (LLVM 23.1.2) [LLVM-MSSA].

GCC virtual operands (.MEM SSA names in gcc/tree-ssa-operands.cc) play the same role for memory (GCC 15).

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Def-use chains	Same as dense for per-value problems (Theorem 14.6.3)	\(O(h \cdot U)\); skips irrelevant blocks	Facts per value, not per point	Low on SSA; quadratic chains without it	DemandedBits, value-lattice analyses
SSA-based sparse propagation	SCCP: strictly more than CP + UCE; sparse liveness = dense liveness	Linear (SCCP); proportional to live ranges (liveness)	Per-value lattice, executable edges	Medium (two worklists)	SCCP/CCP in every compiler; codegen liveness
Sparse evaluation graphs	Same as dense MFP for any monotone problem (Theorem 14.6.10)	Near-linear per problem after DF+	A per-problem sparse graph	High (per-problem construction)	MemorySSA; sparse memory analyses

Choose def-use/SSA propagation when your facts are per value and the IR is in SSA — the default in LLVM. Choose sparse liveness when you need live sets once on SSA (register allocation); choose dense bit vectors when you re-solve often after small edits or the IR is not in SSA. Choose an SEG when the problem is not per value (memory) but its interesting nodes are few.

Lab numbers: Part 3 above; reproduce with build/<preset>/bin/ch14-solverbench after E1, E2 and L1.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Def-use chains	`defuse-quadratic`, `sparse-vs-dense-cost`	— (see below)	`def-use`	—
SSA-based sparse propagation	`sccp-executable`, `sparse-liveness-marks`, `llvm-where-sccp-edge`	`./course drill dataflow-table` (liveness, to re-derive sparsely)	`sparse`	lab L1
Sparse evaluation graphs	`seg-meet-nodes`, `memoryssa-seg`	`./course drill idf` (Ch 15: iterated dominance frontiers = SEG meet nodes)	`seg`	—

Def-use chains have no drill of their own: tracing them is reading operands; the computational content (reaching definitions) is drilled by dataflow-table.

Pitfall

"Sparse means less precise." It does not: Theorems 14.6.3, 14.6.5 and 14.6.10 say sparse and dense compute the same fixed point; SCCP is even more precise than dense constant propagation, because it also tracks executable edges. Sparsity changes the cost, not the answer.

References¶

See the chapter references.

Lesson 14.6 — Sparse analysis: def-use chains, SSA and sparse evaluation graphs¶

1. Problem and motivation¶

Def-use chains¶

SSA-based sparse propagation¶

Sparse evaluation graphs¶

2. Definitions and algorithms¶

Def-use chains¶

SSA-based sparse propagation¶

Sparse evaluation graphs¶

3. Worked example¶

Def-use chains on the running example¶

SSA-based sparse propagation on the running example¶

Sparse evaluation graphs on the running example¶

4. Invariants and correctness¶

Def-use chains¶

SSA-based sparse propagation¶

Sparse evaluation graphs¶

5. Complexity¶

6. Variants and refinements¶

Def-use chains¶

SSA-based sparse propagation¶

Sparse evaluation graphs¶

7. In real compilers¶

Def-use chains¶

SSA-based sparse propagation¶

Sparse evaluation graphs¶

8. Comparison¶

9. Assessment¶

References¶