rucc_ir/

flags.rs

//! Instruction flags, atomic orderings, and the read-modify-write operations.
//!
//! Design: `spec/08-ir.md` section 8.4.
//!
//! Nearly every flag is a licence the frontend grants the optimizer, and each of those is tied to
//! something the C standard leaves undefined. `-fwrapv` is implemented by not setting
//! [`Flags::NSW`], and that is the whole of it.
//!
//! [`Flags::NOFREE`] and [`Flags::STATIC`] are the two that are not licences. Each is a fact worked
//! out over the whole module and written onto the instruction it is about, because a pass is given
//! one function and neither fact is in it: what a call reaches belongs to the callee, and how big a
//! global is belongs to the module. The frontend does the same thing with a call that never comes
//! back: it puts an `unreachable` after it rather than expecting every later pass to go and look
//! the callee up.
//!
//! **There is no poison.** An `add nsw` that overflows does not produce a value that taints
//! everything downstream. It produces an unspecified but stable value, meaning two reads of it
//! agree, and `nsw` licenses only the specific rewrites the rule set proves sound under the
//! assumption that the overflow does not happen. The cost is real, and it is that arithmetic
//! cannot be speculated across control flow as aggressively. The benefit is that every rewrite
//! is locally justifiable, which is what keeps the rule set verifiable, and that a wrong answer
//! cannot travel from somewhere the user cannot see to somewhere they can.
//!
//! The fast-math flags sit on individual instructions rather than in a global mode, so
//! `-ffast-math` is a decision the frontend makes per expression. That is what keeps link time
//! optimization across a unit built with it and a unit built without it correct.

use std::fmt;

use crate::Opcode;

/// The flags on one instruction.
///
/// A bitset rather than a struct of `bool`s, because it rides along in the instruction table
/// and two bytes there is two bytes per instruction in every function in the program.
#[derive(Clone, Copy, PartialEq, Eq, Default, Hash)]
pub struct Flags(u16);

impl Flags {
    /// No flags, which is what `-O0` and `-fwrapv` and a plain unsigned addition all produce.
    pub const NONE: Self = Self(0);

    /// No signed wrap. Signed overflow is undefined, so the optimizer may assume it does not
    /// happen. `-fwrapv` stops the frontend setting this and nothing else changes.
    pub const NSW: Self = Self(1 << 0);
    /// No unsigned wrap. Set only where the frontend knows it from the source, since C's
    /// unsigned arithmetic wraps by definition and most unsigned arithmetic does not get this.
    pub const NUW: Self = Self(1 << 1);
    /// The shift or division is exact, so no bits are discarded and no remainder is dropped.
    pub const EXACT: Self = Self(1 << 2);

    /// No NaN operands or results.
    pub const NNAN: Self = Self(1 << 3);
    /// No infinite operands or results.
    pub const NINF: Self = Self(1 << 4);
    /// The sign of a zero does not matter.
    pub const NSZ: Self = Self(1 << 5);
    /// A division may become a multiplication by the reciprocal.
    pub const ARCP: Self = Self(1 << 6);
    /// A multiplication and an addition may be contracted into one rounding.
    pub const CONTRACT: Self = Self(1 << 7);
    /// The operation may be reassociated, which is the one that changes results the most.
    pub const REASSOC: Self = Self(1 << 8);

    /// The access is `volatile`, so it happens exactly once and is never moved or merged.
    pub const VOLATILE: Self = Self(1 << 9);
    /// The result does not alias anything else reachable, which is what `restrict` gives.
    pub const NOALIAS: Self = Self(1 << 10);

    /// Nothing this call reaches ends the lifetime of any storage.
    ///
    /// The `nofree` summary of `spec/safe-memory/07-check-elimination.md` section 7.5, written onto
    /// the call site by a module-level analysis rather than by the frontend. A pass carrying what
    /// an earlier safety check established keeps it across a call that has this and gives it up
    /// across a call that does not.
    pub const NOFREE: Self = Self(1 << 11);

