compiler/rustc_mir_dataflow/src/value_analysis.rs

   1 //! This module provides a framework on top of the normal MIR dataflow framework to simplify the
   2 //! implementation of analyses that track information about the values stored in certain places.
   3 //! We are using the term "place" here to refer to a `mir::Place` (a place expression) instead of
   4 //! an `interpret::Place` (a memory location).
   5 //!
   6 //! The default methods of [`ValueAnalysis`] (prefixed with `super_` instead of `handle_`)
   7 //! provide some behavior that should be valid for all abstract domains that are based only on the
   8 //! value stored in a certain place. On top of these default rules, an implementation should
   9 //! override some of the `handle_` methods. For an example, see `ConstAnalysis`.
  10 //!
  11 //! An implementation must also provide a [`Map`]. Before the analysis begins, all places that
  12 //! should be tracked during the analysis must be registered. During the analysis, no new places
  13 //! can be registered. The [`State`] can be queried to retrieve the abstract value stored for a
  14 //! certain place by passing the map.
  15 //!
  16 //! This framework is currently experimental. Originally, it supported shared references and enum
  17 //! variants. However, it was discovered that both of these were unsound, and especially references
  18 //! had subtle but serious issues. In the future, they could be added back in, but we should clarify
  19 //! the rules for optimizations that rely on the aliasing model first.
  20 //!
  21 //!
  22 //! # Notes
  23 //!
  24 //! - The bottom state denotes uninitialized memory. Because we are only doing a sound approximation
  25 //! of the actual execution, we can also use this state for places where access would be UB.
  26 //!
  27 //! - The assignment logic in `State::assign_place_idx` assumes that the places are non-overlapping,
  28 //! or identical. Note that this refers to place expressions, not memory locations.
  29 //!
  30 //! - Currently, places that have their reference taken cannot be tracked. Although this would be
  31 //! possible, it has to rely on some aliasing model, which we are not ready to commit to yet.
  32 //! Because of that, we can assume that the only way to change the value behind a tracked place is
  33 //! by direct assignment.
  34
  35 use std::fmt::{Debug, Formatter};
  36
  37 use rustc_data_structures::fx::FxHashMap;
  38 use rustc_index::vec::IndexVec;
  39 use rustc_middle::mir::visit::{MutatingUseContext, PlaceContext, Visitor};
  40 use rustc_middle::mir::*;
  41 use rustc_middle::ty::{self, Ty, TyCtxt};
  42 use rustc_target::abi::VariantIdx;
  43
  44 use crate::lattice::{HasBottom, HasTop};
  45 use crate::{
  46     fmt::DebugWithContext, Analysis, AnalysisDomain, CallReturnPlaces, JoinSemiLattice,
  47     SwitchIntEdgeEffects,
  48 };
  49
  50 pub trait ValueAnalysis<'tcx> {
  51     /// For each place of interest, the analysis tracks a value of the given type.
  52     type Value: Clone + JoinSemiLattice + HasBottom + HasTop;
  53
  54     const NAME: &'static str;
  55
  56     fn map(&self) -> &Map;
  57
  58     fn handle_statement(&self, statement: &Statement<'tcx>, state: &mut State<Self::Value>) {
  59         self.super_statement(statement, state)
  60     }
  61
  62     fn super_statement(&self, statement: &Statement<'tcx>, state: &mut State<Self::Value>) {
  63         match &statement.kind {
  64             StatementKind::Assign(box (place, rvalue)) => {
  65                 self.handle_assign(*place, rvalue, state);
  66             }
  67             StatementKind::SetDiscriminant { .. } => {
  68                 // Could treat this as writing a constant to a pseudo-place.
  69                 // But discriminants are currently not tracked, so we do nothing.
  70                 // Related: https://github.com/rust-lang/unsafe-code-guidelines/issues/84
  71             }
  72             StatementKind::Intrinsic(box intrinsic) => {
  73                 self.handle_intrinsic(intrinsic, state);
  74             }
  75             StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => {
  76                 // StorageLive leaves the local in an uninitialized state.
  77                 // StorageDead makes it UB to access the local afterwards.
  78                 state.flood_with(Place::from(*local).as_ref(), self.map(), Self::Value::bottom());
  79             }
  80             StatementKind::Deinit(box place) => {
  81                 // Deinit makes the place uninitialized.
  82                 state.flood_with(place.as_ref(), self.map(), Self::Value::bottom());
  83             }
  84             StatementKind::Retag(..) => {
  85                 // We don't track references.
  86             }
  87             StatementKind::Nop
  88             | StatementKind::FakeRead(..)
  89             | StatementKind::Coverage(..)
  90             | StatementKind::AscribeUserType(..) => (),
  91         }
  92     }
  93
  94     fn handle_intrinsic(
  95         &self,
  96         intrinsic: &NonDivergingIntrinsic<'tcx>,
  97         state: &mut State<Self::Value>,
  98     ) {
  99         self.super_intrinsic(intrinsic, state);
 100     }
 101
 102     fn super_intrinsic(
 103         &self,
 104         intrinsic: &NonDivergingIntrinsic<'tcx>,
 105         state: &mut State<Self::Value>,
 106     ) {
 107         match intrinsic {
 108             NonDivergingIntrinsic::Assume(..) => {
 109                 // Could use this, but ignoring it is sound.
 110             }
 111             NonDivergingIntrinsic::CopyNonOverlapping(CopyNonOverlapping { dst, .. }) => {
 112                 if let Some(place) = dst.place() {
 113                     state.flood(place.as_ref(), self.map());
 114                 }
 115             }
 116         }
 117     }
 118
 119     fn handle_assign(
 120         &self,
 121         target: Place<'tcx>,
 122         rvalue: &Rvalue<'tcx>,
 123         state: &mut State<Self::Value>,
 124     ) {
 125         self.super_assign(target, rvalue, state)
 126     }
 127
 128     fn super_assign(
 129         &self,
 130         target: Place<'tcx>,
 131         rvalue: &Rvalue<'tcx>,
 132         state: &mut State<Self::Value>,
 133     ) {
 134         let result = self.handle_rvalue(rvalue, state);
 135         state.assign(target.as_ref(), result, self.map());
 136     }
 137
 138     fn handle_rvalue(
 139         &self,
 140         rvalue: &Rvalue<'tcx>,
 141         state: &mut State<Self::Value>,
 142     ) -> ValueOrPlace<Self::Value> {
 143         self.super_rvalue(rvalue, state)
 144     }
 145
 146     fn super_rvalue(
 147         &self,
 148         rvalue: &Rvalue<'tcx>,
 149         state: &mut State<Self::Value>,
 150     ) -> ValueOrPlace<Self::Value> {
 151         match rvalue {
 152             Rvalue::Use(operand) => self.handle_operand(operand, state),
 153             Rvalue::CopyForDeref(place) => self.handle_operand(&Operand::Copy(*place), state),
 154             Rvalue::Ref(..) | Rvalue::AddressOf(..) => {
 155                 // We don't track such places.
 156                 ValueOrPlace::top()
 157             }
 158             Rvalue::Repeat(..)
 159             | Rvalue::ThreadLocalRef(..)
 160             | Rvalue::Len(..)
 161             | Rvalue::Cast(..)
 162             | Rvalue::BinaryOp(..)
 163             | Rvalue::CheckedBinaryOp(..)
 164             | Rvalue::NullaryOp(..)
 165             | Rvalue::UnaryOp(..)
 166             | Rvalue::Discriminant(..)
 167             | Rvalue::Aggregate(..)
 168             | Rvalue::ShallowInitBox(..) => {
 169                 // No modification is possible through these r-values.
 170                 ValueOrPlace::top()
 171             }
 172         }
 173     }
 174
 175     fn handle_operand(
 176         &self,
 177         operand: &Operand<'tcx>,
 178         state: &mut State<Self::Value>,
 179     ) -> ValueOrPlace<Self::Value> {
 180         self.super_operand(operand, state)
 181     }
 182
 183     fn super_operand(
 184         &self,
 185         operand: &Operand<'tcx>,
 186         state: &mut State<Self::Value>,
 187     ) -> ValueOrPlace<Self::Value> {
 188         match operand {
 189             Operand::Constant(box constant) => {
 190                 ValueOrPlace::Value(self.handle_constant(constant, state))
 191             }
 192             Operand::Copy(place) | Operand::Move(place) => {
 193                 // On move, we would ideally flood the place with bottom. But with the current
 194                 // framework this is not possible (similar to `InterpCx::eval_operand`).
 195                 self.map()
 196                     .find(place.as_ref())
 197                     .map(ValueOrPlace::Place)
 198                     .unwrap_or(ValueOrPlace::top())
 199             }
 200         }
 201     }
 202
 203     fn handle_constant(
 204         &self,
 205         constant: &Constant<'tcx>,
 206         state: &mut State<Self::Value>,
 207     ) -> Self::Value {
 208         self.super_constant(constant, state)
 209     }
 210
 211     fn super_constant(
 212         &self,
 213         _constant: &Constant<'tcx>,
 214         _state: &mut State<Self::Value>,
 215     ) -> Self::Value {
 216         Self::Value::top()
 217     }
 218
 219     /// The effect of a successful function call return should not be
 220     /// applied here, see [`Analysis::apply_terminator_effect`].
 221     fn handle_terminator(&self, terminator: &Terminator<'tcx>, state: &mut State<Self::Value>) {
 222         self.super_terminator(terminator, state)
 223     }
 224
 225     fn super_terminator(&self, terminator: &Terminator<'tcx>, _state: &mut State<Self::Value>) {
 226         match &terminator.kind {
 227             TerminatorKind::Call { .. } | TerminatorKind::InlineAsm { .. } => {
 228                 // Effect is applied by `handle_call_return`.
 229             }
 230             TerminatorKind::Drop { .. } => {
 231                 // We don't track dropped places.
 232             }
 233             TerminatorKind::DropAndReplace { .. } | TerminatorKind::Yield { .. } => {
 234                 // They would have an effect, but are not allowed in this phase.
 235                 bug!("encountered disallowed terminator");
 236             }
 237             TerminatorKind::Goto { .. }
 238             | TerminatorKind::SwitchInt { .. }
 239             | TerminatorKind::Resume
 240             | TerminatorKind::Abort
 241             | TerminatorKind::Return
 242             | TerminatorKind::Unreachable
 243             | TerminatorKind::Assert { .. }
 244             | TerminatorKind::GeneratorDrop
 245             | TerminatorKind::FalseEdge { .. }
 246             | TerminatorKind::FalseUnwind { .. } => {
 247                 // These terminators have no effect on the analysis.
 248             }
 249         }
 250     }
 251
 252     fn handle_call_return(
 253         &self,
 254         return_places: CallReturnPlaces<'_, 'tcx>,
 255         state: &mut State<Self::Value>,
 256     ) {
 257         self.super_call_return(return_places, state)
 258     }
 259
 260     fn super_call_return(
 261         &self,
 262         return_places: CallReturnPlaces<'_, 'tcx>,
 263         state: &mut State<Self::Value>,
 264     ) {
 265         return_places.for_each(|place| {
 266             state.flood(place.as_ref(), self.map());
 267         })
 268     }
 269
 270     fn handle_switch_int(
 271         &self,
 272         discr: &Operand<'tcx>,
 273         apply_edge_effects: &mut impl SwitchIntEdgeEffects<State<Self::Value>>,
 274     ) {
 275         self.super_switch_int(discr, apply_edge_effects)
 276     }
 277
 278     fn super_switch_int(
 279         &self,
 280         _discr: &Operand<'tcx>,
 281         _apply_edge_effects: &mut impl SwitchIntEdgeEffects<State<Self::Value>>,
 282     ) {
 283     }
 284
 285     fn wrap(self) -> ValueAnalysisWrapper<Self>
 286     where
 287         Self: Sized,
 288     {
 289         ValueAnalysisWrapper(self)
 290     }
 291 }
 292
 293 pub struct ValueAnalysisWrapper<T>(pub T);
 294
 295 impl<'tcx, T: ValueAnalysis<'tcx>> AnalysisDomain<'tcx> for ValueAnalysisWrapper<T> {
 296     type Domain = State<T::Value>;
 297
 298     type Direction = crate::Forward;
 299
 300     const NAME: &'static str = T::NAME;
 301
 302     fn bottom_value(&self, _body: &Body<'tcx>) -> Self::Domain {
 303         State(StateData::Unreachable)
 304     }
 305
 306     fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain) {
 307         // The initial state maps all tracked places of argument projections to ⊤ and the rest to ⊥.
 308         assert!(matches!(state.0, StateData::Unreachable));
 309         let values = IndexVec::from_elem_n(T::Value::bottom(), self.0.map().value_count);
 310         *state = State(StateData::Reachable(values));
 311         for arg in body.args_iter() {
 312             state.flood(PlaceRef { local: arg, projection: &[] }, self.0.map());
 313         }
 314     }
 315 }
 316
 317 impl<'tcx, T> Analysis<'tcx> for ValueAnalysisWrapper<T>
 318 where
 319     T: ValueAnalysis<'tcx>,
 320 {
 321     fn apply_statement_effect(
 322         &self,
 323         state: &mut Self::Domain,
 324         statement: &Statement<'tcx>,
 325         _location: Location,
 326     ) {
 327         if state.is_reachable() {
 328             self.0.handle_statement(statement, state);
 329         }
 330     }
 331
 332     fn apply_terminator_effect(
 333         &self,
 334         state: &mut Self::Domain,
 335         terminator: &Terminator<'tcx>,
 336         _location: Location,
 337     ) {
 338         if state.is_reachable() {
 339             self.0.handle_terminator(terminator, state);
 340         }
 341     }
 342
 343     fn apply_call_return_effect(
 344         &self,
 345         state: &mut Self::Domain,
 346         _block: BasicBlock,
 347         return_places: crate::CallReturnPlaces<'_, 'tcx>,
 348     ) {
 349         if state.is_reachable() {
 350             self.0.handle_call_return(return_places, state)
 351         }
 352     }
 353
 354     fn apply_switch_int_edge_effects(
 355         &self,
 356         _block: BasicBlock,
 357         discr: &Operand<'tcx>,
 358         apply_edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>,
 359     ) {
 360         // FIXME: Dataflow framework provides no access to current state here.
 361         self.0.handle_switch_int(discr, apply_edge_effects)
 362     }
 363 }
 364
 365 rustc_index::newtype_index!(
 366     /// This index uniquely identifies a place.
 367     ///
 368     /// Not every place has a `PlaceIndex`, and not every `PlaceIndex` correspondends to a tracked
 369     /// place. However, every tracked place and all places along its projection have a `PlaceIndex`.
 370     pub struct PlaceIndex {}
 371 );
 372
 373 rustc_index::newtype_index!(
 374     /// This index uniquely identifies a tracked place and therefore a slot in [`State`].
 375     ///
 376     /// It is an implementation detail of this module.
 377     struct ValueIndex {}
 378 );
 379
 380 /// See [`State`].
 381 #[derive(PartialEq, Eq, Debug)]
 382 enum StateData<V> {
 383     Reachable(IndexVec<ValueIndex, V>),
 384     Unreachable,
 385 }
 386
 387 impl<V: Clone> Clone for StateData<V> {
 388     fn clone(&self) -> Self {
 389         match self {
 390             Self::Reachable(x) => Self::Reachable(x.clone()),
 391             Self::Unreachable => Self::Unreachable,
 392         }
 393     }
 394
 395     fn clone_from(&mut self, source: &Self) {
 396         match (&mut *self, source) {
 397             (Self::Reachable(x), Self::Reachable(y)) => {
 398                 // We go through `raw` here, because `IndexVec` currently has a naive `clone_from`.
 399                 x.raw.clone_from(&y.raw);
 400             }
 401             _ => *self = source.clone(),
 402         }
 403     }
 404 }
 405
 406 /// The dataflow state for an instance of [`ValueAnalysis`].
 407 ///
 408 /// Every instance specifies a lattice that represents the possible values of a single tracked
 409 /// place. If we call this lattice `V` and set of tracked places `P`, then a [`State`] is an
 410 /// element of `{unreachable} ∪ (P -> V)`. This again forms a lattice, where the bottom element is
 411 /// `unreachable` and the top element is the mapping `p ↦ ⊤`. Note that the mapping `p ↦ ⊥` is not
 412 /// the bottom element (because joining an unreachable and any other reachable state yields a
 413 /// reachable state). All operations on unreachable states are ignored.
 414 ///
 415 /// Flooding means assigning a value (by default `⊤`) to all tracked projections of a given place.
 416 #[derive(PartialEq, Eq, Debug)]
 417 pub struct State<V>(StateData<V>);
 418
 419 impl<V: Clone> Clone for State<V> {
 420     fn clone(&self) -> Self {
 421         Self(self.0.clone())
 422     }
 423
 424     fn clone_from(&mut self, source: &Self) {
 425         self.0.clone_from(&source.0);
 426     }
 427 }
 428
 429 impl<V: Clone + HasTop + HasBottom> State<V> {
 430     pub fn is_reachable(&self) -> bool {
 431         matches!(&self.0, StateData::Reachable(_))
 432     }
 433
 434     pub fn mark_unreachable(&mut self) {
 435         self.0 = StateData::Unreachable;
 436     }
 437
 438     pub fn flood_all(&mut self) {
 439         self.flood_all_with(V::top())
 440     }
 441
 442     pub fn flood_all_with(&mut self, value: V) {
 443         let StateData::Reachable(values) = &mut self.0 else { return };
 444         values.raw.fill(value);
 445     }
 446
 447     pub fn flood_with(&mut self, place: PlaceRef<'_>, map: &Map, value: V) {
 448         if let Some(root) = map.find(place) {
 449             self.flood_idx_with(root, map, value);
 450         }
 451     }
 452
 453     pub fn flood(&mut self, place: PlaceRef<'_>, map: &Map) {
 454         self.flood_with(place, map, V::top())
 455     }
 456
 457     pub fn flood_idx_with(&mut self, place: PlaceIndex, map: &Map, value: V) {
 458         let StateData::Reachable(values) = &mut self.0 else { return };
 459         map.preorder_invoke(place, &mut |place| {
 460             if let Some(vi) = map.places[place].value_index {
 461                 values[vi] = value.clone();
 462             }
 463         });
 464     }
 465
 466     pub fn flood_idx(&mut self, place: PlaceIndex, map: &Map) {
 467         self.flood_idx_with(place, map, V::top())
 468     }
 469
 470     /// Copies `source` to `target`, including all tracked places beneath.
 471     ///
 472     /// If `target` contains a place that is not contained in `source`, it will be overwritten with
 473     /// Top. Also, because this will copy all entries one after another, it may only be used for
 474     /// places that are non-overlapping or identical.
 475     pub fn assign_place_idx(&mut self, target: PlaceIndex, source: PlaceIndex, map: &Map) {
 476         let StateData::Reachable(values) = &mut self.0 else { return };
 477
 478         // If both places are tracked, we copy the value to the target. If the target is tracked,
 479         // but the source is not, we have to invalidate the value in target. If the target is not
 480         // tracked, then we don't have to do anything.
 481         if let Some(target_value) = map.places[target].value_index {
 482             if let Some(source_value) = map.places[source].value_index {
 483                 values[target_value] = values[source_value].clone();
 484             } else {
 485                 values[target_value] = V::top();
 486             }
 487         }
 488         for target_child in map.children(target) {
 489             // Try to find corresponding child and recurse. Reasoning is similar as above.
 490             let projection = map.places[target_child].proj_elem.unwrap();
 491             if let Some(source_child) = map.projections.get(&(source, projection)) {
 492                 self.assign_place_idx(target_child, *source_child, map);
 493             } else {
 494                 self.flood_idx(target_child, map);
 495             }
 496         }
 497     }
 498
 499     pub fn assign(&mut self, target: PlaceRef<'_>, result: ValueOrPlace<V>, map: &Map) {
 500         if let Some(target) = map.find(target) {
 501             self.assign_idx(target, result, map);
 502         } else {
 503             // We don't track this place nor any projections, assignment can be ignored.
 504         }
 505     }
 506
 507     pub fn assign_idx(&mut self, target: PlaceIndex, result: ValueOrPlace<V>, map: &Map) {
 508         match result {
 509             ValueOrPlace::Value(value) => {
 510                 // First flood the target place in case we also track any projections (although
 511                 // this scenario is currently not well-supported by the API).
 512                 self.flood_idx(target, map);
 513                 let StateData::Reachable(values) = &mut self.0 else { return };
 514                 if let Some(value_index) = map.places[target].value_index {
 515                     values[value_index] = value;
 516                 }
 517             }
 518             ValueOrPlace::Place(source) => self.assign_place_idx(target, source, map),
 519         }
 520     }
 521
 522     /// Retrieve the value stored for a place, or ⊤ if it is not tracked.
 523     pub fn get(&self, place: PlaceRef<'_>, map: &Map) -> V {
 524         map.find(place).map(|place| self.get_idx(place, map)).unwrap_or(V::top())
 525     }
 526
 527     /// Retrieve the value stored for a place index, or ⊤ if it is not tracked.
 528     pub fn get_idx(&self, place: PlaceIndex, map: &Map) -> V {
 529         match &self.0 {
 530             StateData::Reachable(values) => {
 531                 map.places[place].value_index.map(|v| values[v].clone()).unwrap_or(V::top())
 532             }
 533             StateData::Unreachable => {
 534                 // Because this is unreachable, we can return any value we want.
 535                 V::bottom()
 536             }
 537         }
 538     }
 539 }
 540
 541 impl<V: JoinSemiLattice + Clone> JoinSemiLattice for State<V> {
 542     fn join(&mut self, other: &Self) -> bool {
 543         match (&mut self.0, &other.0) {
 544             (_, StateData::Unreachable) => false,
 545             (StateData::Unreachable, _) => {
 546                 *self = other.clone();
 547                 true
 548             }
 549             (StateData::Reachable(this), StateData::Reachable(other)) => this.join(other),
 550         }
 551     }
 552 }
 553
 554 /// Partial mapping from [`Place`] to [`PlaceIndex`], where some places also have a [`ValueIndex`].
 555 ///
 556 /// This data structure essentially maintains a tree of places and their projections. Some
 557 /// additional bookkeeping is done, to speed up traversal over this tree:
 558 /// - For iteration, every [`PlaceInfo`] contains an intrusive linked list of its children.
 559 /// - To directly get the child for a specific projection, there is a `projections` map.
 560 #[derive(Debug)]
 561 pub struct Map {
 562     locals: IndexVec<Local, Option<PlaceIndex>>,
 563     projections: FxHashMap<(PlaceIndex, TrackElem), PlaceIndex>,
 564     places: IndexVec<PlaceIndex, PlaceInfo>,
 565     value_count: usize,
 566 }
 567
 568 impl Map {
 569     fn new() -> Self {
 570         Self {
 571             locals: IndexVec::new(),
 572             projections: FxHashMap::default(),
 573             places: IndexVec::new(),
 574             value_count: 0,
 575         }
 576     }
 577
 578     /// Returns a map that only tracks places whose type passes the filter.
 579     ///
 580     /// This is currently the only way to create a [`Map`]. The way in which the tracked places are
 581     /// chosen is an implementation detail and may not be relied upon (other than that their type
 582     /// passes the filter).
 583     #[instrument(skip_all, level = "debug")]
 584     pub fn from_filter<'tcx>(
 585         tcx: TyCtxt<'tcx>,
 586         body: &Body<'tcx>,
 587         filter: impl FnMut(Ty<'tcx>) -> bool,
 588     ) -> Self {
 589         let mut map = Self::new();
 590         let exclude = excluded_locals(body);
 591         map.register_with_filter(tcx, body, filter, &exclude);
 592         debug!("registered {} places ({} nodes in total)", map.value_count, map.places.len());
 593         map
 594     }
 595
 596     /// Register all non-excluded places that pass the filter.
 597     fn register_with_filter<'tcx>(
 598         &mut self,
 599         tcx: TyCtxt<'tcx>,
 600         body: &Body<'tcx>,
 601         mut filter: impl FnMut(Ty<'tcx>) -> bool,
 602         exclude: &IndexVec<Local, bool>,
 603     ) {
 604         // We use this vector as stack, pushing and popping projections.
 605         let mut projection = Vec::new();
 606         for (local, decl) in body.local_decls.iter_enumerated() {
 607             if !exclude[local] {
 608                 self.register_with_filter_rec(tcx, local, &mut projection, decl.ty, &mut filter);
 609             }
 610         }
 611     }
 612
 613     /// Potentially register the (local, projection) place and its fields, recursively.
 614     ///
 615     /// Invariant: The projection must only contain fields.
 616     fn register_with_filter_rec<'tcx>(
 617         &mut self,
 618         tcx: TyCtxt<'tcx>,
 619         local: Local,
 620         projection: &mut Vec<PlaceElem<'tcx>>,
 621         ty: Ty<'tcx>,
 622         filter: &mut impl FnMut(Ty<'tcx>) -> bool,
 623     ) {
 624         // Note: The framework supports only scalars for now.
 625         if filter(ty) && ty.is_scalar() {
 626             // We know that the projection only contains trackable elements.
 627             let place = self.make_place(local, projection).unwrap();
 628
 629             // Allocate a value slot if it doesn't have one.
 630             if self.places[place].value_index.is_none() {
 631                 self.places[place].value_index = Some(self.value_count.into());
 632                 self.value_count += 1;
 633             }
 634         }
 635
 636         // Recurse with all fields of this place.
 637         iter_fields(ty, tcx, |variant, field, ty| {
 638             if variant.is_some() {
 639                 // Downcasts are currently not supported.
 640                 return;
 641             }
 642             projection.push(PlaceElem::Field(field, ty));
 643             self.register_with_filter_rec(tcx, local, projection, ty, filter);
 644             projection.pop();
 645         });
 646     }
 647
 648     /// Tries to add the place to the map, without allocating a value slot.
 649     ///
 650     /// Can fail if the projection contains non-trackable elements.
 651     fn make_place<'tcx>(
 652         &mut self,
 653         local: Local,
 654         projection: &[PlaceElem<'tcx>],
 655     ) -> Result<PlaceIndex, ()> {
 656         // Get the base index of the local.
 657         let mut index =
 658             *self.locals.get_or_insert_with(local, || self.places.push(PlaceInfo::new(None)));
 659
 660         // Apply the projection.
 661         for &elem in projection {
 662             let elem = elem.try_into()?;
 663             index = *self.projections.entry((index, elem)).or_insert_with(|| {
 664                 // Prepend new child to the linked list.
 665                 let next = self.places.push(PlaceInfo::new(Some(elem)));
 666                 self.places[next].next_sibling = self.places[index].first_child;
 667                 self.places[index].first_child = Some(next);
 668                 next
 669             });
 670         }
 671
 672         Ok(index)
 673     }
 674
 675     /// Returns the number of tracked places, i.e., those for which a value can be stored.
 676     pub fn tracked_places(&self) -> usize {
 677         self.value_count
 678     }
 679
 680     /// Applies a single projection element, yielding the corresponding child.
 681     pub fn apply(&self, place: PlaceIndex, elem: TrackElem) -> Option<PlaceIndex> {
 682         self.projections.get(&(place, elem)).copied()
 683     }
 684
 685     /// Locates the given place, if it exists in the tree.
 686     pub fn find(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
 687         let mut index = *self.locals.get(place.local)?.as_ref()?;
 688
 689         for &elem in place.projection {
 690             index = self.apply(index, elem.try_into().ok()?)?;
 691         }
 692
 693         Some(index)
 694     }
 695
 696     /// Iterate over all direct children.
 697     pub fn children(&self, parent: PlaceIndex) -> impl Iterator<Item = PlaceIndex> + '_ {
 698         Children::new(self, parent)
 699     }
 700
 701     /// Invoke a function on the given place and all descendants.
 702     pub fn preorder_invoke(&self, root: PlaceIndex, f: &mut impl FnMut(PlaceIndex)) {
 703         f(root);
 704         for child in self.children(root) {
 705             self.preorder_invoke(child, f);
 706         }
 707     }
 708 }
 709
 710 /// This is the information tracked for every [`PlaceIndex`] and is stored by [`Map`].
 711 ///
 712 /// Together, `first_child` and `next_sibling` form an intrusive linked list, which is used to
 713 /// model a tree structure (a replacement for a member like `children: Vec<PlaceIndex>`).
 714 #[derive(Debug)]
 715 struct PlaceInfo {
 716     /// We store a [`ValueIndex`] if and only if the placed is tracked by the analysis.
 717     value_index: Option<ValueIndex>,
 718
 719     /// The projection used to go from parent to this node (only None for root).
 720     proj_elem: Option<TrackElem>,
 721
 722     /// The left-most child.
 723     first_child: Option<PlaceIndex>,
 724
 725     /// Index of the sibling to the right of this node.
 726     next_sibling: Option<PlaceIndex>,
 727 }
 728
 729 impl PlaceInfo {
 730     fn new(proj_elem: Option<TrackElem>) -> Self {
 731         Self { next_sibling: None, first_child: None, proj_elem, value_index: None }
 732     }
 733 }
 734
 735 struct Children<'a> {
 736     map: &'a Map,
 737     next: Option<PlaceIndex>,
 738 }
 739
 740 impl<'a> Children<'a> {
 741     fn new(map: &'a Map, parent: PlaceIndex) -> Self {
 742         Self { map, next: map.places[parent].first_child }
 743     }
 744 }
 745
 746 impl<'a> Iterator for Children<'a> {
 747     type Item = PlaceIndex;
 748
 749     fn next(&mut self) -> Option<Self::Item> {
 750         match self.next {
 751             Some(child) => {
 752                 self.next = self.map.places[child].next_sibling;
 753                 Some(child)
 754             }
 755             None => None,
 756         }
 757     }
 758 }
 759
 760 /// Used as the result of an operand or r-value.
 761 pub enum ValueOrPlace<V> {
 762     Value(V),
 763     Place(PlaceIndex),
 764 }
 765
 766 impl<V: HasTop> ValueOrPlace<V> {
 767     pub fn top() -> Self {
 768         ValueOrPlace::Value(V::top())
 769     }
 770 }
 771
 772 /// The set of projection elements that can be used by a tracked place.
 773 ///
 774 /// Although only field projections are currently allowed, this could change in the future.
 775 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
 776 pub enum TrackElem {
 777     Field(Field),
 778 }
 779
 780 impl<V, T> TryFrom<ProjectionElem<V, T>> for TrackElem {
 781     type Error = ();
 782
 783     fn try_from(value: ProjectionElem<V, T>) -> Result<Self, Self::Error> {
 784         match value {
 785             ProjectionElem::Field(field, _) => Ok(TrackElem::Field(field)),
 786             _ => Err(()),
 787         }
 788     }
 789 }
 790
 791 /// Invokes `f` on all direct fields of `ty`.
 792 fn iter_fields<'tcx>(
 793     ty: Ty<'tcx>,
 794     tcx: TyCtxt<'tcx>,
 795     mut f: impl FnMut(Option<VariantIdx>, Field, Ty<'tcx>),
 796 ) {
 797     match ty.kind() {
 798         ty::Tuple(list) => {
 799             for (field, ty) in list.iter().enumerate() {
 800                 f(None, field.into(), ty);
 801             }
 802         }
 803         ty::Adt(def, substs) => {
 804             if def.is_union() {
 805                 return;
 806             }
 807             for (v_index, v_def) in def.variants().iter_enumerated() {
 808                 let variant = if def.is_struct() { None } else { Some(v_index) };
 809                 for (f_index, f_def) in v_def.fields.iter().enumerate() {
 810                     let field_ty = f_def.ty(tcx, substs);
 811                     let field_ty = tcx
 812                         .try_normalize_erasing_regions(ty::ParamEnv::reveal_all(), field_ty)
 813                         .unwrap_or(field_ty);
 814                     f(variant, f_index.into(), field_ty);
 815                 }
 816             }
 817         }
 818         ty::Closure(_, substs) => {
 819             iter_fields(substs.as_closure().tupled_upvars_ty(), tcx, f);
 820         }
 821         _ => (),
 822     }
 823 }
 824
 825 /// Returns all locals with projections that have their reference or address taken.
 826 fn excluded_locals(body: &Body<'_>) -> IndexVec<Local, bool> {
 827     struct Collector {
 828         result: IndexVec<Local, bool>,
 829     }
 830
 831     impl<'tcx> Visitor<'tcx> for Collector {
 832         fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, _location: Location) {
 833             if context.is_borrow()
 834                 || context.is_address_of()
 835                 || context.is_drop()
 836                 || context == PlaceContext::MutatingUse(MutatingUseContext::AsmOutput)
 837             {
 838                 // A pointer to a place could be used to access other places with the same local,
 839                 // hence we have to exclude the local completely.
 840                 self.result[place.local] = true;
 841             }
 842         }
 843     }
 844
 845     let mut collector = Collector { result: IndexVec::from_elem(false, &body.local_decls) };
 846     collector.visit_body(body);
 847     collector.result
 848 }
 849
 850 /// This is used to visualize the dataflow analysis.
 851 impl<'tcx, T> DebugWithContext<ValueAnalysisWrapper<T>> for State<T::Value>
 852 where
 853     T: ValueAnalysis<'tcx>,
 854     T::Value: Debug,
 855 {
 856     fn fmt_with(&self, ctxt: &ValueAnalysisWrapper<T>, f: &mut Formatter<'_>) -> std::fmt::Result {
 857         match &self.0 {
 858             StateData::Reachable(values) => debug_with_context(values, None, ctxt.0.map(), f),
 859             StateData::Unreachable => write!(f, "unreachable"),
 860         }
 861     }
 862
 863     fn fmt_diff_with(
 864         &self,
 865         old: &Self,
 866         ctxt: &ValueAnalysisWrapper<T>,
 867         f: &mut Formatter<'_>,
 868     ) -> std::fmt::Result {
 869         match (&self.0, &old.0) {
 870             (StateData::Reachable(this), StateData::Reachable(old)) => {
 871                 debug_with_context(this, Some(old), ctxt.0.map(), f)
 872             }
 873             _ => Ok(()), // Consider printing something here.
 874         }
 875     }
 876 }
 877
 878 fn debug_with_context_rec<V: Debug + Eq>(
 879     place: PlaceIndex,
 880     place_str: &str,
 881     new: &IndexVec<ValueIndex, V>,
 882     old: Option<&IndexVec<ValueIndex, V>>,
 883     map: &Map,
 884     f: &mut Formatter<'_>,
 885 ) -> std::fmt::Result {
 886     if let Some(value) = map.places[place].value_index {
 887         match old {
 888             None => writeln!(f, "{}: {:?}", place_str, new[value])?,
 889             Some(old) => {
 890                 if new[value] != old[value] {
 891                     writeln!(f, "\u{001f}-{}: {:?}", place_str, old[value])?;
 892                     writeln!(f, "\u{001f}+{}: {:?}", place_str, new[value])?;
 893                 }
 894             }
 895         }
 896     }
 897
 898     for child in map.children(place) {
 899         let info_elem = map.places[child].proj_elem.unwrap();
 900         let child_place_str = match info_elem {
 901             TrackElem::Field(field) => {
 902                 if place_str.starts_with('*') {
 903                     format!("({}).{}", place_str, field.index())
 904                 } else {
 905                     format!("{}.{}", place_str, field.index())
 906                 }
 907             }
 908         };
 909         debug_with_context_rec(child, &child_place_str, new, old, map, f)?;
 910     }
 911
 912     Ok(())
 913 }
 914
 915 fn debug_with_context<V: Debug + Eq>(
 916     new: &IndexVec<ValueIndex, V>,
 917     old: Option<&IndexVec<ValueIndex, V>>,
 918     map: &Map,
 919     f: &mut Formatter<'_>,
 920 ) -> std::fmt::Result {
 921     for (local, place) in map.locals.iter_enumerated() {
 922         if let Some(place) = place {
 923             debug_with_context_rec(*place, &format!("{local:?}"), new, old, map, f)?;
 924         }
 925     }
 926     Ok(())
 927 }