rapx/analysis/core/alias_analysis/default/
alias.rs

1use crate::{
2    analysis::{
3        core::alias_analysis::{default::graph::*, AAFact, AAResult},
4        utils::intrinsic_id::*,
5    },
6    rap_debug,
7};
8use rustc_data_structures::fx::FxHashMap;
9use rustc_hir::def_id::DefId;
10use rustc_middle::{
11    mir::{Operand, Place, ProjectionElem, TerminatorKind},
12    ty,
13};
14use std::collections::HashSet;
15
16impl<'tcx> MopGraph<'tcx> {
17    /* alias analysis for a single block */
18    pub fn alias_bb(&mut self, bb_index: usize) {
19        for stmt in self.blocks[bb_index].const_value.clone() {
20            self.constant.insert(stmt.0, stmt.1);
21        }
22        let cur_block = self.blocks[bb_index].clone();
23        for assign in cur_block.assignments {
24            let mut lv_aliaset_idx = self.projection(false, assign.lv);
25            let rv_aliaset_idx = self.projection(true, assign.rv);
26            rap_debug!("{:?} = {:?}", lv_aliaset_idx, rv_aliaset_idx);
27            match assign.atype {
28                AssignType::Variant => {
29                    self.alias_set[lv_aliaset_idx] = rv_aliaset_idx;
30                    continue;
31                }
32                AssignType::InitBox => {
33                    lv_aliaset_idx = *self.values[lv_aliaset_idx].fields.get(&0).unwrap();
34                }
35                _ => {} // Copy or Move
36            }
37            if self.values[lv_aliaset_idx].local != self.values[rv_aliaset_idx].local {
38                self.merge_alias(lv_aliaset_idx, rv_aliaset_idx, 0);
39            }
40        }
41    }
42
43    /* Check the aliases introduced by the terminators (function call) of a scc block */
44    pub fn alias_bbcall(
45        &mut self,
46        bb_index: usize,
47        fn_map: &mut FxHashMap<DefId, AAResult>,
48        recursion_set: &mut HashSet<DefId>,
49    ) {
50        let cur_block = self.blocks[bb_index].clone();
51        for call in cur_block.calls {
52            if let TerminatorKind::Call {
53                func: Operand::Constant(ref constant),
54                ref args,
55                ref destination,
56                target: _,
57                unwind: _,
58                call_source: _,
59                fn_span: _,
60            } = call.kind
61            {
62                let lv = self.projection(false, *destination);
63                let mut merge_vec = Vec::new();
64                merge_vec.push(lv);
65                for arg in args {
66                    match arg.node {
67                        Operand::Copy(ref p) => {
68                            let rv = self.projection(true, *p);
69                            merge_vec.push(rv);
70                        }
71                        Operand::Move(ref p) => {
72                            let rv = self.projection(true, *p);
73                            merge_vec.push(rv);
74                        }
75                        Operand::Constant(_) => {
76                            merge_vec.push(0);
77                        }
78                    }
79                }
80                if let ty::FnDef(ref target_id, _) = constant.const_.ty().kind() {
81                    if self.tcx.is_mir_available(*target_id) {
82                        rap_debug!("target_id {:?}", target_id);
83                        if fn_map.contains_key(target_id) {
84                            let assignments = fn_map.get(target_id).unwrap();
85                            for assign in assignments.aliases().iter() {
86                                self.merge(assign, &merge_vec);
87                            }
88                        } else {
89                            /* Fixed-point iteration: this is not perfect */
90                            if recursion_set.contains(target_id) {
91                                continue;
92                            }
93                            recursion_set.insert(*target_id);
94                            let mut mop_graph = MopGraph::new(self.tcx, *target_id);
95                            mop_graph.solve_scc();
96                            mop_graph.check(0, fn_map, recursion_set);
97                            let ret_alias = mop_graph.ret_alias.clone();
98                            for assign in ret_alias.aliases().iter() {
99                                self.merge(assign, &merge_vec);
100                            }
101                            fn_map.insert(*target_id, ret_alias);
102                            recursion_set.remove(target_id);
103                        }
104                    } else {
105                        if target_id.index.as_usize() == CALL_MUT {
106                            continue;
107                        }
108
109                        let mut right_set = Vec::new();
110                        for rv in &merge_vec {
111                            if lv != *rv {
112                                right_set.push(*rv);
113                            }
114                        }
115                        if right_set.len() == 1 {
116                            self.merge_alias(lv, right_set[0], 0);
117                        }
118                    }
119                }
120            }
121        }
122    }
123
124    /*
125     * This is the function for field sensitivity
126     * If the projection is a deref, we directly return its head alias or alias[0].
127     * If the id is not a ref, we further make the id and its first element an alias, i.e., level-insensitive
128     *
129     */
130    pub fn projection(&mut self, is_right: bool, place: Place<'tcx>) -> usize {
131        let mut local = place.local.as_usize();
132        let mut proj_id: usize = local;
133        for proj in place.projection {
134            let new_id = self.values.len();
135            match proj {
136                ProjectionElem::Deref => {
137                    proj_id = self.values[proj_id].index;
138                }
139                /*
140                 * Objective: 2 = 1.0; 0 = 2.0; => 0 = 1.0.0
141                 */
142                ProjectionElem::Field(field, _ty) => {
143                    if is_right && self.values[proj_id].index != proj_id {
144                        proj_id = self.values[proj_id].index;
145                        local = self.values[proj_id].local;
146                    }
147                    let field_idx = field.as_usize();
148                    if let std::collections::hash_map::Entry::Vacant(e) =
149                        self.values[proj_id].fields.entry(field_idx)
150                    {
151                        let mut node = ValueNode::new(new_id, local);
152                        node.field_id = field_idx;
153                        e.insert(node.index);
154                        self.alias_set.push(self.values.len());
155                        self.values.push(node);
156                    }
157                    proj_id = *self.values[proj_id].fields.get(&field_idx).unwrap();
158                }
159                _ => {}
160            }
161        }
162        proj_id
163    }
164
165    //assign alias for a variable.
166    pub fn merge_alias(&mut self, lv: usize, rv: usize, depth: usize) {
167        rap_debug!("Alias set now: {:?}", self.alias_set);
168        // println!("A:{:?} V:{:?}", self.alias_set, self.values.len());
169        self.union_merge(lv, rv);
170        // println!("Li:{} Ri:{} L:{:?} R:{:?} A:{:?} V:{:?}", self.values[lv].index, self.values[rv].index, self.values[lv].alias ,self.values[rv].alias, self.alias_set, self.values.len());
171        rap_debug!(
172            "Update the alias set for lv:{} rv:{} set:{:?}",
173            lv,
174            rv,
175            self.alias_set
176        );
177
178        let max_field_depth = match std::env::var_os("ALIAS") {
179            Some(val) if val == "0" => 10,
180            Some(val) if val == "1" => 20,
181            Some(val) if val == "2" => 30,
182            Some(val) if val == "3" => 50,
183            _ => 15,
184        };
185
186        if depth > max_field_depth {
187            return;
188        }
189
190        for field in self.values[rv].fields.clone().into_iter() {
191            if !self.values[lv].fields.contains_key(&field.0) {
192                let mut node = ValueNode::new(self.values.len(), self.values[lv].local);
193                node.field_id = field.0;
194                self.values[lv].fields.insert(field.0, node.index);
195                self.alias_set.push(self.values.len());
196                self.values.push(node);
197            }
198            let lv_field = *(self.values[lv].fields.get(&field.0).unwrap());
199            self.merge_alias(lv_field, field.1, depth + 1);
200        }
201    }
202
203    //inter-procedure instruction to merge alias.
204    pub fn merge(&mut self, ret_alias: &AAFact, arg_vec: &[usize]) {
205        rap_debug!("{:?}", ret_alias);
206        if ret_alias.lhs_no() >= arg_vec.len() || ret_alias.rhs_no() >= arg_vec.len() {
207            rap_debug!("Vector error!");
208            return;
209        }
210        let left_init = arg_vec[ret_alias.lhs_no()];
211        let mut right_init = arg_vec[ret_alias.rhs_no()];
212        let mut lv = left_init;
213        let mut rv = right_init;
214        for index in ret_alias.lhs_fields().iter() {
215            if !self.values[lv].fields.contains_key(index) {
216                let mut node = ValueNode::new(self.values.len(), left_init);
217                node.field_id = *index;
218                self.values[lv].fields.insert(*index, node.index);
219                self.alias_set.push(self.values.len());
220                self.values.push(node);
221            }
222            lv = *self.values[lv].fields.get(index).unwrap();
223        }
224        for index in ret_alias.rhs_fields().iter() {
225            if self.union_is_same(rv, self.alias_set[rv]) {
226                right_init = self.values[rv].local;
227            }
228            if !self.values[rv].fields.contains_key(index) {
229                let mut node = ValueNode::new(self.values.len(), right_init);
230                node.field_id = *index;
231                self.values[rv].fields.insert(*index, node.index);
232                self.alias_set.push(self.values.len());
233                self.values.push(node);
234            }
235            rv = *self.values[rv].fields.get(index).unwrap();
236        }
237        self.merge_alias(lv, rv, 0);
238    }
239
240    //merge the result of current path to the final result.
241    pub fn merge_results(&mut self, results_nodes: Vec<ValueNode>) {
242        for node in results_nodes.iter() {
243            if node.local <= self.arg_size
244                && (self.union_is_same(node.index, self.alias_set[node.index])
245                    || self.alias_set[node.index] != node.index)
246            {
247                if self.values.len() == 1 {
248                    return;
249                }
250                let f_node: Vec<usize> = results_nodes.iter().map(|v| v.father).collect();
251
252                for idx in 1..self.values.len() {
253                    if !self.union_is_same(idx, node.index) {
254                        continue;
255                    }
256
257                    let mut replace = None;
258                    if results_nodes[idx].local > self.arg_size {
259                        for (i, &fidx) in f_node.iter().enumerate() {
260                            if i != idx && i != node.index && fidx == f_node[idx] {
261                                for (j, v) in results_nodes.iter().enumerate() {
262                                    if j != idx
263                                        && j != node.index
264                                        && self.union_is_same(j, fidx)
265                                        && v.local <= self.arg_size
266                                    {
267                                        replace = Some(&results_nodes[j]);
268                                    }
269                                }
270                            }
271                        }
272                    }
273
274                    if (results_nodes[idx].local <= self.arg_size || replace.is_some())
275                        && idx != node.index
276                        && node.local != results_nodes[idx].local
277                    {
278                        let left_node;
279                        let right_node;
280                        match results_nodes[idx].local {
281                            0 => {
282                                left_node = match replace {
283                                    Some(replace_node) => replace_node,
284                                    None => &results_nodes[idx],
285                                };
286                                right_node = node;
287                            }
288                            _ => {
289                                left_node = node;
290                                right_node = match replace {
291                                    Some(replace_node) => replace_node,
292                                    None => &results_nodes[idx],
293                                };
294                            }
295                        }
296                        let mut new_alias = AAFact::new(left_node.local, right_node.local);
297                        new_alias.lhs_fields = self.get_field_seq(left_node);
298                        new_alias.rhs_fields = self.get_field_seq(right_node);
299                        if new_alias.lhs_no() == 0 && new_alias.rhs_no() == 0 {
300                            return;
301                        }
302                        self.ret_alias.add_alias(new_alias);
303                    }
304                }
305            }
306        }
307    }
308
309    pub fn get_field_seq(&self, value: &ValueNode) -> Vec<usize> {
310        let mut field_id_seq = vec![];
311        let mut node_ref = value;
312        while node_ref.field_id != usize::MAX {
313            field_id_seq.push(node_ref.field_id);
314            node_ref = &self.values[value.father];
315        }
316        field_id_seq
317    }
318
319    #[inline]
320    pub fn union_find(&mut self, e: usize) -> usize {
321        let mut r = e;
322        while self.alias_set[r] != r {
323            r = self.alias_set[r];
324        }
325        r
326    }
327
328    #[inline]
329    pub fn union_merge(&mut self, e1: usize, e2: usize) {
330        let f1 = self.union_find(e1);
331        let f2 = self.union_find(e2);
332
333        if f1 < f2 {
334            self.alias_set[f2] = f1;
335        }
336        if f1 > f2 {
337            self.alias_set[f1] = f2;
338        }
339
340        for member in 0..self.alias_set.len() {
341            self.alias_set[member] = self.union_find(self.alias_set[member]);
342        }
343    }
344
345    #[inline]
346    pub fn union_is_same(&mut self, e1: usize, e2: usize) -> bool {
347        let f1 = self.union_find(e1);
348        let f2 = self.union_find(e2);
349        f1 == f2
350    }
351}
rapx/analysis/core/alias_analysis/default/alias.rs

rapx/analysis/core/alias_analysis/default/
alias.rs
