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::{AAFact, AAResult, AAResultMap, AliasAnalysis};
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::{collections::HashSet, convert::From, fmt};
20
21pub const VISIT_LIMIT: usize = 1000;
22
23#[derive(Debug, Clone, Hash, PartialEq, Eq)]
24pub struct MopAAFact {
25    pub fact: AAFact,
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 MopAAFact {
33    pub fn new(
34        lhs_no: usize,
35        lhs_may_drop: bool,
36        lhs_need_drop: bool,
37        rhs_no: usize,
38        rhs_may_drop: bool,
39        rhs_need_drop: bool,
40    ) -> MopAAFact {
41        MopAAFact {
42            fact: AAFact::new(lhs_no, rhs_no),
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 lhs_no(&self) -> usize {
61        self.fact.lhs_no
62    }
63
64    pub fn rhs_no(&self) -> usize {
65        self.fact.rhs_no
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<MopAAFact> for AAFact {
78    fn from(m: MopAAFact) -> Self {
79        m.fact
80    }
81}
82
83impl From<MopAAResult> for AAResult {
84    fn from(m: MopAAResult) -> Self {
85        let alias_set = m.alias_set.into_iter().map(Into::into).collect(); // MopAAFact -> AAFact
86        AAResult {
87            arg_size: m.arg_size,
88            alias_set,
89        }
90    }
91}
92
93#[derive(Debug, Clone)]
94pub struct MopAAResult {
95    arg_size: usize,
96    alias_set: HashSet<MopAAFact>,
97}
98
99impl fmt::Display for MopAAResult {
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 MopAAResult {
114    pub fn new(arg_size: usize) -> MopAAResult {
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<MopAAFact> {
126        &self.alias_set
127    }
128
129    pub fn add_alias(&mut self, alias: MopAAFact) {
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.lhs_no() >= ra.rhs_no() {
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 MopAAResultMap = FxHashMap<DefId, MopAAResult>;
153
154pub struct AliasAnalyzer<'tcx> {
155    pub tcx: TyCtxt<'tcx>,
156    pub fn_map: FxHashMap<DefId, MopAAResult>,
157}
158
159impl<'tcx> Analysis for AliasAnalyzer<'tcx> {
160    fn name(&self) -> &'static str {
161        "Alias Analysis (MoP)"
162    }
163
164    fn run(&mut self) {
165        rap_debug!("Start alias analysis via MoP.");
166        let mir_keys = self.tcx.mir_keys(());
167        for local_def_id in mir_keys {
168            self.query_mop(local_def_id.to_def_id());
169        }
170        // Meaning of output: 0 for ret value; 1,2,3,... for corresponding args.
171        for (fn_id, fn_alias) in &mut self.fn_map {
172            let fn_name = get_fn_name(self.tcx, *fn_id);
173            fn_alias.sort_alias_index();
174            if fn_alias.len() > 0 {
175                rap_debug!("Alias found in {:?}: {}", fn_name, fn_alias);
176            }
177        }
178        self.handle_conor_cases();
179    }
180
181    fn reset(&mut self) {
182        todo!();
183    }
184}
185
186impl<'tcx> AliasAnalysis for AliasAnalyzer<'tcx> {
187    fn get_fn_alias(&self, def_id: DefId) -> Option<AAResult> {
188        self.fn_map.get(&def_id).cloned().map(Into::into)
189    }
190
191    fn get_all_fn_alias(&self) -> AAResultMap {
192        self.fn_map
193            .iter()
194            .map(|(k, v)| (*k, AAResult::from(v.clone())))
195            .collect()
196    }
197}
198
199impl<'tcx> AliasAnalyzer<'tcx> {
200    pub fn new(tcx: TyCtxt<'tcx>) -> Self {
201        Self {
202            tcx,
203            fn_map: FxHashMap::default(),
204        }
205    }
206
207    fn handle_conor_cases(&mut self) {
208        let cases = [
209            copy_from_nonoverlapping(),
210            copy_to_nonoverlapping(),
211            copy_to(),
212            copy_from(),
213        ];
214        let alias = MopAAFact::new(1, true, true, 2, true, true);
215        for (key, value) in self.fn_map.iter_mut() {
216            if cases.iter().any(|lock| lock == key) {
217                value.alias_set.clear();
218                value.alias_set.insert(alias.clone());
219            }
220        }
221    }
222
223    fn query_mop(&mut self, def_id: DefId) {
224        let fn_name = get_fn_name(self.tcx, def_id);
225        rap_trace!("query_mop: {:?}", fn_name);
226        /* filter const mir */
227        if let Some(_other) = self.tcx.hir_body_const_context(def_id.expect_local()) {
228            return;
229        }
230
231        if self.tcx.is_mir_available(def_id) {
232            let mut mop_graph = MopGraph::new(self.tcx, def_id);
233            mop_graph.find_scc();
234            let mut recursion_set = HashSet::default();
235            mop_graph.check(0, &mut self.fn_map, &mut recursion_set);
236            if mop_graph.visit_times > VISIT_LIMIT {
237                rap_trace!("Over visited: {:?}", def_id);
238            }
239            self.fn_map.insert(def_id, mop_graph.ret_alias);
240        } else {
241            rap_trace!("Mir is not available at {}", self.tcx.def_path_str(def_id));
242        }
243    }
244
245    pub fn get_all_fn_alias_raw(&mut self) -> MopAAResultMap {
246        self.fn_map.clone()
247    }
248}
rapx/analysis/core/alias_analysis/default/mod.rs

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