rucc_opt/

phiopt.rs

//! If-conversion, the part of it that turns a diamond into a select.
//!
//! Design: `spec/optimizer/22-phiopt-and-if-conversion.md`. A block ends in a two way branch, each
//! arm works out a value and does nothing else, and the two arms meet again at a block that takes
//! that value as a parameter. The branch is not deciding what the program does, it is deciding
//! which of two numbers to keep, and `select` says that directly. Section 22.2 asks for the shape
//! matcher and five transformations built on it, and the shape matcher plus the first, the second,
//! the third and half of the fourth of them is what is here.
//!
//! This is the highest variance transformation in the compiler and the document says so in its
//! third paragraph. Removing a mispredicted branch is worth about twenty cycles. Removing a
//! perfectly predicted one costs whatever the arm that is no longer skipped costs, and no static
//! analysis tells the two apart reliably. So the cost rule below is written to be argued with
//! rather than to be right, and section 42's measurement of the pass on and off at `-O2` is the
//! only honest evaluation there is.
//!
//! # The shape
//!
//! A head block ending in `br_if`, and a join block both arms reach. Each side of the branch is
//! either a block of its own that does nothing but work out values and jump to the join, or the
//! join itself. That gives three shapes and the pass takes all three: the diamond where both sides
//! have a block, and the two triangles where one side goes straight to the join because the arm
//! was empty and `simplify-cfg` already took it out.
//!
//! What replaces it is one block. Everything the arms worked out moves into the head, a `select`
//! is built for each of the join's parameters the two sides disagree about, and the head jumps to
//! the join carrying them. The arms are then unreachable and go, and the join is left for
//! `simplify-cfg` to merge upward when nothing else arrives at it.
//!
//! # The value the condition already settled
//!
//! Section 22.2's second transformation, `value_replacement`. `x = (a == b) ? b : a` is `x = a`,
//! because the only way to arrive at the join carrying `b` is along the edge where `a` and `b` are
//! the same number. No select is written, the branch goes with the rest of them, and whichever arm
//! was only there to work the other value out is left with nothing in it.
//!
//! What answers this is document 10's relational oracle, which is what section 22.2 says it needs
//! and this is its first caller in the compiler. The question is put as `Ranges::compare` at the
//! arm rather than as a range lookup, because the fact wanted is about two values rather than about
//! either one of them, and section 10.3 is where that distinction is made.
//!
//! The branch has to be on an equality, and that gate is the difference between a cheap pass and an
//! expensive one. Section 22.7 already names this query as the expensive part of the pass. What the
//! oracle records is what a dominating edge established between two values, and the edge out of a
//! `br_if` establishes something about two values only when the branch is on a comparison of them,
//! so a branch on `x < n` cannot answer whether two other values are equal and asking is a query
//! with nothing at the end of it. GCC gates the same way, on `EQ_EXPR` and `NE_EXPR`.
//!
//! The oracle only knows what the edge said about the two values it compared, so the forms gcc
//! calls the neutral and absorbing elements are answered here by looking at the instructions
//! instead. `x == 0 ? y : y + x` is `y + x`, because on the edge where `x` is zero the add gives
//! `y`, and `x != 0 ? y * x : 0` is `y * x`, because on the edge where it is zero the multiply
//! gives zero. The operation still runs on both paths, so it is still arm work and the cost rule
//! still asks about it, but the select is gone. Only operations that cannot trap are taken, and
//! the tested value has to be one operand, possibly widened, with the constant it was tested
//! against on the other side of the comparison. gcc's version of the same is in `value_replacement`
//! at `gcc/tree-ssa-phiopt.cc:1345`, through `neutral_element_p` and `absorbing_element_p`.
//!
//! One thing this does that the select cannot is a value whose type has no `select` at all. A
//! pointer is the case: `p == q ? q : p` used to keep its branch, because a `select` of two
//! pointers is a term nothing lowers, and it is now one move, because nothing has to be chosen.
//! The width refusal below is therefore asked after this rather than before it.
//!
//! It is one deep, in the same sense the factoring below is. What the join is handed is what gets
//! asked about, so `a == b ? b + c : a + c` factors to one add over a select and the select stays,
//! because what the oracle would have to know is that `b + c` and `a + c` are equal rather than
//! that `a` and `b` are. Asking about the factored operand instead is the change that would take
//! it, and it is left for when something measures a use for it.
//!
//! # The operation both arms did
//!
//! Section 22.2's third transformation, `factor_out_conditional_operation`. When the two sides
//! worked out their answers the same way from different operands, `cond ? f(a) : f(b)`, the select
//! goes under the operation rather than over it and the answer is `f(cond ? a : b)`. One operation
//! where there were two, and the same one select either way.
//!
//! It is structural and not a rewrite rule for the reason section 22.2 gives about all five: the
//! two `f`s are in different blocks and no pattern spans blocks. By the time they are in one block
//! the arms have already been hoisted and the select already written, and undoing that is a larger
//! rewrite than never writing it.
//!
//! The two operations have to match in everything but one operand. The opcode and the operand count
//! obviously. The flags, because those are what the optimizer is licensed to assume and one copy
//! written under the union of two sets of assumptions would be claiming on one path something only
//! the other path established. Whatever else the instruction carries, which for a comparison is the
//! predicate, since two predicates are two different questions. And exactly one operand position
//! apart, because two positions apart needs two selects and one operation, which is what one select
//! and two operations already cost.
//!
//! Agreeing in every position is allowed and is the case where no select is written at all. Both
//! arms working out the same thing from the same operands is what a common subexpression that
//! nothing has numbered looks like from here, and one copy of it serves both sides.
//!
//! The operation has to be worked out in the arm and read only by the arm's jump to the join. The
//! first because an operation to stop writing is one this has to be able to find. The second
//! because the one copy that replaces the two is written after the arms have gone, and a second
//! reader inside the arm would have been left pointing at an instruction that is no longer in any
//! block.
//!
//! Only the value the join takes is asked about, so a chain both arms share is factored one deep.
//! `total += (long long)(i * 2)` against `total += (long long)(i + 1)` has three operations in each
//! arm, the outermost pair factors, the sign extensions under them are the same operation on
//! different operands and would factor too, and they are not looked at because nothing hands them
//! to the join. Doing it to a depth would mean factoring what the select then reads, which is the
//! same function called on what it just produced, and it is left for when something asks for it.
//!
//! A constant operand is not refused and the reason is that it was measured and it goes both ways.
//! An operation with a constant in it takes that constant as an immediate, so factoring turns two
//! free immediates into a select between two values that have to be in registers, and on
//! `product + 2` against `product + 1` outside a loop that costs five bytes. On `total += 1`
//! against `total += 1000` inside one it saves fourteen, because the constants were being
//! rematerialized every iteration anyway. Over the corpus, refusing every constant operand trades
//! thirty two bytes of win for twenty two bytes of loss, which is ten bytes across 1453 programs
//! and is not worth a rule.
//!
//! # The store both arms made
//!
//! Section 22.2's fourth transformation, conditional store replacement, in the half of it that
//! needs no proof. When both arms store to the same place, `if (c) *p = a; else *p = b;` becomes
//! `*p = c ? a : b`, and the branch goes with the rest of them.
//!
//! Half, and which half is the whole point. Section 22.6 calls the other half the worst bug in the
//! document, because a store made on a path that was not going to make one writes memory the
//! program was not going to write. The load modify store form GCC uses, reading the location and
//! writing back what it read on the path that had no store, is not a no-op: it is a write, so it
//! races with another thread writing the same bytes, and it faults if the page is read only. What
//! would license it is knowing the location is written whatever happens, which is the predicate
//! section 22.6 asks for and which nothing here can answer yet.
//!
//! When both arms store to the same address, that predicate is discharged by the shape itself and
//! nothing has to be proved. One store before and one store after, to the same address, of a value
//! the program was going to write there on one path or the other. Nothing new is written, nothing
//! is written twice, and the order of that store against everything else in the function is where
//! it was. So this is the case that goes in with nothing more to ask. The one armed case goes in
//! only with the proof the next section gives, and is refused by name when that proof is missing,
//! so that `-fopt-info-all` says which of the two it was.
//!
//! What has to match beyond the address is the access itself: the flags, and the alignment, size,
//! aliasing node and `restrict` scope that a store carries alongside them, because the one store
//! written below carries one of each and two that disagree have no single answer to carry. The
//! address has to be the same value rather than a provably equal one, which is the strong form of
//! the question and is the only form available without an alias analysis. It also settles where the
//! address comes from: neither arm dominates the other, so a value both of them name is worked out
//! at or above the head, and the one store is written where it is available.
//!
//! The same value rather than the same address is also where most of what this does not catch
//! goes, so the two refusals are counted separately and say which. `if (x > 128) q[i] = 128; else
//! q[i] = x;` works `q + i` out twice, once in each arm, and two instructions that compute the same
//! address are two values, so this walks away from a diamond whose two stores go to the same place
//! by any reading a person would give it. What fixes that is document 16's value numbering turning
//! the two into one, not anything about memory, and hoisting the address by hand into `int *p =
//! &q[i];` is enough to get the fold today.
//!
//! `volatile` and atomic are refused. `volatile` because section 22.6 says never, and the reason is
//! not that the flags fail to match: how many accesses there are and what order they come in are
//! both observable, and a value that arrives through a select is a different program from one that
//! arrives through a branch. Atomic for the ordering rather than the access, since a store with an
//! order on it is a fence as much as a write.
//!
//! # The store one arm made
//!
//! The other half of section 22.2's fourth transformation, for the one kind of location where the
//! proof section 22.6 asks for can be given. `if (v > best[k]) best[k] = v;` becomes a load of
//! `best[k]`, a select between `v` and what the load found, and a store of the select, on both
//! paths. GCC does the same thing to the same loop and under the same two conditions.
//!
//! The location is a local whose address never leaves the function. That answers the race, since
//! another thread can only write bytes it can name and nothing outside this function can name
//! these, and it answers the read only page, since a local is on the stack. Where the address
//! points is `alias::origin` and whether anything else was ever handed it is `alias::Escapes`. A
//! function that gives stack back part way through, which is what a variable length array going
//! out of scope does, is refused whole.
//!
//! The head read or wrote the same address at the same width, with nothing after that access that
//! could have given the memory back. That answers the fault. `best[k]` with a `k` the branch was
//! guarding is an address the other path never reaches, and a local is only in the frame for the
//! offsets it has. An access the head already made there means the other path reached it anyway.
//! The same address is a structural question, two chains of the same pure operations over the same
//! values, because nothing before value numbering has made the arm's copy of a subscript and the
//! head's copy one value.
//!
//! A load in an arm is taken on the second condition alone. An arm that reads an address the head
//! already touched cannot fault on the path that did not read it, and a plain load is not something
//! another thread can see. That is what lets `if (v[i] > best[k]) best[k] = v[i];` go, where the arm
//! reads `v[i]` a second time. The loads an arm makes have to come before its store, since the one
//! store is written below everything the arms did.
//!
//! The store is counted as work, because it now happens on a path that did not make one, so the
//! predictability half of the cost rule still has its say about it. The load that finds the old
//! value is not counted, since the head has just touched the same bytes.
//!
//! # What a select is built for
//!
//! Two sides disagree about a parameter when they hand the join different values, and also when
//! they hand it different values that are the same number. The second half is there because the
//! corpus has eight diamonds whose two arms both work out the same constant, in separate
//! instructions that nothing has hash consed into one, and the tier six rule `select(c, x, x) -> x`
//! does not reach them for exactly the same reason: two operands that are not one value do not
//! match a pattern that writes one name twice. What would reach them is document 12.1's hash
//! consing or document 16's value numbering, and until one of those exists the cheap question is
//! worth asking here, where the alternative is a `select` this pass wrote itself between two sevens.
//!
//! # Why moving an arm's work into the head is safe
//!
//! Because the arm has exactly one predecessor, which is the head. That is checked, and it is the
//! whole of the argument in both directions.
//!
//! Downward: an instruction in the arm reads values that dominate the arm, and the head dominates
//! the arm too, so every one of them is available where the instruction is going. Upward: nothing
//! outside the arm can read what the arm defines except by the arm's own jump, since the arm
//! dominates only itself, and that jump's arguments are exactly what the selects are built out of.
//! An arm with two predecessors would break both halves at once, which is why the check is on the
//! predecessor count and not on the shape of the graph around it.
//!
//! The loop rules that `spec/optimizer/23-jump-threading.md` needs are not needed here, and the
//! reason is worth writing down rather than leaving as an absence. No edge is added, so no loop
//! gains a second way in and no loop can become irreducible. An arm cannot be a loop header, since
//! a header has a back edge and this arm has one predecessor and it is not itself. An arm can be a
//! latch, and then the head becomes the latch instead, which keeps the single latch property
//! document 07.3 wants rather than spoiling it. The one shape that would matter is a join that
//! only its own arms reach, which is a region unreachable from the entry, and the pass asks
//! whether the head is reachable before it looks at anything.
//!
//! # What it refuses, and every one of them is section 22.6
//!
//! An arm that does something. The predicate is [`rucc_ir::Opcode::has_effects`], which is what
//! dead code elimination deletes an instruction under, so an arm this pass will hoist is an arm
//! whose instructions could have been deleted outright had nothing read them. A call, a `volatile`
//! access and a load are all effects by that answer, which closes the second and sixth failures in
//! section 22.6 with one question. The exceptions are the stores and the loads the sections above
//! give a proof for, which are the effects this pass moves, and each of them only with its proof.
//!
//! A store the other side does not match, to a location the section above cannot prove anything
//! about. That is the first failure in section 22.6 and it gets a reason of its own rather than the
//! general one, because it is a different answer rather than a stricter one: the transformation
//! exists, it is section 22.2's fourth, and what is missing is the proof.
//!
//! An arm that divides. Division is not an effect, because nothing observes it and dead code
//! elimination is right to delete one, but it traps, and a trap on a path that did not have one is
//! section 22.6's third failure. The exception is a divisor that is a constant which is neither
//! zero nor minus one, which cannot trap and is most of the divisions real code contains.
//!
//! A value the two sides disagree about whose type has no `select`. The IR names a `select` at
//! eight, sixteen, thirty two and sixty four bit integers and at nothing else, so producing one of
//! any other type would build a term the back end has no rule for. That is an invisible gap rather
//! than a wrong answer, and the producer is the side that has to avoid it. It is asked after the
//! condition has had its say, because a value nothing has to choose between needs no select and so
//! does not need one that can be lowered.
//!
//! A branch that is already decided. Section 22.6 does not list this one and the corpus found it,
//! on a program whose source says `if (1)`. `simplify-cfg` runs after this pass and turns a decided
//! branch into a jump, and then the arm that cannot run is deleted whole and its work with it.
//! Converting first replaces a branch that costs nothing at run time with a select that costs
//! something, and it keeps alive the work in the arm that never ran, because the fold that would
//! undo it is `select(1, a, b) -> a` and that rule does not exist yet. The case cost twenty eight
//! bytes of `.text` and a multiply that could not happen.
//!
//! The question is put to `simplify_cfg::taken` rather than answered again here, for the
//! reason that function's own documentation gives: two answers about when a branch is decided
//! would be two compilers. It matters in this case rather than being tidiness. The condition on
//! `if (1)` is not a constant, it is `icmp ne 1, 0`, and `fold` leaves that standing on purpose,
//! because nothing lowers an `i1` by itself and folding one would turn working code into code that
//! does not build, which is issue 352. `taken` reads the answer off without leaving anything
//! standing, since the branch that was the comparison's only reader goes at the same time.
//!
//! # The cost rule
//!
//! Section 22.2 states it and this implements it without softening it.
//!
//! Both arms empty of instructions: convert, always. The select replaces a branch with one
//! operation that reads two values which already exist, and there is no machine where that is
//! worse. Nothing about predictability enters, because there is nothing being speculated.
//!
//! What is factored does not count as work. Both arms did the operation, one of them was always
//! going to do it, and afterwards one copy of it runs whichever way the branch would have gone, so
//! nothing is being speculated. A diamond whose arms factor away entirely converts on the same
//! terms as a diamond with empty arms, and one that factors down to two instructions is judged on
//! the two rather than on what it started as.
//!
//! What the head already worked out does not count either. The arm of `if (v[i] > best[k])` works
//! out the address of `best[k]` a second time, because lowering a subscript does not know it has
//! lowered it before, and once that copy is moved into the head it sits in the same block as the
//! first one and `number` makes the two one value. Counting it would refuse the diamond for work
//! nobody ends up doing.
//!
//! Arms with work left in them: up to [`heuristics::PHIOPT_ARM_INSTRUCTIONS`] instructions each,
//! and only when the branch probability is no nearer either end than
//! [`heuristics::PHIOPT_UNPREDICTABLE_MARGIN_PERCENT`] by document 11's estimate. A branch
//! the estimate calls one sided keeps its branch, because if the estimate is right the branch is
//! free and the arm is not.
//!
//! The estimate is usually a guess and the guess is often wrong, which section 22.6 lists as the
//! failure with no defence. Note where that leaves an unpredicted branch: document 11 answers even
//! and says it is guessing, even is inside the margin, so a branch nothing is known about is
//! treated as unpredictable and converted. That is the aggressive reading and it is deliberate,
//! since the alternative is a pass that fires on almost nothing and measures nothing.
//!
//! It is also, today, the only reading, and that is worth saying rather than leaving to be
//! discovered. Every static predictor in document 11 that gives a one sided answer keys on
//! something one arm of the branch does and the other does not: one arm never comes back, one arm
//! calls something cold, one arm leaves the loop, one arm returns a negative number. A diamond has
//! neither of those, because both of its arms fall through to the same block, so the predictors
//! that could refuse a conversion here are exactly the ones a diamond cannot trip. What is left is
//! the branch condition itself, which is `__builtin_expect` and the pointer heuristic at seventy.
//! The `expect` pass moves the hint onto the branch before this pass runs, so the hint is what the
//! rule is really about. A plain `__builtin_expect` claims ninety, which is inside the margin, so it
//! converts, and only `__builtin_expect_with_probability` at more than ninety seven keeps its
//! branch. The margin was a quarter until #1902 timed a diamond at known rates and found the branch
//! losing at ninety and ninety five and winning only at ninety nine.
//!
//! # Which level, and how many times
//!
//! Every level that optimizes, which is section 22.2's `-O1` and above.
//!
//! Once at `-O1`, and twice at `-O2` and `-O3`. Section 22.7 asks for a second instance after the
//! loop pipeline, because the loop passes make diamonds. The second instance waits for the `fold`
//! and `simplify` after `unroll`, because a body `unroll` copied has a branch in each copy whose
//! condition is a constant that has not been folded yet. Converted, each of those is a conditional
//! move on a constant nothing later folds. Folded first, it is a branch this pass leaves to
//! `simplify-cfg`. On the corpus at `-O2` the two instances convert 561 diamonds where the first
//! converts 546. It is not at `-O1` because `unroll` is not.
//!
//! Section 22.2 also wants a peephole run after this one, so that the rule set can answer what the
//! `select` becomes. Those rules are tier six of `spec/optimizer/13-rewrite-rules.md`, in
//! `rules/select.rules`, and the run that fires them is the `simplify` every level already has
//! after this pass. `select(c, 1, 0)` is `zext(c)` there, and a select between a value and one
//! step from it is the value moved by the condition.

