Step 5 — Dead-code elimination

DCE removes instructions whose results are not used. The principle is simple but the bookkeeping is subtle.

The naïve version

bool dce(Function& fn) {
    unordered_set<int> used;
    for (auto& bb : fn.blocks)
        for (auto& ins : bb.instrs)
            for (auto& s : ins.srcs)
                if (s.isTemp()) used.insert(s.tempId);

    for (auto& bb : fn.blocks) {
        auto& v = bb.instrs;
        auto endIt = remove_if(v.begin(), v.end(), [&](const Instr& ins) {
            if (!isPureValueOp(ins.op)) return false;
            if (!ins.dst.isTemp())     return false;
            return used.count(ins.dst.tempId) == 0;
        });
        v.erase(endIt, v.end());
    }
}

Two checks:

1. The op must be pure — no side effects. print, stg, call, jmp, cjmp, ret always survive. (We're being conservative on call: in reality some calls are pure and could be elided. Doing that safely requires effect analysis — punt to cp-14.)
2. The dst must be an unused temp. Named operands are storage; we don't DCE writes to them because they may be loaded later (or externally visible). Globals are out of scope entirely.

What "side effect" really means

A side effect is any change observable outside the local computation:

• I/O — print, read, file writes, system calls.
• Mutation of memory aliased by anyone else — globals, fields, references.
• Synchronisation — atomics, fences, locks.
• Exceptions / traps — div by zero, signed overflow in some languages, dereferencing null.

The trickiest is the last: in most languages, integer division is conditionally effectful — it traps on zero. LLVM marks udiv as having no side effects only when accompanied by an nuw (no-unsigned-wrap) or exact flag the optimiser inserted after proving the divisor nonzero. The point: "purity" is not a property of the opcode alone but of the opcode and the values that flow through it.

We dodge all of this by treating Div and Mod as pure even though they can trap. A real compiler would track this in a side-table.

Why DCE matters

It's not just hygienic cleanup. DCE is what makes other passes affordable. After inlining or partial evaluation, the IR is bloated with intermediate temps that no longer matter. Without DCE every subsequent pass would walk all of that dead material on every iteration. With DCE the IR stays roughly the size of the live program.

LLVM's ADCE (Aggressive DCE) goes further: it starts from the program's observable sinks (ret, stores, calls) and works backwards, considering any instruction not reachable from a sink to be dead. This catches things our naïve forward-pass misses (mutually dead temps that nominally use each other).

The DCE-CFG interaction

After simplifyCFG drops a block, the temps defined in that block are "unreachable" in a stronger sense — no one references them anymore. DCE catches that on the next iteration. This is why our runAll re-runs the whole pipeline to a fixed point.

The inverse interaction also matters: after DCE removes a Move t1 = 7 that nobody read, the constant 7 is no longer propagated anywhere. So the next constFold has nothing new to do — fix point reached.