compiler/rustc_mir_transform/src/instcombine.rs

   1 //! Performs various peephole optimizations.
   2
   3 use crate::MirPass;
   4 use rustc_hir::Mutability;
   5 use rustc_middle::mir::{
   6     BinOp, Body, Constant, ConstantKind, LocalDecls, Operand, Place, ProjectionElem, Rvalue,
   7     SourceInfo, Statement, StatementKind, Terminator, TerminatorKind, UnOp,
   8 };
   9 use rustc_middle::ty::{self, layout::TyAndLayout, ParamEnv, ParamEnvAnd, SubstsRef, Ty, TyCtxt};
  10 use rustc_span::symbol::{sym, Symbol};
  11
  12 pub struct InstCombine;
  13
  14 impl<'tcx> MirPass<'tcx> for InstCombine {
  15     fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
  16         sess.mir_opt_level() > 0
  17     }
  18
  19     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
  20         let ctx = InstCombineContext {
  21             tcx,
  22             local_decls: &body.local_decls,
  23             param_env: tcx.param_env_reveal_all_normalized(body.source.def_id()),
  24         };
  25         for block in body.basic_blocks.as_mut() {
  26             for statement in block.statements.iter_mut() {
  27                 match statement.kind {
  28                     StatementKind::Assign(box (_place, ref mut rvalue)) => {
  29                         ctx.combine_bool_cmp(&statement.source_info, rvalue);
  30                         ctx.combine_ref_deref(&statement.source_info, rvalue);
  31                         ctx.combine_len(&statement.source_info, rvalue);
  32                     }
  33                     _ => {}
  34                 }
  35             }
  36
  37             ctx.combine_primitive_clone(
  38                 &mut block.terminator.as_mut().unwrap(),
  39                 &mut block.statements,
  40             );
  41             ctx.combine_intrinsic_assert(
  42                 &mut block.terminator.as_mut().unwrap(),
  43                 &mut block.statements,
  44             );
  45         }
  46     }
  47 }
  48
  49 struct InstCombineContext<'tcx, 'a> {
  50     tcx: TyCtxt<'tcx>,
  51     local_decls: &'a LocalDecls<'tcx>,
  52     param_env: ParamEnv<'tcx>,
  53 }
  54
  55 impl<'tcx> InstCombineContext<'tcx, '_> {
  56     fn should_combine(&self, source_info: &SourceInfo, rvalue: &Rvalue<'tcx>) -> bool {
  57         self.tcx.consider_optimizing(|| {
  58             format!("InstCombine - Rvalue: {:?} SourceInfo: {:?}", rvalue, source_info)
  59         })
  60     }
  61
  62     /// Transform boolean comparisons into logical operations.
  63     fn combine_bool_cmp(&self, source_info: &SourceInfo, rvalue: &mut Rvalue<'tcx>) {
  64         match rvalue {
  65             Rvalue::BinaryOp(op @ (BinOp::Eq | BinOp::Ne), box (a, b)) => {
  66                 let new = match (op, self.try_eval_bool(a), self.try_eval_bool(b)) {
  67                     // Transform "Eq(a, true)" ==> "a"
  68                     (BinOp::Eq, _, Some(true)) => Some(Rvalue::Use(a.clone())),
  69
  70                     // Transform "Ne(a, false)" ==> "a"
  71                     (BinOp::Ne, _, Some(false)) => Some(Rvalue::Use(a.clone())),
  72
  73                     // Transform "Eq(true, b)" ==> "b"
  74                     (BinOp::Eq, Some(true), _) => Some(Rvalue::Use(b.clone())),
  75
  76                     // Transform "Ne(false, b)" ==> "b"
  77                     (BinOp::Ne, Some(false), _) => Some(Rvalue::Use(b.clone())),
  78
  79                     // Transform "Eq(false, b)" ==> "Not(b)"
  80                     (BinOp::Eq, Some(false), _) => Some(Rvalue::UnaryOp(UnOp::Not, b.clone())),
  81
  82                     // Transform "Ne(true, b)" ==> "Not(b)"
  83                     (BinOp::Ne, Some(true), _) => Some(Rvalue::UnaryOp(UnOp::Not, b.clone())),
  84
  85                     // Transform "Eq(a, false)" ==> "Not(a)"
  86                     (BinOp::Eq, _, Some(false)) => Some(Rvalue::UnaryOp(UnOp::Not, a.clone())),
  87
  88                     // Transform "Ne(a, true)" ==> "Not(a)"
  89                     (BinOp::Ne, _, Some(true)) => Some(Rvalue::UnaryOp(UnOp::Not, a.clone())),
  90
  91                     _ => None,
  92                 };
  93
  94                 if let Some(new) = new && self.should_combine(source_info, rvalue) {
  95                     *rvalue = new;
  96                 }
  97             }
  98
  99             _ => {}
 100         }
 101     }
 102
 103     fn try_eval_bool(&self, a: &Operand<'_>) -> Option<bool> {
 104         let a = a.constant()?;
 105         if a.literal.ty().is_bool() { a.literal.try_to_bool() } else { None }
 106     }
 107
 108     /// Transform "&(*a)" ==> "a".
 109     fn combine_ref_deref(&self, source_info: &SourceInfo, rvalue: &mut Rvalue<'tcx>) {
 110         if let Rvalue::Ref(_, _, place) = rvalue {
 111             if let Some((base, ProjectionElem::Deref)) = place.as_ref().last_projection() {
 112                 if let ty::Ref(_, _, Mutability::Not) =
 113                     base.ty(self.local_decls, self.tcx).ty.kind()
 114                 {
 115                     // The dereferenced place must have type `&_`, so that we don't copy `&mut _`.
 116                 } else {
 117                     return;
 118                 }
 119
 120                 if !self.should_combine(source_info, rvalue) {
 121                     return;
 122                 }
 123
 124                 *rvalue = Rvalue::Use(Operand::Copy(Place {
 125                     local: base.local,
 126                     projection: self.tcx.intern_place_elems(base.projection),
 127                 }));
 128             }
 129         }
 130     }
 131
 132     /// Transform "Len([_; N])" ==> "N".
 133     fn combine_len(&self, source_info: &SourceInfo, rvalue: &mut Rvalue<'tcx>) {
 134         if let Rvalue::Len(ref place) = *rvalue {
 135             let place_ty = place.ty(self.local_decls, self.tcx).ty;
 136             if let ty::Array(_, len) = *place_ty.kind() {
 137                 if !self.should_combine(source_info, rvalue) {
 138                     return;
 139                 }
 140
 141                 let literal = ConstantKind::from_const(len, self.tcx);
 142                 let constant = Constant { span: source_info.span, literal, user_ty: None };
 143                 *rvalue = Rvalue::Use(Operand::Constant(Box::new(constant)));
 144             }
 145         }
 146     }
 147
 148     fn combine_primitive_clone(
 149         &self,
 150         terminator: &mut Terminator<'tcx>,
 151         statements: &mut Vec<Statement<'tcx>>,
 152     ) {
 153         let TerminatorKind::Call { func, args, destination, target, .. } = &mut terminator.kind
 154         else { return };
 155
 156         // It's definitely not a clone if there are multiple arguments
 157         if args.len() != 1 {
 158             return;
 159         }
 160
 161         let Some(destination_block) = *target
 162         else { return };
 163
 164         // Only bother looking more if it's easy to know what we're calling
 165         let Some((fn_def_id, fn_substs)) = func.const_fn_def()
 166         else { return };
 167
 168         // Clone needs one subst, so we can cheaply rule out other stuff
 169         if fn_substs.len() != 1 {
 170             return;
 171         }
 172
 173         // These types are easily available from locals, so check that before
 174         // doing DefId lookups to figure out what we're actually calling.
 175         let arg_ty = args[0].ty(self.local_decls, self.tcx);
 176
 177         let ty::Ref(_region, inner_ty, Mutability::Not) = *arg_ty.kind()
 178         else { return };
 179
 180         if !inner_ty.is_trivially_pure_clone_copy() {
 181             return;
 182         }
 183
 184         let trait_def_id = self.tcx.trait_of_item(fn_def_id);
 185         if trait_def_id.is_none() || trait_def_id != self.tcx.lang_items().clone_trait() {
 186             return;
 187         }
 188
 189         if !self.tcx.consider_optimizing(|| {
 190             format!(
 191                 "InstCombine - Call: {:?} SourceInfo: {:?}",
 192                 (fn_def_id, fn_substs),
 193                 terminator.source_info
 194             )
 195         }) {
 196             return;
 197         }
 198
 199         let Some(arg_place) = args.pop().unwrap().place()
 200         else { return };
 201
 202         statements.push(Statement {
 203             source_info: terminator.source_info,
 204             kind: StatementKind::Assign(Box::new((
 205                 *destination,
 206                 Rvalue::Use(Operand::Copy(
 207                     arg_place.project_deeper(&[ProjectionElem::Deref], self.tcx),
 208                 )),
 209             ))),
 210         });
 211         terminator.kind = TerminatorKind::Goto { target: destination_block };
 212     }
 213
 214     fn combine_intrinsic_assert(
 215         &self,
 216         terminator: &mut Terminator<'tcx>,
 217         _statements: &mut Vec<Statement<'tcx>>,
 218     ) {
 219         let TerminatorKind::Call { func, target, .. } = &mut terminator.kind  else { return; };
 220         let Some(target_block) = target else { return; };
 221         let func_ty = func.ty(self.local_decls, self.tcx);
 222         let Some((intrinsic_name, substs)) = resolve_rust_intrinsic(self.tcx, func_ty) else {
 223             return;
 224         };
 225         // The intrinsics we are interested in have one generic parameter
 226         if substs.is_empty() {
 227             return;
 228         }
 229         let ty = substs.type_at(0);
 230
 231         // Check this is a foldable intrinsic before we query the layout of our generic parameter
 232         let Some(assert_panics) = intrinsic_assert_panics(intrinsic_name) else { return; };
 233         let Ok(layout) = self.tcx.layout_of(self.param_env.and(ty)) else { return; };
 234         if assert_panics(self.tcx, self.param_env.and(layout)) {
 235             // If we know the assert panics, indicate to later opts that the call diverges
 236             *target = None;
 237         } else {
 238             // If we know the assert does not panic, turn the call into a Goto
 239             terminator.kind = TerminatorKind::Goto { target: *target_block };
 240         }
 241     }
 242 }
 243
 244 fn intrinsic_assert_panics<'tcx>(
 245     intrinsic_name: Symbol,
 246 ) -> Option<fn(TyCtxt<'tcx>, ParamEnvAnd<'tcx, TyAndLayout<'tcx>>) -> bool> {
 247     fn inhabited_predicate<'tcx>(
 248         _tcx: TyCtxt<'tcx>,
 249         param_env_and_layout: ParamEnvAnd<'tcx, TyAndLayout<'tcx>>,
 250     ) -> bool {
 251         let (_param_env, layout) = param_env_and_layout.into_parts();
 252         layout.abi.is_uninhabited()
 253     }
 254     fn zero_valid_predicate<'tcx>(
 255         tcx: TyCtxt<'tcx>,
 256         param_env_and_layout: ParamEnvAnd<'tcx, TyAndLayout<'tcx>>,
 257     ) -> bool {
 258         !tcx.permits_zero_init(param_env_and_layout)
 259     }
 260     fn mem_uninitialized_valid_predicate<'tcx>(
 261         tcx: TyCtxt<'tcx>,
 262         param_env_and_layout: ParamEnvAnd<'tcx, TyAndLayout<'tcx>>,
 263     ) -> bool {
 264         !tcx.permits_uninit_init(param_env_and_layout)
 265     }
 266
 267     match intrinsic_name {
 268         sym::assert_inhabited => Some(inhabited_predicate),
 269         sym::assert_zero_valid => Some(zero_valid_predicate),
 270         sym::assert_mem_uninitialized_valid => Some(mem_uninitialized_valid_predicate),
 271         _ => None,
 272     }
 273 }
 274
 275 fn resolve_rust_intrinsic<'tcx>(
 276     tcx: TyCtxt<'tcx>,
 277     func_ty: Ty<'tcx>,
 278 ) -> Option<(Symbol, SubstsRef<'tcx>)> {
 279     if let ty::FnDef(def_id, substs) = *func_ty.kind() {
 280         if tcx.is_intrinsic(def_id) {
 281             return Some((tcx.item_name(def_id), substs));
 282         }
 283     }
 284     None
 285 }