rucc_target/

short.rs

//! The instructions that have a shorter spelling of the same answer, and what the shorter one is.
//!
//! Design: `spec/optimizer/37-machine-level-optimization.md` section 37.4.
//!
//! There is more than one instruction for putting a number in a register, and on a machine with
//! variable length instructions they are not the same number of bytes. Putting zero there is the
//! case worth having a description for: `movl $0, %eax` spells the zero out and is five bytes, and
//! `xorl %eax, %eax` says it without spelling it and is two. GCC writes the second one everywhere
//! and rucc writes the first, which over the corpus at `-Os` is twenty thousand instructions
//! against seven.
//!
//! What stops it being a thing the encoder does on its own is that the two are not the same
//! instruction. The exclusive or writes the condition state and the move does not, so the rewrite
//! is legal where nothing reads the state before something else writes it and is wrong where
//! anything does. That is a question about the instructions behind it rather than about the
//! instruction itself, which is what makes it a pass rather than a choice of encoding, and
//! [`crate::FlagInsts`] is the description that pass asks.
//!
//! The other thing described here is width. A number that is not negative and fits in thirty-two
//! bits goes into a sixty-four bit register either way, because writing the low half of a register
//! on this machine clears the high half rather than leaving it alone, and the instruction that
//! writes the low half is the shorter of the two. So `movq $7, %rax` and `movl $7, %eax` leave the
//! same number in the same place and are seven bytes and five.
//!
//! That one an encoder could do without asking anything, since neither instruction touches the
//! condition state and the register ends up holding the same number. It is not done there because
//! an encoder that wrote `movl` where it was handed `movq` would be writing bytes the listing beside
//! them does not say, and the listing and the bytes saying the same thing is worth more than the
//! two bytes. Choosing the instruction is this pass's job and spelling the one it chose is the
//! encoder's.
//!
//! The third thing described here is a comparison against zero. `cmpl $0, %eax` asks whether what
//! is in the register is zero, is above it or is below it, and `testl %eax, %eax` asks the machine
//! the same three questions of the same register without a constant on the instruction, which is
//! three bytes against two. Both leave the sign, the zero and the parity of what is in the register,
//! and both clear the carry and the overflow, so every condition behind either of them reads the
//! same answer.
//!
//! That one is an encoder's rewrite even less than the width one is, since the two instructions are
//! not even the same length of operand list, and it is here for the same reason: the listing and the
//! bytes say the same thing because the pass chose the instruction the encoder then spells.
//!
//! The fourth thing described here is adding one and taking one away. `addl $1, %eax` is three
//! bytes, one for the opcode, one saying which register and one for the number, and `incl %eax` is
//! two, the number being part of the opcode rather than written after it.
//!
//! That one is the first thing here that is not free. The addition writes the carry and the
//! increment leaves it as it found it, so the two are the same only where nothing behind reads a
//! carry the addition would have set, which is the question [`crate::FlagInsts`] answers and is the
//! same shape of question the exclusive or asks. It is also the first thing here that is a trade
//! rather than a saving: an instruction that leaves part of the condition state alone leaves the
//! next instruction to write that state having to merge with what it left, which costs where the
//! code is hot and is worth the byte where the goal is size. So a target says which instructions
//! these are and the pass asks the goal before it writes one, which is what tamnd/rucc#741 is about.
//!
//! The fifth thing described here is an address computation that computes no address. The
//! instruction that works an address out and keeps it takes a whole addressing mode, and an
//! addressing mode naming one register and adding nothing to it is that register. So `leaq (%rsp),
//! %rax` puts in `rax` what is already in `rsp`, which is what `movq %rsp, %rax` does.
//!
//! The byte comes from the shape of the addressing mode rather than from the opcode. An address
//! counted from the stack pointer cannot be written without the extra byte that says there is no
//! index, so the address computation is four bytes where the move is three, and the stack pointer
//! is the register this shape turns up on, because what makes it is taking the address of the local
//! that happens to sit at the bottom of the frame. It is not only a byte either: a move between
//! registers is a thing the machine can do by renaming rather than by computing, and an address
//! computation is arithmetic whatever the numbers in it are.
//!
//! Neither instruction touches the condition state, so unlike the exclusive or and the increment
//! this one asks nothing about what is behind it. What it asks about is the addressing mode, which
//! is why the entry names the two opcodes and the pass looks at the mode: a description cannot say
//! which addressing modes an instruction will turn out to have.
//!
//! It is here rather than in the pass for the reason [`crate::FlagInsts`] 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.

