compiler/rustc_mir/src/transform/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::transform::simplify;
   6 use crate::transform::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 run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
  15         if tcx.sess.mir_opt_level() < 4 {
  16             // Enable only under -Zmir-opt-level=4 as in some cases (check the deeply-nested-opt
  17             // perf benchmark) LLVM may spend quite a lot of time optimizing the generated code.
  18             return;
  19         }
  20
  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             // HACK: If the block contains any asm statement it is not regarded as unreachable.
  27             // This is a temporary solution that handles possibly diverging asm statements.
  28             // Accompanying testcases: mir-opt/unreachable_asm.rs and mir-opt/unreachable_asm_2.rs
  29             let asm_stmt_in_block = || {
  30                 bb_data.statements.iter().any(|stmt: &Statement<'_>| match stmt.kind {
  31                     StatementKind::LlvmInlineAsm(..) => true,
  32                     _ => false,
  33                 })
  34             };
  35
  36             if terminator.kind == TerminatorKind::Unreachable && !asm_stmt_in_block() {
  37                 unreachable_blocks.insert(bb);
  38             } else {
  39                 let is_unreachable = |succ: BasicBlock| unreachable_blocks.contains(&succ);
  40                 let terminator_kind_opt = remove_successors(&terminator.kind, is_unreachable);
  41
  42                 if let Some(terminator_kind) = terminator_kind_opt {
  43                     if terminator_kind == TerminatorKind::Unreachable && !asm_stmt_in_block() {
  44                         unreachable_blocks.insert(bb);
  45                     }
  46                     replacements.insert(bb, terminator_kind);
  47                 }
  48             }
  49         }
  50
  51         let replaced = !replacements.is_empty();
  52         for (bb, terminator_kind) in replacements {
  53             if !tcx.consider_optimizing(|| {
  54                 format!("UnreachablePropagation {:?} ", body.source.def_id())
  55             }) {
  56                 break;
  57             }
  58
  59             body.basic_blocks_mut()[bb].terminator_mut().kind = terminator_kind;
  60         }
  61
  62         if replaced {
  63             simplify::remove_dead_blocks(tcx, body);
  64         }
  65     }
  66 }
  67
  68 fn remove_successors<F>(
  69     terminator_kind: &TerminatorKind<'tcx>,
  70     predicate: F,
  71 ) -> Option<TerminatorKind<'tcx>>
  72 where
  73     F: Fn(BasicBlock) -> bool,
  74 {
  75     let terminator = match *terminator_kind {
  76         TerminatorKind::Goto { target } if predicate(target) => TerminatorKind::Unreachable,
  77         TerminatorKind::SwitchInt { ref discr, switch_ty, ref targets } => {
  78             let otherwise = targets.otherwise();
  79
  80             let original_targets_len = targets.iter().len() + 1;
  81             let (mut values, mut targets): (Vec<_>, Vec<_>) =
  82                 targets.iter().filter(|(_, bb)| !predicate(*bb)).unzip();
  83
  84             if !predicate(otherwise) {
  85                 targets.push(otherwise);
  86             } else {
  87                 values.pop();
  88             }
  89
  90             let retained_targets_len = targets.len();
  91
  92             if targets.is_empty() {
  93                 TerminatorKind::Unreachable
  94             } else if targets.len() == 1 {
  95                 TerminatorKind::Goto { target: targets[0] }
  96             } else if original_targets_len != retained_targets_len {
  97                 TerminatorKind::SwitchInt {
  98                     discr: discr.clone(),
  99                     switch_ty,
 100                     targets: SwitchTargets::new(
 101                         values.iter().copied().zip(targets.iter().copied()),
 102                         *targets.last().unwrap(),
 103                     ),
 104                 }
 105             } else {
 106                 return None;
 107             }
 108         }
 109         _ => return None,
 110     };
 111     Some(terminator)
 112 }