compiler/rustc_mir_transform/src/unreachable_prop.rs

   1 //! A pass that propagates the unreachable terminator of a block to its predecessors
   2 //! when all of their successors are unreachable. This is achieved through a
   3 //! post-order traversal of the blocks.
   4
   5 use crate::simplify;
   6 use crate::MirPass;
   7 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
   8 use rustc_middle::mir::*;
   9 use rustc_middle::ty::TyCtxt;
  10
  11 pub struct UnreachablePropagation;
  12
  13 impl MirPass<'_> for UnreachablePropagation {
  14     fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
  15         // Enable only under -Zmir-opt-level=4 as in some cases (check the deeply-nested-opt
  16         // perf benchmark) LLVM may spend quite a lot of time optimizing the generated code.
  17         sess.mir_opt_level() >= 4
  18     }
  19
  20     fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
  21         let mut unreachable_blocks = FxHashSet::default();
  22         let mut replacements = FxHashMap::default();
  23
  24         for (bb, bb_data) in traversal::postorder(body) {
  25             let terminator = bb_data.terminator();
  26             if terminator.kind == TerminatorKind::Unreachable {
  27                 unreachable_blocks.insert(bb);
  28             } else {
  29                 let is_unreachable = |succ: BasicBlock| unreachable_blocks.contains(&succ);
  30                 let terminator_kind_opt = remove_successors(&terminator.kind, is_unreachable);
  31
  32                 if let Some(terminator_kind) = terminator_kind_opt {
  33                     if terminator_kind == TerminatorKind::Unreachable {
  34                         unreachable_blocks.insert(bb);
  35                     }
  36                     replacements.insert(bb, terminator_kind);
  37                 }
  38             }
  39         }
  40
  41         let replaced = !replacements.is_empty();
  42         for (bb, terminator_kind) in replacements {
  43             if !tcx.consider_optimizing(|| {
  44                 format!("UnreachablePropagation {:?} ", body.source.def_id())
  45             }) {
  46                 break;
  47             }
  48
  49             body.basic_blocks_mut()[bb].terminator_mut().kind = terminator_kind;
  50         }
  51
  52         if replaced {
  53             simplify::remove_dead_blocks(tcx, body);
  54         }
  55     }
  56 }
  57
  58 fn remove_successors<'tcx, F>(
  59     terminator_kind: &TerminatorKind<'tcx>,
  60     predicate: F,
  61 ) -> Option<TerminatorKind<'tcx>>
  62 where
  63     F: Fn(BasicBlock) -> bool,
  64 {
  65     let terminator = match *terminator_kind {
  66         TerminatorKind::Goto { target } if predicate(target) => TerminatorKind::Unreachable,
  67         TerminatorKind::SwitchInt { ref discr, switch_ty, ref targets } => {
  68             let otherwise = targets.otherwise();
  69
  70             let original_targets_len = targets.iter().len() + 1;
  71             let (mut values, mut targets): (Vec<_>, Vec<_>) =
  72                 targets.iter().filter(|(_, bb)| !predicate(*bb)).unzip();
  73
  74             if !predicate(otherwise) {
  75                 targets.push(otherwise);
  76             } else {
  77                 values.pop();
  78             }
  79
  80             let retained_targets_len = targets.len();
  81
  82             if targets.is_empty() {
  83                 TerminatorKind::Unreachable
  84             } else if targets.len() == 1 {
  85                 TerminatorKind::Goto { target: targets[0] }
  86             } else if original_targets_len != retained_targets_len {
  87                 TerminatorKind::SwitchInt {
  88                     discr: discr.clone(),
  89                     switch_ty,
  90                     targets: SwitchTargets::new(
  91                         values.iter().copied().zip(targets.iter().copied()),
  92                         *targets.last().unwrap(),
  93                     ),
  94                 }
  95             } else {
  96                 return None;
  97             }
  98         }
  99         _ => return None,
 100     };
 101     Some(terminator)
 102 }