Cfg = cfg(Entry, Rpo, Succs, Preds) is the control-flow graph of Blocks, whose first block is the entry:

- Rpo: the reachable labels in reverse postorder, Entry first;
- Succs: assoc Label -> ordset of successor labels (every block);
- Preds: assoc Label -> ordset of predecessor labels (every block,
  including unreachable predecessors, as phis must list them).

Preds is Preds₀ with Pred in the (unsorted) predecessor list of each label in Ss.

Idom is the assoc Label -> immediate dominator, for the reachable labels other than the entry (Cooper, Harvey and Kennedy, "A Simple, Fast Dominance Algorithm").

Idom is the fixed point, from Idom₀, of sweeps over Labels in reverse postorder.

in Idom, the idom of B is the nearest common dominator of those of its predecessors that have an idom in Idom₀. Changed is true if that differs from B's idom in Idom₀, and Changed₀ if not.

Common is the nearest common dominator of A and B: A if they are equal, and otherwise the nearest common dominator of the earlier one in reverse postorder and the idom of the later one.

Kids is the assoc Label -> the children of Label in the dominator tree, in reverse postorder, for every reachable label.

Kids is Kids₀ with L in front of the children of its idom, if it has one.

A dominates B (both reachable): A is B, or A dominates the idom of B.

Intervals is the assoc Label -> Pre-Last for every reachable label: Pre is the preorder number of Label in the dominator tree, and Last the last one in its subtree.

Intervals is Intervals₀ with the intervals of the dominator subtree at L, numbered in preorder from N₀; N is the next free number.

A dominates B, in constant time, given Intervals from dom_intervals/3.

DF is the assoc Label -> ordset of the labels in its dominance frontier, for every reachable label. As in CHK, a join point is in the frontier of each label on the idom path from each of its predecessors up to (not including) its own idom.

DF is DF₀ with B in the frontiers it joins, if it has two or more reachable predecessors. DF₀ has a key for every reachable label, so it also tells which predecessors are reachable.

DF is DF₀ with B in the frontier of every label on the idom path from Runner up to (not including) Stop.

Loops is the assoc Header -> loop(Latches, Body), both ordsets of labels. A latch has an edge to a header that dominates it. Body is the union of their natural loops. Only reachable blocks participate. Nested loops have separate entries; an irreducible cycle without a dominating header is NOT a natural loop. Empty does not mean acyclic, and this analysis alone cannot justify removing polls.

LiveIn and LiveOut are the assocs Label -> ordset of the names live on entry to and exit from each block (every block, reachable or not), the least solution of the backward dataflow equations

LiveOut(B) = union over successors S of LiveIn(S) and EdgeUses(B-S)
LiveIn(B)  = Gen(B) ∪ (LiveOut(B) \ Kill(B))

GenKill is the assoc Label -> Gen-Kill (ordsets: the names read before any write in the block, and the names written). EdgeUses is the assoc (Pred-Succ) -> ordset of the names read on that edge only (phi arguments). Names are anything ordsets can hold, so the same relation serves temps (temp_liveness/3) and promote's memory slots.

Out is the live-out set of L, given the live-in sets LiveIn.

LiveIn and LiveOut are liveness/5 of Blocks over temp names. A phi defines its temp at block entry (in Kill, never in LiveIn) and reads its argument on the edge.

GenKill is the assoc Label -> Gen-Kill for each block: Gen is the ordset of temps read before they are written in it, and Kill the ordset of temps written (phi destinations included).

EdgeUses is the assoc (Pred-Succ) -> ordset of the temps that the phis of Succ read on the edge from Pred, for the edges that have any.

Names is the ordset of temp names among Values.