calyx_opt/passes/
dead_assignment_removal.rs

1use crate::traversal::{Action, Named, VisResult, Visitor};
2use calyx_ir::{self as ir};
3use std::collections::{HashMap, HashSet};
4
5// Construct map from combinational instances to all the combinational instances that write to them.
6// So the entries are (comb comp, <set of comb components that write to comb comp>)
7fn get_comb_dependence_map<T>(
8    assigns: &Vec<ir::Assignment<T>>,
9) -> HashMap<ir::Id, HashSet<ir::Id>> {
10    let mut comb_dependence_map: HashMap<ir::Id, HashSet<ir::Id>> =
11        HashMap::new();
12    for assign in assigns {
13        let src = assign.src.borrow();
14        let dst = assign.dst.borrow();
15        let dst_name = dst.get_parent_name();
16        if dst.parent_is_comb() {
17            if src.parent_is_comb() {
18                comb_dependence_map
19                    .entry(dst_name)
20                    .or_default()
21                    .insert(src.get_parent_name());
22            }
23            for p in assign.guard.all_ports() {
24                if p.borrow().parent_is_comb() {
25                    comb_dependence_map
26                        .entry(dst_name)
27                        .or_default()
28                        .insert(p.borrow().get_parent_name());
29                }
30            }
31        }
32    }
33    comb_dependence_map
34}
35
36// non_comb_writes includes all combinational cells that write to
37// something besides a combinational cell
38// i.e., the combinational cells that write to group holes or stateful cells
39fn get_non_comb_writes<T>(assigns: &Vec<ir::Assignment<T>>) -> Vec<ir::Id> {
40    let mut non_comb_writes: Vec<ir::Id> = Vec::new();
41    for assign in assigns {
42        if !assign.dst.borrow().parent_is_comb() {
43            let src = assign.src.borrow();
44            let src_name = src.get_parent_name();
45            if src.parent_is_comb() {
46                non_comb_writes.push(src_name);
47            }
48            for p in assign.guard.all_ports() {
49                let p_name = p.borrow().get_parent_name();
50                if p.borrow().parent_is_comb() {
51                    non_comb_writes.push(p_name);
52                }
53            }
54        }
55    }
56    non_comb_writes
57}
58
59/// Removes unused assigns from groups.
60/// Analyzes the writes to combinational cells in groups
61/// In order for a combinational cell to be considered "used", it must:
62/// 1) write to a non-combinational cell/group hole
63/// 2) write to a non-combinational cell that has been shown to be "used"
64#[derive(Default)]
65pub struct DeadAssignmentRemoval;
66
67impl Named for DeadAssignmentRemoval {
68    fn name() -> &'static str {
69        "dead-assign-removal"
70    }
71
72    fn description() -> &'static str {
73        "removes assignments that are never used inside a group"
74    }
75}
76
77/// Saturate the combinational dependence map by repeatedly adding used cells till we reach a fixed point.
78fn saturate_dep_maps(
79    mut comb_dep_map: HashMap<ir::Id, HashSet<ir::Id>>,
80    mut non_comb_writes: Vec<ir::Id>,
81) -> HashSet<ir::Id> {
82    // To be a used_comb, must
83    // a) be a non_comb_write
84    // b) writes to a used_comb
85    let mut used_combs = HashSet::new();
86    // while loop is bound by size of comb_dependence_map, which is bound
87    // in size by number of ports in the group's assignments
88    while let Some(used) = non_comb_writes.pop() {
89        // add all writes to used to non_comb_writes
90        if let Some(write_to_used) = comb_dep_map.remove(&used) {
91            for write in write_to_used {
92                non_comb_writes.push(write);
93            }
94        }
95        // add used to used_combs
96        used_combs.insert(used);
97    }
98
99    used_combs
100}
101
102impl Visitor for DeadAssignmentRemoval {
103    fn start(
104        &mut self,
105        comp: &mut ir::Component,
106        _sigs: &ir::LibrarySignatures,
107        _comps: &[ir::Component],
108    ) -> VisResult {
109        let cont_comb_dep_map =
110            get_comb_dependence_map(&comp.continuous_assignments);
111        let cont_non_comb_writes =
112            get_non_comb_writes(&comp.continuous_assignments);
113
114        for gr in comp.groups.iter() {
115            let group = gr.borrow();
116
117            // Construct the dependence maps from the group assignments and extend using the continuous assignments
118            let mut comb_dependence_map =
119                get_comb_dependence_map(&group.assignments);
120            comb_dependence_map.extend(cont_comb_dep_map.clone());
121
122            let mut non_comb_writes = get_non_comb_writes(&group.assignments);
123            non_comb_writes.extend(cont_non_comb_writes.clone());
124
125            let used_combs =
126                saturate_dep_maps(comb_dependence_map, non_comb_writes);
127
128            // Explicit drop so we don't get already borrowed error from mutable borrow.
129            drop(group);
130
131            gr.borrow_mut().assignments.retain(|assign| {
132                if assign.dst.borrow().parent_is_fsm() {
133                    // otherwise, assignments to FSMs would be marked as dead
134                    true
135                } else {
136                    let dst = assign.dst.borrow();
137                    // if dst is a combinational component that is not protected,
138                    // the assignment is removed if it is not used
139                    if dst.parent_is_comb() && !dst.parent_is_protected() {
140                        return used_combs.contains(&dst.get_parent_name());
141                    }
142                    // Make sure that the assignment's guard it not false
143                    !assign.guard.is_false()
144                }
145            });
146        }
147
148        Ok(Action::Stop)
149    }
150}
calyx_opt/passes/dead_assignment_removal.rs

calyx_opt/passes/
dead_assignment_removal.rs
