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