]>
Commit | Line | Data |
---|---|---|
92a42be0 SL |
1 | // Copyright 2015 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
c30ab7b3 | 11 | //! A number of passes which remove various redundancies in the CFG. |
3157f602 | 12 | //! |
c30ab7b3 SL |
13 | //! The `SimplifyCfg` pass gets rid of unnecessary blocks in the CFG, whereas the `SimplifyLocals` |
14 | //! gets rid of all the unnecessary local variable declarations. | |
3157f602 | 15 | //! |
c30ab7b3 SL |
16 | //! The `SimplifyLocals` pass is kinda expensive and therefore not very suitable to be run often. |
17 | //! Most of the passes should not care or be impacted in meaningful ways due to extra locals | |
18 | //! either, so running the pass once, right before translation, should suffice. | |
19 | //! | |
20 | //! On the other side of the spectrum, the `SimplifyCfg` pass is considerably cheap to run, thus | |
21 | //! one should run it after every pass which may modify CFG in significant ways. This pass must | |
22 | //! also be run before any analysis passes because it removes dead blocks, and some of these can be | |
23 | //! ill-typed. | |
24 | //! | |
25 | //! The cause of this typing issue is typeck allowing most blocks whose end is not reachable have | |
26 | //! an arbitrary return type, rather than having the usual () return type (as a note, typeck's | |
27 | //! notion of reachability is in fact slightly weaker than MIR CFG reachability - see #31617). A | |
28 | //! standard example of the situation is: | |
3157f602 | 29 | //! |
3157f602 XL |
30 | //! ```rust |
31 | //! fn example() { | |
32 | //! let _a: char = { return; }; | |
33 | //! } | |
34 | //! ``` | |
35 | //! | |
c30ab7b3 SL |
36 | //! Here the block (`{ return; }`) has the return type `char`, rather than `()`, but the MIR we |
37 | //! naively generate still contains the `_a = ()` write in the unreachable block "after" the | |
38 | //! return. | |
3157f602 | 39 | |
a7813a04 | 40 | use rustc_data_structures::bitvec::BitVector; |
3157f602 | 41 | use rustc_data_structures::indexed_vec::{Idx, IndexVec}; |
54a0048b | 42 | use rustc::ty::TyCtxt; |
c30ab7b3 | 43 | use rustc::mir::*; |
c30ab7b3 | 44 | use rustc::mir::visit::{MutVisitor, Visitor, LvalueContext}; |
7cac9316 | 45 | use std::borrow::Cow; |
abe05a73 | 46 | use transform::{MirPass, MirSource}; |
92a42be0 | 47 | |
7cac9316 | 48 | pub struct SimplifyCfg { label: String } |
a7813a04 | 49 | |
7cac9316 XL |
50 | impl SimplifyCfg { |
51 | pub fn new(label: &str) -> Self { | |
52 | SimplifyCfg { label: format!("SimplifyCfg-{}", label) } | |
92a42be0 | 53 | } |
a7813a04 XL |
54 | } |
55 | ||
cc61c64b XL |
56 | pub fn simplify_cfg(mir: &mut Mir) { |
57 | CfgSimplifier::new(mir).simplify(); | |
58 | remove_dead_blocks(mir); | |
59 | ||
60 | // FIXME: Should probably be moved into some kind of pass manager | |
61 | mir.basic_blocks_mut().raw.shrink_to_fit(); | |
62 | } | |
63 | ||
7cac9316 XL |
64 | impl MirPass for SimplifyCfg { |
65 | fn name<'a>(&'a self) -> Cow<'a, str> { | |
66 | Cow::Borrowed(&self.label) | |
3157f602 | 67 | } |
3157f602 | 68 | |
7cac9316 XL |
69 | fn run_pass<'a, 'tcx>(&self, |
70 | _tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
71 | _src: MirSource, | |
72 | mir: &mut Mir<'tcx>) { | |
73 | debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, mir); | |
74 | simplify_cfg(mir); | |
a7813a04 | 75 | } |
3157f602 XL |
76 | } |
77 | ||
78 | pub struct CfgSimplifier<'a, 'tcx: 'a> { | |
79 | basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, | |
80 | pred_count: IndexVec<BasicBlock, u32> | |
a7813a04 XL |
81 | } |
82 | ||
3157f602 | 83 | impl<'a, 'tcx: 'a> CfgSimplifier<'a, 'tcx> { |
8bb4bdeb | 84 | pub fn new(mir: &'a mut Mir<'tcx>) -> Self { |
3157f602 | 85 | let mut pred_count = IndexVec::from_elem(0u32, mir.basic_blocks()); |
a7813a04 | 86 | |
3157f602 XL |
87 | // we can't use mir.predecessors() here because that counts |
88 | // dead blocks, which we don't want to. | |
c30ab7b3 SL |
89 | pred_count[START_BLOCK] = 1; |
90 | ||
3157f602 XL |
91 | for (_, data) in traversal::preorder(mir) { |
92 | if let Some(ref term) = data.terminator { | |
93 | for &tgt in term.successors().iter() { | |
94 | pred_count[tgt] += 1; | |
95 | } | |
a7813a04 XL |
96 | } |
97 | } | |
3157f602 XL |
98 | |
99 | let basic_blocks = mir.basic_blocks_mut(); | |
100 | ||
101 | CfgSimplifier { | |
3b2f2976 XL |
102 | basic_blocks, |
103 | pred_count, | |
3157f602 | 104 | } |
a7813a04 XL |
105 | } |
106 | ||
8bb4bdeb | 107 | pub fn simplify(mut self) { |
3b2f2976 XL |
108 | self.strip_nops(); |
109 | ||
3157f602 XL |
110 | loop { |
111 | let mut changed = false; | |
112 | ||
113 | for bb in (0..self.basic_blocks.len()).map(BasicBlock::new) { | |
114 | if self.pred_count[bb] == 0 { | |
115 | continue | |
a7813a04 XL |
116 | } |
117 | ||
3157f602 XL |
118 | debug!("simplifying {:?}", bb); |
119 | ||
120 | let mut terminator = self.basic_blocks[bb].terminator.take() | |
121 | .expect("invalid terminator state"); | |
122 | ||
123 | for successor in terminator.successors_mut() { | |
124 | self.collapse_goto_chain(successor, &mut changed); | |
a7813a04 XL |
125 | } |
126 | ||
cc61c64b XL |
127 | changed |= self.simplify_unwind(&mut terminator); |
128 | ||
3157f602 XL |
129 | let mut new_stmts = vec![]; |
130 | let mut inner_changed = true; | |
131 | while inner_changed { | |
132 | inner_changed = false; | |
133 | inner_changed |= self.simplify_branch(&mut terminator); | |
134 | inner_changed |= self.merge_successor(&mut new_stmts, &mut terminator); | |
135 | changed |= inner_changed; | |
92a42be0 | 136 | } |
92a42be0 | 137 | |
3157f602 XL |
138 | self.basic_blocks[bb].statements.extend(new_stmts); |
139 | self.basic_blocks[bb].terminator = Some(terminator); | |
a7813a04 | 140 | |
3157f602 | 141 | changed |= inner_changed; |
a7813a04 | 142 | } |
92a42be0 | 143 | |
3157f602 | 144 | if !changed { break } |
a7813a04 XL |
145 | } |
146 | } | |
a7813a04 | 147 | |
3157f602 XL |
148 | // Collapse a goto chain starting from `start` |
149 | fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) { | |
150 | let mut terminator = match self.basic_blocks[*start] { | |
151 | BasicBlockData { | |
152 | ref statements, | |
153 | terminator: ref mut terminator @ Some(Terminator { | |
154 | kind: TerminatorKind::Goto { .. }, .. | |
155 | }), .. | |
156 | } if statements.is_empty() => terminator.take(), | |
157 | // if `terminator` is None, this means we are in a loop. In that | |
158 | // case, let all the loop collapse to its entry. | |
159 | _ => return | |
160 | }; | |
161 | ||
162 | let target = match terminator { | |
163 | Some(Terminator { kind: TerminatorKind::Goto { ref mut target }, .. }) => { | |
164 | self.collapse_goto_chain(target, changed); | |
165 | *target | |
92a42be0 | 166 | } |
3157f602 XL |
167 | _ => unreachable!() |
168 | }; | |
169 | self.basic_blocks[*start].terminator = terminator; | |
92a42be0 | 170 | |
3157f602 | 171 | debug!("collapsing goto chain from {:?} to {:?}", *start, target); |
a7813a04 | 172 | |
3157f602 | 173 | *changed |= *start != target; |
c30ab7b3 SL |
174 | |
175 | if self.pred_count[*start] == 1 { | |
176 | // This is the last reference to *start, so the pred-count to | |
177 | // to target is moved into the current block. | |
178 | self.pred_count[*start] = 0; | |
179 | } else { | |
180 | self.pred_count[target] += 1; | |
181 | self.pred_count[*start] -= 1; | |
182 | } | |
183 | ||
3157f602 XL |
184 | *start = target; |
185 | } | |
7453a54e | 186 | |
3157f602 XL |
187 | // merge a block with 1 `goto` predecessor to its parent |
188 | fn merge_successor(&mut self, | |
189 | new_stmts: &mut Vec<Statement<'tcx>>, | |
190 | terminator: &mut Terminator<'tcx>) | |
191 | -> bool | |
192 | { | |
193 | let target = match terminator.kind { | |
194 | TerminatorKind::Goto { target } | |
195 | if self.pred_count[target] == 1 | |
196 | => target, | |
197 | _ => return false | |
198 | }; | |
199 | ||
200 | debug!("merging block {:?} into {:?}", target, terminator); | |
201 | *terminator = match self.basic_blocks[target].terminator.take() { | |
202 | Some(terminator) => terminator, | |
203 | None => { | |
204 | // unreachable loop - this should not be possible, as we | |
205 | // don't strand blocks, but handle it correctly. | |
206 | return false | |
207 | } | |
208 | }; | |
209 | new_stmts.extend(self.basic_blocks[target].statements.drain(..)); | |
210 | self.pred_count[target] = 0; | |
7453a54e | 211 | |
3157f602 XL |
212 | true |
213 | } | |
214 | ||
215 | // turn a branch with all successors identical to a goto | |
216 | fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool { | |
217 | match terminator.kind { | |
3157f602 XL |
218 | TerminatorKind::SwitchInt { .. } => {}, |
219 | _ => return false | |
220 | }; | |
221 | ||
222 | let first_succ = { | |
223 | let successors = terminator.successors(); | |
224 | if let Some(&first_succ) = terminator.successors().get(0) { | |
225 | if successors.iter().all(|s| *s == first_succ) { | |
226 | self.pred_count[first_succ] -= (successors.len()-1) as u32; | |
227 | first_succ | |
228 | } else { | |
229 | return false | |
92a42be0 | 230 | } |
3157f602 XL |
231 | } else { |
232 | return false | |
92a42be0 | 233 | } |
3157f602 XL |
234 | }; |
235 | ||
236 | debug!("simplifying branch {:?}", terminator); | |
237 | terminator.kind = TerminatorKind::Goto { target: first_succ }; | |
238 | true | |
239 | } | |
8bb4bdeb | 240 | |
cc61c64b XL |
241 | // turn an unwind branch to a resume block into a None |
242 | fn simplify_unwind(&mut self, terminator: &mut Terminator<'tcx>) -> bool { | |
243 | let unwind = match terminator.kind { | |
244 | TerminatorKind::Drop { ref mut unwind, .. } | | |
245 | TerminatorKind::DropAndReplace { ref mut unwind, .. } | | |
246 | TerminatorKind::Call { cleanup: ref mut unwind, .. } | | |
247 | TerminatorKind::Assert { cleanup: ref mut unwind, .. } => | |
248 | unwind, | |
249 | _ => return false | |
250 | }; | |
251 | ||
252 | if let &mut Some(unwind_block) = unwind { | |
253 | let is_resume_block = match self.basic_blocks[unwind_block] { | |
254 | BasicBlockData { | |
255 | ref statements, | |
256 | terminator: Some(Terminator { | |
257 | kind: TerminatorKind::Resume, .. | |
258 | }), .. | |
259 | } if statements.is_empty() => true, | |
260 | _ => false | |
261 | }; | |
262 | if is_resume_block { | |
263 | debug!("simplifying unwind to {:?} from {:?}", | |
264 | unwind_block, terminator.source_info); | |
265 | *unwind = None; | |
266 | } | |
267 | return is_resume_block; | |
268 | } | |
269 | ||
270 | false | |
271 | } | |
272 | ||
8bb4bdeb XL |
273 | fn strip_nops(&mut self) { |
274 | for blk in self.basic_blocks.iter_mut() { | |
275 | blk.statements.retain(|stmt| if let StatementKind::Nop = stmt.kind { | |
276 | false | |
277 | } else { | |
278 | true | |
279 | }) | |
280 | } | |
281 | } | |
3157f602 XL |
282 | } |
283 | ||
8bb4bdeb | 284 | pub fn remove_dead_blocks(mir: &mut Mir) { |
3157f602 XL |
285 | let mut seen = BitVector::new(mir.basic_blocks().len()); |
286 | for (bb, _) in traversal::preorder(mir) { | |
287 | seen.insert(bb.index()); | |
288 | } | |
289 | ||
290 | let basic_blocks = mir.basic_blocks_mut(); | |
291 | ||
292 | let num_blocks = basic_blocks.len(); | |
293 | let mut replacements : Vec<_> = (0..num_blocks).map(BasicBlock::new).collect(); | |
294 | let mut used_blocks = 0; | |
295 | for alive_index in seen.iter() { | |
296 | replacements[alive_index] = BasicBlock::new(used_blocks); | |
297 | if alive_index != used_blocks { | |
298 | // Swap the next alive block data with the current available slot. Since alive_index is | |
299 | // non-decreasing this is a valid operation. | |
300 | basic_blocks.raw.swap(alive_index, used_blocks); | |
92a42be0 | 301 | } |
3157f602 XL |
302 | used_blocks += 1; |
303 | } | |
304 | basic_blocks.raw.truncate(used_blocks); | |
92a42be0 | 305 | |
3157f602 XL |
306 | for block in basic_blocks { |
307 | for target in block.terminator_mut().successors_mut() { | |
308 | *target = replacements[target.index()]; | |
92a42be0 | 309 | } |
92a42be0 SL |
310 | } |
311 | } | |
c30ab7b3 SL |
312 | |
313 | ||
314 | pub struct SimplifyLocals; | |
315 | ||
7cac9316 XL |
316 | impl MirPass for SimplifyLocals { |
317 | fn run_pass<'a, 'tcx>(&self, | |
318 | _: TyCtxt<'a, 'tcx, 'tcx>, | |
319 | _: MirSource, | |
320 | mir: &mut Mir<'tcx>) { | |
c30ab7b3 SL |
321 | let mut marker = DeclMarker { locals: BitVector::new(mir.local_decls.len()) }; |
322 | marker.visit_mir(mir); | |
323 | // Return pointer and arguments are always live | |
324 | marker.locals.insert(0); | |
325 | for idx in mir.args_iter() { | |
326 | marker.locals.insert(idx.index()); | |
327 | } | |
328 | let map = make_local_map(&mut mir.local_decls, marker.locals); | |
329 | // Update references to all vars and tmps now | |
330 | LocalUpdater { map: map }.visit_mir(mir); | |
331 | mir.local_decls.shrink_to_fit(); | |
332 | } | |
333 | } | |
334 | ||
335 | /// Construct the mapping while swapping out unused stuff out from the `vec`. | |
336 | fn make_local_map<'tcx, I: Idx, V>(vec: &mut IndexVec<I, V>, mask: BitVector) -> Vec<usize> { | |
337 | let mut map: Vec<usize> = ::std::iter::repeat(!0).take(vec.len()).collect(); | |
338 | let mut used = 0; | |
339 | for alive_index in mask.iter() { | |
340 | map[alive_index] = used; | |
341 | if alive_index != used { | |
342 | vec.swap(alive_index, used); | |
343 | } | |
344 | used += 1; | |
345 | } | |
346 | vec.truncate(used); | |
347 | map | |
348 | } | |
349 | ||
350 | struct DeclMarker { | |
351 | pub locals: BitVector, | |
352 | } | |
353 | ||
354 | impl<'tcx> Visitor<'tcx> for DeclMarker { | |
ea8adc8c XL |
355 | fn visit_local(&mut self, local: &Local, ctx: LvalueContext<'tcx>, _: Location) { |
356 | // ignore these altogether, they get removed along with their otherwise unused decls. | |
357 | if ctx != LvalueContext::StorageLive && ctx != LvalueContext::StorageDead { | |
358 | self.locals.insert(local.index()); | |
c30ab7b3 | 359 | } |
c30ab7b3 SL |
360 | } |
361 | } | |
362 | ||
363 | struct LocalUpdater { | |
364 | map: Vec<usize>, | |
365 | } | |
366 | ||
367 | impl<'tcx> MutVisitor<'tcx> for LocalUpdater { | |
368 | fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) { | |
369 | // Remove unnecessary StorageLive and StorageDead annotations. | |
370 | data.statements.retain(|stmt| { | |
371 | match stmt.kind { | |
ea8adc8c XL |
372 | StatementKind::StorageLive(l) | StatementKind::StorageDead(l) => { |
373 | self.map[l.index()] != !0 | |
c30ab7b3 SL |
374 | } |
375 | _ => true | |
376 | } | |
377 | }); | |
378 | self.super_basic_block_data(block, data); | |
379 | } | |
ea8adc8c XL |
380 | fn visit_local(&mut self, l: &mut Local, _: LvalueContext<'tcx>, _: Location) { |
381 | *l = Local::new(self.map[l.index()]); | |
c30ab7b3 SL |
382 | } |
383 | } |