    /// The bytes this safety check is about lie inside one object of static storage duration
    /// whose extent this module knows.
    ///
    /// Section 7.2 of `spec/safe-memory/07-check-elimination.md` puts the frontend first of the
    /// four sources of a discharge, because most accesses in real C are to a local or a global at a
    /// constant offset and how big either one is is not something anybody has to work out. The
    /// local half is read straight off the `alloca` by the pass that removes the check. The global
    /// half is this flag, because a global's size lives on the module and a pass is given one
    /// function, so a module-level analysis works it out before the pipeline starts and writes it
    /// onto the check.
    ///
    /// A fact rather than a licence, like [`Flags::NOFREE`] and unlike everything above it. It
    /// says what is true of the bytes, and whether that is enough for the check to go is a rule.
    pub const STATIC: Self = Self(1 << 12);

    /// The bytes this safety check is about lie inside one object that every call to this
    /// function hands it, and whose extent this module knows.
    ///
    /// The same shape as [`Flags::STATIC`] and the next of the four sources section 7.2 lists,
    /// which is section 7.5's summaries. A pointer that arrived as a parameter is a pointer
    /// nothing in the function can say anything about, and it is where most of the checks a real
    /// program keeps are. What can be said about it is said by the callers: if every call to a
    /// function only this module can call passes a frame slot or a global with at least so many
    /// bytes left in it, then the parameter has at least so many bytes wherever it is used.
    ///
    /// Worked out over the module before the pipeline starts, for the reason [`Flags::STATIC`]
    /// gives: a call site is in a different function from the parameter it is about, and a pass is
    /// given one function.
    ///
    /// It says the same two things [`Flags::STATIC`] says, an extent and a lifetime, because the
    /// objects it is ever about are a caller's frame slot or a global and both of those are alive
    /// for as long as the call runs. A fact rather than a licence, in the same way.
    pub const HANDED: Self = Self(1 << 13);

    /// This call hands back either null or one fresh storage instance of at least as many bytes as
    /// its last argument asks for.
    ///
    /// The third of the objects whose extent is known without anybody having checked it, after the
    /// two [`Flags::STATIC`] and [`Flags::HANDED`] are about. `malloc(n)` states the same fact an
    /// `alloca` states, with a different instruction stating it, and the null half is why a program
    /// has to test what it gets: a null pointer is inside no object at all, so a bounds check on one
    /// is a check that is supposed to fail.
    ///
    /// On the call rather than on the checks, which is the shape [`Flags::NOFREE`] has and not the
    /// shape the two flags above have. What has to be worked out before the pipeline starts is only
    /// which function this call names, because resolving a name takes the interner and a pass is
    /// handed a function and no names. Everything else, which is how many bytes and where the
    /// program has tested for null, is read out of the function by the pass that removes the check,
    /// and has to be: before anything has folded, `malloc(16)` is a call to `malloc` of a sign
    /// extension of a thirty two bit sixteen.
    ///
    /// What it says is an extent, and never a lifetime, which is the difference from the two flags
    /// above. A global and a caller's frame slot are alive for as long as the call runs, and an
    /// object on the heap is alive until something frees it, which may well be this same function.
    /// So a `free` between the allocation and the access leaves the lifetime check standing to
    /// report the use after free.
    ///
    /// A fact rather than a licence, in the way [`Flags::NOFREE`] is.
    pub const HEAP: Self = Self(1 << 14);

    /// The address the check this is on is about starts where the access assumes it does.
    ///
    /// The alignment conjunct of judgement J1 rides on `check_bounds`, which
    /// `spec/safe-memory/06-instrumentation.md` section 6.3 settled, so a check that goes takes the
    /// test of it away with it and `crate::discharge` will not take one out until something has
    /// answered it. Mostly it answers itself, off the `alloca` or the allocation the address was
    /// computed from and the steps taken from there. This is the case it cannot: how aligned a
    /// global is lives on the module and a pass is given one function, which is the reason
    /// [`Flags::STATIC`] exists and the same reason repeated.
    ///
    /// It says the address and not the object. A global aligned to sixteen read four bytes in at a
    /// width of four is one of these and the same global read one byte in is not, so what was
    /// worked out before the pipeline started is the offset as well as the object.
    ///
    /// A fact rather than a licence, in the way [`Flags::STATIC`] is.
    pub const ALIGNED: Self = Self(1 << 15);

    /// Every fast-math flag, which is what `-ffast-math` sets on an expression.
    pub const FAST: Self = Self(
        Self::NNAN.0
            | Self::NINF.0
            | Self::NSZ.0
            | Self::ARCP.0
            | Self::CONTRACT.0
            | Self::REASSOC.0,
    );

