calyx_opt/passes/simplify_static_guards.rs
1use crate::traversal::{Action, Named, VisResult, Visitor};
2use calyx_ir as ir;
3
4#[derive(Default)]
5/// Simplifies Static Guards
6/// In particular if g = g1 & g2 & ...gn, then it takes all of the g_i's that
7/// are "static timing intervals", e.g., %[2:3], and combines them into one
8/// timing interval.
9/// For example: (port.out | !port1.out) & (port2.out == port3.out) & %[2:8] & %[5:10] ?
10/// becomes (port.out | !port1.out) & (port2.out == port3.out) & %[5:8] ?
11/// by "combining" %[2:8] & %[5:10]
12pub struct SimplifyStaticGuards;
13
14impl Named for SimplifyStaticGuards {
15 fn name() -> &'static str {
16 "simplify-static-guards"
17 }
18
19 fn description() -> &'static str {
20 "Simplify Static Guards"
21 }
22}
23
24impl SimplifyStaticGuards {
25 /// takes in g, and separates the "anded intervals" from the rest of the guard.
26 /// In other words, if we can rewrite g as g1 & g2 & .... gn, then
27 /// we take all of the g_i's that are static timing intervals (e.g., %[2:3])
28 /// and return a vec of (u64, u64)s. We also return the Some(rest of guard) (i.e.,
29 /// the parts that aren't "anded" intervals) if they exist
30 /// e.g.:
31 /// port.out & port1.out & %[3:5] & %[4:6] -> Some(port.out & port1.out), vec[(3,5), (4,6)]
32 /// %[3:5] & %[4:6] -> None, vec[(3,5), (4,6)]
33 pub fn separate_anded_intervals(
34 g: ir::Guard<ir::StaticTiming>,
35 cur_anded_intervals: &mut Vec<(u64, u64)>,
36 ) -> Option<ir::Guard<ir::StaticTiming>> {
37 match g {
38 ir::Guard::And(g1, g2) => {
39 // recursively call separate_anded_intervals on g1 and g2
40 let rest_g1 =
41 Self::separate_anded_intervals(*g1, cur_anded_intervals);
42 let rest_g2 =
43 Self::separate_anded_intervals(*g2, cur_anded_intervals);
44 match (rest_g1, rest_g2) {
45 // both g1 and g2 are entirely made up of static timing guards
46 (None, None) => None,
47 // one of g1 or g2 is made up entirely of static timing guards
48 (None, Some(g)) | (Some(g), None) => Some(g),
49 // both g1 and g2 have non-static timing guards
50 (Some(g1_unwrapped), Some(g2_unwrapped)) => {
51 Some(ir::Guard::And(
52 Box::new(g1_unwrapped),
53 Box::new(g2_unwrapped),
54 ))
55 }
56 }
57 }
58 ir::Guard::Info(static_timing_info) => {
59 // no "rest of guard" for static intervals
60 cur_anded_intervals.push(static_timing_info.get_interval());
61 None
62 }
63 ir::Guard::True
64 | ir::Guard::CompOp(_, _, _)
65 | ir::Guard::Not(_)
66 | ir::Guard::Or(_, _)
67 | ir::Guard::Port(_) => Some(g),
68 }
69 }
70
71 /// Takes in a guard and returns the simplified guard
72 /// In particular if g = g1 & g2 & ...gn, then it takes all of the g_i's that
73 /// are "static timing intervals", e.g., %[2:3], and combines them into one
74 /// timing interval.
75 /// For example: (port.out | !port1.out) & (port2.out == port3.out) & %[2:8] & %[5:10] ?
76 /// becomes (port.out | !port1.out) & (port2.out == port3.out) & %[5:8] ?
77 /// by "combining: %[2:8] & %[5:10]
78 fn simplify_anded_guards(
79 guard: ir::Guard<ir::StaticTiming>,
80 group_latency: u64,
81 ) -> ir::Guard<ir::StaticTiming> {
82 // get the rest of the guard and the "anded intervals"
83 let mut anded_intervals = Vec::new();
84 let rest_guard =
85 Self::separate_anded_intervals(guard, &mut anded_intervals);
86 // first simplify the vec of `anded_intervals` into a single interval
87 let replacing_interval = {
88 if anded_intervals.is_empty() {
89 // if there were no static timing guards (i.e., no %[2:3]), then
90 // there is no "replacing intervals"
91 None
92 } else {
93 // the replacing intervals should just be the latest beginning interval
94 // combined with the earliest ending interval, since we know that all of
95 // the intervals are connected by &.
96 let (mut max_beg, mut min_end) = anded_intervals.pop().unwrap();
97 for (cur_beg, cur_end) in anded_intervals {
98 max_beg = std::cmp::max(cur_beg, max_beg);
99 min_end = std::cmp::min(cur_end, min_end);
100 }
101 if max_beg >= min_end {
102 // if the vec was something like %[2:3] & %[4:5], then this is always false
103 // if max_beg >= min_end, then guard is always false
104 return ir::Guard::Not(Box::new(ir::Guard::True));
105 } else if max_beg == 0 && min_end == group_latency {
106 // if guard will just be [0:group_latency] then it's not necessary
107 None
108 } else {
109 // otherwise return the single interval as the "new" interval
110 Some(ir::Guard::Info(ir::StaticTiming::new((
111 max_beg, min_end,
112 ))))
113 }
114 }
115 };
116
117 // now based on `rest_guard` and `replacing_interval` we create the final guard
118 match (rest_guard, replacing_interval) {
119 (None, None) => ir::Guard::True,
120 (None, Some(g)) | (Some(g), None) => g,
121 (Some(rg), Some(ig)) => ir::Guard::And(Box::new(rg), Box::new(ig)),
122 }
123 }
124
125 fn simplify_guard(
126 guard: ir::Guard<ir::StaticTiming>,
127 group_latency: u64,
128 ) -> ir::Guard<ir::StaticTiming> {
129 match guard {
130 ir::Guard::Not(g) => ir::Guard::Not(Box::new(
131 Self::simplify_guard(*g, group_latency),
132 )),
133 ir::Guard::Or(g1, g2) => ir::Guard::Or(
134 Box::new(Self::simplify_guard(*g1, group_latency)),
135 Box::new(Self::simplify_guard(*g2, group_latency)),
136 ),
137 ir::Guard::And(_, _) => {
138 Self::simplify_anded_guards(guard, group_latency)
139 }
140 ir::Guard::Info(_) => {
141 Self::simplify_anded_guards(guard, group_latency)
142 }
143 ir::Guard::Port(_)
144 | ir::Guard::True
145 | ir::Guard::CompOp(_, _, _) => guard,
146 }
147 }
148}
149
150impl Visitor for SimplifyStaticGuards {
151 fn start(
152 &mut self,
153 comp: &mut ir::Component,
154 _: &ir::LibrarySignatures,
155 _comps: &[ir::Component],
156 ) -> VisResult {
157 for group in comp.get_static_groups().iter() {
158 let group_latency = group.borrow().get_latency();
159 group
160 .borrow_mut()
161 .assignments
162 .iter_mut()
163 .for_each(|assign| {
164 assign.guard.update(|guard| {
165 Self::simplify_guard(guard, group_latency)
166 })
167 });
168 }
169
170 // we don't need to traverse control
171 Ok(Action::Stop)
172 }
173}