sway_ir/analysis/
dominator.rs

1use crate::{
2    block::Block, AnalysisResult, AnalysisResultT, AnalysisResults, BranchToWithArgs, Context,
3    Function, IrError, Pass, PassMutability, ScopedPass,
4};
5use indexmap::IndexSet;
6/// Dominator tree and related algorithms.
7/// The algorithms implemented here are from the paper
8// "A Simple, Fast Dominance Algorithm" -- Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy.
9use rustc_hash::{FxHashMap, FxHashSet};
10use std::fmt::Write;
11use sway_types::{FxIndexMap, FxIndexSet};
12
13/// Represents a node in the dominator tree.
14pub struct DomTreeNode {
15    /// The immediate dominator of self.
16    pub parent: Option<Block>,
17    /// The blocks that self immediately dominates.
18    pub children: Vec<Block>,
19}
20
21impl DomTreeNode {
22    pub fn new(parent: Option<Block>) -> DomTreeNode {
23        DomTreeNode {
24            parent,
25            children: vec![],
26        }
27    }
28}
29
30// The dominator tree is represented by mapping each Block to its DomTreeNode.
31#[derive(Default)]
32pub struct DomTree(FxIndexMap<Block, DomTreeNode>);
33impl AnalysisResultT for DomTree {}
34
35// Dominance frontier sets.
36pub type DomFronts = FxIndexMap<Block, FxIndexSet<Block>>;
37impl AnalysisResultT for DomFronts {}
38
39/// Post ordering of blocks in the CFG.
40pub struct PostOrder {
41    pub block_to_po: FxHashMap<Block, usize>,
42    pub po_to_block: Vec<Block>,
43}
44impl AnalysisResultT for PostOrder {}
45
46pub const POSTORDER_NAME: &str = "postorder";
47
48pub fn create_postorder_pass() -> Pass {
49    Pass {
50        name: POSTORDER_NAME,
51        descr: "Postorder traversal of the control-flow graph",
52        deps: vec![],
53        runner: ScopedPass::FunctionPass(PassMutability::Analysis(compute_post_order_pass)),
54    }
55}
56
57pub fn compute_post_order_pass(
58    context: &Context,
59    _: &AnalysisResults,
60    function: Function,
61) -> Result<AnalysisResult, IrError> {
62    Ok(Box::new(compute_post_order(context, &function)))
63}
64
65/// Compute the post-order traversal of the CFG.
66/// Beware: Unreachable blocks aren't part of the result.
67pub fn compute_post_order(context: &Context, function: &Function) -> PostOrder {
68    let mut res = PostOrder {
69        block_to_po: FxHashMap::default(),
70        po_to_block: Vec::default(),
71    };
72    let entry = function.get_entry_block(context);
73
74    let mut counter = 0;
75    let mut on_stack = FxHashSet::<Block>::default();
76    fn post_order(
77        context: &Context,
78        n: Block,
79        res: &mut PostOrder,
80        on_stack: &mut FxHashSet<Block>,
81        counter: &mut usize,
82    ) {
83        if on_stack.contains(&n) {
84            return;
85        }
86        on_stack.insert(n);
87        for BranchToWithArgs { block: n_succ, .. } in n.successors(context) {
88            post_order(context, n_succ, res, on_stack, counter);
89        }
90        res.block_to_po.insert(n, *counter);
91        res.po_to_block.push(n);
92        *counter += 1;
93    }
94    post_order(context, entry, &mut res, &mut on_stack, &mut counter);
95
96    // We could assert the whole thing, but it'd be expensive.
97    assert!(res.po_to_block.last().unwrap() == &entry);
98
99    res
100}
101
102pub const DOMINATORS_NAME: &str = "dominators";
103
104pub fn create_dominators_pass() -> Pass {
105    Pass {
106        name: DOMINATORS_NAME,
107        descr: "Dominator tree computation",
108        deps: vec![POSTORDER_NAME],
109        runner: ScopedPass::FunctionPass(PassMutability::Analysis(compute_dom_tree)),
110    }
111}
112
113/// Compute the dominator tree for the CFG.
114fn compute_dom_tree(
115    context: &Context,
116    analyses: &AnalysisResults,
117    function: Function,
118) -> Result<AnalysisResult, IrError> {
119    let po: &PostOrder = analyses.get_analysis_result(function);
120    let mut dom_tree = DomTree::default();
121    let entry = function.get_entry_block(context);
122
123    // This is to make the algorithm happy. It'll be changed to None later.
124    dom_tree.0.insert(entry, DomTreeNode::new(Some(entry)));
125    // initialize the dominators tree. This allows us to do dom_tree[b] fearlessly.
126    // Note that we just previously initialized "entry", so we skip that here.
127    for b in po.po_to_block.iter().take(po.po_to_block.len() - 1) {
128        dom_tree.0.insert(*b, DomTreeNode::new(None));
129    }
130    let mut changed = true;
131
132    while changed {
133        changed = false;
134        // For all nodes, b, in reverse postorder (except start node)
135        for b in po.po_to_block.iter().rev().skip(1) {
136            // new_idom <- first (processed) predecessor of b (pick one)
137            let mut new_idom = b
138                .pred_iter(context)
139                .find(|p| {
140                    // "p" may not be reachable, and hence not in dom_tree.
141                    po.block_to_po
142                        .get(p)
143                        .is_some_and(|p_po| *p_po > po.block_to_po[b])
144                })
145                .cloned()
146                .unwrap();
147            let picked_pred = new_idom;
148            // for all other (reachable) predecessors, p, of b:
149            for p in b
150                .pred_iter(context)
151                .filter(|p| **p != picked_pred && po.block_to_po.contains_key(p))
152            {
153                if dom_tree.0[p].parent.is_some() {
154                    // if doms[p] already calculated
155                    new_idom = intersect(po, &dom_tree, *p, new_idom);
156                }
157            }
158            let b_node = dom_tree.0.get_mut(b).unwrap();
159            match b_node.parent {
160                Some(idom) if idom == new_idom => {}
161                _ => {
162                    b_node.parent = Some(new_idom);
163                    changed = true;
164                }
165            }
166        }
167    }
168
169    // Find the nearest common dominator of two blocks,
170    // using the partially computed dominator tree.
171    fn intersect(
172        po: &PostOrder,
173        dom_tree: &DomTree,
174        mut finger1: Block,
175        mut finger2: Block,
176    ) -> Block {
177        while finger1 != finger2 {
178            while po.block_to_po[&finger1] < po.block_to_po[&finger2] {
179                finger1 = dom_tree.0[&finger1].parent.unwrap();
180            }
181            while po.block_to_po[&finger2] < po.block_to_po[&finger1] {
182                finger2 = dom_tree.0[&finger2].parent.unwrap();
183            }
184        }
185        finger1
186    }
187
188    // Fix the root.
189    dom_tree.0.get_mut(&entry).unwrap().parent = None;
190    // Build the children.
191    let child_parent: Vec<_> = dom_tree
192        .0
193        .iter()
194        .filter_map(|(n, n_node)| n_node.parent.map(|n_parent| (*n, n_parent)))
195        .collect();
196    for (child, parent) in child_parent {
197        dom_tree.0.get_mut(&parent).unwrap().children.push(child);
198    }
199
200    Ok(Box::new(dom_tree))
201}
202
203impl DomTree {
204    /// Does `dominator` dominate `dominatee`?
205    pub fn dominates(&self, dominator: Block, dominatee: Block) -> bool {
206        let mut node_opt = Some(dominatee);
207        while let Some(node) = node_opt {
208            if node == dominator {
209                return true;
210            }
211            node_opt = self.0[&node].parent;
212        }
213        false
214    }
215
216    /// Get an iterator over the children nodes
217    pub fn children(&self, node: Block) -> impl Iterator<Item = Block> + '_ {
218        self.0[&node].children.iter().cloned()
219    }
220
221    /// Get i'th child of a given node
222    pub fn child(&self, node: Block, i: usize) -> Option<Block> {
223        self.0[&node].children.get(i).cloned()
224    }
225}
226
227pub const DOM_FRONTS_NAME: &str = "dominance-frontiers";
228
229pub fn create_dom_fronts_pass() -> Pass {
230    Pass {
231        name: DOM_FRONTS_NAME,
232        descr: "Dominance frontiers computation",
233        deps: vec![DOMINATORS_NAME],
234        runner: ScopedPass::FunctionPass(PassMutability::Analysis(compute_dom_fronts)),
235    }
236}
237
238/// Compute dominance frontiers set for each block.
239fn compute_dom_fronts(
240    context: &Context,
241    analyses: &AnalysisResults,
242    function: Function,
243) -> Result<AnalysisResult, IrError> {
244    let dom_tree: &DomTree = analyses.get_analysis_result(function);
245    let mut res = DomFronts::default();
246    for (b, _) in dom_tree.0.iter() {
247        res.insert(*b, IndexSet::default());
248    }
249
250    // for all nodes, b
251    for (b, _) in dom_tree.0.iter() {
252        // if the number of predecessors of b >= 2
253        if b.num_predecessors(context) > 1 {
254            // unwrap() is safe as b is not "entry", and hence must have idom.
255            let b_idom = dom_tree.0[b].parent.unwrap();
256            // for all (reachable) predecessors, p, of b
257            for p in b.pred_iter(context).filter(|&p| dom_tree.0.contains_key(p)) {
258                let mut runner = *p;
259                while runner != b_idom {
260                    // add b to runner’s dominance frontier set
261                    res.get_mut(&runner).unwrap().insert(*b);
262                    runner = dom_tree.0[&runner].parent.unwrap();
263                }
264            }
265        }
266    }
267    Ok(Box::new(res))
268}
269
270/// Print dominator tree in the graphviz dot format.
271pub fn print_dot(context: &Context, func_name: &str, dom_tree: &DomTree) -> String {
272    let mut res = format!("digraph {func_name} {{\n");
273    for (b, idom) in dom_tree.0.iter() {
274        if let Some(idom) = idom.parent {
275            let _ = writeln!(
276                res,
277                "\t{} -> {}",
278                idom.get_label(context),
279                b.get_label(context)
280            );
281        }
282    }
283    res += "}\n";
284    res
285}
286
287/// Print dominator frontiers information.
288pub fn print_dom_fronts(context: &Context, func_name: &str, dom_fronts: &DomFronts) -> String {
289    let mut res = format!("Dominance frontiers set for {func_name}:\n");
290    for (b, dfs) in dom_fronts.iter() {
291        res += &("\t".to_string() + &b.get_label(context) + ": ");
292        for f in dfs {
293            res += &(f.get_label(context) + " ");
294        }
295        res += "\n";
296    }
297    res
298}
sway_ir/analysis/dominator.rs

sway_ir/analysis/
dominator.rs
