ssa_impls/
cfg.rs

1use alloc::{collections::{BTreeMap, BTreeSet}, vec::Vec};
2use alloc::vec;
3use cfg_traits::{Block, Func, Target, Term};
4
5pub fn calculate_postorder<
6    F: Func<Block: Ord + Clone>,
7    SuccFn: FnMut(F::Block) -> Vec<F::Block>,
8>(
9    entry: F::Block,
10    mut succ_blocks: SuccFn,
11) -> Vec<F::Block> {
12    let mut ret = vec![];
13
14    // State: visited-block map, and explicit DFS stack.
15    let mut visited: BTreeSet<F::Block> = BTreeSet::new();
16
17    #[derive(Debug)]
18    struct State<F: Func> {
19        block: F::Block,
20        succs: Vec<F::Block>,
21        next_succ: usize,
22    }
23    let mut stack: Vec<State<F>> = vec![];
24
25    visited.insert(entry.clone());
26    stack.push(State {
27        block: entry.clone(),
28        succs: succ_blocks(entry.clone()),
29        next_succ: 0,
30    });
31
32    while let Some(ref mut state) = stack.last_mut() {
33        // log::trace!("postorder: TOS is {:?}", state);
34        // Perform one action: push to new succ, skip an already-visited succ, or pop.
35        if state.next_succ < state.succs.len() {
36            let succ = state.succs[state.next_succ].clone();
37            // log::trace!(" -> succ {}", succ);
38            state.next_succ += 1;
39            if !visited.contains(&succ) {
40                // log::trace!(" -> visiting");
41                visited.insert(succ.clone());
42                stack.push(State {
43                    block: succ.clone(),
44                    succs: succ_blocks(succ.clone()),
45                    next_succ: 0,
46                });
47            }
48        } else {
49            // log::trace!("retreating from {}", state.block);
50            ret.push(state.block.clone());
51            stack.pop();
52        }
53    }
54
55    ret
56}
57pub fn postorder<F: Func<Block: Ord + Clone>>(f: &F) -> Vec<F::Block> {
58    return calculate_postorder::<F, _>(f.entry(), |a| {
59        f.blocks()[a].term().targets().map(|a| a.block()).collect()
60    });
61}
ssa_impls/cfg.rs

ssa_impls/
cfg.rs
