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
//! AArch64 table has its own tests beside it.
//!
//! 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 aarch64;
pub mod x86_64;

pub use rucc_base::rules::{Guard, Match, Node, Piece, Rule, Subject, Table};
use rucc_target::{
    Address, BranchInsts, FrameInsts, MachineInsts, OperandDesc, PhysReg, RegClass, Segment,
};

/// What `crate::lower` has to know about the machine it selects instructions for.
///
/// The lowering is one walk over the IR whichever machine it is for, and everything in it that
/// differs between two machines is a question this answers: which table the rules compiled into,
/// what each opcode's operands are, what an address constructor's arguments mean, and the handful
/// of instructions the walk writes itself rather than getting from a rule. A walk that reaches
/// for a machine's module by name is a walk for that machine only, which is what this is here to
/// stop.
///
/// The frame and branch instructions are the same tables `crate::pipeline::Machine` hands the
/// passes after this one. They are in here as well so that the lowering is handed one thing,
/// rather than a machine and the convention and the rules separately.
#[derive(Debug)]
pub struct Selector {
    /// The rules, compiled.
    pub table: &'static Table,
    /// The shape of each opcode, and the prefix a rule file puts in front of one.
    pub shapes: &'static MachineInsts,
    /// What an address constructor in a replacement stands for, or `None` for a name that is not
    /// one of this machine's.
    pub address: fn(&str) -> Option<Address>,
    /// The instructions that take a frame and give it back, of which the walk writes the address
    /// of a local and the move between two registers itself.
    pub frame: &'static FrameInsts,
    /// The instructions a branch becomes, of which the walk writes the indirect jump itself.
    pub branch: &'static BranchInsts,
    /// The class an address is in.
    pub gpr: RegClass,
    /// The instruction a full fence is, without the prefix.
    pub fence: &'static str,
    /// The instruction a program that must stop here stops with, without the prefix.
    pub trap: &'static str,
    /// The instructions the calling convention is written with.
    pub abi: &'static crate::abi::Insts,
    /// The address registers held back from the allocator for the rewriter's reloads, which are
    /// the ones the walk must not keep anything in across more than one instruction.
    pub scratch: &'static [PhysReg],
    /// How the walk comes by the address of a symbol, which is its own business rather than a
    /// rule's because whether it goes through the global offset table is a fact about the link and
    /// not about the instruction.
    pub symbols: &'static Symbols,
    /// The instructions a jump through a table is built from, and the address of a label.
    pub jumps: &'static Jumps,
}

/// The instructions a place in this function is reached with: the address of a block or a jump
/// table, and the read of one cell of a table and the add that turns it back into an address.
#[derive(Debug)]
pub struct Jumps {
    /// The address of a block or a table, which is carried in the addressing mode.
    pub near: &'static str,
    /// A load of a 32-bit cell, sign extended to the width of an address.
    pub cell: &'static str,
    /// The add of two addresses.
    pub add: &'static str,
    /// Whether the add writes its first operand, the way it does on x86-64.
    pub two_address: bool,
}

/// The two ways the address of a symbol is come by.
#[derive(Debug)]
pub struct Symbols {
    /// A symbol this image defines, whose address is a fixed distance from the code.
    pub near: Reach,
    /// A symbol another image may define, whose address is read out of the global offset table.
    pub far: Reach,
    /// A pointer this image holds, read where the name it points to is reached through it, which
    /// is how COFF reaches a name in a DLL or one another object may define.
    pub slot: Reach,
    /// How far a thread-local variable is from the thread pointer, which is read out of the global
    /// offset table too, from a slot the link fills in with that distance.
    pub thread: Reach,
    /// The thread pointer itself.
    pub pointer: Pointer,
    /// How a Windows thread finds its copy of a thread-local variable, where this machine has
    /// been taught. See [`Indexed`].
    pub indexed: Option<Indexed>,
    /// The same on a machine that keeps the TEB in a register rather than a segment, which is
    /// AArch64. See [`Teb`].
    pub teb: Option<Teb>,
}

/// The instructions a thread-local variable is reached with on Windows on AArch64.
///
/// The same walk as [`Indexed`], from the TEB Windows keeps in `x18` rather than in a segment,
/// and the six instructions clang writes for it.
///
/// ```text
/// adrp x8, _tls_index
/// ldr  w8, [x8, :lo12:_tls_index]
/// ldr  x9, [x18, #88]
/// ldr  x8, [x9, x8, lsl #3]
/// add  x8, x8, :secrel_hi12:x, lsl #12
/// add  x0, x8, :secrel_lo12:x
/// ```
#[derive(Debug)]
pub struct Teb {
    /// The first two, which read `_tls_index`, carrying it as its symbol.
    pub index: &'static str,
    /// The third, which reads the array out of the TEB.
    pub array: &'static str,
    /// The rest, which read this thread's block out of the array with the index and add the
    /// variable's offset in its section, carrying the variable as its symbol. It takes the array
    /// and the index as its two sources, in that order.
    pub block: &'static str,
}

