rucc_opt/

pipeline.rs

//! The pipelines, one per optimization level, and the manager that runs one.
//!
//! Section 9.1 of `spec/09-optimizer.md` says the pipelines are written out rather than assembled
//! from flags, and gives the reason: the prior art ran the same pipeline at every level and named
//! that as a limitation. A level here is a list of pass names, and the list is the definition of
//! the level rather than something that emerges from which flags happen to be set.
//!
//! Section 9.10 says the manager is deliberately boring. There is no adaptive ordering and no
//! scheduling heuristic, because document 03's determinism rule needs the same input to produce
//! the same output on every host and predictability is worth more than the last percent.
//!
//! What the manager does beyond running the list is the four things that make a pass debuggable:
//! it counts each pass's transformations against its fuel, it collects what each pass said it did
//! and did not do, it dumps the IR around whichever passes were asked for, and it verifies any
//! function a pass changed.
//!
//! That last one is section 41.4 of `spec/optimizer/41-correctness.md`, which reads GCC's
//! `execute_function_todo` and takes six things from it. Three of them are already true here by
//! construction and are worth naming so that nobody looks for them. GCC verifies what the IR
//! currently is, by consulting `curr_properties`, because its IR passes through GENERIC, GIMPLE
//! with and without a CFG, GIMPLE in SSA, and RTL. rucc has one IR, it is in SSA from the moment
//! the lowering walk builds it, and it always has a CFG, so the applicable set never varies and a
//! bitmask saying so would have nothing to say. GCC guards the verifiers with `!seen_error()`,
//! because after a user error the IR is legitimately malformed and an internal error raised over
//! it hides the real diagnostic. Here the optimizer is not reached at all after a parse, check or
//! lowering error, which is the same guard placed one level up where it cannot be forgotten. And
//! GCC asserts that a verifier did not change the dominator state. Here a verifier takes the
//! module by shared reference, so that is a type error rather than an assertion.
//!
//! What is left of the six is the part below: verify what changed, not everything, and say which
//! function it was.

use std::collections::HashMap;
use std::fmt::Write as _;

use rucc_base::{Interner, Symbol};
use rucc_ir::{FuncId, Module, Pic};
use rucc_session::OptLevel;

use crate::{
    Analyses, Fuel, Gates, Machine, Pass, Preserved, Stats, extents, heap, nofree, params, pass,
};

/// The passes that read a summary [`nofree::annotate`], [`extents::annotate`],
/// [`params::annotate`] or [`heap::annotate`] writes onto the IR.
///
/// A list rather than one name because there will be more of them: section 7.5 asks for three more
/// summary fields and section 7.3's lifetime elimination is the next thing to want this one. A pass
/// that reads a summary and is not named here reads whatever the last build left, which is nothing,
/// so the cost of forgetting to add a name is a missed optimization.
///
/// The five after the first are `crate::discharge`'s measurement runs, and leaving them out was a
/// missed optimization of exactly that kind: a run measuring what an object says about itself, with
/// no table saying how big any global is, answers that objects say nothing, and the number looks
/// like a result rather than like a list with a name missing from it.
const READS_SUMMARIES: &[&str] = &[
    "discharge",
    "discharge-objects",
    "discharge-dominance",
    "discharge-summaries",
    "discharge-narrow",
    "discharge-every",
];

/// `-O0`. Two passes, and neither of them is an optimization. Section 9.1 gives this level SSA
/// construction, which the lowering walk in `spec/08-ir.md` already does, and mem2reg for the
/// allocas that are left, which is the next pass to be written.
///
/// `expect` is here because what it takes out is a node the front end writes for every
/// `__builtin_expect` in the program and gcc writes for none of them. Left standing it would be an
/// instruction in the output of a level whose whole contract is that it emits what it was given.
///
/// `simplify-cfg` is here because a branch on a condition that is a constant is not a missed
/// optimization, it is a call to a function the program never calls, and a program that calls a
/// function it never calls is one that does not link. That is issue 359, gcc removes the code at
/// every level including this one, and a `-O0` that emitted it would be a `-O0` some correct
/// programs cannot be built at. Nothing else runs, and no analysis beyond the graph the pass
/// reads reachability out of is computed.
const O0: &[&str] = &["expect", "simplify-cfg"];

/// `-O1`. Section 9.1 asks for one e-graph round, conservative inlining, simplify-CFG, SROA,
/// GVN, DCE, LICM and the loop canonicalizations. Folding, control flow simplification and dead
/// code elimination are the part of that which exists, with the peephole among them. They run in
/// that order because folding and the peephole are what make most of the dead code there is to
/// eliminate, because a constant a fold produced is a branch condition the control flow pass can
/// then read, and because the comparison that branch was on is dead once it has.
///
/// The peephole runs on both sides of `narrow`, which is the one place in this list where a pass
/// is named twice, so the reason is worth stating. The rewrite table is written at a width, and
/// the widths below `int` are unreachable from C source: the integer promotions mean an addition
/// of two `char` values arrives here as an `add.i32`, so a rule about `add.i8` matches nothing
/// that a front end can produce. `narrow` is what puts the width back, and it is therefore the
/// only producer the narrow half of the table has. Running the peephole only before it left
/// sixty nine of the first hundred and twenty five rules unable to fire on any program, which is
/// issue 505 and is what the corpus measured. Running it only after it would give up the smaller
/// trees the peephole hands `narrow`, since a subtree `narrow` redoes has to have one reader and
/// an identity left standing is a second one. Both sides costs one more walk over each function
/// and is what the pass is for.
///
/// `phiopt` comes after `thread` and the order between them is not arbitrary. Both look at a
/// diamond whose arms carry a value to a join. Where the join then branches on that value,
/// threading removes a branch and costs nothing, and if-conversion would have turned the same
/// shape into a `select` the join branches on instead, which is strictly worse. Threading first
/// leaves if-conversion the diamonds whose value is used rather than tested, which are the ones it
/// is for.
///
/// `prune` is between `phiopt` and `simplify-cfg` and both sides of that are load bearing. It reads
/// document 10's ranges off the graph to find a branch that can only go one way and a switch case
/// nothing can reach, so it has to run after the two passes that change the graph most. What it
/// leaves is a jump where a branch was and a block nothing reaches, and `simplify-cfg` is the pass
/// that takes those out, so it has to run before it rather than after.
///
/// `canon` is where document 26's loop pipeline opens, so it goes after the value level passes and
/// before the cleanup. It gives every loop a preheader, one latch, exits of its own and loop closed
/// form, which is what lets the loop passes that follow it write `insert at the end of the
/// preheader` rather than each making one. On its own it generates nothing: the blocks it adds are
/// empty and the parameters it adds have one argument each, and `simplify-cfg` runs straight after
/// it and takes both back out to a fixed point. That is section 26.7's arrangement, and it is why
/// the position matters more than the pass does until the loop passes land on top of it.
///
/// `header-copy` is section 26.7's third step and `canon` runs again after it, which is the same
/// section's instruction to re-canonicalize the loops it changed. It has to: what the copy leaves
/// is a loop entered from a block that branches two ways, and a block that branches two ways is not
/// a preheader. Nothing between the two needs the properties, so the second run is bookkeeping
/// against the loop passes that come later rather than something this level's output depends on,
/// and `simplify-cfg` after it takes out the blocks and parameters both runs added that nothing
/// used.
///
/// `licm` comes after the copy and the canonicalization behind it, and section 27.1 says why it has
/// to. What it may move in front of a loop depends on what runs on every entry to the loop, and
/// after that pair that is the whole body rather than the header alone. Running it before the
/// copy would leave it the header, which is most of the pass's value gone. It is also the reason
/// the copy exists, so the two are one arrangement read from either end.
///
/// It is in the three speed levels and not in `-Os` or `-Oz`. Moving a computation out of a loop
/// does not remove one, so there are no bytes in it for a level whose cost model is size, and the
/// one thing it can cost is a spill inside the loop, which is bytes. That trade is worth making for
/// time and there is nothing on the other side of it for space.
///
/// `unroll` runs after `licm` and only at the two speed levels. After, because what it does is copy
/// the body, and a computation licm has already moved in front of the loop is one the copies do not
/// each get their own of. It needs the same shape licm does and for the same reason, a loop that
/// tests at the bottom with a preheader in front of it, so it sits at the end of the same run of
/// loop passes rather than anywhere of its own. `simplify-cfg` straight after it is what turns the
/// chain of copies into one block, since each copy now ends in a jump to the next and a block with
/// one way in and one way out is a block that goes away.
///
/// `number` goes straight after that `simplify-cfg` and immediately before `load-forward`, and the
/// two are one arrangement rather than two passes that happen to be adjacent. On its own it removes
/// an instruction here and there, because the arithmetic a person writes is not usually written
/// twice. What it is really for is the arithmetic the front end writes underneath: a subscript
/// lowered twice is the same multiply and add twice, and giving the two one name is what turns a
/// store and a load that `load-forward` was refusing into a store and a load of the same address.
/// Running it the other way round would leave the pass after it nothing it did not already have.
///
/// `load-forward` goes next, and the position is the whole of what
/// the pass is worth. It is the block local half of document 16, so what it can find is bounded by
/// how much code is in one block, and `simplify-cfg` merging the straight line chains is what makes
/// the blocks the largest they are ever going to be. At the two speed levels that position is also
/// just after `unroll`, which is where the case the pass was written for lives: the body
/// copies now sit in one block, and a copy that stored to an array slot and read it straight back
/// is a store and a load of the same address with nothing in between.
///
/// `fold` runs a second time after it, and it is not there out of habit. What forwarding leaves
/// behind is a value that arrived as a constant through memory, `grid[i] = 3` read back as a load
/// that is now the literal three, and nothing else this late in the list would fold the arithmetic
/// on top of it. The first `fold` ran before any of this existed.
///
/// `simplify` runs after that second `fold` for the same reason the second `fold` runs at all.
/// Folding does not remove an instruction whose answer is a constant somebody still adds, it only
/// writes the constant down, and an index folded to zero leaves a `ptr_add x, 0` behind. That is
/// an identity the peephole takes and nothing else in the list is about. The unrolled body is
/// where they come from: the copy that runs first subscripts the array at zero, so the multiply
/// that worked its offset out is a multiply by zero, and until now the last thing any level did to
/// that arithmetic was fold it. The add of zero reached the selector and was written out as an
/// `addq $0`. Over the corpus at `-O2` the run is worth 3000 bytes across 1830 programs, 224 of
/// them smaller and 4 larger, with every result unchanged.
///
/// `hoist` is the first of the two check passes and it runs where it does because of what is above
/// it. It needs a loop that tests at the bottom, which is what `header-copy` makes, and it needs a
/// preheader to put a check in, which is what the `canon` after it puts back. Running it before
/// `discharge` rather than after is deliberate as well: what it leaves in the preheader is a check
/// over the whole range the loop sweeps, and that is a fact `discharge` can then use on anything
/// else in front of the loop that is about the same bytes.
///
/// `discharge` is second to last, between `hoist` and `dce`, and both neighbours are the reason. It
/// reads the dominator tree to find a safety check whose bytes an earlier check already covered, so
/// it wants the graph after the block merging rather than before, when a straight run of code is
/// still several blocks and a fact does not reach the check it would cover. What it leaves behind
/// is the `cap_of` the check it removed was reading, which nothing now reads, so `dce` after it is
/// what makes the function smaller rather than shorter by one instruction. It is in every level
/// except `-O0`, which keeps every check on purpose: document 14 measures against a build where
/// nothing was discharged, and that build is `-O0`.
const O1: &[&str] = &[
    "expect",
    "fold",
    "simplify",
    "narrow",
    "simplify",
    "thread",
    "phiopt",
    "prune",
    "canon",
    "header-copy",
    "canon",
    "licm",
    "simplify-cfg",
    "number",
    "load-forward",
    "fold",
    "simplify",
    "hoist",
    "discharge",
    "dead-plane",
    "coalesce",
    "dce",
];

