rustc_mir_dataflow/
value_analysis.rs

1use std::fmt::{Debug, Formatter};
2use std::ops::Range;
3
4use rustc_abi::{FieldIdx, VariantIdx};
5use rustc_data_structures::fx::{FxHashMap, FxIndexSet, StdEntry};
6use rustc_data_structures::stack::ensure_sufficient_stack;
7use rustc_index::IndexVec;
8use rustc_index::bit_set::DenseBitSet;
9use rustc_middle::mir::visit::{MutatingUseContext, PlaceContext, Visitor};
10use rustc_middle::mir::*;
11use rustc_middle::ty::{self, Ty, TyCtxt};
12use tracing::debug;
13
14use crate::JoinSemiLattice;
15use crate::lattice::{HasBottom, HasTop};
16
17rustc_index::newtype_index!(
18    /// This index uniquely identifies a place.
19    ///
20    /// Not every place has a `PlaceIndex`, and not every `PlaceIndex` corresponds to a tracked
21    /// place. However, every tracked place and all places along its projection have a `PlaceIndex`.
22    pub struct PlaceIndex {}
23);
24
25rustc_index::newtype_index!(
26    /// This index uniquely identifies a tracked place and therefore a slot in [`State`].
27    ///
28    /// It is an implementation detail of this module.
29    struct ValueIndex {}
30);
31
32/// See [`State`].
33#[derive(PartialEq, Eq, Debug)]
34pub struct StateData<V> {
35    bottom: V,
36    /// This map only contains values that are not `⊥`.
37    map: FxHashMap<ValueIndex, V>,
38}
39
40impl<V: HasBottom> StateData<V> {
41    fn new() -> StateData<V> {
42        StateData { bottom: V::BOTTOM, map: FxHashMap::default() }
43    }
44
45    fn get(&self, idx: ValueIndex) -> &V {
46        self.map.get(&idx).unwrap_or(&self.bottom)
47    }
48
49    fn insert(&mut self, idx: ValueIndex, elem: V) {
50        if elem.is_bottom() {
51            self.map.remove(&idx);
52        } else {
53            self.map.insert(idx, elem);
54        }
55    }
56}
57
58impl<V: Clone> Clone for StateData<V> {
59    fn clone(&self) -> Self {
60        StateData { bottom: self.bottom.clone(), map: self.map.clone() }
61    }
62
63    fn clone_from(&mut self, source: &Self) {
64        self.map.clone_from(&source.map)
65    }
66}
67
68impl<V: JoinSemiLattice + Clone> JoinSemiLattice for StateData<V> {
69    fn join(&mut self, other: &Self) -> bool {
70        let mut changed = false;
71        #[allow(rustc::potential_query_instability)]
72        for (i, v) in other.map.iter() {
73            match self.map.entry(*i) {
74                StdEntry::Vacant(e) => {
75                    e.insert(v.clone());
76                    changed = true
77                }
78                StdEntry::Occupied(e) => changed |= e.into_mut().join(v),
79            }
80        }
81        changed
82    }
83}
84
85/// Dataflow state.
86///
87/// Every instance specifies a lattice that represents the possible values of a single tracked
88/// place. If we call this lattice `V` and set of tracked places `P`, then a [`State`] is an
89/// element of `{unreachable} ∪ (P -> V)`. This again forms a lattice, where the bottom element is
90/// `unreachable` and the top element is the mapping `p ↦ ⊤`. Note that the mapping `p ↦ ⊥` is not
91/// the bottom element (because joining an unreachable and any other reachable state yields a
92/// reachable state). All operations on unreachable states are ignored.
93///
94/// Flooding means assigning a value (by default `⊤`) to all tracked projections of a given place.
95#[derive(PartialEq, Eq, Debug)]
96pub enum State<V> {
97    Unreachable,
98    Reachable(StateData<V>),
99}
100
101impl<V: Clone> Clone for State<V> {
102    fn clone(&self) -> Self {
103        match self {
104            Self::Reachable(x) => Self::Reachable(x.clone()),
105            Self::Unreachable => Self::Unreachable,
106        }
107    }
108
109    fn clone_from(&mut self, source: &Self) {
110        match (&mut *self, source) {
111            (Self::Reachable(x), Self::Reachable(y)) => {
112                x.clone_from(&y);
113            }
114            _ => *self = source.clone(),
115        }
116    }
117}
118
119impl<V: Clone + HasBottom> State<V> {
120    pub fn new_reachable() -> State<V> {
121        State::Reachable(StateData::new())
122    }
123
124    pub fn all_bottom(&self) -> bool {
125        match self {
126            State::Unreachable => false,
127            State::Reachable(values) =>
128            {
129                #[allow(rustc::potential_query_instability)]
130                values.map.values().all(V::is_bottom)
131            }
132        }
133    }
134
135    pub fn is_reachable(&self) -> bool {
136        matches!(self, State::Reachable(_))
137    }
138
139    /// Assign `value` to all places that are contained in `place` or may alias one.
140    pub fn flood_with(&mut self, place: PlaceRef<'_>, map: &Map<'_>, value: V) {
141        self.flood_with_tail_elem(place, None, map, value)
142    }
143
144    /// Assign `TOP` to all places that are contained in `place` or may alias one.
145    pub fn flood(&mut self, place: PlaceRef<'_>, map: &Map<'_>)
146    where
147        V: HasTop,
148    {
149        self.flood_with(place, map, V::TOP)
150    }
151
152    /// Assign `value` to the discriminant of `place` and all places that may alias it.
153    fn flood_discr_with(&mut self, place: PlaceRef<'_>, map: &Map<'_>, value: V) {
154        self.flood_with_tail_elem(place, Some(TrackElem::Discriminant), map, value)
155    }
156
157    /// Assign `TOP` to the discriminant of `place` and all places that may alias it.
158    pub fn flood_discr(&mut self, place: PlaceRef<'_>, map: &Map<'_>)
159    where
160        V: HasTop,
161    {
162        self.flood_discr_with(place, map, V::TOP)
163    }
164
165    /// This method is the most general version of the `flood_*` method.
166    ///
167    /// Assign `value` on the given place and all places that may alias it. In particular, when
168    /// the given place has a variant downcast, we invoke the function on all the other variants.
169    ///
170    /// `tail_elem` allows to support discriminants that are not a place in MIR, but that we track
171    /// as such.
172    pub fn flood_with_tail_elem(
173        &mut self,
174        place: PlaceRef<'_>,
175        tail_elem: Option<TrackElem>,
176        map: &Map<'_>,
177        value: V,
178    ) {
179        let State::Reachable(values) = self else { return };
180        map.for_each_aliasing_place(place, tail_elem, &mut |vi| values.insert(vi, value.clone()));
181    }
182
183    /// Low-level method that assigns to a place.
184    /// This does nothing if the place is not tracked.
185    ///
186    /// The target place must have been flooded before calling this method.
187    fn insert_idx(&mut self, target: PlaceIndex, result: ValueOrPlace<V>, map: &Map<'_>) {
188        match result {
189            ValueOrPlace::Value(value) => self.insert_value_idx(target, value, map),
190            ValueOrPlace::Place(source) => self.insert_place_idx(target, source, map),
191        }
192    }
193
194    /// Low-level method that assigns a value to a place.
195    /// This does nothing if the place is not tracked.
196    ///
197    /// The target place must have been flooded before calling this method.
198    pub fn insert_value_idx(&mut self, target: PlaceIndex, value: V, map: &Map<'_>) {
199        let State::Reachable(values) = self else { return };
200        if let Some(value_index) = map.places[target].value_index {
201            values.insert(value_index, value)
202        }
203    }
204
205    /// Copies `source` to `target`, including all tracked places beneath.
206    ///
207    /// If `target` contains a place that is not contained in `source`, it will be overwritten with
208    /// Top. Also, because this will copy all entries one after another, it may only be used for
209    /// places that are non-overlapping or identical.
210    ///
211    /// The target place must have been flooded before calling this method.
212    pub fn insert_place_idx(&mut self, target: PlaceIndex, source: PlaceIndex, map: &Map<'_>) {
213        let State::Reachable(values) = self else { return };
214
215        // If both places are tracked, we copy the value to the target.
216        // If the target is tracked, but the source is not, we do nothing, as invalidation has
217        // already been performed.
218        if let Some(target_value) = map.places[target].value_index {
219            if let Some(source_value) = map.places[source].value_index {
220                values.insert(target_value, values.get(source_value).clone());
221            }
222        }
223        for target_child in map.children(target) {
224            // Try to find corresponding child and recurse. Reasoning is similar as above.
225            let projection = map.places[target_child].proj_elem.unwrap();
226            if let Some(source_child) = map.projections.get(&(source, projection)) {
227                self.insert_place_idx(target_child, *source_child, map);
228            }
229        }
230    }
231
232    /// Helper method to interpret `target = result`.
233    pub fn assign(&mut self, target: PlaceRef<'_>, result: ValueOrPlace<V>, map: &Map<'_>)
234    where
235        V: HasTop,
236    {
237        self.flood(target, map);
238        if let Some(target) = map.find(target) {
239            self.insert_idx(target, result, map);
240        }
241    }
242
243    /// Helper method for assignments to a discriminant.
244    pub fn assign_discr(&mut self, target: PlaceRef<'_>, result: ValueOrPlace<V>, map: &Map<'_>)
245    where
246        V: HasTop,
247    {
248        self.flood_discr(target, map);
249        if let Some(target) = map.find_discr(target) {
250            self.insert_idx(target, result, map);
251        }
252    }
253
254    /// Retrieve the value stored for a place, or `None` if it is not tracked.
255    pub fn try_get(&self, place: PlaceRef<'_>, map: &Map<'_>) -> Option<V> {
256        let place = map.find(place)?;
257        self.try_get_idx(place, map)
258    }
259
260    /// Retrieve the discriminant stored for a place, or `None` if it is not tracked.
261    pub fn try_get_discr(&self, place: PlaceRef<'_>, map: &Map<'_>) -> Option<V> {
262        let place = map.find_discr(place)?;
263        self.try_get_idx(place, map)
264    }
265
266    /// Retrieve the slice length stored for a place, or `None` if it is not tracked.
267    pub fn try_get_len(&self, place: PlaceRef<'_>, map: &Map<'_>) -> Option<V> {
268        let place = map.find_len(place)?;
269        self.try_get_idx(place, map)
270    }
271
272    /// Retrieve the value stored for a place index, or `None` if it is not tracked.
273    pub fn try_get_idx(&self, place: PlaceIndex, map: &Map<'_>) -> Option<V> {
274        match self {
275            State::Reachable(values) => {
276                map.places[place].value_index.map(|v| values.get(v).clone())
277            }
278            State::Unreachable => None,
279        }
280    }
281
282    /// Retrieve the value stored for a place, or ⊤ if it is not tracked.
283    ///
284    /// This method returns ⊥ if the place is tracked and the state is unreachable.
285    pub fn get(&self, place: PlaceRef<'_>, map: &Map<'_>) -> V
286    where
287        V: HasBottom + HasTop,
288    {
289        match self {
290            State::Reachable(_) => self.try_get(place, map).unwrap_or(V::TOP),
291            // Because this is unreachable, we can return any value we want.
292            State::Unreachable => V::BOTTOM,
293        }
294    }
295
296    /// Retrieve the value stored for a place, or ⊤ if it is not tracked.
297    ///
298    /// This method returns ⊥ the current state is unreachable.
299    pub fn get_discr(&self, place: PlaceRef<'_>, map: &Map<'_>) -> V
300    where
301        V: HasBottom + HasTop,
302    {
303        match self {
304            State::Reachable(_) => self.try_get_discr(place, map).unwrap_or(V::TOP),
305            // Because this is unreachable, we can return any value we want.
306            State::Unreachable => V::BOTTOM,
307        }
308    }
309
310    /// Retrieve the value stored for a place, or ⊤ if it is not tracked.
311    ///
312    /// This method returns ⊥ the current state is unreachable.
313    pub fn get_len(&self, place: PlaceRef<'_>, map: &Map<'_>) -> V
314    where
315        V: HasBottom + HasTop,
316    {
317        match self {
318            State::Reachable(_) => self.try_get_len(place, map).unwrap_or(V::TOP),
319            // Because this is unreachable, we can return any value we want.
320            State::Unreachable => V::BOTTOM,
321        }
322    }
323
324    /// Retrieve the value stored for a place index, or ⊤ if it is not tracked.
325    ///
326    /// This method returns ⊥ the current state is unreachable.
327    pub fn get_idx(&self, place: PlaceIndex, map: &Map<'_>) -> V
328    where
329        V: HasBottom + HasTop,
330    {
331        match self {
332            State::Reachable(values) => {
333                map.places[place].value_index.map(|v| values.get(v).clone()).unwrap_or(V::TOP)
334            }
335            State::Unreachable => {
336                // Because this is unreachable, we can return any value we want.
337                V::BOTTOM
338            }
339        }
340    }
341}
342
343impl<V: JoinSemiLattice + Clone> JoinSemiLattice for State<V> {
344    fn join(&mut self, other: &Self) -> bool {
345        match (&mut *self, other) {
346            (_, State::Unreachable) => false,
347            (State::Unreachable, _) => {
348                *self = other.clone();
349                true
350            }
351            (State::Reachable(this), State::Reachable(other)) => this.join(other),
352        }
353    }
354}
355
356/// Partial mapping from [`Place`] to [`PlaceIndex`], where some places also have a [`ValueIndex`].
357///
358/// This data structure essentially maintains a tree of places and their projections. Some
359/// additional bookkeeping is done, to speed up traversal over this tree:
360/// - For iteration, every [`PlaceInfo`] contains an intrusive linked list of its children.
361/// - To directly get the child for a specific projection, there is a `projections` map.
362#[derive(Debug)]
363pub struct Map<'tcx> {
364    locals: IndexVec<Local, Option<PlaceIndex>>,
365    projections: FxHashMap<(PlaceIndex, TrackElem), PlaceIndex>,
366    places: IndexVec<PlaceIndex, PlaceInfo<'tcx>>,
367    value_count: usize,
368    // The Range corresponds to a slice into `inner_values_buffer`.
369    inner_values: IndexVec<PlaceIndex, Range<usize>>,
370    inner_values_buffer: Vec<ValueIndex>,
371}
372
373impl<'tcx> Map<'tcx> {
374    /// Returns a map that only tracks places whose type has scalar layout.
375    ///
376    /// This is currently the only way to create a [`Map`]. The way in which the tracked places are
377    /// chosen is an implementation detail and may not be relied upon (other than that their type
378    /// are scalars).
379    pub fn new(tcx: TyCtxt<'tcx>, body: &Body<'tcx>, value_limit: Option<usize>) -> Self {
380        let mut map = Self {
381            locals: IndexVec::from_elem(None, &body.local_decls),
382            projections: FxHashMap::default(),
383            places: IndexVec::new(),
384            value_count: 0,
385            inner_values: IndexVec::new(),
386            inner_values_buffer: Vec::new(),
387        };
388        let exclude = excluded_locals(body);
389        map.register(tcx, body, exclude, value_limit);
390        debug!("registered {} places ({} nodes in total)", map.value_count, map.places.len());
391        map
392    }
393
394    /// Register all non-excluded places that have scalar layout.
395    #[tracing::instrument(level = "trace", skip(self, tcx, body))]
396    fn register(
397        &mut self,
398        tcx: TyCtxt<'tcx>,
399        body: &Body<'tcx>,
400        exclude: DenseBitSet<Local>,
401        value_limit: Option<usize>,
402    ) {
403        // Start by constructing the places for each bare local.
404        for (local, decl) in body.local_decls.iter_enumerated() {
405            if exclude.contains(local) {
406                continue;
407            }
408            if decl.ty.is_async_drop_in_place_coroutine(tcx) {
409                continue;
410            }
411
412            // Create a place for the local.
413            debug_assert!(self.locals[local].is_none());
414            let place = self.places.push(PlaceInfo::new(decl.ty, None));
415            self.locals[local] = Some(place);
416        }
417
418        // Collect syntactic places and assignments between them.
419        let mut collector =
420            PlaceCollector { tcx, body, map: self, assignments: Default::default() };
421        collector.visit_body(body);
422        let PlaceCollector { mut assignments, .. } = collector;
423
424        // Just collecting syntactic places is not enough. We may need to propagate this pattern:
425        //      _1 = (const 5u32, const 13i64);
426        //      _2 = _1;
427        //      _3 = (_2.0 as u32);
428        //
429        // `_1.0` does not appear, but we still need to track it. This is achieved by propagating
430        // projections from assignments. We recorded an assignment between `_2` and `_1`, so we
431        // want `_1` and `_2` to have the same sub-places.
432        //
433        // This is what this fixpoint loop does. While we are still creating places, run through
434        // all the assignments, and register places for children.
435        let mut num_places = 0;
436        while num_places < self.places.len() {
437            num_places = self.places.len();
438
439            for assign in 0.. {
440                let Some(&(lhs, rhs)) = assignments.get_index(assign) else { break };
441
442                // Mirror children from `lhs` in `rhs`.
443                let mut child = self.places[lhs].first_child;
444                while let Some(lhs_child) = child {
445                    let PlaceInfo { ty, proj_elem, next_sibling, .. } = self.places[lhs_child];
446                    let rhs_child =
447                        self.register_place(ty, rhs, proj_elem.expect("child is not a projection"));
448                    assignments.insert((lhs_child, rhs_child));
449                    child = next_sibling;
450                }
451
452                // Conversely, mirror children from `rhs` in `lhs`.
453                let mut child = self.places[rhs].first_child;
454                while let Some(rhs_child) = child {
455                    let PlaceInfo { ty, proj_elem, next_sibling, .. } = self.places[rhs_child];
456                    let lhs_child =
457                        self.register_place(ty, lhs, proj_elem.expect("child is not a projection"));
458                    assignments.insert((lhs_child, rhs_child));
459                    child = next_sibling;
460                }
461            }
462        }
463        drop(assignments);
464
465        // Create values for places whose type have scalar layout.
466        let typing_env = body.typing_env(tcx);
467        for place_info in self.places.iter_mut() {
468            // The user requires a bound on the number of created values.
469            if let Some(value_limit) = value_limit
470                && self.value_count >= value_limit
471            {
472                break;
473            }
474
475            if let Ok(ty) = tcx.try_normalize_erasing_regions(typing_env, place_info.ty) {
476                place_info.ty = ty;
477            }
478
479            // Allocate a value slot if it doesn't have one, and the user requested one.
480            assert!(place_info.value_index.is_none());
481            if let Ok(layout) = tcx.layout_of(typing_env.as_query_input(place_info.ty))
482                && layout.backend_repr.is_scalar()
483            {
484                place_info.value_index = Some(self.value_count.into());
485                self.value_count += 1;
486            }
487        }
488
489        // Pre-compute the tree of ValueIndex nested in each PlaceIndex.
490        // `inner_values_buffer[inner_values[place]]` is the set of all the values
491        // reachable by projecting `place`.
492        self.inner_values_buffer = Vec::with_capacity(self.value_count);
493        self.inner_values = IndexVec::from_elem(0..0, &self.places);
494        for local in body.local_decls.indices() {
495            if let Some(place) = self.locals[local] {
496                self.cache_preorder_invoke(place);
497            }
498        }
499
500        // Trim useless places.
501        for opt_place in self.locals.iter_mut() {
502            if let Some(place) = *opt_place
503                && self.inner_values[place].is_empty()
504            {
505                *opt_place = None;
506            }
507        }
508        #[allow(rustc::potential_query_instability)]
509        self.projections.retain(|_, child| !self.inner_values[*child].is_empty());
510    }
511
512    #[tracing::instrument(level = "trace", skip(self), ret)]
513    fn register_place(&mut self, ty: Ty<'tcx>, base: PlaceIndex, elem: TrackElem) -> PlaceIndex {
514        *self.projections.entry((base, elem)).or_insert_with(|| {
515            let next = self.places.push(PlaceInfo::new(ty, Some(elem)));
516            self.places[next].next_sibling = self.places[base].first_child;
517            self.places[base].first_child = Some(next);
518            next
519        })
520    }
521
522    /// Precompute the list of values inside `root` and store it inside
523    /// as a slice within `inner_values_buffer`.
524    fn cache_preorder_invoke(&mut self, root: PlaceIndex) {
525        let start = self.inner_values_buffer.len();
526        if let Some(vi) = self.places[root].value_index {
527            self.inner_values_buffer.push(vi);
528        }
529
530        // We manually iterate instead of using `children` as we need to mutate `self`.
531        let mut next_child = self.places[root].first_child;
532        while let Some(child) = next_child {
533            ensure_sufficient_stack(|| self.cache_preorder_invoke(child));
534            next_child = self.places[child].next_sibling;
535        }
536
537        let end = self.inner_values_buffer.len();
538        self.inner_values[root] = start..end;
539    }
540}
541
542struct PlaceCollector<'a, 'tcx> {
543    tcx: TyCtxt<'tcx>,
544    body: &'a Body<'tcx>,
545    map: &'a mut Map<'tcx>,
546    assignments: FxIndexSet<(PlaceIndex, PlaceIndex)>,
547}
548
549impl<'tcx> PlaceCollector<'_, 'tcx> {
550    #[tracing::instrument(level = "trace", skip(self))]
551    fn register_place(&mut self, place: Place<'tcx>) -> Option<PlaceIndex> {
552        // Create a place for this projection.
553        let mut place_index = self.map.locals[place.local]?;
554        let mut ty = PlaceTy::from_ty(self.body.local_decls[place.local].ty);
555        tracing::trace!(?place_index, ?ty);
556
557        if let ty::Ref(_, ref_ty, _) | ty::RawPtr(ref_ty, _) = ty.ty.kind()
558            && let ty::Slice(..) = ref_ty.kind()
559        {
560            self.map.register_place(self.tcx.types.usize, place_index, TrackElem::DerefLen);
561        } else if ty.ty.is_enum() {
562            let discriminant_ty = ty.ty.discriminant_ty(self.tcx);
563            self.map.register_place(discriminant_ty, place_index, TrackElem::Discriminant);
564        }
565
566        for proj in place.projection {
567            let track_elem = proj.try_into().ok()?;
568            ty = ty.projection_ty(self.tcx, proj);
569            place_index = self.map.register_place(ty.ty, place_index, track_elem);
570            tracing::trace!(?proj, ?place_index, ?ty);
571
572            if let ty::Ref(_, ref_ty, _) | ty::RawPtr(ref_ty, _) = ty.ty.kind()
573                && let ty::Slice(..) = ref_ty.kind()
574            {
575                self.map.register_place(self.tcx.types.usize, place_index, TrackElem::DerefLen);
576            } else if ty.ty.is_enum() {
577                let discriminant_ty = ty.ty.discriminant_ty(self.tcx);
578                self.map.register_place(discriminant_ty, place_index, TrackElem::Discriminant);
579            }
580        }
581
582        Some(place_index)
583    }
584}
585
586impl<'tcx> Visitor<'tcx> for PlaceCollector<'_, 'tcx> {
587    #[tracing::instrument(level = "trace", skip(self))]
588    fn visit_place(&mut self, place: &Place<'tcx>, ctxt: PlaceContext, _: Location) {
589        if !ctxt.is_use() {
590            return;
591        }
592
593        self.register_place(*place);
594    }
595
596    fn visit_assign(&mut self, lhs: &Place<'tcx>, rhs: &Rvalue<'tcx>, location: Location) {
597        self.super_assign(lhs, rhs, location);
598
599        match rhs {
600            Rvalue::Use(Operand::Move(rhs) | Operand::Copy(rhs)) | Rvalue::CopyForDeref(rhs) => {
601                let Some(lhs) = self.register_place(*lhs) else { return };
602                let Some(rhs) = self.register_place(*rhs) else { return };
603                self.assignments.insert((lhs, rhs));
604            }
605            Rvalue::Aggregate(kind, fields) => {
606                let Some(mut lhs) = self.register_place(*lhs) else { return };
607                match **kind {
608                    // Do not propagate unions.
609                    AggregateKind::Adt(_, _, _, _, Some(_)) => return,
610                    AggregateKind::Adt(_, variant, _, _, None) => {
611                        let ty = self.map.places[lhs].ty;
612                        if ty.is_enum() {
613                            lhs = self.map.register_place(ty, lhs, TrackElem::Variant(variant));
614                        }
615                    }
616                    AggregateKind::RawPtr(..)
617                    | AggregateKind::Array(_)
618                    | AggregateKind::Tuple
619                    | AggregateKind::Closure(..)
620                    | AggregateKind::Coroutine(..)
621                    | AggregateKind::CoroutineClosure(..) => {}
622                }
623                for (index, field) in fields.iter_enumerated() {
624                    if let Some(rhs) = field.place()
625                        && let Some(rhs) = self.register_place(rhs)
626                    {
627                        let lhs = self.map.register_place(
628                            self.map.places[rhs].ty,
629                            lhs,
630                            TrackElem::Field(index),
631                        );
632                        self.assignments.insert((lhs, rhs));
633                    }
634                }
635            }
636            _ => {}
637        }
638    }
639}
640
641impl<'tcx> Map<'tcx> {
642    /// Applies a single projection element, yielding the corresponding child.
643    pub fn apply(&self, place: PlaceIndex, elem: TrackElem) -> Option<PlaceIndex> {
644        self.projections.get(&(place, elem)).copied()
645    }
646
647    /// Locates the given place, if it exists in the tree.
648    fn find_extra(
649        &self,
650        place: PlaceRef<'_>,
651        extra: impl IntoIterator<Item = TrackElem>,
652    ) -> Option<PlaceIndex> {
653        let mut index = *self.locals[place.local].as_ref()?;
654
655        for &elem in place.projection {
656            index = self.apply(index, elem.try_into().ok()?)?;
657        }
658        for elem in extra {
659            index = self.apply(index, elem)?;
660        }
661
662        Some(index)
663    }
664
665    /// Locates the given place, if it exists in the tree.
666    pub fn find(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
667        self.find_extra(place, [])
668    }
669
670    /// Locates the given place and applies `Discriminant`, if it exists in the tree.
671    pub fn find_discr(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
672        self.find_extra(place, [TrackElem::Discriminant])
673    }
674
675    /// Locates the given place and applies `DerefLen`, if it exists in the tree.
676    pub fn find_len(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
677        self.find_extra(place, [TrackElem::DerefLen])
678    }
679
680    /// Iterate over all direct children.
681    fn children(&self, parent: PlaceIndex) -> impl Iterator<Item = PlaceIndex> {
682        Children::new(self, parent)
683    }
684
685    /// Invoke a function on the given place and all places that may alias it.
686    ///
687    /// In particular, when the given place has a variant downcast, we invoke the function on all
688    /// the other variants.
689    ///
690    /// `tail_elem` allows to support discriminants that are not a place in MIR, but that we track
691    /// as such.
692    fn for_each_aliasing_place(
693        &self,
694        place: PlaceRef<'_>,
695        tail_elem: Option<TrackElem>,
696        f: &mut impl FnMut(ValueIndex),
697    ) {
698        if place.is_indirect_first_projection() {
699            // We do not track indirect places.
700            return;
701        }
702        let Some(mut index) = self.locals[place.local] else {
703            // The local is not tracked at all, so it does not alias anything.
704            return;
705        };
706        let elems = place.projection.iter().map(|&elem| elem.try_into()).chain(tail_elem.map(Ok));
707        for elem in elems {
708            // A field aliases the parent place.
709            if let Some(vi) = self.places[index].value_index {
710                f(vi);
711            }
712
713            let Ok(elem) = elem else { return };
714            let sub = self.apply(index, elem);
715            if let TrackElem::Variant(..) | TrackElem::Discriminant = elem {
716                // Enum variant fields and enum discriminants alias each another.
717                self.for_each_variant_sibling(index, sub, f);
718            }
719            if let Some(sub) = sub {
720                index = sub
721            } else {
722                return;
723            }
724        }
725        self.for_each_value_inside(index, f);
726    }
727
728    /// Invoke the given function on all the descendants of the given place, except one branch.
729    fn for_each_variant_sibling(
730        &self,
731        parent: PlaceIndex,
732        preserved_child: Option<PlaceIndex>,
733        f: &mut impl FnMut(ValueIndex),
734    ) {
735        for sibling in self.children(parent) {
736            let elem = self.places[sibling].proj_elem;
737            // Only invalidate variants and discriminant. Fields (for coroutines) are not
738            // invalidated by assignment to a variant.
739            if let Some(TrackElem::Variant(..) | TrackElem::Discriminant) = elem
740                // Only invalidate the other variants, the current one is fine.
741                && Some(sibling) != preserved_child
742            {
743                self.for_each_value_inside(sibling, f);
744            }
745        }
746    }
747
748    /// Invoke a function on each value in the given place and all descendants.
749    fn for_each_value_inside(&self, root: PlaceIndex, f: &mut impl FnMut(ValueIndex)) {
750        let range = self.inner_values[root].clone();
751        let values = &self.inner_values_buffer[range];
752        for &v in values {
753            f(v)
754        }
755    }
756
757    /// Invoke a function on each value in the given place and all descendants.
758    pub fn for_each_projection_value<O>(
759        &self,
760        root: PlaceIndex,
761        value: O,
762        project: &mut impl FnMut(TrackElem, &O) -> Option<O>,
763        f: &mut impl FnMut(PlaceIndex, &O),
764    ) {
765        // Fast path is there is nothing to do.
766        if self.inner_values[root].is_empty() {
767            return;
768        }
769
770        if self.places[root].value_index.is_some() {
771            f(root, &value)
772        }
773
774        for child in self.children(root) {
775            let elem = self.places[child].proj_elem.unwrap();
776            if let Some(value) = project(elem, &value) {
777                self.for_each_projection_value(child, value, project, f);
778            }
779        }
780    }
781}
782
783/// This is the information tracked for every [`PlaceIndex`] and is stored by [`Map`].
784///
785/// Together, `first_child` and `next_sibling` form an intrusive linked list, which is used to
786/// model a tree structure (a replacement for a member like `children: Vec<PlaceIndex>`).
787#[derive(Debug)]
788struct PlaceInfo<'tcx> {
789    /// Type of the referenced place.
790    ty: Ty<'tcx>,
791
792    /// We store a [`ValueIndex`] if and only if the placed is tracked by the analysis.
793    value_index: Option<ValueIndex>,
794
795    /// The projection used to go from parent to this node (only None for root).
796    proj_elem: Option<TrackElem>,
797
798    /// The leftmost child.
799    first_child: Option<PlaceIndex>,
800
801    /// Index of the sibling to the right of this node.
802    next_sibling: Option<PlaceIndex>,
803}
804
805impl<'tcx> PlaceInfo<'tcx> {
806    fn new(ty: Ty<'tcx>, proj_elem: Option<TrackElem>) -> Self {
807        Self { ty, next_sibling: None, first_child: None, proj_elem, value_index: None }
808    }
809}
810
811struct Children<'a, 'tcx> {
812    map: &'a Map<'tcx>,
813    next: Option<PlaceIndex>,
814}
815
816impl<'a, 'tcx> Children<'a, 'tcx> {
817    fn new(map: &'a Map<'tcx>, parent: PlaceIndex) -> Self {
818        Self { map, next: map.places[parent].first_child }
819    }
820}
821
822impl Iterator for Children<'_, '_> {
823    type Item = PlaceIndex;
824
825    fn next(&mut self) -> Option<Self::Item> {
826        match self.next {
827            Some(child) => {
828                self.next = self.map.places[child].next_sibling;
829                Some(child)
830            }
831            None => None,
832        }
833    }
834}
835
836/// Used as the result of an operand or r-value.
837#[derive(Debug)]
838pub enum ValueOrPlace<V> {
839    Value(V),
840    Place(PlaceIndex),
841}
842
843impl<V: HasTop> ValueOrPlace<V> {
844    pub const TOP: Self = ValueOrPlace::Value(V::TOP);
845}
846
847/// The set of projection elements that can be used by a tracked place.
848///
849/// Although only field projections are currently allowed, this could change in the future.
850#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
851pub enum TrackElem {
852    Field(FieldIdx),
853    Variant(VariantIdx),
854    Discriminant,
855    // Length of a slice.
856    DerefLen,
857}
858
859impl<V, T> TryFrom<ProjectionElem<V, T>> for TrackElem {
860    type Error = ();
861
862    fn try_from(value: ProjectionElem<V, T>) -> Result<Self, Self::Error> {
863        match value {
864            ProjectionElem::Field(field, _) => Ok(TrackElem::Field(field)),
865            ProjectionElem::Downcast(_, idx) => Ok(TrackElem::Variant(idx)),
866            _ => Err(()),
867        }
868    }
869}
870
871/// Invokes `f` on all direct fields of `ty`.
872pub fn iter_fields<'tcx>(
873    ty: Ty<'tcx>,
874    tcx: TyCtxt<'tcx>,
875    typing_env: ty::TypingEnv<'tcx>,
876    mut f: impl FnMut(Option<VariantIdx>, FieldIdx, Ty<'tcx>),
877) {
878    match ty.kind() {
879        ty::Tuple(list) => {
880            for (field, ty) in list.iter().enumerate() {
881                f(None, field.into(), ty);
882            }
883        }
884        ty::Adt(def, args) => {
885            if def.is_union() {
886                return;
887            }
888            for (v_index, v_def) in def.variants().iter_enumerated() {
889                let variant = if def.is_struct() { None } else { Some(v_index) };
890                for (f_index, f_def) in v_def.fields.iter().enumerate() {
891                    let field_ty = f_def.ty(tcx, args);
892                    let field_ty = tcx
893                        .try_normalize_erasing_regions(typing_env, field_ty)
894                        .unwrap_or_else(|_| tcx.erase_regions(field_ty));
895                    f(variant, f_index.into(), field_ty);
896                }
897            }
898        }
899        ty::Closure(_, args) => {
900            iter_fields(args.as_closure().tupled_upvars_ty(), tcx, typing_env, f);
901        }
902        ty::Coroutine(_, args) => {
903            iter_fields(args.as_coroutine().tupled_upvars_ty(), tcx, typing_env, f);
904        }
905        ty::CoroutineClosure(_, args) => {
906            iter_fields(args.as_coroutine_closure().tupled_upvars_ty(), tcx, typing_env, f);
907        }
908        _ => (),
909    }
910}
911
912/// Returns all locals with projections that have their reference or address taken.
913pub fn excluded_locals(body: &Body<'_>) -> DenseBitSet<Local> {
914    struct Collector {
915        result: DenseBitSet<Local>,
916    }
917
918    impl<'tcx> Visitor<'tcx> for Collector {
919        fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, _location: Location) {
920            if (context.is_borrow()
921                || context.is_address_of()
922                || context.is_drop()
923                || context == PlaceContext::MutatingUse(MutatingUseContext::AsmOutput))
924                && !place.is_indirect()
925            {
926                // A pointer to a place could be used to access other places with the same local,
927                // hence we have to exclude the local completely.
928                self.result.insert(place.local);
929            }
930        }
931    }
932
933    let mut collector = Collector { result: DenseBitSet::new_empty(body.local_decls.len()) };
934    collector.visit_body(body);
935    collector.result
936}
937
938fn debug_with_context_rec<V: Debug + Eq + HasBottom>(
939    place: PlaceIndex,
940    place_str: &str,
941    new: &StateData<V>,
942    old: Option<&StateData<V>>,
943    map: &Map<'_>,
944    f: &mut Formatter<'_>,
945) -> std::fmt::Result {
946    if let Some(value) = map.places[place].value_index {
947        match old {
948            None => writeln!(f, "{}: {:?}", place_str, new.get(value))?,
949            Some(old) => {
950                if new.get(value) != old.get(value) {
951                    writeln!(f, "\u{001f}-{}: {:?}", place_str, old.get(value))?;
952                    writeln!(f, "\u{001f}+{}: {:?}", place_str, new.get(value))?;
953                }
954            }
955        }
956    }
957
958    for child in map.children(place) {
959        let info_elem = map.places[child].proj_elem.unwrap();
960        let child_place_str = match info_elem {
961            TrackElem::Discriminant => {
962                format!("discriminant({place_str})")
963            }
964            TrackElem::Variant(idx) => {
965                format!("({place_str} as {idx:?})")
966            }
967            TrackElem::Field(field) => {
968                if place_str.starts_with('*') {
969                    format!("({}).{}", place_str, field.index())
970                } else {
971                    format!("{}.{}", place_str, field.index())
972                }
973            }
974            TrackElem::DerefLen => {
975                format!("Len(*{})", place_str)
976            }
977        };
978        debug_with_context_rec(child, &child_place_str, new, old, map, f)?;
979    }
980
981    Ok(())
982}
983
984pub fn debug_with_context<V: Debug + Eq + HasBottom>(
985    new: &StateData<V>,
986    old: Option<&StateData<V>>,
987    map: &Map<'_>,
988    f: &mut Formatter<'_>,
989) -> std::fmt::Result {
990    for (local, place) in map.locals.iter_enumerated() {
991        if let Some(place) = place {
992            debug_with_context_rec(*place, &format!("{local:?}"), new, old, map, f)?;
993        }
994    }
995    Ok(())
996}