calyx_opt/passes/
dead_cell_removal.rs

1use crate::traversal::{Action, Named, VisResult, Visitor};
2use calyx_ir::{self as ir};
3use std::collections::HashSet;
4use std::iter;
5
6/// Warn if dead cell removal loops more than this number of times
7const LOOP_THRESHOLD: u64 = 5;
8
9/// Removes unused cells from components.
10#[derive(Default)]
11pub struct DeadCellRemoval {
12    /// Names of cells that have been read from.
13    all_reads: HashSet<ir::Id>,
14}
15
16impl Named for DeadCellRemoval {
17    fn name() -> &'static str {
18        "dead-cell-removal"
19    }
20
21    fn description() -> &'static str {
22        "removes cells that are never used inside a component"
23    }
24}
25
26impl DeadCellRemoval {
27    /// Retain the write if the destination is a hole or if the parent of the
28    /// destination is read from.
29    fn retain_write<T: Clone + Eq + ToString>(
30        &self,
31        wire_reads: &HashSet<ir::Id>,
32        asgn: &ir::Assignment<T>,
33    ) -> bool {
34        let dst = asgn.dst.borrow();
35        if dst.is_hole() {
36            true
37        } else {
38            let parent = &dst.get_parent_name();
39            let out = self.all_reads.contains(parent)
40                || wire_reads.contains(parent)
41                || asgn.dst.borrow().parent_is_fsm();
42            if !out {
43                log::debug!(
44                    "`{}' because `{}' is unused",
45                    ir::Printer::assignment_to_str(asgn),
46                    parent
47                )
48            }
49            out
50        }
51    }
52
53    fn visit_invoke(
54        &mut self,
55        comp: &ir::RRC<ir::Cell>,
56        inputs: &[(ir::Id, ir::RRC<ir::Port>)],
57        outputs: &[(ir::Id, ir::RRC<ir::Port>)],
58        ref_cells: &[(ir::Id, ir::RRC<ir::Cell>)],
59    ) {
60        let cells = inputs
61            .iter()
62            .map(|(_, p)| p)
63            .chain(outputs.iter().map(|(_, p)| p))
64            .map(|p| p.borrow().get_parent_name())
65            .chain(iter::once(comp.borrow().name()))
66            .chain(ref_cells.iter().map(|(_, c)| c.borrow().name()));
67        self.all_reads.extend(cells);
68    }
69}
70
71impl Visitor for DeadCellRemoval {
72    fn start_if(
73        &mut self,
74        s: &mut ir::If,
75        _comp: &mut ir::Component,
76        _sigs: &ir::LibrarySignatures,
77        _comps: &[ir::Component],
78    ) -> VisResult {
79        self.all_reads.insert(s.port.borrow().get_parent_name());
80        Ok(Action::Continue)
81    }
82
83    fn start_static_if(
84        &mut self,
85        s: &mut ir::StaticIf,
86        _comp: &mut ir::Component,
87        _sigs: &ir::LibrarySignatures,
88        _comps: &[ir::Component],
89    ) -> VisResult {
90        self.all_reads.insert(s.port.borrow().get_parent_name());
91        Ok(Action::Continue)
92    }
93
94    fn start_while(
95        &mut self,
96        s: &mut ir::While,
97        _comp: &mut ir::Component,
98        _sigs: &ir::LibrarySignatures,
99        _comps: &[ir::Component],
100    ) -> VisResult {
101        self.all_reads.insert(s.port.borrow().get_parent_name());
102        Ok(Action::Continue)
103    }
104
105    fn invoke(
106        &mut self,
107        s: &mut ir::Invoke,
108        _comp: &mut ir::Component,
109        _sigs: &ir::LibrarySignatures,
110        _comps: &[ir::Component],
111    ) -> VisResult {
112        self.visit_invoke(&s.comp, &s.inputs, &s.outputs, &s.ref_cells);
113        Ok(Action::Continue)
114    }
115
116    fn static_invoke(
117        &mut self,
118        s: &mut ir::StaticInvoke,
119        _comp: &mut ir::Component,
120        _sigs: &ir::LibrarySignatures,
121        _comps: &[ir::Component],
122    ) -> VisResult {
123        self.visit_invoke(&s.comp, &s.inputs, &s.outputs, &s.ref_cells);
124        Ok(Action::Continue)
125    }
126
127    fn finish(
128        &mut self,
129        comp: &mut ir::Component,
130        _sigs: &ir::LibrarySignatures,
131        _comps: &[ir::Component],
132    ) -> VisResult {
133        // Add cells required by any FSM
134        self.all_reads.extend(comp.fsms.iter().flat_map(|fsm| {
135            fsm.borrow().get_called_port_parents(
136                |cell_names: &mut Vec<ir::Id>, port: &ir::RRC<ir::Port>| {
137                    if let ir::PortParent::Cell(group_wref) =
138                        &port.borrow().parent
139                    {
140                        cell_names.push(group_wref.upgrade().borrow().name());
141                    }
142                },
143            )
144        }));
145        // Add @external cells, @protected cells and ref cells.
146        self.all_reads.extend(
147            comp.cells
148                .iter()
149                .filter(|c| {
150                    let cell = c.borrow();
151                    cell.attributes.get(ir::BoolAttr::External).is_some()
152                        || cell.attributes.has(ir::BoolAttr::Protected)
153                        || cell.is_reference()
154                })
155                .map(|c| c.borrow().name()),
156        );
157        // Add component signature
158        self.all_reads.insert(comp.signature.borrow().name());
159
160        // Add all cells that have at least one output read.
161        let mut count = 0;
162        loop {
163            let mut wire_reads = HashSet::new();
164            comp.for_each_assignment(|assign| {
165                assign.for_each_port(|port| {
166                    let port = port.borrow();
167                    if port.direction == ir::Direction::Output {
168                        wire_reads.insert(port.get_parent_name());
169                    }
170                    None
171                });
172            });
173            comp.for_each_static_assignment(|assign| {
174                assign.for_each_port(|port| {
175                    let port = port.borrow();
176                    if port.direction == ir::Direction::Output {
177                        wire_reads.insert(port.get_parent_name());
178                    }
179                    None
180                });
181            });
182
183            // Remove writes to ports on unused cells.
184            for gr in comp.get_groups().iter() {
185                gr.borrow_mut()
186                    .assignments
187                    .retain(|asgn| self.retain_write(&wire_reads, asgn))
188            }
189            // Remove writes to ports on unused cells.
190            for gr in comp.get_static_groups().iter() {
191                gr.borrow_mut()
192                    .assignments
193                    .retain(|asgn| self.retain_write(&wire_reads, asgn))
194            }
195            for cgr in comp.comb_groups.iter() {
196                cgr.borrow_mut()
197                    .assignments
198                    .retain(|asgn| self.retain_write(&wire_reads, asgn))
199            }
200            comp.continuous_assignments
201                .retain(|asgn| self.retain_write(&wire_reads, asgn));
202
203            // Remove unused cells
204            let removed = comp.cells.retain(|c| {
205                let cell = c.borrow();
206                self.all_reads.contains(&cell.name())
207                    || wire_reads.contains(&cell.name())
208            });
209
210            if removed == 0 {
211                break;
212            }
213
214            count += 1;
215        }
216
217        if count >= LOOP_THRESHOLD {
218            log::warn!("{} looped {count} times", Self::name());
219        }
220
221        Ok(Action::Stop)
222    }
223}
calyx_opt/passes/dead_cell_removal.rs

calyx_opt/passes/
dead_cell_removal.rs
