rucc_opt/

libcall.rs

//! A call to the library, folded into the call it really is.
//!
//! Section 20.2 of `spec/optimizer/20-idioms-and-libcalls.md`, the half of it that is about a
//! library call rather than about arithmetic. `printf("hello world\n")` writes the same bytes as
//! `puts("hello world")`, and the second one does not read a format string at run time, so gcc
//! rewrites it and has done since 2000. A program that checks which of the two it was left with,
//! which is what `gcc.c-torture/execute/builtins/printf.c` does by defining a `printf` of its own
//! that aborts, fails outright on a compiler that leaves the call alone. tamnd/rucc#1636 is that
//! program and the two beside it.
//!
//! # The rules
//!
//! All of them measured against gcc 16.2.0 on x86-64 rather than read out of its source, and all of
//! them conditional on the format being a string this module holds the bytes of.
//!
//! `strstr(s, "")` is `s`, since the empty string is found at once wherever it is looked for.
//! `strstr(s, "w")` is `strchr(s, 'w')`, which is a search for a character rather than for a string
//! and is worth doing wherever the haystack came from. `strstr` of two strings this module holds is
//! the answer itself, which is a place in the haystack or a null pointer, and nothing is called.
//!
//! `strlen`, `strnlen`, `strcmp`, `strncmp`, `strchr`, `strrchr`, `memchr`, `strspn`, `strcspn` and
//! `strpbrk` of strings this module holds are the answer itself in the same way, which is a number
//! for the first four and the last two of the six that search, and a place in the first argument or
//! a null pointer for the other ones. The number goes in with the width the call was declared to
//! give back, because a program that declared `strlen` as something returning an `int` is a program
//! whose reader of that answer reads an `int`.
//!
//! Three of them have a rule about the shape rather than about the bytes. `strpbrk(s, "")` is a
//! null pointer and `strspn(s, "")` is zero, since nothing at all is in an empty set, and
//! `strcspn(s, "")` is `strlen(s)` for the same reason read the other way. `strpbrk(s, "c")` is
//! `strchr(s, 'c')`, which is the `strstr` rule again for a set of one character instead of a
//! needle of one.
//!
//! Two of them are told how far to read rather than going looking for a terminator, and those two
//! read the object's bytes rather than the string in it. `memchr(s, c, n)` needs the object to have
//! `n` bytes from `s` on, and it is refused where it does not, since a call reading past the end of
//! what the compiler can see is a call whose answer the compiler does not know. `strnlen(s, n)` is
//! the count where nothing terminated the string inside it.
//!
//! `printf` with the format alone: nothing at all when it is empty, `putchar` when it is one
//! character, and `puts` of the format without its last character when the format holds no `%` and
//! ends in a newline. `printf("%s\n", p)` is `puts(p)` and `printf("%c", c)` is `putchar(c)`,
//! whatever `p` and `c` are. `printf("%s", p)` where `p` is a string this module holds is the same
//! question again asked of that string, and where it is not, the call stays: `printf` has no stream
//! argument to hand to `fputs`, and `stdout` is not a name a compiler may invent.
//!
//! `fprintf` is the same list with a stream in hand, so the case `printf` cannot take is the case
//! this one can. A format holding no `%` becomes `fputc` of its one character or `fwrite` of the
//! whole of it, `fprintf(s, "%c", c)` becomes `fputc(c, s)`, and `fprintf(s, "%s", p)` becomes
//! `fputs(p, s)` however little is known about `p`.
//!
//! `fputs(p, s)` needs the length of `p` and nothing else. Zero is nothing at all, one is `fputc`
//! when the character is known as well, and anything longer is `fwrite(p, 1, len, s)`.
//!
//! The `_unlocked` spellings get the one fold that names no function, which is that a call writing
//! nothing is removed. gcc stops in exactly the same place and the reason is in the torture
//! program's own comment: a system need not have a `puts_unlocked` for the compiler to name.
//!
//! # What a call has to be
//!
//! For the printf family, its result has to be read by nothing. `printf` answers the number of
//! characters written and `puts` answers a non-negative number that is not that count, so a program
//! looking at the answer is a program this may not touch. The str and mem families are the other
//! way round: the answer is the whole point of the call and the fold produces it, so a program
//! reading it is the ordinary case.
//!
//! It has to give back one value of the kind its name says it does. A program that declared
//! `strchr` as something returning two values, or a number, declared a function of its own and a
//! pointer into a string literal is not what it answers.
//!
//! The name has to be the one the source spelled rather than the one the object file will carry.
//! `extern char *strstr (const char *, const char *) __asm ("my_strstr");` is a declaration of
//! `strstr`, and a compiler that reads the symbol alone sees a call to a function it knows nothing
//! about. So the callee is looked up through [`rucc_ir::Func::spelled`], and a call this leaves
//! behind is a call to whatever symbol the module says that name has, which is the rename again
//! read from the other end.
//!
//! The name has to be one this module does not define. A translation unit holding the body of its
//! own `fputs` means that body, which is the rule [`crate::heap`] applies to `malloc` and for the
//! same reason.
//!
//! The function must not carry memory SSA yet, which where this runs it does not. Memory is
//! threaded by [`crate::number`], that pass is in the function pipeline, and this runs before the
//! pipeline starts. The check is here anyway, because a call with a memory operand rewritten into
//! one without would be a use of a value nothing defines.
//!
//! # Where it runs, and why it is not a rule
//!
//! Section 20.2 asks for folds like these to be rules in the rewrite DSL with the callee's identity
//! in the pattern, and most of them can be. These cannot. A rule rewrites one instruction into
//! instructions, and two of the rewrites here need something no rule has: the name `puts` has to be
//! interned before a call can name it, and `printf("hello world\n")` has to leave behind a string
//! that is not in the module yet, because "hello world" with a terminator is not a suffix of
//! "hello world\n" with one. So this is a module at a time transformation beside [`crate::ipcp`]
//! and [`crate::ipasra`], which is where the interner and the module both are.
//!
//! `-O1` and above, which is one level below where those two run. gcc folds these at `-O1`, the
//! torture programs are compiled at every level from `-O1` up, and the fold makes the program
//! smaller as well as faster, so there is no level above `-O0` where declining it is right.
//!
//! Off under `-fno-builtin` and `-ffreestanding`, which is the flag pair section 20.1 describes,
//! and off for one name at a time under `-fno-builtin-<name>`. A freestanding program left with a
//! call to a `puts` it never wrote is a link failure, and that is the whole reason the flag exists.

use std::collections::{HashMap, HashSet};

use rucc_base::{Interner, Symbol};
use rucc_ir::{
    CallInfo, Datum, Def, Extra, Func, FuncId, Global, Imm, Inst, InstData, Linkage, Module,
    Opcode, Pic, Signature, SymbolRef, Type, Value,
};

use crate::extents::vouched;
use crate::{Cfg, Fuel, Stats, uses};

/// What the pass is called in `-fopt-info` and `-fpass-fuel=`.
pub const NAME: &str = "libcall";

/// How many block parameters deep the walk that answers "what string is this" goes.
///
/// A conditional expression whose arms are two literals is one level, which is what
/// `builtins/fputs.c` writes twice. Four is room for that nested three deep and is the bound that
/// stops a walk which would otherwise go round a loop forever. The same number bounds the walk
/// down a chain of `ptr_add`, where one level is one index written in the source.
const DEPTH: u32 = 4;

/// The names a fold may leave behind, sorted.
const REPLACEMENTS: [&str; 7] = ["fputc", "fputs", "fwrite", "putchar", "puts", "strchr", "strlen"];

/// The names a fold reads, sorted.
const SOURCES: [&str; 19] = [
    "fprintf",
    "fprintf_unlocked",
    "fputs",
    "fputs_unlocked",
    "index",
    "memchr",
    "printf",
    "printf_unlocked",
    "rindex",
    "strchr",
    "strcmp",
    "strcspn",
    "strlen",
    "strncmp",
    "strnlen",
    "strpbrk",
    "strrchr",
    "strspn",
    "strstr",
];

/// What the compiler worked out a call writes, which is what it is replaced by.
#[derive(Debug, Clone, PartialEq, Eq)]
enum Plan {
    /// It writes nothing, so it goes and nothing takes its place.
    Drop,
    /// The answer is a place in an argument the call was given, or nowhere at all, and that answer
    /// takes the place of the call's result.
    Answer(Answer),
    /// This call takes its place.
    Swap {
        /// The symbol the replacement names, which is what the module calls that function.
        callee: Symbol,
        /// What that function takes and returns.
        signature: Signature,
        /// What to pass it.
        args: Vec<Argument>,
    },
}

/// What a call that answers rather than writes was going to answer.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Answer {
    /// That many bytes along from a value the call was handed.
    Along(Value, u64),
    /// Nowhere in it, which is a null pointer.
    Nowhere,
    /// That number, in whatever type the call was declared to give back.
    ///
    /// The type is read off the call rather than worked out from the name, because a program that
    /// declared `strlen` as something returning an `int` gets an `int`, and a constant of the
    /// width the call already had is the only one that can take its place.
    Number(i128),
}

/// Which of the places a character appears in a string a search wants.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Side {
    /// `strchr`.
    First,
    /// `strrchr`.
    Last,
}

/// Which way round the test in a span is.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Set {
    /// `strspn`, which walks while the character is one of the set.
    Inside,
    /// `strcspn`, which walks while it is not.
    Outside,
}

/// One argument of a replacement call.
#[derive(Debug, Clone, PartialEq, Eq)]
enum Argument {
    /// A value the call being replaced already had.
    Have(Value),
    /// An `int` constant, which in every case here is a character.
    Char(u8),
    /// A `size_t` constant, which in every case here is a count of bytes.
    Count(u64),
    /// The address of a read only object holding these bytes and a terminator.
    Text(Vec<u8>),
}

/// What this module already says about each name a fold may leave behind.
///
/// The verifier holds that a call to a name the module declares carries that name's own signature,
/// so a program that declared `fwrite` through `<stdio.h>` decides what a call to it looks like and
/// a program that declared it as something else stops the fold. The alternative is a fold that
/// produces IR the verifier refuses, which is a compiler that crashes on a program gcc compiles.
struct Shapes {
    /// The symbol a call to that name has to carry and the signature it has to have, and `None`
    /// where no call may name it.
    held: HashMap<&'static str, Option<(Symbol, Signature)>>,
}