    /// The underlying bits, for the printer and for hashing an instruction.
    #[must_use]
    pub const fn bits(self) -> u16 {
        self.0
    }

    /// Whether nothing is set.
    #[must_use]
    pub const fn is_empty(self) -> bool {
        self.0 == 0
    }

    /// Whether every flag in `other` is set here.
    #[must_use]
    pub const fn contains(self, other: Self) -> bool {
        self.0 & other.0 == other.0
    }

    /// Both sets.
    #[must_use]
    pub const fn union(self, other: Self) -> Self {
        Self(self.0 | other.0)
    }

    /// The flags in both sets.
    ///
    /// This is what a rewrite does when it replaces two instructions with one: a licence
    /// granted on one of them and not the other is not a licence over the result.
    #[must_use]
    pub const fn intersection(self, other: Self) -> Self {
        Self(self.0 & other.0)
    }

    /// This set without the flags in `other`.
    #[must_use]
    pub const fn without(self, other: Self) -> Self {
        Self(self.0 & !other.0)
    }

    /// The flags that mean anything on that opcode.
    ///
    /// Anything outside this is a verifier failure rather than something ignored, because a
    /// flag on an instruction that does not read it is a flag somebody meant to put somewhere
    /// else.
    #[must_use]
    pub const fn legal_on(opcode: Opcode) -> Self {
        match opcode {
            Opcode::Add | Opcode::Sub | Opcode::Mul | Opcode::Shl => Self::NSW.union(Self::NUW),
            Opcode::SDiv | Opcode::UDiv | Opcode::LShr | Opcode::AShr => Self::EXACT,
            Opcode::FAdd
            | Opcode::FSub
            | Opcode::FMul
            | Opcode::FDiv
            | Opcode::FRem
            | Opcode::FNeg
            | Opcode::Fma
            | Opcode::FCmp => Self::FAST,
            Opcode::Load | Opcode::Store | Opcode::Memcpy | Opcode::Memmove | Opcode::Memset => {
                Self::VOLATILE
            }
            // On the ordered accesses as well. `volatile _Atomic int x;` is a type C allows and
            // the two words say different things: the ordering is what other threads see and the
            // qualifier is what the compiler may leave out, so an object can want both and an
            // access to one carries both.
            Opcode::AtomicLoad | Opcode::AtomicStore | Opcode::Cmpxchg | Opcode::AtomicRmw => {
                Self::VOLATILE
            }
            Opcode::InlineAsm => Self::VOLATILE,
            // On all three spellings of a call, including the indirect one. Nothing works out
            // `nofree` for a call through an address today, and the flag is legal there because
            // what it says is about the functions the call reaches rather than about how the call
            // names them, so a later analysis that knows the targets has somewhere to write it.
            //
            // `HEAP` is on the direct call alone, because what it says is worked out from the name
            // the call names and the other two spellings do not name one. A tail call is left out
            // for a second reason as well: its result leaves the function, so there is nothing here
            // that could ever be inside it.
            Opcode::Call => Self::NOFREE.union(Self::HEAP),
            Opcode::TailCall | Opcode::CallIndirect => Self::NOFREE,
            // On the three checks `rucc-safety` emits and on nothing else. What they say is about
            // the bytes a check names, so an instruction that names no bytes has no room for them.
            Opcode::CheckLive | Opcode::CheckDeriv => Self::STATIC.union(Self::HANDED),
            // `ALIGNED` on the bounds check alone, because the alignment conjunct rides on that
            // one and the other two say nothing about where an access starts.
            Opcode::CheckBounds => Self::STATIC.union(Self::HANDED).union(Self::ALIGNED),
            Opcode::Alloca | Opcode::PtrAdd => Self::NOALIAS,
            _ => Self::NONE,
        }
    }

    /// Every flag that is set, with its name, in the order the printer writes them.
    pub fn iter(self) -> impl Iterator<Item = (Self, &'static str)> {
        NAMED.iter().copied().filter(move |&(flag, _)| self.contains(flag))
    }

    /// The flag with that name, if there is one.
    #[must_use]
    pub fn from_name(name: &str) -> Option<Self> {
        NAMED.iter().find(|&&(_, named)| named == name).map(|&(flag, _)| flag)
    }
}

impl std::ops::BitOr for Flags {
    type Output = Self;

