diff options
Diffstat (limited to 'compiler/rustc_mir_transform/src/ssa.rs')
| -rw-r--r-- | compiler/rustc_mir_transform/src/ssa.rs | 163 |
1 files changed, 75 insertions, 88 deletions
diff --git a/compiler/rustc_mir_transform/src/ssa.rs b/compiler/rustc_mir_transform/src/ssa.rs index 43fc1b7b9..1f59c790b 100644 --- a/compiler/rustc_mir_transform/src/ssa.rs +++ b/compiler/rustc_mir_transform/src/ssa.rs @@ -5,7 +5,6 @@ //! As a consequence of rule 2, we consider that borrowed locals are not SSA, even if they are //! `Freeze`, as we do not track that the assignment dominates all uses of the borrow. -use either::Either; use rustc_data_structures::graph::dominators::Dominators; use rustc_index::bit_set::BitSet; use rustc_index::{IndexSlice, IndexVec}; @@ -15,7 +14,7 @@ use rustc_middle::mir::*; pub struct SsaLocals { /// Assignments to each local. This defines whether the local is SSA. - assignments: IndexVec<Local, Set1<LocationExtended>>, + assignments: IndexVec<Local, Set1<DefLocation>>, /// We visit the body in reverse postorder, to ensure each local is assigned before it is used. /// We remember the order in which we saw the assignments to compute the SSA values in a single /// pass. @@ -27,39 +26,10 @@ pub struct SsaLocals { direct_uses: IndexVec<Local, u32>, } -/// We often encounter MIR bodies with 1 or 2 basic blocks. In those cases, it's unnecessary to -/// actually compute dominators, we can just compare block indices because bb0 is always the first -/// block, and in any body all other blocks are always dominated by bb0. -struct SmallDominators<'a> { - inner: Option<&'a Dominators<BasicBlock>>, -} - -impl SmallDominators<'_> { - fn dominates(&self, first: Location, second: Location) -> bool { - if first.block == second.block { - first.statement_index <= second.statement_index - } else if let Some(inner) = &self.inner { - inner.dominates(first.block, second.block) - } else { - first.block < second.block - } - } - - fn check_dominates(&mut self, set: &mut Set1<LocationExtended>, loc: Location) { - let assign_dominates = match *set { - Set1::Empty | Set1::Many => false, - Set1::One(LocationExtended::Arg) => true, - Set1::One(LocationExtended::Plain(assign)) => { - self.dominates(assign.successor_within_block(), loc) - } - }; - // We are visiting a use that is not dominated by an assignment. - // Either there is a cycle involved, or we are reading for uninitialized local. - // Bail out. - if !assign_dominates { - *set = Set1::Many; - } - } +pub enum AssignedValue<'a, 'tcx> { + Arg, + Rvalue(&'a mut Rvalue<'tcx>), + Terminator(&'a mut TerminatorKind<'tcx>), } impl SsaLocals { @@ -67,15 +37,14 @@ impl SsaLocals { let assignment_order = Vec::with_capacity(body.local_decls.len()); let assignments = IndexVec::from_elem(Set1::Empty, &body.local_decls); - let dominators = - if body.basic_blocks.len() > 2 { Some(body.basic_blocks.dominators()) } else { None }; - let dominators = SmallDominators { inner: dominators }; + let dominators = body.basic_blocks.dominators(); let direct_uses = IndexVec::from_elem(0, &body.local_decls); let mut visitor = SsaVisitor { assignments, assignment_order, dominators, direct_uses }; for local in body.args_iter() { - visitor.assignments[local] = Set1::One(LocationExtended::Arg); + visitor.assignments[local] = Set1::One(DefLocation::Argument); + visitor.assignment_order.push(local); } // For SSA assignments, a RPO visit will see the assignment before it sees any use. @@ -131,14 +100,7 @@ impl SsaLocals { location: Location, ) -> bool { match self.assignments[local] { - Set1::One(LocationExtended::Arg) => true, - Set1::One(LocationExtended::Plain(ass)) => { - if ass.block == location.block { - ass.statement_index < location.statement_index - } else { - dominators.dominates(ass.block, location.block) - } - } + Set1::One(def) => def.dominates(location, dominators), _ => false, } } @@ -148,9 +110,9 @@ impl SsaLocals { body: &'a Body<'tcx>, ) -> impl Iterator<Item = (Local, &'a Rvalue<'tcx>, Location)> + 'a { self.assignment_order.iter().filter_map(|&local| { - if let Set1::One(LocationExtended::Plain(loc)) = self.assignments[local] { + if let Set1::One(DefLocation::Body(loc)) = self.assignments[local] { + let stmt = body.stmt_at(loc).left()?; // `loc` must point to a direct assignment to `local`. - let Either::Left(stmt) = body.stmt_at(loc) else { bug!() }; let Some((target, rvalue)) = stmt.kind.as_assign() else { bug!() }; assert_eq!(target.as_local(), Some(local)); Some((local, rvalue, loc)) @@ -162,18 +124,33 @@ impl SsaLocals { pub fn for_each_assignment_mut<'tcx>( &self, - basic_blocks: &mut BasicBlocks<'tcx>, - mut f: impl FnMut(Local, &mut Rvalue<'tcx>, Location), + basic_blocks: &mut IndexSlice<BasicBlock, BasicBlockData<'tcx>>, + mut f: impl FnMut(Local, AssignedValue<'_, 'tcx>, Location), ) { for &local in &self.assignment_order { - if let Set1::One(LocationExtended::Plain(loc)) = self.assignments[local] { - // `loc` must point to a direct assignment to `local`. - let bbs = basic_blocks.as_mut_preserves_cfg(); - let bb = &mut bbs[loc.block]; - let stmt = &mut bb.statements[loc.statement_index]; - let StatementKind::Assign(box (target, ref mut rvalue)) = stmt.kind else { bug!() }; - assert_eq!(target.as_local(), Some(local)); - f(local, rvalue, loc) + match self.assignments[local] { + Set1::One(DefLocation::Argument) => f( + local, + AssignedValue::Arg, + Location { block: START_BLOCK, statement_index: 0 }, + ), + Set1::One(DefLocation::Body(loc)) => { + let bb = &mut basic_blocks[loc.block]; + let value = if loc.statement_index < bb.statements.len() { + // `loc` must point to a direct assignment to `local`. + let stmt = &mut bb.statements[loc.statement_index]; + let StatementKind::Assign(box (target, ref mut rvalue)) = stmt.kind else { + bug!() + }; + assert_eq!(target.as_local(), Some(local)); + AssignedValue::Rvalue(rvalue) + } else { + let term = bb.terminator_mut(); + AssignedValue::Terminator(&mut term.kind) + }; + f(local, value, loc) + } + _ => {} } } } @@ -224,19 +201,29 @@ impl SsaLocals { } } -#[derive(Copy, Clone, Debug, PartialEq, Eq)] -enum LocationExtended { - Plain(Location), - Arg, -} - struct SsaVisitor<'a> { - dominators: SmallDominators<'a>, - assignments: IndexVec<Local, Set1<LocationExtended>>, + dominators: &'a Dominators<BasicBlock>, + assignments: IndexVec<Local, Set1<DefLocation>>, assignment_order: Vec<Local>, direct_uses: IndexVec<Local, u32>, } +impl SsaVisitor<'_> { + fn check_dominates(&mut self, local: Local, loc: Location) { + let set = &mut self.assignments[local]; + let assign_dominates = match *set { + Set1::Empty | Set1::Many => false, + Set1::One(def) => def.dominates(loc, self.dominators), + }; + // We are visiting a use that is not dominated by an assignment. + // Either there is a cycle involved, or we are reading for uninitialized local. + // Bail out. + if !assign_dominates { + *set = Set1::Many; + } + } +} + impl<'tcx> Visitor<'tcx> for SsaVisitor<'_> { fn visit_local(&mut self, local: Local, ctxt: PlaceContext, loc: Location) { match ctxt { @@ -254,7 +241,7 @@ impl<'tcx> Visitor<'tcx> for SsaVisitor<'_> { self.assignments[local] = Set1::Many; } PlaceContext::NonMutatingUse(_) => { - self.dominators.check_dominates(&mut self.assignments[local], loc); + self.check_dominates(local, loc); self.direct_uses[local] += 1; } PlaceContext::NonUse(_) => {} @@ -262,34 +249,34 @@ impl<'tcx> Visitor<'tcx> for SsaVisitor<'_> { } fn visit_place(&mut self, place: &Place<'tcx>, ctxt: PlaceContext, loc: Location) { - if place.projection.first() == Some(&PlaceElem::Deref) { - // Do not do anything for storage statements and debuginfo. + let location = match ctxt { + PlaceContext::MutatingUse( + MutatingUseContext::Store | MutatingUseContext::Call | MutatingUseContext::Yield, + ) => Some(DefLocation::Body(loc)), + _ => None, + }; + if let Some(location) = location + && let Some(local) = place.as_local() + { + self.assignments[local].insert(location); + if let Set1::One(_) = self.assignments[local] { + // Only record if SSA-like, to avoid growing the vector needlessly. + self.assignment_order.push(local); + } + } else if place.projection.first() == Some(&PlaceElem::Deref) { + // Do not do anything for debuginfo. if ctxt.is_use() { // Only change the context if it is a real use, not a "use" in debuginfo. let new_ctxt = PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy); self.visit_projection(place.as_ref(), new_ctxt, loc); - self.dominators.check_dominates(&mut self.assignments[place.local], loc); + self.check_dominates(place.local, loc); } - return; } else { self.visit_projection(place.as_ref(), ctxt, loc); self.visit_local(place.local, ctxt, loc); } } - - fn visit_assign(&mut self, place: &Place<'tcx>, rvalue: &Rvalue<'tcx>, loc: Location) { - if let Some(local) = place.as_local() { - self.assignments[local].insert(LocationExtended::Plain(loc)); - if let Set1::One(_) = self.assignments[local] { - // Only record if SSA-like, to avoid growing the vector needlessly. - self.assignment_order.push(local); - } - } else { - self.visit_place(place, PlaceContext::MutatingUse(MutatingUseContext::Store), loc); - } - self.visit_rvalue(rvalue, loc); - } } #[instrument(level = "trace", skip(ssa, body))] @@ -356,7 +343,7 @@ fn compute_copy_classes(ssa: &mut SsaLocals, body: &Body<'_>) { #[derive(Debug)] pub(crate) struct StorageLiveLocals { /// Set of "StorageLive" statements for each local. - storage_live: IndexVec<Local, Set1<LocationExtended>>, + storage_live: IndexVec<Local, Set1<DefLocation>>, } impl StorageLiveLocals { @@ -366,13 +353,13 @@ impl StorageLiveLocals { ) -> StorageLiveLocals { let mut storage_live = IndexVec::from_elem(Set1::Empty, &body.local_decls); for local in always_storage_live_locals.iter() { - storage_live[local] = Set1::One(LocationExtended::Arg); + storage_live[local] = Set1::One(DefLocation::Argument); } for (block, bbdata) in body.basic_blocks.iter_enumerated() { for (statement_index, statement) in bbdata.statements.iter().enumerate() { if let StatementKind::StorageLive(local) = statement.kind { storage_live[local] - .insert(LocationExtended::Plain(Location { block, statement_index })); + .insert(DefLocation::Body(Location { block, statement_index })); } } } |