rucc_codegen/

select.rs

//! Matching a target's lowering rules against a term.
//!
//! Design: `spec/10-backend.md` section 10.2. The rules themselves are in `rules/`, one file per
//! target, and the automaton they compile into is generated by `rucc-rules` when this crate is
//! built.
//!
//! The walk over that automaton is [`rucc_base::rules`], because `rucc-opt` matches IR against a
//! table of rewrite rules with the same walk and neither crate can see the other. What is here
//! is which targets there are and the tests that the x86-64 table lowers what it should.
//!
//! The names are re-exported rather than reached for through `rucc_base`, because the generated
//! file refers to them through `super` and that is the whole of the contract between the two.

pub mod x86_64;

pub use rucc_base::rules::{Guard, Match, Node, Piece, Rule, Subject, Table};

#[cfg(test)]
mod tests {
    use super::x86_64::TABLE;
    use super::{Piece, Subject};

    /// A term, in the only shape a test needs: a flat arena, because that is the shape the IR
    /// has and answering the questions out of one is what the selector will be doing.
    #[derive(Debug)]
    enum Node {
        Int(i128),
        App(String, Vec<usize>),
    }

    #[derive(Debug, Default)]
    struct Terms {
        nodes: Vec<Node>,
    }

    impl Terms {
        fn constant(&mut self, value: i128) -> usize {
            self.nodes.push(Node::Int(value));
            self.nodes.len() - 1
        }

        fn app(&mut self, head: &str, args: &[usize]) -> usize {
            self.nodes.push(Node::App(head.to_owned(), args.to_vec()));
            self.nodes.len() - 1
        }

        /// A register operand, which is a term with a head the rules write and nothing under it.
        fn value(&mut self, width: u32, name: &str) -> usize {
            let inner = self.app(name, &[]);
            self.app(&format!("value.i{width}"), &[inner])
        }
    }

    impl Subject for Terms {
        type Node = usize;

        fn head(&self, node: usize) -> Option<(&str, usize)> {
            match &self.nodes[node] {
                Node::App(head, args) => Some((head.as_str(), args.len())),
                Node::Int(_) => None,
            }
        }

        fn arg(&self, node: usize, index: usize) -> usize {
            match &self.nodes[node] {
                Node::App(_, args) => args[index],
                Node::Int(_) => unreachable!("a constant has no arguments"),
            }
        }

        fn int(&self, node: usize) -> Option<i128> {
            match self.nodes[node] {
                Node::Int(value) => Some(value),
                Node::App(..) => None,
            }
        }

        // An index into the arena is the identity of a term here, so two places are the same
        // thing when they point at the same entry.
        fn same(&self, a: usize, b: usize) -> bool {
            a == b
        }
    }