use rucc_cost::heuristics;
use rucc_ir::{
    Block, Builder, Def, Extra, Flags, Func, Imm, Inst, InstData, IntPred, MemInfo, MemOrder,
    Opcode, Type, Value,
};

use crate::alias::{self, Escapes, Origin};
use crate::cfg::Cfg;
use crate::fold::constant;
use crate::profile::Probability;
use crate::range::ops::Truth;
use crate::range::query::Ranges;
use crate::simplify_cfg::{self, Bindings};
use crate::{Analyses, Fuel, Pass, Preserved, Stats};

/// Recorded once for each diamond that became a select.
const CONVERTED: &str =
    "branch whose two arms only work out a value replaced by the value and no branch";

/// Recorded once for each operation both arms did that ended up being done once.
const FACTORED: &str = "operation both arms did to different operands done once below the branch";

/// Recorded once for each value the branch condition settled, so that no select was written for it.
const VALUE_IMPLIED: &str =
    "value the two arms disagreed about settled by the condition rather than by a select";

/// Recorded once for each pair of stores to one place that became one store below the branch.
const STORE_REPLACED: &str = "store both arms made to the same place made once below the branch";

/// Recorded once for each store only one arm made, to a local the head had already touched.
const STORE_GUARDED: &str =
    "store one path made to a local the branch had already touched made on both paths";

/// Recorded once for each load an arm made of an address the head had already touched.
const LOAD_SPECULATED: &str =
    "load one path made of an address the branch had already touched made on both paths";

/// Recorded for a diamond one of whose arms does something that has to happen.
const ARM_HAS_EFFECTS: &str =
    "branch kept, an arm does something that only happens on the path it is on";

/// Recorded for a diamond where only one of the two paths stores at all.
const STORE_ON_ONE_PATH: &str =
    "branch kept, a store only one path makes would have to be made on the other path too";

/// Recorded for a diamond where both paths store but not the same store to the same place.
const STORES_DO_NOT_MATCH: &str =
    "branch kept, both paths store but not to one address the two of them name the same way";

/// Recorded for a diamond one of whose arms divides by something that could be zero.
const ARM_MAY_TRAP: &str = "branch kept, an arm divides and doing it on both paths could trap";

/// Recorded for a diamond whose two arms disagree about a value nothing can choose between.
const NO_SELECT_AT_THAT_WIDTH: &str =
    "branch kept, the value the arms disagree about is not a width a select is lowered at";

/// Recorded for a diamond whose arms are more work than the branch is worth.
const ARMS_TOO_LONG: &str = "branch kept, its arms are more work than doing both of them is worth";

/// Recorded for a diamond whose branch the estimate says the machine will get right.
const BRANCH_IS_PREDICTED: &str =
    "branch kept, it goes one way often enough that the machine will predict it";

/// Recorded for a diamond that would have been converted if there had been fuel for it.
const CONDITION_IS_DECIDED: &str =
    "branch kept, its condition is already known and the arm that cannot run is better deleted";
const NO_FUEL: &str = "branch kept, the pass ran out of fuel";

/// The pass.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PhiOpt;

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

    fn describe(&self) -> &'static str {
        "a branch whose two arms only work out a value becomes a select, and the branch goes"
    }

    fn preserves(&self) -> Preserved {
        // Nothing. Blocks stop existing and an edge stops existing with them, so every analysis
        // built on the graph was built on a different graph.
        Preserved::NONE
    }

    fn run(&self, func: &mut Func, an: &mut Analyses, fuel: &mut Fuel) -> Stats {
        let mut stats = Stats::new();
        if func.entry().is_none() {
            return stats;
        }
        for head in func.blocks().collect::<Vec<Block>>() {
            let cfg = an.cfg(func);
            if !cfg.reaches(head) {
                continue;
            }
            let Some(shape) = diamond(func, cfg, head) else { continue };
            let store = storing(func, &shape);
            // Before the refusals rather than after, because one of them is about a value having a
            // width a select is lowered at, and a value the condition settles gets no select at all.
            // The waste that costs is a range query on a diamond that then turns out to have an
            // effect in it, and the equality gate below is what keeps that from being every diamond.
            let implied = implied(func, an, &shape);
            if let Some(reason) = refused(func, &shape, store.as_ref(), &implied) {
                stats.missed(reason);
                continue;
            }
            let plan = factoring(func, &shape, &implied);
            // What is factored is not speculated. Both arms did the operation, one of them was
            // always going to do it, and after this one copy of it runs whichever way the branch
            // would have gone. So it comes off the count the cost rule is about, and a diamond
            // whose arms factor away entirely converts on the same terms as a diamond with empty
            // arms: always, because there is nothing being done that was not being done before.
            // The store both arms made comes off the count for the same reason a factored operation
            // does. One of the two was always going to run, and afterwards one copy of it runs
            // whichever way the branch would have gone, so nothing about memory is being speculated.
            // A store only one arm made stays on it, since the other path now makes it too.
            let paired = store.as_ref().is_some_and(|one| one.insts.len() == 2);
            let levels: usize = plan.iter().flatten().map(|one| one.levels().count()).sum();
            let replaced = levels + usize::from(paired);
            let saved = u32::try_from(replaced).unwrap_or(u32::MAX);
            let work = shape
                .arms
                .map(|arm| arm.map_or(0, |block| work(func, head, block)).saturating_sub(saved));
            if work.iter().any(|&count| count > 0) {
                if work.iter().any(|&count| count > heuristics::PHIOPT_ARM_INSTRUCTIONS) {
                    stats.missed(ARMS_TOO_LONG);
                    continue;
                }
                // The first edge out of the head, which is the arm taken when the condition holds,
                // because `Cfg::successors` is in the order the terminator names its targets. Which
                // of the two is asked about does not matter, since the question is whether the
                // number is near even and the other edge is its complement.
                if !unpredictable(an.frequencies(func).taken(head, 0)) {
                    stats.missed(BRANCH_IS_PREDICTED);
                    continue;
                }
            }
            if !fuel.take() {
                // Where the pass stops rather than where it starts skipping, for the reason jump
                // threading gives: a budget that has reached zero will not have anything in it at
                // the next block either, and the refusals above are the counts worth being true.
                stats.missed(NO_FUEL);
                break;
            }
            let loads = shape
                .arms
                .iter()
                .flatten()
                .flat_map(|&arm| func.insts(arm))
                .filter(|&inst| func[inst].opcode == Opcode::Load)
                .count();
            convert(func, &shape, &plan, store.as_ref(), &implied);
            // The graph was about the function as it was a moment ago, and the manager clears the
            // cache after the pass returns, which is too late for the next block.
            an.clear();
            for _ in plan.iter().flatten().flat_map(Factored::levels) {
                stats.optimized(FACTORED);
            }
            for _ in implied.iter().flatten() {
                stats.optimized(VALUE_IMPLIED);
            }
            match store.as_ref().map(|one| one.insts.len()) {
                Some(2) => stats.optimized(STORE_REPLACED),
                Some(_) => stats.optimized(STORE_GUARDED),
                None => {}
            }
            for _ in 0..loads {
                stats.optimized(LOAD_SPECULATED);
            }
            stats.optimized(CONVERTED);
        }
        stats
    }
}

/// A branch whose two arms meet again, and what each of them hands the block they meet at.
pub(crate) struct Diamond {
    /// The block the branch is in.
    pub(crate) head: Block,
    /// The bit the branch is on, which is the bit the selects are on.
    pub(crate) cond: Value,
    /// The block both arms reach.
    pub(crate) join: Block,
    /// The block on each side, when that side is a block of its own rather than the join.
    ///
    /// Index zero is the side taken when the condition holds, which is the side `select` calls
    /// `then`, and the order is the order the terminator names its targets in.
    pub(crate) arms: [Option<Block>; 2],
    /// What each side hands the join, in the order the join takes its parameters.
    pub(crate) args: [Vec<Value>; 2],
}

/// The diamond this block is the head of, if it is the head of one.
pub(crate) fn diamond(func: &Func, cfg: &Cfg, head: Block) -> Option<Diamond> {
    let entry = cfg.entry()?;
    let term = func.terminator(head)?;
    if func[term].opcode != Opcode::BrIf {
        return None;
    }
    let cond = *func[func[term].args].first()?;
    let mut targets = func.successors(term);
    let sides = [targets.next()?, targets.next()?];
    // Both arms at the same block is a branch that goes to one place carrying two argument lists.
    // It is convertible and it is rare enough not to be worth a second shape, and `simplify-cfg`
    // takes the case where the two lists agree.
    if sides[0].block == sides[1].block {
        return None;
    }
    let through = [
        passes_through(func, cfg, head, sides[0].block),
        passes_through(func, cfg, head, sides[1].block),
    ];
    // The diamond, then the two triangles. A side that is not the join has to be a block that
    // reaches it, which is what makes the arm below a side that has one.
    let join = match through {
        [Some(left), Some(right)] if left == right => left,
        [Some(left), _] if left == sides[1].block => left,
        [_, Some(right)] if right == sides[0].block => right,
        _ => return None,
    };
    // A join that is the head is a loop with nothing outside it, and one that is the entry is a
    // block control arrives at rather than one it reaches.
    if join == head || join == entry {
        return None;
    }
    let arms = [
        (sides[0].block != join).then_some(sides[0].block),
        (sides[1].block != join).then_some(sides[1].block),
    ];
    let mut args = [Vec::new(), Vec::new()];
    for (index, side) in sides.iter().enumerate() {
        let carried = match arms[index] {
            // The arm's own jump is what tells the join what this side worked out.
            Some(arm) => func.successors(func.terminator(arm)?).next()?.args,
            None => side.args,
        };
        args[index] = func[carried].to_vec();
    }
    Some(Diamond { head, cond, join, arms, args })
}

/// Where this side of the branch ends up, when it is a block whose only job is to get there.
///
/// Everything this asks is needed. Parameters, because a block that takes them is being told
/// something on the edge and there would be nothing to tell it once the edge is gone. One
/// predecessor and it being the head, because that is the whole argument for moving the block's
/// work upward and it is also what makes removing the block afterwards legal. A jump, because an
/// arm that branches is a second decision and this pass is about one.
fn passes_through(func: &Func, cfg: &Cfg, head: Block, block: Block) -> Option<Block> {
    if !func[block].params.is_empty() {
        return None;
    }
    // A block an image holds the address of has a way in the graph does not show: what arrives
    // there is a `goto *p` that can be in another function, so the one predecessor below is not the
    // only one and the block is not one this pass may take out.
    if func.block_name(block).is_some() {
        return None;
    }
    match cfg.predecessors(block) {
        [only] if *only == head => {}
        _ => return None,
    }
    let term = func.terminator(block)?;
    if func[term].opcode != Opcode::Jump {
        return None;
    }
    Some(func.successors(term).next()?.block)
}

