]>
Commit | Line | Data |
---|---|---|
94222f64 XL |
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. | |
5 | //! | |
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. | |
10 | //! | |
11 | //! ```text | |
12 | //! x = 12 --- ---> something | |
13 | //! \ / 12 | |
14 | //! --> switch x | |
15 | //! / \ otherwise | |
16 | //! x = y --- ---> something else | |
17 | //! ``` | |
18 | //! becomes | |
19 | //! ```text | |
20 | //! x = 12 ---> switch x ------> something | |
21 | //! \ / 12 | |
22 | //! X | |
23 | //! / \ otherwise | |
24 | //! x = y ---> switch x ------> something else | |
25 | //! ``` | |
26 | //! so it can hopefully later be turned by another pass into | |
27 | //! ```text | |
28 | //! x = 12 --------------------> something | |
29 | //! / 12 | |
30 | //! / | |
31 | //! / otherwise | |
32 | //! x = y ---- switch x ------> something else | |
33 | //! ``` | |
34 | //! | |
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). | |
39 | ||
c295e0f8 | 40 | use crate::MirPass; |
94222f64 XL |
41 | use rustc_middle::mir::*; |
42 | use rustc_middle::ty::TyCtxt; | |
43 | use smallvec::SmallVec; | |
44 | ||
45 | pub struct SeparateConstSwitch; | |
46 | ||
47 | impl<'tcx> MirPass<'tcx> for SeparateConstSwitch { | |
a2a8927a XL |
48 | fn is_enabled(&self, sess: &rustc_session::Session) -> bool { |
49 | sess.mir_opt_level() >= 4 | |
50 | } | |
94222f64 | 51 | |
a2a8927a | 52 | fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { |
94222f64 XL |
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); | |
57 | } | |
58 | } | |
59 | } | |
60 | ||
61 | /// Returns the amount of blocks that were duplicated | |
a2a8927a | 62 | pub fn separate_const_switch(body: &mut Body<'_>) -> usize { |
94222f64 | 63 | let mut new_blocks: SmallVec<[(BasicBlock, BasicBlock); 6]> = SmallVec::new(); |
064997fb | 64 | let predecessors = body.basic_blocks.predecessors(); |
f2b60f7d | 65 | 'block_iter: for (block_id, block) in body.basic_blocks.iter_enumerated() { |
94222f64 XL |
66 | if let TerminatorKind::SwitchInt { |
67 | discr: Operand::Copy(switch_place) | Operand::Move(switch_place), | |
68 | .. | |
69 | } = block.terminator().kind | |
70 | { | |
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 | |
74 | if block.is_cleanup { | |
75 | continue 'block_iter; | |
76 | } | |
77 | ||
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 { | |
82 | continue 'block_iter; | |
83 | } | |
84 | ||
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 | |
90 | ||
91 | let mut predecessors_left = predecessors[block_id].len(); | |
92 | 'predec_iter: for predecessor_id in predecessors[block_id].iter().copied() { | |
f2b60f7d | 93 | let predecessor = &body.basic_blocks[predecessor_id]; |
94222f64 XL |
94 | |
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 { .. } => {} | |
101 | ||
102 | TerminatorKind::FalseEdge { real_target, .. } => { | |
103 | if *real_target != block_id { | |
104 | continue 'predec_iter; | |
105 | } | |
106 | } | |
107 | ||
108 | // The following terminators are not allowed | |
109 | TerminatorKind::Resume | |
110 | | TerminatorKind::Drop { .. } | |
94222f64 XL |
111 | | TerminatorKind::Call { .. } |
112 | | TerminatorKind::Assert { .. } | |
113 | | TerminatorKind::FalseUnwind { .. } | |
114 | | TerminatorKind::Yield { .. } | |
353b0b11 | 115 | | TerminatorKind::Terminate |
94222f64 XL |
116 | | TerminatorKind::Return |
117 | | TerminatorKind::Unreachable | |
118 | | TerminatorKind::InlineAsm { .. } | |
119 | | TerminatorKind::GeneratorDrop => { | |
120 | continue 'predec_iter; | |
121 | } | |
122 | } | |
123 | ||
124 | if is_likely_const(switch_place, predecessor) { | |
125 | new_blocks.push((predecessor_id, block_id)); | |
126 | predecessors_left -= 1; | |
127 | if predecessors_left < 2 { | |
128 | // If the original block only has one predecessor left, | |
129 | // we have nothing left to do | |
130 | break 'predec_iter; | |
131 | } | |
132 | } | |
133 | } | |
134 | } | |
135 | } | |
136 | } | |
137 | ||
138 | // Once the analysis is done, perform the duplication | |
139 | let body_span = body.span; | |
140 | let copied_blocks = new_blocks.len(); | |
141 | let blocks = body.basic_blocks_mut(); | |
142 | for (pred_id, target_id) in new_blocks { | |
143 | let new_block = blocks[target_id].clone(); | |
144 | let new_block_id = blocks.push(new_block); | |
145 | let terminator = blocks[pred_id].terminator_mut(); | |
146 | ||
147 | match terminator.kind { | |
148 | TerminatorKind::Goto { ref mut target } => { | |
149 | *target = new_block_id; | |
150 | } | |
151 | ||
152 | TerminatorKind::FalseEdge { ref mut real_target, .. } => { | |
153 | if *real_target == target_id { | |
154 | *real_target = new_block_id; | |
155 | } | |
156 | } | |
157 | ||
158 | TerminatorKind::SwitchInt { ref mut targets, .. } => { | |
159 | targets.all_targets_mut().iter_mut().for_each(|x| { | |
160 | if *x == target_id { | |
161 | *x = new_block_id; | |
162 | } | |
163 | }); | |
164 | } | |
165 | ||
166 | TerminatorKind::Resume | |
353b0b11 | 167 | | TerminatorKind::Terminate |
94222f64 XL |
168 | | TerminatorKind::Return |
169 | | TerminatorKind::Unreachable | |
170 | | TerminatorKind::GeneratorDrop | |
171 | | TerminatorKind::Assert { .. } | |
94222f64 XL |
172 | | TerminatorKind::FalseUnwind { .. } |
173 | | TerminatorKind::Drop { .. } | |
174 | | TerminatorKind::Call { .. } | |
175 | | TerminatorKind::InlineAsm { .. } | |
176 | | TerminatorKind::Yield { .. } => { | |
177 | span_bug!( | |
178 | body_span, | |
179 | "basic block terminator had unexpected kind {:?}", | |
180 | &terminator.kind | |
181 | ) | |
182 | } | |
183 | } | |
184 | } | |
185 | ||
186 | copied_blocks | |
187 | } | |
188 | ||
189 | /// This function describes a rough heuristic guessing | |
190 | /// whether a place is last set with a const within the block. | |
191 | /// Notably, it will be overly pessimistic in cases that are already | |
192 | /// not handled by `separate_const_switch`. | |
193 | fn is_likely_const<'tcx>(mut tracked_place: Place<'tcx>, block: &BasicBlockData<'tcx>) -> bool { | |
194 | for statement in block.statements.iter().rev() { | |
195 | match &statement.kind { | |
196 | StatementKind::Assign(assign) => { | |
197 | if assign.0 == tracked_place { | |
198 | match assign.1 { | |
199 | // These rvalues are definitely constant | |
200 | Rvalue::Use(Operand::Constant(_)) | |
201 | | Rvalue::Ref(_, _, _) | |
202 | | Rvalue::AddressOf(_, _) | |
203 | | Rvalue::Cast(_, Operand::Constant(_), _) | |
204 | | Rvalue::NullaryOp(_, _) | |
c295e0f8 | 205 | | Rvalue::ShallowInitBox(_, _) |
94222f64 XL |
206 | | Rvalue::UnaryOp(_, Operand::Constant(_)) => return true, |
207 | ||
208 | // These rvalues make things ambiguous | |
209 | Rvalue::Repeat(_, _) | |
210 | | Rvalue::ThreadLocalRef(_) | |
211 | | Rvalue::Len(_) | |
212 | | Rvalue::BinaryOp(_, _) | |
213 | | Rvalue::CheckedBinaryOp(_, _) | |
214 | | Rvalue::Aggregate(_, _) => return false, | |
215 | ||
216 | // These rvalues move the place to track | |
217 | Rvalue::Cast(_, Operand::Copy(place) | Operand::Move(place), _) | |
218 | | Rvalue::Use(Operand::Copy(place) | Operand::Move(place)) | |
064997fb | 219 | | Rvalue::CopyForDeref(place) |
94222f64 XL |
220 | | Rvalue::UnaryOp(_, Operand::Copy(place) | Operand::Move(place)) |
221 | | Rvalue::Discriminant(place) => tracked_place = place, | |
222 | } | |
223 | } | |
224 | } | |
225 | ||
226 | // If the discriminant is set, it is always set | |
227 | // as a constant, so the job is done. | |
228 | // As we are **ignoring projections**, if the place | |
229 | // we are tracking sees its discriminant be set, | |
230 | // that means we had to be tracking the discriminant | |
231 | // specifically (as it is impossible to switch over | |
232 | // an enum directly, and if we were switching over | |
233 | // its content, we would have had to at least cast it to | |
234 | // some variant first) | |
235 | StatementKind::SetDiscriminant { place, .. } => { | |
236 | if **place == tracked_place { | |
237 | return true; | |
238 | } | |
239 | } | |
240 | ||
94222f64 XL |
241 | // These statements have no influence on the place |
242 | // we are interested in | |
243 | StatementKind::FakeRead(_) | |
04454e1e | 244 | | StatementKind::Deinit(_) |
94222f64 XL |
245 | | StatementKind::StorageLive(_) |
246 | | StatementKind::Retag(_, _) | |
247 | | StatementKind::AscribeUserType(_, _) | |
353b0b11 | 248 | | StatementKind::PlaceMention(..) |
94222f64 XL |
249 | | StatementKind::Coverage(_) |
250 | | StatementKind::StorageDead(_) | |
f2b60f7d | 251 | | StatementKind::Intrinsic(_) |
9ffffee4 | 252 | | StatementKind::ConstEvalCounter |
94222f64 XL |
253 | | StatementKind::Nop => {} |
254 | } | |
255 | } | |
256 | ||
257 | // If no good reason for the place to be const is found, | |
258 | // give up. We could maybe go up predecessors, but in | |
259 | // most cases giving up now should be sufficient. | |
260 | false | |
261 | } | |
262 | ||
263 | /// Finds a unique place that entirely determines the value | |
264 | /// of `switch_place`, if it exists. This is only a heuristic. | |
265 | /// Ideally we would like to track multiple determining places | |
266 | /// for some edge cases, but one is enough for a lot of situations. | |
267 | fn find_determining_place<'tcx>( | |
268 | mut switch_place: Place<'tcx>, | |
269 | block: &BasicBlockData<'tcx>, | |
270 | ) -> Option<Place<'tcx>> { | |
271 | for statement in block.statements.iter().rev() { | |
272 | match &statement.kind { | |
273 | StatementKind::Assign(op) => { | |
274 | if op.0 != switch_place { | |
275 | continue; | |
276 | } | |
277 | ||
278 | match op.1 { | |
279 | // The following rvalues move the place | |
280 | // that may be const in the predecessor | |
281 | Rvalue::Use(Operand::Move(new) | Operand::Copy(new)) | |
282 | | Rvalue::UnaryOp(_, Operand::Copy(new) | Operand::Move(new)) | |
064997fb | 283 | | Rvalue::CopyForDeref(new) |
94222f64 XL |
284 | | Rvalue::Cast(_, Operand::Move(new) | Operand::Copy(new), _) |
285 | | Rvalue::Repeat(Operand::Move(new) | Operand::Copy(new), _) | |
286 | | Rvalue::Discriminant(new) | |
287 | => switch_place = new, | |
288 | ||
289 | // The following rvalues might still make the block | |
290 | // be valid but for now we reject them | |
291 | Rvalue::Len(_) | |
292 | | Rvalue::Ref(_, _, _) | |
293 | | Rvalue::BinaryOp(_, _) | |
294 | | Rvalue::CheckedBinaryOp(_, _) | |
295 | | Rvalue::Aggregate(_, _) | |
296 | ||
297 | // The following rvalues definitely mean we cannot | |
298 | // or should not apply this optimization | |
299 | | Rvalue::Use(Operand::Constant(_)) | |
300 | | Rvalue::Repeat(Operand::Constant(_), _) | |
301 | | Rvalue::ThreadLocalRef(_) | |
302 | | Rvalue::AddressOf(_, _) | |
303 | | Rvalue::NullaryOp(_, _) | |
c295e0f8 | 304 | | Rvalue::ShallowInitBox(_, _) |
94222f64 XL |
305 | | Rvalue::UnaryOp(_, Operand::Constant(_)) |
306 | | Rvalue::Cast(_, Operand::Constant(_), _) | |
307 | => return None, | |
308 | } | |
309 | } | |
310 | ||
311 | // These statements have no influence on the place | |
312 | // we are interested in | |
313 | StatementKind::FakeRead(_) | |
04454e1e | 314 | | StatementKind::Deinit(_) |
94222f64 XL |
315 | | StatementKind::StorageLive(_) |
316 | | StatementKind::StorageDead(_) | |
317 | | StatementKind::Retag(_, _) | |
318 | | StatementKind::AscribeUserType(_, _) | |
353b0b11 | 319 | | StatementKind::PlaceMention(..) |
94222f64 | 320 | | StatementKind::Coverage(_) |
f2b60f7d | 321 | | StatementKind::Intrinsic(_) |
9ffffee4 | 322 | | StatementKind::ConstEvalCounter |
94222f64 XL |
323 | | StatementKind::Nop => {} |
324 | ||
94222f64 XL |
325 | // If the discriminant is set, it is always set |
326 | // as a constant, so the job is already done. | |
327 | // As we are **ignoring projections**, if the place | |
328 | // we are tracking sees its discriminant be set, | |
329 | // that means we had to be tracking the discriminant | |
330 | // specifically (as it is impossible to switch over | |
331 | // an enum directly, and if we were switching over | |
332 | // its content, we would have had to at least cast it to | |
333 | // some variant first) | |
334 | StatementKind::SetDiscriminant { place, .. } => { | |
335 | if **place == switch_place { | |
336 | return None; | |
337 | } | |
338 | } | |
339 | } | |
340 | } | |
341 | ||
342 | Some(switch_place) | |
343 | } |