/// The shorter spellings this target has.
#[derive(Debug)]
pub struct ShortInsts {
    /// What a rule file and the machine IR put in front of this target's opcodes, such as `x64.`.
    pub prefix: &'static str,
    /// Every instruction that puts a constant in a register and has a shorter way of putting zero
    /// there.
    pub zeroing: &'static [Zeroed],
    /// Every instruction that puts a constant in a register and has a narrower one that writes the
    /// same register and clears the rest of it.
    pub narrowing: &'static [Narrowed],
    /// Every instruction that compares a register against a constant and has a shorter one that
    /// asks the same thing of the register against itself when the constant is zero.
    pub testing: &'static [Tested],
    /// Every instruction that adds a constant to a register and has a shorter one that carries the
    /// number in its opcode, for the one or two numbers that shorter one is about.
    pub stepping: &'static [Stepped],
    /// Every instruction that works out an address and keeps it, and the move that says the same
    /// thing when the address is one register and nothing else.
    pub copying: &'static [Copied],
}

impl ShortInsts {
    /// The shorter way of writing zero into a register, for the instruction of that name.
    #[must_use]
    pub fn zeroed(&self, name: &str) -> Option<&'static str> {
        self.zeroing.iter().find(|entry| entry.name == name).map(|entry| entry.into)
    }

    /// The narrower instruction that writes the same register, for the instruction of that name.
    #[must_use]
    pub fn narrowed(&self, name: &str) -> Option<Narrowed> {
        self.narrowing.iter().find(|entry| entry.name == name).copied()
    }

    /// The shorter way of comparing a register against zero, for the instruction of that name.
    #[must_use]
    pub fn tested(&self, name: &str) -> Option<&'static str> {
        self.testing.iter().find(|entry| entry.name == name).map(|entry| entry.into)
    }

    /// The shorter way of adding that number to a register, for the instruction of that name.
    ///
    /// Both halves are the key. One instruction has a shorter spelling for more than one number,
    /// since an addition of one and a subtraction of one are each other going the other way, and
    /// which of the two shorter instructions is meant depends on which number was written.
    #[must_use]
    pub fn stepped(&self, name: &str, by: i64) -> Option<&'static str> {
        self.stepping
            .iter()
            .find(|entry| entry.name == name && entry.by == by)
            .map(|entry| entry.into)
    }

    /// The move that says the same thing as the address computation of that name.
    ///
    /// Only the name is the key, because what makes the two the same is the addressing mode rather
    /// than anything about the opcode, and the addressing mode is not a thing a table of names could
    /// hold. The pass is what looks at it.
    #[must_use]
    pub fn copied(&self, name: &str) -> Option<&'static str> {
        self.copying.iter().find(|entry| entry.name == name).map(|entry| entry.into)
    }

    /// Whether the instruction of that name is one of the shorter ones that leaves the carry alone.
    ///
    /// Asked of an instruction the walk is looking past rather than of one it is thinking about
    /// rewriting, so what it is really asking is whether this instruction ends the life of a carry
    /// something in front of it set. One of these does not, which is the whole of what makes it
    /// shorter and the whole of what makes the rewrite conditional.
    #[must_use]
    pub fn steps(&self, name: &str) -> bool {
        self.stepping.iter().any(|entry| entry.into == name)
    }
}

