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

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

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