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