compiler/rustc_mir/src/transform/instcombine.rs

   1 //! Performs various peephole optimizations.
   2
   3 use crate::transform::MirPass;
   4 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
   5 use rustc_hir::Mutability;
   6 use rustc_index::vec::Idx;
   7 use rustc_middle::mir::{
   8     visit::PlaceContext,
   9     visit::{MutVisitor, Visitor},
  10     Statement,
  11 };
  12 use rustc_middle::mir::{
  13     BinOp, Body, BorrowKind, Constant, Local, Location, Operand, Place, PlaceRef, ProjectionElem,
  14     Rvalue,
  15 };
  16 use rustc_middle::ty::{self, TyCtxt};
  17 use std::mem;
  18
  19 pub struct InstCombine;
  20
  21 impl<'tcx> MirPass<'tcx> for InstCombine {
  22     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
  23         // Check for fuel here before gathering the optimization list. If we're out of fuel,
  24         // we don't want to take the time to pass over the MIR only to find optimizations
  25         // we won't run.
  26         if !tcx.consider_optimizing(|| format!("InstCombine {:?} ", body.source.def_id())) {
  27             return;
  28         }
  29
  30         // First, find optimization opportunities. This is done in a pre-pass to keep the MIR
  31         // read-only so that we can do global analyses on the MIR in the process (e.g.
  32         // `Place::ty()`).
  33         let optimizations = {
  34             let mut optimization_finder = OptimizationFinder::new(body, tcx);
  35             optimization_finder.visit_body(body);
  36             optimization_finder.optimizations
  37         };
  38
  39         // Then carry out those optimizations.
  40         MutVisitor::visit_body(&mut InstCombineVisitor { optimizations, tcx }, body);
  41     }
  42 }
  43
  44 pub struct InstCombineVisitor<'tcx> {
  45     optimizations: OptimizationList<'tcx>,
  46     tcx: TyCtxt<'tcx>,
  47 }
  48
  49 impl<'tcx> MutVisitor<'tcx> for InstCombineVisitor<'tcx> {
  50     fn tcx(&self) -> TyCtxt<'tcx> {
  51         self.tcx
  52     }
  53
  54     fn visit_rvalue(&mut self, rvalue: &mut Rvalue<'tcx>, location: Location) {
  55         if self.optimizations.and_stars.remove(&location) {
  56             debug!("replacing `&*`: {:?}", rvalue);
  57             let new_place = match rvalue {
  58                 Rvalue::Ref(_, _, place) => {
  59                     if let &[ref proj_l @ .., proj_r] = place.projection.as_ref() {
  60                         place.projection = self.tcx().intern_place_elems(&[proj_r]);
  61
  62                         Place {
  63                             // Replace with dummy
  64                             local: mem::replace(&mut place.local, Local::new(0)),
  65                             projection: self.tcx().intern_place_elems(proj_l),
  66                         }
  67                     } else {
  68                         unreachable!();
  69                     }
  70                 }
  71                 _ => bug!("Detected `&*` but didn't find `&*`!"),
  72             };
  73             *rvalue = Rvalue::Use(Operand::Copy(new_place))
  74         }
  75
  76         if let Some(constant) = self.optimizations.arrays_lengths.remove(&location) {
  77             debug!("replacing `Len([_; N])`: {:?}", rvalue);
  78             *rvalue = Rvalue::Use(Operand::Constant(box constant));
  79         }
  80
  81         if let Some(operand) = self.optimizations.unneeded_equality_comparison.remove(&location) {
  82             debug!("replacing {:?} with {:?}", rvalue, operand);
  83             *rvalue = Rvalue::Use(operand);
  84         }
  85
  86         if let Some(place) = self.optimizations.unneeded_deref.remove(&location) {
  87             debug!("unneeded_deref: replacing {:?} with {:?}", rvalue, place);
  88             *rvalue = Rvalue::Use(Operand::Copy(place));
  89         }
  90
  91         self.super_rvalue(rvalue, location)
  92     }
  93 }
  94
  95 struct MutatingUseVisitor {
  96     has_mutating_use: bool,
  97     local_to_look_for: Local,
  98 }
  99
 100 impl MutatingUseVisitor {
 101     fn has_mutating_use_in_stmt(local: Local, stmt: &Statement<'tcx>, location: Location) -> bool {
 102         let mut _self = Self { has_mutating_use: false, local_to_look_for: local };
 103         _self.visit_statement(stmt, location);
 104         _self.has_mutating_use
 105     }
 106 }
 107
 108 impl<'tcx> Visitor<'tcx> for MutatingUseVisitor {
 109     fn visit_local(&mut self, local: &Local, context: PlaceContext, _: Location) {
 110         if *local == self.local_to_look_for {
 111             self.has_mutating_use |= context.is_mutating_use();
 112         }
 113     }
 114 }
 115
 116 /// Finds optimization opportunities on the MIR.
 117 struct OptimizationFinder<'b, 'tcx> {
 118     body: &'b Body<'tcx>,
 119     tcx: TyCtxt<'tcx>,
 120     optimizations: OptimizationList<'tcx>,
 121 }
 122
 123 impl OptimizationFinder<'b, 'tcx> {
 124     fn new(body: &'b Body<'tcx>, tcx: TyCtxt<'tcx>) -> OptimizationFinder<'b, 'tcx> {
 125         OptimizationFinder { body, tcx, optimizations: OptimizationList::default() }
 126     }
 127
 128     fn find_deref_of_address(&mut self, rvalue: &Rvalue<'tcx>, location: Location) -> Option<()> {
 129         // FIXME(#78192): This optimization can result in unsoundness.
 130         if !self.tcx.sess.opts.debugging_opts.unsound_mir_opts {
 131             return None;
 132         }
 133
 134         // Look for the sequence
 135         //
 136         // _2 = &_1;
 137         // ...
 138         // _5 = (*_2);
 139         //
 140         // which we can replace the last statement with `_5 = _1;` to avoid the load of `_2`.
 141         if let Rvalue::Use(op) = rvalue {
 142             let local_being_derefed = match op.place()?.as_ref() {
 143                 PlaceRef { local, projection: [ProjectionElem::Deref] } => Some(local),
 144                 _ => None,
 145             }?;
 146
 147             let mut dead_locals_seen = vec![];
 148
 149             let stmt_index = location.statement_index;
 150             // Look behind for statement that assigns the local from a address of operator.
 151             // 6 is chosen as a heuristic determined by seeing the number of times
 152             // the optimization kicked in compiling rust std.
 153             let lower_index = stmt_index.saturating_sub(6);
 154             let statements_to_look_in = self.body.basic_blocks()[location.block].statements
 155                 [lower_index..stmt_index]
 156                 .iter()
 157                 .rev();
 158             for stmt in statements_to_look_in {
 159                 match &stmt.kind {
 160                     // Exhaustive match on statements to detect conditions that warrant we bail out of the optimization.
 161                     rustc_middle::mir::StatementKind::Assign(box (l, r))
 162                         if l.local == local_being_derefed =>
 163                     {
 164                         match r {
 165                             // Looking for immutable reference e.g _local_being_deref = &_1;
 166                             Rvalue::Ref(
 167                                 _,
 168                                 // Only apply the optimization if it is an immutable borrow.
 169                                 BorrowKind::Shared,
 170                                 place_taken_address_of,
 171                             ) => {
 172                                 // Make sure that the place has not been marked dead
 173                                 if dead_locals_seen.contains(&place_taken_address_of.local) {
 174                                     return None;
 175                                 }
 176
 177                                 self.optimizations
 178                                     .unneeded_deref
 179                                     .insert(location, *place_taken_address_of);
 180                                 return Some(());
 181                             }
 182
 183                             // We found an assignment of `local_being_deref` that is not an immutable ref, e.g the following sequence
 184                             // _2 = &_1;
 185                             // _3 = &5
 186                             // _2 = _3;  <-- this means it is no longer valid to replace the last statement with `_5 = _1;`
 187                             // _5 = (*_2);
 188                             _ => return None,
 189                         }
 190                     }
 191
 192                     // Inline asm can do anything, so bail out of the optimization.
 193                     rustc_middle::mir::StatementKind::LlvmInlineAsm(_) => return None,
 194
 195                     // Remember `StorageDead`s, as the local being marked dead could be the
 196                     // place RHS we are looking for, in which case we need to abort to avoid UB
 197                     // using an uninitialized place
 198                     rustc_middle::mir::StatementKind::StorageDead(dead) => {
 199                         dead_locals_seen.push(*dead)
 200                     }
 201
 202                     // Check that `local_being_deref` is not being used in a mutating way which can cause misoptimization.
 203                     rustc_middle::mir::StatementKind::Assign(box (_, _))
 204                     | rustc_middle::mir::StatementKind::Coverage(_)
 205                     | rustc_middle::mir::StatementKind::Nop
 206                     | rustc_middle::mir::StatementKind::FakeRead(_, _)
 207                     | rustc_middle::mir::StatementKind::StorageLive(_)
 208                     | rustc_middle::mir::StatementKind::Retag(_, _)
 209                     | rustc_middle::mir::StatementKind::AscribeUserType(_, _)
 210                     | rustc_middle::mir::StatementKind::SetDiscriminant { .. } => {
 211                         if MutatingUseVisitor::has_mutating_use_in_stmt(
 212                             local_being_derefed,
 213                             stmt,
 214                             location,
 215                         ) {
 216                             return None;
 217                         }
 218                     }
 219                 }
 220             }
 221         }
 222         Some(())
 223     }
 224
 225     fn find_unneeded_equality_comparison(&mut self, rvalue: &Rvalue<'tcx>, location: Location) {
 226         // find Ne(_place, false) or Ne(false, _place)
 227         // or   Eq(_place, true) or Eq(true, _place)
 228         if let Rvalue::BinaryOp(op, l, r) = rvalue {
 229             let const_to_find = if *op == BinOp::Ne {
 230                 false
 231             } else if *op == BinOp::Eq {
 232                 true
 233             } else {
 234                 return;
 235             };
 236             // (const, _place)
 237             if let Some(o) = self.find_operand_in_equality_comparison_pattern(l, r, const_to_find) {
 238                 self.optimizations.unneeded_equality_comparison.insert(location, o.clone());
 239             }
 240             // (_place, const)
 241             else if let Some(o) =
 242                 self.find_operand_in_equality_comparison_pattern(r, l, const_to_find)
 243             {
 244                 self.optimizations.unneeded_equality_comparison.insert(location, o.clone());
 245             }
 246         }
 247     }
 248
 249     fn find_operand_in_equality_comparison_pattern(
 250         &self,
 251         l: &Operand<'tcx>,
 252         r: &'a Operand<'tcx>,
 253         const_to_find: bool,
 254     ) -> Option<&'a Operand<'tcx>> {
 255         let const_ = l.constant()?;
 256         if const_.literal.ty == self.tcx.types.bool
 257             && const_.literal.val.try_to_bool() == Some(const_to_find)
 258         {
 259             if r.place().is_some() {
 260                 return Some(r);
 261             }
 262         }
 263
 264         None
 265     }
 266 }
 267
 268 impl Visitor<'tcx> for OptimizationFinder<'b, 'tcx> {
 269     fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) {
 270         if let Rvalue::Ref(_, _, place) = rvalue {
 271             if let PlaceRef { local, projection: &[ref proj_base @ .., ProjectionElem::Deref] } =
 272                 place.as_ref()
 273             {
 274                 // The dereferenced place must have type `&_`.
 275                 let ty = Place::ty_from(local, proj_base, self.body, self.tcx).ty;
 276                 if let ty::Ref(_, _, Mutability::Not) = ty.kind() {
 277                     self.optimizations.and_stars.insert(location);
 278                 }
 279             }
 280         }
 281
 282         if let Rvalue::Len(ref place) = *rvalue {
 283             let place_ty = place.ty(&self.body.local_decls, self.tcx).ty;
 284             if let ty::Array(_, len) = place_ty.kind() {
 285                 let span = self.body.source_info(location).span;
 286                 let constant = Constant { span, literal: len, user_ty: None };
 287                 self.optimizations.arrays_lengths.insert(location, constant);
 288             }
 289         }
 290
 291         let _ = self.find_deref_of_address(rvalue, location);
 292
 293         self.find_unneeded_equality_comparison(rvalue, location);
 294
 295         self.super_rvalue(rvalue, location)
 296     }
 297 }
 298
 299 #[derive(Default)]
 300 struct OptimizationList<'tcx> {
 301     and_stars: FxHashSet<Location>,
 302     arrays_lengths: FxHashMap<Location, Constant<'tcx>>,
 303     unneeded_equality_comparison: FxHashMap<Location, Operand<'tcx>>,
 304     unneeded_deref: FxHashMap<Location, Place<'tcx>>,
 305 }