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

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

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