compiler/rustc_mir/src/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;
  31 use rustc_index::vec::{Idx, IndexVec};
  32 use rustc_middle::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor};
  33 use rustc_middle::mir::*;
  34 use rustc_middle::ty::TyCtxt;
  35 use smallvec::SmallVec;
  36 use std::borrow::Cow;
  37 use std::convert::TryInto;
  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>, body: &mut Body<'tcx>) {
  63         debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, body.source);
  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
 147             if !changed {
 148                 break;
 149             }
 150         }
 151
 152         if start != START_BLOCK {
 153             debug_assert!(self.pred_count[START_BLOCK] == 0);
 154             self.basic_blocks.swap(START_BLOCK, start);
 155             self.pred_count.swap(START_BLOCK, start);
 156
 157             // pred_count == 1 if the start block has no predecessor _blocks_.
 158             if self.pred_count[START_BLOCK] > 1 {
 159                 for (bb, data) in self.basic_blocks.iter_enumerated_mut() {
 160                     if self.pred_count[bb] == 0 {
 161                         continue;
 162                     }
 163
 164                     for target in data.terminator_mut().successors_mut() {
 165                         if *target == start {
 166                             *target = START_BLOCK;
 167                         }
 168                     }
 169                 }
 170             }
 171         }
 172     }
 173
 174     /// This function will return `None` if
 175     /// * the block has statements
 176     /// * the block has a terminator other than `goto`
 177     /// * the block has no terminator (meaning some other part of the current optimization stole it)
 178     fn take_terminator_if_simple_goto(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> {
 179         match self.basic_blocks[bb] {
 180             BasicBlockData {
 181                 ref statements,
 182                 terminator:
 183                     ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }),
 184                 ..
 185             } if statements.is_empty() => terminator.take(),
 186             // if `terminator` is None, this means we are in a loop. In that
 187             // case, let all the loop collapse to its entry.
 188             _ => None,
 189         }
 190     }
 191
 192     /// Collapse a goto chain starting from `start`
 193     fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
 194         // Using `SmallVec` here, because in some logs on libcore oli-obk saw many single-element
 195         // goto chains. We should probably benchmark different sizes.
 196         let mut terminators: SmallVec<[_; 1]> = Default::default();
 197         let mut current = *start;
 198         while let Some(terminator) = self.take_terminator_if_simple_goto(current) {
 199             let target = match terminator {
 200                 Terminator { kind: TerminatorKind::Goto { target }, .. } => target,
 201                 _ => unreachable!(),
 202             };
 203             terminators.push((current, terminator));
 204             current = target;
 205         }
 206         let last = current;
 207         *start = last;
 208         while let Some((current, mut terminator)) = terminators.pop() {
 209             let target = match terminator {
 210                 Terminator { kind: TerminatorKind::Goto { ref mut target }, .. } => target,
 211                 _ => unreachable!(),
 212             };
 213             *changed |= *target != last;
 214             *target = last;
 215             debug!("collapsing goto chain from {:?} to {:?}", current, target);
 216
 217             if self.pred_count[current] == 1 {
 218                 // This is the last reference to current, so the pred-count to
 219                 // to target is moved into the current block.
 220                 self.pred_count[current] = 0;
 221             } else {
 222                 self.pred_count[*target] += 1;
 223                 self.pred_count[current] -= 1;
 224             }
 225             self.basic_blocks[current].terminator = Some(terminator);
 226         }
 227     }
 228
 229     // merge a block with 1 `goto` predecessor to its parent
 230     fn merge_successor(
 231         &mut self,
 232         merged_blocks: &mut Vec<BasicBlock>,
 233         terminator: &mut Terminator<'tcx>,
 234     ) -> bool {
 235         let target = match terminator.kind {
 236             TerminatorKind::Goto { target } if self.pred_count[target] == 1 => target,
 237             _ => return false,
 238         };
 239
 240         debug!("merging block {:?} into {:?}", target, terminator);
 241         *terminator = match self.basic_blocks[target].terminator.take() {
 242             Some(terminator) => terminator,
 243             None => {
 244                 // unreachable loop - this should not be possible, as we
 245                 // don't strand blocks, but handle it correctly.
 246                 return false;
 247             }
 248         };
 249
 250         merged_blocks.push(target);
 251         self.pred_count[target] = 0;
 252
 253         true
 254     }
 255
 256     // turn a branch with all successors identical to a goto
 257     fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
 258         match terminator.kind {
 259             TerminatorKind::SwitchInt { .. } => {}
 260             _ => return false,
 261         };
 262
 263         let first_succ = {
 264             if let Some(&first_succ) = terminator.successors().next() {
 265                 if terminator.successors().all(|s| *s == first_succ) {
 266                     let count = terminator.successors().count();
 267                     self.pred_count[first_succ] -= (count - 1) as u32;
 268                     first_succ
 269                 } else {
 270                     return false;
 271                 }
 272             } else {
 273                 return false;
 274             }
 275         };
 276
 277         debug!("simplifying branch {:?}", terminator);
 278         terminator.kind = TerminatorKind::Goto { target: first_succ };
 279         true
 280     }
 281
 282     fn strip_nops(&mut self) {
 283         for blk in self.basic_blocks.iter_mut() {
 284             blk.statements.retain(|stmt| !matches!(stmt.kind, StatementKind::Nop))
 285         }
 286     }
 287 }
 288
 289 pub fn remove_dead_blocks(body: &mut Body<'_>) {
 290     let reachable = traversal::reachable_as_bitset(body);
 291     let num_blocks = body.basic_blocks().len();
 292     if num_blocks == reachable.count() {
 293         return;
 294     }
 295
 296     let basic_blocks = body.basic_blocks_mut();
 297     let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
 298     let mut used_blocks = 0;
 299     for alive_index in reachable.iter() {
 300         let alive_index = alive_index.index();
 301         replacements[alive_index] = BasicBlock::new(used_blocks);
 302         if alive_index != used_blocks {
 303             // Swap the next alive block data with the current available slot. Since
 304             // alive_index is non-decreasing this is a valid operation.
 305             basic_blocks.raw.swap(alive_index, used_blocks);
 306         }
 307         used_blocks += 1;
 308     }
 309     basic_blocks.raw.truncate(used_blocks);
 310
 311     for block in basic_blocks {
 312         for target in block.terminator_mut().successors_mut() {
 313             *target = replacements[target.index()];
 314         }
 315     }
 316 }
 317
 318 pub struct SimplifyLocals;
 319
 320 impl<'tcx> MirPass<'tcx> for SimplifyLocals {
 321     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
 322         trace!("running SimplifyLocals on {:?}", body.source);
 323         simplify_locals(body, tcx);
 324     }
 325 }
 326
 327 pub fn simplify_locals<'tcx>(body: &mut Body<'tcx>, tcx: TyCtxt<'tcx>) {
 328     // First, we're going to get a count of *actual* uses for every `Local`.
 329     let mut used_locals = UsedLocals::new(body);
 330
 331     // Next, we're going to remove any `Local` with zero actual uses. When we remove those
 332     // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals`
 333     // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from
 334     // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a
 335     // fixedpoint where there are no more unused locals.
 336     remove_unused_definitions(&mut used_locals, body);
 337
 338     // Finally, we'll actually do the work of shrinking `body.local_decls` and remapping the `Local`s.
 339     let map = make_local_map(&mut body.local_decls, &used_locals);
 340
 341     // Only bother running the `LocalUpdater` if we actually found locals to remove.
 342     if map.iter().any(Option::is_none) {
 343         // Update references to all vars and tmps now
 344         let mut updater = LocalUpdater { map, tcx };
 345         updater.visit_body(body);
 346
 347         body.local_decls.shrink_to_fit();
 348     }
 349 }
 350
 351 /// Construct the mapping while swapping out unused stuff out from the `vec`.
 352 fn make_local_map<V>(
 353     local_decls: &mut IndexVec<Local, V>,
 354     used_locals: &UsedLocals,
 355 ) -> IndexVec<Local, Option<Local>> {
 356     let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*local_decls);
 357     let mut used = Local::new(0);
 358
 359     for alive_index in local_decls.indices() {
 360         // `is_used` treats the `RETURN_PLACE` and arguments as used.
 361         if !used_locals.is_used(alive_index) {
 362             continue;
 363         }
 364
 365         map[alive_index] = Some(used);
 366         if alive_index != used {
 367             local_decls.swap(alive_index, used);
 368         }
 369         used.increment_by(1);
 370     }
 371     local_decls.truncate(used.index());
 372     map
 373 }
 374
 375 /// Keeps track of used & unused locals.
 376 struct UsedLocals {
 377     increment: bool,
 378     arg_count: u32,
 379     use_count: IndexVec<Local, u32>,
 380 }
 381
 382 impl UsedLocals {
 383     /// Determines which locals are used & unused in the given body.
 384     fn new(body: &Body<'_>) -> Self {
 385         let mut this = Self {
 386             increment: true,
 387             arg_count: body.arg_count.try_into().unwrap(),
 388             use_count: IndexVec::from_elem(0, &body.local_decls),
 389         };
 390         this.visit_body(body);
 391         this
 392     }
 393
 394     /// Checks if local is used.
 395     ///
 396     /// Return place and arguments are always considered used.
 397     fn is_used(&self, local: Local) -> bool {
 398         trace!("is_used({:?}): use_count: {:?}", local, self.use_count[local]);
 399         local.as_u32() <= self.arg_count || self.use_count[local] != 0
 400     }
 401
 402     /// Updates the use counts to reflect the removal of given statement.
 403     fn statement_removed(&mut self, statement: &Statement<'tcx>) {
 404         self.increment = false;
 405
 406         // The location of the statement is irrelevant.
 407         let location = Location { block: START_BLOCK, statement_index: 0 };
 408         self.visit_statement(statement, location);
 409     }
 410
 411     /// Visits a left-hand side of an assignment.
 412     fn visit_lhs(&mut self, place: &Place<'tcx>, location: Location) {
 413         if place.is_indirect() {
 414             // A use, not a definition.
 415             self.visit_place(place, PlaceContext::MutatingUse(MutatingUseContext::Store), location);
 416         } else {
 417             // A definition. Although, it still might use other locals for indexing.
 418             self.super_projection(
 419                 place.as_ref(),
 420                 PlaceContext::MutatingUse(MutatingUseContext::Projection),
 421                 location,
 422             );
 423         }
 424     }
 425 }
 426
 427 impl Visitor<'_> for UsedLocals {
 428     fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
 429         match statement.kind {
 430             StatementKind::LlvmInlineAsm(..)
 431             | StatementKind::CopyNonOverlapping(..)
 432             | StatementKind::Retag(..)
 433             | StatementKind::Coverage(..)
 434             | StatementKind::FakeRead(..)
 435             | StatementKind::AscribeUserType(..) => {
 436                 self.super_statement(statement, location);
 437             }
 438
 439             StatementKind::Nop => {}
 440
 441             StatementKind::StorageLive(_local) | StatementKind::StorageDead(_local) => {}
 442
 443             StatementKind::Assign(box (ref place, ref rvalue)) => {
 444                 self.visit_lhs(place, location);
 445                 self.visit_rvalue(rvalue, location);
 446             }
 447
 448             StatementKind::SetDiscriminant { ref place, variant_index: _ } => {
 449                 self.visit_lhs(place, location);
 450             }
 451         }
 452     }
 453
 454     fn visit_local(&mut self, local: &Local, _ctx: PlaceContext, _location: Location) {
 455         if self.increment {
 456             self.use_count[*local] += 1;
 457         } else {
 458             assert_ne!(self.use_count[*local], 0);
 459             self.use_count[*local] -= 1;
 460         }
 461     }
 462 }
 463
 464 /// Removes unused definitions. Updates the used locals to reflect the changes made.
 465 fn remove_unused_definitions<'a, 'tcx>(used_locals: &'a mut UsedLocals, body: &mut Body<'tcx>) {
 466     // The use counts are updated as we remove the statements. A local might become unused
 467     // during the retain operation, leading to a temporary inconsistency (storage statements or
 468     // definitions referencing the local might remain). For correctness it is crucial that this
 469     // computation reaches a fixed point.
 470
 471     let mut modified = true;
 472     while modified {
 473         modified = false;
 474
 475         for data in body.basic_blocks_mut() {
 476             // Remove unnecessary StorageLive and StorageDead annotations.
 477             data.statements.retain(|statement| {
 478                 let keep = match &statement.kind {
 479                     StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => {
 480                         used_locals.is_used(*local)
 481                     }
 482                     StatementKind::Assign(box (place, _)) => used_locals.is_used(place.local),
 483
 484                     StatementKind::SetDiscriminant { ref place, .. } => {
 485                         used_locals.is_used(place.local)
 486                     }
 487                     _ => true,
 488                 };
 489
 490                 if !keep {
 491                     trace!("removing statement {:?}", statement);
 492                     modified = true;
 493                     used_locals.statement_removed(statement);
 494                 }
 495
 496                 keep
 497             });
 498         }
 499     }
 500 }
 501
 502 struct LocalUpdater<'tcx> {
 503     map: IndexVec<Local, Option<Local>>,
 504     tcx: TyCtxt<'tcx>,
 505 }
 506
 507 impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> {
 508     fn tcx(&self) -> TyCtxt<'tcx> {
 509         self.tcx
 510     }
 511
 512     fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) {
 513         *l = self.map[*l].unwrap();
 514     }
 515 }