rapx/analysis/alias_analysis/default/
mod.rs

1pub mod alias;
2pub mod assign;
3pub mod block;
4pub mod graph;
5pub mod mop;
6pub mod types;
7pub mod value;
8
9use super::{AliasAnalysis, AliasPair, FnAliasMap, FnAliasPairs};
10use crate::compat::FxHashMap;
11use crate::{
12    analysis::{Analysis, path_analysis::default::PathAnalyzer},
13    def_id::*,
14    utils::source::*,
15};
16use graph::AliasGraph;
17use rustc_hir::def_id::DefId;
18use rustc_middle::ty::TyCtxt;
19use std::{collections::HashSet, convert::From, fmt};
20
21pub const VISIT_LIMIT: usize = 80;
22
23#[derive(Debug, Clone, Hash, PartialEq, Eq)]
24pub struct MopAliasPair {
25    pub fact: AliasPair,
26    pub lhs_may_drop: bool,
27    pub lhs_need_drop: bool,
28    pub rhs_may_drop: bool,
29    pub rhs_need_drop: bool,
30}
31
32impl MopAliasPair {
33    pub fn new(
34        left_local: usize,
35        lhs_may_drop: bool,
36        lhs_need_drop: bool,
37        right_local: usize,
38        rhs_may_drop: bool,
39        rhs_need_drop: bool,
40    ) -> MopAliasPair {
41        MopAliasPair {
42            fact: AliasPair::new(left_local, right_local),
43            lhs_may_drop,
44            lhs_need_drop,
45            rhs_may_drop,
46            rhs_need_drop,
47        }
48    }
49
50    pub fn valuable(&self) -> bool {
51        return self.lhs_may_drop && self.rhs_may_drop;
52    }
53
54    pub fn swap(&mut self) {
55        self.fact.swap();
56        std::mem::swap(&mut self.lhs_may_drop, &mut self.rhs_may_drop);
57        std::mem::swap(&mut self.lhs_need_drop, &mut self.rhs_need_drop);
58    }
59
60    pub fn left_local(&self) -> usize {
61        self.fact.left_local
62    }
63
64    pub fn right_local(&self) -> usize {
65        self.fact.right_local
66    }
67
68    pub fn lhs_fields(&self) -> &[usize] {
69        &self.fact.lhs_fields
70    }
71
72    pub fn rhs_fields(&self) -> &[usize] {
73        &self.fact.rhs_fields
74    }
75}
76
77impl From<MopAliasPair> for AliasPair {
78    fn from(m: MopAliasPair) -> Self {
79        m.fact
80    }
81}
82
83impl From<MopFnAliasPairs> for FnAliasPairs {
84    fn from(m: MopFnAliasPairs) -> Self {
85        let alias_set = m.alias_set.into_iter().map(Into::into).collect(); // MopAliasPair -> AliasPair
86        FnAliasPairs {
87            arg_size: m.arg_size,
88            alias_set,
89        }
90    }
91}
92
93#[derive(Debug, Clone)]
94pub struct MopFnAliasPairs {
95    arg_size: usize,
96    alias_set: HashSet<MopAliasPair>,
97}
98
99impl fmt::Display for MopFnAliasPairs {
100    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
101        write!(
102            f,
103            "{{{}}}",
104            self.aliases()
105                .iter()
106                .map(|alias| format!("{}", alias.fact))
107                .collect::<Vec<String>>()
108                .join(",")
109        )
110    }
111}
112
113impl MopFnAliasPairs {
114    pub fn new(arg_size: usize) -> MopFnAliasPairs {
115        Self {
116            arg_size,
117            alias_set: HashSet::new(),
118        }
119    }
120
121    pub fn arg_size(&self) -> usize {
122        self.arg_size
123    }
124
125    pub fn aliases(&self) -> &HashSet<MopAliasPair> {
126        &self.alias_set
127    }
128
129    pub fn add_alias(&mut self, alias: MopAliasPair) {
130        self.alias_set.insert(alias);
131    }
132
133    pub fn len(&self) -> usize {
134        self.alias_set.len()
135    }
136
137    pub fn sort_alias_index(&mut self) {
138        let alias_set = std::mem::take(&mut self.alias_set);
139        let mut new_alias_set = HashSet::with_capacity(alias_set.len());
140
141        for mut ra in alias_set.into_iter() {
142            if ra.left_local() >= ra.right_local() {
143                ra.swap();
144            }
145            new_alias_set.insert(ra);
146        }
147        self.alias_set = new_alias_set;
148    }
149}
150
151//struct to cache the results for analyzed functions.
152pub type MopFnAliasMap = FxHashMap<DefId, MopFnAliasPairs>;
153
154pub struct AliasAnalyzer<'tcx> {
155    pub tcx: TyCtxt<'tcx>,
156    pub fn_map: FxHashMap<DefId, MopFnAliasPairs>,
157    path_analyzer: PathAnalyzer<'tcx>,
158}
159
160impl<'tcx> Analysis for AliasAnalyzer<'tcx> {
161    fn name(&self) -> &'static str {
162        "Alias Analysis (MoP)"
163    }
164
165    fn run(&mut self) {
166        rap_debug!("Start alias analysis via MoP.");
167        let mir_keys = self.tcx.mir_keys(());
168        for local_def_id in mir_keys {
169            self.query_alias_graph(local_def_id.to_def_id());
170        }
171        // Meaning of output: 0 for ret value; 1,2,3,... for corresponding args.
172        for (fn_id, fn_alias) in &mut self.fn_map {
173            let fn_name = get_fn_name(self.tcx, *fn_id);
174            fn_alias.sort_alias_index();
175            if fn_alias.len() > 0 {
176                rap_debug!("Alias found in {:?}: {}", fn_name, fn_alias);
177            }
178        }
179        self.handle_conor_cases();
180    }
181
182    fn reset(&mut self) {
183        todo!();
184    }
185}
186
187impl<'tcx> AliasAnalysis for AliasAnalyzer<'tcx> {
188    fn get_fn_alias(&self, def_id: DefId) -> Option<FnAliasPairs> {
189        self.fn_map.get(&def_id).cloned().map(Into::into)
190    }
191
192    fn get_all_fn_alias(&self) -> FnAliasMap {
193        self.fn_map
194            .iter()
195            .map(|(k, v)| (*k, FnAliasPairs::from(v.clone())))
196            .collect()
197    }
198}
199
200impl<'tcx> AliasAnalyzer<'tcx> {
201    pub fn new(tcx: TyCtxt<'tcx>) -> Self {
202        Self {
203            tcx,
204            fn_map: FxHashMap::default(),
205            path_analyzer: PathAnalyzer::new(tcx, false),
206        }
207    }
208
209    fn handle_conor_cases(&mut self) {
210        let cases = [
211            copy_from_nonoverlapping_opt(),
212            copy_to_nonoverlapping_opt(),
213            copy_to_opt(),
214            copy_from_opt(),
215        ];
216        let alias = MopAliasPair::new(1, true, true, 2, true, true);
217        for (key, value) in self.fn_map.iter_mut() {
218            if contains(&cases, *key) {
219                value.alias_set.clear();
220                value.alias_set.insert(alias.clone());
221            }
222        }
223    }
224
225    fn query_alias_graph(&mut self, def_id: DefId) {
226        let fn_name = get_fn_name(self.tcx, def_id);
227        if fn_name
228            .as_ref()
229            .map_or(false, |s| s.contains("__raw_ptr_deref_dummy"))
230        {
231            return;
232        }
233        rap_trace!("query_alias_graph: {:?}", fn_name);
234        /* filter const mir */
235        if let Some(_other) = self.tcx.hir_body_const_context(def_id.expect_local()) {
236            return;
237        }
238
239        if self.tcx.is_mir_available(def_id) {
240            let paths = self.path_analyzer.analyze(def_id);
241            let path_graph = self
242                .path_analyzer
243                .graphs
244                .get(&def_id)
245                .cloned()
246                .unwrap_or_else(|| {
247                    let mut g =
248                        crate::analysis::path_analysis::graph::PathGraph::new(self.tcx, def_id);
249                    g.find_scc();
250                    g
251                });
252            let mut alias_graph = AliasGraph::from_path_graph(self.tcx, def_id, path_graph);
253            rap_debug!("Alias graph created: {}", alias_graph);
254            rap_debug!("Search scc components in the graph.");
255            alias_graph.find_scc();
256            rap_trace!("After searching scc: {}", alias_graph);
257            let mut recursion_set = HashSet::default();
258            alias_graph.process_function_paths_opt(paths, &mut self.fn_map, &mut recursion_set);
259            if alias_graph.visit_times() > VISIT_LIMIT {
260                rap_trace!("Over visited: {:?}", def_id);
261            }
262            self.fn_map.insert(def_id, alias_graph.ret_alias);
263        } else {
264            rap_trace!("Mir is not available at {}", self.tcx.def_path_str(def_id));
265        }
266    }
267
268    pub fn get_all_fn_alias_raw(&mut self) -> MopFnAliasMap {
269        self.fn_map.clone()
270    }
271
272    pub fn take_path_analyzer(&mut self) -> PathAnalyzer<'tcx> {
273        std::mem::replace(&mut self.path_analyzer, PathAnalyzer::new(self.tcx, false))
274    }
275}
rapx/analysis/alias_analysis/default/mod.rs

rapx/analysis/alias_analysis/default/
mod.rs
