rucc_target/

flags.rs

//! What each instruction leaves in the condition state, and which comparisons ask the same thing.
//!
//! Design: `spec/optimizer/37-machine-level-optimization.md` section 37.4.
//!
//! A comparison on this kind of machine computes nothing. What it does is set a few bits nobody
//! named, and the instruction behind it reads them. So a comparison whose bits are already the
//! bits that are there is an instruction that could not be observed to have run, and taking it out
//! is the whole of this. There are two ways for the bits to already be there. The same comparison
//! was made a few instructions ago and nothing has disturbed it since, which is what a program
//! that asks whether something is zero and then whether it is not comes out as. Or the comparison
//! is against zero and the value it is about was worked out by arithmetic, which set the same bits
//! on its way past.
//!
//! It is here rather than in the pass for the reason [`crate::FrameInsts`] and
//! [`crate::BranchInsts`] are here. The pass is in a pipeline crate and `spec/10-backend.md`
//! section 10.8 says a pipeline crate holds no target-specific code, so what the pass knows about
//! a machine arrives as a description rather than as a name it says out loud.
//!
//! # Why the second case is not every condition
//!
//! A comparison against zero leaves more than the answer to it. `cmpl $0, %eax` says whether the
//! register is zero, and it says the register's sign, and it says that nothing carried and nothing
//! overflowed, because subtracting zero from a number cannot do either. An instruction that merely
//! happens to have written the register agrees about some of that and not all of it. `andl` agrees
//! about all of it: the machine clears carry and overflow after one, and sets the zero and sign
//! bits from what it wrote, which is what the comparison would have set them from. `subl` agrees
//! about the zero bit and about nothing else, because a subtraction that overflowed says so and
//! the comparison would have said it did not, and a condition built out of the sign and the
//! overflow together then reads two bits that no longer belong to each other.
//!
//! So a [`Zeroing`] says which of the three groups of conditions it is good for, [`Reads`] is
//! which group a condition belongs to, and a [`Reader`] is an instruction that names one. The zero
//! group is the one every entry is good for, since every instruction here that writes the
//! condition state at all sets the zero bit from what it wrote.
//!
//! The first case needs none of that. Two instructions that made the same comparison of the same
//! values left the same bits, all of them, so what may read them is not a question.
//!
//! # The instruction that reads the state and is not a condition
//!
//! An add with carry, and the subtract that goes with it, which arrive from an `asm` template
//! rather than from a rule. They are here for the half of this description that is not about
//! finding a comparison: the list of what reads the state is also what the scheduler keeps in
//! order, so an instruction missing from it is one the scheduler is free to move a comparison in
//! front of. What they read is [`Reads::Carry`], which is a fourth group with nothing in the table
//! good for it, so naming them here can only stop a rewrite and never allow one.
//!
//! # The two kinds of read
//!
//! An add with carry reads a bit the instruction in front of it left. A comparison that keeps a
//! byte reads a bit it set itself a moment earlier, in the same instruction. Both are a [`Reader`]
//! and the entry says the same thing about both, because what the entry is for is naming which
//! part of the state a condition is about, and that is the same question either way.
//!
//! It is not the same question for a pass asking whether a state is still needed. State arriving at
//! an add with carry is read. State arriving at a comparison that keeps a byte is written over
//! before anything looks at it, so it is dead there, exactly as it would be at a plain comparison.
//! [`FlagInsts::asks_what_it_reads`] is the question, and the answer is already in the two tables:
//! the second kind makes a comparison and the first kind does not.
//!
//! # What is not a [`Zeroing`]
//!
//! A shift, because a shift by zero leaves the condition state exactly as it found it, and the
//! count is in a register often enough that the compiler cannot tell. A multiply, because the
//! machine leaves the zero bit undefined after one. An increment and a decrement, because they
//! leave carry alone rather than clearing it. None of those is a shape a program runs into often,
//! and each of them is a way to be quietly wrong, so the table says nothing about them and the
//! pass believes the table.

/// What a pass has to know about a machine to find a comparison the machine has already made.
#[derive(Debug, Clone, Copy)]
pub struct FlagInsts {
    /// What a rule file and the machine IR put in front of this target's opcodes, such as `x64.`.
    pub prefix: &'static str,
    /// How many bits of the operand at that index the instruction of that name uses.
    ///
    /// The same question [`crate::BitInsts`] asks and the same answer, because two instructions
    /// that agree about a register's low half and not about the rest of it have not made the same
    /// comparison. `None` means the description does not name that operand, which the pass reads
    /// as not knowing and so as not the same.
    pub width: fn(&str, u8) -> Option<u32>,
    /// Whether the instruction of that name leaves the condition state other than it found it.
    ///
    /// True for a name this target does not have, since an instruction nothing knows anything
    /// about is one that may have done anything. It is the answer that makes the pass find less
    /// rather than the one that makes it wrong.
    pub writes: fn(&str) -> bool,
    /// Every instruction that makes a comparison, whether or not it keeps the answer.
    pub compares: &'static [Compare],
    /// Whether the instruction of that name makes the comparison it reads, all in the one
    /// instruction.
    ///
    /// Every entry in [`Self::compares`] that keeps a byte does, and so do the ones whose operand
    /// is in memory. Those are left out of that table on purpose, because a comparison against
    /// memory is not one a pass can prove was already made. What they read is still what they
    /// found, and that is all this asks. False for a name this target does not have.
    pub compares_itself: fn(&str) -> bool,
    /// Every instruction that reads the condition state and names which part of it.
    pub readers: &'static [Reader],
    /// Every instruction that leaves what a comparison of what it wrote against zero would leave.
    pub zeroing: &'static [Zeroing],
}

