]>
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 | |
0bf4aa26 | 30 | use rustc_data_structures::bit_set::BitSet; |
3157f602 | 31 | use rustc_data_structures::indexed_vec::{Idx, IndexVec}; |
54a0048b | 32 | use rustc::ty::TyCtxt; |
c30ab7b3 | 33 | use rustc::mir::*; |
ff7c6d11 | 34 | use rustc::mir::visit::{MutVisitor, Visitor, PlaceContext}; |
b7449926 | 35 | use rustc::session::config::DebugInfo; |
7cac9316 | 36 | use std::borrow::Cow; |
9fa01778 | 37 | use crate::transform::{MirPass, MirSource}; |
92a42be0 | 38 | |
7cac9316 | 39 | pub struct SimplifyCfg { label: String } |
a7813a04 | 40 | |
7cac9316 XL |
41 | impl SimplifyCfg { |
42 | pub fn new(label: &str) -> Self { | |
43 | SimplifyCfg { label: format!("SimplifyCfg-{}", label) } | |
92a42be0 | 44 | } |
a7813a04 XL |
45 | } |
46 | ||
dc9dc135 XL |
47 | pub fn simplify_cfg(body: &mut Body<'_>) { |
48 | CfgSimplifier::new(body).simplify(); | |
49 | remove_dead_blocks(body); | |
cc61c64b XL |
50 | |
51 | // FIXME: Should probably be moved into some kind of pass manager | |
dc9dc135 | 52 | body.basic_blocks_mut().raw.shrink_to_fit(); |
cc61c64b XL |
53 | } |
54 | ||
7cac9316 | 55 | impl MirPass for SimplifyCfg { |
416331ca | 56 | fn name(&self) -> Cow<'_, str> { |
7cac9316 | 57 | Cow::Borrowed(&self.label) |
3157f602 | 58 | } |
3157f602 | 59 | |
dc9dc135 XL |
60 | fn run_pass<'tcx>(&self, _tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut Body<'tcx>) { |
61 | debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, body); | |
62 | simplify_cfg(body); | |
a7813a04 | 63 | } |
3157f602 XL |
64 | } |
65 | ||
dc9dc135 | 66 | pub struct CfgSimplifier<'a, 'tcx> { |
3157f602 XL |
67 | basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, |
68 | pred_count: IndexVec<BasicBlock, u32> | |
a7813a04 XL |
69 | } |
70 | ||
dc9dc135 XL |
71 | impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> { |
72 | pub fn new(body: &'a mut Body<'tcx>) -> Self { | |
73 | let mut pred_count = IndexVec::from_elem(0u32, body.basic_blocks()); | |
a7813a04 | 74 | |
3157f602 XL |
75 | // we can't use mir.predecessors() here because that counts |
76 | // dead blocks, which we don't want to. | |
c30ab7b3 SL |
77 | pred_count[START_BLOCK] = 1; |
78 | ||
dc9dc135 | 79 | for (_, data) in traversal::preorder(body) { |
3157f602 | 80 | if let Some(ref term) = data.terminator { |
83c7162d | 81 | for &tgt in term.successors() { |
3157f602 XL |
82 | pred_count[tgt] += 1; |
83 | } | |
a7813a04 XL |
84 | } |
85 | } | |
3157f602 | 86 | |
dc9dc135 | 87 | let basic_blocks = body.basic_blocks_mut(); |
3157f602 XL |
88 | |
89 | CfgSimplifier { | |
3b2f2976 XL |
90 | basic_blocks, |
91 | pred_count, | |
3157f602 | 92 | } |
a7813a04 XL |
93 | } |
94 | ||
8bb4bdeb | 95 | pub fn simplify(mut self) { |
3b2f2976 XL |
96 | self.strip_nops(); |
97 | ||
0731742a XL |
98 | let mut start = START_BLOCK; |
99 | ||
3157f602 XL |
100 | loop { |
101 | let mut changed = false; | |
102 | ||
0731742a XL |
103 | self.collapse_goto_chain(&mut start, &mut changed); |
104 | ||
105 | for bb in self.basic_blocks.indices() { | |
3157f602 XL |
106 | if self.pred_count[bb] == 0 { |
107 | continue | |
a7813a04 XL |
108 | } |
109 | ||
3157f602 XL |
110 | debug!("simplifying {:?}", bb); |
111 | ||
112 | let mut terminator = self.basic_blocks[bb].terminator.take() | |
113 | .expect("invalid terminator state"); | |
114 | ||
115 | for successor in terminator.successors_mut() { | |
116 | self.collapse_goto_chain(successor, &mut changed); | |
a7813a04 XL |
117 | } |
118 | ||
3157f602 XL |
119 | let mut new_stmts = vec![]; |
120 | let mut inner_changed = true; | |
121 | while inner_changed { | |
122 | inner_changed = false; | |
123 | inner_changed |= self.simplify_branch(&mut terminator); | |
124 | inner_changed |= self.merge_successor(&mut new_stmts, &mut terminator); | |
125 | changed |= inner_changed; | |
92a42be0 | 126 | } |
92a42be0 | 127 | |
3157f602 XL |
128 | self.basic_blocks[bb].statements.extend(new_stmts); |
129 | self.basic_blocks[bb].terminator = Some(terminator); | |
a7813a04 | 130 | |
3157f602 | 131 | changed |= inner_changed; |
a7813a04 | 132 | } |
92a42be0 | 133 | |
3157f602 | 134 | if !changed { break } |
a7813a04 | 135 | } |
0731742a XL |
136 | |
137 | if start != START_BLOCK { | |
138 | debug_assert!(self.pred_count[START_BLOCK] == 0); | |
139 | self.basic_blocks.swap(START_BLOCK, start); | |
140 | self.pred_count.swap(START_BLOCK, start); | |
141 | ||
142 | // pred_count == 1 if the start block has no predecessor _blocks_. | |
143 | if self.pred_count[START_BLOCK] > 1 { | |
144 | for (bb, data) in self.basic_blocks.iter_enumerated_mut() { | |
145 | if self.pred_count[bb] == 0 { | |
146 | continue; | |
147 | } | |
148 | ||
149 | for target in data.terminator_mut().successors_mut() { | |
150 | if *target == start { | |
151 | *target = START_BLOCK; | |
152 | } | |
153 | } | |
154 | } | |
155 | } | |
156 | } | |
a7813a04 | 157 | } |
a7813a04 | 158 | |
3157f602 XL |
159 | // Collapse a goto chain starting from `start` |
160 | fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) { | |
161 | let mut terminator = match self.basic_blocks[*start] { | |
162 | BasicBlockData { | |
163 | ref statements, | |
164 | terminator: ref mut terminator @ Some(Terminator { | |
165 | kind: TerminatorKind::Goto { .. }, .. | |
166 | }), .. | |
167 | } if statements.is_empty() => terminator.take(), | |
168 | // if `terminator` is None, this means we are in a loop. In that | |
169 | // case, let all the loop collapse to its entry. | |
170 | _ => return | |
171 | }; | |
172 | ||
173 | let target = match terminator { | |
174 | Some(Terminator { kind: TerminatorKind::Goto { ref mut target }, .. }) => { | |
175 | self.collapse_goto_chain(target, changed); | |
176 | *target | |
92a42be0 | 177 | } |
3157f602 XL |
178 | _ => unreachable!() |
179 | }; | |
180 | self.basic_blocks[*start].terminator = terminator; | |
92a42be0 | 181 | |
3157f602 | 182 | debug!("collapsing goto chain from {:?} to {:?}", *start, target); |
a7813a04 | 183 | |
3157f602 | 184 | *changed |= *start != target; |
c30ab7b3 SL |
185 | |
186 | if self.pred_count[*start] == 1 { | |
187 | // This is the last reference to *start, so the pred-count to | |
188 | // to target is moved into the current block. | |
189 | self.pred_count[*start] = 0; | |
190 | } else { | |
191 | self.pred_count[target] += 1; | |
192 | self.pred_count[*start] -= 1; | |
193 | } | |
194 | ||
3157f602 XL |
195 | *start = target; |
196 | } | |
7453a54e | 197 | |
3157f602 XL |
198 | // merge a block with 1 `goto` predecessor to its parent |
199 | fn merge_successor(&mut self, | |
200 | new_stmts: &mut Vec<Statement<'tcx>>, | |
201 | terminator: &mut Terminator<'tcx>) | |
202 | -> bool | |
203 | { | |
204 | let target = match terminator.kind { | |
205 | TerminatorKind::Goto { target } | |
206 | if self.pred_count[target] == 1 | |
207 | => target, | |
208 | _ => return false | |
209 | }; | |
210 | ||
211 | debug!("merging block {:?} into {:?}", target, terminator); | |
212 | *terminator = match self.basic_blocks[target].terminator.take() { | |
213 | Some(terminator) => terminator, | |
214 | None => { | |
215 | // unreachable loop - this should not be possible, as we | |
216 | // don't strand blocks, but handle it correctly. | |
217 | return false | |
218 | } | |
219 | }; | |
220 | new_stmts.extend(self.basic_blocks[target].statements.drain(..)); | |
221 | self.pred_count[target] = 0; | |
7453a54e | 222 | |
3157f602 XL |
223 | true |
224 | } | |
225 | ||
226 | // turn a branch with all successors identical to a goto | |
227 | fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool { | |
228 | match terminator.kind { | |
3157f602 XL |
229 | TerminatorKind::SwitchInt { .. } => {}, |
230 | _ => return false | |
231 | }; | |
232 | ||
233 | let first_succ = { | |
83c7162d XL |
234 | if let Some(&first_succ) = terminator.successors().nth(0) { |
235 | if terminator.successors().all(|s| *s == first_succ) { | |
236 | let count = terminator.successors().count(); | |
237 | self.pred_count[first_succ] -= (count - 1) as u32; | |
3157f602 XL |
238 | first_succ |
239 | } else { | |
240 | return false | |
92a42be0 | 241 | } |
3157f602 XL |
242 | } else { |
243 | return false | |
92a42be0 | 244 | } |
3157f602 XL |
245 | }; |
246 | ||
247 | debug!("simplifying branch {:?}", terminator); | |
248 | terminator.kind = TerminatorKind::Goto { target: first_succ }; | |
249 | true | |
250 | } | |
8bb4bdeb XL |
251 | |
252 | fn strip_nops(&mut self) { | |
253 | for blk in self.basic_blocks.iter_mut() { | |
254 | blk.statements.retain(|stmt| if let StatementKind::Nop = stmt.kind { | |
255 | false | |
256 | } else { | |
257 | true | |
258 | }) | |
259 | } | |
260 | } | |
3157f602 XL |
261 | } |
262 | ||
dc9dc135 XL |
263 | pub fn remove_dead_blocks(body: &mut Body<'_>) { |
264 | let mut seen = BitSet::new_empty(body.basic_blocks().len()); | |
265 | for (bb, _) in traversal::preorder(body) { | |
3157f602 XL |
266 | seen.insert(bb.index()); |
267 | } | |
268 | ||
dc9dc135 | 269 | let basic_blocks = body.basic_blocks_mut(); |
3157f602 XL |
270 | |
271 | let num_blocks = basic_blocks.len(); | |
272 | let mut replacements : Vec<_> = (0..num_blocks).map(BasicBlock::new).collect(); | |
273 | let mut used_blocks = 0; | |
274 | for alive_index in seen.iter() { | |
275 | replacements[alive_index] = BasicBlock::new(used_blocks); | |
276 | if alive_index != used_blocks { | |
277 | // Swap the next alive block data with the current available slot. Since alive_index is | |
278 | // non-decreasing this is a valid operation. | |
279 | basic_blocks.raw.swap(alive_index, used_blocks); | |
92a42be0 | 280 | } |
3157f602 XL |
281 | used_blocks += 1; |
282 | } | |
283 | basic_blocks.raw.truncate(used_blocks); | |
92a42be0 | 284 | |
3157f602 XL |
285 | for block in basic_blocks { |
286 | for target in block.terminator_mut().successors_mut() { | |
287 | *target = replacements[target.index()]; | |
92a42be0 | 288 | } |
92a42be0 SL |
289 | } |
290 | } | |
c30ab7b3 SL |
291 | |
292 | ||
293 | pub struct SimplifyLocals; | |
294 | ||
7cac9316 | 295 | impl MirPass for SimplifyLocals { |
dc9dc135 XL |
296 | fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut Body<'tcx>) { |
297 | let mut marker = DeclMarker { locals: BitSet::new_empty(body.local_decls.len()) }; | |
298 | marker.visit_body(body); | |
c30ab7b3 | 299 | // Return pointer and arguments are always live |
8faf50e0 | 300 | marker.locals.insert(RETURN_PLACE); |
dc9dc135 | 301 | for arg in body.args_iter() { |
8faf50e0 | 302 | marker.locals.insert(arg); |
c30ab7b3 | 303 | } |
0531ce1d XL |
304 | |
305 | // We may need to keep dead user variables live for debuginfo. | |
b7449926 | 306 | if tcx.sess.opts.debuginfo == DebugInfo::Full { |
dc9dc135 | 307 | for local in body.vars_iter() { |
8faf50e0 | 308 | marker.locals.insert(local); |
0531ce1d XL |
309 | } |
310 | } | |
311 | ||
dc9dc135 | 312 | let map = make_local_map(&mut body.local_decls, marker.locals); |
c30ab7b3 | 313 | // Update references to all vars and tmps now |
dc9dc135 XL |
314 | LocalUpdater { map }.visit_body(body); |
315 | body.local_decls.shrink_to_fit(); | |
c30ab7b3 SL |
316 | } |
317 | } | |
318 | ||
319 | /// Construct the mapping while swapping out unused stuff out from the `vec`. | |
dc9dc135 | 320 | fn make_local_map<V>( |
8faf50e0 | 321 | vec: &mut IndexVec<Local, V>, |
0bf4aa26 | 322 | mask: BitSet<Local>, |
8faf50e0 XL |
323 | ) -> IndexVec<Local, Option<Local>> { |
324 | let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*vec); | |
325 | let mut used = Local::new(0); | |
c30ab7b3 | 326 | for alive_index in mask.iter() { |
8faf50e0 | 327 | map[alive_index] = Some(used); |
c30ab7b3 SL |
328 | if alive_index != used { |
329 | vec.swap(alive_index, used); | |
330 | } | |
8faf50e0 | 331 | used.increment_by(1); |
c30ab7b3 | 332 | } |
8faf50e0 | 333 | vec.truncate(used.index()); |
c30ab7b3 SL |
334 | map |
335 | } | |
336 | ||
337 | struct DeclMarker { | |
0bf4aa26 | 338 | pub locals: BitSet<Local>, |
c30ab7b3 SL |
339 | } |
340 | ||
341 | impl<'tcx> Visitor<'tcx> for DeclMarker { | |
48663c56 | 342 | fn visit_local(&mut self, local: &Local, ctx: PlaceContext, _: Location) { |
13cf67c4 XL |
343 | // Ignore storage markers altogether, they get removed along with their otherwise unused |
344 | // decls. | |
345 | // FIXME: Extend this to all non-uses. | |
346 | if !ctx.is_storage_marker() { | |
8faf50e0 | 347 | self.locals.insert(*local); |
c30ab7b3 | 348 | } |
c30ab7b3 SL |
349 | } |
350 | } | |
351 | ||
352 | struct LocalUpdater { | |
8faf50e0 | 353 | map: IndexVec<Local, Option<Local>>, |
c30ab7b3 SL |
354 | } |
355 | ||
356 | impl<'tcx> MutVisitor<'tcx> for LocalUpdater { | |
357 | fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) { | |
358 | // Remove unnecessary StorageLive and StorageDead annotations. | |
359 | data.statements.retain(|stmt| { | |
360 | match stmt.kind { | |
ea8adc8c | 361 | StatementKind::StorageLive(l) | StatementKind::StorageDead(l) => { |
8faf50e0 | 362 | self.map[l].is_some() |
c30ab7b3 SL |
363 | } |
364 | _ => true | |
365 | } | |
366 | }); | |
367 | self.super_basic_block_data(block, data); | |
368 | } | |
48663c56 | 369 | fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) { |
8faf50e0 | 370 | *l = self.map[*l].unwrap(); |
c30ab7b3 SL |
371 | } |
372 | } |