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, gen: Prop, kill: Prop) {
106 self.sub(kill);
107 self.or(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, gen: TypeNameSet, kill: TypeNameSet) {
117 self.sub_set(kill);
118 self.or_set(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 ) -> Self {
354 let mut ranges = LiveRangeAnalysis {
355 state_share,
356 share,
357 ..Default::default()
358 };
359
360 // Give each control statement a unique "NODE_ID" attribute.
361 ControlId::compute_unique_ids(control, 0, false);
362
363 ranges.build_live_ranges(
364 control,
365 Prop::default(),
366 Prop::default(),
367 Prop::default(),
368 );
369
370 for (node, cells_by_type) in &ranges.invokes_enables_map {
371 if let Some(prop) = ranges.live.get_mut(node) {
372 prop.or_set(cells_by_type.clone());
373 }
374 }
375
376 ranges
377 }
378
379 // updates live_cell_map and live_once_map
380 // maps all cells live at node `id` to node `id` in `live_cells_map`,
381 // and maps all cells live at node `id` to `parents` in `live_once_map`.
382 fn update_live_control_data(
383 &self,
384 id: u64,
385 live_once_map: &mut LiveMapByType,
386 live_cell_map: &mut LiveMapByType,
387 parents: &HashSet<u64>,
388 ) {
389 let live_set = self.live.get(&id).unwrap().map.clone();
390 for (cell_type, live_cells) in live_set {
391 let cell_to_node =
392 live_cell_map.entry(cell_type.clone()).or_default();
393 let cell_to_control = live_once_map.entry(cell_type).or_default();
394 for cell in live_cells {
395 cell_to_node.entry(cell).or_default().insert(id);
396 cell_to_control.entry(cell).or_default().extend(parents);
397 }
398 }
399 }
400
401 fn add_cell_to_control_data(
402 id: u64,
403 (cell_type, cell_name): &(ir::CellType, ir::Id),
404 live_once_map: &mut LiveMapByType,
405 live_cell_map: &mut LiveMapByType,
406 parents: &HashSet<u64>,
407 ) {
408 // add cell as live within whichever direct children of
409 // par blocks they're located within
410 if !parents.is_empty() {
411 live_once_map
412 .entry(cell_type.clone())
413 .or_default()
414 .entry(*cell_name)
415 .or_default()
416 .extend(parents);
417 }
418 // mark cell as live in the control id
419 // If id corresponds to an if/while guard,
420 // what is really means, is that the cell is live
421 // at the comb group/port guard of the if/while statement
422 live_cell_map
423 .entry(cell_type.clone())
424 .or_default()
425 .entry(*cell_name)
426 .or_default()
427 .insert(id);
428 }
429
430 fn get_live_control_data_static(
431 &self,
432 live_once_map: &mut LiveMapByType,
433 par_thread_map: &mut HashMap<u64, u64>,
434 live_cell_map: &mut LiveMapByType,
435 parents: &HashSet<u64>,
436 sc: &ir::StaticControl,
437 ) {
438 match sc {
439 ir::StaticControl::Empty(_) => (),
440 ir::StaticControl::Enable(_) | ir::StaticControl::Invoke(_) => {
441 let id = ControlId::get_guaranteed_id_static(sc);
442 self.update_live_control_data(
443 id,
444 live_once_map,
445 live_cell_map,
446 parents,
447 )
448 }
449 ir::StaticControl::Repeat(ir::StaticRepeat { body, .. }) => {
450 self.get_live_control_data_static(
451 live_once_map,
452 par_thread_map,
453 live_cell_map,
454 parents,
455 body,
456 );
457 }
458 ir::StaticControl::Seq(ir::StaticSeq { stmts, .. }) => {
459 for stmt in stmts {
460 self.get_live_control_data_static(
461 live_once_map,
462 par_thread_map,
463 live_cell_map,
464 parents,
465 stmt,
466 );
467 }
468 }
469 ir::StaticControl::Par(ir::StaticPar { stmts, .. }) => {
470 let parent_id = ControlId::get_guaranteed_id_static(sc);
471 let mut new_parents = parents.clone();
472 for stmt in stmts {
473 // building par_thread_map
474 let child_id = ControlId::get_guaranteed_id_static(stmt);
475 par_thread_map.insert(child_id, parent_id);
476
477 // building live_once_map by adding child_id to parents when
478 // we recursively call get_live_control_data on each child
479 new_parents.insert(child_id);
480 self.get_live_control_data_static(
481 live_once_map,
482 par_thread_map,
483 live_cell_map,
484 &new_parents,
485 stmt,
486 );
487 new_parents.remove(&child_id);
488 }
489 }
490 ir::StaticControl::If(ir::StaticIf {
491 port,
492 tbranch,
493 fbranch,
494 ..
495 }) => {
496 self.get_live_control_data_static(
497 live_once_map,
498 par_thread_map,
499 live_cell_map,
500 parents,
501 tbranch,
502 );
503 self.get_live_control_data_static(
504 live_once_map,
505 par_thread_map,
506 live_cell_map,
507 parents,
508 fbranch,
509 );
510 let id = ControlId::get_guaranteed_id_static(sc);
511 // Examining the cell read from in the if guard
512 if let Some(cell_info) = LiveRangeAnalysis::port_to_cell_name(
513 port,
514 &self.state_share,
515 ) {
516 Self::add_cell_to_control_data(
517 id,
518 &cell_info,
519 live_once_map,
520 live_cell_map,
521 parents,
522 )
523 }
524 }
525 }
526 }
527
528 /// Updates live_once_map and par_thread_map.
529 /// live_once_map should map celltypes to a map, which should map cells of
530 /// celltype to control statements in which it is live for at least one group
531 /// or invoke in the control. We only map to control statements that are
532 /// direct children of par blocks.
533 /// par_thread_map maps direct children of par blocks to their parents
534 /// live_cell_map maps cells to the nodes in which it is live
535 /// par_thread_map maps direct children of par blocks to their parents
536 /// parents is the list of current control statements (that are direct children
537 /// of par blocks) that are parents (at any level of nesting) of c.
538 pub fn get_live_control_data(
539 &self,
540 live_once_map: &mut LiveMapByType,
541 par_thread_map: &mut HashMap<u64, u64>,
542 live_cell_map: &mut LiveMapByType,
543 parents: &HashSet<u64>,
544 c: &ir::Control,
545 ) {
546 match c {
547 ir::Control::Empty(_) => (),
548 ir::Control::Par(ir::Par { stmts, .. }) => {
549 let parent_id = ControlId::get_guaranteed_id(c);
550 let mut new_parents = parents.clone();
551 for stmt in stmts {
552 // building par_thread_map
553 let child_id = ControlId::get_guaranteed_id(stmt);
554 par_thread_map.insert(child_id, parent_id);
555
556 // building live_once_map by adding child_id to parents when
557 // we recursively call get_live_control_data on each child
558 new_parents.insert(child_id);
559 self.get_live_control_data(
560 live_once_map,
561 par_thread_map,
562 live_cell_map,
563 &new_parents,
564 stmt,
565 );
566 new_parents.remove(&child_id);
567 }
568 }
569 ir::Control::Seq(ir::Seq { stmts, .. }) => {
570 for stmt in stmts {
571 self.get_live_control_data(
572 live_once_map,
573 par_thread_map,
574 live_cell_map,
575 parents,
576 stmt,
577 );
578 }
579 }
580 ir::Control::If(ir::If {
581 tbranch, fbranch, ..
582 }) => {
583 self.get_live_control_data(
584 live_once_map,
585 par_thread_map,
586 live_cell_map,
587 parents,
588 tbranch,
589 );
590 self.get_live_control_data(
591 live_once_map,
592 par_thread_map,
593 live_cell_map,
594 parents,
595 fbranch,
596 );
597 let id = ControlId::get_guaranteed_id(c);
598 // Examining all the cells used at the comb group of the if stmt
599 if let Some(comb_group_uses) = self.cgroup_uses_map.get(&id) {
600 for cell_info in comb_group_uses {
601 Self::add_cell_to_control_data(
602 id,
603 cell_info,
604 live_once_map,
605 live_cell_map,
606 parents,
607 )
608 }
609 }
610 }
611 ir::Control::While(ir::While { body, .. }) => {
612 self.get_live_control_data(
613 live_once_map,
614 par_thread_map,
615 live_cell_map,
616 parents,
617 body,
618 );
619 let id = ControlId::get_guaranteed_id(c);
620 if let Some(comb_group_uses) = self.cgroup_uses_map.get(&id) {
621 for (cell_type, cell_name) in comb_group_uses {
622 if !parents.is_empty() {
623 live_once_map
624 .entry(cell_type.clone())
625 .or_default()
626 .entry(*cell_name)
627 .or_default()
628 .extend(parents);
629 }
630 live_cell_map
631 .entry(cell_type.clone())
632 .or_default()
633 .entry(*cell_name)
634 .or_default()
635 .insert(id);
636 }
637 }
638 }
639 ir::Control::Repeat(ir::Repeat { body, .. }) => {
640 self.get_live_control_data(
641 live_once_map,
642 par_thread_map,
643 live_cell_map,
644 parents,
645 body,
646 );
647 }
648 ir::Control::Enable(_) | ir::Control::Invoke(_) => {
649 let id = ControlId::get_guaranteed_id(c);
650 self.update_live_control_data(
651 id,
652 live_once_map,
653 live_cell_map,
654 parents,
655 )
656 }
657 ir::Control::Static(sc) => self.get_live_control_data_static(
658 live_once_map,
659 par_thread_map,
660 live_cell_map,
661 parents,
662 sc,
663 ),
664 }
665 }
666
667 /// Look up the set of things live at a node (i.e. group or invoke) definition.
668 pub fn get(&self, node: &u64) -> &CellsByType {
669 &self
670 .live
671 .get(node)
672 .unwrap_or_else(|| panic!("Live set missing for {}", node))
673 .map
674 }
675
676 /// Get a unique list of all live cells in `component`.
677 pub fn get_all(&self) -> impl Iterator<Item = ir::Id> + '_ {
678 self.live
679 .iter()
680 .flat_map(|(_, set)| {
681 set.map.iter().fold(HashSet::new(), |mut acc, (_, set)| {
682 acc.extend(set);
683 acc
684 })
685 })
686 .unique()
687 .cloned()
688 }
689
690 fn variable_like(
691 &mut self,
692 grp: &RRC<ir::Group>,
693 ) -> &Option<(ir::CellType, ir::Id)> {
694 let group = grp.borrow();
695 let name = &group.name();
696 if !self.variable_like.contains_key(name) {
697 let res = VariableDetection::variable_like(grp, &self.state_share);
698 self.variable_like.insert(grp.borrow().name(), res);
699 }
700 &self.variable_like[name]
701 }
702
703 /// Compute the `gen` and `kill` sets for a given group definition. Because
704 /// we can't always know if a group will *definitely* kill something or *definitely*
705 /// read something, this function is conservative.
706 ///
707 /// However, it is conservative in different directions for `gens` and `kills`.
708 /// In particular, it is always ok to accidentally put something in `gens` because
709 /// in the worst case we say something is alive when it isn't.
710 ///
711 /// However, it is **never** ok to accidentally put something in `writes` because
712 /// we might accidentally kill something that should be alive.
713 ///
714 /// To implement this, we say that something is being read if it shows up on the rhs
715 /// of any assignment in a group. Something is written if it it's guard is `1` or if it has no guard.
716 fn find_gen_kill_group(
717 &mut self,
718 group_ref: &RRC<ir::Group>,
719 ) -> (TypeNameSet, TypeNameSet) {
720 let group = group_ref.borrow();
721 let maybe_var = self.variable_like(group_ref).clone();
722 let sc_clone = &self.state_share;
723 // if the group contains what looks like a variable write,
724 // then just add variable to write set
725 if let Some((cell_type, variable)) = maybe_var {
726 // we don't want to read the control signal of `variable`
727 let assignments = group
728 .assignments
729 .iter()
730 .filter(|asgn| {
731 !(asgn.src.borrow().get_parent_name() == variable
732 && asgn.src.borrow().name == "done")
733 })
734 .filter(|asgn| {
735 if let ir::Guard::Port(port) = &*asgn.guard {
736 !(port.borrow().get_parent_name() == variable
737 && port.borrow().name == "done")
738 } else {
739 true
740 }
741 });
742
743 // calculate reads, but ignore `variable`. we've already dealt with that
744 let reads: HashSet<_> = assignments
745 .analysis()
746 .cell_reads()
747 .filter(|c| sc_clone.is_shareable_component(c))
748 .map(|c| (c.borrow().prototype.clone(), c.borrow().name()))
749 .collect();
750
751 let mut writes = HashSet::new();
752 writes.insert((cell_type, variable));
753
754 (reads, writes)
755 } else {
756 let reads: HashSet<_> =
757 meaningful_read_set(group.assignments.iter())
758 .filter(|c| sc_clone.is_shareable_component(c))
759 .map(|c| (c.borrow().prototype.clone(), c.borrow().name()))
760 .collect();
761
762 // only consider write assignments where the guard is true
763 let assignments = group
764 .assignments
765 .iter()
766 .filter(|asgn| *asgn.guard == ir::Guard::True)
767 .cloned()
768 .collect::<Vec<_>>();
769
770 let writes: HashSet<_> = assignments
771 .iter()
772 .analysis()
773 .cell_writes()
774 .filter(|c| sc_clone.is_shareable_component(c))
775 .map(|c| (c.borrow().prototype.clone(), c.borrow().name()))
776 .collect();
777
778 (reads, writes)
779 }
780 }
781
782 // TODO(calebmkim) TODO(paili0628): This is similar to find_static_group right now
783 // We could eventually try to merge it, but we should do it after we have
784 // hammered down the details of the rest of the static IR assignments
785 fn find_gen_kill_static_group(
786 &mut self,
787 group_ref: &RRC<ir::StaticGroup>,
788 ) -> (TypeNameSet, TypeNameSet) {
789 let group = group_ref.borrow();
790 // we don't have to worry about variable like for static groups
791 let sc_clone = &self.state_share;
792 let reads: HashSet<_> = meaningful_read_set(group.assignments.iter())
793 .filter(|c| sc_clone.is_shareable_component(c))
794 .map(|c| (c.borrow().prototype.clone(), c.borrow().name()))
795 .collect();
796 // only consider write assignments where the guard is true
797 let assignments = group
798 .assignments
799 .iter()
800 .filter(|asgn| *asgn.guard == ir::Guard::True)
801 .cloned()
802 .collect::<Vec<_>>();
803
804 let writes: HashSet<_> = assignments
805 .iter()
806 .analysis()
807 .cell_writes()
808 .filter(|c| sc_clone.is_shareable_component(c))
809 .map(|c| (c.borrow().prototype.clone(), c.borrow().name()))
810 .collect();
811
812 (reads, writes)
813 }
814
815 fn find_uses_assigns<T>(
816 assigns: &[ir::Assignment<T>],
817 shareable_components: &ShareSet,
818 ) -> TypeNameSet {
819 assigns
820 .iter()
821 .analysis()
822 .cell_uses()
823 .filter(|cell| shareable_components.is_shareable_component(cell))
824 .map(|cell| (cell.borrow().prototype.clone(), cell.borrow().name()))
825 .collect::<HashSet<_>>()
826 }
827
828 // returns (share_uses, state_reads), which are the uses of shareable components
829 // and reads of state shareable components
830 fn uses_reads_cgroup(
831 group_ref: &RRC<ir::CombGroup>,
832 shareable: &ShareSet,
833 state_shareable: &ShareSet,
834 ) -> (TypeNameSet, TypeNameSet) {
835 let group = group_ref.borrow();
836 let share_uses = group
837 .assignments
838 .iter()
839 .analysis()
840 .cell_uses()
841 .filter(|cell| shareable.is_shareable_component(cell))
842 .map(|cell| (cell.borrow().prototype.clone(), cell.borrow().name()))
843 .collect::<HashSet<_>>();
844 let state_reads = group
845 .assignments
846 .iter()
847 .analysis()
848 .reads()
849 .cells()
850 .filter(|cell| state_shareable.is_shareable_component(cell))
851 .map(|cell| (cell.borrow().prototype.clone(), cell.borrow().name()))
852 .collect::<HashSet<_>>();
853 (share_uses, state_reads)
854 }
855
856 fn port_to_cell_name(
857 port: &RRC<ir::Port>,
858 shareable_components: &ShareSet,
859 ) -> Option<(ir::CellType, ir::Id)> {
860 if let ir::PortParent::Cell(cell_wref) = &port.borrow().parent {
861 let cell = cell_wref.upgrade();
862 if shareable_components.is_shareable_component(&cell) {
863 return Some((
864 cell.borrow().prototype.clone(),
865 cell.borrow().name(),
866 ));
867 }
868 }
869 None
870 }
871
872 // gets the gens/kills (aka reads/writes) of the invoke given inputs, outputs, and comb group.
873 fn gen_kill_invoke(
874 inputs: &[(ir::Id, ir::RRC<ir::Port>)],
875 outputs: &[(ir::Id, ir::RRC<ir::Port>)],
876 comb_group_info: &Option<ir::RRC<ir::CombGroup>>,
877 comp: &ir::RRC<ir::Cell>,
878 shareable_components: &ShareSet,
879 ) -> (TypeNameSet, TypeNameSet) {
880 // The writes of the invoke include its outputs. Also, we count the cell
881 // being invoked as being written to.
882 let mut write_set: TypeNameSet = outputs
883 .iter()
884 .filter_map(|(_, src)| {
885 Self::port_to_cell_name(src, shareable_components)
886 })
887 .collect();
888
889 if shareable_components.is_shareable_component(comp) {
890 write_set.insert((
891 comp.borrow().prototype.clone(),
892 comp.borrow().name(),
893 ));
894 }
895
896 // The reads of the invoke include its inputs.
897 // One quick note: since the component is written to, there is no need to include this
898 // component as being read from since we know the write to the component
899 // precedes the read from it, due to the nature of `invoke` statements.
900 // This is "cheating" in a sense, since the component is technically being
901 // read from. However, since we know that there is a write to the component
902 // that that precedes the read from it within the very same invoke statement,
903 // it "appears" to all the other control statements in the program that the
904 // component is not being read from in the invoke statement.
905 let mut read_set: TypeNameSet = inputs
906 .iter()
907 .filter_map(|(_, src)| {
908 Self::port_to_cell_name(src, shareable_components)
909 })
910 .collect();
911
912 if let Some(comb_group) = comb_group_info {
913 read_set.extend(
914 comb_group
915 .borrow()
916 .assignments
917 .iter()
918 .analysis()
919 .reads()
920 .cells()
921 .filter(|cell| {
922 shareable_components.is_shareable_component(cell)
923 })
924 .map(|cell| {
925 (cell.borrow().prototype.clone(), cell.borrow().name())
926 }),
927 );
928 }
929
930 (read_set, write_set)
931 }
932
933 // gets the uses of the invoke given inputs, outputs, and comb group.
934 // Should include any cell that is either read from or written to at all
935 // in the invoke statement (including the comb group)
936 fn uses_invoke(
937 inputs: &[(ir::Id, ir::RRC<ir::Port>)],
938 outputs: &[(ir::Id, ir::RRC<ir::Port>)],
939 comb_group_info: &Option<ir::RRC<ir::CombGroup>>,
940 shareable_components: &ShareSet,
941 ) -> TypeNameSet {
942 // uses of shareable components in the invoke statement
943 let mut uses: TypeNameSet = inputs
944 .iter()
945 .chain(outputs.iter())
946 .filter_map(|(_, src)| {
947 Self::port_to_cell_name(src, shareable_components)
948 })
949 .collect();
950 // uses of shareable components in the comb group (if it exists)
951 if let Some(comb_group) = &comb_group_info {
952 uses.extend(
953 comb_group
954 .borrow()
955 .assignments
956 .iter()
957 .analysis()
958 .cell_uses()
959 .filter(|cell| {
960 shareable_components.is_shareable_component(cell)
961 })
962 .map(|cell| {
963 (cell.borrow().prototype.clone(), cell.borrow().name())
964 }),
965 );
966 };
967 uses
968 }
969
970 // updates liveness for an invoke: build to handle either static or dynamic invokes
971 // invoke_info = (inputs, outputs) of invoke
972 // comp = comp being invokes
973 // comb_group_invo = Option<comb group if invoke has one>
974 // liveness_info = (alive, gens, kills) coming into the invoke
975 // returns the (alive, gens, kills) based on the invoke info
976 // also updates self.invokes_enables_map using the input information
977 fn update_invoke_liveness(
978 &mut self,
979 invoke_info: InvokeInfo,
980 comb_group_info: &Option<ir::RRC<ir::CombGroup>>,
981 comp: &ir::RRC<ir::Cell>,
982 id: u64,
983 liveness_info: (Prop, Prop, Prop),
984 ) -> (Prop, Prop, Prop) {
985 let (inputs, outputs) = invoke_info;
986 let (mut alive, mut gens, mut kills) = liveness_info;
987
988 // get uses of all shareable components, and then update self.invokes_enables_map
989 let uses_shareable =
990 Self::uses_invoke(inputs, outputs, comb_group_info, &self.share);
991
992 self.invokes_enables_map
993 .entry(id)
994 .or_default()
995 .extend(uses_shareable);
996
997 // get the reads and writes of the invoke, and use that to determine livenes propogation
998 let (reads, writes) = LiveRangeAnalysis::gen_kill_invoke(
999 inputs,
1000 outputs,
1001 comb_group_info,
1002 comp,
1003 &self.state_share,
1004 );
1005
1006 alive.transfer_set(reads.clone(), writes.clone());
1007 let alive_out = alive.clone();
1008
1009 // set the live set of this node to be the things live on the
1010 // output of this node plus the things written to in this invoke
1011 // plus all shareable components used
1012 self.live.insert(id, {
1013 alive.or_set(writes.clone());
1014 alive
1015 });
1016 (
1017 alive_out,
1018 {
1019 gens.sub_set(writes.clone());
1020 gens.or_set(reads);
1021 gens
1022 },
1023 {
1024 kills.or_set(writes);
1025 kills
1026 },
1027 )
1028 }
1029
1030 // Updates Live Range Analysis
1031 // id should correspond to the id of an enable, and assigns should correspond
1032 // to the assignments in that enable
1033 // reads and writes should be the reads/writes of the assigns
1034 // alive, gens, kills are the alive, gens, and kills coming into the enable
1035 // returns the alive, gens, and kills leaving the enable
1036 // It also updates self.live at id to be the cells live at live
1037 // It also updates self.invokes_enables_map
1038 fn update_group_liveness<T>(
1039 &mut self,
1040 assigns: &[ir::Assignment<T>],
1041 id: u64,
1042 read_write_info: ReadWriteInfo,
1043 mut alive: Prop,
1044 mut gens: Prop,
1045 mut kills: Prop,
1046 ) -> (Prop, Prop, Prop) {
1047 let uses_share =
1048 LiveRangeAnalysis::find_uses_assigns(assigns, &self.share);
1049 self.invokes_enables_map
1050 .entry(id)
1051 .or_default()
1052 .extend(uses_share);
1053 let (reads, writes) = read_write_info;
1054 // compute transfer function
1055 alive.transfer_set(reads.clone(), writes.clone());
1056 let alive_out = alive.clone();
1057
1058 // set the live set of this node to be the things live on the
1059 // output of this node plus the things written to in this group
1060 self.live.insert(id, {
1061 alive.or_set(writes.clone());
1062 alive
1063 });
1064 (
1065 alive_out,
1066 {
1067 gens.sub_set(writes.clone());
1068 gens.or_set(reads);
1069 gens
1070 },
1071 {
1072 kills.or_set(writes);
1073 kills
1074 },
1075 )
1076 }
1077
1078 fn build_live_ranges_static(
1079 &mut self,
1080 sc: &ir::StaticControl,
1081 alive: Prop,
1082 gens: Prop,
1083 kills: Prop,
1084 ) -> (Prop, Prop, Prop) {
1085 match sc {
1086 ir::StaticControl::Empty(_) => (alive, gens, kills),
1087 ir::StaticControl::Enable(ir::StaticEnable { group, .. }) => {
1088 // XXX(sam) no reason to compute this every time
1089 let (reads, writes) = self.find_gen_kill_static_group(group);
1090 self.update_group_liveness(
1091 &group.borrow().assignments,
1092 ControlId::get_guaranteed_id_static(sc),
1093 (reads, writes),
1094 alive,
1095 gens,
1096 kills,
1097 )
1098 }
1099 ir::StaticControl::Repeat(ir::StaticRepeat { body, .. }) => {
1100 let (a, g, k) =
1101 self.build_live_ranges_static(body, alive, gens, kills);
1102 // Have to go through the repeat body twice in order to get a
1103 // correct live range analysis
1104 self.build_live_ranges_static(body, a, g, k)
1105 }
1106 ir::StaticControl::Seq(ir::StaticSeq { stmts, .. }) => stmts
1107 .iter()
1108 .rev()
1109 .fold((alive, gens, kills), |(alive, gens, kills), e| {
1110 self.build_live_ranges_static(e, alive, gens, kills)
1111 }),
1112 ir::StaticControl::Par(ir::StaticPar { stmts, .. }) => {
1113 let (mut alive, gens, kills) = stmts
1114 .iter()
1115 .rev()
1116 .map(|e| {
1117 self.build_live_ranges_static(
1118 e,
1119 alive.clone(),
1120 Prop::default(),
1121 Prop::default(),
1122 )
1123 })
1124 .fold(
1125 (Prop::default(), Prop::default(), Prop::default()),
1126 |(mut acc_alive, mut acc_gen, mut acc_kill),
1127 (alive, gen, kill)| {
1128 (
1129 // Doing in place operations saves time
1130 {
1131 acc_alive.or(alive);
1132 acc_alive
1133 },
1134 {
1135 acc_gen.or(gen);
1136 acc_gen
1137 },
1138 {
1139 acc_kill.or(kill);
1140 acc_kill
1141 },
1142 )
1143 },
1144 );
1145 // should only count as a "gen" if it is alive on at least one
1146 // of the outputs of the child node
1147 alive.transfer(gens.clone(), kills.clone());
1148 (alive, gens, kills)
1149 }
1150 ir::StaticControl::If(ir::StaticIf {
1151 tbranch,
1152 fbranch,
1153 port,
1154 ..
1155 }) => {
1156 // compute each branch
1157 let (mut t_alive, mut t_gens, mut t_kills) = self
1158 .build_live_ranges_static(
1159 tbranch,
1160 alive.clone(),
1161 gens.clone(),
1162 kills.clone(),
1163 );
1164 let (f_alive, f_gens, f_kills) =
1165 self.build_live_ranges_static(fbranch, alive, gens, kills);
1166
1167 // take union
1168 t_alive.or(f_alive);
1169 t_gens.or(f_gens);
1170 // kills must take intersection to be conservative
1171 t_kills.intersect(f_kills);
1172
1173 // add if guard cell to the alive/gens sets
1174 if let Some(cell_info) = LiveRangeAnalysis::port_to_cell_name(
1175 port,
1176 &self.state_share,
1177 ) {
1178 t_alive.insert(cell_info.clone());
1179 t_gens.insert(cell_info);
1180 }
1181
1182 (t_alive, t_gens, t_kills)
1183 }
1184 ir::StaticControl::Invoke(ir::StaticInvoke {
1185 inputs,
1186 outputs,
1187 comp,
1188 ..
1189 }) => {
1190 //get the shareable components used in the invoke stmt
1191 self.update_invoke_liveness(
1192 (inputs, outputs),
1193 &None,
1194 comp,
1195 ControlId::get_guaranteed_id_static(sc),
1196 (alive, gens, kills),
1197 )
1198 }
1199 }
1200 }
1201
1202 /// Implements the parallel dataflow analysis that computes the liveness of every state shareable component
1203 /// at every point in the program.
1204 fn build_live_ranges(
1205 &mut self,
1206 c: &ir::Control,
1207 alive: Prop,
1208 gens: Prop,
1209 kills: Prop,
1210 ) -> (Prop, Prop, Prop) {
1211 match c {
1212 ir::Control::Empty(_) => (alive, gens, kills),
1213 ir::Control::Invoke(ir::Invoke {
1214 inputs,
1215 outputs,
1216 comb_group,
1217 comp,
1218 ..
1219 }) => self.update_invoke_liveness(
1220 (inputs, outputs),
1221 comb_group,
1222 comp,
1223 ControlId::get_guaranteed_id(c),
1224 (alive, gens, kills),
1225 ),
1226 ir::Control::Enable(ir::Enable { group, .. }) => {
1227 // XXX(sam) no reason to compute this every time
1228 let (reads, writes) = self.find_gen_kill_group(group);
1229
1230 self.update_group_liveness(
1231 &group.borrow().assignments,
1232 ControlId::get_guaranteed_id(c),
1233 (reads, writes),
1234 alive,
1235 gens,
1236 kills,
1237 )
1238 }
1239 ir::Control::Seq(ir::Seq { stmts, .. }) => stmts.iter().rev().fold(
1240 (alive, gens, kills),
1241 |(alive, gens, kills), e| {
1242 self.build_live_ranges(e, alive, gens, kills)
1243 },
1244 ),
1245 ir::Control::If(ir::If {
1246 tbranch,
1247 fbranch,
1248 port,
1249 cond,
1250 ..
1251 }) => {
1252 // compute each branch
1253 let (mut t_alive, mut t_gens, mut t_kills) = self
1254 .build_live_ranges(
1255 tbranch,
1256 alive.clone(),
1257 gens.clone(),
1258 kills.clone(),
1259 );
1260 let (f_alive, f_gens, f_kills) =
1261 self.build_live_ranges(fbranch, alive, gens, kills);
1262
1263 // take union
1264 t_alive.or(f_alive);
1265 t_gens.or(f_gens);
1266 // kills must be intersection to be conservative
1267 t_kills.intersect(f_kills);
1268
1269 let id = ControlId::get_guaranteed_id(c);
1270
1271 // reads from state shareable components in the comb group
1272 // These should get "passed on" as live/gens as we go up the
1273 // control flow of the program
1274 let mut cgroup_reads: TypeNameSet = HashSet::new();
1275 // Any uses of any shareable components in the comb group.
1276 let mut shareable_uses: TypeNameSet = HashSet::new();
1277
1278 if let Some(comb_group) = cond {
1279 let (share_uses, state_reads) = Self::uses_reads_cgroup(
1280 comb_group,
1281 &self.share,
1282 &self.state_share,
1283 );
1284 shareable_uses = share_uses;
1285 cgroup_reads = state_reads;
1286 }
1287
1288 if let Some(cell_info) = LiveRangeAnalysis::port_to_cell_name(
1289 port,
1290 &self.state_share,
1291 ) {
1292 // If we read from a state shareable component (like a register)
1293 // in the port, then we add it to cgroup_reads.
1294 cgroup_reads.insert(cell_info);
1295 }
1296 if !cgroup_reads.is_empty() || !shareable_uses.is_empty() {
1297 let mut all_uses = cgroup_reads.clone();
1298 all_uses.extend(shareable_uses);
1299 // add all uses of both shareable and state-shareable components
1300 // in the cgroup_uses_map.
1301 self.cgroup_uses_map.insert(id, all_uses);
1302 }
1303 // adding cgroup_reads as live on output of if stmt
1304 t_alive.or_set(cgroup_reads.clone());
1305 t_gens.or_set(cgroup_reads);
1306 (t_alive, t_gens, t_kills)
1307 }
1308 ir::Control::Par(ir::Par { stmts, .. }) => {
1309 let (mut alive, gens, kills) = stmts
1310 .iter()
1311 .rev()
1312 .map(|e| {
1313 self.build_live_ranges(
1314 e,
1315 alive.clone(),
1316 Prop::default(),
1317 Prop::default(),
1318 )
1319 })
1320 .fold(
1321 (Prop::default(), Prop::default(), Prop::default()),
1322 |(mut acc_alive, mut acc_gen, mut acc_kill),
1323 (alive, gen, kill)| {
1324 (
1325 // Doing in place operations saves time
1326 {
1327 acc_alive.or(alive);
1328 acc_alive
1329 },
1330 {
1331 acc_gen.or(gen);
1332 acc_gen
1333 },
1334 {
1335 acc_kill.or(kill);
1336 acc_kill
1337 },
1338 )
1339 },
1340 );
1341 // should only count as a "gen" if it is alive on at least one
1342 // of the outputs of the child node
1343 alive.transfer(gens.clone(), kills.clone());
1344 (alive, gens, kills)
1345 }
1346 ir::Control::While(ir::While {
1347 body, port, cond, ..
1348 }) => {
1349 let id = ControlId::get_guaranteed_id(c);
1350 // need this info twice, so just pre-calculate whether port is
1351 // a state shareable component.
1352 let port_if_shareable: Option<(ir::CellType, ir::Id)> =
1353 LiveRangeAnalysis::port_to_cell_name(
1354 port,
1355 &self.state_share,
1356 );
1357 // all reads from state shareable components in the comb group or port
1358 let mut cgroup_reads: TypeNameSet = HashSet::new();
1359 // all uses of shareable components in the comb group or port
1360 let mut shareable_uses: TypeNameSet = HashSet::new();
1361
1362 let input_kills = kills.clone();
1363 // Go through while body and while port + comb group once
1364 let (mut alive, mut gens, kills) =
1365 self.build_live_ranges(body, alive, gens, kills);
1366 if let Some(cell_info) = port_if_shareable {
1367 // adds port to cgroup_reads if state_shareable.
1368 cgroup_reads.insert(cell_info);
1369 }
1370 if let Some(comb_group) = cond {
1371 let (share_uses, state_reads) = Self::uses_reads_cgroup(
1372 comb_group,
1373 &self.share,
1374 &self.state_share,
1375 );
1376 shareable_uses = share_uses;
1377 cgroup_reads.extend(state_reads);
1378 }
1379 // setting alive and gens appropriately based on the updated info
1380 // from the comb group + port.
1381 alive.or_set(cgroup_reads.clone());
1382 gens.or_set(cgroup_reads.clone());
1383
1384 if !cgroup_reads.is_empty() || !shareable_uses.is_empty() {
1385 // add all uses of shareable and non-shareable components into
1386 // cgroup_uses_map
1387 let mut all_uses = cgroup_reads.clone();
1388 all_uses.extend(shareable_uses);
1389 self.cgroup_uses_map.insert(id, all_uses);
1390 }
1391
1392 // Going through the while body and guard + port once again
1393 let (mut alive, mut gens, kills) =
1394 self.build_live_ranges(body, alive, gens, kills);
1395 alive.or_set(cgroup_reads.clone());
1396 gens.or_set(cgroup_reads);
1397
1398 // we can only inlcude the kills if we know the while loop executes
1399 // at least once
1400 if let Some(val) = c.get_attribute(ir::NumAttr::Bound) {
1401 if val > 0 {
1402 return (alive, gens, kills);
1403 }
1404 }
1405
1406 (alive, gens, input_kills)
1407 }
1408 ir::Control::Repeat(ir::Repeat { body, .. }) => {
1409 let (a, g, k) =
1410 self.build_live_ranges(body, alive, gens, kills);
1411 // need to feed the live nodes on the output of the body
1412 // back into the body to get correct live range analysis
1413 self.build_live_ranges(body, a, g, k)
1414 }
1415 ir::Control::Static(sc) => {
1416 self.build_live_ranges_static(sc, alive, gens, kills)
1417 }
1418 }
1419 }
1420}