rapx/analysis/core/alias/
mop.rs

1pub mod alias;
2pub mod graph;
3pub mod mop;
4pub mod types;
5
6use super::{AAFact, AAResult, 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
79#[derive(Debug, Clone)]
80pub struct MopAAResult {
81    arg_size: usize,
82    alias_set: HashSet<MopAAFact>,
83}
84
85impl fmt::Display for MopAAResult {
86    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
87        write!(
88            f,
89            "{{{}}}",
90            self.aliases()
91                .iter()
92                .map(|alias| format!("{}", alias.fact))
93                .collect::<Vec<String>>()
94                .join(",")
95        )
96    }
97}
98
99impl MopAAResult {
100    pub fn new(arg_size: usize) -> MopAAResult {
101        Self {
102            arg_size,
103            alias_set: HashSet::new(),
104        }
105    }
106
107    pub fn arg_size(&self) -> usize {
108        self.arg_size
109    }
110
111    pub fn aliases(&self) -> &HashSet<MopAAFact> {
112        &self.alias_set
113    }
114
115    pub fn add_alias(&mut self, alias: MopAAFact) {
116        self.alias_set.insert(alias);
117    }
118
119    pub fn len(&self) -> usize {
120        self.alias_set.len()
121    }
122
123    pub fn sort_alias_index(&mut self) {
124        let alias_set = std::mem::take(&mut self.alias_set);
125        let mut new_alias_set = HashSet::with_capacity(alias_set.len());
126
127        for mut ra in alias_set.into_iter() {
128            if ra.lhs_no() >= ra.rhs_no() {
129                ra.swap();
130            }
131            new_alias_set.insert(ra);
132        }
133        self.alias_set = new_alias_set;
134    }
135}
136
137impl Into<AAResult> for MopAAResult {
138    fn into(self) -> AAResult {
139        AAResult {
140            arg_size: self.arg_size,
141            alias_set: self.alias_set.into_iter().map(|alias| alias.fact).collect(),
142        }
143    }
144}
145
146//struct to cache the results for analyzed functions.
147pub type FnMap = FxHashMap<DefId, MopAAResult>;
148
149pub struct MopAlias<'tcx> {
150    pub tcx: TyCtxt<'tcx>,
151    pub fn_map: FxHashMap<DefId, MopAAResult>,
152}
153
154impl<'tcx> Analysis for MopAlias<'tcx> {
155    fn name(&self) -> &'static str {
156        "Alias Analysis (MoP)"
157    }
158
159    fn run(&mut self) {
160        rap_debug!("Start alias analysis via MoP.");
161        let mir_keys = self.tcx.mir_keys(());
162        for local_def_id in mir_keys {
163            self.query_mop(local_def_id.to_def_id());
164        }
165        // Meaning of output: 0 for ret value; 1,2,3,... for corresponding args.
166        for (fn_id, fn_alias) in &mut self.fn_map {
167            let fn_name = get_fn_name(self.tcx, *fn_id);
168            fn_alias.sort_alias_index();
169            if fn_alias.len() > 0 {
170                rap_debug!("Alias found in {:?}: {}", fn_name, fn_alias);
171            }
172        }
173        self.handle_conor_cases();
174    }
175
176    fn reset(&mut self) {
177        todo!();
178    }
179}
180
181impl<'tcx, T> AliasAnalysis<T> for MopAlias<'tcx>
182where
183    T: From<MopAAResult> + Clone,
184{
185    fn get_fn_alias(&mut self, def_id: DefId) -> T {
186        self.fn_map
187            .get(&def_id)
188            .expect(&format!("cannot find alias analysis result for {def_id:?}"))
189            .clone()
190            .into()
191    }
192
193    fn get_all_fn_alias(&mut self) -> FxHashMap<DefId, T> {
194        self.fn_map
195            .iter()
196            .map(|(k, v)| (*k, T::from(v.clone())))
197            .collect::<FxHashMap<DefId, T>>()
198    }
199}
200
201impl<'tcx> MopAlias<'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}
rapx/analysis/core/alias/mop.rs

rapx/analysis/core/alias/
mop.rs
