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.
5 use crate::transform::simplify;
6 use crate::transform::{MirPass, MirSource};
7 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
8 use rustc_middle::mir::*;
9 use rustc_middle::ty::TyCtxt;
12 pub struct UnreachablePropagation;
14 impl MirPass<'_> for UnreachablePropagation {
15 fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut Body<'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.
22 let mut unreachable_blocks = FxHashSet::default();
23 let mut replacements = FxHashMap::default();
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::LlvmInlineAsm(..) => true,
37 if terminator.kind == TerminatorKind::Unreachable && !asm_stmt_in_block() {
38 unreachable_blocks.insert(bb);
40 let is_unreachable = |succ: BasicBlock| unreachable_blocks.contains(&succ);
41 let terminator_kind_opt = remove_successors(&terminator.kind, is_unreachable);
43 if let Some(terminator_kind) = terminator_kind_opt {
44 if terminator_kind == TerminatorKind::Unreachable && !asm_stmt_in_block() {
45 unreachable_blocks.insert(bb);
47 replacements.insert(bb, terminator_kind);
52 let replaced = !replacements.is_empty();
53 for (bb, terminator_kind) in replacements {
54 body.basic_blocks_mut()[bb].terminator_mut().kind = terminator_kind;
58 simplify::remove_dead_blocks(body);
63 fn remove_successors<F>(
64 terminator_kind: &TerminatorKind<'tcx>,
66 ) -> Option<TerminatorKind<'tcx>>
68 F: Fn(BasicBlock) -> bool,
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();
78 .filter(|(_, &t)| !predicate(t))
80 let mut values = retained.iter().map(|&(v, _)| *v).collect::<Vec<_>>();
81 let mut targets = retained.iter().map(|&(_, d)| *d).collect::<Vec<_>>();
83 if !predicate(*otherwise) {
84 targets.push(*otherwise);
89 let retained_targets_len = targets.len();
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 {
99 values: Cow::from(values),