/// `-O2`. The level the code quality claim is about. Section 9.1 asks for two e-graph rounds
/// around the loop pipeline, the full inlining cost model, Memory SSA and the full alias
/// analysis stack, and then the scalar and machine passes on top.
///
/// `short-circuit` is the one pass here that `-O1` does not have, and section 22.5 is where the
/// level comes from. It folds the two branches of an `a && b` into one, which costs the right
/// operand's work on the path that was skipping it and buys a branch the machine no longer has to
/// guess. That is a trade worth making when the aim is speed and the branch is hard to call, and
/// it is not one to make by default, which is what `-O1` is.
///
/// It runs before `thread` and `phiopt` rather than after, and the order is not arbitrary. Both of
/// those look at edges, and the collapse removes a block and turns two edges into one, so running
/// it first hands them a smaller graph with nothing lost. The other way round, threading is free
/// to give the second branch's block another predecessor, and a block two edges reach is one the
/// collapse will not touch, so a chain that was foldable stops being foldable.
///
/// `canon` and `licm` run a second time after `split`, and that pair is the only thing here that
/// looks at what `split` wrote. A guard goes in the preheader of the loop being split, which for an
/// inner loop is a block inside the loops around it, and the guard asks the runtime how big each
/// object is. On a matrix multiply that is four queries per entry to the innermost loop, two of
/// them about a pointer that has not changed since it was allocated, and the pass that would take
/// those out ran seven passes ago. `spec/safe-memory/13-performance.md` section 13.1 measured the
/// cost and tamnd/rucc#893 is the rest of it.
///
/// `ivopts` goes last of the loop passes, because it is the one that decides what the loop's
/// variables finally are and everything above it is still moving code around. It is followed by
/// `simplify-cfg` and the pair cannot be separated. Section 28.4 has a loop stop asking its counter
/// anything, and the counter goes on being incremented round the loop until the parameter carrying
/// it is taken away. `crate::dce` says in its own documentation that it cannot do that, because the
/// only reader left is the addition feeding the parameter back and a use count never reaches zero
/// on a cycle. `crate::simplify_cfg` can, and says it was written for this. Without it the loop
/// pays for the new pointer and keeps the old counter as well, which over the corpus is about half
/// of what choosing badly costs.
const O2: &[&str] = &[
    "expect",
    "fold",
    "simplify",
    "narrow",
    "simplify",
    "switch-conv",
    "short-circuit",
    "thread",
    "phiopt",
    "prune",
    "canon",
    "header-copy",
    "canon",
    "licm",
    "unroll",
    "simplify-cfg",
    "number",
    "load-forward",
    "fold",
    "simplify",
    "hoist",
    "split",
    "canon",
    "licm",
    "ivopts",
    "simplify-cfg",
    "discharge",
    "dead-plane",
    "coalesce",
    "dce",
];

/// `-O3`. `-O2` plus loop vectorization, larger inlining and unrolling thresholds, interchange
/// and distribution where the dependence analysis is confident, and function specialization.
const O3: &[&str] = &[
    "expect",
    "fold",
    "simplify",
    "narrow",
    "simplify",
    "switch-conv",
    "short-circuit",
    "thread",
    "phiopt",
    "prune",
    "canon",
    "header-copy",
    "canon",
    "licm",
    "unroll",
    "simplify-cfg",
    "number",
    "load-forward",
    "fold",
    "simplify",
    "hoist",
    "split",
    "canon",
    "licm",
    "ivopts",
    "simplify-cfg",
    "discharge",
    "dead-plane",
    "coalesce",
    "dce",
];

/// `-Os`. `-O2`'s passes under a size cost model: inlining only where it shrinks, no unrolling
/// and no vectorization.
///
/// The second peephole is here rather than cut for size, because every rule it can fire replaces
/// a term with a strictly smaller one. Tier one of `spec/optimizer/13-rewrite-rules.md` is
/// defined that way, so a level that wants smaller code wants more of it and not less.
///
/// `short-circuit` is the pass this level drops from `-O2`, for the mirror of that reason. What it
/// removes is a branch, which is time, and what it adds is the right operand's instructions on a
/// path that did not run them and an and on top. The code comes out no smaller and usually a byte
/// or two larger, so a level whose cost model is size has nothing to gain from it.
///
/// `hoist` is dropped here as well, and the reason is the same trade read the other way.
/// It takes a check out of a loop body and puts one in the preheader, plus the address arithmetic
/// the new check needs, so the loop runs faster and the function is a few instructions larger. That
/// is a speed transformation with a size cost, which is what `-Os` and `-Oz` are for declining.
///
/// `header-copy-small` is the same pass `-O1` and above run under section 26.6's smaller budget.
/// The copy is code growth and this level pays for it once per loop, so five instructions is what
/// it will pay. What it gets back is a body that is one region and an exit test at the bottom,
/// which is slightly smaller in the steady state, so the trade is worth making at a limit that
/// keeps the header small and not at one that copies twenty instructions to save two.
const OS: &[&str] = &[
    "expect",
    "fold",
    "simplify",
    "narrow",
    "simplify",
    "switch-conv",
    "thread",
    "phiopt",
    "prune",
    "canon",
    "header-copy-small",
    "canon",
    "simplify-cfg",
    "number",
    "load-forward",
    "fold",
    "simplify",
    "discharge",
    "dead-plane",
    "coalesce",
    "dce",
];

