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::{Context, SubTest, run_filecheck};
17use cranelift_codegen::dominator_tree::DominatorTree;
18use cranelift_codegen::flowgraph::ControlFlowGraph;
19use cranelift_codegen::ir::Function;
20use cranelift_codegen::ir::entities::AnyEntity;
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 {inst} is not in layout"),
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 {src_block}:\n\
82                                 want: {inst}, got: {got_block}"
83                            );
84                        }
85                        None => {
86                            anyhow::bail!(
87                                "mismatching idoms for {src_block}:\n\
88                                 want: {inst}, got: unreachable"
89                            );
90                        }
91                        _ => {}
92                    }
93                }
94            }
95        }
96
97        // Now we know that everything in `expected` is consistent with `domtree`.
98        // All other block's should be either unreachable or the entry block.
99        for block in func
100            .layout
101            .blocks()
102            .skip(1)
103            .filter(|block| !expected.contains_key(block))
104        {
105            if let Some(got_block) = domtree.idom(block) {
106                anyhow::bail!(
107                    "mismatching idoms for renumbered {block}:\n\
108                     want: unreachable, got: {got_block}"
109                );
110            }
111        }
112
113        let text = filecheck_text(func, &domtree).expect("formatting error");
114        run_filecheck(&text, context)
115    }
116}
117
118// Generate some output for filecheck testing
119fn filecheck_text(func: &Function, domtree: &DominatorTree) -> Result<String, fmt::Error> {
120    let mut s = String::new();
121
122    write!(s, "cfg_postorder:")?;
123    for &block in domtree.cfg_postorder() {
124        write!(s, " {block}")?;
125    }
126    writeln!(s)?;
127
128    // Compute and print out a pre-order of the dominator tree.
129    writeln!(s, "domtree_preorder {{")?;
130    let mut stack = Vec::new();
131    stack.extend(func.layout.entry_block());
132    while let Some(block) = stack.pop() {
133        write!(s, "    {block}:")?;
134        let i = stack.len();
135        for ch in domtree.children(block) {
136            write!(s, " {ch}")?;
137            stack.push(ch);
138        }
139        writeln!(s)?;
140        // Reverse the children we just pushed so we'll pop them in order.
141        stack[i..].reverse();
142    }
143    writeln!(s, "}}")?;
144
145    Ok(s)
146}
cranelift_filetests/test_domtree.rs

cranelift_filetests/
test_domtree.rs
