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.
7 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
8 use rustc_middle::mir::*;
9 use rustc_middle::ty::TyCtxt;
11 pub struct UnreachablePropagation;
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
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();
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);
28 let is_unreachable = |succ: BasicBlock| unreachable_blocks.contains(&succ);
29 let terminator_kind_opt = remove_successors(&terminator.kind, is_unreachable);
31 if let Some(terminator_kind) = terminator_kind_opt {
32 if terminator_kind == TerminatorKind::Unreachable {
33 unreachable_blocks.insert(bb);
35 replacements.insert(bb, terminator_kind);
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())
48 body.basic_blocks_mut()[bb].statements.clear();
51 let replaced = !replacements.is_empty();
53 for (bb, terminator_kind) in replacements {
54 if !tcx.consider_optimizing(|| {
55 format!("UnreachablePropagation {:?} ", body.source.def_id())
60 body.basic_blocks_mut()[bb].terminator_mut().kind = terminator_kind;
64 simplify::remove_dead_blocks(tcx, body);
69 fn remove_successors<'tcx, F>(
70 terminator_kind: &TerminatorKind<'tcx>,
72 ) -> Option<TerminatorKind<'tcx>>
74 F: Fn(BasicBlock) -> bool,
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, switch_ty } => {
80 let otherwise = targets.otherwise();
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 src/test/codegen/match-optimizes-away.rs)
92 // pub enum Two { A, B }
93 // pub fn identity(x: Two) -> Two {
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));
106 let new_targets = SwitchTargets::new(reachable_iter, otherwise);
108 // No unreachable branches were removed.
109 if new_targets.all_targets().len() == targets.all_targets().len() {
113 TerminatorKind::SwitchInt {
114 discr: discr.clone(),
115 switch_ty: *switch_ty,
116 targets: new_targets,
119 // If the otherwise branch is reachable, we don't want to delete any unreachable branches.