rapx/analysis/alias/default/
mod.rs

1pub mod alias;
2pub mod graph;
3pub mod mop;
4pub mod stmt;
5pub mod types;
6pub mod value;
7
8use super::{AliasAnalysis, AliasPair, FnAliasMap, FnAliasPairs};
9use crate::compat::FxHashMap;
10use crate::{
11    analysis::{Analysis, path::default::PathAnalyzer},
12    def_id::*,
13    utils::source::*,
14};
15use graph::AliasGraph;
16use rustc_hir::def_id::DefId;
17use rustc_middle::ty::TyCtxt;
18use std::{collections::HashSet, fmt};
19
20pub const VISIT_LIMIT: usize = 80;
21
22#[derive(Debug, Clone, Hash, PartialEq, Eq)]
23pub struct MopAliasPair {
24    pub fact: AliasPair,
25    pub lhs_may_drop: bool,
26    pub lhs_need_drop: bool,
27    pub rhs_may_drop: bool,
28    pub rhs_need_drop: bool,
29}
30
31impl MopAliasPair {
32    pub fn new(
33        left_local: usize,
34        lhs_may_drop: bool,
35        lhs_need_drop: bool,
36        right_local: usize,
37        rhs_may_drop: bool,
38        rhs_need_drop: bool,
39    ) -> MopAliasPair {
40        MopAliasPair {
41            fact: AliasPair::new(left_local, right_local),
42            lhs_may_drop,
43            lhs_need_drop,
44            rhs_may_drop,
45            rhs_need_drop,
46        }
47    }
48
49    pub fn swap(&mut self) {
50        self.fact.swap();
51        std::mem::swap(&mut self.lhs_may_drop, &mut self.rhs_may_drop);
52        std::mem::swap(&mut self.lhs_need_drop, &mut self.rhs_need_drop);
53    }
54
55    pub fn left_local(&self) -> usize { self.fact.left_local }
56    pub fn right_local(&self) -> usize { self.fact.right_local }
57    pub fn lhs_fields(&self) -> &[usize] { &self.fact.lhs_fields }
58    pub fn rhs_fields(&self) -> &[usize] { &self.fact.rhs_fields }
59}
60
61impl From<MopAliasPair> for AliasPair {
62    fn from(m: MopAliasPair) -> Self { m.fact }
63}
64
65impl From<MopFnAliasPairs> for FnAliasPairs {
66    fn from(m: MopFnAliasPairs) -> Self {
67        FnAliasPairs { arg_size: m.arg_size, alias_set: m.alias_set.into_iter().map(Into::into).collect() }
68    }
69}
70
71#[derive(Debug, Clone)]
72pub struct MopFnAliasPairs {
73    pub arg_size: usize,
74    pub alias_set: HashSet<MopAliasPair>,
75}
76
77impl fmt::Display for MopFnAliasPairs {
78    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
79        write!(f, "{{{}}}", self.aliases().iter().map(|a| format!("{}", a.fact)).collect::<Vec<_>>().join(","))
80    }
81}
82
83impl MopFnAliasPairs {
84    pub fn new(arg_size: usize) -> Self { Self { arg_size, alias_set: HashSet::new() } }
85    pub fn arg_size(&self) -> usize { self.arg_size }
86    pub fn aliases(&self) -> &HashSet<MopAliasPair> { &self.alias_set }
87    pub fn add_alias(&mut self, alias: MopAliasPair) { self.alias_set.insert(alias); }
88    pub fn len(&self) -> usize { self.alias_set.len() }
89    pub fn sort_alias_index(&mut self) {
90        let alias_set = std::mem::take(&mut self.alias_set);
91        let mut new = HashSet::with_capacity(alias_set.len());
92        for mut ra in alias_set {
93            if ra.left_local() >= ra.right_local() { ra.swap(); }
94            new.insert(ra);
95        }
96        self.alias_set = new;
97    }
98}
99
100pub type MopFnAliasMap = FxHashMap<DefId, MopFnAliasPairs>;
101
102pub struct AliasAnalyzer<'tcx> {
103    pub tcx: TyCtxt<'tcx>,
104    pub fn_map: FxHashMap<DefId, MopFnAliasPairs>,
105    path_analyzer: PathAnalyzer<'tcx>,
106}
107
108impl<'tcx> Analysis for AliasAnalyzer<'tcx> {
109    fn run(&mut self) {
110        rap_debug!("Start alias analysis via MoP.");
111        let mir_keys = self.tcx.mir_keys(());
112        for local_def_id in mir_keys {
113            self.query_alias_graph(local_def_id.to_def_id());
114        }
115        for (fn_id, fn_alias) in &mut self.fn_map {
116            let fn_name = get_fn_name(self.tcx, *fn_id);
117            fn_alias.sort_alias_index();
118            if fn_alias.len() > 0 {
119                rap_debug!("Alias found in {:?}: {}", fn_name, fn_alias);
120            }
121        }
122        self.handle_conor_cases();
123    }
124}
125
126impl<'tcx> AliasAnalysis for AliasAnalyzer<'tcx> {
127    fn get_fn_alias(&self, def_id: DefId) -> Option<FnAliasPairs> {
128        self.fn_map.get(&def_id).cloned().map(Into::into)
129    }
130    fn get_all_fn_alias(&self) -> FnAliasMap {
131        self.fn_map.iter().map(|(k, v)| (*k, FnAliasPairs::from(v.clone()))).collect()
132    }
133}
134
135impl<'tcx> AliasAnalyzer<'tcx> {
136    pub fn new(tcx: TyCtxt<'tcx>) -> Self {
137        Self { tcx, fn_map: FxHashMap::default(), path_analyzer: PathAnalyzer::new(tcx, false) }
138    }
139
140    fn handle_conor_cases(&mut self) {
141        let cases = [copy_from_nonoverlapping_opt(), copy_to_nonoverlapping_opt(), copy_to_opt(), copy_from_opt()];
142        let alias = MopAliasPair::new(1, true, true, 2, true, true);
143        for (key, value) in self.fn_map.iter_mut() {
144            if contains(&cases, *key) {
145                value.alias_set.clear();
146                value.alias_set.insert(alias.clone());
147            }
148        }
149    }
150
151    fn query_alias_graph(&mut self, def_id: DefId) {
152        let fn_name = get_fn_name(self.tcx, def_id);
153        if fn_name.as_ref().map_or(false, |s| s.contains("__raw_ptr_deref_dummy")) { return; }
154        if let Some(_other) = self.tcx.hir_body_const_context(def_id.expect_local()) { return; }
155        if self.tcx.is_mir_available(def_id) {
156            let paths = self.path_analyzer.analyze(def_id);
157            let path_graph = self.path_analyzer.graphs.get(&def_id).cloned().unwrap_or_else(|| {
158                let mut g = crate::analysis::path::graph::PathGraph::new(self.tcx, def_id);
159                g.find_scc();
160                g
161            });
162            let mut alias_graph = AliasGraph::from_path_graph(self.tcx, def_id, path_graph);
163            alias_graph.path_graph.find_scc();
164            let mut recursion_set = HashSet::default();
165            alias_graph.process_function_paths_opt(paths, &mut self.fn_map, &mut recursion_set);
166            if alias_graph.visit_times() > VISIT_LIMIT {
167                rap_trace!("Over visited: {:?}", def_id);
168            }
169            self.fn_map.insert(def_id, alias_graph.ret_alias);
170        }
171    }
172
173    pub fn get_all_fn_alias_raw(&mut self) -> MopFnAliasMap { self.fn_map.clone() }
174    pub fn take_path_analyzer(&mut self) -> PathAnalyzer<'tcx> {
175        std::mem::replace(&mut self.path_analyzer, PathAnalyzer::new(self.tcx, false))
176    }
177}
rapx/analysis/alias/default/mod.rs

rapx/analysis/alias/default/
mod.rs
