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

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

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