llvm_transforms/
dce.rs

1//! Dead-code elimination (DCE).
2//!
3//! Removes instructions whose results are never used and which have no
4//! observable side effects.  A single scan is enough; iterate via the
5//! `PassManager` for a full fixed-point.
6//!
7//! Side-effecting instructions (`Store`, `Call`, `Load`, `Alloca`,
8//! terminators) are never removed even if their results are unused.
9
10use crate::pass::FunctionPass;
11use llvm_analysis::UseDefInfo;
12use llvm_ir::{Context, Function, InstrId, InstrKind, ValueRef};
13use std::collections::HashSet;
14
15/// Dead-code elimination pass.
16pub struct DeadCodeElim;
17
18impl FunctionPass for DeadCodeElim {
19    fn name(&self) -> &'static str {
20        "dce"
21    }
22
23    fn run_on_function(&mut self, _ctx: &mut Context, func: &mut Function) -> bool {
24        let info = UseDefInfo::compute(func);
25
26        let dead: HashSet<InstrId> = func
27            .instructions
28            .iter()
29            .enumerate()
30            .filter_map(|(i, instr)| {
31                let iid = InstrId(i as u32);
32                if is_dce_safe(&instr.kind) && info.is_dead(ValueRef::Instruction(iid)) {
33                    Some(iid)
34                } else {
35                    None
36                }
37            })
38            .collect();
39
40        if dead.is_empty() {
41            return false;
42        }
43
44        for bb in &mut func.blocks {
45            bb.body.retain(|id| !dead.contains(id));
46        }
47        true
48    }
49}
50
51/// Returns `true` if an unused instruction with this kind can safely be deleted.
52///
53/// Pure instructions (arithmetic, comparisons, casts, etc.) are safe.
54/// Instructions with observable side effects (`Store`, `Call`, `Load`,
55/// `Alloca`, terminators) are kept even when the result is dead.
56pub fn is_dce_safe(kind: &InstrKind) -> bool {
57    !matches!(
58        kind,
59        InstrKind::Alloca { .. }
60            | InstrKind::Load { .. }
61            | InstrKind::Store { .. }
62            | InstrKind::Call { .. }
63            | InstrKind::Ret { .. }
64            | InstrKind::Br { .. }
65            | InstrKind::CondBr { .. }
66            | InstrKind::Switch { .. }
67            | InstrKind::Unreachable
68    )
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74    use crate::pass::FunctionPass;
75    use llvm_ir::{ArgId, Builder, Context, InstrKind, Linkage, Module, ValueRef};
76
77    // Build:  f(i32 %x) -> i32 { dead = add %x, %x; ret %x }
78    fn make_dead_fn() -> (Context, Module) {
79        let mut ctx = Context::new();
80        let mut module = Module::new("test");
81        let mut b = Builder::new(&mut ctx, &mut module);
82        b.add_function(
83            "f",
84            b.ctx.i32_ty,
85            vec![b.ctx.i32_ty],
86            vec!["x".into()],
87            false,
88            Linkage::External,
89        );
90        let entry = b.add_block("entry");
91        b.position_at_end(entry);
92        let x = b.get_arg(0);
93        let _dead = b.build_add("dead", x, x); // never used
94        b.build_ret(x);
95        (ctx, module)
96    }
97
98    #[test]
99    fn dce_removes_dead_add() {
100        let (mut ctx, mut module) = make_dead_fn();
101        let func = &module.functions[0];
102        // Before DCE: 2 instructions in body (add + ret).
103        let body_before = func.blocks[0].body.len();
104        assert_eq!(body_before, 1, "one non-term instr (add)");
105
106        let mut pass = DeadCodeElim;
107        let changed = pass.run_on_function(&mut ctx, &mut module.functions[0]);
108        assert!(changed);
109        assert_eq!(
110            module.functions[0].blocks[0].body.len(),
111            0,
112            "add removed; body should be empty"
113        );
114    }
115
116    #[test]
117    fn dce_keeps_used_instr() {
118        let mut ctx = Context::new();
119        let mut module = Module::new("test");
120        let mut b = Builder::new(&mut ctx, &mut module);
121        b.add_function(
122            "g",
123            b.ctx.i32_ty,
124            vec![b.ctx.i32_ty, b.ctx.i32_ty],
125            vec!["a".into(), "b".into()],
126            false,
127            Linkage::External,
128        );
129        let entry = b.add_block("entry");
130        b.position_at_end(entry);
131        let a = b.get_arg(0);
132        let bv = b.get_arg(1);
133        let sum = b.build_add("sum", a, bv);
134        b.build_ret(sum); // sum is used
135
136        let mut pass = DeadCodeElim;
137        let changed = pass.run_on_function(&mut ctx, &mut module.functions[0]);
138        assert!(!changed);
139        assert_eq!(
140            module.functions[0].blocks[0].body.len(),
141            1,
142            "sum must remain"
143        );
144    }
145
146    #[test]
147    fn dce_safe_classification() {
148        // Terminators / memory ops must not be considered safe.
149        assert!(!is_dce_safe(&InstrKind::Unreachable));
150        assert!(!is_dce_safe(&InstrKind::Ret { val: None }));
151        assert!(!is_dce_safe(&InstrKind::Store {
152            val: ValueRef::Argument(ArgId(0)),
153            ptr: ValueRef::Argument(ArgId(1)),
154            align: None,
155            volatile: false,
156        }));
157        // Pure arithmetic is safe.
158        assert!(is_dce_safe(&InstrKind::Add {
159            flags: llvm_ir::IntArithFlags::default(),
160            lhs: ValueRef::Argument(ArgId(0)),
161            rhs: ValueRef::Argument(ArgId(0)),
162        }));
163    }
164}
llvm_transforms/dce.rs

llvm_transforms/
dce.rs
