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