    fn bitor(self, other: Self) -> Self {
        self.union(other)
    }
}

impl std::ops::BitOrAssign for Flags {
    fn bitor_assign(&mut self, other: Self) {
        *self = self.union(other);
    }
}

impl fmt::Display for Flags {
    /// The suffix form the textual IR uses, `add.nsw`, with a leading dot on each flag and
    /// nothing at all when the set is empty.
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for (_, name) in self.iter() {
            write!(f, ".{name}")?;
        }
        Ok(())
    }
}

impl fmt::Debug for Flags {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.is_empty() {
            return f.write_str("Flags::NONE");
        }
        fmt::Display::fmt(self, f)
    }
}

/// Each flag with its name, in printing order.
static NAMED: &[(Flags, &str)] = &[
    (Flags::NSW, "nsw"),
    (Flags::NUW, "nuw"),
    (Flags::EXACT, "exact"),
    (Flags::NNAN, "nnan"),
    (Flags::NINF, "ninf"),
    (Flags::NSZ, "nsz"),
    (Flags::ARCP, "arcp"),
    (Flags::CONTRACT, "contract"),
    (Flags::REASSOC, "reassoc"),
    (Flags::VOLATILE, "volatile"),
    (Flags::NOALIAS, "noalias"),
    (Flags::NOFREE, "nofree"),
    (Flags::STATIC, "static"),
    (Flags::HANDED, "handed"),
    (Flags::HEAP, "heap"),
    (Flags::ALIGNED, "aligned"),
];

/// How strongly an atomic operation is ordered against everything around it.
///
/// These are C11's, minus `consume`, which every compiler in existence widens to `acquire`
/// because nobody can implement it as specified and the standard committee has said so.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub enum MemOrder {
    /// Not atomic at all, which is what an ordinary load or store is.
    #[default]
    NotAtomic,
    /// Atomic, with no ordering against anything else.
    Relaxed,
    /// Nothing after this in program order moves before it.
    Acquire,
    /// Nothing before this in program order moves after it.
    Release,
    /// Both, for a read-modify-write.
    AcqRel,
    /// Both, and a single total order over every sequentially consistent operation.
    SeqCst,
}

impl MemOrder {
    /// The textual form.
    #[must_use]
    pub const fn name(self) -> &'static str {
        match self {
            Self::NotAtomic => "not_atomic",
            Self::Relaxed => "relaxed",
            Self::Acquire => "acquire",
            Self::Release => "release",
            Self::AcqRel => "acq_rel",
            Self::SeqCst => "seq_cst",
        }
    }

    /// The ordering with that name, if there is one.
    #[must_use]
    pub fn from_name(name: &str) -> Option<Self> {
        Self::all().find(|order| order.name() == name)
    }

    /// Every ordering, weakest first.
    pub fn all() -> impl Iterator<Item = Self> {
        [Self::NotAtomic, Self::Relaxed, Self::Acquire, Self::Release, Self::AcqRel, Self::SeqCst]
            .into_iter()
    }

    /// Whether this ordering can be asked of a load.
    ///
    /// A load cannot release, because there is nothing it published.
    #[must_use]
    pub const fn is_valid_for_load(self) -> bool {
        matches!(self, Self::Relaxed | Self::Acquire | Self::SeqCst)
    }

    /// Whether this ordering can be asked of a store.
    ///
    /// A store cannot acquire, because it read nothing to synchronise with.
    #[must_use]
    pub const fn is_valid_for_store(self) -> bool {
        matches!(self, Self::Relaxed | Self::Release | Self::SeqCst)
    }

    /// Whether this ordering can be asked of a read-modify-write, which is any of them.
    #[must_use]
    pub const fn is_valid_for_rmw(self) -> bool {
        !matches!(self, Self::NotAtomic)
    }

    /// Whether this ordering publishes everything before it, which is the release half.
    ///
    /// Asked by the race detector rather than by the back end. A release is a synchronization edge
    /// in the sense of `spec/safe-memory/09-type-init-and-races.md` section 9.5, so it is where a
    /// thread's clock has to be written down for whoever takes the other end.
    #[must_use]
    pub const fn is_release(self) -> bool {
        matches!(self, Self::Release | Self::AcqRel | Self::SeqCst)
    }

    /// Whether this ordering takes everything published before it, which is the acquire half.
    ///
    /// The other end of [`MemOrder::is_release`]. `acq_rel` and `seq_cst` answer yes to both, which
    /// is what makes a read-modify-write one edge in and one edge out.
    #[must_use]
    pub const fn is_acquire(self) -> bool {
        matches!(self, Self::Acquire | Self::AcqRel | Self::SeqCst)
    }
}

