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

1use rustc_hir::def_id::DefId;
2use rustc_middle::{
3    mir::{
4        Operand::{Constant, Copy, Move},
5        TerminatorKind,
6    },
7    ty::{TyKind, TypingEnv},
8};
9
10use std::{
11    cell::{Cell, RefCell},
12    collections::HashSet,
13};
14
15use rustc_data_structures::fx::{FxHashMap, FxHashSet};
16
17use crate::analysis::graphs::scc::{SccInfo, SccTree};
18
19use super::{block::Term, graph::*, *};
20
21// rustc analysis threads may have a relatively small stack; keep recursion limits conservative.
22const CHECK_STACK_LIMIT: usize = 96;
23const SCC_DFS_STACK_LIMIT: usize = 128;
24const SCC_PATH_CACHE_LIMIT: usize = 2048;
25
26thread_local! {
27    static CHECK_DEPTH: Cell<usize> = Cell::new(0);
28    static SCC_DFS_DEPTH: Cell<usize> = Cell::new(0);
29    static SCC_PATH_CACHE: RefCell<
30        FxHashMap<SccPathCacheKey, Vec<(Vec<usize>, FxHashMap<usize, usize>)>>
31    > = RefCell::new(FxHashMap::default());
32}
33
34#[derive(Clone, Hash, PartialEq, Eq)]
35struct SccPathCacheKey {
36    def_id: DefId,
37    scc_enter: usize,
38    constraints: Vec<(usize, usize)>,
39}
40
41fn constraints_key(constraints: &FxHashMap<usize, usize>) -> Vec<(usize, usize)> {
42    let mut v: Vec<(usize, usize)> = constraints.iter().map(|(k, val)| (*k, *val)).collect();
43    v.sort_unstable();
44    v
45}
46
47struct DepthLimitGuard {
48    key: &'static std::thread::LocalKey<Cell<usize>>,
49}
50
51fn enter_depth_limit(
52    key: &'static std::thread::LocalKey<Cell<usize>>,
53    limit: usize,
54) -> Option<DepthLimitGuard> {
55    key.with(|d| {
56        let cur = d.get() + 1;
57        d.set(cur);
58        if cur > limit {
59            d.set(cur - 1);
60            None
61        } else {
62            Some(DepthLimitGuard { key })
63        }
64    })
65}
66
67impl Drop for DepthLimitGuard {
68    fn drop(&mut self) {
69        self.key.with(|d| {
70            let cur = d.get();
71            if cur > 0 {
72                d.set(cur - 1);
73            }
74        });
75    }
76}
77
78#[derive(Clone, Hash, PartialEq, Eq)]
79struct PathKey {
80    path: Vec<usize>,
81    constraints: Vec<(usize, usize)>,
82}
83
84impl<'tcx> MopGraph<'tcx> {
85    fn switch_target_for_value(
86        &self,
87        targets: &rustc_middle::mir::SwitchTargets,
88        value: usize,
89    ) -> usize {
90        for (v, bb) in targets.iter() {
91            if v as usize == value {
92                return bb.as_usize();
93            }
94        }
95        targets.otherwise().as_usize()
96    }
97
98    fn unique_otherwise_switch_value(
99        &self,
100        discr: &rustc_middle::mir::Operand<'tcx>,
101        targets: &rustc_middle::mir::SwitchTargets,
102    ) -> Option<usize> {
103        let tcx = self.tcx;
104        let local_decls = &tcx.optimized_mir(self.def_id).local_decls;
105
106        let place = match discr {
107            Copy(p) | Move(p) => Some(*p),
108            _ => None,
109        }?;
110
111        let place_ty = place.ty(local_decls, tcx).ty;
112        let possible_values: Vec<usize> = match place_ty.kind() {
113            TyKind::Bool => vec![0, 1],
114            TyKind::Adt(adt_def, _) if adt_def.is_enum() => (0..adt_def.variants().len()).collect(),
115            _ => return None,
116        };
117
118        let mut seen = FxHashSet::default();
119        for (val, _) in targets.iter() {
120            seen.insert(val as usize);
121        }
122
123        let remaining: Vec<usize> = possible_values
124            .into_iter()
125            .filter(|v| !seen.contains(v))
126            .collect();
127
128        if remaining.len() == 1 {
129            Some(remaining[0])
130        } else {
131            None
132        }
133    }
134
135    fn record_scc_exit_path(
136        &self,
137        scc: &SccInfo,
138        node: usize,
139        constraints: &FxHashMap<usize, usize>,
140        cur_path: &Vec<usize>,
141        out: &mut Vec<(Vec<usize>, FxHashMap<usize, usize>)>,
142        seen_paths: &mut FxHashSet<PathKey>,
143    ) {
144        if !scc.exits.iter().any(|e| e.exit == node) {
145            return;
146        }
147
148        let key = PathKey {
149            path: cur_path.clone(),
150            constraints: constraints_key(constraints),
151        };
152        if seen_paths.insert(key) {
153            out.push((cur_path.clone(), constraints.clone()));
154        }
155    }
156
157    fn possible_switch_values_for_constraint_id(&self, discr_local: usize) -> Option<Vec<usize>> {
158        let tcx = self.tcx;
159        let local_decls = &tcx.optimized_mir(self.def_id).local_decls;
160        if discr_local >= local_decls.len() {
161            return None;
162        }
163
164        let ty = local_decls[rustc_middle::mir::Local::from_usize(discr_local)].ty;
165        match ty.kind() {
166            TyKind::Bool => Some(vec![0, 1]),
167            TyKind::Adt(adt_def, _) if adt_def.is_enum() => {
168                Some((0..adt_def.variants().len()).collect())
169            }
170            _ => None,
171        }
172    }
173
174    pub fn split_check(
175        &mut self,
176        bb_idx: usize,
177        fn_map: &mut MopFnAliasMap,
178        recursion_set: &mut HashSet<DefId>,
179    ) {
180        /* duplicate the status before visiting a path; */
181        let backup_values = self.values.clone(); // duplicate the status when visiting different paths;
182        let backup_constant = self.constants.clone();
183        let backup_alias_sets = self.alias_sets.clone();
184        self.check(bb_idx, fn_map, recursion_set);
185        /* restore after visit */
186        self.alias_sets = backup_alias_sets;
187        self.values = backup_values;
188        self.constants = backup_constant;
189    }
190    pub fn split_check_with_cond(
191        &mut self,
192        bb_idx: usize,
193        path_discr_id: usize,
194        path_discr_val: usize,
195        fn_map: &mut MopFnAliasMap,
196        recursion_set: &mut HashSet<DefId>,
197    ) {
198        /* duplicate the status before visiting a path; */
199        let backup_values = self.values.clone(); // duplicate the status when visiting different paths;
200        let backup_constant = self.constants.clone();
201        let backup_alias_sets = self.alias_sets.clone();
202        /* add control-sensitive indicator to the path status */
203        self.constants.insert(path_discr_id, path_discr_val);
204        self.check(bb_idx, fn_map, recursion_set);
205        /* restore after visit */
206        self.alias_sets = backup_alias_sets;
207        self.values = backup_values;
208        self.constants = backup_constant;
209    }
210
211    // the core function of the alias analysis algorithm.
212    pub fn check(
213        &mut self,
214        bb_idx: usize,
215        fn_map: &mut MopFnAliasMap,
216        recursion_set: &mut HashSet<DefId>,
217    ) {
218        let Some(_guard) = enter_depth_limit(&CHECK_DEPTH, CHECK_STACK_LIMIT) else {
219            // Prevent rustc stack overflow on extremely deep CFG / SCC exploration.
220            return;
221        };
222        self.visit_times += 1;
223        if self.visit_times > VISIT_LIMIT {
224            return;
225        }
226        let scc_idx = self.blocks[bb_idx].scc.enter;
227        let cur_block = self.blocks[bb_idx].clone();
228
229        rap_debug!("check {:?}", bb_idx);
230        if bb_idx == scc_idx && !cur_block.scc.nodes.is_empty() {
231            rap_debug!("check {:?} as a scc", bb_idx);
232            self.check_scc(bb_idx, fn_map, recursion_set);
233        } else {
234            self.check_single_node(bb_idx, fn_map, recursion_set);
235            self.handle_nexts(bb_idx, fn_map, None, recursion_set);
236        }
237    }
238
239    pub fn check_scc(
240        &mut self,
241        bb_idx: usize,
242        fn_map: &mut MopFnAliasMap,
243        recursion_set: &mut HashSet<DefId>,
244    ) {
245        let cur_block = self.blocks[bb_idx].clone();
246
247        /* Handle cases if the current block is a merged scc block with sub block */
248        rap_debug!("Searchng paths in scc: {:?}, {:?}", bb_idx, cur_block.scc);
249        let scc_tree = self.sort_scc_tree(&cur_block.scc);
250        rap_debug!("scc_tree: {:?}", scc_tree);
251        // Propagate constraints collected so far (top-down)
252        let inherited_constraints = self.constants.clone();
253        let paths_in_scc = self.find_scc_paths(bb_idx, &scc_tree, &inherited_constraints);
254        rap_debug!("Paths found in scc: {:?}", paths_in_scc);
255
256        let backup_values = self.values.clone(); // duplicate the status when visiteding different paths;
257        let backup_constant = self.constants.clone();
258        let backup_alias_sets = self.alias_sets.clone();
259        let backup_recursion_set = recursion_set.clone();
260
261        // SCC exits are stored on the SCC enter node.
262        let scc_exits = cur_block.scc.exits.clone();
263        for raw_path in paths_in_scc {
264            self.alias_sets = backup_alias_sets.clone();
265            self.values = backup_values.clone();
266            self.constants = backup_constant.clone();
267            *recursion_set = backup_recursion_set.clone();
268
269            let path = raw_path.0;
270            let path_constraints = &raw_path.1;
271            rap_debug!("checking path: {:?}", path);
272
273            // Apply alias transfer for every node in the path (including the exit node).
274            for idx in &path {
275                self.alias_bb(*idx);
276                self.alias_bbcall(*idx, fn_map, recursion_set);
277            }
278
279            // The path ends at an SCC-exit node (inside the SCC). We now leave the SCC only via
280            // recorded SCC exit edges from that node, carrying the collected path constraints.
281            if let Some(&exit_node) = path.last() {
282                self.constants.extend(path_constraints);
283                let mut followed = false;
284
285                // If exit_node is a SwitchInt, only follow SCC-exit edges consistent with the
286                // current constraint (important for enum parameters).
287                let mut allowed_targets: Option<FxHashSet<usize>> = None;
288                if let Term::Switch(sw) = self.blocks[exit_node].terminator.clone() {
289                    if let TerminatorKind::SwitchInt { discr, targets } = sw.kind {
290                        // Resolve discr local id in the same way as SCC path generation.
291                        let place = match discr {
292                            Copy(p) | Move(p) => Some(self.projection(p)),
293                            _ => None,
294                        };
295                        if let Some(place) = place {
296                            let discr_local = self
297                                .discriminants
298                                .get(&self.values[place].local)
299                                .cloned()
300                                .unwrap_or(place);
301
302                            let mut allowed = FxHashSet::default();
303                            if let Some(&c) = self.constants.get(&discr_local) {
304                                allowed.insert(self.switch_target_for_value(&targets, c));
305                            } else {
306                                // No constraint: allow all explicit targets + default.
307                                for (_, bb) in targets.iter() {
308                                    allowed.insert(bb.as_usize());
309                                }
310                                allowed.insert(targets.otherwise().as_usize());
311                            }
312                            allowed_targets = Some(allowed);
313                        }
314                    }
315                }
316
317                for e in &scc_exits {
318                    if e.exit != exit_node {
319                        continue;
320                    }
321                    if let Some(allowed) = &allowed_targets {
322                        if !allowed.contains(&e.to) {
323                            continue;
324                        }
325                    }
326                    followed = true;
327                    self.split_check(e.to, fn_map, recursion_set);
328                }
329
330                // If this SCC path ends at a node that is not recorded as an exit (should be rare),
331                // fall back to exploring its successors normally.
332                if !followed {
333                    self.handle_nexts(exit_node, fn_map, Some(path_constraints), recursion_set);
334                }
335            }
336        }
337    }
338
339    pub fn check_single_node(
340        &mut self,
341        bb_idx: usize,
342        fn_map: &mut MopFnAliasMap,
343        recursion_set: &mut HashSet<DefId>,
344    ) {
345        rap_debug!("check {:?} as a node", bb_idx);
346        let cur_block = self.blocks[bb_idx].clone();
347        self.alias_bb(self.blocks[bb_idx].scc.enter);
348        self.alias_bbcall(self.blocks[bb_idx].scc.enter, fn_map, recursion_set);
349        if cur_block.next.is_empty() {
350            self.merge_results();
351            return;
352        }
353    }
354
355    pub fn handle_nexts(
356        &mut self,
357        bb_idx: usize,
358        fn_map: &mut MopFnAliasMap,
359        path_constraints: Option<&FxHashMap<usize, usize>>,
360        recursion_set: &mut HashSet<DefId>,
361    ) {
362        let cur_block = self.blocks[bb_idx].clone();
363        let tcx = self.tcx;
364
365        rap_debug!(
366            "handle nexts {:?} of node {:?}",
367            self.blocks[bb_idx].next,
368            bb_idx
369        );
370        // Extra path contraints are introduced during scc handling.
371        if let Some(path_constraints) = path_constraints {
372            self.constants.extend(path_constraints);
373        }
374        /* Begin: handle the SwitchInt statement. */
375        let mut single_target = false;
376        let mut sw_val = 0;
377        let mut sw_target = 0; // Single target
378        let mut path_discr_id = 0; // To avoid analyzing paths that cannot be reached with one enum type.
379        let mut sw_targets = None; // Multiple targets of SwitchInt
380        let mut sw_otherwise_val: Option<usize> = None;
381
382        match cur_block.terminator {
383            Term::Switch(ref switch) => {
384                if let TerminatorKind::SwitchInt {
385                    ref discr,
386                    ref targets,
387                } = switch.kind
388                {
389                    sw_otherwise_val = self.unique_otherwise_switch_value(discr, targets);
390                    match discr {
391                        Copy(p) | Move(p) => {
392                            let value_idx = self.projection(*p);
393                            let local_decls = &tcx.optimized_mir(self.def_id).local_decls;
394                            let place_ty = (*p).ty(local_decls, tcx);
395                            rap_debug!("value_idx: {:?}", value_idx);
396                            match place_ty.ty.kind() {
397                                TyKind::Bool => {
398                                    if let Some(constant) = self.constants.get(&value_idx) {
399                                        if *constant != usize::MAX {
400                                            single_target = true;
401                                            sw_val = *constant;
402                                        }
403                                    }
404                                    path_discr_id = value_idx;
405                                    sw_targets = Some(targets.clone());
406                                }
407                                _ => {
408                                    if let Some(father) =
409                                        self.discriminants.get(&self.values[value_idx].local)
410                                    {
411                                        if let Some(constant) = self.constants.get(father) {
412                                            if *constant != usize::MAX {
413                                                single_target = true;
414                                                sw_val = *constant;
415                                            }
416                                        }
417                                        if self.values[value_idx].local == value_idx {
418                                            path_discr_id = *father;
419                                            sw_targets = Some(targets.clone());
420                                        }
421                                    }
422                                }
423                            }
424                        }
425                        Constant(c) => {
426                            single_target = true;
427                            let ty_env = TypingEnv::post_analysis(tcx, self.def_id);
428                            if let Some(val) = c.const_.try_eval_target_usize(tcx, ty_env) {
429                                sw_val = val as usize;
430                            }
431                        }
432                    }
433                    if single_target {
434                        rap_debug!("targets: {:?}; sw_val = {:?}", targets, sw_val);
435                        sw_target = self.switch_target_for_value(targets, sw_val);
436                    }
437                }
438            }
439            _ => {
440                // Not SwitchInt
441            }
442        }
443        /* End: finish handling SwitchInt */
444        // fixed path since a constant switchInt value
445        if single_target {
446            rap_debug!("visit a single target: {:?}", sw_target);
447            self.check(sw_target, fn_map, recursion_set);
448        } else {
449            // Other cases in switchInt terminators
450            if let Some(targets) = sw_targets {
451                if let Some(values) = self.possible_switch_values_for_constraint_id(path_discr_id) {
452                    // Enumerate each possible value explicitly (bool: 0/1, enum: 0..N).
453                    for path_discr_val in values {
454                        if self.visit_times > VISIT_LIMIT {
455                            continue;
456                        }
457                        let next = self.switch_target_for_value(&targets, path_discr_val);
458                        self.split_check_with_cond(
459                            next,
460                            path_discr_id,
461                            path_discr_val,
462                            fn_map,
463                            recursion_set,
464                        );
465                    }
466                } else {
467                    // Fallback: explore explicit branches + otherwise.
468                    for iter in targets.iter() {
469                        if self.visit_times > VISIT_LIMIT {
470                            continue;
471                        }
472                        let next = iter.1.as_usize();
473                        let path_discr_val = iter.0 as usize;
474                        self.split_check_with_cond(
475                            next,
476                            path_discr_id,
477                            path_discr_val,
478                            fn_map,
479                            recursion_set,
480                        );
481                    }
482                    let next_index = targets.otherwise().as_usize();
483                    // For bool/enum switches, the "otherwise" arm may represent a single concrete
484                    // value (e.g., an enum with 2 variants). Prefer a concrete value when unique.
485                    let path_discr_val = sw_otherwise_val.unwrap_or(usize::MAX); // default/otherwise path
486                    self.split_check_with_cond(
487                        next_index,
488                        path_discr_id,
489                        path_discr_val,
490                        fn_map,
491                        recursion_set,
492                    );
493                }
494            } else {
495                for next in cur_block.next {
496                    if self.visit_times > VISIT_LIMIT {
497                        continue;
498                    }
499                    self.split_check(next, fn_map, recursion_set);
500                }
501            }
502        }
503    }
504
505    pub fn sort_scc_tree(&mut self, scc: &SccInfo) -> SccTree {
506        // child_enter -> SccInfo
507        let mut child_sccs: FxHashMap<usize, SccInfo> = FxHashMap::default();
508
509        // find all sub sccs
510        for &node in scc.nodes.iter() {
511            let node_scc = &self.blocks[node].scc;
512            if node_scc.enter != scc.enter && !node_scc.nodes.is_empty() {
513                child_sccs
514                    .entry(node_scc.enter)
515                    .or_insert_with(|| node_scc.clone());
516            }
517        }
518
519        // recursively sort children
520        let children = child_sccs
521            .into_values()
522            .map(|child_scc| self.sort_scc_tree(&child_scc))
523            .collect();
524
525        SccTree {
526            scc: scc.clone(),
527            children,
528        }
529    }
530
531    pub fn find_scc_paths(
532        &mut self,
533        start: usize,
534        scc_tree: &SccTree,
535        initial_constraints: &FxHashMap<usize, usize>,
536    ) -> Vec<(Vec<usize>, FxHashMap<usize, usize>)> {
537        let key = SccPathCacheKey {
538            def_id: self.def_id,
539            scc_enter: scc_tree.scc.enter,
540            constraints: constraints_key(initial_constraints),
541        };
542
543        if let Some(cached) = SCC_PATH_CACHE.with(|c| c.borrow().get(&key).cloned()) {
544            return cached;
545        }
546
547        let mut all_paths = Vec::new();
548        let mut seen_paths: FxHashSet<PathKey> = FxHashSet::default();
549
550        // DFS stack path
551        let mut path = vec![start];
552
553        // Track nodes on the current *segment* recursion stack (since the last dominator entry).
554        // This prevents non-dominator cycles inside a segment, but allows revisiting nodes across
555        // multiple segments separated by returning to the dominator.
556        let mut segment_stack = FxHashSet::default();
557        segment_stack.insert(start);
558
559        // Track nodes visited since entering the dominator on this path.
560        let mut visited_since_enter = FxHashSet::default();
561        visited_since_enter.insert(start);
562
563        // Snapshot of visited nodes at the *start* of the current cycle segment (at dominator).
564        // Used to decide whether a new cycle (return-to-dominator) introduced new nodes.
565        let baseline_at_dominator = visited_since_enter.clone();
566
567        self.find_scc_paths_inner(
568            start,
569            start,
570            scc_tree,
571            &mut path,
572            initial_constraints.clone(),
573            segment_stack,
574            visited_since_enter,
575            baseline_at_dominator,
576            None,
577            &mut all_paths,
578            &mut seen_paths,
579        );
580
581        // Paths are deduplicated incrementally via `seen_paths`.
582
583        SCC_PATH_CACHE.with(|c| {
584            let mut cache = c.borrow_mut();
585            if cache.len() >= SCC_PATH_CACHE_LIMIT {
586                cache.clear();
587            }
588            cache.insert(key, all_paths.clone());
589        });
590
591        all_paths
592    }
593
594    fn find_scc_paths_inner(
595        &mut self,
596        start: usize,
597        cur: usize,
598        scc_tree: &SccTree,
599        path: &mut Vec<usize>,
600        mut path_constraints: FxHashMap<usize, usize>,
601        mut segment_stack: FxHashSet<usize>,
602        visited_since_enter: FxHashSet<usize>,
603        baseline_at_dominator: FxHashSet<usize>,
604        skip_child_enter: Option<usize>,
605        paths_in_scc: &mut Vec<(Vec<usize>, FxHashMap<usize, usize>)>,
606        seen_paths: &mut FxHashSet<PathKey>,
607    ) {
608        let Some(_guard) = enter_depth_limit(&SCC_DFS_DEPTH, SCC_DFS_STACK_LIMIT) else {
609            return;
610        };
611        let scc = &scc_tree.scc;
612        if scc.nodes.is_empty() {
613            let key = PathKey {
614                path: path.clone(),
615                constraints: constraints_key(&path_constraints),
616            };
617            if seen_paths.insert(key) {
618                paths_in_scc.push((path.clone(), path_constraints));
619            }
620            return;
621        }
622
623        // Temporary complexity control to avoid path explosion.
624        // Use unique-path count to avoid biased truncation from duplicates.
625        if path.len() > 200 || seen_paths.len() > 4000 {
626            return;
627        }
628
629        // We do not traverse outside the SCC when generating SCC internal paths.
630        // Instead, we record paths that end at SCC-exit nodes (nodes with an outgoing edge leaving
631        // the SCC), and the caller is responsible for resuming traversal outside the SCC.
632        let cur_in_scc = cur == start || scc.nodes.contains(&cur);
633        if !cur_in_scc {
634            return;
635        }
636
637        // Incremental cycle validity check:
638        // When we return to the dominator (start), we keep the cycle only if the *most recent*
639        // segment between two occurrences of the dominator introduced at least one node that
640        // was not visited at the beginning of that segment.
641        let mut baseline_at_dominator = baseline_at_dominator;
642        let visited_since_enter = visited_since_enter;
643
644        if cur == start {
645            if path.len() > 1 {
646                // Find previous occurrence of `start` before the trailing `start`.
647                let prev_start_pos = path[..path.len() - 1]
648                    .iter()
649                    .rposition(|&node| node == start)
650                    .unwrap_or(0);
651                // Nodes in the cycle segment exclude both dominator endpoints.
652                let cycle_nodes = &path[prev_start_pos + 1..path.len() - 1];
653                let introduces_new = cycle_nodes
654                    .iter()
655                    .any(|node| !baseline_at_dominator.contains(node));
656                if !introduces_new {
657                    return;
658                }
659            }
660            // We are at a dominator boundary: reset baseline for the next segment.
661            baseline_at_dominator = visited_since_enter.clone();
662
663            // IMPORTANT: reset segment recursion stack at the dominator.
664            // After completing a cycle back to the dominator, the next segment is allowed to
665            // traverse previously seen nodes again; only the incremental-cycle check above
666            // controls whether such repetition is useful.
667            segment_stack.clear();
668            segment_stack.insert(start);
669        }
670
671        // Clear the constriants if the local is reassigned in the current block;
672        // Otherwise, it cannot reach other branches.
673        for local in &self.blocks[cur].assigned_locals {
674            rap_debug!(
675                "Remove path_constraints {:?}, because it has been reassigned.",
676                local
677            );
678            path_constraints.remove(&local);
679        }
680
681        // Find the pathes of inner scc recursively;
682        for child_tree in &scc_tree.children {
683            let child_enter = child_tree.scc.enter;
684            if cur == child_enter {
685                // When a spliced child-SCC path ends back at the child-enter, we must continue
686                // exploring the *parent* SCC without immediately re-expanding the same child SCC
687                // again (otherwise we can loop until the depth guard triggers and drop paths).
688                if skip_child_enter == Some(child_enter) {
689                    break;
690                }
691
692                let sub_paths = self.find_scc_paths(child_enter, child_tree, &path_constraints);
693                rap_debug!("paths in sub scc: {}, {:?}", child_enter, sub_paths);
694
695                // Always allow the parent SCC to proceed from `child_enter` without traversing
696                // into the child SCC (conceptually, an empty child path). This is necessary when
697                // the child enumeration is truncated/empty and also to allow parent exits at
698                // `child_enter` (e.g., an edge to a sink `Unreachable` block) to be recorded.
699                {
700                    let mut nop_path = path.clone();
701                    self.find_scc_paths_inner(
702                        start,
703                        child_enter,
704                        scc_tree,
705                        &mut nop_path,
706                        path_constraints.clone(),
707                        segment_stack.clone(),
708                        visited_since_enter.clone(),
709                        baseline_at_dominator.clone(),
710                        Some(child_enter),
711                        paths_in_scc,
712                        seen_paths,
713                    );
714                }
715
716                for (subp, subconst) in sub_paths {
717                    // A single-node sub-path ([child_enter]) makes no progress and would only
718                    // re-trigger child expansion; the no-op continuation above already covers it.
719                    if subp.len() <= 1 {
720                        continue;
721                    }
722
723                    let mut new_path = path.clone();
724                    new_path.extend(&subp[1..]);
725                    // `subconst` already starts from `path_constraints` and accumulates changes.
726                    // Use it as the current constraints after splicing.
727                    let new_const = subconst;
728
729                    // Update visited set based on spliced nodes.
730                    let mut new_visited = visited_since_enter.clone();
731                    for node in &new_path {
732                        new_visited.insert(*node);
733                    }
734
735                    // Rebuild segment stack from the suffix of the path after the most recent
736                    // dominator occurrence.
737                    let last_start_pos = new_path
738                        .iter()
739                        .rposition(|&node| node == start)
740                        .unwrap_or(0);
741                    let mut new_segment_stack = FxHashSet::default();
742                    for node in &new_path[last_start_pos..] {
743                        new_segment_stack.insert(*node);
744                    }
745
746                    let new_cur = *new_path.last().unwrap();
747                    let next_skip_child_enter = if new_cur == child_enter {
748                        Some(child_enter)
749                    } else {
750                        None
751                    };
752
753                    self.find_scc_paths_inner(
754                        start,
755                        new_cur,
756                        scc_tree,
757                        &mut new_path,
758                        new_const,
759                        new_segment_stack,
760                        new_visited,
761                        baseline_at_dominator.clone(),
762                        next_skip_child_enter,
763                        paths_in_scc,
764                        seen_paths,
765                    );
766                }
767                return;
768            }
769        }
770
771        let term = self.terminators[cur].clone();
772        rap_debug!("term: {:?}", term);
773
774        // Clear constraints when their discriminant locals are redefined by terminators.
775        // NOTE: `assigned_locals` is populated only from `StatementKind::Assign`, and does not
776        // include locals assigned by terminators (e.g., `_11 = random()` in MIR is a `Call`).
777        // If we don't clear these, stale constraints can incorrectly prune SwitchInt branches and
778        // also amplify path explosion via inconsistent constraint propagation across iterations.
779        if let TerminatorKind::Call { destination, .. } = &term {
780            let dest_idx = self.projection(*destination);
781            let dest_local = self
782                .discriminants
783                .get(&self.values[dest_idx].local)
784                .cloned()
785                .unwrap_or(dest_idx);
786            path_constraints.remove(&dest_local);
787        }
788
789        match term {
790            TerminatorKind::SwitchInt { discr, targets } => {
791                let otherwise_val = self.unique_otherwise_switch_value(&discr, &targets);
792                // Resolve discr local id for constraint propagation
793                let place = match discr {
794                    Copy(p) | Move(p) => Some(self.projection(p)),
795                    _ => None,
796                };
797
798                let Some(place) = place else {
799                    return;
800                };
801
802                let discr_local = self
803                    .discriminants
804                    .get(&self.values[place].local)
805                    .cloned()
806                    .unwrap_or(place);
807
808                let possible_values = self.possible_switch_values_for_constraint_id(discr_local);
809
810                if let Some(&constant) = path_constraints.get(&discr_local) {
811                    // Existing constraint: only explore the feasible branch.
812                    if constant == usize::MAX {
813                        let next = targets.otherwise().as_usize();
814                        let next_in_scc = next == start || scc.nodes.contains(&next);
815                        if !next_in_scc {
816                            // Exits the SCC via the default branch.
817                            self.record_scc_exit_path(
818                                scc,
819                                cur,
820                                &path_constraints,
821                                path,
822                                paths_in_scc,
823                                seen_paths,
824                            );
825                            return;
826                        }
827                        if !segment_stack.contains(&next) || next == start {
828                            let mut new_path = path.clone();
829                            new_path.push(next);
830                            let mut new_segment_stack = segment_stack.clone();
831                            new_segment_stack.insert(next);
832                            let mut new_visited = visited_since_enter.clone();
833                            new_visited.insert(next);
834                            self.find_scc_paths_inner(
835                                start,
836                                next,
837                                scc_tree,
838                                &mut new_path,
839                                path_constraints,
840                                new_segment_stack,
841                                new_visited,
842                                baseline_at_dominator,
843                                None,
844                                paths_in_scc,
845                                seen_paths,
846                            );
847                        }
848                    } else {
849                        let mut found = false;
850                        for branch in targets.iter() {
851                            if branch.0 as usize != constant {
852                                continue;
853                            }
854                            found = true;
855                            let next = branch.1.as_usize();
856                            let next_in_scc = next == start || scc.nodes.contains(&next);
857                            if !next_in_scc {
858                                // Exits the SCC via this constrained branch.
859                                self.record_scc_exit_path(
860                                    scc,
861                                    cur,
862                                    &path_constraints,
863                                    path,
864                                    paths_in_scc,
865                                    seen_paths,
866                                );
867                                continue;
868                            }
869                            if segment_stack.contains(&next) && next != start {
870                                continue;
871                            }
872                            let mut new_path = path.clone();
873                            new_path.push(next);
874                            let mut new_segment_stack = segment_stack.clone();
875                            new_segment_stack.insert(next);
876                            let mut new_visited = visited_since_enter.clone();
877                            new_visited.insert(next);
878                            self.find_scc_paths_inner(
879                                start,
880                                next,
881                                scc_tree,
882                                &mut new_path,
883                                path_constraints.clone(),
884                                new_segment_stack,
885                                new_visited,
886                                baseline_at_dominator.clone(),
887                                None,
888                                paths_in_scc,
889                                seen_paths,
890                            );
891                        }
892                        if !found {
893                            let next = targets.otherwise().as_usize();
894                            let next_in_scc = next == start || scc.nodes.contains(&next);
895                            if !next_in_scc {
896                                // Exits the SCC via the default branch.
897                                self.record_scc_exit_path(
898                                    scc,
899                                    cur,
900                                    &path_constraints,
901                                    path,
902                                    paths_in_scc,
903                                    seen_paths,
904                                );
905                                return;
906                            }
907                            if !segment_stack.contains(&next) || next == start {
908                                let mut new_path = path.clone();
909                                new_path.push(next);
910                                let mut new_segment_stack = segment_stack.clone();
911                                new_segment_stack.insert(next);
912                                let mut new_visited = visited_since_enter.clone();
913                                new_visited.insert(next);
914                                self.find_scc_paths_inner(
915                                    start,
916                                    next,
917                                    scc_tree,
918                                    &mut new_path,
919                                    path_constraints,
920                                    new_segment_stack,
921                                    new_visited,
922                                    baseline_at_dominator,
923                                    None,
924                                    paths_in_scc,
925                                    seen_paths,
926                                );
927                            }
928                        }
929                    }
930                } else {
931                    // No constraint yet: if this is a bool/enum discriminant, enumerate every
932                    // possible value explicitly (not just "iter + otherwise").
933                    if let Some(values) = possible_values {
934                        for constant in values {
935                            let next = self.switch_target_for_value(&targets, constant);
936
937                            let next_in_scc = next == start || scc.nodes.contains(&next);
938                            let mut new_constraints = path_constraints.clone();
939                            new_constraints.insert(discr_local, constant);
940
941                            if !next_in_scc {
942                                self.record_scc_exit_path(
943                                    scc,
944                                    cur,
945                                    &new_constraints,
946                                    path,
947                                    paths_in_scc,
948                                    seen_paths,
949                                );
950                                continue;
951                            }
952                            if segment_stack.contains(&next) && next != start {
953                                continue;
954                            }
955
956                            let mut new_path = path.clone();
957                            new_path.push(next);
958
959                            let mut new_segment_stack = segment_stack.clone();
960                            new_segment_stack.insert(next);
961
962                            let mut new_visited = visited_since_enter.clone();
963                            new_visited.insert(next);
964
965                            self.find_scc_paths_inner(
966                                start,
967                                next,
968                                scc_tree,
969                                &mut new_path,
970                                new_constraints,
971                                new_segment_stack,
972                                new_visited,
973                                baseline_at_dominator.clone(),
974                                None,
975                                paths_in_scc,
976                                seen_paths,
977                            );
978                        }
979                    } else {
980                        // Fallback: explore explicit branches + otherwise.
981                        for branch in targets.iter() {
982                            let constant = branch.0 as usize;
983                            let next = branch.1.as_usize();
984                            let next_in_scc = next == start || scc.nodes.contains(&next);
985                            let mut new_constraints = path_constraints.clone();
986                            new_constraints.insert(discr_local, constant);
987
988                            if !next_in_scc {
989                                self.record_scc_exit_path(
990                                    scc,
991                                    cur,
992                                    &new_constraints,
993                                    path,
994                                    paths_in_scc,
995                                    seen_paths,
996                                );
997                                continue;
998                            }
999                            if segment_stack.contains(&next) && next != start {
1000                                continue;
1001                            }
1002                            let mut new_path = path.clone();
1003                            new_path.push(next);
1004
1005                            let mut new_segment_stack = segment_stack.clone();
1006                            new_segment_stack.insert(next);
1007
1008                            let mut new_visited = visited_since_enter.clone();
1009                            new_visited.insert(next);
1010
1011                            self.find_scc_paths_inner(
1012                                start,
1013                                next,
1014                                scc_tree,
1015                                &mut new_path,
1016                                new_constraints,
1017                                new_segment_stack,
1018                                new_visited,
1019                                baseline_at_dominator.clone(),
1020                                None,
1021                                paths_in_scc,
1022                                seen_paths,
1023                            );
1024                        }
1025
1026                        let next = targets.otherwise().as_usize();
1027                        let next_in_scc = next == start || scc.nodes.contains(&next);
1028                        let mut new_constraints = path_constraints;
1029                        new_constraints.insert(discr_local, otherwise_val.unwrap_or(usize::MAX));
1030
1031                        if !next_in_scc {
1032                            self.record_scc_exit_path(
1033                                scc,
1034                                cur,
1035                                &new_constraints,
1036                                path,
1037                                paths_in_scc,
1038                                seen_paths,
1039                            );
1040                            return;
1041                        }
1042                        if !segment_stack.contains(&next) || next == start {
1043                            let mut new_path = path.clone();
1044                            new_path.push(next);
1045
1046                            let mut new_segment_stack = segment_stack.clone();
1047                            new_segment_stack.insert(next);
1048
1049                            let mut new_visited = visited_since_enter.clone();
1050                            new_visited.insert(next);
1051
1052                            self.find_scc_paths_inner(
1053                                start,
1054                                next,
1055                                scc_tree,
1056                                &mut new_path,
1057                                new_constraints,
1058                                new_segment_stack,
1059                                new_visited,
1060                                baseline_at_dominator,
1061                                None,
1062                                paths_in_scc,
1063                                seen_paths,
1064                            );
1065                        }
1066                    }
1067                }
1068            }
1069            _ => {
1070                // For non-SwitchInt terminators, reaching an SCC-exit node is enough to record a
1071                // usable path segment. Successors leaving the SCC are not traversed here.
1072                self.record_scc_exit_path(
1073                    scc,
1074                    cur,
1075                    &path_constraints,
1076                    path,
1077                    paths_in_scc,
1078                    seen_paths,
1079                );
1080                for next in self.blocks[cur].next.clone() {
1081                    let next_in_scc = next == start || scc.nodes.contains(&next);
1082                    if !next_in_scc {
1083                        continue;
1084                    }
1085                    if segment_stack.contains(&next) && next != start {
1086                        continue;
1087                    }
1088                    let mut new_path = path.clone();
1089                    new_path.push(next);
1090
1091                    let mut new_segment_stack = segment_stack.clone();
1092                    new_segment_stack.insert(next);
1093
1094                    let mut new_visited = visited_since_enter.clone();
1095                    new_visited.insert(next);
1096
1097                    self.find_scc_paths_inner(
1098                        start,
1099                        next,
1100                        scc_tree,
1101                        &mut new_path,
1102                        path_constraints.clone(),
1103                        new_segment_stack,
1104                        new_visited,
1105                        baseline_at_dominator.clone(),
1106                        None,
1107                        paths_in_scc,
1108                        seen_paths,
1109                    );
1110                }
1111            }
1112        }
1113    }
1114}
rapx/analysis/core/alias_analysis/default/mop.rs

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