impl Shapes {
    /// Reads the module's answer for each of the names a fold may leave behind.
    fn of(module: &Module, names: &mut Interner) -> Self {
        let mut held: HashMap<&'static str, Option<(Symbol, Signature)>> = REPLACEMENTS
            .iter()
            .map(|&name| (name, Some((names.intern(name), canonical(module, name)))))
            .collect();
        for id in module.funcs() {
            // The name the source gave it, so that a module which renamed `puts` is left with a
            // call to the symbol it renamed it to rather than one to a `puts` it never declared.
            let func = &module[id];
            let spelled = func.spelled.unwrap_or(func.name);
            let Some(slot) = held.get_mut(names.resolve(spelled)) else { continue };
            let declared = func.signature();
            let agrees = slot.as_ref().is_some_and(|(_, want)| {
                !declared.variadic
                    && declared.param_types().eq(want.param_types())
                    && declared.return_types().eq(want.return_types())
            });
            *slot = agrees.then(|| (func.name, declared.clone()));
        }
        // A variable or a second name for something else is not a function to call, whatever it is
        // spelled.
        for id in module.globals() {
            if let Some(slot) = held.get_mut(names.resolve(module[id].name)) {
                *slot = None;
            }
        }
        for id in module.aliases() {
            if let Some(slot) = held.get_mut(names.resolve(module[id].name)) {
                *slot = None;
            }
        }
        Self { held }
    }

    /// What a call to that name carries, or `None` where this module does not allow one.
    fn get(&self, name: &'static str) -> Option<(Symbol, Signature)> {
        self.held.get(name)?.clone()
    }
}

/// The signature a call to that name carries where nothing in the module declared it.
///
/// What the frontend already writes, which is how `__builtin_putchar` reaches `putchar` in a
/// program that never named it.
fn canonical(module: &Module, name: &str) -> Signature {
    let int = int();
    let size = size(module);
    match name {
        "puts" => Signature::new().with_params(&[Type::PTR]).with_returns(&[int]),
        "putchar" => Signature::new().with_params(&[int]).with_returns(&[int]),
        "fputc" => Signature::new().with_params(&[int, Type::PTR]).with_returns(&[int]),
        "fputs" => Signature::new().with_params(&[Type::PTR, Type::PTR]).with_returns(&[int]),
        "strchr" => Signature::new().with_params(&[Type::PTR, int]).with_returns(&[Type::PTR]),
        "strlen" => Signature::new().with_params(&[Type::PTR]).with_returns(&[size]),
        // `fwrite`, the one that is told how many bytes to write rather than going looking for a
        // terminator, and the only one of the five whose types are the target's rather than fixed.
        _ => {
            Signature::new().with_params(&[Type::PTR, size, size, Type::PTR]).with_returns(&[size])
        }
    }
}

/// The type an `int` is in the IR.
///
/// Thirty two bits on every target this compiler has a back end for, which is why it is written
/// here rather than asked of the layout. The day one of them says otherwise, a fold under this rule
/// would hand `putchar` the wrong width, and this is the one place that would have to change.
const fn int() -> Type {
    Type::int(32)
}

/// The type a `size_t` is on the target this module is for.
fn size(module: &Module) -> Type {
    Type::int(module.datalayout.pointer_bits)
}

/// Folds every call in the module whose output the compiler can work out.
///
/// Gives back the functions that changed and what changed in them, which is what the pipeline turns
/// into `-fopt-info` remarks.
pub fn fold(
    module: &mut Module,
    names: &mut Interner,
    no_builtin: &[String],
    pic: Pic,
    fuel: &mut Fuel,
) -> Vec<(FuncId, Stats)> {
    let shapes = Shapes::of(module, names);
    // What each symbol was called in the source, for the declarations where the two differ. A call
    // names a symbol, and a symbol an assembler name replaced says nothing about which library
    // function it is, so this is what the two names are put back together through.
    let standard: HashMap<Symbol, Symbol> =
        module.funcs().filter_map(|id| Some((module[id].name, module[id].spelled?))).collect();
    // A module that defines one of these names itself is where that function comes from, and what a
    // function called `fputs` does in there is whatever it was written to do.
    let defined: HashSet<Symbol> = module
        .funcs()
        .filter(|&id| !module[id].is_declaration())
        .map(|id| module[id].name)
        .collect();
    // One table for the module rather than one per function, so that two calls folded to the same
    // string share one object instead of each getting one of its own.
    let mut texts: HashMap<Vec<u8>, Symbol> = HashMap::new();
    let mut done = Vec::new();
    for id in module.funcs().collect::<Vec<FuncId>>() {
        // A function with none of these names in it is most of them, and the answer for one is a
        // walk over its instructions that allocates nothing. The two tables below are a vector and
        // a predecessor list per block, which is a cost worth not paying over a module whose
        // functions print nothing.
        if module[id].is_declaration() || !mentions(&module[id], names, &standard) {
            continue;
        }
        let mut stats = Stats::new();
        // The whole body is read before any of it changes. A plan names values the body holds, and
        // working the next one out from a body half rewritten is how a pass comes to read a value
        // whose definition it has just taken away.
        let plans = {
            let func = &module[id];
            let site = Site {
                module,
                func,
                cfg: &Cfg::new(func),
                shapes: &shapes,
                counts: &uses::count(func),
                defined: &defined,
                standard: &standard,
                names,
                no_builtin,
                pic,
            };
            site.survey(fuel, &mut stats)
        };
        for (inst, plan) in plans {
            apply(module, id, names, &mut texts, inst, plan);
        }
        if stats.changed() {
            done.push((id, stats));
        }
    }
    done
}

/// Whether this function calls any of the names a fold reads.
fn mentions(func: &Func, names: &Interner, standard: &HashMap<Symbol, Symbol>) -> bool {
    func.blocks().flat_map(|block| func.insts(block)).any(|inst| {
        let data = &func[inst];
        let Extra::Call(at) = data.extra else { return false };
        data.opcode == Opcode::Call
            && func[at].callee.is_some_and(|callee| {
                let spelled = standard.get(&callee).copied().unwrap_or(callee);
                SOURCES.contains(&names.resolve(spelled))
            })
    })
}

/// One function and everything reading it takes to answer what a call in it writes.
struct Site<'a> {
    /// The module it is in, which is where a string literal's bytes are.
    module: &'a Module,
    /// The function.
    func: &'a Func,
    /// Its shape, which is what a block parameter's arguments are found through.
    cfg: &'a Cfg,
    /// What the module allows a replacement call to look like.
    shapes: &'a Shapes,
    /// How many times each value is read, which is what says a result is ignored.
    counts: &'a [u32],
    /// The names this module defines bodies for.
    defined: &'a HashSet<Symbol>,
    /// What each renamed symbol was called in the source.
    standard: &'a HashMap<Symbol, Symbol>,
    /// The spellings, for reading a callee's name.
    names: &'a Interner,
    /// The names `-fno-builtin-<name>` took away.
    no_builtin: &'a [String],
    /// Which definitions something else may replace at load time.
    pic: Pic,
}