impl fmt::Display for MemOrder {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(self.name())
    }
}

/// Which operation an `atomic_rmw` performs.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum RmwOp {
    /// Replace, returning the old value.
    Xchg,
    /// Integer addition.
    Add,
    /// Integer subtraction.
    Sub,
    /// Bitwise and.
    And,
    /// Bitwise and, then complement, which is the one hardware sometimes has natively.
    Nand,
    /// Bitwise or.
    Or,
    /// Bitwise exclusive or.
    Xor,
    /// Signed maximum.
    SMax,
    /// Signed minimum.
    SMin,
    /// Unsigned maximum.
    UMax,
    /// Unsigned minimum.
    UMin,
    /// Floating point addition.
    FAdd,
    /// Floating point subtraction.
    FSub,
}

impl RmwOp {
    /// The textual form.
    #[must_use]
    pub const fn name(self) -> &'static str {
        match self {
            Self::Xchg => "xchg",
            Self::Add => "add",
            Self::Sub => "sub",
            Self::And => "and",
            Self::Nand => "nand",
            Self::Or => "or",
            Self::Xor => "xor",
            Self::SMax => "smax",
            Self::SMin => "smin",
            Self::UMax => "umax",
            Self::UMin => "umin",
            Self::FAdd => "fadd",
            Self::FSub => "fsub",
        }
    }

    /// The operation with that name, if there is one.
    #[must_use]
    pub fn from_name(name: &str) -> Option<Self> {
        Self::all().find(|op| op.name() == name)
    }

    /// Every operation.
    pub fn all() -> impl Iterator<Item = Self> {
        [
            Self::Xchg,
            Self::Add,
            Self::Sub,
            Self::And,
            Self::Nand,
            Self::Or,
            Self::Xor,
            Self::SMax,
            Self::SMin,
            Self::UMax,
            Self::UMin,
            Self::FAdd,
            Self::FSub,
        ]
        .into_iter()
    }

    /// Whether this operates on a floating point value rather than an integer.
    #[must_use]
    pub const fn is_float(self) -> bool {
        matches!(self, Self::FAdd | Self::FSub)
    }
}

impl fmt::Display for RmwOp {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(self.name())
    }
}

/// What kind of storage a memory safety instance is, which is `class` of
/// `spec/safe-memory/04-safety-model.md` section 4.1.
///
/// It is on `meta_begin` because judgement J4 writes it when the instance is created, and the
/// one place it is read afterwards is J6: `free` is permitted on an allocated instance and on
/// no other kind, which is what makes freeing a stack address a report rather than a crash in
/// the allocator.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum StorageClass {
    /// A global or a static local, which lives as long as the program does.
    Static,
    /// A local, which lives as long as its block does.
    Automatic,
    /// Storage an allocator handed out, and the only kind `free` may be given.
    Allocated,
    /// A mapping, from `mmap` or its equivalent.
    Mapped,
    /// A device register window, where a read is not a read of anything the program wrote.
    Mmio,
    /// Storage a device owns, which is what a DMA buffer is while the transfer runs.
    Device,
    /// A function, which is what the address of one points at.
    Function,
    /// A string or compound literal, which the implementation may have merged with another.
    Literal,
}

impl StorageClass {
    /// The textual form.
    #[must_use]
    pub const fn name(self) -> &'static str {
        match self {
            Self::Static => "static",
            Self::Automatic => "automatic",
            Self::Allocated => "allocated",
            Self::Mapped => "mapped",
            Self::Mmio => "mmio",
            Self::Device => "device",
            Self::Function => "function",
            Self::Literal => "literal",
        }
    }

    /// The class with that name, if there is one.
    #[must_use]
    pub fn from_name(name: &str) -> Option<Self> {
        Self::all().find(|class| class.name() == name)
    }

    /// Every class, in the order document 04 lists them.
    pub fn all() -> impl Iterator<Item = Self> {
        [
            Self::Static,
            Self::Automatic,
            Self::Allocated,
            Self::Mapped,
            Self::Mmio,
            Self::Device,
            Self::Function,
            Self::Literal,
        ]
        .into_iter()
    }
}

