circomspect_program_structure/static_single_assignment/
traits.rs

1use log::trace;
2use std::collections::HashSet;
3use std::hash::Hash;
4
5use super::errors::SSAResult;
6
7pub trait SSAConfig: Sized {
8    /// The type used to track variable versions.
9    type Version;
10
11    /// The type of a variable.
12    type Variable: PartialEq + Eq + Hash + Clone;
13
14    /// An environment type used to track version across the CFG.
15    type Environment: SSAEnvironment;
16
17    /// The type of a statement.
18    type Statement: SSAStatement<Self>;
19
20    /// The type of a basic block.
21    type BasicBlock: SSABasicBlock<Self> + DirectedGraphNode;
22}
23
24/// An environment used to track variable versions across a CFG.
25pub trait SSAEnvironment {
26    /// Enter variable scope.
27    fn add_variable_scope(&mut self);
28
29    /// Leave variable scope.
30    fn remove_variable_scope(&mut self);
31}
32
33/// A basic block containing a (possibly empty) list of statements.
34pub trait SSABasicBlock<Cfg: SSAConfig>: DirectedGraphNode {
35    /// Add the given statement to the front of the basic block.
36    fn prepend_statement(&mut self, stmt: Cfg::Statement);
37
38    /// Returns an iterator over the statements of the basic block.
39    ///
40    /// Note: We have to use dynamic dispatch here because returning `impl
41    /// Trait` from trait methods is not a thing yet. For details, see
42    /// rust-lang.github.io/impl-trait-initiative/RFCs/rpit-in-traits.html)
43    fn statements<'a>(&'a self) -> Box<dyn Iterator<Item = &'a Cfg::Statement> + 'a>;
44
45    /// Returns an iterator over mutable references to the statements of the
46    /// basic block.
47    ///
48    /// Note: We have to use dynamic dispatch here because returning `impl
49    /// Trait` from trait methods is not a thing yet. For details, see
50    /// rust-lang.github.io/impl-trait-initiative/RFCs/rpit-in-traits.html)
51    fn statements_mut<'a>(&'a mut self) -> Box<dyn Iterator<Item = &'a mut Cfg::Statement> + 'a>;
52
53    /// Returns the set of variables written by the basic block.
54    fn variables_written(&self) -> HashSet<Cfg::Variable> {
55        self.statements().fold(HashSet::new(), |mut vars, stmt| {
56            vars.extend(stmt.variables_written());
57            vars
58        })
59    }
60
61    /// Returns true if the basic block has a phi statement for the given
62    /// variable.
63    fn has_phi_statement(&self, var: &Cfg::Variable) -> bool {
64        self.statements().any(|stmt| stmt.is_phi_statement_for(var))
65    }
66
67    /// Inserts a new phi statement for the given variable at the top of the basic
68    /// block.
69    fn insert_phi_statement(&mut self, var: &Cfg::Variable, env: &Cfg::Environment) {
70        self.prepend_statement(SSAStatement::new_phi_statement(var, env));
71    }
72
73    /// Updates the RHS of each phi statement in the basic block with the SSA
74    /// variable versions from the given environment.
75    fn update_phi_statements(&mut self, env: &Cfg::Environment) {
76        trace!("updating phi expression arguments in block {}", self.index());
77        for stmt in self.statements_mut() {
78            if stmt.is_phi_statement() {
79                stmt.ensure_phi_argument(env);
80            } else {
81                // Since phi statements proceed all other statements we are done
82                // here.
83                break;
84            }
85        }
86    }
87
88    /// Updates each variable to the corresponding SSA variable, in each
89    /// statement in the basic block.
90    fn insert_ssa_variables(&mut self, env: &mut Cfg::Environment) -> SSAResult<()> {
91        trace!("inserting SSA variables in block {}", self.index());
92        for stmt in self.statements_mut() {
93            stmt.insert_ssa_variables(env)?;
94        }
95        Ok(())
96    }
97}
98
99/// A statement in the language.
100pub trait SSAStatement<Cfg: SSAConfig>: Clone {
101    /// Returns the set of variables written by statement.
102    fn variables_written(&self) -> HashSet<Cfg::Variable>;
103
104    /// Returns a new phi statement (with empty RHS) for the given variable.
105    fn new_phi_statement(name: &Cfg::Variable, env: &Cfg::Environment) -> Self;
106
107    /// Returns true iff the statement is a phi statement.
108    fn is_phi_statement(&self) -> bool;
109
110    /// Returns true iff the statement is a phi statement for the given variable.
111    fn is_phi_statement_for(&self, var: &Cfg::Variable) -> bool;
112
113    /// Ensure that the phi expression argument list of a phi statement contains the
114    /// current version of the variable, according to the given environment.
115    ///
116    /// Panics if the statement is not a phi statement.
117    fn ensure_phi_argument(&mut self, env: &Cfg::Environment);
118
119    /// Replace each variable occurring in the statement by the corresponding
120    /// versioned SSA variable.
121    fn insert_ssa_variables(&mut self, env: &mut Cfg::Environment) -> SSAResult<()>;
122}
123
124pub type Index = usize;
125pub type IndexSet = HashSet<Index>;
126
127/// This trait is used to make graph algorithms (like dominator tree and dominator
128/// frontier generation) generic over the graph node type for unit testing purposes.
129pub trait DirectedGraphNode {
130    fn index(&self) -> Index;
131
132    fn predecessors(&self) -> &IndexSet;
133
134    fn successors(&self) -> &IndexSet;
135}
circomspect_program_structure/static_single_assignment/traits.rs

circomspect_program_structure/static_single_assignment/
traits.rs