impl Site<'_> {
    /// Every call in this function that has a plan, with the plan.
    fn survey(&self, fuel: &mut Fuel, stats: &mut Stats) -> Vec<(Inst, Plan)> {
        let mut plans = Vec::new();
        for block in self.func.blocks().collect::<Vec<_>>() {
            for inst in self.func.insts(block).collect::<Vec<Inst>>() {
                let Some(plan) = self.plan(inst) else { continue };
                if !fuel.take() {
                    stats.missed("call to the library folded");
                    continue;
                }
                stats.optimized(match &plan {
                    Plan::Drop => "call to the library that writes nothing removed",
                    Plan::Answer(_) => "call to the library whose answer is known folded",
                    Plan::Swap { .. } => "call to the library folded",
                });
                plans.push((inst, plan));
            }
        }
        plans
    }

    /// What this call writes, where it is one of the calls this knows and the answer can be worked
    /// out.
    fn plan(&self, inst: Inst) -> Option<Plan> {
        let data = &self.func[inst];
        if data.opcode != Opcode::Call || self.func.mem_in(inst).is_some() {
            return None;
        }
        // A program looking at how many characters went out is a program the count matters to, and
        // no two of the printf family answer the same number. `strstr` is not in that position: its
        // answer is what the call is for and the fold produces the same one.
        let ignored = data.results().all(|result| self.counts[result.index()] == 0);
        let Extra::Call(at) = data.extra else { return None };
        let callee = self.func[at].callee?;
        if self.defined.contains(&callee) {
            return None;
        }
        let name = self.names.resolve(self.standard.get(&callee).copied().unwrap_or(callee));
        if self.no_builtin.iter().any(|it| it == name) {
            return None;
        }
        let args: Vec<Value> = self.func[data.args].to_vec();
        // The locked and the unlocked spellings take the same arguments and differ only in how far
        // the fold may go, so they are an arm each with a flag rather than two bodies.
        match name {
            "printf" if ignored => self.printf(&args, false),
            "printf_unlocked" if ignored => self.printf(&args, true),
            "fprintf" if ignored => self.fprintf(&args, false),
            "fprintf_unlocked" if ignored => self.fprintf(&args, true),
            "fputs" if ignored => self.fputs(&args, false),
            "fputs_unlocked" if ignored => self.fputs(&args, true),
            "strstr" => self.strstr(data, &args),
            // `index` and `rindex` are the older spellings of the same two searches, and a
            // program that wrote one of them is asking for the same answer.
            "strchr" | "index" => self.strchr(data, &args, Side::First),
            "strrchr" | "rindex" => self.strchr(data, &args, Side::Last),
            "memchr" => self.memchr(data, &args),
            "strlen" => self.strlen(data, &args),
            "strnlen" => self.strnlen(data, &args),
            "strcmp" => self.strcmp(data, &args),
            "strncmp" => self.strncmp(data, &args),
            "strcspn" => self.span(data, &args, Set::Outside),
            "strspn" => self.span(data, &args, Set::Inside),
            "strpbrk" => self.strpbrk(data, &args),
            _ => None,
        }
    }

    /// The type this call's one result has, where it has one and it is an integer.
    ///
    /// A declaration of another shape is a function of the program's own, and a number is not what
    /// it answers.
    fn answers(&self, data: &InstData) -> Option<Type> {
        let mut results = data.results();
        let ty = self.func[results.next()?].ty;
        (results.next().is_none() && ty.is_int() && !ty.is_vector()).then_some(ty)
    }

    /// Whether this call's one result is a pointer, which every search for a place gives back.
    fn places(&self, data: &InstData) -> bool {
        let mut results = data.results();
        results.next().is_some_and(|result| self.func[result].ty == Type::PTR)
            && results.next().is_none()
    }

    /// The character a search was told to look for, which the call carries as an `int` and the
    /// library reads as a `char`.
    fn character(&self, value: Value) -> Option<u8> {
        let (imm, ty) = crate::fold::constant(self.func, value)?;
        u8::try_from(imm.signed(ty).rem_euclid(256)).ok()
    }

    /// A count of bytes the call was given, which has to be a constant that fits a `usize`.
    ///
    /// The source writes a small count as an `int` and the call takes a `size_t`, so what the
    /// argument holds is a widening of the constant rather than the constant, and reading only the
    /// argument would miss every count anyone actually writes.
    fn count(&self, value: Value) -> Option<usize> {
        let narrow = self.widened(value);
        let (imm, ty) = crate::fold::constant(self.func, narrow)?;
        // A count the source wrote as a negative number is not a count, whatever the conversion
        // makes of it, and folding on one would be reading an object that is not there.
        (narrow == value || imm.signed(ty) >= 0).then_some(())?;
        usize::try_from(imm.unsigned()).ok()
    }

    /// What this value is a widening of, or the value itself where it is not one.
    ///
    /// Both conversions leave a non negative constant alone, so which one it was only matters for
    /// refusing a negative one, and the caller is the one that does that.
    fn widened(&self, value: Value) -> Value {
        let Def::Result { inst, .. } = self.func[value].def else { return value };
        if !matches!(self.func[inst].opcode, Opcode::SExt | Opcode::ZExt) {
            return value;
        }
        self.func[self.func[inst].args].first().copied().unwrap_or(value)
    }

    /// Where a `strchr` or a `strrchr` finds its character.
    ///
    /// A terminator is found at the end of the string rather than not at all, which is what makes
    /// `strchr(s, 0)` the address of the terminator and is the one place the bytes this reads and
    /// the string it is searching are not the same length.
    fn strchr(&self, data: &InstData, args: &[Value], side: Side) -> Option<Plan> {
        if args.len() != 2 || self.func[args[0]].ty != Type::PTR || !self.places(data) {
            return None;
        }
        let wanted = self.character(args[1])?;
        let Some(text) = self.one(args[0]) else {
            // A string has one terminator in it, so looking for that one from the right finds the
            // same place as looking for it from the left, and which end the walk started at stops
            // mattering. That is an answer even where nothing at all is known about the string.
            return match (wanted, side) {
                (0, Side::Last) => {
                    self.call("strchr", vec![Argument::Have(args[0]), Argument::Char(0)])
                }
                _ => None,
            };
        };
        let found = match (wanted, side) {
            (0, _) => Some(text.len()),
            (_, Side::First) => text.iter().position(|&byte| byte == wanted),
            (_, Side::Last) => text.iter().rposition(|&byte| byte == wanted),
        };
        Some(Plan::Answer(match found {
            Some(at) => Answer::Along(args[0], u64::try_from(at).ok()?),
            None => Answer::Nowhere,
        }))
    }

    /// Where a `memchr` finds its character, which is a search over a count rather than up to a
    /// terminator.
    ///
    /// So this reads the object's bytes rather than the string in it, and it refuses a count the
    /// object does not have that many bytes for, since a call that reads past the end of what the
    /// compiler can see is a call whose answer the compiler does not know.
    fn memchr(&self, data: &InstData, args: &[Value]) -> Option<Plan> {
        (args.len() == 3).then_some(())?; // not a threshold: `memchr` takes three arguments.
        if self.func[args[0]].ty != Type::PTR || !self.places(data) {
            return None;
        }
        let wanted = self.character(args[1])?;
        let count = self.count(args[2])?;
        let bytes = self.raw(args[0])?;
        let window = bytes.get(..count)?;
        Some(Plan::Answer(match window.iter().position(|&byte| byte == wanted) {
            Some(at) => Answer::Along(args[0], u64::try_from(at).ok()?),
            None => Answer::Nowhere,
        }))
    }

    /// How long a string this module holds is.
    fn strlen(&self, data: &InstData, args: &[Value]) -> Option<Plan> {
        if args.len() != 1 || self.func[args[0]].ty != Type::PTR {
            return None;
        }
        self.answers(data)?;
        let text = self.one(args[0])?;
        Some(Plan::Answer(Answer::Number(i128::try_from(text.len()).ok()?)))
    }

    /// The same, stopping at a count.
    ///
    /// A string with no terminator inside the count is the count, and that needs the object's bytes
    /// rather than the string in it, because there may be no string in it at all.
    fn strnlen(&self, data: &InstData, args: &[Value]) -> Option<Plan> {
        if args.len() != 2 || self.func[args[0]].ty != Type::PTR {
            return None;
        }
        self.answers(data)?;
        let count = self.count(args[1])?;
        let bytes = self.raw(args[0])?;
        let window = bytes.get(..count.min(bytes.len()))?;
        let len = match window.iter().position(|&byte| byte == 0) {
            Some(at) => at,
            // Nothing terminated it inside the window, so the answer is the count only where the
            // window was the whole count.
            None if window.len() == count => count,
            None => return None,
        };
        Some(Plan::Answer(Answer::Number(i128::try_from(len).ok()?)))
    }

    /// How two strings this module holds compare.
    fn strcmp(&self, data: &InstData, args: &[Value]) -> Option<Plan> {
        (args.len() == 2).then_some(())?;
        self.compared(data, args, usize::MAX)
    }

    /// The same over a count the call was given, which has to be a constant.
    fn strncmp(&self, data: &InstData, args: &[Value]) -> Option<Plan> {
        (args.len() == 3).then_some(())?; // not a threshold: `strncmp` takes three arguments.
        let count = self.count(args[2])?;
        self.compared(data, args, count)
    }

    /// The comparison both of them are, over however many bytes each is allowed to read.
    ///
    /// The sign is what the standard promises and the magnitude is not, so this answers one of
    /// minus one, zero and one, which is what gcc leaves behind as well.
    fn compared(&self, data: &InstData, args: &[Value], bound: usize) -> Option<Plan> {
        if self.func[args[0]].ty != Type::PTR || self.func[args[1]].ty != Type::PTR {
            return None;
        }
        self.answers(data)?;
        let (mut left, mut right) = (self.one(args[0])?, self.one(args[1])?);
        // The terminator is part of the comparison, since it is what stops one string before the
        // other and it is smaller than every byte that could be opposite it.
        left.push(0);
        right.push(0);
        let mut answer = 0;
        for at in 0..bound.min(left.len()).min(right.len()) {
            if left[at] != right[at] {
                answer = if left[at] < right[at] { -1 } else { 1 };
                break;
            }
            if left[at] == 0 {
                break;
            }
        }
        Some(Plan::Answer(Answer::Number(answer)))
    }

    /// How far into the first string the second one's characters start, or stop.
    ///
    /// `strcspn` walks while the character is outside the set and `strspn` walks while it is
    /// inside, which is one walk with the test turned round, and the shape rules fall out of it:
    /// nothing is outside an empty set, so `strspn(s, "")` is zero, and everything is, so
    /// `strcspn(s, "")` is the length of `s`.
    fn span(&self, data: &InstData, args: &[Value], set: Set) -> Option<Plan> {
        if args.len() != 2
            || self.func[args[0]].ty != Type::PTR
            || self.func[args[1]].ty != Type::PTR
        {
            return None;
        }
        let ty = self.answers(data)?;
        // An empty first string is no bytes to walk over, whatever the set is, and that is the
        // answer `strcspn("", s)` wants where nothing is known about `s`.
        if let Some(text) = self.one(args[0])
            && text.is_empty()
        {
            return Some(Plan::Answer(Answer::Number(0)));
        }
        let accept = self.one(args[1])?;
        // Both walks are the same walk with the test turned round, and an empty set needs no arm of
        // its own here, because nothing is inside one and so the walk stops at once or not at all.
        if let Some(text) = self.one(args[0]) {
            let len = text
                .iter()
                .position(|byte| accept.contains(byte) != matches!(set, Set::Inside))
                .unwrap_or(text.len());
            return Some(Plan::Answer(Answer::Number(i128::try_from(len).ok()?)));
        }
        // Nothing is known about the string, so only the shape rules are left.
        accept.is_empty().then_some(())?;
        match set {
            Set::Inside => Some(Plan::Answer(Answer::Number(0))),
            // A number the call gives back and a number `strlen` gives back have to be the same
            // width, since what reads the first is going to read the second and nothing here writes
            // a conversion.
            Set::Outside => {
                let (_, signature) = self.shapes.get("strlen")?;
                signature.return_types().eq([ty]).then_some(())?;
                self.call("strlen", vec![Argument::Have(args[0])])
            }
        }
    }

    /// Where the first character of one string that is in the other is.
    fn strpbrk(&self, data: &InstData, args: &[Value]) -> Option<Plan> {
        if args.len() != 2 || self.func[args[0]].ty != Type::PTR || !self.places(data) {
            return None;
        }
        if self.func[args[1]].ty != Type::PTR {
            return None;
        }
        let accept = self.one(args[1])?;
        // Nothing is in an empty set, so the search runs off the end of any string at all.
        if accept.is_empty() {
            return Some(Plan::Answer(Answer::Nowhere));
        }
        match self.one(args[0]) {
            Some(text) => {
                Some(Plan::Answer(match text.iter().position(|byte| accept.contains(byte)) {
                    Some(at) => Answer::Along(args[0], u64::try_from(at).ok()?),
                    None => Answer::Nowhere,
                }))
            }
            // A set of one character is a search for that character, which is the same fold
            // `strstr` of a needle of one character gets.
            None => match accept.as_slice() {
                [one] => self.call("strchr", vec![Argument::Have(args[0]), Argument::Char(*one)]),
                _ => None,
            },
        }
    }

    /// Where a `strstr` finds what it was told to look for.
    ///
    /// The three folds gcc has for it, and the order matters: two strings this module holds are an
    /// answer, and a haystack nothing is known about is a search for a character where the needle is
    /// one character long.
    fn strstr(&self, data: &InstData, args: &[Value]) -> Option<Plan> {
        if args.len() != 2 {
            return None;
        }
        let (haystack, needle) = (args[0], args[1]);
        if self.func[haystack].ty != Type::PTR || self.func[needle].ty != Type::PTR {
            return None;
        }
        // A declaration of another shape is a function of the program's own, and the answer this
        // produces is a pointer whatever the program said the call gives back.
        let mut results = data.results();
        if !results.next().is_some_and(|result| self.func[result].ty == Type::PTR)
            || results.next().is_some()
        {
            return None;
        }
        let needle = self.one(needle)?;
        // The empty string is found at once, wherever it is looked for and whatever is there.
        if needle.is_empty() {
            return Some(Plan::Answer(Answer::Along(haystack, 0)));
        }
        match self.one(haystack) {
            Some(hay) => Some(Plan::Answer(match at(&hay, &needle) {
                Some(found) => Answer::Along(haystack, u64::try_from(found).ok()?),
                None => Answer::Nowhere,
            })),
            // A needle of one character is a search for that character, which is a smaller function
            // and is worth doing wherever the haystack came from.
            None => match needle.as_slice() {
                [one] => self.call("strchr", vec![Argument::Have(haystack), Argument::Char(*one)]),
                _ => None,
            },
        }
    }

    /// What a `printf` writes.
    fn printf(&self, args: &[Value], quiet: bool) -> Option<Plan> {
        let format = self.one(*args.first()?)?;
        match args.len() {
            1 => self.plain(&format, None, quiet),
            2 if format == b"%s\n" && !quiet && self.func[args[1]].ty == Type::PTR => {
                self.call("puts", vec![Argument::Have(args[1])])
            }
            2 if format == b"%c" && !quiet && self.func[args[1]].ty == int() => {
                self.call("putchar", vec![Argument::Have(args[1])])
            }
            // The same question asked again of the argument, because what `printf("%s", p)` writes
            // is what `printf(p)` writes for a `p` holding no `%`. A `p` that does hold one is left
            // alone here and folded by gcc, which is a missed fold and not a wrong answer.
            2 if format == b"%s" => self.plain(&self.one(args[1])?, None, quiet),
            _ => None,
        }
    }

    /// What an `fprintf` writes.
    fn fprintf(&self, args: &[Value], quiet: bool) -> Option<Plan> {
        let stream = *args.first()?;
        if self.func[stream].ty != Type::PTR {
            return None;
        }
        let format = self.one(*args.get(1)?)?;
        match args.len() {
            2 => self.plain(&format, Some((args[1], stream)), quiet),
            3 if format == b"%c" && !quiet && self.func[args[2]].ty == int() => {
                self.call("fputc", vec![Argument::Have(args[2]), Argument::Have(stream)])
            }
            // Whatever is known about the argument, which is the fold `printf` cannot have: this
            // one holds the stream, so the call it leaves behind is one the program could have
            // written for itself.
            3 if format == b"%s" && self.func[args[2]].ty == Type::PTR => {
                match self.strings(args[2], DEPTH) {
                    Some(candidates) => self.string(&candidates, args[2], stream, quiet),
                    None if quiet => None,
                    None => {
                        self.call("fputs", vec![Argument::Have(args[2]), Argument::Have(stream)])
                    }
                }
            }
            _ => None,
        }
    }

    /// What an `fputs` writes.
    fn fputs(&self, args: &[Value], quiet: bool) -> Option<Plan> {
        if args.len() != 2 {
            return None;
        }
        let (text, stream) = (args[0], args[1]);
        if self.func[text].ty != Type::PTR || self.func[stream].ty != Type::PTR {
            return None;
        }
        self.string(&self.strings(text, DEPTH)?, text, stream, quiet)
    }

    /// What a format holding no `%` writes, given the stream to write it to or nothing.
    ///
    /// The empty case comes first and is the one an unlocked spelling is allowed, because a call
    /// writing nothing is removed without naming any function at all.
    fn plain(&self, format: &[u8], stream: Option<(Value, Value)>, quiet: bool) -> Option<Plan> {
        if format.is_empty() {
            return Some(Plan::Drop);
        }
        if quiet || format.contains(&b'%') {
            return None;
        }
        match (format, stream) {
            ([one], Some((_, stream))) => {
                self.call("fputc", vec![Argument::Char(*one), Argument::Have(stream)])
            }
            // Anything longer takes the whole format, since `fwrite` is told how many bytes to
            // write and does not go looking for a terminator.
            (_, Some((text, stream))) => self.fwrite(Argument::Have(text), format.len(), stream),
            ([one], None) => self.call("putchar", vec![Argument::Char(*one)]),
            // `puts` writes a newline of its own, so what it has to be given is the format without
            // its last character, and that is a string the module does not hold yet.
            (_, None) => {
                let (&last, rest) = format.split_last()?;
                match last {
                    b'\n' => self.call("puts", vec![Argument::Text(rest.to_vec())]),
                    _ => None,
                }
            }
        }
    }

    /// What writing this string to this stream is, given every string the pointer may point at.
    ///
    /// The candidates have to agree on their length, because the length is what decides which call
    /// this becomes. They need not agree on their contents unless the length is one, where the
    /// character itself is an argument.
    fn string(
        &self,
        candidates: &[Vec<u8>],
        text: Value,
        stream: Value,
        quiet: bool,
    ) -> Option<Plan> {
        let first = candidates.first()?;
        if candidates.iter().any(|it| it.len() != first.len()) {
            return None;
        }
        if first.is_empty() {
            return Some(Plan::Drop);
        }
        if quiet {
            return None;
        }
        match first.as_slice() {
            [one] if candidates.iter().all(|it| it[0] == *one) => {
                self.call("fputc", vec![Argument::Char(*one), Argument::Have(stream)])
            }
            // A length of one that two candidates disagree about is an `fwrite` of one byte, since
            // the byte itself is not a constant here and the pointer is what has to be written.
            // That is gcc's answer too, and its output for this is a conditional move feeding an
            // `fwrite` of one.
            _ => self.fwrite(Argument::Have(text), first.len(), stream),
        }
    }

    /// An `fwrite` of that many bytes from that address.
    fn fwrite(&self, text: Argument, bytes: usize, stream: Value) -> Option<Plan> {
        let len = u64::try_from(bytes).ok()?;
        self.call(
            "fwrite",
            vec![text, Argument::Count(1), Argument::Count(len), Argument::Have(stream)],
        )
    }

    /// A call to that name, or nothing where this module does not allow one.
    fn call(&self, callee: &'static str, args: Vec<Argument>) -> Option<Plan> {
        let (callee, signature) = self.shapes.get(callee)?;
        Some(Plan::Swap { callee, signature, args })
    }

    /// The one string this value points at, or `None` where there is more than one of them.
    fn one(&self, value: Value) -> Option<Vec<u8>> {
        let mut candidates = self.strings(value, DEPTH)?;
        (candidates.len() == 1).then(|| candidates.pop()).flatten()
    }

    /// Every string this value may point at, or `None` where any of them is not one this module
    /// holds.
    ///
    /// A block parameter is every argument every branch to that block passes, which is how the
    /// conditional expression in `builtins/fputs.c` gets a length without anything having turned it
    /// into a `select` first. `depth` is what stops the walk on a loop, where a parameter's
    /// argument is the parameter.
    fn strings(&self, value: Value, depth: u32) -> Option<Vec<Vec<u8>>> {
        if depth == 0 {
            return None;
        }
        match self.func[value].def {
            Def::Param { block, index } => {
                let preds = self.cfg.predecessors(block);
                if preds.is_empty() {
                    return None;
                }
                let mut all = Vec::new();
                for &pred in preds {
                    let term = self.func.terminator(pred)?;
                    for call in self.func.successors(term).collect::<Vec<_>>() {
                        if call.block != block {
                            continue;
                        }
                        let arg = *self.func[call.args].get(index as usize)?;
                        all.extend(self.strings(arg, depth - 1)?);
                    }
                }
                (!all.is_empty()).then_some(all)
            }
            Def::Result { inst, .. } if self.func[inst].opcode == Opcode::Select => {
                let args = &self.func[self.func[inst].args];
                let (then, other) = (*args.get(1)?, *args.get(2)?);
                let mut all = self.strings(then, depth - 1)?;
                all.extend(self.strings(other, depth - 1)?);
                Some(all)
            }
            _ => Some(vec![self.literal(value)?]),
        }
    }

    /// The bytes up to the first terminator at the address this value is, where that address is
    /// inside a read only object this module vouches for.
    fn literal(&self, value: Value) -> Option<Vec<u8>> {
        let bytes = self.raw(value)?;
        let end = bytes.iter().position(|&byte| byte == 0)?;
        Some(bytes[..end].to_vec())
    }

    /// Every byte from the address this value is to the end of the object it is in.
    ///
    /// The same walk as above with nothing stopping it at a terminator, because `memchr` is told
    /// how far to read rather than going looking for one, and `strnlen` may be told to stop before
    /// there is one. A caller that wants a string wants [`Self::literal`] instead.
    fn raw(&self, value: Value) -> Option<Vec<u8>> {
        let (base, offset) = self.address(value)?;
        let Def::Result { inst, .. } = self.func[base].def else { return None };
        if self.func[inst].opcode != Opcode::GlobalAddr {
            return None;
        }
        let Extra::Symbol(name) = self.func[inst].extra else { return None };
        let Some(SymbolRef::Global(id)) = self.module.lookup(name) else { return None };
        let global = &self.module[id];
        if !global.constant || !vouched(global, self.pic) {
            return None;
        }
        let mut bytes = Vec::new();
        for &datum in &self.module[global.init?] {
            match datum {
                Datum::Bytes(range) => bytes.extend_from_slice(&self.module[range]),
                Datum::Zero(count) => {
                    bytes.resize(bytes.len().checked_add(usize::try_from(count).ok()?)?, 0);
                }
                // A number written in the target's byte order, or an address the linker has not
                // filled in. Neither is a byte this can read, and what follows one is at an offset
                // that is right only if this one's width is, so the walk stops.
                Datum::Scalar { .. } | Datum::Addr(_) | Datum::Away(_) => return None,
            }
        }
        // An object whose image stops short of its size is zero from there on, which is what an
        // array with fewer initializers than members is and is a byte a search may reach.
        let size = usize::try_from(global.size).ok()?;
        if bytes.len() < size {
            bytes.resize(size, 0);
        }
        Some(bytes.get(usize::try_from(offset).ok()?..)?.to_vec())
    }

    /// The address this value is, as something it was computed from and a distance in bytes from
    /// it.
    ///
    /// The same walk [`crate::image`] does down a chain of `ptr_add` of a constant, because an
    /// index into a string literal is one of these and the frontend writes one per index.
    fn address(&self, mut value: Value) -> Option<(Value, i128)> {
        let mut offset: i128 = 0;
        for _ in 0..DEPTH {
            let Def::Result { inst, .. } = self.func[value].def else {
                return Some((value, offset));
            };
            if self.func[inst].opcode != Opcode::PtrAdd {
                return Some((value, offset));
            }
            let args = &self.func[self.func[inst].args];
            offset = offset.checked_add(self.step(*args.get(1)?)?)?;
            value = *args.first()?;
        }
        None
    }

    /// The constant this value is, looking through a widening of one.
    ///
    /// An index into an array is an `int` where the source wrote one, and a pointer is sixty four
    /// bits, so what the frontend leaves in front of a `ptr_add` is a `sext` of a constant rather
    /// than a constant. This runs before anything has folded that, since everything that would is
    /// one function at a time and the function pipeline has not started, so the walk above would
    /// stop at the first index written in the source without this.
    fn step(&self, mut value: Value) -> Option<i128> {
        for _ in 0..DEPTH {
            if let Some((imm, ty)) = crate::fold::constant(self.func, value) {
                return Some(imm.signed(ty));
            }
            let Def::Result { inst, .. } = self.func[value].def else { return None };
            match self.func[inst].opcode {
                // The narrow value read the way the widening reads it, which for the signed one is
                // the same number and for the unsigned one is the same number only where it was
                // not negative.
                Opcode::SExt => value = *self.func[self.func[inst].args].first()?,
                Opcode::ZExt => {
                    let arg = *self.func[self.func[inst].args].first()?;
                    let (imm, _) = crate::fold::constant(self.func, arg)?;
                    return i128::try_from(imm.unsigned()).ok();
                }
                _ => return None,
            }
        }
        None
    }
}