/// `-Oz`. `-Os` and additionally the outliner, with instruction selection preferring the smaller
/// encoding wherever there is a choice.
///
/// Header copying is the pass this level drops from `-Os`, which section 26.6 asks for by name. It
/// is the one loop canonicalization that makes the function bigger, `-Oz` is the level that would
/// rather have the branch than the bytes, and every reason to want the do-while form here is a
/// speed reason.
const OZ: &[&str] = &[
    "expect",
    "fold",
    "simplify",
    "narrow",
    "simplify",
    "switch-conv",
    "thread",
    "phiopt",
    "prune",
    "canon",
    "simplify-cfg",
    "number",
    "load-forward",
    "fold",
    "simplify",
    "discharge",
    "dead-plane",
    "coalesce",
    "dce",
];

/// The passes this level runs, before the command line adds to or removes from them.
#[must_use]
pub const fn for_level(level: OptLevel) -> &'static [&'static str] {
    match level {
        OptLevel::O0 => O0,
        OptLevel::O1 => O1,
        OptLevel::O2 => O2,
        OptLevel::O3 => O3,
        OptLevel::Os => OS,
        OptLevel::Oz => OZ,
    }
}

/// Which passes the IR is written out around.
///
/// Empty by default, which is the whole point: a dump is a debugging aid and writing files
/// nobody asked for is not one.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Dumps {
    /// Every pass, on both sides.
    all: bool,
    /// The passes to write out before.
    before: Vec<String>,
    /// The passes to write out after.
    after: Vec<String>,
}

impl Dumps {
    /// Adds one `-fdump-ir=` argument.
    ///
    /// # Errors
    ///
    /// When the argument is not `all`, `before-<pass>` or `after-<pass>`, or when it names a
    /// pass this compiler does not have. A misspelled pass name that quietly dumped nothing
    /// would look exactly like a pass that did not run.
    pub fn add(&mut self, spec: &str) -> Result<(), String> {
        if spec == "all" {
            self.all = true;
            return Ok(());
        }
        let (side, name) = match spec.split_once('-') {
            Some(("before", name)) => (&mut self.before, name),
            Some(("after", name)) => (&mut self.after, name),
            _ => {
                return Err(format!(
                    "`{spec}` is not a dump this compiler makes, which are `all`, \
                     `before-<pass>` and `after-<pass>`"
                ));
            }
        };
        if pass::find(name).is_none() {
            return Err(format!("`{name}` is not a pass this compiler has, see --print-pipeline"));
        }
        side.push(name.to_owned());
        Ok(())
    }

    /// Whether anything is dumped at all.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        !self.all && self.before.is_empty() && self.after.is_empty()
    }

    /// Whether the IR is written out before this pass runs.
    #[must_use]
    pub fn wants_before(&self, name: &str) -> bool {
        self.all || self.before.iter().any(|it| it == name)
    }

    /// Whether the IR is written out after this pass runs.
    #[must_use]
    pub fn wants_after(&self, name: &str) -> bool {
        self.all || self.after.iter().any(|it| it == name)
    }
}

/// What the command line asked the optimizer for.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Options {
    /// Which pipeline to start from.
    pub level: OptLevel,
    /// The passes `-f<name>` added and `-fno-<name>` removed, in the order they were given, so
    /// that the last mention of a pass is the one that decides.
    pub toggles: Vec<(String, bool)>,
    /// What `-fpass-fuel=<pass>=<n>` limited, by pass name.
    pub fuel: HashMap<String, u32>,
    /// What `-fpass-fuel-global=<n>` limited the whole pipeline to, across every pass.
    ///
    /// This is the outer search of the two in section 4.5 of
    /// `spec/optimizer/04-pass-manager.md`. Halving this finds the pass, and halving
    /// `-fpass-fuel` for that pass finds the rewrite inside it. Two searches of twenty
    /// compilations each beat one search over a space nobody knows the shape of.
    pub global_fuel: Option<u32>,
    /// What `-fdisable-<pass>` and `-fenable-<pass>` said about which functions a pass runs on.
    pub gates: Gates,
    /// What `-fdump-ir=` asked to see.
    pub dumps: Dumps,
    /// Whether the verifier runs after every pass that changed anything.
    pub verify: bool,
    /// Which definitions in this module something else may replace at load time.
    ///
    /// The analyses that read a body and write down what they found have to stop at a name like
    /// that, because the body they read is not the one that will run. [`Pic::Library`] is the
    /// answer when the object may end up in a shared library and the exported names in it are
    /// interposable, which is what `-fPIC` alone means and is gcc's default.
    ///
    /// [`Pic::Executable`] is the answer for everything else, and that includes
    /// `-fno-semantic-interposition`, where the build has promised that the definition here is the
    /// one that runs. It is a promise and not a deduction, and it is the one every distribution
    /// makes, because a library that cannot inline its own functions into each other pays for the
    /// possibility of an interposition that never happens.
    ///
    /// This is not the same value the code generator is given. How an address is reached does not
    /// change under that promise, and gcc does not change it either: a variable a shared library
    /// exports is still read out of the global offset table, because the promise is about which
    /// definition runs rather than about how many copies of the variable there are.
    pub interposition: Pic,
}

impl Default for Options {
    /// The default level with nothing added to it, and the verifier on in a debug build, which
    /// is what section 9.10 asks for.
    fn default() -> Self {
        Self {
            level: OptLevel::default(),
            toggles: Vec::new(),
            fuel: HashMap::new(),
            global_fuel: None,
            gates: Gates::default(),
            dumps: Dumps::default(),
            verify: cfg!(debug_assertions),
            interposition: Pic::Executable,
        }
    }
}

impl Options {
    /// The options a level asks for on its own.
    #[must_use]
    pub fn for_level(level: OptLevel) -> Self {
        Self { level, ..Self::default() }
    }

    /// The passes the level and the `-f` flags chose, in order, before the gates are consulted.
    ///
    /// A pass named by `-f<name>` that the level did not choose is appended, because the only
    /// place it could go that does not need an ordering rule nobody wrote down is the end.
    #[must_use]
    pub fn chosen(&self) -> Vec<&'static str> {
        let mut names: Vec<&str> = for_level(self.level).to_vec();
        for (name, on) in &self.toggles {
            let name = name.as_str();
            match *on {
                true if !names.contains(&name) => names.push(name),
                true => {}
                // A pass that says it is required stays, since turning it off is a compile that
                // fails rather than one that optimizes less. See [`Pass::required`].
                false => names.retain(|it| *it != name || required(it)),
            }
        }
        names.into_iter().filter_map(pass::find).map(Pass::name).collect()
    }
}

/// Whether the pass of that name is one `-fno-<name>` does not turn off.
fn required(name: &str) -> bool {
    pass::find(name).is_some_and(|pass| pass.required())
}

impl Options {
    /// The passes that will run, in order, over at least one function.
    ///
    /// A pass `-fenable-<name>` reached that the level did not choose is appended after them,
    /// for the same reason and in the same place. It runs only over the functions the gate names,
    /// which is the whole point of the flag: a pass being in this list is not the same question as
    /// a pass running on the function somebody is looking at.
    #[must_use]
    pub fn passes(&self) -> Vec<&'static dyn Pass> {
        let mut names = self.chosen();
        for name in self.gates.enabled() {
            // Through the pass list rather than straight from the gate, because the name the
            // pass holds outlives this call and the one the gate holds does not.
            let Some(found) = pass::find(name) else { continue };
            if !names.contains(&found.name()) {
                names.push(found.name());
            }
        }
        names.into_iter().filter_map(pass::find).collect()
    }
}

/// One written out copy of the IR.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Dump {
    /// What to call it, which is a number, a side and a pass name, as in `01-after-fold`. The
    /// number is there so that a directory listing is in the order the passes ran.
    pub name: String,
    /// The module, in the textual form from `spec/08-ir.md`.
    pub text: String,
}

/// What one pass had to say about one function.
///
/// One of these per pass per function with a body, whether or not the pass said anything, because
/// a pass that reports nothing being visible as a pass that reports nothing is the point of the
/// record. Section 42.2 of `spec/optimizer/42-measurement.md` has the argument.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Remark {
    /// Which pass, by the name a `-f` flag spells.
    pub pass: &'static str,
    /// Which function, by the name in the source.
    pub func: Symbol,
    /// What it said.
    pub stats: Stats,
}

/// What running the pipeline produced beyond the changed module.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Report {
    /// The dumps asked for, in the order they were taken. The manager does not write files,
    /// because nothing below the driver in `spec/18-package-layout.md` knows what a file is.
    pub dumps: Vec<Dump>,
    /// A pass that left the IR in a state the verifier refuses, named, with what it said.
    pub broke: Vec<String>,
    /// How much fuel each pass spent, which is the number a bisection halves.
    pub spent: Vec<(&'static str, u32)>,
    /// What every pass said about every function, in the order the passes ran and then in the
    /// order the module holds its functions. This is what `-fopt-info` prints.
    pub remarks: Vec<Remark>,
}

