circomspect_program_structure/static_single_assignment/
mod.rs

1//! This module implements a generic conversion into single-static assignment
2//! form.
3pub mod dominator_tree;
4pub mod errors;
5pub mod traits;
6
7use log::trace;
8
9use dominator_tree::DominatorTree;
10use errors::SSAResult;
11use traits::*;
12
13/// Insert a dummy phi statement in block `j`, for each variable written in block
14/// `i`, if `j` is in the dominance frontier of `i`.
15pub fn insert_phi_statements<Cfg: SSAConfig>(
16    basic_blocks: &mut [Cfg::BasicBlock],
17    dominator_tree: &DominatorTree<Cfg::BasicBlock>,
18    env: &mut Cfg::Environment,
19) {
20    // Insert phi statements at the dominance frontier of each block.
21    let mut work_list: Vec<Index> = (0..basic_blocks.len()).collect();
22    while let Some(current_index) = work_list.pop() {
23        let variables_written = {
24            let current_block = &basic_blocks[current_index];
25            current_block.variables_written().clone()
26        };
27        if variables_written.is_empty() {
28            trace!("basic block {current_index} does not write any variables");
29            continue;
30        }
31        trace!(
32            "dominance frontier for block {current_index} is {:?}",
33            dominator_tree.get_dominance_frontier(current_index)
34        );
35        for frontier_index in dominator_tree.get_dominance_frontier(current_index) {
36            let frontier_block = &mut basic_blocks[frontier_index];
37            for var in &variables_written {
38                if !frontier_block.has_phi_statement(var) {
39                    // If a phi statement was added to the block we need to
40                    // re-add the block to the work list.
41                    frontier_block.insert_phi_statement(var, env);
42                    work_list.push(frontier_index);
43                }
44            }
45        }
46    }
47}
48
49/// Traverses the dominator tree in pre-order and for each block, the function
50///
51/// 1. Renames all variables to SSA form, keeping track of the current
52///    version of each variable.
53/// 2. Updates phi expression arguments in each successor of the current
54///    block, adding the correct versioned arguments to the expression.
55pub fn insert_ssa_variables<Cfg: SSAConfig>(
56    basic_blocks: &mut [Cfg::BasicBlock],
57    dominator_tree: &DominatorTree<Cfg::BasicBlock>,
58    env: &mut Cfg::Environment,
59) -> SSAResult<()> {
60    insert_ssa_variables_impl::<Cfg>(0, basic_blocks, dominator_tree, env)?;
61    Ok(())
62}
63
64fn insert_ssa_variables_impl<Cfg: SSAConfig>(
65    current_index: Index,
66    basic_blocks: &mut [Cfg::BasicBlock],
67    dominator_tree: &DominatorTree<Cfg::BasicBlock>,
68    env: &mut Cfg::Environment,
69) -> SSAResult<()> {
70    // 1. Update variables in current block.
71    let successors = {
72        let current_block =
73            basic_blocks.get_mut(current_index).expect("invalid block index during SSA generation");
74        current_block.insert_ssa_variables(env)?;
75        current_block.successors().clone()
76    };
77    // 2. Update phi statements in successor blocks.
78    for successor_index in successors {
79        let successor_block = basic_blocks
80            .get_mut(successor_index)
81            .expect("invalid block index during SSA generation");
82        successor_block.update_phi_statements(env);
83    }
84    // 3. Update dominator tree successors recursively.
85    for successor_index in dominator_tree.get_dominator_successors(current_index) {
86        env.add_variable_scope();
87        insert_ssa_variables_impl::<Cfg>(successor_index, basic_blocks, dominator_tree, env)?;
88        env.remove_variable_scope();
89    }
90    Ok(())
91}
circomspect_program_structure/static_single_assignment/mod.rs

circomspect_program_structure/static_single_assignment/
mod.rs