impl fmt::Display for StorageClass {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(self.name())
    }
}

/// Who a range of memory belongs to while it is out of the monitor's authority.
///
/// Judgement J7 of `spec/safe-memory/04-safety-model.md`, which is the one that has no analogue
/// in any existing tool. A range handed to a device is a range the program must not touch until
/// it comes back, and saying which of the three it went to is what lets the report name what the
/// program broke rather than only that it broke something.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Owner {
    /// A device, which is what the DMA ownership contract hands a buffer to.
    Device,
    /// Code compiled without the instrumentation, per document 10.
    Uninstrumented,
    /// The kernel, across a system call that writes into the range.
    Kernel,
}

impl Owner {
    /// The textual form.
    #[must_use]
    pub const fn name(self) -> &'static str {
        match self {
            Self::Device => "device",
            Self::Uninstrumented => "uninstrumented",
            Self::Kernel => "kernel",
        }
    }

    /// The owner with that name, if there is one.
    #[must_use]
    pub fn from_name(name: &str) -> Option<Self> {
        Self::all().find(|owner| owner.name() == name)
    }

    /// Every owner.
    pub fn all() -> impl Iterator<Item = Self> {
        [Self::Device, Self::Uninstrumented, Self::Kernel].into_iter()
    }
}

impl fmt::Display for Owner {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(self.name())
    }
}

/// What a [`crate::Opcode::Prefetch`] says about the access it is a hint for.
///
/// Two facts, both of them out of `__builtin_prefetch`'s own arguments, and neither of them a
/// promise. A prefetch that says the wrong thing, or a target that ignores it, changes how long
/// the program takes and nothing else, so nothing downstream may read either of these as a fact
/// about what the program will do.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub struct PrefetchHint {
    /// Whether the access being prepared for will write, which is the second argument.
    ///
    /// It matters on a machine that has separate instructions for the two, because a line fetched
    /// for writing is fetched in a state that does not have to be asked for again when the write
    /// happens. x86-64 has one for it, `prefetchw`, and only on a processor that says it has it,
    /// so this reaches the back end and the back end decides.
    pub write: bool,
    /// How much of the data will still be wanted after the access, from zero for none of it to
    /// three for all of it, which is the third argument.
    ///
    /// Three is the default and is what a program that writes the one argument form means. Zero is
    /// the one that is a different instruction rather than a different cache level on x86-64: it
    /// says the line is wanted once, so `prefetchnta` fetches it in a way that does not push
    /// anything else out.
    pub locality: u8,
}

impl PrefetchHint {
    /// The highest locality, which is the one the one argument form of the builtin means.
    pub const MOST: u8 = 3;

    /// The hint a call that said nothing beyond the address means, which is a read that will want
    /// all of the data afterwards.
    #[must_use]
    pub const fn read() -> Self {
        Self { write: false, locality: Self::MOST }
    }

    /// The word for which half of the access this is about, which is how it prints.
    #[must_use]
    pub const fn access(self) -> &'static str {
        if self.write { "write" } else { "read" }
    }

    /// Whether the locality is one of the four the builtin has.
    ///
    /// Asked by the verifier. Nothing here clamps an out of range one, because a number this did
    /// not come from `__builtin_prefetch`'s third argument is a bug in whoever built the
    /// instruction rather than something a program wrote.
    #[must_use]
    pub const fn is_valid(self) -> bool {
        self.locality <= Self::MOST
    }
}

