compiler/rustc_mir_transform/src/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::{Idx, IndexSlice, IndexVec};
  31 use rustc_middle::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor};
  32 use rustc_middle::mir::*;
  33 use rustc_middle::ty::TyCtxt;
  34 use smallvec::SmallVec;
  35
  36 pub enum SimplifyCfg {
  37     Initial,
  38     PromoteConsts,
  39     RemoveFalseEdges,
  40     EarlyOpt,
  41     ElaborateDrops,
  42     Final,
  43     MakeShim,
  44     AfterUninhabitedEnumBranching,
  45 }
  46
  47 impl SimplifyCfg {
  48     pub fn name(&self) -> &'static str {
  49         match self {
  50             SimplifyCfg::Initial => "SimplifyCfg-initial",
  51             SimplifyCfg::PromoteConsts => "SimplifyCfg-promote-consts",
  52             SimplifyCfg::RemoveFalseEdges => "SimplifyCfg-remove-false-edges",
  53             SimplifyCfg::EarlyOpt => "SimplifyCfg-early-opt",
  54             SimplifyCfg::ElaborateDrops => "SimplifyCfg-elaborate-drops",
  55             SimplifyCfg::Final => "SimplifyCfg-final",
  56             SimplifyCfg::MakeShim => "SimplifyCfg-make_shim",
  57             SimplifyCfg::AfterUninhabitedEnumBranching => {
  58                 "SimplifyCfg-after-uninhabited-enum-branching"
  59             }
  60         }
  61     }
  62 }
  63
  64 pub(crate) fn simplify_cfg(body: &mut Body<'_>) {
  65     CfgSimplifier::new(body).simplify();
  66     remove_dead_blocks(body);
  67
  68     // FIXME: Should probably be moved into some kind of pass manager
  69     body.basic_blocks_mut().raw.shrink_to_fit();
  70 }
  71
  72 impl<'tcx> MirPass<'tcx> for SimplifyCfg {
  73     fn name(&self) -> &'static str {
  74         self.name()
  75     }
  76
  77     fn run_pass(&self, _: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
  78         debug!("SimplifyCfg({:?}) - simplifying {:?}", self.name(), body.source);
  79         simplify_cfg(body);
  80     }
  81 }
  82
  83 pub struct CfgSimplifier<'a, 'tcx> {
  84     basic_blocks: &'a mut IndexSlice<BasicBlock, BasicBlockData<'tcx>>,
  85     pred_count: IndexVec<BasicBlock, u32>,
  86 }
  87
  88 impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
  89     pub fn new(body: &'a mut Body<'tcx>) -> Self {
  90         let mut pred_count = IndexVec::from_elem(0u32, &body.basic_blocks);
  91
  92         // we can't use mir.predecessors() here because that counts
  93         // dead blocks, which we don't want to.
  94         pred_count[START_BLOCK] = 1;
  95
  96         for (_, data) in traversal::preorder(body) {
  97             if let Some(ref term) = data.terminator {
  98                 for tgt in term.successors() {
  99                     pred_count[tgt] += 1;
 100                 }
 101             }
 102         }
 103
 104         let basic_blocks = body.basic_blocks_mut();
 105
 106         CfgSimplifier { basic_blocks, pred_count }
 107     }
 108
 109     pub fn simplify(mut self) {
 110         self.strip_nops();
 111
 112         // Vec of the blocks that should be merged. We store the indices here, instead of the
 113         // statements itself to avoid moving the (relatively) large statements twice.
 114         // We do not push the statements directly into the target block (`bb`) as that is slower
 115         // due to additional reallocations
 116         let mut merged_blocks = Vec::new();
 117         loop {
 118             let mut changed = false;
 119
 120             for bb in self.basic_blocks.indices() {
 121                 if self.pred_count[bb] == 0 {
 122                     continue;
 123                 }
 124
 125                 debug!("simplifying {:?}", bb);
 126
 127                 let mut terminator =
 128                     self.basic_blocks[bb].terminator.take().expect("invalid terminator state");
 129
 130                 for successor in terminator.successors_mut() {
 131                     self.collapse_goto_chain(successor, &mut changed);
 132                 }
 133
 134                 let mut inner_changed = true;
 135                 merged_blocks.clear();
 136                 while inner_changed {
 137                     inner_changed = false;
 138                     inner_changed |= self.simplify_branch(&mut terminator);
 139                     inner_changed |= self.merge_successor(&mut merged_blocks, &mut terminator);
 140                     changed |= inner_changed;
 141                 }
 142
 143                 let statements_to_merge =
 144                     merged_blocks.iter().map(|&i| self.basic_blocks[i].statements.len()).sum();
 145
 146                 if statements_to_merge > 0 {
 147                     let mut statements = std::mem::take(&mut self.basic_blocks[bb].statements);
 148                     statements.reserve(statements_to_merge);
 149                     for &from in &merged_blocks {
 150                         statements.append(&mut self.basic_blocks[from].statements);
 151                     }
 152                     self.basic_blocks[bb].statements = statements;
 153                 }
 154
 155                 self.basic_blocks[bb].terminator = Some(terminator);
 156             }
 157
 158             if !changed {
 159                 break;
 160             }
 161         }
 162     }
 163
 164     /// This function will return `None` if
 165     /// * the block has statements
 166     /// * the block has a terminator other than `goto`
 167     /// * the block has no terminator (meaning some other part of the current optimization stole it)
 168     fn take_terminator_if_simple_goto(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> {
 169         match self.basic_blocks[bb] {
 170             BasicBlockData {
 171                 ref statements,
 172                 terminator:
 173                     ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }),
 174                 ..
 175             } if statements.is_empty() => terminator.take(),
 176             // if `terminator` is None, this means we are in a loop. In that
 177             // case, let all the loop collapse to its entry.
 178             _ => None,
 179         }
 180     }
 181
 182     /// Collapse a goto chain starting from `start`
 183     fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
 184         // Using `SmallVec` here, because in some logs on libcore oli-obk saw many single-element
 185         // goto chains. We should probably benchmark different sizes.
 186         let mut terminators: SmallVec<[_; 1]> = Default::default();
 187         let mut current = *start;
 188         while let Some(terminator) = self.take_terminator_if_simple_goto(current) {
 189             let Terminator { kind: TerminatorKind::Goto { target }, .. } = terminator else {
 190                 unreachable!();
 191             };
 192             terminators.push((current, terminator));
 193             current = target;
 194         }
 195         let last = current;
 196         *start = last;
 197         while let Some((current, mut terminator)) = terminators.pop() {
 198             let Terminator { kind: TerminatorKind::Goto { ref mut target }, .. } = terminator
 199             else {
 200                 unreachable!();
 201             };
 202             *changed |= *target != last;
 203             *target = last;
 204             debug!("collapsing goto chain from {:?} to {:?}", current, target);
 205
 206             if self.pred_count[current] == 1 {
 207                 // This is the last reference to current, so the pred-count to
 208                 // to target is moved into the current block.
 209                 self.pred_count[current] = 0;
 210             } else {
 211                 self.pred_count[*target] += 1;
 212                 self.pred_count[current] -= 1;
 213             }
 214             self.basic_blocks[current].terminator = Some(terminator);
 215         }
 216     }
 217
 218     // merge a block with 1 `goto` predecessor to its parent
 219     fn merge_successor(
 220         &mut self,
 221         merged_blocks: &mut Vec<BasicBlock>,
 222         terminator: &mut Terminator<'tcx>,
 223     ) -> bool {
 224         let target = match terminator.kind {
 225             TerminatorKind::Goto { target } if self.pred_count[target] == 1 => target,
 226             _ => return false,
 227         };
 228
 229         debug!("merging block {:?} into {:?}", target, terminator);
 230         *terminator = match self.basic_blocks[target].terminator.take() {
 231             Some(terminator) => terminator,
 232             None => {
 233                 // unreachable loop - this should not be possible, as we
 234                 // don't strand blocks, but handle it correctly.
 235                 return false;
 236             }
 237         };
 238
 239         merged_blocks.push(target);
 240         self.pred_count[target] = 0;
 241
 242         true
 243     }
 244
 245     // turn a branch with all successors identical to a goto
 246     fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
 247         match terminator.kind {
 248             TerminatorKind::SwitchInt { .. } => {}
 249             _ => return false,
 250         };
 251
 252         let first_succ = {
 253             if let Some(first_succ) = terminator.successors().next() {
 254                 if terminator.successors().all(|s| s == first_succ) {
 255                     let count = terminator.successors().count();
 256                     self.pred_count[first_succ] -= (count - 1) as u32;
 257                     first_succ
 258                 } else {
 259                     return false;
 260                 }
 261             } else {
 262                 return false;
 263             }
 264         };
 265
 266         debug!("simplifying branch {:?}", terminator);
 267         terminator.kind = TerminatorKind::Goto { target: first_succ };
 268         true
 269     }
 270
 271     fn strip_nops(&mut self) {
 272         for blk in self.basic_blocks.iter_mut() {
 273             blk.statements.retain(|stmt| !matches!(stmt.kind, StatementKind::Nop))
 274         }
 275     }
 276 }
 277
 278 pub fn simplify_duplicate_switch_targets(terminator: &mut Terminator<'_>) {
 279     if let TerminatorKind::SwitchInt { targets, .. } = &mut terminator.kind {
 280         let otherwise = targets.otherwise();
 281         if targets.iter().any(|t| t.1 == otherwise) {
 282             *targets = SwitchTargets::new(
 283                 targets.iter().filter(|t| t.1 != otherwise),
 284                 targets.otherwise(),
 285             );
 286         }
 287     }
 288 }
 289
 290 pub(crate) fn remove_dead_blocks(body: &mut Body<'_>) {
 291     let should_deduplicate_unreachable = |bbdata: &BasicBlockData<'_>| {
 292         // CfgSimplifier::simplify leaves behind some unreachable basic blocks without a
 293         // terminator. Those blocks will be deleted by remove_dead_blocks, but we run just
 294         // before then so we need to handle missing terminators.
 295         // We also need to prevent confusing cleanup and non-cleanup blocks. In practice we
 296         // don't emit empty unreachable cleanup blocks, so this simple check suffices.
 297         bbdata.terminator.is_some() && bbdata.is_empty_unreachable() && !bbdata.is_cleanup
 298     };
 299
 300     let reachable = traversal::reachable_as_bitset(body);
 301     let empty_unreachable_blocks = body
 302         .basic_blocks
 303         .iter_enumerated()
 304         .filter(|(bb, bbdata)| should_deduplicate_unreachable(bbdata) && reachable.contains(*bb))
 305         .count();
 306
 307     let num_blocks = body.basic_blocks.len();
 308     if num_blocks == reachable.count() && empty_unreachable_blocks <= 1 {
 309         return;
 310     }
 311
 312     let basic_blocks = body.basic_blocks.as_mut();
 313
 314     let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
 315     let mut orig_index = 0;
 316     let mut used_index = 0;
 317     let mut kept_unreachable = None;
 318     basic_blocks.raw.retain(|bbdata| {
 319         let orig_bb = BasicBlock::new(orig_index);
 320         if !reachable.contains(orig_bb) {
 321             orig_index += 1;
 322             return false;
 323         }
 324
 325         let used_bb = BasicBlock::new(used_index);
 326         if should_deduplicate_unreachable(bbdata) {
 327             let kept_unreachable = *kept_unreachable.get_or_insert(used_bb);
 328             if kept_unreachable != used_bb {
 329                 replacements[orig_index] = kept_unreachable;
 330                 orig_index += 1;
 331                 return false;
 332             }
 333         }
 334
 335         replacements[orig_index] = used_bb;
 336         used_index += 1;
 337         orig_index += 1;
 338         true
 339     });
 340
 341     for block in basic_blocks {
 342         for target in block.terminator_mut().successors_mut() {
 343             *target = replacements[target.index()];
 344         }
 345     }
 346 }
 347
 348 pub enum SimplifyLocals {
 349     BeforeConstProp,
 350     AfterGVN,
 351     Final,
 352 }
 353
 354 impl<'tcx> MirPass<'tcx> for SimplifyLocals {
 355     fn name(&self) -> &'static str {
 356         match &self {
 357             SimplifyLocals::BeforeConstProp => "SimplifyLocals-before-const-prop",
 358             SimplifyLocals::AfterGVN => "SimplifyLocals-after-value-numbering",
 359             SimplifyLocals::Final => "SimplifyLocals-final",
 360         }
 361     }
 362
 363     fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
 364         sess.mir_opt_level() > 0
 365     }
 366
 367     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
 368         trace!("running SimplifyLocals on {:?}", body.source);
 369         simplify_locals(body, tcx);
 370     }
 371 }
 372
 373 pub fn remove_unused_definitions<'tcx>(body: &mut Body<'tcx>) {
 374     // First, we're going to get a count of *actual* uses for every `Local`.
 375     let mut used_locals = UsedLocals::new(body);
 376
 377     // Next, we're going to remove any `Local` with zero actual uses. When we remove those
 378     // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals`
 379     // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from
 380     // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a
 381     // fixedpoint where there are no more unused locals.
 382     remove_unused_definitions_helper(&mut used_locals, body);
 383 }
 384
 385 pub fn simplify_locals<'tcx>(body: &mut Body<'tcx>, tcx: TyCtxt<'tcx>) {
 386     // First, we're going to get a count of *actual* uses for every `Local`.
 387     let mut used_locals = UsedLocals::new(body);
 388
 389     // Next, we're going to remove any `Local` with zero actual uses. When we remove those
 390     // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals`
 391     // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from
 392     // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a
 393     // fixedpoint where there are no more unused locals.
 394     remove_unused_definitions_helper(&mut used_locals, body);
 395
 396     // Finally, we'll actually do the work of shrinking `body.local_decls` and remapping the `Local`s.
 397     let map = make_local_map(&mut body.local_decls, &used_locals);
 398
 399     // Only bother running the `LocalUpdater` if we actually found locals to remove.
 400     if map.iter().any(Option::is_none) {
 401         // Update references to all vars and tmps now
 402         let mut updater = LocalUpdater { map, tcx };
 403         updater.visit_body_preserves_cfg(body);
 404
 405         body.local_decls.shrink_to_fit();
 406     }
 407 }
 408
 409 /// Construct the mapping while swapping out unused stuff out from the `vec`.
 410 fn make_local_map<V>(
 411     local_decls: &mut IndexVec<Local, V>,
 412     used_locals: &UsedLocals,
 413 ) -> IndexVec<Local, Option<Local>> {
 414     let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, local_decls);
 415     let mut used = Local::new(0);
 416
 417     for alive_index in local_decls.indices() {
 418         // `is_used` treats the `RETURN_PLACE` and arguments as used.
 419         if !used_locals.is_used(alive_index) {
 420             continue;
 421         }
 422
 423         map[alive_index] = Some(used);
 424         if alive_index != used {
 425             local_decls.swap(alive_index, used);
 426         }
 427         used.increment_by(1);
 428     }
 429     local_decls.truncate(used.index());
 430     map
 431 }
 432
 433 /// Keeps track of used & unused locals.
 434 struct UsedLocals {
 435     increment: bool,
 436     arg_count: u32,
 437     use_count: IndexVec<Local, u32>,
 438 }
 439
 440 impl UsedLocals {
 441     /// Determines which locals are used & unused in the given body.
 442     fn new(body: &Body<'_>) -> Self {
 443         let mut this = Self {
 444             increment: true,
 445             arg_count: body.arg_count.try_into().unwrap(),
 446             use_count: IndexVec::from_elem(0, &body.local_decls),
 447         };
 448         this.visit_body(body);
 449         this
 450     }
 451
 452     /// Checks if local is used.
 453     ///
 454     /// Return place and arguments are always considered used.
 455     fn is_used(&self, local: Local) -> bool {
 456         trace!("is_used({:?}): use_count: {:?}", local, self.use_count[local]);
 457         local.as_u32() <= self.arg_count || self.use_count[local] != 0
 458     }
 459
 460     /// Updates the use counts to reflect the removal of given statement.
 461     fn statement_removed(&mut self, statement: &Statement<'_>) {
 462         self.increment = false;
 463
 464         // The location of the statement is irrelevant.
 465         let location = Location::START;
 466         self.visit_statement(statement, location);
 467     }
 468
 469     /// Visits a left-hand side of an assignment.
 470     fn visit_lhs(&mut self, place: &Place<'_>, location: Location) {
 471         if place.is_indirect() {
 472             // A use, not a definition.
 473             self.visit_place(place, PlaceContext::MutatingUse(MutatingUseContext::Store), location);
 474         } else {
 475             // A definition. The base local itself is not visited, so this occurrence is not counted
 476             // toward its use count. There might be other locals still, used in an indexing
 477             // projection.
 478             self.super_projection(
 479                 place.as_ref(),
 480                 PlaceContext::MutatingUse(MutatingUseContext::Projection),
 481                 location,
 482             );
 483         }
 484     }
 485 }
 486
 487 impl<'tcx> Visitor<'tcx> for UsedLocals {
 488     fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
 489         match statement.kind {
 490             StatementKind::Intrinsic(..)
 491             | StatementKind::Retag(..)
 492             | StatementKind::Coverage(..)
 493             | StatementKind::FakeRead(..)
 494             | StatementKind::PlaceMention(..)
 495             | StatementKind::AscribeUserType(..) => {
 496                 self.super_statement(statement, location);
 497             }
 498
 499             StatementKind::ConstEvalCounter | StatementKind::Nop => {}
 500
 501             StatementKind::StorageLive(_local) | StatementKind::StorageDead(_local) => {}
 502
 503             StatementKind::Assign(box (ref place, ref rvalue)) => {
 504                 if rvalue.is_safe_to_remove() {
 505                     self.visit_lhs(place, location);
 506                     self.visit_rvalue(rvalue, location);
 507                 } else {
 508                     self.super_statement(statement, location);
 509                 }
 510             }
 511
 512             StatementKind::SetDiscriminant { ref place, variant_index: _ }
 513             | StatementKind::Deinit(ref place) => {
 514                 self.visit_lhs(place, location);
 515             }
 516         }
 517     }
 518
 519     fn visit_local(&mut self, local: Local, _ctx: PlaceContext, _location: Location) {
 520         if self.increment {
 521             self.use_count[local] += 1;
 522         } else {
 523             assert_ne!(self.use_count[local], 0);
 524             self.use_count[local] -= 1;
 525         }
 526     }
 527 }
 528
 529 /// Removes unused definitions. Updates the used locals to reflect the changes made.
 530 fn remove_unused_definitions_helper(used_locals: &mut UsedLocals, body: &mut Body<'_>) {
 531     // The use counts are updated as we remove the statements. A local might become unused
 532     // during the retain operation, leading to a temporary inconsistency (storage statements or
 533     // definitions referencing the local might remain). For correctness it is crucial that this
 534     // computation reaches a fixed point.
 535
 536     let mut modified = true;
 537     while modified {
 538         modified = false;
 539
 540         for data in body.basic_blocks.as_mut_preserves_cfg() {
 541             // Remove unnecessary StorageLive and StorageDead annotations.
 542             data.statements.retain(|statement| {
 543                 let keep = match &statement.kind {
 544                     StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => {
 545                         used_locals.is_used(*local)
 546                     }
 547                     StatementKind::Assign(box (place, _)) => used_locals.is_used(place.local),
 548
 549                     StatementKind::SetDiscriminant { ref place, .. }
 550                     | StatementKind::Deinit(ref place) => used_locals.is_used(place.local),
 551                     StatementKind::Nop => false,
 552                     _ => true,
 553                 };
 554
 555                 if !keep {
 556                     trace!("removing statement {:?}", statement);
 557                     modified = true;
 558                     used_locals.statement_removed(statement);
 559                 }
 560
 561                 keep
 562             });
 563         }
 564     }
 565 }
 566
 567 struct LocalUpdater<'tcx> {
 568     map: IndexVec<Local, Option<Local>>,
 569     tcx: TyCtxt<'tcx>,
 570 }
 571
 572 impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> {
 573     fn tcx(&self) -> TyCtxt<'tcx> {
 574         self.tcx
 575     }
 576
 577     fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) {
 578         *l = self.map[*l].unwrap();
 579     }
 580 }