impl Report {
    /// Everything one pass said across the whole module, added up.
    ///
    /// The counts of an event are addable across functions because an event names a site in a
    /// pass rather than a fact about a program, which is the reason [`crate::stats::Event::what`]
    /// is a fixed string.
    #[must_use]
    pub fn totals(&self, pass: &str) -> Stats {
        let mut total = Stats::new();
        for remark in self.remarks.iter().filter(|it| it.pass == pass) {
            total.merge(&remark.stats);
        }
        total
    }
}

/// Runs the pipeline over the module.
///
/// Every pass sees every function with a body, one at a time, and a pass runs over the whole
/// module before the next one starts. That order is what makes the dumps readable: a dump is
/// the state of the program between two passes rather than between two functions.
pub fn run(module: &mut Module, names: &Interner, opts: &Options) -> Report {
    let mut report = Report::default();
    let chosen = opts.chosen();
    // One cache per function, kept across passes because a pass runs over the whole module
    // before the next one starts. A cache that lived only as long as one function would be
    // thrown away between every pass and would never answer a second question. Section 4.2 of
    // `spec/optimizer/04-pass-manager.md` is the plan for turning the loop inside out, and the
    // day that happens this map becomes a local in the inner loop.
    let mut cached: HashMap<FuncId, Analyses> = HashMap::new();
    // The machine, once for the module, because every function in it is compiled for the same
    // target at the same goal. It goes into each function's cache rather than into a parameter of
    // its own, per `crate::machine`.
    let machine = Machine::of(module, opts.level);
    // What the whole pipeline has left, which every pass draws its own allowance out of and
    // gives the unspent part of back. A pass past the end of it is given nothing rather than
    // skipped, so it still runs, still reports, and still transforms nothing.
    let mut budget = opts.global_fuel;
    // What each pass has left of what `-fpass-fuel` gave it. One allowance across every place
    // the list names that pass, rather than one allowance each, because the number in the flag
    // is meant to be the number of rewrites that happened. A peephole that runs twice under
    // `-fpass-fuel=simplify=5` and rewrites ten things would make the bisection in section 4.5
    // of `spec/optimizer/04-pass-manager.md` step over the rewrite it was looking for.
    let mut allowance = opts.fuel.clone();
    let passes = opts.passes();
    // Before anything runs, because each of these is a fact about the module and every pass after
    // this sees one function. Only when a pass in this run reads them: a flag nothing looks at
    // would show up in every `-O0` dump and mean nothing to anybody reading one.
    if passes.iter().any(|pass| READS_SUMMARIES.contains(&pass.name())) {
        nofree::annotate(module, names, opts.interposition);
        extents::annotate(module, opts.interposition);
        params::annotate(module, opts.interposition);
        heap::annotate(module, names);
    }
    for (index, pass) in passes.into_iter().enumerate() {
        let name = pass.name();
        if opts.dumps.wants_before(name) {
            report.dumps.push(dump(index, "before", name, module, names));
        }
        let mut fuel = match (allowance.get(name).copied(), budget) {
            // Whichever limit is tighter, because two limits that disagree mean the one that
            // stops first, and a bisection that started with the global one has to stay inside
            // it while the per pass one is halved.
            (Some(count), Some(left)) => Fuel::of(count.min(left)),
            (Some(count), None) => Fuel::of(count),
            (None, Some(left)) => Fuel::of(left),
            (None, None) => Fuel::unlimited(),
        };
        // What the level and the `-f` flags decided, which is what a gate overrides for the
        // functions it names and leaves alone for the ones it does not.
        let default = chosen.contains(&name);
        for id in module.funcs() {
            if module[id].is_declaration() {
                continue;
            }
            if !opts.gates.allows(name, default, id.raw(), names.resolve(module[id].name)) {
                // No remark either. A pass that did not run on a function has nothing to say
                // about it, and a record saying it found nothing would read as a pass that
                // looked.
                continue;
            }
            let an = cached.entry(id).or_insert_with(|| Analyses::new(machine));
            let stats = pass.run(&mut module[id], an, &mut fuel);
            // A pass that changed nothing preserved everything, whatever it says about itself,
            // so the cheap case does not need every pass to have a second opinion about it.
            // A pass that did change something is taken at its word, and in a checked build the
            // word is checked.
            let keeps = if stats.changed() { pass.preserves() } else { Preserved::ALL };
            for broken in an.settle(&module[id], keeps, opts.verify) {
                let func = names.resolve(module[id].name);
                report.broke.push(format!(
                    "the {name} pass said it preserved {} of {func} and did not",
                    broken.name()
                ));
            }
            // Here rather than after the pass, and this function rather than the module. A pass
            // is a function pass, so the only thing it can have broken is the function it was
            // given, and walking the other ones again after every one of them is the quadratic
            // walk `rucc_ir::verify_func` exists to avoid. Doing it here is also what lets the
            // message name the function, which the module walk could not, and it puts the
            // failure next to the pass that caused it rather than at the end of the module.
            if stats.changed() && opts.verify {
                if let Err(errors) = rucc_ir::verify_func(module, &module[id], names) {
                    let func = names.resolve(module[id].name);
                    for error in errors {
                        report
                            .broke
                            .push(format!("the {name} pass left invalid IR in {func}, {error}"));
                    }
                }
            }
            // The record is the only place the manager learns that anything happened, which is
            // why the pass cannot leave recording until later. See `crate::stats`.
            report.remarks.push(Remark { pass: name, func: module[id].name, stats });
        }
        // Added to rather than pushed, so a pass the list names twice is one line here with what
        // both of its runs spent. That is the number a bisection halves, and two lines under one
        // name would be two numbers where the flag takes one.
        match report.spent.iter_mut().find(|(it, _)| *it == name) {
            Some((_, total)) => *total += fuel.spent(),
            None => report.spent.push((name, fuel.spent())),
        }
        if let Some(left) = &mut budget {
            // Never below zero, because the allowance the pass was given was at most this.
            *left -= fuel.spent();
        }
        if let Some(left) = allowance.get_mut(name) {
            // Same, and for the same reason.
            *left -= fuel.spent();
        }
        if opts.dumps.wants_after(name) {
            report.dumps.push(dump(index, "after", name, module, names));
        }
    }
    report
}

/// The module written out, under a name that sorts in the order the passes ran.
fn dump(index: usize, side: &str, name: &str, module: &Module, names: &Interner) -> Dump {
    Dump { name: format!("{index:02}-{side}-{name}"), text: rucc_ir::print(module, names) }
}

/// Renders what `--print-pipeline` prints.
///
/// One line per pass, numbered from one, with what the pass does after it. A level that runs
/// nothing says so rather than printing an empty list, because an empty answer and a broken
/// command look the same.
#[must_use]
pub fn print(opts: &Options) -> String {
    let mut out = String::new();
    let _ = writeln!(out, "level: {}", opts.level);
    // Only when it was asked for, so the listing of a compilation nobody is bisecting is the
    // same listing it has always been. A run under a budget is a run whose output is not the
    // one the level asked for, and the listing is where that has to be visible.
    if let Some(count) = opts.global_fuel {
        let _ = writeln!(out, "global fuel: {count}");
    }
    let passes = opts.passes();
    if passes.is_empty() {
        let _ = writeln!(out, "no passes");
        return out;
    }
    for (index, pass) in passes.iter().enumerate() {
        let _ = write!(out, "{}: {}, {}", index + 1, pass.name(), pass.describe());
        // Only when a gate mentions the pass, so the listing of a compilation nobody is
        // debugging is the same listing it has always been.
        if let Some(note) = opts.gates.note(pass.name()) {
            let _ = write!(out, " [{note}]");
        }
        out.push('\n');
    }
    out
}

#[cfg(test)]
mod tests {
    use rucc_base::Interner;
    use rucc_ir::{
        Builder, Extra, Flags, Func, IntPred, MemInfo, MemOrder, Module, Opcode, Restrict,
        Signature, Type,
    };
    use rucc_session::OptLevel;
    use rucc_target::{Arch, Env, Os, TargetInfo, Triple};

    use super::{Dumps, Options, for_level};
    use crate::stats::Kind;
    use crate::{Pass, pass};

    /// A module with one function whose body has something to fold in it.
    fn module() -> (Interner, Module) {
        let mut names = Interner::new();
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let mut module = Module::new(names.intern("test.c"), &target);
        let func = foldable(&mut names, "f");
        module.add_func(func);
        (names, module)
    }

