MIR move elimination [3/6]: PreciseLiveness

@@ -592,6 +592,7 @@ pub enum RustcDumpLayoutKind { #[derive(Clone, Debug, StableHash, Encodable, Decodable, PrintAttribute, PartialEq, Eq)] pub enum RustcMirKind {     PrettyLiveLocals,+    PrettyPreciseLiveness,     PrettyTransitiveLiveLocals,     PeekMaybeInit,     PeekMaybeUninit,

@@ -630,6 +630,10 @@ impl CombineAttributeParser for RustcMirParser {                             cx.expect_no_args(mi.args())?;                             Some(RustcMirKind::PrettyLiveLocals)                         }+                        sym::rustc_pretty_precise_liveness => {+                            cx.expect_no_args(mi.args())?;+                            Some(RustcMirKind::PrettyPreciseLiveness)+                        }                         sym::rustc_pretty_transitive_live_locals => {                             cx.expect_no_args(mi.args())?;                             Some(RustcMirKind::PrettyTransitiveLiveLocals)

@@ -127,6 +127,8 @@ impl Direction for Backward {             analysis.apply_primary_statement_effect(state, stmt, loc);             vis.visit_after_primary_statement_effect(state, stmt, loc);         }++        vis.visit_block_exit(state, block);     } } @@ -242,5 +244,7 @@ impl Direction for Forward {         vis.visit_after_early_terminator_effect(state, term, loc);         analysis.apply_primary_terminator_effect(state, term, loc);         vis.visit_after_primary_terminator_effect(state, term, loc);++        vis.visit_block_exit(state, block);     } }

