rapx/analysis/core/alias_analysis/
mod.rs

1pub mod default;
2pub mod mfp;
3use crate::utils::source::get_fn_name_byid;
4
5use super::super::Analysis;
6use rustc_data_structures::fx::FxHashMap;
7use rustc_hir::def_id::DefId;
8use rustc_span::def_id::LOCAL_CRATE;
9use std::{collections::HashSet, fmt};
10
11/// The data structure to store aliases for a set of functions.
12pub type FnAliasMap = FxHashMap<DefId, FnAliasPairs>;
13
14/// This is a wrapper struct for displaying FnAliasMap.
15pub struct FnAliasMapWrapper(pub FnAliasMap);
16
17/// This trait provides features related to alias analysis.
18pub trait AliasAnalysis: Analysis {
19    /// Return the aliases among the function arguments and return value of a specific function.
20    fn get_fn_alias(&self, def_id: DefId) -> Option<FnAliasPairs>;
21    /// Return the aliases among the function arguments and return value for all functions.
22    fn get_all_fn_alias(&self) -> FnAliasMap;
23    /// Return the aliases among the function arguments and return value for functions of the local
24    /// crate.
25    fn get_local_fn_alias(&self) -> FnAliasMap {
26        self.get_all_fn_alias()
27            .iter()
28            .filter(|(def_id, _)| def_id.krate == LOCAL_CRATE)
29            .map(|(k, v)| (*k, v.clone()))
30            .collect()
31    }
32}
33
34/// To store the alias relationships among arguments and return values.
35/// Each function may have multiple return instructions, leading to different RetAlias.
36#[derive(Debug, Clone)]
37pub struct FnAliasPairs {
38    arg_size: usize,
39    alias_set: HashSet<AliasPair>,
40}
41
42impl FnAliasPairs {
43    pub fn new(arg_size: usize) -> FnAliasPairs {
44        Self {
45            arg_size,
46            alias_set: HashSet::new(),
47        }
48    }
49
50    pub fn arg_size(&self) -> usize {
51        self.arg_size
52    }
53
54    pub fn aliases(&self) -> &HashSet<AliasPair> {
55        &self.alias_set
56    }
57
58    pub fn add_alias(&mut self, alias: AliasPair) {
59        self.alias_set.insert(alias);
60    }
61
62    pub fn len(&self) -> usize {
63        self.alias_set.len()
64    }
65
66    pub fn sort_alias_index(&mut self) {
67        let alias_set = std::mem::take(&mut self.alias_set);
68        let mut new_alias_set = HashSet::with_capacity(alias_set.len());
69
70        for mut ra in alias_set.into_iter() {
71            if ra.left_local() >= ra.right_local() {
72                ra.swap();
73            }
74            new_alias_set.insert(ra);
75        }
76        self.alias_set = new_alias_set;
77    }
78}
79
80impl fmt::Display for FnAliasPairs {
81    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
82        if self.aliases().is_empty() {
83            write!(f, "null")?;
84        } else {
85            let mut facts: Vec<_> = self.aliases().iter().collect();
86            facts.sort_by(|a, b| {
87                a.left_local
88                    .cmp(&b.left_local)
89                    .then(a.right_local.cmp(&b.right_local))
90                    .then(a.lhs_fields.cmp(&b.lhs_fields))
91                    .then(a.rhs_fields.cmp(&b.rhs_fields))
92            });
93            let joined = facts
94                .into_iter()
95                .map(|fact| format!("{}", fact))
96                .collect::<Vec<_>>()
97                .join(", ");
98            write!(f, "{}", joined)?;
99        }
100        Ok(())
101    }
102}
103
104impl fmt::Display for FnAliasMapWrapper {
105    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
106        writeln!(f, "=== Print alias analysis resuts ===")?;
107        for (def_id, result) in &self.0 {
108            let fn_name = get_fn_name_byid(def_id);
109            writeln!(f, "Alias of {:?}: {}", fn_name, result)?;
110        }
111        Ok(())
112    }
113}
114
115/// AliasPair is used to store the alias relationships between two places.
116/// The result is field-sensitive.
117#[derive(Debug, Clone, Hash, PartialEq, Eq)]
118pub struct AliasPair {
119    pub left_local: usize,
120    pub lhs_fields: Vec<usize>,
121    pub right_local: usize,
122    pub rhs_fields: Vec<usize>,
123}
124
125impl AliasPair {
126    pub fn new(left_local: usize, right_local: usize) -> AliasPair {
127        AliasPair {
128            left_local,
129            lhs_fields: Vec::<usize>::new(),
130            right_local,
131            rhs_fields: Vec::<usize>::new(),
132        }
133    }
134
135    /// Swap the two elements of an alias pair, i.e., left to right, and right to left.
136    pub fn swap(&mut self) {
137        std::mem::swap(&mut self.left_local, &mut self.right_local);
138        std::mem::swap(&mut self.lhs_fields, &mut self.rhs_fields);
139    }
140
141    pub fn left_local(&self) -> usize {
142        self.left_local
143    }
144
145    pub fn right_local(&self) -> usize {
146        self.right_local
147    }
148
149    pub fn lhs_fields(&self) -> &[usize] {
150        &self.lhs_fields
151    }
152
153    pub fn rhs_fields(&self) -> &[usize] {
154        &self.rhs_fields
155    }
156}
157
158impl fmt::Display for AliasPair {
159    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
160        write!(
161            f,
162            "({},{})",
163            aa_place_desc_str(self.left_local, &self.lhs_fields, true),
164            aa_place_desc_str(self.right_local, &self.rhs_fields, true)
165        )
166    }
167}
168
169fn aa_place_desc_str(no: usize, fields: &[usize], field_sensitive: bool) -> String {
170    let mut result = String::new();
171    result.push_str(&no.to_string());
172    if !field_sensitive {
173        return result;
174    }
175    for num in fields.iter() {
176        result.push('.');
177        result.push_str(&num.to_string());
178    }
179    result
180}
rapx/analysis/core/alias_analysis/mod.rs

rapx/analysis/core/alias_analysis/
mod.rs
