1 //! A pass that duplicates switch-terminated blocks
2 //! into a new copy for each predecessor, provided
3 //! the predecessor sets the value being switched
4 //! over to a constant.
6 //! The purpose of this pass is to help constant
7 //! propagation passes to simplify the switch terminator
8 //! of the copied blocks into gotos when some predecessors
9 //! statically determine the output of switches.
12 //! x = 12 --- ---> something
16 //! x = y --- ---> something else
20 //! x = 12 ---> switch x ------> something
24 //! x = y ---> switch x ------> something else
26 //! so it can hopefully later be turned by another pass into
28 //! x = 12 --------------------> something
32 //! x = y ---- switch x ------> something else
35 //! This optimization is meant to cover simple cases
36 //! like `?` desugaring. For now, it thus focuses on
37 //! simplicity rather than completeness (it notably
38 //! sometimes duplicates abusively).
41 use rustc_middle::mir::*;
42 use rustc_middle::ty::TyCtxt;
43 use smallvec::SmallVec;
45 pub struct SeparateConstSwitch;
47 impl<'tcx> MirPass<'tcx> for SeparateConstSwitch {
48 fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
49 sess.mir_opt_level() >= 4
52 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
53 // If execution did something, applying a simplification layer
54 // helps later passes optimize the copy away.
55 if separate_const_switch(body) > 0 {
56 super::simplify::simplify_cfg(tcx, body);
61 /// Returns the amount of blocks that were duplicated
62 pub fn separate_const_switch(body: &mut Body<'_>) -> usize {
63 let mut new_blocks: SmallVec<[(BasicBlock, BasicBlock); 6]> = SmallVec::new();
64 let predecessors = body.predecessors();
65 'block_iter: for (block_id, block) in body.basic_blocks().iter_enumerated() {
66 if let TerminatorKind::SwitchInt {
67 discr: Operand::Copy(switch_place) | Operand::Move(switch_place),
69 } = block.terminator().kind
71 // If the block is on an unwind path, do not
72 // apply the optimization as unwind paths
73 // rely on a unique parent invariant
78 // If the block has fewer than 2 predecessors, ignore it
79 // we could maybe chain blocks that have exactly one
80 // predecessor, but for now we ignore that
81 if predecessors[block_id].len() < 2 {
85 // First, let's find a non-const place
86 // that determines the result of the switch
87 if let Some(switch_place) = find_determining_place(switch_place, block) {
88 // We now have an input place for which it would
89 // be interesting if predecessors assigned it from a const
91 let mut predecessors_left = predecessors[block_id].len();
92 'predec_iter: for predecessor_id in predecessors[block_id].iter().copied() {
93 let predecessor = &body.basic_blocks()[predecessor_id];
95 // First we make sure the predecessor jumps
96 // in a reasonable way
97 match &predecessor.terminator().kind {
98 // The following terminators are
99 // unconditionally valid
100 TerminatorKind::Goto { .. } | TerminatorKind::SwitchInt { .. } => {}
102 TerminatorKind::FalseEdge { real_target, .. } => {
103 if *real_target != block_id {
104 continue 'predec_iter;
108 // The following terminators are not allowed
109 TerminatorKind::Resume
110 | TerminatorKind::Drop { .. }
111 | TerminatorKind::DropAndReplace { .. }
112 | TerminatorKind::Call { .. }
113 | TerminatorKind::Assert { .. }
114 | TerminatorKind::FalseUnwind { .. }
115 | TerminatorKind::Yield { .. }
116 | TerminatorKind::Abort
117 | TerminatorKind::Return
118 | TerminatorKind::Unreachable
119 | TerminatorKind::InlineAsm { .. }
120 | TerminatorKind::GeneratorDrop => {
121 continue 'predec_iter;
125 if is_likely_const(switch_place, predecessor) {
126 new_blocks.push((predecessor_id, block_id));
127 predecessors_left -= 1;
128 if predecessors_left < 2 {
129 // If the original block only has one predecessor left,
130 // we have nothing left to do
139 // Once the analysis is done, perform the duplication
140 let body_span = body.span;
141 let copied_blocks = new_blocks.len();
142 let blocks = body.basic_blocks_mut();
143 for (pred_id, target_id) in new_blocks {
144 let new_block = blocks[target_id].clone();
145 let new_block_id = blocks.push(new_block);
146 let terminator = blocks[pred_id].terminator_mut();
148 match terminator.kind {
149 TerminatorKind::Goto { ref mut target } => {
150 *target = new_block_id;
153 TerminatorKind::FalseEdge { ref mut real_target, .. } => {
154 if *real_target == target_id {
155 *real_target = new_block_id;
159 TerminatorKind::SwitchInt { ref mut targets, .. } => {
160 targets.all_targets_mut().iter_mut().for_each(|x| {
167 TerminatorKind::Resume
168 | TerminatorKind::Abort
169 | TerminatorKind::Return
170 | TerminatorKind::Unreachable
171 | TerminatorKind::GeneratorDrop
172 | TerminatorKind::Assert { .. }
173 | TerminatorKind::DropAndReplace { .. }
174 | TerminatorKind::FalseUnwind { .. }
175 | TerminatorKind::Drop { .. }
176 | TerminatorKind::Call { .. }
177 | TerminatorKind::InlineAsm { .. }
178 | TerminatorKind::Yield { .. } => {
181 "basic block terminator had unexpected kind {:?}",
191 /// This function describes a rough heuristic guessing
192 /// whether a place is last set with a const within the block.
193 /// Notably, it will be overly pessimistic in cases that are already
194 /// not handled by `separate_const_switch`.
195 fn is_likely_const<'tcx>(mut tracked_place: Place<'tcx>, block: &BasicBlockData<'tcx>) -> bool {
196 for statement in block.statements.iter().rev() {
197 match &statement.kind {
198 StatementKind::Assign(assign) => {
199 if assign.0 == tracked_place {
201 // These rvalues are definitely constant
202 Rvalue::Use(Operand::Constant(_))
203 | Rvalue::Ref(_, _, _)
204 | Rvalue::AddressOf(_, _)
205 | Rvalue::Cast(_, Operand::Constant(_), _)
206 | Rvalue::NullaryOp(_, _)
207 | Rvalue::ShallowInitBox(_, _)
208 | Rvalue::UnaryOp(_, Operand::Constant(_)) => return true,
210 // These rvalues make things ambiguous
212 | Rvalue::ThreadLocalRef(_)
214 | Rvalue::BinaryOp(_, _)
215 | Rvalue::CheckedBinaryOp(_, _)
216 | Rvalue::Aggregate(_, _) => return false,
218 // These rvalues move the place to track
219 Rvalue::Cast(_, Operand::Copy(place) | Operand::Move(place), _)
220 | Rvalue::Use(Operand::Copy(place) | Operand::Move(place))
221 | Rvalue::UnaryOp(_, Operand::Copy(place) | Operand::Move(place))
222 | Rvalue::Discriminant(place) => tracked_place = place,
227 // If the discriminant is set, it is always set
228 // as a constant, so the job is done.
229 // As we are **ignoring projections**, if the place
230 // we are tracking sees its discriminant be set,
231 // that means we had to be tracking the discriminant
232 // specifically (as it is impossible to switch over
233 // an enum directly, and if we were switching over
234 // its content, we would have had to at least cast it to
235 // some variant first)
236 StatementKind::SetDiscriminant { place, .. } => {
237 if **place == tracked_place {
242 // If inline assembly is found, we probably should
243 // not try to analyze the code
244 StatementKind::LlvmInlineAsm(_) => return false,
246 // These statements have no influence on the place
247 // we are interested in
248 StatementKind::FakeRead(_)
249 | StatementKind::StorageLive(_)
250 | StatementKind::Retag(_, _)
251 | StatementKind::AscribeUserType(_, _)
252 | StatementKind::Coverage(_)
253 | StatementKind::StorageDead(_)
254 | StatementKind::CopyNonOverlapping(_)
255 | StatementKind::Nop => {}
259 // If no good reason for the place to be const is found,
260 // give up. We could maybe go up predecessors, but in
261 // most cases giving up now should be sufficient.
265 /// Finds a unique place that entirely determines the value
266 /// of `switch_place`, if it exists. This is only a heuristic.
267 /// Ideally we would like to track multiple determining places
268 /// for some edge cases, but one is enough for a lot of situations.
269 fn find_determining_place<'tcx>(
270 mut switch_place: Place<'tcx>,
271 block: &BasicBlockData<'tcx>,
272 ) -> Option<Place<'tcx>> {
273 for statement in block.statements.iter().rev() {
274 match &statement.kind {
275 StatementKind::Assign(op) => {
276 if op.0 != switch_place {
281 // The following rvalues move the place
282 // that may be const in the predecessor
283 Rvalue::Use(Operand::Move(new) | Operand::Copy(new))
284 | Rvalue::UnaryOp(_, Operand::Copy(new) | Operand::Move(new))
285 | Rvalue::Cast(_, Operand::Move(new) | Operand::Copy(new), _)
286 | Rvalue::Repeat(Operand::Move(new) | Operand::Copy(new), _)
287 | Rvalue::Discriminant(new)
288 => switch_place = new,
290 // The following rvalues might still make the block
291 // be valid but for now we reject them
293 | Rvalue::Ref(_, _, _)
294 | Rvalue::BinaryOp(_, _)
295 | Rvalue::CheckedBinaryOp(_, _)
296 | Rvalue::Aggregate(_, _)
298 // The following rvalues definitely mean we cannot
299 // or should not apply this optimization
300 | Rvalue::Use(Operand::Constant(_))
301 | Rvalue::Repeat(Operand::Constant(_), _)
302 | Rvalue::ThreadLocalRef(_)
303 | Rvalue::AddressOf(_, _)
304 | Rvalue::NullaryOp(_, _)
305 | Rvalue::ShallowInitBox(_, _)
306 | Rvalue::UnaryOp(_, Operand::Constant(_))
307 | Rvalue::Cast(_, Operand::Constant(_), _)
312 // These statements have no influence on the place
313 // we are interested in
314 StatementKind::FakeRead(_)
315 | StatementKind::StorageLive(_)
316 | StatementKind::StorageDead(_)
317 | StatementKind::Retag(_, _)
318 | StatementKind::AscribeUserType(_, _)
319 | StatementKind::Coverage(_)
320 | StatementKind::CopyNonOverlapping(_)
321 | StatementKind::Nop => {}
323 // If inline assembly is found, we probably should
324 // not try to analyze the code
325 StatementKind::LlvmInlineAsm(_) => return None,
327 // If the discriminant is set, it is always set
328 // as a constant, so the job is already done.
329 // As we are **ignoring projections**, if the place
330 // we are tracking sees its discriminant be set,
331 // that means we had to be tracking the discriminant
332 // specifically (as it is impossible to switch over
333 // an enum directly, and if we were switching over
334 // its content, we would have had to at least cast it to
335 // some variant first)
336 StatementKind::SetDiscriminant { place, .. } => {
337 if **place == switch_place {