/// One instruction that writes a constant, and the instruction that writes zero in fewer bytes.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Zeroed {
    /// The opcode that takes the constant.
    pub name: &'static str,
    /// The opcode that writes zero into the one register the first one wrote, reading that same
    /// register twice. It writes the condition state, which is the whole of why this is a
    /// description and not a rewrite anyone could do without looking around.
    pub into: &'static str,
}

/// One instruction that writes a constant, and the narrower one that writes the same register.
///
/// Narrower means fewer bytes of the number written out, and on this machine it also means fewer
/// bytes of instruction: the sixty-four bit move carries a prefix byte saying so and the thirty-two
/// bit move does not, and a number too wide to sign extend from thirty-two bits is written out
/// whole where the narrower instruction writes four bytes of it.
///
/// It says the same thing only for the numbers the narrower instruction can hold and only on a
/// machine where writing part of a register clears the rest of it, which is why [`Narrowed::writes`]
/// is here rather than the pass working the range out from the name.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Narrowed {
    /// The opcode that takes the constant.
    pub name: &'static str,
    /// The opcode that takes the same constant in fewer bytes.
    pub into: &'static str,
    /// How many bits of the register the narrower opcode writes. The rest of the register is
    /// cleared rather than left alone, so the two say the same thing for a number that is not
    /// negative and fits in this many bits, and disagree for every other number.
    pub writes: u32,
}

/// One comparison against a constant, and the shorter instruction that asks it against zero.
///
/// The shorter one reads the register it is given and reads it again instead of the constant, so it
/// names one register where the first names a register and a number, and the bytes it saves are the
/// bytes the number was written in. It says the same thing only for zero: a comparison of a register
/// against zero and a bitwise and of the register with itself leave the same sign, the same zero and
/// the same parity, and both leave the carry and the overflow clear.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Tested {
    /// The opcode that takes the constant.
    pub name: &'static str,
    /// The opcode that asks the same question of the register alone. It writes the condition state
    /// exactly as the first one does, which is why nothing about where the state is live is a
    /// question this rewrite has to ask.
    pub into: &'static str,
}

/// One addition of a constant, and the shorter instruction that adds that constant and no other.
///
/// Shorter because the number is in the opcode. An addition of a small constant spells the constant
/// out in a byte after the one saying which register, and an increment says both in the opcode and
/// the byte after it, so the saving is the byte the number was written in whatever the width.
///
/// It says the same thing about the register and not about the condition state. The addition writes
/// the carry and the increment leaves the carry as it found it, so the two agree wherever nothing
/// reads a carry between the instruction and the next thing to write one, and disagree everywhere
/// else. That is a question about the instructions behind rather than about this one, which is what
/// keeps this a description a pass asks rather than a spelling an encoder chooses.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Stepped {
    /// The opcode that takes the constant.
    pub name: &'static str,
    /// The constant it has to be carrying, as the number written on the instruction rather than as
    /// the number the instruction adds. So a subtraction that takes one away is here as one and
    /// turns into the instruction that takes one away, and the two agree about the register without
    /// the pass having to know which of the two opcodes is the subtraction.
    pub by: i64,
    /// The opcode that adds that number without writing it out. It writes every part of the
    /// condition state the first one writes except the carry, which it leaves alone.
    pub into: &'static str,
}

/// One address computation, and the move that says the same thing when the address is a register.
///
/// The two are the same instruction only for an addressing mode that names a base and nothing else:
/// no index, no constant added, no symbol and no label, since each of those is arithmetic the move
/// does not do. That is a question about the instruction in hand rather than about its name, so the
/// entry names the pair and the pass asks the mode.
///
/// Neither of them writes the condition state, which is what keeps this rewrite out of the walk that
/// the exclusive or and the increment wait on. It saves a byte where the base is one of the
/// registers an addressing mode cannot name on its own, and it saves the machine an addition
/// everywhere, since a move between registers is a rename rather than work.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Copied {
    /// The opcode that takes the addressing mode.
    pub name: &'static str,
    /// The opcode that moves one register into another, which writes the register the first one
    /// wrote and reads the one its addressing mode named.
    pub into: &'static str,
}