rucc_opt/

simplify.rs

//! Peephole rewrites: a small pattern of instructions becomes a smaller one.
//!
//! The third pass, and the one that will eventually not exist. Section 9.3 of
//! `spec/09-optimizer.md` says the value level optimizer is an acyclic e-graph, and that an
//! e-graph replaces what would otherwise be a folding pass, a peephole pass, a GVN pass, a
//! reassociation pass and an instcombine pass, all with a pass ordering problem between them.
//! This is the peephole pass, written now because the e-graph is a milestone away and because
//! there is a rewrite that unblocks twelve lowering rules today.
//!
//! Every rewrite here has to survive being moved into the rule set later, so each one is stated
//! as a pattern and a replacement in its own function and nothing shares state with anything.
//!
//! # The rewrites
//!
//! Two kinds. The rules of `rules/`, one file per tier, which are matched against every
//! instruction and are where anything new goes, and one rewrite written out by hand below them.
//!
//! ## The rules
//!
//! Four tiers of `spec/optimizer/13-rewrite-rules.md` section 13.4 so far.
//!
//! Tier one is the identities. Adding nothing, multiplying by one, and'ing a value with itself.
//! None of them needs anything known about the operands and each leaves a term strictly smaller
//! than the one it replaced.
//!
//! Tier two is the strength reductions, which swap an operation for a cheaper one rather than
//! taking one away: multiplying by two is an addition, and multiplying or dividing by minus one is
//! a subtraction from nothing. Tier one is tried first because losing an operation beats swapping
//! one.
//!
//! Tier four is the width rules, the algebra of truncation and extension. Truncating an extension
//! back to the width it came from is the value that was there before either of them, and an
//! extension of an extension is one extension. This is the tier
//! the specification says pays on real C, and the reason is C rather than anything about this
//! compiler: the integer promotions widen nearly every operand of nearly every expression, and
//! most of those widenings compute something the instruction after them throws away.
//!
//! Tier three is the canonicalisations, which put the constant of a commutative operation on the
//! right. They make nothing smaller and nothing faster. What they do is halve how many ways a term
//! can be written, so that every rule above them needs one variant where it needs two today, and
//! so that hash consing can see two spellings of one expression as one. They are tried last rather
//! than third, because rearranging a term is only worth doing when no rule that improves it fires.
//!
//! Every rule in all four has been proved against `crates/rucc-ir/rules/ir.model` by
//! `rucc-verify` before it may be used.
//!
//! Which plans a tier is matched under belongs to the tier. Tiers one and two are matched with
//! either operand offered as a number, since a rule about a constant should fire whichever side it
//! was written on. Tier three is matched with the left operand offered as a number and the right
//! one refused if it is one, which is what makes a rule that moves the constant across fire once
//! rather than forever. Tier four is matched with the operand expanded into the instruction that
//! computed it, which is what a rule about two instructions at once needs and what none of the
//! others wants.
//!
//! What a rule leaves behind is one of four things. `(value.iN x)` means the result is a value
//! the function already has, so every use of the result is pointed at that value and the
//! instruction is left for [`crate::dce`]. `(iconst.iN k)` means the result is a constant, and the
//! instruction becomes that constant where it stands, which keeps the result value and is why
//! nothing else has to be rewritten for that half. An instruction means this one becomes that one
//! where it stands, which keeps the result value for the same reason, and an operand of it the
//! rule wrote as a number gets an `iconst` in front of the instruction to hold it. A conversion is
//! that same rewrite in place with one operand instead of two, and it is its own case because a
//! conversion is the one instruction whose operand is not the width of its result.
//!
//! ## The one written by hand
//!
//! An exclusive or of a comparison with an `i1` of all ones is that comparison with the opposite
//! predicate. That is issue 379, and it is worth more than the instruction it saves.
//!
//! C spells eight of the sixteen floating point predicates. The six relational and equality
//! operators give the six ordered ones, `!=` gives `une`, and `__builtin_isunordered` gives `uno`.
//! The other eight are what the negation of one of those means, and the front end writes a
//! negation as an exclusive or rather than as a flipped predicate, so `!(x < y)` lowers to an
//! `fcmp olt` and an `xor` where the machine has an `fcmp uge`. Twelve rules in the x86-64 rule
//! set are written on those predicates and none of them has ever fired, over the whole torture
//! suite at every optimization level, because no IR that reaches selection contains one.
//!
//! The integer case comes with it. `!(a < b)` on integers is the same shape, the same rewrite and
//! the same saving, and leaving it out because the coverage report did not complain about it would
//! be picking the rewrite by what measures it rather than by what it does.
//!
//! # Why it needs dead code elimination after it
//!
//! The rewrite turns the `xor` into the comparison and leaves the original comparison where it
//! was, used by nothing when the negation was its only reader. Rewriting in place keeps the
//! result value, so every use of it is already correct and there is nothing to rewrite, and what
//! is left over is exactly what [`crate::dce`] takes out. That is why the pipeline runs the two in
//! this order, and it is why the pass before the dead code eliminator was written first.
//!
//! An identity that produces a value leaves the same kind of litter for the same reason. The
//! instruction it fired on reads what it always read and nothing reads it, so it is dead, and
//! taking it out here would mean deciding whether its operands are still read by anything, which
//! is the question the dead code eliminator answers for the whole function at once.

use std::collections::HashMap;
use std::sync::OnceLock;

use rucc_ir::term::{PLAIN, Plan, Shown, Term, Terms};
use rucc_ir::{Block, Def, Extra, Flags, Func, Imm, Inst, InstData, IntPred, Opcode, Type, Value};

use crate::rules::{Match, Piece, Table, canonical, compare, identities, strength, width};
use crate::uses::{count, substitute};
use crate::{Analyses, Analysis, Fuel, Pass, Preserved, Stats};

/// Recorded once for each negation folded into the comparison under it.
const FLIPPED: &str = "comparison negated by an exclusive or rewritten as the opposite comparison";

/// Recorded for a negation that would have folded if there had been fuel for it.
const NO_FUEL: &str = "negated comparison left alone, the pass ran out of fuel";

/// Recorded for a rule that would have fired if there had been fuel for it.
const NO_FUEL_RULE: &str = "rewrite left alone, the pass ran out of fuel";

/// How each operand of an instruction is shown to the matcher, and in what order the ways are
/// tried.
///
/// The two with a constant come first, because a rule about a number is the more specific one and
/// an operand that is not a constant declines it at the first node of the trie. Nothing here
/// expands an operand into the instruction that computed it, since no tier one identity is about
/// two instructions at once.
const PLANS: [Plan; 3] =
    [[Shown::Reg, Shown::Const, Shown::Reg], [Shown::Const, Shown::Reg, Shown::Reg], PLAIN];

/// How the operands are shown to a canonicalisation, which is the one plan tier three is matched
/// under.
///
/// A canonicalisation moves the constant to the right, so the left operand has to be the number
/// and the right one has to be something that is not, or the rule swaps a pair of constants back
/// and forth until the pass runs out of fuel. [`Shown::Var`] is what says the right one is not a
/// number. The plans above cannot be reused here for exactly that reason: the second of them
/// shows a constant left operand as a number and a constant right operand as a register, which is
/// the cycling match.
const CANONICAL: [Plan; 1] = [[Shown::Const, Shown::Var, Shown::Reg]];

/// How the operands are shown to a width rule, which is the one plan tier four is matched under.
///
/// Every rule in that tier is about two instructions at once, a conversion and the conversion or
/// value under it, so the operand it is about has to be shown as the instruction that computed it
/// rather than as a register holding the answer. That is [`Shown::Expand`], and it is the first
/// plan here to use it.
///
/// One operand, because every instruction the tier matches has one. The other two entries are
/// never read and say [`Shown::Reg`] because that is what an operand nobody asks about is.
const EXPAND: [Plan; 1] = [[Shown::Expand, Shown::Reg, Shown::Reg]];

/// How the operands are shown to a comparison rule, which is the one plan tier five is matched
/// under.
///
/// Every rule in that tier compares something against a constant, and writes the constant on the
/// right, so the right operand has to be shown as a number and the left one has to be shown as a
/// register. That is the first of [`PLANS`] and this is the same triple, spelled again rather than
/// borrowed, because the tier is matched under one plan and the other two would be tried for
/// nothing: a comparison with the constant on the left matches no rule here, and neither does one
/// with no constant at all.
///
/// The constant on the left is not the missing half of the tier. A comparison is not commutative,
/// so `0 < x` is not `x < 0` with the operands swapped, it is `x > 0`, and turning the first into
/// the second is a canonicalisation that belongs in tier three rather than four more rules here.
const COMPARE: [Plan; 1] = [[Shown::Reg, Shown::Const, Shown::Reg]];

