X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=compiler%2Frustc_mir_dataflow%2Fsrc%2Fvalue_analysis.rs;h=db4b0a3deda9dba74aea18e8e184eac255f55b70;hb=becc24a23aed2639db3b78acd93ec6d553898583;hp=1dcea430a0f6794fbf14f900be9e7f41eb74fe30;hpb=4f9c30fb676482a5148f28c0728b5280246a9886;p=rust.git diff --git a/compiler/rustc_mir_dataflow/src/value_analysis.rs b/compiler/rustc_mir_dataflow/src/value_analysis.rs index 1dcea430a0f..db4b0a3deda 100644 --- a/compiler/rustc_mir_dataflow/src/value_analysis.rs +++ b/compiler/rustc_mir_dataflow/src/value_analysis.rs @@ -1,26 +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. The set of tracked places cannot be -//! changed during the analysis. +//! 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. +//! +//! 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. +//! +//! +//! # Notes +//! +//! - 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. +//! +//! - 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. +//! +//! - 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::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> { @@ -41,24 +65,57 @@ fn super_statement(&self, statement: &Statement<'tcx>, state: &mut State { - // Could tread this as writing a constant to a pseudo-place. + // Could treat this as writing a constant to a pseudo-place. + // But discriminants are currently not tracked, so we do nothing. + // Related: https://github.com/rust-lang/unsafe-code-guidelines/issues/84 + } + StatementKind::Intrinsic(box intrinsic) => { + self.handle_intrinsic(intrinsic, state); } - StatementKind::CopyNonOverlapping(..) => { - // FIXME: What to do here? + StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => { + // 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::StorageLive(..) - | StatementKind::StorageDead(..) - | StatementKind::Deinit(_) => { - // Could perhaps use these. + StatementKind::Deinit(box place) => { + // 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>, @@ -74,28 +131,8 @@ fn super_assign( rvalue: &Rvalue<'tcx>, state: &mut State, ) { - match rvalue { - Rvalue::Ref(_, BorrowKind::Shared, place) => { - let target_deref = self - .map() - .find(target.as_ref()) - .and_then(|target| self.map().apply_elem(target, ProjElem::Deref)); - let place = self.map().find(place.as_ref()); - match (target_deref, place) { - (Some(target_deref), Some(place)) => { - state.assign_idx(target_deref, ValueOrPlace::Place(place), self.map()) - } - _ => (), - } - } - Rvalue::Ref(_, _, place) | Rvalue::AddressOf(_, place) => { - state.flood(place.as_ref(), self.map(), Self::Value::top()); - } - _ => { - let result = self.handle_rvalue(rvalue, state); - state.assign(target.as_ref(), result, self.map()); - } - } + let result = self.handle_rvalue(rvalue, state); + state.assign(target.as_ref(), result, self.map()); } fn handle_rvalue( @@ -115,11 +152,22 @@ fn super_rvalue( Rvalue::Use(operand) => self.handle_operand(operand, state), Rvalue::CopyForDeref(place) => self.handle_operand(&Operand::Copy(*place), state), Rvalue::Ref(..) | Rvalue::AddressOf(..) => { - bug!("this rvalue must be handled by handle_assign() or super_assign()") + // We don't track such places. + ValueOrPlace::top() } - _ => { - // FIXME: Check that other Rvalues really have no side-effect. - ValueOrPlace::Unknown + 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() } } } @@ -142,11 +190,12 @@ fn super_operand( ValueOrPlace::Value(self.handle_constant(constant, state)) } Operand::Copy(place) | Operand::Move(place) => { - // Do want want to handle moves different? 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()) } } } @@ -167,11 +216,38 @@ fn super_constant( Self::Value::top() } + /// The effect of a successful function call return should not be + /// applied here, see [`Analysis::apply_terminator_effect`]. fn handle_terminator(&self, terminator: &Terminator<'tcx>, state: &mut State) { self.super_terminator(terminator, state) } - fn super_terminator(&self, _terminator: &Terminator<'tcx>, _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 { .. } => { + // 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"); + } + 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. + } + } + } fn handle_call_return( &self, @@ -187,7 +263,7 @@ fn super_call_return( state: &mut State, ) { return_places.for_each(|place| { - state.flood(place.as_ref(), self.map(), Self::Value::top()); + state.flood(place.as_ref(), self.map()); }) } @@ -224,12 +300,16 @@ impl<'tcx, T: ValueAnalysis<'tcx>> AnalysisDomain<'tcx> for ValueAnalysisWrapper const NAME: &'static str = T::NAME; fn bottom_value(&self, _body: &Body<'tcx>) -> Self::Domain { - State(IndexVec::from_elem_n(T::Value::bottom(), self.0.map().value_count)) + State(StateData::Unreachable) } 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 ⊥. + 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)); for arg in body.args_iter() { - state.flood(PlaceRef { local: arg, projection: &[] }, self.0.map(), T::Value::top()); + state.flood(PlaceRef { local: arg, projection: &[] }, self.0.map()); } } } @@ -244,7 +324,9 @@ fn apply_statement_effect( statement: &Statement<'tcx>, _location: Location, ) { - self.0.handle_statement(statement, state); + if state.is_reachable() { + self.0.handle_statement(statement, state); + } } fn apply_terminator_effect( @@ -253,7 +335,9 @@ fn apply_terminator_effect( terminator: &Terminator<'tcx>, _location: Location, ) { - self.0.handle_terminator(terminator, state); + if state.is_reachable() { + self.0.handle_terminator(terminator, state); + } } fn apply_call_return_effect( @@ -262,7 +346,9 @@ fn apply_call_return_effect( _block: BasicBlock, return_places: crate::CallReturnPlaces<'_, 'tcx>, ) { - self.0.handle_call_return(return_places, state) + if state.is_reachable() { + self.0.handle_call_return(return_places, state) + } } fn apply_switch_int_edge_effects( @@ -271,55 +357,141 @@ fn apply_switch_int_edge_effects( discr: &Operand<'tcx>, apply_edge_effects: &mut impl SwitchIntEdgeEffects, ) { + // FIXME: Dataflow framework provides no access to current state here. self.0.handle_switch_int(discr, apply_edge_effects) } } rustc_index::newtype_index!( + /// This index uniquely identifies a place. + /// + /// Not every place has a `PlaceIndex`, and not every `PlaceIndex` correspondends to a tracked + /// place. However, every tracked place and all places along its projection have a `PlaceIndex`. pub struct PlaceIndex {} ); rustc_index::newtype_index!( + /// This index uniquely identifies a tracked place and therefore a slot in [`State`]. + /// + /// It is an implementation detail of this module. struct ValueIndex {} ); -#[derive(PartialEq, Eq, Clone, Debug)] -pub struct State(IndexVec); +/// See [`State`]. +#[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 +/// place. If we call this lattice `V` and set set of tracked places `P`, then a [`State`] is an +/// element of `{unreachable} ∪ (P -> V)`. This again forms a lattice, where the bottom element is +/// `unreachable` and the top element is the mapping `p ↦ ⊤`. Note that the mapping `p ↦ ⊥` is not +/// the bottom element (because joining an unreachable and any other reachable state yields a +/// 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, Debug)] +pub struct State(StateData); + +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(_)) + } -impl State { - pub fn flood_all(&mut self, value: V) { - self.0.raw.fill(value); + pub fn mark_unreachable(&mut self) { + self.0 = StateData::Unreachable; } - pub fn flood(&mut self, place: PlaceRef<'_>, map: &Map, value: V) { + pub fn flood_all(&mut self) { + self.flood_all_with(V::top()) + } + + pub fn flood_all_with(&mut self, value: V) { + let StateData::Reachable(values) = &mut self.0 else { return }; + values.raw.fill(value); + } + + pub fn flood_with(&mut self, place: PlaceRef<'_>, map: &Map, value: V) { if let Some(root) = map.find(place) { - self.flood_idx(root, map, value); + self.flood_idx_with(root, map, value); } } - pub fn flood_idx(&mut self, place: PlaceIndex, map: &Map, value: V) { + pub fn flood(&mut self, place: PlaceRef<'_>, map: &Map) { + self.flood_with(place, map, V::top()) + } + + pub fn flood_idx_with(&mut self, place: PlaceIndex, map: &Map, value: V) { + let StateData::Reachable(values) = &mut self.0 else { return }; map.preorder_invoke(place, &mut |place| { if let Some(vi) = map.places[place].value_index { - self.0[vi] = value.clone(); + values[vi] = value.clone(); } }); } + pub fn flood_idx(&mut self, place: PlaceIndex, map: &Map) { + self.flood_idx_with(place, map, V::top()) + } + + /// 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. if let Some(target_value) = map.places[target].value_index { if let Some(source_value) = map.places[source].value_index { - self.0[target_value] = self.0[source_value].clone(); + values[target_value] = values[source_value].clone(); } else { - self.0[target_value] = V::top(); + values[target_value] = V::top(); } } for target_child in map.children(target) { - // Try to find corresponding child in source. + // Try to find corresponding child and recurse. Reasoning is similar as above. let projection = map.places[target_child].proj_elem.unwrap(); if let Some(source_child) = map.projections.get(&(source, projection)) { self.assign_place_idx(target_child, *source_child, map); } else { - self.flood_idx(target_child, map, V::top()); + self.flood_idx(target_child, map); } } } @@ -327,49 +499,74 @@ pub fn assign_place_idx(&mut self, target: PlaceIndex, source: PlaceIndex, 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 { + // We don't track this place nor any projections, assignment can be ignored. } } pub fn assign_idx(&mut self, target: PlaceIndex, result: ValueOrPlace, map: &Map) { match result { ValueOrPlace::Value(value) => { - // FIXME: What if not all tracked projections are overwritten? Can this happen? + // 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); + let StateData::Reachable(values) = &mut self.0 else { return }; if let Some(value_index) = map.places[target].value_index { - self.0[value_index] = value; + values[value_index] = value; } } ValueOrPlace::Place(source) => self.assign_place_idx(target, source, map), - ValueOrPlace::Unknown => { - self.flood_idx(target, map, V::top()); - } } } + /// 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 { - map.places[place].value_index.map(|v| self.0[v].clone()).unwrap_or(V::top()) + match &self.0 { + StateData::Reachable(values) => { + map.places[place].value_index.map(|v| values[v].clone()).unwrap_or(V::top()) + } + StateData::Unreachable => { + // Because this is unreachable, we can return any value we want. + V::bottom() + } + } } } -impl JoinSemiLattice for State { +impl JoinSemiLattice for State { fn join(&mut self, other: &Self) -> bool { - self.0.join(&other.0) + match (&mut self.0, &other.0) { + (_, StateData::Unreachable) => false, + (StateData::Unreachable, _) => { + *self = other.clone(); + true + } + (StateData::Reachable(this), StateData::Reachable(other)) => this.join(other), + } } } +/// 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(), @@ -378,65 +575,84 @@ 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) { - self.register(local, projection) - .expect("projection should only contain convertible elements"); - } - 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 let Some(variant) = variant { - projection.push(PlaceElem::Downcast(None, variant)); + 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(); - if variant.is_some() { - projection.pop(); - } }); } - pub fn register<'tcx>( + /// 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, projection: &[PlaceElem<'tcx>], - ) -> Result<(), ()> { + ) -> Result { // Get the base index of the local. let mut index = *self.locals.get_or_insert_with(local, || self.places.push(PlaceInfo::new(None))); @@ -453,33 +669,36 @@ pub fn register<'tcx>( }); } - // Allocate a value slot if it doesn't have one. - if self.places[index].value_index.is_none() { - self.places[index].value_index = Some(self.value_count.into()); - self.value_count += 1; - } + Ok(index) + } - Ok(()) + /// 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 } - 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) { @@ -488,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 } } } @@ -528,53 +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 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()) } } +/// The set of projection elements that can be used by a tracked place. +/// +/// 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), - Downcast(VariantIdx), } -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::Downcast(_, variant) => Ok(ProjElem::Downcast(variant)), + 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>, @@ -587,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 = tcx.normalize_erasing_regions( - ty::ParamEnv::reveal_all(), - f_def.ty(tcx, substs), - ); - f(Some(v_index), f_index.into(), field_ty); + 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(variant, f_index.into(), field_ty); } } } @@ -604,21 +822,74 @@ 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, - new: &State, - old: Option<&State>, + new: &IndexVec, + old: Option<&IndexVec>, map: &Map, f: &mut Formatter<'_>, ) -> std::fmt::Result { if let Some(value) = map.places[place].value_index { match old { - None => writeln!(f, "{}: {:?}", place_str, new.0[value])?, + None => writeln!(f, "{}: {:?}", place_str, new[value])?, Some(old) => { - if new.0[value] != old.0[value] { - writeln!(f, "\u{001f}-{}: {:?}", place_str, old.0[value])?; - writeln!(f, "\u{001f}+{}: {:?}", place_str, new.0[value])?; + if new[value] != old[value] { + writeln!(f, "\u{001f}-{}: {:?}", place_str, old[value])?; + writeln!(f, "\u{001f}+{}: {:?}", place_str, new[value])?; } } } @@ -627,15 +898,13 @@ 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 { format!("{}.{}", place_str, field.index()) } } - ProjElem::Downcast(variant) => format!("({} as #{})", place_str, variant.index()), }; debug_with_context_rec(child, &child_place_str, new, old, map, f)?; } @@ -644,8 +913,8 @@ fn debug_with_context_rec( } fn debug_with_context( - new: &State, - old: Option<&State>, + new: &IndexVec, + old: Option<&IndexVec>, map: &Map, f: &mut Formatter<'_>, ) -> std::fmt::Result { @@ -656,22 +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 { - debug_with_context(self, None, ctxt.0.map(), f) - } - - fn fmt_diff_with( - &self, - old: &Self, - ctxt: &ValueAnalysisWrapper, - f: &mut Formatter<'_>, - ) -> std::fmt::Result { - debug_with_context(self, Some(old), ctxt.0.map(), f) - } -}