    /// What the head of the rule that fired selects, which is the answer every one of these
    /// tests is really about.
    fn selects(terms: &Terms, term: usize) -> Option<&'static str> {
        let found = TABLE.find(terms, term)?;
        TABLE.rule(&found).head()
    }

    /// No pattern is reached by reading past the ones in front of it.
    ///
    /// `spec/optimizer/36-lowering-and-isel.md` section 36.5 asks for the decision to be on the
    /// shape of the term, and the root of this table is where that is worth anything: every
    /// instruction the selector looks at arrives there, and a hundred and sixty seven different
    /// heads are written on it. Sorted, that is eight comparisons and the walk finds the branch.
    /// In the order the rules happen to be written it would be a hundred and sixty seven, every
    /// time, and worst for the terms no rule covers, which are the ones the selector has to see
    /// the most of.
    ///
    /// What is asserted is the property the search needs, which is that every node is in order.
    /// A node that is not is not a slower table, it is a wrong one, because a binary search over
    /// an unsorted list finds nothing and the rule silently stops firing.
    #[test]
    fn no_rule_is_reached_by_reading_past_the_rules_in_front_of_it() {
        let root = TABLE.nodes.first().expect("the table has a root");
        assert!(root.heads.len() > 100, "the root is the node this is about");
        for (at, node) in TABLE.nodes.iter().enumerate() {
            assert!(node.heads.is_sorted(), "node {at} is not in an order a search can use");
            assert!(node.ints.is_sorted(), "node {at} is not in an order a search can use");
        }
    }

    #[test]
    fn the_table_holds_every_rule_the_file_writes() {
        let text = include_str!("../rules/x86-64.rules");
        let written = text.lines().filter(|line| line.starts_with("(rule ")).count();
        assert_eq!(TABLE.rules.len(), written, "the table and the rule file disagree");
        assert_eq!(TABLE.source, "rules/x86-64.rules");
    }

    #[test]
    fn an_addition_of_two_registers_is_the_register_form() {
        let mut terms = Terms::default();
        let x = terms.value(64, "v0");
        let y = terms.value(64, "v1");
        let add = terms.app("add.i64", &[x, y]);
        assert_eq!(selects(&terms, add), Some("x64.add_rr_64"));
    }

    /// The bindings are the operands in the order the pattern names them, and the replacement
    /// says which of them goes where. This is the whole of what the selector will read.
    ///
    /// What a name is bound to is what the pattern put it under, so `(value.i32 x)` binds the
    /// register and not the term saying it is one. That is the difference between the operand of
    /// the instruction this becomes and a wrapper that exists to say how wide it is.
    #[test]
    fn a_match_gives_back_the_operands_the_pattern_named() {
        let mut terms = Terms::default();
        let first = terms.app("v0", &[]);
        let second = terms.app("v1", &[]);
        let x = terms.app("value.i32", &[first]);
        let y = terms.app("value.i32", &[second]);
        let sub = terms.app("sub.i32", &[x, y]);
        let found = TABLE.find(&terms, sub).expect("a rule fires");
        let rule = TABLE.rule(&found);
        assert_eq!(rule.pattern, "(sub.i32 (value.i32 x) (value.i32 y))");
        assert_eq!(found.bindings, vec![first, second]);
        let names: Vec<&str> = rule
            .replacement
            .iter()
            .filter_map(|piece| match piece {
                Piece::Var { name, index } => {
                    assert_eq!(found.bindings[*index], if *index == 0 { first } else { second });
                    Some(*name)
                }
                _ => None,
            })
            .collect();
        assert_eq!(names, ["x", "y"]);
    }

    /// An immediate the instruction has room for takes the immediate form. The rule for it is
    /// guarded, so this is also the test that a guard which holds does not stop a rule firing.
    #[test]
    fn an_addition_of_an_immediate_that_fits_is_the_immediate_form() {
        let mut terms = Terms::default();
        let x = terms.value(64, "v0");
        let k = terms.constant(4);
        let k = terms.app("iconst.i64", &[k]);
        let add = terms.app("add.i64", &[x, k]);
        assert_eq!(selects(&terms, add), Some("x64.add_ri_64"));
    }

    /// An immediate too wide for the encoding is what the guard is there to refuse. Nothing else
    /// matches such a term, and that is the right answer: the constant has to be put in a
    /// register first, which is a decision for the selector and not for the table.
    #[test]
    fn an_addition_of_an_immediate_too_wide_for_the_form_matches_nothing() {
        let mut terms = Terms::default();
        let x = terms.value(64, "v0");
        let k = terms.constant(1 << 40);
        let k = terms.app("iconst.i64", &[k]);
        let add = terms.app("add.i64", &[x, k]);
        assert_eq!(selects(&terms, add), None);
    }

    /// The other shape of guard, which is a shift count the width allows.
    #[test]
    fn a_shift_by_a_count_the_width_allows_is_the_immediate_form() {
        let mut terms = Terms::default();
        let x = terms.value(64, "v0");
        let k = terms.constant(3);
        let k = terms.app("iconst.i64", &[k]);
        let shl = terms.app("shl.i64", &[x, k]);
        assert_eq!(selects(&terms, shl), Some("x64.shl_ri_64"));
    }

    #[test]
    fn a_shift_by_a_count_the_width_does_not_allow_matches_nothing() {
        let mut terms = Terms::default();
        let x = terms.value(64, "v0");
        let k = terms.constant(64);
        let k = terms.app("iconst.i64", &[k]);
        let shl = terms.app("shl.i64", &[x, k]);
        assert_eq!(selects(&terms, shl), None);
    }

    /// One bit reaches the byte instructions, which is the whole of how the machine holds a truth
    /// value. The widening is the interesting one: it is `movzbl` under a name of its own, so the
    /// rule that fires here is not the rule a byte would have found.
    #[test]
    fn a_truth_value_is_lowered_to_the_byte_instructions_that_keep_it_one() {
        let mut terms = Terms::default();
        let x = terms.value(1, "v0");
        let y = terms.value(1, "v1");
        let xor = terms.app("xor.i1", &[x, y]);
        assert_eq!(selects(&terms, xor), Some("x64.xor_rr_8"));

        let x = terms.value(1, "v2");
        let wide = terms.app("zext.i1.i32", &[x]);
        assert_eq!(selects(&terms, wide), Some("x64.bit_to_32"));

        let x = terms.value(8, "v3");
        let byte = terms.app("zext.i8.i32", &[x]);
        assert_eq!(selects(&terms, byte), Some("x64.movzx_8_32"));
    }

    /// The half of a truth value that is an object rather than a value in a register. A `_Bool`
    /// in memory is a byte holding a zero or a one, so a load widens on the way in and a store
    /// writes the byte, and both are named apart from the byte pair for the reason the widening
    /// is named apart from the byte widening. The narrowing is the mask, and it is the one of
    /// these that nothing in C asks for directly: a bit field one bit wide whose type is a
    /// `_Bool` is what writes it.
    #[test]
    fn a_truth_value_in_memory_is_the_byte_it_lives_in() {
        let mut terms = Terms::default();
        let address = terms.value(64, "v0");
        let read = terms.app("load.i1", &[address]);
        assert_eq!(selects(&terms, read), Some("x64.mov_rm_bit"));

        let value = terms.value(1, "v1");
        let address = terms.value(64, "v2");
        let write = terms.app("store.i1", &[value, address]);
        assert_eq!(selects(&terms, write), Some("x64.mov_mr_bit"));

        let value = terms.value(1, "v3");
        let back = terms.app("ret.i1", &[value]);
        assert_eq!(selects(&terms, back), Some("x64.ret_val_8"));

        let x = terms.value(32, "v4");
        let bit = terms.app("trunc.i32.i1", &[x]);
        assert_eq!(selects(&terms, bit), Some("x64.bit_of_32"));
    }

    /// A term the rule set says nothing about is nothing rather than a wrong answer, which is
    /// what the completeness check in `spec/10-backend.md` will be for.
    #[test]
    fn a_term_no_rule_covers_finds_no_rule() {
        let mut terms = Terms::default();
        let x = terms.value(64, "v0");
        let y = terms.value(64, "v1");
        let odd = terms.app("no.such.opcode", &[x, y]);
        assert_eq!(selects(&terms, odd), None);
    }
}