compiler/rustc_mir/src/monomorphize/polymorphize.rs

   1 //! Polymorphization Analysis
   2 //! =========================
   3 //!
   4 //! This module implements an analysis of functions, methods and closures to determine which
   5 //! generic parameters are unused (and eventually, in what ways generic parameters are used - only
   6 //! for their size, offset of a field, etc.).
   7
   8 use rustc_hir::{def::DefKind, def_id::DefId};
   9 use rustc_index::bit_set::FiniteBitSet;
  10 use rustc_middle::mir::{
  11     visit::{TyContext, Visitor},
  12     Local, LocalDecl, Location,
  13 };
  14 use rustc_middle::ty::{
  15     self,
  16     fold::{TypeFoldable, TypeVisitor},
  17     query::Providers,
  18     subst::SubstsRef,
  19     Const, Ty, TyCtxt,
  20 };
  21 use rustc_span::symbol::sym;
  22 use std::convert::TryInto;
  23 use std::ops::ControlFlow;
  24
  25 /// Provide implementations of queries relating to polymorphization analysis.
  26 pub fn provide(providers: &mut Providers) {
  27     providers.unused_generic_params = unused_generic_params;
  28 }
  29
  30 /// Determine which generic parameters are used by the function/method/closure represented by
  31 /// `def_id`. Returns a bitset where bits representing unused parameters are set (`is_empty`
  32 /// indicates all parameters are used).
  33 fn unused_generic_params(tcx: TyCtxt<'_>, def_id: DefId) -> FiniteBitSet<u32> {
  34     debug!("unused_generic_params({:?})", def_id);
  35
  36     if !tcx.sess.opts.debugging_opts.polymorphize {
  37         // If polymorphization disabled, then all parameters are used.
  38         return FiniteBitSet::new_empty();
  39     }
  40
  41     // Polymorphization results are stored in cross-crate metadata only when there are unused
  42     // parameters, so assume that non-local items must have only used parameters (else this query
  43     // would not be invoked, and the cross-crate metadata used instead).
  44     if !def_id.is_local() {
  45         return FiniteBitSet::new_empty();
  46     }
  47
  48     let generics = tcx.generics_of(def_id);
  49     debug!("unused_generic_params: generics={:?}", generics);
  50
  51     // Exit early when there are no parameters to be unused.
  52     if generics.count() == 0 {
  53         return FiniteBitSet::new_empty();
  54     }
  55
  56     // Exit early when there is no MIR available.
  57     let context = tcx.hir().body_const_context(def_id.expect_local());
  58     match context {
  59         None if !tcx.is_mir_available(def_id) => {
  60             debug!("unused_generic_params: (no mir available) def_id={:?}", def_id);
  61             return FiniteBitSet::new_empty();
  62         }
  63         Some(_) if !tcx.is_ctfe_mir_available(def_id) => {
  64             debug!("unused_generic_params: (no ctfe mir available) def_id={:?}", def_id);
  65             return FiniteBitSet::new_empty();
  66         }
  67         _ => {}
  68     }
  69
  70     // Create a bitset with N rightmost ones for each parameter.
  71     let generics_count: u32 =
  72         generics.count().try_into().expect("more generic parameters than can fit into a `u32`");
  73     let mut unused_parameters = FiniteBitSet::<u32>::new_empty();
  74     unused_parameters.set_range(0..generics_count);
  75     debug!("unused_generic_params: (start) unused_parameters={:?}", unused_parameters);
  76     mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters);
  77     debug!("unused_generic_params: (after default) unused_parameters={:?}", unused_parameters);
  78
  79     // Visit MIR and accumululate used generic parameters.
  80     let body = match context {
  81         None => tcx.optimized_mir(def_id),
  82         // FIXME(oli-obk): since this is solely used for codegen (I think?), should we keep using
  83         // the optimized MIR for `const fn`? Need to adjust the above `is_mir_available` check
  84         // in that case.
  85         Some(_) => tcx.mir_for_ctfe(def_id),
  86     };
  87     let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters };
  88     vis.visit_body(body);
  89     debug!("unused_generic_params: (after visitor) unused_parameters={:?}", unused_parameters);
  90
  91     mark_used_by_predicates(tcx, def_id, &mut unused_parameters);
  92     debug!("unused_generic_params: (end) unused_parameters={:?}", unused_parameters);
  93
  94     // Emit errors for debugging and testing if enabled.
  95     if !unused_parameters.is_empty() {
  96         emit_unused_generic_params_error(tcx, def_id, generics, &unused_parameters);
  97     }
  98
  99     unused_parameters
 100 }
 101
 102 /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy
 103 /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should
 104 /// be `true` if the item that `unused_generic_params` was invoked on is a closure.
 105 fn mark_used_by_default_parameters<'tcx>(
 106     tcx: TyCtxt<'tcx>,
 107     def_id: DefId,
 108     generics: &'tcx ty::Generics,
 109     unused_parameters: &mut FiniteBitSet<u32>,
 110 ) {
 111     if !tcx.is_trait(def_id) && (tcx.is_closure(def_id) || tcx.type_of(def_id).is_generator()) {
 112         for param in &generics.params {
 113             debug!("mark_used_by_default_parameters: (closure/gen) param={:?}", param);
 114             unused_parameters.clear(param.index);
 115         }
 116     } else {
 117         for param in &generics.params {
 118             debug!("mark_used_by_default_parameters: (other) param={:?}", param);
 119             if let ty::GenericParamDefKind::Lifetime = param.kind {
 120                 unused_parameters.clear(param.index);
 121             }
 122         }
 123     }
 124
 125     if let Some(parent) = generics.parent {
 126         mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
 127     }
 128 }
 129
 130 /// Search the predicates on used generic parameters for any unused generic parameters, and mark
 131 /// those as used.
 132 fn mark_used_by_predicates<'tcx>(
 133     tcx: TyCtxt<'tcx>,
 134     def_id: DefId,
 135     unused_parameters: &mut FiniteBitSet<u32>,
 136 ) {
 137     let def_id = tcx.closure_base_def_id(def_id);
 138     let predicates = tcx.explicit_predicates_of(def_id);
 139     debug!("mark_used_by_predicates: predicates_of={:?}", predicates);
 140
 141     let mut current_unused_parameters = FiniteBitSet::new_empty();
 142     // Run to a fixed point to support `where T: Trait<U>, U: Trait<V>`, starting with an empty
 143     // bit set so that this is skipped if all parameters are already used.
 144     while current_unused_parameters != *unused_parameters {
 145         debug!(
 146             "mark_used_by_predicates: current_unused_parameters={:?} = unused_parameters={:?}",
 147             current_unused_parameters, unused_parameters
 148         );
 149         current_unused_parameters = *unused_parameters;
 150
 151         for (predicate, _) in predicates.predicates {
 152             // Consider all generic params in a predicate as used if any other parameter in the
 153             // predicate is used.
 154             let any_param_used = {
 155                 let mut vis = HasUsedGenericParams { unused_parameters };
 156                 predicate.visit_with(&mut vis).is_break()
 157             };
 158
 159             if any_param_used {
 160                 let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters };
 161                 predicate.visit_with(&mut vis);
 162             }
 163         }
 164     }
 165
 166     if let Some(parent) = predicates.parent {
 167         mark_used_by_predicates(tcx, parent, unused_parameters);
 168     }
 169 }
 170
 171 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
 172 /// parameter which was unused.
 173 fn emit_unused_generic_params_error<'tcx>(
 174     tcx: TyCtxt<'tcx>,
 175     def_id: DefId,
 176     generics: &'tcx ty::Generics,
 177     unused_parameters: &FiniteBitSet<u32>,
 178 ) {
 179     debug!("emit_unused_generic_params_error: def_id={:?}", def_id);
 180     let base_def_id = tcx.closure_base_def_id(def_id);
 181     if !tcx
 182         .get_attrs(base_def_id)
 183         .iter()
 184         .any(|a| tcx.sess.check_name(a, sym::rustc_polymorphize_error))
 185     {
 186         return;
 187     }
 188
 189     debug!("emit_unused_generic_params_error: unused_parameters={:?}", unused_parameters);
 190     let fn_span = match tcx.opt_item_name(def_id) {
 191         Some(ident) => ident.span,
 192         _ => tcx.def_span(def_id),
 193     };
 194
 195     let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters");
 196
 197     let mut next_generics = Some(generics);
 198     while let Some(generics) = next_generics {
 199         for param in &generics.params {
 200             if unused_parameters.contains(param.index).unwrap_or(false) {
 201                 debug!("emit_unused_generic_params_error: param={:?}", param);
 202                 let def_span = tcx.def_span(param.def_id);
 203                 err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name));
 204             }
 205         }
 206
 207         next_generics = generics.parent.map(|did| tcx.generics_of(did));
 208     }
 209
 210     err.emit();
 211 }
 212
 213 /// Visitor used to aggregate generic parameter uses.
 214 struct MarkUsedGenericParams<'a, 'tcx> {
 215     tcx: TyCtxt<'tcx>,
 216     def_id: DefId,
 217     unused_parameters: &'a mut FiniteBitSet<u32>,
 218 }
 219
 220 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
 221     /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
 222     /// a closure, generator or constant).
 223     fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
 224         let unused = self.tcx.unused_generic_params(def_id);
 225         debug!(
 226             "visit_child_body: unused_parameters={:?} unused={:?}",
 227             self.unused_parameters, unused
 228         );
 229         for (i, arg) in substs.iter().enumerate() {
 230             let i = i.try_into().unwrap();
 231             if !unused.contains(i).unwrap_or(false) {
 232                 arg.visit_with(self);
 233             }
 234         }
 235         debug!("visit_child_body: unused_parameters={:?}", self.unused_parameters);
 236     }
 237 }
 238
 239 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 240     fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
 241         debug!("visit_local_decl: local_decl={:?}", local_decl);
 242         if local == Local::from_usize(1) {
 243             let def_kind = self.tcx.def_kind(self.def_id);
 244             if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
 245                 // Skip visiting the closure/generator that is currently being processed. This only
 246                 // happens because the first argument to the closure is a reference to itself and
 247                 // that will call `visit_substs`, resulting in each generic parameter captured being
 248                 // considered used by default.
 249                 debug!("visit_local_decl: skipping closure substs");
 250                 return;
 251             }
 252         }
 253
 254         self.super_local_decl(local, local_decl);
 255     }
 256
 257     fn visit_const(&mut self, c: &&'tcx Const<'tcx>, _: Location) {
 258         c.visit_with(self);
 259     }
 260
 261     fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
 262         ty.visit_with(self);
 263     }
 264 }
 265
 266 impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 267     fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 268         debug!("visit_const: c={:?}", c);
 269         if !c.has_param_types_or_consts() {
 270             return ControlFlow::CONTINUE;
 271         }
 272
 273         match c.val {
 274             ty::ConstKind::Param(param) => {
 275                 debug!("visit_const: param={:?}", param);
 276                 self.unused_parameters.clear(param.index);
 277                 ControlFlow::CONTINUE
 278             }
 279             ty::ConstKind::Unevaluated(def, _, Some(p))
 280                 // Avoid considering `T` unused when constants are of the form:
 281                 //   `<Self as Foo<T>>::foo::promoted[p]`
 282                 if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self =>
 283             {
 284                 // If there is a promoted, don't look at the substs - since it will always contain
 285                 // the generic parameters, instead, traverse the promoted MIR.
 286                 let promoted = self.tcx.promoted_mir(def.did);
 287                 self.visit_body(&promoted[p]);
 288                 ControlFlow::CONTINUE
 289             }
 290             ty::ConstKind::Unevaluated(def, unevaluated_substs, None)
 291                 if self.tcx.def_kind(def.did) == DefKind::AnonConst =>
 292             {
 293                 self.visit_child_body(def.did, unevaluated_substs);
 294                 ControlFlow::CONTINUE
 295             }
 296             _ => c.super_visit_with(self),
 297         }
 298     }
 299
 300     fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 301         debug!("visit_ty: ty={:?}", ty);
 302         if !ty.has_param_types_or_consts() {
 303             return ControlFlow::CONTINUE;
 304         }
 305
 306         match *ty.kind() {
 307             ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
 308                 debug!("visit_ty: def_id={:?}", def_id);
 309                 // Avoid cycle errors with generators.
 310                 if def_id == self.def_id {
 311                     return ControlFlow::CONTINUE;
 312                 }
 313
 314                 // Consider any generic parameters used by any closures/generators as used in the
 315                 // parent.
 316                 self.visit_child_body(def_id, substs);
 317                 ControlFlow::CONTINUE
 318             }
 319             ty::Param(param) => {
 320                 debug!("visit_ty: param={:?}", param);
 321                 self.unused_parameters.clear(param.index);
 322                 ControlFlow::CONTINUE
 323             }
 324             _ => ty.super_visit_with(self),
 325         }
 326     }
 327 }
 328
 329 /// Visitor used to check if a generic parameter is used.
 330 struct HasUsedGenericParams<'a> {
 331     unused_parameters: &'a FiniteBitSet<u32>,
 332 }
 333
 334 impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a> {
 335     type BreakTy = ();
 336
 337     fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 338         debug!("visit_const: c={:?}", c);
 339         if !c.has_param_types_or_consts() {
 340             return ControlFlow::CONTINUE;
 341         }
 342
 343         match c.val {
 344             ty::ConstKind::Param(param) => {
 345                 if self.unused_parameters.contains(param.index).unwrap_or(false) {
 346                     ControlFlow::CONTINUE
 347                 } else {
 348                     ControlFlow::BREAK
 349                 }
 350             }
 351             _ => c.super_visit_with(self),
 352         }
 353     }
 354
 355     fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 356         debug!("visit_ty: ty={:?}", ty);
 357         if !ty.has_param_types_or_consts() {
 358             return ControlFlow::CONTINUE;
 359         }
 360
 361         match ty.kind() {
 362             ty::Param(param) => {
 363                 if self.unused_parameters.contains(param.index).unwrap_or(false) {
 364                     ControlFlow::CONTINUE
 365                 } else {
 366                     ControlFlow::BREAK
 367                 }
 368             }
 369             _ => ty.super_visit_with(self),
 370         }
 371     }
 372 }