/// The rule tables, one per tier, in the order they are tried, each with the plans it is matched
/// under.
///
/// Tier one first, because an identity takes an operation away and a strength reduction swaps one
/// for another, so a term both have something to say about is better off losing the operation.
/// Tier four after those two and tier three last, because a canonicalisation only makes a term
/// easier for another rule to be about and there is no reason to reach for it while a rule that
/// improves the code still fires. Nothing turns on the order of those last two anyway: tier three
/// is about a commutative operation with a constant in it and tier four is about a conversion, so
/// no instruction is one both have something to say about.
///
/// The plans belong to the table rather than to the loop because a tier is written against them.
/// Tier three is only correct under the one plan that refuses a constant on the right, and a
/// table matched under a plan it was not written for is a table whose rules mean something else.
/// Tier four is the other way round: its rules mean nothing at all under a plan that does not
/// expand, since the second level of every one of its patterns is an instruction.
///
/// Tier five sits where it does because nothing turns on it either. It is the only table about a
/// comparison and no other table mentions one, so there is no instruction two of them have
/// something to say about and no order in which one of them gets there first.
const TABLES: [(&Table, &[Plan]); 5] = [
    (&identities::TABLE, &PLANS),
    (&strength::TABLE, &PLANS),
    (&width::TABLE, &EXPAND),
    (&compare::TABLE, &COMPARE),
    (&canonical::TABLE, &CANONICAL),
];

/// The pass. It holds nothing, because a peephole needs to know nothing beyond the pattern.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Simplify;

impl Pass for Simplify {
    fn name(&self) -> &'static str {
        "simplify"
    }

    fn describe(&self) -> &'static str {
        "the identities, the strength reductions, the canonicalisations, and a negated comparison \
         as the opposite one"
    }

    fn preserves(&self) -> Preserved {
        // Everything about the shape of the function. No block is added, none is removed and no
        // edge moves, so the graph and everything built out of it stand.
        //
        // The liveness does not, and that is the whole of the difference. An identity that
        // produces a value points every reader of one value at another, which is one more place
        // the second is live and one fewer the first is, and the same is true of the negation
        // below, which reads the comparison's operands where it used to read its result.
        //
        // A rule that writes an instruction with a constant in it puts one in the block, and that
        // is still the same answer. It adds a value nothing else mentions, in the block it is
        // read in, and it ends every path it starts on, so nothing about the shape of the
        // function moves and the only analysis with something new to say about it is the one
        // already given up.
        Preserved::ALL.without(Analysis::Liveness)
    }

    fn run(&self, func: &mut Func, _an: &mut Analyses, fuel: &mut Fuel) -> Stats {
        let mut stats = Stats::new();
        // What a rule that produced a value decided, applied to the whole function at the end.
        // Rewriting each one where it is found would be a walk over every instruction for every
        // rewrite, and there is nothing to be gained by it: what a pattern asks about is the
        // instruction and its operands, and neither changes under a redirection.
        let mut forward: HashMap<Value, Value> = HashMap::new();
        // Who reads what, so that an instruction nothing reads is left alone. A rule that fires
        // on one changes no program, because what it does is point the readers somewhere else and
        // there are none, and it would still spend fuel and still report having optimized
        // something. That matters here more than it would in a pass that runs once: this pass is
        // named twice in every pipeline above `-O0`, an identity it takes stays in the function
        // until dead code elimination removes it, and without this the second run would rewrite
        // everything the first run did all over again and say so.
        //
        // Stale by design. It is what the function looked like when this run started, and a
        // rewrite below only ever removes readers, so a value this says nothing reads is a value
        // nothing reads.
        let uses = count(func);
        let dead = |func: &Func, inst: Inst| match func[inst].first_result {
            Some(result) => uses[result.index()] == 0,
            None => false,
        };
        for block in func.blocks().collect::<Vec<Block>>() {
            for inst in func.insts(block).collect::<Vec<Inst>>() {
                if dead(func, inst) {
                    continue;
                }
                if let Some(flip) = negated_comparison(func, inst) {
                    if !fuel.take() {
                        // Out of fuel, which stops the transforming rather than the looking, the
                        // same way the other two passes treat it. The walk is the same walk at
                        // every fuel setting, which is what makes bisecting over it monotonic.
                        stats.missed(NO_FUEL);
                        continue;
                    }
                    let args = func.push_values(&[flip.lhs, flip.rhs]);
                    let data = &mut func[inst];
                    data.opcode = flip.opcode;
                    data.flags = flip.flags;
                    data.args = args;
                    data.extra = flip.extra;
                    stats.optimized(FLIPPED);
                    continue;
                }
                let Some((rewrite, pattern)) = identity(func, inst) else { continue };
                if !fuel.take() {
                    stats.missed(NO_FUEL_RULE);
                    continue;
                }
                match rewrite {
                    Rewrite::Value(value) => {
                        let result = func[inst].first_result.expect("the rule matched a result");
                        forward.insert(result, value);
                    }
                    Rewrite::Constant(number) => become_constant(func, inst, number),
                    Rewrite::Built { opcode, pred, lhs, rhs } => {
                        become_instruction(func, inst, opcode, pred, lhs, rhs);
                    }
                    Rewrite::Converted { opcode, from } => {
                        become_conversion(func, inst, opcode, from);
                    }
                }
                stats.optimized(pattern);
            }
        }
        if !forward.is_empty() {
            substitute(func, &forward);
        }
        stats
    }
}

/// What a rule says an instruction's result is instead.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Rewrite {
    /// A value the function already has, which every reader of the result is pointed at.
    Value(Value),
    /// A number, which the instruction becomes where it stands.
    Constant(i128),
    /// Another instruction, which this one becomes where it stands.
    Built {
        /// What it is.
        opcode: Opcode,
        /// Which comparison it is, when it is one.
        ///
        /// The predicate is not part of the opcode. Every one of the ten integer comparisons is
        /// `ICmp` and the predicate is beside it, so an opcode on its own does not say what a
        /// rule asked for, and a rule that wrote `icmp_sge` and got the predicate of the
        /// instruction it replaced would compute the opposite rather than something else.
        pred: Option<IntPred>,
        /// Its left operand.
        lhs: Operand,
        /// Its right operand.
        rhs: Operand,
    },
    /// A conversion, which this one becomes where it stands.
    ///
    /// Separate from [`Rewrite::Built`] rather than one variant with a list of operands, because a
    /// conversion is the one instruction a rule writes whose operand is not the width of its
    /// result. That is what makes it the one whose operand cannot be a number the rule wrote:
    /// there would be no width to give the constant, and every rule that writes one of these
    /// writes a value the pattern bound.
    Converted {
        /// Which of the three it is.
        opcode: Opcode,
        /// What it converts, which is always a value the pattern bound.
        from: Value,
    },
}

/// One operand of an instruction a rule writes.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Operand {
    /// A value the pattern bound.
    Value(Value),
    /// A number the rule wrote, which needs an `iconst` in front of the instruction before it is
    /// an operand at all, because an operand in this IR is a value and a number is not one until
    /// something defines it.
    Constant {
        /// The number.
        number: i128,
        /// How wide it is, which is the width the `iconst.iN` head named.
        ///
        /// Taken from the rule rather than from the instruction's result, because the two are
        /// the same width for everything above and are not for a comparison: the result of one
        /// is a single bit and its operands are as wide as what was compared. A constant built
        /// at the result's width would be a one bit zero standing where a thirty two bit one
        /// was asked for.
        bits: u32,
    },
}

/// The rule that fires on this instruction, and the pattern it came from.
///
/// The plans are tried in order and the first that matches wins. A plan is how the operands are
/// shown rather than what they are, so trying three of them is three walks over a trie, each of
/// which fails in its first node or two when the instruction is not one any rule is about.
fn identity(func: &Func, inst: Inst) -> Option<(Rewrite, &'static str)> {
    let result = func[inst].first_result?;
    for (table, plan) in
        TABLES.into_iter().flat_map(|(table, plans)| plans.iter().map(move |&plan| (table, plan)))
    {
        let terms = Terms::new(func, inst, plan);
        let Some(found) = table.find(&terms, Term::Root) else { continue };
        let rule = table.rule(&found);
        let rewrite = match rule.replacement {
            // A value the pattern bound, which is a register because that is the only thing a
            // `value.iN` binds.
            [Piece::App { head, arity: 1 }, Piece::Var { index, .. }]
                if head.starts_with("value.") =>
            {
                match found.bindings.get(*index) {
                    Some(&Term::Reg(value)) => Rewrite::Value(value),
                    _ => continue,
                }
            }
            // A constant written in the rule. Only at a width the instruction's result has, which
            // it always does: an `iconst.iN` names an integer width and a rule is proved at the
            // width it is written at.
            [Piece::App { head, arity: 1 }, Piece::Int(number)]
                if head.starts_with("iconst.") && func[result].ty.is_int() =>
            {
                Rewrite::Constant(*number)
            }
            // An instruction the rule writes, which this one becomes. That is the third shape and
            // the last one: a replacement deeper than one instruction would need somewhere to put
            // the ones under it, and a rule that wanted it can be written as two rules that each
            // leave one.
            pieces => match built(pieces, &found) {
                Some(rewrite) => rewrite,
                // Any other shape, which no rule in the file has. A test below says so, because a
                // rule that fell through here would be a rule that never fires and nothing would
                // say it had stopped.
                None => continue,
            },
        };
        return Some((rewrite, rule.pattern));
    }
    None
}

