solar_codegen/analysis/
call_graph.rs

1//! Module-level call graph facts for MIR.
2
3use crate::mir::{Function, FunctionId, InstKind, Module};
4use solar_data_structures::map::{FxHashMap, FxHashSet};
5use std::collections::VecDeque;
6
7/// Module-level internal-call graph facts.
8#[derive(Clone, Debug)]
9pub struct CallGraphInfo {
10    callees: FxHashMap<FunctionId, FxHashSet<FunctionId>>,
11    callers: FxHashMap<FunctionId, FxHashSet<FunctionId>>,
12    entry_functions: FxHashSet<FunctionId>,
13    reachable_from_entries: FxHashSet<FunctionId>,
14    recursive_functions: FxHashSet<FunctionId>,
15    has_body: FxHashSet<FunctionId>,
16}
17
18impl CallGraphInfo {
19    /// Computes call graph facts for `module`.
20    #[must_use]
21    pub fn new(module: &Module) -> Self {
22        let mut callees: FxHashMap<FunctionId, FxHashSet<FunctionId>> = FxHashMap::default();
23        let mut callers: FxHashMap<FunctionId, FxHashSet<FunctionId>> = FxHashMap::default();
24        let mut entry_functions = FxHashSet::default();
25        let mut has_body = FxHashSet::default();
26
27        for (func_id, func) in module.functions.iter_enumerated() {
28            if Self::is_entry_function(func) {
29                entry_functions.insert(func_id);
30            }
31            if Self::has_body(func) {
32                has_body.insert(func_id);
33            }
34
35            let direct_callees = Self::collect_internal_callees(func);
36            if !direct_callees.is_empty() {
37                for &callee in &direct_callees {
38                    callers.entry(callee).or_default().insert(func_id);
39                }
40                callees.insert(func_id, direct_callees);
41            }
42        }
43
44        let reachable_from_entries =
45            Self::reachable_from_roots_in_graph(&callees, &entry_functions);
46        let recursive_functions = Self::recursive_functions_in_graph(&callees);
47
48        Self {
49            callees,
50            callers,
51            entry_functions,
52            reachable_from_entries,
53            recursive_functions,
54            has_body,
55        }
56    }
57
58    /// Returns functions directly called by `func`.
59    #[must_use]
60    pub fn callees(&self, func: FunctionId) -> Option<&FxHashSet<FunctionId>> {
61        self.callees.get(&func)
62    }
63
64    /// Returns functions that directly call `func`.
65    #[must_use]
66    pub fn callers(&self, func: FunctionId) -> Option<&FxHashSet<FunctionId>> {
67        self.callers.get(&func)
68    }
69
70    /// Returns entry functions: external ABI entries, constructor, fallback, and receive.
71    #[must_use]
72    pub fn entry_functions(&self) -> &FxHashSet<FunctionId> {
73        &self.entry_functions
74    }
75
76    /// Returns all functions reachable from entry functions.
77    #[must_use]
78    pub fn reachable_from_entries(&self) -> &FxHashSet<FunctionId> {
79        &self.reachable_from_entries
80    }
81
82    /// Returns true if `func` is directly or indirectly recursive.
83    #[must_use]
84    pub fn is_recursive(&self, func: FunctionId) -> bool {
85        self.recursive_functions.contains(&func)
86    }
87
88    /// Returns functions reachable from `roots` that have MIR bodies.
89    #[must_use]
90    pub fn reachable_bodies_from(
91        &self,
92        roots: impl IntoIterator<Item = FunctionId>,
93    ) -> FxHashSet<FunctionId> {
94        let mut reachable = FxHashSet::default();
95        let mut worklist: VecDeque<_> = roots.into_iter().collect();
96
97        while let Some(func) = worklist.pop_front() {
98            let Some(callees) = self.callees.get(&func) else { continue };
99            for &callee in callees {
100                if self.has_body.contains(&callee) && reachable.insert(callee) {
101                    worklist.push_back(callee);
102                }
103            }
104        }
105
106        reachable
107    }
108
109    /// Returns all functions reachable from `roots`.
110    #[must_use]
111    pub fn reachable_from_roots(
112        &self,
113        roots: impl IntoIterator<Item = FunctionId>,
114    ) -> FxHashSet<FunctionId> {
115        let roots: FxHashSet<_> = roots.into_iter().collect();
116        Self::reachable_from_roots_in_graph(&self.callees, &roots)
117    }
118
119    fn collect_internal_callees(func: &Function) -> FxHashSet<FunctionId> {
120        let mut callees = FxHashSet::default();
121        for inst in &func.instructions {
122            if let InstKind::InternalCall { function, .. } = inst.kind {
123                callees.insert(function);
124            }
125        }
126        callees
127    }
128
129    fn is_entry_function(func: &Function) -> bool {
130        func.selector.is_some()
131            || func.attributes.is_constructor
132            || func.attributes.is_fallback
133            || func.attributes.is_receive
134    }
135
136    fn has_body(func: &Function) -> bool {
137        !func.blocks.is_empty()
138    }
139
140    fn reachable_from_roots_in_graph(
141        callees: &FxHashMap<FunctionId, FxHashSet<FunctionId>>,
142        roots: &FxHashSet<FunctionId>,
143    ) -> FxHashSet<FunctionId> {
144        let mut reachable = FxHashSet::default();
145        let mut worklist = VecDeque::new();
146        for &root in roots {
147            reachable.insert(root);
148            worklist.push_back(root);
149        }
150
151        while let Some(func) = worklist.pop_front() {
152            let Some(callees) = callees.get(&func) else { continue };
153            for &callee in callees {
154                if reachable.insert(callee) {
155                    worklist.push_back(callee);
156                }
157            }
158        }
159
160        reachable
161    }
162
163    fn recursive_functions_in_graph(
164        callees: &FxHashMap<FunctionId, FxHashSet<FunctionId>>,
165    ) -> FxHashSet<FunctionId> {
166        let mut recursive = FxHashSet::default();
167        for &func_id in callees.keys() {
168            if Self::has_cycle_from(func_id, callees, &mut FxHashSet::default()) {
169                recursive.insert(func_id);
170            }
171        }
172        recursive
173    }
174
175    fn has_cycle_from(
176        func_id: FunctionId,
177        callees: &FxHashMap<FunctionId, FxHashSet<FunctionId>>,
178        visiting: &mut FxHashSet<FunctionId>,
179    ) -> bool {
180        if !visiting.insert(func_id) {
181            return true;
182        }
183
184        let recursive = callees.get(&func_id).is_some_and(|direct_callees| {
185            direct_callees.iter().any(|&callee| Self::has_cycle_from(callee, callees, visiting))
186        });
187        visiting.remove(&func_id);
188        recursive
189    }
190}
solar_codegen/analysis/call_graph.rs

solar_codegen/analysis/
call_graph.rs
