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

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