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 crate::MirPass;
  31 use rustc_index::vec::{Idx, IndexVec};
  32 use rustc_middle::mir::coverage::*;
  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 use std::convert::TryInto;
  39
  40 pub struct SimplifyCfg {
  41     label: String,
  42 }
  43
  44 impl SimplifyCfg {
  45     pub fn new(label: &str) -> Self {
  46         SimplifyCfg { label: format!("SimplifyCfg-{}", label) }
  47     }
  48 }
  49
  50 pub fn simplify_cfg<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
  51     CfgSimplifier::new(body).simplify();
  52     remove_dead_blocks(tcx, body);
  53
  54     // FIXME: Should probably be moved into some kind of pass manager
  55     body.basic_blocks_mut().raw.shrink_to_fit();
  56 }
  57
  58 impl<'tcx> MirPass<'tcx> for SimplifyCfg {
  59     fn name(&self) -> Cow<'_, str> {
  60         Cow::Borrowed(&self.label)
  61     }
  62
  63     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
  64         debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, body.source);
  65         simplify_cfg(tcx, body);
  66     }
  67 }
  68
  69 pub struct CfgSimplifier<'a, 'tcx> {
  70     basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>,
  71     pred_count: IndexVec<BasicBlock, u32>,
  72 }
  73
  74 impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
  75     pub fn new(body: &'a mut Body<'tcx>) -> Self {
  76         let mut pred_count = IndexVec::from_elem(0u32, body.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(body) {
  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 = body.basic_blocks_mut();
  91
  92         CfgSimplifier { basic_blocks, pred_count }
  93     }
  94
  95     pub fn simplify(mut self) {
  96         self.strip_nops();
  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             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 =
 114                     self.basic_blocks[bb].terminator.take().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 inner_changed = true;
 121                 merged_blocks.clear();
 122                 while inner_changed {
 123                     inner_changed = false;
 124                     inner_changed |= self.simplify_branch(&mut terminator);
 125                     inner_changed |= self.merge_successor(&mut merged_blocks, &mut terminator);
 126                     changed |= inner_changed;
 127                 }
 128
 129                 let statements_to_merge =
 130                     merged_blocks.iter().map(|&i| self.basic_blocks[i].statements.len()).sum();
 131
 132                 if statements_to_merge > 0 {
 133                     let mut statements = std::mem::take(&mut self.basic_blocks[bb].statements);
 134                     statements.reserve(statements_to_merge);
 135                     for &from in &merged_blocks {
 136                         statements.append(&mut self.basic_blocks[from].statements);
 137                     }
 138                     self.basic_blocks[bb].statements = statements;
 139                 }
 140
 141                 self.basic_blocks[bb].terminator = Some(terminator);
 142             }
 143
 144             if !changed {
 145                 break;
 146             }
 147         }
 148     }
 149
 150     /// This function will return `None` if
 151     /// * the block has statements
 152     /// * the block has a terminator other than `goto`
 153     /// * the block has no terminator (meaning some other part of the current optimization stole it)
 154     fn take_terminator_if_simple_goto(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> {
 155         match self.basic_blocks[bb] {
 156             BasicBlockData {
 157                 ref statements,
 158                 terminator:
 159                     ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }),
 160                 ..
 161             } if statements.is_empty() => terminator.take(),
 162             // if `terminator` is None, this means we are in a loop. In that
 163             // case, let all the loop collapse to its entry.
 164             _ => None,
 165         }
 166     }
 167
 168     /// Collapse a goto chain starting from `start`
 169     fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
 170         // Using `SmallVec` here, because in some logs on libcore oli-obk saw many single-element
 171         // goto chains. We should probably benchmark different sizes.
 172         let mut terminators: SmallVec<[_; 1]> = Default::default();
 173         let mut current = *start;
 174         while let Some(terminator) = self.take_terminator_if_simple_goto(current) {
 175             let Terminator { kind: TerminatorKind::Goto { target }, .. } = terminator else {
 176                 unreachable!();
 177             };
 178             terminators.push((current, terminator));
 179             current = target;
 180         }
 181         let last = current;
 182         *start = last;
 183         while let Some((current, mut terminator)) = terminators.pop() {
 184             let Terminator { kind: TerminatorKind::Goto { ref mut target }, .. } = terminator else {
 185                 unreachable!();
 186             };
 187             *changed |= *target != last;
 188             *target = last;
 189             debug!("collapsing goto chain from {:?} to {:?}", current, target);
 190
 191             if self.pred_count[current] == 1 {
 192                 // This is the last reference to current, so the pred-count to
 193                 // to target is moved into the current block.
 194                 self.pred_count[current] = 0;
 195             } else {
 196                 self.pred_count[*target] += 1;
 197                 self.pred_count[current] -= 1;
 198             }
 199             self.basic_blocks[current].terminator = Some(terminator);
 200         }
 201     }
 202
 203     // merge a block with 1 `goto` predecessor to its parent
 204     fn merge_successor(
 205         &mut self,
 206         merged_blocks: &mut Vec<BasicBlock>,
 207         terminator: &mut Terminator<'tcx>,
 208     ) -> bool {
 209         let target = match terminator.kind {
 210             TerminatorKind::Goto { target } if self.pred_count[target] == 1 => 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
 224         merged_blocks.push(target);
 225         self.pred_count[target] = 0;
 226
 227         true
 228     }
 229
 230     // turn a branch with all successors identical to a goto
 231     fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
 232         match terminator.kind {
 233             TerminatorKind::SwitchInt { .. } => {}
 234             _ => return false,
 235         };
 236
 237         let first_succ = {
 238             if let Some(&first_succ) = terminator.successors().next() {
 239                 if terminator.successors().all(|s| *s == first_succ) {
 240                     let count = terminator.successors().count();
 241                     self.pred_count[first_succ] -= (count - 1) as u32;
 242                     first_succ
 243                 } else {
 244                     return false;
 245                 }
 246             } else {
 247                 return false;
 248             }
 249         };
 250
 251         debug!("simplifying branch {:?}", terminator);
 252         terminator.kind = TerminatorKind::Goto { target: first_succ };
 253         true
 254     }
 255
 256     fn strip_nops(&mut self) {
 257         for blk in self.basic_blocks.iter_mut() {
 258             blk.statements.retain(|stmt| !matches!(stmt.kind, StatementKind::Nop))
 259         }
 260     }
 261 }
 262
 263 pub fn remove_dead_blocks<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
 264     let reachable = traversal::reachable_as_bitset(body);
 265     let num_blocks = body.basic_blocks().len();
 266     if num_blocks == reachable.count() {
 267         return;
 268     }
 269
 270     let basic_blocks = body.basic_blocks_mut();
 271     let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
 272     let mut used_blocks = 0;
 273     for alive_index in reachable.iter() {
 274         let alive_index = alive_index.index();
 275         replacements[alive_index] = BasicBlock::new(used_blocks);
 276         if alive_index != used_blocks {
 277             // Swap the next alive block data with the current available slot. Since
 278             // alive_index is non-decreasing this is a valid operation.
 279             basic_blocks.raw.swap(alive_index, used_blocks);
 280         }
 281         used_blocks += 1;
 282     }
 283
 284     if tcx.sess.instrument_coverage() {
 285         save_unreachable_coverage(basic_blocks, used_blocks);
 286     }
 287
 288     basic_blocks.raw.truncate(used_blocks);
 289
 290     for block in basic_blocks {
 291         for target in block.terminator_mut().successors_mut() {
 292             *target = replacements[target.index()];
 293         }
 294     }
 295 }
 296
 297 /// Some MIR transforms can determine at compile time that a sequences of
 298 /// statements will never be executed, so they can be dropped from the MIR.
 299 /// For example, an `if` or `else` block that is guaranteed to never be executed
 300 /// because its condition can be evaluated at compile time, such as by const
 301 /// evaluation: `if false { ... }`.
 302 ///
 303 /// Those statements are bypassed by redirecting paths in the CFG around the
 304 /// `dead blocks`; but with `-C instrument-coverage`, the dead blocks usually
 305 /// include `Coverage` statements representing the Rust source code regions to
 306 /// be counted at runtime. Without these `Coverage` statements, the regions are
 307 /// lost, and the Rust source code will show no coverage information.
 308 ///
 309 /// What we want to show in a coverage report is the dead code with coverage
 310 /// counts of `0`. To do this, we need to save the code regions, by injecting
 311 /// `Unreachable` coverage statements. These are non-executable statements whose
 312 /// code regions are still recorded in the coverage map, representing regions
 313 /// with `0` executions.
 314 fn save_unreachable_coverage(
 315     basic_blocks: &mut IndexVec<BasicBlock, BasicBlockData<'_>>,
 316     first_dead_block: usize,
 317 ) {
 318     let has_live_counters = basic_blocks.raw[0..first_dead_block].iter().any(|live_block| {
 319         live_block.statements.iter().any(|statement| {
 320             if let StatementKind::Coverage(coverage) = &statement.kind {
 321                 matches!(coverage.kind, CoverageKind::Counter { .. })
 322             } else {
 323                 false
 324             }
 325         })
 326     });
 327     if !has_live_counters {
 328         // If there are no live `Counter` `Coverage` statements anymore, don't
 329         // move dead coverage to the `START_BLOCK`. Just allow the dead
 330         // `Coverage` statements to be dropped with the dead blocks.
 331         //
 332         // The `generator::StateTransform` MIR pass can create atypical
 333         // conditions, where all live `Counter`s are dropped from the MIR.
 334         //
 335         // At least one Counter per function is required by LLVM (and necessary,
 336         // to add the `function_hash` to the counter's call to the LLVM
 337         // intrinsic `instrprof.increment()`).
 338         return;
 339     }
 340
 341     // Retain coverage info for dead blocks, so coverage reports will still
 342     // report `0` executions for the uncovered code regions.
 343     let mut dropped_coverage = Vec::new();
 344     for dead_block in basic_blocks.raw[first_dead_block..].iter() {
 345         for statement in dead_block.statements.iter() {
 346             if let StatementKind::Coverage(coverage) = &statement.kind {
 347                 if let Some(code_region) = &coverage.code_region {
 348                     dropped_coverage.push((statement.source_info, code_region.clone()));
 349                 }
 350             }
 351         }
 352     }
 353
 354     let start_block = &mut basic_blocks[START_BLOCK];
 355     for (source_info, code_region) in dropped_coverage {
 356         start_block.statements.push(Statement {
 357             source_info,
 358             kind: StatementKind::Coverage(Box::new(Coverage {
 359                 kind: CoverageKind::Unreachable,
 360                 code_region: Some(code_region),
 361             })),
 362         })
 363     }
 364 }
 365
 366 pub struct SimplifyLocals;
 367
 368 impl<'tcx> MirPass<'tcx> for SimplifyLocals {
 369     fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
 370         sess.mir_opt_level() > 0
 371     }
 372
 373     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
 374         trace!("running SimplifyLocals on {:?}", body.source);
 375         simplify_locals(body, tcx);
 376     }
 377 }
 378
 379 pub fn simplify_locals<'tcx>(body: &mut Body<'tcx>, tcx: TyCtxt<'tcx>) {
 380     // First, we're going to get a count of *actual* uses for every `Local`.
 381     let mut used_locals = UsedLocals::new(body);
 382
 383     // Next, we're going to remove any `Local` with zero actual uses. When we remove those
 384     // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals`
 385     // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from
 386     // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a
 387     // fixedpoint where there are no more unused locals.
 388     remove_unused_definitions(&mut used_locals, body);
 389
 390     // Finally, we'll actually do the work of shrinking `body.local_decls` and remapping the `Local`s.
 391     let map = make_local_map(&mut body.local_decls, &used_locals);
 392
 393     // Only bother running the `LocalUpdater` if we actually found locals to remove.
 394     if map.iter().any(Option::is_none) {
 395         // Update references to all vars and tmps now
 396         let mut updater = LocalUpdater { map, tcx };
 397         updater.visit_body(body);
 398
 399         body.local_decls.shrink_to_fit();
 400     }
 401 }
 402
 403 /// Construct the mapping while swapping out unused stuff out from the `vec`.
 404 fn make_local_map<V>(
 405     local_decls: &mut IndexVec<Local, V>,
 406     used_locals: &UsedLocals,
 407 ) -> IndexVec<Local, Option<Local>> {
 408     let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*local_decls);
 409     let mut used = Local::new(0);
 410
 411     for alive_index in local_decls.indices() {
 412         // `is_used` treats the `RETURN_PLACE` and arguments as used.
 413         if !used_locals.is_used(alive_index) {
 414             continue;
 415         }
 416
 417         map[alive_index] = Some(used);
 418         if alive_index != used {
 419             local_decls.swap(alive_index, used);
 420         }
 421         used.increment_by(1);
 422     }
 423     local_decls.truncate(used.index());
 424     map
 425 }
 426
 427 /// Keeps track of used & unused locals.
 428 struct UsedLocals {
 429     increment: bool,
 430     arg_count: u32,
 431     use_count: IndexVec<Local, u32>,
 432 }
 433
 434 impl UsedLocals {
 435     /// Determines which locals are used & unused in the given body.
 436     fn new(body: &Body<'_>) -> Self {
 437         let mut this = Self {
 438             increment: true,
 439             arg_count: body.arg_count.try_into().unwrap(),
 440             use_count: IndexVec::from_elem(0, &body.local_decls),
 441         };
 442         this.visit_body(body);
 443         this
 444     }
 445
 446     /// Checks if local is used.
 447     ///
 448     /// Return place and arguments are always considered used.
 449     fn is_used(&self, local: Local) -> bool {
 450         trace!("is_used({:?}): use_count: {:?}", local, self.use_count[local]);
 451         local.as_u32() <= self.arg_count || self.use_count[local] != 0
 452     }
 453
 454     /// Updates the use counts to reflect the removal of given statement.
 455     fn statement_removed(&mut self, statement: &Statement<'_>) {
 456         self.increment = false;
 457
 458         // The location of the statement is irrelevant.
 459         let location = Location { block: START_BLOCK, statement_index: 0 };
 460         self.visit_statement(statement, location);
 461     }
 462
 463     /// Visits a left-hand side of an assignment.
 464     fn visit_lhs(&mut self, place: &Place<'_>, location: Location) {
 465         if place.is_indirect() {
 466             // A use, not a definition.
 467             self.visit_place(place, PlaceContext::MutatingUse(MutatingUseContext::Store), location);
 468         } else {
 469             // A definition. The base local itself is not visited, so this occurrence is not counted
 470             // toward its use count. There might be other locals still, used in an indexing
 471             // projection.
 472             self.super_projection(
 473                 place.as_ref(),
 474                 PlaceContext::MutatingUse(MutatingUseContext::Projection),
 475                 location,
 476             );
 477         }
 478     }
 479 }
 480
 481 impl<'tcx> Visitor<'tcx> for UsedLocals {
 482     fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
 483         match statement.kind {
 484             StatementKind::CopyNonOverlapping(..)
 485             | StatementKind::Retag(..)
 486             | StatementKind::Coverage(..)
 487             | StatementKind::FakeRead(..)
 488             | StatementKind::AscribeUserType(..) => {
 489                 self.super_statement(statement, location);
 490             }
 491
 492             StatementKind::Nop => {}
 493
 494             StatementKind::StorageLive(_local) | StatementKind::StorageDead(_local) => {}
 495
 496             StatementKind::Assign(box (ref place, ref rvalue)) => {
 497                 self.visit_lhs(place, location);
 498                 self.visit_rvalue(rvalue, location);
 499             }
 500
 501             StatementKind::SetDiscriminant { ref place, variant_index: _ }
 502             | StatementKind::Deinit(ref place) => {
 503                 self.visit_lhs(place, location);
 504             }
 505         }
 506     }
 507
 508     fn visit_local(&mut self, local: &Local, _ctx: PlaceContext, _location: Location) {
 509         if self.increment {
 510             self.use_count[*local] += 1;
 511         } else {
 512             assert_ne!(self.use_count[*local], 0);
 513             self.use_count[*local] -= 1;
 514         }
 515     }
 516 }
 517
 518 /// Removes unused definitions. Updates the used locals to reflect the changes made.
 519 fn remove_unused_definitions(used_locals: &mut UsedLocals, body: &mut Body<'_>) {
 520     // The use counts are updated as we remove the statements. A local might become unused
 521     // during the retain operation, leading to a temporary inconsistency (storage statements or
 522     // definitions referencing the local might remain). For correctness it is crucial that this
 523     // computation reaches a fixed point.
 524
 525     let mut modified = true;
 526     while modified {
 527         modified = false;
 528
 529         for data in body.basic_blocks_mut() {
 530             // Remove unnecessary StorageLive and StorageDead annotations.
 531             data.statements.retain(|statement| {
 532                 let keep = match &statement.kind {
 533                     StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => {
 534                         used_locals.is_used(*local)
 535                     }
 536                     StatementKind::Assign(box (place, _)) => used_locals.is_used(place.local),
 537
 538                     StatementKind::SetDiscriminant { ref place, .. }
 539                     | StatementKind::Deinit(ref place) => used_locals.is_used(place.local),
 540                     _ => true,
 541                 };
 542
 543                 if !keep {
 544                     trace!("removing statement {:?}", statement);
 545                     modified = true;
 546                     used_locals.statement_removed(statement);
 547                 }
 548
 549                 keep
 550             });
 551         }
 552     }
 553 }
 554
 555 struct LocalUpdater<'tcx> {
 556     map: IndexVec<Local, Option<Local>>,
 557     tcx: TyCtxt<'tcx>,
 558 }
 559
 560 impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> {
 561     fn tcx(&self) -> TyCtxt<'tcx> {
 562         self.tcx
 563     }
 564
 565     fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) {
 566         *l = self.map[*l].unwrap();
 567     }
 568 }