calyx_opt/analysis/domination_analysis/
dominator_map.rs

1use crate::analysis::{
2    ControlId, ShareSet,
3    domination_analysis::{
4        node_analysis::{NodeReads, NodeSearch},
5        static_par_domination::StaticParDomination,
6    },
7};
8use calyx_ir as ir;
9use ir::GenericControl;
10use std::collections::{HashMap, HashSet};
11use std::fmt::Debug;
12
13const NODE_ID: ir::Attribute =
14    ir::Attribute::Internal(ir::InternalAttr::NODE_ID);
15const BEGIN_ID: ir::Attribute =
16    ir::Attribute::Internal(ir::InternalAttr::BEGIN_ID);
17const END_ID: ir::Attribute = ir::Attribute::Internal(ir::InternalAttr::END_ID);
18
19/// Builds a Domination Map for the control program. It maps nodes to sets of
20/// nodes. Here is what is included as a "node" in the domination map:
21/// - Invokes
22/// - Enables
23/// - While Guards
24/// - If Guards
25/// - "End" If nodes, representing the place we're at in the program after the if
26///   statement has just finished. This doesn't correspond to any actual Calyx code, but is
27///   just a conceptualization we use to reason about domination.
28///
29/// Note that seqs and pars will *not* be included in the domination map.
30///
31/// Here is the algorithm we use to build the domination map.
32/// - Start with an emtpy map.
33/// - Visit each node n in the control program, and set:
34/// - dom(n) = {U dom(p) for each predecessor p of n} U {n}. In other words, take the
35///   dominators of each predecessor of n, and union them together. Then add n to
36///   this set, and set this set as the dominators of n.
37/// - (Another clarification): by "predecessors" of node n we mean the set of nodes
38///   that could be the most recent node executed when n begins to execute.
39/// - If we visit every node of the control program and the map has not changed,
40///   then we are done. If it has changed, then we visit each node again to repeat
41///   the process.
42///
43/// The reason why we can take the union (rather than intersection) of the
44/// dominators of each predecessor is because we know each predecessor of each
45/// node must (rather than may) be executed.
46/// There are two exceptions to this general rule, and we have special cases in
47/// our algorithm to deal with them.
48///
49/// 1) The While Guard
50///    The last node(s) in the while body are predecessor(s) of the while guard but
51///    are not guaranteed to be executed. So, we can think of the while guard's
52///    predecessors as being split in two groups: the "body predecessors" that are not guaranteed to
53///    be executed before the while guard and the "outside predecessors" that are
54///    outside the body of the while loop and are guaranteed to be executed before
55///    the while loop guard.
56///    Here we take:
57///    dom(while guard) = U(dom(outside preds)) U {while guard}
58///
59/// Justification:
60/// dom(while guard) is a subset of U(dom(outside preds)) U {while guard}
61/// Suppose n dominates the while guard. Every path to the while guard must end in
62/// (1) outside pred -> while guard OR (2) body pred -> while guard. But for choice 2)
63/// we know the path was really something like outside pred -> while guard -> body
64/// -> while guard... body -> while guard. Since n dominates the while guard
65/// we know that it *cannot* be in the while body. Therefore, since every path to the
66/// while guard is in the form outside pred -> [possibly while guard + some other
67/// while body statements] -> while guard, we know that n must either dominate
68/// outside pred or be the while guard itself.
69///
70/// dom(outside preds) U {while guard} is a subset of dom(while guard)
71/// Suppose n dominates outside preds. Since we already established that every
72/// path to the while guard involves going through otuside preds, we know that
73/// n dominates the while guard.
74///
75/// 2) "End Node" of If Statements
76///    In this case, *neither* of the predecessor sets (the set in the tbranch or
77///    the set in the fbranch) are guaranteed to be executed.
78///    Here we take:
79///    dom(end node) = dom(if guard) U {end node}.
80///
81/// Justification:
82/// dom(end node) is a subset of dom(if guard) U {end node}.
83/// If n dominates the end node, then it either a) is the end node itself, or b) must
84/// dominate the if guard. Justification for b)
85/// Every possible path to the if guard must be followed by
86/// if guard -> tbranch/fbranch -> end node. We also know that n must exist
87/// outside the tbranch/fbranch (if it was inside either branch, it wouldn't
88/// dominate the end node). Therefore, since we know that n must have appeared somewhere
89/// before if_guard on the path to end node, we know n dominates the if guard.
90///
91/// dom(if guard) U {end node} is a subset of dom(end node)
92/// If n dominates the if guard or is itself the end node, then it is very easy to
93/// see how it will dominate the end node.
94#[derive(Default)]
95pub struct DominatorMap {
96    /// Map from node (either invokes, enables, or if/while ports) ids to the ids of nodes that dominate it
97    pub map: HashMap<u64, HashSet<u64>>,
98    /// Maps ids of control stmts, to the "last" nodes in them. By "last" is meant
99    /// the final node that will be executed in them. For invokes and enables, it
100    /// will be themselves, for while statements it will be the while guard,
101    /// and for if statements it will be the "if" nods. For pars in seqs, you
102    /// have to look inside the children to see what their "last" nodes are.
103    pub exits_map: HashMap<u64, HashSet<u64>>,
104    /// an analysis to help domination across static pars
105    /// static pars give us more precise timing guarantees and therefore allow
106    /// us to more aggresively assign dominators
107    pub static_par_domination: StaticParDomination,
108    pub component_name: ir::Id,
109}
110
111impl Debug for DominatorMap {
112    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
113        //must sort the hashmap and hashsets in order to get consistent ordering
114        writeln!(
115            f,
116            "The numbers in the domination map refer to the BEGIN_ID, END_ID, and NODE_ID attributes \nthat are attached to each non-empty control statement when the domination map is built. \nTo see which ID's refer to which control statement, look at the Calyx Program, which should \nbe printed along with the map when it is printed."
117        )?;
118        writeln!(
119            f,
120            "Domination Map for component \"{}\"  {{",
121            self.component_name
122        )?;
123        let map = self.map.clone();
124        let mut vec1: Vec<(u64, HashSet<u64>)> = map.into_iter().collect();
125        vec1.sort_by(|(k1, _), (k2, _)| k1.cmp(k2));
126        for (k, hs) in vec1.into_iter() {
127            write!(f, "Node: {k:?} --")?;
128            let mut vec = hs.into_iter().collect::<Vec<_>>();
129            vec.sort_unstable();
130            writeln!(f, " Dominators: {vec:?}")?;
131        }
132        write!(f, "}}")
133    }
134}
135
136#[inline]
137fn get_id_static<const BEGIN: bool>(c: &ir::StaticControl) -> u64 {
138    let v = match c {
139        ir::StaticControl::If(_) => {
140            if BEGIN {
141                c.get_attribute(BEGIN_ID)
142            } else {
143                c.get_attribute(END_ID)
144            }
145        }
146        _ => c.get_attribute(NODE_ID),
147    };
148    v.unwrap_or_else(|| unreachable!(
149            "get_id() shouldn't be called on control stmts that don't have id numbering"
150    ))
151}
152
153// Given a control, gets its associated id. For if statments, gets the
154// beginning id if begin_id is true and end_id if begin_id is false.
155// Should not be called on empty control
156// statements or any other statements that don't have an id numbering.
157#[inline]
158fn get_id<const BEGIN: bool>(c: &ir::Control) -> u64 {
159    let v = match c {
160        ir::Control::If(_) | ir::Control::Static(ir::StaticControl::If(_)) => {
161            if BEGIN {
162                c.get_attribute(BEGIN_ID)
163            } else {
164                c.get_attribute(END_ID)
165            }
166        }
167        _ => c.get_attribute(NODE_ID),
168    };
169    v.unwrap_or_else(|| unreachable!(
170            "get_id() shouldn't be called on control stmts that don't have id numbering"
171    ))
172}
173
174fn matches_key_static(sc: &ir::StaticControl, key: u64) -> bool {
175    if get_id_static::<true>(sc) == key {
176        return true;
177    }
178    //could match the end id of an if statement as well
179    if let Some(end) = sc.get_attribute(END_ID) {
180        key == end
181    } else {
182        false
183    }
184}
185
186// Given a control stmt c and a key, returns true if c matches key, false
187// otherwise. For if stmts return true if key matches either begin or end id.
188fn matches_key(c: &ir::Control, key: u64) -> bool {
189    if get_id::<true>(c) == key {
190        return true;
191    }
192    //could match the end id of an if statement as well
193    if let Some(end) = c.get_attribute(END_ID) {
194        key == end
195    } else {
196        false
197    }
198}
199
200fn get_final_static(sc: &ir::StaticControl) -> HashSet<u64> {
201    let mut hs = HashSet::new();
202    match sc {
203        ir::StaticControl::Empty(_) => (),
204        ir::StaticControl::Enable(_) | ir::StaticControl::Invoke(_) => {
205            hs.insert(ControlId::get_guaranteed_attribute_static(sc, NODE_ID));
206        }
207        ir::StaticControl::Repeat(ir::StaticRepeat {
208            body,
209            num_repeats,
210            ..
211        }) => {
212            // `Repeat 0` statements are essentially just Control::empty() stmts
213            // and therefore do not have "final" nodes
214            if *num_repeats != 0 {
215                return get_final_static(body);
216            }
217        }
218        ir::StaticControl::Seq(ir::StaticSeq { stmts, .. }) => {
219            return get_final_static(stmts[..].last().unwrap_or_else(|| {
220                panic!(
221                    "error: empty Static Seq block. TODO: Make Static Seq work on collapse-control pass."
222                )
223            }));
224        }
225        ir::StaticControl::Par(ir::StaticPar { stmts, .. }) => {
226            for stmt in stmts {
227                let stmt_final = get_final_static(stmt);
228                hs = hs.union(&stmt_final).copied().collect()
229            }
230        }
231        ir::StaticControl::If(_) => {
232            hs.insert(ControlId::get_guaranteed_attribute_static(sc, END_ID));
233        }
234    }
235    hs
236}
237
238// Gets the "final" nodes in control c. Used to build exits_map.
239fn get_final(c: &ir::Control) -> HashSet<u64> {
240    let mut hs = HashSet::new();
241    match c {
242        ir::Control::Empty(_) | ir::Control::FSMEnable(_) => (), // todo
243        ir::Control::Invoke(_)
244        | ir::Control::Enable(_)
245        | ir::Control::While(_) => {
246            hs.insert(ControlId::get_guaranteed_attribute(c, NODE_ID));
247        }
248        ir::Control::Repeat(ir::Repeat {
249            body, num_repeats, ..
250        }) => {
251            // `Repeat 0` statements are essentially just Control::empty() stmts
252            // and therefore do not have "final" nodes
253            if *num_repeats != 0 {
254                return get_final(body);
255            }
256        }
257        ir::Control::If(_) => {
258            hs.insert(ControlId::get_guaranteed_attribute(c, END_ID));
259        }
260        ir::Control::Seq(ir::Seq { stmts, .. }) => {
261            return get_final(stmts[..].last().unwrap_or_else(|| {
262                panic!("error: empty Seq block. Run collapse-control pass.")
263            }));
264        }
265        ir::Control::Par(ir::Par { stmts, .. }) => {
266            for stmt in stmts {
267                let stmt_final = get_final(stmt);
268                hs = hs.union(&stmt_final).copied().collect()
269            }
270        }
271        ir::Control::Static(s) => return get_final_static(s),
272    }
273    hs
274}
275
276impl DominatorMap {
277    /// Construct a domination map.
278    pub fn new(control: &mut ir::Control, component_name: ir::Id) -> Self {
279        ControlId::compute_unique_ids(control, 0, true);
280        let mut map = DominatorMap {
281            map: HashMap::new(),
282            exits_map: HashMap::new(),
283            static_par_domination: StaticParDomination::new(
284                control,
285                component_name,
286            ),
287            component_name,
288        };
289        map.build_exit_map(control);
290        map.build_map(control);
291        map
292    }
293
294    fn build_exit_map_static(&mut self, sc: &ir::StaticControl) {
295        match sc {
296            ir::StaticControl::Enable(_) | ir::StaticControl::Invoke(_) => {
297                let id =
298                    ControlId::get_guaranteed_attribute_static(sc, NODE_ID);
299                self.exits_map.insert(id, HashSet::from([id]));
300            }
301            ir::StaticControl::Repeat(ir::StaticRepeat { body, .. }) => {
302                let id =
303                    ControlId::get_guaranteed_attribute_static(sc, NODE_ID);
304                self.exits_map.insert(id, get_final_static(sc));
305                self.build_exit_map_static(body);
306            }
307            ir::StaticControl::Seq(ir::StaticSeq { stmts, .. })
308            | ir::StaticControl::Par(ir::StaticPar { stmts, .. }) => {
309                for stmt in stmts {
310                    self.build_exit_map_static(stmt);
311                }
312                let id =
313                    ControlId::get_guaranteed_attribute_static(sc, NODE_ID);
314                self.exits_map.insert(id, get_final_static(sc));
315            }
316            ir::StaticControl::If(ir::StaticIf {
317                tbranch, fbranch, ..
318            }) => {
319                let begin_id =
320                    ControlId::get_guaranteed_attribute_static(sc, BEGIN_ID);
321                let end_id =
322                    ControlId::get_guaranteed_attribute_static(sc, END_ID);
323                self.exits_map.insert(begin_id, HashSet::from([end_id]));
324                self.exits_map.insert(end_id, HashSet::from([end_id]));
325                self.build_exit_map_static(tbranch);
326                self.build_exit_map_static(fbranch);
327            }
328            ir::StaticControl::Empty(_) => (),
329        }
330    }
331
332    // Builds the "exit map" of c. This is getting what will be the final "node"
333    // executed in c.
334    fn build_exit_map(&mut self, c: &ir::Control) {
335        match c {
336            ir::Control::Empty(_) | ir::Control::FSMEnable(_) => (), // todo
337            ir::Control::Invoke(_) | ir::Control::Enable(_) => {
338                let id = ControlId::get_guaranteed_attribute(c, NODE_ID);
339                self.exits_map.insert(id, HashSet::from([id]));
340            }
341            ir::Control::While(ir::While { body, .. }) => {
342                let id = ControlId::get_guaranteed_attribute(c, NODE_ID);
343                self.exits_map.insert(id, HashSet::from([id]));
344                self.build_exit_map(body);
345            }
346            ir::Control::Repeat(ir::Repeat { body, .. }) => {
347                let id = ControlId::get_guaranteed_attribute(c, NODE_ID);
348                self.exits_map.insert(id, get_final(body));
349                self.build_exit_map(body);
350            }
351            ir::Control::If(ir::If {
352                tbranch, fbranch, ..
353            }) => {
354                let begin_id = ControlId::get_guaranteed_attribute(c, BEGIN_ID);
355                let end_id = ControlId::get_guaranteed_attribute(c, END_ID);
356                self.exits_map.insert(begin_id, HashSet::from([end_id]));
357                self.exits_map.insert(end_id, HashSet::from([end_id]));
358                self.build_exit_map(tbranch);
359                self.build_exit_map(fbranch);
360            }
361            ir::Control::Seq(ir::Seq { stmts, .. })
362            | ir::Control::Par(ir::Par { stmts, .. }) => {
363                for stmt in stmts {
364                    self.build_exit_map(stmt);
365                }
366                let id = ControlId::get_guaranteed_attribute(c, NODE_ID);
367                self.exits_map.insert(id, get_final(c));
368            }
369            ir::Control::Static(sc) => self.build_exit_map_static(sc),
370        }
371    }
372
373    // Builds the domination map by running update_map() until the map
374    // stops changing.
375    fn build_map(&mut self, main_c: &mut ir::Control) {
376        let mut og_map = self.map.clone();
377        self.update_map(main_c, 0, &HashSet::new());
378        while og_map != self.map {
379            og_map = self.map.clone();
380            self.update_map(main_c, 0, &HashSet::new());
381        }
382        self.update_static_dominators();
383    }
384
385    // updates static dominators based on self.static_par_domination
386    // this can more aggresively add dominators to the map by
387    // using the timing guarantees of static par
388    fn update_static_dominators(&mut self) {
389        let new_static_domminators =
390            self.static_par_domination.get_static_dominators();
391        for (node_id, node_dominators) in new_static_domminators {
392            let cur_dominators = self.map.entry(node_id).or_default();
393            cur_dominators.extend(node_dominators);
394        }
395    }
396
397    // Given an id and its predecessors pred, and a domination map d_map, updates
398    // d_map accordingly (i.e. the union of all dominators of the predecessors
399    // plus itself).
400    fn update_node(&mut self, pred: &HashSet<u64>, id: u64) {
401        let mut union: HashSet<u64> = HashSet::new();
402        for id in pred.iter() {
403            if let Some(dominators) = self.map.get(id) {
404                union = union.union(dominators).copied().collect();
405            }
406        }
407        union.insert(id);
408        self.map.insert(id, union);
409    }
410
411    fn update_map_static(
412        &mut self,
413        main_sc: &ir::StaticControl,
414        cur_id: u64,
415        pred: &HashSet<u64>,
416    ) {
417        match Self::get_static_control(cur_id, main_sc) {
418            Some(GenericControl::Dynamic(_)) => {
419                unreachable!("should never get dynamic from get_static_control")
420            }
421            None => (),
422            Some(GenericControl::Static(sc)) => match sc {
423                ir::StaticControl::Empty(_) => (),
424                ir::StaticControl::Enable(_) | ir::StaticControl::Invoke(_) => {
425                    self.update_node(pred, cur_id);
426                }
427                ir::StaticControl::Repeat(ir::StaticRepeat {
428                    body,
429                    num_repeats,
430                    ..
431                }) => {
432                    if *num_repeats != 0 {
433                        let body_id = get_id_static::<true>(body);
434                        self.update_map_static(main_sc, body_id, pred);
435                    }
436                }
437                ir::StaticControl::Seq(ir::StaticSeq { stmts, .. }) => {
438                    let mut p = pred;
439                    let mut nxt: HashSet<u64>;
440                    for stmt in stmts {
441                        let id = get_id_static::<true>(stmt);
442                        self.update_map_static(main_sc, id, p);
443                        // updating the predecessors for the next stmt we iterate
444                        nxt = self
445                            .exits_map
446                            .get(&id)
447                            .unwrap_or(
448                                // If the exits map is empty, then it means the
449                                // current stmt is `Repeat 0`/Empty.
450                                // So the predecessors for the nxt stmt are the
451                                // same as the predecessors for the current stmt.
452                                pred,
453                            )
454                            .clone();
455                        p = &nxt;
456                    }
457                }
458                ir::StaticControl::Par(ir::StaticPar { stmts, .. }) => {
459                    for stmt in stmts {
460                        let id = get_id_static::<true>(stmt);
461                        self.update_map_static(main_sc, id, pred);
462                    }
463                }
464                ir::StaticControl::If(ir::StaticIf {
465                    tbranch,
466                    fbranch,
467                    ..
468                }) => {
469                    //updating the if guard
470                    self.update_node(pred, cur_id);
471
472                    //building a set w/ just the if_guard id in it
473                    let if_guard_set = HashSet::from([cur_id]);
474
475                    //updating the tbranch
476                    let t_id = get_id_static::<true>(tbranch);
477                    self.update_map_static(main_sc, t_id, &if_guard_set);
478
479                    // If the false branch is present, update the map
480                    if !matches!(**fbranch, ir::StaticControl::Empty(_)) {
481                        let f_id = get_id_static::<true>(fbranch);
482                        self.update_map_static(main_sc, f_id, &if_guard_set);
483                    }
484
485                    let end_id =
486                        ControlId::get_guaranteed_attribute_static(sc, END_ID);
487                    self.update_node(&if_guard_set, end_id)
488                }
489            },
490        }
491    }
492
493    // Looks through each "node" in the "graph" and updates the dominators accordingly
494    fn update_map(
495        &mut self,
496        main_c: &ir::Control,
497        cur_id: u64,
498        pred: &HashSet<u64>,
499    ) {
500        match Self::get_control(cur_id, main_c) {
501            None => (),
502            Some(GenericControl::Dynamic(c)) => {
503                match c {
504                    ir::Control::Empty(_) => {
505                        unreachable!(
506                            "should not pattern match agaisnt empty in update_map()"
507                        )
508                    }
509                    ir::Control::FSMEnable(_) => {
510                        unreachable!("should not encounter fsm nodes")
511                    }
512                    ir::Control::Invoke(_) | ir::Control::Enable(_) => {
513                        self.update_node(pred, cur_id);
514                    }
515                    ir::Control::Seq(ir::Seq { stmts, .. }) => {
516                        let mut p = pred;
517                        let mut nxt: HashSet<u64>;
518                        for stmt in stmts {
519                            let id = get_id::<true>(stmt);
520                            self.update_map(main_c, id, p);
521                            nxt = self
522                                .exits_map
523                                .get(&id)
524                                .unwrap_or(
525                                    pred, // If the exits map is empty, then it means the
526                                         // current stmt is `Repeat 0`/Empty.
527                                         // So the predecessors for the nxt stmt are the
528                                         // same as the predecessors for the current stmt
529                                )
530                                .clone();
531                            p = &nxt;
532                        }
533                    }
534                    ir::Control::Par(ir::Par { stmts, .. }) => {
535                        for stmt in stmts {
536                            let id = get_id::<true>(stmt);
537                            self.update_map(main_c, id, pred);
538                        }
539                    }
540                    ir::Control::Repeat(ir::Repeat {
541                        body,
542                        num_repeats,
543                        ..
544                    }) => {
545                        if *num_repeats != 0 {
546                            let body_id = get_id::<true>(body);
547                            self.update_map(main_c, body_id, pred);
548                        }
549                    }
550                    // Keep in mind that NODE_IDs attached to while loops/if statements
551                    // refer to the while/if guard, and as we pattern match against a while
552                    // or if statement, the control statement refers to the "guard",
553                    // which includes their combinational group and the conditional port
554                    // So (for example) if a while loop has NODE_ID = 10, then "node 10"
555                    // refers to the while guard-- comb group and conditional port-- but not the body.
556                    ir::Control::While(ir::While { body, .. }) => {
557                        self.update_node(pred, cur_id);
558                        // updating the while body
559                        let body_id = get_id::<true>(body);
560                        self.update_map(
561                            main_c,
562                            body_id,
563                            &HashSet::from([cur_id]),
564                        );
565                    }
566                    ir::Control::If(ir::If {
567                        tbranch, fbranch, ..
568                    }) => {
569                        //updating the if guard
570                        self.update_node(pred, cur_id);
571
572                        //building a set w/ just the if_guard id in it
573                        let if_guard_set = HashSet::from([cur_id]);
574
575                        //updating the tbranch
576                        let t_id = get_id::<true>(tbranch);
577                        self.update_map(main_c, t_id, &if_guard_set);
578
579                        // If the false branch is present, update the map
580                        if !matches!(**fbranch, ir::Control::Empty(_)) {
581                            let f_id = get_id::<true>(fbranch);
582                            self.update_map(main_c, f_id, &if_guard_set);
583                        }
584
585                        let end_id =
586                            ControlId::get_guaranteed_attribute(c, END_ID);
587                        self.update_node(&if_guard_set, end_id)
588                    }
589                    ir::Control::Static(_) => panic!(
590                        "when matching c in GenericControl::Dynamic(c), c shouldn't be Static Control"
591                    ),
592                };
593            }
594            Some(GenericControl::Static(sc)) => {
595                let static_id = get_id_static::<true>(sc);
596                self.update_map_static(sc, static_id, pred);
597            }
598        }
599    }
600
601    pub fn get_static_control(
602        id: u64,
603        sc: &ir::StaticControl,
604    ) -> Option<GenericControl> {
605        if matches!(sc, ir::StaticControl::Empty(_)) {
606            return None;
607        }
608        if matches_key_static(sc, id) {
609            return Some(GenericControl::from(sc));
610        };
611        match sc {
612            ir::StaticControl::Empty(_)
613            | ir::StaticControl::Enable(_)
614            | ir::StaticControl::Invoke(_) => None,
615            ir::StaticControl::Repeat(ir::StaticRepeat { body, .. }) => {
616                Self::get_static_control(id, body)
617            }
618            ir::StaticControl::Seq(ir::StaticSeq { stmts, .. })
619            | ir::StaticControl::Par(ir::StaticPar { stmts, .. }) => {
620                for stmt in stmts {
621                    match Self::get_static_control(id, stmt) {
622                        None => (),
623                        Some(GenericControl::Dynamic(_)) => {
624                            unreachable!(
625                                "Got a GenericControl::Dynamic when we called get_static_control"
626                            )
627                        }
628                        Some(GenericControl::Static(sc)) => {
629                            return Some(GenericControl::from(sc));
630                        }
631                    }
632                }
633                None
634            }
635            ir::StaticControl::If(ir::StaticIf {
636                tbranch, fbranch, ..
637            }) => {
638                match Self::get_static_control(id, tbranch) {
639                    Some(GenericControl::Dynamic(_)) => {
640                        unreachable!(
641                            "Got a GenericControl::Dynamic when we called get_static_control"
642                        )
643                    }
644                    Some(GenericControl::Static(sc)) => {
645                        return Some(GenericControl::from(sc));
646                    }
647                    None => (),
648                }
649                match Self::get_static_control(id, fbranch) {
650                    Some(GenericControl::Dynamic(_)) => {
651                        unreachable!(
652                            "Got a GenericControl::Dynamic when we called get_static_control"
653                        )
654                    }
655                    Some(GenericControl::Static(sc)) => {
656                        return Some(GenericControl::from(sc));
657                    }
658                    None => (),
659                };
660                None
661            }
662        }
663    }
664
665    /// Given a control c and an id, finds the control statement within c that
666    /// has id, if it exists. If it doesn't, return None.
667    pub fn get_control(id: u64, c: &ir::Control) -> Option<GenericControl> {
668        if matches!(c, ir::Control::Empty(_)) {
669            return None;
670        }
671        if matches_key(c, id) {
672            return Some(GenericControl::from(c));
673        }
674        match c {
675            ir::Control::Empty(_)
676            | ir::Control::Invoke(_)
677            | ir::Control::Enable(_)
678            | ir::Control::FSMEnable(_) => None,
679            ir::Control::Seq(ir::Seq { stmts, .. })
680            | ir::Control::Par(ir::Par { stmts, .. }) => {
681                for stmt in stmts {
682                    match Self::get_control(id, stmt) {
683                        None => (),
684                        Some(GenericControl::Dynamic(c)) => {
685                            return Some(GenericControl::from(c));
686                        }
687                        Some(GenericControl::Static(sc)) => {
688                            return Some(GenericControl::from(sc));
689                        }
690                    }
691                }
692                None
693            }
694            ir::Control::Repeat(ir::Repeat { body, .. }) => {
695                Self::get_control(id, body)
696            }
697            ir::Control::If(ir::If {
698                tbranch, fbranch, ..
699            }) => {
700                match Self::get_control(id, tbranch) {
701                    Some(GenericControl::Dynamic(c)) => {
702                        return Some(GenericControl::from(c));
703                    }
704                    Some(GenericControl::Static(sc)) => {
705                        return Some(GenericControl::from(sc));
706                    }
707                    None => (),
708                }
709                match Self::get_control(id, fbranch) {
710                    Some(GenericControl::Dynamic(c)) => {
711                        return Some(GenericControl::from(c));
712                    }
713                    Some(GenericControl::Static(sc)) => {
714                        return Some(GenericControl::from(sc));
715                    }
716                    None => (),
717                };
718                None
719            }
720            ir::Control::While(ir::While { body, .. }) => {
721                Self::get_control(id, body)
722            }
723            ir::Control::Static(sc) => Self::get_static_control(id, sc),
724        }
725    }
726
727    // Given a set of nodes, gets the control in main_control that corresponds
728    // to the node. If there is a node in the set not corresponding to a control
729    // statement in main_control, then it gives an unreachable! error.
730    // Returns two vectors: controls, static_controls
731    // (the dynamic and static nodes)
732    pub fn get_control_nodes<'a>(
733        nodes: &HashSet<u64>,
734        main_control: &'a ir::Control,
735    ) -> (Vec<&'a ir::Control>, Vec<&'a ir::StaticControl>) {
736        let mut controls: Vec<&ir::Control> = Vec::new();
737        let mut static_controls: Vec<&ir::StaticControl> = Vec::new();
738        for node in nodes {
739            match Self::get_control(*node, main_control) {
740                Some(GenericControl::Static(sc)) => static_controls.push(sc),
741                Some(GenericControl::Dynamic(c)) => controls.push(c),
742                None => {
743                    unreachable!("No control statement for ID {}", node)
744                }
745            }
746        }
747        (controls, static_controls)
748    }
749
750    // Gets the reads of shareable cells in node
751    // Assumes the control statements in comp have been given NODE_IDs in the same
752    // style of the domination map NODE_ID stuff.
753    pub fn get_node_reads(
754        node: &u64,
755        comp: &mut ir::Component,
756        shareset: &ShareSet,
757    ) -> HashSet<ir::Id> {
758        NodeReads::get_reads_of_node(node, comp, shareset)
759    }
760
761    // Returns whether key is guaranteed to be written in at least one of nodes
762    // Assumes the control statements in comp have been given NODE_IDs in the same
763    // style of the domination map NODE_ID stuff.
764    pub fn key_written_guaranteed(
765        key: ir::Id,
766        nodes: &HashSet<u64>,
767        comp: &mut ir::Component,
768    ) -> bool {
769        let search_struct = NodeSearch::new(key);
770        search_struct.is_written_guaranteed(nodes, comp)
771    }
772}
calyx_opt/analysis/domination_analysis/dominator_map.rs

calyx_opt/analysis/domination_analysis/
dominator_map.rs
