1 //! A number of passes which remove various redundancies in the CFG.
3 //! The `SimplifyCfg` pass gets rid of unnecessary blocks in the CFG, whereas the `SimplifyLocals`
4 //! gets rid of all the unnecessary local variable declarations.
6 //! The `SimplifyLocals` pass is kinda expensive and therefore not very suitable to be run often.
7 //! Most of the passes should not care or be impacted in meaningful ways due to extra locals
8 //! either, so running the pass once, right before codegen, should suffice.
10 //! On the other side of the spectrum, the `SimplifyCfg` pass is considerably cheap to run, thus
11 //! one should run it after every pass which may modify CFG in significant ways. This pass must
12 //! also be run before any analysis passes because it removes dead blocks, and some of these can be
15 //! The cause of this typing issue is typeck allowing most blocks whose end is not reachable have
16 //! an arbitrary return type, rather than having the usual () return type (as a note, typeck's
17 //! notion of reachability is in fact slightly weaker than MIR CFG reachability - see #31617). A
18 //! standard example of the situation is:
22 //! let _a: char = { return; };
26 //! Here the block (`{ return; }`) has the return type `char`, rather than `()`, but the MIR we
27 //! naively generate still contains the `_a = ()` write in the unreachable block "after" the
30 use crate::transform::MirPass;
31 use rustc_index::vec::{Idx, IndexVec};
32 use rustc_middle::mir::coverage::*;
33 use rustc_middle::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor};
34 use rustc_middle::mir::*;
35 use rustc_middle::ty::TyCtxt;
36 use smallvec::SmallVec;
38 use std::convert::TryInto;
40 pub struct SimplifyCfg {
45 pub fn new(label: &str) -> Self {
46 SimplifyCfg { label: format!("SimplifyCfg-{}", label) }
50 pub fn simplify_cfg(tcx: TyCtxt<'tcx>, body: &mut Body<'_>) {
51 CfgSimplifier::new(body).simplify();
52 remove_dead_blocks(tcx, body);
54 // FIXME: Should probably be moved into some kind of pass manager
55 body.basic_blocks_mut().raw.shrink_to_fit();
58 impl<'tcx> MirPass<'tcx> for SimplifyCfg {
59 fn name(&self) -> Cow<'_, str> {
60 Cow::Borrowed(&self.label)
63 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
64 debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, body.source);
65 simplify_cfg(tcx, body);
69 pub struct CfgSimplifier<'a, 'tcx> {
70 basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>,
71 pred_count: IndexVec<BasicBlock, u32>,
74 impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
75 pub fn new(body: &'a mut Body<'tcx>) -> Self {
76 let mut pred_count = IndexVec::from_elem(0u32, body.basic_blocks());
78 // we can't use mir.predecessors() here because that counts
79 // dead blocks, which we don't want to.
80 pred_count[START_BLOCK] = 1;
82 for (_, data) in traversal::preorder(body) {
83 if let Some(ref term) = data.terminator {
84 for &tgt in term.successors() {
90 let basic_blocks = body.basic_blocks_mut();
92 CfgSimplifier { basic_blocks, pred_count }
95 pub fn simplify(mut self) {
98 let mut start = START_BLOCK;
100 // Vec of the blocks that should be merged. We store the indices here, instead of the
101 // statements itself to avoid moving the (relatively) large statements twice.
102 // We do not push the statements directly into the target block (`bb`) as that is slower
103 // due to additional reallocations
104 let mut merged_blocks = Vec::new();
106 let mut changed = false;
108 self.collapse_goto_chain(&mut start, &mut changed);
110 for bb in self.basic_blocks.indices() {
111 if self.pred_count[bb] == 0 {
115 debug!("simplifying {:?}", bb);
118 self.basic_blocks[bb].terminator.take().expect("invalid terminator state");
120 for successor in terminator.successors_mut() {
121 self.collapse_goto_chain(successor, &mut changed);
124 let mut inner_changed = true;
125 merged_blocks.clear();
126 while inner_changed {
127 inner_changed = false;
128 inner_changed |= self.simplify_branch(&mut terminator);
129 inner_changed |= self.merge_successor(&mut merged_blocks, &mut terminator);
130 changed |= inner_changed;
133 let statements_to_merge =
134 merged_blocks.iter().map(|&i| self.basic_blocks[i].statements.len()).sum();
136 if statements_to_merge > 0 {
137 let mut statements = std::mem::take(&mut self.basic_blocks[bb].statements);
138 statements.reserve(statements_to_merge);
139 for &from in &merged_blocks {
140 statements.append(&mut self.basic_blocks[from].statements);
142 self.basic_blocks[bb].statements = statements;
145 self.basic_blocks[bb].terminator = Some(terminator);
153 if start != START_BLOCK {
154 debug_assert!(self.pred_count[START_BLOCK] == 0);
155 self.basic_blocks.swap(START_BLOCK, start);
156 self.pred_count.swap(START_BLOCK, start);
158 // pred_count == 1 if the start block has no predecessor _blocks_.
159 if self.pred_count[START_BLOCK] > 1 {
160 for (bb, data) in self.basic_blocks.iter_enumerated_mut() {
161 if self.pred_count[bb] == 0 {
165 for target in data.terminator_mut().successors_mut() {
166 if *target == start {
167 *target = START_BLOCK;
175 /// This function will return `None` if
176 /// * the block has statements
177 /// * the block has a terminator other than `goto`
178 /// * the block has no terminator (meaning some other part of the current optimization stole it)
179 fn take_terminator_if_simple_goto(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> {
180 match self.basic_blocks[bb] {
184 ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }),
186 } if statements.is_empty() => terminator.take(),
187 // if `terminator` is None, this means we are in a loop. In that
188 // case, let all the loop collapse to its entry.
193 /// Collapse a goto chain starting from `start`
194 fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
195 // Using `SmallVec` here, because in some logs on libcore oli-obk saw many single-element
196 // goto chains. We should probably benchmark different sizes.
197 let mut terminators: SmallVec<[_; 1]> = Default::default();
198 let mut current = *start;
199 while let Some(terminator) = self.take_terminator_if_simple_goto(current) {
200 let target = match terminator {
201 Terminator { kind: TerminatorKind::Goto { target }, .. } => target,
204 terminators.push((current, terminator));
209 while let Some((current, mut terminator)) = terminators.pop() {
210 let target = match terminator {
211 Terminator { kind: TerminatorKind::Goto { ref mut target }, .. } => target,
214 *changed |= *target != last;
216 debug!("collapsing goto chain from {:?} to {:?}", current, target);
218 if self.pred_count[current] == 1 {
219 // This is the last reference to current, so the pred-count to
220 // to target is moved into the current block.
221 self.pred_count[current] = 0;
223 self.pred_count[*target] += 1;
224 self.pred_count[current] -= 1;
226 self.basic_blocks[current].terminator = Some(terminator);
230 // merge a block with 1 `goto` predecessor to its parent
233 merged_blocks: &mut Vec<BasicBlock>,
234 terminator: &mut Terminator<'tcx>,
236 let target = match terminator.kind {
237 TerminatorKind::Goto { target } if self.pred_count[target] == 1 => target,
241 debug!("merging block {:?} into {:?}", target, terminator);
242 *terminator = match self.basic_blocks[target].terminator.take() {
243 Some(terminator) => terminator,
245 // unreachable loop - this should not be possible, as we
246 // don't strand blocks, but handle it correctly.
251 merged_blocks.push(target);
252 self.pred_count[target] = 0;
257 // turn a branch with all successors identical to a goto
258 fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
259 match terminator.kind {
260 TerminatorKind::SwitchInt { .. } => {}
265 if let Some(&first_succ) = terminator.successors().next() {
266 if terminator.successors().all(|s| *s == first_succ) {
267 let count = terminator.successors().count();
268 self.pred_count[first_succ] -= (count - 1) as u32;
278 debug!("simplifying branch {:?}", terminator);
279 terminator.kind = TerminatorKind::Goto { target: first_succ };
283 fn strip_nops(&mut self) {
284 for blk in self.basic_blocks.iter_mut() {
285 blk.statements.retain(|stmt| !matches!(stmt.kind, StatementKind::Nop))
290 pub fn remove_dead_blocks(tcx: TyCtxt<'tcx>, body: &mut Body<'_>) {
291 let reachable = traversal::reachable_as_bitset(body);
292 let num_blocks = body.basic_blocks().len();
293 if num_blocks == reachable.count() {
297 let basic_blocks = body.basic_blocks_mut();
298 let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
299 let mut used_blocks = 0;
300 for alive_index in reachable.iter() {
301 let alive_index = alive_index.index();
302 replacements[alive_index] = BasicBlock::new(used_blocks);
303 if alive_index != used_blocks {
304 // Swap the next alive block data with the current available slot. Since
305 // alive_index is non-decreasing this is a valid operation.
306 basic_blocks.raw.swap(alive_index, used_blocks);
311 if tcx.sess.instrument_coverage() {
312 save_unreachable_coverage(basic_blocks, used_blocks);
315 basic_blocks.raw.truncate(used_blocks);
317 for block in basic_blocks {
318 for target in block.terminator_mut().successors_mut() {
319 *target = replacements[target.index()];
324 fn save_unreachable_coverage(
325 basic_blocks: &mut IndexVec<BasicBlock, BasicBlockData<'_>>,
326 first_dead_block: usize,
328 // retain coverage info for dead blocks, so coverage reports will still
329 // report `0` executions for the uncovered code regions.
330 let mut dropped_coverage = Vec::new();
331 for dead_block in first_dead_block..basic_blocks.len() {
332 for statement in basic_blocks[BasicBlock::new(dead_block)].statements.iter() {
333 if let StatementKind::Coverage(coverage) = &statement.kind {
334 if let Some(code_region) = &coverage.code_region {
335 dropped_coverage.push((statement.source_info, code_region.clone()));
340 for (source_info, code_region) in dropped_coverage {
341 basic_blocks[START_BLOCK].statements.push(Statement {
343 kind: StatementKind::Coverage(box Coverage {
344 kind: CoverageKind::Unreachable,
345 code_region: Some(code_region),
350 pub struct SimplifyLocals;
352 impl<'tcx> MirPass<'tcx> for SimplifyLocals {
353 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
354 trace!("running SimplifyLocals on {:?}", body.source);
355 simplify_locals(body, tcx);
359 pub fn simplify_locals<'tcx>(body: &mut Body<'tcx>, tcx: TyCtxt<'tcx>) {
360 // First, we're going to get a count of *actual* uses for every `Local`.
361 let mut used_locals = UsedLocals::new(body);
363 // Next, we're going to remove any `Local` with zero actual uses. When we remove those
364 // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals`
365 // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from
366 // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a
367 // fixedpoint where there are no more unused locals.
368 remove_unused_definitions(&mut used_locals, body);
370 // Finally, we'll actually do the work of shrinking `body.local_decls` and remapping the `Local`s.
371 let map = make_local_map(&mut body.local_decls, &used_locals);
373 // Only bother running the `LocalUpdater` if we actually found locals to remove.
374 if map.iter().any(Option::is_none) {
375 // Update references to all vars and tmps now
376 let mut updater = LocalUpdater { map, tcx };
377 updater.visit_body(body);
379 body.local_decls.shrink_to_fit();
383 /// Construct the mapping while swapping out unused stuff out from the `vec`.
384 fn make_local_map<V>(
385 local_decls: &mut IndexVec<Local, V>,
386 used_locals: &UsedLocals,
387 ) -> IndexVec<Local, Option<Local>> {
388 let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*local_decls);
389 let mut used = Local::new(0);
391 for alive_index in local_decls.indices() {
392 // `is_used` treats the `RETURN_PLACE` and arguments as used.
393 if !used_locals.is_used(alive_index) {
397 map[alive_index] = Some(used);
398 if alive_index != used {
399 local_decls.swap(alive_index, used);
401 used.increment_by(1);
403 local_decls.truncate(used.index());
407 /// Keeps track of used & unused locals.
411 use_count: IndexVec<Local, u32>,
415 /// Determines which locals are used & unused in the given body.
416 fn new(body: &Body<'_>) -> Self {
417 let mut this = Self {
419 arg_count: body.arg_count.try_into().unwrap(),
420 use_count: IndexVec::from_elem(0, &body.local_decls),
422 this.visit_body(body);
426 /// Checks if local is used.
428 /// Return place and arguments are always considered used.
429 fn is_used(&self, local: Local) -> bool {
430 trace!("is_used({:?}): use_count: {:?}", local, self.use_count[local]);
431 local.as_u32() <= self.arg_count || self.use_count[local] != 0
434 /// Updates the use counts to reflect the removal of given statement.
435 fn statement_removed(&mut self, statement: &Statement<'tcx>) {
436 self.increment = false;
438 // The location of the statement is irrelevant.
439 let location = Location { block: START_BLOCK, statement_index: 0 };
440 self.visit_statement(statement, location);
443 /// Visits a left-hand side of an assignment.
444 fn visit_lhs(&mut self, place: &Place<'tcx>, location: Location) {
445 if place.is_indirect() {
446 // A use, not a definition.
447 self.visit_place(place, PlaceContext::MutatingUse(MutatingUseContext::Store), location);
449 // A definition. The base local itself is not visited, so this occurrence is not counted
450 // toward its use count. There might be other locals still, used in an indexing
452 self.super_projection(
454 PlaceContext::MutatingUse(MutatingUseContext::Projection),
461 impl Visitor<'_> for UsedLocals {
462 fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
463 match statement.kind {
464 StatementKind::LlvmInlineAsm(..)
465 | StatementKind::CopyNonOverlapping(..)
466 | StatementKind::Retag(..)
467 | StatementKind::Coverage(..)
468 | StatementKind::FakeRead(..)
469 | StatementKind::AscribeUserType(..) => {
470 self.super_statement(statement, location);
473 StatementKind::Nop => {}
475 StatementKind::StorageLive(_local) | StatementKind::StorageDead(_local) => {}
477 StatementKind::Assign(box (ref place, ref rvalue)) => {
478 self.visit_lhs(place, location);
479 self.visit_rvalue(rvalue, location);
482 StatementKind::SetDiscriminant { ref place, variant_index: _ } => {
483 self.visit_lhs(place, location);
488 fn visit_local(&mut self, local: &Local, _ctx: PlaceContext, _location: Location) {
490 self.use_count[*local] += 1;
492 assert_ne!(self.use_count[*local], 0);
493 self.use_count[*local] -= 1;
498 /// Removes unused definitions. Updates the used locals to reflect the changes made.
499 fn remove_unused_definitions<'a, 'tcx>(used_locals: &'a mut UsedLocals, body: &mut Body<'tcx>) {
500 // The use counts are updated as we remove the statements. A local might become unused
501 // during the retain operation, leading to a temporary inconsistency (storage statements or
502 // definitions referencing the local might remain). For correctness it is crucial that this
503 // computation reaches a fixed point.
505 let mut modified = true;
509 for data in body.basic_blocks_mut() {
510 // Remove unnecessary StorageLive and StorageDead annotations.
511 data.statements.retain(|statement| {
512 let keep = match &statement.kind {
513 StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => {
514 used_locals.is_used(*local)
516 StatementKind::Assign(box (place, _)) => used_locals.is_used(place.local),
518 StatementKind::SetDiscriminant { ref place, .. } => {
519 used_locals.is_used(place.local)
525 trace!("removing statement {:?}", statement);
527 used_locals.statement_removed(statement);
536 struct LocalUpdater<'tcx> {
537 map: IndexVec<Local, Option<Local>>,
541 impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> {
542 fn tcx(&self) -> TyCtxt<'tcx> {
546 fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) {
547 *l = self.map[*l].unwrap();