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