/// The instructions a thread-local variable is reached with on Windows.
///
/// Every thread keeps an array of pointers, one for each image's copy of its `.tls` section. The
/// thread block holds the array, the image's `_tls_index` says which slot is its own, and the
/// variable is as far into the copy as it is into the section.
///
/// ```text
/// movl  _tls_index(%rip), %idx
/// movq  %gs:88, %arr
/// movq  (%arr,%idx,8), %blk
/// leaq  x@SECREL32(%blk), %x
/// ```
#[derive(Debug)]
pub struct Indexed {
    /// A 32-bit load, zero extended, which reads `_tls_index`.
    pub index: &'static str,
    /// A load of a whole word, which reads the array out of the thread block and the block out of
    /// the array.
    pub load: &'static str,
    /// The segment the thread block is in, and how far into it the array is.
    pub segment: Segment,
    /// The same.
    pub at: i32,
    /// The instruction that adds an offset to a register, which takes the variable's offset in its
    /// section as its displacement.
    pub add: &'static str,
}

/// Where the thread pointer is read from.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Pointer {
    /// A load at zero in a segment, since the word at the front of the block is its own address.
    /// That is x86-64, whose `%fs` is not a register a program can read.
    Segment(&'static str, Segment),
    /// An instruction that reads a system register, which is AArch64's `mrs` of `tpidr_el0`.
    Own(&'static str),
}

/// One instruction that puts the address of a symbol in a register, and where it carries the
/// symbol.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Reach {
    /// In its addressing mode, which is how x86-64 does both: a `lea` or a `mov` relative to the
    /// instruction pointer.
    Mode(&'static str),
    /// As the instruction's own symbol with no addressing mode at all, which is how AArch64 does
    /// both: an `adrp` for the page and a second instruction for the rest, written as one opcode.
    Own(&'static str),
}

impl Selector {
    /// What a rule file and the machine IR put in front of this machine's opcodes.
    #[must_use]
    pub fn prefix(&self) -> &'static str {
        self.shapes.prefix
    }

    /// The operands the opcode of that name has, the name written without the prefix.
    #[must_use]
    pub fn operands(&self, name: &str) -> Option<&'static [OperandDesc]> {
        (self.shapes.operands)(name)
    }
}

#[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"));
    }

    /// The divisions at one byte and at two, which the `narrow` pass writes for a division of two
    /// zero extensions and, signed, for a division of two sign extensions the ranges clear.
    #[test]
    fn a_narrow_division_is_the_narrow_divide() {
        let mut terms = Terms::default();
        for width in [8, 16] {
            let x = terms.value(width, "v0");
            let y = terms.value(width, "v1");
            for (op, head) in [
                ("udiv", "div_quo"),
                ("urem", "div_rem"),
                ("sdiv", "idiv_quo"),
                ("srem", "idiv_rem"),
            ] {
                let term = terms.app(&format!("{op}.i{width}"), &[x, y]);
                let want = format!("x64.{head}_{width}");
                assert_eq!(selects(&terms, term), Some(want.as_str()));
            }
        }
    }

    /// 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);
    }

    /// Every instruction a selector names outside its rules is one its machine describes, since
    /// the lowering writes those without asking a rule and nothing else would catch a name that is
    /// not there.
    #[test]
    fn a_selector_names_only_instructions_its_machine_has() {
        for selector in [&super::x86_64::SELECTOR, &super::aarch64::SELECTOR] {
            let named = [
                selector.fence,
                selector.trap,
                selector.frame.lea,
                selector.frame.grow,
                selector.frame.imm,
                selector.branch.indirect,
            ];
            for name in named {
                assert!(
                    selector.operands(name).is_some(),
                    "{}{name} is not an instruction of its machine",
                    selector.prefix()
                );
            }
            // And the rules it is handed are the ones written for the same machine.
            for rule in selector.table.rules {
                let Some(Piece::App { head, .. }) = rule.replacement.first() else { continue };
                assert!(head.starts_with(selector.prefix()), "{head} in {}", selector.table.source);
            }
        }
    }

    /// An address constructor is read the same way on both machines, and the one the AArch64 rules
    /// cannot write is not one it answers for.
    #[test]
    fn both_machines_read_an_address_the_same_way() {
        let (x86, a64) = (&super::x86_64::SELECTOR, &super::aarch64::SELECTOR);
        for name in ["amode_base", "amode_base_offset"] {
            assert_eq!((x86.address)(name), (a64.address)(name));
            assert!((a64.address)(name).is_some());
        }
        assert!((x86.address)("amode_base_index_scale").is_some());
        assert_eq!((a64.address)("amode_base_index_scale"), None);
        assert_eq!((a64.address)("add_rr_64"), None);
    }
}