]> git.proxmox.com Git - rustc.git/blob - src/librustc_mir/transform/remove_dead_blocks.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc_mir / transform / remove_dead_blocks.rs
1 // Copyright 2016 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
11 //! A pass that erases the contents of dead blocks. This pass must
12 //! run before any analysis passes because some of the dead blocks
13 //! can be ill-typed.
14 //!
15 //! The main problem is that typeck lets most blocks whose end is not
16 //! reachable have an arbitrary return type, rather than having the
17 //! usual () return type (as a note, typeck's notion of reachability
18 //! is in fact slightly weaker than MIR CFG reachability - see #31617).
19 //!
20 //! A standard example of the situation is:
21 //! ```rust
22 //! fn example() {
23 //! let _a: char = { return; };
24 //! }
25 //! ```
26 //!
27 //! Here the block (`{ return; }`) has the return type `char`,
28 //! rather than `()`, but the MIR we naively generate still contains
29 //! the `_a = ()` write in the unreachable block "after" the return.
30 //!
31 //! As we have to run this pass even when we want to debug the MIR,
32 //! this pass just replaces the blocks with empty "return" blocks
33 //! and does not renumber anything.
34
35 use rustc_data_structures::bitvec::BitVector;
36 use rustc::ty::TyCtxt;
37 use rustc::mir::repr::*;
38 use rustc::mir::transform::{Pass, MirPass};
39 use syntax::ast::NodeId;
40
41 pub struct RemoveDeadBlocks;
42
43 impl<'tcx> MirPass<'tcx> for RemoveDeadBlocks {
44 fn run_pass(&mut self, _: &TyCtxt<'tcx>, _: NodeId, mir: &mut Mir<'tcx>) {
45 let mut seen = BitVector::new(mir.basic_blocks.len());
46 // These blocks are always required.
47 seen.insert(START_BLOCK.index());
48 seen.insert(END_BLOCK.index());
49
50 let mut worklist = Vec::with_capacity(4);
51 worklist.push(START_BLOCK);
52 while let Some(bb) = worklist.pop() {
53 for succ in mir.basic_block_data(bb).terminator().successors().iter() {
54 if seen.insert(succ.index()) {
55 worklist.push(*succ);
56 }
57 }
58 }
59 retain_basic_blocks(mir, &seen);
60 }
61 }
62
63 impl Pass for RemoveDeadBlocks {}
64
65 /// Mass removal of basic blocks to keep the ID-remapping cheap.
66 fn retain_basic_blocks(mir: &mut Mir, keep: &BitVector) {
67 let num_blocks = mir.basic_blocks.len();
68
69 let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
70 let mut used_blocks = 0;
71 for alive_index in keep.iter() {
72 replacements[alive_index] = BasicBlock::new(used_blocks);
73 if alive_index != used_blocks {
74 // Swap the next alive block data with the current available slot. Since alive_index is
75 // non-decreasing this is a valid operation.
76 mir.basic_blocks.swap(alive_index, used_blocks);
77 }
78 used_blocks += 1;
79 }
80 mir.basic_blocks.truncate(used_blocks);
81
82 for bb in mir.all_basic_blocks() {
83 for target in mir.basic_block_data_mut(bb).terminator_mut().successors_mut() {
84 *target = replacements[target.index()];
85 }
86 }
87 }