diff options
| -rw-r--r-- | compiler/rustc_borrowck/src/nll.rs | 5 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/mod.rs | 6 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/values.rs | 104 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs | 8 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/type_check/liveness/mod.rs | 5 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/type_check/liveness/trace.rs | 9 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/type_check/mod.rs | 9 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/lib.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/points.rs | 156 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/dest_prop.rs | 81 |
10 files changed, 226 insertions, 158 deletions
diff --git a/compiler/rustc_borrowck/src/nll.rs b/compiler/rustc_borrowck/src/nll.rs index 5b764495922..cc8208e9dc3 100644 --- a/compiler/rustc_borrowck/src/nll.rs +++ b/compiler/rustc_borrowck/src/nll.rs @@ -12,6 +12,7 @@ use rustc_middle::ty::print::with_no_trimmed_paths; use rustc_middle::ty::{self, OpaqueHiddenType, TyCtxt}; use rustc_mir_dataflow::impls::MaybeInitializedPlaces; use rustc_mir_dataflow::move_paths::MoveData; +use rustc_mir_dataflow::points::DenseLocationMap; use rustc_mir_dataflow::ResultsCursor; use rustc_span::symbol::sym; use std::env; @@ -27,7 +28,7 @@ use crate::{ facts::{AllFacts, AllFactsExt, RustcFacts}, location::LocationTable, polonius, - region_infer::{values::RegionValueElements, RegionInferenceContext}, + region_infer::RegionInferenceContext, renumber, type_check::{self, MirTypeckRegionConstraints, MirTypeckResults}, universal_regions::UniversalRegions, @@ -98,7 +99,7 @@ pub(crate) fn compute_regions<'cx, 'tcx>( let universal_regions = Rc::new(universal_regions); - let elements = &Rc::new(RegionValueElements::new(body)); + let elements = &Rc::new(DenseLocationMap::new(body)); // Run the MIR type-checker. let MirTypeckResults { constraints, universal_region_relations, opaque_type_values } = diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs index 948221e9407..cbf01feae06 100644 --- a/compiler/rustc_borrowck/src/region_infer/mod.rs +++ b/compiler/rustc_borrowck/src/region_infer/mod.rs @@ -19,6 +19,7 @@ use rustc_middle::mir::{ use rustc_middle::traits::ObligationCause; use rustc_middle::traits::ObligationCauseCode; use rustc_middle::ty::{self, RegionVid, Ty, TyCtxt, TypeFoldable, TypeVisitableExt}; +use rustc_mir_dataflow::points::DenseLocationMap; use rustc_span::Span; use crate::constraints::graph::{self, NormalConstraintGraph, RegionGraph}; @@ -30,8 +31,7 @@ use crate::{ nll::PoloniusOutput, region_infer::reverse_sccs::ReverseSccGraph, region_infer::values::{ - LivenessValues, PlaceholderIndices, RegionElement, RegionValueElements, RegionValues, - ToElementIndex, + LivenessValues, PlaceholderIndices, RegionElement, RegionValues, ToElementIndex, }, type_check::{free_region_relations::UniversalRegionRelations, Locations}, universal_regions::UniversalRegions, @@ -330,7 +330,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { universe_causes: FxIndexMap<ty::UniverseIndex, UniverseInfo<'tcx>>, type_tests: Vec<TypeTest<'tcx>>, liveness_constraints: LivenessValues, - elements: &Rc<RegionValueElements>, + elements: &Rc<DenseLocationMap>, ) -> Self { debug!("universal_regions: {:#?}", universal_regions); debug!("outlives constraints: {:#?}", outlives_constraints); diff --git a/compiler/rustc_borrowck/src/region_infer/values.rs b/compiler/rustc_borrowck/src/region_infer/values.rs index dc3ee849d00..01f7bfcadb6 100644 --- a/compiler/rustc_borrowck/src/region_infer/values.rs +++ b/compiler/rustc_borrowck/src/region_infer/values.rs @@ -5,97 +5,13 @@ use rustc_index::bit_set::SparseBitMatrix; use rustc_index::interval::IntervalSet; use rustc_index::interval::SparseIntervalMatrix; use rustc_index::Idx; -use rustc_index::IndexVec; -use rustc_middle::mir::{BasicBlock, Body, Location}; +use rustc_middle::mir::{BasicBlock, Location}; use rustc_middle::ty::{self, RegionVid}; +use rustc_mir_dataflow::points::{DenseLocationMap, PointIndex}; use std::fmt::Debug; use std::rc::Rc; -use crate::dataflow::BorrowIndex; - -/// Maps between a `Location` and a `PointIndex` (and vice versa). -pub(crate) struct RegionValueElements { - /// For each basic block, how many points are contained within? - statements_before_block: IndexVec<BasicBlock, usize>, - - /// Map backward from each point to the basic block that it - /// belongs to. - basic_blocks: IndexVec<PointIndex, BasicBlock>, - - num_points: usize, -} - -impl RegionValueElements { - pub(crate) fn new(body: &Body<'_>) -> Self { - let mut num_points = 0; - let statements_before_block: IndexVec<BasicBlock, usize> = body - .basic_blocks - .iter() - .map(|block_data| { - let v = num_points; - num_points += block_data.statements.len() + 1; - v - }) - .collect(); - debug!("RegionValueElements: statements_before_block={:#?}", statements_before_block); - debug!("RegionValueElements: num_points={:#?}", num_points); - - let mut basic_blocks = IndexVec::with_capacity(num_points); - for (bb, bb_data) in body.basic_blocks.iter_enumerated() { - basic_blocks.extend((0..=bb_data.statements.len()).map(|_| bb)); - } - - Self { statements_before_block, basic_blocks, num_points } - } - - /// Total number of point indices - pub(crate) fn num_points(&self) -> usize { - self.num_points - } - - /// Converts a `Location` into a `PointIndex`. O(1). - pub(crate) fn point_from_location(&self, location: Location) -> PointIndex { - let Location { block, statement_index } = location; - let start_index = self.statements_before_block[block]; - PointIndex::new(start_index + statement_index) - } - - /// Converts a `Location` into a `PointIndex`. O(1). - pub(crate) fn entry_point(&self, block: BasicBlock) -> PointIndex { - let start_index = self.statements_before_block[block]; - PointIndex::new(start_index) - } - - /// Return the PointIndex for the block start of this index. - pub(crate) fn to_block_start(&self, index: PointIndex) -> PointIndex { - PointIndex::new(self.statements_before_block[self.basic_blocks[index]]) - } - - /// Converts a `PointIndex` back to a location. O(1). - pub(crate) fn to_location(&self, index: PointIndex) -> Location { - assert!(index.index() < self.num_points); - let block = self.basic_blocks[index]; - let start_index = self.statements_before_block[block]; - let statement_index = index.index() - start_index; - Location { block, statement_index } - } - - /// Sometimes we get point-indices back from bitsets that may be - /// out of range (because they round up to the nearest 2^N number - /// of bits). Use this function to filter such points out if you - /// like. - pub(crate) fn point_in_range(&self, index: PointIndex) -> bool { - index.index() < self.num_points - } -} - -rustc_index::newtype_index! { - /// A single integer representing a `Location` in the MIR control-flow - /// graph. Constructed efficiently from `RegionValueElements`. - #[orderable] - #[debug_format = "PointIndex({})"] - pub struct PointIndex {} -} +use crate::BorrowIndex; rustc_index::newtype_index! { /// A single integer representing a `ty::Placeholder`. @@ -123,7 +39,7 @@ pub(crate) enum RegionElement { /// an interval matrix storing liveness ranges for each region-vid. pub(crate) struct LivenessValues { /// The map from locations to points. - elements: Rc<RegionValueElements>, + elements: Rc<DenseLocationMap>, /// For each region: the points where it is live. points: SparseIntervalMatrix<RegionVid, PointIndex>, @@ -155,9 +71,9 @@ impl LiveLoans { impl LivenessValues { /// Create an empty map of regions to locations where they're live. - pub(crate) fn new(elements: Rc<RegionValueElements>) -> Self { + pub(crate) fn new(elements: Rc<DenseLocationMap>) -> Self { LivenessValues { - points: SparseIntervalMatrix::new(elements.num_points), + points: SparseIntervalMatrix::new(elements.num_points()), elements, loans: None, } @@ -298,7 +214,7 @@ impl PlaceholderIndices { /// it would also contain various points from within the function. #[derive(Clone)] pub(crate) struct RegionValues<N: Idx> { - elements: Rc<RegionValueElements>, + elements: Rc<DenseLocationMap>, placeholder_indices: Rc<PlaceholderIndices>, points: SparseIntervalMatrix<N, PointIndex>, free_regions: SparseBitMatrix<N, RegionVid>, @@ -313,14 +229,14 @@ impl<N: Idx> RegionValues<N> { /// Each of the regions in num_region_variables will be initialized with an /// empty set of points and no causal information. pub(crate) fn new( - elements: &Rc<RegionValueElements>, + elements: &Rc<DenseLocationMap>, num_universal_regions: usize, placeholder_indices: &Rc<PlaceholderIndices>, ) -> Self { let num_placeholders = placeholder_indices.len(); Self { elements: elements.clone(), - points: SparseIntervalMatrix::new(elements.num_points), + points: SparseIntervalMatrix::new(elements.num_points()), placeholder_indices: placeholder_indices.clone(), free_regions: SparseBitMatrix::new(num_universal_regions), placeholders: SparseBitMatrix::new(num_placeholders), @@ -486,7 +402,7 @@ impl ToElementIndex for ty::PlaceholderRegion { /// For debugging purposes, returns a pretty-printed string of the given points. pub(crate) fn pretty_print_points( - elements: &RegionValueElements, + elements: &DenseLocationMap, points: impl IntoIterator<Item = PointIndex>, ) -> String { pretty_print_region_elements( diff --git a/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs b/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs index 7433c94a0bc..da5456692ab 100644 --- a/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs +++ b/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs @@ -2,9 +2,9 @@ use rustc_data_structures::vec_linked_list as vll; use rustc_index::IndexVec; use rustc_middle::mir::visit::{PlaceContext, Visitor}; use rustc_middle::mir::{Body, Local, Location}; +use rustc_mir_dataflow::points::{DenseLocationMap, PointIndex}; use crate::def_use::{self, DefUse}; -use crate::region_infer::values::{PointIndex, RegionValueElements}; /// A map that cross references each local with the locations where it /// is defined (assigned), used, or dropped. Used during liveness @@ -60,7 +60,7 @@ impl vll::LinkElem for Appearance { impl LocalUseMap { pub(crate) fn build( live_locals: &[Local], - elements: &RegionValueElements, + elements: &DenseLocationMap, body: &Body<'_>, ) -> Self { let nones = IndexVec::from_elem(None, &body.local_decls); @@ -103,7 +103,7 @@ impl LocalUseMap { struct LocalUseMapBuild<'me> { local_use_map: &'me mut LocalUseMap, - elements: &'me RegionValueElements, + elements: &'me DenseLocationMap, // Vector used in `visit_local` to signal which `Local`s do we need // def/use/drop information on, constructed from `live_locals` (that @@ -144,7 +144,7 @@ impl LocalUseMapBuild<'_> { } fn insert( - elements: &RegionValueElements, + elements: &DenseLocationMap, first_appearance: &mut Option<AppearanceIndex>, appearances: &mut IndexVec<AppearanceIndex, Appearance>, location: Location, diff --git a/compiler/rustc_borrowck/src/type_check/liveness/mod.rs b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs index e137bc1be0a..51ae7d14e43 100644 --- a/compiler/rustc_borrowck/src/type_check/liveness/mod.rs +++ b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs @@ -6,6 +6,7 @@ use rustc_middle::ty::visit::TypeVisitable; use rustc_middle::ty::{GenericArgsRef, Region, RegionVid, Ty, TyCtxt}; use rustc_mir_dataflow::impls::MaybeInitializedPlaces; use rustc_mir_dataflow::move_paths::MoveData; +use rustc_mir_dataflow::points::DenseLocationMap; use rustc_mir_dataflow::ResultsCursor; use std::rc::Rc; @@ -13,7 +14,7 @@ use crate::{ constraints::OutlivesConstraintSet, facts::{AllFacts, AllFactsExt}, location::LocationTable, - region_infer::values::{LivenessValues, RegionValueElements}, + region_infer::values::LivenessValues, universal_regions::UniversalRegions, }; @@ -34,7 +35,7 @@ mod trace; pub(super) fn generate<'mir, 'tcx>( typeck: &mut TypeChecker<'_, 'tcx>, body: &Body<'tcx>, - elements: &Rc<RegionValueElements>, + elements: &Rc<DenseLocationMap>, flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, move_data: &MoveData<'tcx>, location_table: &LocationTable, diff --git a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs index c718d57bec3..eec128b5f1d 100644 --- a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs +++ b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs @@ -7,6 +7,7 @@ use rustc_infer::infer::outlives::for_liveness; use rustc_middle::mir::{BasicBlock, Body, ConstraintCategory, Local, Location}; use rustc_middle::traits::query::DropckOutlivesResult; use rustc_middle::ty::{Ty, TyCtxt, TypeVisitable, TypeVisitableExt}; +use rustc_mir_dataflow::points::{DenseLocationMap, PointIndex}; use rustc_span::DUMMY_SP; use rustc_trait_selection::traits::query::type_op::outlives::DropckOutlives; use rustc_trait_selection::traits::query::type_op::{TypeOp, TypeOpOutput}; @@ -17,7 +18,7 @@ use rustc_mir_dataflow::move_paths::{HasMoveData, MoveData, MovePathIndex}; use rustc_mir_dataflow::ResultsCursor; use crate::{ - region_infer::values::{self, LiveLoans, PointIndex, RegionValueElements}, + region_infer::values::{self, LiveLoans}, type_check::liveness::local_use_map::LocalUseMap, type_check::liveness::polonius, type_check::NormalizeLocation, @@ -41,7 +42,7 @@ use crate::{ pub(super) fn trace<'mir, 'tcx>( typeck: &mut TypeChecker<'_, 'tcx>, body: &Body<'tcx>, - elements: &Rc<RegionValueElements>, + elements: &Rc<DenseLocationMap>, flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, move_data: &MoveData<'tcx>, relevant_live_locals: Vec<Local>, @@ -105,7 +106,7 @@ struct LivenessContext<'me, 'typeck, 'flow, 'tcx> { typeck: &'me mut TypeChecker<'typeck, 'tcx>, /// Defines the `PointIndex` mapping - elements: &'me RegionValueElements, + elements: &'me DenseLocationMap, /// MIR we are analyzing. body: &'me Body<'tcx>, @@ -570,7 +571,7 @@ impl<'tcx> LivenessContext<'_, '_, '_, 'tcx> { } fn make_all_regions_live( - elements: &RegionValueElements, + elements: &DenseLocationMap, typeck: &mut TypeChecker<'_, 'tcx>, value: impl TypeVisitable<TyCtxt<'tcx>>, live_at: &IntervalSet<PointIndex>, diff --git a/compiler/rustc_borrowck/src/type_check/mod.rs b/compiler/rustc_borrowck/src/type_check/mod.rs index aa951a6ce55..48444a6b6f7 100644 --- a/compiler/rustc_borrowck/src/type_check/mod.rs +++ b/compiler/rustc_borrowck/src/type_check/mod.rs @@ -35,6 +35,7 @@ use rustc_middle::ty::{ OpaqueHiddenType, OpaqueTypeKey, RegionVid, Ty, TyCtxt, UserType, UserTypeAnnotationIndex, }; use rustc_middle::ty::{GenericArgsRef, UserArgs}; +use rustc_mir_dataflow::points::DenseLocationMap; use rustc_span::def_id::CRATE_DEF_ID; use rustc_span::source_map::Spanned; use rustc_span::symbol::sym; @@ -59,9 +60,7 @@ use crate::{ location::LocationTable, member_constraints::MemberConstraintSet, path_utils, - region_infer::values::{ - LivenessValues, PlaceholderIndex, PlaceholderIndices, RegionValueElements, - }, + region_infer::values::{LivenessValues, PlaceholderIndex, PlaceholderIndices}, region_infer::TypeTest, type_check::free_region_relations::{CreateResult, UniversalRegionRelations}, universal_regions::{DefiningTy, UniversalRegions}, @@ -134,7 +133,7 @@ pub(crate) fn type_check<'mir, 'tcx>( all_facts: &mut Option<AllFacts>, flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, move_data: &MoveData<'tcx>, - elements: &Rc<RegionValueElements>, + elements: &Rc<DenseLocationMap>, upvars: &[&ty::CapturedPlace<'tcx>], use_polonius: bool, ) -> MirTypeckResults<'tcx> { @@ -556,7 +555,7 @@ impl<'a, 'b, 'tcx> TypeVerifier<'a, 'b, 'tcx> { let all_facts = &mut None; let mut constraints = Default::default(); let mut liveness_constraints = - LivenessValues::new(Rc::new(RegionValueElements::new(promoted_body))); + LivenessValues::new(Rc::new(DenseLocationMap::new(promoted_body))); // Don't try to add borrow_region facts for the promoted MIR let mut swap_constraints = |this: &mut Self| { diff --git a/compiler/rustc_mir_dataflow/src/lib.rs b/compiler/rustc_mir_dataflow/src/lib.rs index f0b21fd4184..b805f8ca23e 100644 --- a/compiler/rustc_mir_dataflow/src/lib.rs +++ b/compiler/rustc_mir_dataflow/src/lib.rs @@ -34,6 +34,7 @@ mod errors; mod framework; pub mod impls; pub mod move_paths; +pub mod points; pub mod rustc_peek; pub mod storage; pub mod un_derefer; diff --git a/compiler/rustc_mir_dataflow/src/points.rs b/compiler/rustc_mir_dataflow/src/points.rs new file mode 100644 index 00000000000..ff17ce1fe07 --- /dev/null +++ b/compiler/rustc_mir_dataflow/src/points.rs @@ -0,0 +1,156 @@ +use crate::framework::{visit_results, ResultsVisitable, ResultsVisitor}; +use rustc_index::bit_set::ChunkedBitSet; +use rustc_index::interval::SparseIntervalMatrix; +use rustc_index::Idx; +use rustc_index::IndexVec; +use rustc_middle::mir::{self, BasicBlock, Body, Location}; + +/// Maps between a `Location` and a `PointIndex` (and vice versa). +pub struct DenseLocationMap { + /// For each basic block, how many points are contained within? + statements_before_block: IndexVec<BasicBlock, usize>, + + /// Map backward from each point to the basic block that it + /// belongs to. + basic_blocks: IndexVec<PointIndex, BasicBlock>, + + num_points: usize, +} + +impl DenseLocationMap { + #[inline] + pub fn new(body: &Body<'_>) -> Self { + let mut num_points = 0; + let statements_before_block: IndexVec<BasicBlock, usize> = body + .basic_blocks + .iter() + .map(|block_data| { + let v = num_points; + num_points += block_data.statements.len() + 1; + v + }) + .collect(); + + let mut basic_blocks = IndexVec::with_capacity(num_points); + for (bb, bb_data) in body.basic_blocks.iter_enumerated() { + basic_blocks.extend((0..=bb_data.statements.len()).map(|_| bb)); + } + + Self { statements_before_block, basic_blocks, num_points } + } + + /// Total number of point indices + #[inline] + pub fn num_points(&self) -> usize { + self.num_points + } + + /// Converts a `Location` into a `PointIndex`. O(1). + #[inline] + pub fn point_from_location(&self, location: Location) -> PointIndex { + let Location { block, statement_index } = location; + let start_index = self.statements_before_block[block]; + PointIndex::new(start_index + statement_index) + } + + /// Returns the `PointIndex` for the first statement in the given `BasicBlock`. O(1). + #[inline] + pub fn entry_point(&self, block: BasicBlock) -> PointIndex { + let start_index = self.statements_before_block[block]; + PointIndex::new(start_index) + } + + /// Return the PointIndex for the block start of this index. + #[inline] + pub fn to_block_start(&self, index: PointIndex) -> PointIndex { + PointIndex::new(self.statements_before_block[self.basic_blocks[index]]) + } + + /// Converts a `PointIndex` back to a location. O(1). + #[inline] + pub fn to_location(&self, index: PointIndex) -> Location { + assert!(index.index() < self.num_points); + let block = self.basic_blocks[index]; + let start_index = self.statements_before_block[block]; + let statement_index = index.index() - start_index; + Location { block, statement_index } + } + + /// Sometimes we get point-indices back from bitsets that may be + /// out of range (because they round up to the nearest 2^N number + /// of bits). Use this function to filter such points out if you + /// like. + #[inline] + pub fn point_in_range(&self, index: PointIndex) -> bool { + index.index() < self.num_points + } +} + +rustc_index::newtype_index! { + /// A single integer representing a `Location` in the MIR control-flow + /// graph. Constructed efficiently from `DenseLocationMap`. + #[orderable] + #[debug_format = "PointIndex({})"] + pub struct PointIndex {} +} + +/// Add points depending on the result of the given dataflow analysis. +pub fn save_as_intervals<'tcx, N, R>( + elements: &DenseLocationMap, + body: &mir::Body<'tcx>, + mut results: R, +) -> SparseIntervalMatrix<N, PointIndex> +where + N: Idx, + R: ResultsVisitable<'tcx, FlowState = ChunkedBitSet<N>>, +{ + let values = SparseIntervalMatrix::new(elements.num_points()); + let mut visitor = Visitor { elements, values }; + visit_results( + body, + body.basic_blocks.reverse_postorder().iter().copied(), + &mut results, + &mut visitor, + ); + visitor.values +} + +struct Visitor<'a, N: Idx> { + elements: &'a DenseLocationMap, + values: SparseIntervalMatrix<N, PointIndex>, +} + +impl<'mir, 'tcx, R, N> ResultsVisitor<'mir, 'tcx, R> for Visitor<'_, N> +where + N: Idx, +{ + type FlowState = ChunkedBitSet<N>; + + fn visit_statement_after_primary_effect( + &mut self, + _results: &mut R, + state: &Self::FlowState, + _statement: &'mir mir::Statement<'tcx>, + location: Location, + ) { + let point = self.elements.point_from_location(location); + // Use internal iterator manually as it is much more efficient. + state.iter().for_each(|node| { + self.values.insert(node, point); + }); + } + + fn visit_terminator_after_primary_effect( + &mut self, + _results: &mut R, + state: &Self::FlowState, + _terminator: &'mir mir::Terminator<'tcx>, + location: Location, + ) { + let point = self.elements.point_from_location(location); + // Use internal iterator manually as it is much more efficient. + state.iter().for_each(|node| { + self.values.insert(node, point); + }); + } +} diff --git a/compiler/rustc_mir_transform/src/dest_prop.rs b/compiler/rustc_mir_transform/src/dest_prop.rs index 2cc76f30fcf..0ac4ab61d40 100644 --- a/compiler/rustc_mir_transform/src/dest_prop.rs +++ b/compiler/rustc_mir_transform/src/dest_prop.rs @@ -134,6 +134,7 @@ use crate::MirPass; use rustc_data_structures::fx::{FxIndexMap, IndexEntry, IndexOccupiedEntry}; use rustc_index::bit_set::BitSet; +use rustc_index::interval::SparseIntervalMatrix; use rustc_middle::mir::visit::{MutVisitor, PlaceContext, Visitor}; use rustc_middle::mir::HasLocalDecls; use rustc_middle::mir::{dump_mir, PassWhere}; @@ -143,7 +144,8 @@ use rustc_middle::mir::{ }; use rustc_middle::ty::TyCtxt; use rustc_mir_dataflow::impls::MaybeLiveLocals; -use rustc_mir_dataflow::{Analysis, ResultsCursor}; +use rustc_mir_dataflow::points::{save_as_intervals, DenseLocationMap, PointIndex}; +use rustc_mir_dataflow::Analysis; pub struct DestinationPropagation; @@ -167,6 +169,13 @@ impl<'tcx> MirPass<'tcx> for DestinationPropagation { let borrowed = rustc_mir_dataflow::impls::borrowed_locals(body); + let live = MaybeLiveLocals + .into_engine(tcx, body) + .pass_name("MaybeLiveLocals-DestinationPropagation") + .iterate_to_fixpoint(); + let points = DenseLocationMap::new(body); + let mut live = save_as_intervals(&points, body, live); + // In order to avoid having to collect data for every single pair of locals in the body, we // do not allow doing more than one merge for places that are derived from the same local at // once. To avoid missed opportunities, we instead iterate to a fixed point - we'll refer to @@ -190,22 +199,19 @@ impl<'tcx> MirPass<'tcx> for DestinationPropagation { &mut allocations.candidates_reverse, ); trace!(?candidates); - let mut live = MaybeLiveLocals - .into_engine(tcx, body) - .iterate_to_fixpoint() - .into_results_cursor(body); - dest_prop_mir_dump(tcx, body, &mut live, round_count); + dest_prop_mir_dump(tcx, body, &points, &live, round_count); FilterInformation::filter_liveness( &mut candidates, - &mut live, + &points, + &live, &mut allocations.write_info, body, ); - // Because we do not update liveness information, it is unsound to use a local for more - // than one merge operation within a single round of optimizations. We store here which - // ones we have already used. + // Because we only filter once per round, it is unsound to use a local for more than + // one merge operation within a single round of optimizations. We store here which ones + // we have already used. let mut merged_locals: BitSet<Local> = BitSet::new_empty(body.local_decls.len()); // This is the set of merges we will apply this round. It is a subset of the candidates. @@ -224,9 +230,15 @@ impl<'tcx> MirPass<'tcx> for DestinationPropagation { }) { break; } + + // Replace `src` by `dest` everywhere. merges.insert(*src, *dest); merged_locals.insert(*src); merged_locals.insert(*dest); + + // Update liveness information based on the merge we just performed. + // Every location where `src` was live, `dest` will be live. + live.union_rows(*src, *dest); } trace!(merging = ?merges); @@ -349,7 +361,8 @@ impl<'a, 'tcx> MutVisitor<'tcx> for Merger<'a, 'tcx> { struct FilterInformation<'a, 'body, 'alloc, 'tcx> { body: &'body Body<'tcx>, - live: &'a mut ResultsCursor<'body, 'tcx, MaybeLiveLocals>, + points: &'a DenseLocationMap, + live: &'a SparseIntervalMatrix<Local, PointIndex>, candidates: &'a mut Candidates<'alloc>, write_info: &'alloc mut WriteInfo, at: Location, @@ -452,12 +465,14 @@ impl<'a, 'body, 'alloc, 'tcx> FilterInformation<'a, 'body, 'alloc, 'tcx> { /// locals as also being read from. fn filter_liveness<'b>( candidates: &mut Candidates<'alloc>, - live: &mut ResultsCursor<'b, 'tcx, MaybeLiveLocals>, + points: &DenseLocationMap, + live: &SparseIntervalMatrix<Local, PointIndex>, write_info_alloc: &'alloc mut WriteInfo, body: &'b Body<'tcx>, ) { let mut this = FilterInformation { body, + points, live, candidates, // We don't actually store anything at this scope, we just keep things here to be able @@ -472,13 +487,11 @@ impl<'a, 'body, 'alloc, 'tcx> FilterInformation<'a, 'body, 'alloc, 'tcx> { fn internal_filter_liveness(&mut self) { for (block, data) in traversal::preorder(self.body) { self.at = Location { block, statement_index: data.statements.len() }; - self.live.seek_after_primary_effect(self.at); self.write_info.for_terminator(&data.terminator().kind); self.apply_conflicts(); for (i, statement) in data.statements.iter().enumerate().rev() { self.at = Location { block, statement_index: i }; - self.live.seek_after_primary_effect(self.at); self.write_info.for_statement(&statement.kind, self.body); self.apply_conflicts(); } @@ -497,6 +510,7 @@ impl<'a, 'body, 'alloc, 'tcx> FilterInformation<'a, 'body, 'alloc, 'tcx> { None } }); + let at = self.points.point_from_location(self.at); self.candidates.filter_candidates_by( *p, |q| { @@ -508,7 +522,7 @@ impl<'a, 'body, 'alloc, 'tcx> FilterInformation<'a, 'body, 'alloc, 'tcx> { // calls or inline asm. Because of this, we also mark locals as // conflicting when both of them are written to in the same // statement. - if self.live.contains(q) || writes.contains(&q) { + if self.live.contains(q, at) || writes.contains(&q) { CandidateFilter::Remove } else { CandidateFilter::Keep @@ -801,38 +815,17 @@ fn is_local_required(local: Local, body: &Body<'_>) -> bool { fn dest_prop_mir_dump<'body, 'tcx>( tcx: TyCtxt<'tcx>, body: &'body Body<'tcx>, - live: &mut ResultsCursor<'body, 'tcx, MaybeLiveLocals>, + points: &DenseLocationMap, + live: &SparseIntervalMatrix<Local, PointIndex>, round: usize, ) { - let mut reachable = None; + let locals_live_at = |location| { + let location = points.point_from_location(location); + live.rows().filter(|&r| live.contains(r, location)).collect::<Vec<_>>() + }; dump_mir(tcx, false, "DestinationPropagation-dataflow", &round, body, |pass_where, w| { - let reachable = reachable.get_or_insert_with(|| traversal::reachable_as_bitset(body)); - - match pass_where { - PassWhere::BeforeLocation(loc) if reachable.contains(loc.block) => { - live.seek_after_primary_effect(loc); - writeln!(w, " // live: {:?}", live.get())?; - } - PassWhere::AfterTerminator(bb) if reachable.contains(bb) => { - let loc = body.terminator_loc(bb); - live.seek_before_primary_effect(loc); - writeln!(w, " // live: {:?}", live.get())?; - } - - PassWhere::BeforeBlock(bb) if reachable.contains(bb) => { - live.seek_to_block_start(bb); - writeln!(w, " // live: {:?}", live.get())?; - } - - PassWhere::BeforeCFG | PassWhere::AfterCFG | PassWhere::AfterLocation(_) => {} - - PassWhere::BeforeLocation(_) | PassWhere::AfterTerminator(_) => { - writeln!(w, " // live: <unreachable>")?; - } - - PassWhere::BeforeBlock(_) => { - writeln!(w, " // live: <unreachable>")?; - } + if let PassWhere::BeforeLocation(loc) = pass_where { + writeln!(w, " // live: {:?}", locals_live_at(loc))?; } Ok(()) |