src/librustc_mir/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, MirSource};
   7 use rustc::mir::*;
   8 use rustc::ty::TyCtxt;
   9 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  10 use std::borrow::Cow;
  11
  12 pub struct UnreachablePropagation;
  13
  14 impl MirPass<'_> for UnreachablePropagation {
  15     fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) {
  16         if tcx.sess.opts.debugging_opts.mir_opt_level < 3 {
  17             // Enable only under -Zmir-opt-level=3 as in some cases (check the deeply-nested-opt
  18             // perf benchmark) LLVM may spend quite a lot of time optimizing the generated code.
  19             return;
  20         }
  21
  22         let mut unreachable_blocks = FxHashSet::default();
  23         let mut replacements = FxHashMap::default();
  24
  25         for (bb, bb_data) in traversal::postorder(body) {
  26             let terminator = bb_data.terminator();
  27             // HACK: If the block contains any asm statement it is not regarded as unreachable.
  28             // This is a temporary solution that handles possibly diverging asm statements.
  29             // Accompanying testcases: mir-opt/unreachable_asm.rs and mir-opt/unreachable_asm_2.rs
  30             let asm_stmt_in_block = || {
  31                 bb_data.statements.iter().any(|stmt: &Statement<'_>| match stmt.kind {
  32                     StatementKind::InlineAsm(..) => true,
  33                     _ => false,
  34                 })
  35             };
  36
  37             if terminator.kind == TerminatorKind::Unreachable && !asm_stmt_in_block() {
  38                 unreachable_blocks.insert(bb);
  39             } else {
  40                 let is_unreachable = |succ: BasicBlock| unreachable_blocks.contains(&succ);
  41                 let terminator_kind_opt = remove_successors(&terminator.kind, is_unreachable);
  42
  43                 if let Some(terminator_kind) = terminator_kind_opt {
  44                     if terminator_kind == TerminatorKind::Unreachable && !asm_stmt_in_block() {
  45                         unreachable_blocks.insert(bb);
  46                     }
  47                     replacements.insert(bb, terminator_kind);
  48                 }
  49             }
  50         }
  51
  52         let replaced = !replacements.is_empty();
  53         for (bb, terminator_kind) in replacements {
  54             body.basic_blocks_mut()[bb].terminator_mut().kind = terminator_kind;
  55         }
  56
  57         if replaced {
  58             simplify::remove_dead_blocks(body);
  59         }
  60     }
  61 }
  62
  63 fn remove_successors<F>(
  64     terminator_kind: &TerminatorKind<'tcx>,
  65     predicate: F,
  66 ) -> Option<TerminatorKind<'tcx>>
  67 where
  68     F: Fn(BasicBlock) -> bool,
  69 {
  70     match *terminator_kind {
  71         TerminatorKind::Goto { target } if predicate(target) => Some(TerminatorKind::Unreachable),
  72         TerminatorKind::SwitchInt { ref discr, switch_ty, ref values, ref targets } => {
  73             let original_targets_len = targets.len();
  74             let (otherwise, targets) = targets.split_last().unwrap();
  75             let retained = values
  76                 .iter()
  77                 .zip(targets.iter())
  78                 .filter(|(_, &t)| !predicate(t))
  79                 .collect::<Vec<_>>();
  80             let mut values = retained.iter().map(|&(v, _)| *v).collect::<Vec<_>>();
  81             let mut targets = retained.iter().map(|&(_, d)| *d).collect::<Vec<_>>();
  82
  83             if !predicate(*otherwise) {
  84                 targets.push(*otherwise);
  85             } else {
  86                 values.pop();
  87             }
  88
  89             let retained_targets_len = targets.len();
  90
  91             if targets.is_empty() {
  92                 Some(TerminatorKind::Unreachable)
  93             } else if targets.len() == 1 {
  94                 Some(TerminatorKind::Goto { target: targets[0] })
  95             } else if original_targets_len != retained_targets_len {
  96                 Some(TerminatorKind::SwitchInt {
  97                     discr: discr.clone(),
  98                     switch_ty,
  99                     values: Cow::from(values),
 100                     targets,
 101                 })
 102             } else {
 103                 None
 104             }
 105         }
 106         _ => None,
 107     }
 108 }