/// Why this diamond is left alone, or `None` when nothing is in the way.
///
/// The store plan is passed in because the two stores it names are the one pair of instructions
/// with effects this pass is allowed to move, and everything else with an effect still refuses.
fn refused(
    func: &Func,
    shape: &Diamond,
    store: Option<&Stored>,
    implied: &[Option<usize>],
) -> Option<&'static str> {
    // A branch nobody has to take is not a branch worth removing. `simplify-cfg` runs after this
    // pass and turns a decided branch into a jump, and then the arm that cannot run is deleted
    // whole. Converting first replaces a branch that costs nothing with a select that costs
    // something, and the fold that would undo it is a rule the set does not have yet, so the work
    // in the arm that never ran survives into the machine code. The corpus found this on `if (1)`.
    //
    // The question is put to `simplify-cfg` rather than answered again here, for the reason its
    // own documentation gives: two answers about when a branch is decided would be two compilers.
    // It matters in this case, because the condition on `if (1)` is not a constant, it is a
    // comparison of two constants, which `fold` deliberately leaves standing.
    let term = func.terminator(shape.head).expect("the head of a diamond ends in its branch");
    if simplify_cfg::taken(func, term, &Bindings::new()).is_some() {
        return Some(CONDITION_IS_DECIDED);
    }
    let moving: &[Inst] = store.map_or(&[], |one| &one.insts);
    for &arm in shape.arms.iter().flatten() {
        for inst in func.insts(arm) {
            if func.is_terminator(inst) || moving.contains(&inst) {
                continue;
            }
            if readable(func, shape.head, inst) {
                continue;
            }
            if func[inst].opcode == Opcode::Store {
                // Named separately from the effects below because it is a different answer rather
                // than a stricter one. A store the other side does not make is section 22.2's
                // fourth transformation without its proof, and section 22.6 calls it the worst bug
                // in the document: making it on both paths writes memory the program was not going
                // to write, which is not a no-op if another thread is writing the same bytes and is
                // not a no-op if the page is read only. What licenses it is a local nothing else
                // can name that the head already touched, and a store that got here had neither.
                return Some(mismatch(func, shape));
            }
            if func[inst].opcode.has_effects() {
                return Some(ARM_HAS_EFFECTS);
            }
            if !speculatable(func, inst) {
                return Some(ARM_MAY_TRAP);
            }
        }
    }
    let params = func[shape.join].params.to_vec();
    for (index, &param) in params.iter().enumerate() {
        // The two sides agreeing about a parameter is the common case in a triangle, where one
        // side passes on what it was already holding, and it needs no select at all. Neither does
        // one the condition settles, which is why this is asked after that question rather than
        // before it: a value of a type nothing can select between is fine when nothing has to.
        if agree(func, shape.args[0][index], shape.args[1][index]) {
            continue;
        }
        if implied.get(index).copied().flatten().is_some() {
            continue;
        }
        if !selectable(func[param].ty) {
            return Some(NO_SELECT_AT_THAT_WIDTH);
        }
    }
    None
}

/// Whether the two sides hand the join the same thing, so that no `select` is needed for it.
///
/// The same value is the easy answer and it is the one a triangle gives, where one side passes on
/// what it was already holding. The same constant is the answer the corpus asked for. `x ? 7 : 7`
/// arrives here as two `iconst.i32 7` instructions, one in each arm, which are two values because
/// nothing has hash consed them into one. Asking only about the value builds a `select` between two
/// sevens, which costs a compare, a byte and a conditional move to work out that seven is seven.
/// The module comment says what the general answer would be and why it is not available yet.
fn agree(func: &Func, then: Value, other: Value) -> bool {
    if then == other {
        return true;
    }
    let (Some((left, lty)), Some((right, rty))) = (constant(func, then), constant(func, other))
    else {
        return false;
    };
    lty == rty && left == right
}

/// Whether doing this on a path that was not going to do it is harmless.
///
/// Only division asks anything here, because the caller has already refused everything with an
/// effect and what is left is arithmetic. Zero is the divisor everybody knows about. Minus one is
/// the other one: the smallest signed number divided by it is not representable and x86 raises the
/// same exception it raises for zero.
pub(crate) fn speculatable(func: &Func, inst: Inst) -> bool {
    let opcode = func[inst].opcode;
    if !matches!(opcode, Opcode::SDiv | Opcode::UDiv | Opcode::SRem | Opcode::URem) {
        return true;
    }
    let Some(&divisor) = func[func[inst].args].get(1) else { return false };
    let Some((imm, ty)) = constant(func, divisor) else { return false };
    if imm.unsigned() == 0 {
        return false;
    }
    imm.signed(ty) != -1
}

/// A store one or both arms make, which becomes one store below the branch.
///
/// Section 22.2's fourth transformation. `if (c) *p = a; else *p = b;` is `*p = c ? a : b`, and
/// the number of stores is one before and one after, to the same address, of a value the program
/// was going to write there on one path or the other. With one arm storing, the other side writes
/// back what it finds, and that is only done where the module comment says it can be.
struct Stored {
    /// The store each side wrote, which goes when the one copy below replaces them.
    insts: Vec<Inst>,
    /// What each side wrote, taken in the order the branch names its targets, and `None` on a side
    /// that wrote nothing and so writes back what is already there.
    values: [Option<Value>; 2],
    /// The address, which is one value both sides named.
    addr: Value,
    /// The store to write once, whose value operand is replaced by the select above it.
    data: InstData,
    /// What is stored.
    ty: Type,
}

/// Which side's value serves for both, for each join parameter the branch condition settles.
///
/// Section 22.2's second transformation, `value_replacement`. `x = (a == b) ? b : a` is `x = a`,
/// because the only way to arrive carrying `b` is along the edge where `a` and `b` are the same
/// number. The select goes, and so does whichever arm was only there to work the other value out.
///
/// The answer for a parameter is the side whose value is passed on. If the two are known equal on
/// one side's edge, then that side's value is the other side's value there, and the other side's
/// value is right on both edges. Availability comes for free: everything both arms worked out is
/// moved into the head before the jump is written, so a value that came from an arm is defined
/// above the point it is now read at.
///
/// # Why the condition has to be an equality
///
/// This is the pass's one expensive question and section 22.7 says so. What answers it is document
/// 10's relational oracle, which records what a dominating edge established between two values, and
/// the edge out of a `br_if` establishes something about two values only when the branch is on a
/// comparison of them. A branch on `x < n` says nothing about whether two other values are equal,
/// so asking is a query that cannot come back with anything. Gating on the comparison being an
/// equality is what turns this from a query per diamond into a query per diamond that could
/// possibly answer, which on the corpus is a small fraction of them. GCC gates the same way, on
/// `EQ_EXPR` and `NE_EXPR` at `gcc/tree-ssa-phiopt.cc`.
fn implied(func: &Func, an: &mut Analyses, shape: &Diamond) -> Vec<Option<usize>> {
    let count = shape.args[0].len();
    let mut answers = vec![None; count];
    if !equality(func, shape.cond) {
        return answers;
    }
    let mut asking = Vec::new();
    for index in (0..count).filter(|&index| worth_asking(func, shape, index)) {
        let pair = [shape.args[0][index], shape.args[1][index]];
        match element(func, shape.cond, pair) {
            Some(side) => answers[index] = Some(side),
            None => asking.push(index),
        }
    }
    if asking.is_empty() {
        return answers;
    }
    // Cloned because the two are held at once and the cache hands out one borrow at a time. It is
    // paid for only by a diamond that got this far, which the two gates above have already made
    // rare, and section 22.7 is where the cost of this query was budgeted.
    let cfg = an.cfg(func);
    let dom = an.dominators(func);
    let mut ranges = Ranges::new(func, cfg, dom);
    for index in asking {
        let pair = [shape.args[0][index], shape.args[1][index]];
        for side in 0..2 {
            let Some(block) = shape.arms[side] else { continue };
            if ranges.compare(IntPred::Eq, pair[0], pair[1], block) == Truth::Always {
                answers[index] = Some(1 - side);
                break;
            }
        }
    }
    answers
}

/// Whether the branch is on a comparison that says two values are the same or are not.
fn equality(func: &Func, cond: Value) -> bool {
    let Def::Result { inst, .. } = func[cond].def else { return false };
    if func[inst].opcode != Opcode::ICmp {
        return false;
    }
    matches!(func[inst].extra, Extra::IntPred(IntPred::Eq | IntPred::Ne))
}

/// Which side's value serves for both, when it is an operation that gives the other side's value
/// once the tested value is the constant it was tested against.
///
/// These are gcc's neutral and absorbing elements. On the edge where `x == c` holds, `y + x` is
/// `y` when `c` is zero, and `y * x` is zero when `c` is zero, whatever `y` is. So when the other
/// side carries `y`, or zero, the side that works the operation out is right on both edges. The
/// comparison
/// has to be of a value against a constant, and the value has to be an operand of the operation,
/// itself or widened. Every operation here is one that cannot trap, which a division by the tested
/// value could, so running it on the other edge as well changes nothing but the time.
fn element(func: &Func, cond: Value, pair: [Value; 2]) -> Option<usize> {
    let Def::Result { inst, .. } = func[cond].def else { return None };
    let equal = match func[inst].extra {
        Extra::IntPred(IntPred::Eq) => 0,
        Extra::IntPred(IntPred::Ne) => 1,
        _ => return None,
    };
    let &[a, b] = &func[func[inst].args] else { return None };
    let tested = match (constant(func, a), constant(func, b)) {
        (None, Some(c)) => (a, c),
        (Some(c), None) => (b, c),
        _ => return None,
    };
    // Either side can be the one working the operation out. When it is the side the test does not
    // hold on, its value is right on both edges. When it is the side the test holds on, the
    // operation gives the other side's value there, so the other side's value is right on both.
    // The side passed on is the one the test does not hold on either way.
    let other = 1 - equal;
    let settles = reduces(func, tested, pair[other], pair[equal])
        || reduces(func, tested, pair[equal], pair[other]);
    settles.then_some(other)
}

/// Whether `worked` is `kept` on the edge where `tested` is the constant it was compared with.
fn reduces(func: &Func, tested: (Value, (Imm, Type)), worked: Value, kept: Value) -> bool {
    let (tested, (imm, ty)) = tested;
    let Def::Result { inst: op, .. } = func[worked].def else { return false };
    let &[left, right] = &func[func[op].args] else { return false };
    if !func[worked].ty.is_int() {
        return false;
    }
    // What an operand is on that edge, if it is the tested value, itself or widened.
    let at = |operand: Value| -> Option<i128> {
        if operand == tested {
            return Some(imm.signed(ty));
        }
        let Def::Result { inst, .. } = func[operand].def else { return None };
        if func[func[inst].args].first() != Some(&tested) {
            return None;
        }
        match func[inst].opcode {
            Opcode::SExt => Some(imm.signed(ty)),
            Opcode::ZExt => i128::try_from(imm.unsigned()).ok(),
            _ => None,
        }
    };
    // An element that leaves the other operand as it was, which has to be the value kept.
    let neutral = |x: Value, element: i128, y: Value| at(x) == Some(element) && y == kept;
    // An element that decides the answer alone, which has to be the number kept.
    let absorbing = |x: Value, element: i128, gives: i128| {
        at(x) == Some(element)
            && constant(func, kept).is_some_and(|(number, ty)| number.signed(ty) == gives)
    };
    let either = |test: &dyn Fn(Value, Value) -> bool| test(left, right) || test(right, left);
    match func[op].opcode {
        Opcode::Add | Opcode::Xor => either(&|x, y| neutral(x, 0, y)),
        Opcode::Or => either(&|x, y| neutral(x, 0, y) || absorbing(x, -1, -1)),
        Opcode::Sub => neutral(right, 0, left),
        Opcode::Mul => either(&|x, y| neutral(x, 1, y) || absorbing(x, 0, 0)),
        Opcode::And => either(&|x, y| neutral(x, -1, y) || absorbing(x, 0, 0)),
        Opcode::Shl | Opcode::LShr => neutral(right, 0, left) || absorbing(left, 0, 0),
        Opcode::AShr => neutral(right, 0, left) || absorbing(left, 0, 0) || absorbing(left, -1, -1),
        _ => false,
    }
}

/// Whether this join parameter is one the oracle could have something to say about.
///
/// Two sides that agree need nothing. Two constants that are not the same number are not the same
/// number on any edge, and asking is a query whose answer is already in hand.
fn worth_asking(func: &Func, shape: &Diamond, index: usize) -> bool {
    let pair = [shape.args[0][index], shape.args[1][index]];
    if agree(func, pair[0], pair[1]) {
        return false;
    }
    constant(func, pair[0]).is_none() || constant(func, pair[1]).is_none()
}

/// Which of the two store refusals this diamond is, once it is known to be one of them.
///
/// The two are worth separating because they say different things about what would fix them. One
/// path storing is section 22.6's predicate, which is a proof nothing here can do. Both paths
/// storing and not matching is usually two arms that worked the same address out separately, which
/// is `a[i] = ...` on both sides, and what fixes that is document 16's value numbering making the
/// two into one value rather than anything about memory.
fn mismatch(func: &Func, shape: &Diamond) -> &'static str {
    let [Some(then), Some(other)] = shape.arms else { return STORE_ON_ONE_PATH };
    match (stored_in(func, then), stored_in(func, other)) {
        (Some(_), Some(_)) => STORES_DO_NOT_MATCH,
        _ => STORE_ON_ONE_PATH,
    }
}

/// The store this diamond can move below the branch, if it has one.
///
/// Two stores to the same place are the half of the transformation that needs no proof. One store
/// is the half that does, and [`alone`] is where it is asked for.
fn storing(func: &Func, shape: &Diamond) -> Option<Stored> {
    let found = shape.arms.map(|arm| arm.and_then(|block| stored_in(func, block)));
    match found {
        [Some(then), Some(other)] => both(func, [then, other]),
        [Some(one), None] => alone(func, shape, one, 0),
        [None, Some(one)] => alone(func, shape, one, 1),
        [None, None] => None,
    }
}

/// The one store two stores to the same place become.
fn both(func: &Func, insts: [Inst; 2]) -> Option<Stored> {
    let data = [func[insts[0]], func[insts[1]]];
    // The flags are what the optimizer is licensed to assume about the access, so one store written
    // under the union of two sets of assumptions would be claiming on one path something only the
    // other path established. `volatile` is refused outright rather than by disagreeing, because
    // section 22.6 says never and because the reason is not the flag matching: both how many
    // accesses there are and what order they come in are observable, and a value that arrives
    // through a select is a different program from one that arrives through a branch.
    if data[0].flags != data[1].flags || data[0].flags.contains(Flags::VOLATILE) {
        return None;
    }
    let (Extra::Mem(one), Extra::Mem(two)) = (data[0].extra, data[1].extra) else { return None };
    // The alignment, the size, the aliasing node and the `restrict` scope, all of which the one
    // store carries forward, so two that disagree about any of them have no single answer to carry.
    if func[one] != func[two] || func[one].order != MemOrder::NotAtomic {
        return None;
    }
    // A store names what it writes and then where, which is the order the builder takes them in.
    let &[then, addr] = func[data[0].args].first_chunk::<2>()?;
    let &[other, addr_two] = func[data[1].args].first_chunk::<2>()?;
    // The same value for the address, which is stronger than the same address and is what can be
    // checked without an alias analysis. It also settles where that value comes from: neither arm
    // dominates the other, so a value both of them name is one worked out at or above the head, and
    // the one store is written in the head where it is available.
    if addr != addr_two || func[then].ty != func[other].ty {
        return None;
    }
    if !agree(func, then, other) && !selectable(func[then].ty) {
        return None;
    }
    let ty = func[then].ty;
    Some(Stored {
        insts: insts.to_vec(),
        values: [Some(then), Some(other)],
        addr,
        data: data[0],
        ty,
    })
}

