diff options
Diffstat (limited to 'compiler/rustc_mir_dataflow/src')
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/elaborate_drops.rs | 7 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/engine.rs | 9 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/graphviz.rs | 5 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/lattice.rs | 34 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/impls/init_locals.rs | 122 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/impls/mod.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/lib.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/value_analysis.rs | 927 |
8 files changed, 970 insertions, 137 deletions
diff --git a/compiler/rustc_mir_dataflow/src/elaborate_drops.rs b/compiler/rustc_mir_dataflow/src/elaborate_drops.rs index 23403628c..ce87a1916 100644 --- a/compiler/rustc_mir_dataflow/src/elaborate_drops.rs +++ b/compiler/rustc_mir_dataflow/src/elaborate_drops.rs @@ -407,9 +407,8 @@ where self.drop_ladder(fields, succ, unwind).0 } + #[instrument(level = "debug", ret)] fn open_drop_for_box(&mut self, adt: ty::AdtDef<'tcx>, substs: SubstsRef<'tcx>) -> BasicBlock { - debug!("open_drop_for_box({:?}, {:?}, {:?})", self, adt, substs); - // drop glue is sent straight to codegen // box cannot be directly dereferenced let unique_ty = adt.non_enum_variant().fields[0].ty(self.tcx(), substs); @@ -431,8 +430,8 @@ where self.drop_subpath(interior, interior_path, succ, unwind_succ) } + #[instrument(level = "debug", ret)] fn open_drop_for_adt(&mut self, adt: ty::AdtDef<'tcx>, substs: SubstsRef<'tcx>) -> BasicBlock { - debug!("open_drop_for_adt({:?}, {:?}, {:?})", self, adt, substs); if adt.variants().is_empty() { return self.elaborator.patch().new_block(BasicBlockData { statements: vec![], @@ -616,7 +615,7 @@ where let drop_trait = tcx.require_lang_item(LangItem::Drop, None); let drop_fn = tcx.associated_item_def_ids(drop_trait)[0]; let ty = self.place_ty(self.place); - let substs = tcx.mk_substs_trait(ty, &[]); + let substs = tcx.mk_substs_trait(ty, []); let ref_ty = tcx.mk_ref(tcx.lifetimes.re_erased, ty::TypeAndMut { ty, mutbl: hir::Mutability::Mut }); diff --git a/compiler/rustc_mir_dataflow/src/framework/engine.rs b/compiler/rustc_mir_dataflow/src/framework/engine.rs index bc75645e7..6ddbe69e1 100644 --- a/compiler/rustc_mir_dataflow/src/framework/engine.rs +++ b/compiler/rustc_mir_dataflow/src/framework/engine.rs @@ -294,14 +294,7 @@ where None if tcx.sess.opts.unstable_opts.dump_mir_dataflow && dump_enabled(tcx, A::NAME, def_id) => { - create_dump_file( - tcx, - ".dot", - None, - A::NAME, - &pass_name.unwrap_or("-----"), - body.source, - )? + create_dump_file(tcx, ".dot", false, A::NAME, &pass_name.unwrap_or("-----"), body)? } _ => return Ok(()), diff --git a/compiler/rustc_mir_dataflow/src/framework/graphviz.rs b/compiler/rustc_mir_dataflow/src/framework/graphviz.rs index 579fe68a1..c9d5601f2 100644 --- a/compiler/rustc_mir_dataflow/src/framework/graphviz.rs +++ b/compiler/rustc_mir_dataflow/src/framework/graphviz.rs @@ -475,7 +475,10 @@ where r#"<td colspan="{colspan}" {fmt} align="left">{state}</td>"#, colspan = this.style.num_state_columns(), fmt = fmt, - state = format!("{:?}", DebugWithAdapter { this: state, ctxt: analysis }), + state = dot::escape_html(&format!( + "{:?}", + DebugWithAdapter { this: state, ctxt: analysis } + )), ) }) } diff --git a/compiler/rustc_mir_dataflow/src/framework/lattice.rs b/compiler/rustc_mir_dataflow/src/framework/lattice.rs index d6b89eb82..f0e75c53e 100644 --- a/compiler/rustc_mir_dataflow/src/framework/lattice.rs +++ b/compiler/rustc_mir_dataflow/src/framework/lattice.rs @@ -73,6 +73,16 @@ pub trait MeetSemiLattice: Eq { fn meet(&mut self, other: &Self) -> bool; } +/// A set that has a "bottom" element, which is less than or equal to any other element. +pub trait HasBottom { + fn bottom() -> Self; +} + +/// A set that has a "top" element, which is greater than or equal to any other element. +pub trait HasTop { + fn top() -> Self; +} + /// A `bool` is a "two-point" lattice with `true` as the top element and `false` as the bottom: /// /// ```text @@ -102,6 +112,18 @@ impl MeetSemiLattice for bool { } } +impl HasBottom for bool { + fn bottom() -> Self { + false + } +} + +impl HasTop for bool { + fn top() -> Self { + true + } +} + /// A tuple (or list) of lattices is itself a lattice whose least upper bound is the concatenation /// of the least upper bounds of each element of the tuple (or list). /// @@ -250,3 +272,15 @@ impl<T: Clone + Eq> MeetSemiLattice for FlatSet<T> { true } } + +impl<T> HasBottom for FlatSet<T> { + fn bottom() -> Self { + Self::Bottom + } +} + +impl<T> HasTop for FlatSet<T> { + fn top() -> Self { + Self::Top + } +} diff --git a/compiler/rustc_mir_dataflow/src/impls/init_locals.rs b/compiler/rustc_mir_dataflow/src/impls/init_locals.rs deleted file mode 100644 index 83ce4c44b..000000000 --- a/compiler/rustc_mir_dataflow/src/impls/init_locals.rs +++ /dev/null @@ -1,122 +0,0 @@ -//! A less precise version of `MaybeInitializedPlaces` whose domain is entire locals. -//! -//! A local will be maybe initialized if *any* projections of that local might be initialized. - -use crate::{CallReturnPlaces, GenKill}; - -use rustc_index::bit_set::BitSet; -use rustc_middle::mir::visit::{PlaceContext, Visitor}; -use rustc_middle::mir::{self, BasicBlock, Local, Location}; - -pub struct MaybeInitializedLocals; - -impl<'tcx> crate::AnalysisDomain<'tcx> for MaybeInitializedLocals { - type Domain = BitSet<Local>; - - const NAME: &'static str = "maybe_init_locals"; - - fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain { - // bottom = uninit - BitSet::new_empty(body.local_decls.len()) - } - - fn initialize_start_block(&self, body: &mir::Body<'tcx>, entry_set: &mut Self::Domain) { - // Function arguments are initialized to begin with. - for arg in body.args_iter() { - entry_set.insert(arg); - } - } -} - -impl<'tcx> crate::GenKillAnalysis<'tcx> for MaybeInitializedLocals { - type Idx = Local; - - fn statement_effect( - &self, - trans: &mut impl GenKill<Self::Idx>, - statement: &mir::Statement<'tcx>, - loc: Location, - ) { - TransferFunction { trans }.visit_statement(statement, loc) - } - - fn terminator_effect( - &self, - trans: &mut impl GenKill<Self::Idx>, - terminator: &mir::Terminator<'tcx>, - loc: Location, - ) { - TransferFunction { trans }.visit_terminator(terminator, loc) - } - - fn call_return_effect( - &self, - trans: &mut impl GenKill<Self::Idx>, - _block: BasicBlock, - return_places: CallReturnPlaces<'_, 'tcx>, - ) { - return_places.for_each(|place| trans.gen(place.local)); - } - - /// See `Analysis::apply_yield_resume_effect`. - fn yield_resume_effect( - &self, - trans: &mut impl GenKill<Self::Idx>, - _resume_block: BasicBlock, - resume_place: mir::Place<'tcx>, - ) { - trans.gen(resume_place.local) - } -} - -struct TransferFunction<'a, T> { - trans: &'a mut T, -} - -impl<T> Visitor<'_> for TransferFunction<'_, T> -where - T: GenKill<Local>, -{ - // FIXME: Using `visit_local` here is a bug. For example, on `move _5.field` we mark `_5` as - // deinitialized, although clearly it is only partially deinitialized. This analysis is not - // actually used anywhere at the moment, so this is not critical, but this does need to be fixed - // before it starts being used again. - fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) { - use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, NonUseContext}; - match context { - // These are handled specially in `call_return_effect` and `yield_resume_effect`. - PlaceContext::MutatingUse( - MutatingUseContext::Call - | MutatingUseContext::AsmOutput - | MutatingUseContext::Yield, - ) => {} - - // If it's deinitialized, it's no longer init - PlaceContext::MutatingUse(MutatingUseContext::Deinit) => self.trans.kill(local), - - // Otherwise, when a place is mutated, we must consider it possibly initialized. - PlaceContext::MutatingUse(_) => self.trans.gen(local), - - // If the local is moved out of, or if it gets marked `StorageDead`, consider it no - // longer initialized. - PlaceContext::NonUse(NonUseContext::StorageDead) - | PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) => self.trans.kill(local), - - // All other uses do not affect this analysis. - PlaceContext::NonUse( - NonUseContext::StorageLive - | NonUseContext::AscribeUserTy - | NonUseContext::VarDebugInfo, - ) - | PlaceContext::NonMutatingUse( - NonMutatingUseContext::Inspect - | NonMutatingUseContext::Copy - | NonMutatingUseContext::SharedBorrow - | NonMutatingUseContext::ShallowBorrow - | NonMutatingUseContext::UniqueBorrow - | NonMutatingUseContext::AddressOf - | NonMutatingUseContext::Projection, - ) => {} - } - } -} diff --git a/compiler/rustc_mir_dataflow/src/impls/mod.rs b/compiler/rustc_mir_dataflow/src/impls/mod.rs index fd1e49277..bc31ec42b 100644 --- a/compiler/rustc_mir_dataflow/src/impls/mod.rs +++ b/compiler/rustc_mir_dataflow/src/impls/mod.rs @@ -19,13 +19,11 @@ use crate::{drop_flag_effects, on_all_children_bits}; use crate::{lattice, AnalysisDomain, GenKill, GenKillAnalysis}; mod borrowed_locals; -mod init_locals; mod liveness; mod storage_liveness; pub use self::borrowed_locals::borrowed_locals; pub use self::borrowed_locals::MaybeBorrowedLocals; -pub use self::init_locals::MaybeInitializedLocals; pub use self::liveness::MaybeLiveLocals; pub use self::liveness::MaybeTransitiveLiveLocals; pub use self::storage_liveness::{MaybeRequiresStorage, MaybeStorageLive}; diff --git a/compiler/rustc_mir_dataflow/src/lib.rs b/compiler/rustc_mir_dataflow/src/lib.rs index b471d04fd..7f40cfca3 100644 --- a/compiler/rustc_mir_dataflow/src/lib.rs +++ b/compiler/rustc_mir_dataflow/src/lib.rs @@ -41,6 +41,7 @@ pub mod move_paths; pub mod rustc_peek; pub mod storage; pub mod un_derefer; +pub mod value_analysis; pub(crate) mod indexes { pub(crate) use super::move_paths::MovePathIndex; diff --git a/compiler/rustc_mir_dataflow/src/value_analysis.rs b/compiler/rustc_mir_dataflow/src/value_analysis.rs new file mode 100644 index 000000000..7df011422 --- /dev/null +++ b/compiler/rustc_mir_dataflow/src/value_analysis.rs @@ -0,0 +1,927 @@ +//! This module provides a framework on top of the normal MIR dataflow framework to simplify the +//! 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 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, Analysis, AnalysisDomain, CallReturnPlaces, JoinSemiLattice, + SwitchIntEdgeEffects, +}; + +pub trait ValueAnalysis<'tcx> { + /// For each place of interest, the analysis tracks a value of the given type. + type Value: Clone + JoinSemiLattice + HasBottom + HasTop; + + const NAME: &'static str; + + fn map(&self) -> ⤅ + + fn handle_statement(&self, statement: &Statement<'tcx>, state: &mut State<Self::Value>) { + self.super_statement(statement, state) + } + + fn super_statement(&self, statement: &Statement<'tcx>, state: &mut State<Self::Value>) { + match &statement.kind { + StatementKind::Assign(box (place, rvalue)) => { + self.handle_assign(*place, rvalue, state); + } + StatementKind::SetDiscriminant { .. } => { + // 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::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::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::FakeRead(..) + | StatementKind::Coverage(..) + | StatementKind::AscribeUserType(..) => (), + } + } + + fn handle_intrinsic( + &self, + intrinsic: &NonDivergingIntrinsic<'tcx>, + state: &mut State<Self::Value>, + ) { + self.super_intrinsic(intrinsic, state); + } + + fn super_intrinsic( + &self, + intrinsic: &NonDivergingIntrinsic<'tcx>, + state: &mut State<Self::Value>, + ) { + 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>, + rvalue: &Rvalue<'tcx>, + state: &mut State<Self::Value>, + ) { + self.super_assign(target, rvalue, state) + } + + fn super_assign( + &self, + target: Place<'tcx>, + rvalue: &Rvalue<'tcx>, + state: &mut State<Self::Value>, + ) { + let result = self.handle_rvalue(rvalue, state); + state.assign(target.as_ref(), result, self.map()); + } + + fn handle_rvalue( + &self, + rvalue: &Rvalue<'tcx>, + state: &mut State<Self::Value>, + ) -> ValueOrPlace<Self::Value> { + self.super_rvalue(rvalue, state) + } + + fn super_rvalue( + &self, + rvalue: &Rvalue<'tcx>, + state: &mut State<Self::Value>, + ) -> ValueOrPlace<Self::Value> { + match rvalue { + 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::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() + } + } + } + + fn handle_operand( + &self, + operand: &Operand<'tcx>, + state: &mut State<Self::Value>, + ) -> ValueOrPlace<Self::Value> { + self.super_operand(operand, state) + } + + fn super_operand( + &self, + operand: &Operand<'tcx>, + state: &mut State<Self::Value>, + ) -> ValueOrPlace<Self::Value> { + match operand { + Operand::Constant(box constant) => { + ValueOrPlace::Value(self.handle_constant(constant, state)) + } + Operand::Copy(place) | Operand::Move(place) => { + // 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::top()) + } + } + } + + fn handle_constant( + &self, + constant: &Constant<'tcx>, + state: &mut State<Self::Value>, + ) -> Self::Value { + self.super_constant(constant, state) + } + + fn super_constant( + &self, + _constant: &Constant<'tcx>, + _state: &mut State<Self::Value>, + ) -> Self::Value { + 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::Value>) { + self.super_terminator(terminator, state) + } + + fn super_terminator(&self, terminator: &Terminator<'tcx>, _state: &mut State<Self::Value>) { + 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, + return_places: CallReturnPlaces<'_, 'tcx>, + state: &mut State<Self::Value>, + ) { + self.super_call_return(return_places, state) + } + + fn super_call_return( + &self, + return_places: CallReturnPlaces<'_, 'tcx>, + state: &mut State<Self::Value>, + ) { + return_places.for_each(|place| { + state.flood(place.as_ref(), self.map()); + }) + } + + fn handle_switch_int( + &self, + discr: &Operand<'tcx>, + apply_edge_effects: &mut impl SwitchIntEdgeEffects<State<Self::Value>>, + ) { + self.super_switch_int(discr, apply_edge_effects) + } + + fn super_switch_int( + &self, + _discr: &Operand<'tcx>, + _apply_edge_effects: &mut impl SwitchIntEdgeEffects<State<Self::Value>>, + ) { + } + + fn wrap(self) -> ValueAnalysisWrapper<Self> + where + Self: Sized, + { + ValueAnalysisWrapper(self) + } +} + +pub struct ValueAnalysisWrapper<T>(pub T); + +impl<'tcx, T: ValueAnalysis<'tcx>> AnalysisDomain<'tcx> for ValueAnalysisWrapper<T> { + type Domain = State<T::Value>; + + type Direction = crate::Forward; + + const NAME: &'static str = T::NAME; + + fn bottom_value(&self, _body: &Body<'tcx>) -> Self::Domain { + 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()); + } + } +} + +impl<'tcx, T> Analysis<'tcx> for ValueAnalysisWrapper<T> +where + T: ValueAnalysis<'tcx>, +{ + fn apply_statement_effect( + &self, + state: &mut Self::Domain, + statement: &Statement<'tcx>, + _location: Location, + ) { + if state.is_reachable() { + self.0.handle_statement(statement, state); + } + } + + fn apply_terminator_effect( + &self, + state: &mut Self::Domain, + terminator: &Terminator<'tcx>, + _location: Location, + ) { + if state.is_reachable() { + self.0.handle_terminator(terminator, state); + } + } + + fn apply_call_return_effect( + &self, + state: &mut Self::Domain, + _block: BasicBlock, + return_places: crate::CallReturnPlaces<'_, 'tcx>, + ) { + if state.is_reachable() { + self.0.handle_call_return(return_places, state) + } + } + + fn apply_switch_int_edge_effects( + &self, + _block: BasicBlock, + discr: &Operand<'tcx>, + apply_edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>, + ) { + // 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 {} +); + +/// See [`State`]. +#[derive(PartialEq, Eq, Debug)] +enum StateData<V> { + Reachable(IndexVec<ValueIndex, V>), + Unreachable, +} + +impl<V: Clone> Clone for StateData<V> { + 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 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<V>(StateData<V>); + +impl<V: Clone> Clone for State<V> { + fn clone(&self) -> Self { + Self(self.0.clone()) + } + + fn clone_from(&mut self, source: &Self) { + self.0.clone_from(&source.0); + } +} + +impl<V: Clone + HasTop + HasBottom> State<V> { + pub fn is_reachable(&self) -> bool { + matches!(&self.0, StateData::Reachable(_)) + } + + pub fn mark_unreachable(&mut self) { + self.0 = StateData::Unreachable; + } + + 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_with(root, map, value); + } + } + + 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 { + 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 { + values[target_value] = values[source_value].clone(); + } else { + values[target_value] = V::top(); + } + } + for target_child in map.children(target) { + // 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); + } + } + } + + pub fn assign(&mut self, target: PlaceRef<'_>, result: ValueOrPlace<V>, 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<V>, map: &Map) { + match result { + 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); + let StateData::Reachable(values) = &mut self.0 else { return }; + if let Some(value_index) = map.places[target].value_index { + values[value_index] = value; + } + } + 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 => { + // Because this is unreachable, we can return any value we want. + V::bottom() + } + } + } +} + +impl<V: JoinSemiLattice + Clone> JoinSemiLattice for State<V> { + fn join(&mut self, other: &Self) -> bool { + 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<Local, Option<PlaceIndex>>, + projections: FxHashMap<(PlaceIndex, TrackElem), PlaceIndex>, + places: IndexVec<PlaceIndex, PlaceInfo>, + value_count: usize, +} + +impl Map { + fn new() -> Self { + Self { + locals: IndexVec::new(), + projections: FxHashMap::default(), + places: IndexVec::new(), + value_count: 0, + } + } + + /// 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>, + body: &Body<'tcx>, + mut filter: impl FnMut(Ty<'tcx>) -> bool, + exclude: &IndexVec<Local, bool>, + ) { + // We use this vector as stack, pushing and popping projections. + let mut projection = Vec::new(); + 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>, + local: Local, + projection: &mut Vec<PlaceElem<'tcx>>, + ty: Ty<'tcx>, + filter: &mut impl FnMut(Ty<'tcx>) -> bool, + ) { + // 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, 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, + projection: &[PlaceElem<'tcx>], + ) -> Result<PlaceIndex, ()> { + // Get the base index of the local. + let mut index = + *self.locals.get_or_insert_with(local, || self.places.push(PlaceInfo::new(None))); + + // Apply the projection. + for &elem in projection { + let elem = elem.try_into()?; + index = *self.projections.entry((index, elem)).or_insert_with(|| { + // Prepend new child to the linked list. + let next = self.places.push(PlaceInfo::new(Some(elem))); + self.places[next].next_sibling = self.places[index].first_child; + self.places[index].first_child = Some(next); + next + }); + } + + Ok(index) + } + + /// 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 + } + + /// Applies a single projection element, yielding the corresponding child. + pub fn apply(&self, place: PlaceIndex, elem: TrackElem) -> Option<PlaceIndex> { + self.projections.get(&(place, elem)).copied() + } + + /// Locates the given place, if it exists in the tree. + pub fn find(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> { + let mut index = *self.locals.get(place.local)?.as_ref()?; + + for &elem in place.projection { + index = self.apply(index, elem.try_into().ok()?)?; + } + + Some(index) + } + + /// Iterate over all direct children. + pub fn children(&self, parent: PlaceIndex) -> impl Iterator<Item = PlaceIndex> + '_ { + 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) { + self.preorder_invoke(child, f); + } + } +} + +/// 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<PlaceIndex>`). +#[derive(Debug)] +struct PlaceInfo { + /// We store a [`ValueIndex`] if and only if the placed is tracked by the analysis. + value_index: Option<ValueIndex>, + + /// The projection used to go from parent to this node (only None for root). + proj_elem: Option<TrackElem>, + + /// The left-most child. + first_child: Option<PlaceIndex>, + + /// Index of the sibling to the right of this node. + next_sibling: Option<PlaceIndex>, +} + +impl PlaceInfo { + fn new(proj_elem: Option<TrackElem>) -> Self { + Self { next_sibling: None, first_child: None, proj_elem, value_index: None } + } +} + +struct Children<'a> { + map: &'a Map, + next: Option<PlaceIndex>, +} + +impl<'a> Children<'a> { + fn new(map: &'a Map, parent: PlaceIndex) -> Self { + Self { map, next: map.places[parent].first_child } + } +} + +impl<'a> Iterator for Children<'a> { + type Item = PlaceIndex; + + fn next(&mut self) -> Option<Self::Item> { + match self.next { + Some(child) => { + self.next = self.map.places[child].next_sibling; + Some(child) + } + None => None, + } + } +} + +/// Used as the result of an operand or r-value. +pub enum ValueOrPlace<V> { + Value(V), + Place(PlaceIndex), +} + +impl<V: HasTop> ValueOrPlace<V> { + 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 TrackElem { + Field(Field), +} + +impl<V, T> TryFrom<ProjectionElem<V, T>> for TrackElem { + type Error = (); + + fn try_from(value: ProjectionElem<V, T>) -> Result<Self, Self::Error> { + match value { + 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>, + mut f: impl FnMut(Option<VariantIdx>, Field, Ty<'tcx>), +) { + match ty.kind() { + ty::Tuple(list) => { + for (field, ty) in list.iter().enumerate() { + f(None, field.into(), ty); + } + } + 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(variant, f_index.into(), field_ty); + } + } + } + ty::Closure(_, substs) => { + iter_fields(substs.as_closure().tupled_upvars_ty(), tcx, f); + } + _ => (), + } +} + +/// Returns all locals with projections that have their reference or address taken. +fn excluded_locals<'tcx>(body: &Body<'tcx>) -> IndexVec<Local, bool> { + struct Collector { + result: IndexVec<Local, bool>, + } + + 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<ValueAnalysisWrapper<T>> for State<T::Value> +where + T: ValueAnalysis<'tcx>, + T::Value: Debug, +{ + fn fmt_with(&self, ctxt: &ValueAnalysisWrapper<T>, 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<T>, + 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<V: Debug + Eq>( + place: PlaceIndex, + place_str: &str, + new: &IndexVec<ValueIndex, V>, + old: Option<&IndexVec<ValueIndex, V>>, + 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[value])?, + Some(old) => { + if new[value] != old[value] { + writeln!(f, "\u{001f}-{}: {:?}", place_str, old[value])?; + writeln!(f, "\u{001f}+{}: {:?}", place_str, new[value])?; + } + } + } + } + + for child in map.children(place) { + let info_elem = map.places[child].proj_elem.unwrap(); + let child_place_str = match info_elem { + TrackElem::Field(field) => { + if place_str.starts_with('*') { + format!("({}).{}", place_str, field.index()) + } else { + format!("{}.{}", place_str, field.index()) + } + } + }; + debug_with_context_rec(child, &child_place_str, new, old, map, f)?; + } + + Ok(()) +} + +fn debug_with_context<V: Debug + Eq>( + new: &IndexVec<ValueIndex, V>, + old: Option<&IndexVec<ValueIndex, V>>, + map: &Map, + f: &mut Formatter<'_>, +) -> std::fmt::Result { + for (local, place) in map.locals.iter_enumerated() { + if let Some(place) = place { + debug_with_context_rec(*place, &format!("{:?}", local), new, old, map, f)?; + } + } + Ok(()) +} |