1 //! Performs various peephole optimizations.
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::{
9 visit::{MutVisitor, Visitor},
12 use rustc_middle::mir::{
13 BinOp, Body, BorrowKind, Constant, Local, Location, Operand, Place, PlaceRef, ProjectionElem,
16 use rustc_middle::ty::{self, TyCtxt};
19 pub struct InstCombine;
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.
27 let mut optimization_finder = OptimizationFinder::new(body, tcx);
28 optimization_finder.visit_body(body);
29 optimization_finder.optimizations
32 if !optimizations.is_empty() {
33 // Then carry out those optimizations.
34 MutVisitor::visit_body(&mut InstCombineVisitor { optimizations, tcx }, body);
39 pub struct InstCombineVisitor<'tcx> {
40 optimizations: OptimizationList<'tcx>,
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)
52 impl<'tcx> MutVisitor<'tcx> for InstCombineVisitor<'tcx> {
53 fn tcx(&self) -> TyCtxt<'tcx> {
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]);
67 local: mem::replace(&mut place.local, Local::new(0)),
68 projection: self.tcx().intern_place_elems(proj_l),
74 _ => bug!("Detected `&*` but didn't find `&*`!"),
76 *rvalue = Rvalue::Use(Operand::Copy(new_place))
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));
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);
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));
100 // We do not call super_rvalue as we are not interested in any other parts of the tree
104 struct MutatingUseVisitor {
105 has_mutating_use: bool,
106 local_to_look_for: Local,
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
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();
125 /// Finds optimization opportunities on the MIR.
126 struct OptimizationFinder<'b, 'tcx> {
127 body: &'b Body<'tcx>,
129 optimizations: OptimizationList<'tcx>,
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() }
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 {
143 // Look for the sequence
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),
156 let mut dead_locals_seen = vec![];
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]
167 for stmt in statements_to_look_in {
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 =>
174 // Looking for immutable reference e.g _local_being_deref = &_1;
177 // Only apply the optimization if it is an immutable borrow.
179 place_taken_address_of,
181 // Make sure that the place has not been marked dead
182 if dead_locals_seen.contains(&place_taken_address_of.local) {
188 .insert(location, *place_taken_address_of);
192 // We found an assignment of `local_being_deref` that is not an immutable ref, e.g the following sequence
195 // _2 = _3; <-- this means it is no longer valid to replace the last statement with `_5 = _1;`
201 // Inline asm can do anything, so bail out of the optimization.
202 rustc_middle::mir::StatementKind::LlvmInlineAsm(_) => return None,
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)
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(
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 {
240 } else if *op == BinOp::Eq {
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());
250 else if let Some(o) =
251 self.find_operand_in_equality_comparison_pattern(r, l, const_to_find)
253 self.optimizations.unneeded_equality_comparison.insert(location, o.clone());
258 fn find_operand_in_equality_comparison_pattern(
261 r: &'a Operand<'tcx>,
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)
268 if r.place().is_some() {
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);
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);
298 let _ = self.find_deref_of_address(rvalue, location);
300 self.find_unneeded_equality_comparison(rvalue, location);
302 // We do not call super_rvalue as we are not interested in any other parts of the tree
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>>,
314 impl<'tcx> OptimizationList<'tcx> {
315 fn is_empty(&self) -> bool {
320 unneeded_equality_comparison,
324 && arrays_lengths.is_empty()
325 && unneeded_equality_comparison.is_empty()
326 && unneeded_deref.is_empty()