calyx_opt/analysis/control_order.rs
1use crate::analysis::{PromotionAnalysis, ReadWriteSet};
2use calyx_ir as ir;
3use calyx_utils::{CalyxResult, Error};
4use ir::RRC;
5use itertools::Itertools;
6use petgraph::{
7 algo,
8 graph::{DiGraph, NodeIndex},
9};
10use std::collections::{HashMap, HashSet};
11use std::fmt::Write as _;
12
13/// Extract the dependency order of a list of control programs.
14/// Dependencies are defined using read/write sets used in the control program.
15/// The read/write sets ignore ports on constants and ThisComponent.
16///
17/// For example, if we have control programs C1 and C2 with read sets R1 and
18/// R2 and write sets W1 and W2 respectively, we can define an order relationship:
19///
20/// C1 < C2 if (R1 subset of W2) and (R2 disjoint W1)
21/// C1 > C2 if (R2 subset of W1) and (R1 disjoint W2)
22/// C1 =!= if (R1 subset of W2) and (R2 subset of W1)
23///
24/// Setting `BETTER_ERR` turns on additional machinery to generate an explanation for what caused
25/// the error but may require expensive computations. Turn on when cycles should be a hard error.
26pub struct ControlOrder<const BETTER_ERR: bool>;
27
28impl<const BETTER_ERR: bool> ControlOrder<BETTER_ERR> {
29 fn get_cells(ports: Vec<RRC<ir::Port>>) -> impl Iterator<Item = ir::Id> {
30 ports
31 .into_iter()
32 .filter_map(|p| {
33 let cr = p.borrow().cell_parent();
34 let cell = cr.borrow();
35 match cell.prototype {
36 // Ignore constants and _this
37 ir::CellType::Constant { .. } => None,
38 ir::CellType::ThisComponent => None,
39 _ => Some(cell.name()),
40 }
41 })
42 .unique()
43 }
44
45 // Filters out the constants from `cells`, while mapping the remaining `ir:Cell`s
46 // to their cell name.
47 fn filter_out_constants(
48 cells: &[RRC<ir::Cell>],
49 ) -> impl Iterator<Item = ir::Id> + '_ {
50 cells
51 .iter()
52 .filter_map(|cell| match cell.borrow().prototype {
53 ir::CellType::Constant { .. } => None,
54 ir::CellType::Component { .. }
55 | ir::CellType::Primitive { .. }
56 | ir::CellType::ThisComponent => Some(cell.borrow().name()),
57 })
58 .unique()
59 }
60
61 /// Return a total order for the control programs.
62 /// Returns an error if there is a cycle
63 pub fn get_total_order(
64 stmts: impl Iterator<Item = ir::Control>,
65 ) -> CalyxResult<Vec<ir::Control>> {
66 // Directed graph where edges means that a control program must be run before.
67 let mut gr: DiGraph<Option<ir::Control>, ()> = DiGraph::new();
68
69 // Mapping name of cell to all the indices that read or write to it.
70 let mut reads: HashMap<ir::Id, Vec<NodeIndex>> = HashMap::default();
71 let mut writes: HashMap<ir::Id, Vec<NodeIndex>> = HashMap::default();
72
73 let add_cells =
74 |idx: NodeIndex,
75 ports: Vec<RRC<ir::Port>>,
76 map: &mut HashMap<ir::Id, Vec<NodeIndex>>| {
77 let cells = Self::get_cells(ports);
78 for cell in cells {
79 map.entry(cell).or_default().push(idx);
80 }
81 };
82
83 // Compute read/write sets and add them to the maps
84 for c in stmts {
85 let (port_reads, port_writes) =
86 ReadWriteSet::control_port_read_write_set::<true>(&c);
87 let idx = gr.add_node(Some(c));
88 add_cells(idx, port_reads, &mut reads);
89 add_cells(idx, port_writes, &mut writes);
90 }
91
92 // Add edges between read and writes
93 for (cell, r_idxs) in reads {
94 if let Some(wr_idxs) = writes.get(&cell) {
95 wr_idxs.iter().cartesian_product(r_idxs.iter()).for_each(
96 |(wr, r)| {
97 if wr != r {
98 gr.add_edge(*r, *wr, ());
99 }
100 },
101 );
102 }
103 }
104
105 if let Ok(order) = algo::toposort(&gr, None) {
106 let assigns = order
107 .into_iter()
108 .map(|idx| gr[idx].take().unwrap())
109 .collect_vec();
110 Ok(assigns)
111 } else {
112 let mut msg = "".to_string();
113 if BETTER_ERR {
114 // Compute strongly connected component of the graph
115 let sccs = algo::kosaraju_scc(&gr);
116 let scc = sccs.iter().find(|cc| cc.len() > 1).unwrap();
117 msg = scc
118 .iter()
119 .map(|idx| {
120 let con = gr[*idx].as_ref().unwrap();
121 let mut msg = ir::Printer::control_to_str(con);
122 let (port_reads, port_writes) =
123 ReadWriteSet::control_port_read_write_set::<true>(
124 con,
125 );
126 write!(
127 msg,
128 " which reads: {}\n and writes: {}",
129 Self::get_cells(port_reads)
130 .map(|c| c.id)
131 .join(", "),
132 Self::get_cells(port_writes)
133 .map(|c| c.id)
134 .join(", "),
135 )
136 .unwrap();
137 msg
138 })
139 .join("\n");
140 }
141 Err(Error::misc(format!(
142 "No possible sequential ordering. Control programs exhibit data race:\n{msg}"
143 )))
144 }
145 }
146
147 // Returns a graph of dependency for input programs.
148 // IMPORTANT: we ignore assignments to done ports.
149 // Input control programs are considered to have data dependency if:
150 // 1. subsequent program writes to cells that previous program reads from
151 // 2. subsequent program writes to cells that previous program writes to
152 // 3. subsequent program reads from cells that previous program writes to
153 // Furthermore, we add dependencies due to continuous assignments as well. If:
154 // 4. Program writes to cell that a continuous assignment writes to or reads from.
155 // 5. Program reads from a cell that a continuous assignment writes to.
156 // Then the program "touches" the continuous assignments, and therefore depends
157 // on all previous programs that "touched" continuous assignments as well.
158 // In short, we treat continuous assignments as one big cell.
159 pub fn get_dependency_graph_seq(
160 stmts: impl Iterator<Item = ir::Control>,
161 (cont_reads, cont_writes): (
162 &Vec<ir::RRC<ir::Cell>>,
163 &Vec<ir::RRC<ir::Cell>>,
164 ),
165 dependency: &mut HashMap<NodeIndex, Vec<NodeIndex>>,
166 latency_map: &mut HashMap<NodeIndex, u64>,
167 ) -> DiGraph<Option<ir::Control>, ()> {
168 // The names of the cells that are read/written in continuous assignments
169 let cont_read_cell_names =
170 Self::filter_out_constants(cont_reads).collect_vec();
171 let cont_write_cell_names =
172 Self::filter_out_constants(cont_writes).collect_vec();
173
174 // Directed graph where edges means that a control program must be run before.
175 let mut gr: DiGraph<Option<ir::Control>, ()> = DiGraph::new();
176
177 // Mapping name of cell to all the indices that read or write to it.
178 let mut reads: HashMap<ir::Id, Vec<NodeIndex>> = HashMap::default();
179 let mut writes: HashMap<ir::Id, Vec<NodeIndex>> = HashMap::default();
180
181 // Stores the nodes (i.e., control stmts) that are affected by continuous
182 // assignments
183 let mut continuous_idxs: HashSet<NodeIndex> = HashSet::new();
184
185 for c in stmts {
186 let (cell_reads, cell_writes) =
187 ReadWriteSet::control_read_write_set::<false>(&c);
188 let r_cell_names = Self::filter_out_constants(&cell_reads);
189 let w_cell_names = Self::filter_out_constants(&cell_writes);
190 let latency = PromotionAnalysis::get_inferred_latency(&c);
191 let idx = gr.add_node(Some(c));
192 dependency.insert(idx, Vec::new());
193 latency_map.insert(idx, latency);
194
195 for cell in r_cell_names {
196 // Checking: 3. subsequent program reads from cells that previous program writes to
197 if let Some(wr_idxs) = writes.get(&cell) {
198 for wr_idx in wr_idxs {
199 if !wr_idx.eq(&idx) {
200 gr.add_edge(*wr_idx, idx, ());
201 dependency.entry(idx).or_default().push(*wr_idx);
202 }
203 }
204 }
205
206 // Checking: 5. Program reads from a cell that a continuous
207 // assignment writes to.
208 if cont_write_cell_names.contains(&cell) {
209 for cur_idx in continuous_idxs.iter() {
210 if !cur_idx.eq(&idx) {
211 gr.add_edge(*cur_idx, idx, ());
212 dependency.entry(idx).or_default().push(*cur_idx);
213 }
214 }
215 continuous_idxs.insert(idx);
216 }
217 reads.entry(cell).or_default().push(idx);
218 }
219
220 for cell in w_cell_names {
221 // Checking: 2. subsequent program writes to cells that previous program writes to
222 if let Some(wr_idxs) = writes.get(&cell) {
223 for wr_idx in wr_idxs {
224 if !wr_idx.eq(&idx) {
225 gr.add_edge(*wr_idx, idx, ());
226 dependency.entry(idx).or_default().push(*wr_idx);
227 }
228 }
229 }
230
231 // Checking: 1. subsequent program writes to cells that previous program reads from
232 if let Some(r_idxs) = reads.get(&cell) {
233 for r_idx in r_idxs {
234 if !r_idx.eq(&idx) {
235 gr.add_edge(*r_idx, idx, ());
236 dependency.entry(idx).or_default().push(*r_idx);
237 }
238 }
239 }
240
241 // Checking: 4. Program writes to cell that a continuous assignment
242 // writes to or reads from.
243 if cont_write_cell_names.contains(&cell)
244 || cont_read_cell_names.contains(&cell)
245 {
246 for cur_idx in continuous_idxs.iter() {
247 if !cur_idx.eq(&idx) {
248 gr.add_edge(*cur_idx, idx, ());
249 dependency.entry(idx).or_default().push(*cur_idx);
250 }
251 }
252 continuous_idxs.insert(idx);
253 }
254
255 writes.entry(cell).or_default().push(idx);
256 }
257 }
258 gr
259 }
260}