rapx/analysis/core/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::{
11    analysis::{Analysis, graphs::scc::Scc},
12    def_id::*,
13    utils::source::*,
14};
15use graph::MopGraph;
16use rustc_data_structures::fx::FxHashMap;
17use rustc_hir::def_id::DefId;
18use rustc_middle::ty::TyCtxt;
19use std::{cmp::Ordering, collections::HashSet, convert::From, fmt};
20
21pub const VISIT_LIMIT: usize = 1000;
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
93impl PartialOrd for MopAliasPair {
94    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
95        Some(self.cmp(other))
96    }
97}
98
99impl Ord for MopAliasPair {
100    fn cmp(&self, other: &Self) -> Ordering {
101        self.fact
102            .left_local
103            .cmp(&other.fact.left_local)
104            .then_with(|| self.fact.lhs_fields.cmp(&other.fact.lhs_fields))
105            .then_with(|| self.fact.right_local.cmp(&other.fact.right_local))
106            .then_with(|| self.fact.rhs_fields.cmp(&other.fact.rhs_fields))
107            .then_with(|| self.lhs_may_drop.cmp(&other.lhs_may_drop))
108            .then_with(|| self.lhs_need_drop.cmp(&other.lhs_need_drop))
109            .then_with(|| self.rhs_may_drop.cmp(&other.rhs_may_drop))
110            .then_with(|| self.rhs_need_drop.cmp(&other.rhs_need_drop))
111    }
112}
113
114impl fmt::Display for MopAliasPair {
115    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
116        write!(f, "{}", self.fact)
117    }
118}
119
120#[derive(Debug, Clone)]
121pub struct MopFnAliasPairs {
122    arg_size: usize,
123    alias_set: HashSet<MopAliasPair>,
124}
125
126impl fmt::Display for MopFnAliasPairs {
127    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
128        write!(
129            f,
130            "{{{}}}",
131            self.aliases()
132                .iter()
133                .map(|alias| format!("{}", alias.fact))
134                .collect::<Vec<String>>()
135                .join(",")
136        )
137    }
138}
139
140impl MopFnAliasPairs {
141    pub fn new(arg_size: usize) -> MopFnAliasPairs {
142        Self {
143            arg_size,
144            alias_set: HashSet::new(),
145        }
146    }
147
148    pub fn arg_size(&self) -> usize {
149        self.arg_size
150    }
151
152    pub fn aliases(&self) -> &HashSet<MopAliasPair> {
153        &self.alias_set
154    }
155
156    pub fn add_alias(&mut self, alias: MopAliasPair) {
157        self.alias_set.insert(alias);
158    }
159
160    pub fn len(&self) -> usize {
161        self.alias_set.len()
162    }
163
164    pub fn sort_alias_index(&mut self) {
165        let alias_set = std::mem::take(&mut self.alias_set);
166        let mut new_alias_set = HashSet::with_capacity(alias_set.len());
167
168        for mut ra in alias_set.into_iter() {
169            if ra.left_local() >= ra.right_local() {
170                ra.swap();
171            }
172            new_alias_set.insert(ra);
173        }
174        self.alias_set = new_alias_set;
175    }
176}
177
178//struct to cache the results for analyzed functions.
179pub type MopFnAliasMap = FxHashMap<DefId, MopFnAliasPairs>;
180
181pub struct AliasAnalyzer<'tcx> {
182    pub tcx: TyCtxt<'tcx>,
183    pub fn_map: FxHashMap<DefId, MopFnAliasPairs>,
184}
185
186impl<'tcx> Analysis for AliasAnalyzer<'tcx> {
187    fn name(&self) -> &'static str {
188        "Alias Analysis (MoP)"
189    }
190
191    fn run(&mut self) {
192        rap_debug!("Start alias analysis via MoP.");
193        let mir_keys = self.tcx.mir_keys(());
194        for local_def_id in mir_keys {
195            self.query_mop(local_def_id.to_def_id());
196        }
197        // Meaning of output: 0 for ret value; 1,2,3,... for corresponding args.
198        for (fn_id, fn_alias) in &mut self.fn_map {
199            let fn_name = get_fn_name(self.tcx, *fn_id);
200            fn_alias.sort_alias_index();
201            if fn_alias.len() > 0 {
202                rap_debug!("Alias found in {:?}: {}", fn_name, fn_alias);
203            }
204        }
205        self.handle_conor_cases();
206    }
207
208    fn reset(&mut self) {
209        todo!();
210    }
211}
212
213impl<'tcx> AliasAnalysis for AliasAnalyzer<'tcx> {
214    fn get_fn_alias(&self, def_id: DefId) -> Option<FnAliasPairs> {
215        self.fn_map.get(&def_id).cloned().map(Into::into)
216    }
217
218    fn get_all_fn_alias(&self) -> FnAliasMap {
219        self.fn_map
220            .iter()
221            .map(|(k, v)| (*k, FnAliasPairs::from(v.clone())))
222            .collect()
223    }
224}
225
226impl<'tcx> AliasAnalyzer<'tcx> {
227    pub fn new(tcx: TyCtxt<'tcx>) -> Self {
228        Self {
229            tcx,
230            fn_map: FxHashMap::default(),
231        }
232    }
233
234    fn handle_conor_cases(&mut self) {
235        let cases = [
236            copy_from_nonoverlapping(),
237            copy_to_nonoverlapping(),
238            copy_to(),
239            copy_from(),
240        ];
241        let alias = MopAliasPair::new(1, true, true, 2, true, true);
242        for (key, value) in self.fn_map.iter_mut() {
243            if cases.iter().any(|lock| lock == key) {
244                value.alias_set.clear();
245                value.alias_set.insert(alias.clone());
246            }
247        }
248    }
249
250    fn query_mop(&mut self, def_id: DefId) {
251        let fn_name = get_fn_name(self.tcx, def_id);
252        if fn_name
253            .as_ref()
254            .map_or(false, |s| s.contains("__raw_ptr_deref_dummy"))
255        {
256            return;
257        }
258        rap_trace!("query_mop: {:?}", fn_name);
259        /* filter const mir */
260        if let Some(_other) = self.tcx.hir_body_const_context(def_id.expect_local()) {
261            return;
262        }
263
264        if self.tcx.is_mir_available(def_id) {
265            let mut mop_graph = MopGraph::new(self.tcx, def_id);
266            rap_debug!("Mop graph crated: {}", mop_graph);
267            rap_debug!("Search scc components in the graph.");
268            mop_graph.find_scc();
269            rap_trace!("After searching scc: {}", mop_graph);
270            let mut recursion_set = HashSet::default();
271            mop_graph.check(0, &mut self.fn_map, &mut recursion_set);
272            if mop_graph.visit_times > VISIT_LIMIT {
273                rap_trace!("Over visited: {:?}", def_id);
274            }
275            self.fn_map.insert(def_id, mop_graph.ret_alias);
276        } else {
277            rap_trace!("Mir is not available at {}", self.tcx.def_path_str(def_id));
278        }
279    }
280
281    pub fn get_all_fn_alias_raw(&mut self) -> MopFnAliasMap {
282        self.fn_map.clone()
283    }
284}
rapx/analysis/core/alias_analysis/default/mod.rs

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