/// Writes one plan into the function.
fn apply(
    module: &mut Module,
    id: FuncId,
    names: &mut Interner,
    texts: &mut HashMap<Vec<u8>, Symbol>,
    inst: Inst,
    plan: Plan,
) {
    let (callee, signature, args) = match plan {
        Plan::Drop => {
            module[id].remove_inst(inst);
            return;
        }
        Plan::Answer(answer) => {
            let width = size(module);
            answered(&mut module[id], inst, answer, width);
            return;
        }
        Plan::Swap { callee, signature, args } => (callee, signature, args),
    };
    // The objects first, because a string the fold prints belongs to the module and the module is
    // what the function is reached through.
    let symbols: Vec<Option<Symbol>> = args
        .iter()
        .map(|arg| match arg {
            Argument::Text(bytes) => Some(object(module, names, texts, bytes)),
            _ => None,
        })
        .collect();
    let width = size(module);
    let func = &mut module[id];
    let span = func.span(inst);
    let mut values = Vec::with_capacity(args.len());
    for (arg, symbol) in args.iter().zip(symbols) {
        values.push(match arg {
            Argument::Have(value) => *value,
            Argument::Char(byte) => constant(func, inst, int(), i128::from(*byte)),
            Argument::Count(count) => constant(func, inst, width, i128::from(*count)),
            Argument::Text(_) => {
                let extra = Extra::Symbol(symbol.expect("a text argument has an object"));
                let data = InstData { extra, ..InstData::new(Opcode::GlobalAddr) };
                let made = func.create_inst(data, &[Type::PTR], span);
                func.insert_before(made, inst);
                func[made].results().next().expect("an address is one value")
            }
        });
    }
    let results: Vec<Type> = signature.return_types().collect();
    let sig = func.add_signature(signature);
    let varargs = func.push_abis(&[]);
    let info = func.add_call(CallInfo { callee: Some(callee), signature: sig, varargs });
    let args = func.push_values(&values);
    let data = InstData { args, extra: Extra::Call(info), ..InstData::new(Opcode::Call) };
    let made = func.create_inst(data, &results, span);
    func.insert_before(made, inst);
    // Whoever read the old call's answer reads the new one's, where the two are the same kind of
    // thing. The printf family is folded only where nothing read it, so the map is empty there and
    // this costs a walk over a function that is about to be walked anyway.
    let forward: HashMap<Value, Value> = func[inst]
        .results()
        .zip(func[made].results().collect::<Vec<Value>>())
        .filter(|&(from, to)| func[from].ty == func[to].ty)
        .collect();
    if !forward.is_empty() {
        uses::substitute(func, &forward);
    }
    func.remove_inst(inst);
}

