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

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

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