calyx_opt/analysis/live_range_analysis.rs
1use crate::analysis::{
2 AssignmentAnalysis, ControlId, ReadWriteSet, ShareSet, VariableDetection,
3};
4use calyx_ir::{self as ir, Id, RRC};
5use itertools::Itertools;
6use std::{
7 collections::{HashMap, HashSet},
8 fmt::Debug,
9 rc::Rc,
10};
11
12type TypeNameSet = HashSet<(ir::CellType, ir::Id)>;
13type CellsByType = HashMap<ir::CellType, HashSet<ir::Id>>;
14// maps cell type to maps that map cell name to control statement
15type LiveMapByType = HashMap<ir::CellType, HashMap<ir::Id, HashSet<u64>>>;
16type ReadWriteInfo = (
17 HashSet<(ir::CellType, ir::Id)>,
18 HashSet<(ir::CellType, ir::Id)>,
19);
20type InvokeInfo<'a> = (
21 &'a [(ir::Id, ir::RRC<ir::Port>)],
22 &'a [(ir::Id, ir::RRC<ir::Port>)],
23);
24
25/// Returns [ir::Cell] which are read from in the assignments.
26/// **Ignores** reads from group holes, and reads from done signals, when it
27/// is safe to do so.
28/// To ignore a read from a done signal:
29/// the `@go` signal for the same cell *must* be written to in the group
30pub fn meaningful_read_set<'a, T: 'a>(
31 assigns: impl Iterator<Item = &'a ir::Assignment<T>> + Clone + 'a,
32) -> impl Iterator<Item = RRC<ir::Cell>> + 'a {
33 meaningful_port_read_set(assigns)
34 .map(|port| Rc::clone(&port.borrow().cell_parent()))
35 .unique_by(|cell| cell.borrow().name())
36}
37
38/// Returns the "meaningful" [ir::Port] which are read from in the assignments.
39/// "Meaningful" means we just exclude the following `@done` reads:
40/// the `@go` signal for the same cell *must* be written to in the group
41pub fn meaningful_port_read_set<'a, T: 'a>(
42 assigns: impl Iterator<Item = &'a ir::Assignment<T>> + Clone + 'a,
43) -> impl Iterator<Item = RRC<ir::Port>> + 'a {
44 // go_writes = all cells which are guaranteed to have their go port written to in assigns
45 let go_writes: Vec<RRC<ir::Cell>> = assigns
46 .clone()
47 .filter(|asgn| {
48 // to be included in go_writes, one of the following must hold:
49 // a) guard is true
50 // b cell.go = !cell.done ? 1'd1
51 if asgn.guard.is_true() {
52 return true;
53 }
54
55 // checking cell.go = !cell.done! 1'd1
56 asgn.dst.borrow().attributes.has(ir::NumAttr::Go)
57 && asgn.guard.is_not_done(
58 &asgn.dst.borrow().cell_parent().borrow().name(),
59 )
60 && asgn.src.borrow().is_constant(1, 1)
61 })
62 .analysis()
63 .writes()
64 .filter(|port| port.borrow().attributes.has(ir::NumAttr::Go))
65 .map(|port| Rc::clone(&port.borrow().cell_parent()))
66 .collect();
67
68 // if we have a done port that overlaps with go_writes, then can remove the
69 // done port. Otherwise, we should keep it.
70 assigns
71 .flat_map(ReadWriteSet::port_reads)
72 .filter(move |port| {
73 if port.borrow().attributes.has(ir::NumAttr::Done) {
74 let done_parent = Rc::clone(&port.borrow().cell_parent());
75 go_writes
76 .iter()
77 .all(|go_parent| !Rc::ptr_eq(go_parent, &done_parent))
78 } else {
79 true
80 }
81 })
82}
83
84/// The data structure used to represent sets of ids. This is used to represent
85/// the `live`, `gen`, and `kill` sets.
86#[derive(Default, Clone)]
87pub struct Prop {
88 map: CellsByType,
89}
90
91/// Implement nice printing for prop for debugging purposes.
92impl Debug for Prop {
93 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
94 write!(f, "{{")?;
95 let names = self.map.iter().flat_map(|(_, ids)| ids).join(", ");
96 write!(f, "{names}")?;
97 write!(f, "}}")
98 }
99}
100
101impl Prop {
102 /// Defines the dataflow transfer function.
103 /// We use the standard definition for liveness:
104 /// `(alive - kill) + gen`
105 fn transfer(&mut self, r#gen: Prop, kill: Prop) {
106 self.sub(kill);
107 self.or(r#gen);
108 }
109
110 fn insert(&mut self, (cell_type, cell_name): (ir::CellType, ir::Id)) {
111 self.map.entry(cell_type).or_default().insert(cell_name);
112 }
113
114 /// Defines the data_flow transfer function. `(alive - kill) + gen`.
115 /// However, this is for when gen and kill are sets, and self is a map.
116 fn transfer_set(&mut self, r#gen: TypeNameSet, kill: TypeNameSet) {
117 self.sub_set(kill);
118 self.or_set(r#gen);
119 }
120
121 // The or operation, but when the self is a map and rhs is a set of tuples.
122 fn or_set(&mut self, rhs: TypeNameSet) {
123 for (cell_type, cell_name) in rhs {
124 self.map.entry(cell_type).or_default().insert(cell_name);
125 }
126 }
127
128 // The sub operation, but when the self is a map and rhs is a set of tuples.
129 fn sub_set(&mut self, rhs: TypeNameSet) {
130 for (cell_type, cell_name) in rhs {
131 self.map.entry(cell_type).or_default().remove(&cell_name);
132 }
133 }
134
135 // edits self to equal self | rhs. Faster than self | rhs but must take rhs
136 // ownership and not &rhs.
137 fn or(&mut self, rhs: Prop) {
138 for (cell_type, cell_names) in rhs.map {
139 self.map.entry(cell_type).or_default().extend(cell_names);
140 }
141 }
142
143 // edits self to equal self intersect rhs. Must take ownership of rhs
144 // ownership and not &rhs.
145 fn intersect(&mut self, mut rhs: Prop) {
146 for (cell_type, cell_names) in self.map.iter_mut() {
147 let empty_hash = HashSet::new();
148 let entry: HashSet<Id> =
149 rhs.map.remove(cell_type).unwrap_or(empty_hash);
150 cell_names.retain(|cell| entry.contains(cell));
151 }
152 }
153
154 // edits self to equal self - rhs. Faster than self - rhs but must take rhs
155 // ownership and not &rhs.
156 fn sub(&mut self, rhs: Prop) {
157 for (cell_type, cell_names) in rhs.map {
158 self.map
159 .entry(cell_type)
160 .or_default()
161 .retain(|cell| !cell_names.contains(cell));
162 }
163 }
164}
165
166/// This analysis implements a parallel version of a classic liveness analysis.
167/// For each group or invoke, it returns a list of the state shareable cells
168/// that are "alive" during an execution of a group or invoke statement (we
169/// identify an invoke statement by the cell that is being invoked, and groups
170/// by the name of the group).
171///
172/// ## Parallel Analog to a CFG
173/// The `par` statement introduces a new kind of control branching that can
174/// not be captured by a traditional CFG.
175///
176/// Consider whether `x` is alive at `foo` in the following program.
177/// ```
178/// seq {
179/// wr_x; // writes register x
180/// foo;
181/// par {
182/// wr_x2; // writes register x
183/// bar;
184/// }
185/// rd_x; // reads register x
186/// }
187/// ```
188/// `x` is not alive at `foo` because there are no reads to `x` before
189/// `wr_x2` is executed which writes to `x` again. Note that `wr_x2` is always
190/// executed.
191///
192/// We might try and represent the `par` branching with a normal CFG like this:
193/// ```
194/// +------+
195/// | wr_x |
196/// +--+---+
197/// |
198/// v
199/// +--+--+
200/// +--+ foo +--+
201/// | +-----+ |
202/// | |
203/// v v
204/// +--+----+ +--+--+
205/// | wr_x2 | | bar |
206/// +--+----+ +--+--+
207/// | |
208/// +------+----+
209/// |
210/// v
211/// +------+
212/// | rd_x |
213/// +------+
214/// ```
215/// But then this program is identical to
216/// ```
217/// seq {
218/// wr_x; // writes register x
219/// foo;
220/// if blah.out with B {
221/// wr_x2; // writes register x
222/// } else {
223/// bar;
224/// }
225/// rd_x; // reads register x
226/// }
227/// ```
228/// which has different semantics. In particular `x` is still alive at `foo` because
229/// `wr_x2` may not be executed.
230///
231/// We need to augment the traditional CFG to account for `par`.
232///
233/// ## A Parallel CFG
234/// The representation should:
235/// 1) Have the same properties as a normal CFG when no parallelism is present.
236/// 2) Threads of a `par` block should not have to know that they are in a `par` (i.e. are just CFGs themselves)
237/// 3) External to the `par` block, the information of running all threads in `par` should be visible.
238///
239/// To address these concerns, we use a parallel CFG (pCFG) based on
240/// [Analyzing programs with explicit parallelism](https://link.springer.com/chapter/10.1007%2FBFb0038679).
241/// We introduce a new kind of node in the CFG called a `par node`. A `par node` represents an entire
242/// `par` block. The above program with `par` would look like:
243/// ```
244/// +------+
245/// | wr_x |
246/// +--+---+
247/// |
248/// v
249/// +--+--+
250/// | foo |
251/// +--+--+
252/// |
253/// v
254/// +--+---+
255/// | par1 |
256/// +--+---+
257/// |
258/// v
259/// +--+---+
260/// | rd_x |
261/// +------+
262/// ```
263/// For each `par node`, we associate a list of pCFGs where each pCFG represents a thread.
264/// Each thread starts with a `begin par` node and ends with a `end par` node.
265///
266/// These are the graphs associated with `par1`.
267/// ```
268/// First thread: Second thread:
269/// +----------+ +----------+
270/// |begin par1| |begin par1|
271/// +--+-------+ +-+--------+
272/// | |
273/// v v
274/// +--+--+ +-+-+
275/// |wr_x2| |bar|
276/// +--+--+ +-+-+
277/// | |
278/// v v
279/// +--+-----+ +-+------+
280/// |end par1| |end par1|
281/// +--------+ +--------+
282/// ```
283///
284/// The idea with the `begin/end parx` nodes is that these will handle the flow
285/// of information in and out of the threads. For example, you could write these equations:
286/// ```
287/// out(begin par1) = in(par1)
288/// out(par1) = join over all in(end par1)
289/// ```
290///
291/// ## Definition of Liveness
292/// Now we finally come to the definition of "liveness" and how we use the pCFG to compute this.
293///
294/// We say a cell `x` is "live" at a node `p` in the CFG if there is a write to `x` ordered before
295/// `p` (such that there are no more writes to `x` at a point between that and `p`) and if there is a read
296/// of `x` ordered after `p` (such that there are no writes between that and `p`).
297///
298/// We define the following equations (assuming a reversed direction dataflow analysis):
299/// ```
300/// for some node n:
301/// gen(n) = registers that may be read in n
302/// kill(n) = register that must be written to in n
303/// live_in(n) = union over live_out(pred(n))
304/// live_out(n) = (live_in(n) - kill(n)) + gen(n)
305/// for some par node p:
306/// gen(p) = union over gen(n) for sub-nodes n in p
307/// kill(p) = union over kill(n) for sub-nodes n in p
308/// live_in(p) = union over live_out(pred(p))
309/// live_out(p) = (live_in(p) - kill(p)) + gen(p)
310/// ```
311/// The main place this analysis differs from traditional liveness analysis
312/// is the definition of `gen(p)` and `kill(p)` for `par` nodes. These are the
313/// union of the `gen`s and `kill`s of all of their sub-nodes. Intuitively we
314/// are treating `par` blocks as if they were just a single group. Note that this
315/// is overly conservative because we are potentially ignoring ordering
316/// information of the threads.
317#[derive(Default)]
318pub struct LiveRangeAnalysis {
319 /// Map from node ids (i.e., group enables or invokes) names
320 /// to the components live inside them.
321 live: HashMap<u64, Prop>,
322 /// Groups that have been identified as variable-like.
323 /// Mapping from group name to Some(type, name) where type is the cell type and
324 /// name is the cell name. If group is not variable like, maps to None.
325 variable_like: HashMap<ir::Id, Option<(ir::CellType, ir::Id)>>,
326 /// Set of state shareable components (as type names)
327 state_share: ShareSet,
328 /// Set of shareable components (as type names)
329 share: ShareSet,
330 /// maps invokes/enable ids to the shareable cell types/names used in them
331 invokes_enables_map: HashMap<u64, TypeNameSet>,
332 /// maps comb groups of if/while statements to the cell types/
333 /// names used in them
334 cgroup_uses_map: HashMap<u64, TypeNameSet>,
335}
336
337impl Debug for LiveRangeAnalysis {
338 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
339 writeln!(f, "Live variables {{")?;
340 for (k, v) in self.live.iter() {
341 writeln!(f, " {k}: {v:?}")?;
342 }
343 write!(f, "}}")
344 }
345}
346
347impl LiveRangeAnalysis {
348 /// Construct a live range analysis.
349 pub fn new(
350 control: &mut ir::Control,
351 state_share: ShareSet,
352 share: ShareSet,
353 only_run_once: bool,
354 ) -> Self {
355 let mut ranges = LiveRangeAnalysis {
356 state_share,
357 share,
358 ..Default::default()
359 };
360
361 // Give each control statement a unique "NODE_ID" attribute.
362 ControlId::compute_unique_ids(control, 0, false);
363
364 let (alive, gens, kills) = ranges.build_live_ranges(
365 control,
366 Prop::default(),
367 Prop::default(),
368 Prop::default(),
369 );
370 // If the component could run more than once, than we have to feed the
371 // output alive,gens,kills, back into the control and run the algorithm
372 // again.
373 if !only_run_once {
374 ranges.build_live_ranges(control, alive, gens, kills);
375 }
376
377 for (node, cells_by_type) in &ranges.invokes_enables_map {
378 if let Some(prop) = ranges.live.get_mut(node) {
379 prop.or_set(cells_by_type.clone());
380 }
381 }
382
383 ranges
384 }
385
386 // updates live_cell_map and live_once_map
387 // maps all cells live at node `id` to node `id` in `live_cells_map`,
388 // and maps all cells live at node `id` to `parents` in `live_once_map`.
389 fn update_live_control_data(
390 &self,
391 id: u64,
392 live_once_map: &mut LiveMapByType,
393 live_cell_map: &mut LiveMapByType,
394 parents: &HashSet<u64>,
395 ) {
396 let live_set = self.live.get(&id).unwrap().map.clone();
397 for (cell_type, live_cells) in live_set {
398 let cell_to_node =
399 live_cell_map.entry(cell_type.clone()).or_default();
400 let cell_to_control = live_once_map.entry(cell_type).or_default();
401 for cell in live_cells {
402 cell_to_node.entry(cell).or_default().insert(id);
403 cell_to_control.entry(cell).or_default().extend(parents);
404 }
405 }
406 }
407
408 fn add_cell_to_control_data(
409 id: u64,
410 (cell_type, cell_name): &(ir::CellType, ir::Id),
411 live_once_map: &mut LiveMapByType,
412 live_cell_map: &mut LiveMapByType,
413 parents: &HashSet<u64>,
414 ) {
415 // add cell as live within whichever direct children of
416 // par blocks they're located within
417 if !parents.is_empty() {
418 live_once_map
419 .entry(cell_type.clone())
420 .or_default()
421 .entry(*cell_name)
422 .or_default()
423 .extend(parents);
424 }
425 // mark cell as live in the control id
426 // If id corresponds to an if/while guard,
427 // what is really means, is that the cell is live
428 // at the comb group/port guard of the if/while statement
429 live_cell_map
430 .entry(cell_type.clone())
431 .or_default()
432 .entry(*cell_name)
433 .or_default()
434 .insert(id);
435 }
436
437 fn get_live_control_data_static(
438 &self,
439 live_once_map: &mut LiveMapByType,
440 par_thread_map: &mut HashMap<u64, u64>,
441 live_cell_map: &mut LiveMapByType,
442 parents: &HashSet<u64>,
443 sc: &ir::StaticControl,
444 ) {
445 match sc {
446 ir::StaticControl::Empty(_) => (),
447 ir::StaticControl::Enable(_) | ir::StaticControl::Invoke(_) => {
448 let id = ControlId::get_guaranteed_id_static(sc);
449 self.update_live_control_data(
450 id,
451 live_once_map,
452 live_cell_map,
453 parents,
454 )
455 }
456 ir::StaticControl::Repeat(ir::StaticRepeat { body, .. }) => {
457 self.get_live_control_data_static(
458 live_once_map,
459 par_thread_map,
460 live_cell_map,
461 parents,
462 body,
463 );
464 }
465 ir::StaticControl::Seq(ir::StaticSeq { stmts, .. }) => {
466 for stmt in stmts {
467 self.get_live_control_data_static(
468 live_once_map,
469 par_thread_map,
470 live_cell_map,
471 parents,
472 stmt,
473 );
474 }
475 }
476 ir::StaticControl::Par(ir::StaticPar { stmts, .. }) => {
477 let parent_id = ControlId::get_guaranteed_id_static(sc);
478 let mut new_parents = parents.clone();
479 for stmt in stmts {
480 // building par_thread_map
481 let child_id = ControlId::get_guaranteed_id_static(stmt);
482 par_thread_map.insert(child_id, parent_id);
483
484 // building live_once_map by adding child_id to parents when
485 // we recursively call get_live_control_data on each child
486 new_parents.insert(child_id);
487 self.get_live_control_data_static(
488 live_once_map,
489 par_thread_map,
490 live_cell_map,
491 &new_parents,
492 stmt,
493 );
494 new_parents.remove(&child_id);
495 }
496 }
497 ir::StaticControl::If(ir::StaticIf {
498 port,
499 tbranch,
500 fbranch,
501 ..
502 }) => {
503 self.get_live_control_data_static(
504 live_once_map,
505 par_thread_map,
506 live_cell_map,
507 parents,
508 tbranch,
509 );
510 self.get_live_control_data_static(
511 live_once_map,
512 par_thread_map,
513 live_cell_map,
514 parents,
515 fbranch,
516 );
517 let id = ControlId::get_guaranteed_id_static(sc);
518 // Examining the cell read from in the if guard
519 if let Some(cell_info) = LiveRangeAnalysis::port_to_cell_name(
520 port,
521 &self.state_share,
522 ) {
523 Self::add_cell_to_control_data(
524 id,
525 &cell_info,
526 live_once_map,
527 live_cell_map,
528 parents,
529 )
530 }
531 }
532 }
533 }
534
535 /// Updates live_once_map and par_thread_map.
536 /// live_once_map should map celltypes to a map, which should map cells of
537 /// celltype to control statements in which it is live for at least one group
538 /// or invoke in the control. We only map to control statements that are
539 /// direct children of par blocks.
540 /// par_thread_map maps direct children of par blocks to their parents
541 /// live_cell_map maps cells to the nodes in which it is live
542 /// par_thread_map maps direct children of par blocks to their parents
543 /// parents is the list of current control statements (that are direct children
544 /// of par blocks) that are parents (at any level of nesting) of c.
545 pub fn get_live_control_data(
546 &self,
547 live_once_map: &mut LiveMapByType,
548 par_thread_map: &mut HashMap<u64, u64>,
549 live_cell_map: &mut LiveMapByType,
550 parents: &HashSet<u64>,
551 c: &ir::Control,
552 ) {
553 match c {
554 ir::Control::Empty(_) => (),
555 ir::Control::Par(ir::Par { stmts, .. }) => {
556 let parent_id = ControlId::get_guaranteed_id(c);
557 let mut new_parents = parents.clone();
558 for stmt in stmts {
559 // building par_thread_map
560 let child_id = ControlId::get_guaranteed_id(stmt);
561 par_thread_map.insert(child_id, parent_id);
562
563 // building live_once_map by adding child_id to parents when
564 // we recursively call get_live_control_data on each child
565 new_parents.insert(child_id);
566 self.get_live_control_data(
567 live_once_map,
568 par_thread_map,
569 live_cell_map,
570 &new_parents,
571 stmt,
572 );
573 new_parents.remove(&child_id);
574 }
575 }
576 ir::Control::Seq(ir::Seq { stmts, .. }) => {
577 for stmt in stmts {
578 self.get_live_control_data(
579 live_once_map,
580 par_thread_map,
581 live_cell_map,
582 parents,
583 stmt,
584 );
585 }
586 }
587 ir::Control::If(ir::If {
588 tbranch, fbranch, ..
589 }) => {
590 self.get_live_control_data(
591 live_once_map,
592 par_thread_map,
593 live_cell_map,
594 parents,
595 tbranch,
596 );
597 self.get_live_control_data(
598 live_once_map,
599 par_thread_map,
600 live_cell_map,
601 parents,
602 fbranch,
603 );
604 let id = ControlId::get_guaranteed_id(c);
605 // Examining all the cells used at the comb group of the if stmt
606 if let Some(comb_group_uses) = self.cgroup_uses_map.get(&id) {
607 for cell_info in comb_group_uses {
608 Self::add_cell_to_control_data(
609 id,
610 cell_info,
611 live_once_map,
612 live_cell_map,
613 parents,
614 )
615 }
616 }
617 }
618 ir::Control::While(ir::While { body, .. }) => {
619 self.get_live_control_data(
620 live_once_map,
621 par_thread_map,
622 live_cell_map,
623 parents,
624 body,
625 );
626 let id = ControlId::get_guaranteed_id(c);
627 if let Some(comb_group_uses) = self.cgroup_uses_map.get(&id) {
628 for (cell_type, cell_name) in comb_group_uses {
629 if !parents.is_empty() {
630 live_once_map
631 .entry(cell_type.clone())
632 .or_default()
633 .entry(*cell_name)
634 .or_default()
635 .extend(parents);
636 }
637 live_cell_map
638 .entry(cell_type.clone())
639 .or_default()
640 .entry(*cell_name)
641 .or_default()
642 .insert(id);
643 }
644 }
645 }
646 ir::Control::Repeat(ir::Repeat { body, .. }) => {
647 self.get_live_control_data(
648 live_once_map,
649 par_thread_map,
650 live_cell_map,
651 parents,
652 body,
653 );
654 }
655 ir::Control::Enable(_) | ir::Control::Invoke(_) => {
656 let id = ControlId::get_guaranteed_id(c);
657 self.update_live_control_data(
658 id,
659 live_once_map,
660 live_cell_map,
661 parents,
662 )
663 }
664 ir::Control::Static(sc) => self.get_live_control_data_static(
665 live_once_map,
666 par_thread_map,
667 live_cell_map,
668 parents,
669 sc,
670 ),
671 ir::Control::FSMEnable(_) => {
672 todo!("should not encounter fsm nodes")
673 }
674 }
675 }
676
677 /// Look up the set of things live at a node (i.e. group or invoke) definition.
678 pub fn get(&self, node: &u64) -> &CellsByType {
679 &self
680 .live
681 .get(node)
682 .unwrap_or_else(|| panic!("Live set missing for {node}"))
683 .map
684 }
685
686 /// Get a unique list of all live cells in `component`.
687 pub fn get_all(&self) -> impl Iterator<Item = ir::Id> + '_ {
688 self.live
689 .iter()
690 .flat_map(|(_, set)| {
691 set.map.iter().fold(HashSet::new(), |mut acc, (_, set)| {
692 acc.extend(set);
693 acc
694 })
695 })
696 .unique()
697 .cloned()
698 }
699
700 fn variable_like(
701 &mut self,
702 grp: &RRC<ir::Group>,
703 ) -> &Option<(ir::CellType, ir::Id)> {
704 let group = grp.borrow();
705 let name = &group.name();
706 if !self.variable_like.contains_key(name) {
707 let res = VariableDetection::variable_like(grp, &self.state_share);
708 self.variable_like.insert(grp.borrow().name(), res);
709 }
710 &self.variable_like[name]
711 }
712
713 /// Compute the `gen` and `kill` sets for a given group definition. Because
714 /// we can't always know if a group will *definitely* kill something or *definitely*
715 /// read something, this function is conservative.
716 ///
717 /// However, it is conservative in different directions for `gens` and `kills`.
718 /// In particular, it is always ok to accidentally put something in `gens` because
719 /// in the worst case we say something is alive when it isn't.
720 ///
721 /// However, it is **never** ok to accidentally put something in `writes` because
722 /// we might accidentally kill something that should be alive.
723 ///
724 /// To implement this, we say that something is being read if it shows up on the rhs
725 /// of any assignment in a group. Something is written if it it's guard is `1` or if it has no guard.
726 fn find_gen_kill_group(
727 &mut self,
728 group_ref: &RRC<ir::Group>,
729 ) -> (TypeNameSet, TypeNameSet) {
730 let group = group_ref.borrow();
731 let maybe_var = self.variable_like(group_ref).clone();
732 let sc_clone = &self.state_share;
733 // if the group contains what looks like a variable write,
734 // then just add variable to write set
735 if let Some((cell_type, variable)) = maybe_var {
736 // we don't want to read the control signal of `variable`
737 let assignments = group
738 .assignments
739 .iter()
740 .filter(|asgn| {
741 !(asgn.src.borrow().get_parent_name() == variable
742 && asgn.src.borrow().name == "done")
743 })
744 .filter(|asgn| {
745 if let ir::Guard::Port(port) = &*asgn.guard {
746 !(port.borrow().get_parent_name() == variable
747 && port.borrow().name == "done")
748 } else {
749 true
750 }
751 });
752
753 // calculate reads, but ignore `variable`. we've already dealt with that
754 let reads: HashSet<_> = assignments
755 .analysis()
756 .cell_reads()
757 .filter(|c| sc_clone.is_shareable_component(c))
758 .map(|c| (c.borrow().prototype.clone(), c.borrow().name()))
759 .collect();
760
761 let mut writes = HashSet::new();
762 writes.insert((cell_type, variable));
763
764 (reads, writes)
765 } else {
766 let reads: HashSet<_> =
767 meaningful_read_set(group.assignments.iter())
768 .filter(|c| sc_clone.is_shareable_component(c))
769 .map(|c| (c.borrow().prototype.clone(), c.borrow().name()))
770 .collect();
771
772 // only consider write assignments where the guard is true
773 let assignments = group
774 .assignments
775 .iter()
776 .filter(|asgn| *asgn.guard == ir::Guard::True)
777 .cloned()
778 .collect::<Vec<_>>();
779
780 let writes: HashSet<_> = assignments
781 .iter()
782 .analysis()
783 .cell_writes()
784 .filter(|c| sc_clone.is_shareable_component(c))
785 .map(|c| (c.borrow().prototype.clone(), c.borrow().name()))
786 .collect();
787
788 (reads, writes)
789 }
790 }
791
792 // TODO(calebmkim) TODO(paili0628): This is similar to find_static_group right now
793 // We could eventually try to merge it, but we should do it after we have
794 // hammered down the details of the rest of the static IR assignments
795 fn find_gen_kill_static_group(
796 &mut self,
797 group_ref: &RRC<ir::StaticGroup>,
798 ) -> (TypeNameSet, TypeNameSet) {
799 let group = group_ref.borrow();
800 // we don't have to worry about variable like for static groups
801 let sc_clone = &self.state_share;
802 let reads: HashSet<_> = meaningful_read_set(group.assignments.iter())
803 .filter(|c| sc_clone.is_shareable_component(c))
804 .map(|c| (c.borrow().prototype.clone(), c.borrow().name()))
805 .collect();
806 // only consider write assignments where the guard is true
807 let assignments = group
808 .assignments
809 .iter()
810 .filter(|asgn| *asgn.guard == ir::Guard::True)
811 .cloned()
812 .collect::<Vec<_>>();
813
814 let writes: HashSet<_> = assignments
815 .iter()
816 .analysis()
817 .cell_writes()
818 .filter(|c| sc_clone.is_shareable_component(c))
819 .map(|c| (c.borrow().prototype.clone(), c.borrow().name()))
820 .collect();
821
822 (reads, writes)
823 }
824
825 fn find_uses_assigns<T>(
826 assigns: &[ir::Assignment<T>],
827 shareable_components: &ShareSet,
828 ) -> TypeNameSet {
829 assigns
830 .iter()
831 .analysis()
832 .cell_uses()
833 .filter(|cell| shareable_components.is_shareable_component(cell))
834 .map(|cell| (cell.borrow().prototype.clone(), cell.borrow().name()))
835 .collect::<HashSet<_>>()
836 }
837
838 // returns (share_uses, state_reads), which are the uses of shareable components
839 // and reads of state shareable components
840 fn uses_reads_cgroup(
841 group_ref: &RRC<ir::CombGroup>,
842 shareable: &ShareSet,
843 state_shareable: &ShareSet,
844 ) -> (TypeNameSet, TypeNameSet) {
845 let group = group_ref.borrow();
846 let share_uses = group
847 .assignments
848 .iter()
849 .analysis()
850 .cell_uses()
851 .filter(|cell| shareable.is_shareable_component(cell))
852 .map(|cell| (cell.borrow().prototype.clone(), cell.borrow().name()))
853 .collect::<HashSet<_>>();
854 let state_reads = group
855 .assignments
856 .iter()
857 .analysis()
858 .reads()
859 .cells()
860 .filter(|cell| state_shareable.is_shareable_component(cell))
861 .map(|cell| (cell.borrow().prototype.clone(), cell.borrow().name()))
862 .collect::<HashSet<_>>();
863 (share_uses, state_reads)
864 }
865
866 fn port_to_cell_name(
867 port: &RRC<ir::Port>,
868 shareable_components: &ShareSet,
869 ) -> Option<(ir::CellType, ir::Id)> {
870 if let ir::PortParent::Cell(cell_wref) = &port.borrow().parent {
871 let cell = cell_wref.upgrade();
872 if shareable_components.is_shareable_component(&cell) {
873 return Some((
874 cell.borrow().prototype.clone(),
875 cell.borrow().name(),
876 ));
877 }
878 }
879 None
880 }
881
882 // gets the gens/kills (aka reads/writes) of the invoke given inputs, outputs, and comb group.
883 fn gen_kill_invoke(
884 inputs: &[(ir::Id, ir::RRC<ir::Port>)],
885 outputs: &[(ir::Id, ir::RRC<ir::Port>)],
886 comb_group_info: &Option<ir::RRC<ir::CombGroup>>,
887 comp: &ir::RRC<ir::Cell>,
888 shareable_components: &ShareSet,
889 ) -> (TypeNameSet, TypeNameSet) {
890 // The writes of the invoke include its outputs. Also, we count the cell
891 // being invoked as being written to.
892 let mut write_set: TypeNameSet = outputs
893 .iter()
894 .filter_map(|(_, src)| {
895 Self::port_to_cell_name(src, shareable_components)
896 })
897 .collect();
898
899 if shareable_components.is_shareable_component(comp) {
900 write_set.insert((
901 comp.borrow().prototype.clone(),
902 comp.borrow().name(),
903 ));
904 }
905
906 // The reads of the invoke include its inputs.
907 // One quick note: since the component is written to, there is no need to include this
908 // component as being read from since we know the write to the component
909 // precedes the read from it, due to the nature of `invoke` statements.
910 // This is "cheating" in a sense, since the component is technically being
911 // read from. However, since we know that there is a write to the component
912 // that that precedes the read from it within the very same invoke statement,
913 // it "appears" to all the other control statements in the program that the
914 // component is not being read from in the invoke statement.
915 let mut read_set: TypeNameSet = inputs
916 .iter()
917 .filter_map(|(_, src)| {
918 Self::port_to_cell_name(src, shareable_components)
919 })
920 .collect();
921
922 if let Some(comb_group) = comb_group_info {
923 read_set.extend(
924 comb_group
925 .borrow()
926 .assignments
927 .iter()
928 .analysis()
929 .reads()
930 .cells()
931 .filter(|cell| {
932 shareable_components.is_shareable_component(cell)
933 })
934 .map(|cell| {
935 (cell.borrow().prototype.clone(), cell.borrow().name())
936 }),
937 );
938 }
939
940 (read_set, write_set)
941 }
942
943 // gets the uses of the invoke given inputs, outputs, and comb group.
944 // Should include any cell that is either read from or written to at all
945 // in the invoke statement (including the comb group)
946 fn uses_invoke(
947 inputs: &[(ir::Id, ir::RRC<ir::Port>)],
948 outputs: &[(ir::Id, ir::RRC<ir::Port>)],
949 comb_group_info: &Option<ir::RRC<ir::CombGroup>>,
950 shareable_components: &ShareSet,
951 ) -> TypeNameSet {
952 // uses of shareable components in the invoke statement
953 let mut uses: TypeNameSet = inputs
954 .iter()
955 .chain(outputs.iter())
956 .filter_map(|(_, src)| {
957 Self::port_to_cell_name(src, shareable_components)
958 })
959 .collect();
960 // uses of shareable components in the comb group (if it exists)
961 if let Some(comb_group) = &comb_group_info {
962 uses.extend(
963 comb_group
964 .borrow()
965 .assignments
966 .iter()
967 .analysis()
968 .cell_uses()
969 .filter(|cell| {
970 shareable_components.is_shareable_component(cell)
971 })
972 .map(|cell| {
973 (cell.borrow().prototype.clone(), cell.borrow().name())
974 }),
975 );
976 };
977 uses
978 }
979
980 // updates liveness for an invoke: build to handle either static or dynamic invokes
981 // invoke_info = (inputs, outputs) of invoke
982 // comp = comp being invokes
983 // comb_group_invo = Option<comb group if invoke has one>
984 // liveness_info = (alive, gens, kills) coming into the invoke
985 // returns the (alive, gens, kills) based on the invoke info
986 // also updates self.invokes_enables_map using the input information
987 fn update_invoke_liveness(
988 &mut self,
989 invoke_info: InvokeInfo,
990 comb_group_info: &Option<ir::RRC<ir::CombGroup>>,
991 comp: &ir::RRC<ir::Cell>,
992 id: u64,
993 liveness_info: (Prop, Prop, Prop),
994 ) -> (Prop, Prop, Prop) {
995 let (inputs, outputs) = invoke_info;
996 let (mut alive, mut gens, mut kills) = liveness_info;
997
998 // get uses of all shareable components, and then update self.invokes_enables_map
999 let uses_shareable =
1000 Self::uses_invoke(inputs, outputs, comb_group_info, &self.share);
1001
1002 self.invokes_enables_map
1003 .entry(id)
1004 .or_default()
1005 .extend(uses_shareable);
1006
1007 // get the reads and writes of the invoke, and use that to determine livenes propogation
1008 let (reads, writes) = LiveRangeAnalysis::gen_kill_invoke(
1009 inputs,
1010 outputs,
1011 comb_group_info,
1012 comp,
1013 &self.state_share,
1014 );
1015
1016 alive.transfer_set(reads.clone(), writes.clone());
1017 let alive_out = alive.clone();
1018
1019 // set the live set of this node to be the things live on the
1020 // output of this node plus the things written to in this invoke
1021 // plus all shareable components used
1022 self.live.insert(id, {
1023 alive.or_set(writes.clone());
1024 alive
1025 });
1026 (
1027 alive_out,
1028 {
1029 gens.sub_set(writes.clone());
1030 gens.or_set(reads);
1031 gens
1032 },
1033 {
1034 kills.or_set(writes);
1035 kills
1036 },
1037 )
1038 }
1039
1040 // Updates Live Range Analysis
1041 // id should correspond to the id of an enable, and assigns should correspond
1042 // to the assignments in that enable
1043 // reads and writes should be the reads/writes of the assigns
1044 // alive, gens, kills are the alive, gens, and kills coming into the enable
1045 // returns the alive, gens, and kills leaving the enable
1046 // It also updates self.live at id to be the cells live at live
1047 // It also updates self.invokes_enables_map
1048 fn update_group_liveness<T>(
1049 &mut self,
1050 assigns: &[ir::Assignment<T>],
1051 id: u64,
1052 read_write_info: ReadWriteInfo,
1053 mut alive: Prop,
1054 mut gens: Prop,
1055 mut kills: Prop,
1056 ) -> (Prop, Prop, Prop) {
1057 let uses_share =
1058 LiveRangeAnalysis::find_uses_assigns(assigns, &self.share);
1059 self.invokes_enables_map
1060 .entry(id)
1061 .or_default()
1062 .extend(uses_share);
1063 let (reads, writes) = read_write_info;
1064 // compute transfer function
1065 alive.transfer_set(reads.clone(), writes.clone());
1066 let alive_out = alive.clone();
1067
1068 // set the live set of this node to be the things live on the
1069 // output of this node plus the things written to in this group
1070 self.live.insert(id, {
1071 alive.or_set(writes.clone());
1072 alive
1073 });
1074 (
1075 alive_out,
1076 {
1077 gens.sub_set(writes.clone());
1078 gens.or_set(reads);
1079 gens
1080 },
1081 {
1082 kills.or_set(writes);
1083 kills
1084 },
1085 )
1086 }
1087
1088 fn build_live_ranges_static(
1089 &mut self,
1090 sc: &ir::StaticControl,
1091 alive: Prop,
1092 gens: Prop,
1093 kills: Prop,
1094 ) -> (Prop, Prop, Prop) {
1095 match sc {
1096 ir::StaticControl::Empty(_) => (alive, gens, kills),
1097 ir::StaticControl::Enable(ir::StaticEnable { group, .. }) => {
1098 // XXX(sam) no reason to compute this every time
1099 let (reads, writes) = self.find_gen_kill_static_group(group);
1100 self.update_group_liveness(
1101 &group.borrow().assignments,
1102 ControlId::get_guaranteed_id_static(sc),
1103 (reads, writes),
1104 alive,
1105 gens,
1106 kills,
1107 )
1108 }
1109 ir::StaticControl::Repeat(ir::StaticRepeat { body, .. }) => {
1110 let (a, g, k) =
1111 self.build_live_ranges_static(body, alive, gens, kills);
1112 // Have to go through the repeat body twice in order to get a
1113 // correct live range analysis
1114 self.build_live_ranges_static(body, a, g, k)
1115 }
1116 ir::StaticControl::Seq(ir::StaticSeq { stmts, .. }) => stmts
1117 .iter()
1118 .rev()
1119 .fold((alive, gens, kills), |(alive, gens, kills), e| {
1120 self.build_live_ranges_static(e, alive, gens, kills)
1121 }),
1122 ir::StaticControl::Par(ir::StaticPar { stmts, .. }) => {
1123 let (mut alive, gens, kills) = stmts
1124 .iter()
1125 .rev()
1126 .map(|e| {
1127 self.build_live_ranges_static(
1128 e,
1129 alive.clone(),
1130 Prop::default(),
1131 Prop::default(),
1132 )
1133 })
1134 .fold(
1135 (Prop::default(), Prop::default(), Prop::default()),
1136 |(mut acc_alive, mut acc_gen, mut acc_kill),
1137 (alive, r#gen, kill)| {
1138 (
1139 // Doing in place operations saves time
1140 {
1141 acc_alive.or(alive);
1142 acc_alive
1143 },
1144 {
1145 acc_gen.or(r#gen);
1146 acc_gen
1147 },
1148 {
1149 acc_kill.or(kill);
1150 acc_kill
1151 },
1152 )
1153 },
1154 );
1155 // should only count as a "gen" if it is alive on at least one
1156 // of the outputs of the child node
1157 alive.transfer(gens.clone(), kills.clone());
1158 (alive, gens, kills)
1159 }
1160 ir::StaticControl::If(ir::StaticIf {
1161 tbranch,
1162 fbranch,
1163 port,
1164 ..
1165 }) => {
1166 // compute each branch
1167 let (mut t_alive, mut t_gens, mut t_kills) = self
1168 .build_live_ranges_static(
1169 tbranch,
1170 alive.clone(),
1171 gens.clone(),
1172 kills.clone(),
1173 );
1174 let (f_alive, f_gens, f_kills) =
1175 self.build_live_ranges_static(fbranch, alive, gens, kills);
1176
1177 // take union
1178 t_alive.or(f_alive);
1179 t_gens.or(f_gens);
1180 // kills must take intersection to be conservative
1181 t_kills.intersect(f_kills);
1182
1183 // add if guard cell to the alive/gens sets
1184 if let Some(cell_info) = LiveRangeAnalysis::port_to_cell_name(
1185 port,
1186 &self.state_share,
1187 ) {
1188 t_alive.insert(cell_info.clone());
1189 t_gens.insert(cell_info);
1190 }
1191
1192 (t_alive, t_gens, t_kills)
1193 }
1194 ir::StaticControl::Invoke(ir::StaticInvoke {
1195 inputs,
1196 outputs,
1197 comp,
1198 ..
1199 }) => {
1200 //get the shareable components used in the invoke stmt
1201 self.update_invoke_liveness(
1202 (inputs, outputs),
1203 &None,
1204 comp,
1205 ControlId::get_guaranteed_id_static(sc),
1206 (alive, gens, kills),
1207 )
1208 }
1209 }
1210 }
1211
1212 /// Implements the parallel dataflow analysis that computes the liveness of every state shareable component
1213 /// at every point in the program.
1214 fn build_live_ranges(
1215 &mut self,
1216 c: &ir::Control,
1217 alive: Prop,
1218 gens: Prop,
1219 kills: Prop,
1220 ) -> (Prop, Prop, Prop) {
1221 match c {
1222 ir::Control::Empty(_) => (alive, gens, kills),
1223 ir::Control::Invoke(ir::Invoke {
1224 inputs,
1225 outputs,
1226 comb_group,
1227 comp,
1228 ..
1229 }) => self.update_invoke_liveness(
1230 (inputs, outputs),
1231 comb_group,
1232 comp,
1233 ControlId::get_guaranteed_id(c),
1234 (alive, gens, kills),
1235 ),
1236 ir::Control::Enable(ir::Enable { group, .. }) => {
1237 // XXX(sam) no reason to compute this every time
1238 let (reads, writes) = self.find_gen_kill_group(group);
1239
1240 self.update_group_liveness(
1241 &group.borrow().assignments,
1242 ControlId::get_guaranteed_id(c),
1243 (reads, writes),
1244 alive,
1245 gens,
1246 kills,
1247 )
1248 }
1249 ir::Control::Seq(ir::Seq { stmts, .. }) => stmts.iter().rev().fold(
1250 (alive, gens, kills),
1251 |(alive, gens, kills), e| {
1252 self.build_live_ranges(e, alive, gens, kills)
1253 },
1254 ),
1255 ir::Control::If(ir::If {
1256 tbranch,
1257 fbranch,
1258 port,
1259 cond,
1260 ..
1261 }) => {
1262 // compute each branch
1263 let (mut t_alive, mut t_gens, mut t_kills) = self
1264 .build_live_ranges(
1265 tbranch,
1266 alive.clone(),
1267 gens.clone(),
1268 kills.clone(),
1269 );
1270 let (f_alive, f_gens, f_kills) =
1271 self.build_live_ranges(fbranch, alive, gens, kills);
1272
1273 // take union
1274 t_alive.or(f_alive);
1275 t_gens.or(f_gens);
1276 // kills must be intersection to be conservative
1277 t_kills.intersect(f_kills);
1278
1279 let id = ControlId::get_guaranteed_id(c);
1280
1281 // reads from state shareable components in the comb group
1282 // These should get "passed on" as live/gens as we go up the
1283 // control flow of the program
1284 let mut cgroup_reads: TypeNameSet = HashSet::new();
1285 // Any uses of any shareable components in the comb group.
1286 let mut shareable_uses: TypeNameSet = HashSet::new();
1287
1288 if let Some(comb_group) = cond {
1289 let (share_uses, state_reads) = Self::uses_reads_cgroup(
1290 comb_group,
1291 &self.share,
1292 &self.state_share,
1293 );
1294 shareable_uses = share_uses;
1295 cgroup_reads = state_reads;
1296 }
1297
1298 if let Some(cell_info) = LiveRangeAnalysis::port_to_cell_name(
1299 port,
1300 &self.state_share,
1301 ) {
1302 // If we read from a state shareable component (like a register)
1303 // in the port, then we add it to cgroup_reads.
1304 cgroup_reads.insert(cell_info);
1305 }
1306 if !cgroup_reads.is_empty() || !shareable_uses.is_empty() {
1307 let mut all_uses = cgroup_reads.clone();
1308 all_uses.extend(shareable_uses);
1309 // add all uses of both shareable and state-shareable components
1310 // in the cgroup_uses_map.
1311 self.cgroup_uses_map.insert(id, all_uses);
1312 }
1313 // adding cgroup_reads as live on output of if stmt
1314 t_alive.or_set(cgroup_reads.clone());
1315 t_gens.or_set(cgroup_reads);
1316 (t_alive, t_gens, t_kills)
1317 }
1318 ir::Control::Par(ir::Par { stmts, .. }) => {
1319 let (mut alive, gens, kills) = stmts
1320 .iter()
1321 .rev()
1322 .map(|e| {
1323 self.build_live_ranges(
1324 e,
1325 alive.clone(),
1326 Prop::default(),
1327 Prop::default(),
1328 )
1329 })
1330 .fold(
1331 (Prop::default(), Prop::default(), Prop::default()),
1332 |(mut acc_alive, mut acc_gen, mut acc_kill),
1333 (alive, r#gen, kill)| {
1334 (
1335 // Doing in place operations saves time
1336 {
1337 acc_alive.or(alive);
1338 acc_alive
1339 },
1340 {
1341 acc_gen.or(r#gen);
1342 acc_gen
1343 },
1344 {
1345 acc_kill.or(kill);
1346 acc_kill
1347 },
1348 )
1349 },
1350 );
1351 // should only count as a "gen" if it is alive on at least one
1352 // of the outputs of the child node
1353 alive.transfer(gens.clone(), kills.clone());
1354 (alive, gens, kills)
1355 }
1356 ir::Control::While(ir::While {
1357 body, port, cond, ..
1358 }) => {
1359 let id = ControlId::get_guaranteed_id(c);
1360 // need this info twice, so just pre-calculate whether port is
1361 // a state shareable component.
1362 let port_if_shareable: Option<(ir::CellType, ir::Id)> =
1363 LiveRangeAnalysis::port_to_cell_name(
1364 port,
1365 &self.state_share,
1366 );
1367 // all reads from state shareable components in the comb group or port
1368 let mut cgroup_reads: TypeNameSet = HashSet::new();
1369 // all uses of shareable components in the comb group or port
1370 let mut shareable_uses: TypeNameSet = HashSet::new();
1371
1372 let input_kills = kills.clone();
1373 // Go through while body and while port + comb group once
1374 let (mut alive, mut gens, kills) =
1375 self.build_live_ranges(body, alive, gens, kills);
1376 if let Some(cell_info) = port_if_shareable {
1377 // adds port to cgroup_reads if state_shareable.
1378 cgroup_reads.insert(cell_info);
1379 }
1380 if let Some(comb_group) = cond {
1381 let (share_uses, state_reads) = Self::uses_reads_cgroup(
1382 comb_group,
1383 &self.share,
1384 &self.state_share,
1385 );
1386 shareable_uses = share_uses;
1387 cgroup_reads.extend(state_reads);
1388 }
1389 // setting alive and gens appropriately based on the updated info
1390 // from the comb group + port.
1391 alive.or_set(cgroup_reads.clone());
1392 gens.or_set(cgroup_reads.clone());
1393
1394 if !cgroup_reads.is_empty() || !shareable_uses.is_empty() {
1395 // add all uses of shareable and non-shareable components into
1396 // cgroup_uses_map
1397 let mut all_uses = cgroup_reads.clone();
1398 all_uses.extend(shareable_uses);
1399 self.cgroup_uses_map.insert(id, all_uses);
1400 }
1401
1402 // Going through the while body and guard + port once again
1403 let (mut alive, mut gens, kills) =
1404 self.build_live_ranges(body, alive, gens, kills);
1405 alive.or_set(cgroup_reads.clone());
1406 gens.or_set(cgroup_reads);
1407
1408 // we can only inlcude the kills if we know the while loop executes
1409 // at least once
1410 if let Some(val) = c.get_attribute(ir::NumAttr::Bound) {
1411 if val > 0 {
1412 return (alive, gens, kills);
1413 }
1414 }
1415
1416 (alive, gens, input_kills)
1417 }
1418 ir::Control::Repeat(ir::Repeat { body, .. }) => {
1419 let (a, g, k) =
1420 self.build_live_ranges(body, alive, gens, kills);
1421 // need to feed the live nodes on the output of the body
1422 // back into the body to get correct live range analysis
1423 self.build_live_ranges(body, a, g, k)
1424 }
1425 ir::Control::Static(sc) => {
1426 self.build_live_ranges_static(sc, alive, gens, kills)
1427 }
1428 ir::Control::FSMEnable(_) => {
1429 todo!("should not encounter fsm nodes")
1430 }
1431 }
1432 }
1433}