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

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

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