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