Module ssa 

SSA construction via Cytron’s algorithm (DF-1).

Compute immediate dominators for a diamond CFG:

use std::collections::{HashMap, HashSet};
use weir::ssa::{try_compute_dominators, Block, Cfg};

let mut blocks = HashMap::new();
for (id, preds, succs) in [
    (0u32, vec![], vec![1, 2]),
    (1, vec![0], vec![3]),
    (2, vec![0], vec![3]),
    (3, vec![1, 2], vec![]),
] {
    blocks.insert(id, Block { id, preds, succs, defs: HashSet::new(), uses: HashSet::new() });
}

let idoms = try_compute_dominators(&Cfg { entry: 0, blocks }).unwrap();
assert_eq!(idoms[&1], 0);
assert_eq!(idoms[&2], 0);
assert_eq!(idoms[&3], 0);

DF-1 - SSA construction (Cytron dominance-frontier phi insertion + variable renaming).

Two complementary surfaces:

1. Reference Cytron / Cooper-Harvey-Kennedy implementation (compute_dominators, compute_dominance_frontiers, place_phi_nodes, rename_variables) for parity evidence and host-side AST integration while the full SSA builder migrates to resident graph programs. This surface is not the production dispatch path for dataflow propagation.

2. GPU-emitting [ssa_phi_placement_step] that lowers Cytron’s phi-placement worklist to a single csr_forward_traverse pass over the dominance-frontier graph. The surge-side fixpoint driver iterates this step to convergence - same shape as DF-2 reaching-defs and DF-3 points-to (consistent convergence-contract). Renaming is a remaining migration target: callers should treat the functions below as reference/oracle machinery until resident dominator-tree traversal lands.

Op id and soundness

Op id: weir::ssa. Soundness: Exact - Cytron places phi nodes at the exact set of join points reachable from a def via dominance-frontier edges; no over-approximation.

Structs

Block

Basic block summary used by the SSA builder.

Cfg

Control-flow graph consumed by the SSA builder.

Ssa

Marker type for the SSA construction dataflow primitive.

SsaForm

SSA construction result: phi placement, renamed uses, and def-use chains.

Constants

DOMINATOR_GPU_THRESHOLD

Tunable threshold: CFGs with more than this many blocks are routed to the GPU dominator-tree primitive when a backend is available.

Functions

compute_dominators

Compute immediate dominators for every reachable block.

ssa_phi_placement_step

Build one dominance-frontier propagation step for SSA phi placement.

try_compute_dominance_frontiers

Compute dominance frontiers with fallible allocation errors.

try_compute_dominators

Compute immediate dominators for every reachable block with fallible allocation errors.

try_compute_dominators_cpu

Reference CPU immediate-dominator construction (Cooper–Harvey–Kennedy iterative fixpoint). Used for CFGs at or below the GPU threshold and as a fallback when no backend is available.

try_place_phi_nodes

Place phi nodes for variables with definitions reaching dominance frontiers with an explicit allocator failure contract.

try_rename_variables

Rename variables into SSA versions and build def-use chains with fallible allocation and checked synthetic node-id arithmetic.