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