impl fmt::Display for PrefetchHint {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}, locality {}", self.access(), self.locality)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn a_flag_set_is_two_bytes() {
        assert_eq!(size_of::<Flags>(), 2);
    }

    #[test]
    fn every_flag_has_a_name_and_finds_it_again() {
        for &(flag, name) in NAMED {
            assert_eq!(Flags::from_name(name), Some(flag), "{name}");
            assert_eq!(flag.to_string(), format!(".{name}"));
        }
        assert_eq!(Flags::from_name("poison"), None);
        assert_eq!(Flags::from_name(""), None);
    }

    #[test]
    fn no_two_flags_share_a_bit() {
        let mut seen = 0u16;
        for &(flag, name) in NAMED {
            assert_eq!(flag.bits().count_ones(), 1, "{name} is not one bit");
            assert_eq!(seen & flag.bits(), 0, "{name} shares a bit");
            seen |= flag.bits();
        }
    }

    #[test]
    fn fast_is_exactly_the_six_fast_math_flags() {
        let named: Vec<&str> = Flags::FAST.iter().map(|(_, name)| name).collect();
        assert_eq!(named, ["nnan", "ninf", "nsz", "arcp", "contract", "reassoc"]);
        assert!(!Flags::FAST.contains(Flags::NSW));
        assert!(!Flags::FAST.contains(Flags::VOLATILE));
    }

    #[test]
    fn the_empty_set_prints_as_nothing() {
        assert!(Flags::NONE.is_empty());
        assert_eq!(Flags::NONE.to_string(), "");
        assert_eq!(Flags::NONE.iter().count(), 0);
    }

    #[test]
    fn flags_print_as_the_suffix_the_textual_form_uses() {
        assert_eq!((Flags::NSW | Flags::NUW).to_string(), ".nsw.nuw");
        // Whatever order they were combined in, the printer writes them in one order, which
        // is what a byte for byte round trip needs.
        assert_eq!((Flags::NUW | Flags::NSW).to_string(), ".nsw.nuw");
    }

    #[test]
    fn intersecting_is_what_a_rewrite_keeps() {
        let one = Flags::NSW | Flags::NUW;
        let other = Flags::NSW;
        assert_eq!(one.intersection(other), Flags::NSW);
        assert_eq!(one.without(Flags::NSW), Flags::NUW);
        assert!(one.contains(Flags::NSW));
        assert!(!other.contains(Flags::NUW));
    }

    #[test]
    fn wrapping_flags_go_on_arithmetic_and_nowhere_else() {
        assert!(Flags::legal_on(Opcode::Add).contains(Flags::NSW));
        assert!(Flags::legal_on(Opcode::Shl).contains(Flags::NUW));
        assert!(!Flags::legal_on(Opcode::Add).contains(Flags::EXACT));
        assert!(!Flags::legal_on(Opcode::FAdd).contains(Flags::NSW));
        assert!(!Flags::legal_on(Opcode::Load).contains(Flags::NSW));
        assert!(Flags::legal_on(Opcode::SDiv).contains(Flags::EXACT));
        assert!(Flags::legal_on(Opcode::FMul).contains(Flags::CONTRACT));
        assert!(Flags::legal_on(Opcode::Store).contains(Flags::VOLATILE));
        assert!(Flags::legal_on(Opcode::Jump).is_empty());
    }

    #[test]
    fn nofree_goes_on_a_call_and_nowhere_else() {
        for opcode in [Opcode::Call, Opcode::TailCall, Opcode::CallIndirect] {
            assert!(Flags::legal_on(opcode).contains(Flags::NOFREE), "{opcode}");
        }
        for opcode in Opcode::all() {
            let call = matches!(opcode, Opcode::Call | Opcode::TailCall | Opcode::CallIndirect);
            assert_eq!(Flags::legal_on(opcode).contains(Flags::NOFREE), call, "{opcode}");
        }
        // It is a fact rather than a licence, so it is not part of what `-ffast-math` grants and
        // it is not something a rewrite over arithmetic could carry onto a call.
        assert!(!Flags::FAST.contains(Flags::NOFREE));
    }

    #[test]
    fn static_goes_on_a_safety_check_and_nowhere_else() {
        for opcode in [Opcode::CheckBounds, Opcode::CheckLive, Opcode::CheckDeriv] {
            assert!(Flags::legal_on(opcode).contains(Flags::STATIC), "{opcode}");
            assert!(Flags::legal_on(opcode).contains(Flags::HANDED), "{opcode}");
        }
        for opcode in Opcode::all() {
            let check =
                matches!(opcode, Opcode::CheckBounds | Opcode::CheckLive | Opcode::CheckDeriv);
            assert_eq!(Flags::legal_on(opcode).contains(Flags::STATIC), check, "{opcode}");
            assert_eq!(Flags::legal_on(opcode).contains(Flags::HANDED), check, "{opcode}");
        }
        // The other fact, and they are legal on disjoint sets of opcodes, so an instruction that
        // carries one can never be read as carrying the other.
        assert!(!Flags::legal_on(Opcode::Call).contains(Flags::STATIC));
        assert!(!Flags::legal_on(Opcode::CheckBounds).contains(Flags::NOFREE));
    }

    #[test]
    fn heap_goes_on_the_one_call_that_names_who_it_calls() {
        assert!(Flags::legal_on(Opcode::Call).contains(Flags::HEAP));
        for opcode in Opcode::all() {
            let direct = opcode == Opcode::Call;
            assert_eq!(Flags::legal_on(opcode).contains(Flags::HEAP), direct, "{opcode}");
        }
        // It rides on a call the way `nofree` does rather than on a check the way the other two
        // facts do, and a check has no room for it.
        assert!(!Flags::legal_on(Opcode::CheckBounds).contains(Flags::HEAP));
        assert!(!Flags::legal_on(Opcode::TailCall).contains(Flags::HEAP));
    }

    #[test]
    fn every_flag_is_legal_on_something() {
        for &(flag, name) in NAMED {
            assert!(
                Opcode::all().any(|op| Flags::legal_on(op).contains(flag)),
                "{name} is legal nowhere, so nothing can ever set it"
            );
        }
    }

    #[test]
    fn a_load_cannot_release_and_a_store_cannot_acquire() {
        assert!(MemOrder::Acquire.is_valid_for_load());
        assert!(!MemOrder::Release.is_valid_for_load());
        assert!(!MemOrder::AcqRel.is_valid_for_load());
        assert!(MemOrder::Release.is_valid_for_store());
        assert!(!MemOrder::Acquire.is_valid_for_store());
        assert!(MemOrder::SeqCst.is_valid_for_load());
        assert!(MemOrder::SeqCst.is_valid_for_store());
    }

    #[test]
    fn the_two_halves_of_an_edge_are_the_orderings_that_carry_one() {
        let releases: Vec<&str> =
            MemOrder::all().filter(|order| order.is_release()).map(MemOrder::name).collect();
        assert_eq!(releases, ["release", "acq_rel", "seq_cst"]);
        let acquires: Vec<&str> =
            MemOrder::all().filter(|order| order.is_acquire()).map(MemOrder::name).collect();
        assert_eq!(acquires, ["acquire", "acq_rel", "seq_cst"]);
        // Relaxed is atomic and is not an edge, which is the distinction the race detector rests
        // on: it says the word does not tear and it says nothing about what happened around it.
        assert!(!MemOrder::Relaxed.is_release());
        assert!(!MemOrder::Relaxed.is_acquire());
    }

    #[test]
    fn not_atomic_is_valid_for_no_atomic_operation() {
        assert!(!MemOrder::NotAtomic.is_valid_for_load());
        assert!(!MemOrder::NotAtomic.is_valid_for_store());
        assert!(!MemOrder::NotAtomic.is_valid_for_rmw());
        assert_eq!(MemOrder::default(), MemOrder::NotAtomic);
    }

    #[test]
    fn every_ordering_and_operation_finds_its_name_again() {
        for order in MemOrder::all() {
            assert_eq!(MemOrder::from_name(order.name()), Some(order));
        }
        for op in RmwOp::all() {
            assert_eq!(RmwOp::from_name(op.name()), Some(op));
        }
        assert_eq!(MemOrder::from_name("consume"), None);
        assert_eq!(RmwOp::from_name("fmul"), None);
    }

    #[test]
    fn the_floating_read_modify_writes_are_the_two_that_have_one() {
        let floats: Vec<&str> = RmwOp::all().filter(|op| op.is_float()).map(RmwOp::name).collect();
        assert_eq!(floats, ["fadd", "fsub"]);
    }

    #[test]
    fn every_storage_class_and_owner_finds_its_name_again() {
        for class in StorageClass::all() {
            assert_eq!(StorageClass::from_name(class.name()), Some(class));
        }
        for owner in Owner::all() {
            assert_eq!(Owner::from_name(owner.name()), Some(owner));
        }
        // The eight of document 04 and no more. `heap` is what a reader would guess and the
        // model does not have it, since what the allocator hands out is `allocated`.
        assert_eq!(StorageClass::all().count(), 8);
        assert_eq!(StorageClass::from_name("heap"), None);
        assert_eq!(Owner::from_name("hardware"), None);
    }
}