diff options
18 files changed, 788 insertions, 516 deletions
diff --git a/src/librustc_mir/borrow_check/flows.rs b/src/librustc_mir/borrow_check/flows.rs deleted file mode 100644 index 57c544fda0c..00000000000 --- a/src/librustc_mir/borrow_check/flows.rs +++ /dev/null @@ -1,142 +0,0 @@ -//! Manages the dataflow bits required for borrowck. -//! -//! FIXME: this might be better as a "generic" fixed-point combinator, -//! but is not as ugly as it is right now. - -use rustc::mir::{BasicBlock, Location}; -use rustc_index::bit_set::BitIter; - -use crate::borrow_check::location::LocationIndex; - -use crate::borrow_check::nll::PoloniusOutput; - -use crate::dataflow::indexes::BorrowIndex; -use crate::dataflow::move_paths::HasMoveData; -use crate::dataflow::Borrows; -use crate::dataflow::EverInitializedPlaces; -use crate::dataflow::MaybeUninitializedPlaces; -use crate::dataflow::{FlowAtLocation, FlowsAtLocation}; -use either::Either; -use std::fmt; -use std::rc::Rc; - -crate struct Flows<'b, 'tcx> { - borrows: FlowAtLocation<'tcx, Borrows<'b, 'tcx>>, - pub uninits: FlowAtLocation<'tcx, MaybeUninitializedPlaces<'b, 'tcx>>, - pub ever_inits: FlowAtLocation<'tcx, EverInitializedPlaces<'b, 'tcx>>, - - /// Polonius Output - pub polonius_output: Option<Rc<PoloniusOutput>>, -} - -impl<'b, 'tcx> Flows<'b, 'tcx> { - crate fn new( - borrows: FlowAtLocation<'tcx, Borrows<'b, 'tcx>>, - uninits: FlowAtLocation<'tcx, MaybeUninitializedPlaces<'b, 'tcx>>, - ever_inits: FlowAtLocation<'tcx, EverInitializedPlaces<'b, 'tcx>>, - polonius_output: Option<Rc<PoloniusOutput>>, - ) -> Self { - Flows { borrows, uninits, ever_inits, polonius_output } - } - - crate fn borrows_in_scope( - &self, - location: LocationIndex, - ) -> impl Iterator<Item = BorrowIndex> + '_ { - if let Some(ref polonius) = self.polonius_output { - Either::Left(polonius.errors_at(location).iter().cloned()) - } else { - Either::Right(self.borrows.iter_incoming()) - } - } - - crate fn with_outgoing_borrows(&self, op: impl FnOnce(BitIter<'_, BorrowIndex>)) { - self.borrows.with_iter_outgoing(op) - } -} - -macro_rules! each_flow { - ($this:ident, $meth:ident($arg:ident)) => { - FlowAtLocation::$meth(&mut $this.borrows, $arg); - FlowAtLocation::$meth(&mut $this.uninits, $arg); - FlowAtLocation::$meth(&mut $this.ever_inits, $arg); - }; -} - -impl<'b, 'tcx> FlowsAtLocation for Flows<'b, 'tcx> { - fn reset_to_entry_of(&mut self, bb: BasicBlock) { - each_flow!(self, reset_to_entry_of(bb)); - } - - fn reset_to_exit_of(&mut self, bb: BasicBlock) { - each_flow!(self, reset_to_exit_of(bb)); - } - - fn reconstruct_statement_effect(&mut self, location: Location) { - each_flow!(self, reconstruct_statement_effect(location)); - } - - fn reconstruct_terminator_effect(&mut self, location: Location) { - each_flow!(self, reconstruct_terminator_effect(location)); - } - - fn apply_local_effect(&mut self, location: Location) { - each_flow!(self, apply_local_effect(location)); - } -} - -impl<'b, 'tcx> fmt::Display for Flows<'b, 'tcx> { - fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { - let mut s = String::new(); - - s.push_str("borrows in effect: ["); - let mut saw_one = false; - self.borrows.each_state_bit(|borrow| { - if saw_one { - s.push_str(", "); - }; - saw_one = true; - let borrow_data = &self.borrows.operator().borrows()[borrow]; - s.push_str(&borrow_data.to_string()); - }); - s.push_str("] "); - - s.push_str("borrows generated: ["); - let mut saw_one = false; - self.borrows.each_gen_bit(|borrow| { - if saw_one { - s.push_str(", "); - }; - saw_one = true; - let borrow_data = &self.borrows.operator().borrows()[borrow]; - s.push_str(&borrow_data.to_string()); - }); - s.push_str("] "); - - s.push_str("uninits: ["); - let mut saw_one = false; - self.uninits.each_state_bit(|mpi_uninit| { - if saw_one { - s.push_str(", "); - }; - saw_one = true; - let move_path = &self.uninits.operator().move_data().move_paths[mpi_uninit]; - s.push_str(&move_path.to_string()); - }); - s.push_str("] "); - - s.push_str("ever_init: ["); - let mut saw_one = false; - self.ever_inits.each_state_bit(|mpi_ever_init| { - if saw_one { - s.push_str(", "); - }; - saw_one = true; - let ever_init = &self.ever_inits.operator().move_data().inits[mpi_ever_init]; - s.push_str(&format!("{:?}", ever_init)); - }); - s.push_str("]"); - - fmt::Display::fmt(&s, fmt) - } -} diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs index 82a9c631b72..88173137bd2 100644 --- a/src/librustc_mir/borrow_check/mod.rs +++ b/src/librustc_mir/borrow_check/mod.rs @@ -4,8 +4,8 @@ use rustc::infer::InferCtxt; use rustc::lint::builtin::MUTABLE_BORROW_RESERVATION_CONFLICT; use rustc::lint::builtin::UNUSED_MUT; use rustc::mir::{ - read_only, Body, BodyAndCache, ClearCrossCrate, Local, Location, Mutability, Operand, Place, - PlaceElem, PlaceRef, ReadOnlyBodyAndCache, + read_only, traversal, Body, BodyAndCache, ClearCrossCrate, Local, Location, Mutability, + Operand, Place, PlaceElem, PlaceRef, ReadOnlyBodyAndCache, }; use rustc::mir::{AggregateKind, BasicBlock, BorrowCheckResult, BorrowKind}; use rustc::mir::{Field, ProjectionElem, Promoted, Rvalue, Statement, StatementKind}; @@ -21,6 +21,7 @@ use rustc_hir::{def_id::DefId, HirId, Node}; use rustc_index::bit_set::BitSet; use rustc_index::vec::IndexVec; +use either::Either; use smallvec::SmallVec; use std::cell::RefCell; use std::collections::BTreeMap; @@ -30,19 +31,17 @@ use std::rc::Rc; use rustc_span::{Span, DUMMY_SP}; use syntax::ast::Name; +use crate::dataflow; +use crate::dataflow::generic::{Analysis, BorrowckFlowState as Flows, BorrowckResults}; use crate::dataflow::indexes::{BorrowIndex, InitIndex, MoveOutIndex, MovePathIndex}; -use crate::dataflow::move_paths::{HasMoveData, InitLocation, LookupResult, MoveData, MoveError}; +use crate::dataflow::move_paths::{InitLocation, LookupResult, MoveData, MoveError}; use crate::dataflow::Borrows; -use crate::dataflow::DataflowResultsConsumer; use crate::dataflow::EverInitializedPlaces; -use crate::dataflow::FlowAtLocation; use crate::dataflow::MoveDataParamEnv; -use crate::dataflow::{do_dataflow, DebugFormatted}; use crate::dataflow::{MaybeInitializedPlaces, MaybeUninitializedPlaces}; use crate::transform::MirSource; use self::diagnostics::{AccessKind, RegionName}; -use self::flows::Flows; use self::location::LocationTable; use self::prefixes::PrefixSet; use self::MutateMode::{JustWrite, WriteAndRead}; @@ -54,7 +53,6 @@ mod constraint_generation; mod constraints; mod diagnostics; mod facts; -mod flows; mod invalidation; mod location; mod member_constraints; @@ -70,7 +68,7 @@ mod universal_regions; mod used_muts; crate use borrow_set::{BorrowData, BorrowSet}; -crate use nll::ToRegionVid; +crate use nll::{PoloniusOutput, ToRegionVid}; crate use place_ext::PlaceExt; crate use places_conflict::{places_conflict, PlaceConflictBias}; crate use region_infer::RegionInferenceContext; @@ -115,7 +113,6 @@ fn do_mir_borrowck<'a, 'tcx>( debug!("do_mir_borrowck(def_id = {:?})", def_id); let tcx = infcx.tcx; - let attributes = tcx.get_attrs(def_id); let param_env = tcx.param_env(def_id); let id = tcx.hir().as_local_hir_id(def_id).expect("do_mir_borrowck: non-local DefId"); @@ -188,16 +185,10 @@ fn do_mir_borrowck<'a, 'tcx>( let mdpe = MoveDataParamEnv { move_data, param_env }; - let dead_unwinds = BitSet::new_empty(body.basic_blocks().len()); - let mut flow_inits = FlowAtLocation::new(do_dataflow( - tcx, - &body, - def_id, - &attributes, - &dead_unwinds, - MaybeInitializedPlaces::new(tcx, &body, &mdpe), - |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]), - )); + let mut flow_inits = MaybeInitializedPlaces::new(tcx, &body, &mdpe) + .into_engine(tcx, &body, def_id) + .iterate_to_fixpoint() + .into_results_cursor(&body); let locals_are_invalidated_at_exit = tcx.hir().body_owner_kind(id).is_fn_or_closure(); let borrow_set = @@ -233,33 +224,15 @@ fn do_mir_borrowck<'a, 'tcx>( let regioncx = Rc::new(regioncx); - let flow_borrows = FlowAtLocation::new(do_dataflow( - tcx, - &body, - def_id, - &attributes, - &dead_unwinds, - Borrows::new(tcx, &body, regioncx.clone(), &borrow_set), - |rs, i| DebugFormatted::new(&rs.location(i)), - )); - let flow_uninits = FlowAtLocation::new(do_dataflow( - tcx, - &body, - def_id, - &attributes, - &dead_unwinds, - MaybeUninitializedPlaces::new(tcx, &body, &mdpe), - |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]), - )); - let flow_ever_inits = FlowAtLocation::new(do_dataflow( - tcx, - &body, - def_id, - &attributes, - &dead_unwinds, - EverInitializedPlaces::new(tcx, &body, &mdpe), - |bd, i| DebugFormatted::new(&bd.move_data().inits[i]), - )); + let flow_borrows = Borrows::new(tcx, &body, regioncx.clone(), &borrow_set) + .into_engine(tcx, &body, def_id) + .iterate_to_fixpoint(); + let flow_uninits = MaybeUninitializedPlaces::new(tcx, &body, &mdpe) + .into_engine(tcx, &body, def_id) + .iterate_to_fixpoint(); + let flow_ever_inits = EverInitializedPlaces::new(tcx, &body, &mdpe) + .into_engine(tcx, &body, def_id) + .iterate_to_fixpoint(); let movable_generator = match tcx.hir().get(id) { Node::Expr(&hir::Expr { @@ -294,17 +267,28 @@ fn do_mir_borrowck<'a, 'tcx>( local_names, region_names: RefCell::default(), next_region_name: RefCell::new(1), + polonius_output, }; // Compute and report region errors, if any. mbcx.report_region_errors(nll_errors); - let mut state = Flows::new(flow_borrows, flow_uninits, flow_ever_inits, polonius_output); + let results = BorrowckResults { + ever_inits: flow_ever_inits, + uninits: flow_uninits, + borrows: flow_borrows, + }; if let Some(errors) = move_errors { mbcx.report_move_errors(errors); } - mbcx.analyze_results(&mut state); // entry point for DataflowResultsConsumer + + dataflow::generic::visit_results( + &*body, + traversal::reverse_postorder(&*body).map(|(bb, _)| bb), + &results, + &mut mbcx, + ); // Convert any reservation warnings into lints. let reservation_warnings = mem::take(&mut mbcx.reservation_warnings); @@ -499,6 +483,9 @@ crate struct MirBorrowckCtxt<'cx, 'tcx> { /// The counter for generating new region names. next_region_name: RefCell<usize>, + + /// Results of Polonius analysis. + polonius_output: Option<Rc<PoloniusOutput>>, } // Check that: @@ -506,24 +493,16 @@ crate struct MirBorrowckCtxt<'cx, 'tcx> { // 2. loans made in overlapping scopes do not conflict // 3. assignments do not affect things loaned out as immutable // 4. moves do not affect things loaned out in any way -impl<'cx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx> { +impl<'cx, 'tcx> dataflow::generic::ResultsVisitor<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx> { type FlowState = Flows<'cx, 'tcx>; - fn body(&self) -> &'cx Body<'tcx> { - *self.body - } - - fn visit_block_entry(&mut self, bb: BasicBlock, flow_state: &Self::FlowState) { - debug!("MirBorrowckCtxt::process_block({:?}): {}", bb, flow_state); - } - - fn visit_statement_entry( + fn visit_statement( &mut self, - location: Location, + flow_state: &Flows<'cx, 'tcx>, stmt: &'cx Statement<'tcx>, - flow_state: &Self::FlowState, + location: Location, ) { - debug!("MirBorrowckCtxt::process_statement({:?}, {:?}): {}", location, stmt, flow_state); + debug!("MirBorrowckCtxt::process_statement({:?}, {:?}): {:?}", location, stmt, flow_state); let span = stmt.source_info.span; self.check_activations(location, span, flow_state); @@ -606,17 +585,16 @@ impl<'cx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx } } - fn visit_terminator_entry( + fn visit_terminator( &mut self, - location: Location, + flow_state: &Flows<'cx, 'tcx>, term: &'cx Terminator<'tcx>, - flow_state: &Self::FlowState, + loc: Location, ) { - let loc = location; - debug!("MirBorrowckCtxt::process_terminator({:?}, {:?}): {}", location, term, flow_state); + debug!("MirBorrowckCtxt::process_terminator({:?}, {:?}): {:?}", loc, term, flow_state); let span = term.source_info.span; - self.check_activations(location, span, flow_state); + self.check_activations(loc, span, flow_state); match term.kind { TerminatorKind::SwitchInt { ref discr, switch_ty: _, values: _, targets: _ } => { @@ -685,19 +663,40 @@ impl<'cx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx TerminatorKind::Yield { ref value, resume: _, ref resume_arg, drop: _ } => { self.consume_operand(loc, (value, span), flow_state); + self.mutate_place(loc, (resume_arg, span), Deep, JustWrite, flow_state); + } + TerminatorKind::Goto { target: _ } + | TerminatorKind::Abort + | TerminatorKind::Unreachable + | TerminatorKind::Resume + | TerminatorKind::Return + | TerminatorKind::GeneratorDrop + | TerminatorKind::FalseEdges { real_target: _, imaginary_target: _ } + | TerminatorKind::FalseUnwind { real_target: _, unwind: _ } => { + // no data used, thus irrelevant to borrowck + } + } + } + + fn visit_terminator_exit( + &mut self, + flow_state: &Flows<'cx, 'tcx>, + term: &'cx Terminator<'tcx>, + loc: Location, + ) { + let span = term.source_info.span; + + match term.kind { + TerminatorKind::Yield { value: _, resume: _, resume_arg: _, drop: _ } => { if self.movable_generator { // Look for any active borrows to locals let borrow_set = self.borrow_set.clone(); - flow_state.with_outgoing_borrows(|borrows| { - for i in borrows { - let borrow = &borrow_set[i]; - self.check_for_local_borrow(borrow, span); - } - }); + for i in flow_state.borrows.iter() { + let borrow = &borrow_set[i]; + self.check_for_local_borrow(borrow, span); + } } - - self.mutate_place(loc, (resume_arg, span), Deep, JustWrite, flow_state); } TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => { @@ -706,20 +705,22 @@ impl<'cx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx // StorageDead, but we don't always emit those (notably on unwind paths), // so this "extra check" serves as a kind of backup. let borrow_set = self.borrow_set.clone(); - flow_state.with_outgoing_borrows(|borrows| { - for i in borrows { - let borrow = &borrow_set[i]; - self.check_for_invalidation_at_exit(loc, borrow, span); - } - }); + for i in flow_state.borrows.iter() { + let borrow = &borrow_set[i]; + self.check_for_invalidation_at_exit(loc, borrow, span); + } } - TerminatorKind::Goto { target: _ } - | TerminatorKind::Abort - | TerminatorKind::Unreachable + + TerminatorKind::Abort + | TerminatorKind::Assert { .. } + | TerminatorKind::Call { .. } + | TerminatorKind::Drop { .. } + | TerminatorKind::DropAndReplace { .. } | TerminatorKind::FalseEdges { real_target: _, imaginary_target: _ } - | TerminatorKind::FalseUnwind { real_target: _, unwind: _ } => { - // no data used, thus irrelevant to borrowck - } + | TerminatorKind::FalseUnwind { real_target: _, unwind: _ } + | TerminatorKind::Goto { .. } + | TerminatorKind::SwitchInt { .. } + | TerminatorKind::Unreachable => {} } } } @@ -854,6 +855,10 @@ impl InitializationRequiringAction { } impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { + fn body(&self) -> &'cx Body<'tcx> { + *self.body + } + /// Checks an access to the given place to see if it is allowed. Examines the set of borrows /// that are in scope, as well as which paths have been initialized, to ensure that (a) the /// place is initialized and (b) it is not borrowed in some way that would prevent this @@ -933,8 +938,17 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { let tcx = self.infcx.tcx; let body = self.body; let body: &Body<'_> = &body; - let location_table = self.location_table.start_index(location); let borrow_set = self.borrow_set.clone(); + + // Use polonius output if it has been enabled. + let polonius_output = self.polonius_output.clone(); + let borrows_in_scope = if let Some(polonius) = &polonius_output { + let location = self.location_table.start_index(location); + Either::Left(polonius.errors_at(location).iter().copied()) + } else { + Either::Right(flow_state.borrows.iter()) + }; + each_borrow_involving_path( self, tcx, @@ -942,7 +956,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { location, (sd, place_span.0), &borrow_set, - flow_state.borrows_in_scope(location_table), + borrows_in_scope, |this, borrow_index, borrow| match (rw, borrow.kind) { // Obviously an activation is compatible with its own // reservation (or even prior activating uses of same @@ -1472,9 +1486,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { // initial reservation. } } -} -impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { fn check_if_reassignment_to_immutable_state( &mut self, location: Location, @@ -1564,21 +1576,26 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { location: Location, desired_action: InitializationRequiringAction, place_span: (PlaceRef<'cx, 'tcx>, Span), - maybe_uninits: &FlowAtLocation<'tcx, MaybeUninitializedPlaces<'cx, 'tcx>>, + maybe_uninits: &BitSet<MovePathIndex>, from: u32, to: u32, ) { if let Some(mpi) = self.move_path_for_place(place_span.0) { - let mut child = self.move_data.move_paths[mpi].first_child; + let move_paths = &self.move_data.move_paths; + let mut child = move_paths[mpi].first_child; while let Some(child_mpi) = child { - let child_move_place = &self.move_data.move_paths[child_mpi]; - let child_place = &child_move_place.place; - let last_proj = child_place.projection.last().unwrap(); + let child_move_path = &move_paths[child_mpi]; + let last_proj = child_move_path.place.projection.last().unwrap(); if let ProjectionElem::ConstantIndex { offset, from_end, .. } = last_proj { debug_assert!(!from_end, "Array constant indexing shouldn't be `from_end`."); if (from..to).contains(offset) { - if let Some(uninit_child) = maybe_uninits.has_any_child_of(child_mpi) { + let uninit_child = + self.move_data.find_in_move_path_or_its_descendants(child_mpi, |mpi| { + maybe_uninits.contains(mpi) + }); + + if let Some(uninit_child) = uninit_child { self.report_use_of_moved_or_uninitialized( location, desired_action, @@ -1589,7 +1606,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { } } } - child = child_move_place.next_sibling; + child = child_move_path.next_sibling; } } } @@ -1650,12 +1667,16 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { debug!("check_if_path_or_subpath_is_moved place: {:?}", place_span.0); if let Some(mpi) = self.move_path_for_place(place_span.0) { - if let Some(child_mpi) = maybe_uninits.has_any_child_of(mpi) { + let uninit_mpi = self + .move_data + .find_in_move_path_or_its_descendants(mpi, |mpi| maybe_uninits.contains(mpi)); + + if let Some(uninit_mpi) = uninit_mpi { self.report_use_of_moved_or_uninitialized( location, desired_action, (place_span.0, place_span.0, place_span.1), - child_mpi, + uninit_mpi, ); return; // don't bother finding other problems. } diff --git a/src/librustc_mir/borrow_check/nll.rs b/src/librustc_mir/borrow_check/nll.rs index 73718d58346..a71dfc9a778 100644 --- a/src/librustc_mir/borrow_check/nll.rs +++ b/src/librustc_mir/borrow_check/nll.rs @@ -20,8 +20,8 @@ use std::str::FromStr; use self::mir_util::PassWhere; use polonius_engine::{Algorithm, Output}; +use crate::dataflow::generic::ResultsCursor; use crate::dataflow::move_paths::{InitKind, InitLocation, MoveData}; -use crate::dataflow::FlowAtLocation; use crate::dataflow::MaybeInitializedPlaces; use crate::transform::MirSource; use crate::util as mir_util; @@ -149,7 +149,7 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>( promoted: &IndexVec<Promoted, ReadOnlyBodyAndCache<'_, 'tcx>>, location_table: &LocationTable, param_env: ty::ParamEnv<'tcx>, - flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'cx, 'tcx>>, + flow_inits: &mut ResultsCursor<'cx, 'tcx, MaybeInitializedPlaces<'cx, 'tcx>>, move_data: &MoveData<'tcx>, borrow_set: &BorrowSet<'tcx>, ) -> NllOutput<'tcx> { diff --git a/src/librustc_mir/borrow_check/type_check/liveness/mod.rs b/src/librustc_mir/borrow_check/type_check/liveness/mod.rs index e461ce739a7..cdf962ee31a 100644 --- a/src/librustc_mir/borrow_check/type_check/liveness/mod.rs +++ b/src/librustc_mir/borrow_check/type_check/liveness/mod.rs @@ -3,8 +3,8 @@ use rustc::ty::{RegionVid, TyCtxt}; use rustc_data_structures::fx::FxHashSet; use std::rc::Rc; +use crate::dataflow::generic::ResultsCursor; use crate::dataflow::move_paths::MoveData; -use crate::dataflow::FlowAtLocation; use crate::dataflow::MaybeInitializedPlaces; use crate::borrow_check::{ @@ -30,11 +30,11 @@ mod trace; /// /// N.B., this computation requires normalization; therefore, it must be /// performed before -pub(super) fn generate<'tcx>( +pub(super) fn generate<'mir, 'tcx>( typeck: &mut TypeChecker<'_, 'tcx>, body: ReadOnlyBodyAndCache<'_, 'tcx>, elements: &Rc<RegionValueElements>, - flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>, + flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, move_data: &MoveData<'tcx>, location_table: &LocationTable, ) { diff --git a/src/librustc_mir/borrow_check/type_check/liveness/trace.rs b/src/librustc_mir/borrow_check/type_check/liveness/trace.rs index ebb925ae0cb..198f4b4b42e 100644 --- a/src/librustc_mir/borrow_check/type_check/liveness/trace.rs +++ b/src/librustc_mir/borrow_check/type_check/liveness/trace.rs @@ -8,9 +8,10 @@ use rustc_data_structures::fx::{FxHashMap, FxHashSet}; use rustc_index::bit_set::HybridBitSet; use std::rc::Rc; +use crate::dataflow::generic::ResultsCursor; use crate::dataflow::indexes::MovePathIndex; -use crate::dataflow::move_paths::MoveData; -use crate::dataflow::{FlowAtLocation, FlowsAtLocation, MaybeInitializedPlaces}; +use crate::dataflow::move_paths::{HasMoveData, MoveData}; +use crate::dataflow::MaybeInitializedPlaces; use crate::borrow_check::{ region_infer::values::{self, PointIndex, RegionValueElements}, @@ -38,7 +39,7 @@ pub(super) fn trace( typeck: &mut TypeChecker<'_, 'tcx>, body: ReadOnlyBodyAndCache<'_, 'tcx>, elements: &Rc<RegionValueElements>, - flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>, + flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, move_data: &MoveData<'tcx>, live_locals: Vec<Local>, polonius_drop_used: Option<Vec<(Local, Location)>>, @@ -85,7 +86,7 @@ struct LivenessContext<'me, 'typeck, 'flow, 'tcx> { /// Results of dataflow tracking which variables (and paths) have been /// initialized. - flow_inits: &'me mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'flow, 'tcx>>, + flow_inits: &'me mut ResultsCursor<'flow, 'tcx, MaybeInitializedPlaces<'flow, 'tcx>>, /// Index indicating where each variable is assigned, used, or /// dropped. @@ -389,23 +390,26 @@ impl LivenessResults<'me, 'typeck, 'flow, 'tcx> { } impl LivenessContext<'_, '_, '_, 'tcx> { + /// Returns `true` if the local variable (or some part of it) is initialized at the current + /// cursor position. Callers should call one of the `seek` methods immediately before to point + /// the cursor to the desired location. + fn initialized_at_curr_loc(&self, mpi: MovePathIndex) -> bool { + let state = self.flow_inits.get(); + if state.contains(mpi) { + return true; + } + + let move_paths = &self.flow_inits.analysis().move_data().move_paths; + move_paths[mpi].find_descendant(&move_paths, |mpi| state.contains(mpi)).is_some() + } + /// Returns `true` if the local variable (or some part of it) is initialized in /// the terminator of `block`. We need to check this to determine if a /// DROP of some local variable will have an effect -- note that /// drops, as they may unwind, are always terminators. fn initialized_at_terminator(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool { - // Compute the set of initialized paths at terminator of block - // by resetting to the start of the block and then applying - // the effects of all statements. This is the only way to get - // "just ahead" of a terminator. - self.flow_inits.reset_to_entry_of(block); - for statement_index in 0..self.body[block].statements.len() { - let location = Location { block, statement_index }; - self.flow_inits.reconstruct_statement_effect(location); - self.flow_inits.apply_local_effect(location); - } - - self.flow_inits.has_any_child_of(mpi).is_some() + self.flow_inits.seek_before(self.body.terminator_loc(block)); + self.initialized_at_curr_loc(mpi) } /// Returns `true` if the path `mpi` (or some part of it) is initialized at @@ -414,8 +418,8 @@ impl LivenessContext<'_, '_, '_, 'tcx> { /// **Warning:** Does not account for the result of `Call` /// instructions. fn initialized_at_exit(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool { - self.flow_inits.reset_to_exit_of(block); - self.flow_inits.has_any_child_of(mpi).is_some() + self.flow_inits.seek_after(self.body.terminator_loc(block)); + self.initialized_at_curr_loc(mpi) } /// Stores the result that all regions in `value` are live for the diff --git a/src/librustc_mir/borrow_check/type_check/mod.rs b/src/librustc_mir/borrow_check/type_check/mod.rs index f645435cdf6..100fd7dc48d 100644 --- a/src/librustc_mir/borrow_check/type_check/mod.rs +++ b/src/librustc_mir/borrow_check/type_check/mod.rs @@ -34,8 +34,8 @@ use rustc_index::vec::{Idx, IndexVec}; use rustc_span::{Span, DUMMY_SP}; use syntax::ast; +use crate::dataflow::generic::ResultsCursor; use crate::dataflow::move_paths::MoveData; -use crate::dataflow::FlowAtLocation; use crate::dataflow::MaybeInitializedPlaces; use crate::transform::promote_consts::should_suggest_const_in_array_repeat_expressions_attribute; @@ -114,7 +114,7 @@ mod relate_tys; /// constraints for the regions in the types of variables /// - `flow_inits` -- results of a maybe-init dataflow analysis /// - `move_data` -- move-data constructed when performing the maybe-init dataflow analysis -pub(crate) fn type_check<'tcx>( +pub(crate) fn type_check<'mir, 'tcx>( infcx: &InferCtxt<'_, 'tcx>, param_env: ty::ParamEnv<'tcx>, body: ReadOnlyBodyAndCache<'_, 'tcx>, @@ -124,7 +124,7 @@ pub(crate) fn type_check<'tcx>( location_table: &LocationTable, borrow_set: &BorrowSet<'tcx>, all_facts: &mut Option<AllFacts>, - flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>, + flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, move_data: &MoveData<'tcx>, elements: &Rc<RegionValueElements>, ) -> MirTypeckResults<'tcx> { diff --git a/src/librustc_mir/dataflow/at_location.rs b/src/librustc_mir/dataflow/at_location.rs index c6d29211d45..e4eb8506846 100644 --- a/src/librustc_mir/dataflow/at_location.rs +++ b/src/librustc_mir/dataflow/at_location.rs @@ -4,7 +4,6 @@ use rustc::mir::{BasicBlock, Location}; use rustc_index::bit_set::{BitIter, BitSet, HybridBitSet}; -use crate::dataflow::move_paths::{HasMoveData, MovePathIndex}; use crate::dataflow::{BitDenotation, DataflowResults, GenKillSet}; use std::borrow::Borrow; @@ -168,43 +167,3 @@ where self.stmt_trans.apply(&mut self.curr_state) } } - -impl<'tcx, T, DR> FlowAtLocation<'tcx, T, DR> -where - T: HasMoveData<'tcx> + BitDenotation<'tcx, Idx = MovePathIndex>, - DR: Borrow<DataflowResults<'tcx, T>>, -{ - pub fn has_any_child_of(&self, mpi: T::Idx) -> Option<T::Idx> { - // We process `mpi` before the loop below, for two reasons: - // - it's a little different from the loop case (we don't traverse its - // siblings); - // - ~99% of the time the loop isn't reached, and this code is hot, so - // we don't want to allocate `todo` unnecessarily. - if self.contains(mpi) { - return Some(mpi); - } - let move_data = self.operator().move_data(); - let move_path = &move_data.move_paths[mpi]; - let mut todo = if let Some(child) = move_path.first_child { - vec![child] - } else { - return None; - }; - - while let Some(mpi) = todo.pop() { - if self.contains(mpi) { - return Some(mpi); - } - let move_path = &move_data.move_paths[mpi]; - if let Some(child) = move_path.first_child { - todo.push(child); - } - // After we've processed the original `mpi`, we should always - // traverse the siblings of any of its children. - if let Some(sibling) = move_path.next_sibling { - todo.push(sibling); - } - } - return None; - } -} diff --git a/src/librustc_mir/dataflow/generic/cursor.rs b/src/librustc_mir/dataflow/generic/cursor.rs index d2eff494ad7..8c0ab150528 100644 --- a/src/librustc_mir/dataflow/generic/cursor.rs +++ b/src/librustc_mir/dataflow/generic/cursor.rs @@ -65,6 +65,13 @@ where &self.state } + /// Returns `true` if the dataflow state at the current location contains the given element. + /// + /// Shorthand for `self.get().contains(elem)` + pub fn contains(&self, elem: A::Idx) -> bool { + self.state.contains(elem) + } + /// Resets the cursor to the start of the given basic block. pub fn seek_to_block_start(&mut self, block: BasicBlock) { self.state.overwrite(&self.results.borrow().entry_sets[block]); diff --git a/src/librustc_mir/dataflow/generic/engine.rs b/src/librustc_mir/dataflow/generic/engine.rs index 718c1e9ae20..b81f0adc201 100644 --- a/src/librustc_mir/dataflow/generic/engine.rs +++ b/src/librustc_mir/dataflow/generic/engine.rs @@ -44,15 +44,20 @@ where def_id: DefId, analysis: A, ) -> Self { + // If there are no back-edges in the control-flow graph, we only ever need to apply the + // transfer function for each block exactly once (assuming that we process blocks in RPO). + // + // In this case, there's no need to compute the block transfer functions ahead of time. + if !body.is_cfg_cyclic() { + return Self::new(tcx, body, def_id, analysis, None); + } + + // Otherwise, compute and store the cumulative transfer function for each block. + let bits_per_block = analysis.bits_per_block(body); let mut trans_for_block = IndexVec::from_elem(GenKillSet::identity(bits_per_block), body.basic_blocks()); - // Compute cumulative block transfer functions. - // - // FIXME: we may want to skip this if the MIR is acyclic, since we will never access a - // block transfer function more than once. - for (block, block_data) in body.basic_blocks().iter_enumerated() { let trans = &mut trans_for_block[block]; @@ -62,11 +67,10 @@ where analysis.statement_effect(trans, statement, loc); } - if let Some(terminator) = &block_data.terminator { - let loc = Location { block, statement_index: block_data.statements.len() }; - analysis.before_terminator_effect(trans, terminator, loc); - analysis.terminator_effect(trans, terminator, loc); - } + let terminator = block_data.terminator(); + let loc = Location { block, statement_index: block_data.statements.len() }; + analysis.before_terminator_effect(trans, terminator, loc); + analysis.terminator_effect(trans, terminator, loc); } Self::new(tcx, body, def_id, analysis, Some(trans_for_block)) diff --git a/src/librustc_mir/dataflow/generic/mod.rs b/src/librustc_mir/dataflow/generic/mod.rs index c9b4f875ebd..ea643042c5f 100644 --- a/src/librustc_mir/dataflow/generic/mod.rs +++ b/src/librustc_mir/dataflow/generic/mod.rs @@ -35,6 +35,8 @@ use std::io; use rustc::mir::{self, BasicBlock, Location}; +use rustc::ty::TyCtxt; +use rustc_hir::def_id::DefId; use rustc_index::bit_set::{BitSet, HybridBitSet}; use rustc_index::vec::{Idx, IndexVec}; @@ -43,9 +45,12 @@ use crate::dataflow::BottomValue; mod cursor; mod engine; mod graphviz; +mod visitor; pub use self::cursor::{ResultsCursor, ResultsRefCursor}; pub use self::engine::Engine; +pub use self::visitor::{visit_results, ResultsVisitor}; +pub use self::visitor::{BorrowckFlowState, BorrowckResults}; /// A dataflow analysis that has converged to fixpoint. pub struct Results<'tcx, A> @@ -166,6 +171,30 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { args: &[mir::Operand<'tcx>], return_place: &mir::Place<'tcx>, ); + + /// Calls the appropriate `Engine` constructor to find the fixpoint for this dataflow problem. + /// + /// You shouldn't need to override this outside this module, since the combination of the + /// default impl and the one for all `A: GenKillAnalysis` will do the right thing. + /// Its purpose is to enable method chaining like so: + /// + /// ```ignore(cross-crate-imports) + /// let results = MyAnalysis::new(tcx, body) + /// .into_engine(tcx, body, def_id) + /// .iterate_to_fixpoint() + /// .into_results_cursor(body); + /// ``` + fn into_engine( + self, + tcx: TyCtxt<'tcx>, + body: &'mir mir::Body<'tcx>, + def_id: DefId, + ) -> Engine<'mir, 'tcx, Self> + where + Self: Sized, + { + Engine::new_generic(tcx, body, def_id, self) + } } /// A gen/kill dataflow problem. @@ -272,6 +301,18 @@ where ) { self.call_return_effect(state, block, func, args, return_place); } + + fn into_engine( + self, + tcx: TyCtxt<'tcx>, + body: &'mir mir::Body<'tcx>, + def_id: DefId, + ) -> Engine<'mir, 'tcx, Self> + where + Self: Sized, + { + Engine::new_gen_kill(tcx, body, def_id, self) + } } /// The legal operations for a transfer function in a gen/kill problem. diff --git a/src/librustc_mir/dataflow/generic/visitor.rs b/src/librustc_mir/dataflow/generic/visitor.rs new file mode 100644 index 00000000000..5bad8c61a0c --- /dev/null +++ b/src/librustc_mir/dataflow/generic/visitor.rs @@ -0,0 +1,272 @@ +use rustc::mir::{self, BasicBlock, Location}; +use rustc_index::bit_set::BitSet; + +use super::{Analysis, Results}; +use crate::dataflow::impls::{borrows::Borrows, EverInitializedPlaces, MaybeUninitializedPlaces}; + +/// Calls the corresponding method in `ResultsVisitor` for every location in a `mir::Body` with the +/// dataflow state at that location. +pub fn visit_results<F>( + body: &'mir mir::Body<'tcx>, + blocks: impl IntoIterator<Item = BasicBlock>, + results: &impl ResultsVisitable<'tcx, FlowState = F>, + vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = F>, +) { + let mut state = results.new_flow_state(body); + + for block in blocks { + let block_data = &body[block]; + results.reset_to_block_start(&mut state, block); + + for (statement_index, stmt) in block_data.statements.iter().enumerate() { + let loc = Location { block, statement_index }; + + results.reconstruct_before_statement_effect(&mut state, stmt, loc); + vis.visit_statement(&mut state, stmt, loc); + + results.reconstruct_statement_effect(&mut state, stmt, loc); + vis.visit_statement_exit(&mut state, stmt, loc); + } + + let loc = body.terminator_loc(block); + let term = block_data.terminator(); + + results.reconstruct_before_terminator_effect(&mut state, term, loc); + vis.visit_terminator(&mut state, term, loc); + + results.reconstruct_terminator_effect(&mut state, term, loc); + vis.visit_terminator_exit(&mut state, term, loc); + } +} + +pub trait ResultsVisitor<'mir, 'tcx> { + type FlowState; + + /// Called with the `before_statement_effect` of the given statement applied to `state` but not + /// its `statement_effect`. + fn visit_statement( + &mut self, + _state: &Self::FlowState, + _statement: &'mir mir::Statement<'tcx>, + _location: Location, + ) { + } + + /// Called with both the `before_statement_effect` and the `statement_effect` of the given + /// statement applied to `state`. + fn visit_statement_exit( + &mut self, + _state: &Self::FlowState, + _statement: &'mir mir::Statement<'tcx>, + _location: Location, + ) { + } + + /// Called with the `before_terminator_effect` of the given terminator applied to `state` but not + /// its `terminator_effect`. + fn visit_terminator( + &mut self, + _state: &Self::FlowState, + _terminator: &'mir mir::Terminator<'tcx>, + _location: Location, + ) { + } + + /// Called with both the `before_terminator_effect` and the `terminator_effect` of the given + /// terminator applied to `state`. + /// + /// The `call_return_effect` (if one exists) will *not* be applied to `state`. + fn visit_terminator_exit( + &mut self, + _state: &Self::FlowState, + _terminator: &'mir mir::Terminator<'tcx>, + _location: Location, + ) { + } +} + +/// Things that can be visited by a `ResultsVisitor`. +/// +/// This trait exists so that we can visit the results of multiple dataflow analyses simultaneously. +/// DO NOT IMPLEMENT MANUALLY. Instead, use the `impl_visitable` macro below. +pub trait ResultsVisitable<'tcx> { + type FlowState; + + /// Creates an empty `FlowState` to hold the transient state for these dataflow results. + /// + /// The value of the newly created `FlowState` will be overwritten by `reset_to_block_start` + /// before it can be observed by a `ResultsVisitor`. + fn new_flow_state(&self, body: &mir::Body<'tcx>) -> Self::FlowState; + + fn reset_to_block_start(&self, state: &mut Self::FlowState, block: BasicBlock); + + fn reconstruct_before_statement_effect( + &self, + state: &mut Self::FlowState, + statement: &mir::Statement<'tcx>, + location: Location, + ); + + fn reconstruct_statement_effect( + &self, + state: &mut Self::FlowState, + statement: &mir::Statement<'tcx>, + location: Location, + ); + + fn reconstruct_before_terminator_effect( + &self, + state: &mut Self::FlowState, + terminator: &mir::Terminator<'tcx>, + location: Location, + ); + + fn reconstruct_terminator_effect( + &self, + state: &mut Self::FlowState, + terminator: &mir::Terminator<'tcx>, + location: Location, + ); +} + +impl<'tcx, A> ResultsVisitable<'tcx> for Results<'tcx, A> +where + A: Analysis<'tcx>, +{ + type FlowState = BitSet<A::Idx>; + + fn new_flow_state(&self, body: &mir::Body<'tcx>) -> Self::FlowState { + BitSet::new_empty(self.analysis.bits_per_block(body)) + } + + fn reset_to_block_start(&self, state: &mut Self::FlowState, block: BasicBlock) { + state.overwrite(&self.entry_set_for_block(block)); + } + + fn reconstruct_before_statement_effect( + &self, + state: &mut Self::FlowState, + stmt: &mir::Statement<'tcx>, + loc: Location, + ) { + self.analysis.apply_before_statement_effect(state, stmt, loc); + } + + fn reconstruct_statement_effect( + &self, + state: &mut Self::FlowState, + stmt: &mir::Statement<'tcx>, + loc: Location, + ) { + self.analysis.apply_statement_effect(state, stmt, loc); + } + + fn reconstruct_before_terminator_effect( + &self, + state: &mut Self::FlowState, + term: &mir::Terminator<'tcx>, + loc: Location, + ) { + self.analysis.apply_before_terminator_effect(state, term, loc); + } + + fn reconstruct_terminator_effect( + &self, + state: &mut Self::FlowState, + term: &mir::Terminator<'tcx>, + loc: Location, + ) { + self.analysis.apply_terminator_effect(state, term, loc); + } +} + +/// A tuple with named fields that can hold either the results or the transient state of the +/// dataflow analyses used by the borrow checker. +#[derive(Debug)] +pub struct BorrowckAnalyses<B, U, E> { + pub borrows: B, + pub uninits: U, + pub ever_inits: E, +} + +/// The results of the dataflow analyses used by the borrow checker. +pub type BorrowckResults<'mir, 'tcx> = BorrowckAnalyses< + Results<'tcx, Borrows<'mir, 'tcx>>, + Results<'tcx, MaybeUninitializedPlaces<'mir, 'tcx>>, + Results<'tcx, EverInitializedPlaces<'mir, 'tcx>>, +>; + +/// The transient state of the dataflow analyses used by the borrow checker. +pub type BorrowckFlowState<'mir, 'tcx> = + <BorrowckResults<'mir, 'tcx> as ResultsVisitable<'tcx>>::FlowState; + +macro_rules! impl_visitable { + ( $( + $T:ident { $( $field:ident : $A:ident ),* $(,)? } + )* ) => { $( + impl<'tcx, $($A),*> ResultsVisitable<'tcx> for $T<$( Results<'tcx, $A> ),*> + where + $( $A: Analysis<'tcx>, )* + { + type FlowState = $T<$( BitSet<$A::Idx> ),*>; + + fn new_flow_state(&self, body: &mir::Body<'tcx>) -> Self::FlowState { + $T { + $( $field: BitSet::new_empty(self.$field.analysis.bits_per_block(body)) ),* + } + } + + fn reset_to_block_start( + &self, + state: &mut Self::FlowState, + block: BasicBlock, + ) { + $( state.$field.overwrite(&self.$field.entry_sets[block]); )* + } + + fn reconstruct_before_statement_effect( + &self, + state: &mut Self::FlowState, + stmt: &mir::Statement<'tcx>, + loc: Location, + ) { + $( self.$field.analysis + .apply_before_statement_effect(&mut state.$field, stmt, loc); )* + } + + fn reconstruct_statement_effect( + &self, + state: &mut Self::FlowState, + stmt: &mir::Statement<'tcx>, + loc: Location, + ) { + $( self.$field.analysis + .apply_statement_effect(&mut state.$field, stmt, loc); )* + } + + fn reconstruct_before_terminator_effect( + &self, + state: &mut Self::FlowState, + term: &mir::Terminator<'tcx>, + loc: Location, + ) { + $( self.$field.analysis + .apply_before_terminator_effect(&mut state.$field, term, loc); )* + } + + fn reconstruct_terminator_effect( + &self, + state: &mut Self::FlowState, + term: &mir::Terminator<'tcx>, + loc: Location, + ) { + $( self.$field.analysis + .apply_terminator_effect(&mut state.$field, term, loc); )* + } + } + )* } +} + +impl_visitable! { + BorrowckAnalyses { borrows: B, uninits: U, ever_inits: E } +} diff --git a/src/librustc_mir/dataflow/impls/borrows.rs b/src/librustc_mir/dataflow/impls/borrows.rs index f94ee67f2be..74d1094f964 100644 --- a/src/librustc_mir/dataflow/impls/borrows.rs +++ b/src/librustc_mir/dataflow/impls/borrows.rs @@ -4,13 +4,12 @@ use rustc::ty::TyCtxt; use rustc_data_structures::fx::FxHashMap; use rustc_index::bit_set::BitSet; -use rustc_index::vec::IndexVec; use crate::borrow_check::{ - places_conflict, BorrowData, BorrowSet, PlaceConflictBias, PlaceExt, RegionInferenceContext, - ToRegionVid, + places_conflict, BorrowSet, PlaceConflictBias, PlaceExt, RegionInferenceContext, ToRegionVid, }; -use crate::dataflow::{BitDenotation, BottomValue, GenKillSet}; +use crate::dataflow::generic::{self, GenKill}; +use crate::dataflow::BottomValue; use std::rc::Rc; @@ -160,10 +159,6 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> { } } - crate fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { - &self.borrow_set.borrows - } - pub fn location(&self, idx: BorrowIndex) -> &Location { &self.borrow_set.borrows[idx].reserve_location } @@ -172,7 +167,7 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> { /// That means they went out of a nonlexical scope fn kill_loans_out_of_scope_at_location( &self, - trans: &mut GenKillSet<BorrowIndex>, + trans: &mut impl GenKill<BorrowIndex>, location: Location, ) { // NOTE: The state associated with a given `location` @@ -187,16 +182,21 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> { // region, then setting that gen-bit will override any // potential kill introduced here. if let Some(indices) = self.borrows_out_of_scope_at_location.get(&location) { - trans.kill_all(indices); + trans.kill_all(indices.iter().copied()); } } /// Kill any borrows that conflict with `place`. - fn kill_borrows_on_place(&self, trans: &mut GenKillSet<BorrowIndex>, place: &Place<'tcx>) { + fn kill_borrows_on_place(&self, trans: &mut impl GenKill<BorrowIndex>, place: &Place<'tcx>) { debug!("kill_borrows_on_place: place={:?}", place); - let other_borrows_of_local = - self.borrow_set.local_map.get(&place.local).into_iter().flat_map(|bs| bs.into_iter()); + let other_borrows_of_local = self + .borrow_set + .local_map + .get(&place.local) + .into_iter() + .flat_map(|bs| bs.into_iter()) + .copied(); // If the borrowed place is a local with no projections, all other borrows of this // local must conflict. This is purely an optimization so we don't have to call @@ -212,7 +212,7 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> { // pair of array indices are unequal, so that when `places_conflict` returns true, we // will be assured that two places being compared definitely denotes the same sets of // locations. - let definitely_conflicting_borrows = other_borrows_of_local.filter(|&&i| { + let definitely_conflicting_borrows = other_borrows_of_local.filter(|&i| { places_conflict( self.tcx, self.body, @@ -226,36 +226,41 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> { } } -impl<'a, 'tcx> BitDenotation<'tcx> for Borrows<'a, 'tcx> { +impl<'tcx> generic::AnalysisDomain<'tcx> for Borrows<'_, 'tcx> { type Idx = BorrowIndex; - fn name() -> &'static str { - "borrows" - } - fn bits_per_block(&self) -> usize { + + const NAME: &'static str = "borrows"; + + fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize { self.borrow_set.borrows.len() * 2 } - fn start_block_effect(&self, _entry_set: &mut BitSet<Self::Idx>) { + fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut BitSet<Self::Idx>) { // no borrows of code region_scopes have been taken prior to // function execution, so this method has no effect. } - fn before_statement_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { - debug!("Borrows::before_statement_effect trans: {:?} location: {:?}", trans, location); - self.kill_loans_out_of_scope_at_location(trans, location); + fn pretty_print_idx(&self, w: &mut impl std::io::Write, idx: Self::Idx) -> std::io::Result<()> { + write!(w, "{:?}", self.location(idx)) } +} - fn statement_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { - debug!("Borrows::statement_effect: trans={:?} location={:?}", trans, location); - - let block = &self.body.basic_blocks().get(location.block).unwrap_or_else(|| { - panic!("could not find block at location {:?}", location); - }); - let stmt = block.statements.get(location.statement_index).unwrap_or_else(|| { - panic!("could not find statement at location {:?}"); - }); +impl<'tcx> generic::GenKillAnalysis<'tcx> for Borrows<'_, 'tcx> { + fn before_statement_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + _statement: &mir::Statement<'tcx>, + location: Location, + ) { + self.kill_loans_out_of_scope_at_location(trans, location); + } - debug!("Borrows::statement_effect: stmt={:?}", stmt); + fn statement_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + stmt: &mir::Statement<'tcx>, + location: Location, + ) { match stmt.kind { mir::StatementKind::Assign(box (ref lhs, ref rhs)) => { if let mir::Rvalue::Ref(_, _, ref place) = *rhs { @@ -301,18 +306,29 @@ impl<'a, 'tcx> BitDenotation<'tcx> for Borrows<'a, 'tcx> { } } - fn before_terminator_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { - debug!("Borrows::before_terminator_effect: trans={:?} location={:?}", trans, location); + fn before_terminator_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + _terminator: &mir::Terminator<'tcx>, + location: Location, + ) { self.kill_loans_out_of_scope_at_location(trans, location); } - fn terminator_effect(&self, _: &mut GenKillSet<Self::Idx>, _: Location) {} + fn terminator_effect( + &self, + _: &mut impl GenKill<Self::Idx>, + _: &mir::Terminator<'tcx>, + _: Location, + ) { + } - fn propagate_call_return( + fn call_return_effect( &self, - _in_out: &mut BitSet<BorrowIndex>, - _call_bb: mir::BasicBlock, - _dest_bb: mir::BasicBlock, + _trans: &mut impl GenKill<Self::Idx>, + _block: mir::BasicBlock, + _func: &mir::Operand<'tcx>, + _args: &[mir::Operand<'tcx>], _dest_place: &mir::Place<'tcx>, ) { } diff --git a/src/librustc_mir/dataflow/impls/mod.rs b/src/librustc_mir/dataflow/impls/mod.rs index 6b66406338d..5b2264c2a65 100644 --- a/src/librustc_mir/dataflow/impls/mod.rs +++ b/src/librustc_mir/dataflow/impls/mod.rs @@ -11,8 +11,9 @@ use super::MoveDataParamEnv; use crate::util::elaborate_drops::DropFlagState; +use super::generic::{AnalysisDomain, GenKill, GenKillAnalysis}; use super::move_paths::{HasMoveData, InitIndex, InitKind, MoveData, MovePathIndex}; -use super::{BitDenotation, BottomValue, GenKillSet}; +use super::{BottomValue, GenKillSet}; use super::drop_flag_effects_for_function_entry; use super::drop_flag_effects_for_location; @@ -216,6 +217,7 @@ impl<'a, 'tcx> HasMoveData<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> { /// } /// ``` pub struct EverInitializedPlaces<'a, 'tcx> { + #[allow(dead_code)] tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, mdpe: &'a MoveDataParamEnv<'tcx>, @@ -235,7 +237,7 @@ impl<'a, 'tcx> HasMoveData<'tcx> for EverInitializedPlaces<'a, 'tcx> { impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> { fn update_bits( - trans: &mut GenKillSet<MovePathIndex>, + trans: &mut impl GenKill<MovePathIndex>, path: MovePathIndex, state: DropFlagState, ) { @@ -248,7 +250,7 @@ impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> { impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> { fn update_bits( - trans: &mut GenKillSet<MovePathIndex>, + trans: &mut impl GenKill<MovePathIndex>, path: MovePathIndex, state: DropFlagState, ) { @@ -261,7 +263,7 @@ impl<'a, 'tcx> MaybeUninitializedPlaces<'a, 'tcx> { impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> { fn update_bits( - trans: &mut GenKillSet<MovePathIndex>, + trans: &mut impl GenKill<MovePathIndex>, path: MovePathIndex, state: DropFlagState, ) { @@ -272,39 +274,56 @@ impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> { } } -impl<'a, 'tcx> BitDenotation<'tcx> for MaybeInitializedPlaces<'a, 'tcx> { +impl<'tcx> AnalysisDomain<'tcx> for MaybeInitializedPlaces<'_, 'tcx> { type Idx = MovePathIndex; - fn name() -> &'static str { - "maybe_init" - } - fn bits_per_block(&self) -> usize { + + const NAME: &'static str = "maybe_init"; + + fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize { self.move_data().move_paths.len() } - fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) { + fn initialize_start_block(&self, _: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) { drop_flag_effects_for_function_entry(self.tcx, self.body, self.mdpe, |path, s| { assert!(s == DropFlagState::Present); - entry_set.insert(path); + state.insert(path); }); } - fn statement_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { + fn pretty_print_idx(&self, w: &mut impl std::io::Write, mpi: Self::Idx) -> std::io::Result<()> { + write!(w, "{}", self.move_data().move_paths[mpi]) + } +} + +impl<'tcx> GenKillAnalysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx> { + fn statement_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + _statement: &mir::Statement<'tcx>, + location: Location, + ) { drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| { Self::update_bits(trans, path, s) }) } - fn terminator_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { + fn terminator_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + _terminator: &mir::Terminator<'tcx>, + location: Location, + ) { drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| { Self::update_bits(trans, path, s) }) } - fn propagate_call_return( + fn call_return_effect( &self, - in_out: &mut BitSet<MovePathIndex>, - _call_bb: mir::BasicBlock, - _dest_bb: mir::BasicBlock, + trans: &mut impl GenKill<Self::Idx>, + _block: mir::BasicBlock, + _func: &mir::Operand<'tcx>, + _args: &[mir::Operand<'tcx>], dest_place: &mir::Place<'tcx>, ) { // when a call returns successfully, that means we need to set @@ -315,50 +334,67 @@ impl<'a, 'tcx> BitDenotation<'tcx> for MaybeInitializedPlaces<'a, 'tcx> { self.move_data(), self.move_data().rev_lookup.find(dest_place.as_ref()), |mpi| { - in_out.insert(mpi); + trans.gen(mpi); }, ); } } -impl<'a, 'tcx> BitDenotation<'tcx> for MaybeUninitializedPlaces<'a, 'tcx> { +impl<'tcx> AnalysisDomain<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> { type Idx = MovePathIndex; - fn name() -> &'static str { - "maybe_uninit" - } - fn bits_per_block(&self) -> usize { + + const NAME: &'static str = "maybe_uninit"; + + fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize { self.move_data().move_paths.len() } // sets on_entry bits for Arg places - fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) { + fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) { // set all bits to 1 (uninit) before gathering counterevidence - assert!(self.bits_per_block() == entry_set.domain_size()); - entry_set.insert_all(); + assert!(self.bits_per_block(body) == state.domain_size()); + state.insert_all(); drop_flag_effects_for_function_entry(self.tcx, self.body, self.mdpe, |path, s| { assert!(s == DropFlagState::Present); - entry_set.remove(path); + state.remove(path); }); } - fn statement_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { + fn pretty_print_idx(&self, w: &mut impl std::io::Write, mpi: Self::Idx) -> std::io::Result<()> { + write!(w, "{}", self.move_data().move_paths[mpi]) + } +} + +impl<'tcx> GenKillAnalysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> { + fn statement_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + _statement: &mir::Statement<'tcx>, + location: Location, + ) { drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| { Self::update_bits(trans, path, s) }) } - fn terminator_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { + fn terminator_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + _terminator: &mir::Terminator<'tcx>, + location: Location, + ) { drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| { Self::update_bits(trans, path, s) }) } - fn propagate_call_return( + fn call_return_effect( &self, - in_out: &mut BitSet<MovePathIndex>, - _call_bb: mir::BasicBlock, - _dest_bb: mir::BasicBlock, + trans: &mut impl GenKill<Self::Idx>, + _block: mir::BasicBlock, + _func: &mir::Operand<'tcx>, + _args: &[mir::Operand<'tcx>], dest_place: &mir::Place<'tcx>, ) { // when a call returns successfully, that means we need to set @@ -369,48 +405,65 @@ impl<'a, 'tcx> BitDenotation<'tcx> for MaybeUninitializedPlaces<'a, 'tcx> { self.move_data(), self.move_data().rev_lookup.find(dest_place.as_ref()), |mpi| { - in_out.remove(mpi); + trans.kill(mpi); }, ); } } -impl<'a, 'tcx> BitDenotation<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> { +impl<'a, 'tcx> AnalysisDomain<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> { type Idx = MovePathIndex; - fn name() -> &'static str { - "definite_init" - } - fn bits_per_block(&self) -> usize { + + const NAME: &'static str = "definite_init"; + + fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize { self.move_data().move_paths.len() } // sets on_entry bits for Arg places - fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) { - entry_set.clear(); + fn initialize_start_block(&self, _: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) { + state.clear(); drop_flag_effects_for_function_entry(self.tcx, self.body, self.mdpe, |path, s| { assert!(s == DropFlagState::Present); - entry_set.insert(path); + state.insert(path); }); } - fn statement_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { + fn pretty_print_idx(&self, w: &mut impl std::io::Write, mpi: Self::Idx) -> std::io::Result<()> { + write!(w, "{}", self.move_data().move_paths[mpi]) + } +} + +impl<'tcx> GenKillAnalysis<'tcx> for DefinitelyInitializedPlaces<'_, 'tcx> { + fn statement_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + _statement: &mir::Statement<'tcx>, + location: Location, + ) { drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| { Self::update_bits(trans, path, s) }) } - fn terminator_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { + fn terminator_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + _terminator: &mir::Terminator<'tcx>, + location: Location, + ) { drop_flag_effects_for_location(self.tcx, self.body, self.mdpe, location, |path, s| { Self::update_bits(trans, path, s) }) } - fn propagate_call_return( + fn call_return_effect( &self, - in_out: &mut BitSet<MovePathIndex>, - _call_bb: mir::BasicBlock, - _dest_bb: mir::BasicBlock, + trans: &mut impl GenKill<Self::Idx>, + _block: mir::BasicBlock, + _func: &mir::Operand<'tcx>, + _args: &[mir::Operand<'tcx>], dest_place: &mir::Place<'tcx>, ) { // when a call returns successfully, that means we need to set @@ -421,30 +474,36 @@ impl<'a, 'tcx> BitDenotation<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> { self.move_data(), self.move_data().rev_lookup.find(dest_place.as_ref()), |mpi| { - in_out.insert(mpi); + trans.gen(mpi); }, ); } } -impl<'a, 'tcx> BitDenotation<'tcx> for EverInitializedPlaces<'a, 'tcx> { +impl<'tcx> AnalysisDomain<'tcx> for EverInitializedPlaces<'_, 'tcx> { type Idx = InitIndex; - fn name() -> &'static str { - "ever_init" - } - fn bits_per_block(&self) -> usize { + + const NAME: &'static str = "ever_init"; + + fn bits_per_block(&self, _: &mir::Body<'tcx>) -> usize { self.move_data().inits.len() } - fn start_block_effect(&self, entry_set: &mut BitSet<InitIndex>) { - for arg_init in 0..self.body.arg_count { - entry_set.insert(InitIndex::new(arg_init)); + fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) { + for arg_init in 0..body.arg_count { + state.insert(InitIndex::new(arg_init)); } } +} - fn statement_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { - let (_, body, move_data) = (self.tcx, self.body, self.move_data()); - let stmt = &body[location.block].statements[location.statement_index]; +impl<'tcx> GenKillAnalysis<'tcx> for EverInitializedPlaces<'_, 'tcx> { + fn statement_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + stmt: &mir::Statement<'tcx>, + location: Location, + ) { + let move_data = self.move_data(); let init_path_map = &move_data.init_path_map; let init_loc_map = &move_data.init_loc_map; let rev_lookup = &move_data.rev_lookup; @@ -453,7 +512,7 @@ impl<'a, 'tcx> BitDenotation<'tcx> for EverInitializedPlaces<'a, 'tcx> { "statement {:?} at loc {:?} initializes move_indexes {:?}", stmt, location, &init_loc_map[location] ); - trans.gen_all(&init_loc_map[location]); + trans.gen_all(init_loc_map[location].iter().copied()); match stmt.kind { mir::StatementKind::StorageDead(local) => { @@ -464,13 +523,18 @@ impl<'a, 'tcx> BitDenotation<'tcx> for EverInitializedPlaces<'a, 'tcx> { "stmt {:?} at loc {:?} clears the ever initialized status of {:?}", stmt, location, &init_path_map[move_path_index] ); - trans.kill_all(&init_path_map[move_path_index]); + trans.kill_all(init_path_map[move_path_index].iter().copied()); } _ => {} } } - fn terminator_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location) { + fn terminator_effect( + &self, + trans: &mut impl GenKill<Self::Idx>, + _terminator: &mir::Terminator<'tcx>, + location: Location, + ) { let (body, move_data) = (self.body, self.move_data()); let term = body[location.block].terminator(); let init_loc_map = &move_data.init_loc_map; @@ -479,28 +543,29 @@ impl<'a, 'tcx> BitDenotation<'tcx> for EverInitializedPlaces<'a, 'tcx> { term, location, &init_loc_map[location] ); trans.gen_all( - init_loc_map[location].iter().filter(|init_index| { - move_data.inits[**init_index].kind != InitKind::NonPanicPathOnly - }), + init_loc_map[location] + .iter() + .filter(|init_index| { + move_data.inits[**init_index].kind != InitKind::NonPanicPathOnly + }) + .copied(), ); } - fn propagate_call_return( + fn call_return_effect( &self, - in_out: &mut BitSet<InitIndex>, - call_bb: mir::BasicBlock, - _dest_bb: mir::BasicBlock, + trans: &mut impl GenKill<Self::Idx>, + block: mir::BasicBlock, + _func: &mir::Operand<'tcx>, + _args: &[mir::Operand<'tcx>], _dest_place: &mir::Place<'tcx>, ) { let move_data = self.move_data(); - let bits_per_block = self.bits_per_block(); let init_loc_map = &move_data.init_loc_map; - let call_loc = - Location { block: call_bb, statement_index: self.body[call_bb].statements.len() }; + let call_loc = self.body.terminator_loc(block); for init_index in &init_loc_map[call_loc] { - assert!(init_index.index() < bits_per_block); - in_out.insert(*init_index); + trans.gen(*init_index); } } } diff --git a/src/librustc_mir/dataflow/move_paths/mod.rs b/src/librustc_mir/dataflow/move_paths/mod.rs index 8d62b84bda8..614a2761643 100644 --- a/src/librustc_mir/dataflow/move_paths/mod.rs +++ b/src/librustc_mir/dataflow/move_paths/mod.rs @@ -72,6 +72,41 @@ impl<'tcx> MovePath<'tcx> { parents } + + /// Finds the closest descendant of `self` for which `f` returns `true` using a breadth-first + /// search. + /// + /// `f` will **not** be called on `self`. + pub fn find_descendant( + &self, + move_paths: &IndexVec<MovePathIndex, MovePath<'_>>, + f: impl Fn(MovePathIndex) -> bool, + ) -> Option<MovePathIndex> { + let mut todo = if let Some(child) = self.first_child { + vec![child] + } else { + return None; + }; + + while let Some(mpi) = todo.pop() { + if f(mpi) { + return Some(mpi); + } + + let move_path = &move_paths[mpi]; + if let Some(child) = move_path.first_child { + todo.push(child); + } + + // After we've processed the original `mpi`, we should always + // traverse the siblings of any of its children. + if let Some(sibling) = move_path.next_sibling { + todo.push(sibling); + } + } + + None + } } impl<'tcx> fmt::Debug for MovePath<'tcx> { @@ -333,4 +368,16 @@ impl<'tcx> MoveData<'tcx> { } } } + + pub fn find_in_move_path_or_its_descendants( + &self, + root: MovePathIndex, + pred: impl Fn(MovePathIndex) -> bool, + ) -> Option<MovePathIndex> { + if pred(root) { + return Some(root); + } + + self.move_paths[root].find_descendant(&self.move_paths, pred) + } } diff --git a/src/librustc_mir/transform/check_consts/validation.rs b/src/librustc_mir/transform/check_consts/validation.rs index 94c2f77335c..e9715f682b0 100644 --- a/src/librustc_mir/transform/check_consts/validation.rs +++ b/src/librustc_mir/transform/check_consts/validation.rs @@ -22,6 +22,7 @@ use super::resolver::FlowSensitiveAnalysis; use super::{is_lang_panic_fn, ConstKind, Item, Qualif}; use crate::const_eval::{is_const_fn, is_unstable_const_fn}; use crate::dataflow::{self as old_dataflow, generic as dataflow}; +use dataflow::Analysis; pub type IndirectlyMutableResults<'mir, 'tcx> = old_dataflow::DataflowResultsCursor<'mir, 'tcx, IndirectlyMutableLocals<'mir, 'tcx>>; @@ -33,10 +34,10 @@ struct QualifCursor<'a, 'mir, 'tcx, Q: Qualif> { impl<Q: Qualif> QualifCursor<'a, 'mir, 'tcx, Q> { pub fn new(q: Q, item: &'a Item<'mir, 'tcx>) -> Self { - let analysis = FlowSensitiveAnalysis::new(q, item); - let results = dataflow::Engine::new_generic(item.tcx, &item.body, item.def_id, analysis) - .iterate_to_fixpoint(); - let cursor = dataflow::ResultsCursor::new(*item.body, results); + let cursor = FlowSensitiveAnalysis::new(q, item) + .into_engine(item.tcx, &item.body, item.def_id) + .iterate_to_fixpoint() + .into_results_cursor(*item.body); let mut in_any_value_of_ty = BitSet::new_empty(item.body.local_decls.len()); for (local, decl) in item.body.local_decls.iter_enumerated() { diff --git a/src/librustc_mir/transform/elaborate_drops.rs b/src/librustc_mir/transform/elaborate_drops.rs index 1c0b1b8c137..99f13f68cbc 100644 --- a/src/librustc_mir/transform/elaborate_drops.rs +++ b/src/librustc_mir/transform/elaborate_drops.rs @@ -1,7 +1,7 @@ -use crate::dataflow::move_paths::{HasMoveData, LookupResult, MoveData, MovePathIndex}; -use crate::dataflow::DataflowResults; +use crate::dataflow; +use crate::dataflow::generic::{Analysis, Results}; +use crate::dataflow::move_paths::{LookupResult, MoveData, MovePathIndex}; use crate::dataflow::MoveDataParamEnv; -use crate::dataflow::{self, do_dataflow, DebugFormatted}; use crate::dataflow::{drop_flag_effects_for_location, on_lookup_result_bits}; use crate::dataflow::{on_all_children_bits, on_all_drop_children_bits}; use crate::dataflow::{MaybeInitializedPlaces, MaybeUninitializedPlaces}; @@ -40,24 +40,16 @@ impl<'tcx> MirPass<'tcx> for ElaborateDrops { let body = &*body; let env = MoveDataParamEnv { move_data, param_env }; let dead_unwinds = find_dead_unwinds(tcx, body, def_id, &env); - let flow_inits = do_dataflow( - tcx, - body, - def_id, - &[], - &dead_unwinds, - MaybeInitializedPlaces::new(tcx, body, &env), - |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]), - ); - let flow_uninits = do_dataflow( - tcx, - body, - def_id, - &[], - &dead_unwinds, - MaybeUninitializedPlaces::new(tcx, body, &env), - |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]), - ); + + let flow_inits = MaybeInitializedPlaces::new(tcx, body, &env) + .into_engine(tcx, body, def_id) + .dead_unwinds(&dead_unwinds) + .iterate_to_fixpoint(); + + let flow_uninits = MaybeUninitializedPlaces::new(tcx, body, &env) + .into_engine(tcx, body, def_id) + .dead_unwinds(&dead_unwinds) + .iterate_to_fixpoint(); ElaborateDropsCtxt { tcx, @@ -87,15 +79,9 @@ fn find_dead_unwinds<'tcx>( // We only need to do this pass once, because unwind edges can only // reach cleanup blocks, which can't have unwind edges themselves. let mut dead_unwinds = BitSet::new_empty(body.basic_blocks().len()); - let flow_inits = do_dataflow( - tcx, - body, - def_id, - &[], - &dead_unwinds, - MaybeInitializedPlaces::new(tcx, body, &env), - |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]), - ); + let flow_inits = MaybeInitializedPlaces::new(tcx, body, &env) + .into_engine(tcx, body, def_id) + .iterate_to_fixpoint(); for (bb, bb_data) in body.basic_blocks().iter_enumerated() { let location = match bb_data.terminator().kind { TerminatorKind::Drop { ref location, unwind: Some(_), .. } @@ -104,7 +90,7 @@ fn find_dead_unwinds<'tcx>( }; let mut init_data = InitializationData { - live: flow_inits.sets().entry_set_for(bb.index()).to_owned(), + live: flow_inits.entry_set_for_block(bb).clone(), dead: BitSet::new_empty(env.move_data.move_paths.len()), }; debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}", bb, bb_data, init_data.live); @@ -283,8 +269,8 @@ struct ElaborateDropsCtxt<'a, 'tcx> { tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, env: &'a MoveDataParamEnv<'tcx>, - flow_inits: DataflowResults<'tcx, MaybeInitializedPlaces<'a, 'tcx>>, - flow_uninits: DataflowResults<'tcx, MaybeUninitializedPlaces<'a, 'tcx>>, + flow_inits: Results<'tcx, MaybeInitializedPlaces<'a, 'tcx>>, + flow_uninits: Results<'tcx, MaybeUninitializedPlaces<'a, 'tcx>>, drop_flags: FxHashMap<MovePathIndex, Local>, patch: MirPatch<'tcx>, } @@ -298,10 +284,13 @@ impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> { self.env.param_env } + // FIXME(ecstaticmorse): This duplicates `dataflow::ResultsCursor` but hardcodes the transfer + // function for `Maybe{Un,}InitializedPlaces` directly. It should be replaced by a a pair of + // `ResultsCursor`s. fn initialization_data_at(&self, loc: Location) -> InitializationData { let mut data = InitializationData { - live: self.flow_inits.sets().entry_set_for(loc.block.index()).to_owned(), - dead: self.flow_uninits.sets().entry_set_for(loc.block.index()).to_owned(), + live: self.flow_inits.entry_set_for_block(loc.block).to_owned(), + dead: self.flow_uninits.entry_set_for_block(loc.block).to_owned(), }; for stmt in 0..loc.statement_index { data.apply_location( diff --git a/src/librustc_mir/transform/rustc_peek.rs b/src/librustc_mir/transform/rustc_peek.rs index 7a90cb0390e..7d8506eb281 100644 --- a/src/librustc_mir/transform/rustc_peek.rs +++ b/src/librustc_mir/transform/rustc_peek.rs @@ -9,11 +9,9 @@ use rustc::ty::{self, Ty, TyCtxt}; use rustc_hir::def_id::DefId; use rustc_index::bit_set::BitSet; +use crate::dataflow::generic::{Analysis, Results, ResultsCursor}; use crate::dataflow::move_paths::{HasMoveData, MoveData}; use crate::dataflow::move_paths::{LookupResult, MovePathIndex}; -use crate::dataflow::BitDenotation; -use crate::dataflow::DataflowResults; -use crate::dataflow::DataflowResultsCursor; use crate::dataflow::IndirectlyMutableLocals; use crate::dataflow::MoveDataParamEnv; use crate::dataflow::{do_dataflow, DebugFormatted}; @@ -21,12 +19,12 @@ use crate::dataflow::{ DefinitelyInitializedPlaces, MaybeInitializedPlaces, MaybeUninitializedPlaces, }; -use crate::dataflow::has_rustc_mir_with; - pub struct SanityCheck; impl<'tcx> MirPass<'tcx> for SanityCheck { fn run_pass(&self, tcx: TyCtxt<'tcx>, src: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) { + use crate::dataflow::has_rustc_mir_with; + let def_id = src.def_id(); if !tcx.has_attr(def_id, sym::rustc_mir) { debug!("skipping rustc_peek::SanityCheck on {}", tcx.def_path_str(def_id)); @@ -40,34 +38,17 @@ impl<'tcx> MirPass<'tcx> for SanityCheck { let move_data = MoveData::gather_moves(body, tcx, param_env).unwrap(); let mdpe = MoveDataParamEnv { move_data: move_data, param_env: param_env }; let dead_unwinds = BitSet::new_empty(body.basic_blocks().len()); - let flow_inits = do_dataflow( - tcx, - body, - def_id, - &attributes, - &dead_unwinds, - MaybeInitializedPlaces::new(tcx, body, &mdpe), - |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]), - ); - let flow_uninits = do_dataflow( - tcx, - body, - def_id, - &attributes, - &dead_unwinds, - MaybeUninitializedPlaces::new(tcx, body, &mdpe), - |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]), - ); - let flow_def_inits = do_dataflow( - tcx, - body, - def_id, - &attributes, - &dead_unwinds, - DefinitelyInitializedPlaces::new(tcx, body, &mdpe), - |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]), - ); - let flow_indirectly_mut = do_dataflow( + + let flow_inits = MaybeInitializedPlaces::new(tcx, body, &mdpe) + .into_engine(tcx, body, def_id) + .iterate_to_fixpoint(); + let flow_uninits = MaybeUninitializedPlaces::new(tcx, body, &mdpe) + .into_engine(tcx, body, def_id) + .iterate_to_fixpoint(); + let flow_def_inits = DefinitelyInitializedPlaces::new(tcx, body, &mdpe) + .into_engine(tcx, body, def_id) + .iterate_to_fixpoint(); + let _flow_indirectly_mut = do_dataflow( tcx, body, def_id, @@ -86,9 +67,12 @@ impl<'tcx> MirPass<'tcx> for SanityCheck { if has_rustc_mir_with(&attributes, sym::rustc_peek_definite_init).is_some() { sanity_check_via_rustc_peek(tcx, body, def_id, &attributes, &flow_def_inits); } + // FIXME: Uncomment these as analyses are migrated to the new framework + /* if has_rustc_mir_with(&attributes, sym::rustc_peek_indirectly_mutable).is_some() { sanity_check_via_rustc_peek(tcx, body, def_id, &attributes, &flow_indirectly_mut); } + */ if has_rustc_mir_with(&attributes, sym::stop_after_dataflow).is_some() { tcx.sess.fatal("stop_after_dataflow ended compilation"); } @@ -111,18 +95,18 @@ impl<'tcx> MirPass<'tcx> for SanityCheck { /// (If there are any calls to `rustc_peek` that do not match the /// expression form above, then that emits an error as well, but those /// errors are not intended to be used for unit tests.) -pub fn sanity_check_via_rustc_peek<'tcx, O>( +pub fn sanity_check_via_rustc_peek<'tcx, A>( tcx: TyCtxt<'tcx>, body: &Body<'tcx>, def_id: DefId, _attributes: &[ast::Attribute], - results: &DataflowResults<'tcx, O>, + results: &Results<'tcx, A>, ) where - O: RustcPeekAt<'tcx>, + A: RustcPeekAt<'tcx>, { debug!("sanity_check_via_rustc_peek def_id: {:?}", def_id); - let mut cursor = DataflowResultsCursor::new(results, body); + let mut cursor = ResultsCursor::new(body, results); let peek_calls = body.basic_blocks().iter_enumerated().filter_map(|(bb, block_data)| { PeekCall::from_terminator(tcx, block_data.terminator()).map(|call| (bb, block_data, call)) @@ -153,9 +137,9 @@ pub fn sanity_check_via_rustc_peek<'tcx, O>( | (PeekCallKind::ByVal, mir::Rvalue::Use(mir::Operand::Move(place))) | (PeekCallKind::ByVal, mir::Rvalue::Use(mir::Operand::Copy(place))) => { let loc = Location { block: bb, statement_index }; - cursor.seek(loc); + cursor.seek_before(loc); let state = cursor.get(); - results.operator().peek_at(tcx, place, state, call); + results.analysis.peek_at(tcx, place, state, call); } _ => { @@ -255,7 +239,7 @@ impl PeekCall { } } -pub trait RustcPeekAt<'tcx>: BitDenotation<'tcx> { +pub trait RustcPeekAt<'tcx>: Analysis<'tcx> { fn peek_at( &self, tcx: TyCtxt<'tcx>, @@ -265,9 +249,9 @@ pub trait RustcPeekAt<'tcx>: BitDenotation<'tcx> { ); } -impl<'tcx, O> RustcPeekAt<'tcx> for O +impl<'tcx, A> RustcPeekAt<'tcx> for A where - O: BitDenotation<'tcx, Idx = MovePathIndex> + HasMoveData<'tcx>, + A: Analysis<'tcx, Idx = MovePathIndex> + HasMoveData<'tcx>, { fn peek_at( &self, @@ -292,6 +276,7 @@ where } } +/* FIXME: Add this back once `IndirectlyMutableLocals` uses the new dataflow framework. impl<'tcx> RustcPeekAt<'tcx> for IndirectlyMutableLocals<'_, 'tcx> { fn peek_at( &self, @@ -313,3 +298,4 @@ impl<'tcx> RustcPeekAt<'tcx> for IndirectlyMutableLocals<'_, 'tcx> { } } } +*/ diff --git a/src/test/ui/mir-dataflow/indirect-mutation-offset.rs b/src/test/ui/mir-dataflow/indirect-mutation-offset.rs index 8087a3e1399..884c83b6616 100644 --- a/src/test/ui/mir-dataflow/indirect-mutation-offset.rs +++ b/src/test/ui/mir-dataflow/indirect-mutation-offset.rs @@ -1,5 +1,7 @@ // compile-flags: -Zunleash-the-miri-inside-of-you +// ignore-test Temporarily ignored while this analysis is migrated to the new framework. + #![feature(core_intrinsics, rustc_attrs, const_raw_ptr_deref)] use std::cell::UnsafeCell; |