diff options
Diffstat (limited to 'compiler/rustc_mir_transform')
| -rw-r--r-- | compiler/rustc_mir_transform/src/jump_threading.rs | 42 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/patch.rs | 36 |
2 files changed, 46 insertions, 32 deletions
diff --git a/compiler/rustc_mir_transform/src/jump_threading.rs b/compiler/rustc_mir_transform/src/jump_threading.rs index f9e642e28eb..68298767e7f 100644 --- a/compiler/rustc_mir_transform/src/jump_threading.rs +++ b/compiler/rustc_mir_transform/src/jump_threading.rs @@ -84,7 +84,7 @@ impl<'tcx> crate::MirPass<'tcx> for JumpThreading { body, arena, map: Map::new(tcx, body, Some(MAX_PLACES)), - loop_headers: loop_headers(body), + maybe_loop_headers: maybe_loop_headers(body), opportunities: Vec::new(), }; @@ -100,7 +100,7 @@ impl<'tcx> crate::MirPass<'tcx> for JumpThreading { // Verify that we do not thread through a loop header. for to in opportunities.iter() { - assert!(to.chain.iter().all(|&block| !finder.loop_headers.contains(block))); + assert!(to.chain.iter().all(|&block| !finder.maybe_loop_headers.contains(block))); } OpportunitySet::new(body, opportunities).apply(body); } @@ -124,7 +124,7 @@ struct TOFinder<'a, 'tcx> { ecx: InterpCx<'tcx, DummyMachine>, body: &'a Body<'tcx>, map: Map<'tcx>, - loop_headers: DenseBitSet<BasicBlock>, + maybe_loop_headers: DenseBitSet<BasicBlock>, /// We use an arena to avoid cloning the slices when cloning `state`. arena: &'a DroplessArena, opportunities: Vec<ThreadingOpportunity>, @@ -190,7 +190,7 @@ impl<'a, 'tcx> TOFinder<'a, 'tcx> { #[instrument(level = "trace", skip(self))] fn start_from_switch(&mut self, bb: BasicBlock) { let bbdata = &self.body[bb]; - if bbdata.is_cleanup || self.loop_headers.contains(bb) { + if bbdata.is_cleanup || self.maybe_loop_headers.contains(bb) { return; } let Some((discr, targets)) = bbdata.terminator().kind.as_switch() else { return }; @@ -235,7 +235,7 @@ impl<'a, 'tcx> TOFinder<'a, 'tcx> { depth: usize, ) { // Do not thread through loop headers. - if self.loop_headers.contains(bb) { + if self.maybe_loop_headers.contains(bb) { return; } @@ -833,20 +833,28 @@ enum Update { Decr, } -/// Compute the set of loop headers in the given body. We define a loop header as a block which has -/// at least a predecessor which it dominates. This definition is only correct for reducible CFGs. -/// But if the CFG is already irreducible, there is no point in trying much harder. -/// is already irreducible. -fn loop_headers(body: &Body<'_>) -> DenseBitSet<BasicBlock> { - let mut loop_headers = DenseBitSet::new_empty(body.basic_blocks.len()); - let dominators = body.basic_blocks.dominators(); - // Only visit reachable blocks. - for (bb, bbdata) in traversal::preorder(body) { +/// Compute the set of loop headers in the given body. A loop header is usually defined as a block +/// which dominates one of its predecessors. This definition is only correct for reducible CFGs. +/// However, computing dominators is expensive, so we approximate according to the post-order +/// traversal order. A loop header for us is a block which is visited after its predecessor in +/// post-order. This is ok as we mostly need a heuristic. +fn maybe_loop_headers(body: &Body<'_>) -> DenseBitSet<BasicBlock> { + let mut maybe_loop_headers = DenseBitSet::new_empty(body.basic_blocks.len()); + let mut visited = DenseBitSet::new_empty(body.basic_blocks.len()); + for (bb, bbdata) in traversal::postorder(body) { + // Post-order means we visit successors before the block for acyclic CFGs. + // If the successor is not visited yet, consider it a loop header. for succ in bbdata.terminator().successors() { - if dominators.dominates(succ, bb) { - loop_headers.insert(succ); + if !visited.contains(succ) { + maybe_loop_headers.insert(succ); } } + + // Only mark `bb` as visited after we checked the successors, in case we have a self-loop. + // bb1: goto -> bb1; + let _new = visited.insert(bb); + debug_assert!(_new); } - loop_headers + + maybe_loop_headers } diff --git a/compiler/rustc_mir_transform/src/patch.rs b/compiler/rustc_mir_transform/src/patch.rs index c781d1a5324..d831ab50b1a 100644 --- a/compiler/rustc_mir_transform/src/patch.rs +++ b/compiler/rustc_mir_transform/src/patch.rs @@ -1,4 +1,5 @@ -use rustc_index::{Idx, IndexVec}; +use rustc_data_structures::fx::FxHashMap; +use rustc_index::Idx; use rustc_middle::mir::*; use rustc_middle::ty::Ty; use rustc_span::Span; @@ -9,7 +10,7 @@ use tracing::debug; /// and replacement of terminators, and then apply the queued changes all at /// once with `apply`. This is useful for MIR transformation passes. pub(crate) struct MirPatch<'tcx> { - term_patch_map: IndexVec<BasicBlock, Option<TerminatorKind<'tcx>>>, + term_patch_map: FxHashMap<BasicBlock, TerminatorKind<'tcx>>, new_blocks: Vec<BasicBlockData<'tcx>>, new_statements: Vec<(Location, StatementKind<'tcx>)>, new_locals: Vec<LocalDecl<'tcx>>, @@ -22,17 +23,21 @@ pub(crate) struct MirPatch<'tcx> { terminate_block: Option<(BasicBlock, UnwindTerminateReason)>, body_span: Span, next_local: usize, + /// The number of blocks at the start of the transformation. New blocks + /// get appended at the end. + next_block: usize, } impl<'tcx> MirPatch<'tcx> { /// Creates a new, empty patch. pub(crate) fn new(body: &Body<'tcx>) -> Self { let mut result = MirPatch { - term_patch_map: IndexVec::from_elem(None, &body.basic_blocks), + term_patch_map: Default::default(), new_blocks: vec![], new_statements: vec![], new_locals: vec![], next_local: body.local_decls.len(), + next_block: body.basic_blocks.len(), resume_block: None, unreachable_cleanup_block: None, unreachable_no_cleanup_block: None, @@ -141,7 +146,7 @@ impl<'tcx> MirPatch<'tcx> { /// Has a replacement of this block's terminator been queued in this patch? pub(crate) fn is_term_patched(&self, bb: BasicBlock) -> bool { - self.term_patch_map[bb].is_some() + self.term_patch_map.contains_key(&bb) } /// Universal getter for block data, either it is in 'old' blocks or in patched ones @@ -194,18 +199,17 @@ impl<'tcx> MirPatch<'tcx> { /// Queues the addition of a new basic block. pub(crate) fn new_block(&mut self, data: BasicBlockData<'tcx>) -> BasicBlock { - let block = self.term_patch_map.next_index(); + let block = BasicBlock::from_usize(self.next_block + self.new_blocks.len()); debug!("MirPatch: new_block: {:?}: {:?}", block, data); self.new_blocks.push(data); - self.term_patch_map.push(None); block } /// Queues the replacement of a block's terminator. pub(crate) fn patch_terminator(&mut self, block: BasicBlock, new: TerminatorKind<'tcx>) { - assert!(self.term_patch_map[block].is_none()); + assert!(!self.term_patch_map.contains_key(&block)); debug!("MirPatch: patch_terminator({:?}, {:?})", block, new); - self.term_patch_map[block] = Some(new); + self.term_patch_map.insert(block, new); } /// Queues the insertion of a statement at a given location. The statement @@ -244,6 +248,7 @@ impl<'tcx> MirPatch<'tcx> { self.new_blocks.len(), body.basic_blocks.len() ); + debug_assert_eq!(self.next_block, body.basic_blocks.len()); let bbs = if self.term_patch_map.is_empty() && self.new_blocks.is_empty() { body.basic_blocks.as_mut_preserves_cfg() } else { @@ -251,11 +256,12 @@ impl<'tcx> MirPatch<'tcx> { }; bbs.extend(self.new_blocks); body.local_decls.extend(self.new_locals); - for (src, patch) in self.term_patch_map.into_iter_enumerated() { - if let Some(patch) = patch { - debug!("MirPatch: patching block {:?}", src); - bbs[src].terminator_mut().kind = patch; - } + + // The order in which we patch terminators does not change the result. + #[allow(rustc::potential_query_instability)] + for (src, patch) in self.term_patch_map { + debug!("MirPatch: patching block {:?}", src); + bbs[src].terminator_mut().kind = patch; } let mut new_statements = self.new_statements; @@ -273,8 +279,8 @@ impl<'tcx> MirPatch<'tcx> { } debug!("MirPatch: adding statement {:?} at loc {:?}+{}", stmt, loc, delta); loc.statement_index += delta; - let source_info = Self::source_info_for_index(&body[loc.block], loc); - body[loc.block] + let source_info = Self::source_info_for_index(&bbs[loc.block], loc); + bbs[loc.block] .statements .insert(loc.statement_index, Statement::new(source_info, stmt)); delta += 1; |