/// The instruction a rule writes, out of the pieces its replacement flattened into.
///
/// Two operands under a head that names an opcode, each of them either a value the pattern bound
/// or a number the rule wrote. Anything else is nothing this pass can build, and the answer to
/// one is that the rule does not fire, which the test over the whole table turns into a failure
/// rather than a silence.
fn built(pieces: &'static [Piece], found: &Match<Term>) -> Option<Rewrite> {
    if let Some(rewrite) = converted(pieces, found) {
        return Some(rewrite);
    }
    let [Piece::App { head, arity: 2 }, rest @ ..] = pieces else { return None };
    let opcode = opcode_of(head)?;
    // The predicate comes from the same head the opcode did, so a rule whose replacement this
    // pass can build is a rule written in the vocabulary it matched with, predicate and all.
    let pred = rucc_ir::term::int_pred(head);
    if (opcode == Opcode::ICmp) != pred.is_some() {
        // A comparison whose head names no predicate, or a predicate on something that is not a
        // comparison. Neither is a head the vocabulary produces, so neither is a rule anybody
        // wrote, and building the instruction anyway would mean guessing at one of the two.
        return None;
    }
    let (lhs, rest) = operand(rest, found)?;
    let (rhs, rest) = operand(rest, found)?;
    rest.is_empty().then_some(Rewrite::Built { opcode, pred, lhs, rhs })
}

/// The conversion a rule writes, if it wrote one.
///
/// Three heads rather than any head of one operand, because the width rules are the only tier that
/// writes an instruction with one, and being specific is what keeps this from claiming a
/// replacement it cannot build. A `value.iN` or an `iconst.iN` is also a head of one operand and
/// neither is an instruction, and [`identity`] has already dealt with both by the time anything
/// gets here, so a test would not catch the day one slipped past.
///
/// The operand is a value the pattern bound, and nothing else. A number would need a width to be
/// written at and the result's width is the wrong one for a conversion, which is the whole reason
/// this is separate from [`built`].
fn converted(pieces: &'static [Piece], found: &Match<Term>) -> Option<Rewrite> {
    let [Piece::App { head, arity: 1 }, rest @ ..] = pieces else { return None };
    let opcode = match opcode_of(head)? {
        opcode @ (Opcode::SExt | Opcode::ZExt | Opcode::Trunc) => opcode,
        _ => return None,
    };
    let [Piece::App { head: inner, arity: 1 }, Piece::Var { index, .. }] = rest else {
        return None;
    };
    if !inner.starts_with("value.") {
        return None;
    }
    match found.bindings.get(*index) {
        Some(&Term::Reg(from)) => Some(Rewrite::Converted { opcode, from }),
        _ => None,
    }
}

/// One operand of that instruction, and the pieces after it.
fn operand(pieces: &'static [Piece], found: &Match<Term>) -> Option<(Operand, &'static [Piece])> {
    match pieces {
        [Piece::App { head, arity: 1 }, Piece::Var { index, .. }, rest @ ..]
            if head.starts_with("value.") =>
        {
            match found.bindings.get(*index) {
                Some(&Term::Reg(value)) => Some((Operand::Value(value), rest)),
                _ => None,
            }
        }
        [Piece::App { head, arity: 1 }, Piece::Int(number), rest @ ..]
            if head.starts_with("iconst.") =>
        {
            Some((Operand::Constant { number: *number, bits: bits_of(head)? }, rest))
        }
        // A number the pattern bound rather than one the rule wrote. This is what a
        // canonicalisation needs: it moves the operand it matched to the other side, and what it
        // matched was whatever number happened to be there.
        [Piece::App { head, arity: 1 }, Piece::Var { index, .. }, rest @ ..]
            if head.starts_with("iconst.") =>
        {
            match found.bindings.get(*index) {
                Some(&Term::Num(number)) => {
                    Some((Operand::Constant { number, bits: bits_of(head)? }, rest))
                }
                _ => None,
            }
        }
        _ => None,
    }
}

/// The width a head names, out of the `iN` after its last dot.
///
/// Every head that takes a width ends in one, and reading it off the name is what keeps the width
/// a rule was written at attached to the rule rather than inferred from whatever the instruction
/// being replaced happened to be. A head with no width, or one whose width is not a number, is a
/// head this cannot build an operand for, and the answer to that is that the rule does not fire.
fn bits_of(head: &str) -> Option<u32> {
    head.rsplit_once('.')?.1.strip_prefix('i')?.parse().ok()
}

/// The opcode a replacement head names, or nothing if the rules have no instruction by that name.
///
/// Built the once out of [`rucc_ir::term::heads`], which is where the name of the instruction a
/// pattern matched comes from as well, so a rule whose replacement this pass can build is a rule
/// written in the vocabulary it matched with. A table here would be a second vocabulary and the
/// two would drift.
///
/// A name two opcodes answer to belongs to the first of them, which is the general one:
/// `ptr_add` is an add at the address width and is named as one, and a rule that writes `add` is
/// asking for the add.
fn opcode_of(head: &str) -> Option<Opcode> {
    static NAMES: OnceLock<HashMap<&'static str, Opcode>> = OnceLock::new();
    let names = NAMES.get_or_init(|| {
        let mut names = HashMap::new();
        for (opcode, name) in rucc_ir::term::heads() {
            names.entry(name).or_insert(opcode);
        }
        names
    });
    names.get(head).copied()
}

/// Turns an instruction into the one a rule says computes the same thing.
///
/// In place, like the constant below and for the same reason: the result value survives, so every
/// reader of it is already right and there is nothing to redirect.
fn become_instruction(
    func: &mut Func,
    inst: Inst,
    opcode: Opcode,
    pred: Option<IntPred>,
    lhs: Operand,
    rhs: Operand,
) {
    let result = func[inst].first_result.expect("the rule matched a result");
    let ty = func[result].ty;
    let lhs = defined(func, inst, ty, lhs);
    let rhs = defined(func, inst, ty, rhs);
    let args = func.push_values(&[lhs, rhs]);
    let data = &mut func[inst];
    data.opcode = opcode;
    data.args = args;
    // The predicate the rule named, and nothing else a rule writes carries an extra. What was
    // there belonged to the instruction that is gone, which is the case that matters: a rule
    // rewriting a comparison into an addition that left the predicate behind would leave an
    // addition claiming to be `slt`, and one rewriting a comparison into another comparison that
    // kept the old predicate would compute the opposite of what it said.
    data.extra = match pred {
        Some(pred) => Extra::IntPred(pred),
        None => Extra::None,
    };
    // The flags go with the instruction that had them, the same as for a constant. An `nsw` on a
    // multiplication is a promise about that multiplication, and the addition that replaces it is
    // a different instruction. The promise may well still hold, and carrying one across a rewrite
    // because it probably still holds is how a wrong one gets made. Dropping it costs a later
    // pass an assumption and costs no program its meaning.
    data.flags = Flags::NONE;
}

/// Turns an instruction into the conversion a rule says computes the same thing.
///
/// In place, for the same reason as the two above: the result value survives, so every reader of
/// it is already right.
///
/// The result keeps the type it had, which is the type the rule wrote. A replacement head names
/// both widths it converts between, `rucc-verify` refuses a replacement narrower than the pattern
/// and the rules are written with the two the same, so the width the head names on the way out is
/// the width the instruction already produces.
fn become_conversion(func: &mut Func, inst: Inst, opcode: Opcode, from: Value) {
    let args = func.push_values(&[from]);
    let data = &mut func[inst];
    data.opcode = opcode;
    data.args = args;
    // Nothing a rule writes carries an extra, and the flags belonged to the instruction that is
    // gone. Both for the reasons `become_instruction` gives.
    data.extra = Extra::None;
    data.flags = Flags::NONE;
}

/// An operand as a value, defining it in front of the instruction if the rule wrote a number.
///
/// `ty` is the type of the instruction's result, which is the width the constant is built at for
/// everything whose operands are as wide as what it produces. A comparison is the exception and
/// the reason the rule's own width is carried this far: its result is one bit and its operands are
/// as wide as what was compared, so the width comes from the `iconst.iN` the rule wrote and the
/// result's type is used only for its shape.
fn defined(func: &mut Func, before: Inst, ty: Type, operand: Operand) -> Value {
    match operand {
        Operand::Value(value) => value,
        Operand::Constant { number, bits } => {
            let ty = if ty.lane() == Type::int(bits) { ty } else { Type::int(bits) };
            let at = func.add_imm(Imm::int(number, ty.lane()));
            let data = InstData { extra: Extra::Imm(at), ..InstData::new(Opcode::IConst) };
            let span = func.span(before);
            let iconst = func.create_inst(data, &[ty], span);
            func.insert_before(iconst, before);
            func[iconst].first_result.expect("one result was asked for")
        }
    }
}

/// Turns an instruction into the constant a rule says its result is.
///
/// In place, so the result value survives and every reader of it is already right. That is what
/// makes this the half of the pass with nothing to redirect.
fn become_constant(func: &mut Func, inst: Inst, number: i128) {
    let result = func[inst].first_result.expect("the rule matched a result");
    let ty = func[result].ty;
    let imm = func.add_imm(Imm::int(number, ty.lane()));
    let args = func.push_values(&[]);
    let data = &mut func[inst];
    data.opcode = Opcode::IConst;
    data.args = args;
    data.extra = Extra::Imm(imm);
    // The flags go with the instruction that had them. An `nsw` on an add is a promise about an
    // addition, and a constant makes no promise because it performs nothing.
    data.flags = Flags::NONE;
}