/// Writes the answer a search worked out in place of the call that would have worked it out.
fn answered(func: &mut Func, inst: Inst, answer: Answer, width: Type) {
    let span = func.span(inst);
    let value = match answer {
        // The haystack itself, which is what a search for the empty string finds and what a search
        // that found its needle at the front of one finds. No instruction at all for either.
        Answer::Along(haystack, 0) => haystack,
        Answer::Along(haystack, by) => {
            let step = constant(func, inst, width, i128::from(by));
            let args = func.push_values(&[haystack, step]);
            let data = InstData { args, ..InstData::new(Opcode::PtrAdd) };
            let made = func.create_inst(data, &[Type::PTR], span);
            func.insert_before(made, inst);
            func[made].results().next().expect("an address is one value")
        }
        Answer::Nowhere => {
            let zero = constant(func, inst, width, 0);
            let args = func.push_values(&[zero]);
            let data = InstData { args, ..InstData::new(Opcode::IntToPtr) };
            let made = func.create_inst(data, &[Type::PTR], span);
            func.insert_before(made, inst);
            func[made].results().next().expect("a null pointer is one value")
        }
        Answer::Number(number) => {
            let ty = func[inst]
                .results()
                .next()
                .map(|result| func[result].ty)
                .expect("a call whose answer is a number has one");
            constant(func, inst, ty, number)
        }
    };
    let forward: HashMap<Value, Value> =
        func[inst].results().map(|result| (result, value)).collect();
    uses::substitute(func, &forward);
    func.remove_inst(inst);
}

/// Where the second string is inside the first, in bytes from its front.
fn at(haystack: &[u8], needle: &[u8]) -> Option<usize> {
    haystack.windows(needle.len()).position(|window| window == needle)
}

/// An integer constant of that type, put in front of the call being replaced.
fn constant(func: &mut Func, before: Inst, ty: Type, value: i128) -> Value {
    let span = func.span(before);
    let imm = func.add_imm(Imm::int(value, ty.lane()));
    let data = InstData { extra: Extra::Imm(imm), ..InstData::new(Opcode::IConst) };
    let made = func.create_inst(data, &[ty], span);
    func.insert_before(made, before);
    func[made].results().next().expect("a constant is one value")
}

/// The read only object holding these bytes and a terminator, making it the first time it is asked
/// for.
///
/// `.Lfold` rather than `.Lstr`, so that this numbering and the frontend's cannot meet, and a
/// number past the end of the table in the case where a program has named one of these itself.
fn object(
    module: &mut Module,
    names: &mut Interner,
    texts: &mut HashMap<Vec<u8>, Symbol>,
    bytes: &[u8],
) -> Symbol {
    if let Some(&symbol) = texts.get(bytes) {
        return symbol;
    }
    let mut image = bytes.to_vec();
    image.push(0);
    let mut symbol = names.intern(&format!(".Lfold.{}", texts.len()));
    for next in texts.len().. {
        if module.lookup(symbol).is_none() {
            break;
        }
        symbol = names.intern(&format!(".Lfold.{}", next + 1));
    }
    let mut global = Global::new(symbol, image.len() as u64, 1);
    global.linkage = Linkage::Internal;
    global.constant = true;
    let range = module.push_bytes(&image);
    global.init = Some(module.push_data(&[Datum::Bytes(range)]));
    module.add_global(global);
    texts.insert(bytes.to_vec(), symbol);
    symbol
}

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

    /// What every fixture below starts with, which is the target the counts and widths are of.
    const HEAD: &str = "\
; ModuleID = 't.c'
; format 0
target triple = \"x86_64-unknown-linux-gnu\"
target datalayout = \"e-p:64:64-i64:64-f80:128-S128\"
";

    /// The module that text is, folded, printed, and checked by the verifier on the way out.
    ///
    /// Printing it rather than walking it, because what a reader of one of these tests wants to
    /// know is what the function ended up being, and a chain of accessors says that less clearly
    /// than the line it produces.
    fn folded(body: &str) -> String {
        run(body, &[], &mut Fuel::unlimited())
    }

    /// The same, under whatever `-fno-builtin-<name>` and fuel the test wants.
    fn run(body: &str, no_builtin: &[String], fuel: &mut Fuel) -> String {
        let mut names = Interner::new();
        let text = format!("{HEAD}{body}");
        let mut module = rucc_ir::parse(&text, &mut names).expect("the fixture parses");
        fold(&mut module, &mut names, no_builtin, Pic::Executable, fuel);
        if let Err(errors) = rucc_ir::verify(&module, &names) {
            panic!("the fold left invalid IR, {errors:?}\n{}", rucc_ir::print(&module, &names));
        }
        rucc_ir::print(&module, &names)
    }

    /// A `printf` of a format holding no `%` and ending in a newline is a `puts` of the rest of it.
    ///
    /// The rest of it is a string this module did not hold, because "hello world" terminated is not
    /// a suffix of "hello world\n" terminated, so the fold has to leave an object behind as well as
    /// a call.
    #[test]
    fn a_format_that_ends_in_a_newline_is_written_by_puts() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 13 = { bytes "hello world\0a\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @printf(%0) : (ptr, ...) -> i32
    return
}
"#,
        );
        assert!(out.contains("call @puts("), "{out}");
        assert!(!out.contains("call @printf("), "{out}");
        assert!(out.contains(r#"@.Lfold.0 : bytes 12 = { bytes "hello world\00" }"#), "{out}");
    }

    /// A one character format is a `putchar` of that character, and an empty one is nothing at all.
    #[test]
    fn a_short_format_is_written_by_putchar_or_by_nothing() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 2 = { bytes "x\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 1 = { bytes "\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @printf(%0) : (ptr, ...) -> i32
    %2 = global_addr @.Lstr.1
    %3 = call @printf(%2) : (ptr, ...) -> i32
    return
}
"#,
        );
        assert!(out.contains("iconst.i32 120"), "the character is the argument, {out}");
        assert!(out.contains("call @putchar("), "{out}");
        assert_eq!(out.matches("call @").count(), 1, "the empty one is gone, {out}");
    }

    /// `printf("%s\n", p)` is `puts(p)` and `printf("%c", c)` is `putchar(c)`, whatever the
    /// argument is.
    #[test]
    fn the_two_formats_that_are_a_call_on_their_own_are_folded_for_any_argument() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 4 = { bytes "%s\0a\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 3 = { bytes "%c\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external);

