Struct MergedNodeFlowGraph

pub(crate) struct MergedNodeFlowGraph<Node: Idx> {
    supernodes: FrozenUnionFind<Node>,
    succ_supernodes: IndexVec<Node, Node>,
}

View of some underlying graph, in which each node’s successors have been merged into a single “supernode”.

The resulting supernodes have no obvious meaning on their own. However, merging successor nodes means that a node’s out-edges can all be combined into a single out-edge, whose flow is the same as the flow (execution count) of its corresponding node in the original graph.

With all node flows now in the original graph now represented as edge flows in the merged graph, it becomes possible to analyze the original node flows using techniques for analyzing edge flows.

Fields

supernodes: FrozenUnionFind<Node>

Maps each node to the supernode that contains it, indicated by some arbitrary “root” node that is part of that supernode.

succ_supernodes: IndexVec<Node, Node>

For each node, stores the single supernode that all of its successors have been merged into.

(Note that each node in a supernode can potentially have a different successor supernode from its peers.)

Implementations

impl<Node: Idx> MergedNodeFlowGraph<Node>

pub(crate) fn for_balanced_graph<G>(graph: G) -> Self

where G: DirectedGraph<Node = Node> + Successors,

Creates a “merged” view of an underlying graph.

The given graph is assumed to have “balanced flow”, though it does not necessarily have to be a BalancedFlowGraph.

fn num_nodes(&self) -> usize

fn is_supernode(&self, node: Node) -> bool

pub(crate) fn make_node_counters( &self, all_nodes_permutation: &[Node], ) -> NodeCounters<Node>

Using the information in this merged graph, together with a given permutation of all nodes in the graph, to create physical counters and counter expressions for each node in the underlying graph.

The given list must contain exactly one copy of each node in the underlying balanced-flow graph. The order of nodes is used as a hint to influence counter allocation:

• Earlier nodes are more likely to receive counter expressions.
• Later nodes are more likely to receive physical counters.

Trait Implementations

impl<Node: Debug + Idx> Debug for MergedNodeFlowGraph<Node>

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

Formats the value using the given formatter.

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 48 bytes