/// The store only one side makes, when the module comment's proof for it is there.
///
/// The side is the one that stores. The other side stores too once this is done, and what it
/// stores is what it would have found had it looked.
fn alone(func: &Func, shape: &Diamond, inst: Inst, side: usize) -> Option<Stored> {
    let data = func[inst];
    if data.flags.contains(Flags::VOLATILE) {
        return None;
    }
    let Extra::Mem(mem) = data.extra else { return None };
    if func[mem].order != MemOrder::NotAtomic {
        return None;
    }
    let &[value, addr] = func[data.args].first_chunk::<2>()?;
    let ty = func[value].ty;
    if !selectable(ty) || !touched(func, shape.head, addr, ty) {
        return None;
    }
    let (Origin::Local(slot), _) = alias::origin(func, addr) else { return None };
    let gives_back = func
        .blocks()
        .flat_map(|block| func.insts(block))
        .any(|one| func[one].opcode == Opcode::StackRestore);
    if gives_back || Escapes::of(func).escaped(slot) {
        return None;
    }
    let mut values = [None, None];
    values[side] = Some(value);
    Some(Stored { insts: vec![inst], values, addr, data, ty })
}

/// Whether the head reads or writes this address at this type, with nothing after that access that
/// could have given the memory back.
///
/// Walked from the branch upward, and the walk stops at the first thing with an effect that is not
/// a load or a store, because a call is what frees memory and everything above it proves nothing
/// about the memory below it.
fn touched(func: &Func, head: Block, addr: Value, ty: Type) -> bool {
    let insts: Vec<Inst> = func.insts(head).collect();
    for &inst in insts.iter().rev() {
        let data = func[inst];
        if func.is_terminator(inst) || !data.opcode.has_effects() {
            continue;
        }
        let access = match data.opcode {
            Opcode::Load => func[data.args].first().copied().zip(data.first_result),
            Opcode::Store => func[data.args].first_chunk::<2>().map(|&[value, at]| (at, value)),
            _ => return false,
        };
        let Some((at, value)) = access else { return false };
        if plain(func, data) && func[value].ty == ty && same(func, at, addr, 0) {
            return true;
        }
    }
    false
}

/// Whether this load in an arm is one the head has already shown can be made on both paths.
fn readable(func: &Func, head: Block, inst: Inst) -> bool {
    let data = func[inst];
    if data.opcode != Opcode::Load || !plain(func, data) {
        return false;
    }
    let (Some(&addr), Some(value)) = (func[data.args].first(), data.first_result) else {
        return false;
    };
    touched(func, head, addr, func[value].ty)
}

/// Whether this access is neither `volatile` nor atomic.
fn plain(func: &Func, data: InstData) -> bool {
    let Extra::Mem(mem) = data.extra else { return false };
    !data.flags.contains(Flags::VOLATILE) && func[mem].order == MemOrder::NotAtomic
}

/// How deep [`same`] follows two chains of operations before it gives up on them.
///
/// A subscript is a sign extension, a shift and an add, and a field of an element of a local
/// array is one more add, so this is that with room to spare.
const SAME_DEPTH: usize = 6;

/// Whether two values are worked out the same way from the same things.
///
/// The operations are the pure ones an address is made of, compared on everything
/// `number` compares them on, so that two values this calls the same are two values that pass
/// would make one.
fn same(func: &Func, one: Value, two: Value, depth: usize) -> bool {
    if agree(func, one, two) {
        return true;
    }
    if depth == SAME_DEPTH || func[one].ty != func[two].ty {
        return false;
    }
    let (Def::Result { inst: left, .. }, Def::Result { inst: right, .. }) =
        (func[one].def, func[two].def)
    else {
        return false;
    };
    let (left, right) = (func[left], func[right]);
    if left.opcode != right.opcode || left.flags != right.flags || left.extra != right.extra {
        return false;
    }
    if left.results != 1 || right.results != 1 || !addressing(left.opcode) {
        return false;
    }
    let (left, right) = (&func[left.args], &func[right.args]);
    left.len() == right.len()
        && left.iter().zip(right).all(|(&one, &two)| same(func, one, two, depth + 1))
}

/// Whether this is one of the operations [`same`] follows.
fn addressing(opcode: Opcode) -> bool {
    matches!(
        opcode,
        Opcode::PtrAdd
            | Opcode::Add
            | Opcode::Sub
            | Opcode::Mul
            | Opcode::Shl
            | Opcode::And
            | Opcode::Or
            | Opcode::Xor
            | Opcode::SExt
            | Opcode::ZExt
            | Opcode::Trunc
            | Opcode::Bitcast
            | Opcode::GlobalAddr
    )
}

/// The one store this arm makes, if it makes exactly one and does nothing else that has to happen.
///
/// Exactly one, because two stores below one select is two selects and a shape nothing has asked
/// for. Nothing else with an effect, because everything else with an effect is still refused and
/// this is the check that says so: an arm that stores and also calls something has a call that only
/// happens on the path it is on, and no amount of agreement about the store changes that.
fn stored_in(func: &Func, arm: Block) -> Option<Inst> {
    let mut store = None;
    for inst in func.insts(arm) {
        if func.is_terminator(inst) || !func[inst].opcode.has_effects() {
            continue;
        }
        // A load ahead of the store is judged on its own by the refusals. One after it is not
        // allowed, because the one store is written below everything the arms did, and a load that
        // came after it would then read memory from before it.
        if func[inst].opcode == Opcode::Load && store.is_none() {
            continue;
        }
        if func[inst].opcode != Opcode::Store || store.is_some() {
            return None;
        }
        store = Some(inst);
    }
    store
}

/// One join argument both arms worked out the same way, and the one operand they disagreed about.
///
/// Section 22.2's third transformation. `cond ? f(a) : f(b)` is `f(cond ? a : b)`, which is one
/// operation where there were two and one select either way, and it is structural rather than a
/// rewrite rule because the two `f`s are in different blocks and no pattern spans blocks.
struct Factored {
    /// The instruction each side wrote, which goes when the one copy below replaces both.
    insts: [Inst; 2],
    /// What each side handed that instruction, taken from the side taken when the condition holds.
    operands: Vec<Value>,
    /// The one position the two sides put different values in, and what each of them put there.
    ///
    /// `None` when they agree in every position, which is both arms computing the same thing from
    /// the same operands. Then one copy serves both and there is no select at all.
    differ: Option<(usize, [Value; 2])>,
    /// The same again one level down, when the two values the sides differ in were themselves
    /// worked out the same way in each arm.
    ///
    /// Then what goes in the differing position is that operation written once, and the select
    /// moves down to where the chain stops agreeing. `(long long)(i * 2)` against
    /// `(long long)(i + 1)` under an add both arms share is an add of a widening of a select,
    /// rather than an add of a select of two widenings that each arm would still be paying for.
    below: Option<Box<Factored>>,
    /// The instruction to write once, whose operand list is replaced by the one above.
    data: InstData,
    /// What it produces.
    ty: Type,
}

impl Factored {
    /// This level and every level under it, from the one the join reads down.
    fn levels(&self) -> impl Iterator<Item = &Factored> {
        std::iter::successors(Some(self), |one| one.below.as_deref())
    }
}

/// What can be factored out of each of the join's parameters, in the order the join takes them.
///
/// A triangle factors nothing. One of its sides is the join itself, so there is no block on that
/// side holding an operation to pair the other one with, and what that side hands the join is a
/// value worked out before the branch.
fn factoring(func: &Func, shape: &Diamond, implied: &[Option<usize>]) -> Vec<Option<Factored>> {
    let count = shape.args[0].len();
    let [Some(then), Some(other)] = shape.arms else {
        return (0..count).map(|_| None).collect();
    };
    (0..count)
        .map(|index| {
            // A value the condition settled is passed on whole, so there is no operation to write
            // once below and the two that worked the two values out are left for dead code.
            if implied.get(index).copied().flatten().is_some() {
                return None;
            }
            factored(func, shape, [then, other], index)
        })
        .collect()
}

/// Whether this join argument is the same operation on both sides, and what to write instead.
fn factored(func: &Func, shape: &Diamond, arms: [Block; 2], index: usize) -> Option<Factored> {
    factored_at(func, arms, [shape.args[0][index], shape.args[1][index]], 0)
}

/// Whether these two values are the same operation, one in each arm, and what to write instead.
///
/// `depth` is how many levels above this one were already factored, which is what keeps a long
/// chain from being walked all the way down. gcc's `factor_out_conditional_operation` at
/// `gcc/tree-ssa-phiopt.cc:310` runs to a fixed point instead, and the bound is here for the same
/// reason the arm scan has one.
fn factored_at(func: &Func, arms: [Block; 2], sides: [Value; 2], depth: u32) -> Option<Factored> {
    // Two sides that agree need no operation written at all, and the caller passes the value on.
    if agree(func, sides[0], sides[1]) {
        return None;
    }
    let insts = [written_in(func, arms[0], sides[0])?, written_in(func, arms[1], sides[1])?];
    let data = [func[insts[0]], func[insts[1]]];
    // Everything about the two has to match except the operands. The flags are what the optimizer
    // is licensed to assume, so writing one copy under the union of two sets of assumptions would
    // be claiming on one path something only the other path established. The extra is whatever the
    // instruction carries that is not an operand, which for a comparison is the predicate, and two
    // predicates that differ are two different questions.
    if data[0].opcode != data[1].opcode || data[0].flags != data[1].flags {
        return None;
    }
    if data[0].extra != data[1].extra || func[sides[0]].ty != func[sides[1]].ty {
        return None;
    }
    let operands = [func[data[0].args].to_vec(), func[data[1].args].to_vec()];
    if operands[0].len() != operands[1].len() {
        return None;
    }
    // Below the first level only an operation of one operand, which is a conversion or something
    // like it, and what gcc's loop takes too. One of two operands trades a select of the two
    // answers for a select of two operands and the operation, and when those operands are what
    // unrolling makes into constants the select of the answers was a select of two constants.
    if depth > 0 && operands[0].len() != 1 {
        return None;
    }
    // A conversion of a constant in each arm is two constants once it folds, and a select of two
    // constants is what the level above already writes. Factoring it would put the conversion
    // after the select, which is one more instruction for nothing.
    if depth > 0 && operands.iter().all(|side| constant(func, side[0]).is_some()) {
        return None;
    }
    let mut apart =
        operands[0].iter().zip(&operands[1]).enumerate().filter(|(_, (one, two))| one != two);
    let mut below = None;
    let differ = match (apart.next(), apart.next()) {
        // Two positions apart would need two selects, and two selects and one operation is what
        // one select and two operations already cost. There is nothing to win, so it is left.
        (_, Some(_)) => return None,
        (Some((at, (&one, &two))), None) => {
            if func[one].ty != func[two].ty {
                return None;
            }
            // A level that factors below needs no select at this one, so the width a select can
            // choose at is asked about only where the chain stops.
            let deeper = depth + 1 < heuristics::PHIOPT_FACTOR_DEPTH;
            below = deeper.then(|| factored_at(func, arms, [one, two], depth + 1)).flatten();
            if below.is_none() && !selectable(func[one].ty) {
                return None;
            }
            Some((at, [one, two]))
        }
        (None, None) => None,
    };
    let ty = func[sides[0]].ty;
    let below = below.map(Box::new);
    Some(Factored { insts, operands: operands[0].clone(), differ, below, data: data[0], ty })
}

/// The instruction in this arm that works out this value, if the arm is where it comes from and the
/// only thing that reads it is the jump to the join.
///
/// Both halves are needed. The arm has to be where it is worked out, because an operation to factor
/// out is one this pass is about to stop writing and it can only stop writing what it can find.
/// Nothing else can read it, because the one copy that replaces the two is written after the arms
/// have gone and a second reader in the arm would have been left pointing at an instruction that is
/// no longer in any block.
fn written_in(func: &Func, arm: Block, value: Value) -> Option<Inst> {
    let inst = func
        .insts(arm)
        .find(|&inst| func[inst].results == 1 && func[inst].first_result == Some(value))?;
    let mut seen = 0;
    for inst in func.insts(arm) {
        seen += func[func[inst].args].iter().filter(|&&arg| arg == value).count();
        for call in func.successors(inst) {
            seen += func[call.args].iter().filter(|&&arg| arg == value).count();
        }
    }
    (seen == 1).then_some(inst)
}

/// Whether a value of this type is one a `select` can choose.
///
/// The four widths `crates/rucc-ir/src/term.rs` names a `select` at. A wider integer, a float, a
/// pointer, a bit or a vector has no head, so a `select` of one would be a term the rule set has
/// no lowering for and the failure would be at instruction selection rather than here.
///
/// This function is also the whole answer to whether a `select` at any of those types can exist at
/// all, since this pass is the only one that turns a choice into one and every other writer of one
/// in the tree is choosing between integers it built itself. `crates/rucc-codegen/src/quad.rs`
/// leans on that where it says a conditional expression over two `_Float128`s stays a branch.
fn selectable(ty: Type) -> bool {
    ty.is_scalar() && ty.is_int() && matches!(ty.bits(), 8 | 16 | 32 | 64)
}

/// How much work an arm does, not counting the jump that is about to go.
pub(crate) fn length(func: &Func, block: Block) -> u32 {
    let count = func.insts(block).filter(|&inst| !func.is_terminator(inst)).count();
    u32::try_from(count).unwrap_or(u32::MAX)
}

/// How much work an arm does that the head is not already doing, not counting the jump.
///
/// An arm longer than this bothers to look through is counted whole, since it is refused as too
/// long either way and the question is a walk over the head for each of its instructions.
///
/// An integer constant is not counted. On the machine it is an immediate in the instruction that
/// reads it, or at worst a move nothing waits on, so it is not work the other path would be paying
/// for. Counting it made the arm of `acc = c ? acc + 1 : acc` two instructions when `acc` is an
/// `int` and three when it is anything else, since the front end writes the `1` as an `int` and
/// converts it, and that one extra constant was the difference between a select and a branch.
fn work(func: &Func, head: Block, arm: Block) -> u32 {
    let whole = length(func, arm);
    if whole > heuristics::PHIOPT_ARM_SCAN_INSTRUCTIONS {
        return whole;
    }
    let done: Vec<Value> = func
        .insts(head)
        .filter(|&inst| func[inst].results == 1 && !func[inst].opcode.has_effects())
        .filter_map(|inst| func[inst].first_result)
        .collect();
    let repeated = |inst: Inst| {
        let data = func[inst];
        if data.results != 1 || data.opcode.has_effects() {
            return false;
        }
        let Some(value) = data.first_result else { return false };
        done.iter().any(|&there| same(func, there, value, 0))
    };
    let free = |inst: Inst| func[inst].opcode == Opcode::IConst;
    let count = func
        .insts(arm)
        .filter(|&inst| !func.is_terminator(inst) && !repeated(inst) && !free(inst))
        .count();
    u32::try_from(count).unwrap_or(u32::MAX)
}

