src/librustc_mir/transform/simplify.rs

   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
  11 //! A number of passes which remove various redundancies in the CFG.
  12 //!
  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.
  15 //!
  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:
  29 //!
  30 //! ```rust
  31 //!   fn example() {
  32 //!       let _a: char = { return; };
  33 //!   }
  34 //! ```
  35 //!
  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.
  39
  40 use rustc_data_structures::bitvec::BitVector;
  41 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  42 use rustc::ty::TyCtxt;
  43 use rustc::mir::*;
  44 use rustc::mir::transform::{MirPass, MirSource, Pass};
  45 use rustc::mir::visit::{MutVisitor, Visitor, LvalueContext};
  46 use std::fmt;
  47
  48 pub struct SimplifyCfg<'a> { label: &'a str }
  49
  50 impl<'a> SimplifyCfg<'a> {
  51     pub fn new(label: &'a str) -> Self {
  52         SimplifyCfg { label: label }
  53     }
  54 }
  55
  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
  64 impl<'l, 'tcx> MirPass<'tcx> for SimplifyCfg<'l> {
  65     fn run_pass<'a>(&mut self, _tcx: TyCtxt<'a, 'tcx, 'tcx>, _src: MirSource, mir: &mut Mir<'tcx>) {
  66         debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, mir);
  67         simplify_cfg(mir);
  68     }
  69 }
  70
  71 impl<'l> Pass for SimplifyCfg<'l> {
  72     fn disambiguator<'a>(&'a self) -> Option<Box<fmt::Display+'a>> {
  73         Some(Box::new(self.label))
  74     }
  75
  76     // avoid calling `type_name` - it contains `<'static>`
  77     fn name(&self) -> ::std::borrow::Cow<'static, str> { "SimplifyCfg".into() }
  78 }
  79
  80 pub struct CfgSimplifier<'a, 'tcx: 'a> {
  81     basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>,
  82     pred_count: IndexVec<BasicBlock, u32>
  83 }
  84
  85 impl<'a, 'tcx: 'a> CfgSimplifier<'a, 'tcx> {
  86     pub fn new(mir: &'a mut Mir<'tcx>) -> Self {
  87         let mut pred_count = IndexVec::from_elem(0u32, mir.basic_blocks());
  88
  89         // we can't use mir.predecessors() here because that counts
  90         // dead blocks, which we don't want to.
  91         pred_count[START_BLOCK] = 1;
  92
  93         for (_, data) in traversal::preorder(mir) {
  94             if let Some(ref term) = data.terminator {
  95                 for &tgt in term.successors().iter() {
  96                     pred_count[tgt] += 1;
  97                 }
  98             }
  99         }
 100
 101         let basic_blocks = mir.basic_blocks_mut();
 102
 103         CfgSimplifier {
 104             basic_blocks: basic_blocks,
 105             pred_count: pred_count
 106         }
 107     }
 108
 109     pub fn simplify(mut self) {
 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
 116                 }
 117
 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);
 125                 }
 126
 127                 changed |= self.simplify_unwind(&mut terminator);
 128
 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;
 136                 }
 137
 138                 self.basic_blocks[bb].statements.extend(new_stmts);
 139                 self.basic_blocks[bb].terminator = Some(terminator);
 140
 141                 changed |= inner_changed;
 142             }
 143
 144             if !changed { break }
 145         }
 146
 147         self.strip_nops()
 148     }
 149
 150     // Collapse a goto chain starting from `start`
 151     fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
 152         let mut terminator = match self.basic_blocks[*start] {
 153             BasicBlockData {
 154                 ref statements,
 155                 terminator: ref mut terminator @ Some(Terminator {
 156                     kind: TerminatorKind::Goto { .. }, ..
 157                 }), ..
 158             } if statements.is_empty() => terminator.take(),
 159             // if `terminator` is None, this means we are in a loop. In that
 160             // case, let all the loop collapse to its entry.
 161             _ => return
 162         };
 163
 164         let target = match terminator {
 165             Some(Terminator { kind: TerminatorKind::Goto { ref mut target }, .. }) => {
 166                 self.collapse_goto_chain(target, changed);
 167                 *target
 168             }
 169             _ => unreachable!()
 170         };
 171         self.basic_blocks[*start].terminator = terminator;
 172
 173         debug!("collapsing goto chain from {:?} to {:?}", *start, target);
 174
 175         *changed |= *start != target;
 176
 177         if self.pred_count[*start] == 1 {
 178             // This is the last reference to *start, so the pred-count to
 179             // to target is moved into the current block.
 180             self.pred_count[*start] = 0;
 181         } else {
 182             self.pred_count[target] += 1;
 183             self.pred_count[*start] -= 1;
 184         }
 185
 186         *start = target;
 187     }
 188
 189     // merge a block with 1 `goto` predecessor to its parent
 190     fn merge_successor(&mut self,
 191                        new_stmts: &mut Vec<Statement<'tcx>>,
 192                        terminator: &mut Terminator<'tcx>)
 193                        -> bool
 194     {
 195         let target = match terminator.kind {
 196             TerminatorKind::Goto { target }
 197                 if self.pred_count[target] == 1
 198                 => target,
 199             _ => return false
 200         };
 201
 202         debug!("merging block {:?} into {:?}", target, terminator);
 203         *terminator = match self.basic_blocks[target].terminator.take() {
 204             Some(terminator) => terminator,
 205             None => {
 206                 // unreachable loop - this should not be possible, as we
 207                 // don't strand blocks, but handle it correctly.
 208                 return false
 209             }
 210         };
 211         new_stmts.extend(self.basic_blocks[target].statements.drain(..));
 212         self.pred_count[target] = 0;
 213
 214         true
 215     }
 216
 217     // turn a branch with all successors identical to a goto
 218     fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
 219         match terminator.kind {
 220             TerminatorKind::SwitchInt { .. } => {},
 221             _ => return false
 222         };
 223
 224         let first_succ = {
 225             let successors = terminator.successors();
 226             if let Some(&first_succ) = terminator.successors().get(0) {
 227                 if successors.iter().all(|s| *s == first_succ) {
 228                     self.pred_count[first_succ] -= (successors.len()-1) as u32;
 229                     first_succ
 230                 } else {
 231                     return false
 232                 }
 233             } else {
 234                 return false
 235             }
 236         };
 237
 238         debug!("simplifying branch {:?}", terminator);
 239         terminator.kind = TerminatorKind::Goto { target: first_succ };
 240         true
 241     }
 242
 243     // turn an unwind branch to a resume block into a None
 244     fn simplify_unwind(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
 245         let unwind = match terminator.kind {
 246             TerminatorKind::Drop { ref mut unwind, .. } |
 247             TerminatorKind::DropAndReplace { ref mut unwind, .. } |
 248             TerminatorKind::Call { cleanup: ref mut unwind, .. } |
 249             TerminatorKind::Assert { cleanup: ref mut unwind, .. } =>
 250                 unwind,
 251             _ => return false
 252         };
 253
 254         if let &mut Some(unwind_block) = unwind {
 255             let is_resume_block = match self.basic_blocks[unwind_block] {
 256                 BasicBlockData {
 257                     ref statements,
 258                     terminator: Some(Terminator {
 259                         kind: TerminatorKind::Resume, ..
 260                     }), ..
 261                 } if statements.is_empty() => true,
 262                 _ => false
 263             };
 264             if is_resume_block {
 265                 debug!("simplifying unwind to {:?} from {:?}",
 266                        unwind_block, terminator.source_info);
 267                 *unwind = None;
 268             }
 269             return is_resume_block;
 270         }
 271
 272         false
 273     }
 274
 275     fn strip_nops(&mut self) {
 276         for blk in self.basic_blocks.iter_mut() {
 277             blk.statements.retain(|stmt| if let StatementKind::Nop = stmt.kind {
 278                 false
 279             } else {
 280                 true
 281             })
 282         }
 283     }
 284 }
 285
 286 pub fn remove_dead_blocks(mir: &mut Mir) {
 287     let mut seen = BitVector::new(mir.basic_blocks().len());
 288     for (bb, _) in traversal::preorder(mir) {
 289         seen.insert(bb.index());
 290     }
 291
 292     let basic_blocks = mir.basic_blocks_mut();
 293
 294     let num_blocks = basic_blocks.len();
 295     let mut replacements : Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
 296     let mut used_blocks = 0;
 297     for alive_index in seen.iter() {
 298         replacements[alive_index] = BasicBlock::new(used_blocks);
 299         if alive_index != used_blocks {
 300             // Swap the next alive block data with the current available slot. Since alive_index is
 301             // non-decreasing this is a valid operation.
 302             basic_blocks.raw.swap(alive_index, used_blocks);
 303         }
 304         used_blocks += 1;
 305     }
 306     basic_blocks.raw.truncate(used_blocks);
 307
 308     for block in basic_blocks {
 309         for target in block.terminator_mut().successors_mut() {
 310             *target = replacements[target.index()];
 311         }
 312     }
 313 }
 314
 315
 316 pub struct SimplifyLocals;
 317
 318 impl Pass for SimplifyLocals {
 319     fn name(&self) -> ::std::borrow::Cow<'static, str> { "SimplifyLocals".into() }
 320 }
 321
 322 impl<'tcx> MirPass<'tcx> for SimplifyLocals {
 323     fn run_pass<'a>(&mut self, _: TyCtxt<'a, 'tcx, 'tcx>, _: MirSource, mir: &mut Mir<'tcx>) {
 324         let mut marker = DeclMarker { locals: BitVector::new(mir.local_decls.len()) };
 325         marker.visit_mir(mir);
 326         // Return pointer and arguments are always live
 327         marker.locals.insert(0);
 328         for idx in mir.args_iter() {
 329             marker.locals.insert(idx.index());
 330         }
 331         let map = make_local_map(&mut mir.local_decls, marker.locals);
 332         // Update references to all vars and tmps now
 333         LocalUpdater { map: map }.visit_mir(mir);
 334         mir.local_decls.shrink_to_fit();
 335     }
 336 }
 337
 338 /// Construct the mapping while swapping out unused stuff out from the `vec`.
 339 fn make_local_map<'tcx, I: Idx, V>(vec: &mut IndexVec<I, V>, mask: BitVector) -> Vec<usize> {
 340     let mut map: Vec<usize> = ::std::iter::repeat(!0).take(vec.len()).collect();
 341     let mut used = 0;
 342     for alive_index in mask.iter() {
 343         map[alive_index] = used;
 344         if alive_index != used {
 345             vec.swap(alive_index, used);
 346         }
 347         used += 1;
 348     }
 349     vec.truncate(used);
 350     map
 351 }
 352
 353 struct DeclMarker {
 354     pub locals: BitVector,
 355 }
 356
 357 impl<'tcx> Visitor<'tcx> for DeclMarker {
 358     fn visit_lvalue(&mut self, lval: &Lvalue<'tcx>, ctx: LvalueContext<'tcx>, loc: Location) {
 359         if ctx == LvalueContext::StorageLive || ctx == LvalueContext::StorageDead {
 360             // ignore these altogether, they get removed along with their otherwise unused decls.
 361             return;
 362         }
 363         if let Lvalue::Local(ref v) = *lval {
 364             self.locals.insert(v.index());
 365         }
 366         self.super_lvalue(lval, ctx, loc);
 367     }
 368 }
 369
 370 struct LocalUpdater {
 371     map: Vec<usize>,
 372 }
 373
 374 impl<'tcx> MutVisitor<'tcx> for LocalUpdater {
 375     fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) {
 376         // Remove unnecessary StorageLive and StorageDead annotations.
 377         data.statements.retain(|stmt| {
 378             match stmt.kind {
 379                 StatementKind::StorageLive(ref lval) | StatementKind::StorageDead(ref lval) => {
 380                     match *lval {
 381                         Lvalue::Local(l) => self.map[l.index()] != !0,
 382                         _ => true
 383                     }
 384                 }
 385                 _ => true
 386             }
 387         });
 388         self.super_basic_block_data(block, data);
 389     }
 390     fn visit_lvalue(&mut self, lval: &mut Lvalue<'tcx>, ctx: LvalueContext<'tcx>, loc: Location) {
 391         match *lval {
 392             Lvalue::Local(ref mut l) => *l = Local::new(self.map[l.index()]),
 393             _ => (),
 394         };
 395         self.super_lvalue(lval, ctx, loc);
 396     }
 397 }