rustc_mir_transform/coverage/counters/
balanced_flow.rs

Help
1//! A control-flow graph can be said to have “balanced flow” if the flow
2//! (execution count) of each node is equal to the sum of its in-edge flows,
3//! and also equal to the sum of its out-edge flows.
4//!
5//! Control-flow graphs typically have one or more nodes that don't satisfy the
6//! balanced-flow property, e.g.:
7//! - The start node has out-edges, but no in-edges.
8//! - Return nodes have in-edges, but no out-edges.
9//! - `Yield` nodes can have an out-flow that is less than their in-flow.
10//! - Inescapable loops cause the in-flow/out-flow relationship to break down.
11//!
12//! Balanced-flow graphs are nevertheless useful for analysis, so this module
13//! provides a wrapper type ([`BalancedFlowGraph`]) that imposes balanced flow
14//! on an underlying graph. This is done by non-destructively adding synthetic
15//! nodes and edges as necessary.
16
17use rustc_data_structures::graph;
18use rustc_data_structures::graph::iterate::DepthFirstSearch;
19use rustc_data_structures::graph::reversed::ReversedGraph;
20use rustc_index::Idx;
21use rustc_index::bit_set::DenseBitSet;
22
23/// A view of an underlying graph that has been augmented to have “balanced flow”.
24/// This means that the flow (execution count) of each node is equal to the
25/// sum of its in-edge flows, and also equal to the sum of its out-edge flows.
26///
27/// To achieve this, a synthetic "sink" node is non-destructively added to the
28/// graph, with synthetic in-edges from these nodes:
29/// - Any node that has no out-edges.
30/// - Any node that explicitly requires a sink edge, as indicated by a
31///   caller-supplied `force_sink_edge` function.
32/// - Any node that would otherwise be unable to reach the sink, because it is
33///   part of an inescapable loop.
34///
35/// To make the graph fully balanced, there is also a synthetic edge from the
36/// sink node back to the start node.
37///
38/// ---
39/// The benefit of having a balanced-flow graph is that it can be subsequently
40/// transformed in ways that are guaranteed to preserve balanced flow
41/// (e.g. merging nodes together), which is useful for discovering relationships
42/// between the node flows of different nodes in the graph.
43pub(crate) struct BalancedFlowGraph<G: graph::DirectedGraph> {
44    graph: G,
45    sink_edge_nodes: DenseBitSet<G::Node>,
46    pub(crate) sink: G::Node,
47}
48
49impl<G: graph::DirectedGraph> BalancedFlowGraph<G> {
50    /// Creates a balanced view of an underlying graph, by adding a synthetic
51    /// sink node that has in-edges from nodes that need or request such an edge,
52    /// and a single out-edge to the start node.
53    ///
54    /// Assumes that all nodes in the underlying graph are reachable from the
55    /// start node.
56    pub(crate) fn for_graph(graph: G, force_sink_edge: impl Fn(G::Node) -> bool) -> Self
57    where
58        G: graph::ControlFlowGraph,
59    {
60        let mut sink_edge_nodes = DenseBitSet::new_empty(graph.num_nodes());
61        let mut dfs = DepthFirstSearch::new(ReversedGraph::new(&graph));
62
63        // First, determine the set of nodes that explicitly request or require
64        // an out-edge to the sink.
65        for node in graph.iter_nodes() {
66            if force_sink_edge(node) || graph.successors(node).next().is_none() {
67                sink_edge_nodes.insert(node);
68                dfs.push_start_node(node);
69            }
70        }
71
72        // Next, find all nodes that are currently not reverse-reachable from
73        // `sink_edge_nodes`, and add them to the set as well.
74        dfs.complete_search();
75        sink_edge_nodes.union_not(dfs.visited_set());
76
77        // The sink node is 1 higher than the highest real node.
78        let sink = G::Node::new(graph.num_nodes());
79
80        BalancedFlowGraph { graph, sink_edge_nodes, sink }
81    }
82}
83
84impl<G> graph::DirectedGraph for BalancedFlowGraph<G>
85where
86    G: graph::DirectedGraph,
87{
88    type Node = G::Node;
89
90    /// Returns the number of nodes in this balanced-flow graph, which is 1
91    /// more than the number of nodes in the underlying graph, to account for
92    /// the synthetic sink node.
93    fn num_nodes(&self) -> usize {
94        // The sink node's index is already the size of the underlying graph,
95        // so just add 1 to that instead.
96        self.sink.index() + 1
97    }
98}
99
100impl<G> graph::StartNode for BalancedFlowGraph<G>
101where
102    G: graph::StartNode,
103{
104    fn start_node(&self) -> Self::Node {
105        self.graph.start_node()
106    }
107}
108
109impl<G> graph::Successors for BalancedFlowGraph<G>
110where
111    G: graph::StartNode + graph::Successors,
112{
113    fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
114        let real_edges;
115        let sink_edge;
116
117        if node == self.sink {
118            // The sink node has no real out-edges, and one synthetic out-edge
119            // to the start node.
120            real_edges = None;
121            sink_edge = Some(self.graph.start_node());
122        } else {
123            // Real nodes have their real out-edges, and possibly one synthetic
124            // out-edge to the sink node.
125            real_edges = Some(self.graph.successors(node));
126            sink_edge = self.sink_edge_nodes.contains(node).then_some(self.sink);
127        }
128
129        real_edges.into_iter().flatten().chain(sink_edge)
130    }
131}
rustc_mir_transform/coverage/counters/balanced_flow.rs

rustc_mir_transform/coverage/counters/
balanced_flow.rs