/// Whether the estimate leaves enough doubt about this branch to be worth removing it.
pub(crate) fn unpredictable(taken: Probability) -> bool {
    let margin = heuristics::PHIOPT_UNPREDICTABLE_MARGIN_PERCENT * (Probability::SCALE / 100);
    taken.parts() >= margin && taken.parts() <= Probability::SCALE - margin
}

/// Moves the arms into the head, builds the selects and takes the branch out.
///
/// The order matters and is the reason this is one function. The branch goes first, so that what
/// the arms were doing can be appended to the head without anything having to be threaded around a
/// terminator. The selects are built after that work has moved, since they read what it produced.
/// The jump goes last because it is the terminator.
fn convert(
    func: &mut Func,
    shape: &Diamond,
    plan: &[Option<Factored>],
    store: Option<&Stored>,
    implied: &[Option<usize>],
) {
    let term = func.terminator(shape.head).expect("the head of a diamond ends in its branch");
    let span = func.span(term);
    func.remove_inst(term);
    let mut dropped: Vec<Inst> =
        plan.iter().flatten().flat_map(Factored::levels).flat_map(|one| one.insts).collect();
    dropped.extend(store.iter().flat_map(|one| one.insts.iter().copied()));
    for &arm in shape.arms.iter().flatten() {
        for inst in func.insts(arm).collect::<Vec<Inst>>() {
            if func.is_terminator(inst) {
                continue;
            }
            func.remove_inst(inst);
            // A factored operation is not moved, it is replaced. One copy of it is written below,
            // after the selects it reads, and these two are what that copy is instead of.
            if !dropped.contains(&inst) {
                func.append_inst(shape.head, inst);
            }
        }
    }
    let mut build = Builder::new(func, shape.head).at(span);
    let mut args = Vec::with_capacity(shape.args[0].len());
    for (index, (&then, &other)) in shape.args[0].iter().zip(&shape.args[1]).enumerate() {
        // A value the condition settled, passed on as it is. The side named is the one whose value
        // is right on both edges, which is the side the two were not shown to be equal on.
        if let Some(side) = implied.get(index).copied().flatten() {
            args.push(shape.args[side][index]);
            continue;
        }
        if let Some(one) = &plan[index] {
            args.push(write_factored(&mut build, shape.cond, one));
            continue;
        }
        // The condition holds on the first side, which is the side `select` takes when the bit is
        // one, so the order the branch named its targets in is the order the arguments go in.
        let same = agree(build.func(), then, other);
        args.push(if same { then } else { build.select(shape.cond, then, other) });
    }
    // After everything the arms were doing has moved, because the value being stored is often one
    // of the things they were working out, and before the jump because the jump is the terminator.
    if let Some(one) = store {
        // The side that made no store writes back what it finds, and it finds it here, after
        // everything the arms did and before the one store, which is where the side that stored
        // had not yet done it.
        let old = one.values.contains(&None).then(|| {
            let Extra::Mem(mem) = one.data.extra else { unreachable!("a store says what it is") };
            // Everything the store says about the access is true of the read too, except the
            // padding it owns: only a store records any, and a read carrying the number is one the
            // verifier refuses.
            let info = MemInfo { owns: 0, ..build.func()[mem] };
            build.load(one.ty, one.addr, info, one.data.flags)
        });
        let [then, other] = one
            .values
            .map(|value| value.or(old).expect("a side that stored nothing reads what is there"));
        let same = agree(build.func(), then, other);
        let what = if same { then } else { build.select(shape.cond, then, other) };
        let list = build.func().push_values(&[what, one.addr]);
        build.inst(InstData { args: list, ..one.data }, &[]);
    }
    build.jump(shape.join, &args);
    // Nothing arrives at the arms now, and section 6.5 makes taking an unreachable block out the
    // standing obligation of whichever pass stranded it rather than something the next pass tidies
    // up. The verifier holds every pass to that.
    for &arm in shape.arms.iter().flatten() {
        func.remove_block(arm);
    }
}

/// Writes one copy of a factored chain, from the select at the bottom up to the level the join
/// reads, and answers what that level produces.
fn write_factored(build: &mut Builder<'_>, cond: Value, one: &Factored) -> Value {
    let mut operands = one.operands.clone();
    if let Some((at, sides)) = one.differ {
        operands[at] = match &one.below {
            Some(below) => write_factored(build, cond, below),
            None => build.select(cond, sides[0], sides[1]),
        };
    }
    let list = build.func().push_values(&operands);
    build.value(InstData { args: list, ..one.data }, one.ty)
}

#[cfg(test)]
mod tests {
    use rucc_base::Interner;
    use rucc_ir::{
        Block, Builder, Extra, Flags, Float, Func, InstData, IntPred, MemInfo, MemOrder, Opcode,
        Restrict, Signature, Type, Value,
    };

    use super::PhiOpt;
    use crate::profile::{Probability, Quality};
    use crate::stats::Kind;
    use crate::{Fuel, Pass, Stats};

    /// Runs the pass with as much fuel as it wants.
    fn phiopt(func: &mut Func) -> Stats {
        PhiOpt.run(func, &mut crate::machine::fixtures::analyses(), &mut Fuel::unlimited())
    }

    /// The blocks the function still has, by number.
    fn blocks(func: &Func) -> Vec<usize> {
        func.blocks().map(Block::index).collect()
    }

    /// Where a block's terminator goes, as block numbers.
    fn goes_to(func: &Func, block: usize) -> Vec<usize> {
        let block = Block::from_usize(block);
        let term = func.terminator(block).expect("every block here has one");
        func.successors(term).map(|call| call.block.index()).collect()
    }

    /// The opcodes a block holds, in order.
    fn opcodes(func: &Func, block: usize) -> Vec<Opcode> {
        let block = Block::from_usize(block);
        func.insts(block).map(|inst| func[inst].opcode).collect()
    }

    /// What a block's terminator carries on its first edge.
    fn carries(func: &Func, block: usize) -> Vec<Value> {
        let block = Block::from_usize(block);
        let term = func.terminator(block).expect("every block here has one");
        let call = func.successors(term).next().expect("a terminator here has an edge");
        func[call.args].to_vec()
    }

    /// Four aligned bytes, ordinary, with nothing known about aliasing.
    fn plain() -> MemInfo {
        MemInfo {
            size: 4,
            align: 4,
            order: MemOrder::NotAtomic,
            tbaa: None,
            owns: 0,
            restrict: Restrict::NONE,
        }
    }

    /// A store, which is the instruction used here whenever something has to happen.
    fn store_something(build: &mut Builder<'_>) {
        let what = build.iconst(Type::int(32), 7);
        let address = build.iconst(Type::int(64), 16);
        let address = build.unary(Opcode::IntToPtr, address, Type::PTR);
        build.store(what, address, plain(), Flags::NONE);
    }

    /// `if (x < 0) *p = a; else *p = b;`, with both stores told the same thing about the access.
    ///
    /// The address is a function parameter, so it is one value both arms name, and the two values
    /// written are the other two parameters. Block 0 is the head, blocks 1 and 2 are the arms and
    /// block 3 is the join, which takes nothing and returns.
    fn both_arms_store(info: MemInfo, flags: [Flags; 2], addresses: bool) -> Func {
        let mut names = Interner::new();
        let ints = [Type::PTR, Type::int(32), Type::int(32), Type::PTR];
        let signature = Signature::new().with_params(&ints);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let address = func.append_param(head, Type::PTR);
        let written =
            [func.append_param(head, Type::int(32)), func.append_param(head, Type::int(32))];
        let elsewhere = func.append_param(head, Type::PTR);
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, written[0], zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for (index, arm) in arms.iter().enumerate() {
            let mut build = Builder::new(&mut func, *arm);
            let where_to = if addresses && index == 1 { elsewhere } else { address };
            build.store(written[index], where_to, info, flags[index]);
            build.jump(join, &[]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[]);
        func
    }

    /// `x < y ? a : b`, as a diamond whose two arms are empty.
    ///
    /// Block 0 is the head and takes the two values it compares as function parameters, blocks 1
    /// and 2 are the arms and carry one of two constants, and block 3 is the join and returns what
    /// it was given.
    fn empty_arms() -> Func {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32), Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, Type::int(32));
        let right = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for (arm, value) in arms.iter().zip([1, 2]) {
            let mut build = Builder::new(&mut func, *arm);
            let it = build.iconst(Type::int(32), value);
            build.jump(join, &[it]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);
        func
    }

    #[test]
    fn a_branch_that_is_already_decided_is_left_for_simplify_cfg() {
        // What `if (1)` looks like by the time it gets here. Converting would build a select on a
        // constant and keep the arm that cannot run, and the pass that would fold it does not
        // exist, so the answer is to leave the branch alone and let the arm be deleted whole.
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"), Signature::new());
        let head = func.create_block();
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        // What `if (1)` reaches this pass as. Not a constant, a comparison of two constants, since
        // `fold` will not turn an `icmp` into an `i1` that nothing lowers.
        let one = build.iconst(Type::int(32), 1);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Ne, one, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for (arm, value) in arms.iter().zip([1, 2]) {
            let mut build = Builder::new(&mut func, *arm);
            let it = build.iconst(Type::int(32), value);
            build.jump(join, &[it]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Missed, super::CONDITION_IS_DECIDED), 1);
        assert_eq!(blocks(&func), vec![0, 1, 2, 3]);
    }

    #[test]
    fn a_diamond_whose_arms_are_empty_becomes_a_select() {
        let mut func = empty_arms();
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        // The two constants moved up with the arms, and the select is what the branch was.
        assert_eq!(
            opcodes(&func, 0),
            vec![Opcode::ICmp, Opcode::IConst, Opcode::IConst, Opcode::Select, Opcode::Jump]
        );
        assert_eq!(goes_to(&func, 0), vec![3]);
        assert_eq!(blocks(&func), vec![0, 3]);
    }

    #[test]
    fn the_side_the_condition_holds_on_is_the_side_the_select_takes_first() {
        let mut func = empty_arms();
        phiopt(&mut func);
        let select = func
            .insts(Block::from_usize(0))
            .find(|&inst| func[inst].opcode == Opcode::Select)
            .expect("the select the pass just built");
        let args = func[func[select].args].to_vec();
        let one = crate::fold::constant(&func, args[1]).expect("the true arm carried a constant");
        let two = crate::fold::constant(&func, args[2]).expect("the false arm carried a constant");
        assert_eq!(one.0.unsigned(), 1, "the arm the branch named first");
        assert_eq!(two.0.unsigned(), 2, "the arm the branch named second");
    }

