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_index::bit_set::BitSet;
  32 use rustc_index::vec::{Idx, IndexVec};
  33 use rustc_middle::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor};
  34 use rustc_middle::mir::*;
  35 use rustc_middle::ty::TyCtxt;
  36 use smallvec::SmallVec;
  37 use std::borrow::Cow;
  38
  39 pub struct SimplifyCfg {
  40     label: String,
  41 }
  42
  43 impl SimplifyCfg {
  44     pub fn new(label: &str) -> Self {
  45         SimplifyCfg { label: format!("SimplifyCfg-{}", label) }
  46     }
  47 }
  48
  49 pub fn simplify_cfg(body: &mut Body<'_>) {
  50     CfgSimplifier::new(body).simplify();
  51     remove_dead_blocks(body);
  52
  53     // FIXME: Should probably be moved into some kind of pass manager
  54     body.basic_blocks_mut().raw.shrink_to_fit();
  55 }
  56
  57 impl<'tcx> MirPass<'tcx> for SimplifyCfg {
  58     fn name(&self) -> Cow<'_, str> {
  59         Cow::Borrowed(&self.label)
  60     }
  61
  62     fn run_pass(&self, _tcx: TyCtxt<'tcx>, _src: MirSource<'tcx>, body: &mut Body<'tcx>) {
  63         debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, body);
  64         simplify_cfg(body);
  65     }
  66 }
  67
  68 pub struct CfgSimplifier<'a, 'tcx> {
  69     basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>,
  70     pred_count: IndexVec<BasicBlock, u32>,
  71 }
  72
  73 impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
  74     pub fn new(body: &'a mut Body<'tcx>) -> Self {
  75         let mut pred_count = IndexVec::from_elem(0u32, body.basic_blocks());
  76
  77         // we can't use mir.predecessors() here because that counts
  78         // dead blocks, which we don't want to.
  79         pred_count[START_BLOCK] = 1;
  80
  81         for (_, data) in traversal::preorder(body) {
  82             if let Some(ref term) = data.terminator {
  83                 for &tgt in term.successors() {
  84                     pred_count[tgt] += 1;
  85                 }
  86             }
  87         }
  88
  89         let basic_blocks = body.basic_blocks_mut();
  90
  91         CfgSimplifier { basic_blocks, pred_count }
  92     }
  93
  94     pub fn simplify(mut self) {
  95         self.strip_nops();
  96
  97         let mut start = START_BLOCK;
  98
  99         // Vec of the blocks that should be merged. We store the indices here, instead of the
 100         // statements itself to avoid moving the (relatively) large statements twice.
 101         // We do not push the statements directly into the target block (`bb`) as that is slower
 102         // due to additional reallocations
 103         let mut merged_blocks = Vec::new();
 104         loop {
 105             let mut changed = false;
 106
 107             self.collapse_goto_chain(&mut start, &mut changed);
 108
 109             for bb in self.basic_blocks.indices() {
 110                 if self.pred_count[bb] == 0 {
 111                     continue;
 112                 }
 113
 114                 debug!("simplifying {:?}", bb);
 115
 116                 let mut terminator =
 117                     self.basic_blocks[bb].terminator.take().expect("invalid terminator state");
 118
 119                 for successor in terminator.successors_mut() {
 120                     self.collapse_goto_chain(successor, &mut changed);
 121                 }
 122
 123                 let mut inner_changed = true;
 124                 merged_blocks.clear();
 125                 while inner_changed {
 126                     inner_changed = false;
 127                     inner_changed |= self.simplify_branch(&mut terminator);
 128                     inner_changed |= self.merge_successor(&mut merged_blocks, &mut terminator);
 129                     changed |= inner_changed;
 130                 }
 131
 132                 let statements_to_merge =
 133                     merged_blocks.iter().map(|&i| self.basic_blocks[i].statements.len()).sum();
 134
 135                 if statements_to_merge > 0 {
 136                     let mut statements = std::mem::take(&mut self.basic_blocks[bb].statements);
 137                     statements.reserve(statements_to_merge);
 138                     for &from in &merged_blocks {
 139                         statements.append(&mut self.basic_blocks[from].statements);
 140                     }
 141                     self.basic_blocks[bb].statements = statements;
 142                 }
 143
 144                 self.basic_blocks[bb].terminator = Some(terminator);
 145
 146                 changed |= inner_changed;
 147             }
 148
 149             if !changed {
 150                 break;
 151             }
 152         }
 153
 154         if start != START_BLOCK {
 155             debug_assert!(self.pred_count[START_BLOCK] == 0);
 156             self.basic_blocks.swap(START_BLOCK, start);
 157             self.pred_count.swap(START_BLOCK, start);
 158
 159             // pred_count == 1 if the start block has no predecessor _blocks_.
 160             if self.pred_count[START_BLOCK] > 1 {
 161                 for (bb, data) in self.basic_blocks.iter_enumerated_mut() {
 162                     if self.pred_count[bb] == 0 {
 163                         continue;
 164                     }
 165
 166                     for target in data.terminator_mut().successors_mut() {
 167                         if *target == start {
 168                             *target = START_BLOCK;
 169                         }
 170                     }
 171                 }
 172             }
 173         }
 174     }
 175
 176     /// This function will return `None` if
 177     /// * the block has statements
 178     /// * the block has a terminator other than `goto`
 179     /// * the block has no terminator (meaning some other part of the current optimization stole it)
 180     fn take_terminator_if_simple_goto(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> {
 181         match self.basic_blocks[bb] {
 182             BasicBlockData {
 183                 ref statements,
 184                 terminator:
 185                     ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }),
 186                 ..
 187             } if statements.is_empty() => terminator.take(),
 188             // if `terminator` is None, this means we are in a loop. In that
 189             // case, let all the loop collapse to its entry.
 190             _ => None,
 191         }
 192     }
 193
 194     /// Collapse a goto chain starting from `start`
 195     fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
 196         // Using `SmallVec` here, because in some logs on libcore oli-obk saw many single-element
 197         // goto chains. We should probably benchmark different sizes.
 198         let mut terminators: SmallVec<[_; 1]> = Default::default();
 199         let mut current = *start;
 200         while let Some(terminator) = self.take_terminator_if_simple_goto(current) {
 201             let target = match terminator {
 202                 Terminator { kind: TerminatorKind::Goto { target }, .. } => target,
 203                 _ => unreachable!(),
 204             };
 205             terminators.push((current, terminator));
 206             current = target;
 207         }
 208         let last = current;
 209         *start = last;
 210         while let Some((current, mut terminator)) = terminators.pop() {
 211             let target = match terminator {
 212                 Terminator { kind: TerminatorKind::Goto { ref mut target }, .. } => target,
 213                 _ => unreachable!(),
 214             };
 215             *target = last;
 216             debug!("collapsing goto chain from {:?} to {:?}", current, target);
 217
 218             if self.pred_count[current] == 1 {
 219                 // This is the last reference to current, so the pred-count to
 220                 // to target is moved into the current block.
 221                 self.pred_count[current] = 0;
 222             } else {
 223                 self.pred_count[*target] += 1;
 224                 self.pred_count[current] -= 1;
 225             }
 226             *changed = true;
 227             self.basic_blocks[current].terminator = Some(terminator);
 228         }
 229     }
 230
 231     // merge a block with 1 `goto` predecessor to its parent
 232     fn merge_successor(
 233         &mut self,
 234         merged_blocks: &mut Vec<BasicBlock>,
 235         terminator: &mut Terminator<'tcx>,
 236     ) -> bool {
 237         let target = match terminator.kind {
 238             TerminatorKind::Goto { target } if self.pred_count[target] == 1 => target,
 239             _ => return false,
 240         };
 241
 242         debug!("merging block {:?} into {:?}", target, terminator);
 243         *terminator = match self.basic_blocks[target].terminator.take() {
 244             Some(terminator) => terminator,
 245             None => {
 246                 // unreachable loop - this should not be possible, as we
 247                 // don't strand blocks, but handle it correctly.
 248                 return false;
 249             }
 250         };
 251
 252         merged_blocks.push(target);
 253         self.pred_count[target] = 0;
 254
 255         true
 256     }
 257
 258     // turn a branch with all successors identical to a goto
 259     fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
 260         match terminator.kind {
 261             TerminatorKind::SwitchInt { .. } => {}
 262             _ => return false,
 263         };
 264
 265         let first_succ = {
 266             if let Some(&first_succ) = terminator.successors().next() {
 267                 if terminator.successors().all(|s| *s == first_succ) {
 268                     let count = terminator.successors().count();
 269                     self.pred_count[first_succ] -= (count - 1) as u32;
 270                     first_succ
 271                 } else {
 272                     return false;
 273                 }
 274             } else {
 275                 return false;
 276             }
 277         };
 278
 279         debug!("simplifying branch {:?}", terminator);
 280         terminator.kind = TerminatorKind::Goto { target: first_succ };
 281         true
 282     }
 283
 284     fn strip_nops(&mut self) {
 285         for blk in self.basic_blocks.iter_mut() {
 286             blk.statements
 287                 .retain(|stmt| if let StatementKind::Nop = stmt.kind { false } else { true })
 288         }
 289     }
 290 }
 291
 292 pub fn remove_dead_blocks(body: &mut Body<'_>) {
 293     let mut seen = BitSet::new_empty(body.basic_blocks().len());
 294     for (bb, _) in traversal::preorder(body) {
 295         seen.insert(bb.index());
 296     }
 297
 298     let basic_blocks = body.basic_blocks_mut();
 299
 300     let num_blocks = basic_blocks.len();
 301     let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
 302     let mut used_blocks = 0;
 303     for alive_index in seen.iter() {
 304         replacements[alive_index] = BasicBlock::new(used_blocks);
 305         if alive_index != used_blocks {
 306             // Swap the next alive block data with the current available slot. Since
 307             // alive_index is non-decreasing this is a valid operation.
 308             basic_blocks.raw.swap(alive_index, used_blocks);
 309         }
 310         used_blocks += 1;
 311     }
 312     basic_blocks.raw.truncate(used_blocks);
 313
 314     for block in basic_blocks {
 315         for target in block.terminator_mut().successors_mut() {
 316             *target = replacements[target.index()];
 317         }
 318     }
 319 }
 320
 321 pub struct SimplifyLocals;
 322
 323 impl<'tcx> MirPass<'tcx> for SimplifyLocals {
 324     fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>) {
 325         trace!("running SimplifyLocals on {:?}", source);
 326
 327         // First, we're going to get a count of *actual* uses for every `Local`.
 328         // Take a look at `DeclMarker::visit_local()` to see exactly what is ignored.
 329         let mut used_locals = {
 330             let mut marker = DeclMarker::new(body);
 331             marker.visit_body(&body);
 332
 333             marker.local_counts
 334         };
 335
 336         let arg_count = body.arg_count;
 337
 338         // Next, we're going to remove any `Local` with zero actual uses. When we remove those
 339         // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals`
 340         // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from
 341         // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a
 342         // fixedpoint where there are no more unused locals.
 343         loop {
 344             let mut remove_statements = RemoveStatements::new(&mut used_locals, arg_count, tcx);
 345             remove_statements.visit_body(body);
 346
 347             if !remove_statements.modified {
 348                 break;
 349             }
 350         }
 351
 352         // Finally, we'll actually do the work of shrinking `body.local_decls` and remapping the `Local`s.
 353         let map = make_local_map(&mut body.local_decls, used_locals, arg_count);
 354
 355         // Only bother running the `LocalUpdater` if we actually found locals to remove.
 356         if map.iter().any(Option::is_none) {
 357             // Update references to all vars and tmps now
 358             let mut updater = LocalUpdater { map, tcx };
 359             updater.visit_body(body);
 360
 361             body.local_decls.shrink_to_fit();
 362         }
 363     }
 364 }
 365
 366 /// Construct the mapping while swapping out unused stuff out from the `vec`.
 367 fn make_local_map<V>(
 368     local_decls: &mut IndexVec<Local, V>,
 369     used_locals: IndexVec<Local, usize>,
 370     arg_count: usize,
 371 ) -> IndexVec<Local, Option<Local>> {
 372     let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*local_decls);
 373     let mut used = Local::new(0);
 374     for (alive_index, count) in used_locals.iter_enumerated() {
 375         // The `RETURN_PLACE` and arguments are always live.
 376         if alive_index.as_usize() > arg_count && *count == 0 {
 377             continue;
 378         }
 379
 380         map[alive_index] = Some(used);
 381         if alive_index != used {
 382             local_decls.swap(alive_index, used);
 383         }
 384         used.increment_by(1);
 385     }
 386     local_decls.truncate(used.index());
 387     map
 388 }
 389
 390 struct DeclMarker<'a, 'tcx> {
 391     pub local_counts: IndexVec<Local, usize>,
 392     pub body: &'a Body<'tcx>,
 393 }
 394
 395 impl<'a, 'tcx> DeclMarker<'a, 'tcx> {
 396     pub fn new(body: &'a Body<'tcx>) -> Self {
 397         Self { local_counts: IndexVec::from_elem(0, &body.local_decls), body }
 398     }
 399 }
 400
 401 impl<'a, 'tcx> Visitor<'tcx> for DeclMarker<'a, 'tcx> {
 402     fn visit_local(&mut self, local: &Local, ctx: PlaceContext, location: Location) {
 403         // Ignore storage markers altogether, they get removed along with their otherwise unused
 404         // decls.
 405         // FIXME: Extend this to all non-uses.
 406         if ctx.is_storage_marker() {
 407             return;
 408         }
 409
 410         // Ignore stores of constants because `ConstProp` and `CopyProp` can remove uses of many
 411         // of these locals. However, if the local is still needed, then it will be referenced in
 412         // another place and we'll mark it as being used there.
 413         if ctx == PlaceContext::MutatingUse(MutatingUseContext::Store)
 414             || ctx == PlaceContext::MutatingUse(MutatingUseContext::Projection)
 415         {
 416             let block = &self.body.basic_blocks()[location.block];
 417             if location.statement_index != block.statements.len() {
 418                 let stmt = &block.statements[location.statement_index];
 419
 420                 if let StatementKind::Assign(box (dest, rvalue)) = &stmt.kind {
 421                     if !dest.is_indirect() && dest.local == *local {
 422                         let can_skip = match rvalue {
 423                             Rvalue::Use(_)
 424                             | Rvalue::Discriminant(_)
 425                             | Rvalue::BinaryOp(_, _, _)
 426                             | Rvalue::CheckedBinaryOp(_, _, _)
 427                             | Rvalue::Repeat(_, _)
 428                             | Rvalue::AddressOf(_, _)
 429                             | Rvalue::Len(_)
 430                             | Rvalue::UnaryOp(_, _)
 431                             | Rvalue::Aggregate(_, _) => true,
 432
 433                             _ => false,
 434                         };
 435
 436                         if can_skip {
 437                             trace!("skipping store of {:?} to {:?}", rvalue, dest);
 438                             return;
 439                         }
 440                     }
 441                 }
 442             }
 443         }
 444
 445         self.local_counts[*local] += 1;
 446     }
 447 }
 448
 449 struct StatementDeclMarker<'a, 'tcx> {
 450     used_locals: &'a mut IndexVec<Local, usize>,
 451     statement: &'a Statement<'tcx>,
 452 }
 453
 454 impl<'a, 'tcx> StatementDeclMarker<'a, 'tcx> {
 455     pub fn new(
 456         used_locals: &'a mut IndexVec<Local, usize>,
 457         statement: &'a Statement<'tcx>,
 458     ) -> Self {
 459         Self { used_locals, statement }
 460     }
 461 }
 462
 463 impl<'a, 'tcx> Visitor<'tcx> for StatementDeclMarker<'a, 'tcx> {
 464     fn visit_local(&mut self, local: &Local, context: PlaceContext, _location: Location) {
 465         // Skip the lvalue for assignments
 466         if let StatementKind::Assign(box (p, _)) = self.statement.kind {
 467             if p.local == *local && context.is_place_assignment() {
 468                 return;
 469             }
 470         }
 471
 472         let use_count = &mut self.used_locals[*local];
 473         // If this is the local we're removing...
 474         if *use_count != 0 {
 475             *use_count -= 1;
 476         }
 477     }
 478 }
 479
 480 struct RemoveStatements<'a, 'tcx> {
 481     used_locals: &'a mut IndexVec<Local, usize>,
 482     arg_count: usize,
 483     tcx: TyCtxt<'tcx>,
 484     modified: bool,
 485 }
 486
 487 impl<'a, 'tcx> RemoveStatements<'a, 'tcx> {
 488     fn new(
 489         used_locals: &'a mut IndexVec<Local, usize>,
 490         arg_count: usize,
 491         tcx: TyCtxt<'tcx>,
 492     ) -> Self {
 493         Self { used_locals, arg_count, tcx, modified: false }
 494     }
 495
 496     fn keep_local(&self, l: Local) -> bool {
 497         trace!("keep_local({:?}): count: {:?}", l, self.used_locals[l]);
 498         l.as_usize() <= self.arg_count || self.used_locals[l] != 0
 499     }
 500 }
 501
 502 impl<'a, 'tcx> MutVisitor<'tcx> for RemoveStatements<'a, 'tcx> {
 503     fn tcx(&self) -> TyCtxt<'tcx> {
 504         self.tcx
 505     }
 506
 507     fn visit_basic_block_data(&mut self, block: BasicBlock, data: &mut BasicBlockData<'tcx>) {
 508         // Remove unnecessary StorageLive and StorageDead annotations.
 509         let mut i = 0usize;
 510         data.statements.retain(|stmt| {
 511             let keep = match &stmt.kind {
 512                 StatementKind::StorageLive(l) | StatementKind::StorageDead(l) => {
 513                     self.keep_local(*l)
 514                 }
 515                 StatementKind::Assign(box (place, _)) => self.keep_local(place.local),
 516                 _ => true,
 517             };
 518
 519             if !keep {
 520                 trace!("removing statement {:?}", stmt);
 521                 self.modified = true;
 522
 523                 let mut visitor = StatementDeclMarker::new(self.used_locals, stmt);
 524                 visitor.visit_statement(stmt, Location { block, statement_index: i });
 525             }
 526
 527             i += 1;
 528
 529             keep
 530         });
 531
 532         self.super_basic_block_data(block, data);
 533     }
 534 }
 535
 536 struct LocalUpdater<'tcx> {
 537     map: IndexVec<Local, Option<Local>>,
 538     tcx: TyCtxt<'tcx>,
 539 }
 540
 541 impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> {
 542     fn tcx(&self) -> TyCtxt<'tcx> {
 543         self.tcx
 544     }
 545
 546     fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) {
 547         *l = self.map[*l].unwrap();
 548     }
 549 }