rustc_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
5use rustc_abi::Size;
6use rustc_data_structures::fx::FxHashSet;
7use rustc_middle::bug;
8use rustc_middle::mir::interpret::Scalar;
9use rustc_middle::mir::*;
10use rustc_middle::ty::{self, TyCtxt};
11
12use crate::PassPolicy;
13use crate::patch::MirPatch;
14
15pub(super) struct UnreachablePropagation;
16
17impl crate::MirPass<'_> for UnreachablePropagation {
18    fn policy(&self, sess: &rustc_session::Session) -> PassPolicy {
19        // Enable only under -Zmir-opt-level=2 as this can make programs less debuggable.
20        PassPolicy::optimization(sess.mir_opt_level() >= 2)
21    }
22
23    fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
24        let mut patch = MirPatch::new(body);
25        let mut unreachable_blocks = FxHashSet::default();
26
27        for (bb, bb_data) in traversal::postorder(body) {
28            let terminator = bb_data.terminator();
29            let is_unreachable = match &terminator.kind {
30                TerminatorKind::Unreachable => true,
31                // This will unconditionally run into an unreachable and is therefore unreachable
32                // as well.
33                TerminatorKind::Goto { target } if unreachable_blocks.contains(target) => {
34                    patch.patch_terminator(bb, TerminatorKind::Unreachable);
35                    true
36                }
37                // Try to remove unreachable targets from the switch.
38                TerminatorKind::SwitchInt { .. } => {
39                    remove_successors_from_switch(tcx, bb, body, &mut patch, |bb| {
40                        unreachable_blocks.contains(&bb)
41                    })
42                }
43                _ => false,
44            };
45            if is_unreachable {
46                unreachable_blocks.insert(bb);
47            }
48        }
49
50        patch.apply(body);
51
52        // We do want do keep some unreachable blocks, but make them empty.
53        // The order in which we clear bb statements does not matter.
54        #[allow(rustc::potential_query_instability)]
55        for bb in unreachable_blocks {
56            body.basic_blocks_mut()[bb].statements.clear();
57        }
58    }
59}
60
61/// Return whether the current terminator is fully unreachable.
62pub(crate) fn remove_successors_from_switch<'tcx>(
63    tcx: TyCtxt<'tcx>,
64    bb: BasicBlock,
65    body: &Body<'tcx>,
66    patch: &mut MirPatch<'tcx>,
67    is_unreachable_block: impl Fn(BasicBlock) -> bool,
68) -> bool {
69    let terminator = body.basic_blocks[bb].terminator();
70    let TerminatorKind::SwitchInt { discr, targets } = &terminator.kind else { bug!() };
71    let source_info = terminator.source_info;
72    let location = body.terminator_loc(bb);
73
74    // If there are multiple targets, we want to keep information about reachability for codegen.
75    // For example (see tests/codegen-llvm/match-optimizes-away.rs)
76    //
77    // pub enum Two { A, B }
78    // pub fn identity(x: Two) -> Two {
79    //     match x {
80    //         Two::A => Two::A,
81    //         Two::B => Two::B,
82    //     }
83    // }
84    //
85    // This generates a `switchInt() -> [0: 0, 1: 1, otherwise: unreachable]`, which allows us or
86    // LLVM to turn it into just `x` later. Without the unreachable, such a transformation would be
87    // illegal.
88    //
89    // In order to preserve this information, we record reachable and unreachable targets as
90    // `Assume` statements in MIR.
91
92    let discr_ty = discr.ty(body, tcx);
93    let discr_size = Size::from_bits(match discr_ty.kind() {
94        ty::Uint(uint) => uint.normalize(tcx.sess.target.pointer_width).bit_width().unwrap(),
95        ty::Int(int) => int.normalize(tcx.sess.target.pointer_width).bit_width().unwrap(),
96        ty::Char => 32,
97        ty::Bool => 1,
98        other => bug!("unhandled type: {:?}", other),
99    });
100
101    let mut add_assumption = |binop, value| {
102        let local = patch.new_temp(tcx.types.bool, source_info.span);
103        let value = Operand::Constant(Box::new(ConstOperand {
104            span: source_info.span,
105            user_ty: None,
106            const_: Const::from_scalar(tcx, Scalar::from_uint(value, discr_size), discr_ty),
107        }));
108        let cmp = Rvalue::BinaryOp(binop, Box::new((discr.to_copy(), value)));
109        patch.add_assign(location, local.into(), cmp);
110
111        let assume = NonDivergingIntrinsic::Assume(Operand::Move(local.into()));
112        patch.add_statement(location, StatementKind::Intrinsic(Box::new(assume)));
113    };
114
115    let otherwise = targets.otherwise();
116    let otherwise_unreachable = is_unreachable_block(otherwise);
117
118    let reachable_iter = targets.iter().filter(|&(value, bb)| {
119        let is_unreachable = is_unreachable_block(bb);
120        // We remove this target from the switch, so record the inequality using `Assume`.
121        if is_unreachable && !otherwise_unreachable {
122            add_assumption(BinOp::Ne, value);
123        }
124        !is_unreachable
125    });
126
127    let new_targets = SwitchTargets::new(reachable_iter, otherwise);
128
129    let num_targets = new_targets.all_targets().len();
130    let fully_unreachable = num_targets == 1 && otherwise_unreachable;
131
132    let terminator = match (num_targets, otherwise_unreachable) {
133        // If all targets are unreachable, we can be unreachable as well.
134        (1, true) => TerminatorKind::Unreachable,
135        (1, false) => TerminatorKind::Goto { target: otherwise },
136        (2, true) => {
137            // All targets are unreachable except one. Record the equality, and make it a goto.
138            let (value, target) = new_targets.iter().next().unwrap();
139            add_assumption(BinOp::Eq, value);
140            TerminatorKind::Goto { target }
141        }
142        _ if num_targets == targets.all_targets().len() => {
143            // Nothing has changed.
144            return false;
145        }
146        _ => TerminatorKind::SwitchInt { discr: discr.clone(), targets: new_targets },
147    };
148
149    patch.patch_terminator(bb, terminator);
150    fully_unreachable
151}
rustc_mir_transform/unreachable_prop.rs

rustc_mir_transform/
unreachable_prop.rs
