rucc-opt 0.10.21

//! Dead code elimination: an instruction nothing uses and nothing depends on goes away.
//!
//! The other half of [`crate::fold`]. Folding rewrites an instruction in place and leaves its
//! operands behind, used by nothing, so a function that folds well is a function whose printed IR
//! grows a tail of arithmetic that computes numbers nobody reads. Every later pass will do the
//! same thing, because a rewrite that has to clean up after itself is a rewrite that has to know
//! what else was using what it replaced, and that is the knowledge this pass exists to hold in one
//! place.
//!
//! It is not primarily an optimization. The backend materializes a constant where it is wanted
//! rather than where the IR wrote it, so most of what this removes was already costing nothing in
//! the output. What it buys is that a dump reads like the program, that the passes after it see a
//! function whose size is the size of the work in it, and that a rule which fires on a dead
//! instruction is a rule that fired on nothing rather than a rule that fired.
//!
//! # How it decides
//!
//! An instruction goes when it is not a terminator, when every value it produces is used by
//! nothing, and when it does not happen for a reason of its own. [`Opcode::has_effects`] is the
//! predicate for the last of those and it answers one question for two different things: it means
//! both that an instruction writes memory or does something the program can observe, and that it
//! reads memory. An allocation, a call and a `va_arg` are the first and stay. A plain load is only
//! the second, and it goes.
//!
//! Removing a dead load needs no memory analysis, which is why it does not wait for one. It cannot
//! change what any byte holds, it cannot change what another load sees, and nothing after it can
//! tell that it did not happen. The only thing it changes is whether the program faults on an
//! address it was never going to use the bytes of, and that is what a compiler is for. What does
//! stay is a load the program asked to happen, which is a `volatile` one, and a load other threads
//! can see the order of, which is an atomic one at any strength.
//!
//! An allocation nothing addresses is still removable and still here, and that one does want a
//! memory analysis, because whether anything addresses it is the question.
//!
//! # Why it is a worklist
//!
//! Removing an instruction can kill the one that fed it, and that one can kill its own operand, so
//! a single walk in any order finds a fraction of what is there. The counts are built once, and
//! removing an instruction decrements what its operands were used for, and an operand that reaches
//! zero puts its own definition back on the list. That reaches the same fixpoint a repeated walk
//! would and touches each instruction about once.
//!
//! Uses are counted per occurrence rather than per instruction, because `x + x` uses `x` twice and
//! removing one adder should not make `x` look dead.
//!
//! # What it does not remove
//!
//! Not a block parameter. A parameter nothing reads is dead in exactly the same sense, and taking
//! it out means rewriting the argument list of every branch that arrives at the block, which is
//! worth doing and is a different transformation from this one. The loop carried case is the
//! interesting one there and it is the reason to do it separately: a parameter whose only use is
//! the argument it passes to itself is dead, and seeing that needs the cycle broken rather than a
//! count driven to zero.
//!
//! Not an unreachable block. A block no branch names is dead code by any definition, and removing
//! it is control flow work rather than value work. It belongs with the branch folding that creates
//! most of it.

use rucc_ir::{Block, Def, Extra, Flags, Func, Inst, MemOrder, Opcode};

use crate::uses::{count, operands};
use crate::{Analyses, Analysis, Fuel, Pass, Preserved, Stats};

/// Recorded once for each instruction taken out.
const REMOVED: &str = "instruction with no effects and no users removed";

/// Recorded for an instruction that would have gone if there had been fuel for it.
const NO_FUEL: &str = "dead instruction kept, the pass ran out of fuel";

/// Recorded once for a function that has an instruction this pass is not allowed to look at.
///
/// The honest miss of this pass, and the one worth reading. A store nothing can read again, an
/// allocation nothing addresses and a call that returns nothing and does nothing are all removable
/// once there is a memory analysis to say so, and all of them stay. A function with none of these
/// is a function where this pass found everything there was.
const NEEDS_MEMORY_ANALYSIS: &str =
    "instruction with effects left alone, removing it needs a memory analysis";

