]>
Commit | Line | Data |
---|---|---|
dfeec247 XL |
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 | ||
c295e0f8 XL |
5 | use crate::simplify; |
6 | use crate::MirPass; | |
dfeec247 | 7 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
ba9703b0 XL |
8 | use rustc_middle::mir::*; |
9 | use rustc_middle::ty::TyCtxt; | |
dfeec247 XL |
10 | |
11 | pub struct UnreachablePropagation; | |
12 | ||
13 | impl MirPass<'_> for UnreachablePropagation { | |
a2a8927a | 14 | fn is_enabled(&self, sess: &rustc_session::Session) -> bool { |
f2b60f7d FG |
15 | // Enable only under -Zmir-opt-level=2 as this can make programs less debuggable. |
16 | sess.mir_opt_level() >= 2 | |
a2a8927a | 17 | } |
dfeec247 | 18 | |
a2a8927a | 19 | fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { |
dfeec247 XL |
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(); | |
5099ac24 | 25 | if terminator.kind == TerminatorKind::Unreachable { |
dfeec247 XL |
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 { | |
5099ac24 | 32 | if terminator_kind == TerminatorKind::Unreachable { |
dfeec247 XL |
33 | unreachable_blocks.insert(bb); |
34 | } | |
35 | replacements.insert(bb, terminator_kind); | |
36 | } | |
37 | } | |
38 | } | |
39 | ||
f2b60f7d FG |
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 | ||
dfeec247 | 51 | let replaced = !replacements.is_empty(); |
f2b60f7d | 52 | |
dfeec247 | 53 | for (bb, terminator_kind) in replacements { |
fc512014 XL |
54 | if !tcx.consider_optimizing(|| { |
55 | format!("UnreachablePropagation {:?} ", body.source.def_id()) | |
56 | }) { | |
57 | break; | |
58 | } | |
59 | ||
dfeec247 XL |
60 | body.basic_blocks_mut()[bb].terminator_mut().kind = terminator_kind; |
61 | } | |
62 | ||
63 | if replaced { | |
17df50a5 | 64 | simplify::remove_dead_blocks(tcx, body); |
dfeec247 XL |
65 | } |
66 | } | |
67 | } | |
68 | ||
a2a8927a | 69 | fn remove_successors<'tcx, F>( |
dfeec247 | 70 | terminator_kind: &TerminatorKind<'tcx>, |
f2b60f7d | 71 | is_unreachable: F, |
dfeec247 XL |
72 | ) -> Option<TerminatorKind<'tcx>> |
73 | where | |
74 | F: Fn(BasicBlock) -> bool, | |
75 | { | |
f2b60f7d FG |
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, | |
9c376795 | 79 | TerminatorKind::SwitchInt { targets, discr } => { |
29967ef6 XL |
80 | let otherwise = targets.otherwise(); |
81 | ||
f2b60f7d FG |
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. | |
9c376795 | 90 | // For example (see tests/codegen/match-optimizes-away.rs) |
f2b60f7d FG |
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)); | |
dfeec247 | 105 | |
f2b60f7d | 106 | let new_targets = SwitchTargets::new(reachable_iter, otherwise); |
dfeec247 | 107 | |
f2b60f7d FG |
108 | // No unreachable branches were removed. |
109 | if new_targets.all_targets().len() == targets.all_targets().len() { | |
110 | return None; | |
111 | } | |
dfeec247 | 112 | |
9c376795 | 113 | TerminatorKind::SwitchInt { discr: discr.clone(), targets: new_targets } |
dfeec247 | 114 | } else { |
f2b60f7d | 115 | // If the otherwise branch is reachable, we don't want to delete any unreachable branches. |
3dfed10e | 116 | return None; |
dfeec247 XL |
117 | } |
118 | } | |
3dfed10e XL |
119 | _ => return None, |
120 | }; | |
121 | Some(terminator) | |
dfeec247 | 122 | } |