rapx/analysis/core/alias_analysis/mfp/
mod.rs

1pub mod interproc;
2pub mod intraproc;
3pub mod transfer;
4
5use rustc_data_structures::fx::{FxHashMap, FxHashSet};
6use rustc_hir::def_id::DefId;
7use rustc_middle::mir::{Operand, TerminatorKind};
8use rustc_middle::ty::{self, TyCtxt};
9use rustc_mir_dataflow::Analysis;
10use std::cell::RefCell;
11use std::rc::Rc;
12
13use super::{AliasAnalysis, FnAliasMap, FnAliasPairs};
14use crate::analysis::Analysis as RapxAnalysis;
15use intraproc::FnAliasAnalyzer;
16
17/// MFP-based alias analyzer
18pub struct MfpAliasAnalyzer<'tcx> {
19    tcx: TyCtxt<'tcx>,
20    /// Function summaries (alias relationships between arguments and return values)
21    fn_map: FxHashMap<DefId, FnAliasPairs>,
22}
23
24impl<'tcx> MfpAliasAnalyzer<'tcx> {
25    /// Create a new MFP alias analyzer
26    pub fn new(tcx: TyCtxt<'tcx>) -> Self {
27        MfpAliasAnalyzer {
28            tcx,
29            fn_map: FxHashMap::default(),
30        }
31    }
32
33    /// Get argument count for a function (returns None if MIR not available)
34    fn get_arg_count(&self, def_id: DefId) -> Option<usize> {
35        if !self.tcx.is_mir_available(def_id) {
36            return None;
37        }
38        // Skip const contexts (only applicable to local functions)
39        if let Some(local_def_id) = def_id.as_local() {
40            if self.tcx.hir_body_const_context(local_def_id).is_some() {
41                return None;
42            }
43        }
44        let body = self.tcx.optimized_mir(def_id);
45        Some(body.arg_count)
46    }
47
48    /// Analyze a single function
49    fn analyze_function(
50        &mut self,
51        def_id: DefId,
52        fn_summaries: &Rc<RefCell<FxHashMap<DefId, FnAliasPairs>>>,
53    ) {
54        let fn_name = self.tcx.def_path_str(def_id);
55
56        // Skip functions without MIR
57        if !self.tcx.is_mir_available(def_id) {
58            return;
59        }
60
61        // Skip const contexts (only applicable to local functions)
62        if let Some(local_def_id) = def_id.as_local() {
63            if self.tcx.hir_body_const_context(local_def_id).is_some() {
64                return;
65            }
66        }
67
68        // Skip dummy functions
69        if fn_name.contains("__raw_ptr_deref_dummy") {
70            return;
71        }
72
73        // Get the optimized MIR
74        let body = self.tcx.optimized_mir(def_id);
75
76        // Create the intraprocedural analyzer
77        let analyzer = FnAliasAnalyzer::new(self.tcx, def_id, body, fn_summaries.clone());
78
79        // Run the dataflow analysis
80        let mut results = analyzer
81            .iterate_to_fixpoint(self.tcx, body, None)
82            .into_results_cursor(body);
83
84        // (Debug)
85        let iter_cnt = *results.analysis().bb_iter_cnt.borrow();
86        let bb_cnt = body.basic_blocks.iter().len();
87        rap_debug!(
88            "[Alias-mfp] {fn_name} {iter_cnt}/{bb_cnt}, analysis ratio: {:.2}",
89            (iter_cnt as f32) / (bb_cnt as f32)
90        );
91
92        // Extract the function summary from this analysis
93        let new_summary = interproc::extract_summary(&mut results, body, def_id);
94
95        // Join with existing summary to maintain monotonicity
96        // This ensures we never lose alias relationships discovered in previous iterations
97        if let Some(old_summary) = self.fn_map.get_mut(&def_id) {
98            for alias in new_summary.aliases() {
99                old_summary.add_alias(alias.clone());
100            }
101        } else {
102            self.fn_map.insert(def_id, new_summary);
103        }
104    }
105
106    /// Recursively collect all reachable functions with available MIR
107    fn collect_reachable_functions(&self, def_id: DefId, reachable: &mut FxHashSet<DefId>) {
108        // Prevent infinite recursion
109        if reachable.contains(&def_id) {
110            return;
111        }
112
113        // Check if MIR is available
114        if self.get_arg_count(def_id).is_none() {
115            return;
116        }
117
118        // Mark as visited
119        reachable.insert(def_id);
120
121        // Traverse all basic blocks in the MIR body
122        let body = self.tcx.optimized_mir(def_id);
123        for bb_data in body.basic_blocks.iter() {
124            if let Some(terminator) = &bb_data.terminator {
125                if let TerminatorKind::Call { func, .. } = &terminator.kind {
126                    if let Operand::Constant(c) = func {
127                        if let ty::FnDef(callee_def_id, _) = c.ty().kind() {
128                            // Recursively collect called functions
129                            self.collect_reachable_functions(*callee_def_id, reachable);
130                        }
131                    }
132                }
133            }
134        }
135    }
136}
137
138impl<'tcx> RapxAnalysis for MfpAliasAnalyzer<'tcx> {
139    fn name(&self) -> &'static str {
140        "Alias Analysis (MFP)"
141    }
142
143    fn run(&mut self) {
144        // Get all functions to analyze
145        let mir_keys = self.tcx.mir_keys(());
146
147        // Shared function summaries for interprocedural analysis
148        let fn_summaries = Rc::new(RefCell::new(FxHashMap::default()));
149
150        // Step 1: Collect all reachable functions with available MIR
151        let mut reachable_functions = FxHashSet::default();
152
153        // Start from mir_keys and recursively collect
154        for local_def_id in mir_keys.iter() {
155            self.collect_reachable_functions(local_def_id.to_def_id(), &mut reachable_functions);
156        }
157
158        // Step 2: Initialize function summaries to ⊥ (empty) for all reachable functions
159        for def_id in reachable_functions.iter() {
160            if let Some(arg_count) = self.get_arg_count(*def_id) {
161                self.fn_map.insert(*def_id, FnAliasPairs::new(arg_count));
162            }
163        }
164
165        // Convert to Vec for iteration
166        let reachable_vec: Vec<DefId> = reachable_functions.iter().copied().collect();
167
168        // Step 3: Fixpoint iteration
169        const MAX_ITERATIONS: usize = 10;
170        let mut iteration = 0;
171
172        loop {
173            iteration += 1;
174            let mut changed = false;
175
176            // Sync current summaries to fn_summaries (critical for interprocedural analysis)
177            {
178                let mut summaries = fn_summaries.borrow_mut();
179                summaries.clear();
180                for (def_id, summary) in &self.fn_map {
181                    summaries.insert(*def_id, summary.clone());
182                }
183            }
184
185            // Analyze each function with current summaries
186            for def_id in reachable_vec.iter() {
187                // Skip if not analyzable
188                if !self.fn_map.contains_key(def_id) {
189                    continue;
190                }
191
192                // Save old summary for comparison
193                let old_summary = self.fn_map.get(def_id).cloned().unwrap();
194
195                // Re-analyze the function
196                self.analyze_function(*def_id, &fn_summaries);
197
198                // Check if summary changed
199                if let Some(new_summary) = self.fn_map.get(def_id) {
200                    // Compare by checking if alias sets are equal
201                    let old_aliases: std::collections::HashSet<_> =
202                        old_summary.aliases().iter().cloned().collect();
203                    let new_aliases: std::collections::HashSet<_> =
204                        new_summary.aliases().iter().cloned().collect();
205
206                    if old_aliases != new_aliases {
207                        changed = true;
208                        rap_trace!(
209                            "Summary changed for {:?}: {} -> {}",
210                            self.tcx.def_path_str(def_id),
211                            old_summary.len(),
212                            new_summary.len()
213                        );
214                    }
215                }
216            }
217
218            // Check convergence
219            if !changed {
220                rap_trace!(
221                    "Interprocedural analysis converged after {} iterations",
222                    iteration
223                );
224                break;
225            }
226
227            if iteration >= MAX_ITERATIONS {
228                rap_warn!("Reached maximum iterations ({}), stopping", MAX_ITERATIONS);
229                break;
230            }
231        }
232
233        // Step 3: Sort and display results
234        for (fn_id, fn_alias) in &mut self.fn_map {
235            let fn_name = self.tcx.def_path_str(fn_id);
236            fn_alias.sort_alias_index();
237            if fn_alias.len() > 0 {
238                rap_trace!("Alias found in {:?}: {}", fn_name, fn_alias);
239            }
240        }
241    }
242
243    fn reset(&mut self) {
244        self.fn_map.clear();
245    }
246}
247
248impl<'tcx> AliasAnalysis for MfpAliasAnalyzer<'tcx> {
249    fn get_fn_alias(&self, def_id: DefId) -> Option<FnAliasPairs> {
250        self.fn_map.get(&def_id).cloned()
251    }
252
253    fn get_all_fn_alias(&self) -> FnAliasMap {
254        self.fn_map.clone()
255    }
256}
rapx/analysis/core/alias_analysis/mfp/mod.rs

rapx/analysis/core/alias_analysis/mfp/
mod.rs
