cranelift_filetests/
test_domtree.rs

1//! Test command for verifying dominator trees.
2//!
3//! The `test domtree` test command looks for annotations on instructions like this:
4//!
5//! ```clif
6//!     jump block3 ; dominates: block3
7//! ```
8//!
9//! This annotation means that the jump instruction is expected to be the immediate dominator of
10//! `block3`.
11//!
12//! We verify that the dominator tree annotations are complete and correct.
13//!
14
15use crate::match_directive::match_directive;
16use crate::subtest::{run_filecheck, Context, SubTest};
17use cranelift_codegen::dominator_tree::{DominatorTree, DominatorTreePreorder};
18use cranelift_codegen::flowgraph::ControlFlowGraph;
19use cranelift_codegen::ir::entities::AnyEntity;
20use cranelift_codegen::ir::Function;
21use cranelift_reader::TestCommand;
22use std::borrow::{Borrow, Cow};
23use std::collections::HashMap;
24use std::fmt::{self, Write};
25
26struct TestDomtree;
27
28pub fn subtest(parsed: &TestCommand) -> anyhow::Result<Box<dyn SubTest>> {
29    assert_eq!(parsed.command, "domtree");
30    if !parsed.options.is_empty() {
31        anyhow::bail!("No options allowed on {}", parsed)
32    }
33    Ok(Box::new(TestDomtree))
34}
35
36impl SubTest for TestDomtree {
37    fn name(&self) -> &'static str {
38        "domtree"
39    }
40
41    // Extract our own dominator tree from
42    fn run(&self, func: Cow<Function>, context: &Context) -> anyhow::Result<()> {
43        let func = func.borrow();
44        let cfg = ControlFlowGraph::with_function(func);
45        let domtree = DominatorTree::with_function(func, &cfg);
46
47        // Build an expected domtree from the source annotations.
48        let mut expected = HashMap::new();
49        for comment in &context.details.comments {
50            if let Some(tail) = match_directive(comment.text, "dominates:") {
51                let inst = match comment.entity {
52                    AnyEntity::Inst(inst) => inst,
53                    _ => {
54                        anyhow::bail!(
55                            "annotation on non-inst {}: {}",
56                            comment.entity,
57                            comment.text
58                        );
59                    }
60                };
61
62                let expected_block = match func.layout.inst_block(inst) {
63                    Some(expected_block) => expected_block,
64                    _ => anyhow::bail!("instruction {} is not in layout", inst),
65                };
66                for src_block in tail.split_whitespace() {
67                    let block = match context.details.map.lookup_str(src_block) {
68                        Some(AnyEntity::Block(block)) => block,
69                        _ => anyhow::bail!("expected defined block, got {}", src_block),
70                    };
71
72                    // Annotations say that `expected_block` is the idom of `block`.
73                    if expected.insert(block, expected_block).is_some() {
74                        anyhow::bail!("multiple dominators for {}", src_block);
75                    }
76
77                    // Compare to computed domtree.
78                    match domtree.idom(block) {
79                        Some(got_block) if got_block != expected_block => {
80                            anyhow::bail!(
81                                "mismatching idoms for {}:\n\
82                                 want: {}, got: {}",
83                                src_block,
84                                inst,
85                                got_block
86                            );
87                        }
88                        None => {
89                            anyhow::bail!(
90                                "mismatching idoms for {}:\n\
91                                 want: {}, got: unreachable",
92                                src_block,
93                                inst
94                            );
95                        }
96                        _ => {}
97                    }
98                }
99            }
100        }
101
102        // Now we know that everything in `expected` is consistent with `domtree`.
103        // All other block's should be either unreachable or the entry block.
104        for block in func
105            .layout
106            .blocks()
107            .skip(1)
108            .filter(|block| !expected.contains_key(block))
109        {
110            if let Some(got_block) = domtree.idom(block) {
111                anyhow::bail!(
112                    "mismatching idoms for renumbered {}:\n\
113                     want: unreachable, got: {}",
114                    block,
115                    got_block
116                );
117            }
118        }
119
120        let text = filecheck_text(func, &domtree).expect("formatting error");
121        run_filecheck(&text, context)
122    }
123}
124
125// Generate some output for filecheck testing
126fn filecheck_text(func: &Function, domtree: &DominatorTree) -> Result<String, fmt::Error> {
127    let mut s = String::new();
128
129    write!(s, "cfg_postorder:")?;
130    for &block in domtree.cfg_postorder() {
131        write!(s, " {block}")?;
132    }
133    writeln!(s)?;
134
135    // Compute and print out a pre-order of the dominator tree.
136    writeln!(s, "domtree_preorder {{")?;
137    let mut dtpo = DominatorTreePreorder::new();
138    dtpo.compute(domtree);
139    let mut stack = Vec::new();
140    stack.extend(func.layout.entry_block());
141    while let Some(block) = stack.pop() {
142        write!(s, "    {block}:")?;
143        let i = stack.len();
144        for ch in dtpo.children(block) {
145            write!(s, " {ch}")?;
146            stack.push(ch);
147        }
148        writeln!(s)?;
149        // Reverse the children we just pushed so we'll pop them in order.
150        stack[i..].reverse();
151    }
152    writeln!(s, "}}")?;
153
154    Ok(s)
155}
cranelift_filetests/test_domtree.rs

cranelift_filetests/
test_domtree.rs
