Struct calyx_opt::analysis::DominatorMap

pub struct DominatorMap {
    pub map: HashMap<u64, HashSet<u64>>,
    pub exits_map: HashMap<u64, HashSet<u64>>,
    pub static_par_domination: StaticParDomination,
    pub component_name: Id,
}

Builds a Domination Map for the control program. It maps nodes to sets of nodes. Here is what is included as a “node” in the domination map:

• Invokes
• Enables
• While Guards
• If Guards
• “End” If nodes, representing the place we’re at in the program after the if statement has just finished. This doesn’t correspond to any actual Calyx code, but is just a conceptualization we use to reason about domination. Note that seqs and pars will not be included in the domination map.

Here is the algorithm we use to build the domination map.

• Start with an emtpy map.
• Visit each node n in the control program, and set:
• dom(n) = {U dom(p) for each predecessor p of n} U {n}. In other words, take the dominators of each predecessor of n, and union them together. Then add n to this set, and set this set as the dominators of n.
• (Another clarification): by “predecessors” of node n we mean the set of nodes that could be the most recent node executed when n begins to execute.
• If we visit every node of the control program and the map has not changed, then we are done. If it has changed, then we visit each node again to repeat the process.

The reason why we can take the union (rather than intersection) of the dominators of each predecessor is because we know each predecessor of each node must (rather than may) be executed. There are two exceptions to this general rule, and we have special cases in our algorithm to deal with them.

1. The While Guard The last node(s) in the while body are predecessor(s) of the while guard but are not guaranteed to be executed. So, we can think of the while guard’s predecessors as being split in two groups: the “body predecessors” that are not guaranteed to be executed before the while guard and the “outside predecessors” that are outside the body of the while loop and are guaranteed to be executed before the while loop guard. Here we take: dom(while guard) = U(dom(outside preds)) U {while guard}

Justification: dom(while guard) is a subset of U(dom(outside preds)) U {while guard} Suppose n dominates the while guard. Every path to the while guard must end in

1. outside pred -> while guard OR 2) body pred -> while guard. But for choice 2) we know the path was really something like outside pred -> while guard -> body -> while guard… body -> while guard. Since n dominates the while guard we know that it cannot be in the while body. Therefore, since every path to the while guard is in the form outside pred -> [possibly while guard + some other while body statements] -> while guard, we know that n must either dominate outside pred or be the while guard itself.

dom(outside preds) U {while guard} is a subset of dom(while guard) Suppose n dominates outside preds. Since we already established that every path to the while guard involves going through otuside preds, we know that n dominates the while guard.

2. “End Node” of If Statements In this case, neither of the predecessor sets (the set in the tbranch or the set in the fbranch) are guaranteed to be executed. Here we take: dom(end node) = dom(if guard) U {end node}.

Justification: dom(end node) is a subset of dom(if guard) U {end node}. If n dominates the end node, then it either a) is the end node itself, or b) must dominate the if guard. Justification for b) Every possible path to the if guard must be followed by if guard -> tbranch/fbranch -> end node. We also know that n must exist outside the tbranch/fbranch (if it was inside either branch, it wouldn’t dominate the end node). Therefore, since we know that n must have appeared somewhere before if_guard on the path to end node, we know n dominates the if guard.

dom(if guard) U {end node} is a subset of dom(end node) If n dominates the if guard or is itself the end node, then it is very easy to see how it will dominate the end node.

Fields

map: HashMap<u64, HashSet<u64>>

Map from node (either invokes, enables, or if/while ports) ids to the ids of nodes that dominate it

exits_map: HashMap<u64, HashSet<u64>>

Maps ids of control stmts, to the “last” nodes in them. By “last” is meant the final node that will be executed in them. For invokes and enables, it will be themselves, for while statements it will be the while guard, and for if statements it will be the “if” nods. For pars in seqs, you have to look inside the children to see what their “last” nodes are.

static_par_domination: StaticParDomination

an analysis to help domination across static pars static pars give us more precise timing guarantees and therefore allow us to more aggresively assign dominators

component_name: Id

Implementations

impl DominatorMap

pub fn new(control: &mut Control, component_name: Id) -> Self

Construct a domination map.

pub fn get_static_control(
    id: u64,
    sc: &StaticControl
) -> Option<GenericControl<'_>>

pub fn get_control(id: u64, c: &Control) -> Option<GenericControl<'_>>

Given a control c and an id, finds the control statement within c that has id, if it exists. If it doesn’t, return None.

pub fn get_control_nodes<'a>(
    nodes: &HashSet<u64>,
    main_control: &'a Control
) -> (Vec<&'a Control>, Vec<&'a StaticControl>)

pub fn get_node_reads(
    node: &u64,
    comp: &mut Component,
    shareset: &ShareSet
) -> HashSet<Id>

pub fn key_written_guaranteed(
    key: Id,
    nodes: &HashSet<u64>,
    comp: &mut Component
) -> bool

Trait Implementations

impl Debug for DominatorMap

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for DominatorMap

fn default() -> DominatorMap

Returns the “default value” for a type.