    /// A module with two of them, called `f` and `g`, in that order, so `f` is function 0.
    fn two_functions() -> (Interner, Module) {
        let mut names = Interner::new();
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let mut module = Module::new(names.intern("test.c"), &target);
        for name in ["f", "g"] {
            let func = foldable(&mut names, name);
            module.add_func(func);
        }
        (names, module)
    }

    /// A module with one function holding two identities the peephole takes, on a value that
    /// arrives as a parameter so that folding cannot get to them first.
    fn identities() -> (Interner, Module) {
        let mut names = Interner::new();
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let mut module = Module::new(names.intern("test.c"), &target);
        let i32_ = Type::int(32);
        let mut func = Func::new(
            names.intern("h"),
            Signature::new().with_params(&[i32_]).with_returns(&[i32_]),
        );
        let entry = func.create_block();
        let x = func.append_param(entry, i32_);
        let mut build = Builder::new(&mut func, entry);
        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);
        build.ret(&[product]);
        module.add_func(func);
        (names, module)
    }

    /// A function that returns a sign extension of a constant, which folding rewrites.
    fn foldable(names: &mut Interner, name: &str) -> Func {
        let mut func =
            Func::new(names.intern(name), Signature::new().with_returns(&[Type::int(64)]));
        let block = func.create_block();
        let mut build = Builder::new(&mut func, block);
        let narrow = build.iconst(Type::int(32), 7);
        let wide = build.unary(Opcode::SExt, narrow, Type::int(64));
        build.ret(&[wide]);
        func
    }

    /// Whether the pass said anything about the function, which it only does when it ran on it.
    fn spoke_about(report: &super::Report, pass: &str, func: &str, names: &Interner) -> bool {
        report.remarks.iter().any(|it| it.pass == pass && names.resolve(it.func) == func)
    }

    /// A module with a loop short enough for the unroller to flatten, over an array a parameter
    /// points at.
    ///
    /// Four iterations, which is a trip count the unroller takes whole. The copy that runs first
    /// subscripts the array at zero, so what works its offset out is a multiply by zero, and
    /// folding that is what leaves the addition this is here to look for.
    fn a_short_loop() -> (Interner, Module) {
        let mut names = Interner::new();
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let mut module = Module::new(names.intern("test.c"), &target);
        let (i32_, i64_) = (Type::int(32), Type::int(64));
        let signature = Signature::new().with_params(&[Type::PTR]).with_returns(&[i32_]);
        let mut func = Func::new(names.intern("sum"), signature);
        let entry = func.create_block();
        let head = func.create_block();
        let body = func.create_block();
        let exit = func.create_block();
        let p = func.append_param(entry, Type::PTR);
        let i = func.append_param(head, i32_);
        let acc = func.append_param(head, i32_);

        let mut build = Builder::new(&mut func, entry);
        let zero = build.iconst(i32_, 0);
        build.jump(head, &[zero, zero]);

        let mut build = Builder::new(&mut func, head);
        let four = build.iconst(i32_, 4);
        let more = build.icmp(IntPred::Slt, i, four);
        build.br_if(more, body, &[], exit, &[]);

        let mut build = Builder::new(&mut func, body);
        let wide = build.unary(Opcode::SExt, i, i64_);
        let scale = build.iconst(i64_, 4);
        let offset = build.binary(Opcode::Mul, wide, scale, Flags::NSW);
        let at = build.binary(Opcode::PtrAdd, p, offset, Flags::NONE);
        let read = build.load(i32_, at, plain(), Flags::NONE);
        let total = build.binary(Opcode::Add, acc, read, Flags::NONE);
        let one = build.iconst(i32_, 1);
        let next = build.binary(Opcode::Add, i, one, Flags::NSW);
        build.jump(head, &[next, total]);

        let mut build = Builder::new(&mut func, exit);
        build.ret(&[acc]);
        module.add_func(func);
        (names, module)
    }

    /// Memory with nothing said about it, which is what a plain subscript reads through.
    fn plain() -> MemInfo {
        MemInfo {
            size: 4,
            align: 4,
            order: MemOrder::NotAtomic,
            tbaa: None,
            owns: 0,
            restrict: Restrict::NONE,
        }
    }

    /// Every addition in the module whose right operand is the constant zero.
    fn adds_of_zero(module: &Module) -> usize {
        let mut found = 0;
        for id in module.funcs() {
            let func = &module[id];
            for block in func.blocks() {
                for inst in func.insts(block) {
                    if !matches!(func[inst].opcode, Opcode::Add | Opcode::PtrAdd) {
                        continue;
                    }
                    let args = &func[func[inst].args];
                    let Some(&rhs) = args.get(1) else { continue };
                    let rucc_ir::Def::Result { inst: from, .. } = func[rhs].def else { continue };
                    if func[from].opcode != Opcode::IConst {
                        continue;
                    }
                    let Extra::Imm(at) = func[from].extra else { continue };
                    found += usize::from(func[at].signed(func[rhs].ty) == 0);
                }
            }
        }
        found
    }

    /// An index the unroller worked out to zero does not leave the addition behind.
    ///
    /// The peephole is what removes it and the peephole used to run only near the top of the
    /// list, before the unroller had made any of these. Folding writes the constant down and
    /// leaves the addition, so an `add x, 0` reached the selector and was written out as an
    /// `addq $0` the machine runs for nothing. tamnd/rucc#875.
    #[test]
    fn an_index_folded_to_zero_is_not_added_to_anything() {
        let (names, mut module) = a_short_loop();
        assert_eq!(adds_of_zero(&module), 0, "the fixture already has one before anything runs");
        let report = super::run(&mut module, &names, &Options::for_level(OptLevel::O2));
        assert!(report.broke.is_empty(), "{:?}", report.broke);
        assert!(spent(&report, "unroll").is_some_and(|it| it > 0), "the loop was not unrolled");
        assert_eq!(adds_of_zero(&module), 0, "{}", rucc_ir::print(&module, &names));
    }

    #[test]
    fn every_pass_a_pipeline_names_is_a_pass_that_exists() {
        for level in
            [OptLevel::O0, OptLevel::O1, OptLevel::O2, OptLevel::O3, OptLevel::Os, OptLevel::Oz]
        {
            for name in for_level(level) {
                assert!(
                    pass::find(name).is_some(),
                    "{level} names `{name}` and no pass answers to it"
                );
            }
        }
    }

    #[test]
    fn a_pass_a_pipeline_names_twice_is_never_named_twice_in_a_row() {
        // Running a pass again after another pass has been through is the point of naming it
        // twice, and `simplify` around `narrow` is why the rule that used to be here, which was
        // that no level names a pass twice at all, is not the rule any more. Two runs with
        // nothing between them is still a mistake: the second one sees exactly what the first
        // one finished with, so it can only report that it found nothing.
        for level in
            [OptLevel::O0, OptLevel::O1, OptLevel::O2, OptLevel::O3, OptLevel::Os, OptLevel::Oz]
        {
            for pair in for_level(level).windows(2) {
                assert_ne!(pair[0], pair[1], "{level} runs `{}` twice in a row", pair[0]);
            }
        }
    }

    #[test]
    fn a_pass_the_pipeline_runs_twice_gets_one_allowance_and_reports_one_number() {
        // `-fpass-fuel=<pass>=<n>` is halved to find one rewrite, so the number in the flag has
        // to be the number of rewrites that happened however many times the list names the pass.
        // The peephole is named more than once from `-O1` up and the function below holds two
        // identities it takes, so a cap of one has to stop after one rather than after one per
        // occurrence.
        assert!(for_level(OptLevel::O2).iter().filter(|it| **it == "simplify").count() > 1);

        let (names, mut module) = identities();
        let free = super::run(&mut module, &names, &Options::for_level(OptLevel::O2));
        assert_eq!(spent(&free, "simplify"), Some(2), "{:?}", free.spent);

        let (names, mut module) = identities();
        let mut opts = Options::for_level(OptLevel::O2);
        opts.fuel.insert("simplify".to_owned(), 1);
        let capped = super::run(&mut module, &names, &opts);
        assert_eq!(capped.spent.iter().filter(|(name, _)| *name == "simplify").count(), 1);
        assert_eq!(spent(&capped, "simplify"), Some(1), "{:?}", capped.spent);
    }

    #[test]
    fn an_identity_only_the_narrow_pass_can_produce_is_still_taken() {
        // Issue 505, and the reason the peephole is named on both sides of `narrow`. C promotes
        // before it operates, so `unsigned char x; (unsigned char)(x & 255)` arrives here as a
        // thirty two bit `and` of a zero extension, and the rule that says `and` with every bit
        // set is the value has nothing at eight bits to match. `narrow` is the only producer that
        // width has. Before this ran twice the `and.i8` below reached the back end untouched.
        let mut names = Interner::new();
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let mut module = Module::new(names.intern("test.c"), &target);
        let (i8_, i32_) = (Type::int(8), Type::int(32));
        let mut func =
            Func::new(names.intern("f"), Signature::new().with_params(&[i8_]).with_returns(&[i8_]));
        let entry = func.create_block();
        let x = func.append_param(entry, i8_);
        let mut build = Builder::new(&mut func, entry);
        let wide = build.unary(Opcode::ZExt, x, i32_);
        let mask = build.iconst(i32_, 255);
        let kept = build.binary(Opcode::And, wide, mask, Flags::NONE);
        let back = build.unary(Opcode::Trunc, kept, i8_);
        build.ret(&[back]);
        module.add_func(func);

        let report = super::run(&mut module, &names, &Options::for_level(OptLevel::O2));
        assert!(report.broke.is_empty(), "{:?}", report.broke);
        let text = rucc_ir::print(&module, &names);
        assert!(!text.contains("and."), "the masking survived the pipeline\n{text}");
    }

    /// What a pass spent, or `None` if it did not run.
    fn spent(report: &super::Report, pass: &str) -> Option<u32> {
        report.spent.iter().find(|(name, _)| *name == pass).map(|&(_, count)| count)
    }

    /// The names of the passes a set of options would run, in order.
    fn names(opts: &Options) -> Vec<&'static str> {
        opts.passes().into_iter().map(Pass::name).collect()
    }

    #[test]
    fn every_level_that_splits_a_loop_looks_at_what_the_split_wrote() {
        // A guard goes in the preheader of the loop being split, which for an inner loop is inside
        // the loops around it, and it asks the runtime how big an object is. Nothing after `split`
        // moves anything, so a level that splits and then stops leaves those queries where they
        // cost the most.
        for level in [super::O1, super::O2, super::O3, super::OS, super::OZ] {
            let Some(at) = level.iter().position(|pass| *pass == "split") else {
                continue;
            };
            assert!(
                level[at..].contains(&"licm"),
                "a level splits a loop and never looks at the guard again"
            );
        }
    }

    #[test]
    fn every_level_that_chooses_induction_variables_takes_the_old_one_away_afterwards() {
        // The counter a loop stops asking anything is still incremented round it, and what removes
        // the parameter carrying it is `simplify-cfg` rather than `dce`. See the comment on `O2`.
        // A level that chooses and then stops keeps both variables and is worse off than if it had
        // never chosen at all.
        for level in [super::O1, super::O2, super::O3, super::OS, super::OZ] {
            let Some(at) = level.iter().position(|pass| *pass == "ivopts") else {
                continue;
            };
            assert!(
                level[at + 1..].contains(&"simplify-cfg"),
                "a level chooses induction variables and leaves the one it stopped using behind"
            );
        }
    }

    #[test]
    fn every_run_of_the_pass_that_reads_a_summary_is_named_as_one_that_does() {
        // A run left off the list gets no table of globals and no caller guarantees, and answers
        // that there were none rather than that nobody built them.
        for pass in pass::PASSES {
            let name = pass.name();
            assert_eq!(
                name.starts_with("discharge"),
                super::READS_SUMMARIES.contains(&name),
                "`{name}` and READS_SUMMARIES disagree about whether it reads a summary"
            );
        }
    }

    #[test]
    fn the_level_that_optimizes_nothing_still_removes_what_nothing_reaches() {
        // Two passes at `-O0`, and neither of them is an optimization. See the comment on the
        // level itself, and issue 359.
        assert_eq!(names(&Options::for_level(OptLevel::O0)), ["expect", "simplify-cfg"]);
        assert!(names(&Options::for_level(OptLevel::O2)).len() > 1);
    }

    #[test]
    fn a_pass_is_removed_by_no_and_added_by_the_bare_name_and_the_last_word_wins() {
        let mut opts = Options::for_level(OptLevel::O2);
        opts.toggles.push(("fold".to_owned(), false));
        assert!(!names(&opts).contains(&"fold"), "{:?}", names(&opts));
        opts.toggles.push(("fold".to_owned(), true));
        assert!(names(&opts).contains(&"fold"), "{:?}", names(&opts));

        let mut off = Options::for_level(OptLevel::O0);
        off.toggles.push(("fold".to_owned(), true));
        assert_eq!(
            names(&off),
            ["expect", "simplify-cfg", "fold"],
            "a pass the level did not choose is still reachable"
        );
    }

    #[test]
    fn asking_for_a_pass_twice_does_not_run_it_twice() {
        let mut opts = Options::for_level(OptLevel::O2);
        let before = names(&opts);
        opts.toggles.push(("fold".to_owned(), true));
        assert_eq!(names(&opts), before);
    }

    #[test]
    fn the_pipeline_listing_names_the_level_and_every_pass_in_order() {
        let text = super::print(&Options::for_level(OptLevel::O2));
        assert!(text.starts_with("level: -O2\n"), "{text}");
        assert!(text.contains("1: expect, "), "{text}");
        assert!(text.contains("2: fold, "), "{text}");
        // Turning off everything the level asked for leaves the one pass that cannot be turned
        // off, since the back end has no rule for what it removes. See `Pass::required`.
        let mut none = Options::for_level(OptLevel::O0);
        none.toggles.push(("expect".to_owned(), false));
        none.toggles.push(("simplify-cfg".to_owned(), false));
        let none = super::print(&none);
        assert!(none.contains("1: expect, "), "{none}");
        assert!(!none.contains("simplify-cfg"), "{none}");
    }

    #[test]
    fn running_the_pipeline_changes_the_module_and_reports_what_it_spent() {
        let (names, mut module) = module();
        let report = super::run(&mut module, &names, &Options::for_level(OptLevel::O2));
        // Folding rewrites the sign extension into a constant, and then the constant it was
        // extending is read by nothing and dead code elimination takes it out. One
        // transformation each, which is what the two of them together are for. Asserted by
        // name rather than as the whole vector, so a pass added later does not fail this.
        assert_eq!(spent(&report, "fold"), Some(1));
        assert_eq!(spent(&report, "dce"), Some(1));
        assert!(report.broke.is_empty(), "{:?}", report.broke);
        assert!(report.dumps.is_empty(), "nothing asked for a dump");
        assert!(rucc_ir::print(&module, &names).contains("iconst.i64 7"));
    }

    #[test]
    fn the_analyses_survive_a_pass_that_keeps_them_and_not_one_that_does_not() {
        // The pipeline half of the analysis manager. A branch on a constant, so `simplify-cfg`
        // has something to do and says it preserved nothing, and the whole run comes out with
        // the verifier and the manager both satisfied. What a pass that lied would produce is in
        // `crate::analysis`, where a lie can be told on purpose.
        let mut names = Interner::new();
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let mut module = Module::new(names.intern("test.c"), &target);
        let mut func = Func::new(names.intern("f"), Signature::new());
        let entry = func.create_block();
        let dead = func.create_block();
        let exit = func.create_block();
        let mut build = Builder::new(&mut func, entry);
        let never = build.iconst(Type::int(1), 0);
        build.br_if(never, dead, &[], exit, &[]);
        for block in [dead, exit] {
            let mut build = Builder::new(&mut func, block);
            build.ret(&[]);
        }
        module.add_func(func);
        let report = super::run(&mut module, &names, &Options::for_level(OptLevel::O2));
        // The fold, and then the merge of the arm it left with one way into it.
        assert_eq!(spent(&report, "simplify-cfg"), Some(2));
        assert!(report.broke.is_empty(), "{:?}", report.broke);
        let text = rucc_ir::print(&module, &names);
        // The labels, which start a line, and not the mentions of one, which are indented. One
        // left: the arm nothing reaches went, and the arm that is always taken came up into the
        // entry, which is what is left of the branch.
        assert_eq!(text.matches("\nblock").count(), 1, "there is more than one block:\n{text}");
    }

    #[test]
    fn no_pass_that_optimizes_runs_at_no_optimization_however_much_there_is_to_do() {
        let (names, mut module) = module();
        let before = rucc_ir::print(&module, &names);
        let report = super::run(&mut module, &names, &Options::for_level(OptLevel::O0));
        // The two passes the level runs looked, found no `__builtin_expect`, no branch they could
        // read and no block nothing reaches, and spent nothing. The constant arithmetic the fixture
        // is full of is still there, which is the part of `-O0` that has not changed.
        assert_eq!(report.spent, vec![("expect", 0), ("simplify-cfg", 0)]);
        assert_eq!(rucc_ir::print(&module, &names), before);
    }

    #[test]
    fn a_gate_takes_a_pass_away_from_one_function_and_leaves_the_other_alone() {
        let (names, mut module) = two_functions();
        let mut opts = Options::for_level(OptLevel::O2);
        opts.gates.add(false, "fold=g").expect("g is a function and fold is a pass");
        let report = super::run(&mut module, &names, &opts);
        assert!(spoke_about(&report, "fold", "f", &names));
        assert!(!spoke_about(&report, "fold", "g", &names), "fold ran where it was gated off");
        assert!(spoke_about(&report, "dce", "g", &names), "one pass gated off is not all of them");
        // What the gate is for: the two functions came out different, and the difference is one
        // pass on one function rather than a level on a file.
        let text = rucc_ir::print(&module, &names);
        assert_eq!(text.matches("sext.i64").count(), 1, "{text}");
    }

    #[test]
    fn a_function_can_be_gated_by_the_number_it_has_in_the_module() {
        let (names, mut module) = two_functions();
        let mut opts = Options::for_level(OptLevel::O2);
        opts.gates.add(false, "fold=0").expect("0 is a function and fold is a pass");
        let report = super::run(&mut module, &names, &opts);
        assert!(!spoke_about(&report, "fold", "f", &names), "function 0 is the first one");
        assert!(spoke_about(&report, "fold", "g", &names));
    }

    #[test]
    fn enabling_a_pass_reaches_one_function_at_a_level_that_did_not_ask_for_it() {
        let (names, mut module) = two_functions();
        let mut opts = Options::for_level(OptLevel::O0);
        opts.gates.add(true, "fold=1").expect("1 is a function and fold is a pass");
        let running: Vec<&str> = opts.passes().into_iter().map(Pass::name).collect();
        assert_eq!(
            running,
            ["expect", "simplify-cfg", "fold"],
            "the flag has to put the pass in the pipeline"
        );
        let report = super::run(&mut module, &names, &opts);
        assert!(!spoke_about(&report, "fold", "f", &names), "nothing asked for f");
        assert!(spoke_about(&report, "fold", "g", &names));
        let text = rucc_ir::print(&module, &names);
        assert_eq!(text.matches("sext.i64").count(), 1, "{text}");
    }

    #[test]
    fn a_pass_gated_off_everywhere_runs_on_nothing_and_still_says_so() {
        let (names, mut module) = two_functions();
        let before = rucc_ir::print(&module, &names);
        let mut opts = Options::for_level(OptLevel::O2);
        for pass in pass::PASSES {
            opts.gates.add(false, pass.name()).expect("a pass in the list is a pass that exists");
        }
        let report = super::run(&mut module, &names, &opts);
        assert!(report.remarks.is_empty(), "a pass that did not run has nothing to report");
        assert_eq!(spent(&report, "fold"), Some(0), "the pass is still in the pipeline");
        assert_eq!(rucc_ir::print(&module, &names), before);
    }

    #[test]
    fn the_pipeline_listing_says_which_passes_a_gate_touched() {
        let mut opts = Options::for_level(OptLevel::O2);
        // `narrow` rather than `fold`, because a gate names a pass and the level runs some of its
        // passes more than once. A note on one of those is printed against every run of it, and
        // the count at the bottom would then be counting repeats rather than what it is asking.
        opts.gates.add(false, "narrow=2-4").expect("narrow is a pass");
        let text = super::print(&opts);
        assert!(text.contains("4: narrow, "), "{text}");
        assert!(text.contains("[off for 2-4]"), "{text}");
        assert_eq!(text.matches('[').count(), 1, "a pass no gate mentions says nothing extra");
    }

    #[test]
    fn every_pass_at_no_fuel_leaves_the_module_exactly_as_it_found_it() {
        // The check section 9.10 asks for by name, and the reason it is here rather than in each
        // pass is that it has to hold for every pass that is ever added.
        for pass in pass::PASSES {
            let (names, mut module) = module();
            let before = rucc_ir::print(&module, &names);
            let mut opts = Options::for_level(OptLevel::O0);
            // The level's own passes out of the way first, so that what this measures is the one
            // pass under test. A pass turned off and then on again is on, so this is right for
            // those passes as well as for the others. `expect` cannot be turned off, so it is
            // starved of fuel instead and is expected in the report ahead of the pass under test.
            opts.toggles.push(("simplify-cfg".to_owned(), false));
            opts.toggles.push((pass.name().to_owned(), true));
            opts.fuel.insert("expect".to_owned(), 0);
            opts.fuel.insert(pass.name().to_owned(), 0);
            let report = super::run(&mut module, &names, &opts);
            let mut want = vec![("expect", 0)];
            if pass.name() != "expect" {
                want.push((pass.name(), 0));
            }
            assert_eq!(report.spent, want, "{} spent fuel it had none of", pass.name());
            assert_eq!(
                rucc_ir::print(&module, &names),
                before,
                "{} transformed the module at fuel zero",
                pass.name()
            );
        }
    }

    #[test]
    fn fuel_is_shared_across_the_functions_of_a_module() {
        let mut names = Interner::new();
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let mut module = Module::new(names.intern("test.c"), &target);
        for which in ["f", "g"] {
            let mut func =
                Func::new(names.intern(which), Signature::new().with_returns(&[Type::int(64)]));
            let block = func.create_block();
            let mut build = Builder::new(&mut func, block);
            let narrow = build.iconst(Type::int(32), 7);
            let wide = build.unary(Opcode::SExt, narrow, Type::int(64));
            build.ret(&[wide]);
            module.add_func(func);
        }
        let mut opts = Options::for_level(OptLevel::O2);
        opts.fuel.insert("fold".to_owned(), 1);
        let report = super::run(&mut module, &names, &opts);
        // One fold across both functions, because fuel is per pass and per compilation. Dead
        // code elimination has its own and spends it on the constant the one fold orphaned.
        assert_eq!(spent(&report, "fold"), Some(1));
        assert_eq!(spent(&report, "dce"), Some(1));
        let text = rucc_ir::print(&module, &names);
        assert_eq!(text.matches("sext.i64").count(), 1, "{text}");
    }

    #[test]
    fn global_fuel_is_spent_by_the_passes_in_order_and_the_rest_get_none() {
        let (names, mut module) = module();
        let mut opts = Options::for_level(OptLevel::O2);
        opts.global_fuel = Some(1);
        let report = super::run(&mut module, &names, &opts);
        // Folding is first and there is one thing to fold, so it takes the one unit and dead
        // code elimination gets nothing. Without the budget it would have taken the constant
        // that fold orphaned, which is what the other test measures.
        assert_eq!(spent(&report, "fold"), Some(1));
        assert_eq!(spent(&report, "dce"), Some(0));
        let text = rucc_ir::print(&module, &names);
        assert!(text.contains("iconst.i64 7"), "{text}");
        assert!(text.contains("iconst.i32 7"), "the orphaned constant is still there, {text}");
    }

    #[test]
    fn a_budget_of_nothing_leaves_the_module_alone_and_still_runs_every_pass() {
        let (names, mut module) = module();
        let before = rucc_ir::print(&module, &names);
        let mut opts = Options::for_level(OptLevel::O2);
        opts.global_fuel = Some(0);
        let report = super::run(&mut module, &names, &opts);
        assert_eq!(rucc_ir::print(&module, &names), before);
        assert!(report.spent.iter().all(|(_, spent)| *spent == 0), "{:?}", report.spent);
        // Every pass, because a pass out of fuel is a pass that ran and did nothing rather than
        // a pass that was skipped, and a bisection that skipped passes would be searching a
        // different pipeline at every step. One line per name rather than one per place the list
        // names it, because what a name was given is one allowance across all of them.
        let mut want: Vec<&str> = opts.passes().into_iter().map(Pass::name).collect();
        want.sort_unstable();
        want.dedup();
        let mut got: Vec<&str> = report.spent.iter().map(|&(name, _)| name).collect();
        got.sort_unstable();
        assert_eq!(got, want);
    }

    #[test]
    fn the_tighter_of_the_two_limits_is_the_one_that_stops_the_pass() {
        // A pass allowed more than the budget gets the budget.
        let (names, mut under) = module();
        let mut opts = Options::for_level(OptLevel::O2);
        opts.global_fuel = Some(0);
        opts.fuel.insert("fold".to_owned(), 9);
        assert_eq!(spent(&super::run(&mut under, &names, &opts), "fold"), Some(0));

        // And a pass allowed less than the budget keeps its own limit, with the budget left
        // over for whatever comes after it.
        let (names, mut over) = module();
        let mut opts = Options::for_level(OptLevel::O2);
        opts.global_fuel = Some(9);
        opts.fuel.insert("fold".to_owned(), 0);
        let report = super::run(&mut over, &names, &opts);
        assert_eq!(spent(&report, "fold"), Some(0));
        assert_eq!(spent(&report, "dce"), Some(0), "nothing was orphaned for it to remove");
    }

    #[test]
    fn the_pipeline_listing_says_when_there_is_a_budget_and_says_nothing_when_there_is_not() {
        let opts = Options::for_level(OptLevel::O2);
        assert!(!super::print(&opts).contains("global fuel"));
        let with = Options { global_fuel: Some(12), ..Options::for_level(OptLevel::O2) };
        assert!(super::print(&with).contains("global fuel: 12"), "{}", super::print(&with));
    }

    #[test]
    fn a_dump_is_taken_on_the_side_that_asked_for_it_and_not_the_other() {
        let (names, mut module) = module();
        let mut opts = Options::for_level(OptLevel::O2);
        opts.dumps.add("after-fold").expect("a pass that exists");
        let report = super::run(&mut module, &names, &opts);
        // The level folds twice, once at the top and once after the loop pipeline, and what a
        // dump request names is a pass rather than a position, so both runs are written out. The
        // side is what this is about: not one of the two is a `before`.
        assert_eq!(report.dumps.len(), 2, "both runs of the pass, one dump each");
        assert!(
            report.dumps.iter().all(|dump| dump.name.ends_with("-after-fold")),
            "{:?}",
            report.dumps.iter().map(|dump| &dump.name).collect::<Vec<&String>>()
        );
        assert_eq!(report.dumps[0].name, "01-after-fold");
        assert!(report.dumps[0].text.contains("iconst.i64 7"));
    }

    #[test]
    fn asking_for_all_dumps_gives_both_sides_of_every_pass() {
        let (interner, mut module) = module();
        let opts = {
            let mut opts = Options::for_level(OptLevel::O2);
            opts.dumps.add("all").expect("all is always a dump");
            opts
        };
        let report = super::run(&mut module, &interner, &opts);
        // Both sides of every pass in the level, numbered by position, whatever the level
        // holds. Written out of the pipeline rather than as a literal, because the point of
        // the test is the pairing and the numbering and not which passes exist this month.
        let taken: Vec<&str> = report.dumps.iter().map(|d| d.name.as_str()).collect();
        let expected: Vec<String> = names(&opts)
            .into_iter()
            .enumerate()
            .flat_map(|(at, name)| {
                [format!("{at:02}-before-{name}"), format!("{at:02}-after-{name}")]
            })
            .collect();
        assert_eq!(taken, expected);
        // Either side of the fold, which is the pass that has something to do to this fixture,
        // found by name rather than by position so that a pass in front of it does not move it.
        let side = |which: &str| {
            let tail = format!("-{which}-fold");
            let dump = report.dumps.iter().find(|dump| dump.name.ends_with(&tail));
            dump.expect("the level folds").text.clone()
        };
        assert!(side("before").contains("sext.i64"));
        assert!(!side("after").contains("sext.i64"));
    }

    #[test]
    fn every_pass_leaves_a_record_for_every_function_whether_or_not_it_had_anything_to_say() {
        let (names, mut module) = module();
        let opts = Options::for_level(OptLevel::O2);
        let report = super::run(&mut module, &names, &opts);
        let ran: Vec<&'static str> = opts.passes().into_iter().map(Pass::name).collect();
        // One function in the fixture, so one record per pass, and the passes in the order they
        // ran. A pass that found nothing is in here with an empty record, which is the point:
        // a pass that fires on nothing is either dead code or a bug, and output that leaves it
        // out cannot say which.
        let seen: Vec<&'static str> = report.remarks.iter().map(|it| it.pass).collect();
        assert_eq!(seen, ran);
        assert!(report.remarks.iter().all(|it| names.resolve(it.func) == "f"));
        assert!(
            report.remarks.iter().any(|it| it.pass == "simplify" && it.stats.is_empty()),
            "there is nothing in the fixture for the peephole to do"
        );
    }

    #[test]
    fn a_pass_spends_one_unit_of_fuel_for_each_rewrite_it_reports() {
        // The invariant that keeps the record honest, checked over every pass rather than
        // written into each one. Fuel is taken immediately before a transformation and a
        // rewrite is recorded immediately after it, so the two counts are the same number
        // arrived at from two directions. A pass where they disagree either transformed without
        // asking, which breaks bisection, or rewrote without recording, which means the manager
        // did not run the verifier over what it produced.
        let (names, mut module) = module();
        let report = super::run(&mut module, &names, &Options::for_level(OptLevel::O2));
        for (pass, spent) in &report.spent {
            assert_eq!(
                report.totals(pass).total(Kind::Optimized),
                *spent,
                "{pass} spent {spent} units of fuel and did not say on what"
            );
        }
        assert!(report.spent.iter().any(|(_, spent)| *spent > 0), "nothing happened at all");
    }

    #[test]
    fn what_the_passes_said_is_what_opt_info_prints() {
        let (names, mut module) = module();
        let report = super::run(&mut module, &names, &Options::for_level(OptLevel::O2));
        let text = crate::optinfo::render("t.c", &report, &names, crate::Wants::all());
        assert!(
            text.contains("t.c: f: optimized: integer instruction folded to a constant (1) [fold]"),
            "{text}"
        );
        assert!(
            text.contains(
                "t.c: f: optimized: instruction with no effects and no users removed (1) [dce]"
            ),
            "{text}"
        );
        // Nothing in the fixture is a miss, so asking only for the misses gets nothing back,
        // and that is different from the flag having been left off.
        let mut misses = crate::Wants::none();
        misses.add("missed").expect("that kind exists");
        assert_eq!(crate::optinfo::render("t.c", &report, &names, misses), "");
    }

    #[test]
    fn the_verifier_says_which_function_it_refused_and_leaves_the_others_out_of_it() {
        // Two functions with the same foldable body, and a block in the second one that nothing
        // reaches, which the verifier refuses. The pass is not what put it there, and the
        // complaint says the pass anyway, because a pass that hands back a function the
        // verifier will not take is where the search has to start whoever wrote the block.
        let mut names = Interner::new();
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let mut module = Module::new(names.intern("test.c"), &target);
        module.add_func(foldable(&mut names, "f"));
        let mut g = foldable(&mut names, "g");
        let stranded = g.create_block();
        let mut build = Builder::new(&mut g, stranded);
        let seven = build.iconst(Type::int(64), 7);
        build.ret(&[seven]);
        module.add_func(g);

        // Folding on its own, because simplify-CFG would take the stranded block out and there
        // would be nothing left to complain about.
        let mut opts = Options::for_level(OptLevel::O0);
        opts.toggles.push(("simplify-cfg".to_owned(), false));
        opts.toggles.push(("fold".to_owned(), true));
        opts.verify = true;
        let report = super::run(&mut module, &names, &opts);

        assert_eq!(report.broke.len(), 1, "{:?}", report.broke);
        let complaint = &report.broke[0];
        assert!(complaint.starts_with("the fold pass left invalid IR in g,"), "{complaint}");
        assert!(complaint.contains("this block is not reachable"), "{complaint}");
    }

    #[test]
    fn a_function_a_pass_did_not_change_is_not_verified_after_it() {
        // The stranded block is in `f` this time and `f` has nothing to fold, so the pass runs
        // over an invalid function, changes nothing, and says nothing. That is the whole trade:
        // the verifier answers for the rewrite that just happened, and a function no rewrite
        // touched was already answered for when it was built.
        let mut names = Interner::new();
        let target = TargetInfo::new(Triple::new(Arch::X86_64, Os::Linux, Env::Gnu));
        let mut module = Module::new(names.intern("test.c"), &target);
        let mut f = Func::new(names.intern("f"), Signature::new().with_returns(&[Type::int(64)]));
        for _ in 0..2 {
            let block = f.create_block();
            let mut build = Builder::new(&mut f, block);
            let seven = build.iconst(Type::int(64), 7);
            build.ret(&[seven]);
        }
        module.add_func(f);
        module.add_func(foldable(&mut names, "g"));

        let mut opts = Options::for_level(OptLevel::O0);
        opts.toggles.push(("simplify-cfg".to_owned(), false));
        opts.toggles.push(("fold".to_owned(), true));
        opts.verify = true;
        let report = super::run(&mut module, &names, &opts);

        assert!(report.broke.is_empty(), "{:?}", report.broke);
        // And it did run on it, so this is the verifier staying quiet rather than the pass
        // being skipped.
        assert!(spoke_about(&report, "fold", "f", &names));
    }

    #[test]
    fn a_dump_of_a_pass_that_does_not_exist_is_refused_rather_than_ignored() {
        let mut dumps = Dumps::default();
        assert!(dumps.add("after-no-such-pass").is_err());
        assert!(dumps.add("sideways-fold").is_err());
        assert!(dumps.add("fold").is_err());
        assert!(dumps.is_empty());
    }
}