    /// A triangle: one side goes straight to the join carrying what it already had.
    #[test]
    fn a_triangle_whose_empty_side_goes_straight_to_the_join_is_converted() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let arm = func.create_block();
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arm, &[], join, &[outside]);
        let mut build = Builder::new(&mut func, arm);
        let it = build.iconst(Type::int(32), 0);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert_eq!(blocks(&func), vec![0, 2]);
        assert_eq!(goes_to(&func, 0), vec![2]);
        assert_eq!(opcodes(&func, 0).last(), Some(&Opcode::Jump));
    }

    #[test]
    fn a_parameter_both_sides_agree_about_needs_no_select() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for arm in arms {
            let mut build = Builder::new(&mut func, arm);
            build.jump(join, &[outside]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert!(!opcodes(&func, 0).contains(&Opcode::Select), "both sides carried the same value");
        assert_eq!(carries(&func, 0), vec![outside]);
    }

    #[test]
    fn two_sides_carrying_the_same_number_need_no_select_either() {
        // `x ? 7 : 7`, which the corpus has eight of. The two sevens are two values, because
        // nothing has hash consed them into one, so asking only whether the values are equal
        // builds a select between two sevens and pays a compare and a conditional move for it.
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for arm in arms {
            let mut build = Builder::new(&mut func, arm);
            let seven = build.iconst(Type::int(32), 7);
            build.jump(join, &[seven]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert!(!opcodes(&func, 0).contains(&Opcode::Select), "both sides carried a seven");
    }

    #[test]
    fn two_sides_carrying_different_numbers_still_get_a_select() {
        let mut func = empty_arms();
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert!(opcodes(&func, 0).contains(&Opcode::Select), "one and two are not the same number");
    }

    /// `x = (a == b) ? b : a`, as the diamond it arrives here as.
    ///
    /// Block 0 is the head and takes the two values, blocks 1 and 2 are the arms and each carries
    /// one of them to block 3, which returns what it was given. The comparison's predicate and the
    /// type of the two values are what the tests below vary.
    fn condition_settles_it(pred: IntPred, ty: Type) -> Func {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[ty, ty]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, ty);
        let right = func.append_param(head, ty);
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, ty);

        let mut build = Builder::new(&mut func, head);
        let test = build.icmp(pred, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        // The side taken when the condition holds carries the right hand value, the other side
        // carries the left, which is what makes the two the same number on one edge and not the
        // other. Which side that is follows the predicate.
        for (arm, value) in arms.iter().zip([right, left]) {
            let mut build = Builder::new(&mut func, *arm);
            build.jump(join, &[value]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);
        func
    }

    #[test]
    fn a_value_the_condition_says_is_the_other_one_needs_no_select() {
        let mut func = condition_settles_it(IntPred::Eq, Type::int(32));
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::VALUE_IMPLIED), 1);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert_eq!(opcodes(&func, 0), vec![Opcode::ICmp, Opcode::Jump]);
        // The value passed on is the one carried by the side the two were not shown equal on.
        let params = func[Block::from_usize(0)].params.to_vec();
        assert_eq!(carries(&func, 0), vec![params[0]]);
        assert_eq!(blocks(&func), vec![0, 3]);
    }

    /// The same with the branch the other way round, where the equal side is the one not taken.
    #[test]
    fn an_inequality_settles_it_from_the_other_side() {
        let mut func = condition_settles_it(IntPred::Ne, Type::int(32));
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::VALUE_IMPLIED), 1);
        let params = func[Block::from_usize(0)].params.to_vec();
        assert_eq!(carries(&func, 0), vec![params[1]]);
    }

    /// A pointer has no `select`, and a value nothing has to choose between does not need one.
    #[test]
    fn a_value_of_a_type_with_no_select_is_still_settled_by_the_condition() {
        let mut func = condition_settles_it(IntPred::Eq, Type::PTR);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Missed, super::NO_SELECT_AT_THAT_WIDTH), 0);
        assert_eq!(stats.count(Kind::Optimized, super::VALUE_IMPLIED), 1);
        assert_eq!(opcodes(&func, 0), vec![Opcode::ICmp, Opcode::Jump]);
    }

    /// A branch on anything but an equality is not asked about, and the select is written as usual.
    #[test]
    fn a_branch_that_is_not_an_equality_gets_its_select() {
        let mut func = condition_settles_it(IntPred::Slt, Type::int(32));
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::VALUE_IMPLIED), 0);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert!(opcodes(&func, 0).contains(&Opcode::Select));
    }

    /// How the operation in [`element_diamond`] is written.
    #[derive(Clone, Copy)]
    enum Order {
        /// `y op x`, with the tested value on the right.
        TestedRight,
        /// `x op y`, with the tested value on the left.
        TestedLeft,
    }

    /// What [`element_diamond`] varies besides the comparison and the operation.
    #[derive(Clone, Copy, PartialEq, Eq)]
    enum Shape {
        /// Everything 64 bits wide.
        Plain,
        /// `x` 32 bits wide and sign extended before the operation reads it.
        Widened,
        /// The operation on the side the test holds on, and the kept value on the other.
        Swapped,
    }

    /// `x == c ? kept : y op x`, as the diamond it arrives here as, or `!=` with the arms swapped.
    ///
    /// Block 0 takes `x` and `y` and tests `x` against `c`. The side on which the test says `x` is
    /// `c` carries `kept`, which is `y` when it is `None` and that number when it is not, and the
    /// other side works out the operation and carries it, unless `shape` says otherwise.
    fn element_diamond(
        pred: IntPred,
        c: i128,
        opcode: Opcode,
        order: Order,
        kept: Option<i128>,
        shape: Shape,
    ) -> Func {
        let narrow = if shape == Shape::Widened { Type::int(32) } else { Type::int(64) };
        let ty = Type::int(64);
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[narrow, ty]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let x = func.append_param(head, narrow);
        let y = func.append_param(head, ty);
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, ty);

        let mut build = Builder::new(&mut func, head);
        let c = build.iconst(narrow, c);
        let test = build.icmp(pred, x, c);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        let mut equal = usize::from(pred == IntPred::Ne);
        if shape == Shape::Swapped {
            equal = 1 - equal;
        }
        let mut build = Builder::new(&mut func, arms[equal]);
        let kept = kept.map_or(y, |number| build.iconst(ty, number));
        build.jump(join, &[kept]);
        let mut build = Builder::new(&mut func, arms[1 - equal]);
        let x = if shape == Shape::Widened { build.unary(Opcode::SExt, x, ty) } else { x };
        let worked = match order {
            Order::TestedRight => build.binary(opcode, y, x, Flags::NONE),
            Order::TestedLeft => build.binary(opcode, x, y, Flags::NONE),
        };
        build.jump(join, &[worked]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);
        func
    }

    /// Whether the diamond went without a select because the condition settled its value.
    fn settled(pred: IntPred, c: i128, opcode: Opcode, order: Order, kept: Option<i128>) -> bool {
        let mut func = element_diamond(pred, c, opcode, order, kept, Shape::Plain);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        let implied = stats.count(Kind::Optimized, super::VALUE_IMPLIED) == 1;
        assert_eq!(implied, !opcodes(&func, 0).contains(&Opcode::Select));
        implied
    }

    /// `x == 0 ? y : y + x` is `y + x`, and the same for every operation zero leaves alone, with
    /// the tested value on either side of the ones where the order does not matter.
    #[test]
    fn an_operation_the_tested_constant_leaves_alone_needs_no_select() {
        use Order::{TestedLeft, TestedRight};
        for opcode in [Opcode::Add, Opcode::Or, Opcode::Xor] {
            assert!(settled(IntPred::Eq, 0, opcode, TestedRight, None), "{opcode:?}");
            assert!(settled(IntPred::Eq, 0, opcode, TestedLeft, None), "{opcode:?}");
        }
        for opcode in [Opcode::Sub, Opcode::Shl, Opcode::LShr, Opcode::AShr] {
            assert!(settled(IntPred::Eq, 0, opcode, TestedRight, None), "{opcode:?}");
        }
        assert!(settled(IntPred::Eq, 1, Opcode::Mul, TestedRight, None));
        assert!(settled(IntPred::Eq, -1, Opcode::And, TestedLeft, None));
        assert!(settled(IntPred::Ne, 0, Opcode::Add, TestedRight, None));
    }

    /// `x != 0 ? y * x : 0` is `y * x`, and the same for every operation the tested constant
    /// swallows whole.
    #[test]
    fn an_operation_the_tested_constant_decides_needs_no_select() {
        use Order::{TestedLeft, TestedRight};
        assert!(settled(IntPred::Ne, 0, Opcode::Mul, TestedRight, Some(0)));
        assert!(settled(IntPred::Eq, 0, Opcode::And, TestedLeft, Some(0)));
        assert!(settled(IntPred::Eq, -1, Opcode::Or, TestedRight, Some(-1)));
        assert!(settled(IntPred::Eq, 0, Opcode::Shl, TestedLeft, Some(0)));
        assert!(settled(IntPred::Eq, -1, Opcode::AShr, TestedLeft, Some(-1)));
    }

    /// The ones that look the same and are not, each of which has to keep its select.
    #[test]
    fn an_operation_the_tested_constant_does_not_settle_keeps_its_select() {
        use Order::{TestedLeft, TestedRight};
        // `x - y` at zero is `-y`, and a shift of zero by `y` is zero rather than `y`.
        assert!(!settled(IntPred::Eq, 0, Opcode::Sub, TestedLeft, None));
        assert!(!settled(IntPred::Eq, 0, Opcode::Shl, TestedLeft, None));
        // One is not what an add leaves alone, and zero is not what a multiply does.
        assert!(!settled(IntPred::Eq, 1, Opcode::Add, TestedRight, None));
        assert!(!settled(IntPred::Eq, 0, Opcode::Mul, TestedRight, None));
        // The multiply at zero is zero, so the side that keeps a value has to keep zero.
        assert!(!settled(IntPred::Eq, 0, Opcode::Mul, TestedRight, Some(1)));
    }

    /// `x == 0 ? y + x : y` is `y`, since the add on the side the test holds on gives `y` too, and
    /// then nothing reads the add and `dce` takes it.
    #[test]
    fn an_operation_on_the_side_the_test_holds_on_gives_way_to_the_other_side() {
        let mut func =
            element_diamond(IntPred::Eq, 0, Opcode::Add, Order::TestedRight, None, Shape::Swapped);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::VALUE_IMPLIED), 1);
        let params = func[Block::from_usize(0)].params.to_vec();
        assert_eq!(carries(&func, 0), vec![params[1]]);
    }

    /// A division by the tested value could trap on the path that did not divide, so it is not
    /// taken, and the branch it is in is kept for the same reason.
    #[test]
    fn a_division_is_not_an_operation_the_constant_settles() {
        let mut func =
            element_diamond(IntPred::Eq, 1, Opcode::SDiv, Order::TestedRight, None, Shape::Plain);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::VALUE_IMPLIED), 0);
    }

    /// `x == 0 ? y : y + (long)x`, which is how the front end hands over the add when `y` is the
    /// wider of the two.
    #[test]
    fn a_widened_tested_value_is_still_the_tested_value() {
        let mut func =
            element_diamond(IntPred::Eq, 0, Opcode::Add, Order::TestedRight, None, Shape::Widened);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::VALUE_IMPLIED), 1);
        assert!(!opcodes(&func, 0).contains(&Opcode::Select));
    }

    /// Two constants that are not the same number are not the same number on any edge.
    #[test]
    fn two_different_constants_are_not_asked_about() {
        let mut func = empty_arms();
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::VALUE_IMPLIED), 0);
        assert!(opcodes(&func, 0).contains(&Opcode::Select));
    }

    #[test]
    fn a_store_both_arms_make_to_one_place_is_made_once_below_the_branch() {
        let mut func = both_arms_store(plain(), [Flags::NONE; 2], false);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::STORE_REPLACED), 1);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        // One store, below the select that chooses what it writes, and no branch above either.
        assert_eq!(
            opcodes(&func, 0),
            vec![Opcode::IConst, Opcode::ICmp, Opcode::Select, Opcode::Store, Opcode::Jump]
        );
        assert_eq!(blocks(&func), vec![0, 3]);
        assert_eq!(goes_to(&func, 0), vec![3]);
    }

    #[test]
    fn the_one_store_writes_what_the_side_the_condition_holds_on_was_writing() {
        let mut func = both_arms_store(plain(), [Flags::NONE; 2], false);
        phiopt(&mut func);
        let head = Block::from_usize(0);
        let select = func
            .insts(head)
            .find(|&inst| func[inst].opcode == Opcode::Select)
            .expect("the select the pass just built");
        let store = func
            .insts(head)
            .find(|&inst| func[inst].opcode == Opcode::Store)
            .expect("the one store that is left");
        let chosen = func[func[select].args].to_vec();
        let written = func[func[store].args].to_vec();
        // The head's parameters in order: the address, then what each side writes.
        let params = func[head].params.to_vec();
        assert_eq!(chosen[1], params[1], "the arm the branch named first");
        assert_eq!(chosen[2], params[2], "the arm the branch named second");
        assert_eq!(written[0], func[select].first_result.expect("a select produces one value"));
        assert_eq!(written[1], params[0], "the address both arms named");
    }

    /// Both arms writing the same value needs no select, only the one store.
    #[test]
    fn two_arms_that_write_the_same_thing_get_a_store_and_no_select() {
        let mut func = both_arms_store(plain(), [Flags::NONE; 2], false);
        // Point the second arm's store at the first arm's value, which is what the front end
        // produces when both branches of a conditional assign the same thing.
        let head = Block::from_usize(0);
        let params = func[head].params.to_vec();
        let store = func
            .insts(Block::from_usize(2))
            .find(|&inst| func[inst].opcode == Opcode::Store)
            .expect("the second arm's store");
        let args = func.push_values(&[params[1], params[0]]);
        func[store].args = args;

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::STORE_REPLACED), 1);
        assert_eq!(
            opcodes(&func, 0),
            vec![Opcode::IConst, Opcode::ICmp, Opcode::Store, Opcode::Jump]
        );
    }

    /// Two stores to two different places is two writes, and doing both is writing one of them twice.
    #[test]
    fn two_arms_that_store_to_different_addresses_keep_their_branch() {
        let mut func = both_arms_store(plain(), [Flags::NONE; 2], true);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::STORE_REPLACED), 0);
        assert_eq!(stats.count(Kind::Missed, super::STORES_DO_NOT_MATCH), 1);
        assert_eq!(goes_to(&func, 0), vec![1, 2]);
    }

    #[test]
    fn a_volatile_store_keeps_its_branch_even_when_both_arms_make_it() {
        let mut func = both_arms_store(plain(), [Flags::VOLATILE; 2], false);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::STORE_REPLACED), 0);
        assert_eq!(stats.count(Kind::Missed, super::STORES_DO_NOT_MATCH), 1);
        assert_eq!(goes_to(&func, 0), vec![1, 2]);
    }

    #[test]
    fn an_atomic_store_keeps_its_branch_even_when_both_arms_make_it() {
        let mut func = both_arms_store(
            MemInfo { order: MemOrder::SeqCst, ..plain() },
            [Flags::NONE; 2],
            false,
        );
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::STORE_REPLACED), 0);
        assert_eq!(stats.count(Kind::Missed, super::STORES_DO_NOT_MATCH), 1);
    }

    /// Two stores told different things about the access have no one answer to carry downward.
    #[test]
    fn two_stores_that_disagree_about_the_access_keep_their_branch() {
        let mut func = both_arms_store(plain(), [Flags::NONE; 2], false);
        let store = func
            .insts(Block::from_usize(2))
            .find(|&inst| func[inst].opcode == Opcode::Store)
            .expect("the second arm's store");
        let mem = func.add_mem(MemInfo { align: 1, ..plain() });
        func[store].extra = Extra::Mem(mem);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::STORE_REPLACED), 0);
        assert_eq!(stats.count(Kind::Missed, super::STORES_DO_NOT_MATCH), 1);
    }

    /// The store comes off the work count, because one of the two arms was always going to make it.
    ///
    /// Each arm here holds the store and as much other work as the rule allows, so counting the
    /// store as work would put both arms one over the limit and the branch would stay.
    #[test]
    fn a_store_each_way_does_not_count_against_how_long_the_arms_may_be() {
        let mut func = both_arms_store(plain(), [Flags::NONE; 2], false);
        let params = func[Block::from_usize(0)].params.to_vec();
        for arm in [1, 2] {
            let block = Block::from_usize(arm);
            let term = func.terminator(block).expect("an arm ends in its jump");
            func.remove_inst(term);
            let mut build = Builder::new(&mut func, block);
            let mut value = params[1];
            for _ in 0..rucc_cost::heuristics::PHIOPT_ARM_INSTRUCTIONS {
                value = build.binary(Opcode::Add, value, params[2], Flags::NONE);
            }
            func.append_inst(block, term);
        }

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Missed, super::ARMS_TOO_LONG), 0);
        assert_eq!(stats.count(Kind::Optimized, super::STORE_REPLACED), 1);
    }

    /// A store one side makes and the other does not, which is the transformation with no proof.
    #[test]
    fn an_arm_that_stores_where_the_other_does_not_keeps_its_branch() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        let mut build = Builder::new(&mut func, arms[0]);
        store_something(&mut build);
        let it = build.iconst(Type::int(32), 1);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, arms[1]);
        let it = build.iconst(Type::int(32), 2);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::STORE_ON_ONE_PATH), 1);
        assert_eq!(goes_to(&func, 0), vec![1, 2]);
    }

    /// `if (x < a[2]) a[2] = x;` on a local `int a[8]`, which is the one armed store section 22.6
    /// needs a proof for.
    ///
    /// Block 0 is the head, which makes the local and branches. Block 1 is the arm, which works the
    /// slot's address out a second time, the way a subscript is lowered, and stores to it. Block 2
    /// is the join. `escape` hands the local's address to memory first, and `read` says whether the
    /// head reads the slot or compares against zero instead.
    fn one_arm_stores(escape: bool, read: bool) -> Func {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let written = func.append_param(head, Type::int(32));
        let arm = func.create_block();
        let join = func.create_block();

        let mut build = Builder::new(&mut func, head);
        let mem = build.func().add_mem(MemInfo { size: 32, align: 16, ..plain() });
        let alloca = InstData { extra: Extra::Mem(mem), ..InstData::new(Opcode::Alloca) };
        let local = build.value(alloca, Type::PTR);
        if escape {
            let somewhere = build.iconst(Type::int(64), 16);
            let somewhere = build.unary(Opcode::IntToPtr, somewhere, Type::PTR);
            build.store(local, somewhere, MemInfo { size: 8, align: 8, ..plain() }, Flags::NONE);
        }
        let eight = build.iconst(Type::int(64), 8);
        let slot = build.binary(Opcode::PtrAdd, local, eight, Flags::NONE);
        let against = if read {
            build.load(Type::int(32), slot, plain(), Flags::NONE)
        } else {
            build.iconst(Type::int(32), 0)
        };
        let test = build.icmp(IntPred::Slt, written, against);
        build.br_if(test, arm, &[], join, &[]);
        let mut build = Builder::new(&mut func, arm);
        let eight = build.iconst(Type::int(64), 8);
        let slot = build.binary(Opcode::PtrAdd, local, eight, Flags::NONE);
        build.store(written, slot, plain(), Flags::NONE);
        build.jump(join, &[]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[]);
        func
    }

    /// The fold GCC makes too, and the second address the arm works out costs nothing, since it is
    /// the head's address worked out again and would otherwise have put the arm over the limit.
    #[test]
    fn a_store_one_arm_makes_to_a_local_the_head_read_is_made_on_both_paths() {
        let mut func = one_arm_stores(false, true);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::STORE_GUARDED), 1);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert_eq!(blocks(&func), vec![0, 2]);
        let ops = opcodes(&func, 0);
        assert_eq!(ops.iter().filter(|&&op| op == Opcode::Load).count(), 2);
        assert_eq!(ops[ops.len() - 3..], [Opcode::Select, Opcode::Store, Opcode::Jump]);
    }

    /// The read that stands in for the side that did not store is told everything the store was
    /// told except the padding it owns, which is a thing only a store records. `20021010-2.c` is
    /// a structure copy whose member store owns the padding after it, and the read made from it
    /// failed the verifier.
    #[test]
    fn the_read_a_one_armed_store_is_given_owns_no_padding() {
        let mut func = one_arm_stores(false, true);
        let arm = Block::from_usize(1);
        let store = func.insts(arm).find(|&inst| func[inst].opcode == Opcode::Store).unwrap();
        let Extra::Mem(mem) = func[store].extra else { panic!("a store says what it is") };
        let owning = func.add_mem(MemInfo { owns: 2, ..func[mem] });
        func[store].extra = Extra::Mem(owning);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        let head = Block::from_usize(0);
        let mut owns = Vec::new();
        for inst in func.insts(head).collect::<Vec<_>>() {
            if let Extra::Mem(mem) = func[inst].extra {
                owns.push((func[inst].opcode, func[mem].owns));
            }
        }
        assert!(owns.contains(&(Opcode::Store, 2)), "{owns:?}");
        assert!(owns.iter().all(|&(op, owns)| op == Opcode::Store || owns == 0), "{owns:?}");
    }

    /// A local whose address has left the function is one another thread could be writing.
    #[test]
    fn a_store_one_arm_makes_to_a_local_that_escaped_keeps_its_branch() {
        let mut func = one_arm_stores(true, true);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::STORE_ON_ONE_PATH), 1);
        assert_eq!(goes_to(&func, 0), vec![1, 2]);
    }

    /// Without the head's read nothing says the other path ever reached the slot, and `a[k]` with a
    /// `k` the branch was guarding is the case where it did not.
    #[test]
    fn a_store_one_arm_makes_to_a_slot_the_head_never_touched_keeps_its_branch() {
        let mut func = one_arm_stores(false, false);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::STORE_ON_ONE_PATH), 1);
        assert_eq!(goes_to(&func, 0), vec![1, 2]);
    }

    /// `x = *p; if (x < 0) x = *p;`, with the arm's load told `flags`.
    fn arm_reads(flags: Flags) -> Func {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::PTR]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let address = func.append_param(head, Type::PTR);
        let arm = func.create_block();
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let first = build.load(Type::int(32), address, plain(), Flags::NONE);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, first, zero);
        build.br_if(test, arm, &[], join, &[zero]);
        let mut build = Builder::new(&mut func, arm);
        let again = build.load(Type::int(32), address, plain(), flags);
        build.jump(join, &[again]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);
        func
    }

    #[test]
    fn a_load_in_an_arm_of_an_address_the_head_read_is_made_on_both_paths() {
        let mut func = arm_reads(Flags::NONE);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::LOAD_SPECULATED), 1);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert_eq!(blocks(&func), vec![0, 2]);
    }

    /// How many reads there are is what `volatile` makes observable, so the head's read proves
    /// nothing about a second one.
    #[test]
    fn a_volatile_load_in_an_arm_keeps_its_branch() {
        let mut func = arm_reads(Flags::VOLATILE);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::ARM_HAS_EFFECTS), 1);
        assert_eq!(goes_to(&func, 0), vec![1, 2]);
    }

    /// A load, which is the effect that is not a store and gets the general answer.
    #[test]
    fn an_arm_that_does_something_else_keeps_its_branch() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        let mut build = Builder::new(&mut func, arms[0]);
        let address = build.iconst(Type::int(64), 16);
        let address = build.unary(Opcode::IntToPtr, address, Type::PTR);
        let it = build.load(Type::int(32), address, plain(), Flags::NONE);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, arms[1]);
        let it = build.iconst(Type::int(32), 2);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::ARM_HAS_EFFECTS), 1);
        assert_eq!(goes_to(&func, 0), vec![1, 2]);
    }

    /// A division whose divisor is not known cannot be moved onto the path that skipped it.
    #[test]
    fn an_arm_that_divides_by_something_unknown_keeps_its_branch() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32), Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, Type::int(32));
        let right = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Ne, right, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        let mut build = Builder::new(&mut func, arms[0]);
        let it = build.binary(Opcode::SDiv, left, right, Flags::NONE);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, arms[1]);
        let it = build.iconst(Type::int(32), 0);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::ARM_MAY_TRAP), 1);
        assert_eq!(goes_to(&func, 0), vec![1, 2]);
    }

    #[test]
    fn a_division_by_a_constant_that_is_not_zero_or_minus_one_is_moved() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        let mut build = Builder::new(&mut func, arms[0]);
        let three = build.iconst(Type::int(32), 3);
        let it = build.binary(Opcode::SDiv, outside, three, Flags::NONE);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, arms[1]);
        let it = build.iconst(Type::int(32), 0);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert!(opcodes(&func, 0).contains(&Opcode::SDiv));
    }

    /// Nothing chooses between two pointers, so the shape is matched and then left alone.
    #[test]
    fn a_value_no_select_is_lowered_for_keeps_its_branch() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        func.append_param(join, Type::PTR);

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for (arm, value) in arms.iter().zip([16, 32]) {
            let mut build = Builder::new(&mut func, *arm);
            let it = build.iconst(Type::int(64), value);
            let it = build.unary(Opcode::IntToPtr, it, Type::PTR);
            build.jump(join, &[it]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::NO_SELECT_AT_THAT_WIDTH), 1);
    }

    /// And nothing chooses between two floats either, at any format.
    ///
    /// Worth its own test although the answer is the pointer one's, because this is the pass that
    /// decides it for every float in the language and `crates/rucc-codegen/src/quad.rs` says so in
    /// its own documentation: a conditional expression over two quads is a branch and a phi and
    /// stays one, so the back end never sees a `select` at that format and needs no lowering for
    /// one. A quad here rather than a `double` since the quad is the format with no register of its
    /// own arithmetic, which makes it the one a later change is most likely to reach for.
    #[test]
    fn a_choice_between_two_quads_keeps_its_branch_as_well() {
        let mut names = Interner::new();
        let quad = Type::float(Float::F128);
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        func.append_param(join, quad);

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for (arm, bits) in arms.iter().zip([0x3fff_u128 << 112, 0x4000_u128 << 112]) {
            let mut build = Builder::new(&mut func, *arm);
            let it = build.fconst(quad, bits);
            build.jump(join, &[it]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::NO_SELECT_AT_THAT_WIDTH), 1);
    }

    #[test]
    fn arms_with_more_work_in_them_than_the_budget_keep_their_branch() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        let mut build = Builder::new(&mut func, arms[0]);
        // Four instructions, which is past the budget however cheap each of them is.
        let mut it = outside;
        for _ in 0..4 {
            it = build.binary(Opcode::Add, it, outside, Flags::NONE);
        }
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, arms[1]);
        let it = build.iconst(Type::int(32), 0);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::ARMS_TOO_LONG), 1);
    }

    /// An arm whose work is one addition and two constants, one of them left over.
    ///
    /// This is `acc = v < k ? acc + 1 : acc` with `acc` an `unsigned long long`, as the front end
    /// hands it over: the `1` written as an `int`, the same `1` as the add reads it, and the add.
    /// Only the add is work, so the arm fits and the branch goes.
    #[test]
    fn constants_in_an_arm_are_not_counted_as_work() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32), Type::int(64)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let acc = func.append_param(head, Type::int(64));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(64));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        let mut build = Builder::new(&mut func, arms[0]);
        build.iconst(Type::int(32), 1);
        let one = build.iconst(Type::int(64), 1);
        let it = build.binary(Opcode::Add, acc, one, Flags::NONE);
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, arms[1]);
        build.jump(join, &[acc]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Missed, super::ARMS_TOO_LONG), 0);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
    }

    /// The same arm with a third operation in it is still too long, constants or not.
    #[test]
    fn an_arm_of_three_operations_is_too_long_with_its_constants_free() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32), Type::int(64)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let acc = func.append_param(head, Type::int(64));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(64));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        let mut build = Builder::new(&mut func, arms[0]);
        let mut it = acc;
        for step in 1..=3 {
            let by = build.iconst(Type::int(64), step);
            it = build.binary(Opcode::Mul, it, by, Flags::NONE);
        }
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, arms[1]);
        build.jump(join, &[acc]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::ARMS_TOO_LONG), 1);
    }

    /// The margin, at the two ends of it and just outside.
    #[test]
    fn the_margin_is_three_in_from_each_end() {
        let guessed = |percent: u32| Probability::percent(percent, Quality::Guessed);
        assert!(super::unpredictable(Probability::even()));
        assert!(super::unpredictable(guessed(3)));
        assert!(super::unpredictable(guessed(97)));
        assert!(!super::unpredictable(guessed(2)));
        assert!(!super::unpredictable(guessed(98)));
        assert!(!super::unpredictable(Probability::always()));
        assert!(!super::unpredictable(Probability::never()));
    }

    /// A diamond with an add in one arm and a subtract in the other, with a hint on its branch the
    /// way `crate::expect` writes one: `parts` of [`rucc_ir::Hint::SCALE`] on the first arm and the
    /// rest on the second.
    fn hinted_diamond(parts: u32) -> Stats {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let test = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for (arm, opcode) in arms.into_iter().zip([Opcode::Add, Opcode::Sub]) {
            let mut build = Builder::new(&mut func, arm);
            let it = build.binary(opcode, outside, outside, Flags::NONE);
            build.jump(join, &[it]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let term = func.terminator(head).expect("a branch");
        let hint = rucc_ir::Hint::parts(parts);
        for (at, hint) in func.target_list(term).iter().zip([hint, hint.complement()]) {
            let call = func[at];
            func.set_block_call(at, rucc_ir::BlockCall { hint, ..call });
        }
        phiopt(&mut func)
    }

    /// `__builtin_expect_with_probability` at 99%, either way round, keeps the branch.
    #[test]
    fn a_diamond_hinted_past_the_margin_keeps_its_branch() {
        for parts in [9_900, 100] {
            let stats = hinted_diamond(parts);
            assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0, "{parts}");
            assert_eq!(stats.count(Kind::Missed, super::BRANCH_IS_PREDICTED), 1, "{parts}");
        }
    }

    /// A plain `__builtin_expect` claims 90%, which the corpus timed as a branch that still loses to
    /// a select, and a hint at even says nothing at all. Both convert.
    #[test]
    fn a_diamond_hinted_inside_the_margin_converts() {
        for parts in [9_000, 1_000, 5_000] {
            let stats = hinted_diamond(parts);
            assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1, "{parts}");
            assert_eq!(stats.count(Kind::Missed, super::BRANCH_IS_PREDICTED), 0, "{parts}");
        }
    }

    #[test]
    fn an_arm_that_two_edges_reach_is_not_an_arm() {
        let mut names = Interner::new();
        let signature = Signature::new().with_params(&[Type::int(32)]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let outside = func.append_param(head, Type::int(32));
        let above = func.create_block();
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, Type::int(32));

        // The entry reaches the first arm as well as the head does, so moving the arm's work into
        // the head would leave the entry's path without it.
        let mut build = Builder::new(&mut func, head);
        let zero = build.iconst(Type::int(32), 0);
        let first = build.icmp(IntPred::Slt, outside, zero);
        build.br_if(first, above, &[], arms[0], &[]);
        let mut build = Builder::new(&mut func, above);
        let one = build.iconst(Type::int(32), 1);
        let second = build.icmp(IntPred::Slt, outside, one);
        build.br_if(second, arms[0], &[], arms[1], &[]);
        for (arm, value) in arms.iter().zip([1, 2]) {
            let mut build = Builder::new(&mut func, *arm);
            let it = build.iconst(Type::int(32), value);
            build.jump(join, &[it]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        // Neither branch is a diamond. The head's first side goes to a block that is not the join
        // and is not an arm either, since two edges reach it, and the second branch's first side
        // is the same block for the same reason.
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(goes_to(&func, 0), vec![1, 2]);
        assert_eq!(goes_to(&func, 1), vec![2, 3]);
    }

    #[test]
    fn fuel_stops_the_conversion_where_it_stands() {
        let mut func = empty_arms();
        let mut fuel = Fuel::of(0);
        let stats = PhiOpt.run(&mut func, &mut crate::machine::fixtures::analyses(), &mut fuel);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 0);
        assert_eq!(stats.count(Kind::Missed, super::NO_FUEL), 1);
        assert_eq!(goes_to(&func, 0), vec![1, 2]);
    }

    /// `x < y ? f(a, k) : f(b, k)`, as a diamond whose two arms do the same thing to different
    /// operands.
    ///
    /// Block 0 is the head, taking the two values it compares and the two operands and working out
    /// the operand both arms share. Blocks 1 and 2 are the arms, each applying every one of
    /// `steps` to its own operand and that shared value, and block 3 is the join, taking one
    /// parameter for each of them.
    fn same_operation(steps: &[Opcode]) -> Func {
        let mut names = Interner::new();
        let int = Type::int(32);
        let signature = Signature::new().with_params(&[int, int, int, int]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, int);
        let right = func.append_param(head, int);
        let operands = [func.append_param(head, int), func.append_param(head, int)];
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let params: Vec<Value> = steps.iter().map(|_| func.append_param(join, int)).collect();

        let mut build = Builder::new(&mut func, head);
        // In the head rather than in each arm, so that the two sides share this operand as one
        // value. Two arms that each work out their own three are two operations apart, not one.
        let shared = build.iconst(int, 3);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for (&arm, operand) in arms.iter().zip(operands) {
            let mut build = Builder::new(&mut func, arm);
            let carried: Vec<Value> = steps
                .iter()
                .map(|&opcode| build.binary(opcode, operand, shared, Flags::default()))
                .collect();
            build.jump(join, &carried);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&params);
        func
    }

    /// The transformation. Two adds become one add of a select, rather than one select of two adds.
    #[test]
    fn an_operation_both_arms_did_is_done_once_below_the_branch() {
        let mut func = same_operation(&[Opcode::Add]);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 1);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert_eq!(
            opcodes(&func, 0),
            vec![Opcode::IConst, Opcode::ICmp, Opcode::Select, Opcode::Add, Opcode::Jump],
            "the select chooses the operand and the add happens once"
        );
        assert_eq!(blocks(&func), vec![0, 3]);
    }

    /// The select goes under the operation, so what it chooses between is the operands and not the
    /// answers. Getting that the wrong way round would be a select of two adds that happens to have
    /// the right opcodes in it.
    #[test]
    fn the_select_chooses_the_operands_and_not_the_answers() {
        let mut func = same_operation(&[Opcode::Add]);
        phiopt(&mut func);
        let head = Block::from_usize(0);
        let select = func
            .insts(head)
            .find(|&inst| func[inst].opcode == Opcode::Select)
            .expect("the select the pass just built");
        let add = func
            .insts(head)
            .find(|&inst| func[inst].opcode == Opcode::Add)
            .expect("the add the pass just wrote");
        let chosen = func[func[select].args].to_vec();
        let params = func[head].params.to_vec();
        assert_eq!(&chosen[1..], &params[2..], "the two operands the arms differed in");
        let added = func[func[add].args].to_vec();
        assert_eq!(added[0], func[select].first_result.expect("a select has a result"));
        assert_eq!(carries(&func, 0), vec![func[add].first_result.expect("an add has a result")]);
    }

    /// Nothing is speculated by an operation both arms were doing, so the length rule is about what
    /// is left after the factoring rather than about what the arms arrived holding. Three
    /// instructions an arm is over the limit, and three instructions that all factor is none.
    #[test]
    fn arms_that_factor_away_entirely_are_not_too_long() {
        let steps = [Opcode::Add, Opcode::Sub, Opcode::Mul];
        let mut func = same_operation(&steps);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Missed, super::ARMS_TOO_LONG), 0);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 3);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        let written = opcodes(&func, 0);
        assert_eq!(written.iter().filter(|&&op| op == Opcode::Select).count(), 3);
        for step in steps {
            assert_eq!(written.iter().filter(|&&op| op == step).count(), 1, "{step:?} once");
        }
    }

    /// Both arms doing the same thing to the same operands is a common subexpression nothing has
    /// numbered, and one copy of it serves both sides with no select at all.
    #[test]
    fn arms_that_agree_in_every_operand_need_no_select() {
        let mut names = Interner::new();
        let int = Type::int(32);
        let signature = Signature::new().with_params(&[int, int, int]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, int);
        let right = func.append_param(head, int);
        let operand = func.append_param(head, int);
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, int);

        let mut build = Builder::new(&mut func, head);
        let shared = build.iconst(int, 3);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for &arm in &arms {
            let mut build = Builder::new(&mut func, arm);
            let it = build.binary(Opcode::Add, operand, shared, Flags::default());
            build.jump(join, &[it]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 1);
        assert_eq!(
            opcodes(&func, 0),
            vec![Opcode::IConst, Opcode::ICmp, Opcode::Add, Opcode::Jump],
            "one add and nothing to choose between"
        );
    }

    /// `x < y ? g(f(a)) : g(f(b))` and so on down, as a diamond whose arms each run their own list
    /// of operations over their own operand, every step taking the value the step before it made.
    ///
    /// Block 0 is the head, blocks 1 and 2 the arms, and block 3 the join, with one parameter.
    fn chain(steps: [&[Opcode]; 2]) -> Func {
        let mut names = Interner::new();
        let int = Type::int(32);
        let signature = Signature::new().with_params(&[int, int, int, int]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, int);
        let right = func.append_param(head, int);
        let operands = [func.append_param(head, int), func.append_param(head, int)];
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, int);

        let mut build = Builder::new(&mut func, head);
        let shared = build.iconst(int, 3);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for ((&arm, operand), steps) in arms.iter().zip(operands).zip(steps) {
            let mut build = Builder::new(&mut func, arm);
            let mut value = operand;
            for &opcode in steps {
                value = build.binary(opcode, value, shared, Flags::default());
            }
            build.jump(join, &[value]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);
        func
    }

    /// How many times each of these opcodes is in the head after the pass.
    fn counted(func: &Func, wanted: &[Opcode]) -> Vec<usize> {
        let written = opcodes(func, 0);
        wanted.iter().map(|&op| written.iter().filter(|&&one| one == op).count()).collect()
    }

    /// `x < y ? total + g(f(a)) : total + g(f(b))`, where every step under the add is a conversion
    /// to the width it names, with each arm running its own list over its own operand.
    ///
    /// Block 0 is the head, taking the two values it compares, the two 32 bit operands and a 64 bit
    /// total, blocks 1 and 2 are the arms, and block 3 is the join, with one 64 bit parameter.
    fn converted(steps: [&[(Opcode, u32)]; 2]) -> Func {
        let mut names = Interner::new();
        let (int, wide) = (Type::int(32), Type::int(64));
        let signature = Signature::new().with_params(&[int, int, int, int, wide]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, int);
        let right = func.append_param(head, int);
        let operands = [func.append_param(head, int), func.append_param(head, int)];
        let total = func.append_param(head, wide);
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, wide);

        let mut build = Builder::new(&mut func, head);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for ((&arm, operand), steps) in arms.iter().zip(operands).zip(steps) {
            let mut build = Builder::new(&mut func, arm);
            let mut value = operand;
            for &(opcode, bits) in steps {
                value = build.unary(opcode, value, Type::int(bits));
            }
            let sum = build.binary(Opcode::Add, total, value, Flags::default());
            build.jump(join, &[sum]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);
        func
    }

    /// The type of the one select the pass wrote into the head.
    fn selected(func: &Func) -> Type {
        let select = func
            .insts(Block::from_usize(0))
            .find(|&inst| func[inst].opcode == Opcode::Select)
            .expect("the select the pass just built");
        func[func[select].first_result.expect("a select has a result")].ty
    }

    /// An add over a widening over a narrowing, all three shared, is all three written once, with
    /// the select under the lowest of them choosing between the two operands.
    #[test]
    fn a_chain_of_conversions_is_factored_all_the_way_down() {
        let steps: &[(Opcode, u32)] = &[(Opcode::Trunc, 16), (Opcode::SExt, 64)];
        let mut func = converted([steps, steps]);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 3);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        let head = [Opcode::Select, Opcode::Trunc, Opcode::SExt, Opcode::Add];
        assert_eq!(counted(&func, &head), vec![1, 1, 1, 1]);
        assert_eq!(selected(&func), Type::int(32), "the select is under the whole chain");
        assert_eq!(blocks(&func), vec![0, 3]);
    }

    /// Where the two arms stop doing the same thing is where the select goes, choosing between
    /// the two different answers, with the level above them still written once.
    #[test]
    fn a_chain_that_differs_at_the_second_level_is_factored_one_deep() {
        let mut func = converted([&[(Opcode::SExt, 64)], &[(Opcode::ZExt, 64)]]);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 1);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        let head = [Opcode::Select, Opcode::SExt, Opcode::ZExt, Opcode::Add];
        assert_eq!(counted(&func, &head), vec![1, 1, 1, 1]);
        assert_eq!(selected(&func), Type::int(64));
    }

    /// Below the operation the join reads, only an operation of one operand is factored, the way
    /// gcc's loop over `factor_out_conditional_operation` only takes those. `total + (i + i)`
    /// against `total + (i + 1)` would otherwise be `total + (i + select(i, 1))`, which once the
    /// loop is unrolled is an add of a select where there had been a select of two constants.
    #[test]
    fn an_operation_of_two_operands_below_the_first_level_is_not_factored() {
        let steps: &[Opcode] = &[Opcode::Add, Opcode::Mul];
        let mut func = chain([steps, steps]);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 1);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        let head = [Opcode::Select, Opcode::Add, Opcode::Mul];
        assert_eq!(counted(&func, &head), vec![1, 2, 1]);
    }

    /// A chain longer than the bound is factored as deep as the bound, and the rest stays in the
    /// arms as work the cost rule is asked about.
    #[test]
    fn a_chain_is_factored_only_as_deep_as_the_bound() {
        let bound = rucc_cost::heuristics::PHIOPT_FACTOR_DEPTH;
        let depth = usize::try_from(bound).unwrap();
        let steps: Vec<(Opcode, u32)> = (0..=depth)
            .map(|at| if at % 2 == 0 { (Opcode::SExt, 64) } else { (Opcode::Trunc, 32) })
            .collect();
        let steps = &steps[..depth + usize::from(depth % 2 == 0)];
        let mut func = converted([steps, steps]);
        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), bound);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
    }

    /// The shape the issue came from. `total + (long)(x * 2)` against `total + (long)(x + 1)`
    /// factors the add and the widening under it, and the select is between the two 32 bit
    /// answers, so neither widening is left in an arm.
    /// `flag ? total + (long long)0 : total + (long long)1`, which is what a loop over
    /// `total += (long long)(i * 2)` against `total += (long long)(i + 1)` is once it is unrolled.
    /// The widenings fold into their constants, so only the add is factored and the select is
    /// between the two wide constants, rather than a narrow select widened after it.
    #[test]
    fn a_widening_of_a_constant_in_each_arm_is_left_to_fold() {
        let mut names = Interner::new();
        let (narrow, wide) = (Type::int(32), Type::int(64));
        let signature = Signature::new().with_params(&[narrow, narrow, wide]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, narrow);
        let right = func.append_param(head, narrow);
        let total = func.append_param(head, wide);
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, wide);

        let mut build = Builder::new(&mut func, head);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for (&arm, value) in arms.iter().zip([0, 1]) {
            let mut build = Builder::new(&mut func, arm);
            let value = build.iconst(narrow, value);
            let widened = build.unary(Opcode::SExt, value, wide);
            let sum = build.binary(Opcode::Add, total, widened, Flags::default());
            build.jump(join, &[sum]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 1);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert_eq!(selected(&func), wide, "the select is between the two widened constants");
    }

    #[test]
    fn a_widening_both_arms_share_under_an_operation_is_factored_too() {
        let mut names = Interner::new();
        let (narrow, wide) = (Type::int(32), Type::int(64));
        let signature = Signature::new().with_params(&[narrow, narrow, narrow, wide]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, narrow);
        let right = func.append_param(head, narrow);
        let x = func.append_param(head, narrow);
        let total = func.append_param(head, wide);
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, wide);

        let mut build = Builder::new(&mut func, head);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for (&arm, (opcode, by)) in arms.iter().zip([(Opcode::Mul, 2), (Opcode::Add, 1)]) {
            let mut build = Builder::new(&mut func, arm);
            let by = build.iconst(narrow, by);
            let step = build.binary(opcode, x, by, Flags::default());
            let widened = build.unary(Opcode::SExt, step, wide);
            let sum = build.binary(Opcode::Add, total, widened, Flags::default());
            build.jump(join, &[sum]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 2);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        let head = [Opcode::Select, Opcode::SExt, Opcode::Add, Opcode::Mul];
        assert_eq!(counted(&func, &head), vec![1, 1, 2, 1]);
        let select = func
            .insts(Block::from_usize(0))
            .find(|&inst| func[inst].opcode == Opcode::Select)
            .unwrap();
        let chosen = func[select].first_result.unwrap();
        assert_eq!(func[chosen].ty, narrow, "the select is under the widening");
    }

    /// Two different operations are two operations, and the pass falls back to hoisting both and
    /// selecting between what they produced.
    #[test]
    fn arms_that_do_different_things_are_not_factored() {
        let mut names = Interner::new();
        let int = Type::int(32);
        let signature = Signature::new().with_params(&[int, int, int, int]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, int);
        let right = func.append_param(head, int);
        let operands = [func.append_param(head, int), func.append_param(head, int)];
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, int);

        let mut build = Builder::new(&mut func, head);
        let shared = build.iconst(int, 3);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for ((&arm, operand), opcode) in arms.iter().zip(operands).zip([Opcode::Add, Opcode::Sub]) {
            let mut build = Builder::new(&mut func, arm);
            let it = build.binary(opcode, operand, shared, Flags::default());
            build.jump(join, &[it]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 0);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert_eq!(
            opcodes(&func, 0),
            vec![
                Opcode::IConst,
                Opcode::ICmp,
                Opcode::Add,
                Opcode::Sub,
                Opcode::Select,
                Opcode::Jump
            ],
            "both operations hoisted and a select between their answers"
        );
    }

    /// Two operand positions apart needs two selects and one operation, which is what one select
    /// and two operations already cost, so there is nothing to win and it is left alone.
    #[test]
    fn arms_that_differ_in_two_operands_are_not_factored() {
        let mut names = Interner::new();
        let int = Type::int(32);
        let signature = Signature::new().with_params(&[int, int, int, int, int, int]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, int);
        let right = func.append_param(head, int);
        let first = [func.append_param(head, int), func.append_param(head, int)];
        let second = [func.append_param(head, int), func.append_param(head, int)];
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let param = func.append_param(join, int);

        let mut build = Builder::new(&mut func, head);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for ((&arm, one), two) in arms.iter().zip(first).zip(second) {
            let mut build = Builder::new(&mut func, arm);
            let it = build.binary(Opcode::Add, one, two, Flags::default());
            build.jump(join, &[it]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 0);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert_eq!(opcodes(&func, 0).iter().filter(|&&op| op == Opcode::Add).count(), 2);
    }

    /// The one copy is written after the arms have gone, so an operation something else in the arm
    /// reads cannot be one of the two it replaces. Here each arm hands its answer to the join
    /// twice, which is two readers and not one.
    #[test]
    fn an_operation_read_more_than_once_is_not_factored() {
        let mut names = Interner::new();
        let int = Type::int(32);
        let signature = Signature::new().with_params(&[int, int, int, int]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, int);
        let right = func.append_param(head, int);
        let operands = [func.append_param(head, int), func.append_param(head, int)];
        let arms = [func.create_block(), func.create_block()];
        let join = func.create_block();
        let params = [func.append_param(join, int), func.append_param(join, int)];

        let mut build = Builder::new(&mut func, head);
        let shared = build.iconst(int, 3);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arms[0], &[], arms[1], &[]);
        for (&arm, operand) in arms.iter().zip(operands) {
            let mut build = Builder::new(&mut func, arm);
            let it = build.binary(Opcode::Add, operand, shared, Flags::default());
            build.jump(join, &[it, it]);
        }
        let mut build = Builder::new(&mut func, join);
        build.ret(&params);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 0);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
        assert_eq!(opcodes(&func, 0).iter().filter(|&&op| op == Opcode::Add).count(), 2);
    }

    /// A triangle has a block on one side only, so there is no second operation to pair the first
    /// one with and nothing to factor.
    #[test]
    fn a_triangle_factors_nothing() {
        let mut names = Interner::new();
        let int = Type::int(32);
        let signature = Signature::new().with_params(&[int, int, int]);
        let mut func = Func::new(names.intern("f"), signature);
        let head = func.create_block();
        let left = func.append_param(head, int);
        let right = func.append_param(head, int);
        let operand = func.append_param(head, int);
        let arm = func.create_block();
        let join = func.create_block();
        let param = func.append_param(join, int);

        let mut build = Builder::new(&mut func, head);
        let shared = build.iconst(int, 3);
        let test = build.icmp(IntPred::Slt, left, right);
        build.br_if(test, arm, &[], join, &[operand]);
        let mut build = Builder::new(&mut func, arm);
        let it = build.binary(Opcode::Add, operand, shared, Flags::default());
        build.jump(join, &[it]);
        let mut build = Builder::new(&mut func, join);
        build.ret(&[param]);

        let stats = phiopt(&mut func);
        assert_eq!(stats.count(Kind::Optimized, super::FACTORED), 0);
        assert_eq!(stats.count(Kind::Optimized, super::CONVERTED), 1);
    }
}