| //! Performs various peephole optimizations. |
| |
| use crate::transform::{MirPass, MirSource}; |
| use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
| use rustc_hir::Mutability; |
| use rustc_index::vec::Idx; |
| use rustc_middle::mir::{ |
| visit::PlaceContext, |
| visit::{MutVisitor, Visitor}, |
| Statement, |
| }; |
| use rustc_middle::mir::{ |
| BinOp, Body, BorrowKind, Constant, Local, Location, Operand, Place, PlaceRef, ProjectionElem, |
| Rvalue, |
| }; |
| use rustc_middle::ty::{self, TyCtxt}; |
| use std::mem; |
| |
| pub struct InstCombine; |
| |
| impl<'tcx> MirPass<'tcx> for InstCombine { |
| fn run_pass(&self, tcx: TyCtxt<'tcx>, _: MirSource<'tcx>, body: &mut Body<'tcx>) { |
| // First, find optimization opportunities. This is done in a pre-pass to keep the MIR |
| // read-only so that we can do global analyses on the MIR in the process (e.g. |
| // `Place::ty()`). |
| let optimizations = { |
| let mut optimization_finder = OptimizationFinder::new(body, tcx); |
| optimization_finder.visit_body(body); |
| optimization_finder.optimizations |
| }; |
| |
| // Then carry out those optimizations. |
| MutVisitor::visit_body(&mut InstCombineVisitor { optimizations, tcx }, body); |
| } |
| } |
| |
| pub struct InstCombineVisitor<'tcx> { |
| optimizations: OptimizationList<'tcx>, |
| tcx: TyCtxt<'tcx>, |
| } |
| |
| impl<'tcx> MutVisitor<'tcx> for InstCombineVisitor<'tcx> { |
| fn tcx(&self) -> TyCtxt<'tcx> { |
| self.tcx |
| } |
| |
| fn visit_rvalue(&mut self, rvalue: &mut Rvalue<'tcx>, location: Location) { |
| if self.optimizations.and_stars.remove(&location) { |
| debug!("replacing `&*`: {:?}", rvalue); |
| let new_place = match rvalue { |
| Rvalue::Ref(_, _, place) => { |
| if let &[ref proj_l @ .., proj_r] = place.projection.as_ref() { |
| place.projection = self.tcx().intern_place_elems(&[proj_r]); |
| |
| Place { |
| // Replace with dummy |
| local: mem::replace(&mut place.local, Local::new(0)), |
| projection: self.tcx().intern_place_elems(proj_l), |
| } |
| } else { |
| unreachable!(); |
| } |
| } |
| _ => bug!("Detected `&*` but didn't find `&*`!"), |
| }; |
| *rvalue = Rvalue::Use(Operand::Copy(new_place)) |
| } |
| |
| if let Some(constant) = self.optimizations.arrays_lengths.remove(&location) { |
| debug!("replacing `Len([_; N])`: {:?}", rvalue); |
| *rvalue = Rvalue::Use(Operand::Constant(box constant)); |
| } |
| |
| if let Some(operand) = self.optimizations.unneeded_equality_comparison.remove(&location) { |
| debug!("replacing {:?} with {:?}", rvalue, operand); |
| *rvalue = Rvalue::Use(operand); |
| } |
| |
| if let Some(place) = self.optimizations.unneeded_deref.remove(&location) { |
| debug!("unneeded_deref: replacing {:?} with {:?}", rvalue, place); |
| *rvalue = Rvalue::Use(Operand::Copy(place)); |
| } |
| |
| self.super_rvalue(rvalue, location) |
| } |
| } |
| |
| struct MutatingUseVisitor { |
| has_mutating_use: bool, |
| local_to_look_for: Local, |
| } |
| |
| impl MutatingUseVisitor { |
| fn has_mutating_use_in_stmt(local: Local, stmt: &Statement<'tcx>, location: Location) -> bool { |
| let mut _self = Self { has_mutating_use: false, local_to_look_for: local }; |
| _self.visit_statement(stmt, location); |
| _self.has_mutating_use |
| } |
| } |
| |
| impl<'tcx> Visitor<'tcx> for MutatingUseVisitor { |
| fn visit_local(&mut self, local: &Local, context: PlaceContext, _: Location) { |
| if *local == self.local_to_look_for { |
| self.has_mutating_use |= context.is_mutating_use(); |
| } |
| } |
| } |
| |
| /// Finds optimization opportunities on the MIR. |
| struct OptimizationFinder<'b, 'tcx> { |
| body: &'b Body<'tcx>, |
| tcx: TyCtxt<'tcx>, |
| optimizations: OptimizationList<'tcx>, |
| } |
| |
| impl OptimizationFinder<'b, 'tcx> { |
| fn new(body: &'b Body<'tcx>, tcx: TyCtxt<'tcx>) -> OptimizationFinder<'b, 'tcx> { |
| OptimizationFinder { body, tcx, optimizations: OptimizationList::default() } |
| } |
| |
| fn find_deref_of_address(&mut self, rvalue: &Rvalue<'tcx>, location: Location) -> Option<()> { |
| // Look for the sequence |
| // |
| // _2 = &_1; |
| // ... |
| // _5 = (*_2); |
| // |
| // which we can replace the last statement with `_5 = _1;` to avoid the load of `_2`. |
| if let Rvalue::Use(op) = rvalue { |
| let local_being_derefed = match op.place()?.as_ref() { |
| PlaceRef { local, projection: [ProjectionElem::Deref] } => Some(local), |
| _ => None, |
| }?; |
| |
| let stmt_index = location.statement_index; |
| // Look behind for statement that assigns the local from a address of operator. |
| // 6 is chosen as a heuristic determined by seeing the number of times |
| // the optimization kicked in compiling rust std. |
| let lower_index = stmt_index.saturating_sub(6); |
| let statements_to_look_in = self.body.basic_blocks()[location.block].statements |
| [lower_index..stmt_index] |
| .iter() |
| .rev(); |
| for stmt in statements_to_look_in { |
| match &stmt.kind { |
| // Exhaustive match on statements to detect conditions that warrant we bail out of the optimization. |
| rustc_middle::mir::StatementKind::Assign(box (l, r)) |
| if l.local == local_being_derefed => |
| { |
| match r { |
| // Looking for immutable reference e.g _local_being_deref = &_1; |
| Rvalue::Ref( |
| _, |
| // Only apply the optimization if it is an immutable borrow. |
| BorrowKind::Shared, |
| place_taken_address_of, |
| ) => { |
| self.optimizations |
| .unneeded_deref |
| .insert(location, *place_taken_address_of); |
| return Some(()); |
| } |
| |
| // We found an assignment of `local_being_deref` that is not an immutable ref, e.g the following sequence |
| // _2 = &_1; |
| // _3 = &5 |
| // _2 = _3; <-- this means it is no longer valid to replace the last statement with `_5 = _1;` |
| // _5 = (*_2); |
| _ => return None, |
| } |
| } |
| |
| // Inline asm can do anything, so bail out of the optimization. |
| rustc_middle::mir::StatementKind::LlvmInlineAsm(_) => return None, |
| |
| // Check that `local_being_deref` is not being used in a mutating way which can cause misoptimization. |
| rustc_middle::mir::StatementKind::Assign(box (_, _)) |
| | rustc_middle::mir::StatementKind::Coverage(_) |
| | rustc_middle::mir::StatementKind::Nop |
| | rustc_middle::mir::StatementKind::FakeRead(_, _) |
| | rustc_middle::mir::StatementKind::StorageLive(_) |
| | rustc_middle::mir::StatementKind::StorageDead(_) |
| | rustc_middle::mir::StatementKind::Retag(_, _) |
| | rustc_middle::mir::StatementKind::AscribeUserType(_, _) |
| | rustc_middle::mir::StatementKind::SetDiscriminant { .. } => { |
| if MutatingUseVisitor::has_mutating_use_in_stmt( |
| local_being_derefed, |
| stmt, |
| location, |
| ) { |
| return None; |
| } |
| } |
| } |
| } |
| } |
| Some(()) |
| } |
| |
| fn find_unneeded_equality_comparison(&mut self, rvalue: &Rvalue<'tcx>, location: Location) { |
| // find Ne(_place, false) or Ne(false, _place) |
| // or Eq(_place, true) or Eq(true, _place) |
| if let Rvalue::BinaryOp(op, l, r) = rvalue { |
| let const_to_find = if *op == BinOp::Ne { |
| false |
| } else if *op == BinOp::Eq { |
| true |
| } else { |
| return; |
| }; |
| // (const, _place) |
| if let Some(o) = self.find_operand_in_equality_comparison_pattern(l, r, const_to_find) { |
| self.optimizations.unneeded_equality_comparison.insert(location, o.clone()); |
| } |
| // (_place, const) |
| else if let Some(o) = |
| self.find_operand_in_equality_comparison_pattern(r, l, const_to_find) |
| { |
| self.optimizations.unneeded_equality_comparison.insert(location, o.clone()); |
| } |
| } |
| } |
| |
| fn find_operand_in_equality_comparison_pattern( |
| &self, |
| l: &Operand<'tcx>, |
| r: &'a Operand<'tcx>, |
| const_to_find: bool, |
| ) -> Option<&'a Operand<'tcx>> { |
| let const_ = l.constant()?; |
| if const_.literal.ty == self.tcx.types.bool |
| && const_.literal.val.try_to_bool() == Some(const_to_find) |
| { |
| if r.place().is_some() { |
| return Some(r); |
| } |
| } |
| |
| None |
| } |
| } |
| |
| impl Visitor<'tcx> for OptimizationFinder<'b, 'tcx> { |
| fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) { |
| if let Rvalue::Ref(_, _, place) = rvalue { |
| if let PlaceRef { local, projection: &[ref proj_base @ .., ProjectionElem::Deref] } = |
| place.as_ref() |
| { |
| // The dereferenced place must have type `&_`. |
| let ty = Place::ty_from(local, proj_base, self.body, self.tcx).ty; |
| if let ty::Ref(_, _, Mutability::Not) = ty.kind() { |
| self.optimizations.and_stars.insert(location); |
| } |
| } |
| } |
| |
| if let Rvalue::Len(ref place) = *rvalue { |
| let place_ty = place.ty(&self.body.local_decls, self.tcx).ty; |
| if let ty::Array(_, len) = place_ty.kind() { |
| let span = self.body.source_info(location).span; |
| let constant = Constant { span, literal: len, user_ty: None }; |
| self.optimizations.arrays_lengths.insert(location, constant); |
| } |
| } |
| |
| let _ = self.find_deref_of_address(rvalue, location); |
| |
| self.find_unneeded_equality_comparison(rvalue, location); |
| |
| self.super_rvalue(rvalue, location) |
| } |
| } |
| |
| #[derive(Default)] |
| struct OptimizationList<'tcx> { |
| and_stars: FxHashSet<Location>, |
| arrays_lengths: FxHashMap<Location, Constant<'tcx>>, |
| unneeded_equality_comparison: FxHashMap<Location, Operand<'tcx>>, |
| unneeded_deref: FxHashMap<Location, Place<'tcx>>, |
| } |