| //! A number of passes which remove various redundancies in the CFG. |
| //! |
| //! The `SimplifyCfg` pass gets rid of unnecessary blocks in the CFG, whereas the `SimplifyLocals` |
| //! gets rid of all the unnecessary local variable declarations. |
| //! |
| //! The `SimplifyLocals` pass is kinda expensive and therefore not very suitable to be run often. |
| //! Most of the passes should not care or be impacted in meaningful ways due to extra locals |
| //! either, so running the pass once, right before codegen, should suffice. |
| //! |
| //! On the other side of the spectrum, the `SimplifyCfg` pass is considerably cheap to run, thus |
| //! one should run it after every pass which may modify CFG in significant ways. This pass must |
| //! also be run before any analysis passes because it removes dead blocks, and some of these can be |
| //! ill-typed. |
| //! |
| //! The cause of this typing issue is typeck allowing most blocks whose end is not reachable have |
| //! an arbitrary return type, rather than having the usual () return type (as a note, typeck's |
| //! notion of reachability is in fact slightly weaker than MIR CFG reachability - see #31617). A |
| //! standard example of the situation is: |
| //! |
| //! ```rust |
| //! fn example() { |
| //! let _a: char = { return; }; |
| //! } |
| //! ``` |
| //! |
| //! Here the block (`{ return; }`) has the return type `char`, rather than `()`, but the MIR we |
| //! naively generate still contains the `_a = ()` write in the unreachable block "after" the |
| //! return. |
| |
| use crate::transform::{MirPass, MirSource}; |
| use rustc::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor}; |
| use rustc::mir::*; |
| use rustc::ty::{self, TyCtxt}; |
| use rustc_index::bit_set::BitSet; |
| use rustc_index::vec::{Idx, IndexVec}; |
| use std::borrow::Cow; |
| |
| pub struct SimplifyCfg { |
| label: String, |
| } |
| |
| impl SimplifyCfg { |
| pub fn new(label: &str) -> Self { |
| SimplifyCfg { label: format!("SimplifyCfg-{}", label) } |
| } |
| } |
| |
| pub fn simplify_cfg(body: &mut BodyAndCache<'_>) { |
| CfgSimplifier::new(body).simplify(); |
| remove_dead_blocks(body); |
| |
| // FIXME: Should probably be moved into some kind of pass manager |
| body.basic_blocks_mut().raw.shrink_to_fit(); |
| } |
| |
| impl<'tcx> MirPass<'tcx> for SimplifyCfg { |
| fn name(&self) -> Cow<'_, str> { |
| Cow::Borrowed(&self.label) |
| } |
| |
| fn run_pass(&self, _tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) { |
| debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, body); |
| simplify_cfg(body); |
| } |
| } |
| |
| pub struct CfgSimplifier<'a, 'tcx> { |
| basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, |
| pred_count: IndexVec<BasicBlock, u32>, |
| } |
| |
| impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> { |
| pub fn new(body: &'a mut BodyAndCache<'tcx>) -> Self { |
| let mut pred_count = IndexVec::from_elem(0u32, body.basic_blocks()); |
| |
| // we can't use mir.predecessors() here because that counts |
| // dead blocks, which we don't want to. |
| pred_count[START_BLOCK] = 1; |
| |
| for (_, data) in traversal::preorder(body) { |
| if let Some(ref term) = data.terminator { |
| for &tgt in term.successors() { |
| pred_count[tgt] += 1; |
| } |
| } |
| } |
| |
| let basic_blocks = body.basic_blocks_mut(); |
| |
| CfgSimplifier { basic_blocks, pred_count } |
| } |
| |
| pub fn simplify(mut self) { |
| self.strip_nops(); |
| |
| let mut start = START_BLOCK; |
| |
| loop { |
| let mut changed = false; |
| |
| self.collapse_goto_chain(&mut start, &mut changed); |
| |
| for bb in self.basic_blocks.indices() { |
| if self.pred_count[bb] == 0 { |
| continue; |
| } |
| |
| debug!("simplifying {:?}", bb); |
| |
| let mut terminator = |
| self.basic_blocks[bb].terminator.take().expect("invalid terminator state"); |
| |
| for successor in terminator.successors_mut() { |
| self.collapse_goto_chain(successor, &mut changed); |
| } |
| |
| let mut new_stmts = vec![]; |
| let mut inner_changed = true; |
| while inner_changed { |
| inner_changed = false; |
| inner_changed |= self.simplify_branch(&mut terminator); |
| inner_changed |= self.merge_successor(&mut new_stmts, &mut terminator); |
| changed |= inner_changed; |
| } |
| |
| let data = &mut self.basic_blocks[bb]; |
| data.statements.extend(new_stmts); |
| data.terminator = Some(terminator); |
| |
| changed |= inner_changed; |
| } |
| |
| if !changed { |
| break; |
| } |
| } |
| |
| if start != START_BLOCK { |
| debug_assert!(self.pred_count[START_BLOCK] == 0); |
| self.basic_blocks.swap(START_BLOCK, start); |
| self.pred_count.swap(START_BLOCK, start); |
| |
| // pred_count == 1 if the start block has no predecessor _blocks_. |
| if self.pred_count[START_BLOCK] > 1 { |
| for (bb, data) in self.basic_blocks.iter_enumerated_mut() { |
| if self.pred_count[bb] == 0 { |
| continue; |
| } |
| |
| for target in data.terminator_mut().successors_mut() { |
| if *target == start { |
| *target = START_BLOCK; |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| // Collapse a goto chain starting from `start` |
| fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) { |
| let mut terminator = match self.basic_blocks[*start] { |
| BasicBlockData { |
| ref statements, |
| terminator: |
| ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }), |
| .. |
| } if statements.is_empty() => terminator.take(), |
| // if `terminator` is None, this means we are in a loop. In that |
| // case, let all the loop collapse to its entry. |
| _ => return, |
| }; |
| |
| let target = match terminator { |
| Some(Terminator { kind: TerminatorKind::Goto { ref mut target }, .. }) => { |
| self.collapse_goto_chain(target, changed); |
| *target |
| } |
| _ => unreachable!(), |
| }; |
| self.basic_blocks[*start].terminator = terminator; |
| |
| debug!("collapsing goto chain from {:?} to {:?}", *start, target); |
| |
| *changed |= *start != target; |
| |
| if self.pred_count[*start] == 1 { |
| // This is the last reference to *start, so the pred-count to |
| // to target is moved into the current block. |
| self.pred_count[*start] = 0; |
| } else { |
| self.pred_count[target] += 1; |
| self.pred_count[*start] -= 1; |
| } |
| |
| *start = target; |
| } |
| |
| // merge a block with 1 `goto` predecessor to its parent |
| fn merge_successor( |
| &mut self, |
| new_stmts: &mut Vec<Statement<'tcx>>, |
| terminator: &mut Terminator<'tcx>, |
| ) -> bool { |
| let target = match terminator.kind { |
| TerminatorKind::Goto { target } if self.pred_count[target] == 1 => target, |
| _ => return false, |
| }; |
| |
| debug!("merging block {:?} into {:?}", target, terminator); |
| *terminator = match self.basic_blocks[target].terminator.take() { |
| Some(terminator) => terminator, |
| None => { |
| // unreachable loop - this should not be possible, as we |
| // don't strand blocks, but handle it correctly. |
| return false; |
| } |
| }; |
| new_stmts.extend(self.basic_blocks[target].statements.drain(..)); |
| self.pred_count[target] = 0; |
| |
| true |
| } |
| |
| // turn a branch with all successors identical to a goto |
| fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool { |
| match terminator.kind { |
| TerminatorKind::SwitchInt { .. } => {} |
| _ => return false, |
| }; |
| |
| let first_succ = { |
| if let Some(&first_succ) = terminator.successors().nth(0) { |
| if terminator.successors().all(|s| *s == first_succ) { |
| let count = terminator.successors().count(); |
| self.pred_count[first_succ] -= (count - 1) as u32; |
| first_succ |
| } else { |
| return false; |
| } |
| } else { |
| return false; |
| } |
| }; |
| |
| debug!("simplifying branch {:?}", terminator); |
| terminator.kind = TerminatorKind::Goto { target: first_succ }; |
| true |
| } |
| |
| fn strip_nops(&mut self) { |
| for blk in self.basic_blocks.iter_mut() { |
| blk.statements |
| .retain(|stmt| if let StatementKind::Nop = stmt.kind { false } else { true }) |
| } |
| } |
| } |
| |
| pub fn remove_dead_blocks(body: &mut BodyAndCache<'_>) { |
| let mut seen = BitSet::new_empty(body.basic_blocks().len()); |
| for (bb, _) in traversal::preorder(body) { |
| seen.insert(bb.index()); |
| } |
| |
| let basic_blocks = body.basic_blocks_mut(); |
| |
| let num_blocks = basic_blocks.len(); |
| let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect(); |
| let mut used_blocks = 0; |
| for alive_index in seen.iter() { |
| replacements[alive_index] = BasicBlock::new(used_blocks); |
| if alive_index != used_blocks { |
| // Swap the next alive block data with the current available slot. Since |
| // alive_index is non-decreasing this is a valid operation. |
| basic_blocks.raw.swap(alive_index, used_blocks); |
| } |
| used_blocks += 1; |
| } |
| basic_blocks.raw.truncate(used_blocks); |
| |
| for block in basic_blocks { |
| for target in block.terminator_mut().successors_mut() { |
| *target = replacements[target.index()]; |
| } |
| } |
| } |
| |
| pub struct SimplifyLocals; |
| |
| impl<'tcx> MirPass<'tcx> for SimplifyLocals { |
| fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) { |
| trace!("running SimplifyLocals on {:?}", source); |
| let locals = { |
| let read_only_cache = read_only!(body); |
| let mut marker = DeclMarker { locals: BitSet::new_empty(body.local_decls.len()), body }; |
| marker.visit_body(read_only_cache); |
| // Return pointer and arguments are always live |
| marker.locals.insert(RETURN_PLACE); |
| for arg in body.args_iter() { |
| marker.locals.insert(arg); |
| } |
| |
| marker.locals |
| }; |
| |
| let map = make_local_map(&mut body.local_decls, locals); |
| // Update references to all vars and tmps now |
| LocalUpdater { map, tcx }.visit_body(body); |
| body.local_decls.shrink_to_fit(); |
| } |
| } |
| |
| /// Construct the mapping while swapping out unused stuff out from the `vec`. |
| fn make_local_map<V>( |
| vec: &mut IndexVec<Local, V>, |
| mask: BitSet<Local>, |
| ) -> IndexVec<Local, Option<Local>> { |
| let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*vec); |
| let mut used = Local::new(0); |
| for alive_index in mask.iter() { |
| map[alive_index] = Some(used); |
| if alive_index != used { |
| vec.swap(alive_index, used); |
| } |
| used.increment_by(1); |
| } |
| vec.truncate(used.index()); |
| map |
| } |
| |
| struct DeclMarker<'a, 'tcx> { |
| pub locals: BitSet<Local>, |
| pub body: &'a Body<'tcx>, |
| } |
| |
| impl<'a, 'tcx> Visitor<'tcx> for DeclMarker<'a, 'tcx> { |
| fn visit_local(&mut self, local: &Local, ctx: PlaceContext, location: Location) { |
| // Ignore storage markers altogether, they get removed along with their otherwise unused |
| // decls. |
| // FIXME: Extend this to all non-uses. |
| if ctx.is_storage_marker() { |
| return; |
| } |
| |
| // Ignore stores of constants because `ConstProp` and `CopyProp` can remove uses of many |
| // of these locals. However, if the local is still needed, then it will be referenced in |
| // another place and we'll mark it as being used there. |
| if ctx == PlaceContext::MutatingUse(MutatingUseContext::Store) |
| || ctx == PlaceContext::MutatingUse(MutatingUseContext::Projection) |
| { |
| let block = &self.body.basic_blocks()[location.block]; |
| if location.statement_index != block.statements.len() { |
| let stmt = &block.statements[location.statement_index]; |
| |
| if let StatementKind::Assign(box (p, Rvalue::Use(Operand::Constant(c)))) = |
| &stmt.kind |
| { |
| match c.literal.val { |
| // Keep assignments from unevaluated constants around, since the evaluation |
| // may report errors, even if the use of the constant is dead code. |
| ty::ConstKind::Unevaluated(..) => {} |
| _ => { |
| if !p.is_indirect() { |
| trace!("skipping store of const value {:?} to {:?}", c, p); |
| return; |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| self.locals.insert(*local); |
| } |
| } |
| |
| struct LocalUpdater<'tcx> { |
| map: IndexVec<Local, Option<Local>>, |
| tcx: TyCtxt<'tcx>, |
| } |
| |
| impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> { |
| fn tcx(&self) -> TyCtxt<'tcx> { |
| self.tcx |
| } |
| |
| fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) { |
| // Remove unnecessary StorageLive and StorageDead annotations. |
| data.statements.retain(|stmt| match &stmt.kind { |
| StatementKind::StorageLive(l) | StatementKind::StorageDead(l) => self.map[*l].is_some(), |
| StatementKind::Assign(box (place, _)) => self.map[place.local].is_some(), |
| _ => true, |
| }); |
| self.super_basic_block_data(block, data); |
| } |
| |
| fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) { |
| *l = self.map[*l].unwrap(); |
| } |
| |
| fn process_projection_elem(&mut self, elem: &PlaceElem<'tcx>) -> Option<PlaceElem<'tcx>> { |
| match elem { |
| PlaceElem::Index(local) => Some(PlaceElem::Index(self.map[*local].unwrap())), |
| _ => None, |
| } |
| } |
| } |