/// The pass. It holds nothing, because the counts are per function and live in [`Pass::run`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Dce;

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

    fn describe(&self) -> &'static str {
        "an instruction with no effects whose results nothing uses is removed"
    }

    fn preserves(&self) -> Preserved {
        // Instructions go and blocks do not. A terminator is never dead, because it has an
        // effect, so no block loses the thing that gives it its edges. What does go is a use, and
        // the last use of a value is the end of its live range, so the liveness is not what it
        // was and neither is anything counted off it. Nothing had caught this because no pass
        // before this one in any pipeline builds the liveness, and an analysis nobody has built
        // is an analysis nobody can be wrong about.
        Preserved::ALL.without(Analysis::Liveness)
    }

    fn run(&self, func: &mut Func, _an: &mut Analyses, fuel: &mut Fuel) -> Stats {
        let mut stats = Stats::new();
        let mut uses = count(func);
        let mut work: Vec<Inst> = Vec::new();
        for block in func.blocks().collect::<Vec<Block>>() {
            for inst in func.insts(block) {
                match verdict(func, inst, &uses) {
                    Verdict::Dead => work.push(inst),
                    // Nothing reads it and it stays anyway, which is the one thing this pass
                    // gives up on rather than the thousands of instructions that are simply
                    // live. Counted here, in the one walk that sees every instruction, so the
                    // number is per function and not per visit of the worklist.
                    Verdict::Effects => stats.missed(NEEDS_MEMORY_ANALYSIS),
                    Verdict::Used | Verdict::Terminator => {}
                }
            }
        }
        while let Some(inst) = work.pop() {
            // A worklist can name the same instruction twice, once from the first walk and once
            // from an operand reaching zero, and the second visit finds it already gone.
            if func.block_of(inst).is_none() {
                continue;
            }
            if verdict(func, inst, &uses) != Verdict::Dead {
                continue;
            }
            if !fuel.take() {
                // Out of fuel, which stops the transforming and not the looking, the same way
                // folding treats it. Draining the rest of the list without removing anything
                // costs one pass over what is left and keeps the walk's shape independent of
                // where the fuel ran out.
                stats.missed(NO_FUEL);
                continue;
            }
            operands(func, inst, |value| {
                let count = &mut uses[value.index()];
                *count -= 1;
                if *count == 0 {
                    if let Def::Result { inst: def, .. } = func[value].def {
                        work.push(def);
                    }
                }
            });
            func.remove_inst(inst);
            stats.optimized(REMOVED);
        }
        stats
    }
}

/// Whether this instruction can go, and when it cannot, what kept it.
///
/// The reason is separated out from the answer because two of the three reasons are ordinary and
/// one of them is worth reporting. Nearly every instruction in a function is [`Verdict::Used`],
/// which says nothing. [`Verdict::Effects`] is reached only by an instruction nothing reads, and
/// there are few of those and every one of them is a thing this pass would take if it knew more.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Verdict {
    /// Nothing reads it, nothing depends on it happening, and it can go.
    Dead,
    /// Something reads one of its results.
    Used,
    /// It ends a block, so the block goes with it or neither does.
    Terminator,
    /// Nothing reads it and it happens anyway, as far as this pass can tell.
    Effects,
}

/// Whether this instruction only reads memory, so that not doing it is something nothing can tell.
///
/// A plain load and nothing else. A `volatile` load is an access the program asked for by name and
/// happens whether or not anybody wanted the value. An atomic load is part of an order other
/// threads can see, at every strength and not only at the fence-like ones, and there is no reason
/// to argue about the weak end of that until something is waiting on the answer.
fn reads_only(func: &Func, inst: Inst) -> bool {
    let data = &func[inst];
    if data.opcode != Opcode::Load || data.flags.contains(Flags::VOLATILE) {
        return false;
    }
    let Extra::Mem(mem) = data.extra else { return false };
    func[mem].order == MemOrder::NotAtomic
}

