compiler/rustc_monomorphize/src/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_middle::mir::{
  10     self,
  11     visit::{TyContext, Visitor},
  12     Constant, ConstantKind, Local, LocalDecl, Location,
  13 };
  14 use rustc_middle::query::Providers;
  15 use rustc_middle::ty::{
  16     self,
  17     subst::SubstsRef,
  18     visit::{TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor},
  19     Const, Ty, TyCtxt, UnusedGenericParams,
  20 };
  21 use rustc_span::symbol::sym;
  22 use std::ops::ControlFlow;
  23
  24 use crate::errors::UnusedGenericParamsHint;
  25
  26 /// Provide implementations of queries relating to polymorphization analysis.
  27 pub fn provide(providers: &mut Providers) {
  28     providers.unused_generic_params = unused_generic_params;
  29 }
  30
  31 /// Determine which generic parameters are used by the instance.
  32 ///
  33 /// Returns a bitset where bits representing unused parameters are set (`is_empty` indicates all
  34 /// parameters are used).
  35 fn unused_generic_params<'tcx>(
  36     tcx: TyCtxt<'tcx>,
  37     instance: ty::InstanceDef<'tcx>,
  38 ) -> UnusedGenericParams {
  39     assert!(instance.def_id().is_local());
  40
  41     if !tcx.sess.opts.unstable_opts.polymorphize {
  42         // If polymorphization disabled, then all parameters are used.
  43         return UnusedGenericParams::new_all_used();
  44     }
  45
  46     let def_id = instance.def_id();
  47     // Exit early if this instance should not be polymorphized.
  48     if !should_polymorphize(tcx, def_id, instance) {
  49         return UnusedGenericParams::new_all_used();
  50     }
  51
  52     let generics = tcx.generics_of(def_id);
  53     debug!(?generics);
  54
  55     // Exit early when there are no parameters to be unused.
  56     if generics.count() == 0 {
  57         return UnusedGenericParams::new_all_used();
  58     }
  59
  60     // Create a bitset with N rightmost ones for each parameter.
  61     let generics_count: u32 =
  62         generics.count().try_into().expect("more generic parameters than can fit into a `u32`");
  63     let mut unused_parameters = UnusedGenericParams::new_all_unused(generics_count);
  64     debug!(?unused_parameters, "(start)");
  65
  66     mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters);
  67     debug!(?unused_parameters, "(after default)");
  68
  69     // Visit MIR and accumulate used generic parameters.
  70     let body = match tcx.hir().body_const_context(def_id.expect_local()) {
  71         // Const functions are actually called and should thus be considered for polymorphization
  72         // via their runtime MIR.
  73         Some(ConstContext::ConstFn) | None => tcx.optimized_mir(def_id),
  74         Some(_) => tcx.mir_for_ctfe(def_id),
  75     };
  76     let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters };
  77     vis.visit_body(body);
  78     debug!(?unused_parameters, "(end)");
  79
  80     // Emit errors for debugging and testing if enabled.
  81     if !unused_parameters.all_used() {
  82         emit_unused_generic_params_error(tcx, def_id, generics, &unused_parameters);
  83     }
  84
  85     unused_parameters
  86 }
  87
  88 /// Returns `true` if the instance should be polymorphized.
  89 fn should_polymorphize<'tcx>(
  90     tcx: TyCtxt<'tcx>,
  91     def_id: DefId,
  92     instance: ty::InstanceDef<'tcx>,
  93 ) -> bool {
  94     // If an instance's MIR body is not polymorphic then the modified substitutions that are
  95     // derived from polymorphization's result won't make any difference.
  96     if !instance.has_polymorphic_mir_body() {
  97         return false;
  98     }
  99
 100     // Don't polymorphize intrinsics or virtual calls - calling `instance_mir` will panic.
 101     if matches!(instance, ty::InstanceDef::Intrinsic(..) | ty::InstanceDef::Virtual(..)) {
 102         return false;
 103     }
 104
 105     // Foreign items have no bodies to analyze.
 106     if tcx.is_foreign_item(def_id) {
 107         return false;
 108     }
 109
 110     // Make sure there is MIR available.
 111     match tcx.hir().body_const_context(def_id.expect_local()) {
 112         Some(ConstContext::ConstFn) | None if !tcx.is_mir_available(def_id) => {
 113             debug!("no mir available");
 114             return false;
 115         }
 116         Some(_) if !tcx.is_ctfe_mir_available(def_id) => {
 117             debug!("no ctfe mir available");
 118             return false;
 119         }
 120         _ => true,
 121     }
 122 }
 123
 124 /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy
 125 /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should
 126 /// be `true` if the item that `unused_generic_params` was invoked on is a closure.
 127 #[instrument(level = "debug", skip(tcx, def_id, generics, unused_parameters))]
 128 fn mark_used_by_default_parameters<'tcx>(
 129     tcx: TyCtxt<'tcx>,
 130     def_id: DefId,
 131     generics: &'tcx ty::Generics,
 132     unused_parameters: &mut UnusedGenericParams,
 133 ) {
 134     match tcx.def_kind(def_id) {
 135         DefKind::Closure | DefKind::Generator => {
 136             for param in &generics.params {
 137                 debug!(?param, "(closure/gen)");
 138                 unused_parameters.mark_used(param.index);
 139             }
 140         }
 141         DefKind::Mod
 142         | DefKind::Struct
 143         | DefKind::Union
 144         | DefKind::Enum
 145         | DefKind::Variant
 146         | DefKind::Trait
 147         | DefKind::TyAlias
 148         | DefKind::ForeignTy
 149         | DefKind::TraitAlias
 150         | DefKind::AssocTy
 151         | DefKind::TyParam
 152         | DefKind::Fn
 153         | DefKind::Const
 154         | DefKind::ConstParam
 155         | DefKind::Static(_)
 156         | DefKind::Ctor(_, _)
 157         | DefKind::AssocFn
 158         | DefKind::AssocConst
 159         | DefKind::Macro(_)
 160         | DefKind::ExternCrate
 161         | DefKind::Use
 162         | DefKind::ForeignMod
 163         | DefKind::AnonConst
 164         | DefKind::InlineConst
 165         | DefKind::OpaqueTy
 166         | DefKind::ImplTraitPlaceholder
 167         | DefKind::Field
 168         | DefKind::LifetimeParam
 169         | DefKind::GlobalAsm
 170         | DefKind::Impl { .. } => {
 171             for param in &generics.params {
 172                 debug!(?param, "(other)");
 173                 if let ty::GenericParamDefKind::Lifetime = param.kind {
 174                     unused_parameters.mark_used(param.index);
 175                 }
 176             }
 177         }
 178     }
 179
 180     if let Some(parent) = generics.parent {
 181         mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
 182     }
 183 }
 184
 185 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
 186 /// parameter which was unused.
 187 #[instrument(level = "debug", skip(tcx, generics))]
 188 fn emit_unused_generic_params_error<'tcx>(
 189     tcx: TyCtxt<'tcx>,
 190     def_id: DefId,
 191     generics: &'tcx ty::Generics,
 192     unused_parameters: &UnusedGenericParams,
 193 ) {
 194     let base_def_id = tcx.typeck_root_def_id(def_id);
 195     if !tcx.has_attr(base_def_id, sym::rustc_polymorphize_error) {
 196         return;
 197     }
 198
 199     let fn_span = match tcx.opt_item_ident(def_id) {
 200         Some(ident) => ident.span,
 201         _ => tcx.def_span(def_id),
 202     };
 203
 204     let mut param_spans = Vec::new();
 205     let mut param_names = Vec::new();
 206     let mut next_generics = Some(generics);
 207     while let Some(generics) = next_generics {
 208         for param in &generics.params {
 209             if unused_parameters.is_unused(param.index) {
 210                 debug!(?param);
 211                 let def_span = tcx.def_span(param.def_id);
 212                 param_spans.push(def_span);
 213                 param_names.push(param.name.to_string());
 214             }
 215         }
 216
 217         next_generics = generics.parent.map(|did| tcx.generics_of(did));
 218     }
 219
 220     tcx.sess.emit_err(UnusedGenericParamsHint { span: fn_span, param_spans, param_names });
 221 }
 222
 223 /// Visitor used to aggregate generic parameter uses.
 224 struct MarkUsedGenericParams<'a, 'tcx> {
 225     tcx: TyCtxt<'tcx>,
 226     def_id: DefId,
 227     unused_parameters: &'a mut UnusedGenericParams,
 228 }
 229
 230 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
 231     /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
 232     /// a closure, generator or constant).
 233     #[instrument(level = "debug", skip(self, def_id, substs))]
 234     fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
 235         let instance = ty::InstanceDef::Item(def_id);
 236         let unused = self.tcx.unused_generic_params(instance);
 237         debug!(?self.unused_parameters, ?unused);
 238         for (i, arg) in substs.iter().enumerate() {
 239             let i = i.try_into().unwrap();
 240             if unused.is_used(i) {
 241                 arg.visit_with(self);
 242             }
 243         }
 244         debug!(?self.unused_parameters);
 245     }
 246 }
 247
 248 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 249     #[instrument(level = "debug", skip(self, local))]
 250     fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
 251         if local == Local::from_usize(1) {
 252             let def_kind = self.tcx.def_kind(self.def_id);
 253             if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
 254                 // Skip visiting the closure/generator that is currently being processed. This only
 255                 // happens because the first argument to the closure is a reference to itself and
 256                 // that will call `visit_substs`, resulting in each generic parameter captured being
 257                 // considered used by default.
 258                 debug!("skipping closure substs");
 259                 return;
 260             }
 261         }
 262
 263         self.super_local_decl(local, local_decl);
 264     }
 265
 266     fn visit_constant(&mut self, ct: &Constant<'tcx>, location: Location) {
 267         match ct.literal {
 268             ConstantKind::Ty(c) => {
 269                 c.visit_with(self);
 270             }
 271             ConstantKind::Unevaluated(mir::UnevaluatedConst { def, substs: _, promoted }, ty) => {
 272                 // Avoid considering `T` unused when constants are of the form:
 273                 //   `<Self as Foo<T>>::foo::promoted[p]`
 274                 if let Some(p) = promoted {
 275                     if self.def_id == def && !self.tcx.generics_of(def).has_self {
 276                         // If there is a promoted, don't look at the substs - since it will always contain
 277                         // the generic parameters, instead, traverse the promoted MIR.
 278                         let promoted = self.tcx.promoted_mir(def);
 279                         self.visit_body(&promoted[p]);
 280                     }
 281                 }
 282
 283                 Visitor::visit_ty(self, ty, TyContext::Location(location));
 284             }
 285             ConstantKind::Val(_, ty) => Visitor::visit_ty(self, ty, TyContext::Location(location)),
 286         }
 287     }
 288
 289     fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
 290         ty.visit_with(self);
 291     }
 292 }
 293
 294 impl<'a, 'tcx> TypeVisitor<TyCtxt<'tcx>> for MarkUsedGenericParams<'a, 'tcx> {
 295     #[instrument(level = "debug", skip(self))]
 296     fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 297         if !c.has_non_region_param() {
 298             return ControlFlow::Continue(());
 299         }
 300
 301         match c.kind() {
 302             ty::ConstKind::Param(param) => {
 303                 debug!(?param);
 304                 self.unused_parameters.mark_used(param.index);
 305                 ControlFlow::Continue(())
 306             }
 307             ty::ConstKind::Unevaluated(ty::UnevaluatedConst { def, substs })
 308                 if matches!(self.tcx.def_kind(def), DefKind::AnonConst) =>
 309             {
 310                 self.visit_child_body(def, substs);
 311                 ControlFlow::Continue(())
 312             }
 313             _ => c.super_visit_with(self),
 314         }
 315     }
 316
 317     #[instrument(level = "debug", skip(self))]
 318     fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 319         if !ty.has_non_region_param() {
 320             return ControlFlow::Continue(());
 321         }
 322
 323         match *ty.kind() {
 324             ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
 325                 debug!(?def_id);
 326                 // Avoid cycle errors with generators.
 327                 if def_id == self.def_id {
 328                     return ControlFlow::Continue(());
 329                 }
 330
 331                 // Consider any generic parameters used by any closures/generators as used in the
 332                 // parent.
 333                 self.visit_child_body(def_id, substs);
 334                 ControlFlow::Continue(())
 335             }
 336             ty::Param(param) => {
 337                 debug!(?param);
 338                 self.unused_parameters.mark_used(param.index);
 339                 ControlFlow::Continue(())
 340             }
 341             _ => ty.super_visit_with(self),
 342         }
 343     }
 344 }