calyx_opt/analysis/
graph.rs

1use calyx_ir::{self as ir, Id, PortIterator, RRC};
2use petgraph::{
3    Direction::{Incoming, Outgoing},
4    algo,
5    graph::{DiGraph, NodeIndex},
6    visit::EdgeRef,
7};
8use std::fmt::{Display, Write};
9use std::{collections::HashMap, rc::Rc};
10
11type Node = RRC<ir::Port>;
12type Edge = ();
13
14/// A petgraph::DiGraph where ports are the nodes and edges contain no
15/// information.
16pub type CellGraph = DiGraph<Node, Edge>;
17
18/// Constructs a graph based representation of a component. Each node represents
19/// a [`ir::Port`](calyx_ir::Port) and each directed edge (`X -> Y`) means
20/// that `X`'s value written to `Y`.
21///
22/// # Example
23///  ```
24///  c.in = G[done] & b.done ? add.out
25///  ```
26/// creates the edges:
27///  ```
28///  add.out -> c.in
29///  G[done] -> c.in
30///  b.done -> c.in
31///  ```
32///
33/// This representation is useful for asking graph based queries
34/// such as all the reads from a port or all the write to a port.
35#[derive(Clone, Default, Debug)]
36pub struct GraphAnalysis {
37    nodes: HashMap<ir::Canonical, NodeIndex>,
38    graph: CellGraph,
39}
40
41impl From<&ir::Group> for GraphAnalysis {
42    fn from(group: &ir::Group) -> Self {
43        let mut analysis = GraphAnalysis::default();
44
45        for asgn in &group.assignments {
46            analysis.insert_assignment(asgn);
47        }
48
49        analysis
50    }
51}
52
53impl From<&ir::Component> for GraphAnalysis {
54    fn from(component: &ir::Component) -> Self {
55        let mut analysis = GraphAnalysis::default();
56        component.iter_assignments(|asgn| {
57            analysis.insert_assignment(asgn);
58        });
59        component.iter_static_assignments(|asgn| {
60            analysis.insert_assignment(asgn);
61        });
62        analysis
63    }
64}
65
66impl GraphAnalysis {
67    fn insert_assignment<T>(&mut self, asgn: &ir::Assignment<T>) {
68        let GraphAnalysis { nodes, graph } = self;
69        // insert nodes for src and dst ports
70        let src_key = asgn.src.borrow().canonical();
71        let dst_key = asgn.dst.borrow().canonical();
72        let src_node = *nodes
73            .entry(src_key)
74            .or_insert_with(|| graph.add_node(Rc::clone(&asgn.src)));
75        let dst_node = *nodes
76            .entry(dst_key)
77            .or_insert_with(|| graph.add_node(Rc::clone(&asgn.dst)));
78        graph.add_edge(src_node, dst_node, ());
79        // add edges for guards that read from the port in the guard
80        // and write to the dst of the assignment
81        for port in &asgn.guard.all_ports() {
82            let guard_key = port.borrow().canonical();
83            let idx = *nodes
84                .entry(guard_key)
85                .or_insert_with(|| graph.add_node(Rc::clone(port)));
86            graph.add_edge(idx, dst_node, ());
87        }
88    }
89
90    /// Returns an iterator over all the reads from a port.
91    /// Returns an empty iterator if this is an Input port.
92    pub fn reads_from(&self, port: &ir::Port) -> PortIterator<'_> {
93        if let Some(&idx) = self.nodes.get(&port.canonical()) {
94            match port.direction {
95                ir::Direction::Input => PortIterator::empty(),
96                ir::Direction::Output | ir::Direction::Inout => {
97                    PortIterator::new(Box::new(
98                        self.graph.edges_directed(idx, Outgoing).map(
99                            move |edge| {
100                                let node_idx = self
101                                    .graph
102                                    .edge_endpoints(edge.id())
103                                    .unwrap()
104                                    .1;
105                                Rc::clone(&self.graph[node_idx])
106                            },
107                        ),
108                    ))
109                }
110            }
111        } else {
112            PortIterator::empty()
113        }
114    }
115
116    /// Returns an iterator over all the writes to this port.
117    /// Returns an empty iterator if this is an Output port.
118    pub fn writes_to(&self, port: &ir::Port) -> PortIterator<'_> {
119        if let Some(&idx) = self.nodes.get(&port.canonical()) {
120            match port.direction {
121                ir::Direction::Input | ir::Direction::Inout => {
122                    return PortIterator::new(Box::new(
123                        self.graph.edges_directed(idx, Incoming).map(
124                            move |edge| {
125                                let node_idx = self
126                                    .graph
127                                    .edge_endpoints(edge.id())
128                                    .unwrap()
129                                    .0;
130                                Rc::clone(&self.graph[node_idx])
131                            },
132                        ),
133                    ));
134                }
135                ir::Direction::Output => (),
136            }
137        }
138        PortIterator::empty()
139    }
140
141    /// Add each edge in `edges` to the graph.
142    pub fn add_edges(self, edges: &[(RRC<ir::Port>, RRC<ir::Port>)]) -> Self {
143        let Self { graph, nodes } = self;
144        let mut graph = graph;
145        for (a_ref, b_ref) in edges {
146            let a = a_ref.borrow();
147            let b = b_ref.borrow();
148            if let (Some(a_idx), Some(b_idx)) =
149                (nodes.get(&a.canonical()), nodes.get(&b.canonical()))
150            {
151                graph.add_edge(*a_idx, *b_idx, ());
152            }
153        }
154
155        Self { nodes, graph }
156    }
157
158    /// Return a topological sort of this graph.
159    pub fn toposort(&self) -> PortIterator<'_> {
160        PortIterator::new(Box::new(
161            algo::toposort(&self.graph, None)
162                .unwrap()
163                .into_iter()
164                .map(move |node_idx| Rc::clone(&self.graph[node_idx])),
165        ))
166    }
167
168    /// Return a Vec of paths from `start` to `finish`, each path a Vec of ports.
169    pub fn paths(
170        &self,
171        start: &ir::Port,
172        finish: &ir::Port,
173    ) -> Vec<Vec<RRC<ir::Port>>> {
174        let start_idx = self.nodes.get(&start.canonical()).unwrap();
175        let finish_idx = self.nodes.get(&finish.canonical()).unwrap();
176
177        let paths: Vec<Vec<RRC<ir::Port>>> = algo::all_simple_paths(
178            &self.graph,
179            *start_idx,
180            *finish_idx,
181            0,
182            None,
183        )
184        .map(|v: Vec<_>| {
185            v.into_iter()
186                .map(|i| Rc::clone(&self.graph[NodeIndex::new(i.index())]))
187                .collect()
188        })
189        .collect();
190        paths
191    }
192
193    /// Restricts the analysis graph to only include edges
194    /// that are specified by the `filter`.
195    ///
196    /// `filter` is passed references to the `src` and `dst` of each
197    /// edge. When `filter(src, dst)` is `true`, then the edge between
198    /// `src` and `dst` is kept. Otherwise, it is removed.
199    pub fn edge_induced_subgraph<F>(self, mut filter: F) -> Self
200    where
201        F: FnMut(&ir::Port, &ir::Port) -> bool,
202    {
203        let Self { graph, nodes } = self;
204        let graph = graph.filter_map(
205            |_, node| Some(Rc::clone(node)),
206            |idx, _| {
207                let (src_idx, dst_idx) = graph.edge_endpoints(idx).unwrap();
208                if filter(&graph[src_idx].borrow(), &graph[dst_idx].borrow()) {
209                    Some(())
210                } else {
211                    None
212                }
213            },
214        );
215        Self { nodes, graph }
216    }
217
218    /// Returns all the [`Port`](calyx_ir::Port) associated with this instance.
219    pub fn ports(&self) -> Vec<RRC<ir::Port>> {
220        self.graph
221            .raw_nodes()
222            .iter()
223            .map(|node| Rc::clone(&node.weight))
224            .collect()
225    }
226
227    /// Remove all vertices that have no undirected neighbors from the analysis graph.
228    pub fn remove_isolated_vertices(self) -> Self {
229        // Create a node -> neighbor count mapping, that's insensitive to `NodeIndex`s.
230        // `retain_nodes`, called a few lines down, invalidates `NodeIndex`s.
231        let mut num_neighbors: HashMap<(Id, Id), usize> = HashMap::new();
232
233        let Self { graph, nodes } = self;
234        for n_idx in graph.node_indices() {
235            let node = graph[n_idx].borrow();
236            num_neighbors.insert(
237                (node.get_parent_name(), node.name),
238                graph.neighbors_undirected(n_idx).count(),
239            );
240        }
241        let mut graph_copy = graph.clone();
242        let mut nodes_copy = nodes;
243
244        graph_copy.retain_nodes(|_g, n_idx| {
245            let node = graph[n_idx].borrow();
246            *num_neighbors
247                .get(&(node.get_parent_name(), node.name))
248                .unwrap()
249                > 0
250        });
251
252        // retain_nodes breaks existing `NodeIndex`s, so repopulate nodes.
253        for node in graph_copy.raw_nodes() {
254            let port = node.weight.borrow();
255            let n_idx = graph_copy
256                .node_indices()
257                .find(|idx| *graph_copy[*idx].borrow() == *port)
258                .unwrap();
259            nodes_copy.insert(port.canonical(), n_idx);
260        }
261
262        Self {
263            graph: graph_copy,
264            nodes: nodes_copy,
265        }
266    }
267
268    /// Checks if there are cycles in the analysis graph.
269    pub fn has_cycles(&self) -> bool {
270        algo::is_cyclic_directed(&self.graph)
271    }
272}
273
274impl Display for GraphAnalysis {
275    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
276        let mut out = String::new();
277        for idx in self.graph.node_indices() {
278            let src_port = self.graph[idx].borrow();
279            let src =
280                format!("{}.{}", src_port.get_parent_name(), src_port.name);
281            writeln!(
282                &mut out,
283                "{} -> [{}]",
284                src,
285                self.graph
286                    .neighbors_directed(idx, petgraph::Direction::Outgoing)
287                    .map(|idx| {
288                        let port = self.graph[idx].borrow();
289                        format!("{}.{}", port.get_parent_name(), port.name)
290                    })
291                    .collect::<Vec<String>>()
292                    .join(", ")
293            )
294            .expect("Failed to write to ScheduleConflicts string");
295        }
296        out.fmt(f)
297    }
298}
calyx_opt/analysis/graph.rs

calyx_opt/analysis/
graph.rs