func @g(ptr, i32), linkage(external) {
block0(%0: ptr, %1: i32):
    %2 = global_addr @.Lstr.0
    %3 = call @printf(%2, %0) : (ptr, ...) -> i32
    %4 = global_addr @.Lstr.1
    %5 = call @printf(%4, %1) : (ptr, ...) -> i32
    return
}
"#,
        );
        assert!(out.contains("call @puts(%0)"), "{out}");
        assert!(out.contains("call @putchar(%1)"), "{out}");
    }

    /// `printf("%s", p)` where `p` is not a string this module holds stays as it is.
    ///
    /// There is no stream argument to hand to `fputs`, and `stdout` is not a name a compiler may
    /// invent. gcc stops in the same place.
    #[test]
    fn a_string_argument_nothing_is_known_about_is_left_to_printf() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 3 = { bytes "%s\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external);

func @g(ptr), linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @printf(%1, %0) : (ptr, ...) -> i32
    return
}
"#,
        );
        assert!(out.contains("call @printf("), "{out}");
    }

    /// The `fprintf` list, which is the `printf` one with a stream in hand.
    ///
    /// A format holding no `%` is an `fwrite` of the whole of it rather than a `puts` of part of
    /// it, since `fwrite` is told how many bytes to write and adds no newline of its own.
    #[test]
    fn a_stream_takes_the_whole_format_through_fwrite() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 13 = { bytes "hello world\0a\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 2 = { bytes "q\00" }, align 1, linkage(internal), constant

func @fprintf(ptr, ptr, ...) -> i32, linkage(external);

func @g(ptr), linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @fprintf(%0, %1) : (ptr, ptr, ...) -> i32
    %3 = global_addr @.Lstr.1
    %4 = call @fprintf(%0, %3) : (ptr, ptr, ...) -> i32
    return
}
"#,
        );
        assert!(out.contains("call @fwrite("), "{out}");
        assert!(out.contains("iconst.i64 12"), "the whole format, newline and all, {out}");
        assert!(out.contains("call @fputc("), "{out}");
        assert!(!out.contains("call @fprintf("), "{out}");
    }

    /// `fprintf(s, "%s", p)` is `fputs(p, s)` however little is known about `p`, which is the fold
    /// `printf` cannot have.
    #[test]
    fn a_string_argument_with_a_stream_beside_it_becomes_fputs() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 3 = { bytes "%s\00" }, align 1, linkage(internal), constant

func @fprintf(ptr, ptr, ...) -> i32, linkage(external);

func @g(ptr, ptr), linkage(external) {
block0(%0: ptr, %1: ptr):
    %2 = global_addr @.Lstr.0
    %3 = call @fprintf(%0, %2, %1) : (ptr, ptr, ...) -> i32
    return
}
"#,
        );
        assert!(out.contains("call @fputs(%1, %0)"), "{out}");
    }

    /// An `fputs` of a string whose length is known is an `fwrite` of that many bytes, one of a
    /// single character is an `fputc`, and one of nothing is nothing.
    #[test]
    fn fputs_of_a_string_this_module_holds_is_folded_by_its_length() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 7 = { bytes "abcdef\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 2 = { bytes "z\00" }, align 1, linkage(internal), constant
global @.Lstr.2 : bytes 1 = { bytes "\00" }, align 1, linkage(internal), constant

func @fputs(ptr, ptr) -> i32, linkage(external);

func @g(ptr), linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @fputs(%1, %0) : (ptr, ptr) -> i32
    %3 = global_addr @.Lstr.1
    %4 = call @fputs(%3, %0) : (ptr, ptr) -> i32
    %5 = global_addr @.Lstr.2
    %6 = call @fputs(%5, %0) : (ptr, ptr) -> i32
    return
}
"#,
        );
        assert!(out.contains("call @fwrite("), "{out}");
        assert!(out.contains("iconst.i64 6"), "{out}");
        assert!(out.contains("iconst.i32 122"), "{out}");
        assert!(out.contains("call @fputc("), "{out}");
        assert!(!out.contains("call @fputs("), "the empty one is gone too, {out}");
    }

    /// An index into a string literal is a string as well, which is what `fputs(s1 + 6, s)` is.
    ///
    /// The index is an `int` widened to the width of a pointer, because that is what the frontend
    /// writes for an index the source wrote as one and nothing has folded it yet where this runs.
    /// An index landing on the terminator is the empty string, so that call goes altogether.
    #[test]
    fn an_index_into_a_literal_is_a_string_of_its_own() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant

func @fputs(ptr, ptr) -> i32, linkage(external);

func @g(ptr), linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = iconst.i32 6
    %3 = sext.i64 %2
    %4 = ptr_add %1, %3
    %5 = call @fputs(%4, %0) : (ptr, ptr) -> i32
    %6 = iconst.i32 11
    %7 = sext.i64 %6
    %8 = ptr_add %1, %7
    %9 = call @fputs(%8, %0) : (ptr, ptr) -> i32
    return
}
"#,
        );
        assert!(out.contains("iconst.i64 5"), "world without its terminator, {out}");
        assert!(out.contains("call @fwrite("), "{out}");
        assert!(!out.contains("call @fputs("), "and the terminator itself is nothing, {out}");
    }

    /// A conditional expression whose arms are two literals of one length is folded, and one whose
    /// arms are two lengths is not.
    ///
    /// The arms reach the call through a block parameter rather than through a `select`, because
    /// that is what the lowering walk builds for a conditional expression, so the walk that answers
    /// what string a value is has to go up through the branches to find them.
    #[test]
    fn a_choice_between_two_literals_is_folded_when_they_are_the_same_length() {
        let text = r#"
global @.Lstr.0 : bytes 2 = { bytes "f\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 2 = { bytes "x\00" }, align 1, linkage(internal), constant
global @.Lstr.2 : bytes 4 = { bytes "abc\00" }, align 1, linkage(internal), constant

func @fputs(ptr, ptr) -> i32, linkage(external);

func @g(ptr, i1), linkage(external) {
block0(%0: ptr, %1: i1):
    %2 = global_addr @.LEFT
    %3 = global_addr @.Lstr.1
    br_if %1, block1(%2), block1(%3)
block1(%4: ptr):
    %5 = call @fputs(%4, %0) : (ptr, ptr) -> i32
    return
}
"#;
        let same = folded(&text.replace(".LEFT", ".Lstr.0"));
        assert!(same.contains("call @fwrite("), "{same}");
        assert!(same.contains("iconst.i64 1"), "{same}");

        let differing = folded(&text.replace(".LEFT", ".Lstr.2"));
        assert!(differing.contains("call @fputs("), "{differing}");
    }

    /// A call whose result something reads is left alone.
    ///
    /// `printf` answers how many characters it wrote and `puts` answers a number that is not that
    /// count, so a program looking at the answer is a program this may not touch.
    #[test]
    fn a_call_whose_answer_is_read_is_not_folded() {
        let out = folded(
            r#"
global @n : bytes 4 = { zero 4 }, align 4, linkage(external)
global @.Lstr.0 : bytes 3 = { bytes "a\0a\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @printf(%0) : (ptr, ...) -> i32
    %2 = global_addr @n
    store %1 -> %2, align 4
    return
}
"#,
        );
        assert!(out.contains("call @printf("), "{out}");
    }

    /// A module holding the body of its own `printf` means that body.
    #[test]
    fn a_name_this_module_defines_is_that_definition() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 3 = { bytes "a\0a\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external) {
block0(%0: ptr):
    %1 = iconst.i32 0
    return %1
}

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @printf(%0) : (ptr, ...) -> i32
    return
}
"#,
        );
        assert!(out.contains("call @printf("), "{out}");
    }

    /// A program that declared `puts` as something else keeps the call it had.
    ///
    /// The verifier holds that a call to a name this module declares carries that name's signature,
    /// so the fold either agrees with the declaration or does not happen. A fold that went ahead
    /// here would produce IR the compiler itself refuses.
    #[test]
    fn a_declaration_of_another_shape_stops_the_fold() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 13 = { bytes "hello world\0a\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external);
func @puts(ptr, i32) -> i32, linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @printf(%0) : (ptr, ...) -> i32
    return
}
"#,
        );
        assert!(out.contains("call @printf("), "{out}");
        assert!(!out.contains("@.Lfold."), "and no object was left behind either, {out}");
    }

    /// A variable by one of those names stops it as well, since a variable is not a function to
    /// call.
    #[test]
    fn a_variable_by_the_name_of_a_replacement_stops_the_fold() {
        let out = folded(
            r#"
global @putchar : bytes 4 = { zero 4 }, align 4, linkage(external)
global @.Lstr.0 : bytes 2 = { bytes "x\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @printf(%0) : (ptr, ...) -> i32
    return
}
"#,
        );
        assert!(out.contains("call @printf("), "{out}");
    }

    /// An `_unlocked` spelling gets the one fold that names no function.
    ///
    /// A system need not have a `puts_unlocked` for the compiler to name, which is the reason the
    /// torture program gives and the place gcc stops too.
    #[test]
    fn the_unlocked_spellings_are_only_removed_when_they_write_nothing() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 13 = { bytes "hello world\0a\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 1 = { bytes "\00" }, align 1, linkage(internal), constant

func @printf_unlocked(ptr, ...) -> i32, linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @printf_unlocked(%0) : (ptr, ...) -> i32
    %2 = global_addr @.Lstr.1
    %3 = call @printf_unlocked(%2) : (ptr, ...) -> i32
    return
}
"#,
        );
        assert_eq!(out.matches("call @printf_unlocked(").count(), 1, "{out}");
        assert!(!out.contains("call @puts("), "{out}");
    }

    /// `-fno-builtin-printf` takes one name away and leaves the rest of the family folded.
    #[test]
    fn one_name_can_be_taken_away_without_taking_the_family_away() {
        let body = r#"
global @.Lstr.0 : bytes 2 = { bytes "x\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external);
func @fputs(ptr, ptr) -> i32, linkage(external);

func @g(ptr), linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @printf(%1) : (ptr, ...) -> i32
    %3 = call @fputs(%1, %0) : (ptr, ptr) -> i32
    return
}
"#;
        let out = run(body, &["printf".to_owned()], &mut Fuel::unlimited());
        assert!(out.contains("call @printf("), "{out}");
        assert!(out.contains("call @fputc("), "and the other one still folded, {out}");
    }

    /// Fuel stops it, which is what a bisection over a miscompilation needs of every transformation
    /// here.
    #[test]
    fn a_run_out_of_fuel_transforms_nothing() {
        let body = r#"
global @.Lstr.0 : bytes 2 = { bytes "x\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @printf(%0) : (ptr, ...) -> i32
    return
}
"#;
        let mut fuel = Fuel::of(0);
        let out = run(body, &[], &mut fuel);
        assert!(out.contains("call @printf("), "{out}");
        assert_eq!(fuel.spent(), 0);
    }

    /// Two calls folded to the same string share one object rather than getting one each.
    #[test]
    fn one_object_serves_every_call_that_prints_the_same_thing() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 4 = { bytes "hi\0a\00" }, align 1, linkage(internal), constant

