X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=compiler%2Frustc_mir_dataflow%2Fsrc%2Fvalue_analysis.rs;h=db4b0a3deda9dba74aea18e8e184eac255f55b70;hb=becc24a23aed2639db3b78acd93ec6d553898583;hp=55b1185acd39f7e875f27c8319c18a93bea89a9f;hpb=c56e99cdba2dc969902005fc495c12f13b9eb2e1;p=rust.git diff --git a/compiler/rustc_mir_dataflow/src/value_analysis.rs b/compiler/rustc_mir_dataflow/src/value_analysis.rs index 55b1185acd3..db4b0a3deda 100644 --- a/compiler/rustc_mir_dataflow/src/value_analysis.rs +++ b/compiler/rustc_mir_dataflow/src/value_analysis.rs @@ -1,68 +1,50 @@ //! This module provides a framework on top of the normal MIR dataflow framework to simplify the -//! implementation of analyses that track the values stored in places of interest. +//! implementation of analyses that track information about the values stored in certain places. +//! We are using the term "place" here to refer to a `mir::Place` (a place expression) instead of +//! an `interpret::Place` (a memory location). //! //! The default methods of [`ValueAnalysis`] (prefixed with `super_` instead of `handle_`) //! provide some behavior that should be valid for all abstract domains that are based only on the //! value stored in a certain place. On top of these default rules, an implementation should //! override some of the `handle_` methods. For an example, see `ConstAnalysis`. //! -//! An implementation must also provide a [`Map`]. Before the anaylsis begins, all places that -//! should be tracked during the analysis must be registered. Currently, the projections of these -//! places may only contain derefs, fields and downcasts (otherwise registration fails). During the -//! analysis, no new places can be registered. +//! An implementation must also provide a [`Map`]. Before the analysis begins, all places that +//! should be tracked during the analysis must be registered. During the analysis, no new places +//! can be registered. The [`State`] can be queried to retrieve the abstract value stored for a +//! certain place by passing the map. //! -//! Note that if you want to track values behind references, you have to register the dereferenced -//! place. For example: Assume `let x = (0, 0)` and that we want to propagate values from `x.0` and -//! `x.1` also through the assignment `let y = &x`. In this case, we should register `x.0`, `x.1`, -//! `(*y).0` and `(*y).1`. +//! This framework is currently experimental. Originally, it supported shared references and enum +//! variants. However, it was discovered that both of these were unsound, and especially references +//! had subtle but serious issues. In the future, they could be added back in, but we should clarify +//! the rules for optimizations that rely on the aliasing model first. //! //! -//! # Correctness +//! # Notes //! -//! Warning: This is a semi-formal attempt to argue for the correctness of this analysis. If you -//! find any weak spots, let me know! Recommended reading: Abstract Interpretation. We will use the -//! term "place" to refer to a place expression (like `mir::Place`), and we will call the -//! underlying entity "object". For instance, `*_1` and `*_2` are not the same place, but depending -//! on the value of `_1` and `_2`, they could refer to the same object. Also, the same place can -//! refer to different objects during execution. If `_1` is reassigned, then `*_1` may refer to -//! different objects before and after assignment. Additionally, when saying "access to a place", -//! what we really mean is "access to an object denoted by arbitrary projections of that place". +//! - The bottom state denotes uninitialized memory. Because we are only doing a sound approximation +//! of the actual execution, we can also use this state for places where access would be UB. //! -//! In the following, we will assume a constant propagation analysis. Our analysis is correct if -//! every transfer function is correct. This is the case if for every pair (f, f#) and abstract -//! state s, we have f(y(s)) <= y(f#(s)), where s is a mapping from tracked place to top, bottom or -//! a constant. Since pointers (and mutable references) are not tracked, but can be used to change -//! values in the concrete domain, f# must assume that all places that can be affected in this way -//! for a given program point are already marked with top in s (otherwise many assignments and -//! function calls would have no choice but to mark all tracked places with top). This leads us to -//! an invariant: For all possible program points where there could possibly exist means of mutable -//! access to a tracked place (in the concrete domain), this place must be assigned to top (in the -//! abstract domain). The concretization function y can be defined as expected for the constant -//! propagation analysis, although the concrete state of course contains all kinds of non-tracked -//! data. However, by the invariant above, no mutable access to tracked places that are not marked -//! with top may be introduced. +//! - The assignment logic in `State::assign_place_idx` assumes that the places are non-overlapping, +//! or identical. Note that this refers to place expressions, not memory locations. //! -//! Note that we (at least currently) do not differentiate between "this place may assume different -//! values" and "a pointer to this place escaped the analysis". However, we still want to handle -//! assignments to constants as usual for f#. This adds an assumption: Whenever we have an -//! assignment that is captured by the analysis, all mutable access to the underlying place (which -//! is not observable by the analysis) must be invalidated. This is (hopefully) covered by Stacked -//! Borrows. -//! -//! To be continued... +//! - Currently, places that have their reference taken cannot be tracked. Although this would be +//! possible, it has to rely on some aliasing model, which we are not ready to commit to yet. +//! Because of that, we can assume that the only way to change the value behind a tracked place is +//! by direct assignment. use std::fmt::{Debug, Formatter}; use rustc_data_structures::fx::FxHashMap; use rustc_index::vec::IndexVec; -use rustc_middle::mir::tcx::PlaceTy; +use rustc_middle::mir::visit::{MutatingUseContext, PlaceContext, Visitor}; use rustc_middle::mir::*; use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_target::abi::VariantIdx; +use crate::lattice::{HasBottom, HasTop}; use crate::{ - fmt::DebugWithContext, lattice::FlatSet, Analysis, AnalysisDomain, CallReturnPlaces, - JoinSemiLattice, SwitchIntEdgeEffects, + fmt::DebugWithContext, Analysis, AnalysisDomain, CallReturnPlaces, JoinSemiLattice, + SwitchIntEdgeEffects, }; pub trait ValueAnalysis<'tcx> { @@ -87,25 +69,53 @@ fn super_statement(&self, statement: &Statement<'tcx>, state: &mut State { - // FIXME: What to do here? + StatementKind::Intrinsic(box intrinsic) => { + self.handle_intrinsic(intrinsic, state); } StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => { - // It is UB to read from an unitialized or unallocated local. - state.flood(Place::from(*local).as_ref(), self.map()); + // StorageLive leaves the local in an uninitialized state. + // StorageDead makes it UB to access the local afterwards. + state.flood_with(Place::from(*local).as_ref(), self.map(), Self::Value::bottom()); } StatementKind::Deinit(box place) => { - // It is UB to read `uninit` bytes. - state.flood(place.as_ref(), self.map()); + // Deinit makes the place uninitialized. + state.flood_with(place.as_ref(), self.map(), Self::Value::bottom()); + } + StatementKind::Retag(..) => { + // We don't track references. } StatementKind::Nop - | StatementKind::Retag(..) | StatementKind::FakeRead(..) | StatementKind::Coverage(..) | StatementKind::AscribeUserType(..) => (), } } + fn handle_intrinsic( + &self, + intrinsic: &NonDivergingIntrinsic<'tcx>, + state: &mut State, + ) { + self.super_intrinsic(intrinsic, state); + } + + fn super_intrinsic( + &self, + intrinsic: &NonDivergingIntrinsic<'tcx>, + state: &mut State, + ) { + match intrinsic { + NonDivergingIntrinsic::Assume(..) => { + // Could use this, but ignoring it is sound. + } + NonDivergingIntrinsic::CopyNonOverlapping(CopyNonOverlapping { dst, .. }) => { + if let Some(place) = dst.place() { + state.flood(place.as_ref(), self.map()); + } + } + } + } + fn handle_assign( &self, target: Place<'tcx>, @@ -129,7 +139,7 @@ fn handle_rvalue( &self, rvalue: &Rvalue<'tcx>, state: &mut State, - ) -> ValueOrPlaceOrRef { + ) -> ValueOrPlace { self.super_rvalue(rvalue, state) } @@ -137,22 +147,28 @@ fn super_rvalue( &self, rvalue: &Rvalue<'tcx>, state: &mut State, - ) -> ValueOrPlaceOrRef { + ) -> ValueOrPlace { match rvalue { - Rvalue::Use(operand) => self.handle_operand(operand, state).into(), - Rvalue::Ref(_, BorrowKind::Shared, place) => self - .map() - .find(place.as_ref()) - .map(ValueOrPlaceOrRef::Ref) - .unwrap_or(ValueOrPlaceOrRef::Unknown), - Rvalue::Ref(_, _, place) | Rvalue::AddressOf(_, place) => { - state.flood(place.as_ref(), self.map()); - ValueOrPlaceOrRef::Unknown + Rvalue::Use(operand) => self.handle_operand(operand, state), + Rvalue::CopyForDeref(place) => self.handle_operand(&Operand::Copy(*place), state), + Rvalue::Ref(..) | Rvalue::AddressOf(..) => { + // We don't track such places. + ValueOrPlace::top() } - Rvalue::CopyForDeref(place) => { - self.handle_operand(&Operand::Copy(*place), state).into() + Rvalue::Repeat(..) + | Rvalue::ThreadLocalRef(..) + | Rvalue::Len(..) + | Rvalue::Cast(..) + | Rvalue::BinaryOp(..) + | Rvalue::CheckedBinaryOp(..) + | Rvalue::NullaryOp(..) + | Rvalue::UnaryOp(..) + | Rvalue::Discriminant(..) + | Rvalue::Aggregate(..) + | Rvalue::ShallowInitBox(..) => { + // No modification is possible through these r-values. + ValueOrPlace::top() } - _ => ValueOrPlaceOrRef::Unknown, } } @@ -174,11 +190,12 @@ fn super_operand( ValueOrPlace::Value(self.handle_constant(constant, state)) } Operand::Copy(place) | Operand::Move(place) => { - // Do we want to handle moves differently? Could flood place with bottom. + // On move, we would ideally flood the place with bottom. But with the current + // framework this is not possible (similar to `InterpCx::eval_operand`). self.map() .find(place.as_ref()) .map(ValueOrPlace::Place) - .unwrap_or(ValueOrPlace::Unknown) + .unwrap_or(ValueOrPlace::top()) } } } @@ -205,21 +222,29 @@ fn handle_terminator(&self, terminator: &Terminator<'tcx>, state: &mut State, state: &mut State) { + fn super_terminator(&self, terminator: &Terminator<'tcx>, _state: &mut State) { match &terminator.kind { TerminatorKind::Call { .. } | TerminatorKind::InlineAsm { .. } => { // Effect is applied by `handle_call_return`. } - TerminatorKind::Drop { place, .. } => { - // Place can still be accessed after drop, and drop has mutable access to it. - state.flood(place.as_ref(), self.map()); + TerminatorKind::Drop { .. } => { + // We don't track dropped places. } TerminatorKind::DropAndReplace { .. } | TerminatorKind::Yield { .. } => { // They would have an effect, but are not allowed in this phase. bug!("encountered disallowed terminator"); } - _ => { - // The other terminators can be ignored. + TerminatorKind::Goto { .. } + | TerminatorKind::SwitchInt { .. } + | TerminatorKind::Resume + | TerminatorKind::Abort + | TerminatorKind::Return + | TerminatorKind::Unreachable + | TerminatorKind::Assert { .. } + | TerminatorKind::GeneratorDrop + | TerminatorKind::FalseEdge { .. } + | TerminatorKind::FalseUnwind { .. } => { + // These terminators have no effect on the analysis. } } } @@ -280,7 +305,6 @@ fn bottom_value(&self, _body: &Body<'tcx>) -> Self::Domain { fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain) { // The initial state maps all tracked places of argument projections to ⊤ and the rest to ⊥. - // This utilizes that reading from an uninitialized place is UB. assert!(matches!(state.0, StateData::Unreachable)); let values = IndexVec::from_elem_n(T::Value::bottom(), self.0.map().value_count); *state = State(StateData::Reachable(values)); @@ -354,12 +378,31 @@ struct ValueIndex {} ); /// See [`State`]. -#[derive(PartialEq, Eq, Clone, Debug)] +#[derive(PartialEq, Eq, Debug)] enum StateData { Reachable(IndexVec), Unreachable, } +impl Clone for StateData { + fn clone(&self) -> Self { + match self { + Self::Reachable(x) => Self::Reachable(x.clone()), + Self::Unreachable => Self::Unreachable, + } + } + + fn clone_from(&mut self, source: &Self) { + match (&mut *self, source) { + (Self::Reachable(x), Self::Reachable(y)) => { + // We go through `raw` here, because `IndexVec` currently has a naive `clone_from`. + x.raw.clone_from(&y.raw); + } + _ => *self = source.clone(), + } + } +} + /// The dataflow state for an instance of [`ValueAnalysis`]. /// /// Every instance specifies a lattice that represents the possible values of a single tracked @@ -370,10 +413,20 @@ enum StateData { /// reachable state). All operations on unreachable states are ignored. /// /// Flooding means assigning a value (by default `⊤`) to all tracked projections of a given place. -#[derive(PartialEq, Eq, Clone, Debug)] +#[derive(PartialEq, Eq, Debug)] pub struct State(StateData); -impl State { +impl Clone for State { + fn clone(&self) -> Self { + Self(self.0.clone()) + } + + fn clone_from(&mut self, source: &Self) { + self.0.clone_from(&source.0); + } +} + +impl State { pub fn is_reachable(&self) -> bool { matches!(&self.0, StateData::Reachable(_)) } @@ -414,10 +467,14 @@ pub fn flood_idx(&mut self, place: PlaceIndex, map: &Map) { self.flood_idx_with(place, map, V::top()) } - /// This method assumes that the given places are not overlapping, and that we can therefore - /// copy all entries one after another. + /// Copies `source` to `target`, including all tracked places beneath. + /// + /// If `target` contains a place that is not contained in `source`, it will be overwritten with + /// Top. Also, because this will copy all entries one after another, it may only be used for + /// places that are non-overlapping or identical. pub fn assign_place_idx(&mut self, target: PlaceIndex, source: PlaceIndex, map: &Map) { let StateData::Reachable(values) = &mut self.0 else { return }; + // If both places are tracked, we copy the value to the target. If the target is tracked, // but the source is not, we have to invalidate the value in target. If the target is not // tracked, then we don't have to do anything. @@ -439,7 +496,7 @@ pub fn assign_place_idx(&mut self, target: PlaceIndex, source: PlaceIndex, map: } } - pub fn assign(&mut self, target: PlaceRef<'_>, result: ValueOrPlaceOrRef, map: &Map) { + pub fn assign(&mut self, target: PlaceRef<'_>, result: ValueOrPlace, map: &Map) { if let Some(target) = map.find(target) { self.assign_idx(target, result, map); } else { @@ -447,9 +504,9 @@ pub fn assign(&mut self, target: PlaceRef<'_>, result: ValueOrPlaceOrRef, map } } - pub fn assign_idx(&mut self, target: PlaceIndex, result: ValueOrPlaceOrRef, map: &Map) { + pub fn assign_idx(&mut self, target: PlaceIndex, result: ValueOrPlace, map: &Map) { match result { - ValueOrPlaceOrRef::Value(value) => { + ValueOrPlace::Value(value) => { // First flood the target place in case we also track any projections (although // this scenario is currently not well-supported by the API). self.flood_idx(target, map); @@ -458,32 +515,25 @@ pub fn assign_idx(&mut self, target: PlaceIndex, result: ValueOrPlaceOrRef, m values[value_index] = value; } } - ValueOrPlaceOrRef::Place(source) => self.assign_place_idx(target, source, map), - ValueOrPlaceOrRef::Ref(source) => { - let StateData::Reachable(values) = &mut self.0 else { return }; - if let Some(value_index) = map.places[target].value_index { - values[value_index] = V::top(); - } - if let Some(target_deref) = map.apply_elem(target, ProjElem::Deref) { - self.assign_place_idx(target_deref, source, map); - } - } - ValueOrPlaceOrRef::Unknown => { - self.flood_idx(target, map); - } + ValueOrPlace::Place(source) => self.assign_place_idx(target, source, map), } } + /// Retrieve the value stored for a place, or ⊤ if it is not tracked. pub fn get(&self, place: PlaceRef<'_>, map: &Map) -> V { map.find(place).map(|place| self.get_idx(place, map)).unwrap_or(V::top()) } + /// Retrieve the value stored for a place index, or ⊤ if it is not tracked. pub fn get_idx(&self, place: PlaceIndex, map: &Map) -> V { match &self.0 { StateData::Reachable(values) => { map.places[place].value_index.map(|v| values[v].clone()).unwrap_or(V::top()) } - StateData::Unreachable => V::top(), + StateData::Unreachable => { + // Because this is unreachable, we can return any value we want. + V::bottom() + } } } } @@ -501,16 +551,22 @@ fn join(&mut self, other: &Self) -> bool { } } +/// Partial mapping from [`Place`] to [`PlaceIndex`], where some places also have a [`ValueIndex`]. +/// +/// This data structure essentially maintains a tree of places and their projections. Some +/// additional bookkeeping is done, to speed up traversal over this tree: +/// - For iteration, every [`PlaceInfo`] contains an intrusive linked list of its children. +/// - To directly get the child for a specific projection, there is a `projections` map. #[derive(Debug)] pub struct Map { locals: IndexVec>, - projections: FxHashMap<(PlaceIndex, ProjElem), PlaceIndex>, + projections: FxHashMap<(PlaceIndex, TrackElem), PlaceIndex>, places: IndexVec, value_count: usize, } impl Map { - pub fn new() -> Self { + fn new() -> Self { Self { locals: IndexVec::new(), projections: FxHashMap::default(), @@ -519,58 +575,79 @@ pub fn new() -> Self { } } - /// Register all places with suitable types up to a certain derefence depth (to prevent cycles). - pub fn register_with_filter<'tcx>( + /// Returns a map that only tracks places whose type passes the filter. + /// + /// This is currently the only way to create a [`Map`]. The way in which the tracked places are + /// chosen is an implementation detail and may not be relied upon (other than that their type + /// passes the filter). + #[instrument(skip_all, level = "debug")] + pub fn from_filter<'tcx>( + tcx: TyCtxt<'tcx>, + body: &Body<'tcx>, + filter: impl FnMut(Ty<'tcx>) -> bool, + ) -> Self { + let mut map = Self::new(); + let exclude = excluded_locals(body); + map.register_with_filter(tcx, body, filter, &exclude); + debug!("registered {} places ({} nodes in total)", map.value_count, map.places.len()); + map + } + + /// Register all non-excluded places that pass the filter. + fn register_with_filter<'tcx>( &mut self, tcx: TyCtxt<'tcx>, - source: &impl HasLocalDecls<'tcx>, - max_derefs: u32, + body: &Body<'tcx>, mut filter: impl FnMut(Ty<'tcx>) -> bool, + exclude: &IndexVec, ) { + // We use this vector as stack, pushing and popping projections. let mut projection = Vec::new(); - for (local, decl) in source.local_decls().iter_enumerated() { - self.register_with_filter_rec( - tcx, - max_derefs, - local, - &mut projection, - decl.ty, - &mut filter, - ); + for (local, decl) in body.local_decls.iter_enumerated() { + if !exclude[local] { + self.register_with_filter_rec(tcx, local, &mut projection, decl.ty, &mut filter); + } } } + /// Potentially register the (local, projection) place and its fields, recursively. + /// + /// Invariant: The projection must only contain fields. fn register_with_filter_rec<'tcx>( &mut self, tcx: TyCtxt<'tcx>, - max_derefs: u32, local: Local, projection: &mut Vec>, ty: Ty<'tcx>, filter: &mut impl FnMut(Ty<'tcx>) -> bool, ) { - if filter(ty) { - // This might fail if `ty` is not scalar. - let _ = self.register_with_ty(local, projection, ty); - } - if max_derefs > 0 { - if let Some(ty::TypeAndMut { ty, .. }) = ty.builtin_deref(false) { - projection.push(PlaceElem::Deref); - self.register_with_filter_rec(tcx, max_derefs - 1, local, projection, ty, filter); - projection.pop(); + // Note: The framework supports only scalars for now. + if filter(ty) && ty.is_scalar() { + // We know that the projection only contains trackable elements. + let place = self.make_place(local, projection).unwrap(); + + // Allocate a value slot if it doesn't have one. + if self.places[place].value_index.is_none() { + self.places[place].value_index = Some(self.value_count.into()); + self.value_count += 1; } } + + // Recurse with all fields of this place. iter_fields(ty, tcx, |variant, field, ty| { if variant.is_some() { // Downcasts are currently not supported. return; } projection.push(PlaceElem::Field(field, ty)); - self.register_with_filter_rec(tcx, max_derefs, local, projection, ty, filter); + self.register_with_filter_rec(tcx, local, projection, ty, filter); projection.pop(); }); } + /// Tries to add the place to the map, without allocating a value slot. + /// + /// Can fail if the projection contains non-trackable elements. fn make_place<'tcx>( &mut self, local: Local, @@ -582,10 +659,6 @@ fn make_place<'tcx>( // Apply the projection. for &elem in projection { - match elem { - PlaceElem::Downcast(..) => return Err(()), - _ => (), - } let elem = elem.try_into()?; index = *self.projections.entry((index, elem)).or_insert_with(|| { // Prepend new child to the linked list. @@ -599,67 +672,33 @@ fn make_place<'tcx>( Ok(index) } - pub fn register<'tcx>( - &mut self, - local: Local, - projection: &[PlaceElem<'tcx>], - decls: &impl HasLocalDecls<'tcx>, - tcx: TyCtxt<'tcx>, - ) -> Result<(), ()> { - projection - .iter() - .fold(PlaceTy::from_ty(decls.local_decls()[local].ty), |place_ty, &elem| { - place_ty.projection_ty(tcx, elem) - }); - - let place_ty = Place::ty_from(local, projection, decls, tcx); - if place_ty.variant_index.is_some() { - return Err(()); - } - self.register_with_ty(local, projection, place_ty.ty) + /// Returns the number of tracked places, i.e., those for which a value can be stored. + pub fn tracked_places(&self) -> usize { + self.value_count } - fn register_with_ty<'tcx>( - &mut self, - local: Local, - projection: &[PlaceElem<'tcx>], - ty: Ty<'tcx>, - ) -> Result<(), ()> { - if !ty.is_scalar() { - // Currently, only scalar types are allowed, because they are atomic - // and therefore do not require invalidation of parent places. - return Err(()); - } - - let place = self.make_place(local, projection)?; - - // Allocate a value slot if it doesn't have one. - if self.places[place].value_index.is_none() { - self.places[place].value_index = Some(self.value_count.into()); - self.value_count += 1; - } - - Ok(()) - } - - pub fn apply_elem(&self, place: PlaceIndex, elem: ProjElem) -> Option { + /// Applies a single projection element, yielding the corresponding child. + pub fn apply(&self, place: PlaceIndex, elem: TrackElem) -> Option { self.projections.get(&(place, elem)).copied() } + /// Locates the given place, if it exists in the tree. pub fn find(&self, place: PlaceRef<'_>) -> Option { let mut index = *self.locals.get(place.local)?.as_ref()?; for &elem in place.projection { - index = self.apply_elem(index, elem.try_into().ok()?)?; + index = self.apply(index, elem.try_into().ok()?)?; } Some(index) } + /// Iterate over all direct children. pub fn children(&self, parent: PlaceIndex) -> impl Iterator + '_ { Children::new(self, parent) } + /// Invoke a function on the given place and all descendants. pub fn preorder_invoke(&self, root: PlaceIndex, f: &mut impl FnMut(PlaceIndex)) { f(root); for child in self.children(root) { @@ -668,17 +707,27 @@ pub fn preorder_invoke(&self, root: PlaceIndex, f: &mut impl FnMut(PlaceIndex)) } } +/// This is the information tracked for every [`PlaceIndex`] and is stored by [`Map`]. +/// +/// Together, `first_child` and `next_sibling` form an intrusive linked list, which is used to +/// model a tree structure (a replacement for a member like `children: Vec`). #[derive(Debug)] struct PlaceInfo { - next_sibling: Option, - first_child: Option, - /// The projection used to go from parent to this node (only None for root). - proj_elem: Option, + /// We store a [`ValueIndex`] if and only if the placed is tracked by the analysis. value_index: Option, + + /// The projection used to go from parent to this node (only None for root). + proj_elem: Option, + + /// The left-most child. + first_child: Option, + + /// Index of the sibling to the right of this node. + next_sibling: Option, } impl PlaceInfo { - fn new(proj_elem: Option) -> Self { + fn new(proj_elem: Option) -> Self { Self { next_sibling: None, first_child: None, proj_elem, value_index: None } } } @@ -708,71 +757,38 @@ fn next(&mut self) -> Option { } } -// FIXME: See if we can get rid of `Unknown`. +/// Used as the result of an operand or r-value. pub enum ValueOrPlace { Value(V), Place(PlaceIndex), - Unknown, } -pub enum ValueOrPlaceOrRef { - Value(V), - Place(PlaceIndex), - Ref(PlaceIndex), - Unknown, -} - -impl From> for ValueOrPlaceOrRef { - fn from(x: ValueOrPlace) -> Self { - match x { - ValueOrPlace::Value(value) => ValueOrPlaceOrRef::Value(value), - ValueOrPlace::Place(place) => ValueOrPlaceOrRef::Place(place), - ValueOrPlace::Unknown => ValueOrPlaceOrRef::Unknown, - } - } -} - -pub trait HasBottom { - fn bottom() -> Self; -} - -pub trait HasTop { - fn top() -> Self; -} - -impl HasBottom for FlatSet { - fn bottom() -> Self { - Self::Bottom - } -} - -impl HasTop for FlatSet { - fn top() -> Self { - Self::Top +impl ValueOrPlace { + pub fn top() -> Self { + ValueOrPlace::Value(V::top()) } } -/// Currently, we only track places through deref and field projections. +/// The set of projection elements that can be used by a tracked place. /// -/// For now, downcast is not allowed due to aliasing between variants (see #101168). +/// Although only field projections are currently allowed, this could change in the future. #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] -pub enum ProjElem { - Deref, +pub enum TrackElem { Field(Field), } -impl TryFrom> for ProjElem { +impl TryFrom> for TrackElem { type Error = (); fn try_from(value: ProjectionElem) -> Result { match value { - ProjectionElem::Deref => Ok(ProjElem::Deref), - ProjectionElem::Field(field, _) => Ok(ProjElem::Field(field)), + ProjectionElem::Field(field, _) => Ok(TrackElem::Field(field)), _ => Err(()), } } } +/// Invokes `f` on all direct fields of `ty`. fn iter_fields<'tcx>( ty: Ty<'tcx>, tcx: TyCtxt<'tcx>, @@ -785,13 +801,17 @@ fn iter_fields<'tcx>( } } ty::Adt(def, substs) => { + if def.is_union() { + return; + } for (v_index, v_def) in def.variants().iter_enumerated() { + let variant = if def.is_struct() { None } else { Some(v_index) }; for (f_index, f_def) in v_def.fields.iter().enumerate() { let field_ty = f_def.ty(tcx, substs); let field_ty = tcx .try_normalize_erasing_regions(ty::ParamEnv::reveal_all(), field_ty) .unwrap_or(field_ty); - f(Some(v_index), f_index.into(), field_ty); + f(variant, f_index.into(), field_ty); } } } @@ -802,6 +822,59 @@ fn iter_fields<'tcx>( } } +/// Returns all locals with projections that have their reference or address taken. +fn excluded_locals<'tcx>(body: &Body<'tcx>) -> IndexVec { + struct Collector { + result: IndexVec, + } + + impl<'tcx> Visitor<'tcx> for Collector { + fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, _location: Location) { + if context.is_borrow() + || context.is_address_of() + || context.is_drop() + || context == PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) + { + // A pointer to a place could be used to access other places with the same local, + // hence we have to exclude the local completely. + self.result[place.local] = true; + } + } + } + + let mut collector = Collector { result: IndexVec::from_elem(false, &body.local_decls) }; + collector.visit_body(body); + collector.result +} + +/// This is used to visualize the dataflow analysis. +impl<'tcx, T> DebugWithContext> for State +where + T: ValueAnalysis<'tcx>, + T::Value: Debug, +{ + fn fmt_with(&self, ctxt: &ValueAnalysisWrapper, f: &mut Formatter<'_>) -> std::fmt::Result { + match &self.0 { + StateData::Reachable(values) => debug_with_context(values, None, ctxt.0.map(), f), + StateData::Unreachable => write!(f, "unreachable"), + } + } + + fn fmt_diff_with( + &self, + old: &Self, + ctxt: &ValueAnalysisWrapper, + f: &mut Formatter<'_>, + ) -> std::fmt::Result { + match (&self.0, &old.0) { + (StateData::Reachable(this), StateData::Reachable(old)) => { + debug_with_context(this, Some(old), ctxt.0.map(), f) + } + _ => Ok(()), // Consider printing something here. + } + } +} + fn debug_with_context_rec( place: PlaceIndex, place_str: &str, @@ -825,8 +898,7 @@ fn debug_with_context_rec( for child in map.children(place) { let info_elem = map.places[child].proj_elem.unwrap(); let child_place_str = match info_elem { - ProjElem::Deref => format!("*{}", place_str), - ProjElem::Field(field) => { + TrackElem::Field(field) => { if place_str.starts_with("*") { format!("({}).{}", place_str, field.index()) } else { @@ -853,30 +925,3 @@ fn debug_with_context( } Ok(()) } - -impl<'tcx, T> DebugWithContext> for State -where - T: ValueAnalysis<'tcx>, - T::Value: Debug, -{ - fn fmt_with(&self, ctxt: &ValueAnalysisWrapper, f: &mut Formatter<'_>) -> std::fmt::Result { - match &self.0 { - StateData::Reachable(values) => debug_with_context(values, None, ctxt.0.map(), f), - StateData::Unreachable => write!(f, "unreachable"), - } - } - - fn fmt_diff_with( - &self, - old: &Self, - ctxt: &ValueAnalysisWrapper, - f: &mut Formatter<'_>, - ) -> std::fmt::Result { - match (&self.0, &old.0) { - (StateData::Reachable(this), StateData::Reachable(old)) => { - debug_with_context(this, Some(old), ctxt.0.map(), f) - } - _ => Ok(()), // Consider printing something here. - } - } -}