diff options
Diffstat (limited to 'compiler/rustc_mir_dataflow/src/framework')
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/cursor.rs | 65 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/direction.rs | 294 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/fmt.rs | 13 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/graphviz.rs | 8 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/lattice.rs | 108 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/mod.rs | 31 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/results.rs | 39 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/visitor.rs | 4 |
8 files changed, 234 insertions, 328 deletions
diff --git a/compiler/rustc_mir_dataflow/src/framework/cursor.rs b/compiler/rustc_mir_dataflow/src/framework/cursor.rs index 5ebb343f4e1..11cf8c3e898 100644 --- a/compiler/rustc_mir_dataflow/src/framework/cursor.rs +++ b/compiler/rustc_mir_dataflow/src/framework/cursor.rs @@ -1,6 +1,7 @@ //! Random access inspection of the results of a dataflow analysis. use std::cmp::Ordering; +use std::ops::{Deref, DerefMut}; #[cfg(debug_assertions)] use rustc_index::bit_set::BitSet; @@ -8,18 +9,63 @@ use rustc_middle::mir::{self, BasicBlock, Location}; use super::{Analysis, Direction, Effect, EffectIndex, Results}; -/// Allows random access inspection of the results of a dataflow analysis. +/// Some `ResultsCursor`s want to own a `Results`, and some want to borrow a `Results`, either +/// mutable or immutably. This type allows all of the above. It's similar to `Cow`. +pub enum ResultsHandle<'a, 'tcx, A> +where + A: Analysis<'tcx>, +{ + Borrowed(&'a Results<'tcx, A>), + BorrowedMut(&'a mut Results<'tcx, A>), + Owned(Results<'tcx, A>), +} + +impl<'tcx, A> Deref for ResultsHandle<'_, 'tcx, A> +where + A: Analysis<'tcx>, +{ + type Target = Results<'tcx, A>; + + fn deref(&self) -> &Results<'tcx, A> { + match self { + ResultsHandle::Borrowed(borrowed) => borrowed, + ResultsHandle::BorrowedMut(borrowed) => borrowed, + ResultsHandle::Owned(owned) => owned, + } + } +} + +impl<'tcx, A> DerefMut for ResultsHandle<'_, 'tcx, A> +where + A: Analysis<'tcx>, +{ + fn deref_mut(&mut self) -> &mut Results<'tcx, A> { + match self { + ResultsHandle::Borrowed(_borrowed) => { + panic!("tried to deref_mut a `ResultsHandle::Borrowed") + } + ResultsHandle::BorrowedMut(borrowed) => borrowed, + ResultsHandle::Owned(owned) => owned, + } + } +} + +/// Allows random access inspection of the results of a dataflow analysis. Use this when you want +/// to inspect domain values only in certain locations; use `ResultsVisitor` if you want to inspect +/// domain values in many or all locations. /// -/// This cursor only has linear performance within a basic block when its statements are visited in -/// the same order as the `DIRECTION` of the analysis. In the worst case—when statements are -/// visited in *reverse* order—performance will be quadratic in the number of statements in the -/// block. The order in which basic blocks are inspected has no impact on performance. +/// Because `Results` only has domain values for the entry of each basic block, these inspections +/// involve some amount of domain value recomputations. This cursor only has linear performance +/// within a basic block when its statements are visited in the same order as the `DIRECTION` of +/// the analysis. In the worst case—when statements are visited in *reverse* order—performance will +/// be quadratic in the number of statements in the block. The order in which basic blocks are +/// inspected has no impact on performance. pub struct ResultsCursor<'mir, 'tcx, A> where A: Analysis<'tcx>, { body: &'mir mir::Body<'tcx>, - results: Results<'tcx, A>, + results: ResultsHandle<'mir, 'tcx, A>, state: A::Domain, pos: CursorPosition, @@ -47,13 +93,8 @@ where self.body } - /// Unwraps this cursor, returning the underlying `Results`. - pub fn into_results(self) -> Results<'tcx, A> { - self.results - } - /// Returns a new cursor that can inspect `results`. - pub fn new(body: &'mir mir::Body<'tcx>, results: Results<'tcx, A>) -> Self { + pub fn new(body: &'mir mir::Body<'tcx>, results: ResultsHandle<'mir, 'tcx, A>) -> Self { let bottom_value = results.analysis.bottom_value(body); ResultsCursor { body, diff --git a/compiler/rustc_mir_dataflow/src/framework/direction.rs b/compiler/rustc_mir_dataflow/src/framework/direction.rs index 9a5cf9d4e84..566a6b09b2b 100644 --- a/compiler/rustc_mir_dataflow/src/framework/direction.rs +++ b/compiler/rustc_mir_dataflow/src/framework/direction.rs @@ -9,30 +9,35 @@ use super::{Analysis, Effect, EffectIndex, Results, SwitchIntTarget}; pub trait Direction { const IS_FORWARD: bool; - const IS_BACKWARD: bool = !Self::IS_FORWARD; - /// Applies all effects between the given `EffectIndex`s. - /// - /// `effects.start()` must precede or equal `effects.end()` in this direction. - fn apply_effects_in_range<'tcx, A>( + /// Called by `iterate_to_fixpoint` during initial analysis computation. + fn apply_effects_in_block<'mir, 'tcx, A>( analysis: &mut A, + body: &mir::Body<'tcx>, state: &mut A::Domain, block: BasicBlock, - block_data: &mir::BasicBlockData<'tcx>, - effects: RangeInclusive<EffectIndex>, + block_data: &'mir mir::BasicBlockData<'tcx>, + propagate: impl FnMut(BasicBlock, &A::Domain), ) where A: Analysis<'tcx>; - fn apply_effects_in_block<'mir, 'tcx, A>( + /// Called by `ResultsCursor` to recompute the domain value for a location + /// in a basic block. Applies all effects between the given `EffectIndex`s. + /// + /// `effects.start()` must precede or equal `effects.end()` in this direction. + fn apply_effects_in_range<'tcx, A>( analysis: &mut A, state: &mut A::Domain, block: BasicBlock, - block_data: &'mir mir::BasicBlockData<'tcx>, - ) -> TerminatorEdges<'mir, 'tcx> - where + block_data: &mir::BasicBlockData<'tcx>, + effects: RangeInclusive<EffectIndex>, + ) where A: Analysis<'tcx>; + /// Called by `ResultsVisitor` to recompute the analysis domain values for + /// all locations in a basic block (starting from the entry value stored + /// in `Results`) and to visit them with `vis`. fn visit_results_in_block<'mir, 'tcx, A>( state: &mut A::Domain, block: BasicBlock, @@ -41,16 +46,6 @@ pub trait Direction { vis: &mut impl ResultsVisitor<'mir, 'tcx, A>, ) where A: Analysis<'tcx>; - - fn join_state_into_successors_of<'tcx, A>( - analysis: &mut A, - body: &mir::Body<'tcx>, - exit_state: &mut A::Domain, - block: BasicBlock, - edges: TerminatorEdges<'_, 'tcx>, - propagate: impl FnMut(BasicBlock, &A::Domain), - ) where - A: Analysis<'tcx>; } /// Dataflow that runs from the exit of a block (terminator), to its entry (the first statement). @@ -61,23 +56,84 @@ impl Direction for Backward { fn apply_effects_in_block<'mir, 'tcx, A>( analysis: &mut A, + body: &mir::Body<'tcx>, state: &mut A::Domain, block: BasicBlock, block_data: &'mir mir::BasicBlockData<'tcx>, - ) -> TerminatorEdges<'mir, 'tcx> - where + mut propagate: impl FnMut(BasicBlock, &A::Domain), + ) where A: Analysis<'tcx>, { let terminator = block_data.terminator(); let location = Location { block, statement_index: block_data.statements.len() }; analysis.apply_before_terminator_effect(state, terminator, location); - let edges = analysis.apply_terminator_effect(state, terminator, location); + analysis.apply_terminator_effect(state, terminator, location); for (statement_index, statement) in block_data.statements.iter().enumerate().rev() { let location = Location { block, statement_index }; analysis.apply_before_statement_effect(state, statement, location); analysis.apply_statement_effect(state, statement, location); } - edges + + let exit_state = state; + for pred in body.basic_blocks.predecessors()[block].iter().copied() { + match body[pred].terminator().kind { + // Apply terminator-specific edge effects. + // + // FIXME(ecstaticmorse): Avoid cloning the exit state unconditionally. + mir::TerminatorKind::Call { destination, target: Some(dest), .. } + if dest == block => + { + let mut tmp = exit_state.clone(); + analysis.apply_call_return_effect( + &mut tmp, + pred, + CallReturnPlaces::Call(destination), + ); + propagate(pred, &tmp); + } + + mir::TerminatorKind::InlineAsm { ref targets, ref operands, .. } + if targets.contains(&block) => + { + let mut tmp = exit_state.clone(); + analysis.apply_call_return_effect( + &mut tmp, + pred, + CallReturnPlaces::InlineAsm(operands), + ); + propagate(pred, &tmp); + } + + mir::TerminatorKind::Yield { resume, resume_arg, .. } if resume == block => { + let mut tmp = exit_state.clone(); + analysis.apply_call_return_effect( + &mut tmp, + resume, + CallReturnPlaces::Yield(resume_arg), + ); + propagate(pred, &tmp); + } + + mir::TerminatorKind::SwitchInt { targets: _, ref discr } => { + let mut applier = BackwardSwitchIntEdgeEffectsApplier { + body, + pred, + exit_state, + block, + propagate: &mut propagate, + effects_applied: false, + }; + + analysis.apply_switch_int_edge_effects(pred, discr, &mut applier); + + if !applier.effects_applied { + propagate(pred, exit_state) + } + } + + _ => propagate(pred, exit_state), + } + } } fn apply_effects_in_range<'tcx, A>( @@ -170,7 +226,6 @@ impl Direction for Backward { vis.visit_block_end(state); - // Terminator let loc = Location { block, statement_index: block_data.statements.len() }; let term = block_data.terminator(); results.analysis.apply_before_terminator_effect(state, term, loc); @@ -188,82 +243,13 @@ impl Direction for Backward { vis.visit_block_start(state); } - - fn join_state_into_successors_of<'tcx, A>( - analysis: &mut A, - body: &mir::Body<'tcx>, - exit_state: &mut A::Domain, - bb: BasicBlock, - _edges: TerminatorEdges<'_, 'tcx>, - mut propagate: impl FnMut(BasicBlock, &A::Domain), - ) where - A: Analysis<'tcx>, - { - for pred in body.basic_blocks.predecessors()[bb].iter().copied() { - match body[pred].terminator().kind { - // Apply terminator-specific edge effects. - // - // FIXME(ecstaticmorse): Avoid cloning the exit state unconditionally. - mir::TerminatorKind::Call { destination, target: Some(dest), .. } if dest == bb => { - let mut tmp = exit_state.clone(); - analysis.apply_call_return_effect( - &mut tmp, - pred, - CallReturnPlaces::Call(destination), - ); - propagate(pred, &tmp); - } - - mir::TerminatorKind::InlineAsm { ref targets, ref operands, .. } - if targets.contains(&bb) => - { - let mut tmp = exit_state.clone(); - analysis.apply_call_return_effect( - &mut tmp, - pred, - CallReturnPlaces::InlineAsm(operands), - ); - propagate(pred, &tmp); - } - - mir::TerminatorKind::Yield { resume, resume_arg, .. } if resume == bb => { - let mut tmp = exit_state.clone(); - analysis.apply_call_return_effect( - &mut tmp, - resume, - CallReturnPlaces::Yield(resume_arg), - ); - propagate(pred, &tmp); - } - - mir::TerminatorKind::SwitchInt { targets: _, ref discr } => { - let mut applier = BackwardSwitchIntEdgeEffectsApplier { - body, - pred, - exit_state, - bb, - propagate: &mut propagate, - effects_applied: false, - }; - - analysis.apply_switch_int_edge_effects(pred, discr, &mut applier); - - if !applier.effects_applied { - propagate(pred, exit_state) - } - } - - _ => propagate(pred, exit_state), - } - } - } } struct BackwardSwitchIntEdgeEffectsApplier<'mir, 'tcx, D, F> { body: &'mir mir::Body<'tcx>, pred: BasicBlock, exit_state: &'mir mut D, - bb: BasicBlock, + block: BasicBlock, propagate: &'mir mut F, effects_applied: bool, } @@ -276,8 +262,8 @@ where fn apply(&mut self, mut apply_edge_effect: impl FnMut(&mut D, SwitchIntTarget)) { assert!(!self.effects_applied); - let values = &self.body.basic_blocks.switch_sources()[&(self.bb, self.pred)]; - let targets = values.iter().map(|&value| SwitchIntTarget { value, target: self.bb }); + let values = &self.body.basic_blocks.switch_sources()[&(self.block, self.pred)]; + let targets = values.iter().map(|&value| SwitchIntTarget { value, target: self.block }); let mut tmp = None; for target in targets { @@ -298,11 +284,12 @@ impl Direction for Forward { fn apply_effects_in_block<'mir, 'tcx, A>( analysis: &mut A, + _body: &mir::Body<'tcx>, state: &mut A::Domain, block: BasicBlock, block_data: &'mir mir::BasicBlockData<'tcx>, - ) -> TerminatorEdges<'mir, 'tcx> - where + mut propagate: impl FnMut(BasicBlock, &A::Domain), + ) where A: Analysis<'tcx>, { for (statement_index, statement) in block_data.statements.iter().enumerate() { @@ -313,7 +300,53 @@ impl Direction for Forward { let terminator = block_data.terminator(); let location = Location { block, statement_index: block_data.statements.len() }; analysis.apply_before_terminator_effect(state, terminator, location); - analysis.apply_terminator_effect(state, terminator, location) + let edges = analysis.apply_terminator_effect(state, terminator, location); + + let exit_state = state; + match edges { + TerminatorEdges::None => {} + TerminatorEdges::Single(target) => propagate(target, exit_state), + TerminatorEdges::Double(target, unwind) => { + propagate(target, exit_state); + propagate(unwind, exit_state); + } + TerminatorEdges::AssignOnReturn { return_, cleanup, place } => { + // This must be done *first*, otherwise the unwind path will see the assignments. + if let Some(cleanup) = cleanup { + propagate(cleanup, exit_state); + } + + if !return_.is_empty() { + analysis.apply_call_return_effect(exit_state, block, place); + for &target in return_ { + propagate(target, exit_state); + } + } + } + TerminatorEdges::SwitchInt { targets, discr } => { + let mut applier = ForwardSwitchIntEdgeEffectsApplier { + exit_state, + targets, + propagate, + effects_applied: false, + }; + + analysis.apply_switch_int_edge_effects(block, discr, &mut applier); + + let ForwardSwitchIntEdgeEffectsApplier { + exit_state, + mut propagate, + effects_applied, + .. + } = applier; + + if !effects_applied { + for target in targets.all_targets() { + propagate(*target, exit_state); + } + } + } + } } fn apply_effects_in_range<'tcx, A>( @@ -351,7 +384,8 @@ impl Direction for Forward { let statement = &block_data.statements[from.statement_index]; analysis.apply_statement_effect(state, statement, location); - // If we only needed to apply the after effect of the statement at `idx`, we are done. + // If we only needed to apply the after effect of the statement at `idx`, we are + // done. if from == to { return; } @@ -419,62 +453,6 @@ impl Direction for Forward { vis.visit_block_end(state); } - - fn join_state_into_successors_of<'tcx, A>( - analysis: &mut A, - _body: &mir::Body<'tcx>, - exit_state: &mut A::Domain, - bb: BasicBlock, - edges: TerminatorEdges<'_, 'tcx>, - mut propagate: impl FnMut(BasicBlock, &A::Domain), - ) where - A: Analysis<'tcx>, - { - match edges { - TerminatorEdges::None => {} - TerminatorEdges::Single(target) => propagate(target, exit_state), - TerminatorEdges::Double(target, unwind) => { - propagate(target, exit_state); - propagate(unwind, exit_state); - } - TerminatorEdges::AssignOnReturn { return_, cleanup, place } => { - // This must be done *first*, otherwise the unwind path will see the assignments. - if let Some(cleanup) = cleanup { - propagate(cleanup, exit_state); - } - - if !return_.is_empty() { - analysis.apply_call_return_effect(exit_state, bb, place); - for &target in return_ { - propagate(target, exit_state); - } - } - } - TerminatorEdges::SwitchInt { targets, discr } => { - let mut applier = ForwardSwitchIntEdgeEffectsApplier { - exit_state, - targets, - propagate, - effects_applied: false, - }; - - analysis.apply_switch_int_edge_effects(bb, discr, &mut applier); - - let ForwardSwitchIntEdgeEffectsApplier { - exit_state, - mut propagate, - effects_applied, - .. - } = applier; - - if !effects_applied { - for target in targets.all_targets() { - propagate(*target, exit_state); - } - } - } - } - } } struct ForwardSwitchIntEdgeEffectsApplier<'mir, D, F> { diff --git a/compiler/rustc_mir_dataflow/src/framework/fmt.rs b/compiler/rustc_mir_dataflow/src/framework/fmt.rs index ed540cd148c..c177d98106f 100644 --- a/compiler/rustc_mir_dataflow/src/framework/fmt.rs +++ b/compiler/rustc_mir_dataflow/src/framework/fmt.rs @@ -230,16 +230,3 @@ where write!(f, "{}", ctxt.move_data().move_paths[*self]) } } - -impl<T, C> DebugWithContext<C> for crate::lattice::Dual<T> -where - T: DebugWithContext<C>, -{ - fn fmt_with(&self, ctxt: &C, f: &mut fmt::Formatter<'_>) -> fmt::Result { - (self.0).fmt_with(ctxt, f) - } - - fn fmt_diff_with(&self, old: &Self, ctxt: &C, f: &mut fmt::Formatter<'_>) -> fmt::Result { - (self.0).fmt_diff_with(&old.0, ctxt, f) - } -} diff --git a/compiler/rustc_mir_dataflow/src/framework/graphviz.rs b/compiler/rustc_mir_dataflow/src/framework/graphviz.rs index 98a4f58cb5d..6e4994af8b4 100644 --- a/compiler/rustc_mir_dataflow/src/framework/graphviz.rs +++ b/compiler/rustc_mir_dataflow/src/framework/graphviz.rs @@ -47,20 +47,16 @@ where { pub(crate) fn new( body: &'mir Body<'tcx>, - results: Results<'tcx, A>, + results: &'mir Results<'tcx, A>, style: OutputStyle, ) -> Self { let reachable = mir::traversal::reachable_as_bitset(body); - Formatter { cursor: results.into_results_cursor(body).into(), style, reachable } + Formatter { cursor: results.as_results_cursor(body).into(), style, reachable } } fn body(&self) -> &'mir Body<'tcx> { self.cursor.borrow().body() } - - pub(crate) fn into_results(self) -> Results<'tcx, A> { - self.cursor.into_inner().into_results() - } } /// A pair of a basic block and an index into that basic blocks `successors`. diff --git a/compiler/rustc_mir_dataflow/src/framework/lattice.rs b/compiler/rustc_mir_dataflow/src/framework/lattice.rs index 4d03ee53b7c..6d2a7a099a0 100644 --- a/compiler/rustc_mir_dataflow/src/framework/lattice.rs +++ b/compiler/rustc_mir_dataflow/src/framework/lattice.rs @@ -25,8 +25,8 @@ //! //! ## `PartialOrd` //! -//! Given that they represent partially ordered sets, you may be surprised that [`JoinSemiLattice`] -//! and [`MeetSemiLattice`] do not have [`PartialOrd`] as a supertrait. This +//! Given that it represents a partially ordered set, you may be surprised that [`JoinSemiLattice`] +//! does not have [`PartialOrd`] as a supertrait. This //! is because most standard library types use lexicographic ordering instead of set inclusion for //! their `PartialOrd` impl. Since we do not actually need to compare lattice elements to run a //! dataflow analysis, there's no need for a newtype wrapper with a custom `PartialOrd` impl. The @@ -58,23 +58,6 @@ pub trait JoinSemiLattice: Eq { fn join(&mut self, other: &Self) -> bool; } -/// A [partially ordered set][poset] that has a [greatest lower bound][glb] for any pair of -/// elements in the set. -/// -/// Dataflow analyses only require that their domains implement [`JoinSemiLattice`], not -/// `MeetSemiLattice`. However, types that will be used as dataflow domains should implement both -/// so that they can be used with [`Dual`]. -/// -/// [glb]: https://en.wikipedia.org/wiki/Infimum_and_supremum -/// [poset]: https://en.wikipedia.org/wiki/Partially_ordered_set -pub trait MeetSemiLattice: Eq { - /// Computes the greatest lower bound of two elements, storing the result in `self` and - /// returning `true` if `self` has changed. - /// - /// The lattice meet operator is abbreviated as `∧`. - 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 { const BOTTOM: Self; @@ -105,17 +88,6 @@ impl JoinSemiLattice for bool { } } -impl MeetSemiLattice for bool { - fn meet(&mut self, other: &Self) -> bool { - if let (true, false) = (*self, *other) { - *self = false; - return true; - } - - false - } -} - impl HasBottom for bool { const BOTTOM: Self = false; @@ -145,18 +117,6 @@ impl<I: Idx, T: JoinSemiLattice> JoinSemiLattice for IndexVec<I, T> { } } -impl<I: Idx, T: MeetSemiLattice> MeetSemiLattice for IndexVec<I, T> { - fn meet(&mut self, other: &Self) -> bool { - assert_eq!(self.len(), other.len()); - - let mut changed = false; - for (a, b) in iter::zip(self, other) { - changed |= a.meet(b); - } - changed - } -} - /// A `BitSet` represents the lattice formed by the powerset of all possible values of /// the index type `T` ordered by inclusion. Equivalently, it is a tuple of "two-point" lattices, /// one for each possible value of `T`. @@ -166,60 +126,12 @@ impl<T: Idx> JoinSemiLattice for BitSet<T> { } } -impl<T: Idx> MeetSemiLattice for BitSet<T> { - fn meet(&mut self, other: &Self) -> bool { - self.intersect(other) - } -} - impl<T: Idx> JoinSemiLattice for ChunkedBitSet<T> { fn join(&mut self, other: &Self) -> bool { self.union(other) } } -impl<T: Idx> MeetSemiLattice for ChunkedBitSet<T> { - fn meet(&mut self, other: &Self) -> bool { - self.intersect(other) - } -} - -/// The counterpart of a given semilattice `T` using the [inverse order]. -/// -/// The dual of a join-semilattice is a meet-semilattice and vice versa. For example, the dual of a -/// powerset has the empty set as its top element and the full set as its bottom element and uses -/// set *intersection* as its join operator. -/// -/// [inverse order]: https://en.wikipedia.org/wiki/Duality_(order_theory) -#[derive(Clone, Copy, Debug, PartialEq, Eq)] -pub struct Dual<T>(pub T); - -impl<T: Idx> BitSetExt<T> for Dual<BitSet<T>> { - fn contains(&self, elem: T) -> bool { - self.0.contains(elem) - } - - fn union(&mut self, other: &HybridBitSet<T>) { - self.0.union(other); - } - - fn subtract(&mut self, other: &HybridBitSet<T>) { - self.0.subtract(other); - } -} - -impl<T: MeetSemiLattice> JoinSemiLattice for Dual<T> { - fn join(&mut self, other: &Self) -> bool { - self.0.meet(&other.0) - } -} - -impl<T: JoinSemiLattice> MeetSemiLattice for Dual<T> { - fn meet(&mut self, other: &Self) -> bool { - self.0.join(&other.0) - } -} - /// Extends a type `T` with top and bottom elements to make it a partially ordered set in which no /// value of `T` is comparable with any other. /// @@ -257,22 +169,6 @@ impl<T: Clone + Eq> JoinSemiLattice for FlatSet<T> { } } -impl<T: Clone + Eq> MeetSemiLattice for FlatSet<T> { - fn meet(&mut self, other: &Self) -> bool { - let result = match (&*self, other) { - (Self::Bottom, _) | (_, Self::Top) => return false, - (Self::Elem(ref a), Self::Elem(ref b)) if a == b => return false, - - (Self::Top, Self::Elem(ref x)) => Self::Elem(x.clone()), - - _ => Self::Bottom, - }; - - *self = result; - true - } -} - impl<T> HasBottom for FlatSet<T> { const BOTTOM: Self = Self::Bottom; diff --git a/compiler/rustc_mir_dataflow/src/framework/mod.rs b/compiler/rustc_mir_dataflow/src/framework/mod.rs index 244dfe26ad3..bb652a75caa 100644 --- a/compiler/rustc_mir_dataflow/src/framework/mod.rs +++ b/compiler/rustc_mir_dataflow/src/framework/mod.rs @@ -8,8 +8,9 @@ //! The `impls` module contains several examples of dataflow analyses. //! //! Then call `iterate_to_fixpoint` on your type that impls `Analysis` to get a `Results`. From -//! there, you can use a `ResultsCursor` to inspect the fixpoint solution to your dataflow problem, -//! or implement the `ResultsVisitor` interface and use `visit_results`. The following example uses +//! there, you can use a `ResultsCursor` to inspect the fixpoint solution to your dataflow problem +//! (good for inspecting a small number of locations), or implement the `ResultsVisitor` interface +//! and use `visit_results` (good for inspecting many or all locations). The following example uses //! the `ResultsCursor` approach. //! //! ```ignore (cross-crate-imports) @@ -278,22 +279,17 @@ pub trait Analysis<'tcx> { // every iteration. let mut state = self.bottom_value(body); while let Some(bb) = dirty_queue.pop() { - let bb_data = &body[bb]; - // Set the state to the entry state of the block. // This is equivalent to `state = entry_sets[bb].clone()`, // but it saves an allocation, thus improving compile times. state.clone_from(&entry_sets[bb]); - // Apply the block transfer function, using the cached one if it exists. - let edges = Self::Direction::apply_effects_in_block(&mut self, &mut state, bb, bb_data); - - Self::Direction::join_state_into_successors_of( + Self::Direction::apply_effects_in_block( &mut self, body, &mut state, bb, - edges, + &body[bb], |target: BasicBlock, state: &Self::Domain| { let set_changed = entry_sets[target].join(state); if set_changed { @@ -306,14 +302,13 @@ pub trait Analysis<'tcx> { let results = Results { analysis: self, entry_sets }; if tcx.sess.opts.unstable_opts.dump_mir_dataflow { - let (res, results) = write_graphviz_results(tcx, body, results, pass_name); + let res = write_graphviz_results(tcx, body, &results, pass_name); if let Err(e) = res { error!("Failed to write graphviz dataflow results: {}", e); } - results - } else { - results } + + results } } @@ -378,16 +373,6 @@ impl<T, S: GenKill<T>> GenKill<T> for MaybeReachable<S> { } } -impl<T: Idx> GenKill<T> for lattice::Dual<BitSet<T>> { - fn gen_(&mut self, elem: T) { - self.0.insert(elem); - } - - fn kill(&mut self, elem: T) { - self.0.remove(elem); - } -} - // NOTE: DO NOT CHANGE VARIANT ORDER. The derived `Ord` impls rely on the current order. #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)] enum Effect { diff --git a/compiler/rustc_mir_dataflow/src/framework/results.rs b/compiler/rustc_mir_dataflow/src/framework/results.rs index ff6cafbfbae..8493a7aa44b 100644 --- a/compiler/rustc_mir_dataflow/src/framework/results.rs +++ b/compiler/rustc_mir_dataflow/src/framework/results.rs @@ -17,10 +17,13 @@ use super::{Analysis, ResultsCursor, ResultsVisitor, graphviz, visit_results}; use crate::errors::{ DuplicateValuesFor, PathMustEndInFilename, RequiresAnArgument, UnknownFormatter, }; +use crate::framework::cursor::ResultsHandle; pub type EntrySets<'tcx, A> = IndexVec<BasicBlock, <A as Analysis<'tcx>>::Domain>; -/// A dataflow analysis that has converged to fixpoint. +/// A dataflow analysis that has converged to fixpoint. It only holds the domain values at the +/// entry of each basic block. Domain values in other parts of the block are recomputed on the fly +/// by visitors (i.e. `ResultsCursor`, or `ResultsVisitor` impls). #[derive(Clone)] pub struct Results<'tcx, A> where @@ -34,12 +37,30 @@ impl<'tcx, A> Results<'tcx, A> where A: Analysis<'tcx>, { - /// Creates a `ResultsCursor` that can inspect these `Results`. + /// Creates a `ResultsCursor` that can inspect these `Results`. Immutably borrows the `Results`, + /// which is appropriate when the `Results` is used outside the cursor. + pub fn as_results_cursor<'mir>( + &'mir self, + body: &'mir mir::Body<'tcx>, + ) -> ResultsCursor<'mir, 'tcx, A> { + ResultsCursor::new(body, ResultsHandle::Borrowed(self)) + } + + /// Creates a `ResultsCursor` that can mutate these `Results`. Mutably borrows the `Results`, + /// which is appropriate when the `Results` is used outside the cursor. + pub fn as_results_cursor_mut<'mir>( + &'mir mut self, + body: &'mir mir::Body<'tcx>, + ) -> ResultsCursor<'mir, 'tcx, A> { + ResultsCursor::new(body, ResultsHandle::BorrowedMut(self)) + } + + /// Creates a `ResultsCursor` that takes ownership of the `Results`. pub fn into_results_cursor<'mir>( self, body: &'mir mir::Body<'tcx>, ) -> ResultsCursor<'mir, 'tcx, A> { - ResultsCursor::new(body, self) + ResultsCursor::new(body, ResultsHandle::Owned(self)) } /// Gets the dataflow state for the given block. @@ -74,9 +95,9 @@ where pub(super) fn write_graphviz_results<'tcx, A>( tcx: TyCtxt<'tcx>, body: &mir::Body<'tcx>, - results: Results<'tcx, A>, + results: &Results<'tcx, A>, pass_name: Option<&'static str>, -) -> (std::io::Result<()>, Results<'tcx, A>) +) -> std::io::Result<()> where A: Analysis<'tcx>, A::Domain: DebugWithContext<A>, @@ -87,7 +108,7 @@ where let def_id = body.source.def_id(); let Ok(attrs) = RustcMirAttrs::parse(tcx, def_id) else { // Invalid `rustc_mir` attrs are reported in `RustcMirAttrs::parse` - return (Ok(()), results); + return Ok(()); }; let file = try { @@ -104,12 +125,12 @@ where create_dump_file(tcx, "dot", false, A::NAME, &pass_name.unwrap_or("-----"), body)? } - _ => return (Ok(()), results), + _ => return Ok(()), } }; let mut file = match file { Ok(f) => f, - Err(e) => return (Err(e), results), + Err(e) => return Err(e), }; let style = match attrs.formatter { @@ -132,7 +153,7 @@ where file.write_all(&buf)?; }; - (lhs, graphviz.into_results()) + lhs } #[derive(Default)] diff --git a/compiler/rustc_mir_dataflow/src/framework/visitor.rs b/compiler/rustc_mir_dataflow/src/framework/visitor.rs index 5c7539eed4d..bde41974d47 100644 --- a/compiler/rustc_mir_dataflow/src/framework/visitor.rs +++ b/compiler/rustc_mir_dataflow/src/framework/visitor.rs @@ -26,7 +26,9 @@ pub fn visit_results<'mir, 'tcx, A>( } } -/// A visitor over the results of an `Analysis`. +/// A visitor over the results of an `Analysis`. Use this when you want to inspect domain values in +/// many or all locations; use `ResultsCursor` if you want to inspect domain values only in certain +/// locations. pub trait ResultsVisitor<'mir, 'tcx, A> where A: Analysis<'tcx>, |