/// One comparison, and what is left of it when the machine has already made it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Compare {
    /// The opcode.
    pub name: &'static str,
    /// What it asks, which is the same string for every condition at one width.
    ///
    /// Two instructions have made the same comparison when this agrees and the registers and
    /// constants they read agree. The condition on the front of each of them is not part of it:
    /// the machine is asked the question once and the two conditions read two answers to it, which
    /// is exactly the case the pass is here for.
    pub asks: &'static str,
    /// What is left of it when the answer is already in the condition state.
    ///
    /// [`None`] is nothing at all, which is the entry for a comparison that keeps no answer,
    /// because the instruction behind it is reading the condition state and the condition state is
    /// already right. Anything else is an opcode that writes the same answer to the same register
    /// and makes no comparison, which is what a comparison that keeps a byte becomes.
    pub kept: Option<&'static str>,
}

/// One instruction that reads the condition state, and which part of it it reads.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Reader {
    /// The opcode.
    ///
    /// A comparison that keeps a byte is one of these as well as a [`Compare`], and what it reads
    /// is what it just set rather than what it found. That is the same entry either way, since
    /// what the entry says is which part of the condition state the condition names.
    pub name: &'static str,
    /// Which part of it.
    pub reads: Reads,
}

/// Which part of what a comparison against zero left a condition is about.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Reads {
    /// Whether the value was zero, and nothing else.
    Zero,
    /// Where the value sits against zero as a signed number, which is the sign and the overflow.
    Signed,
    /// Where it sits as an unsigned number, which is the carry, alone or with the zero.
    Unsigned,
    /// The carry as the instruction in front left it, which no comparison is a substitute for.
    ///
    /// The other three are parts of the answer to a question, so an instruction that has already
    /// asked that question can stand in for the one that would have asked it again. An add with
    /// carry is not reading an answer. It is reading the bit that fell off the end of the addition
    /// in front of it, and the only thing that leaves that bit is that addition, so nothing this
    /// pass could put there instead is the same. [`Zeroing::covers`] says no to it for every entry
    /// there is and will go on saying no to every entry added later, which is what keeps a
    /// comparison in front of one of these where the program put it.
    Carry,
    /// One bit read on its own, the sign, the overflow or the parity, which is what a jump an `asm`
    /// template writes as `js`, `jo` or `jp` asks about.
    ///
    /// No comparison against zero is asked that question, so nothing this pass could put in front
    /// of one is known to answer it, and [`Zeroing::covers`] says no here for the reason it says no
    /// to [`Reads::Carry`].
    Bit,
}

/// One instruction that leaves behind the comparison of what it wrote against zero.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Zeroing {
    /// The opcode.
    pub name: &'static str,
    /// Whether a signed comparison against zero reads what it left and gets the right answer.
    pub signed: bool,
    /// Whether an unsigned one does.
    pub unsigned: bool,
}

impl FlagInsts {
    /// The entry for the instruction of that name, if it makes a comparison.
    #[must_use]
    pub fn compare(&self, name: &str) -> Option<&'static Compare> {
        self.compares.iter().find(|entry| entry.name == name)
    }

    /// Which part of the condition state the instruction of that name reads, if it reads any.
    #[must_use]
    pub fn reads(&self, name: &str) -> Option<Reads> {
        self.readers.iter().find(|entry| entry.name == name).map(|entry| entry.reads)
    }

    /// Whether what the instruction of that name reads is what it wrote itself.
    ///
    /// A comparison that keeps a byte makes a comparison and then reads the answer, both in the one
    /// instruction, so it is a [`Compare`] and a [`Reader`] at once. What it reads is not what it
    /// found. An add with carry is the other kind: it reads the bit the instruction in front left,
    /// and it is a [`Reader`] and no [`Compare`], which is what tells the two apart without a
    /// second table. The comparisons against memory are the exception that needs one, and
    /// [`Self::compares_itself`] is where they are named.
    ///
    /// The difference is the whole question for a pass asking whether some state is still needed
    /// behind an instruction. A state arriving at an add with carry is a state that is read. A
    /// state arriving at a comparison that keeps a byte is a state that is written over before
    /// anything looks at it, which is to say a state that is dead there, and treating the two the
    /// same way makes a pass decline rewrites in most of the functions a C program has.
    #[must_use]
    pub fn asks_what_it_reads(&self, name: &str) -> bool {
        self.reads(name).is_some() && (self.compare(name).is_some() || (self.compares_itself)(name))
    }

    /// The entry for the instruction of that name, if it leaves a comparison against zero.
    #[must_use]
    pub fn zeroed(&self, name: &str) -> Option<&'static Zeroing> {
        self.zeroing.iter().find(|entry| entry.name == name)
    }
}

impl Zeroing {
    /// Whether a condition about that part of the condition state may read what it left.
    #[must_use]
    pub const fn covers(&self, reads: Reads) -> bool {
        match reads {
            Reads::Zero => true,
            Reads::Signed => self.signed,
            Reads::Unsigned => self.unsigned,
            Reads::Carry | Reads::Bit => false,
        }
    }
}