]>
Commit | Line | Data |
---|---|---|
c30ab7b3 | 1 | //! A number of passes which remove various redundancies in the CFG. |
3157f602 | 2 | //! |
c30ab7b3 SL |
3 | //! The `SimplifyCfg` pass gets rid of unnecessary blocks in the CFG, whereas the `SimplifyLocals` |
4 | //! gets rid of all the unnecessary local variable declarations. | |
3157f602 | 5 | //! |
c30ab7b3 SL |
6 | //! The `SimplifyLocals` pass is kinda expensive and therefore not very suitable to be run often. |
7 | //! Most of the passes should not care or be impacted in meaningful ways due to extra locals | |
94b46f34 | 8 | //! either, so running the pass once, right before codegen, should suffice. |
c30ab7b3 SL |
9 | //! |
10 | //! On the other side of the spectrum, the `SimplifyCfg` pass is considerably cheap to run, thus | |
11 | //! one should run it after every pass which may modify CFG in significant ways. This pass must | |
12 | //! also be run before any analysis passes because it removes dead blocks, and some of these can be | |
13 | //! ill-typed. | |
14 | //! | |
15 | //! The cause of this typing issue is typeck allowing most blocks whose end is not reachable have | |
16 | //! an arbitrary return type, rather than having the usual () return type (as a note, typeck's | |
17 | //! notion of reachability is in fact slightly weaker than MIR CFG reachability - see #31617). A | |
18 | //! standard example of the situation is: | |
3157f602 | 19 | //! |
3157f602 XL |
20 | //! ```rust |
21 | //! fn example() { | |
22 | //! let _a: char = { return; }; | |
23 | //! } | |
24 | //! ``` | |
25 | //! | |
c30ab7b3 SL |
26 | //! Here the block (`{ return; }`) has the return type `char`, rather than `()`, but the MIR we |
27 | //! naively generate still contains the `_a = ()` write in the unreachable block "after" the | |
28 | //! return. | |
3157f602 | 29 | |
dfeec247 XL |
30 | use crate::transform::{MirPass, MirSource}; |
31 | use rustc::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor}; | |
32 | use rustc::mir::*; | |
33 | use rustc::ty::{self, TyCtxt}; | |
e74abb32 XL |
34 | use rustc_index::bit_set::BitSet; |
35 | use rustc_index::vec::{Idx, IndexVec}; | |
7cac9316 | 36 | use std::borrow::Cow; |
92a42be0 | 37 | |
dfeec247 XL |
38 | pub struct SimplifyCfg { |
39 | label: String, | |
40 | } | |
a7813a04 | 41 | |
7cac9316 XL |
42 | impl SimplifyCfg { |
43 | pub fn new(label: &str) -> Self { | |
44 | SimplifyCfg { label: format!("SimplifyCfg-{}", label) } | |
92a42be0 | 45 | } |
a7813a04 XL |
46 | } |
47 | ||
60c5eb7d | 48 | pub fn simplify_cfg(body: &mut BodyAndCache<'_>) { |
dc9dc135 XL |
49 | CfgSimplifier::new(body).simplify(); |
50 | remove_dead_blocks(body); | |
cc61c64b XL |
51 | |
52 | // FIXME: Should probably be moved into some kind of pass manager | |
dc9dc135 | 53 | body.basic_blocks_mut().raw.shrink_to_fit(); |
cc61c64b XL |
54 | } |
55 | ||
e1599b0c | 56 | impl<'tcx> MirPass<'tcx> for SimplifyCfg { |
416331ca | 57 | fn name(&self) -> Cow<'_, str> { |
7cac9316 | 58 | Cow::Borrowed(&self.label) |
3157f602 | 59 | } |
3157f602 | 60 | |
dfeec247 | 61 | fn run_pass(&self, _tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) { |
dc9dc135 XL |
62 | debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, body); |
63 | simplify_cfg(body); | |
a7813a04 | 64 | } |
3157f602 XL |
65 | } |
66 | ||
dc9dc135 | 67 | pub struct CfgSimplifier<'a, 'tcx> { |
3157f602 | 68 | basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, |
dfeec247 | 69 | pred_count: IndexVec<BasicBlock, u32>, |
a7813a04 XL |
70 | } |
71 | ||
dc9dc135 | 72 | impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> { |
60c5eb7d | 73 | pub fn new(body: &'a mut BodyAndCache<'tcx>) -> Self { |
dc9dc135 | 74 | let mut pred_count = IndexVec::from_elem(0u32, body.basic_blocks()); |
a7813a04 | 75 | |
3157f602 XL |
76 | // we can't use mir.predecessors() here because that counts |
77 | // dead blocks, which we don't want to. | |
c30ab7b3 SL |
78 | pred_count[START_BLOCK] = 1; |
79 | ||
dc9dc135 | 80 | for (_, data) in traversal::preorder(body) { |
3157f602 | 81 | if let Some(ref term) = data.terminator { |
83c7162d | 82 | for &tgt in term.successors() { |
3157f602 XL |
83 | pred_count[tgt] += 1; |
84 | } | |
a7813a04 XL |
85 | } |
86 | } | |
3157f602 | 87 | |
dc9dc135 | 88 | let basic_blocks = body.basic_blocks_mut(); |
3157f602 | 89 | |
dfeec247 | 90 | CfgSimplifier { basic_blocks, pred_count } |
a7813a04 XL |
91 | } |
92 | ||
8bb4bdeb | 93 | pub fn simplify(mut self) { |
3b2f2976 XL |
94 | self.strip_nops(); |
95 | ||
0731742a XL |
96 | let mut start = START_BLOCK; |
97 | ||
3157f602 XL |
98 | loop { |
99 | let mut changed = false; | |
100 | ||
0731742a XL |
101 | self.collapse_goto_chain(&mut start, &mut changed); |
102 | ||
103 | for bb in self.basic_blocks.indices() { | |
3157f602 | 104 | if self.pred_count[bb] == 0 { |
dfeec247 | 105 | continue; |
a7813a04 XL |
106 | } |
107 | ||
3157f602 XL |
108 | debug!("simplifying {:?}", bb); |
109 | ||
dfeec247 XL |
110 | let mut terminator = |
111 | self.basic_blocks[bb].terminator.take().expect("invalid terminator state"); | |
3157f602 XL |
112 | |
113 | for successor in terminator.successors_mut() { | |
114 | self.collapse_goto_chain(successor, &mut changed); | |
a7813a04 XL |
115 | } |
116 | ||
3157f602 XL |
117 | let mut new_stmts = vec![]; |
118 | let mut inner_changed = true; | |
119 | while inner_changed { | |
120 | inner_changed = false; | |
121 | inner_changed |= self.simplify_branch(&mut terminator); | |
122 | inner_changed |= self.merge_successor(&mut new_stmts, &mut terminator); | |
123 | changed |= inner_changed; | |
92a42be0 | 124 | } |
92a42be0 | 125 | |
60c5eb7d XL |
126 | let data = &mut self.basic_blocks[bb]; |
127 | data.statements.extend(new_stmts); | |
128 | data.terminator = Some(terminator); | |
a7813a04 | 129 | |
3157f602 | 130 | changed |= inner_changed; |
a7813a04 | 131 | } |
92a42be0 | 132 | |
dfeec247 XL |
133 | if !changed { |
134 | break; | |
135 | } | |
a7813a04 | 136 | } |
0731742a XL |
137 | |
138 | if start != START_BLOCK { | |
139 | debug_assert!(self.pred_count[START_BLOCK] == 0); | |
140 | self.basic_blocks.swap(START_BLOCK, start); | |
141 | self.pred_count.swap(START_BLOCK, start); | |
142 | ||
143 | // pred_count == 1 if the start block has no predecessor _blocks_. | |
144 | if self.pred_count[START_BLOCK] > 1 { | |
145 | for (bb, data) in self.basic_blocks.iter_enumerated_mut() { | |
146 | if self.pred_count[bb] == 0 { | |
147 | continue; | |
148 | } | |
149 | ||
150 | for target in data.terminator_mut().successors_mut() { | |
151 | if *target == start { | |
152 | *target = START_BLOCK; | |
153 | } | |
154 | } | |
155 | } | |
156 | } | |
157 | } | |
a7813a04 | 158 | } |
a7813a04 | 159 | |
3157f602 XL |
160 | // Collapse a goto chain starting from `start` |
161 | fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) { | |
162 | let mut terminator = match self.basic_blocks[*start] { | |
163 | BasicBlockData { | |
164 | ref statements, | |
dfeec247 XL |
165 | terminator: |
166 | ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }), | |
167 | .. | |
3157f602 XL |
168 | } if statements.is_empty() => terminator.take(), |
169 | // if `terminator` is None, this means we are in a loop. In that | |
170 | // case, let all the loop collapse to its entry. | |
dfeec247 | 171 | _ => return, |
3157f602 XL |
172 | }; |
173 | ||
174 | let target = match terminator { | |
175 | Some(Terminator { kind: TerminatorKind::Goto { ref mut target }, .. }) => { | |
176 | self.collapse_goto_chain(target, changed); | |
177 | *target | |
92a42be0 | 178 | } |
dfeec247 | 179 | _ => unreachable!(), |
3157f602 XL |
180 | }; |
181 | self.basic_blocks[*start].terminator = terminator; | |
92a42be0 | 182 | |
3157f602 | 183 | debug!("collapsing goto chain from {:?} to {:?}", *start, target); |
a7813a04 | 184 | |
3157f602 | 185 | *changed |= *start != target; |
c30ab7b3 SL |
186 | |
187 | if self.pred_count[*start] == 1 { | |
188 | // This is the last reference to *start, so the pred-count to | |
189 | // to target is moved into the current block. | |
190 | self.pred_count[*start] = 0; | |
191 | } else { | |
192 | self.pred_count[target] += 1; | |
193 | self.pred_count[*start] -= 1; | |
194 | } | |
195 | ||
3157f602 XL |
196 | *start = target; |
197 | } | |
7453a54e | 198 | |
3157f602 | 199 | // merge a block with 1 `goto` predecessor to its parent |
dfeec247 XL |
200 | fn merge_successor( |
201 | &mut self, | |
202 | new_stmts: &mut Vec<Statement<'tcx>>, | |
203 | terminator: &mut Terminator<'tcx>, | |
204 | ) -> bool { | |
3157f602 | 205 | let target = match terminator.kind { |
dfeec247 XL |
206 | TerminatorKind::Goto { target } if self.pred_count[target] == 1 => target, |
207 | _ => return false, | |
3157f602 XL |
208 | }; |
209 | ||
210 | debug!("merging block {:?} into {:?}", target, terminator); | |
211 | *terminator = match self.basic_blocks[target].terminator.take() { | |
212 | Some(terminator) => terminator, | |
213 | None => { | |
214 | // unreachable loop - this should not be possible, as we | |
215 | // don't strand blocks, but handle it correctly. | |
dfeec247 | 216 | return false; |
3157f602 XL |
217 | } |
218 | }; | |
219 | new_stmts.extend(self.basic_blocks[target].statements.drain(..)); | |
220 | self.pred_count[target] = 0; | |
7453a54e | 221 | |
3157f602 XL |
222 | true |
223 | } | |
224 | ||
225 | // turn a branch with all successors identical to a goto | |
226 | fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool { | |
227 | match terminator.kind { | |
dfeec247 XL |
228 | TerminatorKind::SwitchInt { .. } => {} |
229 | _ => return false, | |
3157f602 XL |
230 | }; |
231 | ||
232 | let first_succ = { | |
74b04a01 | 233 | if let Some(&first_succ) = terminator.successors().next() { |
83c7162d XL |
234 | if terminator.successors().all(|s| *s == first_succ) { |
235 | let count = terminator.successors().count(); | |
236 | self.pred_count[first_succ] -= (count - 1) as u32; | |
3157f602 XL |
237 | first_succ |
238 | } else { | |
dfeec247 | 239 | return false; |
92a42be0 | 240 | } |
3157f602 | 241 | } else { |
dfeec247 | 242 | return false; |
92a42be0 | 243 | } |
3157f602 XL |
244 | }; |
245 | ||
246 | debug!("simplifying branch {:?}", terminator); | |
247 | terminator.kind = TerminatorKind::Goto { target: first_succ }; | |
248 | true | |
249 | } | |
8bb4bdeb XL |
250 | |
251 | fn strip_nops(&mut self) { | |
252 | for blk in self.basic_blocks.iter_mut() { | |
dfeec247 XL |
253 | blk.statements |
254 | .retain(|stmt| if let StatementKind::Nop = stmt.kind { false } else { true }) | |
8bb4bdeb XL |
255 | } |
256 | } | |
3157f602 XL |
257 | } |
258 | ||
60c5eb7d | 259 | pub fn remove_dead_blocks(body: &mut BodyAndCache<'_>) { |
dc9dc135 XL |
260 | let mut seen = BitSet::new_empty(body.basic_blocks().len()); |
261 | for (bb, _) in traversal::preorder(body) { | |
3157f602 XL |
262 | seen.insert(bb.index()); |
263 | } | |
264 | ||
dc9dc135 | 265 | let basic_blocks = body.basic_blocks_mut(); |
3157f602 XL |
266 | |
267 | let num_blocks = basic_blocks.len(); | |
dfeec247 | 268 | let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect(); |
3157f602 XL |
269 | let mut used_blocks = 0; |
270 | for alive_index in seen.iter() { | |
271 | replacements[alive_index] = BasicBlock::new(used_blocks); | |
272 | if alive_index != used_blocks { | |
60c5eb7d XL |
273 | // Swap the next alive block data with the current available slot. Since |
274 | // alive_index is non-decreasing this is a valid operation. | |
3157f602 | 275 | basic_blocks.raw.swap(alive_index, used_blocks); |
92a42be0 | 276 | } |
3157f602 XL |
277 | used_blocks += 1; |
278 | } | |
279 | basic_blocks.raw.truncate(used_blocks); | |
92a42be0 | 280 | |
3157f602 XL |
281 | for block in basic_blocks { |
282 | for target in block.terminator_mut().successors_mut() { | |
283 | *target = replacements[target.index()]; | |
92a42be0 | 284 | } |
92a42be0 SL |
285 | } |
286 | } | |
c30ab7b3 | 287 | |
c30ab7b3 SL |
288 | pub struct SimplifyLocals; |
289 | ||
e1599b0c | 290 | impl<'tcx> MirPass<'tcx> for SimplifyLocals { |
dfeec247 | 291 | fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) { |
e74abb32 XL |
292 | trace!("running SimplifyLocals on {:?}", source); |
293 | let locals = { | |
60c5eb7d | 294 | let read_only_cache = read_only!(body); |
dfeec247 | 295 | let mut marker = DeclMarker { locals: BitSet::new_empty(body.local_decls.len()), body }; |
60c5eb7d | 296 | marker.visit_body(read_only_cache); |
e74abb32 XL |
297 | // Return pointer and arguments are always live |
298 | marker.locals.insert(RETURN_PLACE); | |
299 | for arg in body.args_iter() { | |
300 | marker.locals.insert(arg); | |
301 | } | |
0531ce1d | 302 | |
e74abb32 XL |
303 | marker.locals |
304 | }; | |
305 | ||
306 | let map = make_local_map(&mut body.local_decls, locals); | |
c30ab7b3 | 307 | // Update references to all vars and tmps now |
e74abb32 | 308 | LocalUpdater { map, tcx }.visit_body(body); |
dc9dc135 | 309 | body.local_decls.shrink_to_fit(); |
c30ab7b3 SL |
310 | } |
311 | } | |
312 | ||
313 | /// Construct the mapping while swapping out unused stuff out from the `vec`. | |
dc9dc135 | 314 | fn make_local_map<V>( |
8faf50e0 | 315 | vec: &mut IndexVec<Local, V>, |
0bf4aa26 | 316 | mask: BitSet<Local>, |
8faf50e0 XL |
317 | ) -> IndexVec<Local, Option<Local>> { |
318 | let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*vec); | |
319 | let mut used = Local::new(0); | |
c30ab7b3 | 320 | for alive_index in mask.iter() { |
8faf50e0 | 321 | map[alive_index] = Some(used); |
c30ab7b3 SL |
322 | if alive_index != used { |
323 | vec.swap(alive_index, used); | |
324 | } | |
8faf50e0 | 325 | used.increment_by(1); |
c30ab7b3 | 326 | } |
8faf50e0 | 327 | vec.truncate(used.index()); |
c30ab7b3 SL |
328 | map |
329 | } | |
330 | ||
e74abb32 | 331 | struct DeclMarker<'a, 'tcx> { |
0bf4aa26 | 332 | pub locals: BitSet<Local>, |
e74abb32 | 333 | pub body: &'a Body<'tcx>, |
c30ab7b3 SL |
334 | } |
335 | ||
e74abb32 XL |
336 | impl<'a, 'tcx> Visitor<'tcx> for DeclMarker<'a, 'tcx> { |
337 | fn visit_local(&mut self, local: &Local, ctx: PlaceContext, location: Location) { | |
13cf67c4 XL |
338 | // Ignore storage markers altogether, they get removed along with their otherwise unused |
339 | // decls. | |
340 | // FIXME: Extend this to all non-uses. | |
e74abb32 XL |
341 | if ctx.is_storage_marker() { |
342 | return; | |
343 | } | |
344 | ||
345 | // Ignore stores of constants because `ConstProp` and `CopyProp` can remove uses of many | |
346 | // of these locals. However, if the local is still needed, then it will be referenced in | |
347 | // another place and we'll mark it as being used there. | |
dfeec247 XL |
348 | if ctx == PlaceContext::MutatingUse(MutatingUseContext::Store) |
349 | || ctx == PlaceContext::MutatingUse(MutatingUseContext::Projection) | |
350 | { | |
60c5eb7d XL |
351 | let block = &self.body.basic_blocks()[location.block]; |
352 | if location.statement_index != block.statements.len() { | |
dfeec247 | 353 | let stmt = &block.statements[location.statement_index]; |
60c5eb7d | 354 | |
dfeec247 XL |
355 | if let StatementKind::Assign(box (p, Rvalue::Use(Operand::Constant(c)))) = |
356 | &stmt.kind | |
357 | { | |
60c5eb7d XL |
358 | match c.literal.val { |
359 | // Keep assignments from unevaluated constants around, since the evaluation | |
360 | // may report errors, even if the use of the constant is dead code. | |
361 | ty::ConstKind::Unevaluated(..) => {} | |
dfeec247 XL |
362 | _ => { |
363 | if !p.is_indirect() { | |
364 | trace!("skipping store of const value {:?} to {:?}", c, p); | |
365 | return; | |
366 | } | |
367 | } | |
60c5eb7d | 368 | } |
e74abb32 XL |
369 | } |
370 | } | |
c30ab7b3 | 371 | } |
e74abb32 XL |
372 | |
373 | self.locals.insert(*local); | |
c30ab7b3 SL |
374 | } |
375 | } | |
376 | ||
e74abb32 | 377 | struct LocalUpdater<'tcx> { |
8faf50e0 | 378 | map: IndexVec<Local, Option<Local>>, |
e74abb32 | 379 | tcx: TyCtxt<'tcx>, |
c30ab7b3 SL |
380 | } |
381 | ||
e74abb32 XL |
382 | impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> { |
383 | fn tcx(&self) -> TyCtxt<'tcx> { | |
384 | self.tcx | |
385 | } | |
386 | ||
c30ab7b3 SL |
387 | fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) { |
388 | // Remove unnecessary StorageLive and StorageDead annotations. | |
dfeec247 XL |
389 | data.statements.retain(|stmt| match &stmt.kind { |
390 | StatementKind::StorageLive(l) | StatementKind::StorageDead(l) => self.map[*l].is_some(), | |
391 | StatementKind::Assign(box (place, _)) => self.map[place.local].is_some(), | |
392 | _ => true, | |
c30ab7b3 SL |
393 | }); |
394 | self.super_basic_block_data(block, data); | |
395 | } | |
e74abb32 | 396 | |
48663c56 | 397 | fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) { |
8faf50e0 | 398 | *l = self.map[*l].unwrap(); |
c30ab7b3 | 399 | } |
e74abb32 | 400 | |
dfeec247 | 401 | fn process_projection_elem(&mut self, elem: &PlaceElem<'tcx>) -> Option<PlaceElem<'tcx>> { |
e74abb32 | 402 | match elem { |
dfeec247 XL |
403 | PlaceElem::Index(local) => Some(PlaceElem::Index(self.map[*local].unwrap())), |
404 | _ => None, | |
e74abb32 XL |
405 | } |
406 | } | |
c30ab7b3 | 407 | } |