wasmtime/compile/
call_graph.rs

1//! Construction of the call-graph, for the purposes of inlining.
2//!
3//! These call graphs are not necessarily complete or accurate, and Wasmtime's
4//! soundness does not rely on those properties. First off, we do not attempt to
5//! understand indirect calls, which at their worst must force any call analysis
6//! give up and say "the callee could be absolutely any function". More
7//! interestingly, these call graphs are only used for scheduling bottom-up
8//! inlining, so the worst that inaccurate information can do is cause us to
9//! miss inlining opportunities or lose potential parallelism in our
10//! schedule. For best results, however, every direct call that is potentially
11//! inlinable should be reported when constructing these call graphs.
12
13use super::*;
14use core::{
15    fmt::{self, Debug},
16    ops::Range,
17};
18use wasmtime_environ::{EntityRef, SecondaryMap};
19
20/// A call graph reified into a densely packed and quickly accessible
21/// representation.
22///
23/// In a call graph, nodes are functions, and an edge `f --> g` means that the
24/// function `f` calls the function `g`.
25pub struct CallGraph<Node>
26where
27    Node: EntityRef + Debug,
28{
29    /// A map from each node to the subslice of `self.edge_elems` that are its
30    /// edges.
31    edges: SecondaryMap<Node, Range<u32>>,
32
33    /// Densely packed edge elements for `self.edges`.
34    edge_elems: Vec<Node>,
35}
36
37impl<Node> Debug for CallGraph<Node>
38where
39    Node: EntityRef + Debug,
40{
41    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
42        struct Edges<'a, Node: EntityRef + Debug>(&'a CallGraph<Node>);
43
44        impl<'a, Node: EntityRef + Debug> Debug for Edges<'a, Node> {
45            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
46                f.debug_map()
47                    .entries(self.0.nodes().map(|n| (n, self.0.edges(n))))
48                    .finish()
49            }
50        }
51
52        f.debug_struct("CallGraph")
53            .field("edges", &Edges(self))
54            .finish()
55    }
56}
57
58impl<Node> CallGraph<Node>
59where
60    Node: EntityRef + Debug,
61{
62    /// Construct a new call graph.
63    ///
64    /// `funcs` should be an iterator over all function nodes in this call
65    /// graph's translation unit.
66    ///
67    /// The `get_calls` function should yield (by pushing onto the given `Vec`)
68    /// all of the callee function nodes that the given caller function node
69    /// calls.
70    pub fn new(
71        funcs: impl IntoIterator<Item = Node>,
72        mut get_calls: impl FnMut(Node, &mut Vec<Node>) -> Result<()>,
73    ) -> Result<Self> {
74        let funcs = funcs.into_iter();
75
76        let (min, max) = funcs.size_hint();
77        let capacity = max.unwrap_or_else(|| 2 * min);
78        let mut edges = SecondaryMap::with_capacity(capacity);
79        let mut edge_elems = vec![];
80
81        let mut calls = vec![];
82        for caller in funcs {
83            debug_assert!(calls.is_empty());
84            get_calls(caller, &mut calls)?;
85
86            debug_assert_eq!(edges[caller], Range::default());
87            edges[caller] = extend_with_range(&mut edge_elems, calls.drain(..));
88        }
89
90        Ok(CallGraph { edges, edge_elems })
91    }
92
93    /// Get the function nodes in this call graph.
94    pub fn nodes(&self) -> impl ExactSizeIterator<Item = Node> {
95        self.edges.keys()
96    }
97
98    /// Get the callee function nodes that the given caller function node calls.
99    pub fn edges(&self, node: Node) -> &[Node] {
100        let Range { start, end } = self.edges[node].clone();
101        let start = usize::try_from(start).unwrap();
102        let end = usize::try_from(end).unwrap();
103        &self.edge_elems[start..end]
104    }
105}
wasmtime/compile/call_graph.rs

wasmtime/compile/
call_graph.rs
