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=2 as this can make programs less debuggable.
  16         sess.mir_opt_level() >= 2
  17     }
  18
  19     fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
  20         let mut unreachable_blocks = FxHashSet::default();
  21         let mut replacements = FxHashMap::default();
  22
  23         for (bb, bb_data) in traversal::postorder(body) {
  24             let terminator = bb_data.terminator();
  25             if terminator.kind == TerminatorKind::Unreachable {
  26                 unreachable_blocks.insert(bb);
  27             } else {
  28                 let is_unreachable = |succ: BasicBlock| unreachable_blocks.contains(&succ);
  29                 let terminator_kind_opt = remove_successors(&terminator.kind, is_unreachable);
  30
  31                 if let Some(terminator_kind) = terminator_kind_opt {
  32                     if terminator_kind == TerminatorKind::Unreachable {
  33                         unreachable_blocks.insert(bb);
  34                     }
  35                     replacements.insert(bb, terminator_kind);
  36                 }
  37             }
  38         }
  39
  40         // We do want do keep some unreachable blocks, but make them empty.
  41         for bb in unreachable_blocks {
  42             if !tcx.consider_optimizing(|| {
  43                 format!("UnreachablePropagation {:?} ", body.source.def_id())
  44             }) {
  45                 break;
  46             }
  47
  48             body.basic_blocks_mut()[bb].statements.clear();
  49         }
  50
  51         let replaced = !replacements.is_empty();
  52
  53         for (bb, terminator_kind) in replacements {
  54             if !tcx.consider_optimizing(|| {
  55                 format!("UnreachablePropagation {:?} ", body.source.def_id())
  56             }) {
  57                 break;
  58             }
  59
  60             body.basic_blocks_mut()[bb].terminator_mut().kind = terminator_kind;
  61         }
  62
  63         if replaced {
  64             simplify::remove_dead_blocks(tcx, body);
  65         }
  66     }
  67 }
  68
  69 fn remove_successors<'tcx, F>(
  70     terminator_kind: &TerminatorKind<'tcx>,
  71     is_unreachable: F,
  72 ) -> Option<TerminatorKind<'tcx>>
  73 where
  74     F: Fn(BasicBlock) -> bool,
  75 {
  76     let terminator = match terminator_kind {
  77         // This will unconditionally run into an unreachable and is therefore unreachable as well.
  78         TerminatorKind::Goto { target } if is_unreachable(*target) => TerminatorKind::Unreachable,
  79         TerminatorKind::SwitchInt { targets, discr } => {
  80             let otherwise = targets.otherwise();
  81
  82             // If all targets are unreachable, we can be unreachable as well.
  83             if targets.all_targets().iter().all(|bb| is_unreachable(*bb)) {
  84                 TerminatorKind::Unreachable
  85             } else if is_unreachable(otherwise) {
  86                 // If there are multiple targets, don't delete unreachable branches (like an unreachable otherwise)
  87                 // unless otherwise is unreachable, in which case deleting a normal branch causes it to be merged with
  88                 // the otherwise, keeping its unreachable.
  89                 // This looses information about reachability causing worse codegen.
  90                 // For example (see tests/codegen/match-optimizes-away.rs)
  91                 //
  92                 // pub enum Two { A, B }
  93                 // pub fn identity(x: Two) -> Two {
  94                 //     match x {
  95                 //         Two::A => Two::A,
  96                 //         Two::B => Two::B,
  97                 //     }
  98                 // }
  99                 //
 100                 // This generates a `switchInt() -> [0: 0, 1: 1, otherwise: unreachable]`, which allows us or LLVM to
 101                 // turn it into just `x` later. Without the unreachable, such a transformation would be illegal.
 102                 // If the otherwise branch is unreachable, we can delete all other unreacahble targets, as they will
 103                 // still point to the unreachable and therefore not lose reachability information.
 104                 let reachable_iter = targets.iter().filter(|(_, bb)| !is_unreachable(*bb));
 105
 106                 let new_targets = SwitchTargets::new(reachable_iter, otherwise);
 107
 108                 // No unreachable branches were removed.
 109                 if new_targets.all_targets().len() == targets.all_targets().len() {
 110                     return None;
 111                 }
 112
 113                 TerminatorKind::SwitchInt { discr: discr.clone(), targets: new_targets }
 114             } else {
 115                 // If the otherwise branch is reachable, we don't want to delete any unreachable branches.
 116                 return None;
 117             }
 118         }
 119         _ => return None,
 120     };
 121     Some(terminator)
 122 }