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

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

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