func @printf(ptr, ...) -> i32, linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @printf(%0) : (ptr, ...) -> i32
    %2 = call @printf(%0) : (ptr, ...) -> i32
    return
}

func @h(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @printf(%0) : (ptr, ...) -> i32
    return
}
"#,
        );
        assert_eq!(out.matches("@.Lfold.0 : bytes").count(), 1, "{out}");
        assert!(!out.contains("@.Lfold.1"), "{out}");
        assert_eq!(out.matches("call @puts(").count(), 3, "{out}");
    }

    /// A search for the empty string finds it at the front of whatever it was given.
    ///
    /// The haystack need not be a string this module holds, because the answer does not depend on
    /// what is in it.
    #[test]
    fn a_search_for_nothing_answers_with_the_haystack_itself() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 1 = { bytes "\00" }, align 1, linkage(internal), constant

func @strstr(ptr, ptr) -> ptr, linkage(external);

func @g(ptr) -> ptr, linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @strstr(%0, %1) : (ptr, ptr) -> ptr
    return %2
}
"#,
        );
        assert!(!out.contains("call @strstr("), "{out}");
        assert!(out.contains("return %0"), "{out}");
    }

    /// Two strings this module holds answer themselves, at a place in the first or nowhere in it.
    #[test]
    fn two_strings_this_module_holds_answer_without_a_call() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 2 = { bytes "w\00" }, align 1, linkage(internal), constant
global @.Lstr.2 : bytes 3 = { bytes "zz\00" }, align 1, linkage(internal), constant

func @strstr(ptr, ptr) -> ptr, linkage(external);
func @use(ptr, ptr), linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = global_addr @.Lstr.1
    %2 = call @strstr(%0, %1) : (ptr, ptr) -> ptr
    %3 = global_addr @.Lstr.2
    %4 = call @strstr(%0, %3) : (ptr, ptr) -> ptr
    call @use(%2, %4) : (ptr, ptr)
    return
}
"#,
        );
        assert!(!out.contains("call @strstr("), "{out}");
        assert!(out.contains("ptr_add %0, "), "the w is six bytes along, {out}");
        assert!(out.contains("iconst.i64 6"), "{out}");
        assert!(out.contains("inttoptr"), "and the zz is nowhere in it, {out}");
    }

    /// A one character needle is a search for a character, which `strchr` is the name of.
    #[test]
    fn a_one_character_needle_becomes_a_search_for_that_character() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 2 = { bytes "o\00" }, align 1, linkage(internal), constant

func @strstr(ptr, ptr) -> ptr, linkage(external);

func @g(ptr) -> ptr, linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @strstr(%0, %1) : (ptr, ptr) -> ptr
    return %2
}
"#,
        );
        assert!(!out.contains("call @strstr("), "{out}");
        assert!(out.contains("call @strchr(%0, "), "{out}");
        assert!(out.contains("iconst.i32 111"), "{out}");
    }

    /// A module whose `strchr` is something else of that name keeps its `strstr` call.
    #[test]
    fn a_strchr_of_another_shape_is_not_the_one_to_call() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 2 = { bytes "o\00" }, align 1, linkage(internal), constant

func @strstr(ptr, ptr) -> ptr, linkage(external);
func @strchr(ptr, ptr) -> ptr, linkage(external);

func @g(ptr) -> ptr, linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @strstr(%0, %1) : (ptr, ptr) -> ptr
    return %2
}
"#,
        );
        assert!(out.contains("call @strstr("), "{out}");
    }

    /// A declaration renamed by an assembler name is the function the standard describes still.
    ///
    /// The call names the symbol the rename asked for, and the fold reads the spelling beside it,
    /// which is what `gcc.c-torture/execute/builtins/strstr-asm.c` is written to catch.
    #[test]
    fn a_renamed_declaration_is_still_the_function_it_was_spelled() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 1 = { bytes "\00" }, align 1, linkage(internal), constant

func @my_strstr(ptr, ptr) -> ptr, linkage(external), spelled "strstr";

func @g(ptr) -> ptr, linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @my_strstr(%0, %1) : (ptr, ptr) -> ptr
    return %2
}
"#,
        );
        assert!(!out.contains("call @my_strstr("), "{out}");
        assert!(out.contains("return %0"), "{out}");
    }

    /// A module that renamed `strchr` gets a call to the symbol it renamed it to.
    #[test]
    fn a_renamed_replacement_is_called_by_the_symbol_the_rename_asked_for() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 2 = { bytes "o\00" }, align 1, linkage(internal), constant

func @strstr(ptr, ptr) -> ptr, linkage(external);
func @my_strchr(ptr, i32) -> ptr, linkage(external), spelled "strchr";

func @g(ptr) -> ptr, linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @strstr(%0, %1) : (ptr, ptr) -> ptr
    return %2
}
"#,
        );
        assert!(out.contains("call @my_strchr(%0, "), "{out}");
        assert!(!out.contains("call @strchr("), "{out}");
    }

    /// `-fno-builtin-strstr` leaves the call alone.
    #[test]
    fn a_strstr_taken_away_is_a_call_like_any_other() {
        let body = r#"
global @.Lstr.0 : bytes 1 = { bytes "\00" }, align 1, linkage(internal), constant

func @strstr(ptr, ptr) -> ptr, linkage(external);

func @g(ptr) -> ptr, linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @strstr(%0, %1) : (ptr, ptr) -> ptr
    return %2
}
"#;
        let out = run(body, &["strstr".to_owned()], &mut Fuel::unlimited());
        assert!(out.contains("call @strstr("), "{out}");
    }

    /// `strlen` of a string this module holds is its length, and of a place inside one is the rest.
    #[test]
    fn strlen_of_a_string_this_module_holds_is_a_number() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant

func @strlen(ptr) -> i64, linkage(external);
func @use(i64, i64), linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = call @strlen(%0) : (ptr) -> i64
    %2 = iconst.i64 6
    %3 = ptr_add %0, %2
    %4 = call @strlen(%3) : (ptr) -> i64
    call @use(%1, %4) : (i64, i64)
    return
}
"#,
        );
        assert!(!out.contains("call @strlen("), "{out}");
        assert!(out.contains("iconst.i64 11"), "{out}");
        assert!(out.contains("iconst.i64 5"), "the world on its own, {out}");
    }

    /// `strnlen` stops at its count, and the count is what the answer is where nothing terminated
    /// the string inside it.
    #[test]
    fn strnlen_answers_the_count_where_the_string_runs_past_it() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant

func @strnlen(ptr, i64) -> i64, linkage(external);
func @use(i64, i64), linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = iconst.i64 3
    %2 = call @strnlen(%0, %1) : (ptr, i64) -> i64
    %3 = iconst.i64 40
    %4 = call @strnlen(%0, %3) : (ptr, i64) -> i64
    call @use(%2, %4) : (i64, i64)
    return
}
"#,
        );
        assert!(!out.contains("call @strnlen("), "{out}");
        assert!(out.contains("iconst.i64 3"), "the count came first, {out}");
        assert!(out.contains("iconst.i64 11"), "the terminator came first, {out}");
    }

    /// A count the source wrote as an `int` reaches the call widened, and the constant is under the
    /// widening rather than in the argument.
    #[test]
    fn a_count_that_was_widened_on_the_way_in_is_still_a_count() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant

func @strnlen(ptr, i64) -> i64, linkage(external);

func @g() -> i64, linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = iconst.i32 4
    %2 = sext.i64 %1
    %3 = call @strnlen(%0, %2) : (ptr, i64) -> i64
    return %3
}
"#,
        );
        assert!(!out.contains("call @strnlen("), "{out}");
        assert!(out.contains("iconst.i64 4"), "{out}");
    }

    /// `memchr` reads a count rather than a string, so it finds a byte past the terminator, and it
    /// answers nowhere where the byte is outside the count.
    #[test]
    fn memchr_searches_the_object_rather_than_the_string_in_it() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant

func @memchr(ptr, i32, i64) -> ptr, linkage(external);
func @use(ptr, ptr), linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = iconst.i32 0
    %2 = iconst.i64 12
    %3 = call @memchr(%0, %1, %2) : (ptr, i32, i64) -> ptr
    %4 = iconst.i32 100
    %5 = iconst.i64 10
    %6 = call @memchr(%0, %4, %5) : (ptr, i32, i64) -> ptr
    call @use(%3, %6) : (ptr, ptr)
    return
}
"#,
        );
        assert!(!out.contains("call @memchr("), "{out}");
        assert!(out.contains("iconst.i64 11"), "the terminator is inside the count, {out}");
        assert!(out.contains("inttoptr.ptr "), "the d is one byte past the count, {out}");
    }

    /// A count the object does not have that many bytes for is a read the compiler cannot see the
    /// end of, so the call stays.
    #[test]
    fn a_memchr_that_runs_off_the_object_is_left_alone() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant

func @memchr(ptr, i32, i64) -> ptr, linkage(external);

