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

1use super::{
2    MopAliasPair, MopFnAliasMap, block::Term, graph::*, types::*, value::*,
3};
4use crate::{
5    def_id::*,
6    analysis::graphs::scc::Scc,
7};
8use rustc_data_structures::fx::FxHashSet;
9use rustc_hir::def_id::DefId;
10use rustc_middle::{
11    mir::{Local, Operand, Place, ProjectionElem, TerminatorKind},
12    ty::self,
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 constant in self.blocks[bb_index].const_value.clone() {
20            self.constants.insert(constant.local, constant.value);
21        }
22        let cur_block = self.blocks[bb_index].clone();
23        for assign in cur_block.assignments {
24            rap_debug!("assign: {:?}", assign);
25            let lv_idx = self.projection(assign.lv);
26            let rv_idx = self.projection(assign.rv);
27
28            self.assign_alias(lv_idx, rv_idx);
29            rap_debug!("Alias sets: {:?}", self.alias_sets)
30        }
31    }
32
33    /* Check the aliases introduced by the terminator of a basic block, i.e., a function call */
34    pub fn alias_bbcall(
35        &mut self,
36        bb_index: usize,
37        fn_map: &mut MopFnAliasMap,
38        recursion_set: &mut HashSet<DefId>,
39    ) {
40        let cur_block = self.blocks[bb_index].clone();
41        if let Term::Call(call) | Term::Drop(call) = cur_block.terminator {
42            if let TerminatorKind::Call {
43                func: Operand::Constant(ref constant),
44                ref args,
45                ref destination,
46                target: _,
47                unwind: _,
48                call_source: _,
49                fn_span: _,
50            } = call.kind
51            {
52                let lv = self.projection(*destination);
53                let mut may_drop = false;
54                if self.values[lv].may_drop {
55                    may_drop = true;
56                }
57
58                let mut merge_vec = Vec::new();
59                merge_vec.push(lv);
60
61                for arg in args {
62                    match arg.node {
63                        Operand::Copy(ref p) | Operand::Move(ref p) => {
64                            let rv = self.projection(*p);
65                            merge_vec.push(rv);
66                            if self.values[rv].may_drop {
67                                may_drop = true;
68                            }
69                        }
70                        //
71                        Operand::Constant(_) => {
72                            merge_vec.push(0);
73                        }
74                    }
75                }
76                if let &ty::FnDef(target_id, _) = constant.const_.ty().kind() {
77                    if may_drop == false {
78                        return;
79                    }
80                    // This function does not introduce new aliases.
81                    if is_no_alias_intrinsic(target_id) {
82                        return;
83                    }
84                    if !self.tcx.is_mir_available(target_id) {
85                        return;
86                    }
87                    rap_debug!("Sync aliases for function call: {:?}", target_id);
88                    let fn_aliases = if fn_map.contains_key(&target_id) {
89                        rap_debug!("Aliases existed");
90                        fn_map.get(&target_id).unwrap()
91                    } else {
92                        /* Fixed-point iteration: this is not perfect */
93                        if recursion_set.contains(&target_id) {
94                            return;
95                        }
96                        recursion_set.insert(target_id);
97                        let mut mop_graph = MopGraph::new(self.tcx, target_id);
98                        mop_graph.find_scc();
99                        mop_graph.check(0, fn_map, recursion_set);
100                        let ret_alias = mop_graph.ret_alias.clone();
101                        rap_info!("Find aliases of {:?}: {:?}", target_id, ret_alias);
102                        fn_map.insert(target_id, ret_alias);
103                        recursion_set.remove(&target_id);
104                        fn_map.get(&target_id).unwrap()
105                    };
106                    if fn_aliases.aliases().is_empty() {
107                        if let Some(l_set_idx) = self.find_alias_set(lv) {
108                            self.alias_sets[l_set_idx].remove(&lv);
109                        }
110                    }
111                    for alias in fn_aliases.aliases().iter() {
112                        if !alias.valuable() {
113                            continue;
114                        }
115                        self.handle_fn_alias(alias, &merge_vec);
116                        rap_debug!("{:?}", self.alias_sets);
117                    }
118                } else if self.values[lv].may_drop {
119                    for rv in &merge_vec {
120                        if self.values[*rv].may_drop && lv != *rv && self.values[lv].is_ptr() {
121                            // We assume they are alias;
122                            // It is a function call and we should not distinguish left or right;
123                            // Merge the alias instead of assign.
124                            self.merge_alias(lv, *rv);
125                        }
126                    }
127                }
128            }
129        }
130    }
131
132    /*
133     * This is the function for field sensitivity
134     * If the projection is a deref, we directly return its local;
135     * If the projection is a field, we further make the id and its first element an alias.
136     */
137    pub fn projection(&mut self, place: Place<'tcx>) -> usize {
138        let local = place.local.as_usize();
139        rap_debug!("projection: place = {:?}, local = {:?}", place, local);
140        let mut value_idx = local;
141        // Projections are leveled
142        // Case 1: (*6).1 involves two projections: a Deref and a Field.
143        // Case 2: (6.0).1 involves two field projections.
144        // We should recursively parse the projection.
145        for proj in place.projection {
146            rap_debug!("proj: {:?}", proj);
147            let new_value_idx = self.values.len();
148            match proj {
149                ProjectionElem::Deref => {}
150                ProjectionElem::Field(field, ty) => {
151                    let field_idx = field.as_usize();
152                    // If the field has not been created as a value, we crate a value;
153                    if !self.values[value_idx].fields.contains_key(&field_idx) {
154                        let ty_env = ty::TypingEnv::post_analysis(self.tcx, self.def_id);
155                        let need_drop = ty.needs_drop(self.tcx, ty_env);
156                        let may_drop = !is_not_drop(self.tcx, ty);
157                        let mut node =
158                            Value::new(new_value_idx, local, need_drop, need_drop || may_drop);
159                        node.kind = kind(ty);
160                        node.father = Some(FatherInfo::new(value_idx, field_idx));
161                        self.values[value_idx].fields.insert(field_idx, node.index);
162                        self.values.push(node);
163                    }
164                    value_idx = *self.values[value_idx].fields.get(&field_idx).unwrap();
165                }
166                _ => {}
167            }
168        }
169        value_idx
170    }
171
172    /// Used to assign alias for a statement.
173    /// Operation: dealiasing the left; aliasing the left with right.
174    /// Synchronize the fields and father nodes iteratively.
175    pub fn assign_alias(&mut self, lv_idx: usize, rv_idx: usize) {
176        rap_debug!("assign_alias: lv = {:?}. rv = {:?}", lv_idx, rv_idx);
177
178        let r_set_idx = if let Some(idx) = self.find_alias_set(rv_idx) {
179            idx
180        } else {
181            self.alias_sets
182                .push([rv_idx].into_iter().collect::<FxHashSet<usize>>());
183            self.alias_sets.len() - 1
184        };
185
186        if let Some(l_set_idx) = self.find_alias_set(lv_idx) {
187            if l_set_idx == r_set_idx {
188                return;
189            }
190            self.alias_sets[l_set_idx].remove(&lv_idx);
191        }
192        let new_l_set_idx = r_set_idx;
193        self.alias_sets[new_l_set_idx].insert(lv_idx);
194
195        if self.values[lv_idx].fields.len() > 0 || self.values[rv_idx].fields.len() > 0 {
196            self.sync_field_alias(lv_idx, rv_idx, 0, true);
197        }
198        if self.values[rv_idx].father != None {
199            self.sync_father_alias(lv_idx, rv_idx, new_l_set_idx);
200        }
201    }
202
203    // Update the aliases of fields.
204    // Case 1, lv = 1; rv = 2; field of rv: 1;
205    // Expected result: [1,2] [1.1,2.1];
206    // Case 2, lv = 0.0, rv = 7, field of rv: 0;
207    // Expected result: [0.0,7] [0.0.0,7.0]
208    pub fn sync_field_alias(&mut self, lv: usize, rv: usize, depth: usize, clear_left: bool) {
209        rap_debug!("sync field aliases for lv:{} rv:{}", lv, rv);
210
211        let max_field_depth = match std::env::var_os("MOP") {
212            Some(val) if val == "0" => 10,
213            Some(val) if val == "1" => 20,
214            Some(val) if val == "2" => 30,
215            Some(val) if val == "3" => 50,
216            _ => 15,
217        };
218
219        if depth > max_field_depth {
220            return;
221        }
222
223        // For the fields of lv; we should remove them from the alias sets;
224        if clear_left {
225            for lv_field in self.values[lv].fields.clone().into_iter() {
226                if let Some(alias_set_idx) = self.find_alias_set(lv_field.1) {
227                    self.alias_sets[alias_set_idx].remove(&lv_field.1);
228                }
229            }
230        }
231        for rv_field in self.values[rv].fields.clone().into_iter() {
232            rap_debug!("rv_field: {:?}", rv_field);
233            if !self.values[lv].fields.contains_key(&rv_field.0) {
234                let mut node = Value::new(
235                    self.values.len(),
236                    self.values[lv].local,
237                    self.values[rv_field.1].need_drop,
238                    self.values[rv_field.1].may_drop,
239                );
240                node.kind = self.values[rv_field.1].kind;
241                node.father = Some(FatherInfo::new(lv, rv_field.0));
242                self.values[lv].fields.insert(rv_field.0, node.index);
243                self.values.push(node);
244            }
245            let lv_field_value_idx = *(self.values[lv].fields.get(&rv_field.0).unwrap());
246
247            rap_debug!(
248                "alias_set_id of rv_field {:?}",
249                self.find_alias_set(rv_field.1)
250            );
251            if let Some(alias_set_idx) = self.find_alias_set(rv_field.1) {
252                self.alias_sets[alias_set_idx].insert(lv_field_value_idx);
253            }
254            rap_debug!("alias sets: {:?}", self.alias_sets);
255            self.sync_field_alias(lv_field_value_idx, rv_field.1, depth + 1, true);
256        }
257    }
258
259    // For example,
260    // Case 1: lv = 1; rv = 2.0; alias set [2, 3]
261    // Expected result: [1, 2.0, 3.0], [2, 3];
262    // Case 2: lv = 1.0; rv = 2; alias set [1, 3]
263    // Expected result: [1.0, 2], [1, 3]
264    pub fn sync_father_alias(&mut self, lv: usize, rv: usize, lv_alias_set_idx: usize) {
265        rap_debug!("sync father aliases for lv:{} rv:{}", lv, rv);
266        let mut father_id = rv;
267        let mut father = self.values[father_id].father.clone();
268        while let Some(father_info) = father {
269            father_id = father_info.father_value_id;
270            let field_id = father_info.field_id;
271            let father_value = self.values[father_id].clone();
272            if let Some(alias_set_idx) = self.find_alias_set(father_id) {
273                for value_idx in self.alias_sets[alias_set_idx].clone() {
274                    // create a new node if the node does not exist;
275                    let field_value_idx = if self.values[value_idx].fields.contains_key(&field_id) {
276                        *self.values[value_idx].fields.get(&field_id).unwrap()
277                    } else {
278                        let mut node = Value::new(
279                            self.values.len(),
280                            self.values[value_idx].local,
281                            self.values[value_idx].need_drop,
282                            self.values[value_idx].may_drop,
283                        );
284                        node.kind = self.values[value_idx].kind;
285                        node.father = Some(FatherInfo::new(value_idx, field_id));
286                        self.values.push(node.clone());
287                        self.values[value_idx].fields.insert(field_id, node.index);
288                        node.index
289                    };
290                    // add the node to the alias_set of lv;
291                    self.alias_sets[lv_alias_set_idx].insert(field_value_idx);
292                }
293            }
294            father = father_value.father;
295        }
296    }
297
298    // Handle aliases introduced by function calls.
299    pub fn handle_fn_alias(&mut self, fn_alias: &MopAliasPair, arg_vec: &[usize]) {
300        rap_debug!(
301            "merge aliases returned by function calls, args: {:?}",
302            arg_vec
303        );
304        rap_debug!("fn alias: {}", fn_alias);
305        if fn_alias.left_local() >= arg_vec.len() || fn_alias.right_local() >= arg_vec.len() {
306            return;
307        }
308
309        let mut lv = arg_vec[fn_alias.left_local()];
310        let mut rv = arg_vec[fn_alias.right_local()];
311        let left_local = self.values[lv].local;
312        let right_local = self.values[rv].local;
313
314        for index in fn_alias.lhs_fields().iter() {
315            if !self.values[lv].fields.contains_key(index) {
316                let need_drop = fn_alias.lhs_need_drop;
317                let may_drop = fn_alias.lhs_may_drop;
318                let mut node = Value::new(self.values.len(), left_local, need_drop, may_drop);
319                node.kind = ValueKind::RawPtr;
320                node.father = Some(FatherInfo::new(lv, *index));
321                self.values[lv].fields.insert(*index, node.index);
322                self.values.push(node);
323            }
324            lv = *self.values[lv].fields.get(index).unwrap();
325        }
326        for index in fn_alias.rhs_fields().iter() {
327            if !self.values[rv].fields.contains_key(index) {
328                let need_drop = fn_alias.rhs_need_drop;
329                let may_drop = fn_alias.rhs_may_drop;
330                let mut node = Value::new(self.values.len(), right_local, need_drop, may_drop);
331                node.kind = ValueKind::RawPtr;
332                node.father = Some(FatherInfo::new(rv, *index));
333                self.values[rv].fields.insert(*index, node.index);
334                self.values.push(node);
335            }
336            rv = *self.values[rv].fields.get(index).unwrap();
337        }
338        // It is a function call and we should not distinguish left or right;
339        // Merge the alias instead of assign.
340        self.merge_alias(lv, rv);
341    }
342
343    pub fn get_field_seq(&self, value: &Value) -> Vec<usize> {
344        let mut field_id_seq = vec![];
345        let mut node_ref = value;
346        while let Some(father) = &node_ref.father {
347            field_id_seq.push(father.field_id);
348            node_ref = &self.values[father.father_value_id];
349        }
350        field_id_seq
351    }
352
353    /// Checks whether a sequence of field projections on a local MIR variable is valid.
354    /// For example, if the type of a local (e.g., 0) has two fields, 0.2 or 0.3 are both invalid.
355    fn is_valid_field(&self, local: usize, field_seq: &[usize]) -> bool {
356        let body = self.tcx.optimized_mir(self.def_id);
357        let mut ty = body.local_decls[Local::from_usize(local)].ty;
358        for &fidx in field_seq {
359            while let ty::TyKind::Ref(_, inner, _) | ty::TyKind::RawPtr(inner, _) = ty.kind() {
360                ty = *inner;
361            }
362            if let ty::Adt(def, _) = ty.kind() {
363                let field_count = def.all_fields().count();
364                if fidx >= field_count {
365                    return false;
366                }
367            } else {
368                // 不是 ADT（struct/tuple），不能投影 field
369                return false;
370            }
371        }
372        true
373    }
374
375    //merge the result of current path to the final result.
376    pub fn merge_results(&mut self) {
377        rap_debug!("merge results");
378        let f_node: Vec<Option<FatherInfo>> =
379            self.values.iter().map(|v| v.father.clone()).collect();
380        for node in self.values.iter() {
381            if node.local > self.arg_size {
382                continue;
383            }
384            for idx in 1..self.values.len() {
385                if !self.is_aliasing(idx, node.index) {
386                    continue;
387                }
388
389                let mut replace = None;
390                if self.values[idx].local > self.arg_size {
391                    for (i, fidx) in f_node.iter().enumerate() {
392                        if let Some(father_info) = fidx {
393                            if i != idx && i != node.index {
394                                // && father_info.father_value_id == f_node[idx] {
395                                for (j, v) in self.values.iter().enumerate() {
396                                    if j != idx
397                                        && j != node.index
398                                        && self.is_aliasing(j, father_info.father_value_id)
399                                        && v.local <= self.arg_size
400                                    {
401                                        replace = Some(&self.values[j]);
402                                    }
403                                }
404                            }
405                        }
406                    }
407                }
408
409                if (self.values[idx].local <= self.arg_size || replace.is_some())
410                    && idx != node.index
411                    && node.local != self.values[idx].local
412                {
413                    let left_node;
414                    let right_node;
415                    match self.values[idx].local {
416                        0 => {
417                            left_node = match replace {
418                                Some(replace_node) => replace_node,
419                                None => &self.values[idx],
420                            };
421                            right_node = node;
422                        }
423                        _ => {
424                            left_node = node;
425                            right_node = match replace {
426                                Some(replace_node) => replace_node,
427                                None => &self.values[idx],
428                            };
429                        }
430                    }
431                    let mut new_alias = MopAliasPair::new(
432                        left_node.local,
433                        left_node.may_drop,
434                        left_node.need_drop,
435                        right_node.local,
436                        right_node.may_drop,
437                        right_node.need_drop,
438                    );
439                    new_alias.fact.lhs_fields = self.get_field_seq(left_node);
440                    new_alias.fact.rhs_fields = self.get_field_seq(right_node);
441                    if new_alias.left_local() == new_alias.right_local() {
442                        continue;
443                    }
444                    if !self.is_valid_field(left_node.local, &new_alias.fact.lhs_fields)
445                        || !self.is_valid_field(right_node.local, &new_alias.fact.rhs_fields)
446                    {
447                        rap_debug!("new_alias with invalid field: {:?}", new_alias);
448                        continue;
449                    }
450                    rap_debug!("new_alias: {:?}", new_alias);
451                    self.ret_alias.add_alias(new_alias);
452                }
453            }
454        }
455        self.compress_aliases();
456    }
457
458    /// Compresses the alias analysis results with a two-step procedure:
459    ///
460    /// 1. **Field Truncation:**
461    ///    For each alias fact, any `lhs_fields` or `rhs_fields` projection longer than one element
462    ///    is truncated to just its first element (e.g., `1.0.1` becomes `1.0`, `1.2.2.0.0` becomes `1.2`).
463    ///    This aggressively flattens all field projections to a single field level.
464    ///
465    /// 2. **Containment Merging:**
466    ///    For all pairs of alias facts with the same locals, if both the truncated `lhs_fields` and
467    ///    `rhs_fields` of one are a (strict) prefix of another, only the more general (shorter) alias
468    ///    is kept. For example:
469    ///      - Keep (0, 1), remove (0.0, 1.1)
470    ///      - But do **not** merge (0, 1.0) and (0, 1.1), since these have different non-prefix fields.
471    ///
472    /// Call this after constructing the alias set to minimize and canonicalize the result.
473    pub fn compress_aliases(&mut self) {
474        // Step 1: Truncate fields to only the first element if present
475        let mut truncated_facts = Vec::new();
476        for fact in self.ret_alias.alias_set.iter() {
477            let mut new_fact = fact.clone();
478            if !new_fact.fact.lhs_fields.is_empty() {
479                new_fact.fact.lhs_fields = vec![new_fact.fact.lhs_fields[0]];
480            }
481            if !new_fact.fact.rhs_fields.is_empty() {
482                new_fact.fact.rhs_fields = vec![new_fact.fact.rhs_fields[0]];
483            }
484            truncated_facts.push(new_fact);
485        }
486        // Clean up alias set and replace with truncated
487        self.ret_alias.alias_set.clear();
488        for fact in truncated_facts {
489            self.ret_alias.alias_set.insert(fact);
490        }
491
492        // Step 2: Containment merging
493        // For the same (left_local, rhs_local), if (a, b) is a prefix of (a', b'), keep only (a, b)
494        let aliases: Vec<MopAliasPair> = self.ret_alias.alias_set.iter().cloned().collect();
495        let n = aliases.len();
496        let mut to_remove: HashSet<MopAliasPair> = HashSet::new();
497
498        for i in 0..n {
499            for j in 0..n {
500                if i == j || to_remove.contains(&aliases[j]) {
501                    continue;
502                }
503                let a = &aliases[i].fact;
504                let b = &aliases[j].fact;
505                // Only merge if both lhs/rhs locals are equal and BOTH are strict prefixes
506                if a.left_local() == b.left_local() && a.right_local() == b.right_local() {
507                    if a.lhs_fields.len() <= b.lhs_fields.len()
508                    && a.lhs_fields == b.lhs_fields[..a.lhs_fields.len()]
509                    && a.rhs_fields.len() <= b.rhs_fields.len()
510                    && a.rhs_fields == b.rhs_fields[..a.rhs_fields.len()]
511                    // Exclude case where fields are exactly the same (avoid self-removal)
512                    && (a.lhs_fields.len() < b.lhs_fields.len() || a.rhs_fields.len() < b.rhs_fields.len())
513                    {
514                        to_remove.insert(aliases[j].clone());
515                    }
516                }
517            }
518        }
519        for alias in to_remove {
520            self.ret_alias.alias_set.remove(&alias);
521        }
522    }
523
524    #[inline(always)]
525    pub fn find_alias_set(&self, e: usize) -> Option<usize> {
526        self.alias_sets.iter().position(|set| set.contains(&e))
527    }
528
529    #[inline(always)]
530    pub fn is_aliasing(&self, e1: usize, e2: usize) -> bool {
531        let s1 = self.find_alias_set(e1);
532        let s2 = self.find_alias_set(e2);
533        s1.is_some() && s1 == s2
534    }
535
536    pub fn merge_alias(&mut self, e1: usize, e2: usize) {
537        let mut s1 = self.find_alias_set(e1);
538        let mut s2 = self.find_alias_set(e2);
539
540        // Create set for e1 if needed
541        if s1.is_none() {
542            self.alias_sets
543                .push([e1].into_iter().collect::<FxHashSet<usize>>());
544            s1 = Some(self.alias_sets.len() - 1);
545        }
546
547        // Create set for e2 if needed
548        if s2.is_none() {
549            self.alias_sets
550                .push([e2].into_iter().collect::<FxHashSet<usize>>());
551            s2 = Some(self.alias_sets.len() - 1);
552        }
553
554        // After creation, fetch indices (unwrap OK)
555        let idx1 = s1.unwrap();
556        let idx2 = s2.unwrap();
557
558        if idx1 == idx2 {
559            return;
560        }
561
562        let set2 = self.alias_sets.remove(idx2);
563        // If idx2 < idx1, removing idx2 shifts idx1 down by one
564        let idx1 = if idx2 < idx1 { idx1 - 1 } else { idx1 };
565        self.alias_sets[idx1].extend(set2);
566
567        if self.values[e1].fields.len() > 0 {
568            self.sync_field_alias(e2, e1, 0, false);
569        }
570        if self.values[e2].fields.len() > 0 {
571            self.sync_field_alias(e1, e2, 0, false);
572        }
573        if self.values[e1].father != None {
574            self.sync_father_alias(e2, e1, idx1);
575        }
576        if self.values[e2].father != None {
577            self.sync_father_alias(e1, e2, idx1);
578        }
579    }
580
581    #[inline(always)]
582    pub fn get_alias_set(&mut self, e: usize) -> Option<FxHashSet<usize>> {
583        if let Some(idx) = self.find_alias_set(e) {
584            Some(self.alias_sets[idx].clone())
585        } else {
586            None
587        }
588    }
589}
590
591pub fn is_no_alias_intrinsic(def_id: DefId) -> bool {
592    if def_id == call_mut() || def_id == clone() || def_id == take() {
593        return true;
594    }
595    return false;
596}
rapx/analysis/core/alias_analysis/default/alias.rs

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