celox_analysis/
ssa.rs

1//! Sparse pruned SSA construction over caller-defined variable identities.
2
3use std::collections::{BTreeMap, BTreeSet, VecDeque};
4use std::fmt;
5
6use crate::cfg::{ControlFlowGraph, ForwardControlFlowGraph};
7
8/// Minimal CFG view required by SSA construction.
9///
10/// Clients that already own dominance information can implement this view
11/// without rebuilding postdominators, control dependence, SCCs, or loops.
12pub trait SsaCfg {
13    type FrontierIter<'a>: Iterator<Item = usize>
14    where
15        Self: 'a;
16
17    fn root(&self) -> usize;
18    fn predecessors(&self) -> &[Vec<usize>];
19    fn successors(&self) -> &[Vec<usize>];
20    fn dominator_children(&self) -> &[Vec<usize>];
21    fn dominance_frontier_len(&self) -> usize;
22    fn dominance_frontier(&self, block: usize) -> Self::FrontierIter<'_>;
23}
24
25impl SsaCfg for ControlFlowGraph {
26    type FrontierIter<'a> = std::iter::Copied<std::slice::Iter<'a, usize>>;
27
28    fn root(&self) -> usize {
29        self.root
30    }
31
32    fn predecessors(&self) -> &[Vec<usize>] {
33        &self.predecessors
34    }
35
36    fn successors(&self) -> &[Vec<usize>] {
37        &self.successors
38    }
39
40    fn dominator_children(&self) -> &[Vec<usize>] {
41        &self.dominators.children
42    }
43
44    fn dominance_frontier_len(&self) -> usize {
45        self.dominance_frontier.len()
46    }
47
48    fn dominance_frontier(&self, block: usize) -> Self::FrontierIter<'_> {
49        self.dominance_frontier[block].iter().copied()
50    }
51}
52
53impl SsaCfg for ForwardControlFlowGraph {
54    type FrontierIter<'a> = std::iter::Copied<std::slice::Iter<'a, usize>>;
55
56    fn root(&self) -> usize {
57        self.root
58    }
59
60    fn predecessors(&self) -> &[Vec<usize>] {
61        &self.predecessors
62    }
63
64    fn successors(&self) -> &[Vec<usize>] {
65        &self.successors
66    }
67
68    fn dominator_children(&self) -> &[Vec<usize>] {
69        &self.dominators.children
70    }
71
72    fn dominance_frontier_len(&self) -> usize {
73        self.dominance_frontier.len()
74    }
75
76    fn dominance_frontier(&self, block: usize) -> Self::FrontierIter<'_> {
77        self.dominance_frontier[block].iter().copied()
78    }
79}
80
81#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
82pub enum Version<V, D> {
83    Entry(V),
84    Definition { variable: V, definition: D },
85    Phi { variable: V, block: usize },
86}
87
88#[derive(Debug, Clone, Copy, PartialEq, Eq)]
89pub enum Event<V, D, U> {
90    Use { variable: V, usage: U },
91    Definition { variable: V, definition: D },
92}
93
94#[derive(Debug, Clone, PartialEq, Eq)]
95pub struct Phi<V, D> {
96    pub variable: V,
97    pub block: usize,
98    pub version: Version<V, D>,
99    pub inputs: Vec<(usize, Version<V, D>)>,
100}
101
102#[derive(Debug, Clone, PartialEq, Eq)]
103pub struct SparseSsa<V, D, U> {
104    pub phis: Vec<Phi<V, D>>,
105    pub phis_by_block: Vec<Vec<usize>>,
106    pub uses: BTreeMap<U, Version<V, D>>,
107}
108
109#[derive(Debug, Clone, PartialEq, Eq)]
110pub struct SsaError {
111    pub rule: &'static str,
112    pub block: Option<usize>,
113    pub message: String,
114}
115
116impl SsaError {
117    fn new(rule: &'static str, block: Option<usize>, message: impl Into<String>) -> Self {
118        Self {
119            rule,
120            block,
121            message: message.into(),
122        }
123    }
124}
125
126impl fmt::Display for SsaError {
127    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
128        write!(formatter, "{}", self.rule)?;
129        if let Some(block) = self.block {
130            write!(formatter, " at block {block}")?;
131        }
132        write!(formatter, ": {}", self.message)
133    }
134}
135
136impl std::error::Error for SsaError {}
137
138/// Construct pruned SSA from events already ordered within each dense block.
139pub fn build<V, D, U>(
140    cfg: &impl SsaCfg,
141    events: &[Vec<Event<V, D, U>>],
142) -> Result<SparseSsa<V, D, U>, SsaError>
143where
144    V: Copy + Ord,
145    D: Copy + Ord,
146    U: Copy + Ord,
147{
148    let blocks = cfg.successors().len();
149    if events.len() != blocks
150        || cfg.predecessors().len() != blocks
151        || cfg.dominator_children().len() != blocks
152        || cfg.dominance_frontier_len() != blocks
153    {
154        return Err(SsaError::new(
155            "SSA.MODEL_SHAPE",
156            None,
157            "CFG and event tables do not cover the same block domain",
158        ));
159    }
160
161    let mut definitions = BTreeMap::<V, BTreeSet<usize>>::new();
162    let mut definition_ids = BTreeSet::<(V, D)>::new();
163    let mut upward_uses = BTreeSet::<(V, usize)>::new();
164    let mut usage_ids = BTreeSet::<U>::new();
165    for (block, block_events) in events.iter().enumerate() {
166        let mut locally_defined = BTreeSet::<V>::new();
167        for event in block_events {
168            match *event {
169                Event::Use { variable, usage } => {
170                    if !usage_ids.insert(usage) {
171                        return Err(SsaError::new(
172                            "SSA.USE_IDENTITY",
173                            Some(block),
174                            "one use identity occurs more than once",
175                        ));
176                    }
177                    if !locally_defined.contains(&variable) {
178                        upward_uses.insert((variable, block));
179                    }
180                }
181                Event::Definition {
182                    variable,
183                    definition,
184                } => {
185                    if !definition_ids.insert((variable, definition)) {
186                        return Err(SsaError::new(
187                            "SSA.DEFINITION_IDENTITY",
188                            Some(block),
189                            "one variable-definition identity occurs more than once",
190                        ));
191                    }
192                    locally_defined.insert(variable);
193                    definitions.entry(variable).or_default().insert(block);
194                }
195            }
196        }
197    }
198
199    let definition_pairs = definitions
200        .iter()
201        .flat_map(|(&variable, blocks)| blocks.iter().map(move |&block| (variable, block)))
202        .collect::<BTreeSet<_>>();
203    let mut live_in = upward_uses.clone();
204    let mut live_work = upward_uses.into_iter().collect::<VecDeque<_>>();
205    while let Some((variable, block)) = live_work.pop_front() {
206        for &predecessor in &cfg.predecessors()[block] {
207            let pair = (variable, predecessor);
208            if !definition_pairs.contains(&pair) && live_in.insert(pair) {
209                live_work.push_back(pair);
210            }
211        }
212    }
213
214    let mut phi_pairs = BTreeSet::<(usize, V)>::new();
215    for (&variable, original_definitions) in &definitions {
216        let mut queued = original_definitions.clone();
217        let mut work = original_definitions
218            .iter()
219            .copied()
220            .collect::<VecDeque<_>>();
221        while let Some(definition) = work.pop_front() {
222            for frontier in cfg.dominance_frontier(definition) {
223                if !live_in.contains(&(variable, frontier))
224                    || !phi_pairs.insert((frontier, variable))
225                {
226                    continue;
227                }
228                if queued.insert(frontier) {
229                    work.push_back(frontier);
230                }
231            }
232        }
233    }
234
235    let mut phis = Vec::<Phi<V, D>>::with_capacity(phi_pairs.len());
236    let mut phis_by_block = vec![Vec::<usize>::new(); blocks];
237    for (block, variable) in phi_pairs {
238        let phi = phis.len();
239        phis.push(Phi {
240            variable,
241            block,
242            version: Version::Phi { variable, block },
243            inputs: Vec::with_capacity(cfg.predecessors()[block].len()),
244        });
245        phis_by_block[block].push(phi);
246    }
247
248    enum Action<V, D> {
249        Enter(usize),
250        Exit(Vec<(V, Option<Version<V, D>>)>),
251    }
252    let mut current = BTreeMap::<V, Version<V, D>>::new();
253    let mut uses = BTreeMap::<U, Version<V, D>>::new();
254    let mut actions = vec![Action::Enter(cfg.root())];
255    while let Some(action) = actions.pop() {
256        let block = match action {
257            Action::Exit(changes) => {
258                for (variable, previous) in changes.into_iter().rev() {
259                    if let Some(previous) = previous {
260                        current.insert(variable, previous);
261                    } else {
262                        current.remove(&variable);
263                    }
264                }
265                continue;
266            }
267            Action::Enter(block) => block,
268        };
269        let mut changes = Vec::new();
270        for &phi in &phis_by_block[block] {
271            let variable = phis[phi].variable;
272            changes.push((variable, current.insert(variable, phis[phi].version)));
273        }
274        for event in &events[block] {
275            match *event {
276                Event::Use { variable, usage } => {
277                    let version = current
278                        .get(&variable)
279                        .copied()
280                        .unwrap_or(Version::Entry(variable));
281                    if uses.insert(usage, version).is_some() {
282                        return Err(SsaError::new(
283                            "SSA.USE_RENAME",
284                            Some(block),
285                            "dominator rename visited one use more than once",
286                        ));
287                    }
288                }
289                Event::Definition {
290                    variable,
291                    definition,
292                } => {
293                    let version = Version::Definition {
294                        variable,
295                        definition,
296                    };
297                    changes.push((variable, current.insert(variable, version)));
298                }
299            }
300        }
301        for &successor in &cfg.successors()[block] {
302            for &phi in &phis_by_block[successor] {
303                let variable = phis[phi].variable;
304                let version = current
305                    .get(&variable)
306                    .copied()
307                    .unwrap_or(Version::Entry(variable));
308                phis[phi].inputs.push((block, version));
309            }
310        }
311        actions.push(Action::Exit(changes));
312        actions.extend(
313            cfg.dominator_children()[block]
314                .iter()
315                .rev()
316                .copied()
317                .map(Action::Enter),
318        );
319    }
320
321    if uses.len() != usage_ids.len() {
322        return Err(SsaError::new(
323            "SSA.USE_COVERAGE",
324            None,
325            "dominator rename did not visit every use",
326        ));
327    }
328    for phi in &mut phis {
329        phi.inputs
330            .sort_unstable_by_key(|(predecessor, _)| *predecessor);
331        if phi.inputs.len() != cfg.predecessors()[phi.block].len()
332            || phi
333                .inputs
334                .iter()
335                .zip(&cfg.predecessors()[phi.block])
336                .any(|((actual, _), expected)| actual != expected)
337        {
338            return Err(SsaError::new(
339                "SSA.PHI_INPUTS",
340                Some(phi.block),
341                "phi inputs do not cover every CFG predecessor exactly once",
342            ));
343        }
344    }
345
346    Ok(SparseSsa {
347        phis,
348        phis_by_block,
349        uses,
350    })
351}
352
353#[cfg(test)]
354mod tests {
355    use super::*;
356
357    #[test]
358    fn branch_definitions_create_one_live_join_phi() {
359        let cfg = ControlFlowGraph::analyze(vec![vec![1, 2], vec![3], vec![3], vec![]], 0).unwrap();
360        let events = vec![
361            vec![],
362            vec![Event::Definition {
363                variable: 7,
364                definition: 10,
365            }],
366            vec![Event::Definition {
367                variable: 7,
368                definition: 20,
369            }],
370            vec![Event::Use {
371                variable: 7,
372                usage: 30,
373            }],
374        ];
375
376        let ssa = build(&cfg, &events).unwrap();
377
378        assert_eq!(ssa.phis.len(), 1);
379        assert_eq!(ssa.phis[0].block, 3);
380        assert_eq!(ssa.phis[0].inputs.len(), 2);
381        assert_eq!(
382            ssa.uses[&30],
383            Version::Phi {
384                variable: 7,
385                block: 3
386            }
387        );
388    }
389
390    #[test]
391    fn dead_join_does_not_receive_a_phi() {
392        let cfg = ControlFlowGraph::analyze(vec![vec![1, 2], vec![3], vec![3], vec![]], 0).unwrap();
393        let events = vec![
394            vec![],
395            vec![Event::Definition {
396                variable: 7,
397                definition: 10,
398            }],
399            vec![Event::Definition {
400                variable: 7,
401                definition: 20,
402            }],
403            vec![],
404        ];
405
406        let ssa = build::<_, _, usize>(&cfg, &events).unwrap();
407
408        assert!(ssa.phis.is_empty());
409    }
410
411    #[test]
412    fn loop_use_observes_header_phi() {
413        let cfg = ControlFlowGraph::analyze(vec![vec![1], vec![2, 3], vec![1], vec![]], 0).unwrap();
414        let events = vec![
415            vec![Event::Definition {
416                variable: 1,
417                definition: 0,
418            }],
419            vec![Event::Use {
420                variable: 1,
421                usage: 10,
422            }],
423            vec![Event::Definition {
424                variable: 1,
425                definition: 20,
426            }],
427            vec![],
428        ];
429
430        let ssa = build(&cfg, &events).unwrap();
431
432        assert_eq!(
433            ssa.uses[&10],
434            Version::Phi {
435                variable: 1,
436                block: 1
437            }
438        );
439        assert_eq!(ssa.phis[0].inputs.len(), 2);
440    }
441
442    #[test]
443    fn same_block_uses_observe_event_order() {
444        let cfg = ControlFlowGraph::analyze(vec![vec![]], 0).unwrap();
445        let events = vec![vec![
446            Event::Use {
447                variable: 1,
448                usage: 1,
449            },
450            Event::Definition {
451                variable: 1,
452                definition: 2,
453            },
454            Event::Use {
455                variable: 1,
456                usage: 3,
457            },
458        ]];
459
460        let ssa = build(&cfg, &events).unwrap();
461
462        assert_eq!(ssa.uses[&1], Version::Entry(1));
463        assert_eq!(
464            ssa.uses[&3],
465            Version::Definition {
466                variable: 1,
467                definition: 2
468            }
469        );
470    }
471}
celox_analysis/ssa.rs

celox_analysis/
ssa.rs