func @g() -> ptr, linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = iconst.i32 122
    %2 = iconst.i64 13
    %3 = call @memchr(%0, %1, %2) : (ptr, i32, i64) -> ptr
    return %3
}
"#,
        );
        assert!(out.contains("call @memchr("), "{out}");
    }

    /// `strchr` finds the first, `strrchr` the last, and a search for the terminator finds it at the
    /// end rather than not at all.
    #[test]
    fn the_two_character_searches_answer_from_either_end() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant

func @strchr(ptr, i32) -> ptr, linkage(external);
func @strrchr(ptr, i32) -> ptr, linkage(external);
func @use(ptr, ptr, ptr, ptr), linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = iconst.i32 111
    %2 = call @strchr(%0, %1) : (ptr, i32) -> ptr
    %3 = call @strrchr(%0, %1) : (ptr, i32) -> ptr
    %4 = iconst.i32 0
    %5 = call @strchr(%0, %4) : (ptr, i32) -> ptr
    %6 = iconst.i32 122
    %7 = call @strchr(%0, %6) : (ptr, i32) -> ptr
    call @use(%2, %3, %5, %7) : (ptr, ptr, ptr, ptr)
    return
}
"#,
        );
        assert!(!out.contains("call @strchr("), "{out}");
        assert!(!out.contains("call @strrchr("), "{out}");
        assert!(out.contains("iconst.i64 4"), "the first o, {out}");
        assert!(out.contains("iconst.i64 7"), "the last o, {out}");
        assert!(out.contains("iconst.i64 11"), "the terminator, {out}");
        assert!(out.contains("inttoptr.ptr "), "there is no z in it, {out}");
    }

    /// The two comparisons answer one of minus one, zero and one, which is the sign the standard
    /// promises and nothing more.
    #[test]
    fn the_two_comparisons_answer_a_sign() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 6 = { bytes "hello\00" }, align 1, linkage(internal), constant

func @strcmp(ptr, ptr) -> i32, linkage(external);
func @strncmp(ptr, ptr, i64) -> i32, linkage(external);
func @use(i32, i32, i32), linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = global_addr @.Lstr.1
    %2 = call @strcmp(%0, %1) : (ptr, ptr) -> i32
    %3 = call @strcmp(%1, %0) : (ptr, ptr) -> i32
    %4 = iconst.i64 5
    %5 = call @strncmp(%0, %1, %4) : (ptr, ptr, i64) -> i32
    call @use(%2, %3, %5) : (i32, i32, i32)
    return
}
"#,
        );
        assert!(!out.contains("call @strcmp("), "{out}");
        assert!(!out.contains("call @strncmp("), "{out}");
        assert!(out.contains("iconst.i32 1"), "the longer one is the greater, {out}");
        assert!(out.contains("iconst.i32 -1"), "and the other way round, {out}");
        assert!(out.contains("iconst.i32 0"), "five bytes of each are the same, {out}");
    }

    /// The two spans walk the same string with the test turned round.
    #[test]
    fn the_two_spans_are_one_walk_each_way() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 4 = { bytes "hel\00" }, align 1, linkage(internal), constant
global @.Lstr.2 : bytes 3 = { bytes "wz\00" }, align 1, linkage(internal), constant

func @strspn(ptr, ptr) -> i64, linkage(external);
func @strcspn(ptr, ptr) -> i64, linkage(external);
func @use(i64, i64), linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = global_addr @.Lstr.1
    %2 = call @strspn(%0, %1) : (ptr, ptr) -> i64
    %3 = global_addr @.Lstr.2
    %4 = call @strcspn(%0, %3) : (ptr, ptr) -> i64
    call @use(%2, %4) : (i64, i64)
    return
}
"#,
        );
        assert!(!out.contains("call @strspn("), "{out}");
        assert!(!out.contains("call @strcspn("), "{out}");
        assert!(out.contains("iconst.i64 4"), "hello stops at the o, {out}");
        assert!(out.contains("iconst.i64 6"), "the w is six bytes along, {out}");
    }

    /// Nothing is inside an empty set, so `strspn(s, "")` is zero and `strcspn(s, "")` is the length
    /// of `s`, whatever `s` is.
    #[test]
    fn an_empty_set_is_a_span_of_nothing_or_of_all_of_it() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 1 = { bytes "\00" }, align 1, linkage(internal), constant

func @strspn(ptr, ptr) -> i64, linkage(external);
func @strcspn(ptr, ptr) -> i64, linkage(external);
func @strlen(ptr) -> i64, linkage(external);
func @use(i64, i64), linkage(external);

func @g(ptr), linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @strspn(%0, %1) : (ptr, ptr) -> i64
    %3 = call @strcspn(%0, %1) : (ptr, ptr) -> i64
    call @use(%2, %3) : (i64, i64)
    return
}
"#,
        );
        assert!(!out.contains("call @strspn("), "{out}");
        assert!(!out.contains("call @strcspn("), "{out}");
        assert!(out.contains("call @strlen(%0)"), "{out}");
        assert!(out.contains("iconst.i64 0"), "{out}");
    }

    /// A `strcspn` answering a width `strlen` does not answer is a fold that would leave a reader
    /// holding a number of the wrong size, so it does not happen.
    #[test]
    fn a_strcspn_of_another_width_than_strlen_is_left_alone() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 1 = { bytes "\00" }, align 1, linkage(internal), constant

func @strcspn(ptr, ptr) -> i32, linkage(external);
func @strlen(ptr) -> i64, linkage(external);

func @g(ptr) -> i32, linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @strcspn(%0, %1) : (ptr, ptr) -> i32
    return %2
}
"#,
        );
        assert!(out.contains("call @strcspn("), "{out}");
    }

    /// `strpbrk` of a set of one character is a search for that character, and of an empty set is
    /// nowhere at all.
    #[test]
    fn strpbrk_of_a_short_set_is_a_search_or_an_answer() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 2 = { bytes "w\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 1 = { bytes "\00" }, align 1, linkage(internal), constant

func @strpbrk(ptr, ptr) -> ptr, linkage(external);
func @strchr(ptr, i32) -> ptr, linkage(external);
func @use(ptr, ptr), linkage(external);

func @g(ptr), linkage(external) {
block0(%0: ptr):
    %1 = global_addr @.Lstr.0
    %2 = call @strpbrk(%0, %1) : (ptr, ptr) -> ptr
    %3 = global_addr @.Lstr.1
    %4 = call @strpbrk(%0, %3) : (ptr, ptr) -> ptr
    call @use(%2, %4) : (ptr, ptr)
    return
}
"#,
        );
        assert!(!out.contains("call @strpbrk("), "{out}");
        assert!(out.contains("call @strchr(%0, "), "{out}");
        assert!(out.contains("iconst.i32 119"), "{out}");
        assert!(out.contains("inttoptr.ptr "), "the empty set is nowhere, {out}");
    }

    /// Two strings this module holds answer `strpbrk` without either call.
    #[test]
    fn strpbrk_over_two_strings_this_module_holds_is_a_place() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant
global @.Lstr.1 : bytes 3 = { bytes "wz\00" }, align 1, linkage(internal), constant
global @.Lstr.2 : bytes 3 = { bytes "qz\00" }, align 1, linkage(internal), constant

func @strpbrk(ptr, ptr) -> ptr, linkage(external);
func @use(ptr, ptr), linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = global_addr @.Lstr.1
    %2 = call @strpbrk(%0, %1) : (ptr, ptr) -> ptr
    %3 = global_addr @.Lstr.2
    %4 = call @strpbrk(%0, %3) : (ptr, ptr) -> ptr
    call @use(%2, %4) : (ptr, ptr)
    return
}
"#,
        );
        assert!(!out.contains("call @strpbrk("), "{out}");
        assert!(out.contains("iconst.i64 6"), "the w is six bytes along, {out}");
        assert!(out.contains("inttoptr.ptr "), "there is neither a q nor a z in it, {out}");
    }

    /// `index` and `rindex` are the same two searches under their older names.
    #[test]
    fn the_older_spellings_of_the_two_searches_are_folded_as_well() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant

func @index(ptr, i32) -> ptr, linkage(external);
func @rindex(ptr, i32) -> ptr, linkage(external);
func @use(ptr, ptr), linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    %1 = iconst.i32 111
    %2 = call @index(%0, %1) : (ptr, i32) -> ptr
    %3 = call @rindex(%0, %1) : (ptr, i32) -> ptr
    call @use(%2, %3) : (ptr, ptr)
    return
}
"#,
        );
        assert!(!out.contains("call @index("), "{out}");
        assert!(!out.contains("call @rindex("), "{out}");
        assert!(out.contains("iconst.i64 4"), "the first o, {out}");
        assert!(out.contains("iconst.i64 7"), "the last o, {out}");
    }

    /// A search from the right for the terminator is a search from the left for it, because a
    /// string has one terminator and both walks find that one.
    #[test]
    fn a_strrchr_of_the_terminator_is_a_strchr_of_it() {
        let out = folded(
            r#"
func @strrchr(ptr, i32) -> ptr, linkage(external);

func @g(ptr) -> ptr, linkage(external) {
block0(%0: ptr):
    %1 = iconst.i32 0
    %2 = call @strrchr(%0, %1) : (ptr, i32) -> ptr
    return %2
}
"#,
        );
        assert!(!out.contains("call @strrchr("), "{out}");
        assert!(out.contains("call @strchr(%0, "), "{out}");
    }

    /// A search from the right for anything else needs the string, since where the last one is
    /// depends on what is in it.
    #[test]
    fn a_strrchr_of_another_character_needs_the_string() {
        let out = folded(
            r#"
func @strrchr(ptr, i32) -> ptr, linkage(external);

func @g(ptr) -> ptr, linkage(external) {
block0(%0: ptr):
    %1 = iconst.i32 111
    %2 = call @strrchr(%0, %1) : (ptr, i32) -> ptr
    return %2
}
"#,
        );
        assert!(out.contains("call @strrchr("), "{out}");
    }

    /// A declaration of the wrong shape is a function of the program's own, whatever it is called.
    #[test]
    fn a_strlen_that_answers_nothing_is_not_the_one_the_library_has() {
        let out = folded(
            r#"
global @.Lstr.0 : bytes 12 = { bytes "hello world\00" }, align 1, linkage(internal), constant

func @strlen(ptr), linkage(external);

func @g(), linkage(external) {
block0:
    %0 = global_addr @.Lstr.0
    call @strlen(%0) : (ptr)
    return
}
"#,
        );
        assert!(out.contains("call @strlen("), "{out}");
    }
}