/// What to do with this instruction.
fn verdict(func: &Func, inst: Inst, uses: &[u32]) -> Verdict {
    let data = &func[inst];
    // `is_terminator` on the function rather than on the opcode, because `asm goto` branches
    // and its opcode does not say so. Inline assembly has effects either way, so this is belt
    // and braces, and it is the cheaper of the two mistakes to make.
    if func.is_terminator(inst) {
        return Verdict::Terminator;
    }
    if !data.results().all(|value| uses[value.index()] == 0) {
        return Verdict::Used;
    }
    if data.opcode.has_effects() && !reads_only(func, inst) {
        return Verdict::Effects;
    }
    debug_assert!(
        data.opcode != Opcode::InlineAsm,
        "inline assembly has effects and cannot reach here"
    );
    Verdict::Dead
}

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

    use crate::stats::Kind;
    use crate::{Analysis, Fuel, Pass, dce::Dce};

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

    /// A four byte access of that strength, with nothing else said about it.
    fn plain(order: MemOrder) -> MemInfo {
        MemInfo { size: 4, align: 4, owns: 4, order, tbaa: None, restrict: Restrict::NONE }
    }

    /// How many instructions are left in a block.
    fn left(func: &Func, block: Block) -> usize {
        func.insts(block).count()
    }

    #[test]
    fn arithmetic_nothing_reads_goes_away() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let a = build.iconst(Type::int(32), 2);
        let b = build.iconst(Type::int(32), 3);
        build.binary(Opcode::Add, a, b, Flags::NONE);
        build.ret(&[a]);
        assert!(
            Dce.run(&mut func, &mut crate::machine::fixtures::analyses(), &mut Fuel::unlimited())
                .changed()
        );
        // The add, and then the constant that only it read. A single walk in this order would
        // have removed the add and left the three behind, which is what the worklist is for.
        assert_eq!(left(&func, block), 2);
    }

    #[test]
    fn the_counts_in_the_cache_go_with_the_uses_that_were_removed() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let a = build.iconst(Type::int(32), 2);
        let b = build.iconst(Type::int(32), 3);
        build.binary(Opcode::Add, a, b, Flags::NONE);
        build.ret(&[a]);
        let mut an = crate::machine::fixtures::analyses();
        // Two values are live where the add is and one is live once it has gone, which is the
        // fact this pass used to say it had left standing.
        an.pressure(&func);
        assert!(Dce.run(&mut func, &mut an, &mut Fuel::unlimited()).changed());
        assert!(an.settle(&func, Dce.preserves(), true).is_empty(), "the pass was caught out");
        assert!(!an.holds(Analysis::Pressure), "a stale count was left for the next pass to read");
    }

    #[test]
    fn arithmetic_something_reads_stays() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let a = build.iconst(Type::int(32), 2);
        let b = build.iconst(Type::int(32), 3);
        let sum = build.binary(Opcode::Add, a, b, Flags::NONE);
        build.ret(&[sum]);
        assert!(
            !Dce.run(&mut func, &mut crate::machine::fixtures::analyses(), &mut Fuel::unlimited())
                .changed()
        );
        assert_eq!(left(&func, block), 4);
    }

    #[test]
    fn a_value_used_twice_is_not_dead_when_one_use_goes() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let x = build.iconst(Type::int(32), 7);
        let kept = build.binary(Opcode::Add, x, x, Flags::NONE);
        build.binary(Opcode::Add, x, x, Flags::NONE);
        build.ret(&[kept]);
        assert!(
            Dce.run(&mut func, &mut crate::machine::fixtures::analyses(), &mut Fuel::unlimited())
                .changed()
        );
        // Only the second add. Counting a use per instruction rather than per position would
        // have driven the constant to zero and taken it out from under the first one.
        assert_eq!(left(&func, block), 3);
    }

    #[test]
    fn a_store_stays_however_dead_it_looks() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let value = build.iconst(Type::int(32), 1);
        let address = build.iconst(Type::int(64), 0);
        let address = build.unary(Opcode::IntToPtr, address, Type::PTR);
        let info = MemInfo {
            size: 4,
            align: 4,
            order: MemOrder::NotAtomic,
            tbaa: None,
            owns: 0,
            restrict: Restrict::NONE,
        };
        build.store(value, address, info, Flags::NONE);
        build.ret(&[value]);
        let stats =
            Dce.run(&mut func, &mut crate::machine::fixtures::analyses(), &mut Fuel::unlimited());
        assert!(!stats.changed());
        assert_eq!(left(&func, block), 5);
        // The store is the one instruction here that nothing reads and that stays anyway, so it
        // is the one this pass reports as a miss. That count is the honest size of what a memory
        // analysis would buy, per function, without anybody having to guess at it.
        assert_eq!(stats.count(Kind::Missed, super::NEEDS_MEMORY_ANALYSIS), 1);
    }

    /// A plain load nothing reads goes, which is the one thing here that does not wait for a
    /// memory analysis. Removing it cannot change what any byte holds or what another load sees.
    #[test]
    fn a_load_nothing_reads_goes_away() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let address = build.iconst(Type::int(64), 0);
        let address = build.unary(Opcode::IntToPtr, address, Type::PTR);
        build.load(Type::int(32), address, plain(MemOrder::NotAtomic), Flags::NONE);
        let kept = build.iconst(Type::int(32), 1);
        build.ret(&[kept]);
        let stats =
            Dce.run(&mut func, &mut crate::machine::fixtures::analyses(), &mut Fuel::unlimited());
        assert!(stats.changed());
        // The load, then the cast and the constant that only it read, so what is left is the
        // constant the return reads and the return.
        assert_eq!(left(&func, block), 2);
        assert_eq!(stats.count(Kind::Missed, super::NEEDS_MEMORY_ANALYSIS), 0);
    }

    /// A `volatile` load stays. It is an access the program asked for by name, and it happens
    /// whether or not anybody wanted the value it produced.
    #[test]
    fn a_volatile_load_nothing_reads_stays() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let address = build.iconst(Type::int(64), 0);
        let address = build.unary(Opcode::IntToPtr, address, Type::PTR);
        build.load(Type::int(32), address, plain(MemOrder::NotAtomic), Flags::VOLATILE);
        let kept = build.iconst(Type::int(32), 1);
        build.ret(&[kept]);
        let stats =
            Dce.run(&mut func, &mut crate::machine::fixtures::analyses(), &mut Fuel::unlimited());
        assert!(!stats.changed());
        assert_eq!(left(&func, block), 5);
        assert_eq!(stats.count(Kind::Missed, super::NEEDS_MEMORY_ANALYSIS), 1);
    }

    /// An atomic load stays at every strength, because what it is part of is an order other
    /// threads can see rather than the value it hands back.
    #[test]
    fn an_atomic_load_nothing_reads_stays_however_weak_it_is() {
        for order in [MemOrder::Relaxed, MemOrder::Acquire, MemOrder::SeqCst] {
            let (_, mut func, block) = blank();
            let mut build = Builder::new(&mut func, block);
            let address = build.iconst(Type::int(64), 0);
            let address = build.unary(Opcode::IntToPtr, address, Type::PTR);
            build.load(Type::int(32), address, plain(order), Flags::NONE);
            let kept = build.iconst(Type::int(32), 1);
            build.ret(&[kept]);
            let stats = Dce.run(
                &mut func,
                &mut crate::machine::fixtures::analyses(),
                &mut Fuel::unlimited(),
            );
            assert!(!stats.changed(), "{order:?}");
            assert_eq!(left(&func, block), 5, "{order:?}");
        }
    }

    #[test]
    fn a_value_a_branch_passes_on_is_used_by_the_branch() {
        let (_, mut func, block) = blank();
        let target = func.create_block();
        let param = func.append_param(target, Type::int(32));
        let mut build = Builder::new(&mut func, block);
        let x = build.iconst(Type::int(32), 9);
        build.jump(target, &[x]);
        let mut build = Builder::new(&mut func, target);
        build.ret(&[param]);
        assert!(
            !Dce.run(&mut func, &mut crate::machine::fixtures::analyses(), &mut Fuel::unlimited())
                .changed()
        );
        // The constant is read by nothing in its own block and is not dead, because the only
        // use an instruction can have that its argument list does not hold is this one.
        assert_eq!(left(&func, block), 2);
    }

    #[test]
    fn a_result_a_removed_instruction_read_is_looked_at_again() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let a = build.iconst(Type::int(32), 2);
        let b = build.iconst(Type::int(32), 3);
        let sum = build.binary(Opcode::Add, a, b, Flags::NONE);
        let doubled = build.binary(Opcode::Add, sum, sum, Flags::NONE);
        build.unary(Opcode::SExt, doubled, Type::int(64));
        let kept = build.iconst(Type::int(32), 1);
        build.ret(&[kept]);
        assert!(
            Dce.run(&mut func, &mut crate::machine::fixtures::analyses(), &mut Fuel::unlimited())
                .changed()
        );
        // A chain five long, dead from the far end, and all of it goes in one run. This is the
        // case a walk in program order finds one instruction of per run.
        assert_eq!(left(&func, block), 2);
    }

    #[test]
    fn fuel_stops_the_removing_and_not_the_looking() {
        let (_, mut func, block) = blank();
        let mut build = Builder::new(&mut func, block);
        let a = build.iconst(Type::int(32), 2);
        let b = build.iconst(Type::int(32), 3);
        build.binary(Opcode::Add, a, b, Flags::NONE);
        build.ret(&[a]);
        let mut fuel = Fuel::of(1);
        let stats = Dce.run(&mut func, &mut crate::machine::fixtures::analyses(), &mut fuel);
        assert!(stats.changed());
        // The add and nothing after it, so the constant the add was keeping alive stays. One
        // unit of fuel is one transformation, which is what makes a bisection over it land on
        // a single site.
        assert_eq!(left(&func, block), 3);
        assert_eq!(stats.count(Kind::Optimized, super::REMOVED), 1);
        assert_eq!(stats.count(Kind::Missed, super::NO_FUEL), 1);
    }
}