@@ -34,6 +34,13 @@ pub trait ResultsVisitor<'tcx, A> where     A: Analysis<'tcx>, {+    /// Called after all effects in a block have been applied in the direction+    /// of the analysis.+    ///+    /// In a forwards analysis, `state` is from the block's end. In a backwards+    /// analysis, `state` is from the block's start.+    fn visit_block_exit(&mut self, _state: &A::Domain, _block: BasicBlock) {}+     /// Called after the "early" effect of the given statement is applied to `state`.     fn visit_after_early_statement_effect(         &mut self,

@@ -1,6 +1,7 @@ mod borrowed_locals; mod initialized; mod liveness;+mod precise_liveness; mod storage_liveness;  pub use self::borrowed_locals::{MaybeBorrowedLocals, borrowed_locals};@@ -11,6 +12,10 @@ pub use self::initialized::{ pub use self::liveness::{     DefUse, LivenessTransferFunction, MaybeLiveLocals, MaybeTransitiveLiveLocals, };+pub use self::precise_liveness::{+    SplitPointEffect, SplitPointIndex, VisitAllocatedLocalsWith, VisitDeallocatedLocalsWith,+    dump_liveness_matrix, liveness_matrix,+}; pub use self::storage_liveness::{     MaybeRequiresStorage, MaybeStorageDead, MaybeStorageLive, always_storage_live_locals, };

@@ -0,0 +1,596 @@+//! Computes the points where each local must have a distinct allocation.+//!+//! The result is a [`SparseIntervalMatrix`] with one row per local. Two locals+//! may share the same address only if their rows are disjoint. To model MIR+//! statements where a source operand and destination place may share an+//! address, each statement and terminator is split into an early point, where+//! operands are read, and a late point, where destinations are written.+//!+//! A local live range starts at the late point of any statement or terminator+//! that writes to it without a `Deref` projection. It ends at `StorageLive` or+//! `StorageDead`, or at the early point of a whole-local move operand or the+//! last use of that local on a control-flow path (only for locals whose address+//! is never observed). This happens at `StorageLive` because it resets a local+//! to an uninitialized state.+//!+//! `Call` terminators are handled specially: move operands are kept live+//! through the late point of the terminator so they conflict with each other+//! and with the destination place. This matches the runtime behavior where the+//! place is donated to the callee for the duration of the call.+//!+//! The analysis consists of three passes:+//!+//! 1. A backward value-liveness analysis which identifies the last point at+//!    which each local is directly used in each control flow path. This is used+//!    to shorten the lifetime of unborrowed locals to their last use.+//! 2. A forward allocation-liveness analysis which uses that information+//!    together with writes, moves, and storage markers to compute which+//!    allocations may be live on entry to each block.+//! 3. A final walk using those entry states which constructs the matrix and+//!    distinguishes whether each effect happens at the early or late point of a+//!    statement or terminator.++use rustc_index::IndexVec;+use rustc_index::bit_set::DenseBitSet;+use rustc_index::interval::SparseIntervalMatrix;+use rustc_middle::mir::visit::{+    MutatingUseContext, NonMutatingUseContext, NonUseContext, PlaceContext, VisitPlacesWith,+    Visitor,+};+use rustc_middle::mir::{self, BasicBlock, Local, Location, MirDumper, PassWhere, Place};+use rustc_middle::ty::TyCtxt;+use tracing::trace;++use crate::impls::{DefUse, MaybeLiveLocals, borrowed_locals};+use crate::points::{DenseLocationMap, PointIndex};+use crate::{Analysis, GenKill, ResultsVisitor, visit_results};++/// Visits locals that are implicitly allocated by a statement or terminator as+/// part of destination place evaluation.+pub struct VisitAllocatedLocalsWith<F>(pub F);++impl<'tcx, F> Visitor<'tcx> for VisitAllocatedLocalsWith<F>+where+    F: FnMut(Local, PlaceContext),+{+    fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, _: Location) {+        match DefUse::for_place(*place, context) {+            DefUse::Def | DefUse::PartialWrite => (self.0)(place.local, context),+            DefUse::Use | DefUse::NonUse => {}+        }+    }+}++/// Visits locals that are implicitly freed by being evaluated as a bare-local+/// move operand or through a storage statement.+pub struct VisitDeallocatedLocalsWith<F>(pub F);++impl<'tcx, F> Visitor<'tcx> for VisitDeallocatedLocalsWith<F>+where+    F: FnMut(Local, PlaceContext),+{+    fn visit_statement(&mut self, statement: &mir::Statement<'tcx>, location: Location) {+        match statement.kind {+            // StorageLive resets a local to the live-but-unallocated state,+            // which also has the effect of freeing its allocation.+            mir::StatementKind::StorageLive(local) => {+                (self.0)(local, PlaceContext::NonUse(NonUseContext::StorageLive));+            }+            mir::StatementKind::StorageDead(local) => {+                (self.0)(local, PlaceContext::NonUse(NonUseContext::StorageDead));+            }+            _ => self.super_statement(statement, location),+        }+    }++    fn visit_operand(&mut self, operand: &mir::Operand<'tcx>, _: Location) {+        if let mir::Operand::Move(place) = operand+            && let Some(local) = place.as_local()+        {+            (self.0)(local, PlaceContext::NonMutatingUse(NonMutatingUseContext::Move));+        }+    }+}++////////////////////////////////////////////////////////////////////////////////+// Backward dataflow pass+//+// This pass computes "kill points" for each local, indicating the location of+// their last use in a particular control flow branch. These are later used in+// the forward pass to end the live range of locals that are never borrowed at+// their last direct use.+//+// This pass ignores borrowed locals: we can't determine their last use from+// syntactic uses of the base local, so we conservatively treat them as always+// live in the backwards pass and don't emit kill points for them. The main+// forward pass still kills at `StorageDead` and whole-local moves, which is+// when their allocation is freed.+//+// This pass has 2 outputs: a set of kill points that mark the last use+// locations of locals and a per-block bitset indicating which locals are live+// on entry to that block. The latter acts as a set of kill points at block+// entry for all locals not in the bit set.++struct KillPoints<'a> {+    live_on_entry: IndexVec<BasicBlock, DenseBitSet<Local>>,+    kill_points_map: IndexVec<PointIndex, &'a [(Local, Location)]>,+}++impl<'a> KillPoints<'a> {+    fn compute<'tcx>(+        tcx: TyCtxt<'tcx>,+        body: &mir::Body<'tcx>,+        pass_name: Option<&'static str>,+        points: &DenseLocationMap,+        kill_points: &'a mut Vec<(Local, Location)>,+    ) -> Self {+        let maybe_live_locals = MaybeLiveLocals.iterate_to_fixpoint(tcx, body, pass_name);+        let borrowed_locals = borrowed_locals(body);++        // Initialize all borrowed locals as live on entry. We never try to kill+        // those.+        let mut live_on_entry =+            IndexVec::from_elem_n(borrowed_locals.clone(), body.basic_blocks.len());++        // Collect kill points and live-on-entry states from the results of+        // MaybeLiveLocals.+        kill_points.clear();+        let mut visitor = KillPointsVisitor {+            kill_points,+            live_on_entry: &mut live_on_entry,+            borrowed_locals: &borrowed_locals,+        };+        visit_results(+            body,+            mir::traversal::reachable(body).map(|(block, _)| block),+            &maybe_live_locals,+            &mut visitor,+        );+        trace!(?kill_points);+        trace!(?live_on_entry);++        // Create a mapping of `PointIndex` to the set of killed locals at that+        // location.+        let mut kill_points_map = IndexVec::from_elem_n(&[][..], points.num_points());+        for chunk in kill_points.chunk_by(|a, b| a.1 == b.1) {+            let point = points.point_from_location(chunk[0].1);+            trace!("Kill points at {:?}: {:?}", chunk[0].1, chunk);+            debug_assert!(kill_points_map[point].is_empty());+            kill_points_map[point] = chunk;+        }++        Self { live_on_entry, kill_points_map }+    }+}++struct KillPointsVisitor<'a> {+    kill_points: &'a mut Vec<(Local, Location)>,+    live_on_entry: &'a mut IndexVec<BasicBlock, DenseBitSet<Local>>,+    borrowed_locals: &'a DenseBitSet<Local>,+}++impl<'tcx> ResultsVisitor<'tcx, MaybeLiveLocals> for KillPointsVisitor<'_> {+    fn visit_block_exit(&mut self, state: &DenseBitSet<Local>, block: BasicBlock) {+        // Borrowed locals are already marked as live when live_on_entry was+        // initialized. This adds the non-borrowed locals that we have+        // determined are live on entry to this block.+        self.live_on_entry[block].union(state);+    }++    fn visit_after_early_statement_effect(+        &mut self,+        state: &DenseBitSet<Local>,+        statement: &mir::Statement<'tcx>,+        location: Location,+    ) {+        VisitPlacesWith(|place: Place<'tcx>, ctxt| {+            // Ignore non-uses.+            match ctxt {+                PlaceContext::NonMutatingUse(_) | PlaceContext::MutatingUse(_) => {}+                PlaceContext::NonUse(_) => return,+            }++            // If a local is used in a statement but is dead after it then this+            // location is a kill point. Don't emit a kill point for borrowed+            // locals.+            if !state.contains(place.local) && !self.borrowed_locals.contains(place.local) {+                self.kill_points.push((place.local, location));+            }+        })+        .visit_statement(statement, location);+    }++    fn visit_after_early_terminator_effect(+        &mut self,+        state: &DenseBitSet<Local>,+        terminator: &mir::Terminator<'tcx>,+        location: Location,+    ) {+        VisitPlacesWith(|place: Place<'tcx>, ctxt| {+            // Ignore non-uses (they don't do anything) and edge uses+            // (implicitly killed though live_on_entry at the start of the+            // corresponding successor).+            match ctxt {+                PlaceContext::MutatingUse(+                    MutatingUseContext::AsmOutput+                    | MutatingUseContext::Call+                    | MutatingUseContext::Yield,+                )+                | PlaceContext::NonUse(_) => return,+                PlaceContext::NonMutatingUse(_) | PlaceContext::MutatingUse(_) => {}+            }++            // If a local is used in a terminator but is dead after it then this+            // location is a kill point. Don't emit a kill point for borrowed+            // locals.+            if !state.contains(place.local) && !self.borrowed_locals.contains(place.local) {+                self.kill_points.push((place.local, location));+            }+        })+        .visit_terminator(terminator, location);+    }+}++////////////////////////////////////////////////////////////////////////////////+// Forward dataflow pass+//+// This is a simpler version of the main pass in `liveness_matrix`. It only+// needs to determine local liveness at block edges and doesn't distinguish+// between "early" and "late" effects. However it must still preserve the+// ordering of effects: moved operands are killed before destinations are+// generated.++struct PreciseLiveness<'a> {+    kill_points: &'a KillPoints<'a>,+    points: &'a DenseLocationMap,+}++impl PreciseLiveness<'_> {+    fn apply_block_start_effect(&self, state: &mut DenseBitSet<Local>, block: BasicBlock) {+        // Kill any unborrowed locals that are dead at the start of this block.+        // Notably this kills any dead results produced by a predecessor's+        // terminator. Borrowed locals are always included in live_on_entry.+        state.intersect(&self.kill_points.live_on_entry[block]);+    }+}++impl<'tcx> Analysis<'tcx> for PreciseLiveness<'_> {+    type Domain = DenseBitSet<Local>;++    const NAME: &'static str = "precise_liveness";++    fn bottom_value(&self, body: &mir::Body<'tcx>) -> DenseBitSet<Local> {+        DenseBitSet::new_empty(body.local_decls.len())+    }++    fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut DenseBitSet<Local>) {+        // Function arguments start out as live.+        for arg in body.args_iter() {+            state.gen_(arg);+        }+    }++    fn apply_primary_statement_effect(+        &self,+        state: &mut DenseBitSet<Local>,+        statement: &mir::Statement<'tcx>,+        location: Location,+    ) {+        if location.statement_index == 0 {+            self.apply_block_start_effect(state, location.block);+        }++        VisitDeallocatedLocalsWith(|local, _| state.kill(local))+            .visit_statement(statement, location);+        VisitAllocatedLocalsWith(|local, _| state.gen_(local)).visit_statement(statement, location);++        // Apply kill points at this statement: if a variable is dead then it+        // doesn't need storage.+        let point = self.points.point_from_location(location);+        for &(local, _) in self.kill_points.kill_points_map[point] {+            state.kill(local);+        }+    }++    fn apply_primary_terminator_effect(+        &self,+        state: &mut DenseBitSet<Local>,+        terminator: &mir::Terminator<'tcx>,+        location: Location,+    ) {+        if location.statement_index == 0 {+            self.apply_block_start_effect(state, location.block);+        }++        VisitDeallocatedLocalsWith(|local, _| state.kill(local))+            .visit_terminator(terminator, location);++        // Gen destination places.+        VisitAllocatedLocalsWith(|local, ctxt| {+            // The resume place of a Yield is only evaluated after the coroutine+            // is resumed. This is in contrast to call destinations and inline+            // asm outputs which are evaluated before the call and therefore+            // remain allocated on both normal and unwind edges.+            if ctxt != PlaceContext::MutatingUse(MutatingUseContext::Yield) {+                state.gen_(local);+            }+        })+        .visit_terminator(terminator, location);+    }++    fn apply_call_return_effect(+        &self,+        state: &mut DenseBitSet<Local>,+        _block: BasicBlock,+        return_places: mir::CallReturnPlaces<'_, 'tcx>,+    ) {+        if let mir::CallReturnPlaces::Yield(place) = return_places+            && !place.is_indirect()+        {+            state.gen_(place.local);+        }+    }+}++////////////////////////////////////////////////////////////////////////////////+// Matrix construction++/// Different "phases" of a single MIR statement, used to describe how+/// overlapping operands are handled.+///+/// As a general rule, source operands are read in the `Early` phase and+/// destination places are written in the `Late` phase.+#[derive(Copy, Clone, Debug, PartialEq, Eq)]+pub enum SplitPointEffect {+    Early = 0,+    Late = 1,+}++rustc_index::newtype_index! {+    /// A `PointIndex` with the lower bit encoding early/late inside a+    /// statement.+    ///+    /// This is used to model overlap constraints within a MIR statement: if a+    /// source/destination are allowed to overlap then the source is read in+    /// `SplitPointEffect::Early` and the write is done in+    /// `SplitPointEffect::Late`.+    #[orderable]+    #[debug_format = "SplitPointIndex({})"]+    pub struct SplitPointIndex {}+}++impl SplitPointIndex {+    pub fn new(point: PointIndex, effect: SplitPointEffect) -> SplitPointIndex {+        let index = (point.as_u32() << 1) | (effect as u32);+        SplitPointIndex::from_u32(index)+    }++    pub fn point(self) -> PointIndex {+        PointIndex::from_u32(self.as_u32() >> 1)+    }++    pub fn effect(self) -> SplitPointEffect {+        match self.as_u32() & 1 {+            0 => SplitPointEffect::Early,+            1 => SplitPointEffect::Late,+            _ => unreachable!(),+        }+    }+}++/// Helper type to construct a `SparseIntervalMatrix`.+struct MatrixBuilder {+    matrix: SparseIntervalMatrix<Local, SplitPointIndex>,+    range_start: IndexVec<Local, Option<SplitPointIndex>>,++    // Track locals that have been live at any point in a block so that at the+    // end of a block we don't need to iterate over all locals. This+    // significantly speeds up matrix building.+    maybe_live_locals: Vec<Local>,+}++impl MatrixBuilder {+    fn gen_(&mut self, local: Local, point: PointIndex, effect: SplitPointEffect) {+        let split_point = SplitPointIndex::new(point, effect);++        // No-op if the local is already live.+        if self.range_start[local].is_none() {+            self.range_start[local] = Some(split_point);+            self.maybe_live_locals.push(local);+        }+    }++    fn kill(&mut self, local: Local, point: PointIndex, effect: SplitPointEffect) {+        let end = SplitPointIndex::new(point, effect);++        // No-op if the local is already dead.+        if let Some(start) = self.range_start[local].take() {+            debug_assert!(end >= start);+            self.matrix.append_range(local, start..=end);+        }+    }++    fn kill_all(&mut self, point: PointIndex, effect: SplitPointEffect) {+        while let Some(local) = self.maybe_live_locals.pop() {+            self.kill(local, point, effect);+        }+    }++    fn kill_all_except(&mut self, except: Local, point: PointIndex, effect: SplitPointEffect) {+        while let Some(local) = self.maybe_live_locals.pop() {+            if local != except {+                self.kill(local, point, effect);+            }+        }+        self.maybe_live_locals.push(except);+    }+}++pub fn liveness_matrix<'tcx>(+    tcx: TyCtxt<'tcx>,+    body: &mir::Body<'tcx>,+    points: &DenseLocationMap,+    pass_name: Option<&'static str>,+) -> SparseIntervalMatrix<Local, SplitPointIndex> {+    let mut kill_points_vec = vec![];+    let kill_points = KillPoints::compute(tcx, body, pass_name, points, &mut kill_points_vec);+    let mut results = PreciseLiveness { kill_points: &kill_points, points }+        .iterate_to_fixpoint(tcx, body, pass_name);++    let mut builder = MatrixBuilder {+        matrix: SparseIntervalMatrix::new(points.num_points() * 2),+        range_start: IndexVec::from_elem_n(None, body.local_decls.len()),+        maybe_live_locals: Vec::new(),+    };+    for (block, block_data) in body.basic_blocks.iter_enumerated() {+        // We can mutate the state in-place since we're not using it any more+        // after this point.+        let state = &mut results.entry_states[block];++        // Notably this kills any dead results produced by a predecessor's+        // terminator.+        state.intersect(&kill_points.live_on_entry[block]);++        // Gen any locals that are live at the start of the block. If this block+        // only consists of a return terminator then only gen the return place+        // instead. This ensures that StorageDead for all other locals are+        // inserted before the return terminator.+        let terminator = block_data.terminator();+        if let mir::TerminatorKind::Return = terminator.kind+            && block_data.statements.is_empty()+        {+            if state.contains(mir::RETURN_PLACE) {+                builder.gen_(mir::RETURN_PLACE, points.entry_point(block), SplitPointEffect::Early);+            }+        } else {+            for local in state.iter() {+                builder.gen_(local, points.entry_point(block), SplitPointEffect::Early);+            }+        }++        for (statement_index, statement) in block_data.statements.iter().enumerate() {+            let location = Location { block, statement_index };+            let point = points.point_from_location(location);++            // Kill moved locals at the early point.+            VisitDeallocatedLocalsWith(|local, _| {+                builder.kill(local, point, SplitPointEffect::Early);+            })+            .visit_statement(statement, location);++            // Kill any locals which are no longer used after this statement.+            for &(local, _) in kill_points.kill_points_map[point] {+                builder.kill(local, point, SplitPointEffect::Early);+            }++            // Gen destination places at the late point.+            VisitAllocatedLocalsWith(|local, _| {+                builder.gen_(local, point, SplitPointEffect::Late);+            })+            .visit_statement(statement, location);++            // Kill any dead destination places: they will only appear at the+            // late point of the statement they are generated in, which is+            // sufficient for determining overlap.+            for &(local, _) in kill_points.kill_points_map[point] {+                builder.kill(local, point, SplitPointEffect::Late);+            }+        }++        // If this block ends in a return terminator, end all live ranges before+        // the terminator so that StorageDead statements are inserted before it.+        //+        // This is useful after inlining so that the lifetime of locals in the+        // inlined callee don't extend past the call in the caller.+        if let mir::TerminatorKind::Return = terminator.kind+            && !block_data.statements.is_empty()+        {+            // Blocks with only a return terminator are handled above.+            let location = Location { block, statement_index: block_data.statements.len() - 1 };+            let point = points.point_from_location(location);+            builder.kill_all_except(mir::RETURN_PLACE, point, SplitPointEffect::Late);+        }++        let location = Location { block, statement_index: block_data.statements.len() };+        let point = points.point_from_location(location);++        // Kill moved locals at the early point.+        VisitDeallocatedLocalsWith(|local, _| {+            builder.kill(local, point, SplitPointEffect::Early);+        })+        .visit_terminator(terminator, location);++        // Kill any locals which are no longer used after this terminator.+        for &(local, _) in kill_points.kill_points_map[point] {+            builder.kill(local, point, SplitPointEffect::Early);+        }++        // Gen destination places at the late point.+        VisitAllocatedLocalsWith(|local, _| {+            builder.gen_(local, point, SplitPointEffect::Late);+        })+        .visit_terminator(terminator, location);++        // Move arguments to a call are treated specially: the place that they+        // represent is passed directly to the callee, which means that they are+        // not allowed to alias any other move operand or the destination place.+        // This is represented here by extending their live range to the late+        // part, making it overlap with that of the destination place.+        //+        // Notably, this *doesn't* apply to TailCall.+        if let mir::TerminatorKind::Call {+            func: _,+            args,+            destination: _,+            target: _,+            unwind: _,+            call_source: _,+            fn_span: _,+        } = &terminator.kind+        {+            for arg in args {+                if let mir::Operand::Move(place) = arg.node+                    && !place.is_indirect()+                {+                    builder.gen_(place.local, point, SplitPointEffect::Late);+                }+            }+        }++        // End the lifetimes of all locals at the end of the block. Successor+        // blocks (which may not be contiguous in the index space!) will+        // initialize the lifetimes again from their entry state.+        builder.kill_all(point, SplitPointEffect::Late);+    }++    builder.matrix+}++pub fn dump_liveness_matrix<'tcx>(+    tcx: TyCtxt<'tcx>,+    body: &mir::Body<'tcx>,+    pass_name: &'static str,+    points: &DenseLocationMap,+    matrix: &SparseIntervalMatrix<Local, SplitPointIndex>,+) {+    let locals_live_at = |split_point| {+        matrix.rows().filter(|&r| matrix.contains(r, split_point)).collect::<Vec<_>>()+    };++    if let Some(dumper) = MirDumper::new(tcx, pass_name, body) {+        let extra_data = &|pass_where, w: &mut dyn std::io::Write| {+            if let PassWhere::BeforeLocation(loc) = pass_where {+                let point = points.point_from_location(loc);+                let split_point = SplitPointIndex::new(point, SplitPointEffect::Early);+                let live = locals_live_at(split_point);+                writeln!(w, "        // {loc:?}-early => {live:?}")?;+                let split_point = SplitPointIndex::new(point, SplitPointEffect::Late);+                let live = locals_live_at(split_point);+                writeln!(w, "        // {loc:?}-late => {live:?}")?;+            }+            Ok(())+        };++        dumper.set_extra_data(extra_data).dump_mir(body)+    }+}

@@ -7,7 +7,11 @@ use rustc_middle::ty::TyCtxt;  use crate::debuginfo::debuginfo_locals; use crate::framework::Analysis;-use crate::impls::{MaybeLiveLocals, MaybeTransitiveLiveLocals, borrowed_locals};+use crate::impls::{+    MaybeLiveLocals, MaybeTransitiveLiveLocals, SplitPointEffect, SplitPointIndex, borrowed_locals,+    liveness_matrix,+};+use crate::points::DenseLocationMap; use crate::{ResultsVisitor, visit_results};  type ExtraDataFn = dyn Fn(PassWhere, &mut dyn io::Write) -> io::Result<()>;@@ -33,6 +37,29 @@ pub(crate) fn mir_pretty_extra_data<'tcx>(                     &mut Annotator { annotations: &mut annotations },                 );             }+            RustcMirKind::PrettyPreciseLiveness => {+                let points = DenseLocationMap::new(body);+                let matrix = liveness_matrix(tcx, body, &points, None);+                for (block, data) in body.basic_blocks.iter_enumerated() {+                    for statement_index in 0..=data.statements.len() {+                        let location = mir::Location { block, statement_index };+                        let point = points.point_from_location(location);+                        let locals_live_at = |effect| {+                            let split_point = SplitPointIndex::new(point, effect);+                            matrix+                                .rows()+                                .filter(|&r| matrix.contains(r, split_point))+                                .collect::<Vec<_>>()+                        };+                        let early = locals_live_at(SplitPointEffect::Early);+                        annotations+                            .add(PassWhere::BeforeLocation(location), format!("early: {early:?}"));+                        let late = locals_live_at(SplitPointEffect::Late);+                        annotations+                            .add(PassWhere::BeforeLocation(location), format!("late: {late:?}"));+                    }+                }+            }             RustcMirKind::PrettyTransitiveLiveLocals => {                 let borrowed_locals = borrowed_locals(body);                 let debuginfo_locals = debuginfo_locals(body);

@@ -1899,6 +1899,7 @@ symbols! {         rustc_peek_maybe_uninit,         rustc_preserve_ub_checks,         rustc_pretty_live_locals,+        rustc_pretty_precise_liveness,         rustc_pretty_transitive_live_locals,         rustc_private,         rustc_proc_macro_decls,

@@ -0,0 +1,30 @@+// MIR for `borrowed` 0 dataflow++fn borrowed() -> u32 {+    let mut _0: u32;+    let mut _1: u32;+    let mut _2: u32;+    let mut _3: *const u32;+    let mut _4: *const u32;++    bb0: {+        // early: []+        // late: [_1]+        _1 = const 1_u32;+        // early: [_1]+        // late: [_1, _2]+        _2 = const 2_u32;+        // early: [_1, _2]+        // late: [_1, _2, _3]+        _3 = &raw const _1;+        // early: [_1, _2]+        // late: [_1, _2, _4]+        _4 = &raw const _2;+        // early: [_1, _2]+        // late: [_0, _1]+        _0 = Add(copy _1, move _2);+        // early: [_0]+        // late: []+        return;+    }+}

@@ -0,0 +1,33 @@+// MIR for `branch` 0 dataflow++fn branch(_1: bool) -> u32 {+    let mut _0: u32;+    let mut _2: u32;++    bb0: {+        // early: [_1]+        // late: [_1, _2]+        _2 = const 1_u32;+        // early: [_1, _2]+        // late: [_2]+        switchInt(copy _1) -> [1: bb1, otherwise: bb2];+    }++    bb1: {+        // early: [_2]+        // late: [_0]+        _0 = move _2;+        // early: [_0]+        // late: []+        return;+    }++    bb2: {+        // early: []+        // late: [_0]+        _0 = const 0_u32;+        // early: [_0]+        // late: []+        return;+    }+}

@@ -0,0 +1,39 @@+// MIR for `call` 0 dataflow++fn call() -> u32 {+    let mut _0: u32;+    let mut _1: u32;+    let mut _2: u32;+    let mut _3: u32;+    let mut _4: *const u32;++    bb0: {+        // early: []+        // late: [_1]+        _1 = const 1_u32;+        // early: [_1]+        // late: [_1, _2]+        _2 = const 2_u32;+        // early: [_1, _2]+        // late: [_1, _3]+        _3 = callee(move _1, copy _2) -> [return: bb1, unwind: bb2];+    }++    bb1: {+        // early: [_3]+        // late: [_3, _4]+        _4 = &raw const _3;+        // early: [_3]+        // late: [_0]+        _0 = move _3;+        // early: [_0]+        // late: []+        return;+    }++    bb2 (cleanup): {+        // early: [_3]+        // late: [_3]+        resume;+    }+}

@@ -0,0 +1,35 @@+// MIR for `call_borrowed_field` 0 dataflow++fn call_borrowed_field() -> u32 {+    let mut _0: u32;+    let mut _1: (u32,);+    let mut _2: u32;+    let mut _3: *const (u32,);++    bb0: {+        // early: []+        // late: [_1]+        (_1.0: u32) = const 1_u32;+        // early: [_1]+        // late: [_1, _3]+        _3 = &raw const _1;+        // early: [_1]+        // late: [_1, _2]+        _2 = callee(move (_1.0: u32), const 0_u32) -> [return: bb1, unwind: bb2];+    }++    bb1: {+        // early: [_1, _2]+        // late: [_0, _1]+        _0 = move _2;+        // early: [_0]+        // late: []+        return;+    }++    bb2 (cleanup): {+        // early: [_1]+        // late: [_1]+        resume;+    }+}

@@ -0,0 +1,21 @@+// MIR for `call_field` 0 dataflow++fn call_field() -> u32 {+    let mut _0: u32;+    let mut _1: (u32,);++    bb0: {+        // early: []+        // late: [_1]+        (_1.0: u32) = const 1_u32;+        // early: [_1]+        // late: [_0, _1]+        _0 = callee(move (_1.0: u32), const 0_u32) -> [return: bb1, unwind unreachable];+    }++    bb1: {+        // early: [_0]+        // late: []+        return;+    }+}

@@ -0,0 +1,17 @@+// MIR for `call_indirect` 0 dataflow++fn call_indirect(_1: *const u32) -> u32 {+    let mut _0: u32;++    bb0: {+        // early: [_1]+        // late: [_0]+        _0 = callee(move (*_1), const 0_u32) -> [return: bb1, unwind unreachable];+    }++    bb1: {+        // early: [_0]+        // late: []+        return;+    }+}

@@ -0,0 +1,31 @@+// MIR for `dead_destinations` 0 dataflow++fn dead_destinations() -> u32 {+    let mut _0: u32;+    let mut _1: u32;+    let mut _2: u32;++    bb0: {+        // early: []+        // late: [_1]+        _1 = const 1_u32;+        // early: []+        // late: [_2]+        _2 = callee(const 1_u32, const 2_u32) -> [return: bb1, unwind: bb2];+    }++    bb1: {+        // early: []+        // late: [_0]+        _0 = const 0_u32;+        // early: [_0]+        // late: []+        return;+    }++    bb2 (cleanup): {+        // early: []+        // late: []+        resume;+    }+}

@@ -0,0 +1,14 @@+// MIR for `dereference` 0 dataflow++fn dereference(_1: *mut u32) -> () {+    let mut _0: ();++    bb0: {+        // early: [_1]+        // late: []+        (*_1) = const 1_u32;+        // early: []+        // late: []+        return;+    }+}

@@ -0,0 +1,25 @@+// MIR for `fields` 0 dataflow++fn fields() -> u32 {+    let mut _0: u32;+    let mut _1: (u32, u32);+    let mut _2: *const (u32, u32);++    bb0: {+        // early: []+        // late: [_1]+        (_1.0: u32) = const 1_u32;+        // early: [_1]+        // late: [_1]+        (_1.1: u32) = const 2_u32;+        // early: [_1]+        // late: [_1, _2]+        _2 = &raw const _1;+        // early: [_1]+        // late: [_0, _1]+        _0 = Add(move (_1.0: u32), move (_1.1: u32));+        // early: [_0]+        // late: []+        return;+    }+}

@@ -0,0 +1,15 @@+// MIR for `indexed` 0 dataflow++fn indexed(_1: usize) -> () {+    let mut _0: ();+    let mut _2: [u32; 2];++    bb0: {+        // early: [_1]+        // late: [_2]+        _2[_1] = const 1_u32;+        // early: []+        // late: []+        return;+    }+}

@@ -0,0 +1,357 @@+//@ needs-unwind++#![feature(core_intrinsics, custom_mir, rustc_attrs)]+#![crate_type = "lib"]++use std::intrinsics::mir::*;++// A non-borrowed local dies on its last use.+// EMIT_MIR precise_liveness.unborrowed.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn unborrowed() -> u32 {+    // CHECK-LABEL: fn unborrowed(+    // CHECK: [[A:_[0-9]+]] = const 1_u32;+    // CHECK: [[B:_[0-9]+]] = const 2_u32;+    // CHECK: // early: [[[A]], [[B]]]+    // CHECK-NEXT: // late: [_0]+    // CHECK-NEXT: _0 = Add(copy [[A]], move [[B]]);+    mir! {+        let a: u32;+        let b: u32;+        {+            a = 1;+            b = 2;+            RET = a + Move(b);+            Return()+        }+    }+}++// A borrowed local only dies on move.+// EMIT_MIR precise_liveness.borrowed.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn borrowed() -> u32 {+    // CHECK-LABEL: fn borrowed(+    // CHECK: [[A:_[0-9]+]] = const 1_u32;+    // CHECK: [[B:_[0-9]+]] = const 2_u32;+    // CHECK: = &raw const [[B]];+    // CHECK-NEXT: // early: [[[A]], [[B]]]+    // CHECK-NEXT: // late: [_0, [[A]]]+    // CHECK-NEXT: _0 = Add(copy [[A]], move [[B]]);+    mir! {+        let a: u32;+        let b: u32;+        let a_ptr: *const u32;+        let b_ptr: *const u32;+        {+            a = 1;+            b = 2;+            a_ptr = &raw const a;+            b_ptr = &raw const b;+            RET = a + Move(b);+            Return()+        }+    }+}++// StorageDead kills a lifetime, but it can be re-initialized later.+// EMIT_MIR precise_liveness.storage.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn storage() -> u32 {+    // CHECK-LABEL: fn storage(+    // CHECK: // early: [_0, [[BORROWED:_[0-9]+]]]+    // CHECK-NEXT: // late: [_0]+    // CHECK-NEXT: StorageDead([[BORROWED]]);+    // CHECK-NEXT: // early: [_0]+    // CHECK-NEXT: // late: [_0]+    // CHECK-NEXT: StorageLive([[BORROWED]]);+    // CHECK-NEXT: // early: [_0]+    // CHECK-NEXT: // late: [_0, [[BORROWED]]]+    // CHECK-NEXT: [[BORROWED]] = const 3_u32;+    // CHECK-NEXT: // early: [_0, [[BORROWED]]]+    // CHECK-NEXT: // late: [_0]+    // CHECK-NEXT: StorageDead([[BORROWED]]);+    // CHECK-NEXT: // early: [_0]+    // CHECK-NEXT: // late: []+    // CHECK-NEXT: return;+    mir! {+        let borrowed: u32;+        let pointer: *const u32;+        {+            StorageLive(borrowed);+            borrowed = 2;+            pointer = &raw const borrowed;+            RET = borrowed;+            StorageDead(borrowed);+            StorageLive(borrowed);+            borrowed = 3;+            StorageDead(borrowed);+            Return()+        }+    }+}++// Partial initialization starts a lifetime, but only a bare local move ends it.+// EMIT_MIR precise_liveness.fields.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn fields() -> u32 {+    // CHECK-LABEL: fn fields(+    // CHECK: // early: []+    // CHECK-NEXT: // late: [[[AGGREGATE:_[0-9]+]]]+    // CHECK-NEXT: ([[AGGREGATE]].0: u32) = const 1_u32;+    // CHECK: = &raw const [[AGGREGATE]];+    // CHECK-NEXT: // early: [[[AGGREGATE]]]+    // CHECK-NEXT: // late: [_0, [[AGGREGATE]]]+    // CHECK-NEXT: _0 = Add(move ([[AGGREGATE]].0: u32), move ([[AGGREGATE]].1: u32));+    mir! {+        let aggregate: (u32, u32);+        let pointer: *const (u32, u32);+        {+            aggregate.0 = 1;+            aggregate.1 = 2;+            pointer = &raw const aggregate;+            RET = Move(aggregate.0) + Move(aggregate.1);+            Return()+        }+    }+}++unsafe extern "C-unwind" {+    fn callee(a: u32, b: u32) -> u32;+}++// Check the behavior around calls:+// - Destination is initialized at the late point.+// - Move arguments have their live range extended to the late point.+// - Copy arguments die at the early point when this is their last use.+// - Destination remains live on unwind edges.+// EMIT_MIR precise_liveness.call.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn call() -> u32 {+    // CHECK-LABEL: fn call(+    // CHECK: [[A:_[0-9]+]] = const 1_u32;+    // CHECK: [[B:_[0-9]+]] = const 2_u32;+    // CHECK-NEXT: // early: [[[A]], [[B]]]+    // CHECK-NEXT: // late: [[[A]], [[DESTINATION:_[0-9]+]]]+    // CHECK-NEXT: [[DESTINATION]] = callee(move [[A]], copy [[B]])+    // CHECK: = &raw const [[DESTINATION]];+    // CHECK-NEXT: // early: [[[DESTINATION]]]+    // CHECK-NEXT: // late: [_0]+    // CHECK-NEXT: _0 = move [[DESTINATION]];+    // CHECK: (cleanup): {+    // CHECK-NEXT: // early: [[[DESTINATION]]]+    // CHECK-NEXT: // late: [[[DESTINATION]]]+    // CHECK-NEXT: resume;+    mir! {+        let a: u32;+        let b: u32;+        let destination: u32;+        let pointer: *const u32;+        {+            a = 1;+            b = 2;+            Call(destination = callee(Move(a), b), ReturnTo(done), UnwindCleanup(cleanup))+        }+        done = {+            pointer = &raw const destination;+            RET = Move(destination);+            Return()+        }+        cleanup(cleanup) = {+            UnwindResume()+        }+    }+}++// A value used on only one branch is not live on the other branch.+// EMIT_MIR precise_liveness.branch.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn branch(condition: bool) -> u32 {+    // CHECK-LABEL: fn branch(+    // CHECK: [[VALUE:_[0-9]+]] = const 1_u32;+    // CHECK-NEXT: // early: [[[CONDITION:_[0-9]+]], [[VALUE]]]+    // CHECK-NEXT: // late: [[[VALUE]]]+    // CHECK-NEXT: switchInt(copy [[CONDITION]]) -> [1: [[USE:bb[0-9]+]], otherwise: [[SKIP:bb[0-9]+]]];+    // CHECK: [[USE]]: {+    // CHECK-NEXT: // early: [[[VALUE]]]+    // CHECK-NEXT: // late: [_0]+    // CHECK-NEXT: _0 = move [[VALUE]];+    // CHECK: [[SKIP]]: {+    // CHECK-NEXT: // early: []+    // CHECK-NEXT: // late: [_0]+    // CHECK-NEXT: _0 = const 0_u32;+    mir! {+        let value: u32;+        {+            value = 1;+            match condition { true => use_value, _ => skip_value }+        }+        use_value = {+            RET = Move(value);+            Return()+        }+        skip_value = {+            RET = 0;+            Return()+        }+    }+}++// Dead destinations are live only at the late point of the assignment or call.+// EMIT_MIR precise_liveness.dead_destinations.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn dead_destinations() -> u32 {+    // CHECK-LABEL: fn dead_destinations(+    // CHECK: // early: []+    // CHECK-NEXT: // late: [[[ASSIGNMENT:_[0-9]+]]]+    // CHECK-NEXT: [[ASSIGNMENT]] = const 1_u32;+    // CHECK-NEXT: // early: []+    // CHECK-NEXT: // late: [[[DESTINATION:_[0-9]+]]]+    // CHECK-NEXT: [[DESTINATION]] = callee(const 1_u32, const 2_u32) -> [return: [[DONE:bb[0-9]+]], unwind: [[CLEANUP:bb[0-9]+]]];+    // CHECK: [[DONE]]: {+    // CHECK-NEXT: // early: []+    // CHECK-NEXT: // late: [_0]+    // CHECK-NEXT: _0 = const 0_u32;+    // CHECK: [[CLEANUP]] (cleanup): {+    // CHECK-NEXT: // early: []+    // CHECK-NEXT: // late: []+    // CHECK-NEXT: resume;+    mir! {+        let assignment: u32;+        let destination: u32;+        {+            assignment = 1;+            Call(destination = callee(1, 2), ReturnTo(done), UnwindCleanup(cleanup))+        }+        done = {+            RET = 0;+            Return()+        }+        cleanup(cleanup) = {+            UnwindResume()+        }+    }+}++// An indexed write allocates the array. The index is a use, not a destination.+// EMIT_MIR precise_liveness.indexed.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn indexed(index: usize) {+    // CHECK-LABEL: fn indexed(+    // CHECK: // early: [[[INDEX:_[0-9]+]]]+    // CHECK-NEXT: // late: [[[ARRAY:_[0-9]+]]]+    // CHECK-NEXT: [[ARRAY]][[[INDEX]]] = const 1_u32;+    mir! {+        let array: [u32; 2];+        {+            array[index] = 1;+            Return()+        }+    }+}++// A write through a pointer is a use of the pointer, not a def.+// EMIT_MIR precise_liveness.dereference.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn dereference(pointer: *mut u32) {+    // CHECK-LABEL: fn dereference(+    // CHECK: // early: [[[POINTER:_[0-9]+]]]+    // CHECK-NEXT: // late: []+    // CHECK-NEXT: (*[[POINTER]]) = const 1_u32;+    mir! {+        {+            *pointer = 1;+            Return()+        }+    }+}++// A field move keeps the base allocation live through the call's late point.+// EMIT_MIR precise_liveness.call_field.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn call_field() -> u32 {+    // CHECK-LABEL: fn call_field(+    // CHECK: ([[AGGREGATE:_[0-9]+]].0: u32) = const 1_u32;+    // CHECK-NEXT: // early: [[[AGGREGATE]]]+    // CHECK-NEXT: // late: [_0, [[AGGREGATE]]]+    // CHECK-NEXT: _0 = callee(move ([[AGGREGATE]].0: u32), const 0_u32)+    // CHECK: // early: [_0]+    // CHECK-NEXT: // late: []+    // CHECK-NEXT: return;+    mir! {+        let aggregate: (u32,);+        {+            aggregate.0 = 1;+            Call(RET = callee(Move(aggregate.0), 0), ReturnTo(done), UnwindUnreachable())+        }+        done = {+            Return()+        }+    }+}++// A borrowed field's base remains live in both successors after a field move.+// EMIT_MIR precise_liveness.call_borrowed_field.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn call_borrowed_field() -> u32 {+    // CHECK-LABEL: fn call_borrowed_field(+    // CHECK: = &raw const [[AGGREGATE:_[0-9]+]];+    // CHECK-NEXT: // early: [[[AGGREGATE]]]+    // CHECK-NEXT: // late: [[[AGGREGATE]], [[DESTINATION:_[0-9]+]]]+    // CHECK-NEXT: [[DESTINATION]] = callee(move ([[AGGREGATE]].0: u32), const 0_u32) -> [return: [[DONE:bb[0-9]+]], unwind: [[CLEANUP:bb[0-9]+]]];+    // CHECK: [[DONE]]: {+    // CHECK-NEXT: // early: [[[AGGREGATE]], [[DESTINATION]]]+    // CHECK-NEXT: // late: [_0, [[AGGREGATE]]]+    // CHECK-NEXT: _0 = move [[DESTINATION]];+    // CHECK: [[CLEANUP]] (cleanup): {+    // CHECK-NEXT: // early: [[[AGGREGATE]]]+    // CHECK-NEXT: // late: [[[AGGREGATE]]]+    // CHECK-NEXT: resume;+    mir! {+        let aggregate: (u32,);+        let destination: u32;+        let borrow: *const (u32,);+        {+            aggregate.0 = 1;+            borrow = &raw const aggregate;+            Call(destination = callee(Move(aggregate.0), 0), ReturnTo(done), UnwindCleanup(cleanup))+        }+        done = {+            RET = Move(destination);+            Return()+        }+        cleanup(cleanup) = {+            UnwindResume()+        }+    }+}++// An indirect move does not extend the pointer local's lifetime to the late point.+// EMIT_MIR precise_liveness.call_indirect.dataflow.0.mir+#[custom_mir(dialect = "runtime", phase = "optimized")]+#[rustc_mir(rustc_pretty_precise_liveness)]+pub fn call_indirect(pointer: *const u32) -> u32 {+    // CHECK-LABEL: fn call_indirect(+    // CHECK: // early: [[[POINTER:_[0-9]+]]]+    // CHECK-NEXT: // late: [_0]+    // CHECK-NEXT: _0 = callee(move (*[[POINTER]]), const 0_u32)+    mir! {+        {+            Call(RET = callee(Move(*pointer), 0), ReturnTo(done), UnwindUnreachable())+        }+        done = {+            Return()+        }+    }+}

@@ -0,0 +1,37 @@+// MIR for `storage` 0 dataflow++fn storage() -> u32 {+    let mut _0: u32;+    let mut _1: u32;+    let mut _2: *const u32;++    bb0: {+        // early: []+        // late: []+        StorageLive(_1);+        // early: []+        // late: [_1]+        _1 = const 2_u32;+        // early: [_1]+        // late: [_1, _2]+        _2 = &raw const _1;+        // early: [_1]+        // late: [_0, _1]+        _0 = copy _1;+        // early: [_0, _1]+        // late: [_0]+        StorageDead(_1);+        // early: [_0]+        // late: [_0]+        StorageLive(_1);+        // early: [_0]+        // late: [_0, _1]+        _1 = const 3_u32;+        // early: [_0, _1]+        // late: [_0]+        StorageDead(_1);+        // early: [_0]+        // late: []+        return;+    }+}

@@ -0,0 +1,22 @@+// MIR for `unborrowed` 0 dataflow++fn unborrowed() -> u32 {+    let mut _0: u32;+    let mut _1: u32;+    let mut _2: u32;++    bb0: {+        // early: []+        // late: [_1]+        _1 = const 1_u32;+        // early: [_1]+        // late: [_1, _2]+        _2 = const 2_u32;+        // early: [_1, _2]+        // late: [_0]+        _0 = Add(copy _1, move _2);+        // early: [_0]+        // late: []+        return;+    }+}