Function iterated_dominance_frontiers 

pub fn iterated_dominance_frontiers(
    graph: &SqliteGraph,
    dom_result: &DominatorResult,
    definition_nodes: &AHashSet<i64>,
) -> Result<IteratedDominanceFrontierResult, SqliteGraphError>

Computes iterated dominance frontier for SSA φ-placement.

The iterated dominance frontier finds all nodes that need φ-functions for a given set of definition nodes. This is computed by fixed-point iteration: IDF(S) = DF(S) ∪ DF(DF(S)) ∪ DF(DF(DF(S))) ∪ ... until convergence.

Arguments

• graph - The control flow graph to analyze
• dom_result - Pre-computed dominator result (from dominators)
• definition_nodes - Set of nodes where variables are defined

Returns

IteratedDominanceFrontierResult containing φ-node placement set and iteration count.

Algorithm Steps

1. Initialize: Start with definition nodes as current set
2. Iterate: Compute DF of current set, add to result, repeat until no change
3. Fixed-point detection: Stop when DF(current) ⊆ result (no new nodes)
4. Return result: All nodes needing φ-nodes

Complexity

• Time: O(N × iterations) where iterations is typically small (2-4)
• Space: O(N) for result set

Error Handling

• Has iteration limit (100) to prevent non-termination on pathological inputs
• Returns error if iteration limit is reached (indicates algorithm bug or malformed CFG)

Example

use ahash::AHashSet;

// Variables x and y are defined at nodes 1 and 3
let mut definitions = AHashSet::new();
definitions.insert(1);
definitions.insert(3);

let idf_result = iterated_dominance_frontiers(&graph, &dom_result, &definitions)?;

// Place φ-nodes at all nodes in idf_result.phi_nodes
for &node in &idf_result.phi_nodes {
    println!("Place φ-node at node {}", node);
}

References

• Cytron, Ron, et al. “Efficiently computing static single assignment form and the control dependence graph.” ACM TOPLAS, 1991.