/// What an instruction should become, when it is a comparison written as a negation.
struct Flip {
    /// `ICmp` or `FCmp`, whichever the comparison underneath was.
    opcode: Opcode,
    /// The flags of the comparison, which is where a fast math promise lives.
    flags: Flags,
    /// The opposite predicate.
    extra: Extra,
    /// The comparison's left operand.
    lhs: Value,
    /// Its right operand.
    rhs: Value,
}

/// Whether this instruction is `xor (cmp p a b), true`, and what it becomes if it is.
///
/// The exclusive or is commutative, so the constant is looked for on both sides. Nothing else
/// about the shape is negotiable: the result has to be an `i1`, because an exclusive or with one
/// is a negation only at that width, and the constant has to be all ones, because the front end
/// writes it as `iconst.i1 -1` and a reader who assumed the literal 1 would match nothing.
fn negated_comparison(func: &Func, inst: Inst) -> Option<Flip> {
    let data = &func[inst];
    if data.opcode != Opcode::Xor {
        return None;
    }
    let args = &func[data.args];
    let (&first, &second) = (args.first()?, args.get(1)?);
    if func[first].ty != Type::int(1) {
        return None;
    }
    let cmp = match (all_ones(func, first), all_ones(func, second)) {
        (true, false) => second,
        (false, true) => first,
        // Both, which folding would have turned into a constant, or neither, which is an
        // exclusive or of two comparisons and is not this pattern.
        _ => return None,
    };
    let Def::Result { inst: cmp, .. } = func[cmp].def else { return None };
    let data = &func[cmp];
    let extra = match (data.opcode, data.extra) {
        (Opcode::ICmp, Extra::IntPred(pred)) => Extra::IntPred(pred.inverse()),
        (Opcode::FCmp, Extra::FloatPred(pred)) => Extra::FloatPred(pred.inverse()),
        _ => return None,
    };
    let args = &func[data.args];
    Some(Flip {
        opcode: data.opcode,
        flags: data.flags,
        extra,
        lhs: *args.first()?,
        rhs: *args.get(1)?,
    })
}

/// Whether this value is a constant with every bit of its type set.
fn all_ones(func: &Func, value: Value) -> bool {
    let ty = func[value].ty;
    let Def::Result { inst, .. } = func[value].def else { return false };
    let data = &func[inst];
    let Extra::Imm(at) = data.extra else { return false };
    if data.opcode != Opcode::IConst {
        return false;
    }
    // Read as signed, because an all ones value of any width is minus one that way and reading
    // it unsigned would need the width to build the mask from.
    func[at].signed(ty) == -1
}

#[cfg(test)]
mod tests {
    use rucc_base::Interner;
    use rucc_ir::{
        Block, Builder, Extra, Flags, Float, FloatPred, Func, IntPred, Module, Opcode, Signature,
        Type, Value,
    };
    use rucc_target::{Arch, Env, Os, TargetInfo, Triple};

    use super::{
        CANONICAL, COMPARE, EXPAND, PLANS, Shown, TABLES, canonical, compare, identities, strength,
        width,
    };
    use crate::rules::Piece;
    use crate::stats::Kind;
    use crate::{Analyses, Fuel, Pass, simplify::Simplify};

    /// A function with one block, ready to have instructions appended to it.
    fn blank() -> (Interner, Func, Block) {
        let mut names = Interner::new();
        let name = names.intern("f");
        let mut func = Func::new(name, Signature::new().with_returns(&[Type::int(1)]));
        let block = func.create_block();
        (names, func, block)
    }

    /// The same, at the width the test is about and taking a parameter of it, since every identity
    /// below needs an operand that is not itself a constant.
    fn one_block(ty: Type) -> (Interner, Func, Block) {
        let mut names = Interner::new();
        let name = names.intern("f");
        let signature = Signature::new().with_params(&[ty]).with_returns(&[ty]);
        let mut func = Func::new(name, signature);
        let block = func.create_block();
        (names, func, block)
    }

    /// Runs the pass with as much fuel as it wants, and says whether it rewrote anything.
    fn simplify(func: &mut Func) -> bool {
        Simplify.run(func, &mut Analyses::new(), &mut Fuel::unlimited()).changed()
    }

    /// The opcode and the predicate the value now comes from.
    fn came_from(func: &Func, value: Value) -> (Opcode, Extra) {
        let rucc_ir::Def::Result { inst, .. } = func[value].def else { panic!("not a result") };
        (func[inst].opcode, func[inst].extra)
    }

    /// What the block gives back, which is where every identity test reads its answer. A rule
    /// that produces a value is only worth anything if the readers move, so the readers are what
    /// the test looks at rather than the instruction that fired.
    fn returned(func: &Func, block: Block) -> Value {
        let inst = func.terminator(block).expect("the block has a terminator");
        func[func[inst].args][0]
    }

    /// The operands of the instruction a value comes from.
    fn operands(func: &Func, value: Value) -> Vec<Value> {
        let rucc_ir::Def::Result { inst, .. } = func[value].def else { panic!("not a result") };
        func[func[inst].args].to_vec()
    }

    /// The number a value is, which panics unless it is a constant.
    fn number(func: &Func, value: Value) -> i128 {
        let rucc_ir::Def::Result { inst, .. } = func[value].def else { panic!("not a result") };
        let data = &func[inst];
        assert_eq!(data.opcode, Opcode::IConst, "not a constant");
        let Extra::Imm(at) = data.extra else { panic!("a constant with no number") };
        func[at].signed(func[value].ty)
    }

    /// Every rule in every table leaves one of the four shapes the pass knows how to apply.
    ///
    /// A rule that left anything else would be matched, found to be none of them, and skipped, and
    /// nothing at run time would say so: the rewrite would simply stop happening. So it is said
    /// here instead, once, over every table.
    #[test]
    fn every_rule_leaves_a_shape_the_pass_knows_what_to_do_with() {
        for (table, _) in TABLES {
            for rule in table.rules {
                let known = matches!(
                    rule.replacement,
                    [Piece::App { head, arity: 1 }, Piece::Var { .. }]
                        if head.starts_with("value.")
                ) || matches!(
                    rule.replacement,
                    [Piece::App { head, arity: 1 }, Piece::Int(_)]
                        if head.starts_with("iconst.")
                ) || matches!(
                    rule.replacement,
                    [Piece::App { arity: 2, .. }, ..] if instruction(rule.replacement)
                ) || conversion(rule.replacement);
                assert!(known, "{} leaves a shape the pass would skip", rule.pattern);
            }
        }
    }

    /// The pieces of a replacement that is a conversion, read the way [`super::converted`] reads
    /// them, and shape only for the same reason [`instruction`] is: there are no bindings here to
    /// resolve the operand against.
    fn conversion(pieces: &'static [Piece]) -> bool {
        let [Piece::App { head, arity: 1 }, rest @ ..] = pieces else { return false };
        let converts =
            matches!(super::opcode_of(head), Some(Opcode::SExt | Opcode::ZExt | Opcode::Trunc));
        converts
            && matches!(
                rest,
                [Piece::App { head, arity: 1 }, Piece::Var { .. }] if head.starts_with("value.")
            )
    }

    /// Every rule in the width table writes a term ending at the width the one it matched ended
    /// at.
    ///
    /// The pass rewrites in place and leaves the result type where it was, so a rule whose
    /// replacement converted to some other width would quietly produce a value of the wrong one.
    /// `rucc-verify` refuses a replacement narrower than what it replaces and says nothing about a
    /// wider one, so this is the half of that pair the solver does not cover.
    #[test]
    fn a_width_rule_writes_a_term_that_ends_where_the_one_it_matched_ended() {
        for rule in width::TABLE.rules {
            let [Piece::App { head, .. }, ..] = rule.replacement else {
                panic!("{} writes no head", rule.pattern)
            };
            let wrote = head.rsplit_once('.').expect("a replacement head names a width").1;
            let matched = rule
                .pattern
                .trim_start_matches('(')
                .split([' ', ')'])
                .next()
                .and_then(|head| head.rsplit_once('.'))
                .expect("a pattern head names a width")
                .1;
            assert_eq!(wrote, matched, "{} ends somewhere else", rule.pattern);
        }
    }

