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

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

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