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