    /// The pieces of a replacement that is an instruction, read the way the pass reads them, so
    /// that the check above is the pass's own answer rather than a second opinion about it.
    ///
    /// The bindings are empty, which is why a `value.iN` operand fails to resolve and this only
    /// says the shape is one the pass would take rather than that it would take it here.
    fn instruction(pieces: &'static [Piece]) -> bool {
        let [Piece::App { head, arity: 2 }, rest @ ..] = pieces else { return false };
        if super::opcode_of(head).is_none() {
            return false;
        }
        let operand = |pieces: &'static [Piece]| match pieces {
            [Piece::App { head, arity: 1 }, Piece::Var { .. }, rest @ ..]
                if head.starts_with("value.") =>
            {
                Some(rest)
            }
            [Piece::App { head, arity: 1 }, Piece::Int(_), rest @ ..]
                if head.starts_with("iconst.") =>
            {
                Some(rest)
            }
            [Piece::App { head, arity: 1 }, Piece::Var { .. }, rest @ ..]
                if head.starts_with("iconst.") =>
            {
                Some(rest)
            }
            _ => None,
        };
        operand(rest).and_then(operand).is_some_and(<[Piece]>::is_empty)
    }

    /// And each table holds every rule its file writes. The tables are generated, so this is
    /// asking whether the generator saw the whole file, which is the one thing about it worth
    /// doubting.
    #[test]
    fn each_table_holds_every_rule_its_file_writes() {
        let tier_one = include_str!("../rules/simplify.rules");
        let tier_two = include_str!("../rules/strength.rules");
        let tier_three = include_str!("../rules/canonical.rules");
        let tier_four = include_str!("../rules/width.rules");
        let tier_five = include_str!("../rules/compare.rules");
        let count = |text: &str| text.matches("(rule (simplify ").count();
        assert_eq!(identities::TABLE.rules.len(), count(tier_one));
        assert_eq!(strength::TABLE.rules.len(), count(tier_two));
        assert_eq!(canonical::TABLE.rules.len(), count(tier_three));
        assert_eq!(width::TABLE.rules.len(), count(tier_four));
        assert_eq!(compare::TABLE.rules.len(), count(tier_five));
        assert!(
            identities::TABLE.rules.len() > 100,
            "tier one is about a hundred rules and there are fewer"
        );
        assert!(
            strength::TABLE.rules.len() > 20,
            "tier two is the multiplications and the divisions and there are fewer"
        );
        assert_eq!(
            canonical::TABLE.rules.len(),
            20,
            "tier three is five commutative operators at four widths"
        );
        assert_eq!(
            width::TABLE.rules.len(),
            44,
            "tier four is the truncation and extension algebra over four widths"
        );
        assert_eq!(
            compare::TABLE.rules.len(),
            64,
            "tier five is four predicates against each of four constants at four widths"
        );
    }

    /// Three ways of showing an operand and no more, since a fourth would be a plan nothing
    /// tries and a rule written for it would never fire.
    #[test]
    fn a_pattern_is_reached_by_one_of_the_plans() {
        assert_eq!(PLANS.len(), 3);
    }

    /// Tier four is matched with its operand expanded, and nothing else is.
    ///
    /// Every pattern in that tier has an instruction at its second level, so under any of the
    /// plans above it every rule in it would fail at the first node and the whole tier would be a
    /// file nobody matched with. Asserted rather than left to be read, because that failure is
    /// silent.
    #[test]
    fn a_width_rule_is_only_matched_with_its_operand_expanded() {
        let (_, plans) = TABLES[2];
        assert_eq!(plans.len(), 1);
        assert_eq!(plans[0], EXPAND[0]);
        assert_eq!(plans[0][0], Shown::Expand);
        for plan in PLANS {
            assert_ne!(plan, plans[0], "no shared plan expands an operand");
        }
        assert_ne!(CANONICAL[0], plans[0]);
    }

    /// Tier three is matched under its own plan and no other.
    ///
    /// This is what makes the rules terminate rather than swap a pair of constants back and forth
    /// until the fuel runs out. It is asserted rather than left to be read, because the cost of
    /// somebody adding the shared plans to the tier three row is a pass that does not stop.
    #[test]
    fn a_canonicalisation_is_only_matched_with_the_right_operand_refused() {
        let (_, plans) = TABLES[4];
        assert_eq!(plans.len(), 1);
        assert_eq!(plans[0], CANONICAL[0]);
        assert_eq!(plans[0][1], Shown::Var);
        for plan in PLANS {
            assert_ne!(plan, plans[0], "a shared plan would let a canonicalisation cycle");
        }
    }

    /// Tier five is matched with the constant on the right and no other way.
    ///
    /// Every rule in it writes the constant there, so under the plan that shows a constant left
    /// operand as a number none of them would match and under the plan that refuses a constant on
    /// the right none of them would either. One plan, and it is the first of the shared three.
    #[test]
    fn a_comparison_rule_is_only_matched_with_the_constant_on_the_right() {
        let (_, plans) = TABLES[3];
        assert_eq!(plans.len(), 1);
        assert_eq!(plans[0], COMPARE[0]);
        assert_eq!(plans[0][0], Shown::Reg);
        assert_eq!(plans[0][1], Shown::Const);
    }

    /// The edge of a type, at each width, read each way.
    ///
    /// The least and greatest unsigned value and the least and greatest signed one, which are the
    /// four constants tier five is written against.
    fn edges(width: u32) -> [(i128, bool); 4] {
        let signed = 1i128 << (width - 1);
        [(0, false), (-1, false), (-signed, true), (signed - 1, true)]
    }

    /// A comparison that its type has already answered becomes the answer.
    ///
    /// Nothing unsigned is below zero, everything unsigned is at least zero, and the same pair of
    /// sentences holds at each of the other three edges. Thirty two rules, run as one test,
    /// because what is being checked is the same sentence at four constants and four widths.
    #[test]
    fn a_comparison_against_the_edge_of_its_type_folds_to_a_bit() {
        for width in [8u32, 16, 32, 64] {
            let ty = Type::int(width);
            for (edge, signed) in edges(width) {
                // Below the edge is false at the bottom and above it is false at the top, and the
                // other of each pair is the negation, so one table gives all four.
                let below = edge == 0 || edge == -(1i128 << (width - 1));
                let (false_pred, true_pred) = match (signed, below) {
                    (false, true) => (IntPred::Ult, IntPred::Uge),
                    (false, false) => (IntPred::Ugt, IntPred::Ule),
                    (true, true) => (IntPred::Slt, IntPred::Sge),
                    (true, false) => (IntPred::Sgt, IntPred::Sle),
                };
                // Minus one for the true bit, because the rule writes `(iconst.i1 1)` and one bit
                // holding a one read signed is minus one, which is the same bit pattern and the
                // reading everything else in the compiler takes of a true condition.
                for (pred, answer) in [(false_pred, 0), (true_pred, -1)] {
                    let (_, mut func, block) = blank();
                    let x = func.append_param(block, ty);
                    let mut build = Builder::new(&mut func, block);
                    let bound = build.iconst(ty, edge);
                    let cmp = build.icmp(pred, x, bound);
                    build.ret(&[cmp]);
                    assert!(simplify(&mut func), "i{width} {pred:?} {edge} was left alone");
                    let got = returned(&func, block);
                    assert_eq!(
                        came_from(&func, got).0,
                        Opcode::IConst,
                        "i{width} {pred:?} {edge} did not fold"
                    );
                    assert_eq!(number(&func, got), answer, "i{width} {pred:?} {edge}");
                    assert_eq!(func[got].ty, Type::int(1), "i{width} {pred:?} {edge} is a bit");
                }
            }
        }
    }

    /// And one that is true or false for exactly one value becomes the test for that value.
    ///
    /// The predicate has to come from the rule. Every case here matched an ordering and every one
    /// of them has to leave `eq` or `ne`, so a rewriter that took the predicate from the
    /// instruction it replaced would leave the ordering in place and this would say so.
    #[test]
    fn a_comparison_true_for_one_value_becomes_a_test_for_that_value() {
        for width in [8u32, 16, 32, 64] {
            let ty = Type::int(width);
            for (edge, signed) in edges(width) {
                let below = edge == 0 || edge == -(1i128 << (width - 1));
                // At most the bottom is equality and above it is inequality, and at the top the
                // two swap over.
                let (eq_pred, ne_pred) = match (signed, below) {
                    (false, true) => (IntPred::Ule, IntPred::Ugt),
                    (false, false) => (IntPred::Uge, IntPred::Ult),
                    (true, true) => (IntPred::Sle, IntPred::Sgt),
                    (true, false) => (IntPred::Sge, IntPred::Slt),
                };
                for (pred, left) in [(eq_pred, IntPred::Eq), (ne_pred, IntPred::Ne)] {
                    let (_, mut func, block) = blank();
                    let x = func.append_param(block, ty);
                    let mut build = Builder::new(&mut func, block);
                    let bound = build.iconst(ty, edge);
                    let cmp = build.icmp(pred, x, bound);
                    build.ret(&[cmp]);
                    assert!(simplify(&mut func), "i{width} {pred:?} {edge} was left alone");
                    let got = returned(&func, block);
                    assert_eq!(
                        came_from(&func, got),
                        (Opcode::ICmp, Extra::IntPred(left)),
                        "i{width} {pred:?} {edge} kept the predicate it matched"
                    );
                    let args = operands(&func, got);
                    assert_eq!(args[0], x, "i{width} {pred:?} {edge} lost its value");
                    assert_eq!(number(&func, args[1]), edge, "i{width} {pred:?} {edge}");
                    // The width the rule was written at, which is the width of what is being
                    // compared and not the width of the answer. A constant built at the result's
                    // type would be a one bit zero standing where a wider one was asked for.
                    assert_eq!(func[args[1]].ty, ty, "i{width} {pred:?} {edge} narrowed its bound");
                }
            }
        }
    }

    /// Every commutative operator tier three writes moves its constant to the right.
    ///
    /// One test over the five rather than five tests, because what is being checked is the same
    /// thing five times and the operator is the only part that differs.
    #[test]
    fn a_constant_on_the_left_of_a_commutative_operation_moves_to_the_right() {
        for opcode in [Opcode::Add, Opcode::Mul, Opcode::And, Opcode::Or, Opcode::Xor] {
            for width in [8, 16, 32, 64] {
                let ty = Type::int(width);
                let (_, mut func, block) = one_block(ty);
                let x = func.append_param(block, ty);
                let mut build = Builder::new(&mut func, block);
                // Three, because it is a number no identity in tier one is about and no strength
                // reduction in tier two is about, so the only rule that can fire is the one this
                // test is here for.
                let three = build.iconst(ty, 3);
                let value = build.binary(opcode, three, x, Flags::NONE);
                build.ret(&[value]);
                assert!(simplify(&mut func), "{opcode:?} at i{width} was left alone");
                let args = operands(&func, returned(&func, block));
                assert_eq!(came_from(&func, returned(&func, block)).0, opcode);
                assert_eq!(args[0], x, "{opcode:?} at i{width} kept the value on the right");
                assert_eq!(number(&func, args[1]), 3, "{opcode:?} at i{width} lost its constant");
            }
        }
    }

    /// And an operation whose operands are both constants is left where it is.
    ///
    /// This is the termination argument, run rather than read. Without the plan that refuses a
    /// constant on the right, the rule above would match this, swap the two, match the swapped
    /// form, and go on doing it until the fuel ran out. Folding is what this instruction is for
    /// and `crate::fold` is where it happens.
    #[test]
    fn an_operation_on_two_constants_is_not_swapped_back_and_forth() {
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let mut build = Builder::new(&mut func, block);
        let three = build.iconst(i32, 3);
        let five = build.iconst(i32, 5);
        let sum = build.binary(Opcode::Add, three, five, Flags::NONE);
        build.ret(&[sum]);
        assert!(!simplify(&mut func), "the constants were rearranged rather than left to folding");
        let args = operands(&func, returned(&func, block));
        assert_eq!(number(&func, args[0]), 3);
        assert_eq!(number(&func, args[1]), 5);
    }

    /// A constant already on the right stays there and nothing fires.
    ///
    /// The other half of the same argument. A canonicalisation that fired on the shape it produces
    /// would be a canonicalisation with no direction, which is what section 13.5 refuses.
    #[test]
    fn a_constant_already_on_the_right_is_left_alone() {
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let three = build.iconst(i32, 3);
        let sum = build.binary(Opcode::Add, x, three, Flags::NONE);
        build.ret(&[sum]);
        assert!(!simplify(&mut func));
        let args = operands(&func, returned(&func, block));
        assert_eq!(args[0], x);
        assert_eq!(number(&func, args[1]), 3);
    }

    /// A subtraction is not commutative and nothing moves its constant.
    ///
    /// Turning `c - x` into anything is not what tier three does, and the rules are written per
    /// opcode rather than over a set of them, so this is asking whether the wrong opcode found its
    /// way into the file.
    #[test]
    fn a_subtraction_keeps_its_operands_where_they_are() {
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let three = build.iconst(i32, 3);
        let difference = build.binary(Opcode::Sub, three, x, Flags::NONE);
        build.ret(&[difference]);
        assert!(!simplify(&mut func));
        let args = operands(&func, returned(&func, block));
        assert_eq!(number(&func, args[0]), 3);
        assert_eq!(args[1], x);
    }

    /// A block whose parameter and whose result are different widths, which is what every width
    /// rule needs and what `one_block` cannot give.
    fn narrow_to_wide(takes: Type, gives: Type) -> (Interner, Func, Block) {
        let mut names = Interner::new();
        let name = names.intern("f");
        let signature = Signature::new().with_params(&[takes]).with_returns(&[gives]);
        let mut func = Func::new(name, signature);
        let block = func.create_block();
        (names, func, block)
    }

    /// A conversion of a conversion of a parameter, which is the shape every width rule matches.
    ///
    /// The parameter is at `from`, the inner conversion takes it to `through` and the outer one
    /// takes that to `to`, and what comes back is the function, the block and the parameter.
    fn chain(
        inner: Opcode,
        outer: Opcode,
        from: Type,
        through: Type,
        to: Type,
    ) -> (Func, Block, Value) {
        let (_, mut func, block) = narrow_to_wide(from, to);
        let x = func.append_param(block, from);
        let mut build = Builder::new(&mut func, block);
        let middle = build.unary(inner, x, through);
        let outside = build.unary(outer, middle, to);
        build.ret(&[outside]);
        (func, block, x)
    }

    /// Truncating an extension back to the width it came from is the value that was there.
    ///
    /// Every pair of widths and both extensions, because the rule file writes all twelve and a
    /// test of one of them would say nothing about the other eleven.
    #[test]
    fn truncating_an_extension_back_to_its_own_width_gives_the_value_back() {
        for extend in [Opcode::SExt, Opcode::ZExt] {
            for (narrow, wide) in [(8, 16), (8, 32), (8, 64), (16, 32), (16, 64), (32, 64)] {
                let (from, through) = (Type::int(narrow), Type::int(wide));
                let (mut func, block, x) = chain(extend, Opcode::Trunc, from, through, from);
                assert!(simplify(&mut func), "{extend:?} i{narrow} to i{wide} was left alone");
                assert_eq!(
                    returned(&func, block),
                    x,
                    "{extend:?} i{narrow} to i{wide} and back did not give the value back"
                );
            }
        }
    }

    /// Truncating an extension to a width still above the source is the same extension, stopping
    /// earlier.
    #[test]
    fn truncating_an_extension_above_its_source_is_a_shorter_extension() {
        let (mut func, block, x) =
            chain(Opcode::SExt, Opcode::Trunc, Type::int(8), Type::int(64), Type::int(16));
        assert!(simplify(&mut func));
        let result = returned(&func, block);
        assert_eq!(came_from(&func, result).0, Opcode::SExt);
        assert_eq!(operands(&func, result), vec![x]);
        assert_eq!(func[result].ty, Type::int(16));
    }

    /// Truncating an extension to a width below the source is a truncation of the source, and
    /// which extension it was never mattered.
    #[test]
    fn truncating_an_extension_below_its_source_is_a_truncation_of_the_source() {
        let (mut func, block, x) =
            chain(Opcode::ZExt, Opcode::Trunc, Type::int(16), Type::int(32), Type::int(8));
        assert!(simplify(&mut func));
        let result = returned(&func, block);
        assert_eq!(came_from(&func, result).0, Opcode::Trunc);
        assert_eq!(operands(&func, result), vec![x]);
        assert_eq!(func[result].ty, Type::int(8));
    }

    /// An extension of an extension is one extension, and a sign extension of a zero extension is
    /// a zero extension rather than a sign extension.
    #[test]
    fn an_extension_of_an_extension_is_one_extension() {
        for (inner, outer, want) in [
            (Opcode::ZExt, Opcode::ZExt, Opcode::ZExt),
            (Opcode::SExt, Opcode::SExt, Opcode::SExt),
            (Opcode::ZExt, Opcode::SExt, Opcode::ZExt),
        ] {
            let (mut func, block, x) =
                chain(inner, outer, Type::int(8), Type::int(16), Type::int(64));
            assert!(simplify(&mut func), "{outer:?} of {inner:?} was left alone");
            let result = returned(&func, block);
            assert_eq!(came_from(&func, result).0, want, "{outer:?} of {inner:?}");
            assert_eq!(operands(&func, result), vec![x]);
            assert_eq!(func[result].ty, Type::int(64));
        }
    }

    /// A truncation of a truncation is one truncation, straight to the width the outer one asked
    /// for.
    ///
    /// The inner one threw away bits the outer one was going to throw away as well, so the width
    /// in the middle was never read and the rule goes to the outer width from the source. Both
    /// orderings of the three widths are tried, because a rule that picked the middle width rather
    /// than the outer one would still pass a test that only went from sixty four to eight through
    /// thirty two.
    #[test]
    fn a_truncation_of_a_truncation_is_one_truncation() {
        for (from, through, to) in [(64u32, 32u32, 16u32), (64, 32, 8), (64, 16, 8), (32, 16, 8)] {
            let (mut func, block, x) = chain(
                Opcode::Trunc,
                Opcode::Trunc,
                Type::int(from),
                Type::int(through),
                Type::int(to),
            );
            assert!(simplify(&mut func), "i{from} to i{through} to i{to} was left alone");
            let result = returned(&func, block);
            assert_eq!(came_from(&func, result).0, Opcode::Trunc, "i{from} to i{through} to i{to}");
            assert_eq!(operands(&func, result), vec![x]);
            assert_eq!(func[result].ty, Type::int(to));
        }
    }

    /// And zero extending a sign extension is not one, because the bits the sign extension copied
    /// are bits of the value now and nothing above them is a function of the source alone.
    #[test]
    fn zero_extending_a_sign_extension_is_left_alone() {
        let (mut func, _, _) =
            chain(Opcode::SExt, Opcode::ZExt, Type::int(8), Type::int(16), Type::int(64));
        assert!(!simplify(&mut func), "a zero extension of a sign extension was rewritten");
    }

    /// And zero extending a truncation is left alone, which is the rule the tier would be expected
    /// to have and does not.
    ///
    /// It was written and proved and then measured, and the measurement is why it went: the
    /// machine has one instruction for the pair already, the `and` with an immediate that replaced
    /// it is the longer encoding of the two, and the mask hides the narrowing from
    /// [`crate::narrow`]. The rule file says the whole of it. This is here so that somebody adding
    /// it back finds a test rather than a silence.
    #[test]
    fn zero_extending_a_truncation_is_left_alone() {
        let (mut func, _, _) =
            chain(Opcode::Trunc, Opcode::ZExt, Type::int(64), Type::int(32), Type::int(64));
        assert!(!simplify(&mut func), "a zero extension of a truncation became a mask");
    }

    /// A width rule needs an operand something computed, and a parameter is not one.
    ///
    /// This is what the plan being an expanding one means at the bottom: there is no instruction
    /// under the operand to be the second level of the pattern, so nothing matches and nothing is
    /// rewritten. Said out loud because it is the case that would otherwise be a crash rather than
    /// a miss.
    #[test]
    fn a_width_rule_needs_an_operand_an_instruction_computed() {
        let (_, mut func, block) = narrow_to_wide(Type::int(64), Type::int(32));
        let x = func.append_param(block, Type::int(64));
        let mut build = Builder::new(&mut func, block);
        let narrowed = build.unary(Opcode::Trunc, x, Type::int(32));
        build.ret(&[narrowed]);
        assert!(!simplify(&mut func), "a truncation of a parameter was rewritten");
    }

    #[test]
    fn adding_nothing_points_every_reader_at_the_operand() {
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let zero = build.iconst(i32, 0);
        let sum = build.binary(Opcode::Add, x, zero, Flags::NONE);
        build.ret(&[sum]);
        assert!(simplify(&mut func));
        // The `add` is still there, used by nothing, which is what dead code elimination is for.
        assert_eq!(returned(&func, block), x);
        assert_eq!(came_from(&func, sum).0, Opcode::Add);
    }

    /// The constant on either side, since nothing puts it on the right yet and a rule written one
    /// way round would fire on half the additions it should.
    #[test]
    fn the_constant_is_found_on_either_side_of_an_identity() {
        for swapped in [false, true] {
            let i32 = Type::int(32);
            let (_, mut func, block) = one_block(i32);
            let x = func.append_param(block, i32);
            let mut build = Builder::new(&mut func, block);
            let zero = build.iconst(i32, 0);
            let (lhs, rhs) = if swapped { (zero, x) } else { (x, zero) };
            let sum = build.binary(Opcode::Add, lhs, rhs, Flags::NONE);
            build.ret(&[sum]);
            assert!(simplify(&mut func), "swapped {swapped}");
            assert_eq!(returned(&func, block), x, "swapped {swapped}");
        }
    }

    #[test]
    fn multiplying_by_nothing_becomes_the_constant_where_it_stands() {
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let zero = build.iconst(i32, 0);
        let product = build.binary(Opcode::Mul, x, zero, Flags::NONE);
        build.ret(&[product]);
        assert!(simplify(&mut func));
        // The result value survives, which is the whole reason this half rewrites in place.
        assert_eq!(returned(&func, block), product);
        assert_eq!(came_from(&func, product).0, Opcode::IConst);
        assert_eq!(number(&func, product), 0);
    }

    /// The two identities a pattern that writes one name twice exists for, at every width they
    /// are written at.
    #[test]
    fn a_value_against_itself() {
        for bits in [8, 16, 32, 64] {
            let ty = Type::int(bits);
            let (_, mut func, block) = one_block(ty);
            let x = func.append_param(block, ty);
            let mut build = Builder::new(&mut func, block);
            let both = build.binary(Opcode::And, x, x, Flags::NONE);
            build.ret(&[both]);
            assert!(simplify(&mut func), "{bits} bits");
            assert_eq!(returned(&func, block), x, "{bits} bits");

            let (_, mut func, block) = one_block(ty);
            let x = func.append_param(block, ty);
            let mut build = Builder::new(&mut func, block);
            let nothing = build.binary(Opcode::Sub, x, x, Flags::NONE);
            build.ret(&[nothing]);
            assert!(simplify(&mut func), "{bits} bits");
            assert_eq!(number(&func, nothing), 0, "{bits} bits");
        }
    }

    /// A remainder by one is nothing, and a division by one is the value. The pair is worth a
    /// test of its own because they are the two identities that produce different shapes from the
    /// same operands.
    #[test]
    fn dividing_by_one_and_the_remainder_that_goes_with_it() {
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let one = build.iconst(i32, 1);
        let quotient = build.binary(Opcode::SDiv, x, one, Flags::NONE);
        let rest = build.binary(Opcode::SRem, x, one, Flags::NONE);
        let sum = build.binary(Opcode::Add, quotient, rest, Flags::NONE);
        build.ret(&[sum]);
        assert!(simplify(&mut func));
        assert_eq!(number(&func, rest), 0);
        // The add reads the value the division was of, which is what the redirection did.
        let rucc_ir::Def::Result { inst, .. } = func[sum].def else { panic!("not a result") };
        assert_eq!(func[func[inst].args][0], x);
    }

    /// All ones at one bit is the `1` the rule file writes, and the front end writes it as `-1`.
    /// The two are the same bit and the rule has to fire on what the front end wrote.
    #[test]
    fn all_ones_at_one_bit_is_the_one_the_front_end_writes() {
        for written in [-1, 1] {
            let bit = Type::int(1);
            let (_, mut func, block) = one_block(bit);
            let x = func.append_param(block, bit);
            let mut build = Builder::new(&mut func, block);
            let ones = build.iconst(bit, written);
            let kept = build.binary(Opcode::And, x, ones, Flags::NONE);
            build.ret(&[kept]);
            assert!(simplify(&mut func), "written as {written}");
            assert_eq!(returned(&func, block), x, "written as {written}");
        }
    }

    /// One identity feeding another is followed all the way, so the second is worth as much as
    /// the first. The redirections are applied once at the end of the run, and this is what says
    /// that costs nothing.
    #[test]
    fn one_identity_feeding_another_is_followed_to_the_end() {
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let zero = build.iconst(i32, 0);
        let one = build.iconst(i32, 1);
        let sum = build.binary(Opcode::Add, x, zero, Flags::NONE);
        let product = build.binary(Opcode::Mul, sum, one, Flags::NONE);
        let shifted = build.binary(Opcode::Shl, product, zero, Flags::NONE);
        build.ret(&[shifted]);
        assert!(simplify(&mut func));
        assert_eq!(returned(&func, block), x);
    }

    #[test]
    fn an_instruction_no_rule_is_about_is_left_alone() {
        // Multiplying by three. Two is tier two and is an addition, and one and zero are tier one,
        // so three is the smallest constant no tier written yet has anything to say about. Turning
        // it into a shift and an add is the rest of tier two and is issue 523.
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let three = build.iconst(i32, 3);
        let tripled = build.binary(Opcode::Mul, x, three, Flags::NONE);
        build.ret(&[tripled]);
        assert!(!simplify(&mut func), "no rule is about multiplying by three");
        assert_eq!(returned(&func, block), tripled);
        assert_eq!(came_from(&func, tripled).0, Opcode::Mul);
    }

    #[test]
    fn multiplying_by_two_becomes_an_addition_of_the_value_with_itself() {
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let two = build.iconst(i32, 2);
        let doubled = build.binary(Opcode::Mul, x, two, Flags::NONE);
        build.ret(&[doubled]);
        assert!(simplify(&mut func));
        // In place, so the value the return reads is the one it always read.
        assert_eq!(returned(&func, block), doubled);
        assert_eq!(came_from(&func, doubled).0, Opcode::Add);
        assert_eq!(operands(&func, doubled), [x, x]);
    }

    #[test]
    fn multiplying_by_minus_one_becomes_a_subtraction_from_a_zero_the_rewrite_defines() {
        // The other shape of operand: nothing in the function holds a zero, so the rewrite has to
        // put one in front of the instruction it is rewriting.
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let minus = build.iconst(i32, -1);
        let negated = build.binary(Opcode::Mul, x, minus, Flags::NONE);
        build.ret(&[negated]);
        assert!(simplify(&mut func));
        assert_eq!(returned(&func, block), negated);
        assert_eq!(came_from(&func, negated).0, Opcode::Sub);
        let args = operands(&func, negated);
        assert_eq!(number(&func, args[0]), 0);
        assert_eq!(args[1], x);
    }

    #[test]
    fn the_flags_of_the_instruction_a_strength_reduction_replaces_do_not_come_with_it() {
        // An `nsw` on a multiplication is a promise about that multiplication. The addition below
        // may well keep it, and a promise carried across a rewrite because it probably still holds
        // is how a wrong one gets made.
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let two = build.iconst(i32, 2);
        let doubled = build.binary(Opcode::Mul, x, two, Flags::NSW);
        build.ret(&[doubled]);
        assert!(simplify(&mut func));
        let rucc_ir::Def::Result { inst, .. } = func[doubled].def else { panic!("not a result") };
        assert_eq!(func[inst].flags, Flags::NONE);
    }

    #[test]
    fn a_strength_reduction_leaves_the_verifier_nothing_to_complain_about() {
        // The zero the negation needs is defined in front of the instruction that reads it, and
        // whether it really is in front of it is a question about the block rather than about the
        // instruction, which is what the verifier is for.
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let i32 = Type::int(32);
        let (mut names, mut func, block) = one_block(i32);
        let mut module = Module::new(names.intern("test.c"), &target);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let minus = build.iconst(i32, -1);
        let negated = build.binary(Opcode::Mul, x, minus, Flags::NONE);
        let two = build.iconst(i32, 2);
        let doubled = build.binary(Opcode::Mul, negated, two, Flags::NONE);
        build.ret(&[doubled]);
        assert!(simplify(&mut func));
        module.add_func(func);
        rucc_ir::verify(&module, &names).expect("the pass left the function verifiable");
    }

    /// The function the pass leaves is still one the verifier accepts. Pointing a reader at a
    /// different value and turning an instruction into a constant are both things a rewrite could
    /// get wrong in a way none of the tests above would notice, because each of those asks about
    /// one instruction and this asks about the function.
    #[test]
    fn the_pass_leaves_the_verifier_nothing_to_complain_about() {
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let i32 = Type::int(32);
        let (mut names, mut func, block) = one_block(i32);
        let mut module = Module::new(names.intern("test.c"), &target);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let zero = build.iconst(i32, 0);
        let one = build.iconst(i32, 1);
        let sum = build.binary(Opcode::Add, x, zero, Flags::NONE);
        let product = build.binary(Opcode::Mul, sum, one, Flags::NONE);
        let gone = build.binary(Opcode::Sub, product, product, Flags::NONE);
        let total = build.binary(Opcode::Add, product, gone, Flags::NONE);
        build.ret(&[total]);
        assert!(simplify(&mut func));
        module.add_func(func);
        rucc_ir::verify(&module, &names).expect("the pass left the function verifiable");
    }

    #[test]
    fn fuel_stops_an_identity_and_not_the_walk() {
        let i32 = Type::int(32);
        let (_, mut func, block) = one_block(i32);
        let x = func.append_param(block, i32);
        let mut build = Builder::new(&mut func, block);
        let zero = build.iconst(i32, 0);
        let first = build.binary(Opcode::Add, x, zero, Flags::NONE);
        let second = build.binary(Opcode::Sub, x, zero, Flags::NONE);
        let sum = build.binary(Opcode::Add, first, second, Flags::NONE);
        build.ret(&[sum]);
        let stats = Simplify.run(&mut func, &mut Analyses::new(), &mut Fuel::of(1));
        assert!(stats.changed());
        assert_eq!(stats.total(Kind::Optimized), 1);
        assert_eq!(stats.count(Kind::Missed, super::NO_FUEL_RULE), 1);
        // The first fired and the second did not, and the second is still read by the add.
        let rucc_ir::Def::Result { inst, .. } = func[sum].def else { panic!("not a result") };
        assert_eq!(func[func[inst].args], [x, second]);
    }

    #[test]
    fn a_negated_float_comparison_becomes_the_opposite_predicate() {
        // Every ordered predicate and its opposite, which is the table `!(x < y)` is `x >= y`
        // or unordered lives in, and the one place a sign error would hide.
        for pred in FloatPred::all() {
            let (_, mut func, block) = blank();
            let mut build = Builder::new(&mut func, block);
            let x = build.iconst(Type::int(64), 0);
            let x = build.unary(Opcode::Bitcast, x, Type::float(Float::F64));
            let cmp = build.fcmp(pred, x, x, Flags::NONE);
            let ones = build.iconst(Type::int(1), -1);
            let not = build.binary(Opcode::Xor, cmp, ones, Flags::NONE);
            build.ret(&[not]);
            assert!(simplify(&mut func), "{pred:?}");
            assert_eq!(
                came_from(&func, not),
                (Opcode::FCmp, Extra::FloatPred(pred.inverse())),
                "{pred:?}"
            );
        }
    }

    #[test]
    fn a_negated_integer_comparison_becomes_the_opposite_predicate() {
        for pred in IntPred::all() {
            let (_, mut func, block) = blank();
            let mut build = Builder::new(&mut func, block);
            let x = build.iconst(Type::int(32), 3);
            let cmp = build.icmp(pred, x, x);
            let ones = build.iconst(Type::int(1), -1);
            let not = build.binary(Opcode::Xor, cmp, ones, Flags::NONE);
            build.ret(&[not]);
            assert!(simplify(&mut func), "{pred:?}");
            assert_eq!(
                came_from(&func, not),
                (Opcode::ICmp, Extra::IntPred(pred.inverse())),
                "{pred:?}"
            );
        }
    }

    #[test]
    fn the_constant_is_found_on_either_side() {
        for swapped in [false, true] {
            let (_, mut func, block) = blank();
            let mut build = Builder::new(&mut func, block);
            let x = build.iconst(Type::int(32), 3);
            let cmp = build.icmp(IntPred::Slt, x, x);
            let ones = build.iconst(Type::int(1), -1);
            let (lhs, rhs) = if swapped { (ones, cmp) } else { (cmp, ones) };
            let not = build.binary(Opcode::Xor, lhs, rhs, Flags::NONE);
            build.ret(&[not]);
            assert!(simplify(&mut func), "swapped {swapped}");
            assert_eq!(came_from(&func, not).1, Extra::IntPred(IntPred::Sge));
        }
    }

    #[test]
    fn an_exclusive_or_of_two_comparisons_is_left_alone() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let x = build.iconst(Type::int(32), 3);
        let a = build.icmp(IntPred::Slt, x, x);
        let b = build.icmp(IntPred::Sgt, x, x);
        let differ = build.binary(Opcode::Xor, a, b, Flags::NONE);
        build.ret(&[differ]);
        assert!(!simplify(&mut func));
        assert_eq!(came_from(&func, differ).0, Opcode::Xor);
    }

    #[test]
    fn an_exclusive_or_of_something_that_is_not_a_comparison_is_left_alone() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let x = build.iconst(Type::int(32), 3);
        let narrow = build.unary(Opcode::Trunc, x, Type::int(1));
        let ones = build.iconst(Type::int(1), -1);
        let not = build.binary(Opcode::Xor, narrow, ones, Flags::NONE);
        build.ret(&[not]);
        assert!(!simplify(&mut func));
        assert_eq!(came_from(&func, not).0, Opcode::Xor);
    }

    #[test]
    fn a_wider_exclusive_or_with_one_is_not_a_negation_and_is_left_alone() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let x = build.iconst(Type::int(32), 3);
        let cmp = build.icmp(IntPred::Slt, x, x);
        let wide = build.unary(Opcode::ZExt, cmp, Type::int(32));
        let one = build.iconst(Type::int(32), 1);
        let flipped = build.binary(Opcode::Xor, wide, one, Flags::NONE);
        let narrow = build.unary(Opcode::Trunc, flipped, Type::int(1));
        build.ret(&[narrow]);
        assert!(!simplify(&mut func), "an i32 xor 1 flips one bit of thirty two");
        assert_eq!(came_from(&func, flipped).0, Opcode::Xor);
    }

    #[test]
    fn the_comparisons_flags_travel_with_the_predicate() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let x = build.iconst(Type::int(64), 0);
        let x = build.unary(Opcode::Bitcast, x, Type::float(Float::F64));
        let cmp = build.fcmp(FloatPred::Olt, x, x, Flags::FAST);
        let ones = build.iconst(Type::int(1), -1);
        let not = build.binary(Opcode::Xor, cmp, ones, Flags::NONE);
        build.ret(&[not]);
        assert!(simplify(&mut func));
        let rucc_ir::Def::Result { inst, .. } = func[not].def else { panic!("not a result") };
        // The promise the original comparison was made under, not the exclusive or's absence of
        // one. Dropping it would be correct and would quietly undo a fast math flag.
        assert_eq!(func[inst].flags, Flags::FAST);
    }

    #[test]
    fn fuel_stops_the_transformation_and_not_the_walk() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let x = build.iconst(Type::int(32), 3);
        let a = build.icmp(IntPred::Slt, x, x);
        let b = build.icmp(IntPred::Sgt, x, x);
        let ones = build.iconst(Type::int(1), -1);
        let first = build.binary(Opcode::Xor, a, ones, Flags::NONE);
        let second = build.binary(Opcode::Xor, b, ones, Flags::NONE);
        let both = build.binary(Opcode::And, first, second, Flags::NONE);
        build.ret(&[both]);
        let stats = Simplify.run(&mut func, &mut Analyses::new(), &mut Fuel::of(1));
        assert!(stats.changed());
        assert_eq!(stats.count(Kind::Optimized, super::FLIPPED), 1);
        assert_eq!(stats.count(Kind::Missed, super::NO_FUEL), 1);
        assert_eq!(came_from(&func, first).0, Opcode::ICmp);
        assert_eq!(came_from(&func, second).0, Opcode::Xor);
    }
}