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 FnAliasMap = FxHashMap<DefId, FnAliasPairs>;
12
13/// This is a wrapper struct for displaying FnAliasMap.
14pub struct FnAliasMapWrapper(pub FnAliasMap);
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<FnAliasPairs>;
20    /// Return the aliases among the function arguments and return value for all functions.
21    fn get_all_fn_alias(&self) -> FnAliasMap;
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) -> FnAliasMap {
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 FnAliasPairs {
37    arg_size: usize,
38    alias_set: HashSet<AliasPair>,
39}
40
41impl FnAliasPairs {
42    pub fn new(arg_size: usize) -> FnAliasPairs {
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<AliasPair> {
54        &self.alias_set
55    }
56
57    pub fn add_alias(&mut self, alias: AliasPair) {
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.left_local() >= ra.right_local() {
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 FnAliasPairs {
80    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
81        if self.aliases().is_empty() {
82            write!(f, "null")?;
83        } else {
84            let mut facts: Vec<_> = self.aliases().iter().collect();
85            facts.sort_by(|a, b| {
86                a.left_local
87                    .cmp(&b.left_local)
88                    .then(a.right_local.cmp(&b.right_local))
89                    .then(a.lhs_fields.cmp(&b.lhs_fields))
90                    .then(a.rhs_fields.cmp(&b.rhs_fields))
91            });
92            let joined = facts
93                .into_iter()
94                .map(|fact| format!("{}", fact))
95                .collect::<Vec<_>>()
96                .join(", ");
97            write!(f, "{}", joined)?;
98        }
99        Ok(())
100    }
101}
102
103impl fmt::Display for FnAliasMapWrapper {
104    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
105        writeln!(f, "=== Print alias analysis resuts ===")?;
106        for (def_id, result) in &self.0 {
107            let fn_name = get_fn_name_byid(def_id);
108            writeln!(f, "Alias of {:?}: {}", fn_name, result)?;
109        }
110        Ok(())
111    }
112}
113
114/// AliasPair is used to store the alias relationships between two places.
115/// The result is field-sensitive.
116#[derive(Debug, Clone, Hash, PartialEq, Eq)]
117pub struct AliasPair {
118    pub left_local: usize,
119    pub lhs_fields: Vec<usize>,
120    pub right_local: usize,
121    pub rhs_fields: Vec<usize>,
122}
123
124impl AliasPair {
125    pub fn new(left_local: usize, right_local: usize) -> AliasPair {
126        AliasPair {
127            left_local,
128            lhs_fields: Vec::<usize>::new(),
129            right_local,
130            rhs_fields: Vec::<usize>::new(),
131        }
132    }
133
134    /// Swap the two elements of an alias pair, i.e., left to right, and right to left.
135    pub fn swap(&mut self) {
136        std::mem::swap(&mut self.left_local, &mut self.right_local);
137        std::mem::swap(&mut self.lhs_fields, &mut self.rhs_fields);
138    }
139
140    pub fn left_local(&self) -> usize {
141        self.left_local
142    }
143
144    pub fn right_local(&self) -> usize {
145        self.right_local
146    }
147
148    pub fn lhs_fields(&self) -> &[usize] {
149        &self.lhs_fields
150    }
151
152    pub fn rhs_fields(&self) -> &[usize] {
153        &self.rhs_fields
154    }
155}
156
157impl fmt::Display for AliasPair {
158    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
159        write!(
160            f,
161            "({},{})",
162            aa_place_desc_str(self.left_local, &self.lhs_fields, true),
163            aa_place_desc_str(self.right_local, &self.rhs_fields, true)
164        )
165    }
166}
167
168fn aa_place_desc_str(no: usize, fields: &[usize], field_sensitive: bool) -> String {
169    let mut result = String::new();
170    result.push_str(&no.to_string());
171    if !field_sensitive {
172        return result;
173    }
174    for num in fields.iter() {
175        result.push('.');
176        result.push_str(&num.to_string());
177    }
178    result
179}
rapx/analysis/core/alias_analysis/mod.rs

rapx/analysis/core/alias_analysis/
mod.rs
