rapx/analysis/core/alias_analysis/
mod.rs

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

rapx/analysis/core/alias_analysis/
mod.rs
