///|
// The graph is validated and entry_reachable has one slot per original node.
// Full analysis already owns this reachability result; standalone queries need
// only a traversal, not the forward dominator tree or any structural analysis.
fn compute_postdominance(
graph : Graph,
entry_reachable : Array[Bool],
) -> Dominance {
let n = graph.nodes.length()
let reverse : Array[Array[Int32]] = Array::makei(n + 1, _ => [])
let reverse_pred : Array[Array[Int32]] = Array::makei(n + 1, _ => [])
for (from, to) in graph.edges {
if entry_reachable[from] && entry_reachable[to] {
reverse[to].push(from)
reverse_pred[from].push(to)
}
}
for exit in graph.exits {
if entry_reachable[exit] {
reverse[n].push(exit)
reverse_pred[exit].push(n)
}
}
compute_dominance(reverse, reverse_pred, n)
}
///|
/// Compute postdominance without forward dominators, control dependencies,
/// loops or SCCs. Scope is finite paths from entry reaching declared terminal
/// exits, exactly as analyze(graph).post; this is not a termination proof.
/// The root is the virtual exit at graph.nodes.length(), and all arrays have
/// one extra slot for it. With no reachable declared exit only that root is
/// reachable. Returned arrays are independently owned.
pub fn postdominators(input : Graph) -> Dominance raise GraphError {
let graph = snapshot_graph(input)
let n = graph.nodes.length()
let succ : Array[Array[Int32]] = Array::makei(n, _ => [])
for (from, to) in graph.edges {
succ[from].push(to)
}
let reachable = Array::make(n, false)
let work = [graph.entry]
reachable[graph.entry] = true
let mut cursor = 0
while cursor < work.length() {
let node = work[cursor]
cursor += 1
for next in succ[node] {
if !reachable[next] {
reachable[next] = true
work.push(next)
}
}
}
compute_postdominance(graph, reachable)
}