aver/ir/mir/optimize/
dead_code.rs

1//! Phase 6 wave 6 — dead-code elimination on MIR.
2//!
3//! Drop `Let { binding, value: <pure>, body }` when `binding` is
4//! never read in `body`. Pure = no observable side effect:
5//! `Literal` / `Local` / `BinOp` / `Neg` / `Tuple` / `List` /
6//! `MapLiteral` (with pure entries) / `Project` / `Construct` /
7//! `RecordCreate` / `RecordUpdate` (with pure subtrees). `Call` /
8//! `TailCall` / `Try` / `Return` / `Match` / `InterpolatedStr` /
9//! `IndependentProduct` are conservatively impure.
10//!
11//! Const-fold runs before DCE so any folded sub-arithmetic
12//! collapses to a `Literal` (pure) and unlocks its enclosing
13//! `Let` for elimination.
14
15use crate::ast::{Literal, Spanned};
16
17use super::super::expr::{MirBinOp, MirExpr, MirLet};
18use super::super::program::{LocalId, MirProgram};
19
20pub fn dead_code(mut program: MirProgram) -> MirProgram {
21    for mir_fn in program.fns.values_mut() {
22        dce_in_place(&mut mir_fn.body);
23    }
24    program
25}
26
27/// Post-order DCE: recurse into children first so any inner
28/// `Let` chain collapses bottom-up. The bind-elision shape
29/// then catches `let _unused = pure; body` at every level.
30fn dce_in_place(expr: &mut Spanned<MirExpr>) {
31    dce_walk_children(&mut expr.node);
32
33    let should_elide = if let MirExpr::Let(spanned_let) = &expr.node {
34        let let_node = &spanned_let.node;
35        !local_is_read(let_node.binding, &let_node.body) && is_pure(&let_node.value)
36    } else {
37        false
38    };
39
40    if should_elide {
41        let placeholder = MirExpr::Literal(Spanned {
42            node: Literal::Unit,
43            line: expr.line,
44            ty: std::sync::OnceLock::new(),
45        });
46        let original = std::mem::replace(&mut expr.node, placeholder);
47        if let MirExpr::Let(spanned_let) = original {
48            let body = *spanned_let.node.body;
49            *expr = body;
50        } else {
51            unreachable!("should_elide is only set inside the Let branch")
52        }
53    }
54}
55
56fn dce_walk_children(node: &mut MirExpr) {
57    match node {
58        MirExpr::Literal(_) | MirExpr::Local(_) | MirExpr::FnValue(_) => {}
59        MirExpr::Neg(inner) => dce_in_place(inner),
60        MirExpr::BinOp(spanned_bop) => {
61            let bop: &mut MirBinOp = &mut spanned_bop.node;
62            dce_in_place(&mut bop.lhs);
63            dce_in_place(&mut bop.rhs);
64        }
65        MirExpr::Let(spanned_let) => {
66            let let_node: &mut MirLet = &mut spanned_let.node;
67            dce_in_place(&mut let_node.value);
68            dce_in_place(&mut let_node.body);
69        }
70        MirExpr::Call(spanned_call) => {
71            for arg in &mut spanned_call.node.args {
72                dce_in_place(arg);
73            }
74        }
75        MirExpr::TailCall(spanned_tc) => {
76            for arg in &mut spanned_tc.node.args {
77                dce_in_place(arg);
78            }
79        }
80        MirExpr::Match(spanned_match) => {
81            dce_in_place(&mut spanned_match.node.subject);
82            for arm in &mut spanned_match.node.arms {
83                dce_in_place(&mut arm.body);
84            }
85        }
86        MirExpr::IfThenElse(spanned_ite) => {
87            dce_in_place(&mut spanned_ite.node.cond);
88            dce_in_place(&mut spanned_ite.node.then_branch);
89            dce_in_place(&mut spanned_ite.node.else_branch);
90        }
91        MirExpr::Construct(spanned_ctor) => {
92            for arg in &mut spanned_ctor.node.args {
93                dce_in_place(arg);
94            }
95        }
96        MirExpr::RecordCreate(spanned_rec) => {
97            for f in &mut spanned_rec.node.fields {
98                dce_in_place(&mut f.value);
99            }
100        }
101        MirExpr::RecordUpdate(spanned_upd) => {
102            dce_in_place(&mut spanned_upd.node.base);
103            for f in &mut spanned_upd.node.updates {
104                dce_in_place(&mut f.value);
105            }
106        }
107        MirExpr::Project(spanned_proj) => dce_in_place(&mut spanned_proj.node.base),
108        MirExpr::Try(inner) => dce_in_place(inner),
109        MirExpr::Return(inner) => dce_in_place(inner),
110        MirExpr::List(items) | MirExpr::Tuple(items) => {
111            for item in items {
112                dce_in_place(item);
113            }
114        }
115        MirExpr::MapLiteral(entries) => {
116            for (k, v) in entries {
117                dce_in_place(k);
118                dce_in_place(v);
119            }
120        }
121        MirExpr::InterpolatedStr(parts) => {
122            for part in parts {
123                if let super::super::expr::MirStrPart::Expr(e) = part {
124                    dce_in_place(e);
125                }
126            }
127        }
128        MirExpr::IndependentProduct(spanned_ip) => {
129            for item in &mut spanned_ip.node.items {
130                dce_in_place(item);
131            }
132        }
133    }
134}
135
136/// `true` when `body` contains a `MirExpr::Local` whose slot
137/// equals `target`. Lexical — doesn't track scope shadowing
138/// because MIR's slot numbering is already SSA-ish.
139fn local_is_read(target: LocalId, body: &Spanned<MirExpr>) -> bool {
140    let mut found = false;
141    visit_locals(&body.node, &mut |slot| {
142        if slot == target {
143            found = true;
144        }
145    });
146    found
147}
148
149fn visit_locals(node: &MirExpr, visit: &mut impl FnMut(LocalId)) {
150    match node {
151        MirExpr::Literal(_) | MirExpr::FnValue(_) => {}
152        MirExpr::Local(spanned_local) => visit(spanned_local.node.slot),
153        MirExpr::Neg(inner) => visit_locals(&inner.node, visit),
154        MirExpr::BinOp(spanned_bop) => {
155            visit_locals(&spanned_bop.node.lhs.node, visit);
156            visit_locals(&spanned_bop.node.rhs.node, visit);
157        }
158        MirExpr::Let(spanned_let) => {
159            visit_locals(&spanned_let.node.value.node, visit);
160            visit_locals(&spanned_let.node.body.node, visit);
161        }
162        MirExpr::Call(spanned_call) => {
163            for arg in &spanned_call.node.args {
164                visit_locals(&arg.node, visit);
165            }
166        }
167        MirExpr::TailCall(spanned_tc) => {
168            for arg in &spanned_tc.node.args {
169                visit_locals(&arg.node, visit);
170            }
171        }
172        MirExpr::Match(spanned_match) => {
173            visit_locals(&spanned_match.node.subject.node, visit);
174            for arm in &spanned_match.node.arms {
175                visit_locals(&arm.body.node, visit);
176            }
177        }
178        MirExpr::IfThenElse(spanned_ite) => {
179            visit_locals(&spanned_ite.node.cond.node, visit);
180            visit_locals(&spanned_ite.node.then_branch.node, visit);
181            visit_locals(&spanned_ite.node.else_branch.node, visit);
182        }
183        MirExpr::Construct(spanned_ctor) => {
184            for arg in &spanned_ctor.node.args {
185                visit_locals(&arg.node, visit);
186            }
187        }
188        MirExpr::RecordCreate(spanned_rec) => {
189            for f in &spanned_rec.node.fields {
190                visit_locals(&f.value.node, visit);
191            }
192        }
193        MirExpr::RecordUpdate(spanned_upd) => {
194            visit_locals(&spanned_upd.node.base.node, visit);
195            for f in &spanned_upd.node.updates {
196                visit_locals(&f.value.node, visit);
197            }
198        }
199        MirExpr::Project(spanned_proj) => visit_locals(&spanned_proj.node.base.node, visit),
200        MirExpr::Try(inner) | MirExpr::Return(inner) => visit_locals(&inner.node, visit),
201        MirExpr::List(items) | MirExpr::Tuple(items) => {
202            for item in items {
203                visit_locals(&item.node, visit);
204            }
205        }
206        MirExpr::MapLiteral(entries) => {
207            for (k, v) in entries {
208                visit_locals(&k.node, visit);
209                visit_locals(&v.node, visit);
210            }
211        }
212        MirExpr::InterpolatedStr(parts) => {
213            for part in parts {
214                if let super::super::expr::MirStrPart::Expr(e) = part {
215                    visit_locals(&e.node, visit);
216                }
217            }
218        }
219        MirExpr::IndependentProduct(spanned_ip) => {
220            for item in &spanned_ip.node.items {
221                visit_locals(&item.node, visit);
222            }
223        }
224    }
225}
226
227/// Whether a division divisor is provably non-zero, so the division
228/// cannot trap and the enclosing `BinOp::Div` may count as pure. Only a
229/// literal we can inspect qualifies: a non-zero integer, or any float
230/// (Float `/` is total). A variable or computed divisor could be zero,
231/// so it is conservatively treated as possibly-trapping.
232fn divisor_proven_nonzero(rhs: &Spanned<MirExpr>) -> bool {
233    match &rhs.node {
234        MirExpr::Literal(spanned) => match spanned.node {
235            Literal::Int(n) => n != 0,
236            Literal::Float(_) => true,
237            _ => false,
238        },
239        _ => false,
240    }
241}
242
243/// Conservative purity classification — `true` means the
244/// expression has no observable side effect AND cannot diverge
245/// or raise. Exported `pub(super)` so the algebraic pass can
246/// reuse it for `x * 0` (only collapse when the surviving
247/// operand is pure).
248pub(super) fn is_pure(expr: &Spanned<MirExpr>) -> bool {
249    match &expr.node {
250        MirExpr::Literal(_) | MirExpr::Local(_) | MirExpr::FnValue(_) => true,
251        MirExpr::Neg(inner) => is_pure(inner),
252        MirExpr::BinOp(spanned_bop) => {
253            let bop = &spanned_bop.node;
254            // Integer `/` by a possibly-zero divisor traps at runtime
255            // ("division by zero"). Classifying it pure would let DCE drop
256            // a dead `5 / 0`, or the `x * 0` collapse fold `(5 / 0) * 0`
257            // to `0` — silently turning a trapping program into a
258            // non-trapping one. Only a divisor we can prove non-zero is
259            // safe to elide. (Float `/` is total — `x / 0.0` is Infinity,
260            // never traps — and `%`/modulo is a Result-returning builtin,
261            // not a `BinOp`, so neither applies here.)
262            if matches!(bop.op, crate::ast::BinOp::Div) && !divisor_proven_nonzero(&bop.rhs) {
263                return false;
264            }
265            is_pure(&bop.lhs) && is_pure(&bop.rhs)
266        }
267        MirExpr::Tuple(items) | MirExpr::List(items) => items.iter().all(is_pure),
268        MirExpr::MapLiteral(entries) => entries.iter().all(|(k, v)| is_pure(k) && is_pure(v)),
269        MirExpr::Construct(spanned_ctor) => spanned_ctor.node.args.iter().all(is_pure),
270        MirExpr::RecordCreate(spanned_rec) => {
271            spanned_rec.node.fields.iter().all(|f| is_pure(&f.value))
272        }
273        MirExpr::RecordUpdate(spanned_upd) => {
274            is_pure(&spanned_upd.node.base)
275                && spanned_upd.node.updates.iter().all(|f| is_pure(&f.value))
276        }
277        MirExpr::Project(spanned_proj) => is_pure(&spanned_proj.node.base),
278        MirExpr::Let(spanned_let) => {
279            is_pure(&spanned_let.node.value) && is_pure(&spanned_let.node.body)
280        }
281        MirExpr::IfThenElse(spanned_ite) => {
282            is_pure(&spanned_ite.node.cond)
283                && is_pure(&spanned_ite.node.then_branch)
284                && is_pure(&spanned_ite.node.else_branch)
285        }
286        MirExpr::Call(_)
287        | MirExpr::TailCall(_)
288        | MirExpr::Try(_)
289        | MirExpr::Return(_)
290        | MirExpr::Match(_)
291        | MirExpr::InterpolatedStr(_)
292        | MirExpr::IndependentProduct(_) => false,
293    }
294}
295
296#[cfg(test)]
297mod tests {
298    use super::super::super::expr::{MirBinOp, MirCall, MirCallee, MirLet};
299    use super::super::super::program::LocalId;
300    use super::super::const_fold::const_fold;
301    use super::super::test_helpers::{body_of, one_fn_program, span};
302    use super::*;
303    use crate::ast::BinOp;
304    use crate::ir::FnId;
305
306    #[test]
307    fn dce_drops_unused_pure_let() {
308        let body = MirExpr::Let(span(MirLet {
309            binding: LocalId(0),
310            binding_name: "x".to_string(),
311            value: Box::new(span(MirExpr::Literal(span(Literal::Int(7))))),
312            body: Box::new(span(MirExpr::Literal(span(Literal::Int(42))))),
313        }));
314        let eliminated = dead_code(one_fn_program(body));
315        assert!(
316            matches!(body_of(&eliminated), MirExpr::Literal(s) if matches!(s.node, Literal::Int(42))),
317            "dead Let with pure value should collapse to body"
318        );
319    }
320
321    #[test]
322    fn dce_keeps_used_let() {
323        use super::super::super::expr::MirLocal;
324        let read = MirExpr::BinOp(span(MirBinOp {
325            op: BinOp::Add,
326            lhs: Box::new(span(MirExpr::Local(span(MirLocal::at(LocalId(0)))))),
327            rhs: Box::new(span(MirExpr::Literal(span(Literal::Int(1))))),
328        }));
329        let body = MirExpr::Let(span(MirLet {
330            binding: LocalId(0),
331            binding_name: "x".to_string(),
332            value: Box::new(span(MirExpr::Literal(span(Literal::Int(7))))),
333            body: Box::new(span(read)),
334        }));
335        let eliminated = dead_code(one_fn_program(body));
336        assert!(
337            matches!(body_of(&eliminated), MirExpr::Let(_)),
338            "Let with read binding must stay"
339        );
340    }
341
342    #[test]
343    fn dce_keeps_unused_impure_let() {
344        let call_value = MirExpr::Call(span(MirCall {
345            callee: MirCallee::Fn(FnId(0)),
346            args: vec![],
347        }));
348        let body = MirExpr::Let(span(MirLet {
349            binding: LocalId(0),
350            binding_name: String::new(),
351            value: Box::new(span(call_value)),
352            body: Box::new(span(MirExpr::Literal(span(Literal::Int(42))))),
353        }));
354        let eliminated = dead_code(one_fn_program(body));
355        assert!(
356            matches!(body_of(&eliminated), MirExpr::Let(_)),
357            "unused Let with impure (Call) value must stay — could be an effect"
358        );
359    }
360
361    #[test]
362    fn div_purity_classification_respects_trapping_divisor() {
363        use super::super::super::expr::MirLocal;
364        let div = |l: MirExpr, r: MirExpr| {
365            span(MirExpr::BinOp(span(MirBinOp {
366                op: BinOp::Div,
367                lhs: Box::new(span(l)),
368                rhs: Box::new(span(r)),
369            })))
370        };
371        let int = |n| MirExpr::Literal(span(Literal::Int(n)));
372        let flt = |f| MirExpr::Literal(span(Literal::Float(f)));
373
374        // Integer `/` by a zero literal traps at runtime → must be impure.
375        assert!(!is_pure(&div(int(5), int(0))), "5 / 0 traps → impure");
376        // Integer `/` by a proven non-zero literal cannot trap → pure.
377        assert!(is_pure(&div(int(10), int(2))), "10 / 2 cannot trap → pure");
378        // Float `/` is total (`x / 0.0` is Infinity) → pure.
379        assert!(
380            is_pure(&div(flt(1.0), flt(0.0))),
381            "float div is total → pure"
382        );
383        // A variable divisor could be zero at runtime → conservatively impure.
384        assert!(
385            !is_pure(&div(int(5), MirExpr::Local(span(MirLocal::at(LocalId(0)))))),
386            "variable divisor could be zero → impure"
387        );
388    }
389
390    #[test]
391    fn dce_keeps_unused_integer_div_by_zero() {
392        // Regression: a dead `5 / 0` binding must NOT be eliminated — the
393        // division traps, and dropping it would silently turn a trapping
394        // program into a non-trapping one.
395        let value = MirExpr::BinOp(span(MirBinOp {
396            op: BinOp::Div,
397            lhs: Box::new(span(MirExpr::Literal(span(Literal::Int(5))))),
398            rhs: Box::new(span(MirExpr::Literal(span(Literal::Int(0))))),
399        }));
400        let body = MirExpr::Let(span(MirLet {
401            binding: LocalId(0),
402            binding_name: String::new(),
403            value: Box::new(span(value)),
404            body: Box::new(span(MirExpr::Literal(span(Literal::Int(42))))),
405        }));
406        let eliminated = dead_code(one_fn_program(body));
407        assert!(
408            matches!(body_of(&eliminated), MirExpr::Let(_)),
409            "unused `5 / 0` Let must stay — eliding it would drop a runtime trap"
410        );
411    }
412
413    #[test]
414    fn dce_drops_nested_unused_pure_let_chains() {
415        let inner = MirExpr::Let(span(MirLet {
416            binding: LocalId(1),
417            binding_name: "b".to_string(),
418            value: Box::new(span(MirExpr::Literal(span(Literal::Int(2))))),
419            body: Box::new(span(MirExpr::Literal(span(Literal::Int(99))))),
420        }));
421        let outer = MirExpr::Let(span(MirLet {
422            binding: LocalId(0),
423            binding_name: "a".to_string(),
424            value: Box::new(span(MirExpr::Literal(span(Literal::Int(1))))),
425            body: Box::new(span(inner)),
426        }));
427        let eliminated = dead_code(one_fn_program(outer));
428        assert!(
429            matches!(body_of(&eliminated), MirExpr::Literal(s) if matches!(s.node, Literal::Int(99))),
430            "two stacked dead pure Lets should both collapse"
431        );
432    }
433
434    #[test]
435    fn const_fold_then_dce_composes() {
436        let value = MirExpr::BinOp(span(MirBinOp {
437            op: BinOp::Add,
438            lhs: Box::new(span(MirExpr::Literal(span(Literal::Int(1))))),
439            rhs: Box::new(span(MirExpr::Literal(span(Literal::Int(2))))),
440        }));
441        let body = MirExpr::Let(span(MirLet {
442            binding: LocalId(0),
443            binding_name: "x".to_string(),
444            value: Box::new(span(value)),
445            body: Box::new(span(MirExpr::Literal(span(Literal::Int(99))))),
446        }));
447        let optimized = dead_code(const_fold(one_fn_program(body)));
448        assert!(
449            matches!(body_of(&optimized), MirExpr::Literal(s) if matches!(s.node, Literal::Int(99))),
450            "fold→dce should collapse the whole Let to the body literal"
451        );
452    }
453}
aver/ir/mir/optimize/dead_code.rs

aver/ir/mir/optimize/
dead_code.rs
