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
31 use rustc_data_structures
::fx
::FxHashSet
;
32 use rustc_index
::vec
::{Idx, IndexVec}
;
33 use rustc_middle
::mir
::coverage
::*;
34 use rustc_middle
::mir
::visit
::{MutVisitor, MutatingUseContext, PlaceContext, Visitor}
;
35 use rustc_middle
::mir
::*;
36 use rustc_middle
::ty
::TyCtxt
;
37 use smallvec
::SmallVec
;
39 use std
::convert
::TryInto
;
41 pub struct SimplifyCfg
{
46 pub fn new(label
: &str) -> Self {
47 SimplifyCfg { label: format!("SimplifyCfg-{}
", label) }
51 pub fn simplify_cfg<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
52 CfgSimplifier::new(body).simplify();
53 remove_dead_blocks(tcx, body);
55 // FIXME: Should probably be moved into some kind of pass manager
56 body.basic_blocks_mut().raw.shrink_to_fit();
59 impl<'tcx> MirPass<'tcx> for SimplifyCfg {
60 fn name(&self) -> Cow<'_, str> {
61 Cow::Borrowed(&self.label)
64 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
65 debug!("SimplifyCfg({:?}
) - simplifying {:?}
", self.label, body.source);
66 simplify_cfg(tcx, body);
70 pub struct CfgSimplifier<'a, 'tcx> {
71 basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>,
72 pred_count: IndexVec<BasicBlock, u32>,
75 impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
76 pub fn new(body: &'a mut Body<'tcx>) -> Self {
77 let mut pred_count = IndexVec::from_elem(0u32, body.basic_blocks());
79 // we can't use mir.predecessors() here because that counts
80 // dead blocks, which we don't want to.
81 pred_count[START_BLOCK] = 1;
83 for (_, data) in traversal::preorder(body) {
84 if let Some(ref term) = data.terminator {
85 for tgt in term.successors() {
91 let basic_blocks = body.basic_blocks_mut();
93 CfgSimplifier { basic_blocks, pred_count }
96 pub fn simplify(mut self) {
99 // Vec of the blocks that should be merged. We store the indices here, instead of the
100 // statements itself to avoid moving the (relatively) large statements twice.
101 // We do not push the statements directly into the target block (`bb`) as that is slower
102 // due to additional reallocations
103 let mut merged_blocks = Vec::new();
105 let mut changed = false;
107 for bb in self.basic_blocks.indices() {
108 if self.pred_count[bb] == 0 {
112 debug!("simplifying {:?}
", bb);
115 self.basic_blocks[bb].terminator.take().expect("invalid terminator state
");
117 for successor in terminator.successors_mut() {
118 self.collapse_goto_chain(successor, &mut changed);
121 let mut inner_changed = true;
122 merged_blocks.clear();
123 while inner_changed {
124 inner_changed = false;
125 inner_changed |= self.simplify_branch(&mut terminator);
126 inner_changed |= self.merge_successor(&mut merged_blocks, &mut terminator);
127 changed |= inner_changed;
130 let statements_to_merge =
131 merged_blocks.iter().map(|&i| self.basic_blocks[i].statements.len()).sum();
133 if statements_to_merge > 0 {
134 let mut statements = std::mem::take(&mut self.basic_blocks[bb].statements);
135 statements.reserve(statements_to_merge);
136 for &from in &merged_blocks {
137 statements.append(&mut self.basic_blocks[from].statements);
139 self.basic_blocks[bb].statements = statements;
142 self.basic_blocks[bb].terminator = Some(terminator);
151 /// This function will return `None` if
152 /// * the block has statements
153 /// * the block has a terminator other than `goto`
154 /// * the block has no terminator (meaning some other part of the current optimization stole it)
155 fn take_terminator_if_simple_goto(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> {
156 match self.basic_blocks[bb] {
160 ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }),
162 } if statements.is_empty() => terminator.take(),
163 // if `terminator` is None, this means we are in a loop. In that
164 // case, let all the loop collapse to its entry.
169 /// Collapse a goto chain starting from `start`
170 fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
171 // Using `SmallVec` here, because in some logs on libcore oli-obk saw many single-element
172 // goto chains. We should probably benchmark different sizes.
173 let mut terminators: SmallVec<[_; 1]> = Default::default();
174 let mut current = *start;
175 while let Some(terminator) = self.take_terminator_if_simple_goto(current) {
176 let Terminator { kind: TerminatorKind::Goto { target }, .. } = terminator else {
179 terminators.push((current, terminator));
184 while let Some((current, mut terminator)) = terminators.pop() {
185 let Terminator { kind: TerminatorKind::Goto { ref mut target }, .. } = terminator else {
188 *changed |= *target != last;
190 debug!("collapsing goto chain from {:?} to {:?}
", current, target);
192 if self.pred_count[current] == 1 {
193 // This is the last reference to current, so the pred-count to
194 // to target is moved into the current block.
195 self.pred_count[current] = 0;
197 self.pred_count[*target] += 1;
198 self.pred_count[current] -= 1;
200 self.basic_blocks[current].terminator = Some(terminator);
204 // merge a block with 1 `goto` predecessor to its parent
207 merged_blocks: &mut Vec<BasicBlock>,
208 terminator: &mut Terminator<'tcx>,
210 let target = match terminator.kind {
211 TerminatorKind::Goto { target } if self.pred_count[target] == 1 => target,
215 debug!("merging block {:?} into {:?}
", target, terminator);
216 *terminator = match self.basic_blocks[target].terminator.take() {
217 Some(terminator) => terminator,
219 // unreachable loop - this should not be possible, as we
220 // don't strand blocks, but handle it correctly.
225 merged_blocks.push(target);
226 self.pred_count[target] = 0;
231 // turn a branch with all successors identical to a goto
232 fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
233 match terminator.kind {
234 TerminatorKind::SwitchInt { .. } => {}
239 if let Some(first_succ) = terminator.successors().next() {
240 if terminator.successors().all(|s| s == first_succ) {
241 let count = terminator.successors().count();
242 self.pred_count[first_succ] -= (count - 1) as u32;
252 debug!("simplifying branch {:?}
", terminator);
253 terminator.kind = TerminatorKind::Goto { target: first_succ };
257 fn strip_nops(&mut self) {
258 for blk in self.basic_blocks.iter_mut() {
259 blk.statements.retain(|stmt| !matches!(stmt.kind, StatementKind::Nop))
264 pub fn remove_dead_blocks<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
265 let reachable = traversal::reachable_as_bitset(body);
266 let num_blocks = body.basic_blocks().len();
267 if num_blocks == reachable.count() {
271 let basic_blocks = body.basic_blocks.as_mut();
272 let source_scopes = &body.source_scopes;
273 let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
274 let mut used_blocks = 0;
275 for alive_index in reachable.iter() {
276 let alive_index = alive_index.index();
277 replacements[alive_index] = BasicBlock::new(used_blocks);
278 if alive_index != used_blocks {
279 // Swap the next alive block data with the current available slot. Since
280 // alive_index is non-decreasing this is a valid operation.
281 basic_blocks.raw.swap(alive_index, used_blocks);
286 if tcx.sess.instrument_coverage() {
287 save_unreachable_coverage(basic_blocks, source_scopes, used_blocks);
290 basic_blocks.raw.truncate(used_blocks);
292 for block in basic_blocks {
293 for target in block.terminator_mut().successors_mut() {
294 *target = replacements[target.index()];
299 /// Some MIR transforms can determine at compile time that a sequences of
300 /// statements will never be executed, so they can be dropped from the MIR.
301 /// For example, an `if` or `else` block that is guaranteed to never be executed
302 /// because its condition can be evaluated at compile time, such as by const
303 /// evaluation: `if false { ... }`.
305 /// Those statements are bypassed by redirecting paths in the CFG around the
306 /// `dead blocks`; but with `-C instrument-coverage`, the dead blocks usually
307 /// include `Coverage` statements representing the Rust source code regions to
308 /// be counted at runtime. Without these `Coverage` statements, the regions are
309 /// lost, and the Rust source code will show no coverage information.
311 /// What we want to show in a coverage report is the dead code with coverage
312 /// counts of `0`. To do this, we need to save the code regions, by injecting
313 /// `Unreachable` coverage statements. These are non-executable statements whose
314 /// code regions are still recorded in the coverage map, representing regions
315 /// with `0` executions.
317 /// If there are no live `Counter` `Coverage` statements remaining, we remove
318 /// `Coverage` statements along with the dead blocks. Since at least one
319 /// counter per function is required by LLVM (and necessary, to add the
320 /// `function_hash` to the counter's call to the LLVM intrinsic
321 /// `instrprof.increment()`).
323 /// The `generator::StateTransform` MIR pass and MIR inlining can create
324 /// atypical conditions, where all live `Counter`s are dropped from the MIR.
326 /// With MIR inlining we can have coverage counters belonging to different
327 /// instances in a single body, so the strategy described above is applied to
328 /// coverage counters from each instance individually.
329 fn save_unreachable_coverage(
330 basic_blocks: &mut IndexVec<BasicBlock, BasicBlockData<'_>>,
331 source_scopes: &IndexVec<SourceScope, SourceScopeData<'_>>,
332 first_dead_block: usize,
334 // Identify instances that still have some live coverage counters left.
335 let mut live = FxHashSet::default();
336 for basic_block in &basic_blocks.raw[0..first_dead_block] {
337 for statement in &basic_block.statements {
338 let StatementKind::Coverage(coverage) = &statement.kind else { continue };
339 let CoverageKind::Counter { .. } = coverage.kind else { continue };
340 let instance = statement.source_info.scope.inlined_instance(source_scopes);
341 live.insert(instance);
345 for block in &mut basic_blocks.raw[..first_dead_block] {
346 for statement in &mut block.statements {
347 let StatementKind::Coverage(_) = &statement.kind else { continue };
348 let instance = statement.source_info.scope.inlined_instance(source_scopes);
349 if !live.contains(&instance) {
350 statement.make_nop();
359 // Retain coverage for instances that still have some live counters left.
360 let mut retained_coverage = Vec::new();
361 for dead_block in &basic_blocks.raw[first_dead_block..] {
362 for statement in &dead_block.statements {
363 let StatementKind::Coverage(coverage) = &statement.kind else { continue };
364 let Some(code_region) = &coverage.code_region else { continue };
365 let instance = statement.source_info.scope.inlined_instance(source_scopes);
366 if live.contains(&instance) {
367 retained_coverage.push((statement.source_info, code_region.clone()));
372 let start_block = &mut basic_blocks[START_BLOCK];
373 start_block.statements.extend(retained_coverage.into_iter().map(
374 |(source_info, code_region)| Statement {
376 kind: StatementKind::Coverage(Box::new(Coverage {
377 kind: CoverageKind::Unreachable,
378 code_region: Some(code_region),
384 pub struct SimplifyLocals;
386 impl<'tcx> MirPass<'tcx> for SimplifyLocals {
387 fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
388 sess.mir_opt_level() > 0
391 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
392 trace!("running SimplifyLocals on {:?}
", body.source);
393 simplify_locals(body, tcx);
397 pub fn simplify_locals<'tcx>(body: &mut Body<'tcx>, tcx: TyCtxt<'tcx>) {
398 // First, we're going to get a count of *actual* uses for every `Local`.
399 let mut used_locals = UsedLocals::new(body);
401 // Next, we're going to remove any `Local` with zero actual uses. When we remove those
402 // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals`
403 // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from
404 // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a
405 // fixedpoint where there are no more unused locals.
406 remove_unused_definitions(&mut used_locals, body);
408 // Finally, we'll actually do the work of shrinking `body.local_decls` and remapping the `Local`s.
409 let map = make_local_map(&mut body.local_decls, &used_locals);
411 // Only bother running the `LocalUpdater` if we actually found locals to remove.
412 if map.iter().any(Option::is_none) {
413 // Update references to all vars and tmps now
414 let mut updater = LocalUpdater { map, tcx };
415 updater.visit_body(body);
417 body.local_decls.shrink_to_fit();
421 /// Construct the mapping while swapping out unused stuff out from the `vec`.
422 fn make_local_map<V>(
423 local_decls: &mut IndexVec<Local, V>,
424 used_locals: &UsedLocals,
425 ) -> IndexVec<Local, Option<Local>> {
426 let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*local_decls);
427 let mut used = Local::new(0);
429 for alive_index in local_decls.indices() {
430 // `is_used` treats the `RETURN_PLACE` and arguments as used.
431 if !used_locals.is_used(alive_index) {
435 map[alive_index] = Some(used);
436 if alive_index != used {
437 local_decls.swap(alive_index, used);
439 used.increment_by(1);
441 local_decls.truncate(used.index());
445 /// Keeps track of used & unused locals.
449 use_count: IndexVec<Local, u32>,
453 /// Determines which locals are used & unused in the given body.
454 fn new(body: &Body<'_>) -> Self {
455 let mut this = Self {
457 arg_count: body.arg_count.try_into().unwrap(),
458 use_count: IndexVec::from_elem(0, &body.local_decls),
460 this.visit_body(body);
464 /// Checks if local is used.
466 /// Return place and arguments are always considered used.
467 fn is_used(&self, local: Local) -> bool {
468 trace!("is_used({:?}
): use_count
: {:?}
", local, self.use_count[local]);
469 local.as_u32() <= self.arg_count || self.use_count[local] != 0
472 /// Updates the use counts to reflect the removal of given statement.
473 fn statement_removed(&mut self, statement: &Statement<'_>) {
474 self.increment = false;
476 // The location of the statement is irrelevant.
477 let location = Location { block: START_BLOCK, statement_index: 0 };
478 self.visit_statement(statement, location);
481 /// Visits a left-hand side of an assignment.
482 fn visit_lhs(&mut self, place: &Place<'_>, location: Location) {
483 if place.is_indirect() {
484 // A use, not a definition.
485 self.visit_place(place, PlaceContext::MutatingUse(MutatingUseContext::Store), location);
487 // A definition. The base local itself is not visited, so this occurrence is not counted
488 // toward its use count. There might be other locals still, used in an indexing
490 self.super_projection(
492 PlaceContext::MutatingUse(MutatingUseContext::Projection),
499 impl<'tcx> Visitor<'tcx> for UsedLocals {
500 fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
501 match statement.kind {
502 StatementKind::CopyNonOverlapping(..)
503 | StatementKind::Retag(..)
504 | StatementKind::Coverage(..)
505 | StatementKind::FakeRead(..)
506 | StatementKind::AscribeUserType(..) => {
507 self.super_statement(statement, location);
510 StatementKind::Nop => {}
512 StatementKind::StorageLive(_local) | StatementKind::StorageDead(_local) => {}
514 StatementKind::Assign(box (ref place, ref rvalue)) => {
515 if rvalue.is_safe_to_remove() {
516 self.visit_lhs(place, location);
517 self.visit_rvalue(rvalue, location);
519 self.super_statement(statement, location);
523 StatementKind::SetDiscriminant { ref place, variant_index: _ }
524 | StatementKind::Deinit(ref place) => {
525 self.visit_lhs(place, location);
530 fn visit_local(&mut self, local: Local, _ctx: PlaceContext, _location: Location) {
532 self.use_count[local] += 1;
534 assert_ne!(self.use_count[local], 0);
535 self.use_count[local] -= 1;
540 /// Removes unused definitions. Updates the used locals to reflect the changes made.
541 fn remove_unused_definitions(used_locals: &mut UsedLocals, body: &mut Body<'_>) {
542 // The use counts are updated as we remove the statements. A local might become unused
543 // during the retain operation, leading to a temporary inconsistency (storage statements or
544 // definitions referencing the local might remain). For correctness it is crucial that this
545 // computation reaches a fixed point.
547 let mut modified = true;
551 for data in body.basic_blocks_mut() {
552 // Remove unnecessary StorageLive and StorageDead annotations.
553 data.statements.retain(|statement| {
554 let keep = match &statement.kind {
555 StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => {
556 used_locals.is_used(*local)
558 StatementKind::Assign(box (place, _)) => used_locals.is_used(place.local),
560 StatementKind::SetDiscriminant { ref place, .. }
561 | StatementKind::Deinit(ref place) => used_locals.is_used(place.local),
566 trace!("removing statement {:?}
", statement);
568 used_locals.statement_removed(statement);
577 struct LocalUpdater<'tcx> {
578 map: IndexVec<Local, Option<Local>>,
582 impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> {
583 fn tcx(&self) -> TyCtxt<'tcx> {
587 fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) {
588 *l = self.map[*l].unwrap();